« October 2018 | Main

November 07, 2018

判断点是否在三角形内的算法精度问题

今天一个同事反应,在使用 recastnavigation 库时,判断一个点是否在一个三角形内,遇到了精度问题,而且精度误差很大。

具体是 dtClosestHeightPointTriangle 这个函数。

他给出了一组测试参数,abc 三点为 {261.137939, 8.13000488} , {73.6379318, 8.13000488}, {76.9379349, 10.2300053} ,测试 p 为 {74.4069519 , 8.6193819 } 应该在这个三角形内,但是这个函数计算出来并不是。

我看了一下源代码,把这个函数提出来,改写了一点点,方便独立测试。

#include <stdio.h>

// #define float double

static float
dtVdot2D(const float v0[3], const float v1[3]) {
    return v0[0] * v1[0] + v0[2] * v1[2];
}

static float *
dtVsub(float p[3], const float v0[3], const float v1[3]) {
    p[0] = v0[0] - v1[0];
    p[1] = v0[1] - v1[1];
    p[2] = v0[2] - v1[2];
    return p;
}

static int
dtClosestHeightPointTriangle(const float p[3], const float a[3], const float b[3],const float c[3], float *h) {
    float v0[3], v1[3], v2[3];

    dtVsub(v0, c,a);
    dtVsub(v1, b,a);
    dtVsub(v2, p,a);

    float dot00 = dtVdot2D(v0, v0);
    float dot01 = dtVdot2D(v0, v1);
    float dot02 = dtVdot2D(v0, v2);
    float dot11 = dtVdot2D(v1, v1);
    float dot12 = dtVdot2D(v1, v2);

    // Compute barycentric coordinates
    float InvDenom = 1.0f / (dot00 * dot11 - dot01 * dot01);
    float u = (dot11 * dot02 - dot01 * dot12) * InvDenom;
    float v = (dot00 * dot12 - dot01 * dot02) * InvDenom;

    // The (sloppy) epsilon is needed to allow to get height of points which
    // are interpolated along the edges of the triangles.
    float EPS = 1e-4f;

    // If point lies inside the triangle, return interpolated ycoord.
    if (u >= -EPS && v >= -EPS && (u+v) <= 1+EPS) {
        *h = a[1] + (v0[1]*u + v1[1]*v);
        return 1;
    }
    return 0;
}

int
main() {
    float a[2] = {261.137939, 8.13000488};
    float b[2] = {73.6379318, 8.13000488};
    float c[2] = {76.9379349, 10.2300053};
    float p[2] = {74.4069519 , 8.6193819 };
    float h;

    int r = dtClosestHeightPointTriangle(p, a, b, c, &h);

    printf("%d %f\n", r, h);

    return 0;
}

如果你在前面加上 #define float double ,把所有 float 换成双精度,那么测试是可以通过的。

我认为问题出在 dot00 * dot11 - dot01 * dot01 这样的运算上。dot00 点乘已经是单个量的平方,在测试数据中,大约这个量会是 261 - 73 = 188 ,小数点前大约是 8bit 的信息含量,如果我们计算 dot00 * dot11 ,差不多会得到一个这个量的 4 次方的结果,也就是 28bit ~ 32bit 之间。

但是 float 本身的有效精度才 23bit ,对一个 2^32 的数字做加减法,本身的误差就可能在 2 ~ 2^9 左右,这个误差是相当巨大的。

这段程序一个明显可以改进的地方是把乘 InvDenom 从 u v 中去掉,但 Denom 看起来可能是负数,需要增加符号判断。那么代码应该写成:

    float Denom = (dot00 * dot11 - dot01 * dot01);
    float u = (dot11 * dot02 - dot01 * dot12);
    float v = (dot00 * dot12 - dot01 * dot02);

    if (Denom < 0) {
        Denom = -Denom;
        u = -u;
        v = -v;
    }
    float EPS = 1e-4f * Denom ;

    // If point lies inside the triangle, return interpolated ycoord.
    if (u >= -EPS && v >= -EPS && (u+v) <= Denom+EPS) {
        *h = a[1] + (v0[1]*u + v1[1]*v) / Denom;
        return 1;
    }       

光这样写还是不够,其实我们应该进一步把 dot00 * dot11 - dot01 * dot01 展开为 (v0[0] * v1[1] - v0[1] * v1[0]) * (v0[0] * v1[1] - v1[0] * v0[1]) 。这样,就不会在四次方的基础上再做加减法,而是在二次方的基础上先做加减,再做乘法。这样就最大化的保持了精度。

