Spatial Index and Occlusion culling introducing into core

[Usnul]

Spatial Index

Spatial index is necessary when dealing with large scenes, such large scenes are very common in games for example.

Motivation

If you want to do a raycast into the scene - currently you are stuck with a linear search, which is dominated by number of objects and polygons. A spatial index would enable a lot of internal optimizations, such as faster occlusion culling and sorting.

Direct application in the renderer:

Occlusion culling

Good occlusion culling is required for good performance. Point above would help here. There are a lot of techniques that can be utilized further here.

born as a result of this discussion: #13807

[donmccurdy]

Related: https://github.com/mrdoob/three.js/blob/dev/examples/js/Octree.js

I haven’t used that example for any projects yet, and would be curious to hear feedback from those who have. I would say keeping this in core vs. an example is not the first question, but rather let’s measure examples with many dynamic objects and many static objects, and get a better understanding of when and how it helps.

There may not be a one-size-fits-all answer here, adding a renderer.setOcclusionCullingTechnique( octreeCullingHelper ) method to override defaults may be an option, and let users opt into the cost of updating an octree.

[Usnul]

@donmccurdy
When it comes to a spatial index, it has a fairly non-trivial impact on the a lot of entrails of the engine. Lets say you want to do ray tracing - spatial index would make that faster. Let's say you want to do volume queries (such as occlusion culling) - spatial index makes that faster too. Let's say that you go further with visibility culling and put that into Animation system and Sound system - doing that with a plugin solution is going to be a fair bit more complex that with a single solution. I understand your point about updates though, it is not a free solution, and that has to be considered. I have a few suggestions here:

• Spatial index interface. Have several implementations, in the same vein as your suggestion with setOcculusionCullingTechnique. Basic implementation that maintains no extra data structures and just computes on raw mesh data, and additional indices that do maintain a dedicated accelerated data structures.
• Embrace additional overhead of updates to spatial index, such updates are very cheap in largely static geometries and are expensive for largely dynamic geometries. Conversely, for larger scenes it will offer more savings when performing culling and other spatial queries. In some cases it will slow you down, in other cases it will speed you up. You can say that the slowdown is worth it for the speedup.
• Make updates lazy. Have a command queue of some sort and let it build up when no queries are made, can also do some optimizations on a queue, like cancelling update operations if there's a delete operation further in the pipeline or batching some updates.

[donmccurdy]

When it comes to a spatial index, it has a fairly non-trivial impact on the a lot of entrails of the engine.

It certainly can affect internal parts of the engine, but that doesn't mean we need to use a spatial index for every purpose right from the beginning. Start with one or two important use cases — ideally things that can be tested without major internal changes — and quantify the result. This is not a criticism of the idea at all — I just think the right place to start is evaluating Octree or other solutions. See how they perform, what changes would make them more useful or if something entirely different is needed, and proceed from there.

Embrace additional overhead of updates to spatial index, such updates are very cheap in largely static geometries and are expensive for largely dynamic geometries ... You can say that the slowdown is worth it for the speedup.

It will not be worth it if yours is the app being slowed down and someone else's is being sped up. 😉 But the point above about letting people opt into the spatial index does address this fine.

[gkjohnson]

I think this is a valuable addition to THREE, but I don't think it belongs in the core of the library -- primarily because (as has already been mentioned) it doesn't feel like there's a one-size fits all solution. It does bring up the question of "what belongs in THREEjs core", though.

You mentioned that it could afford internal optimizations (presumably meaning it would difficult to write an extension to THREE to do this, atm). Would another solution involve officially exposing some more of THREE.js' internal events to enable a cleaner extension implementation of this? preRender or postRender events for cameras and objects, for example.

[Usnul]

@gkjohnson

Would another solution involve officially exposing some more of THREE.js' internal events to enable a cleaner extension implementation of this?

You got to the heart of the matter. The answer is "no". Currently I work with scenes that have tens of thousands of objects, and just sorting them takes three.js a non-trivial amount of time, then culling takes some, then also updates to animations. So what do I do? - I rebuild the scene every frame. To be more precise I do a diff on currently visible set and remove objects that are no longer visible and add those that have become visible this frame. This is a very ugly solution from my point of view, because I basically say "you know nóthing Three Jay-ess."

The alternative that I propose is to allow thousands and tens of thousands ob objects to be managed on the same scene by three.js, and let it do the optimizations necessary to make it run smoothly.

