梁友栋-Barsky直线裁剪算法计算机图形学课程设计

《计算机图形学实验》报告任课教师：钱文华2016年春季学期实验:梁友栋裁剪实验时间：2016年11月17日实验地点：信息学院2204实验目的：掌握梁友栋裁剪程序代码：#include <stdio.h>#include <glut.h>#include <stdlib.h>#include <math.h>class wcPt2D{public:GLfloat x,y;void setCoords(GLfloat xCoord,GLfloat yCoord){x=xCoord;y=yCoord;}GLfloat getx() const{return x;}GLfloat gety() const{return y;}};inline GLint round(const GLfloat a){return GLint(a+0.5);}void setPixel(int x,int y){glBegin(GL_POINTS);glVertex2i(x,y);glEnd();}void init(){glClearColor(1.0,1.0,1.0,0.0);glMatrixMode (GL_PROJECTION);gluOrtho2D(-200.0,200.0,-200.0,200.0);}void lineBres(GLfloat x0,GLfloat y0,GLfloat xEnd,GLfloat yEnd){ int dx = fabs(xEnd - x0),dy = fabs(yEnd - y0);int p = 2*dy - dx;int twoDy = 2*dy,twoDyMinusDx = 2*(dy - dx);int x,y;if(x0>xEnd){x = xEnd;y = yEnd;xEnd = x0;}else{x = x0;y = y0;}setPixel(x,y);while(x<xEnd){x++;if(p<0)p+=twoDy;else{y++;p+=twoDyMinusDx;}setPixel(x,y);}}GLint clipTest(GLfloat p,GLfloat q,GLfloat *u1,GLfloat *u2){ GLfloat r;GLint returnValue = true;if(p<0.0){r = q/p;if(r>*u2)returnValue = false;elseif(r>*u1)*u1 = r;}elseif(p>0.0){r = q/p;if(r<*u1)returnValue = false;else if(r<*u2)*u2 = r;}elseif(q<0.0)returnValue = false;return(returnValue);}void lineClipLiangBarsk(wcPt2D winMin,wcPt2D winMax,wcPt2D p1,wcPt2D p2){GLfloat u1 = 0.0,u2 = 1.0,dx = p2.getx()-p1.getx(),dy;GLfloat x1 = p1.getx(),y1 = p1.gety();GLfloat x2 = p2.getx(),y2 = p2.gety();if(clipTest(-dx,p1.getx()-winMin.getx(),&u1,&u2))if(clipTest(dx,winMax.getx()-p1.getx(),&u1,&u2)){dy = p2.gety()-p1.gety();if(clipTest(-dy,p1.gety()-winMin.gety(),&u1,&u2)){if(clipTest(dy,winMax.gety()-p1.gety(),&u1,&u2)){if(u2<1.0){p2.setCoords(p1.getx()+u2*dx,p1.gety()+u2*dy);}if(u1>0.0){p1.setCoords(p1.getx()+u1*dx,p1.gety()+u1*dy);}glColor3f(0.0,0.0,0.0);lineBres(x1,y1,p1.getx(),p1.gety());lineBres(p2.getx(),p2.gety(),x2,y2);glColor3f(1.0,0.0,0.0);lineBres(p1.getx(),p1.gety(),p2.getx(),p2.gety());}}else{glColor3f(0.0,0.0,0.0);lineBres(x1,y1,x2,y2);}}}void displayliangyoudongcaijian(){glClear(GL_COLOR_BUFFER_BIT);glLineWidth(5.0);glColor3f(0.0,0.0,0.0);glBegin(GL_LINE_LOOP);glVertex2i(100,100);glVertex2i(100,-100);glVertex2i(-100,-100);glVertex2i(-100,100);glEnd();glPointSize(4);wcPt2D test1[4] = {{-100.0,-100.0},{100.0,100.0},{-150.0,-200.0},{200.0,120.0}};wcPt2D test2[4] = {{-100.0,-100.0},{100.0,100.0},{-150.0,-120.0},{0.0,0.0}};wcPt2D test3[4] = {{-100.0,-100.0},{100.0,100.0},{-50.0,50.0},{150.0,150.0}};wcPt2D test4[4] = {{-100.0,-100.0},{100.0,100.0},{-50.0,0.0},{60.0,50.0}};wcPt2D test5[4] = {{-100.0,-100.0},{100.0,100.0},{-170.0,-200.0},{200.0,-120.0}};lineClipLiangBarsk(test1[0],test1[1],test1[2],test1[3]);lineClipLiangBarsk(test2[0],test2[1],test2[2],test2[3]);lineClipLiangBarsk(test3[0],test3[1],test3[2],test3[3]);lineClipLiangBarsk(test4[0],test4[1],test4[2],test4[3]);lineClipLiangBarsk(test5[0],test5[1],test5[2],test5[3]);glFlush();}void main(int argc, char* argv[]){glutInit(&argc,argv);glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);glutInitWindowPosition(50,100);glutInitWindowSize(400,300);glutCreateWindow("梁友栋裁剪算法");init();glutDisplayFunc(displayliangyoudongcaijian);glutMainLoop();}实验结果：。

