Skip to main content

trackball/
clamp.rs

1use crate::{Delta, Frame, Plane, Scope, float};
2use core::fmt::Debug;
3use glam::{Quat, Vec3};
4
5/// Clamp wrt abstract boundary conditions of [`Frame`] and [`Scope`].
6///
7/// Specific boundary conditions are defined by trait implementations (e.g., [`Bound`]).
8///
9/// Exceeding a boundary condition is communicated by specifying an exceeded plane in world space.
10/// If the plane is orthogonal to [`Delta`], it is completely stopped. If not, it glides along the
11/// plane. In this case, the direction of [`Delta`] is changed by projecting the exceeded position
12/// onto the boundary plane and finding the [`Delta`] from initial to projected position. This
13/// projected [`Delta`] is repeatedly revalidated wrt boundary conditions until no new boundary
14/// plane is exceeded. For orthogonal boundary conditions (e.g., a box), revalidation usually
15/// passes after one, two, or three loops whenever zero, one, or two boundary conditions intersect
16/// (i.e., face, edge, or corner).
17///
18/// Positions moving on spheres (e.g., the eye orbiting around the target) are projected onto the
19/// circle where the sphere intersects the boundary plane. The up axis is treated as position on
20/// the unit sphere. [`Delta::Scale`] glides by keeping its ratio but moving its pivot such that
21/// the exceeded position is projected onto the boundary plane, i.e., scaling turns partially into
22/// sliding. It stops where boundary planes moving along with the frame (e.g., distance bounds)
23/// are reached.
24///
25/// [`Bound`]: crate::Bound
26pub trait Clamp: Send + Sync + Debug + 'static {
27    /// Maximum loops due to maximum possible boundary plane intersections.
28    ///
29    /// Measure to break out of validation loop as last resort. Default is `100`. Round boundary
30    /// conditions require more loops whereas flat ones should stop with the 3rd validation
31    /// (i.e., a corner) for each validated position (e.g., target, eye). When reached, [`Delta`]
32    /// stops at the boundary instead of gliding along it.
33    #[must_use]
34    fn loops(&self) -> usize {
35        100
36    }
37
38    /// Exceeded boundary plane for target position in world space.
39    ///
40    /// Must return `None` if target position satisfies all boundary conditions.
41    #[must_use]
42    fn target(&self, frame: Frame) -> Option<Plane>;
43    /// Exceeded boundary plane for eye position in world space.
44    ///
45    /// Must return `None` if eye position satisfies all boundary conditions.
46    #[must_use]
47    fn eye(&self, frame: Frame) -> Option<Plane>;
48    /// Exceeded boundary plane for up position in world space.
49    ///
50    /// The up position is the up axis (i.e., [`Frame::yaw_axis()`]) as position on the unit
51    /// sphere.
52    ///
53    /// Must return `None` if up position satisfies all boundary conditions.
54    #[must_use]
55    fn up(&self, frame: Frame) -> Option<Plane>;
56
57    /// Computes clamped [`Delta`] wrt abstract boundary conditions of [`Frame`] and [`Scope`].
58    ///
59    /// Returns `None` if [`Delta`] satisfies all boundary conditions.
60    #[allow(clippy::too_many_lines)]
61    #[must_use]
62    fn compute(&self, frame: Frame, scope: Scope, delta: Delta) -> Option<(Delta, usize)> {
63        let mut min_delta = delta;
64        let mut loops = 0;
65        match delta {
66            Delta::Frame => return None,
67            Delta::First { yaw_axis, .. } => {
68                // Target orbits around fixed eye.
69                let eye = frame.eye();
70                let distance = frame.distance();
71                loop {
72                    let new_frame = min_delta.transform(frame);
73                    let new_target = if let Some(plane) = self.target(new_frame) {
74                        cap(eye, distance, plane, new_frame.target())
75                    } else if let Some(plane) = self.up(new_frame) {
76                        let up = new_frame.yaw_axis();
77                        cap(Vec3::ZERO, 1.0, plane, up)
78                            .map(|new_up| eye + arc(up, new_up) * (new_frame.target() - eye))
79                    } else {
80                        break;
81                    };
82                    min_delta = new_target
83                        .and_then(|new_target| look_around(frame, yaw_axis, new_target))
84                        .map_or(Delta::Frame, |(pitch, yaw)| Delta::First {
85                            pitch,
86                            yaw,
87                            yaw_axis,
88                        });
89                    if loops == self.loops() {
90                        min_delta = stop(self, frame, delta).unwrap_or(min_delta);
91                        break;
92                    }
93                    loops += 1;
94                }
95            }
96            Delta::Track { .. } => {
97                // Target slides in world space while eye is fixed.
98                let old_target = frame.target();
99                let eye = frame.eye();
100                // Fixed eye cannot be moved inside if it is already outside.
101                let eye_bound = self.eye(frame).is_none();
102                loop {
103                    let new_frame = min_delta.transform(frame);
104                    let new_target = if let Some(plane) = self.target(new_frame) {
105                        Some(plane.project_point(new_frame.target()))
106                    } else if let Some(plane) = self.eye(new_frame).filter(|_| eye_bound) {
107                        // Move target inversely to projected eye, e.g., to satisfy distance.
108                        let new_eye = new_frame.eye();
109                        Some(new_frame.target() - (plane.project_point(new_eye) - new_eye))
110                    } else if let Some(plane) = self.up(new_frame) {
111                        let up = new_frame.yaw_axis();
112                        cap(Vec3::ZERO, 1.0, plane, up)
113                            .map(|new_up| eye + arc(up, new_up) * (new_frame.target() - eye))
114                    } else {
115                        break;
116                    };
117                    min_delta = new_target.map_or(Delta::Frame, |new_target| Delta::Track {
118                        vector: new_target - old_target,
119                    });
120                    if loops == self.loops() {
121                        min_delta = stop(self, frame, delta).unwrap_or(min_delta);
122                        break;
123                    }
124                    loops += 1;
125                }
126            }
127            Delta::Orbit {
128                rotation: mut rot,
129                point: pos,
130            } => {
131                // Eye and target orbit around pivot in world space.
132                let old_rot = frame.view().rotation;
133                let pivot = frame.target() + old_rot * pos;
134                // Target only moves if pivot is not the target.
135                let target_bound = pos != Vec3::ZERO;
136                loop {
137                    let new_frame = min_delta.transform(frame);
138                    let correction =
139                        if let Some(plane) = self.target(new_frame).filter(|_| target_bound) {
140                            let new_target = new_frame.target();
141                            let radius = (new_target - pivot).length();
142                            cap(pivot, radius, plane, new_target)
143                                .map(|target| arc(new_target - pivot, target - pivot))
144                        } else if let Some(plane) = self.eye(new_frame) {
145                            let new_eye = new_frame.eye();
146                            let radius = (new_eye - pivot).length();
147                            cap(pivot, radius, plane, new_eye)
148                                .map(|eye| arc(new_eye - pivot, eye - pivot))
149                        } else if let Some(plane) = self.up(new_frame) {
150                            let up = new_frame.yaw_axis();
151                            cap(Vec3::ZERO, 1.0, plane, up).map(|new_up| arc(up, new_up))
152                        } else {
153                            break;
154                        };
155                    // Apply world space correction after delta rotation around same pivot.
156                    min_delta = correction.map_or(Delta::Frame, |correction| {
157                        rot = (old_rot.inverse() * correction * old_rot * rot).normalize();
158                        Delta::Orbit {
159                            rotation: rot,
160                            point: pos,
161                        }
162                    });
163                    if loops == self.loops() {
164                        min_delta = stop(self, frame, delta).unwrap_or(min_delta);
165                        break;
166                    }
167                    loops += 1;
168                }
169            }
170            Delta::Slide { .. } => {
171                // Eye and target slide in camera space.
172                let old_target = frame.target();
173                let old_rot_inverse = frame.view().rotation.inverse();
174                let old_eye = frame.eye();
175                loop {
176                    let new_frame = min_delta.transform(frame);
177                    let vec = if let Some(plane) = self.target(new_frame) {
178                        plane.project_point(new_frame.target()) - old_target
179                    } else if let Some(plane) = self.eye(new_frame) {
180                        plane.project_point(new_frame.eye()) - old_eye
181                    } else {
182                        break;
183                    };
184                    min_delta = Delta::Slide {
185                        vector: old_rot_inverse * vec,
186                    };
187                    if loops == self.loops() {
188                        min_delta = stop(self, frame, delta).unwrap_or(min_delta);
189                        break;
190                    }
191                    loops += 1;
192                }
193            }
194            Delta::Scale {
195                ratio: mut rat,
196                point: pos,
197            } => {
198                // Eye and target linearly move towards pivot in world space by `1.0 - rat`.
199                let old_target = frame.target();
200                let old_eye = frame.eye();
201                let old_rot = frame.view().rotation;
202                if scope.inspect() {
203                    let (znear, _zfar) = scope.clip_planes(0.0);
204                    let min_zat = -znear * (1.0 + float::sqrt(f32::EPSILON));
205                    let old_zat = frame.distance();
206                    if old_zat * rat < min_zat {
207                        rat = min_zat / old_zat;
208                        min_delta = Delta::Scale {
209                            ratio: rat,
210                            point: pos,
211                        };
212                    }
213                }
214                let scale = |pivot: Vec3, rat: f32| Delta::Scale {
215                    ratio: rat,
216                    point: old_rot.inverse() * (pivot - old_target),
217                };
218                // Exceeded plane of moved target or eye with its new and old position.
219                let exceeded = |delta: Delta| {
220                    let frame = delta.transform(frame);
221                    self.target(frame)
222                        .map(|plane| (plane, frame.target(), old_target, true))
223                        .or_else(|| {
224                            self.eye(frame)
225                                .map(|plane| (plane, frame.eye(), old_eye, false))
226                        })
227                };
228                // Keep ratio but move pivot such that exceeded position is projected onto plane.
229                let glide = |rat: f32| {
230                    let fraction = 1.0 - rat;
231                    let mut delta = Delta::Scale {
232                        ratio: rat,
233                        point: pos,
234                    };
235                    for loops in 0..=self.loops() {
236                        let Some((plane, new, old, target)) = exceeded(delta) else {
237                            return Some((delta, loops));
238                        };
239                        let glided = old + (plane.project_point(new) - old) / fraction;
240                        delta = scale(glided, rat);
241                        // Plane moving along with frame (e.g., distance bound) cannot be glided
242                        // along.
243                        let moving = exceeded(delta).is_some_and(|(other, _, _, other_target)| {
244                            other_target == target
245                                && other.normal.dot(plane.normal) > 1.0 - float::sqrt(f32::EPSILON)
246                        });
247                        if moving || fraction == 0.0 {
248                            return None;
249                        }
250                    }
251                    None
252                };
253                if let Some((delta, glide_loops)) = glide(rat) {
254                    (min_delta, loops) = (delta, glide_loops);
255                } else if exceeded(Delta::Frame).is_none() {
256                    // Stop at largest ratio still gliding along remaining planes.
257                    let fraction = 1.0 - rat;
258                    let (mut min, mut max) = (0.0, 1.0);
259                    for _ in 0..f32::MANTISSA_DIGITS {
260                        let mid = f32::midpoint(min, max);
261                        if glide(float::mul_add(fraction, -mid, 1.0)).is_some() {
262                            min = mid;
263                        } else {
264                            max = mid;
265                        }
266                    }
267                    if let Some((delta, glide_loops)) = glide(float::mul_add(fraction, -min, 1.0)) {
268                        (min_delta, loops) = (delta, glide_loops);
269                    }
270                }
271            }
272        }
273        (min_delta != delta).then_some((min_delta, loops))
274    }
275}
276
277/// Stops `delta` at largest fraction satisfying boundary conditions of `clamp` by bisection.
278///
279/// Returns `None` if boundary conditions are not satisfied initially.
280fn stop<C: Clamp + ?Sized>(clamp: &C, frame: Frame, delta: Delta) -> Option<Delta> {
281    let inside = |delta: Delta| {
282        let frame = delta.transform(frame);
283        clamp.target(frame).is_none() && clamp.eye(frame).is_none() && clamp.up(frame).is_none()
284    };
285    inside(Delta::Frame).then(|| {
286        let (mut min, mut max) = (0.0, 1.0);
287        for _ in 0..f32::MANTISSA_DIGITS {
288            let mid = f32::midpoint(min, max);
289            if inside(delta.lerp_slerp(mid)) {
290                min = mid;
291            } else {
292                max = mid;
293            }
294        }
295        delta.lerp_slerp(min)
296    })
297}
298
299/// Projects `point` onto circle where sphere at `center` with `radius` intersects with `plane`.
300///
301/// Returns `None` if sphere and plane do not intersect or if projection is ambiguous.
302fn cap(center: Vec3, radius: f32, plane: Plane, point: Vec3) -> Option<Vec3> {
303    let distance = plane.normal.dot(center) + plane.bias;
304    let square = float::mul_add(radius, radius, -distance * distance);
305    let ray = (plane.project_point(point) - plane.project_point(center)).try_normalize()?;
306    (square > 0.0).then(|| plane.project_point(center) + ray * float::sqrt(square))
307}
308
309/// Shortest arc rotation from `from` to `to` or identity if opposite or if either is zero.
310///
311/// Unlike `Quat::from_rotation_arc()`, small angles are not snapped to identity.
312fn arc(from: Vec3, to: Vec3) -> Quat {
313    match (from.try_normalize(), to.try_normalize()) {
314        (Some(from), Some(to)) if 1.0 + from.dot(to) >= 2.0 * f32::EPSILON => {
315            let axis = from.cross(to);
316            Quat::from_xyzw(axis.x, axis.y, axis.z, 1.0 + from.dot(to)).normalize()
317        }
318        _ => Quat::IDENTITY,
319    }
320}
321
322/// Decomposes rotation of target around eye into pitch and yaw of [`Delta::First`].
323///
324/// Pitch is the rotation around the pitch axis bringing the old target to the height of the new
325/// target along `yaw_axis`, which yaw preserves. Yaw is the remaining change of azimuth around
326/// `yaw_axis`. The pitch axis is not necessarily orthogonal to `yaw_axis`, e.g., when `yaw_axis` is
327/// captured from another camera of a constellation. If the height is out of reach, pitch gets as
328/// close as possible. Returns `None` if the new target coincides with the eye.
329fn look_around(frame: Frame, yaw_axis: Vec3, new_target: Vec3) -> Option<(f32, f32)> {
330    let eye = frame.eye();
331    let old_ray = (frame.target() - eye).try_normalize()?;
332    let new_ray = (new_target - eye).try_normalize()?;
333    let pitch_axis = frame.pitch_axis();
334    // Height of ray pitched by angle is `cos * angle.cos() + sin * angle.sin()`.
335    let cos = old_ray.dot(yaw_axis);
336    let sin = pitch_axis.cross(old_ray).dot(yaw_axis);
337    let square = float::mul_add(cos, cos, sin * sin);
338    let radius = float::sqrt(square);
339    let height = new_ray.dot(yaw_axis).clamp(-radius, radius);
340    // Signed elevation of old target from yaw axis.
341    let old_elevation = float::atan2(sin, cos);
342    // Elevation of new target from yaw axis on same side as old target.
343    let new_elevation = float::atan2(
344        float::sqrt(float::mul_add(height, -height, square).max(0.0)),
345        height,
346    )
347    .copysign(old_elevation);
348    // Rotating by positive pitch around pitch axis decreases elevation.
349    let pitch = old_elevation - new_elevation;
350    // Remaining azimuth from pitched to new target around yaw axis.
351    let pitched = Quat::from_axis_angle(pitch_axis, pitch) * old_ray;
352    let horizontal = |ray: Vec3| (ray - yaw_axis * ray.dot(yaw_axis)).try_normalize();
353    let yaw = horizontal(pitched)
354        .zip(horizontal(new_ray))
355        .map_or(0.0, |(from, to)| {
356            float::atan2(yaw_axis.dot(from.cross(to)), from.dot(to))
357        });
358    Some((pitch, yaw))
359}