{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/22002"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/22002","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Spatial reasoning for computer aided design, manufacturing and process planning","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Ruiz, Oscar Eduardo"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mechanical Engineering","degree_department":null,"school":null,"contributors":["Ferreira, Placid M."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T13:25:49Z","date_published":"2011-05-07T13:25:49Z","updated_at":"2026-07-22T22:25:19Z","subjects":["Engineering, Industrial","Engineering, Mechanical"],"languages":["eng"],"rights":["Copyright 1995 Ruiz, Oscar Eduardo"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9522166","(UMI)AAI9522166"],"render_values":[{"text":"AAI9522166","href":null,"code":true},{"text":"(UMI)AAI9522166","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/22002","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Ferreira, Placid M."]},{"key":"dc:creator","label":"Author","values":["Ruiz, Oscar Eduardo"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T13:25:49Z","10000-01-01","1995"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mechanical Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Engineering, Industrial","Engineering, Mechanical"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1995 Ruiz, Oscar Eduardo"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9522166","(UMI)AAI9522166","http://hdl.handle.net/2142/22002"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2011-05-07T13:25:49Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9522166.pdf: 6093053 bytes, checksum: 7123cd7aeaceab09a6cab8e9ff0d2660 (MD5) Previous issue date: 1995","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:54:39Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:25:25-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Spatial reasoning for computer aided design, manufacturing and process planning"]}]}],"canonical_facts":{"dc:contributor":["Ferreira, Placid M."],"dc:creator":["Ruiz, Oscar Eduardo"],"dc:date":["2011-05-07T13:25:49Z","10000-01-01","1995"],"dc:description":["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.","Made available in DSpace on 2011-05-07T13:25:49Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9522166.pdf: 6093053 bytes, checksum: 7123cd7aeaceab09a6cab8e9ff0d2660 (MD5) Previous issue date: 1995","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:54:39Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:25:25-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9522166","(UMI)AAI9522166","http://hdl.handle.net/2142/22002"],"dc:language":["eng"],"dc:rights":["Copyright 1995 Ruiz, Oscar Eduardo"],"dc:subject":["Engineering, Industrial","Engineering, Mechanical"],"dc:title":["Spatial reasoning for computer aided design, manufacturing and process planning"],"dc:type":["text"],"thesis:degree_discipline":["Mechanical Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:19Z"}