TriangleAdjacencyGraph.cpp

/*---------------------------------------------------------------------------*\
 *                                OpenSG                                     *
 *                                                                           *
 *                                                                           *
 *             Copyright (C) 2000-2002 by the OpenSG Forum                   *
 *                                                                           *
 *                            www.opensg.org                                 *
 *                                                                           *
 *   contact: dirk@opensg.org, gerrit.voss@vossg.org, jbehr@zgdv.de          *
 *                                                                           *
 \*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*\
 *                                License                                    *
 *                                                                           *
 * This library is free software; you can redistribute it and/or modify it   *
 * under the terms of the GNU Library General Public License as published    *
 * by the Free Software Foundation, version 2.                               *
 *                                                                           *
 * This library is distributed in the hope that it will be useful, but       *
 * WITHOUT ANY WARRANTY; without even the implied warranty of                *
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU         *
 * Library General Public License for more details.                          *
 *                                                                           *
 * You should have received a copy of the GNU Library General Public         *
 * License along with this library; if not, write to the Free Software       *
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.                 *
 *                                                                           *
 \*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------*\
 *                                Changes                                    *
 *                                                                           *
 *                                                                           *
 *                                                                           *
 *                                                                           *
 *                                                                           *
 *                                                                           *
 \*---------------------------------------------------------------------------*/

// System declarations

#include <iostream>
#include <stdlib.h>
#include <math.h>

#include <GL/gl.h>

// Application declarations



// Class declarations

#include "TriangleAdjacencyGraph.h"


// Static Class Varible implementations: 


//----------------------------------------------------------------------

// Method: TriangleAdjacencyGraph

// Author: jbehr

// Date:   Tue Feb 15 18:16:59 2000

// Description:

//         Default Constructor

//----------------------------------------------------------------------

TriangleAdjacencyGraph::TriangleAdjacencyGraph (void)
{
  ;
}          

//----------------------------------------------------------------------

// Method: TriangleAdjacencyGraph

// Author: jbehr

// Date:   Tue Feb 15 18:16:59 2000

// Description:

//         Copy Constructor

//----------------------------------------------------------------------

TriangleAdjacencyGraph::TriangleAdjacencyGraph (const TriangleAdjacencyGraph &obj )
{
  cerr << "Run TriangleAdjacencyGraph copy constructor; not impl.\n" << endl;
}

//----------------------------------------------------------------------

// Method: ~TriangleAdjacencyGraph

// Author: jbehr

// Date:   Tue Feb 15 18:16:59 2000

// Description:

//         Destructor

//----------------------------------------------------------------------

TriangleAdjacencyGraph::~TriangleAdjacencyGraph (void )
{
  clear();
}

//----------------------------------------------------------------------

// Method: ~TriangleAdjacencyGraph

// Author: jbehr

// Date:   Tue Feb 15 18:16:59 2000

// Description:

//         Destructor

//----------------------------------------------------------------------

bool TriangleAdjacencyGraph::Triangle::verify(void)
{
  bool retCode = true;
  Triangle *neighbor[3];

  neighbor[0] = halfEdgeVec[0].twin ? halfEdgeVec[0].twin->triangle : 0;
  neighbor[1] = halfEdgeVec[1].twin ? halfEdgeVec[1].twin->triangle : 0;
  neighbor[2] = halfEdgeVec[2].twin ? halfEdgeVec[2].twin->triangle : 0;

  if ( ( neighbor[0] &&
	( (neighbor[0] == neighbor[1]) ||
	  (neighbor[0] == neighbor[2]) ) ) ||
      ( neighbor[1] &&
	( (neighbor[1] == neighbor[0]) ||
	  (neighbor[1] == neighbor[2]) ) ) ||
      ( neighbor[2] &&
	( (neighbor[2] == neighbor[0]) )   ||
	(neighbor[2] == neighbor[1]) ) ) {
    cerr << "Neighbor linked more than once" << endl;
    retCode = false;
  }

  if ( (halfEdgeVec[0].vertexStart() == halfEdgeVec[1].vertexStart()) ||
      (halfEdgeVec[0].vertexStart() == halfEdgeVec[2].vertexStart()) ||
      (halfEdgeVec[1].vertexStart() == halfEdgeVec[2].vertexStart()) ) {
    cerr << "Invalid collapsed Triangle" << endl;
    retCode = false;
  }

  if ( (halfEdgeVec[0].triangle != this) ||
      (halfEdgeVec[1].triangle != this) ||
      (halfEdgeVec[2].triangle != this) ) {
    cerr << "Invalid halfEdge->triangle pointer" << endl;
    retCode = false;
  }

  if ( (halfEdgeVec[0].next != &halfEdgeVec[1]) ||
      (halfEdgeVec[1].next != &halfEdgeVec[2]) ||
      (halfEdgeVec[2].next != &halfEdgeVec[0]) ) {
    cerr << "Edge next link error" << endl;
    retCode = false;
  }

  return retCode;
}

//----------------------------------------------------------------------

// Method: reserve

// Author: jbehr

// Date:   Tue Feb 15 18:16:59 2000

// Description:

//         

//----------------------------------------------------------------------

void TriangleAdjacencyGraph::reserve ( unsigned vertexNum, 
    unsigned triangleNum, 
    unsigned reserveEdges )
{
  unsigned i;

  _trianglePool.setChunkSize(triangleNum);
  _temporaryVector.resize(vertexNum); 

  if (reserveEdges > 0)
    for (i = 0; i < vertexNum; i++)
      _temporaryVector[i].reserve(reserveEdges);
}

//----------------------------------------------------------------------

// Method: verify

// Author: jbehr

// Date:   Tue Feb 15 18:16:59 2000

// Description:

//         

//----------------------------------------------------------------------

bool TriangleAdjacencyGraph::verify (void )
{
  bool retCode = true;
  unsigned int i, n;
  Triangle *triangle;
  int triangleState[4];
  int invalidTriangles = 0;
  int halfEdgeCount = 0;
  map< int, int > connectionMap;
  map< int, int >::iterator connectionI;
  int connectionCount;

  for (i = 0; i < 4; i++)
    triangleState[i] = 0;

  for (triangle = _validTriangleBag.first; triangle; 
      triangle = triangle->next) {
    if ( triangle->verify() && 
	(triangle->state >= 0) || (triangle->state <= 3) )
      triangleState[triangle->state]++;
    else
      invalidTriangles++;
  }

  cout << "nonmanifold split: " << _invalidTriangleBag.countElem() << endl;

  cout << invalidTriangles << endl;

  cout << "TriangleState: ";
  for (i = 0; i < 4; i++)
    cout << triangleState[i] << " ";
  cout << endl;

  if (invalidTriangles) {
    cout << "######################################################\n";
    cout << "invalid: " << invalidTriangles << endl;
    cout << "######################################################\n";
  }

  n = _temporaryVector.size();
  for (i = 0; i < n; i++) {
    connectionCount = _temporaryVector[i].size();

    halfEdgeCount += connectionCount;
    if (connectionMap.find(connectionCount) == connectionMap.end())
      connectionMap[connectionCount] = 1;
    else
      connectionMap[connectionCount]++;
  }
  for ( connectionI = connectionMap.begin();
      connectionI != connectionMap.end(); ++connectionI ) 
    cout << connectionI->first << '/' << connectionI->second << ' ';
  cout << endl;

  cout << "HalfEdgeCount: " << halfEdgeCount << endl;

  return retCode;
}

//----------------------------------------------------------------------

// Method: calcOptPrim

// Author: jbehr

// Date:   Tue Feb 15 18:16:59 2000

// Description:

//         

//----------------------------------------------------------------------

unsigned int TriangleAdjacencyGraph::calcOptPrim ( unsigned extIteration,
    bool doStrip, bool doFan, 
    unsigned minFanTriangles )
{
  int iteration = extIteration;
  bool sample = iteration > 1 ? true : false;
  bool checkRevOrder = sample;
  TriangleList degreeBag[4];
  TriangleList *fList = 0;
  int cost = 0, sampleCost = 0;
  int stripCost = 0, revCost = 0, fanCost = 0, triCost = 0;
  int bestCost = 0, worstCost = 0, lowDegree;
  unsigned int i, n;
  WalkCase walkCase = START;
  Triangle *triangle, *next;
  HalfEdge *twin = 0, *gateEdge = 0, *halfEdge = 0;
  bool doMainLoop = true;
  unsigned int seed = 1, bestSeed = 1;
  int mostDegree = 3;
  unsigned triangleLeft = _trianglePool.countElem();
  srand(1);

  if (doFan) {
    n = _temporaryVector.size();
    fanCost = 0;

    // find fans 

    for (i = 0; i < n; i++) 
      if ( (_temporaryVector[i].size() >= minFanTriangles) &&
	  (gateEdge = _temporaryVector[i][0].second) &&
	  (gateEdge->triangle->valid()) ) {
	for ( halfEdge = gateEdge->next->next->twin;
	    (halfEdge && halfEdge->triangle->valid() && (halfEdge != gateEdge));
	    halfEdge = halfEdge->next->next->twin )
	  ;
	if (halfEdge == gateEdge) {
	  // fan is closed; mark every triangle          

	  triangle = 0;
	  fList = new TriangleList;
	  for ( halfEdge = gateEdge;
	      !triangle || (halfEdge != gateEdge);
	      halfEdge = halfEdge->next->next->twin ) {
	    triangle = halfEdge->triangle;
	    _validTriangleBag.release(*triangle);
	    triangle->drop();
	    triangle->state = FAN_PART;
	    fList->add(*triangle);
	  }
	  _fanBag.push_back(Primitive(i,fList));
	  fanCost += (_temporaryVector[i].size() + 2);
	  triangleLeft -= _temporaryVector[i].size();
	}
      }
  }

  if (doStrip && iteration) {

    // push every triangle into the according degree bag

    degreeBag[mostDegree].paste(_validTriangleBag);
    for (triangle = degreeBag[mostDegree].first; triangle; triangle = next) {
      next = triangle->next;
      if (triangle->valid()) {
	if (triangle->state != mostDegree) {
	  degreeBag[mostDegree].release(*triangle);
	  _validTriangleBag.release(*triangle);
	  degreeBag[triangle->state].add( *triangle);
	}
      }
      else {
	cerr << "INVALID TRIANGLE IN VALID TRIANGLE BAG\n" << endl;
      }
    }

    for (iteration--; iteration >= 0; iteration--) {

      seed = iteration ? rand() : bestSeed;
      srand (seed);

      fList = 0;
      cost = 0;
      doMainLoop = true;
      walkCase = START;

      // run the main loop

      while (doMainLoop) {

	switch (walkCase) {
	  case START:      

	    stripCost = 0;
	    triangle = 0;

	    for (lowDegree = 1; lowDegree < 4; lowDegree++)
	      if ((degreeBag[lowDegree].empty() == false)) {
		if (sample) {
		  // pick a random triangle

		  n = degreeBag[lowDegree].countElem() - 1;
		  i = int(float(n) * rand()/float(RAND_MAX));
		  triangle = degreeBag[lowDegree].first;
                  while (i--) 
                     triangle = triangle->next;
		}
		else {
		  // pick the first triangle

		  triangle = degreeBag[lowDegree].first;
		}              
		break;
	      }

	    if (triangle) {

	      // create the new list

	      fList = new TriangleList;

	      // find the best neighbour

	      gateEdge = 0;
	      for (i = 0; i < 3; i++) 
		if ( (twin = triangle->halfEdgeVec[i].twin) && 
		    (twin->triangle->state > 0) ) {
		  if ( twin->next->next->twin &&
		      (twin->next->next->twin->triangle->state > 0) ) {
		    gateEdge = &triangle->halfEdgeVec[i];
		    break;
		  }
		  else {
		    if ( twin->next->twin &&
			(twin->next->twin->triangle->state > 0) )
		      gateEdge = &triangle->halfEdgeVec[i];
		    else {
		      if ((twin->triangle->state > 0))
			gateEdge = &triangle->halfEdgeVec[i];
		    }
		  }
		}

	      // release and store the first triangle

	      dropOutTriangle (*triangle,degreeBag);
	      fList->add(*triangle);
	      stripCost += 3;

	      // set the next step

	      if (gateEdge) {          
		walkCase = LEFT;
		stripCost++;
	      }
	      else 
		walkCase = FINISH;
	    }
	    else
	      doMainLoop = false;      
	    break;

	  case LEFT:
	    gateEdge = gateEdge->twin;
	    triangle = gateEdge->triangle;

	    // find the next gate

	    if (triangle->state == DEGREE_0) {
	      gateEdge = 0;
	      walkCase = FINISH;
	    }
	    else
	      if ( (twin = gateEdge->next->next->twin) && 
		  (twin->triangle->state > 0) ){
		gateEdge = gateEdge->next->next;
		stripCost++;
		walkCase = RIGHT;
	      }
	      else {
		gateEdge = gateEdge->next;
		stripCost += 2;
		walkCase = LEFT;
	      }

	    // store the current triangle

	    dropOutTriangle (*triangle,degreeBag);
	    fList->add(*triangle);
	    break;

	  case RIGHT:      
	    gateEdge = gateEdge->twin;
	    triangle = gateEdge->triangle;

	    // find the next gate

	    if (triangle->state == DEGREE_0) {
	      gateEdge = 0;
	      walkCase = FINISH;
	    }
	    else
	      if ( (twin = gateEdge->next->twin) && 
		  (twin->triangle->state > 0) ) {
		gateEdge = gateEdge->next;
		stripCost++;
		walkCase = LEFT;
	      }
	      else {
		gateEdge = gateEdge->next->next;
		stripCost += 2;
		walkCase = RIGHT;
	      }

	    // store the current triangle

	    dropOutTriangle (*triangle,degreeBag);
	    fList->add(*triangle);
	    break;

	  case FINISH:      
	    // try to reverse the strip

	    if ( checkRevOrder &&
		(revCost = calcStripCost(*fList,true)) &&
		(revCost < stripCost) ) {
	      _stripBag.push_back(Primitive(1,fList));
	      cost += revCost;
	    }
	    else {
	      _stripBag.push_back(Primitive(0,fList));
	      cost += stripCost;
	    }
	    walkCase = START;
	    fList = 0;
	    break;
	}  
      }

      if (sample) {
	sampleCost = cost + (degreeBag[0].countElem() * 3) + fanCost;
	if (!bestCost || (sampleCost < bestCost)) {
	  bestCost = sampleCost;
	  bestSeed = seed;
	}
	if (sampleCost > worstCost)
	  worstCost = sampleCost;

	cout << " cost/best/worst: " 
	  << sampleCost << '/' << bestCost << '/' << worstCost
	  << endl;
      }

      if (iteration) {
	// reinit the four degree bags

	degreeBag[mostDegree].paste(degreeBag[0]);
	n = _stripBag.size();
	for (i = 0; i < n; i++) {
	  degreeBag[mostDegree].paste(*_stripBag[i].second);
	  delete _stripBag[i].second;
	}
	_stripBag.clear();
	for ( triangle = degreeBag[mostDegree].first; triangle; 
	    triangle = next) {
	  next = triangle->next;
	  triangle->resetDegreeState(STRIP_PART);
	  if (triangle->valid()) {
	    if (triangle->state != mostDegree) {
	      degreeBag[mostDegree].release(*triangle);
	      degreeBag[triangle->state].add(*triangle);
	    }
	  }
	  else {
	    cerr << "INVALID TRIANGLE IN REINIT\n" << endl;
	    cerr << triangle->state << endl;
	  }
	}
      }
    }
  }
  else {    
    // push every valid triangle in degree 0; we don't strip anything

    degreeBag[0].paste(_validTriangleBag);
  }

  if (sample) {
    cerr << "range: " 
      << bestCost << '/' << worstCost << ' '
      << float(100 * (worstCost-bestCost))/float(bestCost) << '%'
      << endl;
  }

  // collect isolated triangles  

  degreeBag[0].paste(_invalidTriangleBag);  
  triCost = degreeBag[0].countElem() * 3;
  if (triCost) {
    fList = new TriangleList;  
    fList->paste(degreeBag[0]);
    _triBag.push_back(Primitive(0,fList));
  }

  return (cost + fanCost + triCost);
}                                                  

//----------------------------------------------------------------------

// Method: calcStripCost

// Author: jbehr

// Date:   Tue Feb 15 18:16:59 2000

// Description:

//         

//----------------------------------------------------------------------

int TriangleAdjacencyGraph::calcStripCost ( TriangleList &strip, bool rev )
{
  Triangle *triangle = rev ? strip.last : strip.first, *nextTriangle;
  HalfEdge *firstEdge, *halfEdge, *gate;
  WalkCase walkCase;
  int cost = 0;

  if (triangle) {
    cost = 3;
    if ((nextTriangle = rev ? triangle->prev : triangle->next)) {
      gate = findGateEdge(triangle,nextTriangle);
      firstEdge = gate->next->next;
      cost++;
      walkCase = LEFT;
      for ( triangle = nextTriangle; 
	  (nextTriangle = (rev ? triangle->prev : triangle->next));
	  triangle = nextTriangle ) {
	halfEdge = gate->twin;
	gate = findGateEdge(triangle,nextTriangle); 
	if (walkCase == RIGHT)
	  // RIGHT

	  if (halfEdge->next == gate) {
	    cost++;
	    walkCase = LEFT;
	  }
	  else {
	    // swap; walkCase stays RIGHT;

	    cost += 2;
	  }
	else
	  // LEFT

	  if (halfEdge->next->next == gate) {
	    cost++;
	    walkCase = RIGHT;
	  }
	  else {
	    // swap; walkCase stays LEFT;

	    cost += 2;
	  }
      }
    }
  }

  return cost;
}

//----------------------------------------------------------------------

// Method: fillPrimFromStrip

// Author: jbehr

// Date:   Tue Feb 15 18:16:59 2000

// Description:

//         

//----------------------------------------------------------------------

int TriangleAdjacencyGraph::fillIndexFromStrip ( std::vector<Index> &indexVec,
    TriangleList &strip, bool rev )
{
  Triangle *triangle = rev ? strip.last : strip.first, *nextTriangle;
  HalfEdge *firstEdge, *halfEdge, *gate;
  WalkCase walkCase;
  Index vertex;
  int cost = 0;

  if (triangle) {
    cost = 3;
    indexVec.reserve(32); // find better value

    indexVec.resize(3);
    if ((nextTriangle = (rev ? triangle->prev : triangle->next))) {
      cost++;
      gate = findGateEdge(triangle,nextTriangle);
      firstEdge = gate->next->next;
      indexVec.push_back(vertex = gate->twin->next->vertexEnd());

      walkCase = LEFT;
      for ( triangle = nextTriangle; 
	  (nextTriangle = (rev ? triangle->prev : triangle->next));
	  triangle = nextTriangle ) {
	halfEdge = gate->twin;
	gate = findGateEdge(triangle,nextTriangle); 
	if (walkCase == RIGHT)
	  // RIGHT

	  if (halfEdge->next == gate) {
	    indexVec.push_back(vertex = gate->twin->next->vertexEnd());
	    walkCase = LEFT;
	    cost++;
	  }
	  else {
	    // swap; walkCase stays RIGHT;

	    indexVec.back() = gate->vertexEnd();
	    indexVec.push_back(gate->vertexStart());              
	    indexVec.push_back(vertex = gate->twin->next->vertexEnd());
	    cost += 2;
	  }
	else
	  // LEFT

	  if (halfEdge->next->next == gate) {
	    indexVec.push_back(vertex = gate->twin->next->vertexEnd());
	    walkCase = RIGHT;
	    cost++;
	  }
	  else {
	    // swap; walkCase stays LEFT;

	    indexVec.back() = gate->vertexStart();
	    indexVec.push_back(gate->vertexEnd());
	    indexVec.push_back(vertex = gate->twin->next->vertexEnd());
	    cost += 2;
	  }
      }
    }
    else 
      firstEdge = &triangle->halfEdgeVec[0];      
    indexVec[0] = vertex = firstEdge->vertexStart();
    indexVec[1] = vertex = firstEdge->next->vertexStart();      
    indexVec[2] = vertex = firstEdge->next->next->vertexStart();
  }

  return cost;
}

//----------------------------------------------------------------------

// Method: fillPrimFromFan

// Author: jbehr

// Date:   Tue Feb 15 18:16:59 2000

// Description:

//         

//----------------------------------------------------------------------

int TriangleAdjacencyGraph::fillIndexFromFan( std::vector<Index> &indexVec,
    HalfEdge &firstEdge )
{
  int count = 0;
  HalfEdge *halfEdge(&firstEdge);
  HalfEdge *gateEdge = 0;

  if (halfEdge) {
    count = 3;
    indexVec.resize(2);
    indexVec[0] = halfEdge->vertexStart();
    indexVec[1] = halfEdge->vertexEnd();
    for ( gateEdge = halfEdge->next->next->twin;
	gateEdge != halfEdge;
	gateEdge = gateEdge->next->next->twin ) {
      indexVec.push_back(gateEdge->vertexEnd());
      count++;
    }
    indexVec.push_back(halfEdge->vertexEnd());
  }
  else {
    cerr << "Invalid fac in fillIndexFromFan()" << endl;
  }

  return count;
}

//----------------------------------------------------------------------

// Method: calcEdgeLines

// Author: jbehr

// Date:   Tue Feb 15 18:16:59 2000

// Description:

//         

//----------------------------------------------------------------------

int TriangleAdjacencyGraph::getPrimitive ( vector<Index> & indexVec, int type  )
{
  unsigned i = 0, n = 0;
  Triangle *triangle;
  std::vector<Primitive> *bag = 0;

  indexVec.clear();

  // fan

  if ( !bag && 
      (type == GL_TRIANGLE_FAN) || (!type && (n = _fanBag.size()))) {
    i = n - 1;
    bag = &_fanBag;
    fillIndexFromFan ( indexVec, 
	*_temporaryVector[_fanBag[i].first][0].second );
    type = GL_TRIANGLE_FAN;
  }

  // strip

  if ( !bag &&
      (type == GL_TRIANGLE_STRIP) || (!type && (n = _stripBag.size()))) {
    i = n - 1;
    bag = &_stripBag;
    fillIndexFromStrip ( indexVec,
	*_stripBag[i].second,
	_stripBag[i].first ? true : false );
    type = GL_TRIANGLE_STRIP;
  }

  // tri

  if (!bag &&
      (type == GL_TRIANGLES) || (!type && (n = _triBag.size()))) {
    bag = &_triBag;
    if (_triBag[0].second->empty() == false) {
      n = _triBag[0].second->countElem() * 3;
      indexVec.resize(n);
      i = 0;
      for ( triangle = _triBag[0].second->first; triangle; 
	  triangle = triangle->next ) {
	indexVec[i++] = triangle->halfEdgeVec[0].vertexStart();
	indexVec[i++] = triangle->halfEdgeVec[1].vertexStart();
	indexVec[i++] = triangle->halfEdgeVec[2].vertexStart();
      }
    }
    type = GL_TRIANGLES;
    i = 0;
  }

  if (bag) {
    _invalidTriangleBag.paste(*((*bag)[i].second));
    delete (*bag)[i].second;
    if (i)
      bag->resize(i);    
    else
      bag->clear();
  }
  else
    type = 0;

  return type;
}

//----------------------------------------------------------------------

// Method: calcEdgeLines

// Author: jbehr

// Date:   Tue Feb 15 18:16:59 2000

// Description:

//         

//----------------------------------------------------------------------

int TriangleAdjacencyGraph::calcEgdeLines ( vector<Index> & indexVec, bool codeBorder )
{
  unsigned int i, nN, j, nE, halfEdgeCount = 0;
  Index startVertexIndex, endVertexIndex;
  HalfEdge *halfEdge;
  bool isBorder;

  indexVec.clear();
  nN = _temporaryVector.size();
  for (i = 0; i < nN; i++) {
    nE = _temporaryVector[i].size();
    for ( j = 0; j < nE; j++) {      
      halfEdge = _temporaryVector[i][j].second;
      startVertexIndex = halfEdge->vertexStart();
      endVertexIndex = halfEdge->vertexEnd();

      if ((isBorder = (halfEdge->twin == 0)) || (startVertexIndex <
	    endVertexIndex)) {
	indexVec.push_back(startVertexIndex);
	indexVec.push_back(endVertexIndex);
	if (codeBorder)
	  indexVec.push_back(isBorder ? 0 : 1);
	halfEdgeCount++;
      }
    }
  }

  return halfEdgeCount;
}

//----------------------------------------------------------------------

// Method: 

// Author: jbehr

// Date:   Tue Feb 15 18:16:59 2000

// Description:

//         

//----------------------------------------------------------------------

void TriangleAdjacencyGraph::clear(void)
{
  unsigned int i,n;

  _temporaryVector.clear();
  _trianglePool.clear();

  n = _stripBag.size();
  for (i = 0; i < n; i++)
    delete _stripBag[i].second;
  _stripBag.clear();

  n = _fanBag.size();
  for (i = 0; i < n; i++)
    delete _fanBag[i].second;
  _fanBag.clear();

  n = _triBag.size();
  for (i = 0; i < n; i++)
    delete _triBag[i].second;
  _triBag.clear();
}