Multiphase implicit modeling and variational blue noise sampling

Abstract

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.