# Commits

committed f7a1c4a

comments on collision test and reaction are done.
obsolete functions such as Partly_LB are deleted.

• Participants
• Parent commits bd7a8e4
• Branches physics

# File include/pgCollision.h

` #include "pgphysics.h"`
` `
` /**`
`- * TODO`
`+ * pgCollision.h mainly contains structures and functions related with`
`+   collision reaction functions. The main algorithm is a complex empirical `
`+   formula. You can find it in Helmut Garstenauer's thesis, Page 60. It also `
`+   employ split impulse to correct the position after collision reaction. You can`
`+   learn this method thoroughly from Erin Canto's www.gphysics.com. I'm sorry i don't`
`+   explain them in detail here, since it's a complicated mission for me while all the`
`+   two references illustrate them perfectly:)`
`+`
`+   Note the only relation between collision test and collision reaction is PyContact.`
`+   So you can change two parts almost independently.`
`+`
`+   TODO: fraction simulation is in construction. I'll commit the code as soon as it is stable.`
`+ */`
`+`
`+/*`
`+ *`
`+	PyContact includes essential data for collision reaction computation.`
`+	@param body1 (inheriting from PyJointObject) the reference body`
`+	@param body2 (inheriting from PyJointObject) the incident body`
`+	@param pos the contact point's position`
`+	@param dv the relative velocity between reference body and incident body(in reference body's local coordinate)`
`+	@param depth the penetrating depth`
`+	@param weight to average impulses caused by each contact point`
`+	@param kFactor precomputed factor for impulse-based collision reaction calculation.`
`+	@param tFactor similar with kFactor but is not used at the moment`
`+	@param ppAccMoment the accumulated moment(impulse)`
`+	@param ppSplitAccMoment the accumulated split moment(impulse)`
`  */`
` typedef struct`
` {`
`-    //assert body2 is the incident rigid body`
`-    //and body1 is the reference rigid body`
`     PyJointObject joint;`
` `
`     PyVector2 pos;`
` } PyContact;`
` `
` /**`
`- * TODO`
`- */`
`-typedef enum`
`-{`
`-    MOVING_AWAY,`
`-    RESTING,`
`-    MOVING_TOWARD`
`-} CollisionType;`
`-`
`-/**`
`- * TODO`
`- */`
`-typedef enum`
`-{`
`-    CA_X = 0,`
`-    CA_Y = 1`
`-} CollisionAxis;`
`-`
`-/**`
`- * TODO`
`+ * represent the collision face which collision happens on`
`  */`
` typedef enum`
` {`
` } CollisionFace;`
` `
` /**`
`- * TODO`
`+ * Collision_LiangBarskey is an Liang-Barskey 2d line clipping method`
`  *`
`- * @param`
`- * @param`
`- * @param`
`- * @param`
`- * @param`
`- * @return`
`+ * Directed line segment(p1, p2) will be clipped against the AABB box`
`+ * and result in (ans_p1, ans_p2).`
`+ *`
`+ * @param box AABB box used for 2D line clipping`
`+ * @param p1 Start point of the directed line segment to be clipped`
`+ * @param p2 End point of the directed line segment to be clipped`
`+ * @param ans_p1 Start point of clipped line`
`+ * @param ans_p2 End point of clipped line`
`+ * @return If there is no overlap, return 0. Otherwise return 1`
`  */`
` int Collision_LiangBarskey(AABBBox* box, PyVector2* p1, PyVector2* p2, `
`     PyVector2* ans_p1, PyVector2* ans_p2);`
` `
` /**`
`- * TODO`
`+ * Collision_ApplyContact does collision reaction calculation based on`
`+ * information in contactObject`
`  *`
`- * @param`
`- * @param`
`- * @param`
`- * @param`
`- * @param`
`- * @param`
`- * @param`
`- * @param`
`- * @return`
`- */`
`-int Collision_PartlyLB(AABBBox* box, PyVector2* p1, PyVector2* p2, `
`-    CollisionAxis axis, PyVector2* ans_p1, PyVector2* ans_p2,`
`-    int* valid_p1, int* valid_p2);`
`-`
`-/**`
`- * TODO`
`- *`
`- * @param`
`- * @param`
`- * @return`
`- */`
`-PyJointObject* Collision_ContactNew(PyBodyObject* refBody,`
`-    PyBodyObject* incidBody);`
`-`
`-/**`
`- * TODO`
`- *`
`- * @param`
`- * @param`
`+ * @contactObject a contact contains collision information`
`+ * @param step time step`
`  */`
` void Collision_ApplyContact(PyObject* contactObject, double step);`
` `
` /**`
`- * TODO`
`- *`
`- * @param refBody`
`- * @param incidBody`
`- */`
`+* PyContact_New creates a new contact connected with refBody and incidBody`
`+*`
`+* @param refBody the reference body`
`+* @param incidBody the incident body`
`+* @return a new PyContact`
`+*/`
` PyObject* PyContact_New(PyBodyObject* refBody, PyBodyObject* incidBody);`
` `
` #endif /* _PHYSICS_COLLISION_H_ */`

