Rendering Algorithm:
Fluffy is a attempt at building a rendering algorithm where instead of the run time being decided by model complexity, it is decided by the size of the screen. This is done by hierarchically traversing models stored as octrees, and occluding as many nodes and their children as possible.
The renderer begins by projecting the root node to the screen and checking if the node is occluded. If it isn't we check if the node is of a single pixels size. If it is, we render it, otherwise we split it into its 8 children, and we recursively apply the above algorithm in a front to back order. This way, we are only traversing nodes which are visible, and if a node isn't visible, it and its children are all rejected, preventing us from doing needless checks. The above algorithm's run time is mostly dependent on the size of the screen instead of the geometry since it only traverses nodes which are visible, and renders nodes as soon as they are of a single pixel size. The pseudo code can be found below:
void RenderOctree(v3 NodeCenter, f32 NodeRadius, octree* Node)
{
i32 MinX, MaxX, MinY, MaxY;
ProjectNodesCorners(NodeCenter, NodeRadius, &MinX, &MaxX, &MinY, &MaxY);
MinX = ClipMinX(MinX);
MaxX = ClipMinX(MaxX);
MinY = ClipMinX(MinY);
MaxY = ClipMinX(MaxY);
if (IsNodeOccluded(MinX, MaxX, MinY, MaxY))
{
return;
}
f32 ChildRadius = NodeRadius / 2.0f;
v3 ChildrenCenters[8] = GetChildrenCenters(NodeCenter, NodeRadius);
// NOTE: Sort children centers such that we traverse them front to back
f32 Keys[8] =
{
Length(ChildrenCenters[0]),
Length(ChildrenCenters[1]),
Length(ChildrenCenters[2]),
Length(ChildrenCenters[3]),
Length(ChildrenCenters[4]),
Length(ChildrenCenters[5]),
Length(ChildrenCenters[6]),
Length(ChildrenCenters[7]),
};
u32 Order = {0, 1, 2, 3, 4, 5, 6, 7};
SortLeastToGreatest(Keys, Order);
for (u32 ChildId = 0; ChildId < 8; ++ChildId)
{
u32 SortedId = Order[ChildId];
RenderOctree(ChildrenCenters[SortedId], ChildRadius, Node->Children[SortedId]);
}
}I visualized how many recursions the algorithm above needs to perform for every pixel and we can see the results below (different colors represent different number of recursions):
Algorithm Optimizations
Quicker projection calculation
In the above renderer pseudo code, we treat each octree node as a cube and project its 8 corners onto the screen to calculate the min/max bounds that the cube takes up on screen. Doing so is a very slow operation, and had to be executed millions of times per frame. To speed this process up, I pretend every oriented octree node is a actually the smallest screen facing cube that encapsulates that node. I would then calculate which corners of this cube correspond to the min/max values of the nodes projected space.
Minimizing Sorting:
Given that the program traverses millions of octree nodes a frame, it can't feasibly sort every nodes children to be ordered front to back. At the point I decided to examine this issue, the sorting was taking roughly 25% of the programs run time. If a octree node is rotated, the program finds the largest encapsulating box that is facing the camera, and renders that box instead. When drawing these nodes, I realized most of the time, the sorted order of the parent is the same as the child's, but I also identified cases where that isn't true shown in the images below:
I realized later that the only times that the traversal order for a parent changes for the children is when the faces of the parent which are visible are different than the faces of the children. This change of visible faces only happens when the parent node intersects the x or y axis, while the child node does not as can be seen in the below picture:
Orthographic Mode:
The last optimization is to try to render as many nodes using orthographic projection as possible. When performing perspective projection, we have to store world positions of nodes and perform divisions to project nodes to the screen. This means we use up more memory and have to wait for long latency instructions which can stall our CPU pipelines. So Fluffy checks if a nodes backface projects to the same pixels as the front face, which means that the node is so small that the effects of perspective projection are no longer visible. This is shown in the below images:
SIMD Optimizations
Processing 8 nodes at a time
Originally, I tried to apply SIMD on the original algorithm which was outlined above, which meant Fluffy was processing one node at a time. This resulted in lots of horizontal operations like finding the min/max value in a AVX vector. I decided to instead process 8 nodes at a time doing as much of it in SIMD as possible, then switching to scalar for things like checking node occlusion. This helped make the code more parallel and easier to implement in SIMD.
Screen as 8x8 blocks
The algorithm touches many pixels to render the octree to the screen. I knew that every row of pixels touched by a node would result in a cache miss once we had to jump to the next row of pixels. I tried to group pixels into 8x8 blocks, each being a 1 bit coverage mask instead of a 32 bit depth value so that I could lower the amount of cache misses in coverage buffer access. This however incurs a performance hit to generate masks whenever we loop per pixel since sometimes our projected cube partially covers a 8x8 block of pixels. The performance results can be seen below:
Surprisingly, this method made the performance worse because of the extra instructions it took to generate the pixel masks. In the end, I decided to use a 8 bit coverage mask with a scalar loop to check for node occlusion to avoid any extra operations to generate masks, while shrinking my rendered buffer by a factor of 4 (from 32 bit depth).
