Final Project Milestone Report : Point-cloud to Mesh

Name:   Star Li | SID: 3033789672   Han Cui | SID: 3033631995

Abstract

Surface reconstruction is the task to recover the surface mesh using a list of 3D points and their normals, which are usually scanned from the original objects and scenes in .ply format. It has been a heated topic in computer graphics over the years and what our focus is to implement one of the most famous algorithms -- the Ball-Pivoting Algorithm -- to enable efficient and accurate reconstruction. We started from building optimized, basic geometry structure and acceleration structure octree, and successfully implemented the core BPA algorithm using an iterative approach. Finally, we completed our pipeline by performing pre-processing and post-processing with python, so that we are able to read in .ply files from the Stanford Scan Repo and visualize the final results with Blender.


reconstructed result: dragon
reconstructed result: monster

Technical approach: Octree

In the BPA algorithm, there are lots of spatial queries that requires checking all the vertices (points) in the 3D space. For example, whenver we want to construct a new triangle mesh, we need to ensure the circumsphere of this triangle doesn't contain any point other than the triangle vertices. Without the help of an acceleration structure, this operation is so inefficient that our personal computer can barely perform any reconstruction. In this project, we chose Octree as our acceleration structure and modify it to fit in our use cases.

OcNode & Octree

An Octree is a data-structure where each node represents a bounding box volume in the 3D space and can have up to 8 children, which evenly subdivide the space into 8 smaller boxes of identical shapes (see below illustration). Each node can represent some region in space, yet only the leaf nodes (without any children) actually store a list of Vector3D points located inside that region.

Once constructed, the Octree is able to answer spatial queries efficiently because, suppose we want to find all points within a certain distance to a query location (essentially search a spherical region), we can quickly index all nodes in Octree that potentially contain such points and ONLY iterate through points in those nodes. In contrast, we might need to iterate through every single point if they are unorganized.


https://geidav.files.wordpress.com/2014/08/full_octree.png

Each OcNode represents a grid (box) region; however, many cases (e.g. the one above) require finding certain points within a spherical volume. Thus one important task is to calculate which nodes intersect with the spherical volume and such nodes need to be checked. What we did is to go from bottom-down (starting from the whole space), iteratively comparing the size of a node and the sphere at different layer, and stop when we cannot cover the sphere.

Implementation Details: Construction

In our setup, a OcNode contains its origin, which is the minimum of the box at all 3 axis, and its shape. These two vectors are enough to fully describe the node's region.

For Octree and similar data-structures such as BST, the construction step is about putting assigning each point to the corresponding "leaf node" where it's pointer can be stored for the future. This is an iterative process and the key is to determine "going left or right" (for Octree, we do that decision for x, y, and z) at each layer. To accelerate this process, we choose to calculate locational codes, a binary representation of coordinates, for each point. Suppose we have a point p with the root node's size to be s and origin at o. Then the locational code is: \[ L = (\frac{p.x - o.x}{s.x}, \frac{p.y - o.y}{s.y}, \frac{p.z - o.z}{s.z}) \] taken the floor of each term and represented in binary. An example of the actual locational code for a BST is shown below. The coordinate 7.1 is transformed into locational code 1011, and we surprisingly notice that each digit, taking value 0 or 1, actually contains the information of going left (0) or right (1) at the corresponding layer (first digit -- top layer). We can thus "extract out" these information with bit operation at each layer. The locational code in 3D space (BST is 1D) simply helps extract out these information in all axes. In this way we can construct our Octree very efficiently (24ms for 1 million points).


http://www.ipol.im/pub/art/2014/81/article.pdf

Implementation Details: Searching

In the searching phase, we can use the aforementioned locational code again to better index the query position and relate it to certain nodes.

We also briefly mentioned how do we determine the layer to start searching by comparing our nodes' size at each layer with the spherical region of interest. In reality, we make a specific modification to our Octree such that its height, width, and length doesn't have to be the same (in many octree implementation each node has to be cubic). This modification enables us to put a "tighter" bounding box around our object in the root object. Thus, whenver we try to compare the node's shape with a sphere, we will take the min of the x, y, z size of the node.

Decisions and Improvements

To sum up the above explanations, the following are some major decisions and improvements we make that are different from the original references


Technical approach: Geometry data structures

Since our implementation of “Point to Mesh” reconstruction requires huge amount of interactions and calculations with 3D geometries in different forms, we implemented several geometry class in C++ from scratch. Our data structures include Vertex, Edge, Sphere, and Triangle.

Vertex:

The Vertex class contains two Vector3D parameters of point and normal, which stores its 3D location and vertex normal read from the .xyz file. It also has an adjacent_edges and an adjacent_triangles list to store all the edges and triangles around the Vertex. Thus, the Vertex class has an add_edge and add_triangle method to update these two lists in the construction of the Edge and Triangle class. The Vertex class also contains a type parameter to flag whether the Vertex is connected to the Edges and Triangles and whether the Vertex is included in the reconstructed mesh with a corresponding update_type method. Another important method of Vertex class is compatible check with both an Edge and two other Vertices; the method examines whether the area-weighted face normal of the Triangle composited of corresponding elements is in the same direction of each Vertex’s normal.

Edge:

The Edge class contains two Vertex elements, representing two endpoints of the edge. In the Edge construction, these Vertex elements would update their adjacent_edges list, and the Edge class contains the get_Vertex method for both Vertex elements. The Edge class also contains two Triangle elements to represent the adjacent two Triangles, which is updated through the add_triangle method. Similar to the Vertex class, the Edge class also contains the type parameter to flag whether the Edge is inside the reconstructed mesh, or on the boundary of the mesh, which is updated in the add_triangle method. One specific method for the Edge class called update_edge is to maintain the identical orientation of edges by comparing the face normal of adjacent Triangle and vertex normal of the vertex besides Edge’s endpoints.

Sphere:

The Sphere class is mainly used in the empty ball configuration, which contains a Vector3D parameter sphere center, and a double parameter radius.

Triangle:

The Triangle class is a class in higher hierarchy compared to Vertex and Edge. The data of faces in the BPA output come from the Triangle class. The Triangle class contains three Vertex elements and three Edge elements. In the Triangle construction, the type and all adjacent lists of Vertex and Edge elements get updated, and the Triangle construction takes care of whether the Edge is already created to prevent repetitive Edges between vertices.

Technical approach: Ball-Pivoting Algorithm

The essense of BPA is to keep a list of "active edges". In the beginning, we will use the subroutine findSeedTriangle() to find a triangle mesh (with 3 vertices) to begin with, and add the triangle's three edges to the list; then we call expandTriangulation(), which will pop out the edge from the list and try to build more triangle meshes on its basis. This method will consume the edges in the list and once the list is empty, we start again by finding a seed triangle. This is the overall iterative process that builds up the mesh in BPA.

FindSeedTriangle()

We know that in most cases, three arbitrary vertices can form a triangle plane in space. The task of findSeedTriangle() is thus to check if such a triangle is valid or not. There are three main conditions:

If the three vertices satisfy the above 3 conditions, we accept the triangle they form as a "seed triangle", adding this triangle to the mesh and its three edges to the active (front) edge list.

FindCandidate()

findCandidate() algorithm is another core composition of BPA, mainly called in expandTriangulation(). It takes a pointer of Edge and tries to return a valid candidate vertex that a Ball of radius m_radius could pivot on without touching other vertices or include any vertices inside. This function is the process of simulating the physical ball-pivoting process on vertices. If no valid candidate is found, the algorithm will return NULL.

The first step of findCandidate() is to deal with the already-exist triangle of Edge e. Because BPA always calls findSeedTriangle() before the expandTriangulation(), it is ensured, by construction, that the Edge e passed in findCandidate() would always have one adjacent triangle t1, to prevent BAD_ACCESS error. The function findCandidate() calculates the center of the sphere with radius m_radius on t1 and the midpoint m of Edge e. The important step is to calculate radius \(r’\) with formula \( r’ = |m – c| + \text{m_radius} \), and find sorted neighbors of radius \(r’\) within query point of midpoint m’s location, given the acceleration structure Octree and Octsearch.

