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

目标

实现

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;
}

总结

目标达成。