path: root/indra/newview/llvotree.cpp

/** 
 * @file llvotree.cpp
 * @brief LLVOTree class implementation
 *
 * $LicenseInfo:firstyear=2002&license=viewerlgpl$
 * Second Life Viewer Source Code
 * Copyright (C) 2010, Linden Research, Inc.
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation;
 * version 2.1 of the License only.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 * 
 * Linden Research, Inc., 945 Battery Street, San Francisco, CA  94111  USA
 * $/LicenseInfo$
 */

#include "llviewerprecompiledheaders.h"

#include "llvotree.h"

#include "lldrawpooltree.h"

#include "llviewercontrol.h"
#include "lldir.h"
#include "llprimitive.h"
#include "lltree_common.h"
#include "llxmltree.h"
#include "material_codes.h"
#include "object_flags.h"

#include "llagentcamera.h"
#include "lldrawable.h"
#include "llface.h"
#include "llviewercamera.h"
#include "llviewertexturelist.h"
#include "llviewerobjectlist.h"
#include "llviewerregion.h"
#include "llvolumemgr.h"
#include "llvovolume.h"
#include "llworld.h"
#include "noise.h"
#include "pipeline.h"
#include "llspatialpartition.h"
#include "llnotificationsutil.h"
#include "raytrace.h"
#include "llglslshader.h"

extern LLPipeline gPipeline;

const S32 MAX_SLICES = 32;
const F32 LEAF_LEFT = 0.52f;
const F32 LEAF_RIGHT = 0.98f;
const F32 LEAF_TOP = 1.0f;
const F32 LEAF_BOTTOM = 0.52f;
const F32 LEAF_WIDTH = 1.f;

const S32 LLVOTree::sMAX_NUM_TREE_LOD_LEVELS = 4 ;

S32 LLVOTree::sLODVertexOffset[sMAX_NUM_TREE_LOD_LEVELS];
S32 LLVOTree::sLODVertexCount[sMAX_NUM_TREE_LOD_LEVELS];
S32 LLVOTree::sLODIndexOffset[sMAX_NUM_TREE_LOD_LEVELS];
S32 LLVOTree::sLODIndexCount[sMAX_NUM_TREE_LOD_LEVELS];
S32 LLVOTree::sLODSlices[sMAX_NUM_TREE_LOD_LEVELS] = {10, 5, 4, 3};
F32 LLVOTree::sLODAngles[sMAX_NUM_TREE_LOD_LEVELS] = {30.f, 20.f, 15.f, F_ALMOST_ZERO};

F32 LLVOTree::sTreeFactor = 1.f;

LLVOTree::SpeciesMap LLVOTree::sSpeciesTable;
S32 LLVOTree::sMaxTreeSpecies = 0;

// Tree variables and functions

LLVOTree::LLVOTree(const LLUUID &id, const LLPCode pcode, LLViewerRegion *regionp):
						LLViewerObject(id, pcode, regionp)
{
	mSpecies = 0;
	mFrameCount = 0;
	mWind = mRegionp->mWind.getVelocity(getPositionRegion());
	mTrunkLOD = 0;

	// if assert triggers, idleUpdate() needs to be revised and adjusted to new LOD levels
	llassert(sMAX_NUM_TREE_LOD_LEVELS == LLVolumeLODGroup::NUM_LODS);
}


LLVOTree::~LLVOTree()
{
	if (mData)
	{
		delete[] mData;
		mData = NULL;
	}
}

//static
bool LLVOTree::isTreeRenderingStopped()
{
	return LLVOTree::sTreeFactor < LLVOTree::sLODAngles[sMAX_NUM_TREE_LOD_LEVELS - 1] ;
}

