Skip to Main content Skip to Navigation

Simplification polyédrique optimale pour le rendu

Abstract : In computer science, pictures are digital and so, they are composed of pixels in 2D or of voxels in 3D. In 3D virtual scenes, we cannot directly manipulate objects as sets of voxels because the data are too huge. As a result, the objects are transformed into polyhedra, i.e. collections of facets. For this, we must be able to decide if a subset of voxels can be replaced by a facet in the polyhedrisation. This problem is called digital plane recognition. To solve it, we design a new algorithm especially adapted for sets of voxels which are dense in a bounding box. Our method achieves a quasi-linear worst-case time complexity in this case and it is efficient in practice. In parallel, we study another algorithmic problem which occures in our digital plane recognition algorithm. It is computing the two convex hulls of grid points lying in a bounded vertical domain and located on either side of a straight line. We propose an optimal time complexity method to compute these convex hulls and which is also output sensitive. We present the problem in a different way : find the rational number of bounded denominator that best approximates a given real number. We establish the link between this numerical problem and geometry. Finally, we independently propose a new algorithm to compute the lattice width of a set of points in Zd. Our method is optimal in 2D and is greedy but efficent in higher dimension
Document type :
Complete list of metadata

Cited literature [84 references]  Display  Hide  Download
Contributor : Abes Star :  Contact
Submitted on : Thursday, November 4, 2010 - 2:07:34 PM
Last modification on : Wednesday, February 3, 2021 - 7:54:26 AM
Long-term archiving on: : Saturday, February 5, 2011 - 2:57:49 AM


Version validated by the jury (STAR)


  • HAL Id : tel-00532792, version 1


Emilie Charrier. Simplification polyédrique optimale pour le rendu. Informatique. Université Paris-Est, 2009. Français. ⟨NNT : 2009PEST1011⟩. ⟨tel-00532792⟩



Record views


Files downloads