Sign in to follow this  
Juliean

Raycast to AABB with non-uniform scaling

Recommended Posts

Hello,

I've got a problem with my raycasting-routine. I'm doing raychecks against meshes by transform the ray into model-space, and then check that ray against the AABB. This works fine, as long as the model has a uniform scaling.

As soon as the scaling derived from being uniform, the perceived collision will no long be at its correct position. Its a bit confusion and hard to test/explain, but here's what I've got so far:

If the scaling on y&z are both egal, ie. 2.0; if x is lower then 2.0, the ray will recognize intersection only when moved further along the positive x-coordinate than the mesh actually is. If x is higher than 2.0, it will be the same for the negative x-axis. For z, the box will scale inverse to the amount of scaling & be slightly offset, and for y I'm not getting any reported collision as soon as its not the same as eigther x or z.

I'm not sure how much that helps, so here's the code in question:

const auto mWorld = transform.GetWorldMatrix();
const auto mInvTransform = mWorld.inverse();

const auto vInvOrigin = mInvTransform.TransformCoord(ray.vOrigin);
const auto vInvDirection = mTranmInvTransform.sform.TransformNormal(ray.vDirection.normal()).normal();

const math::Ray invRay(vInvOrigin, vInvDirection * 1000.0f);

const auto AABB = pMesh->GetFile()->GetAABB();

return AABB.Intersect(invRay);

As an example, ray could have

position = {x=-9.32999897 y=13.9499998 z=4.90000010 }
direction = {x=39.5732002 y=-91.8366089 z=0.346698761 }

Transform of the mesh is actually composed of local and parent transform:

local = {vPosition={x=0.000000000 y=0.000000000 z=0.000000000 } vScale={x=1.70000005 y=2.00000000 z=1.79999995 }, vRotation = {x=0.000000000 y=-90.0000000 z=0.000000000 }}
parent = {vPosition={x=-3.32999992 y=0.000000000 z=4.90000010 } vScale={x=1.00000000 y=1.00000000 z=1.00000000 }, vRotation = {x=0.000000000 y=0.000000000 z=-0.000000000 }}

Inverse (= model space) ray becomes:

position ={x=2.38418579e-07 y=6.97499990 z=3.52941179 } 
direction ={x=3.19035053 y=-938.991150 z=-343.926605 } }

And the AABB itself is

center = {x=-0.00645050406 y=0.0604675002 z=0.00448551774 } 
size={x=0.613541484 y=0.0504675023 ...} }