// static
void LLVOTree::initClass()
{
	std::string xml_filename = gDirUtilp->getExpandedFilename(LL_PATH_APP_SETTINGS,"trees.xml");
	
	LLXmlTree tree_def_tree;

	if (!tree_def_tree.parseFile(xml_filename))
	{
		LL_ERRS() << "Failed to parse tree file." << LL_ENDL;
	}

	LLXmlTreeNode* rootp = tree_def_tree.getRoot();

	for (LLXmlTreeNode* tree_def = rootp->getFirstChild();
		tree_def;
		tree_def = rootp->getNextChild())
		{
			if (!tree_def->hasName("tree"))
			{
				LL_WARNS() << "Invalid tree definition node " << tree_def->getName() << LL_ENDL;
				continue;
			}
			F32 F32_val;
			LLUUID id;
			S32 S32_val;

			bool success{ true };
			S32 species;
			static LLStdStringHandle species_id_string = LLXmlTree::addAttributeString("species_id");
			if (!tree_def->getFastAttributeS32(species_id_string, species))
			{
				LL_WARNS() << "No species id defined" << LL_ENDL;
				continue;
			}

			if (species < 0)
			{
				LL_WARNS() << "Invalid species id " << species << LL_ENDL;
				continue;
			}

			if (sSpeciesTable.count(species))
			{
				LL_WARNS() << "Tree species " << species << " already defined! Duplicate discarded." << LL_ENDL;
				continue;
			}

			TreeSpeciesData* newTree = new TreeSpeciesData();

			static LLStdStringHandle texture_id_string = LLXmlTree::addAttributeString("texture_id");
			success &= tree_def->getFastAttributeUUID(texture_id_string, id);
			newTree->mTextureID = id;
			
			static LLStdStringHandle droop_string = LLXmlTree::addAttributeString("droop");
			success &= tree_def->getFastAttributeF32(droop_string, F32_val);
			newTree->mDroop = F32_val;

			static LLStdStringHandle twist_string = LLXmlTree::addAttributeString("twist");
			success &= tree_def->getFastAttributeF32(twist_string, F32_val);
			newTree->mTwist = F32_val;
			
			static LLStdStringHandle branches_string = LLXmlTree::addAttributeString("branches");
			success &= tree_def->getFastAttributeF32(branches_string, F32_val);
			newTree->mBranches = F32_val;

			static LLStdStringHandle depth_string = LLXmlTree::addAttributeString("depth");
			success &= tree_def->getFastAttributeS32(depth_string, S32_val);
			newTree->mDepth = S32_val;

			static LLStdStringHandle scale_step_string = LLXmlTree::addAttributeString("scale_step");
			success &= tree_def->getFastAttributeF32(scale_step_string, F32_val);
			newTree->mScaleStep = F32_val;
			
			static LLStdStringHandle trunk_depth_string = LLXmlTree::addAttributeString("trunk_depth");
			success &= tree_def->getFastAttributeS32(trunk_depth_string, S32_val);
			newTree->mTrunkDepth = S32_val;
			
			static LLStdStringHandle branch_length_string = LLXmlTree::addAttributeString("branch_length");
			success &= tree_def->getFastAttributeF32(branch_length_string, F32_val);
			newTree->mBranchLength = F32_val;

			static LLStdStringHandle trunk_length_string = LLXmlTree::addAttributeString("trunk_length");
			success &= tree_def->getFastAttributeF32(trunk_length_string, F32_val);
			newTree->mTrunkLength = F32_val;

			static LLStdStringHandle leaf_scale_string = LLXmlTree::addAttributeString("leaf_scale");
			success &= tree_def->getFastAttributeF32(leaf_scale_string, F32_val);
			newTree->mLeafScale = F32_val;
			
			static LLStdStringHandle billboard_scale_string = LLXmlTree::addAttributeString("billboard_scale");
			success &= tree_def->getFastAttributeF32(billboard_scale_string, F32_val);
			newTree->mBillboardScale = F32_val;
			
			static LLStdStringHandle billboard_ratio_string = LLXmlTree::addAttributeString("billboard_ratio");
			success &= tree_def->getFastAttributeF32(billboard_ratio_string, F32_val);
			newTree->mBillboardRatio = F32_val;
			
			static LLStdStringHandle trunk_aspect_string = LLXmlTree::addAttributeString("trunk_aspect");
			success &= tree_def->getFastAttributeF32(trunk_aspect_string, F32_val);
			newTree->mTrunkAspect = F32_val;

			static LLStdStringHandle branch_aspect_string = LLXmlTree::addAttributeString("branch_aspect");
			success &= tree_def->getFastAttributeF32(branch_aspect_string, F32_val);
			newTree->mBranchAspect = F32_val;

			static LLStdStringHandle leaf_rotate_string = LLXmlTree::addAttributeString("leaf_rotate");
			success &= tree_def->getFastAttributeF32(leaf_rotate_string, F32_val);
			newTree->mRandomLeafRotate = F32_val;
			
			static LLStdStringHandle noise_mag_string = LLXmlTree::addAttributeString("noise_mag");
			success &= tree_def->getFastAttributeF32(noise_mag_string, F32_val);
			newTree->mNoiseMag = F32_val;

			static LLStdStringHandle noise_scale_string = LLXmlTree::addAttributeString("noise_scale");
			success &= tree_def->getFastAttributeF32(noise_scale_string, F32_val);
			newTree->mNoiseScale = F32_val;

			static LLStdStringHandle taper_string = LLXmlTree::addAttributeString("taper");
			success &= tree_def->getFastAttributeF32(taper_string, F32_val);
			newTree->mTaper = F32_val;

			static LLStdStringHandle repeat_z_string = LLXmlTree::addAttributeString("repeat_z");
			success &= tree_def->getFastAttributeF32(repeat_z_string, F32_val);
			newTree->mRepeatTrunkZ = F32_val;

			sSpeciesTable[species] = newTree;

			if (species >= sMaxTreeSpecies) sMaxTreeSpecies = species + 1;

			if (!success)
			{
				std::string name;
				static LLStdStringHandle name_string = LLXmlTree::addAttributeString("name");
				tree_def->getFastAttributeString(name_string, name);
				LL_WARNS() << "Incomplete definition of tree " << name << LL_ENDL;
			}
		}
		
		bool have_all_trees {true};
		std::string err;

		for (S32 i=0;i<sMaxTreeSpecies;++i)
		{
			if (!sSpeciesTable.count(i))
			{
				err.append(llformat(" %d",i));
				have_all_trees = false;
			}
		}

		if (!have_all_trees) 
		{
			LLSD args;
			args["SPECIES"] = err;
			LLNotificationsUtil::add("ErrorUndefinedTrees", args);
		}
};

//static
void LLVOTree::cleanupClass()
{
	std::for_each(sSpeciesTable.begin(), sSpeciesTable.end(), DeletePairedPointer());
	sSpeciesTable.clear();
}

U32 LLVOTree::processUpdateMessage(LLMessageSystem *mesgsys,
										  void **user_data,
										  U32 block_num, EObjectUpdateType update_type,
										  LLDataPacker *dp)
{
	// Do base class updates...
	U32 retval = LLViewerObject::processUpdateMessage(mesgsys, user_data, block_num, update_type, dp);

	if (  (getVelocity().lengthSquared() > 0.f)
		||(getAcceleration().lengthSquared() > 0.f)
		||(getAngularVelocity().lengthSquared() > 0.f))
	{
		LL_INFOS() << "ACK! Moving tree!" << LL_ENDL;
		setVelocity(LLVector3::zero);
		setAcceleration(LLVector3::zero);
		setAngularVelocity(LLVector3::zero);
	}

	if (update_type == OUT_TERSE_IMPROVED)
	{
		// Nothing else needs to be done for the terse message.
		return retval;
	}

	// 
	//  Load Instance-Specific data 
	//
	if (mData)
	{
		mSpecies = ((U8 *)mData)[0];
	}
	
	if (!sSpeciesTable.count(mSpecies))
	{
		if (sSpeciesTable.size())
		{
			SpeciesMap::const_iterator it = sSpeciesTable.begin();
			mSpecies = (*it).first;
		}
	}

	//
	//  Load Species-Specific data 
	//
	static const S32 MAX_TREE_TEXTURE_VIRTURE_SIZE_RESET_INTERVAL = 32 ; //frames.
	mTreeImagep = LLViewerTextureManager::getFetchedTexture(sSpeciesTable[mSpecies]->mTextureID, FTT_DEFAULT, true, LLGLTexture::BOOST_NONE, LLViewerTexture::LOD_TEXTURE);
	mTreeImagep->setMaxVirtualSizeResetInterval(MAX_TREE_TEXTURE_VIRTURE_SIZE_RESET_INTERVAL); //allow to wait for at most 16 frames to reset virtual size.

	mBranchLength = sSpeciesTable[mSpecies]->mBranchLength;
	mTrunkLength = sSpeciesTable[mSpecies]->mTrunkLength;
	mLeafScale = sSpeciesTable[mSpecies]->mLeafScale;
	mDroop = sSpeciesTable[mSpecies]->mDroop;
	mTwist = sSpeciesTable[mSpecies]->mTwist;
	mBranches = sSpeciesTable[mSpecies]->mBranches;
	mDepth = sSpeciesTable[mSpecies]->mDepth;
	mScaleStep = sSpeciesTable[mSpecies]->mScaleStep;
	mTrunkDepth = sSpeciesTable[mSpecies]->mTrunkDepth;
	mBillboardScale = sSpeciesTable[mSpecies]->mBillboardScale;
	mBillboardRatio = sSpeciesTable[mSpecies]->mBillboardRatio;
	mTrunkAspect = sSpeciesTable[mSpecies]->mTrunkAspect;
	mBranchAspect = sSpeciesTable[mSpecies]->mBranchAspect;
	
	// position change not caused by us, etc.  make sure to rebuild.
	gPipeline.markRebuild(mDrawable, LLDrawable::REBUILD_ALL);

	return retval;
}

void LLVOTree::idleUpdate(LLAgent &agent, const F64 &time)
{
 	if (mDead || !(gPipeline.hasRenderType(LLPipeline::RENDER_TYPE_TREE)))
	{
		return;
	}
	
	S32 trunk_LOD = sMAX_NUM_TREE_LOD_LEVELS ; // disabled
	F32 app_angle = getAppAngle()*LLVOTree::sTreeFactor;
	F32 distance = mDrawable->mDistanceWRTCamera * LLVOVolume::sDistanceFactor * (F_PI / 3.f);
	F32 diameter = getScale().length(); // trees have very broken scale, but length rougtly outlines proper diameter
	F32 sz = mBillboardScale * mBillboardRatio * diameter;

	for (S32 j = 0; j < sMAX_NUM_TREE_LOD_LEVELS; j++)
	{
		if (app_angle > LLVOTree::sLODAngles[j])
		{
			trunk_LOD = j;
			break;
		}
	}

    F32 tan_angle = (LLVOTree::sTreeFactor * 64 * sz) / distance;
    S32 cur_detail = LLVolumeLODGroup::getDetailFromTan(ll_round(tan_angle, 0.01f)); // larger value, better quality

    // for trunk_LOD lower value means better quality, but both trunk_LOD and cur_detail have 4 levels
    trunk_LOD = llmax(trunk_LOD, LLVolumeLODGroup::NUM_LODS - cur_detail - 1);
    trunk_LOD = llmin(trunk_LOD, sMAX_NUM_TREE_LOD_LEVELS);

	if (mReferenceBuffer.isNull())
	{
		gPipeline.markRebuild(mDrawable, LLDrawable::REBUILD_ALL);
	}
	else if (trunk_LOD != mTrunkLOD)
	{
		gPipeline.markRebuild(mDrawable, LLDrawable::REBUILD_ALL);
	}
	else
	{
		// we're not animating but we may *still* need to
		// regenerate the mesh if we moved, since position
		// and rotation are baked into the mesh.
		// *TODO: I don't know what's so special about trees
		// that they don't get REBUILD_POSITION automatically
		// at a higher level.
		const LLVector3 &this_position = getPositionRegion();
		if (this_position != mLastPosition)
		{
			gPipeline.markRebuild(mDrawable, LLDrawable::REBUILD_POSITION);
			mLastPosition = this_position;
		}
		else
		{
			const LLQuaternion &this_rotation = getRotation();
			
			if (this_rotation != mLastRotation)
			{
				gPipeline.markRebuild(mDrawable, LLDrawable::REBUILD_POSITION);
				mLastRotation = this_rotation;
			}
		}
	}

	mTrunkLOD = trunk_LOD;
}

void LLVOTree::render(LLAgent &agent)
{
}


void LLVOTree::setPixelAreaAndAngle(LLAgent &agent)
{
	LLVector3 center = getPositionAgent();//center of tree.
	LLVector3 viewer_pos_agent = gAgentCamera.getCameraPositionAgent();
	LLVector3 lookAt = center - viewer_pos_agent;
	F32 dist = lookAt.normVec() ;	
	F32 cos_angle_to_view_dir = lookAt * LLViewerCamera::getInstance()->getXAxis() ;	
	F32 radius = getScale().length()*0.5f;
	F32 range = dist - radius;

	if (range < F_ALMOST_ZERO || isHUDAttachment())		// range == zero
	{
		mAppAngle = 180.f;
	}
	else
	{
		mAppAngle = (F32) atan2( getMaxScale(), range) * RAD_TO_DEG;		
	}

	F32 max_scale = mBillboardScale * getMaxScale();
	F32 area = max_scale * (max_scale*mBillboardRatio);
	// Compute pixels per meter at the given range
	F32 pixels_per_meter = LLViewerCamera::getInstance()->getViewHeightInPixels() / (tan(LLViewerCamera::getInstance()->getView()) * dist);
	mPixelArea = pixels_per_meter * pixels_per_meter * area ;	

	F32 importance = LLFace::calcImportanceToCamera(cos_angle_to_view_dir, dist) ;
	mPixelArea = LLFace::adjustPixelArea(importance, mPixelArea) ;
	if (mPixelArea > LLViewerCamera::getInstance()->getScreenPixelArea())
	{
		mAppAngle = 180.f;
	}

#if 0
	// mAppAngle is a bit of voodoo;
	// use the one calculated LLViewerObject::setPixelAreaAndAngle above
	// to avoid LOD miscalculations
	mAppAngle = (F32) atan2( max_scale, range) * RAD_TO_DEG;
#endif
}

void LLVOTree::updateTextures()
{
	if (mTreeImagep)
	{
		if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_TEXTURE_AREA))
		{
			setDebugText(llformat("%4.0f", (F32) sqrt(mPixelArea)));
		}
		mTreeImagep->addTextureStats(mPixelArea);
	}

}


LLDrawable* LLVOTree::createDrawable(LLPipeline *pipeline)
{
	pipeline->allocDrawable(this);
	mDrawable->setLit(false);

	mDrawable->setRenderType(LLPipeline::RENDER_TYPE_TREE);

	LLDrawPoolTree *poolp = (LLDrawPoolTree*) gPipeline.getPool(LLDrawPool::POOL_TREE, mTreeImagep);

	// Just a placeholder for an actual object...
	LLFace *facep = mDrawable->addFace(poolp, mTreeImagep);
	facep->setSize(1, 3);

	updateRadius();

	return mDrawable;
}


// Yes, I know this is bad.  I'll clean this up soon. - djs 04/02/02
const S32 LEAF_INDICES = 24;
const S32 LEAF_VERTICES = 16;

bool LLVOTree::updateGeometry(LLDrawable *drawable)
{
    LL_PROFILE_ZONE_SCOPED;

	if(mTrunkLOD >= sMAX_NUM_TREE_LOD_LEVELS) //do not display the tree.
	{
		mReferenceBuffer = NULL ;
		LLFace * facep = drawable->getFace(0);
		if (facep)
		{
			facep->setVertexBuffer(NULL);
		}
		return true ;
	}

	if (mDrawable->getFace(0) &&
		(mReferenceBuffer.isNull() || !mDrawable->getFace(0)->getVertexBuffer()))
	{
		const F32 SRR3 = 0.577350269f; // sqrt(1/3)
		const F32 SRR2 = 0.707106781f; // sqrt(1/2)
		U32 i, j;

		U32 slices = MAX_SLICES;

		S32 max_indices = LEAF_INDICES;
		S32 max_vertices = LEAF_VERTICES;
		S32 lod;

		LLFace *face = drawable->getFace(0);
		if (!face) return true;

		face->mCenterAgent = getPositionAgent();
		face->mCenterLocal = face->mCenterAgent;

		for (lod = 0; lod < sMAX_NUM_TREE_LOD_LEVELS; lod++)
		{
			slices = sLODSlices[lod];
			sLODVertexOffset[lod] = max_vertices;
			sLODVertexCount[lod] = slices*slices;
			sLODIndexOffset[lod] = max_indices;
			sLODIndexCount[lod] = (slices-1)*(slices-1)*6;
			max_indices += sLODIndexCount[lod];
			max_vertices += sLODVertexCount[lod];
		}

		mReferenceBuffer = new LLVertexBuffer(LLDrawPoolTree::VERTEX_DATA_MASK);
		if (!mReferenceBuffer->allocateBuffer(max_vertices, max_indices))
		{
			LL_WARNS() << "Failed to allocate Vertex Buffer on update to "
				<< max_vertices << " vertices and "
				<< max_indices << " indices" << LL_ENDL;
			mReferenceBuffer = NULL; //unref
			return true;
		}

		LLStrider<LLVector3> vertices;
		LLStrider<LLVector3> normals;
        LLStrider<LLColor4U> colors;
		LLStrider<LLVector2> tex_coords;
		LLStrider<U16> indicesp;

		mReferenceBuffer->getVertexStrider(vertices);
		mReferenceBuffer->getNormalStrider(normals);
		mReferenceBuffer->getTexCoord0Strider(tex_coords);
        mReferenceBuffer->getColorStrider(colors);
		mReferenceBuffer->getIndexStrider(indicesp);
				
		S32 vertex_count = 0;
		S32 index_count = 0;
		
		// First leaf
		*(normals++) =		LLVector3(-SRR2, -SRR2, 0.f);
		*(tex_coords++) =	LLVector2(LEAF_LEFT, LEAF_BOTTOM);
		*(vertices++) =		LLVector3(-0.5f*LEAF_WIDTH, 0.f, 0.f);
        *(colors++) =       LLColor4U::white;
		vertex_count++;

		*(normals++) =		LLVector3(SRR3, -SRR3, SRR3);
		*(tex_coords++) =	LLVector2(LEAF_RIGHT, LEAF_TOP);
		*(vertices++) =		LLVector3(0.5f*LEAF_WIDTH, 0.f, 1.f);
        *(colors++) =       LLColor4U::white;
		vertex_count++;

		*(normals++) =		LLVector3(-SRR3, -SRR3, SRR3);
		*(tex_coords++) =	LLVector2(LEAF_LEFT, LEAF_TOP);
		*(vertices++) =		LLVector3(-0.5f*LEAF_WIDTH, 0.f, 1.f);
        *(colors++) =       LLColor4U::white;
		vertex_count++;

		*(normals++) =		LLVector3(SRR2, -SRR2, 0.f);
		*(tex_coords++) =	LLVector2(LEAF_RIGHT, LEAF_BOTTOM);
		*(vertices++) =		LLVector3(0.5f*LEAF_WIDTH, 0.f, 0.f);
        *(colors++) =       LLColor4U::white;
		vertex_count++;
        
		*(indicesp++) = 0;
		index_count++;
		*(indicesp++) = 1;
		index_count++;
		*(indicesp++) = 2;
		index_count++;

		*(indicesp++) = 0;
		index_count++;
		*(indicesp++) = 3;
		index_count++;
		*(indicesp++) = 1;
		index_count++;

		// Same leaf, inverse winding/normals
		*(normals++) =		LLVector3(-SRR2, SRR2, 0.f);
		*(tex_coords++) =	LLVector2(LEAF_LEFT, LEAF_BOTTOM);
		*(vertices++) =		LLVector3(-0.5f*LEAF_WIDTH, 0.f, 0.f);
        *(colors++) =       LLColor4U::white;
		vertex_count++;

		*(normals++) =		LLVector3(SRR3, SRR3, SRR3);
		*(tex_coords++) =	LLVector2(LEAF_RIGHT, LEAF_TOP);
		*(vertices++) =		LLVector3(0.5f*LEAF_WIDTH, 0.f, 1.f);
        *(colors++) =       LLColor4U::white;
		vertex_count++;

		*(normals++) =		LLVector3(-SRR3, SRR3, SRR3);
		*(tex_coords++) =	LLVector2(LEAF_LEFT, LEAF_TOP);
		*(vertices++) =		LLVector3(-0.5f*LEAF_WIDTH, 0.f, 1.f);
        *(colors++) =       LLColor4U::white;
		vertex_count++;

		*(normals++) =		LLVector3(SRR2, SRR2, 0.f);
		*(tex_coords++) =	LLVector2(LEAF_RIGHT, LEAF_BOTTOM);
		*(vertices++) =		LLVector3(0.5f*LEAF_WIDTH, 0.f, 0.f);
        *(colors++) =       LLColor4U::white;
		vertex_count++;

		*(indicesp++) = 4;
		index_count++;
		*(indicesp++) = 6;
		index_count++;
		*(indicesp++) = 5;
		index_count++;

		*(indicesp++) = 4;
		index_count++;
		*(indicesp++) = 5;
		index_count++;
		*(indicesp++) = 7;
		index_count++;


		// next leaf
		*(normals++) =		LLVector3(SRR2, -SRR2, 0.f);
		*(tex_coords++) =	LLVector2(LEAF_LEFT, LEAF_BOTTOM);
		*(vertices++) =		LLVector3(0.f, -0.5f*LEAF_WIDTH, 0.f);
        *(colors++) =       LLColor4U::white;
		vertex_count++;

		*(normals++) =		LLVector3(SRR3, SRR3, SRR3);
		*(tex_coords++) =	LLVector2(LEAF_RIGHT, LEAF_TOP);
		*(vertices++) =		LLVector3(0.f, 0.5f*LEAF_WIDTH, 1.f);
        *(colors++) =       LLColor4U::white;
		vertex_count++;

		*(normals++) =		LLVector3(SRR3, -SRR3, SRR3);
		*(tex_coords++) =	LLVector2(LEAF_LEFT, LEAF_TOP);
		*(vertices++) =		LLVector3(0.f, -0.5f*LEAF_WIDTH, 1.f);
        *(colors++) =       LLColor4U::white;
		vertex_count++;

		*(normals++) =		LLVector3(SRR2, SRR2, 0.f);
		*(tex_coords++) =	LLVector2(LEAF_RIGHT, LEAF_BOTTOM);
		*(vertices++) =		LLVector3(0.f, 0.5f*LEAF_WIDTH, 0.f);
        *(colors++) =       LLColor4U::white;
		vertex_count++;

		*(indicesp++) = 8;
		index_count++;
		*(indicesp++) = 9;
		index_count++;
		*(indicesp++) = 10;
		index_count++;

		*(indicesp++) = 8;
		index_count++;
		*(indicesp++) = 11;
		index_count++;
		*(indicesp++) = 9;
		index_count++;


		// other side of same leaf
		*(normals++) =		LLVector3(-SRR2, -SRR2, 0.f);
		*(tex_coords++) =	LLVector2(LEAF_LEFT, LEAF_BOTTOM);
		*(vertices++) =		LLVector3(0.f, -0.5f*LEAF_WIDTH, 0.f);
        *(colors++) =       LLColor4U::white;
		vertex_count++;

		*(normals++) =		LLVector3(-SRR3, SRR3, SRR3);
		*(tex_coords++) =	LLVector2(LEAF_RIGHT, LEAF_TOP);
		*(vertices++) =		LLVector3(0.f, 0.5f*LEAF_WIDTH, 1.f);
        *(colors++) =       LLColor4U::white;
		vertex_count++;

		*(normals++) =		LLVector3(-SRR3, -SRR3, SRR3);
		*(tex_coords++) =	LLVector2(LEAF_LEFT, LEAF_TOP);
		*(vertices++) =		LLVector3(0.f, -0.5f*LEAF_WIDTH, 1.f);
        *(colors++) =       LLColor4U::white;
		vertex_count++;

		*(normals++) =		LLVector3(-SRR2, SRR2, 0.f);
		*(tex_coords++) =	LLVector2(LEAF_RIGHT, LEAF_BOTTOM);
		*(vertices++) =		LLVector3(0.f, 0.5f*LEAF_WIDTH, 0.f);
        *(colors++) =       LLColor4U::white;
		vertex_count++;

		*(indicesp++) = 12;
		index_count++;
		*(indicesp++) = 14;
		index_count++;
		*(indicesp++) = 13;
		index_count++;

		*(indicesp++) = 12;
		index_count++;
		*(indicesp++) = 13;
		index_count++;
		*(indicesp++) = 15;
		index_count++;

		// Generate geometry for the cylinders

		// Different LOD's

		// Generate the vertices
		// Generate the indices

		for (lod = 0; lod < sMAX_NUM_TREE_LOD_LEVELS; lod++)
		{
			slices = sLODSlices[lod];
			F32 base_radius = 0.65f;
			F32 top_radius = base_radius * sSpeciesTable[mSpecies]->mTaper;
			//LL_INFOS() << "Species " << ((U32) mSpecies) << ", taper = " << sSpeciesTable[mSpecies].mTaper << LL_ENDL;
			//LL_INFOS() << "Droop " << mDroop << ", branchlength: " << mBranchLength << LL_ENDL;
			F32 angle = 0;
			F32 angle_inc = 360.f/(slices-1);
			F32 z = 0.f;
			F32 z_inc = 1.f;
			if (slices > 3)
			{
				z_inc = 1.f/(slices - 3);
			}
			F32 radius = base_radius;

			F32 x1,y1;
			F32 noise_scale = sSpeciesTable[mSpecies]->mNoiseMag;
			LLVector3 nvec;

			const F32 cap_nudge = 0.1f;			// Height to 'peak' the caps on top/bottom of branch

			const S32 fractal_depth = 5;
			F32 nvec_scale = 1.f * sSpeciesTable[mSpecies]->mNoiseScale;
			F32 nvec_scalez = 4.f * sSpeciesTable[mSpecies]->mNoiseScale;

			F32 tex_z_repeat = sSpeciesTable[mSpecies]->mRepeatTrunkZ;

			F32 start_radius;
			F32 nangle = 0;
			F32 height = 1.f;
			F32 r0;

			for (i = 0; i < slices; i++)
			{
				if (i == 0) 
				{
					z = - cap_nudge;
					r0 = 0.0;
				}
				else if (i == (slices - 1))
				{
					z = 1.f + cap_nudge;//((i - 2) * z_inc) + cap_nudge;
					r0 = 0.0;
				}
				else  
				{
					z = (i - 1) * z_inc;
					r0 = base_radius + (top_radius - base_radius)*z;
				}

				for (j = 0; j < slices; j++)
				{
					if (slices - 1 == j)
					{
						angle = 0.f;
					}
					else
					{
						angle =  j*angle_inc;
					}
				
					nangle = angle;
					
					x1 = cos(angle * DEG_TO_RAD);
					y1 = sin(angle * DEG_TO_RAD);
					LLVector2 tc;
					// This isn't totally accurate.  Should compute based on slope as well.
					start_radius = r0 * (1.f + 1.2f*fabs(z - 0.66f*height)/height);
					nvec.set(	cos(nangle * DEG_TO_RAD)*start_radius*nvec_scale, 
								sin(nangle * DEG_TO_RAD)*start_radius*nvec_scale, 
								z*nvec_scalez); 
					// First and last slice at 0 radius (to bring in top/bottom of structure)
					radius = start_radius + turbulence3((F32*)&nvec.mV, (F32)fractal_depth)*noise_scale;

					if (slices - 1 == j)
					{
						// Not 0.5 for slight slop factor to avoid edges on leaves
						tc = LLVector2(0.490f, (1.f - z/2.f)*tex_z_repeat);
					}
					else
					{
						tc = LLVector2((angle/360.f)*0.5f, (1.f - z/2.f)*tex_z_repeat);
					}

					*(vertices++) =		LLVector3(x1*radius, y1*radius, z);
					*(normals++) =		LLVector3(x1, y1, 0.f);
					*(tex_coords++) = tc;
                    *(colors++) =       LLColor4U::white;
					vertex_count++;
				}
			}

			for (i = 0; i < (slices - 1); i++)
			{
				for (j = 0; j < (slices - 1); j++)
				{
					S32 x1_offset = j+1;
					if ((j+1) == slices)
					{
						x1_offset = 0;
					}
					// Generate the matching quads
					*(indicesp) = j + (i*slices) + sLODVertexOffset[lod];
					llassert(*(indicesp) < (U32)max_vertices);
					indicesp++;
					index_count++;
					*(indicesp) = x1_offset + ((i+1)*slices) + sLODVertexOffset[lod];
					llassert(*(indicesp) < (U32)max_vertices);
					indicesp++;
					index_count++;
					*(indicesp) = j + ((i+1)*slices) + sLODVertexOffset[lod];
					llassert(*(indicesp) < (U32)max_vertices);
					indicesp++;
					index_count++;

					*(indicesp) = j + (i*slices) + sLODVertexOffset[lod];
					llassert(*(indicesp) < (U32)max_vertices);
					indicesp++;
					index_count++;
					*(indicesp) = x1_offset + (i*slices) + sLODVertexOffset[lod];
					llassert(*(indicesp) < (U32)max_vertices);
					indicesp++;
					index_count++;
					*(indicesp) = x1_offset + ((i+1)*slices) + sLODVertexOffset[lod];
					llassert(*(indicesp) < (U32)max_vertices);
					indicesp++;
					index_count++;
				}
			}
			slices /= 2; 
		}

		mReferenceBuffer->unmapBuffer();
		llassert(vertex_count == max_vertices);
		llassert(index_count == max_indices);
#ifndef SHOW_ASSERT
        (void)vertex_count;
        (void)index_count;
#endif
	}

	//generate tree mesh
	updateMesh();
	
	return true;
}

