Checking coplanar 3D polygons

Checking coplanar 3D polygons

Post by Kev Kwa » Sat, 11 Jul 1998 04:00:00



Is their a fast algorithm that can be used to check whether a 3D polygon
is coplanar or not?  I'm trying to write a prog that checks a mesh for
non-coplanar polygons and flag them if they are not.  Any feedbacks here
are appreciated.

                                :)kev

 
 
 

Checking coplanar 3D polygons

Post by Joseph O'Rour » Sat, 11 Jul 1998 04:00:00




Quote:>Is their a fast algorithm that can be used to check whether a 3D polygon
>is coplanar or not?  [...]

Four points are coplanar iff the volume of the tetrahedron they
determine is zero.  See [O'Rourke (C), p.26] for how to compute
this volume, or any good Linear Algebra text.  This can be used
for an algorithm as follows, assuming your vertices are labeled
from i=0.

  for i = 3 to n do
     if vi is not coplanar with v0, v1, v2 return noncoplanar
  return coplanar

If you have floating point coordinates, there will be an issue
of near-coplanarity that you will need to deal with.

    [O'Rourke (C)]
    Computational Geometry in C,
    Joseph O'Rourke, Cambridge University Press 1994,
    ISBN 0-521-44592-2 Pbk, ISBN 0-521-44034-3 Hdbk
    Additional information at http://cs.smith.edu/~orourke/ .

 
 
 

Checking coplanar 3D polygons

Post by Vince Valent » Sun, 12 Jul 1998 04:00:00



> Is their a fast algorithm that can be used to check whether a 3D polygon
> is coplanar or not?  I'm trying to write a prog that checks a mesh for
> non-coplanar polygons and flag them if they are not.  Any feedbacks here
> are appreciated.

>                                 :)kev

I don't know if it is fast but,  :)

take 3 points in the polygon, and find the normal (A,B,C)

once you have the normal take any one of THOSE 3 points and solve
for D.

D = Ax + By + Cz

ABC = Normal  (-1 to +1)
xyz = vector (point)

Now, go through every OTHER point in the polygon that is left and
run it thorugh the equation

Current_Vector = Ax + By + Cz

if (Current_Vector == D)
   then it's co-planar

Make sure that you allow for "rounding errors" as D may never EXACTLY
equal to Current_Vector.

Hope this helps,

Vince

 
 
 

Checking coplanar 3D polygons

Post by Kev Kwa » Tue, 14 Jul 1998 04:00:00


Quote:> >Is their a fast algorithm that can be used to check whether a 3D polygon
> >is coplanar or not?
> Four points are coplanar iff the volume of the tetrahedron they
> determine is zero.  See [O'Rourke (C), p.26] for how to compute
> this volume, or any good Linear Algebra text.  This can be used
> for an algorithm as follows, assuming your vertices are labeled
> from i=0.

>   for i = 3 to n do
>      if vi is not coplanar with v0, v1, v2 return noncoplanar
>   return coplanar

Will this also work for hexagons?

Hmmm...Oh yeah...Can I use this as a basis for a "Polygon splitter", which
splits non-coplanar quadrangles into triangles?

Quote:> If you have floating point coordinates, there will be an issue
> of near-coplanarity that you will need to deal with.

Fortunately, they are integers, but what's the "near coplanarity" issue
with floats?

                                        :)kev

 
 
 

Checking coplanar 3D polygons

Post by Joseph O'Rour » Wed, 15 Jul 1998 04:00:00




Quote:>> >Is their a fast algorithm that can be used to check whether a 3D polygon
>> >is coplanar or not?

>> [...]
>>   for i = 3 to n do
>>      if vi is not coplanar with v0, v1, v2 return noncoplanar
>>   return coplanar

>[...] Can I use this as a basis for a "Polygon splitter", which
>splits non-coplanar quadrangles into triangles?

Yes.
Quote:

>> If you have floating point coordinates, there will be an issue
>> of near-coplanarity that you will need to deal with.

>Fortunately, they are integers, but what's the "near coplanarity" issue
>with floats?

Suppose, for example, you have a quadrilateral in the xy-plane,
and you rotate it into another plane with a floating-point rotation
matrix.  The four vertices are still coplanar, but roundoff in the
computations may result in a slightly nonzero tetrahedron volume.
So the check volume == 0.0 will return FALSE even though the points
are coplanar.
 
 
 

Checking coplanar 3D polygons

Post by Kev Kwa » Wed, 15 Jul 1998 04:00:00





> >> >Is their a fast algorithm that can be used to check whether a 3D polygon
> >> >is coplanar or not?

> >> [...]
> >>   for i = 3 to n do
> >>      if vi is not coplanar with v0, v1, v2 return noncoplanar
> >>   return coplanar

> >[...] Can I use this as a basis for a "Polygon splitter", which
> >splits non-coplanar quadrangles into triangles?

> Yes.

I see, I noticed that alot of realtime mesh engines (X-Plane, FSFS,
Quake/Q2) seems to favor using triangles to "build" a shape up.  Is it
because of the difficulties of having non-coplanar polygons render
incorrectly in a rasterization engine?

Quote:

> >> If you have floating point coordinates, there will be an issue
> >> of near-coplanarity that you will need to deal with.

> >Fortunately, they are integers, but what's the "near coplanarity" issue
> >with floats?

> Suppose, for example, you have a quadrilateral in the xy-plane,
> and you rotate it into another plane with a floating-point rotation
> matrix.  The four vertices are still coplanar, but roundoff in the
> computations may result in a slightly nonzero tetrahedron volume.
> So the check volume == 0.0 will return FALSE even though the points
> are coplanar.

Is that an imprecision problem within the Floating point unit?

                                        :)kev

 
 
 

Checking coplanar 3D polygons

Post by Joseph O'Rour » Thu, 16 Jul 1998 04:00:00







>> >Fortunately, they are integers, but what's the "near coplanarity" issue
>> >with floats?

>> Suppose, for example, you have a quadrilateral in the xy-plane,
>> and you rotate it into another plane with a floating-point rotation
>> matrix.  The four vertices are still coplanar, but roundoff in the
>> computations may result in a slightly nonzero tetrahedron volume.
>> So the check volume == 0.0 will return FALSE even though the points
>> are coplanar.

>Is that an imprecision problem within the Floating point unit?

There are several issues here, but it is not a failure of the fpu.
For example, suppose you rotate the point (2,0,0) 30 degrees about
the z-axis.  It's new coordinates are (sqrt(3),1,0).  sqrt(3) cannot
be represented exactly in floating-point, so your double representation
of this point is slightly wrong, by about 2^{-50}.  Four coplanar
points, all slightly wrong, may not give an exact zero volume.