计算机图形学期末复习资料.docx

图形与图像的关系？
答：图形是指由外部轮廓线条构成的矢量图。即由计算机绘制的直线、圆、矩形、 曲线、图表等；而图像是由扫描仪、摄像机等输入设备捕捉实际的画面产生的数字图像，是由像素点阵构成的位图。
位图图像由像素点组合而成；色彩丰富、过渡自然；保存时计算机需记录每个像素点的位置和颜色，所以图像像素点越多（分辨率高），图像越清晰，文件就越大。一般能直接通过照相、扫描、摄像得到图形都是位图图像。缺点：体积一般较大；放大图形不能增加图形的点数，可以看到不光滑边缘和明显颗粒，质量不容易得到保证 矢量图形由数学公式表达的线条所构成；线条非常光滑流畅，放大图形，其线条依然可以保持良好的光滑性及比例相似性，图形整体不变形；占用空间较小。工程设计图、图表、插图经常以矢量图形曲线来表示。
随机扫描与光栅扫描？
答：随机扫描显示器显示图形时，电子束的移动方式是 随机的,电子束可以在任意方向上自由移动，按照显示命令用画线的方式绘出图形，因此也称矢量显示器。而光栅扫描显示器显示图形时，电子束依照固定的扫描线和规定的扫描顺序进行扫描。电子束先从荧光屏左上角开始，向右扫一条水平线，然后迅速地回扫到左边偏下一点的位置，再扫第二条水平线，照此固定的路径及顺序扫下去，直到最后一条水平线，即完成了整个屏幕的扫描。随机扫描显示器依靠显示文件对屏幕图形进行刷新；光栅扫描显示器是靠帧缓存实现对屏幕图形的刷新。
窗口与视口？
答：窗口：就是用窗口的边界去裁剪数据并获得所需要的部分。二维情况下窗口由一个矩形上下左右四条边确定。
视口：是显示设备上用于显示窗口内图形数据的一个区域。二维规则视口由一个矩形上 下左右四条边确定。

图形系统初始化
#include
main(){
int driver=DETECT,mode; //适配器驱动程序设为自动检测,图形显示模式为0
initgraph(&driver,&mode,”c:\\tc”);
……
closegraph(); //关闭图形系统
}

颜色
设置背景色void setbkcolor(int color)
设置画笔色void setcolor(int color)
返回背景色int getbkcolor()
返回画笔色int getcolor()
返回点的颜色int getpixel(int x,int y)
0
1
2
3
4
5
6
7
BLACK
BLUE
GREEN
CYAN青
RED
MAGENTA洋红
BROWN
LIGHTGRAY
8
9
10
11
12
13
14
15
DARKGRAY
LIGHTBLUE
LIGHTGREEN
LIGHTCYAN
LIGHTRED
LIGHTMAGENTA
YELLOW
WHITE
设置线格式void setlinestyle(int linestyle,unsigned upattern,int thickness)
linestyle样式
SOLID-LINE
0
实线
DOTTED-LINE
1
点线
CENTER-LINE
2
中心线
DASHED-LINE
3
虚线
USERBIT-LINE
4
自定义线
upattern仅在自定义线时有效,默认为0
thickness线宽
NORM-WIDTH
1
一个像素宽
THICK-WIDTH
3
三个像素宽

点
画点 void putpixel(int x,int y,int color)
指定点 void moveto(int x,int y) 50,30 当前坐标50,30
相对画点 void moverel(int dx,int dy) 10,20 当前坐标60,50
获取坐标int getx() int gety()

直线
2个点画线void line(int x0,int y0,int x1,int y1)
从已有点画线到指定坐标lineto(int x,int y)
相对画线linerel(int dx,int dy)

矩形
画矩形void rectangle(int 左上角x,int 左上角y,int 右下角x,int 右下角y)

圆,圆弧椭圆
画圆void circle(int x,int y,int r) 指定圆心和半径
画同心圆弧void arc(int x,int y,int sangle,int eangle,int r)
指定圆心半径,从开始角到终止角画弧,角度0~360即圆
画异心圆弧void ellipse(int x,int y,int sangle,int eangle,int xr,int yr)
指定圆心,x方向半径,y方向半径,从开始角到终止角画弧,角度0~360即椭圆

多边形
画多边形void drawpoly(int num,int *polypoints)
num为顶点数
polypoints为各顶点的整数序列
若第一个和最后一个点坐标相同则画出多边形,否则为折线

int Round(float x){ return (int)(x<0?x-0.5:x+0.5); } //四舍五入

直线的生成算法
图形的扫描转换:在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程
直线DDA算法Digital Differential Analyser
void Line_DDA(int x1,int x2,int y1,int y2,int color)
{
int i=0;
float x,y; float dx,dy;
int steps=abs(x2-x1)>abs(y2-y1)?abs(x2-x1):abs(y2-y1);
x=(float)x1;
y=(float)y1;
dx=(float)(x2-x1)/steps; dy=(float)(y2-y1)/steps;
for(i=0;i使长线段计算的象素位置偏离实际线段
浮点运算十分耗时
简述 dda直线的数字微分分析法的算法与步骤？
答：直线生成算法中的数字微分分析法是一种增量计算方法。它使用数字微分分析器（通过同时在X方向和Y方向分别增加dx和dy成正比的小数值来积分微分方程的机械设备），按照斜率绝对值|k|<1和|k|>1来递增画描点。|k|<1时，取像素（x，（int）(y+0.5)；|k|>1时，取像素（（int）(x+0.5)，y)。其步骤为：1.选择dx或dy中的较大者为一个光栅单位Length；2.取Δy=dy/Length, Δx=dx/Length 3. 按照斜率绝对值|k|<1和k|>1来递增画描点。
直线Bresenham算法
void BRES(int x1,int y1,int x2,int y2,int color)
{
int x,y,dx,dy; int i=0;float p;
x=x1;y=y1;dx=x2-x1;dy=y2-y1;p=2*dy-dx;
for(i=0;i=0){y++;p=p-2*dx;} }
} (要保证x2>x1)
优点:不做除法,只用整数,只有整数加减和乘2运算
圆的生成算法
圆的Bresenham算法
void putdot(int x1,int y1,int x,int y,int color) //8方向对称画点
{
putpixel(x1+x,y1+y,color);
putpixel(x1+x,y1-y,color);
putpixel(x1-x,y1+y,color);
putpixel(x1-x,y1-y,color);
putpixel(x1+y,y1+x,color);
putpixel(x1+y,y1-x,color);
putpixel(x1-y,y1+x,color);
putpixel(x1-y,y1-x,color);
}
void BRESC(int x1,int y1,int r,int color)
{
int x,y;float p;x=0;y=r;p=5/4-r;
while(x<=y)
{
putdot(x1,y1,x,y,color);
if(p<0){p=p+x*2+3;}
else{p=p+2*(x-y)+5;y--;}
x++;
}
}
圆的生成——Bresenham算法及步骤？
答：考虑以坐标原点为圆心的第一四分圆，取x=0，y=R为起点按顺时针方向生成圆，假设圆心及起点均精确地落在像素点上。从圆上任意一点出发，按顺时针方向生成圆时，为了最佳逼近该圆，对于下一像素的的取法只有三种可能：右方mh，右下角md，下方mv。要在三个像素中选择一个使其与真正圆的距离的平方达到最小即可。结合圆与点(xi,yi)附近光栅网格相交关系的五种可能，找到最合适的像素点显示即为圆的Bresenham算法。其具体步骤为：1.判别圆心到右下角像素的距离和圆心到圆上点距离的平方之差Δi的正负性；2.根据第一步的结果，继续判别圆到mh,md距离的平方差δ。当Δi<0时，若δ≤0,取mh, 若δ>0,取md; 当Δi>0时，若δ≤0,取md, 若δ>0,取mv; 当Δi=0时，取md。