计算机图形学——梁友栋-Barsky算法梁算法是计算机图形学上最经典的⼏个算法，也是⽬前唯⼀⼀个以中国⼈命名的出现在国内外计算机图形学课本的算法，我之前在介绍裁剪算法的时候介绍过这个算法这⼏天复习图形学，发现当时那篇博客写的很空洞，⼀些关键性的推理式⼦讲的不是很清楚，于是在这⾥仔细介绍⼀下。

最近发现中国⼤学MOOC上中国农业⼤学的赵明教授讲的很不错，课程短⼩精悍，感兴趣的同学可以去看⼀下⼀、直线的参数⽅程梁算法表⽰直线是通过直线的参数⽅程来确定的，也就是说给出两个点，利⽤参数表⽰直线。

这⾥对U的理解就是(x,y)点在所给两点之间线段上的位置。

⼆、出边和⼊边把被裁剪的红⾊直线段看 成是⼀条有⽅向的线段，把窗⼝ 的四条边分成两类：⼊边和出边⼊边：直线由窗⼝外向窗⼝内移动时和窗⼝边界相交的边（左边界和下边界）。

出边：直线由窗⼝内向窗⼝外移动时和窗⼝边界相交的边（右边界和上边界）。

裁剪结果的线段起点是直线和两条⼊边的交点以及始端点三 个点⾥最前⾯的⼀个点，即参数u最⼤的那个点；裁剪线段的终点是和两条出边的交点以及端点最后⾯的⼀个 点，取参数u最⼩的那个点。

值得注意的是，当u从-∞到+∞遍历直线时，⾸先对裁剪窗⼝的两条边界直线（下边和左边）从外⾯向⾥⾯移动，再对裁剪窗⼝两条边界直线（上边和右边）从⾥⾯向外⾯移动。

如果⽤u1，u2分别表⽰ 线段（u1≤u2）可见部分的开始和结束上⾯就是梁友栋先⽣的发现，但⼜有了新的问题：如何判断出边和⼊边？四个U值是如何求出来的？判断线段某⼀部分是否在窗⼝内，可以简化为判断直线上⼀个点是否在窗⼝内的问题。

我们知道梁友栋算法的基本出发点是直线的参数⽅程，那么对于那些不会被裁剪掉的点⼀定会满⾜下⾯的不等式：三、运算所⽤的量将上⾯的不等式移项得：在这⾥可以确定那些直线与裁剪窗⼝的交点中P K<0的点输⼊⼊边，P K>0的点属于出边1）分析P k=0的情况如果还满⾜q k<0则线段完全在边界外，应舍弃该线段如果q k≥0则进⼀步判断（2）当p k≠0时：当p k<0时线段从裁剪边界延长线的外部 延伸到内部，是⼊边交点当p k> 0时线段从裁剪边界延长线的内部 延伸到外部，是出边交点线段和窗⼝边界⼀共有四个交点，根据p k的符号，就知道 哪两个是⼊交点，哪两个是出交点当p k< 0时：对应⼊边交点当p k> 0时：对应出边交点⼀共四个u值，再加上u=0、u=1两个端点值，总共六个值把pk＜0的两个u值和0⽐较去找最⼤的，把pk＞0的两个u值 和1⽐较去找最⼩的，这样就得到两个端点的参数值四、⼩结直线参数化直线段看成是有⽅向的把窗⼝的四条边分为⼊边和出边。

