2 bezier.cc -- implement Bezier and Bezier_bow
4 source file of the GNU LilyPond music typesetter
6 (c) 1998--2004 Jan Nieuwenhuizen <janneke@gnu.org>
13 #include "libc-extension.hh"
15 #include "polynomial.hh"
18 binomial_coefficient (Real over
, int under
)
24 x
*= over
/ Real (under
);
33 scale (Array
<Offset
>* array
, Real x
, Real y
)
35 for (int i
= 0; i
< array
->size (); i
++)
37 (*array
)[i
][X_AXIS
] = x
* (*array
)[i
][X_AXIS
];
38 (*array
)[i
][Y_AXIS
] = y
* (*array
)[i
][Y_AXIS
];
43 rotate (Array
<Offset
>* array
, Real phi
)
45 Offset
rot (complex_exp (Offset (0, phi
)));
46 for (int i
= 0; i
< array
->size (); i
++)
47 (*array
)[i
] = complex_multiply (rot
, (*array
)[i
]);
51 translate (Array
<Offset
>* array
, Offset o
)
53 for (int i
= 0; i
< array
->size (); i
++)
59 Formula of the bezier 3-spline
61 sum_{j=0}^3 (3 over j) z_j (1-t)^ (3-j) t^j
65 Bezier::get_other_coordinate (Axis a
, Real x
) const
67 Axis other
= Axis ((a
+1)%NO_AXES
);
68 Array
<Real
> ts
= solve_point (a
, x
);
72 programming_error ("No solution found for Bezier intersection.");
76 Offset c
= curve_point (ts
[0]);
78 if (fabs (c
[a
] - x
) > 1e-8)
79 programming_error ("Bezier intersection not correct?");
86 Bezier::curve_point (Real t
)const
89 Real one_min_tj
= (1-t
)* (1-t
)* (1-t
);
92 for (int j
=0 ; j
< 4; j
++)
94 o
+= control_
[j
] * binomial_coefficient (3, j
)
95 * pow (t
,j
) * pow (1-t
, 3-j
);
103 assert (fabs (o
[X_AXIS
] - polynomial (X_AXIS
).eval (t
))< 1e-8);
104 assert (fabs (o
[Y_AXIS
] - polynomial (Y_AXIS
).eval (t
))< 1e-8);
112 Bezier::polynomial (Axis a
)const
115 for (int j
=0; j
<= 3; j
++)
117 p
+= (control_
[j
][a
] * binomial_coefficient (3, j
))
118 * Polynomial::power (j
, Polynomial (0,1))*
119 Polynomial::power (3 - j
, Polynomial (1,-1));
126 Remove all numbers outside [0,1] from SOL
129 filter_solutions (Array
<Real
> sol
)
131 for (int i
= sol
.size (); i
--;)
132 if (sol
[i
] < 0 || sol
[i
] >1)
138 find t such that derivative is proportional to DERIV
141 Bezier::solve_derivative (Offset deriv
)const
143 Polynomial xp
=polynomial (X_AXIS
);
144 Polynomial yp
=polynomial (Y_AXIS
);
148 Polynomial combine
= xp
* deriv
[Y_AXIS
] - yp
* deriv
[X_AXIS
];
150 return filter_solutions (combine
.solve ());
155 Find t such that curve_point (t)[AX] == COORDINATE
158 Bezier::solve_point (Axis ax
, Real coordinate
) const
160 Polynomial
p (polynomial (ax
));
161 p
.coefs_
[0] -= coordinate
;
163 Array
<Real
> sol (p
.solve ());
164 return filter_solutions (sol
);
168 Compute the bounding box dimensions in direction of A.
171 Bezier::extent (Axis a
)const
173 int o
= (a
+1)%NO_AXES
;
177 Array
<Real
> sols (solve_derivative (d
));
180 for (int i
= sols
.size (); i
--;)
182 Offset
o (curve_point (sols
[i
]));
183 iv
.unite (Interval (o
[a
],o
[a
]));
193 Bezier::scale (Real x
, Real y
)
195 for (int i
= CONTROL_COUNT
; i
--;)
197 control_
[i
][X_AXIS
] = x
* control_
[i
][X_AXIS
];
198 control_
[i
][Y_AXIS
] = y
* control_
[i
][Y_AXIS
];
203 Bezier::rotate (Real phi
)
205 Offset
rot (complex_exp (Offset (0, phi
)));
206 for (int i
= 0; i
< CONTROL_COUNT
; i
++)
207 control_
[i
] = complex_multiply (rot
, control_
[i
]);
211 Bezier::translate (Offset o
)
213 for (int i
= 0; i
< CONTROL_COUNT
; i
++)
218 Bezier::assert_sanity () const
220 for (int i
=0; i
< CONTROL_COUNT
; i
++)
221 assert (!isnan (control_
[i
].length ())
222 && !isinf (control_
[i
].length ()));
229 for (int i
=0; i
< CONTROL_COUNT
; i
++)
230 b2
.control_
[CONTROL_COUNT
-i
-1] = control_
[i
];