是否有某种Bresenham算法或等效方法可用于扫描线渲染旋转的椭圆？

#1 楼

Foley，van Dam等人撰写的经典著作《计算机图形学：原理与实践》（第二版）。在19.2节中描述了这种算法。

书中的解释似乎来自于Dilip Da Silva的MSc论文《 2D基元的栅格算法》。

另请参阅以下论文：Van Aken和Novak的光栅显示曲线绘制算法（ACM TOG，1985年）。
Chandler的隐式定义曲线跟踪算法（IEEE计算机图形学和应用程序，1988年）。

#2 楼

所有圆锥形曲线（包括旋转的椭圆形）都可以用形式为

H(x, y) = A x² + B xy + C y² + D x + E y + F = 0

的隐式方程式描述。增量线跟踪算法的基本原理（我不会称其为扫描线）是要跟随尽可能满足方程的像素。

根据线的局部斜率，在横向或对角线移动后，您会在x或y方向上进行更多的操作。做出此决定是为了使H（x，y）的绝对值最小。

在直线的情况下，斜率是一个常数，因此横向和对角线移动始终在

如果是圆弧，则斜率会变化，并且可以区分对应于曲线的8个八分圆的8种情况（有4种可能的横向运动，每2种对角运动）。

对于椭圆形和其他圆锥形，可以推广八分圆分解。这导致一个相当乏味的讨论。

您可以避免八分圆的讨论，并修改算法以查看当前像素的所有邻居。这会导致像Moore邻域这样的通用轮廓跟踪算法，在该算法中，您将遵循H(x, y) >= 0区域的轮廓。

请注意，直线，圆和与椭圆对齐的椭圆可以用带整数的隐式方程式描述系数。使用普通圆锥曲线不再可能，您将不得不求助于浮点数或良好的有理逼近。


最后，请注意，增量计算可节省计算H时的工作量。

H(x+1, y) = H(x, y) + A.(2x+1) + B.y + D = H(x, y) + (2A).x + (A + B.y + D)

也可以使用真正的扫描线解决方案。让y逐渐变化，并求解H的x方程：

H(x, y) = A x² + (B y + D) x + (C y² + E y + F) = 0

这将为每个x产生两个y值。所得的曲线将不那么令人愉快，因为它将始终每行计数两个像素，当斜率低于1时，它将留下孔。您可以通过填充连续行的根之间的像素范围来应对。