Suboptimal / Weird (?) heuristic in BIHTree (Raycasting, Collisions, etc.)

[destroflyer]

Hey guys,

as some of you know I’ve been working on my Vulkan engine from time to time - Since I reached the point where I wanted to implement raycasting/mousepicking on the CPU, I wanted to see how jMonkey sets up its bounding hierarchy.

I quickly found, that meshes ultimately setup a bounding interval hierarchy:

Bounding interval hierarchy

The according class is com.jme3.collision.bih.BIHTree. (In fact, it’s the only CollisionData implementation so far in jME)

I read the code and saw that it’s very close to the description of Wikipedia. I understood the algorithm and what jME does internally, but I can’t seem to make sense of the splitting heuristic that jME uses.

Usually, one uses the longest axis of each “sub-block”/node - This is also what Wikipedia refers to as “Classic”. However, jME passes the “exterior” bounding box (the accoding split of the parents bounding box) and substracts the “interior” (the actual bounding box around the objects in said split) from it. The result is basically the empty/wasted space inside this split (Can even be negative if the actual submesh overflows it because of a previous split decision, just for information). It then chooses the longest axis of that delta boundingbox to decide which axis to take for the next split.

I don’t understand why a bigger “gap” to the exterior bounding box would mean a better split axis.

(Technically, what it also does is avoiding axes, that have overflowing triangles (interior being bigger then exterior → negative delta), but again, since it then just takes one of the 0-distance-to-exterior axes, I don’t see how it would be better than simply picking the longest axis of the actual “submesh” bounds)

I painted a picture:

You can see a long (or imagine an even longer) (in “X” direction) submesh inside the split, but because the longet distance to the exterior bounding box would be on the “Z” axis, it would make the next split based on the “Z” axis. This is most likely suboptimal, because (I think) it’s more likely that stuff like rays are checked along the “long” side. Imagine a user clicking on this object - I would say it’s more likely that we omit more unnecessary triangles to check if we split along the “X” axis, because the object probably has more triangles alongside longer axes.

The according place in the code is here:

jMonkeyEngine/jmonkeyengine/blob/master/jme3-core/src/main/java/com/jme3/collision/bih/BIHTree.java#L309

So basically the classic approach (which would be the one I would’ve used instinctly) would be to just check the longest axis of “interiorExt” instead of “exteriorExt.subtract(interiorExt)”.

I don’t know if anyone who worked on this (I assume this is around from the days of Kirill, Remy, Normen, etc.) is still here to remember if there was a reasoning behind this or if it was unintentional (Sadly there is no @author in the Java class) - Remember that this is only the decision on which axis to split the “submesh”. Even if it’s a suboptimal one, the “submesh” is always divided at the center on that axis, so it’s never toooooooo bad - But still, it seems suboptimal. What confuses me the most, is that I find very little information on the term “BIH” on the internet, only about BVHs. This coupled with the fact that the variable names and algorithm seem very similar to the Wikipedia entry makes me think, that this was written based on the Wikipedia page. Which makes it even weirder that such a special heuristic was used. Especially, because you would need to specifically pass the exterior bounding box to the according method to calculate this. So I’m not sure that it is unintentional…

Maybe someone from the current core team has an opinion on this or can provide some clarity.

If I have time, I will play around with the jME sourcecode and see if I can provide some test results if the classic heuristic has better results (although it’s hard to say stuff like this in general, because you can always be lucky/unlucky with the mesh).

Best regards and thanks a lot for any feedback

[sgold]

Most of the BIH code is 10 years old or more. I’m impressed that you were able to make sense of it!

Improvements would be welcome, but first we’d need a suite of tests (preferably automated ones) to provide some insurance against regressions.

[daBlesr]

Is it not the case where you want to to split to remove asap the largest empty area from the box? If I understand you correctly your solution would be suboptimal

splitting using the longest axis of the mesh, instead of splitting using the green axis cutting away most of the area.
Take a look at this article, it might be of interest to you (with 256 citations): Google Scholar

[destroflyer]

Thanks a lot for your response.

