P(R*_{3, 0, 1}) specialized SIMD Geometric Algebra Library

Overview

Klein

License: MIT DOI

Build Status Build Status Coverity Status Codacy Badge

๐Ÿ‘‰ ๐Ÿ‘‰ Project Site ๐Ÿ‘ˆ ๐Ÿ‘ˆ

Description

Do you need to do any of the following? Quickly? Really quickly even?

  • Projecting points onto lines, lines to planes, points to planes?
  • Measuring distances and angles between points, lines, and planes?
  • Rotate or translate points, lines, and planes?
  • Perform smooth rigid body transforms? Interpolate them smoothly?
  • Construct lines from points? Planes from points? Planes from a line and a point?
  • Intersect planes to form lines? Intersect a planes and lines to form points?

If so, then Klein is the library for you!

Klein is an implementation of P(R*_{3, 0, 1}), aka 3D Projective Geometric Algebra. It is designed for applications that demand high-throughput (animation libraries, kinematic solvers, etc). In contrast to other GA libraries, Klein does not attempt to generalize the metric or dimensionality of the space. In exchange for this loss of generality, Klein implements the algebraic operations using the full weight of SSE (Streaming SIMD Extensions) for maximum throughput.

Requirements

  • Machine with a processor that supports SSE3 or later (Steam hardware survey reports 100% market penetration)
  • C++11/14/17 compliant compiler (tested with GCC 9.2.1, Clang 9.0.1, and Visual Studio 2019)
  • Optional SSE4.1 support

Usage

You have two options to use Klein in your codebase. First, you can simply copy the contents of the public folder somewhere in your include path. Alternatively, you can include this entire project in your source tree, and using cmake, add_subdirectory(Klein) and link the klein::klein interface target.

In your code, there is a single header to include via #include <klein/klein.hpp>, at which point you can create planes, points, lines, ideal lines, bivectors, motors, directions, and use their operations. Please refer to the project site for the most up-to-date documentation.

Motivation

PGA fully streamlines traditionally used quaternions, and dual-quaternions in a single algebra. Normally, the onus is on the user to perform appropriate casts and ensure signs and memory layout are accounted for. Here, all types are unified within the geometric algebra, and operations such as applying quaternion or dual-quaternions (rotor/motor) to planes, points, and lines make sense. There is a surprising amount of uniformity in the algebra, which enables efficient implementation, a simple API, and reduced code size.

Performance Considerations

It is known that a "better" way to vectorize computation in general is to arrange the data in an SoA layout to avoid unnecessary cross-lane arithmetic or unnecessary shuffling. PGA is unique in that a given PGA multivector has a natural decomposition into 4 blocks of 4 floating-point quantities. For the even sub-algebra (isomorphic to the space of dual-quaternions) also known as the motor algebra, the geometric product can be densely packed and implemented efficiently using SSE.

References

Klein is deeply indebted to several members of the GA community and their work. Beyond the works cited here, the author stands of the shoulders of giants (Felix Klein, Sophus Lie, Arthur Cayley, William Rowan Hamilton, Julius Plรผcker, and William Kingdon Clifford, among others).

[1] Gunn, Charles G. (2019). Course notes Geometric Algebra for Computer Graphics, SIGGRAPH 2019. arXiv link

[2] Steven De Keninck and Charles Gunn. (2019). SIGGRAPH 2019 Geometric Algebra Course. youtube link

[3] Leo Dorst, Daniel Fontijne, Stephen Mann. (2007) Geometric Algebra for Computer Science. Burlington, MA: Morgan Kaufmann Publishers Inc.

