(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.)
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.
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 paper I mentioned regarding this approach for protocol fuzzing was Extraction of ABNF Rules from RFCs to Enable Automated Test Data Generation.
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.
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.
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.
Bag of links
- Matrix grammar — a potentially simpler way to formalize the LOD idea in the paper;
- Shape Grammars — in which you can find reference to many uses of shape grammars in architecture and design, including the coffee maker and Buick applications I mentioned;
- Virtual Terrain Project;
- Generative Modeling Language;
- GRAPE — a parametric shape grammar interpreter;
- From topologies to shapes: parametric shape grammars implemented by graphs;
- The aesthetics of science fiction spaceship design — be sure to check out the Death Star trench modeling section;
- Andrew Li's publications — including some interesting analysis of historical Chinese building standards with shape grammars;
- Garment-modeling papers that look interesting but which I haven't read:
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.
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:
- Differential Privacy
- Monte Carlo Tree Search
- linear types and all kinds of resource-bound guarantees (e.g. Robson's proof that SQLite uses)
- Flipping Bits in Memory Without Accessing Them (chilling!)
- Coverage is not strongly correlated with test suite effectiveness (provocative!)
- A Language-based Approach to Unifying Events and Threads
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.