如何修复我的3D射线投射算法以获取玩家正在观看的方块 [英] How to fix my 3D Ray-Casting Algorithm for getting the Block the player is looking at
问题描述
我用于计算玩家正在看哪个方块(基于体素的世界)的算法无法正常工作.我已经从本教程中将其从2D修改为3D.有时它显示正确的块，但有时它要么什么都不显示，要么在完全不同的方向上返回东西，为什么会发生?
My algorithm for calculating which block a player is looking at (voxel based world) is not working correctly. I have adapted it from this tutorial from 2D to 3D. At times it shows the correct block but other times it either returns nothing when it should or something in a completely different direction, why is this happening?
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);
}
}
推荐答案
您的 DDA 有两个问题，从我的初看起来就可以看出:
your DDA have two issues I can see from the first look:
-
仅当Z为主轴时有效
work only if Z is the major axis
仅当您在相机空间中或固定相机沿Z方向观看时
so only if you are in camera space or have fixed camera looking in Z direction
您的三角洲很奇怪
为什么:
delta? = abs(1 / look.Normalized().?);
我希望:
delta? = abs(look.Normalized().?);
我没有使用 C#进行编码，因此我不确定要修复您的代码，但这是我的 C ++ 模板，用于n维 DDA 因此，只需根据它进行比较和修复即可...
I do not code in C# so I am not confident to repair your code however here is my C++ template for n-dimensional DDA so just compare and repair yours according it ...
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
start() init the variables and position for the DDA (from p0,p1 control points) and the update() is just single step of the DDA ... Resulting iterated point is in p
s是步骤，d是增量，c是计数器，ix是主轴索引.
s is the step, d is delta, c is counter and ix is major axis index.
用法如下:
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)之间某行上整数位置的插值(光栅化).线方程是这样的:
well DDA is just interpolation (rasterization) of integer positions on some line between two endpoints (p0,p1). The line equation is like this:
p(t) = p0 + t*(p1-p0);
t = <0.0,1.0>
但是涉及浮点数学，我们需要整数，因此我们可以将其重写为如下形式:
however that involves floating math and we want integer so we can rewrite to something like this:
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轴)其他将具有相同的索引...):
where i,D is matching the major axis (the one with biggest change). If you look closer we are using *i/D Which is slow operation and we usually want speed so we can rewrite the therm (exploiting the fact that i goes from 0 to D in order) into something like this (for x axis only the others will be the same with different indexes ...):
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，这是重写为D迭代的i/D.所有其他轴的计算方式相同，您只需要为每个轴添加计数器c步骤s和绝对增量d ...
Now take a closer look at the counter c which we are adding the D and substracting d.x which is the i/D rewrited into D iterations. All the other axises are computed in the same manner you just need to add counter c step s and abs delta d for each axis ...
顺便说一句:
这是(我假设)您正在做的事情，但是是在GLSL着色器中实现的(请参见片段代码)，但是它不使用 DDA ，而是将单元方向矢量添加到初始位置，直到碰到某些东西为止或体素空间的结尾...
which is (I assume) what you are doing but implemented in GLSL shader (see the fragment code) however it does not use DDA instead it is adding unit direction vector to initial position until hit something or end of voxel space ...
btw其基于:
就像您的链接一样.
错误的命中(根据您的评论推测)
这很可能与 DDA 没有关系.它更像是边缘情况，当您直接站在单元格交叉点上或被错误地截断位置或错误地对命中进行z排序时.我记得我在遇到麻烦.最后，我在 GLSL 中找到了一个非常奇怪的解决方案，请参见上面的链接并查看片段代码.寻找
That has most likely nothing to do with DDA. Its more like edge case when you are standing directly on cell crossing or have wrongly truncated position or have wrongly z-sorted the hits. I remember I was having trouble with it. I ended up with very weird solution in GLSL see the Link above and see the fragment code. Look for
// YZ plane voxels hits
直接在非"DDA"射线投射代码之后.它可以检测到哪个平面将被撞击，我认为您应该执行类似的操作.就像在2D DOOM中一样(在上面的链接中)，这也很奇怪，我没有这样的问题...但是那是由于它们是通过使用不同的数学方法解决的(仅适用于2D).
its directly after the non "DDA" ray casting code. It detects which plane of the voxel will be hit I think you should do something similar. It was weird as in 2D DOOM (also in links above) I had no such problems... but that was due to fact they were solved by different math used (suitable only for 2D).
在射线投射之前的GLSL代码会稍微改变位置以避免边缘情况.注意floor和ceil，但是我的在浮点数上起作用，因此需要对int数学进行一些调整.幸运的是，我正在基于此来修复我的其他射线投射引擎:
The GLSL code just before the casting of ray changes a position a bit to avoid edge cases. pay attention to the floor and ceil but mine works on floats so it would need some tweaking for int math. Luckily I was repairing my other ray casting engine based on this:
解决方案是使 DDA 偏移射线的亚像素开始位置.我在新用法上方更新了 DDA 代码:
And the solution is to offset the DDA by subpixel start position of the ray. I updated the DDA code above the new usage is:
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是整数(如果它们是浮点数)，那么这也可能会引起您所描述的问题...
Also on second taught make sure that in your DDA the c,d,s are integers if they are floating instead then it might cause the problems you are describing too...
这篇关于如何修复我的3D射线投射算法以获取玩家正在观看的方块的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
