🔒 Locked

ABTrees Questions

Started by HellRaiZer Jul 9, 2003 at 4:17 AM 5 replies 6.5k views

Original Post

Jul 9, 2003 at 4:17 AM

I'' read in the "Combining Octrees and BSP trees_is it Possible" post , the algorithm about ABTrees by YannL and i have some questions to ask. 1. Yann L said that you don''t have to split the polygons if you grow the bounding box of the two nodes. My approach to the ABtrees is this: I found the root BBox of the model I found the Larger axis I found a Plane with "starting" Origin the center of the root BBox and normal the normal of the larger axis. In example: if the larger axis is X then the normal is (1,0,0) , if the larger axis is Y then the normal is (0,1,0) ... With that plane i found the number of polygons that are front,back, or divided by the plane. To choose the right splitter i check to see if a function , in example: fabs(NumOfFrontPolygons - NumOfBackPolygons) <= TotalPolygons * factor) Where the factor is a percentance of the total polygons that each time passed. If the above function return true then the SplitterPlane found. If the above function return false then i move the SplitterPlane.Origin, like that: SplitterPlane.Origin += SplitterPlane.Normal * largerAxisLength *FACTOR Where the FACTOR i found it that way: If (NumOfFrontPolygons > NumOfBackPolygons) { // I use this, because if the Numerator is zero then the FACTOR = 0 and no movement of the Origin NumOfBAckPolygons == 0 ? NumOfBackPolygons = 10: NumOfBackPolygons; FACTOR = NumOfBackPolygons/NumOfFrontPolygons; } if(NumOfBAckPolygons > NumOfFrontPolygons ) { NumOfFrontPolygons == 0 ? NumOfFrontPolygons = 10: NumOfFrontPolygons; FACTOR = NumOfFrontPolygons/ NumOfBackPolygons; } If I found polygon that divided by the plane then i add it to both Front and Back Polygons. That way i found the best splittin Plane. Now When i build the ABTrees I calculate the BBox for every node and the best Splitter and then i put the polygons in front and back nodes. The problem is that i don''t want to split the polygons cause there are many polygons created and i do it that way: When i found that a polygons is divided by the plane, i calculate polygon''s center.Then i calculate to which side of the plane that center is. If it''s in front then i put it in Front polygons, if it''s in Back of the plane i put it Back polygons. The problem is that i don''t grow the BBox of the Node (I did''nt understood when you should do this) and i don''t spli the Polygons. The other problem is when to stop the recursion.I stop the recursion when 5 or less polygons are in node.Is that right? From the above approach what is wrong ? Because when i draw the BBoxes of the tree i see some gaps(Not in the polygons but in Bounding Boxes of them. The polygons are rendered correct).I don''t know how this should look like but i thinK that i do something wrong. I test the code on a Box with 300 polygons. Maybe if anyone have any screenshot of the ABTree Bounding Boxes distribution, i would like to see it. Another Question: Must i build a tree per Object or one tree for the entire scene? Thanks in advanced. Hellraizer

sBibi

Jul 9, 2003 at 1:03 PM

so you find the splitting planes, and distribute the splitted polygones ton one AABB or the other.
and what you don't understand is why grow the AABB dimensions?
well when you grow an AABB's sides, some of the polygons partially outside the box will come inside, then there's no need to split them... you only need to split the ones that are still partially out. you could even avoid every single split, but you'd loose a great advantage of the tree, because the culling you can do with the AABBs will become very unaccurate, as you'll get more and more geometry outside your viewing frustrum...
that's why you need to define a treshold (something around 10-15 % of the box size) to tell you when you should stop growing the AABB...

[edited by - sBibi on July 9, 2003 2:04:52 PM]

Yann L

Jul 10, 2003 at 8:24 AM

Well, if you don''t grow, nor split, you don''t have an ABT. Both operations are a vital part of the algorithm.

sBibi already mentioned it: the process of growing the node (also called ''making it loose'') is used to avoid face splits. But it will delocalize the node. It''s a tradeoff: for a perfect localization, you would have to split every single face that comes in the way of your partitioning plane. While such an approach would give you an excellent spatial behaviour (you''d have a perfect tree), the number of split faces can quickly become overwhelming. But sometimes, a face is only a very short way over the partitioning plane. In that case, it can be better the slightly grow the AABB, so that the face goes inside of it''s volume. That way, you just avoided a split. But at the same time, you have delocalized your AABB from the optimal position.

So basically, you are trading in localization quality for less subdivisions. You have to find a good middle ground: a little delocalization is not going to have much negative impact on the tree quality, but it can avoid a lot of splits. If you go too far, however, then you might perhaps avoid 99% of all splits, but your tree will be so extremely degenerated, it will lose all of its effect. In short: the secret behind an efficient ABT is the balancing of growth vs. splitting (besides finding a good partitioning plane, of course).

HellRaiZer

Jul 11, 2003 at 2:09 PM

I''ve done the "growing" of the bounding boxes and i split the polygons, but i still have questions.

1. When you stop the recursion? In example if you have a scene with 10000,and you stop the recursion when 1000 polygons is inside every node is OK? Because in the above scene if i stop the recursion when 100 polygons are in the scene then it takes too much time to do the recursion and it creates too much splited polygons, in the other hand if i stop the recursion when 1000 polygons are in every node then the splitted polygons are 2.If the recursion stop when 100 polygons are in every node the splitted polygons are 500.

2. The more you grow the BBox the less polygons you split. If I use the range that Yann said (5 - 10 %),then when i draw the bounding boxes i notice that the BBoxes overlap each other.I think that i must make the inverse procedure from the leafs to recalculate the BBoxes. I''m i right?

Any ideas how to do it?
I think that if i begin from the root BBox and go down to recalculate all the child BBoxes is much simpler.In example:
I take the root Node and then i go to the right child node and from the right child node i go down to the right child node of the right child node... When i reach the right leaf then i calculate his BBox.I do the same to the left node.

From the left and right BBox i found the parent (Parent BBox = Right child BBox + Left child BBox) BBox and in the same way i go to the others.

Is that right???

Again!!!
The end of the recursion result from mathematics or is it experiential (let''s say that you have a scene with A number of polygons and the recursion stop when every node has 10*A% Polygons)???

Thanks in advance.

HellRaizer.

Yann L

Jul 11, 2003 at 6:25 PM

quote:

1. When you stop the recursion? In example if you have a scene with 10000,and you stop the recursion when 1000 polygons is inside every node is OK?

Yep, that sounds OK. I'd suggest a threshold of at least 800 faces, or more. Note, that you won't always get that much faces in your leaves, depending on local geometry. But if you have less than 800, you shouldn't split further. A vertex array/buffer tends to lose efficiency below that limit. Depending on geometric complexity, you can even go higher (I generally use between 2500 and 5000).

quote:

2. The more you grow the BBox the less polygons you split. If I use the range that Yann said (5 - 10 %),then when i draw the bounding boxes i notice that the BBoxes overlap each other.

That's correct behaviour.

quote:

I think that i must make the inverse procedure from the leafs to recalculate the BBoxes. I'm i right?

Well, depends. If all you do is relaxing the tree (growing it along the normal of the partitioning plane), then the parent box size won't change. But if you do further optimizations, exchanging faces or fusioning leaves, for example, then you need to rebuild the volumes.

quote:

I think that if i begin from the root BBox and go down to recalculate all the child BBoxes is much simpler.In example:
I take the root Node and then i go to the right child node and from the right child node i go down to the right child node of the right child node... When i reach the right leaf then i calculate his BBox.I do the same to the left node.

From the left and right BBox i found the parent (Parent BBox = Right child BBox + Left child BBox) BBox and in the same way i go to the others.

Is that right???

You'd actually be missing the point of the rebuild process by doing that. The idea is to compute a best-fit AABB for each leaf separately, by not taking the hierarchy into account. Just take the extend of all faces assigned to the leaf, and derive the AABB. Once you have all the leaf AABBs, you can go on with the second part of your algorithm: parent AABB = union of both child AABBs, recursively applied to the entire tree. Up until you reach the root. That's basically a bottom->top approach.

quote:

Again!!!
The end of the recursion result from mathematics or is it experiential (let's say that you have a scene with A number of polygons and the recursion stop when every node has 10*A% Polygons)???

Experimental. Depends on your geometry and modelling style, on your engine capabilities, etc. Make sure to not go below 700 or 800, and you should be fine. On larger scenes and a low threshold, you'll end up with a very high number of tree nodes, and a very deep ABT. In this case, it is sometimes better to increase the count. Experiment a little.

[edited by - Yann L on July 11, 2003 7:27:20 PM]

HellRaiZer

Jul 12, 2003 at 2:31 AM

Thaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaanks Yann. I'll try the things you said and i'll post again.

Any ideas on occlusion culling (papers ,tutorials,... )?

[edited by - HEllraizer on July 12, 2003 3:35:02 AM]

HellRaiZer

Jul 15, 2003 at 9:57 AM

Does anybody have a tutorial ,idea, etc. on how you can make occlusion culling if you don''t have a card that support the extensions: GL_NV_Occlusion_query, GL_HP_Occlusion_test?

Can somebody do occlusion culling in software mode (not using this extensions), because every paper on net seems to refer only to the hardware approach of the occlusion culling.

PS. Yann i''ve made the rearangement of the BBoxes. Is there something else to do to turn this "thing" to ABTrees ,or the whole procedure was that?

HellRaizer.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.