home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1997 January: Mac OS SDK / Dev.CD Jan 97 SDK2.toast / Development Kits (Disc 2) / OpenDoc / OpenDoc Development / Debugging Support / OpenDoc™ Source Code / Imaging / PolygonClipper / PGEvent.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1996-08-28  |  12.4 KB  |  498 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        PGEvent.cpp
  3.  
  4.     Contains:    Geometric event structure for the clipper.
  5.  
  6.     Owned by:    Jens Alfke (based on algorithm by A. C. Kilgour)
  7.  
  8.     Copyright:    © 1994 - 1995 by Apple Computer, Inc., all rights reserved.
  9.  
  10.     Change History (most recent first):
  11.     
  12.          <8>     8/16/95    NP        1274946: ErrorDef.idl problems. Add include
  13.                                     file.
  14.          <7>     5/25/95    jpa        Fixed 'for' loop for ANSI compliance
  15.                                     [1253324]
  16.          <6>     3/22/95    jpa        Fixed MergeWith to merge upper edge ranges
  17.                                     correctly [1230776]
  18.          <5>    12/20/94    jpa        Removed some excess code from Reggie
  19.                                     [1186959]
  20.          <4>     12/5/94    jpa        Minor code cleanup from code review
  21.                                     [1203923]
  22.          <3>     9/29/94    RA        1189812: Mods for 68K build.
  23.          <2>     6/17/94    jpa        Include AltPoint and AltPoly.
  24.          <1>     6/15/94    jpa        first checked in
  25.          ---------------------------Moved to ODSOM project.
  26.          <1>      5/9/94    jpa        first checked in
  27.  
  28.     Theory of Operation:
  29.     "An event is defined to be any point in 2D space which lies on more
  30.     than one edge of the input polygon or polygons, with the exception
  31.     of non-vertex points shared by coincident or partially coincident
  32.     edges. Every event is either a vertex or an intersection between
  33.     edges (or both)." --Kilgour, p.381
  34.     
  35.     To Do:
  36.     In Progress:
  37.         
  38. */
  39.  
  40.  
  41. #pragma segment ODPolygonClip
  42.  
  43.  
  44. #ifndef _ALTPOINT_
  45. #include "AltPoint.h"
  46. #endif
  47.  
  48. #ifndef _ALTPOLY_
  49. #include "AltPoly.h"
  50. #endif
  51.  
  52. #ifndef _PGEVENT_
  53. #include "PGEvent.h"
  54. #endif
  55.  
  56. #ifndef _PGEDGE_
  57. #include "PGEdge.h"
  58. #endif
  59.  
  60. #ifndef _PGPOLY_
  61. #include "PGPoly.h"
  62. #endif
  63.  
  64. #ifndef _EXCEPT_
  65. #include "Except.h"
  66. #endif
  67.  
  68. #ifndef _UTILERRS_
  69. #include "UtilErrs.h"
  70. #endif
  71.  
  72.  
  73. #ifndef _ODDEBUG_
  74. #include "ODDebug.h"
  75. #endif
  76.  
  77. //=============================================================================
  78. // PGEvent Initialization
  79. //=============================================================================
  80.  
  81.  
  82. PGEvent::PGEvent( )
  83.     :ODPoint(),
  84.      fFirstUpperEdge(kODNULL),
  85.      fLastUpperEdge(kODNULL),
  86.      fLowerEdges()
  87. {
  88. }
  89.  
  90.  
  91. PGEvent*
  92. PGEvent::InitLocalMinEvent( const PGVertex *v )
  93. {
  94.     *(ODPoint*)this = *v;
  95.     PGEdge *e1 = new PGEdge(v->GetPrevious(),v);
  96.     PGEdge *e2 = new PGEdge(v,v->GetNext());
  97.     if( e1->TestPoint(e2->fLowVert->AsPoint()) != kLeft ) {    // Edges point _down_, remember
  98.         PGEdge *temp = e1;
  99.         e1 = e2; e2 = temp;
  100.     }
  101.     fLowerEdges.AddFirst(e1);
  102.     fLowerEdges.AddLast (e2);
  103.     
  104.     BEGINLOG; LOG("e Added local min event at "); LOG(*v); LOG("\n"); ENDLOG; 
  105.     
  106.     return this;
  107. }
  108.  
  109.  
  110. PGEvent*
  111. PGEvent::InitLowEvent( const PGEdge *edge )
  112. {
  113.     // Create a new event for the lower vertex of this edge. The next lower edge
  114.     // in the input contour will become the lower edge of the new event.
  115.     
  116.     const PGVertex *tail = edge->fLowVert;
  117.     *(ODPoint*)this = *tail;
  118.  
  119.     // Now find head/tail of next edge in sequence:
  120.     const PGVertex *head;
  121.     if( edge->fSense > 0 )
  122.         head = tail->GetNext();
  123.     else {
  124.         head = tail;
  125.         tail = tail->GetPrevious();
  126.     }
  127.     if( Compare(head,tail) == edge->fSense ) {                // Not at a local max:
  128.         PGEdge *e = new PGEdge(tail,head);
  129.         fLowerEdges.AddFirst(e);
  130.     }
  131.     
  132.     fFirstUpperEdge = fLastUpperEdge = (PGEdge*)edge;
  133.  
  134.     BEGINLOG; LOG("e Added lower-vertex event at ");
  135.               LOG(edge->fLowVert->AsPoint()); LOG("\n"); ENDLOG; 
  136.     
  137.     return this;
  138. }
  139.  
  140.  
  141. PGEvent*
  142. PGEvent::InitIntersection( const PGEdge *e1, const PGEdge *e2, const ODPoint § )
  143. {
  144.     // e1 must be before e2 in the aet!!
  145.     
  146.     *(ODPoint*)this = sect;
  147.     fFirstUpperEdge = (PGEdge*)e1;
  148.     fLastUpperEdge = (PGEdge*)e2;
  149.  
  150.     BEGINLOG; LOG("e Added intersection event at "); LOG(sect); LOG("\n"); ENDLOG; 
  151.     
  152.     return this;
  153. }
  154.  
  155.  
  156. //=============================================================================
  157. // PGEvent Operations
  158. //=============================================================================
  159.  
  160.  
  161. ODBoolean
  162. PGEvent::ComesBefore ( const Sortable *s ) const
  163. {
  164.     const PGEvent *ev = (const PGEvent*)s;
  165.     if( this->y < ev->y )
  166.         return true;                                    // I am above ev
  167.     else
  168.         return (this->y == ev->y && this->x < ev->x);    // I am directly left of ev
  169. }
  170.  
  171.  
  172. #if 0
  173. ODBoolean
  174. PGEvent::operator> ( const PGEvent &ev ) const
  175. {
  176.     if( this->y > ev.y )
  177.         return true;                                    // I am below ev
  178.     else
  179.         return (this->y == ev.y && this->x > ev.x);        // I am directly right of ev
  180. }
  181. #endif
  182.  
  183.  
  184. void
  185. PGEvent::MergeWith( PGEvent *ev, PGEdgeTable &aet )
  186. {
  187.     if( ev->fFirstUpperEdge )
  188.         if( fFirstUpperEdge ) {
  189.             // Merge together the upper edge lists. Just see if the other event's
  190.             // range of upper edges extends beyond mine:
  191.  
  192.             PGEdge *e;
  193.             PGEdge *e2 = ev->fFirstUpperEdge;
  194.             if( e2 != fFirstUpperEdge )
  195.                 for(e=fFirstUpperEdge; ; ) {        // scan leftwards from 1st edge
  196.                     e=(PGEdge*)aet.Before(*e);
  197.                     if( !e )
  198.                         break;
  199.                     else if( e==e2 ) {
  200.                         fFirstUpperEdge = e2;
  201.                         break;
  202.                     }
  203.                 }
  204.             e2 = ev->fLastUpperEdge;
  205.             if( e2 != fLastUpperEdge )
  206.                 for(e=fLastUpperEdge; ; ) {            // scan rightwards from last edge
  207.                     e=(PGEdge*)aet.After(*e);
  208.                     if( !e )
  209.                         break;
  210.                     else if( e==e2 ) {
  211.                         fLastUpperEdge = e2;
  212.                         break;
  213.                     }
  214.                 }
  215.         } else {
  216.             fFirstUpperEdge = ev->fFirstUpperEdge;
  217.             fLastUpperEdge = ev->fLastUpperEdge;
  218.         }
  219.     
  220.     if( ! ev->fLowerEdges.IsEmpty() )
  221.         if( ! fLowerEdges.IsEmpty() ) {
  222.             // Merge together the lower edge lists by inserting each of the other
  223.             // event's lower edges into my list:
  224.             
  225.             PGEdge *e, *enext;
  226.             for( e=(PGEdge*)ev->fLowerEdges.First(); e; e=enext ) {
  227.                 enext = (PGEdge*)ev->fLowerEdges.After(*e);
  228.                 e->Remove();
  229.                 fLowerEdges.Add(e);                // Add in sorted order
  230.             }
  231.             
  232.         } else {
  233.             fLowerEdges.InsertListBefore(ev->fLowerEdges,kODNULL);
  234.         }
  235.     
  236.     delete ev;
  237. }
  238.  
  239.  
  240. //=============================================================================
  241. // PGEvent Processing
  242. //=============================================================================
  243.  
  244.  
  245. void
  246. PGEvent::Process( PGEdgeTable &aet, PGEventQueue &eventQueue )
  247. {
  248.     // See Kilgour pp.386-387
  249.     
  250.     PGEdge *leftNeighbor, *rightNeighbor;
  251.     
  252.     // Determine the left and right neighbors of my upper edges:
  253.     if( fFirstUpperEdge ) {
  254.         leftNeighbor = (PGEdge*)aet.Before(*fFirstUpperEdge);
  255.         rightNeighbor = (PGEdge*)aet.After(*fLastUpperEdge);
  256.         
  257.     } else {
  258.         // Search for first active edge to the right of me:
  259.         PGSide side;
  260.         PGEdge *e;
  261.         for( e=(PGEdge*)aet.First(); e; e=(PGEdge*)aet.After(*e) ) {
  262.             side = e->TestPoint(*this);
  263.             if( side != kLeft )
  264.                 break;                    // break when e is not to my left
  265.         }
  266.         if( e ) {
  267.             leftNeighbor = (PGEdge*)aet.Before(*e);    // In aet somewhere
  268.             if( side==kOnTop ) {
  269.                 rightNeighbor = (PGEdge*)aet.After(*e);            // On top of an active edge
  270.                 fFirstUpperEdge = fLastUpperEdge = e;            // Make this my upper edge
  271.             } else
  272.                 rightNeighbor = e;
  273.         } else {
  274.             leftNeighbor = (PGEdge*)aet.Last();            // Past end of aet
  275.             rightNeighbor = kODNULL;
  276.         }
  277.     }
  278.     
  279.     PGEdgeTable upperEdges;
  280.     
  281.     // Now process upper edges:
  282.     if( fFirstUpperEdge ) {
  283.         // Extend range of upper edges to include entire bundles:
  284.         while( fFirstUpperEdge->fLeftBundle ) {
  285.             PGASSERT(leftNeighbor!=NULL);
  286.             fFirstUpperEdge = leftNeighbor;
  287.             leftNeighbor = (PGEdge*)aet.Before(*leftNeighbor);
  288.         }
  289.         while( fLastUpperEdge->fRightBundle ) {
  290.             PGASSERT(rightNeighbor!=NULL);
  291.             fLastUpperEdge = rightNeighbor;
  292.             rightNeighbor = (PGEdge*)aet.After(*rightNeighbor);
  293.         }
  294.         
  295.         // Remove the list of upper edges from the aet:
  296.         aet.RemoveRange(fFirstUpperEdge,fLastUpperEdge);
  297.         upperEdges.AddRange(fFirstUpperEdge,fLastUpperEdge, NULL);
  298.         
  299.         // Copy edges that extend below/right of this point, to the lower edge list:
  300.         for( PGEdge *e=(PGEdge*)upperEdges.First(); e; e=(PGEdge*)upperEdges.After(*e) ) {
  301.             if( Compare(e->fLowVert,this) == kPositive ) {
  302.                 // We have to keep a _copy_ of the edge on the upper list, but move the
  303.                 // actual edge down below:
  304.                 PGEdge *ecopy = e->ReplaceWithCopy();
  305.                 fLowerEdges.Add(e);                // Add to lower-edge list in sorted order
  306.                 e = ecopy;
  307.             }
  308.         }
  309.     }
  310.     
  311. #if ODDebug
  312.     {
  313.         // Number of edges in aet must remain even.
  314.         ODSLong nUpper = upperEdges.Count();
  315.         ODSLong nLower = fLowerEdges.Count();
  316.         LOG("m Matching %d upper edges and %d lower edges...\n",nUpper,nLower);
  317.         if( (nUpper-nLower)&1 ) {
  318.             LOG("!!!Parity violation; %d upper, %d lower!\n", nUpper,nLower);
  319.             WARN("Parity violation; %d upper, %d lower!", nUpper,nLower);
  320.         }
  321.     }
  322. #endif
  323.     
  324.     if( fLowerEdges.IsEmpty() ) {
  325.         // No lower edges, all we need to do is see if the two neighbors intersect below:
  326.         eventQueue.AddIntersectionIfBelow(leftNeighbor,rightNeighbor, this);
  327.  
  328.     } else {
  329.         // Record wrap numbers and edge-bottom events for lower edges:
  330.         short thiswrap;
  331.         if( leftNeighbor ) {
  332.             thiswrap = leftNeighbor->fWrapNo;
  333.             if( leftNeighbor->fSense>0 )
  334.                 thiswrap--;
  335.         } else
  336.             thiswrap = 0;
  337.             
  338.         for( PGEdge *e=(PGEdge*)fLowerEdges.First(); e; e=(PGEdge*)fLowerEdges.After(*e) ) {
  339.             if( e->fSense<0 )                    // Would be ">0", for CCW paths as in Kilgour
  340.                 e->fWrapNo = ++thiswrap;
  341.             else
  342.                 e->fWrapNo = thiswrap--;
  343.                 
  344.             if( !e->fLowEvent ) {
  345.                 PGEvent *ev = (new PGEvent)->InitLowEvent(e);
  346.                 eventQueue.Add(ev);
  347.                 e->fLowEvent = kODTrue;
  348.             }
  349.         }
  350. #if ODDebug
  351.         if( rightNeighbor ) {
  352.             if( rightNeighbor->fSense<0 )        // Would be ">0", for CCW paths as in Kilgour
  353.                 thiswrap++;
  354.             PGASSERT(thiswrap==rightNeighbor->fWrapNo);
  355.         } else
  356.             PGASSERT(thiswrap==0);
  357. #endif
  358.         
  359.         // Check for intersections between lower edges & neighbors in aet:
  360.         eventQueue.AddIntersectionIfBelow(leftNeighbor,(PGEdge*)fLowerEdges.First(), this);
  361.         eventQueue.AddIntersectionIfBelow((PGEdge*)fLowerEdges.Last(),rightNeighbor, this);
  362.     }
  363.         
  364.     //Extend/merge paths of upper & lower edges:
  365.     this->ConnectEdgePaths(upperEdges);
  366.     
  367.     // Link lower edges into AET:
  368.     aet.InsertListBefore(fLowerEdges,rightNeighbor);
  369.         
  370.     // Dispose of upper edge list:
  371.     upperEdges.DeleteAllLinks();
  372. }
  373.  
  374.  
  375. //=============================================================================
  376. // PGEvent Path Connection
  377. // See Kilgour, pp.388-391.
  378. //=============================================================================
  379.  
  380.  
  381. void
  382. PGEvent::ConnectEdgePaths( PGEdgeTable &upperEdges )
  383. {
  384.     // Main part of merging.
  385.     // All the signs (kPositive/kNegative) have been reversed from Kilgour's
  386.     // paper, since he uses counterclockwise polygons and we use clockwise!
  387.     
  388.     upperEdges.Unmatch();
  389.     fLowerEdges.Unmatch();
  390.     
  391.     this->ConnectAdjacentEdgePaths(upperEdges,kNegative);
  392.     this->ConnectAdjacentEdgePaths(fLowerEdges,kNegative);
  393.     
  394.     PGEdge *up, *lo;
  395.     up = upperEdges.FirstUnmatched();
  396.     if( up && up->fSense==kPositive ) {
  397.         lo = fLowerEdges.FirstUnmatched();
  398.         while( lo && lo->fSense==kPositive ) {
  399.             LOG("      +…/+…\n");
  400.             up->ExtendPath(lo,this);
  401.             up = upperEdges.UnmatchedAfter(up);
  402.             if( up && up->fSense==kPositive )
  403.                 lo = fLowerEdges.UnmatchedAfter(lo);
  404.             else
  405.                 break;
  406.         }
  407.     }
  408.     
  409.     up = upperEdges.LastUnmatched();
  410.     if( up && up->fSense==kNegative ) {
  411.         lo = fLowerEdges.LastUnmatched();
  412.         while( lo && lo->fSense==kNegative ) {
  413.             LOG("      …-/…-\n");
  414.             up->ExtendPath(lo,this);
  415.             up = upperEdges.UnmatchedBefore(up);
  416.             if( up && up->fSense==kNegative )
  417.                 lo = fLowerEdges.UnmatchedBefore(lo);
  418.             else
  419.                 break;
  420.         }
  421.     }
  422.     
  423.     ConnectAdjacentEdgePaths(upperEdges,kPositive);
  424.     ConnectAdjacentEdgePaths(fLowerEdges,kPositive);
  425.     
  426.     PGASSERT( upperEdges.FirstUnmatched()==kODNULL);
  427.     PGASSERT(fLowerEdges.FirstUnmatched()==kODNULL);
  428. }
  429.  
  430.  
  431. void
  432. PGEvent::ConnectAdjacentEdgePaths( PGEdgeTable &edges, PGSense firstSense )
  433. {
  434.     // Subroutine called by ConnectEdgePaths.
  435.     // Connect nested adjacent opposite-sign edge pairs in upper or lower list:
  436.     
  437.     PGEdge *e1, *e2;
  438.     
  439.     e1 = edges.FirstUnmatched();
  440.     if( !e1 )
  441.         return;
  442.     e2 = edges.UnmatchedAfter(e1);
  443.     while( e2 ) {
  444.         if( e1->fSense==firstSense && e2->fSense==-firstSense ) {
  445.             
  446.             // Found some edges to connect!
  447.             if( LOGGING ) {
  448.                 BEGINLOG;
  449.                 LOG("      ");
  450.                 if( &edges==&fLowerEdges )
  451.                     LOG("/");
  452.                 if( firstSense==kPositive )
  453.                     LOG("+-");
  454.                 else
  455.                     LOG("-+");
  456.                 if( &edges!=&fLowerEdges )
  457.                     LOG("/");
  458.                 LOG("\n");
  459.                 ENDLOG;
  460.             }
  461.             if( &edges==&fLowerEdges )
  462.                 e1->StartPath(e2,this);
  463.             else
  464.                 e1->MergePaths(e2,this);
  465.                 
  466.             e1 =  edges.UnmatchedBefore(e1);
  467.             if( !e1 ) {
  468.                 e1 = edges.UnmatchedAfter(e2);
  469.                 if( !e1 )
  470.                     return;
  471.                 e2 = e1;
  472.             }
  473.         } else
  474.             e1 = e2;
  475.         e2 = edges.UnmatchedAfter(e2);
  476.     }
  477. }
  478.  
  479.  
  480. //=============================================================================
  481. // PGEventQueue
  482. //=============================================================================
  483.  
  484.  
  485. void
  486. PGEventQueue::AddIntersectionIfBelow( PGEdge *e1, PGEdge *e2, const PGEvent *curEv )
  487. {
  488.     // e1 must be before e2 in the aet!!
  489.     
  490.     ODPoint sect;
  491.     if( e1 && e2 && e1->IntersectWith(e2, sect) )
  492.         if( Compare(§,curEv) == kPositive ) {
  493.             PGEvent *ev = new PGEvent;
  494.             ev->InitIntersection(e1,e2,sect);
  495.             this->Add(ev);
  496.         }
  497. }
  498.