如何用布雷森汉姆算法绘制椭圆扇区？

Question

如何使用布雷森汉姆的算法绘制填充椭圆扇区，并使用 DrawPixel 方法绘制位图对象？

我写了绘制椭圆的方法，但这种方法使用对称性并且只通过第一象限。此算法不适用于扇区。当然，我可以写 8 个周期，但我认为这不是任务中最优雅的解决方案。

Answer 1

在整数数学中，通常的参数化是使用极限线(在 CW 或 CCW 方向上(而不是角度。因此，如果您可以将这些角度转换为这样的角度(您需要sin,cos，但只需一次(，那么您可以使用基于整数数学的渲染。正如我在评论中提到的，bresenham 对于椭圆扇区来说不是一个好方法，因为您需要计算插值起点的内部迭代器和计数器状态，并且它还会只为您提供圆周点而不是填充形状。

这里有很多方法可以做到这一点，一个简单的方法：

1. 将椭圆转换为圆

   只需重新缩放较小的半径轴

2. 循环通过这种圆圈的bbox。

   简单的 2 个嵌套for环，覆盖外切的正方形到我们的圆

3. 检查点是否在圆内

   只需检查圆圈居中时是否x^2 + y^2 <= r^2(0,0)

4. 检查点是否位于边线之间

   所以它应该是一条边缘的 CW 和另一条边缘的 CCW。您可以为此利用交叉乘积(它的 z 坐标极性将告诉您点是 CW 还是 CCW 相对于测试的边缘线(

   但这最多只能工作 180 度切片，因此您还需要为象限添加一些检查以避免漏报。但这些只是在此之上的几个如果。

5. 如果满足所有条件，则将点转换回椭圆并渲染

这里有一个小C++例子：

void elliptic_arc(int x0,int y0,int rx,int ry,int a0,int a1,DWORD c)    
{
// variables
int  x, y, r,
xx,yy,rr,
xa,ya,xb,yb,                // a0,a1 edge points with radius r
mx,my,cx,cy,sx,sy,i,a;
// my Pixel access (you can ignore it and use your style of gfx access)
int **Pixels=Main->pyx;         // Pixels[y][x]
int   xs=Main->xs;              // resolution
int   ys=Main->ys;
// init variables
r=rx; if (r<ry) r=ry; rr=r*r;   // r=max(rx,ry)
mx=(rx<<10)/r;                  // scale from circle to ellipse (fixed point)
my=(ry<<10)/r;
xa=+double(r)*cos(double(a0)*M_PI/180.0);
ya=+double(r)*sin(double(a0)*M_PI/180.0);
xb=+double(r)*cos(double(a1)*M_PI/180.0);
yb=+double(r)*sin(double(a1)*M_PI/180.0);
// render
for (y=-r,yy=y*y,cy=(y*my)>>10,sy=y0+cy;y<=+r;y++,yy=y*y,cy=(y*my)>>10,sy=y0+cy) if ((sy>=0)&&(sy<ys))
for (x=-r,xx=x*x,cx=(x*mx)>>10,sx=x0+cx;x<=+r;x++,xx=x*x,cx=(x*mx)>>10,sx=x0+cx) if ((sx>=0)&&(sx<xs))
if (xx+yy<=rr)                // inside circle
{
if ((cx>=0)&&(cy>=0)) a=  0;// actual quadrant
if ((cx< 0)&&(cy>=0)) a= 90;
if ((cx>=0)&&(cy< 0)) a=270;
if ((cx< 0)&&(cy< 0)) a=180;
if ((a   >=a0)||((cx*ya)-(cy*xa)<=0))           // x,y is above a0 in clockwise direction
if ((a+90<=a1)||((cx*yb)-(cy*xb)>=0))
Pixels[sy][sx]=c;
}
}

请注意，两个角度都必须在<0,360>范围内。我的屏幕有 y 指向下方，所以如果a0<a1它将是与 routione 匹配的 CW 方向。如果使用a1<a0则将跳过范围，而是呈现椭圆的其余部分。

这种方法使用a0,a1作为真实角度!!

为了避免循环内部的除法，我使用了 10 位定点刻度。

您可以简单地将其划分为 4 个象限，以避免 4 个 if 内部循环以提高性能。

x,y是圆形比例尺中的点，以(0,0)
cx,cy是椭圆刻度中以(0,0)为中心的点
sx,sy是椭圆刻度中的点转换为椭圆中心位置

请注意我的像素访问是Pixels[y][x]但大多数 API 都使用Pixels[x][y]所以不要忘记将其更改为您的 API，以避免访问违规或结果旋转 90 度......