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
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
use crate::general::{
    ClosedDiv, ClosedMul, ClosedNeg, ComplexField, Id, MultiplicativeGroup, MultiplicativeMonoid,
    RealField, SubsetOf, TwoSidedInverse,
};
use crate::linear::{EuclideanSpace, NormedSpace};

// NOTE: A subgroup trait inherit from its parent groups.

/// A general transformation acting on an euclidean space. It may not be inversible.
pub trait Transformation<E: EuclideanSpace>: MultiplicativeMonoid {
    /// Applies this group's action on a point from the euclidean space.
    fn transform_point(&self, pt: &E) -> E;

    /// Applies this group's action on a vector from the euclidean space.
    ///
    /// If `v` is a vector and `a, b` two point such that `v = a - b`, the action `∘` on a vector
    /// is defined as `self ∘ v = (self × a) - (self × b)`.
    fn transform_vector(&self, v: &E::Coordinates) -> E::Coordinates;
}

/// The most general form of invertible transformations on an euclidean space.
pub trait ProjectiveTransformation<E: EuclideanSpace>:
    MultiplicativeGroup + Transformation<E>
{
    /// Applies this group's two_sided_inverse action on a point from the euclidean space.
    fn inverse_transform_point(&self, pt: &E) -> E;

    /// Applies this group's two_sided_inverse action on a vector from the euclidean space.
    ///
    /// If `v` is a vector and `a, b` two point such that `v = a - b`, the action `∘` on a vector
    /// is defined as `self ∘ v = (self × a) - (self × b)`.
    fn inverse_transform_vector(&self, v: &E::Coordinates) -> E::Coordinates;
}

/// The group of affine transformations. They are decomposable into a rotation, a non-uniform
/// scaling, a second rotation, and a translation (applied in that order).
pub trait AffineTransformation<E: EuclideanSpace>: ProjectiveTransformation<E> {
    /// Type of the first rotation to be applied.
    type Rotation: Rotation<E>;
    /// Type of the non-uniform scaling to be applied.
    type NonUniformScaling: AffineTransformation<E>;
    /// The type of the pure translation part of this affine transformation.
    type Translation: Translation<E>;

    /// Decomposes this affine transformation into a rotation followed by a non-uniform scaling,
    /// followed by a rotation, followed by a translation.
    fn decompose(
        &self,
    ) -> (
        Self::Translation,
        Self::Rotation,
        Self::NonUniformScaling,
        Self::Rotation,
    );
    // FIXME: add a `recompose` method?

    /*
     * Composition with components.
     */
    /// Appends a translation to this similarity.
    fn append_translation(&self, t: &Self::Translation) -> Self;

    /// Prepends a translation to this similarity.
    fn prepend_translation(&self, t: &Self::Translation) -> Self;

    /// Appends a rotation to this similarity.
    fn append_rotation(&self, r: &Self::Rotation) -> Self;

    /// Prepends a rotation to this similarity.
    fn prepend_rotation(&self, r: &Self::Rotation) -> Self;

    /// Appends a scaling factor to this similarity.
    fn append_scaling(&self, s: &Self::NonUniformScaling) -> Self;

    /// Prepends a scaling factor to this similarity.
    fn prepend_scaling(&self, s: &Self::NonUniformScaling) -> Self;

    /// Appends to this similarity a rotation centered at the point `p`, i.e., this point is left
    /// invariant.
    ///
    /// May return `None` if `Self` does not have enough translational degree of liberty to perform
    /// this computation.
    #[inline]
    fn append_rotation_wrt_point(&self, r: &Self::Rotation, p: &E) -> Option<Self> {
        if let Some(t) = Self::Translation::from_vector(p.coordinates()) {
            let it = t.two_sided_inverse();
            Some(
                self.append_translation(&it)
                    .append_rotation(&r)
                    .append_translation(&t),
            )
        } else {
            None
        }
    }
}

