/*------------------------------------------------------------------------

 *

 * OpenVG 1.1 Reference Implementation

 * -----------------------------------

 *

 * Copyright (c) 2007 The Khronos Group Inc.

 *

 * Permission is hereby granted, free of charge, to any person obtaining a

 * copy of this software and /or associated documentation files

 * (the "Materials "), to deal in the Materials without restriction,

 * including without limitation the rights to use, copy, modify, merge,

 * publish, distribute, sublicense, and/or sell copies of the Materials,

 * and to permit persons to whom the Materials are furnished to do so,

 * subject to the following conditions: 

 *

 * The above copyright notice and this permission notice shall be included 

 * in all copies or substantial portions of the Materials. 

 *

 * THE MATERIALS ARE PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,

 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF

 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.

 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,

 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR

 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE MATERIALS OR

 * THE USE OR OTHER DEALINGS IN THE MATERIALS.

 *

 *//**

 * \file

 * \brief	Implementation of Path functions.

 * \note	

 *//*-------------------------------------------------------------------*/

#include "riPath.h"

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

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

namespace OpenVGRI

{

RIfloat inputFloat(VGfloat f);	//defined in riApi.cpp

/*-------------------------------------------------------------------*//*!

* \brief	Form a reliable normalized average of the two unit input vectors.

*           The average always lies to the given direction from the first

*			vector.

* \param	u0, u1 Unit input vectors.

* \param	cw True if the average should be clockwise from u0, false if

*              counterclockwise.

* \return	Average of the two input vectors.

* \note		

*//*-------------------------------------------------------------------*/

static const Vector2 unitAverage(const Vector2& u0, const Vector2& u1, bool cw)

{

	Vector2 u = 0.5f * (u0 + u1);

	Vector2 n0 = perpendicularCCW(u0);

	if( dot(u, u) > 0.25f )

	{	//the average is long enough and thus reliable

		if( dot(n0, u1) < 0.0f )

			u = -u;	//choose the larger angle

	}

	else

	{	// the average is too short, use the average of the normals to the vectors instead

		Vector2 n1 = perpendicularCW(u1);

		u = 0.5f * (n0 + n1);

	}

	if( cw )

		u = -u;

	return normalize(u);

}

/*-------------------------------------------------------------------*//*!

* \brief	Form a reliable normalized average of the two unit input vectors.

*			The average lies on the side where the angle between the input

*			vectors is less than 180 degrees.

* \param	u0, u1 Unit input vectors.

* \return	Average of the two input vectors.

* \note		

*//*-------------------------------------------------------------------*/

static const Vector2 unitAverage(const Vector2& u0, const Vector2& u1)

{

	Vector2 u = 0.5f * (u0 + u1);

	if( dot(u, u) < 0.25f )

	{	// the average is unreliable, use the average of the normals to the vectors instead

		Vector2 n0 = perpendicularCCW(u0);

		Vector2 n1 = perpendicularCW(u1);

		u = 0.5f * (n0 + n1);

		if( dot(n1, u0) < 0.0f )

			u = -u;

	}

	return normalize(u);

}

/*-------------------------------------------------------------------*//*!

* \brief	Interpolate the given unit tangent vectors to the given

*			direction on a unit circle.

* \param	

* \return	

* \note		

*//*-------------------------------------------------------------------*/

static const Vector2 circularLerp(const Vector2& t0, const Vector2& t1, RIfloat ratio, bool cw)

{

	Vector2 u0 = t0, u1 = t1;

	RIfloat l0 = 0.0f, l1 = 1.0f;

	for(int i=0;i<18;i++)

	{

		Vector2 n = unitAverage(u0, u1, cw);

		RIfloat l = 0.5f * (l0 + l1);

		if( ratio < l )

		{

			u1 = n;

			l1 = l;

		}

		else

		{

			u0 = n;

			l0 = l;

		}

	}

	return u0;

}

/*-------------------------------------------------------------------*//*!

* \brief	Interpolate the given unit tangent vectors on a unit circle.

*			Smaller angle between the vectors is used.

* \param	

* \return	

* \note		

*//*-------------------------------------------------------------------*/

static const Vector2 circularLerp(const Vector2& t0, const Vector2& t1, RIfloat ratio)

{

	Vector2 u0 = t0, u1 = t1;

	RIfloat l0 = 0.0f, l1 = 1.0f;

	for(int i=0;i<18;i++)

	{

		Vector2 n = unitAverage(u0, u1);

		RIfloat l = 0.5f * (l0 + l1);

		if( ratio < l )

		{

			u1 = n;

			l1 = l;

		}

		else

		{

			u0 = n;

			l0 = l;

		}

	}

	return u0;

}

/*-------------------------------------------------------------------*//*!

* \brief	Path constructor.

* \param	

* \return	

* \note		

*//*-------------------------------------------------------------------*/

Path::Path(VGint format, VGPathDatatype datatype, RIfloat scale, RIfloat bias, int segmentCapacityHint, int coordCapacityHint, VGbitfield caps) :

