15abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick/* 25abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * Copyright (C) 2010 Google Inc. All rights reserved. 35abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * 45abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * Redistribution and use in source and binary forms, with or without 55abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * modification, are permitted provided that the following conditions 65abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * are met: 75abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * 85abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * 1. Redistributions of source code must retain the above copyright 95abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * notice, this list of conditions and the following disclaimer. 105abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * 2. Redistributions in binary form must reproduce the above copyright 115abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * notice, this list of conditions and the following disclaimer in the 125abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * documentation and/or other materials provided with the distribution. 135abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * 145abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 155abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 165abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 175abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 185abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 195abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 205abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 215abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 225abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 235abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 245abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick */ 255abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 265abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#include "config.h" 275abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 28a94275402997c11dd2e778633dacf4b7e630a35dBen Murdoch#if ENABLE(ACCELERATED_2D_CANVAS) 29a94275402997c11dd2e778633dacf4b7e630a35dBen Murdoch 305abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#include "LoopBlinnClassifier.h" 315abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 325abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick#include "LoopBlinnMathUtils.h" 335abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 345abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merricknamespace WebCore { 355abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 365abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrickusing LoopBlinnMathUtils::approxEqual; 375abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrickusing LoopBlinnMathUtils::roundToZero; 385abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 395abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain MerrickLoopBlinnClassifier::Result LoopBlinnClassifier::classify(const FloatPoint& c0, 405abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick const FloatPoint& c1, 415abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick const FloatPoint& c2, 425abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick const FloatPoint& c3) 435abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick{ 445abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Consult the chapter for the definitions of the following 455abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // (terse) variable names. Note that the b0..b3 coordinates are 465abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // homogeneous, so the "z" value (actually the w coordinate) must 475abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // be 1.0. 485abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick FloatPoint3D b0(c0.x(), c0.y(), 1.0f); 495abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick FloatPoint3D b1(c1.x(), c1.y(), 1.0f); 505abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick FloatPoint3D b2(c2.x(), c2.y(), 1.0f); 515abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick FloatPoint3D b3(c3.x(), c3.y(), 1.0f); 525abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 535abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Compute a1..a3. 545abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick float a1 = b0 * b3.cross(b2); 555abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick float a2 = b1 * b0.cross(b3); 565abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick float a3 = b2 * b1.cross(b0); 575abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 585abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Compute d1..d3. 595abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick float d1 = a1 - 2 * a2 + 3 * a3; 605abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick float d2 = -a2 + 3 * a3; 615abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick float d3 = 3 * a3; 625abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 635abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Experimentation has shown that the texture coordinates computed 645abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // from these values quickly become huge, leading to roundoff errors 655abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // and artifacts in the shader. It turns out that if we normalize 665abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // the vector defined by (d1, d2, d3), this fixes the problem of the 675abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // texture coordinates getting too large without affecting the 685abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // classification results. 695abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick FloatPoint3D nd(d1, d2, d3); 705abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick nd.normalize(); 715abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick d1 = nd.x(); 725abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick d2 = nd.y(); 735abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick d3 = nd.z(); 745abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 755abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Compute the discriminant. 765abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // term0 is a common term in the computation which helps decide 775abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // which way to classify the cusp case: as serpentine or loop. 785abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick float term0 = (3 * d2 * d2 - 4 * d1 * d3); 795abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick float discriminant = d1 * d1 * term0; 805abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 815abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Experimentation has also shown that when the classification is 825abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // near the boundary between one curve type and another, the shader 835abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // becomes numerically unstable, particularly with the cusp case. 845abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Correct for this by rounding d1..d3 and the discriminant to zero 855abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // when they get near it. 865abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick d1 = roundToZero(d1); 875abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick d2 = roundToZero(d2); 885abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick d3 = roundToZero(d3); 895abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick discriminant = roundToZero(discriminant); 905abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 915abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Do the classification. 925abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (approxEqual(b0, b1) && approxEqual(b0, b2) && approxEqual(b0, b3)) 935abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return Result(kPoint, d1, d2, d3); 945abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 955abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (!discriminant) { 965abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (!d1 && !d2) { 975abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (!d3) 985abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return Result(kLine, d1, d2, d3); 995abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return Result(kQuadratic, d1, d2, d3); 1005abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 1015abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1025abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (!d1) 1035abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return Result(kCusp, d1, d2, d3); 1045abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1055abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // This is the boundary case described in Loop and Blinn's 1065abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // SIGGRAPH '05 paper of a cusp with inflection at infinity. 1075abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // Because term0 might not be exactly 0, we decide between using 1085abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // the serpentine and loop cases depending on its sign to avoid 1095abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // taking the square root of a negative number when computing the 1105abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // cubic texture coordinates. 1115abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (term0 < 0) 1125abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return Result(kLoop, d1, d2, d3); 1135abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1145abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return Result(kSerpentine, d1, d2, d3); 1155abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick } 1165abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1175abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick if (discriminant > 0) 1185abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return Result(kSerpentine, d1, d2, d3); 1195abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1205abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick // discriminant < 0 1215abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick return Result(kLoop, d1, d2, d3); 1225abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick} 1235abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick 1245abb8606fa57c3ebfc8b3c3dbc3fa4a25d2ae306Iain Merrick} // namespace WebCore 125a94275402997c11dd2e778633dacf4b7e630a35dBen Murdoch 126a94275402997c11dd2e778633dacf4b7e630a35dBen Murdoch#endif 127