Contributing vertices-based Minkowski sum of a non-convez polyhedron without fold and a convez polyhedron

摘要：

We present an original approach for the computation of the Minkowski sum of a non-convex polyhedron without fold and a convex polyhedron, without decomposition and union steps—that constitute the bottleneck of convex decomposition-based algorithms. A non-convex polyhedron without fold is a polyhedron whose boundary is completely recoverable from three orthographic projections defined by three orthogonal basis vectors in R3. First, we generate a superset of the Minkowski sum facets using the concept of contributing vertices we accommodate for a non-convex–convex pair of polyhedra. The generated superset guarantees that its envelope is the boundary of the Minkowski sum polyhedron. Secondly, we extract the Minkowski sum facets and handle the intersections among the superset facets by using 3D envelope computation. Our approach is limited to non-convex polyhedra without fold because of the use of 3D envelope computation to recover the Minkowski sum boundary. Models with holes are not handled by our method. The implementation of our algorithm uses exact number types, produces exact results, and is based on CGAL, the Computational Geometry Algorithms Library.

关键词： Minkowski sum contributing vertices 3D envelope computation

作者: Hichem Barki Florence Denis Florent Dupont

作者单位: Université de Lyon, CNRS-Université Lyon 1, LIRIS, UMR5205-43 Bd.Du 11 novembre 1918, F-69622Villeurbanne, France

会议类型: 国际会议

会议名称: IEEE International Conference on Shape Modeling and Applications (SMI)(2009年形状建模国际会议)

会议地点: 北京

会议语种:英文

页码: 73-80

在线出版日期: 2009-06-26（万方平台首次上网日期，不代表论文的发表时间）