bombadil@diku.dk (Kristian Nielsen) (11/09/90)
Given a list of 3D polygons defined by the co-ordinates of the corner points, does anyone know of a SIMPLE and FAST way to sort the list so that if polygon A is partly or wholly covered by polygon B, then polygon A will be placed after B in the list? I.e. how does one determine which of two polygons is closest to view? I use a simple parallel projection for display, that is polygons are rendered in 2D simply by dropping the Z-coord. After the sort, the list will be draw from the tail up, so that parts of polygons that should be hidden from view are overwritten by a polygon closer to the eyepoint. I've tried the obvious - to average the z-coords and sort by these values, and it failed miserably. Any references, ideas, algorithms etc. will be greatly appreciated. Please note that the sort is for real-time rendering in pure machine-code using fixpoint arithmetics, so I need a really simple and really fast one. If I get enough Email, I will post a summary so as not to provoke flames for drowning the net. ========================================================================== Kristian Nielsen | /// Only the AMIGA Student at DIKU, University of Copenhagen | /// (Institute of Computer Science) | \\\/// makes it possibly! Denmark | \XX/ ==========================================================================
jcs@crash.cts.com (John Schultz) (11/10/90)
In <1990Nov8.193625.18540@diku.dk> bombadil@diku.dk (Kristian Nielsen) writes: >Given a list of 3D polygons defined by the co-ordinates of the corner >points, does anyone know of a SIMPLE and FAST way to sort the list so >that if polygon A is partly or wholly covered by polygon B, then polygon >A will be placed after B in the list? I.e. how does one determine which >of two polygons is closest to view? I use a simple parallel projection >for display, that is polygons are rendered in 2D simply by dropping the >Z-coord. After the sort, the list will be draw from the tail up, so that >parts of polygons that should be hidden from view are overwritten by >a polygon closer to the eyepoint. I've tried the obvious - to average the >z-coords and sort by these values, and it failed miserably. >Any references, ideas, algorithms etc. will be greatly appreciated. Please >note that the sort is for real-time rendering in pure machine-code using >fixpoint arithmetics, so I need a really simple and really fast one. With a need for speed, there are at least two good ways to go: a binary space partition (BSP) or a priority queue (depth sort algorithm). If your polygons don't move relative to one another, the BSP is the way to go. For moving objects, depth sort is the way to go. You can make hybrids of both techniques as well. Both the BSP and depth sort algorithm are explained fully in "Computer Graphics: Principles and Practice", by Foley, van Dam, Feiner, and Hughes (and others). Both algorithms make use of the polygon's 3D normals to resolve depth conflicts. Unresolvable overlap results in polygon splitting (one poly sliced by the plane of another, thus increasing the polygon count). If you're most interested in real-time speed, you can get away without doing the splits if you design your objects correctly (but with a loss of generality). Good luck, John