Sketch-based path design

ABSTRACT

We present Drive, a system for the conceptual layout of 3D path networks. Our sketch-based interface allows users to efficiently author path layouts with minimal instruction. Our system incorporates some new and noteworthy components. We present the break-out lens, a novel widget for interactive graphics, inspired by break-out views used in engineering visualization. We also make three contributions specific to path curve design: First, we extend our previous work to fit aesthetic paths to sketch strokes with constraints, using piecewise clothoid curves. Second, we determine the height of paths above the terrain using a constraint optimization formulation of the occlusion relationships between sketched strokes. Finally, we illustrate examples of terrain sensitive path construction in the context of road design: automatically removing foliage, building bridges and tunnels across topographic features and constructing road signs appropriate to the sketched paths.

REFERENCES

• 1: Anand Agarawala , Ravin Balakrishnan, Keepin' it real: pushing the desktop metaphor with physics, piles and the pen, Proceedings of the SIGCHI conference on Human Factors in computing systems, April 22-27, 2006, Montréal, Québec, Canada [doi>10.1145/1124772.1124965]
• 2: Fabricio Anastacio , Mario Costa Sousa , Faramarz Samavati , Joaquim A. Jorge, Modeling plant structures using concept sketches, Proceedings of the 4th international symposium on Non-photorealistic animation and rendering, June 05-07, 2006, Annecy, France [doi>10.1145/1124728.1124746]
• 3: Thomas Baudel, A mark-based interaction paradigm for free-hand drawing, Proceedings of the 7th annual ACM symposium on User interface software and technology, p.185-192, November 02-04, 1994, Marina del Rey, California, United States [doi>10.1145/192426.192496]
• 4: Eric A. Bier , Maureen C. Stone , Ken Pier , Ken Fishkin , Thomas Baudel , Matt Conway , William Buxton , Tony DeRose, Toolglass and magic lenses: the see-through interface, Conference companion on Human factors in computing systems, p.445-446, April 24-28, 1994, Boston, Massachusetts, United States [doi>10.1145/259963.260447]
• 5: Nicholas Burtnyk , Azam Khan , George Fitzmaurice , Ravin Balakrishnan , Gordon Kurtenbach, StyleCam: interactive stylized 3D navigation using integrated spatial & temporal controls, Proceedings of the 15th annual ACM symposium on User interface software and technology, October 27-30, 2002, Paris, France [doi>10.1145/571985.572000]
• 6: M. Carpendale. Viewing transformations: Perspective, distortion and deformation. In SIGGRAPH03 Course Notes; Theory and Practice of Non-Photorealistic Graphics: Algorithms, Methods, and Production Systems Presentation. ACM, 2003.
• 7: Guoning Chen , Gregory Esch , Peter Wonka , Pascal Müller , Eugene Zhang, Interactive procedural street modeling, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 8: Jonathan M. Cohen , Lee Markosian , Robert C. Zeleznik , John F. Hughes , Ronen Barzel, An interface for sketching 3D curves, Proceedings of the 1999 symposium on Interactive 3D graphics, p.17-21, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300655]
• 9: Patrick Coleman , Karan Singh, Ryan: rendering your animation nonlinearly projected, Proceedings of the 3rd international symposium on Non-photorealistic animation and rendering, June 07-09, 2004, Annecy, France [doi>10.1145/987657.987678]
• 10: Frederic Cordier , Hyewon Seo, Free-Form Sketching of Self-Occluding Objects, IEEE Computer Graphics and Applications, v.27 n.1, p.50-59, January 2007 [doi>10.1109/MCG.2007.8]
• 11: Richard C. Davis , Brien Colwell , James A. Landay, K-sketch: a 'kinetic' sketch pad for novice animators, Proceeding of the twenty-sixth annual SIGCHI conference on Human factors in computing systems, April 05-10, 2008, Florence, Italy [doi>10.1145/1357054.1357122]
• 12: J. A. Dennison and C. D. Johnson. Technical Illustration: Techniques and Applications. Goodheart-Wilcox, 2003.
• 13: Gerald Farin , G. Rein , N. Sapidis , A. J. Worsey, Fairing cubic B-spline curves, Computer Aided Geometric Design, v.4 n.1-2, p.91-103, July 1987 [doi>10.1016/0167-8396(87)90027-6]
• 14: Tovi Grossman , Ravin Balakrishnan , Karan Singh, An interface for creating and manipulating curves using a high degree-of-freedom curve input device, Proceedings of the SIGCHI conference on Human factors in computing systems, April 05-10, 2003, Ft. Lauderdale, Florida, USA [doi>10.1145/642611.642645]
• 15: Li Guiqing , Li Xianmin , Li Hua, 3D Discrete Clothoid Splines, Proceedings of the International Conference on Computer Graphics, p.321, July 03-06, 2001
• 16: L. Halprin. Notebooks 1959--1971. The MIT Press, 1972.
• 17: Takeo Igarashi , Rieko Kadobayashi , Kenji Mase , Hidehiko Tanaka, Path drawing for 3D walkthrough, Proceedings of the 11th annual ACM symposium on User interface software and technology, p.173-174, November 01-04, 1998, San Francisco, California, United States [doi>10.1145/288392.288599]
• 18: Takeo Igarashi , Satoshi Matsuoka , Hidehiko Tanaka, Teddy: a sketching interface for 3D freeform design, ACM SIGGRAPH 2007 courses, August 05-09, 2007, San Diego, California [doi>10.1145/1281500.1281532]
• 19: Levent Burak Kara , Kenji Shimada , Sarah D. Marmalefsky, Calligraphic Interfaces: An evaluation of user experience with a sketch-based 3D modeling system, Computers and Graphics, v.31 n.4, p.580-597, August, 2007 [doi>10.1016/j.cag.2007.04.004]
• 20: O. Karpenko, J. F. Hughes, and R. Raskar. Epipolar methods for multi-view sketching. In Eurographics Workshop on Sketch-Based Interfaces and Modeling, pages 167--173, Aug. 2004.
• 21: Azam Khan , Ben Komalo , Jos Stam , George Fitzmaurice , Gordon Kurtenbach, HoverCam: interactive 3D navigation for proximal object inspection, Proceedings of the 2005 symposium on Interactive 3D graphics and games, April 03-06, 2005, Washington, District of Columbia [doi>10.1145/1053427.1053439]
• 22: Richard A. Kilgore, Silk, Java and object-oriented simulation, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
• 23: Benjamin B. Kimia , Ilana Frankel , Ana-Maria Popescu, Euler Spiral for Shape Completion, International Journal of Computer Vision, v.54 n.1-3, p.157-180, August-September 2003 [doi>10.1023/A:1023713602895]
• 24: M. Sheelagh T. Carpendale , David J. Cowperthwaite , F. David Fracchia, Multi-scale viewing, ACM SIGGRAPH 96 Visual Proceedings: The art and interdisciplinary programs of SIGGRAPH '96, p.149, August 04-09, 1996, New Orleans, Louisiana, United States [doi>10.1145/253607.253882]
• 25: J. McCrae and K. Singh. Sketching piecewise clothoid curves. In Sketch-Based Interfaces and Modeling 2008, pages 1--8. Eurographics Association, 2008.
• 26: D. Meek and D. Walton. Clothoid spline transition spirals. Mathematics of Computation, 59(199):117--133, July 1992.
• 27: Matthias Müller , Bruno Heidelberger , Matthias Teschner , Markus Gross, Meshless deformations based on shape matching, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 28: Glen Mullineux , Sebastian T. Robinson, Fairing point sets using curvature, Computer-Aided Design, v.39 n.1, p.27-34, January, 2007 [doi>10.1016/j.cad.2006.09.002]
• 29: Andrew Nealen , Takeo Igarashi , Olga Sorkine , Marc Alexa, FiberMesh: designing freeform surfaces with 3D curves, ACM SIGGRAPH 2007 papers, August 05-09, 2007, San Diego, California
• 30: Vaughan Pratt, Direct least-squares fitting of algebraic surfaces, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.145-152, August 1987
• 31: R. Schmidt , B. Wyvill , M. C. Sousa , J. A. Jorge, ShapeShop: sketch-based solid modeling with BlobTrees, ACM SIGGRAPH 2007 courses, August 05-09, 2007, San Diego, California [doi>10.1145/1281500.1281554]
• 32: R. Schneider and L. Kobbelt. Discrete fairing of curves and surfaces based on linear curvature distribution. In In Curve and Surface Design: Saint-Malo, pages 371--380. University Press, 1999.
• 33: Karan Singh , Eugene Fiume, Wires: a geometric deformation technique, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.405-414, July 1998 [doi>10.1145/280814.280946]
• 34: Desney S. Tan , George G. Robertson , Mary Czerwinski, Exploring 3D navigation: combining speed-coupled flying with orbiting, Proceedings of the SIGCHI conference on Human factors in computing systems, p.418-425, March 2001, Seattle, Washington, United States [doi>10.1145/365024.365307]
• 35: Matthew Thorne , David Burke , Michiel van de Panne, Motion doodles: an interface for sketching character motion, ACM SIGGRAPH 2007 courses, August 05-09, 2007, San Diego, California [doi>10.1145/1281500.1281535]
• 36: Steve Tsang , Ravin Balakrishnan , Karan Singh , Abhishek Ranjan, A suggestive interface for image guided 3D sketching, Proceedings of the SIGCHI conference on Human factors in computing systems, p.591-598, April 24-29, 2004, Vienna, Austria [doi>10.1145/985692.985767]
• 37: D. Walton and D. Meek. A controlled clothoid spline. Computers & Graphics 29, pages 353--363, 2005.
• 38: Colin Ware , Steven Osborne, Exploration and virtual camera control in virtual three dimensional environments, ACM SIGGRAPH Computer Graphics, v.24 n.2, p.175-183, Mar. 1990
• 39: Nayuko Watanabe , Motoi Washida , Takeo Igarashi, Bubble clusters: an interface for manipulating spatial aggregation of graphical objects, Proceedings of the 20th annual ACM symposium on User interface software and technology, October 07-10, 2007, Newport, Rhode Island, USA [doi>10.1145/1294211.1294241]
• 40: Robert C. Zeleznik , Kenneth P. Herndon , John F. Hughes, SKETCH: an interface for sketching 3D scenes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.163-170, August 1996 [doi>10.1145/237170.237238]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Line and curve generation

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Interaction techniques