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
classify(const FloatPoint & c0,const FloatPoint & c1,const FloatPoint & c2,const FloatPoint & c3)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