Path: utzoo!attcan!uunet!cs.utexas.edu!uwm.edu!dogie.macc.wisc.edu!vms.macc.wisc.edu
From: gilmore@vms.macc.wisc.edu (Neil Gilmore)
Newsgroups: comp.sys.amiga.tech
Subject: Re: 3D-graphics
Message-ID: <2754@dogie.macc.wisc.edu>
Date: 2 Dec 89 17:47:40 GMT
Sender: news@dogie.macc.wisc.edu
Organization: University of Wisconsin Academic Computing Center
Lines: 49

In article <3379@cbnewsd.ATT.COM>, jmdavis@cbnewsd.ATT.COM (j.michael.davis) writes...

>In article <734@crash.cts.com> wade@pnet01.cts.com (Wade Bickel) writes:
>>PKONTKANEN@cc.helsinki.fi writes:
(algebra deleted)
>After you get the math part solved how do you plan to solve hidden
>surfaces? This is your next big time hurdle. The math is linear in
>the number of polygons, but the scale factor is large. Simple polygon
>sorting methods are nlog(n) but the scale factor is lower. However there
>are tricks for simple camera movements that is linear, and of course
>there is the zbuffer method.

(more appropriate to comp.graphics) If most of the polys are static, and 
if there is no interpenetration, and if each moving figure is fairly 
static, and if preprocessing time is of no (or small)object, I would 
recommend the use of a BSP (binary space partition) tree. This is a 
binary tree in which all left descendants of a node are spatially to one 
side of that node, and all right descendants are to the other. In order 
to use this, the distance from the viewer to each poly is computed (as 
it would be in other algotithms), and a traversal of the rule, draw the 
near side, draw yourself, draw the far side, results in processing of 
the polys from nearest to furthest. Maintaining a sorted list of the 
centers of moving figures for comparison versus fixed polys allows this 
method to be used without recomputation of the tree to allow moving 
figures. The tree is constructed as follows: pick a polygon and make it 
a node, if the extension of this poly intersects any other polys, divide 
it in two along the intersection. Continue working along util you run 
out of polys.

I have also found that an acceptable trade-off (to me, at least) is to 
store, for each moving figure, 4 sets of polys representing views 90 
degrees apart and choosing the appropriate one to transform and render. 
This takes far less time than hidden-surface removal, and if the figure 
is repeated often (likely the case in games, anyway) the extra storage 
required doesn't hurt too much.

In simple exercises, I used the BSP tree to draw from farthest to 
nearest, obviating the need for hidden-surface removal at all, but 
switched to nearest first w/ hidden surface for the final projects. I 
haven't programmed much on the Amiga yet, but if the blitter is fast 
enough, this might work for your purpose, and releive many headaches.

Hope this helps.

+-----------------------------------------------------------------------+
| Kitakaze Tatsu Raito	Neil Gilmore     internet:gilmore@macc.wisc.edu | 
| Jararvellir,          MACC, UW-Madison bitnet: gilmore@wiscmac3       |  
| Middle Kingdom        Madison, Wi                                     |
+-----------------------------------------------------------------------+