3DICA v2.

22b
The Ultimate 3D Coding Tutorial (C) Ica /Hubris 1996,1997,1998
Over 150k of pure sh...er, 3d coding power !

0 General Things
0.0 LICENSE AGREEMENT

0.0.1 DISCLAIMER

3DICA PROGRAMMING TUTORIAL IS SUPPLIED AS-IS. THE AUTHOR

DISCLAIMS ALL WARRANTIES, EXPRESSED OR IMPLIED, INCLUDING, WITHOUT
LIMITATION, THE WARRANTIES OF MERCHANTABILITY AND OF FITNESS FOR
ANY PURPOSE. THE AUTHOR ASSUMES NO LIABILITY FOR DAMAGE TO ANY
LIVING / DEAD CREATURE OR EQUIPMENT, DIRECT OR CONSEQUENTIAL,
WHICH MAY RESULT FROM THE USE OF THE 3DICA PROGRAMMING TUTORIAL.

0.0.2 LIMITED WARRANTY

SATISFACTION GUARANTEE. If you are dissatisfied with this product

you downloaded from some F..ine BBS or the Internet, you may delete it at
any time up to 30 days after download and you will get your hard disk space
(that was occupied by the product) back. The space will be based on the
space that was occupied during the installation, with the cost of some bad
sectors, viruses and neat hidden files excluded. You must contact the author
before deleting the product.

(Used the readme.txt of Action Supercross as a basis)

0.0.3 Seriously

The 3DICA Programming Tutorial is FREEWARE. This means, it can

freely be used and distributed as long as it is NOT CHANGED in any way. Of
3DICA, one is not allowed to charge any fee without a written permission of the
author. The author is not liable of any damage caused by the source code
included in the package.
 0.0.4 3dica careware - what does that mean ?

If you have noticed how much work I have had making this tutorial and
are thinking about how to repay my efforts, I would appreciate any cash / other
nice things you could send. The people who send at least USD 5 (20FIM in
Finland), will get their names and some comment of their own published in
the next versions of 3dica. I reserve myself the right of not to publishing sick,
offensive or in some other way tasteless ‘comments’.

Just to mention, Chem (Kaj Bjorklund) will get a third of all

contributions. Since version 2.1, Chem has been an active supporter of 3dica in
three ways : by proofreading every new version of the doc, by writing many
chapters of text, and by asking now and then unbelievably stupid questions 

Here’s the address to which you can send your wallets / daddy's wallet /
its contents :

Ilkka Pelkonen
Kynnysmaentie 10
FIN-01860 Perttula
FINLAND.

0.1 The Authors, Greets, etc

0.1.1 Ica

My real name is Ilkka Pelkonen and I’m a 19-year-old c, (pascal), and

assembly coder. I live in Finland, near the capital city of Helsinki (30 km to the
north). My hobbies include 3D coding, some cool games (Paybacktime2, Steel
Panthers, C&C, Warcraft 2, Screamer 2), writing 3dica, and jogging.
I’m studying computer science in the Helsinki University of Technology,
and I’ll probably concentrate on digital media. I’ll join the Finnish Army in july
1998, and my ‘job’ there being "a special duty for mathematically oriented men"
8-) I belong to the group Hubris, see a short overview below.

The best way to contact me is emailing to the address ipelkone@cc.hut.fi,

so any comments or other discussion there. Please report any errors you
might find in the text.

0.1.2 Chem

My real name is Kaj Mikael Bjorklund, and I’m a 18-year-old c, pascal,

and assembly coder. I live in Finland, Helsinki, ‘Roihuvuori’ if it says
something. Nice place. I’m mainly into programming (a real surprise I can
guess), but I have also tried to keep my physical condition up by lifting
weights. I’m joining Ica and (other ) gurus (Tremor/Trauma, Abyss/FC,
Beta/5C, ...) in HUT this fall. I’ll join the Finnish Army in January 1999.

I’ve released a couple of players which no one (understandably) is using,

and made with my pals a game Rocket Chase (which some ppl even play).

The best way to contact me is emailing to the address

kaj.bjorklund@mbnet.fi. You may check out http://www.pcuf.fi/~chem/, too.
Especially females are encouraged to email immediately 

0.1.3 Hubris Productions

First, you may want to check the Hubris Productions Homepage (although
it’s quite nothing; built up in a couple of hours just as a practice )

The history of Hubris Productions :

1995

February Bull (Tapio Vuorinen) and Slimey (Petri Tuohimaa)

found the group Dozer, Bull as an organizer/coder
March Override (Jouni Airaksinen) joins Dozer as a musician
October Zass (Jesse Lantinen) joins Dozer
1996

Planning a demo ‘Totally Oldish’ (nothing was ever released, though

)
Zass and Slimey leave Dozer
1997

February Bull and Override start coding a demo ‘Rain’

April Override releases a tune "Deep Dreams"
May Ica (Ilkka Pelkonen) and Chem (Kaj Bjorklund) join in, Ica as a
3D coder and secondary organizer, Chem as a music system coder
Dozer changes its name to Hubris (yeah!)
Ica releases v2.1 of his 3D coding tutorial 3DICA
June Acute (Aleksi Kallio) and Tweeker (Timo Makimattila) join
Hubris, Acute as a general stuff coder, Tweeker as a musician/graphician
July Ica releases v2.11 of 3DICA
September Chem releases first public version v1.0 of Hubris Module
Player supporting SB2/Pro/16/GUS and MOD/S3M (DJGPP)
 October Codger (Juha Leinonen) joins Hubris as a 3D modeller
Chem releases HMP v1.01
November Ica releases v2.2 of 3DICA this version describing widely
3D coding stuff from basic vector math to lighting effects, phong shading, and
BSP tree. The document is a great success
December Rondo (Lauri Tuovinen) joins Hubris as a musician
Chem releases HMP v1.06 with XM support. Many speed-requiring
loops have been translated into assembly and the player is now a tad bit faster
1998

January Ica converts 3DICA into HTML and translates the whole shit
into English. Plenty of bugs have been fixed and some enhancements have been
done. The English and Finnish versions are now developed separately
March Ica releases 3DICA v2.21 (the first complete English version).
New subjects include inverse transformations, rotation about an arbitrary
vector, and B-Splines

0.1.4 Thanks for help

I list here the people who have somehow helped me with my own engine
or written themselves a chapter to 3dica. Thank you guys.

 Kaj Bjorklund (Chem/Hubris) Kaj is the official proofreader of 3dica.

In addition, he has written about linear interpolation, phong
illumination, frameskip, texture mapping tricks, gouraud, mip-
mapping, convex polygons, bilinear filtering, and "real" phong. He has
also written the c source code included in the package.
 Jonathan Castellanes (Loonix) Correcting grammatical and other
errors in the English version of the document (so blame him not
me  ; general debugging.
 Tapio Vuorinen (Bull/Hubris) Proofreading, Z-buffer; the Finnish
version after v2.21.
 Henri Tuhkanen (Rodex/Static) Asm optimizing course, some texture
mapping tricks.
 Jere Sanisalo Portals. You'll always find the newest version of 3dica at
the homepage of Jere, if hut.fi is down.
 Timo Saarinen Perspective correction.
 Sampsa Lehtonen (TexMex/Gigamess) Palette quantisizing.
 Jukka Liimatta (Wog/Orange) Bilinear filtering.
 Jari Komppa (Sol/Trauma) Median cut.
 Altair Mental support 
 The readers Informing about bugs that can always be found
everywhere
  Ilkka Pelkonen (Ica/Hubris) Everything else. 

0.1.5 Greets

Ica (in no special order) :

Beta /5C, TheJoker /Crusaders, Ripple /Inside, Tonic /Trauma, !Cube

/Trauma, Sol /Trauma, Spector /Trauma, Wog /Orange, Case /Fuse,
Friction /Morel Arts, Memon /m0ppi prods, Jokke /Bad Karma, GREco
/Oblivion, Submissive /Cubic Team, Sagacity /Acme, Mrz /Astroidea,
Reptile /Astroidea, Zox /Storm, Proton /Tehdas (4ever!!), Texmex
/Gigamess, Goblin /Quad, Fobic /Cycla, Howler /Fobia Design, Hude
/RE, Cyberfish /TLS, Zapmies, Venomix, RaS, Mako, dAS, Whizzzzter,
MiGbear, Sqrt(-1), JayLettu, Raster, Harmless, Midnight, Altair, Kalms,
Malc, Praetor, Absent, Adept, Gaffer, 3D-Zed , Loonix, RH, Vulc, Duet,
Vulture, Elflord, Janne Gronthal, Antti Haapakoski, Jussi Vainionpaa,
Jukka Keski-Oja, Otto Chrons, ..., *.Hubris, everyone at #coders,
everyone who think they ought to have been greeted 

Chem :

Haanpera bros & other RC people, Markku Ekblom, Antti Qvickstrom,

Sampsa Lehtonen, Antti Karjalainen, Ilkka Pelkonen, Tapio Vuorinen,
Jere Sanisalo, Joonas Pihlajamaa, Pekka Nurminen, Aki Puustinen, tAAt
members, Hubris members, mailing pals, other friends.

0.1.6 Thanks for support

Our heartfelt thanks to these people who have supported the development
of 3dica monetarily. Special thanks to the people whose names are marked bold.
Registered persons’ own comments in italic.

 Joonas Pihlajamaa : Imuroi lamertutti, imuroi lamertutti ! BAD

KARMA rulettaa !
 Tommi Pisto
 JiMM: jeejee paasin greetzeihin ..
 Erik Seesjarvi
 Juhana Venalainen : Ei millaan pahalla mutta hyvaa paivaa.
 Ville Ruusutie : Some day I will conquer the world.
 0.2 About the Document

0.2.1 Where can I get the newest version of 3dica ?

The Official home page and distribution site of 3dica can be found in
http://www.hut.fi/~ipelkone/3dica/. The newest version can also always be
found at Jere Sanisalo's home page http://www.sicom.fi/~cooldude/.

0.2.2 What has happened since the last version ?

 Fixed some minor errors in typing etc

 Optimized bfc and vertex normal calculation pseudos
 In the BSP-Tree / Required Formulas chapter there was a minus sign missing
in the formula of t. This didn’t matter, though, if you used the formula only
in BSP-Tree. Fixed.
 The vertex transformation pseudo was surprisingly buggy : two of the
coefficients were wrong (the XYZ rotation matrix was correct though).
Fixed.
 4x4 matrices !
 For the convenience of unix users, the picture filenames were changed to
lower case in both document and the files themselves.

0.2.3 Features to be added

Some topics, which will probably be described in some way in future

versions :

 Complex numbers (needed with fractals)

 Quaternions
 3D shadows
 Bresenham line algorithm (for tmapping optimization)
 Subpixel accurary
 Optimization tricks for 3D geometry
 Suggest yorself new topics !

0.3 3D Terms etc.

At first, the co-ordinate system I’m using is as follows: x-axis from left to
right, y-axis from up to down, and z-axis points directly into the screen. The
coordinate system is so a right-handed one, which means two things :

1) The direction of the z-axis can be found with the first three
fingers of the right hand, by sticking thumb to the right and the following
 finger downwards. The third finger shows now the direction of the z-axis
