/**
 * @file llspatialpartition.cpp
 * @brief LLSpatialGroup class implementation and supporting functions
 *
 * $LicenseInfo:firstyear=2003&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 "llspatialpartition.h"

#include "llappviewer.h"
#include "llcallstack.h"
#include "lltexturecache.h"
#include "lltexturefetch.h"
#include "llimageworker.h"
#include "llviewerwindow.h"
#include "llviewerobjectlist.h"
#include "llvovolume.h"
#include "llvolume.h"
#include "llvolumeoctree.h"
#include "llviewercamera.h"
#include "llface.h"
#include "llfloatertools.h"
#include "llviewercontrol.h"
#include "llviewerregion.h"
#include "llcamera.h"
#include "pipeline.h"
#include "llmeshrepository.h"
#include "llrender.h"
#include "lldrawpool.h"
#include "lloctree.h"
#include "llphysicsshapebuilderutil.h"
#include "llvoavatar.h"
#include "llvolumemgr.h"
#include "llviewershadermgr.h"
#include "llcontrolavatar.h"

extern bool gShiftFrame;

static U32 sZombieGroups = 0;
U32 LLSpatialGroup::sNodeCount = 0;

bool LLSpatialGroup::sNoDelete = false;

static F32 sLastMaxTexPriority = 1.f;
static F32 sCurMaxTexPriority = 1.f;

// enable expensive sanity checks around redundant drawable and group insertion to LLCullResult
#define LL_DEBUG_CULL_RESULT 0

//static counter for frame to switch LOD on

void sg_assert(bool expr)
{
#if LL_OCTREE_PARANOIA_CHECK
    if (!expr)
    {
        LL_ERRS() << "Octree invalid!" << LL_ENDL;
    }
#endif
}

//returns:
//  0 if sphere and AABB are not intersecting
//  1 if they are
//  2 if AABB is entirely inside sphere

S32 LLSphereAABB(const LLVector3& center, const LLVector3& size, const LLVector3& pos, const F32 &rad)
{
    S32 ret = 2;

    LLVector3 min = center - size;
    LLVector3 max = center + size;
    for (U32 i = 0; i < 3; i++)
    {
        if (min.mV[i] > pos.mV[i] + rad ||
            max.mV[i] < pos.mV[i] - rad)
        {   //totally outside
            return 0;
        }

        if (min.mV[i] < pos.mV[i] - rad ||
            max.mV[i] > pos.mV[i] + rad)
        {   //intersecting
            ret = 1;
        }
    }

    return ret;
}

LLSpatialGroup::~LLSpatialGroup()
{
    /*if (sNoDelete)
    {
        LL_ERRS() << "Illegal deletion of LLSpatialGroup!" << LL_ENDL;
    }*/

    if (gDebugGL)
    {
        gPipeline.checkReferences(this);
    }

    if (hasState(DEAD))
    {
        sZombieGroups--;
    }

    sNodeCount--;

    clearDrawMap();
}

void LLSpatialGroup::clearDrawMap()
{
    mDrawMap.clear();
}

bool LLSpatialGroup::isHUDGroup()
{
    return getSpatialPartition() && getSpatialPartition()->isHUDPartition() ;
}

void LLSpatialGroup::validate()
{
    ll_assert_aligned(this,64);
#if LL_OCTREE_PARANOIA_CHECK

    sg_assert(!isState(DIRTY));
    sg_assert(!isDead());

    LLVector4a myMin;
    myMin.setSub(mBounds[0], mBounds[1]);
    LLVector4a myMax;
    myMax.setAdd(mBounds[0], mBounds[1]);

    validateDrawMap();

    for (element_iter i = getDataBegin(); i != getDataEnd(); ++i)
    {
        LLDrawable* drawable = *i;
        sg_assert(drawable->getSpatialGroup() == this);
        if (drawable->getSpatialBridge())
        {
            sg_assert(drawable->getSpatialBridge() == getSpatialPartition()->asBridge());
        }

        /*if (drawable->isSpatialBridge())
        {
            LLSpatialPartition* part = drawable->asPartition();
            if (!part)
            {
                LL_ERRS() << "Drawable reports it is a spatial bridge but not a partition." << LL_ENDL;
            }
            LLSpatialGroup* group = (LLSpatialGroup*) part->mOctree->getListener(0);
            group->validate();
        }*/
    }

    for (U32 i = 0; i < mOctreeNode->getChildCount(); ++i)
    {
        LLSpatialGroup* group = (LLSpatialGroup*) mOctreeNode->getChild(i)->getListener(0);

        group->validate();

        //ensure all children are enclosed in this node
        LLVector4a center = group->mBounds[0];
        LLVector4a size = group->mBounds[1];

        LLVector4a min;
        min.setSub(center, size);
        LLVector4a max;
        max.setAdd(center, size);

        for (U32 j = 0; j < 3; j++)
        {
            sg_assert(min[j] >= myMin[j]-0.02f);
            sg_assert(max[j] <= myMax[j]+0.02f);
        }
    }

#endif
}

void LLSpatialGroup::validateDrawMap()
{
#if LL_OCTREE_PARANOIA_CHECK
    for (draw_map_t::iterator i = mDrawMap.begin(); i != mDrawMap.end(); ++i)
    {
        LLSpatialGroup::drawmap_elem_t& draw_vec = i->second;
        for (drawmap_elem_t::iterator j = draw_vec.begin(); j != draw_vec.end(); ++j)
        {
            LLDrawInfo& params = **j;

            params.validate();
        }
    }
#endif
}

bool LLSpatialGroup::updateInGroup(LLDrawable *drawablep, bool immediate)
{
    LL_PROFILE_ZONE_SCOPED;
    drawablep->updateSpatialExtents();

    OctreeNode* parent = mOctreeNode->getOctParent();

    if (mOctreeNode->isInside(drawablep->getPositionGroup()) &&
        (mOctreeNode->contains(drawablep->getEntry()) ||
         (drawablep->getBinRadius() > mOctreeNode->getSize()[0] &&
                parent && parent->getElementCount() >= gOctreeMaxCapacity)))
    {
        unbound();
        setState(OBJECT_DIRTY);
        //setState(GEOM_DIRTY);
        return true;
    }

    return false;
}

void LLSpatialGroup::expandExtents(const LLVector4a* addingExtents, const LLXformMatrix& currentTransform)
{
    // Get coordinates of the adding extents
    const LLVector4a& min = addingExtents[0];
    const LLVector4a& max = addingExtents[1];

    // Get coordinates of all corners of the bounding box
    LLVector3 corners[] =
    {
        LLVector3(min[0], min[1], min[2]),
        LLVector3(min[0], min[1], max[2]),
        LLVector3(min[0], max[1], min[2]),
        LLVector3(min[0], max[1], max[2]),
        LLVector3(max[0], min[1], min[2]),
        LLVector3(max[0], min[1], max[2]),
        LLVector3(max[0], max[1], min[2]),
        LLVector3(max[0], max[1], max[2])
    };

    // New extents (to be expanded)
    LLVector3 extents[] =
    {
        LLVector3(mExtents[0].getF32ptr()),
        LLVector3(mExtents[1].getF32ptr())
    };

    LLQuaternion backwardRotation = ~currentTransform.getWorldRotation();
    for (LLVector3& corner : corners)
    {
        // Make coordinates relative to the current position
        corner -= currentTransform.getWorldPosition();
        // Rotate coordinates backward to the current rotation
        corner.rotVec(backwardRotation);
        // Expand root extents on the current corner
        for (int j = 0; j < 3; ++j)
        {
            if (corner[j] < extents[0][j])
                extents[0][j] = corner[j];
            if (corner[j] > extents[1][j])
                extents[1][j] = corner[j];
        }
    }

    // Set new expanded extents
    mExtents[0].load3(extents[0].mV);
    mExtents[1].load3(extents[1].mV);

    // Calculate new center and size
    mBounds[0].setAdd(mExtents[0], mExtents[1]);
    mBounds[0].mul(0.5f);
    mBounds[1].setSub(mExtents[0], mExtents[1]);
    mBounds[1].mul(0.5f);
}

bool LLSpatialGroup::addObject(LLDrawable *drawablep)
{
    if(!drawablep)
    {
        return false;
    }
    {
        drawablep->setGroup(this);
        setState(OBJECT_DIRTY | GEOM_DIRTY);
        setOcclusionState(LLSpatialGroup::DISCARD_QUERY, LLSpatialGroup::STATE_MODE_ALL_CAMERAS);
        gPipeline.markRebuild(this);
        if (drawablep->isSpatialBridge())
        {
            mBridgeList.push_back((LLSpatialBridge*) drawablep);
        }
        if (drawablep->getRadius() > 1.f)
        {
            setState(IMAGE_DIRTY);
        }
    }

    return true;
}

void LLSpatialGroup::rebuildGeom()
{
    if (!isDead())
    {
        getSpatialPartition()->rebuildGeom(this);

        if (hasState(LLSpatialGroup::MESH_DIRTY))
        {
            gPipeline.markMeshDirty(this);
        }
    }
}

void LLSpatialGroup::rebuildMesh()
{
    if (!isDead())
    {
        getSpatialPartition()->rebuildMesh(this);
    }
}

void LLSpatialPartition::rebuildGeom(LLSpatialGroup* group)
{
    if (group->isDead() || !group->hasState(LLSpatialGroup::GEOM_DIRTY))
    {
        return;
    }

    if (group->changeLOD())
    {
        group->mLastUpdateDistance = group->mDistance;
        group->mLastUpdateViewAngle = group->mViewAngle;
    }

    LL_PROFILE_ZONE_SCOPED_CATEGORY_SPATIAL;

    group->clearDrawMap();

    //get geometry count
    U32 index_count = 0;
    U32 vertex_count = 0;

    addGeometryCount(group, vertex_count, index_count);

    if (vertex_count > 0 && index_count > 0)
    { //create vertex buffer containing volume geometry for this node
        {
            group->mBuilt = 1.f;
            if (group->mVertexBuffer.isNull() ||
                group->mVertexBuffer->getNumVerts() != vertex_count ||
                group->mVertexBuffer->getNumVerts() != index_count)
            {
                group->mVertexBuffer = new LLVertexBuffer(mVertexDataMask);
                if (!group->mVertexBuffer->allocateBuffer(vertex_count, index_count))
                {
                    LL_WARNS() << "Failed to allocate Vertex Buffer on rebuild to "
                        << vertex_count << " vertices and "
                        << index_count << " indices" << LL_ENDL;
                    group->mVertexBuffer = NULL;
                    group->mBufferMap.clear();
                }
            }
        }

        if (group->mVertexBuffer)
        {
            getGeometry(group);
        }
    }
    else
    {
        group->mVertexBuffer = NULL;
        group->mBufferMap.clear();
    }

    group->mLastUpdateTime = gFrameTimeSeconds;
    group->clearState(LLSpatialGroup::GEOM_DIRTY);
}


void LLSpatialPartition::rebuildMesh(LLSpatialGroup* group)
{

}

LLSpatialGroup* LLSpatialGroup::getParent()
{
    return (LLSpatialGroup*)LLViewerOctreeGroup::getParent();
    }

bool LLSpatialGroup::removeObject(LLDrawable *drawablep, bool from_octree)
{
    LL_PROFILE_ZONE_SCOPED_CATEGORY_SPATIAL

    if(!drawablep)
    {
        return false;
    }

    unbound();
    if (mOctreeNode && !from_octree)
    {
        drawablep->setGroup(NULL);
    }
    else
    {
        drawablep->setGroup(NULL);
        setState(GEOM_DIRTY);
        gPipeline.markRebuild(this);

        if (drawablep->isSpatialBridge())
        {
            for (bridge_list_t::iterator i = mBridgeList.begin(); i != mBridgeList.end(); ++i)
            {
                if (*i == drawablep)
                {
                    mBridgeList.erase(i);
                    break;
                }
            }
        }

        if (getElementCount() == 0)
        { //delete draw map on last element removal since a rebuild might never happen
            clearDrawMap();
        }
    }
    return true;
}

void LLSpatialGroup::shift(const LLVector4a &offset)
{
    LLVector4a t = mOctreeNode->getCenter();
    t.add(offset);
    mOctreeNode->setCenter(t);
    mOctreeNode->updateMinMax();
    mBounds[0].add(offset);
    mExtents[0].add(offset);
    mExtents[1].add(offset);
    mObjectBounds[0].add(offset);
    mObjectExtents[0].add(offset);
    mObjectExtents[1].add(offset);

    if (!getSpatialPartition()->mRenderByGroup &&
        getSpatialPartition()->mPartitionType != LLViewerRegion::PARTITION_TREE &&
        getSpatialPartition()->mPartitionType != LLViewerRegion::PARTITION_TERRAIN &&
        getSpatialPartition()->mPartitionType != LLViewerRegion::PARTITION_BRIDGE &&
        getSpatialPartition()->mPartitionType != LLViewerRegion::PARTITION_AVATAR &&
        getSpatialPartition()->mPartitionType != LLViewerRegion::PARTITION_CONTROL_AV)
    {
        setState(GEOM_DIRTY);
        gPipeline.markRebuild(this);
    }
}

class LLSpatialSetState : public OctreeTraveler
{
public:
    U32 mState;
    LLSpatialSetState(U32 state) : mState(state) { }
    virtual void visit(const OctreeNode* branch) { ((LLSpatialGroup*) branch->getListener(0))->setState(mState); }
};

class LLSpatialSetStateDiff : public LLSpatialSetState
{
public:
    LLSpatialSetStateDiff(U32 state) : LLSpatialSetState(state) { }

    virtual void traverse(const OctreeNode* n)
    {
        LLSpatialGroup* group = (LLSpatialGroup*) n->getListener(0);

        if (!group->hasState(mState))
        {
            OctreeTraveler::traverse(n);
        }
    }
};

void LLSpatialGroup::setState(U32 state, S32 mode)
{
    LL_PROFILE_ZONE_SCOPED_CATEGORY_SPATIAL

    llassert(state <= LLSpatialGroup::STATE_MASK);

    if (mode > STATE_MODE_SINGLE)
    {
        if (mode == STATE_MODE_DIFF)
        {
            LLSpatialSetStateDiff setter(state);
            setter.traverse(mOctreeNode);
        }
        else
        {
            LLSpatialSetState setter(state);
            setter.traverse(mOctreeNode);
        }
    }
    else
    {
        mState |= state;
    }
}

class LLSpatialClearState : public OctreeTraveler
{
public:
    U32 mState;
    LLSpatialClearState(U32 state) : mState(state) { }
    virtual void visit(const OctreeNode* branch) { ((LLSpatialGroup*) branch->getListener(0))->clearState(mState); }
};

class LLSpatialClearStateDiff : public LLSpatialClearState
{
public:
    LLSpatialClearStateDiff(U32 state) : LLSpatialClearState(state) { }

    virtual void traverse(const OctreeNode* n)
    {
        LLSpatialGroup* group = (LLSpatialGroup*) n->getListener(0);

        if (group->hasState(mState))
        {
            OctreeTraveler::traverse(n);
        }
    }
};

void LLSpatialGroup::clearState(U32 state, S32 mode)
{
    LL_PROFILE_ZONE_SCOPED_CATEGORY_SPATIAL

    llassert(state <= LLSpatialGroup::STATE_MASK);

    if (mode > STATE_MODE_SINGLE)
    {
        if (mode == STATE_MODE_DIFF)
        {
            LLSpatialClearStateDiff clearer(state);
            clearer.traverse(mOctreeNode);
        }
        else
        {
            LLSpatialClearState clearer(state);
            clearer.traverse(mOctreeNode);
        }
    }
    else
    {
        mState &= ~state;
    }
}

//======================================
//      Octree Listener Implementation
//======================================

LLSpatialGroup::LLSpatialGroup(OctreeNode* node, LLSpatialPartition* part) : LLOcclusionCullingGroup(node, part),
    mObjectBoxSize(1.f),
    mGeometryBytes(0),
    mSurfaceArea(0.f),
    mBuilt(0.f),
    mVertexBuffer(NULL),
    mDistance(0.f),
    mDepth(0.f),
    mLastUpdateDistance(-1.f),
    mLastUpdateTime(gFrameTimeSeconds)
{
    ll_assert_aligned(this,16);

    sNodeCount++;

    mViewAngle.splat(0.f);
    mLastUpdateViewAngle.splat(-1.f);

    sg_assert(mOctreeNode->getListenerCount() == 0);
    setState(SG_INITIAL_STATE_MASK);
    gPipeline.markRebuild(this);

    // let the reflection map manager know about this spatial group
    mReflectionProbe = gPipeline.mReflectionMapManager.registerSpatialGroup(this);

    mRadius = 1;
    mPixelArea = 1024.f;
}

