计算机图形学笔记二——圆形、圆弧段的绘制算法

圆形的绘制

绘制圆形，我们要利用好圆形的对称性，我们可以通过绘制\(\frac{1}{8}\)圆，然后进行一些变换完成整个圆的绘制。

上一篇：绘制直线的算法

下一篇：橡皮筋技术

中点画圆法

和中点画线法相似，首先构造圆的隐式方程：

\[F(x,y)=x^2+y^2-R^2

\]

在圆上的点是0，在圆外面的是F(x,y)>0，在圆里面的是F(x,y)<0，我们绘制第一卦象的\(\frac{1}{8}\)个圆[\(\frac{\pi}{2}\),\(\frac{\pi}{4}\)]（往x轴正方向迭代），构造判别式：

\[d=F(M)=F(x_i+1,y_i-0.5)=(x_i+1)^2+y_i-0.5)^2-R^2

\]

当d$>=$0时，最佳逼近点取 \((x_i+1,y_i-1)\)

\[d_1=F(M)=F(x_i+2,y_i-1.5)=d+2(x_i+y_i)+5

\]

当d$<$0，最佳逼近点取 \((x_i,y_i)\)

\[d_1=F(M)=F(x_i+2,y_i-0.5)=d+2x_i+3

\]

（这里书上似乎写错了，书中写成了\(F(x_i+2,y_i-1.5)\)，在此予以纠正。）

得到迭代公式，我们可以写出这样的代码：这份代码与书中的有所不同，书中的代码没有使用数组来存储循环的部分。

void Mid_Circle(int Rx, int Ry, int R) {

glBegin(GL_POINTS);

int x, y, d;

x = 0, y = R;

d = 5 - 4 * R;

int dir[4][2] = {

{ 1, 1 }, { 1,-1 },

{ -1,1}, {-1,-1 }

}; //使用循环来计算对称的区域

for (int i = 0; i < 2; i++) {//这里x=0所以只需要循环2次就行了。

glVertex2i(Rx + x * dir[i][0], Ry + y * dir[i][1]);

glVertex2i(Rx + y * dir[i][0], Ry + x * dir[i][1]);

}

while (x <= y) {

if (d >= 0) {

x += 1;

y -= 1;

d += 8 * (x - y) + 20;

}

else {

x += 1;

d += 8 * x + 12;

}

for (int i = 0; i < 4; i++) {

glVertex2i(Rx + x * dir[i][0], Ry + y * dir[i][1]);

glVertex2i(Rx + y * dir[i][0], Ry + x * dir[i][1]);

}

}

glFlush();

glEnd();

}

Bresenham画圆算法

和画线算法很相似，也是通过计算残差来进行近似，只是迭代方程有所不同，我们直接开始推导：

设当前最佳逼近点为 \((x_i,y_i)\)，那么下一个最佳逼近点为\((x_i+1,y_i)\)或者 \((x_i+1,y_i-1)\)，残差分别为：

\[d_1=y_i^2-y^2=y_i^2-(R^2-(x_i+1)^2)

\]

\[d_2=y^2-(y_i-1)^2=R^2-(x_i+1)^2-(y_i-1)^2

\]

\[p_i=d_1-d_2=2(x_i+1)^2+y_i^2-(y_i-1)^2-2R^2

\]

若 \(p_i>0\)则取 \((x_i+1,y_i-1)\)作为取样点，得到迭代方程：

\[p_{i+1}=p_i+4(x_i-y_i)+10

\]

若 \((p_i<=0)\)则取点 \((x_i+1,y_i)\)作为最佳取样点，得到迭代方程：

\[p_{i+1}=p_i+4x_i+6

\]

在点 \((0,R)\)可以得到判别式:

\[p_0=3-2R

\]

我们可以写出这样的代码

void BRESENHAM_Circle(int Rx, int Ry, int R) {

glBegin(GL_POINTS);

int x, y;

x = 0, y = R;

int d = 3 - 2 * R;

int dir[4][2] = {

{ 1, 1 }, { 1,-1 },

{ -1,1}, {-1,-1 }

}; //使用循环来计算对称的区域

for (int i = 0; i < 2; i++) {

glVertex2i(Rx, Ry + y*dir[i][1]);

glVertex2i(Rx + y * dir[i][0], Ry);

}

while (x < y) {

if (d >= 0) {

x += 1;

y -= 1;

d += 4*(x - y) + 10;

}

else {

x += 1;

d += 4 * x + 6;

}

for (int i = 0; i < 4; i++) {

glVertex2i(Rx + x * dir[i][0], Ry + y * dir[i][1]);

glVertex2i(Rx + y * dir[i][0], Ry + x * dir[i][1]);

}

}

glFlush();

glEnd();

}

辅助画圆函数

再为两个算法重载两个使用两个点作为参数的画圆函数，来丰富画圆的方式：

void Mid_Circle(int Rx, int Ry, int endx, int endy) {

int distance = static_cast(sqrt((endx - Rx) * (endx - Rx) + (endy - Ry) * (endy - Ry)));

Mid_Circle(Rx, Ry, distance);

}

