for SH-3472: prioritize object loading

9 files changed, 423 insertions, 226 deletions

diff --git a/indra/newview/lldrawable.cpp b/indra/newview/lldrawable.cpp
index e29551e83c..c782fbfe7e 100644
--- a/indra/newview/lldrawable.cpp
+++ b/indra/newview/lldrawable.cpp
@@ -470,7 +470,13 @@ void LLDrawable::makeActive()
 		}
 		updatePartition();
 	}
-
+	else if (!isRoot() && !mParent->isActive()) //this should not happen, but occasionally it does...
+	{
+		mParent->makeActive();
+		//NOTE: linked set will now NEVER become static
+		mParent->setState(LLDrawable::ACTIVE_CHILD);
+	}
+	
 	llassert(isAvatar() || isRoot() || mParent->isActive());
 }
 
@@ -1093,6 +1099,11 @@ LLSpatialBridge::LLSpatialBridge(LLDrawable* root, BOOL render_by_group, U32 dat
 	{
 		part->put(this);
 	}
+
+	if(mDrawable->getEntry()->hasVOCacheEntry())
+	{
+		((LLVOCacheEntry*)mDrawable->getEntry()->getVOCacheEntry())->setBridgeChild();
+	}
 }
 
 LLSpatialBridge::~LLSpatialBridge()
@@ -1470,9 +1481,9 @@ void LLSpatialBridge::cleanupReferences()
 		dummy_entry = new LLVOCacheEntry();
 		dummy_entry->setOctreeEntry(mEntry);
 		dummy_entry->addChild((LLVOCacheEntry*)mDrawable->getEntry()->getVOCacheEntry());
-		llassert(!mDrawable->getParent());
+		//llassert(!mDrawable->getParent());
 		
-		mDrawable->mParent = this;
+		//mDrawable->mParent = this;
 	}
 
 	LLDrawable::cleanupReferences();
diff --git a/indra/newview/llviewerobjectlist.cpp b/indra/newview/llviewerobjectlist.cpp
index d41eee5926..f3552e2c2b 100644
--- a/indra/newview/llviewerobjectlist.cpp
+++ b/indra/newview/llviewerobjectlist.cpp
@@ -376,7 +376,7 @@ LLViewerObject* LLViewerObjectList::processObjectUpdateFromCache(LLVOCacheEntry*
 void LLViewerObjectList::processObjectUpdate(LLMessageSystem *mesgsys,
 											 void **user_data,
 											 const EObjectUpdateType update_type,
-											 bool cached, bool compressed)
+											 bool compressed)
 {
 	LLFastTimer t(FTM_PROCESS_OBJECTS);	
 	
@@ -395,7 +395,7 @@ void LLViewerObjectList::processObjectUpdate(LLMessageSystem *mesgsys,
 	num_objects = mesgsys->getNumberOfBlocksFast(_PREHASH_ObjectData);
 
 	// I don't think this case is ever hit.  TODO* Test this.
-	if (!cached && !compressed && update_type != OUT_FULL)
+	if (!compressed && update_type != OUT_FULL)
 	{
 		//llinfos << "TEST: !cached && !compressed && update_type != OUT_FULL" << llendl;
 		gTerseObjectUpdates += num_objects;
@@ -439,7 +439,6 @@ void LLViewerObjectList::processObjectUpdate(LLMessageSystem *mesgsys,
 
 	U8 compressed_dpbuffer[2048];
 	LLDataPackerBinaryBuffer compressed_dp(compressed_dpbuffer, 2048);
-	LLDataPacker *cached_dpp = NULL;
 	LLViewerStatsRecorder& recorder = LLViewerStatsRecorder::instance();
 
 	for (i = 0; i < num_objects; i++)
@@ -449,34 +448,7 @@ void LLViewerObjectList::processObjectUpdate(LLMessageSystem *mesgsys,
 		BOOL justCreated = FALSE;
 		S32	msg_size = 0;
 
-		if (cached)
-		{
-			U32 id;
-			U32 crc;
-			mesgsys->getU32Fast(_PREHASH_ObjectData, _PREHASH_ID, id, i);
-			mesgsys->getU32Fast(_PREHASH_ObjectData, _PREHASH_CRC, crc, i);
-			msg_size += sizeof(U32) * 2;
-		
-			// Lookup data packer and add this id to cache miss lists if necessary.
-			U8 cache_miss_type = LLViewerRegion::CACHE_MISS_TYPE_NONE;
-			cached_dpp = regionp->getDP(id, crc, cache_miss_type);
-			if (cached_dpp)
-			{
-				// Cache Hit.
-				cached_dpp->reset();
-				cached_dpp->unpackUUID(fullid, "ID");
-				cached_dpp->unpackU32(local_id, "LocalID");
-				cached_dpp->unpackU8(pcode, "PCode");
-			}
-			else
-			{
-				// Cache Miss.
-				recorder.cacheMissEvent(id, update_type, cache_miss_type, msg_size);
-
-				continue; // no data packer, skip this object
-			}
-		}
-		else if (compressed)
+		if (compressed)
 		{
 			S32	uncompressed_length = 2048;
 			compressed_dp.reset();			
@@ -575,9 +547,6 @@ void LLViewerObjectList::processObjectUpdate(LLMessageSystem *mesgsys,
 					continue;
 				}
 			}
-			else if (cached) // Cache hit only?
-			{
-			}
 			else
 			{
 				if (update_type != OUT_FULL)
@@ -610,7 +579,7 @@ void LLViewerObjectList::processObjectUpdate(LLMessageSystem *mesgsys,
 			}
 			justCreated = TRUE;
 			mNumNewObjects++;
-			sCacheHitRate.addValue(cached ? 100.f : 0.f);
+			sCacheHitRate.addValue(0.f);
 
 		}
 
@@ -641,11 +610,6 @@ void LLViewerObjectList::processObjectUpdate(LLMessageSystem *mesgsys,
 				}
 			}
 		}
-		else if (cached) // Cache hit only?
-		{
-			objectp->mLocalID = local_id;
-			processUpdateCore(objectp, user_data, i, update_type, cached_dpp, justCreated);
-		}
 		else
 		{
 			if (update_type == OUT_FULL)
@@ -668,14 +632,51 @@ void LLViewerObjectList::processCompressedObjectUpdate(LLMessageSystem *mesgsys,
 											 void **user_data,
 											 const EObjectUpdateType update_type)
 {
-	processObjectUpdate(mesgsys, user_data, update_type, false, true);
+	processObjectUpdate(mesgsys, user_data, update_type, true);
 }
 
 void LLViewerObjectList::processCachedObjectUpdate(LLMessageSystem *mesgsys,
 											 void **user_data,
 											 const EObjectUpdateType update_type)
 {
-	processObjectUpdate(mesgsys, user_data, update_type, true, false);
+	//processObjectUpdate(mesgsys, user_data, update_type, true, false);
+
+	S32 num_objects = mesgsys->getNumberOfBlocksFast(_PREHASH_ObjectData);
+	gFullObjectUpdates += num_objects;
+
+	U64 region_handle;
+	mesgsys->getU64Fast(_PREHASH_RegionData, _PREHASH_RegionHandle, region_handle);	
+	LLViewerRegion *regionp = LLWorld::getInstance()->getRegionFromHandle(region_handle);
+	if (!regionp)
+	{
+		llwarns << "Object update from unknown region! " << region_handle << llendl;
+		return;
+	}
+
+	LLViewerStatsRecorder& recorder = LLViewerStatsRecorder::instance();
+
+	for (S32 i = 0; i < num_objects; i++)
+	{
+		S32	msg_size = 0;
+		U32 id;
+		U32 crc;
+		mesgsys->getU32Fast(_PREHASH_ObjectData, _PREHASH_ID, id, i);
+		mesgsys->getU32Fast(_PREHASH_ObjectData, _PREHASH_CRC, crc, i);
+		msg_size += sizeof(U32) * 2;
+		
+		// Lookup data packer and add this id to cache miss lists if necessary.
+		U8 cache_miss_type = LLViewerRegion::CACHE_MISS_TYPE_NONE;
+		if(!regionp->probeCache(id, crc, cache_miss_type))
+		{
+			// Cache Miss.
+			recorder.cacheMissEvent(id, update_type, cache_miss_type, msg_size);
+
+			continue; // no data packer, skip this object
+		}
+		sCacheHitRate.addValue(100.f);
+	}
+
+	return;
 }	
 
 void LLViewerObjectList::dirtyAllObjectInventory()
diff --git a/indra/newview/llviewerobjectlist.h b/indra/newview/llviewerobjectlist.h
index 1476f44215..17c8c86ff5 100644
--- a/indra/newview/llviewerobjectlist.h
+++ b/indra/newview/llviewerobjectlist.h
@@ -83,7 +83,7 @@ public:
 	void processUpdateCore(LLViewerObject* objectp, void** data, U32 block, const EObjectUpdateType update_type, 
 		                   LLDataPacker* dpp, bool justCreated, bool from_cache = false);
 	LLViewerObject* processObjectUpdateFromCache(LLVOCacheEntry* entry, LLViewerRegion* regionp);
-	void processObjectUpdate(LLMessageSystem *mesgsys, void **user_data, EObjectUpdateType update_type, bool cached=false, bool compressed=false);
+	void processObjectUpdate(LLMessageSystem *mesgsys, void **user_data, EObjectUpdateType update_type, bool compressed=false);
 	void processCompressedObjectUpdate(LLMessageSystem *mesgsys, void **user_data, EObjectUpdateType update_type);
 	void processCachedObjectUpdate(LLMessageSystem *mesgsys, void **user_data, EObjectUpdateType update_type);
 	void updateApparentAngles(LLAgent &agent);
diff --git a/indra/newview/llvieweroctree.cpp b/indra/newview/llvieweroctree.cpp
index 143f2a6819..b6e0674a95 100644
--- a/indra/newview/llvieweroctree.cpp
+++ b/indra/newview/llvieweroctree.cpp
@@ -126,13 +126,14 @@ S32 AABBSphereIntersectR2(const LLVector4a& min, const LLVector4a& max, const LL
 //-----------------------------------------------------------------------------------
 //class LLViewerOctreeEntry definitions
 //-----------------------------------------------------------------------------------
-LLViewerOctreeEntry::LLViewerOctreeEntry() : mGroup(NULL)
+LLViewerOctreeEntry::LLViewerOctreeEntry() 
+	: mGroup(NULL),
+	  mBinRadius(0.f),
+	  mBinIndex(-1)
 {
 	mPositionGroup.clear();
 	mExtents[0].clear();
-	mExtents[1].clear();
-	mBinRadius = 0.f;
-	mBinIndex = -1;
+	mExtents[1].clear();	
 
 	for(S32 i = 0; i < NUM_DATA_TYPE; i++)
 	{
diff --git a/indra/newview/llvieweroctree.h b/indra/newview/llvieweroctree.h
index 498ec3e75d..b89014119c 100644
--- a/indra/newview/llvieweroctree.h
+++ b/indra/newview/llvieweroctree.h
@@ -135,7 +135,7 @@ public:
 	const LLVector4a*    getSpatialExtents() const;
 	LLviewerOctreeGroup* getGroup()const;
 	const LLVector4a&    getPositionGroup() const;
-
+	
 	void setBinRadius(F32 rad)  {mEntry->mBinRadius = rad;}
 	void setSpatialExtents(const LLVector3& min, const LLVector3& max);
 	void setSpatialExtents(const LLVector4a& min, const LLVector4a& max);
@@ -247,9 +247,9 @@ protected:
 	U32         mState;
 	OctreeNode* mOctreeNode;	
 
-	LL_ALIGN_16(LLVector4a mBounds[2]);       // bounding box (center, size) of this node and all its children (tight fit to objects)
-	LL_ALIGN_16(LLVector4a mObjectBounds[2]); // bounding box (center, size) of objects in this node
-	LL_ALIGN_16(LLVector4a mExtents[2]); // extents (min, max) of this node and all its children
+	LL_ALIGN_16(LLVector4a mBounds[2]);        // bounding box (center, size) of this node and all its children (tight fit to objects)
+	LL_ALIGN_16(LLVector4a mObjectBounds[2]);  // bounding box (center, size) of objects in this node
+	LL_ALIGN_16(LLVector4a mExtents[2]);       // extents (min, max) of this node and all its children
 	LL_ALIGN_16(LLVector4a mObjectExtents[2]); // extents (min, max) of objects in this node
 
 public:
diff --git a/indra/newview/llviewerregion.cpp b/indra/newview/llviewerregion.cpp
index 1adab15d70..24bd68825b 100644
--- a/indra/newview/llviewerregion.cpp
+++ b/indra/newview/llviewerregion.cpp
@@ -100,6 +100,8 @@ public:
 			mSeedCapMaxAttemptsBeforeLogin(MAX_SEED_CAP_ATTEMPTS_BEFORE_LOGIN),
 			mSeedCapAttempts(0),
 			mHttpResponderID(0),
+			mLastCameraUpdate(0),
+			mLastCameraOrigin(),
 		    // I'd prefer to set the LLCapabilityListener name to match the region
 		    // name -- it's disappointing that's not available at construction time.
 		    // We could instead store an LLCapabilityListener*, making
@@ -136,13 +138,14 @@ public:
 	// Misc
 	LLVLComposition *mCompositionp;		// Composition layer for the surface
 
-	LLVOCacheEntry::vocache_entry_map_t	mCacheMap; //all cached entries
-	LLVOCacheEntry::vocache_entry_set_t mActiveSet; //all active entries;
-	LLVOCacheEntry::vocache_entry_set_t mWaitingSet; //entries waiting for LLDrawable to be generated.
-	LLVOCacheEntry::vocache_entry_set_t mVisibleEntries; //visible root entries of a linked set.
+	LLVOCacheEntry::vocache_entry_map_t	  mCacheMap; //all cached entries
+	LLVOCacheEntry::vocache_entry_set_t   mActiveSet; //all active entries;
+	LLVOCacheEntry::vocache_entry_set_t   mWaitingSet; //entries waiting for LLDrawable to be generated.	
 	std::set< LLPointer<LLVOCacheEntry> > mDummyEntries; //dummy vo cache entries, for LLSpatialBridge use.
-	std::set< LLviewerOctreeGroup* >      mVisibleGroups; //visible llspatialgroup
-	LLVOCachePartition*                 mVOCachePartition;
+	std::set< LLviewerOctreeGroup* >      mVisibleGroups; //visible groupa
+	LLVOCachePartition*                   mVOCachePartition;
+	LLVOCacheEntry::vocache_entry_set_t   mVisibleEntries; //must-be-created visible entries wait for objects creation.	
+	LLVOCacheEntry::vocache_entry_priority_list_t mWaitingList; //transient list storing sorted visible entries waiting for object creation.
 
 	// time?
 	// LRU info?
@@ -168,6 +171,9 @@ public:
 
 	//spatial partitions for objects in this region
 	std::vector<LLViewerOctreePartition*> mObjectPartition;
+
+	LLVector3 mLastCameraOrigin;
+	U32       mLastCameraUpdate;
 };
 
 // support for secondlife:///app/region/{REGION} SLapps
@@ -736,27 +742,16 @@ void LLViewerRegion::dirtyHeights()
 
 void LLViewerRegion::replaceCacheEntry(LLVOCacheEntry* old_entry, LLVOCacheEntry* new_entry)
 {
-	LLPointer<LLViewerOctreeEntry> oct_entry;
 	U32 state = LLVOCacheEntry::INACTIVE;
 
 	if(old_entry)
 	{
-		oct_entry = old_entry->getEntry();
+		new_entry->copy(old_entry);
 		state = old_entry->getState();		
-
-		while(old_entry->getNumOfChildren() > 0)
-		{
-			new_entry->addChild(old_entry->getNextChild());
-		}
-
 		killCacheEntry(old_entry);
 	}
 
 	mImpl->mCacheMap[new_entry->getLocalID()] = new_entry;
-	if(oct_entry.notNull())
-	{
-		new_entry->setOctreeEntry(oct_entry);
-	}
 
 	if(state == LLVOCacheEntry::ACTIVE)
 	{
@@ -767,7 +762,7 @@ void LLViewerRegion::replaceCacheEntry(LLVOCacheEntry* old_entry, LLVOCacheEntry
 	{
 		mImpl->mWaitingSet.insert(new_entry);
 	}
-	else if(old_entry && oct_entry)
+	else if(old_entry && new_entry->getEntry())
 	{
 		addToVOCacheTree(new_entry);
 	}
@@ -790,19 +785,23 @@ void LLViewerRegion::killCacheEntry(LLVOCacheEntry* entry)
 	else if(entry->isState(LLVOCacheEntry::WAITING))
 	{
 		mImpl->mWaitingSet.erase(entry);
-	}	
-
-	//2, kill LLViewerObject if exists
-	//this should be done by the rendering pipeline automatically.
-
-	//3, remove from mVOCachePartition
-	if(entry->isState(LLVOCacheEntry::INACTIVE) && entry->getEntry())
+	}
+	else if(entry->isState(LLVOCacheEntry::IN_QUEUE))
 	{
+		mImpl->mVisibleEntries.erase(entry);
+	}
+	else if(entry->isState(LLVOCacheEntry::INACTIVE))
+	{
+		//remove from mVOCachePartition
 		removeFromVOCacheTree(entry);
 	}
 
+	//kill LLViewerObject if exists
+	//this should be done by the rendering pipeline automatically.
+	
 	entry->setState(LLVOCacheEntry::INACTIVE);
-	//4, remove from mCacheMap, real deletion
+	
+	//remove from mCacheMap, real deletion
 	mImpl->mCacheMap.erase(entry->getLocalID());
 }
 
@@ -885,7 +884,10 @@ void LLViewerRegion::addToVOCacheTree(LLVOCacheEntry* entry)
 	{
 		return;
 	}
-	llassert(!entry->getGroup());
+	if(entry->getGroup()) //already in octree.
+	{
+		return;
+	}
 
 	mImpl->mVOCachePartition->addEntry(entry->getEntry());
 }
@@ -896,18 +898,31 @@ void LLViewerRegion::removeFromVOCacheTree(LLVOCacheEntry* entry)
 	{
 		return;
 	}
+	if(!entry->getGroup())
+	{
+		return;
+	}
 
 	mImpl->mVOCachePartition->removeEntry(entry->getEntry());
 }
 
-//add the visible root entry of a linked set
+//add the visible entries
 void LLViewerRegion::addVisibleCacheEntry(LLVOCacheEntry* entry)
 {
-	if(mDead || !entry || !entry->getNumOfChildren())
+	if(mDead || !entry)
 	{
-		return; //no child entries
+		return; 
 	}
 
+	if(entry->isState(LLVOCacheEntry::IN_QUEUE))
+	{
+		return;
+	}
+
+	if(entry->isState(LLVOCacheEntry::INACTIVE))
+	{
+		entry->setState(LLVOCacheEntry::IN_QUEUE);
+	}
 	mImpl->mVisibleEntries.insert(entry);
 }
 
@@ -922,124 +937,148 @@ void LLViewerRegion::clearVisibleGroup(LLviewerOctreeGroup* group)
 
 	mImpl->mVisibleGroups.erase(group);
 }
-	
-//return time left
-F32 LLViewerRegion::addLinkedSetChildren(F32 max_time, S32& max_num_objects)
+
+F32 LLViewerRegion::updateVisibleEntries(F32 max_time)
 {
-	if(mImpl->mVisibleEntries.empty())
+	if(mImpl->mVisibleGroups.empty() && mImpl->mVisibleEntries.empty())
 	{
 		return max_time;
 	}
 
 	LLTimer update_timer;
-	bool timeout = false;
+
+	const LLVector3 camera_origin = LLViewerCamera::getInstance()->getOrigin();
+	const U32 cur_frame = LLViewerOctreeEntryData::getCurrentFrame();
+	bool needs_update = ((cur_frame - mImpl->mLastCameraUpdate) > 5) && ((camera_origin - mImpl->mLastCameraOrigin).lengthSquared() > 10.f);	
+
+	//process visible entries
+	max_time *= 0.5f; //only use up to half available time to update entries.
 
 	for(LLVOCacheEntry::vocache_entry_set_t::iterator iter = mImpl->mVisibleEntries.begin(); iter != mImpl->mVisibleEntries.end();)
 	{
-		LLVOCacheEntry* entry = *iter;				
-		LLVOCacheEntry* child = entry->getNextChild();
-		while(child != NULL)
+		LLVOCacheEntry* vo_entry = *iter;
+		vo_entry->calcSceneContribution(camera_origin, needs_update, mImpl->mLastCameraUpdate);
+
+		if(vo_entry->getState() < LLVOCacheEntry::WAITING && !vo_entry->isDummy())
+		{			
+			mImpl->mWaitingList.insert(vo_entry);
+		}
+
+		LLVOCacheEntry* child;
+		S32 num_child = vo_entry->getNumOfChildren();
+		S32 num_done = 0;
+		for(S32 i = 0; i < num_child; i++)
 		{
-			if(child->isState(LLVOCacheEntry::INACTIVE))
+			child = vo_entry->getChild(i);
+			if(child->getState() < LLVOCacheEntry::WAITING)
 			{
-				addNewObject(child);
-				
-				if(max_num_objects-- < 0 && update_timer.getElapsedTimeF32() > max_time)
-				{
-					timeout = true; //timeout
-					break;
-				}
+				child->setSceneContribution(vo_entry->getSceneContribution());
+				mImpl->mWaitingList.insert(child);
 			}
-			child = entry->getNextChild();
-		}
-		if(!child)
-		{
-			if(entry->isDummy())
+			else
 			{
-				mImpl->mDummyEntries.erase(entry);
+				num_done++;
 			}
 		}
-		
-		if(!timeout)
+		if(num_done == num_child)
 		{
-			iter = mImpl->mVisibleEntries.erase(iter);
+			vo_entry->clearChildrenList();
+		}
+
+		if(!vo_entry->getNumOfChildren())
+		{
+			if(vo_entry->isDummy())
+			{
+				mImpl->mDummyEntries.erase(vo_entry);
+				iter = mImpl->mVisibleEntries.erase(iter);
+			}
+			else if(vo_entry->getState() >= LLVOCacheEntry::WAITING)
+			{
+				iter = mImpl->mVisibleEntries.erase(iter);
+			}
+			else
+			{
+				++iter;
+			}
 		}
 		else
 		{
-			break; //timeout
+			++iter;
 		}
-	}
 
-	if(timeout)
-	{
-		return -1.f;
-	}
-	return max_time - update_timer.getElapsedTimeF32(); //time left
-}
-
-F32 LLViewerRegion::addVisibleObjects(F32 max_time, S32& max_num_objects)
-{
-	if(mImpl->mVisibleGroups.empty())
-	{
-		return max_time;
+		//if(update_timer.getElapsedTimeF32() > max_time)
+		//{
+		//	break;
+		//}
 	}
 
-	LLTimer update_timer;
-	bool timeout = false;
-
+	//process visible groups
 	std::set< LLviewerOctreeGroup* >::iterator group_iter = mImpl->mVisibleGroups.begin();
-	while(group_iter != mImpl->mVisibleGroups.end())
+	for(; group_iter != mImpl->mVisibleGroups.end(); ++group_iter)
 	{
 		LLviewerOctreeGroup* group = *group_iter;
 		if(!group->getOctreeNode() || group->isEmpty())
 		{
-			mImpl->mVisibleGroups.erase(group_iter);
-			group_iter = mImpl->mVisibleGroups.begin();
 			continue;
 		}
 
-		std::vector<LLViewerOctreeEntry*> entry_list;
 		for (LLviewerOctreeGroup::element_iter i = group->getDataBegin(); i != group->getDataEnd(); ++i)
 		{
-			//group data contents could change during creating new objects, so copy all contents first.
-			entry_list.push_back(*i);
-		}
-		
-		for(S32 i = 0; i < entry_list.size(); i++)
-		{
-			LLViewerOctreeEntry* entry = entry_list[i];
-			if(entry && entry->hasVOCacheEntry())
+			if((*i)->hasVOCacheEntry())
 			{
-				LLVOCacheEntry* vo_entry = (LLVOCacheEntry*)entry->getVOCacheEntry();
+				LLVOCacheEntry* vo_entry = (LLVOCacheEntry*)(*i)->getVOCacheEntry();
 				if(vo_entry->isDummy())
 				{
 					addVisibleCacheEntry(vo_entry); //for LLSpatialBridge.
+					continue;
 				}
-				else if(vo_entry->isState(LLVOCacheEntry::INACTIVE))
-				{
-					addNewObject(vo_entry);
-					if(max_num_objects-- < 0 && update_timer.getElapsedTimeF32() > max_time)
-					{
-						timeout = true;
-						break;
-					}
-				}
+
+				vo_entry->calcSceneContribution(camera_origin, needs_update, mImpl->mLastCameraUpdate);				
+				mImpl->mWaitingList.insert(vo_entry);
 			}
 		}
-		entry_list.clear();
 
-		if(timeout)
-		{
-			break;
-		}
-		mImpl->mVisibleGroups.erase(group);
-		group_iter = mImpl->mVisibleGroups.begin();
-	}	
+		//if(update_timer.getElapsedTimeF32() > max_time)
+		//{
+		//	break;
+		//}
+	}
+	mImpl->mVisibleGroups.clear();
+
+	if(needs_update)
+	{
+		mImpl->mLastCameraOrigin = camera_origin;
+		mImpl->mLastCameraUpdate = cur_frame;
+	}
+
+	return 2.0f * max_time - update_timer.getElapsedTimeF32();
+}
+
+F32 LLViewerRegion::createVisibleObjects(F32 max_time)
+{
+	if(mImpl->mWaitingList.empty())
+	{
+		return max_time;
+	}
 
-	if(timeout)
+	LLTimer update_timer;
+	S32 max_num_objects = 64; //minimum number of new objects to be added
+	for(LLVOCacheEntry::vocache_entry_priority_list_t::iterator iter = mImpl->mWaitingList.begin();
+		iter != mImpl->mWaitingList.end(); ++iter)
 	{
-		return -1.0f;
+		LLVOCacheEntry* vo_entry = *iter;
+			
+		if(vo_entry->getState() < LLVOCacheEntry::WAITING)
+		{
+			addNewObject(vo_entry);
+			if(max_num_objects-- < 0 && update_timer.getElapsedTimeF32() > max_time)
+			{
+				break;
+			}
+		}
 	}
+	mImpl->mWaitingList.clear();
+
 	return max_time - update_timer.getElapsedTimeF32();
 }
 
@@ -1057,7 +1096,7 @@ BOOL LLViewerRegion::idleUpdate(F32 max_update_time)
 	}
 
 	max_update_time -= update_timer.getElapsedTimeF32();
-	if(max_update_time < 0.f)
+	if(max_update_time < 0.f || mImpl->mCacheMap.empty())
 	{
 		return did_update;
 	}
@@ -1065,20 +1104,14 @@ BOOL LLViewerRegion::idleUpdate(F32 max_update_time)
 	sCurRegionp = this;
 
 	//kill invisible objects
-	max_update_time = killInvisibleObjects(max_update_time);
-
-	S32 new_object_count = 64; //minimum number of new objects to be added
+	max_update_time = killInvisibleObjects(max_update_time);	
 	
-	//add childrens of visible objects to the rendering pipeline
-	max_update_time = addLinkedSetChildren(max_update_time, new_object_count);
-
-	//add objects in the visible groups to the rendering pipeline
-	if(max_update_time > 0.f)
-	{
-		addVisibleObjects(max_update_time, new_object_count);
-	}
+	max_update_time = updateVisibleEntries(max_update_time);
+	createVisibleObjects(max_update_time);
 
 	mImpl->mVisibleGroups.clear();
+	mImpl->mWaitingList.clear();
+
 	sCurRegionp = NULL;
 	return did_update;
 }
@@ -1687,7 +1720,7 @@ LLVOCacheEntry* LLViewerRegion::getCacheEntry(U32 local_id)
 
 // Get data packer for this object, if we have cached data
 // AND the CRC matches. JC
-LLDataPacker *LLViewerRegion::getDP(U32 local_id, U32 crc, U8 &cache_miss_type)
+bool LLViewerRegion::probeCache(U32 local_id, U32 crc, U8 &cache_miss_type)
 {
 	//llassert(mCacheLoaded);  This assert failes often, changing to early-out -- davep, 2010/10/18
 
@@ -1702,7 +1735,51 @@ LLDataPacker *LLViewerRegion::getDP(U32 local_id, U32 crc, U8 &cache_miss_type)
 			entry->recordHit();
 			cache_miss_type = CACHE_MISS_TYPE_NONE;
 
-			return entry->getDP(crc);
+			if(entry->getGroup() || !entry->isState(LLVOCacheEntry::INACTIVE))
+			{
+				return true;
+			}
+
+			addVisibleCacheEntry(entry);
+#if 0
+			if(entry->isBridgeChild()) //bridge child
+			{
+				addVisibleCacheEntry(entry);
+			}
+			else
+			{
+				U32 parent_id = entry->getParentID();
+				if(parent_id > 0) //has parent
+				{
+					LLVOCacheEntry* parent = getCacheEntry(parent_id);
+				
+					if(parent) //parent cached
+					{
+						parent->addChild(entry);
+
+						if(parent->isState(LLVOCacheEntry::INACTIVE))
+						{
+							//addToVOCacheTree(parent);
+							addVisibleCacheEntry(parent);
+						}
+						else //parent visible
+						{
+							addVisibleCacheEntry(parent);
+						}
+					}
+					else //parent not cached. This should not happen, but just in case...
+					{
+						addVisibleCacheEntry(entry);
+					}
+				}
+				else //root node
+				{
+					//addToVOCacheTree(entry);
+					addVisibleCacheEntry(entry);
+				}
+			}
+#endif
+			return true;
 		}
 		else
 		{
@@ -1718,7 +1795,7 @@ LLDataPacker *LLViewerRegion::getDP(U32 local_id, U32 crc, U8 &cache_miss_type)
 		mCacheMissFull.put(local_id);
 	}
 
-	return NULL;
+	return false;
 }
 
 void LLViewerRegion::addCacheMissFull(const U32 local_id)
diff --git a/indra/newview/llviewerregion.h b/indra/newview/llviewerregion.h
index 86d3ee0d8c..9a47227f1c 100644
--- a/indra/newview/llviewerregion.h
+++ b/indra/newview/llviewerregion.h
@@ -317,7 +317,7 @@ public:
 	// handle a full update message
 	eCacheUpdateResult cacheFullUpdate(LLViewerObject* objectp, LLDataPackerBinaryBuffer &dp);	
 	LLVOCacheEntry* getCacheEntryForOctree(U32 local_id);
-	LLDataPacker *getDP(U32 local_id, U32 crc, U8 &cache_miss_type);
+	bool probeCache(U32 local_id, U32 crc, U8 &cache_miss_type);
 	void requestCacheMisses();
 	void addCacheMissFull(const U32 local_id);
 
@@ -354,8 +354,8 @@ private:
 	void killCacheEntry(LLVOCacheEntry* entry); //physically delete the cache entry	
 
 	F32 killInvisibleObjects(F32 max_time);
-	F32 addLinkedSetChildren(F32 max_time, S32& max_num_objects);
-	F32 addVisibleObjects(F32 max_time, S32& max_num_objects);
+	F32 createVisibleObjects(F32 max_time);
+	F32 updateVisibleEntries(F32 max_time); //update visible entries
 
 public:
 	struct CompareDistance
diff --git a/indra/newview/llvocache.cpp b/indra/newview/llvocache.cpp
index db6aa9cd00..ec8585852b 100644
--- a/indra/newview/llvocache.cpp
+++ b/indra/newview/llvocache.cpp
@@ -32,6 +32,7 @@
 #include "llviewerobjectlist.h"
 #include "lldrawable.h"
 #include "llviewerregion.h"
+#include "pipeline.h"
 
 BOOL check_read(LLAPRFile* apr_file, void* src, S32 n_bytes) 
 {
@@ -57,11 +58,24 @@ LLVOCacheEntry::LLVOCacheEntry(U32 local_id, U32 crc, LLDataPackerBinaryBuffer &
 	mCRCChangeCount(0),
 	mState(INACTIVE),
 	mRepeatedVisCounter(0),
-	mVisFrameRange(64)
+	mVisFrameRange(64),
+	mSceneContrib(0.f)
 {
 	mBuffer = new U8[dp.getBufferSize()];
 	mDP.assignBuffer(mBuffer, dp.getBufferSize());
 	mDP = dp;
+
+	if(dp.getBufferSize() > 0)
+	{
+		U32 parent_id = 0;
+		dp.reset();
+		dp.unpackU32(parent_id, "ParentID");
+		dp.reset();
+		if(parent_id > 0)
+		{
+			mState |= CHILD; //is a child
+		}
+	}
 }
 
 LLVOCacheEntry::LLVOCacheEntry()
@@ -74,7 +88,8 @@ LLVOCacheEntry::LLVOCacheEntry()
 	mBuffer(NULL),
 	mState(INACTIVE),
 	mRepeatedVisCounter(0),
-	mVisFrameRange(64)
+	mVisFrameRange(64),
+	mSceneContrib(0.f)
 {
 	mDP.assignBuffer(mBuffer, 0);
 }
@@ -84,7 +99,8 @@ LLVOCacheEntry::LLVOCacheEntry(LLAPRFile* apr_file)
 	mBuffer(NULL),
 	mState(INACTIVE),
 	mRepeatedVisCounter(0),
-	mVisFrameRange(64)
+	mVisFrameRange(64),
+	mSceneContrib(0.f)
 {
 	S32 size = -1;
 	BOOL success;
@@ -111,6 +127,10 @@ LLVOCacheEntry::LLVOCacheEntry(LLAPRFile* apr_file)
 	}
 	if(success)
 	{
+		success = check_read(apr_file, &mState, sizeof(U32));
+	}
+	if(success)
+	{
 		F32 ext[8];
 		success = check_read(apr_file, (void*)ext, sizeof(F32) * 8);
 
@@ -174,6 +194,7 @@ LLVOCacheEntry::LLVOCacheEntry(LLAPRFile* apr_file)
 		mCRCChangeCount = 0;
 		mBuffer = NULL;
 		mEntry = NULL;
+		mState = 0;
 	}
 }
 
@@ -203,11 +224,40 @@ void LLVOCacheEntry::setOctreeEntry(LLViewerOctreeEntry* entry)
 	LLViewerOctreeEntryData::setOctreeEntry(entry);
 }
 
+void LLVOCacheEntry::setBridgeChild()
+{
+	mState |= BRIDGE_CHILD;
+}
+	
+void LLVOCacheEntry::clearBridgeChild()
+{
+	mState &= ~BRIDGE_CHILD;
+}
+
+void LLVOCacheEntry::copy(LLVOCacheEntry* entry)
+{
+	//copy LLViewerOctreeEntry
+	LLViewerOctreeEntry* oct_entry = entry->getEntry();
+	if(!oct_entry)
+	{
+		setOctreeEntry(oct_entry);
+	}
+
+	//copy children
+	S32 num_children = entry->getNumOfChildren();
+	for(S32 i = 0; i < num_children; i++)
+	{
+		addChild(entry->getChild(i));
+	}
+}
+
 void LLVOCacheEntry::setState(U32 state)
 {
-	mState = state;
+	mState &= 0xffff0000; //clear the low 16 bits
+	state &= 0x0000ffff;  //clear the high 16 bits;
+	mState |= state;
 
-	if(mState == ACTIVE)
+	if(getState() == ACTIVE)
 	{
 		const S32 MIN_REAVTIVE_INTERVAL = 20;
 		U32 last_visible = getVisible();
@@ -247,37 +297,6 @@ void LLVOCacheEntry::addChild(LLVOCacheEntry* entry)
 	mChildrenList.push_back(entry);
 }
 	
-LLVOCacheEntry* LLVOCacheEntry::getNextChild()
-{
-	S32 size = mChildrenList.size();
-	if(!size)
-	{
-		return NULL;
-	}
-
-	LLVOCacheEntry* entry = mChildrenList[size - 1];
-	mChildrenList.pop_back(); //remove the entry;
-
-	return entry;
-}
-
-// New CRC means the object has changed.
-void LLVOCacheEntry::assignCRC(U32 crc, LLDataPackerBinaryBuffer &dp)
-{
-	if (  (mCRC != crc)
-		||(mDP.getBufferSize() == 0))
-	{
-		mCRC = crc;
-		mHitCount = 0;
-		mCRCChangeCount++;
-
-		mDP.freeBuffer();
-		mBuffer = new U8[dp.getBufferSize()];
-		mDP.assignBuffer(mBuffer, dp.getBufferSize());
-		mDP = dp;
-	}
-}
-
 LLDataPackerBinaryBuffer *LLVOCacheEntry::getDP(U32 crc)
 {
 	if (  (mCRC != crc)
@@ -344,6 +363,11 @@ BOOL LLVOCacheEntry::writeToFile(LLAPRFile* apr_file) const
 	}
 	if(success)
 	{
+		U32 state = mState & 0xffff0000; //only store the high 16 bits.
+		success = check_write(apr_file, (void*)&state, sizeof(U32));
+	}
+	if(success)
+	{
 		const LLVector4a* exts = getSpatialExtents() ;
 		LLVector4 ext(exts[0][0], exts[0][1], exts[0][2], exts[0][3]);
 		success = check_write(apr_file, ext.mV, sizeof(LLVector4));		
@@ -378,6 +402,46 @@ BOOL LLVOCacheEntry::writeToFile(LLAPRFile* apr_file) const
 	return success ;
 }
 
+void LLVOCacheEntry::calcSceneContribution(const LLVector3& camera_origin, bool needs_update, U32 last_update)
+{
+	if(!needs_update && getVisible() >= last_update)
+	{
+		return; //no need to update
+	}
+
+	const LLVector4a& center = getPositionGroup();
+	
+	LLVector4a origin;
+	origin.load3(camera_origin.mV);
+
+	LLVector4a lookAt;
+	lookAt.setSub(center, origin);
+	F32 squared_dist = lookAt.dot3(lookAt).getF32();
+
+	F32 rad = getBinRadius();
+	mSceneContrib = rad * rad / squared_dist;
+
+	setVisible();
+}
+
+U32 LLVOCacheEntry::getParentID()
+{
+	if(!(mState & CHILD))
+	{
+		return 0; //not a child
+	}
+
+	U32 parent_id = 0;
+	LLDataPackerBinaryBuffer* dp = getDP();
+	if(dp)
+	{
+		dp->reset();
+		dp->unpackU32(parent_id, "ParentID");
+		dp->reset();
+	}
+	return parent_id;
+}
+
 //-------------------------------------------------------------------
 //LLVOCachePartition
 //-------------------------------------------------------------------
diff --git a/indra/newview/llvocache.h b/indra/newview/llvocache.h
index 675c12a3eb..ded29dd990 100644
--- a/indra/newview/llvocache.h
+++ b/indra/newview/llvocache.h
@@ -36,17 +36,47 @@
 //---------------------------------------------------------------------------
 // Cache entries
 class LLVOCacheEntry;
+class LLCamera;
 
 class LLVOCacheEntry : public LLViewerOctreeEntryData
 {
 public:
 	enum
 	{
-		INACTIVE = 0,
-		WAITING,
-		ACTIVE
+		INACTIVE = 0x00000000,     //not visible
+		IN_QUEUE = 0x00000001,     //in visible queue, object to be created
+		WAITING  = 0x00000002,     //object creation request sent
+		ACTIVE   = 0x00000004      //object created, and in rendering pipeline.
 	};
 
+	enum
+	{
+		CHILD        = 0x00010000, //has parent
+		BRIDGE_CHILD = 0x00020000  //is a child of a spatial bridge.
+	};
+
+	struct CompareVOCacheEntry
+	{
+		bool operator()(const LLVOCacheEntry* const& lhs, const LLVOCacheEntry* const& rhs)
+		{
+			F32 lpa = lhs->getSceneContribution();
+			F32 rpa = rhs->getSceneContribution();
+
+			//larger pixel area first
+			if(lpa > rpa)		
+			{
+				return true;
+			}
+			else if(lpa < rpa)
+			{
+				return false;
+			}
+			else
+			{
+				return lhs < rhs;
+			}			
+		}
+	};
 protected:
 	~LLVOCacheEntry();
 public:
@@ -55,33 +85,45 @@ public:
 	LLVOCacheEntry();	
 
 	void setState(U32 state);
-	bool isState(U32 state)  {return mState == state;}
-	U32  getState() const    {return mState;}
+	bool isState(U32 state)   {return (mState & 0xffff) == state;}
+	U32  getState() const     {return (mState & 0xffff);}
+	U32  getFullState() const {return mState;}
+
+	void setBridgeChild();  
+	void clearBridgeChild(); 
+	bool isBridgeChild()     {return mState & BRIDGE_CHILD;}
 
 	U32 getLocalID() const			{ return mLocalID; }
 	U32 getCRC() const				{ return mCRC; }
 	S32 getHitCount() const			{ return mHitCount; }
 	S32 getCRCChangeCount() const	{ return mCRCChangeCount; }
-	S32 getMinVisFrameRange()const;
+	S32 getMinVisFrameRange()const;	
+	U32 getParentID();
+
+	void calcSceneContribution(const LLVector3& camera_origin, bool needs_update, U32 last_update);
+	void setSceneContribution(F32 scene_contrib) {mSceneContrib = scene_contrib;}
+	F32 getSceneContribution() const             { return mSceneContrib;}
 
 	void dump() const;
 	BOOL writeToFile(LLAPRFile* apr_file) const;
-	void assignCRC(U32 crc, LLDataPackerBinaryBuffer &dp);
 	LLDataPackerBinaryBuffer *getDP(U32 crc);
 	LLDataPackerBinaryBuffer *getDP();
 	void recordHit();
 	void recordDupe() { mDupeCount++; }
 	
+	void copy(LLVOCacheEntry* entry); //copy variables 
 	/*virtual*/ void setOctreeEntry(LLViewerOctreeEntry* entry);
 
 	void addChild(LLVOCacheEntry* entry);
-	LLVOCacheEntry* getNextChild();
-	S32 getNumOfChildren() {return mChildrenList.size();}
-	bool isDummy() {return !mBuffer;}
+	LLVOCacheEntry* getChild(S32 i) {return mChildrenList[i];}
+	S32  getNumOfChildren()         {return mChildrenList.size();}
+	void clearChildrenList()        {mChildrenList.clear();}
+	bool isDummy()                  {return !mBuffer;}	
 
 public:
-	typedef std::map<U32, LLPointer<LLVOCacheEntry> >	vocache_entry_map_t;
-	typedef std::set<LLVOCacheEntry*>                   vocache_entry_set_t;
+	typedef std::map<U32, LLPointer<LLVOCacheEntry> >	   vocache_entry_map_t;
+	typedef std::set<LLVOCacheEntry*>                      vocache_entry_set_t;
+	typedef std::set<LLVOCacheEntry*, CompareVOCacheEntry> vocache_entry_priority_list_t;	
 
 protected:
 	U32							mLocalID;
@@ -92,9 +134,10 @@ protected:
 	LLDataPackerBinaryBuffer	mDP;
 	U8							*mBuffer;
 
+	F32                         mSceneContrib; //projected scene contributuion of this object.
 	S32                         mVisFrameRange;
 	S32                         mRepeatedVisCounter; //number of repeatedly visible within a short time.
-	U32                         mState;
+	U32                         mState; //high 16 bits reserved for special use.
 	std::vector<LLVOCacheEntry*> mChildrenList; //children entries in a linked set.
 };