Cohen-Sutherland 裁剪算法中计算水平线的 x 截距时为什么需要舍入？

Question

我正在学习计算机图形学，偶然发现了 Cohen-Sutherland 剪线算法。我们有一条由点 P1 和 P2 定义的线段，我们试图找出它是否在裁剪矩形内被裁剪（通常由屏幕的宽度和高度定义，左上角是 [0, 0])

算法很简单，我们只是检查每个点，看看该点的 x 和 y 是否越界：

if (y1 < min_clip_y)
        p1_code |= CLIP_NORTH;
else if (y1 > max_clip_y)
        p1_code |= CLIP_SOUTH;

if (x1 < min_clip_x)
        p1_code |= CLIP_WEST;
else if (x1 > max_clip_x)
        p1_code |= CLIP_EAST;

// Same deal with x2, y2

如果 p1_code 和 p2_code 都不等于零，我们拒绝该线，如果它们都为零，我们接受它，否则我们继续测试以找到剪辑与相交的剪裁矩形边：

switch(p1_code)
{
    case CLIP_NORTH:
    {
         yc1 = min_clip_y;
         xc1 = x1 + 0.5f + (min_clip_y - y1) * (x2-x1) / (y2-y1);
    } break;

    // other cases...
}

这是我从一本书上读到的。我了解我们如何推导出 x 截距的方程式，我只是不明白为什么我们要添加 0.5f 以舍入到下一个整数。为什么要四舍五入？

谢谢！

Answer 1

很多计算机图形文字都有这样的错误。 C-S 是大约 50 年前发明的，当时浮点数比整数数学运算要慢得多，所以规范是使用整数算术或整数指令来模拟定点数。结果是旧代码的奇怪重新实现用浮点数移植了旧的定点数。这显然是其中之一。

如您所料，您可能希望使用浮点数进行整个计算，然后在最后绝对需要时四舍五入到最近的像素。但是对于现代 GPU，您甚至可以跳过它，因为消除锯齿的线条绘制可以正确处理浮点坐标。

事实上，奇怪的是图形文本仍然如此突出地裁剪线，因为现代图形更多地是关于多边形的。有许多漂亮的三角形和多边形算法比线裁剪具有更实际的重要性。太多的教科书作者成为学徒工具的奴隶。

Cohen-Sutherland 裁剪算法中计算水平线的 x 截距时为什么需要舍入？

Why do we need to round when computing x-intercept of horizontal line in Cohen-Sutherland clipping algorithm?

algorithm

rounding

clipping

line-segment