"align" function that derives transformation between a reference frame and a target frame in CGA

[CaseySanchez]

Hello Dr. Fernandes,

In episode 1 of his SIBGRAPI 2021 PGA video series, Enki (creator of BiVector.net and ganja.js) describes how to create an align function that aligns a reference frame with a target frame, which are arrays consisting of equal quantities of points. This function serves as an analogue to the gluLookAt function (https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml/gluLookAt.xml), but can take any number of points to create the transformation.

Here is the timestamped video link:
https://www.youtube.com/watch?v=pq9YfdPHhIo&t=1334s

Below is the CGA-equivalent ganja.js example that he has provided:
https://enkimute.github.io/ganja.js/examples/coffeeshop.html#IqKUeyUhu

I've attempted to get something similar to work in GATL using ga3c, but the only way I could think was to use full_multivector_t (which I am sure results in many redundant operations) as follows:

#include <tuple>

#include <gatl/ga3c.hpp>

using namespace ga3c;

template <typename CoefficientType, typename Expression>
constexpr auto make_conformal_point(clifford_expression<CoefficientType, Expression> const &euclidean_point)
{
    return euclidean_point + no + 0.5 * euclidean_point * euclidean_point * ni;
}

template <typename CoefficientType, typename Expression>
constexpr auto sqrt(clifford_expression<CoefficientType, Expression> const &multivector)
{
    return unit(1.0 + multivector);
}

template <typename CoefficientType, typename FromExpression, typename ToExpression>
constexpr auto inv_transform(clifford_expression<CoefficientType, FromExpression> const &from, clifford_expression<CoefficientType, ToExpression> const &to)
{
    return sqrt(to * inv(from));
}

template <typename CoefficientType, typename FromExpression, typename ToExpression>
constexpr void align(clifford_expression<CoefficientType, FromExpression> const &from, clifford_expression<CoefficientType, ToExpression> const &to, full_multivector_t<CoefficientType, space.vector_space_dimensions> &P, full_multivector_t<CoefficientType, space.vector_space_dimensions> &Q, full_multivector_t<CoefficientType, space.vector_space_dimensions> &M)
{
    P = Q ^ apply_even_versor(M, from);
    Q = Q ^ to;
    M = inv_transform(P, Q) * M;
}

template <typename CoefficientType, typename ...FromExpressions, typename ...ToExpressions, std::size_t ...Indices>
constexpr auto align(std::tuple<clifford_expression<CoefficientType, FromExpressions>...> const &from, std::tuple<clifford_expression<CoefficientType, ToExpressions>...> const &to, std::index_sequence<Indices...>)
{
    full_multivector_t<CoefficientType, space.vector_space_dimensions> P = ni;
    full_multivector_t<CoefficientType, space.vector_space_dimensions> Q = ni;
    full_multivector_t<CoefficientType, space.vector_space_dimensions> M = dual(I);

    (align(std::get<Indices>(from), std::get<Indices>(to), P, Q, M), ...);

    return M;
}

template <typename CoefficientType, typename ...FromExpressions, typename ...ToExpressions>
constexpr auto align(std::tuple<clifford_expression<CoefficientType, FromExpressions>...> const &from, std::tuple<clifford_expression<CoefficientType, ToExpressions>...> const &to)
{
    static_assert(sizeof...(FromExpressions) == sizeof...(ToExpressions));

    return align(from, to, std::make_index_sequence<sizeof...(FromExpressions)>{});
}

int main(int argc, char **argv)
{
    auto const from = std::make_tuple(1.0 * no, make_conformal_point(1.0 * e1), make_conformal_point(1.0 * e2));
    auto const to = std::make_tuple(1.0 * no, make_conformal_point(0.707 * e1 + 0.707 * e3), make_conformal_point(0.707 * e2 + 0.707 * e3));

    auto const aligned = align(from, to);

    std::cout << aligned << std::endl;

    return 0;
}

The problem is that this completely overwhelms the compiler and it never completes with the following output:

c++: fatal error: Killed signal terminated program cc1plus
compilation terminated.

I am by no means a template wizard, and perhaps that is obvious in my attempt. Do you have any suggestions to get this align method working (preferably without using full_multivector_t)?