	m_format(format),

	m_datatype(datatype),

	m_scale(scale),

	m_bias(bias),

	m_capabilities(caps),

	m_referenceCount(0),

	m_segments(),

	m_data(),

	m_vertices(),

	m_segmentToVertex(),

	m_userMinx(0.0f),

	m_userMiny(0.0f),

	m_userMaxx(0.0f),

	m_userMaxy(0.0f)

{

	RI_ASSERT(format == VG_PATH_FORMAT_STANDARD);

	RI_ASSERT(datatype >= VG_PATH_DATATYPE_S_8 && datatype <= VG_PATH_DATATYPE_F);

	if(segmentCapacityHint > 0)

		m_segments.reserve(RI_INT_MIN(segmentCapacityHint, 65536));

	if(coordCapacityHint > 0)

		m_data.reserve(RI_INT_MIN(coordCapacityHint, 65536) * getBytesPerCoordinate(datatype));

}

/*-------------------------------------------------------------------*//*!

* \brief	Path destructor.

* \param	

* \return	

* \note		

*//*-------------------------------------------------------------------*/

Path::~Path()

{

	RI_ASSERT(m_referenceCount == 0);

}

/*-------------------------------------------------------------------*//*!

* \brief	Reads a coordinate and applies scale and bias.

* \param	

* \return	

*//*-------------------------------------------------------------------*/

RIfloat Path::getCoordinate(int i) const

{

	RI_ASSERT(i >= 0 && i < m_data.size() / getBytesPerCoordinate(m_datatype));

	RI_ASSERT(m_scale != 0.0f);

	const RIuint8* ptr = &m_data[0];

	switch(m_datatype)

	{

	case VG_PATH_DATATYPE_S_8:

		return (RIfloat)(((const RIint8*)ptr)[i]) * m_scale + m_bias;

	case VG_PATH_DATATYPE_S_16:

		return (RIfloat)(((const RIint16*)ptr)[i]) * m_scale + m_bias;

	case VG_PATH_DATATYPE_S_32:

		return (RIfloat)(((const RIint32*)ptr)[i]) * m_scale + m_bias;

	default:

		RI_ASSERT(m_datatype == VG_PATH_DATATYPE_F);

		return (RIfloat)(((const RIfloat32*)ptr)[i]) * m_scale + m_bias;

	}

}

/*-------------------------------------------------------------------*//*!

* \brief	Writes a coordinate, subtracting bias and dividing out scale.

* \param	

* \return	

* \note		If the coordinates do not fit into path datatype range, they

*			will overflow silently.

*//*-------------------------------------------------------------------*/

void Path::setCoordinate(Array<RIuint8>& data, VGPathDatatype datatype, RIfloat scale, RIfloat bias, int i, RIfloat c)

{

	RI_ASSERT(i >= 0 && i < data.size()/getBytesPerCoordinate(datatype));

	RI_ASSERT(scale != 0.0f);

	c -= bias;

	c /= scale;

	RIuint8* ptr = &data[0];

	switch(datatype)

	{

	case VG_PATH_DATATYPE_S_8:

		((RIint8*)ptr)[i] = (RIint8)floor(c + 0.5f);	//add 0.5 for correct rounding

		break;

	case VG_PATH_DATATYPE_S_16:

		((RIint16*)ptr)[i] = (RIint16)floor(c + 0.5f);	//add 0.5 for correct rounding

		break;

	case VG_PATH_DATATYPE_S_32:

		((RIint32*)ptr)[i] = (RIint32)floor(c + 0.5f);	//add 0.5 for correct rounding

		break;

	default:

		RI_ASSERT(datatype == VG_PATH_DATATYPE_F);

		((RIfloat32*)ptr)[i] = (RIfloat32)c;

		break;

	}

}

/*-------------------------------------------------------------------*//*!

* \brief	Given a datatype, returns the number of bytes per coordinate.

* \param	

* \return	

* \note		

*//*-------------------------------------------------------------------*/

int Path::getBytesPerCoordinate(VGPathDatatype datatype)

{

	if(datatype == VG_PATH_DATATYPE_S_8)

		return 1;

	if(datatype == VG_PATH_DATATYPE_S_16)

		return 2;

	RI_ASSERT(datatype == VG_PATH_DATATYPE_S_32 || datatype == VG_PATH_DATATYPE_F);

	return 4;

}

/*-------------------------------------------------------------------*//*!

* \brief	Given a path segment type, returns the number of coordinates

*			it uses.

* \param	

* \return	

* \note		

*//*-------------------------------------------------------------------*/

int Path::segmentToNumCoordinates(VGPathSegment segment)

{

	RI_ASSERT(((int)segment >> 1) >= 0 && ((int)segment >> 1) <= 12);

	static const int coords[13] = {0,2,2,1,1,4,6,2,4,5,5,5,5};

	return coords[(int)segment >> 1];

}

/*-------------------------------------------------------------------*//*!

* \brief	Computes the number of coordinates a segment sequence uses.

* \param	

* \return	

* \note		

*//*-------------------------------------------------------------------*/

int Path::countNumCoordinates(const RIuint8* segments, int numSegments)

{

	RI_ASSERT(segments);

	RI_ASSERT(numSegments >= 0);

	int coordinates = 0;

	for(int i=0;i<numSegments;i++)

		coordinates += segmentToNumCoordinates(getPathSegment(segments[i]));

	return coordinates;

}

/*-------------------------------------------------------------------*//*!

* \brief	Clears path segments and data, and resets capabilities.

* \param	

* \return	

* \note		

*//*-------------------------------------------------------------------*/

void Path::clear(VGbitfield capabilities)

{

	m_segments.clear();

	m_data.clear();

	m_capabilities = capabilities;

}

/*-------------------------------------------------------------------*//*!

* \brief	Appends user segments and data.

* \param	

* \return	

* \note		if runs out of memory, throws bad_alloc and leaves the path as it was

*//*-------------------------------------------------------------------*/

void Path::appendData(const RIuint8* segments, int numSegments, const RIuint8* data)

{

	RI_ASSERT(numSegments > 0);

	RI_ASSERT(segments && data);

	RI_ASSERT(m_referenceCount > 0);

	//allocate new arrays

	int oldSegmentsSize = m_segments.size();

	int newSegmentsSize = oldSegmentsSize + numSegments;

	Array<RIuint8> newSegments;

	newSegments.resize(newSegmentsSize);	//throws bad_alloc

	int newCoords = countNumCoordinates(segments, numSegments);

	int bytesPerCoordinate = getBytesPerCoordinate(m_datatype);

	int newDataSize = m_data.size() + newCoords * bytesPerCoordinate;

	Array<RIuint8> newData;

	newData.resize(newDataSize);	//throws bad_alloc

	//if we get here, the memory allocations have succeeded

	//copy old segments and append new ones

	if(m_segments.size())

		memcpy(&newSegments[0], &m_segments[0], m_segments.size());

	memcpy(&newSegments[0] + m_segments.size(), segments, numSegments);

	//copy old data and append new ones

	if(newData.size())

	{

		if(m_data.size())

			memcpy(&newData[0], &m_data[0], m_data.size());

		if(m_datatype == VG_PATH_DATATYPE_F)

		{

			RIfloat32* d = (RIfloat32*)(&newData[0] + m_data.size());

			const RIfloat32* s = (const RIfloat32*)data;

			for(int i=0;i<newCoords;i++)

				*d++ = (RIfloat32)inputFloat(*s++);

		}

		else

		{

			memcpy(&newData[0] + m_data.size(), data, newCoords * bytesPerCoordinate);

		}

	}

	RI_ASSERT(newData.size() == countNumCoordinates(&newSegments[0],newSegments.size()) * getBytesPerCoordinate(m_datatype));

	//replace old arrays

	m_segments.swap(newSegments);

	m_data.swap(newData);

	int c = 0;

	for(int i=0;i<m_segments.size();i++)

	{

		VGPathSegment segment = getPathSegment(m_segments[i]);

		int coords = segmentToNumCoordinates(segment);

		c += coords;

	}

}

/*-------------------------------------------------------------------*//*!

* \brief	Appends a path.

* \param	

* \return	

* \note		if runs out of memory, throws bad_alloc and leaves the path as it was

*//*-------------------------------------------------------------------*/

void Path::append(const Path* srcPath)

{

	RI_ASSERT(srcPath);

	RI_ASSERT(m_referenceCount > 0 && srcPath->m_referenceCount > 0);

	if(srcPath->m_segments.size())

	{

		//allocate new arrays

		int newSegmentsSize = m_segments.size() + srcPath->m_segments.size();

		Array<RIuint8> newSegments;

		newSegments.resize(newSegmentsSize);	//throws bad_alloc

		int newDataSize = m_data.size() + srcPath->getNumCoordinates() * getBytesPerCoordinate(m_datatype);

		Array<RIuint8> newData;

		newData.resize(newDataSize);	//throws bad_alloc

		//if we get here, the memory allocations have succeeded

		//copy old segments and append new ones

		if(m_segments.size())

			memcpy(&newSegments[0], &m_segments[0], m_segments.size());

		if(srcPath->m_segments.size())

			memcpy(&newSegments[0] + m_segments.size(), &srcPath->m_segments[0], srcPath->m_segments.size());

		//copy old data and append new ones

		if(m_data.size())

			memcpy(&newData[0], &m_data[0], m_data.size());

		for(int i=0;i<srcPath->getNumCoordinates();i++)

			setCoordinate(newData, m_datatype, m_scale, m_bias, i + getNumCoordinates(), srcPath->getCoordinate(i));

		RI_ASSERT(newData.size() == countNumCoordinates(&newSegments[0],newSegments.size()) * getBytesPerCoordinate(m_datatype));

		//replace old arrays

		m_segments.swap(newSegments);

		m_data.swap(newData);

	}

}

/*-------------------------------------------------------------------*//*!

* \brief	Modifies existing coordinate data.

* \param	

* \return	

* \note		

*//*-------------------------------------------------------------------*/

void Path::modifyCoords(int startIndex, int numSegments, const RIuint8* data)

{

	RI_ASSERT(numSegments > 0);

	RI_ASSERT(startIndex >= 0 && startIndex + numSegments <= m_segments.size());

	RI_ASSERT(data);

	RI_ASSERT(m_referenceCount > 0);

	int startCoord = countNumCoordinates(&m_segments[0], startIndex);

	int numCoords = countNumCoordinates(&m_segments[startIndex], numSegments);

	if(!numCoords)

		return;

	int bytesPerCoordinate = getBytesPerCoordinate(m_datatype);

	RIuint8* dst = &m_data[startCoord * bytesPerCoordinate];

	if(m_datatype == VG_PATH_DATATYPE_F)

	{

		RIfloat32* d = (RIfloat32*)dst;

		const RIfloat32* s = (const RIfloat32*)data;

		for(int i=0;i<numCoords;i++)

			*d++ = (RIfloat32)inputFloat(*s++);

	}

	else

	{

		memcpy(dst, data, numCoords*bytesPerCoordinate);

	}

}

/*-------------------------------------------------------------------*//*!

* \brief	Appends a transformed copy of the source path.

* \param	

* \return	

* \note		if runs out of memory, throws bad_alloc and leaves the path as it was

*//*-------------------------------------------------------------------*/

void Path::transform(const Path* srcPath, const Matrix3x3& matrix)

{

	RI_ASSERT(srcPath);

	RI_ASSERT(m_referenceCount > 0 && srcPath->m_referenceCount > 0);

	RI_ASSERT(matrix.isAffine());

	if(!srcPath->m_segments.size())

		return;

	//count the number of resulting coordinates

	int numSrcCoords = 0;

	int numDstCoords = 0;

	for(int i=0;i<srcPath->m_segments.size();i++)

	{

		VGPathSegment segment = getPathSegment(srcPath->m_segments[i]);

		int coords = segmentToNumCoordinates(segment);

		numSrcCoords += coords;

		if(segment == VG_HLINE_TO || segment == VG_VLINE_TO)

			coords = 2;	//convert hline and vline to lines

		numDstCoords += coords;

	}

	//allocate new arrays

	Array<RIuint8> newSegments;

	newSegments.resize(m_segments.size() + srcPath->m_segments.size());	//throws bad_alloc

	Array<RIuint8> newData;

	newData.resize(m_data.size() + numDstCoords * getBytesPerCoordinate(m_datatype));	//throws bad_alloc

	//if we get here, the memory allocations have succeeded

	//copy old segments

	if(m_segments.size())

		memcpy(&newSegments[0], &m_segments[0], m_segments.size());

	//copy old data

	if(m_data.size())

		memcpy(&newData[0], &m_data[0], m_data.size());

	int srcCoord = 0;

	int dstCoord = getNumCoordinates();

	Vector2 s(0,0);		//the beginning of the current subpath

	Vector2 o(0,0);		//the last point of the previous segment

	for(int i=0;i<srcPath->m_segments.size();i++)

	{

		VGPathSegment segment = getPathSegment(srcPath->m_segments[i]);

		VGPathAbsRel absRel = getPathAbsRel(srcPath->m_segments[i]);