Papers We Love Montreal Followup: Procedural Modeling of Buildings [pwl, shape-grammar, test-generation, procedural-content-generation, no-code]

(I organize a meetup group which is the Montreal chapter of Papers We Love; we meet monthly to discuss a paper or papers someone loves, to help bridge the gap between industry and academia for working programmers. This is a followup to the last meetup, where I talked about the paper Procedural Modeling of Buildings.)

1. On questions

There were some very good questions during my talk, but I think it could be made more clear: at a PWL meetup, there are no dumb questions, and "What's a Spline?" questions can often benefit everyone. For example, I was a little surprised no one asked about Euler operators, since I'd never heard of them until I started implementing the boundary representation code for this talk. There were a few aspects like that I realized I should have explained in more detail. Next time, you can help, by speaking up and asking a question.

Also, I'll add this to the meetup page, but it should be noted that papers, presentations, and questions are welcome in French. If the speaker doesn't understand French, someone will be happy to translate.

2. Grammar-driven test case generation

One of the big things we talked about was how to choose productions when generating from a grammar, and I mentioned Monte Carlo tree search in the context of a game where your generator is "playing against" the system under test, with crashes, resource leaks, or code coverage as the "score". Lots of learning algorithms could be used in this case, but MCTS is worth checking out because it doesn't require coming up with a good admissible heuristic yourself. Also, it's a very cool, very general algorithm that has had tremendous success playing Go against humans.

The ABNF-driven generator I mentioned will be released soon. Until then, check out this one.

The paper I mentioned regarding this approach for protocol fuzzing was Extraction of ABNF Rules from RFCs to Enable Automated Test Data Generation.

3. L-systems

The Algorithmic Botany page is full of great stuff, often L-system-related.

I mentioned Sean Barrett's criticism of L-systems, and I think it's worth a read. I don't agree with his conclusion, but his reduction of a specific L-system down to simple algorithm is a great demonstration of the need to think about generality and constraint in notation.

4. Procedural Modeling of Buildings

The most important link is Peter Wonka's publications page; most of the papers mentioned are there, or are directly cited by one of those papers.

In particular, in addition to the central papers discussed (Instant Architecture, Procedural Modeling of Buildings), check out the papers on Inverse Procedural Modeling, and parallel derivation/evaluation of shape grammars.

Also, I mentioned CityEngine, but be sure to check out their impressive demo videos.

Two things I would have liked to discuss more were the parallels between a grammar-driven generator and a programming language interpreter, and graph rewriting / graph grammars. Maybe those are topics that can come up again at a future PWL meetup.

4.1. Bag of links

5. Demos

The 64k demo we watched at the beginning was The Timeless (1st place, pc 64k, Revision 2014), by Mercury. As I mentioned, given what looks like shape grammar techniques, I suspect the title is a reference to The Timeless Way of Building by Christopher Alexander.

I think one of the big inspirations for procedural content generation at this scale was .the .product (1st place, pc 64k, The Party 2000), another 64k demo by one of my favorite demo groups, farbrausch. The architecture generated is less sophisticated than in the Mercury demo, but given that it was released fourteen years ago, I think it could be considered more impressive.

I meant to talk more about the tools they released, but you can find the source code in their github repo. Among other things, this includes their 96 kilobyte FPS game. There are a couple of talks on YouTube by members of farbrausch talking about some of their techniques that are worth checking out, especially if you're interested in texture generation.

6. The next paper

We decided at the meeting to skip December; I'll be out of town, and late December is a busy time for everyone. This gives us a bit of time to plan the January meetup, so I urge anyone in the group with an interest in presenting a paper to contact me about presenting in January.

Alternately, if there's a topic you'd like to see discussed but don't feel comfortable presenting, why not ask?

Here are some papers and topics I'd love to see presented:

There's also a poll, here on the meetup website, but I can appreciate that no one has voted on it yet, since meetup's website forces me to make it illegibly dense. Also, if you need help tracking down a copy of a paper, just email me.

JS