spherepack.cpp

游戏编程精粹2第四章源码

#if DEMO
unsigned int SpherePackFactory::GetColor(void)
{
  unsigned int ret = mColors[mColorCount];
  mColorCount++;
  if ( mColorCount == MAXCOLORS ) mColorCount = 0;
  return ret;
}
#endif

void SpherePackFactory::Integrate(SpherePack *pack,
                                  SpherePack *supersphere,
                                  float node_size)
{
  // ok..time to integrate this sphere with the tree
  // first find which supersphere we are closest to the center of

  SpherePack *search = supersphere->GetChildren();

  SpherePack *nearest1 = 0;  // nearest supersphere we are completely
  float neardist1 = 1e9;     // enclosed within

  SpherePack *nearest2 = 0; // supersphere we must grow the least to
  float neardist2 = 1e9;    // add ourselves to.

  int scount = 1;

  while ( search )
  {
    if ( search->HasSpherePackFlag(SPF_SUPERSPHERE) && !search->HasSpherePackFlag(SPF_ROOTNODE) && search->GetChildCount() )
    {

      float dist = pack->DistanceSquared(search);

      if ( nearest1 )
      {
        if ( dist < neardist1 )
        {

          float d = sqrtf(dist)+pack->GetRadius();

          if ( d <= search->GetRadius() )
          {
            neardist1 = dist;
            nearest1  = search;
          }
        }
      }
      else
      {

        float d = (sqrtf(dist) + pack->GetRadius())-search->GetRadius();

        if ( d < neardist2 )
        {
          if ( d < 0 )
          {
            neardist1 = dist;
            nearest1  = search;
          }
          else
          {
            neardist2 = d;
            nearest2  = search;
          }
        }
      }
    }
    search = search->GetNextSibling();
  }

  // ok...now..on exit let's see what we got.
  if ( nearest1 )
  {
    // if we are inside an existing supersphere, we are all good!
    // we need to detach item from wherever it is, and then add it to
    // this supersphere as a child.
    pack->Unlink();
    nearest1->AddChild(pack);
    pack->ComputeBindingDistance(nearest1);
    nearest1->Recompute(mSuperSphereGravy);

    if ( nearest1->HasSpherePackFlag(SPF_LEAF_TREE) )
    {
      SpherePack *link = (SpherePack *) nearest1->GetUserData();
      link->NewPosRadius( nearest1->GetPos(), nearest1->GetRadius() );
    }

  }
  else
  {
    bool newsphere = true;

    if ( nearest2 )
    {
      float newsize = neardist2 + nearest2->GetRadius() + mSuperSphereGravy;

      if ( newsize <= node_size )
      {
        pack->Unlink();

        nearest2->SetRadius(newsize);
        nearest2->AddChild(pack);
        nearest2->Recompute(mSuperSphereGravy);
        pack->ComputeBindingDistance(nearest2);

        if ( nearest2->HasSpherePackFlag(SPF_LEAF_TREE) )
        {
          SpherePack *link = (SpherePack *) nearest2->GetUserData();
          link->NewPosRadius( nearest2->GetPos(), nearest2->GetRadius() );
        }

        newsphere = false;

      }

    }

    if ( newsphere )
    {
      assert( supersphere->HasSpherePackFlag(SPF_ROOTNODE) );
      // we are going to create a new superesphere around this guy!
      pack->Unlink();

      SpherePack *parent = mSpheres.GetFreeLink();
      assert( parent );
      parent->Init( this, pack->GetPos(), pack->GetRadius()+mSuperSphereGravy, 0 );

      if ( supersphere->HasSpherePackFlag(SPF_ROOT_TREE) )
        parent->SetSpherePackFlag(SPF_ROOT_TREE);
      else
        parent->SetSpherePackFlag(SPF_LEAF_TREE);

      parent->SetSpherePackFlag(SPF_SUPERSPHERE);
      #if DEMO
      parent->SetColor( GetColor() );
      #endif
      parent->AddChild(pack);

      supersphere->AddChild(parent);

      parent->Recompute(mSuperSphereGravy);
      pack->ComputeBindingDistance(parent);

      if ( parent->HasSpherePackFlag(SPF_LEAF_TREE) )
      {
        // need to create parent association!
        SpherePack *link = AddSphere( parent->GetPos(), parent->GetRadius(), parent, SPF_ROOT_TREE);
        parent->SetUserData(link); // hook him up!!
      }

    }
  }

  pack->ClearSpherePackFlag(SPF_INTEGRATE); // we've been integrated!
}


void SpherePackFactory::FrustumTest(const Frustum &f,SpherePackCallback *callback)
{
  // test case here, just traverse children.
  mCallback = callback;
  mRoot->VisibilityTest(f,this,VS_PARTIAL);
}


void SpherePack::VisibilityTest(const Frustum &f,SpherePackCallback *callback,ViewState state)
{

  if ( state == VS_PARTIAL )
  {
    state = f.ViewVolumeTest( mCenter, GetRadius() );
    #if DEMO
    if ( state != VS_OUTSIDE )
    {
      DrawCircle( int(mCenter.x), int(mCenter.y), int(GetRadius()), 0x404040);
    }
    #endif
  }

  if ( HasSpherePackFlag(SPF_SUPERSPHERE) )
  {


    if ( state == VS_OUTSIDE )
    {
      if ( HasSpherePackFlag(SPF_HIDDEN) ) return; // no state change
      ClearSpherePackFlag( SpherePackFlag(SPF_INSIDE | SPF_PARTIAL) );
      SetSpherePackFlag(SPF_HIDDEN);
    }
    else
    {
      if ( state == VS_INSIDE )
      {
        if ( HasSpherePackFlag(SPF_INSIDE) ) return; // no state change
        ClearSpherePackFlag( SpherePackFlag(SPF_PARTIAL | SPF_HIDDEN) );
        SetSpherePackFlag(SPF_INSIDE);
      }
      else
      {
        ClearSpherePackFlag( SpherePackFlag(SPF_HIDDEN | SPF_INSIDE) );
        SetSpherePackFlag(SPF_PARTIAL);
      }
    }

    SpherePack *pack = mChildren;

    while ( pack )
    {
      pack->VisibilityTest(f,callback,state);
      pack = pack->GetNextSibling();
    }

  }
  else
  {
    switch ( state )
    {
      case VS_INSIDE:
        if ( !HasSpherePackFlag(SPF_INSIDE) )
        {
          ClearSpherePackFlag( SpherePackFlag(SPF_HIDDEN | SPF_PARTIAL) );
          SetSpherePackFlag(SPF_INSIDE);
          callback->VisibilityCallback(f,this,state);
        }
        break;
      case VS_OUTSIDE:
        if ( !HasSpherePackFlag(SPF_HIDDEN) )
        {
          ClearSpherePackFlag( SpherePackFlag(SPF_INSIDE | SPF_PARTIAL) );
          SetSpherePackFlag(SPF_HIDDEN);
          callback->VisibilityCallback(f,this,state);
        }
        break;
      case VS_PARTIAL:
        if ( !HasSpherePackFlag(SPF_PARTIAL) )
        {
          ClearSpherePackFlag( SpherePackFlag(SPF_INSIDE | SPF_HIDDEN) );
          SetSpherePackFlag(SPF_PARTIAL);
          callback->VisibilityCallback(f,this,state);
        }
        break;
    }

  }
}

void SpherePackFactory::RayTrace(const Vector3d<float> &p1,
                                 const Vector3d<float> &p2,
                                 SpherePackCallback *callback)
{
  // test case here, just traverse children.
  Vector3d<float> dir = p2-p1;
  float dist = dir.Normalize();
  mCallback = callback;
  mRoot->RayTrace(p1,dir,dist,this);
}

void SpherePack::RayTrace(const Vector3d<float> &p1,
                          const Vector3d<float> &dir,
                          float distance,
                          SpherePackCallback *callback)
{
  bool hit = false;

  if ( HasSpherePackFlag(SPF_SUPERSPHERE) )
  {

    hit = RayIntersectionInFront(p1,dir,0);

    if ( hit )
    {
      #if DEMO
      DrawCircle( int(mCenter.x), int(mCenter.y), int(GetRadius()), 0x404040);
      #endif
      SpherePack *pack = mChildren;

      while ( pack )
      {
        pack->RayTrace(p1,dir,distance,callback);
        pack = pack->GetNextSibling();
      }
    }

  }
  else
  {
    Vector3d<float> sect;
    hit = RayIntersection(p1,dir,distance,&sect);
  	if ( hit )
	  {
  	  callback->RayTraceCallback(p1,dir,distance,sect,this);
  	}
  }
}

void SpherePackFactory::RayTraceCallback(const Vector3d<float> &p1,          // source pos of ray
                              const Vector3d<float> &dir,          // direction of ray
                              float distance,                      // distance of ray
             	  						  const Vector3d<float> &sect,          // intersection location
                              SpherePack *sphere)
{
  SpherePack *link = (SpherePack *) sphere->GetUserData();
  if ( link ) link->RayTrace(p1,dir,distance,mCallback);
};


void SpherePackFactory::RangeTest(const Vector3d<float> &center,float radius,SpherePackCallback *callback)
{
  mCallback = callback;
  mRoot->RangeTest(center,radius,this,VS_PARTIAL);
}


void SpherePack::RangeTest(const Vector3d<float> &p,
                           float distance,
                           SpherePackCallback *callback,
                           ViewState state)
{
  if ( state == VS_PARTIAL )
  {
    float d = p.Distance(mCenter);
    if ( (d-distance) > GetRadius() ) return;;
    if ( (GetRadius()+d) < distance ) state = VS_INSIDE;
  }

  if ( HasSpherePackFlag(SPF_SUPERSPHERE) )
  {
    #if DEMO
    if ( state == VS_PARTIAL )
    {
      DrawCircle( int(mCenter.x), int(mCenter.y), int(GetRadius()), 0x404040);
    }
    #endif
    SpherePack *pack = mChildren;
    while ( pack )
    {
      pack->RangeTest(p,distance,callback,state);
      pack = pack->GetNextSibling();
    }

  }
  else
  {
    callback->RangeTestCallback(p,distance,this,state);
  }
}

void SpherePackFactory::RangeTestCallback(const Vector3d<float> &p,float distance,SpherePack *sphere,ViewState state)
{
  SpherePack *link = (SpherePack *) sphere->GetUserData();
  if ( link ) link->RangeTest(p,distance,mCallback,state);
};


void SpherePackFactory::Reset(void)
{
  mRoot->Reset();
  mLeaf->Reset();
}


void SpherePack::Reset(void)
{
  ClearSpherePackFlag( SpherePackFlag(SPF_HIDDEN | SPF_PARTIAL | SPF_INSIDE) );

  SpherePack *pack = mChildren;
  while ( pack )
  {
    pack->Reset();
    pack = pack->GetNextSibling();
  }
}

void SpherePackFactory::VisibilityCallback(const Frustum &f,SpherePack *sphere,ViewState state)
{
  SpherePack *link = (SpherePack *) sphere->GetUserData();
  if ( link ) link->VisibilityTest(f,mCallback,state);
}