Explanation of a Hieroglyph

[BurakCanik]

An exercise from the Picking chapter of my DirectX book wants me to "Research the algorithm for doing a ray/AABB intersection test". So I researched the subject and found that the "slabs" method was quite popular, also it's the fastest algorithm I believe, though I could be wrong. Anyways, for those who don't know the slabs method, here it is :
https://www.siggraph.org/education/mate ... inter3.htm

Algorithm is quite simple, requires a little geometry. Anyways, after I understood the algorithm mentioned in the link, I wanted to see an implementation of this and since the book uses the XNA collision library (which doesn't exist anymore since XNA became DirectXMath), I decided to take a look at the XNA::IntersectRayAxisAlignedBox() method. I'm trying to decipher this shit and I'm having difficulty understanding some parts of it.

This is the function :

Code: Select all

//-----------------------------------------------------------------------------
// Compute the intersection of a ray (Origin, Direction) with an axis aligned 
// box using the slabs method.
//-----------------------------------------------------------------------------
BOOL IntersectRayAxisAlignedBox( FXMVECTOR Origin, FXMVECTOR Direction, const AxisAlignedBox* pVolume, FLOAT* pDist )
{
    XMASSERT( pVolume );
    XMASSERT( pDist );
    XMASSERT( XMVector3IsUnit( Direction ) );

    static const XMVECTOR Epsilon =
    {
        1e-20f, 1e-20f, 1e-20f, 1e-20f
    };
    static const XMVECTOR FltMin =
    {
        -FLT_MAX, -FLT_MAX, -FLT_MAX, -FLT_MAX
    };
    static const XMVECTOR FltMax =
    {
        FLT_MAX, FLT_MAX, FLT_MAX, FLT_MAX
    };

    // Load the box.
    XMVECTOR Center = XMLoadFloat3( &pVolume->Center );
    XMVECTOR Extents = XMLoadFloat3( &pVolume->Extents );

    // Adjust ray origin to be relative to center of the box.
    XMVECTOR TOrigin = Center - Origin;

    // Compute the dot product againt each axis of the box.
    // Since the axii are (1,0,0), (0,1,0), (0,0,1) no computation is necessary.
    XMVECTOR AxisDotOrigin = TOrigin;
    XMVECTOR AxisDotDirection = Direction;

    // if (fabs(AxisDotDirection) <= Epsilon) the ray is nearly parallel to the slab.
    XMVECTOR IsParallel = XMVectorLessOrEqual( XMVectorAbs( AxisDotDirection ), Epsilon );

    // Test against all three axii simultaneously.
    XMVECTOR InverseAxisDotDirection = XMVectorReciprocal( AxisDotDirection );
    XMVECTOR t1 = ( AxisDotOrigin - Extents ) * InverseAxisDotDirection;
    XMVECTOR t2 = ( AxisDotOrigin + Extents ) * InverseAxisDotDirection;

    // Compute the max of min(t1,t2) and the min of max(t1,t2) ensuring we don't
    // use the results from any directions parallel to the slab.
    XMVECTOR t_min = XMVectorSelect( XMVectorMin( t1, t2 ), FltMin, IsParallel );
    XMVECTOR t_max = XMVectorSelect( XMVectorMax( t1, t2 ), FltMax, IsParallel );

    // t_min.x = maximum( t_min.x, t_min.y, t_min.z );
    // t_max.x = minimum( t_max.x, t_max.y, t_max.z );
    t_min = XMVectorMax( t_min, XMVectorSplatY( t_min ) );  // x = max(x,y)
    t_min = XMVectorMax( t_min, XMVectorSplatZ( t_min ) );  // x = max(max(x,y),z)
    t_max = XMVectorMin( t_max, XMVectorSplatY( t_max ) );  // x = min(x,y)
    t_max = XMVectorMin( t_max, XMVectorSplatZ( t_max ) );  // x = min(min(x,y),z)

    // if ( t_min > t_max ) return FALSE;
    XMVECTOR NoIntersection = XMVectorGreater( XMVectorSplatX( t_min ), XMVectorSplatX( t_max ) );

    // if ( t_max < 0.0f ) return FALSE;
    NoIntersection = XMVectorOrInt( NoIntersection, XMVectorLess( XMVectorSplatX( t_max ), XMVectorZero() ) );

    // if (IsParallel && (-Extents > AxisDotOrigin || Extents < AxisDotOrigin)) return FALSE;
    XMVECTOR ParallelOverlap = XMVectorInBounds( AxisDotOrigin, Extents );
    NoIntersection = XMVectorOrInt( NoIntersection, XMVectorAndCInt( IsParallel, ParallelOverlap ) );

    if( !XMVector3AnyTrue( NoIntersection ) )
    {
        // Store the x-component to *pDist
        XMStoreFloat( pDist, t_min );
        return TRUE;
    }

    return FALSE;
}

Okay so first problem is the dot product part. As we know, if we take a vector A and a unit vector B and take their dot product A * B, then we get a vector which is the projection of A onto B.

Like this, kind of :

If the v is not a unit vector then the projected vector u is given with a slightly different method. Anyways, getting off topic here.

Question is : What are these lines of code accomplishing to do ?

Code: Select all

// Compute the dot product againt each axis of the box.
// Since the axii are (1,0,0), (0,1,0), (0,0,1) no computation is necessary.
XMVECTOR AxisDotOrigin = TOrigin;
XMVECTOR AxisDotDirection = Direction;

Second problem is this part :

Code: Select all

// Test against all three axii simultaneously.
XMVECTOR InverseAxisDotDirection = XMVectorReciprocal( AxisDotDirection );
XMVECTOR t1 = ( AxisDotOrigin - Extents ) * InverseAxisDotDirection;
XMVECTOR t2 = ( AxisDotOrigin + Extents ) * InverseAxisDotDirection;

Why do you take reciprocals of every component of a vector ? What use is there ?

I managed to understand the other parts of it but I'm stuck on these two. Does anybody have an idea ?

EDIT : By the way XNA Collision library is under Program Files (x86)\Microsoft DirectX SDK (June 2010)\Samples\C++\Misc\Collision

[nackles]

hungrier than a muhfucka up in hur

[BurakCanik]

hungrier than a muhfucka up in hur

Yes yes, I see the link now. Everything makes sense!

[albinopapa]

K, I'm confused lol.

[BurakCanik]

If you're confused about the method welcome to the club It's a freaking hieroglyph let me tell you that! It's almost natural to get confused.

If you're confused about our "homie" nackles that's a whole another story though...

[LuisR14]

this became hilarious, can't hold my laughter xD

[albinopapa]

If you're confused about the method welcome to the club It's a freaking hieroglyph let me tell you that! It's almost natural to get confused.

If you're confused about our "homie" nackles that's a whole another story though...

Yes, it seems that the code for your first question is a bit unnecessary and the second question would require a bit more understanding of the algorithm than I currently have.

Yes, confused about the response from and to nackles regarding your questions, other than just a random statement and an equally random response, in which case sorry to hear about your hunger, maybe you should eat some PI.

[BurakCanik]

I just can't figure out the aim of those lines. I remember Chili covering collision. It's been some time since the last time I watched Chili's videos. Got distracted with 3D and shizzle. Hope to return to them soon. Anyways maybe he'll cover 3D collision, AABB's, bounding spheres etc. when we get to 3D and hopefully some of my questions will be answered then.

[albinopapa]

So doing some coding and came across a situation where I do some optimizations. I've read that division is slower than multiplication, so doing multiplication on something that needs dividing especially if going to be done more than once, you would use the reciprocal of the thing you want to divide by so you can now use it as a multiplier.

Instead of:

Code: Select all

float a = 5.0f;
float b = 7.0f;
float c = a / b;

// you would take the reciprocal of b and multiply a by b.
float a = 5.0f;
float b = 7.0f;
float rB = 1 / b;
float c = a * rB;

This by itself would not speed things up since you are actually adding another instruction and still doing a division. However, if you were going to divide other stuff by b, now you can multiply by rB and it will be faster. Not sure how much faster the above code would be as it still does 1 divide and 2 multiply instead of 2 divides though, but that's the only explanation I can see.

[BurakCanik]

Okay that makes sense. I'll take a look at it from this perspective.