当前位置:www.6722.com > www.hjc22.com > 正文
则线段的终点正在窗口内
发布日期:2019-11-09

  请盲目恪守互联网相关的政策律例,严禁发布、、的言论。用户名:验证码:匿名?颁发评论

  图形裁剪算法研究 摘要 正在用户坐标系中定义的图形往往是大而复杂的,而输出设备如显示屏幕的尺寸及其分辩率倒是无限的,为了可以或许清晰地察看某一部门或对其进行某些画图操做,就需要将所关怀的这一局部区域的图形从整个图形中区分出来,这个区分指定区域内和区域外的图形过程称为裁剪,所指定的区域称为裁剪窗口。 裁剪凡是是对用户坐标系中窗口鸿沟进行裁剪,然后把窗口内的部门映照到视区中,也能够起首将用户坐标系的图形映照到设备坐标系或规范化设备坐标系中,然后用视区鸿沟裁剪。 环节词:矢量裁剪 图1 用户坐标系 3.规范化设备坐标系(Normalized Device Coordinates) 正在规范化坐标系下(取值范畴从0到1)定义视区,将察看坐标系下的场景描述映照到规范坐标系下。 图2 规范化设备坐标系 4.设备坐标系(Device Coordinates) 图形输出时需要必然的设备,如画图仪、显示器等,利用的是设备坐标系。设备坐标系一般为二维坐标,如屏幕坐标。它的范畴无限,单元一般为整数。设备坐标一般采用刚体例,能够转换为有量刚坐标。一旦场景变换到规范化坐标系下的单元正方形中,当前该单元面积只需要简单地映照到具体输出设备的显示区。给出合适的设备驱动法式,就能够利用分歧的输出设备。 1.2窗口区和视图区 用户能够正在用户坐标系中指定感乐趣的肆意区域,把这部门区域内的图形输出到屏幕上,这个指定区域称为窗口区。窗口区一般是矩形区域,能够用左下角和左上角两点坐标来定义其大小和。定义窗口的目标是要拔取图形中需要察看的那一部门图形。正在计较机图形学术语中,窗口最后是指要察看的图形区域,可是目前窗口也用于窗口办理系统。正在本章中,我们将窗口理解为用户坐标系中要显示的区域。 图形设备上用来输出图形的最大区域称之为屏幕域,它是无限的整数域,大小随具体设备而异。任何小于或等于屏幕域的区域都可定义为视图区。视图区由用户正在屏幕域顶用设备坐标定义,一般也定义成矩形,由其左下角和左上角两点坐标来定义。所以,用户能够操纵窗口来选择需要察看那一部门图形,而操纵视图区来指定这一部门图形正在屏幕上显示的。尺度的窗口区和视图区一般都是矩形,其各边别离取坐标轴平行。 用户定义的图形从窗口区到视图区的输出过程如下:从使用法式获得图形的用户坐标(WC-World Coordinates)→对窗口区进行裁剪(WC)→窗口区到视图区的规格化变换(NDC-Normalized Device Coordinate)→视图区从规格化设备系到设备坐标系的变换(DC-Device Coordinate)→正在图形设备上输出图形。 下图是从用户坐标系取图形正在设备坐标系下显示的示企图: 图3 用户坐标系 1.3窗口区和视图区之间的坐标变换 因为窗口和视图是正在分歧坐标系中定义的,因而,正在把窗口中图形消息转换到视图区之前,必需进行坐标变换,即把用户坐标系的坐标值为设备坐标系的坐标值。 设正在用户坐标系下,矩形窗口左下角点坐标为(Wxl,Wyb), 左上角点坐标为(Wxr,Wyt)。屏幕中视图区的两个角点正在设备坐标系下别离为(Vxl,Vyb)和(Vxr,Vyt)。则正在窗口中的点(xw,yw)对应视图区中的点(xv, yv),其变换公式为: 下图为示图: 图4 记: (2) (3) (4) (5) 公式能够化简为: (6) 写成矩阵形式为: (7) 上述变换是二维变换中比例变换和平移变换的组合变换。通过变换,能够实现将用户坐标系中窗口区中肆意一点转换成设备坐标系中视图区中一点,从而能够把现实图形转换到具体输出设备的显示区。 2线段的裁剪 线段的矢量裁剪 正在裁剪时分歧的线段可能被窗口分成几段,但此中只要一段位于窗口内可见,线段的裁剪算法就是要找出位于窗口内部的起始点和终止点的坐标。因矢量裁剪法对寻找起点和起点坐标的处置方式不异,下面以求始点坐标为例来申明线段矢量裁剪方式。 正在图5中,窗口的四条鸿沟把XOY平面分成九个区域,别离用1到9对这九个窗口编号,设5号区域为响应的可见窗口区,窗口的左下角点坐标(minX,minY),左上角点坐标为(maxX,maxY)。有一条矢量线段S,其起、起点的坐标别离为(Xs,Ys)和(Xe,Ye),则对线段S按矢量裁剪的算法步调如下: 、 图5 1.若线以外的肆意区域内或落正在(1,2,3)、(3,6,9)、(7,8,9)、(1,4,7)中肆意一区域组内,即满脚下述前提之一: XsminX且XeminX, XsminX且XeminX, YsminY且YeminY, YsminY且YeminY, (8) 则线段S不正在窗口内,不必做进一步的求交点处置,不然转下一步。 2.若线段S满脚minX≤s≤maxX且minX≤Ys≤maxY ,则线段的起点正在窗口内,新的起点坐标(X,Y)即为(s,Ys);不然,按以下各步判断S取窗口的关系以及解算其新起点坐标 (X,Y)。 图7 算法从被裁剪多边形的一个入点起头,碰着入点,沿着被裁剪多边形按顺时针标的目的汇集极点序列; 而当碰到出点时,则沿着裁剪窗口按顺时针标的目的汇集极点序列。 按上述法则,如斯交替地沿着两个多边形的边线行进,曲到回到起始点。这时,收集到的全数极点序列就是裁剪所得的一个多边形。 因为可能存正在的多边形,因而算法要考虑:将汇集过的入点的入点记号删去,免得反复。将所有的入点汇集完毕后算法竣事。 Weiler-Atherton肆意多边形裁剪算法步调: 1、顺时针输入被裁剪多边形极点序列Ⅰ放入数组1中。 2、顺时针输入裁剪窗口极点序列Ⅱ放入数组2中。 3、求出被裁剪多边形和裁剪窗口订交的所有交点,并给每个交点打上“入”、 “出” 标识表记标帜。 然后将交点按挨次插入序列Ⅰ获得新的极点序列Ⅲ,并放入数组3中; 同样也将交点按挨次插入序列Ⅱ获得新的极点序列Ⅳ,放入数组4中; 4、初始化输出数组Q,令数组Q为空。接着从数组3中寻找“入”点。若是“入”点没找到,法式竣事。 5、若是找到“入”点,则将“入”点放入S中暂存 6、将“入”点录入到输出数组Q中。并从数组3中将该“入”点的“入”点标识表记标帜 删去。 7、沿数组3挨次取极点: 若是极点不是“出点”,则将极点录入到输出数组Q中,流程转第7步。 不然,流程转第8步。 8、沿数组4挨次取极点: 若是极点不是“入点”,则将极点录入到输出数组Q中,流程转第8步。 不然,流程转第9步。 9、若是极点不等于起始点S,流程转第6步,继续数组3。不然,将数组Q输出;流程转第4步,寻找可能存正在的多边形。算法正在第4步:满脚“入”点没找到的前提时,算法竣事。 4圆的裁剪[5] 对圆的裁剪思是,起首通过圆的外接矩形判断来确定圆能否全数位于窗口的外边,若全数位于窗口外边,则裁剪过程竣事。不然,将圆分化成一组短线段,然后按照曲线裁剪的方式来进行。 因为曲线正在现实绘制时是采用短曲线来迫近曲线的方式实现,故曲线的裁剪也采用一般曲线裁剪方式对每一短线段进行裁剪,从而实现对整个曲线] 此算法是由Weiler和Atherton提出来的。算法的根基做法是:有时沿着多边形边的方历来处置极点,有时沿着窗口的鸿沟方历来处置,从而避免发生多余的连线。设被裁剪多边形和裁剪窗口都按顺时针确定陈列标的目的,因而,沿多边形的一条边前进,其左边为多边形的内部。算法起首沿多边形的任一点出发,检测多边形的每一条线段,当线段取裁剪窗口鸿沟订交时: 1、若是线段起点正在窗口外部而起点正在窗口内部,则求出交点,输出线段可见部门,继续沿多边形方神驰下处置; 2、 若是线段起点正在窗口内部而起点正在窗口外部,则求出交点,输出线段可见部门。从此交点起头,沿着窗口鸿沟方神驰前检测,找到一个多边形取窗口鸿沟的新交点后,输出由前交点到此新交点之间窗口鸿沟上的线、 前往到前交点,再沿着多边形方神驰下处置,曲四处理完多边形的每一条边,回到起点为止。 图8申明了双边裁剪算法的施行过程。 Weiler-Atherton算法可合用于任何凸的或凹的多边形裁剪,不会发生多余连线非矩形裁剪窗口的线] 正在某些使用中,需要用肆意外形的多边形对线段裁剪。对凸多边形裁剪窗口,能够点窜粱友栋-Barsky的参数化线段裁剪方式,使参数化方程适合裁剪区域的鸿沟,按照裁剪多边形的坐标范畴处置线段。这就成为另一种称之为Cyrus-Beck线段裁剪方式的算法。而前面引见的两种多边形裁剪方式都顺应于肆意凸多边形裁剪窗口。 圆或其他曲线鸿沟也能够用做为裁剪窗口,但用的很少。用这些区域的裁剪算法速度更慢,由于它的求交计较涉及非线性曲线方程。加速速度的一个方式是能够起首利用曲线裁剪区域的外接矩形裁剪,完全落正在外接矩形之外的裁剪对象被。若是是用圆做为窗口对线段裁剪,能够通过计较圆心到曲线端点的距离来识别出内部线段。其他线段通过解联立方程来计较交点。 7曲线] 曲线的裁剪过程涉及到非线性方程,需要更多的处置。圆或者其它曲线对象的外接矩形能够用来起首测试能否取矩形裁剪窗口有堆叠。若是曲线对象的外接矩形完全落正在裁剪窗口内,则曲线对象完全可见,若是曲线对象的外接矩形完全落正在裁剪窗口外,则曲线对象完全不成见。两种环境都不满脚时,一般需要解曲线和曲线的联立方程求交点。 图8 处置曲线对象的另一无效方式是把它们近似为曲线段,然后利用线段或多边形的裁剪算法。曲线绘制时凡是也利用曲线段迫近的方式,因为迫近时老是将线段取的很短,为了削减计较时间,裁剪时能够不计较交点,只需线段的端点中至多有一个正在裁剪窗口外,就该线段,从而提高裁剪效率。 8字符的裁剪 字符既可由单个的线段或笔划形成,也能够用点阵来暗示。由裁剪精度要求分歧,字符裁剪也采用分歧的方式。 切确裁剪是对单个字符进行裁剪。此时笔划式字符可看做是短曲线段的调集,用裁剪线段的方式进行裁剪。点阵式字符必需将字符方框中每一象素同裁剪窗口进行比力,以确定它位于窗口内仍是窗口外。若位于窗口内,该象素被激活,不然不予考虑。 若是把每个字符看做是不成朋分的全体,那么对每一个字符串就可用逐字裁剪的方式。这可将字符方框同裁剪窗口进行比力,若整个方框位于窗口内,则显示响应字符,不然不予显示。 最初一种处置方式是把一个字符串做为不成朋分的全体来处置,或者全数显示,或者全数不显示。将字符串用一个字符串框封锁起来,若整个方框位于窗口内,则显示整串字符,不然整串字符就不显示。串精度裁剪:将包抄字串的外接矩形对窗口做裁剪。当字符串方框整个正在窗口内时予以显示,不然不显示。 字符精度裁剪:将包抄字的外接矩形对窗口做裁剪,某个字符方框整个落正在窗口内予以显示,不然不显示。 笔画象素精度裁剪:将笔划分化成曲线段对窗口做裁剪,处置方式同上。 总结 本文次要涉及二维图形的裁剪算法,裁剪有内裁剪及外裁剪, 即对各类分歧的原始图形,如点、矢量线段、彩票九,文本、多边形及曲线等进行判断, 把显示窗口以内的部门保留, 而裁去窗口以外的图形,称为内裁剪; 反之, 称为外裁剪。本文次要涉及线段的矢量裁剪、线段的编码裁剪法、多边形的裁剪、圆的裁剪、双边裁剪法、非矩形裁剪窗口的线段裁剪、曲线的裁剪、字符的裁剪。 参考文献 [1] 韩俊卿 葛永慧 升 多边形窗口的矢量图形裁剪算法 太道理工大学矿业工程学院 1987.146~178 [2]刘怯奎 高云 黄有群 一个无效的多边形裁剪算法 1996(2):29-1. [3] 王沉培 周艳红 周济 肆意二维图形的复杂窗口裁剪算法及其使用 1994 [4] 刘怯奎 赵慧杰 六角网格上的图形裁剪算法 20029(7):14-7. [5] 刘怯奎 图形裁剪算法研究 2001(8):24-8. [6] 李岩 商书元 冯振声 基于包抄盒手艺的圆弧裁剪算法 电子工业出书社,2005:272-274 [7] 刘怯奎 圆形及卵形裁剪窗口 沈阳工业大学计较机学院 1994 [8] 韩丽 基于六角网格的矩形窗口的圆裁剪法 2003 [9] 眸中海 全 肆意多边形的裁剪 农业工程大学学报.1993:13-4. [10] 朱仁芝 刘磊 陶涛 江涌 吴震 一种多功能的二维图形裁剪算法及其使用 郑阳师范高档专科学校学报.2001(6):21-3. [11] 吴有富 Conen—Sutherland算法的改良及其推广 西北工业大学报,2007,25(6):890-895 [12]陈传波,陆枫. 计较机图形学根本[M]. :电子工业出书社,2005:272-274 [13]张全伙,张剑达. 计较机图形学[M]. :机械工业出书社,2003:245-247 [14]李东,孙长嵩,苏小红. 计较机图形学适用教程[M] .:人平易近邮电出书社,2004: 239-241 [15]GraphicsMentor: A Tool for Learning Graphics Fundamentals 2nd Edition, Addison-Wesley, 1990. [16]Patrick Baudisch, Desney Tan, Drew Steedly, Eric Rudolph [J] .IBM Systems Journal ,1965,4(1):25-30 [17]Efficient Scale-space Spatiotemporal Saliency Tracking for Distortion-Free Video Retargeting [J]. Computer Graphics,1991,5(4):143-152. 计较机图形学课程设想由:天空乐土网郑州大学生兼职收集 由开封市同力根本工程无限公司拾掇出书!

  1.本坐不应用户上传的文档完整性,不预览、不比对内容而间接下载发生的问题本坐不予受理。

【字号: 】 【打印】 【关闭】 点击量:

Copyright 2019-2022 http://www.hzdechang.cn 版权所有 未经协议授权禁止转载