murrayk@prism.CS.ORST.EDU (04/06/91)
I have been working on programming my IBM compatible (286 for now, soon to be a 486) :) for quite some time now and I have some aspirations to program a game that uses 3-dimensional graphics, probable line graphics. I have looked all over the country for books on the subject. I have read books that include code, and books that include theory from which I created my own code. All to no avail. I can rotate things up the yin-yang but the rotations are not correct. They seem to be absolute to the screen, not to the actual object. I have tried every thing I can think of to remedy this problem, but I have had no luck. I don't know if I am just missing something elemental or if there is actually a big idea that I just don't see... I would be really happy to hear from anyone with some experience in this field about what I am doing wrong. Thanks a LOT. This problem has been giving me headaches for quite some time now. Keith Murray CHAOS Software -------------------------------------------------------------------------------- CHAOS Software Software for someone... 1360 NW VanBuren Keith Murray a.k.a. Slammer Corvallis, OR 97330 murrayk@prism.cs.orst.edu --------------------------------------------------------------------------------
ressler@CS.Cornell.EDU (Gene Ressler) (04/06/91)
In article <1991Apr05.224711.12750@lynx.CS.ORST.EDU> murrayk@prism.CS.ORST.EDU writes: > >I have been working on programming my IBM compatible (286 for now, soon to >be a 486) :) for quite some time now and I have some aspirations to >program a game that uses 3-dimensional graphics, probable line graphics. >I have looked all over the country for books on the subject. I have read >books that include code, and books that include theory from which I >created my own code. All to no avail. I can rotate things up the >yin-yang but the rotations are not correct. They seem to be absolute to >the screen, not to the actual object. I have tried every thing I can >think of to remedy this problem, but I have had no luck. I don't know if >I am just missing something elemental or if there is actually a big idea >that I just don't see... > >I would be really happy to hear from anyone with some experience in this >field about what I am doing wrong. Thanks a LOT. This problem has been >giving me headaches for quite some time now. > >Keith Murray You couldn't have looked _that_ hard. Any descent text on computer graphics will discuss homogeneous view transforms. The idea you are looking for is to translate the object so the point you wish to be the center of rotation is at the origin, rotate, then translate back. Of course you can concatenate these three into a single transformation (in matrix form or all the way to hard-coded arithmetic). See for example Foley and Van Dam, or for a slightly simplified treatment, Hearn and Baker. There are dozens of others. Good Luck. Graphics are a blast. Gene Ressler
2fmlcalls@kuhub.cc.ukans.edu (04/06/91)
In article <1991Apr05.224711.12750@lynx.CS.ORST.EDU>, murrayk@prism.CS.ORST.EDU writes: > yin-yang but the rotations are not correct. They seem to be absolute to > the screen, not to the actual object. I have tried every thing I can I know the problem - I fought with it too. Basically, you have to set the origin to the center of your object and rotate it's points about it's own axis - then with these transformed points, run them through another transformation matrix that has the 'eye' of the person viewing as the origin. But how fast do you want the code to run? I found that pre-rotating your objects about their own axis in some increment of degrees and storing all the points in an array makes for some fast lookups. Given the angle that the object is rotated from North (or Zenith or some arbitrary global zero) you can grab the points for that object at said angle - translate them the distance from the object to the eye (from the origin) and them transform them through your 'eye's angle from North. It's faster (tanslate/rotate once), but the array of points can be a memory hog. Of course you can decide on 20 degree increments and decide only to rotate the object about one axis (as in a BattleZone-like game). As well, sine cosine lookups will make calculating your transform matrix quicker. > think of to remedy this problem, but I have had no luck. I don't know if > I am just missing something elemental or if there is actually a big idea > that I just don't see... > > I would be really happy to hear from anyone with some experience in this > field about what I am doing wrong. Thanks a LOT. This problem has been > giving me headaches for quite some time now. > > Keith Murray > CHAOS Software Well, this atleast is how I've done it. Perhaps someone knows of an even quicker method? john calhoun
ressler@CS.Cornell.EDU (Gene Ressler) (04/07/91)
In article <1991Apr5.201714.29494@kuhub.cc.ukans.edu> 2fmlcalls@kuhub.cc.ukans.edu writes: >In article <1991Apr05.224711.12750@lynx.CS.ORST.EDU>, murrayk@prism.CS.ORST.EDU writes: > >Well, this atleast is how I've done it. Perhaps someone knows of an even >quicker method [for doing view transforms]? > >john calhoun If you're into speed, there was an old Byte (~84) that had a rough but useful article for doing a full view transform (translate eye point to origin, rotate, scale, and optionally apply planar OR concentric (spherical) perspective _transformation_ so you could still do hidden surface removal). They had fudged the whole deal into integers, so the `world' coordinates could be anything -32768 to 32767 (almost; this was the rough part) and the view transform was in assembly language that used 16 bit multiply and divide only as necessary to get pretty good approximate images (there were some view angles where overflow could be arbitrarily bad with their math, but a careful reprogramming got around these). Anyway, the code was in the article; again rough but usable. The reason I remember this is that I fiddled with it for a bit. The code easily interfaced to good old DeSmet C. (This was before DOS 2.0!) Sorry I can't retrieve the article or its date. Anyone else remember? With my 4.77Mhz 8088, it could transform about a 1000 points a second. I'm certain a 486 could approach 100 times this. Actually another guy and I made a project out of building an add-in board with another 8088 scan converting lines, so with both processors running full blast we could get images of a few hundred vectors animated at about 2 frames a second; not much these days, but great fun at the time. Also, there are neat tricks if you're willing to accept orthographic (not perspective) projections and other special cases. For instance, there is an almost trivial hidden surface algorithm for ``floating fishnet'' f(x,y) plots. I've got TP/asm code that, given an array of 21x21 values, displays a 20x20 square grid that can be rotated under cursor control at about 3 frames/sec including hidden surface removal (on an 8Mhz 80286). It does a little prestorage of transformation parameters, but no where near entire images. I suppose I could post it somewhere if there's interest. Sorry for rambling. You can probably tell that squeezing descent 3d graphics performance from marginal hardware is somewhat of a hobby. Gene Ressler
cmk@chi.sub.org (Christian Kaiser) (04/07/91)
[ Followup to comp.graphics... ] In article <1991Apr05.224711.12750@lynx.CS.ORST.EDU> murrayk@prism.CS.ORST.EDU writes: [... 3D graphics & rotation ...] )created my own code. All to no avail. I can rotate things up the )yin-yang but the rotations are not correct. They seem to be absolute to )the screen, not to the actual object. I have tried every thing I can )think of to remedy this problem, but I have had no luck. I don't know if )I am just missing something elemental or if there is actually a big idea )that I just don't see... If I have understood your problem, you seem to be doing the rotations with matrices. You can rotate a set of points around the origin(!) of your coordinate system using a simple matrix multiplication. For simplicity, here is an example for the 2D case (3D is mostly analogous). x', y' = coordinates after rotation x , y = coordinates before rotation phi = angle of rotation | cos(phi) sin(phi) 0 | [ x' y' 1 ] = [ x y 1 ] * | -sin(phi) cos(phi) 0 | | 0 0 1 | Now, the key point is that this transformation rotates around the ORIGIN ( [ 0 0 ] ) of your coordinate system. To rotate around an arbitrary point [ u v ], which may in your case be the center of the object, first translate the rotation center point to the origin, then rotate, then translate it back to where it was before. The equation changes as follows: u , v = coordinates of rotation center | 1 0 0 | | cos(phi) sin(phi) 0 | | 1 0 0 | [ x' y' 1 ] = [ x y 1 ] * | 0 1 0 | * |-sin(phi) cos(phi) 0 | * | 0 1 0 | |-u -v 1 | | 0 0 1 | | u v 1 | You can, of course, multiply the matrices beforehand to get ONE transform- ation matrix in order to save time... For an excellent (really!) introduction into these things try to get D.F. Rogers, J.A. Adams, "Mathematical Elements for Computer Graphics", Second Edition, McGraw Hill 1990, ISBN 0-07-100289-8 . Gruesse, Christian -- Christian Kaiser, Munich, Germany Mail: cmk@chi.sub.org, cmk@chiuur.UUCP
Bobster@cup.portal.com (Robert Jules Shaughnessy) (04/08/91)
I also have had this problem. I think you should fallow what is said in reply #2 and then be sure to NOT DRAW ALL LINES/POINTS witha NEGATIVE Z coordinate. This will cause objects to disapeare when they go behind the view screen (Coordinate Origin). I think this may be what you want since if you do not do this, you do get that local rotation effect. Also there are other ways of doing this. (If your using lines) You could draw the lines with only one negative z coordinate by substituting the -z for 0. This would let yyou view an object more clearly as you pass through them. I hope this is what you want! Also, I would be VERY interested in looking at your Code. Could you send it?
patrik@hexagon.se (Patrik ]berg) (04/08/91)
In article <1991Apr05.224711.12750@lynx.CS.ORST.EDU> murrayk@prism.CS.ORST.EDU writes: > >created my own code. All to no avail. I can rotate things up the >yin-yang but the rotations are not correct. They seem to be absolute to >the screen, not to the actual object. I have tried every thing I can Have you ever thought about that they much probably are correct? What formulas do you use? It would be much easier to answer your question, if you told me exactly what you are doing. However, I think your problem is that you must learn to think relativly. /Patrik.
ressler@CS.Cornell.EDU (Gene Ressler) (04/09/91)
In article <41021@cup.portal.com> Bobster@cup.portal.com (Robert Jules Shaughnessy) writes: > > I also have had this problem. I think you should fallow what is said >in reply #2 and then be sure to NOT DRAW ALL LINES/POINTS witha NEGATIVE >Z coordinate. This will cause objects to disapeare when they go behind the >view screen (Coordinate Origin). I think this may be what you want since if >you do not do this, you do get that local rotation effect. Also there are >other ways of doing this. (If your using lines) You could draw the lines with >only one negative z coordinate by substituting the -z for 0. This would let >yyou view an object more clearly as you pass through them. To beat a dead horse ;-), what is really wanted (at least in concept) is to _clip_ to the perspective view volume in _3D_, then draw. (There is no `behind the observer' for orthogonal projections.) This volume is the (infinite) double pyramid formed by projecting lines through the observer point to the corners of the viewport (think `screen'). Without 3D clipping, objects in the `other' lobe of the pyramid from the viewport are projected upsidedown --- not surprising as in this case you've effectively modeled a pinhole camera. Check out the 3D version of the Liang Barsky clipping algorithm. It nicely truncates 3d lines to just the viewport lobe of the pyramid. Hence when you fly through objects, they swell to the size of the screen, then are cleanly clipped as you get too close for the whole thing to fit, then disappear after you've gone through. Or you can have a 3d database with both an airplane and the ground and get a correct simulated image sitting in the seat looking out the window. If you just skip lines with a point of negative Z coord, chunks of the airplane will be missing. If you need to clip _polygons_ instead of just lines (say for hidden surface removal), then look at the Sutherland- Hodgeman algorithm. L/B is presented in Hearn and Baker, Computer Graphics (though I can't recall if they do the 3d version --- you may have to look up Liang's paper in the references; it's very clear and easy to program from. S/H is in Foley and Van Dam, Fundamentals of interactive computer graphics (and many others). They do a chapter on `the graphics pipeline' that is _very_ worthwhile study if you're doing 3D imaging. These guys virtually invented computer flight simulations; they know what they're talking about. Having said this, I gladly admit that programs like MS Flight simulator play all kinds of games to get around the expensive (read floating point) computation of the above algorithms. But you can't understand the games until you've got the rules. Happy landings, Gene
ttobler@unislc.uucp (Trent Tobler) (04/09/91)
From article <1991Apr05.224711.12750@lynx.CS.ORST.EDU>, by murrayk@prism.CS.ORST.EDU: > > [Article on problem with 3D rotations] Perhaps, if instead of thinking in terms of rotation, you thought in terms of A) tranformation, or B) point of view. Both of these are two methods I know of to do "3 dimension rotation". In the first method, primitive matricies are multiplied together to product a composite 'transformation' matrix. Then to transform your coordinates, you would multiply a vector of your point with the matrix. An example of a matrix transform is... / 1 0 0 0 \ / 1 0 0 0 \ | 0 cos(t) sin(t) 0 | X | 0 1 0 0 | = Tranformation | 0 -sin(t) cos(t) 0 | | 0 0 1 0 | Matrix \ 0 0 0 1 / \ -2 1 3 1 / rotate by t radians move origin to ( 2, -1, -3) in the y-z plane Then to get the new location of point [x y z], do / \ [x y z 1] X | Transformation | = [x' y' z' 1] | Matrix | \ / and then plot perhaps (x', y') to the screen. I suggest you read some books on matricies (linear algebra), and consult more books on three-dimensional graphics. The other method involves using a 'camera' or an 'eye' similar to that used by ray tracers. This involves taking a point in the space, E = [ex ey ez] as the camera, having a window (I usually specify this as two vectors X, and Y, and W - all vectors). Then to convert a point from three dimensions to two dimensions, a line is constructed between the camera and the point, P = [px py pz], finding the intersection on the window, ie. solve t(P - E) + E = x'X + y'Y + W for (x', y'), and then simply use the x' and y' as the coordinates on your window. (note: t is also solved for to determine if the point is virtual, ie,. behind the camera) If you plan on using this method, you should read on vector algebra (which should also be covered in a book on linear algebra), and look into books on ray-tracing, as well as general three dimensional graphic books. The advantages of each method are: Transformations are simple to calculate, and can do more than just 'what we would really see if this existed' type pictures. It can rotate, shift, change size, and skew objects in three dimensions. Point of view leads to an easy way of generating relistic pictures, and perspective is handled automatically. It can move around and throught the objects with ease. Problems with the methods are: Transformations are quite complex, and determining a specific reference can sometime be very difficult. It is more difficult to do the things that point of view handles easily. Also, calculating the transformation matrix can be very computationally intense. Point of view has problems with virtual points when drawing lines from virtual point to visible point (virtual points are those that are behind the camera). It also lacks the ease that transformations have when doing skewed and distorted images. My suggestion: explore both of these methods. It is possible to combine the two to get more power (at cost of computation) at changing your image. -- Trent Tobler - ttobler@csulx.weber.edu
nyet@nntp-server.caltech.edu (n liu) (04/09/91)
ressler@CS.Cornell.EDU (Gene Ressler) writes: >easy to program from. S/H is in Foley and Van Dam, Fundamentals >of interactive computer graphics (and many others). They do a chapter >on `the graphics pipeline' that is _very_ worthwhile study if you're doing >3D imaging. These guys virtually invented computer flight simulations; they >know what they're talking about. >Having said this, I gladly admit that programs like MS Flight simulator >play all kinds of games to get around the expensive (read floating point) >computation of the above algorithms. But you can't understand the games >until you've got the rules. I actually have one of those pipelines described in Foley & Van Dam that does pretty much any wireframe 3D modeling I could ever want, but it's a bit slow for real animation... unless you have a quick 386 with fpu. So, what i want to know is, where is a good place to start to learn those integer math tricks MS et al use? Also, if anybody is interested in the pipeline, i can mail it to them - its kinda convoluted and there's no documentation or comments (hey, i'm sorry - what do i look like; a CS major?) but if you're willing to sit down and untangle it, it might be useful. Two "front ends" are available - one is an interactive line-driven renderer which will also read in data (got lots of sample stuff for it); cli.c the other is a little animation front end that bounces and rotates red/blue 3d stuff on screen; danime.c again, docs are sparse, so use at your own risk! The syntax for the cli is pretty much what James Blinn wrote about in some random Computer Graphics treatises.. i have photocopies of those lying around somewhere.
xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (04/10/91)
If you want to see 3D display math in all its most gruesome generality, find Puk, Richard F., "General Clipping on an Oblique Viewing Frustrum", SIGGRAPH '77 Proceedings, Computer Graphics Volume 11, Number 2, Summer 1977, pages 229 - 235. I implemented this into firmware in a graphics display workstation for an employer in 1981, along with the general 4x4 homogeneous transformation code ably covered in, e.g., the recently referenced Foley & van Dam 2nd Edition. The published math, I remember, had one rather obvious bug when converted to software; it assumes infinite precision arithmetic, and stops a loop based on equality between two real values computed from different inputs. This is nonsense with limited precision arithmetic, and I stopped the same loop with an ugly but fast set of flags to assure I only clipped a line once at each clipping plane. There have been several quite good responses to the original posted request for help, but I feel that a couple of things haven't been emphasized enough, so let me restate one point, and add a bit of information of my own from my experience doing the above coding. 1) The complaint was that the rotations seemed absolute to the screen, rather than relative to the object. That's correct; the homogeneous rotation transform rotates about _the origin of the coordinate system_, not about your modeled object's "design "axes. As posted, you need logically to a) move the object to be centered with _its_ "design origin" at the coordinate systems' origin, b) do the desired rotation, and c) move the object's design origin back to its previous location in the scene. I said logically, because it is normally _much_ faster to take the three 4x4 matrices needed to accomplish these three operations, multiply them together as several posters have mentioned, and use the single product matrix to multiply times each point in the object's point list to do the transformation "all at once". 2) Another possible source of "this doesn't look right" when doing a screen rotation is to neglect the screen pixel shapes, or "aspect ratio"; if the pixels are 4/3rds as tall as they are wide, an object when rotated will appear to change shape with various orientations if the drawing code treats the pixels as grid coordinates on a grid equal in x and y dimensions. 3) Doing the "move, rotate, move back" transformations of 1) repeatedly and storing only the new coordinates will eventually, if you are doing real time rotation or at least lots of rotations of the same object, "destroy" the object by the effects of accumulated round off errors moving the points with respect to one another. You want instead to keep an original copy of the object description, and accumulate the rotations about each "object design" axis, scaling along each "object design" axis, and translation along each scene coordinate axis, and use these to build the transformation matrices fresh before each use. This way small errors in the accumulated values may still occur, but the created transformation matrix will transform the original data without inappropriate moves of the object's points with respect to one another. 4) The _easy_ way to do smooth rotations through a series of positions is to create transformation matrix for the original and final position, do a linear interpolation between individual matrix elements for each rotation step to be displayed, and use the interpolated matrix to do the intermediate transformation. Do _not_ take the delta matrix for one frame and repeatedly apply it; the same accumulated roundoff will get you. When using this technique, do a maximum rotation in one set of interpolations of 90 degrees about any axis; this assures that you don't accidently rotate the object backwards to your intended direction. I really don't know if the interpolation is mathematically sound, but it looks right, which is what counted for me. I suspect, since a sine curve is being interpolated by a straight line, that the rotation speed is not really constant, but the eye doesn't pick up on this kind of a problem, and the start and end positions are correct. The less the maximum rotation you allow for endpoint matrices between which you interpolate, the better the straight line interpolates the sine curve, of course, and the less the problem would show, but the extra math can hurt. Of course, if you're doing sines and cosines by table lookup, either interpolating or doing each frame's transformation matrix separately works out about the same. Kent, the man from xanth. <xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>
hartlemp@mentor.cc.purdue.edu (Michael P Hartley) (04/12/91)
In article <1991Apr8.181450.15309@cs.cornell.edu>, ressler@CS.Cornell.EDU (Gene Ressler) writes: > In article <41021@cup.portal.com> Bobster@cup.portal.com (Robert Jules Shaughnessy) writes: > > > > I also have had this problem. I think you should fallow what is said ect... > >yyou view an object more clearly as you pass through them. > > To beat a dead horse ;-), what is really wanted (at least in concept) is to > _clip_ to the perspective view volume in _3D_, then draw. (There is > no `behind the observer' for orthogonal projections.) This volume is the > (infinite) double pyramid formed by projecting lines through > the observer point to the corners of the viewport (think `screen'). ect... > Check out the 3D version of the Liang Barsky clipping algorithm. > It nicely truncates 3d lines to just the viewport lobe > of the pyramid. Hence when you fly through objects, they > > Happy landings, Gene Another way to do it is to transform the perspective (ie pyramid) into a parallel orthogonal canonical space.. clipping is extremely easy then. Check in Foley "Computer Graphics: Principles and Practice" chapters 5 and 6. Every thing you always wanted to know about 3D projections onto a 2D view-reference- plane. **************************************************************************** * \ | / "A 40 kW Full-Spec EMR in every satellite * * \ | / by the year 1995!" * * ---*-----------------------------==============>>>>>>>>>>>>||||||||| * * / | \ Michael Hartley (Yes, I did melt that) * * / | \ Purdue University * * hartley@maxwell.physics.purdue.edu hartlemp@mentor.cc.purdue.edu * * hartley@bard7.cs.purdue.edu me@my.self.and.I * ****************************************************************************