Looking for an efficient way to do a ray (2D line segment defined by start and end points) intersection test with a single square on a regular grid (for a raycaster)..what i need to return is the 2D x,y point of intersection (if there is one)

I've done a bunch of searches and found a lot of answers that seem too complicated for this problem..this seems to be a very simple case, so there should be a fast robust solution…

		void DistanceRayFrontAndBackface (float &ffd, float& bfd, const vec& rayOrigin, const vec& rayInvDirection) const
		{
			vec t0 = vec(minmax[0] - rayOrigin).MulPerElem (rayInvDirection);
			vec t1 = vec(minmax[1] - rayOrigin).MulPerElem (rayInvDirection);
			vec tMin = t0.MinPerElem (t1);
			vec tMax = t0.MaxPerElem (t1);
			ffd = tMin.MaxElem(); // front face distance (behind origin if inside box) 
			bfd = tMax.MinElem(); // back face distance	
		}

		bool TestRay (const vec& rayOrigin, const vec& rayInvDirection, const float rayLength) const
		{
			float ffd, bfd;
			DistanceRayFrontAndBackface (ffd, bfd, rayOrigin, rayInvDirection);
			return (ffd <= bfd) & (bfd >= 0.0f) & (ffd <= rayLength);
		}

		bool IntersectRay (float& t, const vec& rayOrigin, const vec& rayInvDirection, const float rayLength) const
		{
			float ffd, bfd;
			DistanceRayFrontAndBackface (ffd, bfd, rayOrigin, rayInvDirection);
			t = (ffd > 0) ? ffd : bfd; // always the first intersection with a face
			return (ffd <= bfd) & (bfd >= 0.0f) & (ffd <= rayLength);
		}

This is what i use for 3D, but math is the same. It is the so called ‘Slab Test’.

MulPerElem for two vectors is: (a,b) x (c,d) = (a x c, b x d)
MinPerElem and MinElem for ((a,b), (c,d)) boils down to simply the minimum af all involved numbers.
(Looks quirky because those are SIMD abstractions)

This is the fastest method to do this AFAIK, but robustness is an issue because of division. I need to look up how to make rayInvDirection to show how to deal with this…

class Ray 
{
public:
 
	qVec3 origin;
    qVec3 direction; // Unit length
    qVec3 invDirection; // 1.0 / direction
	float length;

	void SetInfinite (const qVec3& origin, const qVec3& unitDir);
	void SetFinite (const qVec3& start, const qVec3& end);
	void Jitter ();
};

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


	void Ray::SetInfinite (const qVec3& origin, const qVec3& direction) 
	{
		this->origin = origin;
		this->direction = direction;
		Jitter(); 
		invDirection = qVec3 (1.0f / this->direction[0], 1.0f / this->direction[1], 1.0f / this->direction[2]);
		length = FLT_MAX;
	}

	void Ray::Jitter () 
	{
		constexpr float epsilon = FP_TINY;
		for (int i=0; i<3; i++)
		{
			if (direction[i] < epsilon && direction[i] > -epsilon)
				direction[i] = epsilon;
		}
	}
	

	#define FP_TINY 1.0e-12f

More code than you expected i guess : )

But just look at Jitter() where i prevent zero dimensions so the division works.

I never noticed the inaccuracy that happens when the ray is exactly axis aligned.

Oh, my box is defined this way:

minMax[0] = minimum coordinates,

minMax[1] = maximum coordinates,

Thanks, this should work, but I'm wondering if there is something even simpler…

say we have an infinite ray, and one specific box on the regular grid, all 2D, isnt there some sort of simple method..all i need is distance to intersect..

Matt_Aufderheide said:
Thanks, this should work, but I'm wondering if there is something even simpler…

No, but it's 10 lines of code if you do only what you actually need.

There is no way around calculating the slope against both box axis, then there are two sides per axis, and there is the special case of being inside the box where you may want to decide which side to take.

OK, thank you for your help!