diff -r 39e5f73667ba -r c2ef9095503a hostsupport/hostopenvg/src/riPath.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/hostsupport/hostopenvg/src/riPath.cpp Wed Oct 06 17:59:01 2010 +0100 @@ -0,0 +1,2779 @@ +/*------------------------------------------------------------------------ + * + * OpenVG 1.1 Reference Implementation + * ----------------------------------- + * + * Copyright (c) 2007 The Khronos Group Inc. + * Portions copyright (c) 2010 Nokia Corporation and/or its subsidiary(-ies). + * + * 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& data, VGPathDatatype datatype, RIfloat scale, RIfloat bias, int i, RIfloat c) +{ + RI_ASSERT(i >= 0 && i < data.size()/getBytesPerCoordinate(datatype)); + RI_ASSERT(!RI_ISNAN(scale)); + RI_ASSERT(!RI_ISNAN(bias)); + RI_ASSERT(scale != 0.0f); + + c = inputFloat(c); // Revalidate: Can happen when a coordinate has been transformed. + c -= bias; + c /= scale; + + RI_ASSERT(!RI_ISNAN(c)); + + 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 0); + RI_ASSERT(segments && data); + RI_ASSERT(m_referenceCount > 0); + + //allocate new arrays + int oldSegmentsSize = m_segments.size(); + int newSegmentsSize = oldSegmentsSize + numSegments; + Array 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 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()) + ri_memcpy(&newSegments[0], &m_segments[0], m_segments.size()); + ri_memcpy(&newSegments[0] + m_segments.size(), segments, numSegments); + + //copy old data and append new ones + if(newData.size()) + { + if(m_data.size()) + ri_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 0 && srcPath->m_referenceCount > 0); + + if(srcPath->m_segments.size()) + { + //allocate new arrays + int newSegmentsSize = m_segments.size() + srcPath->m_segments.size(); + Array newSegments; + newSegments.resize(newSegmentsSize); //throws bad_alloc + + int newDataSize = m_data.size() + srcPath->getNumCoordinates() * getBytesPerCoordinate(m_datatype); + Array 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()) + ri_memcpy(&newSegments[0], &m_segments[0], m_segments.size()); + if(srcPath->m_segments.size()) + ri_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()) + ri_memcpy(&newData[0], &m_data[0], m_data.size()); + for(int i=0;igetNumCoordinates();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); + } +} + +int Path::coordsSizeInBytes( int startIndex, int numSegments ) + { + RI_ASSERT(numSegments > 0); + RI_ASSERT(startIndex >= 0 && startIndex + numSegments <= m_segments.size()); + RI_ASSERT(m_referenceCount > 0); + + int numCoords = countNumCoordinates(&m_segments[startIndex], numSegments); + if(!numCoords) + return 0; + int bytesPerCoordinate = getBytesPerCoordinate(m_datatype); + return (numCoords * bytesPerCoordinate); + } + +/*-------------------------------------------------------------------*//*! +* \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 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;im_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 newSegments; + newSegments.resize(m_segments.size() + srcPath->m_segments.size()); //throws bad_alloc + Array 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()) + ri_memcpy(&newSegments[0], &m_segments[0], m_segments.size()); + + //copy old data + if(m_data.size()) + ri_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;im_segments.size();i++) + { + VGPathSegment segment = getPathSegment(srcPath->m_segments[i]); + VGPathAbsRel absRel = getPathAbsRel(srcPath->m_segments[i]); + int coords = segmentToNumCoordinates(segment); + + switch(segment) + { + case VG_CLOSE_PATH: + { + RI_ASSERT(coords == 0); + o = s; + break; + } + + case VG_MOVE_TO: + { + RI_ASSERT(coords == 2); + Vector2 c(srcPath->getCoordinate(srcCoord+0), srcPath->getCoordinate(srcCoord+1)); + Vector2 tc; + + if (absRel == VG_ABSOLUTE) + tc = affineTransform(matrix, c); + else + { + tc = affineTangentTransform(matrix, c); + c += o; + } + + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc.x); + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc.y); + s = c; + o = c; + break; + } + + case VG_LINE_TO: + { + RI_ASSERT(coords == 2); + Vector2 c(srcPath->getCoordinate(srcCoord+0), srcPath->getCoordinate(srcCoord+1)); + Vector2 tc; + + if (absRel == VG_ABSOLUTE) + tc = affineTransform(matrix, c); + else + { + tc = affineTangentTransform(matrix, c); + c += o; + } + + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc.x); + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc.y); + o = c; + break; + } + + case VG_HLINE_TO: + { + RI_ASSERT(coords == 1); + Vector2 c(srcPath->getCoordinate(srcCoord+0), 0); + Vector2 tc; + + if (absRel == VG_ABSOLUTE) + { + c.y = o.y; + tc = affineTransform(matrix, c); + } + else + { + tc = affineTangentTransform(matrix, c); + c += o; + } + + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc.x); + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc.y); + o = c; + segment = VG_LINE_TO; + break; + } + + case VG_VLINE_TO: + { + RI_ASSERT(coords == 1); + Vector2 c(0, srcPath->getCoordinate(srcCoord+0)); + Vector2 tc; + + if (absRel == VG_ABSOLUTE) + { + c.x = o.x; + tc = affineTransform(matrix, c); + } + else + { + tc = affineTangentTransform(matrix, c); + c += o; + } + + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc.x); + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc.y); + o = c; + segment = VG_LINE_TO; + break; + } + + case VG_QUAD_TO: + { + RI_ASSERT(coords == 4); + Vector2 c0(srcPath->getCoordinate(srcCoord+0), srcPath->getCoordinate(srcCoord+1)); + Vector2 c1(srcPath->getCoordinate(srcCoord+2), srcPath->getCoordinate(srcCoord+3)); + Vector2 tc0, tc1; + + if (absRel == VG_ABSOLUTE) + { + tc0 = affineTransform(matrix, c0); + tc1 = affineTransform(matrix, c1); + } + else + { + tc0 = affineTangentTransform(matrix, c0); + tc1 = affineTangentTransform(matrix, c1); + c1 += o; + } + + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc0.x); + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc0.y); + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc1.x); + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc1.y); + o = c1; + break; + } + + case VG_CUBIC_TO: + { + RI_ASSERT(coords == 6); + Vector2 c0(srcPath->getCoordinate(srcCoord+0), srcPath->getCoordinate(srcCoord+1)); + Vector2 c1(srcPath->getCoordinate(srcCoord+2), srcPath->getCoordinate(srcCoord+3)); + Vector2 c2(srcPath->getCoordinate(srcCoord+4), srcPath->getCoordinate(srcCoord+5)); + Vector2 tc0, tc1, tc2; + + if (absRel == VG_ABSOLUTE) + { + tc0 = affineTransform(matrix, c0); + tc1 = affineTransform(matrix, c1); + tc2 = affineTransform(matrix, c2); + } + else + { + tc0 = affineTangentTransform(matrix, c0); + tc1 = affineTangentTransform(matrix, c1); + tc2 = affineTangentTransform(matrix, c2); + c2 += o; + } + + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc0.x); + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc0.y); + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc1.x); + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc1.y); + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc2.x); + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc2.y); + o = c2; + break; + } + + case VG_SQUAD_TO: + { + RI_ASSERT(coords == 2); + Vector2 c1(srcPath->getCoordinate(srcCoord+0), srcPath->getCoordinate(srcCoord+1)); + Vector2 tc1; + + if (absRel == VG_ABSOLUTE) + tc1 = affineTransform(matrix, c1); + else + { + tc1 = affineTangentTransform(matrix, c1); + c1 += o; + } + + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc1.x); + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc1.y); + o = c1; + break; + } + + case VG_SCUBIC_TO: + { + RI_ASSERT(coords == 4); + Vector2 c1(srcPath->getCoordinate(srcCoord+0), srcPath->getCoordinate(srcCoord+1)); + Vector2 c2(srcPath->getCoordinate(srcCoord+2), srcPath->getCoordinate(srcCoord+3)); + Vector2 tc1, tc2; + + if (absRel == VG_ABSOLUTE) + { + tc1 = affineTransform(matrix, c1); + tc2 = affineTransform(matrix, c2); + } + else + { + tc1 = affineTangentTransform(matrix, c1); + tc2 = affineTangentTransform(matrix, c2); + c2 += o; + } + + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc1.x); + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc1.y); + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc2.x); + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc2.y); + o = c2; + break; + } + + default: + { + RI_ASSERT(segment == VG_SCCWARC_TO || segment == VG_SCWARC_TO || + segment == VG_LCCWARC_TO || segment == VG_LCWARC_TO); + RI_ASSERT(coords == 5); + RIfloat rh = srcPath->getCoordinate(srcCoord+0); + RIfloat rv = srcPath->getCoordinate(srcCoord+1); + RIfloat rot = srcPath->getCoordinate(srcCoord+2); + Vector2 c(srcPath->getCoordinate(srcCoord+3), srcPath->getCoordinate(srcCoord+4)); + + rot = RI_DEG_TO_RAD(rot); + Matrix3x3 u((RIfloat)cos(rot)*rh, -(RIfloat)sin(rot)*rv, 0, + (RIfloat)sin(rot)*rh, (RIfloat)cos(rot)*rv, 0, + 0, 0, 1); + u = matrix * u; + u[2].set(0,0,1); //force affinity + //u maps from the unit circle to transformed ellipse + + //compute new rh, rv and rot + Vector2 p(u[0][0], u[1][0]); + Vector2 q(u[1][1], -u[0][1]); + bool swapped = false; + if(dot(p,p) < dot(q,q)) + { + RI_SWAP(p.x,q.x); + RI_SWAP(p.y,q.y); + swapped = true; + } + Vector2 h = (p+q) * 0.5f; + Vector2 hp = (p-q) * 0.5f; + RIfloat hlen = h.length(); + RIfloat hplen = hp.length(); + rh = hlen + hplen; + rv = hlen - hplen; + + if (RI_ISNAN(rh)) rh = 0.0f; + if (RI_ISNAN(rv)) rv = 0.0f; + + h = hplen * h + hlen * hp; + hlen = dot(h,h); + if(hlen == 0.0f) + rot = 0.0f; + else + { + h.normalize(); + rot = (RIfloat)acos(h.x); + if(h.y < 0.0f) + rot = 2.0f*RI_PI - rot; + if (RI_ISNAN(rot)) + rot = 0.0f; + } + if(swapped) + rot += RI_PI*0.5f; + + Vector2 tc; + if (absRel == VG_ABSOLUTE) + tc = affineTransform(matrix, c); + else + { + tc = affineTangentTransform(matrix, c); + c += o; + } + + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, rh); + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, rv); + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, RI_RAD_TO_DEG(rot)); + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc.x); + setCoordinate(newData, m_datatype, m_scale, m_bias, dstCoord++, tc.y); + o = c; + + //flip winding if the determinant is negative + if (matrix.det() < 0) + { + switch (segment) + { + case VG_SCCWARC_TO: segment = VG_SCWARC_TO; break; + case VG_SCWARC_TO: segment = VG_SCCWARC_TO; break; + case VG_LCCWARC_TO: segment = VG_LCWARC_TO; break; + case VG_LCWARC_TO: segment = VG_LCCWARC_TO; break; + default: break; + } + } + break; + } + } + + newSegments[m_segments.size() + i] = (RIuint8)(segment | absRel); + srcCoord += coords; + } + RI_ASSERT(srcCoord == numSrcCoords); + RI_ASSERT(dstCoord == getNumCoordinates() + numDstCoords); + + RI_ASSERT(newData.size() == countNumCoordinates(&newSegments[0],newSegments.size()) * getBytesPerCoordinate(m_datatype)); + + //replace old arrays + m_segments.swap(newSegments); + m_data.swap(newData); +} + +/*-------------------------------------------------------------------*//*! +* \brief Normalizes a path for interpolation. +* \param +* \return +* \note +*//*-------------------------------------------------------------------*/ + +void Path::normalizeForInterpolation(const Path* srcPath) +{ + RI_ASSERT(srcPath); + RI_ASSERT(srcPath != this); + RI_ASSERT(srcPath->m_referenceCount > 0); + + //count the number of resulting coordinates + int numSrcCoords = 0; + int numDstCoords = 0; + for(int i=0;im_segments.size();i++) + { + VGPathSegment segment = getPathSegment(srcPath->m_segments[i]); + int coords = segmentToNumCoordinates(segment); + numSrcCoords += coords; + switch(segment) + { + case VG_CLOSE_PATH: + case VG_MOVE_TO: + case VG_LINE_TO: + break; + + case VG_HLINE_TO: + case VG_VLINE_TO: + coords = 2; + break; + + case VG_QUAD_TO: + case VG_CUBIC_TO: + case VG_SQUAD_TO: + case VG_SCUBIC_TO: + coords = 6; + break; + + default: + RI_ASSERT(segment == VG_SCCWARC_TO || segment == VG_SCWARC_TO || + segment == VG_LCCWARC_TO || segment == VG_LCWARC_TO); + break; + } + numDstCoords += coords; + } + + m_segments.resize(srcPath->m_segments.size()); //throws bad_alloc + m_data.resize(numDstCoords * getBytesPerCoordinate(VG_PATH_DATATYPE_F)); //throws bad_alloc + + int srcCoord = 0; + int dstCoord = 0; + Vector2 s(0,0); //the beginning of the current subpath + Vector2 o(0,0); //the last point of the previous segment + + // the last internal control point of the previous segment, if the + //segment was a (regular or smooth) quadratic or cubic + //Bezier, or else the last point of the previous segment + Vector2 p(0,0); + for(int i=0;im_segments.size();i++) + { + VGPathSegment segment = getPathSegment(srcPath->m_segments[i]); + VGPathAbsRel absRel = getPathAbsRel(srcPath->m_segments[i]); + int coords = segmentToNumCoordinates(segment); + + switch(segment) + { + case VG_CLOSE_PATH: + { + RI_ASSERT(coords == 0); + p = s; + o = s; + break; + } + + case VG_MOVE_TO: + { + RI_ASSERT(coords == 2); + Vector2 c(srcPath->getCoordinate(srcCoord+0), srcPath->getCoordinate(srcCoord+1)); + if(absRel == VG_RELATIVE) + c += o; + setCoordinate(dstCoord++, c.x); + setCoordinate(dstCoord++, c.y); + s = c; + p = c; + o = c; + break; + } + + case VG_LINE_TO: + { + RI_ASSERT(coords == 2); + Vector2 c(srcPath->getCoordinate(srcCoord+0), srcPath->getCoordinate(srcCoord+1)); + if(absRel == VG_RELATIVE) + c += o; + setCoordinate(dstCoord++, c.x); + setCoordinate(dstCoord++, c.y); + p = c; + o = c; + break; + } + + case VG_HLINE_TO: + { + RI_ASSERT(coords == 1); + Vector2 c(srcPath->getCoordinate(srcCoord+0), o.y); + if(absRel == VG_RELATIVE) + c.x += o.x; + setCoordinate(dstCoord++, c.x); + setCoordinate(dstCoord++, c.y); + p = c; + o = c; + segment = VG_LINE_TO; + break; + } + + case VG_VLINE_TO: + { + RI_ASSERT(coords == 1); + Vector2 c(o.x, srcPath->getCoordinate(srcCoord+0)); + if(absRel == VG_RELATIVE) + c.y += o.y; + setCoordinate(dstCoord++, c.x); + setCoordinate(dstCoord++, c.y); + p = c; + o = c; + segment = VG_LINE_TO; + break; + } + + case VG_QUAD_TO: + { + RI_ASSERT(coords == 4); + Vector2 c0(srcPath->getCoordinate(srcCoord+0), srcPath->getCoordinate(srcCoord+1)); + Vector2 c1(srcPath->getCoordinate(srcCoord+2), srcPath->getCoordinate(srcCoord+3)); + if(absRel == VG_RELATIVE) + { + c0 += o; + c1 += o; + } + Vector2 d0 = (1.0f/3.0f) * (o + 2.0f * c0); + Vector2 d1 = (1.0f/3.0f) * (c1 + 2.0f * c0); + setCoordinate(dstCoord++, d0.x); + setCoordinate(dstCoord++, d0.y); + setCoordinate(dstCoord++, d1.x); + setCoordinate(dstCoord++, d1.y); + setCoordinate(dstCoord++, c1.x); + setCoordinate(dstCoord++, c1.y); + p = c0; + o = c1; + segment = VG_CUBIC_TO; + break; + } + + case VG_CUBIC_TO: + { + RI_ASSERT(coords == 6); + Vector2 c0(srcPath->getCoordinate(srcCoord+0), srcPath->getCoordinate(srcCoord+1)); + Vector2 c1(srcPath->getCoordinate(srcCoord+2), srcPath->getCoordinate(srcCoord+3)); + Vector2 c2(srcPath->getCoordinate(srcCoord+4), srcPath->getCoordinate(srcCoord+5)); + if(absRel == VG_RELATIVE) + { + c0 += o; + c1 += o; + c2 += o; + } + setCoordinate(dstCoord++, c0.x); + setCoordinate(dstCoord++, c0.y); + setCoordinate(dstCoord++, c1.x); + setCoordinate(dstCoord++, c1.y); + setCoordinate(dstCoord++, c2.x); + setCoordinate(dstCoord++, c2.y); + p = c1; + o = c2; + break; + } + + case VG_SQUAD_TO: + { + RI_ASSERT(coords == 2); + Vector2 c0 = 2.0f * o - p; + Vector2 c1(srcPath->getCoordinate(srcCoord+0), srcPath->getCoordinate(srcCoord+1)); + if(absRel == VG_RELATIVE) + c1 += o; + Vector2 d0 = (1.0f/3.0f) * (o + 2.0f * c0); + Vector2 d1 = (1.0f/3.0f) * (c1 + 2.0f * c0); + setCoordinate(dstCoord++, d0.x); + setCoordinate(dstCoord++, d0.y); + setCoordinate(dstCoord++, d1.x); + setCoordinate(dstCoord++, d1.y); + setCoordinate(dstCoord++, c1.x); + setCoordinate(dstCoord++, c1.y); + p = c0; + o = c1; + segment = VG_CUBIC_TO; + break; + } + + case VG_SCUBIC_TO: + { + RI_ASSERT(coords == 4); + Vector2 c0 = 2.0f * o - p; + Vector2 c1(srcPath->getCoordinate(srcCoord+0), srcPath->getCoordinate(srcCoord+1)); + Vector2 c2(srcPath->getCoordinate(srcCoord+2), srcPath->getCoordinate(srcCoord+3)); + if(absRel == VG_RELATIVE) + { + c1 += o; + c2 += o; + } + setCoordinate(dstCoord++, c0.x); + setCoordinate(dstCoord++, c0.y); + setCoordinate(dstCoord++, c1.x); + setCoordinate(dstCoord++, c1.y); + setCoordinate(dstCoord++, c2.x); + setCoordinate(dstCoord++, c2.y); + p = c1; + o = c2; + segment = VG_CUBIC_TO; + break; + } + + default: + { + RI_ASSERT(segment == VG_SCCWARC_TO || segment == VG_SCWARC_TO || + segment == VG_LCCWARC_TO || segment == VG_LCWARC_TO); + RI_ASSERT(coords == 5); + RIfloat rh = srcPath->getCoordinate(srcCoord+0); + RIfloat rv = srcPath->getCoordinate(srcCoord+1); + RIfloat rot = srcPath->getCoordinate(srcCoord+2); + Vector2 c(srcPath->getCoordinate(srcCoord+3), srcPath->getCoordinate(srcCoord+4)); + if(absRel == VG_RELATIVE) + c += o; + setCoordinate(dstCoord++, rh); + setCoordinate(dstCoord++, rv); + setCoordinate(dstCoord++, rot); + setCoordinate(dstCoord++, c.x); + setCoordinate(dstCoord++, c.y); + p = c; + o = c; + break; + } + } + + m_segments[i] = (RIuint8)(segment | VG_ABSOLUTE); + srcCoord += coords; + } + RI_ASSERT(srcCoord == numSrcCoords); + RI_ASSERT(dstCoord == numDstCoords); +} + +/*-------------------------------------------------------------------*//*! +* \brief Appends a linearly interpolated copy of the two source paths. +* \param +* \return +* \note if runs out of memory, throws bad_alloc and leaves the path as it was +*//*-------------------------------------------------------------------*/ + +bool Path::interpolate(const Path* startPath, const Path* endPath, RIfloat amount) +{ + RI_ASSERT(startPath && endPath); + RI_ASSERT(m_referenceCount > 0 && startPath->m_referenceCount > 0 && endPath->m_referenceCount > 0); + + if(!startPath->m_segments.size() || startPath->m_segments.size() != endPath->m_segments.size()) + return false; //start and end paths are incompatible or zero length + + Path start(VG_PATH_FORMAT_STANDARD, VG_PATH_DATATYPE_F, 1.0f, 0.0f, 0, 0, 0); + start.normalizeForInterpolation(startPath); //throws bad_alloc + + Path end(VG_PATH_FORMAT_STANDARD, VG_PATH_DATATYPE_F, 1.0f, 0.0f, 0, 0, 0); + end.normalizeForInterpolation(endPath); //throws bad_alloc + + //check that start and end paths are compatible + if(start.m_data.size() != end.m_data.size() || start.m_segments.size() != end.m_segments.size()) + return false; //start and end paths are incompatible + + //allocate new arrays + Array newSegments; + newSegments.resize(m_segments.size() + start.m_segments.size()); //throws bad_alloc + Array newData; + newData.resize(m_data.size() + start.m_data.size() * getBytesPerCoordinate(m_datatype) / getBytesPerCoordinate(start.m_datatype)); //throws bad_alloc + //if we get here, the memory allocations have succeeded + + //copy old segments + if(m_segments.size()) + ri_memcpy(&newSegments[0], &m_segments[0], m_segments.size()); + + //copy old data + if(m_data.size()) + ri_memcpy(&newData[0], &m_data[0], m_data.size()); + + //copy segments + for(int i=0;i 0); + RI_ASSERT(pathToSurface.isAffine()); + + tessellate(pathToSurface, 0.0f); //throws bad_alloc + + try + { + Vector2 p0(0,0), p1(0,0); + for(int i=0;ip1) and (p2->p3) + * \todo This must be done in the rasterizer to get correct results. + */ +static void intersectLines(const Vector2& p0, const Vector2& p1, const Vector2& p2, const Vector2& p3, Vector2& pt) +{ + RIfloat n = (p1.x-p0.x)*(p0.y-p2.y)-(p1.y-p0.y)*(p0.x-p2.x); + RIfloat d = (p3.y-p2.y)*(p1.x-p0.x)-(p3.x-p2.x)*(p1.y-p0.y); + if (d == 0) + { + pt = p0; + return; + } + RIfloat t = n/d; + Vector2 dir = p1-p0; + + pt = p0+t*dir; +} + +static bool isCCW(const Vector2& a, const Vector2& b) +{ + RIfloat c = a.x*b.y - a.y*b.x; + return c >= 0; +} + +/** + * \brief Add a CCW stitch-triangle so that accw -> acw is the base of the triangle. + * \param accw Counter-clockwise stroke end (for example). + * \param acw Clockwise stroke end. + * \param p Tip of the triangle to form. + */ +static void addStitchTriangle(Rasterizer& rasterizer, const Vector2& accw, const Vector2& acw, const Vector2& p) +{ + if (isCCW(p - accw, acw - accw)) + { + // p "below" + rasterizer.addEdge(accw, p); + rasterizer.addEdge(p, acw); + rasterizer.addEdge(acw, accw); + } + else + { + rasterizer.addEdge(accw, acw); + rasterizer.addEdge(acw, p); + rasterizer.addEdge(p, accw); + } +} + +/** + * \brief Add a (ccw-closed) segment to path. See the naming of parameters for input order: + * pp = previous, nn = next + */ +static void addStrokeSegment(Rasterizer& rasterizer, const Vector2& ppccw, const Vector2& ppcw, const Vector2& nnccw, const Vector2& nncw) +{ + RIfloat d = dot(nnccw-ppccw, nncw-ppcw); + if(d < 0) + { + Vector2 ip; + intersectLines(ppccw, ppcw, nnccw, nncw, ip); + + // Create two triangles from the self-intersecting part + if (isCCW(ppccw - nnccw, ip - nnccw)) + { + rasterizer.addEdge(nnccw, ppccw); + rasterizer.addEdge(ppccw, ip); + rasterizer.addEdge(ip, nnccw); + + rasterizer.addEdge(nncw, ppcw); + rasterizer.addEdge(ppcw, ip); + rasterizer.addEdge(ip, nncw); + } + else + { + rasterizer.addEdge(nnccw, ip); + rasterizer.addEdge(ip, ppccw); + rasterizer.addEdge(ppccw, nnccw); + + rasterizer.addEdge(nncw, ip); + rasterizer.addEdge(ip, ppcw); + rasterizer.addEdge(ppcw, nncw); + } + // Final stitch (not necessary if done in the rasterizer) + addStitchTriangle(rasterizer, ppccw, ppcw, ip); + addStitchTriangle(rasterizer, nnccw, nncw, ip); + } + else + { + rasterizer.addEdge(ppccw, ppcw); //throws bad_alloc + rasterizer.addEdge(ppcw, nncw); //throws bad_alloc + rasterizer.addEdge(nncw, nnccw); //throws bad_alloc + rasterizer.addEdge(nnccw, ppccw); //throws bad_alloc + } +} + +/*-------------------------------------------------------------------*//*! +* \brief Smoothly interpolates between two StrokeVertices. Positions +* are interpolated linearly, while tangents are interpolated +* on a unit circle. Stroking is implemented so that overlapping +* geometry doesnt cancel itself when filled with nonzero rule. +* The resulting polygons are closed. +* \param +* \return +* \note +*//*-------------------------------------------------------------------*/ + +void Path::interpolateStroke(const Matrix3x3& pathToSurface, Rasterizer& rasterizer, const StrokeVertex& v0, const StrokeVertex& v1, RIfloat strokeWidth) const +{ + Vector2 ppccw, endccw; + Vector2 ppcw, endcw; + + if (m_mirror) + { + ppccw = affineTransform(pathToSurface, v0.cw); + ppcw = affineTransform(pathToSurface, v0.ccw); + endccw = affineTransform(pathToSurface, v1.cw); + endcw = affineTransform(pathToSurface, v1.ccw); + } + else + { + ppccw = affineTransform(pathToSurface, v0.ccw); + ppcw = affineTransform(pathToSurface, v0.cw); + endccw = affineTransform(pathToSurface, v1.ccw); + endcw = affineTransform(pathToSurface, v1.cw); + } + + const RIfloat tessellationAngle = 5.0f; + + RIfloat angle = RI_RAD_TO_DEG((RIfloat)acos(RI_CLAMP(dot(v0.t, v1.t), -1.0f, 1.0f))) / tessellationAngle; + int samples = RI_INT_MAX((int)ceil(angle), 1); + Vector2 prev = v0.p; + Vector2 prevt = v0.t; + Vector2 position = v0.p; + for(int j=0;j= 0) + cw = false; + + // Add the bevel (which is part of all the other joins also) + // This would be a "consistent" way to handle joins (in addition + // to creating rounding to _both_ side of the join). However, + // the conformance test currently invalidates this case. + // \note Causes some extra geometry. + if (cw) + addStrokeSegment(rasterizer, ccw0t, m0t, ccw1t, m1t); + else + addStrokeSegment(rasterizer, m0t, cw0t, m1t, cw1t); + + switch (joinStyle) + { + case VG_JOIN_BEVEL: + break; + case VG_JOIN_MITER: + { + RIfloat theta = (RIfloat)acos(RI_CLAMP(dot(v0.t, -v1.t), -1.0f, 1.0f)); + RIfloat miterLengthPerStrokeWidth = 1.0f / (RIfloat)sin(theta*0.5f); + if (miterLengthPerStrokeWidth < miterLimit) + { + // Miter + if (cw) + { + m = !mirror ? v0.ccw : v0.cw; + s = ccw1t; + e = ccw0t; + } else + { + m = !mirror ? v0.cw : v0.ccw; + s = cw0t; + e = cw1t; + } + + RIfloat l = (RIfloat)cos(theta*0.5f) * miterLengthPerStrokeWidth * (strokeWidth * 0.5f); + l = RI_MIN(l, RI_FLOAT_MAX); //force finite + Vector2 c = m + v0.t * l; + c = affineTransform(pathToSurface, c); + + rasterizer.addEdge(s, c); + rasterizer.addEdge(c, e); + rasterizer.addEdge(e, s); + } + break; + } + default: + { + RI_ASSERT(joinStyle == VG_JOIN_ROUND); + + Vector2 sp, ep; + + const RIfloat tessellationAngle = 5.0f; + + if (cw) + { + s = ccw1t; + st = -v1.t; + e = ccw0t; + et = -v0.t; + sp = v1.p; + ep = v0.p; + } else + { + s = cw0t; + st = v0.t; + e = cw1t; + et = v1.t; + sp = v0.p; + ep = v1.p; + } + + Vector2 prev = s; + RIfloat angle = RI_RAD_TO_DEG((RIfloat)acos(RI_CLAMP(dot(st, et), -1.0f, 1.0f))) / tessellationAngle; + int samples = (int)ceil(angle); + if( samples ) + { + RIfloat step = 1.0f / samples; + RIfloat t = step; + for(int j=1;j& dashPattern, RIfloat dashPhase, bool dashPhaseReset, RIfloat strokeWidth, VGCapStyle capStyle, VGJoinStyle joinStyle, RIfloat miterLimit) +{ + RI_ASSERT(pathToSurface.isAffine()); + RI_ASSERT(m_referenceCount > 0); + RI_ASSERT(strokeWidth >= 0.0f); + RI_ASSERT(miterLimit >= 1.0f); + + tessellate(pathToSurface, strokeWidth); //throws bad_alloc + + m_mirror = pathToSurface[0][0]*pathToSurface[1][1] < 0 ? true : false; + + if(!m_vertices.size()) + return; + + bool dashing = true; + int dashPatternSize = dashPattern.size(); + if( dashPattern.size() & 1 ) + dashPatternSize--; //odd number of dash pattern entries, discard the last one + RIfloat dashPatternLength = 0.0f; + for(int i=0;i= v1.pathLength) + break; + + if( d & 1 ) + inDash = true; + else + inDash = false; + d = (d+1) % dashPatternSize; + } + v1.inDash = inDash; + //the first point of the path lies between prevDash and nextDash + //d in the index of the next dash stop + //inDash is true if the first point is in a dash + } + } + vs = v1; //save the subpath start point + } + else + { + if( v.flags & IMPLICIT_CLOSE_SUBPATH ) + { //do caps for the start and end of the current subpath + if( v0.inDash ) + doCap(pathToSurface, rasterizer, v0, strokeWidth, capStyle); //end cap //throws bad_alloc + if( vs.inDash ) + { + StrokeVertex vi = vs; + vi.t = -vi.t; + RI_SWAP(vi.ccw.x, vi.cw.x); + RI_SWAP(vi.ccw.y, vi.cw.y); + doCap(pathToSurface, rasterizer, vi, strokeWidth, capStyle); //start cap //throws bad_alloc + } + } + else + { //join two segments + RI_ASSERT(v0.inDash == v1.inDash); + if( v0.inDash ) + doJoin(pathToSurface, rasterizer, v0, v1, strokeWidth, joinStyle, miterLimit); //throws bad_alloc + } + } + } + else + { //in the middle of a segment + if( !(v.flags & IMPLICIT_CLOSE_SUBPATH) ) + { //normal segment, do stroking + if( dashing ) + { + StrokeVertex prevDashVertex = v0; //dashing of the segment starts from the previous vertex + + if(nextDash + 10000.0f * dashPatternLength < v1.pathLength) + throw std::bad_alloc(); //too many dashes, throw bad_alloc + + //loop dash events until the next vertex event + //zero length dashes are handled as a special case since if they hit the vertex, + //we want to include their starting point to this segment already in order to generate a join + int numDashStops = 0; + while(nextDash < v1.pathLength || (nextDash <= v1.pathLength && dashPattern[(d+1) % dashPatternSize] == 0.0f)) + { + RIfloat edgeLength = v1.pathLength - v0.pathLength; + RIfloat ratio = 0.0f; + if(edgeLength > 0.0f) + ratio = (nextDash - v0.pathLength) / edgeLength; + StrokeVertex nextDashVertex; + nextDashVertex.p = v0.p * (1.0f - ratio) + v1.p * ratio; + nextDashVertex.t = circularLerp(v0.t, v1.t, ratio); + nextDashVertex.ccw = nextDashVertex.p + normalize(perpendicularCCW(nextDashVertex.t)) * strokeWidth * 0.5f; + nextDashVertex.cw = nextDashVertex.p + normalize(perpendicularCW(nextDashVertex.t)) * strokeWidth * 0.5f; + + if( inDash ) + { //stroke from prevDashVertex -> nextDashVertex + if( numDashStops ) + { //prevDashVertex is not the start vertex of the segment, cap it (start vertex has already been joined or capped) + StrokeVertex vi = prevDashVertex; + vi.t = -vi.t; + RI_SWAP(vi.ccw.x, vi.cw.x); + RI_SWAP(vi.ccw.y, vi.cw.y); + doCap(pathToSurface, rasterizer, vi, strokeWidth, capStyle); //throws bad_alloc + } + interpolateStroke(pathToSurface, rasterizer, prevDashVertex, nextDashVertex, strokeWidth); //throws bad_alloc + doCap(pathToSurface, rasterizer, nextDashVertex, strokeWidth, capStyle); //end cap //throws bad_alloc + } + prevDashVertex = nextDashVertex; + + if( d & 1 ) + { //dash starts + RI_ASSERT(!inDash); + inDash = true; + } + else + { //dash ends + RI_ASSERT(inDash); + inDash = false; + } + d = (d+1) % dashPatternSize; + nextDash += RI_MAX(dashPattern[d], 0.0f); + numDashStops++; + } + + if( inDash ) + { //stroke prevDashVertex -> v1 + if( numDashStops ) + { //prevDashVertex is not the start vertex of the segment, cap it (start vertex has already been joined or capped) + StrokeVertex vi = prevDashVertex; + vi.t = -vi.t; + RI_SWAP(vi.ccw.x, vi.cw.x); + RI_SWAP(vi.ccw.y, vi.cw.y); + doCap(pathToSurface, rasterizer, vi, strokeWidth, capStyle); //throws bad_alloc + } + interpolateStroke(pathToSurface, rasterizer, prevDashVertex, v1, strokeWidth); //throws bad_alloc + //no cap, leave path open + } + + v1.inDash = inDash; //update inDash status of the segment end point + } + else //no dashing, just interpolate segment end points + interpolateStroke(pathToSurface, rasterizer, v0, v1, strokeWidth); //throws bad_alloc + } + } + + if((v.flags & END_SEGMENT) && (v.flags & CLOSE_SUBPATH)) + { //join start and end of the current subpath + if( v1.inDash && vs.inDash ) + doJoin(pathToSurface, rasterizer, v1, vs, strokeWidth, joinStyle, miterLimit); //throws bad_alloc + else + { //both start and end are not in dash, cap them + if( v1.inDash ) + doCap(pathToSurface, rasterizer, v1, strokeWidth, capStyle); //end cap //throws bad_alloc + if( vs.inDash ) + { + StrokeVertex vi = vs; + vi.t = -vi.t; + RI_SWAP(vi.ccw.x, vi.cw.x); + RI_SWAP(vi.ccw.y, vi.cw.y); + doCap(pathToSurface, rasterizer, vi, strokeWidth, capStyle); //start cap //throws bad_alloc + } + } + } + + v0 = v1; + } + } + catch(std::bad_alloc) + { + rasterizer.clear(); //remove the unfinished path + throw; + } +} + +/*-------------------------------------------------------------------*//*! +* \brief Tessellates a path, and returns a position and a tangent on the path +* given a distance along the path. +* \param +* \return +* \note if runs out of memory, throws bad_alloc and leaves the path as it was +*//*-------------------------------------------------------------------*/ + +void Path::getPointAlong(int startIndex, int numSegments, RIfloat distance, Vector2& p, Vector2& t) +{ + RI_ASSERT(m_referenceCount > 0); + RI_ASSERT(startIndex >= 0 && startIndex + numSegments <= m_segments.size() && numSegments > 0); + + Matrix3x3 identity; + identity.identity(); + tessellate(identity, 0.0f); //throws bad_alloc + + RI_ASSERT(startIndex >= 0 && startIndex < m_segmentToVertex.size()); + RI_ASSERT(startIndex + numSegments >= 0 && startIndex + numSegments <= m_segmentToVertex.size()); + + // ignore move segments at the start of the path + while (numSegments && (m_segments[startIndex] & ~VG_RELATIVE) == VG_MOVE_TO) + { + startIndex++; + numSegments--; + } + + // ignore move segments at the end of the path + while (numSegments && (m_segments[startIndex + numSegments - 1] & ~VG_RELATIVE) == VG_MOVE_TO) + numSegments--; + + // empty path? + if (!m_vertices.size() || !numSegments) + { + p.set(0,0); + t.set(1,0); + return; + } + + int startVertex = m_segmentToVertex[startIndex].start; + int endVertex = m_segmentToVertex[startIndex + numSegments - 1].end; + + if(startVertex == -1) + startVertex = 0; + + // zero length? + if (startVertex >= endVertex) + { + p = m_vertices[startVertex].userPosition; + t.set(1,0); + return; + } + + RI_ASSERT(startVertex >= 0 && startVertex < m_vertices.size()); + RI_ASSERT(endVertex >= 0 && endVertex < m_vertices.size()); + + distance += m_vertices[startVertex].pathLength; //map distance to the range of the whole path + + if(distance <= m_vertices[startVertex].pathLength) + { //return the first point of the path + p = m_vertices[startVertex].userPosition; + t = m_vertices[startVertex].userTangent; + return; + } + + if(distance >= m_vertices[endVertex].pathLength) + { //return the last point of the path + p = m_vertices[endVertex].userPosition; + t = m_vertices[endVertex].userTangent; + return; + } + + //search for the segment containing the distance + for(int s=startIndex;s= 0 && start < m_vertices.size()); + RI_ASSERT(end >= 0 && end < m_vertices.size()); + + if(distance >= m_vertices[start].pathLength && distance < m_vertices[end].pathLength) + { //segment contains the queried distance + for(int i=start;i= v0.pathLength && distance < v1.pathLength) + { //segment found, interpolate linearly between its end points + RIfloat edgeLength = v1.pathLength - v0.pathLength; + RI_ASSERT(edgeLength > 0.0f); + RIfloat r = (distance - v0.pathLength) / edgeLength; + p = (1.0f - r) * v0.userPosition + r * v1.userPosition; + t = (1.0f - r) * v0.userTangent + r * v1.userTangent; + return; + } + } + } + } + + RI_ASSERT(0); //point not found (should never get here) +} + +/*-------------------------------------------------------------------*//*! +* \brief Tessellates a path, and computes its length. +* \param +* \return +* \note if runs out of memory, throws bad_alloc and leaves the path as it was +*//*-------------------------------------------------------------------*/ + +RIfloat Path::getPathLength(int startIndex, int numSegments) +{ + RI_ASSERT(m_referenceCount > 0); + RI_ASSERT(startIndex >= 0 && startIndex + numSegments <= m_segments.size() && numSegments > 0); + + Matrix3x3 identity; + identity.identity(); + tessellate(identity, 0.0f); //throws bad_alloc + + RI_ASSERT(startIndex >= 0 && startIndex < m_segmentToVertex.size()); + RI_ASSERT(startIndex + numSegments >= 0 && startIndex + numSegments <= m_segmentToVertex.size()); + + int startVertex = m_segmentToVertex[startIndex].start; + int endVertex = m_segmentToVertex[startIndex + numSegments - 1].end; + + if(!m_vertices.size()) + return 0.0f; + + RIfloat startPathLength = 0.0f; + if(startVertex >= 0) + { + RI_ASSERT(startVertex >= 0 && startVertex < m_vertices.size()); + startPathLength = m_vertices[startVertex].pathLength; + } + RIfloat endPathLength = 0.0f; + if(endVertex >= 0) + { + RI_ASSERT(endVertex >= 0 && endVertex < m_vertices.size()); + endPathLength = m_vertices[endVertex].pathLength; + } + + return endPathLength - startPathLength; +} + +/*-------------------------------------------------------------------*//*! +* \brief Tessellates a path, and computes its bounding box in user space. +* \param +* \return +* \note if runs out of memory, throws bad_alloc and leaves the path as it was +*//*-------------------------------------------------------------------*/ + +void Path::getPathBounds(RIfloat& minx, RIfloat& miny, RIfloat& maxx, RIfloat& maxy) +{ + RI_ASSERT(m_referenceCount > 0); + + Matrix3x3 identity; + identity.identity(); + tessellate(identity, 0.0f); //throws bad_alloc + + if(m_vertices.size()) + { + minx = m_userMinx; + miny = m_userMiny; + maxx = m_userMaxx; + maxy = m_userMaxy; + } + else + { + minx = miny = 0; + maxx = maxy = -1; + } +} + +/*-------------------------------------------------------------------*//*! +* \brief Tessellates a path, and computes its bounding box in surface space. +* \param +* \return +* \note if runs out of memory, throws bad_alloc and leaves the path as it was +*//*-------------------------------------------------------------------*/ + +void Path::getPathTransformedBounds(const Matrix3x3& pathToSurface, RIfloat& minx, RIfloat& miny, RIfloat& maxx, RIfloat& maxy) +{ + RI_ASSERT(m_referenceCount > 0); + RI_ASSERT(pathToSurface.isAffine()); + + Matrix3x3 identity; + identity.identity(); + tessellate(identity, 0.0f); //throws bad_alloc + + if(m_vertices.size()) + { + Vector3 p0(m_userMinx, m_userMiny, 1.0f); + Vector3 p1(m_userMinx, m_userMaxy, 1.0f); + Vector3 p2(m_userMaxx, m_userMaxy, 1.0f); + Vector3 p3(m_userMaxx, m_userMiny, 1.0f); + p0 = pathToSurface * p0; + p1 = pathToSurface * p1; + p2 = pathToSurface * p2; + p3 = pathToSurface * p3; + + minx = RI_MIN(RI_MIN(RI_MIN(p0.x, p1.x), p2.x), p3.x); + miny = RI_MIN(RI_MIN(RI_MIN(p0.y, p1.y), p2.y), p3.y); + maxx = RI_MAX(RI_MAX(RI_MAX(p0.x, p1.x), p2.x), p3.x); + maxy = RI_MAX(RI_MAX(RI_MAX(p0.y, p1.y), p2.y), p3.y); + } + else + { + minx = miny = 0; + maxx = maxy = -1; + } +} + +/*-------------------------------------------------------------------*//*! +* \brief Adds a vertex to a tessellated path. +* \param +* \return +* \note +*//*-------------------------------------------------------------------*/ + +void Path::addVertex(const Vector2& p, const Vector2& t, RIfloat pathLength, unsigned int flags) +{ + RI_ASSERT(!isZero(t)); + + Vertex v; + v.pathLength = pathLength; + v.userPosition = p; + v.userTangent = t; + v.flags = flags; + m_vertices.push_back(v); //throws bad_alloc + m_numTessVertices++; + + m_userMinx = RI_MIN(m_userMinx, v.userPosition.x); + m_userMiny = RI_MIN(m_userMiny, v.userPosition.y); + m_userMaxx = RI_MAX(m_userMaxx, v.userPosition.x); + m_userMaxy = RI_MAX(m_userMaxy, v.userPosition.y); +} + +/*-------------------------------------------------------------------*//*! +* \brief Adds an edge to a tessellated path. +* \param +* \return +* \note +*//*-------------------------------------------------------------------*/ + +void Path::addEdge(const Vector2& p0, const Vector2& p1, const Vector2& t0, const Vector2& t1, unsigned int startFlags, unsigned int endFlags) +{ + Vertex v; + RIfloat pathLength = 0.0f; + + RI_ASSERT(!isZero(t0) && !isZero(t1)); + + //segment midpoints are shared between edges + if(!m_numTessVertices) + { + if(m_vertices.size() > 0) + pathLength = m_vertices[m_vertices.size()-1].pathLength; + + addVertex(p0, t0, pathLength, startFlags); //throws bad_alloc + } + + //other than implicit close paths (caused by a MOVE_TO) add to path length + if( !(endFlags & IMPLICIT_CLOSE_SUBPATH) ) + { + //NOTE: with extremely large coordinates the floating point path length is infinite + RIfloat l = (p1 - p0).length(); + pathLength = m_vertices[m_vertices.size()-1].pathLength + l; + pathLength = RI_MIN(pathLength, RI_FLOAT_MAX); + } + + addVertex(p1, t1, pathLength, endFlags); //throws bad_alloc +} + +/*-------------------------------------------------------------------*//*! +* \brief Tessellates a close-path segment. +* \param +* \return +* \note +*//*-------------------------------------------------------------------*/ + +void Path::addEndPath(const Matrix3x3& pathToSurface, const Vector2& p0, const Vector2& p1, bool subpathHasGeometry, unsigned int flags) +{ + RI_UNREF(pathToSurface); + m_numTessVertices = 0; + if(!subpathHasGeometry) + { //single vertex + Vector2 t(1.0f,0.0f); + addEdge(p0, p1, t, t, START_SEGMENT | START_SUBPATH, END_SEGMENT | END_SUBPATH); //throws bad_alloc + m_numTessVertices = 0; + addEdge(p0, p1, -t, -t, IMPLICIT_CLOSE_SUBPATH | START_SEGMENT, IMPLICIT_CLOSE_SUBPATH | END_SEGMENT); //throws bad_alloc + return; + } + //the subpath contains segment commands that have generated geometry + + //add a close path segment to the start point of the subpath + RI_ASSERT(m_vertices.size() > 0); + m_vertices[m_vertices.size()-1].flags |= END_SUBPATH; + + Vector2 t = normalize(p1 - p0); + if(isZero(t)) + t = m_vertices[m_vertices.size()-1].userTangent; //if the segment is zero-length, use the tangent of the last segment end point so that proper join will be generated + RI_ASSERT(!isZero(t)); + + addEdge(p0, p1, t, t, flags | START_SEGMENT, flags | END_SEGMENT); //throws bad_alloc +} + +/*-------------------------------------------------------------------*//*! +* \brief Tessellates a line-to segment. +* \param +* \return +* \note +*//*-------------------------------------------------------------------*/ + +bool Path::addLineTo(const Matrix3x3& pathToSurface, const Vector2& p0, const Vector2& p1, bool subpathHasGeometry) +{ + RI_UNREF(pathToSurface); + if(p0 == p1) + return false; //discard zero-length segments + + //compute end point tangents + Vector2 t = normalize(p1 - p0); + RI_ASSERT(!isZero(t)); + + m_numTessVertices = 0; + unsigned int startFlags = START_SEGMENT; + if(!subpathHasGeometry) + startFlags |= START_SUBPATH; + addEdge(p0, p1, t, t, startFlags, END_SEGMENT); //throws bad_alloc + return true; +} + +/*-------------------------------------------------------------------*//*! +* \brief Tessellates a quad-to segment. +* \param +* \return +* \note +*//*-------------------------------------------------------------------*/ + +bool Path::addQuadTo(const Matrix3x3& pathToSurface, const Vector2& p0, const Vector2& p1, const Vector2& p2, bool subpathHasGeometry, float strokeWidth) +{ + RI_UNREF(pathToSurface); + RI_UNREF(strokeWidth); + if(p0 == p1 && p0 == p2) + { + RI_ASSERT(p1 == p2); + return false; //discard zero-length segments + } + + //compute end point tangents + + Vector2 incomingTangent = normalize(p1 - p0); + Vector2 outgoingTangent = normalize(p2 - p1); + if(p0 == p1) + incomingTangent = normalize(p2 - p0); + if(p1 == p2) + outgoingTangent = normalize(p2 - p0); + RI_ASSERT(!isZero(incomingTangent) && !isZero(outgoingTangent)); + + m_numTessVertices = 0; + unsigned int startFlags = START_SEGMENT; + if(!subpathHasGeometry) + startFlags |= START_SUBPATH; + + const int segments = RI_NUM_TESSELLATED_SEGMENTS_QUAD; + Vector2 pp = p0; + Vector2 tp = incomingTangent; + unsigned int prevFlags = startFlags; + for(int i=1;i m_segmentToVertex[i].start) + { //segment produced vertices + m_segmentToVertex[i].end = m_vertices.size() - 1; + } + else + { //segment didn't produce vertices (zero-length segment). Ignore it. + m_segmentToVertex[i].start = m_segmentToVertex[i].end = m_vertices.size()-1; + } + prevSegment = segment; + coordIndex += coords; + } + + //add an implicit MOVE_TO to the end to close the last subpath. + //if the subpath contained only zero-length segments, this produces the necessary geometry to get it stroked + // and included in path bounds. The geometry won't be included in the pointAlongPath query. + if(prevSegment != VG_MOVE_TO && prevSegment != VG_CLOSE_PATH) + addEndPath(pathToSurface, o, s, subpathHasGeometry, IMPLICIT_CLOSE_SUBPATH); + + //check that the flags are correct +#ifdef RI_DEBUG + int prev = -1; + bool subpathStarted = false; + bool segmentStarted = false; + for(int i=0;i= 0 ) + { + RI_ASSERT(segmentStarted); + RI_ASSERT(subpathStarted || ((m_vertices[prev].flags & CLOSE_SUBPATH) && (m_vertices[i].flags & CLOSE_SUBPATH)) || + ((m_vertices[prev].flags & IMPLICIT_CLOSE_SUBPATH) && (m_vertices[i].flags & IMPLICIT_CLOSE_SUBPATH))); + } + + prev = i; + if(v.flags & END_SEGMENT) + { + RI_ASSERT(subpathStarted || (v.flags & CLOSE_SUBPATH) || (v.flags & IMPLICIT_CLOSE_SUBPATH)); + RI_ASSERT(segmentStarted); + RI_ASSERT(!(v.flags & START_SUBPATH)); + RI_ASSERT(!(v.flags & START_SEGMENT)); + segmentStarted = false; + prev = -1; + } + + if(v.flags & END_SUBPATH) + { + RI_ASSERT(subpathStarted); + RI_ASSERT(v.flags & END_SEGMENT); + RI_ASSERT(!(v.flags & START_SUBPATH)); + RI_ASSERT(!(v.flags & START_SEGMENT)); + RI_ASSERT(!(v.flags & CLOSE_SUBPATH)); + RI_ASSERT(!(v.flags & IMPLICIT_CLOSE_SUBPATH)); + subpathStarted = false; + } + } +#endif //RI_DEBUG + } + catch(std::bad_alloc) + { + m_vertices.clear(); + throw; + } +} + +//============================================================================================== + +} //namespace OpenVGRI + +//==============================================================================================