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

#ifndef LL_LLVOLUME_H
#define LL_LLVOLUME_H

#include <iostream>

class LLProfileParams;
class LLPathParams;
class LLVolumeParams;
class LLProfile;
class LLPath;

template<class T> class LLPointer;
template <class T, typename T_PTR> class LLOctreeNode;

class LLVolumeFace;
class LLVolume;
class LLVolumeTriangle;

#include "lluuid.h"
#include "v4color.h"
//#include "vmath.h"
#include "v2math.h"
#include "v3math.h"
#include "v3dmath.h"
#include "v4math.h"
#include "llvector4a.h"
#include "llmatrix4a.h"
#include "llquaternion.h"
#include "llstrider.h"
#include "v4coloru.h"
#include "llrefcount.h"
#include "llpointer.h"
#include "llfile.h"
#include "llalignedarray.h"
#include "llrigginginfo.h"

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

constexpr S32 MIN_DETAIL_FACES = 6;
constexpr S32 MIN_LOD = 0;
constexpr S32 MAX_LOD = 3;

// These are defined here but are not enforced at this level,
// rather they are here for the convenience of code that uses
// the LLVolume class.
constexpr F32 MIN_VOLUME_PROFILE_WIDTH 	= 0.05f;
constexpr F32 MIN_VOLUME_PATH_WIDTH 	= 0.05f;

constexpr F32 CUT_QUANTA    = 0.00002f;
constexpr F32 SCALE_QUANTA  = 0.01f;
constexpr F32 SHEAR_QUANTA  = 0.01f;
constexpr F32 TAPER_QUANTA  = 0.01f;
constexpr F32 REV_QUANTA    = 0.015f;
constexpr F32 HOLLOW_QUANTA = 0.00002f;

constexpr S32 MAX_VOLUME_TRIANGLE_INDICES = 10000;

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

// useful masks
constexpr LLPCode LL_PCODE_HOLLOW_MASK 	= 0x80;		// has a thickness
constexpr LLPCode LL_PCODE_SEGMENT_MASK = 0x40;		// segments (1 angle)
constexpr LLPCode LL_PCODE_PATCH_MASK 	= 0x20;		// segmented segments (2 angles)
constexpr LLPCode LL_PCODE_HEMI_MASK 	= 0x10;		// half-primitives get their own type per PR's dictum
constexpr LLPCode LL_PCODE_BASE_MASK 	= 0x0F;

	// primitive shapes
constexpr LLPCode	LL_PCODE_CUBE 			= 1;
constexpr LLPCode	LL_PCODE_PRISM 			= 2;
constexpr LLPCode	LL_PCODE_TETRAHEDRON 	= 3;
constexpr LLPCode	LL_PCODE_PYRAMID 		= 4;
constexpr LLPCode	LL_PCODE_CYLINDER 		= 5;
constexpr LLPCode	LL_PCODE_CONE 			= 6;
constexpr LLPCode	LL_PCODE_SPHERE 		= 7;
constexpr LLPCode	LL_PCODE_TORUS 			= 8;
constexpr LLPCode	LL_PCODE_VOLUME			= 9;

	// surfaces
//constexpr LLPCode	LL_PCODE_SURFACE_TRIANGLE 	= 10;
//constexpr LLPCode	LL_PCODE_SURFACE_SQUARE 	= 11;
//constexpr LLPCode	LL_PCODE_SURFACE_DISC 		= 12;

constexpr LLPCode	LL_PCODE_APP				= 14; // App specific pcode (for viewer/sim side only objects)
constexpr LLPCode	LL_PCODE_LEGACY				= 15;

// Pcodes for legacy objects
//constexpr LLPCode	LL_PCODE_LEGACY_ATOR =				0x10 | LL_PCODE_LEGACY; // ATOR
constexpr LLPCode	LL_PCODE_LEGACY_AVATAR =			0x20 | LL_PCODE_LEGACY; // PLAYER
//constexpr LLPCode	LL_PCODE_LEGACY_BIRD =				0x30 | LL_PCODE_LEGACY; // BIRD
//constexpr LLPCode	LL_PCODE_LEGACY_DEMON =				0x40 | LL_PCODE_LEGACY; // DEMON
constexpr LLPCode	LL_PCODE_LEGACY_GRASS =				0x50 | LL_PCODE_LEGACY; // GRASS
constexpr LLPCode	LL_PCODE_TREE_NEW =					0x60 | LL_PCODE_LEGACY; // new trees
//constexpr LLPCode	LL_PCODE_LEGACY_ORACLE =			0x70 | LL_PCODE_LEGACY; // ORACLE
constexpr LLPCode	LL_PCODE_LEGACY_PART_SYS =			0x80 | LL_PCODE_LEGACY; // PART_SYS
constexpr LLPCode	LL_PCODE_LEGACY_ROCK =				0x90 | LL_PCODE_LEGACY; // ROCK
//constexpr LLPCode	LL_PCODE_LEGACY_SHOT =				0xA0 | LL_PCODE_LEGACY; // BASIC_SHOT
//constexpr LLPCode	LL_PCODE_LEGACY_SHOT_BIG =			0xB0 | LL_PCODE_LEGACY;
//constexpr LLPCode	LL_PCODE_LEGACY_SMOKE =				0xC0 | LL_PCODE_LEGACY; // SMOKE
//constexpr LLPCode	LL_PCODE_LEGACY_SPARK =				0xD0 | LL_PCODE_LEGACY;// SPARK
constexpr LLPCode	LL_PCODE_LEGACY_TEXT_BUBBLE =		0xE0 | LL_PCODE_LEGACY; // TEXTBUBBLE
constexpr LLPCode	LL_PCODE_LEGACY_TREE =				0xF0 | LL_PCODE_LEGACY; // TREE

	// hemis
constexpr LLPCode	LL_PCODE_CYLINDER_HEMI =		LL_PCODE_CYLINDER	| LL_PCODE_HEMI_MASK;
constexpr LLPCode	LL_PCODE_CONE_HEMI =			LL_PCODE_CONE		| LL_PCODE_HEMI_MASK;
constexpr LLPCode	LL_PCODE_SPHERE_HEMI =			LL_PCODE_SPHERE		| LL_PCODE_HEMI_MASK;
constexpr LLPCode	LL_PCODE_TORUS_HEMI =			LL_PCODE_TORUS		| LL_PCODE_HEMI_MASK;


// Volumes consist of a profile at the base that is swept around
// a path to make a volume.
// The profile code
constexpr U8	LL_PCODE_PROFILE_MASK		= 0x0f;
constexpr U8	LL_PCODE_PROFILE_MIN		= 0x00;
constexpr U8    LL_PCODE_PROFILE_CIRCLE		= 0x00;
constexpr U8    LL_PCODE_PROFILE_SQUARE		= 0x01;
constexpr U8	LL_PCODE_PROFILE_ISOTRI		= 0x02;
constexpr U8    LL_PCODE_PROFILE_EQUALTRI	= 0x03;
constexpr U8    LL_PCODE_PROFILE_RIGHTTRI	= 0x04;
constexpr U8	LL_PCODE_PROFILE_CIRCLE_HALF = 0x05;
constexpr U8	LL_PCODE_PROFILE_MAX		= 0x05;

// Stored in the profile byte
constexpr U8	LL_PCODE_HOLE_MASK		= 0xf0;
constexpr U8	LL_PCODE_HOLE_MIN		= 0x00;
constexpr U8	LL_PCODE_HOLE_SAME		= 0x00;		// same as outside profile
constexpr U8	LL_PCODE_HOLE_CIRCLE	= 0x10;
constexpr U8	LL_PCODE_HOLE_SQUARE	= 0x20;
constexpr U8	LL_PCODE_HOLE_TRIANGLE	= 0x30;
constexpr U8	LL_PCODE_HOLE_MAX		= 0x03;		// min/max needs to be >> 4 of real min/max

constexpr U8    LL_PCODE_PATH_IGNORE    = 0x00;
constexpr U8	LL_PCODE_PATH_MIN		= 0x01;		// min/max needs to be >> 4 of real min/max
constexpr U8    LL_PCODE_PATH_LINE      = 0x10;
constexpr U8    LL_PCODE_PATH_CIRCLE    = 0x20;
constexpr U8    LL_PCODE_PATH_CIRCLE2   = 0x30;
constexpr U8    LL_PCODE_PATH_TEST      = 0x40;
constexpr U8    LL_PCODE_PATH_FLEXIBLE  = 0x80;
constexpr U8	LL_PCODE_PATH_MAX		= 0x08;

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

// face identifiers
typedef U16 LLFaceID;

constexpr LLFaceID	LL_FACE_PATH_BEGIN		= 0x1 << 0;
constexpr LLFaceID	LL_FACE_PATH_END		= 0x1 << 1;
constexpr LLFaceID	LL_FACE_INNER_SIDE		= 0x1 << 2;
constexpr LLFaceID	LL_FACE_PROFILE_BEGIN	= 0x1 << 3;
constexpr LLFaceID	LL_FACE_PROFILE_END		= 0x1 << 4;
constexpr LLFaceID	LL_FACE_OUTER_SIDE_0	= 0x1 << 5;
constexpr LLFaceID	LL_FACE_OUTER_SIDE_1	= 0x1 << 6;
constexpr LLFaceID	LL_FACE_OUTER_SIDE_2	= 0x1 << 7;
constexpr LLFaceID	LL_FACE_OUTER_SIDE_3	= 0x1 << 8;

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

// sculpt types + flags

constexpr U8 LL_SCULPT_TYPE_NONE      = 0;
constexpr U8 LL_SCULPT_TYPE_SPHERE    = 1;
constexpr U8 LL_SCULPT_TYPE_TORUS     = 2;
constexpr U8 LL_SCULPT_TYPE_PLANE     = 3;
constexpr U8 LL_SCULPT_TYPE_CYLINDER  = 4;
constexpr U8 LL_SCULPT_TYPE_MESH      = 5;
constexpr U8 LL_SCULPT_TYPE_MASK      = LL_SCULPT_TYPE_SPHERE | LL_SCULPT_TYPE_TORUS | LL_SCULPT_TYPE_PLANE |
	LL_SCULPT_TYPE_CYLINDER | LL_SCULPT_TYPE_MESH;

// for value checks, assign new value after adding new types
constexpr U8 LL_SCULPT_TYPE_MAX = LL_SCULPT_TYPE_MESH;

constexpr U8 LL_SCULPT_FLAG_INVERT    = 64;
constexpr U8 LL_SCULPT_FLAG_MIRROR    = 128;
constexpr U8 LL_SCULPT_FLAG_MASK = LL_SCULPT_FLAG_INVERT | LL_SCULPT_FLAG_MIRROR;

constexpr S32 LL_SCULPT_MESH_MAX_FACES = 8;

extern bool gDebugGL;

class LLProfileParams
{
public:
	LLProfileParams()
		: mCurveType(LL_PCODE_PROFILE_SQUARE),
		  mBegin(0.f),
		  mEnd(1.f),
		  mHollow(0.f),
		  mCRC(0)
	{
	}

	LLProfileParams(U8 curve, F32 begin, F32 end, F32 hollow)
		: mCurveType(curve),
		  mBegin(begin),
		  mEnd(end),
		  mHollow(hollow),
		  mCRC(0)
	{
	}

	LLProfileParams(U8 curve, U16 begin, U16 end, U16 hollow)
	{
		mCurveType = curve;
		F32 temp_f32 = begin * CUT_QUANTA;
		if (temp_f32 > 1.f)
		{
			temp_f32 = 1.f;
		}
		mBegin = temp_f32;
		temp_f32 = end * CUT_QUANTA;
		if (temp_f32 > 1.f)
		{
			temp_f32 = 1.f;
		}
		mEnd = 1.f - temp_f32;
		temp_f32 = hollow * HOLLOW_QUANTA;
		if (temp_f32 > 1.f)
		{
			temp_f32 = 1.f;
		}
		mHollow = temp_f32;
		mCRC = 0;
	}

	bool operator==(const LLProfileParams &params) const;
	bool operator!=(const LLProfileParams &params) const;
	bool operator<(const LLProfileParams &params) const;
	
	void copyParams(const LLProfileParams &params);

	bool importFile(LLFILE *fp);
	bool exportFile(LLFILE *fp) const;

	bool importLegacyStream(std::istream& input_stream);
	bool exportLegacyStream(std::ostream& output_stream) const;

	LLSD asLLSD() const;
	operator LLSD() const { return asLLSD(); }
	bool fromLLSD(LLSD& sd);

	const F32&  getBegin () const				{ return mBegin; }
	const F32&  getEnd   () const				{ return mEnd;   }
	const F32&  getHollow() const				{ return mHollow; }
	const U8&   getCurveType () const			{ return mCurveType; }

	void setCurveType(const U32 type)			{ mCurveType = type;}
	void setBegin(const F32 begin)				{ mBegin = (begin >= 1.0f) ? 0.0f : ((int) (begin * 100000))/100000.0f;}
	void setEnd(const F32 end)					{ mEnd   = (end   <= 0.0f) ? 1.0f : ((int) (end * 100000))/100000.0f;}
	void setHollow(const F32 hollow)			{ mHollow = ((int) (hollow * 100000))/100000.0f;}

	friend std::ostream& operator<<(std::ostream &s, const LLProfileParams &profile_params);

protected:
	// Profile params
	U8			  mCurveType;
	F32           mBegin;
	F32           mEnd;
	F32			  mHollow;

	U32           mCRC;
};

inline bool LLProfileParams::operator==(const LLProfileParams &params) const
{
	return 
		(getCurveType() == params.getCurveType()) &&
		(getBegin() == params.getBegin()) &&
		(getEnd() == params.getEnd()) &&
		(getHollow() == params.getHollow());
}

inline bool LLProfileParams::operator!=(const LLProfileParams &params) const
{
	return 
		(getCurveType() != params.getCurveType()) ||
		(getBegin() != params.getBegin()) ||
		(getEnd() != params.getEnd()) ||
		(getHollow() != params.getHollow());
}


inline bool LLProfileParams::operator<(const LLProfileParams &params) const
{
	if (getCurveType() != params.getCurveType())
	{
		return getCurveType() < params.getCurveType();
	}
	else
	if (getBegin() != params.getBegin())
	{
		return getBegin() < params.getBegin();
	}
	else
	if (getEnd() != params.getEnd())
	{
		return getEnd() < params.getEnd();
	}
	else
	{
		return getHollow() < params.getHollow();
	}
}

#define U8_TO_F32(x) (F32)(*((S8 *)&x))

class LLPathParams
{
public:
	LLPathParams()
		:
		mCurveType(LL_PCODE_PATH_LINE),
		mBegin(0.f),
		mEnd(1.f),
		mScale(1.f,1.f),
		mShear(0.f,0.f),
		mTwistBegin(0.f),
		mTwistEnd(0.f),
		mRadiusOffset(0.f),
		mTaper(0.f,0.f),
		mRevolutions(1.f),
		mSkew(0.f),
		mCRC(0)
	{
	}

	LLPathParams(U8 curve, F32 begin, F32 end, F32 scx, F32 scy, F32 shx, F32 shy, F32 twistend, F32 twistbegin, F32 radiusoffset, F32 tx, F32 ty, F32 revolutions, F32 skew)
		: mCurveType(curve),
		  mBegin(begin),
		  mEnd(end),
		  mScale(scx,scy),
		  mShear(shx,shy),
		  mTwistBegin(twistbegin),
		  mTwistEnd(twistend), 
		  mRadiusOffset(radiusoffset),
		  mTaper(tx,ty),
		  mRevolutions(revolutions),
		  mSkew(skew),
		  mCRC(0)
	{
	}

	LLPathParams(U8 curve, U16 begin, U16 end, U8 scx, U8 scy, U8 shx, U8 shy, U8 twistend, U8 twistbegin, U8 radiusoffset, U8 tx, U8 ty, U8 revolutions, U8 skew)
	{
		mCurveType = curve;
		mBegin = (F32)(begin * CUT_QUANTA);
		mEnd = (F32)(100.f - end) * CUT_QUANTA;
		if (mEnd > 1.f)
			mEnd = 1.f;
		mScale.setVec((F32) (200 - scx) * SCALE_QUANTA,(F32) (200 - scy) * SCALE_QUANTA);
		mShear.setVec(U8_TO_F32(shx) * SHEAR_QUANTA,U8_TO_F32(shy) * SHEAR_QUANTA);
		mTwistBegin = U8_TO_F32(twistbegin) * SCALE_QUANTA;
		mTwistEnd = U8_TO_F32(twistend) * SCALE_QUANTA;
		mRadiusOffset = U8_TO_F32(radiusoffset) * SCALE_QUANTA;
		mTaper.setVec(U8_TO_F32(tx) * TAPER_QUANTA,U8_TO_F32(ty) * TAPER_QUANTA);
		mRevolutions = ((F32)revolutions) * REV_QUANTA + 1.0f;
		mSkew = U8_TO_F32(skew) * SCALE_QUANTA;

		mCRC = 0;
	}

	bool operator==(const LLPathParams &params) const;
	bool operator!=(const LLPathParams &params) const;
	bool operator<(const LLPathParams &params) const;

	void copyParams(const LLPathParams &params);

	bool importFile(LLFILE *fp);
	bool exportFile(LLFILE *fp) const;

	bool importLegacyStream(std::istream& input_stream);
	bool exportLegacyStream(std::ostream& output_stream) const;

	LLSD asLLSD() const;
	operator LLSD() const { return asLLSD(); }
	bool fromLLSD(LLSD& sd);

