ABTs and the possibility of multiple division planes

quote:

---

I was taking a look at Yann''s Adaptive Binary Trees and I was curious if it was possible to extend the concept to have more than one division plane. The way Yann seemed to explain it (as far as I understand it), is that the geometry gets recursively divided into 2 branches. So in essence what I''m asking is is it possible to use something like 2 division planes giving you four areas of even 3 division planes giving you eight areas. If this is the case and you can, would there be any benefits to doing so?

---

I never tried it, but it should be possible. However, I don''t think you''ll get many benefits from doing so. It will for sure reduce the depth of the tree, that can be an advantage. But the number of AABB frustum checks will increase: if a parent node is visible, you need to check the visibility of each of it''s children. If you have only two, then you need exactly two checks. Say the left one is visible, but the right one is not. Then further visibility testing will be stopped for the right leaf. If your parent node has more than two children, then you''ll always need to test them all. So in essence, you''ll have less recursion, but more frustum tests.

Now, the question is, do you make the additional planes mandatory for each node, or are they optional ? In the former case (each node has always 2 or 3 planes), then you''ll get additional problems: just like in an octree, you''ll split space, where there is nothing to split. That''s one of the main reasons I prefer ABTs over octrees. Consider a long bounding box, containing two objects at it''s left and right extremities, and a large void inbetween. This is typically the worst case scenario for an octree. Now, a two-child (one plane) ABT would split along the largest axis, and recompute tightfitting AABBs. The result are the two objects perfectly fit with a boundig box each. Possible further divisions along other planes can be done on the next recursion level, and will operate on the optimized bounding boxes of each object.

But if you add more planes directly to the parent box above, then the following scenario will happen: one plane will split the large void in the middle, just as outlined above. OK. But the next one or two will slice both objects in half, along the two other axes. This slicing, however, is not required from a hierarchical point of view. It will create additional nodes, more faces (as the object''s faces get subdivided), but it won''t improve the hierarchical localization.

In conclusion, splitting a node with a fixed number of planes > 1, will create more faces and unnecessary nodes. On the other hand, splitting with a variable set of planes can be beneficial in certain circumstances. It will make the tree shallower, but keep the localization behaviour. That is a good thing. But at the same time, it will increase the number of AABB/frustum intersection tests required. I guess you''d need to test it, in order to see if there are performance gains or not. It probably also depends on the type of geometry you use (as always with spatial subdivision algorithms).

quote:

---

Also, I''d just like to confirm that the original tree structure is creating during a preprocessing phase. If this is the case, is it possible to do this during level loading times, or does it have to be done seperately and then it can be modified dynamically at run time?

---

Typically, it''s a preprocess. But it can be updated in realtime, so that it can accomodate dynamic objects. It depends on how accurate you want the tree to be. The key is the spliting-plane selection: what axis, what position. If you take a very simple algorithm (median split on the largest axis), then you could probably do it at level-load time. But the tree will be suboptimal. More sophisticated techniques (eg. successive approximation, or even neural nets) will create a much better tree, but will also take much longer to compute.

For static geometry, I always compute the tree at level compile time, and store it with the level data. But for moving objects, you can easily modify it in realtime. Moving objects typically won''t intersect (collision detection should take care of that). And most of the time, the space between two dynamic objects will be pretty large, compared to static geometry. Eg. two characters walking past each other. So in that case, the simple plane selection algorithm (largest axis, split in the middle) will work just fine. Obviously, it will sometimes create a suboptimal dynamic tree, and your FPS will drop a little. But a few frames later, as the animation goes on and resolved the problematic situation, the tree will re-optimize itself.

/ Yann

quote:

---

Original post by Yann L
If your parent node has more than two children, then you''ll always need to test them all.

---

Not necessarilly. Suppose you have 3 orthogonal planes, and you know that the current node intersects the frustum (otherwise you should have discarded it previously). Then the following algorithm can be applied:
1. Put all children in PVS.
1. Check 1st plane against fustum. If it intersects the fustum, then at least one child on each side of the plane is inside the frustum (partially or fully). If it doesn''t, then all the children that are not on the same side of the plane as the frustum, are definitely outside the view - discard those from PVS.
2. Repeat for 2nd plane.
3. Repeat for 3rd plane.
4. All children that weren''t discarded in any of the stages are intersecting the frustum.
5. If you want, you can reduce the non-clipped childrens'' bounding boxes for a thight fit with the geometry inside it, and check the new BB against the frustum.