由于简化过后,发现 Denom 是个平方数,一定为正,所以可以去掉符号判断。我优化过的函数是这样的:

static int
dtClosestHeightPointTriangle(const float p[3], const float a[3], const float b[3],const float c[3], float *h) {
    float v0[3], v1[3], v2[3];

    dtVsub(v0, c,a);
    dtVsub(v1, b,a);
    dtVsub(v2, p,a);

    float Denom = (v0[0] * v1[2] - v0[2] * v1[0]) * (v0[0] * v1[2] - v1[0] * v0[2]);
    float u = (v1[0] * v2[2] - v1[2] * v2[0]) * (v1[0] * v0[2] - v0[0] * v1[2]);
    float v = (v0[0] * v2[2] - v0[2] * v2[0]) * (v0[0] * v1[2] - v1[0] * v0[2]);

    float EPS = - 1e-4f * Denom;

    if (u >= EPS && v >= EPS && (u+v) <= Denom - EPS) {
        *h = a[1] + (v0[1]*u + v1[1]*v) / Denom;
        return 1;
    }
    return 0;
}

由于 u,v,denom 都有共同的项 (v0[0] * v1[2] - v1[0] * v0[2]) 可以约掉,能进一步保留精度。但需要处理一下符号问题。所以最终版本是这样的:

static int
dtClosestHeightPointTriangle(const float p[3], const float a[3], const float b[3],const float c[3], float *h) {
    float v0[3], v1[3], v2[3];

    dtVsub(v0, c,a);
    dtVsub(v1, b,a);
    dtVsub(v2, p,a);

    float Denom = v0[0] * v1[2] - v0[2] * v1[0];
    float u = v1[2] * v2[0] - v1[0] * v2[2];
    float v = v0[0] * v2[2] - v0[2] * v2[0];

    if (Denom < 0) {
        Denom = -Denom;
        u = -u;
        v = -v;
    }

    float EPS = - 1e-4f * Denom;

    if (u >= EPS && v >= EPS && (u+v) <= Denom - EPS) {
        *h = a[1] + (v0[1]*u + v1[1]*v) / Denom;
        return 1;
    }
    return 0;
}

最后这个优化版本可以通过测试。

November 06, 2018

Skynet 1.2.0

今天我发布了 skynet 1.2.0。

距离上次发布 1.1.0 已经有一年了。虽然我觉得给 skynet github 仓库里某个特定版本起个有意义的名字并无太大意义,因为我也不会刻意去维护一个所谓稳定版。但在 issues 中还是发现有一些同学还在基于上个 1.1.0 的 release 版提问题,我认为还是保持一年一个版本号比较好。

其实,对于活跃项目,最好的方法还是始终跟进 github 上的 master 比较好。我也刻意在维持代码的向前兼容性。skynet 的 api 已经很稳定,不用太担心更新造成项目跑不起来。话说回来,即使某次更新打破了兼容性,每次一小步的跟进也比隔上一年才同步一次,或是永不升级来得好。

跟进及时可以减少更新带来的新问题。有麻烦可以马上反馈,我更容易帮助解决;不更新容易让 bug 滞留,原本已经解决的 bug 可能在未来再次困扰你。随着 skynet 的用户越来越多,隐藏在犄角旮旯的 bug 更容易被找出来。在 issues 板块,已经有很多问题其实是在 issue 提出时已经被解决了的,仅仅只是因为未更新代码。这种问题无疑浪费了大家的时间。

这次 1.2.0 主要是累积修复了许多 bug 。例如死掉的服务可能在调用过它的服务中残留信息,导致服务地址回滚复用时系统工作不正常。还有 cluster 发包乱序,socket 并发写等问题。这些都是在大量使用时才会发现的 bug 。

另外,mongodb 和 redis 的 driver 都一定程度上增强了。这部分改进的代码都并非来自于我,而是由使用它们的同学根据实际需求完成的。

由于调试需要,我还增加了许多调试相关的指令。在过往的 blog 中都有介绍,可以通过查看本 blog 的 skynet 标签浏览。未来 skynet 的主要发展方向还是以增强运行维护功能为主,核心功能不会有太大改动。

我希望明年的 1.3 版本可以用上 lua 5.4 。这是 lua 的版本大更新,但应该对已有的项目影响不大。lua 5.4 会极大改进 lua 的 gc 效率,更及时的内存回收,能极大减少内存峰值占用。