Ray casting?

[Night Elf]

Hi, does Chipmunk support ray casting? I've only found old posts about it where it was said the feature was planned but not implemented yet. Is it now? I need to implement a basic line of sight test to know if some body is visible form certain point in the world.

[slembcke]

No. :-\ Still on my todo list unfortunately. It would certainly be a nice feature to have, but I haven't had a strong enough need for it in any of my own projects, and haven't had the time to implement it otherwise.

[Night Elf]

Thanks for your answer. I was afraid that was the case...

However, I was reading this post: http://www.slembcke.net/forums/viewtopi ... tile#p1813 and I think what you propose there would be a good enough solution for what I need right now. I'm looking at the source code you posted, but I'm having a hard time figuring it out. In particular: how do you manage to guarantee the bullet will hit the first obstacle? I don't see where this ordering takes place...

[slembcke]

The length of the bullet segment is longer than the distance the bullet will move in the next timestep. It works well for bullets because the collision shape is still pretty small and you can use it to simulate their trajectory.

If you wanted to fake ray casting, it might be worthwhile to look at how cpSpace.c does the actually collision tests. It would probably be easiest to create a body and shape on the stack and then check them against the static and active spatial hashes in the space. This saves you from having to muck around with adding and removing the shape for just one step in order to get chipmunk to call the collision callbacks.

[Night Elf]

Oh, I understand: so the bullet works because it moves, it doesn't instantly hit the target.

I'm trying to understand how collisions work inside cpSpace, but with all the function pointers, hashes and sets it's really hard... Could you help me a bit with this? For instance, I can't see where you test two shapes for collision and how that triggers the collision callback. Perhaps if you could point me to where I should look...

[slembcke]

Sure, I have some time at the moment. Because of the callback heavy style I use, you have to go a few levels deep to see how it really works. At the top level of cpSpaceStep() you should see the following two lines that find all the collisions:

Code: Select all

        cpSpaceHashEach(space->activeShapes, &active2staticIter, space);
        cpSpaceHashQueryRehash(space->activeShapes, &queryFunc, space);

The cpSpaceHashEach() call iterates all of the active shapes and collides them against the shapes in the static spatial hash, ignore the second line for now. The function active2staticIter() is called and is passed each shape in the activeShapes spatial hash.

Code: Select all

static void
active2staticIter(void *ptr, void *data)
{
        cpShape *shape = (cpShape *)ptr;
        cpSpace *space = (cpSpace *)data;
        cpSpaceHashQuery(space->staticShapes, shape, shape->bb, &queryFunc, space);
}

Because the spatial hash code is meant to be type agnostic, it passes void * pointers to the callback. ptr is the shape, and data is the pointer to the space that we passed to cpSpaceHashEach(). After that, all we need to do is query the spatial hash. The parameters cpSpaceHashQuery() takes are a spatial hash, a pointer to the object we are querying for, the bounding box we want to query, the callback function to call with the potential collision pairs, and finally another data pointer that the query function will pass on to our callback.

At this point, we have set up callbacks that iterate all the active objects and we query their bounding boxes against the static hash. Again, because the spatial hash code was meant to be generic and used outside of just Chipmunk's collision detection, the shape pairs that are passed to the collision callback are potential collisions. The spatial hash is good at figuring which objects are far away from each other, but it does nothing beyond guessing. It doesn't even check that bounding boxes are overlapping as it doesn't cache them. The queryFunc() function is what checks that collisions have actually occured.

Here is a stripped down version of the queryFunc() function:

Code: Select all

static void
queryFunc(void *p1, void *p2, void *data)
{
        // Cast the generic pointers from the spatial hash back to usefull types
        cpShape *a = (cpShape *)p1;
        cpShape *b = (cpShape *)p2;
        cpSpace *space = (cpSpace *)data;
        
        // Reject any of the simple cases
        if(queryReject(a,b)) return; // Look below, just a bunch of boolean checks
        
        // Shape 'a' should have the lower shape type. (required by cpCollideShapes() )
        if(a->klass->type > b->klass->type){
                cpShape *temp = a;
                a = b;
                b = temp;
        }
        
        // Narrow-phase collision detection.
        cpContact *contacts = NULL;
        int numContacts = cpCollideShapes(a, b, &contacts);
        if(!numContacts) return; // Shapes are not colliding.
        
        // ... do something with the collision information here

        free(contacts);
}

static inline int
queryReject(cpShape *a, cpShape *b)
{
        return
                // BBoxes must overlap
                !cpBBintersects(a->bb, b->bb)
                // Don't collide shapes attached to the same body.
                || a->body == b->body
                // Don't collide objects in the same non-zero group
                || (a->group && b->group && a->group == b->group)
                // Don't collide objects that don't share at least on layer.
                || !(a->layers & b->layers);
}

Again there is some casting of the void pointers back to the Chipmunk types first. The next thing to do is to check some of the trivial rejection conditions. You can see these in the queryReject() function listed at the end. Now you are getting into the real gritty bits of Chipmunk's collision detection. Chipmunk has a set number of collision detection functions. There is a circle to segment collision function, but not a segment to circle collision detection function. Because the direction of the normals generated by these functions is very important, you have to sort the shapes so that it matches the order accepted by the collision detection functions. Gross, but there you go. Now you can call cpCollideShapes() to get detailed collision information. You pass a pointer to a pointer of cpContacts that the collision detection will set if the objects actually are colliding. It is your responsibility to free this list.

So there you go, that how collision detection in Chipmunk works. The spatial hash filters out most of the potential collision pairs so you aren't checking collisions between every possible pair of objects. With the pairs that it does give you, you do some fast checks to see if the shapes have overlapping bounding boxes, are in the same layers, etc. Lastly you perform the expensive specific collision detection that gives you the final yes or no answer and other information on how the objects are colliding.

You could probably simplify this a bit more if you have more controlled inputs, but that should hopefully be a good explanation of how it all works.

[Night Elf]

Thank you very much for your detailed response! I really appreciate your taking the time to write it.

So, if I wanted to do as you suggested and implement a pseudo-raycast using shape collision, I would do something like this:

Code: Select all

cpBody* rayBody = cpBodyNew(0, 0);

cpVect rayVerts[] = {rayStart, rayEnd};
cpShape* rayShape = cpShapeNew(rayBody, 2, rayVerts, cpvzero);

cpSpaceHashQuery(space->staticShapes, rayShape, rayShape->bb, &queryFunc, space);
cpSpaceHashQuery(space->activeShapes, rayShape, rayShape->bb, &queryFunc, space);

cpShapeDestroy(rayShape);
cpBodyDestroy(rayBody);

Then I should have a callback in place to detect the collisions... Is that about right? Or should I replace queryFunc with my own (just copy all the contents of queryFunc and add the "ray casting" bits in the part where it accepts a collision)?

[slembcke]

You will have to write your own version of queryFunc(). Otherwise it will create collision pairs that it will add to the space to solve the next time the solver runs. Definitely not what you want.

The version I pasted in the post above was stripped down to exclude those parts. Just use that as a template.