AT + Area == wrong answer?

Java 2D
#1

When I apply a series of AffineTransforms to an Area, it produces the wrong shape - translated by 0.9999 or so along x or y (which it then rounds to being out-by-1 if I call getBounds() to check it’s dimensions).

It depends where the shape starts in 2D co-ords! I can take a shape, translate it around a bit in increments of 10.f, and in most places tha AT’s + Areas come out exactly as they should - at multiples of 10.0f. At some offsets (so far, anything close to x = 0.0 or y = 0.0), they come out offset by an additional 0.9999.

It could be a problem with javax.vecmath, although I’d have thought it more likely to be J2D, because it’s somethign you’d never notice when painting pixels :slight_smile:

…but you do when you have a zoom mode!

This is really distressing, because if it’s a bug in J2D/J3D/vecmath then, well, I’ve only got a few hours/days to find a workaround (sun game deadline almost upon us!). So, I’m hoping there’s something I’m doing that is an “obvious” source of loss-of-precision…?

FYI Tuple2f, Point2f and Vector2f are from javax.vecmath; everything else is java.awt.geom. The vecmath.jar I’m using is the one from Xith3d.org - but I don’t know where they got it.

First we have the code to create the Area from rectangular shapes (no rotations anywhere).


Tuple2f size = getSize();
Tuple2f sizeHalved = new Point2f( size );
sizeHalved.scale( 0.5f );
return new Area( new Rectangle2D.Float( -sizeHalved.x, -sizeHalved.y, size.x, size.y ) );

And then the code that composites mulitple rectangles:


for( Iterator it=allObjects.iterator(); it.hasNext(); )
{
      GameObject object = (GameObject) it.next();
                  
      Area a = object.area(); // just the code above
                  
      Tuple2f position = object.getPosition();
      AffineTransform toRoomSpace = AffineTransform.getTranslateInstance( position.x, position.y );
                  
      a.transform( toRoomSpace );
      a.transform( roomSpaceToLevelSpace ); // just the code below
                  
      roomArea.add( a );
}

…and here is the pre-calculated roomSpaceToLevelSpace transform:


float cellsize = 10.0f;
levelOffset = new Vector2f( 10.0f, 10.0f );
AffineTransform roomSpaceToLevelSpace = AffineTransform.getScaleInstance( 1.0f / cellsize, 1.0f / cellsize );
roomSpaceToLevelSpace.preConcatenate( AffineTransform.getTranslateInstance( levelOffset.x, levelOffset.y ) );
#2

Update: actually, this is only being used by the editor at the moment, not the game, so I can workaround it by requiring that the user “hold down CTRL to turn off collision-detection” and just hope they are smart enough not to drag and drop a player spawn point into a wall or something equally devastating :wink:

#3

This is how floating point (float and double) calculations work in general unfortunatley. 10 additions of x may not add up exactly to 10*x and so on. The only way to get out if this trouble is to have your own rounding algorithms. I known I always do. This is why you NEVER should count on the equals sign (==) for ANY float/double as a result from a calculation.

Cheers,
Mikael

#4

Good point.

However, none of the floats are larger than about 300, and I’m getting an error of +0.9999 here.

From memory, I thought that floats were a lot better than +/- 1 with calcs only working from 0 to a hundred or so? Unless you started doing lots and lots of multiply/divides?

e.g. AFAICS I never have a float that ever goes above 300 - even as a partial result of an equation during evaluation - so errors should not happen, no?

If I were doing:

translate( 100000f, -45f );

