3D SpeedUp
This text comes from IMPHOBIA Issue XII - July 1996
* Gouraud'n'texture adders *
(don't divide in each row)
This topic wouldn't exist if Rod / Mandula wouldn't have posted an idea
of Hyp-X / Mandula to the Coder-L, the mailing list of Hungarian coders.
Additional proof was provided by Rob / We'Kings. This article reveals that
the color intensity adder which is used to incrementally calculate the
pixel colors at Gouraud shading is constant for the entire triangle, so
it's unnecessary to recalculate it at each new row. Imagine three points on
your table, these will be the vertices of the triangle. Now imagine (again)
three points above the table, exactly above the vertices. Let's say that the
distance from the table means the color intensity: the closer is the
point to the table, the less intensive the color is. Now there's a new
plane above the table, determined by the three olor intensity points. (It's
not parallel to the table if the color intensities are different.) The
essence is that this is a flat surface, not a curve. It means that
its steepness (its partial derivative) is constant in every given direction.
So it's enough to calculate it once per triangle. The same goes for linear
texturemapping. (For triangles only!)
* Hidden surface removal *
(a two-level approach)
Inspired by the matrix transformation tutorial of Voltaire / OverThrow Machine.
There are several methods of hidden surface removal:
a) checking if the angle between the surface normal and the eye vector is
greater than 90 degrees;
b) checking whether the points of the polygon are in clockwise order after
transformation and projection;
c) other techniques.
The first one's most straight-forward implementation is to rotate all plane
normals first, then check the sign of the transformed vectors' Z coordinate.
Or rotate all vertices, and calculate the Z coord of all the normal vectors.
If it's positive, then the surface is considered to be visible, otherwise
not. (Actually the Z coordinate is nothing else but the dot product of
the eye vector (0,0,1) and the normal vector.) The advantage of the a) is
that this can be done before rotating the objects' vertices; after backface
culling it's enough to transform only those vertices which belong to visible
faces. However, even transforming the surface normals is unnecessary!
Especially if we know the fact that most objects have approximately twice
as much faces than vertices. All we really need is the angle between the
eye vector and the normal. So it's cheaper to transform the eye vector
back to object space and perform the dot product of the back-transformed
eye and the pre-calculated normals. What does back - transforming mean? It
means that the vector needs to be rotated with negative angles in
reversed order: first rotate around the Z axis by minus gamma, then
around the Y by minus beta, etc. Or, the vector has to be multiplied
with the inverse of the transformation matrix. The inverse of a matrix is
that matrix which multiplied by the original gives the unit matrix. (Which
has 1-s in the main diagonal and 0-s everywhere else.)
This way only one vector needs to be transformed, not all the normals. The
problem with this is that if we check only the sign of the dot product, some
visible faces will be treated as invisible and vice versa. Practically,
if a face normal points away from the eye (the angle between the eye vector
and the normal is greater than 90 degrees) the face still can be
visible. This is valid only when perspective transformation is applied;
in an axonometric system the method is correct. So if we don't want to lose
any visible polygons, this technique is not applicable.
The b) method will not lose any faces; but it requires all vertices to be
transformed. It doesn't need the surface normals at all. It costs two
multiplications per surface after transformation and projection: if
(X1-X2)*(Y1-Y3) > (X1-X3)*(Y1-Y2) then the points follow each other in
clockwise order and the face is visible; otherwise not. So what is our
goal?
1) 100% sure backface culling
2) calculate as less as possible
3) transforming only those vertices
which belong to visible faces
The following set of known algorithms meet all requirements. I use a
two-level hidden face removal. In the first step some of the polys is
culled, in the second step the remaining polys are checked.
Level 1:
This is done before transforming the objects' coordinates from object space
to eye space. (So it happens before rotating the object.)
Instead of transforming (rotating) the surface normals I transform the eye
vector back to object space and calculate the dot product of the
surfaces' normal and the back-transformed eye vector. The result is
the same if I'd transform the plane normals to eye space and calculate the
dot product there. Ok, let's see what does the dot product mean. It's
proportional to the angle between the two vectors somehow. Not linearly, but
proportional. (I assume that all normal vectors are unit vectors.) It's
clear that checking only the sign of the dot product isn't correct.
So here comes the trick ;-) If the dot product is smaller than a certain
negative value (let's say -0.3) it means that the angle between the eye
vector and the normal vector is greater than a certain value, that is,
arc cos (-0.3) = 110 degrees. If I would check the only sign of the dot
product I would know only that the angle between the normal and the eye
vector is smaller or greater than 90 degrees. Those faces whose normal is
perturbed more than 110 degrees form the eye vector, are surely invisible.
This angle, of course, depends on the angle(s) of the viewing pyramid. So,
if the dot product is smaller than -0.3, then the face is surely
invisible. Similarly, those faces where the dot product is greater than
0.3, are surely visible. Now there's three classes of faces:
1) invisible
2) visible
3) suspicious
So now I culled a part of the faces; less faces than I'd cull if I were
using the dot product sign check only, but these faces are at least surely
invisible.
Now I mark those vertices which belong to visible faces, and translate them
and project them to screen space. Not all vertices, but only those which
belong to visible polys.
Now comes Level 2.
It's done in screen space, it's the two - multiplication clowkwise/
counterclocwise check, but for the suspicious faces only.
It will cull a great number of polys again :-)
The remaining polys are shaded. When doing Lambertian flat shading, the dot
product of the lightsource vector and the surface normal can be done in
object space - it's cheaper to transform the lightsource vector to
object space and calculate the dotp there. The same technique applies to
other shading models including Phong 'emulation' with environment maps. (As
I know this was first done by Nix, correct me if I'm wrong.) So I don't
rotate vertex normals either. Just taking the angle between the
back-transformed eye vector and the vertex normal. Actually, in my last
implementation the vertex normals are stored in spherical coord system, the
surface normals in Cartesian.
Calculation requirements for each object:
1 back-transformation of the camera vector (this needs to be done only
once per object in each frame); you may exploit that the inverse of an
ortho-normalized matrix equals its transponent (swapped rows & columns);
an ortho-normalized matrix is a matrix whose determinant is exactly 1 and the
dot product of its columns (pair-by-pair) is zero. All 3*3 transformation
matrices are ortho-normalized.
1 dot product per face (3 muls);
1 transformation per visible vertex (6 or 9 mul + 2 mul + 1 div);
2 muls per suspicious face; + shading each really visible poly.
If you need the implementation of this technique in a form of a Watcom C
source with one assembly routine (the texture poly routine) just drop me a
mail. ('Benchmark': With not-so optimized C code (FPU transformations)
and a (slow :-) poly routine written in assembly a 660 faces object is
happily spinning in 320*200 on a DX2/66).
* Backface culling *
(the better methods)
I was statisfied with myself to find this technique; and I posted it to
comp.sys.ibm.pc.demos; and the day after I received a mail which ruined
my enthusiasm. As always, there was a better algorithm. Here it is.
Now comes another backface culling method by Chris Babcock -
cbabcock@nando.net. (Greetings Chris!)
It is entirely done in object space. It doesn't use the direction of the
eye vector, just its location. (On the contrary, the previous used its
direction only.) So after back-transforming the camera loction to
object space we check if the eye point is behind or not a face. If so, it's
invisible. The math beyond this: a point's coordinates substituted to the
equation of a plane will give the signed distance from the plane. So
this reqiures pre-calculating all the faces' equations. A plane's equation:
a*X + b*Y + c*Z + d = 0 where (a,b,c) is the plane normal, d is a constant
(depends on plane location). Every (X,Y,Z) point substituted to the
aX+bY+cZ+d expression gives the distance from the plane. Those (X,Y,Z)
triads where the expression gives zero, belong to the plane. Here's the
original version:
Just transform the eye LOCATION into object space and plug into plane
equation.
aX + bY + cZ = d
where
(X,Y,Z) = eye location in object space
(a,b,c) = plane normal in object space
Solve d by plugging in one of the vertices of the polygon and store it
with database (precalc like a,b,c).
To determine visibility, solve aX + bY + cZ with the eye location and
compare it to d (if
Finally, the last method, suggested by Luca / G&G Demoware. This works with
the eye location too. Generally, with the eye-direction-only technique the
problem is that the eye direction vector mathematically is not a
constant in the whole viewing pyramid. (If you look towards the upper-left
corner, you gaze to a different direction if you'd look towards the
center of the screen.) So for evey poly we must determine the exact eye
vector; in this case the sign of the dot product will correctly mark the
visibility. So we take a point of the polygon and substract the eye location
from it; the result is the eye->poly vector; now perform the dot product
with the plane normal, and check its sign. The only problem is that which
point of the polygon should be the endpoint of the eye->poly vector. It
might be the center of the face; since it doesn't have to be rotated, it only
increases the size of the data structure. Or it can be any of the
vertices. Well, to tell the truth, it has the very same error as the
eye-direction-only check has; but here it appears much more rare because the
angle between the the eye and the various vertices of one polygon is
much smaller than the angle of the field of view.
The morals of this article:
1) It's profitable to do backface culling in object space. In this case
you don't have to transform and project those vertices which belong to
invisible faces.
2) For shading you don't have to rotate the normal vectors at all.
I wouldn't have dared to publicate such a great speedup technique if I
wouldn't have a working version of it; okey, you might say, then why not to
include it as an example? Well, I admit, I ran outta time so I didn't
have time to make it facy enuf for publication. Of course, if you need
it, I will send it to you, just write to me:
Ervin / AbaddoN
Ervin Toth
48/a, Kiss Janos street
1126 Budapest
HUNGARY
+36-1-201-9563
ervin@sch.bme.hu