Sign in to follow this  
DrZoidberg42

trying to understand "chipmunk"

Recommended Posts

DrZoidberg42    121
I was looking at the source for the chipmunk 2d physics engine.
It's a relatively small, simple engine so I thought I might be able to understand it.
But I already stumbled upon some strange math being used in there that doesn't make sense to me.

In cpPolyShape.h, there is a struct defined like this

[code]

typedef struct cpPolyShapeAxis{
// normal
cpVect n;
// distance from origin
cpFloat d;
} cpPolyShapeAxis;
[/code]


And then in cpPolyShape.c, line 181 it says
[code]
for(int i=0; i<numVerts; i++){
cpVect a = cpvadd(offset, verts[i]);
cpVect b = cpvadd(offset, verts[(i+1)%numVerts]);
cpVect n = cpvnormalize(cpvperp(cpvsub(b, a)));

poly->verts[i] = a;
poly->axes[i].n = n;
poly->axes[i].d = cpvdot(n, a);

}[/code]


cpvadd - adds 2 vectors
cpvnormalize - normalizes a vector
cpvperp - rotates a vector 90 degrees
cpvdot - dot product

I wonder what is meant by "distance from origin"
According to that code the distance from the origin is equal to the dot product of the normalized form of one of the edges of the polygon rotated by 90 degrees and one of the vertices of that edge.
Or in other words the "distance from origin" is equal to the distance of the vertice from (0,0) times the cosine of the angle between that vertice and the normal on the edge.
How does that make sense?

Share this post


Link to post
Share on other sites
Zahlman    1682
The vector is being "projected" onto the edge axis. It's the component of distance-from-the-origin which is in the same direction.

Share this post


Link to post
Share on other sites
DrZoidberg42    121
ok, thanks.
I guess the math for this is more complex then I thought.
I see that those axes are used for collision detection.
The vertices of one polygon are being projected onto the axes of the other.
But is this really necessary? Isn't it easier to just use the sum of the angles to determine whether a point is inside a polygon?
I mean given a point A and a polygon B you take a list with all the vertices of B and then you create a second list that - for each vertex of B - contains the vector from A to the vertex.
Then you go through that second list and add up all the angles between the vectors. If it adds up to 360 the point is inside. If the point is outside, it adds up to 0.

Share this post


Link to post
Share on other sites
Zahlman    1682
[quote name='DrZoidberg42' timestamp='1307842270' post='4822244']
But is this really necessary? Isn't it easier to just use the sum of the angles to determine whether a point is inside a polygon?[/quote]

Calculating these projections is about as easy, faster for the computer, and I believe more accurate (less susceptible to round-off errors - though I can't really cite a source for that) than determining the angles (which requires trig functions) and adding them up.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this