Sticky splines: definition and manipulation of spline structures with maintained topological relations

ABSTRACT

This paper describes an augmentation to the spline concept to account for topological relations between different spline curves. These topological relations include incidence relations, constraining the extremes of spline curves to other spline curves, and also more general geometric relations, for example, involving the tangents of spline curves in their extremes. To maintain these incidence relations, some spline curves may have to be transformed (translated, rotated, scaled), or even deformed (i.e., the shape of the curve may change) as a result of modifying other spline curves. A data structure and algorithms are given to implement the propagation of these transformations and deformations.Based on the augmented spline concept, to be called sticky splines, both a script system to represent spline structures and an interactive system for editing drawings while automatically, maintaining their topological structure are presented.

REFERENCES

• 1: ANSI. 1988. American National Standard'for Information Processing Systems--Programmer's Hierarchical Interactive Graphics System (PHIGS) Functional Description, Archive File Format, Clear-Text Encoding of Archive File. Ref. ANSI X3.144-1988. American National Standards Institute, New York.
• 2: John W. Blake, PHIGS and PHIGS+: an introduction to 3D computer graphics, Academic Press Professional, Inc., San Diego, CA, 1993
• 3: Wolfgang Böhm , Gerald Farin , Jürgen Kahmann, A survey of curve and surface methods in CAGD, Computer Aided Geometric Design, v.1 n.1, p.1-60, July 1984 [doi>10.1016/0167-8396(84)90003-7]
• 4: Alan Borning , Robert Duisberg, Constraint-based tools for building user interfaces, ACM Transactions on Graphics (TOG), v.5 n.4, p.345-374, Oct. 1986 [doi>10.1145/27623.29354]
• 5: Ronen Barzel , Alan H. Barr, A modeling system based on dynamic constraints, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.179-188, June 1988
• 6: CATMULL, E., AND CLARK, J. 1978. Recursively generated B-spline surfaces on arbitrary topological meshes. Comput. Aided Des. 10, 6 (Nov.), 350-355.
• 7: DE BOER, M. 1989. Analysis and computer generation of division patterns in cell layers using developmental algorithms. Ph.D. thesis, Rijks Univ., Utrecht, The Netherlands.
• 8: Doo, D. 1978. A subdivision algorithm for smoothing down irregular shaped polyhedrons. In Proceedings of the Conference on Interactive Techniques in CAD (Bologna, Italy, Sept. 21-23). IEEE, New York, 356-360.
• 9: David R. Forsey , Richard H. Bartels, Hierarchical B-spline refinement, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.205-212, June 1988
• 10: FULLER, N., ~'~o PRUSINIimWlCZ, P. 1989. Application of Euclidean constructions to computer graphics. Visual Comput. 5, 1/2 (March), 53-67.
• 11: William M. Hsu , John F. Hughes , Henry Kaufman, Direct manipulation of free-form deformations, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.177-184, July 1992
• 12: Charles Loop, Smooth spline surfaces over irregular meshes, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.303-310, July 1994 [doi>10.1145/192161.192238]
• 13: Greg Nelson, Juno, a constraint-based graphics system, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.235-243, Jul. 1985
• 14: Theo Pavlidis , Christopher J. Van Wyk, An automatic beautifier for drawings and illustrations, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.225-234, Jul. 1985
• 15: John C. Platt , Alan H. Barr, Constraints methods for flexible models, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.279-288, June 1988
• 16: Przemyslaw Prusinkiewicz , Aristid Lindenmayer , James Hanan, Development models of herbaceous plants for computer imagery purposes, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.141-150, June 1988
• 17: RImEL, A. J., ~ro KAY, R. E. 1977. Kinsyn iii: A new human-engineered system for interactive computer aided design of planar linkages. J. Eng. Industry: Trans. ASME 99, 2 (May), 440-448.
• 18: Thomas W. Sederberg , Scott R. Parry, Free-form deformation of solid geometric models, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.151-160, Aug. 1986
• 19: SUTHERLAND, I. E. 1980. Sketchpad: A man-machine graphical communication system. In Tutorial and Selected Readings in Interactive Computer Graphics, H. Freeman, Ed., IEEE, New York, 2-19. (Reprinted from Proceedings, Spring Joint Computer Conference, 1963.)
• 20: Andrew Witkin , Kurt Fleischer , Alan Barr, Energy constraints on parameterized models, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.225-232, July 1987
• 21: Andrew Witkin , Michael Gleicher , William Welch, Interactive dynamics, ACM SIGGRAPH Computer Graphics, v.24 n.2, p.11-21, Mar. 1990
• 22: WOLBEP~, G. 1990. Digital Image Warping. IEEE, Washington, D.C.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Splines

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Algorithms, Design, Experimentation, Theory

Keywords:
affine and nonaffine mappings, branching structures, drawing system, free-form deformation, geometric properties, splines, topological constraints