void LLSpatialGroup::updateDistance(LLCamera &camera)
{
    if (LLViewerCamera::sCurCameraID != LLViewerCamera::CAMERA_WORLD)
    {
        LL_WARNS() << "Attempted to update distance for camera other than world camera!" << LL_ENDL;
        llassert(false);
        return;
    }

    if (gShiftFrame)
    {
        return;
    }

#if !LL_RELEASE_FOR_DOWNLOAD
    if (hasState(LLSpatialGroup::OBJECT_DIRTY))
    {
        LL_ERRS() << "Spatial group dirty on distance update." << LL_ENDL;
    }
#endif
    if (!isEmpty())
    {
        mRadius = getSpatialPartition()->mRenderByGroup ? mObjectBounds[1].getLength3().getF32() :
                        (F32) mOctreeNode->getSize().getLength3().getF32();
        mDistance = getSpatialPartition()->calcDistance(this, camera);
        mPixelArea = getSpatialPartition()->calcPixelArea(this, camera);
    }
}

F32 LLSpatialPartition::calcDistance(LLSpatialGroup* group, LLCamera& camera)
{
    LL_PROFILE_ZONE_SCOPED_CATEGORY_SPATIAL

    LLVector4a eye;
    LLVector4a origin;
    origin.load3(camera.getOrigin().mV);

    eye.setSub(group->mObjectBounds[0], origin);

    F32 dist = 0.f;

    if (group->mDrawMap.find(LLRenderPass::PASS_ALPHA) != group->mDrawMap.end())
    {
        LLVector4a v = eye;

        dist = eye.getLength3().getF32();
        eye.normalize3fast();

        if (!group->hasState(LLSpatialGroup::ALPHA_DIRTY))
        {
            if (!group->getSpatialPartition()->isBridge())
            {
                LLVector4a view_angle = eye;

                LLVector4a diff;
                diff.setSub(view_angle, group->mLastUpdateViewAngle);

                if (diff.getLength3().getF32() > 0.64f)
                {
                    group->mViewAngle = view_angle;
                    group->mLastUpdateViewAngle = view_angle;
                    //for occasional alpha sorting within the group
                    //NOTE: If there is a trivial way to detect that alpha sorting here would not change the render order,
                    //not setting this node to dirty would be a very good thing
                    group->setState(LLSpatialGroup::ALPHA_DIRTY);
                    gPipeline.markRebuild(group);
                }
            }
        }

        //calculate depth of node for alpha sorting

        LLVector3 at = camera.getAtAxis();

        LLVector4a ata;
        ata.load3(at.mV);

        LLVector4a t = ata;
        //front of bounding box
        t.mul(0.25f);
        t.mul(group->mObjectBounds[1]);
        v.sub(t);

        group->mDepth = v.dot3(ata).getF32();
    }
    else
    {
        dist = eye.getLength3().getF32();
    }

#if !LL_RELEASE
    LL_DEBUGS("RiggedBox") << "calcDistance, group " << group << " camera " << origin << " obj bounds "
                           << group->mObjectBounds[0] << ", " << group->mObjectBounds[1]
                           << " dist " << dist << " radius " << group->mRadius << LL_ENDL;
#endif

    if (dist < 16.f)
    {
        dist /= 16.f;
        dist *= dist;
        dist *= 16.f;
    }

    return dist;
}

F32 LLSpatialPartition::calcPixelArea(LLSpatialGroup* group, LLCamera& camera)
{
    return LLPipeline::calcPixelArea(group->mObjectBounds[0], group->mObjectBounds[1], camera);
}

F32 LLSpatialGroup::getUpdateUrgency() const
{
    if (!isVisible())
    {
        return 0.f;
    }
    else
    {
        F32 time = gFrameTimeSeconds-mLastUpdateTime+4.f;
        return time + (mObjectBounds[1].dot3(mObjectBounds[1]).getF32()+1.f)/mDistance;
    }
}

bool LLSpatialGroup::changeLOD()
{
    LL_PROFILE_ZONE_SCOPED_CATEGORY_SPATIAL

    if (hasState(ALPHA_DIRTY | OBJECT_DIRTY))
    {
        //a rebuild is going to happen, update distance and LoD
        return true;
    }

    if (getSpatialPartition()->mSlopRatio > 0.f)
    {
        F32 ratio = (mDistance - mLastUpdateDistance)/(llmax(mLastUpdateDistance, mRadius));

        // MAINT-8264 - this check is not robust if it needs to work
        // for bounding boxes much larger than the actual enclosed
        // objects, and using distance to box center is also
        // problematic. Consider the case that you have a large box
        // where the enclosed object is in one corner. As you zoom in
        // on the corner, the object gets much closer to the camera,
        // but the distance to the box center changes very little, and
        // an LOD change will not trigger, so object LOD gets "stuck"
        // at a too-low value. In the case of the above JIRA, the box
        // was large only due to another error, so this logic did not
        // need to be changed.

        if (fabsf(ratio) >= getSpatialPartition()->mSlopRatio)
        {
            LL_DEBUGS("RiggedBox") << "changeLOD true because of ratio compare "
                                   << fabsf(ratio) << " " << getSpatialPartition()->mSlopRatio << LL_ENDL;
            LL_DEBUGS("RiggedBox") << "sg " << this << "\nmDistance " << mDistance
                                   << " mLastUpdateDistance " << mLastUpdateDistance
                                   << " mRadius " << mRadius
                                   << " fab ratio " << fabsf(ratio)
                                   << " slop " << getSpatialPartition()->mSlopRatio << LL_ENDL;

            return true;
        }
    }

    if (needsUpdate())
    {
        return true;
    }

    return false;
}

void LLSpatialGroup::handleInsertion(const TreeNode* node, LLViewerOctreeEntry* entry)
{
    addObject((LLDrawable*)entry->getDrawable());
    unbound();
    setState(OBJECT_DIRTY);
}

void LLSpatialGroup::handleRemoval(const TreeNode* node, LLViewerOctreeEntry* entry)
{
    removeObject((LLDrawable*)entry->getDrawable(), true);
    LLViewerOctreeGroup::handleRemoval(node, entry);
}

void LLSpatialGroup::handleDestruction(const TreeNode* node)
{
    if(isDead())
    {
        return;
    }
    setState(DEAD);

    for (element_iter i = getDataBegin(); i != getDataEnd(); ++i)
    {
        LLViewerOctreeEntry* entry = *i;

        if (entry->getGroup() == this)
        {
            if(entry->hasDrawable())
            {
                ((LLDrawable*)entry->getDrawable())->setGroup(NULL);
            }
        }
    }

    clearDrawMap();
    mVertexBuffer = NULL;
    mBufferMap.clear();
    sZombieGroups++;
    mOctreeNode = NULL;
}

void LLSpatialGroup::handleChildAddition(const OctreeNode* parent, OctreeNode* child)
{
    LL_PROFILE_ZONE_SCOPED_CATEGORY_SPATIAL

    if (child->getListenerCount() == 0)
    {
        new LLSpatialGroup(child, getSpatialPartition());
    }
    else
    {
        OCT_ERRS << "LLSpatialGroup redundancy detected." << LL_ENDL;
    }

    unbound();

    assert_states_valid(this);
}

//virtual
void LLSpatialGroup::rebound()
{
    if (!isDirty())
        return;

    super::rebound();

    if (mSpatialPartition->mDrawableType == LLPipeline::RENDER_TYPE_CONTROL_AV)
    {
        llassert(mSpatialPartition->mPartitionType == LLViewerRegion::PARTITION_CONTROL_AV);

        LLSpatialBridge* bridge = getSpatialPartition()->asBridge();
        if (bridge &&
            bridge->mDrawable &&
            bridge->mDrawable->getVObj() &&
            bridge->mDrawable->getVObj()->isRoot())
        {
            LLControlAvatar* controlAvatar = bridge->mDrawable->getVObj()->getControlAvatar();
            if (controlAvatar &&
                controlAvatar->mDrawable &&
                controlAvatar->mControlAVBridge &&
                controlAvatar->mControlAVBridge->mOctree)
            {
                LLSpatialGroup* root = (LLSpatialGroup*)controlAvatar->mControlAVBridge->mOctree->getListener(0);
                if (this == root)
                {
                    const LLVector4a* addingExtents = controlAvatar->mDrawable->getSpatialExtents();
                    const LLXformMatrix* currentTransform = bridge->mDrawable->getXform();
                    expandExtents(addingExtents, *currentTransform);
                }
            }
        }
    }
}

void LLSpatialGroup::destroyGLState(bool keep_occlusion)
{
    setState(LLSpatialGroup::GEOM_DIRTY | LLSpatialGroup::IMAGE_DIRTY);

    if (!keep_occlusion)
    { //going to need a rebuild
        gPipeline.markRebuild(this);
    }

    mLastUpdateTime = gFrameTimeSeconds;
    mVertexBuffer = NULL;
    mBufferMap.clear();

    clearDrawMap();

    if (!keep_occlusion)
    {
        releaseOcclusionQueryObjectNames();
    }


    for (LLSpatialGroup::element_iter i = getDataBegin(); i != getDataEnd(); ++i)
    {
        LLDrawable* drawable = (LLDrawable*)(*i)->getDrawable();
        if(!drawable)
        {
            continue;
        }
        for (S32 j = 0; j < drawable->getNumFaces(); j++)
        {
            LLFace* facep = drawable->getFace(j);
            if (facep)
            {
                facep->clearVertexBuffer();
            }
        }
    }
}

//==============================================

LLSpatialPartition::LLSpatialPartition(U32 data_mask, bool render_by_group, LLViewerRegion* regionp)
: mRenderByGroup(render_by_group), mBridge(NULL)
{
    mRegionp = regionp;
    mPartitionType = LLViewerRegion::PARTITION_NONE;
    mVertexDataMask = data_mask;
    mDepthMask = false;
    mSlopRatio = 0.25f;
    mInfiniteFarClip = false;

    new LLSpatialGroup(mOctree, this);
}


LLSpatialPartition::~LLSpatialPartition()
{
    cleanup();
}

LLSpatialGroup *LLSpatialPartition::put(LLDrawable *drawablep, bool was_visible)
{
    LL_PROFILE_ZONE_SCOPED;
    drawablep->updateSpatialExtents();

    //keep drawable from being garbage collected
    LLPointer<LLDrawable> ptr = drawablep;

    if(!drawablep->getGroup())
    {
    assert_octree_valid(mOctree);
        mOctree->insert(drawablep->getEntry());
    assert_octree_valid(mOctree);
    }

    LLSpatialGroup* group = drawablep->getSpatialGroup();
    //llassert(group != NULL);

    if (group && was_visible && group->isOcclusionState(LLSpatialGroup::QUERY_PENDING))
    {
        group->setOcclusionState(LLSpatialGroup::DISCARD_QUERY, LLSpatialGroup::STATE_MODE_ALL_CAMERAS);
    }

    return group;
}

bool LLSpatialPartition::remove(LLDrawable *drawablep, LLSpatialGroup *curp)
{
    LL_PROFILE_ZONE_SCOPED;
    if (!curp->removeObject(drawablep))
    {
        OCT_ERRS << "Failed to remove drawable from octree!" << LL_ENDL;
    }
    else
    {
        drawablep->setGroup(NULL);
    }

    assert_octree_valid(mOctree);

    return true;
}

void LLSpatialPartition::move(LLDrawable *drawablep, LLSpatialGroup *curp, bool immediate)
{
    LL_PROFILE_ZONE_SCOPED;
    // sanity check submitted by open source user bushing Spatula
    // who was seeing crashing here. (See VWR-424 reported by Bunny Mayne)
    if (!drawablep)
    {
        OCT_ERRS << "LLSpatialPartition::move was passed a bad drawable." << LL_ENDL;
        return;
    }

    bool was_visible = curp ? curp->isVisible() : false;

    if (curp && curp->getSpatialPartition() != this)
    {
        //keep drawable from being garbage collected
        LLPointer<LLDrawable> ptr = drawablep;
        if (curp->getSpatialPartition()->remove(drawablep, curp))
        {
            put(drawablep, was_visible);
            return;
        }
        else
        {
            OCT_ERRS << "Drawable lost between spatial partitions on outbound transition." << LL_ENDL;
        }
    }

    if (curp && curp->updateInGroup(drawablep, immediate))
    {
        // Already updated, don't need to do anything
        assert_octree_valid(mOctree);
        return;
    }

    //keep drawable from being garbage collected
    LLPointer<LLDrawable> ptr = drawablep;
    if (curp && !remove(drawablep, curp))
    {
        OCT_ERRS << "Move couldn't find existing spatial group!" << LL_ENDL;
    }

    put(drawablep, was_visible);
}

class LLSpatialShift : public OctreeTraveler
{
public:
    const LLVector4a& mOffset;

    LLSpatialShift(const LLVector4a& offset) : mOffset(offset) { }
    virtual void visit(const OctreeNode* branch)
    {
        ((LLSpatialGroup*) branch->getListener(0))->shift(mOffset);
    }
};

void LLSpatialPartition::shift(const LLVector4a &offset)
{ //shift octree node bounding boxes by offset
    LLSpatialShift shifter(offset);
    shifter.traverse(mOctree);
}

class LLOctreeCull : public LLViewerOctreeCull
{
public:
    LLOctreeCull(LLCamera* camera) : LLViewerOctreeCull(camera) {}

    virtual bool earlyFail(LLViewerOctreeGroup* base_group)
    {
        if (LLPipeline::sReflectionRender)
        {
            return false;
        }

        LLSpatialGroup* group = (LLSpatialGroup*)base_group;
        group->checkOcclusion();

        if (group->getOctreeNode()->getParent() &&  //never occlusion cull the root node
            LLPipeline::sUseOcclusion &&            //ignore occlusion if disabled
            group->isOcclusionState(LLSpatialGroup::OCCLUDED))
        {
            gPipeline.markOccluder(group);
            return true;
        }

        return false;
    }

    virtual S32 frustumCheck(const LLViewerOctreeGroup* group)
    {
        S32 res = AABBInFrustumNoFarClipGroupBounds(group);
        if (res != 0)
        {
            res = llmin(res, AABBSphereIntersectGroupExtents(group));
        }
        return res;
    }

    virtual S32 frustumCheckObjects(const LLViewerOctreeGroup* group)
    {
        S32 res = AABBInFrustumNoFarClipObjectBounds(group);
        if (res != 0)
        {
            res = llmin(res, AABBSphereIntersectObjectExtents(group));
        }
        return res;
    }

    virtual void processGroup(LLViewerOctreeGroup* base_group)
    {
        LLSpatialGroup* group = (LLSpatialGroup*)base_group;
        /*if (group->needsUpdate() ||
            group->getVisible(LLViewerCamera::sCurCameraID) < LLDrawable::getCurrentFrame() - 1)
        {
            group->doOcclusion(mCamera);
        }*/
        gPipeline.markNotCulled(group, *mCamera);
    }
};

class LLOctreeCullNoFarClip : public LLOctreeCull
{
public:
    LLOctreeCullNoFarClip(LLCamera* camera)
        : LLOctreeCull(camera) { }

    virtual S32 frustumCheck(const LLViewerOctreeGroup* group)
    {
        return AABBInFrustumNoFarClipGroupBounds(group);
    }

    virtual S32 frustumCheckObjects(const LLViewerOctreeGroup* group)
    {
        S32 res = AABBInFrustumNoFarClipObjectBounds(group);
        return res;
    }
};

class LLOctreeCullShadow : public LLOctreeCull
{
public:
    LLOctreeCullShadow(LLCamera* camera)
        : LLOctreeCull(camera) { }

    virtual S32 frustumCheck(const LLViewerOctreeGroup* group)
    {
        return AABBInFrustumGroupBounds(group);
    }

    virtual S32 frustumCheckObjects(const LLViewerOctreeGroup* group)
    {
        return AABBInFrustumObjectBounds(group);
    }
};

class LLOctreeCullVisExtents: public LLOctreeCullShadow
{
public:
    LLOctreeCullVisExtents(LLCamera* camera, LLVector4a& min, LLVector4a& max)
        : LLOctreeCullShadow(camera), mMin(min), mMax(max), mEmpty(true) { }

    virtual bool earlyFail(LLViewerOctreeGroup* base_group)
    {
        LLSpatialGroup* group = (LLSpatialGroup*)base_group;

        if (group->getOctreeNode()->getParent() &&  //never occlusion cull the root node
            LLPipeline::sUseOcclusion &&            //ignore occlusion if disabled
            group->isOcclusionState(LLSpatialGroup::OCCLUDED))
        {
            return true;
        }

        return false;
    }

    virtual void traverse(const OctreeNode* n)
    {
        LLSpatialGroup* group = (LLSpatialGroup*) n->getListener(0);

        if (earlyFail(group))
        {
            return;
        }

        if ((mRes && group->hasState(LLSpatialGroup::SKIP_FRUSTUM_CHECK)) ||
            mRes == 2)
        {   //don't need to do frustum check
            OctreeTraveler::traverse(n);
        }
        else
        {
            mRes = frustumCheck(group);

            if (mRes)
            { //at least partially in, run on down
                OctreeTraveler::traverse(n);
            }

            mRes = 0;
        }
    }

    virtual void processGroup(LLViewerOctreeGroup* base_group)
    {
        LLSpatialGroup* group = (LLSpatialGroup*)base_group;

        llassert(!group->hasState(LLSpatialGroup::DIRTY) && !group->isEmpty());

        if (mRes < 2)
        {
            if (AABBInFrustumObjectBounds(group) > 0)
            {
                mEmpty = false;
                const LLVector4a* exts = group->getObjectExtents();
                update_min_max(mMin, mMax, exts[0]);
                update_min_max(mMin, mMax, exts[1]);
            }
        }
        else
        {
            mEmpty = false;
            const LLVector4a* exts = group->getExtents();
            update_min_max(mMin, mMax, exts[0]);
            update_min_max(mMin, mMax, exts[1]);
        }
    }

    bool mEmpty;
    LLVector4a& mMin;
    LLVector4a& mMax;
};

class LLOctreeCullDetectVisible: public LLOctreeCullShadow
{
public:
    LLOctreeCullDetectVisible(LLCamera* camera)
        : LLOctreeCullShadow(camera), mResult(false) { }

    virtual bool earlyFail(LLViewerOctreeGroup* base_group)
    {
        LLSpatialGroup* group = (LLSpatialGroup*)base_group;

        if (mResult || //already found a node, don't check any more
            (group->getOctreeNode()->getParent() && //never occlusion cull the root node
             LLPipeline::sUseOcclusion &&           //ignore occlusion if disabled
             group->isOcclusionState(LLSpatialGroup::OCCLUDED)))
        {
            return true;
        }

        return false;
    }

    virtual void processGroup(LLViewerOctreeGroup* base_group)
    {
        if (base_group->isVisible())
        {
            mResult = true;
        }
    }

    bool mResult;
};

class LLOctreeSelect : public LLOctreeCull
{
public:
    LLOctreeSelect(LLCamera* camera, std::vector<LLDrawable*>* results)
        : LLOctreeCull(camera), mResults(results) { }

    virtual bool earlyFail(LLViewerOctreeGroup* group) { return false; }
    virtual void preprocess(LLViewerOctreeGroup* group) { }

    virtual void processGroup(LLViewerOctreeGroup* base_group)
    {
        LLSpatialGroup* group = (LLSpatialGroup*)base_group;
        OctreeNode* branch = group->getOctreeNode();

        for (OctreeNode::const_element_iter i = branch->getDataBegin(); i != branch->getDataEnd(); ++i)
        {
            LLDrawable* drawable = (LLDrawable*)(*i)->getDrawable();
            if(!drawable)
        {
                continue;
            }
            if (!drawable->isDead())
            {
                if (drawable->isSpatialBridge())
                {
                    drawable->setVisible(*mCamera, mResults, true);
                }
                else
                {
                    mResults->push_back(drawable);
                }
            }
        }
    }

    std::vector<LLDrawable*>* mResults;
};

void drawBox(const LLVector3& c, const LLVector3& r)
{
    LLVertexBuffer::unbind();

    gGL.begin(LLRender::TRIANGLE_STRIP);
    //left front
    gGL.vertex3fv((c+r.scaledVec(LLVector3(-1,1,-1))).mV);
    gGL.vertex3fv((c+r.scaledVec(LLVector3(-1,1,1))).mV);
    //right front
    gGL.vertex3fv((c+r.scaledVec(LLVector3(1,1,-1))).mV);
    gGL.vertex3fv((c+r.scaledVec(LLVector3(1,1,1))).mV);
    //right back
    gGL.vertex3fv((c+r.scaledVec(LLVector3(1,-1,-1))).mV);
    gGL.vertex3fv((c+r.scaledVec(LLVector3(1,-1,1))).mV);
    //left back
    gGL.vertex3fv((c+r.scaledVec(LLVector3(-1,-1,-1))).mV);
    gGL.vertex3fv((c+r.scaledVec(LLVector3(-1,-1,1))).mV);
    //left front
    gGL.vertex3fv((c+r.scaledVec(LLVector3(-1,1,-1))).mV);
    gGL.vertex3fv((c+r.scaledVec(LLVector3(-1,1,1))).mV);
    gGL.end();

    //bottom
    gGL.begin(LLRender::TRIANGLE_STRIP);
    gGL.vertex3fv((c+r.scaledVec(LLVector3(1,1,-1))).mV);
    gGL.vertex3fv((c+r.scaledVec(LLVector3(1,-1,-1))).mV);
    gGL.vertex3fv((c+r.scaledVec(LLVector3(-1,1,-1))).mV);
    gGL.vertex3fv((c+r.scaledVec(LLVector3(-1,-1,-1))).mV);
    gGL.end();

    //top
    gGL.begin(LLRender::TRIANGLE_STRIP);
    gGL.vertex3fv((c+r.scaledVec(LLVector3(1,1,1))).mV);
    gGL.vertex3fv((c+r.scaledVec(LLVector3(-1,1,1))).mV);
    gGL.vertex3fv((c+r.scaledVec(LLVector3(1,-1,1))).mV);
    gGL.vertex3fv((c+r.scaledVec(LLVector3(-1,-1,1))).mV);
    gGL.end();
}

void drawBox(const LLVector4a& c, const LLVector4a& r)
{
    drawBox(reinterpret_cast<const LLVector3&>(c), reinterpret_cast<const LLVector3&>(r));
}

void drawBoxOutline(const LLVector3& pos, const LLVector3& size)
{
    if (!pos.isFinite() || !size.isFinite())
        return;

    LLVector3 v1 = size.scaledVec(LLVector3( 1, 1,1));
    LLVector3 v2 = size.scaledVec(LLVector3(-1, 1,1));
    LLVector3 v3 = size.scaledVec(LLVector3(-1,-1,1));
    LLVector3 v4 = size.scaledVec(LLVector3( 1,-1,1));

    gGL.begin(LLRender::LINES);

    //top
    gGL.vertex3fv((pos+v1).mV);
    gGL.vertex3fv((pos+v2).mV);
    gGL.vertex3fv((pos+v2).mV);
    gGL.vertex3fv((pos+v3).mV);
    gGL.vertex3fv((pos+v3).mV);
    gGL.vertex3fv((pos+v4).mV);
    gGL.vertex3fv((pos+v4).mV);
    gGL.vertex3fv((pos+v1).mV);

    //bottom
    gGL.vertex3fv((pos-v1).mV);
    gGL.vertex3fv((pos-v2).mV);
    gGL.vertex3fv((pos-v2).mV);
    gGL.vertex3fv((pos-v3).mV);
    gGL.vertex3fv((pos-v3).mV);
    gGL.vertex3fv((pos-v4).mV);
    gGL.vertex3fv((pos-v4).mV);
    gGL.vertex3fv((pos-v1).mV);

    //right
    gGL.vertex3fv((pos+v1).mV);
    gGL.vertex3fv((pos-v3).mV);

    gGL.vertex3fv((pos+v4).mV);
    gGL.vertex3fv((pos-v2).mV);

    //left
    gGL.vertex3fv((pos+v2).mV);
    gGL.vertex3fv((pos-v4).mV);

    gGL.vertex3fv((pos+v3).mV);
    gGL.vertex3fv((pos-v1).mV);

    gGL.end();
}

void drawBoxOutline(const LLVector4a& pos, const LLVector4a& size)
{
    drawBoxOutline(reinterpret_cast<const LLVector3&>(pos), reinterpret_cast<const LLVector3&>(size));
}


void LLSpatialPartition::restoreGL()
{
}

bool LLSpatialPartition::getVisibleExtents(LLCamera& camera, LLVector3& visMin, LLVector3& visMax)
{
    LL_PROFILE_ZONE_SCOPED_CATEGORY_SPATIAL;
    LLVector4a visMina, visMaxa;
    visMina.load3(visMin.mV);
    visMaxa.load3(visMax.mV);

    {
        LLSpatialGroup* group = (LLSpatialGroup*) mOctree->getListener(0);
        group->rebound();
    }

    LLOctreeCullVisExtents vis(&camera, visMina, visMaxa);
    vis.traverse(mOctree);

    visMin.set(visMina.getF32ptr());
    visMax.set(visMaxa.getF32ptr());
    return vis.mEmpty;
}

bool LLSpatialPartition::visibleObjectsInFrustum(LLCamera& camera)
{
    LLOctreeCullDetectVisible vis(&camera);
    vis.traverse(mOctree);
    return vis.mResult;
}

S32 LLSpatialPartition::cull(LLCamera &camera, std::vector<LLDrawable *>* results, bool for_select)
{
    LL_PROFILE_ZONE_SCOPED_CATEGORY_SPATIAL;
#if LL_OCTREE_PARANOIA_CHECK
    ((LLSpatialGroup*)mOctree->getListener(0))->checkStates();
#endif
    {
        LLSpatialGroup* group = (LLSpatialGroup*) mOctree->getListener(0);
        group->rebound();
    }

#if LL_OCTREE_PARANOIA_CHECK
    ((LLSpatialGroup*)mOctree->getListener(0))->validate();
#endif

        LLOctreeSelect selecter(&camera, results);
        selecter.traverse(mOctree);

    return 0;
}

extern bool gCubeSnapshot;

S32 LLSpatialPartition::cull(LLCamera &camera, bool do_occlusion)
{
    LL_PROFILE_ZONE_SCOPED_CATEGORY_SPATIAL;
#if LL_OCTREE_PARANOIA_CHECK
    ((LLSpatialGroup*)mOctree->getListener(0))->checkStates();
#endif
    LLSpatialGroup* group = (LLSpatialGroup*) mOctree->getListener(0);
    group->rebound();

#if LL_OCTREE_PARANOIA_CHECK
    ((LLSpatialGroup*)mOctree->getListener(0))->validate();
#endif

    if (LLPipeline::sShadowRender)
    {
        LLOctreeCullShadow culler(&camera);
        culler.traverse(mOctree);
    }
    else if (mInfiniteFarClip || (!LLPipeline::sUseFarClip && !gCubeSnapshot))
    {
        LLOctreeCullNoFarClip culler(&camera);
        culler.traverse(mOctree);
    }
    else
    {
        LLOctreeCull culler(&camera);
        culler.traverse(mOctree);
    }

    return 0;
}

void pushVerts(LLDrawInfo* params)
{
    LLRenderPass::applyModelMatrix(*params);
    params->mVertexBuffer->setBuffer();
    params->mVertexBuffer->drawRange(LLRender::TRIANGLES,
                                params->mStart, params->mEnd, params->mCount, params->mOffset);
}

void pushVerts(LLSpatialGroup* group)
{
    LLDrawInfo* params = NULL;

    for (LLSpatialGroup::draw_map_t::iterator i = group->mDrawMap.begin(); i != group->mDrawMap.end(); ++i)
    {
        for (LLSpatialGroup::drawmap_elem_t::iterator j = i->second.begin(); j != i->second.end(); ++j)
        {
            params = *j;
            pushVerts(params);
        }
    }
}

void pushVerts(LLFace* face)
{
    if (face)
    {
        llassert(face->verify());
        face->renderIndexed();
    }
}

void pushVerts(LLDrawable* drawable)
{
    for (S32 i = 0; i < drawable->getNumFaces(); ++i)
    {
        pushVerts(drawable->getFace(i));
    }
}

void pushVerts(LLVolume* volume)
{
    LLVertexBuffer::unbind();
    for (S32 i = 0; i < volume->getNumVolumeFaces(); ++i)
    {
        const LLVolumeFace& face = volume->getVolumeFace(i);
        LLVertexBuffer::drawElements(LLRender::TRIANGLES, face.mPositions, NULL, face.mNumIndices, face.mIndices);
    }
}

void pushBufferVerts(LLVertexBuffer* buffer)
{
    if (buffer)
    {
        buffer->setBuffer();
        buffer->drawRange(LLRender::TRIANGLES, 0, buffer->getNumVerts()-1, buffer->getNumIndices(), 0);
    }
}

void pushBufferVerts(LLSpatialGroup* group, bool push_alpha = true)
{
    if (group->getSpatialPartition()->mRenderByGroup)
    {
        if (!group->mDrawMap.empty())
        {
            LLDrawInfo* params = *(group->mDrawMap.begin()->second.begin());
            LLRenderPass::applyModelMatrix(*params);

            if (push_alpha)
            {
                pushBufferVerts(group->mVertexBuffer);
            }

            for (LLSpatialGroup::buffer_map_t::iterator i = group->mBufferMap.begin(); i != group->mBufferMap.end(); ++i)
            {
                for (LLSpatialGroup::buffer_texture_map_t::iterator j = i->second.begin(); j != i->second.end(); ++j)
                {
                    for (LLSpatialGroup::buffer_list_t::iterator k = j->second.begin(); k != j->second.end(); ++k)
                    {
                        pushBufferVerts(*k);
                    }
                }
            }
        }
    }
    /*else
    {
        //const LLVector4a* bounds = group->getBounds();
        //drawBox(bounds[0], bounds[1]);
    }*/
}

void pushVertsColorCoded(LLSpatialGroup* group)
{
    LLDrawInfo* params = NULL;

    static const LLColor4 colors[] = {
        LLColor4::green,
        LLColor4::green1,
        LLColor4::green2,
        LLColor4::green3,
        LLColor4::green4,
        LLColor4::green5,
        LLColor4::green6
    };

    static const U32 col_count = LL_ARRAY_SIZE(colors);

    U32 col = 0;

    for (LLSpatialGroup::draw_map_t::iterator i = group->mDrawMap.begin(); i != group->mDrawMap.end(); ++i)
    {
        for (LLSpatialGroup::drawmap_elem_t::iterator j = i->second.begin(); j != i->second.end(); ++j)
        {
            params = *j;
            LLRenderPass::applyModelMatrix(*params);
            gGL.diffuseColor4f(colors[col].mV[0], colors[col].mV[1], colors[col].mV[2], 0.5f);
            params->mVertexBuffer->setBuffer();
            params->mVertexBuffer->drawRange(LLRender::TRIANGLES,
                params->mStart, params->mEnd, params->mCount, params->mOffset);
            col = (col+1)%col_count;
        }
    }
}

// return false if drawable is rigged and:
//  - a linked rigged drawable has a different spatial group
//  - a linked rigged drawable face has the wrong draw order index
bool check_rigged_group(LLDrawable* drawable)
{
#if 0
    if (drawable->isState(LLDrawable::RIGGED))
    {
        LLSpatialGroup* group = drawable->getSpatialGroup();
        LLDrawable* root = drawable->getRoot();

        if (root->isState(LLDrawable::RIGGED) && root->getSpatialGroup() != group)
        {
            LL_WARNS() << "[root->isState(LLDrawable::RIGGED) and root->getSpatialGroup() != group] is true"
                " (" << root->getSpatialGroup() << " != " << group << ")" << LL_ENDL;
            llassert(false);
            return false;
        }

        S32 last_draw_index = -1;
        if (root->isState(LLDrawable::RIGGED))
        {
            for (auto& face : root->getFaces())
            {
                if ((S32) face->getDrawOrderIndex() <= last_draw_index)
                {
                    LL_WARNS() << "[(S32)face->getDrawOrderIndex() <= last_draw_index] is true"
                        " (" << (S32)face->getDrawOrderIndex() << " <= " << last_draw_index << ")" << LL_ENDL;
                    llassert(false);
                    return false;
                }
                last_draw_index = face->getDrawOrderIndex();
            }
        }

        for (auto& child : root->getVObj()->getChildren())
        {
            if (child->mDrawable->isState(LLDrawable::RIGGED))
            {
                for (auto& face : child->mDrawable->getFaces())
                {
                    if ((S32) face->getDrawOrderIndex() <= last_draw_index)
                    {
                        LL_WARNS() << "[(S32)face->getDrawOrderIndex() <= last_draw_index] is true"
                            " (" << (S32)face->getDrawOrderIndex() << " <= " << last_draw_index << ")" << LL_ENDL;
                        llassert(false);
                        return false;
                    }
                    last_draw_index = face->getDrawOrderIndex();
                }
            }

            if (child->mDrawable->getSpatialGroup() != group)
            {
                LL_WARNS() << "[child->mDrawable->getSpatialGroup() != group] is true"
                    " (" << child->mDrawable->getSpatialGroup() << " != " << group << ")" << LL_ENDL;
                llassert(false);
                return false;
            }
        }
    }
#endif
    return true;
}

void renderOctree(LLSpatialGroup* group)
{
    //render solid object bounding box, color
    //coded by buffer usage and activity
    gGL.setSceneBlendType(LLRender::BT_ADD_WITH_ALPHA);
    LLVector4 col;
    if (group->mBuilt > 0.f)
    {
        group->mBuilt -= 2.f * gFrameIntervalSeconds.value();
        col.setVec(0.1f,0.1f,1,0.1f);

        {
            LLGLDepthTest gl_depth(false, false);
            glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);

            gGL.diffuseColor4f(1,0,0,group->mBuilt);
            gGL.flush();
            glLineWidth(5.f);

            const LLVector4a* bounds = group->getObjectBounds();
            drawBoxOutline(bounds[0], bounds[1]);
            gGL.flush();
            glLineWidth(1.f);
            gGL.flush();

            LLVOAvatar* lastAvatar = nullptr;
            U64 lastMeshId = 0;

            for (LLSpatialGroup::element_iter i = group->getDataBegin(); i != group->getDataEnd(); ++i)
            {
                LLDrawable* drawable = (LLDrawable*)(*i)->getDrawable();
                if(!drawable || drawable->getNumFaces() == 0)
                {
                    continue;
                }

                llassert(check_rigged_group(drawable));

                if (!group->getSpatialPartition()->isBridge())
                {
                    gGL.pushMatrix();
                    LLVector3 trans = drawable->getRegion()->getOriginAgent();
                    gGL.translatef(trans.mV[0], trans.mV[1], trans.mV[2]);
                }

                LLFace* face = drawable->getFace(0);
                bool rigged = face->isState(LLFace::RIGGED);
                gDebugProgram.bind(rigged);

                gGL.diffuseColor4f(1, 0, 0, 1);

                if (rigged)
                {
                    gGL.pushMatrix();
                    gGL.loadMatrix(gGLModelView);
                    if (lastAvatar != face->mAvatar ||
                        lastMeshId != face->mSkinInfo->mHash)
                    {
                        if (!LLRenderPass::uploadMatrixPalette(face->mAvatar, face->mSkinInfo))
                        {
                            continue;
                        }
                        lastAvatar = face->mAvatar;
                        lastMeshId = face->mSkinInfo->mHash;
                    }
                }
                for (S32 j = 0; j < drawable->getNumFaces(); j++)
                {
                    LLFace* face = drawable->getFace(j);
                    if (face && face->getVertexBuffer())
                    {
                        LLVOVolume* vol = drawable->getVOVolume();

                        if (gFrameTimeSeconds - face->mLastUpdateTime < 0.5f)
                        {
                            if (vol && vol->isShrinkWrapped())
                            {
                                gGL.diffuseColor4f(0, 1, 1, group->mBuilt);
                            }
                            else
                            {
                                gGL.diffuseColor4f(0, 1, 0, group->mBuilt);
                            }
                        }
                        else if (gFrameTimeSeconds - face->mLastMoveTime < 0.5f)
                        {
                            if (vol && vol->isShrinkWrapped())
                            {
                                gGL.diffuseColor4f(1, 1, 0, group->mBuilt);
                            }
                            else
                            {
                                gGL.diffuseColor4f(1, 0, 0, group->mBuilt);
                            }
                        }
                        else
                        {
                            continue;
                        }

                        face->getVertexBuffer()->setBuffer();
                        face->getVertexBuffer()->draw(LLRender::TRIANGLES, face->getIndicesCount(), face->getIndicesStart());
                    }
                }

                if (rigged)
                {
                    gGL.popMatrix();
                }

                if (!group->getSpatialPartition()->isBridge())
                {
                    gGL.popMatrix();
                }
            }
            glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
            gDebugProgram.bind(); // make sure non-rigged variant is bound
            gGL.diffuseColor4f(1,1,1,1);
        }
    }

    gGL.diffuseColor4fv(col.mV);
    LLVector4a fudge;
    fudge.splat(0.001f);

    gGL.setSceneBlendType(LLRender::BT_ALPHA);

    {
        //draw opaque outline
        gGL.diffuseColor4f(0,1,1,1);

        const LLVector4a* bounds = group->getBounds();
        drawBoxOutline(bounds[0], bounds[1]);
    }
}

std::set<LLSpatialGroup*> visible_selected_groups;



void renderXRay(LLSpatialGroup* group, LLCamera* camera)
{
    bool render_objects = (!LLPipeline::sUseOcclusion || !group->isOcclusionState(LLSpatialGroup::OCCLUDED)) && group->isVisible() &&
                            !group->isEmpty();

    if (render_objects)
    {
        pushBufferVerts(group, false);

        bool selected = false;

        for (LLSpatialGroup::element_iter iter = group->getDataBegin(); iter != group->getDataEnd(); ++iter)
        {
            LLDrawable* drawable = (LLDrawable*)(*iter)->getDrawable();
            if (drawable->getVObj().notNull() && drawable->getVObj()->isSelected())
            {
                selected = true;
                break;
            }
        }

        if (selected)
        { //store for rendering occlusion volume as overlay

            if (!group->getSpatialPartition()->isBridge())
            {
                visible_selected_groups.insert(group);
            }
            else
            {
                visible_selected_groups.insert(group->getSpatialPartition()->asBridge()->getSpatialGroup());
            }
        }
    }
}

void renderCrossHairs(LLVector3 position, F32 size, LLColor4 color)
{
    gGL.color4fv(color.mV);
    gGL.begin(LLRender::LINES);
    {
        gGL.vertex3fv((position - LLVector3(size, 0.f, 0.f)).mV);
        gGL.vertex3fv((position + LLVector3(size, 0.f, 0.f)).mV);
        gGL.vertex3fv((position - LLVector3(0.f, size, 0.f)).mV);
        gGL.vertex3fv((position + LLVector3(0.f, size, 0.f)).mV);
        gGL.vertex3fv((position - LLVector3(0.f, 0.f, size)).mV);
        gGL.vertex3fv((position + LLVector3(0.f, 0.f, size)).mV);
    }
    gGL.end();
}

void renderUpdateType(LLDrawable* drawablep)
{
    LLViewerObject* vobj = drawablep->getVObj();
    if (!vobj || OUT_UNKNOWN == vobj->getLastUpdateType())
    {
        return;
    }
    LLGLEnable blend(GL_BLEND);
    switch (vobj->getLastUpdateType())
    {
    case OUT_FULL:
        gGL.diffuseColor4f(0,1,0,0.5f);
        break;
    case OUT_TERSE_IMPROVED:
        gGL.diffuseColor4f(0,1,1,0.5f);
        break;
    case OUT_FULL_COMPRESSED:
        if (vobj->getLastUpdateCached())
        {
            gGL.diffuseColor4f(1,0,0,0.5f);
        }
        else
        {
            gGL.diffuseColor4f(1,1,0,0.5f);
        }
        break;
    case OUT_FULL_CACHED:
        gGL.diffuseColor4f(0,0,1,0.5f);
        break;
    default:
        LL_WARNS() << "Unknown update_type " << vobj->getLastUpdateType() << LL_ENDL;
        break;
    };
    S32 num_faces = drawablep->getNumFaces();
    if (num_faces)
    {
        for (S32 i = 0; i < num_faces; ++i)
        {
            pushVerts(drawablep->getFace(i));
        }
    }
}

void renderBoundingBox(LLDrawable* drawable, bool set_color = true)
{
    if (set_color)
    {
        if (drawable->isSpatialBridge())
        {
            gGL.diffuseColor4f(1,0.5f,0,1); // orange
        }
        else if (drawable->getVOVolume())
        {
            if (drawable->isRoot())
            {
                gGL.diffuseColor4f(1,1,0,1); // yellow
            }
            else
            {
                gGL.diffuseColor4f(0,1,0,1); // green
            }
        }
        else if (drawable->getVObj())
        {
            switch (drawable->getVObj()->getPCode())
            {
                case LLViewerObject::LL_VO_SURFACE_PATCH:
                        gGL.diffuseColor4f(0,1,1,1); // cyan
                        break;
                case LLViewerObject::LL_VO_CLOUDS:
                        // no longer used
                        break;
                case LLViewerObject::LL_VO_PART_GROUP:
                case LLViewerObject::LL_VO_HUD_PART_GROUP:
                        gGL.diffuseColor4f(0,0,1,1); // blue
                        break;
                case LLViewerObject::LL_VO_VOID_WATER:
                case LLViewerObject::LL_VO_WATER:
                        gGL.diffuseColor4f(0,0.5f,1,1); // medium blue
                        break;
                case LL_PCODE_LEGACY_TREE:
                        gGL.diffuseColor4f(0,0.5f,0,1); // dark green
                        break;
                default:
                        LLControlAvatar *cav = dynamic_cast<LLControlAvatar*>(drawable->getVObj()->asAvatar());
                        if (cav)
                        {
                            bool has_pos_constraint = (cav->mPositionConstraintFixup != LLVector3());
                            bool has_scale_constraint = (cav->mScaleConstraintFixup != 1.0f);
                            if (has_pos_constraint || has_scale_constraint)
                            {
                                gGL.diffuseColor4f(1,0,0,1);
                            }
                            else
                            {
                                gGL.diffuseColor4f(0,1,0.5,1);
                            }
                        }
                        else
                        {
                            gGL.diffuseColor4f(1,0,1,1); // magenta
                        }
                        break;
            }
        }
        else
        {
            gGL.diffuseColor4f(1,0,0,1);
        }
    }

    const LLVector4a* ext;
    LLVector4a pos, size;

    if (drawable->getVOVolume())
    {
        //render face bounding boxes
        for (S32 i = 0; i < drawable->getNumFaces(); i++)
        {
            LLFace* facep = drawable->getFace(i);
            if (facep)
            {
                ext = facep->mExtents;

                pos.setAdd(ext[0], ext[1]);
                pos.mul(0.5f);
                size.setSub(ext[1], ext[0]);
                size.mul(0.5f);

                drawBoxOutline(pos,size);
            }
        }
    }

    //render drawable bounding box
    ext = drawable->getSpatialExtents();

    pos.setAdd(ext[0], ext[1]);
    pos.mul(0.5f);
    size.setSub(ext[1], ext[0]);
    size.mul(0.5f);

    LLViewerObject* vobj = drawable->getVObj();
    if (vobj && vobj->onActiveList())
    {
        gGL.flush();
        glLineWidth(llmax(4.f*sinf(gFrameTimeSeconds*2.f)+1.f, 1.f));
        //glLineWidth(4.f*(sinf(gFrameTimeSeconds*2.f)*0.25f+0.75f));
        stop_glerror();
        drawBoxOutline(pos,size);
        gGL.flush();
        glLineWidth(1.f);
    }
    else
    {
        drawBoxOutline(pos,size);
    }
}
// *TODO: LLDrawables which are not part of LLVOVolumes fall into a different
// code path which uses a shader - it was tested to be faster than mapping a
// vertex buffer in the terrain case. Consider using it for LLVOVolumes as well
// to simplify and speed up this debug code. Alternatively, a compute shader is
// likely faster. -Cosmic,2023-09-28
void renderNormals(LLDrawable *drawablep)
{
    if (!drawablep->isVisible())
        return;

    LLVertexBuffer::unbind();

    LLViewerObject* obj = drawablep->getVObj();
    LLVOVolume *vol = drawablep->getVOVolume();

    if (obj)
    {
        LLGLEnable blend(GL_BLEND);
        LLGLDepthTest gl_depth(GL_TRUE, GL_FALSE);

        // Drawable's normals & tangents are stored in model space, i.e. before any scaling is applied.
        //
        // SL-13490, using pos + normal to compute the 2nd vertex of a normal line segment doesn't
        // work when there's a non-uniform scale in the mix. Normals require MVP-inverse-transpose
        // transform. We get that effect here by pre-applying the inverse scale (twice, because
        // one forward scale will be re-applied via the MVP in the vertex shader)

        LLVector4a inv_scale;
        float scale_len;
        if (vol)
        {
            LLVector3  scale_v3 = vol->getScale();
            LLVector4a obj_scale(scale_v3.mV[VX], scale_v3.mV[VY], scale_v3.mV[VZ]);
            obj_scale.normalize3();

            // Create inverse-scale vector for normals
            inv_scale.set(1.0f / scale_v3.mV[VX], 1.0f / scale_v3.mV[VY], 1.0f/ scale_v3.mV[VZ], 0.0f);
            inv_scale.mul(inv_scale);  // Squared, to apply inverse scale twice

            inv_scale.normalize3fast();
            scale_len = scale_v3.length();
        }
        else
        {
            inv_scale.set(1.0, 1.0, 1.0, 0.0);
            scale_len = 1.0;
        }

        gGL.pushMatrix();
        if (vol)
        {
            gGL.multMatrix((F32 *) vol->getRelativeXform().mMatrix);
        }

        gGL.getTexUnit(0)->unbind(LLTexUnit::TT_TEXTURE);

        // Normals &tangent line segments get scaled along with the object. Divide by scale length
        // to keep the as-viewed lengths (relatively) constant with the debug setting length
        float draw_length = gSavedSettings.getF32("RenderDebugNormalScale") / scale_len;

        std::vector<LLVolumeFace>* faces = nullptr;
        std::vector<LLFace*>* drawable_faces = nullptr;
        if (vol)
        {
            LLVolume* volume = vol->getVolume();
            faces = &volume->getVolumeFaces();
        }
        else
        {
            drawable_faces = &drawablep->getFaces();
        }

        if (faces)
        {
            for (auto it = faces->begin(); it != faces->end(); ++it)
            {
                const LLVolumeFace& face = *it;

                gGL.flush();
                gGL.diffuseColor4f(1, 1, 0, 1);
                gGL.begin(LLRender::LINES);
                for (S32 j = 0; j < face.mNumVertices; ++j)
                {
                    LLVector4a n, p;

                    n.setMul(face.mNormals[j], 1.0);
                    n.mul(inv_scale);  // Pre-scale normal, so it's left with an inverse-transpose xform after MVP
                    n.normalize3fast();
                    n.mul(draw_length);
                    p.setAdd(face.mPositions[j], n);

                    gGL.vertex3fv(face.mPositions[j].getF32ptr());
                    gGL.vertex3fv(p.getF32ptr());
                }
                gGL.end();

                // Tangents are simple vectors and do not require reorientation via pre-scaling
                if (face.mTangents)
                {
                    gGL.flush();
                    gGL.diffuseColor4f(0, 1, 1, 1);
                    gGL.begin(LLRender::LINES);
                    for (S32 j = 0; j < face.mNumVertices; ++j)
                    {
                        LLVector4a t, p;

                        t.setMul(face.mTangents[j], 1.0f);
                        t.normalize3fast();
                        t.mul(draw_length);
                        p.setAdd(face.mPositions[j], t);

                        gGL.vertex3fv(face.mPositions[j].getF32ptr());
                        gGL.vertex3fv(p.getF32ptr());
                    }
                    gGL.end();
                }
            }
        }
        else if (drawable_faces)
        {
            // *HACK: Prepare to restore previous shader as other debug code depends on a simpler shader being present
            llassert(LLGLSLShader::sCurBoundShaderPtr == &gDebugProgram);
            LLGLSLShader* prev_shader = LLGLSLShader::sCurBoundShaderPtr;
            for (auto it = drawable_faces->begin(); it != drawable_faces->end(); ++it)
            {
                LLFace* facep = *it;
                LLFace& face = **it;
                LLVertexBuffer* buf = face.getVertexBuffer();
                if (!buf) { continue; }
                U32 mask_vn = LLVertexBuffer::TYPE_VERTEX | LLVertexBuffer::TYPE_NORMAL;
                if ((buf->getTypeMask() & mask_vn) != mask_vn) { continue; }

                LLGLSLShader* shader;
                if ((buf->getTypeMask() & LLVertexBuffer::TYPE_TANGENT) != LLVertexBuffer::TYPE_TANGENT)
                {
                    shader = &gNormalDebugProgram[NORMAL_DEBUG_SHADER_DEFAULT];
                }
                else
                {
                    shader = &gNormalDebugProgram[NORMAL_DEBUG_SHADER_WITH_TANGENTS];
                }
                shader->bind();

                shader->uniform1f(LLShaderMgr::DEBUG_NORMAL_DRAW_LENGTH, draw_length);

                LLRenderPass::applyModelMatrix(&facep->getDrawable()->getRegion()->mRenderMatrix);

                buf->setBuffer();
                // *NOTE: The render type in the vertex shader is TRIANGLES, but gets converted to LINES in the geometry shader
                // *NOTE: For terrain normal debug, this seems to also include vertices for water, which is technically not part of the terrain. Should fix that at some point.
                buf->drawRange(LLRender::TRIANGLES, face.getGeomIndex(), face.getGeomIndex() + face.getGeomCount()-1, face.getIndicesCount(), face.getIndicesStart());
            }
            if (prev_shader)
            {
                prev_shader->bind();
            }
        }

        gGL.popMatrix();
    }
}

