3

我在 3D 空间中有一个 2D 凸多边形和一个测量多边形面积的函数。

public double area() {
    if (vertices.size() >= 3) {
        double area = 0;
        Vector3 origin = vertices.get(0);
        Vector3 prev = vertices.get(1).clone();
        prev.sub(origin);
        for (int i = 2; i < vertices.size(); i++) {
            Vector3 current = vertices.get(i).clone();
            current.sub(origin);
            Vector3 cross = prev.cross(current);
            area += cross.magnitude();
            prev = current;
        }
        area /= 2;
        return area;
    } else {
        return 0;
    }
}

为了测试这个方法是否适用于多边形的所有方向,我让我的程序在每次迭代时将它旋转一点并计算面积。像这样...

Face f = poly.getFaces().get(0);
        for (int i = 0; i < f.size(); i++) {
            Vector3 v = f.getVertex(i);
            v.rotate(0.1f, 0.2f, 0.3f);
        }
        if (blah % 1000 == 0)
            System.out.println(blah + ":\t" + f.area());

使用 20x20 正方形进行测试时,我的方法似乎是正确的。然而,rotate 方法(Vector3 类中的一种方法)似乎会在多边形中每个顶点的位置引入一些误差,从而影响面积计算。这是 Vector3.rotate() 方法

public void rotate(double xAngle, double yAngle, double zAngle) {
    double oldY = y;
    double oldZ = z;
    y = oldY * Math.cos(xAngle) - oldZ * Math.sin(xAngle);
    z = oldY * Math.sin(xAngle) + oldZ * Math.cos(xAngle);

    oldZ = z;
    double oldX = x;
    z = oldZ * Math.cos(yAngle) - oldX * Math.sin(yAngle);
    x = oldZ * Math.sin(yAngle) + oldX * Math.cos(yAngle);

    oldX = x;
    oldY = y;
    x = oldX * Math.cos(zAngle) - oldY * Math.sin(zAngle);
    y = oldX * Math.sin(zAngle) + oldY * Math.cos(zAngle);
}

这是我的程序的输出,格式为“迭代:区域”:

0:  400.0
1000:   399.9999999999981
2000:   399.99999999999744
3000:   399.9999999999959
4000:   399.9999999999924
5000:   399.9999999999912
6000:   399.99999999999187
7000:   399.9999999999892
8000:   399.9999999999868
9000:   399.99999999998664
10000:  399.99999999998386
11000:  399.99999999998283
12000:  399.99999999998215
13000:  399.9999999999805
14000:  399.99999999998016
15000:  399.99999999997897
16000:  399.9999999999782
17000:  399.99999999997715
18000:  399.99999999997726
19000:  399.9999999999769
20000:  399.99999999997584

由于这最终打算用于物理引擎,因此我想知道如何将累积误差最小化,因为 Vector3.rotate() 方法将定期使用。

谢谢!

几个奇怪的笔记:

  • 误差与旋转量成正比。IE。每次迭代更大的旋转 -> 每次迭代更大的错误。

  • 将双精度值传递给旋转函数比传递浮点数时出错更多。

4

2 回答 2

9

重复的浮点触发操作总是会产生一些累积错误——这就是它们的工作方式。要处理它,您基本上有两种选择:

  1. 忽略它。请注意,在您的示例中,经过 20,000 次迭代(!),该区域仍然精确到小数点后 13 位。这还不错,考虑到双打只能存储大约 16 位小数以.

    实际上,绘制图表时,正方形的面积似乎或多或少呈线性下降:
    阴谋
    这是有道理的,假设您的近似旋转矩阵的有效行列式约为 1 − 3.417825 × 10 -18,这在正常范围内双精度浮点误差范围一。如果是这种情况,您的正方形面积将继续以非常缓慢的指数衰减到零,因此您需要大约20 亿 (2 × 10 9 )7.3 × 10 14次迭代,使面积降至 399。假设每秒迭代 100 次,大约是七个半月23万年。

    编辑:当我第一次计算该区域达到 399 需要多长时间时,似乎我犯了一个错误,并且以某种方式设法将衰减​​率高估了大约 400,000 倍(!)。我已经纠正了上面的错误。

  2. 如果你仍然觉得你不想要任何累积错误,答案很简单:不要迭代浮点旋转。相反,让您的对象将其当前方向存储在成员变量中,并使用该信息始终将对象从其原始方向旋转到当前方向。

    这在 2D 中很简单,因为您只需要存储一个角度。在 3D 中,我建议存储一个四元数或一个矩阵,并偶尔重新调整它,使其范数/行列式保持大约 1(并且,如果您使用矩阵来表示刚体的方向,它仍然近似正交)。

    当然,这种方法不会消除对象方向的累积误差,但重新缩放确实可以确保对象的体积、面积和/或形状不会受到影响。

于 2012-04-08T11:28:17.450 回答
1

你说有累积误差,但我不相信有(注意你的输出并不总是下降),其余的错误只是由于浮点数的舍入和精度损失。

我确实在大学(在 java 中)研究了一个 2d 物理引擎,发现 double 更精确(当然是看到oracles 数据类型大小

简而言之,您将永远无法摆脱这种行为,您只需要接受精度的限制

编辑:

现在我看看你的 .area 函数,由于

+= cross.magnitude

但我不得不说整个函数看起来有点奇怪。为什么需要知道之前的顶点来计算当前面积?

于 2012-04-08T10:26:44.867 回答