People talk about the cost and overhead, I don't think there is much thought being put into those statements though. Time overhead is basically inversely proportional to scene complexity, the more complex the scene is - the more you win with a spatial index, the undeniable cost is in memory, but even that is manageable, you can adjust how much of an impact your spatial index will be, to a fairly large degree, you can store a dynamic amount of polygons per spatial index node (e.g. leaf in a tree), or you can opt to manage objects entirely at the level of objects, and even group those.
If you want to have a binary tree of depth 2 to manage 4 groups of scene objects - you could do that, at the cost of maintaining some 7 extra objects (root->(left->(left,right), right->(left,right))). Let's say you have 1 spinning cube on the scene, how much of an overhead is a spatial index going to be? - not nothing. It's going to require you to build said index, and to update the hierarchy of nodes leading to the cube.
Even with a very naive implementation, that will still probably not show up on any profiling though, because the time and space required to do this is too low to register on most samples. If we're talking about a scene with thousands(=n) of objects, we're talking about shaving off (n - log(n)) time to cull the scene at the cost of up-to k*log(n) for updates, where k is number of changed objects.

Why do physics engines, for instance, use spatial indices?

• because it provides a no-brainer speed-up to pretty much all kinds of operations it needs to do, from broad-phase to individual collision resolution.

Why do path tracing/ray tracing renderers use spatial indices?

• because it provides the same speed-up, you go from linear complexity performance to a lograrithmic one.

To my mind this is an argument about what's better, a sequence file as a database, or a b-tree, a sequence file sure uses less memory though, and it sure takes less time to update though, and if you have only a few records - it's avoids a lot of unnecessary overhead and implementation complexity.

Bottom line for me is - I would love to see three.js go down the route of supporting complex scenes with large number of objects, and I have offered to donate fully functioning code to that end for a long while now, the offer still stands. I suggest experiments by other people are required to get a better understanding in others of what the impact would be with respect to use-cases they deep important.

[gkjohnson]

Ha, you don't have to convince me on the value of spatial indexing! Trust me, I want something like this for scenes, too, and understand the benefits. All the use cases you've mentioned are valid.

People talk about the cost and overhead, I don't think there is much thought being put into those statements though.

I don't know if that's fair. The value of spatial indexing is really use case dependent and there are cases where unnecessarily using a tree like that can actually hurt performance. If we're talking about including a spatial index as an option, then I think it's worth talking about what needs to change in THREE in order to support this in a clean, more modular way.

I definitely understand what you're saying about pre- and post- render callbacks not being good enough. I recently had to grapple with a similar, but different, performance issue that I solved by basically rebuilding the scene every frame, as you mentioned, so THREE wouldn't spend time iterating over stuff I already knew it didn't need to (along with a few other use-case specific optimizations). Unfortunately a scene BVH wouldn't have helped me there, but accommodating this type of "customized rendering / scene solution" more cleanly seems like a good set of features. Here are a couple laid out:

New Suggestion(s)!

Direct Draw Methods / Custom Renderer Utilities

I know one thing that would have made my implementation cleaner is some "draw mesh now" functions so I didn't have to add and remove geometry from the scene. Something along the lines of

renderer.drawMesh(mesh, camera = null, target = null, matrixOverride = null, materialOverride = null, group = null)

renderer.drawGeometry(mesh, matrix, material, camera = null, target = null, group = null)

the arguments could use some work, but hopefully you get the idea. The ability to optionally turn off frustum cull checks here would be useful, too. This would address my issue of adding and removing objects from the scene so THREE doesn't iterate over them. I see that renderBufferDirect exists, but the documentation doesn't make it super clear how to use. There's some other private logic in the renderer that might nice to expose, as well.

Transform Updating

I think another missing piece here is knowing when something moved. If I'm reading the code right, THREE regenerates every objects world matrix in the entire scene before each render (which makes using the library very nice and simple, but is a separate performance discussion in itself). But once you know which objects have moved more surgically, you can use that re-insert nodes in something like a spatial index (or all kinds of other stuff!)

[Usnul]

Direct Draw Methods / Custom Renderer Utilities

I'm fully in support of a lower-level rendering API. I suggest, however, using a separate issue for that discussion.

I don't know if that's fair. The value of spatial indexing is really use case dependent and there are cases where unnecessarily using a tree like that can actually hurt performance.

