2D clipping.

"Don't discount flying pigs before
you have good air defense."
 jvh@clinet.fi
Screen boundaries clipping.

Throughout the last chapter we've assumed that primitives we were rendering
are completely within the screen boundaries. This is something we can't
really guarantee. The worst thing if we would try using those functions
to render an element outside the screen, they won't much complain and
would most likely try accessing memory outside the colourmap's allocated
space. And I guess: segmentation fault, core dumped is hardly most
graceful way to exit a program. So we don't have another choice but
to guarantee rendering algorithms that the element passed is indeed
inside the screen.
A dot.

Clipping looks trivial in case of a dot, we just have to add few
comparisons checking if the coordinates are in the screen range and
proceed only if that is the case:
void G_dot(int x,int y,unsigned char colour)
{
if( (x>=0)&&(x=0)&&(y ym = y2  
x2xm x2x1 x2x1
but this method involves multiplications and divisions, so
beholding to our tradition let's try to avoid it. The alternative
method is using binary search:
A(3,1)
* 
\ 
(1,3)* 
o I(0,?)
 \
 * B(1,5)

X=0
pic 4.4
Let's see how it works on a simple example: suppose we have
to clip a line A(3,1)B(1,5) by an edge X=0 , we have to
find Y of the intersection point. let's find midpoint of
the line AB:
Ax+Bx Ay+By
midx= midy=
2 2
midx=(3+1)/2=1 midy=(1+5)/2=3
Now, let's see where the boundary lies with respect to the midpoint?
It is still to the right of it, so of two lines AMidPoint MidPointB,
edge intersects MidPointB. Let's rename MidPoint into A and start
the midpoint search over again:
midx=(1+1)/2=0 midy=(3+5)/2=4
Here, the intersection came precisely onto the edge. So midy is the
Y coordinate of Intersection point we were looking for. It appears
that this method involve a lot of calculations, but they are all
very cheap, just an addition and division by two (which is
actually a 1 bit right shift). Practice shows binary search works
indeed faster then calculation resulting from solving similar
triangles.
When dealing with divisions performed by shits however, one has to be
aware of truncation problems that might arise. Since 1>>1=1 that means
that if we would try to use algorithm described above to clipp (1,y1)(0,y2)
line by X==0 boundary chances are we would loop forever, at each iteration
finding that 1>>1 is still 1. (and O(for ever) is hardly, the time
complexity contributing towards high framerate). As in the code below
this situation should be thought of.
Let's create a function which would perform clipping against
two vertical screen edges: that is C_X_CLIPPING_MIN and C_X_CLIPPING_MAX.
int C_line_x_clipping(int **vertex1,int **vertex2,int dimension)
{
register int i;
register int whereto;
register int *l,*r,*m,*t; /* left right and midle and tmp */
static int g_store0[C_MAX_DIMENSIONS]; /* static stores for clipped vxes */
static int g_store1[C_MAX_DIMENSIONS];
static int g_store2[C_MAX_DIMENSIONS];
static int g_store3[C_MAX_DIMENSIONS];
static int g_store4[C_MAX_DIMENSIONS];
static int g_store5[C_MAX_DIMENSIONS];
int **vmn,**vmx; /* so that *vmn[0] < *vmx[0] */
int swap; /* we coordinates swaped? */
C_2D_clipping=0; /* default no clipping yet */
if((*vertex1)[0]<(*vertex2)[0])
{ swap=0; vmn=vertex1; vmx=vertex2; } /* so that *vmn[0] < *vmx[0] */
else
{ swap=1; vmn=vertex2; vmx=vertex1; }
if(((*vmn)[0]>C_X_CLIPPING_MAX)((*vmx)[0]>1;
whereto=m[0]=C_X_CLIPPING_MAX) /* clipping */
{
HW_copy_int(*vmn,l=g_store3,dimension); /* copying old vertixes */
HW_copy_int(*vmx,m=g_store4,dimension);
r=g_store5; /* let middle be here */
whereto=0;
while(m[0]!=C_X_CLIPPING_MAX)
{
if(whereto==1) { t=l; l=m; m=t; }
else { t=r; r=m; m=t; }
for(i=0;i>1;
whereto=m[0] r
  
v v v
++ ++ ++
x,y,z...  x,y,z...  x,y,z... 
++ ++ ++
pic 4.5
This is being done so that at every iteration only pointers to
actual data are moved not the data itself. (The point I am trying to
make: (and I am sure everybody knows that, just a bit of reinforcement)
it's ok to physically copy small amounts of data, but when we have a lot
of it, it is better to move pointers instead)
Let's insert calls to clipping function into the G_line routine:
...
...
v1=vertex1;
v2=vertex2;
if(C_line_x_clipping(&v1,&v2,2)) /* horizontal clipping */
{
if(C_line_y_clipping(&v1,&v2,2)) /* vertical clipping */
{
dx=v2[0]v1[0]; dy=v2[1]v1[1]; /* ranges */
...
...
So, whenever line is completely clipped we wouldn't go any further
in the rasterization function.
A polygon.

Now, remembering that we render polygon by scanning it's edges
using rasterization function pretty much like the one above, we
may think that adding clipping calls into GI_scan would solve our
problem with polygon clipping, unfortunately, it is only half true
(literary half true). Lets consider pictures pic 4.6 and 4.7:
B * B
 *==== I/
/==== *
I*====== /======
/?????? /========
/ ????? /========
A* ?????? A*==========
pic 4.6 pic 4.7
In the cases above edge AB contribute to the left side of the
polygon, clipping present no problem for case on pic 4.7. Clipped
part IB of the edge can be discarded since there's nothing to
form outside the screen. On the other hand in the case on
pic 4.6 we can't simply discard clipped part AI since we would
loose left boundary of all horizontal lines marked "???". The
observation we can make is that polygon, being scanned edge at
a time, may not be clipped against horizontal boundaries but
must be clipped against vertical, this way the code within GI_scan
would look like:
...
...
v1=edges; edges+=skip; v2=edges; /* length ints in each */
if(C_line_y_clipping(&v1,&v2,dimension)) /* vertical clipping */
{
dx=*v2++; dy=*v2++; /* extracting 2D coordinates */
x=*v1++; y=*v1++; /* v2/v1 point remaining dim2 */
...
...
Creating a vertically clipped polygon on the other hand is a bit
more complicated. The problem is that the clipped polygon may
have different from the original one number of edges. let's
consider the situation on the pic 4.8:
/* 3
  / 
5' / 
5***6 * 
/  \ /2''
4*  *1 2 *  
\  / \ 
3***2 *\ 
3' 2'\* 1
pic 4.8 pic 4.9
It can be seen that original polygon has 6 edges which becomes 5
after clipping. Some other polygon pic 4.9 can have 1 more edge
after clipping. It is obvious that we would have to create a
temporary structure to hold the clipped polygon. Now, we know how
to clip a single edge, let's try to find pattern how clipped
edges compose clipped polygon. Let's be considering clipping
against a single boundary, say X==0. it is obvious that if an edge
is completely outside it's vertexes won't be present in the new
polygon. On the other hand if an edge is within the boundary
both points would be present. Any point on the intersection
line would be present too. One more consideration is that each
point in the polygon belong to two edges, so when the edge is
not clipped we may put into the new structure just the second
point assuming that the first one is already taken care of when
we were processing previous edge.
Let's list the patterns:
(1) If edge is not clipped or the second point is clipped put into
new structure just the second point;
(2) When first point is changed or both are changed put both;
(3) When both are outside put none.
Surprisingly enough this algorithm doesn't have to be changed
when we consider simultaneous clipping against two parallel
boundaries:
 **1
/5 \
4'* *2'
/ \
4*   \
   \
****2
3 3' 2''
 
pic 4.10
edge 12 Second point clipped  pattern (1) putting in 2'
edge 23 Both points changed  pattern (2) putting in 2'' and 3'
edge 34 Both points outside  pattern (3) ignoring
edge 45 First point clipped  pattern (2) putting in 4' and 5
edge 51 No clipping  pattern (1) putting in 1
The result is: 2'2''3'4'51 just looking at the picture assures
us that what we got is indeed right. Now finally the purpose of
C_2D_clipping variable being set in C_line_x_clipping must be clear.
It would be set to 1 whenever first or both points were changed,
and would be 0 if none or just second one were changed. Knowing
this all let's write some code:
int C_polygon_x_clipping(register int *from,register int *to,
int dimension,int length
)
{
register int i;
int *v1,*v2,new_lng=0;
int *first_vrtx=to; /* begining of the source */
for(i=0;i
*>
*>
A*  >
II
pic 4.12
By applying perspective transformation we increase the absolute values
of coordinate components depending on inverse of it's distance to the viewer,
so if Z==0 transforms into infinity numbers close to that transform into
something bitsize of numbers stored in computers might not be able to handle,
and no, we can't quite solve it by moving the clipping plane slightly forward,
since there are still those nasty points which are slightly in front of the
viewing plane but already have big absolute value of X or Y. (pic 4.12,
point A). The overflow problem that may result from perspectively transforming
this point is this: positive values may become negative, and if it would
happen to just one point of two offscreen points representing a line we
may actually see this line all across the screen instead of not seeing it
at all.
The conclusion when using perspective transformation, it is better to apply
it to the points we know would produce a valid result. And since what we
ultimately want is to project to the screen we are coming back to the
view volumes since those are exactly sets of points that would be
projected inside the screen. Hence we do need to consider actual viewing
volume for perspective projection.
What the view volume for perspective projection would look like?
The way we modeled this transformation  rays of all visible points
converge in viewer's eye. If we would cast back into space lines connecting
the eye and the screen boundaries, we would obtain the pyramid marking points
from space that would project onto screen edges. what's inside the
pyramid would project inside the screen what's outside  outside the screen.
adding the clipping plane somewhere in front of the viewer we are obtaining the
viewvolume for perspective projection, pic 4.13.
\ /
\ /
\ /
\ /
\ /
I\/I
\ /
*
pic 4.13
The only problem  we now have to clip against planes which are
directed almost arbitrary in space (the exact geometry of this view volume
depends on the "focus" parameter  the distance between the viewer and the
viewing plane (again, not quite the same as clipping plane). Although
conceptually easy to achieve clipping against arbitrary directed plane
would have higher complexity.
There is number of solutions one can consider: obvious one: indeed implement
real volume clipping, although expansive we would be able to completely
get rid of 2D clipping routines which overall might be quite descent.
Second: implement volume clipping with special kind of perspective view
volume, the one having 90' angle. The reason can be seen from the pic 4.14:
\ /
\ /
x=z \ / x=z
\ /
I\/I
\ /
*
pic 4.14
Planes composing this perspective view volume have pretty simple equations:
x==z , y==z, x==z and y==z clipping against those is way easier then
against arbitrary directed planes. The method however we would discuss is a
bit different, that is, we would not do clipping at all, to be more exact we
would only throw away polygons which are for sure outside the view volume and
leave those even partially inside to be further clipped against screen
boundaries after being projected. ( Clipping against viewing plane, is a
sacred matter that one can hardly get rid of ) One should understand that this
method works on assumption that there is no terribly big polygons around,
since a one part of a really big polygon can be within the view volume whereas
another can be both close to viewing plane and have really big absolute value
of X or Y, just something we are trying to exclude from being perspectively
projected.
How can one figure out whether a point is outside the pyramid with 90'
angle? From the pic 4.14 we can see that parts of the space separated
by Z==X and Z==X planes have obvious relationships among X and Z of
every point, if ZX  Z>X /
\  /
A ** B
\  /
Z<X \ / Z X
pic 4.15
We would make decisions, on the other hand, using notion of polygon's
extends. pic 4.16 Extend is a cube completely enclosing within itself
certain polygon. So coordinates of extend planes are that of maximum and
minimum among the polygon vertices along all axes.
xmin xmax
 ymin
\\ 
 \ \ 
 \ \ 
 \ /
 \/ 
 ymax
pic 4.16
This way by considering for example (xmin,zmax) point of the extend box we
can make a decision whether polygon's extend is outside the x=z plane.
^ Z

\  /
\  /
(xmax,zmax) \  / (xmin,zmax)
+ \  / ++
 \  / 
+ \ / +
*> X
++ (zmax)
 
pic 4.17
Let's list all the other cases:
xmin > zmax
ymin > zmax
xmax > zmax
ymax > zmax
On the same stage we can check if the polygon is completely behind
the view plane as well.
int C_volume_clipping(register int *vxes,int number)
{
int xmin,ymin,zmin,xmax,ymax,zmax;
int i;
ymin=xmin=zmin=INT_MAX;
ymax=xmax=zmax=INT_MIN; /* initializing searching */
for(i=0;ixmax) xmax=*vxes;
if(*vxesymax) ymax=*vxes;
if(*vxeszmax) zmax=*vxes;
if(*vxes