nach oben

Computing

Erschienen in:

01.02.2015

Interactive synthesis of self-organizing tree models on the GPU

verfasst von: Štefan Kohek, Damjan Strnad

Erschienen in: Computing | Ausgabe 2/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Real-time synthesis of realistic tree models is a desirable functionality for computer games, simulators, and landscape design software. Self-organizing tree models that adapt to the environment are a welcome addition and central to various 3D design tools but present a challenging task for interactive use even on modern commodity hardware. The paper describes the implementation of a complete self-organizing tree synthesis method running on a contemporary graphics processing unit using OpenCL. We demonstrate that generation and display of tree-populated scenes with shadows at interactive rates can be achieved by utilizing the massively parallel GPU architecture to accelerate the computationally intensive steps of the method. A comparison with the performance of single-threaded and CPU-based OpenCL implementation of the same method is reported.

Vorheriger Artikel Introducing uncertainty in complex event processing: model, implementation, and validation

Nächster Artikel Self-repairing codes

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Aiteanu F, Klein R (2014) Hybrid tree reconstruction from inhomogeneous point clouds. Vis Comput 30(6–8):763–771CrossRef

Aono M, Kunii T (1984) Botanical tree image generation. IEEE Comput Graph Appl 4(5):10–34CrossRef

Balandier P, Lacointe A, Roux XL, Sinoquet H, Cruiziat P, Dizès SL (2000) SIMWAL: a structural-functional model simulating single walnut tree growth in response to climate and pruning. Ann For Sci 57:571–585CrossRef

Bédorf J, Gaburov E, Portegies Zwart S (2012) A sparse octree gravitational N-body code that runs entirely on the GPU processor. J Comput Phys 231(7):2825–2839CrossRefMATHMathSciNet

Beneš B, Št’ava O, Měch R, Miller G (2011) Guided procedural modeling. Comput Graph Forum 30(2):325–334CrossRef

Beneš B, Andrysco N, Št’ava O (2009) Interactive Modeling of Virtual Ecosystems. In: Proceedings of the Fifth Eurographics Conference on Natural Phenomena, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, NPH’09, pp 9–16

Beneš B, Massih MA, Jarvis P, Aliaga DG, Vanegas CA (2011) Urban ecosystem design. In: Symposium on Interactive 3D Graphics and Games, ACM, New York, NY, USA, I3D ’11, pp 167–174

Billeter M, Olsson O, Assarsson U (2009) Efficient stream compaction on wide SIMD many-core architectures. In: Proceedings of the Conference on High Performance Graphics 2009, ACM, New York, NY, USA, HPG ’09, pp 159–166

Blelloch GE (1990) Prefix Sums and Their Applications. Tech. Rep. CMU-CS-90-190, School of Computer Science, Carnegie Mellon University

10.

Bornhofen S, Lattaud C (2009) Competition and evolution in virtual plant communities: a new modeling approach. Nat Compt 8(2):349–385CrossRefMathSciNet

11.

Breitbart J (2009) Data structure design for GPU based heterogeneous systems. In: High Performance Computing Simulation, 2009. HPCS ’09. International Conference on, pp 44–51

12.

Bucksch A, Lindenbergh RC, Menenti M (2009) Skeltre—fast skeletonisation for imperfect point cloud data of botanic trees. In: Proceedings of the 2Nd Eurographics Conference on 3D Object Retrieval, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, EG 3DOR’09, pp 13–20

13.

Chelle M, Andrieu B (2007) Modelling the light environment of virtual crop canopies. In: Marcelis L, de Visser P, Struik P, Vos J, Evers J (eds) Functional-structural plant modelling in crop production. Springer, Dordrecht, The Netherlands, pp 75–89

14.

Chen X, Neubert B, Xu YQ, Deussen O, Kang SB (2008) Sketch-based tree modeling using Markov random field. ACM Trans Graph 27(5):109:1–109:9CrossRef

15.

Deussen O, Hanrahan P, Lintermann B, Měch R, Pharr M, Prusinkiewicz P (1998) Realistic modeling and rendering of plant ecosystems. In: Proceedings of the 25th annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, SIGGRAPH ’98, pp 275–286

16.

Giacomo TD, Capo S, Faure F (2001) An interactive forest. In: Proceedings of the Eurographic workshop on Computer animation and simulation. Springer-Verlag New York Inc, New York, NY, USA, pp 65–74

17.

Goldfarb M, Jo Y, Kulkarni M (2013) General transformations for GPU execution of tree traversals. In: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, ACM, New York, NY, USA, SC ’13, pp 10:1–10:12

18.

Greene N (1989) Voxel space automata: modeling with stochastic growth processes in voxel space. In: SIGGRAPH’89, pp 175–184

19.

Hart JC, Baker B, Michaelraj J (2003) Structural simulation of tree growth and response. Vis Comput 19(2–3):151–163MATH

20.

