Spatial reasoning for computer aided design, manufacturing and process planning

Reasoning about geometric relations and construction of scenes satisfying them are critically important tasks in computer-aided design, manufacturing and process planning. This work addresses these tasks by producing a centralized server for static and dynamic geometric reasoning. Static reasoning involves geometric algorithms with fully and consistently defined entities. The algorithms include (i) constructive queries (intersection, projections, convex hulls, etc); and (ii) logical queries (testing of inclusion, intersection, etc.). Dynamic reasoning addresses the geometric constraint satisfaction or scene feasibility (GCS/SF) problem. In GCS/SF, a context world is used to propose a series of geometric constraints among undefined entities (points, planes, lines, polyhedra). The objective is to obtain either a diagnostic of inconsistency, or a set of entities satisfying the constraints. The solution to GCS/SF finds applications in fixturing, assembly planning, parametric design, tolerancing analysis, kinematic analysis of mechanisms, etc. GCS/SF can be expressed as a set of polynomial equations, with the feasible configurations corresponding to common roots of the polynomials. Using known results in algebraic geometry, this work maps properties of Grobner bases to the GCS/SF domain. The mapping allows to determine multiplicity of feasible scenarios, redundancy and consistency of constraints, and degrees of freedom of the entities involved. A compact and efficient formulation in terms of the subgroups of the special Euclidean group of displacements SE(3) has been used in conjunction with the Grobner bases algorithm. The integration of these techniques (i) lowers the computational cost of the problem; (ii) relates Grobner Bases to the degrees of freedom of the entities; (iii) integrates the topological (nature of the constraints) and geometrical (dimensions of the scene) aspects; and (iv) places no restriction on the constraints modeled. This research has also explored a Divide and Conquer strategy that identifies GCS/SF subproblems which are solved separately and then consolidated in the overall solution. Experimental results obtained reflect the advantages of this approach. Applications of this work to mobility analysis of mechanisms, feasibility analysis of assemblies and form feature extraction are discussed.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mechanical Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Ruiz, Oscar Eduardo

Contributors dc:contributor

• Ferreira, Placid M.

• Engineering, Industrial
• Engineering, Mechanical

Statement dc:rights

• Copyright 1995 Ruiz, Oscar Eduardo

Language dc:language

eng

Identifier

AAI9522166
(UMI)AAI9522166

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/22002