The ray in this example is fired towards the middle of the object, confirmed to be working for uniformly-scaled meshes & if transforming the AABB instead of the ray (though then rotation doesn't work, so, meh).

Actually, last step, the AABB->ray intersection routine:

bool AABB::Intersect(const Ray& ray, Vector3* vOut) const
{
    const Vector3 vMin(m_vCenter - m_vSize), vMax(m_vCenter + m_vSize);

    const float t1 = (vMin.x - ray.vOrigin.x)*ray.vDirFrac.x;
    const float t2 = (vMax.x - ray.vOrigin.x)*ray.vDirFrac.x;
    const float t3 = (vMin.y - ray.vOrigin.y)*ray.vDirFrac.y;
    const float t4 = (vMax.y - ray.vOrigin.y)*ray.vDirFrac.y;
    const float t5 = (vMin.z - ray.vOrigin.z)*ray.vDirFrac.z;
    const float t6 = (vMax.z - ray.vOrigin.z)*ray.vDirFrac.z;

    const float tmin = max(max(min(t1, t2), min(t3, t4)), min(t5, t6));
    const float tmax = min(min(max(t1, t2), max(t3, t4)), max(t5, t6));

    // if tmax < 0, ray (line) is intersecting AABB, but whole AABB is behind us
    if (tmax < 0)
        return false;

    // if tmin > tmax, ray doesn't intersect AABB
    if (tmin > tmax)
        return false; // fails here

    if (vOut)
        *vOut = ray.vOrigin + ray.vDirection * tmin;

    return true;
}

Actually fails on the tmin > tmax condition, with the following values:

t1    -0.194333583
t2    0.190289661
t3    0.00741753448
t4    0.00731004169
t5    0.0118290847
t6    0.00866904669
tmax    0.00741753448
tmin    0.00866904669
vMax    {x=0.607090950 y=0.110935003 z=0.547896028 }
vMin    {x=-0.619992018 y=0.00999999791 z=-0.538925052 }

__________________________________________

So... given all that, has anyone got any idea of whats going on? I hope that some of the more math-savy people here might be able to see from the numbers whats going wrong, my math just sucks too much to even know what I'd be looking for :/

All the math-routines involved are hand-written, so there might be some issues there, though I'm pretty convinced they work as intended, since they have been used extensivly in other parts so far (though if you might suspect a problem somewhere else, please let me know and I can share the code).

Any ideas so far? If not, any alternate way to perform transformed AABB-ray collision?

 

 

Share this post


Link to post
Share on other sites

It shouldn't take any extra work to handle non uniform scaling if you handle the ray right. The key is to NOT normalize the ray direction when you transform to local space. The transformation may change the length, but that's OK because then it means you don't have to deal with transforming t_min/t_max to get the right intersection. In local space, t_min/t_max are not the distance but the parameterization of the ray: x(t) = origin + direction*t. Also, there is no need to compute the intersection point anywhere but in world space after the scene traversal.

I would look into Intel's Embree source code to see how to do the transforms well. It's a bit hard to decipher but probably the best implementation I've seen.

Here's some excerpts from my code, it is very similar to how Embree works:

/// Transform a 3D point by this transformation.
inline SIMDFloat4 BVHTransform:: transformPoint( const SIMDFloat4& point ) const
{
	return position + basis.x*point[0] + basis.y*point[1] + basis.z*point[2];
}


/// Transform a 3D vector by this transformation, neglecting the translation.
inline SIMDFloat4 BVHTransform:: transformVector( const SIMDFloat4& vector ) const
{
	return basis.x*vector[0] + basis.y*vector[1] + basis.z*vector[2];
}

/// Return whether or not the primitive with the specified index is intersected by the specified ray.
inline void intersectSingleBVH( PrimitiveIndex bvhIndex, BVHRay& ray ) const
{
	// Transform the ray to local space.
	const BVHTransform worldToLocal = transforms[bvhIndex].worldToLocal;
	const SIMDFloat4 worldOrigin = ray.origin;
	const SIMDFloat4 worldDirection = ray.direction;
	const PrimitiveIndex worldPrimitive = ray.primitive;
	ray.origin = worldToLocal.transformPoint( worldOrigin );
	ray.direction = worldToLocal.transformVector( worldDirection );
	ray.primitive = BVHGeometry::INVALID_PRIMITIVE;
	
	// Intersect the ray with the child BVH.
	bvhs[bvhIndex]->intersectRay( ray );
	
	// Restore the ray state.
	ray.origin = worldOrigin;
	ray.direction = worldDirection;
	
	if ( ray.hitValid() )
	{
		// Transform the normal to world space.
		ray.normal = transforms[bvhIndex].localToWorld.transformVector( ray.normal );
		ray.instance = bvhIndex;
	}
	else
		ray.primitive = worldPrimitive;
}

// Intersect a single ray against 4 AABBs at once and return the result mask
inline SIMDInt4 intersectRay( const TraversalRay& ray, const SIMDFloat4& tMin, const SIMDFloat4& tMax, SIMDFloat4& near ) const
{
	SIMDFloat4 txmin = (SIMDFloat4::load((const Float32*)((const UByte*)bounds + ray.signMin[0])) - ray.origin.x) * ray.inverseDirection.x;
	SIMDFloat4 txmax = (SIMDFloat4::load((const Float32*)((const UByte*)bounds + ray.signMax[0])) - ray.origin.x) * ray.inverseDirection.x;
	SIMDFloat4 tymin = (SIMDFloat4::load((const Float32*)((const UByte*)bounds + ray.signMin[1])) - ray.origin.y) * ray.inverseDirection.y;
	SIMDFloat4 tymax = (SIMDFloat4::load((const Float32*)((const UByte*)bounds + ray.signMax[1])) - ray.origin.y) * ray.inverseDirection.y;
	SIMDFloat4 tzmin = (SIMDFloat4::load((const Float32*)((const UByte*)bounds + ray.signMin[2])) - ray.origin.z) * ray.inverseDirection.z;
	SIMDFloat4 tzmax = (SIMDFloat4::load((const Float32*)((const UByte*)bounds + ray.signMax[2])) - ray.origin.z) * ray.inverseDirection.z;
	
	near = math::max( math::max( txmin, tymin ), math::max( tzmin, tMin ) );
	SIMDFloat4 far = math::min( math::min( math::min( txmax, tymax ), tzmax ), tMax );
	// near is the intersection with each AABB if (near <= far)
	return near <= far;
}
Edited by Aressera

Share this post


Link to post
Share on other sites

It shouldn't take any extra work to handle non uniform scaling if you handle the ray right. The key is to NOT normalize the ray direction when you transform to local space. The transformation may change the length, but that's OK because then it means you don't have to deal with transforming t_min/t_max to get the right intersection. In local space, t_min/t_max are not the distance but the parameterization of the ray: x(t) = origin + direction*t. Also, there is no need to compute the intersection point anywhere but in world space after the scene traversal.

Removing the normalization didn't change anything, unfortunately. It turns out however that the issue was inside my TransformNormal-function. I'm calculating the inverse-transpose of the matrix there:

Vector3 Matrix::TransformNormal(Vector3 vIn) const
{
    const float length = vIn.length();
    if(length == 0.0f)
        return vIn;

    const Matrix mNew = inverse().transpose();

    return Vector3(    vIn.x * mNew.m11 + vIn.y * mNew.m21 + vIn.z * mNew.m31,
                    vIn.x * mNew.m12 + vIn.y * mNew.m22 + vIn.z * mNew.m32,
                    vIn.x * mNew.m13 + vIn.y * mNew.m23 + vIn.z * mNew.m33 );
}

I mean, I was under the impression that you had to transform by the inverse-transpose matrix when transforming normals, but appearently, in this case I just have to transform by the inverse-world matrix - so removing the inverse().transpose()-part gets rid of the bug. I'm still confused by what exactly is going on, but performing the inverse().transpose() inside this function was probably a bad idea to begin with, if not only for efficieny.

Problem's solved, I'll have a look at Intel Embree though once I've got the time to improve and optimize, right now I'm just trying to get stuff to work for a presentation next week. Thanks still :)

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

Sign in to follow this