Computing plane for polygon, minimize floating point error

[freemancw]

Suppose I have a polygon with vertices specified in a floating point format (float or double - I'm not sure that it's fundamentally relevant which), and I want to compute a plane that "best fits" the given data. I have a number of questions about how to minimize floating point error.

• Typically, one would compute the cross product between two edge vectors to obtain the plane normal. Which two vectors will give the best approximation?
• There are many equivalent plane representations, when dealing with the real numbers. In floating point, which format preserves the most information?

I've been reading Goldberg's paper on floating point, as well as other sources. I was wondering, though, if anyone had readily available answers to these more geometrically oriented questions. Thanks!

edit: I am honored to have posted the 1024th topic.

[bone]

I think the idea you are looking for is the "least squares plane fit" - you might do a Google search for that. I know David Eberly, for one, had a fairly simple code snippet for finding it. If you can't find it, I may be able to dig it up.

[Dirk Gregorius]

Google for Newell plane. You find it discussed in "Real-Time Collision Detection" from Christer Ericson and in Gino's book. Here is a PDF as reference: http://cs.haifa.ac.il/~gordon/plane.pdf
You might also be able to find it in the Bullet source code since you usually use it for face merging. So you can maybe also search the forum and the source code.

HTH,
-Dirk

[freemancw]

Great! Thanks for the answers - I'll have a look into that algorithm.