填色算法
扫描线填色算法:按扫描线顺序计算扫描线与多边形的相交区间,再用要求的颜色或图案显示这些区间的象素,需提供多边形各顶点坐标
1.用水平扫描线由上往下扫描多边形
2.每根扫描线与多边形各边产生一系列交点，采用递归算法
3.将交点按x坐标进入分类，将分类后的交点成对取出，作为两个端点，以所需要填的色彩画水平直线。
种子填色算法:要求给出边界颜色特征区域内的一个点的坐标
1.从(x,y)开始检测相邻位置以确定它们是否是边界颜色，若不是，则用填充颜色涂色，并检测其相邻位置。
2.直至检测完所有象素。
void seed_filling(x,y,fill_color,boundary_color)
{ int c;c=inquirecolor(x,y);
if((c<>boundary_color)&&(c<>fill_color))
{ setpixel(x,y,fill_color);
seed_filling(x,y+1,fill_color,boundary_color);
seed_filling(x,y-1,fill_color,boundary_color);
seed_filling(x-1,y,fill_color,boundary_color);
seed_filling(x+1,y,fill_color,boundary_color);}
}
种子填充算法？
答：从多边形区域的一个内点（种子）开始，由内向外用给定的颜色画点直到边界为止。如果边界是以一种颜色指定的，则种子填充算法可逐个像素地处理直到遇到边界颜色为止。种子填充算法常用四连通域和八连通域技术进行填充操作。从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。用这种方法填充的区域就称为四连通域；这种填充方法称为四向连通算法。从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。用这种方法填充的区域就称为八连通域；这种填充方法称为八向连通算法。

设置填充方式setfillstyle(int pattern,int color)
EMPTY-FILL
0
用背景色
SOLID-FILL
1
实心
LINE-FILL
2
粗水平线
LTSLASH-FILL
3
细斜线
SLASH-FILL
4
粗斜线
BKSLASH-FILL
5
粗反斜线
LTBKSLASH-FILL
6
细反斜线
HATCH-FILL
7
网格线
XHATCH-FILL
8
斜网格线
INTERLEAVE-FILL
9
隔点
WIDE-DOT-FILL
10
宽间断点
CLOSE-DOT-FILL
11
密间断点
USER-FILL
12
自定义
用当前样式填充
长方形bar(int x1,int y1,int x2,int y2)
3d长方形bar3d(int x1,int y1,int x2,int y2,int depth,int topflag)
depth垂直于屏幕方向上的深度
topflag,0画顶点,非0不画顶点
多边形fillpoly(int num,int *polypoints)
扇形pieslice(int x,int y,int sangle,int eangle,int r)
椭圆扇形sector(int x,int y,int sangle,int eangle,int xr,int yr)
种子floodfill(int x,int y,int border) border边界线颜色

文字
设置字体样式settextstyle(int font,int direction,int charsize)
font
DEFAULT-FONT
0
8*8点阵字
TRIPLEX-FONT
1
三元组
SMALL-FONT
2
小型字
SANSSERIF-FONT
3
无衬线
GOTHIC-FONT
4
粗黑体
direction 0从左到右 1从下到上
charsize放大因子,0~10整数
设置对齐方式settextjustify(int horiz,int vert)
horiz水平 0左对齐,1居中对齐,2右对齐
vert垂直 0底对齐,1垂直对齐,2顶对齐
输出文本outtext(char *text) outtextxy(int x,int y,char *text)

裁剪
Cohen-Sutherland直线裁剪算法_最早的线段裁剪算法
左右下上
1001
0001
0101
1000
0000
0100
1010
0010
0110
线段细分裁剪算法
答：（1）检查线段P1P2是否为完全可见或显然不可见；（2）若P1在窗口外，继续步骤（3），否则交换P1，P2；（3）用P1P2和窗口的交点取代P1点，并重复步骤（1）-（3）。
Sutherland和Hodgman多边形裁剪算法
用窗口的上边框对多边形进行裁剪,得到一个(或若干个)新的多边形,再用其余三条边框线对新产生的多边形裁剪
P,S在窗框非同侧,求交点I,将I保存在P前面;P在窗框内侧,保存P,否则不保存P
for(对第一个顶点直到最后一个顶点，逐一处理）
{ if(Pi在边界内侧)
{ if(flag!=0)
{ flag=0;
求交点并放入新的多边形顶点序列Qj中;
j++;
}
将当前顶点放入新的多边形顶点序列Qj中:Qj=Pi;
j
}
else
{ if(flag==0)
{ flag=1;
求交点并放入新的多边形顶点序列Qj中;
j++;
}
}
将当前顶点赋给S:S=Pi;
}

曲线生成
三次Bezier曲线,由4个控制点生成
Bezier的Casteljau算法
r=1,...,n i=0,...,n-r并且
即为Bezier曲线上参数t处的点

void draw_polygon(struct node coeff[])
{ int i;
for(i=0;i[0].x,coeff[0].y); lineto(coeff[i].x,coeff[i].y); }
}
struct node decasteljau(struct node coeff[],float t)
{ int i,r;
struct node point,coeffa[20];
for(i=0;i
coeffa[i].y=(1.0-t)*coeffa[i].y+t*coeffa[i+1].y; }
return coeffa[0];
}
void draw_bezier_curve(struct node coeff[])
{
int i,x,y;
float t,delta;
struct node point;
delta=1.0/(float)(npoints);
for(i=0,t=0;t<=1.0;i++,t=t+delta)
{ point=decasteljau(coeff,t);
if(i==0)moveto(point.x,point.y);
lineto(point.x,point.y); }
}

缩放因子
Sx=(Xvmax-Xvmin)/(Xwmax-Xwmin) w世界坐标系,v屏幕坐标系
Sy=(Yvman-Yvmin)/(Ywmax-Ywmin)
投影
透视变化方程: Xp=X[(Zprp-Zvp)/(Zprp-Z)]=X*dp/(Zprp-Z) dp=Zprp-Zvp是投影参考点
Yp=Y[(Zprp-Zvp)/(Zprp-Z)]=Y*dp/(Zprp-Z) 到观察平面的距离
当Zvp=0 Xp=X[Zprp/(Zprp-Z)]=X*1/(1-Z/Zprp)
Yp=Y[Zprp/(Zprp-Z)]=Y*1/(1-Z/Zprp)
当Zprp=0 Xp=X*Zvp/Z=X*1/(Z/Zvp)
Yp=Y*Zvp/Z=Y*1/(Z/Zvp)

逻辑输入设备
按数据类型:定位设备,描画设备,字符串设备,定值设备,选择设备,拾取设备
鼠标的使用功能
#include
0重置鼠标及取得其状态
1在屏幕上显示鼠标光标
2从屏幕上隐藏鼠标光标
3返回鼠标位置
4把鼠标移到确定位置
5检索上次调用之后一共按了多少次键
6检索上次调用之后一共释放多少次键
void mouse (int *m1,int *m2,int *m3,int *m4)
{ union REGS inregs,outregs;
inregs.x.ax=*m1;
inregs.x.bx=*m2;
inregs.x.cx=*m3;
inregs.x.dx=*m4;
int86(0x33,&inregs,&outregs);
*m1=outregs.x.ax;
*m2=outregs.x.bx;
*m3=outregs.x.cx;
*m4=outregs.x.dx;
}

初始化鼠标
int resetmouse(void)
{ m1,m2 ,m3,m4
m1=0;预设Mouse,如存在Mouse,m1返回1，否则返回0
mouse(&m1,&m2,&m3,&m4);
return(m1);
}
显示(隐藏)鼠标
void showmouse(void)
{ int m1,m2,m3,m4;
m1=1;显示为1,隐藏为2
mouse(&m1,&m2,&m3,&m4);
}
移动到指定位置
void movemouse(void)
{ int *x,*y;
m1=4;
mouse(&m1,&m2,x,y);
}

返回鼠标位置
void getmouse(void)
{ int *x;
int *y;
m1=3;
mouse(&m1,&m2,x,y);
}
检查一共按了几次鼠标
m2=0检查左键
m2=1检查右键
m3中返回x坐标
m4中返回y坐标
{ m1=5;
m2=0;
mouse(&m1,&m2,x,y);
}
检查一共释放了几次鼠标
按键动作数目返回到m2
{ m1=6;
m2=0;
mouse(&m1,&m2,&m3,&m4);
}

