Scan-Converting Polygons
In Simple3DTest1, you drew polygons by converting projected polygons to a GeneralPath. As you saw, this gave imperfect results because the vertices of the polygons were rounded to the nearest integer. To fix this, you'll create a custom scan converter that keeps the floating-point vertices. A scan converter converts a polygon into horizontal scans so that the polygon can be drawn as a series of horizontal lines. You'll reuse this custom scan converter later on for texture mapping. It might sound silly to keep the vertices as floating points because the screen can handle only integer coordinates anyway. Eventually, the polygon will exist on all integer boundaries, but the trick is to convert from floating point to integers at a later time. By default, drawing with GeneralPath rounds each point to the nearest integer before drawing each edge of the polygon; you'll convert to integers after drawing each edge. This way, each edge of the polygon is more drawn more accurately. Drawing the outline of a polygon is like a game of connect-the-dots: You just draw each edge, or every line from vertex to vertex. Filling a polygon with a solid color might initially seem more complicated. To make it easier, we break it down into smaller steps. Shown in Screenshot, a polygon is broken down into horizontal scans for every row of pixels. To fill the polygon, just draw a horizontal line for every scan.
In Screenshot, every pixel under any part of the polygon is drawn. But what happens when two polygons are next to each other? In this scenario, polygons share edges, so some pixels will be drawn twice. It won't be clear which pixel belongs to which polygon. To fix this situation, you'll differentiate between left and right edges of each polygon. Left edges of a polygon will use the ceil() function to round up, while right edges will round down using ceil()-1. This is shown in Screenshot.
Using the technique demonstrated in Screenshot, two adjacent polygons won't overlap each over. Also, you'll use a custom ceil() function in the MoreMath class:
public static int ceil(float f) {
if (f > 0) {
return (int)f + 1;
}
else {
return (int)f;
}
}
This function converts a float to an int, whereas the Math.ceil() function takes a double as a parameter and returns a double. This way, you don't have to convert anything to or from a double. Now you'll create a simple Scan class, shown in Listing 7.7.
Listing 7.7 Scan Class
/**
A horizontal scan line.
*/
public class Scan {
public int left;
public int right;
/**
Sets the left and right boundaries for this scan if
the x value is outside the current boundary.
*/
public void setBoundary(int x) {
if (x < left) {
left = x;
}
if (x-1 > right) {
right = x-1;
}
}
/**
Clears this scan line.
*/
public void clear() {
left = Integer.MAX_VALUE;
right = Integer.MIN_VALUE;
}
/**
Determines if this scan is valid (if left <= right).
*/
public boolean isValid() {
return (left <= right);
}
/**
Sets this scan.
*/
public void setTo(int left, int right) {
this.left = left;
this.right = right;
}
/**
Checks if this scan is equal to the specified values.
*/
public boolean equals(int left, int right) {
return (this.left == left && this.right == right);
}
}
The Scan class is an inner class of ScanConverter. Each scan line has its own Scan object, and the scan converter scans every edge in the polygon. Every time it scans an edge on a particular scan line, the scan converter calls the Scan object's setBoundary() method. Calling this method could change the scan's left or right boundaries. If two different edges are scanned on the same line (and the edges have different locations), the left boundary will be less than the right boundary; thus, the scan will become valid. In other words, it requires more than one edge to create a valid scan. To actually scan a polygon's edge, you'll use the equation of the line. Consider a projected edge of the polygon formed by the points (x1, y1) and (x2, y2). For every horizontal line (y), you can find the corresponding x value by using this equation:
(x-x1)/(x2-x1) = (y-y1)/(y2-y1) x = (y-y1)(x2-x1)/(y2-y1)+x1
The ScanConverter class uses this equation. The ScanConverter class also keeps track of the ViewWindow (in case it changes size), a list of Scans for every horizontal line in the ViewWindow, and a top and bottom value for the top and bottom values of the last scanned polygon. The member variables of the ScanConverter are these:
ViewWindow view; Scan[] scans; int top; int bottom;
The method used to scan a polygon in the ScanConverter class is in Listing 7.8.
Listing 7.8 Simple Polygon Scan Conversion
int minX = view.getLeftOffset();
int maxX = view.getLeftOffset() + view.getWidth() - 1;
int minY = view.getTopOffset();
int maxY = view.getTopOffset() + view.getHeight() - 1;
int numVertices = polygon.getNumVertices();
for (int i=0; i<numVertices; i++) {
Vector3D v1 = polygon.getVertex(i);
Vector3D v2;
if (i == numVertices - 1) {
v2 = polygon.getVertex(0);
}
else {
v2 = polygon.getVertex(i+1);
}
// ensure v1.y < v2.y
if (v1.y > v2.y) {
Vector3D temp = v1;
v1 = v2;
v2 = temp;
}
float dy = v2.y - v1.y;
// ignore horizontal lines
if (dy == 0) {
continue;
}
int startY = Math.max(MoreMath.ceil(v1.y), minY);
int endY = Math.min(MoreMath.ceil(v2.y)-1, maxY);
float dx = v2.x - v1.x;
float gradient = dx / dy;
// scan-convert this edge (line equation)
for (int y=startY; y<=endY; y++) {
int x = MoreMath.ceil(v1.x + (y - v1.y) * gradient);
// ensure x within view bounds
x = Math.min(maxX+1, Math.max(x, minX));
scans[y].setBoundary(x);
}
}
The ScanConverter class converts a projected polygon to a series of horizontal scans. It also ensures that all the scans are in the view window. Note that the ScanConverter works only with convex polygons. Concave polygons could have some inward bulges that the ScanConverter misses. Here's how to iterate through all the scans:
int y = scanConverter.getTopBoundary();
while (y <= scanConverter.getBottomBoundary()) {
ScanConverter.Scan scan = scanConverter.getScan(y);
if (scan.isValid()) {
g.drawLine(scan.left, y, scan.right, y);
}
y++;
}
Optimizing Scan Conversion with Fixed-Point Math
This basic scan converter works, but it's going to be a little slower than it could be. This will be particularly noticeable when there are lots of polygons on screen. One reason this code isn't fast enough is because you are doing a lot of math with floats for every horizontal scan line. To speed up the scan conversion, you can use integers instead of floats and try to limit the amount of math involved per scan line. Of course, integers don't give the desired accuracy, so you'll have to be a little creative on how you interpret the integers. To do this, multiply each floating point value by a scale to get the value in integer range. For example, for a scale of 1,000, multiplying 10.5 times 1,000 gives the integer value 10,500. What value to use as a scale is important. If you use a power of 2, you can convert between scaled and unscaled integers by using bit shifting. In the examples, we use a scale of 216. Because integers are 32 bits long, this leaves the most significant 16 bits as the integer part and the least significant 16 bits as the fractional part. This number representation technique is often called fixed-point because the decimal point is fixed somewhere within the integer. Let's start with some constants that define the scaled, fixed-point integers:
final int SCALE_BITS = 16; final int SCALE = 1 << SCALE_BITS; final int SCALE_MASK = SCALE - 1;
The << operator is a bit shift, and 1 << 16 is equivalent to 216. With these constants, you can go ahead and lay out the code to convert to and from a fixed point. Convert a floating-point number to a fixed-point number:
int fixed = (int)(value * SCALE);
Convert a fixed-point number to a floating-point number:
float value = (float)fixed / SCALE;
Convert an integer to a fixed-point number:
int fixed = value << SCALE_BITS;
Convert a fixed-point number to an integer:
int value = fixed >> SCALE_BITS;
Get the fractional part of a fixed-point number:
float frac = (float)(fixed & SCALE_MASK) / SCALE;
Adding and subtracting two fixed-point numbers is performed just like normal addition and subtraction. Multiplication by a fixed-point number and a normal integer works the same as well. However, multiplication or division of two fixed-point numbers is a bit different. Multiplying two 32-bit numbers creates a 64-bit result, so for two fixed-point numbers, this effectively doubles the number of bits in the fractional part of the result. To fix this, you have to do multiplication in a 64-bit number (a long) so you don't chop off the bits you need. Then you need to shift it back down to convert back to your normal fixed-point number:
int fixed = (int) (((long)fixed1 * fixed2) >> SCALE_BITS);
Likewise, division has a similar effect but can be easily remedied:
int fixed = (int) (((long)fixed1 << SCALE_BITS) / fixed2);
You actually won't need to multiply or divide two fixed-point numbers in your code, but they are here for reference. Okay, now that you understand fixed-point numbers, here's the optimized scan converter:
int minX = view.getLeftOffset();
int maxX = view.getLeftOffset() + view.getWidth() - 1;
int minY = view.getTopOffset();
int maxY = view.getTopOffset() + view.getHeight() - 1;
int numVertices = polygon.getNumVertices();
for (int i=0; i<numVertices; i++) {
Vector3D v1 = polygon.getVertex(i);
Vector3D v2;
if (i == numVertices - 1) {
v2 = polygon.getVertex(0);
}
else {
v2 = polygon.getVertex(i+1);
}
// ensure v1.y < v2.y
if (v1.y > v2.y) {
Vector3D temp = v1;
v1 = v2;
v2 = temp;
}
float dy = v2.y - v1.y;
// ignore horizontal lines
if (dy == 0) {
continue;
}
int startY = Math.max(MoreMath.ceil(v1.y), minY);
int endY = Math.min(MoreMath.ceil(v2.y)-1, maxY);
top = Math.min(top, startY);
bottom = Math.max(bottom, endY);
float dx = v2.x - v1.x;
// special case: vertical line
if (dx == 0) {
int x = MoreMath.ceil(v1.x);
// ensure x within view bounds
x = Math.min(maxX+1, Math.max(x, minX));
for (int y=startY; y<=endY; y++) {
scans[y].setBoundary(x);
}
}
else {
// scan-convert this edge (line equation)
float gradient = dx / dy;
// trim start of line
float startX = v1.x + (startY - v1.y) * gradient;
if (startX < minX) {
int yInt = (int)(v1.y + (minX - v1.x) /
gradient);
yInt = Math.min(yInt, endY);
while (startY <= yInt) {
scans[startY].setBoundary(minX);
startY++;
}
}
else if (startX > maxX) {
int yInt = (int)(v1.y + (maxX - v1.x) /
gradient);
yInt = Math.min(yInt, endY);
while (startY <= yInt) {
scans[startY].setBoundary(maxX+1);
startY++;
}
}
if (startY > endY) {
continue;
}
// trim back of line
float endX = v1.x + (endY - v1.y) * gradient;
if (endX < minX) {
int yInt = MoreMath.ceil(v1.y + (minX - v1.x) /
gradient);
yInt = Math.max(yInt, startY);
while (endY >= yInt) {
scans[endY].setBoundary(minX);
endY--;
}
}
else if (endX > maxX) {
int yInt = MoreMath.ceil(v1.y + (maxX - v1.x) /
gradient);
yInt = Math.max(yInt, startY);
while (endY >= yInt) {
scans[endY].setBoundary(maxX+1);
endY--;
}
}
if (startY > endY) {
continue;
}
// line equation using integers
int xScaled = (int)(SCALE * v1.x +
SCALE * (startY - v1.y) * dx / dy) + SCALE_MASK;
int dxScaled = (int)(dx * SCALE / dy);
for (int y=startY; y<=endY; y++) {
scans[y].setBoundary(xScaled >> SCALE_BITS);
xScaled+=dxScaled;
}
}
}
Of course, fixed-point numbers don't have the precision or range that floating-point numbers do. Because the scan values can be out of range of the fixed-point number representation, in this code you trim the left and right parts of the scan if they are not within the view. Also, instead of recalculating the intersection at every point, you use the line's slope (dxScaled) to increase the x value (xScaled) for every line. The complete ScanConverter is probably not completely optimized; someone out there surely could make it even faster. One idea is to actually clip the 2D polygons to be within the view before scan converting so you don't scan off-screen polygons or the parts of polygons that are not visible. But this ScanConverter works well.