MSc Thesis: Assisted Object Placement

Mon Feb 18 2013 19:10:29

"Assisted Object Placement" is my master thesis in computers science. You can find the thesis here as PDF (30 MB). The final presentation can be downloaded here as PDF (8 MB) and here as annotated PowerPoint presentation (33 MB with German annotations). The LaTeX source of the thesis is hosted in a BitBucket Mercurial repository; you can find it here.

Modern computer games consist of highly detailed levels that require the manual placement of many small props to look convincing. This consumes a lot of time.

There has been some exciting research on generating levels dynamically and automatically ¹, and some games already create full levels automatically, most famously probably the Diablo series. However, there are few research papers which focus on assisting the level designers. This is a very different kind of task compared to fully generating levels because such a system has to work alongside manually generated content and has to be able to incorporate it into its reasoning.

My supervisor, Matthäus Chajdas, has previously researched how textures can be assigned automatically in a level and published a paper called "Assisted Texture Assignment", and he wanted to see if his approach could be extended to place objects as well. Thus the main goal was to learn object placement from an existing scene using the scene's geometry and visual appearance, and without requiring additional augmentation of the scene data.

The basic idea is to use probes to sample the environment around all possible objects that we might want to suggest. Later, to make a suggestion for an object to be placed in a certain volume, we sample the volume's environment as well using probes, and search for the objects whose probe samples match the volume's samples best.

In Assisted Texture Assignment he found that it's better to use many simple probes to sample the environment because it is easier to handle partial matches this way. So we tried this as well.

Example scene Sampled distances. The darker, the nearer; light blue is the “miss” color. Sampled colors Sampled occlusion. The brighter, the less occluded.

A probe samples depth, color and occlusion in a cone using ray-casting with NVIDIA's OptiX. The usual 26 directions that point to all neighbors in a regular 3D grid are supported, and the cones are chosen so that sampling all directions covers the whole sphere. When sampling objects, we voxelize their models to find the best positions and directions for probes to avoid redundant sampling. We then store all probe samples in a database.

Model Voxelized model Generated probes Generated probes overlayed on model

I have implemented a conservative voxelizer using the approach described in "OpenGL Insights, Chapter 22: Octree-Based Sparse Voxelization Using the GPU Hardware Rasterizer" and "GPU Gems 2, Chapter 42: Conservative Rasterization" to make sure that enough probes are generated.

Textured model Model with surface normals shown Voxelized model (without conservative rasterization).
Notice how the antenna has not been sampled correctly. Voxelized model (with conservative rasterization). The antenna is fully sampled now.

We quantize the gathered probe samples into about 22 bits and use hash lookups to find matches. This makes our algorithm very fast.

We also use neighborhood information, that is the distance to other game objects, to improve the results.

Finding a consistent way to score probe matches and a metric to compare neighborhood information on the one hand and a way to combine both results on the other hand turned out to be quite difficult because there is no canonical way for it, and I struggled a lot with trying to find the right approaches. In the end, we tried several different methods and compared their results to choose the best one.

I validated my algorithm with different levels from the game Shadowgrounds Survivor. For this, I sample all objects of interest in a level, and then I remove one object at a time and ask our algorithm for a suggestion at its former position. I use the rank of the removed object in the suggestion list as an error measure: if it comes first, the algorithm ran perfectly; if it comes second, we're off by one; and so on. Sadly, the results were not as good as the ones from Assisted Texture Assignment.

Shadowgrounds Survivor level “marine01_wakeup”.
Objects of interest (that will be suggested later by the algorithm) are highlighted in red. Shadowgrounds Survivor level “marine02_road”.
Objects of interest (that will be suggested later by the algorithm) are highlighted in red. >

I have found a good metric for the neighborhood matching ², but the probe matching is not working as well as we hoped for. Most levels mainly consist of gray, brown or green colors and the occasional red, and especially the former make it hard to distinguish the environments of different objects. Moreover, small objects use fewer probes and thus have a lower "information resolution" but are used more frequently in a level than bigger objects.

All in all, I can say that using many small probes does not work as well for placing objects as for assigning textures, but nonetheless our algorithm can be useful for real-world cases. The neighborhood matching is fast anyhow and can easily be implemented in any level editor, and we optimized probe matching a lot: in the end, it would validate all 1400 objects in a large Shadowgrounds Survivor level in 14 seconds on a 6-core Intel Xeon X5650 machine, which is sufficiently fast for production usage as well.