Now let’s talk clipping: the process of making sure we don’t write a line that’s not visible on the screen.
We’re so used to having clipping done for us that sometimes we can forget that clipping is not something that “just happens.” When we write a line to the screen what we’re really doing, at the bottom of the stack, is writing a bunch of bytes to memory that is being displayed using video hardware. And if we don’t stop at the edges, we’ll have a buffer overrun error: at the very least we’ll see bits of a line wrapping around the screen. Worse case: we will drop garbage into global memory or onto our stack, crashing our application.
Clipping a line ultimately requires us to find the point along the line that hits the edge of the screen. There are multiple ways we can do this: different algorithms which either modify Bresenham’s line drawing algorithm, or perform line clipping calculations before drawing.
For our purposes, since we are drawing 3D lines and our coordinates are specified with floating point values (because we’re now considering the third stage of clipping), we’re going to use the later strategy of finding the point where our lines intersect the edges.
Some Math.
Before we can describe how we clip lines, we need to introduce some vector math. (Yes, that dreaded 4 letter word.)
In this case, let’s talk [dot products.](https://en.wikipedia.org/wiki/Dot_product) Now I won’t get too deep into an explanation as to how this all works; for that, the incredible series on The essence of linear algebra by Grant Sanderson of 3Blue1Brown is absolutely fantastic and explains all this stuff at a level of detail with pretty pictures that can be understood by nearly anyone.
But the essence of it is this:
The dot product of two equal-length vectors–two values (a,b,c) and (x,y,z) for example–is given by the formula:
That is, you multiply all the items inside the two vectors together, and add them all up. So the dot product of (a,b,c) and (x,y,z) would be:
Now the dot product has a very interesting property which will be useful to us when we talk about clipping. And that is, geometrically speaking, the dot product has the useful property that the value of the dot product is equal to the length of the projection of one vector onto another, times the length of the other vector. That is:
where ||A|| is the length of vector A, and θ is the angle between the two vectors.
Graphically this looks like:
That is, if we were to take a vector A and “project” it into vector B, then the dot product is the length of that projection times the length of the vector B.
Now there is a second interesting property which we will use in clipping, which is this: if A and B are pointed more or less in the same direction, then the dot product will be positive. However, if (as in the diagram below) they are pointed roughly in opposite directions (that is, the angle is greater than 90 degrees), then the dot product will be negative:
This property will come in handy in a second.
Equation of a line.
While we’re on the subject, it’s useful to contemplate the “equation of a line” on a 2D surface.
The general form of a line equation is:
Where the variables a, b and c are selected so that any point (x,y) is on the line if it satisfies the relationship above.
Now…
Notice something familiar?
Doesn’t it look like a dot product?
And since we know the dot product is essentially the projected distance along a vector, this gives us a hint as to a geometric interpretation of the equation of a line. For a line (a,b,c), we could interpret our line equation as follows.
First, remember that the dot product (a,b)˙(x,y) is the projected distance of one of the vectors along the other–for example, the projection of (x,y) onto the vector (a,b):
Since our point (x,y) is on the line, this implies the dot product satisfies our equation above: that the dot product plus C = 0.
It also means something else.
It means all the points on our line satisfy this same projection relationship–which means our line is the line that runs perpendicular to the vector (a,b) that intersects (x,y):
More importantly, consider all the lines that run parallel to our line. The closer they are to the origin in our diagram, the smaller the dot product is for the points along that line. And the farther they are from the origin than our line, the bigger the dot product. This means our equation for a line is not just an equation solving for if points are on a line, but also indicates how far a point is from our line, and which side of the line our point is on.
Both of these ideas become very useful to our screen clipping code.
Clipping.
Let’s now consider the operation of clipping a line against a single edge, and part of the line goes across the edge.
In the above diagram, we’re clipping a line from A to B on the left side of our screen along the edge.
First, we need to consider if the line from A to B is even visible and if it intersects the edge. Then, if it intersects the edge, we need to find the point C where it intersects the edge
Notice both questions could be answered if we had the equation (a,b,c) that represents the edge x = -1, since from above we know if we’re inside or outside based on the sign of the result (a,b,c) ˙ (x,y,1), and the distance can help us calculate the point C.
The value for (a,b,c) should be obvious: we have the line for our edge along x = -1, and a little algebra later we get a = 1, b = 0 and c = 1. Ideally we want points inside our screen to be greater than or equal to zero–that is, for (a,b,c)˙(x,y,1) to be greater than or equal to zero if x >= -1, and from a simple inspection our values of (a,b,c) work–as if we were to plug in the coordinates (0,0), we get c = 1.
This gives us our tests to see if our two points are visible on our screen:
if (x + 1 >= 0) { /* Point is inside screen */ }
Where x+1 is a compact way of writing (a,b,c)˙(x,y,z), where (a,b,c) = (1,0.1).
This also gives us a way to calculate the position of C if points A and B cross our edge, by using similar triangles:
We know the triangle at ACJ is proportionally smaller to the triangle ABK. We can figure out how much smaller the triangle is, proportionally speaking, from the length of the two edges we know the length of–that is, the length of AJ, which is -A˙(a,b,c), and the length of AK, which is the length of JK (B˙(a,b,c)) plus the length of AJ.
The relative size of ACJ is:
And we can use this to find the position of C. The value α ranges from 0 to 1 and gives the relative size of triangle ACJ from triangle ABK. If &alpha was 1, then ACJ would be the same as ABK (because B˙(a,b,c) would be 0), and if &alpha was 0, then triangle ACJ would effectively be a point.
So we can find C through the following linear interpolation operation:
This operation is so important to our clipper we write it as a separate subroutine:
static void Lerp(const Point &a, const Point &b, float alpha, Point &c)
{
float a1 = 1.0f - alpha;
c.x = a1 * a.x + alpha * b.x;
c.y = a1 * a.y + alpha * b.y;
}
Where “Lerp” is short for “Linear interpolation”, and you’ll hear that term a lot in computer graphics.
Clipping in 2D
We now can write our 2D clipping routine, which basically clips against the four edges of our screen.
If we assume our four edges are along x = ±1 and y = ±1, then we can sketch our solution.
So let’s assume we’re given two points A and B, and we want to determine if we draw the line, draw a clipped line, or not draw a line at all.
Find the “out code”
First, we need to determine which edges the two points A and B are outside of. Since we have four edges, we need to compute a 4-bit value, with each bit representing if A and B are outside a particular edge. This we’ll call our “out code”, because in the four bits, a bit is set if the point is “outside” the screen at that edge.
Now we have four edges x = ±1 and y = ±1. Since we want a point at (0,0) to have a positive value (by convention), this gives our four edges at (-1,0,1), (1,0,1), (0,-1,1) and (0,1,1).
Remember that a point is outside each edge if the dot product is negative. So now we can quickly calculate our out code, with a little rearranging of our math:
static uint8_t OutCode(const Point &v)
{
uint8_t m = 0;
if (v.x < -1) m |= 1; // v * (1,0,1) < 0
if (v.x > 1) m |= 2; // v * (-1,0,1) < 0
if (v.y < -1) m |= 4; // v * (0,1,1) < 0
if (v.y &t; 1) m |= 8; // v * (0,-1,1) < 0
return m;
}
Next, quickly screen stuff that is not visible.
Notice one nice property of our out code: two points with the same bit set set represents two points on the outside of the same edge.
We can test for this quickly by taking the bit-wise ‘and’ of both out codes:
static void DrawClippedLine(const Point &a, const Point &b)
{
uint8_t a_out = OutCode(a);
uint8_t b_out = OutCode(b);
if (a_out & b_out) return;
Quickly find lines that are not clipped
We can also quickly test if both points are inside our screen–by testing to see if both out codes are zero. One way we can test for this–because we’ll use the intermediate result later–is to take the bit-wise ‘or’ of both out codes and test if zero:
uint8_t out_bits = a_out | b_out;
if (out_bits == 0) {
DrawLine(a,b);
} else {
If both out codes are 0, we can just draw our line.
Now find clipped lines.
But what happens if one or more bits are set? Well, that means that one (or both) of our points are outside the screen, and we need to clip our line. For our line drawing routine we have, basically, three different cases, illustrated below:
The first case, edge S, has one point inside of our screen. We only need to clip one edge.
The second case, edge R, has two points outside our screen, but the middle piece is visible inside our view.
And the third case, edge P, has two points outside our screen and no part of the line is visible.
So how do we screen against all these cases?
First, notice our out_bits variable above. It has the nice property that a bit is set only if we have to clip against a particular edge. This allows us to skip those calculations we don’t need to bother to do.
So let’s iterate across all of the visible edges and calculate our α for each edge:
uint8_t m = 1;
uint8_t i;
float alpha;
for (i = 0; i < 4; ++i) {
if (out_bits & m) {
// Calculate alpha; the intersection along the line
// vector intersecting the specified edge
//
// These are specific cases of the general equation
// alpha = (c - old)/(new - old), which yields
// alpha == 0 if c == old, and alpha == 1 if c == new,
// and with alpha as a linear scale with the intersection
// point sliding from old to new.
switch (i) {
default:
case 0: // clip (1,0,1)
alpha = 1 + p3pos.x;
alpha = alpha/(alpha - (1 + v.x));
break;
case 1: // clip (-1,0,1)
alpha = 1 - p3pos.x;
alpha = alpha/(alpha - (1 - v.x));
break;
case 2: // clip (0,1,1)
alpha = 1 + p3pos.y;
alpha = alpha/(alpha - (1 + v.y));
break;
case 3: // clip (0,-1,1)
alpha = 1 - p3pos.y;
alpha = alpha/(alpha - (1 - v.y));
break;
}
Now we want to track which point is inside and which point is outside, and for the outside point on our line, track the ‘alpha’ for that side, so we can determine which side needs to be clipped.
We do this by tracking an ‘alpha’ for each side of our line, which we’ll call alpha_a and alpha_b. By convention we’ll assume alpha is 0 if our line clips at point A and 1 if we clip at point B.
We also know which side (the side with A or B) is being clipped by looking at our original outcode: if the bit is set in a_out, then we need to clip on side a. If b_out, then on side b. Notice it will only be one or the other; if neither are set we don’t clip (because out_bits would be zero at that bit), and if both are set–well, we skipped this line earlier.
So let’s add the following stuff (in red):
float alpha_a = 0;
float alpha_b = 1;
uint8_t m = 1;
uint8_t i;
float alpha;
for (i = 0; i < 4; ++i, m <<= 1) {
if (out_bits & m) {
// Calculate alpha; the intersection along the line
// vector intersecting the specified edge
//
// These are specific cases of the general equation
// alpha = (c - old)/(new - old), which yields
// alpha == 0 if c == old, and alpha == 1 if c == new,
// and with alpha as a linear scale with the intersection
// point sliding from old to new.
switch (i) {
default:
case 0: // clip (1,0,1)
alpha = 1 + p3pos.x;
alpha = alpha/(alpha - (1 + v.x));
break;
case 1: // clip (-1,0,1)
alpha = 1 - p3pos.x;
alpha = alpha/(alpha - (1 - v.x));
break;
case 2: // clip (0,1,1)
alpha = 1 + p3pos.y;
alpha = alpha/(alpha - (1 + v.y));
break;
case 3: // clip (0,-1,1)
alpha = 1 - p3pos.y;
alpha = alpha/(alpha - (1 - v.y));
break;
}
if (a_out & m) {
if (alpha_a < alpha) alpha_a = alpha;
} else {
if (alpha_b > alpha) alpha_b = alpha;
}
One more thing: if alpha_a has become bigger than alpha_b, that means we have case P above; our line is not visible on the screen. So we can stop processing right away:
if (alpha_a > alpha_b) return;
}
}
Now that we’ve done our calculations, we can now determine the new endpoints and draw our line. To do this we again make use of our outcodes to determine if we even need to clip one side or another.
Point c1;
if (a_out) {
Lerp(a,b,alpha_a,c1);
} else {
c1 = a;
}
Point c2;
if (b_out) {
Lerp(a,b,alpha_b,c2);
} else {
c2 = b;
}
And now–finally! we can draw our line.
DrawLine(c1,c2);
}
}
There are some interesting things we can say about our line clipping algorithm.
First, it follows the principle of only doing work if we have to. If we don’t have to clip against an edge, we don’t clip against the edge.
Second, notice that we could in theory extend this to 3D very easily. If we wanted to clip to a cube where x, y and z range from -1 to 1, our 6 different clipping dot products would be
1: ( 1, 0, 0, 1)
2: (-1, 0, 0, 1)
3: ( 0, 1, 0, 1)
4: ( 0,-1, 0, 1)
5: ( 0, 0, 1, 1)
6: ( 0, 0,-1, 1)
Clipping in homogeneous coordinates
Notice something else very interesting about our list of vectors we’re clipping against: they sort of look like homogeneous coordinates, don’t they?
And in fact, with a minor modification to our X or Y clipping (depending on the aspect ratio of the screen, since our screen is not square), this is becomes our clipping algorithm for drawing lines in 3D.
We can make a few optimizations. For example, rather than supplying both points A and B as we draw our line, if we were to adopt a ‘move/draw’ mechanism, we can reuse some of the calculations we perform with the previous point as we draw the next.
Note: This is why we use a move/draw mechanism for drawing our lines.
We can also define a homogeneous vector for convenience sake:
struct G3DVector {
float x;
float y;
float z;
float w;
};
And voliá! We have our line clipping algorithm for homogeneous coordinates.
First, we need our linear interpolation algorithm and our out code calculator for homogeneous coordinates:
void G3D::Lerp(const G3DVector &a, const G3DVector &b, float alpha, G3DVector &c)
{
float a1 = 1.0f - alpha;
c.x = a1 * a.x + alpha * b.x;
c.y = a1 * a.y + alpha * b.y;
c.z = a1 * a.z + alpha * b.z;
c.w = a1 * a.w + alpha * b.w;
}
uint8_t G3D::OutCode(const G3DVector &v)
{
uint8_t m = 0;
float px = p2xsize * v.x;
float py = p2ysize * v.y;
if (px < -v.w) m |= 1; // (p2xsize,0,0,1)
if (px > v.w) m |= 2; // (-p2xsize,0,0,1)
if (py < -v.w) m |= 4; // (0,p2ysize,0,1)
if (py > v.w) m |= 8; // (0,-p2ysize,0,1)
if (v.z < -v.w) m |= 16;
if (v.z > v.w) m |= 32;
return m;
}
Next, we need to run the same clipping algorithm, but using homogeneous coordinates:
void G3D::p3movedraw(bool drawFlag, const G3DVector &v)
{
uint8_t newOutCode = OutCode(v);
G3DVector lerp;
if (drawFlag) {
uint8_t mask = newOutCode | p3outcode;
/*
* Fast accept/reject
*/
if (0 == (newOutCode & p3outcode)) {
if (0 == mask) {
// Fast accept. Both points are inside; we assume
// the previous point was already passed upwards,
// so we only draw to the current vector location
p2movedraw(true,v.x/v.w,v.y/v.w);
} else {
// At this point we have a line that crosses
// a boundary. We calculate the alpha between
// 0 and 1 for each point along the line.
//
// (This is the Liang-Barsky optimization of
// the Cohen-Sutherland algorithm)
float aold = 0; // (1 - alpha) * old + alpha * new = v
float anew = 1; // in the above, 0 == old, 1 == new.
float alpha;
uint8_t m = 1;
uint8_t i;
for (i = 0; i < 6; ++i) {
if (mask & m) {
// Calculate alpha; the intersection along the line
// vector intersecting the specified edge
//
// These are specific cases of the general equation
// alpha = (c - old)/(new - old), which yields
// alpha == 0 if c == old, and alpha == 1 if c == new,
// and with alpha as a linear scale with the intersection
// point sliding from old to new.
switch (i) {
default:
case 0: // clip (p2xsize,0,0,1)
alpha = p2xsize * p3pos.x + p3pos.w;
alpha = alpha/(alpha - (p2xsize * v.x + v.w));
break;
case 1: // clip (-p2xsize,0,0,1)
alpha = - p2xsize * p3pos.x + p3pos.w;
alpha = alpha/(alpha - (-p2xsize * v.x + v.w));
break;
case 2: // clip (0,p2ysize,0,1)
alpha = p2ysize * p3pos.y + p3pos.w;
alpha = alpha/(alpha - (p2ysize * v.y + v.w));
break;
case 3: // clip (0,-p2ysize,0,1)
alpha = - p2ysize * p3pos.y + p3pos.w;
alpha = alpha/(alpha - (- p2ysize * v.y + v.w));
break;
case 4: // clip (0,0,1,1)
alpha = p3pos.z + p3pos.w;
alpha = alpha/(alpha - (v.z + v.w));
break;
case 5: // clip (0,0,-1,1)
alpha = - p3pos.z + p3pos.w;
alpha = alpha/(alpha - (-v.z + v.w));
break;
}
if (p3outcode & m) {
if (aold < alpha) aold = alpha;
} else {
if (anew > alpha) anew = alpha;
}
if (aold > anew) {
// We have a case where the line is not visible
// because it's outside the visible frustrum.
// abort.
break;
}
}
m <<= 1;
}
if (i >= 6) {
// Ran all clipping edges.
if (p3outcode) {
Lerp(p3pos,v,aold,lerp);
p2movedraw(false,lerp.x/lerp.w,lerp.y/lerp.w);
}
// Draw to the new point
if (newOutCode) {
Lerp(p3pos,v,anew,lerp);
p2movedraw(true,lerp.x/lerp.w,lerp.y/lerp.w);
} else {
p2movedraw(true,v.x/v.w,v.y/v.w);
}
}
}
}
} else {
if (newOutCode == 0) {
p2movedraw(false,v.x/v.w,v.y/v.w);
}
}
p3outcode = newOutCode;
p3pos = v;
}
This assumes we’ve added a couple of new fields to our class:
G3DVector p3pos;
uint8_t p3outcode;
And now we have our clipping routine!
The code for our clipping routine is in GitHub; you can download it from here.
Next time: we’ll take all that stuff we talked about with homogeneous coordinates and put the whole thing together to draw 3D objects!
The Hacking Den 