计算机图形学各种算法
- 格式：doc
- 大小：27.00 KB
- 文档页数：2
1.线面遮挡算法 1）视点和线段在给定平面的同侧，线段不被给定平面遮挡。 2）线段的投影和平面的投影的包围盒不相交，线段不被平面遮挡。 3）计算直线与平面是否相交。若无相交转4）；否则交点在线段的内部或外部。若交点在线段内部，交点将线段分为两段，与视点同侧的一段不被遮挡，另一段在视点异侧，转4）；若交点在线段外部，转4）。 4）求所剩线段的投影和平面边界的投影的所有交点，根据交点在原直线参数方程中的参数值求出Z值。若无交点，转4）。 5）所求的各交点将线段的投影分为若干段，求出第一段中点。 6）若第一段中点在平面的投影内，则相应的段被遮挡，否则不被遮挡，其他段依次交替取值进行判断。 7）算法结束。 2.深度排序算法 1）把所有的多边形按顶点最大z坐标值进行排序。 2）解决当多边形在z坐标范围内发生交迭时出现的不明确问题。 3）按最大z坐标值逐次减小的次序，对每个多边形进行扫描转换。 3.Z-缓冲算法： 更新缓冲区置成背景色； Z-缓冲区置成最大z值； For(各个多边形) {扫描转换该多边形； For(计算多边形所覆盖的每个像素(x,y)) {计算多边形在该像素的深度值z(x,y); If(z(x,y)小于z缓冲区中的(x,y)处的值) {把z(x,y)存入z缓冲区中的(x,y)处； 把多边形在(x,y)处的颜色值存入更新缓存区的(x,y)处；}}} 4.Z—缓冲算法的改进，只用一个缓冲存储器实现消隐 Z-Buffer() {帧缓存全置为背景色； For(屏幕上的每个像素(i,j) {深度缓存变量zb置最大值MaxValue; For(多面体上的每个多边形Pk) {if(像素点(i,j)在pk的投影多边形之内） {计算Pk在(i,j)处的深度值depth; If(depth
{add(v1,Q);S1=delete(v1,S);S
1=delete(u,S1);
D=vector(u,v1);u=v1;v1=wap
ping(u,d,S1);}}
6.简单多边形三角剖分
Void
Simple_polygon_triangulation
(POINT *P,int n)
{Q0=P,m=n;
While(m<3)
{Q1=next(Q0);Q2=next(Q1);
If(Test(Q0,Q1,Q2){输出三
角形
Q0Q1Q2;m--;delete(Q1);}
Else Q0=Q1;}
输出Q0开始的剩下的三角
形；}
7.凸多边形包含算法
Int inner1(POINT p[],int
n,POINT q)
{int i,j,k; i=1;j=n-1;
While(j-i>1)
{k=(i+j)/2;
If(test(q,p,0,k)==0) return
1;
else(test(q,p,0,k)==1) return
0;
else(test(q,p,0,k)==2) i=k;
else(test(q,p,0,k)==3) j=k;
if(test3(q,p,0,i,j)) return 1;
Else return 0;}
8.凸多边形重叠计算
Void advance(POINT P[],int
l,POINT Q[];int m)
{int s; s=vector3(P,Q,i,j);
If(s>=0){
If((left(P,i,Q,j)&&left(Q,j,P,i))|
|(right(P,i,Q,j)&&left(Q,j,P,i)))
{if(i<1) ++i;else i=1;}
Else if(j
If((right(P,i,Q,j)&&left(Q,j,P,i)
)||(right(P,i,Q,j)&&right(Q,j,P,i
)))
{if(i<1) ++i;else i=1;}
Else if(j
Void DDALine(int x1,int
y1,int x2,int y2)
{ double dx,dy,e,x,y;
dx=x2-x1;dy=y2-y1;
e=(fabs(dx)>fabs(dy))?fabs(
dx):fabs(dy);
dx/=e;dy/=e;x=x1;y=y1;
for(int i=0;i<=e;i++)
{SetPixel((int)(x+0.5),(int)(y
+0.5),color);
x+=dy;y+=dy;}}
10.中点划线
MidpointLine(int x0,int y0，
int x1,int y1)
{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;
SetPixel(x,y,color);
while(x
x++;y++;d+=delta2;}
else{
x++;d+=delta1;}
SetPixel(x,y,color);}}
11.BresenhamLine
void B(int x1,int y1,int x2,int
y2)
{int x,y,dx,dy,p;
x=x1;y=y1;
dx=x2-x1;dy=y2-y1;
P=2*dy-dx;
for(;x<=x2;x++){
SetPixel(x,y,color);
If(p>=0){
y++;p+=2*(dy-dx);}
else{p+=2*dy;}}}
