kdtree.C

00001 /*
00002  * This file is part of the "Archon" framework.
00003  * (http://files3d.sourceforge.net)
00004  *
00005  * Copyright © 2002 by Kristian Spangsege and Brian Kristiansen.
00006  *
00007  * Permission to use, copy, modify, and distribute this software and
00008  * its documentation under the terms of the GNU General Public License is
00009  * hereby granted. No representations are made about the suitability of
00010  * this software for any purpose. It is provided "as is" without express
00011  * or implied warranty. See the GNU General Public License
00012  * (http://www.gnu.org/copyleft/gpl.html) for more details.
00013  *
00014  * The characters in this file are ISO8859-1 encoded.
00015  *
00016  * The documentation in this file is in "Doxygen" style
00017  * (http://www.doxygen.org).
00018  */
00019 
00020 #include <archon/util/kdtree.H>
00021 
00022 namespace Archon
00023 {
00024   namespace Utilities
00025   {
00026     void KDTree::buildSubKDTree(int start, int end, int axis)
00027     {
00028       sort(elements.begin()+start, elements.begin()+end+1, sort_func(axis));
00029 
00030       int midpoint = (end-start)/2 + start;
00031         
00032       if(start<midpoint-1) // Build left tree
00033         buildSubKDTree(start, midpoint-1, (axis+1)%3); 
00034       if(end>midpoint+1) // Build right tree
00035         buildSubKDTree(midpoint+1, end,(axis+1)%3);
00036     }
00037 
00038 
00039     void KDTree::findSubNearest(const Math::Vector3 &position, unsigned count, int start, int end, int axis)
00040     {
00041       // Calculate current point
00042       int midpoint = (end-start)/2 + start;
00043 
00044       // Add this Photon to the priority que if close enough
00045       Math::Vector3 m = elements[midpoint]->getPosition();
00046       const double dist = Math::dist(position, m);
00047 
00048       if(dist < radius)
00049       {
00050         QElement *q;
00051         if(nearest_queue.size() >= count)
00052         {
00053           q = nearest_queue.top();
00054           if(dist < q->dist)
00055           {
00056             // Replace top Photon
00057             nearest_queue.pop();
00058             q->element = elements[midpoint];
00059             q->dist = dist; 
00060             nearest_queue.push(q);
00061             radius = nearest_queue.top()->dist;
00062           }
00063         }
00064         else
00065         {
00066           q = new QElement();
00067           q->element = elements[midpoint];
00068           q->dist = dist; 
00069 
00070           nearest_queue.push(q);
00071           if(nearest_queue.size() == count) radius = nearest_queue.top()->dist;
00072         }
00073       }
00074 
00075       if(m[axis] <= position[axis])
00076       {
00077         if(m[axis]-radius <= position[axis]) // Look in right subtree
00078           if(end>=midpoint+1)
00079             findSubNearest(position, count, midpoint+1, end, (axis+1)%3);
00080 
00081         if(m[axis]+radius >= position[axis]) // Look in left subtree
00082           if(start<=midpoint-1)
00083             findSubNearest(position, count, start, midpoint-1, (axis+1)%3);
00084       }
00085       else
00086       {
00087         if(elements[midpoint]->getPosition()[axis]+radius >= position[axis]) // Look in left subtree
00088           if(start<=midpoint-1)
00089             findSubNearest(position, count, start, midpoint-1, (axis+1)%3);
00090 
00091         if(elements[midpoint]->getPosition()[axis]-radius <= position[axis]) // Look in right subtree
00092           if(end>=midpoint+1)
00093             findSubNearest(position, count, midpoint+1, end, (axis+1)%3);
00094       }
00095     }
00096 
00097 
00098     void KDTree::findNearest(const Math::Vector3 &position,
00099                              unsigned count, double max_radius, double &_radius,
00100                              std::vector<const Element *> &_elements)
00101     {
00102       radius = max_radius;
00103       if(!elements.empty()) findSubNearest(position, count, 0, elements.size()-1, 0);
00104       while(!nearest_queue.empty())
00105       {
00106         QElement *q = nearest_queue.top();
00107         _elements.push_back(q->element);
00108         nearest_queue.pop();
00109         delete q;
00110       }
00111       _radius = radius;
00112     }
00113   }
00114 }
00115 
00116 
00117 
00118 
00119 
00120 

Generated on Sun Jul 30 22:55:44 2006 for Archon by  doxygen 1.4.4