浏览量:75

参考

      Mike Cyrus, and Jay Beck. "Generalized two-and three-dimensional clipping."Computers & Graphics, vol.3, no.1, pp.23-28, 1978.       You-Dong Liang, and Brian A. Barsky. "A new concept and method for line clipping." ACM Transactions on Graphics (TOG), vol.3, no.1, pp.1-22, 1984.

spacer
浏览量:151

5.3. 对线性对象的裁剪

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 5.3. 对线性对象的裁剪 5.3.1. 裁剪算法综述 问题描述:求矩形对象\(R:X({{t}_{0}},{{t}_{1}})=C+{{t}_{0}}\cdot {{\vec{e}}_{0}}+{{t}_{1}}\cdot {{\vec{e}}_{1}},-{{u}_{0}}\le {{t}_{0}}\le {{u}_{0}},-{{u}_{1}}\le {{t}_{1}}\le {{u}_{1}}\)对线段\({{P}_{0}}{{P}_{1}}\)的裁剪。 图5.5 线段的端点坐标沿着矩形的两条轴的投影 Cyrus-Beck算法解决了凸多边形或者凸多面体对象对线性对象的裁剪,矩形也是一个凸多边形,同样适用。在图形学中,有一个经典的问题,就是矩形窗口对线段的裁剪,即二维平面上轴对齐的矩形对线段的裁剪问题。对于非轴对齐的矩形的裁剪,可以把线段坐标按矩形的两条互相垂直的轴作投影,把矩形转化为轴对齐的情况。如图5.5所示,把线段的两个端点\({{P}_{0}}\)和\({{P}_{1}}\)投影到\({{\vec{e}}_{0}}\)和\({{\vec{e}}_{1}}\)上,得到新的坐标P0'和P1',投影等式为\( {{P}_{0}}'=\left( ({{P}_{0}}-C)\cdot {{{\vec{e}}}_{0}},({{P}_{0}}-C)\cdot {{{\vec{e}}}_{1}} \right),{{P}_{1}}'=\left( ({{P}_{1}}-C)\cdot {{{\vec{e}}}_{0}},({{P}_{1}}-C)\cdot {{{\vec{e}}}_{1}} \right)\),问题就转化为求轴对齐的矩形对线段P0'P1'的裁剪问题。求出裁剪后的线段Q0'Q1'后,再变换成原矩形的坐标,设\({{Q}_{0}}'=({{x}_{0}},{{y}_{0}}),{{Q}_{1}}'=({{x}_{1}},{{y}_{1}})\),则变换等式是\({{Q}_{0}}={{x}_{0}}{{\vec{e}}_{0}}+{{y}_{0}}{{\vec{e}}_{1}}+C,{{Q}_{1}}={{x}_{1}}{{\vec{e}}_{0}}+{{y}_{1}}{{\vec{e}}_{1}}+C\)。下面将重点讨论轴对齐的矩形对线段的裁剪算法。 大致有五种算法,可以解决轴对齐的矩形对线段的裁剪算法。最早由Danny Cohen&Ivan Sutherland提出的一种算法,称为Cohen-Sutherlad裁剪算法(简称CS算法),该算法把平面分成9个区域,根据点的位置确定与矩形的相交边。后来,Cyrus&Beck(1978)提出了Cyrus-Beck裁剪算法(简称CB算法),线段用参数方程来表示,计算与矩形的每条边所在的直线的交点,但是该算法的效率相对较低。Liang&Barsky(1984)尝试对CS算法进行改进,提出了该算法的一种变种,称为Liang-Barsky裁剪算法(简称为LB算法),Liang和Barsky(1992)进一步对LB算法进行了改进。Sobkow&Pospisil&Yang(1987)描述了另外一种线段的裁剪算法,称为快速裁剪算法(简称为SPY算法)。Nicholl,Lee&Nicholl对前面四种线段裁剪算法进行了较为深入地分析和比较,并且描述了一种更加高效的算法,称为Nicholl-Lee-Nicholl算法(简称为NLN算法)。对比五种算法的性能,它们并不是在数量级上的差别,只是算法中运算个数的差别,比如NLN算法拥有最少的除法次数。CS、LB和SPY在不同机器、不同的数据集上,会显示出不同的算法性能。在算法实现上,NLN和SPY算法较为复杂,CS和LB相对简单。如果不会特别苛求算法的性能,建议选择CS或者LB算法,接下来将详细地描述这两种算法。 5.3.2. Cohen-Sutherland裁剪算法 设矩形的左侧边为\(x={{x}_{\min }}\),右侧边为\(x={{x}_{\max }}\),下侧边为\(y={{y}_{\min }}\),上侧边为\(y={{y}_{\max }}\)。矩形的四条边所在的直线,把平面分成9个区域,可以用4位的编码来指定点所在的区域,我们可以作如下所规定: 0000       点在矩形区域内; 0001       点在左侧边的左侧; 0010      