/// Subgroups of the similarity group `S(n)`, i.e., rotations, translations, and (signed) uniform scaling.
///
/// Similarities map lines to lines and preserve angles.
pub trait Similarity<E: EuclideanSpace>:
    AffineTransformation<E, NonUniformScaling = <Self as Similarity<E>>::Scaling>
{
    /// The type of the pure (uniform) scaling part of this similarity transformation.
    type Scaling: Scaling<E>;

    /*
     * Components retrieval.
     */
    /// The pure translational component of this similarity transformation.
    fn translation(&self) -> Self::Translation;

    /// The pure rotational component of this similarity transformation.
    fn rotation(&self) -> Self::Rotation;

    /// The pure scaling component of this similarity transformation.
    fn scaling(&self) -> Self::Scaling;

    /*
     * Transformations.
     */
    /// Applies this transformation's pure translational part to a point.
    #[inline]
    fn translate_point(&self, pt: &E) -> E {
        self.translation().transform_point(pt)
    }

    /// Applies this transformation's pure rotational part to a point.
    #[inline]
    fn rotate_point(&self, pt: &E) -> E {
        self.rotation().transform_point(pt)
    }

    /// Applies this transformation's pure scaling part to a point.
    #[inline]
    fn scale_point(&self, pt: &E) -> E {
        self.scaling().transform_point(pt)
    }

    /// Applies this transformation's pure rotational part to a vector.
    #[inline]
    fn rotate_vector(&self, pt: &E::Coordinates) -> E::Coordinates {
        self.rotation().transform_vector(pt)
    }

    /// Applies this transformation's pure scaling part to a vector.
    #[inline]
    fn scale_vector(&self, pt: &E::Coordinates) -> E::Coordinates {
        self.scaling().transform_vector(pt)
    }

    /*
     * Inverse transformations.
     */
    /// Applies this transformation inverse's pure translational part to a point.
    #[inline]
    fn inverse_translate_point(&self, pt: &E) -> E {
        self.translation().inverse_transform_point(pt)
    }

    /// Applies this transformation inverse's pure rotational part to a point.
    #[inline]
    fn inverse_rotate_point(&self, pt: &E) -> E {
        self.rotation().inverse_transform_point(pt)
    }

    /// Applies this transformation inverse's pure scaling part to a point.
    #[inline]
    fn inverse_scale_point(&self, pt: &E) -> E {
        self.scaling().inverse_transform_point(pt)
    }

    /// Applies this transformation inverse's pure rotational part to a vector.
    #[inline]
    fn inverse_rotate_vector(&self, pt: &E::Coordinates) -> E::Coordinates {
        self.rotation().inverse_transform_vector(pt)
    }

    /// Applies this transformation inverse's pure scaling part to a vector.
    #[inline]
    fn inverse_scale_vector(&self, pt: &E::Coordinates) -> E::Coordinates {
        self.scaling().inverse_transform_vector(pt)
    }
}

/// Subgroups of the isometry group `E(n)`, i.e., rotations, reflexions, and translations.
pub trait Isometry<E: EuclideanSpace>: Similarity<E, Scaling = Id> {}

/// Subgroups of the orientation-preserving isometry group `SE(n)`, i.e., rotations and translations.
pub trait DirectIsometry<E: EuclideanSpace>: Isometry<E> {}

/// Subgroups of the n-dimensional rotations and scaling `O(n)`.
pub trait OrthogonalTransformation<E: EuclideanSpace>: Isometry<E, Translation = Id> {}

/// Subgroups of the (signed) uniform scaling group.
pub trait Scaling<E: EuclideanSpace>:
    AffineTransformation<E, NonUniformScaling = Self, Translation = Id, Rotation = Id>
    + SubsetOf<E::RealField>
{
    /// Converts this scaling factor to a real. Same as `self.to_superset()`.
    #[inline]
    fn to_real(&self) -> E::RealField {
        self.to_superset()
    }

    /// Attempts to convert a real to an element of this scaling subgroup. Same as
    /// `Self::from_superset()`. Returns `None` if no such scaling is possible for this subgroup.
    #[inline]
    fn from_real(r: E::RealField) -> Option<Self> {
        Self::from_superset(&r)
    }

    /// Raises the scaling to a power. The result must be equivalent to
    /// `self.to_superset().powf(n)`. Returns `None` if the result is not representable by `Self`.
    #[inline]
    fn powf(&self, n: E::RealField) -> Option<Self> {
        Self::from_superset(&self.to_superset().powf(n))
    }

    /// The scaling required to make `a` have the same norm as `b`, i.e., `|b| = |a| * norm_ratio(a,
    /// b)`.
    #[inline]
    fn scale_between(a: &E::Coordinates, b: &E::Coordinates) -> Option<Self> {
        Self::from_superset(&(b.norm() / a.norm()))
    }
}

/// Subgroups of the n-dimensional translation group `T(n)`.
pub trait Translation<E: EuclideanSpace>:
    DirectIsometry<E, Translation = Self, Rotation = Id> /* + SubsetOf<E::Coordinates> */
{
    // NOTE: we must define those two conversions here (instead of just using SubsetOf) because the
    // structure of Self uses the multiplication for composition, while E::Coordinates uses addition.
    // Having a trait that says "remap this operator to this other one" does not seem to be
    // possible without higher kinded traits.
    /// Converts this translation to a vector.
    fn to_vector(&self) -> E::Coordinates;

    /// Attempts to convert a vector to this translation. Returns `None` if the translation
    /// represented by `v` is not part of the translation subgroup represented by `Self`.
    fn from_vector(v: E::Coordinates) -> Option<Self>;

    /// Raises the translation to a power. The result must be equivalent to
    /// `self.to_superset() * n`.  Returns `None` if the result is not representable by `Self`.
    #[inline]
    fn powf(&self, n: E::RealField) -> Option<Self> {
        Self::from_vector(self.to_vector() * n)
    }

    /// The translation needed to make `a` coincide with `b`, i.e., `b = a * translation_to(a, b)`.
    #[inline]
    fn translation_between(a: &E, b: &E) -> Option<Self> {
        Self::from_vector(b.clone() - a.clone())
    }
}

