具有负方向的快速Voxel遍历算法

Question

我试图实现快速体素遍历算法，并根据this answer (T是tDelta，M是tMax)计算T和M。如果方向向量V的两个分量为正，则一切都是好的。但如果其中至少有一个是否定的，那就是错误的。

绿点是起点，红色是终点。一切似乎都是正确的。

​

现在从大到小。

​

遍历方法：

private IEnumerable<Vector2> GetCrossedCells(Vector2 pPoint1, Vector2 pPoint2)
{
    Vector2 V = pPoint2 - pPoint1; // direction & distance vector
    if (V != Vector2.Zero)
    {
        Vector2 U = Vector2.Normalize(V); // direction unit vector
        Vector2 S = new Vector2(Math.Sign(U.X), Math.Sign(U.Y)); // sign vector
        Vector2 P = pPoint1; // position
        Vector2 G = new Vector2((int) Math.Floor(P.X / CELL_SIZE), (int) Math.Floor(P.Y / CELL_SIZE)); // grid coord
        Vector2 T = new Vector2(Math.Abs(CELL_SIZE / U.X), Math.Abs(CELL_SIZE / U.Y));
        Vector2 M = new Vector2(
            Single.IsInfinity(T.X) ? Single.PositiveInfinity : T.X * (1.0f - (P.X / CELL_SIZE) % 1),
            Single.IsInfinity(T.Y) ? Single.PositiveInfinity : T.Y * (1.0f - (P.Y / CELL_SIZE) % 1));

        Vector2 D = Vector2.Zero;
        bool isCanMoveByX = S.X != 0;
        bool isCanMoveByY = S.Y != 0;

        while (isCanMoveByX || isCanMoveByY)
        {
            yield return G;

            D = new Vector2(
                S.X > 0 ? (float) (Math.Floor(P.X / CELL_SIZE) + 1) * CELL_SIZE - P.X :
                S.X < 0 ? (float) (Math.Ceiling(P.X / CELL_SIZE) - 1) * CELL_SIZE - P.X :
                0,
                S.Y > 0 ? (float) (Math.Floor(P.Y / CELL_SIZE) + 1) * CELL_SIZE - P.Y :
                S.Y < 0 ? (float) (Math.Ceiling(P.Y / CELL_SIZE) - 1) * CELL_SIZE - P.Y :
                0);

            if (Math.Abs(V.X) <= Math.Abs(D.X))
            {
                D.X = V.X;
                isCanMoveByX = false;
            }

            if (Math.Abs(V.Y) <= Math.Abs(D.Y))
            {
                D.Y = V.Y;
                isCanMoveByY = false;
            }

            if (M.X <= M.Y)
            {
                M.X += T.X;
                G.X += S.X;
                if (isCanMoveByY)
                {
                    D.Y = U.Y / U.X * D.X; // U.X / U.Y = D.X / D.Y => U.X * D.Y = U.Y * D.X
                }
            }
            else
            {
                M.Y += T.Y;
                G.Y += S.Y;
                if (isCanMoveByX)
                {
                    D.X = U.X / U.Y * D.Y;
                }
            }

            V -= D;
            P += D;
        }
    }
}

在调试中，我可以看到，如果S.X < 0或S.Y <0，则M.Y > M.X应该相反。

请告诉我，我的代码对负向的错误是什么？

Answer 1

，所以，我解决了它。，我使代码更简洁，问题就消失了。

private IEnumerable<Vector2> GetCrossedCells(Vector2 pPoint1, Vector2 pPoint2)
{
    if (pPoint1 != pPoint2)
    {
        Vector2 V = (pPoint2 - pPoint1) / CELL_SIZE; // direction & distance vector
        Vector2 U = Vector2.Normalize(V); // direction unit vector
        Vector2 S = new Vector2(Math.Sign(U.X), Math.Sign(U.Y)); // sign vector
        Vector2 P = pPoint1 / CELL_SIZE; // position in grid coord system
        Vector2 G = new Vector2((int) Math.Floor(P.X), (int) Math.Floor(P.Y)); // grid coord
        Vector2 T = new Vector2(Math.Abs(CELL_SIZE / U.X), Math.Abs(CELL_SIZE / U.Y));
        Vector2 D = new Vector2(
            S.X > 0 ? 1 - P.X % 1 : S.X < 0 ? P.X % 1 : 0,
            S.Y > 0 ? 1 - P.Y % 1 : S.Y < 0 ? P.Y % 1 : 0);
        Vector2 M = new Vector2(
            Single.IsInfinity(T.X) || S.X == 0 ? Single.PositiveInfinity : T.X * D.X,
            Single.IsInfinity(T.Y) || S.Y == 0 ? Single.PositiveInfinity : T.Y * D.Y);

        bool isCanMoveByX = S.X != 0;
        bool isCanMoveByY = S.Y != 0;

        while (isCanMoveByX || isCanMoveByY)
        {
            yield return G;

            D = new Vector2(
                S.X > 0 ? (float) Math.Floor(P.X) + 1 - P.X :
                S.X < 0 ? (float) Math.Ceiling(P.X) - 1 - P.X :
                0,
                S.Y > 0 ? (float) Math.Floor(P.Y) + 1 - P.Y :
                S.Y < 0 ? (float) Math.Ceiling(P.Y) - 1 - P.Y :
                0);

            if (Math.Abs(V.X) <= Math.Abs(D.X))
            {
                D.X = V.X;
                isCanMoveByX = false;
            }

            if (Math.Abs(V.Y) <= Math.Abs(D.Y))
            {
                D.Y = V.Y;
                isCanMoveByY = false;
            }

            if (M.X <= M.Y)
            {
                M.X += T.X;
                G.X += S.X;
                if (isCanMoveByY)
                {
                    D.Y = U.Y / U.X * D.X; // U.X / U.Y = D.X / D.Y => U.X * D.Y = U.Y * D.X
                }
            }
            else
            {
                M.Y += T.Y;
                G.Y += S.Y;
                if (isCanMoveByX)
                {
                    D.X = U.X / U.Y * D.Y;
                }
            }

            V -= D;
            P += D;
        }
    }
}

更新

我从删除GRID_CELL上的冗余除法开始，然后注意到M计算中的错误。在回答问题时使用Frac()函数，这是我提供的链接。我计算它是(1-P% 1)，但这是S> 0的情况，如果S<0时应该有(P % 1)，S= 0应该有Inf。

更新2

也应该有

Vector2 D = new Vector2(
    S.X > 0 ? (float) Math.Floor(P.X) + 1 - P.X :
    S.X < 0 ? (float) Math.Ceiling(P.X) - 1 - P.X :
    0,
    S.Y > 0 ? (float) Math.Floor(P.Y) + 1 - P.Y :
    S.Y < 0 ? (float) Math.Ceiling(P.Y) - 1 - P.Y :
    0);

而不是

Vector2 D = new Vector2(
    S.X > 0 ? 1 - P.X % 1 : S.X < 0 ? P.X % 1 : 0,
    S.Y > 0 ? 1 - P.Y % 1 : S.Y < 0 ? P.Y % 1 : 0);

因为在S<0且P没有分数部分的情况下，M是无穷大的。