Holton M (1994) Strands, gravity and botanical tree imagery. Comput Graph Forum 13(1):57–67CrossRef

21.

Jablin TB, Jablin JA, Prabhu P, Liu F, August DI (2012) Dynamically managed data for CPU-GPU architectures. In: Proceedings of the Tenth International Symposium on Code Generation and Optimization, ACM, pp 165–174

22.

Kalojanov J, Slusallek P (2009) A parallel algorithm for construction of uniform grids. In: Proceedings of the Conference on High Performance Graphics 2009, ACM, New York, NY, USA, HPG ’09, pp 23–28

23.

Kim J, Cho H (2012) Efficient modeling of numerous trees by introducing growth volume for real-time virtual ecosystems. J Vis Compt Animat 23(3–4):155–165

24.

Lacz P, Hart JC (2004) Procedural Geometry Synthesis on the GPU. Workshop on General Purpose Computing on Graphics Processors. ACM, New York, NY, USA, pp 23–23

25.

Lauterbach C, Garland M, Sengupta S, Luebke DP, Manocha D (2009) Fast BVH construction on GPUs. Comput Graph Forum 28(2):375–384CrossRef

26.

Lefohn A, Kniss JM, Strzodka R, Sengupta S, Owens JD (2006) Glift: Generic, efficient, random-access GPU data structures. ACM Trans Graph 25(1):60–99CrossRef

27.

Li C, Deussen O, Song YZ, Willis P, Hall P (2011) Modeling and generating moving trees from video. ACM Trans Graph 30(6):127:1–127:12CrossRef

28.

Lintermann B, Deussen O (1999) Interactive modeling of plants. IEEE Comput Graph Appl 19(1):56–65

29.

Lipp M, Wonka P, Wimmer M (2010) Technical section: parallel generation of multiple L-systems. Comput Graph 34(5):585–593CrossRef

30.

Livny Y, Yan F, Olson M, Chen B, Zhang H, El-Sana J (2010) Automatic reconstruction of tree skeletal structures from point clouds. ACM Trans Graph 29(6):151:1–151:8CrossRef

31.

Livny Y, Pirk S, Cheng Z, Yan F, Deussen O, Cohen-Or D, Chen B (2011) Texture-lobes for tree modelling. ACM Trans Graph 30:53:1–53:10CrossRef

32.

Longay S, Runions A, Boudon F, Prusinkiewicz P (2012) TreeSketch: interactive procedural modeling of trees on a tablet. In: Proceedings of the International Symposium on Sketch-Based Interfaces and Modeling, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SBIM ’12, pp 107–120

33.

Lopez G, Favreau R, Smith C, Costes E, Prusinkiewicz P, DeJong TM (2008) Integrating simulation of architectural development and source-sink behaviour of peach trees by incorporating Markov chains and physiological organ function submodels into L-PEACH. Funct Plant Biol 35(9–10):761–771CrossRef

34.

Lopez LD, Ding Y, Yu J (2010) Modeling complex unfoliaged trees from a sparse set of images. Comput Graph Forum 29(7):2075–2082CrossRef

35.

Munshi (Ed) A (2011) The OpenCL Specification, version 1.1. Khronos OpenCL Working Group, URL http://khronos.org/registry/cl/specs/opencl-1.1.pdf

36.

Munshi (Ed) A (2014) The OpenCL Specification, version 2.0. Khronos OpenCL Working Group, URL http://khronos.org/registry/cl/specs/opencl-2.0.pdf

37.

Měch R, Prusinkiewicz P (1996) Visual models of plants interacting with their environment. In: Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, ACM, New York, NY, USA, SIGGRAPH ’96, pp 397–410

38.

Měch R, Prusinkiewicz P (2003) Generating subdivision curves with L-systems on a GPU. In: ACM SIGGRAPH 2003 Sketches & Applications, ACM, New York, NY, USA, SIGGRAPH ’03, pp 1–1

39.

Neubert B, Franken T, Deussen O (2007) Approximate image-based tree-modeling using particle flows. ACM Transactions on Graphics (TOG), vol 26, issue 3. ACM

40.

Oppenheimer PE (1986) Real time design and animation of fractal plants and trees. In: Proceedings of the 13th Annual Conference on Computer Graphics and Interactive Techniques, ACM, New York, NY, USA, SIGGRAPH ’86, pp 55–64

41.

Palubicki W (2007) Fuzzy plant modeling with OpenGL—novel approaches in simulating phototropism and environmental conditions. VDM Verlag, Saarbrücken

42.

Pałubicki W, Horel K, Longay S, Runions A, Lane B, Měch R, Prusinkiewicz P (2009) Self-organizing tree models for image synthesis. ACM Trans Graph 28(3):58:1–58:10

43.

Pirk S, Niese T, Deussen O, Neubert B (2012) Capturing and animating the morphogenesis of polygonal tree models. ACM Trans Graph 31(6):169:1–169:10CrossRef

44.

Pirk S, Stava O, Kratt J, Said MAM, Neubert B, Měch R, Benes B, Deussen O (2012) Plastic trees: interactive self-adapting botanical tree models. ACM Trans Graph 31(4):50:1–50:10CrossRef

45.

Prusinkiewicz P (2000) Simulation modeling of plants and plant ecosystems. Commun ACM 43(7):84–93

46.

Prusinkiewicz P, Lindenmayer A, Hanan J (1988) Development models of herbaceous plants for computer imagery purposes. In: Proceedings of the 15th Annual Conference on Computer Graphics and Interactive Techniques, ACM, New York, NY, USA, SIGGRAPH ’88, pp 141–150

47.

Prusinkiewicz P, James M, Mech R (1994) Synthetic topiary. In: SIGGRAPH, pp 351–358

48.

Reeves WT, Blau R (1985) Approximate and probabilistic algorithms for shading and rendering structured particle systems. In: Proceedings of the 12th Annual Conference on Computer Graphics and Interactive Techniques, ACM, New York, NY, USA, SIGGRAPH ’85, pp 313–322

49.

de Reffye P, Edelin C, Françon J, Jaeger M, Puech C (1988) Plant models faithful to botanical structure and development. In: Proceedings of the 15th Annual Conference on Computer Graphics and Interactive Techniques, ACM, New York, NY, USA, SIGGRAPH ’88, pp 151–158

50.

Rodkaew Y, Chongstitvatana P, Siripant S, Lursinsap C (2003) Particle systems for plant modeling. In: Hu, B.G., Jaeger, M. (eds) Plant growth modeling and applications. Proceedings of PMA03, Tsinghua University Press and Springer, Bejing, pp 210–217

51.

Runions A, Lane B, Prusinkiewicz P (2007) Modeling Trees with a Space Colonization Algorithm. In: Proceedings of the Third Eurographics Conference on Natural Phenomena, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, NPH’07, pp 63–70

52.

Satish N, Harris M, Garland M (2009) Designing efficient sorting algorithms for manycore GPUs. In: Proceedings of the 2009 IEEE International Symposium on Parallel&Distributed Processing, IEEE Computer Society, Washington, DC, USA, IPDPS ’09, pp 1–10

53.

Shesh A (2010) GPU-generated “parameterized” trees. In: Proceedings of the 26th Spring Conference on Computer Graphics, ACM, New York, NY, USA, SCCG ’10, pp 127–132

54.

Soler C, Sillion F, Blaise F, Dereffye P (2003) An efficient instantiation algorithm for simulating radiant energy transfer in plant models. ACM Trans Graph 22(2):204–233

55.

Stava O, Pirk S, Kratt J, Chen B, Měch R, Deussen O, Benes B (2014) Inverse procedural modelling of trees. Comput Graph Forum. doi:10.1111/cgf.12282

56.

Steinberger M, Kenzel M, Kainz B, Wonka P, Schmalstieg D (2014) On-the-fly generation and rendering of infinite cities on the GPU. Comput Graph Forum 33(2):105–114CrossRef

57.

Wang Y, Chang X, Ning X, Zhang J, Shi Z, Zhao M, Wang Q (2012) Tree branching reconstruction from unilateral point clouds. In: Pan Z, Cheok A, Müller W, Chang M, Zhang M (eds) Transactions on Edutainment VIII, vol 7220., Lecture Notes in Computer ScienceSpringer, Berlin Heidelberg, pp 250–263CrossRef

58.

Weber D, Bender J, Schnoes M, Stork A, Fellner D (2013) Efficient GPU data structures and methods to solve sparse linear systems in dynamics applications. Comput Graph Forum 32(1):16–26CrossRef

59.

Weber J, Penn J (1995) Creation and rendering of realistic trees. In: Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, SIGGRAPH ’95, pp 119–128

60.

Wither J, Boudon F, Cani MP, Godin C (2009) Structure from silhouettes: a new paradigm for fast sketch-based design of trees. Comput Graph Forum 28(2):541–550CrossRef

61.

Xu L, Mould D (2012) A procedural method for irregular tree models. Comput Graph 36(8):1036–1047CrossRef

62.

Zamuda A, Brest J, Bošković B, Žumer V (2011) Differential evolution for parameterized procedural woody plant models reconstruction. Appl Soft Comput 11(8):4904–4912CrossRef

63.

Zhou K, Gong M, Huang X, Guo B (2011) Data-parallel octrees for surface reconstruction. IEEE Trans Vis Comput Graph 17(5):669–681CrossRef

Titel: Interactive synthesis of self-organizing tree models on the GPU
verfasst von: Štefan Kohek
Damjan Strnad
Publikationsdatum: 01.02.2015
Verlag: Springer Vienna
Erschienen in: Computing / Ausgabe 2/2015
Print ISSN: 0010-485X
Elektronische ISSN: 1436-5057
DOI: https://doi.org/10.1007/s00607-014-0424-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Premium Partner