Real-time generation of populated virtual cities

ABSTRACT

This paper presents a new approach for real-time generation of 3D virtual cities. The main goal is to provide of a generic framework which support semi-automatic creation, manage-ment, and visualization of urban complex environments for virtual human simulation, called virtual urban life (VUL). It intends to minimize efforts of designers in the modeling of complex and huge environments. A versatile multi-level data model has been developed to support data management and visualization in an efficient way. Moreover, a polygon partitioning algorithm addresses the city allotment problem in an automatic way, according to input parameters and constraints. In addition, we discuss some results of virtual populated city simulations developed with proposed frame-work.

REFERENCES

• 1: } C. Alexander, S. Ishikawa, and M. Silverstein. A Pattern Language: Towns, Buildings Construction. Oxford University Press, 1977.
• 2: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 3: M. Dikaiakou, A. Efthymiou, and Y. Chrysanthou. Modelling the walled city of Nicosia. In D. Arnold, A. Chalmers, and F. Niccolucci, editors, VAST 2003, pages 57--65, Brighton, United Kingdom, 5-7, Nov. 2003. Eurographics Workshop Proceedings.
• 4: Simon Dobbyn , John Hamill , Keith O'Conor , Carol O'Sullivan, Geopostors: a real-time geometry / impostor crowd rendering system, Proceedings of the 2005 symposium on Interactive 3D graphics and games, April 03-06, 2005, Washington, District of Columbia [doi>10.1145/1053427.1053443]
• 5: Stephane Donikian, VUEMS: A Virtual Urban Environment Modeling System, Proceedings of the 1997 Conference on Computer Graphics International, p.84, June 23-27, 1997
• 6: N. Farenc, R. Boulic, and D. Thalmann. An informed environment dedicated to the simulation of virtual humans in urban context. In P. Brunet and R. Scopigno, editors, Eurographics'99, volume 18, pages 309--318, Milano, Italy, 1999.
• 7: Usama M. Fayyad , Gregory Piatetsky-Shapiro , Padhraic Smyth , Ramasamy Uthurusamy, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 8: W. Forstner. 3d-city models: Automatic and semiautomatic acquisition methods. In D. Fritsch and R. Spiller, editors, Photogrametric Week' 99, pages 291--303, 1999.
• 9: D. H. Greene. Computational Geometry, volume 1, chapter The decomposition of polygons into convex parts, pages 235--259. Computational Geometry, Greenwich, Conn., 1998 3.
• 10: Stefan Hertel , Kurt Mehlhorn, Fast Triangulation of Simple Polygons, Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, p.207-218, August 21-27, 1983
• 11: B. Hillier. Space is the Machine: A Configurational Theory of Architecture. Cambridge University Press, 1996.
• 12: F. Lamarche and S. Donikian. Crowds of virtual humans : a new approach for real time navigation in complex and structured environments. In M.-P. Cani and M. Slater, editors, Eurographics'04, volume 23, pages 509--518, Grenoble, France, 2004.
• 13: Yoav I. H. Parish , Pascal Müller, Procedural modeling of cities, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.301-308, August 2001 [doi>10.1145/383259.383292]
• 14: Wolfgang Pree, Design patterns for object-oriented software development, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995
• 15: C. W. Reynolds. Steering behaviors for autonomous characters. In Game Developers Conference, pages 763--782, San Jose, California - USA, 1999.
• 16: Stephen M. Smith , J. Michael Brady, SUSAN—A New Approach to Low Level Image Processing, International Journal of Computer Vision, v.23 n.1, p.45-78, May 1997 [doi>10.1023/A:1007963824710]
• 17: Y. Takase, N. Sho, A. Sone, and K. Shimiya. Automatic generation of 3d city models and and related applications. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XXXiV(5), 2003.
• 18: Franco Tecchia , Yiorgos Chrysanthou, Real-Time Rendering of Densely Populated Urban Environments, Proceedings of the Eurographics Workshop on Rendering Techniques 2000, p.83-88, June 26-28, 2000
• 19: G. Thomas and S. Donikian. Modeling virtual cities dedicated to behavioural animation. In M. Gross and F. Hopgood, editors, Eurographics'00, volume 19, pages C71--C79, Interlaken - Switzerland, 2000.
• 20: T. Ulrich. Chunked lod: Rendering massive terrains using chunked level of detail control. http://www.vterrain.org/LOD/Papers/index.html, Nov. 2005. (last access).
• 21: K. Weiler. Edge-based data structures for solid modeling in curved-surface environments. IEEE Computer Graphics and Applications, 5(1):21--40, Jan. 1985.
• 22: Peter Wonka , Michael Wimmer , François Sillion , William Ribarsky, Instant architecture, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 23: C. Yap, H. Biermann, A. Hertzman, C. Li, J. Meyer, H. Pao, and T. Paxia. A different manhattan project: Automatic statistical model generation. In IS&TSPIE Symposium on Electronic Imaging, San Jose, CA -USA, Jan. 2002.
• 24: Christopher Zach , Andreas Klaus , Joachim Bauer , Konrad Karner , Markus Grabner, Modeling and visualizing the cultural heritage data set of Graz, Proceedings of the 2001 conference on Virtual reality, archeology, and cultural heritage, November 28-30, 2001, Glyfada, Greece [doi>10.1145/584993.585028]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems; Object hierarchies

General Terms:
Algorithms, Design, Experimentation

Keywords:
city modeling, crowd simulation, polygon partitioning and real-time visualization, terrain modeling, virtual life simulation