Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/trunk/src/external/bullet/BulletCollision/CollisionDispatch/btBox2dBox2dCollisionAlgorithm.cpp @ 12383

Last change on this file since 12383 was 8351, checked in by rgrieder, 14 years ago

Merged kicklib2 branch back to trunk (includes former branches ois_update, mac_osx and kicklib).

Notes for updating

Linux:
You don't need an extra package for CEGUILua and Tolua, it's already shipped with CEGUI.
However you do need to make sure that the OgreRenderer is installed too with CEGUI 0.7 (may be a separate package).
Also, Orxonox now recognises if you install the CgProgramManager (a separate package available on newer Ubuntu on Debian systems).

Windows:
Download the new dependency packages versioned 6.0 and use these. If you have problems with that or if you don't like the in game console problem mentioned below, you can download the new 4.3 version of the packages (only available for Visual Studio 2005/2008).

Key new features:

  • *Support for Mac OS X*
  • Visual Studio 2010 support
  • Bullet library update to 2.77
  • OIS library update to 1.3
  • Support for CEGUI 0.7 —> Support for Arch Linux and even SuSE
  • Improved install target
  • Compiles now with GCC 4.6
  • Ogre Cg Shader plugin activated for Linux if available
  • And of course lots of bug fixes

There are also some regressions:

  • No support for CEGUI 0.5, Ogre 1.4 and boost 1.35 - 1.39 any more
  • In game console is not working in main menu for CEGUI 0.7
  • Tolua (just the C lib, not the application) and CEGUILua libraries are no longer in our repository. —> You will need to get these as well when compiling Orxonox
  • And of course lots of new bugs we don't yet know about
  • Property svn:eol-style set to native