S32 get_physics_detail(const LLVolumeParams& volume_params, const LLVector3& scale)
{
    const S32 DEFAULT_DETAIL = 1;
    const F32 LARGE_THRESHOLD = 5.f;
    const F32 MEGA_THRESHOLD = 25.f;

    S32 detail = DEFAULT_DETAIL;
    F32 avg_scale = (scale[0]+scale[1]+scale[2])/3.f;

    if (avg_scale > LARGE_THRESHOLD)
    {
        detail += 1;
        if (avg_scale > MEGA_THRESHOLD)
        {
            detail += 1;
        }
    }

    return detail;
}

void renderMeshBaseHull(LLVOVolume* volume, U32 data_mask, LLColor4& color)
{
    LLUUID mesh_id = volume->getVolume()->getParams().getSculptID();
    LLModel::Decomposition* decomp = gMeshRepo.getDecomposition(mesh_id);

    const LLVector3 center(0,0,0);
    const LLVector3 size(0.25f,0.25f,0.25f);

    if (decomp)
    {
        if (!decomp->mBaseHullMesh.empty())
        {
            gGL.diffuseColor4fv(color.mV);
            LLVertexBuffer::drawArrays(LLRender::TRIANGLES, decomp->mBaseHullMesh.mPositions);
        }
        else
        {
            gMeshRepo.buildPhysicsMesh(*decomp);
            gGL.diffuseColor4f(0,1,1,1);
            drawBoxOutline(center, size);
        }

    }
    else
    {
        gGL.diffuseColor3f(1,0,1);
        drawBoxOutline(center, size);
    }
}

void render_hull(LLModel::PhysicsMesh& mesh, const LLColor4& color)
{
    gGL.diffuseColor4fv(color.mV);
    LLVertexBuffer::drawArrays(LLRender::TRIANGLES, mesh.mPositions);
}

void renderPhysicsShape(LLDrawable* drawable, LLVOVolume* volume, bool wireframe)
{
    U8 physics_type = volume->getPhysicsShapeType();

    if (physics_type == LLViewerObject::PHYSICS_SHAPE_NONE || volume->isFlexible())
    {
        return;
    }

    //not allowed to return at this point without rendering *something*

    F32 threshold = gSavedSettings.getF32("ObjectCostHighThreshold");
    F32 cost = volume->getObjectCost();

    LLColor4 low = gSavedSettings.getColor4("ObjectCostLowColor");
    LLColor4 mid = gSavedSettings.getColor4("ObjectCostMidColor");
    LLColor4 high = gSavedSettings.getColor4("ObjectCostHighColor");

    F32 normalizedCost = 1.f - exp( -(cost / threshold) );

    LLColor4 color;
    if ( normalizedCost <= 0.5f )
    {
        color = lerp( low, mid, 2.f * normalizedCost );
    }
    else
    {
        color = lerp( mid, high, 2.f * ( normalizedCost - 0.5f ) );
    }

    if (wireframe)
    {
        color = color * 0.5f;
    }

    U32 data_mask = LLVertexBuffer::MAP_VERTEX;

    LLVolumeParams volume_params = volume->getVolume()->getParams();

    LLPhysicsVolumeParams physics_params(volume_params,
        physics_type == LLViewerObject::PHYSICS_SHAPE_CONVEX_HULL);

    LLPhysicsShapeBuilderUtil::PhysicsShapeSpecification physics_spec;
    LLPhysicsShapeBuilderUtil::determinePhysicsShape(physics_params, volume->getScale(), physics_spec);

    U32 type = physics_spec.getType();

    LLVector3 center(0,0,0);
    LLVector3 size(0.25f,0.25f,0.25f);

    gGL.pushMatrix();
    gGL.multMatrix((F32*) volume->getRelativeXform().mMatrix);

    if (type == LLPhysicsShapeBuilderUtil::PhysicsShapeSpecification::USER_MESH)
    {
        LLUUID mesh_id = volume->getVolume()->getParams().getSculptID();
        LLModel::Decomposition* decomp = gMeshRepo.getDecomposition(mesh_id);

        if (decomp)
        { //render a physics based mesh

            gGL.getTexUnit(0)->unbind(LLTexUnit::TT_TEXTURE);

            if (!decomp->mHull.empty())
            { //decomposition exists, use that

                if (decomp->mMesh.empty())
                {
                    gMeshRepo.buildPhysicsMesh(*decomp);
                }

                for (U32 i = 0; i < decomp->mMesh.size(); ++i)
                {
                    render_hull(decomp->mMesh[i], color);
                }
            }
            else if (!decomp->mPhysicsShapeMesh.empty())
            {
                //decomp has physics mesh, render that mesh
                gGL.diffuseColor4fv(color.mV);

                LLVertexBuffer::drawArrays(LLRender::TRIANGLES, decomp->mPhysicsShapeMesh.mPositions);
            }
            else
            { //no mesh or decomposition, render base hull
                renderMeshBaseHull(volume, data_mask, color);

                if (decomp->mPhysicsShapeMesh.empty())
                {
                    //attempt to fetch physics shape mesh if available
                    gMeshRepo.fetchPhysicsShape(mesh_id);
                }
            }
        }
        else
        {
            gGL.diffuseColor3f(1,1,0);
            drawBoxOutline(center, size);
        }
    }
    else if (type == LLPhysicsShapeBuilderUtil::PhysicsShapeSpecification::USER_CONVEX ||
        type == LLPhysicsShapeBuilderUtil::PhysicsShapeSpecification::PRIM_CONVEX)
    {
        if (volume->isMesh())
        {
            renderMeshBaseHull(volume, data_mask, color);
        }
        else
        {
            LLVolumeParams volume_params = volume->getVolume()->getParams();
            S32 detail = get_physics_detail(volume_params, volume->getScale());
            LLVolume* phys_volume = LLPrimitive::sVolumeManager->refVolume(volume_params, detail);

            if (!phys_volume->mHullPoints)
            { //build convex hull
                std::vector<LLVector3> pos;
                std::vector<U16> index;

                S32 index_offset = 0;

                for (S32 i = 0; i < phys_volume->getNumVolumeFaces(); ++i)
                {
                    const LLVolumeFace& face = phys_volume->getVolumeFace(i);
                    if (index_offset + face.mNumVertices > 65535)
                    {
                        continue;
                    }

                    for (S32 j = 0; j < face.mNumVertices; ++j)
                    {
                        pos.push_back(LLVector3(face.mPositions[j].getF32ptr()));
                    }

                    for (S32 j = 0; j < face.mNumIndices; ++j)
                    {
                        index.push_back(face.mIndices[j]+index_offset);
                    }

                    index_offset += face.mNumVertices;
                }

                if (!pos.empty() && !index.empty())
                {
                    LLCDMeshData mesh;
                    mesh.mIndexBase = &index[0];
                    mesh.mVertexBase = pos[0].mV;
                    mesh.mNumVertices = static_cast<int>(pos.size());
                    mesh.mVertexStrideBytes = 12;
                    mesh.mIndexStrideBytes = 6;
                    mesh.mIndexType = LLCDMeshData::INT_16;

                    mesh.mNumTriangles = static_cast<int>(index.size())/3;

                    LLCDMeshData res;

                    LLConvexDecomposition::getInstance()->generateSingleHullMeshFromMesh( &mesh, &res );

                    //copy res into phys_volume
                    phys_volume->mHullPoints = (LLVector4a*) ll_aligned_malloc_16(sizeof(LLVector4a)*res.mNumVertices);
                    phys_volume->mNumHullPoints = res.mNumVertices;

                    S32 idx_size = (res.mNumTriangles*3*2+0xF) & ~0xF;
                    phys_volume->mHullIndices = (U16*) ll_aligned_malloc_16(idx_size);
                    phys_volume->mNumHullIndices = res.mNumTriangles*3;

                    const F32* v = res.mVertexBase;

                    for (S32 i = 0; i < res.mNumVertices; ++i)
                    {
                        F32* p = (F32*) ((U8*)v+i*res.mVertexStrideBytes);
                        phys_volume->mHullPoints[i].load3(p);
                    }

                    if (res.mIndexType == LLCDMeshData::INT_16)
                    {
                        for (S32 i = 0; i < res.mNumTriangles; ++i)
                        {
                            U16* idx = (U16*) (((U8*)res.mIndexBase)+i*res.mIndexStrideBytes);

                            phys_volume->mHullIndices[i*3+0] = idx[0];
                            phys_volume->mHullIndices[i*3+1] = idx[1];
                            phys_volume->mHullIndices[i*3+2] = idx[2];
                        }
                    }
                    else
                    {
                        for (S32 i = 0; i < res.mNumTriangles; ++i)
                        {
                            U32* idx = (U32*) (((U8*)res.mIndexBase)+i*res.mIndexStrideBytes);

                            phys_volume->mHullIndices[i*3+0] = (U16) idx[0];
                            phys_volume->mHullIndices[i*3+1] = (U16) idx[1];
                            phys_volume->mHullIndices[i*3+2] = (U16) idx[2];
                        }
                    }
                }
            }

            if (phys_volume->mHullPoints)
            {
                //render hull
                gGL.diffuseColor4fv(color.mV);

                LLVertexBuffer::unbind();
                LLVertexBuffer::drawElements(LLRender::TRIANGLES, phys_volume->mHullPoints, NULL, phys_volume->mNumHullIndices, phys_volume->mHullIndices);
            }
            else
            {
                gGL.diffuseColor4f(1,0,1,1);
                drawBoxOutline(center, size);
            }

            LLPrimitive::sVolumeManager->unrefVolume(phys_volume);
        }
    }
    else if (type == LLPhysicsShapeBuilderUtil::PhysicsShapeSpecification::BOX)
    {
        if (!wireframe)
        {
            LLVector3 center = physics_spec.getCenter();
            LLVector3 scale = physics_spec.getScale();
            LLVector3 vscale = volume->getScale() * 2.f;
            scale.set(scale[0] / vscale[0], scale[1] / vscale[1], scale[2] / vscale[2]);

            gGL.diffuseColor4fv(color.mV);
            drawBox(center, scale);
        }
    }
    else if (type == LLPhysicsShapeBuilderUtil::PhysicsShapeSpecification::SPHERE)
    {
        if (!wireframe)
        {
            LLVolumeParams volume_params;
            volume_params.setType(LL_PCODE_PROFILE_CIRCLE_HALF, LL_PCODE_PATH_CIRCLE);
            volume_params.setBeginAndEndS(0.f, 1.f);
            volume_params.setBeginAndEndT(0.f, 1.f);
            volume_params.setRatio(1, 1);
            volume_params.setShear(0, 0);
            LLVolume* sphere = LLPrimitive::sVolumeManager->refVolume(volume_params, 3);

            gGL.diffuseColor4fv(color.mV);
            pushVerts(sphere);
            LLPrimitive::sVolumeManager->unrefVolume(sphere);
        }
    }
    else if (type == LLPhysicsShapeBuilderUtil::PhysicsShapeSpecification::CYLINDER)
    {
        if (!wireframe)
        {
            LLVolumeParams volume_params;
            volume_params.setType(LL_PCODE_PROFILE_CIRCLE, LL_PCODE_PATH_LINE);
            volume_params.setBeginAndEndS(0.f, 1.f);
            volume_params.setBeginAndEndT(0.f, 1.f);
            volume_params.setRatio(1, 1);
            volume_params.setShear(0, 0);
            LLVolume* cylinder = LLPrimitive::sVolumeManager->refVolume(volume_params, 3);

            gGL.diffuseColor4fv(color.mV);
            pushVerts(cylinder);
            LLPrimitive::sVolumeManager->unrefVolume(cylinder);
        }
    }
    else if (type == LLPhysicsShapeBuilderUtil::PhysicsShapeSpecification::PRIM_MESH)
    {
        LLVolumeParams volume_params = volume->getVolume()->getParams();
        S32 detail = get_physics_detail(volume_params, volume->getScale());

        LLVolume* phys_volume = LLPrimitive::sVolumeManager->refVolume(volume_params, detail);

        gGL.diffuseColor4fv(color.mV);
        pushVerts(phys_volume);

        LLPrimitive::sVolumeManager->unrefVolume(phys_volume);
    }
    else if (type == LLPhysicsShapeBuilderUtil::PhysicsShapeSpecification::PRIM_CONVEX)
    {
        LLVolumeParams volume_params = volume->getVolume()->getParams();
        S32 detail = get_physics_detail(volume_params, volume->getScale());

        LLVolume* phys_volume = LLPrimitive::sVolumeManager->refVolume(volume_params, detail);

        if (phys_volume->mHullPoints && phys_volume->mHullIndices)
        {

            llassert(LLGLSLShader::sCurBoundShader != 0);
            LLVertexBuffer::unbind();
            glVertexPointer(3, GL_FLOAT, 16, phys_volume->mHullPoints);

            gGL.diffuseColor4fv(color.mV);

            gGL.syncMatrices();
            glDrawElements(GL_TRIANGLES, phys_volume->mNumHullIndices, GL_UNSIGNED_SHORT, phys_volume->mHullIndices);
        }
        else
        {
            gGL.diffuseColor3f(1,0,1);
            drawBoxOutline(center, size);
            gMeshRepo.buildHull(volume_params, detail);
        }
        LLPrimitive::sVolumeManager->unrefVolume(phys_volume);
    }
    else if (type == LLPhysicsShapeBuilderUtil::PhysicsShapeSpecification::SCULPT)
    {
        //TODO: implement sculpted prim physics display
    }
    else
    {
        LL_ERRS() << "Unhandled type" << LL_ENDL;
    }

    gGL.popMatrix();
}

void renderPhysicsShapes(LLSpatialGroup* group, bool wireframe)
{
    for (OctreeNode::const_element_iter i = group->getDataBegin(); i != group->getDataEnd(); ++i)
    {
        LLDrawable* drawable = (LLDrawable*)(*i)->getDrawable();
        if(!drawable)
    {
            continue;
        }

        if (drawable->isSpatialBridge())
        {
            LLSpatialBridge* bridge = drawable->asPartition()->asBridge();

            if (bridge)
            {
                gGL.pushMatrix();
                gGL.multMatrix((F32*)bridge->mDrawable->getRenderMatrix().mMatrix);
                bridge->renderPhysicsShapes(wireframe);
                gGL.popMatrix();
            }
        }
        else
        {
            LLVOVolume* volume = drawable->getVOVolume();
            if (volume && !volume->isAttachment() && volume->getPhysicsShapeType() != LLViewerObject::PHYSICS_SHAPE_NONE )
            {
                if (!group->getSpatialPartition()->isBridge())
                {
                    gGL.pushMatrix();
                    LLVector3 trans = drawable->getRegion()->getOriginAgent();
                    gGL.translatef(trans.mV[0], trans.mV[1], trans.mV[2]);
                    renderPhysicsShape(drawable, volume, wireframe);
                    gGL.popMatrix();
                }
                else
                {
                    renderPhysicsShape(drawable, volume, wireframe);
                }
            }
            else
            {
#if 0
                LLViewerObject* object = drawable->getVObj();
                if (object && object->getPCode() == LLViewerObject::LL_VO_SURFACE_PATCH)
                {
                    gGL.pushMatrix();
                    gGL.multMatrix((F32*) object->getRegion()->mRenderMatrix.mMatrix);
                    //push face vertices for terrain
                    for (S32 i = 0; i < drawable->getNumFaces(); ++i)
                    {
                        LLFace* face = drawable->getFace(i);
                        if (face)
                        {
                            LLVertexBuffer* buff = face->getVertexBuffer();
                            if (buff)
                            {
                                glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);

                                buff->setBuffer();
                                gGL.diffuseColor4f(0.2f, 0.5f, 0.3f, 0.5f);
                                buff->draw(LLRender::TRIANGLES, buff->getNumIndices(), 0);

                                gGL.diffuseColor4f(0.2f, 1.f, 0.3f, 0.75f);
                                glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
                                buff->draw(LLRender::TRIANGLES, buff->getNumIndices(), 0);
                            }
                        }
                    }
                    gGL.popMatrix();
                }
#endif
            }
        }
    }
}

