Java软光栅渲染器-2D直线剪切

冰点 Java, 计算机图形学, 光栅器, 渲染器

目标

实现

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 方法来画线并不是什么好主意，应该把方法名改一改。

  1. 把原来的 drawLine 方法重命名为 drawLineBresenham；
  2. 把 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;
}

总结

目标达成。