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