void LLVOTree::updateMesh()
{
	LLMatrix4 matrix;
	
	// Translate to tree base  HACK - adjustment in Z plants tree underground
	const LLVector3 &pos_region = getPositionRegion();
	//gGL.translatef(pos_agent.mV[VX], pos_agent.mV[VY], pos_agent.mV[VZ] - 0.1f);
	LLMatrix4 trans_mat;
	trans_mat.setTranslation(pos_region.mV[VX], pos_region.mV[VY], pos_region.mV[VZ] - 0.1f);
	trans_mat *= matrix;
	
	// Rotate to tree position and bend for current trunk/wind
	// Note that trunk stiffness controls the amount of bend at the trunk as 
	// opposed to the crown of the tree
	// 
	const F32 TRUNK_STIFF = 22.f;
	
	LLQuaternion rot = 
		LLQuaternion(mTrunkBend.magVec()*TRUNK_STIFF*DEG_TO_RAD, LLVector4(mTrunkBend.mV[VX], mTrunkBend.mV[VY], 0)) *
		LLQuaternion(90.f*DEG_TO_RAD, LLVector4(0,0,1)) *
		getRotation();

	LLMatrix4 rot_mat(rot);
	rot_mat *= trans_mat;

	F32 radius = getScale().magVec()*0.05f;
	LLMatrix4 scale_mat;
	scale_mat.mMatrix[0][0] = 
		scale_mat.mMatrix[1][1] =
		scale_mat.mMatrix[2][2] = radius;

	scale_mat *= rot_mat;

//	const F32 THRESH_ANGLE_FOR_BILLBOARD = 15.f;
//	const F32 BLEND_RANGE_FOR_BILLBOARD = 3.f;

	F32 droop = mDroop + 25.f*(1.f - mTrunkBend.magVec());
	
	S32 stop_depth = 0;
	F32 alpha = 1.0;
	
	U32 vert_count = 0;
	U32 index_count = 0;
	
	calcNumVerts(vert_count, index_count, mTrunkLOD, stop_depth, mDepth, mTrunkDepth, mBranches);

	LLFace* facep = mDrawable->getFace(0);
	if (!facep) return;
	LLVertexBuffer* buff = new LLVertexBuffer(LLDrawPoolTree::VERTEX_DATA_MASK);
	if (!buff->allocateBuffer(vert_count, index_count))
	{
		LL_WARNS() << "Failed to allocate Vertex Buffer on mesh update to "
			<< vert_count << " vertices and "
			<< index_count << " indices" << LL_ENDL;
		buff->allocateBuffer(1, 3);
		memset((U8*)buff->getMappedData(), 0, buff->getSize());
		memset((U8*)buff->getMappedIndices(), 0, buff->getIndicesSize());
		facep->setSize(1, 3);
		facep->setVertexBuffer(buff);
		mReferenceBuffer->unmapBuffer();
		buff->unmapBuffer();
		return;
	}

	facep->setVertexBuffer(buff);
	
	LLStrider<LLVector3> vertices;
	LLStrider<LLVector3> normals;
	LLStrider<LLVector2> tex_coords;
    LLStrider<LLColor4U> colors;
	LLStrider<U16> indices;
	U16 idx_offset = 0;

	buff->getVertexStrider(vertices);
	buff->getNormalStrider(normals);
	buff->getTexCoord0Strider(tex_coords);
    buff->getColorStrider(colors);
	buff->getIndexStrider(indices);

	genBranchPipeline(vertices, normals, tex_coords, colors, indices, idx_offset, scale_mat, mTrunkLOD, stop_depth, mDepth, mTrunkDepth, 1.0, mTwist, droop, mBranches, alpha);
	
	mReferenceBuffer->unmapBuffer();
	buff->unmapBuffer();
}

