Nanite.cpp LOD cut / error projection

[JMS55]

I've been looking at improving my DAG building based on what you've done in nanite.cpp recently.

One thing that stood out to me is that the way I'm using the LOD group bounds is definitely wrong. What you're doing with keeping the error and bounding sphere separate, and forcing parent bounding spheres to contain their children in addition to error monotonic seems correct to me (side note: doing this properly seems like a 183 page thesis https://people.inf.ethz.ch/emo/DoctThesisFiles/fischer05.pdf, but your boundsMerge() seems to work?).

The thing I'm now confused about, is how do you select the DAG cut? What is this section https://github.com/zeux/meshoptimizer/blob/master/demo/nanite.cpp#L603-L615 of code, and boundsError() doing exactly? Some kind of distance-based heuristic it seems, but I'm not quite sure.

I've also looked into what Nanite does (the slides don't really explain, they just mention projecting the error within the group sphere somehow), and the Batched Multi Triangulation paper (figure 3.15, unclear to me what the logic is here https://d-nb.info/997062789/34#page=48), but overall I'm not exactly sure how to project error to the screen in a way that ensures a single DAG cut.

I'm wondering if you have any insight into this area, especially since you're familiar with QEM and the underlying meaning of the error.

[zeux]

doing this properly seems like a 183 page thesis

The difference between "smallest" and "conservative" tends to be like that :)

What is this section of code, and boundsError() doing exactly

Because I lack a full fledged viewer that does LOD selection, I have a function to compute a DAG cut from a given viewpoint for testing purposes, to be able to visually inspect the resulting mesh. boundsError would be a function similar to the one you'd use at runtime in a proper renderer, that returns an approximation of the worst case error as seen from the viewpoint. This code would be absent from a typical mesh builder pipeline, it's just necessary for the demo.

What I'm doing right now is computing the distance to sphere surface from the camera viewpoint, and dividing the error returned by meshopt_simplify by that distance. This is a little bit incorrect: ideally it would account for camera field of view, and perhaps account for the perspective distortion which could help select better LOD in screen corners. I usually like selection algorithms that are invariant to camera rotation, but if the goal is to select an LOD with a given pixel error a more precise method that Nanite uses may be relevant.

UE5 Nanite computation is similar in principle, but mechanically different - it takes into account cases where the sphere is clipped by znear, and it takes camera orientation into account, so the computation is not camera rotation invariant. Conceptually I think it's the same as your reference to fig 3.15, even though I find that specific figure odd as no lines or points there connect to sphere radius :) they compute the projected sphere radius in pixels, invert it (that way they get the length that would project to one pixel, using the same coordinates that the sphere is in), and compare that to the error (which is also in linear units in the same coordinates that the sphere is in).

The "single DAG cut" should be a property of boundsError being monotonic. This is why the conditions I have are structured the way they are: as long as boundsError is monotonic through the DAG for any viewpoint, the selection should be unambiguous. I believe the formula I have atm is monotonic (distance from camera to merged sphere will be <= distance to any sphere inside; error of merged group will be >= error of any group inside; dividing monotonically increasing error by monotonically decreasing distance gives a monotonically increasing value).

Note that the monotonicity should also be maintained for the version Nanite is using: a smaller sphere (contained within the larger sphere) would project to a smaller number of pixels. So it's the same criteria, just computed more precisely.

On further review I think there might be a couple issues in my code though:

• boundsError divides error by distance if distance > 0, which can probably underflow to +inf and make the error case non-monotonic. I should probably return +inf for error when camera is inside the cluster, or clamp this to near plane instead of 0.
• When the camera is inside the leaf cluster bounds, the condition "self error <= threshold && parent error > threshold" will not activate: there is no cluster with the error that is small enough by this metric!

Perhaps a more correct formula would be "return bounds.error / max(d, z_near)"; this should fix both issues and keep monotonicity. And to make it more production ready I would also divide by tan(camera_fov/2), and I guess move the pixel scaler from threshold to the boundsError function. I'll adjust this tomorrow.

Note that all of this is just about converting the error to screen space (and as such not really dependent on whether simplification uses quadrics or something else, but is dependent on the simplifier returning something distance-like). The error returned by meshopt_simplify/WithAttributes should be considered to just be distance (as long as meshopt_SimplifyErrorAbsolute is used), as such it is correct to divide that value by the distance-to-meshlet when the camera is using perspective projection, or compare it to some other distance. What happens with attributes is a little complicated to explain, it's summarized here https://github.com/zeux/meshoptimizer/blob/master/README.md#advanced-simplification; UE uses essentially the same attribute error computation as meshopt last time I checked. The implementation in either case is not really guaranteeing the property documened in the link above, but that's a convenient way to think about it, and the best thing attribute quadrics can compute as far as I am aware.

[zeux]

