This is exactly what least squares solves.
Cross Product of Many Vectors
Author
I know you said that this will run on the GPU, but I sat down to find an analytical solution to this problem (if nothing else, I was just curious myself) under some definition of an optimal solution. Whether it's a feasible solution depends on what constraints you have on your solution and implementation. I came up with an analytical solution at least, so do what you want with it.
This is most excellent. I attempted to implement it. Notice that V*VT is real symmetric (since it is the sum of real symmetric matrices). This simplifies the eigenproblem significantly.
Since this is being implemented in OpenCL, which as of version 1.2 doesn't support matrices directly, I had to manually implement much of the necessary matrix code. However, before I even finished, I was noticing that it was slowing performance unacceptably. It wasn't too bad, but it was still too much.
So, thanks for the derivation, but I don't think it's practical on the GPU yet.
If the surface is well-behaved enough, you could select a few points on the cloth surface, interpolate the surface based on a spline curve or something, and analytically compute the normal.
I thought of that first actually, but it's difficult in general since the cloth surface's simulation grid is not necessarily a simple 2D parametrization of the surface.
You seem to be looking for a best fit plane through a set of nearly coplanar points. The Newell plane is what you are looking for:
This technique, first suggested by Newell (Sutherland et al., 1974), works for concave polygons and polygons containing collinear vertices, as well as for nonplanar polygons, e.g., polygons resulting from perturbed vertex locations...
Newell's method may seem inefficient for planar polygons, since it uses all the vertices of a polygon when, in fact, only three points are needed to define a plane. It should be noted, though, that for arbitrary planar polygons, these three points must be chosen very carefully:
Three points uniquely define a plane if and only if they are not collinear; and
if the three points are chosen around a "concave" corner, the normal of the resulting plane will point in the direction opposite to the expected one.
Checking for the properties would reduce the efficiency of the three-point method as well as making its coding rather inelegant. A good strategy may be that of using the three-point method for polygons that are already known to be planar and strictly convex (no collinear vertices,) and using Newell's method for the rest.
Source: Filippo Tampieri. “Newell's Method for Computing the Plane Equation of a Polygon”. In Graphics Gems III, Academic Press, 1992, pp. 231–232.
Here is a good free reference:
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
