# 梁友栋－barsky 算法实现直线段相对于给定窗口的裁剪 (OpenGL)
# 实验内容
- 用梁友栋－barsky 算法或者中点分割法等其它算法（除 cohen-sutherland 直线裁剪算法外）实现直线段相对于给定窗口的裁剪。
- 采用 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; | |
} |
# 实验报告
# 实验内容
- 用梁友栋－barsky 算法或者中点分割法等其它算法（除 cohen-sutherland 直线裁剪算法外）实现直线段相对于给定窗口的裁剪。
- 采用 C/C++ 、OpenGL 编写程序（参考所提供的程序代码 clip.cpp 及第三次实验提供的建立 Project 的过程说明）。
- 选作：
（1） 利用 Glut 处理鼠标、键盘输入的功能，实现用鼠标交互输入的方式来定义窗口、被裁剪线段的功能。
（2） 改进提供的 cohen-sutherland 算法演示界面（cohen-sutherland.rar），写入你的裁剪算法代码。
# 实验目的
- 通过实现图形学经典的二维裁剪算法，深入理解场景中对几何对象进行裁剪的原理。
- 锻炼实践算法的能力。
- 进一步熟悉 OpenGL 编程。
# 实验要求
- 调试通过算法程序；
- 撰写实验报告（参照所附《实验报告书模板》）：
- 写出算法流程图
- 说明算法中所采用的数据结构；
- 说明算法各函数的功能；
- 提供程序 源代码并进行必要的注释；
- 针对各种情况进行算法检验，并对结果进行说明。
- 若在程序中，有任何创新，请注明。将视情况获得加分。
# 实验方法
- 方法：使用梁友栋－barsky 算法实现直线段相对于给定窗口的裁剪：
# 算法流程图
# 算法代码
跳转
# 代码说明
int Clip(float p, float q, float* tL, float* tU)
这个函数用于判断 q 和 p 的值及各种关系，判断线与窗口的位置，并计算进入点最大值和离开点最小值，从而计算最终的端点值。void myclip()
这个函数用于计算都满足条件下的最终与窗口相交的两个端点坐标，使用的是直线参数方程求解。void display(void)
这个函数是用于绘制窗口以及裁剪线段。
# 实验结果
- 如图所示：
# 实验分析
# 梁友栋 - 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 算法也要对它反复求交点，而且每次求交计算都需要做乘除法。
