P.Kent 9 Pendean Burgess Hill West Sussex RH15 ODW. Write to me! I want some feedback! P.KENT spills the beans on 3D for ACC ===================================== NB Knowledge of the blitter - lines, filling, cookie cutting, and filling, though not necessary will be advantageous when reading this DOC! INTRO: The fundamental shape of any object we wish to represent, on screen, is expressed as x,y,z coordinates.The coordinate triplet corresponds to distances from an origin (at 0,0,0) from the x,y,z axes. Consequently, each triplet corresponds to a unique location within the 3d system. An object's world coordinates are simply its coordinates in this axis system. IE. The world coordinates represent the world that you are modelling. FUNDAMENTALS: There are 3 main stages in generating the object on screen, once we have our objects world coordinates: 1:World coords - True shape of object 2:View coords - The coordinates of the object after any rotation or translation. 3:Display coordinates - The screen coords representing the object, after the 3d coords have been projected(converted) into 2d. 4:Draw the object. (Sounds simple ?) For the majority of this article, I shall just be considering objects made out of surfaces, or 'planes'. Note that I don't mean planes as in the maths definition of an infinite surface! So for example a cube has 6 surfaces. These polygonal surfaces, made by connecting groups of the objects coordinates together, can be plugged together to form complex objects - a helicopter, mouse or whatever, A plane (surface) that can only be viewed by one side, and is currently hidden, is called a HIDDEN surface. Working out which planes are visible is one of the main jobs of any 3d routine - consequently various methods for simple objects that are relatively fast, and slower, more general ones have been developed. MANIPULATION: As already covered to display our object at the VIEW coordinates, we will usually have to translate(move) it and then rotate it to a various extent. The general formulas for transforming world to view to display coordinates are given below: ;Rotations: angles r1,r2,r3 ; coords x,y,z ; xa,ya,za temporary variables xa=cos(r1)*x-sin(r1)*z za=sin(r1)*x+cos(r1)*z x=cos(r2)*xa+sin(r2)*y ya=cos(r2)*y-sin(r2)*xa z=cos(r3)*za-sin(r3)*ya y=sin(r3)*za+cos(r3)*ya ;Translation: by mx,my,mz x=x+mx y=y+my z=z+mz ;Projection: screen distance d ; screen centre scx,scy sx=(d*x/z)+scx sy=(d*y/z)+scy Don't panic if you hate trig! Mark has already written up an explanation of the derivation of these formulas on a previous ACC disk... The first manipulation performed is rotation - taking into account the roll,pitch, and yaw of the object. R1 corresponds to rotating the object about a vertical axis,R2 to an axis running front-back, and R3 through a horizontal axis. The translation is fairly self-explanatory, consisting of just adding a fixed amount to each other the different coords. The projection formulae are derived from similar triangles, by assuming that a flat 2d screen has been placed between you and the object, at a distance d. The image can be calculated by considering two right angled triangles, one each for x & y coords. Not that if d is not set correctly the image of the object will appear distorted - it will either appear too flat and non '3d' or massively distorted. This is due to trying to display an abnormal amount of the object on screen - compare this with walking up to a building : if you are too close you would not see all of the building, hence to see all of the building (object) you would have to step back. IE The angular distortion on the screen is due to trying to display too much of it on screen given your distance form the object! Fortunately this value is not particularly critical - its quite OK to just fiddle with it until you get a view you agree with! OK. So now with some ingenuity we could put a series of points up on screen to represent our object, and maybe join them up with lines to form a WIRE-FRAME view of our object. Although the view would be a fair representation, it would not be particularly good at displaying complex objects with lots of points. Also at certain angles, your poor old brain would begin seeing strange things due to the lack of depth information in the image! One example of the is called the Necker-Cube effect, in which it is not possible to tell whether a wire-frame cube is poking out of the screen or poking into it.... HIDDEN SURFACES: Obviously we need to fill our object to create a solid appearance. To do this we need to ensure that when filling the object's planes we only end up displaying the correct surfaces of the object - we don't want to see the back of a cube when looking at the front of it... I shall now describe two methods for correctly displaying objects in filled 3d, that realistic for real time updates on the amiga: 1)Back-Face removal. (CONVEX VECTORS) This method will only work for convex objects. Before you ask, I'd better explain : a convex object is one where it is not possible for a surface to be partially obscured by another. Examples include polyhedra - cubes,tetrahedrons etc. , prisms, and also a good few wedge shaped spaceships... The definition of a convex object provides a starting point - we can just draw faces that are facing us, and ignore the rest, since by definition they must be completely hidden. It is possible to work out whether a flat plane is facing us by working out the normal vector to this plane, and seeing whether that has a positive or negative z component. A normal vector is simply a vector poking out of the plane perpendicular to its surface - for example a table leg could be said to be normal to the table it is supporting, since it is (hopefully!) perpendicular to the flat table-top. However there happens to be a better method. Consider the orientation of the points at the edge of the surface... Imagine numbering the corners of a disk in anticlockwise order, around its edge. Now turn the disk upside down, and look at the order of the numbers - they are now in clockwise order. We can use this change of order to decide which way the surface is pointing. Given three point numbers and coords, it is possible to derive their order: ;orient: p1,p2,p3 - points on surface (2D coords!) ; v1,v1 - Temporary 2d vectors for p1>p2 and p2>p3 v1.x=p2.x-p1.x v1.y=p2.y-p1.y v2.x=p3.x-p2.x v2.y=p3.y-p2.y orient=sign(v1.x*v2.y-v1.y*v2.x) ;orient is +/- 1 depending on orientation. ;2d vector cross product is faster than a 3d normal vector ;calculation due to fewer multiplies OK. So to draw our filled convex vector object, we transform its coords as described, and then (say) draw only clockwise polygons, using a list of points defined in our object. AS long as we ensure that all of the polygons have point numbers such that when the polygon is visible they are in clockwise order, and that the object is fully convex, we will have no problems. At this point I refer you all to the source v_convex.s which is a basic convex vector routine. There are quite a few comments in the source, so I won't document it further. 2)The Painter's Algorithm. (INCONVEX VECTORS) The (very unsubtle) name of this technique explains all. The idea is that a painter when painting begins at the back of his/her scene and gradually build up layers of paint, coming forwards until the last bit of paint represents the frontmost part of the scene. Hence, anything in front of anything else will be covered over, giving the correct image. This idea is easily applied to our 3d system so far. We filter out all of the hidden planes by their orientation (as above), and then draw them all in order of most negative z coordinate to those closest to 0.(Negative z coords are infront of the viewer, 0 is where the viewer is 'standing', and positive coords are behind the viewer). How can we do this in practice ? Well, when we consider a plane, having decided that is could be visible due to a correct orientation, we then find out how far into the scene is - its depth. There are various ways of doing this, though for reasons that I will explain later, we can just average out all of the plane's corner's z coords. We then put this value and a pointer to the definition of the plane in an array. We do this for every plane, then we sort the array into order of most negative average z to closest to 0. Then we simply step through the array, drawing planes in order as we go... BUT if you have looked at the convex source, you will notice that planes are just drawn directly over 'what has gone before' - this is OK in the convex case since plane will never overlap. :-) In the INCONVEX case however, planes can overlap (hence the painters algoritm & 'depth sort'). Getting around this is easy - we just draw our planes in a temporary buffer, and cookie cut them onto our viewing screen (suitably double buffered - of course!). I suggest a look at my second chunk of source, v_inconvex.s. This is a (VERY) simple inconvex routine, but even as it is, you can do some impressive stuff with it.... :-) I said earlier, that just taking the average of each plane's corner's z coord will generate good enough depths. The reason for this and not using, say, Pythagoras's theorem and working out x^2+y^2+z^2 (forget the root) and average that is simply that I dont think the effort is worth it. The painter's algorithm has one major drawback - it takes no account of the fact that a plane could extend over a considerable range of z values, so just representing it with an average value doesn't give a true picture of the situation. While this problem can be worked around, you should take care with large planes, by perhaps breaking them in two, or also taking minimum & maximum z values into account.... MULTIPLE OBJECTS: Not long ago in the demo scene, there was a bit fuss over being able to display lots of independant objects at once... hence the 'how many cubes' scenarios etc. etc. However, this is really NO BIG DEAL - just a bit of thinking, and only rearrangement of out existing code will allow it to handle multiple objects. What must be done is to make all of the objects positional, rotational (etc) information LOCAL to the object, so the vector- routine is just passed a pointer to some wacky structure in memory. Out depth sort code already saves a pointer to plane definitions so it doesn't really matter whether they are in any particular object... One tiny piece of code that has to be done, is to save some coord number offset or object pointer in with the pointer to the plane, so that are vector routine knows where to get coords from... :-) LINES/BOBS: ACC 21 had some vectorbob code on it, so if you look at that, you will be able to see that to implement bobs we just need to put them in with our planes, sort their z values all together, and hence draw our scene with the bobs at the correct depth. The bitmaps for the bobs can of course just be cookie cut onto the screen - could could probably even re-use parts of the plane cookie-cutter to do this.... Lines can just as easily be put in, by averaging their z coords (all 2 of them - don't let me catch you using a divide instruction for this!), and then entering it as a pointer to the line structure in the 'depth array', and proceeding in a similar fashion to the bob.... Oh, by the way it would probably help to put in some form of identification marker in these line/bob/plane definitions, so when stepping through the sorted depth list your code knows what it is dealing with. (Hope I didn't need to say that...) SHADING: OK. To display stippled colours we simply need to alternate the colour of adjacent pixels... To do this we can set up a mask in memory (01010101010 etc), and use this as our mask for puting down planes. What we can do is look at the two colours we are going to stipple, and the bit-pairs for each respective bit- plane. If both our set, this means that for this bit-plane we put down our plane as normal (cookie with our drawn plane acting as its own mask). Similarly is both are cleared, we do the same, wiping the area of screen where the plane is. If however they are different,say colour1 set colour2 unset, we cookie the plane BUT using our 010101 mask as our plane image SOURCE, and the plane as it own mask as normal. This lays down bits in the order 010101 where the plane is on screen. If the other possible situation occurs, with colour1 unset and colour2 set we need to use a mask starting 1010... to do this we just use the blitter in a different mode inverting our previous set up mask. :-) While quick(ish) this method does have the disadvantage of using up a tonne of memory for the mask, which has to be the same size as one bitplane, or at least the largest plane you are going to display. To avoid this, it is possible to disable the blitter channel through which the 1010 data is flowing, and simply put these alternating values in the BLTxDAT register. Two blits per bit-plane are now required however, since only every other line uses the same mask: LINE1: 10101010 \ LINE2: 01010101 | Only masks for lines 1,3,5.. are the same. LINE3: 10101010 / Lines 2,4,6.. are inverted. IE. Blit every other line of the plane, invert the BLTxDAT value, do the lines that you skipped on the first run... This involved using half the blit height for BLTSIZE, and adding to the blitter modulo values, so only every other line is touched. LIGHT SOURCING: Light sourcing is simply allocaing colours to planes to represent light reflecting off their surface. Two methods are frequently used: Z-Value only - This is simply drawing the plane in a brighter colour, the closest it is to you. Simple, but doesn't look at all conving... This can be done entirely from the planes average z-coord and either a look up table of colours/z values or by implementing the same thing in code only. (Say colour = z/128 or whatever, ensuring the colour generated is within range.) Lambert's cosine rule - This little rule states that the amount of light reflected by a surface follows the cosine of the angle between the normal to the surface, and the direction of the reflected ray. To avoid lots of explaining here, I'll just give the method: Calculate the normal to the surface. This is done by finding two vetors on the surface, and obtaining he normal via their cross-product. The two vectors can come from any three point on the plane - Hence a=p2-p1, b=p3-p1 where p1-3 are the xyz coords of three point on the plane,a-b are vectors. Normal is given by: a*b= (a2*b3-a3*b2,a3*b1-a1*b3,a1*b2-a2*b1) The normal vector must be reduced to a unit vector by dividing it by its modulus... Similarly the vector from the observer to the plane must be made a unit vector. The cosine of the angle between these two unit vectors is now simply the dot product of them - IE. a1*b1+a2*b2+a3*b3 This value between 0 & 1 (hence fixed point arithmetic here) gives the illumination factor of the surface, hence its colour by a similar method to the z-value only technique. :-) FLEXY VECTORS: Some demos recently have featured vectors flexing around, as if made from rubber, or jelly. To `wibble` our vectors in 3d is not as complex as it sounds - 'cos its a con. What we do is to wibble, as per a sin-scroller, our planes while in their temporary buffer, before being cookied to the screen. If we wibble the plane both left/right and up/down we get the required effect. Doing this quickly is the main problem, so practise 2/3 bitplane 1 pixel,1 frame, sin-scrollers first... Use both the 68000 and blitter to their full potential! STENCIL VECTORS: Almost forgot these. To stencil your planes we use a similar technique to that when stippling. In memory we must have a repetitve graphic - akin to floor tiles say. When we put our planes down, we simply use these graphics bitplanes instead of our plane in its temporary buffer as source data,and the temporary buffer for a mask (as usual). To avoid having massive chunks of raw graphic data in memory, we can just break down our cookie operation into smaller chunks, dealing with each separately. OPTIMISATION: If you examine my sample source carefully you will see a few key optimisations necessary for sane speeds. -Only wipe or blit part of the screen or temporary buffer that have data in them! Sounds obvious I know, but... To do this we examine a window consisting of minimum & maximum x/y coordinates so that we only copy/wipe the minimum number of words necessary. -Dont busy wait for the blitter,idling the processor. My example code is especially guilty of this principally so that it is easier to follow... The key point is that the cpu and blitter can function at the same time, so to put the cpu in a loop waiting for the blitter to be ready, when it could either be doing the same job itself or getting on with more point calculations is a waste. To get around this problem either your can simply arrange your code in a careful fashion, minimising 'wastage' or you can use a blitter queueing system of some kind. This system relies on the blitter generating interrupts when it is ready for another blit (ready). What can be done, is to set up an interrupt server that drives the blitter, while your code runs at virually full speed in the background. So, when your code needs to use the blitter it puts the necessary information in a queue for processing by the interrupt server. The server, when the blitter is next ready, just gets the data piecemeal off the queue, sets the blitter registers accordingly, and sets the blitter going. Next time the blitter is free, it does the same, and so on. A simpler example of not busy waiting is when wiping the screen. Instead of using just the blitter for all (say) 4 planes, you could set the blitter doing 2.5 of them, and let the 68000 wipe the remaining 1.5. If however, the cpu could be doing some heavy calculation instead, go for the latter. ETC. Use common sense to get the balance between the cpu and blitter about right. -Another example is that of extrusion. Extrusion is what happens to toothpaste when you squeeze it out of its tube. In terms of vectors it means that we have aconstant cross-section to an object. This also means that points at either end of the object are all connected by a common vector. To save calculating lots of points, just one end can be calculated, and also this common vector. Then to generate the coords at the other end we just add this vector the the coords of the points at the other end. -Sorting the depth list. A favourite target for victims of 'Computer Studies'... However,unless your scene gets really complex, much more time will be spent drawing your object(s) than you actually spend calculating them - consequently your efforts will have little effect comparatively unless you are busy waiting alot. Now I've had my little dig, I will say that if your depth list becomes large say >50 items, a sort routine other than a bubble sort with swap flag will probably be better. A binary sort is probably the best bet - providing you can spare the effort! CLIPPING: At some time, you will also need to put in code to only draw polygons in the screen : not off the top or anything! On ACC21 included a simple polygon clipper that could be adapted to suit. Also I have yet to mention that points with a positive z value are behind the viewer, and so polgons using them can appear distorted. To avoid this, the polygon must be clipped in 3d rather than 2d - various methods can be used, typically plane intersection, but I will leave the authors of the various books in the reference section to discuss... LANDSCAPES: Aka Midwinter. The key problem is principally that of the large volume of data... Got you going there for a minute! I am not about to launch into a full blooded discussion on landscape routines! Seriously though,if anyone reading this has followed what I have said so far, you should have no problems in putting together a landscape routine, comparable to Midwinter's. If you do get this far however and nedd help write to me, I will type out a list of suitable algorithms/optimisations etc. etc. ! I you get this far, please write to me anyway! REFERENCES: These books, though non-Amiga specific and definately not for machine coders contain info on most of what I've mentioned - all bar the Amiga specific effects (flexing etc): COMPUTER GRAPHICS - Steven Harrington. ISBN 0-07-100472-6 VERY through treatment of 2d/3d graphics techniques - lots of psuedo code. Not very good for beginners. HIGH-PERFORMANC CAD GRAPHICS IN C - Lee Adams. ISBN 0-8306-9359-9 Especially good if you have a PC - PC specific but a good soft introduction to 3d. HIGH-RELOUTION COMPUTER GRAPHICS USING PASCAL - Ian O. Angell & Gareth griffith. ISBN 0-333-44241-5 Comments as per Harrington. Also my local library tells me that a book on relatime 3d gfx for games on the Amiga is going to be published shortly, but I haven't any more details. :-( THATS ALL FOLKS! Thanks for your attention. In this little space I'll just say hi to all the AMOS users I know :-) [You know who you are!] and thanks Mark for doing ACC so brilliantly. (+All the other contributors). Please note that this DOC file is in no way a really thorough coverage of realtime 3d - there are lots of little tricks and application specific optimisations that I haven't mentioned for the sake of brevity. If you get into troubles, find my code can blow up your neighbours fridge or find any other bugs then write to me! (Get the hint: write to me! I want to communicate!) Thus concludes this doc file on 12/3/92. P.KENT ...one step closer...