Navigation mesh is a form of representation of a virtual environment, which allows effective navigation of intelligent virtual agents. This thesis deals with the development of a navigation mesh for the intelligent virtual agents in the environment of the computer game Unreal Tournament 2004. Before the development of the navigation mesh, the navigation graph was the only available representation of the environment that the agents could use for navigation. The navigation graph however provides only limited information about the environment. With the use of the navigation mesh the agents are able to navigate in the environment faster and over shorter paths. Creation of the navigation mesh from the environment's geometry extracted from Unreal Tournament 2004 map files is a part of the thesis. Finally, a new navigation module for Pogamut 3 - a platform that allows creation and controlling of intelligent virtual agents, is implemented. The new navigation module consists of the navigation mesh and a set of navigation algorithms Powered by TCPDF (www.tcpdf.org)

Dans le domaine de l’informatique graphique, les données tridimensionnelles, généralement représentées par des maillages triangulaires, sont employées dans une grande variété d’applications (par exemple, le lissage, la compression, le remaillage, la simplification, le rendu, etc.). Cependant, ces procédés introduisent inévitablement des artefacts qui altèrent la qualité visuelle des données 3D rendues. Ainsi, afin de guider perceptuellement les algorithmes de traitement, il y a un besoin croissant d'évaluations subjectives et objectives de la qualité visuelle à la fois performantes et adaptées, pour évaluer et prédire les artefacts visuels. Dans cette thèse, nous présentons d'abord une étude exhaustive sur les différentes sources d'artefacts associés aux données numériques graphiques, ainsi que l’évaluation objective et subjective de la qualité visuelle des artefacts. Ensuite, nous introduisons une nouvelle étude sur la qualité subjective conçue sur la base de l’évaluations de la visibilité locale des artefacts géométriques, dans laquelle il a été demandé à des observateurs de marquer les zones de maillages 3D qui contiennent des distorsions visibles. Les cartes de distorsion visuelle collectées sont utilisées pour illustrer plusieurs fonctionnalités perceptuelles du système visuel humain (HVS), et servent de vérité-terrain pour évaluer les performances des attributs et des mesures géométriques bien connus pour prédire la visibilité locale des distorsions. Notre deuxième étude vise à évaluer la qualité visuelle de modèles 3D texturés, subjectivement et objectivement. Pour atteindre ces objectifs, nous avons introduit 136 modèles traités avec à la fois des distorsions géométriques et de texture, mené une expérience subjective de comparaison par paires, et invité 101 sujets pour évaluer les qualités visuelles des modèles à travers deux protocoles de rendu. Motivés par les opinions subjectives collectées, nous proposons deux mesures de qualité visuelle objective pour les maillages texturés, en se fondant sur les combinaisons optimales des mesures de qualité issues de la géométrie et de la texture. Ces mesures de perception proposées surpassent leurs homologues en termes de corrélation avec le jugement humain. / In computer graphics realm, three-dimensional graphical data, generally represented by triangular meshes, have become commonplace, and are deployed in a variety of application processes (e.g., smoothing, compression, remeshing, simplification, rendering, etc.). However, these processes inevitably introduce artifacts, altering the visual quality of the rendered 3D data. Thus, in order to perceptually drive the processing algorithms, there is an increasing need for efficient and effective subjective and objective visual quality assessments to evaluate and predict the visual artifacts. In this thesis, we first present a comprehensive survey on different sources of artifacts in digital graphics, and current objective and subjective visual quality assessments of the artifacts. Then, we introduce a newly designed subjective quality study based on evaluations of the local visibility of geometric artifacts, in which observers were asked to mark areas of 3D meshes that contain noticeable distortions. The collected perceived distortion maps are used to illustrate several perceptual functionalities of the human visual system (HVS), and serve as ground-truth to evaluate the performances of well-known geometric attributes and metrics for predicting the local visibility of distortions. Our second study aims to evaluate the visual quality of texture mapped 3D model subjectively and objectively. To achieve these goals, we introduced 136 processed models with both geometric and texture distortions, conducted a paired-comparison subjective experiment, and invited 101 subjects to evaluate the visual qualities of the models under two rendering protocols. Driven by the collected subjective opinions, we propose two objective visual quality metrics for textured meshes, relying on the optimal combinations of geometry and texture quality measures. These proposed perceptual metrics outperform their counterparts in term of the correlation with the human judgment.

This thesis relates to research and development in the field of 3D mesh data for computer graphics. A review of existing storage and manipulation techniques for mesh data is given followed by a framework for mesh editing. The proposed framework combines complex mesh editing techniques, automatic level of detail generation and mesh compression for storage. These methods work coherently due to the underlying data structure. The problem of storing and manipulating data for 3D models is a highly researched field. Models are usually represented by sparse mesh data which consists of vertex position information, the connectivity information to generate faces from those vertices, surface normal data and texture coordinate information. This sparse data is sent to the graphics hardware for rendering but must be manipulated on the CPU. The proposed framework is based upon geometry images and is designed to store and manipulate the mesh data entirely on the graphics hardware. By utilizing the highly parallel nature of current graphics hardware and new hardware features, new levels of interactivity with large meshes can be gained. Automatic level of detail rendering can be used to allow models upwards of 2 million polygons to be manipulated in real time while viewing a lower level of detail. Through the use of pixels shaders the high detail is preserved in the surface normals while geometric detail is reduced. A compression scheme is then introduced which utilizes the regular structure of the geometry image to compress the floating point data. A number of existing compression schemes are compared as well as custom bit packing. This is a TIF funded project which is partnered with Unlimited Realities, a Palmerston North software development company. The project was to design a system to create, manipulate and store 3D meshes in a compressed and easy to manipulate manner. The goal is to create the underlying technologies to allow for a 3D modelling system to become integrated into the Umajin engine, not to create a user interface/stand alone modelling program. The Umajin engine is a 3D engine created by Unlimited Realities which has a strong focus on multimedia. More information on the Umajin engine can be found at www.umajin.com. In this project we propose a method which gives the user the ability to model with the high level of detail found in packages aimed at creating offline renders but create models which are designed for real time rendering.

The aims of the studies was to evaluate the short and long term effects on the development of parastomal hernia and stoma complications of a prophylactic prosthetic mesh placed in a sublay position at the index operation.  Also the purpose was to validate a definition of parastomal hernia at clinical examination and a method and a definition of parastomal hernia at CT-scan. In the first two studies 27 patients were randomized to a conventional stoma or to a stoma with the addition of a partly absorbable low weight large pore mesh in sublay position. Patients were examined after one and five years.  After five years the rate of parastomal hernia was 80% with a conventional stoma and 14% with the addition of a mesh.  A prophylactic mesh did not increase the rate of complications. In the third study a prophylactic mesh was intended at stoma formation in 93 consecutive patients in routine surgery. In 75 patients provided with a mesh the rate of parastomal hernia after one year was 13%. Complication rates were not increased in 19 severely contaminated wounds. In the fourth study 27 patients with ostomies were examined by tree surgeons and parastomal hernia was defined as any protrusion in the vicinity of the stoma. CT-scans with patients examined in the supine and prone positions were assessed by three radiologists. Herniation was then defined as any intra abdominal content protruding beyond peritoneum or the presence of a hernia sac. Kappa was 0.85 for surgeons and 0.85 for radiologists with CT-scan in the prone position. Kappa was 0.80 for surgeons and radiologists collectively, with CT-scan in the prone position. Four parastomal hernias detected at CT-scan in the prone position could not be detected in the supine position. A parastomal hernia diagnosed at clinical examination was always detected at CT-scan in the prone position. Conclusions: A prophylactic mesh placed in a sublay position at the index operation reduces the rate of parastomal hernia without increasing the rate of complications. Parastomal hernia should at clinical examination be defined as any protrusion in the vicinity of the stoma with the patient straining in the supine and erect positions.  At CT-scan, with the patient examined in the prone position, herniation should be defined as any intra abdominal content protruding beyond peritoneum or the presence of a hernia sac. / Embargo, publiceras 2011-05-01

Multi-core architectures are present throughout a large selection of computing devices from cell phones to super-computers. Parallel applications running on these devices solve bigger problems in a shorter time. Writing those applications is a difficult task for programmers. They need to deal with low-level parallel mechanisms such as data distribution, inter-processor communication, and task placement. The goal of the Standard Template Adaptive Parallel Library (STAPL) is to provide a generic high-level framework to develop parallel applications. One of the first steps of a parallel application is to partition and distribute the data throughout the system. An important data structure for parallel applications to store large amounts of data and model many types of relations is the graph. A mesh, which is a special type of graph, is often used to model a spatial domain in scientific applications. Graph and mesh partitioning has many applications such as VLSI circuit design, parallel task scheduling, and data distribution. Data distribution, significantly impacts the performance of a parallel application. In this thesis, we introduce the STAPL Parallel Graph Partitioner Framework. This framework provides a generic infrastructure to partition arbitrary graphs and meshes and to build customized partitioners. It includes the state of the art parallel k-way multilevel scheme to partition arbitrary graphs, a parallel mesh partitioner with parameterized partition shape, and a customized partitioner used for discrete ordinates particle transport computations. This framework is also part of a generic library, STAPL, allowing the partitioning of the data and development of the whole parallel application to be done in the same environment. We show the user-friendly interface of the framework and its scalability for partitioning different mesh and graph benchmarks on a Cray XE6 system. We also highlight the performance of our customized unstructured mesh partitioner for a discrete ordinates particle transport code. The developed columnar decompositions significantly reduce the execution time of simultaneous sweeps on unstructured meshes.

Considerações de informação perceptual têm ganhado espaço rapidamente em pesquisas referentes a representação, análise e exibição de malhas. Estudos com usuários, eye tracking e outras técnicas são capazes de fornecer informações cada vez mais úteis para sistemas voltados a usuário, que formam a maioria das aplicações em computação gráfica. Neste trabalho nós expandimos sobre o conceito de Saliência de Malhas — uma medida automática de importância visual para malhas de triângulos baseada em modelos de atenção humana em baixo nível — melhorando, extendendo e realizando integração com diferentes aplicações. Nós extendemos o conceito de Saliência de Malhas para englobar objetos deformáveis, mostrando como um mapa de saliência em nível de vértice pode ser construído capturando corretamente regiões de alta importância perceptual através de um conjunto de poses ou deformações. Nós definimos saliência multi-pose como um agregado multi-escala de valores de curvatura sobre uma vizinhança localmente estável, em conjunto com deformações desta vizinhança em múltiplas poses. Nós substituímos distância Euclideana por geodésica, assim fornecendo melhores estimativas de vizinhança local. Resultados mostram que saliência multi-pose gera resultados visualmente mais interessantes em simplificações quando comparado à saliência em uma única pose. Nós também aplicamos saliência de malhas ao problema de segmentação e rendering dependente de ponto de vista, introduzindo uma técnica para segmentação que particiona um objeto em um conjunto de clusters, cada um englobando um grupo de características localmente interessantes. Saliência de malhas é incorporada em um framework para clustering propagativo, guiando seleção de pontos de partida para clusters e custos de propagação de faces, levando a uma convergência de clusters ao redor de características perceptualmente importantes. Nós comparamos nossa técnica com diferentes métodos automáticos para segmentação, mostrando que ela fornece segmentação melhor ou comparável sem necessidade de intervenção do usuário. Uma vez que o algoritmo de segmentação proposto é especialmente aplicável a rendering multi-resolução, nós ilustramos uma aplicação do mesmo através de um sistema de rendering baseado em ponto de vista guiado por saliência, alcançando melhorias consideráveis em framerate com muito pouca perda de qualidade visual. / Considerations on perceptual information are quickly gaining importance in mesh representation, analysis and display research. User studies, eye tracking and other techniques are able to provide ever more useful insights for many user-centric systems, which form the bulk of computer graphics applications. In this work we build upon the concept of Mesh Saliency — an automatic measure of visual importance for triangle meshes based on models of low-level human visual attention—improving, extending and integrating it with different applications. We extend the concept of Mesh Saliency to encompass deformable objects, showing how a vertex-level saliency map can be constructed that accurately captures the regions of high perceptual importance over a range of mesh poses or deformations. We define multipose saliency as a multi-scale aggregate of curvature values over a locally stable vertex neighborhood together with deformations over multiple poses. We replace the use of the Euclidean distance by geodesic distance thereby providing superior estimates of the local neighborhood. Results show that multi-pose saliency generates more visually appealing mesh simplifications when compared to a single-pose mesh saliency. We also apply Mesh Saliency to the problem of mesh segmentation and view-dependent rendering, introducing a technique for segmentation that partitions an object into a set of face clusters, each encompassing a group of locally interesting features. Mesh Saliency is incorporated in a propagative mesh clustering framework, guiding cluster seed selection and triangle propagation costs and leading to a convergence of face clusters around perceptually important features. We compare our technique with different fully automatic segmentation algorithms, showing that it provides similar or better segmentation without the need for user input. Since the proposed clustering algorithm is specially suitable for multi-resolution rendering, we illustrate application of our clustering results through a saliency-guided view-dependent rendering system, achieving significant framerate increases with little loss of visual detail.

