Back to index

supertuxkart  0.5+dfsg1
Classes | Public Member Functions | Static Public Member Functions | Public Attributes
gjkepa2_impl::GJK Struct Reference
Collaboration diagram for gjkepa2_impl::GJK:
Collaboration graph
[legend]

List of all members.

Classes

struct  eStatus
struct  sSimplex
struct  sSV

Public Member Functions

 GJK ()
void Initialize ()
eStatus::_ Evaluate (const tShape &shapearg, const btVector3 &guess)
bool EncloseOrigin ()
void getsupport (const btVector3 &d, sSV &sv) const
void removevertice (sSimplex &simplex)
void appendvertice (sSimplex &simplex, const btVector3 &v)

Static Public Member Functions

static btScalar det (const btVector3 &a, const btVector3 &b, const btVector3 &c)
static btScalar projectorigin (const btVector3 &a, const btVector3 &b, btScalar *w, U &m)
static btScalar projectorigin (const btVector3 &a, const btVector3 &b, const btVector3 &c, btScalar *w, U &m)
static btScalar projectorigin (const btVector3 &a, const btVector3 &b, const btVector3 &c, const btVector3 &d, btScalar *w, U &m)

Public Attributes

tShape m_shape
btVector3 m_ray
btScalar m_distance
sSimplex m_simplices [2]
sSV m_store [4]
sSVm_free [4]
U m_nfree
U m_current
sSimplexm_simplex
eStatus::_ m_status

Detailed Description

Definition at line 79 of file btGjkEpa2.cpp.


Class Documentation

struct gjkepa2_impl::GJK::sSimplex

Definition at line 86 of file btGjkEpa2.cpp.

Collaboration diagram for gjkepa2_impl::GJK::sSimplex:
Class Members
sSV * c
btScalar p
U rank
struct gjkepa2_impl::GJK::sSV

Definition at line 82 of file btGjkEpa2.cpp.

Collaboration diagram for gjkepa2_impl::GJK::sSV:
Class Members
btVector3 d
btVector3 w

Constructor & Destructor Documentation

gjkepa2_impl::GJK::GJK ( ) [inline]

Definition at line 108 of file btGjkEpa2.cpp.

       {
       Initialize();
       }

Here is the call graph for this function:


Member Function Documentation

void gjkepa2_impl::GJK::appendvertice ( sSimplex simplex,
const btVector3 v 
) [inline]

Definition at line 316 of file btGjkEpa2.cpp.

       {
       simplex.p[simplex.rank]=0;
       simplex.c[simplex.rank]=m_free[--m_nfree];
       getsupport(v,*simplex.c[simplex.rank++]);
       }

Here is the call graph for this function:

Here is the caller graph for this function:

static btScalar gjkepa2_impl::GJK::det ( const btVector3 a,
const btVector3 b,
const btVector3 c 
) [inline, static]

Definition at line 322 of file btGjkEpa2.cpp.

       {
       return(       a.y()*b.z()*c.x()+a.z()*b.x()*c.y()-
                     a.x()*b.z()*c.y()-a.y()*b.x()*c.z()+
                     a.x()*b.y()*c.z()-a.z()*b.y()*c.x());
       }

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 240 of file btGjkEpa2.cpp.

       {
       switch(m_simplex->rank)
              {
              case   1:
                     {
                     for(U i=0;i<3;++i)
                            {
                            btVector3            axis=btVector3(0,0,0);
                            axis[i]=1;
                            appendvertice(*m_simplex, axis);
                            if(EncloseOrigin())  return(true);
                            removevertice(*m_simplex);
                            appendvertice(*m_simplex,-axis);
                            if(EncloseOrigin())  return(true);
                            removevertice(*m_simplex);
                            }
                     }
              break;
              case   2:
                     {
                     const btVector3      d=m_simplex->c[1]->w-m_simplex->c[0]->w;
                     for(U i=0;i<3;++i)
                            {
                            btVector3            axis=btVector3(0,0,0);
                            axis[i]=1;
                            if(btFabs(dot(axis,d))>0)
                                   {
                                   const btVector3      p=cross(d,axis);
                                   appendvertice(*m_simplex, p);
                                   if(EncloseOrigin())  return(true);
                                   removevertice(*m_simplex);
                                   appendvertice(*m_simplex,-p);
                                   if(EncloseOrigin())  return(true);
                                   removevertice(*m_simplex);
                                   }
                            }
                     }
              break;
              case   3:
                     {
                     const btVector3      n=cross(m_simplex->c[1]->w-m_simplex->c[0]->w,
                                                               m_simplex->c[2]->w-m_simplex->c[0]->w);
                     const btScalar       l=n.length();
                     if(l>0)
                            {
                            appendvertice(*m_simplex,n);
                            if(EncloseOrigin())  return(true);
                            removevertice(*m_simplex);
                            appendvertice(*m_simplex,-n);
                            if(EncloseOrigin())  return(true);
                            removevertice(*m_simplex);
                            }
                     }
              break;
              case   4:
                     {
                     if(btFabs(det(       m_simplex->c[0]->w-m_simplex->c[3]->w,
                                                 m_simplex->c[1]->w-m_simplex->c[3]->w,
                                                 m_simplex->c[2]->w-m_simplex->c[3]->w))>0)
                            return(true);
                     }
              break;
              }
       return(false);
       }

Here is the call graph for this function:

Here is the caller graph for this function:

eStatus::_ gjkepa2_impl::GJK::Evaluate ( const tShape shapearg,
const btVector3 guess 
) [inline]

Definition at line 120 of file btGjkEpa2.cpp.

       {
       U                    iterations=0;
       btScalar      sqdist=0;
       btScalar      alpha=0;
       btVector3     lastw[4];
       U                    clastw=0;
       /* Initialize solver        */ 
       m_free[0]                   =      &m_store[0];
       m_free[1]                   =      &m_store[1];
       m_free[2]                   =      &m_store[2];
       m_free[3]                   =      &m_store[3];
       m_nfree                            =      4;
       m_current                   =      0;
       m_status                    =      eStatus::Valid;
       m_shape                            =      shapearg;
       m_distance                  =      0;
       /* Initialize simplex              */ 
       m_simplices[0].rank  =      0;
       m_ray                       =      guess;
       const btScalar       sqrl=  m_ray.length2();
       appendvertice(m_simplices[0],sqrl>0?-m_ray:btVector3(1,0,0));
       m_simplices[0].p[0]  =      1;
       m_ray                       =      m_simplices[0].c[0]->w;     
       sqdist                      =      sqrl;
       lastw[0]                    =
       lastw[1]                    =
       lastw[2]                    =
       lastw[3]                    =      m_ray;
       /* Loop                                          */ 
       do     {
              const U              next=1-m_current;
              sSimplex&     cs=m_simplices[m_current];
              sSimplex&     ns=m_simplices[next];
              /* Check zero                                           */ 
              const btScalar       rl=m_ray.length();
              if(rl<GJK_MIN_DISTANCE)
                     {/* Touching or inside                           */ 
                     m_status=eStatus::Inside;
                     break;
                     }
              /* Append new vertice in -'v' direction   */ 
              appendvertice(cs,-m_ray);
              const btVector3&     w=cs.c[cs.rank-1]->w;
              bool                        found=false;
              for(U i=0;i<4;++i)
                     {
                     if((w-lastw[i]).length2()<GJK_DUPLICATED_EPS)
                            { found=true;break; }
                     }
              if(found)
                     {/* Return old simplex                           */ 
                     removevertice(m_simplices[m_current]);
                     break;
                     }
                     else
                     {/* Update lastw                                 */ 
                     lastw[clastw=(clastw+1)&3]=w;
                     }
              /* Check for termination                         */ 
              const btScalar       omega=dot(m_ray,w)/rl;
              alpha=btMax(omega,alpha);
              if(((rl-alpha)-(GJK_ACCURARY*rl))<=0)
                     {/* Return old simplex                           */ 
                     removevertice(m_simplices[m_current]);
                     break;
                     }             
              /* Reduce simplex                                       */ 
              btScalar      weights[4];
              U                    mask=0;
              switch(cs.rank)
                     {
                     case   2:     sqdist=projectorigin(       cs.c[0]->w,
                                                                                    cs.c[1]->w,
                                                                                    weights,mask);break;
                     case   3:     sqdist=projectorigin(       cs.c[0]->w,
                                                                                    cs.c[1]->w,
                                                                                    cs.c[2]->w,
                                                                                    weights,mask);break;
                     case   4:     sqdist=projectorigin(       cs.c[0]->w,
                                                                                    cs.c[1]->w,
                                                                                    cs.c[2]->w,
                                                                                    cs.c[3]->w,
                                                                                    weights,mask);break;
                     }
              if(sqdist>=0)
                     {/* Valid     */ 
                     ns.rank              =      0;
                     m_ray         =      btVector3(0,0,0);
                     m_current     =      next;
                     for(U i=0,ni=cs.rank;i<ni;++i)
                            {
                            if(mask&(1<<i))
                                   {
                                   ns.c[ns.rank]        =      cs.c[i];
                                   ns.p[ns.rank++]             =      weights[i];
                                   m_ray                       +=     cs.c[i]->w*weights[i];
                                   }
                                   else
                                   {
                                   m_free[m_nfree++]    =      cs.c[i];
                                   }
                            }
                     if(mask==15) m_status=eStatus::Inside;
                     }
                     else
                     {/* Return old simplex                           */ 
                     removevertice(m_simplices[m_current]);
                     break;
                     }
              m_status=((++iterations)<GJK_MAX_ITERATIONS)?m_status:eStatus::Failed;
              } while(m_status==eStatus::Valid);
       m_simplex=&m_simplices[m_current];
       switch(m_status)
              {
              case   eStatus::Valid:             m_distance=m_ray.length();break;
              case   eStatus::Inside:     m_distance=0;break;
              }      
       return(m_status);
       }

