时间戳

首页 > 解决方案 > 如何修复我的 3D 光线投射算法以获取玩家正在查看的方块

c# - 如何修复我的 3D 光线投射算法以获取玩家正在查看的方块

问题描述

我用于计算玩家正在查看哪个方块（基于体素的世界）的算法无法正常工作。我已将本教程中的 2D 改编为 3D。有时它会显示正确的块，但有时它要么什么都不返回，要么是完全不同的方向，为什么会发生这种情况？

public (Block, Box?) GetLookAtBlock(Vector3 pos, Vector3 look) {
    try {
        look = look.Normalized() * 4;

        float deltaX = Math.Abs(look.Normalized().X);
        float deltaY = Math.Abs(look.Normalized().Y);
        float deltaZ = Math.Abs(look.Normalized().Z);

        int stepX, stepY, stepZ;
        float distX, distY, distZ;

        if (look.X < 0) {
            distX = (pos.X - SandboxMath.RoundDown(pos.X)) * deltaX;
            stepX = -1;
        } else {
            distX = (SandboxMath.RoundDown(pos.X) + 1 - pos.X) * deltaX;
            stepX = 1;
        }

        if (look.Y < 0) {
            distY = (pos.Y - SandboxMath.RoundDown(pos.Y)) * deltaY;
            stepY = -1;
        } else {
            distY = (SandboxMath.RoundDown(pos.Y) + 1 - pos.Y) * deltaY;
            stepY = 1;
        }

        if (look.Z < 0) {
            distZ = (pos.Z - SandboxMath.RoundDown(pos.Z)) * deltaZ;
            stepZ = -1;
        } else {
            distZ = (SandboxMath.RoundDown(pos.Z) + 1 - pos.Z) * deltaZ;
            stepZ = 1;
        }

        int endX = SandboxMath.RoundDown(pos.X + look.X);
        int endY = SandboxMath.RoundDown(pos.Y + look.Y);
        int endZ = SandboxMath.RoundDown(pos.Z + look.Z);

        int x = (int)pos.X;
        int y = (int)pos.Y;
        int z = (int)pos.Z;

        Block start = GetBlock(x, y, z);

        if (start != 0) {
            return (start, new Box(new Vector3(x, y, z), new Vector3(x + 1, y + 1, z + 1)));
        }

        while (x != endX && y != endY && z != endZ) {
            if (distX < distY) {
                if (distX < distZ) {
                    distX += deltaX;
                    x += stepX;
                } else {
                    distZ += deltaZ;
                    z += stepZ;
                }
            } else {
                if (distY < distZ) {
                    distY += deltaY;
                    y += stepY;
                } else {
                    distZ += deltaZ;
                    z += stepZ;
                }
            }

            Block b = GetBlock(x, y, z);
            if (b != 0) {
                return (b, new Box(new Vector3(x, y, z), new Vector3(x + 1, y + 1, z + 1)));
            }
        }

        return (0, null);
    } catch (IndexOutOfRangeException) {
        return (0, null);
    }
}

标签： c#mathgame-physicsphysicsraycasting

解决方案

乍一看，您的DDA有两个问题：

  1. 仅当 Z 为主轴时才有效

    所以只有当你在相机空间或者有固定的相机在 Z 方向看

  2. 你的三角洲很奇怪

    为什么：

    delta? = abs(1 / look.Normalized().?);

    我希望：

    delta? = abs(look.Normalized().?);

我不会用C#编写代码，所以我没有信心修复您的代码，但是这里是我的-dimensional DDA的C++模板，所以只需根据它比较和修复您的...n

template<const int n>class DDA
    {
public:
    int p0[n],p1[n],p[n];
    int d[n],s[n],c[n],ix;

    DDA(){};
    DDA(DDA& a) { *this=a; }
    ~DDA(){};
    DDA* operator = (const DDA *a) { *this=*a; return this; }
    //DDA* operator = (const DDA &a) { ..copy... return this; }

    void start()
        {
        int i;
        for (ix=0,i=0;i<n;i++)
            {
            p[i]=p0[i];  s[i]= 0; d[i]=p1[i]-p0[i];
            if (d[i]>0)  s[i]=+1;
            if (d[i]<0){ s[i]=-1; d[i]=-d[i]; }
            if (d[ix]<d[i]) ix=i;
            }
        for (i=0;i<n;i++) c[i]=d[ix];
        }
    void start(double *fp0) // this will add the subpixel offset according to first point as double
        {
        int i; start();
        for (i=0;i<n;i++)
            {
            if (s[i]<0) c[i]=double(double(d[ix])*(    fp0[i]-floor(fp0[i])));
            if (s[i]>0) c[i]=double(double(d[ix])*(1.0-fp0[i]+floor(fp0[i])));
            }
        }

    bool update()
        {
        int i;
        for (i=0;i<n;i++){ c[i]-=d[i]; if (c[i]<=0){ c[i]+=d[ix]; p[i]+=s[i]; }}
        return (p[ix]!=p1[ix]+s[ix]);
        }
    };