spacer
浏览量:92

5.2. 点与矩形

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 5.2. 点与矩形 5.2.1. 点到矩形的矩离 问题描述:在二维空间上,计算点P到矩形对象\(R:X({{t}_{0}},{{t}_{1}})=C+{{t}_{0}}\cdot {{\vec{e}}_{0}}+{{t}_{1}}\cdot {{\vec{e}}_{1}},-{{u}_{0}}\le {{t}_{0}}\le {{u}_{0}},-{{u}_{1}}\le {{t}_{1}}\le {{u}_{1}}\)的距离。 图5.2 矩形把平面划分的9个区域 令\(\Delta =P-C\),有\({{s}_{0}}=\Delta \cdot {{\vec{e}}_{0}}\)和\({{s}_{1}}=\Delta \cdot {{\vec{e}}_{1}}\),矩形上与P最接近的点取决于参数平面\( ({{t}_{0}},{{t}_{1}})\)上9个区域中的哪一个包含\(({{s}_{0}},{{s}_{1}})\),平面上9个区域的划分如图5.2所示。若\(({{s}_{0}},{{s}_{1}})\)落在区域0中,说明点P在矩形内部,它到矩形的距离是0;若\(({{s}_{0}},{{s}_{1}})\)落在区域1、3、5、7上,则\(({{s}_{0}},{{s}_{1}})\)到矩形对应的顶点上的距离最近;若\(({{s}_{0}},{{s}_{1}})\)落在区域2、6上,则最近距离是点P到边\({{\vec{e}}_{1}}\)的投影;若\(({{s}_{0}},{{s}_{1}})\)落在区域4、8上,则最近距离是点P到边\({{\vec{e}}_{0}}\)的投影。 在算法的具体实现中,不需要将参数平面划分成9个区域,然后分成不同的区域来处理,采用每次处理一维,点与矩形距离的伪码如下所示: 求点P到矩形对象\(R:X({{t}_{0}},{{t}_{1}})=C+{{t}_{0}}\cdot {{\vec{e}}_{0}}+{{t}_{1}}\cdot {{\vec{e}}_{1}}\)的距离的平方 1.    计算\(\Delta =P-C\); 2.    计算\({{s}_{0}}=\Delta \cdot {{\vec{e}}_{0}}\)和\({{s}_{1}}=\Delta \cdot {{\vec{e}}_{1}}\); 3.    distSquare = 0; 4.   

spacer
浏览量:98

5.1. 矩形对象简介

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 5.1. 矩形对象简介 二维的矩形对象,在图形学上起到重要的作用,比如碰撞检测。一个矩形形对象如图5.1所示,可以用等式(5.1)表示,其中C表示矩形的中心,\({{\vec{e}}_{0}}\)和\({{\vec{e}}_{1}}\)都是单位长度,表示矩形上互相垂直的两个方向,\({{u}_{0}}\)和\({{u}_{1}}\)分别是矩形在两个方向上的半长度,则有\(-{{u}_{0}}\le {{t}_{0}}\le {{u}_{0}}\)和\(-{{u}_{1}}\le {{t}_{1}}\le {{u}_{1}}\)。 \ 图5.1 矩形对象 实现矩形对象时,可以采用保存等式(5.1)中的矩形中心C,单位长度的两个方向向量\({{\vec{e}}_{0}}\)和\({{\vec{e}}_{1}}\),以及在两个方向上的边的半长\({{u}_{0}}\)和\({{u}_{1}}\)。采用这种表示形式,在计算矩形面积、周长,求点与矩形的距离等问题,都特别的方便。例如计算矩区的面积为\(4\cdot {{u}_{0}}\cdot {{u}_{1}}\),矩形的周长为\(2\cdot ({{u}_{0}}+{{u}_{1}})\)。

spacer
浏览量:103

