The Animal Farm Research

This set of references isn't nearly comprehensive - there's a lot of information about procedurally generating textures, much more than buildings or cities. My thesis also isn't focused on textures, so it's just a side-section. Still, a lot of useful papers:

• Ebert, D. S., Musgrave, F. K., Peachey, D., Perlin, K., and Worley, S. 2002 Texturing and Modeling: a Procedural Approach. 3rd. Morgan Kaufmann Publishers Inc.
• Perlin, K. 1985. An image synthesizer. SIGGRAPH Comput. Graph. 19, 3 (Jul. 1985), 287-296. DOI= http://doi.acm.org/10.1145/325165.325247
• Witkin, A. and Kass, M. 1991. Reaction-diffusion textures. SIGGRAPH Comput. Graph. 25, 4 (Jul. 1991), 299-308. DOI= http://doi.acm.org/10.1145/127719.122750
• Reeves, W. T. 1983. Particle Systems—a Technique for Modeling a Class of Fuzzy Objects. ACM Trans. Graph. 2, 2 (Apr. 1983), 91-108. DOI= http://doi.acm.org/10.1145/357318.357320
• Miyata, K. 1990. A method of generating stone wall patterns. SIGGRAPH Comput. Graph. 24, 4 (Sep. 1990), 387-394. DOI= http://doi.acm.org/10.1145/97880.97921
• Preparata, F. P. and Shamos, M. I. 1985 Computational Geometry: an Introduction. Springer-Verlag New York, Inc.
• Legakis, J., Dorsey, J., and Gortler, S. 2001. Feature-based cellular texturing for architectural models. In Proceedings of the 28th Annual Conference on Computer Graphics and interactive Techniques SIGGRAPH '01. ACM, New York, NY, 309-316. DOI= http://doi.acm.org/10.1145/383259.383293
• Lefebvre, L., and Poulin, P. 2000. Analysis and synthesis of structural textures. In Graphics Interface, 77-86
• Wei, L. and Levoy, M. 2000. Fast texture synthesis using tree-structured vector quantization. In Proceedings of the 27th Annual Conference on Computer Graphics and interactive Techniques International Conference on Computer Graphics and Interactive Techniques. ACM Press/Addison-Wesley Publishing Co., New York, NY, 479-488. DOI= http://doi.acm.org/10.1145/344779.345009
• Lefebvre, S. and Neyret, F. 2003. Pattern based procedural textures. In Proceedings of the 2003 Symposium on interactive 3D Graphics (Monterey, California, April 27 - 30, 2003). I3D '03. ACM, New York, NY, 203-212. DOI= http://doi.acm.org/10.1145/641480.641518

Continuing in yesterday's trend, here are a bunch of references for procedural city generation:

• Parish, Y. I. and Müller, P. 2001. Procedural modeling of cities. In Proceedings of the 28th Annual Conference on Computer Graphics and interactive Techniques SIGGRAPH '01. ACM, New York, NY, 301-308. DOI= http://doi.acm.org/10.1145/383259.383292
• Greuter, S., Parker, J., Stewart, N., and Leach, G. 2003. Real-time procedural generation of `pseudo infinite' cities. In Proceedings of the 1st international Conference on Computer Graphics and interactive Techniques in Australasia and South East Asia (Melbourne, Australia, February 11 - 14, 2003). GRAPHITE '03. ACM, New York, NY, 87-ff. DOI= http://doi.acm.org/10.1145/604471.604490
• Laycock, R. G. and Day, A. M. 2003. Automatically generating large urban environments based on the footprint data of buildings. In Proceedings of the Eighth ACM Symposium on Solid Modeling and Applications (Seattle, Washington, USA, June 16 - 20, 2003). SM '03. ACM, New York, NY, 346-351. DOI= http://doi.acm.org/10.1145/781606.781663
• Kelly, G. and McCabe, H. 2006. A Survey of Procedural Techniques for City Generation. In ITB Journal, Issue 14. Available from http://www.gamesitb.com/SurveyProcedural.pdf
• Sun, J., Yu, X., Baciu, G., and Green, M. 2002. Template-based generation of road networks for virtual city modeling. In Proceedings of the ACM Symposium on Virtual Reality Software and Technology (Hong Kong, China, November 11 - 13, 2002). VRST '02. ACM, New York, NY, 33-40. DOI= http://doi.acm.org/10.1145/585740.585747
• Kelly, G. and McCabe, H. 2006. Interactive generation of cities for real-time applications. In ACM SIGGRAPH 2006 Research Posters (Boston, Massachusetts, July 30 - August 03, 2006). SIGGRAPH '06. ACM, New York, NY, 44. DOI= http://doi.acm.org/10.1145/1179622.1179673

I spent the night organizing my references so that they're easier to cite while writing the actual thesis. I've got a lot of stuff here that other people might find useful, so I'm going to make a multi-day event of posting the references I have. Most of the references have ACM links, so they're fairly easy to get at if you have access to the ACM journals. If not, you can probably still Google Scholar the titles and find PDFs floating around. They're not in any particular order; in the paper I'll be rearranging them based on when they are cited, but that hasn't happened yet.

I've got stuff related to rendering, procedural content generation of almost every variety (cities, buildings, plants, textures, worlds), some machine learning, a tad bit of rejection sampling, and a few odds-and-ends. Tonight I'll stick with the procedural building generation, which is probably my largest set:

• Müller, P., Wonka, P., Haegler, S., Ulmer, A., and Van Gool, L. 2006. Procedural modeling of buildings. ACM Trans. Graph. 25, 3 (Jul. 2006), 614-623. DOI= http://doi.acm.org/10.1145/1141911.1141931
• Wonka, P., Wimmer, M., Sillion, F., and Ribarsky, W. 2003. Instant architecture. ACM Trans. Graph. 22, 3 (Jul. 2003), 669-677. DOI= http://doi.acm.org/10.1145/882262.882324
• Stiny G, 1980. Introduction to shape and shape grammars. Environment and Planning B 7(3) 343-351
• Flemming U, 1987. More than the sum of parts: the grammar of Queen Anne houses. Environment and Planning B: Planning and Design 14(3) 323-350
• Stiny, G., and Mitchell, W.J. 1978. The palladian grammar. Environment and Planning B 5, 5-18
• Müller, P., Zeng, G., Wonka, P., and Van Gool, L. 2007. Image-based procedural modeling of facades. ACM Trans. Graph. 26, 3 (Jul. 2007), 85. DOI= http://doi.acm.org/10.1145/1276377.1276484
• Debevec, P. E., Taylor, C. J., and Malik, J. 1996. Modeling and rendering architecture from photographs: a hybrid geometry- and image-based approach. In Proceedings of the 23rd Annual Conference on Computer Graphics and interactive Techniques SIGGRAPH '96. ACM, New York, NY, 11-20. DOI= http://doi.acm.org/10.1145/237170.237191
• Thiemann, F., and Sester, M. 2004. Segmentation of Buildings for 3D-Generalisation. In ICA Workshop on Generalisation and Multiple Representation. 20-21
• Birch, P. J., Browne, S. P., Jennings, V. J., Day, A. M., and Arnold, D. B. 2001. Rapid procedural-modelling of architectural structures. In Proceedings of the 2001 Conference on Virtual Reality, Archeology, and Cultural Heritage (Glyfada, Greece, November 28 - 30, 2001). VAST '01. ACM, New York, NY, 187-196. DOI= http://doi.acm.org/10.1145/584993.585023
• Noel, J. 2003. Dynamic Building Plan Generation. Undergraduate Project Disseration, University of Sheffield, 2003. Available from http://www.dcs.shef.ac.uk/intranet/teaching/projects/archive/ug2003/pdf/u0jn.pdf
• Martin, J. 2006. Procedural House Generation: A method for dynamically generating floor plans. In Symposium on Interactive 3D Graphics and Games. Available from http://www.cs.unc.edu/~jmartin/i3d/poster.pdf
• Martin, J. 2004. The Algorithmic Beauty of Buildings Methods for Procedural Building Generation. Computer Science Honors Thesis, Trinity University, Texas. Available from http://lib.trinity.edu/digitalcommons/cs_honors/4/doc.pdf
• 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 (Jul. 2002), 302-311. DOI= http://doi.acm.org/10.1145/566654.566581

The nVidia GeForce 8 Documentation explicitly says that loops should now support run-time condition testing, which to my mind means that non-const variables should be permissible in the condition test. Either way, I should be able to create an infinite loop and have a statement inside which breaks out of the loop once a counter variable reaches a certain, dynamically calculated number. And barring that, I should be able to create a for-loop that executes some max number of iterations, but also has a statement inside which breaks out once the counter variable reaches a certain number.

Of course, none of the above works on my 8800 GTX. I speculated that there was some loop unrolling going on that might be throwing the system off, but a quick look at the generated assembly (using NVemulate, handy little program that it is) indicated otherwise. The last example I gave above is especially weird: I can create a for-loop that executes a max number of iterations and put a break condition inside, but the number I put in as the max number of iterations matters and is very, very touchy, despite that the underlying assembly doesn't change at all. Sometimes I can use 70 just fine, sometimes I can only go up to 10, which is highly restrictive.

This isn't an app-killer; I've got my system basically working and working well, but for some of my requirements the restrictions might get in my way.

Alas, the majority of nVidia's profiling/debugging tools only work with DirectX, so I am either forced to insert code myself or find different tools.

GLIntercept looked promising, but it hasn't been updated in a little over two years. There's no logging of geometry shader info in there, which I could really use. It also appears to be mostly non-interactive, preferring to output results to log files (though it does have some very interesting plugins that allow you to dynamically edit shaders or fly through a scene).

glslDevil is much cooler, though very temperamental. It gives dynamic information, allows stepping through GL calls, allows stepping through shaders (very cool), allows putting watches on shader variables (cooler), can show/save the framebuffer, and do a whole lot more. It also gives geometry shader information. It does, however, crash a lot; it crashes when my research program compiles a shader, which is, uh, unfortunate.

It confuses me a bit why the GPU doesn't have a decent random number generator. Procedural textures have been around for quite some time, and moving their generation to a shader makes sense. There is a noise function in GLSL which doesn't work reliably (everything I've read indicates it always returns a 0 on nVidia cards). I needed some kind of random number generation for my building generation, so I had to write my own.

The Mersenne Twister was the first to catch my attention, but after looking at a few implementations, it doesn't look like a natural fit for a GPU. It's fast, which is good, but it has a few bits of the algorithm (using an array for a state vector, really large numbers that would cause an error on the GPU) that made it prohibitive. If I knew the algorithm well enough, perhaps I could overcome the limitations, but I really don't have any experience in this area.

Someone on GameDev.net recommended Simplex Noise, which resembles Perlin noise. This algorithm seemed fairly involved though, and I don't need Perlin noise - random noise works fine for my purposes. Were I randomly generating textures, this would be something to look into.

I landed on a Linear Congruential Generator, which seems to be the simplest type of generator. It's fast, in my case only requiring a single multiplication and modulus operator. The distribution it generates is reasonable; it could be better, but I'm not doing cryptography here. I had to search a bit on the internet for numbers that worked better (the numbers in the Wikipedia article don't play nice with the GPU), but now I'm pretty much set.

Seeding is slightly awkward on the GPU, since I'm doing some ping-ponging and there's no global memory to speak of. Basically I send in a seed with my first bit of data. Then I generate a few numbers and output a new seed with a building component by adding some component-specific attributes to the current seed. Since those are floats, the inaccuracy may be costing me a degree of determinism. Alternatively, it would probably be more random and more deterministic (odd little combination there) if the new seed I output were just the sum of a few random integers, but that would be slower and I'm not sure that it's necessary for my purposes.

So apparently GLSL is very touchy, and instead of giving reasonable error messages or even reporting linking errors, it will choose to simply not work. Sometimes this will be a cryptic failure to link with a meaningless OpenGL error; sometimes the shader will just hang indefinitely. Here are some things I've learned:

Just because you have some varyings and they're used all throughout your code does not mean they're active when you link the shader program. This is problematic when you have to get the location of those varyings so that you can bind them to transform feedback. nVidia is kind enough to provide an extension to force varying variables to be active upon linking. Be sure to use that.

If you attempt to access an invalid array index with a constant, it's a linking error, not a runtime error.

Using variables in loop-terminating conditions is, at best, problematic. If you're very, very lucky, you won't have any problems. What's more likely to happen is that your shader will hang indefinitely. For that scenario, a work-around exists where you use a large (not too large, mind) constant instead of a variable, and then break out of the loop when the loop counter reaches the variable.

It's nice that logs exist, but in my experience, they only report hard syntax errors or blatantly invalid statements (invalid implicit casts, for instance). Subtle nuances like the one above are unreported.

These aren't the only problems, but they're the most prevalent ones currently.