While traversing through the Vertex v in sorted neighbors, findCandidate() ensures that v cannot belong to t1, v cannot be tagged as an inner Vertex in the already constructed mesh, and v must be compatible with Edge e. If so, we construct another Sphere with v and two endpoints of e. If there’s a valid Sphere with radius m_radius available for these three Vertices, and there’s no other Vertex from the sorted neighbor inside the Sphere, we would set candidate to v. The process can be visually illustrated as the following graph:


http://www.ipol.im/pub/art/2014/81/article.pdf

As we want to set the candidate to be the first Vertex encountered by the rotating Sphere, we would use check the angle theta to measure the angle rotated by the Sphere. If Vertex v is eligible to be set as a candidate, we would like to check that the Sphere constructed using v has the smallest rotation angle. After traversing all of the Vertices in sorted neighbors, we return the valid candidate with the smallest rotation angle. If no valid candidate found, we would just return NULL.

expandTriangulation()

Our expandTriangulation() Method works with and updates the active front_edge list. As a self-iterative method, while the active edge list is not empty, we pop out the front Edge e from the active Edge list. After checking that e is not tagged as a border Edge or inner Edge, we call findCandidate() taking e as the parameter, and record the returned candidate Vertex v. Even though we checked the validity of v in the findCandidate(), we still want to double that that v is not tagged as inner Vertex or v is not compatible with e, and of course that v is not NULL. If v is not valid, we update Edge e’s type with border Edge and continue to the iteration.

With a valid candidate Vertex v, we check whether v is not connected to either endpoint of e, or the connecting Edge between v and e is not tagged as active. If so, we update e’s type as the border and continue. If v is still valid after these checks, we create a new triangle between e and v and add two edges connecting v and e’s endpoints to the active edge list if they are newly created.

postProcess()

Through expandTriangulation() process, there will be a special scenario to produces holes on the reconstructed mesh, as shown in the following graph:

http://www.ipol.im/pub/art/2014/81/article.pdf

Thus, we also implemented a post-process to take consideration of this case. For the post-Process() method, it is also a self-iterative method but keeps track of the border edge list, which is also updated by the expandTriangulation(). The border edge list contains the edges that we previously thought as the border and cannot connect to other vertices to form triangles. We pop out the front of the border edge list and tag it as e. Then, we check the neighboring edges to find if there’re two neighboring edges of e connect to the same Vertex v. If such a v could be found, and the Edge e forms an oriented loop with v, then we add a new Triangle with endpoints of e and v and remove e from the border edge list. Otherwise, we just continue to iterate until the border edge list is empty.

Even though we dedicatedly implemented the function, we didn’t include it in the reconstruct() method because that the process doesn’t contribute too much to our overall reconstructed mesh based on our experiments and debug process.

Problems encountered and lessons learnt

Problems:

Lessons learnt:

Results

Speedup by using OcTree

# With Octree (in s) Without Octree (in s)
initialization 0.025 0.024
reconstruction 11.655 40.222

Comparison of different BPA radius:


Bunny reconstruction with different BPA radius

We found is the trade-off between the degree of detail loss and missing parts, as you can see in the comparison of bunny .daes. As the radius increases, the holes and missing parts of the reconstruction decreases, while the degree of detail loss tends to increase.

Comparison of origina .ply:


Comparison, front angle
Comparison, front angle
Comparison, front angle

As we can see here, even though the comparison shows some degrees of detail loss, the overall similarity between the reconstructed meshes and the original meshes is still pretty high.

Examples of other reconstructions:

The reconstruction of Armadillo .ply, 172974 vertices
The reconstruction of dragon .ply, 100250 vertices

Contribution:

All team members contribute to the project files, presentation, testing, debugging, and experiments. The BPA algorithm is implemented equally by both of Star and Han.

There’re some parts they contribute individually:

Star Li: Acceleration Structure, integration of BPA algorithm and other classes.

Han Cui: Geometry Structure, File Input and Output, unintegrated BPA draft.

Resources

Ball-Pivoting Algorithm

Poisson Reconstruction

Others


Made with ❤ with Bootstrap, by Star Li and Han Cui