本文最后更新于2020年11月12日,已超过 3 个月没更新!

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

实验内容

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

代码部分

/*
 *  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算法也要对它反复求交点,而且每次求交计算都需要做乘除法。

  • 最后由lavender编辑于2020年11月21日下午8:45

疏影横斜水清浅,暗香浮动月黄昏