1 /*
2 * Copyright (c) 2022 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include "gfx_utils/diagram/vertexprimitive/geometry_curves.h"
17 #include "gfx_utils/graphic_math.h"
18 #include "gfx_utils/diagram/common/common_math.h"
19 namespace OHOS {
20 const float CURVE_COLLINEARITY_EPSILON = 1e-30;
21 const float CURVE_ANGLE_TO_LERANCE_EPSILON = 0.01f;
22 const int32_t CURVE_RECURSION_LIMIT = 32;
23 const float CURVES_NUM_STEP_LEN = 0.25f;
ApproximationScale() const24 float QuadBezierCurveIncr::ApproximationScale() const
25 {
26 return approximationScale_;
27 }
28
ApproximationScale(float scale)29 void QuadBezierCurveIncr::ApproximationScale(float scale)
30 {
31 approximationScale_ = scale;
32 }
33
Init(float x1,float y1,float x2,float y2,float x3,float y3)34 void QuadBezierCurveIncr::Init(float x1, float y1,
35 float x2, float y2,
36 float x3, float y3)
37 {
38 startCoordinate_.x = x1;
39 startCoordinate_.y = y1;
40 endCoordinate_.x = x3;
41 endCoordinate_.y = y3;
42
43 float deltaX1 = x2 - x1;
44 float deltaY1 = y2 - y1;
45 float deltaX2 = x3 - x2;
46 float deltaY2 = y3 - y2;
47
48 float len = Sqrt(deltaX1 * deltaX1 + deltaY1 * deltaY1) +
49 Sqrt(deltaX2 * deltaX2 + deltaY2 * deltaY2);
50
51 numberSteps_ = MATH_UROUND(len * CURVES_NUM_STEP_LEN * approximationScale_);
52 const int32_t numStepsMax = 4;
53 if (numberSteps_ < numStepsMax) {
54 numberSteps_ = numStepsMax;
55 }
56 if (numberSteps_ == 0) {
57 return;
58 }
59 float subdivideStep = 1.0f / numberSteps_;
60 float subdivideStep2 = subdivideStep * subdivideStep;
61
62 float tmpX = (x1 - x2 * FLOATNUM + x3) * subdivideStep2;
63 float tmpY = (y1 - y2 * FLOATNUM + y3) * subdivideStep2;
64
65 savedFinalCoordinate_.x = x1;
66 finalCoordinate_.x = x1;
67 savedFinalCoordinate_.y = y1;
68 finalCoordinate_.y = y1;
69
70 savedDeltaFinalCoordinate_.x = tmpX + (x2 - x1) * (FLOATNUM * subdivideStep);
71 deltaFinalCoordinate_.x = tmpX + (x2 - x1) * (FLOATNUM * subdivideStep);
72 savedDeltaFinalCoordinate_.y = tmpY + (y2 - y1) * (FLOATNUM * subdivideStep);
73 deltaFinalCoordinate_.y = tmpY + (y2 - y1) * (FLOATNUM * subdivideStep);
74
75 copyDeltaFinalCoordinate_.x = tmpX * FLOATNUM;
76 copyDeltaFinalCoordinate_.y = tmpY * FLOATNUM;
77
78 currentStep_ = numberSteps_;
79 }
80
Rewind(uint32_t)81 void QuadBezierCurveIncr::Rewind(uint32_t)
82 {
83 if (numberSteps_ == 0) {
84 currentStep_ = -1;
85 return;
86 }
87
88 currentStep_ = numberSteps_;
89 finalCoordinate_.x = savedFinalCoordinate_.x;
90 finalCoordinate_.y = savedFinalCoordinate_.y;
91 deltaFinalCoordinate_.x = savedDeltaFinalCoordinate_.x;
92 deltaFinalCoordinate_.y = savedDeltaFinalCoordinate_.y;
93 }
94
GenerateVertex(float * x,float * y)95 uint32_t QuadBezierCurveIncr::GenerateVertex(float* x, float* y)
96 {
97 if (currentStep_ < 0) {
98 return PATH_CMD_STOP;
99 }
100 if (currentStep_ == numberSteps_) {
101 *x = startCoordinate_.x;
102 *y = startCoordinate_.y;
103 --currentStep_;
104 return PATH_CMD_MOVE_TO;
105 }
106 if (currentStep_ == 0) {
107 *x = endCoordinate_.x;
108 *y = endCoordinate_.y;
109 --currentStep_;
110 return PATH_CMD_LINE_TO;
111 }
112
113 finalCoordinate_.x += deltaFinalCoordinate_.x;
114 finalCoordinate_.y += deltaFinalCoordinate_.y;
115 deltaFinalCoordinate_.x += copyDeltaFinalCoordinate_.x;
116 deltaFinalCoordinate_.y += copyDeltaFinalCoordinate_.y;
117 *x = finalCoordinate_.x;
118 *y = finalCoordinate_.y;
119 --currentStep_;
120 return PATH_CMD_LINE_TO;
121 }
122
Init(float x1,float y1,float x2,float y2,float x3,float y3)123 void QuadrBezierCurveDividOp::Init(float x1, float y1,
124 float x2, float y2,
125 float x3, float y3)
126 {
127 points_.Clear();
128 distanceToleranceSquare_ = HALFNUM / approximationScale_;
129 distanceToleranceSquare_ *= distanceToleranceSquare_;
130 Bezier(x1, y1, x2, y2, x3, y3);
131 count_ = 0;
132 }
133
Recursive(float x1,float y1,float x2,float y2,float x3,float y3,uint32_t level)134 void QuadrBezierCurveDividOp::Recursive(float x1, float y1,
135 float x2, float y2,
136 float x3, float y3,
137 uint32_t level)
138 {
139 if (level > CURVE_RECURSION_LIMIT) {
140 return;
141 }
142
143 // Calculates All Midpoints Of a Segment
144 float x12 = (x1 + x2) / FLOATNUM;
145 float y12 = (y1 + y2) / FLOATNUM;
146 float x23 = (x2 + x3) / FLOATNUM;
147 float y23 = (y2 + y3) / FLOATNUM;
148 float x123 = (x12 + x23) / FLOATNUM;
149 float y123 = (y12 + y23) / FLOATNUM;
150 float deltaX = x3 - x1;
151 float deltaY = y3 - y1;
152 float distance = MATH_ABS(((x2 - x3) * deltaY - (y2 - y3) * deltaX));
153 float da;
154 if (distance > CURVE_COLLINEARITY_EPSILON) {
155 if (distance * distance <= distanceToleranceSquare_ * (deltaX * deltaX + deltaY * deltaY)) {
156 // If The Curvature Does Not Exceed The Distance Tolerance Value
157 if (angleTolerance_ < CURVE_ANGLE_TO_LERANCE_EPSILON) {
158 points_.PushBack(PointF(x123, y123));
159 return;
160 }
161
162 da = MATH_ABS(FastAtan2F(y3 - y2, x3 - x2) - FastAtan2F(y2 - y1, x2 - x1));
163 if (da >= PI) {
164 da = TWO_TIMES * PI - da;
165 }
166
167 if (da < angleTolerance_) {
168 points_.PushBack(PointF(x123, y123));
169 return;
170 }
171 }
172 } else {
173 da = deltaX * deltaX + deltaY * deltaY;
174 if (da == 0) {
175 distance = CalcSqDistance(x1, y1, x2, y2);
176 } else {
177 distance = ((x2 - x1) * deltaX + (y2 - y1) * deltaY) / da;
178 if (distance > 0 && distance < 1) {
179 // Simple Collinear Case，1---2---3
180 // We Can Leave Only Two Endpoints
181 return;
182 }
183 if (distance <= 0) {
184 distance = CalcSqDistance(x2, y2, x1, y1);
185 } else if (distance >= 1) {
186 distance = CalcSqDistance(x2, y2, x3, y3);
187 } else {
188 distance = CalcSqDistance(x2, y2, x1 + distance * deltaX, y1 + distance * deltaY);
189 }
190 }
191 if (distance < distanceToleranceSquare_) {
192 points_.PushBack(PointF(x2, y2));
193 return;
194 }
195 }
196
197 // Continue Subdivision
198 Recursive(x1, y1, x12, y12, x123, y123, level + 1);
199 Recursive(x123, y123, x23, y23, x3, y3, level + 1);
200 }
201
Bezier(float x1,float y1,float x2,float y2,float x3,float y3)202 void QuadrBezierCurveDividOp::Bezier(float x1, float y1,
203 float x2, float y2,
204 float x3, float y3)
205 {
206 points_.PushBack(PointF(x1, y1));
207 Recursive(x1, y1, x2, y2, x3, y3, 0);
208 points_.PushBack(PointF(x3, y3));
209 }
210
ApproximationScale(float scale)211 void CubicBezierCurveIncrement::ApproximationScale(float scale)
212 {
213 approximationScale_ = scale;
214 }
215
ApproximationScale() const216 float CubicBezierCurveIncrement::ApproximationScale() const
217 {
218 return approximationScale_;
219 }
220
Init(float x1,float y1,float x2,float y2,float x3,float y3,float x4,float y4)221 void CubicBezierCurveIncrement::Init(float x1, float y1,
222 float x2, float y2,
223 float x3, float y3,
224 float x4, float y4)
225 {
226 startCoordinate_.x = x1;
227 startCoordinate_.y = y1;
228 endCoordinate_.x = x4;
229 endCoordinate_.y = y4;
230
231 float deltaX1 = x2 - x1;
232 float deltaY1 = y2 - y1;
233 float deltaX2 = x3 - x2;
234 float deltaY2 = y3 - y2;
235 float deltaX3 = x4 - x3;
236 float deltaY3 = y4 - y3;
237
238 float len = (Sqrt(deltaX1 * deltaX1 + deltaY1 * deltaY1) +
239 Sqrt(deltaX2 * deltaX2 + deltaY2 * deltaY2) +
240 Sqrt(deltaX3 * deltaX3 + deltaY3 * deltaY3)) *
241 CURVES_NUM_STEP_LEN * approximationScale_;
242
243 numberSteps_ = MATH_UROUND(len);
244 const int32_t cuvereNumStep = 4;
245 if (numberSteps_ < cuvereNumStep) {
246 numberSteps_ = cuvereNumStep;
247 }
248 if (numberSteps_ == 0) {
249 return;
250 }
251 float subdivideStep = 1.0f / numberSteps_;
252 float subdivideStep2 = subdivideStep * subdivideStep;
253 float subdivideStep3 = subdivideStep * subdivideStep * subdivideStep;
254 const float prelMin = 3.0f;
255 const float prelMax = 6.0f;
256
257 float pre1 = prelMin * subdivideStep;
258 float pre2 = prelMin * subdivideStep2;
259 float pre4 = prelMax * subdivideStep2;
260 float pre5 = prelMax * subdivideStep3;
261
262 float tmp1X = x1 - x2 * FLOATNUM + x3;
263 float tmp1Y = y1 - y2 * FLOATNUM + y3;
264
265 float tmp2X = (x2 - x3) * prelMin - x1 + x4;
266 float tmp2Y = (y2 - y3) * prelMin - y1 + y4;
267
268 savedFinalCoordinate_.x = x1;
269 finalCoordinate_.x = x1;
270 savedFinalCoordinate_.y = y1;
271 finalCoordinate_.y = y1;
272
273 savedDeltaFinalCoordinate_.x = (x2 - x1) * pre1 + tmp1X * pre2 + tmp2X * subdivideStep3;
274 deltaFinalCoordinate_.x = (x2 - x1) * pre1 + tmp1X * pre2 + tmp2X * subdivideStep3;
275 savedDeltaFinalCoordinate_.y = (y2 - y1) * pre1 + tmp1Y * pre2 + tmp2Y * subdivideStep3;
276 deltaFinalCoordinate_.y = (y2 - y1) * pre1 + tmp1Y * pre2 + tmp2Y * subdivideStep3;
277
278 savedCopyDeltaFinalCoordinate_.x = tmp1X * pre4 + tmp2X * pre5;
279 copyDeltaFinalCoordinate_.x = tmp1X * pre4 + tmp2X * pre5;
280 savedCopyDeltaFinalCoordinate_.y = tmp1Y * pre4 + tmp2Y * pre5;
281 copyDeltaFinalCoordinate_.y = tmp1Y * pre4 + tmp2Y * pre5;
282
283 repeatCopyDeltaFinalCoordinate_.x = tmp2X * pre5;
284 repeatCopyDeltaFinalCoordinate_.y = tmp2Y * pre5;
285
286 currentStep_ = numberSteps_;
287 }
288
Rewind(uint32_t)289 void CubicBezierCurveIncrement::Rewind(uint32_t)
290 {
291 if (numberSteps_ == 0) {
292 currentStep_ = -1;
293 return;
294 }
295
296 currentStep_ = numberSteps_;
297 finalCoordinate_.x = savedFinalCoordinate_.x;
298 finalCoordinate_.y = savedFinalCoordinate_.y;
299 deltaFinalCoordinate_.x = savedDeltaFinalCoordinate_.x;
300 deltaFinalCoordinate_.y = savedDeltaFinalCoordinate_.y;
301 copyDeltaFinalCoordinate_.x = savedCopyDeltaFinalCoordinate_.x;
302 copyDeltaFinalCoordinate_.y = savedCopyDeltaFinalCoordinate_.y;
303 }
304
GenerateVertex(float * x,float * y)305 uint32_t CubicBezierCurveIncrement::GenerateVertex(float* x, float* y)
306 {
307 if (currentStep_ < 0) {
308 return PATH_CMD_STOP;
309 }
310 if (currentStep_ == numberSteps_) {
311 *x = startCoordinate_.x;
312 *y = startCoordinate_.y;
313 --currentStep_;
314 return PATH_CMD_MOVE_TO;
315 }
316
317 if (currentStep_ == 0) {
318 *x = endCoordinate_.x;
319 *y = endCoordinate_.y;
320 --currentStep_;
321 return PATH_CMD_LINE_TO;
322 }
323
324 finalCoordinate_.x += deltaFinalCoordinate_.x;
325 finalCoordinate_.y += deltaFinalCoordinate_.y;
326 deltaFinalCoordinate_.x += copyDeltaFinalCoordinate_.x;
327 deltaFinalCoordinate_.y += copyDeltaFinalCoordinate_.y;
328 copyDeltaFinalCoordinate_.x += repeatCopyDeltaFinalCoordinate_.x;
329 copyDeltaFinalCoordinate_.y += repeatCopyDeltaFinalCoordinate_.y;
330
331 *x = finalCoordinate_.x;
332 *y = finalCoordinate_.y;
333 --currentStep_;
334 return PATH_CMD_LINE_TO;
335 }
336
Init(float x1,float y1,float x2,float y2,float x3,float y3,float x4,float y4)337 void CubicBezierCurveDividOperate::Init(float x1, float y1,
338 float x2, float y2,
339 float x3, float y3,
340 float x4, float y4)
341 {
342 points_.Clear();
343 distanceToleranceSquare_ = HALFNUM / approximationScale_;
344 distanceToleranceSquare_ *= distanceToleranceSquare_;
345 Bezier(x1, y1, x2, y2, x3, y3, x4, y4);
346 count_ = 0;
347 }
348
Recursive(float x1,float y1,float x2,float y2,float x3,float y3,float x4,float y4,uint32_t level)349 void CubicBezierCurveDividOperate::Recursive(float x1, float y1,
350 float x2, float y2,
351 float x3, float y3,
352 float x4, float y4,
353 uint32_t level)
354 {
355 if (level > CURVE_RECURSION_LIMIT) {
356 return;
357 }
358
359 /** Calculates All Midpoints Of a Segment */
360 float x12 = (x1 + x2) / FLOATNUM;
361 float y12 = (y1 + y2) / FLOATNUM;
362 float x23 = (x2 + x3) / FLOATNUM;
363 float y23 = (y2 + y3) / FLOATNUM;
364 float x34 = (x3 + x4) / FLOATNUM;
365 float y34 = (y3 + y4) / FLOATNUM;
366 float x123 = (x12 + x23) / FLOATNUM;
367 float y123 = (y12 + y23) / FLOATNUM;
368 float x234 = (x23 + x34) / FLOATNUM;
369 float y234 = (y23 + y34) / FLOATNUM;
370 float x1234 = (x123 + x234) / FLOATNUM;
371 float y1234 = (y123 + y234) / FLOATNUM;
372 /** Try to Approximate the Entire Cubic Curve With a Straight Line */
373 float delta41X = x4 - x1;
374 float delta41Y = y4 - y1;
375 float delta2 = MATH_ABS(((x2 - x4) * delta41Y - (y2 - y4) * delta41X));
376 float delta3 = MATH_ABS(((x3 - x4) * delta41Y - (y3 - y4) * delta41X));
377 float dxTemp;
378 float dyTemp;
379 float delta41;
380
381 bool isEnabled = true;
382 switch ((int32_t(delta2 > CURVE_COLLINEARITY_EPSILON) << 1) + int32_t(delta3 > CURVE_COLLINEARITY_EPSILON)) {
383 case COLLINEAR:
384 /** All are Collinear or p1 == p4 */
385 delta41 = delta41X * delta41X + delta41Y * delta41Y;
386 if (delta41 == 0) {
387 delta2 = CalcSqDistance(x1, y1, x2, y2);
388 delta3 = CalcSqDistance(x4, y4, x3, y3);
389 } else {
390 delta41 = 1 / delta41;
391 dxTemp = x2 - x1;
392 dyTemp = y2 - y1;
393 delta2 = delta41 * (dxTemp * delta41X + dyTemp * delta41Y);
394 dxTemp = x3 - x1;
395 dyTemp = y3 - y1;
396 delta3 = delta41 * (dxTemp * delta41X + dyTemp * delta41Y);
397 if (delta2 > 0 && delta2 < 1 && delta3 > 0 && delta3 < 1) {
398 /** Simple Collinear Case，1--2--3--4 */
399 /** We Can Leave Only Two Endpoints */
400 return;
401 }
402
403 if (delta2 <= 0) {
404 delta2 = CalcSqDistance(x2, y2, x1, y1);
405 } else if (delta2 >= 1) {
406 delta2 = CalcSqDistance(x2, y2, x4, y4);
407 } else {
408 delta2 = CalcSqDistance(x2, y2, x1 + delta2 * delta41X, y1 + delta2 * delta41Y);
409 }
410 if (delta3 <= 0) {
411 delta3 = CalcSqDistance(x3, y3, x1, y1);
412 } else if (delta3 >= 1) {
413 delta3 = CalcSqDistance(x3, y3, x4, y4);
414 } else {
415 delta3 = CalcSqDistance(x3, y3, x1 + delta3 * delta41X, y1 + delta3 * delta41Y);
416 }
417 }
418
419 if (delta2 > delta3) {
420 if (delta2 < distanceToleranceSquare_) {
421 points_.PushBack(PointF(x2, y2));
422 isEnabled = false;
423 }
424 } else {
425 if (delta3 < distanceToleranceSquare_) {
426 points_.PushBack(PointF(x3, y3));
427 isEnabled = false;
428 }
429 }
430 break;
431 case COLLINEAR1:
432 /** p1、p2、p4 is Collinear */
433 if (delta3 * delta3 <= distanceToleranceSquare_ * (delta41X * delta41X + delta41Y * delta41Y)) {
434 if (angleTolerance_ < CURVE_ANGLE_TO_LERANCE_EPSILON) {
435 points_.PushBack(PointF(x23, y23));
436 isEnabled = false;
437 }
438 if (isEnabled) {
439 dxTemp = MATH_ABS(FastAtan2F(y4 - y3, x4 - x3) - FastAtan2F(y3 - y2, x3 - x2));
440 if (dxTemp >= PI) {
441 dxTemp = FLOATNUM * PI - dxTemp;
442 }
443 if (dxTemp < angleTolerance_) {
444 points_.PushBack(PointF(x2, y2));
445 points_.PushBack(PointF(x3, y3));
446 isEnabled = false;
447 }
448 if (isEnabled && cuspLimit_ != 0.0f && dxTemp > cuspLimit_) {
449 points_.PushBack(PointF(x3, y3));
450 isEnabled = false;
451 }
452 }
453 }
454 break;
455 case COLLINEAR2:
456 /** p1、p3、p4 is Collinear. */
457 if (delta2 * delta2 <= distanceToleranceSquare_ * (delta41X * delta41X + delta41Y * delta41Y)) {
458 if (angleTolerance_ < CURVE_ANGLE_TO_LERANCE_EPSILON) {
459 points_.PushBack(PointF(x23, y23));
460 isEnabled = false;
461 }
462 if (isEnabled) {
463 dxTemp = MATH_ABS(FastAtan2F(y3 - y2, x3 - x2) - FastAtan2F(y2 - y1, x2 - x1));
464 if (dxTemp >= PI) {
465 dxTemp = FLOATNUM * PI - dxTemp;
466 }
467 if (dxTemp < angleTolerance_) {
468 points_.PushBack(PointF(x2, y2));
469 points_.PushBack(PointF(x3, y3));
470 isEnabled = false;
471 }
472 if (isEnabled && cuspLimit_ != 0.0f && dxTemp > cuspLimit_) {
473 points_.PushBack(PointF(x2, y2));
474 isEnabled = false;
475 }
476 }
477 }
478 break;
479 case COLLINEAR3:
480 if ((delta2 + delta3) * (delta2 + delta3) <=
481 distanceToleranceSquare_ * (delta41X * delta41X + delta41Y * delta41Y)) {
482 if (angleTolerance_ < CURVE_ANGLE_TO_LERANCE_EPSILON) {
483 points_.PushBack(PointF(x23, y23));
484 isEnabled = false;
485 }
486 delta41 = FastAtan2F(y3 - y2, x3 - x2);
487 dxTemp = MATH_ABS(delta41 - FastAtan2F(y2 - y1, x2 - x1));
488 dyTemp = MATH_ABS(FastAtan2F(y4 - y3, x4 - x3) - delta41);
489 if (dxTemp >= PI) {
490 dxTemp = FLOATNUM * PI - dxTemp;
491 }
492 if (dyTemp >= PI) {
493 dyTemp = FLOATNUM * PI - dyTemp;
494 }
495 if (isEnabled) {
496 if (dxTemp + dyTemp < angleTolerance_) {
497 points_.PushBack(PointF(x23, y23));
498 isEnabled = false;
499 }
500 if (isEnabled && cuspLimit_ != 0.0f && dxTemp > cuspLimit_) {
501 points_.PushBack(PointF(x2, y2));
502 isEnabled = false;
503 }
504 if (isEnabled && cuspLimit_ != 0.0f && dyTemp > cuspLimit_) {
505 points_.PushBack(PointF(x3, y3));
506 isEnabled = false;
507 }
508 }
509 }
510 break;
511 }
512 if (!isEnabled) {
513 return;
514 }
515 Recursive(x1, y1, x12, y12, x123, y123, x1234, y1234, level + 1);
516 Recursive(x1234, y1234, x234, y234, x34, y34, x4, y4, level + 1);
517 }
518
Bezier(float x1,float y1,float x2,float y2,float x3,float y3,float x4,float y4)519 void CubicBezierCurveDividOperate::Bezier(float x1, float y1,
520 float x2, float y2,
521 float x3, float y3,
522 float x4, float y4)
523 {
524 points_.PushBack(PointF(x1, y1));
525 Recursive(x1, y1, x2, y2, x3, y3, x4, y4, 0);
526 points_.PushBack(PointF(x4, y4));
527 }
528 } // namespace OHOS
529