• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Juliean

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

1 post in this topic

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[i].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[i][j], j - halfSize);
                    Vector3 vPos2(i + 1 - halfSize, m_vHeights[i+1][j], j - halfSize);
                    Vector3 vPos3(i - halfSize, m_vHeights[i][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[i][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?

Edited by Juliean
0

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  
Followers 0