Virtually Geometric

[Usnul]

Hey Guys, I’ve been playing with the virtual geometry idea for a couple of weeks now and wanted to share some results.

What is virtual geometry?

• it’s an approximation of real geometry, such that the viewer can’t tell the difference between the “real” geometry and the approximation.

It’s a lot like LOD, but it’s continuous. With typical LOD systems you have pre-defined LOD levels, like you’d have LOD0, LOD1, LOD2 for example where each next level has fewer triangles. Here’s a picture:

The idea is to simplify mesh on the fly such that triangles that are smaller than, say 1 pixel, are removed.

Here’s are a few screenshots for demonstration from my work so far.

What you see here is the “real” source geometry on the left, and on the right is the “virtual” geometry in with debug shader. The source geometry is exactly 100,000 triangles. At this resolution/camera angle virtual geometry actually also has 100,000 triangles. But as we move camera further away, we start to drop triangles.

Here’s we have ~60,000 triangles

A bit further and we get ~10,000 triangles

1000 triangles

That is, it takes GPU to draw 100 of these geometries same amount of effort using my Virtual Geometry system as it does using the original mesh (1000 triangles * 100 = 100,000 same as original geometry).

To stress the earlier point - this LOD is continuous, so you won’t see popping of any kind, and as far as the eye can tell - the mesh will look the same from any angle/distance while actual number of triangles will typically be only a fraction of the original.

The technique isn’t exactly new, it’s been around in various shapes and forms for a long time now. One of the most famous applications is the ROAM algorithm that’s typically used for terrain. Each approach has it’s pros and cons. What I’m doing is much more flexible than ROAM, it works with generic static meshes, but that comes at the engineering cost. My approach, like many others requires special pre-processing of the mesh to create a custom data structure for run-time optimization. As a result, run-time optimization is pretty much instant. The pre-processing takes fairly long right now, around 2s for this geometry.

This is very much a work in progress, and there are still a lot of things to do before it’s ready to be used in production. Still, I think it’s pretty cool, so I wanted to share a bit of the progress

[Ben_Mack]

Looks amazing!
Does your method suffer by draw calls overhead?

[Usnul]

Hey Ben, thanks!

About the draw calls. That’s is one of the main reasons I’m working on this, all geometry with the same material in the scene is drawn with a single draw call. So if you have say, 1000 identical meshes in the scene, instead of having 1000 draw calls - you’d have just one.

Granted, there is a trade-off, that is the memory cost, if you have 1000 instanced meshes - you’d only actually be storing 1 copy of the geometry and a transform matrix for each mesh instance. With virtual geometry you are actually pushing each triangle on the screen to the GPU, so you might end up with higher GPU memory usage.

With that being said, the goal is to keep number of triangles on the screen fairly constant, so that “cost” would be proportional to the screen resolution and not the number of meshes on-screen or their complexity.

[edit] To be clear, there is no “free lunch”, so you still have to build that representation geometry at run-time and that costs CPU/GPU cycles, the goal is to be able to do that fast-enough. Right now I only have a naive CPU-side implementation for that, it works, but it’s not fast and it doesn’t scale so well. But I do have pretty good idea on how to improve on that and move most of the work over the GPU. There is also a lot that you can do to cull triangles before they get pushed to the GPU, and because I use a custom data structure for geometry - I can do more aggressive culling and do it more efficiently than you normal would.

Hope that helps! And thanks for asking

[Harold]

Wow that is absolutely brilliant!

Isn’t this a similar technique as Unreal 5’s Nanite technology? I believe UE5 uses depth fields to approximate geometry complexity, but the end result is pretty much the same if I’m guessing this correctly…

Also… Source available by any chance? I’d love to get my hands on this

[Usnul]

Hey Harold, thanks for the praise!

Isn’t this a similar technique as Unreal 5’s Nanite technology?

I believe so, though since I don’t have access to UE5 source, I don’t know what they did under the hood. You could say that seeing Nanite was a motivation for me to try my hand at this though, I was like “wow, so this can be practical, huh?”

Also… Source available by any chance?

Not at the moment, I plan to make source available at some point, but I don’t think I will be open-sourcing the tech.

By the way, Brian Karis of Epic Games will be presenting Nanite at SIGGRAPH this year, in case someone else is interested in how they achieved their Virtual Geometry.