# File include/pgShapeObject.h

` #include "pgphysics.h"`
` `
` /**`
`- * TODO`
`- *`
`- * @param shape`
`- * @param refbody`
`+ * PyShapeObject_UpdateAABB updates the AABB box after refbody's moving`
`+ * @param refbody we'll update refbody's AABB box`
`  */`
` int PyShapeObject_UpdateAABB (PyBodyObject *refbody);`
` `
` /**`
`- * TODO`
`+ * PyShapeObject_Collision does collision test between refbody and incbody`
`  *`
`- * @param shape`
`  * @param refbody`
`  * @param incbody`
`- * @param conactlist`
`+ * @param conactlist we'll put the possible collision information to contactList`
`  */`
` int PyShapeObject_Collision (PyBodyObject *refbody, PyBodyObject *incbody,`
`     PyObject *contactlist);`

# File src/pgCollision.c

` //        e1`
` `
` `
`-//TODO: add rest contact`
`-`
`-`
` /**`
`- * Apply Liang-Barskey clip on a AABB box`
`- * (p1, p2) is the input line segment to be clipped (note: it's a 2d vector)`
`- * (ans_p1, ans_p2) is the output line segment`
`- * TEST: Liang-Barskey clip has been tested.`
`+ * _LiangBarskey_Internal is an internal function used for Liang-Barskey clipping function`
`+ * `
`  *`
`- * @param p`
`- * @param q`
`- * @param u1`
`- * @param u2`
`- * @return`
`+ * @param p Start point of the directed line segment to be clipped `
`+ * @param q End point of the directed line segment to be clipped`
`+ * @param u1 Start parameter of clipped line`
`+ * @param u2 End parameter of clipped line`
`+ * @return If there is no overlap, return 0. Otherwise return 1`
`+ * note: ans_p1 = p1 + u1*(p2-p1);`
`+ *       ans_p2 = p2 + u2*(p2-2p);`
`+ * that's why we need u1 and u2.`
`  */`
` static int _LiangBarskey_Internal(double p, double q, double* u1, double* u2)`
` {`
` }`
` `
` /**`
`- * TODO`
`+ * update the two bodies' velocity connected by PyContact`
`  *`
`- * @param joint`
`- * @param step`
`+ * @param joint It's a PyContact`
`+ * @param step Time step`
`  */`
` static void _UpdateV(PyJointObject* joint, double step)`
` {`
` }`
` `
` /**`
`- * TODO`
`- *`
`- * @param joint`
`- * @param step`
`+ * This function is isolated and only hold the place`
`  */`
` static void _UpdateP(PyJointObject* joint, double step)`
` {`
`-    //isolated function`
` }`
` `
` int Collision_LiangBarskey(AABBBox* box, PyVector2* p1, PyVector2* p2, `
`     return 1;`
` }`
` `
`-int Collision_PartlyLB(AABBBox* box, PyVector2* p1, PyVector2* p2, `
`-    CollisionAxis axis, PyVector2* ans_p1, PyVector2* ans_p2, `
`-    int* valid_p1, int* valid_p2)`
`-{`
`-    PyVector2 dp;`
`-    double u1, u2;`
`-	`
`-    u1 = 0.f;`
`-    u2 = 1.f;`
`-    dp = c_diff(*p2, *p1);`
`-`
`-    switch(axis)`
`-    {`
`-    case CA_X:`
`-        if(!_LiangBarskey_Internal(-dp.imag, p1->imag - box->bottom, &u1, &u2)) return 0;`
`-        if(!_LiangBarskey_Internal(dp.imag, box->top - p1->imag, &u1, &u2)) return 0;`
`-        break;`
`-    case CA_Y:`
`-        if(!_LiangBarskey_Internal(-dp.real, p1->real - box->left, &u1, &u2)) return 0;`
`-        if(!_LiangBarskey_Internal(dp.real, box->right - p1->real, &u1, &u2)) return 0;`
`-        break;`
`-    default:`
`-        assert(0);`
`-        break;`
`-    }`
`-`
`-    if(u1 > u2) return 0;`
`-`
`-    if(u1 == 0.f)`
`-        *ans_p1 = *p1;`
`-    else`
`-        *ans_p1 = c_sum(*p1, PyVector2_MultiplyWithReal(dp, u1)); //ans_p1 = p1 + u1*dp`
`-    if(u2 == 1.f)`
`-        *ans_p2 = *p2;`
`-    else`
`-        *ans_p2 = c_sum(*p1, PyVector2_MultiplyWithReal(dp, u2)); //ans_p2 = p2 + u2*dp;`
`-`
`-    switch(axis)`
`-    {`
`-    case CA_X:`
`-        *valid_p1 = PyMath_LessEqual(box->left, ans_p1->real) && `
`-            PyMath_LessEqual(ans_p1->real, box->right);`
`-        *valid_p2 = PyMath_LessEqual(box->left, ans_p2->real) && `
`-            PyMath_LessEqual(ans_p2->real, box->right);`
`-        break;`
`-    case CA_Y:`
`-        *valid_p1 = PyMath_LessEqual(box->bottom, ans_p1->imag) && `
`-            PyMath_LessEqual(ans_p1->imag, box->top);`
`-        *valid_p2 = PyMath_LessEqual(box->bottom, ans_p2->imag) && `
`-            PyMath_LessEqual(ans_p2->imag, box->top);`
`-        break;`
`-    default:`
`-        assert(0);`
`-        break;`
`-    }`
`-`
`-    return *valid_p1 || *valid_p2;`
`-}`
`-`
` void Collision_ApplyContact(PyObject* contactObject, double step)`
` {`
` /**`
`- * TODO`
`+ * MAX_C_DEP is the maximal permitted penetrating depth after collision reaction.`
`+ * BIAS_FACTOR is a empirical factor. The two constants are used for position collision`
`+ * after collision reaction is done.`
`+ * for further learning you can read Erin Canto's GDC 2006 Slides, page 23.`
`+ * (You can download it from www.gphysics.com)`
`  */`
` #define MAX_C_DEP 0.01`
`-`
`-/**`
`- * TODO`
`- */`
` #define BIAS_FACTOR 0.2`
` `
`     PyVector2 neg_dV, refV, incidV;`
`     contact->resist = sqrt(refBody->fRestitution*incidBody->fRestitution);`
` `
`     /*`
`-     * TODO: explain the magic happening here.`
`+     * The algorithm below is an implementation of the empirical formula for`
`+	 * impulse-based collision reaction. You can learn the formula thoroughly`
`+	 * from Helmut Garstenauer's thesis, Page 60.`
`      */`
`-`
`     refR = c_diff(contact->pos, refBody->vecPosition);`
`     incidR = c_diff(contact->pos, incidBody->vecPosition);`
`     //dV = v2 + w2xr2 - (v1 + w1xr1)`
`     //finally we get the momentum(oh...)`
`     moment = PyVector2_MultiplyWithReal(contact->normal, moment_len);`
`     p = *(contact->ppAccMoment);`
`-    //TODO: test weight`
`     p->real += moment.real/contact->weight;`
`     p->imag += moment.imag/contact->weight; `
` `
`     //split impulse`
`     vbias = BIAS_FACTOR*MAX(0, contact->depth - MAX_C_DEP)/step;`
`-    //biasdv`
`+    //biased dv`
`     bincidV = c_sum(incidBody->cBiasLV, PyVector2_fCross(incidBody->cBiasW, incidR));`
`     brefV = c_sum(refBody->cBiasLV, PyVector2_fCross(refBody->cBiasW, refR));`
`     bneg_dV = c_diff(brefV, bincidV); `
`-    //bias_moment`
`+    //biased moment`
`     bm_len = PyVector2_Dot(PyVector2_MultiplyWithReal(bneg_dV, 1.),`
`         contact->normal)/contact->kFactor;`
`     bm_len = MAX(0, bm_len + vbias/contact->kFactor);`
` static PyJointObject* _ContactNew(PyBodyObject* refBody,PyBodyObject* incidBody)`
` {`
`     PyContact* contact;`
`-    //TODO: this function would be replaced.`
`+`
`     contact = (PyContact*)_ContactNewInternal(&PyContact_Type, NULL, NULL);`
`     contact->joint.body1 = (PyObject*)refBody;`
`     contact->joint.body2 = (PyObject*)incidBody;`

