java - 处理浮点精度问题(测试与SAT的碰撞)

Question

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

Shape 是处理凸网格的接口(interface)，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;
  }
}

谢谢

附注:

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

解决方案如下:

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;
  }
}

Answer 1

第一个想法是使用double而不是float来提高准确性。