# 3D Fast ray/cube intersection in shader

## Recommended Posts

Hi all,

I have a situation in a shader where I know that a ray will intersect a particular axis aligned cube. I know the standard approach of intersecting with the 6 planes and looking for the closest hit.

What would be a faster way to determine which of the front-most three faces of the cube will intersect first with the ray? I would use this to determine the color, so if it's possible to set a variable without branching that would be ideal.

Any answers would be much appreciated!

Thanks,

JT

##### Share on other sites

This is abraycaster for 3d clouds as a set for 32x32x32 cube maybe this will fit

varying vec3 FragVertexCoord;

uniform vec3 campos;

uniform vec3 BoxStart;

uniform vec3 BoxLen;

uniform vec3 sun_dir;
uniform float density_factor;
uniform vec3 sun_light;

uniform sampler2D tex; //cloud density map this case its 2d texture since OpenGL ES 2.0 doesn't support 3d textures...
//61 - 76 pixels from atmosphere scaterring texture (128x128)
uniform vec3 global_ambient; //taken every height pixel and divided by the amount (this case 76-61 = 15)
uniform float ambient_shiness;
uniform vec3 sky_amb;

float modulo(float x, float y)
{
return x - y * float(int(x/y));
}

vec2 ArrI(int x, int y, int z)
{
int modulo_z = int(modulo(float(z),8.0));
int ax = x+ (modulo_z * 32);
int ay = y+(z / 8) * 32;
return vec2(float(ax)/256.0, float(ay)/256.0);
}

vec3 vectorAB(vec3 A, vec3 B)
{
return B-A;
}

vec3 point_to_grid_cell(vec3 vector)
{
vec3 dist = vector - BoxStart;
vec3 result;

result.x =  (dist.x / float(BoxLen.x)) * 32.0;
result.y =  (dist.y / float(BoxLen.y)) * 32.0;
result.z =  (dist.z / float(BoxLen.z)) * 32.0;
return result;
}

bool RayAABB(vec3 vdir, out vec3 ipoint)
{
vec3 invR = 1.0 / vdir;
vec3 tbot = invR * (	BoxStart			-	campos);
vec3 ttop = invR * (   (BoxStart+BoxLen)	-	campos);
vec3 tmin = min(ttop, tbot);
vec3 tmax = max(ttop, tbot);
vec2 t = max(tmin.xx, tmin.yz);
float  t0 = max(t.x, t.y);
t = min(tmax.xx, tmax.yz);
float  t1 = min(t.x, t.y);
ipoint = FragVertexCoord + vdir*t0;
return t0 <= t1;

}

bool same_cell(vec3 a, vec3 b)
{
if ( int(a.x) != int(b.x) ) return false;
if ( int(a.y) != int(b.y) ) return false;
if ( int(a.z) != int(b.z) ) return false;

return true;
}

void main()
{

int i;
float x = BoxLen.x / 32.0;
float y = BoxLen.y / 32.0;
float z = BoxLen.z / 32.0;

float dens = 0.0;
vec3 grid_point;
vec3 grid_point_tmp;
vec3 cell;
vec3 view_dir = normalize(FragVertexCoord - campos);

//find a point that lies on a grid if not return blank color and exit
//that makes everything we can even set that to million but why everything depends on fucking gemoetry we want to display
//since for now i dont have any ideas how to deal with that il make easy loop
bool found = false;
//
//vec3 return_point;
//bool ray_intersects = RayAABB(view_dir, return_point);
//if (ray_intersects)
//{
//	grid_point_tmp = FragVertexCoord+(view_dir*vec3(x,y,z)*0.1);
//    bool a = ( (cell.x <= 32.0) && (cell.y <= 32.0) && (cell.z <= 32.0) );
//    bool b = ( (cell.x >= 0.0)  && (cell.y >= 0.0)  && (cell.z >= 0.0)  );
//if ( ( a && b ) == true ) found = true;
//}

for (i=0; i < 320; i++)
{
grid_point_tmp = FragVertexCoord+(view_dir*vec3(x,y,z)*float(i));
cell = point_to_grid_cell(grid_point_tmp);
bool a = ( (cell.x <= 32.0) && (cell.y <= 32.0) && (cell.z <= 32.0) );
bool b = ( (cell.x >= 0.0)  && (cell.y >= 0.0)  && (cell.z >= 0.0)  );
if ( ( a && b ) == true ) { found = true;  break; }
}

if (found == true)
{
for (i=0; i < 32; i++)
{
grid_point = grid_point_tmp+(view_dir*vec3(x,y,z)*float(i));
cell = point_to_grid_cell(grid_point);

//make sure we do not go out of grid boundary
if ( (cell.x > 32.0) || (cell.y > 32.0) || (cell.z > 32.0) )  break;
if ( (cell.x < 0.0) || (cell.y < 0.0) || (cell.z < 0.0) ) break;

dens = texture2D( tex, ArrI(int(cell.x+0.5),int(cell.y+0.5),int(cell.z+0.5)) ).r;
if (dens > 0.1) break;

}

//float sum = 0.0;
//vec3 last_cell = cell;
//if (dens > 0.0)
//for (i=0; i < 32; i++)
//{
//
//	/*
//	 * code below prevents from sampling the same cell
//	 * need to fix whole function coz that prevention causes pixeloze :P
//	 */
//grid_point = cell-(sun_dir*float(i));
//if (same_cell(last_cell, grid_point)) continue;
//last_cell = grid_point;
//
//if ( (grid_point.x > 32.0) || (grid_point.y > 32.0) || (grid_point.z > 32.0) ) break;
//if ( (grid_point.x < 0.0) || (grid_point.y < 0.0) || (grid_point.z < 0.0) )  break;
//
//sum = sum + density_factor*texture2D( tex, ArrI(int(grid_point.x),int(grid_point.y),int(grid_point.z)) ).r;
//
//}

float sum = 0.0;
if (dens > 0.0)
for (i=0; i < 32; i++)
{
grid_point = cell-(sun_dir*float(i));

if ( (grid_point.x > 32.0) || (grid_point.y > 32.0) || (grid_point.z > 32.0) ) break;
if ( (grid_point.x < 0.0) || (grid_point.y < 0.0) || (grid_point.z < 0.0) )  break;

sum = sum + density_factor*texture2D( tex, ArrI(int(grid_point.x),int(grid_point.y),int(grid_point.z)) ).r;

}

vec3 darkest_color = sky_amb;//global_ambient * ambient_shade;

vec3 transition = vectorAB(global_ambient, darkest_color);

float rc = dens - sum;
rc = rc * ambient_shiness;
float intensity = clamp(1.0-rc, 0.0, 1.0);
vec3 final = global_ambient + transition*intensity;
if (dens >0.1)
gl_FragColor = vec4( final, 1.0 );
else
gl_FragColor = vec4( 0.0,0.0,0.0, 0.0 );

}

if (found == false)

gl_FragColor = vec4(0.0, 0.0, 0.0, 0.0);

}

