3D Coding TAT - Group Vertex Clipping
Like most subjects in this rapidly growing document clipping too can be gifted with a 'group' approach. In the best case it can totally remove ALL need for polygon testing and clipping and in the worst case it can add a multiply, divide and a few other simple instructions and in the intermediate cases it can reduce the clipping tests, so there are far more gains than losses.
The basic idea (like most others) is simple. A little amount of preparation is required which only needs to be done once, probably when the 3d model is created.
First create either a bounding sphere or a bounding rectangle around an object's origin. This is just a length which is the radius of the vertex which is furthest from the origin. This is very easy to work out but requires 3 multiplys and a SQRT (square-root) for every vertex which makes up the object. This ONLY needs to be done ONCE, unless your vertices move.
The below pseudo-code assumes every vertex in an object is defined from its origin (0,0,0).
e.g.
reach = 0
for n = 1 to Number_Of_Vertices
X = vertex[n].X
Y = vertex[n].Y
Z = vertex[n].Z
radius = SQRT (X*X + Y*Y + Z*Z)
if radius > reach then reach = radius
next n
Now the variable 'reach' is the longest 3d vertex length from the object's origin. So no matter what sequence of rotations is done on these vertices we know that none can extend further then the 'reach' value. You can think of it as the radius of a sphere which encloses all the vertices in it.
If you don't like the thought of using 3 multiplies and a SQRT then try using the longest length of each vertex along the X, Y and Z axises, then times it by SQRT(3) = 1.732050808 this radius should then be big enough to enclosed the entire vertices. This method is guaranteed to enclosed all the vertices but it is NOT the true greatest length (like the SQRT method) and in many cases it will be bigger than the proper length. e.g.
reach = 0
for n = 1 to Number_Of_Vertices
X = ABS ( vertex[n].X )
Y = ABS ( vertex[n].Y )
Z = ABS ( vertex[n].Z )
radius = X
if Y > radius then radius = Y
if Z > radius then radius = Z
if radius > reach then reach = radius
next n
reach = reach * SQRT(3)
= reach * 1.732050808
If we use this 'reach' value as the radius of a 2d circle and if we use the object origin's projected 2d screen position then we can employ it to check whether any, all or none of the object's vertices need to be clipped. In the below diagram the top of this bounding circle crosses the top clipping edge which indicates that all the vertices must be tested & possibly clipped. If the entire circle was within the clipping rectangle then we would not need to test or clip a single polygon, line or vertex!
e.g.
xxxx
xx xx
left x x right
x x
³ x x ³
³ x origin x ³
---------Å--x------------x-------------Å------------ top
³ x + x ³
³ x / x ³
³ x / reach x ³
³ x / x ³
³ x x ³
³ xx xx ³
³ xxxx ³
³ ³
---------Å-----------------------------Å------------ bottom
³ ³
³ ³
³ ³
At first it may seem difficult to test a circle against the clipping rectangle because of the curve, but in fact it is similar to checking a square box. The circle can be fitted inside a box and we only need to check the X and Y extremes of the circle where:
left = X - radius
right = X + radius
top = Y - radius
bottom = Y + radius
Remember we are not interesting in clipping the circle we only need to know it any part of it is outside the clipping area.
e.g.
xxxxxxxxxxxxxxxxxxxxxxxx
x x
³ x ³ x
³ x ³ x
---------Å---------------x-------------Å--------x---- top
³ x ³ x
³ x<- reach ->+ ³ x
³ x ³ x
³ x ³ x
³ x ³ x
³ x ³ x
³ xxxxxxxxxxxxxxxxxxxxxxxx
³ ³
---------Å-----------------------------Å------------ bottom
³ ³
³ ³
³ ³
left right
In the above diagram the bounding box crosses the top and right clipping edge. It means that again some vertices could possibly need clipping.
1: The good news
This bounding box/circle/sphere is useful in many ways.
1. It can reject entire objects without the need to rotate, project, backface cull or create outcode for each and every vertex (which is REALLY good news).
2. Using it as a sphere means it can be applied to the Z-clipping plane(s) as well. (Remember 'reach' is a true 3d radius so this ONE length can be used in 2d or 3d clipping.)
3. As a bonus if we create 1 outcode for the bounding box/circle/sphere then we can work out what clipping tests need to be done and what tests DO NOT (double) (e.g. if the bounding shape only crossed the bottom edge then we only need to test and clip that edge on EVERY vertex/line/polygon!).
4. The true 'reach' length could also be used for collision detection purposes (sphere to sphere). Although it will not be as correct as a proper polygon-to-polygon test it will certainly be much, much quicker.
2: The bad news
Well, there isn't much of it.
1. Some calculation and extra testing is performed ONCE per object. The most costly part is that the 'reach' radius value which should be scaled up or down depending on the object's origin distance from the view-point.
2. Extra set-up calculation is needed, for the SQRT bit. This is easy to do even in assembler and it doesn't have to be fast so any method can be used. Or you could use the previously mentioned longest axis length * SQRT(3).