home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Club Amiga de Montreal - CAM
/
CAM_CD_1.iso
/
files
/
374b.lha
/
3DLibrary_v1.5
/
3d.doc
< prev
next >
Wrap
Text File
|
1990-05-02
|
35KB
|
1,056 lines
3D Library
version 1.5 (release)
by Steven Ludtke
April 28, 1990
NOTICE
The 3d library and all associated software in this distribution
is Copyright 1990 by Steven J. Ludtke. You have permission to
use and/or modify this code for any purpose commercial or non-
commercial with two conditions : I must be given credit in any
distributed product's documentation, and if any part of this
package is used in any commercial product (even Shareware) one
free copy of said software must be sent to me at the following
address : Steven Ludtke, 406 Yale Cir., Glenwood Springs, CO
81601; all other royalties are waived. This Copyright notice
must accompany any distributions of any part of this package,
and in general, the package should be distributed intact, with
no modifications. This notice must not be removed from the 3d.c,
test.c, and cube.c source code in this release. Modified
versions of this package may not be distributed without my
consent. If the laws in your home state make any of the
conditions in the disclaimer invalid, permission to use and
distribute any part of this package in that state is withdrawn.
- 2 -
Release Notes
-------------
Version 1.0 : The initial release. It used a very primitive
sorting routine which proved to be insufficient for general
hidden surface removal. It also did perspective views
incorrectly, although it was not terribly obvious.
Version 1.5 (beta) : It fixes the above bugs and
adds an additional method for specifying viewing angles and
positions. The simple sorting routine for hidden surface
removal is still available, since it is much faster and
will work in some cases. The new routine is used by default.
Please mail bug reports to the address found at the end of the
doc file. I've been busy, so assembly language will have to
wait for the next version.
The supplied makefile, etc ... is for Manx 5.0. It should
work with Lattice, but I haven't tried it. It should also work
with Manx 3.6 with appropriate makefile mods. I didn't use
prototypes, but I did use precompiled include files. If you're
not using Manx 5.0, you'll have to tack include.c to the top
of 3d.c to get things to work.
Version 1.5 (release) : A number of problems with the new
surface sorting algorithm were found in beta testing. I fixed
most of these, but eventually decided to take a new approach. A
slightly improved version of the simple sorting routine is used
in the package. The complex routine has been removed. A friend
of mine wrote a 3d editor for files in the standard .3d file
format I use. I included (with his permission) executable for
this editor. It's pretty spiffy. A few new .3d files have also
been included. Oh yeah, the Z axis points in the right direction
now.
- 3 -
Introduction
---------------------
This library represents an attempt to provide the Amiga
community with a high speed, easy to use 3d display library for
C programmers. The library uses the transformation matrix
method, which is the fastest method I know of doing 3d
transformations while still providing relatively intuitive
rotations. Integer arithmetic is used for speed. Additionally,
the data is stored in a format that will make it easy to
optimize the code in assembly language. I wrote the code for
Aztec C (5.0), but I haven't converted anything to assembly
language yet, so the current version should work with Lattice as
well.
A number of beta-testers used Lattice with the library with
complete success. They said a few obvious changes were required,
but other than that, everything went fine. (Be SURE to use the
FFP library, not one of the double prec. libraries. There is a
factor of 2 speed difference involved.)
The library provides what I consider relatively high speed 3d
displays. It can rotate and draw roughly 500 lines/second (with
the FFP library). Once I've converted the rotation code to
optimized assembly, I expect the time required for the
calculation portion of the display to be reduced by at least a
factor of 2. Surface drawing is somewhat slower, depending on a
variety of factors. It is still reasonably fast.
Since a number of the parameters used in the library are
application specific, the 'library' is actually a C source file
that you include in your program. This is done primarily for
speed. If some of the parameters were variables rather than
#defines, the library would run significantly slower. The code
is relatively small, and it seems unlikely that more than one 3d
application would be active at one time, so C source seems to me
to be a reasonable way to go. If anyone has a better idea for
future versions, I'd love to hear it.
Included in this package are the following :
3d.c - The actual library code. This file is included in any
program you use the 3d routines in. It must appear in
the correct place in your program. Read the instr. or
look at one of the sample programs for more info.
include.c- used to precompile all standard includes. Otherwise
put at the beginning of 3d.c.
3d.doc - This file.
makefile - An Aztec 5.0 makefile for the two sample programs.
cube.c - A sample program that does double buffered animation
of a cube moving around. There is a reason it doesn't
move very smoothly. Look at the code before you think
that's the best the library can do.
test.c - A sample program that allows you to display 3d files
that are in a standard (non-IFF) format. Several
sample files are included. Look at the source for
instructions.
- 4 -
*.3d - Various files of 3d data (non-IFF) for use with test.c
maze.3d - This example contains a large 'floor' that won't sort
correctly with filled surfaces. It is an example of
what NOT to do.
earth.3d- This example contains non-planar surfaces. You'll note
that it won't work well with the complex sorting
routine (it does work with the simple one,though).
edit - A 3d editor written by a friend of mine. No source is
included with this release. He compiled it with
Lattice, and I think he might have used a double prec.
math library. This could slow it down a bit more than
is necessary.
edit.doc- Docs for the editor.
The two sample programs were written for Aztec C ver 5.0. A
few changes are necessary to use them with Lattice, but they
will work.
Hopefully most of the bugs have been worked out by now. If you
do find a bug (or have some questions), please let me know so I
can try to fix it.
I can be contacted via any of the following :
stevel@tybalt.caltech.edu (until June 90)
stevel@citiago.bitnet (until June 90)
gluon@theta.caltech.edu
72335,1537 (compuserve)
Steve Ludtke, 1-54 Caltech, Pasadena CA 91126 (until June 90)
Steve Ludtke, 406 Yale Cir, Glen. Spgs. CO 81601 (after that)
My current plans for the next version are as follows :
1. Convert much of the code to assembly for speed.
2. Perhaps I'll try to add some primitive shading routines
(simple lighting effects).
3. More complete x-specs support ???
4. A more intelligent surface sorting routine (faster).
5. Some object oriented routines to sit on top of the current
library.
6. Anything you suggest ...
Please talk to me. I like to get mail. Btw, this code should
be pretty easy to convert for use on other machines. All you
really need to change is the actual graphics function calls.
- 5 -
Here's the actual programming info. Info on structures follows
the function information. I tried to make it as easy to use as
possible.
Before your try to write your own code, you should probably
look at one of the examples. I'll summarize the basic steps in
using the library here :
Before the #include "3d.c" statement, you need to have several
#define statements in you program. If necessary you can replace
some of the defines with global variables, but you should avoid
this as it will slow the program down. The defines you need are
as follows :
#define D3VDIST 256 <- This is the distance from the
observer to the vanishing point. It
is only used with rotatev(), and
rotatevp(). Please read about it.
#define REZ 1024 <- Since the program uses integer
math, it must use several bits
for fractional calculations. 1024
would give 3 digits of accuracy. This
number needs to be a power of 2 for
upward compatibility. In general it
should be roughly as large as the
# of pixels in the display you use.
The larger it is, the smaller your
space for points is. REZ=1024 leaves
you with 20 bits for each of: x,y,z.
#define XCEN 250 <- This is the x coord (in the bitmap)
of the center (x=0) coordinate for 3d
displays.
#define YCEN 100 <- Same for y coord.
#define XHI 600 <- This is the highest x value in your
bitmap. Anything above this will be
clipped by the drawing routines.
#define YHI 180 <- Same for y.
#define XLO 0 <- Low x clipping value.
#define YLO 0 <- Low y clipping value.
#define ASPECT 23/10 <- This is the aspect ratio used to
insure a square coord system on the
screen. 23/10 is correct for 640X200
mode. Obviously 11/10 should be used
in 320X200 mode.
#include "3d.c"
Now, set up a VECTOR structure. You'll need to get free memory
for all 6 arrays it points to. Set up a LINES structure with
sufficient memory, too. Once, this is done, you can load your 3d
data into the structures.
Now set up a window or screen (something with a valid
RastPort), or two for double buffering, or four for double
- 6 -
buffered x-specs displays. If you intend to use d3surf(), call
Init3Ras() with all your RastPorts.
Now SetDrMd() for all RastPorts. If you don't have color data
in your LINES structure, also do a SetAPen() and a SetOPen()
(for surfaces) for all RastPorts.
Now you can actually display data. setxfm() or setxfm2() can
be used to set the viewpoint for the display. rotatev(),
rotate(), rotatep(), or rotatevp() can be used to actually
perform the rotations with or without perspective. d3surf() and
d3lines() can then be used to render the data in a RastPort.
When you're all done, don't forget to call Exit3d() if you
called Init3Ras(). DON'T call it if you only used d3lines().
Simple huh ??? : )
No real x-specs support code is provided in this release. You
still have to set up the code to drive the glasses yourself.
This library is ideal, however, for doing the actual drawing.
Just pick a point the person is looking at, then set up two
viewing positions, one for each eye. This should be quite easy
using the setxfm2() routine.
- 7 -
FUNCTION DEFINITIONS :
setxfm - Set rotation and translation values for next xform.
USAGE :
setxfm(a1,a1,a3,x,y,z,m,d)
double a1,a2,a3;
long x,y,z,m,d;
FUNCTION :
This routine sets transformation matrix values based on the
parameters you pass it. The actual matrix is a global array,
however for upward compatibility's sake, you shouldn't access it
except through this routine.
INPUTS :
The three parameters, 'a1-a3' are rotation angles in radians
(see the description of rotations following the structure
definitions). 'x','y','z' are translation parameters. Since
positional values are integral, the translation values must also
be integral.
'n' and 'd' are scaling factors. Since integer arithmetic is
used, a fraction is used for the scaling factor. 'n' is the
numerator and 'd' is the denominator of the scaling factor. The
way this is implemented, it doesn't slow the translations down,
so if you don't need it just set 'n' and 'd' to 1. It will be
just like they didn't exist.
OUTPUTS :
None.
---------------------------------------
setxfm2 - Set rotation and translation values for next xform.
USAGE :
setxfm(x,y,z,dx,dy,dz,m,d)
long x,y,z,dx,dy,dz,m,d;
FUNCTION :
This routine sets transformation matrix values based on the
parameters you pass it. The actual matrix is a global array,
however for upward compatibility's sake, you shouldn't access it
except through this routine.
The only difference between this routine and setxfm() is how
the viewing angle is specified. rotatep() or rotatevp() is
normally used with this routine.
INPUTS :
'x','y', and 'z' are translation factors, just like those
used in setxfm(). If rotatep() or rotatevp() is used, these
variables are used to specify the location of the viewer.
'dx','dy', and 'dz' are then used to specify viewing
direction. These variables define a vector pointing in the
direction to be looked in. The length of this vector affects
- 8 -
nothing. Z will always be upwards on the screen, unless looking
straight up or straight down. For example, a viewer at (-10,-
10,-10) looking towards the origin would be defined by :
setxfm2(-10,-10,-10,10,10,10,n,d).
'n' and 'd' are scaling factors. Since integer arithmetic is
used, a fraction is used for the scaling factor. 'n' is the
numerator and 'd' is the denominator of the scaling factor. The
way this is implemented, it doesn't slow the translations down,
so if you don't need it just set 'n' and 'd' to 1. It will be
just like they didn't exist.
OUTPUTS :
None.
---------------------------------------
rotate - Rotates an array of vectors using the current setxfm()
vals without perspective.
USAGE :
rotate(v,n)
VECTOR *v;
int n;
FUNCTION:
This routine actually performs the translation of a group of
points in 3-space based on the parameters set by setxfm().
INPUTS :
'v' points to a vector structure which must be initialized with
pointers to all 6 arrays of size >='n'. The first 'n' vectors
will be rotated. Note that the 'x','y','z' VECTOR values are
unchanged. These values are transformed, and the results are
stored in 'tx','ty','tz'. If you wish to transform a subset of
the points, a separate VECTOR structure pointing to the
beginning of the subset can be used.
OUTPUTS:
none.
---------------------------------------
rotatev - Rotates an array of vectors using the current setxfm
vals with perspective.
USAGE :
rotatev(v,n)
VECTOR *v;
int n;
FUNCTION:
This routine actually performs the translation of a group of
points in 3-space based on the parameters set by setxfm(). The
only difference between this routine and rotate() is the
addition of perspective.
- 9 -
INPUTS :
'v' points to a vector structure which must be initialized with
pointers to all 6 arrays of size >='n'. The first 'n' vectors
will be rotated. Note that the 'x','y','z' VECTOR values are
unchanged. These values are transformed, and the results are
stored in 'tx','ty','tz'. If you wish to transform a subset of
the points, a separate VECTOR structure pointing to the
beginning of the subset can be used.
OUTPUTS:
none.
---------------------------------------
rotatep - Rotates an array of vectors using the current setxfm
vals.
USAGE :
rotatep(v,n)
VECTOR *v;
int n;
FUNCTION:
This routine actually performs the translation of a group of
points in 3-space based on the parameters set by setxfm(). The
only difference between this routine and rotate() is that
translations are done before, not after rotations. This makes
this routine work correctly with setxfm2().
INPUTS :
See rotate()
OUTPUTS:
none.
---------------------------------------
rotatevp - Rotates an array of vectors using the current setxfm
vals with perspective.
USAGE :
rotatev(v,n)
VECTOR *v;
int n;
FUNCTION:
This routine actually performs the translation of a group of
points in 3-space based on the parameters set by setxfm(). The
only difference between this routine and rotatev() is that
translations are perfomed before, not after rotations. This
routine should be used with setxfm2().
INPUTS :
See rotatev()
---------------------------------------
- 10 -
Init3Ras - Sets a rastport up for area fills.
USAGE:
Init3Ras(rp,rp2,rp3,rp4)
struct RastPort *rp,*rp2,*rp3,*rp4;
FUNCTION:
This routine should be called once for each RastPort to be used
with d3surf(). If it is called more than once with the same
RastPort it could cause serious problems. This routine only
needs to be called if d3surf() is going to be used. If only
d3lines() is going to be used, you can save some memory by not
calling this routine.
INPUTS:
'rp'-'rp4' point to RastPorts which will be used with d3surf().
d3surf uses area fill operations, so the RastPort it uses must
be given temporary storage for use in the filling. 'rp2'-'rp4'
should be set to NULL if only one RastPort is to be used. If
both are passed, they will be assigned the same temporary
storage area, thus saving a significant amount of memory.
This routine allows multiple rastports for use in double-
buffering and x-specs. If double-buffered, x-specs animation is
performed, 4 screens will be required.
OUTPUTS:
None.
---------------------------------------
Exit3d - Frees up the memory allocated by Init3Ras.
USAGE :
Exit3d(rp)
struct RastPort *rp;
FUNCTION:
This routine frees up the memory allocated by Init3Ras().
INPUTS:
'rp' points to a RastPort initialized with Init3Ras(). If 2 or
more RastPorts were initialized with a SINGLE call to
Init3Ras(), only ONE of them should be passed to Exit3d(), and
none should be used with area fills again.
I should explain this in more detail. If two RastPorts are
initialized with a single Init3Ras() call, both RastPorts will
point to the same scratch memory area. Exit3d() frees this
memory up. After you call it for one of the two RastPorts, the
other one will point to an unallocated area in memory. If a fill
operation is done at this time, it can cause all sorts of nasty
problems. Be warned.
OUTPUTS:
None.
- 11 -
---------------------------------------
d3lines - Draw a group of lines connecting points in 3 space.
USAGE:
d3lines(vector,line,n,rp)
VECTOR *vector;
LINES *line;
int n;
struct RastPort *rp;
FUNCTION:
This routine actually draws lines connecting one or more points
in 3-space. See the information on the VECTOR and LINES
structures for more info.
INPUTS:
'vector' points to a VECTOR structure with information on the
points to be used in the line drawing. 'line' points to an array
of LINES structures which contains a description of how the
lines are to be drawn. 'n' is the number of elements in the
array pointed to by 'line'. 'rp' points to the RastPort where
the lines should be drawn.
OUTPUTS:
none.
---------------------------------------
d3surf - Draw a group of surfaces in 3 space.
USAGE:
d3lines(vector,line,n,rp)
VECTOR *vector;
LINES *line;
int n;
struct RastPort *rp;
FUNCTION:
This routine is just like d3lines(), except filled polygons are
drawn rather than lines. The polygons are sorted before drawing,
so hidden line removal is accomplished. PLEASE READ ABOUT HIDDEN
LINE REMOVAL BELOW.
INPUTS:
'vector' points to a VECTOR structure with information on the
points to be used in the surface drawing. 'line' points to an
array of LINES structures which contains a description of how
the surfaces are to be drawn. 'n' is the number of elements in
the array pointed to by line. 'rp' points to the RastPort where
the surfaces should be drawn.
OUTPUTS: none.
- 12 -
STRUCTURES :
VECTOR ->
long *x,*y,*z;
long *tx,*ty,*tz;
This structure points to the data for all the vertices that
are transformed. 'x','y','z' are arrays with the untransformed
vertex information. 'tx','ty','tz' are arrays which contain the
transformed equivalents of the vertices. 'tx','ty','tz' are
filled in by rotate() and rotatev(). They must be initialized to
point to sufficiently large areas of free memory by the user.
The 'x','y','z' values represent vertical pixels on the
screen. ie - the point (10,1,10) without perspective would
appear 10 pixels below and 23 pixels to the right of the defined
center (using a 23/10) aspect ratio.
-----------------------------------------
LINES ->
unsigned short l;
unsigned short nl : 1,nc : 1, nco : 1;
For those of you not familiar with the above notation, nl, nc,
and nco are 1 bit integers allocated within a single unsigned
short. An array of LINES structures contains the information for
line/polygon drawing. The fact that 'l' is allocated as a short
means that you can't have more than 2^16 vertices in any single
array. Hopefully this won't present any problems.
The array of LINES should be used as follows :
'l' contains a vertex number in a VECTOR structure or a color
(see below).
'nl' is set if this vertex is the beginning of a new
line/polygon.
'nc' is set if 'l' represents a new fill color for polygons.
'nco' is set if 'l' represents a new outline color for polygons,
or a new line color for line drawing.
If filled shapes are to be drawn, not just lines, be sure to
start a new line for each new polygon. That is, don't draw two
filled shapes with one continuous line. This would look fine
with d3lines(), but would produce strange effects with d3surf().
Make sure all filled shapes are planar. The new surface sorting
routine requires all surfaces to be planar. Incorrect sorting
may occur if non-planar shapes are drawn.
Color changes with d3lines() may occur anywhere. However,
color changes used with d3surf() must occur only immediately
after a nl=1 element. This is due to the way hidden line removal
works. Every nl=1 element is taken to be the beginning of a new
polygon. These polygons are then sorted so the farthest ones are
drawn first. Color changes occurring before a nl=1 point will be
attached to the wrong polygon when they are sorted. Color
- 13 -
changes in the middle of the shape may not have the desired
effect (after 1 or more lines have been added).
Here is a sample LINES array to make this all more clear :
l nl nc nco
0 0 1 0 0 <- Starts a shape, vertex 0
1 2 0 0 1 <- Changes to outline color 2
2 1 0 1 0 <- Changes to filled color 1
3 1 0 0 0
4 2 0 0 0
5 3 0 0 0
6 0 0 0 0 <- Closes the shape, not necessary
for d3surf().
7 3 0 0 1 <- Changes outline color. This is
fine for d3lines(), but won't
change correctly for d3surf().
8 4 1 0 0 <- New shape
9 5 0 0 0
10 6 0 0 0 <- No color was defined after the
new shape started, so the color
from the last drawn shape will
be used. The shape is not
closed. d3surf() will close the
shape anyway. d3lines won't.
In the above example, 0-6 will draw a quadrilateral in color 2
if d3lines() is used. It will draw a filled quad., filled with
color 1 and outlined in color 2, if d3surf() is used.
- 14 -
ROTATIONS, AND HOW THEY'RE DONE
-------------------------------
This program uses a very standard scheme for rotating objects
which is completely general. That is, you can observe your
'scene' from absolutely any imaginable perspective (within the
bounds of integer math).
The axes are set up as follows :
Z| / Y
| /
| /
|/
-------------
X
That is, the X axis is the screen x axis, the Z axis is the
screen y axis, and the Y axis goes positive into the screen.
Rotations (for setxfm) are defined in terms of three steps.
'a1' defines a rotation angle from the X axis in the X-Y plane.
'a2' then rotates the specified number of radians away from the
Z axis in the Y-Z plane. Finally 'a3' defines a rotation in
radians from the new (rotated) X axis in the new X-Y plane.
Explained another way : Say the ground is in the X-Y plane, ie
going into the screen. 'a1' would spin an object resting on the
ground as if it were a top. 'a2' would cause this rotated object
to tilt on the screen, just like the Aster*ids spaceship spins.
'a3' would take the tilted object and spin it along the tilted
plane. a3 is a bit hard to picture, play with it.
I know this is somewhat complex, but you can do any possible
rotation with it once you get the hang of it. It may also be
easier to visualize if you picture the observer moving, rather
than the object being rotated. I may try to add a few other
schemes in the next version. We'll see what I can find.
For those of you who are interested you can see how this
transformation works in "Classical Mechanics" by Goldstein on
page 146. (What can I say, I'm a physics major.)
The new setxfm2() routine uses the same translation scheme as
above. It simply converts the information you give it to
setxfm() form. a3 is always set to 0.
To display shapes from setxfm2() as explained, rotatep() or
rotatevp() must be used. These routines perform the translation
operation before the rotation operation. That is, they are
designed to be used with a viewer that is moving around in 3-
space, rather than a fixed viewer with moving objects. (objects
can always be moved by changing their 'x','y','z' coords before
a call to rotate). For the record, it would have been possible
to implement this with the old rotate routines, but the new
routines should do it a little faster.
- 15 -
Hidden Surface Removal
----------------------
This has been the single biggest headache in the development
of this library. Ver 1.5(beta) included an 'improved' routine
that would do hidden surface removal perfectly with any set of
planar shapes. Unfortunately, there was quite a lot of overhead
in this routine, and I found it unbearably slow. I also never
got it working 100% (I did get close). Eventually I got fed up
and decided to do things the fast, but less friendly, way.
An improved simple sorting routine is used in the release
version. It sorts surfaces (planar surfaces are still pretty
necessary) by doing a quicksort on the average y position of
each surface. It is quite speedy, but it has a number of
limitations.
This routine will work fine as long as you restrict yourself
so all surfaces that are close together are roughly the same
size. If you need to make very large surfaces near very small
surfaces, break the large one up into several smaller ones.
Large, strange shapes, like the floor in maze.3d will cause
problems. (that's why I included maze.3d)
Essentially, the way to do high speed display of a series of
3d objects is to separate objects (groups of surfaces), sort the
objects, then sort the surfaces within the object. As long as
objects don't overlap in strange ways, this is the way to go.
So, what you should do is set up several different LINES
structures (all points can go in one VECTOR structure). Each
LINES structure will contain data for one 'object'. Sort the
objects yourself, then call d3surf for each.
I plan to write a set of object oriented routines that will
sit on top of the present library and make the above process
more automatic. I hope to support routines like new_object(),
add_surface(), move_object(), draw_object(), draw_objects(), etc
... This should make the library considerably more user
friendly (if I find time to do it in the near future).
---------
Again, if you run into any bugs or problems please let me
know. Also keep in mind that, while you may feel free to modify
this code, you might have upward compatibility problems if you
do. I tried to comment the code a little for those of you who
feel like making changes. Have fun !!!
- 16 -