橡皮条技术:选择第一个线段端点,光标移动时从初始化拉出一线段,线段随光标移动直到选定第二个端点

#include
#include
#include
typedef struct
{ void (*Inits)();/*初始化鼠标驱动*/ 
 int  (*MButton)();/*按键位置与按键状态*/
 void (*MouseIco)();/*画鼠标光标*/
int  x;/*横向坐标*/
 int  y;/*竖向坐标*/
 int  ox;
 int  oy;
int  button;/*按键标志*/
}MOUSE;/*鼠标类*/
void mInits(); int mMButton(); void mMouseIco(); union REGS rg;
int main()
{ MOUSE *pM,mouse;
 int graphdrive=0,graphmode=0;
 int tracking=0,x1,y1,ox1,oy1;
 pM=&mouse;
 pM->Inits=mInits;
  pM->MButton=mMButton;
 pM->MouseIco=mMouseIco;
  initgraph(&graphdrive,&graphmode,"c:\\tc");
 setbkcolor(1);
  setwritemode(1);/*画线模式*/
  pM->Inits(&pM->x,&pM->y);
 pM->ox=pM->x;
 pM->oy=pM->y;
 do
 { pM->button=pM->MButton(&pM->x,&pM->y);
  pM->MouseIco(&pM->x,&pM->y,&pM->ox,&pM->oy);
  if(pM->button==1)
  { if(!tracking)/*捕捉开关*/
       { ox1=x1=pM->x; oy1=y1=pM->y; tracking=1; }
    if(pM->x!=ox1pM->y!=oy1)
{ line(x1,y1,ox1,oy1); ox1=pM->x; oy1=pM->y; line(x1,y1,pM->x,pM->y);}
  } else tracking=0;
}while(pM->button!=3);
}
void mInits(int *mx,int *my)
{ rg.x.ax=0;
 int86(0x33,&rg,&rg);
 if(rg.x.ax==0)
    exit(1);
 rg.x.ax=7;
  rg.x.cx=2;
 rg.x.dx=640;
 int86(0x33,rg,&rg);
 rg.x.ax=8;
 rg.x.cx=2;
  rg.x.dx=480;
 int86(0x33,&rg,&rg);
  rg.x.ax=4;
 *mx=rg.x.cx=640/2;
 *my=rg.x.dx=480/2;
 int86(0x33,&rg,&rg);
 rectangle(rg.x.cx-2,rg.x.dx-2,rg.x.cx+2,rg.x.dx+2);
}
int mMButton(int *lx,int *ly)
{ rg.x.ax=3;
 int86(0x33,&rg,&rg);
 *lx=rg.x.cx;
 *ly=rg.x.dx;
 return rg.x.bx;
}
void mMouseIco(int *x,int *y,int *oldx,int *oldy)
{ if(*x!=*oldx||*y!=*oldy)
{ rectangle(*oldx-2,*oldy-2,*oldx+2,*oldy+2);
  *oldx=*x; *oldy=*y;
  rectangle(*x-2,*y-2,*x+2,*y+2);
 }
}