If you skip step 5, you''ll have one check per plane and that''s it.

quote:

---

Now, the question is, do you make the additional planes mandatory for each node, or are they optional ? [...] On the other hand, splitting with a variable set of planes can be beneficial in certain circumstances.

---

Hmm... interesting point.


Michael K.,
Designer and Graphics Programmer of "The Keepers"

---

We come in peace... surrender or die!

quote:

---

Not necessarilly. Suppose you have 3 orthogonal planes, and you know that the current node intersects the frustum (otherwise you should have discarded it previously). Then the following algorithm can be applied:
[...]

---

That's exactly what happens if you use a two children node. You check the planes manually against the viewfrustum, to rule them out. In the two children node approach, the recursion takes care of that. It will perform the same tests, with the same results. The question is, what is faster: doing it manually for each plane, or having the recursion do it. The recusrion has the function call + stack overhead. But the testing equation is simpler, faster, and fits in the level 1 cache.

For precise results, one should do an actual test and profile it.

[edited by - Yann L on January 14, 2003 8:25:08 AM]

quote:

---

Original post by Yann L
That''s exactly what happens if you use a two children node.

---

Yes, which is to say that having multiple division planes isn''t slower (or at least not significantly). Basically, if the additional planes aren''t mandatory, what you get is exactly what you get with one plane per node, only flatter.

quote:

---

The question is, what is faster: doing it manually for each plane, or having the recursion do it.

---

Not sure... My guess is that manually is a bit faster, if done properly, since this is somewhat similar to unwrapping a loop (i.e. doing two-three itterations in one go), which is a known optimisation technique.

quote:

---

For precise results, one should do an actual test and profile it.

---

Agreed.

Michael K.,
Designer and Graphics Programmer of "The Keepers"

---

We come in peace... surrender or die!

Here another point to consider, when working with nodes having a higher plane count than one: your tree will get less adaptive to the geometry. Consider the following situations (in 2D, but scales up to 3D with an additional axis):

If we have two planes per node:

As you can see, there is no way to position both planes, so that no object gets subdivided. In the end, either the blue or the green object will be intersected by a plane, and the resulting AABB set is suboptimal.

Now with two-child nodes, using two recursive levels:

Here, the vertical planes can be shifted to tightly enclose the objects, as they are separated by a hierarchic level. The result are perfectly tight AABBs.

Now this might seem like a pathological case, but it happens a lot more in realworld scenes, as one might think. Of course, it will even get worse with 3 planes, in 3D. But it could work for scenes, where objects are always separated by large empty spaces, eg. a space shooter.

[Edit: oops, two intersecting posts ]

quote:

---

Basically, if the additional planes aren't mandatory, what you get is exactly what you get with one plane per node, only flatter.

---

Yes, that's correct.

quote:

---

Not sure... My guess is that manually is a bit faster, if done properly, since this is somewhat similar to unwrapping a loop (i.e. doing two-three itterations in one go), which is a known optimisation technique.

---

It would probably depend on the implementation details.


[edited by - Yann L on January 14, 2003 9:02:04 AM]

In this case, assumming non-mandatory planes, I would split the parent only horizontally, then split the two children in whatever way suitable.

Of course, if this is the usual case, then a one-plane tree is obviously better, since you will almost always split once anyway (hence you won''t gain on much tree flatenning). And one shouldn''t forget that extra checks are needed to see if a node can be split against each one of the plains. Extra checks = extra overhead.

On the other hand, if this is the minority case, then the tree will be much flatter, which may outwiegh that overhead... So the ultimate question is - what is the typical situation in any one game...

Yann, a few questions though:
1. Don''t you need to do these checks (or something similar) anyway when you''re splitting your single-plane nodes? If so, then maybe this isn''t that much overhead afterall...
2. What would be a good (=efficient) way of doing such checks?
3. I am a bit familiar with your structure from other disscussion(s) on gamedev, but I was wonderring if you have some paper/technical doc/something that may explain it a bit more in-depth (if you don''t mind sharing the info, that is)? It sounds like a good choice for "The Keepers", with some adjustments...

