Raycasting to the polygon level [solved]

Problems building or running the engine, queries about how to use features etc.
User avatar
gerds
Goblin
Posts: 260
Joined: Mon Sep 01, 2003 3:59 am
Location: London, United Kingdom
x 1

Raycasting to the polygon level [solved]

Post by gerds »

I've added raycasting to the ogre wrapper for the vision engine I'm working on, however to my amazement ogre only raycasts to the bounding box level. Is this correct?

I need to be able to raycast to the polygon level so we can place user-defined features in the scene. How is this possible?
Last edited by gerds on Tue Aug 29, 2006 7:36 am, edited 1 time in total.
User avatar
xavier
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 9481
Joined: Fri Feb 18, 2005 2:03 am
Location: Dublin, CA, US
x 22

Post by xavier »

You should use a physics or collision-detection library. Ogre's scene queries are designed to operate on AABB's for speed -- it's for rendering, not collisions. When you need finer resolution than what Ogre has, you need to use 3rd-party libs. OPCODE and Bullet seem to work pretty well; there is an OgreOPCODE adapter available in unknown state of fitness -- search should turn it up.
User avatar
gerds
Goblin
Posts: 260
Joined: Mon Sep 01, 2003 3:59 am
Location: London, United Kingdom
x 1

Post by gerds »

Is opcode integrated in some meaningful way?

--------------------------------------------------------------
eg:

Ogre::Entity *pentity;

// some code to create the entity here

OpCodeObj obj;
obj.loadFromOgre(pentity);
hits = obj.raycast(Vector3(0,100,0), Vector3(0,-1,0));

--------------------------------------------------------------

or do we have to do it all ourselves?

We have no need for a physics library of any sort (apart from raycasting - which shouldn't need a physics library? hmm...). We hardly want to load every entity in the world in to OPCODE meshes - we have many thousands of entities.

Has anyone got a snipit of code which shows this working?
User avatar
Frenetic
Bugbear
Posts: 806
Joined: Fri Feb 03, 2006 7:08 am

Post by Frenetic »

This has to be the bajillionth thread I've seen like this. How hard is triangle-collision anyways? I know I could implement the algorithm itself, so within Ogre how hard would it be to take the MoveableObject returned by RaySceneQuery and iterate across the appropriate vertices? Is there some caveat within Ogre's design preventing this?

I'm not saying this should be added to the engine itself, but I think its about time an entry was made in the wiki for a TriCollisionEntity or somesuch.


PS. I can't seem to find any info on OgreOpCode... searching Google and the Ogre Wiki (and the Addons Forum) didn't turn anything up! :shock:
User avatar
gerds
Goblin
Posts: 260
Joined: Mon Sep 01, 2003 3:59 am
Location: London, United Kingdom
x 1

Post by gerds »

I'm almost done with a 'brute force' technique.

I'm taking the 'vector of hits' returned from the ray query, sorted by which is closest, and then I iterate over the vector doing this:

1) convert the entity mesh to triangles (using a forum cut-paste function)
2) test each triangle and save off the closest one hit
3) return the closest hit, or if none hit try the next entity
User avatar
Frenetic
Bugbear
Posts: 806
Joined: Fri Feb 03, 2006 7:08 am

Post by Frenetic »

gerds wrote:I'm almost done with a 'brute force' technique.
I would be delighted if you would be so kind as to post your code when you are finished. I'm sure others would appreciate it too.

Also, I just realized that entities with animation affecting the vertices directly (skeletal anim, etc) would require extra steps for triangle collision if the procedure just iterated acrosss the data in the vertex buffer (otherwise it would be testing the untransformed mesh).
User avatar
gerds
Goblin
Posts: 260
Joined: Mon Sep 01, 2003 3:59 am
Location: London, United Kingdom
x 1

Post by gerds »

Yeah no worries, maybe I'll paste it on the wiki and put a link or something.
Its a bit buggy at the moment, returning hits on some entities and not others :oops:

Good news is the performance seems to be ok (I've got meshes around 100-2000 polys). I'll let you know when its working.

I wont be able to add in the 'animation transform effects', I just dont have time and we dont need it. We only need to be able to raycast objects for placement against our static terrain (roads, platforms, chairs etc).
User avatar
xavier
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 9481
Joined: Fri Feb 18, 2005 2:03 am
Location: Dublin, CA, US
x 22

Post by xavier »

Guys, Ogre is a rendering engine. The features it offers are for rendering. Polygon-level raycasting accuracy is not a rendering requirement, so Ogre doesn't have it, nor does it need it. As you have discovered, if you need it, you are free to code it yourself or find a library that will do it for you.
User avatar
xavier
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 9481
Joined: Fri Feb 18, 2005 2:03 am
Location: Dublin, CA, US
x 22

Post by xavier »

Frenetic wrote:Is there some caveat within Ogre's design preventing this?
See my post above.
PS. I can't seem to find any info on OgreOpCode... searching Google and the Ogre Wiki (and the Addons Forum) didn't turn anything up! :shock:
http://www.google.com/custom?domains=ww ... ogreopcode

*shrug* wasn't that difficult...
User avatar
gerds
Goblin
Posts: 260
Joined: Mon Sep 01, 2003 3:59 am
Location: London, United Kingdom
x 1

Post by gerds »

I know where you are coming from with the comment "ogre is a rendering engine" and I like the fact that ogre is a rendering only engine... however, I would really like to be able to do polygon accurate raycasting within ogre. Although this might not be a requirement of 'rendering' it would be very useful to a lot of people.

I have many thousands of entities in my huge scene and I dont want the overhead of passing all those thousands of entities in to opcode to generate the meshes. Ogre already has all of that mesh information so I would hope there is some *easy* way to do it in ogre, even if it is very suboptimal. For example, lots of graphics apps require picking, and you can't do picking on AABB bounding boxes alone. What if one small object is within another objects bounding box, then you cant pick that smaller object without having to 'zoom-in' to the extreme to find it (and hope you dont have near plane problems).

Anyhow. I've worked out how to raycast to the polygon level, its not perfect 100% of the time, and its far from optimal, however it does allow me to do what I want ("raycast new objects to the ground, wall, bench etc").

It probably doesn't work for static geometry, or hardware based animations, but give it a go in your code if you like.

The following code is a direct copy-paste from our own engine, which is basically a wrapper for ogre to more easily plug-in with our old engine - so you'll have to change a few lines of code to get things to work for you.

During engine initialisation do this:

Code: Select all

// create the ray scene query object
    m_pray_scene_query = m_pscene_manager->createRayQuery(Ogre::Ray(), Ogre::SceneManager::WORLD_GEOMETRY_TYPE_MASK);
    if (NULL == m_pray_scene_query)
    {
        LOG_ERROR << "Failed to create Ogre::RaySceneQuery instance" << ENDLOG;
		return (false);
    }
    m_pray_scene_query->setSortByDistance(true);
This is the method of the engine which does the raycast:

Code: Select all

// raycast from a point in to the scene.
// returns success or failure.
// on success the point is returned in the result.
bool OgreVisionEngine::RaycastFromPoint(const Vector3f &point,
                                        const Vector3f &normal,
                                        Vector3f &result)
{
    // create the ray to test
    Ogre::Ray ray(Ogre::Vector3(point.x, point.y, point.z), 
                  Ogre::Vector3(normal.x, normal.y, normal.z));

    // check we are initialised
    if (m_pray_scene_query != NULL)
    {
        // create a query object
        m_pray_scene_query->setRay(ray);

        // execute the query, returns a vector of hits
        if (m_pray_scene_query->execute().size() <= 0)
        {
            // raycast did not hit an objects bounding box
            return (false);
        }
    }
    else
    {
        LOG_ERROR << "Cannot raycast without RaySceneQuery instance" << ENDLOG;
        return (false);
    }    

    // at this point we have raycast to a series of different objects bounding boxes.
    // we need to test these different objects to see which is the first polygon hit.
    // there are some minor optimizations (distance based) that mean we wont have to 
    // check all of the objects most of the time, but the worst case scenario is that
    // we need to test every triangle of every object.
    Ogre::Real closest_distance = -1.0f;
    Ogre::Vector3 closest_result;
    Ogre::RaySceneQueryResult &query_result = m_pray_scene_query->getLastResults();
    for (size_t qr_idx = 0; qr_idx < query_result.size(); qr_idx++)
    {
        // stop checking if we have found a raycast hit that is closer
        // than all remaining entities
        if ((closest_distance >= 0.0f) &&
            (closest_distance < query_result[qr_idx].distance))
        {
             break;
        }
        
        // only check this result if its a hit against an entity
        if ((query_result[qr_idx].movable != NULL) &&
            (query_result[qr_idx].movable->getMovableType().compare("Entity") == 0))
        {
            // get the entity to check
            Ogre::Entity *pentity = static_cast<Ogre::Entity*>(query_result[qr_idx].movable);            

            // mesh data to retrieve			
            size_t vertex_count;
            size_t index_count;
            Ogre::Vector3 *vertices;
            unsigned long *indices;

            // get the mesh information
			OgreVE::GetMeshInformation(pentity->getMesh(), vertex_count, vertices, index_count, indices,             
									   pentity->getParentNode()->getWorldPosition(),
									   pentity->getParentNode()->getWorldOrientation(),
									   pentity->getParentNode()->getScale());

            // test for hitting individual triangles on the mesh
            bool new_closest_found = false;
            for (int i = 0; i < static_cast<int>(index_count); i += 3)
            {
                // check for a hit against this triangle
                std::pair<bool, Ogre::Real> hit = Ogre::Math::intersects(ray, vertices[indices[i]], 
                    vertices[indices[i+1]], vertices[indices[i+2]], true, false);

                // if it was a hit check if its the closest
                if (hit.first)
                {
                    if ((closest_distance < 0.0f) ||
                        (hit.second < closest_distance))
                    {
                        // this is the closest so far, save it off
                        closest_distance = hit.second;
                        new_closest_found = true;
                    }
                }
            }

			// free the verticies and indicies memory
            delete[] vertices;
            delete[] indices;

            // if we found a new closest raycast for this object, update the
            // closest_result before moving on to the next object.
            if (new_closest_found)
            {
                closest_result = ray.getPoint(closest_distance);                
            }
        }        
    }

    // return the result
    if (closest_distance >= 0.0f)
    {
        // raycast success
        result.Set(closest_result.x, closest_result.y, closest_result.z);
        return (true);
    }
    else
    {
        // raycast failed
        return (false);
    }
Here's the function GetMeshInformation (found on the wiki) that the above method calls.

Code: Select all

// Get the mesh information for the given mesh.
// Code found on this forum link: http://www.ogre3d.org/wiki/index.php/RetrieveVertexData
void OgreVE::GetMeshInformation(const Ogre::MeshPtr mesh,
                                size_t &vertex_count,
                                Ogre::Vector3* &vertices,
                                size_t &index_count,
                                unsigned long* &indices,
                                const Ogre::Vector3 &position,
                                const Ogre::Quaternion &orient,
                                const Ogre::Vector3 &scale)
{
    bool added_shared = false;
    size_t current_offset = 0;
    size_t shared_offset = 0;
    size_t next_offset = 0;
    size_t index_offset = 0;

    vertex_count = index_count = 0;

    // Calculate how many vertices and indices we're going to need
    for (unsigned short i = 0; i < mesh->getNumSubMeshes(); ++i)
    {
        Ogre::SubMesh* submesh = mesh->getSubMesh( i );

        // We only need to add the shared vertices once
        if(submesh->useSharedVertices)
        {
            if( !added_shared )
            {
                vertex_count += mesh->sharedVertexData->vertexCount;
                added_shared = true;
            }
        }
        else
        {
            vertex_count += submesh->vertexData->vertexCount;
        }

        // Add the indices
        index_count += submesh->indexData->indexCount;
    }


    // Allocate space for the vertices and indices
    vertices = new Ogre::Vector3[vertex_count];
    indices = new unsigned long[index_count];

    added_shared = false;

    // Run through the submeshes again, adding the data into the arrays
    for ( unsigned short i = 0; i < mesh->getNumSubMeshes(); ++i)
    {
        Ogre::SubMesh* submesh = mesh->getSubMesh(i);

        Ogre::VertexData* vertex_data = submesh->useSharedVertices ? mesh->sharedVertexData : submesh->vertexData;

        if((!submesh->useSharedVertices)||(submesh->useSharedVertices && !added_shared))
        {
            if(submesh->useSharedVertices)
            {
                added_shared = true;
                shared_offset = current_offset;
            }

            const Ogre::VertexElement* posElem =
                vertex_data->vertexDeclaration->findElementBySemantic(Ogre::VES_POSITION);

            Ogre::HardwareVertexBufferSharedPtr vbuf =
                vertex_data->vertexBufferBinding->getBuffer(posElem->getSource());

            unsigned char* vertex =
                static_cast<unsigned char*>(vbuf->lock(Ogre::HardwareBuffer::HBL_READ_ONLY));

            // There is _no_ baseVertexPointerToElement() which takes an Ogre::Real or a double
            //  as second argument. So make it float, to avoid trouble when Ogre::Real will
            //  be comiled/typedefed as double:
            //      Ogre::Real* pReal;
            float* pReal;

            for( size_t j = 0; j < vertex_data->vertexCount; ++j, vertex += vbuf->getVertexSize())
            {
                posElem->baseVertexPointerToElement(vertex, &pReal);

                Ogre::Vector3 pt(pReal[0], pReal[1], pReal[2]);

                vertices[current_offset + j] = (orient * (pt * scale)) + position;
            }

            vbuf->unlock();
            next_offset += vertex_data->vertexCount;
        }


        Ogre::IndexData* index_data = submesh->indexData;
        size_t numTris = index_data->indexCount / 3;
        Ogre::HardwareIndexBufferSharedPtr ibuf = index_data->indexBuffer;

        bool use32bitindexes = (ibuf->getType() == Ogre::HardwareIndexBuffer::IT_32BIT);

        unsigned long*  pLong = static_cast<unsigned long*>(ibuf->lock(Ogre::HardwareBuffer::HBL_READ_ONLY));
        unsigned short* pShort = reinterpret_cast<unsigned short*>(pLong);


        size_t offset = (submesh->useSharedVertices)? shared_offset : current_offset;

        if ( use32bitindexes )
        {
            for ( size_t k = 0; k < numTris*3; ++k)
            {
                indices[index_offset++] = pLong[k] + static_cast<unsigned long>(offset);
            }
        }
        else
        {
            for ( size_t k = 0; k < numTris*3; ++k)
            {
                indices[index_offset++] = static_cast<unsigned long>(pShort[k]) +
                    static_cast<unsigned long>(offset);
            }
        }

        ibuf->unlock();
        current_offset = next_offset;
    }
}
[/code]
Last edited by gerds on Wed Sep 27, 2006 6:18 am, edited 2 times in total.
User avatar
xavier
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 9481
Joined: Fri Feb 18, 2005 2:03 am
Location: Dublin, CA, US
x 22

Post by xavier »

gerds wrote:however, I would really like to be able to do polygon accurate raycasting within ogre. Although this might not be a requirement of 'rendering' it would be very useful to a lot of people.
And there, you did it. That was my point. ;)

I am toying with the idea again of a sort of "OgreUT" library of "things that are useful and common but do not belong in the core Ogre codebase". Something like this would probably be a candidate for inclusion in such a project, if you don't mind. Are you just tossing this out with just a copyright to protect it or would you rather it go out under some form of license?
User avatar
gerds
Goblin
Posts: 260
Joined: Mon Sep 01, 2003 3:59 am
Location: London, United Kingdom
x 1

Post by gerds »

Yeah I've got a OgreHelpers.h/.cpp group of functions that do useful things like this. That's how I've handled the "common functions not belonging to the ogre codebase" stuff for my project.

Feel free to grab the above bit of code and put it in a common library under LGPL. I pieced it together from info on the forums and the wiki anyway, there's only a small amount of "glue" I added to stick it together.
User avatar
Frenetic
Bugbear
Posts: 806
Joined: Fri Feb 03, 2006 7:08 am

Post by Frenetic »

Frenetic wrote:I'm not saying this should be added to the engine itself, but I think its about time an entry was made in the wiki for a TriCollisionEntity or somesuch.
Be cool, xavier. I am -- I think we all are -- well aware that Ogre is Specifically A Rendering Engine. I was just wondering why a 3rd party had not covered this specific and much-demanded base before, like gerds has so kindly done just now. Thanks for sharing your code, gerds!

By "limitations within Ogre" I was just asking if there is a reason why Ogre would get in the way of someone using Ogre's internal poly/vertex information for a simple collision algorithm. No need to talk to me like I'm a total bonehead! ;)
User avatar
xavier
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 9481
Joined: Fri Feb 18, 2005 2:03 am
Location: Dublin, CA, US
x 22

Post by xavier »

Sorry if you took it personally. The question was "why doesn't Ogre have 'better' scene queries?" and I answered that.

I don't know that Ogre gets in anyone's way at all -- what makes you say that it does?
User avatar
Frenetic
Bugbear
Posts: 806
Joined: Fri Feb 03, 2006 7:08 am

Post by Frenetic »

xavier wrote:I don't know that Ogre gets in anyone's way at all -- what makes you say that it does?
It was just a feeling ("is this not as simple as I think it is?") I was also thinking in terms of performance, eg. maybe iterating across the vertex buffer isn't a good way to do it. Its been a while since I've played with Ogre's vertex API.

Anyways, it looks like gerds is well on his way, so hopefully we'll have yet another wiki link to throw at people. :)
User avatar
xavier
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 9481
Joined: Fri Feb 18, 2005 2:03 am
Location: Dublin, CA, US
x 22

Post by xavier »

If you lock the VBO (ok, GL parlance, I know) for READ_WRITE then it will likely be put into system RAM (maybe AGP memory, maybe not -- it's up to the drivers). This is efficient for the application of course, but not very good for the GPU.

You simply can't have the same data in two places at once, is the problem -- it's the same issue with collisions/shadows and hardware skinning. The tradeoff there is an extra software skinning calculation (and extra VB memory) that allows CPU-bound (decoupled from the GPU) access to transformed vertices for things like CPU collision detection.

Another reason to use independent convex hulls or implicit collision geometry if you ask me -- there rarely is any good immutable reason for actual trimesh collision in a real-time application such as a game...and if you are doing scientific simulations then none of the real-time performance caveats apply. ;)

And none of this is unique to Ogre -- you have the exact same issues with raw GL or D3D. It's a GPU/driver issue.
User avatar
Frenetic
Bugbear
Posts: 806
Joined: Fri Feb 03, 2006 7:08 am

Post by Frenetic »

Yes, now that you mention those things, it makes sense that (implementation-specific) caveats would indeed be present.

However, for non-animated-mesh collision, something along the lines of what gerds came up with would be a good addition to the wiki IMO, and would probably satisfy most of the people demanding trimesh collision detection (without having to plug in a physics engine). :)
User avatar
gerds
Goblin
Posts: 260
Joined: Mon Sep 01, 2003 3:59 am
Location: London, United Kingdom
x 1

Post by gerds »

** Just an update for anyone who has used the above code **

I looked in to the code today and found the bug which caused it to "not work 100% of the time" - I needed to take in to account the entities "world transform" and "world orientation".

I've edited the code in the post above and added the fix.
As far as I can tell it works perfectly now (as tested on my rather large and complicated scene).

If anyone has any problems using it let me know.
Nudel
Halfling
Posts: 79
Joined: Thu Mar 23, 2006 4:14 pm
Location: Vienna

Post by Nudel »

Is OgreNewt cabable of raycasting on polygon level?
PatrickB3
Greenskin
Posts: 101
Joined: Mon May 09, 2005 3:37 am
Location: California, USA

