Two highly effective content-adaptive methods for generating Delaunay mesh models of images, known as IID1 and IID2, are proposed. The methods repeatedly alternate between mesh simplification and refinement, based on the incremental/decremental mesh-generation framework of Adams, which has several free parameters. The effect of different choices of the framework's free parameters is studied, and the results are used to derive two mesh-generation methods that differ in computational complexity. The higher complexity IID2 method generates mesh models of superior reconstruction quality, while the lower complexity IID1 method trades mesh quality in return for a decrease in computational cost. Some of the contributions of our work include the recommendation of a better choice for the growth-schedule parameter of the framework, as well as the use of Floyd-Steinberg error diffusion for the initial-mesh selection. As part of our work, we evaluated the performance of the proposed methods using a data set of 50 images varying in type (e.g., photographic, computer generated, and medical), size and bit depth with multiple target mesh densities ranging from 0.125% to 4%. The experimental results show that our proposed methods perform extremely well, yielding high-quality image approximations in terms of peak-signal-to-noise ratio (PSNR) and subjective visual quality, at an equivalent or lower computational cost compared to other well known approaches such as the ID1, ID2, and IDDT methods of Adams, and the greedy point removal (GPR) scheme of Demaret and Iske. More specifically, the IID2 method outperforms the GPR scheme in terms of mesh quality by 0.2-1.0 dB with a 62-93% decrease in computational cost. Furthermore, the IID2 method yields meshes of similar quality to the ID2 method at a computational cost that is lower by 9-41%. The IID1 method provides improvements in mesh quality in 93% of the test cases by margins of 0.04-1.31 dB compared to the IDDT scheme, while having a similar complexity. Moreover, reductions in execution time of 4-59% are achieved compared to the ID1 method in 86% of the test cases. / Graduate / 0544, 0984, 0537 / marzouki@uvic.ca

The goal of this thesis is to use machine learning methods for datasets of scanned faces and to create a program that allows to explore and edit faces represented as triangle meshes with a number of controls. Firstly we had to reduce dimension of triangle meshes by PCA and then we tried to predict shape of meshes according to physical properties like weight, height, age and BMI. The modeled faces can be used in animation or games.

Many digital models used in entertainment, medical visualization, material science, architecture, Geographic Information Systems (GIS), and mechanical Computer Aided Design (CAD) are defined in terms of their boundaries. These boundaries are often approximated using triangle meshes. The complexity of models, which can be measured by triangle count, increases rapidly with the precision of scanning technologies and with the need for higher resolution. An increase in mesh complexity results in an increase of storage requirement, which in turn increases the frequency of disk access or cache misses during mesh processing, and hence decreases performance. For example, in a test application involving a mesh with 55 million triangles in a machine with 4GB of memory versus a machine with 1GB of memory, performance decreases by a factor of about 6000 because of memory thrashing. To help reduce memory thrashing, we focus on decreasing the average storage requirement per triangle measured in 32-bit integer references per triangle (rpt). This thesis covers compact connectivity representation for triangle meshes and discusses four data structures: 1. Sorted Opposite Table (SOT), which uses 3 rpt and has been extended to support tetrahedral meshes. 2. Sorted Quad (SQuad), which uses about 2 rpt and has been extended to support streaming. 3. Laced Ring (LR), which uses about 1 rpt and offers an excellent compromise between storage compactness and performance of mesh traversal operators. 4. Zipper, an extension of LR, which uses about 6 bits per triangle (equivalently 0.19 rpt), therefore is the most compact representation. The triangle mesh data structures proposed in this thesis support the standard set of mesh connectivity operators introduced by the previously proposed Corner Table at an amortized constant time complexity. They can be constructed in linear time and space from the Corner Table or any equivalent representation. If geometry is stored as 16-bit coordinates, using Zipper instead of the Corner Table increases the size of the mesh that can be stored in core memory by a factor of about 8.

Accurate computational representations of highly deformable surfaces are indispensable in the fields of computer animation, medical simulation, computer vision, digital modeling, and computational physics. The focus of this dissertation is on the animation of physics-based phenomena with highly detailed deformable surfaces represented by triangle meshes. We first present results from an algorithm that generates continuum mechanics animations with intricate surface features. This method combines a finite element method with a tetrahedral mesh generator and a high resolution surface mesh, and it is orders of magnitude more efficient than previous approaches. Next, we present an efficient solution for the challenging problem of computing topological changes in detailed dynamic surface meshes. We then introduce a new physics-inspired surface tracking algorithm that is capable of preserving arbitrarily thin features and reproducing realistic fine-scale topological changes like Rayleigh-Plateau instabilities. This physics-inspired surface tracking technique also opens the door for a unique coupling between surficial finite element methods and volumetric finite difference methods, in order to simulate liquid surface tension phenomena more efficiently than any previous method. Due to its dramatic increase in computational resolution and efficiency, this method yielded the first computer simulations of a fully developed crown splash with droplet pinch off.

Data-dependent triangulation (DDT) based mesh-generation schemes for image representation are studied. A flexible mesh-generation framework and a highly effective mesh-generation method that employs this framework are proposed. The proposed framework is derived from frameworks proposed by Rippa and Garland and Heckbert by making a number of key modifications to facilitate the development of much more effective mesh-generation methods. As the proposed framework has several free parameters, the effects of different choices of these parameters on mesh quality (both in terms of squared error and subjectively) are studied, leading to the recommendation of a particular set of choices for these parameters. A new mesh-generation method is then introduced that employs the proposed framework with these best parameter choices. Experimental results show our proposed mesh-generation method outperforms several competing approaches, namely, the DDT-based incremental scheme proposed by Garland and Heckbert, the COMPRESS scheme proposed by Rippa, and the adaptive thinning scheme proposed by Demaret and Iske. More specifically, in terms of PSNR, our proposed method was found to outperform these three schemes by median margins of 4.1 dB, 10.76 dB, and 0.83 dB, respectively. The subjective qualities of reconstructed images were also found to be correspondingly better. In terms of computational cost, our proposed method was found to be comparable to the schemes proposed by Garland and Heckbert and Rippa. Moreover, our proposed method requires only about 5 to 10% of the time of the scheme proposed by Demaret and Iske. In terms of memory cost, our proposed method was shown to require essentially same amount of memory as the schemes proposed by Garland and Heckbert and Rippa, and orders of magnitude (33 to 800 times) less memory than the scheme proposed by Demaret and Iske. / Graduate

Geometric morphometry serves biologists and anthropologists to rigorously and quantitatively describe shapes. These representations can be treated as a statistical sample, allowing the researchers to study its variability within groups and correlate it to other features. Geometric morphometry uses landmarks as the proxy for shape, with consistent semantics in each specimen. General triangle meshes do not have this property, and as such, semantically consistent remeshes must be created artificially. This thesis deals with the design of an algorithm that consistently resamples a set of surface models for the purpose of statistical analysis. Coherent point drift was employed to perform nonrigid registration, whose result is then used to generate a semantically consistent remeshes. This approach was successfully applied in a number of studies. As CPD is compute-intensive, we propose methods of accelerating both its initialization and processing phases. Also, an extension was introduced, that can map the deviation of the surfaces from perfect bilateral symmetry and analyze it in a sample, which is significant, among others, for quantification of pathologies. Manual trimming of the surfaces and merging datasets results in outlier regions in the individual surfaces and potentially large differences in their vertex...

Despite being the prefered approach for still-image compression for nearly a decade, wavelet-based coding for video has been slow to emerge, due primarily to the fact that the shift variance of the discrete wavelet transform hinders motion estimation and compensation crucial to modern video coders. Recently it has been recognized that a redundant, or overcomplete, wavelet transform is shift invariant and thus permits motion prediction in the wavelet domain. In this dissertation, other uses for the redundancy of overcomplete wavelet transforms in video coding are explored. First, it is demonstrated that the redundant-wavelet domain facilitates the placement of an irregular triangular mesh to video images, thereby exploiting transform redundancy to implement geometries for motion estimation and compensation more general than the traditional block structure widely employed. As the second contribution of this dissertation, a new form of multihypothesis prediction, redundant wavelet multihypothesis, is presented. This new approach to motion estimation and compensation produces motion predictions that are diverse in transform phase to increase prediction accuracy. Finally, it is demonstrated that the proposed redundant-wavelet strategies complement existing advanced video-coding techniques and produce significant performance improvements in a battery of experimental results.

