Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
godotengine
GitHub Repository: godotengine/godot
 Path: blob/master/thirdparty/msdfgen/core/edge-segments.cpp
9903 views
1


2
#include "edge-segments.h"

3


4
#include "arithmetics.hpp"

5
#include "equation-solver.h"

6


7
namespace msdfgen {

8


9
EdgeSegment *EdgeSegment::create(Point2 p0, Point2 p1, EdgeColor edgeColor) {

10
    return new LinearSegment(p0, p1, edgeColor);

11
}

12


13
EdgeSegment *EdgeSegment::create(Point2 p0, Point2 p1, Point2 p2, EdgeColor edgeColor) {

14
    if (!crossProduct(p1-p0, p2-p1))

15
        return new LinearSegment(p0, p2, edgeColor);

16
    return new QuadraticSegment(p0, p1, p2, edgeColor);

17
}

18


19
EdgeSegment *EdgeSegment::create(Point2 p0, Point2 p1, Point2 p2, Point2 p3, EdgeColor edgeColor) {

20
    Vector2 p12 = p2-p1;

21
    if (!crossProduct(p1-p0, p12) && !crossProduct(p12, p3-p2))

22
        return new LinearSegment(p0, p3, edgeColor);

23
    if ((p12 = 1.5*p1-.5*p0) == 1.5*p2-.5*p3)

24
        return new QuadraticSegment(p0, p12, p3, edgeColor);

25
    return new CubicSegment(p0, p1, p2, p3, edgeColor);

26
}

27


28
void EdgeSegment::distanceToPerpendicularDistance(SignedDistance &distance, Point2 origin, double param) const {

29
    if (param < 0) {

30
        Vector2 dir = direction(0).normalize();

31
        Vector2 aq = origin-point(0);

32
        double ts = dotProduct(aq, dir);

33
        if (ts < 0) {

34
            double perpendicularDistance = crossProduct(aq, dir);

35
            if (fabs(perpendicularDistance) <= fabs(distance.distance)) {

36
                distance.distance = perpendicularDistance;

37
                distance.dot = 0;

38
            }

39
        }

40
    } else if (param > 1) {

41
        Vector2 dir = direction(1).normalize();

42
        Vector2 bq = origin-point(1);

43
        double ts = dotProduct(bq, dir);

44
        if (ts > 0) {

45
            double perpendicularDistance = crossProduct(bq, dir);

46
            if (fabs(perpendicularDistance) <= fabs(distance.distance)) {

47
                distance.distance = perpendicularDistance;

48
                distance.dot = 0;

49
            }

50
        }

51
    }

52
}

53


54
LinearSegment::LinearSegment(Point2 p0, Point2 p1, EdgeColor edgeColor) : EdgeSegment(edgeColor) {

55
    p[0] = p0;

56
    p[1] = p1;

57
}

58


59
QuadraticSegment::QuadraticSegment(Point2 p0, Point2 p1, Point2 p2, EdgeColor edgeColor) : EdgeSegment(edgeColor) {

60
    p[0] = p0;

61
    p[1] = p1;

62
    p[2] = p2;

63
}

64


65
CubicSegment::CubicSegment(Point2 p0, Point2 p1, Point2 p2, Point2 p3, EdgeColor edgeColor) : EdgeSegment(edgeColor) {

66
    p[0] = p0;

67
    p[1] = p1;

68
    p[2] = p2;

69
    p[3] = p3;

70
}

71


72
LinearSegment *LinearSegment::clone() const {

73
    return new LinearSegment(p[0], p[1], color);

74
}

75


76
QuadraticSegment *QuadraticSegment::clone() const {

77
    return new QuadraticSegment(p[0], p[1], p[2], color);

78
}

79


80
CubicSegment *CubicSegment::clone() const {

81
    return new CubicSegment(p[0], p[1], p[2], p[3], color);

82
}

83


84
int LinearSegment::type() const {

85
    return (int) EDGE_TYPE;

86
}

87


88
int QuadraticSegment::type() const {

89
    return (int) EDGE_TYPE;

90
}

91


92
int CubicSegment::type() const {

93
    return (int) EDGE_TYPE;

94
}

95


96
const Point2 *LinearSegment::controlPoints() const {

97
    return p;

98
}

99


100
const Point2 *QuadraticSegment::controlPoints() const {

101
    return p;

102
}

103


104
const Point2 *CubicSegment::controlPoints() const {

105
    return p;

106
}

107


108
Point2 LinearSegment::point(double param) const {

109
    return mix(p[0], p[1], param);

110
}

111


112
Point2 QuadraticSegment::point(double param) const {

113
    return mix(mix(p[0], p[1], param), mix(p[1], p[2], param), param);

114
}

115


116
Point2 CubicSegment::point(double param) const {

117
    Vector2 p12 = mix(p[1], p[2], param);

118
    return mix(mix(mix(p[0], p[1], param), p12, param), mix(p12, mix(p[2], p[3], param), param), param);

119
}

120


121
Vector2 LinearSegment::direction(double param) const {

122
    return p[1]-p[0];

123
}

124


125
Vector2 QuadraticSegment::direction(double param) const {

126
    Vector2 tangent = mix(p[1]-p[0], p[2]-p[1], param);

127
    if (!tangent)

128
        return p[2]-p[0];

129
    return tangent;

130
}

131


132
Vector2 CubicSegment::direction(double param) const {

133
    Vector2 tangent = mix(mix(p[1]-p[0], p[2]-p[1], param), mix(p[2]-p[1], p[3]-p[2], param), param);

134
    if (!tangent) {

135
        if (param == 0) return p[2]-p[0];

136
        if (param == 1) return p[3]-p[1];

137
    }

138
    return tangent;

139
}

140


141
Vector2 LinearSegment::directionChange(double param) const {

142
    return Vector2();

143
}

144


145
Vector2 QuadraticSegment::directionChange(double param) const {

146
    return (p[2]-p[1])-(p[1]-p[0]);

147
}

148


149
Vector2 CubicSegment::directionChange(double param) const {

150
    return mix((p[2]-p[1])-(p[1]-p[0]), (p[3]-p[2])-(p[2]-p[1]), param);

151
}

152


153
double LinearSegment::length() const {

154
    return (p[1]-p[0]).length();

155
}

156


157
double QuadraticSegment::length() const {

158
    Vector2 ab = p[1]-p[0];

159
    Vector2 br = p[2]-p[1]-ab;

160
    double abab = dotProduct(ab, ab);

161
    double abbr = dotProduct(ab, br);

162
    double brbr = dotProduct(br, br);

163
    double abLen = sqrt(abab);

164
    double brLen = sqrt(brbr);

165
    double crs = crossProduct(ab, br);

166
    double h = sqrt(abab+abbr+abbr+brbr);

167
    return (

168
        brLen*((abbr+brbr)*h-abbr*abLen)+

169
        crs*crs*log((brLen*h+abbr+brbr)/(brLen*abLen+abbr))

170
    )/(brbr*brLen);

171
}

172


173
SignedDistance LinearSegment::signedDistance(Point2 origin, double &param) const {

174
    Vector2 aq = origin-p[0];

175
    Vector2 ab = p[1]-p[0];

176
    param = dotProduct(aq, ab)/dotProduct(ab, ab);

177
    Vector2 eq = p[param > .5]-origin;

178
    double endpointDistance = eq.length();

179
    if (param > 0 && param < 1) {

180
        double orthoDistance = dotProduct(ab.getOrthonormal(false), aq);

181
        if (fabs(orthoDistance) < endpointDistance)

182
            return SignedDistance(orthoDistance, 0);

183
    }

184
    return SignedDistance(nonZeroSign(crossProduct(aq, ab))*endpointDistance, fabs(dotProduct(ab.normalize(), eq.normalize())));

185
}

186


187
SignedDistance QuadraticSegment::signedDistance(Point2 origin, double &param) const {

188
    Vector2 qa = p[0]-origin;

189
    Vector2 ab = p[1]-p[0];

190
    Vector2 br = p[2]-p[1]-ab;

191
    double a = dotProduct(br, br);

192
    double b = 3*dotProduct(ab, br);

193
    double c = 2*dotProduct(ab, ab)+dotProduct(qa, br);

194
    double d = dotProduct(qa, ab);

195
    double t[3];

196
    int solutions = solveCubic(t, a, b, c, d);

197


198
    Vector2 epDir = direction(0);

199
    double minDistance = nonZeroSign(crossProduct(epDir, qa))*qa.length(); // distance from A

200
    param = -dotProduct(qa, epDir)/dotProduct(epDir, epDir);

201
    {

202
        epDir = direction(1);

203
        double distance = (p[2]-origin).length(); // distance from B

204
        if (distance < fabs(minDistance)) {

205
            minDistance = nonZeroSign(crossProduct(epDir, p[2]-origin))*distance;

206
            param = dotProduct(origin-p[1], epDir)/dotProduct(epDir, epDir);

207
        }

208
    }

209
    for (int i = 0; i < solutions; ++i) {

210
        if (t[i] > 0 && t[i] < 1) {

211
            Point2 qe = qa+2*t[i]*ab+t[i]*t[i]*br;

212
            double distance = qe.length();

213
            if (distance <= fabs(minDistance)) {

214
                minDistance = nonZeroSign(crossProduct(ab+t[i]*br, qe))*distance;

215
                param = t[i];

216
            }

217
        }

218
    }

219


220
    if (param >= 0 && param <= 1)

221
        return SignedDistance(minDistance, 0);

222
    if (param < .5)

223
        return SignedDistance(minDistance, fabs(dotProduct(direction(0).normalize(), qa.normalize())));

224
    else

225
        return SignedDistance(minDistance, fabs(dotProduct(direction(1).normalize(), (p[2]-origin).normalize())));

226
}

227


228
SignedDistance CubicSegment::signedDistance(Point2 origin, double &param) const {

229
    Vector2 qa = p[0]-origin;

230
    Vector2 ab = p[1]-p[0];

231
    Vector2 br = p[2]-p[1]-ab;

232
    Vector2 as = (p[3]-p[2])-(p[2]-p[1])-br;

233


234
    Vector2 epDir = direction(0);

235
    double minDistance = nonZeroSign(crossProduct(epDir, qa))*qa.length(); // distance from A

236
    param = -dotProduct(qa, epDir)/dotProduct(epDir, epDir);

237
    {

238
        epDir = direction(1);

239
        double distance = (p[3]-origin).length(); // distance from B

240
        if (distance < fabs(minDistance)) {

241
            minDistance = nonZeroSign(crossProduct(epDir, p[3]-origin))*distance;

242
            param = dotProduct(epDir-(p[3]-origin), epDir)/dotProduct(epDir, epDir);

243
        }

244
    }

245
    // Iterative minimum distance search

246
    for (int i = 0; i <= MSDFGEN_CUBIC_SEARCH_STARTS; ++i) {

247
        double t = (double) i/MSDFGEN_CUBIC_SEARCH_STARTS;

248
        Vector2 qe = qa+3*t*ab+3*t*t*br+t*t*t*as;

249
        for (int step = 0; step < MSDFGEN_CUBIC_SEARCH_STEPS; ++step) {

250
            // Improve t

251
            Vector2 d1 = 3*ab+6*t*br+3*t*t*as;

252
            Vector2 d2 = 6*br+6*t*as;

253
            t -= dotProduct(qe, d1)/(dotProduct(d1, d1)+dotProduct(qe, d2));

254
            if (t <= 0 || t >= 1)

255
                break;

256
            qe = qa+3*t*ab+3*t*t*br+t*t*t*as;

257
            double distance = qe.length();

258
            if (distance < fabs(minDistance)) {

259
                minDistance = nonZeroSign(crossProduct(d1, qe))*distance;

260
                param = t;

261
            }

262
        }

263
    }

264


265
    if (param >= 0 && param <= 1)

266
        return SignedDistance(minDistance, 0);

267
    if (param < .5)

268
        return SignedDistance(minDistance, fabs(dotProduct(direction(0).normalize(), qa.normalize())));

269
    else

270
        return SignedDistance(minDistance, fabs(dotProduct(direction(1).normalize(), (p[3]-origin).normalize())));

271
}

272


273
int LinearSegment::scanlineIntersections(double x[3], int dy[3], double y) const {

274
    if ((y >= p[0].y && y < p[1].y) || (y >= p[1].y && y < p[0].y)) {

275
        double param = (y-p[0].y)/(p[1].y-p[0].y);

276
        x[0] = mix(p[0].x, p[1].x, param);

277
        dy[0] = sign(p[1].y-p[0].y);

278
        return 1;

279
    }

280
    return 0;

281
}

282


283
int QuadraticSegment::scanlineIntersections(double x[3], int dy[3], double y) const {

284
    int total = 0;

285
    int nextDY = y > p[0].y ? 1 : -1;

286
    x[total] = p[0].x;

287
    if (p[0].y == y) {

288
        if (p[0].y < p[1].y || (p[0].y == p[1].y && p[0].y < p[2].y))

289
            dy[total++] = 1;

290
        else

291
            nextDY = 1;

292
    }

293
    {

294
        Vector2 ab = p[1]-p[0];

295
        Vector2 br = p[2]-p[1]-ab;

296
        double t[2];

297
        int solutions = solveQuadratic(t, br.y, 2*ab.y, p[0].y-y);

298
        // Sort solutions

299
        double tmp;

300
        if (solutions >= 2 && t[0] > t[1])

301
            tmp = t[0], t[0] = t[1], t[1] = tmp;

302
        for (int i = 0; i < solutions && total < 2; ++i) {

303
            if (t[i] >= 0 && t[i] <= 1) {

304
                x[total] = p[0].x+2*t[i]*ab.x+t[i]*t[i]*br.x;

305
                if (nextDY*(ab.y+t[i]*br.y) >= 0) {

306
                    dy[total++] = nextDY;

307
                    nextDY = -nextDY;

308
                }

309
            }

310
        }

311
    }

312
    if (p[2].y == y) {

313
        if (nextDY > 0 && total > 0) {

314
            --total;

315
            nextDY = -1;

316
        }

317
        if ((p[2].y < p[1].y || (p[2].y == p[1].y && p[2].y < p[0].y)) && total < 2) {

318
            x[total] = p[2].x;

319
            if (nextDY < 0) {

320
                dy[total++] = -1;

321
                nextDY = 1;

322
            }

323
        }

324
    }

325
    if (nextDY != (y >= p[2].y ? 1 : -1)) {

326
        if (total > 0)

327
            --total;

328
        else {

329
            if (fabs(p[2].y-y) < fabs(p[0].y-y))

330
                x[total] = p[2].x;

331
            dy[total++] = nextDY;

332
        }

333
    }

334
    return total;

335
}

336


337
int CubicSegment::scanlineIntersections(double x[3], int dy[3], double y) const {

338
    int total = 0;

339
    int nextDY = y > p[0].y ? 1 : -1;

340
    x[total] = p[0].x;

341
    if (p[0].y == y) {

342
        if (p[0].y < p[1].y || (p[0].y == p[1].y && (p[0].y < p[2].y || (p[0].y == p[2].y && p[0].y < p[3].y))))

343
            dy[total++] = 1;

344
        else

345
            nextDY = 1;

346
    }

347
    {

348
        Vector2 ab = p[1]-p[0];

349
        Vector2 br = p[2]-p[1]-ab;

350
        Vector2 as = (p[3]-p[2])-(p[2]-p[1])-br;

351
        double t[3];

352
        int solutions = solveCubic(t, as.y, 3*br.y, 3*ab.y, p[0].y-y);

353
        // Sort solutions

354
        double tmp;

355
        if (solutions >= 2) {

356
            if (t[0] > t[1])

357
                tmp = t[0], t[0] = t[1], t[1] = tmp;

358
            if (solutions >= 3 && t[1] > t[2]) {

359
                tmp = t[1], t[1] = t[2], t[2] = tmp;

360
                if (t[0] > t[1])

361
                    tmp = t[0], t[0] = t[1], t[1] = tmp;

362
            }

363
        }

364
        for (int i = 0; i < solutions && total < 3; ++i) {

365
            if (t[i] >= 0 && t[i] <= 1) {

366
                x[total] = p[0].x+3*t[i]*ab.x+3*t[i]*t[i]*br.x+t[i]*t[i]*t[i]*as.x;

367
                if (nextDY*(ab.y+2*t[i]*br.y+t[i]*t[i]*as.y) >= 0) {

368
                    dy[total++] = nextDY;

369
                    nextDY = -nextDY;

370
                }

371
            }

372
        }

373
    }

374
    if (p[3].y == y) {

375
        if (nextDY > 0 && total > 0) {

376
            --total;

377
            nextDY = -1;

378
        }

379
        if ((p[3].y < p[2].y || (p[3].y == p[2].y && (p[3].y < p[1].y || (p[3].y == p[1].y && p[3].y < p[0].y)))) && total < 3) {

380
            x[total] = p[3].x;

381
            if (nextDY < 0) {

382
                dy[total++] = -1;

383
                nextDY = 1;

384
            }

385
        }

386
    }

387
    if (nextDY != (y >= p[3].y ? 1 : -1)) {

388
        if (total > 0)

389
            --total;

390
        else {

391
            if (fabs(p[3].y-y) < fabs(p[0].y-y))

392
                x[total] = p[3].x;

393
            dy[total++] = nextDY;

394
        }

395
    }

396
    return total;

397
}

398


399
static void pointBounds(Point2 p, double &l, double &b, double &r, double &t) {

400
    if (p.x < l) l = p.x;

401
    if (p.y < b) b = p.y;

402
    if (p.x > r) r = p.x;

403
    if (p.y > t) t = p.y;

404
}

405


406
void LinearSegment::bound(double &l, double &b, double &r, double &t) const {

407
    pointBounds(p[0], l, b, r, t);

408
    pointBounds(p[1], l, b, r, t);

409
}

410


411
void QuadraticSegment::bound(double &l, double &b, double &r, double &t) const {

412
    pointBounds(p[0], l, b, r, t);

413
    pointBounds(p[2], l, b, r, t);

414
    Vector2 bot = (p[1]-p[0])-(p[2]-p[1]);

415
    if (bot.x) {

416
        double param = (p[1].x-p[0].x)/bot.x;

417
        if (param > 0 && param < 1)

418
            pointBounds(point(param), l, b, r, t);

419
    }

420
    if (bot.y) {

421
        double param = (p[1].y-p[0].y)/bot.y;

422
        if (param > 0 && param < 1)

423
            pointBounds(point(param), l, b, r, t);

424
    }

425
}

426


427
void CubicSegment::bound(double &l, double &b, double &r, double &t) const {

428
    pointBounds(p[0], l, b, r, t);

429
    pointBounds(p[3], l, b, r, t);

430
    Vector2 a0 = p[1]-p[0];

431
    Vector2 a1 = 2*(p[2]-p[1]-a0);

432
    Vector2 a2 = p[3]-3*p[2]+3*p[1]-p[0];

433
    double params[2];

434
    int solutions;

435
    solutions = solveQuadratic(params, a2.x, a1.x, a0.x);

436
    for (int i = 0; i < solutions; ++i)

437
        if (params[i] > 0 && params[i] < 1)

438
            pointBounds(point(params[i]), l, b, r, t);

439
    solutions = solveQuadratic(params, a2.y, a1.y, a0.y);

440
    for (int i = 0; i < solutions; ++i)

441
        if (params[i] > 0 && params[i] < 1)

442
            pointBounds(point(params[i]), l, b, r, t);

443
}

444


445
void LinearSegment::reverse() {

446
    Point2 tmp = p[0];

447
    p[0] = p[1];

448
    p[1] = tmp;

449
}

450


451
void QuadraticSegment::reverse() {

452
    Point2 tmp = p[0];

453
    p[0] = p[2];

454
    p[2] = tmp;

455
}

456


457
void CubicSegment::reverse() {

458
    Point2 tmp = p[0];

459
    p[0] = p[3];

460
    p[3] = tmp;

461
    tmp = p[1];

462
    p[1] = p[2];

463
    p[2] = tmp;

464
}

465


466
void LinearSegment::moveStartPoint(Point2 to) {

467
    p[0] = to;

468
}

469


470
void QuadraticSegment::moveStartPoint(Point2 to) {

471
    Vector2 origSDir = p[0]-p[1];

472
    Point2 origP1 = p[1];

473
    p[1] += crossProduct(p[0]-p[1], to-p[0])/crossProduct(p[0]-p[1], p[2]-p[1])*(p[2]-p[1]);

474
    p[0] = to;

475
    if (dotProduct(origSDir, p[0]-p[1]) < 0)

476
        p[1] = origP1;

477
}

478


479
void CubicSegment::moveStartPoint(Point2 to) {

480
    p[1] += to-p[0];

481
    p[0] = to;

482
}

483


484
void LinearSegment::moveEndPoint(Point2 to) {

485
    p[1] = to;

486
}

487


488
void QuadraticSegment::moveEndPoint(Point2 to) {

489
    Vector2 origEDir = p[2]-p[1];

490
    Point2 origP1 = p[1];

491
    p[1] += crossProduct(p[2]-p[1], to-p[2])/crossProduct(p[2]-p[1], p[0]-p[1])*(p[0]-p[1]);

492
    p[2] = to;

493
    if (dotProduct(origEDir, p[2]-p[1]) < 0)

494
        p[1] = origP1;

495
}

496


497
void CubicSegment::moveEndPoint(Point2 to) {

498
    p[2] += to-p[3];

499
    p[3] = to;

500
}

501


502
void LinearSegment::splitInThirds(EdgeSegment *&part0, EdgeSegment *&part1, EdgeSegment *&part2) const {

503
    part0 = new LinearSegment(p[0], point(1/3.), color);

504
    part1 = new LinearSegment(point(1/3.), point(2/3.), color);

505
    part2 = new LinearSegment(point(2/3.), p[1], color);

506
}

507


508
void QuadraticSegment::splitInThirds(EdgeSegment *&part0, EdgeSegment *&part1, EdgeSegment *&part2) const {

509
    part0 = new QuadraticSegment(p[0], mix(p[0], p[1], 1/3.), point(1/3.), color);

510
    part1 = new QuadraticSegment(point(1/3.), mix(mix(p[0], p[1], 5/9.), mix(p[1], p[2], 4/9.), .5), point(2/3.), color);

511
    part2 = new QuadraticSegment(point(2/3.), mix(p[1], p[2], 2/3.), p[2], color);

512
}

513


514
void CubicSegment::splitInThirds(EdgeSegment *&part0, EdgeSegment *&part1, EdgeSegment *&part2) const {

515
    part0 = new CubicSegment(p[0], p[0] == p[1] ? p[0] : mix(p[0], p[1], 1/3.), mix(mix(p[0], p[1], 1/3.), mix(p[1], p[2], 1/3.), 1/3.), point(1/3.), color);

516
    part1 = new CubicSegment(point(1/3.),

517
        mix(mix(mix(p[0], p[1], 1/3.), mix(p[1], p[2], 1/3.), 1/3.), mix(mix(p[1], p[2], 1/3.), mix(p[2], p[3], 1/3.), 1/3.), 2/3.),

518
        mix(mix(mix(p[0], p[1], 2/3.), mix(p[1], p[2], 2/3.), 2/3.), mix(mix(p[1], p[2], 2/3.), mix(p[2], p[3], 2/3.), 2/3.), 1/3.),

519
        point(2/3.), color);

520
    part2 = new CubicSegment(point(2/3.), mix(mix(p[1], p[2], 2/3.), mix(p[2], p[3], 2/3.), 2/3.), p[2] == p[3] ? p[3] : mix(p[2], p[3], 2/3.), p[3], color);

521
}

522


523
EdgeSegment *QuadraticSegment::convertToCubic() const {

524
    return new CubicSegment(p[0], mix(p[0], p[1], 2/3.), mix(p[1], p[2], 1/3.), p[2], color);

525
}

526


527
}

528


529