3
$\begingroup$

I've seen several references to this and related concepts now but I can't find any hard details about these systems, and how they are implemented.

The earliest reference I can find is from the "GPU-driven rendering pipelines" talk by Sebastian Altonen.

enter image description here

But I was made aware of the topic from Nanite information that has surface recently, for example Brian Karis talks about it in the presentation here, but not with many details:

enter image description here

Alex Evans also talked about the concept a bit in his High Performance Graphics 2021 conference keynote, but Dreams (which he worked on) doesn't use triangle meshes, it's a signed distance field system instead:

enter image description here

To summarize what I think I understand:

Mesh vertices, or more generally the geometry representations you have, are apparently grouped in some form ( though I don't know by what algorithm that is done exactly ) into clusters, then culled on the GPU based on bounding volumes of those clusters.

Apparently this concept is well suited for GPU-driven occlusion and frustum culling (why and how?), dynamic LOD (why and how?), and makes it possible to create hierarchical representations of meshes where you can pick the LOD to render not for the whole mesh, but based on single clusters at rendering time (why and how?). Apparently, Nanite pushes this far enough that you can't see any transition between different LODs.

What algorithms are used here for generating these clusters, culling them (particularly occlusion culling), representing them hierarchically, and picking LODs from them?

$\endgroup$
4
$\begingroup$

First, to preface: the reason it's hard to find details about these hierarchical cluster culling systems because they are a still emerging field, at the very cutting edge of real-time rendering development. Only a handful of games/engines have successfully shipped something like this, and mostly not open source (UE5 being a recent exception). It is an area of very active development and research, so there are no standard algorithms; everyone is experimenting and doing it differently. That said, I'll try to give a picture of what this is all about and why people are excited about it. This is going to be kind of a brain dump, but I hope it's somewhat useful.


First of all, why are mesh clusters important? Historically, real-time rendering engines have done things like frustum and occlusion culling, as well as LOD selection and draws, on an object-by-object basis. What an "object" is here, is determined by the engine but would often correspond to a single authored model from a 3D content creation app, or to a scene graph node, or to higher level game logic (e.g. an entity with its own behavior such as a character or vehicle). In other words, object boundaries are not primarily determined by rendering considerations, but by other things entirely.

As games have increased in geometric complexity, the amount of vertices/triangles in an "object" (whatever that means in a given game) have tended to increase. For example, player characters in AAA games might easily have hundreds of thousands of triangles. And we can only make LOD or culling decisions at the object level. If any part of an object is visible, we have to draw the whole thing, which might not be very efficient. When we want to switch LODs, we have to switch it for the whole object at once, which tends to cause visible popping since there are generally only a few discrete LODs stored for any given mesh.

Another effect of increasing geometric complexity is that triangles are typically denser on screen, covering ≲10 pixels each, and often down to just ~1 pixel each for very dense meshes such as AAA characters. Such dense geometry exacerbates various inefficiencies in GPU rasterizers, such that over-rendering (i.e. drawing more triangles than you need to) becomes a more significant performance problem than it was in the past. This is why Nanite uses a compute-based software rasterizer for extremely dense meshes (and falls back to regular hardware rasterization for larger triangles or tricky corner cases, such as triangles that cross the near plane).

Mesh clusters, also known as meshlets, are a way to break down these object-sized meshes into more manageable pieces. The meshlets are a roughly fixed geometry size, such as 64–128 vertices, no matter how big the object they come from. Then we can make rendering decisions per meshlet instead of per object. At a minimum, we can cull per meshlet, which enables us to do things like only render the visible parts of a large object. With some more work we can also make LOD decisions per meshlet, so that we only render parts of an object at high detail that are close enough to need high detail, and farther away parts can be at a lower detail. This also gives us much more fine-grained LOD control; we can transition a mesh from one LOD to another a few meshlets at a time, rather than all at once, reducing the problem of visible pops. To do this we need a way of ensuring that we can have meshlets at different LODs without cracks between them, which is tricky to do; Nanite has a clever approach to this.

Meshlets are also relevant for rendering using mesh shaders, which is a separate topic, although it dovetails well with meshlet-based culling/LOD.

As far as algorithms for building meshlets go: there are lots of ways to do it, but generally you start a meshlet with an arbitrary triangle, then iteratively try to add other triangles that share as many vertices as possible with the triangles already in the meshlet. You might also incorporate some scoring for candidate triangles based on how much they increase the size of the bounding box (favoring smaller boxes) or how much their normals deviate from those already in the meshlet (favoring similar normals). Once you've got enough vertices/triangles to fill the meshlet, you mark them as used, and you start again with a new unmarked triangle. The meshoptimizer library includes a meshlet building algorithm, if you want to take a look at it.

Once you've grouped your triangles into meshlets, you might still have a lot of meshlets, so it can make sense to do the same thing again and group neighboring meshlets together into larger clusters, and so on again hierarchically, forming a tree. Nanite does something along these lines, but also builds simplified representations of each cluster (keeping the boundaries intact) in order to be able to switch LODs without cracks. See the "Brief Analysis of Nanite" article linked at the bottom for more details.

For the SDF-based apps like Dreams and Claybook, I think their "clusters" are just 4×4×4 bricks of SDF, and larger clusters are higher mip levels of the SDF, so that's much simpler to deal with.

For culling on the GPU: the basic idea is you run a compute shader over the list of meshlets (one thread per meshlet). It does the culling calculations (e.g. testing bounding box against frustum, testing normal cone against camera position to eliminate backfacing meshlets) and outputs the list of surviving meshlets into an append buffer. This list becomes the input to an indirect draw or indirect dispatch which renders the visible geometry. This is well-suited for the GPU because it's a massively parallel computation, and there can be a large number of meshlets in the scene.

In the case of a tree of clusters, you start at the root and walk down the tree. At each node you can make the decision to accept the whole node for rasterization (and stop traversal), or cull the whole node, or else recurse to the children. In a compute shader this can be implemented by issuing separate indirect dispatches for each level of the tree, with each level outputting a list of nodes to be processed in the next level. However, Nanite takes a different approach to this with what appears to be a single compute dispatch that uses a ring buffer (maybe?) of nodes to process, and the shaders keep running and popping off nodes to process until the whole thing is done. Nanite also does LOD selection during this phase, as higher levels in the tree represent more simplified LODs, and it stops descending a part of the tree when it reaches a node with low enough LOD error to render it (or if it reaches parts of the tree that are not streamed in at the moment - in which case it can also log a request for that node in another append buffer, to be read back and processed by the CPU streaming code later).

GPU occlusion culling is a pretty interesting algorithm, too. The basic idea is to use last frame's depth buffer as an approximate "initial guess" as to what surfaces are visible or occluded in the new frame, then fix up the errors (things initially marked as occluded that are actually visible) in a second pass. Alex Evans talked about this a bit in the HPG keynote you linked above. This doesn't actually require hierarchical cluster culling, but can be applied even for ordinary object-based culling on the GPU. Basically, while you're traversing your list/tree of meshlets to cull, if they pass the frustum and backfacing tests then you test their bounding box against the HiZ buffer (hierarchical representation of the last frame's Z-buffer - basically a mip chain that stores the min and max Z in each pixel). This is done using the last frame's camera and object transform for that node. If the bounding box is behind the HiZ buffer then that node is culled and traversal stops, but it also gets added to a separate list of occlusion-culled nodes to re-test later. You proceed to rendering all the nodes that passed this first culling pass, then build a new HiZ buffer from the current frame's depth buffer so far. Finally, you re-test all the occlusion-culled nodes against the new HiZ buffer, which lets you find all the ones that were mistakenly culled but are actually visible. Then you resume traversal etc as usual for those nodes, and draw them in a follow-up pass. This second pass usually contains a relatively small number of nodes, in areas where camera or object movement has created a "disocclusion" (a place where previously hidden geometry has been revealed). Finally, the HiZ buffer is updated again and goes forward to repeat the process in the next frame (as well as being potentially used for other purposes, like screen-space ray tracing for lighting).


Further on Nanite specifically, here are some analyses made by third parties (not Epic-associated) looking at Nanite in RenderDoc and reading the source code:

Since UE5 is open-source, you can go and look at the code for Nanite if you want. You have to register with Epic to join their GitHub organization, but then you should be able to access the following links (deep linked to the Nanite source directories within the UE5 GitHub):

Also, some of the Nanite (and Lumen) developers are scheduled to do talks at this summer's SIGGRAPH, where no doubt additional details and history will be discussed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.