Bug 547 : Polygons parallel to z-axis not always filling with nonzero x or y
Last modified: 2007-10-10 12:32




Status:
RESOLVED
Resolution:
FIXED -
Priority:
P2
Severity:
normal

 

Reporter:
ewjordan
Assigned To:
fry

Attachment Type Created Size Actions

Description:   Opened: 2007-04-18 16:27
This is a regression (present in 0124) from the fix to bug 111 which was
added to 0120 - if you draw a polygon that has zero volume when projected
onto the XY plane, it only fills if the X or Y coordinate is zero (the test
case in bug 111 had x==0, so was technically solved by the fix). The
problem occurs in both OpenGL and P3D modes, and can be seen in the
following test case.

import processing.opengl.*;

void setup() {
size(640, 480, OPENGL);
frameRate(30);
}

void draw() {
background(255);
fill(50); stroke(255,0,0);
if (!keyPressed){ beginShape(POLYGON); }
else {beginShape(TRIANGLES);}
if (mousePressed){vertex(mouseX+.0001, mouseY, 0);}
else{ vertex(mouseX, mouseY, 0); }
vertex(mouseX, mouseY+100, -100);
vertex(mouseX, mouseY, -100);
endShape(CLOSE);
}

For now there are two workarounds: 1) use beginShape(TRIANGLES) and
tesselate the polygon yourself, or 2) offset one of the coordinates by a
tiny amount so that the polygon is no longer degenerate when projected onto
the XY plane. In the above example, pressing a key implements fix 1),
pressing the mouse button implements 2).
Additional Comment #1 From Bug Master 2007-04-20 17:28
good, thanks for posting.

does the fix i mentioned not work?
Additional Comment #2 From ewjordan 2007-05-03 00:33
Sorry, forgot to check in on this bug for a while. The fix you mentioned
will be necessary, but I think there's also a problem with the following loop:

for (int i = vertex_start; i < vertex_end; i++) {
if (vertices[i][MX] != 0) foundValidX = true;
if (vertices[i][MY] != 0) foundValidY = true;
}

I'm pretty sure (though I didn't write the algorithm so I'm not positive)
that to have found a valid x or y, we care more that the difference between
the coordinates of two vertices is nonzero rather than that the value at a
single vertex is nonzero. Is that right, or am I misinterpreting what this
part of the method is trying to do?
Additional Comment #3 From fry 2007-05-06 15:36
right, so in fact, that code should be checking to see whether at least one
of the axes is not completely identical to the others, not just that they
equal zero.
Additional Comment #4 From ewjordan 2007-05-08 15:06
Okay, I think the following is the proper replacement code, starting around
line 1550 in PGraphics3D (sorry if the formatting gets swallowed in the
posting - seemed excessive to upload the whole file for such a minor change):

if (area == 0) {

// figure out which dimension is the perpendicular axis
boolean foundValidX = false;
boolean foundValidY = false;

for (int i = vertex_start; i < vertex_end; i++) {
for (int j = i; j<vertex_end; j++){
if ( vertices[i][MX] != vertices[j][MX] ) foundValidX =
true;
if ( vertices[i][MY] != vertices[j][MY] ) foundValidY =
true;
}
}

if ( (foundValidX && !foundValidY) || (foundValidX && foundValidY) ) {
//d1 = MX; // already the case
d2 = MZ;
} else if (!foundValidX && foundValidY) {

[snip - no changes from here on]

If you'd prefer to use an abs(vertices[i][MX]-vertices[j][MX]) > EPSILON
test, that works, too; we could also break out of the loop the moment we've
found a valid coordinate, which might save a few ops (more for more
complicated polygons). We should no longer have to check for the case
(foundValidX && foundValidY), because if the area is zero, this should
never happen, but to allow for precision shenanigans, I rolled it up in the
first case to be safe. Even if we screw up here, the iteration over
vertices later on in the program will punt if there's a problem, so it's
probably best to err on the side of allowing the polygon to attempt to be
tesselated, unless (until?) we discover a case where it's actually drawing
pixels where there should be none.
Additional Comment #5 From Olivier 2007-05-10 12:25
Hi, please note that the turnaround #2 does not fully work.

The following shows that some polygones are not filled :
void setup() {
size(640, 480, P3D);
frameRate(30);

}

void draw() {
background(255);
fill(50); stroke(255,0,0);

float x,y;
fill(50); stroke(255,0,0);
for(x=0;x<=640;x+=25){
for(y=0;y<480;y+=25){
beginShape(POLYGON);
vertex(x+0.0001, y, 0);
vertex(x, y+50, -50);
vertex(x, y, -50);
endShape(CLOSE);
}
}
}
Additional Comment #6 From ewjordan 2007-05-10 16:42
Yup, you're right - for that example adding .0001 is not quite enough, I
went up to .001 and the triangles showed up again. This is a floating
point issue, I think the problem is that you need to bump one of the
coordinates enough so that the area in the xy plane calculates to a nonzero
value; I guess adding .0001 only sometimes gives you enough.

In any case, hopefully the change to PGraphics3D that I suggested above
will make these workarounds moot in an upcoming release. Until then, you
may have to play around with the actual value that you offset coordinates
by. I've seen other examples where you have to add more to make the
triangles appear, BTW. In any case, using TRIANGLES mode should work fine
no matter what as it never invokes the tesselator at all.
Additional Comment #7 From fry 2007-06-23 16:51
i've applied the code from your other posts, i noticed that this was
changed in there too--is it fixed properly?
Additional Comment #8 From ewjordan 2007-06-23 19:31
Yeah, the SVN version now has what I think is the appropriate fix for this
bug - I've been using the version with the PGraphics3D file that I sent
you, so I'm pretty sure it's working right. I can't test anything on the
machine I'm on right now, but as soon as I get to one where I can I'm going
to build the SVN version from scratch and make sure everything is still
working as expected. I do have a fairly good set of test cases for all the
bugs I've been looking at, so I'll try them all and let you know if
everything looks right.
Additional Comment #9 From fry 2007-07-14 19:07
yet another fix for this one in 0125, thanks to ewjordan.