Home | History | Annotate | Download | only in gpu 
      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