Until then, there’s not much detail available on their approach.

[Usnul]

A small update, I’ve made a bit of progress on the rendering side, so there’s a bit more to show now. What you see below is 10x10 grid of Lucy model, each one is 100,000 triangles for total of 10,000,000 triangles in the scene.

Virtual Geometry with WebGL

I added a stat display in the right to show how many triangles are actually being drawn each frame, as you can see it never actually gets to 10m and hovers at around 2-3m when we have most of the scene in view. When we zoom in closer - we drop down to as low as just a few tends of thousand triangles.

here are a few more sample camera angles with FPS and geometry stats:

So far the problems seem to be:

• the fact that geometry is being pushed to the GPU every frame - this seems pretty slow in WebGL somehow.
• culling. All of the back-faces and occluded triangles are still sent to the GPU currently, this vastly increases the number of triangles we end up drawing each frame. Based on some papers I read so far, it seems culling could help eliminate as much as 80% of geometry based on the scenes/camera angles. I am doing frustum culling though, so there’s at least that.

[DolphinIQ]

Brilliant work @Usnul ! Very interesting to see where this would bring most benefits. Will have my eye on this for the future

[Usnul]

An update.

Now supporting arbitrary GLTF with multiple materials and hierarchies.

Micron: Virtual Geometry engine for browser

Rewrote rendering part to keep as much of the geometry in GPU memory between frames as possible. The problem is this - it’s fairly easy to build even several million triangle mesh on the CPU in JS, and you can do it relatively fast too, but uploading it to the GPU takes a lot of time comparatively, which is why FPS in my previous demos was not great.

To go around this problem, you want to keep geometry on the GPU instead of building it from scratch every frame. Since geometry is dynamic, you would need geometry shaders for this, but alas - we don’t have that in WebGL.

So… I write my own geometry shader system on top of WebGL! That was quite fun, the result is - much lower communication overhead between CPU and GPU (around 2% of the previous approach) and silky smooth FPS.

As an added benefit, multiple geometry instances take up less memory, as the final result is assembled on the GPU. I’m not sure if you can see it clearly in the video, but FPS hovers around 144 mark throughout the demo. This is with 23 unique materials in the scene and some 100 unique geometries.

In the demo, I set error_bias to 100 around 00:29 seconds mark, this means that the system will simplify geometry until a single triangle covers no less than 100 screen pixels. Or in other words - we’re willing to accept 100 pixels per triangle. This is done to demonstrate simplification in action, since in normal use-case where that error is 1 pixel - you will not see any visible difference (which is the whole point).

Research & Implementation notes

Graph partitioning

Brian’s SIGGRAPH presentation has been very interesting, he’s using METIS library for clustering. I ported METIS to JS, to try it out as well - but I found that my own graph partitioning implementation was more suited for this specific task. It was consistently around 10x faster while optimizing for more relevant things. I might use METIS in the future, as it’s pretty amazing in general, and I did use their graph coarsening/refinement technique (described in their paper) in my own implementation as well.

Geometry shaders

I ended up writing non-indexed geometry shader, with certain limitations. These limitations result in around 5% memory waste as well as minor overdraw at LOD0, but this pretty much entirely disappears at higher LOD levels, so I found it to be acceptable.

Caching

GPU memory is limited, so you can’t always keep the entire scene in the GPU memory. You need a cache, and a way to figure out what to load/evict. Right now I have a very simple caching strategy, which is not well suited for individual geometries larger than around 1,000,000 triangles.

Small instances

The bane of this type of cluster-based system are tiny geometries. If a geometry only has, say 1-2 triangles, you’re just wasting time and resources trying to build a LOD for it and maintaining the runtime representation of that LOD. There are a few of ways to deal with that:

• Just accept it
• Have variable cluster size, to support small geometries with less waste
• Don’t use virtual geometry for small instances
• Merge instances into larger geometries that can be LODed

Small screen-space footprint

When an instance takes up very little space on the screen (a few pixels), the best you can do with the pure cluster-based approach is draw that with a single cluster. Which, in my case would be 128 triangles. Which doesn’t sounds like much, but it quickly goes out of control, as you start having 1000s of instances. Brian in his SIGGRAPH talk presented an interesting solution of blitting pre-rendered impostors directly into the screen buffer, bypassing clusters altogether.