My argument is that it hurts trivial cases and helps complex cases. There is already a ton of stuff in THREE.js that hurts performance in trivial cases for the benefit of helping complex ones, such as caching/hashing. If i have a couple of cubes on the scene - it does me no good and only hurts my performance, using extra memory and spending extra time doing checks which inevitably always return true. Please do not take this as a criticism of those practices.

Transform Updating

This is, in my eyes, yet another argument for having a spatial index. One may explicitly partition the tree to mimic scene hierarchy, this way tracking changes becomes primitively simple and fast. When a node is resized - you may keep a flag on it to signify that hierarchy's matrices need to be updated, when renderer computes set of visible nodes for a frame, it updates matrices as necessary.

[donmccurdy]

The value of spatial indexing is really use case dependent and there are cases where unnecessarily using a tree like that can actually hurt performance.

My argument is that it hurts trivial cases and helps complex cases...

I would add that for "complex cases" it may be even more use-case dependent, e.g. you may want a separate spatial index for your frequently-updated objects and static objects. A modular API that allows users to turn off certain three.js functionality and enable their own, as opposed to choosing a single spatial index implementation and putting that in core, would be ideal. Of course that does not rule out also improving the three.js defaults over time. 👍

[Usnul]

...you may want a separate spatial index for your frequently-updated objects and static objects...

How so? I do not understand this.

A modular API that allows users to turn off certain three.js functionality and enable their own

I think this is outside of the scope of the discussion, as three.js already has a lot of non-tweakable functions under the hood which some people may really wish not to have, while others enjoy to a varying degree.

I do not really object to modularity. Building BVH as an add-on will be less memory efficient, because you basically have to maintain two representations, to hide the BVH usage from standard API. But it's doable, to me it's not a very attractive option because it involves a lot more engineering and some runtime overhead for the sake "backwards compatible" API. As a design for new users I see a flaw here too. If we make it optional and put it aside, but for all serious applications with complex scenes it is pretty much a must, it's like selling a car and wheels separately. My intention is not to add yet another example to three.js, but to argue for an architecture change.

Conclusion:

It's been a few topics and overall message is: people don't want a spatial index to be a part of three.js core. So i'm closing this. Thanks to everyone for voicing their opinions on the matter. This is not what I wanted by it is not a project that is driven by my wishes alone, and I appreciate that. Maybe we can broach this topic further in the future.

[EliasHasle]

I suggest reopening this. The discussion is of high quality, and no project admins have rejected the proposal. None of the commentators, I would say.

I fully agree that it must be better to have a default method that behaves better with complex scenes by default. There is no need to optimize for simple scenes. As far as I can tell, nearly only scenes/geometries crafted to break octrees will not benefit from them. (Example: a geometry consisting of a large number of polygons that intersect the cell borders at the lowest level in the octree. This would make the search about as slow as the default, and would take up more memory, by a small constant factor or so.) And some other Spatial Index approaches may be more robust.

[EliasHasle]

The conditions for this discussion are not static. I am thinking about Moore's law here. Memory capacity grows almost exponentially with time, both for system RAM and video RAM. Screen resolution grows quite fast too (consider VR, which will eventually have to push toward 2x100 MPx or so, to match the human eyes). Game makers/artists will be tempted/required to increase 3D model resolution accordingly. WebGL2 removes the practical restrictions on index size for indexed geometry (geometry.index/gl.draw_elements()).

VRAM can already easily store terribly large models. But the current linear raycasting simply cannot keep up if such 3D model growth were to become a reality soon, particularly not on low-end/mobile devices. If CPU speed keeps increasing exponentially too, it will eventually be sufficient, but in the mean time, Babylon.js and others will have supported these high-res applications for years. System RAM can room increasingly large spatial indices, even on low-end/mobile devices.

Put in other words: Big O is not a friend of the current raycasting.

[Usnul]

Meanwhile, if you're interested in having this kind of functionality with three.js, it's integrated into https://github.com/Usnul/meep

[LeviPesin]

Is there any progress on this?

[Kyrosee]

Is it possible to use octree to reduce the number of collision objects?

[EliasHasle]

Yes, but there are more than one way octrees could be applied to this, some of which may be done better with other methods.

But just consider a basic FPS game where bullets are fired in rapid succession from any points and in any directions. For simplicity, they can be considered points moving at infinite speed in straight lines, reducing the collision check to a pure raycasting problem. One will need an efficient algorithm to avoid a laggy experience, and an octree is a straightforward solution that reduces the complexity from linear to roughly logarithmic in the number of polygons.