Kind regards,
Casey

[CaseySanchez]

I got it working Dr. Fernandes. Any suggestions to improve the efficiency of this method would be greatly appreciated.

#include <tuple>

#include <gatl/ga3c.hpp>

using namespace ga3c;

template <size_t Index, typename CoefficientType, typename ...FromExpressions, typename ...ToExpressions, typename MotorExpression, typename ToOpExpression>
constexpr full_multivector_t<CoefficientType, space.vector_space_dimensions> align(std::tuple<clifford_expression<CoefficientType, FromExpressions>...> const &from, std::tuple<clifford_expression<CoefficientType, ToExpressions>...> const &to, clifford_expression<CoefficientType, MotorExpression> const &motor_previous, clifford_expression<CoefficientType, ToOpExpression> const &to_op_previous)
{
    if constexpr (Index < sizeof...(FromExpressions)) {
        auto const from_op = to_op_previous ^ apply_even_versor(motor_previous, std::get<Index>(from));
        auto const to_op = to_op_previous ^ std::get<Index>(to);
        
        return align<Index + 1>(from, to, unit(static_cast<CoefficientType>(1.0) + unit(to_op) * inv(unit(from_op))) * motor_previous, to_op);
    }

    return motor_previous;
}

template <typename CoefficientType, typename ...FromExpressions, typename ...ToExpressions>
constexpr auto align(std::tuple<clifford_expression<CoefficientType, FromExpressions>...> const &from, std::tuple<clifford_expression<CoefficientType, ToExpressions>...> const &to)
{
    static_assert(sizeof...(FromExpressions) == sizeof...(ToExpressions));

    return align<0>(from, to, static_cast<CoefficientType>(1.0) * dual(I), static_cast<CoefficientType>(1.0) * ni);
}

int main(int argc, char **argv)
{
    auto const from = std::make_tuple(1.0 * no, point(1.0, 0.0, 0.0), point(0.0, 1.0, 0.0));
    auto const to = std::make_tuple(1.0 * no, point(0.707, 0.0, 0.707), point(0.0, 0.707, 0.707));

    auto const aligned = align(from, to);

    std::cout << "aligned = " << aligned << std::endl;
    
    return 0;
}

Regards,
Casey

[laffernandes]

Sorry about my late response. I'm swamped with work.

I haven't checked that the code is correct for the following comments. The comments are related to GATL and the use of C++ templates.

When you multiply something by 1.0 (like in 1.0 * ni), the compiler cannot tell the templates that 1.0 is the constant value 1. Any literal value is handled as a runtime value. It is well known C++ issue. So, the lazy evaluation approach of GATL cannot simplify the expression. The only way to hangle literal values as constants during expression simplification is by declaring them with c<value>. In 1.0 * ni, thec<1> * ni is unnecessary and can be simplified to ni.

You don't have to use full_multivector_t. Actually, with GATL, it is better to avoid setting the return type and use auto instead.

The coefficient types of function arguments can be different. So, stop forcing all coefficients to be the same type and let GATL find the best choice for your expression.

The last code sent by you defines a recursive template function. It is difficult to follow and can be written more simply without recursion. Below I present the code equivalent to your solution.

#include <tuple>
#include <gatl/ga3c.hpp>

using namespace ga3c;

template <typename ...FromCoefficientType, typename ...FromExpressions, typename ...ToCoefficientType, typename ...ToExpressions>
constexpr auto align(std::tuple<clifford_expression<FromCoefficientType, FromExpressions>...> const &from, std::tuple<clifford_expression<ToCoefficientType, ToExpressions>...> const &to)
{
    auto from_op1 = ni ^ apply_even_versor(dual(I), std::get<0>(from));
    auto to_op1 = ni ^ std::get<0>(to);
    
    auto motor_previous1 = unit(c<1> + unit(to_op1) * inv(unit(from_op1))) * dual(I);
    auto from_op2 = to_op1 ^ apply_even_versor(motor_previous1, std::get<1>(from));
    auto to_op2 = to_op1 ^ std::get<1>(to);
    
    auto motor_previous2 = unit(c<1> + unit(to_op2) * inv(unit(from_op2))) * motor_previous1;
    auto from_op3 = to_op2 ^ apply_even_versor(motor_previous2, std::get<2>(from));
    auto to_op3 = to_op2 ^ std::get<2>(to);
    
    return unit(c<1> + unit(to_op3) * inv(unit(from_op3))) * motor_previous2;
}

int main(int argc, char **argv)
{
    auto const from = std::make_tuple(no, point(1.0, 0.0, 0.0), point(0.0, 1.0, 0.0));
    auto const to = std::make_tuple(no, point(0.707, 0.0, 0.707), point(0.0, 0.707, 0.707));

    auto const aligned = align(from, to);

    std::cout << "aligned = " << aligned << std::endl;
    
    return 0;
}

[CaseySanchez]

The recursion was deliberate because it can be used to align frames consisting of more than 3 points, but this comes with the downside that the function cannot have a return type of auto to avoid the redundancy of full_multivector_t. I was hoping that there would be a way around this.

Thank you kindly for the information pertaining to the use of c<value> and lazy evaluation in GATL.

By the way, Enki had mentioned that he was going to update the /lib section of BiVector.net here soon to include your library, among others! It is certainly deserving of recognition.

[laffernandes]

If the recursion is necessary for handling the n-D case, then the full_multivector_t can be avoided by using a single return in the recursive align function and specializing a template align function overload to handle the last call. Unfortunately, C++ does not implement partial template specialization for functions. The workaround, in that case, is to use a template struct like this:

#include <tuple>
#include <gatl/ga3c.hpp>

using namespace ga3c;

template<size_t Index>
struct _recursive_align
{
    template<typename ...FromCoefficientType, typename ...FromExpressions, typename ...ToCoefficientType, typename ...ToExpressions>
    constexpr static auto run(std::tuple<clifford_expression<FromCoefficientType, FromExpressions>...> const &from, std::tuple<clifford_expression<ToCoefficientType, ToExpressions>...> const &to)
    {
        auto [motor_previous, to_op_previous] = _recursive_align<Index - 1>::run(from, to);
        auto from_op = to_op_previous ^ apply_even_versor(motor_previous, std::get<Index>(from));
        auto to_op = to_op_previous ^ std::get<Index>(to);
        return std::make_tuple(unit(c<1> + unit(to_op) * inv(unit(from_op))) * motor_previous, to_op);
    }
};

template<>
struct _recursive_align<0>
{
    template<typename ...FromCoefficientType, typename ...FromExpressions, typename ...ToCoefficientType, typename ...ToExpressions>
    constexpr static auto run(std::tuple<clifford_expression<FromCoefficientType, FromExpressions>...> const &from, std::tuple<clifford_expression<ToCoefficientType, ToExpressions>...> const &to)
    {
        auto from_op = ni ^ apply_even_versor(dual(I), std::get<0>(from));
        auto to_op = ni ^ std::get<0>(to);
        return std::make_tuple(unit(c<1> + unit(to_op) * inv(unit(from_op))) * dual(I), to_op);
    }
};

template <typename ...FromCoefficientType, typename ...FromExpressions, typename ...ToCoefficientType, typename ...ToExpressions>
constexpr auto align(std::tuple<clifford_expression<FromCoefficientType, FromExpressions>...> const &from, std::tuple<clifford_expression<ToCoefficientType, ToExpressions>...> const &to)
{
    static_assert(sizeof...(FromExpressions) == sizeof...(ToExpressions));
    auto [motor, _] = _recursive_align<sizeof...(FromExpressions) - 1>::run(from, to);
    return motor;
}

int main(int argc, char **argv)
{
    auto const from = std::make_tuple(no, point(1.0, 0.0, 0.0), point(0.0, 1.0, 0.0));
    auto const to = std::make_tuple(no, point(0.707, 0.0, 0.707), point(0.0, 0.707, 0.707));

    auto const aligned = align(from, to);
    std::cout << "aligned = " << aligned << std::endl;
    
    return 0;
}

Notice that I am decrementing the index so that we have the last recursive call indexed by 0. By incrementing the index we can not state the index of the last call while specializing the template struct.

[CaseySanchez]

This is excellent! Thank you so much Dr. Fernandes, I am learning so much.