From: thinman@netcom.netcom.com (Lance Norskog)
Subject: Re: Object database rendering
Date: Sat, 11 Jan 92 02:33:39 GMT
Organization: Netcom - Online Communication Services  (408 241-9760 guest) 



brucec@phoebus.labs.tek.com (Bruce Cohen) writes:

>In article <1992Jan10.030838.20727@milton.u.washington.edu>
>thinman@netcom.netcom.com (Lance Norskog) writes:

>> A: just use an array of pairs of: (Zvalue, poly#).
>> When you project poly X, check all the corners.  If they are
>> all under poly Y, toss poly X.  Else, "paint" poly X
>> into the (Zvalue, poly X) tuples.  When all polys are done,
>> paint the screen from the poly numbers.  You can use
>> the Z values for mist or something.  Before filling the
>> Z array, clear it with the background poly.

second algorithm omitted because I don't like it now.

>I may be missing something, but I think both these algorithms as stated
>will have trouble with non-coplanar polygons which either intersect or
>lie on intersecting planes.   Or were those cases you omitted for
>clarity?

No, algorithm A handles intersecting polys.  This is actually
overkill if your world modeller doesn't let objects intersect:
the polys can't intersect!  Alg. A paints via the Z-buffer
and has the classic Z-buffer feature of fully handling intersecting
polys.  The difference from a classic Z-buffer is that it 
figures out that a "behind" poly is fully covered by one
on-screen poly, and so tosses it trivially.  This is the point
of saving a poly number at each pixel along with a Z value.

This only justifies the extra RAM and extra RAM touches if
you toss lots of "behind" polys.  I would maintain a hash
array of Z values clipped to, say, 12 bits.  You project
the entire poly database and assign each poly to one bucket
of the array, it doesn't matter which corner you use.
Each bucket is a now a linked list of polys which are roughly
at the same distance from the viewpoint.  Now, starting
from the bucket for 0, you apply algorithm A, painting
all the polys in the list.  

Alg A. works better if the polygons come in groups which
are known to be convex from any angle.  The modeller
could have the job of noticing these groups.  For example,
an airplane would be broken up into fusillage, wings,
etc. with all little fins & whatnot off in their own 
"convex groups".  Alg. A can then figure out that a
poly is completely obscured by a wing, where it would
not be obscured by any one little poly in the wing.

This is probably interesting on other hardware than the
PC.  For example, a well-designed machine would let
you plug in high-speed static RAMS and just use them
as an explicitly addressed array instead of an invisible cache.

Lance Norskog