基于Minkowski和的多面体快速碰撞检测算法

为了进一步提高碰撞检测的实时性,提出一种基于Minkowski和的多面体快速碰撞检测算法.该算法以Minkowski和为工具,无需精确计算两个多面体之间的最短距离,首先通过构造两个多面体的Minkowski和,将多面体碰撞检测问题转化为判断原点是否在该Minkowski和内,然后运用射线和求交计算将三维空间问题转化为二维平面问题,再通过判断原点是否在平面多边形内来检测多面体是否发生碰撞,进而提高了碰撞检测的实时性和可靠性.在Visual C#环境下,利用OpenGL图形库搭建一个路径规划仿真系统.实验结果表明,该算法平均检测效率明显高于传统算法,并且有效降低了存储空间和时间复杂度.     

凸多面体连续碰撞检测的运动轨迹分离轴算法

针对凸体间的连续碰撞检测,在距离算法(Gilbert-Johnson-Keerthi distance algorithm,GJK)基础上,提出一种采用运动轨迹分离轴计算的线性连续碰撞检测算法.该算法首先采用支撑点和投影技术,剔除必定不发生碰撞的物体,以加速碰撞检测的速度;然后,对可能发生碰撞的物体,计算2个凸体的Minkowski差集,所形成的凸包与运动路径执行GJK分离轴算法,实现在整个时间区间内一次性完成碰撞检测任务;最后,采用几何方法以及超平面与射线求解方式计算射线与凸体边界近交点,确定出第一次发生碰撞位置,并调整运动物体位置,完成碰撞响应过程.该算法不需要构造扫掠体,连续检测过程中不需要凸体间的求交计算.将文中算法应用于物体方向包围盒的连续碰撞检测,算法分析和实验结果表明,该算法对包围盒的连续碰撞检测具有较高检测精度和响应速度.     

几何变换的误差传播

采用最坏情况法研究几何变换中的误差传播问题．在给出基本几何元素误差域表示方法的基础上，讨论对称、旋转变换的误差传播规律；并利用Minkowski算子，给出计算几何变换后误差域的算法，从而为进一步研究几何误差的控制奠定基础．     

蛋白质亚细胞定位预测的最近邻算法*

基于蛋白质的氨基酸组成,采用三种几何距离,即Euclidean 距离、Minkowski 距离和广义距离,利用最近邻算法对蛋白质亚细胞定位进行预测.结果表明该方法新颖、简单、有效.     

平面多边形Newell 公式的运用与推广

Newell 公式在计算机图形学中常被用于计算多边形面积和平面法向量。 论文主要讨论了Newell 公式的运用与推广。首先将其推广三维空间中用于计算多面体体积 的公式。其次讨论了在异面多边形的情况下,Newell 公式的几何意义。最后,从数值计算 的角度分析了Newell 公式的计算方法。     

利用点面提取的任意多面体快速靠接

文章主要讨论沿直线运动的多面体靠接问题.根据多面体的几何特性，通过一系列的筛选和变换将多面体的靠接问题转化成为计算少量点与平面多边形的距离问题，从而大大地提高了任意空间多面体靠接的计算速度.该算法可广泛地用于以多面体为数学模型的计算机图形学、机器人、多媒体和CAD/CAM等众多领域的系统中.     

几何代数的高阶逻辑形式化

几何代数是一种用于描述和计算几何问题的代数语言.由于它统一的表达分析和不依赖于坐标的几何计算等优点现已成为数学分析、理论物理、几何学、工程应用等领域重要的理论基础和计算工具, 然而利用几何代数进行计算和建模分析的传统方法,如数值计算方法和符号方法等都存在计算不精确或者不完备等问题.高阶逻辑定理证明是验证系统正确的一种严密的形式化方法.本文在高阶逻辑证明工具HOL-Light中建立了几何代数系统的形式化模型,主要包括片积、多重矢量、外积、内积、几何积、几何逆、对偶、基矢量运算和变换算子等的形式化定义和相关性质定理的证明.最后为了说明几何代数形式化的有效性和实用性,本文在共形几何代数空间中对刚体运动问题提供了一种新的简单有效的形式化建模与验证方法.     

二阶多面体网格中关键特征控制的表面重建技术

针对基于二阶多节点多面体网格的表面重建过程中存在的准确拓扑及绘制、传输代价等问题,提出了一种基于关键特征控制的表面重建技术.研究并分析了二阶多节点多面体单元等参插值函数的性质特征,在网格单元棱边插值计算曲面轮廓点,在网格表面及体内提取曲面的几何特征关键点;根据3类插值关键点间的逻辑关系制定了令拓扑准确唯一的面片三角化规则及修复策略,设计了基于关键点的三角面片压缩索引结构.实验结果表明,该方法可准确计算并描述基于二阶多节点多面体网格单元的曲面几何拓扑结构,反映网格单元内部面片的真实凹凸性质,克服了拓扑二义性,具备对不同精度要求的适应性,并有效降低了绘制与传输代价.     

