Back to index

supertuxkart  0.5+dfsg1
Classes | Defines | Typedefs | Functions | Variables
btConvexHull.cpp File Reference
#include <string.h>
#include "btConvexHull.h"
#include "LinearMath/btAlignedObjectArray.h"
#include "LinearMath/btMinMax.h"
#include "LinearMath/btVector3.h"

Go to the source code of this file.

Classes

class  int3
class  VertFlag
class  EdgeFlag
class  PlaneFlag
class  Coplanar
class  Tri

Defines

#define COPLANAR   (0)
#define UNDER   (1)
#define OVER   (2)
#define SPLIT   (OVER|UNDER)
#define PAPERWIDTH   (btScalar(0.001))
#define EPSILON   btScalar(0.000001) /* close enough to consider two btScalaring point numbers to be 'the same'. */

Typedefs

typedef ConvexH::HalfEdge HalfEdge

Functions

template<class T >
void Swap (T &a, T &b)
btPlane PlaneFlip (const btPlane &plane)
int operator== (const btPlane &a, const btPlane &b)
int coplanar (const btPlane &a, const btPlane &b)
btVector3 PlaneLineIntersection (const btPlane &plane, const btVector3 &p0, const btVector3 &p1)
btVector3 PlaneProject (const btPlane &plane, const btVector3 &point)
btVector3 ThreePlaneIntersection (const btPlane &p0, const btPlane &p1, const btPlane &p2)
btScalar DistanceBetweenLines (const btVector3 &ustart, const btVector3 &udir, const btVector3 &vstart, const btVector3 &vdir, btVector3 *upoint=NULL, btVector3 *vpoint=NULL)
btVector3 TriNormal (const btVector3 &v0, const btVector3 &v1, const btVector3 &v2)
btVector3 NormalOf (const btVector3 *vert, const int n)
int PlaneTest (const btPlane &p, const btVector3 &v)
int SplitTest (ConvexH &convex, const btPlane &plane)
template<class T >
int maxdirfiltered (const T *p, int count, const T &dir, btAlignedObjectArray< int > &allow)
btVector3 orth (const btVector3 &v)
template<class T >
int maxdirsterid (const T *p, int count, const T &dir, btAlignedObjectArray< int > &allow)
int operator== (const int3 &a, const int3 &b)
int above (btVector3 *vertices, const int3 &t, const btVector3 &p, btScalar epsilon)
int hasedge (const int3 &t, int a, int b)
int hasvert (const int3 &t, int v)
int shareedge (const int3 &a, const int3 &b)
void ReleaseHull (PHullResult &result)
static void addPoint (unsigned int &vcount, btVector3 *p, btScalar x, btScalar y, btScalar z)
btScalar GetDist (btScalar px, btScalar py, btScalar pz, const btScalar *p2)

Variables

btScalar planetestepsilon = PAPERWIDTH

Class Documentation

class VertFlag

Definition at line 185 of file btConvexHull.cpp.

Class Members
unsigned char junk
unsigned char overmap
unsigned char planetest
unsigned char undermap
class EdgeFlag

Definition at line 193 of file btConvexHull.cpp.

Class Members
unsigned char fixes
short overmap
unsigned char planetest
short undermap
class PlaneFlag

Definition at line 201 of file btConvexHull.cpp.

Class Members
unsigned char overmap
unsigned char undermap
class Coplanar

Definition at line 207 of file btConvexHull.cpp.

Class Members
unsigned short ea
unsigned char v0
unsigned char v1

Define Documentation

#define COPLANAR   (0)

Definition at line 150 of file btConvexHull.cpp.

#define EPSILON   btScalar(0.000001) /* close enough to consider two btScalaring point numbers to be 'the same'. */
#define OVER   (2)

Definition at line 152 of file btConvexHull.cpp.

#define PAPERWIDTH   (btScalar(0.001))

Definition at line 154 of file btConvexHull.cpp.

#define SPLIT   (OVER|UNDER)

Definition at line 153 of file btConvexHull.cpp.

#define UNDER   (1)

Definition at line 151 of file btConvexHull.cpp.


Typedef Documentation

Definition at line 160 of file btConvexHull.cpp.


Function Documentation

int above ( btVector3 vertices,
const int3 t,
const btVector3 p,
btScalar  epsilon 
)

Definition at line 309 of file btConvexHull.cpp.

