00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052 #ifndef __VCGLIB_AABBBINARYTREE_FRUSTUMCULL_H
00053 #define __VCGLIB_AABBBINARYTREE_FRUSTUMCULL_H
00054
00055
00056
00057
00058
00059 #include <vcg/space/point3.h>
00060 #include <vcg/space/plane3.h>
00061 #include <vcg/space/index/aabb_binary_tree/base.h>
00062
00063
00064
00065 namespace vcg {
00066
00067 template <class TREETYPE>
00068 class AABBBinaryTreeFrustumCull {
00069 public:
00070 typedef AABBBinaryTreeFrustumCull<TREETYPE> ClassType;
00071 typedef TREETYPE TreeType;
00072 typedef typename TreeType::ScalarType ScalarType;
00073 typedef typename TreeType::CoordType CoordType;
00074 typedef typename TreeType::NodeType NodeType;
00075 typedef typename TreeType::ObjPtr ObjPtr;
00076
00077 protected:
00078 class VFrustumPlane {
00079 public:
00080 CoordType normal;
00081 ScalarType offset;
00082 unsigned int pVertexIndex[3];
00083 };
00084
00085 class VFrustum {
00086 public:
00087 VFrustumPlane planes[6];
00088 };
00089
00090 public:
00091 enum {
00092 FC_FIRST_PLANE_BIT = 0,
00093 FC_PARTIALLY_VISIBLE_BIT = (1 << (FC_FIRST_PLANE_BIT + 3)),
00094 FC_FULLY_VISIBLE_BIT = (1 << (FC_FIRST_PLANE_BIT + 4)),
00095 FC_PASS_THROUGH_FIRST_BIT = (FC_FIRST_PLANE_BIT + 5)
00096 };
00097
00098 static inline bool IsPartiallyVisible(const NodeType * node) {
00099 return ((node->Flags() & FC_PARTIALLY_VISIBLE_BIT) != 0);
00100 }
00101
00102 static inline bool IsFullyVisible(const NodeType * node) {
00103 return ((node->Flags() & FC_FULLY_VISIBLE_BIT) != 0);
00104 }
00105
00106 static inline void SetFullyVisible(NodeType * node) {
00107 node->Flags() |= FC_FULLY_VISIBLE_BIT;
00108 }
00109
00110 static inline void SetInvisible(NodeType * node) {
00111 node->Flags() &= ~(FC_FULLY_VISIBLE_BIT | FC_PARTIALLY_VISIBLE_BIT);
00112 }
00113
00114 static inline bool IsVisible(const NodeType * node) {
00115 return ((node->Flags() & (FC_PARTIALLY_VISIBLE_BIT | FC_FULLY_VISIBLE_BIT)) != 0);
00116 }
00117
00118 static inline unsigned int PassThrough(const NodeType * node) {
00119 return ((node->Flags() >> FC_PASS_THROUGH_FIRST_BIT) & 0x03);
00120 }
00121
00122 static inline void Initialize(TreeType & tree) {
00123 NodeType * pRoot = tree.pRoot;
00124 if (pRoot == 0) {
00125 return;
00126 }
00127 ClassType::InitializeNodeFlagsRec(pRoot);
00128 }
00129
00130 template <class NODEAPPLYFUNCTOR>
00131 static inline void FrustumCull(TreeType & tree, const Point3<ScalarType> & viewerPosition, const Plane3<ScalarType> frustumPlanes[6], const unsigned int minNodeObjectsCount, NODEAPPLYFUNCTOR & nodeApply) {
00132 NodeType * pRoot = tree.pRoot;
00133 if (pRoot == 0) {
00134 return;
00135 }
00136
00137 VFrustum frustum;
00138 for (int i=0; i<6; ++i) {
00139 frustum.planes[i].normal = frustumPlanes[i].Direction();
00140 frustum.planes[i].offset = frustumPlanes[i].Offset();
00141 frustum.planes[i].pVertexIndex[0] = (frustum.planes[i].normal[0] >= ((ScalarType)0)) ? (1) : (0);
00142 frustum.planes[i].pVertexIndex[1] = (frustum.planes[i].normal[1] >= ((ScalarType)0)) ? (1) : (0);
00143 frustum.planes[i].pVertexIndex[2] = (frustum.planes[i].normal[2] >= ((ScalarType)0)) ? (1) : (0);
00144 }
00145
00146 const unsigned char inMask = 0x3F;
00147 ClassType::NodeVsFrustum(tree.pRoot, viewerPosition, frustum, inMask, minNodeObjectsCount, nodeApply);
00148 }
00149
00150 protected:
00151
00152 static inline void InitializeNodeFlagsRec(NodeType * node) {
00153
00154 node->Flags() = 0;
00155 if (node->children[0] != 0) {
00156 ClassType::InitializeNodeFlagsRec(node->children[0]);
00157 }
00158 if (node->children[1] != 0) {
00159 ClassType::InitializeNodeFlagsRec(node->children[1]);
00160 }
00161 }
00162
00163 template <class NODEAPPLYFUNCTOR>
00164 static inline void NodeVsFrustum(NodeType * node, const Point3<ScalarType> & viewerPosition, const VFrustum & f, unsigned char inMask, unsigned int minNodeObjectsCount, NODEAPPLYFUNCTOR & nodeApply) {
00165 if (node == 0) {
00166 return;
00167 }
00168
00169 const CoordType bminmax[2] = {
00170 node->boxCenter - node->boxHalfDims,
00171 node->boxCenter + node->boxHalfDims,
00172 };
00173 const unsigned int firstFail = (unsigned int)((node->Flags() >> FC_FIRST_PLANE_BIT) & 0x7);
00174 const VFrustumPlane * fp = f.planes + firstFail;
00175 unsigned char k = 1 << firstFail;
00176 unsigned char newMask = 0x0;
00177 bool fullInside = true;
00178
00179 node->Flags() &= ~(1 << 25);
00180 node->Flags() &= ~(FC_PARTIALLY_VISIBLE_BIT | FC_FULLY_VISIBLE_BIT | (0x03 << FC_PASS_THROUGH_FIRST_BIT));
00181
00182 if ((k & inMask) != 0) {
00183 if (
00184 ((fp->normal[0] * bminmax[fp->pVertexIndex[0]][0]) +
00185 (fp->normal[1] * bminmax[fp->pVertexIndex[1]][1]) +
00186 (fp->normal[2] * bminmax[fp->pVertexIndex[2]][2]) +
00187 (fp->offset)) < ((ScalarType)0)
00188 ) {
00189 return;
00190 }
00191
00192 if (
00193 ((fp->normal[0] * bminmax[1 - fp->pVertexIndex[0]][0]) +
00194 (fp->normal[1] * bminmax[1 - fp->pVertexIndex[1]][1]) +
00195 (fp->normal[2] * bminmax[1 - fp->pVertexIndex[2]][2]) +
00196 (fp->offset)) < ((ScalarType)0)
00197 ) {
00198 newMask |= k;
00199 fullInside = false;
00200 }
00201 }
00202
00203 k = 1;
00204 for (unsigned int i=0; k<=inMask; ++i, k<<=1) {
00205 if ((i != firstFail) && ((k & inMask) != 0)) {
00206 fp = f.planes + i;
00207 if (
00208 ((fp->normal[0] * bminmax[fp->pVertexIndex[0]][0]) +
00209 (fp->normal[1] * bminmax[fp->pVertexIndex[1]][1]) +
00210 (fp->normal[2] * bminmax[fp->pVertexIndex[2]][2]) +
00211 (fp->offset)) < ((ScalarType)0)
00212 ) {
00213 node->Flags() = (node->Flags() & ((~0x0) & (0x7 << ClassType::FC_FIRST_PLANE_BIT))) | (i << ClassType::FC_FIRST_PLANE_BIT);
00214 return;
00215 }
00216
00217 if (
00218 ((fp->normal[0] * bminmax[1 - fp->pVertexIndex[0]][0]) +
00219 (fp->normal[1] * bminmax[1 - fp->pVertexIndex[1]][1]) +
00220 (fp->normal[2] * bminmax[1 - fp->pVertexIndex[2]][2]) +
00221 (fp->offset)) < ((ScalarType)0)
00222 ) {
00223 newMask |= k;
00224 fullInside = false;
00225 }
00226 }
00227 }
00228
00229 if (fullInside || (node->IsLeaf()) || (node->ObjectsCount() <= minNodeObjectsCount)) {
00230 node->Flags() |= FC_FULLY_VISIBLE_BIT;
00231 nodeApply(*node);
00232 return;
00233 }
00234
00235 node->Flags() |= FC_PARTIALLY_VISIBLE_BIT;
00236
00237
00238
00239 ScalarType dt;
00240 if (node->splitAxis == 0) {
00241 dt = viewerPosition[0] - node->boxCenter[0];
00242 }
00243 else if (node->splitAxis == 1) {
00244 dt = viewerPosition[1] - node->boxCenter[1];
00245 }
00246 else {
00247 dt = viewerPosition[2] - node->boxCenter[2];
00248 }
00249
00250 if (dt <= (ScalarType)0) {
00251 ClassType::NodeVsFrustum(node->children[0], viewerPosition, f, newMask, minNodeObjectsCount, nodeApply);
00252 ClassType::NodeVsFrustum(node->children[1], viewerPosition, f, newMask, minNodeObjectsCount, nodeApply);
00253 }
00254 else {
00255 ClassType::NodeVsFrustum(node->children[1], viewerPosition, f, newMask, minNodeObjectsCount, nodeApply);
00256 ClassType::NodeVsFrustum(node->children[0], viewerPosition, f, newMask, minNodeObjectsCount, nodeApply);
00257 }
00258
00259 const bool c0 = (node->children[0] != 0) && ClassType::IsVisible(node->children[0]);
00260 const bool c1 = (node->children[1] != 0) && ClassType::IsVisible(node->children[1]);
00261
00262 if (c0 != c1) {
00263 node->Flags() &= ~(0x03 << FC_PASS_THROUGH_FIRST_BIT);
00264 if (c0) {
00265 node->Flags() |= (0x01 << FC_PASS_THROUGH_FIRST_BIT);
00266 }
00267 else {
00268 node->Flags() |= (0x02 << FC_PASS_THROUGH_FIRST_BIT);
00269 }
00270 }
00271 }
00272
00273 };
00274
00275 }
00276
00277 #endif // #ifndef __VCGLIB_AABBBINARYTREE_FRUSTUMCULL_H
