1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2006 The Android Open Source Project 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com */ 7ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 88a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifndef SkGeometry_DEFINED 98a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#define SkGeometry_DEFINED 108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkMatrix.h" 126983f66d8b3a489133b751e2cef03e72a03bfeaereed#include "SkNx.h" 136983f66d8b3a489133b751e2cef03e72a03bfeaereed 146983f66d8b3a489133b751e2cef03e72a03bfeaereedstatic inline Sk2s from_point(const SkPoint& point) { 156983f66d8b3a489133b751e2cef03e72a03bfeaereed return Sk2s::Load(&point.fX); 166983f66d8b3a489133b751e2cef03e72a03bfeaereed} 176983f66d8b3a489133b751e2cef03e72a03bfeaereed 186983f66d8b3a489133b751e2cef03e72a03bfeaereedstatic inline SkPoint to_point(const Sk2s& x) { 196983f66d8b3a489133b751e2cef03e72a03bfeaereed SkPoint point; 206983f66d8b3a489133b751e2cef03e72a03bfeaereed x.store(&point.fX); 216983f66d8b3a489133b751e2cef03e72a03bfeaereed return point; 226983f66d8b3a489133b751e2cef03e72a03bfeaereed} 236983f66d8b3a489133b751e2cef03e72a03bfeaereed 246983f66d8b3a489133b751e2cef03e72a03bfeaereedstatic inline Sk2s sk2s_cubic_eval(const Sk2s& A, const Sk2s& B, const Sk2s& C, const Sk2s& D, 256983f66d8b3a489133b751e2cef03e72a03bfeaereed const Sk2s& t) { 266983f66d8b3a489133b751e2cef03e72a03bfeaereed return ((A * t + B) * t + C) * t + D; 276983f66d8b3a489133b751e2cef03e72a03bfeaereed} 288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given a quadratic equation Ax^2 + Bx + C = 0, return 0, 1, 2 roots for the 308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com equation. 318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]); 338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/////////////////////////////////////////////////////////////////////////////// 358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3640b7dd57ef1f4e91af72512d8ca57459b99d71bdreedSkPoint SkEvalQuadAt(const SkPoint src[3], SkScalar t); 3740b7dd57ef1f4e91af72512d8ca57459b99d71bdreedSkPoint SkEvalQuadTangentAt(const SkPoint src[3], SkScalar t); 3840b7dd57ef1f4e91af72512d8ca57459b99d71bdreed 398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Set pt to the point on the src quadratic specified by t. t must be 408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0 <= t <= 1.0 418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 4265cb2cd2f7ad4146f055810b8bd77bff03a4e76ereedvoid SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, SkVector* tangent = NULL); 438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 446983f66d8b3a489133b751e2cef03e72a03bfeaereed/** 456983f66d8b3a489133b751e2cef03e72a03bfeaereed * output is : eval(t) == coeff[0] * t^2 + coeff[1] * t + coeff[2] 466983f66d8b3a489133b751e2cef03e72a03bfeaereed */ 476983f66d8b3a489133b751e2cef03e72a03bfeaereedvoid SkQuadToCoeff(const SkPoint pts[3], SkPoint coeff[3]); 486983f66d8b3a489133b751e2cef03e72a03bfeaereed 496983f66d8b3a489133b751e2cef03e72a03bfeaereed/** 506983f66d8b3a489133b751e2cef03e72a03bfeaereed * output is : eval(t) == coeff[0] * t^3 + coeff[1] * t^2 + coeff[2] * t + coeff[3] 516983f66d8b3a489133b751e2cef03e72a03bfeaereed */ 526983f66d8b3a489133b751e2cef03e72a03bfeaereedvoid SkCubicToCoeff(const SkPoint pts[4], SkPoint coeff[4]); 536983f66d8b3a489133b751e2cef03e72a03bfeaereed 548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given a src quadratic bezier, chop it at the specified t value, 558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com where 0 < t < 1, and return the two new quadratics in dst: 568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[0..2] and dst[2..4] 578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t); 598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given a src quadratic bezier, chop it at the specified t == 1/2, 618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com The new quads are returned in dst[0..2] and dst[2..4] 628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5]); 648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given the 3 coefficients for a quadratic bezier (either X or Y values), look 668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for extrema, and return the number of t-values that are found that represent 678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com these extrema. If the quadratic has no extrema betwee (0..1) exclusive, the 688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com function returns 0. 698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Returned count tValues[] 708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0 ignored 718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1 0 < tValues[0] < 1 728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValues[1]); 748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given 3 points on a quadratic bezier, chop it into 1, 2 beziers such that 768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com the resulting beziers are monotonic in Y. This is called by the scan converter. 778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Depending on what is returned, dst[] is treated as follows 78909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 0 dst[0..2] is the original quad 79909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 1 dst[0..2] and dst[2..4] are the two new quads 808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]); 8277f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.comint SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]); 838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 845383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com/** Given 3 points on a quadratic bezier, if the point of maximum 855383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com curvature exists on the segment, returns the t value for this 865383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com point along the curve. Otherwise it will return a value of 0. 875383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com*/ 88891372c3b5b8229cf5c20b085f2d9448525f98e4reedSkScalar SkFindQuadMaxCurvature(const SkPoint src[3]); 895383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com 908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given 3 points on a quadratic bezier, divide it into 2 quadratics 918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if the point of maximum curvature exists on the quad segment. 928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Depending on what is returned, dst[] is treated as follows 938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1 dst[0..2] is the original quad 948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2 dst[0..2] and dst[2..4] are the two new quads 958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com If dst == null, it is ignored and only the count is returned. 968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]); 988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 99945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com/** Given 3 points on a quadratic bezier, use degree elevation to 100945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com convert it into the cubic fitting the same curve. The new cubic 101945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com curve is returned in dst[0..3]. 102945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com*/ 1037ffb1b21abcc7bbed5a0fc711f6dd7b9dbb4f577ctguil@chromium.orgSK_API void SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]); 104945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 105ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com/////////////////////////////////////////////////////////////////////////////// 1068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Set pt to the point on the src cubic specified by t. t must be 1088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0 <= t <= 1.0 1098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 110ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.comvoid SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* locOrNull, 111ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com SkVector* tangentOrNull, SkVector* curvatureOrNull); 1128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given a src cubic bezier, chop it at the specified t value, 1148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com where 0 < t < 1, and return the two new cubics in dst: 1158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[0..3] and dst[3..6] 1168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 1178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t); 1186b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed 119647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com/** Given a src cubic bezier, chop it at the specified t values, 120647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com where 0 < t < 1, and return the new cubics in dst: 121647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com dst[0..3],dst[3..6],...,dst[3*t_count..3*(t_count+1)] 122647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com*/ 123647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.comvoid SkChopCubicAt(const SkPoint src[4], SkPoint dst[], const SkScalar t[], 124ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com int t_count); 1258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given a src cubic bezier, chop it at the specified t == 1/2, 1278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com The new cubics are returned in dst[0..3] and dst[3..6] 1288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 1298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7]); 1308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given the 4 coefficients for a cubic bezier (either X or Y values), look 1328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for extrema, and return the number of t-values that are found that represent 1338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com these extrema. If the cubic has no extrema betwee (0..1) exclusive, the 1348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com function returns 0. 1358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Returned count tValues[] 1368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0 ignored 1378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1 0 < tValues[0] < 1 1388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2 0 < tValues[0] < tValues[1] < 1 1398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 140ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.comint SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d, 141ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com SkScalar tValues[2]); 1428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that 1448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com the resulting beziers are monotonic in Y. This is called by the scan converter. 1458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Depending on what is returned, dst[] is treated as follows 146909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 0 dst[0..3] is the original cubic 147909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 1 dst[0..3] and dst[3..6] are the two new cubics 148909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 2 dst[0..3], dst[3..6], dst[6..9] are the three new cubics 1498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com If dst == null, it is ignored and only the count is returned. 1508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 1518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]); 152909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comint SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]); 1538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given a cubic bezier, return 0, 1, or 2 t-values that represent the 1558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com inflection points. 1568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 1578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[2]); 1588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 159647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com/** Return 1 for no chop, 2 for having chopped the cubic at a single 160647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com inflection point, 3 for having chopped at 2 inflection points. 161dbeeac33329f5fd7dbd3514cd7189ca6ed080476bsalomon@google.com dst will hold the resulting 1, 2, or 3 cubics. 1628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 1638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkChopCubicAtInflections(const SkPoint src[4], SkPoint dst[10]); 1648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]); 166ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.comint SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], 167ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com SkScalar tValues[3] = NULL); 1688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 169dc3088570f945ed0ede84f0af0016eedc267dda3reedbool SkChopMonoCubicAtX(SkPoint src[4], SkScalar y, SkPoint dst[7]); 170dc3088570f945ed0ede84f0af0016eedc267dda3reedbool SkChopMonoCubicAtY(SkPoint src[4], SkScalar x, SkPoint dst[7]); 171dc3088570f945ed0ede84f0af0016eedc267dda3reed 1728dd31cf69e24ff82865309781107dfab948b6a02caryclarkenum SkCubicType { 1738dd31cf69e24ff82865309781107dfab948b6a02caryclark kSerpentine_SkCubicType, 1748dd31cf69e24ff82865309781107dfab948b6a02caryclark kCusp_SkCubicType, 1758dd31cf69e24ff82865309781107dfab948b6a02caryclark kLoop_SkCubicType, 1768dd31cf69e24ff82865309781107dfab948b6a02caryclark kQuadratic_SkCubicType, 1778dd31cf69e24ff82865309781107dfab948b6a02caryclark kLine_SkCubicType, 1788dd31cf69e24ff82865309781107dfab948b6a02caryclark kPoint_SkCubicType 1798dd31cf69e24ff82865309781107dfab948b6a02caryclark}; 1808dd31cf69e24ff82865309781107dfab948b6a02caryclark 1818dd31cf69e24ff82865309781107dfab948b6a02caryclark/** Returns the cubic classification. Pass scratch storage for computing inflection data, 1828dd31cf69e24ff82865309781107dfab948b6a02caryclark which can be used with additional work to find the loop intersections and so on. 1838dd31cf69e24ff82865309781107dfab948b6a02caryclark*/ 1848dd31cf69e24ff82865309781107dfab948b6a02caryclarkSkCubicType SkClassifyCubic(const SkPoint p[4], SkScalar inflection[3]); 1858dd31cf69e24ff82865309781107dfab948b6a02caryclark 186ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com/////////////////////////////////////////////////////////////////////////////// 1878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comenum SkRotationDirection { 1898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com kCW_SkRotationDirection, 1908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com kCCW_SkRotationDirection 1918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}; 1928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Maximum number of points needed in the quadPoints[] parameter for 1948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkBuildQuadArc() 1958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 1968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#define kSkBuildQuadArcStorage 17 1978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given 2 unit vectors and a rotation direction, fill out the specified 1998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com array of points with quadratic segments. Return is the number of points 2008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com written to, which will be { 0, 3, 5, 7, ... kSkBuildQuadArcStorage } 2018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com matrix, if not null, is appled to the points before they are returned. 2038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 204ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.comint SkBuildQuadArc(const SkVector& unitStart, const SkVector& unitStop, 205ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com SkRotationDirection, const SkMatrix*, SkPoint quadPoints[]); 2068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 20728552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgstruct SkConic { 208220f926d9d4b38a9018c922c095847bbd261f583reed SkConic() {} 209220f926d9d4b38a9018c922c095847bbd261f583reed SkConic(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, SkScalar w) { 210220f926d9d4b38a9018c922c095847bbd261f583reed fPts[0] = p0; 211220f926d9d4b38a9018c922c095847bbd261f583reed fPts[1] = p1; 212220f926d9d4b38a9018c922c095847bbd261f583reed fPts[2] = p2; 213220f926d9d4b38a9018c922c095847bbd261f583reed fW = w; 214220f926d9d4b38a9018c922c095847bbd261f583reed } 215220f926d9d4b38a9018c922c095847bbd261f583reed SkConic(const SkPoint pts[3], SkScalar w) { 216220f926d9d4b38a9018c922c095847bbd261f583reed memcpy(fPts, pts, sizeof(fPts)); 217220f926d9d4b38a9018c922c095847bbd261f583reed fW = w; 218220f926d9d4b38a9018c922c095847bbd261f583reed } 219220f926d9d4b38a9018c922c095847bbd261f583reed 220c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com SkPoint fPts[3]; 221c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com SkScalar fW; 222c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com 223c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com void set(const SkPoint pts[3], SkScalar w) { 224c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com memcpy(fPts, pts, 3 * sizeof(SkPoint)); 225c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com fW = w; 226c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com } 227c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com 228d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed void set(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, SkScalar w) { 229d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed fPts[0] = p0; 230d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed fPts[1] = p1; 231d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed fPts[2] = p2; 232d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed fW = w; 233d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed } 234d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 23524bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com /** 23624bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com * Given a t-value [0...1] return its position and/or tangent. 23724bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com * If pos is not null, return its position at the t-value. 23824bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com * If tangent is not null, return its tangent at the t-value. NOTE the 23924bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com * tangent value's length is arbitrary, and only its direction should 24024bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com * be used. 24124bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com */ 24224bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com void evalAt(SkScalar t, SkPoint* pos, SkVector* tangent = NULL) const; 24328552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.org void chopAt(SkScalar t, SkConic dst[2]) const; 24428552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.org void chop(SkConic dst[2]) const; 2457841c63136e8aa2d3aadbeab8432405abcd73c32skia.committer@gmail.com 246b640203cd5733aaf110277e28e22007c5b541565reed SkPoint evalAt(SkScalar t) const; 247b640203cd5733aaf110277e28e22007c5b541565reed SkVector evalTangentAt(SkScalar t) const; 248b640203cd5733aaf110277e28e22007c5b541565reed 249af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org void computeAsQuadError(SkVector* err) const; 250af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org bool asQuadTol(SkScalar tol) const; 25197514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org 252277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com /** 253277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com * return the power-of-2 number of quads needed to approximate this conic 254277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com * with a sequence of quads. Will be >= 0. 255277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com */ 2563df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org int computeQuadPOW2(SkScalar tol) const; 257277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com 258277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com /** 259277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com * Chop this conic into N quads, stored continguously in pts[], where 260277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com * N = 1 << pow2. The amount of storage needed is (1 + 2 * N) 261277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com */ 2623df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org int chopIntoQuadsPOW2(SkPoint pts[], int pow2) const; 2630c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 2640c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org bool findXExtrema(SkScalar* t) const; 2650c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org bool findYExtrema(SkScalar* t) const; 26628552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.org bool chopAtXExtrema(SkConic dst[2]) const; 26728552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.org bool chopAtYExtrema(SkConic dst[2]) const; 26845fb8b60137c65106b7903285672d0f8a8041f97skia.committer@gmail.com 2695c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org void computeTightBounds(SkRect* bounds) const; 2705c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org void computeFastBounds(SkRect* bounds) const; 271def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org 272def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org /** Find the parameter value where the conic takes on its maximum curvature. 273def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org * 274def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org * @param t output scalar for max curvature. Will be unchanged if 275def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org * max curvature outside 0..1 range. 276def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org * 277def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org * @return true if max curvature found inside 0..1 range, false otherwise 278def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org */ 279def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org bool findMaxCurvature(SkScalar* t) const; 280220f926d9d4b38a9018c922c095847bbd261f583reed 281220f926d9d4b38a9018c922c095847bbd261f583reed static SkScalar TransformW(const SkPoint[3], SkScalar w, const SkMatrix&); 282d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed 283d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed enum { 284d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed kMaxConicsForArc = 5 285d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed }; 286d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed static int BuildUnitArc(const SkVector& start, const SkVector& stop, SkRotationDirection, 287d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed const SkMatrix*, SkConic conics[kMaxConicsForArc]); 288c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com}; 289c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com 2904e05fd25c88bea64a988ededfc810770095ed97creed@google.com#include "SkTemplates.h" 2914e05fd25c88bea64a988ededfc810770095ed97creed@google.com 2924e05fd25c88bea64a988ededfc810770095ed97creed@google.com/** 2934e05fd25c88bea64a988ededfc810770095ed97creed@google.com * Help class to allocate storage for approximating a conic with N quads. 2944e05fd25c88bea64a988ededfc810770095ed97creed@google.com */ 2954e05fd25c88bea64a988ededfc810770095ed97creed@google.comclass SkAutoConicToQuads { 2964e05fd25c88bea64a988ededfc810770095ed97creed@google.compublic: 2974e05fd25c88bea64a988ededfc810770095ed97creed@google.com SkAutoConicToQuads() : fQuadCount(0) {} 2984e05fd25c88bea64a988ededfc810770095ed97creed@google.com 2994e05fd25c88bea64a988ededfc810770095ed97creed@google.com /** 3004e05fd25c88bea64a988ededfc810770095ed97creed@google.com * Given a conic and a tolerance, return the array of points for the 3014e05fd25c88bea64a988ededfc810770095ed97creed@google.com * approximating quad(s). Call countQuads() to know the number of quads 3024e05fd25c88bea64a988ededfc810770095ed97creed@google.com * represented in these points. 3034e05fd25c88bea64a988ededfc810770095ed97creed@google.com * 3044e05fd25c88bea64a988ededfc810770095ed97creed@google.com * The quads are allocated to share end-points. e.g. if there are 4 quads, 3054e05fd25c88bea64a988ededfc810770095ed97creed@google.com * there will be 9 points allocated as follows 3064e05fd25c88bea64a988ededfc810770095ed97creed@google.com * quad[0] == pts[0..2] 3074e05fd25c88bea64a988ededfc810770095ed97creed@google.com * quad[1] == pts[2..4] 3084e05fd25c88bea64a988ededfc810770095ed97creed@google.com * quad[2] == pts[4..6] 3094e05fd25c88bea64a988ededfc810770095ed97creed@google.com * quad[3] == pts[6..8] 3104e05fd25c88bea64a988ededfc810770095ed97creed@google.com */ 3114e05fd25c88bea64a988ededfc810770095ed97creed@google.com const SkPoint* computeQuads(const SkConic& conic, SkScalar tol) { 3124e05fd25c88bea64a988ededfc810770095ed97creed@google.com int pow2 = conic.computeQuadPOW2(tol); 3134e05fd25c88bea64a988ededfc810770095ed97creed@google.com fQuadCount = 1 << pow2; 3144e05fd25c88bea64a988ededfc810770095ed97creed@google.com SkPoint* pts = fStorage.reset(1 + 2 * fQuadCount); 3154e05fd25c88bea64a988ededfc810770095ed97creed@google.com conic.chopIntoQuadsPOW2(pts, pow2); 3164e05fd25c88bea64a988ededfc810770095ed97creed@google.com return pts; 3174e05fd25c88bea64a988ededfc810770095ed97creed@google.com } 3184e05fd25c88bea64a988ededfc810770095ed97creed@google.com 3194e05fd25c88bea64a988ededfc810770095ed97creed@google.com const SkPoint* computeQuads(const SkPoint pts[3], SkScalar weight, 3204e05fd25c88bea64a988ededfc810770095ed97creed@google.com SkScalar tol) { 3214e05fd25c88bea64a988ededfc810770095ed97creed@google.com SkConic conic; 3224e05fd25c88bea64a988ededfc810770095ed97creed@google.com conic.set(pts, weight); 3234e05fd25c88bea64a988ededfc810770095ed97creed@google.com return computeQuads(conic, tol); 3244e05fd25c88bea64a988ededfc810770095ed97creed@google.com } 3254e05fd25c88bea64a988ededfc810770095ed97creed@google.com 3264e05fd25c88bea64a988ededfc810770095ed97creed@google.com int countQuads() const { return fQuadCount; } 3274e05fd25c88bea64a988ededfc810770095ed97creed@google.com 3284e05fd25c88bea64a988ededfc810770095ed97creed@google.comprivate: 3294e05fd25c88bea64a988ededfc810770095ed97creed@google.com enum { 3304e05fd25c88bea64a988ededfc810770095ed97creed@google.com kQuadCount = 8, // should handle most conics 3314e05fd25c88bea64a988ededfc810770095ed97creed@google.com kPointCount = 1 + 2 * kQuadCount, 3324e05fd25c88bea64a988ededfc810770095ed97creed@google.com }; 3334e05fd25c88bea64a988ededfc810770095ed97creed@google.com SkAutoSTMalloc<kPointCount, SkPoint> fStorage; 3344e05fd25c88bea64a988ededfc810770095ed97creed@google.com int fQuadCount; // #quads for current usage 3354e05fd25c88bea64a988ededfc810770095ed97creed@google.com}; 3364e05fd25c88bea64a988ededfc810770095ed97creed@google.com 3378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 338