رسائل دكتوراة
English
2017
Surface discretization for point-based image synthesis
Fatima Boumghar, Rachid Namane, Serge Miguet
كلية المعلوماتية والالكترونيات-جامعة العلوم والتكنولوجيا هواري بومدين - الجزائر · الجزائر
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