Michael K.,
Designer and Graphics Programmer of "The Keepers"

---

We come in peace... surrender or die!

quote:

---

In this case, assumming non-mandatory planes, I would split the parent only horizontally, then split the two children in whatever way suitable.

---

Right, I think the emphasis would be on non-mandatory. Then the number of planes could be adjusted according to the local geometry. The worst case scenario would result in a simple two-child tree, while the best case would have 3 planes in each node. Hmm. Yeah, that could work.

quote:

---

So the ultimate question is - what is the typical situation in any one game...

---

That's the magical question with all spatial subdivision schemes It highly depends on your particular type of scene.

quote:

---

1. Don't you need to do these checks (or something similar) anyway when you're splitting your single-plane nodes? If so, then maybe this isn't that much overhead afterall...

---

Basically, you're doing the same number of plane position approximations. But if you want more than one plane, you need to evaluate how much planes you can safely use, without endangering the hierarchic consistency. That's more overhead at level build time (and runtime, if you want to modify the tree in-game). But it won't impact on the traversal time.

quote:

---

2. What would be a good (=efficient) way of doing such checks?

---

Hmm, let's see: What exactly do we need to know about the structure, in order to decide over the plane number ? One plane is the minimum, three are the maximum. Say the first plane is on axis A. Now plane 2 and 3 can be on axis B or C. So we need three additional checks: can we use 2 planes (second plane on either B or C), and if that test succeeds, can we use a third plane on the remaining axis.

Now, the problem is that the position of the first plane will influence on wether the second or third plane can be inserted. In a similar way, the position of the second plane will influence back onto the first and onto the third. Mathematically, the goal is to find the minimum of a non-linear equation with 3 variables. Not easy, and very slow. Especially considering that the equation can have several singularities at the polygonal edges.

There are two ways I can imagine would work in finite time. But neither one will produce an optimal solution (although they will approximate it):

1) Neural nets.
2) Best guess approximation.

Neural nets are hard to get stable, and notoriously slow. I use a NN for the single plane position computation, and it takes ages. But the results are typically very good.

Best guess approximation would simply rely on the fact, that we first try to find the plane axis that is the most interesting for the current node, ignoring additional planes at that moment. Just as in the original ABT algorithm. Then, we search the second and third best planes, but without modifying the first or second, once they are set. This will obviously lead to suboptimal sets ("Damn, I could have positioned a third plane, if I just moved the first plane a few units to the right..."). This approach is conservative (it will revert to the one-plane ABT, as soon as something goes wrong). This implies that it won't catch all cases, where it could actually use more planes. But it will catch the obvious ones. It depends on the scene, if that is worth the overhead or not.

quote:

---

3. I am a bit familiar with your structure from other disscussion(s) on gamedev, but I was wonderring if you have some paper/technical doc/something that may explain it a bit more in-depth (if you don't mind sharing the info, that is)? It sounds like a good choice for "The Keepers", with some adjustments...

---

No, I certainly don't mind sharing the infos. I'm currently writing an ABT-paper for Siggraph 2003, the paper will be publicly available once it's done (with the emphasis on the "when it's done" part... ) Well, deadline is in two weeks, so I guess I'll have to hurry anyway... You're welcome to use the system in your game, actually I would be highly interested in knowing how well it performs in other engines. Currently, I only had the opportunity to profile it in our own engine.

/ Yann

[edited by - Yann L on January 14, 2003 11:22:07 AM]

quote:

---

Original post by Yann L
Now, the problem is that the position of the first plane will influence on wether the second or third plane can be inserted.

---

Actually, since each plane is orthogonal to the other two, they're completely independant of each other (and I doubt they would depend on each other even if they weren't orthogonal). Suppose you have 9 objects like that:

123
456
789

Whether you horizontally divide between 1 and 2 or between 2 and 3, you still have two options (the same two options) for dividing vertically. The same applies to the third axis.

quote:

---

Best guess approximation would simply rely on the fact, that we first try to find the plane axis that is the most interesting for the current node, ignoring additional planes at that moment. Just as in the original ABT algorithm. Then, we search the second and third best planes, but without modifying the first or second, once they are set. This will obviously lead to suboptimal sets ("Damn, I could have positioned a third plane, if I just moved the first plane a few units to the right..."). [...]

