# Virtually Geometric

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

29 Likes

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

1 Like

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.

 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

4 Likes

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

1 Like

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.

4 Likes

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.

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.
6 Likes

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

1 Like

An update.

Now supporting arbitrary GLTF with multiple materials and hierarchies.

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.

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.

10 Likes

1 Like

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

5 Likes

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

3 Likes

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

2 Likes

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).

1 Like

hi

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

1 Like

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.

2 Likes

ok, thanks for taking the time to reply.

1 Like

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

3 Likes

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