Issues
  • [QUESTION] What are the orientations of the basis elements?

    [QUESTION] What are the orientations of the basis elements?

    In your PGA library, I guess the e1, e2, e3 basis elements correspond to the YZ, ZX and XY planes (so the planes x=0, y=0, z=0). Is that correct? Is the orientation also correct, e.g. e1 has orientation Y-direction towards Z-direction, e2 Z to X, and e3 X to Y?

    And I guess e0 corresponds to the "plane at infinity" (w=0). Is it possible to also assign/visualize an orientation to e0? For example, when I'm looking at e0 along any direction vector (imagining e0 are the "stars" on a "sphere at infinity") does it have a clockwise or counter-clockwise orientation?

    I'm porting your code to C#, and I'm trying to add some more comments to the code, but I don't fully understand PGA yet... I'm re-reading Charles Gunns SIGGRAPH paper to get a grip on it.

    Maybe I should ask these questions on the bivector.net forum or discord?

    opened by ziriax 5
  • Log of a motor representing a translator

    Log of a motor representing a translator

    Testing an example of blending with Motors of PGA and I got nan as a result. Here is a sample code:

    	float W[] = {0.2f,0.1f,0.3f};
    
    	kln::motor M0(kln::translator(10.0f,1.0f,0.0f,0.0f)); 
    	kln::motor M1(kln::rotor(3.1416, 1.0f, 0.0, 0.0f));
    	kln::motor M2(kln::rotor(1.0472, 0.0f, 1.0f, 0.0f));
    
            // removing W[0]*kln::log(M0) is OK
    	kln::line blendedLine = W[0]*kln::log(M0) + W[1]*kln::log(M1) + W[2]*kln::log(M2) ;
    
    	kln::motor blended_Motor = kln::exp(blendedLine); 
            std::cout << blended_Motor(kln::point(0.0f,0.0f,0.0f)).x()<<std::endl;
    

    It might come from the fact that the log of translator results in an ideal line whereas the log of a motor is a real line in general.

    opened by sbreuils 4
  • Tests failed in Visual Studio 2019

    Tests failed in Visual Studio 2019

    Well. I built the tests without any problem in environment Windows 10 x64 with Microsoft Visual Studio 2019.

    By running them some are successfully passed on. For example, sym_test.exe.

    image

    However there are problems with klein_test.exe

    image

    DJuego

    opened by DJuego 4
  • Is branch a term for a line passing through the origin?

    Is branch a term for a line passing through the origin?

    Hi @jeremyong, nice library!

    Is branch generally accepted term for a line passing through the origin, or a name you chose? I couldn't find a wider confirmation of the term..

    opened by benhutchison 3
  • Bug in `motor::operator=(translator t)`

    Bug in `motor::operator=(translator t)`

    I believe there is a bug in this code:

        motor& KLN_VEC_CALL operator=(translator t) noexcept
        {
            p1_ = _mm_setzero_ps();
            p2_ = t.p2_;
            return *this;
        }
    

    The rotator p1_ should be set to identity instead of zero.

    opened by Danvil 2
  • Feature/cmake config package

    Feature/cmake config package

    Set CMake project version to 2.3.0 Setting the version of the project will enable creating a CMake package version file.

    Add a new option KLEIN_INSTALL. When this option is enabled, then a CMake config-file package will be created during the install step. By default, this option is set to ON for standalone projects. Otherwise, the option is set of OFF.

    The header files will be installed into include/klein. Therefore, the include directory of the exported targets should be include (i.e. $<INSTALL_INTERFACE:include>). To distinguish this from the include directories during a build we use the BUILD_INTERFACE generator expression (e.g. $<BUILD_INTERFACE:${CMAKE_CURRENT_SOURCE_DIR}/public>).

    if KLEIN_INSTALL is set to ON, then the targets are installed and the CMake config-file package is created. Other CMake projects can then search for the package using e.g. find_package(Klein 2.3.0).

    klein-config.cmake will be executed by other projects when using find_package. Since klein depends on the simde headers, the CMake file will try to find these headers and add them to klein targets include directories.

    opened by JPMMaia 2
  • FetchContent error

    FetchContent error

    I get an error while running the CMake configure step in a fresh copy of the repository:

    Creating directories for 'simde-populate'
      Performing download step (git clone) for 'simde-populate'
      Cloning into 'simde-src'...
      fatal: reference is not a tree: df63f88a364da6be3963b4924c327b12f88d7748
      CMake Error at simde-subbuild/simde-populate-prefix/tmp/simde-populate-gitclone.cmake:40 (message):
        Failed to checkout tag: 'df63f88a364da6be3963b4924c327b12f88d7748'
    

    Steps to reproduce:

    git clone [email protected]:jeremyong/klein.git
    cd klein
    cmake -B build -S .
    

    Possible fix:

    Modifying CMakeLists.txt#L35 from GIT_SHALLOW ON to GIT_SHALLOW OFF solves the issue. I'm not sure if that's the correct approach though.

    opened by JPMMaia 2
  • Question about scaling

    Question about scaling

    Hi, I've recently become interested in PGA, and am considering using it in a new Python render engine. Math (especially this kind) is not my strong suit, but the advantages of PGA are compelling .... so I'm trying to wrap this up in a Python lib with an API suited for normal people :)

    I'm now a bit stuck and I was hoping you could help. Render engines and 3D modeling tools usually provide 3 kinds of transforms for an object: translations, rotations, and scaling. I understand (more or less) how rotors and translators work, but I have not seen the use of scalors (if that's how you'd call them) anywhere. Is a scaling transform/motor even possible? What about anisotropic scaling?

    edit: if there's a better place to ask questions like these, please let me know, and I'll move the question there instead

    opened by almarklein 2
  • invalid plane::normalized function implementation

    invalid plane::normalized function implementation

    class plane final {
    ...
        [[nodiscard]] plane normalized() const noexcept
        {
            plane out;
            out.normalize();
            return out;
        }
    ...
    };
    

    is missing an assignment. Should be:

    class plane final {
    ...
        [[nodiscard]] plane normalized() const noexcept
        {
            plane out = *this;
            out.normalize();
            return out;
        }
    ...
    };
    
    opened by radoslawcybulski 2
  • [QUESTION] No general multivector class?

    [QUESTION] No general multivector class?

    I noticed that Klein doesn't have a multivector class (besides the one in the parser for testing).

    Did you pick all the operators in such a way that a multivector is never an output?

    If so, there must be things that cannot be done with Klein, or, maybe multi vectors are not needed for practical tasks?

    Thanks again.

    opened by ziriax 2
  • Klein 2.0 API changes inbound

    Klein 2.0 API changes inbound

    I hate breaking compatibility. Especially frequently. This issue is my attempt to explain what the issue is, what Iโ€™m doing to fix it, and what assurances can be afforded about API breakages in the future.

    First, the issues:

    1. On some compilers, inheritance is causing subclasses of entity to be passed on the stack instead of in registers.
    2. On some compilers, branch optimization limits are being hit causing certain loops over constexpr variables to not get optimized out at runtime.

    For Klein whose primary goal is realtime PGA, both of these problems are unacceptable. As a result, the entity base class needs to go. This will have the following consequences:

    1. Implicit conversions using the entity as a medium will go away. All conversions will be explicit
    2. Because of (1), most operators will move to separate headers (one per operation) to avoid circular dependencies while maintaining type safety
    3. All the underlying implementation structure will remain the same.

    As for testing, I have vetted that the changes outlined above solve all the issues mentioned and checked assembly/perf against all major compilers. All that remains is to finalize the implementation. The internal SSE code does not need to be changed as it is just the โ€œouter shellโ€ that has this problem. Personally, I much prefer the new API, but it is nevertheless a breaking change. As a result, Klein will get a 2.0 label despite the 1.0 being released relatively recently.

    Feel free to comment with suggestions or feedback below.

    opened by jeremyong 2
  • Add casts for constants to get rid of double -> float warnings

    Add casts for constants to get rid of double -> float warnings

    There's plenty of warnings (at least when compliling under vs, i'd assume clang will print those as well). This PR adds explicit casts to fix this issue.

    opened by radoslawcybulski 1
  • Normalizing a plane with norm = 1 changes its values

    Normalizing a plane with norm = 1 changes its values

    Hi, i am using your library on Windows x64 with MSVC 2022.

    When normalizing a plane which already has a eucl. norm of 1, its value changes. The following test fails if I run it with your other tests in test/test_metric.cpp:

    TEST_CASE("normalized-plane-normalization")
    {
        point a{-0.5, 2, -0.5};
        point b{+0.5, 2, -0.5};
        point c{+0.5, 2, +0.5};
    
        // p is already normalized
        plane p = a & b & c;
        CHECK_EQ(p.norm(), 1);
        CHECK_EQ(p.e0(), -2);
        CHECK_EQ(p.e1(), 0);
        CHECK_EQ(p.e2(), 1);
        CHECK_EQ(p.e3(), 0);
    
        p.normalize();
        // same checks as before
        CHECK_EQ(p.norm(), 1);
        CHECK_EQ(p.e0(), -2);                 // <------- error here, expansion: -4.0f, -2
        CHECK_EQ(p.e1(), 0);
        CHECK_EQ(p.e2(), 1);
        CHECK_EQ(p.e3(), 0);
    }
    

    Using the debugger i found out that the value of p after the normalize() call is kln::point{p0_=(-4, 0, 1, 0)}. Is this intended behaviour? (I am still learning PGA)

    opened by jessestricker 0
  • Typo in the projection of a point to plane

    Typo in the projection of a point to plane

    There was a simple typo in the description of a point to a plane. The product should have been (p dot P)p where p is the plane, P is the point. In the description, the math is correct, except for the labeling of the second term in the geometric product.

    opened by JHonaker 1
  • vcpkg integration

    vcpkg integration

    Hi!

    I am using vcpkg to manage dependencies on a project and I was wondering if I could use vcpkg to include klein in my project.

    So I wrote a port file and made some changes to klein's CMakeLists.txt so that it creates a config package when running CMake install. Packages created this way can be included in other CMake projects by using:

    find_package(klein 2.3.0 REQUIRED) // Version 2.3.0 is used as an example here
    target_link_libraries(app PRIVATE klein::klein) // Other available targets are klein::klein_cxx11 and klein::klein_sse42
    

    I was wondering if you would find these changes interesting and worth adding to the project. The changes can be seen in create-config-package.zip. I can open a pull request with the changes if you are interested.

    opened by JPMMaia 5
  • Problem with precision in Euler Angles.

    Problem with precision in Euler Angles.

    I am working with Microsoft Visual Studio 2019 16.6.1 in Windows 10 x64 environment.

    Well. There seems to be some problem in the numerical accuracy of Euler's new angle conversion feature.

    For instance; When I convert, for example, roll=90ยบ ,pitch=90ยบ, yaw=0ยบ to rotor, I get in rotor: roll=0ยบ, pitch=89.972ยบ, yaw=0ยบ.I find a noticeable difference between 90ยบ and 89,972ยบ (0.028ยบ) that can build up too quickly.

    #include <klein/public/klein/klein.hpp>
    
    #include <cmath>
    #include <iostream>
    
    const float M_PI = 3.141592653589793238462643383279502884; /* pi */
    
    int main()
    {
    	float roll_1 = 90.0;
    	float pitch_1 = 90.0;
    	float yaw_1 = 0.0;
    
    	std::cout << "INPUT: roll: " << roll_1 << " pitch: " << pitch_1 << " yaw: " << yaw_1 << std::endl;
    
    	kln::euler_angles ea_1;
    	ea_1.roll = roll_1 * (M_PI / 180.0f);
    	ea_1.yaw = yaw_1 * (M_PI / 180.0f);
    	ea_1.pitch = pitch_1 * (M_PI / 180.0f);
    
    	kln::rotor r;
    	r = kln::rotor(ea_1);
    	kln::euler_angles ea_2 = r.as_euler_angles();
    	
    	float roll_2 = ea_2.roll * (180.0f / M_PI);
    	float yaw_2 = ea_2.yaw * (180.0f / M_PI);
    	float pitch_2 = ea_2.pitch * (180.0f / M_PI);
    
    	std::cout << "OUTPUT: roll: " << roll_2 << " pitch: " << pitch_2 << " yaw: " << yaw_2 << std::endl;
    	return 0;
    }
    

    I get:

    INPUT: roll: 90 pitch: 90 yaw: 0
    OUTPUT: roll: 0 pitch: 89.972 yaw: 0
    

    DJuego

    opened by DJuego 6
Releases(v2.2.1)
  • v2.2.1(Mar 15, 2020)

  • v2.2(Mar 13, 2020)

    • Addresses an incorrect implicit conversion from translators to motors.
    • Implements a number of optimizations were added for reflections through planes.
    • Adds a division operator (inverses defined with respect to the geometric product.
    Source code(tar.gz)
    Source code(zip)
  • v2.1(Mar 9, 2020)

    This version adds a number of QoL improvements as well as improvements to precision for a nominal cycle cost:

    1. The kln::sqrt free function is available and accepts as its argument kln::rotor, kln::branch, kln::translator, and kln::motor. The function returns the quantity x such that x*x is equal to the argument to within a good approximation.
    2. Motors can now be multiplied by rotors and translators to produce new motors containing the composite action. This was an oversight from the existing API.
    3. Line normalization was fixed so that l * ~l properly produces unity.
    4. Additional helper routines have been added to compute rcp, sqrt, and rsqrt to ~22 bits of accuracy.
    Source code(tar.gz)
    Source code(zip)
  • v2.0(Mar 4, 2020)

    New semantic release due to breaking compatibility.

    • Entity type has been removed due to compiler inability to properly constant-fold interior expressions.
    • Operators have been promoted to first-order types.
    • A number of operators have been specialized for various types for improved throughput/latency.
    • Perf analysis has been updated.
    • Motors can now be constructed from a screw axis, angle, and displacement.
    • A preliminary dual number type as been added.
    • The exp/log methods have been promoted to free functions and now have strongly typed return values.
    • The project function has been added to simplify various projections.

    Some operations that were previously permitted are no longer supported due to a fully general underlying "multivector" class (formerly known as entity<PMask>). Operation overloads are now added individually. This enables another class of optimizations because type safety ensures that certain components of SSE registers are exactly 0.

    Summarizing:

    • Compile times reduced due to very minimal usage of templates and constexpr branches
    • Speed improvements in most situations
    • Increased type safety in a number of situations
    Source code(tar.gz)
    Source code(zip)
  • v1.1(Feb 29, 2020)

  • v1.0(Feb 26, 2020)

    v1.0 comes after extensive testing and performance verification, in addition to shoring up API consistencies in a number of respects. After this release, future releases will be versioned semantically.

    Source code(tar.gz)
    Source code(zip)
  • v0.4(Feb 24, 2020)

    Hurtling toward a 1.0. This release stabilizes the entity memory layout, constructors, and adds a few missing operations (plane normalization, rotor exp/log).

    Source code(tar.gz)
    Source code(zip)
  • v0.3(Feb 20, 2020)

    This release addresses a few API gaps, most notably:

    • Rotor application on lines (bivectors)
    • Motor application on lines (bivectors)
    • Translator application on lines (bivectors)
    • Rotor and motor applications on directions

    Motor conjugation of a direction is implemented in terms of a rotor conjugation due to the translational invariance of the direction application.

    Source code(tar.gz)
    Source code(zip)
  • v0.2(Feb 19, 2020)

    This release adds all primary operations expected in a typical GA library including the symmetric product, exterior product, regressive product, and various SSE-optimized conjugation operators.

    Source code(tar.gz)
    Source code(zip)
  • v0.1(Feb 15, 2020)

Owner
Jeremy Ong
Principal Engineer at Warner Bros. Primary interests: Rendering/graphics Machine learning/AI Networking Low-level optimization/performance tuning
Jeremy Ong
Linear Algebra in C

Linear Algebra in C Quick Start Grab la.h and use it as an stb-style header-only library. For more info on such libraries see: https://github.com/noth

Tsoding 65 Jun 4, 2022
SIMD Vector Classes for C++

You may be interested in switching to std-simd. Features present in Vc 1.4 and not present in std-simd will eventually turn into Vc 2.0, which then de

null 1.2k Jun 23, 2022
Artistic creativity, accelerated with SIMD.

Link the YouTube video demonstration: https://www.youtube.com/watch?v=Bjwml32dxhU The compression algorithm does not work well on this colorful video,

Long Nguyen 17 Mar 16, 2022
SIMD (SSE) implementation of the infamous Fast Inverse Square Root algorithm from Quake III Arena.

simd_fastinvsqrt SIMD (SSE) implementation of the infamous Fast Inverse Square Root algorithm from Quake III Arena. Why Why not. How This video explai

Liam 7 Jan 28, 2022
MIRACL Cryptographic SDK: Multiprecision Integer and Rational Arithmetic Cryptographic Library is a C software library that is widely regarded by developers as the gold standard open source SDK for elliptic curve cryptography (ECC).

MIRACL What is MIRACL? Multiprecision Integer and Rational Arithmetic Cryptographic Library โ€“ the MIRACL Crypto SDK โ€“ is a C software library that is

MIRACL 482 Jun 24, 2022
A C library for statistical and scientific computing

Apophenia is an open statistical library for working with data sets and statistical or simulation models. It provides functions on the same level as t

null 184 Jun 17, 2022
linalg.h is a single header, public domain, short vector math library for C++

linalg.h linalg.h is a single header, public domain, short vector math library for C++. It is inspired by the syntax of popular shading and compute la

Sterling Orsten 724 Jun 23, 2022
LibTomMath is a free open source portable number theoretic multiple-precision integer library written entirely in C.

libtommath This is the git repository for LibTomMath, a free open source portable number theoretic multiple-precision integer (MPI) library written en

libtom 520 Jun 25, 2022
a lean linear math library, aimed at graphics programming. Supports vec3, vec4, mat4x4 and quaternions

linmath.h -- A small library for linear math as required for computer graphics linmath.h provides the most used types required for programming compute

datenwolf 684 Jun 12, 2022
OpenBLAS is an optimized BLAS library based on GotoBLAS2 1.13 BSD version.

OpenBLAS Travis CI: AppVeyor: Drone CI: Introduction OpenBLAS is an optimized BLAS (Basic Linear Algebra Subprograms) library based on GotoBLAS2 1.13

Zhang Xianyi 4.6k Jun 20, 2022
The QuantLib C++ library

QuantLib: the free/open-source library for quantitative finance The QuantLib project (http://quantlib.org) is aimed at providing a comprehensive softw

Luigi Ballabio 3.3k Jun 27, 2022
A C++ header-only library of statistical distribution functions.

StatsLib StatsLib is a templated C++ library of statistical distribution functions, featuring unique compile-time computing capabilities and seamless

Keith O'Hara 377 Jun 19, 2022
SymEngine is a fast symbolic manipulation library, written in C++

SymEngine SymEngine is a standalone fast C++ symbolic manipulation library. Optional thin wrappers allow usage of the library from other languages, e.

null 859 Jun 25, 2022
RcppFastFloat: Rcpp Bindings for the fastfloat C++ Header-Only Library

Converting ascii text into (floating-point) numeric values is a very common problem. The fast_float header-only C++ library by Daniel Lemire does this very well, and very fast at up to or over to 1 gigabyte per second as described in more detail in a recent arXiv paper.

Dirk Eddelbuettel 18 May 2, 2022
๐Ÿ“ฝ Highly optimized 2D|3D math library, also known as OpenGL Mathematics (glm) for `C

Highly optimized 2D|3D math library, also known as OpenGL Mathematics (glm) for `C`. cglm provides lot of utils to help math operations to be fast and quick to write. It is community friendly, feel free to bring any issues, bugs you faced.

Recep Aslantas 1.4k Jun 22, 2022
โœจsigmatch - Modern C++ 20 Signature Match / Search Library

sigmatch Modern C++ 20 Signature Match / Search Library โœจ Features ?? Header-only, no dependencies, no exceptions. โ˜• Compile-time literal signature st

Sprite 35 Jun 22, 2022
C++ library for solving large sparse linear systems with algebraic multigrid method

AMGCL AMGCL is a header-only C++ library for solving large sparse linear systems with algebraic multigrid (AMG) method. AMG is one of the most effecti

Denis Demidov 528 Jun 22, 2022
Header only FFT library

dj_fft: Header-only FFT library Details This repository provides a header-only library to compute fourier transforms in 1D, 2D, and 3D. Its goal is to

Jonathan Dupuy 119 Jun 27, 2022
C++ Mathematical Expression Parsing And Evaluation Library

C++ Mathematical Expression Toolkit Library Documentation Section 00 - Introduction Section 01 - Capabilities Section 02 - Example Expressions

Arash Partow 401 Jun 24, 2022