# Fast raycasting and other spatial queries

**URL:** <https://discourse.threejs.org/t/fast-raycasting-and-other-spatial-queries/8402>\
**Category:** Discussion\
**Tags:** spatial-index, raycaster, performance\
**Created:** [July 5, 2019, 11:29pm UTC](https://discourse.threejs.org/t/fast-raycasting-and-other-spatial-queries/8402 "2019-07-05T23:29:21Z")\
**Posts on this page:** 1\
**Showing post:** 3

<div class="post-metadata">

**Author:** ![Usnul](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.threejs.org/usnul/32/2355_2.png) [@Usnul](https://discourse.threejs.org/u/Usnul)\
**Post date:** [July 6, 2019, 1:58pm UTC](https://discourse.threejs.org/t/fast-raycasting-and-other-spatial-queries/8402/3 "2019-07-06T13:58:30Z")

</div>

> [@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](https://discourse.threejs.org/t/ridiculous-number-of-boxes/6862) 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](https://discourse.threejs.org/t/open-world-planetary-engine/1473/9)) 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. 👍

---

_[View the full topic](https://discourse.threejs.org/t/fast-raycasting-and-other-spatial-queries/8402)._