0

我正在寻找有关跟踪浮点精度泄漏的建议（一个棘手的错误？）。以下代码会导致非常接近的物体出现误报。

Shape 是处理凸网格的接口，Shape.getRange 计算一些点积。

public class SAT
{
  public static boolean areRangesOverlapping( float[] range0, float[] range1 )
  {
    if( range0[1] < range1[0] )
      return false;

    if( range1[1] < range0[0] )
      return false;

    return true;
  }

  public static boolean areShapesColliding( Shape shape0, Matrix4 shapeMatrix0, Shape shape1, Matrix4 shapeMatrix1 )
  {
    float[] range0 = new float[ 2 ];
    float[] range1 = new float[ 2 ];

    Matrix4 shape0To1 = new Matrix4()
      .inverse( shapeMatrix0, 1e-3f )
      .multiply( shapeMatrix1 );

    Matrix4 shape1To0 = new Matrix4()
      .inverse( shapeMatrix1, 1e-3f )
      .multiply( shapeMatrix0 );

    Matrix3 normal0To1 = new Matrix3()
      .setRotationAndScale( shape0To1 )
      .inverse( 1e-3f )
      .transpose();

    Matrix3 normal1To0 = new Matrix3()
      .setRotationAndScale( shape1To0 )
      .inverse( 1e-3f )
      .transpose();

    Vector3 center0 = shape0.getCenter();

    Vector3 center1 = new Vector3()
      .fromP3toR3( new Vector4()
        .multiply( shape0To1, new Vector4( center0, 1.f ) )
      );

    for( int i = 0; i < shape0.getCount(); ++i )
    {
      Vector3 direction0 = shape0.getDirection( i );

      Vector3 direction1 = new Vector3()
        .multiply( normal0To1, direction0 );

      shape0.getRange( center0, direction0, range0 );
      shape1.getRange( center1, direction1, range1 );

      if( !areRangesOverlapping( range0, range1 ) )
        return false;
    }

    center1 = shape1.getCenter();

    center0 = new Vector3()
      .fromP3toR3( new Vector4()
        .multiply( shape1To0, new Vector4( center1, 1.f ) )
      );

    for( int i = 0; i < shape1.getCount(); ++i )
    {
      Vector3 direction1 = shape1.getDirection( i );

      Vector3 direction0 = new Vector3()
        .multiply( normal1To0, direction1 );

      shape0.getRange( center0, direction0, range0 );
      shape1.getRange( center1, direction1, range1 );

      if( !areRangesOverlapping( range0, range1 ) )
        return false;
    }

    return true;
  }
}

谢谢

PS：

这不是浮点精度问题，而是一个大错误。我忘了处理边缘到边缘的情况。无论如何，用双精度数替换所有浮点数为解决问题提供了一些很好的提示。

这是解决方案：

public class SAT
{
  public static boolean areRangesOverlapping( float[] range0, float[] range1 )
  {
    if( range0[1] < range1[0] )
      return false;

    if( range1[1] < range0[0] )
      return false;

    return true;
  }

  public static boolean areShapesColliding( Shape shape0, Matrix4 position0ToW, Shape shape1, Matrix4 position1ToW )
  {
    float[] range0 = new float[ 2 ];
    float[] range1 = new float[ 2 ];

    Matrix4 position0To1 = new Matrix4()
      .inverse( position1ToW, 1e-3f )
      .multiply( position0ToW );

    Matrix4 position1To0 = new Matrix4()
      .inverse( position0To1, 1e-3f );

    Matrix3 normal0To1 = new Matrix3()
      .setRotationAndScale( position0To1 )
      .inverse( 0.f )
      .transpose();

    Matrix3 normal1To0 = new Matrix3()
      .setRotationAndScale( position1To0 )
      .inverse( 0.f )
      .transpose();

    // Face-to-face, Face-to-edge
    //
    Vector3 center0 = shape0.getCenter();

    Vector3 center1 = new Vector3()
      .fromP3toR3( new Vector4()
        .multiply( position0To1, new Vector4( center0, 1.f ) )
      );

    for( int i = 0; i < shape0.getFaceCount(); ++i )
    {
      Vector3 direction0 = shape0.getFaceDirection( i );

      Vector3 direction1 = new Vector3()
        .multiply( normal0To1, direction0 );

      shape0.getRange( center0, direction0, range0 );
      shape1.getRange( center1, direction1, range1 );

      if( !areRangesOverlapping( range0, range1 ) )
        return false;
    }

    center1 = shape1.getCenter();

    center0 = new Vector3()
      .fromP3toR3( new Vector4()
        .multiply( position1To0, new Vector4( center1, 1.f ) )
      );

    for( int i = 0; i < shape1.getFaceCount(); ++i )
    {
      Vector3 direction1 = shape1.getFaceDirection( i );

      Vector3 direction0 = new Vector3()
        .multiply( normal1To0, direction1 );

      shape0.getRange( center0, direction0, range0 );
      shape1.getRange( center1, direction1, range1 );

      if( !areRangesOverlapping( range0, range1 ) )
        return false;
    }

    // Edge-to-edge
    //
    center0 = shape0.getCenter();    

    center1 = new Vector3()
      .fromP3toR3( new Vector4()
        .multiply( position0To1, new Vector4( center0, 1.f ) )
      );

    for( int e0 = 0; e0 < shape0.getEdgeCount(); ++e0 )
    {
      Vector3 edge0 = shape0.getEdgeDirection( e0 );

      for( int e1 = 0; e1 < shape1.getEdgeCount(); ++e1 )
      {
        Vector3 edge1 = new Vector3()
          .multiply( normal1To0, shape1.getEdgeDirection( e1 ) );

        Vector3 direction0 = new Vector3()
          .cross( edge0, edge1 );

        Vector3 direction1 = new Vector3()
          .multiply( normal0To1, direction0 );

        shape0.getRange( center0, direction0, range0 );
        shape1.getRange( center1, direction1, range1 );

        if( !areRangesOverlapping( range0, range1 ) )
          return false;
      }
    }

    return true;
  }
}
4

3 回答 3

2

第一个想法是通过使用doubles 而不是floats 来提高准确性。

于 2013-09-30T20:37:40.860 回答
1

当您比较浮点数时，您必须选择一些“公差精度”。您可以在此处阅读有关该问题的信息

我的意思是：

final float TOLERANCE = 0.00001f;

if (range1[0] - range0[1]  > TOLERANCE)
    return false;

if (range0[0] - range1[1] > TOLERANCE)
    return false;
于 2013-09-30T20:42:39.857 回答
0

如果BigDecimal您有十进制数字并且想要避免精度问题，请使用。否则，无论您是否有float或double，您总是会在比较和某些算术运算方面遇到困难。

于 2013-09-30T20:47:21.047 回答