ABT questions: construction and use

Hmm, it seems nobody has been adventurous enough to respond to any of my questions yet. Perhaps it was a bit overwhelming with all those questions . I''m primarily interested in the 2nd and 4th questions - the ones regarding successive approximation and collision detection - since they will impact the manner in which I build the ABT structure the most.

I would like to have some input from other people before I go off and do something silly though...

Beforehand, please confuse some of my ignorance on abt''s in general, Im commenting from a somewhat removed standpoint.
3) - He says growing, you say shrinking. Is it possible you implemented the algorithm in somewhat a different menthod? Does the abt grow predetermined aabb''s to fit a object that wouldnt otherwise easily fit? or are you shrinking it down to provide the smallest reasonable volume of an object? If I remember correctly though, abt splits an object, and thus would involve shrinking abt''s (they''d fit the split peices better) so Im a bit confused by his statement too...
4)Do you have any reason to believe this wouldnt be possible? with other partitioning schemes it would be. Though the cutoff zone might be different.
5) question on your question- such as how halflife and morrowind load other sections of the world as needed?

I still haven't resolved any of the previous questions on my own, so they all still stand. I've also got a new issue since getting the ABT working and testing it on some data (A Quake3 level).

First, to elaborate on my question #2 involving the successive approximation: if I use a scoring method as listed under question #1, then the iterations through the split-picking algorithm would need to take the weights into account. For instance, if I set the weights to worry 99% about splits and 1% about volume, then there really isn't a good way to decide where to try a sample next, as the # of splits in the specific geometry is unpredictable even after you've taken several samples. However, the volume is completely predictable - it maps linearly to the percent value used to split with, and the axis score can't really be "approximated" since the split-planes are axis-aligned anyway - you just go with the axis that scores best (taking the best composite score from each axis alignment, not just the axis score), right? In fact, it seems the only thing that really benefits from a successive approximation system is the face balance equation, since it's somewhat continuous but non-linear. So should I just do some successive approximation on the face balance until I get as close to a perfect balance as I can, keeping track of all the composite scores along the way, and then keeping the best-scoring split?

7) But enough of the approximation. I have another issue now, and it's a bit of a pain: sparklies. Tiny gaps arise along the edges of polygons that were split while their neighbor wasn't, resulting from floating point roundoff error around the T-junction there. Since the ABT nodes can overlap a bit to avoid splitting all the geometry, you end up splitting the big faces and not splitting the little faces, and get sparklies along the borders between them. It's rather annoying, and since the ABT's design inherently calls for this behavior, I'm not quite sure what to do about it. Should I keep track of all the edges that got split, and then go hunt down all the other faces that didn't need splitting but have the same edge that got split, and then insert the split-edge-vertex into those faces?

Hopefully someone will help me out... I'd like to make use of the ABT structure but it's not working out perfectly.

[edited by - Assassin on June 19, 2003 3:28:14 PM]

Somewhat this thread slipped through my radar. I''ll try to address your points in greater detail this evening, as it will probably take some time.

Hey Assassin,

Amazing... After coding a BSP for the past few weeks, I''ve decided that it isn''t exactly what I need and so I got into the ABT. I''ve been at it for a few days now and I''m almost done... the amazing thing is that I ran into more or less the exact same problems/questions as you.

As for collision detection, the best thing I can come up with is actually doing exactly what you suggested, which is building a ''planes only'' BSP tree to control collisions. You can of course also use that same tree to access the actual poly data in the ABT and use it to dynamically adjust the geometry (CSG). The additional memory for the BSP tree (assuming ''not'' a 10m poly level) is negligable I believe), besides how otherwise would you do collision exactly, even if you had the ABT localized to 50 polys per leaf? I thought about it, even to create mini BSP''s per leaf or maybe another structure, but you don''t have convex hulls there so you can''t rely on just the leaf geometry. Please share any ideas you might have on that.

As for LOD... just so you''d know I''m using the ABT as a replacement/enhancment for meshes. The goal I''m aiming at is a space sim of sorts, so the only static geometry I have is big *big* bases and ships (the kind where you''re fighter get''s really up-close and personal with ). I want the ABT for those guys (no it''s not an over-kill I have some very good resosns for doing so). What was I talking about? ohh yes, LOD... each leaf holds localized chunks of geometry right? From what I remember about mesh optimizations and progressive meshes (ala Hoppe) what''s done is basically enforcing conservation of an energy function on *localized* areas of the mesh (i.e. vertex in relation to it''s neighbors). What if we simplify each leaf independantly, supplying it with it''s own edge collapse map, meantime also insuring the cracks don''t occur with neighbor leaves (or maybe skirt masking the cracks like in terrain). An enhancment where nodes higher in the tree''s hierarchy have ''regional'' collapse maps or maybe even different index buffers altogether that access the same geometry data as the leaves but disregarding detail to some degree.

I just finsihed reading what I wrote and there is a hole in my progressive mesh theory. A solution can probably be found but I''ll go into it later if anyone''s interested. I have to get back to work and this is a long post as is.

