3D Coding TAT - Polygon Drawing & Clipping
This has to be one of the biggest hurdles when writing 3d code for the first (or the 100th) time. Almost all books just describe polygons as "a connected series of lines" and say that clipped line algorithms must be used to scan-convert the polygon edges.
I will describe CONVEX polygons coz they're easy and most important of all, FAST! Some of my first polygon drawing code was done on the Amiga, and I was amazed to recently discover that the way I devised my first polygon filler is still being used today - so I must have got something right all almost a decade ago. The method is: Find the topmost vertex of a polygon and then scan the right side forwards through the vertex list and the left side backwards. 99% of polygons are defined in a clockwise order, the other 1% are done in an anti-clockwise order just to be different.
In this section I will assume that ALL polygons are clockwize in order and that anti-clockwise polygons are consider as hidden (facing away from the view-plane).
Imagine a 4 sided polygon with 4 vertices (hmmmm... there's a connect here somewhere). The vertices are labeled as a, b, c, d. A polygon defined in a clockwize order could have a data structure something like:
Edge number Start vertex End vertex
---------------- -------------- ------------
0 a b
1 b c
2 c d
3 d a
So for each of the 4 sides we have a starting vertex and an ending vertex. But this vertex list could be defined like this instead:
a b c d a <--- vertex list
Because one polygon side begins where the last ends the above list can be used to reduce memory usage.
Start vertex = Vertexlist[n]
End vertex = VertexList[n+1]
Note how I repeated the 1st vertex at the end to avoid doing a wrap-around check (every little helps).
Å-------> x b
³ / \
³ / \ |
³ __ / __\|
³ /| \
³ / | \c
³ / /
v a / /
| /
y | /
| | /
/|\ |/__
/ | \ /
| /
| /
| /
| /
|/
d
In the above diagram vertex b is the topmost point of the polygon. What we want to do is scan the left and the right edges of it into 2 coordinate lists ready for filling. This means that all the left X coordinates needs to go into one list and all the right X coordinates needs to go into a 2nd list. We can then draw a series of horizontal lines between the left/right edges. One thing of interest to note about clockwise polygons is the fact that the edges can quickly be sorted into left or right types just by looking at their Y lengths (the difference between the start and end Y coords). A zero Y length indicates a flat top or bottom polygon in this case examining the X length will determine which.
e.g.
we have 2 vertices (x1,y1) and (x2,y2)
YL = y2 - y1
if YL > 0 then Right_Edge_Of_Polygon
if YL < 0 then Left_Edge_Of_Polygon
otherwise ...
XL = x2 - x1
if XL > 0 then Top_Of_Polygon
if XL < 0 then Bottom_Of_Polygon
else if XL = 0 then ....
ignore this vertex as it is has the same
X and Y coordinates the next vertex.
(x1=x2 and y1=y2).
This is a very useful thing to know as it can make clipping much easier and hopefully quicker. For example if a part of the right edge is beyond the left clipping limit then we know that so is the left edge, so both can be ignored and not drawn. The same fact also works with the left edge, if that is outside the right clipping limit then it means that so is the right edge and again it can be ignored.
1: Convex Half-Space Clipping
Given a convex polygon we know that none of its interior angles can be more than 2*pi (180°), which is a straight line. There are plenty of definitions of what a CONVEX polygon is in any good maths/geometry book. I found a nice one a month or two ago which inspired some new tricks when clipping and drawing a polygon. It went something like this:
A convex polygon is the area of the overlapping regions of all the half-spaces created by its edges.
Put another way, moving round a polygon in a clockwise order take a single edge (the line between two vertices). Now imagine this edge as being on an infinite line (or hyper-line). The hyper-line divides space into two halves, two half-spaces. Now for a CONVEX polygon ALL of its vertices lie on ONE side of this hyper-line. This it true for ALL of its edges.
If any vertices lie on BOTH sides of a hyper-line then the polygon is CONCAVE (and they are much harder to code, so I will only stick with CONCAVE ones).
e.g. 1st half-space
³<---- a side ----->³
.................o-----------------o............ an infinite
/ \ plane
/ o
/ the polygon's /
/ /
o interior /
\ / 2nd half-space
\ /
\ /
o_______________o
The above mathematical description is very useful to know because we know that if we moved around the polygon in a clockwise direction with the centre area of the polygon to our right, then NO edge or vertex can be on the right of current edge.
left right
³ ³
a ³ ³
---e-a---Å-----------------------------Å------------ top
e a ³ ³
e a ³ ³
e a³ clipping ³
e a <-- TOP ³
e ³a view-screen ³
d ³ a ³
d ³ b ³
d ³ b ³
d---------Åb----------------------------Å------------ bottom
d b ³
d b³ ³
cccccb ³ ³
Imagine the above 5 sided polygon with a,b,c,d,e representing each side. Given side a we know it's a downwards pointing slope because we can tell by its start and ending Y coordinates. This means it is part of the right edge of the polygon. As it must be clipped against the left boundary edge we have also found the top-most clipped Y coordinates at the same time. If we follow the polygon down to side b, then it too needs clipping, against the bottom edge AND the left edge. At this stage we can fill the entire polygon without having to deal with any other sides because we know that all the vertices (and so sides) are on the same half-space (side) as the polygon side b plane.
If side b had not been outside the left edge then we would need to check side c and so on. Simply crossing the bottom clipping edge is NOT enough to indicate that the rest of the polygon is clipped off screen.
left right
e.g.
³ ³
³ ³
---------Å-----------------------------Å------------ top
³ ³
ddddddda ³
c ³ a ³
c³ a ³
c a ³
³c a ³
³ c b ³
small gap ----> c b ³
---------Å---c----b--------------------Å------------ bottom
³ c b ³
³ cb ³
³ ³
In the above diagram side b again crosses the bottom clipping edge but does not cross the left edge, which means another side could cut across and leave a small gap in the bottom left corner (see above). If the side c was flat or simply crossed the left edge then we would have enough to draw the polygon.
I have not had chance to research all the possible combinations for a 3 of 4 sided polygon, but it may be worthwhile seeing if a tokenized table could be built to deal with all the possible cases. The outcodes may be a very handy way to describe each vertex or maybe a left/right flag system could be included aswell. It would be worth investigating triangles in detail too as their interior angles are never bigger than 180 degrees so there may be a few more tricks to find...
If you are having trouble with this then take a single side of a polygon and extend it in both directions to infinity. We already know that ALL of a vertices must lie on OR on one side of this infinite line (the same half-space). I believe I 'might' be one of the first people to make the connection between the half-space and clipping or at least one of the first to describe it in a doc! Or perhaps some other more knowledgable programmers have already discovered this and are keeping quiet. Very protective some programmers eh? Maybe they are so reluctant to share because they fear some young whipper-snapper coder will come along and write faster code than theirs (sad ain't it?).
2: SUTHERLAND-HODGMAN Algorithm
This is yet another well known algorithm which I have a brief knowledge of. I believe it works by clipping the entire polygon against one plane at a time rather than against a clipping rectangle or cube (I could be wrong given the sparse information I have).
Basically we walk around the polygon, 1 side at a time and create a new vertex for every clipped line (which crosses the plane). When we have two new vertices or one old and one new vertex we create a new side to join them.
NOTE: It is possible that one or more vertices lie exactly ON the clipping plane in which case no new vertices need be created. So remember to include the equals sign in your compares!
a
o--------------------o inside
f / \
/ our new polygon \ b
-----------*--------------------------*-------- clipping plane
/ P Q \
/ \
o this will be clipped o outside
\ /
\ /
e \ / c
o-----------------------o
d
In the above diagram a 6 sided polygon (a,b,c,d,e,f) is badly drawn. Starting at side a, we keep the entire side as both end-point are inside the clipping half-space. Now we come to side b, it crosses the clipping-plane so we create a new vertex Q which is the intercept point on the clipping-plane. Now we ignore all the other sides which do not cross back through the clipping-plane (c,d and e) until we come to side f. This crosses back into the 'inside' so we find the intercept point P and create a new vertex. Now we connect the vertices Q and P together to make a new side so we end up with the following polygon:
a
o--------------------o inside
f / \
/ \ b
-----------*--------------------------*-------- clipping plane
P created side Q
This new polygon is then tested and clipped against the other 3 or 5 clipping-planes. At the end we have a one of the following situations:
1. a totally unclipped polygon (ACCEPTED)
2. a partially clipped polygon (CLIPPED)
3. a totally clipped polygon (REJECTED)
The outcode technique can be extended to 6 planes so that a polygon or line can be clipped within a 3d cube rather than just a 2d rectangle (4 planes).
I can remember a series of articles by Jeff Lawson in ST WORLD (remember that?) and he hinted at a faster way to clip polygons developed in Canada, but I haven't seen or heard anything about it so maybe it was pure hype or someone was pulling Mr. Lawson's leg.
3: A small improvement ?
If we find a side which can be accepted (totally inside a clipping-plane) then we can work backwards as well as forwards from it. In the above examples we start at side a then clipped side b. We could then work backwards from side a, clip side f and define a new side between P and Q. This means we didn't have to search 3 sides (c,d and e).
But when when no sides are totally outside (only 2 are intercept) then it would probably work out the same with no real saving, just a little more code.
4: Recycling 3-Section Lines
I did mention elsewhere that it should be easy to reuse the edge slopes between two neighbouring polygons. This would save having to perform the slope calculations again, it can also halve the number of line clipping operations too. As drawing polygons is an extension to drawing lines it has some similar problems, but also some new ones. For example a line might be entirely outside the clipping region and so can be rejected but the same is not always true for a polygon edge. The line could be one of the polygon's many edges and yet the rest of the polygon could be inside the clipping region. So it is clear that we can not simply reject lines.
-----------¿
³ A
o----*----o
inside / ³ \ Outside
/ ³ \
/ ³ \
o--------*--------o
³ B
------------
In the above diagram we have half of a polygon outside the clipping region and half inside. The line segment A..B is outside the region so could be rejected but the most of the polygon is still inside. If we have another polygon which shared the A..B line segment then it could be hidden (back-face culled), be completely outside the clipping region or also have part of it within the region like the above polygon.
If we think of a polygon in terms of a finite number of horizontal scan lines (like all bitmaps tend to be) and consider all the possible line clipping operations in a horizontal rectangle type way then it turns out that a line can have 0 to 5 sections. First think about Y-clipping (above & below the clipping region) this can break a line into a maximum of 3 sections.
o above
\ A
--------------\---------------------
\
\ B inside
\
------------------\-----------------
\ C below
o
And so does the X-axis boundaries.
left inside right
³ ³
A ³ ³
o--- ³ ³
--- ³ ³
--* ³
³--- B ³
³ --- ³
³ --- ³
³ --- ³
³ ---³ C
³ *--
³ ³ ---o
Combining both cases we have 5 possible line sections. This is the worst possible case of clipping where the line must be clipped against all 4 boundary edges.
(x1,y1) LEFT RIGHT SECTION
A** ³ ³ A 1
A** ³ ³ A
TOP ------------B**--Å--------------Å----------------- B 2
B** ³ B
³C** ³ C 3
³ C** ³ C
³ C** ³ C
³ C** ³ C
³ C** C
³ ³D** D 4
³ ³ D** D
BOTTOM -----------------Å--------------Å------D**-------- D
³ ³ E** E 5
³ ³ E** E
³ ³ (x2,y2)
Now consider all the possible polygons which could utilise the above line slope as one of its edges. This turns out to be just two, a polygon can be on one side of the line or the other. (In the left half-space OR the right half-space).
e.g.
...00000011111111... 0 = polygon left of line
...00000000111111... 1 = polygon right of line
...00000000001111...
...00000000000011...
We can make things easier by ignoring the A and E cases where a line is above or below our clipping region, so we have just 3 possible line sections like this:
LEFT RIGHT SECTION
³ ³
³ ³
TOP ------------B**--Å--------------Å----------------- B 1
B** ³ B
³C** ³ C 2
³ C** ³ C
³ C** ³ C
³ C** ³ C
³ C** C
³ ³D** D 3
³ ³ D** D
BOTTOM -----------------Å--------------Å------D**-------- D
³ ³
³ ³
The reason why we can discard those two cases is because no matter what side a polygon is on the A & E sections it will never be seen as we are drawing horizontal scan lines which are parallel to the top and bottom clipping region. This Y-axis 'banding' may be a good place to start for a general polygon clipping and drawing routine. It would reject plenty of above and below edges and this would make the rest of the code much easier and quicker.
Now that we have just 3 line sections how can they be reused for two connected polygons and how can we clip them?
Let's first think about a polygon to the right of the line and examine how the line sections are used (taking into consideration the B and D clipped sections).
LEFT RIGHT SECTION DRAWN
³ ³
TOP -------------..--cccccccccccccccÅ----- B left clip
..ccccccccccccccc³ B left clip
³cccccccccccccc³ C c
³ ccccccccccc³ C c
³ cccccccc³ C c
³ ccccc³ C c
³ cc³ C c
³ ³.. D
³ ³ .. D
BOTTOM -----------------Å--------------Å----.. D
³ ³
Please note: the line section B was replaced with 'left' edge of the clipping region and the D line section was completely ignored.
Okay, let's look at the other polygon case, one on the left side of the line.
LEFT RIGHT SECTION DRAWN
³ ³
³ ³
TOP --------------..-Å--------------Å----- B
.. ³ B
³ccc ³ C c
³cccccc ³ C c
³ccccccccc ³ C c
³cccccccccccc ³ C c
³cccccccccccccc³ C c
³cccccccccccccc.. D right clip
³cccccccccccccc³ .. D right clip
BOTTOM -----------------Å--------------Å----- D right clip
³ ³
Now the situation has reversed concerning the B and D line sections. This time B is ignored and D is replaced by the right clipping limit.
There is something which I haven't mentioned yet, you may need to flag a line as either going upwards or downwards. This vertical direction would be used to determine what side a polygon is on (the left or the right). As we have seen in the last two diagrams the left (B) and the right (D) line sections are affected by the side on which the polygon is. I would suggest forcing ALL your edge slopes to be in a single direction (upwards or downwards) and use a single flag to indicate that the slope has been flipped.
5: Recycled Edge Coordinates
The edge recycling can be extended further to include texture-space coordinates and shading coordinates as well. Both of these share the same 2 vertices, the same slope, the same slope length and hopefully the same perspective values. As a number of division are needed for each slope (sometimes even each scan line) this can add up to a large saving in CPU time.
An idea I had a while ago was for texture mapping to help reduce the number of memory accesses when building up the slope value lists. For each slope do just ONE interpolation along it instead of the normal texture-space U, V and shading values. This one value for each scan line can be thought of as a fraction or scale percentage of the entire line with half way being equal to 0.5 or 1/2. The scale for the entire line would be 1.0 or some other constant value for every line.
e.g. 0%
o
50% / \ 25%
100% o \
\ 50%
\
\ 75%
\
o 100%
In the above diagram we have 2 slopes which could be part of a single polygon or parts of two seperate polygons. The percentage % value indicates how far along the line slope we are in relation to the entire line.
Now when you come to texture map you could take this single fraction value and index for the correct coord table. If we were using a 64x64 texture bitmap these coord tables could look like this:
e.g. top right bottom left
fraction edge edge edge edge
-------- ----- ----- ------- ------
0% (0,0) (0,0) (63,63) (0,63)
25% (16,0) (0,16) (48,63) (0,48)
50% (32,0) (0,32) (32,63) (0,32)
75% (48,0) (0,48) (16,63) (0,16)
100% (63,0) (0,63) (0,63) (0,16)
Where the texture bitmap would be:
(0,0) top (63,0)
Ú--------¿
³ ³
³ bitmap ³
left ³ ³ right
³ ³
À---------
(0,63) bottom (63,63)
I'm not sure how useful this would be. It might even be slower than scan converting the slope each time due to the slow speed of most memory compared to the fast CPU + cache speed. The advantage is that these coord table could be non-linear and perhaps translate texture space edges in a weird way without too much CPU time and maybe even animated for water or lava effects.
But there is a problem, what happens when you need to clip a textured polygon? Maybe this isn't such a great idea at the moment.
6: Z-Cropping Polygons
This is a very neglected subject in ALL of the books I have read. It is basically clipping polygons that intersect the Z view-plane (some use the Y coord. as view-plane). I know that most people will call it Z-Clipping or View-Plane-Clipping but I will call it Z-Cropping because you need to create more vertices and it must be down in 3d, unlike the normal screen clipping, which happens in 2d (after projection/perspective). I can remember reading an article by Jeff Lawson who said that it was best to try and prevent polygons crossing the view-plane otherwise you need to create new vertices etc.
Okay, enough waffle.
Like 2d (X,Y) clipping 3d Z-Cropping MUST be done on a line-by-line (or edge-by-edge) basis. You can NOT simply clip each vertex because even though a number of lines might use it as an end point the point of intersection is unique for each unique line. Also Z-Cropping needs to be performed BEFORE any perspective/projection takes place and worst of all you need to peform the intersection calculations twice for each line! (Once for the X-axis and once for the Y-axis.)
To perform this 3d Z-cropping we can break it down into two 2d clips. We want to eventually find the values of a point (xi,yi,zi) which is the point on the projection-plane where the line (X1,Y1,Z1) to (X2,Y2,Z2) intersects it. We know that The (zi) value will just be the projection-plane Z co-ordinate because like most other people keeping it parallel to the X and Y axises makes the maths much easier and quicker. So it's just the (xi) and (yi) values that we need to find.
Let's find the (xi) one first.
PLAN VIEW
(X2,Z2)
o
/.
/ .
(xi,zi) / .
projection-plane ---------*--------------
/ . ^
Z / .. ³ clip this
^ o....... v
³ (X1,Z1)
Å--->X
This is identical to a normal 2d intersection and the two formulas to perform this are:
Pz = Projection Plane Z-coordinate
(Pz-Z1) * (X2-X1)
xi = ------------------- + X1
(Z2 - Z1)
zi = Pz
And a similar thing can be done to find the (yi) value.
LEFT SIDE VIEW
projection
plane
³ (Z1,Y1)
³ o
³ /.
³ / .
³ / .
³/ .
* .
Y /³ .
^ / ³<--->
³ o clip this
Z<---Å (Z2,Y2)
The formulas to find (yi) are:
Pz = Projection Plane Z-coordinate
(Pz-Z1) * (Y2-Y1)
yi = ------------------- + Y1
(Z2 - Z1)
zi = Pz
So now we have the new 3d vertex (xi,yi,zi) which lies exactly ON the projection-plane. This must be repeated for all of the edges of all the polygons which intersection the projection-plane. And this means some polygons will have an extra vertex (and side) to them, some will have the same number and some will have fewer or none at all.
After this Z-Cropping has taken place you still need to project these 3d vertices onto a 2d view-screen. All this extra work chews up more CPU time so any ways to reduce it is a very welcome vistor. The 'outcode' method of creating bit fields to indicate whether a vertex is beyond the clipping region in a number of axises can be extended from 2-d to 3-d. So instead of clipping to a rectangle we are clipping to a cube like volume. The outcodes are very good at rejecting or accepting polygons and telling us what kind of clipping needs to be done.
The actual Z-Cropping calculations can be done with 1 divide and 2 multiplies simply by keeping the (Pz-Z1)/(Z2-Z1) value, which is the same in both stages.
The Z-Cropping must be done in 3-d (X,Y,Z) but there are some other vital things to remember.
1. It must be done BEFORE the projection/perspective calculations.
2. Every line which shares the same end vertex MUST be Z-cropped independently as it has a unique point of intersection on the view-plane.
3. EACH polygon which uses a shared vertex must have its OWN new Z-Cropped vertex (because of the unique point of intersection on the Z view-plane). This means a cube could have 10 vertices instead of the normal 8, this happens when a single corner vertex is on the opposite side of the view-plane to the rest of the cube. So 3 faces of the cube will have 5 sided polygons instead of the normal 4.
4. The projection/perspective calculations need to be done on these Z-Cropped vertices.
5. The normal 2d clipping then needs to be done on these new vertices.
7: Hidden Surfaces & Drawing
Today after glancing through some very, very old articles about 3d graphics I made a previously overlooked connection between hidden surface rejection (back-face culling) and scan converting polygons. I know elsewhere I have stated that
"Sometimes it is very easy to fall into the low-level trap,
(not seeing the forest for the trees) this is where I believe a
more global, group approach can give the best gains."
Pity that I didn't follow my own advice, until now.
Okay, imagine that you have already found the top-most vertex of a polygon and now wish to determine if it is anti-clockwise (hidden) or not (clockwise). In most cases this test will be easy to perform using the X coordinate of the vertices.
CLOCKWISE CLOCKWISE
B B------------C
/ \ /
/ \ / POLYGON
/ \ /
A POLY \ /
C A
In both of the above examples it is clear that polygon is clockwise from looking at their A,B,C vertices. Likewise the below examples are clockwise too.
CLOCKWISE CLOCKWISE CLOCKWISE
A-----------B B A----B--------C
\ /|
\ / |
\ / |
\ / |
C A |
C
In ALL of the above examples the following test will accept A,B,C (clockwise) polygons but would reject C,B,A polygons:
IF (Ax <= Bx) AND (Cx => Bx) THEN clockwise ... (visible)
ELSE anti-clockwise... (hidden)
But if (Ax=Bx) and (Cx=Bx) then we have a problem, the polygon is a straight, vertical line it is impossible to know whether it is clockwise or anti-clockwise. It is probably best to reject this type of polygon rather than using drawing a vertical line.
We just compare the X co-ordinate of the A, B and C points. All of the above examples can be validated with a few compare instructions. But there is a trap which I originally fell into when writting my first polygon filler.
CLOCKWISE CLOCKWISE
--B B--
-- / \ --
-- / \ --
-- / \ --
-- C A --
A --C
This time the two vertices on either side of the top-most vertex (B) both lie on the SAME side of vertex B, this can not be handled by just using compare instructions. You must use the slopes of line A..B and C..B to discover which side one is on in relation to the other.
HIDDEN HIDDEN
--B B--
-- / \ --
-- / \ --
-- / \ --
-- A C --
C --A
These same-side cases can be tested for using this check:
(By-Ay) (Cy-Ay)
IF --------- < --------- then clockwise
(Ax-Bx) (Ax-Cx)
or, you can use:
IF (By-Ay)*(Ax-Cx) < (Cy-Ay)*(Ax-Bx) then clockwise
or,
IF (By-Ay)*(Cx-Ax) > (Cy-Ay)*(Bx-Ax) then clockwise
It basically compares one line gradient (slope) against the other in a sort of angle-type way.
SO WHAT ?
Well this hidden surface test method uses two slopes of each polygon which (here it comes...) can be combined with the normal polygon drawing AND the edge recycling (if used) to save divisions. You need to handle vertical or horizontal slopes seperately to avoid any divide-by-zero problems. You could even break off into custom polygon code for those slopes this would speed up the special cases and possibly clipping could be integrated into each case. So the slope (gradient) of a line is a vital piece of info. to know about. It can be used to draw polygons, locate the correct clipping boundary edge and be used to test for hidden polygon faces.
8: Half-Space Seams & Convex Culling
As we have already seen convex plane polygons have some very useful attributes and very well known characteristics. One of the main reasons for choosing convex rather than concave polygons is mainly due to the fact that the drawing process (scan converting) is far easier for convex ones because no matter where you cross section across them they only ever have 2 edges (usually the left and right). This means that there is only a single solid line to draw per scan line, whereas a concave can have any number.
A CONCAVE POLYGON
o
o / \
---> /x\ /xxx\ <-------- 2 line spans
/ \ / \
/ o \
/ \
o-----------------o
After looking through some of my old scribbles in a dusty folder I have only just thought about a new way to cull convex polygons which could prove worthwhile. I can remember writing it down about 4 or so years ago and then forgetting all about it, until now. Originally the note was done without any real idea how or if the technique would work. In light of reading about the half-space description of a convex polygon another piece of the jigsaw has been added.
1. Remember that a convex polygon has NO interior angle which is bigger than 180 degrees.
2. For each polygon edge ALL of its vertices must lie in the SAME half-space.
Well the above rules really say the same thing. The important thing to note is that 180 degree is a straight line and the two half-spaces are also seperated by a straight line.
e.g. 1st half-space
.................o-----------------o............ an infinite
/ p q \ plane or line
/ o B
/ the polygon's /
/ /
A o interior /
\ / 2nd half-space
\ /
\ /
o_______________o
If we take the two vertices A and B and move them so that angles p and q are at their maximum (180 degrees) we have the following:
A B
......o----------o-----------------o---o........ an infinite
\ p q / plane or line
\ /
\ the polygon's /
\ /
\ interior /
\ / 2nd half-space
\ /
\ /
o_______________o
By choosing any polygon side at random and extending it to infinity in both directions we know that ALL of its vertices (and so sides) all lie on one side of it.
YEAH, BUT WHAT ABOUT THE CLIPPING ?
Suppose we had a polygon and it was entirely outside the clipping region (but we didn't know this yet) and we have just 2 of its vertices that make up a single side (A..B).
e.g. ³ ³ B
³ above ³ o
³ ³ / \
³ ³ / \
³ ³ / \
------------------------Å-------------Å-------/-------\---------
³ ³ / poly o
³ view port ³ / /
³ or ³ / /
³ clipping ³ o--------o
left ³ region ³ A right
³ ³
------------------------Å-------------Å-------------------------
³ ³
³ below ³
³ ³
³ ³
The polygon side A..B can be extended to be a hyper-line which divides space into two half-spaces. We can work out which half-space the polygon is in by standing on vertex A, facing B and looking to our right. This will always give us the interior of the polygon otherwise it is not convex!
And now the good bit.
If this hyper-line doesn't cross into the clipping region then nor does one of its two half-spaces.
e.g. .
. <- hyper-line
³ ³ B .
³ above ³ o
³ ³ / \
³ ³ / \
³ ³ / \
------------------------Å-------------Å-------/-------\---------
³ ³ / poly o
³ view port ³ / /
³ or ³ / /
³ clipping ³ A .o--------o
left ³ region ³ . right
³ ³ .
------------------------Å-------------Å.------------------------
³ .
³ below . <- hyper-line
³ . ³
³ . ³
So if the hyper-line doesn't cut through the clipping region then we can reject one half-space and if we can do that then we can also reject the entire polygon and all of it's vertices which lie in that particular half-space.
In effect we can reject the entire polygon just by checking one of its sides without the need for outcodes or a safety net.
THE BAD NEWS
But a polygon side does not (and can not) be the full length of a hyper-line, so it is possible that the hyper-line might cut across the clipping region but the entire polygon is still outside it.
e.g. .
. <- hyper-line
³ ³ B .
³ above ³ o
³ ³ / \
³ ³ / \
³ ³ / \
------------------------Å-------------Å-----/-------\-----------
³ ³ / poly o C
³ view port ³ / /
³ or ³ / /
³ clipping ³ .o--------o
left ³ region ³. A D
³ .
------------------------Å------------.Å-------------------------
³ . ³
³ below . <---- hyper-line
³ . ³
³ . ³
In the above example the side A..B hyper-line does cross the clipping region but the polygon is still outside. In this case the side D..A (the closing line of the polygon) could be checked.