Algorithms Seminar

Speaker bio:

Joe Marks grew up in Dublin, Ireland, before coming to the U.S. for college. He earned a Ph.D. in Computer Science from Harvard Univeristy in 1991. He has worked previously at Bolt Beranek and Newman and Digital's Cambridge Research Laboratory. His main areas of interest are computer graphics, user interfaces, and heuristic optimization. His current projects concern the development of novel tangible and perceptual user interfaces for design and modeling tasks.

Abstract:

Few people know how to use graphics modeling packages, but everyone can build things out of blocks and clay. Starting from this premise, and with the goal of developing accessible modeling tools for building and populating virtual worlds, we have developed two novel object-modeling systems.

The first system consists of Lego-like building blocks that self-describe the geometric structures into which they are assembled. In contrast to previously reported self-describing construction kits, our approach has advantages of scalability, configurability, and interactivity. Each building block contains a microcontroller that can communicate with the other microcontrollers in the blocks to which it is physically connected. The blocks in an assembled structure use a distributed algorithm to first discover how they are connected to their immediate neighbors. This information is then relayed from block to block --- each of our block structures is essentially a self-configuring, store-and-forward computer network --- until it reaches the host computer. From the block connectivity data that it collects, and knowledge of the shape of each block, the host computer can recover the geometric structure of the assembled blocks. The structure can then be rendered in various styles, ranging from a literal rendition in which blocks look like Lego bricks, to decorative interpretations in which structural elements are identified automatically and augmented appropriately. Once rendered, the virtual models are available for viewing and manipulation by the user. Through the use of embedded sensors and transducers, the user can also interact with the virtual world through the block model.

The second system uses customized variants of known computer-vision techniques to recognize and parse clay models of common toy-like objects, such as people, animals, trees, houses, cars, boats, etc. Using a single calibrated camera to capture images of a clay model on a rotary table, we recover a volumetric scan of the model. The scanned volume is then matched against a small set of object templates. This process allows us to both classify the clay model and to identify its constituent parts. Using this information we can, for example, recognize and parse a clay model of an ambulatory object, and then animate it appropriately in a virtual world.

Joint work with: D. Anderson, J. Frankel, A. Agarwala, P. Beardsley, J. Hodgins, D. Leigh, K. Ryall, E. Sullivan, and J. Yedidia.