Java软光栅渲染器-2D直线剪切
目标
- 实现2D直线的剪切算法（见Line clipping）。
实现
Cohen-Sutherland算法
wiki上列出了很多直线剪切算法，看得有些眼花。我只看了排在第一个的 Cohen-Sutherland 算法。
这种算法把2D空间分成九个区域，画布位于正中。内部（INSIDE）、上(TOP)、下（BOTTOM）、左（LEFT）、右（RIGHT）等各个区域，分别用一个4位的二进制数进行编码。
typedef int OutCode;
const int INSIDE = 0; // 0000
const int LEFT = 1; // 0001
const int RIGHT = 2; // 0010
const int BOTTOM = 4; // 0100
const int TOP = 8; // 1000
在进行剪切时，先判断线段两个端点(x0, y0)、（x1, y1）各自处于哪个空间，然后用“或”运算到它们的编码。
// 使用剪切矩形的边界来计算点(x, y) 的二进制编码
// 假设窗口边界为 (xmin, ymin) 和 (xmax, ymax)，且 被声明为全局变量
OutCode ComputeOutCode(double x, double y)
{
OutCode code;
code = INSIDE; // 初始值，位于剪切窗口内部
if (x < xmin) // 位于剪切窗口左侧
code |= LEFT;
else if (x > xmax) // 位于剪切窗口右侧
code |= RIGHT;
if (y < ymin) // 位于剪切窗口下方
code |= BOTTOM;
else if (y > ymax) // 位于剪切窗口上方
code |= TOP;
return code;
}
返回值（OutCode）应该是下列九个值之一。显然只有0000是位于画布内的。
| left | central| right
--------|--------|--------|--------
top | 1001 | 1000 | 1010
central | 0001 | 0000 | 0010
bottom | 0101 | 0100 | 0110
在剪切函数中，先根据两个端点的OutCode进行判断。
- 如果OutCode0和OutCode1都等于0，那么显然线段位于画布内，就不用计算了，直接画吧。
- 如果OutCode0和OutCode1相等且不为0，说明它们都位于画布外的同一区域，不需要画。
- 如果OutCode0和OutCode1不相等且不为0，但是同处于TOP区域，也不需要画。
- 相同的道理，如果 OutCode0 和 OutCode1 同处于 BOTTOM区域、或者同处于 LEFT 区域、或者同处于 RIGHT 区域，都不需要画。
- 剩下的情况，就要分区域来计算线段与画布边界的交点位置，只绘制屏幕内的线段。
wiki提供的C代码如下：
// Cohen–Sutherland 剪切算法
// 根据一个从 (xmin, ymin) 到 (xmax, ymax) 的矩形空间
// 剪切一条从 P0 = (x0, y0) 到 P1 = (x1, y1) 的线段
void CohenSutherlandLineClipAndDraw(double x0, double y0, double x1, double y1)
{
// 分别计算 P0 和 P1 的OutCode，判断它们是否位于剪切窗口外。
OutCode outcode0 = ComputeOutCode(x0, y0);
OutCode outcode1 = ComputeOutCode(x1, y1);
bool accept = false;
while (true) {
if (!(outcode0 | outcode1)) { // OR运算的结果为0，说明线段位于剪切窗口内，直接画吧。
accept = true;
break;
} else if (outcode0 & outcode1) { // AND运算的结果不为0，说明两个点位于剪切窗口外的相同区域，终止循环。
break;
} else {
// 前两个判断都不通过，说明需要计算线段与剪切矩形的交点。
double x, y;
// 至少有一个端点位于剪切窗口外，判断它的位置。
OutCode outcodeOut = outcode0 ? outcode0 : outcode1;
// 现在计算交点
// 使用公式:
// slope = (y1 - y0) / (x1 - x0)
// x = x0 + (1 / slope) * (ym - y0), ym 等于 ymin 或 ymax
// y = y0 + slope * (xm - x0), xm 等于 xmin 或 xmax
if (outcodeOut & TOP) { // 位于窗口上方
x = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0);
y = ymax;
} else if (outcodeOut & BOTTOM) { // 位于窗口下方
x = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0);
y = ymin;
} else if (outcodeOut & RIGHT) { // 位于窗口右侧
y = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0);
x = xmax;
} else if (outcodeOut & LEFT) { // 位于窗口左侧
y = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0);
x = xmin;
}
// 现在把窗口外面这个端点移到交点处，准备下一轮剪切测试。
if (outcodeOut == outcode0) {
x0 = x;
y0 = y;
outcode0 = ComputeOutCode(x0, y0);
} else {
x1 = x;
y1 = y;
outcode1 = ComputeOutCode(x1, y1);
}
}
}
if (accept) {
// 下面的函数留给用户自己实现。
DrawRectangle(xmin, ymin, xmax, ymax);
LineSegment(x0, y0, x1, y1);
}
}
Java实现
首先在 ImageRaster 类中定义Cohen-Sutherland算法的空间编码
// Cohen-Sutherland算法的空间编码
private final static int INSIDE = 0; // 0000
private final static int LEFT = 1; // 0001
private final static int RIGHT = 2; // 0010
private final static int BOTTOM = 4; // 0100
private final static int TOP = 8; // 1000
然后定义剪切矩形，并在构造方法中初始化。
// 剪切矩形
private final int xmin, ymin;
private final int xmax, ymax;
/**
* 初始化光栅器
* @param image
*/
public ImageRaster(Image image) {
this.width = image.getWidth();
this.height = image.getHeight();
this.components = image.getComponents();
// 初始化剪切矩形
xmin = ymin = 0;
xmax = width - 1;
ymax = height - 1;
}
其实我们并不需要定义这对变量，直接用 (0, 0) 和 (width-1, height-1)这对坐标来裁剪就行了。为了看到直线剪切算法的实际效果，我打算改变一下剪切矩形的大小。
xmin = ymin = 100;
xmax = width - 101;
ymax = height - 101;
待会实现了剪切算法后，我们再运行上一章编写的Test2DLines程序。理论上应该看到画布边缘有一道宽度为100像素的“真空”区域。
实现 computeOutCode 方法。
/**
* 使用剪切矩形的边界来计算点(x, y) 的二进制编码
*
* @param x
* @param y
* @return
*/
private int computeOutCode(int x, int y) {
int code;
code = INSIDE; // 初始值，位于剪切窗口内部
if (x < xmin) // 位于剪切窗口左侧
code |= LEFT;
else if (x > xmax) // 位于剪切窗口右侧
code |= RIGHT;
if (y < ymin) // 位于剪切窗口下方
code |= BOTTOM;
else if (y > ymax) // 位于剪切窗口上方
code |= TOP;
return code;
}
实现 cohenSutherlandLineClipAndDraw 方法。
/**
* Cohen–Sutherland 剪切算法
* @param x0
* @param y0
* @param x1
* @param y1
* @param color
*/
public void cohenSutherlandLineClipAndDraw(int x0, int y0, int x1, int y1, ColorRGBA color) {
// 分别计算 P0 和 P1 的OutCode，判断它们是否位于剪切窗口外。
int outcode0 = computeOutCode(x0, y0);
int outcode1 = computeOutCode(x1, y1);
boolean accept = false;
while (true) {
if ((outcode0 | outcode1) == 0) { // OR运算的结果为0，说明线段位于剪切窗口内，直接画吧。
accept = true;
break;
} else if ((outcode0 & outcode1) != 0) { // AND运算的结果不为0，说明两个点位于剪切窗口外的相同区域，终止循环。
break;
} else {
// 前两个判断都不通过，说明需要计算线段与剪切矩形的交点。
double x = 0, y = 0;
// 至少有一个端点位于剪切窗口外，判断它的位置。
int outcodeOut = outcode0 != 0 ? outcode0 : outcode1;
// 现在计算交点
// 使用公式:
// slope = (y1 - y0) / (x1 - x0)
// x = x0 + (1 / slope) * (ym - y0), ym 等于 ymin 或 ymax
// y = y0 + slope * (xm - x0), xm 等于 xmin 或 xmax
if ((outcodeOut & TOP) != 0) { // 位于窗口上方
x = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0);
y = ymax;
} else if ((outcodeOut & BOTTOM) != 0) { // 位于窗口下方
x = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0);
y = ymin;
} else if ((outcodeOut & RIGHT) != 0) { // 位于窗口右侧
y = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0);
x = xmax;
} else if ((outcodeOut & LEFT) != 0) { // 位于窗口左侧
y = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0);
x = xmin;
}
// 现在把窗口外面这个端点移到交点处，准备下一轮剪切测试。
if (outcodeOut == outcode0) {
x0 = (int) x;
y0 = (int) y;
outcode0 = computeOutCode(x0, y0);
} else {
x1 = (int) x;
y1 = (int) y;
outcode1 = computeOutCode(x1, y1);
}
}
}
if (accept) {
drawLine(x0, y0, x1, y1, color);
}
}
写完了，把Line2D中的Draw方法改动一下，通过调用 cohenSutherlandLineClipAndDraw() 方法来画线。
/**
* 代表一条线段。
*
* @author yanmaoyuan
*
*/
public class Line2D implements Drawable {
public int x0, y0;
public int x1, y1;
public ColorRGBA color = ColorRGBA.RED;
@Override
public void draw(ImageRaster imageRaster) {
//imageRaster.drawLine(x0, y0, x1, y1, color);
imageRaster.cohenSutherlandLineClipAndDraw(x0, y0, x1, y1, color);
}
}
运行我们上一章实现的 Test2DLines 程序，结果如下：
还不错，矩形外的线段都被剪切了。
再次重构
我认为调用 cohenSutherlandLineClipAndDraw 方法来画线并不是什么好主意，应该把方法名改一改。
- 把原来的 drawLine 方法重命名为 drawLineBresenham；
- 把 cohenSutherlandLineClipAndDraw 重命名为 drawLine 。
注：在Eclipse 中可以先用鼠标选中方法名，然后按快捷键 Alt + Shift + R 来改名。连续按2次 Alt + Shift + R 将会弹出一个改名窗口，可以把工程中所有调用该方法的地方都一起改掉。
改完名后，Line2D 类就可以直接调用 drawLine 方法来画线了。新的 drawLine 方法拥有了2D直线剪切的功能。
其次，把 (xmin, ymin) 和 (xmax, ymax) 这组变量的值改回来。
/**
* 初始化光栅器
* @param image
*/
public ImageRaster(Image image) {
this.width = image.getWidth();
this.height = image.getHeight();
this.components = image.getComponents();
// 初始化剪切矩形
xmin = ymin = 0;
xmax = width - 1;
ymax = height - 1;
}
总结
目标达成。