Return to search

Multiphase implicit modeling and variational blue noise sampling

This thesis investigates two fundamental problems in computer graphics including object modeling and sampling. In object modeling problems, implicit function is widely used. It has a wide range of applications in entertainment, engineering and medical imaging. A standard two-phase implicit function only represents the interior and exterior of a single object. To facilitate solid modeling of heterogeneous objects with multiple internal regions, object-space multiphase implicit functions are much desired. Multiphase implicit functions have much potential in modeling natural organisms, heterogeneous mechanical parts and anatomical atlases. In the first part of this thesis, we introduce a novel class of object-space multiphase implicit functions that are capable of accurately and compactly representing objects with multiple internal regions. Our proposed multiphase implicit functions facilitate true object-space geometric modeling of heterogeneous objects with non-manifold features. We present multiple methods to create object-space multiphase implicit functions from existing data, including meshes and segmented medical images. Our algorithms are inspired by machine learning algorithms for training multicategory max-margin classifiers. Comparisons demonstrate that our method achieves an error rate one order of magnitude smaller than alternative techniques.

In the second part of this thesis we study another important problem, sampling, which is a core process for numerous graphics applications including rendering, non-photorealistic image stippling, imaging, and geometry processing. Among all the existing sampling algorithms, blue noise point sampling is especially popular because it can generate spatial uniform point distribution with no aliasing artifacts. We present a new and versatile variational framework for generating point distributions with high-quality blue noise characteristics while precisely adapting to given density functions. Different from previous approaches based on discrete settings of capacity-constrained Voronoi tessellation, we cast the blue noise sampling generation as a variational problem with continuous settings. Based on an accurate evaluation of the gradient of an energy function, an efficient optimization is developed which delivers significantly faster performance than the previous optimization-based methods. Our framework can easily be extended to generating blue noise point samples on manifold surfaces and for multi-class sampling. The optimization formulation also allows us to naturally deal with dynamic domains, such as deformable surfaces, and to yield blue noise samplings with temporal coherence. We present experimental results to validate the efficacy of our variational framework.

A core step in our blue noise sampling algorithm is to compute the Voronoi diagram. This is a fundamental geometry structure which has numerous applications including computer animation, pattern recognition and so on. Efficient computation of Voronoi diagram is critical for improving the performance of these applications. Thus, we also study the problem of using the GPU to compute the generalized Voronoi diagram (GVD) for higher-order sites, such as line segments and curves. We propose an algorithm that can compute considerately more accurate GVD with much less memory than using the existing algorithms, with only moderate increase of the running time. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

Identiferoai:union.ndltd.org:HKU/oai:hub.hku.hk:10722/197095
Date January 2013
CreatorsYuan, Zhan
ContributorsWang, WP, Yu, Y
PublisherThe University of Hong Kong (Pokfulam, Hong Kong)
Source SetsHong Kong University Theses
LanguageEnglish
Detected LanguageEnglish
TypePG_Thesis
RightsThe author retains all proprietary rights, (such as patent rights) and the right to use in future works., Creative Commons: Attribution 3.0 Hong Kong License
RelationHKU Theses Online (HKUTO)

Page generated in 0.0015 seconds