00001 #include "sysdep.h"
00002 #include "box.h"
00003
00004 __CD__BEGIN
00005
00006
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
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))
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