Jump to content
  • Advertisement
Sign in to follow this  
sawwgames

Bounding Interval Hierarchy

This topic is 2611 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

[font=arial, verdana, tahoma, sans-serif][size=2]I have been trying to read and understand Bounding Interval Hierarchy, so I can also implement it later.

The pdf file:[/font]
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.4612&rep=rep1&type=pdf

I have it read it all many times, yet i'm confused about the construction/heuristic being used.

(3.3.1) "If a candidate plane is outside the bounding box of a volume element to subdivide,
we continue with candidates from half, where the volume element resides (see figure 3b)"
I have to say i'm really not sure what "we continue with candidates from half" mean in this sentence,
nor the entire sentence it self.
Also, looking at figure 3b compared to figure 2b/2d, make me more confuse. Why is the right
node even being split? As far as I can tell from figure 2, since the entire right node can contain
the right element, there is no need to split it.

So I guess the question is:
What does the sentence literally mean? What are the conditions to splitting (or not splitting)
a specific node, in relation to the elements involved?

Yours, SG.

Share this post


Link to post
Share on other sites
Advertisement
Just skimming the paper, it looks to me like that sentence is talking about the case where the entire object resides on one side of the splitting plane. In that case, the space is only recursively divided on the side of the plane which contains the object(s). In figure 3b, the top left quadrant has been split vertically and the right side left empty because the AABB for the child triangles are completely contained in the left partition.

As for why they subdivide the right half in 3b, this is expected as the BVH presumably splits the space down to triangle level granularity, not object level. (Generally a subdivision algorithm will split objects up to the point where it becomes less efficient that just doing multiple triangle/ray intersections).

I haven't read the paper fully so this could be completely wrong - let me know.

Share this post


Link to post
Share on other sites
pantaloons:

The first part actually make sense, thanks for clearing it out!

However, what did you mean by a "triangle level" ? As far as I understood from the paper, the elements can be anything, they only require an aabb.
Hence the subdivision process should not even know the elements have any triangles.

I also fail to see where would the right element by inserted into (as a child).
The right bottom quadrent? the top right half quadrent? the half quadrent near it? all 3 nodes?

Thanks for your fast reply, SG

Share this post


Link to post
Share on other sites

However, what did you mean by a "triangle level" ? As far as I understood from the paper, the elements can be anything, they only require an aabb.
Hence the subdivision process should not even know the elements have any triangles.


Sure, it doesn't particularly matter what the leaf nodes are. In general it is sensible to use triangles (or small groups of triangles), otherwise your work is for nothing. You could perform a traversal of the bounding hierarchy and still need to perform further intersection tests against whole objects. They are obviously splitting to triangle level here (at least in these images).

The right element, (you mean right three triangles?) first gets split horizontally. The bottom triangle is largely below the splitting plane so it gets put in that half, and the other two are mostly above so they go on top. The top quadrant is still not fully divided (it has two triangles assigned now) so is again split, this time vertically with the two triangles going in the left and right halves respectively. This is indicated by the edge colours, red: left child, blue: right child.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!