src/core/SkStrokerPriv.cpp - platform/external/skia - Git at Google

 /* libs/graphics/sgl/SkStrokerPriv.cpp
 **
 ** Copyright 2006, The Android Open Source Project
 **
 ** Licensed under the Apache License, Version 2.0 (the "License");
 ** you may not use this file except in compliance with the License.
 ** You may obtain a copy of the License at
 **
 **     http://www.apache.org/licenses/LICENSE-2.0
 **
 ** Unless required by applicable law or agreed to in writing, software
 ** distributed under the License is distributed on an "AS IS" BASIS,
 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 ** See the License for the specific language governing permissions and
 ** limitations under the License.
 */

 #include "SkStrokerPriv.h"
 #include "SkGeometry.h"
 #include "SkPath.h"

 static void ButtCapper(SkPath* path, const SkPoint& pivot,
                        const SkVector& normal, const SkPoint& stop,
                        SkPath*)
 {
     path->lineTo(stop.fX, stop.fY);
 }

 static void RoundCapper(SkPath* path, const SkPoint& pivot,
                         const SkVector& normal, const SkPoint& stop,
                         SkPath*)
 {
     SkScalar    px = pivot.fX;
     SkScalar    py = pivot.fY;
     SkScalar    nx = normal.fX;
     SkScalar    ny = normal.fY;
     SkScalar    sx = SkScalarMul(nx, CUBIC_ARC_FACTOR);
     SkScalar    sy = SkScalarMul(ny, CUBIC_ARC_FACTOR);

     path->cubicTo(px + nx + CWX(sx, sy), py + ny + CWY(sx, sy),
                   px + CWX(nx, ny) + sx, py + CWY(nx, ny) + sy,
                   px + CWX(nx, ny), py + CWY(nx, ny));
     path->cubicTo(px + CWX(nx, ny) - sx, py + CWY(nx, ny) - sy,
                   px - nx + CWX(sx, sy), py - ny + CWY(sx, sy),
                   stop.fX, stop.fY);
 }

 static void SquareCapper(SkPath* path, const SkPoint& pivot,
                          const SkVector& normal, const SkPoint& stop,
                          SkPath* otherPath)
 {
     SkVector parallel;
     normal.rotateCW(&parallel);

     if (otherPath)
     {
         path->setLastPt(pivot.fX + normal.fX + parallel.fX, pivot.fY + normal.fY + parallel.fY);
         path->lineTo(pivot.fX - normal.fX + parallel.fX, pivot.fY - normal.fY + parallel.fY);
     }
     else
     {
         path->lineTo(pivot.fX + normal.fX + parallel.fX, pivot.fY + normal.fY + parallel.fY);
         path->lineTo(pivot.fX - normal.fX + parallel.fX, pivot.fY - normal.fY + parallel.fY);
         path->lineTo(stop.fX, stop.fY);
     }
 }

 /////////////////////////////////////////////////////////////////////////////

 static bool is_clockwise(const SkVector& before, const SkVector& after)
 {
     return SkScalarMul(before.fX, after.fY) - SkScalarMul(before.fY, after.fX) > 0;
 }

 enum AngleType {
     kNearly180_AngleType,
     kSharp_AngleType,
     kShallow_AngleType,
     kNearlyLine_AngleType
 };

 static AngleType Dot2AngleType(SkScalar dot)
 {
 // need more precise fixed normalization
 //  SkASSERT(SkScalarAbs(dot) <= SK_Scalar1 + SK_ScalarNearlyZero);

     if (dot >= 0)   // shallow or line
         return SkScalarNearlyZero(SK_Scalar1 - dot) ? kNearlyLine_AngleType : kShallow_AngleType;
     else            // sharp or 180
         return SkScalarNearlyZero(SK_Scalar1 + dot) ? kNearly180_AngleType : kSharp_AngleType;
 }

 static void HandleInnerJoin(SkPath* inner, const SkPoint& pivot, const SkVector& after)
 {
 #if 1
     /*  In the degenerate case that the stroke radius is larger than our segments
         just connecting the two inner segments may "show through" as a funny
         diagonal. To pseudo-fix this, we go through the pivot point. This adds
         an extra point/edge, but I can't see a cheap way to know when this is
         not needed :(
     */
     inner->lineTo(pivot.fX, pivot.fY);
 #endif

     inner->lineTo(pivot.fX - after.fX, pivot.fY - after.fY);
 }

 static void BluntJoiner(SkPath* outer, SkPath* inner, const SkVector& beforeUnitNormal,
                         const SkPoint& pivot, const SkVector& afterUnitNormal,
                         SkScalar radius, SkScalar invMiterLimit, bool, bool)
 {
     SkVector    after;
     afterUnitNormal.scale(radius, &after);

     if (!is_clockwise(beforeUnitNormal, afterUnitNormal))
     {
         SkTSwap<SkPath*>(outer, inner);
         after.negate();
     }

     outer->lineTo(pivot.fX + after.fX, pivot.fY + after.fY);
     HandleInnerJoin(inner, pivot, after);
 }

 static void RoundJoiner(SkPath* outer, SkPath* inner, const SkVector& beforeUnitNormal,
                         const SkPoint& pivot, const SkVector& afterUnitNormal,
                         SkScalar radius, SkScalar invMiterLimit, bool, bool)
 {
     SkScalar    dotProd = SkPoint::DotProduct(beforeUnitNormal, afterUnitNormal);
     AngleType   angleType = Dot2AngleType(dotProd);

     if (angleType == kNearlyLine_AngleType)
         return;

     SkVector            before = beforeUnitNormal;
     SkVector            after = afterUnitNormal;
     SkRotationDirection dir = kCW_SkRotationDirection;

     if (!is_clockwise(before, after))
     {
         SkTSwap<SkPath*>(outer, inner);
         before.negate();
         after.negate();
         dir = kCCW_SkRotationDirection;
     }

     SkPoint     pts[kSkBuildQuadArcStorage];
     SkMatrix    matrix;
     matrix.setScale(radius, radius);
     matrix.postTranslate(pivot.fX, pivot.fY);
     int count = SkBuildQuadArc(before, after, dir, &matrix, pts);
     SkASSERT((count & 1) == 1);

     if (count > 1)
     {
         for (int i = 1; i < count; i += 2)
             outer->quadTo(pts[i].fX, pts[i].fY, pts[i+1].fX, pts[i+1].fY);

         after.scale(radius);
         HandleInnerJoin(inner, pivot, after);
     }
 }

 #ifdef SK_SCALAR_IS_FLOAT
     #define kOneOverSqrt2   (0.707106781f)
 #else
     #define kOneOverSqrt2   (46341)
 #endif

 static void MiterJoiner(SkPath* outer, SkPath* inner, const SkVector& beforeUnitNormal,
                         const SkPoint& pivot, const SkVector& afterUnitNormal,
                         SkScalar radius, SkScalar invMiterLimit,
                         bool prevIsLine, bool currIsLine)
 {
     // negate the dot since we're using normals instead of tangents
     SkScalar    dotProd = SkPoint::DotProduct(beforeUnitNormal, afterUnitNormal);
     AngleType   angleType = Dot2AngleType(dotProd);
     SkVector    before = beforeUnitNormal;
     SkVector    after = afterUnitNormal;
     SkVector    mid;
     SkScalar    sinHalfAngle;
     bool        ccw;

     if (angleType == kNearlyLine_AngleType)
         return;
     if (angleType == kNearly180_AngleType)
     {
         currIsLine = false;
         goto DO_BLUNT;
     }

     ccw = !is_clockwise(before, after);
     if (ccw)
     {
         SkTSwap<SkPath*>(outer, inner);
         before.negate();
         after.negate();
     }

     /*  Before we enter the world of square-roots and divides,
         check if we're trying to join an upright right angle
         (common case for stroking rectangles). If so, special case
         that (for speed an accuracy).
         Note: we only need to check one normal if dot==0
     */
     if (0 == dotProd && invMiterLimit <= kOneOverSqrt2)
     {
         mid.set(SkScalarMul(before.fX + after.fX, radius),
                 SkScalarMul(before.fY + after.fY, radius));
         goto DO_MITER;
     }

     /*  midLength = radius / sinHalfAngle
         if (midLength > miterLimit * radius) abort
         if (radius / sinHalf > miterLimit * radius) abort
         if (1 / sinHalf > miterLimit) abort
         if (1 / miterLimit > sinHalf) abort
         My dotProd is opposite sign, since it is built from normals and not tangents
         hence 1 + dot instead of 1 - dot in the formula
     */
     sinHalfAngle = SkScalarSqrt(SkScalarHalf(SK_Scalar1 + dotProd));
     if (sinHalfAngle < invMiterLimit)
     {
         currIsLine = false;
         goto DO_BLUNT;
     }

     // choose the most accurate way to form the initial mid-vector
     if (angleType == kSharp_AngleType)
     {
         mid.set(after.fY - before.fY, before.fX - after.fX);
         if (ccw)
             mid.negate();
     }
     else
         mid.set(before.fX + after.fX, before.fY + after.fY);

     mid.setLength(SkScalarDiv(radius, sinHalfAngle));
 DO_MITER:
     if (prevIsLine)
         outer->setLastPt(pivot.fX + mid.fX, pivot.fY + mid.fY);
     else
         outer->lineTo(pivot.fX + mid.fX, pivot.fY + mid.fY);

 DO_BLUNT:
     after.scale(radius);
     if (!currIsLine)
         outer->lineTo(pivot.fX + after.fX, pivot.fY + after.fY);
     HandleInnerJoin(inner, pivot, after);
 }

 /////////////////////////////////////////////////////////////////////////////

 SkStrokerPriv::CapProc SkStrokerPriv::CapFactory(SkPaint::Cap cap)
 {
     static const SkStrokerPriv::CapProc gCappers[] = {
         ButtCapper, RoundCapper, SquareCapper
     };

     SkASSERT((unsigned)cap < SkPaint::kCapCount);
     return gCappers[cap];
 }

 SkStrokerPriv::JoinProc SkStrokerPriv::JoinFactory(SkPaint::Join join)
 {
     static const SkStrokerPriv::JoinProc gJoiners[] = {
         MiterJoiner, RoundJoiner, BluntJoiner
     };

     SkASSERT((unsigned)join < SkPaint::kJoinCount);
     return gJoiners[join];
 }
	/* libs/graphics/sgl/SkStrokerPriv.cpp
	**
	** Copyright 2006, The Android Open Source Project
	**
	** Licensed under the Apache License, Version 2.0 (the "License");
	** you may not use this file except in compliance with the License.
	** You may obtain a copy of the License at
	**
	** http://www.apache.org/licenses/LICENSE-2.0
	**
	** Unless required by applicable law or agreed to in writing, software
	** distributed under the License is distributed on an "AS IS" BASIS,
	** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	** See the License for the specific language governing permissions and
	** limitations under the License.
	*/

	#include "SkStrokerPriv.h"
	#include "SkGeometry.h"
	#include "SkPath.h"

	static void ButtCapper(SkPath* path, const SkPoint& pivot,
	const SkVector& normal, const SkPoint& stop,
	SkPath*)
	{
	path->lineTo(stop.fX, stop.fY);
	}

	static void RoundCapper(SkPath* path, const SkPoint& pivot,
	const SkVector& normal, const SkPoint& stop,
	SkPath*)
	{
	SkScalar px = pivot.fX;
	SkScalar py = pivot.fY;
	SkScalar nx = normal.fX;
	SkScalar ny = normal.fY;
	SkScalar sx = SkScalarMul(nx, CUBIC_ARC_FACTOR);
	SkScalar sy = SkScalarMul(ny, CUBIC_ARC_FACTOR);

	path->cubicTo(px + nx + CWX(sx, sy), py + ny + CWY(sx, sy),
	px + CWX(nx, ny) + sx, py + CWY(nx, ny) + sy,
	px + CWX(nx, ny), py + CWY(nx, ny));
	path->cubicTo(px + CWX(nx, ny) - sx, py + CWY(nx, ny) - sy,
	px - nx + CWX(sx, sy), py - ny + CWY(sx, sy),
	stop.fX, stop.fY);
	}

	static void SquareCapper(SkPath* path, const SkPoint& pivot,
	const SkVector& normal, const SkPoint& stop,
	SkPath* otherPath)
	{
	SkVector parallel;
	normal.rotateCW(&parallel);

	if (otherPath)
	{
	path->setLastPt(pivot.fX + normal.fX + parallel.fX, pivot.fY + normal.fY + parallel.fY);
	path->lineTo(pivot.fX - normal.fX + parallel.fX, pivot.fY - normal.fY + parallel.fY);
	}
	else
	{
	path->lineTo(pivot.fX + normal.fX + parallel.fX, pivot.fY + normal.fY + parallel.fY);
	path->lineTo(pivot.fX - normal.fX + parallel.fX, pivot.fY - normal.fY + parallel.fY);
	path->lineTo(stop.fX, stop.fY);
	}
	}

	/////////////////////////////////////////////////////////////////////////////

	static bool is_clockwise(const SkVector& before, const SkVector& after)
	{
	return SkScalarMul(before.fX, after.fY) - SkScalarMul(before.fY, after.fX) > 0;
	}

	enum AngleType {
	kNearly180_AngleType,
	kSharp_AngleType,
	kShallow_AngleType,
	kNearlyLine_AngleType
	};

	static AngleType Dot2AngleType(SkScalar dot)
	{
	// need more precise fixed normalization
	// SkASSERT(SkScalarAbs(dot) <= SK_Scalar1 + SK_ScalarNearlyZero);

	if (dot >= 0) // shallow or line
	return SkScalarNearlyZero(SK_Scalar1 - dot) ? kNearlyLine_AngleType : kShallow_AngleType;
	else // sharp or 180
	return SkScalarNearlyZero(SK_Scalar1 + dot) ? kNearly180_AngleType : kSharp_AngleType;
	}

	static void HandleInnerJoin(SkPath* inner, const SkPoint& pivot, const SkVector& after)
	{
	#if 1
	/* In the degenerate case that the stroke radius is larger than our segments
	just connecting the two inner segments may "show through" as a funny
	diagonal. To pseudo-fix this, we go through the pivot point. This adds
	an extra point/edge, but I can't see a cheap way to know when this is
	not needed :(
	*/
	inner->lineTo(pivot.fX, pivot.fY);
	#endif

	inner->lineTo(pivot.fX - after.fX, pivot.fY - after.fY);
	}

	static void BluntJoiner(SkPath* outer, SkPath* inner, const SkVector& beforeUnitNormal,
	const SkPoint& pivot, const SkVector& afterUnitNormal,
	SkScalar radius, SkScalar invMiterLimit, bool, bool)
	{
	SkVector after;
	afterUnitNormal.scale(radius, &after);

	if (!is_clockwise(beforeUnitNormal, afterUnitNormal))
	{
	SkTSwap<SkPath*>(outer, inner);
	after.negate();
	}

	outer->lineTo(pivot.fX + after.fX, pivot.fY + after.fY);
	HandleInnerJoin(inner, pivot, after);
	}

	static void RoundJoiner(SkPath* outer, SkPath* inner, const SkVector& beforeUnitNormal,
	const SkPoint& pivot, const SkVector& afterUnitNormal,
	SkScalar radius, SkScalar invMiterLimit, bool, bool)
	{
	SkScalar dotProd = SkPoint::DotProduct(beforeUnitNormal, afterUnitNormal);
	AngleType angleType = Dot2AngleType(dotProd);

	if (angleType == kNearlyLine_AngleType)
	return;

	SkVector before = beforeUnitNormal;
	SkVector after = afterUnitNormal;
	SkRotationDirection dir = kCW_SkRotationDirection;

	if (!is_clockwise(before, after))
	{
	SkTSwap<SkPath*>(outer, inner);
	before.negate();
	after.negate();
	dir = kCCW_SkRotationDirection;
	}

	SkPoint pts[kSkBuildQuadArcStorage];
	SkMatrix matrix;
	matrix.setScale(radius, radius);
	matrix.postTranslate(pivot.fX, pivot.fY);
	int count = SkBuildQuadArc(before, after, dir, &matrix, pts);
	SkASSERT((count & 1) == 1);

	if (count > 1)
	{
	for (int i = 1; i < count; i += 2)
	outer->quadTo(pts[i].fX, pts[i].fY, pts[i+1].fX, pts[i+1].fY);

	after.scale(radius);
	HandleInnerJoin(inner, pivot, after);
	}
	}

	#ifdef SK_SCALAR_IS_FLOAT
	#define kOneOverSqrt2 (0.707106781f)
	#else
	#define kOneOverSqrt2 (46341)
	#endif

	static void MiterJoiner(SkPath* outer, SkPath* inner, const SkVector& beforeUnitNormal,
	const SkPoint& pivot, const SkVector& afterUnitNormal,
	SkScalar radius, SkScalar invMiterLimit,
	bool prevIsLine, bool currIsLine)
	{
	// negate the dot since we're using normals instead of tangents
	SkScalar dotProd = SkPoint::DotProduct(beforeUnitNormal, afterUnitNormal);
	AngleType angleType = Dot2AngleType(dotProd);
	SkVector before = beforeUnitNormal;
	SkVector after = afterUnitNormal;
	SkVector mid;
	SkScalar sinHalfAngle;
	bool ccw;

	if (angleType == kNearlyLine_AngleType)
	return;
	if (angleType == kNearly180_AngleType)
	{
	currIsLine = false;
	goto DO_BLUNT;
	}

	ccw = !is_clockwise(before, after);
	if (ccw)
	{
	SkTSwap<SkPath*>(outer, inner);
	before.negate();
	after.negate();
	}

	/* Before we enter the world of square-roots and divides,
	check if we're trying to join an upright right angle
	(common case for stroking rectangles). If so, special case
	that (for speed an accuracy).
	Note: we only need to check one normal if dot==0
	*/
	if (0 == dotProd && invMiterLimit <= kOneOverSqrt2)
	{
	mid.set(SkScalarMul(before.fX + after.fX, radius),
	SkScalarMul(before.fY + after.fY, radius));
	goto DO_MITER;
	}

	/* midLength = radius / sinHalfAngle
	if (midLength > miterLimit * radius) abort
	if (radius / sinHalf > miterLimit * radius) abort
	if (1 / sinHalf > miterLimit) abort
	if (1 / miterLimit > sinHalf) abort
	My dotProd is opposite sign, since it is built from normals and not tangents
	hence 1 + dot instead of 1 - dot in the formula
	*/
	sinHalfAngle = SkScalarSqrt(SkScalarHalf(SK_Scalar1 + dotProd));
	if (sinHalfAngle < invMiterLimit)
	{
	currIsLine = false;
	goto DO_BLUNT;
	}

	// choose the most accurate way to form the initial mid-vector
	if (angleType == kSharp_AngleType)
	{
	mid.set(after.fY - before.fY, before.fX - after.fX);
	if (ccw)
	mid.negate();
	}
	else
	mid.set(before.fX + after.fX, before.fY + after.fY);

	mid.setLength(SkScalarDiv(radius, sinHalfAngle));
	DO_MITER:
	if (prevIsLine)
	outer->setLastPt(pivot.fX + mid.fX, pivot.fY + mid.fY);
	else
	outer->lineTo(pivot.fX + mid.fX, pivot.fY + mid.fY);

	DO_BLUNT:
	after.scale(radius);
	if (!currIsLine)
	outer->lineTo(pivot.fX + after.fX, pivot.fY + after.fY);
	HandleInnerJoin(inner, pivot, after);
	}

	/////////////////////////////////////////////////////////////////////////////

	SkStrokerPriv::CapProc SkStrokerPriv::CapFactory(SkPaint::Cap cap)
	{
	static const SkStrokerPriv::CapProc gCappers[] = {
	ButtCapper, RoundCapper, SquareCapper
	};

	SkASSERT((unsigned)cap < SkPaint::kCapCount);
	return gCappers[cap];
	}

	SkStrokerPriv::JoinProc SkStrokerPriv::JoinFactory(SkPaint::Join join)
	{
	static const SkStrokerPriv::JoinProc gJoiners[] = {
	MiterJoiner, RoundJoiner, BluntJoiner
	};

	SkASSERT((unsigned)join < SkPaint::kJoinCount);
	return gJoiners[join];
	}