General

This technique is super interesting, but the rendering pipeline is super deep, which makes errors compound, and bugs had to find. I found myself having to write more development/debug tools for this than any other graphics-related projects so far.

[alwxkxk]

Thanks your showcase.

[mrdoob]

@Usnul This is amazing! Do you think you’ll be able to share a live link at some point?

[Usnul]

Definitely!

I’m struggling to find a good example to use though, something with a lot of geometry, and preferably multiple instances of said geometry, preferably something that’s fully opaque and doesn’t have too many thin/small elements (like grass or trees, those are terrible for simplification). I had a roam around of sketchfab, but couldn’t find anything that’s free and fits the bill.

Seeing many copies of an angel is not super impressive

[felixmariotto]

An asteroid field in Saturn rings ? Or the ruins of a castle maybe, with piles of dressed stones ?

[Usnul]

I like the castle idea! I was looking for something like that too, alas, haven’t found anything good so far, either too low poly-count (not useful to demonstrate the technique) or too much aggregate geometry (small thin parts that don’t simplify well, like tree leaves, grass, thin sticks etc).

[vegarringdal]

@Usnul

thousand

hi

Any updates on this project ?
Is this something we can use with threejs now or in the future ?

[Usnul]

Hey @vegarringdal , I have been working more on the tech and it’s now capable of running scenes with billions of triangles at 60+ FPS. However the tech itself was sold to a certain commercial organization, so this will not be open-sourced and will not be available for free.

As for the prospect of this kind of technology being available in three.js, this is something we had a brief talk with @mrdoob and the conclusion is that it’s too complex to be included in three.js. I can imagine someone else creating a virtual geometry library that can be used with three.js in the future, but unless it’s backed by an organization - I don’t believe it would be viable for the foreseeable future as it’s just too complex to be maintained on one person’s enthusiasm and is way too involved for others to be casually involved in.

At the risk of belaboring the point, this is a bit similar with the deep internals of three.js’s rendering code, only a handful of people in the world understand it in sufficient detail to make meaningful changes there and gaining said understanding may require you to spend weeks on learning before you could make some progress.

Anyway, sorry to disappoint, and hope this clears things up a bit.

[vegarringdal]

ok, thanks for taking the time to reply.

[mrdoob]

@Usnul

As for the prospect of this kind of technology being available in three.js, this is something we had a brief talk with @mrdoob and the conclusion is that it’s too complex to be included in three.js.

Probably not in core but I could be an external class, right?

[stanis3d]

Very, very, very great and helpfull!!! Thank you!

[Usnul]

hey guys, here’s a live link

Here’s another version of the same thing with patches colored with random colors to help visualize the technique.

What you see there is a grid of 100x100 angel statues, each 100,000 polygons for a total of exactly 1 billion triangles. I thought it should be enough to prove my point.

main things that have changed since last time I talked about this:

• much better performance
• removed a few limitations, such as supported source maximum geometry size
• full support for all three.js materials

There are some goodies under the hood in there as well, such as:

• accelerated raycasting for free basically, because there’s already a spatially partitioned hierarchy. You get same performacne as with a great quality BVH, but without having to build that separately.
• export of any mesh simplification LOD. You input number of triangles in the desired output mesh - and we get a hierarchy cut that satisfies this constraint. Super fast too.
• used the above, building discrete LOD proxies for a mesh. Say you don’t want to actually use the entire Micron (my Virtual Geometry solution name) rendering stack - you can quickly build any number of LODs from the micron representation. When I say - I mean linear speed with respect to output size, it’s about as fast as you can write to memory
• support of custom geometry attributes
• automatic normal, uv and tangent compression. This is something Unreal’s nanite does as well, for vast majority of meshes - it’s able to reduce normals memory requirements from 12 bytes per vertex, down to just 3 bytes, for UVs and tangents it’s similar. Not that Micron meshes were heavy to begin with, but with this they are around ~30 lighter as well as taking less GPU ram (~40-50% typically) and rendering faster.

Overall it’s hard to compete with C++, threads and native graphics API that has bindless resources as well as compute shaders. But you can get pretty far even with what we have in browser today

PS:
please note that this still is not an open-source project

[mrdoob]

Runs amazingly smooth on a M1 Max!