{
       btVector3 n=TriNormal(vertices[t[0]],vertices[t[1]],vertices[t[2]]);
       return (dot(n,p-vertices[t[0]]) > epsilon); // EPSILON???
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void addPoint ( unsigned int &  vcount,
btVector3 p,
btScalar  x,
btScalar  y,
btScalar  z 
) [static]

Definition at line 822 of file btConvexHull.cpp.

{
       // XXX, might be broken
       btVector3& dest = p[vcount];
       dest[0] = x;
       dest[1] = y;
       dest[2] = z;
       vcount++;
}

Here is the caller graph for this function:

int coplanar ( const btPlane a,
const btPlane b 
) [inline]

Definition at line 52 of file btConvexHull.cpp.

{ return (a==b || a==PlaneFlip(b)); }

Here is the call graph for this function:

btScalar DistanceBetweenLines ( const btVector3 ustart,
const btVector3 udir,
const btVector3 vstart,
const btVector3 vdir,
btVector3 upoint = NULL,
btVector3 vpoint = NULL 
)

Definition at line 119 of file btConvexHull.cpp.

{
       static btVector3 cp;
       cp = cross(udir,vdir).normalized();

       btScalar distu = -dot(cp,ustart);
       btScalar distv = -dot(cp,vstart);
       btScalar dist = (btScalar)fabs(distu-distv);
       if(upoint) 
              {
              btPlane plane;
              plane.normal = cross(vdir,cp).normalized();
              plane.dist = -dot(plane.normal,vstart);
              *upoint = PlaneLineIntersection(plane,ustart,ustart+udir);
       }
       if(vpoint) 
              {
              btPlane plane;
              plane.normal = cross(udir,cp).normalized();
              plane.dist = -dot(plane.normal,ustart);
              *vpoint = PlaneLineIntersection(plane,vstart,vstart+vdir);
       }
       return dist;
}

Here is the call graph for this function:

btScalar GetDist ( btScalar  px,
btScalar  py,
btScalar  pz,
const btScalar p2 
)

Definition at line 833 of file btConvexHull.cpp.

{

       btScalar dx = px - p2[0];
       btScalar dy = py - p2[1];
       btScalar dz = pz - p2[2];

       return dx*dx+dy*dy+dz*dz;
}

Here is the caller graph for this function:

int hasedge ( const int3 t,
int  a,
int  b 
)

Definition at line 314 of file btConvexHull.cpp.

{
       for(int i=0;i<3;i++)
       {
              int i1= (i+1)%3;
              if(t[i]==a && t[i1]==b) return 1;
       }
       return 0;
}

Here is the caller graph for this function:

int hasvert ( const int3 t,
int  v 
)

Definition at line 323 of file btConvexHull.cpp.

{
       return (t[0]==v || t[1]==v || t[2]==v) ;
}

Here is the caller graph for this function:

template<class T >
int maxdirfiltered ( const T *  p,
int  count,
const T &  dir,
btAlignedObjectArray< int > &  allow 
)

Definition at line 222 of file btConvexHull.cpp.

{
       btAssert(count);
       int m=-1;
       for(int i=0;i<count;i++) 
              if(allow[i])
              {
                     if(m==-1 || dot(p[i],dir)>dot(p[m],dir))
                            m=i;
              }
       btAssert(m!=-1);
       return m;
} 

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T >
int maxdirsterid ( const T *  p,
int  count,
const T &  dir,
btAlignedObjectArray< int > &  allow 
)

Definition at line 250 of file btConvexHull.cpp.

{
       int m=-1;
       while(m==-1)
       {
              m = maxdirfiltered(p,count,dir,allow);
              if(allow[m]==3) return m;
              T u = orth(dir);
              T v = cross(u,dir);
              int ma=-1;
              for(btScalar x = btScalar(0.0) ; x<= btScalar(360.0) ; x+= btScalar(45.0))
              {
                     btScalar s = sinf(SIMD_RADS_PER_DEG*(x));
                     btScalar c = cosf(SIMD_RADS_PER_DEG*(x));
                     int mb = maxdirfiltered(p,count,dir+(u*s+v*c)*btScalar(0.025),allow);
                     if(ma==m && mb==m)
                     {
                            allow[m]=3;
                            return m;
                     }
                     if(ma!=-1 && ma!=mb)  // Yuck - this is really ugly
                     {
                            int mc = ma;
                            for(btScalar xx = x-btScalar(40.0) ; xx <= x ; xx+= btScalar(5.0))
                            {
                                   btScalar s = sinf(SIMD_RADS_PER_DEG*(xx));
                                   btScalar c = cosf(SIMD_RADS_PER_DEG*(xx));
                                   int md = maxdirfiltered(p,count,dir+(u*s+v*c)*btScalar(0.025),allow);
                                   if(mc==m && md==m)
                                   {
                                          allow[m]=3;
                                          return m;
                                   }
                                   mc=md;
                            }
                     }
                     ma=mb;
              }
              allow[m]=0;
              m=-1;
       }
       btAssert(0);
       return m;
} 

Here is the call graph for this function:

Here is the caller graph for this function:

btVector3 NormalOf ( const btVector3 vert,
const int  n 
)
int operator== ( const btPlane a,
const btPlane b 
) [inline]

Definition at line 51 of file btConvexHull.cpp.

{ return (a.normal==b.normal && a.dist==b.dist); }
int operator== ( const int3 a,
const int3 b 
)

Definition at line 298 of file btConvexHull.cpp.

{
       for(int i=0;i<3;i++) 
       {
              if(a[i]!=b[i]) return 0;
       }
       return 1;
}
btVector3 orth ( const btVector3 v)

Definition at line 236 of file btConvexHull.cpp.

{
       btVector3 a=cross(v,btVector3(0,0,1));
       btVector3 b=cross(v,btVector3(0,1,0));
       if (a.length() > b.length())
       {
              return a.normalized();
       } else {
              return b.normalized();
       }
}

Here is the call graph for this function:

Here is the caller graph for this function:

btPlane PlaneFlip ( const btPlane plane) [inline]

Definition at line 50 of file btConvexHull.cpp.

{return btPlane(-plane.normal,-plane.dist);}

Here is the caller graph for this function:

btVector3 PlaneLineIntersection ( const btPlane plane,
const btVector3 p0,
const btVector3 p1 
)

Definition at line 93 of file btConvexHull.cpp.

{
       // returns the point where the line p0-p1 intersects the plane n&d
                            static btVector3 dif;
              dif = p1-p0;
                            btScalar dn= dot(plane.normal,dif);
                            btScalar t = -(plane.dist+dot(plane.normal,p0) )/dn;
                            return p0 + (dif*t);
}

Here is the call graph for this function:

Here is the caller graph for this function:

btVector3 PlaneProject ( const btPlane plane,
const btVector3 point 
)

Definition at line 103 of file btConvexHull.cpp.

{
       return point - plane.normal * (dot(point,plane.normal)+plane.dist);
}

Here is the call graph for this function:

int PlaneTest ( const btPlane p,
const btVector3 v 
)

Definition at line 171 of file btConvexHull.cpp.

                                                    {
       btScalar a  = dot(v,p.normal)+p.dist;
       int   flag = (a>planetestepsilon)?OVER:((a<-planetestepsilon)?UNDER:COPLANAR);
       return flag;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void ReleaseHull ( PHullResult result)

Definition at line 656 of file btConvexHull.cpp.

{
       if ( result.m_Indices.size() )
       {
              result.m_Indices.clear();
       }

       result.mVcount = 0;
       result.mIndexCount = 0;
       result.mVertices = 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int shareedge ( const int3 a,
const int3 b 
)

Definition at line 327 of file btConvexHull.cpp.

{
       int i;
       for(i=0;i<3;i++)
       {
              int i1= (i+1)%3;
              if(hasedge(a,b[i1],b[i])) return 1;
       }
       return 0;
}

Here is the call graph for this function:

int SplitTest ( ConvexH convex,
const btPlane plane 
)

Definition at line 177 of file btConvexHull.cpp.

                                                    {
       int flag=0;
       for(int i=0;i<convex.vertices.size();i++) {
              flag |= PlaneTest(plane,convex.vertices[i]);
       }
       return flag;
}

Here is the call graph for this function:

template<class T >
void Swap ( T &  a,
T &  b 
)

Definition at line 26 of file btConvexHull.cpp.

{
       T tmp = a;
       a=b;
       b=tmp;
}

Here is the caller graph for this function:

btVector3 ThreePlaneIntersection ( const btPlane p0,
const btPlane p1,
const btPlane p2 
)

Definition at line 60 of file btConvexHull.cpp.

{
       btVector3 N1 = p0.normal;
       btVector3 N2 = p1.normal;
       btVector3 N3 = p2.normal;

       btVector3 n2n3; n2n3 = N2.cross(N3);
       btVector3 n3n1; n3n1 = N3.cross(N1);
       btVector3 n1n2; n1n2 = N1.cross(N2);

       btScalar quotient = (N1.dot(n2n3));

       btAssert(btFabs(quotient) > btScalar(0.000001));
       
       quotient = btScalar(-1.) / quotient;
       n2n3 *= p0.dist;
       n3n1 *= p1.dist;
       n1n2 *= p2.dist;
       btVector3 potentialVertex = n2n3;
       potentialVertex += n3n1;
       potentialVertex += n1n2;
       potentialVertex *= quotient;

       btVector3 result(potentialVertex.getX(),potentialVertex.getY(),potentialVertex.getZ());
       return result;

}

Here is the call graph for this function:

btVector3 TriNormal ( const btVector3 v0,
const btVector3 v1,
const btVector3 v2 
)

Definition at line 108 of file btConvexHull.cpp.

{
       // return the normal of the triangle
       // inscribed by v0, v1, and v2
       btVector3 cp=cross(v1-v0,v2-v1);
       btScalar m=cp.length();
       if(m==0) return btVector3(1,0,0);
       return cp*(btScalar(1.0)/m);
}

Here is the call graph for this function:

Here is the caller graph for this function:


Variable Documentation

Definition at line 156 of file btConvexHull.cpp.