“Representing and scheduling procedural generation using operator graphs”
Conference:
Type(s):
Title:
- Representing and scheduling procedural generation using operator graphs
Session/Category Title: Sound & Pattern Synthesis
Presenter(s)/Author(s):
Abstract:
In this paper, we present the concept of operator graph scheduling for high performance procedural generation on the graphics processing unit (GPU). The operator graph forms an intermediate representation that describes all possible operations and objects that can arise during a specific procedural generation. While previous methods have focused on parallelizing a specific procedural approach, the operator graph is applicable to all procedural generation methods that can be described by a graph, such as L-systems, shape grammars, or stack based generation methods. Using the operator graph, we show that all partitions of the graph correspond to possible ways of scheduling a procedural generation on the GPU, including the scheduling strategies of previous work. As the space of possible partitions is very large, we describe three search heuristics, aiding an optimizer in finding the fastest valid schedule for any given operator graph. The best partitions found by our optimizer increase performance of 8 to 30x over the previous state of the art in GPU shape grammar and L-system generation.
References:
1. Beneš, B., Štava, O., Měch, R., and Miller, G. 2011. Guided Procedural Modeling. Comp. Graph. Forum 30, 2, 325–334. Cross Ref
2. Guerrero, P., Jeschke, S., Wimmer, M., and Wonka, P. 2015. Learning shape placements by example. ACM Trans. Graph. 34, 4 (July), 108:1–108:13.
3. Haegler, S., Wonka, P., Arisona, S. M., Gool, L. J. V., and Müller, P. 2010. Grammar-based Encoding of Facades. Comp. Graph. Forum 29, 4, 1479–1487.
4. Havemann, S. 2005. Generative Mesh Modeling. PhD thesis, TU Braunschweig.
5. He, Y., Foley, T., Tatarchuk, N., and Fatahalian, K. 2015. A system for rapid, automatic shader level-of-detail. ACM Trans. Graph. 34, 6 (Oct.), 187:1–187:12.
6. Krecklau, L., and Kobbelt, L. 2011. Procedural Modeling of Interconnected Structures. Comp. Graph. Forum 30.
7. Krecklau, L., Pavic, D., and Kobbelt, L. 2011. Generalized Use of Non-Terminal Symbols for Procedural Modeling. Comp. Graph. Forum 29, 2291–2303. Cross Ref
8. Krejcie, R. V., and Morgan, D. W. 1970. Determining sample size for research activities. Educ Psychol Meas.
9. Lacz, P., and Hart, J. 2004. Procedural Geometry Synthesis on the GPU. In Workshop on General Purpose Computing on Graphics Processors, 23–23.
10. Li, Y., Bao, F., Zhang, E., Kobayashi, Y., and Wonka, P. 2011. Geometry Synthesis on Surfaces Using Field-Guided Shape Grammars. IEEE Trans. Visualization and Computer Graphics 17, 2, 231–243.
11. Lipp, M., Wonka, P., and Wimmer, M. 2010. Parallel Generation of Multiple L-systems. Computers & Graphics 34, 5, 585–593.
12. Magdics, M. 2009. Real-time Generation of L-system Scene Models for Rendering and Interaction. In Spring Conf. on Computer Graphics, Comenius Univ., 77–84.
13. Marvie, J.-E., Pascal, G., Hirtzlin, P., and Gael, S. 2011. Render-Time Procedural Per-Pixel Geometry Generation. In Graphics Interface, 167–174.
14. Marvie, J.-E., Buron, C., Gautron, P., Hirtzlin, P., and Sourimant, G. 2012. GPU Shape Grammars. Comp. Graph. Forum 31, 7-1, 2087–2095.
15. Mullapudi, R. T., Adams, A., Sharlet, D., Ragan-Kelley, J., and Fatahalian, K. 2016. Automatically scheduling Halide image processing pipelines. ACM Trans. Graph. 35, 4 (July), 83:1–83:11.
16. 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.
17. Parish, Y. I. H., and Müller, P. 2001. Procedural modeling of cities. In Proc. SIGGRAPH 2001, 301–308.
18. Parker, S. G., Bigler, J., Dietrich, A., Friedrich, H., Hoberock, J., Luebke, D., McAllister, D., McGuire, M., Morley, K., Robison, A., and Stich, M. 2010. Optix: A general purpose ray tracing engine. ACM Trans. Graph. 29, 4 (July), 66:1–66:13.
19. Patney, A., Tzeng, S., Seitz, Jr., K. A., and Owens, J. D. 2015. Piko: A framework for authoring programmable graphics pipelines. ACM Trans. Graph. 34, 4 (July), 147:1–147:13.
20. Patow, G. 2012. User-friendly graph editing for procedural modeling of buildings. Computer Graphics and Applications, IEEE 32, 2 (March), 66–75.
21. Prusinkiewicz, P., and Lindenmayer, A. 1990. The Algorithmic Beauty of Plants. Springer-Verlag.
22. Prusinkiewicz, P., James, M., and Měch, R. 1994. Synthetic Topiary. In Proc. SIGGRAPH 94, 351–358.
23. Ragan-Kelley, J., Adams, A., Paris, S., Levoy, M., Amarasinghe, S., and Durand, F. 2012. Decoupling algorithms from schedules for easy optimization of image processing pipelines. ACM Trans. Graph. 31, 4 (July), 32:1–32:12.
24. Ritchie, D., Mildenhall, B., Goodman, N. D., and Hanrahan, P. 2015. Controlling procedural modeling programs with stochastically-ordered sequential monte carlo. ACM Transactions on Graphics (TOG) 34, 4, 105.
25. Schwarz, M., and Müller, P. 2015. Advanced procedural modeling of architecture. ACM Trans. Graph. 34, 4 (July), 107:1–107:12.
26. Steinberger, M., Kenzel, M., Boechat, P., Kerbl, B., Dokter, M., and Schmalstieg, D. 2014. Whippletree: Task-based scheduling of dynamic workloads on the GPU. ACM Trans. Graph. 33, 6, 228:1–228:11.
27. Steinberger, M., Kenzel, M., Kainz, B., Müller, J., Wonka, P., and Schmalstieg, D. 2014. Parallel generation of architecture on the GPU. Computer Graphics Forum 33, 2, 73–82.
28. Steinberger, M., Kenzel, M., Kainz, B., Wonka, P., and Schmalstieg, D. 2014. On-the-fly generation and rendering of infinite cities on the GPU. Computer Graphics Forum 33, 2, 105–114.
29. Stiny, G. 1975. Pictorial and Formal Aspects of Shape and Shape Grammars. Birkhauser Verlag.
30. Stiny, G. 1982. Spatial Relations and Grammars. Environment and Planning B 9, 313–314. Cross Ref
31. Sugerman, J., Fatahalian, K., Boulos, S., Akeley, K., and Hanrahan, P. 2009. GRAMPS: A programming model for graphics pipelines. ACM Trans. Graph. 28, 1 (Feb.), 4:1–4:11.
32. Sussman, G., Abelson, H., and Sussman, J., 1983. Structure and interpretation of computer programs.
33. Talton, J. O., Lou, Y., Lesser, S., Duke, J., Měch, R., and Koltun, V. 2011. Metropolis Procedural Modeling. ACM Trans. Graph. 30, 11:1–11:14.
34. Wadge, W. W., and Ashcroft, E. A. 1985. Lucid, the dataflow programming langugage1. Academic Press.
35. Wonka, P., Wimmer, M., Sillion, F. X., and Ribarsky, W. 2003. Instant Architecture. ACM Trans. Graph. 22, 669–677.
