Back to index

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

List of all members.

Classes

struct  Face

Public Member Functions

 EPA (GJK *pgjk)
 ~EPA ()
Vector3 GetCoordinates (const Face *face) const
FaceFindBest () const
Z Set (Face *f, const GJK::Mkv *a, const GJK::Mkv *b, const GJK::Mkv *c) const
FaceNewFace (const GJK::Mkv *a, const GJK::Mkv *b, const GJK::Mkv *c)
void Detach (Face *face)
void Link (Face *f0, U e0, Face *f1, U e1) const
GJK::MkvSupport (const Vector3 &w) const
U BuildHorizon (U markid, const GJK::Mkv *w, Face &f, U e, Face *&cf, Face *&ff)
F EvaluatePD (F accuracy=EPA_accuracy)

Public Attributes

GJKgjk
btStackAllocsa
Faceroot
U nfaces
U iterations
Vector3 features [2][3]
Vector3 nearest [2]
Vector3 normal
F depth
Z failed

Detailed Description

Definition at line 320 of file btGjkEpa.cpp.


Constructor & Destructor Documentation

gjkepa_impl::EPA::EPA ( GJK pgjk) [inline]

Definition at line 347 of file btGjkEpa.cpp.

              {
              gjk           =      pgjk;
              sa            =      pgjk->sa;
              }
gjkepa_impl::EPA::~EPA ( ) [inline]

Definition at line 353 of file btGjkEpa.cpp.

              {
              }

Member Function Documentation

U gjkepa_impl::EPA::BuildHorizon ( U  markid,
const GJK::Mkv w,
Face f,
U  e,
Face *&  cf,
Face *&  ff 
) [inline]

Definition at line 447 of file btGjkEpa.cpp.

              {
              static const U       mod3[]={0,1,2,0,1};
              U                           ne(0);
              if(f.mark!=markid)
                     {
                     const U       e1(mod3[e+1]);
                     if((f.n.dot(w->w)+f.d)>0)
                            {
                            Face*  nf = NewFace(f.v[e1],f.v[e],w);
                            Link(nf,0,&f,e);
                            if(cf) Link(cf,1,nf,2); else ff=nf;
                            cf=nf;ne=1;
                            }
                            else
                            {
                            const U       e2(mod3[e+2]);
                            Detach(&f);
                            f.mark =      markid;
                            ne            +=     BuildHorizon(markid,w,*f.f[e1],f.e[e1],cf,ff);
                            ne            +=     BuildHorizon(markid,w,*f.f[e2],f.e[e2],cf,ff);
                            }
                     }
              return(ne);
              }

Here is the call graph for this function:

Here is the caller graph for this function:

void gjkepa_impl::EPA::Detach ( Face face) [inline]

Definition at line 416 of file btGjkEpa.cpp.

              {
              if(face->prev||face->next)
                     {
                     --nfaces;
                     if(face==root)
                            { root=face->next;root->prev=0; }
                            else
                            {
                            if(face->next==0)
                                   { face->prev->next=0; }
                                   else
                                   { face->prev->next=face->next;face->next->prev=face->prev; }
                            }
                     face->prev=face->next=0;
                     }
              }

Here is the caller graph for this function:

F gjkepa_impl::EPA::EvaluatePD ( F  accuracy = EPA_accuracy) [inline]