	const F32& getBegin() const			{ return mBegin; }
	const F32& getEnd() const			{ return mEnd; }
	const LLVector2 &getScale() const	{ return mScale; }
	const F32& getScaleX() const		{ return mScale.mV[0]; }
	const F32& getScaleY() const		{ return mScale.mV[1]; }
	const LLVector2 getBeginScale() const;
	const LLVector2 getEndScale() const;
	const LLVector2 &getShear() const	{ return mShear; }
	const F32& getShearX() const		{ return mShear.mV[0]; }
	const F32& getShearY() const		{ return mShear.mV[1]; }
	const U8& getCurveType () const		{ return mCurveType; }

	const F32& getTwistBegin() const	{ return mTwistBegin;	}
	const F32& getTwistEnd() const		{ return mTwistEnd;	}
	const F32& getTwist() const			{ return mTwistEnd; }	// deprecated
	const F32& getRadiusOffset() const	{ return mRadiusOffset; }
	const LLVector2 &getTaper() const	{ return mTaper;		}
	const F32& getTaperX() const		{ return mTaper.mV[0];	}
	const F32& getTaperY() const		{ return mTaper.mV[1];	}
	const F32& getRevolutions() const	{ return mRevolutions;	}
	const F32& getSkew() const			{ return mSkew;			}

	void setCurveType(const U8 type)	{ mCurveType = type;	}
	void setBegin(const F32 begin)		{ mBegin     = begin;	}
	void setEnd(const F32 end)			{ mEnd       = end;	}

	void setScale(const F32 x, const F32 y)		{ mScale.setVec(x,y); }
	void setScaleX(const F32 v)					{ mScale.mV[VX] = v; }
	void setScaleY(const F32 v)					{ mScale.mV[VY] = v; }
	void setShear(const F32 x, const F32 y)		{ mShear.setVec(x,y); }
	void setShearX(const F32 v)					{ mShear.mV[VX] = v; }
	void setShearY(const F32 v)					{ mShear.mV[VY] = v; }

	void setTwistBegin(const F32 twist_begin)	{ mTwistBegin	= twist_begin;	}
	void setTwistEnd(const F32 twist_end)		{ mTwistEnd		= twist_end;	}
	void setTwist(const F32 twist)				{ setTwistEnd(twist); }	// deprecated
	void setRadiusOffset(const F32 radius_offset){ mRadiusOffset	= radius_offset; }
	void setTaper(const F32 x, const F32 y)		{ mTaper.setVec(x,y);			}
	void setTaperX(const F32 v)					{ mTaper.mV[VX]	= v;			}
	void setTaperY(const F32 v)					{ mTaper.mV[VY]	= v;			}
	void setRevolutions(const F32 revolutions)	{ mRevolutions	= revolutions;	}
	void setSkew(const F32 skew)				{ mSkew			= skew;			}

	friend std::ostream& operator<<(std::ostream &s, const LLPathParams &path_params);

protected:
	// Path params
	U8			  mCurveType;
	F32           mBegin;
	F32           mEnd;
	LLVector2	  mScale;
	LLVector2     mShear;

	F32			  mTwistBegin;
	F32			  mTwistEnd;
	F32			  mRadiusOffset;
	LLVector2	  mTaper;
	F32			  mRevolutions;
	F32			  mSkew;

	U32           mCRC;
};

inline bool LLPathParams::operator==(const LLPathParams &params) const
{
	return
		(getCurveType() == params.getCurveType()) && 
		(getScale() == params.getScale()) &&
		(getBegin() == params.getBegin()) && 
		(getEnd() == params.getEnd()) && 
		(getShear() == params.getShear()) &&
		(getTwist() == params.getTwist()) &&
		(getTwistBegin() == params.getTwistBegin()) &&
		(getRadiusOffset() == params.getRadiusOffset()) &&
		(getTaper() == params.getTaper()) &&
		(getRevolutions() == params.getRevolutions()) &&
		(getSkew() == params.getSkew());
}

inline bool LLPathParams::operator!=(const LLPathParams &params) const
{
	return
		(getCurveType() != params.getCurveType()) ||
		(getScale() != params.getScale()) ||
		(getBegin() != params.getBegin()) || 
		(getEnd() != params.getEnd()) || 
		(getShear() != params.getShear()) ||
		(getTwist() != params.getTwist()) ||
		(getTwistBegin() !=params.getTwistBegin()) ||
		(getRadiusOffset() != params.getRadiusOffset()) ||
		(getTaper() != params.getTaper()) ||
		(getRevolutions() != params.getRevolutions()) ||
		(getSkew() != params.getSkew());
}


inline bool LLPathParams::operator<(const LLPathParams &params) const
{
	if( getCurveType() != params.getCurveType()) 
	{
		return getCurveType() < params.getCurveType();
	}
	else
	if( getScale() != params.getScale()) 
	{
		return getScale() < params.getScale();
	}
	else
	if( getBegin() != params.getBegin()) 
	{
		return getBegin() < params.getBegin();
	}
	else
	if( getEnd() != params.getEnd()) 
	{
		return getEnd() < params.getEnd();
	}
	else
	if( getShear() != params.getShear()) 
	{
		return getShear() < params.getShear();
	}
	else
	if( getTwist() != params.getTwist())
	{
		return getTwist() < params.getTwist();
	}
	else
	if( getTwistBegin() != params.getTwistBegin())
	{
		return getTwistBegin() < params.getTwistBegin();
	}
	else
	if( getRadiusOffset() != params.getRadiusOffset())
	{
		return getRadiusOffset() < params.getRadiusOffset();
	}
	else
	if( getTaper() != params.getTaper())
	{
		return getTaper() < params.getTaper();
	}
	else
	if( getRevolutions() != params.getRevolutions())
	{
		return getRevolutions() < params.getRevolutions();
	}
	else
	{
		return getSkew() < params.getSkew();
	}
}

typedef LLVolumeParams* LLVolumeParamsPtr;
typedef const LLVolumeParams* const_LLVolumeParamsPtr;

class LLVolumeParams
{
public:
	LLVolumeParams()
		: mSculptType(LL_SCULPT_TYPE_NONE)
	{
	}

	LLVolumeParams(LLProfileParams &profile, LLPathParams &path,
				   LLUUID sculpt_id = LLUUID::null, U8 sculpt_type = LL_SCULPT_TYPE_NONE)
		: mProfileParams(profile), mPathParams(path), mSculptID(sculpt_id), mSculptType(sculpt_type)
	{
	}

	bool operator==(const LLVolumeParams &params) const;
	bool operator!=(const LLVolumeParams &params) const;
	bool operator<(const LLVolumeParams &params) const;


	void copyParams(const LLVolumeParams &params);
	
	const LLProfileParams &getProfileParams() const {return mProfileParams;}
	LLProfileParams &getProfileParams() {return mProfileParams;}
	const LLPathParams &getPathParams() const {return mPathParams;}
	LLPathParams &getPathParams() {return mPathParams;}

	bool importFile(LLFILE *fp);
	bool exportFile(LLFILE *fp) const;

	bool importLegacyStream(std::istream& input_stream);
	bool exportLegacyStream(std::ostream& output_stream) const;

	LLSD sculptAsLLSD() const;
	bool sculptFromLLSD(LLSD& sd);
	
	LLSD asLLSD() const;
	operator LLSD() const { return asLLSD(); }
	bool fromLLSD(LLSD& sd);

	bool setType(U8 profile, U8 path);

	//void setBeginS(const F32 beginS)			{ mProfileParams.setBegin(beginS); }	// range 0 to 1
	//void setBeginT(const F32 beginT)			{ mPathParams.setBegin(beginT); }		// range 0 to 1
	//void setEndS(const F32 endS)				{ mProfileParams.setEnd(endS); }		// range 0 to 1, must be greater than begin
	//void setEndT(const F32 endT)				{ mPathParams.setEnd(endT); }			// range 0 to 1, must be greater than begin

	bool setBeginAndEndS(const F32 begin, const F32 end);			// both range from 0 to 1, begin must be less than end
	bool setBeginAndEndT(const F32 begin, const F32 end);			// both range from 0 to 1, begin must be less than end

	bool setHollow(const F32 hollow);	// range 0 to 1
	bool setRatio(const F32 x)					{ return setRatio(x,x); }			// 0 = point, 1 = same as base
	bool setShear(const F32 x)					{ return setShear(x,x); }			// 0 = no movement, 
	bool setRatio(const F32 x, const F32 y);			// 0 = point, 1 = same as base
	bool setShear(const F32 x, const F32 y);			// 0 = no movement

	bool setTwistBegin(const F32 twist_begin);	// range -1 to 1
	bool setTwistEnd(const F32 twist_end);		// range -1 to 1
	bool setTwist(const F32 twist)				{ return setTwistEnd(twist); }		// deprecated
	bool setTaper(const F32 x, const F32 y)		{ bool pass_x = setTaperX(x); bool pass_y = setTaperY(y); return pass_x && pass_y; }
	bool setTaperX(const F32 v);				// -1 to 1
	bool setTaperY(const F32 v);				// -1 to 1
	bool setRevolutions(const F32 revolutions);	// 1 to 4
	bool setRadiusOffset(const F32 radius_offset);
	bool setSkew(const F32 skew);
	bool setSculptID(const LLUUID& sculpt_id, U8 sculpt_type);

	static bool validate(U8 prof_curve, F32 prof_begin, F32 prof_end, F32 hollow,
		U8 path_curve, F32 path_begin, F32 path_end,
		F32 scx, F32 scy, F32 shx, F32 shy,
		F32 twistend, F32 twistbegin, F32 radiusoffset,
		F32 tx, F32 ty, F32 revolutions, F32 skew);
	
	const F32&  getBeginS() 	const	{ return mProfileParams.getBegin(); }
 	const F32&  getBeginT() 	const	{ return mPathParams.getBegin(); }
 	const F32&  getEndS() 		const	{ return mProfileParams.getEnd(); }
 	const F32&  getEndT() 		const	{ return mPathParams.getEnd(); }
 
 	const F32&  getHollow() 	const   { return mProfileParams.getHollow(); }
 	const F32&  getTwist() 	const   	{ return mPathParams.getTwist(); }
 	const F32&  getRatio() 	const		{ return mPathParams.getScaleX(); }
 	const F32&  getRatioX() 	const   { return mPathParams.getScaleX(); }
 	const F32&  getRatioY() 	const   { return mPathParams.getScaleY(); }
 	const F32&  getShearX() 	const   { return mPathParams.getShearX(); }
 	const F32&  getShearY() 	const   { return mPathParams.getShearY(); }

	const F32&	getTwistBegin()const	{ return mPathParams.getTwistBegin();	}
	const F32&  getRadiusOffset() const	{ return mPathParams.getRadiusOffset();	}
	const F32&  getTaper() const		{ return mPathParams.getTaperX();		}
	const F32&	getTaperX() const		{ return mPathParams.getTaperX();		}
	const F32&  getTaperY() const		{ return mPathParams.getTaperY();		}
	const F32&  getRevolutions() const	{ return mPathParams.getRevolutions();	}
	const F32&  getSkew() const			{ return mPathParams.getSkew();			}
	const LLUUID& getSculptID() const	{ return mSculptID;						}
	const U8& getSculptType() const     { return mSculptType;                   }
	bool isSculpt() const;
	bool isMeshSculpt() const;
	bool isConvex() const;

	// 'begin' and 'end' should be in range [0, 1] (they will be clamped)
	// (begin, end) = (0, 1) will not change the volume
	// (begin, end) = (0, 0.5) will reduce the volume to the first half of its profile/path (S/T)
	void reduceS(F32 begin, F32 end);
	void reduceT(F32 begin, F32 end);

	struct compare
	{
		bool operator()( const const_LLVolumeParamsPtr& first, const const_LLVolumeParamsPtr& second) const
		{
			return (*first < *second);
		}
	};
	
	friend std::ostream& operator<<(std::ostream &s, const LLVolumeParams &volume_params);

	// debug helper functions
	void setCube();

protected:
	LLProfileParams mProfileParams;
	LLPathParams	mPathParams;
	LLUUID mSculptID;
	U8 mSculptType;
};


class LLProfile
{
	friend class LLVolume;

public:
	LLProfile()
		: mOpen(false),
		  mConcave(false),
		  mDirty(true),
		  mTotalOut(0),
		  mTotal(2)
	{
	}

	S32	 getTotal() const								{ return mTotal; }
	S32	 getTotalOut() const							{ return mTotalOut; }	// Total number of outside points
	bool isFlat(S32 face) const							{ return (mFaces[face].mCount == 2); }
	bool isOpen() const									{ return mOpen; }
	void setDirty()										{ mDirty = true; }

	static S32 getNumPoints(const LLProfileParams& params, bool path_open, F32 detail = 1.0f, S32 split = 0,
				  bool is_sculpted = false, S32 sculpt_size = 0);
	bool generate(const LLProfileParams& params, bool path_open, F32 detail = 1.0f, S32 split = 0,
				  bool is_sculpted = false, S32 sculpt_size = 0);
	bool isConcave() const								{ return mConcave; }
public:
	struct Face
	{
		S32       mIndex;
		S32       mCount;
		F32       mScaleU;
		bool      mCap;
		bool      mFlat;
		LLFaceID  mFaceID;
	};
	
	LLAlignedArray<LLVector4a, 64> mProfile;	
	//LLAlignedArray<LLVector4a, 64> mNormals;
	std::vector<Face>      mFaces;

	//LLAlignedArray<LLVector4a, 64> mEdgeNormals;
	//LLAlignedArray<LLVector4a, 64> mEdgeCenters;

	friend std::ostream& operator<<(std::ostream &s, const LLProfile &profile);

protected:
	~LLProfile();

	static S32 getNumNGonPoints(const LLProfileParams& params, S32 sides, F32 offset=0.0f, F32 bevel = 0.0f, F32 ang_scale = 1.f, S32 split = 0);
	void genNGon(const LLProfileParams& params, S32 sides, F32 offset=0.0f, F32 bevel = 0.0f, F32 ang_scale = 1.f, S32 split = 0);

	Face* addHole(const LLProfileParams& params, bool flat, F32 sides, F32 offset, F32 box_hollow, F32 ang_scale, S32 split = 0);
	Face* addCap (S16 faceID);
	Face* addFace(S32 index, S32 count, F32 scaleU, S16 faceID, bool flat);

protected:
	bool		  mOpen;
	bool		  mConcave;
	bool          mDirty;

	S32			  mTotalOut;
	S32			  mTotal;
};

//-------------------------------------------------------------------
// SWEEP/EXTRUDE PATHS
//-------------------------------------------------------------------

class LLPath
{
public:
	class PathPt
	{
	public:
		LLMatrix4a   mRot;
		LLVector4a	 mPos;
		
		LLVector4a   mScale;
		F32			 mTexT;
		F32 pad[3]; //for alignment
		PathPt() 
		{ 
			mPos.clear(); 
			mTexT = 0; 
			mScale.clear(); 
			mRot.setRows(LLVector4a(1,0,0,0),
						LLVector4a(0,1,0,0),
						LLVector4a(0,0,1,0));

			//distinguished data in the pad for debugging
			pad[0] = 3.14159f;
			pad[1] = -3.14159f;
			pad[2] = 0.585f;
		}
	};

public:
	LLPath()
		: mOpen(false),
		  mTotal(0),
		  mDirty(true),
		  mStep(1)
	{
	}

	virtual ~LLPath();

	static S32 getNumPoints(const LLPathParams& params, F32 detail);
	static S32 getNumNGonPoints(const LLPathParams& params, S32 sides, F32 offset=0.0f, F32 end_scale = 1.f, F32 twist_scale = 1.f);

	void genNGon(const LLPathParams& params, S32 sides, F32 offset=0.0f, F32 end_scale = 1.f, F32 twist_scale = 1.f);
	virtual bool generate(const LLPathParams& params, F32 detail=1.0f, S32 split = 0,
						  bool is_sculpted = false, S32 sculpt_size = 0);

	bool isOpen() const						{ return mOpen; }
	F32 getStep() const						{ return mStep; }
	void setDirty()							{ mDirty = true; }

	S32 getPathLength() const				{ return (S32)mPath.size(); }

	void resizePath(S32 length) { mPath.resize(length); }

	friend std::ostream& operator<<(std::ostream &s, const LLPath &path);

public:
	LLAlignedArray<PathPt, 64> mPath;

protected:
	bool		  mOpen;
	S32			  mTotal;
	bool          mDirty;
	F32           mStep;
};

class LLDynamicPath : public LLPath
{
public:
	LLDynamicPath() : LLPath() { }
	/*virtual*/ bool generate(const LLPathParams& params, F32 detail=1.0f, S32 split = 0,
							  bool is_sculpted = false, S32 sculpt_size = 0);
};

// Yet another "face" class - caches volume-specific, but not instance-specific data for faces)
class LLVolumeFace
{
public:
	class VertexData
	{
		enum 
		{
			POSITION = 0,
			NORMAL = 1
		};

	private:
		void init();
	public:
		VertexData();
		VertexData(const VertexData& rhs);
		const VertexData& operator=(const VertexData& rhs);

		~VertexData();
		LLVector4a& getPosition();
		LLVector4a& getNormal();
		const LLVector4a& getPosition() const;
		const LLVector4a& getNormal() const;
		void setPosition(const LLVector4a& pos);
		void setNormal(const LLVector4a& norm);
		

		LLVector2 mTexCoord;

		bool operator<(const VertexData& rhs) const;
		bool operator==(const VertexData& rhs) const;
		bool compareNormal(const VertexData& rhs, F32 angle_cutoff) const;

	private:
		LLVector4a* mData;
	};

	LLVolumeFace();
	LLVolumeFace(const LLVolumeFace& src);
	LLVolumeFace& operator=(const LLVolumeFace& rhs);

	~LLVolumeFace();
private:
	void freeData();
public:

	bool create(LLVolume* volume, bool partial_build = false);
	void createTangents();
	
	void resizeVertices(S32 num_verts);
	void allocateTangents(S32 num_verts);
	void allocateWeights(S32 num_verts);
    void allocateJointIndices(S32 num_verts);
	void resizeIndices(S32 num_indices);
	void fillFromLegacyData(std::vector<LLVolumeFace::VertexData>& v, std::vector<U16>& idx);

	void pushVertex(const VertexData& cv);
	void pushVertex(const LLVector4a& pos, const LLVector4a& norm, const LLVector2& tc);
	void pushIndex(const U16& idx);

	void swapData(LLVolumeFace& rhs);

	void getVertexData(U16 indx, LLVolumeFace::VertexData& cv);

	class VertexMapData : public LLVolumeFace::VertexData
	{
	public:
		U16 mIndex;

		bool operator==(const LLVolumeFace::VertexData& rhs) const;

		struct ComparePosition
		{
			bool operator()(const LLVector3& a, const LLVector3& b) const;
		};

		typedef std::map<LLVector3, std::vector<VertexMapData>, VertexMapData::ComparePosition > PointMap;
	};

    // Eliminates non unique triangles, takes positions,
    // normals and texture coordinates into account.
    void remap();

	void optimize(F32 angle_cutoff = 2.f);
	bool cacheOptimize(bool gen_tangents = false);

	void createOctree(F32 scaler = 0.25f, const LLVector4a& center = LLVector4a(0,0,0), const LLVector4a& size = LLVector4a(0.5f,0.5f,0.5f));
    void destroyOctree();
    // Get a reference to the octree, which may be null
    const LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>* getOctree() const;

	enum
	{
		SINGLE_MASK =	0x0001,
		CAP_MASK =		0x0002,
		END_MASK =		0x0004,
		SIDE_MASK =		0x0008,
		INNER_MASK =	0x0010,
		OUTER_MASK =	0x0020,
		HOLLOW_MASK =	0x0040,
		OPEN_MASK =		0x0080,
		FLAT_MASK =		0x0100,
		TOP_MASK =		0x0200,
		BOTTOM_MASK =	0x0400
	};
	
public:
	S32 mID;
	U32 mTypeMask;
	
	// Only used for INNER/OUTER faces
	S32 mBeginS;
	S32 mBeginT;
	S32 mNumS;
	S32 mNumT;

	LLVector4a* mExtents; //minimum and maximum point of face
	LLVector4a* mCenter;
	LLVector2   mTexCoordExtents[2]; //minimum and maximum of texture coordinates of the face.

	S32 mNumVertices; // num vertices == num normals == num texcoords
	S32 mNumAllocatedVertices;
	S32 mNumIndices;

	LLVector4a* mPositions; // Contains vertices, nortmals and texcoords
	LLVector4a* mNormals; // pointer into mPositions
	LLVector4a* mTangents;
	LLVector2*  mTexCoords; // pointer into mPositions

	// mIndices contains mNumIndices amount of elements.
	// It contains triangles, each 3 indices describe one triangle.
    // If mIndices contains {0, 2, 3, 1, 2, 4}, it means there
    // are two triangles {0, 2, 3} and {1, 2, 4} with values being
    // indexes for mPositions/mNormals/mTexCoords
	U16* mIndices;

	std::vector<S32>	mEdge;

	//list of skin weights for rigged volumes
	// format is mWeights[vertex_index].mV[influence] = <joint_index>.<weight>
	// mWeights.size() should be empty or match mVertices.size()  
	LLVector4a* mWeights;

#if USE_SEPARATE_JOINT_INDICES_AND_WEIGHTS
    LLVector4a* mJustWeights;
    U8* mJointIndices;
#endif

    mutable bool mWeightsScrubbed;

    // Which joints are rigged to, and the bounding box of any rigged
    // vertices per joint.
    LLJointRiggingInfoTab mJointRiggingInfoTab;

	//whether or not face has been cache optimized
	bool mOptimized;

    // if this is a mesh asset, scale and translation that were applied
    // when encoding the source mesh into a unit cube
    // used for regenerating tangents
    LLVector3 mNormalizedScale = LLVector3(1,1,1);

private:
    LLOctreeNode<LLVolumeTriangle, LLVolumeTriangle*>* mOctree;
    LLVolumeTriangle* mOctreeTriangles;

	bool createUnCutCubeCap(LLVolume* volume, bool partial_build = false);
	bool createCap(LLVolume* volume, bool partial_build = false);
	bool createSide(LLVolume* volume, bool partial_build = false);
};

class LLVolume : public LLRefCount
{
	friend class LLVolumeLODGroup;

protected:
	virtual ~LLVolume(); // use unref

public:
	typedef std::vector<LLVolumeFace> face_list_t;
		
	struct FaceParams
	{
		LLFaceID mFaceID;
		S32 mBeginS;
		S32 mCountS;
		S32 mBeginT;
		S32 mCountT;
	};

	LLVolume(const LLVolumeParams &params, const F32 detail, const bool generate_single_face = false, const bool is_unique = false);
	
	U8 getProfileType()	const								{ return mParams.getProfileParams().getCurveType(); }
	U8 getPathType() const									{ return mParams.getPathParams().getCurveType(); }
	S32	getNumFaces() const;
	S32 getNumVolumeFaces() const							{ return mVolumeFaces.size(); }
	F32 getDetail() const									{ return mDetail; }
	F32 getSurfaceArea() const								{ return mSurfaceArea; }
	const LLVolumeParams& getParams() const					{ return mParams; }
	LLVolumeParams getCopyOfParams() const					{ return mParams; }
	const LLProfile& getProfile() const						{ return *mProfilep; }
	LLPath& getPath() const									{ return *mPathp; }
	void resizePath(S32 length);
	const LLAlignedArray<LLVector4a,64>&	getMesh() const				{ return mMesh; }
	const LLVector4a& getMeshPt(const U32 i) const			{ return mMesh[i]; }
	

	void setDirty() { mPathp->setDirty(); mProfilep->setDirty(); }

	void regen();
    void genTangents(S32 face);

	bool isConvex() const;
	bool isCap(S32 face);
	bool isFlat(S32 face);
	bool isUnique() const									{ return mUnique; }

	S32 getSculptLevel() const                              { return mSculptLevel; }
	void setSculptLevel(S32 level)							{ mSculptLevel = level; }

	
	static void getLoDTriangleCounts(const LLVolumeParams& params, S32* counts);

	S32 getNumTriangles(S32* vcount = nullptr) const;

	void generateSilhouetteVertices(std::vector<LLVector3> &vertices, 
									std::vector<LLVector3> &normals, 
									const LLVector3& view_vec,
									const LLMatrix4& mat,
									const LLMatrix3& norm_mat,
									S32 face_index);

	//get the face index of the face that intersects with the given line segment at the point 
	//closest to start.  Moves end to the point of intersection.  Returns -1 if no intersection.
	//Line segment must be in volume space.
	S32 lineSegmentIntersect(const LLVector4a& start, const LLVector4a& end,
							 S32 face = -1,                          // which face to check, -1 = ALL_SIDES
							 LLVector4a* intersection = nullptr,     // return the intersection point
							 LLVector2* tex_coord = nullptr,         // return the texture coordinates of the intersection point
							 LLVector4a* normal = nullptr,           // return the surface normal at the intersection point
							 LLVector4a* tangent = nullptr           // return the surface tangent at the intersection point
		);

	LLFaceID generateFaceMask();

	bool isFaceMaskValid(LLFaceID face_mask);
	static S32 sNumMeshPoints;

	friend std::ostream& operator<<(std::ostream &s, const LLVolume &volume);
	friend std::ostream& operator<<(std::ostream &s, const LLVolume *volumep);		// HACK to bypass Windoze confusion over 
																				// conversion if *(LLVolume*) to LLVolume&
	const LLVolumeFace &getVolumeFace(const S32 f) const {return mVolumeFaces[f];} // DO NOT DELETE VOLUME WHILE USING THIS REFERENCE, OR HOLD A POINTER TO THIS VOLUMEFACE
	
	LLVolumeFace &getVolumeFace(const S32 f) {return mVolumeFaces[f];} // DO NOT DELETE VOLUME WHILE USING THIS REFERENCE, OR HOLD A POINTER TO THIS VOLUMEFACE

	face_list_t& getVolumeFaces() { return mVolumeFaces; }

	U32					mFaceMask;			// bit array of which faces exist in this volume
	LLVector3			mLODScaleBias;		// vector for biasing LOD based on scale
	
	void sculpt(U16 sculpt_width, U16 sculpt_height, S8 sculpt_components, const U8* sculpt_data, S32 sculpt_level, bool visible_placeholder);
	void copyVolumeFaces(const LLVolume* volume);
	void copyFacesTo(std::vector<LLVolumeFace> &faces) const;
	void copyFacesFrom(const std::vector<LLVolumeFace> &faces);

    // use meshoptimizer to optimize index buffer for vertex shader cache
    //  gen_tangents - if true, generate MikkTSpace tangents if needed before optimizing index buffer
	bool cacheOptimize(bool gen_tangents = false);

private:
	void sculptGenerateMapVertices(U16 sculpt_width, U16 sculpt_height, S8 sculpt_components, const U8* sculpt_data, U8 sculpt_type);
	F32 sculptGetSurfaceArea();
	void sculptGenerateEmptyPlaceholder();
	void sculptGenerateSpherePlaceholder();

protected:
	bool generate();
	void createVolumeFaces();
public:
	bool unpackVolumeFaces(std::istream& is, S32 size);
	bool unpackVolumeFaces(U8* in_data, S32 size);
private:
	bool unpackVolumeFacesInternal(const LLSD& mdl);

public:
	virtual void setMeshAssetLoaded(bool loaded);
	virtual bool isMeshAssetLoaded();
    virtual void setMeshAssetUnavaliable(bool unavaliable);
    virtual bool isMeshAssetUnavaliable();

 protected:
	bool mUnique;
	F32 mDetail;
	S32 mSculptLevel;
	F32 mSurfaceArea; //unscaled surface area
	bool mIsMeshAssetLoaded;
    bool mIsMeshAssetUnavaliable;
	
	const LLVolumeParams mParams;
	LLPath *mPathp;
	LLProfile *mProfilep;
	LLAlignedArray<LLVector4a,64> mMesh;
	
	
	bool mGenerateSingleFace;
	face_list_t mVolumeFaces;

public:
	LLVector4a* mHullPoints;
	U16* mHullIndices;
	S32 mNumHullPoints;
	S32 mNumHullIndices;
};

std::ostream& operator<<(std::ostream &s, const LLVolumeParams &volume_params);

bool LLLineSegmentBoxIntersect(const F32* start, const F32* end, const F32* center, const F32* size);
bool LLLineSegmentBoxIntersect(const LLVector3& start, const LLVector3& end, const LLVector3& center, const LLVector3& size);
bool LLLineSegmentBoxIntersect(const LLVector4a& start, const LLVector4a& end, const LLVector4a& center, const LLVector4a& size);

bool LLTriangleRayIntersect(const LLVector4a& vert0, const LLVector4a& vert1, const LLVector4a& vert2, const LLVector4a& orig, const LLVector4a& dir,
							F32& intersection_a, F32& intersection_b, F32& intersection_t);
bool LLTriangleRayIntersectTwoSided(const LLVector4a& vert0, const LLVector4a& vert1, const LLVector4a& vert2, const LLVector4a& orig, const LLVector4a& dir,
							F32& intersection_a, F32& intersection_b, F32& intersection_t);

#endif