Performing geometric transformations by program transformation

ABSTRACT

Problems in geometry often possess symmetry properties that may be exploited in order to develop solutions. Algorithms based on these symmetry properties will frequently use geometric transformations to transform one case into another (symmetric) case. One advantage of this approach is that the algorithm avoids enumeration of cases and thus is shorter and generally easier to read. One disadvantage is that some additional execution time is required to perform these transformations. We describe how simple program equivalences may be used as program transformations to eliminate this additional execution time from programs that use geometric transformations. This approach has been used to develop an efficient implementation of a new algorithm for the two-dimensional line-clipping problem.

REFERENCES

• 1: Proceedings of an International Workshop on Advanced Programming Environments, June 1986
• 2: James D. Foley , Andries Van Dam, Fundamentals of interactive computer graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 3: C. A. R. Hoare , I. J. Hayes , He Jifeng , C. C. Morgan , A. W. Roscoe , J. W. Sanders , I. H. Sorensen , J. M. Spivey , B. A. Sufrin, Laws of programming, Communications of the ACM, v.30 n.8, p.672-686, Aug. 1987 [doi>10.1145/27651.27653]
• 4: NICHOLL, R. A., AND NICHOLL, T.M. Laws about programs with inverses. Rep. 178, Dept. of Computer Science, Univ. of Western Ontario, London, 1987.
• 5: Tina M. Nicholl , D. T. Lee , Robin A. Nicholl, An efficient new algorithm for 2-D line clipping: Its development and analysis, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.253-262, July 1987
• 6: H. Partsch , R. Steinbrüggen, Program Transformation Systems, ACM Computing Surveys (CSUR), v.15 n.3, p.199-236, Sept. 1983 [doi>10.1145/356914.356917]
• 7: R. F. Sproull, Using program transformations to derive line-drawing algorithms, ACM Transactions on Graphics (TOG), v.1 n.4, p.259-273, Oct. 1982 [doi>10.1145/357311.357312]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms