Solution space navigation for geometric constraint systems

Meera Sitharam

doi:10.1145/1138450.1138452

Return

Solution space navigation for geometric constraint systems

2006-04-01

PRE

Meera Sitharam *

Yong Zhou

DOI：10.1145/1138450.1138452

Original

Original request for help

Save

Abstract

En 中文

We study the well documented problem of systematically navigating the potentially exponentially many roots or realizations of well-constrained, variational geometric constraint systems. We give a scalable method called the Equation and Solution Manager (ESM) that can be used both for automatic searches and visual, user-driven searches for desired realizations. The method incrementally assembles the desired solution of the entire system and avoids combinatorial explosion by offering the user a visual walk-through of the solutions to recursively constructed subsystems and by permitting the user to make gradual, adaptive solution choices. We isolate requirements on companion methods that are essential and desirable for efficient, meaningful solution space navigation. Specifically, they permit (a) incorporation of many existing approaches to solution space steering or navigation into the ESM; and (b) integration of the ESM into a standard geometric constraint solver architecture. We address the latter challenge and explain how the integration is achieved. Additionally, we sketch the ESM implementation as part of an opensource, 2D and 3D geometric constraint solver, FRONTIER.

Keywords:

algorithms

design

performance

theory

root selection for geometric constraint systems

well constrained systems

underconstrained and overconstrained systems

constraint graphs

cyclical and 3D geometric constraint systems

variational geometric constraint solving

decomposition of geometric constraint systems

degree of freedom analysis

conceptual design

feature-based and assembly modeling

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.