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.
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:
Continuing in yesterday's trend, here are a bunch of references for procedural city generation:
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:
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.
For complex GPGPU stuff and even with normal graphics rendering, it's sometimes required to "ping pong" input and output repeatedly to achieve a desired effect. The output in one pass becomes the input in the next, and the output of that next pass becomes the input to the next, and so on. I just got this process working using vertex buffers and transform feedback, which will lead naturally into my building generation:
Fill a vertex buffer object (we'll call it "send") with some initial information that you want expanded upon. In the case of building generation, this initial information will be the initial lot.
Turn on transform feedback and bind it to a different vertex buffer ("receive"). Transform feedback is used to take geometry data after it's gone through the vertex and geometry processing and place that data back in a client-side buffer. For our purposes, the vertex shader becomes a simple pass-through shader (it doesn't transform the vertices), and the geometry shader is where the spawning of new information (building components) takes place.
Draw the send buffer such that the results of the geometry shader end up in the receive buffer.
Repeat the above steps N times, where N is the total number of passes you need over the data. When dealing with a split grammar, N might just be the number of rules if no rules go 'backward' in the grammar. However, there's no real guarantee of this - I've written grammars myself that go backward. For the time being, I'm going to fix N at 2 * numRules.
Here are some considerations:
Why am I fixing N? Because I haven't thought of a better way to tell if processing of the entire building has finished. I have a hunch I might be able to pull something off here by doing some trickery with the fragment shader, but I'm not certain yet.
Is this going to be faster than doing everything on the CPU? I have no clue. Geometry shaders aren't fully mature yet. When they do mature, this *should* be faster, but I'm not sure by how much yet.
Should I only process a single component in one shader pass, or should I run through multiple steps? Here I run into the risk of exceeding the maximum outputs of a geometry shader, but I think I can safely run through two or three steps in one pass without that being a problem. Whether this will help or hurt speed, I don't know yet.
The next step is writing the code-generator that takes a grammar and turns it into GLSL code. I'm convinced I can do this in a relatively straight-forward fashion, with only a few awkward places (basically anything involving strings). I do, however, need to find a good (and fast) noise function to generate random numbers. I've heard simplex noise is good for this, but I haven't found a lot of information on it yet.
So here's the current problem I'm working on:
There's no good way to send the rules across into the shader dynamically, so I'm nixing that. Instead, I'm writing a translator that takes the rules (as already parsed by Lex/Yacc) and converts them directly into shader code. The rules fit mostly neatly into a series of if-then statements, with little problems when variables or functions are encountered (these problems don't seem heavy, but enough to make the translator a little awkward in places).
After that, it becomes a problem of ping-ponging the generated building components back and forth in such a way that I don't waste time processing components that have already reached terminal status. I thought using multiple transform feedback targets would work - sending the finished components to a different buffer than the unfinished - but there's a limit on the amount of information I can feedback in one shot such that I can't get out all the information needed for this. The nasty alternative seems to be searching through the feedback buffer for terminals and shifting them out, but I can't imagine that being in any way fast. If only fragment shaders allowed a greater number of outputs (since processing any component might result in 10+ other components, a fragment shader won't be able to work here). Fragment shaders are more mature than geometry shaders, and I'm afraid that the geometry shader might not provide a significant speed boost even if I get my current problems worked out.
So here are my current gripes with GPGPU programming:
First, CUDA (a GPGPU library from nVidia) isn't supported under Vista. I'm hesitant to move away from Vista, because if I need to tap into DX10 at some point it won't be feasible on XP. At any rate, CUDA programming seems to be, quite frankly, a little icky.
No static global memory exposed by GLSL! It'd be nice if I could do some computations once, store them in some internal structures, and then use those structures the next time a shader is invoked. But alas, those structures are forced to be local to the current invocation of the shader, meaning any precomputation is thrown out.
No serialization/deserialization of textures. Since any real data has to be sent through a texture, it would be awfully nice if I could fill a texture with my structure data, send it across, and easily reassemble the structures on the other side without a huge speed penalty. Not really possible. Instead, I'm going to have to arrange my texture in such a way that it can act as a structure on its own and pray (oh shall I pray!) that texture reads aren't too slow.
Fragment shaders can only produce one output (barring the existence of multiple render targets, which might allow more). This is by design, I know, but it means that I'm *probably* going to be forced to use geometry shaders, which aren't very mature right now. Hopefully transform feedback isn't horribly slow.
I've read in forums (though I haven't benchmarked this personally) that flow control on the GPU is pretty slow. Let's hope that's false, because my shader is going to rely pretty heavily on it.
So, yea, this ought to be interesting.
In my last post, I talked about the transition table approach to procedural music generation. Since then, I have implemented a neural network approach, which I'm going to talk about now.
Neural networks are interesting in that they "just work." They're hard to prove and verify (though not necessarily impossible), but for a certain class of problems they provide fairly good results.
For music generation... 'eh. Researchers have tried using recurrent neural networks to learn music from a batch of examples. Back-propagation Through Time (BPTT), Long Short-Term Memory, that kind of thing. I tried BPTT personally for class and found the results mediocre at best. It sounds better than the transition table approach, but still not all that pretty.
But to be fair, my methods weren't perfect. Most researchers going in this direction espouse a PHCCCF approach to music representation, whereas I was using something considerably simpler. Further, I didn't include chords or any form of harmonies, and single track melodies aren't always especially impressive. I've been considering extending my research further to see if I could do better, but realistically I'll probably be focusing the majority of my time on building generation.
image: detail of installation by Bronwyn Lace