Definition at line 474 of file btGjkEpa.cpp.

              {
              btBlock*      sablock = sa->beginBlock();
              Face*                       bestface = 0;
              U                                  markid(1);
              depth         =      -cstInf;
              normal        =      Vector3(0,0,0);
              root          =      0;
              nfaces        =      0;
              iterations    =      0;
              failed        =      false;
              /* Prepare hull             */
              if(gjk->EncloseOrigin())
                     {
                     const U*             pfidx = 0;
                     U                           nfidx= 0;
                     const U*             peidx = 0;
                     U                           neidx = 0;
                     GJK::Mkv*            basemkv[5];
                     Face*                basefaces[6];
                     switch(gjk->order)
                            {
                            /* Tetrahedron              */
                            case   3:     {
                                                 static const U       fidx[4][3]={{2,1,0},{3,0,1},{3,1,2},{3,2,0}};
                                                 static const 
U      eidx[6][4]={{0,0,2,1},{0,1,1,1},{0,2,3,1},{1,0,3,2},{2,0,1,2},{3,0,2,2}};
                                                 pfidx=(const U*)fidx;nfidx=4;peidx=(const U*)eidx;neidx=6;
                                                 }      break;
                            /* Hexahedron        */
                            case   4:     {
                                                 static const 
U      fidx[6][3]={{2,0,4},{4,1,2},{1,4,0},{0,3,1},{0,2,3},{1,3,2}};
                                                 static const 
U      eidx[9][4]={{0,0,4,0},{0,1,2,1},{0,2,1,2},{1,1,5,2},{1,0,2,0},{2,2,3,2},{3,1,5,0},{3,0,4,2},{5,1,4,1}};
                                                 pfidx=(const U*)fidx;nfidx=6;peidx=(const U*)eidx;neidx=9;
                                                 }      break;
                            }
                     U i;

                     for( i=0;i<=gjk->order;++i)        { 
basemkv[i]=(GJK::Mkv*)sa->allocate(sizeof(GJK::Mkv));*basemkv[i]=gjk->simplex[i]; 
}
                     for( i=0;i<nfidx;++i,pfidx+=3)            { 
basefaces[i]=NewFace(basemkv[pfidx[0]],basemkv[pfidx[1]],basemkv[pfidx[2]]); 
}
                     for( i=0;i<neidx;++i,peidx+=4)            { 
Link(basefaces[peidx[0]],peidx[1],basefaces[peidx[2]],peidx[3]); }
                     }
              if(0==nfaces)
                     {
                     sa->endBlock(sablock);
                     return(depth);
                     }
              /* Expand hull              */
              for(;iterations<EPA_maxiterations;++iterations)
                     {
                     Face*         bf = FindBest();
                     if(bf)
                            {
                            GJK::Mkv*     w = Support(-bf->n);
                            const F              d(bf->n.dot(w->w)+bf->d);
                            bestface      =      bf;
                            if(d<-accuracy)
                                   {
                                   Face*  cf =0;
                                   Face*  ff =0;
                                   U             nf = 0;
                                   Detach(bf);
                                   bf->mark=++markid;
                                   for(U i=0;i<3;++i)   { 
nf+=BuildHorizon(markid,w,*bf->f[i],bf->e[i],cf,ff); }
                                   if(nf<=2)                   { break; }
                                   Link(cf,1,ff,2);
                                   } else break;
                            } else break;
                     }
              /* Extract contact   */
              if(bestface)
                     {
                     const Vector3 b(GetCoordinates(bestface));
                     normal               =      bestface->n;
                     depth                =      Max<F>(0,bestface->d);
                     for(U i=0;i<2;++i)
                            {
                            const F       s(F(i?-1:1));
                            for(U j=0;j<3;++j)
                                   {
                                   features[i][j]=gjk->LocalSupport(s*bestface->v[j]->r,i);
                                   }
                            }
                     nearest[0]           =      features[0][0]*b.x()+features[0][1]*b.y()+features[0][2]*b.z();
                     nearest[1]           =      features[1][0]*b.x()+features[1][1]*b.y()+features[1][2]*b.z();
                     } else failed=true;
              sa->endBlock(sablock);
              return(depth);
              }

Here is the call graph for this function:

Here is the caller graph for this function:

Face* gjkepa_impl::EPA::FindBest ( ) const [inline]

Definition at line 367 of file btGjkEpa.cpp.

              {
              Face*  bf = 0;
              if(root)
                     {
                     Face*  cf = root;
                     F             bd(cstInf);
                     do     {
                            if(cf->d<bd) { bd=cf->d;bf=cf; }
                            } while(0!=(cf=cf->next));
                     }
              return(bf);
              }

