Page 1 of 3

Raycasting to the polygon level [solved]

Posted: Tue Aug 15, 2006 6:19 am
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?

Posted: Tue Aug 15, 2006 6:32 am
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.

Posted: Tue Aug 15, 2006 6:39 am
by gerds
Is opcode integrated in some meaningful way?


Ogre::Entity *pentity;

// some code to create the entity here

OpCodeObj obj;
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?

Posted: Tue Aug 15, 2006 7:26 am
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:

Posted: Tue Aug 15, 2006 7:50 am
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

Posted: Tue Aug 15, 2006 8:01 am
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).

Posted: Tue Aug 15, 2006 8:52 am
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).

Posted: Tue Aug 15, 2006 9:30 am
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.

Posted: Tue Aug 15, 2006 9:32 am
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: ... ogreopcode

*shrug* wasn't that difficult...

Posted: Wed Aug 16, 2006 4:47 am
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);
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

        // 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);
        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))
        // 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,             

            // 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);
        // 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:
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( !added_shared )
                vertex_count += mesh->sharedVertexData->vertexCount;
                added_shared = true;
            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))
                added_shared = true;
                shared_offset = current_offset;

            const Ogre::VertexElement* posElem =

            Ogre::HardwareVertexBufferSharedPtr vbuf =

            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;

            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);
            for ( size_t k = 0; k < numTris*3; ++k)
                indices[index_offset++] = static_cast<unsigned long>(pShort[k]) +
                    static_cast<unsigned long>(offset);

        current_offset = next_offset;

Posted: Wed Aug 16, 2006 6:56 am
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?

Posted: Wed Aug 16, 2006 7:50 am
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.

Posted: Thu Aug 17, 2006 4:24 am
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! ;)

Posted: Thu Aug 17, 2006 5:30 am
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?

Posted: Thu Aug 17, 2006 5:49 am
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. :)

Posted: Thu Aug 17, 2006 7:48 am
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.

Posted: Fri Aug 18, 2006 8:31 am
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). :)

Posted: Wed Sep 27, 2006 6:17 am
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.

Posted: Wed Sep 27, 2006 7:50 am
by Nudel
Is OgreNewt cabable of raycasting on polygon level?

Posted: Wed Sep 27, 2006 8:50 pm
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.

Posted: Wed Dec 06, 2006 8:59 pm
by hmoraldo
Is there any reason not to post it in the wiki, in the Code Snippits section?

Posted: Thu Dec 07, 2006 5:34 pm
by hmoraldo
Well, I posted it in the wiki here: ... ygon_level

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

Best regards,

Posted: Thu Dec 07, 2006 11:33 pm
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

Posted: Sat Jan 06, 2007 12:18 pm
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:


Posted: Wed May 16, 2007 5:58 pm
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: ... 28Mogre%29