I''d also be interested to see how you approach LOD with a ABT tree. Do you have complete ''objects'' in the tree that change LOD based upon the cam distance, or is there some other way by changing vertex/index buffers in the tree at runtime? I suppose to some extents this is expanding a little more upon question 5 above.

Many thanks
James

A few more questions to add, concerning state-switch optimization and occlusion culling.

8) How can you avoid putting too many materials into a node, to keep the number of drawprimitive calls down? For example, if my split function decides to slice the geometry right on the border of where a material is being used, thus including about 1 or 2 polygons of that material in a node while the node next to it has 500 polygons with that material, you end up having to make a dp call to render 2 polygons, which doesn't seem so hot to me. I'm building the vertex buffers for my ABT nodes (partition spaces) by the following process:

foreach face
 foreach vertex on face
  record index in "seen indices" list
  record material ID in "seen materials" list
make one vertex buffer
make enough index buffer for each of the "seen materials"
dump all vertices listed in the "seen indices" list into the vertex data stream
foreach seen material
 foreach face with matching material ID
  foreach vertex on face
   record translated index into material-matched index buffer
 

which should end up with one vertex buffer per node and one index buffer for each material used in the node. This works properly, I think, but on my test data (a Quake 3 level that probably isn't tessellated enough to see many benefits from splitting, but I'm testing with it anyway) which has a total of 75 materials, the average ABT node gets 40 of them (using a 2000-face vbuffer threshold... a 500 threshold gets an average of 20 materials per node). Since the whole level only has about 22,000 faces, I end up with 14 or so nodes that each need 40 calls to DP (for a total of 560). By comparison, brute-forcing the level only takes 75 DP calls and runs faster when more of the ABT nodes come inside the frustum (with no occlusion culling for the time being, which may resolve this issue a bit). Is the Quake 3 level just using too many materials near each other, or is this a common breakdown of the data in other setups also? Is there a function that can be added to the split evaluator to minimize chopping up materials?

9) Yann, you've mentioned that you use image-space occlusion to the exclusion of all other occlusion methods, such as portals and occlusion frustums... might I ask how you build occlusion hulls from the level geometry? Also, is it worthwhile using that approach for enclosed geometry (like Quake 3 levels) or is it better-suited to open-area geometry? I'm guessing that each ABT node gets an "occlusion mesh" built from the geometry contained in that node, which can then be used to occlude further-away nodes. What kind of mesh simplification can be done to break the geometry up into a valid low-poly occlusion mesh that is "contained inside" the geometry of the node? It seems that plain-vanilla VIPM can't really do that effectively on non-convex geometric sets, so some insight into how to achieve the desired result would be appreciated.

10) On the note of portals for occlusion, could it be possible to auto-generate portals using the ABT-splits? I'm thinking of achieving it by finding all the faces that lie across the split plane, taking the 2D convex hull of them on that plane, and making a portal from that. Alternatively, an edge-connectivity graph could be constructed from the intersection points of the spanning face edges and the split-plane, welding vertices with the "same" position but from faces with different materials, and then tracing loops to make portals. This would of course only work on 2-manifold closed surface geometry, but that shouldn't be too hard for an artist to enforce, right?

Some feedback would be appreciated...

[edited by - Assassin on June 20, 2003 10:42:25 PM]

I can take a crack at number 9).
If I recall correctly, Yann is using a low-poly occlusion skin (auto or hand generated I don''t know) for his set of occluders that is software rasterized with depth info (and opacity?). The rendered image is used to create a hierarchical structure (it''s shrunk down into smaller and smaller maps) to speed up the comming visibility checks.
For the visibility checks, the given node (set of geometry to be tested) has it''s AABB tested against the occlusion info for, well, occlusion. I think he''s mucked around with these checks a little bit, but I think it''s the basic idea and it should let you start thinking about it.
Here''s the link he gave about HOM: http://www.cs.unc.edu/~zhangh/hom.html
This paper also implements screen space projection in addition to the depth method that Yann uses. Never got around to asking why he ditched that test. So Yann, why''d you ditch the projection (overlap) test?

Karg

Thanks Karg, but I already have an image-space occlusion rasterizer that works decently for me. Question 9 was more directed at how to get the low-poly occlusion skin that''s used for doing the occlusion. You can''t just simplify the geometry by any old method, you need to make sure it won''t be occluding anything erroneously by keeping it entirely "inside" the rendered geometry... that''s the issue I''m trying to resolve.

If I recall correctly he uses virtual occluders.

------------------------------------------------------
Cuando miras al abismo el abismo te devuelve la mirada.
F. Nietzsche

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.

Do you think that the best way to manage meshes with ABT''s is to insert the mesh as an entire object, and have meshes at the leaf level as well as a list of faces. The reason for asking this is this is the only way I can see of doing LOD on static meshes e.g. a tree - close up fully 3D, further away 2.5D, eventually becoming an imposter at large distances. You see this would require the mesh object to know where in each of the leaf''s face lists it''s vertexes are stored if it wishes to make modifications to it.

My engine already takes duplicate materials from face lists and groups their rendering together, so I can not see any problems with doing it this way. Can anyone see any potential problems or better ways of managing this?