cgma
KdTree.hpp
Go to the documentation of this file.
00001 /*
00002  *
00003  *
00004  * Copyright (C) 2004 Sandia Corporation.  Under the terms of Contract DE-AC04-94AL85000
00005  * with Sandia Corporation, the U.S. Government retains certain rights in this software.
00006  *
00007  * This file is part of facetbool--contact via [email protected]
00008  *
00009  * This library is free software; you can redistribute it and/or
00010  * modify it under the terms of the GNU Lesser General Public
00011  * License as published by the Free Software Foundation; either
00012  * version 2.1 of the License, or (at your option) any later version.
00013  *
00014  * This library is distributed in the hope that it will be useful,
00015  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00016  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00017  * Lesser General Public License for more details.
00018  *
00019  * You should have received a copy of the GNU Lesser General Public
00020  * License along with this library; if not, write to the Free Software
00021  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00022  *
00023  *
00024  *
00025  */
00026 
00027 #ifndef _KDTREE
00028 #define _KDTREE
00029 #include <vector>
00030 
00031 #include "FBStructs.hpp"
00032 
00033 class TreeStack {
00034 
00035 public:
00036 
00037   TreeStack(int imin, int imax, int cut_dir, int iseq) {
00038    cuttingdir = cut_dir;
00039     min = imin;
00040     max = imax;
00041     sequence = iseq;
00042   }
00043   
00044   ~TreeStack() { }
00045   
00046   int min, max, cuttingdir, sequence;
00047 };
00048 
00049 class KDTree
00050 {
00051 
00052 public:
00053 
00054   KDTree();
00055   ~KDTree();
00056   void box_kdtree_intersect(FSBoundingBox& bbox, int *count, int *indexlist) const;
00057   int makeKDTree(int npoly, const FSBOXVECTOR& boxlist);
00058 
00059 private:
00060 
00061   double epsilonkd;
00062   int numtris;
00063   FSBoundingBox* *treebox; 
00064   int *nextbranch;
00065   FSBOXVECTOR boxlistptr;
00066 //  std::vector<FSBoundingBox* > boxlist;
00067   int *isequence;
00068   FSBoundingBox* getbox(int min, int max);
00069   void find_the_median(int k, int l, int r, double *array, int *ia);
00070   int getcuttingdirection(FSBoundingBox* box);
00071   inline void SWAP(int &x, int &y)
00072   {
00073   int temp;
00074     temp = x;
00075     x = y;
00076     y = temp;
00077   }   
00078   double rayxstart, rayystart, rayzstart, dx, dy, dz;
00079   bool rayintersectsbox(FSBoundingBox *box);
00080   inline double MAXX(double a, double b) {
00081     if ( a > b ) return a;
00082     else return b;
00083   }
00084   inline double MINN(double a, double b) {
00085     if ( a < b ) return a;
00086     else return b;
00087   }
00088 };
00089 
00090 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines