先求dx=x_1-x_0,dy=y_1-y_0 ;
再求e = (|dx|>|dy|)?|dx|:|dy|
令 dx = e/dx,dy = e/dy ;
后续点的产生:x = x+dx,y = y+dy .
void DDALine(int x0,int y0,int x1,int y1){
double dx = x1-x0;
double dy = y1-y0;
double e = fabs(dx)>fabs(dy)?fabs(dx):fabs(dy);
dx /= e;
dy /= e;
double x = x0;
double y = y0;
for(int i=0;i<e;i++){
printf("x=%d,y=%d\n",(int)(x+0.5),(int)(y+0.5));
x += dx;
y += dy;
}
}
先求a=y0-y_1,b=x_1-x_0 ;
再求d = 2a+b ;
令 \Delta_{1} = 2a,\Delta_{2} = 2(a+b) ;
b后续点的产生:如果d>0x=x+1,y=y,并且更新d=d+\Delta_{1},否则,x=x+1,y=y,并且更新d=d+\Delta_{2} .
void MidpointLine(int x0,int y0,int x1,int y1){
int x0=0,x1=5,y0=0,y1=2;
int a,b,delta1,delta2,d,x,y;
a = y0-y1;
b = x1-x0;
d = 2*a + b;
delta1 = 2*a;
delta2 = 2*(a+b);
x = x0;
y = y0;
printf("x=%d,y=%d\n",x,y);
while(x<x1){
x++;
if(d<0){
y++;
d+=delta2;
}else {
d+=delta1;
}
printf("x=%d,y=%d\n",x,y);
}
}
先求dx,dy;
再求p=2dy-dx ;
后续的点:如果p>=0,p=p+2(dy-dx),否则,p=p+2dy .
void BresenhamLine(int x0,int y0,int x1,int y1){
int p,x,y,dx,dy;
x=x0;
y=y0;
dx = x1-x0;
dy = y1-y0;
p = 2*dy-dx;
while(x<=x1){
printf("x=%d,y=%d\n",x,y);
if(p>=0){
y++;
p+=2*(dy-dx);
}else{
p+=2*dy;
}
x++;
}
}
初始d=1.25-R .
每次判断d<0x=x+1,y=y-1 ,d = d+2x+3 ;否则取x=x+1 ,d=d+2(x-y)+5 .
如果是整数版本的,初值d = 1-R。
递增版本:初值\Delta_{x} = 3,\Delta_{y}=2-R-R ,d=d+\Delta_{x}+\Delta_{y},\Delta_{x}=\Delta_{x}+2,\Delta_{y}=\Delta_{y}+2
void MidpointCircle(int R){
int x=0,y=R;
double d=1.25-R;
printf("x=%d,y=%d",x,y);
while(x<y){
if(d<0){
d += 2*x+3;
}else {
d += 2*(x-y) + 5;
y--;
}
x++;
}
printf("x=%d,y=%d",x,y)
}
/**
* 递增版本
**/
void MidpointCircle(int R){
int x=0,y=R,d=1-R;
int deltax=3,deltay=2-R-R;
printf("x=%d,y=%d",x,y);
while(x<y){
if(d<0){
d += deltax;
deltax+=2;
}else {
d += deltax+deltay;
deltax+=2;
deltay+=2;
}
y--;
x++;
}
printf("x=%d,y=%d",x,y)
}
判别式p1=3-2R ,如果p_i<0p_{i+1}=p_i +4x+6 .否则选D点,p_{i+1}=p_i+4(x_i-y_i)+10。
void bresenham(int R){
int x,y,p;
x=0;
y=R;
p=3-2*R;
for(;x<=y;x++){
if(p>=0){
p+=4*(x-y)+10;
y--;
}else {
p+=4*x+6;
}
}
}
void Polygonfill(Edge ET, COLORREF color){
1.y=ET中登记项对应的y坐标的最小值;
2.AET初始化为空表;
3.while(ET表非空或AET表非空){
3.1 将ET表登记项y对应的各“吊桶”合并到AET表中,将AET中各“吊桶”按x坐标递增排序;
3.2 在扫描线y上,按照AET提供的x坐标对,用color值实施填充;
3.3 将AET中有y=y_max的各项清除出表;
3.4 对AET中留下的各项,分别将x替换为x+1/m,这是求出AET中各边与下一条扫描线交点的x坐标;
3.5 由于前一步可能破坏了AET中各项x坐标的递增次序,故按x坐标重新排序;
3.6 y++,去处理下一条扫描线;
}
}
ET表和AET表的数据结构是一个链表;
y_max | x_min | 斜率 | 指针 |
---|---|---|---|
###图形变换
二维齐次变换矩阵 $$ \begin{Bmatrix} a & d & g \ b & e & h\ c & f & i \end{Bmatrix} $$
$$ \begin{Bmatrix} 1 & 0 & 0 \ 0 & -1 & 0\ 0 & 0 & 1 \end{Bmatrix} $$
绕y轴对称变换 $$ \begin{Bmatrix} -1 & 0 & 0 \ 0 & 1 & 0\ 0 & 0 & 1 \end{Bmatrix} $$
三维齐次变换矩阵 $$ \begin{Bmatrix} a_{11} & a_{12} & a_{13} & a_{14} \ a_{21} & a_{22} & a_{23} & a_{24} \ a_{31} & a_{32} & a_{33} & a_{34} \ a_{41} & a_{42} & a_{43} & a_{44} \ \end{Bmatrix} $$