GPU-based Anti-aliasing Of Free- Form Deformation

Free-Form Deformation (abbreviated as FFD) is a method for geometric model editing and soft object animation generation. It has been widely applied to various areas, such as computer animation, computer-aided design and engineering, computer vision, and scientific visualization, etc., since it is simple, intuitive and independent of model representation. Moreover, it has been integrated into many mainstream commercial 3D animation software.The deformation sampling is still an open problem in FFD. In the traditional FFDs, the deformation operations are performed on the sampled points of the model. Thus the deformation result mainly relies on the sampling density. As an alternative, accurate FFD deforms the planar polygons of the model as a set of triangular Bezier patches or trimmed tensor-product Bezier patches, where the deformation results are accurate in theory. It solves the deformation aliasing problems caused by low sampling density. However, the high computational costs make the real-time or interactive accurate FFD almost prohibited, which limits its utilities. Moreover, accurate FFD considers only the geometry of the original model, excluding its normal field. As a result, the deformed object is unsmooth. In the recent years, with rapid developments of tremendous comput-ing powers of general purpose GPU, the problems of efficiency and effect in accurate FFD are carefully considered, and a series of GPU based anti-aliasing methods of FFD are proposed in this thesis. The main contributions are summarized as follows:● A GPU based real-time accurate FFD is proposed, where the deformation results are represented in terms of trimmed tensor-product Bezier patches. By carefully analyzing the relationships among large amounts of B-spline volume evaluations, computations of tensor-product Bezier surfaces and triangulations of trimmed Bezier patches, a highly parallel algorithm is designed to execute all of the compu- tations mentioned above on GPU. Then, OpenGL Vertex Buffer Object is adopted to render the tessellation of the deformation result in order to avoid huge data transfer between CPU and GPU. Experimental results show that the proposed GPU algorithm is two orders of magnitude faster than its CPU counterpart. It can meet the real-time or interactive editing demands in accurate FFD.● The GPU based accurate FFD is further accelerated, where the deformation results are represented in terms of triangular Bezier patches. In the CPU implementations, the approach of accurate FFD in terms of trimmed tensor-product Bezier surfaces is much faster than the one in terms of triangular Bezier patches. After analyzing and exploiting the parallel computing capacities of modern GPUs, a more efficient accurate FFD is proposed. All the computations involved can be abstracted into two matrix multiplications which can be efficiently accomplished by the cuBLAS library on GPU. Experimental results show that the proposed algorithm is about 30% faster than the previous work. This research indicates that we can achieve higher acceleration ratio by exploiting the parallel capacities of modern GPGPU to implement traditional data-and computation-intensive geometric algorithms.● A GPU-based smooth FFD with sharp feature awareness is proposed. It approxi-mately deforms the geometry and the related normal field of the polygonal model as two sets of cubic triangular Bezier patches respectively. The deformed geom-etry is locally adjusted according to the deformed normal field to alleviate the unfairness caused by the knot box clipping. As a result, a visually plausible Gl smooth geometry and G0 deformed normal field are obtained in the smooth parts of the model; a G0 deformed geometry and G-1 deformed normal field are ob-tained in the sharp features of the model. Because all the computations are local, the algorithm can be performed fully in parallel on a GPU to meet the real-time and interactive demands.● An implicit surface editing method is proposed based on smooth FFD. FFD is independent of the representation of the model. Thus it can be applied to shape editing of implicit surfaces. First, the implicit surface is triangulated adaptively and the normal of each vertex is also computed. Then the smooth FFD is adopted to deform the triangulated implicit surface. The granularity of the triangulation is adaptively determined according to the implicit surface and the deformation space. Experimental results show that the proposed method is very efficient. The mesh refinement capacity of smooth FFD guarantees a good appearance defor-mation result even for a coarse triangulation of implicit surface.