From: colin@nyx10.cs.du.edu (Colin Plumb)
Newsgroups: rec.games.programmer,sci.math
Subject: Re: polygons in space -- probably easy
Date: 13 Apr 1995 14:02:00 -0600

Well, telling which is in front is easy - you just extend the polygons
to planes by ignoring their edges, project a ray and see which gets
hit first.  I.e. if missing is problem, ensure that the ray can't miss.

With certain assumptions on the polygons, you can draw them in back-to-front
order and eliminate the need for Z-buffering, but you haven't said that
these assumptions are possible.  From your description, it's possible
to have three objects A, B and C such that A is in front of B, B
in front of C and C in front of A.

A nice technique you might want to try are the BSP trees popularized
by Doom.  They work in three dimensions and have the nice property
that one tree can cover all possible observer positions.  If your
polygons move around a lot, it's going to be trickier, however.

To build a BSP tree, do recursive subdivision on your planes.  Pick a
partitioning plane.  This is usually one of the polygons, but doesn't
have to be.  Divide everything else into things on one side of that
plane and on the other.  Objects that intersect the plane will have to
be split.

Keep dividing until every partition contains just one object.

To render this tree, start at the root and figure out which side the
observer is in.  Render the furthest part, then the root itself (if
it's a polygon that should be rendered), then the near side.  At each
sub-tree, do the same thing.
-- 
	-Colin