Python implementation of the ball-pivoting algorithm (BPA), which was published in 1999 by Bernardini [1]. The code implements are inspired by Lotemn102 (2021). Ball-Pivoting-Algorithm GitHub repository
This algorithm solves the problem of reconstructing mesh surface from a 3D point cloud. The main assumption this algorithm is
based on is the following: Given three vertices, and a ball of radius r, the three vertices form a triangle if the ball is getting "caught" and settle
between the points, without containing any other point.
The algorithm stimulates a virtual ball of radius r. Each iteration consists of two steps:
- Seed triangle - The ball rolls over the point cloud until it gets "caught" between three vertices and settles between in them.
Choosing the right
rpromises no other point is contained in the formed triangle. This triangle is called "Seed triangle". - Expanding triangle - The ball pivots from each edge in the seed triangle, looking for a third point. It pivots until it gets "caught" in the triangle formed by the edge and the third point. A new triangle is formed, and the algorithm tries to expand from it. This process continues until the ball can't find any point to expand to.
At this point, the algorithm looks for a new seed triangle, and the process described above starts all over.
The following figures demonstrates those two steps.
2D view of the finding seed triangle step
2D view of the expanding triangle step
Two vague assumptions that are necessary for the algorithm are that the point cloud is "dense enough", and that the
chosen r size is "slightly" larger than the average space between points. I couldn't find a metric method to evaluate
those two variables at the moment, and more work needs to be done on this.
I used a virtual 3D grid in which in each cell of the grid, all points are at distance of maximum 2r from all
other points. With this method, i am able to limit the number of points i need to search. Since we are looking to fit a
ball of radius r between three points, we can be assured that if the distance be two points is larger than 2r, the ball
won't get caught between them. Therefore, while checking all possible points to pivot from a point p when generating
seed triangle or expanding triangle, i need to check p's cell, and all 8 cells that touches this cell. Note that there
might get points that are 4r apart, and i have to check that when iterating through these neighbor points. Example for that
is shown in the following figure.
2D view on part of the grid. The orange cells are the neighbors of the green cell
Each cell is represented by a single point. For example, all cells are represented by the point marked by p:
Each cells saves the entire points contained in it, but i also needed each point to save which cell it belongs to, to avoid iterating all the grid when searching for a point. I decided that each point will save the cell in belongs to. In order to decrease the memory required for this cyclic-design, each point save encoded unique version of the cell it belongs to. The encoding was done by shifting and concatenating the coordinates of the point that defines the cell.
Encodeing the cell define by (1, 2, 3) to 197121
Consists of 3 coordinates, the normal in this point, the cell node it's sitting in, according to the grid's initiation.
Consists of 2 Point objects.
Finding a seed costs time. We iterate through all points.
For each point
p1, i check in time it's neighbor cells
in order to find all points that are at maximum distance of
2r from p1. I sort all neighbor points by distance from
p1 in to make sure the formed triangles will be as small as possible to reduce the number of cases where a
point in contained inside the formed triangle. For each point
p2 in p1's neighbors, the same sorting process occurs.
In order to check if a ball with radius of r can fit into the triangle defined by p1, p2 and p3, i calculate the
radius of the inner-circle of that triangle. This calculation is in
. If the normal of this triangle is in the same direction as the point's normal, the triangle is added to the mesh.
This check is also in
.
Expanding a single triangle costs .
For each of the triangle's edges
e=(p1,p2), i check in
time the neighbor cells of
p1 and p2 in order to find all points that are at maximum distance of 2r from p1 and p2.
I sort the points as before, in .
I then check if the ball can fit into the formed triangle, and that it's normal vector is in the same
direction as the points.
At the worst case, the algorithm fails to expand the triangle everytime and has to find a new seed, making the total
run time complexity . This scenario is unlikely.
This algorithm expects to get as input .txt file in the following pattern:
x y z nx ny nz
Where x, y and z are the point's coordinates, and nx, ny and nz are the point's normal vector's coordinates.
In order to generate the data to test the algorithm, i've downloaded 3D objects in .obj format [4], extracted the points, and
extracted each point's normal based on one of the facets it belongs to. Examples of the data are in the data folder. Code for generating new data is in data_generator.py.
- Python>=3.7
- numpy>=1.20.1
python main.py -i data/bunny.txt -r 0.1data_generator.py- Generates data from .obj files.bpa.py- The main implementation of the algorithm, including the grid and the data structures and save the mesh to a .obj file.
[1] The Ball-Pivoting Algorithm for Surface Reconstruction, by F. Bernardini, J. Mittleman and H. Rushmeier, 1999.
[2] An Analysis and Implementation of a Parallel Ball Pivoting Algorithm, by J. Digne, 2014.