void renderTexturePriority(LLDrawable* drawable)
{
    for (int face=0; face<drawable->getNumFaces(); ++face)
    {
        LLFace *facep = drawable->getFace(face);

        LLVector4 cold(0,0,0.25f);
        LLVector4 hot(1,0.25f,0.25f);

        LLVector4 boost_cold(0,0,0,0);
        LLVector4 boost_hot(0,1,0,1);

        LLGLDisable blend(GL_BLEND);

        //LLViewerTexture* imagep = facep->getTexture();
        //if (imagep)
        if (facep)
        {

            //F32 vsize = imagep->mMaxVirtualSize;
            F32 vsize = facep->getPixelArea();

            if (vsize > sCurMaxTexPriority)
            {
                sCurMaxTexPriority = vsize;
            }

            F32 t = vsize/sLastMaxTexPriority;

            LLVector4 col = lerp(cold, hot, t);
            gGL.diffuseColor4fv(col.mV);
        }
        //else
        //{
        //  gGL.diffuseColor4f(1,0,1,1);
        //}

        LLVector4a center;
        center.setAdd(facep->mExtents[1],facep->mExtents[0]);
        center.mul(0.5f);
        LLVector4a size;
        size.setSub(facep->mExtents[1],facep->mExtents[0]);
        size.mul(0.5f);
        size.add(LLVector4a(0.01f));
        drawBox(center, size);

        /*S32 boost = imagep->getBoostLevel();
        if (boost>LLGLTexture::BOOST_NONE)
        {
            F32 t = (F32) boost / (F32) (LLGLTexture::BOOST_MAX_LEVEL-1);
            LLVector4 col = lerp(boost_cold, boost_hot, t);
            LLGLEnable blend_on(GL_BLEND);
            gGL.blendFunc(GL_SRC_ALPHA, GL_ONE);
            gGL.diffuseColor4fv(col.mV);
            drawBox(center, size);
            gGL.blendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
        }*/
    }
}

void renderPoints(LLDrawable* drawablep)
{
    LLGLDepthTest depth(GL_FALSE, GL_FALSE);
    if (drawablep->getNumFaces())
    {
        gGL.begin(LLRender::POINTS);
        gGL.diffuseColor3f(1,1,1);
        for (S32 i = 0; i < drawablep->getNumFaces(); i++)
        {
            LLFace * face = drawablep->getFace(i);
            if (face)
            {
                gGL.vertex3fv(face->mCenterLocal.mV);
            }
        }
        gGL.end();
    }
}

void renderTextureAnim(LLDrawInfo* params)
{
    if (!params->mTextureMatrix)
    {
        return;
    }

    LLGLEnable blend(GL_BLEND);
    gGL.diffuseColor4f(1,1,0,0.5f);
    pushVerts(params);
}

void renderBatchSize(LLDrawInfo* params)
{
    LLGLEnable offset(GL_POLYGON_OFFSET_FILL);
    glPolygonOffset(-1.f, 1.f);
    LLGLSLShader* old_shader = LLGLSLShader::sCurBoundShaderPtr;
    bool bind = false;
    if (params->mAvatar)
    {
        gGL.pushMatrix();
        gGL.loadMatrix(gGLModelView);
        bind = true;
        old_shader->mRiggedVariant->bind();
        LLRenderPass::uploadMatrixPalette(*params);
    }


    gGL.diffuseColor4ubv(params->getDebugColor().mV);
    pushVerts(params);

    if (bind)
    {
        gGL.popMatrix();
        old_shader->bind();
    }
}

void renderTexelDensity(LLDrawable* drawable)
{
    if (LLViewerTexture::sDebugTexelsMode == LLViewerTexture::DEBUG_TEXELS_OFF
        || LLViewerTexture::sCheckerBoardImagep.isNull())
    {
        return;
    }

    LLGLEnable _(GL_BLEND);

    LLMatrix4 checkerboard_matrix;
    S32 discard_level = -1;

    for (S32 f = 0; f < drawable->getNumFaces(); f++)
    {
        LLFace* facep = drawable->getFace(f);
        LLVertexBuffer* buffer = facep->getVertexBuffer();
        LLViewerTexture* texturep = facep->getTexture();

        if (texturep == NULL) continue;

        switch(LLViewerTexture::sDebugTexelsMode)
        {
        case LLViewerTexture::DEBUG_TEXELS_CURRENT:
            discard_level = -1;
            break;
        case LLViewerTexture::DEBUG_TEXELS_DESIRED:
            {
                LLViewerFetchedTexture* fetched_texturep = dynamic_cast<LLViewerFetchedTexture*>(texturep);
                discard_level = fetched_texturep ? fetched_texturep->getDesiredDiscardLevel() : -1;
                break;
            }
        default:
        case LLViewerTexture::DEBUG_TEXELS_FULL:
            discard_level = 0;
            break;
        }

        checkerboard_matrix.initScale(LLVector3((F32)texturep->getWidth(discard_level) / 8.f, (F32)texturep->getHeight(discard_level) / 8.f, 1.f));

        gGL.getTexUnit(0)->bind(LLViewerTexture::sCheckerBoardImagep, true);
        gGL.matrixMode(LLRender::MM_TEXTURE);
        gGL.loadMatrix((GLfloat*)&checkerboard_matrix.mMatrix);

        if (buffer && (facep->getGeomCount() >= 3))
        {
            buffer->setBuffer();
            U16 start = facep->getGeomStart();
            U16 end = start + facep->getGeomCount()-1;
            U32 count = facep->getIndicesCount();
            U16 offset = facep->getIndicesStart();
            buffer->drawRange(LLRender::TRIANGLES, start, end, count, offset);
        }

        gGL.loadIdentity();
        gGL.matrixMode(LLRender::MM_MODELVIEW);
    }

    //S32 num_textures = llmax(1, (S32)params->mTextureList.size());

    //for (S32 i = 0; i < num_textures; i++)
    //{
    //  LLViewerTexture* texturep = params->mTextureList.empty() ? params->mTexture.get() : params->mTextureList[i].get();
    //  if (texturep == NULL) continue;

    //  LLMatrix4 checkboard_matrix;
    //  S32 discard_level = -1;
    //  switch(LLViewerTexture::sDebugTexelsMode)
    //  {
    //  case LLViewerTexture::DEBUG_TEXELS_CURRENT:
    //      discard_level = -1;
    //      break;
    //  case LLViewerTexture::DEBUG_TEXELS_DESIRED:
    //      {
    //          LLViewerFetchedTexture* fetched_texturep = dynamic_cast<LLViewerFetchedTexture*>(texturep);
    //          discard_level = fetched_texturep ? fetched_texturep->getDesiredDiscardLevel() : -1;
    //          break;
    //      }
    //  default:
    //  case LLViewerTexture::DEBUG_TEXELS_FULL:
    //      discard_level = 0;
    //      break;
    //  }

    //  checkboard_matrix.initScale(LLVector3(texturep->getWidth(discard_level) / 8, texturep->getHeight(discard_level) / 8, 1.f));
    //  gGL.getTexUnit(i)->activate();

    //  glMatrixMode(GL_TEXTURE);
    //  glPushMatrix();
    //  glLoadIdentity();
    //  //gGL.matrixMode(LLRender::MM_TEXTURE);
    //  glLoadMatrixf((GLfloat*) checkboard_matrix.mMatrix);

    //  gGL.getTexUnit(i)->bind(LLViewerTexture::sCheckerBoardImagep, true);

    //  pushVerts(params, LLVertexBuffer::MAP_VERTEX | LLVertexBuffer::MAP_TEXCOORD0 | LLVertexBuffer::MAP_COLOR | LLVertexBuffer::MAP_NORMAL );

    //  glPopMatrix();
    //  glMatrixMode(GL_MODELVIEW);
    //  //gGL.matrixMode(LLRender::MM_MODELVIEW);
    //}
}


void renderLights(LLDrawable* drawablep)
{
    if (!drawablep->isLight())
    {
        return;
    }

    if (drawablep->getNumFaces())
    {
        LLGLEnable blend(GL_BLEND);
        gGL.diffuseColor4f(0,1,1,0.5f);

        for (S32 i = 0; i < drawablep->getNumFaces(); i++)
        {
            LLFace * face = drawablep->getFace(i);
            if (face)
            {
                pushVerts(face);
            }
        }

        const LLVector4a* ext = drawablep->getSpatialExtents();

        LLVector4a pos;
        pos.setAdd(ext[0], ext[1]);
        pos.mul(0.5f);
        LLVector4a size;
        size.setSub(ext[1], ext[0]);
        size.mul(0.5f);

        {
            LLGLDepthTest depth(GL_FALSE, GL_TRUE);
            gGL.diffuseColor4f(1,1,1,1);
            drawBoxOutline(pos, size);
        }

        gGL.diffuseColor4f(1,1,0,1);
        F32 rad = drawablep->getVOVolume()->getLightRadius();
        drawBoxOutline(pos, LLVector4a(rad));
    }
}

class LLRenderOctreeRaycast : public LLOctreeTriangleRayIntersect
{
public:
    LLRenderOctreeRaycast(const LLVector4a& start, const LLVector4a& dir, F32* closest_t)
        : LLOctreeTriangleRayIntersect(start, dir, nullptr, closest_t, NULL, NULL, NULL, NULL)
    {

    }

    void visit(const LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>* branch)
    {
        LLVolumeOctreeListener* vl = (LLVolumeOctreeListener*) branch->getListener(0);

        LLVector3 center, size;

        if (branch->isEmpty())
        {
            gGL.diffuseColor3f(1.f,0.2f,0.f);
            center.set(branch->getCenter().getF32ptr());
            size.set(branch->getSize().getF32ptr());
        }
        else
        {
            gGL.diffuseColor3f(0.75f, 1.f, 0.f);
            center.set(vl->mBounds[0].getF32ptr());
            size.set(vl->mBounds[1].getF32ptr());
        }

        drawBoxOutline(center, size);

        for (U32 i = 0; i < 2; i++)
        {
            LLGLDepthTest depth(GL_TRUE, GL_FALSE, i == 1 ? GL_LEQUAL : GL_GREATER);

            if (i == 1)
            {
                gGL.diffuseColor4f(0,1,1,0.5f);
            }
            else
            {
                gGL.diffuseColor4f(0,0.5f,0.5f, 0.25f);
                drawBoxOutline(center, size);
            }

            if (i == 1)
            {
                gGL.flush();
                glLineWidth(3.f);
            }

            gGL.begin(LLRender::TRIANGLES);
            for (LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>::const_element_iter iter = branch->getDataBegin();
                    iter != branch->getDataEnd();
                    ++iter)
            {
                const LLVolumeTriangle* tri = *iter;

                gGL.vertex3fv(tri->mV[0]->getF32ptr());
                gGL.vertex3fv(tri->mV[1]->getF32ptr());
                gGL.vertex3fv(tri->mV[2]->getF32ptr());
            }
            gGL.end();

            if (i == 1)
            {
                gGL.flush();
                glLineWidth(1.f);
            }
        }
    }
};

void renderOctreeRaycast(const LLVector4a& start, const LLVector4a& end, const LLVolumeOctree* octree)
{
    F32 t = 1.f;
    LLRenderOctreeRaycast render(start, end, &t);
    render.traverse(octree);
}

void renderRaycast(LLDrawable* drawablep)
{
    if (drawablep->getNumFaces())
    {
        LLGLEnable blend(GL_BLEND);
        gGL.diffuseColor4f(0,1,1,0.5f);

        LLVOVolume* vobj = drawablep->getVOVolume();
        if (vobj && !vobj->isDead())
        {
            //glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
            //pushVerts(drawablep->getFace(gDebugRaycastFaceHit), LLVertexBuffer::MAP_VERTEX);
            //glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);

            LLVolume* volume = vobj->getVolume();

            bool transform = true;
            if (drawablep->isState(LLDrawable::RIGGED))
            {
                volume = vobj->getRiggedVolume();
                transform = false;
            }

            if (volume)
            {
                LLVector3 trans = drawablep->getRegion()->getOriginAgent();

                for (S32 i = 0; i < volume->getNumVolumeFaces(); ++i)
                {
                    const LLVolumeFace& face = volume->getVolumeFace(i);

                    gGL.pushMatrix();
                    gGL.translatef(trans.mV[0], trans.mV[1], trans.mV[2]);
                    gGL.multMatrix((F32*) vobj->getRelativeXform().mMatrix);

                    LLVector4a start, end;
                    if (transform)
                    {
                        LLVector3 v_start(gDebugRaycastStart.getF32ptr());
                        LLVector3 v_end(gDebugRaycastEnd.getF32ptr());

                        v_start = vobj->agentPositionToVolume(v_start);
                        v_end = vobj->agentPositionToVolume(v_end);

                        start.load3(v_start.mV);
                        end.load3(v_end.mV);
                    }
                    else
                    {
                        start = gDebugRaycastStart;
                        end = gDebugRaycastEnd;
                    }

                    LLVector4a dir;
                    dir.setSub(end, start);

                    gGL.flush();
                    glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);

                    {
                        //render face positions
                        //gGL.diffuseColor4f(0,1,1,0.5f);
                        //LLVertexBuffer::drawElements(LLRender::TRIANGLES, face.mPositions, nullptr, face.mNumIndices, face.mIndices);
                    }

                    if (!volume->isUnique())
                    {
                        if (!face.getOctree())
                        {
                            ((LLVolumeFace*) &face)->createOctree();
                        }

                        renderOctreeRaycast(start, end, face.getOctree());
                    }

                    gGL.popMatrix();
                    glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
                }
            }
        }
        else if (drawablep->isAvatar())
        {
            if (drawablep->getVObj() == gDebugRaycastObject)
            {
                LLGLDepthTest depth(GL_FALSE);
                LLVOAvatar* av = (LLVOAvatar*) drawablep->getVObj().get();
                av->renderCollisionVolumes();
            }
        }

        if (drawablep->getVObj() == gDebugRaycastObject)
        {
            // draw intersection point
            gGL.pushMatrix();
            gGL.loadMatrix(gGLModelView);
            LLVector3 translate(gDebugRaycastIntersection.getF32ptr());
            gGL.translatef(translate.mV[0], translate.mV[1], translate.mV[2]);
            LLCoordFrame orient;
            LLVector4a debug_binormal;

            debug_binormal.setCross3(gDebugRaycastNormal, gDebugRaycastTangent);
            debug_binormal.mul(gDebugRaycastTangent.getF32ptr()[3]);

            LLVector3 normal(gDebugRaycastNormal.getF32ptr());
            LLVector3 binormal(debug_binormal.getF32ptr());

            orient.lookDir(normal, binormal);
            LLMatrix4 rotation;
            orient.getRotMatrixToParent(rotation);
            gGL.multMatrix((float*)rotation.mMatrix);

            gGL.diffuseColor4f(1,0,0,0.5f);
            drawBox(LLVector3(0, 0, 0), LLVector3(0.1f, 0.022f, 0.022f));
            gGL.diffuseColor4f(0,1,0,0.5f);
            drawBox(LLVector3(0, 0, 0), LLVector3(0.021f, 0.1f, 0.021f));
            gGL.diffuseColor4f(0,0,1,0.5f);
            drawBox(LLVector3(0, 0, 0), LLVector3(0.02f, 0.02f, 0.1f));
            gGL.popMatrix();

            // draw bounding box of prim
            const LLVector4a* ext = drawablep->getSpatialExtents();

            LLVector4a pos;
            pos.setAdd(ext[0], ext[1]);
            pos.mul(0.5f);
            LLVector4a size;
            size.setSub(ext[1], ext[0]);
            size.mul(0.5f);

            LLGLDepthTest depth(GL_FALSE, GL_TRUE);
            gGL.diffuseColor4f(0,0.5f,0.5f,1);
            drawBoxOutline(pos, size);
        }
    }
}


void renderAvatarCollisionVolumes(LLVOAvatar* avatar)
{
    avatar->renderCollisionVolumes();
}

void renderAvatarBones(LLVOAvatar* avatar)
{
    avatar->renderBones();
}

void renderAgentTarget(LLVOAvatar* avatar)
{
    // render these for self only (why, i don't know)
    if (avatar->isSelf())
    {
        renderCrossHairs(avatar->getPositionAgent(), 0.2f, LLColor4(1, 0, 0, 0.8f));
        renderCrossHairs(avatar->mDrawable->getPositionAgent(), 0.2f, LLColor4(0, 1, 0, 0.8f));
        renderCrossHairs(avatar->mRoot->getWorldPosition(), 0.2f, LLColor4(1, 1, 1, 0.8f));
        renderCrossHairs(avatar->mPelvisp->getWorldPosition(), 0.2f, LLColor4(0, 0, 1, 0.8f));
    }
}

