How to fix my 3D Ray-Casting Algorithm for getting the Block the player is looking at

Multi tool use
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);
}
}
c# math game-physics physics ray
add a comment |
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);
}
}
c# math game-physics physics ray
add a comment |
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);
}
}
c# math game-physics physics ray
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);
}
}
c# math game-physics physics ray
c# math game-physics physics ray
edited Jan 3 at 7:33
Voxl David
asked Jan 3 at 4:13
Voxl DavidVoxl David
3517
3517
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
your DDA have two issues I can see from the first look:
work only if Z is the major axis
so only if you are in camera space or have fixed camera looking in Z direction
your deltas are weird
why:
delta? = abs(1 / look.Normalized().?);
I would expect:
delta? = abs(look.Normalized().?);
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()
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
is the step, d
is delta, c
is counter and ix
is major axis index.
The usage is like this:
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 go through
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 }
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
}
}
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 ...
btw if it helps look at this:
volumetric GLSL back ray tracer
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 its based on:
- Ray Casting with different height size
just like the link of yours.
[Edit] wrong hits (guessed from your comments)
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
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).
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:
- Comanche Voxel space ray casting
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
}
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...
thank you, but could you explain the code a bit more? I'm not an expert (or anything close) on the subject so I don't really understand what each variable in your class template is for
– Voxl David
Jan 3 at 7:39
Ah thanks, If you don't mind, I'd really appreciate a complete go through
– Voxl David
Jan 3 at 7:45
Okay, thank you very much, I've tried to implement this now here but it sometimes seems like it skips some blocks in between so that it returns a block behind the one the player is actually looking at...
– Voxl David
Jan 3 at 8:38
1
Oh, I think it's because I'm, due to the int calculations, not actually starting from where my camera is but from the corner of the block it is inside, which offsets the ray... Do you have any Idea on how to fix that?
– Voxl David
Jan 3 at 9:06
1
@VoxlDavid I reedited the answer added some stuff from comments and also the DDA subpixel offset ... please remove obsolete comments ...
– Spektre
Jan 3 at 10:48
|
show 3 more comments
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54016260%2fhow-to-fix-my-3d-ray-casting-algorithm-for-getting-the-block-the-player-is-looki%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
your DDA have two issues I can see from the first look:
work only if Z is the major axis
so only if you are in camera space or have fixed camera looking in Z direction
your deltas are weird
why:
delta? = abs(1 / look.Normalized().?);
I would expect:
delta? = abs(look.Normalized().?);
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()
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
is the step, d
is delta, c
is counter and ix
is major axis index.
The usage is like this:
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 go through
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 }
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
}
}
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 ...
btw if it helps look at this:
volumetric GLSL back ray tracer
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 its based on:
- Ray Casting with different height size
just like the link of yours.
[Edit] wrong hits (guessed from your comments)
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
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).
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:
- Comanche Voxel space ray casting
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
}
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...
thank you, but could you explain the code a bit more? I'm not an expert (or anything close) on the subject so I don't really understand what each variable in your class template is for
– Voxl David
Jan 3 at 7:39
Ah thanks, If you don't mind, I'd really appreciate a complete go through
– Voxl David
Jan 3 at 7:45
Okay, thank you very much, I've tried to implement this now here but it sometimes seems like it skips some blocks in between so that it returns a block behind the one the player is actually looking at...
– Voxl David
Jan 3 at 8:38
1
Oh, I think it's because I'm, due to the int calculations, not actually starting from where my camera is but from the corner of the block it is inside, which offsets the ray... Do you have any Idea on how to fix that?
– Voxl David
Jan 3 at 9:06
1
@VoxlDavid I reedited the answer added some stuff from comments and also the DDA subpixel offset ... please remove obsolete comments ...
– Spektre
Jan 3 at 10:48
|
show 3 more comments
your DDA have two issues I can see from the first look:
work only if Z is the major axis
so only if you are in camera space or have fixed camera looking in Z direction
your deltas are weird
why:
delta? = abs(1 / look.Normalized().?);
I would expect:
delta? = abs(look.Normalized().?);
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()
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
is the step, d
is delta, c
is counter and ix
is major axis index.
The usage is like this:
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 go through
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 }
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
}
}
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 ...
btw if it helps look at this:
volumetric GLSL back ray tracer
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 its based on:
- Ray Casting with different height size
just like the link of yours.
[Edit] wrong hits (guessed from your comments)
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
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).
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:
- Comanche Voxel space ray casting
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
}
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...
thank you, but could you explain the code a bit more? I'm not an expert (or anything close) on the subject so I don't really understand what each variable in your class template is for
– Voxl David
Jan 3 at 7:39
Ah thanks, If you don't mind, I'd really appreciate a complete go through
– Voxl David
Jan 3 at 7:45
Okay, thank you very much, I've tried to implement this now here but it sometimes seems like it skips some blocks in between so that it returns a block behind the one the player is actually looking at...
– Voxl David
Jan 3 at 8:38
1
Oh, I think it's because I'm, due to the int calculations, not actually starting from where my camera is but from the corner of the block it is inside, which offsets the ray... Do you have any Idea on how to fix that?
– Voxl David
Jan 3 at 9:06
1
@VoxlDavid I reedited the answer added some stuff from comments and also the DDA subpixel offset ... please remove obsolete comments ...
– Spektre
Jan 3 at 10:48
|
show 3 more comments
your DDA have two issues I can see from the first look:
work only if Z is the major axis
so only if you are in camera space or have fixed camera looking in Z direction
your deltas are weird
why:
delta? = abs(1 / look.Normalized().?);
I would expect:
delta? = abs(look.Normalized().?);
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()
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
is the step, d
is delta, c
is counter and ix
is major axis index.
The usage is like this:
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 go through
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 }
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
}
}
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 ...
btw if it helps look at this:
volumetric GLSL back ray tracer
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 its based on:
- Ray Casting with different height size
just like the link of yours.
[Edit] wrong hits (guessed from your comments)
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
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).
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:
- Comanche Voxel space ray casting
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
}
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...
your DDA have two issues I can see from the first look:
work only if Z is the major axis
so only if you are in camera space or have fixed camera looking in Z direction
your deltas are weird
why:
delta? = abs(1 / look.Normalized().?);
I would expect:
delta? = abs(look.Normalized().?);
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()
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
is the step, d
is delta, c
is counter and ix
is major axis index.
The usage is like this:
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 go through
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 }
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
}
}
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 ...
btw if it helps look at this:
volumetric GLSL back ray tracer
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 its based on:
- Ray Casting with different height size
just like the link of yours.
[Edit] wrong hits (guessed from your comments)
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
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).
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:
- Comanche Voxel space ray casting
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
}
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...
edited Jan 3 at 10:52
answered Jan 3 at 7:33


