(1/20/11, sections 1 through 2.7, finish for 1/27/11) Representations for Rigid Solids: Theory, Methods, and Systems (Aristides G. Requicha), ACM Computing Surveys, December 1980. (2/1/11) "The Radial Edge Structure: A Topological Representation for Non-Manifold Geometric Boundary Modeling" (Kevin Weiler), in Geometric Modeling for CAD Applications, c. 1988. Distributed in lecture. (2/8/11)Consistent solid and boundary representations from arbitrary polygonal data (T. M. Murali, Thomas A. Funkhouser), 1997 Symposium on Interactive 3D Graphics, or try this gzipped postscript link from Funkhouser's web site that includes the color plate that didn't make it into the ACM digital library. (Layered Manufacturing slides from lecture introducing the paper) (th 2/17) The power crust (Nina Amenta, Sunghee Choi, Ravi Krishna Kolluri), Sixth ACM Symposium on Solid Modeling and Applications, 2001. (no write-up) Computational Geometry: Algorithms and Applications, Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars, Chapter 7 "Voronoi Diagrams." http://www.springerlink.com/content/k18243/#section=149426&page=1 (You might also enjoy this animation of Fortune's algorithm.) quiz 2 on material below this line
(tu 3/1) Interactive Boolean operations for conceptual design of 3-D solids (Ari Rappoport, Steven Spitz), SIGGRAPH '97 Proceedings of the 24th annual conference on Computer graphics and interactive techniques. (tu 3/15)C-space approach to tool-path generation for die and mould machining by Byoung K Choi, Dae H Kim, and Robert B Jerard, in Computer Aided Design, Vol 29, Issue 9, Sept 1997, pp. 657-669. Color scans of figures 10-14 available here. (Typos I've found: p.660, 2nd column, 1 /3 down, C-space Elements = {...}, the VP should be VF; P. 666 in TPG-algorithm (3.6), omega (w if your browser supports Greek characters) should be lambda (l if your browser supports Greek characters). Warning: CAD is British and its papers are type-set for A4 size paper, so make sure when you print that you have Acrobat set to "shrink pages to paper size" in the print options or the bottom line of text will get cut off.) (tu 3/29) Separating an object from its cast (Hee-Kap Ahn, Mark de Berg, Prosenjit Bose, Siu-Wing Cheng, Dan Halperin, Jirí Matousek, Otfried Schwarzkopf), Symposium on Computational Geometry, 1997. Or see journal version, which fixes a mistake in figure 5 (figure 4 in journal version) but uses a hard-to-interpret font for the math: Separating an object from its cast Computer-Aided Design, July 2002, pp. 547-559. (tu 4/5) Visibility maps and spherical algorithms (Tony C. Woo), Computer-Aided Design, Volume 26, Issue 1, January 1994, Pages 6-16. (th 4/7) Spatial Planning: A Configuration Space Approach (T. Lozano-Perez), IEEE Transactions on Computers, February 1983 (Vol. 32 No. 2) pp. 108-120 (you can skip appendices, though). (optional related text book chapter) Computational Geometry: Algorithms and Applications, Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars, Chapter 13 "Robot Motion Planning." (tu 4/19) Efficient simplex computation for fixture layout design (Yu Zheng, Ming C. Lin, Dinesh Manocha), Proceedings of the 14th ACM Symposium on Solid and Physical Modeling pp. 71-80.