3D Graphics: How to do
(by Andrew Zabolotny)
There are some ways to show an real-life object in interactive graphics,
let`s say games. The most popular is so-called `bitmap` method, i.e.
object first is drawn in some kind of 2D image editor and when object must be
shown an aproppiate picture is selected and `shooted` to video memory.
It is an well-known method, so we will not discuss here its positive and
negative parts, will mention only some negative parts: inability to show
object from _any_ point in real-world 3D space.
Other method is `vector` graphics, i.e. object is described as a lot
of points and faces between these points. All faces are plane, no curve lines
at all (theoretically curve planes are possible but them are too slow for
something more complex than a sphere). Naturally, points can be
two-dimensional (just remember `Another world` and `FlashBack` by Delphine)
and three-dimensional. The last case is what we need.
First question is: how to describe an 3D object. It is a matter of
taste, but often an 3D object is described in the way like this:
; Vertices first
Vertex 0: 10 10 10
Vertex 1: 10 10 -10
Vertex 2: 10 -10 -10
Vertex 3: 10 -10 10
; ... and faces
Face 0: 0 1 2 3
Additional to this you can define keywords for defining attributes,
different face types etc. Now all what we need is to project these 3D points
somehow to the screen and to draw an polygon between 2D points 0, 1, 2 and 3.
The math needed for projection is quite simple, however we`re too limited in
space (and for most of you is no need at all), if you`re interested see
literature at the end of article. The final result is: suppose we`re looking
along X axis and Y axis comes to the right of you and Z axis comes upwards.
Something like: U
.------------------->
| Z| X/ | The border around is the screen. So, how you can
| | / | see, the origin is in center of screen at the
|---------+-------->| (ScreenWidth/2, ScreenHeight/2). How we do the
| O| Y| projection? Let`s say horizontal coordinate
V| | | (often called X) we`ll call U and vertical(Y) - V.
`-------------------´
Y * FD Z * FD
U = -------- + ScreenWidth/2 V = ScreenHeight/2 - --------
X X
where FD stands for `focal distance`, i.e. distance from your eye to the
screen. For medium size objects (about 100-200 units in diameter) it is
around 200.
Now we have a way to convert 3D spacial coordinates into `screen` 2D.
Now, what we have to do if we need to look in a different direction,
not along X axis? All we have to do is to ROTATE these points.
For example, if we need to draw scene as we were looking turned to the
right of X axis by 45ø we need to turn all points around Z axis to the left
by 45ø and then project them as described above. Now if we need to project
a scene looking from a point different from origin and turned around OZ
by 33ø? In this case you need to TRANSLATE points into origin and then
to ROTATE them. Note that you cannot ROTATE and then TRANSLATE, `cause
result will be slightly different :)
So, we need to rotate them. `So complex!` will shout an beginner.
`Those sines and cosines will slow entire program for thousand times!'.
Really all is not so terrible. We need to compute `those sines and cosines`
only once per frame and then use them. We have to use some transformation
matrices for this (if you wish to know more `bout them see literature).
I`ll give here matrices for rotation around OX, OY & OZ (although we`ll
need only two of them now).
Around OX: Around OY:
/ 1 0 0 \ / cos(Q) 0 -sin(Q) \
| 0 cos(£) sin(£) | | 0 1 0 |
\ 0 -sin(£) cos(£) / \ sin(Q) 0 cos(Q) /
Around OZ:
[ cos(P) sin(P) 0 ] X' = X * cos(P) + Y * sin(P)
[ -sin(P) cos(P) 0 ] i.e. Y' =-X * sin(P) + Y * cos(P)
[ 0 0 1 ] Z' = Z
And the nice part of these matrices is that you can multiply them
and get a transformation matrix for two rotations at a time. So, let`s
try to make matrix for rotation around OZ and OY at a time:
/ cos(P) sin(P) 0 \ / cos(Q) 0 -sin(Q) \
| -sin(P) cos(P) 0 | * | 0 1 0 | =
\ 0 0 1 / \ sin(Q) 0 cos(Q) /
/ cos(P) * cos(Q) sin(P) * cos(Q) -sin(Q) \
| -sin(P) cos(P) 0 |
\ cos(P) * sin(Q) sin(P) * sin(Q) cos(Q) /
So, final formulas are:
X' = X * cos(P) * cos(Q) + Y * sin(P) * cos(Q) - Z * sin(Q)
Y' =-X * sin(P) + Y * cos(P)
Z' = X * cos(P) * sin(Q) + Y * sin(P) * sin(Q) + Z * cos(Q)
where P is angle around OZ and Q is angle around OY.
Next question. Can I define looking direction in a more comprehensive
way? First of all, previous two angles are enough comprehensive. P is
horizontal angle (angle to rotate head in horizontal plane) and Q is
vertical angle (angle to rise head by). Second, you can define direction
via a point you`re looking at. If you have point from which you`re looking
(EyeX, EyeY, EyeZ) and point to where you are looking (EyeX+DX, EyeY+DY,
EyeZ+DZ) the sines and cosines are:
DY DZ
sin(P) = --------------- sin(Q) = --------------------
Sqrt(DX²+DY²) Sqrt(DX²+DY²+DZ²)
DX Sqrt(DX²+DY²)
cos(P) = --------------- cos(Q) = --------------------
Sqrt(DX²+DY²) Sqrt(DX²+DY²+DZ²)
Next problem is, how we have to draw resulting polygons so those that
are far will not overlap those which are near? There are some solutions and
compromises, so you have to choose one. An relative FAST and very ACCURATE
method is BSP (binary-space-partitioning) trees, but they are complex to
code and too long to describe here (the only thing I know about them is that
method was developed by LucasFilm somewhere in `84 and published in a
related magazine, don`t remember the name, if you`re really interested look
through old snippets from Internet comp.graphics.algorithms). The most used
method is sorting by distance. All that you need to is to compute for each
face:
Nvertices
Sum ((Xi-EyeX)² + (Yi-EyeY)² + (Zi-EyeZ)²)
i=1
--------------------------------------------------
Nvertices
(i.e. medium distance from eye to face`s vertices) and then sort faces
by this value. Draw first the most distant face then draw next less distant
face and loop through them up to last face.
Now we can outline an general algorythm for drawing an 3D scene:
1) Translate all points by -EyeX, -EyeY, -EyeZ.
2) Rotate them around origin in corespondence to your direction of view.
3) Project all points. You will get a bunch of pairs (U, V).
4) Translate description of each face into pairs (U,V) and compute
medium distance to each face.
5) Draw`em from the most distant to nearest.
And last tip. If all faces will be described clockwise when looking
from an external point (i. e. face`s normal will be oriented towards you)
you can exclude invisible faces from draw buffer before sorting. If
projected face`s coordinates will be still clockwise it will be visible,
otherwise it is invisible (i.e. these faces will be visible only from one
side). To check if points are clockwise you can compute cross product of
two vectors-edges and examine its sign. Say, we have face 1-2-3-4. If
vector (1-2) X (3-2) > 0 points are clockwise. So, we have:
P1(X1,Y1) P2(X2,Y2) P3(X3,Y3) P4(X4,Y4) - four points
V1(X1-X2, Y1-Y2) V2(X3-X2, Y3-Y2) - vectors 1-2 and 3-2.
Cross product = V1x * V2y - V1y * V2x
if CrossProduct>0
then {Face is visible}
else
if CrossProduct=0
then {Points 1-2-3 are colinear}
else {Face is invisible}
Now you have the basic knowledge about what we`re talking about.
In next issue (i hope) I`ll tell how to draw FAST polygons and so on.
Andrew Zabolotny,
2:5030/84.5@FIDOnet, {prefered}
2:469/37.1@FIDOnet.
Literature.
1. J.D.Foley & A.V.Dam "Fundamentals of Interactive Computer Graphics",
Addison-Wessley Publishing Company, 1982.
2. Infused bytes, issue #3 :)))