void LLVOTree::appendMesh(LLStrider<LLVector3>& vertices, 
						 LLStrider<LLVector3>& normals, 
						 LLStrider<LLVector2>& tex_coords, 
                         LLStrider<LLColor4U>& colors, 
						 LLStrider<U16>& indices,
						 U16& cur_idx,
						 LLMatrix4& matrix,
						 LLMatrix4& norm_mat,
						 S32 vert_start,
						 S32 vert_count,
						 S32 index_count,
						 S32 index_offset)
{
	LLStrider<LLVector3> v;
	LLStrider<LLVector3> n;
	LLStrider<LLVector2> t;
    LLStrider<LLColor4U> c;
	LLStrider<U16> idx;

	mReferenceBuffer->getVertexStrider(v);
	mReferenceBuffer->getNormalStrider(n);
	mReferenceBuffer->getTexCoord0Strider(t);
    mReferenceBuffer->getColorStrider(c);
	mReferenceBuffer->getIndexStrider(idx);
	
	//copy/transform vertices into mesh - check
	for (S32 i = 0; i < vert_count; i++)
	{ 
		U16 index = vert_start + i;
		*vertices++ = v[index] * matrix;
		LLVector3 norm = n[index] * norm_mat;
		norm.normalize();
		*normals++ = norm;
		*tex_coords++ = t[index];
        *colors++ = c[index];
	}

	//copy offset indices into mesh - check
	for (S32 i = 0; i < index_count; i++)
	{
		U16 index = index_offset + i;
		*indices++ = idx[index]-vert_start+cur_idx;
	}

	//increment index offset - check
	cur_idx += vert_count;
}
								 

