3
\$\begingroup\$

Playing with XNA Triangle Picking Sample I found out that it does not work well if you scale the world matrix of the objects you want to pick. When I dug into the implementation I found this comment in the RayIntersectsModel method:

        // The input ray is in world space, but our model data is stored in object
        // space. We would normally have to transform all the model data by the
        // modelTransform matrix, moving it into world space before we test it
        // against the ray. That transform can be slow if there are a lot of
        // triangles in the model, however, so instead we do the opposite.
        // Transforming our ray by the inverse modelTransform moves it into object
        // space, where we can test it directly against our model data. Since there
        // is only one ray but typically many triangles, doing things this way
        // around can be much faster.

After the comment they actually transformed the ray:

ray.Position = Vector3.Transform(ray.Position, inverseTransform);
ray.Direction = Vector3.TransformNormal(ray.Direction, inverseTransform);

With this implementation, picking suffered from "short-sightedness" if you scaled the models: it could only pick those objects, that were close enough to it. Even the ray-boundingSphere intersection test, which implementation is hardcoded into XNA, failed in the same way.

I fixed this by "doing the wrong thing" - I actually started transforming every vertex by the model's world matrix and to fix the boundingSphere test I added this code:

Quaternion rot;
Vector3 scale, trans;
modelTransform.Decompose(out scale, out rot, out trans);

float maxScale = Math.Max(Math.Max(scale.X, scale.Y), scale.Z);

boundingSphere.Center = Vector3.Transform(boundingSphere.Center, modelTransform);
boundingSphere.Radius *= maxScale;

This obviously is not optimal and I wanted to know if there is a way to actually transform the ray back to the model's space with the model's inverted matrix, while making it work for scaled matrices?

SOLUTION: Thanks to Nathan's answer I found a way to fix the ray scaling - just renormalize the ray direction:

ray.Position = Vector3.Transform(ray.Position, inverseTransform);
ray.Direction = Vector3.TransformNormal(ray.Direction, inverseTransform);
//ADD THE FOLLOWING LINE:
ray.Direction.Normalize();

SOLUTION UPDATE: As I tested the app, I found that Nathan was indeed completely right and another change was necessary. Here is the full code for the correct RayIntersectsModel() method:

static float? RayIntersectsModel(Ray ray, Model model, Matrix modelTransform,
                                out bool insideBoundingSphere,
                                out Vector3 vertex1, out Vector3 vertex2,
                                out Vector3 vertex3)
{
    vertex1 = vertex2 = vertex3 = Vector3.Zero;
...
    Matrix inverseTransform = Matrix.Invert(modelTransform);
    // STORE WORLDSPACE RAY.
    Ray oldRay = ray;

    ray.Position = Vector3.Transform(ray.Position, inverseTransform);
    ray.Direction = Vector3.TransformNormal(ray.Direction, inverseTransform);
    ray.Direction.Normalize();

    // Look up our custom collision data from the Tag property of the model.
    Dictionary<string, object> tagData = (Dictionary<string, object>)model.Tag;

    if (tagData == null)
    {
        throw new InvalidOperationException(
            "Model.Tag is not set correctly. Make sure your model " +
            "was built using the custom TrianglePickingProcessor.");
    }

    // Start off with a fast bounding sphere test.
    BoundingSphere boundingSphere = (BoundingSphere)tagData["BoundingSphere"];

    if (boundingSphere.Intersects(ray) == null)
    {
        // If the ray does not intersect the bounding sphere, we cannot
        // possibly have picked this model, so there is no need to even
        // bother looking at the individual triangle data.
        insideBoundingSphere = false;

        return null;
    }
    else
    {
        // The bounding sphere test passed, so we need to do a full
        // triangle picking test.
        insideBoundingSphere = true;

        // Keep track of the closest triangle we found so far,
        // so we can always return the closest one.
        float? closestIntersection = null;

        // Loop over the vertex data, 3 at a time (3 vertices = 1 triangle).
        Vector3[] vertices = (Vector3[])tagData["Vertices"];

        for (int i = 0; i < vertices.Length; i += 3)
        {
            // Perform a ray to triangle intersection test.
            float? intersection;

            RayIntersectsTriangle(ref ray,
                                    ref vertices[i],
                                    ref vertices[i + 1],
                                    ref vertices[i + 2],
                                    out intersection);

            // Does the ray intersect this triangle?
            if (intersection != null)
            {
                // RECOMPUTE DISTANCE IN WORLD SPACE:
                Vector3 vertexA = Vector3.Transform(vertices[i], modelTransform);
                Vector3 vertexB = Vector3.Transform(vertices[i+1], modelTransform);
                Vector3 vertexC = Vector3.Transform(vertices[i+2], modelTransform);

                RayIntersectsTriangle(ref oldRay,
                                    ref vertexA,
                                    ref vertexB,
                                    ref vertexC,
                                    out intersection);

                // If so, is it closer than any other previous triangle?
                if ((closestIntersection == null) ||
                    (intersection < closestIntersection))
                {
                    // Store the distance to this triangle.
                    closestIntersection = intersection;

                    // Store the three vertex positions in world space.
                    vertex1 = vertexA;
                    vertex2 = vertexB;
                    vertex3 = vertexC;
                }
            }
        }

        return closestIntersection;
    }
}
\$\endgroup\$
  • \$\begingroup\$ An inverse matrix also inverses the scaling. I do not see any obvious error in the code in XNA or in the idea behind it. Are you sure not something else is going on? Maybe try creating a minimum example that reproduces the error which you can verify by hand? \$\endgroup\$ – Roy T. Mar 25 '14 at 19:16
  • \$\begingroup\$ I might be wrong about the causes of the problem, but all I do is simply change the default matrix for pickable objects in this sample by this expression:modelWorldTransforms[i] = Matrix.CreateScale(1.01f)* Matrix.CreateTranslation(new Vector3(x, 0, 0)); If you put into the scaling matrix anything greater than 1 - everything gets screwed up. If you can download the sample and try for yourself, you might make a better judgement about the cause. \$\endgroup\$ – cubrman Mar 25 '14 at 19:48
  • \$\begingroup\$ Thanks for this, very helpful (even outside XNA). For those who might be wondering what Vector3.TransformNormal does it transforms by the matrix in the same way as Vector3.Transform but ignores the translation component, quite important to get that right! \$\endgroup\$ – CMash Sep 28 '15 at 15:42
7
\$\begingroup\$

Transforming the ray position and direction by the inverse model transformation is correct. However, many ray-intersection routines assume that the ray direction is a unit vector. If the model transformation involves scaling, the ray direction won't be a unit vector afterward, and should likely be renormalized.

However, the distance along the ray returned by the intersection routines will then be measured in model space, and won't represent the distance in world space. If it's a uniform scale, you can simply multiply the returned distance by the scale factor to convert it back to world-space distance. For non-uniform scaling it's trickier; probably the best way is to transform the intersection point back to world space and then re-measure the distance from the ray origin there.

\$\endgroup\$
  • \$\begingroup\$ Guess what? Renormalizing the direction vector after the initial inverse matrix transformation solved everything. I don't know why the second part of your answer was unnesessary, it seemed pretty logical, but that's how things go. Thanks for figuring that out! \$\endgroup\$ – cubrman Mar 26 '14 at 6:53
  • \$\begingroup\$ There is another problem now though. If I try to change the model's world matrix at runtime - everything gets screwed up again! Nomatter how I compute the triangle test - world space or local space! This is madness... \$\endgroup\$ – cubrman Mar 26 '14 at 7:05
  • \$\begingroup\$ Ok it does work with world coordinates, my problem was that I fiddled with the absoluteBoneTransformes. The original sample multiplies every world matrix by this matrix (the one with the parentBone index) when it draws the models and DOES NOT multiply them when computing intersection. In our app we don't multiply the world matrix in any case. I fixed this by multiplying the model's world matrix by the inverse absoluteBoneTransformes at the picking stage, but I messed up the matrix multiplication order and had this issue. So far I think I will have to implement the second part of ur answer... \$\endgroup\$ – cubrman Mar 26 '14 at 7:31
  • 1
    \$\begingroup\$ Ok I made it. You were totally right, both of your suggestions were necessary. Check the question for the full code. \$\endgroup\$ – cubrman Mar 26 '14 at 10:37
  • 1
    \$\begingroup\$ Affine transforms scale parallel distance measurements equally, so you can cache the scale value required to renormalize the ray once in object space, and use that to correct the distance value, rather than converting the intersection point to worldspace and re-measuring. \$\endgroup\$ – DMGregory Mar 26 '14 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.