Using genetic algorithms to optimise triangle strips

ABSTRACT

There is an ever increasing demand for higher levels of visual detail in graphical applications, particularly in computer games and applications employing visualisation. Triangle strips have been commonly used to optimise the rendering of large geometric meshes. This paper investigates the process of generating optimal triangle strips through the use of genetic algorithms (GA), to remove the need for special knowledge of the intended hardware platform. Two methods -- L-System encoding and parameter tuning of an established algorithm were implemented and tested. The results of this work show that over an extended period of time, solutions can be achieved that are comparable to existing triangle stripping techniques, but the best results were obtained from using the GA to tune the parameters of an existing triangle stripping algorithm.

REFERENCES

• 1: Arkin, E. M., Held, M., Mitchell, J. S. B. and Skiena, S. Hamiltonian triangulations for fast rendering. The Visual Computer, 12 (9). 429--444.
• 2: Alexander Bogomjakov , Craig Gotsman, Universal rendering sequences for transparent vertex caching of progressive meshes, No description on Graphics interface 2001, p.81-90, June 07-09, 2001, Ottawa, Ontario, Canada
• 3: Mike M. Chow, Optimized geometry compression for real-time rendering, Proceedings of the 8th conference on Visualization '97, p.347-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 4: Jihad El-Sana , Elvir Azanli , Amitabh Varshney, Skip strips: maintaining triangle strips for view-dependent rendering, Proceedings of the conference on Visualization '99: celebrating ten years, p.131-138, October 1999, San Francisco, California, United States
• 5: Regina Estkowski , Joseph S. B. Mitchell , Xinyu Xiang, Optimal decomposition of polygonal models into triangle strips, Proceedings of the eighteenth annual symposium on Computational geometry, p.254-263, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513431]
• 6: Francine Evans , Steven Skiena , Amitabh Varshney, Optimizing triangle strips for fast rendering, Proceedings of the 7th conference on Visualization '96, p.319-326, October 28-29, 1996, San Francisco, California, United States
• 7: GALib, http://lancet.mit.edu/ga/, 2005
• 8: John H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence, MIT Press, Cambridge, MA, 1992
• 9: Hugues Hoppe, Optimization of mesh locality for transparent vertex caching, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.269-276, July 1999 [doi>10.1145/311535.311565]
• 10: Hornby, G. S. and Pollack, J. B., The advantages of generative grammatical encodings for physical design. in Proceedings of the 2001 Congress on Evolutionary Computation CEC2001, (Samseong-dong, Gangnam-gu, Seoul, Korea, 2001), IEEE Press, 600--607.
• 11: Byrant A. Julstrom, Very greedy crossover in a genetic algorithm for the traveling salesman problem, Proceedings of the 1995 ACM symposium on Applied computing, p.324-328, February 26-28, 1995, Nashville, Tennessee, United States [doi>10.1145/315891.316009]
• 12: Kornmann, D. Fast and simple triangle strip generation., VMS Finland, Espoo, Finland, 1999.
• 13: Lander, J. Game programmer magazine. IEEE Transactions on Evolutionary Computation, 8. 23--28.
• 14: Marshall, C. Triangle strip creation, optimization, and rendering. in D. Treglia ed. Game Programming Gems 3, Charles River Media, 2002, 359--366.
• 15: NVIDIA, http://developer.nvidia.com/object/nvtristrip_library.html, 2004
• 16: Oliver Matias van Kaick, M. V. G. D. S. and Pedrini, H. Efficient generation of triangle strips from triangulated meshes. Journal of WSCG, 12. 1--3.
• 17: SUCGLaboratory, http://graphics.stanford.edu/data/3Dscanrep, 1994

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.8 Applications

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Viewing algorithms
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Keywords:
L-systems, genetic algorithms, triangle strip optimisation