routemap.cpp.svn-base

坦克大战游戏完整全套源代码

                if (e.va >= numOriginalVertices)
                {
                    if (DistancePointToEdge(e.va, polyEdge) < 0.1f)
                        continue;
                }
                if (e.vb >= numOriginalVertices)
                {
                    if (DistancePointToEdge(e.vb, polyEdge) < 0.1f)
                        continue;
                }

                Point2f crossPoint;
                if (LineCrossPoint(e, polyEdge, crossPoint)) // 求交点
                {
                    edgeIds2.push_back(eid);
                    break;
                }
            }
        }

        if (edgeIds2.size() == edgeIds.size() && tryCount-- == 0)
            break;

        // 尝试旋转这些边，如果旋转成功，则再检测一次
        for (i = 0; i < edgeIds2.size(); i++)
        {
            size_t eid = edgeIds2[i];
            // 如果无法旋转（比如边缘的边），那么不必再考虑它了
            // 不过实际情况是，边缘的边 *不可能* 与任何多边形相交。若相交，则它两侧必然存在顶点，于是会得到两侧的三角形。
            if (turnEdge(edges[eid]))
            {
                // 如果旋转成功，那么加入数组再检测一次
                //edgeIds.push_back(eid);
            }
            else
            {
                //edges[eid].failedToTurn = true;
            }
        }
        edgeIds = edgeIds2;
        edgeIds2.clear();
    }
#endif
    for (i = 0; i < edgeIds2.size(); i++)
    {
        edges[edgeIds2[i]].bBad = true;
    }

    for (i = 0; i < edges.size(); i++)
    {
        const Edge &e = edges[i];
        space.addEntity(i, DT_Edge, getBoundingBox(e));
        if (e.t0 != size_t(-1))
        {
            assert(e.t0 < triangles.size());
            Triangle &t = triangles[e.t0];
            for (int j = 0; j < 3; j++)
            {
                if (t.e[j] == i)
                {
                    t.t[j] = e.t1;
                    break;
                }
            }
        }
        if (e.t1 != size_t(-1))
        {
            assert(e.t1 < triangles.size());
            Triangle &t = triangles[e.t1];
            for (int j = 0; j < 3; j++)
            {
                if (t.e[j] == i)
                {
                    t.t[j] = e.t0;
                    break;
                }
            }
        }
    }

    for (i = 0; i < triangles.size(); i++)
    {
        Triangle &t = triangles[i];
        const Point2f pos = getCenter(t);
        vector<size_t> result;
        MapObjCuller culler(result);
        culler.dataType = DT_Poly;
        culler.viewer.leftTop = pos + Point2f(-1.f, -1.f);
        culler.viewer.rightBottom = pos + Point2f(1.f, 1.f);
        space.cull(culler);
        t.block = 0;
        for (size_t j = 0; j < result.size(); j++)
        {
            size_t id = result[j];
            assert(id < polygons.size());
            if (insidePolygon(pos, polygons[id]) || 
                insidePolygon(lerp(verticesBuffer[t.v[Triangle::PointA]], pos, 0.1f), polygons[id]) || 
                insidePolygon(lerp(verticesBuffer[t.v[Triangle::PointB]], pos, 0.1f), polygons[id]) || 
                insidePolygon(lerp(verticesBuffer[t.v[Triangle::PointC]], pos, 0.1f), polygons[id]))
            {
                t.block = 1;
                cc++;
                break;
            }
        }
        space.addEntity(i, t.block ? DT_BlockTriangle : DT_RouteTriangle, getBoundingBox(t));
        t.t[0] = t.t[1] = t.t[2] = size_t(-1);
    }
    for (i = 0; i < edges.size(); i++)
    {
        const Edge &e = edges[i];
        // connect 2 triangles
        size_t t0 = e.t0;
        size_t t1 = e.t1;
        size_t eid = i;
        if (t0 < triangles.size() && t1 < triangles.size())
        {
            Triangle &tri0 = triangles[t0];
            Triangle &tri1 = triangles[t1];
            if (tri0.block || tri1.block)
                continue;

            SET_NEIGHBOUR_TRIANGLE(tri0, t1);
            SET_NEIGHBOUR_TRIANGLE(tri1, t0);
        }
    }
#undef SET_NEIGHBOUR_TRIANGLE
}