Post by PatrickB3 »

I use coldet for my collision detection and do it a little differently such as I create the collision model when the entity is loaded if I haven't already made one from that mesh and then just transform it before checking for collision that way I don't have to create it every frame. Plus I do other stuff like use a simplier model for collision if the real entity has a high polygon count and I don't care if it is 100% accurate for that model.

Anyways... I use that same code from the Wiki. I just store it in a coldet model rather than do anything with it myself. However I have found that it does some wacky stuff when an entity has submeshes. Sometimes it makes an accurate collsion model sometimes it don't. Seems to depend on the model since if it don't then it never does for that entity. Not a random thing.

Generally I make a collision object for things and make sure that only has one mesh to avoid the problem. But if you you aren't I would be on the lookout for that.
User avatar
hmoraldo
OGRE Expert User
OGRE Expert User
Posts: 517
Joined: Tue Mar 07, 2006 11:22 pm
Location: Buenos Aires, Argentina
x 1

Post by hmoraldo »

Is there any reason not to post it in the wiki, in the Code Snippits section?
H. Hernan Moraldo
Personal website
User avatar
hmoraldo
OGRE Expert User
OGRE Expert User
Posts: 517
Joined: Tue Mar 07, 2006 11:22 pm
Location: Buenos Aires, Argentina
x 1

Post by hmoraldo »

Well, I posted it in the wiki here: http://www.ogre3d.org/wiki/index.php/Ra ... ygon_level

I think it's too nice to keep it here and not in the wiki.

Best regards,
H. Hernan Moraldo
Personal website
User avatar
gerds
Goblin
Posts: 260
Joined: Mon Sep 01, 2003 3:59 am
Location: London, United Kingdom
x 1

Post by gerds »

Thanks for that hmoraldo, I'll try and be more proactive in future but I'm overrun with work at the moment.

Thanks again :D
Jerome
Gnoblar
Posts: 3
Joined: Tue Dec 12, 2006 3:14 pm

Post by Jerome »

Hello and thanks a lot for posting the code, it works great for me! :D

Anyway, I wanted to know if anyone has any tip on how to extend it to animated meshes; I would like to use it on an animated ocean surface as height calculator... :roll:

Jerome
funguine
Gnoblar
Posts: 10
Joined: Mon Jan 15, 2007 5:28 pm
Location: Oulu, Finland
x 1

Post by funguine »

gerds wrote: The following code is a direct copy-paste from our own engine, which is basically a wrapper for ogre to more easily plug-in with our old engine - so you'll have to change a few lines of code to get things to work for you.
And the following is copy-paste from our Mogre-port of your algorithm,
as displayed on the Wiki. Seems to work fine. This version also
reports the normal of the face that was hit.

Now available on the Wiki:
http://www.ogre3d.org/wiki/index.php/Ra ... 28Mogre%29
Last edited by funguine on Wed May 16, 2007 7:10 pm, edited 1 time in total.