Raycasting and the BVH Tree


#1

Jme uses a pretty sophisticated method for raytracing called the BVH Tree.
That basically means: “If it’s parent node’s world bounds/bounding box doesn’t collide, then the children won’t either”.
That’s pretty good but unfortunately tied completely to the SceneGraph.
I have the following problems with it:

  1. The first raycast (Tree generation) freezes the game for a short amount of time
  2. I would want to avoid re-generation of trees if I’m tracing different things.
  3. I’d love to run it in another thread.

So really my question is if there is any “tree object” at all to cache or which is discarded? I have the feeling that 1. is simply when the bounding volumes for the whole Scene Graph are calculated?

My use-case is an entitysystem with “interactables”, that means elements in the scene which you can interact with by pressing “E”. For this I’d build up my own “scene graph”/tree, but I don’t want this to infer with “rootNode collision for shooting bullets”.
I guess I’d be fine by just doing it since the only calculation will be the worldBounds?

So the only drawback would be 3, because worldBounds change with the Transforms and it would be writing to Nodes? Would it be a problem if inside the update loop multiple raycasts run in parallel? Apart from maybe duplicate calculation of worldBounds? Or if worldBounds are calculated, could I run them in parallel?


#2

Hold up, you’re getting freezes for a single raycast per player to detect object pickability? How many thousands of objects do you have?


#3

Freezes when fireing a bullet for the first time. The Problem is probably more the 10mio vertices which stress out bounding box calculations and the mesh instance aren’t shared probably


#4

Eyeah that might do that I guess.


#5

Not sure why you edited your post, you actually found the part of code I was searching for probably, so it’s indeed using worldBounds at least for nodes with 5 direct children


#6

The time is taken generating the BVH inside of mesh. You can do that ahead of time and then it will never happen again until you want it to.


#7

I realized my hypothesis was wrong and the point I was making moot. I assumed you’ve already seen that code :smile:


#8

I ran into similar performance issues once, however mine was just ray casting taking waaaaaay longer than it should, I ended up just sampling the mouse less frequently, I never found a fix or a cause.


#9

Since the “first raycast” thing seems to be missed be some responders I’m going to go into more detail on what I think are a bunch of misconceptions in your first post…

Yes, down in the Mesh (Mesh.java):
https://javadoc.jmonkeyengine.org/com/jme3/scene/Mesh.html#createCollisionData--
https://javadoc.jmonkeyengine.org/com/jme3/scene/Mesh.html#clearCollisionData--

Control creating/clearing the Mesh-level BVH data structure.

While that is technically using the scene graph bounding volumes to cull out unimportant stuff, it is not BVH in the context of this discussion and is not “building a tree” or anything that isn’t already built every frame where an object moves just to render the scene.

Try calling createCollisionData() on all of your meshes first (can do it in a separate thread before you attach them to the scene even) and then see if your “first raycast” is slow.

“Trees” are only regenerated if you call clearCollisionData() after the data was cached. In fact, if you modify the mesh data it won’t clear the collision data unless/until you tell it to.

Basically, your slow down has nothing to do with the scene graph. So you can stop worrying about 70% of what’s in your post.

If you weren’t clearing collision data and ray casting was taking a long time then a few things could be in play:

  • badly organized scene graph such that rays end up doing Mesh-level collision detection on more things than necessary
  • somehow a giant mesh was always getting collision checked (for example, a 3 million triangle terrain or something)

Picking can be sped up with some proper scene organization. For example, putting all pickable things under one node to avoid picking useless stuff like background terrain. (Alternately, in that example, the terrain geometry could be extended to override the collideWith() to do nothing.)