Here is the call graph for this function:

Here is the caller graph for this function:

void gjkepa2_impl::GJK::getsupport ( const btVector3 d,
sSV sv 
) const [inline]

Definition at line 307 of file btGjkEpa2.cpp.

       {
       sv.d   =      d/d.length();
       sv.w   =      m_shape.Support(sv.d);
       }

Here is the call graph for this function:

Here is the caller graph for this function:

void gjkepa2_impl::GJK::Initialize ( ) [inline]

Definition at line 112 of file btGjkEpa2.cpp.

Here is the caller graph for this function:

static btScalar gjkepa2_impl::GJK::projectorigin ( const btVector3 a,
const btVector3 b,
btScalar w,
U m 
) [inline, static]

Definition at line 328 of file btGjkEpa2.cpp.

       {
       const btVector3      d=b-a;
       const btScalar       l=d.length2();
       if(l>GJK_SIMPLEX2_EPS)
              {
              const btScalar       t(l>0?-dot(a,d)/l:0);
              if(t>=1)             { w[0]=0;w[1]=1;m=2;return(b.length2()); }
              else if(t<=0) { w[0]=1;w[1]=0;m=1;return(a.length2()); }
              else                 { w[0]=1-(w[1]=t);m=3;return((a+d*t).length2()); }
              }
       return(-1);
       }

Here is the call graph for this function:

Here is the caller graph for this function:

static btScalar gjkepa2_impl::GJK::projectorigin ( const btVector3 a,
const btVector3 b,
const btVector3 c,
btScalar w,
U m 
) [inline, static]