河南理工大学万方科技学院课程设计报告2011 — 2012学年第二学期课程名称计算机图形学设计题目计算机图形学基本算法演示系统设计学生姓名学号专业班级网络11升—1班指导教师徐文鹏2012 年5 月28 日目录第1章设计内容与要求 (1)1.1 总体目标和要求 (1)1.2内容与要求 (1)1.2.1 直线的生成 (1)1.2.2 圆弧的生成 (1)1.2.3 线段裁剪 (2)1.2.4 多边形裁剪 (2)1.2.5 综合 (2)第2章总体设计 (3)2.1 Bresenham算法画直线 (3)2.1.1 Bresenham算法画直线理论基础 (3)2.1.2 Bresenham算法画直线原理 (3)2.2 Bresenham算法画圆 (4)2.2.1 Bresenham算法画圆理论基础 (4)2.2.2 Bresenham算法画圆原理 (5)2.3 梁友栋-Barsky算法进行线段裁剪 (6)2.3.1梁友栋-Barsky算法进行线段裁剪基本原理 (6)2.4 Sutherland-Hodgman算法进行多边形裁剪 (8)2.4.1 Sutherland—Hodgman多边形裁剪算法思想 (8)2.4.2 点在边界内侧的判断方法 (8)2.4.4 Sutherland-Hodgeman多边形裁剪算法特点 (8)第3章详细设计 (9)3.1 Bresenham算法画直线 (9)3.1.1 Bresenham 算法画线算法具体实现过程 (9)3.2 Bresenham算法画圆 (9)3.2.1 Bresenham 算法画圆核心代码 (9)3.3 梁友栋-Barsky算法进行线段裁剪 (10)3.3.1梁友栋-Barsky算法推导过程 (10)3.3.2梁友栋-Barsky算法进行线段裁剪的步骤 (11)3.4 Sutherland-Hodgman算法进行多边形裁剪 (11)3.4.1 Sutherland—Hodgman多边形裁剪算法步骤 (11)3.5将画线、画圆、线段裁剪和多边形裁剪综合 (12)第4章功能实现 (14)4.1用Bresenham算法画线测试结果 (14)4.2用Bresenham算法画圆测试结果 (14)4.3梁友栋-Barsky算法进行线段裁剪测试结果 (15)4.4 Sutherland-Hodgman算法进行多边形裁剪测试结果 (16)4.5将四种算法综合测试结果 (16)第5章总结 (17)参考文献 (18)第1章设计内容与要求1.1 总体目标和要求目标：以图形学算法为目标，深入研究。

计算机图形学课程设计
要求：程序中有必要的注释，程序中变量命名规范合理。

否则，成绩按降一档处理。

1、交互式绘图程序设计
内容：使用VC++6.0编程环境，实现一个简单的交互式绘图界面。

要求：用户通过鼠标能交互式输入一些数据，实现采用橡皮筋技术绘制相应的图形，要求能演示1-2个基本算法（Bresenham画线算法）。

选做：在状态栏上当鼠标运动时，能实时显示鼠标的当前坐标。

2、Cohen-Sutherland裁剪算法的实现
内容：使用VC++6.0环境，编程实现Cohen_Sutherland二维裁剪算法的实现。

要求：用户可以交互输入要裁剪线段的两个顶点，将裁剪后的线段和被裁剪掉的线段以不同的颜色显示在视图中。

3、Liang-Barsky裁剪算法的实现
内容：使用VC++6.0环境，编程实现Liang_Barsky二维裁剪算法的实现。

要求：用户可以交互输入要裁剪线段的两个顶点，将裁剪后的线段和被裁剪掉的线段以不同的颜色显示在视图中。

4、满足四象限的Bresenham绘制直线算法的实现
内容：使用VC++6.0环境，编程实现满足四象限的Bresenham直线段算法，并能够设置线宽和颜色属性。

要求：要求直线段端点可以由用户随机输入。

5、用OpenGL生成裁剪NURBS曲面
内容：使用VC++6.0编程环境，用OpenGL实现一个裁剪NURBS曲面的绘制。

要求：用户能交互式输入控制多面体的顶点，和剪切曲线的顶点数目和顶点坐标。