---

Again, the plains are independant, so this isn't correct. I imagine something like this:

1. Split the current node along longest axis, at a good enough (best?) location.
2. Split each of the two children along their longest axis.
3. If the split planes of the two children are the same, and are orthogonal to the original plane, move the children's children up one level (i.e. flatten the tree):

A (plane 1)
|-B (plane 2)
| |-C
| --D
|
--E (plane 2)
  |-F
  --G 

becomes:

A (planes 1,2)
|-C
|-D
|-F
--G 

4. Repeat for new children (split, compare planes, flatten).

I don't see any reason for the splitting technique to be any diffrent than the orginal ABT, so this can be rearanged to the following:
1. Create/adjust tree as in orginial ABT.
2. Flatten by comparing division planes.

Unforetunately, it may often be the case that while it is possible to split both children with the same plane, the above method would split them along different planes (each better suited to the corresponding child). In which case the method would tend to yield very little flattening. Although this depends on how one decides where to split.

Another approach would be to go ahead and try splitting each node along each of the three axis (axes? axii?) and use as many splitting planes as were found suitable (i.e. planes that don't split objects or something like that). That would result in a flatter tree, but in less optimal division...

quote:

---

I'm currently writing an ABT-paper for Siggraph 2003, the paper will be publicly available once it's done (with the emphasis on the "when it's done" part... ) Well, deadline is in two weeks, so I guess I'll have to hurry anyway...

---

I'll be waiting then.. (it just so happens that I have more than enough other things to do in the mean while )

Michael K.,
Designer and Graphics Programmer of "The Keepers"

---

We come in peace... surrender or die!

[edited by - technobot on January 15, 2003 6:45:57 AM]

[edited by - technobot on January 15, 2003 6:48:37 AM]

I feel for scenes where there''s lots of continuous geometry, like the outdoor part of an indoor/outdoor game, ABTs at the nodes of a grid like structure will be very effecient. For most of such senarios, the camera moves from one grid node to the adjoining grid node so much of the traversal of the ABT is eliminated in subsequent frames. However this also means that for each of the (partially) visible grid nodes, the ABTs much be traversed through. So which one will be better for such scenes? One deep ABT or lots of shallow ABTs at the grid nodes?
And what will be most effecient for just a terrain (say heightmapped) grid with some sort of pvs or a quadtree?

technobot:
Good point. You are right, the planes are indeed independent. I still had the notion of the planes being dislocated by a recursive level in my head yesterday, which would make them dependent. But that is of course not the case, with more than one plane in a single node.

Posting and coding at the same time is not advised

quote:

---

Unforetunately, it may often be the case that while it is possible to split both children with the same plane, the above method would split them along different planes (each better suited to the corresponding child). In which case the method would tend to yield very little flattening. Although this depends on how one decides where to split.

---

This is very likely to happen. The ABT will try to optimize both planes as far as possible, both being at the same position is pure luck. Also, while overgrowing the node, the structure will partially overlap, so that it can't be reintegrated into a single node later on. A simple way to avoid that, would be to compute a two-child ABT for 3 levels (including overgrowing, and volume optimization), and store the results. Then go back, and compute the optimal solution with 2 or 3 planes on the original node. Compare both (all three) solutions, and decide based on some predicate (eg. number of faces subdivided, quality of the node localization, etc).

quote:

---

So which one will be better for such scenes? One deep ABT or lots of shallow ABTs at the grid nodes?

---

Well, it depends on how you implement your intersection tests. The tree itself will have tohe same localization behaviour, but it will be flatter, while adding the need to check for additional planes. Do you have a blazing fast plane check ? Or is your AABB/frustum check faster ? Do you actually recurse into the tree, or do you use an iterative algorithm ? Depends on all that.

/ Yann

[edited by - Yann L on January 15, 2003 7:54:26 AM]

Another possible solution would be something like this:
1. Split current node along longest axis.
2. Use hueristic to determine which of the two children is "more important".
3. Find splitting plane for the "more important" child. Check if it can be used for the other child as well.
4. If it can''t - we''re stuck with two children (and we still have the second child to split). If it can - add that plane to the current node, and use it to split the two children into four children.
5. Find the "most important" child of the four, compute split plane for it.
6. If the new plane can be used for the other three children, you now have 3 planes and 8 children. Otherwise you''re stuck with four children (and must repeat the process for those).

Michael K.,
Designer and Graphics Programmer of "The Keepers"

---

We come in peace... surrender or die!

A Kd-tree, k-dimensional tree, is just that: a tree that gets recursively subdivided using multiple number of dimensions. At the very base, an ABT is a Kd-tree. But a quad or octtree is also a Kd-tree. So is a BSP. Only the division plane rules are different, they are all extensions to the original concept. A Kd-tree in it's rawest original form is much too rigid to be useful in 3D graphics.

But this is where the differences begin: After each Kd-tree-like split operation of a node, the volume gets recompressed and then overgrown, ie. relaxed. The tree loses its 1:1 volume ratio between parent and child, ie. if you add the volumes of two child nodes, you can actually get a larger volume than the parent node. Or a much smaller one. The tree gets 'loose' and nodes can overlap (which is a little bit like T. Ulrich's loose octtrees, but in an adaptive form).

The hierarchic node information is also stored differently: as a chain of AABB's with hierarchically connected degeneracy factors. Those allow efficient runtime rebuilds and adjustments, so that the tree is usable for dynamic geometry (which is not the case with a raw Kd-tree).


[edited by - Yann L on February 2, 2003 6:25:39 PM]

How would ABTs work with meshes (in terms of groups of polygons), since meshes can be an arbitary size and sometimes a whole object (say, a tree for example) can consist of one mesh.

For my Octree I store meshes in the nodes, not faces, and the node cycles through the meshes in the node and draws them (with vertex arrays etc) - so i was wondering how a ABT would work with meshes, I am thinking it would degrade it wouldn''t it?

Every tree like structure, might it be ABT, BSP or octree, will work better, if the minimum size primitive is smaller. But they will all also work on individual objects.

Still, I would suggest using the per-face approach on static geometry. Your vertex arrays will be recomputed based on the newly sorted and subdivided geometry in every node. In the end, it will speed you up, compared to individual objects.

For dynamic objects, realtime face subdivision is, of course, no option. In this case, you can directly insert whole meshes, just treat the objects as geometrical primitives. Depending on how well your objects are localized, this might very well degrade the quality of the tree.

A good approach is to use small local hierarchical trees for each object, where the object''s locally static geometry gets pre-subdivided. This local OBB hierarchy gets transformed with the object''s local matrix. At runtime, when the object moves around, you don''t insert the whole object into a single ABT node, but you go through the object''s local hierarchy instead. Each local node (which will obviously be an OBB tree, since the object can be arbitrarily oriented) is then inserted into the scene ABT. That way, the tree degradation can be kept to a minimum. And as a side effect, you get much better frustum culling on dynamic objects that way.

/ Yann

Do you refer to faces as individual polygons?

If so, how do you associate texture ids, etc with those individual faces?

Excuse me if it sounds ignorant, I''m just used to dealing with the whole mesh idea, where the mesh holds information about texture ids, and other group dependant information.

Yeah, I also wondered how you choose the right texture for the right faces, if you only have one vertex array. How are you supposed to set that up?

OK, so if I say face, then I refer to a basic geometric primitive. Typically, that is a triangle. But it can also be a Bezier patch or a NURBS surface.

The engine doesn''t know about texture ID''s. All it knows about, are shader state ID''s. Every possible way to render a primitive, from simple decal texture mapping to complex PP lighting, is done through dedicated shaders. A set of precompiled shaders is available, and you can dynamically link as much custom shaders as you like (a 3D file can even contain shaders, that get loaded with the scene).

When the geometry comes out of the exporter, you have a collection of objects, as drawn by the artist, each one with a set of parameters. The artist can also attribute a special hand-written shader to objects (which has to be provided as Cg shader).

The scene compiler will load all those objects with their respective parameters. In a first pass, it will assign default shaders to all the objects that have no custom shader attributed. Default shaders are things like decal-texture, specular-bumpmap, EnvBumpmap, etc. For dynamically linked custom shader objects, the system will load the respective Cg shader, auto-compile it for various target systems, compress and encrypt it with RC5 (we don''t want people to steal our shaders ), and store it in the 3D file.

So, now each object has a shader, along with lots of shader parameters. The system will go through all faces (triangles or parametric patches) of that object, and assign a 32bit ''shader state ID'' (SSID) to each face. That''s simply a pointer onto a memory chunk containing the shader ID and shader parameters of the parent object. Once all faces in the scene are processed, the original object structures are destroyed. We are left with a huge polygon soup.

At this point, the ABT construction begins. The system will operate on face-level only, and will hierarchically partion the polygon soup. Once the tree is build, you''ll have a linked list of individual faces attached to each leaf, something between 100 to 5000 per leaf. Each leaf may contains faces with a lot of different SSIDs, and since we don''t want to render faces individually, we need to cluster them. The faces in a leaf will be first sorted by their SSID, and then RLE compressed. You are left with a number of geometry chunks (GC), each GC using a unique SSID. That''s all we need for rendering, the face linked list is now discarded. Typically, the number of GC''s per leaf is around 4 to 10. Each GC can be seen as a separate vertex array, as we have the guarantee that there will be no shader state change within it (unique SSID !). Note, that the engine does not process things like texture ID, since all that data is contained in the shader state data block.

At render time, visible GC''s get recombined by their SSIDs to SSID render groups, once per frame. This will guarantee the minimum possible number of state switches for the current frame, as well as good z-distance sorting, so that we can take advantage of the early z rejection feature of modern 3D cards.

I have also explained the process at the end of this thread.

/ Yann

Yann, thanks for explaining that, I hadn't thought of doing things that way.

Just to go a little of topic - you mentioned Cg. How do you handle integration with the cg compiler and the uniform parameters that are passed to it? For me, I have a simple map that looks up predefined parameters such as (eyePos, ModelViewProj, ModelViewIT, lightPos) and associates them at runtime with their respective values.

For example, eyePos - this just fetches the camera eyePosition.
ModelViewProj - this fetches the modelView projection matrix from Cg itself and binds it.

My only problem comes when i want to use parameters that are only specific to one shader, it doesn't really make sense to add that to my map, since it is only ever going to be used once and is kind of a waste of memory.

Here is what I mean:

For a small sample like this (a bit of code from the ATI paper I am working off for light scattering)

void main(
		float4 Position		: POSITION, //in object space
		float3 Normal		: NORMAL, //in object space
		float2 TexCoord0	: TEXCOORD0,
				

		out float4 oPosition : POSITION, 
		out float4 oExtinction : COLOR0,	// Extinction coeff
		out float4 oInscattering: COLOR1,	//Inscattering coeff
	
		uniform float4x4 ModelViewProj,
		uniform float4x4 ModelViewIT,
		uniform float4 sunDirection,		// Sun Direction Vector
		uniform float3 eyePos,				// Eye Position
		uniform float3 beta_1,				// Rayleigh
		uniform float3 beta_2,				// Mie
		uniform float3 beta1_1,
		uniform float3 beta1_2,
		uniform float3 hgConstants			// hgConstants == [1-g^2, 1+g, 2g]
}
  

Now, things such as the first four uniform parameters are bound in a map like this:

mBindList.insert(tBindList::value_type("ModelViewProj", VSB_MODELVIEW_PROJECTION_MATRIX));
mBindList.insert(tBindList::value_type("objectPos", VSB_OBJECT_POSITION));
mBindList.insert(tBindList::value_type("eyePos", VSB_EYE_POSITION));
mBindList.insert(tBindList::value_type("lightPos", VSB_LIGHT_POSITION));

  

Then, at runtime the shader manager will bind values based on the enumeration (for example VSB_EYE_POSITION will bind the camera position to "eyePos" in the above shader).

Edit: I also thought of maybe creating a class for each shader, ie Bumpmap shader, pp lighting shader, etc.
So really what I am trying to ask is that I feel my system is inadiquate when it comes to parameters that are used only once (ie beta_1, beta_2 etc in the above shader) because I would have to insert them into the map and given the amount of shaders that could be inserted, then the map would just become to big.

If you are allowed to comment, may I ask how you approached this?

What I have wrote is probably confusing, so just ask if you don't understand .. mmm i need coffee

[edited by - robertc on February 13, 2003 6:01:16 PM]