#include "assert.h" #include "kdtree.h" #include "ray.h" #include "objlist.h" #include "raycastable.h" #include "raycastablelist.h" #include "glwin.h" #include "globals.h" #include "globalstate.h" #include "kdcelllist.h" #include "prim.h" #include "log.h" #include #ifndef VIS_ALONE #include "render_thread.h" #include "workrec.h" #include "reconmap.h" #include "fincident.h" #endif #include "common.h" #include "intersect.h" #include "kdtreelog.h" int KDTree::_num_double_checks_avoided = 0; int KDTree::_num_intersects_overruled = 0; int KDTree::_old_intersect_count = 0; int KDTree::_old_intersect_success_count = 0; int KDTree::_new_intersect_count = 0; int KDTree::_new_intersect_success_count = 0; int KDTree::_new_bbox_success_count = 0; int KDTree::_old_bbox_success_count = 0; int KDTree::_worstcase_intersect_count = 0; int KDTree::_num_findpoint_calls = 0; int KDTree::_kdtraversal_cache_misses = 0; int KDTree::_kdtraversal_cache_hits = 0; int KDTree::_num_objs_culled_by_ray_lists = 0; int KDTree::_num_objs_not_culled_by_ray_lists = 0; int KDTree::_num_objs_touched = 0; int KDTree::_num_objs_touched_dbl_count = 0; int KDTree::_num_screen_space_conversions = 0; int KDTree::_num_axis_checks = 0; int KDTree::_num_axis_checks_successes = 0; int KDTree::_num_axis_check_had_to_fail = 0; int _KDTreeNode::_latest_id = 0; Vec4 _KDTreeNode::_latest_debug_color (.2, .5, .8); Counter _KDTreeNode::_total_num_frustum_reqs; Counter _KDTreeNode::_total_num_frusta_clipped; Counter _KDTreeNode::_total_num_cells_touched; Counter _KDTreeNode::_total_num_times_touched; Counter _KDTreeNode::_total_num_frustum_hits_by_cell_size; Counter _KDTreeNode::_total_num_frustum_hits_by_req_size; Counter _KDTreeNode::_total_num_frustum_subdivides; Counter _KDTreeNode::_total_num_objs_partitioned; Counter _KDTreeNode::_total_num_objs_returned; Counter _KDTreeNode::_total_num_objs_not_returned; Counter _KDTreeNode::_total_quick_subdivides; Counter _KDTreeNode::_total_num_straddling_objs; Counter _KDTreeNode::_total_num_one_side_objs; #define DRAWOBJ if (drawing_flags & DRAW_WIREFRAME_OBJS) \ obj->Draw (RayCastable::WIREFRAME); \ else \ obj->Draw (RayCastable::FILLED); float cr = 0.2, cg = 0.5, cb = 0.8; //for assigning debug colors to each obj of each cell. See _KDTreeNode::MakeLists int max_objs_per_cell = 6; #define FACEDIR(face, dir) (2*face + dir) #define KDTREE_DISABL #define X_DIMENSION 0 #define Y_DIMENSION 1 #define Z_DIMENSION 2 #define CELL_SIZE_CUTOFF 100 extern GLWin *debugging_window; int walk_bboxes = 0; int sorted_lists_disabled = 0; int dbl_check_disabled = 0; KDTree::KDTree() { cerr << "Error: KDTree default constructor called" << endl; exit(-1); } //startbox has to encompass all potential objects KDTree::KDTree(RayCastNode *parent, ObjList *objs, const Bounds3d &startbox) : RayCastNode (parent, startbox) { //if we're given objs, we assume that startbox encompasses them. _bounds3d = startbox; KDTREELOG (KDTreeCreate_Start, new KDTreeCreate_Start_Entry (startbox, objs->Size(), this)); //inserting one at a time makes the subdivision not as ideal, so we //give the root all of the objects at once and let it subdivide smartly, if (objs) { _actual_size = objs->Size(); _root = new _KDTreeNode (_bounds3d, NULL, objs); } else { _actual_size = 0; _root = NULL; } } void KDTree::Insert (RayCastable *obj) { const Bounds3d &b = obj->bbox(); if (!_bounds3d.IncludesBox (b)) { cerr << "root of kdtree doesn't include the bbox of inserted obj!" << endl; assert (1==0); } _actual_size++; if (!_root) _root = new _KDTreeNode (_bounds3d, NULL, NULL); _root->Insert (obj); //propagates it down } void KDTree::FinishSetup (void) { //XXX all this should be done on the fly, while we have the leaf there //to play with. assert (_root); cerr << "preculling..." << endl; int numcells = CountLeaves(); int numobjs = _root->CountObjs(); cerr << numcells << " leaves, " << numobjs << " objs means " << (float)numobjs / (float)numcells << " objs per leaf" << endl; cerr << "culling..." << endl; _root->Cull(); numcells = CountLeaves(); numobjs = _root->CountObjs(); cerr << "now " << numcells << " leaves, " << numobjs << " objs means " << (float)numobjs / (float)numcells << " objs per leaf" << endl; cerr << (float)numobjs / (float)_actual_size << " cells/object" << endl; cerr << "making 6 sorted lists and obj info struct..." << endl; _root->MakeLists(); cerr << "making locks..." << endl; _root->CreateLock(); //protect the leaf cells cerr << "telling objs their cells..." << endl; if (dbl_check_disabled) cerr << "disabled!" << endl; else _root->TellObjsTheirCells(); cerr << "done." << endl; KDTREELOG (KDTreeCreate_End, new KDTreeCreate_End_Entry (numobjs, numcells)); } KDTree::~KDTree() { delete _root; } KDTree& KDTree::CopyFrom(const KDTree&) { cerr << "Error: KDTree::CopyFrom() called" << endl; exit(-1); return *this; } ostream& operator<<(ostream &co, const KDTree&) { co << "KDTree (no output function yet)" << endl; return co; } /* istream& operator>>(istream &ci, KDTree &G) { return ci; } */ void KDTree::Grow (const Bounds3d &b) { _root->_bounds.IncludePoint(Vec4 (b.x1(), b.y1(), b.z1())); _root->_bounds.IncludePoint(Vec4 (b.x2(), b.y2(), b.z2())); _bounds3d = _root->_bounds; } void KDTree::PlaceRayCastable(RayCastable *object) { Grow (object->bbox()); _root->Insert(object); } void KDTree::DrawCells (void) const { _root->Draw(1, 0); } void KDTree::DrawObjs (void) const { _root->Draw(0, 1); } //returns t of where it enters; 0 if we're already in there! _KDTreeNode * KDTree::FindStartCell (const Ray &ray, float &t) const { assert (_root); KDTREELOG (KDTreeFindStartCell_Start, new KDTreeFindStartCell_Start_Entry (ray.R(), ray.D())); Vec4 pt = ray.R(); _KDTreeNode *start; // if (drawing_flags) // cerr << "finding start cell intersect" << endl; //is the ray already in the root bbox? if (_root->_bounds.IncludesPoint (pt)) { t = 0.; } //pt in root else { //pt not in the root; we gotta find it. int face, direction; //does ray intersect with root bounding box at all? if (!_root->_bounds.whereEntered(ray, t, face, direction, pt)) { return NULL; } //otherwise t and pt are set now. } #ifndef DEBUG #ifdef DISABLE_LOG if (!_root->_bounds.IncludesPoint (pt)) { cerr << "root bounds: " << _root->_bounds << endl; cerr << "should include P: " << pt << endl; cerr << "but doesn't" << endl; } #endif #endif start = _root->FindPoint (pt); #ifndef NDEBUG #ifdef DISABLE_LOG assert (start); assert (start->_bounds.IncludesPoint (pt)); float testt; int face, dir; assert (start->_bounds.Intersect (ray, testt, face, dir)); //we can't compare testt with t because if we start inside a cell, //our t is properly zero, but Intersect will give us (properly!) //the t of the exit point. #endif #endif KDTREELOG (KDTreeFindStartCell_End, new KDTreeFindStartCell_End_Entry (start)); return start; } void KDTree::Intersect(int rw, int x, int y, _KDTreeNode &start, const Ray &ray, Hit &hit, int drawing_flags, CycleState *CS) { // if (drawing_flags) // cerr << "starting intersect" << endl; // KDTree::_worstcase_intersect_count += _objects->Size(); assert (_root); #if 0 float curpos = 0.; //start of the ray we're GL drawing for debugging; #endif KDTREELOG (KDTreeIntersect_Start, new KDTreeIntersect_Start_Entry (&start, ray.R(), ray.D(), hit)); _KDTreeNode *current = &start; int face, direction; float cell_edge_t; Vec4 nextpt; _KDTreeNode *previous = NULL; int done =0; int gotnext = 0; //if F-C is on, we've already walked out of the cell where the //frustum got stuck; thus, add one. // if (!(truly_GS->_disabled_flags & DISABLE_FC)) // hit.num_kdcells_walked_by_kdtree++; //this loop breaks out in the middle. do { //figure out where the ray leaves us. Any t's beyond that we know //are in another cell. //we'll need face & direction to find the next cell if nothing hits in //here. current->_bounds.whereLeft (ray, cell_edge_t, face, direction, &nextpt); //go for it. done =current->Intersect(rw, x, y, ray, hit, previous, drawing_flags, CS); previous = current; if ((!done) && ((!hit.obj) || (hit.t > cell_edge_t))) { #if 0 //we didn't hit anything or //it's out of our cell if (drawing_flags & DRAW_RAY) { ray.DrawT1T2 (curpos, cell_edge_t); curpos = cell_edge_t; } #endif } else { //we got it. yo. #if 0 if (drawing_flags & DRAW_RAY) { ray.DrawT1T2 (curpos, hit.t); curpos = hit.t; } #endif hit.hitcell = current; KDTREELOG (KDTreeIntersect_End, new KDTreeIntersect_End_Entry (GotHit, hit)); return; } //show the portal we're stepping through if (drawing_flags & DRAW_CELLS) { glColor3fv (portal_color); current->_bounds.DrawXOnFace (face, direction); } gotnext = 0; if (!(truly_GS->_disabled_flags & DISABLE_KDTRAVERSAL_CACHE)) { _KDTreeNode *cached = current->_cache[FACEDIR (face, direction)]; if (cached) { if (cached->_bounds.IncludesPoint (nextpt)) { _kdtraversal_cache_hits++; current = cached; gotnext = 1; } else _kdtraversal_cache_misses++; } } if (!gotnext) current = Step (current, face, direction, nextpt); hit.num_kdcells_walked_by_kdtree++; } while (current); KDTREELOG (KDTreeIntersect_End, new KDTreeIntersect_End_Entry (RanOut, hit)); // cerr << "shot all the way through!" << endl; return; } void KDTree::OldIntersect(_KDTreeNode &start, const Ray &ray, Hit &hit, int drawing_flags, CycleState *CS) { // if (drawing_flags) // cerr << "starting intersect" << endl; // KDTree::_worstcase_intersect_count += _objects->Size(); assert (_root); #if 0 float curpos = 0.; //start of the ray we're GL drawing for debugging; #endif KDTREELOG (KDTreeIntersect_Start, new KDTreeIntersect_Start_Entry (&start, ray.R(), ray.D(), hit)); _KDTreeNode *current = &start; int face, direction; float cell_edge_t; Vec4 nextpt; _KDTreeNode *previous = NULL; int gotnext = 0; //if F-C is on, we've already walked out of the cell where the //frustum got stuck; thus, add one. // if (!(truly_GS->_disabled_flags & DISABLE_FC)) // hit.num_kdcells_walked_by_kdtree++; //this loop breaks out in the middle. do { //figure out where the ray leaves us. Any t's beyond that we know //are in another cell. //we'll need face & direction to find the next cell if nothing hits in //here. current->_bounds.whereLeft (ray, cell_edge_t, face, direction, &nextpt); //go for it. current->OldIntersect(ray, hit, previous, drawing_flags, CS); previous = current; if ((!hit.obj) || (hit.t > cell_edge_t)) { #if 0 //we didn't hit anything or //we hit out of our cell if (drawing_flags & DRAW_RAY) { ray.DrawT1T2 (curpos, cell_edge_t); curpos = cell_edge_t; } #endif } else { //we got it. yo. #if 0 if (drawing_flags & DRAW_RAY) { ray.DrawT1T2 (curpos, hit.t); curpos = hit.t; } #endif hit.hitcell = current; KDTREELOG (KDTreeIntersect_End, new KDTreeIntersect_End_Entry (GotHit, hit)); return; } //show the portal we're stepping through if (drawing_flags & DRAW_CELLS) { glColor3fv (portal_color); current->_bounds.DrawXOnFace (face, direction); } gotnext = 0; if (!(truly_GS->_disabled_flags & DISABLE_KDTRAVERSAL_CACHE)) { _KDTreeNode *cached = current->_cache[FACEDIR (face, direction)]; if (cached) { if (cached->_bounds.IncludesPoint (nextpt)) { _kdtraversal_cache_hits++; current = cached; gotnext = 1; } else _kdtraversal_cache_misses++; } } if (!gotnext) current = Step (current, face, direction, nextpt); hit.num_kdcells_walked_by_kdtree++; } while (current); KDTREELOG (KDTreeIntersect_End, new KDTreeIntersect_End_Entry (RanOut, hit)); // cerr << "shot all the way through!" << endl; return; } _KDTreeNode *KDTree::Step (_KDTreeNode *current, int face, int direction, const Vec4 &nextpt) const { assert (current); float boundary[3][2]; //get the bbox of the portal - we need a cell that encompasses it. for (int i = 0; i < 3; i++) { boundary[i][0] = current->extreme (i, (i != face) ? 0 : direction); boundary[i][1] = current->extreme (i, (i != face) ? 1 : direction); } Bounds3d boundarybox (boundary[0][0], boundary [0][1], boundary[1][0], boundary[1][1], boundary [2][0], boundary [2][1]); KDTREELOG (KDTreeStep_Start, new KDTreeStep_Start_Entry (current, face, direction, nextpt, boundarybox)); _KDTreeNode *next = current; // ascend until some ancestor is a [1-dir] child along correct split while (next->_parent && ((next->_parent->_split_dimension != face) || (next != next->_parent->GetChild(1-direction)))) { next = next->_parent; KDTREELOG (KDTreeStep_Ascend, new KDTreeStep_Ascend_Entry (next)); } // ascend until found cell touches + encloses search boundary //XXX this is gratuitous, no? And it means we might not jump over //to our sibling along the correct plane! while (next->_parent && !next->_bounds.IncludesBox (boundarybox)) { next = next->_parent; KDTREELOG (KDTreeStep_Ascend, new KDTreeStep_Ascend_Entry (next)); } if (!next->_parent) { KDTREELOG (KDTreeStep_End, new KDTreeStep_End_Entry (NULL)); return NULL; //loop breaks out here } // correct sibling of this ancestor next = next->_parent->GetChild(direction); KDTREELOG (KDTreeStep_ToSibling, new KDTreeStep_ToSibling_Entry (next)); #ifndef NDEBUG //assert that the new neighbor doesn't include the old cell if (next->_bounds.IncludesBox (current->_bounds)) { cerr << "ancestor of next cell " << next->_bounds << " includes old cell's bounds " << current->_bounds << endl; if (next == current) cerr << "next == current!" << endl; assert (1==0); } if (!next->_bounds.IncludesPoint (nextpt)) { cerr << "ancestor of next cell " << next->_bounds << " doesn't include the point in it " << nextpt << endl; if (next->_parent->_bounds.IncludesPoint (nextpt)) cerr << "parent does, though." << endl; else cerr << "neither does parent!" << endl; assert (next->_bounds.IncludesBox (boundarybox)); cerr << "it does somehow include the boundary box " << boundarybox << endl; cerr << "the current cell was " << current->_bounds << ", maybe it never had the pt to begin with?" << endl; // assert (1==0); } #endif next = next->FindPoint (nextpt); KDTREELOG (KDTreeStep_End, new KDTreeStep_End_Entry (next)); assert (next != current); return next; } int KDTree::CountChildren() { return _root ? _root->CountChildren() : 0; } int KDTree::CountLeaves() { return _root ? _root->CountLeaves() : 0; } int KDTree::MaxDepth() { return _root ? _root->MaxDepth() : 0; } _KDTreeNode::_KDTreeNode() { cerr << "Error: _KDTreeNode default constructor called" << endl; exit(-1); } _KDTreeNode::_KDTreeNode(const Bounds3d &b, _KDTreeNode *parent, ObjList *objs) : _is_leaf (1), _lokid (NULL), _hikid (NULL), _bounds (b), _parent (parent), _frame_id (-1), _lock (NULL), _same_objs_as_parent (0), _obj_info (NULL), _frusta (NULL), _CS (NULL), _skip_cache(0) { _id = _latest_id++; _debug_color = _latest_debug_color; //prepare next guy's debug color _latest_debug_color += Vec4 (.13579, .19753, .17391); if (_latest_debug_color.r() > .8) _latest_debug_color.set_r (.2); if (_latest_debug_color.g() > .8) _latest_debug_color.set_g (.2); if (_latest_debug_color.b() > .8) _latest_debug_color.set_b (.2); if (!objs) { _objs = new ObjList(); } else { _objs = new ObjList (*objs); cerr << "subdividing..." << endl; if (walk_bboxes) SubDivideWalkBboxes(NULL, -1, 0, 0); else SubDivideByAspectRatio(); } for (int i = 0; i < 6; i++) { _sorted_objs[i] = NULL; _cache[i] = NULL; } } _KDTreeNode::~_KDTreeNode() { //XXX does this recursive crap work? delete _objs; delete _lock; delete _lokid; delete _hikid; delete[] _obj_info; #ifndef NDEBUG int didsort = 0; if (_sorted_objs[0]) didsort = 1; #endif for (int i = 0; i < 6; i++) { #ifndef NDEBUG if (didsort) assert (_sorted_objs[i]); else assert (!_sorted_objs[i]); #endif delete[] _sorted_objs[i]; } ClearOldFrusta(); } _KDTreeNode& _KDTreeNode::CopyFrom(const _KDTreeNode&) { cerr << "Error: _KDTreeNode::CopyFrom() called" << endl; exit(-1); return *this; } void _KDTreeNode::Insert(RayCastable *object) { if (_is_leaf) { _objs->PlaceInList (object); if (_objs->Size() > max_objs_per_cell) { if (walk_bboxes) SubDivideWalkBboxes(NULL, -1, 0, 0); else SubDivideByAspectRatio(); } return; } //distribute to kids int val = object->bbox().TestPlane (_split_dimension, _where_split); if (val >= 0) _hikid->Insert (object); if (val <= 0) _lokid->Insert (object); } //hit->t has the best t so far //if any of our objects were in previous, we shouldn't query it. //if the ray doesn't intersect this cell, we should be alright, but //it'll waste a lot of time void _KDTreeNode::OldIntersect(const Ray &ray, Hit &hit, _KDTreeNode *previous, int drawing_flags, CycleState *CS) { #ifdef ONE_THREAD if (drawing_flags & DRAW_CELLS_ENTERED) Update (CS); //this will cause us to be placed in the cells_entered list if it's the first time we entered the cell. else if (CS) { #ifndef NDEBUG _num_times_touched.Add (CS->_frame_id, _actual.XSize() * _actual.YSize()); _total_num_times_touched.Add (CS->_frame_id, _actual.XSize() * _actual.YSize()); #endif } #endif RayCastable *obj; if (drawing_flags & DRAW_CELLS) { glColor3fv (cell_color); _bounds.drawWireFrame (); } int size = _objs->Size(); int paxis = ray.Primary_Axis(); int dir = paxis % 2; int dimension = paxis/ 2; // if (drawing_flags) // cerr << "ray " << ray << " has paxis " << paxis << ", dim " << dimension << ", dir " << dir << endl; //if any objects are entirely beyond this, we can cull them real maxloc = _bounds[dir][dimension]; int numqrs = hit.num_bbox_quick_rejects; int newnumqrs; float bestt = hit.t; real hitptloc = (ray.R() + (ray.D() * bestt))[dimension]; if (drawing_flags) { // cerr << "edge of cell in that dimension is " << maxloc << endl; // cerr << "cell has " << size << " objects" << endl; } if (hit.obj) { // if (drawing_flags) //cerr << "hitpoint loc in that dimension is " << hitptloc << endl; if (dir == 1) { if (hitptloc < maxloc) maxloc = hitptloc; } else { if (hitptloc > maxloc) maxloc = hitptloc; } } //if list is NULL, we decided not to use the sorted lists for //whatever reason - probably ran out of memory. RayCastable **list = _sorted_objs[paxis]; KDTREELOG (KDTreeNodeIntersect_Start, new KDTreeNodeIntersect_Start_Entry (ray.R(), ray.D(), this, list ? paxis : -1, maxloc, hit)); //get important axis # from the hit location //if that # is > or < the appropriate min/max, we're done. void *place; if (!list) _objs->Reset (place); for (int i = 0; i < size; i++) { if (list) obj = list[i]; else { obj = _objs->Peek (place); _objs->Next (place); } if (CS && (obj->_sent_to_gl_frame_id == CS->_frame_id)) continue; const Bounds3d &objbox = obj->bbox(); //if major axis is negative, we want the max face if (list && ( ((dir == 0) && (objbox[1][dimension] < maxloc)) || ((dir == 1) && (objbox[0][dimension] > maxloc)) )) { // if (drawing_flags) // cerr << " CULLED - FINISHED!" << endl; hit.num_kdtree_sort_list_quick_rejects += size - i; if ((drawing_flags & DRAW_OBJECTS) & (drawing_flags & DRAW_QUICK_REJECT_OBJECTS)) { glColor3fv (qr_color); objbox.drawWireFrame (); // obj->Draw (RayCastable::FILLED); } KDTREELOG (KDTreeNodeIntersect_End, new KDTreeNodeIntersect_End_Entry (SortedListShortcut)); return; } #ifdef DISABLE_LOG if (CS && (truly_GS->_disabled_flags2 & ENABLE_THROW_BAD_AREA_RATIO_TO_GL)) { if (obj->ObjAreaToBboxArea() < .25) { obj->_sent_to_gl_frame_id = CS->_frame_id; CS->_samplebuffer->AddObjForGL (obj, CS->_frame_id); continue; } } if (CS && (truly_GS->_disabled_flags2 & ENABLE_THROW_BAD_HIT_RATIO_TO_GL)) { if ( (obj->_num_intersect_attempts > MIN_HITS_BEFORE_GLED) && (obj->_num_successful_intersects * BAD_HIT_RATIO < obj->_num_intersect_attempts) ) { obj->_sent_to_gl_frame_id = CS->_frame_id; CS->_samplebuffer->AddObjForGL (obj, CS->_frame_id); continue; } } #endif if ((truly_GS->_disabled_flags & DISABLE_DOUBLE_CHECK) || obj->_ray_touched_id != ray.ID()) { KDTree::_old_intersect_count++; int oldnumsuccess = hit.num_bbox_successes; int oldnumint = hit.num_intersect_successes; obj->_num_intersect_attempts++; if (truly_GS->_disabled_flags & DISABLE_UNCACHED_BBOX_TESTS) obj->IntersectProbable (ray, hit); else obj->Intersect (ray, hit); obj->_ray_touched_id = ray.ID(); KDTREELOG (KDTreeNodeIntersect_Obj, new KDTreeNodeIntersect_Obj_Entry (obj, (oldnumsuccess == hit.num_bbox_successes), (oldnumint != hit.num_intersect_successes))); //more bookkeeping if (oldnumsuccess != hit.num_bbox_successes) KDTree::_old_bbox_success_count++; if (oldnumint != hit.num_intersect_successes) { KDTree::_old_intersect_success_count++; obj->_num_successful_intersects++; } newnumqrs = hit.num_bbox_quick_rejects; #ifdef DRAW_ALL_STRADDLER_BBOXES if (drawing_flags & DRAW_CELLS) { if (obj->_cells_we_inhabit.Size() > 1) //straddler! { glColor3f (.4, .4, .2); _KDTreeNode *current; for (int i = 0; i < obj->_cells_we_inhabit->Size(); i++) { current = obj->_cells_we_inhabit->GetPointerToElement (i); if (current != this) current->_bounds.drawWireFrame(); } } } #endif if (drawing_flags & DRAW_OBJECTS) { glColor3fv (obj_color); if (newnumqrs != numqrs) { if (drawing_flags & DRAW_QUICK_REJECT_OBJECTS) { glColor3fv (qr_color); obj->bbox().drawWireFrame (); // obj->Draw (RayCastable::FILLED); } numqrs = newnumqrs; } else { obj->bbox().drawWireFrame (); glColor3fv (obj->GetRepresentativeColor().ArrayForGL()); DRAWOBJ; } } if (hit.obj && hit.t < bestt) { KDTREELOG (KDTreeNodeIntersect_NewBest, new KDTreeNodeIntersect_NewBest_Entry (hit)); bestt = hit.t; hitptloc = (ray.R() + (ray.D() * hit.t))[dimension]; // if (drawing_flags) // cerr << "new hitptloc " << hitptloc << endl; if (dir == 1) { if (hitptloc < maxloc) maxloc = hitptloc; else { //this could happen if the "front" (closest bbox) //object is //really deep and we intersect it way in the back // // if (drawing_flags) // cerr << "what the..." << endl; } } else { if (hitptloc > maxloc) maxloc = hitptloc; else { // if (drawing_flags) // cerr << "what the 2..." << endl; } } } else { if (hit.t > bestt) cerr << "object didn't automatically filter out the t!" << endl; } } else { KDTree::_num_double_checks_avoided++; hit.num_straddlers_skipped++; } } KDTREELOG (KDTreeNodeIntersect_End, new KDTreeNodeIntersect_End_Entry (AllObjsEnd)); } int _KDTreeNode::CountObjs() { int count = _objs->Size(); if (!_is_leaf) { count += _lokid->CountObjs(); count += _hikid->CountObjs(); } return count; } int _KDTreeNode::CountChildren() { if (_is_leaf) return 1; int count = 1; count += _lokid->CountChildren(); count += _hikid->CountChildren(); return count; } int _KDTreeNode::CountLeaves() { if (_is_leaf) return 1; int count = _lokid->CountLeaves(); count += _hikid->CountLeaves(); return count; } int _KDTreeNode::MaxDepth() { if (_is_leaf) return 1; int max = 0; int m = _lokid->MaxDepth(); if (m > max) max = m; m = _hikid->MaxDepth(); if (m > max) max = m; return max + 1; } struct Loc { int which; //min or max real where; //where the min or max is located RayCastable *obj; }; void _KDTreeNode::SubDivideByAspectRatio(void) { if (_objs->Size() <= max_objs_per_cell) { KDTREELOG (KDTreeSubdivide_Reject, new KDTreeSubdivide_Reject_Entry (this, FewObjects)); return; } //other stopping condition; if we didn't succeed in doing anything with //our last two subdivisions - the one that created us, and the one that //created our parents. if (_same_objs_as_parent && _parent && _parent->_same_objs_as_parent) { KDTREELOG (KDTreeSubdivide_Reject, new KDTreeSubdivide_Reject_Entry (this, ParentsUnproductive)); return; } #ifdef KDTREE_DISABLE return; #endif KDTREELOG (KDTreeSubdivide_Start, new KDTreeSubdivide_Start_Entry (this, new ObjList (*_objs))); void *place; RayCastable *obj; real _biggest_dim = -MAXFLOAT; real thisdim; for (int dim = 0; dim < 3; dim++) { thisdim = _bounds[1][dim] - _bounds[0][dim]; if ( thisdim > _biggest_dim) { _split_dimension = dim; _biggest_dim = thisdim; } } _where_split = (_bounds[1][_split_dimension] + _bounds[0][_split_dimension]) / 2.; //make new boundin' boxes. Bounds3d lob, hib; lob = hib = _bounds; switch (_split_dimension) { case X_DIMENSION: lob[1].set_x (_where_split); hib[0].set_x (_where_split); break; case Y_DIMENSION: lob[1].set_y (_where_split); hib[0].set_y (_where_split); break; case Z_DIMENSION: lob[1].set_z (_where_split); hib[0].set_z (_where_split); break; } _lokid = new _KDTreeNode (lob, this); _hikid = new _KDTreeNode (hib, this); if (!_lokid || !_hikid) { delete _lokid; delete _hikid; cerr << "out of memory although cell has " << _objs->Size() << " objs; no more subdivision for us!" << endl; _is_leaf = 1; return; //yes, we ran out of memory } // int wherefalls; ObjList *ournewobjs = new ObjList(); _objs->Reset (place); int numstraddlers = 0; real objmin, objmax; int didplace = 0; //reclassify all the objects into our two kids // cerr << "split is at " << _where_split << " in dimension " << (char)('X' + _split_dimension) << endl; while (place) { obj = _objs->Peek (place); objmin = obj->bbox()[0][_split_dimension]; objmax = obj->bbox()[1][_split_dimension]; didplace = 0; assert (objmax >= objmin); // cerr << "bbox is " << obj->bbox() << endl; // cerr << "bbox has min " << objmin << " and max " << objmax << endl; if ( (objmin < _where_split) || ((objmin == objmax) && (objmin == _where_split)) ) { didplace++; // cerr << "lo!" << endl; _lokid->_objs->PlaceInList (obj); if (objmax >= _where_split) { // cerr << "straddler!" << endl; numstraddlers++; } } if ( (objmax > _where_split) || ((objmin == objmax) && (objmin == _where_split)) ) { didplace++; // cerr << "hi!" << endl; _hikid->_objs->PlaceInList (obj); } if (!didplace) cerr << "lost an object " << obj->bbox() << " while subdividing!" << endl; #ifdef FIND_BUG Vec4 low (-.0625, 0., 11.9375, 1.); Vec4 high (12.0625, 1.5, 12.0625, 1.); if (obj->bbox()[0] == low && obj->bbox()[1] == high) { cerr << "classifyin' crazy box for dimension " << _split_dimension << " at split place " << _where_split << endl; cerr << "placed in " << didplace << " kids." << endl; } #endif _objs->Next (place); } // cerr << "SubDivide split " << _objs->Size() << " objects along the " << (char)('X' + _split_dimension) << " plane at " << _where_split << " into " << numstraddlers << " straddlers, " << _lokid->_objs->Size() << " low and " << _hikid->_objs->Size() << " high objects." << endl; if (_objs->Size() == _lokid->_objs->Size()) _lokid->_same_objs_as_parent = 1; if (_objs->Size() == _hikid->_objs->Size()) _hikid->_same_objs_as_parent = 1; KDTREELOG (KDTreeSubdivide_TryPlane, new KDTreeSubdivide_TryPlane_Entry (this, _split_dimension, _where_split, _hikid->_objs->Size(), _lokid->_objs->Size(), numstraddlers, 0.0, 1)); _objs->Kill(); delete _objs; _objs = ournewobjs; _is_leaf = 0; KDTREELOG (KDTreeSubdivide_End, new KDTreeSubdivide_End_Entry (this)); _lokid->SubDivideByAspectRatio(); _hikid->SubDivideByAspectRatio(); return; } //returns the node containing this point or NULL if no luck. //actually we currently assume that we contain the point; that may //change though. _KDTreeNode *_KDTreeNode::FindPoint (const Vec4 &pt) { //not sure if floats are exact enough to always have IncludesPt //return what we want. // assert (IncludesPt (pt)); //starting from root going down: //are we a leaf? if so, we're done. //check to see if it's on or in the lower kid; give it to it //otherwise,it should be in the upper kid; give it to that. KDTree::_num_findpoint_calls++; if (_is_leaf) { KDTREEFPLOG (KDTreeFindPoint, new KDTreeFindPoint_Entry (this, pt, Yes)); return this; } int test = _lokid->_bounds.TestPlane (_split_dimension, pt.v(_split_dimension)); //dive down if (test == 0) { KDTREEFPLOG (KDTreeFindPoint, new KDTreeFindPoint_Entry (this, pt, Lower)); return _lokid->FindPoint (pt); } else { //if it wasn't in lokid (test != 0), //lokid should have been lower than the point. if (test != -1) cerr << "KDTreeNode::FindPoint, seeking pt " << pt << " in our bbox " << _bounds << " did a plane test on the split dimension " << _split_dimension << " at " << pt.v(_split_dimension) << " and got a totally bizarre result." << endl; KDTREEFPLOG (KDTreeFindPoint, new KDTreeFindPoint_Entry (this, pt, Upper)); return _hikid->FindPoint (pt); } } _KDTreeNode *_KDTreeNode::GetChild (int which) { if (which == 0) return _lokid; else return _hikid; } float _KDTreeNode::extreme (int dimension, int direction) { return _bounds[direction][dimension]; #if 0 if (direction == 0) { if (dimension == 0) return _bounds.x1(); else if (dimension == 1) return _bounds.y1(); else if (dimension == 2) return _bounds.z1(); else assert (1==0); } else { if (dimension == 0) return _bounds.x2(); else if (dimension == 1) return _bounds.y2(); else if (dimension == 2) return _bounds.z2(); else assert (1==0); } return 0; #endif } void _KDTreeNode::Draw (int cells, int objs) const { if (!_is_leaf) { //cerr << "lo kid: " << endl; _lokid->Draw(cells, objs); //cerr << "hi kid: " << endl; _hikid->Draw(cells, objs); // cerr << "parent:" << endl; } if (cells) { glColor3fv (cell_color); _bounds.drawWireFrame(); } if (objs) { RayCastable *obj; void *place; _objs->Reset (place); while (place) { obj = _objs->Peek (place); glColor3fv (obj->GetRepresentativeColor().ArrayForGL()); obj->bbox().drawWireFrame (); if (!(truly_GS->_kddraw_flags & DRAW_WIREFRAME_OBJS)) obj->Draw (RayCastable::FILLED); _objs->Next (place); } } } void _KDTreeNode::MakeLists (void) { int size = _objs->Size(); if (size > 0) { //make an info struct for each object _obj_info = new ObjInfo [size]; if (!_obj_info) { cerr << "out of memory making the obj info struct! we can't handle that." << endl; return; } void *place; _objs->Reset (place); RayCastable *obj; int cur = 0; while (place) { obj = _objs->Peek (place); _obj_info[cur]._obj = obj; _obj_info[cur]._clipped_bbox = obj->bbox(); _obj_info[cur]._clipped_bbox.ClipToBbox (_bounds); _obj_info[cur]._debug_color.Set (cr, cg, cb); _obj_info[cur]._vis_objinfo_frame_id = -1; cr += 0.13579; if ( cr > 0.8f ) cr = 0.2f; cg += 0.19753; if ( cg > 0.8f ) cg = 0.2f; cb += 0.17391; if ( cb > 0.8f ) cb = 0.2f; _objs->Next (place); cur++; } } if (sorted_lists_disabled) { cerr << "disabled!" << endl; return; } if (size > 0) { int i; for (i = 0; i < 6; i++) { _sorted_objs[i] = new RayCastable *[size]; if (!_sorted_objs[i]) //did we run out of memory? { cerr << "out of memory when making sorted lists; returning." << endl; //yup, delete what we alloc'd and return for (int j = 0; j < i; j++) { delete[] _sorted_objs[i]; _sorted_objs[i] = NULL; } return; } } void *place; _objs->Reset (place); //put all the objects into all 6 lists RayCastable *obj; int cur = 0; while (place) { obj = _objs->Peek (place); _sorted_objs[0][cur] = obj; _sorted_objs[1][cur] = obj; _sorted_objs[2][cur] = obj; _sorted_objs[3][cur] = obj; _sorted_objs[4][cur] = obj; _sorted_objs[5][cur] = obj; _objs->Next (place); cur++; } qsort (_sorted_objs[0], size, sizeof (RayCastable *), xmaxcompare); qsort (_sorted_objs[1], size, sizeof (RayCastable *), xmincompare); qsort (_sorted_objs[2], size, sizeof (RayCastable *), ymaxcompare); qsort (_sorted_objs[3], size, sizeof (RayCastable *), ymincompare); qsort (_sorted_objs[4], size, sizeof (RayCastable *), zmaxcompare); qsort (_sorted_objs[5], size, sizeof (RayCastable *), zmincompare); #if 0 for (i=0 ; i < _objs->Size(); i++) { cerr << "x- " << i << " is " << (*_sorted_objs[0])[i].bbox() << endl; } for (i=0 ; i < _objs->Size(); i++) { cerr << "x+ " << i << " is " << (*_sorted_objs[1])[i].bbox() << endl; } #endif } if (!_is_leaf) { _lokid->MakeLists(); _hikid->MakeLists(); } // cerr << "make list out" << endl; } int xmincompare (const void *obj1, const void *obj2) { if ((*(RayCastable **)obj1)->bbox().x1() < (*(RayCastable **)obj2)->bbox().x1()) return -1; else if ((*(RayCastable **)obj1)->bbox().x1() > (*(RayCastable **)obj2)->bbox().x1()) return 1; else return 0; } int ymincompare (const void *obj1, const void *obj2) { if ((*(RayCastable **)obj1)->bbox().y1() < (*(RayCastable **)obj2)->bbox().y1()) return -1; else if ((*(RayCastable **)obj1)->bbox().y1() > (*(RayCastable **)obj2)->bbox().y1()) return 1; else return 0; } int zmincompare (const void *obj1, const void *obj2) { if ((*(RayCastable **)obj1)->bbox().z1() < (*(RayCastable **)obj2)->bbox().z1()) return -1; else if ((*(RayCastable **)obj1)->bbox().z1() > (*(RayCastable **)obj2)->bbox().z1()) return 1; else return 0; } int xmaxcompare (const void *obj1, const void *obj2) { if ((*(RayCastable **)obj1)->bbox().x2() < (*(RayCastable **)obj2)->bbox().x2()) return 1; else if ((*(RayCastable **)obj1)->bbox().x2() > (*(RayCastable **)obj2)->bbox().x2()) return -1; else return 0; } int ymaxcompare (const void *obj1, const void *obj2) { if ((*(RayCastable **)obj1)->bbox().y2() < (*(RayCastable **)obj2)->bbox().y2()) return 1; else if ((*(RayCastable **)obj1)->bbox().y2() > (*(RayCastable **)obj2)->bbox().y2()) return -1; else return 0; } int zmaxcompare (const void *obj1, const void *obj2) { if ((*(RayCastable **)obj1)->bbox().z2() < (*(RayCastable **)obj2)->bbox().z2()) return 1; else if ((*(RayCastable **)obj1)->bbox().z2() > (*(RayCastable **)obj2)->bbox().z2()) return -1; else return 0; } int compareloc (const void *obj1, const void *obj2) { if ( ((Loc *)obj1)->where < ((Loc *)obj2)->where ) return -1; else if ( ((Loc *)obj1)->where > ((Loc *)obj2)->where ) return 1; else { if ( ((Loc *)obj1)->which < ((Loc *)obj2)->which ) return -1; else if ( ((Loc *)obj1)->which > ((Loc *)obj2)->which ) return 1; else return 0; } } #if 0 void _KDTreeNode::GetNearFarPlanes (const Ray &ray, Plane &near, Plane &far) { //XXX untested! int paxis = ray.Primary_Axis(); int dimension = paxis/ 2; int dir = paxis % 2; real which; if (dir == 0) which = -1.; else which = 1.; real nearval = _bounds[1-dir][dimension]; real farval = -_bounds[dir][dimension]; switch (dimension) { case 0: near.Set (which, 0, 0, nearval); far.Set (-which, 0., 0., farval); break; case 1: near.Set (0., which, 0, nearval); far.Set (0., -which, 0., farval); break; case 2: near.Set (0, 0, which, nearval); far.Set (0, 0, -which, farval); break; } } #endif int KDTree::IsValidCell (_KDTreeNode *cell) const { if (!cell) return 0; return _root->IsValidCell (cell); } int _KDTreeNode::IsValidCell (_KDTreeNode *cell) { if (cell == this) return 1; if (_is_leaf) return 0; //recurse down the left if (_lokid->IsValidCell (cell)) return 1; //recurse down the right if (_hikid->IsValidCell (cell)) return 1; return 0; } //takes you from NULL to inside the k-dtree if you're outside //or NULL to NULL if you were outside and missed it altogether //from non-NULL to NULL if you leave the tree //from non-NULL to non-NULL if you're walking inside it. _KDTreeNode *KDTree::Traverse (const Ray &ray, int &face, int &direction, _KDTreeNode *start) const { assert (_root); float t; // int face, direction; Vec4 pt; _KDTreeNode *next; if (start) { #ifndef NDEBUG if (!start->_bounds.Intersect (ray, t, face, direction)) { start->_bounds.Intersect (ray, t, face, direction); assert (0); } #endif start->_bounds.whereLeft (ray, t, face, direction, &pt); if (!(truly_GS->_disabled_flags & DISABLE_KDTRAVERSAL_CACHE)) { _KDTreeNode *cached = start->_cache[FACEDIR (face, direction)]; if (cached) { if (cached->_bounds.IncludesPoint (pt)) { _kdtraversal_cache_hits++; return cached; } else _kdtraversal_cache_misses++; } } assert (start->_bounds.IncludesPoint (pt)); next = Step (start, face, direction, pt); assert (next != start); // if (!next) // cerr << "left the k-d tree" << endl; start->_cache[FACEDIR (face, direction)] = next; return next; } else { float t; face = direction = -1; //we're coming in from nowhere; no exit face/dir yet! return FindStartCell (ray, t); } } void _KDTreeNode::CreateLock (void) { #ifndef USE_LOCKS return; #else if (_is_leaf) { _lock = new ProtectedObject(); } else { _lokid->CreateLock(); _hikid->CreateLock(); } #endif } void _KDTreeNode::TellObjsTheirCells() { if (!_is_leaf) { _lokid->TellObjsTheirCells(); _hikid->TellObjsTheirCells(); } else { void *place; _objs->Reset (place); RayCastable *obj; while (place) { obj = _objs->Peek (place); _objs->Next (place); obj->AddCell (this); } } } void _KDTreeNode::Cull () { if (!_is_leaf) { _lokid->Cull(); _hikid->Cull(); } if (!_is_leaf && _lokid->_is_leaf && _hikid->_is_leaf && _lokid->_same_objs_as_parent && _hikid->_same_objs_as_parent) { assert (_objs->Size() == 0); delete _objs; _objs = _lokid->_objs; delete _hikid; _is_leaf = 1; _lokid->_objs = NULL; delete _lokid; } } void _KDTreeNode::SubDivideWalkBboxes(Loc *given, int givendim, int givensize, int numgivenin) { if (_objs->Size() <= max_objs_per_cell) { KDTREELOG (KDTreeSubdivide_Reject, new KDTreeSubdivide_Reject_Entry (this, FewObjects)); return; } //other stopping condition; if we didn't succeed in doing anything with //our last two subdivisions - the one that created us, and the one that //created our parents. if (_same_objs_as_parent && _parent && _parent->_same_objs_as_parent) { KDTREELOG (KDTreeSubdivide_Reject, new KDTreeSubdivide_Reject_Entry (this, ParentsUnproductive)); return; } #ifdef KDTREE_DISABLE return; #endif KDTREELOG (KDTreeSubdivide_Start, new KDTreeSubdivide_Start_Entry (this, new ObjList (*_objs))); void *place; RayCastable *obj; real middle; //the middle of the bbox along the current axis int _best_straddlers = _objs->Size() + 1; //only this one has to be initted right int _best_balance = _objs->Size() +1; real _best_dist = 0.; int _best_dim = -1; real _best_place = -1; static int totalnumstraddlersmade = 0; #define TAKE_BEST \ _best_straddlers = in; \ _best_balance = balance; \ _best_dist = dist; \ _best_dim = dim; \ _best_place = curlist[i].where; \ if (_best_list && (_best_list != given) && (_best_list != curlist)) \ delete[] _best_list; \ _best_list = curlist; \ best_index = i; \ best_size = listsize; \ best_start_in = startin; \ _best_left = left; \ _best_right = right Loc *_best_list = NULL; int best_index = -1; int best_size = -1; int best_start_in = -1; int _best_left = -1; int _best_right = -1; for (int dim = 0; dim < 3; dim ++) { _objs->Reset (place); Loc *curlist; int listsize; int startin = 0; real ourlow = _bounds[0][dim]; real ourhigh = _bounds[1][dim]; middle = (ourlow + ourhigh) / 2.0; if (dim == givendim) { curlist = given; listsize = givensize; startin = numgivenin; } else { int i = 0; listsize = 0; curlist = new Loc [_objs->Size() * 2]; Bounds3d bounds; real objlow, objhigh; startin = 0; //put min & max of all objects into a list while (place) { obj = _objs->Peek (place); bounds = obj->bbox(); objlow = bounds[0][dim]; objhigh = bounds[1][dim]; if (objlow == objhigh) { curlist[i].which = 2; curlist[i].where = objlow; curlist[i].obj = obj; // cerr << "found zero at " << objlow << " in dimension " << (char)(dim + 'X') << endl; i++; } else { if (objlow >= ourlow) { curlist[i].where = objlow; curlist[i].which = 0; curlist[i].obj = obj; i++; } else { startin++; } if (objhigh <= ourhigh) { curlist[i].where = objhigh; curlist[i].which = 1; curlist[i].obj = obj; i++; } } _objs->Next (place); } listsize = i; //it is sorting correctly, you know. qsort (curlist, listsize, sizeof (Loc), compareloc); } //if list wasn't given, make it int left = 0; int right = _objs->Size() - startin; int in = startin; int balance; real dist; // cerr << "in starting at " << in << endl; int start; real current; //real current, I say! int wasbest; for (int i = 0; i < listsize; i++) { start = i; current = curlist[i].where; // cerr << "at current " << current << endl; //go through the maxes first do { if (curlist[i].which == 1) { in--; left++; } else if (curlist[i].which == 2) { // cerr << "flat obj" << endl; right--; in++; } else assert (curlist[i].which == 0); i++; } while ((i < listsize) && (curlist[i].where == current)); // cerr << "went through " << (i - start) << " objects, we have " << left << ", " << in << ", " << right << endl; //we overshot by one. i--; //now check it for goodness balance = right - left; if (balance < 0) balance = -balance; if (curlist[i].where > middle) dist = curlist[i].where - middle; else dist = middle - curlist[i].where; wasbest = 0; #if 0 if ((right > 0) && (left > 0)) { if (in < _best_straddlers) { // cerr << "found plane with " << numstraddlers << " straddlers" << endl; TAKE_BEST; wasbest = 1; } else if (in == _best_straddlers) { if (balance < _best_balance) { // cerr << "found plane with balance " << balance << endl; TAKE_BEST; wasbest = 1; } else if (balance == _best_balance) { if (dist < _best_dist) { // cerr << "found plane with distance " << dist << endl; TAKE_BEST; wasbest = 1; } } } } #else if ( (curlist[i].where > ourlow) && (curlist[i].where < ourhigh) && ((balance + in) < (_best_balance + _best_straddlers)) ) { TAKE_BEST; wasbest = 1; } #endif KDTREELOG (KDTreeSubdivide_TryPlane, new KDTreeSubdivide_TryPlane_Entry (this, dim, curlist[i].where, right, left, in, dist, wasbest)); //go back over it, for the mins while (start <= i) { if (curlist[start].which == 0) { in++; right--; } else if (curlist[start].which == 2) { in--; left++; } else assert (curlist[start].which == 1); start++; } // cerr << "did mins: we temporarily have " << left << ", " << in << ", " << right << endl; assert (in >= 0); assert (right >= 0); } //for each location if (right != 0) { // cerr << "right is mistakenly nonzero: " << right << endl; assert (0); } if ((left + in) != _objs->Size()) { // cerr << "left + in is " << (left + in) << ", listsize is " << listsize << endl; assert (0); } // cerr << "--------" << endl << " done with a list" << endl; if ((curlist != _best_list) && (curlist != given)) delete[] curlist; } //for each dim if (_best_dim == -1) { cerr << "subdivision FAILED with cell " << _bounds << " containing " << _objs->Size() << " objects. Go figure. " << endl; return; } totalnumstraddlersmade += _best_straddlers; // cerr << "total num straddlers so far: " << totalnumstraddlersmade << endl; _split_dimension = _best_dim; _where_split = _best_place; //make new boundin' boxes. Bounds3d lob, hib; lob = hib = _bounds; switch (_split_dimension) { case X_DIMENSION: lob[1].set_x (_where_split); hib[0].set_x (_where_split); break; case Y_DIMENSION: lob[1].set_y (_where_split); hib[0].set_y (_where_split); break; case Z_DIMENSION: lob[1].set_z (_where_split); hib[0].set_z (_where_split); break; } _lokid = new _KDTreeNode (lob, this); _hikid = new _KDTreeNode (hib, this); if (!_lokid || !_hikid) { delete _lokid; delete _hikid; cerr << "out of memory although cell has " << _objs->Size() << " objs; no more subdivision for us!" << endl; _is_leaf = 1; return; //yes, we ran out of memory } // int wherefalls; ObjList *ournewobjs = new ObjList(); _objs->Reset (place); int numstraddlers = 0; real objmin, objmax; int didplace = 0; //reclassify all the objects into our two kids // cerr << "split is at " << _where_split << " in dimension " << (char)('X' + _split_dimension) << endl; while (place) { obj = _objs->Peek (place); objmin = obj->bbox()[0][_split_dimension]; objmax = obj->bbox()[1][_split_dimension]; didplace = 0; assert (objmax >= objmin); // cerr << "bbox is " << obj->bbox() << endl; // cerr << "bbox has min " << objmin << " and max " << objmax << endl; if ( (objmin < _where_split) || ((objmin == objmax) && (objmin == _where_split)) ) { didplace++; // cerr << "lo!" << endl; _lokid->_objs->PlaceInList (obj); if (objmax >= _where_split) { // cerr << "straddler!" << endl; numstraddlers++; } } if ( (objmax > _where_split) || ((objmin == objmax) && (objmin == _where_split)) ) { didplace++; // cerr << "hi!" << endl; _hikid->_objs->PlaceInList (obj); } if (!didplace) cerr << "lost an object " << obj->bbox() << " while subdividing!" << endl; #ifdef FIND_BUG Vec4 low (-.0625, 0., 11.9375, 1.); Vec4 high (12.0625, 1.5, 12.0625, 1.); if (obj->bbox()[0] == low && obj->bbox()[1] == high) { cerr << "classifyin' crazy box for dimension " << _split_dimension << " at split place " << _where_split << endl; cerr << "placed in " << didplace << " kids." << endl; } #endif _objs->Next (place); } // cerr << "SubDivide split " << _objs->Size() << " objects along the " << (char)('X' + _split_dimension) << " plane at " << _where_split << " into " << numstraddlers << " straddlers, " << _lokid->_objs->Size() << " low and " << _hikid->_objs->Size() << " high objects." << endl; if (_objs->Size() == _lokid->_objs->Size()) _lokid->_same_objs_as_parent = 1; if (_objs->Size() == _hikid->_objs->Size()) _hikid->_same_objs_as_parent = 1; // cerr << "whereas, the split had low " << _best_left << " and high " << _best_right << ", with " << _best_straddlers << " straddlers" << endl; assert (_lokid->_objs->Size() == (_best_left + _best_straddlers)); assert (_hikid->_objs->Size() == (_best_right + _best_straddlers)); _objs->Kill(); delete _objs; _objs = ournewobjs; _is_leaf = 0; KDTREELOG (KDTreeSubdivide_End, new KDTreeSubdivide_End_Entry (this)); #if 0 //pass down the list that we can - aggressive, untested! _lokid->SubDivideWalkBboxes(_best_list, _best_dim, best_index, best_start_in); _hikid->SubDivideWalkBboxes(_best_list + best_index, _best_dim, best_size - best_index, _best_straddlers); #else //make the kids recompute it all _lokid->SubDivideWalkBboxes (NULL, -1, 0, 0); _hikid->SubDivideWalkBboxes (NULL, -1, 0, 0); #endif if (_best_list != given) delete[] _best_list; return; } void _KDTreeNode::UncachedFrustumQuery (int rw, const Frustum &f, MPObjList *inc, MPObjList *str, int clipnear) { CellFrustum dummycf (NULL, f, inc, str); ClipFrustum (rw, &dummycf, clipnear); } //if returns 0, it cached. IF it's a ray request, it'll set callerfrees to TRUE b/c it's not going to keep that list around. Otherwise it'll set callerfrees to FALSE b/c it'll use those lists (and clean them up) later. //if returns nonzero, it decided not to cache, and the lists weren't touched. int _KDTreeNode::FrustumQuery (int rw, const Frustum &f, int &callerfrees, MPObjList *&inc, MPObjList *&str, int clipnear) { if ((truly_GS->_disabled_flags & DISABLE_CELL_FRUSTUM_CACHE) || (_actual.Area() < truly_GS->_cf_cache_area_cutoff) || _skip_cache) { return 1; } if ( (truly_GS->_disabled_flags & DISABLE_RAY_CF_CACHE) && (f.XSize() == 1)) { return 1; } #ifndef NDEBUG _num_reqs.Add (_CS->_frame_id, f.XSize()); #endif // get enclosing frustum once if (!_frusta) { _frusta = new CachedCellFrustum (NULL, _enc); #ifdef SHOW_SMALLEST static int smallest = 10000; int oursize = _actual.XSize() * _actual.YSize(); if (oursize < smallest) { smallest = oursize; cerr << "new smallest " << oursize << endl; } #endif //cell might be partially off-screen; if so, clipping will do //some good. if (_clipped_actual || clipnear) { #ifndef NDEBUG _num_frusta_clipped.Add (_CS->_frame_id, _enc.XSize()); _total_num_frusta_clipped.Add (_CS->_frame_id, _enc.XSize()); #endif ClipFrustum (rw, _frusta, clipnear); } else { //we know every object in the cell will fit in this frustum; //that's why it's the enclosing one! just pack 'em in there. int num = _objs->Size(); ObjInfo *info; if (num > 0) _frusta->_empty = 0; for (int i = 0 ; i < num; i++) { info = &_obj_info[i]; if (info->_tfar < 0.) //cull out anything behind us. continue; _frusta->_inc->PlaceInList (info); } } //!needsclip } CellFrustum *cur = _frusta; CellFrustum *parent = NULL; int subdiv = 0; int numsubd = 0; int ourxsize = _enc.XSize(); int desiredxsize = f.XSize(); int wantsray = 0; int rayx, rayy; int minfsize = truly_GS->_min_frusta_size; if (desiredxsize == 1) { wantsray = 1; rayx = f._x1; rayy = f._y1; desiredxsize = truly_GS->_min_frusta_size; } //how many splits will we have to do? while (ourxsize > desiredxsize) { ourxsize >>= 1; ourxsize++; numsubd++; assert (ourxsize >= truly_GS->_min_frusta_size); } assert (desiredxsize == ourxsize); int kid, potentialkid; for (;;) //while ((numsubd > 0) && !cur->Empty()) { //optimization: we can make tighter object lists for the corners //of the frusta - we only want those objects that returned 0 for //both x and y split planes. if (truly_GS->_disabled_flags & ENABLE_BETTER_RAY_LISTS) { if (wantsray && cur->_f.HasCorner (rayx, rayy)) { inc = new MPObjList; str = new MPObjList; inc->PreAlloc (cur->_inc->Size() + cur->_str->Size()); MakeRayList (cur, rayx, rayy, inc); KDTree::_num_objs_culled_by_ray_lists += cur->_inc->Size() + cur->_str->Size() - inc->Size(); KDTree::_num_objs_not_culled_by_ray_lists += inc->Size(); callerfrees =1; break; } } if ((numsubd-- == 0) || (cur->_empty)) { //if the feature to give each ray its own list is enabled, //and we subdivided down to 2x2, then we should always //give a ray a list. //UNLESS the parent frusta becomes empty, in which case we //give it the parent's (empty) list. assert (!(truly_GS->_disabled_flags & ENABLE_BETTER_RAY_LISTS) || !wantsray || (cur->_empty) || (truly_GS->_min_frusta_size > 2)); inc = cur->_inc; str = cur->_str; callerfrees = 0; break; } assert (cur->_f.XSize() > truly_GS->_min_frusta_size); kid = WhichKidInclusive (cur->_f, f); assert (kid != -1); if (!cur->_kids[0]) { #ifndef NDEBUG subdiv = 1; _num_frustum_subdivides.Add (_CS->_frame_id, cur->_f.XSize()); _total_num_frustum_subdivides.Add (_CS->_frame_id, _actual.Area()); #endif //get the memory in one chunk char *mem = new char [sizeof (CachedCellFrustum) * 4]; if (!mem) { cerr << "ran out of memory subdividing a frustum!" << endl; assert (0); exit (0); } for (int i = 0; i < 4; i++) { //init each kid in place cur->_kids[i] = new (mem) CachedCellFrustum (cur, cur->_f); mem += sizeof (CachedCellFrustum); } //Subdivide gives us a grid like this: _kids[2] _kids[3] // _kids[0] _kids[1] cur->_f.Subdivide(cur->_kids[0]->_f, cur->_kids[1]->_f, cur->_kids[2]->_f, cur->_kids[3]->_f); //if the actual bbox doesn't lie along any of the //split planes of this frustum, its objects only //go into one kid. So we can skip those plane tests //and just distribute directly to the correct kid. //if the actual bbox lies on the split planes, that's //unacceptable, so we call WhichKid_Exclusive_ potentialkid = WhichKidExclusive (cur->_f, _actual); if (potentialkid == -1) { //make one alloc per list so we don't have to make //one per list _addition_ int maxsize = cur->_inc->Size() + cur->_str->Size(); int i; for (i = 0; i < 4; i++) { cur->_kids[i]->_inc->PreAlloc (maxsize); cur->_kids[i]->_str->PreAlloc (maxsize); } if ( (truly_GS->_disabled_flags & DISABLE_LP_SUBDIV) && (!clipnear) ) PartitionKids (cur); else PartitionKidsLP(rw, cur); PassDownStraddlers (cur); CellFrustum *kid; for (i = 0; i < 4; i++) { kid = cur->_kids[i]; if (kid->_inc->Size() || kid->_str->Size()) kid->_empty = 0; } } else { #ifndef NDEBUG _total_quick_subdivides.Add (_CS->_frame_id, _actual.Area()); _num_quick_subdivides.Add (_CS->_frame_id, cur->_f.XSize()); #endif cur->_kids[potentialkid]->_inc->PreAlloc (cur->_inc->Size()); //XXX could share, but there's the difficulty of workrec //promoting objects to straddling PassDownIncident (cur->_kids[potentialkid], cur); cur->_kids[potentialkid]->_empty = 0; assert (cur->_str->Size() == 0); } } parent = cur; cur = cur->_kids[kid]; assert (cur); } //while current frustum is too big, find/make a smaller one cur->_used ++; #ifndef NDEBUG assert (cur->_f.XSize() >= f.XSize()); if (cur->_f.XSize() != f.XSize()) assert (f.XSize() == 1 || cur->_empty); if (!subdiv) { _num_frustum_hits.Add (_CS->_frame_id, f.XSize()); _total_num_frustum_hits_by_cell_size.Add (_CS->_frame_id, _actual.Area()); _total_num_frustum_hits_by_req_size.Add (_CS->_frame_id, f.XSize()); } _total_num_frustum_reqs.Add (_CS->_frame_id, f.XSize()); #endif #ifndef NDEBUG int z; for (z = 0; z < inc->Size(); z++) { _num_objs_returned.Add (_CS->_frame_id, cur->_f.XSize()); _total_num_objs_returned.Add (_CS->_frame_id, _actual.Area()); } for (z = 0; z < str->Size(); z++) { _num_objs_returned.Add (_CS->_frame_id, cur->_f.XSize()); _total_num_objs_returned.Add (_CS->_frame_id, _actual.Area()); } int notused = 0; if (parent) // && parent->_used) { notused = parent->_str->Size() + parent->_inc->Size() - str->Size() - inc->Size() - str->Size(); } else { notused = _objs->Size() - str->Size() - inc->Size() - str->Size(); } for (z = 0; z < notused; z++) { _num_objs_not_returned.Add (_CS->_frame_id, cur->_f.XSize()); _total_num_objs_not_returned.Add (_CS->_frame_id, _actual.XSize() * _actual.YSize()); } #endif return 0; } void _KDTreeNode::Update (CycleState *CS) { assert (CS); _CS = CS; if (_frame_id != _CS->_frame_id) { #ifdef USE_LOCKS assert (_lock); _lock->Lock(); #endif if (_frame_id != _CS->_frame_id) //this cell hasn't been touched in this frame yet { #ifdef ONE_THREAD if (truly_GS->_kddraw_flags & DRAW_CELLS_ENTERED) { CS->_cells_entered.PlaceInList (this); // cerr << "added cell, now " << CS->_cells_entered.Size() << endl; } #endif if (_skip_cache) { _skip_cache--; } else { // if (_frusta && GetCacheEfficiencyPerc() < 1.0) // _skip_cache = -1; //XXX: Set to some positive #. } //clear the old frusta ClearOldFrusta(); if (!(truly_GS->_disabled_flags & DISABLE_CELL_FRUSTUM_CACHE)) { CalcEnclosingFrustum(); if ( (truly_GS->_disabled_flags & DISABLE_SMALL_CELL_WORK) && (_actual.Area() < truly_GS->_cf_cache_area_cutoff) ) return; } else { _enc.Set (0, 0, 128, 128); _actual.Set (0, 0, 128, 128); _unclipped_actual.Set (0, 0, 128, 128); _clipped_actual = 0; } #ifndef NDEBUG _total_num_cells_touched.Add (_CS->_frame_id, _actual.YSize() * _actual.XSize()); #endif //set up the per-cell plane cache and //sort the objects by viewvec T. Vec4 R (_CS->_camera.R()); Vec4 D (_CS->_camera.D()); float t1, t2; int num = _objs->Size(); ObjInfo *cur; Frustum clipped, unclipped; int didclip; int xsize =_CS->_camera.x(); int ysize =_CS->_camera.y(); for (int i = 0; i < num; i++) { KDTree::_num_objs_touched_dbl_count++; cur = &_obj_info[i]; if (cur->_obj->_num_touched_frame_id != _CS->_frame_id) { #ifdef ONE_THREAD if (truly_GS->_kddraw_flags & DRAW_OBJS_TOUCHED) _CS->_objs_checked.PlaceInList (cur->_obj); #endif cur->_obj->_num_touched_frame_id = _CS->_frame_id; cur->_obj->_num_visible_pixels = 0; cur->_obj->_num_intersect_attempts = 0; cur->_obj->_num_successful_intersects = 0; KDTree::_num_objs_touched++; } //initialize the plane cache if ((truly_GS->_disabled_flags & ENABLE_OBJ_SCRN_SPACE_BBOX_CALC) && (_actual.Area() >= truly_GS->_cf_cache_area_cutoff)) { CalcScreenSpaceBbox (_CS->_plane_cache, cur->_clipped_bbox, xsize, ysize, R, unclipped, clipped, didclip); cur->_known_pixel_lower_bound_out[X] = clipped._x1 - 1; cur->_known_pixel_lower_bound_out[Y] = clipped._y1 - 1; cur->_known_pixel_upper_bound_out[X] = clipped._x2 + 1; cur->_known_pixel_upper_bound_out[Y] = clipped._y2 + 1; cur->_known_pixel_upper_bound_in[X] = clipped._x2; cur->_known_pixel_upper_bound_in[Y] = clipped._y2; cur->_known_pixel_lower_bound_in[X] = clipped._x1; cur->_known_pixel_lower_bound_in[Y] = clipped._y1; } else { cur->_known_pixel_lower_bound_out[X] = cur->_known_pixel_lower_bound_out[Y] = cur->_known_pixel_upper_bound_in[X] = cur->_known_pixel_upper_bound_in[Y] = -1; cur->_known_pixel_upper_bound_out[X] = cur->_known_pixel_lower_bound_in[X] = xsize; cur->_known_pixel_upper_bound_out[Y] = cur->_known_pixel_lower_bound_in[Y] = ysize; } if (truly_GS->_disabled_flags & DISABLE_VIEWVEC_T) { cur->_tnear = 0.; cur->_tfar = 0.; } else { assert (_obj_info); calcTAlongViewVec (R, D, cur->_clipped_bbox, t1, t2); cur->_tnear = t1; cur->_tfar = t2; } } if ( (_obj_info) && (!(truly_GS->_disabled_flags & DISABLE_VIEWVEC_T)) ) { typedef int (*qsortfunc) (const void *, const void *); qsort (_obj_info, num, sizeof (ObjInfo), (qsortfunc)tnearsort); } _frame_id = _CS->_frame_id; } #ifdef USE_LOCKS _lock->UnLock(); #endif } #ifndef NDEBUG _num_times_touched.Add (CS->_frame_id, _actual.XSize() * _actual.YSize()); _total_num_times_touched.Add (CS->_frame_id, _actual.XSize() * _actual.YSize()); #endif } int _KDTreeNode::tnearsort (const ObjInfo *r1, const ObjInfo *r2) { float rnear1 = r1->_tnear; float rnear2 = r2->_tnear; if (rnear1 == rnear2) return 0; else if (rnear1 < rnear2) return -1; else return 1; } #define PPP 0 #define PPN 1 #define PNP 2 #define PNN 3 #define NPP 4 #define NPN 5 #define NNP 6 #define NNN 7 //XXX move into ray //also take out automatic ray classification; make it on the fly. int calcClass (const Vec4 &d) { if (d.x() >= 0.) { if (d.y() >= 0.) { if (d.z() >= 0.) { return PPP; } else { return PPN; } } else { if (d.z() >= 0.) { return PNP; } else { return PNN; } } } else { if (d.y() >= 0.) { if (d.z() >= 0.) { return NPP; } else { return NPN; } } else { if (d.z() >= 0.) { return NNP; } else { return NNN; } } } } void _KDTreeNode::calcTAlongViewVec (const Vec4 &R, const Vec4 &dir, const Bounds3d &bounds, float &tnear, float &tfar) { int rayclass = calcClass (dir); Vec4 near, far; switch (rayclass) { case NNN: near = bounds[1]; far = bounds[0]; break; case NNP: near = Vec4 (bounds[1].x(), bounds[1].y(), bounds[0].z()); far = Vec4 (bounds[0].x(), bounds[0].y(), bounds[1].z()); break; case NPN: near = Vec4 (bounds[1].x(), bounds[0].y(), bounds[1].z()); far = Vec4 (bounds[0].x(), bounds[1].y(), bounds[0].z()); break; case NPP: near = Vec4 (bounds[1].x(), bounds[0].y(), bounds[0].z()); far = Vec4 (bounds[0].x(), bounds[1].y(), bounds[1].z()); break; case PNN: near = Vec4 (bounds[0].x(), bounds[1].y(), bounds[1].z()); far = Vec4 (bounds[1].x(), bounds[0].y(), bounds[0].z()); break; case PNP: near = Vec4 (bounds[0].x(), bounds[1].y(), bounds[0].z()); far = Vec4 (bounds[1].x(), bounds[0].y(), bounds[1].z()); break; case PPN: near = Vec4 (bounds[0].x(), bounds[0].y(), bounds[1].z()); far = Vec4 (bounds[1].x(), bounds[1].y(), bounds[0].z()); break; case PPP: near = bounds[0]; far = bounds[1]; break; } //for the plane equation Ax + By + Cz + D = 0, figure out D at the eye //point (R). Since dir is the normal to the plane, its coords //are in fact the A, B, and C. //D = -Ax - By - Cz = -dir dot R float Deye = -dir.Dot3 (R); //now D provides the shifting factor - moving the plane around. Figure //out the D for the plane through the near and far points and take //the difference; that's the distance we need! tnear = dir.Dot3 (near) + Deye; tfar = dir.Dot3 (far) + Deye; assert (tnear <= tfar); } void _KDTreeNode::ClearOldFrusta(void) { delete _frusta; _frusta = NULL; } void _KDTreeNode::CalcFrustumPlanes (const Frustum &frustum, Plane *planes) { assert (planes); _CS->_planes_calced += _CS->_plane_cache->calcPlane (X, frustum.X_left(), planes[0]); _CS->_planes_calced += _CS->_plane_cache->calcPlane (X, frustum.X_right(), planes[1]); _CS->_planes_calced += _CS->_plane_cache->calcPlane (Y, frustum.Y_bottom(), planes[2]); _CS->_planes_calced += _CS->_plane_cache->calcPlane (Y, frustum.Y_top(), planes[3]); //change the right & top planes to point inward planes[1].TotalNegate(); planes[3].TotalNegate(); } //in order l,r,b,t please //LP needs rw # ObjLoc _KDTreeNode::ClassifyObject (int rw, const Bounds3d &bounds, const Frustum &frustum, ObjInfo *info, int clipnear) { _CS->_objs_classified++; if ((truly_GS->_disabled_flags & DISABLE_LP) && (!clipnear)) { int classL, classR, classB, classT; if ( ( classL = classify_plane_bbox ( X, frustum.X_left(), bounds, info )) < 0 ) { return out; } if ( ( classR = classify_plane_bbox ( X, frustum.X_right(), bounds, info ) ) > 0 ) { return out; } if ( ( classB = classify_plane_bbox ( Y, frustum.Y_bottom(), bounds, info) ) < 0 ) { return out; } if ( ( classT = classify_plane_bbox ( Y, frustum.Y_top(), bounds, info ) ) > 0 ) { return out; } //if we got here, the object's bbox is on the correct side of //all of these planes. It's probably inside them, but not //necessarily; this is a conservative test. #if 0 //now we lazily promote straddlers, so this isn't necessary. and it's usually wrong anyway. if ( classL == 0 && classR == 0 && classB == 0 && classT == 0 && !(truly_GS->_disabled_flags & DISABLE_STRADDLERS) ) return straddling; else #endif return incident; } else { #ifndef VIS_ALONE Vec4 witness; int halfspaces_incident_axialbox (const Plane* peqn, int n, const Bounds3d& box, Point3d *witness, LPMem *lpmem ); assert (rw >= 0 && rw < RWNUM); Plane planes[4]; CalcFrustumPlanes (frustum, planes); if (halfspaces_incident_axialbox (planes, 4, bounds, &witness, RW(rw)->GetLPMem())) return incident; else return out; #endif } } //6 float adds //6 float mults //4 float compares int _KDTreeNode::classify_plane_bbox ( const Plane &H, const Bounds3d &box) { Vec4 pmin (box.x1(), box.y1(), box.z1()); Vec4 pmax (box.x2(), box.y2(), box.z2()); float dmin = H.w(), dmax = H.w(); if ( H.x() < 0 ) { dmin += H.x() * pmax.x(); dmax += H.x() * pmin.x(); } else { dmin += H.x() * pmin.x(); dmax += H.x() * pmax.x(); } if ( H.y() < 0 ) { dmin += H.y() * pmax.y(); dmax += H.y() * pmin.y(); } else { dmin += H.y() * pmin.y(); dmax += H.y() * pmax.y(); } if ( H.z() < 0 ) { dmin += H.z() * pmax.z(); dmax += H.z() * pmin.z(); } else { dmin += H.z() * pmin.z(); dmax += H.z() * pmax.z(); } if ( dmin > 0 ) { _CS->_num_classified_to_one_side++; return 1; } else if ( dmax < 0 ) { _CS->_num_classified_to_one_side++; return -1; } else { _CS->_num_classified_straddling++; return 0; } } int _KDTreeNode::classify_neg_plane_bbox ( int dim, int where, const Bounds3d &bbox, ObjInfo *info) { assert (1==0); return -classify_plane_bbox (dim, where, bbox, info); } // return -1 if box lies in H- // return +1 if box lies in H+ // return 0 if box straddles H int _KDTreeNode::classify_plane_bbox ( int dim, int where, const Bounds3d &box, ObjInfo *info) { // cerr << "requesting " << dim << " " << where << endl; _CS->_plane_tests_requested++; if (info && (truly_GS->_disabled_flags & ENABLE_PLANE_CACHE_OUT)) { //the object is known to lie >= lower_bound_in and <= upper_bound_in //it's also known to not be < lower_bound_out and > upper_bound_out if (info->_known_pixel_lower_bound_out [dim] >= where) { //our object's known lower bound is above the plane we're asking for. //so we know the object is above the plane. return 1. // cerr << "hit" << endl; _CS->_num_classified_to_one_side++; return 1; } if (info->_known_pixel_upper_bound_out [dim] <= where) { //our object's known upper bound is below the plane we're asking for. // cerr << "hit2" << endl; //so we know the object is below the plane. return -1. _CS->_num_classified_to_one_side++; return -1; } } if (info && (truly_GS->_disabled_flags & ENABLE_PLANE_CACHE_IN)) { if ( (where >= info->_known_pixel_lower_bound_in [dim]) && (where <= info->_known_pixel_upper_bound_in [dim]) ) { _CS->_num_classified_straddling++; return 0; } } #ifndef NDEBUG //if we missed using the plane cache, we better have either //disabled the plane cache, not been given the plane cache entry (!info) //or disabled the screen-space precalcing. if ((truly_GS->_disabled_flags & ENABLE_PLANE_CACHE_IN) && (truly_GS->_disabled_flags & ENABLE_PLANE_CACHE_OUT)) assert (!info || !(truly_GS->_disabled_flags & ENABLE_OBJ_SCRN_SPACE_BBOX_CALC)); #endif _CS->_planes_tested++; Plane H; _CS->_planes_calced += _CS->_plane_cache->calcPlane (dim, where, H); Vec4 pmin = box[0]; Vec4 pmax = box[1]; float dmin = H.w(), dmax = H.w(); if ( H.x() < 0 ) { dmin += H.x() * pmax.x(); dmax += H.x() * pmin.x(); } else { dmin += H.x() * pmin.x(); dmax += H.x() * pmax.x(); } if ( H.y() < 0 ) { dmin += H.y() * pmax.y(); dmax += H.y() * pmin.y(); } else { dmin += H.y() * pmin.y(); dmax += H.y() * pmax.y(); } if ( H.z() < 0 ) { dmin += H.z() * pmax.z(); dmax += H.z() * pmin.z(); } else { dmin += H.z() * pmin.z(); dmax += H.z() * pmax.z(); } #ifdef FIND_PLANE_CACHE_BUG if ((dmin > 0) || (dmax < 0)) { if (where == 48) cerr << "classified 48, " << H << " as not straddling " << box << endl; if ( (where >= obj->_known_pixel_lower_bound_in [dim]) && (where <= obj->_known_pixel_upper_bound_in [dim]) ) { cerr << "lower was " << obj->_known_pixel_lower_bound_in [dim]; cerr << " upper was " << obj->_known_pixel_upper_bound_in [dim]; cerr << endl << " yet " << where << " wasn't 0!" << endl; Plane lowerplane, upperplane; _CS->_plane_cache->calcPlane (dim, obj->_known_pixel_lower_bound_in[dim], lowerplane); _CS->_plane_cache->calcPlane (dim, obj->_known_pixel_upper_bound_in[dim], upperplane); if (classify_plane_bbox ( lowerplane, obj->bbox()) != 0) cerr << "lower bound no good!" << endl; else if (classify_plane_bbox ( upperplane, obj->bbox()) != 0) cerr << "upper bound no good!" << endl; else cerr << "both were 0!" << endl; } } else { if (where == 48) cerr << "classified 48, " << H << " as straddling " << box << endl; } #endif if ( dmin > 0 ) { if (info && (truly_GS->_disabled_flags & ENABLE_PLANE_CACHE_OUT)) info->_known_pixel_lower_bound_out [dim] = where; // cerr << "lower " << dim << " set to " << where << endl; // cerr << "hard calced 1" << endl; _CS->_num_classified_to_one_side++; return 1; } else if ( dmax < 0 ) { if (info && (truly_GS->_disabled_flags & ENABLE_PLANE_CACHE_OUT)) info->_known_pixel_upper_bound_out [dim] = where; // cerr << "higher " << dim << " set to " << where << endl; // cerr << "hard calced -1" << endl; _CS->_num_classified_to_one_side++; return -1; } else { _CS->_num_classified_straddling++; // cerr << "hard calced 0 at " << (char)('X' + dim) << " " << where << " for " << box << endl; if (info && (truly_GS->_disabled_flags & ENABLE_PLANE_CACHE_IN)) { if (where < info->_known_pixel_lower_bound_in[dim]) info->_known_pixel_lower_bound_in[dim] = where; if (where > info->_known_pixel_upper_bound_in[dim]) info->_known_pixel_upper_bound_in[dim] = where; // cerr << "changed range to " << info->_known_pixel_lower_bound_in[dim] << " to " << info->_known_pixel_upper_bound_in[dim] << endl; } else if (info) { // cerr << "maintained range of " << info->_known_pixel_lower_bound_in[dim] << " to " << info->_known_pixel_upper_bound_in[dim] << endl; } else { // cerr << "no info" << endl; } return 0; } } // partition incident objects with respect to split plane //this is the money routine for frustum culling. void _KDTreeNode::partition (MPObjList *objs, int dim, int low, int split, int high, MPObjList *lowincident, MPObjList *lowstraddle, MPObjList *highincident, MPObjList *highstraddle) { assert ((dim == 0) || (dim == 1)); assert ( (objs) && (lowincident) && (lowstraddle) && (highincident) && (highstraddle)); const void *place; objs->Reset (place); int classH; // int classB; //bounding plane result RayCastable *obj; ObjInfo *info; while (place) { #ifndef NDEBUG _num_objs_partitioned.Add (_CS->_frame_id, high - low + 1); _total_num_objs_partitioned.Add (_CS->_frame_id, high - low + 1); #endif info = objs->Peek (place); obj = info->_obj; objs->Next (place); assert (obj); classH = classify_plane_bbox ( dim, split, info->_clipped_bbox, info); #ifndef NDEBUG if (classH == 0) { _CS->_num_straddles_kids++; _total_num_straddling_objs.Add (_frame_id, high - low + 1); } else { _CS->_num_on_one_side_of_kids++; _total_num_one_side_objs.Add (_frame_id, high - low + 1); } #endif if ( classH <= 0 ) { #if 0 classB = classify_plane_bbox ( dim, low, info->_clipped_bbox, info); if (classB < 0) { cerr << "Err: object was left of low " << (char)('X' + dim) << " plane " << low << endl; #ifdef DISABLE_LOG _CS->AddErrorBbox (obj->bbox()); #endif //continue; //XXX; what's happening here? } //we have to do the sorting because, although parent //incident & straddling lists are sorted, //some incidents could be combined with straddlers, and //they'll need to be sortd out if ((classB == 0) && (classH == 0)) lowstraddle->PlaceInSortedList (info, _KDTreeNode::tnearsort); else #endif if (truly_GS->_disabled_flags & DISABLE_VIEWVEC_T) lowincident->PlaceInList (info); else lowincident->PlaceInSortedList (info, _KDTreeNode::tnearsort); } if ( classH >= 0 ) { #if 0 classB = classify_plane_bbox ( dim, high, info->_clipped_bbox, info); if (classB > 0) { cerr << "Err: object was right of high " << (char)('X' + dim) << " plane " << high << endl; //continue; //XXX; what's happening here? #ifdef DISABLE_LOG _CS->AddErrorBbox (obj->bbox()); #endif } if ((classB == 0) && (classH == 0)) highstraddle->PlaceInSortedList (info, _KDTreeNode::tnearsort); else #endif if (truly_GS->_disabled_flags & DISABLE_VIEWVEC_T) highincident->PlaceInList (info); else highincident->PlaceInSortedList (info, _KDTreeNode::tnearsort); } } } void _KDTreeNode::PartitionKids (CellFrustum *cf) { assert (cf->_kids[0]); //make sure we've got kids to partition! int maxsize = cf->_inc->Size(); //CFT straddlers really aren't used; no need for them! MPObjList ylowincident; MPObjList ylowstraddlers; MPObjList yhighincident; MPObjList yhighstraddlers; ylowincident.PreAlloc (maxsize); //ylowstraddlers.PreAlloc (maxsize); yhighincident.PreAlloc (maxsize); //yhighstraddlers.PreAlloc (maxsize); //partition into top & bottom partition (cf->_inc, Y, cf->_f.Y_bottom(), cf->_kids[0]->_f.Y_top(), cf->_f.Y_top(), &ylowincident, &ylowstraddlers, &yhighincident, &yhighstraddlers); //partition those four lists into left & right //ylow and yhigh could be the same. XXX why? if (truly_GS->_disabled_flags & DISABLE_STRADDLERS) { //everyone -> incident partition (&ylowstraddlers, X, cf->_f.X_left(), cf->_kids[0]->_f.X_right(), cf->_f.X_right(), cf->_kids[0]->_inc, cf->_kids[0]->_inc, cf->_kids[1]->_inc, cf->_kids[1]->_inc); partition (&yhighstraddlers, X, cf->_f.X_left(), cf->_kids[0]->_f.X_right(), cf->_f.X_right(), cf->_kids[2]->_inc, cf->_kids[2]->_inc, cf->_kids[3]->_inc, cf->_kids[3]->_inc); } else { //straddlers in y -> incident or straddlers partition (&ylowstraddlers, X, cf->_f.X_left(), cf->_kids[0]->_f.X_right(), cf->_f.X_right(), cf->_kids[0]->_inc, cf->_kids[0]->_str, cf->_kids[1]->_inc, cf->_kids[1]->_str); partition (&yhighstraddlers, X, cf->_f.X_left(), cf->_kids[0]->_f.X_right(), cf->_f.X_right(), cf->_kids[2]->_inc, cf->_kids[2]->_str, cf->_kids[3]->_inc, cf->_kids[3]->_str); } //if it was incident in y, it's never gonna be a frustum //straddler. Throw all the results into incident lists partition (&yhighincident, X, cf->_f.X_left(), cf->_kids[0]->_f.X_right(), cf->_f.X_right(), cf->_kids[2]->_inc, cf->_kids[2]->_inc, cf->_kids[3]->_inc, cf->_kids[3]->_inc); partition (&ylowincident, X, cf->_f.X_left(), cf->_kids[0]->_f.X_right(), cf->_f.X_right(), cf->_kids[0]->_inc, cf->_kids[0]->_inc, cf->_kids[1]->_inc, cf->_kids[1]->_inc); ylowincident.Clear(); ylowstraddlers.Clear(); yhighincident.Clear(); yhighstraddlers.Clear(); } int KDTree::IsInFrustum (CycleState *CS, int rwnum, const Frustum &f) { if (!_root) return 0; _root->Update (CS); if (out == _root->ClassifyObject (rwnum, _root->_bounds, f)) { #ifdef DISABLE_LOG RW(rwnum)->_num_objs_out_frusta++; #endif return 0; } else { #ifdef DISABLE_LOG RW(rwnum)->_num_objs_in_frusta++; #endif return 1; } } void _KDTreeNode::PartitionKidsLP (int rw, CellFrustum *cf) { #ifdef FIND_BUG if ( (cf->_f.X_left() == 0) && (cf->_f.X_right() == 64) && (cf->_f.Y_top() == 128) && (cf->_f.Y_bottom() == 64)); cerr << "aha!"; #endif #if 0 Plane top, bottom, left, right, xmiddle, ymiddle; _CS->_planes_calced += _CS->_plane_cache->calcPlane (X, cf->_f.X_left(), left); _CS->_planes_calced += _CS->_plane_cache->calcPlane (X, cf->_f.X_right(), right); _CS->_planes_calced += _CS->_plane_cache->calcPlane (Y, cf->_f.Y_bottom(), bottom); _CS->_planes_calced += _CS->_plane_cache->calcPlane (Y, cf->_f.Y_top(), top); _CS->_planes_calced += _CS->_plane_cache->calcPlane (X, _kids[0]->cf->_f.X_right(), xmiddle); _CS->_planes_calced += _CS->_plane_cache->calcPlane (Y, _kids[0]->cf->_f.Y_top(), ymiddle); //change the right & top planes to point inward right.TotalNegate(); top.TotalNegate(); Plane planes[4][4]; #define L 0 #define R 1 #define B 2 #define T 3 planes[BL][L] = left; planes[BL][R] = xmiddle; planes[BL][R].TotalNegate(); planes[BL][T] = ymiddle; planes[BL][T].TotalNegate(); planes[BL][B] = bottom; planes[TL][L] = left; planes[TL][R] = xmiddle; planes[TL][R].TotalNegate(); planes[TL][T] = top; planes[TL][B] = ymiddle; planes[BR][L] = xmiddle; planes[BR][R] = right; planes[BR][T] = ymiddle; planes[BR][T].TotalNegate(); planes[BR][B] = bottom; planes[TR][L] = xmiddle; planes[TR][R] = right; planes[TR][T] = top; planes[TR][B] = ymiddle; #endif ObjLoc loc; int i; const void *place; cf->_inc->Reset (place); ObjInfo *info; while (place) { info = cf->_inc->Peek(place); cf->_inc->Next (place); for (i = 0; i < 4; i++) { loc = ClassifyObject (rw, info->_clipped_bbox, cf->_kids[i]->_f); switch (loc) { case straddling: cf->_kids[i]->_str->PlaceInList (info); break; case incident: cf->_kids[i]->_inc->PlaceInList (info); break; case out: break; default: cerr << "classify obj returned unknown class in PartitionKidsLP" << endl; } } } } void _KDTreeNode::PassDownStraddlers (CellFrustum *cf) { MPObjList *str = cf->_str; int ssize = str->Size(); ObjInfo *info; const void *place; str->Reset (place); float prevnear = -MAXFLOAT; #ifdef CHECK_KIDSTRADDLER_SORTEDNESS //straddlers should stay sorted by tnear. prevnear = -MAXFLOAT; void *cplace; cf->_kids[0]->_str->Reset (cplace); while (cplace) { ObjInfo *info = cf->_kids[0]->_str->Peek (cplace); if (info->_tnear < prevnear) { cerr << "b4 kid straddler info->_tnear is " << info->_tnear << ", prevnear is " << prevnear << endl; } prevnear = info->_tnear; cf->_kids[0]->_str->Next (cplace); } #endif prevnear = -MAXFLOAT; for (int i = 0; i < ssize; i++) { assert (place); info = str->Peek (place); str->Next (place); #ifndef NDEBUG //they should already be sorted by tnear. if (info->_tnear < prevnear) { cerr << "straddler info->_tnear is " << info->_tnear << ", prevnear is " << prevnear << endl; } prevnear = info->_tnear; #endif //gotta place in sorted list because the kid may already have straddlers //in it and we need to preserve sorting order. cf->_kids[0]->_str->PlaceInSortedList (info, _KDTreeNode::tnearsort); cf->_kids[1]->_str->PlaceInSortedList (info, _KDTreeNode::tnearsort); cf->_kids[2]->_str->PlaceInSortedList (info, _KDTreeNode::tnearsort); cf->_kids[3]->_str->PlaceInSortedList (info, _KDTreeNode::tnearsort); } assert (!place); } //give vector from eye to the desired point void GetScreenSpace (PlaneCache *pc, const Vec4 &vec, int xsize, int ysize, int &x, int &y) { KDTree::_num_screen_space_conversions++; Vec4 xhat, yhat, zhat; pc->getHats (xhat, yhat, zhat); float xl = xhat.Length(); float yl = yhat.Length(); float zl = zhat.Length(); float x1 = (xhat * (1./ xl)).Dot3 (vec) / xl; float y1 = (yhat * (1. / yl)).Dot3 (vec) / yl; float z1 = (zhat * (1. / zl)).Dot3 (vec) / zl; // cerr << "original vec: " << vec << endl; // cerr << "xyz components: " << x1 << ", " << y1 << ", " << z1 << endl; // cerr << "recombined vec: " << (xhat * x1 + yhat * y1 + zhat * z1) << endl; if (z1 < 0.) z1 = -z1; //1. / z1; x1 /= z1; x1 += 1.; x1 *= real(xsize) / 2.; y1 /= z1; y1 += 1.; y1 *= real(ysize) / 2.; x = x1 - 1; y = y1 - 1; } //unclipped is not clipped to the given screen size; clipped is //didclip is nonzero if the two are different (aka, if we clipped) void CalcScreenSpaceBbox (PlaneCache *pc, const Bounds3d &box, int xsize, int ysize, const Vec4 &eye, Frustum &unclipped, Frustum &clipped, int &didclip) { int x, y; Vec4 cur; for (int j = 0; j < 2; j++) { for (int i = 0; i < 2; i++) { for (int k = 0; k < 2; k++) { cur[0] = box[j][0]; cur[1] = box[i][1]; cur[2] = box[k][2]; // cerr << "computing for " << cur << endl; GetScreenSpace (pc, cur - eye, xsize, ysize, x, y); if (i == 0 && j == 0 && k == 0) { unclipped.Set (x, y, x, y); continue; } //pull out the upper left if (x < unclipped._x1) {unclipped._x1 = x;} if (y < unclipped._y1) {unclipped._y1 = y;} //pull out the lower right if (x > unclipped._x2) {unclipped._x2 = x;} if (y > unclipped._y2) {unclipped._y2 = y;} } } } didclip = 0; //clip! x = unclipped._x1; y = unclipped._y1; if (x < 0) { x = 0; didclip = 1;} if (y < 0) { y = 0; didclip = 1;} if (x >= xsize) {x = xsize - 1; didclip = 1;} if (y >= ysize) {y = ysize - 1; didclip = 1;} int x2 = unclipped._x2; int y2 = unclipped._y2; if (x2 < 0) { x2 = 0; didclip = 1;} if (y2 < 0) { y2 = 0; didclip = 1;} if (x2 >= xsize) {x2 = xsize - 1; didclip = 1;} if (y2 >= ysize) {y2 = ysize - 1; didclip = 1;} clipped.Set (x, y, x2, y2); } void _KDTreeNode::CalcEnclosingFrustum (void) { int size = _CS->_camera.x(); CalcScreenSpaceBbox (_CS->_plane_cache, _bounds, size, size, _CS->_camera.R(), _unclipped_actual, _actual, _clipped_actual); // cerr << "_actual is " << _actual << endl; _enc.Set (0,0,size - 1, size - 1); int kid; while (_enc.XSize() >= 3) { assert (_actual._x1 >= _enc._x1 && _actual._x2 <= _enc._x2 && _actual._y1 >= _enc._y1 && _actual._y2 <= _enc._y2); kid = WhichKidInclusive (_enc, _actual); if (kid == -1) return; switch (kid) { case BL: _enc._x2 = _enc.HalfX(); _enc._y2 = _enc.HalfY(); break; case BR: _enc._x1 = _enc.HalfX(); _enc._y2 = _enc.HalfY(); break; case TL: _enc._x2 = _enc.HalfX(); _enc._y1 = _enc.HalfY(); break; case TR: _enc._x1 = _enc.HalfX(); _enc._y1 = _enc.HalfY(); break; default: cerr << "ERR: new whichkid return val " << kid << endl; return; } } return; } //which kid of big does small fit into? touching split planes is ok //bottom is at y = 0; //BL, TL, TR, BR, or -1 if it's on a border. int _KDTreeNode::WhichKidInclusive (const Frustum &big, const Frustum &small) { int halfy = big.HalfY(); int halfx = big.HalfX(); if (small._y2 <= halfy) { //it's below the middle line if (small._x2 <= halfx) { return BL; } else if (small._x1 >= halfx) { return BR; } else return -1; } else if (small._y1 >= halfy) { //it's above the middle line if (small._x2 <= halfx) { return TL; } else if (small._x1 >= halfx) { return TR; } else return -1; } else //it straddles the middle line return -1; } //which kid of big does small fit into? touching split planes is *not* ok //bottom is at y = 0; //BL, TL, TR, BR, or -1 if it's on a border. int _KDTreeNode::WhichKidExclusive (const Frustum &big, const Frustum &small) { int halfy = big.HalfY(); int halfx = big.HalfX(); if (small._y2 < halfy) { //it's below the middle line if (small._x2 < halfx) { return BL; } else if (small._x1 > halfx) { return BR; } else return -1; } else if (small._y1 > halfy) { //it's above the middle line if (small._x2 < halfx) { return TL; } else if (small._x1 > halfx) { return TR; } else return -1; } else //it straddles the middle line return -1; } CellFrustum::CellFrustum (CellFrustum *parent, const Frustum &f, MPObjList *inc, MPObjList *str) : _f(f), _inc (inc), _str (str), _used (0), _empty (1), _parent (parent) { for (int i = 0; i < 4; i ++) _kids[i] = NULL; } void _KDTreeNode::ClipFrustum (int rw, CellFrustum *cf, int clipnear) { ObjInfo *info; ObjLoc loc; int num = _objs->Size(); for (int i = 0 ; i < num; i++) { info = &_obj_info[i]; if (info->_tfar < 0.) //cull out anything behind us. continue; cf->_empty = 0; loc = ClassifyObject (rw, info->_clipped_bbox, cf->_f, info, clipnear); assert (rw >= 0); switch (loc) { case straddling: cf->_str->PlaceInList (info); #ifdef DISABLE_LOG RW(rw)->_num_objs_in_frusta++; #endif break; case incident: cf->_inc->PlaceInList (info); #ifdef DISABLE_LOG RW(rw)->_num_objs_in_frusta++; #endif break; case out: #ifdef DISABLE_LOG RW(rw)->_num_objs_out_frusta++; #endif break; default: cerr << "kdcell::calcfrustum got new enum back from ClassifyObject" << endl; break; } } } int _KDTreeNode::Intersect(int rw, int x, int y,const Ray &ray, Hit &hit, _KDTreeNode *previous, int drawing_flags, CycleState *CS) { Update (CS); MPObjList *inc, *str; Frustum f (x, y, x, y); int mustfreelists; if (FrustumQuery (rw, f, mustfreelists, inc, str)) { if (truly_GS->_disabled_flags & DISABLE_SMALL_CELL_WORK) return 1; OldIntersect (ray, hit, previous, drawing_flags, CS); return 0; } PlaneCache *pc = NULL; if (!(truly_GS->_disabled_flags & DISABLE_VIEWVEC_T)) pc = _CS->_plane_cache; if (drawing_flags & DRAW_CELLS) { glColor3fv (cell_color); _bounds.drawWireFrame (); } KDTREELOG (KDTreeNodeNewIntersect_Start, new KDTreeNodeNewIntersect_Start_Entry (this, x, y, inc->Size() + str->Size())); Stats stats; stats.num_intersect_calls = &KDTree::_new_intersect_count; stats.num_bbox_successes = &KDTree::_new_bbox_success_count; stats.num_intersect_successes = &KDTree::_new_intersect_success_count; stats.num_intersections_overruled = &KDTree::_num_intersects_overruled; stats.num_axis_checks = &KDTree::_num_axis_checks; stats.num_axis_check_successes = &KDTree::_num_axis_checks_successes; stats.num_axis_check_had_to_fail = &KDTree::_num_axis_check_had_to_fail; int options = 0; if (truly_GS->_disabled_flags & ENABLE_FCULLED_RAY_BBOX_TESTS) options |= BBOX_CHECK; if (truly_GS->_disabled_flags2 & ENABLE_3_AXIS_CHECK) options |= CHECK_3_AXIS; if (truly_GS->_disabled_flags2 & ENABLE_1_AXIS_CHECK) options |= CHECK_1_AXIS; if (str->Size() > 0) IntersectObjList (*_CS, x, y, ray, str, hit, pc, options, drawing_flags, stats); if (inc->Size() > 0) IntersectObjList (*_CS, x, y, ray, inc, hit, pc, options, drawing_flags, stats); KDTREELOG (KDTreeNodeNewIntersect_End, new KDTreeNodeNewIntersect_End_Entry (this, x, y, hit.obj ? 1 : 0)); if (mustfreelists) { delete inc; delete str; } return 0; } void _KDTreeNode::PartitionKids (WorkRec *wr) { #ifndef VIS_ALONE assert (wr->_kids[0]); //make sure we've got kids to partition! MPObjList *ylowincident = new MPObjList(); MPObjList *ylowstraddlers = new MPObjList(); MPObjList *yhighincident = new MPObjList(); MPObjList *yhighstraddlers = new MPObjList(); //partition into top & bottom partition (wr->_incident, Y, wr->_frustum.Y_bottom(), wr->_kids[0]->_frustum.Y_top(), wr->_frustum.Y_top(), ylowincident, ylowstraddlers, yhighincident, yhighstraddlers); //partition those four lists into left & right //ylow and yhigh could be the same. XXX why? if (truly_GS->_disabled_flags & DISABLE_STRADDLERS) { //everyone -> incident partition (ylowstraddlers, X, wr->_frustum.X_left(), wr->_kids[0]->_frustum.X_right(), wr->_frustum.X_right(), wr->_kids[0]->_incident, wr->_kids[0]->_incident, wr->_kids[1]->_incident, wr->_kids[1]->_incident); partition (yhighstraddlers, X, wr->_frustum.X_left(), wr->_kids[0]->_frustum.X_right(), wr->_frustum.X_right(), wr->_kids[2]->_incident, wr->_kids[2]->_incident, wr->_kids[3]->_incident, wr->_kids[3]->_incident); } else { //straddlers in y -> incident or straddlers partition (ylowstraddlers, X, wr->_frustum.X_left(), wr->_kids[0]->_frustum.X_right(), wr->_frustum.X_right(), wr->_kids[0]->_incident, wr->_kids[0]->_straddlers, wr->_kids[1]->_incident, wr->_kids[1]->_straddlers); partition (yhighstraddlers, X, wr->_frustum.X_left(), wr->_kids[0]->_frustum.X_right(), wr->_frustum.X_right(), wr->_kids[2]->_incident, wr->_kids[2]->_straddlers, wr->_kids[3]->_incident, wr->_kids[3]->_straddlers); } //if it was incident in y, it's never gonna be a frustum //straddler. Throw all the results into incident lists partition (yhighincident, X, wr->_frustum.X_left(), wr->_kids[0]->_frustum.X_right(), wr->_frustum.X_right(), wr->_kids[2]->_incident, wr->_kids[2]->_incident, wr->_kids[3]->_incident, wr->_kids[3]->_incident); partition (ylowincident, X, wr->_frustum.X_left(), wr->_kids[0]->_frustum.X_right(), wr->_frustum.X_right(), wr->_kids[0]->_incident, wr->_kids[0]->_incident, wr->_kids[1]->_incident, wr->_kids[1]->_incident); delete ylowincident; delete ylowstraddlers; delete yhighincident; delete yhighstraddlers; #endif } void _KDTreeNode::PartitionKidsLP (int rw, WorkRec *wr) { #ifndef VIS_ALONE #ifdef FIND_BUG if ( (wr->_frustum.X_left() == 0) && (wr->_frustum.X_right() == 64) && (wr->_frustum.Y_top() == 128) && (wr->_frustum.Y_bottom() == 64)); cerr << "aha!"; #endif #if 0 Plane top, bottom, left, right, xmiddle, ymiddle; wr->_CS->_planes_calced += wr->_CS->_plane_cache->calcPlane (X, wr->_frustum.X_left(), left); wr->_CS->_planes_calced += wr->_CS->_plane_cache->calcPlane (X, wr->_frustum.X_right(), right); wr->_CS->_planes_calced += wr->_CS->_plane_cache->calcPlane (Y, wr->_frustum.Y_bottom(), bottom); wr->_CS->_planes_calced += wr->_CS->_plane_cache->calcPlane (Y, wr->_frustum.Y_top(), top); wr->_CS->_planes_calced += wr->_CS->_plane_cache->calcPlane (X, _kids[0]->_frustum.X_right(), xmiddle); wr->_CS->_planes_calced += wr->_CS->_plane_cache->calcPlane (Y, _kids[0]->_frustum.Y_top(), ymiddle); //change the right & top planes to point inward right.TotalNegate(); top.TotalNegate(); Plane planes[4][4]; #define L 0 #define R 1 #define B 2 #define T 3 planes[BL][L] = left; planes[BL][R] = xmiddle; planes[BL][R].TotalNegate(); planes[BL][T] = ymiddle; planes[BL][T].TotalNegate(); planes[BL][B] = bottom; planes[TL][L] = left; planes[TL][R] = xmiddle; planes[TL][R].TotalNegate(); planes[TL][T] = top; planes[TL][B] = ymiddle; planes[BR][L] = xmiddle; planes[BR][R] = right; planes[BR][T] = ymiddle; planes[BR][T].TotalNegate(); planes[BR][B] = bottom; planes[TR][L] = xmiddle; planes[TR][R] = right; planes[TR][T] = top; planes[TR][B] = ymiddle; #endif ObjLoc loc; int i; const void *place; wr->_incident->Reset (place); ObjInfo *info; Bounds3d bounds; while (place) { info = wr->_incident->Peek(place); wr->_incident->Next (place); for (i = 0; i < 4; i++) { loc = ClassifyObject (rw, info->_clipped_bbox, wr->_kids[i]->_frustum); switch (loc) { case straddling: wr->_kids[i]->_straddlers->PlaceInList (info); break; case incident: wr->_kids[i]->_incident->PlaceInList (info); break; case out: break; default: cerr << "classify obj returned unknown class in PartitionKidsLP" << endl; } } } #endif } //when we know that all the objects in src actually lie within //a certain quadrant of src, we pass them directly to the right kid. void _KDTreeNode::PassDownIncident (CellFrustum *dst, CellFrustum *src) { MPObjList *srcinc = src->_inc; MPObjList *dstinc = dst->_inc; int isize = srcinc->Size(); const void *place; srcinc->Reset (place); while (place) { dstinc->PlaceInList (srcinc->Peek (place)); srcinc->Next (place); } } void _KDTreeNode::CornerRays (const Frustum &f, Vec4 rays[4]) { int corner[4][2]; corner[0][0] = f._x1; corner[0][1] = f._y1; corner[1][0] = f._x1; corner[1][1] = f._y2; corner[2][0] = f._x2; corner[2][1] = f._y2; corner[3][0] = f._x2; corner[3][1] = f._y1; float ratio; //get each corner ray and project it out to lie on the same //eye-space Z plane as the cell center. //distance to cellcenter from eye point along viewvec is zproj //or, zproj = dist from eye to eye-space Z plane of the cell's center. Vec4 eye = _CS->_camera.R(); Vec4 tocenter = .5 * (_bounds[0] + _bounds[1]) - eye; float zproj = _CS->_camera.D().Dot3 (tocenter); int i; for (i = 0; i < 4; i++) { //1 unit along viewvec is ratio along corner ray ratio = 1. / _CS->_plane_cache->ComputeViewVecT (corner[i][0], corner[i][1], 1.); _CS->_plane_cache->ComputeEyeRayDirection (corner[i][0], corner[i][1], rays[i]); rays[i] *= zproj * ratio; } } void _KDTreeNode::DrawFrustumCache (int kidstoo, CellFrustum *cur) { int i; if (!cur) { cur = _frusta; } if (cur) { if (cur->_kids[0]) { for (i = 0; i < 4; i++) { assert (cur->_kids[i]); DrawFrustumCache (0, cur->_kids[i]); } } else { assert (cur->_inc); assert (cur->_str); Vec4 cornerray[4]; CornerRays (cur->_f, cornerray); Vec4 eye = _CS->_camera.R(); glColor3f (0., 1., 0.); glBegin (GL_LINE_LOOP); for (i = 0; i < 4; i++) { glVertex3fv ((eye + cornerray[i]).ArrayForGL()); } glEnd(); glEnable (GL_BLEND); glBlendFunc (GL_CONSTANT_ALPHA_EXT, GL_ONE_MINUS_CONSTANT_ALPHA_EXT); glBlendColorEXT (0, 0, 0, .7); float r, g, b; r = g = b = 0.; // scale = (.1 * (cur->_inc->Size() + cur->_str->Size())); if (truly_GS->_frusta_flags & DRAW_CF_CACHE_OBJS) { if (!cur->_empty) b = 1.0; } if (truly_GS->_frusta_flags & DRAW_CF_CACHE_HITS) { if (cur->_used) r = g = 1.0; } //blue shows whether there was an object there //yellow shows whether we hit or not. glColor3f (r, g, b); glBegin (GL_QUADS); for (i = 0; i < 4; i++) { glVertex3fv ((eye + cornerray[i]).ArrayForGL()); } glEnd(); glDisable (GL_BLEND); } } if (kidstoo && !_is_leaf) { _lokid->DrawFrustumCache (kidstoo); _hikid->DrawFrustumCache (kidstoo); } } float _KDTreeNode::GetCacheEfficiencyPerc (void) { if (!_frusta) return 0.0; int used = 0; int numcf = _frusta->TallyNum(); assert (numcf > 0.); used = _frusta->TallyUsed(); assert (used > 0.); return float (used) / float (numcf); } float _KDTreeNode::GetCacheHitPerc (void) { if (!_frusta) return 0.; int hit = _num_frustum_hits.Total(); int entered = _num_reqs.Total(); assert (entered > 0); return float(hit) / float (entered); } void _KDTreeNode::MakeRayList (CellFrustum *cf, int x, int y, MPObjList *list) { void *place; MPObjList *inc = cf->_inc; ObjInfo *info; inc->Reset (place); while (place) { info = inc->Peek (place); inc->Next (place); if ( (0 == classify_plane_bbox ( X, x, info->_clipped_bbox, info)) && (0 == classify_plane_bbox ( Y, y, info->_clipped_bbox, info)) ) { if (truly_GS->_disabled_flags & DISABLE_VIEWVEC_T) list->PlaceInList (info); else list->PlaceInSortedList (info, _KDTreeNode::tnearsort); } } MPObjList *str = cf->_str; str->Reset (place); while (place) { info = str->Peek (place); str->Next (place); if ( (0 == classify_plane_bbox ( X, x, info->_clipped_bbox, info)) && (0 == classify_plane_bbox ( Y, y, info->_clipped_bbox, info)) ) { if (truly_GS->_disabled_flags & DISABLE_VIEWVEC_T) list->PlaceInList (info); else list->PlaceInSortedList (info, _KDTreeNode::tnearsort); } } } ObjInfo *_KDTreeNode::FindObjInfo (RayCastable *obj) { int size = _objs->Size(); for (int i = 0; i < size; i++) { if (_obj_info[i]._obj == obj) return &_obj_info[i]; } cerr << "unable to find objinfo in the cell!" << endl; assert (0); return NULL; } void KDTree::ClearStats (void) { KDTree::_num_objs_culled_by_ray_lists = 0; KDTree::_num_objs_touched = 0; KDTree::_num_objs_touched_dbl_count = 0; KDTree::_num_screen_space_conversions = 0; KDTree::_old_intersect_count = 0; KDTree::_old_intersect_success_count = 0; KDTree::_new_intersect_count = 0; KDTree::_new_intersect_success_count = 0; KDTree::_new_bbox_success_count = 0; KDTree::_old_bbox_success_count = 0; KDTree::_num_findpoint_calls = 0; KDTree::_kdtraversal_cache_hits = KDTree::_kdtraversal_cache_misses = 0; KDTree::_worstcase_intersect_count = 0; KDTree::_num_intersects_overruled = 0; KDTree::_num_double_checks_avoided = 0; KDTree::_num_axis_checks =0; KDTree::_num_axis_checks_successes = 0; }