PKONTKANEN@cc.helsinki.fi (11/17/89)
I am going to make a program, which uses filled 3D vector
graphics with hidden-surface removal. Normal methods - transform and
rotation matrices - aren't fast enough for my purposes. I have planned
to build a whole city with vector graphics. Can anybody recommend
any good books about this subject? Does someboby know better ways
to calculate the necessary transformations and rotations?
I haven't yet decided what kind of graphics routine to use.
It should make possible to move anywhere in arbitrary 3D-world in
real time. Does anybody have good ideas how to do this?
Right now I'm learning how to make use of Blitter and Copper
directly through hardware. It is in all probability the fastest way
to draw graphics. On the other hand, it's also quite difficult and
troublesome. So, I don't know whether or not to utilize it. If
somebody has any comments, I would be pleased to hear them.
Petri Kontkanen
Sullivan@cup.portal.com (sullivan - segall) (11/19/89)
> > I am going to make a program, which uses filled 3D vector > graphics with hidden-surface removal. Normal methods - transform and > rotation matrices - aren't fast enough for my purposes. I have planned > to build a whole city with vector graphics. Can anybody recommend > any good books about this subject? Does someboby know better ways > to calculate the necessary transformations and rotations? > I haven't yet decided what kind of graphics routine to use. > It should make possible to move anywhere in arbitrary 3D-world in > real time. Does anybody have good ideas how to do this? > Right now I'm learning how to make use of Blitter and Copper > directly through hardware. It is in all probability the fastest way > to draw graphics. On the other hand, it's also quite difficult and > troublesome. So, I don't know whether or not to utilize it. If > somebody has any comments, I would be pleased to hear them. > > > Petri Kontkanen > > If direction of motion is important, use quaternions (20 FLOPS) instead of matric representations (24 FLOPS). If direction is unimportant you can use either body axis angles, or Pitch, Yaw, Roll sequences. If Roll is unnneccessary, try SARA/SADEC angles (Right Ascention, and declination.) SARA and SADEC will allow you to point toward any object, but won't include any information about your attitude. PYR sequences include your attitude but don't describe transitions (eg: 180, 180, 0 == 0, 0, 180) quaternions are your best bet if you need to preserve the method of translation. As for where to find them? I have no idea. All are used in satellite attitude control. Perhaps NASA literature would suffice. -ss
wade@pnet01.cts.com (Wade Bickel) (11/19/89)
PKONTKANEN@cc.helsinki.fi writes: > > I am going to make a program, which uses filled 3D vector > graphics with hidden-surface removal. Normal methods - transform and > rotation matrices - aren't fast enough for my purposes. I have planned > to build a whole city with vector graphics. Can anybody recommend > any good books about this subject? Does someboby know better ways > to calculate the necessary transformations and rotations? > I haven't yet decided what kind of graphics routine to use. > It should make possible to move anywhere in arbitrary 3D-world in > real time. Does anybody have good ideas how to do this? > > Petri Kontkanen > > No can do! If you want to move in arbitrary 3-Space your going to have to do the algebra. If nothing in your 3-D world moves you can cut some big corners, but if the viewpoint is to be able to move to any point and look in any direction you have to do the math. Try developing a fixed point integer system if you want to strive for speed. ie: maintain the fractional part of your coords in the lower ? bits (2 is good), and use the higher bits to store the whole part of your numbers. Note that if you do this, you must shift of excess fractional bits after a multiply, or shift them in befor a divide. Note also that it is possible to use different radix's (positions of the "decimal" point) together, as long as your program knows what the radix of the results must be, and provides the proper shifting. As far as a good text, try Foley & VanDam's (not sure of the spelling) "Fundimentals of Interactive Computer Graphics", or Newman and Sproull's "Principals of Interactive Computer Graphics" (McGraw Hill). Good Luck, Wade. UUCP: {nosc ucsd hplabs!hp-sdd}!crash!pnet01!wade ARPA: crash!pnet01!wade@nosc.mil INET: wade@pnet01.cts.com
bmacintyre@watdragon.waterloo.edu (Blair MacIntyre) (11/21/89)
PKONTKANEN@cc.helsinki.fi writes: > > I am going to make a program, which uses filled 3D vector >graphics with hidden-surface removal. Normal methods - transform and >rotation matrices - aren't fast enough for my purposes. I have planned >to build a whole city with vector graphics. Can anybody recommend >any good books about this subject? Does somebody know better ways >to calculate the necessary transformations and rotations? ( what do you mean by filled 3D vector graphics? ) I assume you mean the normal "graphics pipeline" approach when you are talking about matrices? If you are going to build a large scene, the amount of time taken to multiply the standard rotation and transformation matrices onto the top of the stack is _trivial_ compared to the rest of the work needed, since you are only doing the transformation calculations once per scene. What slows you down is the rendering sequence: for every point ( line vertex, etc ) you have to do a matrix * vector multiplication, do the clipping and do the scaling to the screen coordinates. If that wasn't bad enough, you wish to do hidden surface removal which is incredibly expensive. Since you say you want to move about in an arbitrary 3D-world, no nice tricks will be available. I have a library of 3D routines ( that I've been working on off and on - more off than on - for over a year and may someday release ) that do things in the general case. It's not terribly fast, though, compared to an IRIS. :-) Summary: if you want to draw a city and travel around, make some simplifying assumptions if they will help. Perhaps only traveling on the ground with no tilt ( a "car view" ) or ( even better, perhaps ) use a bounded 3D world so that you can use specialize routines ( the general ones won't cut it ) > I haven't yet decided what kind of graphics routine to use. >It should make possible to move anywhere in arbitrary 3D-world in >real time. Does anybody have good ideas how to do this? On an Amiga, I feel quite confident in saying this is _not_ possible in general (see above ). [ Actually, moving anywhere is possible, drawing from anywhere is the hard part. ( I am assuming you have a fairly large "city" that you want to display ) :^) ] There are tricks you can do to reduce the amount of data you want to draw but if you want to draw a lot of stuff the computer just isn't fast enough. Get a math coprocessor and things will get a little better, but not much. Wade posted: ] No can do! If you want to move in arbitrary 3-Space your going to ] have to do the algebra. If nothing in your 3-D world moves you can cut some ] big corners, but if the viewpoint is to be able to move to any point and ] look in any direction you have to do the math. They went on to say: ] Try developing a fixed point integer system if you want to strive ] for speed. This is fine for a fixed size world, but for an "arbitrary 3D-world" I think you will need to use floating point. ] As far as a good text, try Foley & VanDam's (not sure of the ] spelling) "Fundamentals of Interactive Computer Graphics", or Newman and ] Sproull's "Principals of Interactive Computer Graphics" (McGraw Hill). These books will not help you with anything that will allow you to get any speed improvements over the "standard" approaches. If you aren't using a graphics pipeline approach, you should look into these books, however. The matrix representation is as fast as you are going to go, in general. -- -- Blair MacIntyre, Professional Leech on Society ( aka CS Graduate Student ) -- bmacintyre@{watcgl, watdragon, violet}.{waterloo.edu, UWaterloo.ca} -- "Love can be strange sometimes ... if it's done right!"
swarren@eugene.uucp (Steve Warren) (11/28/89)
In article <18344@watdragon.waterloo.edu> bmacintyre@watdragon.waterloo.edu (Blair MacIntyre) writes: >PKONTKANEN@cc.helsinki.fi writes: >> I haven't yet decided what kind of graphics routine to use. >>It should make possible to move anywhere in arbitrary 3D-world in >>real time. Does anybody have good ideas how to do this? > >On an Amiga, I feel quite confident in saying this is _not_ possible in >general (see above ). What did the Rainbird guys do to get the 3D graphics for Starglider II? I realise the landscape was pretty sparce compared to a city, but maybe a trade-off using similar techniques would work? Starglider is really smooth. Maybe if the frame-rate was reduced by a factor of four a proportionate increase in complexity would be possible. I am not knowledgeable as far as the requirements for the calculations. I just play the game ;^). --Steve ------------------------------------------------------------------------- {uunet,sun}!convex!swarren; swarren@convex.COM
bmacintyre@watdragon.waterloo.edu (Blair MacIntyre) (11/29/89)
swarren@convex.COM (Steve Warren) writes: >bmacintyre@watdragon.waterloo.edu (Blair MacIntyre) writes: >>PKONTKANEN@cc.helsinki.fi writes: >>> I haven't yet decided what kind of graphics routine to use. >>>It should make possible to move anywhere in arbitrary 3D-world in >>>real time. Does anybody have good ideas how to do this? >> >>On an Amiga, I feel quite confident in saying this is _not_ possible in >>general (see above ). > >What did the Rainbird guys do to get the 3D graphics for Starglider II? Note that I said "In general" I went on to say that as soon as you start making simplifying assumptions, such as a fixed size world, things can be spead up. Specifically, if you know the range of values you will be given, it should be possible to write a fixed point math library which is significantly faster than a generic floating point library. An example of generality: I wrote a simple surface patch routine. If I use Bezier or Cardinal Spline basis matrices, the patch's get rendered fine. If I use a normal B-Spline, it screws up. Why? The FFP library isn't precise enough. Somewhere in there, I lost enough precision to screw it up. How do I know this? I recompiled with the IEEE library and it works just fine. So, a simple assumption which would double the speed right now would be that I wouldn't do things that would kill me with regard to FFP precision. In a game _I'm_ writing, that's simple to enforce. >I realise the landscape was pretty sparce compared to a city, but maybe >a trade-off using similar techniques would work? Like I said, restrict yourself, perhaps in area or viewing positions. ( although I don't think the last one will matter ) >Starglider is really smooth. Maybe if the frame-rate was reduced by a >factor of four a proportionate increase in complexity would be possible. It is indeed. I was impressed when I first saw it. -- -- Blair MacIntyre, Professional Leech on Society ( aka CS Graduate Student ) -- bmacintyre@{watcgl, watdragon, violet}.{waterloo.edu, UWaterloo.ca} -- Dating, verb: prearranged socializing with intent.
jmdavis@cbnewsd.ATT.COM (j.michael.davis) (11/29/89)
In article <734@crash.cts.com> wade@pnet01.cts.com (Wade Bickel) writes: >PKONTKANEN@cc.helsinki.fi writes: >> >> I am going to make a program, which uses filled 3D vector >> graphics with hidden-surface removal. Normal methods - transform and >> rotation matrices - aren't fast enough for my purposes. I have planned > No can do! If you want to move in arbitrary 3-Space your going to ^^^^^ ACK ACK!!! you're not your! >have to do the algebra. If nothing in your 3-D world moves you can cut some > Try developing a fixed point integer system if you want to strive Good idea, but also try pre-computing the sines and cosines, an array of 100 for each will provide less than 1 degree accuracy if you keep track of the signs of the numbers and degrees. With this table and the above mentioned fixed point, or even better, total integer but scaled you should be able to do a sine by just doing a table look-up. I have seen this technique used on the APPLE II (gawd that is a long time ago) and it works quite fast there. I suspect that ELITE for the Apple also uses this technique. 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. -- ---------------------------------------------------------------------------- I am just about fed up | Mike Davis and I will only take it | ..!att!ihlpm!jmdavis a few more times. |
bmacintyre@watdragon.waterloo.edu (Blair MacIntyre) (11/30/89)
jmdavis@cbnewsd.ATT.COM (j.michael.davis,ix,) writes: >In article <734@crash.cts.com> wade@pnet01.cts.com (Wade Bickel) writes: >>PKONTKANEN@cc.helsinki.fi writes: >>> I am going to make a program, which uses filled 3D vector >>> graphics with hidden-surface removal. Normal methods - transform and >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. ^^^^^^^^^^^^^^ On an Amiga?!?!? He said he wanted speed. To do this you would have to rewrite all the blitter functions in software. Of course, then you could put in simple goraud shading and some other things, but it would be *yawn* a bit of a sleeper. -- -- Blair MacIntyre, Professional Leech on Society ( aka CS Graduate Student ) -- bmacintyre@{watcgl, watdragon, violet}.{waterloo.edu, UWaterloo.ca} -- Dating, verb: prearranged socializing with intent.
vinsci@ra.abo.fi (Leonard Norrgard) (12/01/89)
Look up the article on BSP-trees in the SIGGRAPH '83 proceedings, pp. 65-72, by H. Fuchs, G. D. Abram & E. D. Grant. Since the city to be drawed (hopefully :-) is static, BSP-trees should be a reasonable solution to your speed requirements. In short, the alghoritm allow you to redraw the scene (the city) from any arbitrary angle without recalculating hidden surfaces, but instead traverse the tree. -- Leonard PS. [To those of you waiting for the Sang info] The Sang transputer board info will come soon. I haven't found the time to type it in yet. DS. -- Leonard Norrgard, vinsci@ra.abo.fi, vinsci@finabo.bitnet, +358-21-6375762, EET.
peter@sugar.hackercorp.com (Peter da Silva) (12/01/89)
In article <18788@watdragon.waterloo.edu> bmacintyre@watdragon.waterloo.edu (Blair MacIntyre) writes: > On an Amiga?!?!? He said he wanted speed. To do this you would have to > rewrite all the blitter functions in software. That may be faster, if the mean size of polygons is smaller than X number of pixels. For example, it's faster to display a standard 8x8 font with the CPU than with the blitter. -- Peter "Have you hugged your wolf today" da Silva <peter@sugar.hackercorp.com> `-_-' 'U` "Really, a video game is nothing more than a Skinner box." -- Peter Merel <pete@basser.oz>
gilmore@vms.macc.wisc.edu (Neil Gilmore) (12/03/89)
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 | +-----------------------------------------------------------------------+