# File src/pgShapeObject.c

` static PyObject *PyShape_New (void);`
` static PyObject *PyRectShape_New (double width, double height, double seta);`
` `
`-/* collision test for RectShape */`
`+`
`+/*`
`+	Below are collision test functions for rectangle shape. `
`+	Here we employ an algorithm similar to Box2D Lite and Chipmunk. The`
`+	key difference is we only make use of a single clipping method to find`
`+	collision face and points, thus it's more robust. It includes such steps:`
`+	`
`+	(1) Given two bodies who have already passed AABB box testing, we employ`
`+	a 2D line clipping method(e.g. Liang-Barskey line clipping) to find the `
`+	overlapped convex polygon. If there's no such polygon the two bodies don't`
`+	collide at all. Otherwise we come to step (2).`
`+	`
`+	(2) Use a heuristic method to figure out the collision face(the face on which `
`+	collision happens): `
`+	Calculate every average distance of all the vertices of the polygon to 8 candidate `
`+	faces(two bodies, who each has 4 faces), and select the face with minimal distance `
`+	to be the collision face, who's normal imply the direction of reacting impulse.`
`+	We say the body which collision face is on is a reference body, and the other one`
`+	is an incident body.`
`+	The key idea is we consider the collision face should has minimal penetrating depth.`
`+`
`+	(3) Reject vertices which is just on the collision face to speed up reaction calculation. `
`+	Return the rest of them and the normal of collision face. That's all.`
`+`
`+`
`+	Some other issues:`
`+	1) For more information of this algorithm you should read the Erin Catto's slides `
`+	on www.gphysics.com, and Helmut Garstenauer's thesis, "A Unified Framework for Rigid `
`+	Body Dynamics" (URL is too long but you can easily google it out :). `
`+`
`+	2) The algorithm isn't a Continuous Collision Detection(CCD) method. So it would `
`+	break down if we can't grasp the early stage of collision. that means you should`
`+	choose proper initial velocities, sizes of bodies and time step. `
`+	The total collision test method would be replaced by a CCD one in the future.`
`+`
`+*/`
` `
` /**`
`- * TODO`
`- */`
`+* MAX_CONTACTS imply the max possible collision points of the two rectangle bodies.`
`+* 16 is plentiful.`
`+*/`
` #define MAX_CONTACTS 16`
` `
`+`
` /**`
`- * TODO`
`+ * _Candiate is a internal structure for saving informations of collision test.`
`+ @param normal collision normal`
`+ @param contacts collision points`
`+ @param kFactors precomputed factors for later computation`
`+ @param contact_size size of contacts and kFactors`
`+ @param min_depth the minimal penetrating depth`
`  */`
` typedef struct _Candidate_`
` {`
`     double min_depth;`
` }_Candidate;`
` `
`-`
` /**`
`- * TODO`
`+ * _ClipTest is an internal function for Rectangle Collsion Test`
`  *`
`- * @param box`
`- * @param points`
`- * @param candi`
`- * @return`
`+ * @param box the AABB box used for 2D line clipping`
`+ * @param points the candidate 4 point, then we can make 4 directed line segment:`
`+		  (0, 1) (1, 2) (2, 3) (3, 1)`
`+ * @param candi clip the 4 directed line segment against the AABB box and save resulting`
`+          vertices of clipped line segment to candi`
`+ * @return If there is no line overlapped with the AABB box, return 0.`
`+           Otherwise return 1`
`  */`
` static int _ClipTest(AABBBox* box, PyVector2* points, _Candidate* candi)`
` {`
` }`
` `
` /**`
`- * TODO`
`+ * _SATFindCollisionProperty is an internal function for Rectangle Collsion Test`
`  * `
`- * @param selfBody`
`- * @param incBody`
`- * @param selfBox`
`- * @param incBox`
`- * @param candi`
`- * @param ans_ref`
`- * @param ans_inc`
`+ * @param selfBody the reference body which the normal face is on.`
`+          note it isn't the real reference body. we just suppose it to be.`
`+		  ans_ref and ans_inc will be the real reference & incident body.`
`+ * @param incBody the reference body`
`+ * @param selfBox selfBody's AABB box(in selfBody's local coordinate)`
`+ * @param incBox incident body's AABB box`
`+ * @param candi resulting collision points (so called contacts) and collision`
`+          normal and some other value would be saved in candi`
`+ * @param ans_ref the real reference body`
`+ * @param ans_inc the real incident body`
`  */`
` static void _SATFindCollisionProperty(PyBodyObject* selfBody,`
`     PyBodyObject* incBody, AABBBox* selfBox, AABBBox* incBox, _Candidate *candi,`
`     double tmp1, tmp2;`
`     `
`     /*`
`-     * TODO: describe the magic here.`
`+     * Here conts[0][i] represent the contacts calculated in selfBody's local coordinate.`
`+	   conts[1][i] represent the contacts translated to incBody's local coordinate.`
`+	   then we can rightly get the two minimal depth.`
`+`
`+	   The key is whether we appoint which one to be the reference body, the resuting contacts`
`+	   are equivalent only except for different coordinate. but while calculating the penetrating `
`+	   depth to all the candidate collision face, we must make sure all the contacts are in the`
`+	   same local coordinate at one time.`
`      */`
`     for(i = 0; i < candi->contact_size; ++i)`
`     {`
`     self[0] = inc[1] = selfBody;`
`     inc[0] = self[1] = incBody;`
`     `
`+	/*`
`+	 * Now we appoint selfBody to be the reference body and incBody`
`+	   to be the incident body for computing min_dep[0]. And vice versa for min_dep[1].`
`+	   `
`+	   Since each computation happens in reference body's local coordinate,`
`+	   it's very simple to get the minimal penetrating depth.`
`+	 */`
`     for(k = 0; k <= 1; ++k)`
`     {`
`         memset(deps, 0, sizeof(deps));`
`     }`
` `
`     /*`
`-     * TODO describe the magic here`
`+     * If min_dep[0] < min_dep[1], we choose selfBody to be the right reference body`
`+	   and incBody to be the incident one. And vice versa. `
`      */`
`-    `
`-    //now select min depth one`
`     k = min_dep[0] < min_dep[1] ? 0 : 1;`
`     `
`     candi->min_depth = min_dep[k];`
`     size = candi->contact_size;`
`     candi->contact_size = 0;`
`-    switch(face_id[k])`
`+    `
`+	/* `
`+	 * Gete collision normal according to the collision face`
`+	   and delete the contacts on the collision face.`
`+	 */`
`+	switch(face_id[k])`
`     {`
`     case CF_LEFT:`
`         PyVector2_Set(candi->normal, -1, 0);`
`     }`
`     `
`     /*`
`-     * TODO: describe the magic here.`
`+     * We are nearly reaching the destination except for three things:`
`+`
`+	   First, collsion normal and contact are in reference body's local coordinate.`
`+	   We must translate them to the global coordinate for easy usage.`
`+`
`+	   Second, In the impulse-based collsion reaction formula, we find there is a small`
`+	   part can be precomputed to speed up the total computation. that's so called kFactor.`
`+	   For more information of that you can read Helmut Garstenauer's thesis.`
`+`
`+	   Third, we must assign the right referent body and incident body to ans_ref and ans_inc.`
`      */`
` `
`-    //translate to global coordinate`
`     PyVector2_Rotate(&(candi->normal), self[k]->fRotation);`
`     for(i = 0; i < candi->contact_size; ++i)`
`     {`
`         PyVector2_Rotate(&(candi->contacts[i]), self[k]->fRotation);`
`         candi->contacts[i] = c_sum(candi->contacts[i], self[k]->vecPosition);`
`-        //precompute kFactor`
`+		`
`+		/*precompute KFactor*/`
`         refR = c_diff(candi->contacts[i], self[k]->vecPosition);`
`         incidR = c_diff(candi->contacts[i], inc[k]->vecPosition);`
`         tmp1 = PyVector2_Dot(PyVector2_fCross(PyVector2_Cross(refR, candi->normal), refR), candi->normal)`
` }`
` `
` /**`
`- * TODO`
`+ * _RectShapeCollision is the user interface for rectangle body's collsion test`
`  *`
`- * @param selfBody`
`- * @param incidBody`
`- * @param contactList`
`+ * @param selfBody One of the two possible colliding bodies, who's shape must be a rectangle `
`+ * @param incidBody The other one of the two, who's shape also must be a rectangle`
`+ * @param contactList Resulting contacts and collision normal would be append to contactList`
`+          for the coming soon collision reaction calculation.`
`+   @return If the two bodies are really colliding, return 1. Otherwise return 0`
`  */`
` static int _RectShapeCollision(PyBodyObject* selfBody, PyBodyObject* incidBody, `
`     PyObject* contactList)`
` `
`     return 1;`
` }`
`+`
` #undef MAX_CONTACTS`
` `
`+`
`+`
` /**`
`  Methods used by the Shape.`
`  */`