1use std::fmt;
2
3use super::AlphaInterval;
4
5const KOHLER_DENOMINATOR_GUARD: f64 = 64.0 * f64::EPSILON;
6
7#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
12#[non_exhaustive]
13pub enum BinaryExtrapolation {
14 RawBarycentric,
20 #[default]
22 Muggianu,
23 Kohler,
25}
26
27#[derive(Clone, Copy, Debug, PartialEq)]
29pub struct PairEvaluation {
30 pub value: f64,
31 pub derivatives: [f64; 3],
33 pub parameter: f64,
34}
35
36#[derive(Clone, Copy, Debug, PartialEq)]
38pub struct DirectedAlphaInterval {
39 pub start: usize,
40 pub end: usize,
41 pub interval: AlphaInterval,
42}
43
44impl DirectedAlphaInterval {
45 pub fn new(
46 start: usize,
47 end: usize,
48 interval: AlphaInterval,
49 ) -> Result<Self, InterpolationError> {
50 if start >= 3 || end >= 3 || start == end {
51 return Err(InterpolationError::InvalidDirectedEdge { start, end });
52 }
53 if !interval.alpha0.is_finite() || !interval.alpha1.is_finite() {
54 return Err(InterpolationError::NonFiniteAlpha {
55 alpha0: interval.alpha0,
56 alpha1: interval.alpha1,
57 });
58 }
59 Ok(Self {
60 start,
61 end,
62 interval,
63 })
64 }
65
66 pub const fn reversed(self) -> Self {
67 Self {
68 start: self.end,
69 end: self.start,
70 interval: self.interval.reversed(),
71 }
72 }
73}
74
75#[derive(Clone, Debug, PartialEq)]
77pub struct CubicAlphaTriangle {
78 vertex_values: [f64; 3],
79 edge_intervals: [DirectedAlphaInterval; 3],
80 extrapolation: BinaryExtrapolation,
81}
82
83impl CubicAlphaTriangle {
84 pub fn new(
85 vertex_values: [f64; 3],
86 edge_intervals: [DirectedAlphaInterval; 3],
87 extrapolation: BinaryExtrapolation,
88 ) -> Result<Self, InterpolationError> {
89 if let Some((index, value)) = vertex_values
90 .into_iter()
91 .enumerate()
92 .find(|(_, value)| !value.is_finite())
93 {
94 return Err(InterpolationError::NonFiniteVertexValue { index, value });
95 }
96 let mut pairs = [false; 3];
97 for edge in edge_intervals {
98 if edge.start >= 3 || edge.end >= 3 || edge.start == edge.end {
99 return Err(InterpolationError::InvalidDirectedEdge {
100 start: edge.start,
101 end: edge.end,
102 });
103 }
104 if !edge.interval.alpha0.is_finite() || !edge.interval.alpha1.is_finite() {
105 return Err(InterpolationError::NonFiniteAlpha {
106 alpha0: edge.interval.alpha0,
107 alpha1: edge.interval.alpha1,
108 });
109 }
110 let pair = pair_index(edge.start, edge.end);
111 if pairs[pair] {
112 return Err(InterpolationError::DuplicateEdgePair {
113 start: edge.start,
114 end: edge.end,
115 });
116 }
117 pairs[pair] = true;
118 }
119 if pairs.iter().any(|present| !present) {
120 return Err(InterpolationError::MissingEdgePair);
121 }
122 Ok(Self {
123 vertex_values,
124 edge_intervals,
125 extrapolation,
126 })
127 }
128
129 pub const fn vertex_values(&self) -> [f64; 3] {
130 self.vertex_values
131 }
132
133 pub const fn edge_intervals(&self) -> &[DirectedAlphaInterval; 3] {
134 &self.edge_intervals
135 }
136
137 pub const fn extrapolation(&self) -> BinaryExtrapolation {
138 self.extrapolation
139 }
140
141 pub fn value(&self, barycentric: [f64; 3]) -> f64 {
143 let linear = self
144 .vertex_values
145 .into_iter()
146 .zip(barycentric)
147 .map(|(value, weight)| value * weight)
148 .sum::<f64>();
149 linear
150 + self
151 .edge_intervals
152 .iter()
153 .map(|edge| self.evaluate_edge(*edge, barycentric).value)
154 .sum::<f64>()
155 }
156
157 pub fn gradient_reduced(&self, u: f64, v: f64) -> [f64; 2] {
159 let barycentric = [u, v, 1.0 - u - v];
160 let mut partial = self.vertex_values;
161 for edge in self.edge_intervals {
162 let evaluation = self.evaluate_edge(edge, barycentric);
163 let remaining = remaining_index(edge.start, edge.end);
164 partial[edge.start] += evaluation.derivatives[0];
165 partial[edge.end] += evaluation.derivatives[1];
166 partial[remaining] += evaluation.derivatives[2];
167 }
168 [partial[0] - partial[2], partial[1] - partial[2]]
169 }
170
171 fn evaluate_edge(&self, edge: DirectedAlphaInterval, barycentric: [f64; 3]) -> PairEvaluation {
172 let remaining = remaining_index(edge.start, edge.end);
173 evaluate_pair(
174 barycentric[edge.start],
175 barycentric[edge.end],
176 barycentric[remaining],
177 edge.interval,
178 self.extrapolation,
179 )
180 }
181}
182
183pub fn evaluate_pair(
188 xi: f64,
189 xj: f64,
190 xk: f64,
191 interval: AlphaInterval,
192 extrapolation: BinaryExtrapolation,
193) -> PairEvaluation {
194 let prefactor = xi * xj;
195 let (parameter, parameter_derivatives) = match extrapolation {
196 BinaryExtrapolation::RawBarycentric => (xj, [0.0, 1.0, 0.0]),
197 BinaryExtrapolation::Muggianu => (xj + 0.5 * xk, [0.0, 1.0, 0.5]),
198 BinaryExtrapolation::Kohler => {
199 let denominator = xi + xj;
200 if denominator.abs() <= KOHLER_DENOMINATOR_GUARD {
201 return PairEvaluation {
202 value: 0.0,
203 derivatives: [0.0; 3],
204 parameter: 0.5,
205 };
206 }
207 let inverse_square = 1.0 / (denominator * denominator);
208 (
209 xj / denominator,
210 [-xj * inverse_square, xi * inverse_square, 0.0],
211 )
212 }
213 };
214 let polynomial = interval.alpha0 + interval.alpha1 * parameter;
215 let prefactor_derivatives = [xj, xi, 0.0];
216 let mut derivatives = [0.0; 3];
217 for index in 0..3 {
218 derivatives[index] = prefactor_derivatives[index] * polynomial
219 + prefactor * interval.alpha1 * parameter_derivatives[index];
220 }
221 PairEvaluation {
222 value: prefactor * polynomial,
223 derivatives,
224 parameter,
225 }
226}
227
228const fn pair_index(left: usize, right: usize) -> usize {
229 let (low, high) = if left < right {
230 (left, right)
231 } else {
232 (right, left)
233 };
234 match (low, high) {
235 (0, 1) => 0,
236 (1, 2) => 1,
237 (0, 2) => 2,
238 _ => usize::MAX,
239 }
240}
241
242const fn remaining_index(left: usize, right: usize) -> usize {
243 3 - left - right
244}
245
246#[derive(Clone, Debug, PartialEq)]
247#[non_exhaustive]
248pub enum InterpolationError {
249 InvalidDirectedEdge { start: usize, end: usize },
250 DuplicateEdgePair { start: usize, end: usize },
251 MissingEdgePair,
252 NonFiniteAlpha { alpha0: f64, alpha1: f64 },
253 NonFiniteVertexValue { index: usize, value: f64 },
254}
255
256impl fmt::Display for InterpolationError {
257 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
258 match self {
259 Self::InvalidDirectedEdge { start, end } => {
260 write!(formatter, "invalid local directed edge {start}->{end}")
261 }
262 Self::DuplicateEdgePair { start, end } => {
263 write!(formatter, "duplicate local edge pair {start}-{end}")
264 }
265 Self::MissingEdgePair => {
266 write!(formatter, "local cubic triangle is missing an edge pair")
267 }
268 Self::NonFiniteAlpha { alpha0, alpha1 } => {
269 write!(
270 formatter,
271 "alpha coefficients must be finite: ({alpha0:?}, {alpha1:?})"
272 )
273 }
274 Self::NonFiniteVertexValue { index, value } => {
275 write!(
276 formatter,
277 "triangle vertex value {index} is not finite: {value:?}"
278 )
279 }
280 }
281 }
282}
283
284impl std::error::Error for InterpolationError {}
285
286#[cfg(test)]
287mod tests {
288 use super::*;
289
290 const ALPHA: AlphaInterval = AlphaInterval::new(1.7, -2.3);
291
292 fn close(left: f64, right: f64) {
293 assert!((left - right).abs() < 2.0e-9, "{left} != {right}");
294 }
295
296 #[test]
297 fn policy_parameters_and_raw_prefactor_are_exact() {
298 let (xi, xj, xk) = (0.2, 0.3, 0.5);
299 let raw = evaluate_pair(xi, xj, xk, ALPHA, BinaryExtrapolation::RawBarycentric);
300 let muggianu = evaluate_pair(xi, xj, xk, ALPHA, BinaryExtrapolation::Muggianu);
301 let kohler = evaluate_pair(xi, xj, xk, ALPHA, BinaryExtrapolation::Kohler);
302 close(raw.parameter, xj);
303 close(muggianu.parameter, xj + xk / 2.0);
304 close(kohler.parameter, xj / (xi + xj));
305 for evaluation in [raw, muggianu, kohler] {
306 close(
307 evaluation.value,
308 xi * xj * (ALPHA.alpha0 + ALPHA.alpha1 * evaluation.parameter),
309 );
310 }
311 }
312
313 #[test]
314 fn all_policies_are_exact_on_binary_edges_and_for_constant_alpha() {
315 for t in [0.0, 0.13, 0.5, 0.87, 1.0] {
316 for policy in [
317 BinaryExtrapolation::RawBarycentric,
318 BinaryExtrapolation::Muggianu,
319 BinaryExtrapolation::Kohler,
320 ] {
321 let pair = evaluate_pair(1.0 - t, t, 0.0, ALPHA, policy);
322 close(pair.parameter, t);
323 close(
324 pair.value,
325 (1.0 - t) * t * (ALPHA.alpha0 + ALPHA.alpha1 * t),
326 );
327 }
328 }
329 let constant = AlphaInterval::new(1.7, 0.0);
330 for policy in [
331 BinaryExtrapolation::RawBarycentric,
332 BinaryExtrapolation::Muggianu,
333 BinaryExtrapolation::Kohler,
334 ] {
335 close(
336 evaluate_pair(0.2, 0.3, 0.5, constant, policy).value,
337 1.7 * 0.2 * 0.3,
338 );
339 }
340 }
341
342 #[test]
343 fn muggianu_and_kohler_reverse_interior_but_raw_is_directional() {
344 let (xi, xj, xk) = (0.17, 0.31, 0.52);
345 for policy in [BinaryExtrapolation::Muggianu, BinaryExtrapolation::Kohler] {
346 let forward = evaluate_pair(xi, xj, xk, ALPHA, policy);
347 let reverse = evaluate_pair(xj, xi, xk, ALPHA.reversed(), policy);
348 close(reverse.parameter, 1.0 - forward.parameter);
349 close(forward.value, reverse.value);
350 }
351 let forward = evaluate_pair(xi, xj, xk, ALPHA, BinaryExtrapolation::RawBarycentric);
352 let reverse = evaluate_pair(
353 xj,
354 xi,
355 xk,
356 ALPHA.reversed(),
357 BinaryExtrapolation::RawBarycentric,
358 );
359 assert!((forward.value - reverse.value).abs() > 1.0e-4);
360 }
361
362 #[test]
363 fn kohler_has_quadratic_dilution_and_finite_third_vertex_limit() {
364 let ratio = 0.35;
365 let full = evaluate_pair(1.0 - ratio, ratio, 0.0, ALPHA, BinaryExtrapolation::Kohler);
366 for dilution in [0.8, 0.2, 1.0e-8] {
367 let diluted = evaluate_pair(
368 dilution * (1.0 - ratio),
369 dilution * ratio,
370 1.0 - dilution,
371 ALPHA,
372 BinaryExtrapolation::Kohler,
373 );
374 close(diluted.value, full.value * dilution * dilution);
375 assert!(diluted.derivatives.into_iter().all(f64::is_finite));
376 }
377 let corner = evaluate_pair(0.0, 0.0, 1.0, ALPHA, BinaryExtrapolation::Kohler);
378 assert_eq!(corner.value, 0.0);
379 assert!(corner.derivatives.into_iter().all(f64::is_finite));
380 }
381
382 #[test]
383 fn analytic_pair_derivatives_match_centered_differences() {
384 let point = [0.21, 0.34, 0.45];
385 let h = 1.0e-7;
386 for policy in [
387 BinaryExtrapolation::RawBarycentric,
388 BinaryExtrapolation::Muggianu,
389 BinaryExtrapolation::Kohler,
390 ] {
391 let actual = evaluate_pair(point[0], point[1], point[2], ALPHA, policy);
392 for index in 0..3 {
393 let mut plus = point;
394 let mut minus = point;
395 plus[index] += h;
396 minus[index] -= h;
397 let plus_value = evaluate_pair(plus[0], plus[1], plus[2], ALPHA, policy).value;
398 let minus_value = evaluate_pair(minus[0], minus[1], minus[2], ALPHA, policy).value;
399 close(
400 actual.derivatives[index],
401 (plus_value - minus_value) / (2.0 * h),
402 );
403 }
404 }
405 }
406
407 fn triangle(policy: BinaryExtrapolation) -> CubicAlphaTriangle {
408 CubicAlphaTriangle::new(
409 [2.0, -0.5, 1.25],
410 [
411 DirectedAlphaInterval::new(0, 1, ALPHA).unwrap(),
412 DirectedAlphaInterval::new(1, 2, AlphaInterval::new(-0.7, 1.1)).unwrap(),
413 DirectedAlphaInterval::new(0, 2, AlphaInterval::new(0.4, -0.9)).unwrap(),
414 ],
415 policy,
416 )
417 .unwrap()
418 }
419
420 #[test]
421 fn local_field_reproduces_vertices_edges_and_zero_alpha_linear_limit() {
422 for policy in [
423 BinaryExtrapolation::RawBarycentric,
424 BinaryExtrapolation::Muggianu,
425 BinaryExtrapolation::Kohler,
426 ] {
427 let model = triangle(policy);
428 assert_eq!(model.value([1.0, 0.0, 0.0]), 2.0);
429 assert_eq!(model.value([0.0, 1.0, 0.0]), -0.5);
430 assert_eq!(model.value([0.0, 0.0, 1.0]), 1.25);
431 for t in [0.0, 0.2, 0.7, 1.0] {
432 close(model.value([1.0 - t, t, 0.0]), ALPHA.value(2.0, -0.5, t));
433 }
434 }
435 let zero = AlphaInterval::default();
436 let model = CubicAlphaTriangle::new(
437 [2.0, -0.5, 1.25],
438 [
439 DirectedAlphaInterval::new(0, 1, zero).unwrap(),
440 DirectedAlphaInterval::new(1, 2, zero).unwrap(),
441 DirectedAlphaInterval::new(0, 2, zero).unwrap(),
442 ],
443 BinaryExtrapolation::Muggianu,
444 )
445 .unwrap();
446 let x = [0.2, 0.3, 0.5];
447 close(model.value(x), 2.0 * x[0] - 0.5 * x[1] + 1.25 * x[2]);
448 }
449
450 #[test]
451 fn constant_alpha_reproduces_pairwise_quadratic_regular_solution() {
452 let model = CubicAlphaTriangle::new(
453 [1.2, -0.4, 2.1],
454 [
455 DirectedAlphaInterval::new(0, 1, AlphaInterval::new(0.8, 0.0)).unwrap(),
456 DirectedAlphaInterval::new(1, 2, AlphaInterval::new(-1.1, 0.0)).unwrap(),
457 DirectedAlphaInterval::new(0, 2, AlphaInterval::new(0.35, 0.0)).unwrap(),
458 ],
459 BinaryExtrapolation::Kohler,
460 )
461 .unwrap();
462 for x in [[0.2, 0.3, 0.5], [0.01, 0.49, 0.5], [0.6, 0.2, 0.2]] {
463 let expected = 1.2 * x[0] - 0.4 * x[1] + 2.1 * x[2] + 0.8 * x[0] * x[1]
464 - 1.1 * x[1] * x[2]
465 + 0.35 * x[0] * x[2];
466 close(model.value(x), expected);
467 }
468 }
469
470 #[test]
471 fn local_vertex_permutation_preserves_canonical_directed_metadata() {
472 let original_edges = [
473 DirectedAlphaInterval::new(0, 1, ALPHA).unwrap(),
474 DirectedAlphaInterval::new(1, 2, AlphaInterval::new(-0.7, 1.1)).unwrap(),
475 DirectedAlphaInterval::new(0, 2, AlphaInterval::new(0.4, -0.9)).unwrap(),
476 ];
477 let old_to_new = [1, 2, 0];
478 let original_x = [0.2, 0.3, 0.5];
479 let permuted_x = [original_x[2], original_x[0], original_x[1]];
480 for policy in [
481 BinaryExtrapolation::RawBarycentric,
482 BinaryExtrapolation::Muggianu,
483 BinaryExtrapolation::Kohler,
484 ] {
485 let original =
486 CubicAlphaTriangle::new([2.0, -0.5, 1.25], original_edges, policy).unwrap();
487 let transformed = original_edges.map(|edge| {
488 DirectedAlphaInterval::new(
489 old_to_new[edge.start],
490 old_to_new[edge.end],
491 edge.interval,
492 )
493 .unwrap()
494 });
495 let permuted = CubicAlphaTriangle::new([1.25, 2.0, -0.5], transformed, policy).unwrap();
496 close(original.value(original_x), permuted.value(permuted_x));
497 }
498 }
499
500 #[test]
501 fn local_analytic_gradient_matches_finite_differences_for_all_policies() {
502 let h = 1.0e-7;
503 for policy in [
504 BinaryExtrapolation::RawBarycentric,
505 BinaryExtrapolation::Muggianu,
506 BinaryExtrapolation::Kohler,
507 ] {
508 let model = triangle(policy);
509 for [u, v] in [[0.23, 0.31], [0.49, 0.49], [1.0e-7, 1.0e-7]] {
510 let gradient = model.gradient_reduced(u, v);
511 let du = (model.value([u + h, v, 1.0 - u - h - v])
512 - model.value([u - h, v, 1.0 - u + h - v]))
513 / (2.0 * h);
514 let dv = (model.value([u, v + h, 1.0 - u - v - h])
515 - model.value([u, v - h, 1.0 - u - v + h]))
516 / (2.0 * h);
517 assert!((gradient[0] - du).abs() < 5.0e-7);
518 assert!((gradient[1] - dv).abs() < 5.0e-7);
519 }
520 }
521 }
522}