Pengfei Wang

Efficient Nearest Neighbor Search Using Dynamic Programming
[Preprint]
Pengfei Wang , Jiantao Song , Shiqing Xin^* , Shuangmin Chen , Changhe Tu , Wenping Wang , Jiaye Wang
[PDF]

Abstract:

Given a collection of points in

ℝ^{3}

, KD-Tree and R-Tree are well-known nearest neighbor search (NNS) algorithms that rely on space partitioning and spatial indexing techniques. However, when the query point is far from the data points or the data points inherently represent a 2-manifold surface, their query performance may degrade. To address this, we propose a novel dynamic programming technique that precomputes a Directed Acyclic Graph (DAG) to encode the proximity structure between data points. More specifically, the DAG captures how the proximity structure evolves during the incremental construction of the Voronoi diagram of the data points. Experimental results demonstrate that our method achieves a 1x-10x speedup. Additionally, our algorithm offers several valuable features. For instance, it naturally supports an

O (k \log n)

algorithm for farthest point sampling, where

k

is the desired number of sample points. Moreover, density peak clustering, which involves finding the nearest point among the top K points, is typically considered to have a time complexity of

O (n^{2})

. With our algorithm, this can be reduced to

O (n \log n)

. We believe this work will inspire further research on the NNS problem.

Towards Voronoi Diagrams of Surface Patches.
IEEE Transactions on Visualization and Computer Graphics (TVCG)
Pengfei Wang , Jiantao Song , Lei Wang , Shiqing Xin^* , Dongming Yan , Shuangmin Chen , Changhe Tu , Wenping Wang
[PDF]

Abstract:

Extraction of a high-fidelity 3D medial axis is a crucial operation in CAD. When dealing with a polygonal model as input, ensuring accuracy and tidiness becomes challenging due to discretization errors inherent in the mesh surface. Commonly, existing approaches yield medial-axis surfaces with various artifacts, including zigzag boundaries, bumpy surfaces, unwanted spikes, and non-smooth stitching curves. Considering that the surface of a CAD model can be easily decomposed into a collection of surface patches, its 3D medial axis can be extracted by computing the Voronoi diagram of these surface patches, where each surface patch serves as a generator. However, no solver currently exists for accurately computing such an extended Voronoi diagram. Under the assumption that each generator defines a linear distance field over a sufficiently small range, our approach operates by tetrahedralizing the region of interest and computing the medial axis within each tetrahedral element. Just as SurfaceVoronoi computes surface-based Voronoi diagrams by cutting a 3D prism with 3D planes (each plane encodes a linear field in a triangle), the key operation in this paper is to conduct the hyperplane cutting process in 4D, where each hyperplane encodes a linear field in a tetrahedron. In comparison with the state-of-the-art, our algorithm produces better outcomes. Furthermore, it can also be used to compute the offset surface.

PCO:Precision-Controllable Offset Surfaces with Sharp Features.
Siggraph Asia 2024
Lei Wang , Xudong Wang , Pengfei Wang , Shuangmin Chen , Shiqing Xin^* , Jiong Guo , Wenping Wang , Changhe Tu
[PDF] | [PROJECT PAGE]

Abstract:

Surface offsetting is a crucial operation in digital geometry processing and computer-aided design, where an offset is defined as an iso-value surface of the distance field. A challenge emerges as even smooth surfaces can exhibit sharp features in their offsets due to the non-differentiable characteristics of the underlying distance field. Prevailing approaches to the offsetting problem involve approximating the distance field and then extracting the iso-surface. However, even with dual contouring (DC), there is a risk of degrading sharp feature points/lines due to the inaccurate discretization of the distance field. This issue is exacerbated when the input is a piecewise-linear triangle mesh. This study is inspired by the observation that a triangle-based distance field, unlike the complex distance field rooted at the entire surface, remains smooth across the entire 3D space except at the triangle itself. With a polygonal surface comprising n triangles, the final distance field for accommodating the offset surface is determined by minimizing these n triangle-based distance fields. In implementation, our approach starts by tetrahedralizing the space around the offset surface, enabling a tetrahedron-wise linear approximation for each triangle-based distance field. The final offset surface within a tetrahedral range can be traced by slicing the tetrahedron with planes. As illustrated in the teaser figure, a key advantage of our algorithm is its ability to precisely preserve sharp features. Furthermore, this paper addresses the problem of simplifying the offset surface's complexity while preserving sharp features, formulating it as a maximal-clique problem.

