1 /*
2 * Copyright 2012 Google Inc.
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 #include "CurveIntersection.h"
8 #include "IntersectionUtilities.h"
9 #include "QuadraticUtilities.h"
10
11 /*
12 Given a quadratic q, t1, and t2, find a small quadratic segment.
13
14 The new quadratic is defined by A, B, and C, where
15 A = c[0]*(1 - t1)*(1 - t1) + 2*c[1]*t1*(1 - t1) + c[2]*t1*t1
16 C = c[3]*(1 - t1)*(1 - t1) + 2*c[2]*t1*(1 - t1) + c[1]*t1*t1
17
18 To find B, compute the point halfway between t1 and t2:
19
20 q(at (t1 + t2)/2) == D
21
22 Next, compute where D must be if we know the value of B:
23
24 _12 = A/2 + B/2
25 12_ = B/2 + C/2
26 123 = A/4 + B/2 + C/4
27 = D
28
29 Group the known values on one side:
30
31 B = D*2 - A/2 - C/2
32 */
33
interp_quad_coords(const double * src,double t)34 static double interp_quad_coords(const double* src, double t)
35 {
36 double ab = interp(src[0], src[2], t);
37 double bc = interp(src[2], src[4], t);
38 double abc = interp(ab, bc, t);
39 return abc;
40 }
41
sub_divide(const Quadratic & src,double t1,double t2,Quadratic & dst)42 void sub_divide(const Quadratic& src, double t1, double t2, Quadratic& dst) {
43 double ax = dst[0].x = interp_quad_coords(&src[0].x, t1);
44 double ay = dst[0].y = interp_quad_coords(&src[0].y, t1);
45 double dx = interp_quad_coords(&src[0].x, (t1 + t2) / 2);
46 double dy = interp_quad_coords(&src[0].y, (t1 + t2) / 2);
47 double cx = dst[2].x = interp_quad_coords(&src[0].x, t2);
48 double cy = dst[2].y = interp_quad_coords(&src[0].y, t2);
49 /* bx = */ dst[1].x = 2*dx - (ax + cx)/2;
50 /* by = */ dst[1].y = 2*dy - (ay + cy)/2;
51 }
52
sub_divide(const Quadratic & src,const _Point & a,const _Point & c,double t1,double t2)53 _Point sub_divide(const Quadratic& src, const _Point& a, const _Point& c, double t1, double t2) {
54 _Point b;
55 double dx = interp_quad_coords(&src[0].x, (t1 + t2) / 2);
56 double dy = interp_quad_coords(&src[0].y, (t1 + t2) / 2);
57 b.x = 2 * dx - (a.x + c.x) / 2;
58 b.y = 2 * dy - (a.y + c.y) / 2;
59 return b;
60 }
61
62 /* classic one t subdivision */
interp_quad_coords(const double * src,double * dst,double t)63 static void interp_quad_coords(const double* src, double* dst, double t)
64 {
65 double ab = interp(src[0], src[2], t);
66 double bc = interp(src[2], src[4], t);
67
68 dst[0] = src[0];
69 dst[2] = ab;
70 dst[4] = interp(ab, bc, t);
71 dst[6] = bc;
72 dst[8] = src[4];
73 }
74
chop_at(const Quadratic & src,QuadraticPair & dst,double t)75 void chop_at(const Quadratic& src, QuadraticPair& dst, double t)
76 {
77 interp_quad_coords(&src[0].x, &dst.pts[0].x, t);
78 interp_quad_coords(&src[0].y, &dst.pts[0].y, t);
79 }
80