消隐
消隐算法:对一个三维物体,从某视点观察;对若干个三维物体,物体之间相互遮挡;将对象表面上不可见的点,线,面消去,执行这种功能的算法,称消隐算法
判断面是否可见: DAB面,法向量n=DA*AB=(A-D)*(B-A) 都是向量
观察方向向量k=(0,0,1)
n*k<0不可见,>0可见
研究情况:
1原理上不复杂。
只需将物体上的所有线段与遮挡面进行遮挡测试，看线段是否被全部遮挡，部分遮挡或不被遮挡，然后画出线段的可见部分。
2消隐算法实现时要求适当的算法及大量的运算。
在60年代，消隐问题虽被认为是计算机图形学中的几大难问题之一。
3目前已提出仅十种算法，研究围绕算法正确，节省内存空间，加快运算速度等目标进行。
消隐算法分类:
按操作对象:
对象空间方法:将三维平面作为分析对象,通过比较各平面的参数来确定可见性
图象空间方法:比较象素投影到二维空间后的z值,确定其可见性
按应用分类:线消隐(线框图),面消隐(填色图)
线消隐
浮动水平算法Floating Horizon Algorithm
通过对某一变量(如z)的离散化,使原来的在三维空间中显示曲面的问题,转变为显示一系列曲线{F(x,y,zi)=0 i=0,1,…,n}的问题
从几何上看,这样做就是选取一组互相平等的平面:z=zi, i=0,1,...,n,使它们依次和原来要显示的曲面相交,显示这些交线,就相当于显示了原曲面
浮动水平线的算法思想？
其基本思想是，采用一系列与坐标平面平行的平面（X,Y或Z为定值）去切割曲面，把三维问题转化为二维问题。将X（Y或Z）定为一系列常数值，可定义一簇平行平面。函数F（x,y,z）=0表示的曲面与每一平行平面的交线为一条曲线，即y=f(x,y)或x=g(y,z)其中z为常数。
面消隐
画家算法Depth-sorting method
算法基本思想:
1先把屏幕置成背景色
2先将场景中的物体按其距观察点的远近进行排序，结果放在一张线性表中；（线性表构造：距观察点远的称优先级低，放在表头；距观察点近的称优先级高，放在表尾。该表称为深度优先级表）
3然后按照从远到近（从表头到表尾）的顺序逐个绘制物体。
不可处理: 多边形循环遮挡,多边形相互穿透
Z缓冲器算法 Z-buffer
帧缓冲器-保存各像素颜色值(CB)
z缓冲器-保存各像素处物体深度值(ZB)
z缓冲器中的单元与帧缓冲器中的单元一一对应
思想:先将z缓冲器中个单元的初始值置为+Zmax (大于场景中的所有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)处
优点：
1）简单稳定，利于硬件实现
2）不需要整个场景的几何数据
缺点:
1）需要一个额外的Z缓冲器
2）在每个多边形占据的每个像素处都要计算深度值，计算量大
Z缓冲器算法改进算法
{ 帧缓存全置为背景色
for(屏幕上的每个象素(i,j))
{ 深度缓存变量zb置最小值MinValue
for(多面体上的每个多边形Pk)
{ if(象素点(i,j)在pk的投影多边形之内)
{ 计算Pk在(i,j)处的深度值depth;
if(depth大于zb)
{ zb = depth;
indexp = k;
}
}
}
if(zb != MinValue)
在交点 (i,j) 处用多边形Pindexp的颜色显示
}
}
光线投射法
思想: 将通过绘图窗口内每一个像素的投影线与场景中的所有多边形求交。如果有交点，用深度值最大的交点（最近的）所属的多边形的颜色显示相应的像素；如果没有交点，说明没有多边形的投影覆盖此像素，用背景色显示即可。
for (v=0;v显示像素(u,v)；
}
}
光照模型
Gouraud方法 在每个多边形顶点处计算颜色,然后在各个多边形内部进行线性插值,得到多边形内部各点颜色.即它是一种颜色插值着色方法.
1先计算出多面体顶点的法线方向.
2用光照模型求得V点的亮度.
3由两顶点的亮度,插值得出棱上各点的亮度.由棱上各点的亮度,插值得出面上各点的亮度.
优点:能有效的显示漫反射曲面,计算量小
缺点: 1高光有时会异常
2当对曲面采用不同的多边形进行分割时会产生不同的效果.
3Gouraud明暗处理会造成表面上出现过亮或过暗的条纹,称为马赫带（Mach_band）效应
改进－Phong提出双线性法向插值，以时间为代价，解决高光问题
Phong方法 通过对多边形顶点的法矢量进行插值,获得其内部各点的法矢量,又称为法向插值着色方法.
1计算多边形单位法矢量
2计算多边形顶点单位法矢量
3对多边形顶点法矢量进行双线性插值,获得内部各点的法矢量
4利用光照明方程计算多边形内部各点颜色
两种方法比较
Phong着色方法绘制的图形比Gouraud方法更真实,体现在两个方面:
高光区域的扩散,产生正确的高光区域
1Phong着色方法计算量远大于Gouraud着色方法
2在处理某些多边形分割的曲面时,Phong算法还不如Gouraud算法好

