Skip to main content

ternary_contours/interpolation/
cubic.rs

1use std::fmt;
2
3use super::AlphaInterval;
4
5const KOHLER_DENOMINATOR_GUARD: f64 = 64.0 * f64::EPSILON;
6
7/// Geometric extension of a directed binary interaction into a ternary interior.
8///
9/// Every policy retains the raw multicomponent prefactor `xi*xj`; only the
10/// directed interval parameter changes.
11#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
12#[non_exhaustive]
13pub enum BinaryExtrapolation {
14    /// Experimental, non-recommended direct extension `t=xj`.
15    ///
16    /// This is neither linear interpolation nor conventional Muggianu. Its
17    /// ternary-interior value depends on the canonical edge direction; use
18    /// [`Self::Muggianu`] or [`Self::Kohler`] for stable applications.
19    RawBarycentric,
20    /// Assign half the remaining component to each member: `t=xj+xk/2`.
21    #[default]
22    Muggianu,
23    /// Normalize within the binary pair: `t=xj/(xi+xj)`.
24    Kohler,
25}
26
27/// Value and unconstrained barycentric partial derivatives of one pair term.
28#[derive(Clone, Copy, Debug, PartialEq)]
29pub struct PairEvaluation {
30    pub value: f64,
31    /// Derivatives with respect to `[xi, xj, xk]` before the simplex constraint.
32    pub derivatives: [f64; 3],
33    pub parameter: f64,
34}
35
36/// A directed alpha interval attached to two local triangle vertices.
37#[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/// One local cubic-alpha field on a ternary elementary triangle.
76#[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    /// Evaluate the complete local field at barycentric coordinates.
142    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    /// Analytic reduced gradient for `x0=u`, `x1=v`, `x2=1-u-v`.
158    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
183/// Centralized binary pair contribution and policy-specific analytic derivative.
184///
185/// Inputs and derivatives are ordered as directed source `xi`, destination
186/// `xj`, and remaining component `xk`.
187pub 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}