[pt] Algoritmos para visualização interativa de terrenos são complexos e, ao mesmo tempo, de grande importância para muitas aplicações como jogos e planejamento de atividades sobre terrenos. Em função desta complexidade e importância, o tema merecido, na última década, muita atenção da comunidade de pesquisadores em Computação Gráfica e, conseqüentemente, muitas estratégias têm sido desenvolvidas. Entre as mais bem sucedidas estratégias, destacam-se os recentes trabalhos de Lindstrom e Pascucci. O algoritmo proposto por estes autores possui diversas implementações disponíveis na Internet e merece ser reavaliado. Esta dissertação faz esta re-avaliação através de uma implementação independente feita pela autora e testada sobre uma base de terrenos reais. Com o objetivo de tornar esta análise mais completa e dar suporte a algumas conclusões, resultados comparativos de outros algoritmos da área também são apresentados. / [en] Algorithms for the interactive visualization of terrains are very complex and, at the same time, of great importance to many applications, such as games and activity-planning over terrains. Due to such complexity and importance, in the past decade this subject has received great attention by researchers on Computer Graphics. As a consequence, a number of strategies have been developed. Among the most successful strategies, one can highlight recent works by Lindstrom and Pascucci. The algorithm proposed by these authors has various implementations available in the Internet and deserves to be reevaluated. The present work makes such reevaluation by means of an independent implementation developed by the author and tested over a base or real terrains. With the purpose of making this analysis more complete and to support some conclusions, comparative results with other algorithms in the area are also presented.

Необходимость в написании программы для расчета рассеянного поля телом вращения возникла в связи с неоднозначностью решения рассеянного поля таких объектов средствами электродинамического моделирования FEKO и Ansoft HFSS. В частности, в HFSS при повороте объекта (конуса) и соответствующем изменении характеристик падающей волны (направления распространения и поляризации) количество сегментов могло меняться более, чем на порядок. Отметим, что в качестве подхода к решению использовался метод физической оптики. Трудности расчета в FEKO вызваны по большей части ресурсами компьютера, а также сложностью последующей трактовки и математической обработки полученных результатов. Программа, описываемая в работе, позволит подойти к решению рассеянного на теле вращения поля более индивидуально и избежать таких неоднозначностей, что могут встречаться при расчетах в пакетах электродинамического моделирования. По результатам рассмотрения ряда задач сделан выбор в пользу метода физической оптики и его численной реализации на базе алгоритмов MATLAB. / The solution of diffraction from perfectly conducting convex solids of revolution is considered. The main aim is obtainment of an optimal approach for diffraction solution from large-scale solids. The implementation of a numerical solution of diffraction with physical optics method using MATLAB is considered. The realized program allows description of the solid of revolution with the analytic form equation of the curve. The possibility of curve description with a few functions defined on disjoint intervals is taken into consideration. The surface meshing with the required value is assured. The measure method of scattering characteristics is touched upon. The experimental results of the solid with three equations of curve are presented. The results of MATLAB modeling are compared with the experimental ones. The upgradability of mathematical modeling algorithms is proposed.

One of the common research goals in disciplines such as computer graphics and robotics is to understand the subtleties of human motion and develop tools for recreating natural and meaningful motion. Physical simulation of virtual human characters is a promising approach since it provides a testbed for developing and testing control strategies required to execute various human behaviors. Designing generic control algorithms for simulating a wide range of human activities, which can robustly adapt to varying physical environments, has remained a primary challenge. This dissertation introduces methods for generic and robust control of virtual characters in an interactive physical environment. Our approach is to use the information of the physical contacts between the character and her environment in the control design. We leverage high-level knowledge of the kinematics goals and the interaction with the surroundings to develop active control strategies that robustly adapt to variations in the physical scene. For synthesizing intentional motion requiring long-term planning, we exploit properties of the physical model for creating efficient and robust controllers in an interactive framework. The control design leverages the reference motion capture data and the contact information with the environment for interactive long-term planning. Finally, we propose a compact soft contact model for handling contacts for rigid body virtual characters. This model aims at improving the robustness of existing control methods without adding any complexity to the control design and opens up possibilities for new control algorithms to synthesize agile human motion.