Back to index

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

List of all members.

Classes

struct  eStatus
struct  sFace
struct  sHorizon
struct  sList

Public Types

typedef GJK::sSV sSV

Public Member Functions

 EPA ()
void Initialize ()
eStatus::_ Evaluate (GJK &gjk, const btVector3 &guess)
sFacenewface (sSV *a, sSV *b, sSV *c, bool forced)
sFacefindbest ()
bool expand (U pass, sSV *w, sFace *f, U e, sHorizon &horizon)

Static Public Member Functions

static void bind (sFace *fa, U ea, sFace *fb, U eb)
static void append (sList &list, sFace *face)
static void remove (sList &list, sFace *face)

Public Attributes

eStatus::_ m_status
GJK::sSimplex m_result
btVector3 m_normal
btScalar m_depth
sSV m_sv_store [EPA_MAX_VERTICES]
sFace m_fc_store [EPA_MAX_FACES]
U m_nextsv
sList m_hull
sList m_stock

Detailed Description

Definition at line 441 of file btGjkEpa2.cpp.


Class Documentation

struct gjkepa2_impl::EPA::sFace

Definition at line 445 of file btGjkEpa2.cpp.

Collaboration diagram for gjkepa2_impl::EPA::sFace:
Class Members
sSV * c
btScalar d
U1 e
sFace * f
sFace * l
btVector3 n
btScalar p
U1 pass

Member Typedef Documentation

Definition at line 444 of file btGjkEpa2.cpp.


Constructor & Destructor Documentation

gjkepa2_impl::EPA::EPA ( ) [inline]

Definition at line 491 of file btGjkEpa2.cpp.

       {
       Initialize(); 
       }

Here is the call graph for this function:


Member Function Documentation

static void gjkepa2_impl::EPA::append ( sList list,
sFace face 
) [inline, static]

Definition at line 701 of file btGjkEpa2.cpp.

       {
       face->l[0]    =      0;
       face->l[1]    =      list.root;
       if(list.root) list.root->l[0]=face;
       list.root     =      face;
       ++list.count;
       }

Here is the caller graph for this function:

static void gjkepa2_impl::EPA::bind ( sFace fa,
U  ea,
sFace fb,
U  eb 
) [inline, static]

Definition at line 696 of file btGjkEpa2.cpp.

       {
       fa->e[ea]=(U1)eb;fa->f[ea]=fb;
       fb->e[eb]=(U1)ea;fb->f[eb]=fa;
       }

Here is the caller graph for this function:

eStatus::_ gjkepa2_impl::EPA::Evaluate ( GJK gjk,
const btVector3 guess 
) [inline]

