leo@philmds.UUCP (Leo de Wit) (09/20/88)
Posting-number: Volume 4, Issue 85 Submitted-by: "Leo de Wit" <leo@philmds.UUCP> Archive-name: 3demo/Part04 [Leo de Wit: HELP!!! Part 2 vanished into the cracks somewhere, and I didn't catch it. Please re-send ASAP. ++bsa] : This is a shar archive. Extract with sh, not csh. : This archive ends with exit, so do not worry about trailing junk. echo 'Extracting matricks.doc' sed 's/^X//' > matricks.doc << '+ END-OF-FILE matricks.doc' X X Documentation for the graphic functions. X ---------------------------------------- X X sources and doc by L.J.M. de Wit X X OBJECTIVE X X The purpose was to supply a number of useful graphic functions that X can be used in a modest scale for animation, 3D motion, demo's. Another X purpose was to poke up some discussion conceirning graphic functions, X representations, etc. I'm only in a minor way involved with graphics in X my job, so I'm open for any other ideas. The functions offered have not X the least pretention to be exhaustive, although it would be nice to X enlarge and enrich the capabilities in future releases. Whoever has ideas, X remarks, bugs found in the package, questions about the source or how to X use it, is invited to send them to me; any help is welcome but also gladly X offered. X X X COPYRIGHT AND THE LIKE X X The source can be used freely for non-commercial purposes; X if you redistribute the source keep my copyright notice in; that's a small X fee for the effort I've put into it. If you plan to make changes to the X source and distribute I would like to know; this to prevent duplication of X effort, and existance of different branches; perhaps redistribution could X go via me (maybe I'm already too optimistic about others willing to work X on some part of the code 8-). Also anyone planning to use (part of) it in X a commercial product should contact me; this be said to keep everyone X interested! 8-). X X X TARGET MACHINES, LANGUAGE USED X X In the present form the demo program runs on Atari STs (1 Meg required). X The amount of memory is merely required to run the demo that stores a X series of compressed images; this is the only part that really requires X memory. It should not be hard to port the code to various machines, notably X the Mac, the Amiga, the IBM PC with graphics card, a Sun, etc. X The language used is C; a small part of the code is in 68000 assembler. X Since this code also has a line drawing routine (for bit mapped display) X it can even be used on systems with a very limited or no graphics library. X X X BREAK UP OF SOURCES X X Currently the following source modules exist: X X matricks.h: header file for extern declarations and the like. X 3demo.c: contains main and all demo functions X mat.c: operations on matrices X object.c: operations on objects: items and instances X gemfuncs.c: O.S. dependant part of graphic functions: opening a work- X station, swapping screen memory etc. X mxops.asm: like mat.c but these are assembler functions. X drawlin.asm: function to draw a line. X X The last 3 named are the ones most likely to cause problems when porting. X If your system doesn't have GEM, gemfuncs.c will have to be rewritten, X but this is no big deal; if your system uses an other processor than a X 68000 the assembler functions will have to be re-created; also if the X layout of your bitmap display is different from (any of the) Atari ST, X the drawlin.asm needs a thorough scan. X X X IDEAS ABOUT REPRESENTATIONS ETC. X X In order to give you a better understanding of the source I'll explain X some of the ideas used in the code and why some choices were made. X 1) Use of matrices for all motions (translation, rotation and any X combination of these). An object in space can be represented by a set X of coordinates for each point; if the object consists of a set of lines X it suffices to store the coordinates of the end points and the way the X points are connected (the polygons). The coordinates of an object are X stored per row for each point in a 2D array (the height equals the X number of points registrated, the width the number of coordinates: 4). X A motion of the object can now be computed by multiplying the (npoints x 4) X coordinate array with the (4 x 4) transformation array, resulting in a X new (npoints x 4) array, representing the new coordinates. Note that in X case a combination of transformations is applied to the object (e.g. X a translation followed by a rotation) it is cheaper (in terms of # of X multiplications) to first multiply the (4 x 4) transformation matrices X (resulting in a new 4 x 4 matrix) and then multiply the coordinate matrix X with this one than to multiply the coordinate matrix with each X transformation matrix separately. This is also one of the reasons that X using matrix calculus is much cleaner and clearer than using goniometric X formulas; you do not get lost in long formulas and you can concentrate X on things that really matter, and the speed gain is vast when you're X handling several points / several transformations at a time. X 2) Use of 3D projective coordinates to represent a point in 3D space. X Those interested in but not familiar with these coordinates are advised X to read an (introductory) book about Projective Geometry; for those that X are only not familiar with it (and thus not interested 8-), it should X suffice to say that a point's X coordinates may all be multiplied with a constant, so for instance X (1, 2, 5, 7) is the same point as (3, 6, 15, 21) and that the (normal) X Carthesian coordinate system can be embedded in projective space as X follows: if (X,Y,Z) is a point in 3D Carthesian it corresponds with X (X,Y,Z,1) in 3D projective space (note: 4 coordinates). Of course X you could choose (2.3X,2.3Y,2.3Z,2.3) also or any constant you like. X The two main advantages of using projective (or homogeneous) coordinates X that I can see are: a) all motions of a rigid body in space can be X represented by a matrix (or series of) multiplication(s), or, put X differently, each transformation can be represented by a matrix. X b) since homogeneous coordinates are used, the elements of the matrix X may be scaled with a constant factor. This is an important issue in X terms of speed, since it allows the use of integers throughout the code X (many architectures deal faster with integer calculations than float X and double calculations); yes, by using correctly chosen scaling factors X (not too small to retain precision, no too big to prevent overflow) X even shorts are usable (16 bits shorts that is). The 68000 handles X word (16 bit) multiplications as one instruction, resulting in fast X performed matrix multiplications. The result matrix is of course a X matrix with 32-bit elements, but these are scaled afterwards to fit again X in a short. In fact, the scaling chosen is such that multiplying these X shorts in pairs and adding 4 such pairs does not overflow a signed long. X X X ABOUT OBJECTS X X This being said and understood the notion of the objects used should be X easy now. Two types of objects are of special interest: X The item, in fact a pointer to a struct, defined by: X X typedef struct itstruct { /* item definition: ptr to this struct */ X int count; /* # of points in this item */ X polygon next; /* pointer to polygon list */ X WORD r_data[1][4]; /* homogene coordinates of first point; */ X } *item; /* the rest follows hereafter */ X X Note that only one row of the coordinate matrix is declared; this is to X allow for arbitrary sized arrays without having to resort to pointers X (of course the only reasonable usage must be by dynamic allocation of the X actual struct). X The 'polygon next' member is a pointer to a linked list of arrays of X indices, as follows: X X typedef struct polystruct {/* polygon def: ptr to this struct */ X int count; /* # of points in this polygon */ X struct polystruct *next;/* ptr to next polygon */ X WORD coord[1]; /* index of first point */ X } *polygon; /* the rest follows hereafter */ X X Like with the item def. only one index is declared; in an actual case many X will follow in consecutive memory. Each polygon is a series of connected X lines, the indices being the numbers of the points in the coordinate array. X Thus an item can have several series of connected lines. X X An item is in fact a very static object, it can be seen as an abstraction. X If we want to use it, we need an other type of object, i.e. the instance. X An instance is also a pointer to a struct, defined by: X X typedef struct instruct { /* instance def: ptr to this struct */ X item in_item; /* item of which this is an instance */ X WORD trans[4][4]; /* 4H that places it */ X WORD i_data[1][2]; /* screen coordinates of first point */ X } *instance; /* the rest follows hereafter */ X X The 'item' member is the pointer to the corresponding item structure X (containing a coordinate array and a list of polygons). X The 'trans' member is the transformation matrix that puts the item in 3D X space (so its contents varies because it is multiplied each time by X whatever transformations act on the object). X To be able to do the calculation of projected points and actual drawing X of the computed lines in different places, there is also a storage area X in the instance structure that contains for each point the actual screen X coordinates (pixel coordinates). So it's written by the projection functions X and read by the draw functions. Again there's room for one point only, X but dynamic allocation 'over the edge of the struct' allows for an X arbitrary number of points. Note that the definition of C says that X consecutive members of the struct occupy consecutive places in memory, so X that we may safely use 'the other end' of the struct. X X X TERMINOLOGY USED X X To keep things small and simple the following abbreviations will be used: X 4H: 4 x 4 homogeneous transformation (matrix). Unless stated otherwise, X this will be represented in the machine by a: short [4][4], where X short is a 16 bit wide integer. X I, O, IO: in, out, inout - for parameters. X X LIST OF FUNCTIONS AND BRIEF DISCUSSION X X Now follows a list of the functions offered and a tiny description of X them; consult the source if you want to go into detail, you will find X this text more or less also there. The functions from the 3demo.c module X are not listed here since they serve only a demonstration purpose and X are not suitable for general use. X X From mat.c: X X - note that, unless stated otherwise, memory for matrices etc. must X already exist, must be either dynamically or statically be allocated. X X o void matapply(mat,func,v,fac) X WORD *mat; IO the 4H to be transformed (e.g. ins->trans). X WORD *(*func)(); I the kind of transformation, i.e. a function ptr. X func can currently only be mattlate, matrotate, X or matreflect. X double *v; I a 3D vector to quantisize the transformation. X double fac; I a number with which v is multiplied. X X Applies a transformation to a 4H. This can be a X translation, rotation or reflection. Matapply can typically be used X to create 4H's beforehand that represent a small motion (small X step in x-, y-, z - direction or turn around x-, y-, z - axis). X In that case mat is taken to be an 4H identity matrix, v one of the X unity vectors ((1,0,0), (0,1,0), (0,0,1)) and fac is a (small) number. X X o void matcompose(a,b) X WORD *a; IO X WORD *b; I X X The result of the (homogeneous) multiplication of a and b is placed X into a. This function is implemented as a macro. X It can be used for instance to update an instance coordinate X transformation (take a to be ins->trans) when an other transformation X affects it (the b matrix). X X o WORD *matident(n,a) X int n; I X WORD *a; O X X Create a nxn identity matrix and return the pointer to it. X X o WORD *matreflect(v,a) X double *v; I a quantisizing 3D vector: the normal vector X WORD *a; O the 4H. X X Create a 4H reflection matrix. Used by matapply(). X X o WORD *matrotate(v,a) X double *v; I a quantisizing 3D vector: the rotation axis X WORD *a; O the 4H. X X Create a 4H rotation matrix. X X o WORD *mattlate(v,a) X double *v; I a quantisizing 3D vector: the translation step X WORD *a; O the 4H. X X Create a 4H translation matrix. X X o uchar *matscr_to_str(b_and_w) X bool b_and_w; I Use-only-black-and-white flag X X Compress screen into unsigned char array and return pointer to it. X If the flag is TRUE, the screen is handled as if only one colour was X present (even if it is multi-colour); this allows for some factors X extra compaction. The memory needed for the array is dynamically X allocated. X The screen information is stored in the following way: X Assume for simplicity's sake the screen consists of 200 lines, each X line being 160 bytes wide, so 160 (byte) columns wide (the peculiarities X of the different resolution and colours will be handled further on). X The first byte contains the number of nonempty columns that were found. X Then follows for each nonempty column: X the column number (0-159) X the number of line sets (0-80). A line set is a series of consecutive X nonzero bytes in one column. X Then follows for each line set: X the first line of the set (0-199). X the number of lines (0-199). X the actual values (each being 0-255) X until last line set in column X until last nonempty column on screen. X As for the different screen modes: X High res on the Atari has 400 lines, 80 byte columns. To be able X to deal with the lines from 256 up (the line no. must fit in a byte) X the lines from 200-399 are marked by using column numbers 160-239 X (instead of 0-79) and line numbers 0-199 (instead of 200-399). X Medium and low res have both 200 lines. Medium has 80 columns, X 2 colour bit planes, whereas low has 40 columns, 4 colour bit planes. X Because the colour info is stored as: word0 of plane0, word0 of X plane1, etc. the simple solution is to view an entire line as simply X 160 bytes (of which there are overlapping pairs for medium and X overlapping quartets for low res.), so use columns 0-159. X The b_and_w flag simply says to ignore each odd word in medium res. X and each second, third and fourth word of four consecutive words in X low res. In this way, if the image was already black, a compaction X of 2 to 4 times above the existing compaction is reached. X X o void matstr_to_scr(s,b_and_w) X register uchar *s; I Array of compressed data X bool b_and_w; I Handle-as-black-and-white-only flag X X Display compressed image. s should have been created by matscr_to_str(). X X o void error(func) X char *func; I name of function in which error occured X X Simple error handling function. Display a message and stop program. X X o double maxfactor(arr,cnt) X double *arr; I the array X int cnt; I # elements in array X X Find maximal multiplication factor for an array of doubles so that each X array element after multiplication with this factor can be cast to X short without truncation. X X o double mycos(a) X double a; I X X Fast cosine function by table lookup. Each value that has been X calculated once can be retrieved by table lookup. X X o double mysin(a) X double a; I X X As mycos() for sine function. X X From mxops.asm: X X o void mxhmul(a,b,c,p,q,r) * X short *a, I points to array of p x q shorts X *b, I points to array of q x r shorts X *c, O points to array of p x r shorts X p, q, r; X X Matrix multiplication for homogeneous coordinate matrices X c points to the result of the multiplication of the matrices X pointed to by a and b. It is scaled to fit in shorts. X Since a temporary array is used to store intermediate 32 bit X results c may be one of a, b without a problem. X X o short *matcopy(a,b,n) X short *a; I X short *b; O X short n; I X X Copy over n shorts from the array pointed to by a to that pointed X to by b. X X o void mxproj(inarr,outarr,pcount,eye_z,scal_x,scal_y) X short *inarr, I X *outarr; O X short pcount; I X short eye_z, I distance of observer to screen X scal_x, I scaling along x axis of screen X scal_y; I scaling along y axis of screen X X Projection of inarr onto the instance's screen coordinates outarr. X inarr points to an pcount x 4 array of shorts representing the hom. X coordinates of the pcount points of the instance. X outarr points to a pcount x 2 array of shorts representing the screen X coordinates to be calculated for each point (this array is part of the X instance). X eye_z, scal_x and scal_y are parameters that determine the projection. X X From gemfuncs.c: X X o void gem_init() X X opens a virtual workstation and allocates extra screen memory for X smooth drawing. X X o void gem_exit() X X closes a virtual workstation, restores screen location and exits. X The allocated memory for a screen is automatically returned to the X system. X X o void swapscreen() X X switches the logical and physical screens. All drawing functions X (including displaying text) takes place on the logical screen, while X the physical screen is displayed. When the drawing is finished, the X pointers to the two screen areas are swapped. The VBL (vertical blank X interrupt routine) checks whether the physical screen pointer has X changed and if so, tells it the hardware. By altering the physical X screen location just before the screen is displayed (the beam is aimed X again at the start of the display it is ensured that movement is smooth X (no screen memory updating while is it being read). X X From drawlin.asm: X X o void drawlin(x1,xy1,x2,y2) X WORD x1,y1,x2,y2; I X X Draw a line between points (x1,y1) and (x2,y2) in high, medium or low X resolution. No attempt has been made to handle colours, different line X styles/widths, clipping, although this should be simple - maybe X something for a next release. X The method used for calculating the pixel coordinates of the line is X Bresenham's algorithm, of which I will give an explanation. Also some X details of how it is speeded up further wil be given. X The algorithm consists of taking always a step in the direction of the X axis of greatest movement, and, depending on an accumulating error term X also in the direction of smallest movement. A derivation for the simple X case that the start point is (0,0) and the end point (a,b) with a >= b X and a and b both >= 0: X Equation of the line: X X a . y - b . x = 0 (1) X X Now take (x(n), y(n)) to be the nth point of the line. Because x(n) and X y(n) are integers, they will generally not satisfy (1). In fact an error X term d(n) exists, generally not 0: X X a . y(n) - b . x(n) = d(n) (2) X X Since steps are to be taken in x direction, the x(n) is 'correct'; X the y(n) may be off at most 0.5, so X X - 0.5a <= d(n) < 0.5a. (3) X X It is easier to compare against 0, so instead of d(n) we use e(n) with X X e(n) = d(n) + 0.5a. (4) X X and X X 0 <= e(n) < a (5) X X By subtracting (2) from (2) with n+1 instead of n we get: X X a . (y(n+1) - y(n)) - b . (x(n+1) - x(n)) = d(n+1) - d(n) X X Since x(n+1) - x(n) == 1, and d(n+1) - d(n) == e(n+1) - e(n): X X a . (y(n+1) - y(n)) - b = e(n+1) - e(n), or X X e(n+1) = e(n) - b + a . (y(n+1) - y(n)) (6) X X Now it's easy, since the e(n+1) must be >= 0 (5), and y(n+1) - y(n) X is either 1 or 0: X subtract b from e(n); if result < 0 increment y and add a to error term. X X In a C program: X X short x,y,a,b,e; X X e = a >> 1; /* d(0) == 0, so e(0) == 0.5a */ X y = 0; X X for (x = 0; x <= a; x++) { X plot(x,y); X if ((e -= b ) < 0) { X y++; X e += a; X } X } X X The 'real' thing must also handle the other cases: b > a, a < 0 or X b < 0: X First end and starting point are swapped if x2 < x1, so that always X x2 >= x1; this implies a > 0. The increment of y is 1 if b >= 0, X -1 if b < 0 and furthermore b is then set to its absolute value. X The cases a >= b and b > a are dealt with separately. X Because the machine addresses bytes, not bits, and thus in order to X avoid excessive address calculations, the pixel (x,y) is represented X by a word address and a bit in that word. Stepping in x direction is X done by rotating the word by 1, incrementing/decrementing the address X if a carry is generated. Stepping in y direction is done by X adding/subtracting the number_of_bytes_per_line to the address X (effectively stepping a line). X The new point is OR-ed into the screen each time; in fact, this OR-ing X is done into a data register for speed; the actual storing into the X screen is done when the address is about to change. In the case that X b > a, the y-step is always taken, so the OR-ing into the data reg. is X NOT done there. X An even faster version of drawlin is being planned, but implementing X it would postpone the current distribution. Next release! X X From object.c: X X o item matcrit(n,d,o) X int n; I the point count X double d[][3]; I the n*3 coordinates of the points X short *o; I an array of indexes for the points; each -1 value X ends a joined set of points, an extra -1 ends the X array. X X Create an item by giving its point count, point coordinates and order. X The function allocates memory for the item, in this it stores the point X count, the points homogeneous 4D coordinates and a polygon list pointer. X For each polygon also memory is allocated to contain a count and an X array of indices. X X o void matfrit(ip) X item ip; I item to be freed X X Frees all memory belonging to the item that was allocated by matcrit. X X o instance matcrins(it,lia,tv) X item it; I the item it's refering to. X double lia[3][3]; I the 3x3 transformation array. X double tv[3]; I the translation vector. X X Create an instance of the item by giving the item and a transformation X matrix to put it into space. Note that the transformation array is an X array of 3x3 doubles (non-homogeneous coordinates), and also the X translation vector is in non-homogeneous coordinates. The memory X allocated will contain a pointer to the item, a 4H to place the item X in space, and an array to hold the screen coordinates of each point of X the instance. X X o void matfrins(ins) X instance ins; I instance to be freed X X Frees all memory belonging to the instance that was allocated by X matcrins. X X o WORD *matseteye(lia,tv,dist,sx,sy) X double lia[3][3]; I the transformation to orientate the screen X double tv[3]; I the vector to place the screen X double dist; I the distance of the eye from the proj. screen X double sx,sy; I scaling for X-, resp. Y-axis. X X Fix the eye and projection screen positions and orientations and scaling. X This generally has to be done once, unless the eye or proj. screen are X moving. X X o void matproject(ins) X register instance ins; I the instance to be projected. X X Project an instance, i.e. calculate the screen coordinates it will need X to draw it. This will fill the array of screen coordinates within the X instance with values that depend on the current contents of the X instance's 4H transformation and the observer's position (set by X matseteye). The critical part is handled by mxproj for speed reasons. X X o void matdraw(ins,mode) X instance ins; I the instance to be drawn. X int mode; I the mode of drawing (OR,XOR,ERASE etc.) X X Draw an instance, using VDI. Each polygon in the instance's item's X polygon list is drawn, using the coordinates in the instances screen X coordinates array. X X o void matfdraw(ins,mode) X instance ins; I the instance to be drawn. X int mode; I the mode of drawing (OR,XOR,ERASE etc.) X X Draw an instance, using drawlin. The mode parameter is currently ignored. X See also matdraw. This method is faster; an even faster method for X drawing lines than drawlin is planned. X X o void insstore(ins,a,n) stores X instance ins; I into X WORD *a; O as entry number X int n; I ; i.e. there are n WORDs in a preceding. X X Store the calculated screenpoints of an instance. X The screen coordinates are stored in a as a[n], a[n+1] etc. X In this way line images can be stored with minimum overhead. The only X processing that needs to be done afterwards is calling insload and X matfdraw (or matdraw). Before insstore is called the coordinate array X has to be calculated, preferably with matproject. X X o void insload(ins,a,n) loads X instance ins; I from X WORD *a; I as entry number X int n; I ; i.e. there are n WORDs in a preceding. X X Recall the calculated screenpoints of an instance. See also insstore. X X o static WORD *matliatv(invers,lia,tv,rotra) X int invers; I Use inverse of lin. transf. X double lia[3][3], I Linear transform. to place it X tv[3]; I Translation vector to place it X WORD *rotra; O 4H result X X Apply linear transformation and translation. Note that this function is X static and can thus not be used as external function. Use matapply for X a function with comparable capabilities; the difference is that X matliatv can specify all kinds of linear transformations, and that it X puts the result in rotra, while matapply is restricted to translation, X rotation and reflection and applies the thus created 4H upon the output X 4H. X X o WORD *matseteye(lia,tv,dist,sx,sy) X double lia[3][3], I Linear transform. to place it X tv[3], I Translation vector to place it X dist, I Distance eye from screen X sx,sy; I Scaling x and y axis X X Set eye coordinates. Besides setting distance and scaling the function X returns a pointer to the (static) 4H observer matrix. + END-OF-FILE matricks.doc chmod 'u=rw,g=r,o=' 'matricks.doc' echo 'SENT: -rw-r----- 1 leo 27488 Aug 21 15:09 matricks.doc' echo -n 'RCVD: ' /bin/ls -l matricks.doc echo 'Extracting readme.doc' sed 's/^X//' > readme.doc << '+ END-OF-FILE readme.doc' X X X +--------------------------------------------------------------+ X | MATRICKS: 3D graphics package; sources, docs, binaries, demo | X +--------------------------------------------------------------+ X X The distributions are as follows: X X SOURCES: BINARIES: X X 3demo.c 3demo.prg X drawlin.asm 3dlib.bin X gemfuncs.c matricks.doc X makefile readme.doc X mat.c X matricks.doc X matricks.h X mxops.asm X object.c X readme.doc X X SOURCES are planned to go to comp.sources.misc because there's a general X interest for the stuff. X BINARIES are planned to go to comp.binaries.atari.st; they are too specific X to run on other hardware than Atari ST's. X X A few remarks conceirning the demo program and library: X X 1) Because clipping is not yet implemented, images can get distorted near X an edge. This is due to the projection function, that truncates all X coordinates that are too big to fit on the screen. Clipping will be X implemented in the next release; no truncation will be needed anymore. X 2) For high resolution monitors the first demo only uses part of the screen. X Since I don't own one, a friend had to tell me (thanks, Frans!). Because X I don't consider it too important, it isn't fixed yet (next release?). X 3) A remark about the library: all parameters of all functions are of size X 4; this is due to the Lattice parameter passing mechanism. This can cause X problems when using them from other compilers (e.g. when passing shorts). X Suggestions: explicit casts to long, or using an interface library, or X creating your own library using the sources (see the makefile). X X Enjoy! X X Leo. X X P.S.: For bug reports, problems, questions, suggestions, etc.: X X L.J.M. de Wit X Nachtegaallaan 7 X 5731XP Mierlo X Holland X X E-mail: ...!mcvax!philmds!leo X + END-OF-FILE readme.doc chmod 'u=rw,g=r,o=' 'readme.doc' echo 'SENT: -rw-r----- 1 leo 2021 Aug 21 14:50 readme.doc' echo -n 'RCVD: ' /bin/ls -l readme.doc exit 0