Raycasting to the polygon level [solved]

Problems building or running the engine, queries about how to use features etc.

Raycasting to the polygon level [solved]

Postby gerds » Tue Aug 15, 2006 6:19 am

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
gerds
Goblin
 
Posts: 260
Kudos: 1
Joined: 01 Sep 2003
Location: London, United Kingdom

Postby xavier » Tue Aug 15, 2006 6:32 am

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
xavier
OGRE Retired Moderator
OGRE Retired Moderator
 
Posts: 9481
Kudos: 23
Joined: 18 Feb 2005
Location: Dublin, CA, US

Postby gerds » Tue Aug 15, 2006 6:39 am

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
gerds
Goblin
 
Posts: 260
Kudos: 1
Joined: 01 Sep 2003
Location: London, United Kingdom

Postby Frenetic » Tue Aug 15, 2006 7:26 am

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
Frenetic
Bugbear
 
Posts: 806
Kudos: 0
Joined: 03 Feb 2006

Postby gerds » Tue Aug 15, 2006 7:50 am

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
gerds
Goblin
 
Posts: 260
Kudos: 1
Joined: 01 Sep 2003
Location: London, United Kingdom

Postby Frenetic » Tue Aug 15, 2006 8:01 am

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
Frenetic
Bugbear
 
Posts: 806
Kudos: 0
Joined: 03 Feb 2006

Postby gerds » Tue Aug 15, 2006 8:52 am

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
gerds
Goblin
 
Posts: 260
Kudos: 1
Joined: 01 Sep 2003
Location: London, United Kingdom

Postby xavier » Tue Aug 15, 2006 9:30 am

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
Kudos: 23
Joined: 18 Feb 2005
Location: Dublin, CA, US

Postby xavier » Tue Aug 15, 2006 9:32 am

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
xavier
OGRE Retired Moderator
OGRE Retired Moderator
 
Posts: 9481
Kudos: 23
Joined: 18 Feb 2005
Location: Dublin, CA, US

Postby gerds » Wed Aug 16, 2006 4:47 am

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.

For this message the author gerds has received kudos
User avatar
gerds
Goblin
 
Posts: 260
Kudos: 1
Joined: 01 Sep 2003
Location: London, United Kingdom

Postby xavier » Wed Aug 16, 2006 6:56 am

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?

For this message the author xavier has received kudos
User avatar
xavier
OGRE Retired Moderator
OGRE Retired Moderator
 
Posts: 9481
Kudos: 23
Joined: 18 Feb 2005
Location: Dublin, CA, US

Postby gerds » Wed Aug 16, 2006 7:50 am

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
gerds
Goblin
 
Posts: 260
Kudos: 1
Joined: 01 Sep 2003
Location: London, United Kingdom

Postby Frenetic » Thu Aug 17, 2006 4:24 am

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
Frenetic
Bugbear
 
Posts: 806
Kudos: 0
Joined: 03 Feb 2006

Postby xavier » Thu Aug 17, 2006 5:30 am

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
xavier
OGRE Retired Moderator
OGRE Retired Moderator
 
Posts: 9481
Kudos: 23
Joined: 18 Feb 2005
Location: Dublin, CA, US

Postby Frenetic » Thu Aug 17, 2006 5:49 am

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
Frenetic
Bugbear
 
Posts: 806
Kudos: 0
Joined: 03 Feb 2006

Postby xavier » Thu Aug 17, 2006 7:48 am

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
xavier
OGRE Retired Moderator
OGRE Retired Moderator
 
Posts: 9481
Kudos: 23
Joined: 18 Feb 2005
Location: Dublin, CA, US

Postby Frenetic » Fri Aug 18, 2006 8:31 am

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
Frenetic
Bugbear
 
Posts: 806
Kudos: 0
Joined: 03 Feb 2006

Postby gerds » Wed Sep 27, 2006 6:17 am

** 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.
User avatar
gerds
Goblin
 
Posts: 260
Kudos: 1
Joined: 01 Sep 2003
Location: London, United Kingdom

Postby Nudel » Wed Sep 27, 2006 7:50 am

Is OgreNewt cabable of raycasting on polygon level?
Nudel
Halfling
 
Posts: 79
Kudos: 0
Joined: 23 Mar 2006
Location: Vienna

Postby PatrickB3 » Wed Sep 27, 2006 8:50 pm

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.
PatrickB3
Greenskin
 
Posts: 101
Kudos: 0
Joined: 09 May 2005
Location: California, USA

Postby hmoraldo » Wed Dec 06, 2006 8:59 pm

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
Kudos: 1
Joined: 07 Mar 2006
Location: Buenos Aires, Argentina

Postby hmoraldo » Thu Dec 07, 2006 5:34 pm

Well, I posted it in the wiki here: http://www.ogre3d.org/wiki/index.php/Raycasting_to_the_polygon_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
hmoraldo
OGRE Expert User
OGRE Expert User
 
Posts: 517
Kudos: 1
Joined: 07 Mar 2006
Location: Buenos Aires, Argentina

Postby gerds » Thu Dec 07, 2006 11:33 pm

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
User avatar
gerds
Goblin
 
Posts: 260
Kudos: 1
Joined: 01 Sep 2003
Location: London, United Kingdom

Postby Jerome » Sat Jan 06, 2007 12:18 pm

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
Jerome
Gnoblar
 
Posts: 3
Kudos: 0
Joined: 12 Dec 2006

Postby funguine » Wed May 16, 2007 5:58 pm

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/Raycasting_to_the_polygon_level_%28Mogre%29
Last edited by funguine on Wed May 16, 2007 7:10 pm, edited 1 time in total.
funguine
Gnoblar
 
Posts: 10
Kudos: 1
Joined: 15 Jan 2007
Location: Oulu, Finland

Next

Return to Help

Who is online

Users browsing this forum: Google [Bot] and 25 guests