Surface discretization for point-based image synthesis

الموضوعات

علوم تطبيقية وتكنولوجية

الملخص

Visualizing isosurfaces is an important mean to explore data and discoverknowledge in volumetric datasets. The Marching Cubes (MC) algorithm isthe original, simple and most popular isosurface extraction technique. In thistechnique, the resulting isosurface consists of the combination ofall polygonsproduced around the discrete point samples of the input dataset.For severaldecades, the improvement of the accuracy and the topological correctness ofthe polygonized isosurface was the goal of many research works.On 3D regular grids of data, most authors consider that the “ideal”isosurfaceis the one obtained by a trilinear interpolation of sample data located atthe eight vertices of every 3D grid cell - voxel. They use this argument topropose alternatives to the original MC algorithm which allows producingpolygonized surface that is homeomorphic to the ideal one, by mainlyintroducing supplementary points to the original mesh.If a smooth surface is to be represented by a triangle mesh, the numberof triangles is inversely proportional to the approximation error. Agoodapproximation can be achieved with a fine mesh to adapt surface curvatureand shape complexity. When the number of triangles is high, rendering suchdatasets leads to triangles whose projected area is less than one pixel; wastingtime in triangle based scan-line rendering. Another alternative to solve theproblem is to use points as rendering primitives instead of triangles.Point-based isosurfacing techniques have been developed for theaim ofvoxelizing the assumed ideal surface to achieve a better approximation of thedesired isosurface. The main advantage of point-based isosurfacing techniquesis their structural simplicity. This is due to the fact that no connectivity, ortopological information is required which makes the geometric processing ofhighly complex 3D-models more flexible.The Dividing Cubes algorithm (DC) is among the proposed point-basedalternatives to solving problems related to MC-like methods by which weare interested. However, it has some drawbacks related mainly to its timecomplexity in the extraction process and the excessive number of points usedin surface representation. In this thesis, we are interested by this familyof isosurface point-based representation approaches, in which we propose amuch more efficient and fast voxelization algorithm.Since in DC technique, the resulting voxelized isosurface is based a piece-wise trilinear interpolation, which makes itG0continuous across the cellBoundaries. The first part of our work consists in the study of using ahigher order interpolation schemes - tricubic interpolation - in the DCbasedisosurface extraction in order to produceG1surfaces; the so called modifiedDC algorithm. Both techniques have been implemented and tested for comparison purposes in terms of both surface quality and computationaltime.The main part of this thesis is devoted to propose a new method for afastincremental voxelization of isosurfaces obtained by the trilinear interpolationof 3D data. Our objective here consists in the fast generation of subvoxelizedisosurfaces extracted by a point-based technique similar to DC algorithm.Our technique involves neither an exhaustive scan search processnor agraph-based search approach when generating isosurface points. Insteadan optimized incremental approach is adopted here for a rapid isosurfaceextraction. With a sufficient sampling subdivision criteria around criticalpoints, the extracted isosurface is both correct and topologicallyconsis-tent with respect to the piecewise trilinear interpolant. Furthermore, thevoxelization scheme used in our method ensures obtaining thin - one voxelwidth - isosurfaces as compared to the one given by the DC algorithm. Theresultant subvoxelized isosurfaces are efficiently tested against all possibleconfigurations of the trilinear interpolant and real-world datasets

روابط وملفات

التعريف والنوع

رقم الوثيقة

0420622f-0001-4525-8799-0d302d8996be

رقم العقد

0

نوع الوسائط

Crawler

نوع المحتوى

الرسائل العلمية

صيغة المصدر

رسائل دكتوراة

نوع الملف

word

أسماء الملفات

1372132_1.docx, 1372132_2.pdf

بيانات النشر

ألقاب المؤلفين

[{"name_ar":"Fatima Boumghar","title_ar":"اشراف","title_en":"Supervision"},{"name_ar":"Rachid Namane","title_ar":"اعداد","title_en":"Preparation"},{"name_ar":"Serge Miguet ","title_ar":"اشراف","title_en":"Supervision"}]

اللغة

English

المصدر والدورية

اسم المصدر

Surface discretization for point-based image synthesis

المحتوى والصفحات

عدد الصفحات

0

ترجمة الملخص

L'algorithme du Marching-Cubes est la technique standard la plus connue dans le domaine de l'extraction d’isosurfaces à partir d’un volume 3D, dans le rendu volumique indirect. L'isosurface résultante dans le Marching-Cubes est représentée par un maillage de polygones produit autour des échantillons d'entrée de l’image 3D. Durant plusieurs décennies, l'amélioration de la précision et de l'exactitude de la topologie de l'isosurface obtenue par le Marching-Cubes a été l'objectif de nombreux travaux de recherche, qui reposaient essentiellement sur l’affinage du maillage en introduisant des points supplémentaires. Lorsque le nombre de triangles induits est élevé, le rendu de ces derniers conduit à des triangles dont la surface projetée est inférieur à un pixel. Une autre alternative pour résoudre les problèmes liés à l’approche polygonale, est l’utilisation de points comme primitives de rendu, plutôt que des triangles. L'algorithme du Dividing-Cubes fait partie des approches basées-point, introduite initialement pour remédier aux problèmes liés au Marching-Cubes et ses variantes. Cependant, cette technique présente certains inconvénients liés principalement à la complexité des calculs dans la phase d'extraction, ainsi qu’au nombre excessif de points générés dans la surface résultante. Dans cette thèse, nous nous sommes intéressés à cette famille d'approches d’extraction d’isosurfaces basées-points, et nous proposons des techniques de discrétisation beaucoup plus efficaces et rapides. Contrairement au Dividing-Cubes, le travail principal de cette thèse a été consacré à proposer une nouvelle méthode de discrétisation rapide de l’isosurface qui est basée sur une approche incrémentale pour éviter l’utilisation du processus de balayage exhaustif ou par graph pour la recherche des points de l’isosurface, ce qui rend la phase d’extraction plus rapide. Avec une résolution d’échantillonnage suffisante autour des points critiques, l'isosurface extraite est à la fois correcte et topologiquement cohérente par rapport à l'interpolant trilinéaire. De plus, la méthode de discrétisation utilisée dans notre approche garantit l'obtention d’une surface plus fine, avec une largeur d’un voxel - par rapport à celle obtenue par l'algorithme des Dividing-Cubes.

كلمات الباحثين

Dividing cubes, Grilles : analyse numérique, Infographie : Logiciels , ncremental algorithm, Point-based renderin, Traitement d'images : Techniques numériques , Trilinear & Tricubic interpolants, Voxelized Isosurface

إشراف وإعداد

الإشراف

Fatima Boumghar, Serge Miguet

الإعداد

Rachid Namane

الاقتباسات الببليوغرافية