凸多面体线消隐算法的研究与改进

为使三维形体有较强的立体感,物体因自身遮挡和物体间的相互遮挡产生的线段就必须被消除.在研究了三维几何形体消隐算法中的线消隐算法之后,针对传统的凸多面体线消隐算法存在计算量大、消隐时间长、效率低的缺点进行改进,在原来线消隐算法的基础上加入包围盒的最大最小测试方法和深度优先排序方法.算法使用C++编程实现,实验证明算法的时间复杂度由原来的N2降低为N,大大提高了消隐效率.     

二维凸壳算法在合成金属设计中的应用

计算几何主要研究解决几何问题的算法.计算几何在图形学、机器人技术、超大规模集成电路设计等诸多领域有着十分重要的应用.凸壳[1]是计算几何中最普遍、最基本的一种结构,凸壳不仅自身有许多特性,而且它还是构造其他几何形体的有效工具.在实际的应用中,许多实际问题可以通过构造凸壳转化为凸壳问题加以解决.详细地介绍了凸壳的基本概念和生成在一定点集上的凸壳的算法以及应用凸壳的基本原理来解决现实生活中的一些问题.     

Two Algorithms for Decomposing a Polyhedron into Convex Parts

Two algorithms are presented for splitting a polyhedron into convex components: one for the case of a simple polyhedron and one for a more general case, when the polyhedron may have ring-shaped faces and cavities. The time requirement in both cases is O ( DN log N ), where D is the number of concave dihedral angles and N is the number of edges. The algorithm for the simple oasis produces at most D + 1 convex pieces which is the minimal number of the convex components.     

On the minimum of a positive polynomial over the standard simplex

We present a new positive lower bound for the minimum value taken by a polynomial P$P$ with integer coefficients in k$k$ variables over the standard simplex of R^k${\mathbb{R}}^k$, assuming that P$P$ is positive on the simplex. This bound depends only on the number of variables k$k$, the degree d$d$ and the bitsize τ$\tau$ of the coefficients of P$P$ and improves all the previous bounds for arbitrary polynomials which are positive over the simplex.     

A method for detecting structure in polyhedra

A construction is given for associating a finite state automaton with a 3-dimensional polyhedron. It has the property that if a polyhedral segment is encoded as a string and used as input to the automaton, the automaton state which is reached contains information about all congruences of the segment with parts of the polyhedral surface. An application is retrieval from a polyhedral database, given as key a partial 3D view.     

Exact Minkowksi Sums of Polyhedra and Exact and Efficient Decomposition of Polyhedra into Convex Pieces

We present the first exact and robust implementation of the 3D Minkowski sum of two non-convex polyhedra. Our implementation decomposes the two polyhedra into convex pieces, performs pairwise Minkowski sums on the convex pieces, and constructs their union. We achieve exactness and the handling of all degeneracies by building upon 3D Nef polyhedra as provided by Cgal. The implementation also supports open and closed polyhedra. This allows the handling of degenerate scenarios like the tight passage problem in robot motion planning. The bottleneck of our approach is the union step. We address efficiency by optimizing this step by two means: we implement an efficient decomposition that yields a small number of convex pieces, and develop, test and optimize multiple strategies for uniting the partial sums by consecutive binary union operations. The decomposition that we implemented as part of the Minkowski sum is interesting in its own right. It is the first robust implementation of a decomposition of polyhedra into convex pieces that yields at most O(r ²) pieces, where r is the number of edges whose adjacent facets comprise an angle of more than 180 degrees with respect to the interior of the polyhedron. This work was partially supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.023.301.     

Integration of polynomials over n-dimensional polyhedra

Explicit formulae and algorithms for computing integrals of polynomials over n-dimensional polyhedra are given. Two different approaches are discussed: one uses a decompositive representation, while the other one uses a boundary representation of the polyhedron. The algorithms are followed by a discussion of the complexity. In the appendix the pseudo-code and some examples of calculation are given.     

Extrusion and boundary evaluation for multidimensional polyhedra

Extrusion is a basic operation allowing the generation of higher intrinsic dimension polyhedra. The paper gives closed formulas both to generate a (d+1)-dimensional polyhedron obtained by affine extrusion of a (d)-dimensional polyhedron, and to generate by rotational extrusion. Algorithms for the boundary evaluation when a decompositive representation is given are also discussed.

The representation used in the paper, based on simplicial complexes, is general and simple, and allows us to represent nonconvex, unconnected, unoriented, nonmanifold and unbounded linear polyhedra. A simplicial complex triangulating the extruded polyhedron is generated by independently extruding the simplices of the input object. The approach is very efficient because no a posteriori triangulation of the extruded polyhedron is required; furthermore, both the underlying complex and the adjacencies between cells are calculated by using closed formulas.