[pt] A extração e visualização de isosuperfícies de campos escalares são importantes para inspeções e análises de modelos em diversas áreas. Uma isosuperfície é representada por uma malha de triângulos que aproxima um conjunto de nível do volume de dados. O foco deste trabalho é a extração e visualização de isosuperfícies de modelos de reservatório de petróleo, representados por malhas de hexaedros levemente côncavos. Para uma melhor representação das isosuperfícies, optou-se pela substituição de triângulos planares por superfícies curvas. Para assegurar a extração de superfícies contínuas e suaves, este trabalho propõe o uso de envelopes para determinação das normais. A técnica proposta é implementada em GPU com uso de subdivisão adaptativa das superfícies. / [en] The extraction and visualization of isosurfaces of scalar fields are important for inspections and analysis of models in several areas. An isosurface is represented by a mesh of triangles that approximates a level set of a data volume. The main focus of this work is the extraction and visualization of isosurfaces of black oil reservoir models, represented by hexahedral meshes with slightly concave cells. For a better representation of the isosurfaces, we have opted to replace planar triangles for curved patches. To ensure the extraction of continuous and smooth surfaces, this work proposes the use of envelopes to determine normals. The proposed technique is implemented in GPU with the usage of adaptive subdivision of patches.

No description available.

In recent years, the potential benefits of high-throughput virtual screening to the drug discovery community have been recognized, bringing an increase in the number of tools developed for this purpose. These programs have to process large quantities of data, searching for an optimal solution in a vast combinatorial range. This is particularly the case for protein-ligand docking, since proteins are sophisticated structures with complicated interactions for which either molecule might reshape itself. Even the very limited flexibility model to be considered here, using ligand conformation ensembles, requires six dimensions of exploration - three translations and three rotations - per rigid conformation. The functions for evaluating pose suitability can also be complex to calculate. Consequently, the programs being written for these biochemical simulations are extremely resource-intensive. This work introduces a pure computer science approach to the field, developing techniques to improve the effectiveness of such tools. Their architecture is generalized to an abstract pattern of nested layers for discussion, covering scoring functions, search methods, and screening overall. Based on this, new stratagems for molecular docking software design are described, including lazy or partial evaluation, geometric analysis, and parallel processing implementation. In addition, a range of novel algorithms are presented for applications such as active site detection with linear complexity (PIES) and small molecule shape description (PASTRY) for pre-alignment of ligands. The various stratagems are assessed individually and in combination, using several modified versions of an existing docking program, to demonstrate their benefit to virtual screening in practical contexts. In particular, the importance of appropriate precision in calculations is highlighted.

Two dimensional magnetic recording (TDMR) achieves high areal densities by reducing the size of a bit comparable to the size of the magnetic grains resulting in two dimensional (2D) inter symbol interference (ISI) and very high media noise. Therefore, it is critical to handle the media noise along with the 2D ISI detection. In this paper, we tune the generalized belief propagation (GBP) algorithm to handle the media noise seen in TDMR. We also provide an intuition into the nature of hard decisions provided by the GBP algorithm. The performance of the GBP algorithm is evaluated over a Voronoi based TDMR channel model where the soft outputs from the GBP algorithm are used by a belief propagation (BP) algorithm to decode low-density parity check (LDPC) codes.

Nous nous intéressons à la phénoménologie des villes en nous limitant à la géométrie induite par le squelette de leur réseau de rues. C'est une étude à volonté synthétique, fonctionnelle et interdisciplinaire qui vient s'ajouter aux travaux qui ont été menés à grande cadence depuis le début du XXème siècle par des urbanistes, sociologues, géographes, statisticiens, physiciens. Nous cherchons à montrer que la rue, en tant qu'alignement cohérent de segments de rues peut être considérée comme structure élémentaire de la ville. Quelle quantité d'information est donnée par la géométrie du réseau routier ? Dans quelle mesure contraint-il nos échanges ? Comment le paysage urbain actuel est-il déterminé par son évolution le long d'axes de circulation et d'éléments structurants ? Nous présentons un cadre mathématique permettant de considérer la carte d'une ville comme un continuum géométrique défi ni par la topologie d'un graphe planaire. Nous superposons à ce graphe une structure d'hypergraphe pour manipuler aisément la notion d'axes ainsi qu'une représentation multi-échelles de la ville. En dépit d'une grande diversité apparente de formes, nous montrons que le réseau de rues d'une ville se soumet à un certain nombre de lois générales qui laissent des traces sur le plan de la ville. Nous proposons des modèles de croissance et de morphogénèse de la ville, implé- mentant l'idée que l'évolution de la ville suit une logique d'extension / division structurée de l'espace et reproduisant les signatures observées sur les plans de villes réelles. La compréhension des mécanismes régulateurs de la ville nous permet de proposer des algorithmes fonctionnels dont le temps de calcul est très intéressant. Ainsi nous présentons un algorithme reconstituant les rues à partir de segments de rues ; la notion de centralité simple dont le calcul sur une carte permet une analyse hiérarchique de celle-ci, met en valeur les axes de trafic principaux et en évidence les zones mal desservies ; un algorithme permettant d'approximer rapidement le plus court chemin entre deux points aléatoires ; un algorithme prenant appui sur le Spectral Clustering pour produire des segmentations morphologiques de cartes et retravaillons l'identi cation de modèles de mosaïques aléatoires pour les substituer à un réseau urbain particulier dans la résolution par équivalents statistiques de grands problèmes d'optimisation.

No description available.

La modélisation automatique de villes à partir d’images satellites est l'un des principaux défis en lien avec la reconstruction urbaine. Son objectif est de représenter des villes en 3D de manière suffisamment compacte et précise. Elle trouve son application dans divers domaines, qui vont de la planification urbaine aux télécommunications, en passant par la gestion des catastrophes. L'imagerie satellite offre plusieurs avantages sur l'imagerie aérienne classique, tels qu'un faible coût d'acquisition, une couverture mondiale et une bonne fréquence de passage au-dessus des sites visités. Elle impose toutefois un certain nombre de contraintes techniques. Les méthodes existantes ne permettent que la synthèse de DSM (Digital Surface Models), dont la précision est parfois inégale. Cette dissertation décrit une méthode entièrement automatique pour la production de modèles 3D compacts, précis et répondant à une sémantique particulière, à partir de deux images satellites en stéréo. Cette méthode repose sur deux grands concepts. D'une part, la description géométrique des objets et leur assimilation à des catégories génériques sont effectuées simultanément, conférant ainsi une certaine robustesse face aux occlusions partielles ainsi qu'à la faible qualité des images. D'autre part, la méthode opère à une échelle géométrique très basse, ce qui permet la préservation de la forme des objets, avec finalement, une plus grande efficacité et un meilleur passage à l'échelle. Pour générer des régions élémentaires, un algorithme de partitionnement de l'image en polygones convexes est présenté. / Automatic city modeling from satellite imagery is one of the biggest challenges in urban reconstruction. The ultimate goal is to produce compact and accurate 3D city models that benefit many application fields such as urban planning, telecommunications and disaster management. Compared with aerial acquisition, satellite imagery provides appealing advantages such as low acquisition cost, worldwide coverage and high collection frequency. However, satellite context also imposes a set of technical constraints as a lower pixel resolution and a wider that challenge 3D city reconstruction. In this PhD thesis, we present a set of methodological tools for generating compact, semantically-aware and geometrically accurate 3D city models from stereo pairs of satellite images. The proposed pipeline relies on two key ingredients. First, geometry and semantics are retrieved simultaneously providing robust handling of occlusion areas and low image quality. Second, it operates at the scale of geometric atomic regions which allows the shape of urban objects to be well preserved, with a gain in scalability and efficiency. Images are first decomposed into convex polygons that capture geometric details via Voronoi diagram. Semantic classes, elevations, and 3D geometric shapes are then retrieved in a joint classification and reconstruction process operating on polygons. Experimental results on various cities around the world show the robustness, scalability and efficiency of the proposed approach.