Here is the caller graph for this function:

Vector3 gjkepa_impl::EPA::GetCoordinates ( const Face face) const [inline]

Definition at line 357 of file btGjkEpa.cpp.

              {
              const Vector3 o(face->n*-face->d);
              const F                     a[]={  cross(face->v[0]->w-o,face->v[1]->w-o).length(),
                                                        cross(face->v[1]->w-o,face->v[2]->w-o).length(),
                                                        cross(face->v[2]->w-o,face->v[0]->w-o).length()};
              const F                     sm(a[0]+a[1]+a[2]);
              return(Vector3(a[1],a[2],a[0])/(sm>0?sm:1));
              }

Here is the call graph for this function:

Here is the caller graph for this function:

void gjkepa_impl::EPA::Link ( Face f0,
U  e0,
Face f1,
U  e1 
) const [inline]

Definition at line 434 of file btGjkEpa.cpp.

              {
              f0->f[e0]=f1;f1->e[e1]=e0;
              f1->f[e1]=f0;f0->e[e0]=e1;
              }

Here is the caller graph for this function:

Face* gjkepa_impl::EPA::NewFace ( const GJK::Mkv a,
const GJK::Mkv b,
const GJK::Mkv c 
) [inline]

Definition at line 398 of file btGjkEpa.cpp.

              {
              Face*  pf = (Face*)sa->allocate(sizeof(Face));
              if(Set(pf,a,b,c))
                     {
                     if(root) root->prev=pf;
                     pf->prev=0;
                     pf->next=root;
                     root   =pf;
                     ++nfaces;
                     }
                     else
                     {
                     pf->prev=pf->next=0;
                     }
              return(pf);
              }

Here is the call graph for this function:

Here is the caller graph for this function:

Z gjkepa_impl::EPA::Set ( Face f,
const GJK::Mkv a,
const GJK::Mkv b,
const GJK::Mkv c 
) const [inline]

Definition at line 381 of file btGjkEpa.cpp.

              {
              const Vector3 nrm(cross(b->w-a->w,c->w-a->w));
              const F                     len(nrm.length());
              const Z                     valid( (cross(a->w,b->w).dot(nrm)>=-EPA_inface_eps)&&
                                                        (cross(b->w,c->w).dot(nrm)>=-EPA_inface_eps)&&
                                                        (cross(c->w,a->w).dot(nrm)>=-EPA_inface_eps));
              f->v[0]       =      a;
              f->v[1]       =      b;
              f->v[2]       =      c;
              f->mark       =      0;
              f->n   =      nrm/(len>0?len:cstInf);
              f->d   =      Max<F>(0,-f->n.dot(a->w));
              return(valid);
              }

Here is the call graph for this function:

Here is the caller graph for this function:

GJK::Mkv* gjkepa_impl::EPA::Support ( const Vector3 w) const [inline]

Definition at line 440 of file btGjkEpa.cpp.

              {
              GJK::Mkv*            v =(GJK::Mkv*)sa->allocate(sizeof(GJK::Mkv));
              gjk->Support(w,*v);
              return(v);
              }

Here is the call graph for this function:

Here is the caller graph for this function:


Member Data Documentation

Definition at line 344 of file btGjkEpa.cpp.

Definition at line 345 of file btGjkEpa.cpp.

Definition at line 341 of file btGjkEpa.cpp.

Definition at line 336 of file btGjkEpa.cpp.

Definition at line 340 of file btGjkEpa.cpp.

Definition at line 342 of file btGjkEpa.cpp.

Definition at line 339 of file btGjkEpa.cpp.

Definition at line 343 of file btGjkEpa.cpp.

Definition at line 338 of file btGjkEpa.cpp.

Definition at line 337 of file btGjkEpa.cpp.


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