LoopBlinnMathUtils.cpp [plain text]
#include "config.h"
#if USE(ACCELERATED_COMPOSITING) || ENABLE(ACCELERATED_2D_CANVAS)
#include "LoopBlinnMathUtils.h"
#include "FloatPoint.h"
#include <algorithm>
#include <wtf/MathExtras.h>
namespace WebCore {
namespace LoopBlinnMathUtils {
namespace {
int orientation(const FloatPoint& p1,
const FloatPoint& p2,
const FloatPoint& p3)
{
float crossProduct = (p2.y() - p1.y()) * (p3.x() - p2.x()) - (p3.y() - p2.y()) * (p2.x() - p1.x());
return (crossProduct < 0.0f) ? -1 : ((crossProduct > 0.0f) ? 1 : 0);
}
bool edgeEdgeTest(const FloatSize& v0Delta,
const FloatPoint& v0,
const FloatPoint& u0,
const FloatPoint& u1)
{
float ax = v0Delta.width();
float ay = v0Delta.height();
float bx = u0.x() - u1.x();
float by = u0.y() - u1.y();
float cx = v0.x() - u0.x();
float cy = v0.y() - u0.y();
float f = ay * bx - ax * by;
float d = by * cx - bx * cy;
if ((f > 0 && d >= 0 && d <= f) || (f < 0 && d <= 0 && d >= f)) {
float e = ax * cy - ay * cx;
if (approxEqual(e, 0) || approxEqual(f, 0) || approxEqual(e, f))
return false;
if (f > 0)
return e >= 0 && e <= f;
return e <= 0 && e >= f;
}
return false;
}
bool edgeAgainstTriangleEdges(const FloatPoint& v0,
const FloatPoint& v1,
const FloatPoint& u0,
const FloatPoint& u1,
const FloatPoint& u2)
{
FloatSize delta = v1 - v0;
if (edgeEdgeTest(delta, v0, u0, u1))
return true;
if (edgeEdgeTest(delta, v0, u1, u2))
return true;
if (edgeEdgeTest(delta, v0, u2, u0))
return true;
return false;
}
const float Epsilon = 5.0e-4f;
}
float roundToZero(float val)
{
if (val < Epsilon && val > -Epsilon)
return 0;
return val;
}
bool approxEqual(const FloatPoint& v0, const FloatPoint& v1)
{
return (v0 - v1).diagonalLengthSquared() < Epsilon * Epsilon;
}
bool approxEqual(const FloatPoint3D& v0, const FloatPoint3D& v1)
{
return (v0 - v1).lengthSquared() < Epsilon * Epsilon;
}
bool approxEqual(float f0, float f1)
{
return fabsf(f0 - f1) < Epsilon;
}
bool linesIntersect(const FloatPoint& p1,
const FloatPoint& q1,
const FloatPoint& p2,
const FloatPoint& q2)
{
return (orientation(p1, q1, p2) != orientation(p1, q1, q2)
&& orientation(p2, q2, p1) != orientation(p2, q2, q1));
}
bool pointInTriangle(const FloatPoint& point,
const FloatPoint& a,
const FloatPoint& b,
const FloatPoint& c)
{
float x0 = c.x() - a.x();
float y0 = c.y() - a.y();
float x1 = b.x() - a.x();
float y1 = b.y() - a.y();
float x2 = point.x() - a.x();
float y2 = point.y() - a.y();
float dot00 = x0 * x0 + y0 * y0;
float dot01 = x0 * x1 + y0 * y1;
float dot02 = x0 * x2 + y0 * y2;
float dot11 = x1 * x1 + y1 * y1;
float dot12 = x1 * x2 + y1 * y2;
float denominator = dot00 * dot11 - dot01 * dot01;
if (!denominator)
return false;
float inverseDenominator = 1.0f / denominator;
float u = (dot11 * dot02 - dot01 * dot12) * inverseDenominator;
float v = (dot00 * dot12 - dot01 * dot02) * inverseDenominator;
return (u > 0.0f) && (v > 0.0f) && (u + v < 1.0f);
}
bool trianglesOverlap(const FloatPoint& a1,
const FloatPoint& b1,
const FloatPoint& c1,
const FloatPoint& a2,
const FloatPoint& b2,
const FloatPoint& c2)
{
if (edgeAgainstTriangleEdges(a1, b1, a2, b2, c2)
|| edgeAgainstTriangleEdges(b1, c1, a2, b2, c2)
|| edgeAgainstTriangleEdges(c1, a1, a2, b2, c2))
return true;
if (pointInTriangle(a1, a2, b2, c2)
|| pointInTriangle(a2, a1, b1, c1)
|| pointInTriangle(b1, a2, b2, c2)
|| pointInTriangle(b2, a1, b1, c1)
|| pointInTriangle(c1, a2, b2, c2)
|| pointInTriangle(c2, a1, b1, c1))
return true;
return false;
}
namespace {
const float NearlyZeroConstant = (1.0f / (1 << 12));
bool nearlyZero(float x, float tolerance = NearlyZeroConstant)
{
ASSERT(tolerance > 0.0f);
return ::fabsf(x) < tolerance;
}
float interpolate(float a, float b, float t)
{
ASSERT(t >= 0 && t <= 1);
return a + (b - a) * t;
}
float evaluateCubic(float controlPoint0, float controlPoint1, float controlPoint2, float controlPoint3, float t)
{
ASSERT(t >= 0 && t <= 1);
if (!t)
return controlPoint0;
float ab = interpolate(controlPoint0, controlPoint1, t);
float bc = interpolate(controlPoint1, controlPoint2, t);
float cd = interpolate(controlPoint2, controlPoint3, t);
float abc = interpolate(ab, bc, t);
float bcd = interpolate(bc, cd, t);
return interpolate(abc, bcd, t);
}
FloatPoint evaluateCubicAt(const FloatPoint cubic[4], float t)
{
return FloatPoint(evaluateCubic(cubic[0].x(), cubic[1].x(), cubic[2].x(), cubic[3].x(), t),
evaluateCubic(cubic[0].y(), cubic[1].y(), cubic[2].y(), cubic[3].y(), t));
}
bool xRayCrossesMonotonicCubic(const XRay& xRay, const FloatPoint cubic[4], bool& ambiguous)
{
ambiguous = false;
float minY = std::min(cubic[0].y(), cubic[3].y());
float maxY = std::max(cubic[0].y(), cubic[3].y());
if (xRay.y() == cubic[0].y()
|| xRay.y() < minY
|| xRay.y() > maxY) {
ambiguous = (xRay.y() == cubic[0].y());
return false;
}
const bool pointAtExtremum = (xRay.y() == cubic[3].y());
float minX = std::min(std::min(std::min(cubic[0].x(), cubic[1].x()),
cubic[2].x()),
cubic[3].x());
if (xRay.x() < minX) {
ambiguous = pointAtExtremum;
return true;
}
float maxX = std::max(std::max(std::max(cubic[0].x(), cubic[1].x()),
cubic[2].x()),
cubic[3].x());
if (xRay.x() > maxX)
return false;
const int MaxIterations = 23;
FloatPoint evaluatedPoint;
int iter = 0;
float upperT;
float lowerT;
if (cubic[3].y() > cubic[0].y()) {
upperT = 1;
lowerT = 0;
} else {
upperT = 0;
lowerT = 1;
}
do {
float t = 0.5f * (upperT + lowerT);
evaluatedPoint = evaluateCubicAt(cubic, t);
if (xRay.y() > evaluatedPoint.y())
lowerT = t;
else
upperT = t;
} while (++iter < MaxIterations && !nearlyZero(evaluatedPoint.y() - xRay.y()));
if (xRay.x() <= evaluatedPoint.x()) {
ambiguous = pointAtExtremum;
return true;
}
return false;
}
bool safeUnitDivide(float numerator, float denominator, float& ratio)
{
if (numerator < 0) {
numerator = -numerator;
denominator = -denominator;
}
if (!numerator || !denominator || numerator >= denominator)
return false;
float r = numerator / denominator;
if (isnan(r))
return false;
ASSERT(r >= 0 && r < 1);
if (!r) return false;
ratio = r;
return true;
}
int findUnitQuadRoots(float a, float b, float c, float roots[2])
{
if (!a)
return safeUnitDivide(-c, b, roots[0]) ? 1 : 0;
float discriminant = b*b - 4*a*c;
if (discriminant < 0 || isnan(discriminant)) return 0;
discriminant = sqrtf(discriminant);
float q = (b < 0) ? -(b - discriminant) / 2 : -(b + discriminant) / 2;
int numberOfRoots = 0;
if (safeUnitDivide(q, a, roots[numberOfRoots]))
++numberOfRoots;
if (safeUnitDivide(c, q, roots[numberOfRoots]))
++numberOfRoots;
if (numberOfRoots == 2) {
if (roots[0] == roots[1])
return 1;
if (roots[0] > roots[1])
std::swap(roots[0], roots[1]);
}
return numberOfRoots;
}
int findCubicExtrema(float a, float b, float c, float d, float tValues[2])
{
float p = d - a + 3*(b - c);
float q = 2*(a - b - b + c);
float r = b - a;
return findUnitQuadRoots(p, q, r, tValues);
}
void interpolateCubicCoords(float controlPoint0, float controlPoint1, float controlPoint2, float controlPoint3, float* dst, float t)
{
float ab = interpolate(controlPoint0, controlPoint1, t);
float bc = interpolate(controlPoint1, controlPoint2, t);
float cd = interpolate(controlPoint2, controlPoint3, t);
float abc = interpolate(ab, bc, t);
float bcd = interpolate(bc, cd, t);
float abcd = interpolate(abc, bcd, t);
dst[0] = controlPoint0;
dst[2] = ab;
dst[4] = abc;
dst[6] = abcd;
dst[8] = bcd;
dst[10] = cd;
dst[12] = controlPoint3;
}
#ifndef NDEBUG
bool isUnitInterval(float x)
{
return x > 0 && x < 1;
}
#endif
void chopCubicAtTValues(const FloatPoint src[4], FloatPoint dst[], const float tValues[], int roots)
{
#ifndef NDEBUG
for (int i = 0; i < roots - 1; ++i) {
ASSERT(isUnitInterval(tValues[i]));
ASSERT(isUnitInterval(tValues[i+1]));
ASSERT(tValues[i] < tValues[i+1]);
}
#endif
if (!roots) {
for (int j = 0; j < 4; ++j)
dst[j] = src[j];
return;
}
float t = tValues[0];
FloatPoint tmp[4];
for (int j = 0; j < 4; ++j)
tmp[j] = src[j];
for (int i = 0; i < roots; ++i) {
chopCubicAt(tmp, dst, t);
if (i == roots - 1)
break;
dst += 3;
for (int j = 0; j < 4; ++j)
tmp[j] = dst[j];
if (!safeUnitDivide(tValues[i+1] - tValues[i], 1.0f - tValues[i], t)) {
dst[4] = dst[5] = dst[6] = tmp[3];
break;
}
}
}
void flattenDoubleCubicYExtrema(FloatPoint coords[7])
{
coords[2].setY(coords[3].y());
coords[4].setY(coords[3].y());
}
int chopCubicAtYExtrema(const FloatPoint src[4], FloatPoint dst[10])
{
float tValues[2];
int roots = findCubicExtrema(src[0].y(), src[1].y(), src[2].y(), src[3].y(), tValues);
chopCubicAtTValues(src, dst, tValues, roots);
if (roots) {
flattenDoubleCubicYExtrema(&dst[0]);
if (roots == 2)
flattenDoubleCubicYExtrema(&dst[3]);
}
return roots;
}
}
void chopCubicAt(const FloatPoint src[4], FloatPoint dst[7], float t)
{
ASSERT(t >= 0 && t <= 1);
float output[14];
interpolateCubicCoords(src[0].x(), src[1].x(), src[2].x(), src[3].x(), &output[0], t);
interpolateCubicCoords(src[0].y(), src[1].y(), src[2].y(), src[3].y(), &output[1], t);
for (int i = 0; i < 7; i++)
dst[i].set(output[2 * i], output[2 * i + 1]);
}
bool xRayCrossesLine(const XRay& xRay, const FloatPoint pts[2], bool& ambiguous)
{
ambiguous = false;
if (xRay.y() == pts[0].y()) {
ambiguous = true;
return false;
}
if (xRay.y() < pts[0].y() && xRay.y() < pts[1].y())
return false;
if (xRay.y() > pts[0].y() && xRay.y() > pts[1].y())
return false;
if (xRay.x() > pts[0].x() && xRay.x() > pts[1].x())
return false;
if (nearlyZero(pts[0].y() - pts[1].y()))
return false;
if (nearlyZero(pts[0].x() - pts[1].x())) {
if (xRay.x() <= pts[0].x()) {
ambiguous = (xRay.y() == pts[1].y());
return true;
}
return false;
}
if (xRay.y() == pts[1].y()) {
if (xRay.x() <= pts[1].x()) {
ambiguous = true;
return true;
}
return false;
}
float deltaY = pts[1].y() - pts[0].y();
float deltaX = pts[1].x() - pts[0].x();
float slope = deltaY / deltaX;
float b = pts[0].y() - slope * pts[0].x();
float x = (xRay.y() - b) / slope;
return xRay.x() <= x;
}
int numXRayCrossingsForCubic(const XRay& xRay, const FloatPoint cubic[4], bool& ambiguous)
{
int numCrossings = 0;
FloatPoint monotonicCubics[10];
int numMonotonicCubics = 1 + chopCubicAtYExtrema(cubic, monotonicCubics);
ambiguous = false;
FloatPoint* monotonicCubicsPointer = &monotonicCubics[0];
for (int i = 0; i < numMonotonicCubics; ++i) {
if (xRayCrossesMonotonicCubic(xRay, monotonicCubicsPointer, ambiguous))
++numCrossings;
if (ambiguous)
return 0;
monotonicCubicsPointer += 3;
}
return numCrossings;
}
static inline int convexCompare(const FloatSize& delta)
{
return (delta.width() > 0) ? -1 :
(delta.width() < 0) ? 1 :
(delta.height() > 0) ? -1 :
(delta.height() < 0) ? 1 :
0;
}
static inline float convexCross(const FloatSize& p, const FloatSize& q)
{
return p.width() * q.height() - p.height() * q.width();
}
static inline bool convexCheckTriple(const FloatSize& dcur, const FloatSize& dprev, int* curDir, int* dirChanges, int* angleSign)
{
int thisDir = convexCompare(dcur);
if (thisDir == -*curDir)
++*dirChanges;
*curDir = thisDir;
float cross = convexCross(dprev, dcur);
if (cross > 0) {
if (*angleSign == -1)
return false;
*angleSign = 1;
} else if (cross < 0) {
if (*angleSign == 1)
return false;
*angleSign = -1;
}
return true;
}
bool isConvex(const FloatPoint* vertices, int nVertices)
{
int dirChanges = 0, angleSign = 0;
FloatPoint second, third;
FloatSize dprev, dcur;
if (nVertices < 3)
return false;
int i = 1;
while (true) {
second = vertices[i++];
dprev = second - vertices[0];
if (dprev.width() || dprev.height())
break;
if (i >= nVertices)
return false;
}
FloatPoint saveSecond = second;
int curDir = convexCompare(dprev);
while (i < nVertices) {
third = vertices[i++];
dcur = third - second;
if (!dcur.width() && !dcur.height())
continue;
if (!convexCheckTriple(dcur, dprev, &curDir, &dirChanges, &angleSign))
return false;
second = third;
dprev = dcur;
}
third = vertices[0];
dcur = third - second;
if (convexCompare(dcur)) {
if (!convexCheckTriple(dcur, dprev, &curDir, &dirChanges, &angleSign))
return false;
second = third;
dprev = dcur;
}
dcur = saveSecond - second;
if (!convexCheckTriple(dcur, dprev, &curDir, &dirChanges, &angleSign))
return false;
if (dirChanges > 2)
return false;
if (angleSign > 0 || angleSign < 0)
return true;
return false;
}
} }
#endif