Definition at line 506 of file btGjkEpa2.cpp.

       {
       GJK::sSimplex&       simplex=*gjk.m_simplex;
       if((simplex.rank>1)&&gjk.EncloseOrigin())
              {
              /* Clean up                        */ 
              while(m_hull.root)
                     {
                     sFace* f(m_hull.root);
                     remove(m_hull,f);
                     append(m_stock,f);
                     }
              m_status      =      eStatus::Valid;
              m_nextsv      =      0;
              /* Orient simplex           */ 
              if(gjk.det(   simplex.c[0]->w-simplex.c[3]->w,
                                   simplex.c[1]->w-simplex.c[3]->w,
                                   simplex.c[2]->w-simplex.c[3]->w)<0)
                     {
                     btSwap(simplex.c[0],simplex.c[1]);
                     btSwap(simplex.p[0],simplex.p[1]);
                     }
              /* Build initial hull       */ 
              sFace* tetra[]={newface(simplex.c[0],simplex.c[1],simplex.c[2],true),
                                          newface(simplex.c[1],simplex.c[0],simplex.c[3],true),
                                          newface(simplex.c[2],simplex.c[1],simplex.c[3],true),
                                          newface(simplex.c[0],simplex.c[2],simplex.c[3],true)};
              if(m_hull.count==4)
                     {
                     sFace*        best=findbest();
                     sFace         outer=*best;
                     U                    pass=0;
                     U                    iterations=0;
                     bind(tetra[0],0,tetra[1],0);
                     bind(tetra[0],1,tetra[2],0);
                     bind(tetra[0],2,tetra[3],0);
                     bind(tetra[1],1,tetra[3],2);
                     bind(tetra[1],2,tetra[2],1);
                     bind(tetra[2],2,tetra[3],1);
                     m_status=eStatus::Valid;
                     for(;iterations<EPA_MAX_ITERATIONS;++iterations)
                            {
                            if(m_nextsv<EPA_MAX_VERTICES)
                                   {      
                                   sHorizon             horizon;
                                   sSV*                 w=&m_sv_store[m_nextsv++];
                                   bool                 valid=true;                               
                                   best->pass    =      (U1)(++pass);
                                   gjk.getsupport(best->n,*w);
                                   const btScalar       wdist=dot(best->n,w->w)-best->d;
                                   if(wdist>EPA_ACCURACY)
                                          {
                                          for(U j=0;(j<3)&&valid;++j)
                                                 {
                                                 valid&=expand(       pass,w,
                                                                             best->f[j],best->e[j],
                                                                             horizon);
                                                 }
                                          if(valid&&(horizon.nf>=3))
                                                 {
                                                 bind(horizon.cf,1,horizon.ff,2);
                                                 remove(m_hull,best);
                                                 append(m_stock,best);
                                                 best=findbest();
                                                 if(best->p>=outer.p) outer=*best;
                                                 } else { m_status=eStatus::InvalidHull;break; }
                                          } else { m_status=eStatus::AccuraryReached;break; }
                                   } else { m_status=eStatus::OutOfVertices;break; }
                            }
                     const btVector3      projection=outer.n*outer.d;
                     m_normal      =      outer.n;
                     m_depth              =      outer.d;
                     m_result.rank =      3;
                     m_result.c[0] =      outer.c[0];
                     m_result.c[1] =      outer.c[1];
                     m_result.c[2] =      outer.c[2];
                     m_result.p[0] =      cross( outer.c[1]->w-projection,
                                                                      outer.c[2]->w-projection).length();
                     m_result.p[1] =      cross( outer.c[2]->w-projection,
                                                                      outer.c[0]->w-projection).length();
                     m_result.p[2] =      cross( outer.c[0]->w-projection,
                                                                      outer.c[1]->w-projection).length();
                     const btScalar       sum=m_result.p[0]+m_result.p[1]+m_result.p[2];
                     m_result.p[0] /=     sum;
                     m_result.p[1] /=     sum;
                     m_result.p[2] /=     sum;
                     return(m_status);
                     }
              }
       /* Fallback          */ 
       m_status      =      eStatus::FallBack;
       m_normal      =      -guess;
       const btScalar       nl=m_normal.length();
       if(nl>0)
              m_normal      =      m_normal/nl;
              else
              m_normal      =      btVector3(1,0,0);
       m_depth       =      0;
       m_result.rank=1;
       m_result.c[0]=simplex.c[0];
       m_result.p[0]=1;     
       return(m_status);
       }

Here is the call graph for this function:

Here is the caller graph for this function:

bool gjkepa2_impl::EPA::expand ( U  pass,
sSV w,
sFace f,
U  e,
sHorizon horizon 
) [inline]

