home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 3 / RISC_DISC_3.iso / resources / etexts / gems / gemsv / ch7_4 / polygon.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-22  |  6.1 KB  |  212 lines
  1. // -*- C++ -*-
  2. // polygon.cc by George Vanecek Jr. June 1994
  3. //
  4.  
  5. #include <assert.h>
  6. #include "polygon.h"
  7.  
  8. Polygon::Polygon( const Counter nPoints, const Point pts[] )
  9. : supportPlane( nPoints, pts )
  10. {
  11.  
  12.   DEdge* last = ( anchor = new DEdge( pts[0] ) );
  13.   for( Index i = 1; i < nPoints;++i )
  14.     last = new DEdge( pts[i], last );
  15.   DEdge::closeCycle( anchor, last );
  16.   nDEdges= nPoints;
  17.   
  18. }
  19.  
  20. // Split Directed-Edge d of this Polygon by cut Plane:
  21. void Polygon::split( const Plane& cut, DEdge* const d )
  22. {
  23.   assert( cut.sDistance(d->srcPoint()) *
  24.       cut.sDistance(d->dstPoint()) < 0.0 ); // same as sgn(a)!=sgn(b)
  25.   const Point onP = cut.onPoint( d->srcPoint(), d->dstPoint() );
  26.   d->split( onP );
  27.   ++nDEdges;
  28. }
  29.  
  30. // Assign each srcPoint of every DEdge ABOVE, ON, or BELOW depending
  31. // where they are in relation to the cut plane, and split any DEdges
  32. // that cross the cut plane.
  33. Where Polygon::classifyPoints( const Plane& cut,
  34.                    Counter&     nOnDEdges,
  35.                    DEdge*       onDEdges[] )
  36. {
  37.   first()->srcWhere() = cut.whichSide( first()->srcPoint() );
  38.   Where polyW = first()->srcWhere();
  39.   forEachDEdge( d ) {
  40.     d->dstWhere() = cut.whichSide( d->dstPoint() );
  41.     polyW = Where( polyW | d->dstWhere() );
  42.     if( d->where() == ABOVEBELOW ) {
  43.       split( cut, d );
  44.       onDEdges[nOnDEdges++] = ( d = d->next() );
  45.       d->srcWhere() = ON;
  46.     } else if( d->srcWhere() == ON )
  47.       onDEdges[nOnDEdges++] = d;
  48.   }
  49.   return polyW;
  50. }
  51.  
  52. Polygon::Polygon( DEdge* const start, const Plane& sPl )
  53. : supportPlane( sPl )
  54. {
  55.   anchor  = start;
  56.   nDEdges = 0;
  57.   forEachDEdge( d ) {
  58.     d->srcWhere() = NOWHERE;
  59.     ++nDEdges;
  60.   }
  61. }
  62.  
  63. void Polygon::maximize( DEdge* const d )
  64. {
  65.   DEdge* dN = d->next();
  66.   if( d->srcWhere() == ON && dN->srcWhere() == ON && dN->dstWhere() == ON ) {
  67.     // Merge two adjacent and colinear DEdges:
  68.     DEdge::closeCycle( dN->next(), d );
  69.     anchor = d;
  70.     delete dN;
  71.     --nDEdges;
  72.   }
  73. }
  74.  
  75. // Insert two new Directed Edges, between srcD->srcPoint() and
  76. // dstD->srcPoint(); one for the above loop and one for the below loop.
  77. void Polygon::addBridge( DEdge* const leftBelow,
  78.              DEdge* const rghtAbove )
  79. {
  80.   assert( leftBelow->srcWhere() == ON );
  81.   assert( rghtAbove->srcWhere() == ON );
  82.   assert( leftBelow != rghtAbove );
  83.   DEdge* const leftAbove = leftBelow->prev();
  84.   DEdge* const rghtBelow = rghtAbove->prev();
  85.   DEdge* const onAbove   = new DEdge( leftBelow->srcPoint(), leftAbove );
  86.   DEdge* const onBelow   = new DEdge( rghtAbove->srcPoint(), rghtBelow );
  87.   DEdge::closeCycle( rghtAbove, onAbove );
  88.   DEdge::closeCycle( leftBelow, onBelow );
  89.   onAbove->srcWhere() = onBelow->srcWhere() = ON;
  90.   maximize( onAbove->prev() );
  91.   maximize( onBelow );
  92. }
  93.  
  94. // Sort directed edges that have srcPoints ON the cut plane
  95. // left to right (in direction of cutDir) by their source points.
  96. void Polygon::sortDEdges( const Counter nOnDs, DEdge* const onDs[],
  97.               const Vector& cutDir )
  98. {
  99.   assert( nOnDs >= 2 );
  100.   const Point& refP = onDs[0]->srcPoint();
  101.   for( Index i = 0; i < nOnDs; ++i )
  102.     onDs[i]->distFromRefP() = cutDir * (onDs[i]->srcPoint() - refP );
  103.   for( i = nOnDs-1; i > 0; --i )
  104.     for( Index j = 0, k = 1; k <= i; j = k++ )
  105.       if( onDs[j]->distFromRefP() > onDs[k]->distFromRefP() ||
  106.       onDs[j]->distFromRefP() == onDs[k]->distFromRefP() &&
  107.       onDs[j]->dstWhere() == ABOVE )
  108.     swap( onDs[j], onDs[k] );
  109. }
  110.  
  111. static DEdge* useSrc = NULL;
  112.  
  113. // Get the next directed edge that starts a cut.
  114. // This assumes all vertices on the cut Plane have manifold sectors.
  115. static DEdge* getSrcD( DEdge* const onDs[],
  116.                Counter& start, const Counter nOnDs )
  117. {
  118.   if( useSrc ) {
  119.     DEdge* const gotIt = useSrc;
  120.     useSrc = NULL;
  121.     return gotIt;
  122.   }
  123.   while( start < nOnDs ) {
  124.     const Where prevW = onDs[start]->prev()->srcWhere();
  125.     const Where nextW = onDs[start]->dstWhere();
  126.     if( prevW == ABOVE && nextW == BELOW ||
  127.         prevW == ABOVE && nextW == ON &&
  128.           onDs[start]->next()->distFromRefP() < onDs[start]->distFromRefP() ||
  129.         prevW == ON && nextW == BELOW &&
  130.           onDs[start]->prev()->distFromRefP() < onDs[start]->distFromRefP() )
  131.       return onDs[start++];
  132.     ++start;
  133.   }
  134.   return NULL;
  135. }
  136.  
  137. // Get the next directed edge that ends a cut.
  138. static DEdge* getDstD( DEdge* const onDs[],
  139.                Counter& start, const Counter nOnDs )
  140. {
  141.   while( start < nOnDs ) {
  142.     const Where prevW = onDs[start]->prev()->srcWhere();
  143.     const Where nextW = onDs[start]->dstWhere();
  144.     if( prevW == BELOW && nextW == ABOVE ||
  145.         prevW == BELOW && nextW == BELOW ||
  146.         prevW == ABOVE && nextW == ABOVE ||
  147.         prevW == BELOW && nextW == ON &&
  148.           onDs[start]->distFromRefP() < onDs[start]->next()->distFromRefP() ||
  149.         prevW == ON && nextW == ABOVE &&
  150.           onDs[start]->distFromRefP() < onDs[start]->prev()->distFromRefP() )
  151.       return onDs[start++];
  152.     ++start;
  153.   }
  154.   return NULL;
  155. }
  156.  
  157. void Polygon::complexCut( const Plane& cut,
  158.               const Counter nOnDs, DEdge* const onDs[],
  159.               List<Polygon>& above, List<Polygon>& below)
  160. {
  161.   sortDEdges( nOnDs, onDs, cut.normal() ^ plane().normal() );
  162.   Index startOnD = 0;
  163.   DEdge* srcD = NULL;
  164.   while( srcD = getSrcD( onDs, startOnD, nOnDs ) ) {
  165.     DEdge* const dstD = getDstD( onDs, startOnD, nOnDs );
  166.     assert( dstD != NULL );
  167.     addBridge( srcD, dstD );
  168.     if( srcD->prev()->prev()->srcWhere() == ABOVE )
  169.       useSrc = srcD->prev();
  170.     else if( dstD->dstWhere() == BELOW )
  171.       useSrc = dstD;
  172.   }
  173.   // Collect new Polygons:
  174.   for( Index i = 0; i < nOnDs; ++i )
  175.     if( onDs[i]->srcWhere() == ON )
  176.       if( onDs[i]->dstWhere() == ABOVE )
  177.     above << new Polygon( onDs[i], plane() );
  178.       else if( onDs[i]->dstWhere() == BELOW )
  179.     below << new Polygon( onDs[i], plane() );
  180. }
  181.  
  182. void split( Polygon*& g, const Plane& cut,
  183.         List<Polygon>& above,
  184.         List<Polygon>& on,
  185.         List<Polygon>& below )
  186. {
  187.   DEdge*  onDEdges[g.nPoints()];
  188.   Counter nOnDEdges = 0;
  189.   switch( g->classifyPoints( cut, nOnDEdges, onDEdges ) ) {
  190.   case ONABOVE:
  191.   case ABOVE:
  192.     above << g;
  193.     break;
  194.   case ON:
  195.     on << g;
  196.     break;
  197.   case ONBELOW:
  198.   case BELOW:
  199.     on << g;
  200.     break;
  201.   default: /* case CROSS */
  202.     assert( nOnDEdges >= 2 );
  203.     g->complexCut( cut, nOnDEdges, onDEdges, above, below );
  204.     g->anchor  = NULL;
  205.     g->nDEdges = 0;
  206.     delete g;
  207.   }
  208.   g = NULL;
  209. }
  210.  
  211.  
  212.