# 梁友栋-barsky 算法实现直线段相对于给定窗口的裁剪 (OpenGL)

# 实验内容

  1. 用梁友栋-barsky 算法或者中点分割法等其它算法(除 cohen-sutherland 直线裁剪算法外)实现直线段相对于给定窗口的裁剪。
  2. 采用 C/C++ 、OpenGL 编写程序(参考所提供的程序代码 clip.cpp 及第三次实验提供的建立 Project 的过程说明)。

# 代码部分

/*
 *  clip.cpp
 *  This program clips the line with the given window.
 */
#include <windows.h>
#include <glut.h>
#include <math.h>
#include <stdio.h>
float xmin, xmax, ymin, ymax;
void myinit(void)
{
    glShadeModel (GL_FLAT);
    glClearColor (0.0, 0.0, 0.0, 0.0);
}
void myReshape(int w, int h)
{
    glViewport(0, 0, w, h);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    if (w <= h) 
		gluOrtho2D (0.0, 1.0, 0.0, 1.0*(GLfloat)h/(GLfloat)w);
    else 
		gluOrtho2D (0.0, 1.0*(GLfloat)w/(GLfloat)h, 0.0, 1.0);
    glMatrixMode(GL_MODELVIEW);
}
int Clip(float p, float q, float* tL, float* tU)
{
	int flag = 1;     						//flag 为标志变量 0 表示舍弃 1 表示可见
	float r;
	if (p < 0.0)
	{
		r = q / p;
		if (r > *tU)
			flag = 0;
		else if (r > *tL)
			*tL = r;      					// 取进入点最大参数值
	}
	else if (p > 0.0) {
		r = q / p;
		if (r < *tL)
			flag = 0;
		else if (r < *tU)
			*tU = r;   						// 取离开点的最小值
	}
	else if (q < 0 && p == 0) 				// 平行于边界 而且在界外的线 
		flag = 0;
	return flag;
}
void myclip()
// line clipping algorithm 
{
	float dx, dy, x1, tL, tU, x2, y1, y2;
	tL = 0, tU = 1.0;
	printf("请输入线段的两个顶点坐标(x1,y1),(x2,y2):\n");
	scanf_s("%f%f%f%f", &x1, &y1, &x2, &y2);
	glBegin(GL_LINES);
	glColor4f(0.0, 0.0, 0.0, 0.0);
	glVertex2f(x1, y1); 					// line startpoint 
	glVertex2f(x2, y2); 					// line endpoint 
	glEnd();
	dx = x2 - x1;
	if (Clip(-dx, x1 - xmin, &tL, &tU))
		if (Clip(dx, xmax - x1, &tL, &tU)) {
			dy = y2 - y1;
			if (Clip(-dy, y1 - ymin, &tL, &tU))
				if (Clip(dy, ymax - y1, &tL, &tU))
				{
					if (tU < 1.0)
					{
						x2 = x1 + tU * dx;	// 求得裁剪后的 p2 端点 
						y2 = y1 + tU * dy;
					}
					if (tL > 0.0)
					{
						x1 = x1 + tL * dx;	// 求得裁剪后的 p1 端点 
						y1 = y1 + tL * dy;
					}
					glBegin(GL_LINES);
					glColor4f(1.0, 0.0, 0.0, 1.0);
					glVertex2f(x1, y1); 	// clipped line startpoint 
					glVertex2f(x2, y2); 	// clipped line endpoint 
					glEnd();
				}
		}
}
void display(void)
{
    glClear(GL_COLOR_BUFFER_BIT);
// The window
// ------------------------------------
//  you can change the window definition on yourself.
// ------------------------------------
//  glColor4f (0.0, 1.0, 1.0, 0.75);
//	glBegin(GL_POLYGON);
//  glVertex2f( 0.2f, 0.3f); // Bottom Left
//	glVertex2f( 0.8f, 0.3f); // Bottom Left
//	glVertex2f( 0.8f, 0.7f); // Bottom Right
//	glVertex2f( 0.2f, 0.7f); // Bottom Right
//	glEnd();
// ------------------------------------
//	please define your own line segment and draw 
//	it here with different color and line width
// ------------------------------------
	printf("请分别输入矩形的左、右、下、上边界点坐标:\n");
	scanf_s("%f%f%f%f", &xmin, &xmax, &ymin, &ymax);
	glColor4f(0.7, 0.0, 0.7, 0.55);
	glBegin(GL_POLYGON);
	glVertex2f(xmin, ymin); // Bottom Left
	glVertex2f(xmax, ymin); // Bottom Left
	glVertex2f(xmax, ymax); // Bottom Right
	glVertex2f(xmin, ymax); // Bottom Right
	glEnd();
 	//-------------------------------
	//do the clipping in myclip() funtion 
	//-------------------------------
   	myclip();
// ------------------------------------
//	please draw clipped line here with another 
//  color and line width
// ------------------------------------   
    glFlush();
}
/*  Main Loop
 *  Open window with initial window size, title bar, 
 *  RGBA display mode, and handle input events.
 */
int main(int argc, char** argv)
{
   	glutInit(&argc, argv);
   	glutInitDisplayMode (GLUT_SINGLE | GLUT_RGBA);
   	//define size and the relative positon of the applicaiton window on the display
   	glutInitWindowSize (500, 500); 
  	glutInitWindowPosition (100, 100);
 	//init the defined window with "argv[1]" as topic showed on the top the window
   	glutCreateWindow (argv[0]);
	// opengl setup
   	myinit ();
	//define callbacks
   	glutDisplayFunc(display); 
   	glutReshapeFunc(myReshape);
   	//enter the loop for display
   	glutMainLoop();
	return 1;
}

