From: Mark Duchaineau <duchaine@ll...>  20020327 01:11:54

> Maltez wrote: [aliasing problem snipped] > I gave a try with the blue book polygon antialiasing : drawing the tris > front to back with blend GL_SRC_ALPHA_SATURATE and polygon antialiasing > mode. Cute. I wonder how sensitive this is to getting an exact sort? What I propose next allows you to spend as much time as you like sorting per frame, so the sort can be made as good as you like. If the Z buffer is still on, then slight out of order seems like it wouldn't be too hideous. > > The tricky part is the front to back ordering : at each step of the recurse > rendering in the bintree tris, i calculate which subtri is nearest to the > camera and recurse first in it to draw it's subtree. All is perfect but not > very fast! > > Here's my question : do you know of any better solutions to order bintree > triangles from camera point of view ? You are close to a fast approach. Here is what I have been working on to get faster. First note that you have a height map, so sorting is really all in the XY plane. Also note that you have a specialized BSP tree where all the planes are in one of four orientations (horiz, vert, and the two 45 degree diagonals). So the classic BSP fronttoback recursion boils down to asking is your eye (X,Y) on one side or the other of lines in the X or Y or X+Y or XY directions, where that line is the one from the bintree triangle apex to its split point. One of the four cases is this: : : A /\ L /  \ R /  \ /  \ *S* : : If eye_X<A_X then you traverse side L first, else side R. The other cases are similar (eye_Y<A_Y, eye_X+eye_Y<A_X+A_Y, eye_Xeye_Y<A_XA_Y). Which case you are is fairly easy. There are 8 triangle shapes: 1 2 3 4 5 6 7 8 * ** ** * * ** * * \ \   / / / \ \ / / \  \ \ / /  ** * *   * ** * * ** \ / * * The transition table for split parent to leftchild and rightchild shape code is (if I got it right): 1 > 5 8 2 > 6 7 3 > 8 6 4 > 7 5 5 > 4 1 6 > 3 2 7 > 2 4 8 > 1 3 Use the eye_X<A_X test for shapes 5,6; eye_Y<A_Y for 7,8; etc. Okay, that was faster that a more general purpose "closer than" test, but you are still doing around 2N of these tests if you have N output triangles. Here is a way to reduce this to M<<N tests per frame. Note that the triangle will change the order of calls to its kids when the eye crosses (for example) a vertical line in the XY plane. Make a 1D array with 2048 lists, one per possible vertical line. Place all case 5,6 triangles on the associated vertical line list (this happens exactly once per triangle, when it is created). Now suppose we have all the leftfirst/rightfirst decisions recorded using one bit per triangle, and they are correct for the previous frame with old_eye_X. Now we are at new_eye_X. Flip all the bits of the triangles listed in the vertical line lists between old_eye_X and new_eye_X. Do the same thing for the other three cases (horizontal line lists, upleft diagonal lists, upright diagonal lists). If you want this even faster, then only walk as far as you have time along the various lists, stopping when time's up. Update old_eye_X to be however far you got, instead of all the way to new_eye_X. > My goal is to get a *very* fast ordering : i'm currently achieving a > 60150FPS at 40k tris, so i can't afford loosing time: say, << 1ms max for > 4050k tris. The "vertical line list" idea will be fast, certainly <<1ms. The case table simple compare idea will also be <1ms, but not as much under. I don't know what kind of data structures you have, but if you are really lean then the extra data structure for the lists might hurt you. In my case, I work in chunks of triangles in place of a single triangle, and so the overhead doesn't hurt. In this case you only resort internal to a bintree triangle chunk every once in a while, for example when the vertical line is crossed for the chunk, not each individual subtri. Also don't resort if someone oscillates around that line, use some hysteresis such as waiting till you move past the left edge to flip back once you've passed to the right over the center. Cheers, Mark D. 