Oh I should say for clarity: when the sphere is small, centered in the view (view-space XY close to 0) and does not intersect the near plane, my approach and Nanite's full fledged computation with projection should yield the same selection criteria (once you correct for camera field of view, pixel error conversion and the like). They are only different when the sphere is significantly off-center such that perspective distortion is applied, cuts the near plane (in which case my code would generally assume "camera is inside" and yield somewhat different results), or is pretty close to the viewpoint (in which case my code would be a bit more pessimistic about the error vs the correct computation that Nanite is doing). This is why I say "similar in principle" above: the logic is more or less the same, but I choose to approximate the camera projection mechanics.

If you want to replicate the entire Nanite computation I think it would be sufficient to implement the figure 3.15 from the paper you linked, solving it as a 2D trigonometry problem. You'd probably need to handle the near clipping case separately.

[zeux]

Also this is solving a slightly different problem, but actually Nanite code looks like a simplified subset of https://jcgt.org/published/0002/02/05/ to me, down to variable names (B/H/T), so maybe that's where they got the derivation from.

[JMS55]

Thanks for all the thoughts!

I think that yeah, so long as:

1. Error is monotonic
2. Group LOD bounds contain all child LOD bounds

Then finding the closest point (P) on the LOD sphere, projecting a sphere with center = P and radius = error, and then checking if the projected size is < 1 pixel works for determining the LOD. Before reading your post I was confused why that would be valid, but I understand now that if a parent bounding sphere contains all child bounding spheres, then the distance to the parent bounding sphere is always less than distance to the child, and it ends up working out once you project the error.

The tricky part like you said is if you're inside the LOD bounding sphere (distance to closest point < 0). For leaf clusters you have to accept them - that close, there is nothing simpler that won't have visible error. For non-leaf clusters, it's trickier. I think you probably want to reject the cluster by returning infinity like you said.

I'm going to play around with this when I get a chance, but I feel like I have a better idea of what's going on now, and what the MBT paper was trying to say. Thanks for the insights!

[JMS55]

Also this is solving a slightly different problem, but actually Nanite code looks like a simplified subset of https://jcgt.org/published/0002/02/05/ to me, down to variable names (B/H/T), so maybe that's where they got the derivation from.

I'm also using this already (with the formula from your blog) for occlusion culling bounds, so I can just reuse it and add a check for clipping :) https://github.com/bevyengine/bevy/blob/d016e52843ad62f8e635f34ad02994bdeb2b2559/crates/bevy_pbr/src/meshlet/cull_clusters.wgsl#L161-L190

[JMS55]

I couldn't quite figure out the projecting an error-sized sphere centered on the LOD sphere's closest point to the camera. It's unclear how to handle the case where the camera is intersecting the LOD sphere - I'm not convinced rejecting the meshlet and using a finer LOD makes sense. It also seems like a strange method to me to begin with, and the paper does not explain it well or link to something else that does.

Instead I tried mimicking the other method you wrote about:

1. Projecting the LOD sphere to screen space
2. Dividing the object-space LOD sphere radius by the projected size to establish how many meters correspond to 1 pixel on screen

• E.g. if radius = 10m and projected_size = 4px, then 10/4 = 2.5m/px
• I'm not sure this is valid... Don't think there's a linear relationship here

4. Comparing the object-space simplification error (no longer divided by 2, just the value meshopt gives directly) to the value from the previous step, essentially checking if the error is >1 pixel on screen

• E.g. Continuing the previous example - error has to be < 2.5m to be considered imperceptible, as then it would be < 1 pixel

However it A) is greatly underestimating the visible error, and B) feels weird to do this, instead of just projecting a sphere based on the error directly...

Can you speak more about this paragraph you wrote? I'm possibly doing something wrong, but I also don't understand why the inversion step is valid.

they compute the projected sphere radius in pixels, invert it (that way they get the length that would project to one pixel, using the same coordinates that the sphere is in), and compare that to the error (which is also in linear units in the same coordinates that the sphere is in).

---

In case I didn't explain well, here's the code I wrote as a reference, specifically lod_error_is_imperceptible() for the runtime projection, and compute_lod_group_data() for the builder section (pretty much copied from your code).
bevyengine/bevy@main...JMS55:bevy:meshlet-builder-improvements-redux2

[zeux]

Can you speak more about this paragraph you wrote?

I should say I am hesitant to comment too much on this because my description is based on my reading of Nanite's code, and it's certainly imprecise in a few places. For example, using the projected sphere size based on my blog isn't correct - the "simplified subset" I was referring to just concerns the boundary vertices they use for the projection math, but the way you get from them to the projected bounds (in my blog) is by projecting them, which is correct for that task, but this task is different, and what they do in this case is they only use these boundary points to compute the solid angle of the sphere, and then use the distance-to-sphere-boundary-along-view-axis (aka view-space Z minus radius, or maybe plus, I forget where their Z axis points) to get the view-space equivalent of this in the worst case. This is not quite the same, especially for spheres that are close to camera, and could be part of the problem here.

I don't love their method in general, it's complex to derive and I think it's still an approximation due to some shortcuts, but I guess what I am saying is the best reference for that specific method is probably their source, not my description :)

I'm not convinced rejecting the meshlet and using a finer LOD makes sense. It also seems like a strange method to me to begin with, and the paper does not explain it well or link to something else that does.

Rejecting the meshlet isn't quite correct, but it's close. The more correct way is (I think) the math I updated in the latest code, which clamps the distance to znear. It's still using radial distances but I think just using view space Z makes this sufficiently precise in practice. If I get some time in the next few days I could try that out in the branch you linked - I'm surprised it didn't work for you but I don't think we mean the same things by the same terms, for example I wasn't quite suggesting projecting the sphere with the radius equal to the error using the projected bounds math.

Aside of that, maybe some intuition for what any of this code should be doing would help; I don't agree that this is a strange method and while the paper certainly doesn't do a good job at covering any of this, I don't think it matters. Let me try to describe this differently.

Imagine you had a perfect value for the error that meant the Hausdorff distance between original and simplified mesh. QEM does not give you that, attributes complicate the picture, etc., so all of this (Nanite implementation included) is an approximation and there's fudge factors involved, but let's suppose we had that perfect value.

That value is a scalar. This means that somewhere there are two points on the two surfaces with this value as a distance, but you don't know where this segment is.

When you have a merged bounding sphere, you know that any points of the original or simplified mesh are inside that sphere, so you know that this worst case segment is somewhere within it and it has the length you know, but the endpoints are unknown.

What you want, then, is to see if this segment with the worst case length can be projected on the screen with a >1px projected segment length. Without knowing where this segment is, you have to assume the worst.

If the camera position is inside that sphere, the worst case for a segment length is error / znear (here and elsewhere I omit the projection into screen space, because it's just a scale on top, and focus on the projection math). This is because every vertex position is divided by the view-space Z; to maximize the projected length, you need to minimize each Z of the endpoint but have them be >= znear because the segment gets clipped (and gets shorter) otherwise. This is exactly what my updated code will compute :) (again with a caveat that for perfect projection math you want to get the distance-to-sphere-surface-along-view-vector, not the radial distance).

The only case where this is completely impossible is the case where the sphere is cut by the near plane such that the cut can never contain a segment of this length. In this case I believe Nanite's code will compute a more granular error bound, whereas simply dividing error by znear in this case overestimates it. This case should be very rare, because it means that the center of the meshlet is behind znear plane, so you're likely looking at the mesh surface from inside (or looking from outside but camera is inside some extremely concave region).

If the distance to sphere surface along view vector (aka view space Z) is d which is larger than znear, then to get the worst case projected segment length you need to assume the sphere is oriented such that the segment is parallel to the camera plane (again, consistent Z) and both segment endpoints touch the sphere boundary. Unless the segment length is comparable in side to the sphere radius/diameter, this will mean this segment's Z is close to the distance to sphere surface. Maybe there's a neat way to approximate this a little better still (e.g. error / (distance - error * 0.5f) might be closer and fairly conservative), Nanite doesn't try to nor should it because as I mentioned above in practice QEM errors are Very Approximate.

Anyway... that's it, that's what that math should be doing. Unreal uses the math I tried to describe to compute the world space size of this worst case segment that'd map to a pixel, unless I'm missing something crucial I like the formulation that directly computes [an approximation of] the worst case projected size of the error segment contained within the sphere, but it's roughly the same.

[zeux]

But also taking a very brief look at the code, isn't project_view_space_sphere_to_screen_space_aabb returning 0..1 results? I haven't looked at that code closely to check that it matches my blog, but my blog returns the 0..1 results, and I think elsewhere in Bevy's code the results are multiplied by dimensions. So in your code you don't actually have "pixels".

[JMS55]

I wrote out a bunch of stuff, deleted it, wrote more, and deleted that too. I'll leave it here as I don't want to take up too much of your time, but I'm starting to get the shape of this I think. Something about the the closest point on the bounding sphere, and then treating the simplification error as a line along the viewing angle within the sphere. I'm going to have to draw some diagrams and think this over more, but I feel closer to understanding at least. Thanks for taking the time to help me.

---

But also taking a very brief look at the code, isn't project_view_space_sphere_to_screen_space_aabb returning 0..1 results? I haven't looked at that code closely to check that it matches my blog, but my blog returns the 0..1 results, and I think elsewhere in Bevy's code the results are multiplied by dimensions. So in your code you don't actually have "pixels".

Well that would explain it, I totally forgot to multiply by the view size... For some reason I thought it was part of the function already😅. That does make my results look fine (not necessarily good or grounded in logic, but hard to see any position-based deformity due to LODs now).

[JMS55]

Fyi on this line

meshoptimizer/demo/nanite.cpp

Line 112 in 1e48e96

// camera_proj is projection[1][1], or cot(fovy/2); camera_znear is *positive* near plane distance

I think this should be tan(), not cot(), right?

[zeux]

For this direction (camera plane => screen space) it should be cot, because you're simulating the perspective projection matrix transform (which has cot(fovy/2) in the [1][1] element).

If you are doing the inverse math, like going from pixels to units in view space, then you'd multiply by tan (and multiply by Z instead of dividing).

camera_proj is the same as P11 in https://zeux.io/2023/01/12/approximate-projected-bounds/.

[JMS55]

Nvm, cot(x) is the same as 1 / tan(x) 😅.