9. 包围体

浏览量:99

参考

       Joseph O'Rourke. "Finding minimal enclosing boxes." International journal of computer & information sciences, vol.14, no.3, pp.183-199, 1985.        David H. Eberly. 3D game engine design: a practical approach to real-time computer graphics. CRC Press, 2006.        Gill Barequet, and

spacer
浏览量:379

9.3. 包围球

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 9.3. 包围球 9.3.1. 最小包围球的创建 问题描述:给定一个点集\(S = \left\{ {{P_0},{P_1}, \cdots ,{P_{n - 1}}} \right\}\),求包围该点集的最小包围球。 早在1982年,Megiddo提出了第一个在三维空间下求最小包围球的线性算法,但是该算法实现难度较大。 Ritter(1990)提出了一种估计算法,该算法非常简单,但并不能得到最小包围球。主要思想是从点集\(S\)中,找到\(x\)值、\(y\)值、\(z\)值最小和最大的点,从这三组点对中找出距离最大的一组点对,取这组点对的中心作为球体的中心\(c\),取点对距离的一半作为球的半径\(r\)。接着,再次遍历点集\(S\),检查点\({{p}_{k}}\)与中心的距离\(d\),如果\(d\succ r\),说明点在球外,将半径更新为\(r'=(d+r)/2\),并将球心向该点移动\((d-r)/2\),即新的球心为\(c'=c+({{p}_{k}}-c)\cdot (d-r)/(2d)\),重复这个过程,直至点集\(S\)中所有的点都包含在球内。 Welzl(1991)提出了一种通过使用随机化的方法来解决问题,算法复杂度的期望是线性的,且算法相对简单、易实现。该算法不仅能得到二维、三维的最小包围球,而且能扩展到更高维的情况,通过“重要点前移”的优化步骤,能显著的提高算法的效率。Gärtner详细地描述了该算法的实现,并提供了C++的代码实现,在CGAL也有该算法的实现,本节将介绍该算法。 以三维空间下的最小包围球为例,定义\(\text{MB}\left( S \right)\)表示点集\(S\)的最小包围球,显然,\(\text{MB}\left( S \right)\)是唯一的。设\({{D}_{1}}\)和\({{D}_{2}}\)是点集\(S\)的两个最小包围球,半径都是\(r\),球心分别是\({{c}_{1}}\)和\({{c}_{2}}\)。有\(S\subset {{D}_{1}}\)且\(S\subset {{D}_{2}}\),所以有\(S\subset {{D}_{1}}\bigcap {{D}_{2}}\),\({{D}_{1}}\bigcap {{D}_{2}}\)被包含在以\(({{c}_{1}}+{{c}_{2}})/2\)为球心,\(\sqrt{{{r}^{2}}-{{a}^{2}}}\)为半径的球内,其中\(a\)表示两个球心距离的一半。若\(a\ne 0\),则存在半径更小的、包含点集\(S\)的球,与假设条件矛盾,因此\(a=0\),\({{D}_{1}}\)和\({{D}_{2}}\)是重合的。 设\(P,R\)是点集\(S\)的两个子集,且满足\(P \cup R = S,P \cap R = \emptyset

spacer
浏览量:674

9.2. 包围盒

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 9.2. 包围盒 9.2.1. 最小有向包围盒的创建 问题描述:给定一个点集\(S=\left\{ {{P}_{0}},{{P}_{1}},\cdots ,{{P}_{n-1}} \right\}\),求包围该点集的最小有向包围盒。 通常这个问题可以简化为求凸多面体的最小有向包围盒问题,关于最小有向包围盒的创建方法有很多,O'Rourke在1985年提出了一种复杂度是\(O({{n}^{3}})\)的精确算法。包围盒在碰撞检测中有很重要的应用,为了提高效率,可以采用更高效的有向包围盒估计算法,评价最小有向包围盒估计算法有两个非常重要的指标:效率和紧密度,即要在尽可能短的时间内,创建出尽可能紧密的拟合点集的包围盒。Barequet和Har-Peled(2001)提出了两种估计算法,一种实现难度较大、复杂度是\(O(n+1/{{\varepsilon }^{4.5}})\)的算法(其中\(0\prec \varepsilon \le 1\)),另外一种相对较容易实现、复杂度是\(O(n\log n+n/{{\varepsilon }^{4.5}})\)的算法。而Gottschalk则提出了一种线性的估计算法,虽然不是最优拟合,但是紧密度上也表示很好,本节将介绍该算法。 首先计算出点集的三维凸包,参见第九章,可以得到\(n\)个三角形,记为\(\Delta {{p}^{k}}{{q}^{k}}{{r}^{k}},0\le k\prec n\),其中\({{p}^{k}}\)、\({{q}^{k}}\)、\({{r}^{k}}\)分别是三角形的3个顶点,三角形的面积记为\({{A}^{k}}\),凸包的整个面积就记作 \ 此外,三角形的质心记为\({{m}^{k}}=({{p}^{k}}+{{q}^{k}}+{{r}^{k}})/3\),也就是3个顶点的平均值,整个凸多面体的质心的加权平均值记为 \

spacer
浏览量:155

9.1. 包围体简介

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 9.1. 包围体简介 在计算机图形学与计算几何领域,包围体(Bounding Volume)就是指把自然物体包容起来的密闭空间。如图9.1所示,就是两类包围体:包围球和包围盒。通常,物体的空间结构比较复杂,需要有上百个顶点组成。如果需要判断两个物体是否发生碰撞,直接采用物体的结构来检测,会使计算量非常的大,而采用包围体,则可以有效的排除不相交的不重叠的情况,降低计算机的开销。 图9.1 包围体 包围体最主要的用途是降低碰撞检测的开销,评价包围体性能的好坏,可以依据如下几个指标: 创建开销; 紧密度; 相交测试; 内存占用性况; 是否容易旋转和变换; 如果一个包围体的创建开销越低,紧密度越好,相交测试简单,内存占用低,容易做旋转和变换,那么这种类型的包围体性能就越好。 常用的包围体有,轴对齐包围盒(AABB),有向包围盒(OBB),包围球,k-离散有向多面体(k-DOP)。其中,轴对齐包围盒创建较为简单,只要将物体的顶点沿着三维空间的3个坐标轴做投影,取得最小值和最大值即可。k-离散有向多面体是轴对齐包围盒的扩展,只要将物体的顶点沿着面的法向量\({{\vec{n}}_{i}}\)做投影,取得最小值和最大值即可创建出k-离散有向多面体。

spacer