Fast raycasting and other spatial queries

[Usnul]

@Fyrestar

I’m not quiet sure what the numbers tell, i mean there are no other specs like your hardware and this is very scene dependend.

That’s fair, I didn’t think many people would care, my specs are:

• Browser: Chrome Version 75.0.3770.100 (Official Build) (64-bit)
• OS: Windows 10 x64
• CPU: i9-9900k @ 3.6GHz
• RAM: DDR4 Dual Channel 14-14-14-34 3200MHz

@Fyrestar

A compasion of with and without index would give a better overview.

Without it the game is just crashing, so I can’t really provide a reliable comparison.

@Fyrestar

I think in your game you benefit from a top-down perspective what reduces the traversal generally.

that’s completely true. A top-down view makes it so that your content is distributed mostly in 1 plane, and you’re able to reject most of the sub-volumes pretty quickly. I did a test with 10,000,000 boxes and I don’t think it’s worth mentioning that that would simply not work on a lot of hardware. That example is not top-down, your view is instantiated at the center of the volume, so it’s close to worst-case.

@Fyrestar

The spatial index (IndexedVolume ) i made uses different techniques to effectively hierarchically perform culling

I’d be curious to know what kinds of techniques you use.

@Fyrestar

The only real downside of a index is the insertion time, depending on if it works dynamic though. Generating a forest with a few million trees can take a while, you wouldn’t do this in production though.

Actually I both agree and disagree, the example I linked earlier, with 10,000,000 boxes does just that, it inserts a lot of boxes into the tree at runtime, so it’s possible to do it without impacting performance, but there are caveats, for sure.

I have 3 tools for making insertion efficient:

• Add one box to the tree. This is relatively slow, but it finds a good placement for a node.
• Add many boxes at once. This uses spatial hash to build a sub-tree that’s relatively good and inserts it as a single unit. Fast, but it creates sub-optimal overall tree as it could have been better to insert some of the boxes into other branches instead of keeping them all in a single sub-tree.
• Incremental tree optimizer. This thing runs relatively slowly performing 1-2 depth rotations on the tree, optimizing spatial locality. The optimizer is kind of like magic sauce, it allows you to sacrifice tree quality in short-term for faster insertion/removal and lets you improve that quality later on with completely adjustable runtime overhead.

@Fyrestar

Instead the scene gets either serialized indexed, or it also supports a progressive chunked insertion for procedural or streamed content.

I use both. My implementation of the tree has barriers to prevent migration of nodes out of a sub-tree, this enables chunking, and I also have a couple of serialization formats, I store my foliage in such a format, as it lets me optimize the tree beforehand and just load the optimal tree from disk later on.

@Fyrestar

btw, shouldn’t this rather go in Discussion?

Sure, we can do that. Mainly I was thinking it might be a resource for those who are thinking about using a spatial index and want to get a feel for what to expect. But I’m personally more interested in having a discussion myself.