Contact Surface Graph: A Data Structure for Efficiently Finding Contact-Rich Poses of Virtual Characters

Rapidly advancing 3D scanning technologies are enabling ready creation of augmented reality (AR) space from an arbitrary physical space. However, it remains a challenging task for an autonomous virtual character to create natural motion in the AR space purely based on the geometric information acquired by 3D scanners. Aiming to create contact-rich poses for virtual characters adaptive to the arbitrary shapes of objects, we present a graph-based data structure, Contact Surface (CS) Graph, that structuralizes the point cloud data and pre-computes important geometric information of objects with respect to generating virtual character´s poses. The CS graph supports building contact poses by matching a node representing an object´s contact surface to a virtual character´s body segment in real time. Tests for constructing CS graphs have been performed for a set of indoor objects including chairs and tables.