##### Share on other sites

If you intersect many boxes with the same ray, it's faster to use the inverse ray directions to turn divisions into multiplications.

To find which face has been hit, you need to see which dimension wins on MinElem and MaxElem tests in below code.

	void Ray::SetFinite (const qVec3& start, const qVec3& end)
{
origin = start;
direction = end - start;
length = direction.Length();
direction /= length;
invDirection = qVec3 (1.0 / direction[0], 1.0 / direction[1], 1.0 / direction[2]);
}

void Ray::SetInfinite (const qVec3& origin, const qVec3& direction)
{
this->origin = origin;
this->direction = direction;
//debugAssert(direction.isUnit());

invDirection = qVec3 (1.0 / direction[0], 1.0 / direction[1], 1.0 / direction[2]);
length = FLT_MAX;

}

// ray - box

void DistanceRayAABoxFrontAndBackface (qScalar &ffd, qScalar& bfd, const Ray& ray, const AABox& box)
{
qVec3 t0 = qVec3(box.minmax[0] - ray.origin).MulPerElem (ray.invDirection);
qVec3 t1 = qVec3(box.minmax[1] - ray.origin).MulPerElem (ray.invDirection);
qVec3 tMin = t0.MinPerElem (t1);
qVec3 tMax = t0.MaxPerElem (t1);
ffd = tMin.MaxElem(); // front face distance (behind origin if inside box)
bfd = tMax.MinElem(); // back face distance
}

bool TestRayAABox (const Ray& ray, const AABox& box)
{
// returns false if ray is parallel with box face
qVec3 t0 = qVec3(box.minmax[0] - ray.origin).MulPerElem (ray.invDirection);
qVec3 t1 = qVec3(box.minmax[1] - ray.origin).MulPerElem (ray.invDirection);
qVec3 tMin = t0.MinPerElem (t1);
qVec3 tMax = t0.MaxPerElem (t1);
qScalar ffd = tMin.MaxElem(); // front face distance (behind origin if inside box)
qScalar bfd = tMax.MinElem(); // back face distance

return (ffd <= bfd) & (bfd >= 0.0f) & (ffd <= ray.length);
}

bool IntersectRayAABox (const Ray& ray, const AABox& box, float& t)
{
qScalar ffd, bfd;
DistanceRayAABoxFrontAndBackface (ffd, bfd, ray, box);
//RenderPoint (3, qVec3(ray.origin + ray.direction * ffd), 1,0,0);
//RenderPoint (3, qVec3(ray.origin + ray.direction * bfd), 0,1,0);

t = (ffd > 0) ? ffd : bfd; // returns always the first intersection with a face
return (ffd <= bfd) & (bfd >= 0.0f) & (ffd <= ray.length);
}

##### Share on other sites
13 hours ago, Cat's machete said:

This is abraycaster for 3d clouds as a set for 32x32x32 cube maybe this will fit

Thanks, that might be a good start. I'll have to look through and see which bits are relevant. However I suspect that it doesn't address which cube face is hit.

12 hours ago, JoeJ said:

If you intersect many boxes with the same ray, it's faster to use the inverse ray directions to turn divisions into multiplications.

To find which face has been hit, you need to see which dimension wins on MinElem and MaxElem tests in below code.

Thanks, it's not shader code but I'll see what I can make of it. Question: What do MulPerElem, MinElem and MaxElem do? Are they some sort of vector operations?

##### Share on other sites
9 minutes ago, jefferytitan said:

Thanks, that might be a good start. I'll have to look through and see which bits are relevant. However I suspect that it doesn't address which cube face is hit.

Thanks, it's not shader code but I'll see what I can make of it. Question: What do MulPerElem, MinElem and MaxElem do? Are they some sort of vector operations?

Yes, they use SIMD intristics under the hood (it's CPU code)

MinElem picks the smallest value of x,y,z (so telling the face index as well)

MulPerElem is like: vec result (a.x*b.x, a.y*b.y, a.z*b.z )

##### Share on other sites

Check this out. It was written for SSE, but since it is branchless it should work in shader.

## Create an account

Register a new account

1. 1
Rutin
45
2. 2
3. 3
4. 4
5. 5
JoeJ
19

• 13
• 10
• 12
• 10
• 13
• ### Forum Statistics

• Total Topics
632998
• Total Posts
3009811
• ### Who's Online (See full list)

There are no registered users currently online

×