from njetti:

I like the P3D renderer because it is much faster than the default renderer
(which is very slow using the video lib).

But there is a strange behaviour in it. - It draws incorrectly and this can
be seen in the following example where the rects around the mouse are drawn
in incorrenct sizes when the mouse is moved.

I am on OS X 10.3.8, in case you don't get the same behaviour:

code :

----

Form aform;

void setup() {
size(400,400, P3D); // DELETE P3D and it works fine !!!
aform = new Form(20, 200);
}

void draw() {
background(122);
aform.update();
}

class Form {
int x;
int y;

Form(int _x, int _y) {
x = _x;
y = _y;
}

void update(){
x = mouseX - 20;
y = mouseY - 20;
rect(x-10, y - 5, 4, 10);
rect(x, y+10, 4, 12);
rect(x+5, y-10, 12, 4);
}
}

follow-up from caj:

Although this is no answer, I just want to add that I am also seeing the
same type of bug - mostly inconsistent drawing of rect(), where the result
changes depending apon where in the applet I draw the rect().

I draw an array of like rectangles (with equal sides), with like spacing
between them. This works fine without P3D in the size statement. With P3D i
sometimes get the spacing between some rectangles taken out, and sometimes
the rectangles are different sizes. I have seen variation of up to three
(3) pixels.

*** Bug 237 has been marked as a duplicate of this bug. ***

this is a general issue of how low the accuracy is in P3D. rect() shapes
may dance around a bit, and line() objects will move too. the issue is that
there are different expectations of accuracy for 2D and 3D rendering, which
is why we separated P2D (not currently available), JAVA2D, and P3D. we
opted to go with fast 3D for the P3D renderer, but at the expense of the
graphics in 2D really suffering.

*** Bug 542 has been marked as a duplicate of this bug. ***

It seems to me that the real issue is that int arguments are passed as
parameters get slightly bumped away from true integer values during the
rendering math - since in P3D the rectangles are rendered as quads with
floating point arguments, a line that's supposed to be from 4 to 7 will
sometimes be drawn from 3.9999 to 7.0001 (for example), in which case the
rasterizer draws 5 pixels, sometimes from 4.0001 to 6.9999, in which case
only 3 are drawn, and sometimes in between those two (i.e. 3.9999 to
6.9999), in which case you'll get 4.

If you change the update section in that test code by adding a tiny bit to
every coordinate the problem disappears and everything draws as expected:

void update(){
x = mouseX - 20;
y = mouseY - 20;
rect(x-10+.001, y - 5+.001, 4, 10);
rect(x+.001, y+10+.001, 4, 12);
rect(x+5+.001, y-10+.001, 12, 4);
}

Would it make sense to just add something like this in as a quick hack?
i.e. if the coordinates passed to rect() are within EPSILON of an integer,
add EPSILON to them and call it a day? Perhaps you could even overload
rect() to handle int arguments like this explicitly, though I do notice
that it's not JUST the int-float cast causing the problem (if you write
10.0 instead of 10, or even cast x before the rect() call it still doesn't
help). This would slightly mess things up for people that like to zoom in
a whole lot, but anyone that's depending on the renderer to draw things
correctly at a scale where floating point precision starts to break down is
really asking for trouble anyways...

i admire many of the simplifying assumptions that enabled processing to get
off the ground and become a useful tool for so many. this approach
anticipates the work of barry schwartz at swarthmore.
http://video.google.com/videoplay?docid=7881889424111915182&q=barry+schwartz&hl=en


because of this it is very important that any change to an underlying
assumption be:
a) backward compatible with existing scripts
b) an improvement
c) fit within the parent language framework (i.e. java)
d) not represent a change in computational time or performance.

my proposed change is that the underlying type of float be changed to double.
evidence that this is a good idea:

