TY - JOUR

T1 - Solving the pentahedron problem

AU - Barki, Hichem

AU - Cane, Jean Marc

AU - Garnier, Lionel

AU - Michelucci, Dominique

AU - Foufou, Sebti

N1 - Funding Information:
This publication was made possible by NPRP grant #09-906-1-137 from the Qatar National Research Fund (a member of Qatar Foundation). The statements made herein are solely the responsibility of the authors.
Publisher Copyright:
© 2014 Elsevier Ltd. All rights reserved.

PY - 2015/1

Y1 - 2015/1

N2 - 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 (x 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.

AB - 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 (x 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.

KW - Al-Kashi theorem

KW - Desargues' theorem

KW - Geometric constraint solving problems

KW - Geometric modeling with constraints

KW - Interval solver

KW - Pentahedron

UR - http://www.scopus.com/inward/record.url?scp=84920716701&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84920716701&partnerID=8YFLogxK

U2 - 10.1016/j.cad.2014.08.027

DO - 10.1016/j.cad.2014.08.027

M3 - Article

AN - SCOPUS:84920716701

SN - 0010-4485

VL - 58

SP - 200

EP - 209

JO - CAD Computer Aided Design

JF - CAD Computer Aided Design

ER -