UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Voronoi ball models for computational shape applications Tam, Roger C.


This thesis evaluates the suitability of Voronoi ball models (VBMs) as a multipurpose shape representation for applications in computer graphics, scientific visualization, and computer vision. The effectiveness of VBMs is judged with respect to six key properties, namely stability, flexibility, accuracy, complexity, efficiency, and intuitiveness. These properties have a significant impact on the range of applicability of a computational shape model. The ability of VBMs to support a number of core shape-driven operations, in particular shape extraction, simplification, matching, interpolation, manipulation, and surface reconstruction, is examined by determining the strength of the key properties in the representation. The general approach is to use VBMs in a number of representative applications, each requiring several of the shape operations being considered. These applications include image matching and interpolation, shape model extraction from image data, two and three-dimensional shape simplification, and polygonal surface reconstruction. The performance of VBMs in these applications is indicative of the extent to which each key property is present. The results of the experiments are very positive. They indicate that a VBM-based shape similarity measure can be effectively applied to quantify 2D shape differences and solve the 2D/3D shape correspondence problem. The findings also show that the VBM and the medial axis can be used together to take advantage of their complementary properties; the VBM gives the medial axis greater stability, while the axis adds connectivity and topological information to the VBM representation. The preservation of the topology of 3D shapes during processing is a particularly strong contribution of the thesis. In addition, the medial axis is shown to enhance the capabilities of the VBM for performing shape simplification and partitioning an object into parts. The experimental results also reveal that VBMs can be effectively used to extract shape information from images and reconstruct polygonal surfaces from point sample data. The primary conclusion made in this thesis is that VBMs are demonstrably capable of supporting a wide variety of shape operations. Additional research is warranted to further exploit the potential of the representation.

Item Media

Item Citations and Data


For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.