(when all fingers are perpendicular to each other).

2) Rotation about the axes is determined like this : when the thumb
of the right hand is pointing to the direction of an axis, the other fingers bend to
the positive rotating direction (that is, when you’re rotating an object about the
z-axis to the positive direction, it rotates clockwise).

And then 3D related terms.

 Additive rotation. Object matrices are reset every frame and the
rotation angles must be changed constantly to the objects rotate
constantly. (Brr.. don’t use this way -- see cumulative rotation below.)
 Bilinear filtering. A technique that smoothens close-zoomed bitmaps.
 Clipping. Cutting a polygon against another.
 Complex polygon. A polygon that can cut itself.
 Concave polygon. A polygon that has angles greater than 180 degrees,
but is still solid.
 Convex polygon. A polygon whose all angles are less than 180
degrees. Drawing one is as easy as drawing a triangle.
 Cumulative rotation. Rotating in a way that object matrices are reset
only in the init part of the program. This means that if the rotation
angles stay constant, the object keeps rotating at a constant speed. This
is the Real Way of rotating; it ensures that objects rotate about their
own axes instead of the whole world’s ones.
 Face. A polygon on an object's surface. The corners of a face are
called vertices.
 Keyframing. Having some key values and interpolating between them
to obtain a smooth movement between colors, rotation angles,
positions, etc. In 3D movement, this practically means having some
orientations of objects and/or camera saved and interpolating between
them with quaternions (below) and splines (below too )
 Matrix. Kind of a table of numbers, with help of which certain
complex mathematical operations are easier to perform. Matrices are
used in 3D transformations.
 Mip-mapping. Of a texture, differently-sized and pre-filtered bitmaps
are kept in the memory. When drawing a polygon, a suitably-sized
mipmap is chosen depending on the size of the polygon. Like this, we
get a neat and good-looking filtering effect to texture mapping for free.
 Origin. The center of a space; coordinates (0,0,0).
 Palette quantisizing. Reducing the number of colors to fit a palette as
optimally as possible.
  Quaternion interpolation. Using 4D space to interpolate object
orientations smoothly from one to another.
 Scanline subdivision. Perspective correction is performed only every
8th or 16th pixel and linear interpolation is used in the middle.
 S-buffer. Segmented buffer or span-buffer or scanline Z-buffer.
