CODEWITHSUNDEEP
c++mathnormalspoint-clouds
DashControl
DashControl

Reputation: 284

Computing normals at each point in a point-cloud?

I have a series of points that form a point cloud. I need to compute the normal vector at each point and cast a ray from that point in the direction of the normal vector. What type of formula do I need to use to compute the normal vector in this situation?

EDIT* I have a series of points (x, y, z) that form a point cloud (call this A), which forms the shape of a half sphere. I also have another point cloud (call this B), which I fitted a surface to, that forms another half sphere which fits inside A. I want to measure the length of how far these surfaces are far apart from each other, so my plan is to cast a ray from each point in A, to the surface B and measure the intersection to that point. I hope this explanation makes my question more clear.

Thank you for the help!

Upvotes: 1

Views: 5400

Answers (3)

pedro_galher
pedro_galher

Reputation: 384

I developed a code in Python that will calculate the normal at each point of a point cloud. You could adapt it to C++.

-Basically you calculate the Single Value Decomposition from the k points near your points.

It will provide you with information regarding where the variance is bigger and smaller.

-Then you take the direction where the variance is smaller (eigenvector associated to the smallest eigenvalue). This eigenvector is the normal to the plane passing through your k-points (including your point P). Finally, repeat this to each of the points of the point cloud.

Upvotes: 2

Suedocode
Suedocode

Reputation: 2524

  1. Can you establish correspondence between the two meshes? That is, for every point in mesh A, there a corresponding point in mesh B at a different location as a result from translation/scaling/rotation. If so, then you can use Procustes Analysis to find the optimal translation/scaling/rotation transformation matrices between the two clouds. In the example provided in the OP, the scaling matrix can reveal the distances between the two meshes.

  2. If the two meshes are arbitrary, then the best algorithm I can think of is to first put both point clouds in the same oct-tree. From here, you can iterate through every point in mesh A and find the nearest point in mesh B. The "minimum distance between two meshes" is the minimum distance found between 2 points after iterating.

The alternative to 2 is simply brute force iterate through all of the points:

double min=BIG_NUMBER;
for(Point a : meshA)
   for(Point b : meshB)
       if(dist(a,b)<min) min=dist(a,b);

Upvotes: 0

Martin Beckett
Martin Beckett

Reputation: 96109

Do you have a mesh so that you know which other local points a point is connected to?

In which case the normal at the point is the average (ie normalize to a unit vector of one) the cross product between each pair of lines meeting at the point.

Upvotes: 1

Related Questions