I will talk about Data-Driven Suggestions for Creativity Support in 3D Modeling. This is joint work with Vladlen Koltun.

The basic idea behind our research is that at every stage in the modeling process, we can automatically suggest creative options for extending the current shape. The user is, we hope, inspired by these suggestions to follow a particular path, and can then repeat the process for further inspiration.

I will introduce the project with a short overview. Given a simple query shape, we search a large database to locate shapes that have similar gross structure. Components of the retrieved models that do not appear in the query shape are suggested to the user as possible ways to extend the model. The user may interactively add some parts to the model and requery. The mocked up shape can then be exported to a high end geometric modeling tool for refinement and texturing.

A few nice things about data-driven suggestions: first, they support creative discovery in 3D modeling. A natural question is: can showing parts from prior models hinder, rather than help, the ideation of original models? We address this issue in more detail in the paper, but in brief, several authors have shown that creativity is indeed stimulated by tailored examples: greater creativity stems from greater access to solution components.

Second, our approach is entirely unsupervised: the user provides no guidance other than the query shape itself. No separate search is required, nor does the user need to indicate the location to augment or a rough indication of the shape of the parts being sought. This is critically important in a creativity support tool, since the user typically does not know what she wants when she asks the tool for suggestions. The most unexpected suggestions are often also the most valuable.

Thirdly, since the suggestions are drawn from a model library, they incorporate domain knowledge and are seldom completely meaningless or inappropriate. The domain knowledge operates at several levels, for instance suggested parts respect broad categories, such as aircraft parts for aircraft queries, and they also reflect, to some extent, what *type* of part is suitable for the current aircraft.

Our tool for prototyping shapes with data-driven suggestions, called InspireMe, looks like this. On the top left, in green, is the original query shape to which parts can be added. Suggestions drawn from the database for this shape are shown in red, with the complete source models indicated in wireframe. I will now show a brief video of interaction with the tool. A part may be selected and automatically positioned in the assembly, and the size and placement adjusted manually. Several such parts may be added, possibly with intermediate requerying, until a satisfactory mockup is obtained.

Our approach has the following components, which are linked to form a pipeline. You can think of the pipeline as taking as input the entire model library at one end, and outputting the most relevant suggestions for the given query shape to the user at the other end. The components in the pipeline are:
- Shape search for retrieving database models from which suggestions may be drawn
- Figuring out what parts are not present in the query and may be shown as suggestions
- Diversifying the suggestions to avoid repetition
- And, as demonstrated, a prototyping tool to present the suggestions to the user and to put everything together.

Let's go over these steps one by one. The first step in generating data-driven suggestions is shape search. The goal of shape search is to find library models that are roughly similar to the query, but contain extra parts, or replacement parts. These parts will be presented as suggestions. A fuselage of an aircraft, for example, should return several models of complete airplanes that contain wings, propellers, engines, landing gear, missiles, and so on, in addition of course to the fuselage itself. The suggestions will then consist of different wings, propellers and so on.

Now it's hard to compare shapes, represented as 3D meshes, directly. There are issues of topology, of compatible tessellations, of efficiency, and so on. Instead, the standard approach is to represent shapes by a short _signature_. These signatures are designed to be easily and efficiently compared -- in other words, they naturally form a metric space that corresponds to visual similarity of models. If the signatures of two shapes are similar, it's extremely probable that the shapes themselves are also similar.

We designed a signature called the D3 histogram that was suitable for our needs. Here's what the D3 signature of two shapes looks like. It's a 3-dimensional distribution, over the unit cube. The false colour of the models shows their local thickness -- thinner parts and red and thicker parts are green or blue. This thickness distribution, called the shape diameter function or SDF, forms part of the signature.

Let's look at the D3 histogram in a little more detail. The bins of the histogram are indexed by the distance between the pair of points, which forms one of the 3 dimensions, and the shape diameter, or SDF, of each point, which form the other two dimensions. Thus the signature is more discriminative than the SDF or pairwise distance histogram alone. To accommodate partial and approximate matches, we use pyramid matching with the histogram intersection kernel. Let me quickly explain what these are: the intersection of two histograms is simply a third histogram whose bin values are the pairwise minima of corresponding bins of the source histograms. In other words, it measures the degree of overlap of the histograms. Pyramid matching constructs downsampled versions of a histogram, like mipmapping, and compares two histograms by taking a weighted sum of their similarity at every resolution.

This combination --  D3 histogram, intersection kernel, and pyramid matching, is especially appropriate for data-driven suggestions since it is robust to local discrepancies of shape. Indeed, if a database model is a superset of the query, its similarity with the query is nearly 100 percent, assuming an appropriate sampling rate and normalization. This is illustrated in the figure on the screen, where the addition of an L-branch doesn't change the similarity of two beams. Thus, models with extra parts that may be used as suggestions are not thrown out just because they yield bad global matches. Of course, this very property makes the D3 histogram less suitable for *global* shape search.

The next step in our pipeline is the actual generation of suggestions from retrieved database models. The goal of suggestion generation is to figure out what parts of the database model are *not* present in the query. I'll illustrate how we achieve this: given a query shape, shown in green, and a database model, we compute a correspondence, or similarity score of each point on the database model to the query. In effect, we're asking whether the source point has a counterpart on the query, how well it's matched to the query. In the diagram blue indicates a good match and red indicates a poor match. Some parts of the database model are well matched to the query, and some parts remain unmatched. Using a prior segmentation of the database model, we suggest the parts that have a low average correspondence score. In this case, the wingtip stabilizers and landing gear constitute the suggestions.

Let's go over those steps again: given a query shape and a database model, we figure out what points on the database model correspond to the query, and which do not. I'll talk about this in a little more detail shortly. Then, we suggest the segments with a low average matching score.

How do we break up a library model into segments? We perform graph clustering on the shape diameter distribution, and then merge segments using an approximate convexity criterion to reduce oversegmentation. However, our technique for suggestion generation does *not* require a compatible segmentation of the query shape as well. Cosegmentations are quite hard to get right, and we wanted to avoid this potentially brittle step.

I said I'd talk a little bit about how we compute the similarity scores between library and query models, so here goes. The first thing to note is that we wanted to avoid having to explicitly align the two shapes. Instead, we use an approach based on feature descriptors at surface points. This descriptor, at a point, concatenates a spin image with a histogram of SDF and distance of neighboring points. As for shape search, we use histogram intersection and pyramid matching to handle approximate and partial matches.

Now, figuring out if a point on the database model has a counterpart on the query shape or not is a high-dimensional nearest neighbor problem. The standard approach to accelerate such queries is locality-sensitive hashing, or LSH. Unfortunately, we run into a small problem here because pyramid matching on a histogram intersection kernel is not a suitable metric for standard LSH. Mercifully (no puns intended), it is nevertheless a Mercer kernel, and we can exploit the recent work of Kulis and Grauman that extends LSH to Mercer kernels (without incurring the dimension inflation associated with expressing the metric as an inner product). This provides significantly increased performance.

Lastly, I would like to talk about diversification of suggested parts to provide a variety of options to the user. The problem is that large databases contain many shapes, or parts of shapes, that are extremely similar. If one such shape is a highly ranked source of suggestions, so are its twins, which leads to a bunch of suggestions that look exactly the same. To avoid this sort of repetition, we use the Maximal Marginal Relevance algorithm of Carbonell and Goldstein, which reorders a ranked list, based on both the original rank and pairwise similarity of elements, so that runs of similar parts are reduced. This provides a range of creative options to the user within the first few suggestions.

I've already demonstrated the interface for the InspireMe prototyping tool, so this seems like a good time to look at some results. First, here's a furniture query, in green, and the corresponding top 4 suggestions, shown in red… Here's an aircraft… an organic shape… and another [talk about what's being shown]. Please note that all these suggestions are drawn from the *same* database -- we did not categorize the database based on query type, and indeed the "type" of the query is not indicated to the program in any way. Further, because the user did not have to indicate any search terms beyond the query shape itself, the suggestions cover a greater range of creative possibilities.

Next, here is a stress test with a very ambiguous query shape -- a long tapering rod. We were curious to see what the technique would suggest for this shape. You can see the range of suggestions generated -- [talk about them]. This also gives some idea of the variety of models in our library.

We conducted some informal studies with users to evaluate the performance of data-driven suggestions. We invited 12 artists to sit for 2-hour sessions and work on two fairly vaguely specified tasks: construct a fantastical creature, and a futuristic aircraft, to be used in the next edition of Avatar. The artists were free to interface between our tool and a commercial modeling package for fine-tuning.

Here are some of the results for the creatures task. The top row shows the simple query shapes the artists started with, the middle row shows the mockups they constructed with suggestions from InspireMe, and the bottom row shows the final textured models they developed from the mockups. All the parts in the mockups that are not in the query shapes come from data-driven suggestions.

And here are the results from the aircraft task. Again, all novel parts in the mockups were suggested by InspireMe.

What would we really like to see in future work? First of all, it would be wonderful to see more research in tools for supporting open-ended design. We feel data-driven techniques are especially effective for this purpose since many problems in this domain are fundamentally ill-constrained and can be resolved only by analogy with prior solutions.

Second, our technique has the limitation that it is purely geometric, and does not utilize semantic information that encodes meaning or function. There has been recent research on automatically inferring semantic tags for shapes and their subparts -- this work has been inspired by prior results in computer vision. We think this is a very exciting direction for new research in geometry processing.

Lastly, large, publicly available databases of decent 3D models are rare. Data-driven content creation depends, not surprisingly, on data, and we need more such resources to augment the few libraries that exist. Note that the problem is not just one of access but of distribution -- if we want people to use the tools that we build, we need to give them the data that drives these tools. As far as commercial libraries are concerned, distribution rights for doing so can be prohibitively expensive, even if the tool is noncommercial. There has been good work done by, e.g., the Princeton Shape Benchmark, AIM@Shape, and the Architecture Benchmark, and this needs to be taken further.

I will conclude with some spins of our user-generated models, for your delectation. Note again that all novel parts are from automatically generated data-driven suggestions. Thank you.