Improved Z-buffer, where calculations are performed for scanlines
instead of points.
 Sorting. Determining the drawing order of polygons so that the farthest
ones are drawn first and the closest ones last.
 Spline. Given a desired amount of arbitrary points, a spline is formed
using certain formulas to go through or near all these points keeping
the spline as smooth as possible. Neat for camera location
interpolation, for example.
 Subpixel. The position inside a pixel.
 Subtexel. The position inside a texel (see bilinear filtering).
 Texel. Texture element; the color of a point in a bitmap (cf. pixel =
picture element).
 Vector. A line which has a constant length and direction, but no
determined location.
 Vertex. A corner point of an object, to which one or more faces are
attached.
 Vertex normal. The normal of a vertex  the approximation of which
can be calculated by taking the average of the normals of every face
attached to the vertex.
 Z-buffer. A sorting technique where points are sorted into a screen-
sized array to an order determined by the values of the points' Z
coordinates. Only the closest pixel is drawn.

0.4 FAQ

A very general but still worth-to-know piece of advice to all questions:

USE YOUR WIT ! Sure your code won’t work, if not even the SYNTAX is
right !

Q: My 3D rotations which have been grabbed straight from the text don’t work.

A: Are all the variables of right type ? Glanced at the C source code ? 

Q: My texturemapper messes the screen up. I can’t find any problems anywhere.

A: Could be a rounding problem. Fixed :

 putpixel( x, y, tmap[ u/65536+v/256) ] )

You’ve cleverly thought to optimize a bit : when v should be divided by 2^16

and multiplied by 2^8, you’ve just divided it by 2^8. The result is wrong. Why ?
Now the upper 8 bits of the decimal part of your 16.16 fixed point won’t be
cleared, and tmap regards them as u coordinates, so the result is wrong. The
right way is as follows :

putpixel( x, y, tmap[ u/65536+(v/65536)*256) ] )

Float:

putpixel( x, y, tmap[ word(u+v*256) ] )

The decimal parts of u and v mess each other up so misrepresenting the result.
The right way :

putpixel( x, y, tmap[ word(u)+word(v)*256) ] )

I myself had btw this problem and wondered for a long time why using floats
totally messed the routines up 

Q: My flat polygon routine doesn’t work.

A: Are the variables of right type ? Do you use integer divide with floats or vice
versa ? Can you really use fixed point ? Do you remember to divide by it at the
end ? Does your vertex sorting work ?

Q: What are the terms AB, BC, and CA in the face listing of 3D-Studio’s asc
format ? (duh )

A: They tell if a line is drawn or not in a wireframe figure.

Q: When should I use vertex normals, when face normals ?

A: Use vertex normals with gouraud and phong shading, and face normals with
lambert flat shading.

0.5 Recommended References

 As a great help and the Bible of graphics coding I use the glamorous book
Computer Graphics : Principles & Practice, 2nd Ed by Foley, Van Dam,
Feiner and Hughes, Addison-Wesley 1993. Other books and documents are
listed below.

 Advanced Animation and Rendering Techniques, Watt brothers,

Addison-Wesley 1996 - every kind of 3D related stuff 
 Algebra ja Geometria, Kivela, Simo, Otatieto 1997 - matrices, 3D
rotations, projections
 OTMMATX.DOC - matrices, hierarchical systems
 OTMPHONG.DOC - phong illuminating
 VGOPHONG.DOC - real phong
 FATMAP2.TXT - texturing stuff
 The S-buffer FAQ - S-buffer 
 PC Game Programmer's Encyclopedia 1.0 - BSP-tree
 PENTOPT.TXT - pentium optimizing tricks

[numerous other documents the names of whose I really can't remember]

0.6 A Quick Introduction to Radians

Radians are called the mystical angles all trigonometric functions (sine,
cosine, tangent, cotangent, ...) in mathematical code libraries take as their
parameters. What are they ? Where did they come ? Why did they come ? I’ll not
answer the two latter questions  but I’ll tell how to use them in your apps.

Radian angles can be treated like any other angle by only

remembering that the degrees of a full circle (360 degrees) are 2*PI
radians:
360 degrees = 2*PI = 6.28.. radians
Using this information, we derive a formula how to convert degrees to
radians and vice versa :
x radians = (360 * x degrees)/2*PI = (180 * x degrees)/PI.
x degrees = (2*PI * x radians)/360 = (PI * x radians)/180.
We can now calculate how many degrees is one radian:

1 radian = (1 degree)*180/PI = 57.295... degrees.

Now it should be quite clear. And remember : don’t be afraid of using

radians – they’re as good an alternative as degrees, and at least as simple to use.