Electronic Theses and Dissertations

Date of Award


Document Type


Degree Name

Ph.D. in Engineering Science


Computer and Information Science

First Advisor

Yixin Chen

Second Advisor

Jianxia Xue

Third Advisor

Dawn Wilkins

Relational Format



Visual 3D data are of interest to a number of fields: medical professionals, game designers, graphic designers, and (in the interest of this paper) ichthyologists interested in the taxonomy of fish. Since the release of the Kinect for the Microsoft XBox, game designers have been interested in using the 3D data returned by the device to understand human movement and translate that movement into an interface with which to interact with game systems. In the medical field, researchers must use computer vision tools to navigate through the data found in CT scans and MRI scans. These tools must segment images into the parts that are relevant to researchers and account for noise related to the scanning process all while ignoring other types of noise such as foreign elements in the body that might indicate signs of illness. 3D point cloud data represents some unique challenges. Consider an object scanned with a laser scanner. The scanner returns the surface points of the object, but nothing more. Using the tool Qhull, a researcher can quickly compute the convex hull of an object (which is an interesting challenge in itself), but the convex hull (obviously) leaves out any description of an object's concave features. Several algorithms have been proposed to illustrate an object's complete features based on unorganized 3D point cloud data as accurately as possible, most notably Boissonnat's tetrahedral culling algorithm and The Power Crust algorithm. We introduce a new approach to the area partitioning problem that takes into consideration these algorithms' strengths and weaknesses. In this paper we propose a methodology for approximating a shape's solid geometry using the unorganized 3D point cloud data of that shape primarily by utilizing localized principal component analysis information. Our model accounts for three comissues that arise in the scanning of 3D objects: noise in surface points, poorly sampled surface area, and narrow corners. We explore each of these areas of concern and outline our approach to each. Our technique uses a growing algorithm that labels points as it progresses and uses those labels with a simple priority queue. We found that our approach works especially well for approximating surfaces under the condition where a local surface is poorly sampled (i.e a significant hole is present in the point cloud). We then turn to study the medial axis of a shape for the purposes of `unfolding' that structure. Our approach uses a ridge formulation based on the spatial depth statistic to create the medial axis. We conclude the paper with visual results of our technique.


Emphasis: Computer Science



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.