基本造型方法
造型技术研究如何在计算机中建立恰当的模型表示物体的技术称为造型技术,现有实体造型技术,曲面造型技术,非几何形体的造型技术
结构实体几何模型CSG Constructive Solid Geometry 体素构造法,结构实体几何法
由两个物体间的并交差操作生成一新物体,物体为立方体,圆柱,圆锥等
CSG结点数据结构:一棵二叉树
体素 集合运算 变换(平移,旋转)操作
终端结点 非终端结点 非终端结点
CSG树定义了构造方式,不反映面,边,点等边界信息,这种表示称为物体的隐式模型
优点:1数据结构比较简单,数据量比较小;2CSG方法表示的形体形状,比较容易修改
缺点: 1对形体的表示受体素的种类和对体素操作的种类的限制;2由于形体的边界几何元素(点,边,面) 是隐含地表示在CSG中,则显示与绘制CSG表示的形体需要较长时间
实体的性质: 具有一定的形状;具有确定的封闭的边界;是一个内部连通的三维点集;占据有限的空间; 经过任意的运算后，仍为有效实体
正则集合运算保证集合运算的结果仍是一个正则形体，即丢弃悬边、悬面等
分解模型
空间位置枚举表示法: 将形体空间细分为小的立方体单元,与此相应,在计算机内存中开辟一个三维数 组,凡有形体占有的空间,存储单元中记为1;其余空间记为0;表示简单,但占用存储量大.
分层树结构:称八叉树,用于表示实体,为四叉树编码的扩展.树根表示整幅图象,将图象分成4个大小相 等的子图,4个子图用4个结点表示.根据均匀性准则判定图块是否再被细分
建立过程:
1八叉树的根结点对应整个物体空间
2如果它完全被物体占据,将该结点标记为F（Full）,算法结束 实心方块-实结点
3如果它内部没有物体,将该结点标记为E（Empty）,算法结束 空心方块-空结点
4如果它被物体部分占据,将该结点标记为P（Partial),并将它分割成8个子立方体,对每一个子立方体作同样处理. 圆-具有子孙的结点
八叉树表示法优点:
1数据结构简单
2简化形体的集合运算.对形体执行交,并,差运算时,只需同时遍历参加集合运算的两形体相应的八叉树,无须进行复杂的求交运算
边界模型 几何信息+拓扑信息
几何信息:描述形体的几何元素(顶点,边,面)之间的连接关系
点是0维几何元素
边是1维几何元素,是两个邻面的交界.直线边,曲线边
面是2维几何元素,是形体上一个有限,非零的区域,由一个外环和若干个内环界定其范围
一个面可以无内环,但必须有一个且只有一个外环.面有方向性
环是有序、有向边组成的面的封闭边界
环中的边不能相交,相邻两条边共享一个端点
确定面的最大外边界的环称之为外环
确定面中内孔环称之为内环
在面上沿一个环前进,其左侧总是面内,右侧总是面外
体是3维几何元素,由封闭表面围成空间,也是欧氏空间R3中非空,有界的封闭子集,其边界是有限面的并集
拓扑信息:描述形体的几何元素性质和度量关系,如位置,大小,方向,尺寸,形状等信息
边界表示 B-rep
欧拉特征: 设表面S由一个平面模型给出,且V,E,F分别表示其顶点,边和小面的个数,那么V-E+F是一个 常数,它与S划分形成平面模型的方式无关
欧拉公式:V-E+F=2,且要求形状满足:1面上没有洞2立体上没有孔洞
欧拉公式可保证形体正确,当形体几何分量的改变不满足欧拉公式,产生病态形体
拓展的欧拉公