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