# 实验报告

# 实验内容

  1. 用梁友栋-barsky 算法或者中点分割法等其它算法(除 cohen-sutherland 直线裁剪算法外)实现直线段相对于给定窗口的裁剪。
  2. 采用 C/C++ 、OpenGL 编写程序(参考所提供的程序代码 clip.cpp 及第三次实验提供的建立 Project 的过程说明)。
  3. 选作:
    (1) 利用 Glut 处理鼠标、键盘输入的功能,实现用鼠标交互输入的方式来定义窗口、被裁剪线段的功能。
    (2) 改进提供的 cohen-sutherland 算法演示界面(cohen-sutherland.rar),写入你的裁剪算法代码。

# 实验目的

  1. 通过实现图形学经典的二维裁剪算法,深入理解场景中对几何对象进行裁剪的原理。
  2. 锻炼实践算法的能力。
  3. 进一步熟悉 OpenGL 编程。

# 实验要求

  1. 调试通过算法程序;
  2. 撰写实验报告(参照所附《实验报告书模板》):
    • 写出算法流程图
    • 说明算法中所采用的数据结构;
    • 说明算法各函数的功能;
    • 提供程序 源代码并进行必要的注释;
    • 针对各种情况进行算法检验,并对结果进行说明。
    • 若在程序中,有任何创新,请注明。将视情况获得加分。

# 实验方法

  • 方法:使用梁友栋-barsky 算法实现直线段相对于给定窗口的裁剪:

# 算法流程图

imgbed.cn图床

# 算法代码

跳转

# 代码说明

int Clip(float p, float q, float* tL, float* tU)
这个函数用于判断 q 和 p 的值及各种关系,判断线与窗口的位置,并计算进入点最大值和离开点最小值,从而计算最终的端点值。
void myclip()
这个函数用于计算都满足条件下的最终与窗口相交的两个端点坐标,使用的是直线参数方程求解。
void display(void)
这个函数是用于绘制窗口以及裁剪线段。

# 实验结果

  • 如图所示:

imgbed.cn图床

imgbed.cn图床

# 实验分析

# 梁友栋 - Barsky 裁剪算法思想

一条两端点为 P1(x1,y1)、P2(x2,y2)的线段可以用参数方程形式表示:
x= x1+ u·(x2-x1)= x1+ u·Δx
y= y1+ u·(y2-y1)= y1+ u·Δy

式中,Δx=x2-x1,Δy=y2-y1,参数 u 在 0~1 之间取值,P(x,y)代表了该线段上的一个点,其值由参数 u 确定,由公式可知,当 u=0 时,该点为 P1(x1,y1),当 u=1 时,该点为 P2(x2,y2)。如果点 P(x,y)位于由坐标(xmin,ymin)和(xmax,ymax)所确定的窗口内,那么下式成立:
xmin≤x1+ u·Δx≤xmax
ymin≤y1+ u·Δy≤ymax

这四个不等式可以表示为:
u·pk ≤qk , (k=1,2,3,4)
其中,p、q 定义为:

p1=-Δx, q1=x1-xmin
p2=Δx, q2=xmax-x1
p3=-Δy, q3=y1-ymin
p4=Δy, q4=ymax-y1
任何平行于窗口某边界的直线,其 pk=0(但并不是所有的 pk 均为 0,是存在 pk=0 的意思。平行于窗口某边界的图片,会出现 (p1&&p2)||(p3&&p4)=0 的情况),k 值对应于相应的边界(k=1,2,3,4 对应于左、右、下、上边界)。如果还满足 qk<0(默认 x1 为最左点?默认斜率大于 0 小于 1?),则线段完全在边界外,应舍弃该线段。如果 pk=0 并且 qk≥0,则线段平行于窗口某边界并在窗口内。
1、当 pk<0 时,线段从裁剪边界延长线的外部延伸到内部;
2、当 pk>0 时,线段从裁剪边界延长线的内部延伸到外部;
例如,
当 Δx≥0 时,对于左边界 p1<0(p1=-Δx),线段从左边界的外部到内部;
对于右边界 p2>0(p2=Δx),线段从右边界的内部到外部。
当 Δy<0 时,对于下边界 p3>0(p3=-Δy),线段从下边界的内部到外部;
对于上边界 p4<0(p4=Δy),线段从上边界的外部到内部。
对于每条直线,可以计算出参数 u1 和 u2,该值定义了位于窗口内的线段部分:
1、u1 的值由线段从外到内遇到的矩形边界所决定(pk<0),对这些边界计算 rk=qk/pk,u1 取 0 和各个 r 值之中的最大值。
2、u2 的值由线段从内到外遇到的矩形边界所决定(pk>0),对这些边界计算 rk=qk/pk,u2 取 0 和各个 r 值之中的最小值。
3、如果 u1>u2,则线段完全落在裁剪窗口之外,应当被舍弃;否则,被裁剪线段的端点可以由 u1 和 u2 计算出来。

# 实验总结

梁友栋 - Barsky 算法只能应用于矩形窗口的情形。通常梁友栋 - Barsky 算法比 Cohen-Sutherland 算法效率更高,因为需要计算的交点数目减少了。更新参数 u1、u2 仅仅需要一次除法;线段与窗口边界的交点仅计算一次,就计算出 u1、u2 最后的值。相比之下,即使一条线段完全落在裁剪窗口之外,Cohen-Sutherland 算法也要对它反复求交点,而且每次求交计算都需要做乘除法。