3D- How to choose the "best point"... Part2

Alsalam alikom wa ra7mat Allah wa barakatoh

Figure 1. Cylinder shape + Flooded Contour. The surface is generated using Huang, Menq Approach explained here

Just few minutes ago, we managed to output the above image using an incremental approach. Thanks Allah.

So, what's the progress so far?

• Robotics APIs (Zezo): Managed to move the robot in an arbitrary direction.
• Motion Planning (Kisho & Moussa): Finished their first approach, working on A* (for shortest route).
• 3D Model Construction (Mustafa & Me): Just managed to output acceptable models of the Incremental Algorithm (after the Brutal Force approach)

Let's get into the topic... the "best point" in Huang Menq approach we explained in the previous post has three criteria:

1. It must fall in the K-Nearest Neighbors of both end points of the edge.
   Just get the K-NN for one end point -> List1
   then use this list to get the K-NN for the other end point.
   
2. It must fall within the area formed by neighboring edges.
   p is the boundary vertex. Any candidate to p must fall within the range defined by that semi-circle.
   
3. It must form the biggest angle to the boundary vertex.

One problem was facing us in choosing the Best Angle, is how to determine the angle in the 3D Space... I tried to draw a diagram for explanation but it was not clear... think about it. In 3D, angles are somehow meaningless.
We had to think of a way to project 3D Points onto an estimated plane so that we can measure the angle easily.
We had two ideas (Actually the first is our idea, the second is from a online document):

1. Given a vertex v, and a plane P (Normal: N, Centroid: C). The procedure is as follows:
   vec = (v - C) -> gets origin based vector for v
   norm1 = (N*vec) -> gets a normal vector to the plane that contains N & vec (norm1 will definitely fall in P)
   result = (norm1 * N) -> gets a normal to the plane that contains N & norm1 (which now falls in P & the plane that contains vec & N)
   This method we are not sure about it... so just don't use it
   
2. result = N * (N.DotMultiplyPositionVector(vec)) * -1;
   Explained here
   

The output above is generated using K = 1000. Which made the algorithm runs in a long time. We are working to know why is that.

That's all till now..

Alsalam alikom wa ra7mat Allah wa barkatoh

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