RE: [Algorithms] Sorting triangles

[Tom F. <to...@mu...>]

There's probably a much more elegant way of doing this, but for n faces you
make a big n*n table. Each entry in the table says that either face 1 must
be drawn first, or face 2 must be drawn first, or it doesn't matter, or they
intersect. You need to remember that backface culling means, e.g. that all
the tris on the outside of a convex hull are "don't care" w.r.t. each other,
and all the tris on the inside are all also "don't care" w.r.t. each other.
So if you draw all the insides then all the outsides - perfect
alpha-sorting! That what this is meant to automate.

Ideally you won't have any "intersect" entries - you would split one of the
two tris along the plane of the other as a preprocess step. Note that in
this sense two planes can intersect even if they don't intersect in the
conventional sense - if the line of the intersection of their planes
actually goes through both tris, then they intersect, because you can't
decide which needs to always be drawn first - it's view-dependent.

Then you go through the table trying to find the face that has no entries
against it saying "must be drawn second", or in practice you find the one
with the leats number of "must be drawn second" entries. Add that to the
draw list, blank that row and column. And repeat until you're done.

Like I say, it's very brute-force, but it's an offline preprocess and the
above is easy to write :-)


(actually on the ST I did the above with convex sub-units of the object, not
individual faces, but it's the same idea).


Tom Forsyth - Muckyfoot bloke and Microsoft MVP.

This email is the product of your deranged imagination,
and does not in any way imply existence of the author.

> -----Original Message-----
> From: Jason Zisk [mailto:zi...@n-...]
> Sent: 10 July 2003 19:26
> To: gda...@li...
> Subject: Re: [Algorithms] Sorting triangles
> 
> 
> > then within objects transparent tris are sorted offline 
> using a pretty
> > expensive brute-force sorter that basically knows you can 
> draw the front
> > face at a different time to the back face, and finds the 
> best sort order
> > so that tris draw over each other properly. I think the algorithm is
> > similar-ish to a BSP tree, though it can be resolved statically.
> 
> I actually thought of generating a BSP tree for each err... 
> tree... but
> thought it was too much.  Archives seem to be dead at the 
> moment, could you
> elaborate on the Atari ST style pre-generated sorting a bit? :)
> 
> Is it like Martin Fuller's idea of generating draw lists for 
> each axis of
> the object?
> 
> I've tried simply not sorting within the trees/bushes but the 
> errors are too
> obvious (at least for the art team :).
> 
> - Jason Zisk
> - nFusion Interactive LLC
> 
> 
> 
> 
> -------------------------------------------------------
> This SF.Net email sponsored by: Parasoft
> Error proof Web apps, automate testing & more.
> Download & eval WebKing and get a free book.
> www.parasoft.com/bulletproofapps1
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=6188
>