The Animal Farm Research

I just had another look at Crazy Bump, a very useful tool for generating normal, AO, displacement, and specular maps, only to discover the tool is no longer free. This saddens me. It's a great tool, but I'm not sure what it does warrants a $100 purchase.

CityEngine

A large portion of my research was based off of some of the ideas behind CityEngine. Their building generation interface is much, much slicker than mine, but then, they were probably more than one guy working for less than two semesters.

Free 30 day trial, but $7000 to buy. Not for me.

Master's research is finished, but there are still things to learn. This site never updated much, but I'll be trying harder to keep it going with my various personal projects.

Component-based design has been my latest hot topic. Here are some useful links I've collected (or written):

Component Based Game Architectures - GDNet Post
Outboard component-based entity system architecture - GDNet post
Object Oriented Game Programming: The Behavior System
301: Introduction to Dungeon Siege Architecture
Various Bilas presentations
Some stuff written by Jeremy Chatalaine
The Animal Farm Creations: A Question of Component-Based Design

Here's a brief summary of various programs I've been trying to use to generate AO maps:

faogen: Costs money. Seems pretty reliable and pretty fast. But, against, costs money.

Blender: Er, wouldn't load the .obj file I tried to throw at it, which started things off in exactly the wrong way. Not sure if there's a way to output AO maps... can't find an option in this interface of theirs.

Melody: Stops responding when you do anything. Stops responding when the screensaver starts. Stops responding when the wind blows. Takes a ridiculously long time. It's an nVidia tool, and I'm running on nVidia hardware, so I can't imagine why it's so fragile.

GPU MeshMapper: Surprisingly good. Free, clean interface, works quickly. Requires that I generate a normal map as well, so I can't get reliable timing information from it, which is a bit of a downer. But very fast and good quality results.

Why is it so hard to find anything good?

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.