是否有某种Bresenham算法或等价于scanline绘制一个旋转椭圆？

Question

回到过去，当你经常要写自己的低级渲染算法时，我们都用它来学习用于线条和圆圈的Bresenham算法。

将Bresenham圆算法扩展到轴心平行于X和Y轴的椭圆几乎是很容易的。

但是，如果有某种Bresenham风格的方法来渲染一个任意的椭圆，它的轴是在某个任意的角度，我总是回避它。

旋转椭圆是否存在这样的扫描线方法？

Answer 1

经典著作“计算机图形学:原理与实践”(第二版)，由Foley，van等人著。在第19.2节中描述了这种算法。

这本书中的解释似乎来自MSc的一篇论文，Dilip的二维基元的栅格算法。

另见这些文件：

• 光栅显示器的曲线绘制算法，Van和Novak著(ACM，1985年)。
• 隐式曲线跟踪算法作者钱德勒(与应用，1988年)。

Answer 2

所有的二次曲线(包括旋转椭圆)都可以用该形式的隐式方程来描述。

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

增量行跟踪算法(我不会称之为scanline)的基本原理是尽可能地遵循满足方程的像素。

根据直线的局部斜率，您在x或y方向上前进得更快，无论是横向移动还是对角线移动。这个决定是为了使H(x，y)的绝对值最小化。

在直线的情况下，斜率是常数，因此横向和对角线的移动总是在同一个方向上。

在圆弧的情况下，坡度是变化的，可以区分出8种情况对应于曲线的8种形式(有四种可能的横向移动，每两种对角线移动)。

对于椭圆和其他二次曲线，你可以推广八分分解。这导致了一场相当乏味的讨论。

您可以避免重要的讨论，并修改算法以查看当前像素的所有邻居。这将导致像摩尔邻域这样的一般轮廓跟踪算法，在这里您将遵循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)

真正的scanline解决方案也是可能的。让y渐变，并求解x的H方程：

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

这将为每个x生成两个y值。由此产生的曲线将不那么愉快，因为它总是计算每一行两个像素，这将在斜率低于1时留下洞。您可以通过填充连续行的根之间的像素范围来处理问题。