Computational Geometry

浏览量:99

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
浏览量:113

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
浏览量:107

参考

    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
浏览量:990

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
浏览量:978

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
浏览量:265

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
浏览量:176

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
浏览量:84

参考

      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
浏览量:669

3.7. 线段集的交

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 3.7. 线段集的交 本小节重点解决求线段集中所有交点的问题,首先会先介绍线段集相交算法的发展历史及其应用,然后介绍Shamos-Hoey算法的基本思想,因为Bentley-Ottmann算法只是对它的扩展,最后着重介绍Bentley-Ottmann算法的基本思想和实现。 3.7.1. 线段集相交算法简介 求\(n\)条线段的相交测试,最多有\(n\left( {n – 1} \right)/2 = O({n^2})\)个交点,最坏情况下就需要一个时间复杂度为\(O({n^2})\)的算法。最简单的暴力算法就是分别对\(O({n^2})\)个线段对进行相交测试,并记录下所有的交点,但对于只有少数交点的线段集,则不需要对每个线段对进行相交测试。 设\(S\)是\(n\)条线段的集合,\(I\)是线段集\(S\)中所有的\(k\)个交点的集合,当\(k = \left( {n – 1} \right)n/2\)时,是最坏情况。早在1976年,Shamos&Hoey提出了通过扫描线的方法在时间为\(O(n\log n)\)、空间为\(O(n)\)内判定集合\(S\)中是否存在相交点的算法。3年后,Bentley&Ottmann对该算法进行了扩展,新的算法能在时间为\(O(n\log n + k\log n)\)、空间为\(O(n + k)\)内,计算集合\(S\)中所有的交点,Pach& Sharir(1991)、Brown(1981)把该算法的空间降低到了\(O(n)\)。由于Bentley-Ottmann算法容易理解、实现较为简单,因此在之后的几十年里得到广泛的应用,但是求线段集所有交点的问题的理论下限为\(O(n\log n + k)\),Bentley-Ottmann算法并没有达到理论上的下限,Chazelle(1986)提出了一种时间为\(O(n{\log ^2}n/\log \log n + k)\)的算法,进一步降低了时间复杂度。直至1988年,Chazelle& Edelsbrunner提出了时间复杂度达到最优的算法,但是他们提出的算法需要\(O(n + k)\)的空间,而且很难实现。后来,Balaban

spacer
浏览量:126

3.6. 直线之间的夹角

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 3.6. 直线之间的夹角 问题描述:求两条直线\({L_0}(s) = {P_0} + s{\vec d_0}\)和\({L_1}(t) = {P_1} + t{\vec d_1}\)之间的夹角。 这可以利用点积和角度之间的关系来计算,有: \ 图3.22两条方向相同的直线 图3.23两条方向相反的直线 角度值介于0到180。之间,主要依据两条向量\({\vec d_0}\)和\({\vec d_1}\)的方向,如图3.22所示,如果两条直线方向相同,它们间的夹角小于90。;相反,如图3.23所示,当它们的方向相反时,它们间的夹角大于90。。  

spacer