Definition at line 662 of file btGjkEpa2.cpp.

       {
       static const U       i1m3[]={1,2,0};
       static const U       i2m3[]={2,0,1};
       if(f->pass!=pass)
              {
              const U       e1=i1m3[e];
              if((dot(f->n,w->w)-f->d)<-EPA_PLANE_EPS)
                     {
                     sFace* nf=newface(f->c[e1],f->c[e],w,false);
                     if(nf)
                            {
                            bind(nf,0,f,e);
                            if(horizon.cf) bind(horizon.cf,1,nf,2); else horizon.ff=nf;
                            horizon.cf=nf;
                            ++horizon.nf;
                            return(true);
                            }
                     }
                     else
                     {
                     const U       e2=i2m3[e];
                     f->pass              =      (U1)pass;
                     if(    expand(pass,w,f->f[e1],f->e[e1],horizon)&&
                            expand(pass,w,f->f[e2],f->e[e2],horizon))
                            {
                            remove(m_hull,f);
                            append(m_stock,f);
                            return(true);
                            }
                     }
              }
       return(false);
       }

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 645 of file btGjkEpa2.cpp.

       {
       sFace*        minf=m_hull.root;
       btScalar      mind=minf->d*minf->d;
       btScalar      maxp=minf->p;
       for(sFace* f=minf->l[1];f;f=f->l[1])
              {
              const btScalar       sqd=f->d*f->d;
              if((f->p>=maxp)&&(sqd<mind))
                     {
                     minf=f;
                     mind=sqd;
                     maxp=f->p;
                     }
              }
       return(minf);
       }

Here is the caller graph for this function:

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

Definition at line 495 of file btGjkEpa2.cpp.

       {
       m_status      =      eStatus::Failed;
       m_normal      =      btVector3(0,0,0);
       m_depth              =      0;
       m_nextsv      =      0;
       for(U i=0;i<EPA_MAX_FACES;++i)
              {
              append(m_stock,&m_fc_store[EPA_MAX_FACES-i-1]);
              }
       }

Here is the call graph for this function:

Here is the caller graph for this function:

sFace* gjkepa2_impl::EPA::newface ( sSV a,
sSV b,
sSV c,
bool  forced 
) [inline]

Definition at line 609 of file btGjkEpa2.cpp.

       {
       if(m_stock.root)
              {
              sFace* face=m_stock.root;
              remove(m_stock,face);
              append(m_hull,face);
              face->pass    =      0;
              face->c[0]    =      a;
              face->c[1]    =      b;
              face->c[2]    =      c;
              face->n              =      cross(b->w-a->w,c->w-a->w);
              const btScalar       l=face->n.length();
              const bool           v=l>EPA_ACCURACY;
              face->p              =      btMin(btMin(
                                                 dot(a->w,cross(face->n,a->w-b->w)),
                                                 dot(b->w,cross(face->n,b->w-c->w))),
                                                 dot(c->w,cross(face->n,c->w-a->w)))       /
                                                 (v?l:1);
              face->p              =      face->p>=-EPA_INSIDE_EPS?0:face->p;
              if(v)
                     {
                     face->d              =      dot(a->w,face->n)/l;
                     face->n              /=     l;
                     if(forced||(face->d>=-EPA_PLANE_EPS))
                            {
                            return(face);
                            } else m_status=eStatus::NonConvex;
                     } else m_status=eStatus::Degenerated;
              remove(m_hull,face);
              append(m_stock,face);
              return(0);
              }
       m_status=m_stock.root?eStatus::OutOfVertices:eStatus::OutOfFaces;
       return(0);
       }

Here is the call graph for this function:

Here is the caller graph for this function:

static void gjkepa2_impl::EPA::remove ( sList list,
sFace face 
) [inline, static]

Definition at line 709 of file btGjkEpa2.cpp.

       {
       if(face->l[1]) face->l[1]->l[0]=face->l[0];
       if(face->l[0]) face->l[0]->l[1]=face->l[1];
       if(face==list.root) list.root=face->l[1];
       --list.count;
       }

Member Data Documentation

Definition at line 484 of file btGjkEpa2.cpp.

Definition at line 486 of file btGjkEpa2.cpp.

Definition at line 488 of file btGjkEpa2.cpp.

Definition at line 487 of file btGjkEpa2.cpp.

Definition at line 483 of file btGjkEpa2.cpp.

Definition at line 482 of file btGjkEpa2.cpp.

Definition at line 481 of file btGjkEpa2.cpp.

Definition at line 489 of file btGjkEpa2.cpp.

Definition at line 485 of file btGjkEpa2.cpp.


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