void BRESENHAM_Circle(int Rx, int Ry, int endx, int endy) {

int distance = static_cast(sqrt((endx - Rx) * (endx - Rx) + (endy - Ry) * (endy - Ry)));

BRESENHAM_Circle(Rx, Ry, distance);

}

圆弧段扫描算法

完成了画圆的扫描算法，接下来学习的是圆弧的扫描算法，为了方便绘制，规定：画的圆弧是起始点在圆上沿顺时针行走得到。

先来对坐标轴进行分区：

我们只绘制0区域的这 \(\frac{1}{8}\)段圆弧，然后通过对称来绘制其他的区域。因为我们需要绘制的不再是所有的区域，所以我们需要对区域的位置进行辨别，当然，使用的位置是相对于圆心的位置。写一个函数来返回我们需要的区域id：

FIndIndexOfArc

GLint FIndIndexOfArc(GLint x, GLint y) {

if (x > 0 && y >= 0) {

if (x < y)return 0;

else return 1;

}

else if (x >= 0&&y<0) {

if (x > -y)return 2;

else return 3;

}

else if (x < 0 && y <=0) {

if (x > y)return 4;

else return 5;

}

else {

if (-x > y)return 6;

else return 7;

}

}

然后根据区域id我们计算需要的变换矩阵这里的变化是对称，不是旋转那么就会面临一个问题——起始段的绘制和结尾段的绘制会有所不同，这个体现在分段处理函数DrawCircleArc中：

GetMatrixT

void GetMatrixT(GLint T[2][2], GLint index) {

int i = index % 8;

if (i == 0) {

T[0][0] = 1, T[0][1] = 0,

T[1][0] = 0, T[1][1] = 1;

}

else if (i == 1) {

T[0][0] = 0, T[0][1] = 1,

T[1][0] = 1, T[1][1] = 0;

}

else if (i == 2) {

T[0][0] = 0, T[0][1] = 1,

T[1][0] = -1, T[1][1] = 0;

}

else if (i == 3) {

T[0][0] = 1, T[0][1] = 0,

T[1][0] = 0, T[1][1] = -1;

}

else if (i == 4) {

T[0][0] = -1, T[0][1] = 0,

T[1][0] = 0, T[1][1] = -1;

}

else if (i == 5) {

T[0][0] = 0, T[0][1] = -1,

T[1][0] = -1, T[1][1] = 0;

}

else if (i == 6) {

T[0][0] = 0, T[0][1] = -1,

T[1][0] = 1, T[1][1] = 0;

}

else if (i == 7) {

T[0][0] = -1, T[0][1] = 0,

T[1][0] = 0, T[1][1] = 1;

}

}

