Public Group

# collision detection and double dispatch

This topic is 3175 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

What is the best way to calculate collision detection between different shapes? I am using the SAT. The main problem I have is that the code used depends on the types of both shapes. The main types of shapes I have are null shapes, axis aligned rectangles, circles, and arbitrary convex polygons.

##### Share on other sites
I think you can make a pure virtual base class, something like 'CollidableBaseClass', like so:

class Collidable{public:    Collidable() {};    virtual ~Collidable() {};    virtual bool Collide(Sphere *pObject) = 0;    virtual bool Collide(Square *pObject) = 0;    //etc (spheres, AABBs, OBBs, whatever)};

And then implement this base class in your actual collision detection classes, and let the virtual functions take care of the rest

class Sphere : public Collidable{    Sphere()    ~Sphere()    bool Collide(Sphere *pObject) //sphere - sphere    bool Collide(Square *pObject) //sphere - square};class Square : public Collidable{    Square();    ~Square();    bool Collide(Sphere *pObject) // square - sphere    bool Collide(Square *pObject) // square - square};

I haven't got much experience with writing collision detection code, but this is how I would handle it...

##### Share on other sites
Like this?

public interface BoundingVolume {	boolean intersects(BoundingVolume bv);	boolean intersectsSphere(BoundingSphere bv);	boolean intersectsRay(Ray ray);}public class BoundingSphere implements BoundingVolume {...	@Override	public boolean intersects(BoundingVolume bv) {		return bv.intersectsSphere(this);	}	/**	 * fast sphere-sphere intersection test	 */	@Override	public boolean intersectsSphere(BoundingSphere bv) {		Vector3f dist = Position.subtract(position, bv.getPosition(), null);		float rrSq = (radius + bv.getRadius()) * (radius + bv.getRadius());		if (dist.lengthSquared() <= rrSq ) 			return true; 		return false;	}...}

I've seen this approach used in a number of engines. You need to implement methods for all your specific bounding volumes but the amount of types is typically small (aabb, obb, sphere, mesh).

##### Share on other sites
Hi Storyyeller,

I guess there is no real "best way" to perform this. It also depends on whether you are in 2D or 3D. In 2D SAT should be all right, however in 3D GJK is probably better but much more difficult. However when using mixed geometries (as in your case) you will always end up writing specific routines to better use the information you have (as e.g. circle-circle collision).

A good description for specific cases of the SAT can be found here: http://www.metanetsoftware.com/technique.html.

Additionally detecting the collisions is one thing, but keeping them seperate is a complete different one!

Cheers,
fng

##### Share on other sites
Personally have never liked that whole 'intersectsSphere' 'intersectsLine' 'intersects*****' chain of methods specifically because it requires a change of interface to add new geometry. Generally, the fewer code files that need to be edited to add a new thing, the better. For this reason, I went with a callback registration system w/ a collision manager. A system with which I would register a function that resolves collisions between two types of bounding volumes. It would then map a <TypeA,TypeB> pair where TypeA is the bounding volume type of a, and same for b, to a function that recieved a and b as arguments, and returned collision details. A simple 2D array indexed by bounding volume type is sufficient.

Regions that did not contain a registered handler would perform in a predictable way [in my case, I threw an exception].

Thus there were no member functions for intersect this and intersect that types, and thus no need to change interfaces of existing bounding volumes when I added a new type. It also seemed simpler, to me at least.

##### Share on other sites
Yes, I am using 2d

I guess I have no choice but a gigantic list of switch statements. At least there are really only 17 cases to check.

I am planning on eventually having 5 types of shapes, but the Null shape always returns false in collision detection no matter what, so there are 1 + 4*4 cases to check.

##### Share on other sites
Hi Storyyeller,

Actually if have some sort of "hierarchy" you only need 10 tests. For each shape you assign a hierarchy index for which two different kinds of shapes must have different values (e.g. Null = 0, Sphere = 1, Rectangles = 2, Circles = 3, Polygons = 4) you always pick the one with the lower index as reference and check the shape with the higher index against it. By doing so, you are using the fact, that a Rectangle vs. Sphere collsion is the symmetric case of Sphere vs. Rectangle.

This leaves you the following 10 checks to implement:
Sphere - Sphere
Sphere - Rectangle
Sphere - Circle
Sphere - Polygon

Rectangle - Rectangle
Rectangle - Circle
Rectangle - Polygon

Circle - Circle
Circle - Polygon

Polygon - Polygon
(I somehow fell I wouldn't call that list gigantic ;D)

NB: A sphere in 2D is a circle, so you would only end up with 6 tests.
NB2: If you either constrain yourself to rectangles or express rectangles through polygons (as rectangles are convex) you only need 3 tests. You could start with this and refine the library later (if really needed).

By the way, in which language are you implementing this? I have been working on a small 2d collision library lately, maybe we could combine efforts? So far Sphere-Sphere and Sphere-Polygon is working. Haven't yet started the Polygon-Polygon case. Send me an email if you are interested.

Cheers,
fng

##### Share on other sites
Quote:
 Original post by fngBy the way, in which language are you implementing this? I have been working on a small 2d collision library lately, maybe we could combine efforts? So far Sphere-Sphere and Sphere-Polygon is working. Haven't yet started the Polygon-Polygon case. Send me an email if you are interested.Cheers,fng

Here's what I came up with. It's not pretty or well designed, but at least it works. Or appears to work at any rate. Feel free to use if it you actually want it.

collisionprofile.h
#pragma once#include "vec2d.h"#include "collisiondetection.h"#include "BOOST/shared_ptr.hpp"#include <vector>class PointList;typedef boost::shared_ptr<PointList> pointlist_sptr;typedef boost::shared_ptr<const PointList> pointlist_sptr_const;class PointInterface{    public:    virtual double GetX() const=0;    virtual double GetY() const=0;};class CollisionProfile{    enum ProfileType {EMPTY, RECT, CIRC, POLY};    ProfileType type;    double centerx,centery;    double halfh,halfw;    double radius; //Used for circles    pointlist_sptr_const mypoly; //Used for polygons    const PointInterface* parent;    static Uint32 Type2Int(ProfileType arg);    double wCenterX() const;    double wCenterY() const;    double ProjectMin(const Vec2d& V) const; //Returns the minimum value when the shape is projected onto V. Divide by ||V|| to get actual distance    double ProjectMax(const Vec2d& V) const;    friend bool CollidesProjected(const CollisionProfile& shape1, const CollisionProfile& shape2, const Vec2d& V);    friend bool CollidePolyRect(const CollisionProfile& shape1, const CollisionProfile& shape2);    friend bool CollidePolyCircle(const CollisionProfile& shape1, const CollisionProfile& shape2);    friend bool CollidePolyPoly(const CollisionProfile& shape1, const CollisionProfile& shape2);    public:    CollisionProfile(): type(EMPTY), parent(NULL) {}    CollisionProfile(const PointInterface* creator): type(EMPTY), parent(creator) {}    //~CollisionProfile();    //Creation of a rect directly    CollisionProfile(double x1, double y1, double x2, double y2)        : parent(NULL), type(RECT), centerx((x2+x1)/2), centery((y2+y1)/2), halfw((x2-x1)/2), halfh((y2-y1)/2)        {assert(halfw>=0);assert(halfh>=0);}    //Mutators    void setNull(){type=EMPTY;mypoly.reset();}    void setRect(double x1, double y1, double x2, double y2);    void setCircle(double x, double y, double r);    void setPoly(pointlist_sptr_const newpoly);    //Accessors    CollisionDetect::RectXYXY getRect() const;    CollisionDetect::CircXYR getCirc() const;    //const PointList& getPoly() const;    Uint32 getPolySize() const;    const Vec2d& getPolyVertex(Uint32 i) const;    Range ProjectRange(const Vec2d& V) const;    friend bool CollidesWith(const CollisionProfile& shape1, const CollisionProfile& shape2);};class PointList{    std::vector<Vec2d> mypoints;    double x1,y1,x2,y2;    public:    PointList();    bool Valid() const {return mypoints.size()>0;}    PointList* AddPoint(double px, double py);    CollisionDetect::RectXYXY getBoundRect(double wxoff, double wyoff) const;    Range getProjectedRange(const Vec2d& V, const Vec2d& wOffset) const;    const std::vector<Vec2d>& MyPoints() const {return mypoints;}};

collisionprofile.cpp
#include "collisionprofile.h"#include "utilityheaders\debug.h"#include "collisiondetection.h"//Comparison functions#include <algorithm>double Max(double v1, double v2, double v3, double v4) {return std::max(std::max(std::max(v1,v2),v3),v4);}double Min(double v1, double v2, double v3, double v4) {return std::min(std::min(std::min(v1,v2),v3),v4);}Uint32 CollisionProfile::Type2Int(ProfileType arg){    switch(arg)    {        case EMPTY:            return 0;        case RECT:            return 1;        case CIRC:            return 2;        case POLY:            return 3;        default:            return 0xFFFF;    }}double CollisionProfile::wCenterX() const{    if(parent)    {        return centerx+parent->GetX();    }    else    {        return centerx;    }}double CollisionProfile::wCenterY() const{    if(parent)    {        return centery+parent->GetY();    }    else    {        return centery;    }}double CollisionProfile::ProjectMin(const Vec2d& V) const{    assert(type != EMPTY);    switch(type)    {        case RECT:            return Min( V * getRect().TL(), V * getRect().TR(), V * getRect().BL(), V * getRect().BR());        case CIRC:            return V * getCirc().Center() - Norm(V) * radius; //V is not necessarily normalized, so we can't just subtract r        case POLY:        default:            assert(false); //We should never get this far            return 0;    }}double CollisionProfile::ProjectMax(const Vec2d& V) const{    assert(type != EMPTY);    switch(type)    {        case RECT:            return Max( V * getRect().TL(), V * getRect().TR(), V * getRect().BL(), V * getRect().BR());        case CIRC:            return V * getCirc().Center() + Norm(V) * radius; //V is not necessarily normalized, so we can't just subtract r        case POLY:        default:            assert(false); //We should never get this far            return 0;    }}Range CollisionProfile::ProjectRange(const Vec2d& V) const{    assert(type != EMPTY);    if (type == POLY)    {        assert(mypoly);        return mypoly->getProjectedRange(V, Vec2d(wCenterX(),wCenterY()));    }    else    {        return Range(ProjectMin(V),ProjectMax(V));    }}void CollisionProfile::setRect(double x1, double y1, double x2, double y2){    assert(x2>=x1);    assert(y2>=y1);    type = RECT;    centerx=(x2+x1)/2;    centery=(y2+y1)/2;    halfw=(x2-x1)/2;    halfh=(y2-y1)/2;    mypoly.reset();}void CollisionProfile::setCircle(double x, double y, double r){    assert(r>=0);    type = CIRC;    centerx=x;    centery=y;    halfw=r;    halfh=r;    radius=r;    mypoly.reset();}void CollisionProfile::setPoly(pointlist_sptr_const newpoly){    centerx=centery=0;    assert(newpoly);    type = POLY;    mypoly=newpoly;}CollisionDetect::RectXYXY CollisionProfile::getRect() const{    assert(type==RECT);    return CollisionDetect::RectXYXY( wCenterX() - halfw, wCenterY() - halfh, wCenterX() + halfw, wCenterY() + halfh);}CollisionDetect::CircXYR CollisionProfile::getCirc() const{    assert(type==CIRC);    return CollisionDetect::CircXYR( wCenterX(), wCenterY(), radius);}Uint32 CollisionProfile::getPolySize() const{    assert(type == POLY);    assert(mypoly);    return mypoly->MyPoints().size();}const Vec2d& CollisionProfile::getPolyVertex(Uint32 i) const{    assert(type == POLY);    assert(mypoly);    assert(i<getPolySize());    return mypoly->MyPoints().at(i);}//Private freind functionsbool CollidesProjected(const CollisionProfile& shape1, const CollisionProfile& shape2, const Vec2d& V){    if (shape1.type == CollisionProfile::EMPTY || shape2.type == CollisionProfile::EMPTY)    {        return false;    }    return StrictIntersect( shape1.ProjectRange(V), shape2.ProjectRange(V));}bool CollidePolyRect(const CollisionProfile& shape1, const CollisionProfile& shape2){    assert(shape1.type == CollisionProfile::POLY);    assert(shape2.type == CollisionProfile::RECT);    //Do bounding rect check first    if (!CollisionDetect::RectRect( shape1.mypoly->getBoundRect(shape1.wCenterX(), shape1.wCenterY()), shape2.getRect()))    {        return false;    }    Vec2d V(1,0);    if (!StrictIntersect(shape1.ProjectRange( V ), shape2.ProjectRange( V ))) {return false;}    V = Vec2d(0,1);    if (!StrictIntersect(shape1.ProjectRange( V ), shape2.ProjectRange( V ))) {return false;}    //Debug("Checking normals");    for(int i=0; i<shape1.getPolySize(); ++i)    {        V = Rot90(shape1.getPolyVertex( (i+1) % shape1.getPolySize()) - shape1.getPolyVertex(i));        //V = shape1.getPolyVertex(i + 1) - shape1.getPolyVertex(i);        //The modulus is because we wrap around to the first point at the end to get all the edges        //Debug(V.x,V.y);        if (!StrictIntersect(shape1.ProjectRange( V ), shape2.ProjectRange( V ))) {return false;}    }    //Debug("\t!!!");    return true;}bool CollidePolyCircle(const CollisionProfile& shape1, const CollisionProfile& shape2){    assert(shape1.type == CollisionProfile::POLY);    assert(shape2.type == CollisionProfile::CIRC);    //Do bounding rect check first    if (!CollisionDetect::RectCircle( shape1.mypoly->getBoundRect(shape1.wCenterX(), shape1.wCenterY()), shape2.getCirc()))    {        return false;    }    //Test the polygon normals    for(int i=0; i<shape1.getPolySize(); ++i)    {        Vec2d V = Rot90(shape1.getPolyVertex( (i+1) % shape1.getPolySize()) - shape1.getPolyVertex(i));        //The modulus is because we wrap around to the first point at the end to get all the edges        if (!StrictIntersect(shape1.ProjectRange( V ), shape2.ProjectRange( V ))) {return false;}    }    //Test the vectors from a vertex to the circle center    for(int i=0; i<shape1.getPolySize(); ++i)    {        Vec2d V = shape1.getPolyVertex(i) + Vec2d(shape1.wCenterX(), shape1.wCenterY()) //We didn't add the world offset before becasue it was a difference anyway, but since we're comparing points from two different shapes, it matters now            - Vec2d(shape2.wCenterX(), shape2.wCenterY());        if (!StrictIntersect(shape1.ProjectRange( V ), shape2.ProjectRange( V ))) {return false;}    }    return true;}bool CollidePolyPoly(const CollisionProfile& shape1, const CollisionProfile& shape2){    assert(shape1.type == CollisionProfile::POLY);    assert(shape2.type == CollisionProfile::POLY);    //Do bounding rect check first    if (!CollisionDetect::RectRect( shape1.mypoly->getBoundRect(shape1.wCenterX(), shape1.wCenterY()), shape2.getRect()))    {        return false;    }    //Check normals of polygon 1    for(int i=0; i<shape1.getPolySize(); ++i)    {        Vec2d V = Rot90(shape1.getPolyVertex( (i+1) % shape1.getPolySize()) - shape1.getPolyVertex(i));        //The modulus is because we wrap around to the first point at the end to get all the edges        if (!StrictIntersect(shape1.ProjectRange( V ), shape2.ProjectRange( V ))) {return false;}    }    //Check normals of polygon 2    for(int i=0; i<shape2.getPolySize(); ++i)    {        Vec2d V = Rot90(shape2.getPolyVertex( (i+1) % shape2.getPolySize()) - shape2.getPolyVertex(i));        //The modulus is because we wrap around to the first point at the end to get all the edges        if (!StrictIntersect(shape1.ProjectRange( V ), shape2.ProjectRange( V ))) {return false;}    }    return true;}//Public freind functionsbool CollidesWith(const CollisionProfile& shape1, const CollisionProfile& shape2){    if (shape1.type == CollisionProfile::EMPTY || shape2.type == CollisionProfile::EMPTY)    {        return false;    }    //Cuts down on number of cases by always putting more complex shape first    if ( CollisionProfile::Type2Int(shape1.type) <  CollisionProfile::Type2Int(shape2.type))    {        return CollidesWith(shape2,shape1);    }    switch( shape1.type )    {        case CollisionProfile::RECT:            switch( shape2.type)            {                case CollisionProfile::RECT:                    return CollisionDetect::RectRect( shape1.getRect(), shape2.getRect());                default:;            }            break;        case CollisionProfile::CIRC:            switch( shape2.type)            {                case CollisionProfile::RECT:                    return CollisionDetect::CircleRect( shape1.getCirc(), shape2.getRect());                case CollisionProfile::CIRC:                    return CollisionDetect::CircleCircle( shape1.getCirc(), shape2.getCirc());                default:;            }            break;        case CollisionProfile::POLY:            switch( shape2.type)            {                case CollisionProfile::RECT:                    return CollidePolyRect(shape1,shape2);                case CollisionProfile::CIRC:                    return CollidePolyCircle(shape1,shape2);                case CollisionProfile::POLY:                    return CollidePolyPoly(shape1,shape2);                default:;            }            break;    }    //We should never get down here    assert(false);    return false;}////////////////////////////////////////////////////////////////////////////PointList::PointList(): x1(0), y1(0), x2(0), y2(0) {}PointList* PointList::AddPoint(double px, double py){    if (mypoints.size() == 0)    {        //Initialize bound rect        x1=x2=px;        y1=y2=py;    }    else    {        //Possibly enlarge bound rect        if (px<x1) {x1=px;}        if (px>x2) {x2=px;}        if (py<y1) {y1=py;}        if (py>y2) {y2=py;}    }    //Check for duplicates    if (mypoints.size()>0 && px == mypoints.back().x && py == mypoints.back().y)    {    }    else    {        mypoints.push_back(Vec2d(px,py));    }    return this;}CollisionDetect::RectXYXY PointList::getBoundRect(double wxoff, double wyoff) const{    assert(Valid());    return CollisionDetect::RectXYXY( wxoff + x1, wyoff + y1, wxoff + x2, wyoff + y2);}Range PointList::getProjectedRange(const Vec2d& V, const Vec2d& wOffset) const{    assert(Valid());    double min = V * (mypoints.at(0) + wOffset);    double max = V * (mypoints.at(0) + wOffset);    for (Uint32 i=1;i<mypoints.size();++i)    {        if (V * (mypoints.at(i) + wOffset) < min)        {            min = V * (mypoints.at(i) + wOffset);        }        if (V * (mypoints.at(i) + wOffset) > max)        {            max = V * (mypoints.at(i) + wOffset);        }    }    return Range(min,max);}

collisiondetection.h
#pragma once#include <algorithm>#include "utilityheaders/debug.h"#include "vec2d.h"namespace CollisionDetect{    struct RectXYXY    {        double x1,y1,x2,y2;        RectXYXY(double left, double top, double right, double bot)            : x1(left), y1(top), x2(right), y2(bot) {}        Vec2d TL() const {return Vec2d(x1,y1);}        Vec2d TR() const {return Vec2d(x2,y1);}        Vec2d BL() const {return Vec2d(x1,y2);}        Vec2d BR() const {return Vec2d(x2,y2);}    };    struct CircXYR    {        double x,y,r;        CircXYR(double centerx, double centery, double radius )            : x(centerx), y(centery), r(radius) {}        Vec2d Center() const {return Vec2d(x,y);}    };    inline double SqrDist(double x1, double y1, double x2, double y2)    {        return (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);        //Can call SqrDist(x,0,0,0) to square a number    }    inline bool RectRect(double left1, double top1, double right1, double bot1, double left2, double top2, double right2, double bot2)    {        assert(right1>=left1);        assert(bot1>=top1);        assert(right2>=left2);        assert(bot2>=top2);        //Performs a simple collision check between two rectangles using the seperating axis theorem        if (left1>=right2) {return false;}        if (left2>=right1) {return false;}        if (top1>=bot2) {return false;}        if (top2>=bot1) {return false;}        return true;    }    inline bool RectCircle(double left, double top, double right, double bot, double circx, double circy, double radius)    {        assert(right>=left);        assert(bot>=top);        assert(radius>=0);        //Check if circle is too far away        if (circx<=left-radius) {return false;}        if (circx>=right+radius) {return false;}        if (circy<=top-radius) {return false;}        if (circy>=bot+radius) {return false;}        //Unless the circle is naer the corners, it's a hit        if (circx<=left && circy<=top)        {            if (SqrDist(circx,circy,left,top) > (radius * radius)) {return false;}        }        if (circx<=left && circy>=bot)        {            if (SqrDist(circx,circy,left,bot) > (radius * radius)) {return false;}        }        if (circx>=right && circy<=top)        {            if (SqrDist(circx,circy,right,top) > (radius * radius)) {return false;}        }        if (circx>=right && circy>=bot)        {            if (SqrDist(circx,circy,right,bot) > (radius * radius)) {return false;}        }        return true;    }    inline bool CircleRect(double circx, double circy, double radius, double left, double top, double right, double bot)    {        return RectCircle(left, top, right, bot, circx, circy, radius);    }    inline bool CircleCircle(double circx1, double circy1, double radius1, double circx2, double circy2, double radius2)    {        double rsq = (radius1 + radius2)*(radius1 + radius2);        return SqrDist(circx1,circy1,circx2,circy2) < rsq;    }    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////    inline bool RectRect(const RectXYXY& rect1, const RectXYXY& rect2)    {        return RectRect(rect1.x1, rect1.y1, rect1.x2, rect1.y2, rect2.x1, rect2.y1, rect2.x2, rect2.y2);    }    inline bool RectCircle(const RectXYXY& rect1, const CircXYR& circ2)    {        return RectCircle(rect1.x1, rect1.y1, rect1.x2, rect1.y2, circ2.x, circ2.y, circ2.r);    }    inline bool CircleRect(const CircXYR& circ1, const RectXYXY& rect2)    {        return CircleRect(circ1.x, circ1.y, circ1.r, rect2.x1, rect2.y1, rect2.x2, rect2.y2);    }    inline bool CircleCircle(const CircXYR& circ1, const CircXYR& circ2)    {        return CircleCircle(circ1.x, circ1.y, circ1.r, circ2.x, circ2.y, circ2.r);    }}

vec2d.h
#pragma once#include <cmath>#include "utilityheaders\debug.h"struct Vec2d{    double x,y;    Vec2d(double newx, double newy): x(newx), y(newy) {}};inline Vec2d operator+ (const Vec2d& lhs, const Vec2d& rhs){    Vec2d temp=lhs;    temp.x += rhs.x;    temp.y += rhs.y;    return temp;}inline Vec2d operator- (const Vec2d& lhs, const Vec2d& rhs){    Vec2d temp=lhs;    temp.x -= rhs.x;    temp.y -= rhs.y;    return temp;}inline double operator* (const Vec2d& lhs, const Vec2d& rhs){    return (lhs.x * rhs.x) + (lhs.y * rhs.y);}inline double Norm(const Vec2d& arg){    return sqrt( arg * arg );}inline Vec2d Rot90(const Vec2d& arg){    return Vec2d(-arg.y, arg.x);}struct Range{    double min,max;    Range(double newmin, double newmax): min(newmin), max(newmax) {assert(newmax>=newmin);}};inline bool StrictIntersect(const Range& range1, const Range& range2){    if (range2.min>=range1.max) {return false;} //LaxIntersect uses strict inequalities here and vice versa    if (range1.min>=range2.max) {return false;}    return true;}

1. 1
Rutin
24
2. 2
JoeJ
20
3. 3
4. 4
5. 5

• 9
• 46
• 41
• 23
• 13
• ### Forum Statistics

• Total Topics
631749
• Total Posts
3002046
×