spherepack.cpp

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

/* Copyright (C) John W. Ratcliff, 2001. 
 * All rights reserved worldwide.
 *
 * This software is provided "as is" without express or implied
 * warranties. You may freely copy and compile this source into
 * applications you distribute provided that the copyright text
 * below is included in the resulting source code, for example:
 * "Portions Copyright (C) John W. Ratcliff, 2001"
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>

#include "spherepack.h"


#if DEMO
int PrintText(int x, int y, int color, char* output, ...);
int DrawLine(int x1, int y1, int x2, int y2, int color);
int DrawCircle(int locx, int locy, int radius, int color);
#endif

SpherePackFactory::SpherePackFactory(int maxspheres,float rootsize,float leafsize,float gravy)
{
  maxspheres*=4; // include room for both trees, the root node and leaf node tree, and the supersheres
  mMaxRootSize      = rootsize;
  mMaxLeafSize      = leafsize;
  mSuperSphereGravy = gravy;
  mIntegrate        = new SpherePackFifo(maxspheres);
  mRecompute        = new SpherePackFifo(maxspheres);

  mSpheres.Set(maxspheres);       // init pool to hold all possible SpherePack instances.

  Vector3d<float> p(0,0,0);

  mRoot = mSpheres.GetFreeLink(); // initially empty
  mRoot->Init(this,p,65536,0);
  mRoot->SetSpherePackFlag( SpherePackFlag(SPF_SUPERSPHERE | SPF_ROOTNODE | SPF_ROOT_TREE) );

  #if DEMO
  mRoot->SetColor(0x00FFFFFF);
  #endif

  mLeaf = mSpheres.GetFreeLink();; // initially empty
  mLeaf->Init(this,p,16384,0);
  mLeaf->SetSpherePackFlag( SpherePackFlag(SPF_SUPERSPHERE | SPF_ROOTNODE | SPF_LEAF_TREE) );

  #if DEMO

  mLeaf->SetColor(0x00FFFFFF);
  mColorCount = 0;

  mColors[0]  = 0x00FF0000;
  mColors[1]  = 0x0000FF00;
  mColors[2]  = 0x000000FF;
  mColors[3]  = 0x00FFFF00;
  mColors[4]  = 0x00FF00FF;
  mColors[5]  = 0x0000FFFF;
  mColors[6]  = 0x00FF8080;
  mColors[7]  = 0x0000FF80;
  mColors[8]  = 0x000080FF;
  mColors[9]  = 0x00FFFF80;
  mColors[10] = 0x00FF80FF;
  mColors[11] = 0x0080FFFF;

  #endif
}

SpherePackFactory::~SpherePackFactory(void)
{
  delete mIntegrate;  // free up integration fifo
  delete mRecompute;  // free up recomputation fifo.
}

void SpherePackFactory::Process(void)
{
  if ( 1 )
  {
    // First recompute anybody that needs to be recomputed!!
    // When leaf node spheres exit their parent sphere, then the parent sphere needs to be rebalanced.  In fact,it may now be empty and
    // need to be removed.
    // This is the location where (n) number of spheres in the recomputation FIFO are allowed to be rebalanced in the tree.
    int maxrecompute = mRecompute->GetCount();
    for (int i=0; i<maxrecompute; i++)
    {
      SpherePack *pack = mRecompute->Pop();
      if ( !pack ) break;
      pack->SetFifo1(0); // no longer on the fifo!!
      bool kill = pack->Recompute(mSuperSphereGravy);
      if ( kill ) Remove(pack);
    }
  }

  if ( 1 )
  {
    // Now, process the integration step.

    int maxintegrate = mIntegrate->GetCount();

    for (int i=0; i<maxintegrate; i++)
    {
      SpherePack *pack = mIntegrate->Pop();
      if ( !pack ) break;
      pack->SetFifo2(0);

      if ( pack->HasSpherePackFlag(SPF_ROOT_TREE) )
        Integrate(pack,mRoot,mMaxRootSize); // integrate this one single dude against the root node.
      else
        Integrate(pack,mLeaf,mMaxLeafSize); // integrate this one single dude against the root node.
    }
  }

}


SpherePack * SpherePackFactory::AddSphere(const Vector3d<float> &pos,
                                          float radius,
                                          void *userdata,
                                          int flags)
{

  SpherePack *pack = mSpheres.GetFreeLink();

  assert( pack );

  if ( pack )
  {
    if ( flags & SPF_ROOT_TREE )
    {
      pack->Init(this,pos,radius,userdata);
      pack->SetSpherePackFlag(SPF_ROOT_TREE); // member of the leaf node tree!
      AddIntegrate(pack); // add to integration list.
    }
    else
    {
      pack->Init(this,pos,radius,userdata);
      pack->SetSpherePackFlag(SPF_LEAF_TREE); // member of the leaf node tree!
      AddIntegrate(pack); // add to integration list.
    }
  }

  return pack;
}

void SpherePackFactory::AddIntegrate(SpherePack *pack)
{

  if ( pack->HasSpherePackFlag(SPF_ROOT_TREE) )
    mRoot->AddChild(pack);
  else
    mLeaf->AddChild(pack);

  pack->SetSpherePackFlag(SPF_INTEGRATE); // still needs to be integrated!
  SpherePack **fifo = mIntegrate->Push(pack); // add it to the integration stack.
  pack->SetFifo2(fifo);
}

void SpherePackFactory::AddRecompute(SpherePack *recompute)
{
  if ( !recompute->HasSpherePackFlag(SPF_RECOMPUTE) )
  {
    if ( recompute->GetChildCount() )
    {
      recompute->SetSpherePackFlag(SPF_RECOMPUTE); // needs to be recalculated!
      SpherePack **fifo = mRecompute->Push(recompute);
      recompute->SetFifo1(fifo);
    }
    else
    {
      Remove(recompute);
    }
  }
}

void SpherePackFactory::Render(void)
{
  #if DEMO
  mRoot->Render( mRoot->GetColor() );
  mLeaf->Render( mLeaf->GetColor() );
  #endif
}


void SpherePack::Render(unsigned int color)
{
  #if DEMO
  if ( !HasSpherePackFlag(SPF_ROOTNODE) )
  {

    if ( HasSpherePackFlag(SPF_SUPERSPHERE) )
    {
      color = mColor;
    }
    else
    {
      if ( mParent->HasSpherePackFlag(SPF_ROOTNODE) ) color = 0x00FFFFFF;
    }
    #if DEMO
  	DrawCircle( int(mCenter.x), int(mCenter.y),int(GetRadius()),color);
    #endif
    if ( HasSpherePackFlag(SPF_SUPERSPHERE) )
    {
      if ( HasSpherePackFlag(SPF_LEAF_TREE) )
      {

        #if DEMO
    	  DrawCircle( int(mCenter.x), int(mCenter.y),int(GetRadius()),color);
        #endif
        SpherePack *link = (SpherePack *) GetUserData();

        link = link->GetParent();

        if ( link && !link->HasSpherePackFlag(SPF_ROOTNODE) )
        {
          DrawLine( int(mCenter.x), int(mCenter.y),
                    int(link->mCenter.x), int(link->mCenter.y),
                    link->GetColor() );
        }
      }
      else
      {
        #if DEMO
    	  DrawCircle( int(mCenter.x), int(mCenter.y),int(GetRadius())+3,color);
        #endif
      }

    }

  }

  if ( mChildren )
  {
    SpherePack *pack = mChildren;

    while ( pack )
    {
      pack->Render(color);
      pack = pack->GetNextSibling();
    }
  }
  #endif
}

bool SpherePack::Recompute(float gravy)
{
  if ( !mChildren ) return true; // kill it!
  if ( HasSpherePackFlag(SPF_ROOTNODE) ) return false; // don't recompute root nodes!

  #if 1
  // recompute bounding sphere!
  Vector3d<float> total(0,0,0);
  int count=0;
  SpherePack *pack = mChildren;
  while ( pack )
  {
    total+=pack->mCenter;
    count++;
    pack = pack->GetNextSibling();
  }

  if ( count )
  {
    float recip = 1.0f / float(count);
    total*=recip;

    Vector3d<float> oldpos = mCenter;

    mCenter = total; // new origin!
    float maxradius = 0;

    pack = mChildren;

    while ( pack )
    {
      float dist = DistanceSquared(pack);
      float radius = sqrtf(dist) + pack->GetRadius();
      if ( radius > maxradius )
      {
        maxradius = radius;
        if ( (maxradius+gravy) >= GetRadius() )
        {
          mCenter = oldpos;
          ClearSpherePackFlag(SPF_RECOMPUTE);
          return false;
        }
      }
      pack = pack->GetNextSibling();
    }

    maxradius+=gravy;

    SetRadius(maxradius);

    // now all children have to recompute binding distance!!
    pack = mChildren;

    while ( pack )
    {
      pack->ComputeBindingDistance(this);
      pack = pack->GetNextSibling();
    }

  }

  #endif

  ClearSpherePackFlag(SPF_RECOMPUTE);

  return false;
}


void SpherePack::LostChild(SpherePack *t)
{
  assert( mChildCount );
  assert( mChildren );

  #ifdef _DEBUG  // debug validation code.

  SpherePack *pack = mChildren;
  bool found = false;
  while ( pack )
  {
    if ( pack == t )
    {
      assert( !found );
      found = true;
    }
    pack = pack->GetNextSibling();
  }
  assert( found );

  #endif

  // first patch old linked list.. his previous now points to his next
  SpherePack *prev = t->GetPrevSibling();

  if ( prev )
  {
    SpherePack *next = t->GetNextSibling();
    prev->SetNextSibling( next ); // my previous now points to my next
    if ( next ) next->SetPrevSibling(prev);
    // list is patched!
  }
  else
  {
    SpherePack *next = t->GetNextSibling();
    mChildren = next;
    if ( mChildren) mChildren->SetPrevSibling(0);
  }

  mChildCount--;

  if ( !mChildCount && HasSpherePackFlag(SPF_SUPERSPHERE))
  {
    mFactory->Remove(this);
  }
}

void SpherePackFactory::Remove(SpherePack *pack)
{

  if ( pack->HasSpherePackFlag(SPF_ROOTNODE) ) return; // CAN NEVER REMOVE THE ROOT NODE EVER!!!

  if ( pack->HasSpherePackFlag(SPF_SUPERSPHERE) && pack->HasSpherePackFlag(SPF_LEAF_TREE) )
  {

    SpherePack *link = (SpherePack *) pack->GetUserData();

    Remove(link);
  }

  pack->Unlink();

  mSpheres.Release(pack);
}