1 /*
2 * Copyright 2006 The Android Open Source Project
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8 #include "include/private/base/SkTo.h"
9 #include "src/base/SkMathPriv.h"
10 #include "src/core/SkAnalyticEdge.h"
11 #include "src/core/SkFDot6.h"
12 #include <utility>
13
14 static const int kInverseTableSize = 1024; // SK_FDot6One * 16
15
quick_inverse(SkFDot6 x)16 static inline SkFixed quick_inverse(SkFDot6 x) {
17 SkASSERT(SkAbs32(x) < kInverseTableSize);
18 static const int32_t table[kInverseTableSize * 2] = {
19 -4096, -4100, -4104, -4108, -4112, -4116, -4120, -4124, -4128, -4132, -4136,
20 -4140, -4144, -4148, -4152, -4156, -4161, -4165, -4169, -4173, -4177, -4181,
21 -4185, -4190, -4194, -4198, -4202, -4206, -4211, -4215, -4219, -4223, -4228,
22 -4232, -4236, -4240, -4245, -4249, -4253, -4258, -4262, -4266, -4271, -4275,
23 -4279, -4284, -4288, -4293, -4297, -4301, -4306, -4310, -4315, -4319, -4324,
24 -4328, -4332, -4337, -4341, -4346, -4350, -4355, -4359, -4364, -4369, -4373,
25 -4378, -4382, -4387, -4391, -4396, -4401, -4405, -4410, -4415, -4419, -4424,
26 -4429, -4433, -4438, -4443, -4447, -4452, -4457, -4462, -4466, -4471, -4476,
27 -4481, -4485, -4490, -4495, -4500, -4505, -4510, -4514, -4519, -4524, -4529,
28 -4534, -4539, -4544, -4549, -4554, -4559, -4563, -4568, -4573, -4578, -4583,
29 -4588, -4593, -4599, -4604, -4609, -4614, -4619, -4624, -4629, -4634, -4639,
30 -4644, -4650, -4655, -4660, -4665, -4670, -4675, -4681, -4686, -4691, -4696,
31 -4702, -4707, -4712, -4718, -4723, -4728, -4733, -4739, -4744, -4750, -4755,
32 -4760, -4766, -4771, -4777, -4782, -4788, -4793, -4798, -4804, -4809, -4815,
33 -4821, -4826, -4832, -4837, -4843, -4848, -4854, -4860, -4865, -4871, -4877,
34 -4882, -4888, -4894, -4899, -4905, -4911, -4917, -4922, -4928, -4934, -4940,
35 -4946, -4951, -4957, -4963, -4969, -4975, -4981, -4987, -4993, -4999, -5005,
36 -5011, -5017, -5023, -5029, -5035, -5041, -5047, -5053, -5059, -5065, -5071,
37 -5077, -5084, -5090, -5096, -5102, -5108, -5115, -5121, -5127, -5133, -5140,
38 -5146, -5152, -5159, -5165, -5171, -5178, -5184, -5190, -5197, -5203, -5210,
39 -5216, -5223, -5229, -5236, -5242, -5249, -5256, -5262, -5269, -5275, -5282,
40 -5289, -5295, -5302, -5309, -5315, -5322, -5329, -5336, -5343, -5349, -5356,
41 -5363, -5370, -5377, -5384, -5391, -5398, -5405, -5412, -5418, -5426, -5433,
42 -5440, -5447, -5454, -5461, -5468, -5475, -5482, -5489, -5497, -5504, -5511,
43 -5518, -5526, -5533, -5540, -5548, -5555, -5562, -5570, -5577, -5584, -5592,
44 -5599, -5607, -5614, -5622, -5629, -5637, -5645, -5652, -5660, -5667, -5675,
45 -5683, -5691, -5698, -5706, -5714, -5722, -5729, -5737, -5745, -5753, -5761,
46 -5769, -5777, -5785, -5793, -5801, -5809, -5817, -5825, -5833, -5841, -5849,
47 -5857, -5866, -5874, -5882, -5890, -5899, -5907, -5915, -5924, -5932, -5940,
48 -5949, -5957, -5966, -5974, -5983, -5991, -6000, -6009, -6017, -6026, -6034,
49 -6043, -6052, -6061, -6069, -6078, -6087, -6096, -6105, -6114, -6123, -6132,
50 -6141, -6150, -6159, -6168, -6177, -6186, -6195, -6204, -6213, -6223, -6232,
51 -6241, -6250, -6260, -6269, -6278, -6288, -6297, -6307, -6316, -6326, -6335,
52 -6345, -6355, -6364, -6374, -6384, -6393, -6403, -6413, -6423, -6432, -6442,
53 -6452, -6462, -6472, -6482, -6492, -6502, -6512, -6523, -6533, -6543, -6553,
54 -6563, -6574, -6584, -6594, -6605, -6615, -6626, -6636, -6647, -6657, -6668,
55 -6678, -6689, -6700, -6710, -6721, -6732, -6743, -6754, -6765, -6775, -6786,
56 -6797, -6808, -6820, -6831, -6842, -6853, -6864, -6875, -6887, -6898, -6909,
57 -6921, -6932, -6944, -6955, -6967, -6978, -6990, -7002, -7013, -7025, -7037,
58 -7049, -7061, -7073, -7084, -7096, -7108, -7121, -7133, -7145, -7157, -7169,
59 -7182, -7194, -7206, -7219, -7231, -7244, -7256, -7269, -7281, -7294, -7307,
60 -7319, -7332, -7345, -7358, -7371, -7384, -7397, -7410, -7423, -7436, -7449,
61 -7463, -7476, -7489, -7503, -7516, -7530, -7543, -7557, -7570, -7584, -7598,
62 -7612, -7626, -7639, -7653, -7667, -7681, -7695, -7710, -7724, -7738, -7752,
63 -7767, -7781, -7796, -7810, -7825, -7839, -7854, -7869, -7884, -7898, -7913,
64 -7928, -7943, -7958, -7973, -7989, -8004, -8019, -8035, -8050, -8065, -8081,
65 -8097, -8112, -8128, -8144, -8160, -8176, -8192, -8208, -8224, -8240, -8256,
66 -8272, -8289, -8305, -8322, -8338, -8355, -8371, -8388, -8405, -8422, -8439,
67 -8456, -8473, -8490, -8507, -8525, -8542, -8559, -8577, -8594, -8612, -8630,
68 -8648, -8665, -8683, -8701, -8719, -8738, -8756, -8774, -8793, -8811, -8830,
69 -8848, -8867, -8886, -8905, -8924, -8943, -8962, -8981, -9000, -9020, -9039,
70 -9058, -9078, -9098, -9118, -9137, -9157, -9177, -9198, -9218, -9238, -9258,
71 -9279, -9300, -9320, -9341, -9362, -9383, -9404, -9425, -9446, -9467, -9489,
72 -9510, -9532, -9554, -9576, -9597, -9619, -9642, -9664, -9686, -9709, -9731,
73 -9754, -9776, -9799, -9822, -9845, -9868, -9892, -9915, -9939, -9962, -9986,
74 -10010, -10034, -10058, -10082, -10106, -10131, -10155, -10180, -10205, -10230,
75 -10255, -10280, -10305, -10330, -10356, -10381, -10407, -10433, -10459, -10485,
76 -10512, -10538, -10564, -10591, -10618, -10645, -10672, -10699, -10727, -10754,
77 -10782, -10810, -10837, -10866, -10894, -10922, -10951, -10979, -11008, -11037,
78 -11066, -11096, -11125, -11155, -11184, -11214, -11244, -11275, -11305, -11335,
79 -11366, -11397, -11428, -11459, -11491, -11522, -11554, -11586, -11618, -11650,
80 -11683, -11715, -11748, -11781, -11814, -11848, -11881, -11915, -11949, -11983,
81 -12018, -12052, -12087, -12122, -12157, -12192, -12228, -12264, -12300, -12336,
82 -12372, -12409, -12446, -12483, -12520, -12557, -12595, -12633, -12671, -12710,
83 -12748, -12787, -12826, -12865, -12905, -12945, -12985, -13025, -13066, -13107,
84 -13148, -13189, -13231, -13273, -13315, -13357, -13400, -13443, -13486, -13530,
85 -13573, -13617, -13662, -13706, -13751, -13797, -13842, -13888, -13934, -13981,
86 -14027, -14074, -14122, -14169, -14217, -14266, -14315, -14364, -14413, -14463,
87 -14513, -14563, -14614, -14665, -14716, -14768, -14820, -14873, -14926, -14979,
88 -15033, -15087, -15141, -15196, -15252, -15307, -15363, -15420, -15477, -15534,
89 -15592, -15650, -15709, -15768, -15827, -15887, -15947, -16008, -16070, -16131,
90 -16194, -16256, -16320, -16384, -16448, -16513, -16578, -16644, -16710, -16777,
91 -16844, -16912, -16980, -17050, -17119, -17189, -17260, -17331, -17403, -17476,
92 -17549, -17623, -17697, -17772, -17848, -17924, -18001, -18078, -18157, -18236,
93 -18315, -18396, -18477, -18558, -18641, -18724, -18808, -18893, -18978, -19065,
94 -19152, -19239, -19328, -19418, -19508, -19599, -19691, -19784, -19878, -19972,
95 -20068, -20164, -20262, -20360, -20460, -20560, -20661, -20763, -20867, -20971,
96 -21076, -21183, -21290, -21399, -21509, -21620, -21732, -21845, -21959, -22075,
97 -22192, -22310, -22429, -22550, -22671, -22795, -22919, -23045, -23172, -23301,
98 -23431, -23563, -23696, -23831, -23967, -24105, -24244, -24385, -24528, -24672,
99 -24818, -24966, -25115, -25266, -25420, -25575, -25731, -25890, -26051, -26214,
100 -26379, -26546, -26715, -26886, -27060, -27235, -27413, -27594, -27776, -27962,
101 -28149, -28339, -28532, -28728, -28926, -29127, -29330, -29537, -29746, -29959,
102 -30174, -30393, -30615, -30840, -31068, -31300, -31536, -31775, -32017, -32263,
103 -32513, -32768, -33026, -33288, -33554, -33825, -34100, -34379, -34663, -34952,
104 -35246, -35544, -35848, -36157, -36472, -36792, -37117, -37449, -37786, -38130,
105 -38479, -38836, -39199, -39568, -39945, -40329, -40721, -41120, -41527, -41943,
106 -42366, -42799, -43240, -43690, -44150, -44620, -45100, -45590, -46091, -46603,
107 -47127, -47662, -48210, -48770, -49344, -49932, -50533, -51150, -51781, -52428,
108 -53092, -53773, -54471, -55188, -55924, -56679, -57456, -58254, -59074, -59918,
109 -60787, -61680, -62601, -63550, -64527, -65536, -66576, -67650, -68759, -69905,
110 -71089, -72315, -73584, -74898, -76260, -77672, -79137, -80659, -82241, -83886,
111 -85598, -87381, -89240, -91180, -93206, -95325, -97541, -99864, -102300,
112 -104857, -107546, -110376, -113359, -116508, -119837, -123361, -127100, -131072,
113 -135300, -139810, -144631, -149796, -155344, -161319, -167772, -174762, -182361,
114 -190650, -199728, -209715, -220752, -233016, -246723, -262144, -279620, -299593,
115 -322638, -349525, -381300, -419430, -466033, -524288, -599186, -699050, -838860,
116 -1048576, -1398101, -2097152, -4194304, 0, 4194304, 2097152, 1398101, 1048576,
117 838860, 699050, 599186, 524288, 466033, 419430, 381300, 349525, 322638, 299593,
118 279620, 262144, 246723, 233016, 220752, 209715, 199728, 190650, 182361, 174762,
119 167772, 161319, 155344, 149796, 144631, 139810, 135300, 131072, 127100, 123361,
120 119837, 116508, 113359, 110376, 107546, 104857, 102300, 99864, 97541, 95325,
121 93206, 91180, 89240, 87381, 85598, 83886, 82241, 80659, 79137, 77672, 76260,
122 74898, 73584, 72315, 71089, 69905, 68759, 67650, 66576, 65536, 64527, 63550,
123 62601, 61680, 60787, 59918, 59074, 58254, 57456, 56679, 55924, 55188, 54471,
124 53773, 53092, 52428, 51781, 51150, 50533, 49932, 49344, 48770, 48210, 47662,
125 47127, 46603, 46091, 45590, 45100, 44620, 44150, 43690, 43240, 42799, 42366,
126 41943, 41527, 41120, 40721, 40329, 39945, 39568, 39199, 38836, 38479, 38130,
127 37786, 37449, 37117, 36792, 36472, 36157, 35848, 35544, 35246, 34952, 34663,
128 34379, 34100, 33825, 33554, 33288, 33026, 32768, 32513, 32263, 32017, 31775,
129 31536, 31300, 31068, 30840, 30615, 30393, 30174, 29959, 29746, 29537, 29330,
130 29127, 28926, 28728, 28532, 28339, 28149, 27962, 27776, 27594, 27413, 27235,
131 27060, 26886, 26715, 26546, 26379, 26214, 26051, 25890, 25731, 25575, 25420,
132 25266, 25115, 24966, 24818, 24672, 24528, 24385, 24244, 24105, 23967, 23831,
133 23696, 23563, 23431, 23301, 23172, 23045, 22919, 22795, 22671, 22550, 22429,
134 22310, 22192, 22075, 21959, 21845, 21732, 21620, 21509, 21399, 21290, 21183,
135 21076, 20971, 20867, 20763, 20661, 20560, 20460, 20360, 20262, 20164, 20068,
136 19972, 19878, 19784, 19691, 19599, 19508, 19418, 19328, 19239, 19152, 19065,
137 18978, 18893, 18808, 18724, 18641, 18558, 18477, 18396, 18315, 18236, 18157,
138 18078, 18001, 17924, 17848, 17772, 17697, 17623, 17549, 17476, 17403, 17331,
139 17260, 17189, 17119, 17050, 16980, 16912, 16844, 16777, 16710, 16644, 16578,
140 16513, 16448, 16384, 16320, 16256, 16194, 16131, 16070, 16008, 15947, 15887,
141 15827, 15768, 15709, 15650, 15592, 15534, 15477, 15420, 15363, 15307, 15252,
142 15196, 15141, 15087, 15033, 14979, 14926, 14873, 14820, 14768, 14716, 14665,
143 14614, 14563, 14513, 14463, 14413, 14364, 14315, 14266, 14217, 14169, 14122,
144 14074, 14027, 13981, 13934, 13888, 13842, 13797, 13751, 13706, 13662, 13617,
145 13573, 13530, 13486, 13443, 13400, 13357, 13315, 13273, 13231, 13189, 13148,
146 13107, 13066, 13025, 12985, 12945, 12905, 12865, 12826, 12787, 12748, 12710,
147 12671, 12633, 12595, 12557, 12520, 12483, 12446, 12409, 12372, 12336, 12300,
148 12264, 12228, 12192, 12157, 12122, 12087, 12052, 12018, 11983, 11949, 11915,
149 11881, 11848, 11814, 11781, 11748, 11715, 11683, 11650, 11618, 11586, 11554,
150 11522, 11491, 11459, 11428, 11397, 11366, 11335, 11305, 11275, 11244, 11214,
151 11184, 11155, 11125, 11096, 11066, 11037, 11008, 10979, 10951, 10922, 10894,
152 10866, 10837, 10810, 10782, 10754, 10727, 10699, 10672, 10645, 10618, 10591,
153 10564, 10538, 10512, 10485, 10459, 10433, 10407, 10381, 10356, 10330, 10305,
154 10280, 10255, 10230, 10205, 10180, 10155, 10131, 10106, 10082, 10058, 10034,
155 10010, 9986, 9962, 9939, 9915, 9892, 9868, 9845, 9822, 9799, 9776, 9754, 9731,
156 9709, 9686, 9664, 9642, 9619, 9597, 9576, 9554, 9532, 9510, 9489, 9467, 9446,
157 9425, 9404, 9383, 9362, 9341, 9320, 9300, 9279, 9258, 9238, 9218, 9198, 9177,
158 9157, 9137, 9118, 9098, 9078, 9058, 9039, 9020, 9000, 8981, 8962, 8943, 8924,
159 8905, 8886, 8867, 8848, 8830, 8811, 8793, 8774, 8756, 8738, 8719, 8701, 8683,
160 8665, 8648, 8630, 8612, 8594, 8577, 8559, 8542, 8525, 8507, 8490, 8473, 8456,
161 8439, 8422, 8405, 8388, 8371, 8355, 8338, 8322, 8305, 8289, 8272, 8256, 8240,
162 8224, 8208, 8192, 8176, 8160, 8144, 8128, 8112, 8097, 8081, 8065, 8050, 8035,
163 8019, 8004, 7989, 7973, 7958, 7943, 7928, 7913, 7898, 7884, 7869, 7854, 7839,
164 7825, 7810, 7796, 7781, 7767, 7752, 7738, 7724, 7710, 7695, 7681, 7667, 7653,
165 7639, 7626, 7612, 7598, 7584, 7570, 7557, 7543, 7530, 7516, 7503, 7489, 7476,
166 7463, 7449, 7436, 7423, 7410, 7397, 7384, 7371, 7358, 7345, 7332, 7319, 7307,
167 7294, 7281, 7269, 7256, 7244, 7231, 7219, 7206, 7194, 7182, 7169, 7157, 7145,
168 7133, 7121, 7108, 7096, 7084, 7073, 7061, 7049, 7037, 7025, 7013, 7002, 6990,
169 6978, 6967, 6955, 6944, 6932, 6921, 6909, 6898, 6887, 6875, 6864, 6853, 6842,
170 6831, 6820, 6808, 6797, 6786, 6775, 6765, 6754, 6743, 6732, 6721, 6710, 6700,
171 6689, 6678, 6668, 6657, 6647, 6636, 6626, 6615, 6605, 6594, 6584, 6574, 6563,
172 6553, 6543, 6533, 6523, 6512, 6502, 6492, 6482, 6472, 6462, 6452, 6442, 6432,
173 6423, 6413, 6403, 6393, 6384, 6374, 6364, 6355, 6345, 6335, 6326, 6316, 6307,
174 6297, 6288, 6278, 6269, 6260, 6250, 6241, 6232, 6223, 6213, 6204, 6195, 6186,
175 6177, 6168, 6159, 6150, 6141, 6132, 6123, 6114, 6105, 6096, 6087, 6078, 6069,
176 6061, 6052, 6043, 6034, 6026, 6017, 6009, 6000, 5991, 5983, 5974, 5966, 5957,
177 5949, 5940, 5932, 5924, 5915, 5907, 5899, 5890, 5882, 5874, 5866, 5857, 5849,
178 5841, 5833, 5825, 5817, 5809, 5801, 5793, 5785, 5777, 5769, 5761, 5753, 5745,
179 5737, 5729, 5722, 5714, 5706, 5698, 5691, 5683, 5675, 5667, 5660, 5652, 5645,
180 5637, 5629, 5622, 5614, 5607, 5599, 5592, 5584, 5577, 5570, 5562, 5555, 5548,
181 5540, 5533, 5526, 5518, 5511, 5504, 5497, 5489, 5482, 5475, 5468, 5461, 5454,
182 5447, 5440, 5433, 5426, 5418, 5412, 5405, 5398, 5391, 5384, 5377, 5370, 5363,
183 5356, 5349, 5343, 5336, 5329, 5322, 5315, 5309, 5302, 5295, 5289, 5282, 5275,
184 5269, 5262, 5256, 5249, 5242, 5236, 5229, 5223, 5216, 5210, 5203, 5197, 5190,
185 5184, 5178, 5171, 5165, 5159, 5152, 5146, 5140, 5133, 5127, 5121, 5115, 5108,
186 5102, 5096, 5090, 5084, 5077, 5071, 5065, 5059, 5053, 5047, 5041, 5035, 5029,
187 5023, 5017, 5011, 5005, 4999, 4993, 4987, 4981, 4975, 4969, 4963, 4957, 4951,
188 4946, 4940, 4934, 4928, 4922, 4917, 4911, 4905, 4899, 4894, 4888, 4882, 4877,
189 4871, 4865, 4860, 4854, 4848, 4843, 4837, 4832, 4826, 4821, 4815, 4809, 4804,
190 4798, 4793, 4788, 4782, 4777, 4771, 4766, 4760, 4755, 4750, 4744, 4739, 4733,
191 4728, 4723, 4718, 4712, 4707, 4702, 4696, 4691, 4686, 4681, 4675, 4670, 4665,
192 4660, 4655, 4650, 4644, 4639, 4634, 4629, 4624, 4619, 4614, 4609, 4604, 4599,
193 4593, 4588, 4583, 4578, 4573, 4568, 4563, 4559, 4554, 4549, 4544, 4539, 4534,
194 4529, 4524, 4519, 4514, 4510, 4505, 4500, 4495, 4490, 4485, 4481, 4476, 4471,
195 4466, 4462, 4457, 4452, 4447, 4443, 4438, 4433, 4429, 4424, 4419, 4415, 4410,
196 4405, 4401, 4396, 4391, 4387, 4382, 4378, 4373, 4369, 4364, 4359, 4355, 4350,
197 4346, 4341, 4337, 4332, 4328, 4324, 4319, 4315, 4310, 4306, 4301, 4297, 4293,
198 4288, 4284, 4279, 4275, 4271, 4266, 4262, 4258, 4253, 4249, 4245, 4240, 4236,
199 4232, 4228, 4223, 4219, 4215, 4211, 4206, 4202, 4198, 4194, 4190, 4185, 4181,
200 4177, 4173, 4169, 4165, 4161, 4156, 4152, 4148, 4144, 4140, 4136, 4132, 4128,
201 4124, 4120, 4116, 4112, 4108, 4104, 4100
202 };
203 return table[kInverseTableSize + x];
204 }
205
quick_div(SkFDot6 a,SkFDot6 b)206 static inline SkFixed quick_div(SkFDot6 a, SkFDot6 b) {
207 const int kMinBits = 3; // abs(b) should be at least (1 << kMinBits) for quick division
208 const int kMaxBits = 31; // Number of bits available in signed int
209 // Given abs(b) <= (1 << kMinBits), the inverse of abs(b) is at most 1 << (22 - kMinBits) in
210 // SkFixed format. Hence abs(a) should be less than kMaxAbsA
211 const int kMaxAbsA = 1 << (kMaxBits - (22 - kMinBits));
212 SkFDot6 abs_a = SkAbs32(a);
213 SkFDot6 abs_b = SkAbs32(b);
214 if (abs_b >= (1 << kMinBits) && abs_b < kInverseTableSize && abs_a < kMaxAbsA) {
215 SkASSERT((int64_t)a * quick_inverse(b) <= SK_MaxS32
216 && (int64_t)a * quick_inverse(b) >= SK_MinS32);
217 SkFixed ourAnswer = (a * quick_inverse(b)) >> 6;
218 SkASSERT(
219 (SkFDot6Div(a,b) == 0 && ourAnswer == 0) ||
220 SkFixedDiv(SkAbs32(SkFDot6Div(a,b) - ourAnswer), SkAbs32(SkFDot6Div(a,b))) <= 1 << 10
221 );
222 return ourAnswer;
223 }
224 return SkFDot6Div(a, b);
225 }
226
setLine(const SkPoint & p0,const SkPoint & p1)227 bool SkAnalyticEdge::setLine(const SkPoint& p0, const SkPoint& p1) {
228 fRiteE = nullptr;
229
230 // We must set X/Y using the same way (e.g., times 4, to FDot6, then to Fixed) as Quads/Cubics.
231 // Otherwise the order of the edge might be wrong due to precision limit.
232 const int accuracy = kDefaultAccuracy;
233 #ifdef SK_RASTERIZE_EVEN_ROUNDING
234 SkFixed x0 = SkFDot6ToFixed(SkScalarRoundToFDot6(p0.fX, accuracy)) >> accuracy;
235 SkFixed y0 = SnapY(SkFDot6ToFixed(SkScalarRoundToFDot6(p0.fY, accuracy)) >> accuracy);
236 SkFixed x1 = SkFDot6ToFixed(SkScalarRoundToFDot6(p1.fX, accuracy)) >> accuracy;
237 SkFixed y1 = SnapY(SkFDot6ToFixed(SkScalarRoundToFDot6(p1.fY, accuracy)) >> accuracy);
238 #else
239 const int multiplier = (1 << kDefaultAccuracy);
240 SkFixed x0 = SkFDot6ToFixed(SkScalarToFDot6(p0.fX * multiplier)) >> accuracy;
241 SkFixed y0 = SnapY(SkFDot6ToFixed(SkScalarToFDot6(p0.fY * multiplier)) >> accuracy);
242 SkFixed x1 = SkFDot6ToFixed(SkScalarToFDot6(p1.fX * multiplier)) >> accuracy;
243 SkFixed y1 = SnapY(SkFDot6ToFixed(SkScalarToFDot6(p1.fY * multiplier)) >> accuracy);
244 #endif
245
246 int winding = 1;
247
248 if (y0 > y1) {
249 using std::swap;
250 swap(x0, x1);
251 swap(y0, y1);
252 winding = -1;
253 }
254
255 // are we a zero-height line?
256 SkFDot6 dy = SkFixedToFDot6(y1 - y0);
257 if (dy == 0) {
258 return false;
259 }
260 SkFDot6 dx = SkFixedToFDot6(x1 - x0);
261 SkFixed slope = quick_div(dx, dy);
262 SkFixed absSlope = SkAbs32(slope);
263
264 fX = x0;
265 fDX = slope;
266 fUpperX = x0;
267 fY = y0;
268 fUpperY = y0;
269 fLowerY = y1;
270 fDY = dx == 0 || slope == 0 ? SK_MaxS32 : absSlope < kInverseTableSize
271 ? quick_inverse(absSlope)
272 : SkAbs32(quick_div(dy, dx));
273 fEdgeType = kLine_Type;
274 fCurveCount = 0;
275 fWinding = SkToS8(winding);
276 fCurveShift = 0;
277
278 return true;
279 }
280
281 // This will become a bottleneck for small ovals rendering if we call SkFixedDiv twice here.
282 // Therefore, we'll let the outter function compute the slope once and send in the value.
283 // Moreover, we'll compute fDY by quickly lookup the inverse table (if possible).
updateLine(SkFixed x0,SkFixed y0,SkFixed x1,SkFixed y1,SkFixed slope)284 bool SkAnalyticEdge::updateLine(SkFixed x0, SkFixed y0, SkFixed x1, SkFixed y1, SkFixed slope) {
285 // Since we send in the slope, we can no longer snap y inside this function.
286 // If we don't send in the slope, or we do some more sophisticated snapping, this function
287 // could be a performance bottleneck.
288 SkASSERT(fWinding == 1 || fWinding == -1);
289 SkASSERT(fCurveCount != 0);
290
291 // We don't chop at y extrema for cubics so the y is not guaranteed to be increasing for them.
292 // In that case, we have to swap x/y and negate the winding.
293 if (y0 > y1) {
294 using std::swap;
295 swap(x0, x1);
296 swap(y0, y1);
297 fWinding = -fWinding;
298 }
299
300 SkASSERT(y0 <= y1);
301
302 SkFDot6 dx = SkFixedToFDot6(x1 - x0);
303 SkFDot6 dy = SkFixedToFDot6(y1 - y0);
304
305 // are we a zero-height line?
306 if (dy == 0) {
307 return false;
308 }
309
310 SkASSERT(slope < SK_MaxS32);
311
312 SkFDot6 absSlope = SkAbs32(SkFixedToFDot6(slope));
313 fX = x0;
314 fDX = slope;
315 fUpperX = x0;
316 fY = y0;
317 fUpperY = y0;
318 fLowerY = y1;
319 fDY = (dx == 0 || slope == 0)
320 ? SK_MaxS32
321 : absSlope < kInverseTableSize
322 ? quick_inverse(absSlope)
323 : SkAbs32(quick_div(dy, dx));
324
325 return true;
326 }
327
update(SkFixed last_y,bool sortY)328 bool SkAnalyticEdge::update(SkFixed last_y, bool sortY) {
329 SkASSERT(last_y >= fLowerY); // we shouldn't update edge if last_y < fLowerY
330 if (fCurveCount < 0) {
331 return static_cast<SkAnalyticCubicEdge*>(this)->updateCubic(sortY);
332 } else if (fCurveCount > 0) {
333 return static_cast<SkAnalyticQuadraticEdge*>(this)->updateQuadratic();
334 }
335 return false;
336 }
337
setQuadratic(const SkPoint pts[3])338 bool SkAnalyticQuadraticEdge::setQuadratic(const SkPoint pts[3]) {
339 fRiteE = nullptr;
340
341 if (!fQEdge.setQuadraticWithoutUpdate(pts, kDefaultAccuracy)) {
342 return false;
343 }
344 fQEdge.fQx >>= kDefaultAccuracy;
345 fQEdge.fQy >>= kDefaultAccuracy;
346 fQEdge.fQDx >>= kDefaultAccuracy;
347 fQEdge.fQDy >>= kDefaultAccuracy;
348 fQEdge.fQDDx >>= kDefaultAccuracy;
349 fQEdge.fQDDy >>= kDefaultAccuracy;
350 fQEdge.fQLastX >>= kDefaultAccuracy;
351 fQEdge.fQLastY >>= kDefaultAccuracy;
352 fQEdge.fQy = SnapY(fQEdge.fQy);
353 fQEdge.fQLastY = SnapY(fQEdge.fQLastY);
354
355 fWinding = fQEdge.fWinding;
356 fEdgeType = kQuad_Type;
357 fCurveCount = fQEdge.fCurveCount;
358 fCurveShift = fQEdge.fCurveShift;
359
360 fSnappedX = fQEdge.fQx;
361 fSnappedY = fQEdge.fQy;
362
363 return this->updateQuadratic();
364 }
365
updateQuadratic()366 bool SkAnalyticQuadraticEdge::updateQuadratic() {
367 int success = 0; // initialize to fail!
368 int count = fCurveCount;
369 SkFixed oldx = fQEdge.fQx;
370 SkFixed oldy = fQEdge.fQy;
371 SkFixed dx = fQEdge.fQDx;
372 SkFixed dy = fQEdge.fQDy;
373 SkFixed newx, newy, newSnappedX, newSnappedY;
374 int shift = fCurveShift;
375
376 SkASSERT(count > 0);
377
378 do {
379 SkFixed slope;
380 if (--count > 0)
381 {
382 newx = oldx + (dx >> shift);
383 newy = oldy + (dy >> shift);
384 if (SkAbs32(dy >> shift) >= SK_Fixed1 * 2) { // only snap when dy is large enough
385 SkFDot6 diffY = SkFixedToFDot6(newy - fSnappedY);
386 slope = diffY ? quick_div(SkFixedToFDot6(newx - fSnappedX), diffY)
387 : SK_MaxS32;
388 newSnappedY = std::min<SkFixed>(fQEdge.fQLastY, SkFixedRoundToFixed(newy));
389 newSnappedX = newx - SkFixedMul(slope, newy - newSnappedY);
390 } else {
391 newSnappedY = std::min(fQEdge.fQLastY, SnapY(newy));
392 newSnappedX = newx;
393 SkFDot6 diffY = SkFixedToFDot6(newSnappedY - fSnappedY);
394 slope = diffY ? quick_div(SkFixedToFDot6(newx - fSnappedX), diffY)
395 : SK_MaxS32;
396 }
397 dx += fQEdge.fQDDx;
398 dy += fQEdge.fQDDy;
399 }
400 else // last segment
401 {
402 newx = fQEdge.fQLastX;
403 newy = fQEdge.fQLastY;
404 newSnappedY = newy;
405 newSnappedX = newx;
406 SkFDot6 diffY = (newy - fSnappedY) >> 10;
407 slope = diffY ? quick_div((newx - fSnappedX) >> 10, diffY) : SK_MaxS32;
408 }
409 if (slope < SK_MaxS32) {
410 success = this->updateLine(fSnappedX, fSnappedY, newSnappedX, newSnappedY, slope);
411 }
412 oldx = newx;
413 oldy = newy;
414 } while (count > 0 && !success);
415
416 SkASSERT(newSnappedY <= fQEdge.fQLastY);
417
418 fQEdge.fQx = newx;
419 fQEdge.fQy = newy;
420 fQEdge.fQDx = dx;
421 fQEdge.fQDy = dy;
422 fSnappedX = newSnappedX;
423 fSnappedY = newSnappedY;
424 fCurveCount = SkToS8(count);
425 return success;
426 }
427
setCubic(const SkPoint pts[4],bool sortY)428 bool SkAnalyticCubicEdge::setCubic(const SkPoint pts[4], bool sortY) {
429 fRiteE = nullptr;
430
431 if (!fCEdge.setCubicWithoutUpdate(pts, kDefaultAccuracy, sortY)) {
432 return false;
433 }
434
435 fCEdge.fCx >>= kDefaultAccuracy;
436 fCEdge.fCy >>= kDefaultAccuracy;
437 fCEdge.fCDx >>= kDefaultAccuracy;
438 fCEdge.fCDy >>= kDefaultAccuracy;
439 fCEdge.fCDDx >>= kDefaultAccuracy;
440 fCEdge.fCDDy >>= kDefaultAccuracy;
441 fCEdge.fCDDDx >>= kDefaultAccuracy;
442 fCEdge.fCDDDy >>= kDefaultAccuracy;
443 fCEdge.fCLastX >>= kDefaultAccuracy;
444 fCEdge.fCLastY >>= kDefaultAccuracy;
445 fCEdge.fCy = SnapY(fCEdge.fCy);
446 fCEdge.fCLastY = SnapY(fCEdge.fCLastY);
447
448 fWinding = fCEdge.fWinding;
449 fEdgeType = kCubic_Type;
450 fCurveCount = fCEdge.fCurveCount;
451 fCurveShift = fCEdge.fCurveShift;
452 fCubicDShift = fCEdge.fCubicDShift;
453
454 fSnappedY = fCEdge.fCy;
455
456 return this->updateCubic(sortY);
457 }
458
updateCubic(bool sortY)459 bool SkAnalyticCubicEdge::updateCubic(bool sortY) {
460 int success;
461 int count = fCurveCount;
462 SkFixed oldx = fCEdge.fCx;
463 SkFixed oldy = fCEdge.fCy;
464 SkFixed newx, newy;
465 const int ddshift = fCurveShift;
466 const int dshift = fCubicDShift;
467
468 SkASSERT(count < 0);
469
470 do {
471 if (++count < 0) {
472 newx = oldx + (fCEdge.fCDx >> dshift);
473 fCEdge.fCDx += fCEdge.fCDDx >> ddshift;
474 fCEdge.fCDDx += fCEdge.fCDDDx;
475
476 newy = oldy + (fCEdge.fCDy >> dshift);
477 fCEdge.fCDy += fCEdge.fCDDy >> ddshift;
478 fCEdge.fCDDy += fCEdge.fCDDDy;
479 }
480 else { // last segment
481 newx = fCEdge.fCLastX;
482 newy = fCEdge.fCLastY;
483 }
484
485 // we want to say SkASSERT(oldy <= newy), but our finite fixedpoint
486 // doesn't always achieve that, so we have to explicitly pin it here.
487 if (sortY && newy < oldy) {
488 newy = oldy;
489 }
490
491 SkFixed newSnappedY = SnapY(newy);
492 // we want to SkASSERT(snappedNewY <= fCEdge.fCLastY), but our finite fixedpoint
493 // doesn't always achieve that, so we have to explicitly pin it here.
494 if (sortY && fCEdge.fCLastY < newSnappedY) {
495 newSnappedY = fCEdge.fCLastY;
496 count = 0;
497 }
498
499 SkFixed slope = SkFixedToFDot6(newSnappedY - fSnappedY) == 0
500 ? SK_MaxS32
501 : SkFDot6Div(SkFixedToFDot6(newx - oldx),
502 SkFixedToFDot6(newSnappedY - fSnappedY));
503
504 success = this->updateLine(oldx, fSnappedY, newx, newSnappedY, slope);
505
506 oldx = newx;
507 oldy = newy;
508 fSnappedY = newSnappedY;
509 } while (count < 0 && !success);
510
511 fCEdge.fCx = newx;
512 fCEdge.fCy = newy;
513 fCurveCount = SkToS8(count);
514 return success;
515 }
516