贪婪投影算法Greedy Projection algorithm - 知乎
创建时间：2020/5/20 10:11
奋斗和学习在图像处理领域小虫一枚
主要用于通过无序点云建立一个surface。输入无线点云集（点坐标以及估算的法向量）通过kdtree搜索近邻点，投影到切平面，通过角度和距离筛选、可见性（以参考点看过去，是否有交叉边存在）筛选，建立三角面片形成surface。
The Greedy Projection algorithm works by maintaining a list of points from which the mesh can be grown (“fringe” points) and extending it until all possible points are connected. Triangulation is performed locally, by projecting the local neighborhood of a point along the point’s normal and connecting unconnected points.
The algorithm is based on incremental surface growing principle, following a greedy type approach. The algorithm starts by creating a starting triangle and keeps on adding new triangles until all the points in the cloud have been considered or there no more valid triangles which can be connected to the resultant mesh.
1. Nearest neighbor search: For each point ‘p’ in the point cloud, a k-neighborhood is selected. This neighborhood is created by searching the reference point’s nearest k-neighbors within a sphere of radius r. The radius is defined as µ.d, where d is the distance of the point p from its closest neighbor and µ is the user-specified constant to take into account the point cloud density.
To find the nearest neighbors for the given point in the point cloud, Kdtree nearest neighbor search has been used.
The points in the cloud are assigned various states depending on their interaction with the algorithm: free, fringe, boundary, and completed.
a) Initially, all the points in the cloud are in the free state and free points are defined as those points which have no incident triangles. b) When all the incident triangles of a point have been determined, the point is referred to as of completed state.
c) When a point has been chosen as a reference point but has some missing triangles due to the maximum allowable angle parameter, it is referred to as a boundary point.
d) Fringe points are the points that have not yet been chosen as a reference point
2. Neighborhood projection using tangent planes : the neighborhood is projected on a plane that is approximately tangential to the surface formed by the neighborhood and ordered around p.
3. Pruning : The points are pruned by visibility and distance criterion , and connected to p and to consecutive points by edges, forming triangles that have a maximum angle criterion and an optional minimum angle criterion. The points in the point cloud are pruned depending on many criterion.
a) Pruning by distance criterion: a distance criterion is applied to prune down the search for candidate adjacent points in the spatial proximity of current reference point using kd-tree.
b) Further points which lie outside the spher e of influence centered at reference point are rejected. The chosen points are referred to as the candidate points.
c) Choice of projection plane: the candidate set of points obtained after applying the distance criterion are projected on the approximate tangent plane.
d) Angle ordering : a new local coordinate system is defined with the reference point as the origin and the plane projection of the previous step serves as the xy-plane. All the points in the candidate set are projected this plane. Ordering around the ref. point is based on the angle (ϴ) between the x-axis of the local coordinate system and the vector from origin to the projected candidate point.
e) Visibility: the points which potentially form a self-intersecting mesh are discarded. The algorithm defines two edge types for checking this condition:
I. Boundary Edge : an edge with only one triangle incident on it. These edges connect fringe and/or boundary points.
II. Internal Edge : connect the completed points with any other points.
The plane is projected using the reference point, candidate set of points and the boundary edges. In case, the line of sight from the reference point to a candidate vertex is obstructed by an edge, the point is occluded.
< surface construction from points cloud> Navpreet Kaur Pawar 2013
< A Fast and Efficient Projection-Based Approach for Surface Reconstruction> Gopi, M. & Krishnan, S. 2000
编辑于 2017-12-07