start()初始化DDA的变量和位置（来自p0,p1控制点），这update()只是DDA的一个步骤......结果迭代点在p

s是步长，d是增量，c是计数器，ix是长轴索引。

用法是这样的：

DDA<3> A; // 3D
A.p0[...]=...; // set start point
A.p1[...]=...; // set end point

for (A.start();A.update();)
 {
 A.p[...]; // here use the iterated point
 }

DDA 通过

好吧，DDA只是两个端点 ( p0, ) 之间某条线上的整数位置的插值（光栅化p1）。直线方程是这样的：

p(t) = p0 + t*(p1-p0);
t = <0.0,1.0>

然而，这涉及到浮动数学，我们想要整数，所以我们可以重写为这样的东西：

dp = p1-p0
D  = max (|dp.x|,|dp.y|,|dp.z|,...)
p.x(i) = p0.x + (dp.x*i)/D
p.y(i) = p0.y + (dp.y*i)/D
p.z(i) = p0.z + (dp.z*i)/D
...
i = { 0,1,...D }

在哪里i,D匹配主轴（变化最大的轴）。如果您仔细观察，我们使用*i/D的是慢速操作，我们通常需要速度，因此我们可以将 therm（利用i从 0 到 D 的顺序）重写为类似的东西（对于 x 轴，只有其他轴是相同的具有不同的索引...）：

p.x=p0.x;                          // start position
s.x=0; d.x=p1.x-p0.x;              // step and abs delta
if (d.x>0) s.x=+1;
if (d.x<0){ s.x=-1; d.x=-d.x; }
D = max(d.x,d.y,d.z,...);          // major axis abs delta
c.x=D;                             // counter for the iteration
for (i=0;i<D;i++)
 {
 c.x-=d.x;                         // update counter with axis abs delta
 if (c.x<=0)                       // counter overflowed?
  {
  c.x+=D;                          // update counter with major axis abs delta
  p.x+=s.x;                        // update axis by step
  }
 }

现在仔细看看c我们正在添加D和减去的计数器，d.x它被i/D重写为D迭代。所有其他轴都以相同的方式计算，您只需为每个轴添加计数器c步长s和绝对增量......d

顺便说一句，如果它有助于看看这个：

  • 体积 GLSL 背光线追踪器

    这是（我假设）你在做什么，但在 GLSL 着色器中实现（参见片段代码）但是它不使用DDA，而是将单位方向向量添加到初始位置，直到碰到某些东西或体素空间的结尾......

顺便说一句，它基于：

就像你的链接一样。

[编辑] 错误点击（根据您的评论猜测）

这很可能与DDA无关。当您直接站在单元格交叉处或错误地截断位置或错误地对命中进行 z 排序时，它更像是边缘情况。我记得我遇到了麻烦。我最终在GLSL中得到了非常奇怪的解决方案，请参阅上面的链接并查看片段代码。寻找

// YZ plane voxels hits

它直接在非“DDA”射线投射代码之后。它检测体素的哪个平面会被击中我认为你应该做类似的事情。这很奇怪，因为在 2D DOOM 中（也在上面的链接中）我没有这样的问题......但这是因为它们是通过使用不同的数学来解决的（仅适用于 2D）。

光线投射之前的 GLSL 代码稍微改变了位置以避免边缘情况。注意floorandceil但是我的工作是浮点数，所以它需要对 int 数学进行一些调整。幸运的是，我正在基于此修复我的其他光线投射引擎：

解决方法是通过光线的亚像素起始位置偏移DDA。我更新了上面的DDA代码，新用法是：

DDA<3> A; // 3D
A.p0[...]=...; // set start point
A.p1[...]=...; // set end point

for (A.start(start_point_as_double[3]);A.update();)
 {
 A.p[...]; // here use the iterated point
 }

同样在第二次教导时，请确保在您的DDA中，c,d,s如果它们是浮点数，则它们是整数，那么它也可能导致您所描述的问题......

推荐阅读