/******************************************************************************\ Copyright 1995 The University of North Carolina at Chapel Hill. All Rights Reserved. Permission to use, copy, modify and distribute this software and its documentation for educational, research and non-profit purposes, without fee, and without a written agreement is hereby granted, provided that the above copyright notice and the following three paragraphs appear in all copies. IN NO EVENT SHALL THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF NORTH CAROLINA HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. Permission to use, copy, modify and distribute this software and its documentation for educational, research and non-profit purposes, without fee, and without a written agreement is hereby granted, provided that the above copyright notice and the following three paragraphs appear in all copies. THE UNIVERSITY OF NORTH CAROLINA SPECIFICALLY DISCLAIM ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF NORTH CAROLINA HAS NO OBLIGATION S TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. The authors may be contacted via: US Mail: J. Cohen/M. Lin/D. Manocha/K. Ponamgi Department of Computer Science Sitterson Hall, CB #3175 University of N. Carolina Chapel Hill, NC 27599-3175 Phone: (919)962-1749 EMail: {cohenj,lin,manocha,ponamgi}@cs.unc.edu \*****************************************************************************/ /*****************************************************************************\ nbody.c -- Description : This file contains the code for sorting bounding boxes and maintaining information about overlaps in each dimension. Naturally, none of these routines will be called unless (state.using_nbody == COL_TRUE), so this is assumed. \*****************************************************************************/ /*----------------------------- Local Includes -----------------------------*/ #include #include #include /*----------------------------- Local Constants -----------------------------*/ /*------------------------------ Local Macros -------------------------------*/ /*------------------------------- Local Types -------------------------------*/ /*------------------------ Local Function Prototypes ------------------------*/ static void UpdateOverlap(__col_State *state, int axis, __col_BoxVert *vert); static void Swap(__col_BoxVert **current); static void sort_list(__col_State *state, int axis); static void LocalSortList(__col_State *state, __col_Polytope *polytope, int axis); /*------------------------------ Local Globals ------------------------------*/ /*---------------------------------Functions-------------------------------- */ /*****************************************************************************\ @ __col_AddPair() ----------------------------------------------------------------------------- description : Add a polytope pair to the nbody_active_list because it has just begun to overlap in all 3 dimensions. input : output : notes : \*****************************************************************************/ void __col_AddPair(__col_State *state, __col_PairNode *pair) { int row, col; pair->prev_nbody_active = COL_NULL; pair->next_nbody_active = state->nbody_active_list; if (state->nbody_active_list != COL_NULL) state->nbody_active_list->prev_nbody_active = pair; state->nbody_active_list = pair; #if 0 /* if you want to initialize the feature pairs intelligently when an overlap begins, put the code here */ __COL_PAIR_ROW_COL(*state, pair, row, col); pair->closest_features[0] = state->polytopes[row].polytope->verts->f.any; pair->closest_features[1] = state->polytopes[col].polytope->verts->f.any; #endif return; } /** End of __col_AddPair() **/ /*****************************************************************************\ @ __col_RemovePair() ----------------------------------------------------------------------------- description : Remove a polytope pair from the nbody_active_list because the polytopes were previously overlapping in all three dimensions, but we've just swapped them in one dimension such that they no longer overlap. input : output : notes : \*****************************************************************************/ void __col_RemovePair(__col_State *state, __col_PairNode *pair) { if (pair->next_nbody_active != COL_NULL) pair->next_nbody_active->prev_nbody_active = pair->prev_nbody_active; if (pair->prev_nbody_active != COL_NULL) pair->prev_nbody_active->next_nbody_active = pair->next_nbody_active; else state->nbody_active_list = pair->next_nbody_active; pair->next_nbody_active = COL_NULL; pair->prev_nbody_active = COL_NULL; pair->distance = __COL_INFINITY; /* Remove the pair from the colliding_list as well, since this non-overlapping pair will not be tested this frame to verify that the polytopes are not colliding */ if (pair->colliding == COL_TRUE) { if (pair->prev_colliding != COL_NULL) pair->prev_colliding->next_colliding = pair->next_colliding; else state->colliding_list = pair->next_colliding; if (pair->next_colliding != COL_NULL) pair->next_colliding->prev_colliding = pair->prev_colliding; pair->prev_colliding = pair->next_colliding = COL_NULL; pair->colliding = COL_FALSE; } return; } /** End of __col_RemovePair() **/ /*****************************************************************************\ @ UpdateOverlap() ----------------------------------------------------------------------------- description : Update the overlap status for a pair of objects along a single dimension. If this affects the total overlap status in 3 dimensions, add or remove this pair from the nbody_active_list if the pair is activated. input : The first box vertex of the pair that were just swapped. output : Overlap status is updated as well as inclusion/exclusion in nbody_active_list. notes : This routine assumes that one vertex is a min and the other is a max for their respective polytopes along the specified axis. This test is made by the caller of this routine to avoid the function call overhead when this condition isn't met (probably half the time, right?). If both are mins or maxes, swapping their sorted order leaves their overlap status the same. \*****************************************************************************/ static void UpdateOverlap(__col_State *state, int axis, __col_BoxVert *vert) { int id1, id2; __col_PairNode *pair; int InNbodyList; char overlapping; id1 = vert->id; id2 = vert->next->id; __COL_GET_PAIR(*state, id1, id2, pair); __COL_OVERLAPPING(*state, id1, id2, overlapping); if (__COL_PAIR_ACTIVE(pair) && overlapping) InNbodyList = COL_TRUE; else InNbodyList = COL_FALSE; __COL_SWAP_OVERLAP(*state, id1, id2, axis); __COL_OVERLAPPING(*state, id1, id2, overlapping); if (InNbodyList == COL_TRUE) __col_RemovePair(state, pair); else if (__COL_PAIR_ACTIVE(pair) && overlapping) __col_AddPair(state, pair); return; } /** End of UpdateOverlap() **/ /*****************************************************************************\ @ Swap() ----------------------------------------------------------------------------- description : Swap a __col_BoxVert and it's "next" pointer. Also update the pointer to the original __col_BoxVert to point to the node that is now preceding it. input : a __col_BoxVert (min or max vertex for some object along some axis) output : notes : \*****************************************************************************/ static void Swap(__col_BoxVert **current) { __col_BoxVert *node1, *node2, *temp; node1 = *current; node2 = node1->next; if (node1->prev != COL_NULL) node1->prev->next = node2; if (node2->next != COL_NULL) node2->next->prev = node1; temp = node1->prev; node1->prev = node2; node1->next = node2->next; node2->prev = temp; node2->next = node1; *current = node2; return; } /** End of Swap() **/ /*****************************************************************************\ @ LocalSortList() ----------------------------------------------------------------------------- description : Sort this particular polytope's min and max -- try moving them outward first if possible to guarantee that we never make comparisons in a section of the list that isn't completely sorted. input : output : notes : It is assumed that all other polytopes in the list are already correctly sorted. \*****************************************************************************/ static void LocalSortList(__col_State *state, __col_Polytope *polytope, int axis) { __col_BoxVert *min, *max, *temp; min = &(polytope->box.min[axis]); max = &(polytope->box.max[axis]); /* try to move the min to the left */ while((min->prev) && (min->value < min->prev->value)) { temp = min->prev; Swap(&temp); if (temp->next == state->box_sort_list[axis]) state->box_sort_list[axis] = temp; if (temp->min_max != temp->next->min_max) UpdateOverlap(state, axis, temp); } /* try to move the max to the right */ while((max->next) && (max->value > max->next->value)) { temp = max; Swap(&temp); if (temp->next == state->box_sort_list[axis]) state->box_sort_list[axis] = temp; if (temp->min_max != temp->next->min_max) UpdateOverlap(state, axis, temp); } /* try to move the min to the right */ while((min->next) && (min->value > min->next->value)) { temp = min; Swap(&temp); if (temp->next == state->box_sort_list[axis]) state->box_sort_list[axis] = temp; if (temp->min_max != temp->next->min_max) UpdateOverlap(state, axis, temp); } /* try to move the max to the left */ while((max->prev) && (max->value < max->prev->value)) { temp = max->prev; Swap(&temp); if (temp->next == state->box_sort_list[axis]) state->box_sort_list[axis] = temp; if (temp->min_max != temp->next->min_max) UpdateOverlap(state, axis, temp); } return; } /** End of LocalSortList() **/ /*****************************************************************************\ @ __col_local_sort() ----------------------------------------------------------------------------- description : Sort a particular polytope's extrema in all 3 lists, which are assumed to be otherwise totally sorted input : output : notes : \*****************************************************************************/ void __col_local_sort(__col_State *state, __col_Polytope *polytope) { int axis; for (axis=0; axis<3; axis++) LocalSortList(state, polytope, axis); } /** End of __col_local_sort() **/ /*****************************************************************************\ @ sort_list() ----------------------------------------------------------------------------- description : Insertion sort routine to sort bounding boxes, which should be mostly sorted from the previous frame. input : Global state, and which axis (X, Y, or Z) to sort. output : The bounding box list for that axis is sorted, and the nbody_active list contains pairs that are overlapping in all dimensions. notes : \*****************************************************************************/ static void sort_list(__col_State *state, int axis) { extern int swaps; __col_BoxVert *current, *begin_item; state->box_sort_list[axis]->prev = 0; for (begin_item= state->box_sort_list[axis]; begin_item->next; begin_item = begin_item->next) ; current = begin_item; while (current) { while (current->next && (current->value > current->next->value)) { Swap(¤t); if (current->next == state->box_sort_list[axis]) state->box_sort_list[axis] = current; if (current->min_max != current->next->min_max) UpdateOverlap(state, axis, current); current = current->next; } current = begin_item = begin_item->prev; } } /** End of sort_list() **/ /*****************************************************************************\ @ __col_nbody() ----------------------------------------------------------------------------- description : Sort the lists of bounding box extrema for each of the 3 dimensions, updating the overlap status of polytope pairs while the sorting takes place. input : output : notes : \*****************************************************************************/ void __col_nbody(__col_State *state) { int axis; for (axis = 0; axis < 3; axis++) sort_list(state, axis); return; } /** End of __col_nbody() **/ /*****************************************************************************\ \*****************************************************************************/