Thread: [Algorithms] Huge terrain antiaiasing
Brought to you by:
vexxed72
From: Maltez <ma...@no...> - 2002-03-26 00:10:11
|
Hi geeks, I'm toying with a *large* terrain rendering engine. I use a Roam-like approach to simplify it at runtime to 10k-80k tris for = a 2k x 2k terrain far clip (representing 130km x 130km). Besides the fact that i'm facing Z-precision, i get ugly *aliasing* as = the camera move near ground looking lines of sight at horizon : that's a = typical polygon aliasing problem! Mipmap don't solve because i'm already using it. I checked that aliasing doesn't come from the Roam engine itself because = it's still aliased when the triangle mesh is frozen. 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. 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 ? I'm looking for any sort of accumulating algo which would use the = bintree structure and it's geometry coherency. I've heard of slicing space in 8 octants, each 45=B0 wide around = camera's eye but i'm wondering how to handle that. My goal is to get a *very* fast ordering : i'm currently achieving a = 60-150FPS at 40k tris, so i can't afford loosing time: say, << 1ms max = for 40-50k tris. Any experiences or ideas ? Maltez |
From: Mark D. <duc...@ll...> - 2002-03-27 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 X-Y 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 front-to-back 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 X-Y 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_X-eye_Y<A_X-A_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 left-child and right-child 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 X-Y 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 left-first/right-first 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, up-left diagonal lists, up-right 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 > 60-150FPS at 40k tris, so i can't afford loosing time: say, << 1ms max for > 40-50k 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 re-sort 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. |
From: Maltez <ma...@no...> - 2002-03-28 20:51:09
|
> > 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? That's damn very sensitive! > 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. Z Buffer can't be on with polygon antialiasing. So, i'm not to catch what you with "slight out of order" ? > > > > > 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 > X-Y 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 front-to-back 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 X-Y 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_X-eye_Y<A_X-A_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 left-child and right-child > 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. I was just heading this way, but i'm still confused to get a clean algo in order to use frame coherencies in the recursion like a frustrum culling algo with flags ALL_IN, ALL_OUT, PARTIAL_IN. > > 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 X-Y 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). Never remove a tri ? The 2048 lists will contain all 5,6 tris, then. > Now suppose we have all the left-first/right-first 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, > up-left diagonal lists, up-right diagonal lists). X+Y and X-Y directions involve two 1D arrays with 4096 lists. Am i wrong ? At the end, it will get all (40k) tris in the lists of the 4 arrays. > > 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 > > 60-150FPS at 40k tris, so i can't afford loosing time: say, << 1ms max for > > 40-50k 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, I have 1 byte overhead per height point. In fact, i use 5 bits for state and 11 bits for variance. Then, I can't add 1 bit ! > 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 Me too, i currently expand 1 tri into 4 microtris. > only re-sort 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. I'm afraid non-sorted tris will be visible. |