Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

box_bld.cpp

Go to the documentation of this file.
00001 #include "sysdep.h"
00002 #include "box.h"
00003 
00004 __CD__BEGIN
00005 
00006 // point in box test
00007 bool Box::intersect(const Vector3D& p) const
00008 {
00009   const Vector3D& pos=getPosition();
00010   const Vector3D& s=getSize();
00011   if (p.x<pos.x || p.x>(pos.x+s.x)) return false;
00012   if (p.y<pos.y || p.y>(pos.y+s.y)) return false;
00013   if (p.z<pos.z || p.z>(pos.z+s.z)) return false;
00014   return true;
00015 }
00016 
00017 // Non-oriented intersection test
00018 bool Box::intersect(const Box& b)
00019 {
00020   const Vector3D& t1=getPosition();
00021   Vector3D t2=getPosition()+getSize();
00022   const Vector3D& p1=b.getPosition();
00023   Vector3D p2=b.getPosition()+b.getSize();
00024   return (Max(p1.x,t1.x) <= Min(p2.x,t2.x)  &&
00025           Max(p1.y,t1.y) <= Min(p2.y,t2.y)  &&
00026           Max(p1.z,t1.z) <= Min(p2.z,t2.z));
00027 }
00028 
00029 BoxedTriangle::BoxedTriangle(const Vector3D& _1, 
00030                              const Vector3D& _2, 
00031                              const Vector3D& _3)
00032                              : BoxTreeNode(), Triangle(_1,_2,_3)
00033 {
00034   m_Pos.x=Min(Min(_1.x,_2.x),_3.x);
00035   m_Pos.y=Min(Min(_1.y,_2.y),_3.y);
00036   m_Pos.z=Min(Min(_1.z,_2.z),_3.z);
00037   Vector3D mx;
00038   mx.x=Max(Max(_1.x,_2.x),_3.x);
00039   mx.y=Max(Max(_1.y,_2.y),_3.y);
00040   mx.z=Max(Max(_1.z,_2.z),_3.z);
00041   m_Size=mx-getPosition();
00042   m_Center=getPosition()+0.5f*getSize();
00043 }
00044 
00045 int BoxTreeInnerNode::createSons(const Vector3D& center)
00046 {
00047   int longest=0;
00048   Vector3D p=getPosition();
00049   Vector3D s=getSize();
00050   if (1)
00051   {
00052     Vector3D dist(Vector3D::Zero);
00053     for(unsigned i=0;i<m_Boxes.size();i++)
00054     {
00055       BoxedTriangle* bt=m_Boxes[i];
00056       dist.x+=flabs(bt->center.x - center.x);
00057       dist.y+=flabs(bt->center.y - center.y);
00058       dist.z+=flabs(bt->center.z - center.z);
00059     }
00060     if (dist.y>dist.x && dist.y>dist.z) longest=1;
00061     else
00062     if (dist.z>dist.x && dist.z>dist.y) longest=2;
00063   }
00064   else
00065   {
00066     int dist[3];
00067     dist[0]=dist[1]=dist[2]=0;
00068     for(unsigned i=0;i<m_Boxes.size();i++)
00069     {
00070       BoxedTriangle* bt=m_Boxes[i];
00071       for(int j=0;j<3;j++)
00072         if (bt->center[j] > center[j]) dist[j]++;
00073         else dist[j]--;
00074     }
00075     for(int j=0;j<3;j++)
00076       dist[j]=abs(dist[j]);
00077     if (dist[1]<dist[0] && dist[1]<dist[2]) longest=1;
00078     else
00079     if (dist[2]<dist[0] && dist[2]<dist[1]) longest=2;
00080   }
00081   float s1=center[longest]-p[longest];
00082   float s2=s[longest]-s1;
00083   s[longest]=s1;
00084   m_First=new BoxTreeInnerNode(p,s,m_logdepth);
00085   p[longest]+=s1;
00086   s[longest]=s2;
00087   m_Second=new BoxTreeInnerNode(p,s,m_logdepth);
00088   return longest;
00089 }
00090 
00091 void BoxTreeInnerNode::recalcBounds(Vector3D& center)
00092 {
00093   if (m_Boxes.empty()) return;
00094   center=Vector3D::Zero;
00095   Vector3D mn(9e9f,9e9f,9e9f),mx(-9e9f,-9e9f,-9e9f);
00096   for(unsigned i=0;i<m_Boxes.size();i++)
00097   {
00098     BoxedTriangle* bt=m_Boxes[i];
00099     center+=bt->center;
00100     mn.x=Min(Min(Min(bt->v1.x,bt->v2.x),bt->v3.x),mn.x);
00101     mn.y=Min(Min(Min(bt->v1.y,bt->v2.y),bt->v3.y),mn.y);
00102     mn.z=Min(Min(Min(bt->v1.z,bt->v2.z),bt->v3.z),mn.z);
00103     mx.x=Max(Max(Max(bt->v1.x,bt->v2.x),bt->v3.x),mx.x);
00104     mx.y=Max(Max(Max(bt->v1.y,bt->v2.y),bt->v3.y),mx.y);
00105     mx.z=Max(Max(Max(bt->v1.z,bt->v2.z),bt->v3.z),mx.z);
00106   }
00107   center/=float(m_Boxes.size());
00108   m_Pos=mn;
00109   m_Size=mx-mn;
00110   if (m_Size.x==0.0f) { m_Size.x=0.002f; m_Pos.x-=0.001f; }
00111   if (m_Size.y==0.0f) { m_Size.y=0.002f; m_Pos.y-=0.001f; }
00112   if (m_Size.z==0.0f) { m_Size.z=0.002f; m_Pos.z-=0.001f; }
00113   m_Center=getPosition()+0.5f*getSize();
00114 }
00115 
00116 int BoxTreeInnerNode::divide(int p_depth)
00117 {
00118   if (m_Boxes.empty()) return 0;
00119   Vector3D center;
00120   recalcBounds(center);
00121   int longest=createSons(center);
00122   BoxTreeInnerNode* f=static_cast<BoxTreeInnerNode*>(m_First);
00123   BoxTreeInnerNode* s=static_cast<BoxTreeInnerNode*>(m_Second);
00124   int depth=1;
00125   int bnum=m_Boxes.size();
00126 #ifdef _DEBUG
00127   int fnum=0;
00128 #endif
00129   for(unsigned i=0;i<bnum;i++)
00130   {
00131     BoxedTriangle* bt=m_Boxes[i];
00132     if (bt->center[longest]<center[longest])
00133     {
00134       f->m_Boxes.push_back(bt);
00135       #ifdef _DEBUG
00136         fnum++;
00137       #endif
00138     }
00139     else
00140     {
00141       s->m_Boxes.push_back(bt);
00142     }
00143   }
00144   
00145   int b1num=f->m_Boxes.size();
00146   int b2num=s->m_Boxes.size();
00147   if ((b1num==bnum  ||  b2num==bnum))// && p_depth>m_logdepth)
00148   {
00149     delete m_First;  m_First=NULL;
00150     delete m_Second; m_Second=NULL;
00151     return depth+1;
00152   }
00153   
00154   m_Boxes.clear();
00155   if (f->m_Boxes.empty()) { delete m_First; m_First=NULL; }
00156   else
00157   if (f->m_Boxes.size()==1)
00158   {
00159     BoxedTriangle* bt=f->m_Boxes.back();
00160     delete m_First;
00161     m_First=bt;
00162   } else depth=f->divide(p_depth+1);
00163   if (s->m_Boxes.empty()) { delete m_Second; m_Second=NULL; }
00164   else
00165   if (s->m_Boxes.size()==1)
00166   {
00167     BoxedTriangle* bt=s->m_Boxes.back();
00168     delete m_Second;
00169     m_Second=bt;
00170   } else depth=Max(depth,s->divide(p_depth+1));
00171   return depth+1;
00172 }
00173 
00174 __CD__BEGIN

Generated at Sat Nov 18 00:15:14 2000 for coldet by doxygen1.2.3 written by Dimitri van Heesch, © 1997-2000