Appearance-preserving manipulation of hand-drawn graphs

ABSTRACT

We describe a sketching system that allows users to create and manipulate directed graphs, such as those depicting state diagrams, using pen-input alone. The system exactly preserves the user's strokes, which may be entered in any order, and depicts them with a chalk texture to evoke a blackboard metaphor. The system automatically interprets the geometry of the sketch, distinguishing vertices, edges, and arrow heads, then tacitly imparts the intended graph semantics based on the two-dimensional placement of these elements. Once drawn, the user can manipulate the directed graph gesturally using the pen. The system responds to vertices or edges being picked and dragged by adjusting all adjacent edges appropriately. The original appearance of the hand-drawn vertices and edges is maintained even while their shapes are continually morphed in response to rearrangement of these elements. All edges exhibit shape memory, which is the proclivity to return to their original hand-drawn shape despite repeated stretching and compression.

REFERENCES

• 1: James Arvo , Kevin Novins, Fluid sketches: continuous recognition and morphing of simple hand-drawn shapes, Proceedings of the 13th annual ACM symposium on User interface software and technology, p.73-80, November 06-08, 2000, San Diego, California, United States [doi>10.1145/354401.354413]
• 2: Arvo, J., and Novins, K. 2000. Smart text: A synthesis of recognition and morphing. In AAAI Spring Symposium on Smart Graphics, 140--147.
• 3: Arvo, J., and Novins, K. 2006. Fluid sketching of directed graphs. In Proceedings of the Seventh Australasian User Interface Conference (AUIC2006). To Appear.
• 4: James Arvo, Computer aided serendipity: the role of autonomous assistants in problem solving, Proceedings of the 1999 conference on Graphics interface '99, p.183-192, September 1999, Kingston, Ontario, Canada
• 5: Dorothea Blostein, General Diagram-Recognition Methodologies, Selected Papers from the First International Workshop on Graphics Recognition, Methods and Applications, p.106-122, August 10-11, 1995
• 6: Giuseppe Di Battista , Peter Eades , Roberto Tamassia , Ioannis G. Tollis, Algorithms for drawing graphs: an annotated bibliography, Computational Geometry: Theory and Applications, v.4 n.5, p.235-282, Oct. 1994 [doi>10.1016/0925-7721(94)00014-X ]
• 7: Takeo Igarashi , Satoshi Matsuoka , Hidehiko Tanaka, Teddy: a sketching interface for 3D freeform design, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.409-416, July 1999 [doi>10.1145/311535.311602]
• 8: Takeo Igarashi , Tomer Moscovich , John F. Hughes, As-rigid-as-possible shape manipulation, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 9: L. Julia , C. Faure, Pattern recognition and beautification for a pen based interface, Proceedings of the Third International Conference on Document Analysis and Recognition (Volume 1), p.58, August 14-15, 1995
• 10: James A. Landay , Brad A. Myers, Interactive sketching for the early stages of user interface design, Proceedings of the SIGCHI conference on Human factors in computing systems, p.43-50, May 07-11, 1995, Denver, Colorado, United States [doi>10.1145/223904.223910]
• 11: Joseph J. LaViola, Jr. , Robert C. Zeleznik, MathPad²: a system for the creation and exploration of mathematical sketches, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 12: Harry R. Lewis , Christos H. Papadimitriou , Christos Papadimitriou, Elements of the Theory of Computation, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 13: J. D. Northrup , Lee Markosian, Artistic silhouettes: a hybrid approach, Proceedings of the 1st international symposium on Non-photorealistic animation and rendering, p.31-37, June 05-07, 2000, Annecy, France [doi>10.1145/340916.340920]
• 14: Beryl Plimmer , Mark Apperley, INTERACTING with sketched interface designs: an evaluation study, CHI '04 extended abstracts on Human factors in computing systems, April 24-29, 2004, Vienna, Austria [doi>10.1145/985921.986058]
• 15: Dean Rubine, Specifying gestures by example, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.329-337, July 1991
• 16: Steve Smithies , Kevin Novins , James Arvo, A handwriting-based equation editor, Proceedings of the 1999 conference on Graphics interface '99, p.84-91, September 1999, Kingston, Ontario, Canada
• 17: Thomas F. Stahovich, Sketchit: a sketch interpretation tool for conceptual mechanical design, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 18: Stahovich, T. F. 1998. The engineering sketch. IEEE Intelligent Systems 13, 3, 17--19.
• 19: Osama Tolba , Julie Dorsey , Leonard McMillan, Sketching with projective 2D strokes, Proceedings of the 12th annual ACM symposium on User interface software and technology, p.149-157, November 07-10, 1999, Asheville, North Carolina, United States [doi>10.1145/320719.322596]
• 20: Richard Zanibbi , Kevin Novins , James Arvo , Katherine Zanibbi, Aiding manipulation of handwritten mathematical expressions through style-preserving morphs, No description on Graphics interface 2001, p.127-134, June 07-09, 2001, Ottawa, Ontario, Canada
• 21: 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:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques

Keywords:
appearance preservation, interactive graph drawing, modeless interaction