What 3D in 3DEER means!!

Alsalam alikom wa ra7mat Allah wa barakatoh

Mustafa and me has the 3D part of the project. Let me tell u a brief about it..

Our problem we are tying to solve is: Given a scattered 3D Points (that the robot returned) we are asked to build a smooth 3D Model.

The first time I sat to think about this task, I just thought "What a pity, we can finish this in a day and have rest for the end of the year"... I was wrong!


What you see above is how the project goes from 3D Perspective... a 3D Model (to the left), the robot returns some scattered points (the middle) we should output a 3D Model (to the right)..


The Algorithms:
We have read about a lot of algorithms.. mainly we read about two types:

• Volumetric: Which works in O(n^2) (bad of course) but produces a fine smooth surface..
  Sample : Hoppe's Paper
  

• Incremental: Which works in O(nlgn) or O(n)... (fast of course) but needs some refining after generating the mesh. Besides, it assumes the points contain no noise..
  Sample: Huang, Menq (this is not their paper, but I couldn't find their original paper free online, and this is the only source I found that explains their algorithm and implements it)
  

Hoppe's Algorithms is as follows (brief of course):

• Use K-Nearest Neighbor (we used kdTree as our data structure Implementation) to calculate the Tangent Plane for every Xi. You need two data about each tangent plane; the Centroid and the Normal.
  The centroid calculation is pretty easy, just sum the K-points and divide them by k
  To calculate the Normal, you will need to use an algorithm called Principal Component Analysis (Implementation)... this link also contains a full java implementation for Hoppe's algorithm.
  

• Now build a graph (n^2 edges) from all points to all points and do a minimum spanning tre algorithm to reduce the number of edges

• The last problem to solve is the orientation of the Normals, those generated tangent planes' normals may need to be flipped to be right-oriented with respect to the whole other surfaces.
  To do this, we decide that the surface having the maximum Z will have its normal pointing to the +ve Z direction. Starting from this oriented surface, we just propagate to determine the orientation of the planes connected to it...
  

Huang, Menq Algorithm:

• We start by building the first triangle which has one point that is the most far point in the Z-Direction and the closet two points to it this triangle 's normal is set to +ve Z Direction

• We start by considering each of the border edges, we find the Best Point (which should lie in the K-Neighbors of the two edge points. More about selecting the Best Point will come in a later Post In Shaa Allah)

This candidate point can be one of the following cases:

Case 1: the B (Best Point) is not visited yet.. just create two edges and form a new triangle.. and add it as a boundary Point.







Case 2: The B is a boundary vertex AND is a close
neighbor to e (which means it lies in the next or previous edge to e)... Add One edge to B, Add the new triangle to your list, remove the internal vertex from the boundary list.







Case 3: B is on the boundary and is NOT a direct neighbor to e.... add two edges to B, add the new Triangle to the list..







That last Algorithm, is the one we are working on now... it's fast which would enable us to make runtime model generation (while the robot is exploring) In Shaa Allah.

That's it for now..

Alsalam alikom wa ra7mat Allah wa barakatoh