Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!wuarchive!mit-eddie!bloom-beacon!eru!hagbard!sunic!dkuug!freja.diku.dk!bombadil
From: bombadil@diku.dk (Kristian Nielsen)
Newsgroups: comp.graphics
Subject: Determining polygon relative position
Keywords: Realtime, polygonal rendering, hidden surface removal
Message-ID: <1990Nov8.193625.18540@diku.dk>
Date: 8 Nov 90 19:36:25 GMT
Distribution: comp
Organization: Department Of Computer Science, University Of Copenhagen
Lines: 25


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/
==========================================================================