shape_reconstruction: frustum

Go to the documentation of this file.
00001 /****************************************************************************
00002 * VCGLib                                                            o o     *
00003 * Visual and Computer Graphics Library                            o     o   *
00004 *                                                                _   O  _   *
00005 * Copyright(C) 2004                                                \/)\/    *
00006 * Visual Computing Lab                                            /\/|      *
00007 * ISTI - Italian National Research Council                           |      *
00008 *                                                                    \      *
00009 * All rights reserved.                                                      *
00010 *                                                                           *
00011 * This program is free software; you can redistribute it and/or modify      *   
00012 * it under the terms of the GNU General Public License as published by      *
00013 * the Free Software Foundation; either version 2 of the License, or         *
00014 * (at your option) any later version.                                       *
00015 *                                                                           *
00016 * This program is distributed in the hope that it will be useful,           *
00017 * but WITHOUT ANY WARRANTY; without even the implied warranty of            *
00018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the             *
00019 * GNU General Public License (http://www.gnu.org/licenses/gpl.txt)          *
00020 * for more details.                                                         *
00021 *                                                                           *
00022 ****************************************************************************/
00023 
00024 /****************************************************************************
00025 History
00026 
00027 $Log: not supported by cvs2svn $
00028 Revision 1.8  2005/11/30 09:57:13  m_di_benedetto
00029 Added methods to flag visibility.
00030 
00031 Revision 1.7  2005/10/26 11:42:03  m_di_benedetto
00032 Added PASS_THROUGH flags.
00033 
00034 Revision 1.6  2005/10/15 19:14:35  m_di_benedetto
00035 Modified objapplyfunctor to nodeapplyfunctor.
00036 
00037 Revision 1.5  2005/10/05 01:59:56  m_di_benedetto
00038 First Commit, new version.
00039 
00040 Revision 1.3  2005/09/29 22:20:49  m_di_benedetto
00041 Removed '&' in FrustumCull() method.
00042 
00043 Revision 1.2  2005/09/28 19:57:18  m_di_benedetto
00044 #included aabb tree base.
00045 
00046 Revision 1.1  2005/09/26 18:33:16  m_di_benedetto
00047 First Commit.
00048 
00049 
00050 ****************************************************************************/
00051 
00052 #ifndef __VCGLIB_AABBBINARYTREE_FRUSTUMCULL_H
00053 #define __VCGLIB_AABBBINARYTREE_FRUSTUMCULL_H
00054 
00055 // std headers
00056 /* EMPTY */
00057 
00058 // vcg headers
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                 //node->Flags() &= ~(0x7F);
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                 // Intermediate BVs containing a sufficient number of objects are marked fully visible even if they don't
00230                 if (fullInside || (node->ObjectsCount() <= minNodeObjectsCount)) {
00231                         node->Flags() |= FC_FULLY_VISIBLE_BIT;
00232                         nodeApply(*node);
00233                         return;
00234                 }
00235 
00236                 node->Flags() |= FC_PARTIALLY_VISIBLE_BIT;
00237 
00238                 if ((node->IsLeaf()))
00239                 {
00240                         nodeApply(*node);
00241                         return;
00242                 }
00243 
00244                 //ClassType::NodeVsFrustum(node->children[0], viewerPosition, f, newMask, minNodeObjectsCount, nodeApply);
00245                 //ClassType::NodeVsFrustum(node->children[1], viewerPosition, f, newMask, minNodeObjectsCount, nodeApply);
00246                 ScalarType dt;
00247                 if (node->splitAxis == 0) {
00248                         dt = viewerPosition[0] - node->boxCenter[0];
00249                 }
00250                 else if (node->splitAxis == 1) {
00251                         dt = viewerPosition[1] - node->boxCenter[1];
00252                 }
00253                 else {
00254                         dt = viewerPosition[2] - node->boxCenter[2];
00255                 }
00256 
00257                 if (dt <= (ScalarType)0) {
00258                         ClassType::NodeVsFrustum(node->children[0], viewerPosition, f, newMask, minNodeObjectsCount, nodeApply);
00259                         ClassType::NodeVsFrustum(node->children[1], viewerPosition, f, newMask, minNodeObjectsCount, nodeApply);
00260                 }
00261                 else {
00262                         ClassType::NodeVsFrustum(node->children[1], viewerPosition, f, newMask, minNodeObjectsCount, nodeApply);
00263                         ClassType::NodeVsFrustum(node->children[0], viewerPosition, f, newMask, minNodeObjectsCount, nodeApply);
00264                 }
00265 
00266                 const bool c0 = (node->children[0] != 0) && ClassType::IsVisible(node->children[0]);
00267                 const bool c1 = (node->children[1] != 0) && ClassType::IsVisible(node->children[1]);
00268 
00269                 if (c0 != c1) {
00270                                 node->Flags() &= ~(0x03 << FC_PASS_THROUGH_FIRST_BIT);
00271                         if (c0) {
00272                                 node->Flags() |= (0x01 << FC_PASS_THROUGH_FIRST_BIT);
00273                         }
00274                         else {
00275                                 node->Flags() |= (0x02 << FC_PASS_THROUGH_FIRST_BIT);
00276                         }
00277                 }
00278         }
00279 
00280 };
00281 
00282 }       // end namespace vcg
00283 
00284 #endif // #ifndef __VCGLIB_AABBBINARYTREE_FRUSTUMCULL_H