{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T04:16:27Z","timestamp":1754108187459,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2016,11,11]],"date-time":"2016-11-11T00:00:00Z","timestamp":1478822400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Max Planck Center for Visual Computing and Communication"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2016,11,11]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/2980179.2980227","type":"journal-article","created":{"date-parts":[[2016,11,11]],"date-time":"2016-11-11T17:02:54Z","timestamp":1478883774000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Representing and scheduling procedural generation using operator graphs"],"prefix":"10.1145","volume":"35","author":[{"given":"Pedro","family":"Boechat","sequence":"first","affiliation":[{"name":"Graz University of Technology, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Dokter","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Kenzel","sequence":"additional","affiliation":[{"name":"Graz University of Technology, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hans-Peter","family":"Seidel","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dieter","family":"Schmalstieg","sequence":"additional","affiliation":[{"name":"Graz University of Technology, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Steinberger","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,12,5]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2011.01886.x"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766933"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2010.01745.x"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818104"},{"key":"e_1_2_2_6_1","doi-asserted-by":"crossref","unstructured":"Krecklau L. and Kobbelt L. 2011. Procedural Modeling of Interconnected Structures. Comp. Graph. Forum 30.  Krecklau L. and Kobbelt L. 2011. Procedural Modeling of Interconnected Structures. Comp. Graph. Forum 30.","DOI":"10.1111\/j.1467-8659.2011.01864.x"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2010.01714.x"},{"key":"e_1_2_2_8_1","doi-asserted-by":"crossref","unstructured":"Krejcie R. V. and Morgan D. W. 1970. Determining sample size for research activities. Educ Psychol Meas.  Krejcie R. V. and Morgan D. W. 1970. Determining sample size for research activities. Educ Psychol Meas.","DOI":"10.1177\/001316447003000308"},{"volume-title":"Procedural Geometry Synthesis on the GPU. In Workshop on General Purpose Computing on Graphics Processors, 23--23","author":"Lacz P.","key":"e_1_2_2_9_1","unstructured":"Lacz , P. , and Hart , J . 2004 . Procedural Geometry Synthesis on the GPU. In Workshop on General Purpose Computing on Graphics Processors, 23--23 . Lacz, P., and Hart, J. 2004. Procedural Geometry Synthesis on the GPU. In Workshop on General Purpose Computing on Graphics Processors, 23--23."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2010.36"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2010.05.014"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1980462.1980478"},{"key":"e_1_2_2_13_1","unstructured":"Marvie J.-E. Pascal G. Hirtzlin P. and Gael S. 2011. Render-Time Procedural Per-Pixel Geometry Generation. In Graphics Interface 167--174.   Marvie J.-E. Pascal G. Hirtzlin P. and Gael S. 2011. Render-Time Procedural Per-Pixel Geometry Generation. In Graphics Interface 167--174."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03201.x"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925952"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141931"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383292"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778803"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766973"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCG.2010.104"},{"key":"e_1_2_2_21_1","doi-asserted-by":"crossref","unstructured":"Prusinkiewicz P. and Lindenmayer A. 1990. The Algorithmic Beauty of Plants. Springer-Verlag.   Prusinkiewicz P. and Lindenmayer A. 1990. The Algorithmic Beauty of Plants. Springer-Verlag.","DOI":"10.1007\/978-1-4613-8476-2"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/192161.192254"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185528"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766895"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766956"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661250"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12312"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12315"},{"volume-title":"Pictorial and Formal Aspects of Shape and Shape Grammars","author":"Stiny G.","key":"e_1_2_2_29_1","unstructured":"Stiny , G. 1975. Pictorial and Formal Aspects of Shape and Shape Grammars . Birkhauser Verlag . Stiny, G. 1975. Pictorial and Formal Aspects of Shape and Shape Grammars. Birkhauser Verlag."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1068\/b090113"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1477926.1477930"},{"key":"e_1_2_2_32_1","unstructured":"Sussman G. Abelson H. and Sussman J. 1983. Structure and interpretation of computer programs.   Sussman G. Abelson H. and Sussman J. 1983. Structure and interpretation of computer programs."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1944846.1944851"},{"key":"e_1_2_2_34_1","unstructured":"Wadge W. W. and Ashcroft E. A. 1985. Lucid the dataflow programming langugage1. Academic Press.   Wadge W. W. and Ashcroft E. A. 1985. Lucid the dataflow programming langugage1. Academic Press."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882324"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2980179.2980227","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2980179.2980227","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:22Z","timestamp":1750220602000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2980179.2980227"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,11]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2016,11,11]]}},"alternative-id":["10.1145\/2980179.2980227"],"URL":"https:\/\/doi.org\/10.1145\/2980179.2980227","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2016,11,11]]},"assertion":[{"value":"2016-12-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}