SOrry, haven't had time to respond to this thread until now. I have a lamans ABT demo running over at my site, check Here.

as for your q's.

1) The four functions that I devised were set up alot like yours. I think the main determinant of how they are created depends on the method you're using to calculate the plane. Yann mentioned he's using a Neural network to determine the spot. I've opted for a more sequential method. Rather than finding the optomal split plane, i try to determine the optomial plane in relation to object volumes in order to reduce split faces. The process is a simple linear step through the objects, calculating the percentage of the volume inside this node, in relation to the rest of the world. this creates alot of really isolated sub notes but greatly reduces split faces. (Eg if a node over steps your 20k poly limit, but 19,567 of those polies are in a single object, i create another "floating" sub node around that object itself.)

3) Once you've sized up and down your ABT nodes, there may be some directions that you haven't optomized yet. Re-creating the bounding box after division ensures the tightest, most effecient box around the data possible. Plus, once you're children are modified, the parents must be as well. So resizing the child nodes may allot the parent nodes to become more efficent, which can cut down on frustum checks.

4) Yes. I recall a thread somewhere that Yann mentioned he (at one time) used duel subdivision algorithms. One for rendering (ABT) and the other for collision. Your collision algorithm would probally be similar to the ABT, that is, to attempt to minimize checks against the world, but at the per polygon level inside the leaf node, you'd have to add something else. (I use a simple bounding sphere check against the isolated objects in my node, then use a more percise, octree divided collision detection)

5) Hum.. the first question you had about inserting / removing data, ABT is quite effecient at it. Since it's a binary tree at it's base, you're already getting the least amount of comparisions to find the target node, so placeing data isn't hard. I haven't played with CSG, so i'm not sure if it would be smart to allow runtime CSG changes to the ABT data.. lemmie know if you find anything worth noting.

6) The process you're talking about here is the basis for "Loose Octrees" which essencially allows the object to exist in the best fit box of it's design, regardless of the heirchacy. From what I remember it's a nice system, (used in oddworld?) but i can't comment on it's effeciency in terms of LOD storage, mainly because i haven't messed with it. Let me know any results you find.

7) I've found a simillar problem. However I'll just end up loosing huge gaps during the poly splitting process. I haven't had time to find a fix besides changing the polygon setup in the editor.

8) One method I devised a while ago is combining the textures for a node into a single texture, and changing the UV coords accordingly. This would allow you a single texture rendering pass, and since each leaf would contain it's own texture, you're only looking at MaxNodes() number of textures to load.
Down side is that a single texture for a node may be extreamly large, and that the same texture may exist in 4 or 5 different leafs. If your card has the video memory however, it seems proficient to follow this path.

I hope some of that helps.

~Main

==
Colt "MainRoach" McAnlis
Programmer
www.badheat.com/sinewave

[edited by - duhroach on June 21, 2003 11:48:39 AM]

[edited by - duhroach on June 21, 2003 11:49:16 AM]

If I''m not mistaken Yann said that all occlusion meshes are lo-res ''artist-created''!! meshes.

Assasin, after you''ve determined all the leaves that should be rendered, why not do a second batching by material. I know it won''t reduce DP calls but I think it would save a lot on big levels.

Wrong....

http://www.gamedev.net/community/forums/topic.asp?topic_id=153497

"Automatic, most of the time. On some models, however, the automatic system can fail. That''s where the artists have to jump in."

Whoa, lots of stuff to respond to...

1) The effeciency of each of the four weights highly depend on the method you use to minimize the equation set. It''s a little bit like a snake biting its own tail: the method used to solve the equation set will feed back onto the equation set itself. But that''s unfortunately not avoidable, since we have chaotic functions in it. It is perhaps a good idea to first set priorities. You will never be able to find the totally optimal set, satisfying all 4 equations. So, try to find the most important ones, taking your general engine structure into account: identify your primary bottlenecks, and adjust the weights accordingly. The next step would be an efficient algorithm to minimize the set. I use a neural net. There are an endless possibilities. The easiest one, and possibly even one that will generate a very good plane, is the one you mentioned: simple sampling, and selecting the best spot. But linear sampling (10%, 20%, etc) is not optimal, since most nodes will have "hotspots", ie. concentrate their geometry in some small sub volumes. Your linear sampler will likely miss them. So you could either use a stochastic sampler (sample at random locations), or a sampler that takes the local face distribution into account.

I have recently tested a different system on my ABT compiler, since then NN got too slow on large data sets. What I did is pretty simple: If you consider a polygon, the splitting equation is going to be linear within that polygon, therefore predictable. Outside of the polygon, it is also predictable - no split will occur. The problem is at the edges. So I simple sample potential planes at each single vertex position (according to the selected axis) of each polygon in the node. I also sample the middle vertex, since splitting a triangle exactly in the middle will create fewer child triangles (2 instead of 3), and is therefore a viable plane target. The system performs pretty well, and the results are almost as good as the NN ones, at a fraction of the required processing time.

2) see 1.

3) After you computed the node separation plane position, you get two child nodes. At this point, you will have to recompute the exact bounging volume of each of the two subnodes, since they will likely present non-optimized dimensions, inherited from the parent AABB. In the case of a node fusion further down the hierarchy (or face exchang, see q.8), the parent node size will not match the child''s volume anymore. That''s why in this case, you''ll need to rebuild the tree from bottom to top. See it this way: the top-bottom pass was just a helper structure to determine the primary leaf distribution. Once the leaf positions and sizes have been determined, and optimized to fit local small scale geometry, you rebuild a perfect match tree starting from the bottom.

4) Well, that would entirely depend on your CD system. Generally speaking, a tree structure that is optimal for rendering will not be optimal for collision detection, and vice-versa. On modern hardware, an ABT leaf intended for rendering should have around 1000 to 2000 faces. Less than 300 will make you lose performance (note that it''s often not avoidable to have leaves with perhaps 50 faces or less. But you should try to minimize those cases, since they won''t offer optimal performance). For CD, such face counts are lethal. You basically have two possibilities: either you continue subdividing the leaf into CD-only subleaves, or you use a separate data structure, ie. a second tree. I used the later approach, but the former one would probably work just as well.

5) You want to implement realtime CSG ? That''s going to be pretty tough, since each operation will invalidate the entire branch below the two operands. Your only choice in that case, is to fully recompute that branch. Besides that, I''m not sure if an ABT is a good intermediate structure to use in an editor. An ABT is primarily aimed at maximal processing speed for rendering, and the efficient insertion of linearily moving dynamic objects. It will not perform very well on an environment that constantly changes in a non-linear fashion. You should consider alternative representations for an editor. Perhaps a simple scenegraph, similar to the one internally used by 3DSMax. It will not give you optimal rendering behaviour, but is better suited for object creation / removal and modification.

6) Yes you can do that, but it will denormalize the tree. Since most objects will struggle a boundary somewhere, they will quickly walk up the tree. Even worse, keep in mind that two locally near nodes do not have to be hierarchically local. For example, if you have two coincident leaves, lying just besides each other, they could very well belong to two totally separate branches of the tree, that will only meet at the root (in the worst case). An object struggling those leaves will, if not splitted, slide up the tree and end up in the root node. In the end, a large percentage of your objects will be localized in the upper parts of the tree, and only very small objects in the deeper leaves. Your tree will get very inefficient.

7) T-junctions are evil™. Yes, they will arise in an ABT, due to the local splitting behaviour. Once the tree is built, a T-junction removal pass is almost mandatory. Keep track of coincident edges of faces assigned to different leaves, and wether or not one of those faces was split along that edge. In a post-process, identify all critical edges, and resolve T-vertices by subdividing the other connected face. This process will generate a few more faces, but is vital for good visual quality.

8) This is done by one of (the several) optimization passes on the leaves, once they are created. Another possiblity is to directly take material boundaries into account, when creating the tree. But that approach doesn''t work for me, because of the way I treat shaders. It might work for you, though - the material balance would then simply become another weight when selecting a subdivision plane. If you opt for the post-optimization process, you can build comparative heuristic, that first identifies critical faces (ie. very low face counts with a certain material), and then tries to reinsert them into a nearby node, that already contains a certain amount of that material. This process will most likely grow the other node, so it''s a tradeoff: tree localization vs. optimized vertex arrays. This optimization pass also answers your question number 3: this is one of the optimizations that will invalidate the parent bounding volumes.

Then, there is another possibility I used: sometimes, you just can''t find an adequate leaf to insert the offending faces. In that case, simply dump them into a "quarantine list": remove them from the leaf (+ resize it), and add them to a critical face list. Built your entire ABT without those faces. That''s your primary ABT. You are left with a list of hard to localize faces, distributed all over the level space. Now you run a second ABT creation over those. This one will be a lot shallower, and will have much less faces than the primary one. Since the nodes will also be much larger in volume, it will fusion the formerly unlocalized faces sharing the same material, from the entire scene. At runtime, you''ll have to traverse two ABTs, but it''s generally worth it. Your vertex array set will be much hardware friendlier.

On a sidenote, a Quake3 level is pretty much the worst dataset you can feed an ABT with. An ABT is intended for high to very high polycount scenes, something from 200k to millions of faces. The efficiency relies on the fact, that the number of different materials is small compared to the number of faces. That is not the case in low-poly environments, such as Quake3 levels. You know, you wouldn''t even need a spatial structure for a Q3 level, simply brute forcing the entire thing will probably be faster. For efficiency tests, I''d recommend a scene of at least 100,000 faces.

9) As RandomLogic mentioned, my occlusion meshes are semi-automatically created, with artist support where needed. The occlusion skin is totally independent of the ABTs. They are neither included, nor dependent on them. They use a separate strcuture, an octree without splits, to be precise. Since they are software rendered, splits are a big no-no. OTOH, we can keep track of each individual polygon, and flag its render state. A polygon can thus be assigned to multiple nodes (impossible for vertex arrays/buffers), which makes an octree the structure of choice.

At runtime, the occlusion skin is rendered from this tree, as a totally separate entitity. In fact, the occlusion skin geometry is not even stored in the same structures as the main scene geometry (for swapping purposes). The scene ABT AABBs are then individually tested against the occlusion map.