掃描線演算法

『壹』 寫出直線段掃描轉換的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軸的線怎麼辦

由於三角形的形狀和位置,主要是靠三個頂點確定的. 那麼是不是可以先找三個頂點,只要找到三個頂點就行了呢. 僅供參卡.