Hello,

I'm trying to implement a triangle intersection test to deremine where to place some objects on the terrain (via heightmap), if I click on it. So far things work ok, however I found a weird bug, where the ray would intersect the triangle the is on the opposite direction of the z axis. Let me explain it better: If the mouse is on the left of the screen, it will collide with the triangle the is on the equivalent position on the right, and vice versa. The more I move the mouse to the middle of the screen, the more the position gets to where it should be - but it never reaches it, even if I am totally in the middle. The actual position and orientation of the camera has no effect on this, it is the same if I am in the middle of the terrain, or at the egde.

Take a look for example at the screenshot in the attachment. I can place the cubes outside of the terrain, because if the mouse is left, it will report a collision with a triangle on the right. Note that it will still place the object in the direciton of the ray, because of the way I calculate the position (see later).

So, let me show you my code. This is how I calculate the view ray:

        math::Ray ViewRayScreenPos(const math::Vector2& vScreenPos, const Camera& camera, const Screen& screen)
        {
	        const D3DXVECTOR3 vNear((float)vScreenPos.x, (float)vScreenPos.y, 0.0f);
	        const D3DXVECTOR3 vFar((float)vScreenPos.x, (float)vScreenPos.y, 1.0f);
            D3DVIEWPORT9 viewPort;
            viewPort.X = 0;
            viewPort.Y = 0;
            viewPort.Width = screen.GetSize().x;
            viewPort.Height = screen.GetSize().y;
            viewPort.MinZ = screen.GetMinZ();
            viewPort.MaxZ = screen.GetMaxZ();

	        D3DXMATRIX mWorld;
	        D3DXMatrixIdentity(&mWorld);

	        D3DXVECTOR3 vP1, vP2;
	        D3DXVec3Unproject(&vP1, &vNear, &viewPort, &camera.GetProjectionMatrix(), &camera.GetViewMatrix(), &mWorld); 

	        D3DXVec3Unproject(&vP2, &vFar, &viewPort, &camera.GetProjectionMatrix(), &camera.GetViewMatrix(), &mWorld); 

            const math::Vector3 v1(vP1.x, vP1.y, vP1.z);
            math::Vector3 vDist(vP2.x, vP2.y, vP2.z);
	        vDist -= v1;
            vDist.Normalize();

	        return math::Ray(v1, vDist);
        }

Note that since I havn't implemented a custom Unproject-method yet, I'm relating on the D3DX-functions. However, this method is most likely not the problem. I tested it with some custom-generated rays too, they show the exact same behaviour, plus the ray is working in my editor to pick objects based on AABBs. Now this is now the heighfield-representation:

        Heightfield::Heightfield(gfx::Texture& texture, unsigned int size): m_size(size), BaseVolume(-(signed)size / 2.0f, 0.0f, -(signed)size / 2.0f)
        {
            // mark texture as readable
            texture.SetMuteable(true);

            // height scaling factor
            const float scale = 1.0f/5.0f;
            // resize height vector
            m_vHeights.resize(m_size);
            // add heights to vector
            for(unsigned int i = 0; i < m_size; i++)
            {
                for(unsigned int j = 0; j < m_size; j++)
                {
                    //push back
                    m_vHeights.push_back( (float)texture.GetPixel<BYTE>(i, j) * scale );
                }
            }

            // precaculate half size of heightfield
            const int halfSize = (signed)m_size/2;
            // add triangles to heightfield
            for(int i = 0; i < (signed)m_size-1; i++)
            {
                for(int j = 0; j < (signed)m_size-1; j++)
                {
                    // first triangle: 0/0 -> 0/1 -> 1/0
                    Vector3 vPos1(i - halfSize, m_vHeights[j], j - halfSize);
                    Vector3 vPos2(i + 1 - halfSize, m_vHeights[i+1][j], j - halfSize);
                    Vector3 vPos3(i - halfSize, m_vHeights[j+1], j + 1 - halfSize);
                    
                    m_vTris.push_back(Triangle(vPos1, vPos2, vPos3));

                    // second triangle: 1/0 -> 0/1 -> 1/1
                    Vector3 vPos4(i + 1 - halfSize, m_vHeights[i + 1][j], j - halfSize);
                    Vector3 vPos5(i - halfSize, m_vHeights[j + 1], j + 1 - halfSize);
                    Vector3 vPos6(i + 1- halfSize, m_vHeights[i + 1][j + 1], j + 1 - halfSize);
                    
                    m_vTris.push_back(Triangle(vPos4, vPos5, vPos6));
                }
            }

            // unmark as readable
            texture.SetMuteable(false);
        }

        bool Heightfield::Intersect(const Ray& ray, math::Vector3* pOut) const
	    {
            Vector3 vOut;

            for(const Triangle& tri : m_vTris)
            {
                if(tri.Intersect(ray, &vOut))
                {
                    if(pOut)
                        *pOut = vOut;
                    return true;
                }
            }

		    return false;
	    }

Obviously, for that not-optimized stage, I decided to do a direct ray vs. all tris test. The triangles are simply generated from the heightmap. And finally, this is my triangle collision test:

        bool Triangle::Intersect(const Ray& ray, math::Vector3* pOut) const
        {
            // calculate edges
            const Vector3 vEdge1(m_vP2 - m_vP1);
            const Vector3 vEdge2(m_vP3 - m_vP1);

            // needed for determinante and u
            const Vector3 vP( ray.m_vDirection.Cross(vEdge2) );

            // calculate determinante
            const float det = vEdge1.Dot(vP);

            // perpendicular if determinante is near zero
            if(abs(det) < 0.0001f)
                return false;
            const float inv_det = 1.0f / det;

            // distance from first vertex to ray origin
            const Vector3 vT( ray.m_vOrigin - m_vP1 );

            // calculate u coordinate
            const float u = vT.Dot(vP) * inv_det;
            // test bounds
            if(u < 0.0f || u > 1.0f)
                return false;

            // used for v coordinate
            const Vector3 vQ = vT.Cross(vEdge1);

            // calculate v coordinated
            const float v = ray.m_vDirection.Dot(vQ) * inv_det;
            // test bounds
            if(v < 0.0f || u + v > 1.0f)
                return false;

            // calculate t coordinate (on ray)
            const float t = vEdge2.Dot(vQ) * inv_det;

            // store intersection component
            if(pOut)
                *pOut = ray.m_vOrigin + ray.m_vDirection * t;

            // intersected
            return true;
        }
 

Which has been taken from http://www.cs.virginia.edu/~gfx/Courses/2003/ImageSynthesis/papers/Acceleration /Fast%20MinimumStorage%20RayTriangle%20Intersection.pdf . Checked it multiple times for erros, found none. Took a second site featuring an almost identical algorythm, seemed fine, too.

Now, does anyone of you see any possible possible issues, or did somebody encounter this problem himself? Unfortunately I'm not mathematically adviced enough, so while I do unterstand somewhat how this collison code is supposed to work, I can't check the result of a dot product and tell something is wrong, or such. I already tried to invert the z-coordinate, which didn't work, since that would mirror the position the object gets put to, too.

EDIT: Switching to barycentric position calculation in combination with mirroring the ray on the z-axis (*= -1) results at least in objects being put at the right height for the triangle, but it now seems to get put to some random triangle near the position I clicked, and if I click around a little, objects get stacked on to the same positions over and over again:

// ....

            // store intersection component
            if(pOut)
                *pOut = m_vP1 * ( 1.0f - u - v) + m_vP2 * u + m_vP3 * v;

// ....

Thats at least one step further, but still, I shouldn't have to invert the z-axis, and this "snapping" is also making this unplayable. Any ideas?

Solved, I actually had a typo in my vector classes cross product method :/