科研之友
微信
新浪微博
Facebook
分享链接
摘要
There is a vast number of applications that require distance field computation over triangular meshes. State-of-the-art algorithms have quadratic or sub-quadratic worst-case complexity, making them impractical for interactive applications. While most of the research oil this subject has been focused on reducing the computation complexity of the algorithms, in this work we propose an approximate algorithm that achieves similar results working in lower resolutions of the input meshes. The creation of lower resolution meshes is the essence of our proposal. The idea is to identify, regions on the input mesh that call be unfolded into planar regions with minimal area distortion (i.e. quasi-developable charts). Once charts are computed, their interior is re-triangulated to reduce the number of triangles, which results in a collection of simplified charts that we call a base mesh. Due to the properties of quasi-developable regions, we are able to compute distance fields over the base mesh instead of over the input mesh. This reduces the memory footprint and data processed for distance computations, which is the bottleneck of these algorithms. We present results that are one order of magnitude faster than current exact solutions, with low approximation errors.
- 出版日期2009-10-7