La complexité de la forme de la surface est une caractéristique morphologique des surfaces pliées. Dans cette thèse, nous visons à développer des méthodes spectrales pour quantifier cette caractéristique du cortex cérébral humain reconstruit à partir d'images MR structurales. Tout d'abord, nous suggérons certaines propriétés qu'une mesure standard de la complexité de surface devrait posséder. Ensuite, nous proposons deux définitions claires de la complexité de la surface en fonction des propriétés de flexion de surface. Pour quantifier ces définitions, nous avons étendu la transformée de Fourier à fenêtres illustrée récemment pour transformer en maillage des surfaces. Grâce à certaines expériences sur les surfaces synthétiques, nous montrons que nos mesures basées sur la courbure permettent de surmonter les surfaces classiques basées sur la surface, ce qui ne distingue pas les plis profonds des oscillants ayant une surface égale. La méthode proposée est appliquée à une base de données de 124 sujets adultes en bonne santé. Nous définissons également la complexité de la surface par la régularité de Hölder des mouvements browniens fractionnés définis sur les collecteurs. Ensuite, pour la première fois, nous développons un algorithme de régression spectrale pour quantifier la régularité de Hölder d'une surface brownienne fractionnée donnée en estimant son paramètre Hurst H. La méthode proposée est évaluée sur un ensemble de sphères browniennes fractionnées simulées. En outre, en supposant que le cortex cérébral est une surface brownienne fractionnée, l'algorithme proposé est appliqué pour estimer les paramètres Hurst d'un ensemble de 14 corticus cérébraux fœtaux. / Surface shape complexity is a morphological characteristic of folded surfaces. In this thesis, we aim at developing some spectral methods to quantify this feature of the human cerebral cortex reconstructed from structural MR images. First, we suggest some properties that a standard measure of surface complexity should possess. Then, we propose two clear definitions of surface complexity based on surface bending properties. To quantify these definitions, we extended the recently introduced graph windowed Fourier transform to mesh model of surfaces. Through some experiments on synthetic surfaces, we show that our curvature-based measurements overcome the classic surface area-based ones which may not distinguish deep folds from oscillating ones with equal area. The proposed method is applied to a database of 124 healthy adult subjects. We also define the surface complexity by the Hölder regularity of fractional Brownian motions defined on manifolds. Then, for the first time, we develop a spectral-regression algorithm to quantify the Hölder regularity of a given fractional Brownian surface by estimating its Hurst parameter H. The proposed method is evaluated on a set of simulated fractional Brownian spheres. Moreover, assuming the cerebral cortex is a fractional Brownian surface, the proposed algorithm is applied to estimate the Hurst parameters of a set of 14 fetal cerebral cortices.

Historically 3D game environments have almost always been immutable. Mutable environments are a technical challenge that will affect performance. For games of the future to continue approaching realism, mutable environments are an essential step. Popularized by the game title Minecraft (2009), the use of voxel engines in games has become increasingly common. However, by the nature of the discrete position of voxels, the method is limited in representing arbitrary polyhedral shapes like angled slopes. It also prohibits smooth mutations including proper movement and rotation of objects within the voxelization. This is generally mitigable with more voxels. However, this paper proposes a more precise solution to the problem. A tetrahedral mesh engine (tetra engine). By altering tetrahedral topology, vertex positions, and material of individual tetrahedrons, tetras are intended to solve the issue of arbitrary polyhedral shapes for voxels. Additionally, the tetrahedral mesh shows other promises such as providing a robust collision detection method and as an acceleration structure for e.g. raycasting. The research question can be summarized as investigating the feasibility of a tetra engine as a mutable game environment. 3 sub-research questions are given: The first regarding performance, the second regarding robustness, and the third different types mutations. The research questions are addressed along with a proof of concept (POC). The POC intends to investigate a proposal for the most efficient robust solution possible for the most basic mutation type known as edits. Because of time constraints, it does not cover all parts of the research questions but works as a bottom-up approach to understand what is required to realize a full-fledged tetra engine. Thus, a large part of the research question is answered theoretically both hypothetically with grounds from the POC and through previous work. The result shows a much more critical robustness consideration than expected and suggests relying on slower but more robust algorithms that are known to work. In conclusion, nothing suggests that a scalable future-proof tetra engine is impossible, but the algorithms required are much less efficient than those for voxels and robustness is an issue to overcome. However, numerous hypothetical advantages particularly regarding deformation and fluid simulation are still recognized and it is not obvious that future mutable environments would not benefit from a tetra engine rather than voxels. / Historiskt sätt har 3D-datorspelmiljöer nästan uteslutande varit oföränderliga. Det finns goda anledningar till detta. Föränderliga miljöer är en teknisk utmaning som påverkar speleffektiviteten. Om man däremot vill fortsätta utveckla mer realistiska datorspel är föränderliga spelmiljöer ett naturligt steg. Spelet Minecraft (2009) populariserade användandet av voxlar i datorspel vars material kan ändras för att förändra miljön. Sedan dess har voxlar i datorspel blivit mer och mer populära. Dock, på grund av voxlars diskreta positioner har de begränsningar i dess förmåga att representera godtyckliga polyedriska former så som arbiträrt vinklade plan. Detta omöjliggör även mjuka rörelser inklusive rörelse och rotering inom voxeliseringen. Det här problemet kan generellt dämpas med hjälp av mindre och fler voxlar. Men, för att lösa problemet ordentligt föreslår den här rapporten en annan lösning, nämligen en tetrahedrisk-mesh-motor (tetramotor). Genom att ändra tetraedrisk topologi, hörn positioner, samt material av individuella tetraedrar ska tetrorna kunna forma arbiträra polyedriska former och lösa problemet med voxlar. Utöver detta visar en tetraedrisk mesh andra intressanta möjligheter likt en metod för robust kollisions hantering och som en accelereringsstruktur för till exempel ray-casting. Forskningsfrågan kan sammanfattas som att utforska tillämpbarheten av en tetramotor för föränderliga datorspelsmiljöer. Tre underfrågor ges: Den första handlar om beräkningseffektivitet, den andra angående robusthet och den tredje oliky typer av mutationer. Forskningsfrågorna angrips med hjälp av en proof of concept lösning (POC). POC:en är menad att utforska ett förslag på en effektiv och robust metod för direkta förändringar. På grund av tidsbegränsningar så täcker inte POC:en alla delar av frågeställningarna men är menad som en botten upp lösning för att inse och förstå kraven för en komplett tetramotor. På grund av detta är en stor del av forskningsfrågorna svarade teoretiskt, både hypotetiskt baserat på insikterna från POC:en och med grund från tidigare forskning. Resultatet visar en mycket mer kritisk hänsyn till robusthet än förväntat och föreslår att man använder sig av långsammare men fungerande existerande lösningar. Slutsatsen är att inget tyder på att en skalbar framtidssäker tetramotor är en omöjlighet, men att algoritmerna är mycket långsammare än de som krävs för voxlar. Däremot finns potentieally fördelar med en tetra motor, främst med hänsyn till deformering och flödessimulering. Det är därför inte självklart att framtida muterbara spelmijöer inte skulle ha fördelar av en tetramotor istället för voxlar.

We formulate Local Shape Descriptor selection for model-based object recognition in range data as an optimization problem and offer a platform that facilitates a solution. The goal of object recognition is to identify and localize objects of interest in an image. Recognition is often performed in three phases: point matching, where correspondences are established between points on the 3-D surfaces of the models and the range image; hypothesis generation, where rough alignments are found between the image and the visible models; and pose refinement, where the accuracy of the initial alignments is improved. The overall efficiency and reliability of a recognition system is highly influenced by the effectiveness of the point matching phase. Local Shape Descriptors are used for establishing point correspondences by way of encapsulating local shape, such that similarity between two descriptors indicates geometric similarity between their respective neighbourhoods. We present a generalized platform for constructing local shape descriptors that subsumes a large class of existing methods and allows for tuning descriptors to the geometry of specific models and to sensor characteristics. Our descriptors, termed as Variable-Dimensional Local Shape Descriptors, are constructed as multivariate observations of several local properties and are represented as histograms. The optimal set of properties, which maximizes the performance of a recognition system, depend on the geometry of the objects of interest and the noise characteristics of range image acquisition devices and is selected through pre-processing the models and sample training images. Experimental analysis confirms the superiority of optimized descriptors over generic ones in recognition tasks in LIDAR and dense stereo range images. / Thesis (Ph.D, Electrical & Computer Engineering) -- Queen's University, 2009-09-01 11:07:32.084