Using Computer Design and Simulation to Improve Manufacturing Productivity

John E. Hopcroft1992 · DOI

TL;DR

This report details progress on developing robust geometric algorithms for computer-aided design and simulation, aiming to enhance manufacturing productivity. Key advancements include robust polyhedral intersection algorithms and guaranteed-quality mesh generation for complex shapes, addressing critical challenges in reliable geometric modeling.

What Problem Does This Paper Address?

The paper addresses the fundamental challenge of creating reliable and robust geometric algorithms for computer-aided design and manufacturing. Traditional geometric algorithms often fail due to floating-point precision issues and imprecise input, leading to errors in modeling and simulation. This lack of robustness hinders the development of advanced manufacturing processes, impacting national defense and economic competitiveness. The research focuses on developing algorithms that can handle real-world geometric data with greater certainty and fewer failures, particularly in areas like polyhedral intersection and mesh generation.

Methods

The research explores two main areas:

  • Robust Polyhedral Intersection: This work focuses on developing algorithms that can reliably determine the intersection of two polyhedra. A key technique involves using "approximate polygons" to handle uncertainty in geometric data. The research also investigates the concept of "local correctness," where an algorithm is guaranteed to succeed for specific, localized geometric configurations (e.g., edge-face intersections), as a practical alternative to proving full formal correctness.
  • Guaranteed-Quality Mesh Generation: The project aims to create mesh generators that produce high-quality, simply-shaped elements (triangles for 2D, tetrahedra for 3D) for numerical simulations (e.g., solving PDEs). The core innovation is a mesh generator that mathematically guarantees element shape (angles between 30-120 degrees) and respects boundaries, without relying on iterative smoothing processes that can introduce errors. This approach allows for controlled element density, optimizing accuracy and computational cost.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The Practicality of Local Correctness: Proving absolute formal correctness for complex geometric operations like polyhedral intersection is extremely difficult. The research suggests that achieving "local correctness" is a more pragmatic and achievable goal, providing a strong foundation for robust algorithms.
  • Implicit Patches for Surface Representation: The paper highlights the advantages of implicit patches over traditional parametric patches for free-form surface modeling. Implicit patches are closed under common geometric operations and allow for efficient intersection computations, overcoming limitations of parametric representations.
  • Guaranteed Quality Over Iterative Refinement: For mesh generation, the research demonstrates that it's possible to achieve guaranteed element quality directly, rather than relying on post-processing smoothing steps. This leads to more predictable and reliable meshing for simulations.
  • Shape Control for Implicit Surfaces: The work on implicit patches shows that shape properties, like convexity, can be effectively controlled by manipulating control points, similar to how parametric patches are handled.

Key Results

  • Robust Polyhedral Intersection: Preliminary versions of the developed algorithm have shown significantly improved robustness compared to earlier designs, particularly for intersections involving corners and edges.
  • Guaranteed-Quality Mesh Generation: A 2D mesh generator has been implemented and proven to guarantee element shapes (triangles with angles between 30-120 degrees) and boundary adherence. A version for simple curved surfaces has also been implemented, with ongoing work for more complex surfaces and 3D problems. The generator is noted to be fast, avoiding iterative smoothing.

Limitations and Future Work

  • Formal Correctness in Polyhedral Intersection: While local correctness is a significant step, the paper acknowledges that achieving complete formal correctness for polyhedral intersection remains a challenge.
  • 3D Mesh Generation: For full 3D problems, current techniques cannot yet guarantee the shape of the resulting tetrahedra, indicating a need for further research in this area.
  • Extending Surface Meshing: The mesh generator for curved surfaces is currently being extended to handle surfaces defined by multiple parametric patches, suggesting future work on more complex surface geometries.
  • Broader Applications: The research aims to extend these robust geometric algorithms to a wider range of applications within manufacturing and simulation.

Summary updated

Abstract

The members of the Modeling and Simulation Group at Cornell believe that improvements in computer capabilities and in software design tools have the potential to radically alter the manufacturing process. These improvements present unique opportunities for improving manufacturing productivity, an area of strategic importance to our nation's defense and economic future. Potential payoffs to industry and to the military include extended capabilities, increased reliability of components, and reduced production costs. Our goal is to develop and extend the science base in representing, manipulating, and reasoning about physical objects and processes. To this end, we are carrying out a broadbased research program to develop the underlying methodology that supports representation, editing, and simulation of objects, tasks, and systems. The remainder of this report summarizes some of our work in one of the areas that we stressed in our original proposal: robust and reliable geometric algorithms.
BibTeX
@misc{hopcroft1992using,
  author = {John E. Hopcroft},
  title = {{Using Computer Design and Simulation to Improve Manufacturing Productivity}},
  year = {1992},
  doi = {10.21236/ada251862},
}
Figure