|
Author Topic:   anyone got pseudocode for first pass through tree?
Zoombapup
New Member
posted November 26, 1999 06:35 AM            
I am a little bit stuck with my implementation of the bintritree (using the two pass brute force method), I cant for the life of me figure out how to generate the tree without a split que.

I currently have a pool of bintri structures (the usual five pointers (actually indexes)), and a byte based implicit variance tree.

Ok, so far...

Now I need to basically build the tree using these two structures. But I guess I am missing something. I dont see how I can build the tree UNLESS I remove the bintri's that have been split (which Is ok, but that seems like its basically making a split que, which apparently isnt needed in the brute force method).

Anyone care to share some psuedocode for the brute force first pass? something rough would be enough.

Do the split bintri's need to be removed from the bintri list? (I am guessing so, so that the priority of the remaining unsplit tri's is taken into account properly). If this is the case, isnt this just a split que forming for the split tri's?

Ah well.. I'll go ahead with my own version until I figure it out.

------------------
Programmer - Team17 Software Ltd. (Although probably not endorsed by them :))

IP:

LDA Seumas
unregistered
posted November 26, 1999 02:22 PM           
They don't need to be removed from the tree as they are split; if they were, it would no longer be a tree, and would be, as you said, a collection of binary triangle structures in a split queue. I keep the tree intact so that I can recurse down the tree for the second and (if using detail texturing without multi-texturing hardware) third times, and so I can pass vertex coordinates on the stack rather than storing them in RAM.

------------------
-- Seumas McNally, Lead Programmer, Longbow Digital Arts

IP:

Zoombapup
New Member
posted November 26, 1999 03:11 PM            
I can understand how you pass the coordinates (I guess thats at render time?).

I have a problem with the initial creation of the tree though, you choose which triangles to split based on a max of the variance. After you split a triangle, its variance shouldnt be considered because that would lead to a loop (find highest variance would always find the same triangle).

So a split implies that the triangle is then not considered for variance checking. How do you store this information? In the implicit tree? Or do you recalculate the variance tree in its entirety (making the variance of split triangles null?)

Basically, how do you make sure that a split triangle is never needed to be split (itself, not its children) again???

Phil.

------------------
Programmer - Team17 Software Ltd. (Although probably not endorsed by them :))

IP:

LDA Seumas
unregistered
posted November 26, 1999 03:33 PM           
I only split triangles if their child pointers are both NULL, and I recurse down into the children if they are not NULL.

------------------
-- Seumas McNally, Lead Programmer, Longbow Digital Arts

IP:

Zoombapup
New Member
posted November 26, 1999 03:36 PM            
Yeah, that makes sense.. but do you visit the nodes more than once?

I guess my biggest problem is that in order to select the next tri to split, you need to find the highest variance. But once that triangle is split, its variance shouldnt really matter???

Phil.

------------------
Programmer - Team17 Software Ltd. (Although probably not endorsed by them :))

IP:

LDA Seumas
unregistered
posted November 26, 1999 03:56 PM           
No, the recursive split test and rendering functions only visit each binary triangle once per pass through the data.

I don't "select the next tri to split"; I just split everything that is above this frame's global variance threshold (modified by distance). To get a relatively consistent triangle count, I modify the variance threshold each frame to try to come closer to the desired count.

Does that make sense?

------------------
-- Seumas McNally, Lead Programmer, Longbow Digital Arts

IP:

Zoombapup
New Member
posted November 26, 1999 04:06 PM            
Yeah, thats much clearer, so you basically dont necassarily "walk" the tree as you would normally while building the tree, in effect, your setting a threshold and just doing a simple comparison per tri.. makes a LOT more sense now (as each tri is split, its children can be compared to the threshold as well, and then split if they fall within the threshold).

So really your not 100% sure how many tri's a specific threshold for the variance is going to create (unless you cap the number of splits per frame).

Ok, I'll take a stab at implementing that and see what turns up. Thanks for the info.

Phil.

------------------
Programmer - Team17 Software Ltd. (Although probably not endorsed by them :))

IP: