扫描线算法

‘壹’ 写出直线段扫描转换的Bresenham算法，并生成从点P1（0,0）到点P2 (5,2)的直线段，要求写出每一步递推过程

没分？····不过既然我有现成的那就给你吧，不过复制粘贴而已！

Bresenham算法是Bresenham提出的一种光栅线生成算法！DDA算法表面上看起来很有效，并且代码也比较容易实现，但是显示每个像素都需要进行一次浮点数加法运算，而Bresenham算法的最大优点是不需要进行浮点数运算！这是一种精确而有效的光栅线生成算法，该算法仅使用增量整数计算，计算速度比DDA要快，另外，Bresenham算法还可用于显示圆和其他曲线，这里暂时只显示直线！

与DDA一样，我们假设线段的两个端点坐标是整数值（x0,y0）（xEnd,yEnd）,且斜率m满足0<=m>=1!坐标轴的垂直轴表示扫描线位置，水平轴标识像素列，假设以单位x间隔取样，需要确定下一个每次取样时两个可能的像素位置中的哪一个更接近于线路径！

从给定线段的左端点（x0,y0）开始,逐步处理每个后继列（x位置），并在其扫描线y值最接近线段的像素处描出一点，假如已经确定要显示的像素在（xk,yk），那么下一步就要确定在列xk+1=xk+1上绘制哪个像素，是在位置(xk+1,yk)还是在(xk+1,yk+1)

在取样位置xk+1，我们使用dlower和pper来标识两个像素与数学上线路径的垂直偏移，在像素列xk+1处的直线上的y坐标根据直线方程可计算得：

y=m(xk+1)+b

那么可求得：

dlower=y-yk=m(xk+1)+b-yk

pper=(yk+1)-y=yk+1-m(xk+1)-b

令斜率m=dy/dx,引入决策参数Pk，定义为：

Pk=dx(dlower-pper)

=2dx*xk-2dy*yk+c

C是一个常数，值为2dx+dx(2b-1)

由此可以计算得到

pk+1=Pk+2dy-2dx(yk+1-yk)

其中yk+1-yk取0还是取1取决于参数Pk的符号，Pk为负时取0，Pk非负时取1！

而Pk为负时，下一个要绘制的点就是（xk+1,yk）且pk+1=Pk+2dy

Pk为非负时则下一个要绘制的点就是（xk+1,yk+1）且pk+1=Pk+2dy-2dx

至此，Bresenham算法介绍完毕，以下为某个示例：

#include<gl/glut.h>

#include<math.h>

#include<stdio.h>

voiddraw_pixel(intix,intiy)

{

glBegin(GL_POINTS);

glVertex2i(ix,iy);

glEnd();

}

voidBresenham(intx1,inty1,intxEnd,intyEnd)

{

intdx=abs(xEnd-x1),dy=abs(yEnd-y1);

intp=2*dy-dx;

inttwoDy=2*dy,twoDyMinusDx=2*dy-2*dx;

intx,y;

if(x1>xEnd)

{

x=xEnd;y=yEnd;

xEnd=x1;

}

else

{

x=x1;

y=y1;

}

draw_pixel(x,y);

while(x<xEnd)

{

x++;

if(p<0)

p+=twoDy;

else

{

y++;

p+=twoDyMinusDx;

draw_pixel(x,y);

}

}

}

voiddisplay()

{

glClear(GL_COLOR_BUFFER_BIT);

Bresenham(0,0,400,400);//这是我的线段两端点的坐标，你可以换成Bresenham(0,0,5,2),

//不过估计很短，看不清

glFlush();

}

voidmyinit()

{

glClearColor(0.8,1.0,1.0,1.0);

glColor3f(0.0,0.0,1.0);

glPointSize(1.0);

glMatrixMode(GL_PROJECTION);

glLoadIdentity();

gluOrtho2D(0.0,500.0,0.0,500.0);

}

voidmain(intargc,char**argv)

{

glutInit(&argc,argv);

glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);

glutInitWindowSize(500,500);

glutInitWindowPosition(200.0,200.0);

glutCreateWindow("CG_test_Bresenham_Lineexample");

glutDisplayFunc(display);

myinit();

glutMainLoop();

}

程序运行效果如图：

‘贰’ 扫描线填充算法与种子填充算法的区别是什么

种子优点是非常简单，缺点是需要大量栈空间来存储相邻的点。

改进的方法就是：通过沿扫描线填充水平像素段，来处理四连通或八连通相邻点，这样就仅仅只需要将每个水平像素段的起始位置压入栈，而不需要将当前位置周围尚未处理的相邻像素都压入栈，从而可以节省大量的栈空间。

‘叁’ 计算机图形学-扫描线算法-课程设计

这类也不难。

‘肆’ 求C源码：计算机图形学程序——扫描线算法

这是我以前上学的时候写的，你改改，凑活用巴。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

#include <graphics.h>
#include <stdio.h>
#include <dos.h>
#include <math.h>
#include <bios.h>
#include <string.h>

void parspl ( int p[10000][2] , long n , int precision , int color )
{
int x = 0 , y = 0 , i = 0 , j = 0 , m = 0 ;
double t2 = 0 , t3 = 0 , t = 0 , a , b , c , d , e = p[1][0] + 5 , f = p[1][1] + 5 ;
setcolor ( color ) ;
m=n+1;
p[0][0] = p[n][0] ;
p[0][1] = p[n][1] ;
p[m][0] = p[1][0] ;
p[m][1] = p[1][1] ;
p[m+1][0] = p[2][0] ;
p[m+1][1] = p[2][1] ;
moveto ( p[1][0] , p[1][1] ) ;
for ( i = 0 ; i < n ; i ++ )
{
t = 0.5 / precision ;
for ( j = 1 ; j < precision ; j ++ )
{
t2 = t * t ;
t3 = t2 * t ;
a = 4 * t2 - t - 4 * t3 ;
b = 1 - 10 * t2 + 12 * t3 ;
c = t + 8 * t2 - 12 * t3 ;
d = 4 * t3 - 2 * t2 ;
x = a * p[i][0] + b * p[i+1][0] + c * p[i+2][0] + d * p[i+3][0] ;
y = a * p[i][1] + b * p[i+1][1] + c * p[i+2][1] + d * p[i+3][1] ;
lineto ( x , y ) ;
line ( e , f , x + 5 , y + 5 ) ;
moveto ( x , y ) ;
t += 0.5 / precision ;
e = x + 5 ;
f = y + 5 ;
}
lineto ( p[i+2][0] , p[i+2][1] ) ;
moveto ( e , f ) ;
lineto ( p[i+2][0] + 5 , p[i+2][1] + 5 ) ;
moveto ( p[i+2][0] , p[i+2][1] ) ;
}
}

int main()
{
long n = 5 ;
char pwd[4] ;
int p[100][2] ;
int a1 , a2 , b1 , b2 , c1 , c2 , d1 , d2 , e1 , e2 ;
int gdriver = VGA , gmode = VGAHI ;
initgraph( &gdriver , &gmode , "c:\\tc" ) ;
setbkcolor ( 0 ) ;
a1 = p[1][0] = 320 ;
a2 = p[1][1] = 240 ;
b1 = p[2][0] = 320 ;
b2 = p[2][1] = 120 ;
c1 = p[3][0] = 452 ;
c2 = p[3][1] = 128 ;
d1 = p[4][0] = 382 ;
d2 = p[4][1] = 388 ;
e1 = p[5][0] = 364 ;
e2 = p[5][1] = 280 ;
loop:
if ( a1 <= p[1][0] && p[1][0] <= 520 )
{
a1 = p[1][0] ;
p[1][0] += 1 ;
}
else
{
if ( p[1][0] >= 120 )
{
a1 = p[1][0] ;
p[1][0] -= 1 ;
}
else
a1 = p[1][0] = 120 ;
}
if ( a2 >= p[1][1] && p[1][1] >= 60 )
{
a2 = p[1][1] ;
p[1][1] -= 2 ;
}
else
{
if ( p[1][1] <= 420 )
{
a2 = p[1][1] ;
p[1][1] += 2 ;
}
else
a2 = p[1][1] = 420 ;
}
if ( b1 >= p[2][0] && p[2][0] >= 120 )
{
b1 = p[2][0] ;
p[2][0] -= 2 ;
}
else
{
if ( p[2][0] <= 520 )
{
b1 = p[2][0] ;
p[2][0] += 2 ;
}
else
b1 = p[2][0] = 520 ;
}
if ( b2 <= p[2][1] && p[2][1] <= 420 )
{
b2 = p[2][1] ;
p[2][1] += 1 ;
}
else
{
if ( p[2][1] >= 60 )
{
b2 = p[2][1] ;
p[2][1] -= 1 ;
}
else
b2 = p[2][1] = 60 ;
}
if ( c1 <= p[3][0] && p[3][0] <= 520 )
{
c1 = p[3][0] ;
p[3][0] += 1 ;
}
else
{
if ( p[3][0] >= 120 )
{
c1 = p[3][0] ;
p[3][0] -= 1 ;
}
else
c1 = p[3][0] = 120 ;
}
if ( c2 <= p[3][1] && p[3][1] <= 420 )
{
c2 = p[3][1] ;
p[3][1] += 1 ;
}
else
{
if ( p[3][1] >= 60 )
{
c2 = p[3][1] ;
p[3][1] -= 1 ;
}
else
c2 = p[3][1] = 60 ;
}
if ( d1 >= p[4][0] && p[4][0] >= 120 )
{
d1 = p[4][0] ;
p[4][0] -= 1 ;
}
else
{
if ( p[4][0] <= 520 )
{
d1 = p[4][0] ;
p[4][0] += 1 ;
}
else
d1 = p[4][0] = 520 ;
}
if ( d2 >= p[4][1] && p[4][1] >= 60 )
{
d2 = p[4][1] ;
p[4][1] -= 1 ;
}
else
{
if ( p[4][1] <= 420 )
{
d2 = p[4][1] ;
p[4][1] += 1 ;
}
else
d2 = p[4][1] = 420 ;
}
if ( e1 <= p[5][0] && p[5][0] <= 520 )
{
e1 = p[5][0] ;
p[5][0] += 1 ;
}
else
{
if ( p[5][0] >= 120 )
{
e1 = p[5][0] ;
p[5][0] -= 1 ;
}
else
e1 = p[5][0] = 120 ;
}
if ( e2 <= p[5][1] && p[5][1] <= 420 )
{
e2 = p[5][1] ;
p[5][1] += 2 ;
}
else
{
if ( p[5][1] >= 60 )
{
e2 = p[5][1] ;
p[5][1] -= 2 ;
}
else
e2 = p[5][1] = 60 ;
}
parspl ( p , n , 100 , 4 ) ;
parspl ( p , n , 100 , 4 ) ;
if ( bioskey ( 1 ) > 0 )
{
printf ("Please Input Password:") ;
gets (pwd) ;
if ( !strcmp(pwd,"cmy") )
{
clearviewport () ;
closegraph () ;
return 1 ;
}
}
cleardevice () ;
goto loop ;
}

‘伍’ 求助：谁有C++的多边形扫描线填充算法的源代码！

typedef struct tEdge
{ int yUpper;
float xIntersect,dxPerScan;
struct tEdge *next;
}Edge;
void insertEdge(Edge *list Edge *edge)//将结点插入边表
{
Edge *p,*q=list;
p=q->next;
while (p!=NULL)
{ if (edge->xIntersect<p->xIntersect) p=NULL;
else { q=p; p=p->next;}
}
edge->next=q->next;
q->next=edge;
}

int yNext(int k,int cnt, dcPt *pts)//求奇异点
{
int j;
if ((k+1)>(cnt-1)) j=0;
else j=k+1;
while (pts[k].y==pts[j].y)
if((j+1)>(cnt-1)) j=0;
else j++;
return (pts[j].y);
}

void makeEdgeRec(dcPt lower,dcPt upper,int yComp, Edge *edge, Edge *edges[]) //生成边表结点，并插入到边表中
{
edge->dxPerScan=(float)(upper.x-lower.x)/(upper.y-lower.y);
edge->xIntersect=lower.x;
if (upper.y<yComp)
edge->yUpper=upper.y-1;
else
edge->yUpper=upper.y;
insertEdge(edges[lower.y],edge);
}

void buildEdgeList(int cnt,dcPt *pts, Edge *edges[])//创建边表的主体函数
{
Edge *edge;
dcPt v1,v2;
int i,yPrev=pts[cnt-2].y;
v1.x=pts[cnt-1].x; v1.y=pts[cnt-1].y;
for (i=0;i<cnt;i++)
{ v2=pts[i];
if (v1.y!=v2.y)
{ edge=(Edge *)malloc(sizeof(Edge));
if (v1.y<v2.y)
makeEdgeRec(v1,v2,yNext(i,cnt,pts),edge,edges);
else makeEdgeRec(v2,v1,yPrev,edge,edges);
}
yPrev=v1.y;
v1=v2;
}
}

void buildActiveList(int scan,Edge * active,Edge *edges[])//建立活动边表的主题函数
{ Edge *p,*q;
p=edges[scan]->next;
while (p)
{ q=p->next;
insertEdge(active,p);
p=q;
}
}

void fillScan(int scan,Edge *active)//填充一对交点
{
Edge *p1,*p2;
int i
p1=active->next;
while(p1)
{
p2=p1->next;
for (i=p1->xIntersect;i<p2->xIntersect;i++)
setPixel((int)i,scan);
p1=p2->next;
}
}

void delectAfter(Edge *q)//删除链表中结点
{
Edge *p=q->next;
q->next=p->next;
free(p);
}

void updateActiveList(int scan,Edge *active)//填充完后，更新活动边表
{
Edge *q=active,*p=active->next;
while (p)
if (scan>=p->yUpper)
{
p=p->next;
deleteAfter(q);
}
else
{ p->xIntersect=p->xIntersect+p->dxPerScan;
q=p;
p=p->next;
}
}

void resortActiveList(Edge *active)//对活动边表结点重新排序
{
Edge *q,*p=active->next;
active->next=NULL;
while(p)
{ q=p->next;
insertEdge(active,p);
p=q;
}
}

void scanFill(int cnt,dcPt *pts)//多边形填充主体程序
{
Edge *edge[WINDOW_HEIGHT],*active;
int i,scan;
for (i=0;i<WINDOW_HEIGHT;i++)
{
edges[i]=(Edge *)malloc(sizeof(Edge));
edges[i]->next=NULL;
}
buildEdgeList(cnt,pts,edges);
active=(Edge *)malloc (sizeof(Edge));
active->next=NULL;
for(scan=0;scan<WINDOW_HEIGHT;scan++)
{
buildActiveList(scan,active,edges);
if (active->next)
{fillScan(sacn,active);<br/> updateActiveList(scan,active);<br/> resortActiveList(active);<br/>}
}
}
}
}
}

‘陆’ 怎么用opengl扫描线算法填充多边形

扫描线算法是光栅图形学的内容，底层硬件实现。opengl是不会关注这种细节的。你写这样的代码
glBegin(GL_POLYGON);
glVertex3f(...);
...
glVertex3f(...);
glEnd();
画一个多边形，但底层的光栅化到底是怎么实现的，是否使用扫描线算法，你是不可以控制的。

‘柒’ 扫描线种子填充算法中，每次压入栈的像素最多有几个

19" 宽屏 16Bits 颜色 1440*900*2 =2M 1M =Screen/2;100M =50Screen
19" 宽屏 24Bits 颜色 1440*900*3 = 3888000=3M 1M =Screen/3;100M =33Screen

19" 宽屏 32Bits 颜色 1440*900*4 = 3888000=4M 1M =Screen/4;100M =25Screen

23" 宽屏 32Bits 颜色 1920*1080*4=8M 1M =Screen/8;100M =12Screen
堆栈不宜过大，64M已经很大了。
图像数据还是放在堆空间吧！

‘捌’ 求c语言扫描线填充算法代码 事成再加100分

早讲啊，删了:(

这有个，一般能摆到的我都不求人
http://tieba..com/f?kz=194814414

pudn上搜呗，多的一塌糊涂

‘玖’ 急求消隐算法源代码，最好是扫描线算法

http://www.wol.net.pk/mtshome/index.html

‘拾’ x扫描线算法平行于x轴的线怎么办

由于三角形的形状和位置,主要是靠三个顶点确定的. 那么是不是可以先找三个顶点,只要找到三个顶点就行了呢. 仅供参卡.