Solving the pentahedron problem

Hichem Barki, Jean Marc Cane, Lionel Garnier, Dominique Michelucci, Sebti Foufou

Research output: Contribution to journalArticlepeer-review

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

Original languageEnglish (US)
Pages (from-to)200-209
Number of pages10
JournalCAD Computer Aided Design
Volume58
DOIs
StatePublished - Jan 2015

Keywords

  • Al-Kashi theorem
  • Desargues' theorem
  • Geometric constraint solving problems
  • Geometric modeling with constraints
  • Interval solver
  • Pentahedron

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Industrial and Manufacturing Engineering

Fingerprint

Dive into the research topics of 'Solving the pentahedron problem'. Together they form a unique fingerprint.

Cite this