To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.
You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.
Computer-Aided Design and Manufacturing (CAD/CAM) is concerned with all aspects of the process of designing, prototyping, manufacturing, inspecting, and maintaining complex geometric objects under computer control. As such, there is a natural synergy between this field and Computational Geometry (CG), which involves the design, analysis, implementation, and testing of efficient algorithms and data representation techniques for geometric entities such as points, polygons, polyhedra, curves, and surfaces. On the one hand, CG can bring about significant performance improvements in CAD/CAM, while, on the other hand, CAD/CAM can be a rich source of interesting problems that can spur new research in CG. Indeed, such two-way interaction has already been witnessed in recent years in areas such as numerically-controlled machining, casting and injection molding, rapid prototyping and layered manufacturing, metrology, and mechanism/linkage design, to name just a few.
To further promote the interaction between the two fields, we organized a Workshop on "Computer-Aided Design and Manufacturing" at the DIMACS Center in Piscataway, NJ, from Oct. 7-9, 2003. The Workshop, which was attended by about fifty-five individuals from academia, research laboratories, and industry, was organized around a series of invited talks, contributed presentations, and informal discussions geared towards fostering collaborative research. Details about the Workshop can be found at http://dimacs.rutgers.edu/Workshops/CompAided/.
Subsequently, authors of papers presented at the Workshop were invited to submit expanded and polished versions of their research to this Volume. The intent was to provide, in one place, a set of self-contained papers that could serve as the starting point for further research. All submissions were refereed. The papers in this Volume are an outgrowth of this process and cover topics such as geometric modeling, computational topology, computational metrology, geometric constraint solving, part immobilization, geometric aspects of machining, layered manufacturing, and algebraic methods.
We thank Fred Roberts (DIMACS Director) and Steve Fortune (Member, DIMACS Executive Council) for their support and encouragement, DIMACS and AMS staff members for organizational help, the referees for their help with the reviews, and, of course, the authors for their research contributions. We are grateful to the National Science Foundation for financial support for the Workshop.
Ravi Janardan (Minneapolis, MN)
Michiel Smid (Ottawa, Canada)
Debasish Dutta (Ann Arbor, MI)
Contents Forward vii Preface ix A Survey of Subdivision-Based Tools for Surface Modeling I. Boier-Martin, D. Zorin, and F. Bernardini 1 Sample Based Geometric Modeling T. Dey 29 Computational Topology and Swept Volumes D. Blackmore, Y. Mileyko, M. Leu, W. Regli, and W. Sun 53 Elements of Computational Metrology V. Srinivasan 79 Combinatorial Approaches to Geometric Constraint Solving: Problems, Progress, and Directions M. Sitharam 117 Immobilization: Analysis, Existence, and Output- Sensitive Synthesis F. van der Stappen 165 Geometric Algorithms for Layered Manufacturing R. Janardan and M. Smid 189 Towards a Process Planning Framework for Multi- Direction Layered Deposition P. Singh and D. Dutta 221 Machinability: Geometric Reasoning for Cutting T. Kim and S. Sarma 245 Zig-Zag Tool Path Generation for Sculptured Surface Finishing D. Misra, V. Sundararajan and P. Wright 265 Implicitization Exploiting Sparseness I. Emiris and I. Kotsireas 281 The Exact Rational Univariate Representation for Detecting Degeneracies J. Keyser, K. Ouchi and J.M. Rojas 299 Mass Properties of the Union of Millions of Identical Cubes W.R. Franklin 329