Structure discovery and navigation on shape data

As computing devices become more versatile, connected and portable, these devices are expanding into more and more aspects of our daily lives, creating an avalanching demand for interfaces and algorithms that can help make sense of vast amounts of shape data. Moreover, large amounts of shape data has created opportunities of being knowledge resources for creative inspiration, design augmentation, and design automation. However, this explosion in shape data presents unique challenges such as noise, multi-scale nature and diversity. For example, shapes represented as meshes are prone to a wide variety of noise factors: topological short circuits, surface holes, pose variations, variations in tessellation, missing features, scaling, as well as normal and shot noise. Further, shape data presents diverse variations which are difficult to be grasped for a human due to limited attention. As an illustration, shape retrieval systems have limited display space, which must be effectively utilized to display a variety of shapes that match the query. This thesis solves the problem of making sense of large unstructured shape data by developing algorithms that help search, organize, and explore data. The work can be divided into two parts depending on area of focus: Part I Organizing Shape Data and Part II Searching and Exploring Shape Data. Part I uses no human intervention. We utilize automatic algorithms to solve a specific problem of segmentation of meshes with various perturbations and multi scale features. Results show that our approach is significantly robust compared to existing methods. Using the interactive approach in Part II, we solve the problem of making sense of large amounts of shape data. We develop an interface which provides multiple pathways for exploration of shapes. Further, we develop a query specification system designed to improve exploratory search