Thanks for taking the bug seriously. I also drew the case again in XZ plane and by twisting my right hand seriously I found out that actually the outer bound is CW and inner bound is CCW, since in XZ plane X axis points to left and Z axis up. I don't know if this information is helpfull, confusing, or trivial.
Pasi
-----Original Message-----
From: Discussion list for Java 3D API
[mailto:[EMAIL PROTECTED]]On Behalf Of Mark Hood
Sent: 11. maaliskuuta 2003 6:40
To: [EMAIL PROTECTED]
Subject: Re: [JAVA3D] Please have a look at the triangulation problem
> Date: Mon, 10 Mar 2003 09:17:09 +0200
> From: Pasi Paasiala <[EMAIL PROTECTED]>
>
> Could you finally have a look in the triangulation problem that we are
> constantly having? There is a simple test case that you can use to verify
> (and possibly fix) the problem.
>
> The problem is that the following data should create a rectangle with a hole
> inside:
>
> Point3d[] coordinates = {
> //outer bounds of the polygon
> new Point3d(2., 0.0, 0.0),
> new Point3d(2., 0.0, 1.3),
> new Point3d(0.0, 0.0, 1.3),
> new Point3d(0.0, 0.0, 0.0),
>
> //the hole
> new Point3d(1.93, 0.0, 0.07),
> new Point3d(0.07, 0.0, 0.07),
> new Point3d(0.07, 0.0, 1.13),
> new Point3d(1.93, 0.0, 1.13)
> };
>
OK, found the problem here.
The FIST algorithm works by first projecting the polygon onto a plane
and then working from the 2D projected points. It does this by
computing an "average" normal from every 3 points along each contour.
This works fine for polygons without holes. It also works fine for
polygons with holes as long as the vertex windings are the same for the
holes and the outer boundary. But in the above case, the normals for
the outer boundary and whole are flipped because of the opposite
windings, so the "average" normal is zero-length [0 0 0].
Instead of throwing an exception, the triangulator substitutes [0 0 1]
for the normal. This causes all the projected points to have a Y
coordinate of 0 in the above case, so the triangulation fails.
Workarounds: the algorithm always works if the original points are in
the XY plane. It also always works if the outer boundary and the holes
have the same winding order. It would also work even in the XZ and YZ
planes with inconsistent winding if the number of contours is odd.
The code looks like it's supposed to handle all cases -- it tries to
reverse the windings to a canonical form, with the outer boundary
ordered CCW and the inner holes ordered CW. So I think this is a
probably a legitimate bug, but I need to find out what the real
capabilities of the code are before determining its status and
evaluating whether we can supply a fix.
-- Mark Hood
===========================================================================
To unsubscribe, send email to [EMAIL PROTECTED] and include in the body
of the message "signoff JAVA3D-INTEREST". For general help, send email to
[EMAIL PROTECTED] and include in the body of the message "help".
