Title: Applications of Randomized Motion Planning in Intelligent CAD
Motion planning arises in a diverse set of application domains such as robotics, computer animation (digital actors), intelligent CAD (virtual prototyping and training), and even computational biology (protein folding or drug design). As one example, a motion planner could be used to find a part removal path in a mechanical assembly. This path could be archived and used in a VR training system for mechanics, or as on-line aid during actual task execution in a mixed reality environment. A typical mechanical assembly consisting of both rigid and flexible parts arranged in a compact design would yield a very difficult, high degree of freedom motion planning problem.
Surprisingly, a single class of planners, called probabilistic roadmap methods (PRMs), have proven effective on challenging motion planning problems from all domains. In this talk, we describe the PRM framework and give an overview of several PRM variants developed in our group that are relevant to CAD, including planners for systems containing foldable objects, deformable objects, or closed kinematic chains. For virtual prototyping scenarios, we present preliminary results of a planner for disassembly sequencing and we show that in some cases a hybrid system incorporating both an automatic planner and haptic user input can solve more difficult problems faster than a fully automatic system.
This is joint work with O. Burchan Bayazit, Jyh-Ming Lien, and Guang Song. More information regarding our work, including movies, can be found at http://parasol.tamu.edu/~amato
Title: Computing Shapes and Their Features from Point Samples
Recent advances in scanning technology and scientific simulations can generate sample points from a geometric domain at ease. Inferring the shape and their features from such a simple light-weight input can be a very effective modeling paradigm across many areas of science and engineering. In this talk we will go over the techniques developed for such modeling paradigms. In particular, we cover algorithms for (i) extracting a surface out of point samples, (ii) computing an approximate medial axis of the sampled object, (iii) segmenting the object into so called "features". Theoretical concepts along with experimental results will be presented.
Title: Geometric Algorithms for Layered Manufacturing: Part II
Layered Manufacturing (LM) is a relatively new technology that enables complex 3-dimensional parts to be built directly from their computer models, using a " 3-dimensional printer'' attached to a personal computer. In essence, the process involves orienting the model suitably, slicing it into parallel layers, and ``printing'' each layer on top of the previous one. LM is becoming increasingly important in computer-aided design and manufacturing because it provides the designer with an additional level of physical verification of the model, thereby allowing the detection and correction of flaws that may have otherwise gone unnoticed. LM is used extensively in the automotive, aerospace, and medical industries.
LM poses a number of interesting geometric problems whose efficient solution would enhance further the speed, accuracy, and utility of the process. These problems include choosing a suitable orientation of the model so as to optimize (various combinations of) certain design criteria (e.g., surface error, so-called support requirements, number of layers), efficient computation and location of support structures, generation of efficient tool-paths for printing the layers, and model decomposition to minimize support requirements. This talk, and the companion talk, will present an overview of the speakers' research on these problems over the past several years.
The material presented in these talks is the result of several joint research efforts by the speakers with various subsets of the following group of individuals: P. Gupta, M. Hon, I. Ilinkin, E. Johnson, J. Majhi, R. Sriram, and J. Schwerdt.
Papers and other information associated with these talks can be found here.
Title: Fast Discretized Algorithms for Arrangement Computations
Given a finite collection of geometric objects (S), the arrangement is the decomposition of the space into connected open cells induced by S. Arrangements serve as a unifying structure for many problems in discrete and computational geometry including robot motion planning, boundary evaluation, swept volume computation, offsets etc. At a broad level, the algorithms for arrangement computation are based on the following framework:
For example, in case of swept volume computation, S is obtained by enumerating ruled and developable surfaces of the primitives. The swept volume corresponds to the outer envelope, i.e., the boundary of the outermost cell. There is a considerable research in computational geometry on the combinatorial complexity of arrangement computation as well as surface intersections in geometric and solid modeling. However, the underlying combinatorial and computational complexity of computating the exact boundary of the arrangement is very high - it is super-quadratic in the number of primitives in S. In our applications, the number of primitives can be relatively large, typically, few thousands. Furthermore, the implementations of any algorithm for computing intersections and arrangements need to deal with accuracy and robustness issues. Given the complexity of arrangement computation, it is very difficult to robustly compute all the intersections between thousands of surface primitives within a reasonable time.
In this talk, we give an overview of our recent work using implicit modeling techniques to approximate the arrangement computation. The main idea is to compute the polyhedral approximation of primitives in S, generate their signed distance fields, and reconstruct the boundaries by performing isosurface extraction from the signed distance field. Our approach uses the following three steps:
Many issues arise when applying this approach to complex shapes and reliably generating the boundary of the final surface. The accuracy of the algorithm is mainly governed by the resolution of the underlying grid and the choice of the reconstruction algorithm. Insufficient grid resolution can create handles in the reconstructed surface or result in disconnected or missing surface components. Moreover, many geometric operations such as swept volume, offset and Booleans create new sharp features or edges on the boundary of the final surface. We present approximate solutions for these problems using feature-sensitive subdivision and reconstruction. We also present novel algorithms for max-norm computation, which are used for reliable voxelization. We have applied our algorithms to compute swept volume of complex polyhedral models, boundary evaluation of complex CAD models designed using Boolean operations, offsets and Minkowski sums. In practice, our algorithm works well on complex models.
This is joint work with Mark Foskey, Gokul Varadhan, Young Kim, Shankar Krishnan and Ming C. Lin
Relevant papers can be found at:
on swept volume computation
on computation of a simplified medial axis
on max norm computation and a general framework
Fast distance field computation
Title: Computational Line Geometry and Manufacturing
This lecture discusses classical line geometry in the modern computational framework with application in manufacturing. It is shown how problems in Numerical Controls machining as well as those involving non-conventional manufacturing operations can be formulated in terms of computational line geometry. Techniques from Lie Groups and the associated Lie Algebras and classical computational geometry are used to solve these problems.
Title: Why Cutting Path Planning is Different from Robotic Planning
Broadly speaking, there have been two approaches to NC path planning: feature recognition and generative planning. We have developed generative techniques for NC path planning which draw inspiration from robotic planning. Specifically, I will define a new, general class of problems called cutting-path problems which is different from robotic obstacle avoidance problem. Cutting paths relate to robots which have a boundary consisting of two types of regions: the cutting portion and the non-cutting portion. The scene is partitioned into three regions: free space, soft obstacles and hard obstacles. I will begin by defining, geometrically, what machining paths need to achieve under the constraint of being legal cutting paths. The strict definition leads a condition that is difficult to check, called cutting-reachability. However, under certain conditions, namely when the robot (the tool) and the scene (the part) satisfy certain shape conditions, machining can be assured if a simpler sufficient condition, called posture-reachability, is met. A necessary condition for posture reachability is visibility. I will present several results related to visibility and visibility cones. I will then describe discrete algorithms for generating visibility cones. Visibility analysis provides a rich basis for further algorithms in planning. I will show how visibility information can be manipulated, and describe algorithms we have developed in the past for automatic path planning using visibility.
Title: Geometric Algorithms for Layered Manufacturing: Part I
Layered Manufacturing (LM) is a relatively new technology that enables complex 3-dimensional parts to be built directly from their computer models, using a ``3-dimensional printer'' attached to a personal computer. In essence, the process involves orienting the model suitably, slicing it into parallel layers, and ``printing'' each layer on top of the previous one. LM is becoming increasingly important in computer-aided design and manufacturing because it provides the designer with an additional level of physical verification of the model, thereby allowing the detection and correction of flaws that may have otherwise gone unnoticed. LM is used extensively in the automotive, aerospace, and medical industries.
LM poses a number of interesting geometric problems whose efficient solution would enhance further the speed, accuracy, and utility of the process. These problems include choosing a suitable orientation of the model so as to optimize (various combinations of) certain design criteria (e.g., surface error, so-called support requirements, number of layers), efficient computation and location of support structures, generation of efficient tool-paths for printing the layers, and model decomposition to minimize support requirements. This talk, and the companion talk, will present an overview of the speakers' research on these problems over the past several years.
The material presented in these talks is the result of several joint research efforts by the speakers with various subsets of the following group of individuals: P. Gupta, M. Hon, I. Ilinkin, E. Johnson, J. Majhi, R. Sriram, and J. Schwerdt.
Papers and other information associated with these talks can be found here.
Title: Beyond Geometry: Issues in Product Modeling
The early part of this millennium has witnessed the emergence of an Internet-based engineering marketplace, where engineers, designers, and manufacturers from small and large companies are collaborating through the Internet to participate in various product development and marketing activities. This will be further enhanced by the next generation manufacturing environment, which will consist of a network of engineering applications, where state of the art multi-media tools and techniques will enhance closer collaboration between geographically distributed applications, virtual reality tools will allow visualization and simulation in a synthetic environment, and information exchange standards will facilitate seamless interoperation of heterogeneous applications. To support such an environment we need a product representation scheme that goes beyond the geometric-centric approach of traditional CAD systems. In this talk, I will describe two major efforts that I have been involved in over the last two decades in achieving such a goal.
The first effort was the MIT DICE project, which was one of the first efforts on developing a computer supported collaborative design environment. In this project, we developed a shared object product model which provided support for: multiple levels of functional abstractions; multiple levels of geometric abstractions; multiple functional views; and representation and management of multiple levels of constraints. This model used an integrated multi-level and multi-dimensional geometric representation scheme that is general enough to capture geometry through the entire design life cycle, i.e., from qualitative spatial relationships to detailed specifications of geometry at various levels of abstraction.
The second effort is the interoperability framework that is currently being developed at NIST. This framework focuses on the exchange of part and assembly information between heterogeneous modeling systems for collaborative design and manufacturing. The framework has the following key attributes: (1) it is based on formal semantics, and will eventually be supported by an appropriate ontology to permit automated reasoning; (2) it is generic: it deals with conceptual entities such as artifacts and features, and not specific artifacts such as motors, pumps or gears; (3) it is to serve as a repository of a rich variety of information about products, including aspects of product description that are not currently incorporated; (4) it is intended to foster the development of novel applications and processes that were not feasible in less information-rich environments; (5) it incorporates the explicit representation of design rationale, considered to be as important as that of the product description itself; and (6) there are provisions for converting and/or interfacing the generic representation schemes into a production-level interoperability framework.
About the Speaker
Ram D. Sriram is currently leading the Design and Process group in the Manufacturing Systems Integration Division at the National Institute of Standards and Technology, where he conducts research on standards for interoperability of computer-aided design systems. Prior to that he was on the engineering faculty (1986-1994) at the Massachusetts Institute of Technology (MIT) and was instrumental in setting up the Intelligent Engineering Systems Laboratory. At MIT, Sriram initiated the MIT-DICE project, which was one of the pioneering projects in collaborative engineering. His work on the MIT- DICE project was compiled into a book entitled "Distributed and Integrated Collaborative Engineering Design." Sriram has co-authored or authored more than 150 papers, books, and reports in computer-aided engineering, including thirteen books. Sriram was a founding co-editor of the International Journal for AI in Engineering. In 1989, he was awarded a Presidential Young Investigators Award from the National Science Foundation, U.S.A. Sriram has a B.S. from IIT, Madras, India, and an M.S. and a Ph.D. from Carnegie Mellon University, Pittsburgh, USA.
Title: Algebraic and Geometric Approximation of Waves as Voronoi Diagrams in Time Tony C. Woo University of Washington, Seattle
Joint work with: Chi Kit Au
Nanyang Technological University, Singapore
Complex flows among obstacles, such as the progression of the melt in plastic mold injection, are thought to require highly sophisticated machineries. Here, waves are modeled as the UNION and INTERSECTION of trimmed cones. A trimmed cone is the DIFFERENCE between the given boundary and a cone, the latter being the geometric model for the linearization of waves from either a real or secondary source, in space and in time. When multiple cones have identical time delays and velocities, their equilibria degenerate to the classical Voronoi diagram of nearest-neighbor partitioning.
This talk presents the algebraic landscape and the geometric structure for approximating wave diffraction and interference. The intellectual contribution of this work is on interface evolution. It addresses the question: How does a symmetric wave in the near field become asymmetric in a field far from the source? (From a geometric/mechanics view point, a paraphrase might be the following. It is intuitive that energy or curvature depletes in time and space: a closed curve becomes a circle and an open curve a straight line. Under what conditions would a curve gain energy?) A gratifying result comes from the classics. The linearization of the two sets of waves and their equilibria give rise to interesting structures attributable to Apollonius, Descartes and Pascal; the construction of the waves are due to Huygens and Kirchhoff. The practical contribution is on the technique. A commercial solid modeling system is used to compute the wave fronts.
Previous: Participation
Next: Registration
Workshop Index
DIMACS Homepage