bool RouteMap::turnEdge(Edge &e)
{
    if (e.t0 == size_t(-1) || e.t1 == size_t(-1))
        return false;

    assert(e.t0 != e.t1);
    assert(e.t0 < triangles.size());
    assert(e.t1 < triangles.size());
    Triangle &tri0 = triangles[e.t0];
    Triangle &tri1 = triangles[e.t1];
/*
    // t0a, t0b, t1a, t1b分别是两个三角形的邻接三角形
    size_t i0a = Triangle::EdgeBC, i0b = Triangle::EdgeAC;
    if (tri0.e[i0a] == e.t1)
        t0a = tri0.t + Triangle::EdgeAB;
    else if (*t0b == e.t1)
        t0b = tri0.t + Triangle::EdgeAB;

    size_t *t1a = tri1.t + Triangle::EdgeBC, *t1b = tri1.t + Triangle::EdgeAC;
    if (*t1a == e.t0)
        t1a = tri1.t + Triangle::EdgeAB;
    else if (*t1b == e.t0)
        t1b = tri1.t + Triangle::EdgeAB;

    // 如果邻接三角形相同，则不能turn本条边
    if (*t0a != size_t(-1) && (*t0a == *t1a || *t0a == *t1b) ||
        *t0b != size_t(-1) && (*t0b == *t1a || *t0b == *t1b))
        return false;
*/
    // turn the edge
    size_t va = e.va, vb = e.vb;
    const size_t *v0 = tri0.v, *v1 = tri1.v; // 两个三角形各自独立的点
#define GET_SINGLE_VERTEX(tri, vx)                                                  \
    if (tri.v[Triangle::PointA] == va)                                              \
    {                                                                               \
        assert(tri.v[Triangle::PointB] == vb || tri.v[Triangle::PointC] == vb);     \
        vx += (tri.v[Triangle::PointB] == vb ? Triangle::PointC : Triangle::PointB);\
    }                                                                               \
    else if (tri.v[Triangle::PointB] == va)                                         \
    {                                                                               \
        assert(tri.v[Triangle::PointA] == vb || tri.v[Triangle::PointC] == vb);     \
        vx += (tri.v[Triangle::PointA] == vb ? Triangle::PointC : Triangle::PointA);\
    }                                                                               \
    else                                                                            \
    {                                                                               \
        assert(tri.v[Triangle::PointC] == va);                                      \
        assert(tri.v[Triangle::PointA] == vb || tri.v[Triangle::PointB] == vb);     \
        vx += (tri.v[Triangle::PointA] == vb ? Triangle::PointB : Triangle::PointA);\
    }

    GET_SINGLE_VERTEX(tri0, v0);
    GET_SINGLE_VERTEX(tri1, v1);
#undef GET_SINGLE_VERTEX

    {
        const Point2f &pa = verticesBuffer[va];
        const Point2f &pb = verticesBuffer[vb];
        const Point2f &p0 = verticesBuffer[*v0];
        const Point2f &p1 = verticesBuffer[*v1];
        const Point2f a1 = pa - p1;
        const Point2f b1 = pb - p1;
        const Point2f _01 = p0 - p1;
        if ((a1 ^ _01) * (_01 ^ b1) < 0) // 不能转到三角形之外。
            return false;
    }

    e.va = *v0;
    e.vb = *v1;
    if (e.va > e.vb)
        swap(e.va, e.vb);

    int i0c = 0, i1c = 0; // 两个三角形需要交换的邻接三角形和
    // turn the triangles
#define SWAP_AND_GET_EDGE(_tri, _vb, _va, _i0c, _v1)                                    \
    if (_tri.v[Triangle::PointA] == _vb)                                                \
    {                                                                                   \
        _tri.v[Triangle::PointA] = *_v1;                                                \
        /*swap(_tri.t[Triangle::EdgeAC], _tri.t[Triangle::EdgeAB]); */                  \
        swap(_tri.e[Triangle::EdgeAC], _tri.e[Triangle::EdgeAB]);                       \
        assert(_tri.v[Triangle::PointB] == _va || _tri.v[Triangle::PointC] == _va);     \
        _i0c = _tri.v[Triangle::PointB] == _va ? Triangle::EdgeAB : Triangle::EdgeAC;   \
    }                                                                                   \
    else if (_tri.v[Triangle::PointB] == _vb)                                           \
    {                                                                                   \
        _tri.v[Triangle::PointB] = *_v1;                                                \
        /*swap(_tri.t[Triangle::EdgeBC], _tri.t[Triangle::EdgeAB]); */                  \
        swap(_tri.e[Triangle::EdgeBC], _tri.e[Triangle::EdgeAB]);                       \
        assert(_tri.v[Triangle::PointA] == _va || _tri.v[Triangle::PointC] == _va);     \
        _i0c = _tri.v[Triangle::PointA] == _va ? Triangle::EdgeAB : Triangle::EdgeBC;   \
    }                                                                                   \
    else                                                                                \
    {                                                                                   \
        assert(_tri.v[Triangle::PointC] == _vb);                                        \
        _tri.v[Triangle::PointC] = *_v1;                                                \
        /*swap(_tri.t[Triangle::EdgeAC], _tri.t[Triangle::EdgeBC]); */                  \
        swap(_tri.e[Triangle::EdgeAC], _tri.e[Triangle::EdgeBC]);                       \
        assert(_tri.v[Triangle::PointB] == _va || _tri.v[Triangle::PointA] == _va);     \
        _i0c = _tri.v[Triangle::PointB] == _va ? Triangle::EdgeBC : Triangle::EdgeAC;   \
    }

    SWAP_AND_GET_EDGE(tri0, vb, va, i0c, v1);
    SWAP_AND_GET_EDGE(tri1, va, vb, i1c, v0);
#undef SWAP_AND_GET_EDGE

    //swap(tri0.t[i0c], tri1.t[i1c]);
    swap(tri0.e[i0c], tri1.e[i1c]);
#if 0
    if (tri0.t[i0c] != size_t(-1))
    {
        Triangle &tOther = triangles[tri0.t[i0c]];
        if (tOther.t[Triangle::EdgeBC] == e.t1)
            tOther.t[Triangle::EdgeBC] = e.t0;
        else if (tOther.t[Triangle::EdgeAC] == e.t1)
            tOther.t[Triangle::EdgeAC] = e.t0;
        else if (tOther.t[Triangle::EdgeAB] == e.t1)
            tOther.t[Triangle::EdgeAB] = e.t0;
        else if (tOther.t[Triangle::EdgeBC] == e.t0)
            tOther.t[Triangle::EdgeBC] = e.t1;
        else if (tOther.t[Triangle::EdgeAC] == e.t0)
            tOther.t[Triangle::EdgeAC] = e.t1;
        else if (tOther.t[Triangle::EdgeAB] == e.t0)
            tOther.t[Triangle::EdgeAB] = e.t1;
        else assert(0);
    }

    if (tri0.t[i1c] != size_t(-1))
    {
        Triangle &tOther = triangles[tri0.t[i1c]];
        if (tOther.t[Triangle::EdgeBC] == e.t0)
            tOther.t[Triangle::EdgeBC] = e.t1;
        else if (tOther.t[Triangle::EdgeAC] == e.t0)
            tOther.t[Triangle::EdgeAC] = e.t1;
        else if (tOther.t[Triangle::EdgeAB] == e.t0)
            tOther.t[Triangle::EdgeAB] = e.t1;
        else if (tOther.t[Triangle::EdgeBC] == e.t1)
            tOther.t[Triangle::EdgeBC] = e.t0;
        else if (tOther.t[Triangle::EdgeAC] == e.t1)
            tOther.t[Triangle::EdgeAC] = e.t0;
        else if (tOther.t[Triangle::EdgeAB] == e.t1)
            tOther.t[Triangle::EdgeAB] = e.t0;
        else assert(0);
    }
#endif
    if (tri0.e[i0c] != size_t(-1))
    {
        Edge &e1 = edges[tri0.e[i0c]];
        assert(e1.t0 == e.t1 || e1.t1 == e.t1 || e1.t0 == e.t0 || e1.t1 == e.t0);
        if (e1.t0 == e.t1)
        {
            assert(e1.t1 != e.t0);
            e1.t0 = e.t0;
        }
        else if (e1.t1 == e.t1)
        {
            assert(e1.t0 != e.t0);
            e1.t1 = e.t0;
        }
        else if (e1.t0 == e.t0)
        {
            assert(e1.t1 != e.t0);
            e1.t0 = e.t1;
        }
        else if (e1.t1 == e.t0)
        {
            assert(e1.t0 != e.t0);
            e1.t1 = e.t1;
        }
        assert(e1.t0 != e1.t1);
    }
    if (tri1.e[i1c] != size_t(-1))
    {
        Edge &e2 = edges[tri1.e[i1c]];
        assert(e2.t0 == e.t1 || e2.t1 == e.t1 || e2.t0 == e.t0 || e2.t1 == e.t0);
        if (e2.t0 == e.t1)
        {
            assert(e2.t1 != e.t0);
            e2.t0 = e.t0;
        }
        else if (e2.t1 == e.t1)
        {
            assert(e2.t0 != e.t0);
            e2.t1 = e.t0;
        }
        else if (e2.t0 == e.t0)
        {
            assert(e2.t1 != e.t0);
            e2.t0 = e.t1;
        }
        else if (e2.t1 == e.t0)
        {
            assert(e2.t0 != e.t0);
            e2.t1 = e.t1;
        }
        assert(e2.t0 != e2.t1);
    }
    return true;
}