File size: 11.9 KB
RevLine 
[7983]1/*
2Bullet Continuous Collision Detection and Physics Library
3* The b2CollidePolygons routines are Copyright (c) 2006-2007 Erin Catto http://www.gphysics.com
4
5This software is provided 'as-is', without any express or implied warranty.
6In no event will the authors be held liable for any damages arising from the use of this software.
7Permission is granted to anyone to use this software for any purpose,
8including commercial applications, and to alter it and redistribute it freely,
9subject to the following restrictions:
10
111. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
122. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
133. This notice may not be removed or altered from any source distribution.
14*/
15
16///btBox2dBox2dCollisionAlgorithm, with modified b2CollidePolygons routines from the Box2D library.
17///The modifications include: switching from b2Vec to btVector3, redefinition of b2Dot, b2Cross
18
19#include "btBox2dBox2dCollisionAlgorithm.h"
20#include "BulletCollision/CollisionDispatch/btCollisionDispatcher.h"
21#include "BulletCollision/CollisionShapes/btBoxShape.h"
22#include "BulletCollision/CollisionDispatch/btCollisionObject.h"
23#include "BulletCollision/CollisionDispatch/btBoxBoxDetector.h"
24#include "BulletCollision/CollisionShapes/btBox2dShape.h"
25
26#define USE_PERSISTENT_CONTACTS 1
27
28btBox2dBox2dCollisionAlgorithm::btBox2dBox2dCollisionAlgorithm(btPersistentManifold* mf,const btCollisionAlgorithmConstructionInfo& ci,btCollisionObject* obj0,btCollisionObject* obj1)
29: btActivatingCollisionAlgorithm(ci,obj0,obj1),
30m_ownManifold(false),
31m_manifoldPtr(mf)
32{
33        if (!m_manifoldPtr && m_dispatcher->needsCollision(obj0,obj1))
34        {
35                m_manifoldPtr = m_dispatcher->getNewManifold(obj0,obj1);
36                m_ownManifold = true;
37        }
38}
39
40btBox2dBox2dCollisionAlgorithm::~btBox2dBox2dCollisionAlgorithm()
41{
42       
43        if (m_ownManifold)
44        {
45                if (m_manifoldPtr)
46                        m_dispatcher->releaseManifold(m_manifoldPtr);
47        }
48       
49}
50
51
52void b2CollidePolygons(btManifoldResult* manifold,  const btBox2dShape* polyA, const btTransform& xfA, const btBox2dShape* polyB, const btTransform& xfB);
53
54//#include <stdio.h>
55void btBox2dBox2dCollisionAlgorithm::processCollision (btCollisionObject* body0,btCollisionObject* body1,const btDispatcherInfo& dispatchInfo,btManifoldResult* resultOut)
56{
57        if (!m_manifoldPtr)
58                return;
59
60        btCollisionObject*      col0 = body0;
61        btCollisionObject*      col1 = body1;
62        btBox2dShape* box0 = (btBox2dShape*)col0->getCollisionShape();
63        btBox2dShape* box1 = (btBox2dShape*)col1->getCollisionShape();
64
65        resultOut->setPersistentManifold(m_manifoldPtr);
66
67        b2CollidePolygons(resultOut,box0,col0->getWorldTransform(),box1,col1->getWorldTransform());
68
69        //  refreshContactPoints is only necessary when using persistent contact points. otherwise all points are newly added
70        if (m_ownManifold)
71        {
72                resultOut->refreshContactPoints();
73        }
74
75}
76
77btScalar btBox2dBox2dCollisionAlgorithm::calculateTimeOfImpact(btCollisionObject* /*body0*/,btCollisionObject* /*body1*/,const btDispatcherInfo& /*dispatchInfo*/,btManifoldResult* /*resultOut*/)
78{
79        //not yet
80        return 1.f;
81}
82
83
84struct ClipVertex
85{
86        btVector3 v;
87        int id;
88        //b2ContactID id;
89        //b2ContactID id;
90};
91
92#define b2Dot(a,b) (a).dot(b)
93#define b2Mul(a,b) (a)*(b)
94#define b2MulT(a,b) (a).transpose()*(b)
95#define b2Cross(a,b) (a).cross(b)
96#define btCrossS(a,s) btVector3(s * a.getY(), -s * a.getX(),0.f)
97
98int b2_maxManifoldPoints =2;
99
100static int ClipSegmentToLine(ClipVertex vOut[2], ClipVertex vIn[2],
101                                          const btVector3& normal, btScalar offset)
102{
103        // Start with no output points
104        int numOut = 0;
105
106        // Calculate the distance of end points to the line
107        btScalar distance0 = b2Dot(normal, vIn[0].v) - offset;
108        btScalar distance1 = b2Dot(normal, vIn[1].v) - offset;
109
110        // If the points are behind the plane
111        if (distance0 <= 0.0f) vOut[numOut++] = vIn[0];
112        if (distance1 <= 0.0f) vOut[numOut++] = vIn[1];
113
114        // If the points are on different sides of the plane
115        if (distance0 * distance1 < 0.0f)
116        {
117                // Find intersection point of edge and plane
118                btScalar interp = distance0 / (distance0 - distance1);
119                vOut[numOut].v = vIn[0].v + interp * (vIn[1].v - vIn[0].v);
120                if (distance0 > 0.0f)
121                {
122                        vOut[numOut].id = vIn[0].id;
123                }
124                else
125                {
126                        vOut[numOut].id = vIn[1].id;
127                }
128                ++numOut;
129        }
130
131        return numOut;
132}
133
134// Find the separation between poly1 and poly2 for a give edge normal on poly1.
135static btScalar EdgeSeparation(const btBox2dShape* poly1, const btTransform& xf1, int edge1,
136                                                          const btBox2dShape* poly2, const btTransform& xf2)
137{
138        const btVector3* vertices1 = poly1->getVertices();
139        const btVector3* normals1 = poly1->getNormals();
140
141        int count2 = poly2->getVertexCount();
142        const btVector3* vertices2 = poly2->getVertices();
143
144        btAssert(0 <= edge1 && edge1 < poly1->getVertexCount());
145
146        // Convert normal from poly1's frame into poly2's frame.
147        btVector3 normal1World = b2Mul(xf1.getBasis(), normals1[edge1]);
148        btVector3 normal1 = b2MulT(xf2.getBasis(), normal1World);
149
150        // Find support vertex on poly2 for -normal.
151        int index = 0;
152        btScalar minDot = BT_LARGE_FLOAT;
153
154        for (int i = 0; i < count2; ++i)
155        {
156                btScalar dot = b2Dot(vertices2[i], normal1);
157                if (dot < minDot)
158                {
159                        minDot = dot;
160                        index = i;
161                }
162        }
163
164        btVector3 v1 = b2Mul(xf1, vertices1[edge1]);
165        btVector3 v2 = b2Mul(xf2, vertices2[index]);
166        btScalar separation = b2Dot(v2 - v1, normal1World);
167        return separation;
168}
169
170// Find the max separation between poly1 and poly2 using edge normals from poly1.
171static btScalar FindMaxSeparation(int* edgeIndex,
172                                                                 const btBox2dShape* poly1, const btTransform& xf1,
173                                                                 const btBox2dShape* poly2, const btTransform& xf2)
174{
175        int count1 = poly1->getVertexCount();
176        const btVector3* normals1 = poly1->getNormals();
177
178        // Vector pointing from the centroid of poly1 to the centroid of poly2.
179        btVector3 d = b2Mul(xf2, poly2->getCentroid()) - b2Mul(xf1, poly1->getCentroid());
180        btVector3 dLocal1 = b2MulT(xf1.getBasis(), d);
181
182        // Find edge normal on poly1 that has the largest projection onto d.
183        int edge = 0;
184        btScalar maxDot = -BT_LARGE_FLOAT;
185        for (int i = 0; i < count1; ++i)
186        {
187                btScalar dot = b2Dot(normals1[i], dLocal1);
188                if (dot > maxDot)
189                {
190                        maxDot = dot;
191                        edge = i;
192                }
193        }
194
195        // Get the separation for the edge normal.
196        btScalar s = EdgeSeparation(poly1, xf1, edge, poly2, xf2);
197        if (s > 0.0f)
198        {
199                return s;
200        }
201
202        // Check the separation for the previous edge normal.
203        int prevEdge = edge - 1 >= 0 ? edge - 1 : count1 - 1;
204        btScalar sPrev = EdgeSeparation(poly1, xf1, prevEdge, poly2, xf2);
205        if (sPrev > 0.0f)
206        {
207                return sPrev;
208        }
209
210        // Check the separation for the next edge normal.
211        int nextEdge = edge + 1 < count1 ? edge + 1 : 0;
212        btScalar sNext = EdgeSeparation(poly1, xf1, nextEdge, poly2, xf2);
213        if (sNext > 0.0f)
214        {
215                return sNext;
216        }
217
218        // Find the best edge and the search direction.
219        int bestEdge;
220        btScalar bestSeparation;
221        int increment;
222        if (sPrev > s && sPrev > sNext)
223        {
224                increment = -1;
225                bestEdge = prevEdge;
226                bestSeparation = sPrev;
227        }
228        else if (sNext > s)
229        {
230                increment = 1;
231                bestEdge = nextEdge;
232                bestSeparation = sNext;
233        }
234        else
235        {
236                *edgeIndex = edge;
237                return s;
238        }
239
240        // Perform a local search for the best edge normal.
241        for ( ; ; )
242        {
243                if (increment == -1)
244                        edge = bestEdge - 1 >= 0 ? bestEdge - 1 : count1 - 1;
245                else
246                        edge = bestEdge + 1 < count1 ? bestEdge + 1 : 0;
247
248                s = EdgeSeparation(poly1, xf1, edge, poly2, xf2);
249                if (s > 0.0f)
250                {
251                        return s;
252                }
253
254                if (s > bestSeparation)
255                {
256                        bestEdge = edge;
257                        bestSeparation = s;
258                }
259                else
260                {
261                        break;
262                }
263        }
264
265        *edgeIndex = bestEdge;
266        return bestSeparation;
267}
268
269static void FindIncidentEdge(ClipVertex c[2],
270                                                         const btBox2dShape* poly1, const btTransform& xf1, int edge1,
271                                                         const btBox2dShape* poly2, const btTransform& xf2)
272{
273        const btVector3* normals1 = poly1->getNormals();
274
275        int count2 = poly2->getVertexCount();
276        const btVector3* vertices2 = poly2->getVertices();
277        const btVector3* normals2 = poly2->getNormals();
278
279        btAssert(0 <= edge1 && edge1 < poly1->getVertexCount());
280
281        // Get the normal of the reference edge in poly2's frame.
282        btVector3 normal1 = b2MulT(xf2.getBasis(), b2Mul(xf1.getBasis(), normals1[edge1]));
283
284        // Find the incident edge on poly2.
285        int index = 0;
286        btScalar minDot = BT_LARGE_FLOAT;
287        for (int i = 0; i < count2; ++i)
288        {
289                btScalar dot = b2Dot(normal1, normals2[i]);
290                if (dot < minDot)
291                {
292                        minDot = dot;
293                        index = i;
294                }
295        }
296
297        // Build the clip vertices for the incident edge.
298        int i1 = index;
299        int i2 = i1 + 1 < count2 ? i1 + 1 : 0;
300
301        c[0].v = b2Mul(xf2, vertices2[i1]);
302//      c[0].id.features.referenceEdge = (unsigned char)edge1;
303//      c[0].id.features.incidentEdge = (unsigned char)i1;
304//      c[0].id.features.incidentVertex = 0;
305
306        c[1].v = b2Mul(xf2, vertices2[i2]);
307//      c[1].id.features.referenceEdge = (unsigned char)edge1;
308//      c[1].id.features.incidentEdge = (unsigned char)i2;
309//      c[1].id.features.incidentVertex = 1;
310}
311
312// Find edge normal of max separation on A - return if separating axis is found
313// Find edge normal of max separation on B - return if separation axis is found
314// Choose reference edge as min(minA, minB)
315// Find incident edge
316// Clip
317
318// The normal points from 1 to 2
319void b2CollidePolygons(btManifoldResult* manifold,
320                                          const btBox2dShape* polyA, const btTransform& xfA,
321                                          const btBox2dShape* polyB, const btTransform& xfB)
322{
323
324        int edgeA = 0;
325        btScalar separationA = FindMaxSeparation(&edgeA, polyA, xfA, polyB, xfB);
326        if (separationA > 0.0f)
327                return;
328
329        int edgeB = 0;
330        btScalar separationB = FindMaxSeparation(&edgeB, polyB, xfB, polyA, xfA);
331        if (separationB > 0.0f)
332                return;
333
334        const btBox2dShape* poly1;      // reference poly
335        const btBox2dShape* poly2;      // incident poly
336        btTransform xf1, xf2;
337        int edge1;              // reference edge
338        unsigned char flip;
339        const btScalar k_relativeTol = 0.98f;
340        const btScalar k_absoluteTol = 0.001f;
341
342        // TODO_ERIN use "radius" of poly for absolute tolerance.
343        if (separationB > k_relativeTol * separationA + k_absoluteTol)
344        {
345                poly1 = polyB;
346                poly2 = polyA;
347                xf1 = xfB;
348                xf2 = xfA;
349                edge1 = edgeB;
350                flip = 1;
351        }
352        else
353        {
354                poly1 = polyA;
355                poly2 = polyB;
356                xf1 = xfA;
357                xf2 = xfB;
358                edge1 = edgeA;
359                flip = 0;
360        }
361
362        ClipVertex incidentEdge[2];
363        FindIncidentEdge(incidentEdge, poly1, xf1, edge1, poly2, xf2);
364
365        int count1 = poly1->getVertexCount();
366        const btVector3* vertices1 = poly1->getVertices();
367
368        btVector3 v11 = vertices1[edge1];
369        btVector3 v12 = edge1 + 1 < count1 ? vertices1[edge1+1] : vertices1[0];
370
371        btVector3 dv = v12 - v11;
372        btVector3 sideNormal = b2Mul(xf1.getBasis(), v12 - v11);
373        sideNormal.normalize();
374        btVector3 frontNormal = btCrossS(sideNormal, 1.0f);
375       
376       
377        v11 = b2Mul(xf1, v11);
378        v12 = b2Mul(xf1, v12);
379
380        btScalar frontOffset = b2Dot(frontNormal, v11);
381        btScalar sideOffset1 = -b2Dot(sideNormal, v11);
382        btScalar sideOffset2 = b2Dot(sideNormal, v12);
383
384        // Clip incident edge against extruded edge1 side edges.
385        ClipVertex clipPoints1[2];
386        clipPoints1[0].v.setValue(0,0,0);
387        clipPoints1[1].v.setValue(0,0,0);
388
389        ClipVertex clipPoints2[2];
390        clipPoints2[0].v.setValue(0,0,0);
391        clipPoints2[1].v.setValue(0,0,0);
392
393
394        int np;
395
396        // Clip to box side 1
397        np = ClipSegmentToLine(clipPoints1, incidentEdge, -sideNormal, sideOffset1);
398
399        if (np < 2)
400                return;
401
402        // Clip to negative box side 1
403        np = ClipSegmentToLine(clipPoints2, clipPoints1,  sideNormal, sideOffset2);
404
405        if (np < 2)
406        {
407                return;
408        }
409
410        // Now clipPoints2 contains the clipped points.
411        btVector3 manifoldNormal = flip ? -frontNormal : frontNormal;
412
413        int pointCount = 0;
414        for (int i = 0; i < b2_maxManifoldPoints; ++i)
415        {
416                btScalar separation = b2Dot(frontNormal, clipPoints2[i].v) - frontOffset;
417
418                if (separation <= 0.0f)
419                {
420                       
421                        //b2ManifoldPoint* cp = manifold->points + pointCount;
422                        //btScalar separation = separation;
423                        //cp->localPoint1 = b2MulT(xfA, clipPoints2[i].v);
424                        //cp->localPoint2 = b2MulT(xfB, clipPoints2[i].v);
425
426                        manifold->addContactPoint(-manifoldNormal,clipPoints2[i].v,separation);
427
428//                      cp->id = clipPoints2[i].id;
429//                      cp->id.features.flip = flip;
430                        ++pointCount;
431                }
432        }
433
434//      manifold->pointCount = pointCount;}
435}
Note: See TracBrowser for help on using the repository browser.