SpektreSpektre
30.1k649219
30.1k649219
thank you, but could you explain the code a bit more? I'm not an expert (or anything close) on the subject so I don't really understand what each variable in your class template is for
– Voxl David
Jan 3 at 7:39
Ah thanks, If you don't mind, I'd really appreciate a complete go through
– Voxl David
Jan 3 at 7:45
Okay, thank you very much, I've tried to implement this now here but it sometimes seems like it skips some blocks in between so that it returns a block behind the one the player is actually looking at...
– Voxl David
Jan 3 at 8:38
1
Oh, I think it's because I'm, due to the int calculations, not actually starting from where my camera is but from the corner of the block it is inside, which offsets the ray... Do you have any Idea on how to fix that?
– Voxl David
Jan 3 at 9:06
1
@VoxlDavid I reedited the answer added some stuff from comments and also the DDA subpixel offset ... please remove obsolete comments ...
– Spektre
Jan 3 at 10:48
|
show 3 more comments
thank you, but could you explain the code a bit more? I'm not an expert (or anything close) on the subject so I don't really understand what each variable in your class template is for
– Voxl David
Jan 3 at 7:39
Ah thanks, If you don't mind, I'd really appreciate a complete go through
– Voxl David
Jan 3 at 7:45
Okay, thank you very much, I've tried to implement this now here but it sometimes seems like it skips some blocks in between so that it returns a block behind the one the player is actually looking at...
– Voxl David
Jan 3 at 8:38
1
Oh, I think it's because I'm, due to the int calculations, not actually starting from where my camera is but from the corner of the block it is inside, which offsets the ray... Do you have any Idea on how to fix that?
– Voxl David
Jan 3 at 9:06
1
@VoxlDavid I reedited the answer added some stuff from comments and also the DDA subpixel offset ... please remove obsolete comments ...
– Spektre
Jan 3 at 10:48
thank you, but could you explain the code a bit more? I'm not an expert (or anything close) on the subject so I don't really understand what each variable in your class template is for
– Voxl David
Jan 3 at 7:39
thank you, but could you explain the code a bit more? I'm not an expert (or anything close) on the subject so I don't really understand what each variable in your class template is for
– Voxl David
Jan 3 at 7:39
Ah thanks, If you don't mind, I'd really appreciate a complete go through
– Voxl David
Jan 3 at 7:45
Ah thanks, If you don't mind, I'd really appreciate a complete go through
– Voxl David
Jan 3 at 7:45
Okay, thank you very much, I've tried to implement this now here but it sometimes seems like it skips some blocks in between so that it returns a block behind the one the player is actually looking at...
– Voxl David
Jan 3 at 8:38
Okay, thank you very much, I've tried to implement this now here but it sometimes seems like it skips some blocks in between so that it returns a block behind the one the player is actually looking at...
– Voxl David
Jan 3 at 8:38
1
1
Oh, I think it's because I'm, due to the int calculations, not actually starting from where my camera is but from the corner of the block it is inside, which offsets the ray... Do you have any Idea on how to fix that?
– Voxl David
Jan 3 at 9:06
Oh, I think it's because I'm, due to the int calculations, not actually starting from where my camera is but from the corner of the block it is inside, which offsets the ray... Do you have any Idea on how to fix that?
– Voxl David
Jan 3 at 9:06
1
1
@VoxlDavid I reedited the answer added some stuff from comments and also the DDA subpixel offset ... please remove obsolete comments ...
– Spektre
Jan 3 at 10:48
@VoxlDavid I reedited the answer added some stuff from comments and also the DDA subpixel offset ... please remove obsolete comments ...
– Spektre
Jan 3 at 10:48
|
show 3 more comments
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54016260%2fhow-to-fix-my-3d-ray-casting-algorithm-for-getting-the-block-the-player-is-looki%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
3mEtQg63IL,NeDRC,I5 zt1aR,WQBCUMJ3IbayjWsDZwGia0Micm2