Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
godotengine
GitHub Repository: godotengine/godot
 Path: blob/master/thirdparty/msdfgen/core/edge-segments.cpp
21334 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
        double distance = (p[2]-origin).length(); // distance from B

203
        if (distance < fabs(minDistance)) {

204
            epDir = direction(1);

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
        double distance = (p[3]-origin).length(); // distance from B

239
        if (distance < fabs(minDistance)) {

240
            epDir = direction(1);

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 = 1./MSDFGEN_CUBIC_SEARCH_STARTS*i;

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

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

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

251
        double improvedT = t-dotProduct(qe, d1)/(dotProduct(d1, d1)+dotProduct(qe, d2));

252
        if (improvedT > 0 && improvedT < 1) {

253
            int remainingSteps = MSDFGEN_CUBIC_SEARCH_STEPS;

254
            do {

255
                t = improvedT;

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

257
                d1 = 3*ab+6*t*br+3*t*t*as;

258
                if (!--remainingSteps)

259
                    break;

260
                d2 = 6*br+6*t*as;

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

262
            } while (improvedT > 0 && improvedT < 1);

263
            double distance = qe.length();

264
            if (distance < fabs(minDistance)) {

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

266
                param = t;

267
            }

268
        }

269
    }

270


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

272
        return SignedDistance(minDistance, 0);

273
    if (param < .5)

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

275
    else

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

277
}

278


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

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

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

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

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

284
        return 1;

285
    }

286
    return 0;

287
}

288


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

290
    int total = 0;

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

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

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

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

295
            dy[total++] = 1;

296
        else

297
            nextDY = 1;

298
    }

299
    {

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

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

302
        double t[2];

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

304
        // Sort solutions

305
        double tmp;

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

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

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

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

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

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

312
                    dy[total++] = nextDY;

313
                    nextDY = -nextDY;

314
                }

315
            }

316
        }

317
    }

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

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

320
            --total;

321
            nextDY = -1;

322
        }

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

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

325
            if (nextDY < 0) {

326
                dy[total++] = -1;

327
                nextDY = 1;

328
            }

329
        }

330
    }

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

332
        if (total > 0)

333
            --total;

334
        else {

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

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

337
            dy[total++] = nextDY;

338
        }

339
    }

340
    return total;

341
}

342


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

344
    int total = 0;

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

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

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

348
        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))))

349
            dy[total++] = 1;

350
        else

351
            nextDY = 1;

352
    }

353
    {

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

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

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

357
        double t[3];

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

359
        // Sort solutions

360
        double tmp;

361
        if (solutions >= 2) {

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

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

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

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

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

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

368
            }

369
        }

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

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

372
                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;

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

374
                    dy[total++] = nextDY;

375
                    nextDY = -nextDY;

376
                }

377
            }

378
        }

379
    }

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

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

382
            --total;

383
            nextDY = -1;

384
        }

385
        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) {

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

387
            if (nextDY < 0) {

388
                dy[total++] = -1;

389
                nextDY = 1;

390
            }

391
        }

392
    }

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

394
        if (total > 0)

395
            --total;

396
        else {

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

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

399
            dy[total++] = nextDY;

400
        }

401
    }

402
    return total;

403
}

404


405
static void pointBounds(Point2 p, double &xMin, double &yMin, double &xMax, double &yMax) {

406
    if (p.x < xMin) xMin = p.x;

407
    if (p.y < yMin) yMin = p.y;

408
    if (p.x > xMax) xMax = p.x;

409
    if (p.y > yMax) yMax = p.y;

410
}

411


412
void LinearSegment::bound(double &xMin, double &yMin, double &xMax, double &yMax) const {

413
    pointBounds(p[0], xMin, yMin, xMax, yMax);

414
    pointBounds(p[1], xMin, yMin, xMax, yMax);

415
}

416


417
void QuadraticSegment::bound(double &xMin, double &yMin, double &xMax, double &yMax) const {

418
    pointBounds(p[0], xMin, yMin, xMax, yMax);

419
    pointBounds(p[2], xMin, yMin, xMax, yMax);

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

421
    if (bot.x) {

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

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

424
            pointBounds(point(param), xMin, yMin, xMax, yMax);

425
    }

426
    if (bot.y) {

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

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

429
            pointBounds(point(param), xMin, yMin, xMax, yMax);

430
    }

431
}

432


433
void CubicSegment::bound(double &xMin, double &yMin, double &xMax, double &yMax) const {

434
    pointBounds(p[0], xMin, yMin, xMax, yMax);

435
    pointBounds(p[3], xMin, yMin, xMax, yMax);

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

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

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

439
    double params[2];

440
    int solutions;

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

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

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

444
            pointBounds(point(params[i]), xMin, yMin, xMax, yMax);

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

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

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

448
            pointBounds(point(params[i]), xMin, yMin, xMax, yMax);

449
}

450


451
void LinearSegment::reverse() {

452
    Point2 tmp = p[0];

453
    p[0] = p[1];

454
    p[1] = tmp;

455
}

456


457
void QuadraticSegment::reverse() {

458
    Point2 tmp = p[0];

459
    p[0] = p[2];

460
    p[2] = tmp;

461
}

462


463
void CubicSegment::reverse() {

464
    Point2 tmp = p[0];

465
    p[0] = p[3];

466
    p[3] = tmp;

467
    tmp = p[1];

468
    p[1] = p[2];

469
    p[2] = tmp;

470
}

471


472
void LinearSegment::moveStartPoint(Point2 to) {

473
    p[0] = to;

474
}

475


476
void QuadraticSegment::moveStartPoint(Point2 to) {

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

478
    Point2 origP1 = p[1];

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

480
    p[0] = to;

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

482
        p[1] = origP1;

483
}

484


485
void CubicSegment::moveStartPoint(Point2 to) {

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

487
    p[0] = to;

488
}

489


490
void LinearSegment::moveEndPoint(Point2 to) {

491
    p[1] = to;

492
}

493


494
void QuadraticSegment::moveEndPoint(Point2 to) {

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

496
    Point2 origP1 = p[1];

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

498
    p[2] = to;

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

500
        p[1] = origP1;

501
}

502


503
void CubicSegment::moveEndPoint(Point2 to) {

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

505
    p[3] = to;

506
}

507


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

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

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

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

512
}

513


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

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

516
    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);

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

518
}

519


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

521
    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);

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

523
        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.),

524
        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.),

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

526
    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);

527
}

528


529
EdgeSegment *QuadraticSegment::convertToCubic() const {

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

531
}

532


533
}

534


535