static void setTextureAreaDebugText(LLDrawable* drawablep)
{
    LLVOVolume* vobjp = drawablep->getVOVolume();

    if (vobjp)
    {
        if (drawablep->mDistanceWRTCamera < 32.f)
        {
            std::ostringstream str;

            //for (S32 i = 0; i < vobjp->getNumTEs(); ++i)
            S32 i = 0;
            {
                if (i < drawablep->getNumFaces())
                {
                    LLFace* facep = drawablep->getFace(i);

                    if (facep)
                    {
                        LLViewerTexture* imagep = facep->getTexture();

                        if (imagep)
                        {
                            str << llformat("D - %.2f", sqrtf(imagep->getMaxVirtualSize()));
                        }

                        imagep = vobjp->getTENormalMap(i);

                        if (imagep && imagep != LLViewerFetchedTexture::sDefaultImagep)
                        {
                            str << llformat("\nN - %.2f", sqrtf(imagep->getMaxVirtualSize()));
                        }

                        imagep = vobjp->getTESpecularMap(i);

                        if (imagep && imagep != LLViewerFetchedTexture::sDefaultImagep)
                        {
                            str << llformat("\nS - %.2f", sqrtf(imagep->getMaxVirtualSize()));
                        }

                        str << "\n\n";
                    }

                    vobjp->setDebugText(str.str());
                }
            }
        }
        else
        {
            vobjp->setDebugText(".");
        }
    }
}

class LLOctreeRenderNonOccluded : public OctreeTraveler
{
public:
    LLCamera* mCamera;
    LLOctreeRenderNonOccluded(LLCamera* camera): mCamera(camera) {}

    virtual void traverse(const OctreeNode* node)
    {
        LLSpatialGroup* group = (LLSpatialGroup*) node->getListener(0);

        const LLVector4a* bounds = group->getBounds();
        if (!mCamera || mCamera->AABBInFrustumNoFarClip(bounds[0], bounds[1]))
        {
            node->accept(this);
            stop_glerror();

            for (U32 i = 0; i < node->getChildCount(); i++)
            {
                traverse(node->getChild(i));
                stop_glerror();
            }

            //draw tight fit bounding boxes for spatial group
            if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_OCTREE))
            {
                group->rebuildGeom();
                group->rebuildMesh();

                renderOctree(group);
                stop_glerror();
            }
        }
    }

    virtual void visit(const OctreeNode* branch)
    {
        LLSpatialGroup* group = (LLSpatialGroup*) branch->getListener(0);
        const LLVector4a* bounds = group->getBounds();
        if (group->hasState(LLSpatialGroup::GEOM_DIRTY) || (mCamera && !mCamera->AABBInFrustumNoFarClip(bounds[0], bounds[1])))
        {
            return;
        }

        group->rebuildGeom();
        group->rebuildMesh();

        if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_BBOXES))
        {
            if (!group->isEmpty())
            {
                gGL.diffuseColor3f(0,0,1);
                const LLVector4a* obj_bounds = group->getObjectBounds();
                drawBoxOutline(obj_bounds[0], obj_bounds[1]);
            }
        }

        for (OctreeNode::const_element_iter i = branch->getDataBegin(); i != branch->getDataEnd(); ++i)
        {
            LLDrawable* drawable = (LLDrawable*)(*i)->getDrawable();
            if(!drawable || drawable->isDead())
        {
                continue;
            }

            if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_BBOXES))
            {
                renderBoundingBox(drawable);
            }

            if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_NORMALS))
            {
                renderNormals(drawable);
            }

            if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_TEXTURE_AREA))
            {
                setTextureAreaDebugText(drawable);
            }

            /*if (drawable->getVOVolume() && gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_TEXTURE_PRIORITY))
            {
                renderTexturePriority(drawable);
            }*/

            if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_POINTS))
            {
                renderPoints(drawable);
            }

            if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_LIGHTS))
            {
                renderLights(drawable);
            }

            if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_RAYCAST))
            {
                renderRaycast(drawable);
            }
            if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_UPDATE_TYPE))
            {
                renderUpdateType(drawable);
            }
            if(gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_TEXEL_DENSITY))
            {
                renderTexelDensity(drawable);
            }

            LLVOAvatar* avatar = dynamic_cast<LLVOAvatar*>(drawable->getVObj().get());

            if (avatar && gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_AVATAR_VOLUME))
            {
                renderAvatarCollisionVolumes(avatar);
            }

            if (avatar && gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_AVATAR_JOINTS))
            {
                renderAvatarBones(avatar);
            }

            if (avatar && gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_AGENT_TARGET))
            {
                renderAgentTarget(avatar);
            }

#if 0
            if (gDebugGL)
            {
                for (U32 i = 0; i < drawable->getNumFaces(); ++i)
                {
                    LLFace* facep = drawable->getFace(i);
                    if (facep)
                    {
                        U8 index = facep->getTextureIndex();
                        if (facep->mDrawInfo)
                        {
                            if (index < FACE_DO_NOT_BATCH_TEXTURES)
                            {
                                if (facep->mDrawInfo->mTextureList.size() <= index)
                                {
                                    LL_ERRS() << "Face texture index out of bounds." << LL_ENDL;
                                }
                                else if (facep->mDrawInfo->mTextureList[index] != facep->getTexture())
                                {
                                    LL_ERRS() << "Face texture index incorrect." << LL_ENDL;
                                }
                            }
                        }
                    }
                }
            }
#endif
        }

        for (LLSpatialGroup::draw_map_t::iterator i = group->mDrawMap.begin(); i != group->mDrawMap.end(); ++i)
        {
            LLSpatialGroup::drawmap_elem_t& draw_vec = i->second;
            for (LLSpatialGroup::drawmap_elem_t::iterator j = draw_vec.begin(); j != draw_vec.end(); ++j)
            {
                LLDrawInfo* draw_info = *j;
                if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_TEXTURE_ANIM))
                {
                    renderTextureAnim(draw_info);
                }
                if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_BATCH_SIZE))
                {
                    renderBatchSize(draw_info);
                }
            }
        }
    }
};

class LLOctreeRenderXRay : public OctreeTraveler
{
public:
    LLCamera* mCamera;
    LLOctreeRenderXRay(LLCamera* camera): mCamera(camera) {}

    virtual void traverse(const OctreeNode* node)
    {
        LLSpatialGroup* group = (LLSpatialGroup*) node->getListener(0);

        const LLVector4a* bounds = group->getBounds();
        if (!mCamera || mCamera->AABBInFrustumNoFarClip(bounds[0], bounds[1]))
        {
            node->accept(this);
            stop_glerror();

            for (U32 i = 0; i < node->getChildCount(); i++)
            {
                traverse(node->getChild(i));
                stop_glerror();
            }

            //render visibility wireframe
            if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_OCCLUSION))
            {
                group->rebuildGeom();
                group->rebuildMesh();

                gGL.flush();
                gGL.pushMatrix();
                gGLLastMatrix = NULL;
                gGL.loadMatrix(gGLModelView);
                renderXRay(group, mCamera);
                stop_glerror();
                gGLLastMatrix = NULL;
                gGL.popMatrix();
            }
        }
    }

    virtual void visit(const OctreeNode* node) {}

};

class LLOctreeRenderPhysicsShapes : public OctreeTraveler
{
public:
    LLCamera* mCamera;
    bool mWireframe;

    LLOctreeRenderPhysicsShapes(LLCamera* camera, bool wireframe): mCamera(camera), mWireframe(wireframe) {}

    virtual void traverse(const OctreeNode* node)
    {
        LLSpatialGroup* group = (LLSpatialGroup*) node->getListener(0);

        const LLVector4a* bounds = group->getBounds();
        if (!mCamera || mCamera->AABBInFrustumNoFarClip(bounds[0], bounds[1]))
        {
            node->accept(this);
            stop_glerror();

            for (U32 i = 0; i < node->getChildCount(); i++)
            {
                traverse(node->getChild(i));
                stop_glerror();
            }

            group->rebuildGeom();
            group->rebuildMesh();

            renderPhysicsShapes(group, mWireframe);
        }
    }

    virtual void visit(const OctreeNode* branch)
    {

    }
};

class LLOctreePushBBoxVerts : public OctreeTraveler
{
public:
    LLCamera* mCamera;
    LLOctreePushBBoxVerts(LLCamera* camera): mCamera(camera) {}

    virtual void traverse(const OctreeNode* node)
    {
        LLSpatialGroup* group = (LLSpatialGroup*) node->getListener(0);

        const LLVector4a* bounds = group->getBounds();
        if (!mCamera || mCamera->AABBInFrustum(bounds[0], bounds[1]))
        {
            node->accept(this);

            for (U32 i = 0; i < node->getChildCount(); i++)
            {
                traverse(node->getChild(i));
            }
        }
    }

    virtual void visit(const OctreeNode* branch)
    {
        LLSpatialGroup* group = (LLSpatialGroup*) branch->getListener(0);

        const LLVector4a* bounds = group->getBounds();
        if (group->hasState(LLSpatialGroup::GEOM_DIRTY) || (mCamera && !mCamera->AABBInFrustumNoFarClip(bounds[0], bounds[1])))
        {
            return;
        }

        for (OctreeNode::const_element_iter i = branch->getDataBegin(); i != branch->getDataEnd(); ++i)
        {
            LLDrawable* drawable = (LLDrawable*)(*i)->getDrawable();
            if(!drawable)
        {
                continue;
            }
            renderBoundingBox(drawable, false);
        }
    }
};

void LLSpatialPartition::renderIntersectingBBoxes(LLCamera* camera)
{
    LLOctreePushBBoxVerts pusher(camera);
    pusher.traverse(mOctree);
}

class LLOctreeStateCheck : public OctreeTraveler
{
public:
    U32 mInheritedMask[LLViewerCamera::NUM_CAMERAS];

    LLOctreeStateCheck()
    {
        for (U32 i = 0; i < LLViewerCamera::NUM_CAMERAS; i++)
        {
            mInheritedMask[i] = 0;
        }
    }

    virtual void traverse(const OctreeNode* node)
    {
        LLSpatialGroup* group = (LLSpatialGroup*) node->getListener(0);

        node->accept(this);


        U32 temp[LLViewerCamera::NUM_CAMERAS];

        for (U32 i = 0; i < LLViewerCamera::NUM_CAMERAS; i++)
        {
            temp[i] = mInheritedMask[i];
            mInheritedMask[i] |= group->mOcclusionState[i] & LLSpatialGroup::OCCLUDED;
        }

        for (U32 i = 0; i < node->getChildCount(); i++)
        {
            traverse(node->getChild(i));
        }

        for (U32 i = 0; i < LLViewerCamera::NUM_CAMERAS; i++)
        {
            mInheritedMask[i] = temp[i];
        }
    }


    virtual void visit(const OctreeNode* state)
    {
        LLSpatialGroup* group = (LLSpatialGroup*) state->getListener(0);

        for (U32 i = 0; i < LLViewerCamera::NUM_CAMERAS; i++)
        {
            if (mInheritedMask[i] && !(group->mOcclusionState[i] & mInheritedMask[i]))
            {
                LL_ERRS() << "Spatial group failed inherited mask test." << LL_ENDL;
            }
        }

        if (group->hasState(LLSpatialGroup::DIRTY))
        {
            assert_parent_state(group, LLSpatialGroup::DIRTY);
        }
    }

    void assert_parent_state(LLSpatialGroup* group, U32 state)
    {
        LLSpatialGroup* parent = group->getParent();
        while (parent)
        {
            if (!parent->hasState(state))
            {
                LL_ERRS() << "Spatial group failed parent state check." << LL_ENDL;
            }
            parent = parent->getParent();
        }
    }
};


void LLSpatialPartition::renderPhysicsShapes(bool wireframe)
{
    LLSpatialBridge* bridge = asBridge();
    LLCamera* camera = LLViewerCamera::getInstance();

    if (bridge)
    {
        camera = NULL;
    }

    gGL.flush();
    gGL.getTexUnit(0)->unbind(LLTexUnit::TT_TEXTURE);
    LLOctreeRenderPhysicsShapes render_physics(camera, wireframe);
    render_physics.traverse(mOctree);
    gGL.flush();
}

void LLSpatialPartition::renderDebug()
{
    if (!gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_OCTREE |
                                      LLPipeline::RENDER_DEBUG_OCCLUSION |
                                      LLPipeline::RENDER_DEBUG_LIGHTS |
                                      LLPipeline::RENDER_DEBUG_BATCH_SIZE |
                                      LLPipeline::RENDER_DEBUG_UPDATE_TYPE |
                                      LLPipeline::RENDER_DEBUG_BBOXES |
                                      LLPipeline::RENDER_DEBUG_NORMALS |
                                      LLPipeline::RENDER_DEBUG_POINTS |
                                      LLPipeline::RENDER_DEBUG_TEXTURE_AREA |
                                      LLPipeline::RENDER_DEBUG_TEXTURE_ANIM |
                                      LLPipeline::RENDER_DEBUG_RAYCAST |
                                      LLPipeline::RENDER_DEBUG_AVATAR_VOLUME |
                                      LLPipeline::RENDER_DEBUG_AVATAR_JOINTS |
                                      LLPipeline::RENDER_DEBUG_AGENT_TARGET |
                                      LLPipeline::RENDER_DEBUG_SHADOW_FRUSTA |
                                      LLPipeline::RENDER_DEBUG_TEXEL_DENSITY))
    {
        return;
    }

    gDebugProgram.bind();

    if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_TEXTURE_PRIORITY))
    {
        //sLastMaxTexPriority = lerp(sLastMaxTexPriority, sCurMaxTexPriority, gFrameIntervalSeconds);
        sLastMaxTexPriority = (F32) LLViewerCamera::getInstance()->getScreenPixelArea();
        sCurMaxTexPriority = 0.f;
    }

    LLGLDisable cullface(GL_CULL_FACE);
    LLGLEnable blend(GL_BLEND);
    gGL.setSceneBlendType(LLRender::BT_ALPHA);
    gGL.getTexUnit(0)->unbind(LLTexUnit::TT_TEXTURE);
    gPipeline.disableLights();

    LLSpatialBridge* bridge = asBridge();
    LLCamera* camera = LLViewerCamera::getInstance();

    if (bridge)
    {
        camera = NULL;
    }

    LLOctreeStateCheck checker;
    checker.traverse(mOctree);

    LLOctreeRenderNonOccluded render_debug(camera);
    render_debug.traverse(mOctree);

    if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_OCCLUSION))
    {
        {
            LLGLEnable cull(GL_CULL_FACE);

            LLGLEnable blend(GL_BLEND);
            LLGLDepthTest depth_under(GL_TRUE, GL_FALSE, GL_GREATER);
            glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
            gGL.diffuseColor4f(0.5f, 0.0f, 0, 0.25f);

            LLGLEnable offset(GL_POLYGON_OFFSET_LINE);
            glPolygonOffset(-1.f, -1.f);

            LLOctreeRenderXRay xray(camera);
            xray.traverse(mOctree);

            glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
        }
    }
    gDebugProgram.unbind();
}

void LLSpatialGroup::drawObjectBox(LLColor4 col)
{
    gGL.diffuseColor4fv(col.mV);
    LLVector4a size;
    size = mObjectBounds[1];
    size.mul(1.01f);
    size.add(LLVector4a(0.001f));
    drawBox(mObjectBounds[0], size);
}

bool LLSpatialPartition::isHUDPartition()
{
    return mPartitionType == LLViewerRegion::PARTITION_HUD ;
}

bool LLSpatialPartition::isVisible(const LLVector3& v)
{
    if (!LLViewerCamera::getInstance()->sphereInFrustum(v, 4.0f))
    {
        return false;
    }

    return true;
}

LL_ALIGN_PREFIX(16)
class LLOctreeIntersect : public LLOctreeTraveler<LLViewerOctreeEntry, LLPointer<LLViewerOctreeEntry>>
{
public:
    LL_ALIGN_16(LLVector4a mStart);
    LL_ALIGN_16(LLVector4a mEnd);

    S32       *mFaceHit;
    LLVector4a *mIntersection;
    LLVector2 *mTexCoord;
    LLVector4a *mNormal;
    LLVector4a *mTangent;
    LLDrawable* mHit;
    bool mPickTransparent;
    bool mPickRigged;
    bool mPickUnselectable;
    bool mPickReflectionProbe;

    LLOctreeIntersect(const LLVector4a& start, const LLVector4a& end, bool pick_transparent, bool pick_rigged, bool pick_unselectable, bool pick_reflection_probe,
                      S32* face_hit, LLVector4a* intersection, LLVector2* tex_coord, LLVector4a* normal, LLVector4a* tangent)
        : mStart(start),
          mEnd(end),
          mFaceHit(face_hit),
          mIntersection(intersection),
          mTexCoord(tex_coord),
          mNormal(normal),
          mTangent(tangent),
          mHit(NULL),
          mPickTransparent(pick_transparent),
          mPickRigged(pick_rigged),
          mPickUnselectable(pick_unselectable),
          mPickReflectionProbe(pick_reflection_probe)
    {
    }