Apresenta-se uma formulação de adaptação de malha para problemas com grandes deformações. A formulação Arbitrária Lagrangeana-Euleraina (ALE) permite manter a qualidade dos elementos finitos durante o processo de cálculo através de rearranjo ou movimento de malha independente do movimento material. Nas formulações Lagrangeanas a malha fica “colada” ao corpo durante toda a análise, logo quando este sofre grandes deformações diferenciais o mesmo se reproduz numa malha distorcida. A formulação ALE desacoplada consta de dois passos: O passo Lagrangeano onde são aplicados os incrementos de carga, a malha permanece “colada” à matéria durante a análise. E cada certo “tempo” o passo Euleriano onde “descola-se” a malha da matéria e efetua-se o movimento de malha que se ajusta melhor ao corpo deformado. São apresentados assim métodos de realocação da malha e transferência ou atualização das variáveis necessárias para, depois do passo Euleriano, continuar a análise com a nova malha sem grandes distorções dos elementos. Os problemas de grandes deformações e deslocamentos são acompanhados de não linearidades físicas e geométricas, assim, são abordados os métodos para o tratamento destas não linearidades. Trabalha-se com o elemento hexaédrico tri-linear com integração reduzida e controle dos modos espúrios que tem demostrado um bom comportamento frente a grandes não linearidades geométricas assim como para as não linearidades físicas. A formulação ALE tem ganhando seu espaço na mecânica dos sólidos, em problemas de conformação mecânica e impacto, devido às grandes deformações e na última década está abrindo-se passo na área da geomecânica tratando problemas recalque e penetração de fundações em solos. / This work presents remeshing techniques for finite element simulation and investigates their performance for large deformation problems. Lagrangian formulation generally results in excessive mesh distortion owing to its attachment to the material. Meanwhile, the Lagrangian- Eulerian (ALE) formulation alouds to keep the finite element quality through the arbitrarily rearrangement or movement of the mesh, to optimize the element’s shape. The decoupled Arbitrary Lagrangian-Eulerian approach consists in a sequence of Lagrangian and Eulerian steps. The mesh is “coupled” to the material during the Lagrangian steps. From step to step, mesh is decoupled from the system material (Eulerian step), the nodes corresponding to free boundaries are relocated using an analytical approach, remeshing is performed and finally the state variables are remapped. Rearrangements methods for the element’s node are presented, as well as the variables remapping algorithms at the new quadrature points, in order to continue with the finite element analysis without altering the element topology of the original mesh. Special attention is given to methods dealing with geometric and physical nonlinearities. A trilinear hexahedral element is used with reduced integration and hourglass control. This combination has shown well behavior in front of large geometric and physical nonlinearities. ALE formulation field has considerably grown in geotechnical research, especially in impact and mechanical extrusion problems. Over the last decade, geomechanic is dealing with settlement problems and foundation penetration in soils.

To decrease the rendering time of a mesh, Level of Detail can be generated by reducing the number of polygons based on some geometrical error. While this works well for most meshes, it is not suitable for meshes with an associated texture atlas. By iteratively collapsing edges based on an extended version of Quadric Error Metric taking both spatial and texture coordinates into account, textured meshes can also be simplified. Results show that constraining edge collapses in the seams of a mesh give poor geometrical appearance when it is reduced to a few polygons. By allowing seam edge collapses and by using a pull-push algorithm to fill areas located outside the seam borders of the texture atlas, the appearance of the mesh is better preserved.

Considerações de informação perceptual têm ganhado espaço rapidamente em pesquisas referentes a representação, análise e exibição de malhas. Estudos com usuários, eye tracking e outras técnicas são capazes de fornecer informações cada vez mais úteis para sistemas voltados a usuário, que formam a maioria das aplicações em computação gráfica. Neste trabalho nós expandimos sobre o conceito de Saliência de Malhas — uma medida automática de importância visual para malhas de triângulos baseada em modelos de atenção humana em baixo nível — melhorando, extendendo e realizando integração com diferentes aplicações. Nós extendemos o conceito de Saliência de Malhas para englobar objetos deformáveis, mostrando como um mapa de saliência em nível de vértice pode ser construído capturando corretamente regiões de alta importância perceptual através de um conjunto de poses ou deformações. Nós definimos saliência multi-pose como um agregado multi-escala de valores de curvatura sobre uma vizinhança localmente estável, em conjunto com deformações desta vizinhança em múltiplas poses. Nós substituímos distância Euclideana por geodésica, assim fornecendo melhores estimativas de vizinhança local. Resultados mostram que saliência multi-pose gera resultados visualmente mais interessantes em simplificações quando comparado à saliência em uma única pose. Nós também aplicamos saliência de malhas ao problema de segmentação e rendering dependente de ponto de vista, introduzindo uma técnica para segmentação que particiona um objeto em um conjunto de clusters, cada um englobando um grupo de características localmente interessantes. Saliência de malhas é incorporada em um framework para clustering propagativo, guiando seleção de pontos de partida para clusters e custos de propagação de faces, levando a uma convergência de clusters ao redor de características perceptualmente importantes. Nós comparamos nossa técnica com diferentes métodos automáticos para segmentação, mostrando que ela fornece segmentação melhor ou comparável sem necessidade de intervenção do usuário. Uma vez que o algoritmo de segmentação proposto é especialmente aplicável a rendering multi-resolução, nós ilustramos uma aplicação do mesmo através de um sistema de rendering baseado em ponto de vista guiado por saliência, alcançando melhorias consideráveis em framerate com muito pouca perda de qualidade visual. / Considerations on perceptual information are quickly gaining importance in mesh representation, analysis and display research. User studies, eye tracking and other techniques are able to provide ever more useful insights for many user-centric systems, which form the bulk of computer graphics applications. In this work we build upon the concept of Mesh Saliency — an automatic measure of visual importance for triangle meshes based on models of low-level human visual attention—improving, extending and integrating it with different applications. We extend the concept of Mesh Saliency to encompass deformable objects, showing how a vertex-level saliency map can be constructed that accurately captures the regions of high perceptual importance over a range of mesh poses or deformations. We define multipose saliency as a multi-scale aggregate of curvature values over a locally stable vertex neighborhood together with deformations over multiple poses. We replace the use of the Euclidean distance by geodesic distance thereby providing superior estimates of the local neighborhood. Results show that multi-pose saliency generates more visually appealing mesh simplifications when compared to a single-pose mesh saliency. We also apply Mesh Saliency to the problem of mesh segmentation and view-dependent rendering, introducing a technique for segmentation that partitions an object into a set of face clusters, each encompassing a group of locally interesting features. Mesh Saliency is incorporated in a propagative mesh clustering framework, guiding cluster seed selection and triangle propagation costs and leading to a convergence of face clusters around perceptually important features. We compare our technique with different fully automatic segmentation algorithms, showing that it provides similar or better segmentation without the need for user input. Since the proposed clustering algorithm is specially suitable for multi-resolution rendering, we illustrate application of our clustering results through a saliency-guided view-dependent rendering system, achieving significant framerate increases with little loss of visual detail.

Apresenta-se uma formulação de adaptação de malha para problemas com grandes deformações. A formulação Arbitrária Lagrangeana-Euleraina (ALE) permite manter a qualidade dos elementos finitos durante o processo de cálculo através de rearranjo ou movimento de malha independente do movimento material. Nas formulações Lagrangeanas a malha fica “colada” ao corpo durante toda a análise, logo quando este sofre grandes deformações diferenciais o mesmo se reproduz numa malha distorcida. A formulação ALE desacoplada consta de dois passos: O passo Lagrangeano onde são aplicados os incrementos de carga, a malha permanece “colada” à matéria durante a análise. E cada certo “tempo” o passo Euleriano onde “descola-se” a malha da matéria e efetua-se o movimento de malha que se ajusta melhor ao corpo deformado. São apresentados assim métodos de realocação da malha e transferência ou atualização das variáveis necessárias para, depois do passo Euleriano, continuar a análise com a nova malha sem grandes distorções dos elementos. Os problemas de grandes deformações e deslocamentos são acompanhados de não linearidades físicas e geométricas, assim, são abordados os métodos para o tratamento destas não linearidades. Trabalha-se com o elemento hexaédrico tri-linear com integração reduzida e controle dos modos espúrios que tem demostrado um bom comportamento frente a grandes não linearidades geométricas assim como para as não linearidades físicas. A formulação ALE tem ganhando seu espaço na mecânica dos sólidos, em problemas de conformação mecânica e impacto, devido às grandes deformações e na última década está abrindo-se passo na área da geomecânica tratando problemas recalque e penetração de fundações em solos. / This work presents remeshing techniques for finite element simulation and investigates their performance for large deformation problems. Lagrangian formulation generally results in excessive mesh distortion owing to its attachment to the material. Meanwhile, the Lagrangian- Eulerian (ALE) formulation alouds to keep the finite element quality through the arbitrarily rearrangement or movement of the mesh, to optimize the element’s shape. The decoupled Arbitrary Lagrangian-Eulerian approach consists in a sequence of Lagrangian and Eulerian steps. The mesh is “coupled” to the material during the Lagrangian steps. From step to step, mesh is decoupled from the system material (Eulerian step), the nodes corresponding to free boundaries are relocated using an analytical approach, remeshing is performed and finally the state variables are remapped. Rearrangements methods for the element’s node are presented, as well as the variables remapping algorithms at the new quadrature points, in order to continue with the finite element analysis without altering the element topology of the original mesh. Special attention is given to methods dealing with geometric and physical nonlinearities. A trilinear hexahedral element is used with reduced integration and hourglass control. This combination has shown well behavior in front of large geometric and physical nonlinearities. ALE formulation field has considerably grown in geotechnical research, especially in impact and mechanical extrusion problems. Over the last decade, geomechanic is dealing with settlement problems and foundation penetration in soils.