拿到两个点之后，我们首先获得他们的区域id，然后判断开始点的id是否小于结束点，如果大于，那么将结束点的id+8，也就是保证开始点的id小于结束点的id。再使用id去获取变换矩阵的时候，我们也要对id进行取模操作。假设我们得到的开始区间的id是a，结束区间的id是b，那么我们可以保证使用的两个id有着（\(a

/*分段处理的函数*/

/************************/

//ins和ine是开始和结束的id

if (ins == ine){

//绘制在同一个区域的圆弧

...

}

else{

//1.起始段画圆弧

...

//2.中间画弧段

...

//3.终止点画弧段

...

}

我们再写一个可以进行矩阵乘法和矩阵求逆的函数（我个人觉得这很浪费时间，但是这里还是这么写了。）

void GetTtoPt(GLint T[2][2], GLint sx, GLint sy, GLint& retx, GLint& rety, bool mode) {

if (mode) { //求逆

//主对角线互换除以行列式，副对角线乘-1，除以行列式

GLint T1[2][2], temp;

T1[0][0]=T[1][1];

T1[1][1] = T[0][0];

T1[1][0] = T[1][0]*-1 ;

T1[0][1] = T[0][1]*-1;

temp = T[0][0] * T[1][1] - T[1][0] * T[0][1];

retx = (sx * T1[0][0] + sy * T1[0][1])/temp;

rety = (sx * T1[1][0] + sy * T1[1][1])/temp;

}

else {

retx = (sx * T[0][0] + sy * T[0][1]) ;

rety = (sx * T[1][0] + sy * T[1][1]) ;

}

}

然后是进行弧段绘制的函数,在绘制任意区域内的一点圆弧时，我们先把目标点的坐标通过乘上变换矩阵的逆矩阵来得到第0区域中对应的点。把目标点绘制之后，在变换到对应的区域。

SetArc

//绘制弧段

/**************/

void SetArc(GLint Rx, GLint Ry, GLint R, GLint ArcType, GLint T[2][2], GLint startx, GLint starty, GLint endx, GLint endy){

GLint x, y, d;

GLint p0x, p0y, p1x, p1y;

glBegin(GL_POINTS);

//ArcType解释：

//0 画1/8圆 是连续段的中部

//1 画0到start圆 是奇数段的开始 偶数段的结束

//2 画start到1/8x圆 是偶数段的开始 奇数段的结束

//3 画start到end圆 是连续段的全部

if (ArcType == 0 || ArcType == 1) {

x = 0;

y = R;

d = 5 - 4 * R;

glColor3f(1.0, 0, 0);

}

else {

glColor3f(0, 1.0, 0);

x = startx;

y = starty;

d = 8 * x - 4 * y + 5;

}

p0x = x, p0y = y;

//投影到第0区域

GetTtoPt(T, p0x,p0y, p1x,p1y);

glVertex2i(Rx + p1x, Ry - p1y);

while (1) {

if (ArcType == 0 || ArcType == 2) { //生成到镜像线八分之一处。

if (x > y)break;

}

else if(ArcType==1){ //生成（0,R）到start的圆弧

glColor3f(0, 1.0, 0);

if (x > startx)break;

}

else if (ArcType == 3) { //生成到end的圆弧

glColor3f(0, 0, 1.0);

if (x > endx)break;

}

//中点画圆法

if (d >= 0) {

x += 1, y -= 1;

d += 8 * (x - y) + 20;

}

else {

x += 1;

d += 8 * x + 12;

}

p0x = x;

p0y = y;

//从第0区域回到绘制区域

GetTtoPt(T, p0x, p0y, p1x, p1y);

glVertex2i(Rx + p1x, Ry - p1y);

}

glColor3f(1.0, 0, 0);

glFlush();

glEnd();

}

最后补充分段处理的函数和它的辅助绘制函数，注意，因为glut中的坐标默认是y轴朝下，所以在绘制的时候可以进行反转y轴的方式来进行纠正。

DrawCircleArc

void DrawCircleArc(GLint Rx,GLint Ry,GLint R,GLint startx,GLint starty,GLint endx,GLint endy) {

//圆心移动到原点，并把y轴反转

GLint sx = startx-Rx, sy = Ry-starty, ex = endx-Rx, ey = Ry-endy;

//第一步查找两个端点所在区域编号

GLint T[2][2], T1[2][2];

GLint pt0x=0, pt0y=0, pt1x=0, pt1y=0;

//找到对应的区间编号（使用移动后的坐标）

GLint ins = FIndIndexOfArc(sx, sy);

GLint ine = FIndIndexOfArc(ex, ey);

//保证结束区域的值大于开始区域，最后使用index%8得到计算区域

if (ine < ins)ine += 8;

if (ins == ine) {//同一个区域

//首先镜像到0号区域，然后镜像到对应的区域

GetMatrixT(T, ins); //获得0区域的镜像矩阵

GetTtoPt(T, sx, sy, pt0x, pt0y, GL_TRUE);

GetTtoPt(T, ex, ey, pt1x, pt1y, GL_TRUE);

if (pt0x < pt1x) {//保证了startx <= endx

SetArc(Rx, Ry, R, 3, T, pt0x, pt0y, pt1x, pt1y); //画弧线上的一段，从pt0到pt1

}

else {

SetArc(Rx, Ry, R, 3, T, pt1x, pt1y, pt0x, pt0y);

}

}

else {

//1.起始段画圆弧

GetMatrixT(T, ins);

GetTtoPt(T, sx, sy, pt0x, pt0y, GL_TRUE);

if (!(ins % 2)) {

SetArc(Rx, Ry, R, 2, T, pt0x, pt0y); //画弧线上的一段，从(0 ,R )到pt1

}

else {

SetArc(Rx, Ry, R, 1, T, pt0x, pt0y);

}

//2.中间画弧段

for (int i = ins + 1; i < ine; i++) {

GetMatrixT(T1, i);

SetArc(Rx, Ry, R, 0, T1); //画整段弧线

}

//3.终止点画弧段

GetMatrixT(T, ine);

GetTtoPt(T, ex, ey, pt1x, pt1y, GL_TRUE);

if (!(ine % 2)) {

SetArc(Rx, Ry, R, 1, T, pt1x, pt1y); //画弧线上的一段，从(0 ,R )到pt1

}

else {

SetArc(Rx, Ry, R, 2, T, pt1x, pt1y);

}

}

}

//辅助绘制函数

void DrawCircleArc(GLint P1x, GLint P1y, GLint P2x, GLint P2y, GLint P3x, GLint P3y) {

GLint x, y, radius;

x = P1x, y = P1y;

radius = static_cast(sqrt((P1x - P2x) * (P1x - P2x) + (P1y - P2y) * (P1y - P2y)));

double distance = sqrt((P3x - P1x) * (P3x - P1x) + (P3y - P1y) * (P3y - P1y));

P3x = static_cast(((P3x - P1x) * radius)/ distance + P1x);

P3y = static_cast(((P3y - P1y) * radius)/ distance + P1y);

DrawCircleArc(x, y, radius, P2x, P2y, P3x, P3y);

}

下/上一篇

上一篇：绘制直线的算法

下一篇：橡皮筋技术