参考

    Tomas Möller, and Ben Trumbore. "Fast, minimum storage ray-triangle intersection." Journal of graphics tools, vol.2, no.1, pp.21-28, 1997.     Philip J. Schneider, and David H. Eberly. Geometric Tools for Computer Graphics. Morgan Kaufmann, 2002.     Tomas Möller. "A fast

spacer
浏览量:906

4.4. 三角形与三角形的重叠检测

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 4.4. 三角形与三角形的重叠检测 问题描述:在三维空间上,有两个三角形\({T_1}:\Delta V_0^1V_1^1V_2^1\)和\({T_2}:\Delta V_0^2V_1^2V_2^2\),分别位于平面\({\pi _1}\)和\({\pi _2}\)上,判断这两个三角形是否重叠。 图4.12 三角形和它所在的平面 至少有六种算法可以用于判定三角形与三角形是否相交。第一种算法,也是最朴素的算法,速度最慢。第二种算法,由Möller et al(1997)提出了一种更加高效的算法,算法是基本思路是:若两个三角形相交,那么它们所在的平面必相交于一条直线,两个三角形分别在该直线上产生间隔,如图4.12所示,若间隔重叠,则两个三角形相交,否则,不相交,因此该方法也称为间隔重叠法。第三种算法,Guigue& Devillers (2003)对间隔重叠法进行改进,通过采用行列式的计算,来判断两个三角形是否相交,有效的避免的除法操作,由于不用求解实际的间隔值,浮点数的误差相对较小,因此也比第二种算法更稳定。第四种算法,Held(1997)实现了一个名为ERIT的软件包,用于三维空间的相交测试,ERIT包括了一种三角形与三角形相交测试的算法,该方法的算法比第一种算法高效,由于需要求交点操作,必需包括一些必要的除法运算,再根据求出的交点进行后续的判断,浮点数的精度误差更大,因此稳定性上也不如第二种和第三种算法。此外,Shen et al(2003)提出了一种通过计算线与线之间有向距离的方法,来判定两个三角形是否相交,还可以采用分离轴的方法实现相交测试。下面将分别介绍前四种算法的思想和实现方法。 4.4.1. 朴素算法 首先,判断三角形\({T_1}\)的每一条边,是否与三角形\({T_2}\)相交,若至少存在一条这样的边,说明两个三角形相交;接着,判断三角形\({T_2}\)的每一条边,是否与三角形\({T_1}\)相交。最坏情况下,需要做6次线段与三角形的相交测试,这是最容易想到的一种算法,也是最暴力的算法。 4.4.2. 间隔重叠法 Möller(1997)提出了通过判断两个三角形在相交直线上是否重叠的方法来实现两个三角形的重叠检测。设平面\({\pi _2}\)的参数方程表示为\({{\vec{d}}_{2}}\cdot X+{{D}_{2}}=0\),\(X\)是平面上的点,由三角形初始化一个平面,即\({{\vec{d}}_{2}}=(V_{1}^{2}-V_{0}^{2})\times (V_{2}^{2}-V_{0}^{2}),{{D}_{2}}=-{{\vec{d}}_{2}}\cdot V_{0}^{2}\)。 三角形\({{T}_{1}}\)上的顶点到到平面\({{\pi }_{2}}\)的有符号距离用如下等式表示,由于这里只需要判断有符号距离的符号,所以可以不需要除法\(\left\| {{{\vec{d}}}_{2}} \right\|\): \({{d}_{V_{i}^{1}}}={{\vec{d}}_{2}}\cdot V_{i}^{1}+{{D}_{2}},i=0,1,2 \tag{4.23}\) 现在,如果对于所有的\(i=0,1,2\),\({{d}_{V_{i}^{1}}}\ne 0\)(说明没有顶点在平面上),同时所有的值均具有相同的符号,那么\({{T}_{1}}\)的三个顶点都位于平面的同一侧。这样,就可以排除重叠的可能性。对于三角形\({{T}_{2}}\)和平面\({{\pi }_{1}}\),也需要这样的测试,测试过程也是相同的。这两步测试,可以避免很多不必要的计算,如果通过了这两个测试,说明两个平面必相交,两个平面相交于一条直线,即\({{\vec{d}}_{1}}\times {{\vec{d}}_{2}}\)一定存在。 如果对于所有的\(i=0,1,2,{{d}_{V_{i}^{1}}}=0\),说明两个三角形在同一个平面上,这种情况在后面会单独讨论。如果不是都为零的情况,设两个平面相交的直线的参数方程是\(L=O+t\vec{d}\),其中\(\vec{d}={{\vec{d}}_{1}}\times

spacer
浏览量:805

4.3. 线性对象与三角形的交

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 4.3. 线性对象与三角形的交 问题描述:在三维空间上,判断线性对象\(P + t\vec d\)与三角形\(\Delta {V_0}{V_1}{V_2}\)是否相交,若相交,求出交点,三角形所在的平面是\(\pi \)。 图4.11 直线与三角形的四种关系 三维空间的模型通常是由一个个三角形面片构成的,线性对象与三角形的相交检测也显得特别的重要。如图4.11所示,一条直线与三角形可能有四种关系:1)直线\({L_0}\)与三角形相交;2)直线\({L_1}\)与三角形所在的平面相交,但与三角形不相交;3)直线\({L_2}\)与在三角形所在的平面上;4)直线\({L_3}\)与三角形所在的平面平行。 一种朴素的检测算法是计算线性对象与三角形所在的平面的交点,再判断交点是否在三角形内。如果交点在三角形内,则线性对象与三角形相交;否则,不相交。这种算法效率不仅效率较低,而且更容易造成浮点数误差。因为计算机中的浮点数占用字节有限,能表示的精度有限,有效数较少,求直线与平面的交点,由于对同一个变量多次的乘法或者除法操作,造成误差的叠加,最后计算出来的结果由于精度问题,可能造成较大的误差。例如,三角形顶点的坐标数值较大,计算的直线与平面的交点,会由于精度误差导致求出的交点偏离平面,即可以检测到交点不在平面上。 Möller&Trumbore(1997)提出了一种更加高效的射线与三角形相交测试的算法,而且乘法或者除法操作造成的误差叠加较少,精度损失更小,因此性能上更加健壮。 三角形内的任意一点都可以用它相对于三角形的顶点的位置来定义: \(T(u,v) = (1 - u - v){V_0} + u{V_1} + v{V_2} \tag{4.18}\) 其中,\((u,v) \in D = \{ (u,v):u \ge 0,v \ge 0,u + v

spacer
浏览量:244

4.2. 点与三角形

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 4.2. 点与三角形 4.2.1. 点与三角形的关系 1. 二维空间 问题描述:在二维空间上,判断点\(P\)与三角形\({V_0}{V_1}{V_2}\)的关系,其中,\({V_i} = \left( {{x_i},{y_i}} \right),i \in \{ 0,1,2\} \)。 图4.3 点与三角形的三种关系 二维空间上点与三角形共有三种关系:三角形内,三角形边上和三角形外。如图4.3所示,\({P_0}\)在三角形内部,\({P_1}\)在三角形边上,\({P_2}\)在三角形外。 在二维空间上的叉积遵守右手定则,设有三个点\({B_0}\),\({B_1}\)和\({B_2}\),令\(d = \left( {{B_1} - {B_0}} \right) \times \left( {{B_2} - {B_0}} \right)\),如果\(d \succ 0\),则\({B_0}\),\({B_1}\)和\({B_2}\)三个点是逆时针方向分布;如果\(d \prec 0\),则是顺时针方向分布;无否则,有\(d = 0\),则三点是共线的。 如果点\(P\)在\(\Delta

spacer
浏览量:76

4.1. 三角形简介

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 4.1. 三角形简介 三角形面片,在图形学上有非常重要的应用,很多三维模型都是以三角形面片为基础图元。 在二维空间上,给定一个三角形\(T:\Delta {V_0}{V_1}{V_2}\),三角形的有符号面积可以表示为: \ 图4.1 逆时针朝向的三角形\(\Delta {V_0}{V_1}{V_2}\)和边\(\overline {{V_0}{V_1}} \)的法向量 三角形顶点顺序影响\({\mathop{\rm Area}\nolimits} (T) = \frac{1}{2}({V_1} - {V_0}) \times ({V_2} - {V_0})\)的正负,\(\left| {{\mathop{\rm Area}\nolimits} (T)} \right|\)表示三角形面积的大小。如果\({\mathop{\rm Area}\nolimits}

spacer
浏览量:77

参考

      Thomas H. Cormen, et al. Introduction to algorithms. Vol. 2. Cambridge: MIT press, 2001.       David Eberly. "Distance between two line segments in 3D." Magic Software Inc, 1999.       Philip Schneider, and David H. Eberly. "Geometric tools for computer

spacer