then I would expect to be shot in the head by float errors; but we’re actually deliberately using floats well below 400 (and most of the time, below 50!) to avoid this hassle :(.

#5

[quote]This is how floating point (float and double) calculations work in general unfortunatley. 10 additions of x may not add up exactly to 10*x and so on.
[/quote]
To be precise, divisions of and subtractions of numbers where the numbers are close to each other should be near perfect. Additions and multiplications of numbers that are close to 0 should be near perfect. As you move away from those ranges, things deteriorate.

It’s really nowhere near as bad as 10*x not equalling 10 additions of x … it only depends on how big x is compared to 0 and 10 (and how big 10 is compared to 0…).

But how does that help here? Are you suggesting there is a bug in Java2D’s internal composition of Area objects?

#6

Try: (you’ll be surprised)


System.out.println(0.1 + 0.2);

Here’s a good link if you don’t mind feeling like a calculus student again :wink:

http://docs.sun.com/source/806-3568/ncg_goldberg.html

I just meant that after doing some floting point math on a Rectangle2d.Float (for example) the bounds have to be rounded in the correct way before comparison to some other geometry. For instance you have to decide whether to round to the correct size OR to corner coordinates. Here is a snippet I use, no guarantees of correctnes though.


      /** Converts a Rectangle2D to a Rectangle by rounding its values to the nearest int.
       * @param rect2d The rect to convert. if null, returns null.
       * @param roundToCords If <code>true</code> the returned rectangle is rounded so that the start and end
       * coordinates is as close to the original positions as possible. If it is <code>false</code> the
       * the start coordinates and the width and height is rounded so it is as close to the original values
       * as possible (just rounds x, y, width, height respectively).

       * <code>true</code> is best for rectangles that are painted on a pixel based screen.
       * @return A rectangle as like as rect2D as possible. <code>null</code> only if <code>rect2d</code> is <code>null</code>.
       */
      public static final Rectangle getRoundedRect(RectangularShape rect2d, boolean roundToCords)
      {
            if (rect2d == null)
                  return null;

            if (roundToCords) {
                  double oldX = rect2d.getX();
                  double oldY = rect2d.getY();
                  int newX = (int) (oldX  + 0.5);
                  int newY = (int) (oldY + 0.5);
                  int newWidth =  (int) (oldX + rect2d.getWidth() - newX + 0.5);
                  int newHeight =  (int) (oldY + rect2d.getHeight() - newY + 0.5);
                  return new Rectangle(newX, newY, newWidth, newHeight);

            } else {
                  return new Rectangle((int) (rect2d.getX() + 0.5),
                                                 (int) (rect2d.getY() + 0.5),
                                                 (int) (rect2d.getWidth() + 0.5),
                                                 (int) (rect2d.getHeight() + 0.5));
            }
      }

Cheers,
Mikael

#7

Also, on a side note, you work behind a CRT monitor, not a TFT screen. Not one connected via a DVI cable anyway
:slight_smile:

Cheers,
Mikael

#8

I’m back to calculus for sure anyway, I read 0.9999 as a 0.00001 rounding error. I am now in the know and it may be a bug after all…

#9

[quote]Try: (you’ll be surprised)


System.out.println(0.1 + 0.2);

[/quote]
Apart from the fact that that line of code is not what you’d use (instead I’d only ever do something like println( (0.1f + 02f) ), for reasons to do with how java handles numeric tokens and auto-conversion), I’d be very surprised if it produced anything other than 0.3. Which, thankfully, (using the corrected version I suggested) it does.

What kind of Maths do you think float can be used for if it can’t even do 0.1 + 0.2? ???

OK, but I still don’t understand why rounding has anythign to do with my problems? I should NOT be encountering any error at this scale, AFAICS.

#10

[quote]Also, on a side note, you work behind a CRT monitor, not a TFT screen. Not one connected via a DVI cable anyway
[/quote]
Um, actually I work with a TFT screen which uses what I assume is a digital connect (laptop).

But my point was that an error of +/- 1 pixel is, in practical terms, unnoticeable as long as it is consistent. If it is non-deterministic, then you’d see a “wobbling” of straight lines, and would notice. But if it’s deterministic, the effects are so subtle that without a screenshot (Robot?) based test-suite you could easily not notice it.

Although I didn’t mention it earlier, this is happening in approximately 20% of translation co-ordinates - although I’ve only tried about 30-50 different offsets. So, if you are only manually checking one or two particular offsets (and the rest you assume to be pixel-perfect) then there’s a high chance you wouldn’t notice.

#11

Ok, with floats you can try System.out.println(0.1f + 0.6f);
which results in 0.70000005. :wink:

As i said in my last post, I was on the wrong track thinking it was a normal round off error. The only time rounding can jump 1 (approx) is if there are some intermediate integer conversions, and that would be a bug then.

I work quite a lot with geometry in Java2D and the 1 pixel jumps are a normal thing if rounding to pixel positions aren’t done properly, that’s why I just jumped to that conclusion. The floating point positions are never of by more than 0.0000001 or so, though.

Sorry for messing up your thread.

The CRT thing has to do with JPEG artifacts for textual graphics usually lookes fine on a CRT, but bad on a TFT. I just browsed your site, which on my monitor (24" TFT) suffer from those artifacts in the top left grexengine logo. You might want to use .png or .gif for those logos to get rid of the artifacts and probably get smaller images as well.

Cheers,
Mikael