1) When developing software in the utah graphics lab, we learned that
computer graphics enables one to see the impact of numerical decisions.
because we compute on machinery of finite precision, we want to use the
maximum precision available. Some analysts have shown that glancing
intersection calculations actually "braid" when zoomed to high detail.
2) many calculations get converted to double "underneath the hood", but if
we have not sampled at the maximum resolution possible, we don't benefit
from this.
3) if we are going to use a one-size-fits-all numerical data type, that
type should be double.

I decided on my all my graphics software, a long time ago, to always use
type double. Thus many of these round-off, underflow and overflow bugs have
never been a problem.

Some calculations, such as "equals" intrinsically require an epsilon model.
For these a function can be created that tests to see if two number are
equal within the floating point representation of the machine. I have code
for this somewhere, from an ATT signal processing lib, that does binary
subdivision till underflow occurs and then reports the resulting value just
before that as EPSILON.

Human beings are excellent difference detection engines. This is why
antialiasing, and sampling issues must be handled with care. Fortunately in
this case the fix is fairly easy, with no loss to the original charter of
simplicity of processing.

- L. Van Warren MS CS, AE
wdv.com

(In reply to comment #6)

> my proposed change is that the underlying type of float be changed to double.

Unfortunately that won't do it in this case. Again, pretend we're working
on the real line (doubles in this case) and rasterizing to a line of
pixels. If we pass in a line starting at 4 and ending at 7, that gets cast
to 4.0 -> 7.0, and the question becomes: do we draw the pixel at 3, or not?
Sim for pixel 7. The answer that the rasterizer decides upon has nothing
to do with the difference between a float and double, it has to do with the
fact that the length and position of that segment leaves both ends
teetering on the brink of turning pixels on or off depending on exactly how
the rasterization goes. Maybe 7.0 will end up drawing pixel 7, whereas 9.0
doesn't trigger pixel 9. I think the real question to decide is which
pixels SHOULD be turned on in this case? I would say you've either got to
shift a little bit left or right, thus drawing exactly 4 pixels no matter
what (I'm glossing over the fact that there is ALWAYS a length and position
where we will have ambiguity - however, these should be chosen so that they
don't arise from the extremely common practice of passing integers into the
rect() function). The problem is that the current renderer doesn't make a
consistent choice, so we end up with artifacts.

Not that there aren't some precision issues with floats, of course, but I
don't think this bug is one of them. BTW, from what I know, one of the
main reasons that floats were chosen for Processing is that they tend to
calculate faster - otherwise I agree with you, for most serious
mathematical code I try to use doubles whenever possible.

the solution silicon graphics used was to make the coordinate represent the
center of the pixel.

for a line going from 3.0 to 7.0, the rasterizer should "area sample" the
line and illuminate that area of the pixel subtended by the line using its
defined strokeWidth.

thus the line would intrude into both end pixels, but neither would be
completely illuminated.

on second thought i think that SGI discretized the raster grid such that
the edges of the pixels were on integer boundaries, otherwise they would
have given up a half pixel edge on the perimeter of the image.

the point is, that if all the geometry, especially the edges and vertices
are "area sampled", one retains good performance (as compared to
convolution with a Gaussian kernel) while retaining acceptable image quality.

i wish i could leave a short graphic of this in the text of this message.

(In reply to comment #5)
> Would it make sense to just add something like this in as a quick hack?
> i.e. if the coordinates passed to rect() are within EPSILON of an integer,
> add EPSILON to them and call it a day? Perhaps you could even overload
> rect() to handle int arguments like this explicitly, though I do notice
> that it's not JUST the int-float cast causing the problem (if you write
> 10.0 instead of 10, or even cast x before the rect() call it still doesn't
> help). This would slightly mess things up for people that like to zoom in
> a whole lot, but anyone that's depending on the renderer to draw things
> correctly at a scale where floating point precision starts to break down is
> really asking for trouble anyways...

interesting.. i'd be surprised if it were that simple to fix, but if you
give it a shot and it seems to be working, then great.

fwiw, the issue is nothing to do with float vs double, it's more to do with
float vs. the fixed point math used internally to PTriangle. this is sami's
code that he worked on, the previous triangle renderer (in PPolygon) used
floats.

and again, the idea is that the real problems in this bug come from using
P3D to draw in 2D (i.e. moving a flat rectangle across the screen), so this
hasn't received much attention.

floats are used in processing because they are significantly faster than
doubles (less so now than when the project first started). more explanation
about this can be seen on the discourse board.

Okay, here is a clear demonstration of the fact that this is not
specifically a problem with P3D, but that it is a general rasterization
issue having to do with pixel offsets. The following sketch breaks all 3
renderers (just change which line is not commented to see), although I
suspect the numerical value of EPS that breaks OPENGL depends upon your
particular hardware - I use a Powerbook G4, so YMMV with this:

import processing.opengl.*;
int iY = 0;
float EPS;
void setup(){
size(200, 200, OPENGL); EPS = .04166; //Break OPENGL (on my machine, at
least)
// size(200,200,P3D); EPS = 0.0; //Break P3D
// size(200,200); EPS = 0.50001; //Break default renderer
stroke(0, 0, 255);
}
void draw(){
line(0,iY+EPS,width/2,iY+EPS);
line(width/2,iY,width,iY);
iY++;
}

