Construction of iso-contours, bisectors and Voronoi diagrams on triangulated surfaces

Yong-Jin Liu Tsinghua University Zhan-Qing Chen Hong Kong University Kai Tang Hong Kong University

Computational Geometry mathscidoc:1608.09009

IEEE Transactions on Pattern Analysis and Machine Intelligence, 33, (8), 1502, 2011.8
In the research of computer vision and machine perception, 3D objects are usually represented by 2-manifold triangular meshes M. In this paper, we present practical and efficient algorithms to construct iso-contours, bisectors, and Voronoi diagrams of point sites onM, based on an exact geodesic metric. Compared to euclidean metric spaces, the Voronoi diagrams onMexhibit many special properties that fail all of the existing euclidean Voronoi algorithms. To provide practical algorithms for constructing geodesicmetric- based Voronoi diagrams onM, this paper studies the analytic structure of iso-contours, bisectors, and Voronoi diagrams onM. After a necessary preprocessing of model M, practical algorithms are proposed for quickly obtaining full information about iso-contours, bisectors, and Voronoi diagrams on M. The complexity of the construction algorithms is also analyzed. Finally, three interesting applications—surface sampling and reconstruction, 3D skeleton extraction, and point pattern analysis—are presented that show the potential power of the proposed algorithms in pattern analysis.
Shape, geometric transformations, triangular meshes, exact geodesic metrics, point patterns
[ Download ] [ 2016-08-19 15:21:01 uploaded by liuyj ] [ 768 downloads ] [ 0 comments ] [ Cited by 49 ]
@inproceedings{yong-jin2011construction,
  title={Construction of iso-contours, bisectors and Voronoi diagrams on triangulated surfaces},
  author={Yong-Jin Liu, Zhan-Qing Chen, and Kai Tang},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160819152101738958264},
  booktitle={IEEE Transactions on Pattern Analysis and Machine Intelligence},
  volume={33},
  number={8},
  pages={1502},
  year={2011},
}
Yong-Jin Liu, Zhan-Qing Chen, and Kai Tang. Construction of iso-contours, bisectors and Voronoi diagrams on triangulated surfaces. 2011. Vol. 33. In IEEE Transactions on Pattern Analysis and Machine Intelligence. pp.1502. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160819152101738958264.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved