1 /* 2 * Copyright (C) 2010 Google Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 16 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 17 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 18 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 19 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 20 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 21 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26 #include "config.h" 27 28 #if ENABLE(ACCELERATED_2D_CANVAS) 29 30 #include "LoopBlinnClassifier.h" 31 32 #include "LoopBlinnMathUtils.h" 33 34 namespace WebCore { 35 36 using LoopBlinnMathUtils::approxEqual; 37 using LoopBlinnMathUtils::roundToZero; 38 39 LoopBlinnClassifier::Result LoopBlinnClassifier::classify(const FloatPoint& c0, 40 const FloatPoint& c1, 41 const FloatPoint& c2, 42 const FloatPoint& c3) 43 { 44 // Consult the chapter for the definitions of the following 45 // (terse) variable names. Note that the b0..b3 coordinates are 46 // homogeneous, so the "z" value (actually the w coordinate) must 47 // be 1.0. 48 FloatPoint3D b0(c0.x(), c0.y(), 1.0f); 49 FloatPoint3D b1(c1.x(), c1.y(), 1.0f); 50 FloatPoint3D b2(c2.x(), c2.y(), 1.0f); 51 FloatPoint3D b3(c3.x(), c3.y(), 1.0f); 52 53 // Compute a1..a3. 54 float a1 = b0 * b3.cross(b2); 55 float a2 = b1 * b0.cross(b3); 56 float a3 = b2 * b1.cross(b0); 57 58 // Compute d1..d3. 59 float d1 = a1 - 2 * a2 + 3 * a3; 60 float d2 = -a2 + 3 * a3; 61 float d3 = 3 * a3; 62 63 // Experimentation has shown that the texture coordinates computed 64 // from these values quickly become huge, leading to roundoff errors 65 // and artifacts in the shader. It turns out that if we normalize 66 // the vector defined by (d1, d2, d3), this fixes the problem of the 67 // texture coordinates getting too large without affecting the 68 // classification results. 69 FloatPoint3D nd(d1, d2, d3); 70 nd.normalize(); 71 d1 = nd.x(); 72 d2 = nd.y(); 73 d3 = nd.z(); 74 75 // Compute the discriminant. 76 // term0 is a common term in the computation which helps decide 77 // which way to classify the cusp case: as serpentine or loop. 78 float term0 = (3 * d2 * d2 - 4 * d1 * d3); 79 float discriminant = d1 * d1 * term0; 80 81 // Experimentation has also shown that when the classification is 82 // near the boundary between one curve type and another, the shader 83 // becomes numerically unstable, particularly with the cusp case. 84 // Correct for this by rounding d1..d3 and the discriminant to zero 85 // when they get near it. 86 d1 = roundToZero(d1); 87 d2 = roundToZero(d2); 88 d3 = roundToZero(d3); 89 discriminant = roundToZero(discriminant); 90 91 // Do the classification. 92 if (approxEqual(b0, b1) && approxEqual(b0, b2) && approxEqual(b0, b3)) 93 return Result(kPoint, d1, d2, d3); 94 95 if (!discriminant) { 96 if (!d1 && !d2) { 97 if (!d3) 98 return Result(kLine, d1, d2, d3); 99 return Result(kQuadratic, d1, d2, d3); 100 } 101 102 if (!d1) 103 return Result(kCusp, d1, d2, d3); 104 105 // This is the boundary case described in Loop and Blinn's 106 // SIGGRAPH '05 paper of a cusp with inflection at infinity. 107 // Because term0 might not be exactly 0, we decide between using 108 // the serpentine and loop cases depending on its sign to avoid 109 // taking the square root of a negative number when computing the 110 // cubic texture coordinates. 111 if (term0 < 0) 112 return Result(kLoop, d1, d2, d3); 113 114 return Result(kSerpentine, d1, d2, d3); 115 } 116 117 if (discriminant > 0) 118 return Result(kSerpentine, d1, d2, d3); 119 120 // discriminant < 0 121 return Result(kLoop, d1, d2, d3); 122 } 123 124 } // namespace WebCore 125 126 #endif 127