Getting a normal from points
Author
I asked this over in the Graphics forum but didn''t get a reply, so I thought I''d ask in this one since its more math oriented.
I have a set of 3-d points that form an object. So given a center point Pc and its n nearest neighbors P1 ... Pn . How can I estimate the normal for it? I heard there is a way using least-squares minimization to build a plane, but I''ve looked at material on this and can''t draw the connection. I haven''t taken a linear algebra, or for that fact, a math course in years.
LinaInverse
One of the easiest ways is to:
a) triangulate several points that are close to the center point using Delaunay triangulation (search the forum archives or google for this---its all over the place)
b) compute the normals for each triangle, making sure they all point roughly in the same direction, e.g., the dot product of each normal with each other normal is positive
c) add the normals together the unitize it.
There are more and less efficient ways to do all that, which I''ll let you figure out on your own.
You could also subdivide the localized triangle mesh before calculating the normals, and use only the interior triangles of the subdivided mesh to calculate the normal---this will better approximate a curved surface:
www.subdivision.org
That said, there are other ways including least squares.
Given a point cloud, with no connectivity or underlying surface definition, you are going to have to make an approximation of the surface at the center point. Computing a least squares surfaces, for example a plane, is one way to do it. Search the forum archives or google and you will probably be able to find an in depth discussion of computing least squares lines or planes from points. If your object has highly variable curvature, or is a closed body, you''d want to compute the plane only from some points in the vicinity of the center point.
Beyond least squares planes, you could fit a higher order surface, for example locally use least squares to find a sphere whose center point and radius minimizes the error from several points that are nearby the center point.
Beyond that you can look into various interpolating spline techniques, or something like minimum norm network (MNN). These are more advanced techniques, though, and unless you have a very specialized purpose won''t amount to much benefit.
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
a) triangulate several points that are close to the center point using Delaunay triangulation (search the forum archives or google for this---its all over the place)
b) compute the normals for each triangle, making sure they all point roughly in the same direction, e.g., the dot product of each normal with each other normal is positive
c) add the normals together the unitize it.
There are more and less efficient ways to do all that, which I''ll let you figure out on your own.
You could also subdivide the localized triangle mesh before calculating the normals, and use only the interior triangles of the subdivided mesh to calculate the normal---this will better approximate a curved surface:
www.subdivision.org
That said, there are other ways including least squares.
Given a point cloud, with no connectivity or underlying surface definition, you are going to have to make an approximation of the surface at the center point. Computing a least squares surfaces, for example a plane, is one way to do it. Search the forum archives or google and you will probably be able to find an in depth discussion of computing least squares lines or planes from points. If your object has highly variable curvature, or is a closed body, you''d want to compute the plane only from some points in the vicinity of the center point.
Beyond least squares planes, you could fit a higher order surface, for example locally use least squares to find a sphere whose center point and radius minimizes the error from several points that are nearby the center point.
Beyond that you can look into various interpolating spline techniques, or something like minimum norm network (MNN). These are more advanced techniques, though, and unless you have a very specialized purpose won''t amount to much benefit.
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
you should use the cross product...
the cross product of two vectors will give you a vector that is perpendicular to both of these... so, if you have 3 points on a plane p1, p2, p3... and you make the vectors v1, v2 like so:
v1 = p2 - p1
v2 = p3 - p1
then do the cross product of v1 x v2... you''ll get yourself a vector which is normal to the plane of those 3 points...
Note: if your gonna do this, it will work best if your vectors v1 and v2 are roughly perpendicular to each other...
the cross product of two vectors will give you a vector that is perpendicular to both of these... so, if you have 3 points on a plane p1, p2, p3... and you make the vectors v1, v2 like so:
v1 = p2 - p1
v2 = p3 - p1
then do the cross product of v1 x v2... you''ll get yourself a vector which is normal to the plane of those 3 points...
Note: if your gonna do this, it will work best if your vectors v1 and v2 are roughly perpendicular to each other...
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
