Solving the pentahedron problem. (January 2015)

• Record Type: Journal Article
• Authors: Barki, Hichem; Cane, Jean-Marc; Garnier, Lionel; Michelucci, Dominique; Foufou, Sebti
• Is Part Of: Computer aided design. Volume 58(2015)
• Page Start: 200
• Page End: 209
• Publication Date: 2015-01
• Subjects: Geometric constraint solving problems -- Pentahedron -- Geometric modeling with constraints -- Interval solver -- Desargues' theorem -- Al-Kashi theorem; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2014.08.027
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: Nowadays, all geometric modelers provide some tools for specifying geometric constraints. The 3D pentahedron problem is an example of a 3D Geometric Constraint Solving Problem (GCSP), composed of six vertices, nine edges, five faces (two triangles and three quadrilaterals), and defined by the lengths of its edges and the planarity of its quadrilateral faces. This problem seems to be the simplest non-trivial problem, as the methods used to solve the Stewart platform or octahedron problem fail to solve it. The naive algebraic formulation of the pentahedron yields an under-constrained system of twelve equations in eighteen unknowns. Even if the use of placement rules transforms the pentahedron into a well-constrained problem of twelve equations in twelve unknowns, the resulting system is still hard to solve for interval solvers. In this work, we focus on solving the pentahedron problem in a more efficient and robust way, by reducing it to a well-constrained system of three equations in three unknowns, which can be solved by any interval solver, avoiding by the way the use of placement rules since the new formulation is already well-constrained. Several experiments showing a considerable performance enhancement ( × 42 ) are reported in this paper to consolidate our theoretical findings. Throughout this paper, we also emphasize some interesting properties of the solution set, by showing that for a generic set of parameters, solutions in the form of 3D parallel edge pentahedra do exist almost all the time, and by providing a geometric construction for these solutions. The pentahedron problem also admits degenerate 2D solutions in finite number. This work also studies how these interesting properties generalize for other polyhedra. Highlights: Reduction of the pentahedron problem to a well-constrained system of 3 equations in 3 unknowns. A considerable performance enhancement ( × 42 ) over classical formulation. Existence of 3D parallel solutions for generic 3D pentahedron problems is shown. Interesting properties of the solution set are studied. Discussion of how the pentahedron interesting properties generalize for other polyhedra.