    virtual void visit(const OctreeNode* branch)
    {
        for (OctreeNode::const_element_iter i = branch->getDataBegin(); i != branch->getDataEnd(); ++i)
        {
            check(*i);
        }
    }

    virtual LLDrawable* check(const OctreeNode* node)
    {
        node->accept(this);

        for (U32 i = 0; i < node->getChildCount(); i++)
        {
            const OctreeNode* child = node->getChild(i);
            LLVector3 res;

            LLSpatialGroup* group = (LLSpatialGroup*) child->getListener(0);

            LLVector4a size;
            LLVector4a center;

            const LLVector4a* bounds = group->getBounds();
            size = bounds[1];
            center = bounds[0];

            LLVector4a local_start = mStart;
            LLVector4a local_end   = mEnd;

            if (group->getSpatialPartition()->isBridge())
            {
                LLMatrix4 local_matrix = group->getSpatialPartition()->asBridge()->mDrawable->getRenderMatrix();
                local_matrix.invert();

                LLMatrix4a local_matrix4a;
                local_matrix4a.loadu(local_matrix);

                local_matrix4a.affineTransform(mStart, local_start);
                local_matrix4a.affineTransform(mEnd, local_end);
            }

            if (LLLineSegmentBoxIntersect(local_start, local_end, center, size))
            {
                check(child);
            }
        }

        return mHit;
    }

    virtual bool check(LLViewerOctreeEntry* entry)
    {
        LLDrawable* drawable = (LLDrawable*)entry->getDrawable();

        if (!drawable || !gPipeline.hasRenderType(drawable->getRenderType()) || !drawable->isVisible())
        {
            return false;
        }

        if (drawable->isSpatialBridge())
        {
            LLSpatialPartition *part = drawable->asPartition();
            LLSpatialBridge* bridge = part->asBridge();
            if (bridge && gPipeline.hasRenderType(bridge->mDrawableType))
            {
                check(part->mOctree);
            }
        }
        else
        {
            LLViewerObject* vobj = drawable->getVObj();

            if (vobj &&
                (!vobj->isReflectionProbe() || mPickReflectionProbe))
            {
                if (vobj->getClickAction() == CLICK_ACTION_IGNORE && !LLFloater::isVisible(gFloaterTools))
                {
                    return false;
                }

                LLVector4a intersection;
                bool skip_check = false;
                if (vobj->isAvatar())
                {
                    LLVOAvatar* avatar = (LLVOAvatar*) vobj;
                    if ((mPickRigged) || ((avatar->isSelf()) && (LLFloater::isVisible(gFloaterTools))))
                    {
                        LLViewerObject* hit = avatar->lineSegmentIntersectRiggedAttachments(mStart, mEnd, -1, mPickTransparent, mPickRigged, mPickUnselectable, mFaceHit, &intersection, mTexCoord, mNormal, mTangent);
                        if (hit)
                        {
                            mEnd = intersection;
                            if (mIntersection)
                            {
                                *mIntersection = intersection;
                            }

                            mHit = hit->mDrawable;
                            skip_check = true;
                        }

                    }
                }

                if (!skip_check && vobj->lineSegmentIntersect(mStart, mEnd, -1,
                    (mPickReflectionProbe && vobj->isReflectionProbe()) ? true : mPickTransparent, // always pick transparent when picking selection probe
                    mPickRigged, mPickUnselectable, mFaceHit, &intersection, mTexCoord, mNormal, mTangent))
                {
                    mEnd = intersection;  // shorten ray so we only find CLOSER hits
                    if (mIntersection)
                    {
                        *mIntersection = intersection;
                    }

                    mHit = vobj->mDrawable;
                }
            }
        }

        return false;
    }
} LL_ALIGN_POSTFIX(16);

LLDrawable* LLSpatialPartition::lineSegmentIntersect(const LLVector4a& start, const LLVector4a& end,
                                                     bool pick_transparent,
                                                     bool pick_rigged,
                                                     bool pick_unselectable,
                                                     bool pick_reflection_probe,
                                                     S32* face_hit,                   // return the face hit
                                                     LLVector4a* intersection,         // return the intersection point
                                                     LLVector2* tex_coord,            // return the texture coordinates of the intersection point
                                                     LLVector4a* normal,               // return the surface normal at the intersection point
                                                     LLVector4a* tangent            // return the surface tangent at the intersection point
    )

{
    LLOctreeIntersect intersect(start, end, pick_transparent, pick_rigged, pick_unselectable, pick_reflection_probe, face_hit, intersection, tex_coord, normal, tangent);
    LLDrawable* drawable = intersect.check(mOctree);

    return drawable;
}

LLDrawable* LLSpatialGroup::lineSegmentIntersect(const LLVector4a& start, const LLVector4a& end,
    bool pick_transparent,
    bool pick_rigged,
    bool pick_unselectable,
    bool pick_reflection_probe,
    S32* face_hit,                   // return the face hit
    LLVector4a* intersection,         // return the intersection point
    LLVector2* tex_coord,            // return the texture coordinates of the intersection point
    LLVector4a* normal,               // return the surface normal at the intersection point
    LLVector4a* tangent         // return the surface tangent at the intersection point
)

{
    LLOctreeIntersect intersect(start, end, pick_transparent, pick_rigged, pick_unselectable, pick_reflection_probe, face_hit, intersection, tex_coord, normal, tangent);
    LLDrawable* drawable = intersect.check(getOctreeNode());

    return drawable;
}

LLDrawInfo::LLDrawInfo(U16 start, U16 end, U32 count, U32 offset,
                       LLViewerTexture* texture, LLVertexBuffer* buffer,
                       bool fullbright, U8 bump)
:   mVertexBuffer(buffer),
    mTexture(texture),
    mStart(start),
    mEnd(end),
    mCount(count),
    mOffset(offset),
    mFullbright(fullbright),
    mBump(bump),
    mBlendFuncSrc(LLRender::BF_SOURCE_ALPHA),
    mBlendFuncDst(LLRender::BF_ONE_MINUS_SOURCE_ALPHA),
    mHasGlow(false),
    mEnvIntensity(0.0f),
    mAlphaMaskCutoff(0.5f)
{
    mVertexBuffer->validateRange(mStart, mEnd, mCount, mOffset);
}

LLDrawInfo::~LLDrawInfo()
{
    if (gDebugGL)
    {
        gPipeline.checkReferences(this);
    }
}

LLColor4U LLDrawInfo::getDebugColor() const
{
    LLColor4U color;

    LLCRC hash;
    hash.update((U8*)this + sizeof(S32), sizeof(LLDrawInfo) - sizeof(S32));

    *((U32*) color.mV) = hash.getCRC();

    color.mV[3] = 200;

    return color;
}

void LLDrawInfo::validate()
{
    mVertexBuffer->validateRange(mStart, mEnd, mCount, mOffset);
}

U64 LLDrawInfo::getSkinHash()
{
    return mSkinInfo ? mSkinInfo->mHash : 0;
}

LLCullResult::LLCullResult()
{
    mVisibleGroupsAllocated = 0;
    mAlphaGroupsAllocated = 0;
    mRiggedAlphaGroupsAllocated = 0;
    mOcclusionGroupsAllocated = 0;
    mDrawableGroupsAllocated = 0;
    mVisibleListAllocated = 0;
    mVisibleBridgeAllocated = 0;

    mVisibleGroups.clear();
    mVisibleGroups.push_back(NULL);
    mVisibleGroupsEnd = &mVisibleGroups[0];
    mAlphaGroups.clear();
    mAlphaGroups.push_back(NULL);
    mAlphaGroupsEnd = &mAlphaGroups[0];
    mRiggedAlphaGroups.clear();
    mRiggedAlphaGroups.push_back(NULL);
    mRiggedAlphaGroupsEnd = &mRiggedAlphaGroups[0];
    mOcclusionGroups.clear();
    mOcclusionGroups.push_back(NULL);
    mOcclusionGroupsEnd = &mOcclusionGroups[0];
    mDrawableGroups.clear();
    mDrawableGroups.push_back(NULL);
    mDrawableGroupsEnd = &mDrawableGroups[0];
    mVisibleList.clear();
    mVisibleList.push_back(NULL);
    mVisibleListEnd = &mVisibleList[0];
    mVisibleBridge.clear();
    mVisibleBridge.push_back(NULL);
    mVisibleBridgeEnd = &mVisibleBridge[0];

    for (U32 i = 0; i < LLRenderPass::NUM_RENDER_TYPES; i++)
    {
        mRenderMap[i].clear();
        mRenderMap[i].push_back(NULL);
        mRenderMapEnd[i] = &mRenderMap[i][0];
        mRenderMapAllocated[i] = 0;
    }

    clear();
}

template <class T, class V>
void LLCullResult::pushBack(T& head, U32& count, V* val)
{
    head[count] = val;
    head.push_back(NULL);
    count++;
}

void LLCullResult::clear()
{
    mVisibleGroupsSize = 0;
    mVisibleGroupsEnd = &mVisibleGroups[0];

    mAlphaGroupsSize = 0;
    mAlphaGroupsEnd = &mAlphaGroups[0];

    mRiggedAlphaGroupsSize = 0;
    mRiggedAlphaGroupsEnd = &mRiggedAlphaGroups[0];

    mOcclusionGroupsSize = 0;
    mOcclusionGroupsEnd = &mOcclusionGroups[0];

    mDrawableGroupsSize = 0;
    mDrawableGroupsEnd = &mDrawableGroups[0];

    mVisibleListSize = 0;
    mVisibleListEnd = &mVisibleList[0];

    mVisibleBridgeSize = 0;
    mVisibleBridgeEnd = &mVisibleBridge[0];


    for (U32 i = 0; i < LLRenderPass::NUM_RENDER_TYPES; i++)
    {
        for (U32 j = 0; j < mRenderMapSize[i]; j++)
        {
            mRenderMap[i][j] = 0;
        }
        mRenderMapSize[i] = 0;
        mRenderMapEnd[i] = &(mRenderMap[i][0]);
    }
}

LLCullResult::sg_iterator LLCullResult::beginVisibleGroups()
{
    return &mVisibleGroups[0];
}

LLCullResult::sg_iterator LLCullResult::endVisibleGroups()
{
    return mVisibleGroupsEnd;
}

LLCullResult::sg_iterator LLCullResult::beginAlphaGroups()
{
    return &mAlphaGroups[0];
}

LLCullResult::sg_iterator LLCullResult::endAlphaGroups()
{
    return mAlphaGroupsEnd;
}

LLCullResult::sg_iterator LLCullResult::beginRiggedAlphaGroups()
{
    return &mRiggedAlphaGroups[0];
}

LLCullResult::sg_iterator LLCullResult::endRiggedAlphaGroups()
{
    return mRiggedAlphaGroupsEnd;
}

LLCullResult::sg_iterator LLCullResult::beginOcclusionGroups()
{
    return &mOcclusionGroups[0];
}

LLCullResult::sg_iterator LLCullResult::endOcclusionGroups()
{
    return mOcclusionGroupsEnd;
}

LLCullResult::sg_iterator LLCullResult::beginDrawableGroups()
{
    return &mDrawableGroups[0];
}

LLCullResult::sg_iterator LLCullResult::endDrawableGroups()
{
    return mDrawableGroupsEnd;
}

LLCullResult::drawable_iterator LLCullResult::beginVisibleList()
{
    return &mVisibleList[0];
}

LLCullResult::drawable_iterator LLCullResult::endVisibleList()
{
    return mVisibleListEnd;
}

LLCullResult::bridge_iterator LLCullResult::beginVisibleBridge()
{
    return &mVisibleBridge[0];
}

LLCullResult::bridge_iterator LLCullResult::endVisibleBridge()
{
    return mVisibleBridgeEnd;
}

LLCullResult::drawinfo_iterator LLCullResult::beginRenderMap(U32 type)
{
    return &mRenderMap[type][0];
}

LLCullResult::drawinfo_iterator LLCullResult::endRenderMap(U32 type)
{
    return mRenderMapEnd[type];
}

void LLCullResult::pushVisibleGroup(LLSpatialGroup* group)
{
    if (mVisibleGroupsSize < mVisibleGroupsAllocated)
    {
        mVisibleGroups[mVisibleGroupsSize] = group;
    }
    else
    {
        pushBack(mVisibleGroups, mVisibleGroupsAllocated, group);
    }
    ++mVisibleGroupsSize;
    mVisibleGroupsEnd = &mVisibleGroups[mVisibleGroupsSize];
}

void LLCullResult::pushAlphaGroup(LLSpatialGroup* group)
{
    if (mAlphaGroupsSize < mAlphaGroupsAllocated)
    {
        mAlphaGroups[mAlphaGroupsSize] = group;
    }
    else
    {
        pushBack(mAlphaGroups, mAlphaGroupsAllocated, group);
    }
    ++mAlphaGroupsSize;
    mAlphaGroupsEnd = &mAlphaGroups[mAlphaGroupsSize];
}

void LLCullResult::pushRiggedAlphaGroup(LLSpatialGroup* group)
{
    if (mRiggedAlphaGroupsSize < mRiggedAlphaGroupsAllocated)
    {
        mRiggedAlphaGroups[mRiggedAlphaGroupsSize] = group;
    }
    else
    {
        pushBack(mRiggedAlphaGroups, mRiggedAlphaGroupsAllocated, group);
    }
    ++mRiggedAlphaGroupsSize;
    mRiggedAlphaGroupsEnd = &mRiggedAlphaGroups[mRiggedAlphaGroupsSize];
}

void LLCullResult::pushOcclusionGroup(LLSpatialGroup* group)
{
    if (mOcclusionGroupsSize < mOcclusionGroupsAllocated)
    {
        mOcclusionGroups[mOcclusionGroupsSize] = group;
    }
    else
    {
        pushBack(mOcclusionGroups, mOcclusionGroupsAllocated, group);
    }
    ++mOcclusionGroupsSize;
    mOcclusionGroupsEnd = &mOcclusionGroups[mOcclusionGroupsSize];
}

void LLCullResult::pushDrawableGroup(LLSpatialGroup* group)
{
#if LL_DEBUG_CULL_RESULT
    // group must NOT be in the drawble groups list already
    llassert(std::find(&mDrawableGroups[0], mDrawableGroupsEnd, group) == mDrawableGroupsEnd);
#endif
    if (mDrawableGroupsSize < mDrawableGroupsAllocated)
    {
        mDrawableGroups[mDrawableGroupsSize] = group;
    }
    else
    {
        pushBack(mDrawableGroups, mDrawableGroupsAllocated, group);
    }
    ++mDrawableGroupsSize;
    mDrawableGroupsEnd = &mDrawableGroups[mDrawableGroupsSize];
}

void LLCullResult::pushDrawable(LLDrawable* drawable)
{
#if LL_DEBUG_CULL_RESULT
    // drawable must NOT be in the visible list already
    llassert(std::find(&mVisibleList[0], mVisibleListEnd, drawable) == mVisibleListEnd);
#endif
    if (mVisibleListSize < mVisibleListAllocated)
    {
        mVisibleList[mVisibleListSize] = drawable;
    }
    else
    {
        pushBack(mVisibleList, mVisibleListAllocated, drawable);
    }
    ++mVisibleListSize;
    mVisibleListEnd = &mVisibleList[mVisibleListSize];
}

void LLCullResult::pushBridge(LLSpatialBridge* bridge)
{
    if (mVisibleBridgeSize < mVisibleBridgeAllocated)
    {
        mVisibleBridge[mVisibleBridgeSize] = bridge;
    }
    else
    {
        pushBack(mVisibleBridge, mVisibleBridgeAllocated, bridge);
    }
    ++mVisibleBridgeSize;
    mVisibleBridgeEnd = &mVisibleBridge[mVisibleBridgeSize];
}

void LLCullResult::pushDrawInfo(U32 type, LLDrawInfo* draw_info)
{
    if (mRenderMapSize[type] < mRenderMapAllocated[type])
    {
        mRenderMap[type][mRenderMapSize[type]] = draw_info;
    }
    else
    {
        pushBack(mRenderMap[type], mRenderMapAllocated[type], draw_info);
    }
    ++mRenderMapSize[type];
    mRenderMapEnd[type] = &(mRenderMap[type][mRenderMapSize[type]]);
}


void LLCullResult::assertDrawMapsEmpty()
{
    for (U32 i = 0; i < LLRenderPass::NUM_RENDER_TYPES; i++)
    {
        if (mRenderMapSize[i] != 0)
        {
            LL_ERRS() << "Stale LLDrawInfo's in LLCullResult!"
                << " (mRenderMapSize[" << i << "] = " << mRenderMapSize[i] << ")" << LL_ENDL;
        }
    }
}