The real problem is that P3D breaks down with EPS = 0, which means that
whenever you put in an integer (which people do a LOT) you are right on the
knife's edge; the other renderers offset the bad value by a little bit, so
unless you are in the habit of passing in an integer + .04166, for
instance, you're unlikely to notice the "problem." But the point is, you
can never eliminate that critical edge, you can only choose to offset it by
a bit so that it doesn't cause trouble.

On an aside, changing the window size changes the behavior under OpenGL, so
I'm guessing that the pixel offset is somehow calculated based on the
window dimensions, and I'm not exactly sure about how, so it might be a bit
tough to exactly match that behavior. I'm also not certain whether the
OpenGL specs cover this - if I had to guess, they probably don't specify an
exact offset, but merely insist that it is not zero. From the OpenGL site,
at least a quick reading seems to confirm this:
http://www.opengl.org/documentation/specs/version1.1/glspec1.1/node47.html#SECTION00641000000000000000


But there is also another slight problem with P3D, in that unless you pass
it exactly an integer, it will never render the last scanline on the
screen. I suspect that means that the screen clipping algorithm rounds one
way and the line drawing rounds the other.

Anyhow, when I get a chance, I will take a closer look through the code and
see if I can patch this stuff up without being too messy, maybe try to at
least bring it closer in line with OpenGL rendering since there appears to
be no way to be mutually consistent with the default renderer and OpenGL.

Okay, here's a very quick hack that seems to fix this, emphasis on "hack"
as opposed to "fix."

In PGraphics3D.java I changed the resize(int iwidth, int iheight) function
so that the lines that are currently:

cameraX = width / 2.0f;
cameraY = height / 2.0f;

(around line 250) turn into this:

cameraX = width / 2.0f + .01f;
cameraY = height / 2.0f + .01f;

This offsets the pixel boundary slightly and forces the rectangles and
lines always to be the same widths no matter where they are on the screen,
at least for the default camera positioning (which is probably the most
common time that this bug shows up). It introduces (actually it doesn't
introduce it, but it causes it to become visible) another bug in that there
are some glitches at the edge of the screen - on the top and left the
stroke shows up when it shouldn't, and at the bottom and right it doesn't
show up where it should. However, I think this is a separate issue that
could show up anyhow.

This could fix things for the moment at least, until a better solution is
determined.

at this point does it become a fill vs. line problem? (i.e. how pixel
coverage is calculated in PLine?)

can the hack be used to consistently get better results (that is, do you
feel it's safe enough to include as default to improve things 85% of the time?)

The numerical analysis for the scanline rasterization is not being done
properly. This is an old and standard bug when roundoff is not properly
computed, or when insufficient bits are used to represent the coordinates
or when the projective geometry has been done improperly. this bug comes up
in scan conversion and BSpline evaluation when recursively subdividing. I
have been doing this since 1983 and I have seen many students stymied in
graphics classes due to this category of bug.

The tools for fixing it are as follows:
1) use doubles for all scan conversion and upstream projective geometry.
2) when comparing floating point numerical values, always use APX_EQ(x,y)
where the function returns true if x is within an EPSILON of y.
3) round correctly using y = IROUND(x) where IROUND = (int)(x + 0.5) and x
& y are type double.
4) compute EPSILON as a machine dependent parameter using the following:

/* epsilon is 8.04683e-315 on my machine */
/* van@wdv.com from memory of an IEEE signal processing book */
/* no rights reserved
*/

main()
{
double trialEpsilon, actualEpsilon;

for(trialEpsilon = 0.0; trialEpsilon = 0.0 ;trialEpsilon /= 2.0)
{
actualEpsilon = trialEpsilon;
}

printf("%g\n", actualEpsilon);
}

5) "area sample" all projected geometry. There are no points, or lines or
any other objects of zero dimensional width. All renderable objects have
finite width and are clipped against the pixel boundaries. Area sampling
is equivalent to convolving with a rectangular filter kernel. It always
looks really good and isn't expensive when implemented properly.
Oversampling always looks bad. In 1984, Shoichi Kitaoka - now vice
president of Hitachi - and I did an experiment where we looked at pixel
value versus oversampling rate. We rendered images with 1, 2, 4, 16, ...
samples per pixel and asked, when did the image quit changing
substantially? We stopped the experiment at 256 samples per pixel because
it was using too much computer time. It never quit changing substantially.
Lesson? Correctly project and area sample all geometry and make sure
geometry always has finite width enabling the area to be correctly
computed. It will look great. This works even when geometry is manipulated
via affine transformations such as 4 x 4 scaling, translation, rotation and
perspective projection matrices.

(In reply to comment #14)
> can the hack be used to consistently get better results (that is, do you
> feel it's safe enough to include as default to improve things 85% of
the time?)

I thought so at first, though after your comment I decided to check the
difference between stroked rects, non-stroked rects, and lines, and none of
the behaviors match between any of the three renderers, even with this hack
- it brings stability, but not consistency. So to the first part of your
post, yes, there does appear to be an issue with lines vs. shapes. FWIW, I
think the cast that's causing these woes is in PLine.java, line 293. This
might actually be a slightly better place to bias the cast, rather than at
the camera level.

Long story short, I wouldn't put this in at the moment - I'm really not
sure if it will improve things 85%, because I really haven't played around
with it much yet.

I'm going to fight with this a bit more, get a better sense of exactly what
needs to be done, but here's a question for the road: which renderer do you
think we should take to be doing things "correctly" for now? I can
probably bring P3D either in line with OpenGL (as it shows up on my
PowerBook, at least - is hardware used for lines?) or the default 2d
renderer for rectangles, lines, and triangles at least, but we've got to
pick one or the other to match.

Van: as far as area sampling goes...well, you're probably right, area
sampling using double variables is probably prettier (if slower), but
that's really an issue for Ben to rule on, and I'm pretty sure that he
already has - it would represent a fundamental change in the way the
rendering engine works, and I don't think it's likely to happen soon unless
you have a lot of time to donate to the project and he feels like
overseeing something like that. I'll agree with you that "This is an old
and standard bug when roundoff is not properly computed," the problem is
that each renderer currently computes the roundoff differently, and we need
to figure out a way to bring them more or less in line.

Checked into this a bit more, looks like a real fix will be tough -
generally strokes and fills do NOT necessarily cover the same edge pixels
in OpenGL, and there is no perfect way to deal with any of this short of
going soft rasterization. We won't be able to bring all three renderers in
line, but I think we can at least fix up P3D by adding PIXEL_CENTER to the
castee (if that is even a word) before each (int) cast in PLine.draw().
This makes the relative movement of strokes and fills identical, and
offsets them away from the integer boundary (the fills are already behaving
more or less correctly, I think), though they do not have pixel-perfect
overlap (stroked rects seem to be one pixel larger in each direction - same
thing in OpenGL, though). I don't think this should cause any other major
problems, but I'll sit on it and play around some more for a couple days
and let you know.

BTW, van, I'm sure a library that handled area sampling methods as you
outlined would be most welcome if you were up for writing one - it
definitely seems that you know enough about this stuff to put together a
good one.

edit]
point step 1

