Model Simplification and Sample Decimation




Model simplification

1.  In many cases the reconstructed model contains too many elements (triangles, edges, vertices) to be amenable for further processing. A widely used method decimates the model by contracting edges with their incident triangles. We study this edge contraction process with the goal that the topology of the model is preserved. This guarantee can be extended to two dimensional simplicial complexes and to three dimensional manifolds with our method. No prior method can guarantee this. This is a joint work with Herbert Edelsbrunner based on which Raindrop Geomagic has developed the decimator software.

Sample Decimation


2.  In another approach we decimate the sample before reconstructing a surface out of it. This has the advantage of automatic topology and feature preservations over the model simplification method. Also, one does not need to worry about self intersection. After decimating the sample we employ our Cocone algorithm to reconstruct the surface. 

./circle23_blue.gif Topology preserving edge contraction.

We consider simplification of meshes with edge contractions. But, we study the condition that allows edge contractions without destroying the topology of the model. Our method works for simplicial complexes upto dimension three.

T. K. Dey, H. Edelsbrunner, S. Guha and D. Nekhayev. Topology preserving edge contraction. . Publications de l' Institut Mathematique (Beograd), Vol. 60 (80), 1999. Aslo, Technical Report RGI-Tech-98-018, Raindrop geomagic Inc., Research Triangle Park, North Carolina, 1998. 


./circle23_blue.gif Decimating Sample.

We have designed two algorithms Decimate  and  Shuffle for sample decimation. Decimate deletes samples where oversampling has occurred. An user input parameter can guide the levle of decimation. This provides a level-of-details (LOD) in meshing the surface. Shuffle not only decimates the samples but also repositions them to guarantee the aspect ratio of the triangles in the output surface.

T. K. Dey,  J. Giesen and J. Hudson. Decimating samples for mesh simplification. Proc. 13th Canadian Conference on Computational Geometry, (2001), 85--88

 T. K. Dey, J. Giesen, S. Goswami, J. Hudson, R. Wenger, W. Zhao. Undersampling and oversampling in sample based shape modeling. Proc. IEEE Visualization, (2001), 83--90.


Decimation of samples at different levels

Decimation of sample Foot at three diffrent levels (nearly 80% data reduction is achieved). Reconstruction is performed with Cocone

For  Shuffle see

T. K. Dey,  J. Giesen and J. Hudson. Sample shuffling for quality hierarchic surface meshing. Proc. 10th International Meshing Roundatble Conference. (2001), 143--154.

Foot without any decimation (skinny triangles around two sparse regions). Approx. 36000 triangles.

Output of Decimate (long skinny triangles still remain). Approx. 4000 triangles.

Output of Shuffle (skinny triangles are smoothed out nicely). Approx. 4000 triangles.