/// Subgroups of the n-dimensional rotation group `SO(n)`.
pub trait Rotation<E: EuclideanSpace>:
    OrthogonalTransformation<E, Rotation = Self> + DirectIsometry<E, Rotation = Self>
{
    /// Raises this rotation to a power. If this is a simple rotation, the result must be
    /// equivalent to multiplying the rotation angle by `n`.
    fn powf(&self, n: E::RealField) -> Option<Self>;

    /// Computes a simple rotation that makes the angle between `a` and `b` equal to zero, i.e.,
    /// `b.angle(a * delta_rotation(a, b)) = 0`. If `a` and `b` are collinear, the computed
    /// rotation may not be unique. Returns `None` if no such simple rotation exists in the
    /// subgroup represented by `Self`.
    fn rotation_between(a: &E::Coordinates, b: &E::Coordinates) -> Option<Self>;

    /// Computes the rotation between `a` and `b` and raises it to the power `n`.
    ///
    /// This is equivalent to calling `self.rotation_between(a, b)` followed by `.powf(n)` but will
    /// usually be much more efficient.
    #[inline]
    fn scaled_rotation_between(
        a: &E::Coordinates,
        b: &E::Coordinates,
        s: E::RealField,
    ) -> Option<Self>;

    // FIXME: add a function that computes the rotation with the axis orthogonal to Span(a, b) and
    // with angle equal to `n`?
}

/*
 *
 * Implementation for floats.
 *
 */

impl<R, E> Transformation<E> for R
where
    R: RealField,
    E: EuclideanSpace<RealField = R>,
    E::Coordinates: ClosedMul<R> + ClosedDiv<R> + ClosedNeg,
{
    #[inline]
    fn transform_point(&self, pt: &E) -> E {
        pt.scale_by(*self)
    }

    #[inline]
    fn transform_vector(&self, v: &E::Coordinates) -> E::Coordinates {
        v.clone() * *self
    }
}

impl<R, E> ProjectiveTransformation<E> for R
where
    R: RealField,
    E: EuclideanSpace<RealField = R>,
    E::Coordinates: ClosedMul<R> + ClosedDiv<R> + ClosedNeg,
{
    #[inline]
    fn inverse_transform_point(&self, pt: &E) -> E {
        assert!(*self != R::zero());
        pt.scale_by(R::one() / *self)
    }

    #[inline]
    fn inverse_transform_vector(&self, v: &E::Coordinates) -> E::Coordinates {
        assert!(*self != R::zero());
        v.clone() * (R::one() / *self)
    }
}

impl<R, E> AffineTransformation<E> for R
where
    R: RealField,
    E: EuclideanSpace<RealField = R>,
    E::Coordinates: ClosedMul<R> + ClosedDiv<R> + ClosedNeg,
{
    type Rotation = Id;
    type NonUniformScaling = R;
    type Translation = Id;

    #[inline]
    fn decompose(&self) -> (Id, Id, R, Id) {
        (Id::new(), Id::new(), *self, Id::new())
    }

    #[inline]
    fn append_translation(&self, _: &Self::Translation) -> Self {
        *self
    }

    #[inline]
    fn prepend_translation(&self, _: &Self::Translation) -> Self {
        *self
    }

    #[inline]
    fn append_rotation(&self, _: &Self::Rotation) -> Self {
        *self
    }

    #[inline]
    fn prepend_rotation(&self, _: &Self::Rotation) -> Self {
        *self
    }

    #[inline]
    fn append_scaling(&self, s: &Self::NonUniformScaling) -> Self {
        *s * *self
    }

    #[inline]
    fn prepend_scaling(&self, s: &Self::NonUniformScaling) -> Self {
        *self * *s
    }
}

impl<R, E> Scaling<E> for R
where
    R: RealField + SubsetOf<R>,
    E: EuclideanSpace<RealField = R>,
    E::Coordinates: ClosedMul<R> + ClosedDiv<R> + ClosedNeg,
{
    #[inline]
    fn to_real(&self) -> E::RealField {
        *self
    }

    #[inline]
    fn from_real(r: E::RealField) -> Option<Self> {
        Some(r)
    }

    #[inline]
    fn powf(&self, n: E::RealField) -> Option<Self> {
        Some(n.powf(n))
    }

    #[inline]
    fn scale_between(a: &E::Coordinates, b: &E::Coordinates) -> Option<Self> {
        Some(b.norm() / a.norm())
    }
}

impl<R, E> Similarity<E> for R
where
    R: RealField + SubsetOf<R>,
    E: EuclideanSpace<RealField = R>,
    E::Coordinates: ClosedMul<R> + ClosedDiv<R> + ClosedNeg,
{
    type Scaling = R;

    fn translation(&self) -> Self::Translation {
        Id::new()
    }

    fn rotation(&self) -> Self::Rotation {
        Id::new()
    }

    fn scaling(&self) -> Self::Scaling {
        *self
    }
}