Constraint-based model synthesis

ABSTRACT

We present a method for procedurally modeling general complex 3D shapes. Our approach is targeted towards applications in digital entertainment and gaming and can automatically generate complex models of buildings, man-made structures, or urban datasets in a few minutes based on user-defined inputs. The algorithm attempts to generate results that resemble a user-defined input model and that satisfy various dimensional, geometric, and algebraic constraints. These constraints are used to capture the intent of the user and generate shapes that look more natural. We also describe efficient techniques to handle complex shapes and demonstrate their performance on many different types of models.

REFERENCES

• 1: Aliaga, D. G., Vanegas, C. A., and Beneš, B. 2008. Interactive example-based urban layout synthesis. ACM Trans. Graph. 27, 5, 1--10.
• 2: Ault, H. 1999. Using geometric constraints to capture design intent. Journal for Geometry and Graphics 3, 1, 39--47.
• 3: Bouma, W., Fudos, I., Hoffmann, C., Cai, J., and Paige, R. 1995. A geometric constraint solver. Computer-Aided Design 27, 6, 487--501.
• 4: Cabral, M., Lefebvre, S., Dachsbacher, C., and Drettakis, G. 2009. Structure preserving reshape for textured architectural scenes. Computer Graphics Forum (Proceedings of the Eurographics conference).
• 5: Cutler, B., Dorsey, J., McMillan, L., Müller, M., and Jagnow, R. 2002. A procedural approach to authoring solid models. ACM Trans. Graph. 21, 3, 302--311.
• 6: Ebert, D. S., Musgrave, F. K., Peachey, D., Perlin, K., and Worley, S. 2002. Texturing and Modeling. 3rd ed. Academic Press.
• 7: Efros, A. A., and Leung, T. K. 1999. Texture synthesis by non-parametric sampling. In IEEE International Conference on Computer Vision, 1033--1038.
• 8: Han, C., Risser, E., Ramamoorthi, R., and Grinspun, E. 2008. Multiscale texture synthesis. Proceedings of ACM SIGGRAPH '08 27, 3, 51.
• 9: Hoffmann, C. M., and Rossignac, J. R. 1996. A road map to solid modeling. IEEE Transactions on Visualization and Computer Graphics 2, 1, 3--10.
• 10: Hoffmann, C. M., Lomonosov, A., and Sitharam, M. 1998. Geometric constraint decomposition. In Geometric Constraint Solving, B. Bruderlin and D. Roller, Eds. Springer-Verlag, 170--195.
• 11: Igarashi, T., Matsuoka, S., and Tanaka, H. 1999. Teddy: a sketching interface for 3d freeform design. In Proc. of ACM SIGGRAPH '99, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 409--416.
• 12: Kopf, J., Fu, C.-W., Cohen-Or, D., Deussen, O., Lischinski, D., and Wong, T.-T. 2007. Solid texture synthesis from 2d exemplars. ACM Trans. Graph. 26, 3, 2.
• 13: Kramer, G. A., and Qh, B. B. 1992. Solving geometric constraint systems. MIT Press, 708--714.
• 14: Kwatra, V., Schdl, A., Essa, I., Turk, G., and Bobick, A. 2003. Graphcut textures: Image and video synthesis using graph cuts. Proc. Of ACM SIGGRAPH '03, 277--286.
• 15: Legakis, J., Dorsey, J., and Gortler, S. 2001. Feature-based cellular texturing for architectural models. In Proc. Of ACM SIGGRAPH '01, 309--316.
• 16: Merrell, P., and Manocha, D. 2008. Continuous model synthesis. Proc. of ACM SIGGRAPH ASIA '08.
• 17: Merrell, P. 2007. Example-based model synthesis. In I3D '07: Symposium on Interactive 3D graphics and games, ACM Press, 105--112.
• 18: Mitra, N. J., Guibas, L., and Pauly, M. 2006. Partial and approximate symmetry detection for 3d geometry. In ACM Transactions on Graphics, vol. 25, 560--568.
• 19: Měch, R., and Prusinkiewicz, P. 1996. Visual models of plants interacting with their environment. In Proc. Of ACM SIGGRAPH '96, 397--410.
• 20: Müller, P., Wonka, P., Haegler, S., Ulmer, A., and Gool, L. V. 2006. Procedural modeling of buildings. ACM Trans. Graph. 25, 3, 614--623.
• 21: Müller, P., Zeng, G., Wonka, P., and Gool, L. V. 2007. Image-based procedural modeling of facades. ACM Trans. Graph. 26, 3, 85.
• 22: Musgrave, F. K., Kolb, C. E., and Mace, R. S. 1989. The synthesis and rendering of eroded fractal terrains. In Proc. Of ACM SIGGRAPH '89, 41--50.
• 23: Nealen, A., Igarashi, T., Sorkine, O., and Alexa, M. 2007. Fibermesh: designing freeform surfaces with 3d curves. Proc. of ACM SIGGRAPH '07 26, 3, 41.
• 24: Pottmann, H., Liu, Y., Wallner, J., Bobenko, A., and Wang, W. 2007. Geometry of multi-layer freeform structures for architecture. Proc. Of ACM SIGGRAPH '07.
• 25: Prusinkiewicz, P., Mündermann, L., Karwowski, R., and Lane, B. 2001. The use of positional information in the modeling of plants. In Proc. Of ACM SIGGRAPH '01, 289--300.
• 26: Smith, J., Hodgins, J., Oppenheim, I., and Witkin, A. 2002. Creating models of truss structures with optimization. ACM Trans. Graph. 21, 3, 295--301.
• 27: Watson, B., Müller, P., Veryovka, O., Fuller, A., Wonka, P., and Sexton, C. 2008. Procedural urban modeling in practice. IEEE Computer Graphics and Applications 28, 3, 18--26.
• 28: Wei, L.-Y., and Levoy, M. 2000. Fast texture synthesis using tree-structured vector quantization. In Proc. Of ACM SIGGRAPH '00, 479--488.
• 29: Wonka, P., Wimmer, M., Sillion, F., and Ribarsky, W. 2003. Instant architecture. In Proc. Of ACM SIGGRAPH '03, 669--677.

INDEX TERMS

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

Keywords:
model synthesis, procedural modeling