Definition at line 343 of file btGjkEpa2.cpp.

       {
       static const U              imd3[]={1,2,0};
       const btVector3*     vt[]={&a,&b,&c};
       const btVector3             dl[]={a-b,b-c,c-a};
       const btVector3             n=cross(dl[0],dl[1]);
       const btScalar              l=n.length2();
       if(l>GJK_SIMPLEX3_EPS)
              {
              btScalar      mindist=-1;
              btScalar      subw[2];
              U                    subm;
              for(U i=0;i<3;++i)
                     {
                     if(dot(*vt[i],cross(dl[i],n))>0)
                            {
                            const U                     j=imd3[i];
                            const btScalar       subd(projectorigin(*vt[i],*vt[j],subw,subm));
                            if((mindist<0)||(subd<mindist))
                                   {
                                   mindist              =      subd;
                                   m                    =      ((subm&1)?1<<i:0)+((subm&2)?1<<j:0);
                                   w[i]          =      subw[0];
                                   w[j]          =      subw[1];
                                   w[imd3[j]]    =      0;                          
                                   }
                            }
                     }
              if(mindist<0)
                     {
                     const btScalar       d=dot(a,n);   
                     const btScalar       s=btSqrt(l);
                     const btVector3      p=n*(d/l);
                     mindist       =      p.length2();
                     m             =      7;
                     w[0]   =      (cross(dl[1],b-p)).length()/s;
                     w[1]   =      (cross(dl[2],c-p)).length()/s;
                     w[2]   =      1-(w[0]+w[1]);
                     }
              return(mindist);
              }
       return(-1);
       }

Here is the call graph for this function:

static btScalar gjkepa2_impl::GJK::projectorigin ( const btVector3 a,
const btVector3 b,
const btVector3 c,
const btVector3 d,
btScalar w,
U m 
) [inline, static]

Definition at line 389 of file btGjkEpa2.cpp.

       {
       static const U              imd3[]={1,2,0};
       const btVector3*     vt[]={&a,&b,&c,&d};
       const btVector3             dl[]={a-d,b-d,c-d};
       const btScalar              vl=det(dl[0],dl[1],dl[2]);
       const bool                  ng=(vl*dot(a,cross(b-c,a-b)))<=0;
       if(ng&&(btFabs(vl)>GJK_SIMPLEX4_EPS))
              {
              btScalar      mindist=-1;
              btScalar      subw[3];
              U                    subm;
              for(U i=0;i<3;++i)
                     {
                     const U                     j=imd3[i];
                     const btScalar       s=vl*dot(d,cross(dl[i],dl[j]));
                     if(s>0)
                            {
                            const btScalar       subd=projectorigin(*vt[i],*vt[j],d,subw,subm);
                            if((mindist<0)||(subd<mindist))
                                   {
                                   mindist              =      subd;
                                   m                    =      (subm&1?1<<i:0)+
                                                               (subm&2?1<<j:0)+
                                                               (subm&4?8:0);
                                   w[i]          =      subw[0];
                                   w[j]          =      subw[1];
                                   w[imd3[j]]    =      0;
                                   w[3]          =      subw[2];
                                   }
                            }
                     }
              if(mindist<0)
                     {
                     mindist       =      0;
                     m             =      15;
                     w[0]   =      det(c,b,d)/vl;
                     w[1]   =      det(a,c,d)/vl;
                     w[2]   =      det(b,a,d)/vl;
                     w[3]   =      1-(w[0]+w[1]+w[2]);
                     }
              return(mindist);
              }
       return(-1);
       }

Here is the call graph for this function:

void gjkepa2_impl::GJK::removevertice ( sSimplex simplex) [inline]

Definition at line 312 of file btGjkEpa2.cpp.

       {
       m_free[m_nfree++]=simplex.c[--simplex.rank];
       }

Here is the caller graph for this function:


Member Data Documentation

Definition at line 104 of file btGjkEpa2.cpp.

Definition at line 99 of file btGjkEpa2.cpp.

Definition at line 102 of file btGjkEpa2.cpp.

Definition at line 103 of file btGjkEpa2.cpp.

Definition at line 98 of file btGjkEpa2.cpp.

Definition at line 97 of file btGjkEpa2.cpp.

Definition at line 105 of file btGjkEpa2.cpp.

Definition at line 100 of file btGjkEpa2.cpp.

Definition at line 106 of file btGjkEpa2.cpp.

Definition at line 101 of file btGjkEpa2.cpp.


The documentation for this struct was generated from the following file: