Finding hyper-structure in space: spatial parsing in 3D

Abstract

Spatial parsers augment spatial hypermedia systems by letting the computer perceive the informal -but visually apparent - groupings formed by humans working with a spatial hypermedia tool. A number of research systems implementing 2D spatial parsing have been described in recent years. This paper extends spatial parsing to 3D and describes an implementation of a tailorable 3D spatial parser for the Topos system: a 3D information organization tool for use on desktops, interactive whiteboards and tables. The parser maintains a proximity graph of the heterogeneous 3D objects and applies structure experts and global repression and reinforcement techniques to this graph to find structures. A number of issues pertaining to 3D parsing as opposed to 2D parsing are discussed. The paper also presents a simple and efficient 2D parser for 3D scenes and compares it to the true 3D parser.