Jump to content
  • Advertisement

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 this post


Link to post
Share on other sites
Advertisement

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 float ambient_shade;
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 );
//discard;

}

if (found == false)

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



}

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
  • Advertisement
  • Popular Tags

  • Popular Now

  • Advertisement
  • Similar Content

    • By lucky6969b
      Dear folks,
      How do I calculate the axis of rotation between 2 vectors, one of them is the source directional vector, and the second is the destination directional vector.
      Thanks a lot
      Jack
    • By mmmax3d
      Hi everyone,
      I would need some assistance from anyone who has a similar experience
      or a nice idea!
      I have created a skybox (as cube) and now I need to add a floor/ground.
      The skybox is created from cubemap and initially it was infinite.
      Now it is finite with a specific size. The floor is a quad in the middle
      of the skybox, like a horizon.
      I have two problems:
      When moving the skybox upwards or downwards, I need to
      sample from points even above the horizon while sampling
      from the botton at the same time.  I am trying to create a seamless blending of the texture
      at the points of the horizon, when the quad is connected
      to the skybox. However, I get skew effects. Does anybody has done sth similar?
      Is there any good practice?
      Thanks everyone!
    • By ChenMo
      I am implementing baking in our engine.I met a problem about how to assignment per object uv in lightmap atlas.
      I am using UVAtlas to generate lightmap uv, most unwrapped mesh has a uv range [0, 1), no matter how big they are. I wanna them have same uv density so to packing them well in lightmap atlas.I have tried thekla_atlas to do the same thing too, but it seems that it can not unwrap uv according mesh size.
      As far as I can see, unwrapping uv coordinates using its world space can solve this, all meshes share a same scale.But I don't hope to spend a lot of time to write these code and debug them.I am wandering is there exist some methods I don't know that can scale each lightmap uv to a same density.
      Thanks in advance. : )
    • By Nikita Sidorenko
      I'm making render just for fun (c++, opengl)
      Want to add decals support. Here what I found
      A couple of slides from doom
      http://advances.realtimerendering.com/s2016/Siggraph2016_idTech6.pdf Decals but deferred 
      http://martindevans.me/game-development/2015/02/27/Drawing-Stuff-… space-Decals/
      No implementation details here
      https://turanszkij.wordpress.com/2017/10/12/forward-decal-rendering/
      As I see there should be a list of decals for each tile same as for light sources. But what to do next?
      Let assume that all decals are packed into a spritesheet. Decal will substitute diffuse and normal.
      - What data should be stored for each decal on the GPU? 
      - Articles above describe decals as OBB. Why OBB if decals seem to be flat?
      - How to actually render a decal during object render pass (since it's forward)? Is it projected somehow? Don't understand this part completely.
      Are there any papers for this topic?
    • By korben_4_leeloo
      Hi.
      I wanted to experiment D3D12 development and decided to run some tutorials: Microsoft DirectX-Graphics-Samples, Braynzar Soft, 3dgep...Whatever sample I run, I've got the same crash.
      All the initialization process is going well, no error, return codes ok, but as soon as the Present method is invoked on the swap chain, I'm encountering a crash with the following call stack:
      https://drive.google.com/open?id=10pdbqYEeRTZA5E6Jm7U5Dobpn-KE9uOg
      The crash is an access violation to a null pointer ( with an offset of 0x80 )
      I'm working on a notebook, a toshiba Qosmio x870 with two gpu's: an integrated Intel HD 4000 and a dedicated NVIDIA GTX 670M ( Fermi based ). The HD 4000 is DX11 only and as far as I understand the GTX 670M is DX12 with a feature level 11_0. 
      I checked that the good adapter was chosen by the sample, and when the D3D12 device is asked in the sample with a 11_0 FL, it is created with no problem. Same for all the required interfaces ( swap chain, command queue...).
      I tried a lot of things to solve the problem or get some info, like forcing the notebook to always use the NVIDIA gpu, disabling the debug layer, asking for a different feature level ( by the way 11_0 is the only one that allows me to create the device, any other FL will fail at device creation )...
      I have the latest NVIDIA drivers ( 391.35 ), the latest Windows 10 sdk ( 10.0.17134.0 ) and I'm working under 
      Visual Studio 2017 Community.
      Thanks to anybody who can help me find the problem...
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!