void LLVOTree::genBranchPipeline(LLStrider<LLVector3>& vertices, 
								 LLStrider<LLVector3>& normals, 
								 LLStrider<LLVector2>& tex_coords, 
                                 LLStrider<LLColor4U>& colors,
								 LLStrider<U16>& indices,
								 U16& index_offset,
								 LLMatrix4& matrix, 
								 S32 trunk_LOD, 
								 S32 stop_level, 
								 U16 depth, 
								 U16 trunk_depth,  
								 F32 scale, 
								 F32 twist, 
								 F32 droop,  
								 F32 branches, 
								 F32 alpha)
{
	//
	//  Generates a tree mesh by recursing, generating branches and then a 'leaf' texture.
	
	static F32 constant_twist;
	static F32 width = 0;

	F32 length = ((trunk_depth || (scale == 1.f))? mTrunkLength:mBranchLength);
	F32 aspect = ((trunk_depth || (scale == 1.f))? mTrunkAspect:mBranchAspect);
	
	constant_twist = 360.f/branches;

	if (stop_level >= 0)
	{
		if (depth > stop_level)
		{
			{
				llassert(sLODIndexCount[trunk_LOD] > 0);
				width = scale * length * aspect;
				LLMatrix4 scale_mat;
				scale_mat.mMatrix[0][0] = width;
				scale_mat.mMatrix[1][1] = width;
				scale_mat.mMatrix[2][2] = scale*length;
				scale_mat *= matrix;

				glh::matrix4f norm((F32*) scale_mat.mMatrix);
				LLMatrix4 norm_mat = LLMatrix4(norm.inverse().transpose().m);

				norm_mat.invert();
				appendMesh(vertices, normals, tex_coords, colors, indices, index_offset, scale_mat, norm_mat, 
							sLODVertexOffset[trunk_LOD], sLODVertexCount[trunk_LOD], sLODIndexCount[trunk_LOD], sLODIndexOffset[trunk_LOD]);
			}
			
			// Recurse to create more branches
			for (S32 i=0; i < (S32)branches; i++) 
			{
				LLMatrix4 trans_mat;
				trans_mat.setTranslation(0,0,scale*length);
				trans_mat *= matrix;

				LLQuaternion rot = 
					LLQuaternion(20.f*DEG_TO_RAD, LLVector4(0.f, 0.f, 1.f)) *
					LLQuaternion(droop*DEG_TO_RAD, LLVector4(0.f, 1.f, 0.f)) *
					LLQuaternion(((constant_twist + ((i%2==0)?twist:-twist))*i)*DEG_TO_RAD, LLVector4(0.f, 0.f, 1.f));
				
				LLMatrix4 rot_mat(rot);
				rot_mat *= trans_mat;

				genBranchPipeline(vertices, normals, tex_coords, colors, indices, index_offset, rot_mat, trunk_LOD, stop_level, depth - 1, 0, scale*mScaleStep, twist, droop, branches, alpha);
			}
			//  Recurse to continue trunk
			if (trunk_depth)
			{
				LLMatrix4 trans_mat;
				trans_mat.setTranslation(0,0,scale*length);
				trans_mat *= matrix;

				LLMatrix4 rot_mat(70.5f*DEG_TO_RAD, LLVector4(0,0,1));
				rot_mat *= trans_mat; // rotate a bit around Z when ascending 
				genBranchPipeline(vertices, normals, tex_coords, colors, indices, index_offset, rot_mat, trunk_LOD, stop_level, depth, trunk_depth-1, scale*mScaleStep, twist, droop, branches, alpha);
			}
		}
		else
		{
			//
			//  Append leaves as two 90 deg crossed quads with leaf textures
			//
			{
				LLMatrix4 scale_mat;
				scale_mat.mMatrix[0][0] = 
					scale_mat.mMatrix[1][1] =
					scale_mat.mMatrix[2][2] = scale*mLeafScale;

				scale_mat *= matrix;

				glh::matrix4f norm((F32*) scale_mat.mMatrix);
				LLMatrix4 norm_mat = LLMatrix4(norm.inverse().transpose().m);

				appendMesh(vertices, normals, tex_coords, colors, indices, index_offset, scale_mat, norm_mat, 0, LEAF_VERTICES, LEAF_INDICES, 0);	
			}
		}
	}
}



void LLVOTree::calcNumVerts(U32& vert_count, U32& index_count, S32 trunk_LOD, S32 stop_level, U16 depth, U16 trunk_depth, F32 branches)
{
	if (stop_level >= 0)
	{
		if (depth > stop_level)
		{
			index_count += sLODIndexCount[trunk_LOD];
			vert_count += sLODVertexCount[trunk_LOD];

			// Recurse to create more branches
			for (S32 i=0; i < (S32)branches; i++) 
			{
				calcNumVerts(vert_count, index_count, trunk_LOD, stop_level, depth - 1, 0, branches);
			}
			
			//  Recurse to continue trunk
			if (trunk_depth)
			{
				calcNumVerts(vert_count, index_count, trunk_LOD, stop_level, depth, trunk_depth-1, branches);
			}
		}
		else
		{
			index_count += LEAF_INDICES;
			vert_count += LEAF_VERTICES;
		}
	}
	else
	{
		index_count += LEAF_INDICES;
		vert_count += LEAF_VERTICES;
	}
}

void LLVOTree::updateRadius()
{
	if (mDrawable.isNull())
	{
		return;
	}
		
	mDrawable->setRadius(32.0f);
}

void LLVOTree::updateSpatialExtents(LLVector4a& newMin, LLVector4a& newMax)
{
	F32 radius = getScale().length()*0.05f;
	LLVector3 center = getRenderPosition();

	F32 sz = mBillboardScale*mBillboardRatio*radius*0.5f; 
	LLVector3 size(sz,sz,sz);

	center += LLVector3(0, 0, size.mV[2]) * getRotation();
	
	newMin.load3((center-size).mV);
	newMax.load3((center+size).mV);
	LLVector4a pos;
	pos.load3(center.mV);
	mDrawable->setPositionGroup(pos);
}

bool LLVOTree::lineSegmentIntersect(const LLVector4a& start, const LLVector4a& end, S32 face, bool pick_transparent, bool pick_rigged, bool pick_unselectable, S32 *face_hitp,
									  LLVector4a* intersection,LLVector2* tex_coord, LLVector4a* normal, LLVector4a* tangent)
	
{

	if (!lineSegmentBoundingBox(start, end))
	{
		return false;
	}

	const LLVector4a* exta = mDrawable->getSpatialExtents();

	//VECTORIZE THIS
	LLVector3 ext[2];
	ext[0].set(exta[0].getF32ptr());
	ext[1].set(exta[1].getF32ptr());
	
	LLVector3 center = (ext[1]+ext[0])*0.5f;
	LLVector3 size = (ext[1]-ext[0]);

	LLQuaternion quat = getRotation();

	center -= LLVector3(0,0,size.magVec() * 0.25f)*quat;

	size.scaleVec(LLVector3(0.25f, 0.25f, 1.f));
	size.mV[0] = llmin(size.mV[0], 1.f);
	size.mV[1] = llmin(size.mV[1], 1.f);

	LLVector3 pos, norm;
		
	LLVector3 start3(start.getF32ptr());
	LLVector3 end3(end.getF32ptr());

	if (linesegment_tetrahedron(start3, end3, center, size, quat, pos, norm))
	{
		if (intersection)
		{
			intersection->load3(pos.mV);
		}

		if (normal)
		{
			normal->load3(norm.mV);
		}
		return true;
	}
	
	return false;
}

U32 LLVOTree::getPartitionType() const
{ 
	return LLViewerRegion::PARTITION_TREE; 
}

LLTreePartition::LLTreePartition(LLViewerRegion* regionp)
: LLSpatialPartition(0, false, regionp)
{
	mDrawableType = LLPipeline::RENDER_TYPE_TREE;
	mPartitionType = LLViewerRegion::PARTITION_TREE;
	mSlopRatio = 0.f;
	mLODPeriod = 1;
}