Jump to content
  • Advertisement
Sign in to follow this  
theequal

Test for nonplanarity

This topic is 3524 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I was wondering if there's a simple and quick test for determining if a polygon is nonplanar? I have some ideas, (like triangulate it and compare all the normals), but I thought I would get a second opinion.

Share this post


Link to post
Share on other sites
Advertisement
Let's suppose you have the pentagon A B C D E. You can calculate the cross product (B-A)x(B-C) (the normal of the plane). If the polygon is planar, then the dot product of (B-A)x(B-C) with any other edge (e.g. D-E) should be near zero, since all the other edges should be perpendicular to ((B-A)x(B-C)) in order to lie on the same plane. I hope I am not missing anything.

Share this post


Link to post
Share on other sites
Grab the first three points and calculate the coefficients for the plane equation (assuming they're non-collinear, otherwise chose the first three non-collinear points). Check to make sure that all other points satisfy that equation, within a certain amount of tolerance. If they do, the polygon is planar.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zipster
Grab the first three points and calculate the coefficients for the plane equation (assuming they're non-collinear, otherwise chose the first three non-collinear points). Check to make sure that all other points satisfy that equation, within a certain amount of tolerance. If they do, the polygon is planar.


that's a pretty good method but you introduce a bias by picking the first 3 points, which could be removed by starting with the least squares equation of a plane and then checking for error from the least squares plane.

Share this post


Link to post
Share on other sites
Quote:
Original post by theequal
Thanks, I guess I could go either way, use the DotProduct or get the plane coefficients, as explained here:
http://local.wasp.uwa.edu.au/~pbourke/geometry/planeeq/

But what is this least squares equation of a plane you mentioned?
It sounds useful if I wanted to convert a nonplanar polygon into a planar polygon, but this is only a test for nonplanarity.


We both made some assumptions about your problem statement. Specifically, we assumed that you want some tolerance to roundoff error, and I additionally assumed that you might want some small tolerance on what is considered planar.

For example, let's say you have 10 points belonging exactly to a plane. Then one of the points is moved off the plane by 1 picometer. IS it still "planar"? How about a millimeter? An inch?

Note that, due to floating point precision issues, even if you intentionally calculate a set of points to be perfectly planar, they won't end up being 100% perfectly planar...so you should use an error tolerance.

You can visualize this question in 2 dimensions by asking if a set of points are colinear (part of the same line). By zipster's method you would choose the first 2 points, calculate the line between them (by y=mx+b) and then calculate the distance (assuming vertical distance) of each point to the line. Note that the vertical distance is biased by the basis vectors and a more robust method would be to use the point-to-line distance as an error tolerance.

Anyway, using that method, you could have a situation with for example 10 points, all of the last 9 are perfect, but the first 1 is not so good. By forming the line between the first two, it causes the last (good) point to exceed the error tolerance and the whole thing is considered not-colinear. But if you use the best fit line, and then measure the error from that, the largest error would be smaller than the largest error you got by using only the first 2 points, so this might cause it to be identified as colinear.

Because there is no special ordering of the points, the unbiased decision is more logical. You may not care about this level of precision so Zipster's method is a little bit simpler.

Depending on how accurate you wanted to be you could even improve this more. For example the typical least squares approach would only measure errors on one dimension, and you could instead use a least squares fit that minimizes the point-to-plane distance of each point, and then use the maximum point-to-plane distance for a threshold. Maybe you also want to consider the situation where the set of points is MOSTLY planar, but has a couple non-planar points mixed in. Then you should combine the method with RANSAC. It depends on the problem.

Share this post


Link to post
Share on other sites
Quote:
Original post by yahastu
Quote:
Original post by theequal
Thanks, I guess I could go either way, use the DotProduct or get the plane coefficients, as explained here:
http://local.wasp.uwa.edu.au/~pbourke/geometry/planeeq/

But what is this least squares equation of a plane you mentioned?
It sounds useful if I wanted to convert a nonplanar polygon into a planar polygon, but this is only a test for nonplanarity.


We both made some assumptions about your problem statement. Specifically, we assumed that you want some tolerance to roundoff error, and I additionally assumed that you might want some small tolerance on what is considered planar.

For example, let's say you have 10 points belonging exactly to a plane. Then one of the points is moved off the plane by 1 picometer. IS it still "planar"? How about a millimeter? An inch?

Note that, due to floating point precision issues, even if you intentionally calculate a set of points to be perfectly planar, they won't end up being 100% perfectly planar...so you should use an error tolerance.

You can visualize this question in 2 dimensions by asking if a set of points are colinear (part of the same line). By zipster's method you would choose the first 2 points, calculate the line between them (by y=mx+b) and then calculate the distance (assuming vertical distance) of each point to the line. Note that the vertical distance is biased by the basis vectors and a more robust method would be to use the point-to-line distance as an error tolerance.

Anyway, using that method, you could have a situation with for example 10 points, all of the last 9 are perfect, but the first 1 is not so good. By forming the line between the first two, it causes the last (good) point to exceed the error tolerance and the whole thing is considered not-colinear. But if you use the best fit line, and then measure the error from that, the largest error would be smaller than the largest error you got by using only the first 2 points, so this might cause it to be identified as colinear.

Because there is no special ordering of the points, the unbiased decision is more logical. You may not care about this level of precision so Zipster's method is a little bit simpler.

Depending on how accurate you wanted to be you could even improve this more. For example the typical least squares approach would only measure errors on one dimension, and you could instead use a least squares fit that minimizes the point-to-plane distance of each point, and then use the maximum point-to-plane distance for a threshold. Maybe you also want to consider the situation where the set of points is MOSTLY planar, but has a couple non-planar points mixed in. Then you should combine the method with RANSAC. It depends on the problem.


Let's say I don't know how to do that, but at the same time, I don't want to use one of my points as the initial plane point.
Do you have any objections against using the average of all points as the plane point?
So, use that as a reference to test all other points?

Share this post


Link to post
Share on other sites
Taking the barycenter as the representative point on the plane should be fine.

To find the perpendicular vector, you can probably study the covariance matrix of the three coordinates, and pick an eigenvector corresponding to the smallest eigenvalue. I would have to think a little more carefully about it, but I am sure something like that can be worked out.

Perhaps I'll post some code if I find the time to write it tonight.

Share this post


Link to post
Share on other sites
Quote:
Let's say I don't know how to do that, but at the same time, I don't want to use one of my points as the initial plane point.
Do you have any objections against using the average of all points as the plane point? So, use that as a reference to test all other points?


Given a set of data points, the average point is the least squares POINT. It takes 3 points to define a plane. The least squares plane is by definition the "average plane" passing through all of those points. Note that the average point also lies on the least squares plane. The most simple way to calculate the least squares plane is by assuming a plane of the form z = ax + by + c. Then you can simply find the least squares line in the x and y directions and use this to construct the plane. All this requires is looping over the data points and computing some sums of squares.

Alternate ways of computing the least squares plane would be to, as alvaro suggested, compute the variance-covariance matrix of your data set and then take the eigenvector corresponding to the largest eigenvalue. To get the dominant eigenvector the simplest method is to use the power iteration, which just involves multiply a matrix times a vector and normalizing it in a loop.

There are a whole host of other complicated methods that can be used for finding a least squares solution (to a plane, or to any other system of linear equations). The fastest method is Cholesky decomposition, but you could also use QR decomposition, Singular value decomposition (take the singular vector corresponding to the smallest singular value), Gaussian elimination, Gauss-Jordan elimination, Gauss-Seidel iterations. If the system is small (ie, a plane with 3 unknowns) then it can be solved with only a 3x3 matrix inverse which could be computed directly by the Laplace Expansion Theorem.

EDIT - anyway, without further description of your problem specifying exactly WHY you want to know if a set of points is coplanar, we are likely to lead you astray in our comments.

Share this post


Link to post
Share on other sites
You run into problems using a functional form of the plane equation. For instance with z = Ax + By + D, you assume the Z component of the least-squares plane normal is non-zero. If it's zero, then you'll end up with a divide-by-zero, an un-invertible matrix, or some other invalid operation during your calculations. It's best to use an approach that can handle the general form, Ax + By + Cz + D = 0, and doesn't make any assumptions about the plane itself.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!