For starters: I tried it out and what jME does, definitely has the right impact. When using just the longest axis of the interior box, way more triangles have to be checked (60k instead of 3k on average in my tests with a high poly mesh). So the question is why - And I think you provided the key to answer this.

I think your intention is correct, that the goal of jME is to cut away the biggest empty space. However, I think you swapped two axes in your picture. Splitting alongside the longest axis (as in the sense of “choosing the axis that the jME algorithm choses”) of the mesh would be the green line, as the axis of jMEs decision is used as a split value - So the plane is orthogonal. The red line would be, what jME does currently, deciding on the axis where the biggest empty space is.

I think the reasoning is the way the algorithm modifies the box for the sub-nodes - It simply limits the one side (of the chosen axis) of each sub-box to the split value:

(Pink referring to the union of the both resulting sub boxes - I should’ve painted that more clearly, but now the images are already done… )

Therefore, when splitting via red (as jME does right now), the resulting sub-box is smaller than via green. If your assumption is correct (and my tests show that), this means the fitting is more optimal (which apparently is worth more than the green splitrig through the object) and less triangles need to be checked. This makes sense, as less ray-vs-boxes are now matching and therefore less ray-vs-triangles have to be checked? Please let me know what you think about this or if I made a thinking error.

I still don’t understand why Wikipedia says “Classical: pick the longest axis and the middle of the node bounding box on that axis”, which is the green split in my understanding.

[daBlesr]

The idea presented in your images, is exactly what I meant, my mistake for being unclear. However, the left side of the green axis is the point where you do the actual splitting, so you do need this vector. Good that you you tested it out. I think what they mean on wikipedia is: “pick the longest axis through empty space from inner bounding box to outer bounding box”

[destroflyer]

Actually, I made a thinking error in my previous post - jME doesn’t simply modify the exterior box by one side. It correctly takes the interior box and modifies one side of that. I had that correct in my initial topic post, but somehow mixed it up when rethinking it:

(Pink being the resulting two sub nodes, with the dotted line marking the split)

So my original question still stands: Why is the red split (1st image) better than the green split (2nd image). There is no difference in the amount of empty space after the cut.

(I have to go to work again, I will read the linked scholar link when I have a bit of spare time, it probably answers my question)

[destroflyer]

Aaaaaalright guys, I finally figured it out thanks to the paper (http://electronic-blue.wdfiles.com/local--files/research:gpurt/WK06.pdf) provided by @daBlesr.

Long story short:

• My initial understanding that the ext-int logic in jMEs implementation is suboptimal, was correct and the paper proves that it’s not the way that BIH was intended
• BIH actually intends you to always use the “exterior” box (purely based on the scene, not the submesh!), not the interior one (So that explains why me testing it with interior failed so horribly)
• I adapted it accordingly to the paper and finally see significant speedup → 44% less checked triangles

A post in the forum is probably not the best way to share the results, so I quickly made a spreadsheet, where I describe the situation (how my test setup looked like and what the exact results were):
http://185.183.156.11/other/jme3-improved-bih-heuristic.pdf

Here is the according citation from the paper:

It is important to note that the split plane candidates are not adapted to actual bounding boxes of the inner nodes, but are solely determined by the global bounding box of the scene. This is the actual difference to previous approaches, which results in an adaptive approximation of the global regular grid as close as possible and bounding boxes as cubic as possible throughout the hierarchy.

From a code perspective (if you want to try it out), this is what changed:

(Plus replacing all usages of currentBox in the method with nodeBBox)

Please let me know what you think about this.

Edit: It just occured to me, that I should also check how many ray-vs-bbox (not only ray-vs-tri) were done - I highly doubt, that the “new” implementation will be horribly worse here, but for completeness it should be tested to really 100% prove that the change is an improvement.

[Ali_RS]

Good job

Sorry if my question is stupid but does this also affect/improve the rendering (frustum checking/culling)?

By the way can we expect a PR?

[pspeed]

@Ali_RS

does this also affect/improve the rendering (frustum checking/culling)?

99% sure this is only done on bounding volumes… so “no”.

[destroflyer]

Exactly. The only other place I found where this code is being called is on some terrain LOD utility.
But nothing, that would have an impact on rendering in that sense.

By the way can we expect a PR?

Sure - When all the remaining stuff has been tested. As stated before, this code is 10 years old and the git history is only going back to the initial migration from SVN, so we can’t be sure that this wasn’t added on top of standard BIH for some reason. I tested it for a complex mesh, which gives me a good feeling that things go the right way, but we will need a way bigger testing set to justify such a low-level change.

[pspeed]

Please make sure to test with quads at various angles. Traditionally, this has been the place where folks making changes are most likely to break things. I remember fixing at least one bug related to this (but I think it was in the bounding shape code)… but apparently it’s a tricky case.

[destroflyer]

Hey guys,

here is an update:

1. Checking how many ray-vs-bboxes were done was actually not really what I meant, as that is unaffected by the BIH (which is on geometry/mesh level). What I meant was checking how many nodes of the BIH tree are checked (and for that, not bboxes are checked, but just the nodes planes and according tMin/tMax values on the ray). So I did that and in short: Even there, the BIH changes are an improvement, so all good, phew Only 80% of the previous amount of nodes have to be checked now!

2. I noticed another little “flaw” in jMEs current implementation, which looks like it is due to refactoring. jME first checks the ray-vs-triangle in model space and if it collides, it also checks it in world space and returns that coordinate:
   
   I noticed it because my IDE showed that the if is unnecessary. My assumption is that the code originally supported both: Not passing a worldMatrix and making the whole check in model space or passing one and doing it in world space. However, jME is currently setup in a way where the worldMatrix always exists. I don’t think checking the model space first is to prevent floating point errors or to make it more stable or something like that, because the ray itself is provided in world space here and for this check, jME first transforms it to model space. So in short: jME does a bit of unnecessary stuff just to make another unnecessary check. One could directly do the whole check in world space and save the ray-transformation and therefore this 2nd ray-vs-triangle check. I initially thought this would save 50% of the checks, but obviously it only affects the triangles that are positive hits, so just a few. Still, I did another test to see how much of an impact this improvement has, since it’s definitely one in my opinion.

Here are the results:
http://185.183.156.11/other/jme3-improved-bih-heuristic_2.pdf

In short:

• The BIH tree improvement only needs ~80% of the current BIH node plane checks and ~55% of the current ray-vs-triangle checks
• With the direct world space check the number of triangle checks decreases a little bit, from ~55.2% to 54.7%. Not much, but an improvement Especially because it simplifies the whole code (jME modified the functions ray parameter “in-place”, and then restored the original values at the end of the function and other ugly stuff…)

I still need to test other usecases, but I used up a lot of my initial motiviation. So it might take me a little while before I post another update. In any case, I plan to make a branch for jME3 with my changes, so you guys can see how little code changes and what an impact it has.

[pspeed]

I think you might be surprised about the accuracy of world checks versus local checks.
…but you’d have to look inside the intersects() method to be sure.

[Ali_RS]

Sorry to bump this thread!

@destroflyer have you been able to thoroughly test with these changes? Did you find any issues?

@destroflyer

In any case, I plan to make a branch for jME3 with my changes, so you guys can see how little code changes and what an impact it has.

Any chance to submit a PR?
Interested to give it a try.

Thanks

[destroflyer]

Hi, no I didn’t have any time lately to pursue this topic

I can create a branch with my changes (as they are not many) and you can try it out if you want - My test results were very promising, but obviously it’s a central part of the engine and one has to be careful. Still, I am pretty confident that I understood everything correctly.

In my Vulkan engine, where I implemented the BIH myself (and therefore saw the differences to jME and created this topic), I didn’t have any problems yet with my approach/findings, so I guess that’s a little bit of other confirmation, even if it’s not worth much.

[Ali_RS]

@destroflyer

I can create a branch with my changes (as they are not many) and you can try it out if you want

That would be cool, Thank you.
I am interested to try it with different meshes in JME. (e.g. quads at various angles,… as pspeed mentioned)