newview

llspatialpartition.cpp

Go to the documentation of this file.
00001 
00032 #include "llviewerprecompiledheaders.h"
00033 
00034 #include "llspatialpartition.h"
00035 
00036 #include "llviewerwindow.h"
00037 #include "llviewerobjectlist.h"
00038 #include "llvovolume.h"
00039 #include "llviewercamera.h"
00040 #include "llface.h"
00041 #include "viewer.h"
00042 #include "llagent.h"
00043 #include "llviewerregion.h"
00044 #include "llcamera.h"
00045 #include "pipeline.h"
00046 
00047 static GLuint sBoxList = 0;
00048 
00049 const F32 SG_OCCLUSION_FUDGE = 1.01f;
00050 //const S32 SG_LOD_PERIOD = 16;
00051 
00052 #define SG_DISCARD_TOLERANCE 0.25f
00053 
00054 #if LL_OCTREE_PARANOIA_CHECK
00055 #define assert_octree_valid(x) x->validate()
00056 #else
00057 #define assert_octree_valid(x)
00058 #endif
00059 
00060 static U32 sZombieGroups = 0;
00061 
00062 static F32 sLastMaxTexPriority = 1.f;
00063 static F32 sCurMaxTexPriority = 1.f;
00064 
00065 //static counter for frame to switch LOD on
00066 
00067 void sg_assert(BOOL expr)
00068 {
00069 #if LL_OCTREE_PARANOIA_CHECK
00070         if (!expr)
00071         {
00072                 llerrs << "Octree invalid!" << llendl;
00073         }
00074 #endif
00075 }
00076 
00077 #if LL_DEBUG
00078 void validate_drawable(LLDrawable* drawablep)
00079 {
00080         F64 rad = drawablep->getBinRadius();
00081         const LLVector3* ext = drawablep->getSpatialExtents();
00082 
00083         if (rad < 0 || rad > 4096 ||
00084                 (ext[1]-ext[0]).magVec() > 4096)
00085         {
00086                 llwarns << "Invalid drawable found in octree." << llendl;
00087         }
00088 }
00089 #else
00090 #define validate_drawable(x)
00091 #endif
00092 
00093 BOOL earlyFail(LLCamera* camera, LLSpatialGroup* group);
00094 
00095 BOOL LLLineSegmentAABB(const LLVector3& start, const LLVector3& end, const LLVector3& center, const LLVector3& size)
00096 {
00097         float fAWdU[3];
00098         LLVector3 dir;
00099         LLVector3 diff;
00100         
00101         for (U32 i = 0; i < 3; i++)
00102         {
00103                 dir.mV[i] = 0.5f * (end.mV[i] - start.mV[i]);
00104                 diff.mV[i] = (0.5f * (end.mV[i] + start.mV[i])) - center.mV[i];
00105                 fAWdU[i] = fabsf(dir.mV[i]);
00106                 if(fabsf(diff.mV[i])>size.mV[i] + fAWdU[i])     return false;
00107         }
00108 
00109         float f;
00110         f = dir.mV[1] * diff.mV[2] - dir.mV[2] * diff.mV[1];    if(fabsf(f)>size.mV[1]*fAWdU[2] + size.mV[2]*fAWdU[1])  return false;
00111         f = dir.mV[2] * diff.mV[0] - dir.mV[0] * diff.mV[2];    if(fabsf(f)>size.mV[0]*fAWdU[2] + size.mV[2]*fAWdU[0])  return false;
00112         f = dir.mV[0] * diff.mV[1] - dir.mV[1] * diff.mV[0];    if(fabsf(f)>size.mV[0]*fAWdU[1] + size.mV[1]*fAWdU[0])  return false;
00113 
00114         return true;
00115 }
00116 
00117 //returns:
00118 //      0 if sphere and AABB are not intersecting 
00119 //      1 if they are
00120 //      2 if AABB is entirely inside sphere
00121 
00122 S32 LLSphereAABB(const LLVector3& center, const LLVector3& size, const LLVector3& pos, const F32 &rad)
00123 {
00124         S32 ret = 2;
00125 
00126         LLVector3 min = center - size;
00127         LLVector3 max = center + size;
00128         for (U32 i = 0; i < 3; i++)
00129         {
00130                 if (min.mV[i] > pos.mV[i] + rad ||
00131                         max.mV[i] < pos.mV[i] - rad)
00132                 {       //totally outside
00133                         return 0;
00134                 }
00135                 
00136                 if (min.mV[i] < pos.mV[i] - rad ||
00137                         max.mV[i] > pos.mV[i] + rad)
00138                 {       //intersecting
00139                         ret = 1;
00140                 }
00141         }
00142 
00143         return ret;
00144 }
00145 
00146 LLSpatialGroup::~LLSpatialGroup()
00147 {
00148         if (isState(DEAD))
00149         {
00150                 sZombieGroups--;
00151         }
00152         
00153         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
00154         clearDrawMap();
00155 }
00156 
00157 void LLSpatialGroup::clearDrawMap()
00158 {
00159         mDrawMap.clear();
00160 }
00161 
00162 class LLRelightPainter : public LLSpatialGroup::OctreeTraveler
00163 {
00164 public:
00165         LLVector3 mOrigin, mDir;
00166         F32 mRadius;
00167 
00168         LLRelightPainter(LLVector3 origin, LLVector3 dir, F32 radius)
00169                 : mOrigin(origin), mDir(dir), mRadius(radius) 
00170         { }
00171 
00172         virtual void traverse(const LLSpatialGroup::TreeNode* n)
00173         {
00174                 LLSpatialGroup::OctreeNode* node = (LLSpatialGroup::OctreeNode*) n;
00175                 
00176                 LLSpatialGroup* group = (LLSpatialGroup*) node->getListener(0);
00177                 group->setState(LLSpatialGroup::RESHADOW);
00178                 
00179                 for (U32 i = 0; i < node->getChildCount(); i++)
00180                 {
00181                         const LLSpatialGroup::OctreeNode* child = node->getChild(i);
00182                         LLSpatialGroup* group = (LLSpatialGroup*) child->getListener(0);
00183                         
00184                         LLVector3 res;
00185                         
00186                         LLVector3 center, size;
00187                         
00188                         center = group->mBounds[0];
00189                         size = group->mBounds[1];
00190                         
00191                         if (child->isInside(LLVector3d(mOrigin)) || LLRayAABB(center, size, mOrigin, mDir, res, mRadius))
00192                         {
00193                                 traverse(child);
00194                         }
00195                 }       
00196         }
00197 
00198         virtual void visit(const LLSpatialGroup::OctreeState* branch) { }
00199 
00200 };
00201 
00202 BOOL LLSpatialGroup::isVisible()
00203 {
00204         if (LLPipeline::sUseOcclusion)
00205         {
00206                 return !isState(CULLED | OCCLUDED);
00207         }
00208         else
00209         {
00210                 return !isState(CULLED); 
00211         }
00212 }
00213 
00214 void LLSpatialGroup::validate()
00215 {
00216 #if LL_OCTREE_PARANOIA_CHECK
00217 
00218         sg_assert(!isState(DIRTY));
00219         sg_assert(!isDead());
00220 
00221         LLVector3 myMin = mBounds[0] - mBounds[1];
00222         LLVector3 myMax = mBounds[0] + mBounds[1];
00223 
00224         validateDrawMap();
00225 
00226         for (element_iter i = getData().begin(); i != getData().end(); ++i)
00227         {
00228                 LLDrawable* drawable = *i;
00229                 sg_assert(drawable->getSpatialGroup() == this);
00230                 if (drawable->getSpatialBridge())
00231                 {
00232                         sg_assert(drawable->getSpatialBridge() == mSpatialPartition->asBridge());
00233                 }
00234 
00235                 if (drawable->isSpatialBridge())
00236                 {
00237                         LLSpatialPartition* part = drawable->asPartition();
00238                         if (!part)
00239                         {
00240                                 llerrs << "Drawable reports it is a spatial bridge but not a partition." << llendl;
00241                         }
00242                         LLSpatialGroup* group = (LLSpatialGroup*) part->mOctree->getListener(0);
00243                         group->validate();
00244                 }
00245         }
00246 
00247         for (U32 i = 0; i < mOctreeNode->getChildCount(); ++i)
00248         {
00249                 LLSpatialGroup* group = (LLSpatialGroup*) mOctreeNode->getChild(i)->getListener(0);
00250 
00251                 group->validate();
00252                 
00253                 //ensure all children are enclosed in this node
00254                 LLVector3 center = group->mBounds[0];
00255                 LLVector3 size = group->mBounds[1];
00256                 
00257                 LLVector3 min = center - size;
00258                 LLVector3 max = center + size;
00259                 
00260                 for (U32 j = 0; j < 3; j++)
00261                 {
00262                         sg_assert(min.mV[j] >= myMin.mV[j]-0.02f);
00263                         sg_assert(max.mV[j] <= myMax.mV[j]+0.02f);
00264                 }
00265         }
00266 
00267 #endif
00268 }
00269 
00270 void validate_draw_info(LLDrawInfo& params)
00271 {
00272 #if LL_OCTREE_PARANOIA_CHECK
00273         if (params.mVertexBuffer.isNull())
00274         {
00275                 llerrs << "Draw batch has no vertex buffer." << llendl;
00276         }
00277         
00278         //bad range
00279         if (params.mStart >= params.mEnd)
00280         {
00281                 llerrs << "Draw batch has invalid range." << llendl;
00282         }
00283         
00284         if (params.mEnd >= (U32) params.mVertexBuffer->getNumVerts())
00285         {
00286                 llerrs << "Draw batch has buffer overrun error." << llendl;
00287         }
00288         
00289         if (params.mOffset + params.mCount > (U32) params.mVertexBuffer->getNumIndices())
00290         {
00291                 llerrs << "Draw batch has index buffer ovverrun error." << llendl;
00292         }
00293         
00294         //bad indices
00295         U32* indicesp = (U32*) params.mVertexBuffer->getIndicesPointer();
00296         if (indicesp)
00297         {
00298                 for (U32 i = params.mOffset; i < params.mOffset+params.mCount; i++)
00299                 {
00300                         if (indicesp[i] < params.mStart)
00301                         {
00302                                 llerrs << "Draw batch has vertex buffer index out of range error (index too low)." << llendl;
00303                         }
00304                         
00305                         if (indicesp[i] > params.mEnd)
00306                         {
00307                                 llerrs << "Draw batch has vertex buffer index out of range error (index too high)." << llendl;
00308                         }
00309                 }
00310         }
00311 #endif
00312 }
00313 
00314 void LLSpatialGroup::validateDrawMap()
00315 {
00316 #if LL_OCTREE_PARANOIA_CHECK
00317         for (draw_map_t::iterator i = mDrawMap.begin(); i != mDrawMap.end(); ++i)
00318         {
00319                 std::vector<LLDrawInfo*>& draw_vec = i->second;
00320                 for (std::vector<LLDrawInfo*>::iterator j = draw_vec.begin(); j != draw_vec.end(); ++j)
00321                 {
00322                         LLDrawInfo& params = **j;
00323                         
00324                         validate_draw_info(params);
00325                 }
00326         }
00327 #endif
00328 }
00329 
00330 void LLSpatialGroup::makeStatic()
00331 {
00332 #if !LL_DARWIN
00333         if (isState(GEOM_DIRTY | ALPHA_DIRTY))
00334         {
00335                 return;
00336         }
00337         
00338         if (mSpatialPartition->mRenderByGroup && mBufferUsage != GL_STATIC_DRAW_ARB)
00339         {
00340                 mBufferUsage = GL_STATIC_DRAW_ARB;
00341                 if (mVertexBuffer.notNull())
00342                 {
00343                         mVertexBuffer->makeStatic();
00344                 }
00345                 
00346                 for (buffer_map_t::iterator i = mBufferMap.begin(); i != mBufferMap.end(); ++i)
00347                 {
00348                         i->second->makeStatic();
00349                 }
00350                 
00351                 mBuilt = 1.f;
00352         }
00353 #endif
00354 }
00355 
00356 BOOL LLSpatialGroup::updateInGroup(LLDrawable *drawablep, BOOL immediate)
00357 {
00358         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
00359                 
00360         drawablep->updateSpatialExtents();
00361         validate_drawable(drawablep);
00362 
00363         OctreeNode* parent = mOctreeNode->getOctParent();
00364         
00365         if (mOctreeNode->isInside(drawablep->getPositionGroup()) && 
00366                 (mOctreeNode->contains(drawablep) ||
00367                  (drawablep->getBinRadius() > mOctreeNode->getSize().mdV[0] &&
00368                                 parent && parent->getElementCount() >= LL_OCTREE_MAX_CAPACITY)))
00369         {
00370                 unbound();
00371                 setState(OBJECT_DIRTY);
00372                 setState(GEOM_DIRTY);
00373                 validate_drawable(drawablep);
00374                 return TRUE;
00375         }
00376                 
00377         return FALSE;
00378 }
00379 
00380 
00381 BOOL LLSpatialGroup::addObject(LLDrawable *drawablep, BOOL add_all, BOOL from_octree)
00382 {
00383         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
00384         if (!from_octree)
00385         {
00386                 mOctreeNode->insert(drawablep);
00387         }
00388         else
00389         {
00390                 drawablep->setSpatialGroup(this);
00391                 validate_drawable(drawablep);
00392                 setState(OBJECT_DIRTY | GEOM_DIRTY);
00393                 mLastAddTime = gFrameTimeSeconds;
00394                 if (drawablep->isSpatialBridge())
00395                 {
00396                         mBridgeList.push_back((LLSpatialBridge*) drawablep);
00397                 }
00398                 if (drawablep->getRadius() > 1.f)
00399                 {
00400                         setState(IMAGE_DIRTY);
00401                 }
00402         }
00403 
00404         return TRUE;
00405 }
00406 
00407 void LLSpatialGroup::rebuildGeom()
00408 {
00409         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
00410         if (!isDead())
00411         {
00412                 mSpatialPartition->rebuildGeom(this);
00413         }
00414 }
00415 
00416 void LLSpatialPartition::rebuildGeom(LLSpatialGroup* group)
00417 {
00418         if (group->changeLOD())
00419         {
00420                 group->mLastUpdateDistance = group->mDistance;
00421                 group->mLastUpdateViewAngle = group->mViewAngle;
00422         }
00423 
00424         if (group->isDead() || !group->isState(LLSpatialGroup::GEOM_DIRTY))
00425         {
00426                 return;
00427         }
00428 
00429         LLFastTimer ftm(LLFastTimer::FTM_REBUILD_VBO);  
00430 
00431         group->clearDrawMap();
00432         
00433         //get geometry count
00434         group->mIndexCount = 0;
00435         group->mVertexCount = 0;
00436 
00437         addGeometryCount(group, group->mVertexCount, group->mIndexCount);
00438 
00439         if (group->mVertexCount > 0 && group->mIndexCount > 0)
00440         { //create vertex buffer containing volume geometry for this node
00441                 group->mBuilt = 1.f;
00442                 if (group->mVertexBuffer.isNull() || (group->mBufferUsage != group->mVertexBuffer->getUsage() && LLVertexBuffer::sEnableVBOs))
00443                 {
00444                         //LLFastTimer ftm(LLFastTimer::FTM_REBUILD_NONE_VB);
00445                         group->mVertexBuffer = createVertexBuffer(mVertexDataMask, group->mBufferUsage);
00446                         group->mVertexBuffer->allocateBuffer(group->mVertexCount, group->mIndexCount, true);
00447                         stop_glerror();
00448                 }
00449                 else
00450                 {
00451                         //LLFastTimer ftm(LLFastTimer::FTM_REBUILD_NONE_VB);
00452                         group->mVertexBuffer->resizeBuffer(group->mVertexCount, group->mIndexCount);
00453                         stop_glerror();
00454                 }
00455                 
00456                 {
00457                         LLFastTimer ftm((LLFastTimer::EFastTimerType) ((U32) LLFastTimer::FTM_REBUILD_VOLUME_VB + mPartitionType));
00458                         getGeometry(group);
00459                 }
00460         }
00461         else
00462         {
00463                 group->mVertexBuffer = NULL;
00464                 group->mBufferMap.clear();
00465         }
00466 
00467         group->mLastUpdateTime = gFrameTimeSeconds;
00468         group->clearState(LLSpatialGroup::GEOM_DIRTY | LLSpatialGroup::MATRIX_DIRTY);
00469 }
00470 
00471 BOOL LLSpatialGroup::boundObjects(BOOL empty, LLVector3& minOut, LLVector3& maxOut)
00472 {       
00473         const OctreeState* node = mOctreeNode->getOctState();
00474 
00475         if (node->getData().empty())
00476         {       //don't do anything if there are no objects
00477                 if (empty && mOctreeNode->getParent())
00478                 {       //only root is allowed to be empty
00479                         OCT_ERRS << "Empty leaf found in octree." << llendl;
00480                 }
00481                 return FALSE;
00482         }
00483 
00484         LLVector3& newMin = mObjectExtents[0];
00485         LLVector3& newMax = mObjectExtents[1];
00486         
00487         if (isState(OBJECT_DIRTY))
00488         { //calculate new bounding box
00489                 clearState(OBJECT_DIRTY);
00490 
00491                 //initialize bounding box to first element
00492                 OctreeState::const_element_iter i = node->getData().begin();
00493                 LLDrawable* drawablep = *i;
00494                 const LLVector3* minMax = drawablep->getSpatialExtents();
00495 
00496                 newMin.setVec(minMax[0]);
00497                 newMax.setVec(minMax[1]);
00498 
00499                 for (++i; i != node->getData().end(); ++i)
00500                 {
00501                         drawablep = *i;
00502                         minMax = drawablep->getSpatialExtents();
00503                         
00504                         //bin up the object
00505                         for (U32 i = 0; i < 3; i++)
00506                         {
00507                                 if (minMax[0].mV[i] < newMin.mV[i])
00508                                 {
00509                                         newMin.mV[i] = minMax[0].mV[i];
00510                                 }
00511                                 if (minMax[1].mV[i] > newMax.mV[i])
00512                                 {
00513                                         newMax.mV[i] = minMax[1].mV[i];
00514                                 }
00515                         }
00516                 }
00517                 
00518                 mObjectBounds[0] = (newMin + newMax) * 0.5f;
00519                 mObjectBounds[1] = (newMax - newMin) * 0.5f;
00520         }
00521         
00522         if (empty)
00523         {
00524                 minOut = newMin;
00525                 maxOut = newMax;
00526         }
00527         else
00528         {
00529                 for (U32 i = 0; i < 3; i++)
00530                 {
00531                         if (newMin.mV[i] < minOut.mV[i])
00532                         {
00533                                 minOut.mV[i] = newMin.mV[i];
00534                         }
00535                         if (newMax.mV[i] > maxOut.mV[i])
00536                         {
00537                                 maxOut.mV[i] = newMax.mV[i];
00538                         }
00539                 }
00540         }
00541                 
00542         return TRUE;
00543 }
00544 
00545 void LLSpatialGroup::unbound()
00546 {
00547         if (isState(DIRTY))
00548         {
00549                 return;
00550         }
00551 
00552         setState(DIRTY);
00553         
00554         //all the parent nodes need to rebound this child
00555         if (mOctreeNode)
00556         {
00557                 OctreeNode* parent = (OctreeNode*) mOctreeNode->getParent();
00558                 while (parent != NULL)
00559                 {
00560                         LLSpatialGroup* group = (LLSpatialGroup*) parent->getListener(0);
00561                         if (group->isState(DIRTY))
00562                         {
00563                                 return;
00564                         }
00565                         
00566                         group->setState(DIRTY);
00567                         parent = (OctreeNode*) parent->getParent();
00568                 }
00569         }
00570 }
00571 
00572 LLSpatialGroup* LLSpatialGroup::getParent()
00573 {
00574         if (isDead())
00575         {
00576                 return NULL;
00577         }
00578 
00579         OctreeNode* parent = mOctreeNode->getOctParent();
00580 
00581         if (parent)
00582         {
00583                 return (LLSpatialGroup*) parent->getListener(0);
00584         }
00585 
00586         return NULL;
00587 }
00588 
00589 BOOL LLSpatialGroup::removeObject(LLDrawable *drawablep, BOOL from_octree)
00590 {
00591         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
00592         unbound();
00593         if (mOctreeNode && !from_octree)
00594         {
00595                 if (!mOctreeNode->remove(drawablep))
00596                 {
00597                         OCT_ERRS << "Could not remove drawable from spatial group" << llendl;
00598                 }
00599         }
00600         else
00601         {
00602                 drawablep->setSpatialGroup(NULL);
00603                 setState(GEOM_DIRTY);
00604                 if (drawablep->isSpatialBridge())
00605                 {
00606                         for (bridge_list_t::iterator i = mBridgeList.begin(); i != mBridgeList.end(); ++i)
00607                         {
00608                                 if (*i == drawablep)
00609                                 {
00610                                         mBridgeList.erase(i);
00611                                         break;
00612                                 }
00613                         }
00614                 }
00615         }
00616         return TRUE;
00617 }
00618 
00619 void LLSpatialGroup::shift(const LLVector3 &offset)
00620 {
00621         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
00622         LLVector3d offsetd(offset);
00623         mOctreeNode->setCenter(mOctreeNode->getCenter()+offsetd);
00624         mOctreeNode->updateMinMax();
00625         mBounds[0] += offset;
00626         mExtents[0] += offset;
00627         mExtents[1] += offset;
00628         mObjectBounds[0] += offset;
00629         mObjectExtents[0] += offset;
00630         mObjectExtents[1] += offset;
00631 
00632         setState(GEOM_DIRTY | MATRIX_DIRTY | OCCLUSION_DIRTY);
00633 }
00634 
00635 class LLSpatialSetState : public LLSpatialGroup::OctreeTraveler
00636 {
00637 public:
00638         U32 mState;
00639         LLSpatialSetState(U32 state) : mState(state) { }
00640         virtual void visit(const LLSpatialGroup::OctreeState* branch) { ((LLSpatialGroup*) branch->getListener(0))->setState(mState); } 
00641 };
00642 
00643 class LLSpatialSetStateDiff : public LLSpatialSetState
00644 {
00645 public:
00646         LLSpatialSetStateDiff(U32 state) : LLSpatialSetState(state) { }
00647 
00648         virtual void traverse(const LLSpatialGroup::TreeNode* n)
00649         {
00650                 LLSpatialGroup* group = (LLSpatialGroup*) n->getListener(0);
00651                 
00652                 if (!group->isState(mState))
00653                 {
00654                         LLSpatialGroup::OctreeTraveler::traverse(n);
00655                 }
00656         }
00657 };
00658 
00659 void LLSpatialGroup::setState(U32 state, S32 mode) 
00660 {
00661         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
00662         if (mode > STATE_MODE_SINGLE)
00663         {
00664                 if (mode == STATE_MODE_DIFF)
00665                 {
00666                         LLSpatialSetStateDiff setter(state);
00667                         setter.traverse(mOctreeNode);
00668                 }
00669                 else
00670                 {
00671                         LLSpatialSetState setter(state);
00672                         setter.traverse(mOctreeNode);
00673                 }
00674         }
00675         else
00676         {
00677                 mState |= state;
00678         }
00679 }
00680 
00681 class LLSpatialClearState : public LLSpatialGroup::OctreeTraveler
00682 {
00683 public:
00684         U32 mState;
00685         LLSpatialClearState(U32 state) : mState(state) { }
00686         virtual void visit(const LLSpatialGroup::OctreeState* branch) { ((LLSpatialGroup*) branch->getListener(0))->clearState(mState); }
00687 };
00688 
00689 class LLSpatialClearStateDiff : public LLSpatialClearState
00690 {
00691 public:
00692         LLSpatialClearStateDiff(U32 state) : LLSpatialClearState(state) { }
00693 
00694         virtual void traverse(const LLSpatialGroup::TreeNode* n)
00695         {
00696                 LLSpatialGroup* group = (LLSpatialGroup*) n->getListener(0);
00697                 
00698                 if (!group->isState(mState))
00699                 {
00700                         LLSpatialGroup::OctreeTraveler::traverse(n);
00701                 }
00702         }
00703 };
00704 
00705 
00706 void LLSpatialGroup::clearState(U32 state, S32 mode)
00707 {
00708         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
00709         if (mode > STATE_MODE_SINGLE)
00710         {
00711                 if (mode == STATE_MODE_DIFF)
00712                 {
00713                         LLSpatialClearStateDiff clearer(state);
00714                         clearer.traverse(mOctreeNode);
00715                 }
00716                 else
00717                 {
00718                         LLSpatialClearState clearer(state);
00719                         clearer.traverse(mOctreeNode);
00720                 }
00721         }
00722         else
00723         {
00724                 mState &= ~state;
00725         }
00726 
00727 #if LL_OCTREE_PARANOIA_CHECK
00728         if (state & LLSpatialGroup::ACTIVE_OCCLUSION)
00729         {
00730                 LLSpatialPartition* part = mSpatialPartition;
00731                 for (U32 i = 0; i < part->mOccludedList.size(); i++)
00732                 {
00733                         if (part->mOccludedList[i] == this)
00734                         {
00735                                 llerrs << "LLSpatialGroup state error: " << mState << llendl;
00736                         }
00737                 }
00738         }
00739 #endif
00740 }
00741 
00742 //======================================
00743 //              Octree Listener Implementation
00744 //======================================
00745 
00746 LLSpatialGroup::LLSpatialGroup(OctreeNode* node, LLSpatialPartition* part) :
00747         mState(0),
00748         mBuilt(0.f),
00749         mOctreeNode(node),
00750         mSpatialPartition(part),
00751         mVertexBuffer(NULL), 
00752         mBufferUsage(GL_STATIC_DRAW_ARB),
00753         mDistance(0.f),
00754         mDepth(0.f),
00755         mLastUpdateDistance(-1.f), 
00756         mLastUpdateTime(gFrameTimeSeconds),
00757         mLastAddTime(gFrameTimeSeconds),
00758         mLastRenderTime(gFrameTimeSeconds),
00759         mViewAngle(0.f),
00760         mLastUpdateViewAngle(-1.f)
00761 {
00762         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
00763 
00764         sg_assert(mOctreeNode->getListenerCount() == 0);
00765         mOctreeNode->addListener(this);
00766         setState(SG_INITIAL_STATE_MASK);
00767 
00768         mBounds[0] = LLVector3(node->getCenter());
00769         mBounds[1] = LLVector3(node->getSize());
00770 
00771         part->mLODSeed = (part->mLODSeed+1)%part->mLODPeriod;
00772         mLODHash = part->mLODSeed;
00773         
00774         mRadius = 1;
00775         mPixelArea = 1024.f;
00776 }
00777 
00778 void LLSpatialGroup::updateDistance(LLCamera &camera)
00779 {
00780 #if !LL_RELEASE_FOR_DOWNLOAD
00781         if (isState(LLSpatialGroup::OBJECT_DIRTY))
00782         {
00783                 llerrs << "Spatial group dirty on distance update." << llendl;
00784         }
00785 #endif
00786         if (!getData().empty())
00787         {
00788                 mRadius = mSpatialPartition->mRenderByGroup ? mObjectBounds[1].magVec() :
00789                                                 (F32) mOctreeNode->getSize().magVec();
00790                 mDistance = mSpatialPartition->calcDistance(this, camera);
00791                 mPixelArea = mSpatialPartition->calcPixelArea(this, camera);
00792         }
00793 }
00794 
00795 F32 LLSpatialPartition::calcDistance(LLSpatialGroup* group, LLCamera& camera)
00796 {
00797         LLVector3 eye = group->mObjectBounds[0] - camera.getOrigin();
00798 
00799         F32 dist = 0.f;
00800 
00801         if (group->mDrawMap.find(LLRenderPass::PASS_ALPHA) != group->mDrawMap.end())
00802         {
00803                 LLVector3 v = eye;
00804                 dist = eye.normVec();
00805 
00806                 if (!group->isState(LLSpatialGroup::ALPHA_DIRTY))
00807                 {
00808                         LLVector3 view_angle = LLVector3(eye * LLVector3(1,0,0),
00809                                                                                         eye * LLVector3(0,1,0),
00810                                                                                         eye * LLVector3(0,0,1));
00811 
00812                         if ((view_angle-group->mLastUpdateViewAngle).magVec() > 0.64f)
00813                         {
00814                                 group->mViewAngle = view_angle;
00815                                 group->mLastUpdateViewAngle = view_angle;
00816                                 //for occasional alpha sorting within the group
00817                                 //NOTE: If there is a trivial way to detect that alpha sorting here would not change the render order,
00818                                 //not setting this node to dirty would be a very good thing
00819                                 group->setState(LLSpatialGroup::ALPHA_DIRTY);
00820                         }               
00821                 }
00822 
00823                 //calculate depth of node for alpha sorting
00824 
00825                 LLVector3 at = camera.getAtAxis();
00826 
00827                 //front of bounding box
00828                 for (U32 i = 0; i < 3; i++)
00829                 {
00830                         v.mV[i] -= group->mObjectBounds[1].mV[i]*0.25f * at.mV[i];
00831                 }
00832 
00833                 group->mDepth = v * at;
00834 
00835                 F32 water_height = gAgent.getRegion()->getWaterHeight();
00836                 //figure out if this node is above or below water
00837                 if (group->mObjectBounds[0].mV[2] < water_height)
00838                 {
00839                         group->setState(LLSpatialGroup::BELOW_WATER);
00840                 }
00841                 else
00842                 {
00843                         group->clearState(LLSpatialGroup::BELOW_WATER);
00844                 }
00845         }
00846         else
00847         {
00848                 dist = eye.magVec();
00849         }
00850 
00851         if (dist < 16.f)
00852         {
00853                 dist /= 16.f;
00854                 dist *= dist;
00855                 dist *= 16.f;
00856         }
00857 
00858         return dist;
00859 }
00860 
00861 F32 LLSpatialPartition::calcPixelArea(LLSpatialGroup* group, LLCamera& camera)
00862 {
00863         return LLPipeline::calcPixelArea(group->mObjectBounds[0], group->mObjectBounds[1], camera);
00864 }
00865 
00866 BOOL LLSpatialGroup::changeLOD()
00867 {
00868         if (isState(ALPHA_DIRTY))
00869         { 
00870                 return TRUE;
00871         }
00872 
00873         if (mSpatialPartition->mSlopRatio > 0.f)
00874         {
00875                 F32 ratio = (mDistance - mLastUpdateDistance)/(llmax(mLastUpdateDistance, mRadius));
00876 
00877                 if (fabsf(ratio) >= mSpatialPartition->mSlopRatio)
00878                 {
00879                         return TRUE;
00880                 }
00881 
00882                 if (mDistance > mRadius)
00883                 {
00884                         return FALSE;
00885                 }
00886         }
00887         
00888         if (LLDrawable::getCurrentFrame()%mSpatialPartition->mLODPeriod == mLODHash)
00889         {
00890                 return TRUE;
00891         }
00892         
00893         return FALSE;
00894 }
00895 
00896 void LLSpatialGroup::handleInsertion(const TreeNode* node, LLDrawable* drawablep)
00897 {
00898         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
00899         addObject(drawablep, FALSE, TRUE);
00900         unbound();
00901         setState(OBJECT_DIRTY);
00902 }
00903 
00904 void LLSpatialGroup::handleRemoval(const TreeNode* node, LLDrawable* drawable)
00905 {
00906         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
00907         removeObject(drawable, TRUE);
00908         setState(OBJECT_DIRTY);
00909 }
00910 
00911 void LLSpatialGroup::handleDestruction(const TreeNode* node)
00912 {
00913         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
00914         setState(DEAD);
00915         
00916         for (element_iter i = getData().begin(); i != getData().end(); ++i)
00917         {
00918                 LLDrawable* drawable = *i;
00919                 if (drawable->getSpatialGroup() == this)
00920                 {
00921                         drawable->setSpatialGroup(NULL);
00922                 }
00923         }
00924         
00925         clearDrawMap();
00926         mOcclusionVerts = NULL;
00927         mVertexBuffer = NULL;
00928         mBufferMap.clear();
00929         sZombieGroups++;
00930         mOctreeNode = NULL;
00931 }
00932 
00933 void LLSpatialGroup::handleStateChange(const TreeNode* node)
00934 {
00935         //drop bounding box upon state change
00936         if (mOctreeNode != node)
00937         {
00938                 mOctreeNode = (OctreeNode*) node;
00939         }
00940         unbound();
00941 }
00942 
00943 void LLSpatialGroup::handleChildAddition(const OctreeNode* parent, OctreeNode* child) 
00944 {
00945         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
00946         if (child->getListenerCount() == 0)
00947         {
00948                 LLSpatialGroup* group = new LLSpatialGroup(child, mSpatialPartition);
00949                 group->setState(mState & SG_STATE_INHERIT_MASK);
00950         }
00951         else
00952         {
00953                 OCT_ERRS << "LLSpatialGroup redundancy detected." << llendl;
00954         }
00955 
00956         unbound();
00957 }
00958 
00959 void LLSpatialGroup::handleChildRemoval(const OctreeNode* parent, const OctreeNode* child)
00960 {
00961         unbound();
00962 }
00963 
00964 void LLSpatialGroup::destroyGL() 
00965 {
00966         setState(LLSpatialGroup::GEOM_DIRTY | 
00967                                         LLSpatialGroup::OCCLUSION_DIRTY |
00968                                         LLSpatialGroup::IMAGE_DIRTY);
00969         mLastUpdateTime = gFrameTimeSeconds;
00970         mVertexBuffer = NULL;
00971         mBufferMap.clear();
00972 
00973         mOcclusionVerts = NULL;
00974         mReflectionMap = NULL;
00975         clearDrawMap();
00976 
00977         for (LLSpatialGroup::element_iter i = getData().begin(); i != getData().end(); ++i)
00978         {
00979                 LLDrawable* drawable = *i;
00980                 for (S32 j = 0; j < drawable->getNumFaces(); j++)
00981                 {
00982                         LLFace* facep = drawable->getFace(j);
00983                         facep->mVertexBuffer = NULL;
00984                         facep->mLastVertexBuffer = NULL;
00985                 }
00986         }
00987 }
00988 
00989 BOOL LLSpatialGroup::rebound()
00990 {
00991         if (!isState(DIRTY))
00992         {       //return TRUE if we're not empty
00993                 return TRUE;
00994         }
00995         
00996         LLVector3 oldBounds[2];
00997         
00998         if (mSpatialPartition->isVolatile() && isState(QUERY_OUT))
00999         {       //a query has been issued, if our bounding box changes significantly
01000                 //we need to discard the issued query
01001                 oldBounds[0] = mBounds[0];
01002                 oldBounds[1] = mBounds[1];
01003         }
01004         
01005         if (mOctreeNode->getChildCount() == 1 && mOctreeNode->getElementCount() == 0)
01006         {
01007                 LLSpatialGroup* group = (LLSpatialGroup*) mOctreeNode->getChild(0)->getListener(0);
01008                 group->rebound();
01009                 
01010                 //copy single child's bounding box
01011                 mBounds[0] = group->mBounds[0];
01012                 mBounds[1] = group->mBounds[1];
01013                 mExtents[0] = group->mExtents[0];
01014                 mExtents[1] = group->mExtents[1];
01015                 
01016                 group->setState(SKIP_FRUSTUM_CHECK);
01017         }
01018         else if (mOctreeNode->hasLeafState())
01019         { //copy object bounding box if this is a leaf
01020                 boundObjects(TRUE, mExtents[0], mExtents[1]);
01021                 mBounds[0] = mObjectBounds[0];
01022                 mBounds[1] = mObjectBounds[1];
01023         }
01024         else
01025         {
01026                 LLVector3& newMin = mExtents[0];
01027                 LLVector3& newMax = mExtents[1];
01028                 LLSpatialGroup* group = (LLSpatialGroup*) mOctreeNode->getChild(0)->getListener(0);
01029                 group->clearState(SKIP_FRUSTUM_CHECK);
01030                 group->rebound();
01031                 //initialize to first child
01032                 newMin = group->mExtents[0];
01033                 newMax = group->mExtents[1];
01034 
01035                 //first, rebound children
01036                 for (U32 i = 1; i < mOctreeNode->getChildCount(); i++)
01037                 {
01038                         group = (LLSpatialGroup*) mOctreeNode->getChild(i)->getListener(0);
01039                         group->clearState(SKIP_FRUSTUM_CHECK);
01040                         group->rebound();
01041                         const LLVector3& max = group->mExtents[1];
01042                         const LLVector3& min = group->mExtents[0];
01043 
01044                         for (U32 j = 0; j < 3; j++)
01045                         {
01046                                 if (max.mV[j] > newMax.mV[j])
01047                                 {
01048                                         newMax.mV[j] = max.mV[j];
01049                                 }
01050                                 if (min.mV[j] < newMin.mV[j])
01051                                 {
01052                                         newMin.mV[j] = min.mV[j];
01053                                 }
01054                         }
01055                 }
01056 
01057                 boundObjects(FALSE, newMin, newMax);
01058                 
01059                 mBounds[0] = (newMin + newMax)*0.5f;
01060                 mBounds[1] = (newMax - newMin)*0.5f;
01061         }
01062         
01063         if (mSpatialPartition->isVolatile() && isState(QUERY_OUT))
01064         {
01065                 for (U32 i = 0; i < 3 && !isState(DISCARD_QUERY); i++)
01066                 {
01067                         if (fabsf(mBounds[0].mV[i]-oldBounds[0].mV[i]) > SG_DISCARD_TOLERANCE ||
01068                                 fabsf(mBounds[1].mV[i]-oldBounds[1].mV[i]) > SG_DISCARD_TOLERANCE)
01069                         {       //bounding box changed significantly, discard last issued
01070                                 //occlusion query
01071                                 setState(DISCARD_QUERY);
01072                         }
01073                 }
01074         }
01075         
01076         setState(OCCLUSION_DIRTY);
01077         
01078         clearState(DIRTY);
01079 
01080         return TRUE;
01081 }
01082 
01083 //==============================================
01084 
01085 LLSpatialPartition::LLSpatialPartition(U32 data_mask, BOOL is_volatile, U32 buffer_usage)
01086 {
01087         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
01088         mDrawableType = 0;
01089         mPartitionType = LLPipeline::PARTITION_NONE;
01090         mVolatile = is_volatile;
01091         mLODSeed = 0;
01092         mLODPeriod = 1;
01093         mVertexDataMask = data_mask;
01094         mBufferUsage = buffer_usage;
01095         mDepthMask = FALSE;
01096         mSlopRatio = 0.25f;
01097         mRenderByGroup = TRUE;
01098         mImageEnabled = FALSE;
01099 
01100         mOctree = new LLSpatialGroup::OctreeNode(LLVector3d(0,0,0), 
01101                                                                                         LLVector3d(1,1,1), 
01102                                                                                         new LLSpatialGroup::OctreeRoot(), NULL);
01103         new LLSpatialGroup(mOctree, this);
01104 }
01105 
01106 
01107 LLSpatialPartition::~LLSpatialPartition()
01108 {
01109         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
01110         
01111         for (U32 i = 0; i < mOcclusionQueries.size(); i++)
01112         {
01113                 glDeleteQueriesARB(1, (GLuint*)(&(mOcclusionQueries[i])));
01114         }
01115         
01116         delete mOctree;
01117         mOctree = NULL;
01118 }
01119 
01120 
01121 LLSpatialGroup *LLSpatialPartition::put(LLDrawable *drawablep, BOOL was_visible)
01122 {
01123         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
01124         const F32 MAX_MAG = 1000000.f*1000000.f; // 1 million
01125                         
01126         if (drawablep->getPositionGroup().magVecSquared() > MAX_MAG)
01127         {
01128 #if 0 //ndef LL_RELEASE_FOR_DOWNLOAD
01129                 llwarns << "LLSpatialPartition::put Object out of range!" << llendl;
01130                 llinfos << drawablep->getPositionGroup() << llendl;
01131 
01132                 if (drawablep->getVObj())
01133                 {
01134                         llwarns << "Dumping debugging info: " << llendl;
01135                         drawablep->getVObj()->dump(); 
01136                 }
01137 #endif
01138                 return NULL;
01139         }
01140                 
01141         drawablep->updateSpatialExtents();
01142         validate_drawable(drawablep);
01143 
01144         //keep drawable from being garbage collected
01145         LLPointer<LLDrawable> ptr = drawablep;
01146                 
01147         assert_octree_valid(mOctree);
01148         mOctree->insert(drawablep);
01149         assert_octree_valid(mOctree);
01150 
01151         LLSpatialGroup::OctreeNode* node = mOctree->getNodeAt(drawablep);
01152         
01153         LLSpatialGroup* group = (LLSpatialGroup*) node->getListener(0);
01154         if (was_visible && group->isState(LLSpatialGroup::QUERY_OUT))
01155         {
01156                 group->setState(LLSpatialGroup::DISCARD_QUERY);
01157         }
01158 
01159         return group;
01160 }
01161 
01162 BOOL LLSpatialPartition::remove(LLDrawable *drawablep, LLSpatialGroup *curp)
01163 {
01164         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
01165         
01166         drawablep->setSpatialGroup(NULL);
01167 
01168         if (!curp->removeObject(drawablep))
01169         {
01170                 OCT_ERRS << "Failed to remove drawable from octree!" << llendl;
01171         }
01172 
01173         assert_octree_valid(mOctree);
01174         
01175         return TRUE;
01176 }
01177 
01178 void LLSpatialPartition::move(LLDrawable *drawablep, LLSpatialGroup *curp, BOOL immediate)
01179 {
01180         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
01181         LLFastTimer t(LLFastTimer::FTM_UPDATE_MOVE);
01182 
01183         // sanity check submitted by open source user bushing Spatula
01184         // who was seeing crashing here. (See VWR-424 reported by Bunny Mayne)
01185         if (!drawablep) {
01186                 OCT_ERRS << "LLSpatialPartition::move was passed a bad drawable." << llendl;
01187                 return;
01188         }
01189                 
01190         BOOL was_visible = curp ? curp->isVisible() : FALSE;
01191 
01192         if (curp && curp->mSpatialPartition != this)
01193         {
01194                 //keep drawable from being garbage collected
01195                 LLPointer<LLDrawable> ptr = drawablep;
01196                 if (curp->mSpatialPartition->remove(drawablep, curp))
01197                 {
01198                         put(drawablep, was_visible);
01199                         return;
01200                 }
01201                 else
01202                 {
01203                         OCT_ERRS << "Drawable lost between spatial partitions on outbound transition." << llendl;
01204                 }
01205         }
01206                 
01207         if (curp && curp->updateInGroup(drawablep, immediate))
01208         {
01209                 // Already updated, don't need to do anything
01210                 assert_octree_valid(mOctree);
01211                 return;
01212         }
01213 
01214         //keep drawable from being garbage collected
01215         LLPointer<LLDrawable> ptr = drawablep;
01216         if (curp && !remove(drawablep, curp))
01217         {
01218                 OCT_ERRS << "Move couldn't find existing spatial group!" << llendl;
01219         }
01220 
01221         put(drawablep, was_visible);
01222 }
01223 
01224 class LLSpatialShift : public LLSpatialGroup::OctreeTraveler
01225 {
01226 public:
01227         LLSpatialShift(LLVector3 offset) : mOffset(offset) { }
01228         virtual void visit(const LLSpatialGroup::OctreeState* branch) 
01229         { 
01230                 ((LLSpatialGroup*) branch->getListener(0))->shift(mOffset); 
01231         }
01232                 
01233         LLVector3 mOffset;
01234 };
01235 
01236 void LLSpatialPartition::shift(const LLVector3 &offset)
01237 {
01238         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
01239         llinfos << "Shifting octree: " << offset << llendl;
01240         LLSpatialShift shifter(offset);
01241         shifter.traverse(mOctree);
01242 }
01243 
01244 BOOL LLSpatialPartition::checkOcclusion(LLSpatialGroup* group, LLCamera* camera)
01245 {
01246         if (LLPipeline::sUseOcclusion &&
01247                 !group->isState(LLSpatialGroup::ACTIVE_OCCLUSION | LLSpatialGroup::OCCLUDED) &&
01248                 (!camera || !earlyFail(camera, group)))
01249         {
01250                 group->setState(LLSpatialGroup::ACTIVE_OCCLUSION);
01251                 mQueryQueue.push(group);
01252                 return TRUE;
01253         }
01254 
01255         return FALSE;
01256 }
01257 
01258 class LLOctreeCull : public LLSpatialGroup::OctreeTraveler
01259 {
01260 public:
01261         LLOctreeCull(LLCamera* camera)
01262                 : mCamera(camera), mRes(0) { }
01263 
01264         virtual bool earlyFail(const LLSpatialGroup* group)
01265         {
01266                 if (group->mOctreeNode->getParent() &&  //never occlusion cull the root node
01267                         LLPipeline::sUseOcclusion &&                    //never occlusion cull selection
01268                         group->isState(LLSpatialGroup::OCCLUDED))
01269                 {
01270                         return true;
01271                 }
01272                 
01273                 return false;
01274         }
01275         
01276         virtual void traverse(const LLSpatialGroup::TreeNode* n)
01277         {
01278                 LLSpatialGroup* group = (LLSpatialGroup*) n->getListener(0);
01279 
01280                 if (earlyFail(group))
01281                 {
01282                         return;
01283                 }
01284                 
01285                 if (mRes == 2 || 
01286                         (mRes && group->isState(LLSpatialGroup::SKIP_FRUSTUM_CHECK)))
01287                 {       //fully in, just add everything
01288                         LLSpatialGroup::OctreeTraveler::traverse(n);
01289                 }
01290                 else
01291                 {
01292                         mRes = mCamera->AABBInFrustum(group->mBounds[0], group->mBounds[1]);
01293                                 
01294                         if (mRes)
01295                         { //at least partially in, run on down
01296                                 LLSpatialGroup::OctreeTraveler::traverse(n);
01297                         }
01298                         else
01299                         {
01300                                 lateFail(group);
01301                         }
01302                         mRes = 0;
01303                 }
01304         }
01305         
01306         virtual void lateFail(LLSpatialGroup* group)
01307         {
01308                 if (!group->isState(LLSpatialGroup::CULLED))
01309                 { //totally culled, so are all its children
01310                         group->setState(LLSpatialGroup::CULLED, LLSpatialGroup::STATE_MODE_DIFF);
01311                 }
01312         }
01313 
01314         virtual bool checkObjects(const LLSpatialGroup::OctreeState* branch, const LLSpatialGroup* group)
01315         {
01316                         
01317                 if (branch->getElementCount() == 0) //no elements
01318                 {
01319                         return false;
01320                 }
01321                 else if (branch->getChildCount() == 0) //leaf state, already checked tightest bounding box
01322                 {
01323                         return true;
01324                 }
01325                 else if (mRes == 1 && !mCamera->AABBInFrustum(group->mObjectBounds[0], group->mObjectBounds[1])) //no objects in frustum
01326                 {
01327                         return false;
01328                 }
01329                 
01330                 return true;
01331         }
01332 
01333         virtual void preprocess(LLSpatialGroup* group)
01334         {
01335                 if (group->isState(LLSpatialGroup::CULLED))
01336                 {       //this is the first frame this node is visible
01337                         group->clearState(LLSpatialGroup::CULLED);
01338                         if (group->mOctreeNode->hasLeafState())
01339                         {       //if it's a leaf, force it onto the active occlusion list to prevent
01340                                 //massive frame stutters
01341                                 group->mSpatialPartition->checkOcclusion(group, mCamera);
01342                         }
01343                 }
01344 
01345                 if (LLPipeline::sDynamicReflections &&
01346                         group->mOctreeNode->getSize().mdV[0] == 16.0 && 
01347                         group->mDistance < 64.f &&
01348                         group->mLastAddTime < gFrameTimeSeconds - 2.f)
01349                 {
01350                         group->mSpatialPartition->markReimage(group);
01351                 }
01352         }
01353         
01354         virtual void processGroup(LLSpatialGroup* group)
01355         {
01356                 gPipeline.markNotCulled(group, *mCamera);
01357         }
01358         
01359         virtual void visit(const LLSpatialGroup::OctreeState* branch) 
01360         {       
01361                 LLSpatialGroup* group = (LLSpatialGroup*) branch->getListener(0);
01362 
01363                 preprocess(group);
01364                 
01365                 if (checkObjects(branch, group))
01366                 {
01367                         processGroup(group);
01368                 }
01369         }
01370 
01371         LLCamera *mCamera;
01372         S32 mRes;
01373 };
01374 
01375 
01376 class LLOctreeSelect : public LLOctreeCull
01377 {
01378 public:
01379         LLOctreeSelect(LLCamera* camera, std::vector<LLDrawable*>* results)
01380                 : LLOctreeCull(camera), mResults(results) { }
01381 
01382         virtual bool earlyFail(const LLSpatialGroup* group) { return false; }
01383         virtual void lateFail(LLSpatialGroup* group) { }
01384         virtual void preprocess(LLSpatialGroup* group) { }
01385 
01386         virtual void processGroup(LLSpatialGroup* group)
01387         {
01388                 LLSpatialGroup::OctreeState* branch = group->mOctreeNode->getOctState();
01389 
01390                 for (LLSpatialGroup::OctreeState::const_element_iter i = branch->getData().begin(); i != branch->getData().end(); ++i)
01391                 {
01392                         LLDrawable* drawable = *i;
01393                         
01394                         if (!drawable->isDead())
01395                         {
01396                                 if (drawable->isSpatialBridge())
01397                                 {
01398                                         drawable->setVisible(*mCamera, mResults, TRUE);
01399                                 }
01400                                 else
01401                                 {
01402                                         mResults->push_back(drawable);
01403                                 }
01404                         }               
01405                 }
01406         }
01407         
01408         std::vector<LLDrawable*>* mResults;
01409 };
01410 
01411 
01412 void genBoxList()
01413 {
01414         if (sBoxList != 0)
01415         {
01416                 return;
01417         }
01418 
01419         sBoxList = glGenLists(1);
01420         glNewList(sBoxList, GL_COMPILE);
01421         
01422         LLVector3 c,r;
01423         c = LLVector3(0,0,0);
01424         r = LLVector3(1,1,1);
01425 
01426         glBegin(GL_TRIANGLE_STRIP);
01427         //left front
01428         glVertex3fv((c+r.scaledVec(LLVector3(-1,1,-1))).mV);
01429         glVertex3fv((c+r.scaledVec(LLVector3(-1,1,1))).mV);
01430         //right front
01431         glVertex3fv((c+r.scaledVec(LLVector3(1,1,-1))).mV);
01432         glVertex3fv((c+r.scaledVec(LLVector3(1,1,1))).mV);
01433         //right back
01434         glVertex3fv((c+r.scaledVec(LLVector3(1,-1,-1))).mV);
01435         glVertex3fv((c+r.scaledVec(LLVector3(1,-1,1))).mV);
01436         //left back
01437         glVertex3fv((c+r.scaledVec(LLVector3(-1,-1,-1))).mV);
01438         glVertex3fv((c+r.scaledVec(LLVector3(-1,-1,1))).mV);
01439         //left front
01440         glVertex3fv((c+r.scaledVec(LLVector3(-1,1,-1))).mV);
01441         glVertex3fv((c+r.scaledVec(LLVector3(-1,1,1))).mV);
01442         glEnd();
01443         
01444         //bottom
01445         glBegin(GL_TRIANGLE_STRIP);
01446         glVertex3fv((c+r.scaledVec(LLVector3(1,1,-1))).mV);
01447         glVertex3fv((c+r.scaledVec(LLVector3(1,-1,-1))).mV);
01448         glVertex3fv((c+r.scaledVec(LLVector3(-1,1,-1))).mV);
01449         glVertex3fv((c+r.scaledVec(LLVector3(-1,-1,-1))).mV);
01450         glEnd();
01451 
01452         //top
01453         glBegin(GL_TRIANGLE_STRIP);
01454         glVertex3fv((c+r.scaledVec(LLVector3(1,1,1))).mV);
01455         glVertex3fv((c+r.scaledVec(LLVector3(-1,1,1))).mV);
01456         glVertex3fv((c+r.scaledVec(LLVector3(1,-1,1))).mV);
01457         glVertex3fv((c+r.scaledVec(LLVector3(-1,-1,1))).mV);
01458         glEnd();        
01459 
01460         glEndList();
01461 }
01462 
01463 void drawBox(const LLVector3& c, const LLVector3& r)
01464 {
01465         genBoxList();
01466 
01467         glPushMatrix();
01468         glTranslatef(c.mV[0], c.mV[1], c.mV[2]);
01469         glScalef(r.mV[0], r.mV[1], r.mV[2]);
01470         glCallList(sBoxList);
01471         glPopMatrix();
01472 }
01473 
01474 void drawBoxOutline(const LLVector3& pos, const LLVector3& size)
01475 {
01476         LLVector3 v1 = size.scaledVec(LLVector3( 1, 1,1));
01477         LLVector3 v2 = size.scaledVec(LLVector3(-1, 1,1));
01478         LLVector3 v3 = size.scaledVec(LLVector3(-1,-1,1));
01479         LLVector3 v4 = size.scaledVec(LLVector3( 1,-1,1));
01480 
01481         glBegin(GL_LINE_LOOP); //top
01482         glVertex3fv((pos+v1).mV);
01483         glVertex3fv((pos+v2).mV);
01484         glVertex3fv((pos+v3).mV);
01485         glVertex3fv((pos+v4).mV);
01486         glEnd();
01487 
01488         glBegin(GL_LINE_LOOP); //bottom
01489         glVertex3fv((pos-v1).mV);
01490         glVertex3fv((pos-v2).mV);
01491         glVertex3fv((pos-v3).mV);
01492         glVertex3fv((pos-v4).mV);
01493         glEnd();
01494 
01495 
01496         glBegin(GL_LINES);
01497 
01498         //right
01499         glVertex3fv((pos+v1).mV);
01500         glVertex3fv((pos-v3).mV);
01501                         
01502         glVertex3fv((pos+v4).mV);
01503         glVertex3fv((pos-v2).mV);
01504 
01505         //left
01506         glVertex3fv((pos+v2).mV);
01507         glVertex3fv((pos-v4).mV);
01508 
01509         glVertex3fv((pos+v3).mV);
01510         glVertex3fv((pos-v1).mV);
01511 
01512         glEnd();
01513 }
01514 
01515 class LLOctreeDirty : public LLOctreeTraveler<LLDrawable>
01516 {
01517 public:
01518         virtual void visit(const LLOctreeState<LLDrawable>* state)
01519         {
01520                 LLSpatialGroup* group = (LLSpatialGroup*) state->getListener(0);
01521                 group->destroyGL();
01522 
01523                 for (LLSpatialGroup::element_iter i = group->getData().begin(); i != group->getData().end(); ++i)
01524                 {
01525                         LLDrawable* drawable = *i;
01526                         if (drawable->getVObj().notNull() && !group->mSpatialPartition->mRenderByGroup)
01527                         {
01528                                 gPipeline.markRebuild(drawable, LLDrawable::REBUILD_ALL, TRUE);
01529                         }
01530                 }
01531 
01532                 for (LLSpatialGroup::bridge_list_t::iterator i = group->mBridgeList.begin(); i != group->mBridgeList.end(); ++i)
01533                 {
01534                         LLSpatialBridge* bridge = *i;
01535                         traverse(bridge->mOctree);
01536                 }
01537         }
01538 };
01539 
01540 void LLSpatialPartition::restoreGL()
01541 {
01542         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
01543         mOcclusionQueries.clear();
01544         sBoxList = 0;
01545 
01546         //generate query ids
01547         while (mOcclusionQueries.size() < mOccludedList.size())
01548         {
01549                 GLuint id;
01550                 glGenQueriesARB(1, &id);
01551                 mOcclusionQueries.push_back(id);
01552         }
01553 
01554         for (U32 i = 0; i < mOccludedList.size(); i++)
01555         {       //previously issued queries are now invalid
01556                 mOccludedList[i]->setState(LLSpatialGroup::DISCARD_QUERY);
01557         }
01558         
01559         genBoxList();
01560 }
01561 
01562 void LLSpatialPartition::resetVertexBuffers()
01563 {
01564         LLOctreeDirty dirty;
01565         dirty.traverse(mOctree);
01566 
01567         mOcclusionIndices = NULL;
01568 }
01569 
01570 S32 LLSpatialPartition::cull(LLCamera &camera, std::vector<LLDrawable *>* results, BOOL for_select)
01571 {
01572         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
01573         {
01574                 LLFastTimer ftm(LLFastTimer::FTM_CULL_REBOUND);         
01575                 LLSpatialGroup* group = (LLSpatialGroup*) mOctree->getListener(0);
01576                 group->rebound();
01577         }
01578         
01579         if (for_select)
01580         {
01581                 LLOctreeSelect selecter(&camera, results);
01582                 selecter.traverse(mOctree);
01583         }
01584         else
01585         {
01586                 LLFastTimer ftm(LLFastTimer::FTM_FRUSTUM_CULL);         
01587                 LLOctreeCull culler(&camera);
01588                 culler.traverse(mOctree);
01589         }
01590         
01591         return 0;
01592 }
01593 
01594 class LLOctreeClearOccludedNotActive : public LLSpatialGroup::OctreeTraveler
01595 {
01596 public:
01597         LLOctreeClearOccludedNotActive() { }
01598 
01599         virtual void traverse(const LLSpatialGroup::TreeNode* n)
01600         {
01601                 LLSpatialGroup* group = (LLSpatialGroup*) n->getListener(0);
01602                 if ((!group->isState(LLSpatialGroup::ACTIVE_OCCLUSION)) //|| group->isState(LLSpatialGroup::QUERY_PENDING)
01603                         || group->isState(LLSpatialGroup::DEACTIVATE_OCCLUSION))
01604                 {       //the children are all occluded or culled as well
01605                         group->clearState(LLSpatialGroup::OCCLUDED);
01606                         for (U32 i = 0; i < group->mOctreeNode->getChildCount(); i++)
01607                         {
01608                                 traverse(group->mOctreeNode->getChild(i));
01609                         }
01610                 }
01611         }
01612 
01613         virtual void visit(const LLSpatialGroup::OctreeState* branch) { }
01614 };
01615 
01616 class LLQueueNonCulled : public LLSpatialGroup::OctreeTraveler
01617 {
01618 public:
01619         std::queue<LLSpatialGroup*>* mQueue;
01620         LLQueueNonCulled(std::queue<LLSpatialGroup*> *queue) : mQueue(queue) { }
01621 
01622         virtual void traverse(const LLSpatialGroup::TreeNode* n)
01623         {
01624                 LLSpatialGroup* group = (LLSpatialGroup*) n->getListener(0);
01625                 if (group->isState(LLSpatialGroup::OCCLUDED | LLSpatialGroup::CULLED))
01626                 {       //the children are all occluded or culled as well
01627                         return;
01628                 }
01629 
01630                 if (!group->isState(LLSpatialGroup::IN_QUEUE))
01631                 {
01632                         group->setState(LLSpatialGroup::IN_QUEUE);
01633                         mQueue->push(group);
01634                 }
01635 
01636                 LLSpatialGroup::OctreeTraveler::traverse(n);
01637         }
01638 
01639         virtual void visit(const LLSpatialGroup::OctreeState* branch) { }
01640 };
01641 
01642 BOOL earlyFail(LLCamera* camera, LLSpatialGroup* group)
01643 {
01644         LLVector3 c = group->mBounds[0];
01645         LLVector3 r = group->mBounds[1]*SG_OCCLUSION_FUDGE + LLVector3(0.2f,0.2f,0.2f);
01646     
01647         //if (group->isState(LLSpatialGroup::CULLED)) // || 
01648         if (!camera->AABBInFrustum(c, r))
01649         {
01650                 return TRUE;
01651         }
01652 
01653         LLVector3 e = camera->getOrigin();
01654         
01655         LLVector3 min = c - r;
01656         LLVector3 max = c + r;
01657         
01658         for (U32 j = 0; j < 3; j++)
01659         {
01660                 if (e.mV[j] < min.mV[j] || e.mV[j] > max.mV[j])
01661                 {
01662                         return FALSE;
01663                 }
01664         }
01665 
01666         return TRUE;
01667 }
01668 
01669 void LLSpatialPartition::markReimage(LLSpatialGroup* group)
01670 {
01671         if (mImageEnabled && group->isState(LLSpatialGroup::IMAGE_DIRTY))
01672         {       
01673                 if (!group->isState(LLSpatialGroup::IN_IMAGE_QUEUE))
01674                 {
01675                         group->setState(LLSpatialGroup::IN_IMAGE_QUEUE);
01676                         mImageQueue.push(group);
01677                 }
01678         }
01679 }
01680 
01681 void LLSpatialPartition::processImagery(LLCamera* camera)
01682 {
01683         if (!mImageEnabled)
01684         {
01685                 return;
01686         }
01687 
01688         U32 process_count = 1;
01689 
01690         while (process_count > 0 && !mImageQueue.empty())
01691         {
01692                 LLPointer<LLSpatialGroup> group = mImageQueue.front();
01693                 mImageQueue.pop();
01694         
01695                 group->clearState(LLSpatialGroup::IN_IMAGE_QUEUE);
01696 
01697                 if (group->isDead())
01698                 {
01699                         continue;
01700                 }
01701 
01702                 if (LLPipeline::sDynamicReflections)
01703                 {
01704                         process_count--;
01705                         LLVector3 origin = group->mBounds[0];
01706                         
01707                         LLCamera cube_cam;
01708                         cube_cam.setOrigin(origin);
01709                         cube_cam.setFar(64.f);
01710 
01711                         LLPointer<LLCubeMap> cube_map = group->mReflectionMap;
01712                         group->mReflectionMap = NULL;
01713                         if (cube_map.isNull())
01714                         {
01715                                 cube_map = new LLCubeMap();
01716                                 cube_map->initGL();
01717                         }
01718 
01719                         if (gPipeline.mCubeBuffer.isNull())
01720                         {
01721                                 gPipeline.mCubeBuffer = new LLCubeMap();
01722                                 gPipeline.mCubeBuffer->initGL();
01723                         }
01724 
01725                         S32 res = gSavedSettings.getS32("RenderReflectionRes");
01726                         gPipeline.generateReflectionMap(gPipeline.mCubeBuffer, cube_cam, 128);
01727                         gPipeline.blurReflectionMap(gPipeline.mCubeBuffer, cube_map, res);
01728                         group->mReflectionMap = cube_map;
01729                         group->setState(LLSpatialGroup::GEOM_DIRTY);
01730                 }
01731 
01732                 group->clearState(LLSpatialGroup::IMAGE_DIRTY);
01733         }
01734 }
01735 
01736 void validate_occlusion_list(std::vector<LLPointer<LLSpatialGroup> >& occluded_list)
01737 {
01738 #if !LL_RELEASE_FOR_DOWNLOAD
01739         for (U32 i = 0; i < occluded_list.size(); i++)
01740         {
01741                 LLSpatialGroup* group = occluded_list[i];
01742                 for (U32 j = i+1; j < occluded_list.size(); j++)
01743                 {
01744                         if (occluded_list[i] == occluded_list[j])
01745                         {
01746                                 llerrs << "Duplicate node in occlusion list." << llendl;
01747                         }
01748                 }
01749 
01750                 LLSpatialGroup::OctreeNode* parent = group->mOctreeNode->getOctParent();
01751                 while (parent)
01752                 {
01753                         LLSpatialGroup* parent_group = (LLSpatialGroup*) parent->getListener(0);
01754                         if (parent_group->isState(LLSpatialGroup::OCCLUDED))
01755                         {
01756                                 llerrs << "Child node of occluded node in occlusion list (redundant query)." << llendl;
01757                         }
01758                         parent = parent->getOctParent();
01759                 }
01760         }
01761 #endif
01762 }
01763 
01764 void LLSpatialPartition::processOcclusion(LLCamera* camera)
01765 {
01766         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
01767         LLSpatialGroup* rootGroup = (LLSpatialGroup*) mOctree->getListener(0);
01768         {
01769                 LLFastTimer ftm(LLFastTimer::FTM_CULL_REBOUND); 
01770                 rootGroup->rebound();
01771         }
01772         
01773         //update potentials 
01774         if (!rootGroup->isState(LLSpatialGroup::IN_QUEUE))
01775         {
01776                 rootGroup->setState(LLSpatialGroup::IN_QUEUE);
01777                 mOcclusionQueue.push(rootGroup);
01778         }
01779 
01780         const U32 MAX_PULLED = 32;
01781         const U32 MAX_PUSHED = mOcclusionQueue.size();
01782         U32 count = 0;
01783         U32 pcount = 0;
01784         
01785         while (pcount < MAX_PUSHED && count < MAX_PULLED && !mOcclusionQueue.empty())
01786         {
01787                 LLFastTimer t(LLFastTimer::FTM_OCCLUSION);
01788 
01789                 LLPointer<LLSpatialGroup> group = mOcclusionQueue.front();
01790                 if (!group->isState(LLSpatialGroup::IN_QUEUE))
01791                 {
01792                         OCT_ERRS << "Spatial Group State Error.  Group in queue not tagged as such." << llendl;
01793                 }
01794 
01795                 mOcclusionQueue.pop();
01796                 group->clearState(LLSpatialGroup::IN_QUEUE);
01797 
01798                 if (group->isDead())
01799                 {
01800                         continue;
01801                 }
01802 
01803                 if (group->isState(LLSpatialGroup::CULLED | LLSpatialGroup::OCCLUDED))
01804                 {       //already culled, skip it
01805                         continue;
01806                 }
01807 
01808                 //before we process, enqueue this group's children
01809                 for (U32 i = 0; i < group->mOctreeNode->getChildCount(); i++)
01810                 {
01811                         LLSpatialGroup* child = (LLSpatialGroup*) group->mOctreeNode->getChild(i)->getListener(0);
01812 
01813                         //if (!child->isState(LLSpatialGroup::OCCLUDED | LLSpatialGroup::CULLED)
01814                         if (!child->isState(LLSpatialGroup::IN_QUEUE | LLSpatialGroup::ACTIVE_OCCLUSION))
01815                         {
01816                                 child->setState(LLSpatialGroup::IN_QUEUE);
01817                                 mOcclusionQueue.push(child);
01818                         }
01819                 }
01820                 
01821                 if (earlyFail(camera, group))
01822                 {
01823                         sg_assert(!group->isState(LLSpatialGroup::OCCLUDED));
01824                         group->setState(LLSpatialGroup::IN_QUEUE);
01825                         mOcclusionQueue.push(group);
01826                         pcount++;
01827                         continue;
01828                 }
01829                 
01830                 //add to pending queue
01831                 if (!group->isState(LLSpatialGroup::ACTIVE_OCCLUSION))
01832                 {
01833 #if LL_OCTREE_PARANOIA_CHECK
01834                         for (U32 i = 0; i < mOccludedList.size(); ++i)
01835                         {
01836                                 sg_assert(mOccludedList[i] != group);
01837                         }
01838 #endif
01839                         group->setState(LLSpatialGroup::ACTIVE_OCCLUSION);
01840                         mQueryQueue.push(group);
01841                         count++;
01842                 }
01843         }
01844 
01845         //read back results from last frame
01846         for (U32 i = 0; i < mOccludedList.size(); i++)
01847         {
01848                 LLFastTimer t(LLFastTimer::FTM_OCCLUSION_READBACK);
01849 
01850                 if (mOccludedList[i]->isDead() || mOccludedList[i]->isState(LLSpatialGroup::DEACTIVATE_OCCLUSION))
01851                 {
01852                         continue;
01853                 }
01854                 GLuint res = 0;
01855                         
01856                 if (mOccludedList[i]->isState(LLSpatialGroup::EARLY_FAIL | LLSpatialGroup::DISCARD_QUERY) ||
01857                         !mOccludedList[i]->isState(LLSpatialGroup::QUERY_OUT))
01858                 {
01859                         mOccludedList[i]->clearState(LLSpatialGroup::EARLY_FAIL);
01860                         mOccludedList[i]->clearState(LLSpatialGroup::DISCARD_QUERY);
01861                         res = 1;
01862                 }
01863                 else
01864                 {       
01865                         glGetQueryObjectuivARB(mOcclusionQueries[i], GL_QUERY_RESULT_ARB, &res);        
01866                         stop_glerror();
01867                 }
01868                 
01869                 if (res) //NOT OCCLUDED
01870                 {       
01871                         if (mOccludedList[i]->isState(LLSpatialGroup::OCCLUDED))
01872                         {       //this node was occluded last frame
01873                                 LLSpatialGroup::OctreeNode* node = mOccludedList[i]->mOctreeNode;
01874                                 //add any immediate children to the queue that are not already there
01875                                 for (U32 j = 0; j < node->getChildCount(); j++)
01876                                 {
01877                                         LLSpatialGroup* group = (LLSpatialGroup*) node->getChild(j)->getListener(0);
01878                                         checkOcclusion(group, camera);
01879                                 }
01880                         }
01881                         
01882                         //clear occlusion status for everything not on the active list
01883                         LLOctreeClearOccludedNotActive clear_occluded;
01884                         mOccludedList[i]->setState(LLSpatialGroup::DEACTIVATE_OCCLUSION);
01885                         mOccludedList[i]->clearState(LLSpatialGroup::OCCLUDED);
01886                         mOccludedList[i]->clearState(LLSpatialGroup::OCCLUDING);
01887                         clear_occluded.traverse(mOccludedList[i]->mOctreeNode);
01888                 }
01889                 else
01890                 { //OCCLUDED
01891                         if (mOccludedList[i]->isState(LLSpatialGroup::OCCLUDING))
01892                         {
01893                                 if (!mOccludedList[i]->isState(LLSpatialGroup::OCCLUDED))
01894                                 {
01895                                         LLSpatialGroup::OctreeNode* oct_parent = (LLSpatialGroup::OctreeNode*) mOccludedList[i]->mOctreeNode->getParent();
01896                                         if (oct_parent)
01897                                         {
01898                                                 LLSpatialGroup* parent = (LLSpatialGroup*) oct_parent->getListener(0);
01899                                                 
01900                                                 if (checkOcclusion(parent, camera))
01901                                                 {       //force a guess on the parent and siblings              
01902                                                         for (U32 i = 0; i < parent->mOctreeNode->getChildCount(); i++)
01903                                                         {
01904                                                                 LLSpatialGroup* child = (LLSpatialGroup*) parent->mOctreeNode->getChild(i)->getListener(0);
01905                                                                 checkOcclusion(child, camera);  
01906                                                         }
01907                                                 }
01908                                         }
01909 
01910                                         //take children off the active list
01911                                         mOccludedList[i]->setState(LLSpatialGroup::DEACTIVATE_OCCLUSION, LLSpatialGroup::STATE_MODE_BRANCH);
01912                                         mOccludedList[i]->clearState(LLSpatialGroup::DEACTIVATE_OCCLUSION);
01913                                 }
01914                                 mOccludedList[i]->setState(LLSpatialGroup::OCCLUDED, LLSpatialGroup::STATE_MODE_DIFF);
01915                         }
01916                         else
01917                         {
01918                                 //take children off the active list
01919                                 mOccludedList[i]->setState(LLSpatialGroup::DEACTIVATE_OCCLUSION, LLSpatialGroup::STATE_MODE_BRANCH);
01920                                                         
01921                                 //keep this node on the active list
01922                                 mOccludedList[i]->clearState(LLSpatialGroup::DEACTIVATE_OCCLUSION);
01923 
01924                                 //this node is a top level occluder
01925                                 mOccludedList[i]->setState(LLSpatialGroup::OCCLUDING);
01926                         }
01927                 }
01928 
01929                 mOccludedList[i]->clearState(LLSpatialGroup::QUERY_OUT);
01930         }
01931 
01932         //remove non-occluded groups from occluded list
01933         for (U32 i = 0; i < mOccludedList.size(); )
01934         {
01935                 if (mOccludedList[i]->isDead() || //needs to be deleted
01936                         !mOccludedList[i]->isState(LLSpatialGroup::OCCLUDING) || //is not occluding
01937                         mOccludedList[i]->isState(LLSpatialGroup::DEACTIVATE_OCCLUSION)) //parent is occluded
01938                 {
01939                         LLSpatialGroup* groupp = mOccludedList[i];
01940                         if (!groupp->isDead())
01941                         {
01942                                 groupp->clearState(LLSpatialGroup::ACTIVE_OCCLUSION);
01943                                 groupp->clearState(LLSpatialGroup::DEACTIVATE_OCCLUSION);
01944                                 groupp->clearState(LLSpatialGroup::OCCLUDING);
01945                         }
01946                         mOccludedList.erase(mOccludedList.begin()+i);
01947                 }
01948                 else
01949                 {
01950                         i++;
01951                 }
01952         }
01953 
01954         validate_occlusion_list(mOccludedList);
01955 
01956         //pump some non-culled items onto the occlusion list
01957         //count = MAX_PULLED;
01958         while (!mQueryQueue.empty())
01959         {
01960                 LLPointer<LLSpatialGroup> group = mQueryQueue.front();
01961                 mQueryQueue.pop();
01962         //group->clearState(LLSpatialGroup::QUERY_PENDING);
01963                 mOccludedList.push_back(group);
01964         }
01965 
01966         //generate query ids
01967         while (mOcclusionQueries.size() < mOccludedList.size())
01968         {
01969                 GLuint id;
01970                 glGenQueriesARB(1, &id);
01971                 mOcclusionQueries.push_back(id);
01972         }
01973 }
01974 
01975 class LLOcclusionIndexBuffer : public LLVertexBuffer
01976 {
01977 public:
01978         LLOcclusionIndexBuffer(U32 size)
01979                 : LLVertexBuffer(0, GL_STREAM_DRAW_ARB)
01980         {
01981                 allocateBuffer(0, size, TRUE);
01982 
01983                 LLStrider<U32> idx;
01984 
01985                 getIndexStrider(idx);
01986 
01987                 //12 triangles' indices
01988                 idx[0] = 1; idx[1] = 0; idx[2] = 2; //front
01989                 idx[3] = 3; idx[4] = 2; idx[5] = 0;
01990 
01991                 idx[6] = 4; idx[7] = 5; idx[8] = 1; //top
01992                 idx[9] = 0; idx[10] = 1; idx[11] = 5; 
01993 
01994                 idx[12] = 5; idx[13] = 4; idx[14] = 6; //back
01995                 idx[15] = 7; idx[16] = 6; idx[17] = 4;
01996 
01997                 idx[18] = 6; idx[19] = 7; idx[20] = 3; //bottom
01998                 idx[21] = 2; idx[22] = 3; idx[23] = 7;
01999 
02000                 idx[24] = 0; idx[25] = 5; idx[26] = 3; //left
02001                 idx[27] = 6; idx[28] = 3; idx[29] = 5;
02002 
02003                 idx[30] = 4; idx[31] = 1; idx[32] = 7; //right
02004                 idx[33] = 2; idx[34] = 7; idx[35] = 1;
02005         }
02006 
02007         //virtual BOOL useVBOs() const { return FALSE; }
02008 
02009         void setBuffer(U32 data_mask)
02010         {
02011                 if (useVBOs())
02012                 {
02013                         glBindBufferARB(GL_ELEMENT_ARRAY_BUFFER_ARB, mGLIndices);
02014                         sIBOActive = TRUE;
02015                         unmapBuffer();
02016                 }
02017                 else if (sIBOActive)
02018                 {
02019                         glBindBufferARB(GL_ELEMENT_ARRAY_BUFFER_ARB, 0);
02020                         sIBOActive = FALSE;
02021                 }
02022                 
02023                 sGLRenderIndices = mGLIndices;
02024         }
02025 };
02026 
02027 class LLOcclusionVertexBuffer : public LLVertexBuffer
02028 {
02029 public:
02030         LLOcclusionVertexBuffer(S32 usage)
02031                 : LLVertexBuffer(MAP_VERTEX, usage)
02032         {
02033                 allocateBuffer(8, 0, TRUE);
02034         }
02035 
02036         //virtual BOOL useVBOs() const { return FALSE; }
02037 
02038         void setBuffer(U32 data_mask)
02039         {
02040                 if (useVBOs())
02041                 {
02042                         glBindBufferARB(GL_ARRAY_BUFFER_ARB, mGLBuffer);
02043                         sVBOActive = TRUE;
02044                         unmapBuffer();
02045                 }
02046                 else if (sVBOActive)
02047                 {
02048                         glBindBufferARB(GL_ARRAY_BUFFER_ARB, 0);
02049                         sVBOActive = FALSE;
02050                 }
02051                 
02052                 if (data_mask)
02053                 {
02054                         glVertexPointer(3,GL_FLOAT, 0, useVBOs() ? 0 : mMappedData);
02055                 }
02056                 
02057                 sGLRenderBuffer = mGLBuffer;
02058         }
02059 };
02060 
02061 void LLSpatialPartition::buildOcclusion()
02062 {
02063         if (mOccludedList.empty())
02064         {
02065                 return;
02066         }
02067 
02068         BOOL reset_all = FALSE;
02069         if (mOcclusionIndices.isNull())
02070         {
02071                 mOcclusionIndices = new LLOcclusionIndexBuffer(36);
02072                 reset_all = TRUE;
02073         }
02074         
02075         //fill occlusion vertex buffers
02076         for (U32 i = 0; i < mOccludedList.size(); i++)
02077         {
02078                 LLSpatialGroup* group = mOccludedList[i];
02079 
02080                 if (group->isState(LLSpatialGroup::OCCLUSION_DIRTY) || reset_all)
02081                 {
02082                         LLFastTimer ftm(LLFastTimer::FTM_REBUILD_OCCLUSION_VB);
02083 
02084                         if (group->mOcclusionVerts.isNull())
02085                         {
02086                                 group->mOcclusionVerts = new LLOcclusionVertexBuffer(GL_STREAM_DRAW_ARB);
02087                         }
02088         
02089                         group->clearState(LLSpatialGroup::OCCLUSION_DIRTY);
02090                         
02091                         LLStrider<LLVector3> vert;
02092 
02093                         group->mOcclusionVerts->getVertexStrider(vert);
02094 
02095                         LLVector3 r = group->mBounds[1]*SG_OCCLUSION_FUDGE + LLVector3(0.1f,0.1f,0.1f);
02096 
02097                         for (U32 k = 0; k < 3; k++)
02098                         {
02099                                 r.mV[k] = llmin(group->mBounds[1].mV[k]+0.25f, r.mV[k]);
02100                         }
02101 
02102                         *vert++ = group->mBounds[0] + r.scaledVec(LLVector3(-1,1,1)); //   0 - left top front
02103                         *vert++ = group->mBounds[0] + r.scaledVec(LLVector3(1,1,1));  //   1 - right top front
02104                         *vert++ = group->mBounds[0] + r.scaledVec(LLVector3(1,-1,1)); //   2 - right bottom front
02105                         *vert++ = group->mBounds[0] + r.scaledVec(LLVector3(-1,-1,1)); //  3 - left bottom front
02106 
02107                         *vert++ = group->mBounds[0] + r.scaledVec(LLVector3(1,1,-1)); //  4 - left top back
02108                         *vert++ = group->mBounds[0] + r.scaledVec(LLVector3(-1,1,-1)); //   5 - right top back
02109                         *vert++ = group->mBounds[0] + r.scaledVec(LLVector3(-1,-1,-1)); //  6 - right bottom back
02110                         *vert++ = group->mBounds[0] + r.scaledVec(LLVector3(1,-1,-1)); // 7 -left bottom back
02111                 }
02112         }
02113 
02114 /*      for (U32 i = 0; i < mOccludedList.size(); i++)
02115         {
02116                 LLSpatialGroup* group = mOccludedList[i];
02117                 if (!group->mOcclusionVerts.isNull() && group->mOcclusionVerts->isLocked())
02118                 {
02119                         LLFastTimer ftm(LLFastTimer::FTM_REBUILD_OCCLUSION_VB);
02120                         group->mOcclusionVerts->setBuffer(0);
02121                 }
02122         }*/
02123 }
02124 
02125 void LLSpatialPartition::doOcclusion(LLCamera* camera)
02126 {
02127         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
02128 
02129         LLFastTimer t(LLFastTimer::FTM_RENDER_OCCLUSION);
02130 
02131 #if LL_OCTREE_PARANOIA_CHECK  
02132         LLSpatialGroup* check = (LLSpatialGroup*) mOctree->getListener(0);
02133         check->validate();
02134 #endif
02135 
02136         stop_glerror();
02137         
02138         U32 num_verts = mOccludedList.size() * 8;
02139 
02140         if (num_verts == 0)
02141         {
02142                 return;
02143         }
02144 
02145         //actually perform the occlusion queries
02146         LLGLDepthTest gls_depth(GL_TRUE, GL_FALSE);
02147         LLGLDisable(GL_TEXTURE_2D);
02148         gPipeline.disableLights();
02149         LLGLEnable cull_face(GL_CULL_FACE);
02150         LLGLDisable blend(GL_BLEND);
02151         LLGLDisable alpha_test(GL_ALPHA_TEST);
02152         LLGLDisable fog(GL_FOG);
02153 
02154         //********UMICH 3D LAB********
02155         // protect the color mask change for correct anaglyph render
02156         GLboolean mask[4];
02157         glGetBooleanv(GL_COLOR_WRITEMASK,mask);
02158         //********UMICH 3D LAB********
02159 
02160         glColorMask(GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE);
02161         glColor4f(1,1,1,1);
02162 
02163         mOcclusionIndices->setBuffer(0);
02164 
02165         U32* indicesp = (U32*) mOcclusionIndices->getIndicesPointer();
02166 
02167         glDisableClientState(GL_NORMAL_ARRAY);
02168         glDisableClientState(GL_TEXTURE_COORD_ARRAY);
02169         glDisableClientState(GL_COLOR_ARRAY);
02170 #if !LL_RELEASE_FOR_DOWNLOAD
02171         LLGLState::checkClientArrays(LLVertexBuffer::MAP_VERTEX);
02172 #endif
02173         for (U32 i = 0; i < mOccludedList.size(); i++)
02174         {
02175 #if LL_OCTREE_PARANOIA_CHECK
02176                 for (U32 j = i+1; j < mOccludedList.size(); j++)
02177                 {
02178                         sg_assert(mOccludedList[i] != mOccludedList[j]);
02179                 }
02180 #endif
02181                 LLSpatialGroup* group = mOccludedList[i];
02182                 if (group->isDead())
02183                 {
02184                         continue;
02185                 }
02186 
02187                 if (earlyFail(camera, group))
02188                 {
02189                         group->setState(LLSpatialGroup::EARLY_FAIL);
02190                 }
02191                 else
02192                 { //early rejection criteria passed, send some geometry to the query
02193                         group->mOcclusionVerts->setBuffer(LLVertexBuffer::MAP_VERTEX);
02194                         glBeginQueryARB(GL_SAMPLES_PASSED_ARB, mOcclusionQueries[i]);                                   
02195                         glDrawRangeElements(GL_TRIANGLES, 0, 7, 36,
02196                                                         GL_UNSIGNED_INT, indicesp);
02197                         glEndQueryARB(GL_SAMPLES_PASSED_ARB);
02198 
02199                         group->setState(LLSpatialGroup::QUERY_OUT);
02200                         group->clearState(LLSpatialGroup::DISCARD_QUERY);
02201                 }               
02202         }
02203         stop_glerror();
02204         
02205         gPipeline.mTrianglesDrawn += mOccludedList.size()*12;
02206 
02207         glFlush();
02208 
02209         //********UMICH 3D LAB********
02210         glColorMask(mask[0], mask[1], mask[2], mask[3]);
02211         //********UMICH 3D LAB********
02212 }
02213 
02214 class LLOctreeGet : public LLSpatialGroup::OctreeTraveler
02215 {
02216 public:
02217         LLOctreeGet(LLVector3 pos, F32 rad, LLDrawable::drawable_set_t* results, BOOL lights)
02218                 : mPosition(pos), mRad(rad), mResults(results), mLights(lights), mRes(0)
02219         {
02220 
02221         }
02222 
02223         virtual void traverse(const LLSpatialGroup::TreeNode* n)
02224         {
02225                 LLSpatialGroup* group = (LLSpatialGroup*) n->getListener(0);
02226 
02227                 if (mRes == 2) 
02228                 { //fully in, just add everything
02229                         LLSpatialGroup::OctreeTraveler::traverse(n);
02230                 }
02231                 else
02232                 {
02233                         LLVector3 center, size;
02234                         
02235                         center = group->mBounds[0];
02236                         size = group->mBounds[1];
02237                                                 
02238                         mRes = LLSphereAABB(center, size, mPosition, mRad);             
02239                         if (mRes > 0)
02240                         {
02241                                 LLSpatialGroup::OctreeTraveler::traverse(n);
02242                         }
02243                         mRes = 0;
02244                 }
02245         }
02246 
02247         static BOOL skip(LLDrawable* drawable, BOOL get_lights)
02248         {
02249                 if (get_lights != drawable->isLight())
02250                 {
02251                         return TRUE;
02252                 }
02253                 if (get_lights && drawable->getVObj()->isHUDAttachment())
02254                 {
02255                         return TRUE; // no lighting from HUD objects
02256                 }
02257                 if (get_lights && drawable->isState(LLDrawable::ACTIVE))
02258                 {
02259                         return TRUE; // ignore active lights
02260                 }
02261                 return FALSE;
02262         }
02263 
02264         virtual void visit(const LLSpatialGroup::OctreeState* branch) 
02265         { 
02266                 for (LLSpatialGroup::OctreeState::const_element_iter i = branch->getData().begin(); i != branch->getData().end(); ++i)
02267                 {
02268                         LLDrawable* drawable = *i;
02269                         if (!skip(drawable, mLights))
02270                         {
02271                                 if (mRes == 2)
02272                                 {
02273                                         mResults->insert(drawable);
02274                                 }
02275                                 else
02276                                 {
02277                                         LLVector3 v = LLVector3(drawable->getPositionGroup())-mPosition;
02278                                         float dsq = v.magVecSquared();
02279                                         float maxd = mRad + drawable->getVisibilityRadius();
02280                                         if (dsq <= maxd*maxd)
02281                                         {
02282                                                 mResults->insert(drawable);
02283                                         }
02284                                 }
02285                         }
02286                 }
02287         }
02288 
02289         LLVector3 mPosition;
02290         F32 mRad;
02291         LLDrawable::drawable_set_t* mResults;
02292         BOOL mLights;
02293         U32 mRes;
02294 };
02295 
02296 S32 LLSpatialPartition::getDrawables(const LLVector3& pos, F32 rad,
02297                                                                          LLDrawable::drawable_set_t &results,
02298                                                                          BOOL get_lights)
02299 {
02300         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
02301         
02302         LLOctreeGet getter(pos, rad, &results, get_lights);
02303         getter.traverse(mOctree);
02304 
02305         return results.size();
02306 }
02307 
02308 S32 LLSpatialPartition::getObjects(const LLVector3& pos, F32 rad, LLDrawable::drawable_set_t &results)
02309 {
02310         LLSpatialGroup* group = (LLSpatialGroup*) mOctree->getListener(0);
02311         group->rebound();
02312         return getDrawables(pos, rad, results, FALSE);
02313 }
02314 
02315 S32 LLSpatialPartition::getLights(const LLVector3& pos, F32 rad, LLDrawable::drawable_set_t &results)
02316 {
02317         return getDrawables(pos, rad, results, TRUE);
02318 }
02319 
02320 void pushVerts(LLDrawInfo* params, U32 mask)
02321 {
02322         params->mVertexBuffer->setBuffer(mask);
02323         U32* indicesp = (U32*) params->mVertexBuffer->getIndicesPointer();
02324         glDrawRangeElements(params->mParticle ? GL_POINTS : GL_TRIANGLES, params->mStart, params->mEnd, params->mCount,
02325                                         GL_UNSIGNED_INT, indicesp+params->mOffset);
02326 }
02327 
02328 void pushVerts(LLSpatialGroup* group, U32 mask)
02329 {
02330         LLDrawInfo* params = NULL;
02331 
02332         for (LLSpatialGroup::draw_map_t::iterator i = group->mDrawMap.begin(); i != group->mDrawMap.end(); ++i)
02333         {
02334                 for (LLSpatialGroup::drawmap_elem_t::iterator j = i->second.begin(); j != i->second.end(); ++j) 
02335                 {
02336                         params = *j;
02337                         pushVerts(params, mask);
02338                 }
02339         }
02340 }
02341 
02342 void pushVertsColorCoded(LLSpatialGroup* group, U32 mask)
02343 {
02344         LLDrawInfo* params = NULL;
02345 
02346         LLColor4 colors[] = {
02347                 LLColor4::green,
02348                 LLColor4::green1,
02349                 LLColor4::green2,
02350                 LLColor4::green3,
02351                 LLColor4::green4,
02352                 LLColor4::green5,
02353                 LLColor4::green6
02354         };
02355                 
02356         static const U32 col_count = sizeof(colors)/sizeof(LLColor4);
02357 
02358         U32 col = 0;
02359 
02360         for (LLSpatialGroup::draw_map_t::iterator i = group->mDrawMap.begin(); i != group->mDrawMap.end(); ++i)
02361         {
02362                 for (LLSpatialGroup::drawmap_elem_t::iterator j = i->second.begin(); j != i->second.end(); ++j) 
02363                 {
02364                         params = *j;
02365                         glColor4f(colors[col].mV[0], colors[col].mV[1], colors[col].mV[2], 0.5f);
02366                         params->mVertexBuffer->setBuffer(mask);
02367                         U32* indicesp = (U32*) params->mVertexBuffer->getIndicesPointer();
02368                         glDrawRangeElements(params->mParticle ? GL_POINTS : GL_TRIANGLES, params->mStart, params->mEnd, params->mCount,
02369                                                         GL_UNSIGNED_INT, indicesp+params->mOffset);
02370                         col = (col+1)%col_count;
02371                 }
02372         }
02373 }
02374 
02375 void renderOctree(LLSpatialGroup* group)
02376 {
02377         //render solid object bounding box, color
02378         //coded by buffer usage and activity
02379         LLGLDepthTest depth(GL_TRUE, GL_FALSE);
02380         glBlendFunc(GL_SRC_ALPHA, GL_ONE);
02381         LLVector4 col;
02382         if (group->mBuilt > 0.f)
02383         {
02384                 group->mBuilt -= 2.f * gFrameIntervalSeconds;
02385                 if (group->mBufferUsage == GL_STATIC_DRAW_ARB)
02386                 {
02387                         col.setVec(1.0f, 0, 0, group->mBuilt*0.5f);
02388                 }
02389                 else 
02390                 {
02391                         col.setVec(0.1f,0.1f,1,0.1f);
02392                         //col.setVec(1.0f, 1.0f, 0, sinf(group->mBuilt*3.14159f)*0.5f);
02393                 }
02394 
02395                 if (group->mBufferUsage != GL_STATIC_DRAW_ARB)
02396                 {
02397                         if (group->mBufferUsage == GL_DYNAMIC_DRAW_ARB)
02398                         {
02399                                 glColor4f(1,0,0,group->mBuilt);
02400                         }
02401                         else
02402                         {
02403                                 glColor4f(1,1,0,group->mBuilt);
02404                         }
02405 
02406                         LLGLDepthTest gl_depth(FALSE, FALSE);
02407                         glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
02408                         for (LLSpatialGroup::element_iter i = group->getData().begin(); i != group->getData().end(); ++i)
02409                         {
02410                                 LLDrawable* drawable = *i;
02411                                 for (S32 j = 0; j < drawable->getNumFaces(); j++)
02412                                 {
02413                                         LLFace* face = drawable->getFace(j);
02414                                         if (gFrameTimeSeconds - face->mLastUpdateTime < 0.5f && face->mVertexBuffer.notNull())
02415                                         { 
02416                                                 face->mVertexBuffer->setBuffer(LLVertexBuffer::MAP_VERTEX);
02417                                                 //drawBox((face->mExtents[0] + face->mExtents[1])*0.5f,
02418                                                 //              (face->mExtents[1]-face->mExtents[0])*0.5f);
02419                                                 glDrawElements(GL_TRIANGLES, face->getIndicesCount(), GL_UNSIGNED_INT, 
02420                                                         ((U32*) face->mVertexBuffer->getIndicesPointer())+face->getIndicesStart());
02421                                         }
02422                                 }
02423                         }
02424                         glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
02425                 }
02426         }
02427         else
02428         {
02429                 if (group->mBufferUsage == GL_STATIC_DRAW_ARB && !group->getData().empty() 
02430                         && group->mSpatialPartition->mRenderByGroup)
02431                 {
02432                         col.setVec(0.8f, 0.4f, 0.1f, 0.1f);
02433                 }
02434                 else
02435                 {
02436                         col.setVec(0.1f, 0.1f, 1.f, 0.1f);
02437                 }
02438         }
02439 
02440         glColor4fv(col.mV);
02441         drawBox(group->mObjectBounds[0], group->mObjectBounds[1]*1.01f+LLVector3(0.001f, 0.001f, 0.001f));
02442         glDepthMask(GL_TRUE);
02443         glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
02444 
02445         //draw opaque outline
02446         glColor4f(col.mV[0], col.mV[1], col.mV[2], 1.f);
02447         drawBoxOutline(group->mObjectBounds[0], group->mObjectBounds[1]);
02448 
02449         if (group->mOctreeNode->hasLeafState())
02450         {
02451                 glColor4f(1,1,1,1);
02452         }
02453         else
02454         {
02455                 glColor4f(0,1,1,1);
02456         }
02457                                         
02458         drawBoxOutline(group->mBounds[0],group->mBounds[1]);
02459         
02460 //      LLSpatialGroup::OctreeNode* node = group->mOctreeNode;
02461 //      glColor4f(0,1,0,1);
02462 //      drawBoxOutline(LLVector3(node->getCenter()), LLVector3(node->getSize()));
02463 }
02464 
02465 void renderVisibility(LLSpatialGroup* group)
02466 {
02467         LLGLEnable blend(GL_BLEND);
02468         glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
02469         LLGLEnable cull(GL_CULL_FACE);
02470         glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
02471         {
02472                 LLGLDepthTest depth_under(GL_TRUE, GL_FALSE, GL_GREATER);
02473                 glColor4f(0, 0.5f, 0, 0.5f);
02474                 pushVerts(group, LLVertexBuffer::MAP_VERTEX);
02475         }
02476 
02477         {
02478                 LLGLDepthTest depth_over(GL_TRUE, GL_FALSE, GL_LEQUAL);
02479                 pushVertsColorCoded(group, LLVertexBuffer::MAP_VERTEX);
02480 
02481                 glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
02482 
02483                 pushVertsColorCoded(group, LLVertexBuffer::MAP_VERTEX);
02484         }
02485 }
02486 
02487 void renderBoundingBox(LLDrawable* drawable)
02488 {
02489         if (drawable->isSpatialBridge())
02490         {
02491                 glColor4f(1,0.5f,0,1);
02492         }
02493         else if (drawable->getVOVolume())
02494         {
02495                 if (drawable->isRoot())
02496                 {
02497                         glColor4f(1,1,0,1);
02498                 }
02499                 else
02500                 {
02501                         glColor4f(0,1,0,1);
02502                 }
02503         }
02504         else if (drawable->getVObj())
02505         {
02506                 switch (drawable->getVObj()->getPCode())
02507                 {
02508                         case LLViewerObject::LL_VO_SURFACE_PATCH:
02509                                         glColor4f(0,1,1,1);
02510                                         break;
02511                         case LLViewerObject::LL_VO_CLOUDS:
02512                                         glColor4f(0.5f,0.5f,0.5f,1.0f);
02513                                         break;
02514                         case LLViewerObject::LL_VO_PART_GROUP:
02515                                         glColor4f(0,0,1,1);
02516                                         break;
02517                         case LLViewerObject::LL_VO_WATER:
02518                                         glColor4f(0,0.5f,1,1);
02519                                         break;
02520                         case LL_PCODE_LEGACY_TREE:
02521                                         glColor4f(0,0.5f,0,1);
02522                         default:
02523                                         glColor4f(1,0,1,1);
02524                                         break;
02525                 }
02526         }
02527         else 
02528         {
02529                 glColor4f(1,0,0,1);
02530         }
02531 
02532         const LLVector3* ext;
02533         LLVector3 pos, size;
02534 
02535         //render face bounding boxes
02536         for (S32 i = 0; i < drawable->getNumFaces(); i++)
02537         {
02538                 LLFace* facep = drawable->getFace(i);
02539 
02540                 ext = facep->mExtents;
02541 
02542                 if (ext[0].isExactlyZero() && ext[1].isExactlyZero())
02543                 {
02544                         continue;
02545                 }
02546                 pos = (ext[0] + ext[1]) * 0.5f;
02547                 size = (ext[1] - ext[0]) * 0.5f;
02548                 drawBoxOutline(pos,size);
02549         }
02550 
02551         //render drawable bounding box
02552         ext = drawable->getSpatialExtents();
02553 
02554         pos = (ext[0] + ext[1]) * 0.5f;
02555         size = (ext[1] - ext[0]) * 0.5f;
02556         
02557         drawBoxOutline(pos,size);
02558 }
02559 
02560 void renderTexturePriority(LLDrawable* drawable)
02561 {
02562         for (int face=0; face<drawable->getNumFaces(); ++face)
02563         {
02564                 LLFace *facep = drawable->getFace(face);
02565                 
02566                 LLVector4 cold(0,0,0.25f);
02567                 LLVector4 hot(1,0.25f,0.25f);
02568         
02569                 LLVector4 boost_cold(0,0,0,0);
02570                 LLVector4 boost_hot(0,1,0,1);
02571                 
02572                 LLGLDisable blend(GL_BLEND);
02573                 
02574                 //LLViewerImage* imagep = facep->getTexture();
02575                 //if (imagep)
02576                 {
02577         
02578                         //F32 vsize = LLVOVolume::getTextureVirtualSize(facep);
02579                         //F32 vsize = imagep->mMaxVirtualSize;
02580                         F32 vsize = facep->getPixelArea();
02581 
02582                         if (vsize > sCurMaxTexPriority)
02583                         {
02584                                 sCurMaxTexPriority = vsize;
02585                         }
02586                         
02587                         F32 t = vsize/sLastMaxTexPriority;
02588                         
02589                         LLVector4 col = lerp(cold, hot, t);
02590                         glColor4fv(col.mV);
02591                 }
02592                 //else
02593                 //{
02594                 //      glColor4f(1,0,1,1);
02595                 //}
02596 
02597                 
02598                 
02599                 LLVector3 center = (facep->mExtents[1]+facep->mExtents[0])*0.5f;
02600                 LLVector3 size = (facep->mExtents[1]-facep->mExtents[0])*0.5f + LLVector3(0.01f, 0.01f, 0.01f);
02601                 drawBox(center, size);
02602                 
02603                 /*S32 boost = imagep->getBoostLevel();
02604                 if (boost)
02605                 {
02606                         F32 t = (F32) boost / (F32) (LLViewerImage::BOOST_MAX_LEVEL-1);
02607                         LLVector4 col = lerp(boost_cold, boost_hot, t);
02608                         LLGLEnable blend_on(GL_BLEND);
02609                         glBlendFunc(GL_SRC_ALPHA, GL_ONE);
02610                         glColor4fv(col.mV);
02611                         drawBox(center, size);
02612                         glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
02613                 }*/
02614         }
02615 }
02616 
02617 void renderPoints(LLDrawable* drawablep)
02618 {
02619         LLGLDepthTest depth(GL_FALSE, GL_FALSE);
02620         glBegin(GL_POINTS);
02621         glColor3f(1,1,1);
02622         LLVector3 center(drawablep->getPositionGroup());
02623         for (S32 i = 0; i < drawablep->getNumFaces(); i++)
02624         {
02625                 glVertex3fv(drawablep->getFace(i)->mCenterLocal.mV);
02626         }
02627         glEnd();
02628 }
02629 
02630 void renderTextureAnim(LLDrawInfo* params)
02631 {
02632         if (!params->mTextureMatrix)
02633         {
02634                 return;
02635         }
02636         
02637         LLGLEnable blend(GL_BLEND);
02638         glColor4f(1,1,0,0.5f);
02639         pushVerts(params, LLVertexBuffer::MAP_VERTEX);
02640 }
02641 
02642 class LLOctreeRenderNonOccluded : public LLOctreeTraveler<LLDrawable>
02643 {
02644 public:
02645         LLOctreeRenderNonOccluded() {}
02646         
02647         virtual void traverse(const LLSpatialGroup::OctreeNode* node)
02648         {
02649                 const LLSpatialGroup::OctreeState* state = node->getOctState();
02650                 LLSpatialGroup* group = (LLSpatialGroup*) node->getListener(0);
02651                 
02652         
02653                 if ((!gPipeline.sUseOcclusion || !group->isState(LLSpatialGroup::OCCLUDED)) &&
02654                         !group->isState(LLSpatialGroup::CULLED))
02655                 {
02656                         state->accept(this);
02657 
02658                         for (U32 i = 0; i < state->getChildCount(); i++)
02659                         {
02660                                 traverse(state->getChild(i));
02661                         }
02662                         
02663                         //draw tight fit bounding boxes for spatial group
02664                         if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_OCTREE))
02665                         {       
02666                                 renderOctree(group);
02667                         }
02668 
02669                         //render visibility wireframe
02670                         if (group->mSpatialPartition->mRenderByGroup &&
02671                                 gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_OCCLUSION) &&
02672                                 !group->isState(LLSpatialGroup::GEOM_DIRTY))
02673                         {
02674                                 renderVisibility(group);
02675                         }
02676                 }
02677         }
02678 
02679         virtual void visit(const LLSpatialGroup::OctreeState* branch)
02680         {
02681                 LLSpatialGroup* group = (LLSpatialGroup*) branch->getListener(0);
02682 
02683                 if (group->isState(LLSpatialGroup::CULLED | LLSpatialGroup::OCCLUDED))
02684                 {
02685                         return;
02686                 }
02687 
02688                 LLVector3 nodeCenter = group->mBounds[0];
02689                 LLVector3 octCenter = LLVector3(group->mOctreeNode->getCenter());
02690 
02691                 for (LLSpatialGroup::OctreeState::const_element_iter i = branch->getData().begin(); i != branch->getData().end(); ++i)
02692                 {
02693                         LLDrawable* drawable = *i;
02694                                                 
02695                         if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_BBOXES))
02696                         {
02697                                 renderBoundingBox(drawable);                    
02698                         }
02699                         
02700                         if (drawable->getVOVolume() && gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_TEXTURE_PRIORITY))
02701                         {
02702                                 renderTexturePriority(drawable);
02703                         }
02704 
02705                         if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_POINTS))
02706                         {
02707                                 renderPoints(drawable);
02708                         }
02709                 }
02710                 
02711                 for (LLSpatialGroup::draw_map_t::iterator i = group->mDrawMap.begin(); i != group->mDrawMap.end(); ++i)
02712                 {
02713                         LLSpatialGroup::drawmap_elem_t& draw_vec = i->second;   
02714                         for (LLSpatialGroup::drawmap_elem_t::iterator j = draw_vec.begin(); j != draw_vec.end(); ++j)   
02715                         {
02716                                 LLDrawInfo* draw_info = *j;
02717                                 if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_TEXTURE_ANIM))
02718                                 {
02719                                         renderTextureAnim(draw_info);
02720                                 }
02721                         }
02722                 }
02723         }
02724 };
02725 
02726 void LLSpatialPartition::renderDebug()
02727 {
02728         if (!gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_OCTREE |
02729                                                                           LLPipeline::RENDER_DEBUG_OCCLUSION |
02730                                                                           LLPipeline::RENDER_DEBUG_BBOXES |
02731                                                                           LLPipeline::RENDER_DEBUG_POINTS |
02732                                                                           LLPipeline::RENDER_DEBUG_TEXTURE_PRIORITY |
02733                                                                           LLPipeline::RENDER_DEBUG_TEXTURE_ANIM))
02734         {
02735                 return;
02736         }
02737         
02738         if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_TEXTURE_PRIORITY))
02739         {
02740                 //sLastMaxTexPriority = lerp(sLastMaxTexPriority, sCurMaxTexPriority, gFrameIntervalSeconds);
02741                 sLastMaxTexPriority = (F32) gCamera->getScreenPixelArea();
02742                 sCurMaxTexPriority = 0.f;
02743         }
02744 
02745         LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION);
02746         
02747         LLGLDisable cullface(GL_CULL_FACE);
02748         LLGLEnable blend(GL_BLEND);
02749         glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
02750         LLGLDisable tex(GL_TEXTURE_2D);
02751         gPipeline.disableLights();
02752                 
02753         LLOctreeRenderNonOccluded render_debug;
02754         render_debug.traverse(mOctree);
02755 
02756         LLGLDisable cull_face(GL_CULL_FACE);
02757         
02758         if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_OCCLUSION) && !mOccludedList.empty() &&
02759                 mOcclusionIndices.notNull())
02760         {
02761                 LLGLDisable fog(GL_FOG);
02762                 LLGLDepthTest gls_depth(GL_FALSE);
02763                 glBlendFunc(GL_SRC_ALPHA, GL_ONE);
02764                 mOcclusionIndices->setBuffer(0);
02765                 U32* indicesp = (U32*) mOcclusionIndices->getIndicesPointer();
02766 
02767                 LLGLEnable blend(GL_BLEND);
02768                 glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
02769                 LLGLEnable cull(GL_CULL_FACE);
02770                 glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
02771 
02772                 for (U32 i = 0; i < mOccludedList.size(); i++)
02773                 {       //draw occluded nodes
02774                         LLSpatialGroup* node = mOccludedList[i];
02775                         if (node->isDead() ||
02776                                 !node->isState(LLSpatialGroup::OCCLUDED) ||
02777                                 node->mOcclusionVerts.isNull())
02778                         {
02779                                 continue;
02780                         }
02781                         
02782                         node->mOcclusionVerts->setBuffer(LLVertexBuffer::MAP_VERTEX);
02783                         {
02784                                 LLGLDepthTest depth_under(GL_TRUE, GL_FALSE, GL_GREATER);
02785                                 glColor4f(0.5, 0.5f, 0, 0.25f);
02786                                 glDrawRangeElements(GL_TRIANGLES, 0, 7, 36,
02787                                                         GL_UNSIGNED_INT, indicesp);
02788                         }
02789 
02790                         {
02791                                 LLGLDepthTest depth_over(GL_TRUE, GL_FALSE, GL_LEQUAL);
02792                                 glColor4f(0.0,1.0f,1.0f,1.0f);
02793                                 glDrawRangeElements(GL_TRIANGLES, 0, 7, 36,
02794                                                         GL_UNSIGNED_INT, indicesp);
02795                         }
02796                 }
02797 
02798                 glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
02799         }       
02800 }
02801 
02802 
02803 BOOL LLSpatialPartition::isVisible(const LLVector3& v)
02804 {
02805         if (!gCamera->sphereInFrustum(v, 4.0f))
02806         {
02807                 return FALSE;
02808         }
02809 
02810         return TRUE;
02811 }
02812 
02813 class LLOctreePick : public LLSpatialGroup::OctreeTraveler
02814 {
02815 public:
02816         LLVector3 mStart;
02817         LLVector3 mEnd;
02818         LLDrawable* mRet;
02819         
02820         LLOctreePick(LLVector3 start, LLVector3 end)
02821         : mStart(start), mEnd(end)
02822         {
02823                 mRet = NULL;
02824         }
02825 
02826         virtual LLDrawable* check(const LLSpatialGroup::OctreeNode* node)
02827         {
02828                 const LLSpatialGroup::OctreeState* state = node->getOctState();
02829                 state->accept(this);
02830         
02831                 for (U32 i = 0; i < node->getChildCount(); i++)
02832                 {
02833                         const LLSpatialGroup::OctreeNode* child = node->getChild(i);
02834                         LLVector3 res;
02835 
02836                         LLSpatialGroup* group = (LLSpatialGroup*) child->getListener(0);
02837                         
02838                         LLVector3 size;
02839                         LLVector3 center;
02840                         
02841                         size = group->mBounds[1];
02842                         center = group->mBounds[0];
02843                         
02844                         if (LLLineSegmentAABB(mStart, mEnd, center, size))
02845                         {
02846                                 check(child);
02847                         }
02848                 }       
02849 
02850                 return mRet;
02851         }
02852 
02853         virtual void visit(const LLSpatialGroup::OctreeState* branch) 
02854         {       
02855                 for (LLSpatialGroup::OctreeState::const_element_iter i = branch->getData().begin(); i != branch->getData().end(); ++i)
02856                 {
02857                         check(*i);
02858                 }
02859         }
02860 
02861         virtual bool check(LLDrawable* drawable)
02862         {
02863                 LLViewerObject* vobj = drawable->getVObj();
02864                 if (vobj->lineSegmentIntersect(mStart, mEnd))
02865                 {
02866                         mRet = vobj->mDrawable;
02867                 }
02868                 
02869                 return false;
02870         }
02871 };
02872 
02873 LLDrawable*     LLSpatialPartition::pickDrawable(const LLVector3& start, const LLVector3& end, LLVector3& collision)
02874 {
02875         LLOctreePick pick(start, end);
02876         LLDrawable* ret = pick.check(mOctree);
02877         collision.setVec(pick.mEnd);
02878         return ret;
02879 }
02880 
02881 LLDrawInfo::LLDrawInfo(U32 start, U32 end, U32 count, U32 offset, 
02882                                            LLViewerImage* texture, LLVertexBuffer* buffer,
02883                                            BOOL fullbright, U8 bump, BOOL particle, F32 part_size)
02884 :
02885         mVertexBuffer(buffer),
02886         mTexture(texture),
02887         mTextureMatrix(NULL),
02888         mStart(start),
02889         mEnd(end),
02890         mCount(count),
02891         mOffset(offset), 
02892         mFullbright(fullbright),
02893         mBump(bump),
02894         mParticle(particle),
02895         mPartSize(part_size),
02896         mVSize(0.f)
02897 {
02898 }
02899 
02900 LLDrawInfo::~LLDrawInfo()       
02901 {
02902 
02903 }
02904 
02905 LLVertexBuffer* LLGeometryManager::createVertexBuffer(U32 type_mask, U32 usage)
02906 {
02907         return new LLVertexBuffer(type_mask, usage);
02908 }
Generated on Thu Jul 1 06:09:12 2010 for Second Life Viewer by  doxygen 1.4.7