edit]
point step 2

edit]
point step 3

edit]
point step 4

edit]
line step 1

edit]
line step 2

edit]
line step 3

edit]
line step 4

edit]
line step 5

edit]
line step 6

edit]
line step 7

please stop with the attachments. what are these, and how are they relevant
to fixing the bug?

we're perfectly aware of the bug, the only useful thing to be done at this
point is to fix it.

(From update of edit])
with StrokeWidth=4
a point (x,y) subtends four pixels.

Are you going to open fire? Was I was trying to help fix the sampling bug?

Did the diagrams demonstrate area sampling, step by step?

Does clicking on "View All" show the sequence of steps for points and lines.

Is it a bug that only one diagram at a time can be uploaded?

Can bug reports be made in html?

Can one modify one's remarks without a spam detonation?

Did you embarass and humilate me?

Okay, so here's the situation with this bug. I've come up with a couple
fixes, but unfortunately each of them is suboptimal in some way. The most
"correct" one involves merely changing the line rasterization algorithm a
bit so that the stroking more closely matches OpenGL. Unfortunately this
fixes rect rendering, but more obviously exposes another bug (reported just
now as bug 580).

If bug 580 can get resolved, then the better fix for this bug will be
preferable to the hack in comment 13. Otherwise, that one looks like a
good, if temporary, workaround, though I might see if I can figure out a
better place to do the .01 shift so that it shifts by that many pixels
regardless of the camera settings (which would keep the fix in place even
if you're moving the camera along the xy plane, which might happen somewhat
often; the fix as listed in comment 13 would just turn off if you moved the
camera).

Okay, below I'm going to attach a proposed "fix" for this bug and some code
to test using the fix. It's not perfect, but it should take care of most
of the problems without altering anything at all if you're drawing in
actual 3D. It only alters anything if the transformation matrices are set
so that they leave z=0 points in the screen plane and you're drawing stuff
with z=0.

It would be easy to only apply this stuff if a hint() is set, too, let me
know if you think that's better.

edit]
PGraphics3d and PLine files edited to "fix" bug 95

These are just my current working copies of PGraphics3d.java and PLine.java.
There may be some extra edits in there from other stuff I'm working on - here
are the changes I know about, with line numbers:

PGraphics3D.java:
render_triangles() 1362->1376, 1449-1463
render_lines() 1514->1536
triangulate_polygon() 1612->1641 (triangulation code, corrected weird
form of boolean checks - sorry, this relates to a different bug)
drawing2D() last function in class

PLine.java:
lineClipCode() 486 (fixes a last pixel clipping bug that becomes
obvious when the other changes are applied)

Head to http://www.ewjordan.com/processing/ to see a test applet compiled with
these fixes. Once the applet has focus, press any key to turn off the 2d fix,
you'll see that a lot of stuff goes wrong, most obviously the background (drawn
as a bunch of single lines, hence the crummy frame rate). Most of the shapes
drawn are just there to prove that this fix doesn't break most shapes.

Don't know if this is the greatest fix, but it seems to work if you want to use
it...

now applied in svn. can you give it a look to make sure that things came
through properly? will this also close bug #267?

Things look right based on a browse through the source, but I'll need to
wait until a little later tonight to actually be able to compile and test.
If everything works as I think it should, this should indeed also close
bug 267 (which actually turned out to be a slightly better test case for
this bug since the issue is more obvious there).

I'll let you know soon and try to hit these things pretty hard in the
meantime to make sure nothing slips by...

*** Bug 267 has been marked as a duplicate of this bug. ***

fixed for now thanks to ewjordan. i think this will be as good as can be
done without a complete rewrite.