A Constrained Triangulation Technique for Visualization on Mobile Devices
Sang-Wook Yang, Young Choi · Korean Journal of Computational Design and Engineering · 2007
3D rendering is becoming a common feature of mobile application programs with the rapid advance of mobile devices. Since the existing rendering engines do not provide triangulation functions, mobile 3D programs have focused on an efficient handling with pre-tessellated geometry. In addition, triangulation is comparatively expensive in computation, so it seems that the triangulation cannot be easily implemented on mobile devices with limited resources. Triangulation of 3D geometry is the essential process of visualization of 3D model data and many different triangulation methods have been reported. We developed a light and fast visualization process that involves constrained triangulation based on Voronoi diagram and applied it to a mobile computer application. In this paper, we applied kd-tree to the original incremental construction algorithm and produced new O(nlogn) incremental construction algorithm. And we show a simple and efficient constrained triangulation method based on Voronoi diagram. This paper also describes an implementation of mobile STEP data viewer as an application of our proposed algorithms.