Tiling motion patches

Simulating multiple character interaction is challenging because character actions must be carefully coordinated to align their spatial locations and synchronized with each other. We present an algorithm to create a dense crowd of virtual characters interacting with each other. The interaction may involve physical contacts, such as hand shaking, hugging, and carrying a heavy object collaboratively. We address the problem by collecting deformable motion patches, each of which describes an episode of multiple interacting characters, and tiling them spatially and temporally. The tiling of motion patches generates a seamless simulation of virtual characters interacting with each other in a nontrivial manner. Our tiling algorithm uses a combination of stochastic sampling and deterministic search to address the discrete and continuous aspects of the tiling problem. Our tiling algorithm made it possible to automatically generate highly complex animation of multiple interacting characters. We achieve the level of interaction complexity far beyond the current state of the art that animation techniques could generate, in terms of the diversity of human behaviors and the spatial/temporal density of interpersonal interactions.