GPDOF -- a fast algorithm to decompose under-constrained geometric constraint systems: application to 3d modeling. Our approach exploits a general-purpose decomposition algorithm, called GPDOF, and a dictionary of very efficient solving procedures, called r-methods, based on theorems of geometry. GPDOF decomposes an equation system into a sequence of small subsystems solved by r-methods, and produces a set of input parameters. Recursive assembly methods (decomposition-recombination), maximum matching based algorithms, and other famous propagation schema are not well-suited or cannot be easily extended to tackle geometric constraint systems that are under-constrained. In this paper, we show experimentally that, provided that redundant constraints have been removed from the system, GPDOF can quickly decompose large under-constrained systems of geometrical constraints. We have validated our approach by reconstructing, from images, 3D models of buildings using interactively introduced geometrical constraints. Models satisfying the set of linear, bilinear and quadratic geometric constraints are optimized to fit the image information. Our models contain several hundreds of equations. The constraint system is decomposed in a few seconds, and can then be solved in hundredths of seconds.
Keywords for this software
References in zbMATH (referenced in 8 articles , 1 standard article )
Showing results 1 to 8 of 8.
- Aftab, Khurrum; Hartley, Richard; Trumpf, Jochen: (L_q)-closest-point to affine subspaces using the generalized Weiszfeld algorithm (2015)
- Bomhoff, Matthijs; Kern, Walter; Still, Georg: On bounded block decomposition problems for under-specified systems of equations (2012)
- Neveu, Bertrand; Trombettoni, Gilles; Chabert, Gilles: Improving inter-block backtracking with interval Newton (2010)
- Jermann, Christophe; Trombettoni, Gilles; Neveu, Bertrand; Mathis, Pascal: Decomposition of geometric constraint systems: a survey (2006)
- Michelucci, Dominique; Foufou, Sebti: Geometric constraint solving: the witness configuration method (2006)
- Neveu, Bertrand; Chabert, Gilles; Trombettoni, Gilles: When interval analysis helps inter-block backtracking (2006)
- Trombettoni, Gilles; Wilczkowiak, Marta: GPDOF -- a fast algorithm to decompose under-constrained geometric constraint systems: application to 3d modeling (2006)
- Neveu, Bertrand; Jermann, Christophe; Trombettoni, Gilles: Inter-block backtracking: Exploiting the structure in continuous CSPs (2005)