src/lib/tvgBezier.cpp

   1 /*
   2  * Copyright (c) 2020 - 2023 the ThorVG project. All rights reserved.
   3
   4  * Permission is hereby granted, free of charge, to any person obtaining a copy
   5  * of this software and associated documentation files (the "Software"), to deal
   6  * in the Software without restriction, including without limitation the rights
   7  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   8  * copies of the Software, and to permit persons to whom the Software is
   9  * furnished to do so, subject to the following conditions:
  10
  11  * The above copyright notice and this permission notice shall be included in all
  12  * copies or substantial portions of the Software.
  13
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  20  * SOFTWARE.
  21  */
  22
  23 #include <float.h>
  24 #include <math.h>
  25 #include "tvgBezier.h"
  26
  27 /************************************************************************/
  28 /* Internal Class Implementation                                        */
  29 /************************************************************************/
  30
  31 static float _lineLength(const Point& pt1, const Point& pt2)
  32 {
  33     /* approximate sqrt(x*x + y*y) using alpha max plus beta min algorithm.
  34        With alpha = 1, beta = 3/8, giving results with the largest error less
  35        than 7% compared to the exact value. */
  36     Point diff = {pt2.x - pt1.x, pt2.y - pt1.y};
  37     if (diff.x < 0) diff.x = -diff.x;
  38     if (diff.y < 0) diff.y = -diff.y;
  39     return (diff.x > diff.y) ? (diff.x + diff.y * 0.375f) : (diff.y + diff.x * 0.375f);
  40 }
  41
  42
  43 /************************************************************************/
  44 /* External Class Implementation                                        */
  45 /************************************************************************/
  46
  47 namespace tvg
  48 {
  49
  50 void bezSplit(const Bezier&cur, Bezier& left, Bezier& right)
  51 {
  52     auto c = (cur.ctrl1.x + cur.ctrl2.x) * 0.5f;
  53     left.ctrl1.x = (cur.start.x + cur.ctrl1.x) * 0.5f;
  54     right.ctrl2.x = (cur.ctrl2.x + cur.end.x) * 0.5f;
  55     left.start.x = cur.start.x;
  56     right.end.x = cur.end.x;
  57     left.ctrl2.x = (left.ctrl1.x + c) * 0.5f;
  58     right.ctrl1.x = (right.ctrl2.x + c) * 0.5f;
  59     left.end.x = right.start.x = (left.ctrl2.x + right.ctrl1.x) * 0.5f;
  60
  61     c = (cur.ctrl1.y + cur.ctrl2.y) * 0.5f;
  62     left.ctrl1.y = (cur.start.y + cur.ctrl1.y) * 0.5f;
  63     right.ctrl2.y = (cur.ctrl2.y + cur.end.y) * 0.5f;
  64     left.start.y = cur.start.y;
  65     right.end.y = cur.end.y;
  66     left.ctrl2.y = (left.ctrl1.y + c) * 0.5f;
  67     right.ctrl1.y = (right.ctrl2.y + c) * 0.5f;
  68     left.end.y = right.start.y = (left.ctrl2.y + right.ctrl1.y) * 0.5f;
  69 }
  70
  71
  72 float bezLength(const Bezier& cur)
  73 {
  74     Bezier left, right;
  75     auto len = _lineLength(cur.start, cur.ctrl1) + _lineLength(cur.ctrl1, cur.ctrl2) + _lineLength(cur.ctrl2, cur.end);
  76     auto chord = _lineLength(cur.start, cur.end);
  77
  78     if (fabsf(len - chord) > BEZIER_EPSILON) {
  79         bezSplit(cur, left, right);
  80         return bezLength(left) + bezLength(right);
  81     }
  82     return len;
  83 }
  84
  85
  86 void bezSplitLeft(Bezier& cur, float at, Bezier& left)
  87 {
  88     left.start = cur.start;
  89
  90     left.ctrl1.x = cur.start.x + at * (cur.ctrl1.x - cur.start.x);
  91     left.ctrl1.y = cur.start.y + at * (cur.ctrl1.y - cur.start.y);
  92
  93     left.ctrl2.x = cur.ctrl1.x + at * (cur.ctrl2.x - cur.ctrl1.x); //temporary holding spot
  94     left.ctrl2.y = cur.ctrl1.y + at * (cur.ctrl2.y - cur.ctrl1.y); //temporary holding spot
  95
  96     cur.ctrl2.x = cur.ctrl2.x + at * (cur.end.x - cur.ctrl2.x);
  97     cur.ctrl2.y = cur.ctrl2.y + at * (cur.end.y - cur.ctrl2.y);
  98
  99     cur.ctrl1.x = left.ctrl2.x + at * (cur.ctrl2.x - left.ctrl2.x);
 100     cur.ctrl1.y = left.ctrl2.y + at * (cur.ctrl2.y - left.ctrl2.y);
 101
 102     left.ctrl2.x = left.ctrl1.x + at * (left.ctrl2.x - left.ctrl1.x);
 103     left.ctrl2.y = left.ctrl1.y + at * (left.ctrl2.y - left.ctrl1.y);
 104
 105     left.end.x = cur.start.x = left.ctrl2.x + at * (cur.ctrl1.x - left.ctrl2.x);
 106     left.end.y = cur.start.y = left.ctrl2.y + at * (cur.ctrl1.y - left.ctrl2.y);
 107 }
 108
 109
 110 float bezAt(const Bezier& bz, float at)
 111 {
 112     auto len = bezLength(bz);
 113     auto biggest = 1.0f;
 114     auto smallest = 0.0f;
 115     auto t = 0.5f;
 116
 117     //just in case to prevent an infinite loop
 118     if (at <= 0) return 0.0f;
 119
 120     if (at >= len) return 1.0f;
 121
 122     while (true) {
 123         auto right = bz;
 124         Bezier left;
 125         bezSplitLeft(right, t, left);
 126         len = bezLength(left);
 127
 128         if (fabsf(len - at) < BEZIER_EPSILON || fabsf(smallest - biggest) < BEZIER_EPSILON) {
 129             break;
 130         }
 131
 132         if (len < at) {
 133             smallest = t;
 134             t = (t + biggest) * 0.5f;
 135         } else {
 136             biggest = t;
 137             t = (smallest + t) * 0.5f;
 138         }
 139     }
 140     return t;
 141 }
 142
 143
 144 void bezSplitAt(const Bezier& cur, float at, Bezier& left, Bezier& right)
 145 {
 146     right = cur;
 147     auto t = bezAt(right, at);
 148     bezSplitLeft(right, t, left);
 149 }
 150
 151 }