Hey all, so I did some experimenting to try and see what rendered outputs of various methods give me. I'm focusing right now on making sure my rendered image renders hard edges properly and I want it to do so in the least amount of octree traversals as possible. My octree render function looks a little like this:
void RenderOctree(v3 Center, octree* Node, u32 Level)
{
b32 IsLeaf = CheckIfLeaf(Node);
i32 MinX, MaxX, MinY, MaxY;
f32 FMinX, FMaxX, FMinY, FMaxY;
f32 MinZ, MaxZ;
ApproximateNodeSize(Center, Level, &FMinX, &FMaxX, &FMinY, &FMaxY, &MinZ, &MaxZ);
if (MaxZ <= 0.0f)
{
// NOTE: Node is behind camera, cull it
return;
}
MinX = SomeRoundingMethod(FMinX);
MaxX = SomeRoundingMethod(FMaxX);
MinY = SomeRoundingMethod(FMinY);
MaxY = SomeRoundingMethod(FMaxY);
if (NodeIsPixelSize())
{
// Render the node as a dot
v2 ProjectedCenter = ProjectPoint(Center);
u32 PixelId = SomeRoundingMethod(ProjectedCenter.y)*ScreenX + SomeRoundingMethod(ProjectedCenter.x);
f32 Depth = DepthMap[PixelId];
if (Depth > Center.z)
{
RenderState->DepthMap[PixelId] = Center.z;
}
return;
}
if (MinX >= ScreenX || MinY >= ScreenX || MaxX <= 0 || MaxY <= 0)
{
// NOTE: Node is outside of the screen, don't render it or its children
return;
}
MinX = Max(0, MinX);
MinY = Max(0, MinY);
MaxX = Min(ScreenX, MaxX);
MaxY = Min(ScreenX, MaxY);
b32 IsOccluded;
{
IsOccluded = true;
f32* DepthRow = DepthMap + MinY*ScreenX + MinX;
for (i32 Y = MinY; Y < MaxY; ++Y)
{
f32* Depth = DepthRow;
for (i32 X = MinX; X < MaxX; ++X)
{
if (*Depth > MinZ)
{
// NOTE: We aren't occluded
IsOccluded = false;
goto EndLoop;
}
++Depth;
}
DepthRow += ScreenX;
}
}
EndLoop:
if (IsOccluded)
{
return;
}
for (u32 CurrNodeId = 0; CurrNodeId < 8; ++CurrNodeId)
{
u32 SortedNodeId = Indicies[GetFrontBackSortId(CurrNodeId)];
if (Node->Children[SortedNodeId])
{
RenderOctree(GetChildCenter(Node, SortedNodeId), Node->Children[NodeId], Level + 1);
}
}
}
So in the above code, we first approximate the nodes size on screen and get its float min/max xy values, we then use some sort of rounding method to convert those values to ints, we check if the nodes size is a pixel (and render if it is), otherwise we clip the node, check for occlusion, and traverse its children. For the various experiments I tried, I used the above code and only modified the rounding method for min/max, the rounding method for rendering the 1 pixel node, and whether the occlusion check was inclusive/exclusive of max x,y values.
The first methods I tried render single pixel nodes by projecting and flooring the center of the node to convert to a integer pair, which represents the pixel that node takes up. The reason we floor the center of the node is because flooring corresponds to rendering the node to the pixel it covers the most.
Method 1:
Render Info: Num Traversals: 5056321 NumRejected: 562733 NumRendered: 3656973
This method takes the floor of FMinX/Y values and the ceiling of FMaxX/Y values to get the pixels a node intersects (for occlusion checks). The idea here is that we try to be conservative with the pixels the node is expected to cover. This method produces renders with sharp edges but traverses a ton of extra nodes to do so. We also check if a node is ready to render by using the FMin/Max values. The node must satisfy (FMaxX - FMinX) <= 1.0f and (FMaxY - FMinY) <= 1.0f to be rendered.
Method 2:
Render Info: Num Traversals: 3406177 NumRejected: 646950 NumRendered: 2193007
Here we round the FMin/Max values to the nearest integer to calculate the integer Min/Max values. If you look at some of the edges in the renderer, they have pixel crawling (random dots sticking out). Method 1 didn't have this artifact because it would fill in the extra line where the dots stick out (the edges were thicker). In this method, we get a ton of nodes that get rounded down to be inside the edge instead of outside, and thus are rejected and prevented from being rendered correctly, which gives us the pixel crawling. We again use the FMin/Max values to check if a node is small enough to be rendered.
Method 3:
Render Info: Num Traversals: 3705105 NumRejected: 299739 NumRendered: 2784177
Here we use integer Min/Max values to decide if a node is small enough to be considered a single pixel in size. We check if MaxX - MinX <= 1 and MaxY - MinY <= 1. We take the floor of our FMin/FMax values to generate the min/max values, and we make our occlusion check inclusively check pixels at MaxX and MaxY coordinates. The result has lots of holes and pixel crawling which seems to be caused by improper coverage of the nodes, due to the rounding method. I figured that being inclusive with the bounds check would make the node size correspond to the actual pixels the node takes up but I guess this isn't the case.
Method 4:
Render Info: Num Traversals: 2544985 NumRejected: 340016 NumRendered: 1777500
Here we use integer Min/Max values to decide when to render a node and we calculate it by rounding FMin/Max to the nearest integer. The idea is that the previous method wasn't capturing the node size properly so maybe rounding provides the actual node size that the nodes take up on screen. We again use integer Min/Max to decide if a node is ready to be rendered. The result looks almost perfect, but it still has a little pixel crawling occurring for hard edges.
Method 5:
Render Info: Num Traversals: 2686033 NumRejected: 1045595 NumRendered: 1184283
This method (like method 4) uses integer Min/Max to decide when a node should be rendered, and it calculates the Min/Max values by rounding to the nearest integer. The only difference is, if a node's MinX==MaxX or MinY == MaxY, then the node is discarded completely and not rendered. This seems to cleanup Method 4's image and make all the edges sharp.
Method 5 seems to be the most correct so far. And best of all, it also has a similar number of traversals as Method 4, so we aren't being overly conservative with approximating the nodes size when converting the coordinates to integers. One thing that bothers me with this method is the fact that nodes which are 0 pixels wide or tall. Of course those nodes should be discarded since they have 0 pixels covered but it feels odd that they exist in the first place and have to be removed. I guess that's just a sacrifice that has to happen because of weird rounding errors that can occur.
The other thing that bothers me with this method and the other methods which use integer min/max values to calculate if a node should be rendered is the resulting level map that gets rendered. So when I render each node, I also render into a separate buffer a color for the given level (recursion depth) that the node is. So we have a color for level 1, another color for level 2, and so on. If we use float FMin/FMax values to decide if a node should be rendered, our level map looks like this:
If we use integer Min/Max, our level map looks like this:
Now there are cases where a node which is 1 pixel by 1 pixel can actually color 4 pixels if it happens to have its center where 4 pixel corners intersect. So from that logic, it makes sense for the node to be rendered based off of integer min/max values. But from the above images, we would expect layers of levels moving farther away from the camera like what we get when we use float FMin/FMax values to decide if a node is small enough to render.
So my question is, whats the right answer here? Should my rendering method generate 0 sized nodes that need to be discarded? Should it also have the weird level map as shown above? Or are there some other rounding methods that make more sense theoretically/experimentally?