Jump to content
  • Advertisement
Sign in to follow this  

Ray vs tri (terrain) - ray mirrored on (z)axis?

This topic is 2045 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts



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;

	        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;

	        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

            // height scaling factor
            const float scale = 1.0f/5.0f;
            // resize height vector
            // 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

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

            for(const Triangle& tri : m_vTris)
                if(tri.Intersect(ray, &vOut))
                        *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
                *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
                *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?

Edited by Juliean

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!