计算机科学与技术学院
20##-20##学年第一学期
《计算机图形学》实验报告
班级:
学号:
姓名:
教师:
成绩:
实验项目(3、二维裁剪)
一、 实验目的与要求
(1) 掌握线段裁剪算法原理,并实现其算法。
(2) 理解多边形裁剪、字符裁剪算法思想,能编程实现其算法。
二、 实验内容
设计菜单程序,利用消息处理函数,完成以下要求:
(1) 实现直线段的标号法(Cohen-Sutherland)、矩形窗口裁剪算法。
(2) 参考教材中的算法,用矩形窗口实现多边形的Sutherland-Hodgman裁剪算法。
三、 重要算法分析
以下分析Cohen-Sutherland和Sutherland-Hodgman两个算法,其中Cohen-Sutherland算法的基本思想通过编码的方法快速实现对直线段的裁剪;Sutherland-Hodgman算法基本思想是用窗口的四条边所在的直线依次来裁剪多边形。
(一) Cohen-Sutherland算法
该算法的基本思想是:对于每条待裁剪的线段P1,P2分三种情况处理:
(1) 若P1P2完全在窗口内,则显示该线段。
(2) 若P1P2完全在窗口外,则丢弃该线段。
(3) 若线段既不满足“取”的条件,也不满足“舍”的条件,则求线段与窗口边界的交点,在交点处把线段分为两段。
1. 编码原则
具体编码过程为将延长线窗口的四条边线(yT、yB、xR、xL),将二维平面分成九个区域,全为0的区域是裁剪窗口,其中各位编码的定义如下:
按照如上定义,相应区域编码如图1所示。
图1 区域编码
2. 裁剪算法:
依据上面的编码原则,可以总结出对一条线段的可见性进行测试:
1) 若线段两个端点的四位二进制编码全为0000,即两端点编码逻辑或运算为0,那么该线段完全位于窗口内,可直接保留。
2) 对端点的四位二进制编码进行逻辑与运算,若结果不为零,那么整条线段必位于窗口外,可直接舍弃。
3) 否则,这条线段既不能保留也不能舍弃,它可能与窗口相交。此时,需要对窗口进行再分割,并对分割后的线段按照一定顺序进行检查,决定保留、舍弃或再分割。重复这过程,直到全部线段均被舍弃或保留为止。
(二) Sutherland-Hodgman算法
算法的基本思想是利用窗口的四条边所在的直线依次来裁剪多边形。多边形的每条边与裁剪线的位置关系有4种情况,如图2所示。
图2 多边形边界与裁剪窗口的关系
其中a)为从外到内的输出P和I,b)为从内到内输出P,c)为从内到外输出I,d)为从外到外不输出。
假设当前处理的多边形为SP。
1) 在图2a的情况中,端点S在外侧,P在内侧,则按顺序将交点I和P都输出到结果多边形的顶点表中。
2) 在图2b的情况中,端点S和都在内侧,则输出P到结果多边形的顶点表中。
3) 在图2c的情况中,端点S在内侧,P在外侧,则输出交点I到结果多边形的顶点表中。
4) 在图2d的情况中,端点S和 P在外侧,没有输出。
四、 程序运行截图
1. 用Cohen-Sutherland算法实现线段的裁剪,如图3所示,其中a)图中的线段为裁剪前的,b)图将超出裁剪多边形的线段部分裁剪后的结果。
图3 Cohen-Sutherland算法裁剪前和后
a)裁剪前 b)裁剪后
2. Sutherland-Hodgman算法实现多边形裁剪,如图4所示。
图4 Sutherland-Hodgman算法裁剪多边形前和后
a)裁剪多边形前 b)裁剪多边形后
五、 总结与调试经验
(1) 通过这次实验,加深了对图形学的理解,尤其对线段裁剪和多边形裁剪有了更加深入的理解。
(2) 我学会了多边形裁剪算法,从刚开始的不知道到现在的理解,这是一个很大的进步,当然我也遇到了些困难,比如用某一条多边形的窗口边界裁剪多边形,它要分为四种情况来分别考虑,也看出了我的思维不够周密,需要多多锻炼。
第二篇:计算机图形学_实验报告三_图形裁剪算法
图形裁剪算法
1. 实验目的:
理解区域编码
设计直线裁剪算法
编程实现直线裁剪算法
2. 实验描述:
设置裁剪窗口坐标为:wxl=250;wxr=850;wyb=250;wyt=450;裁剪前如下图所示:
裁剪后结果为:
3. 算法设计:
直线裁剪算法:
假设裁剪窗口是标准矩形,由上(y=wyt)、下(y=wyb)、左(x=wxl)、右(x=wxr)四条边组成,如下图所示。 延长窗口四条边形成 9个区域。根据被裁剪直线的任一端点 P(x,y)所处的窗口区域位置,可以赋予一组4位二进制区域码C4C3C2C1。
编码定义规则:
第一位C1:若端点位于窗口之左侧,即 X<Wxl,则 C1=1,否则 C1=0。
第二位C2:若端点位于窗口之右侧,即 X>Wxr,则 C2=1,否则 C2=0。
第三位C3:若端点位于窗口之下侧,即 Y<Wyb,则 C3=1,否则 C3=0。
第四位C4:若端点位于窗口之上侧,即 Y>Wyt,则 C4=1,否则 C4=0。
裁剪步骤:
1. 若直线的两个端点的区域编码都为0,即 RC1|RC2=0(二者按位相或的结果为0,即 RC1=0 且RC2=0),说明直线两端点都在窗口内,应“简取”。
2. 若直线的两个端点的区域编码都不为0,即 RC1&RC2≠0(二者按位相与的结果不为0,即 RC1≠0且 RC2≠0,即直线位于窗外的同一侧,说明直线的两个端点都在窗口外,应“简弃”。
3. 若直线既不满足“简取”也不满足“简弃”的条件,直线段必然与窗口相交,需要计算直线与窗口边界的交点。交点将直线分为两段,其中一段完全位于窗口外,可“简弃”。对另一段赋予交点处的区域编码,再次测试,再次求交,直至确定完全位于窗口内的直线段为止。
4. 实现时,一般按固定顺序左(x=wxl)、右(x=wxr)、下(y=wyb)、上(y=wyt)求解窗口与直线的交点。
4.源程序:
//1)TestView.h
class CTestView : public CView
{
…….
protected:
double Pointx[2],Pointy[2];//用户绘制的直线
int wxl,wxr,wyb,wyt;//左上与右下
CDC Picture;//内存(预存)DC,防止屏幕闪烁
char m_i; //第一个点还是第二个点
BOOL m_Attatch;
BOOL m_Draw;
unsigned int RC,RC0,RC1;
……..
}
2) //TestView.cpp
CTestView::CTestView()
{
//窗口位置坐标
wxl=250;wxr=850;wyb=250;wyt=450;
m_Attatch=FALSE;
m_i=0;
m_Draw=FALSE;
RC0=0;RC1=0;
}
void CTestView::OnDraw(CDC* pDC)
{
CTestDoc* pDoc = GetDocument();
ASSERT_VALID(pDoc);
//装载位图
CRect Rect;
GetClientRect(&Rect);//获得客户区的大小
CBitmap Bitmap,*pBitmap;
Bitmap.LoadBitmap(IDB_BITMAP);
CDC MemDC;
MemDC.CreateCompatibleDC(GetDC());
pBitmap=MemDC.SelectObject(&Bitmap);
MemDC.BitBlt(0,0,Rect.Width(),Rect.Height(),&Picture,0,0,SRCCOPY);
MemDC.TextOut((wxl+wxr)/2,wyb-20,"窗口");//窗口标题
//绘制窗口和直线
CPen Pen3,*pOldPen3;//定义3个像素宽度的画笔
Pen3.CreatePen(PS_SOLID,3,RGB(0,0,0));
pOldPen3=MemDC.SelectObject(&Pen3);
MemDC.MoveTo(wxl,wyt);MemDC.LineTo(wxr,wyt);
MemDC.LineTo(wxr,wyb);MemDC.LineTo(wxl,wyb);
MemDC.LineTo(wxl,wyt);MemDC.SelectObject(pOldPen3);
Pen3.DeleteObject();
CPen Pen1,*pOldPen1;//定义1个像素宽度的画笔
Pen1.CreatePen(PS_SOLID,1,RGB(0,0,255));
pOldPen1=MemDC.SelectObject(&Pen1);
if(m_i>=1)
{
MemDC.MoveTo(ROUND(Pointx[0]),ROUND(Pointy[0]));
MemDC.LineTo(ROUND(Pointx[1]),ROUND(Pointy[1]));
}
MemDC.SelectObject(pOldPen1);
Pen1.DeleteObject();
CDC *dc=GetDC();
dc->BitBlt(0,0,Rect.Width(),Rect.Height(),&MemDC,0,0,SRCCOPY);
MemDC.SelectObject(pBitmap);
}
void CTestView::OnMENUClip()//裁剪菜单函数
{
Cohen();
Invalidate(FALSE);
}
unsigned int CTestView::EnCode(double LinePx,double LinePy)//端点编码函数
{//顺序左右下上
RC=0;
if(LinePx<wxl)
{
RC=RC | LEFT;
}
if(LinePx>wxr)
{
RC=RC | RIGHT;
}
if(LinePy<wyb)
{
RC=RC | BOTTOM;
}
if(LinePy>wyt)
{
RC=RC | TOP;
}
return RC;
}
void CTestView::OnMENUDrawLine()//绘制直线菜单函数
{
// TODO: Add your command handler code here
if(FALSE==m_Attatch)
{
Picture.CreateCompatibleDC(GetDC());
CBitmap *Bitmap,*pBitmap;
Bitmap=new CBitmap;
Bitmap->LoadBitmap(IDB_BITMAP);
pBitmap=Picture.SelectObject(Bitmap);
m_Attatch=TRUE;
}
m_Draw=TRUE;
m_i=0;
Invalidate(FALSE);
AfxGetMainWnd()->SetWindowText("案例10:Cohen-Sutherland直线裁剪算法");//显示标题
MessageBox("请使用鼠标在屏幕上绘制直线,然后点击裁剪按钮进行裁剪","提示",MB_OKCANCEL);
}
void CTestView::OnLButtonDown(UINT nFlags, CPoint point)//单击鼠标左键函数
{
// TODO: Add your message handler code here and/or call default
if(TRUE==m_Draw)
{
if(m_i<2)
{
Pointx[m_i]=point.x;Pointy[m_i]=point.y;
m_i++;
}
}
CView::OnLButtonDown(nFlags, point);
}
void CTestView::OnMouseMove(UINT nFlags, CPoint point) //鼠标移动函数
{
// TODO: Add your message handler code here and/or call default
if(TRUE==m_Draw)
{
if(m_i<2)
{
Pointx[m_i]=point.x;Pointy[m_i]=point.y;
Invalidate(FALSE);
}
}
CView::OnMouseMove(nFlags, point);
}
void CTestView::Cohen()//Cohen-Sutherland算法
{
BOOL Change;
double x,y;
RC0=EnCode(Pointx[0],Pointy[0]);
RC1=EnCode(Pointx[1],Pointy[1]);
while(TRUE)
{
Change=FALSE;
if(0 == (RC0|RC1))
{//简取之
return;
}
else if(0!=(RC0 & RC1))
{//简弃之
return;
}
else
{
if(0==RC0)//如果P0点在窗口内,交换P0和P1,保证p0点在窗口外
{
//交换点的坐标值
double TPointx,TPointy;
TPointx=Pointx[0];TPointy=Pointy[0];
Pointx[0]=Pointx[1];Pointy[0]=Pointy[1];
Pointx[1]=TPointx;Pointy[1]=TPointy;
//交换点的编码值
unsigned int TRC;
TRC=RC0;RC0=RC1;RC1=TRC;
}
//按左、右、下、上的顺序裁剪
if(RC0 & LEFT )//P0点位于窗口的左侧
{
x=wxl;//求交点y
y=Pointy[0]+(Pointy[1]-Pointy[0])*(x-Pointx[0])/(Pointx[1]-Pointx[0]);
Pointx[0]=x;Pointy[0]=y;
Change=TRUE;
RC0=EnCode(Pointx[0],Pointy[0]);RC1=EnCode(Pointx[1],Pointy[1]);
}
if(RC0 & RIGHT )//P0点位于窗口的右侧
{
x=wxr;//求交点y
y=Pointy[0]+(Pointy[1]-Pointy[0])*(x-Pointx[0])/(Pointx[1]-Pointx[0]);
Pointx[0]=x;Pointy[0]=y;
Change=TRUE;
RC0=EnCode(Pointx[0],Pointy[0]);RC1=EnCode(Pointx[1],Pointy[1]);
}
if(RC0 & BOTTOM )//P0点位于窗口的下侧
{
y=wyb;//求交点x
x=Pointx[0]+(Pointx[1]-Pointx[0])*(y-Pointy[0])/(Pointy[1]-Pointy[0]);
Pointx[0]=x;Pointy[0]=y;
Change=TRUE;
RC0=EnCode(Pointx[0],Pointy[0]);RC1=EnCode(Pointx[1],Pointy[1]);
}
if(RC0 & TOP )//P0点位于窗口的上侧
{
y=wyt;//求交点x
x=Pointx[0]+(Pointx[1]-Pointx[0])*(y-Pointy[0])/(Pointy[1]-Pointy[0]);
Pointx[0]=x;Pointy[0]=y;
Change=TRUE;
RC0=EnCode(Pointx[0],Pointy[0]);RC1=EnCode(Pointx[1],Pointy[1]);
}
if(FALSE==Change)
{
return;
}
}
}
}
5.运行结果: