home *** CD-ROM | disk | FTP | other *** search
/ AP Professional Graphics CD-ROM Library / AP Professional Graphics CD-ROM Library.iso / pc / unix / appendix / gemsiii / exttest / exthit.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-03-17  |  7.7 KB  |  292 lines
  1. /******************************************************************
  2. exthit.C
  3.  
  4. This code implements a C++ class for fast n-dimensional extent
  5. overlap checking. An instance of the class is initialized with a
  6. call to the constructor. For details on the usage of the ExtHit
  7. class see the header for the ExtHit header file
  8.  
  9. Authors: Len Wanger and Mike Fusco
  10.          SimGraphics Engineering
  11. ******************************************************************/
  12.  
  13. #ifndef _EXTHIT_H
  14. #include "exthit.h"
  15. #endif
  16.  
  17. #include <stdlib.h>
  18.  
  19. static int dim;
  20.  
  21. /******************************************************************
  22.   ExtHit - Class constructor
  23.  
  24.   Inputs:
  25.     size:    Maximum number of extents that can be held by this instance.
  26.  
  27.   Outputs:
  28.     None.
  29. ******************************************************************/
  30. ExtHit::ExtHit (int size)
  31. {
  32.   numColRecs = 0;
  33.   maxSize = size;
  34.   activeList = NULL;
  35.  
  36.   // Allocate internal tables
  37.   collideList  = new CollideRecord[size];
  38.   overlapList  = new MinMaxRecordPtr[2*size];
  39.   overlapTable = (BOOL *) calloc ( (size*size), sizeof(BOOL) );
  40. }
  41.  
  42. /******************************************************************
  43.   ~ExtHit - Class destructor
  44.  
  45.   Inputs:
  46.     None.
  47.  
  48.   Outputs:
  49.     None.
  50. ******************************************************************/
  51. ExtHit::~ExtHit ()
  52. {
  53.   // Reclaim the memory allocated for the internal tables 
  54.   delete ( overlapList );
  55.   delete ( overlapTable );
  56.   delete ( collideList );
  57. }
  58.  
  59. /******************************************************************
  60.   add - Add an extent to be considered for overlap checking.
  61.  
  62.   Inputs:
  63.     extent: The extent to consider for extent overlap checking.
  64.     obj:    A pointer to the parent object for the extent.
  65.  
  66.   Outputs:
  67.     A Boolean value: TRUE if the information was added successfully,
  68.                      FALSE otherwise.
  69. ******************************************************************/
  70. BOOL ExtHit::add( Extent &extent, Ptr obj )
  71. {
  72.   CollideRecord *cr = &collideList[numColRecs];
  73.  
  74.   // Make sure there is room to add the extent
  75.   if ( numColRecs >= maxSize )
  76.     return (FALSE);
  77.  
  78.   // Add the new CollideRecord to the activeList
  79.   if (numColRecs == 0)
  80.     {
  81.       cr->prevActive = NULL;
  82.       activeList = cr;
  83.     }
  84.   else
  85.     {
  86.       cr->prevActive = &collideList[numColRecs-1];
  87.       cr->prevActive->nextActive = cr;
  88.     }
  89.  
  90.   // Initialize the new CollideRecord
  91.   cr->nextActive = NULL;
  92.   cr->index = numColRecs++;
  93.   cr->obj = obj;
  94.   cr->prevOpen = cr->nextOpen = NULL;
  95.   cr->active = TRUE;
  96.   cr->open = FALSE;
  97.  
  98.   // add the extent values to the CollideRecord
  99.   for ( int i=0; i<num_dimensions; i++ )
  100.     {
  101.       cr->min[i].value = extent.min[i];
  102.       cr->max[i].value = extent.max[i];
  103.       cr->min[i].ptr = cr->max[i].ptr = cr;
  104.     }
  105.  
  106.   return (TRUE);
  107. }
  108.  
  109. /******************************************************************
  110.   test - Test for overlapping extents.
  111.  
  112.   Inputs:
  113.     func: A user supplied routine to be called for all pairs of
  114.         overlapping extents.
  115.     data: User supplied data to be passed as the d argument in user
  116.         supplied routine func.
  117.  
  118.   Outputs:
  119.     None.
  120. ******************************************************************/
  121. void ExtHit::test (void (*func)(Ptr d, Ptr obj1, Ptr obj2), Ptr data)
  122. {
  123.   for ( dim=0; dim<num_dimensions; dim++ )
  124.     {
  125.       // Add the min and max values of each active extent to the overlapList
  126.       numOverlaps = 0;
  127.       CollideRecord *activeCr = activeList;
  128.  
  129.       while ( activeCr )
  130.         {
  131.           // Add the min extent value to the overlapList
  132.           MinMaxRecord *mmr = &(activeCr->min[dim]);
  133.           overlapList[numOverlaps++] = mmr;
  134.  
  135.           // Add the max extent value to the overlapList
  136.           mmr = &(activeCr->max[dim]);
  137.           overlapList[numOverlaps++] = mmr;
  138.  
  139.           // Reset the active and open flags
  140.           mmr->ptr->active = mmr->ptr->open = FALSE;
  141.  
  142.           // Mark extent as currently not open
  143.           mmr->ptr->prevOpen = mmr->ptr->nextOpen = NULL;
  144.  
  145.           activeCr = activeCr->nextActive;
  146.         }
  147.  
  148.       // Sort the OverlapList by MinMaxRecord value
  149.       qsort( overlapList, numOverlaps, sizeof(MinMaxRecordPtr), minMaxCompare );
  150.  
  151.       // Process all overlapping pairs in the overlapList
  152.       subtest ( dim, numOverlaps, func, data );
  153.     }
  154. }
  155.  
  156. /******************************************************************
  157.   minMaxCompare - Compare the value of two MinMaxRecords for sorting.
  158.  
  159.   Inputs:
  160.     rec1: A MinMaxRecord to compare.
  161.     rec2: A MinMaxRecord to compare.
  162.  
  163.   Outputs:
  164.     -1: if rec1's MMR value is less than rec2's MMR value.
  165.      0:    if the two MMR values are equal
  166.      1: if rec1's MMR value is greater than rec2's MMR value.
  167. ******************************************************************/
  168. int minMaxCompare( const void* rec1, const void* rec2)
  169. {
  170.   MinMaxRecord *mmr1 = *(MinMaxRecord **) rec1;
  171.   MinMaxRecord *mmr2 = *(MinMaxRecord **) rec2;
  172.  
  173.   if (  mmr1->value > mmr2->value )
  174.     return (1);
  175.   else if (  mmr1->value < mmr2->value )
  176.     return (-1);
  177.   else // mmr1->value == mmr2->value 
  178.     {
  179.       // Put minimum extent values before maximum extent value to
  180.       if ( mmr1->value == mmr1->ptr->min[dim].value )
  181.         return (-1);
  182.       else
  183.         return (1);
  184.     }
  185. }
  186.  
  187. /******************************************************************
  188.   subtest - Find and process each set of overlapping pairs of extents
  189.       for a dimension (i.e. in the overlapList).
  190.  
  191.   Inputs:
  192.     dim:         The extent dimension being tested.
  193.     oLstSize:     The number of MinMaxRecords in the overlapList.
  194.     func:         User supplied function to be called for each overlapping pair.
  195.     data:         User supplied data to be passed in the call to func.
  196.  
  197.   Outputs:
  198.     None.
  199. ******************************************************************/
  200. void ExtHit::subtest ( int dim, int oLstSize, void (*func)(Ptr d, Ptr p1,
  201.                          Ptr p2), Ptr data )
  202. {
  203.   // Reset the list of currently open CollideRecords.
  204.   CollideRecord *openList = NULL;
  205.  
  206.   for (int i=0; i<oLstSize; i++)
  207.     {
  208.       // Get CollideRecord for the overlapList entry
  209.       CollideRecord *rec = overlapList[i]->ptr;
  210.  
  211.       if ( !rec->open )
  212.         {
  213.           // Set rec's open flag
  214.           rec->open = TRUE;
  215.  
  216.           // Set the overlapTable entry for all objects on the openList
  217.           CollideRecord *cr = openList;
  218.  
  219.           while ( cr )
  220.             {
  221.               int min = MIN(cr->index, rec->index);
  222.               int max = MAX(cr->index, rec->index);
  223.               int index = (min * maxSize) + max;
  224.  
  225.               // check whether the entry for cr overlapping rec is set in
  226.               //   the overlapTable.
  227.               if ( overlapTable[index] == dim )
  228.                 {
  229.                   if ( dim < (num_dimensions-1) )
  230.                     {
  231.                       // Set the entry in the top half of the overlapTable
  232.                       overlapTable[index] = dim+1;
  233.                       cr->active = rec->active = TRUE;
  234.                     }
  235.                   else
  236.                     // The extents overlapped in all of the dimensions, call
  237.                     // the user supplied overlap function.
  238.                     (*func)(data, cr->obj, rec->obj );
  239.                 }
  240.  
  241.               cr = cr->nextOpen;
  242.             }
  243.  
  244.           // Add rec at the head of the openList
  245.           rec->nextOpen = openList;
  246.           rec->prevOpen = NULL;
  247.  
  248.           if ( openList )
  249.             openList->prevOpen = rec;
  250.  
  251.           // Update the head of the openList
  252.           openList = rec;
  253.         }
  254.       else // the record is already on the openList
  255.         {
  256.           // remove the record from the openList
  257.           if ( rec->prevOpen ) 
  258.             rec->prevOpen->nextOpen = rec->nextOpen; 
  259.           else 
  260.             openList = rec->nextOpen; 
  261.  
  262.           if ( rec->nextOpen ) 
  263.             rec->nextOpen->prevOpen = rec->prevOpen;  
  264.  
  265.           rec->open = FALSE;
  266.  
  267.           // If the record is not active remove it from the activeList
  268.           if ( ! rec->active ) 
  269.             {
  270.               if ( rec->prevActive == NULL )
  271.                 {
  272.                   activeList = rec->nextActive;
  273.  
  274.                   if (rec->nextActive)
  275.                     rec->nextActive->prevActive = NULL;
  276.                 }
  277.               else
  278.                 {
  279.                   rec->prevActive->nextActive = rec->nextActive;
  280.  
  281.                   if (rec->nextActive)
  282.                     rec->nextActive->prevActive = rec->prevActive;
  283.                 }
  284.             }
  285.         }
  286.     }
  287. }
  288.  
  289. //-------------------------------------------------------------
  290. // End of exthit.C
  291. //-------------------------------------------------------------
  292.