Towards geodesic ridge curve for region-wise linear representation of geodesic distance field
Computer Aided Geometric Design (CAGD). Present at GMP 2024. [Best Paper Award]
Wei Liu^† , Pengfei Wang^† , Shuangmin Chen^* , Shiqing Xin , Changhe Tu , Ying He , Wenping Wang
[PDF]

Abstract:

This paper addresses the challenge of representing geodesic distance fields on triangular meshes in a piecewise linear manner. Unlike general scalar fields, which often assume piecewise linear changes within each triangle, geodesic distance fields pose a unique difficulty due to their non-differentiability at ridge points, where multiple shortest paths may exist. An interesting observation is that the geodesic distance field exhibits an approximately linear change if each triangle is further decomposed into sub-regions by the ridge curve. However, computing the geodesic ridge curve is notoriously difficult. Even when using exact algorithms to infer the ridge curve, desirable results may not be achieved, akin to the well-known medial-axis problem. In this paper, we propose a two-stage algorithm. In the first stage, we employ Dijkstra's algorithm to cut the surface open along the dual structure of the shortest path tree. This operation allows us to extend the surface outward (resembling a double cover but with distinctions), enabling the discovery of longer geodesic paths in the extended surface. In the second stage, any mature geodesic solver, whether exact or approximate, can be employed to predict the real ridge curve. Assuming the fast marching method is used as the solver, despite its limitation of having a single marching direction in a triangle, our extended surface contains multiple copies of each triangle, allowing various geodesic paths to enter the triangle and facilitating ridge curve computation. We further introduce a simple yet effective filtering mechanism to rigorously ensure the connectivity of the output ridge curve. Due to its merits, including robustness and compatibility with any geodesic solver, our algorithm holds great potential for a wide range of applications. We demonstrate its utility in accurate geodesic distance querying and high-fidelity visualization of geodesic iso-lines.

Efficiently Computing Voronoi Diagrams over Mesh Surfaces with Arbitrary Distance Solvers
ACM Transactions on Graphics (TOG). Present at SIGGRAPH Asia 2022.
Shiqing Xin , Pengfei Wang , Rui Xu , Dongming Yan , Shuangmin Chen^* , Wenping Wang , Caiming Zhang , Changhe Tu
[PDF] | [CODE]

Abstract:

In this paper, we propose to compute Voronoi diagrams over mesh surfaces driven by an arbitrary geodesic distance solver, assuming that the input is a triangle mesh as well as a collection of sites on the surface. We propose two key techniques to solve this problem. First, as the partition is determined by minimizing the m distance fields, each of which rooted at a source site,we suggest keeping one or more distance triples, for each triangle, that may help determine the Voronoi bisectors when one uses a mark-and-sweep geodesic algorithm to predict the multi-source distance field. Second, rather than keep the distance itself at a mesh vertex, we use the squared distance to characterize the linear change of distance field restricted in a triangle, which is proved to induce an exact VD when the base surface reduces to a planar triangle mesh.Specially, our algorithm also supports the Euclidean distance, which can handle thin-sheet models (e.g. leaf) and runs fasterthan the traditional restricted Voronoi diagram (RVD) algorithm. It is very extensible to deal with various variants of surface-based Voronoi diagrams including(1) surface-based power diagram, (2) constrained Voronoi diagram with curve-type breaklines,and (3) curve-type generators. We conduct extensive experimental results to validate the ability to approximate the exact VD in different distance-driven scenarios.

📜 updates

🎓 education

Ph.D. in Computer Graphics

Master in Computer Science and Technology

Bachelor in Information Science and Engineering

📚 publications

⛏️ resources