Geode

Mathematics library for Crystal supporting vectors, matrices, quaternions, and more.

The goal of Geode is to be an expressive and performant mathematics library. Geode attempts to distill concepts down to their basic components. Types, such as vectors and matrices, can be used with any numeric primitive (int or float) and any dimensionality. Whenever possible, Geode will produce a compilation error for invalid operations instead of raising a runtime error. E.g. multiplying matrices with mismatched side lengths.

Installation

Add this to your application's shard.yml:

dependencies:
  geode:
    gitlab: arctic-fox/geode
    version: ~> 0.2.1

Usage

This README explains the design of Geode and basic usage. For detailed information on usage and available function, please check the documentation.

It may be useful to include Geode in your code to avoid name-spacing. Examples here and in the documentation omit the Geode:: prefix for brevity.

Common Types

Most types have a "base" type and a collection of modules that implement functionality. The base type defines the underlying data structure and fundamental access patterns. Any specifics of the type are also defined in the base. The base types include a "common" module. The common module then includes all other modules as mix-ins. This pattern allows any "common" type to be used as an argument instead of relying on a base type.

Take for example a 2D vector that has two components.

struct Vector2D(T)
  include CommonVector2D

  getter x : T, y : T
end

struct Vector2DArray(T)
  include CommonVector2D

  @array : StaticArray(T, 2)

  def x
    @array[0]
  end

  def y
    @array[1]
  end
end

NOTE: The types listed above are fictitious and not actually in Geode.

Vector2D and Vector2DArray are base types. They both include the CommonVector2D module. The functions in CommonVector2D and all other mix-ins will work, regardless of the base type used. This allows fundamental properties and rules to be reused across types without duplicating code. It also allows the base type to decide the optimal design for storing and accessing data.

Immutable

All types are immutable unless otherwise specified.

Extension Methods

Methods add to types defined outside this shard are called extensions. These methods are optional and not included by default. To enable them, do:

require "geode/extensions"

Most of these methods provide syntactic sugar. See each "extensions" section below for details regarding methods exposed for each type.

#inv

The #inv method returns the inverse of a number.

2.inv   # => 0.5
0.2.inv # => 5.0

Vectors

Vectors types come in two groups: fixed-size and generic. Both use the common type CommonVector. Vector types include Indexable.

Vector size is a compile-time constant. A compilation error will be raised for any operations where the sizes between vectors don't match. For instance, adding two vectors with different sizes.

Fixed-size

Fixed-size vectors are named VectorN where N is the dimensionality of the vector. There are 4 vectors of this type: Vector1 through Vector4. Each takes a type parameter which is the scalar value stored for each component. Additionally, there are aliases for the common numerical types.

• VectorNI - I for integer, 32-bit integers
• VectorNL - L for long, 64-bit integers
• VectorNF - F for float, 32-bit floating points
• VectorND - D for double, 64-bit floating points

To create a fixed-size vector, one of the initializer methods can be used, the simplest being:

Vector3.new(x, y, z)

The short-hand bracket-notation [] can also be used.

Vector3[x, y, z]

Fixed-size vectors also have convenience methods specific to their size. The #x, #y, #z, and #w getters are available for their corresponding sized vectors.

Vector2 has angle methods #angle, #signed_angle, and #rotate. Vector3 has angle methods #alpha, #beta, #gamma, #rotate_x, #rotate_y, #rotate_z, and #cross (cross-product). These methods are not available on the generic vector type (even if their dimensionality is 2 or 3).

All fixed-size vector use the base type VectorBase.

Generic

Generic vectors are defined by the Vector type. They can have an arbitrarily large size, however, the size must be known at compile-time. Generic vectors take two type arguments: the component type and size. This is similar to StaticArray.

Vector(Float64, 7).new({1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0})

The short-hand bracket-notation [] can also be used.

Vector[1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0]

Functions

Some common vector functions are listed below.

• Standard operations: +, -, *, /
• Geometric operations: #dot, #mag, #mag2, #normalize, #project
• Matrix operations: *, #to_row, #to_column

Extensions

There is a single extension method for vectors: *. This allows multiplying a vector by a scalar, where the scalar is in front.

5 * Vector[1, 2, 3] # => (5, 10, 15)

Without this extension, all vector multiplication requires the vector on the left of the * operator.

Considerations

The fixed-size vectors store their values on the stack. Generic vectors store their values on the heap. For 1-4 dimensions, the fixed-size vectors are recommended. In general, they will be faster and provide more functions since size is explicit. For arbitrarily large dimensions, a generic vector should be used.

Matrices

Like vectors, matrices come in two styles: fixed-size and generic. Both use the common type CommonMatrix. Matrix types include Indexable - see 'Indexing' section below for details.

Matrix dimensions are compile-time constants. A compilation error will be raised for any operations where the sizes between matrices don't match. For instance, multiplying matrices with mismatched dimensions.

Matrix types are complex and have a lot of methods.

Fixed-size

Fixed-size matrices are named MatrixMxN where M and N are the rows and columns respectively. There are 16 matrices of this type: Matrix1x1 through Matrix4x4. Each takes a type parameter which is the scalar value stored for each entry. Additionally, there are aliases for the common square types.

• Matrix1 - Short for Matrix1x1
• Matrix2 - Short for Matrix2x2
• Matrix3 - Short for Matrix3x3
• Matrix4 - Short for Matrix4x4

To create a fixed-size matrix, one of the initializer methods can be used, the simplest being:

Matrix3x2.new({{1, 2, 3}, {4, 5, 6}})

The short-hand bracket-notation [] can also be used.

Matrix3x2[[1, 2, 3], [4, 5, 6]]

The initializers use nested collections, where each element of the outer collection is a row. These could also be written like so for readability:

Matrix3x3[
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

Fixed-size matrices Matrix1x1, Matrix2x2, Matrix3x3, and Matrix4x4 include SquareMatrix. This provides extra methods specifically for square matrix types. These also have an .identity constructor that create an identity matrix.

Generic

Generic matrices are defined by the Matrix type. They can have an arbitrarily large size, however, the size must be known at compile-time. Generic vectors take three type arguments: the component type, the rows, and columns. Rows and columns are represented as integers M and N respectively. This is similar to StaticArray.

Matrix(Float64, 2, 7).new({
  {1.1, 2.1, 3.1, 4.1, 5.1, 6.1, 7.1},
  {1.2, 2.2, 3.2, 4.2, 5.2, 6.2, 7.2}
})

The short-hand bracket-notation [] can also be used.

Matrix[
  [1.1, 2.1, 3.1, 4.1, 5.1, 6.1, 7.1],
  [1.2, 2.2, 3.2, 4.2, 5.2, 6.2, 7.2]
]

The initializers use nested collections, where each element of the outer collection is a row.

The Matrix generic type includes SquareMatrix for convenience, but will generate a compilation error if they're called on non-square matrices.

Functions

Some common matrix functions are listed below.

• Size: #rows, #columns, #size #square?
• Indexers: #row, #column, #each_row, #each_column
• Standard operations: +, -, *, / #transpose #sub
• Square matrices: #diagonal, #trace, #determinant
• Vector operations: *, #row?, #column?, #to_vector
• Transforms (2D): .reflect_x, .reflect_y, .rotate, .scale, .translate #reflect_x, #reflect_y, #rotate, #scale, #translate
• Transforms (3D): .reflect_x, .reflect_y, .reflect_z, .rotate, .rotate_x, .rotate_y, .rotate_z, .scale, .translate, .look_at, #reflect_x, #reflect_y, #reflect_z, #rotate, #rotate_x, #rotate_y, #rotate_z, #scale, #translate
• Projections: .ortho, .perspective

Multiplication

Matrices of any size can be multiplied together, provided their dimensions match. Geode will know at compile-time the resulting matrix size. Recall that MxN x NxP = MxP.

m1 = Matrix[[1, 2, 3], [4, 5, 6]]
m2 = Matrix[[1], [10], [100]]
m1 * m2 # => [[321], [654]]

Matrices and vectors can be multiplied together. Order matters in this case. When multiplying a matrix by a vector (M x v), the vector is treated as a column vector (matrix with one column). Conversely, multiplying a vector by a matrix (v x M), the vector is treated as a row vector (matrix with one row).

mat = Matrix[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
vec = Vector[1, 10, 100]
mat * vec # => (321, 654, 987)
vec * mat # => (741, 852, 963)

Transforms

2D and 3D transforms methods are available on 2x2, 3x3, and 4x4 matrices. 2D transforms can be performed with 2x2 matrices and 3x3 matrices if there is a translation. Likewise, 3D transforms can be performed with 3x3 matrices and 4x4 matrices if there is a translation. There are two categories for each of these transforms.

The first are exposed as class methods on their respective, fixed-size matrix type. These create a matrix as-if the transformation was applied to an identity matrix. They're useful for starting a chain of transformations.

vector = Vector2[1.0, 1.0].normalize
matrix = Matrix2(Float64).rotate(45.degrees)
vector * matrix # => (0.0, 1.0)

The second category are instance methods. These apply the transform and return it as a new matrix.

vector = Vector2[1.0, 1.0].normalize
matrix = Matrix2(Float64).scale(2).rotate(45.degrees) # Scale then rotate.
vector * matrix # => (0.0, 2.0)

Transforms can be chained together.

Matrix2(Float64).identity.scale(5).rotate(180.degrees)

2D translations on a 2x2 matrix will return a 3x3 matrix. Similarly, 3D translations on a 3x3 matrix will returns a 4x4 matrix. When applying to a vector (or other primitive), it must use the expanded size. Typically, 1 or 0 is used for the "extra" dimension.

vector = Vector3[1, 2, 1]
matrix = Matrix2(Float64).rotate(45.degrees).translate(2, 3)
vector * matrix # => (1.292893219, 5.121320343, 1.0)

vector = Vector4[1, 2, 3, 1]
matrix = Matrix3(Float64).rotate_y(45.degrees).translate(2, 3, 4)
vector * matrix # => (4.828427124, 5.0, 5.414213562, 1.0)

Note: The transform matrices are constructed so that the matrix is on the right-hand-side of the multiplication operation. If it is desired to have them on the left, transpose the matrix before multiplying.

vector = Vector3[1, 2, 1]
matrix = Matrix2(Float64).rotate(45.degrees).translate(2, 3)

vector * matrix           # => (1.292893219, 5.121320343, 1.0)
matrix.transpose * vector # => (1.292893219, 5.121320343, 1.0)

Projection

The following projection methods are available:

Orthographic

The Matrix4x4.ortho method can be used to generate an orthographic projection. There is also a 2D variant by the same name. These methods take the bounds of the region to project (clipping planes).

Perspective

The Matrix4x4.perspective constructs a perspective projection matrix. This method takes a field-of-view, aspect ratio, and near and far clipping planes. The field-of-view is the vertical angle, not horizontal.

Handedness and Z-normalization

By default, the 3D projection methods produce matrices for right-handed coordinate systems with z normalized between -1 and 1. This is typical for OpenGL. If a different layout is needed, there are variants of these methods. Add one of the following suffixes to change the behavior (e.g. perspective_lh_zo):

• _lh_zo - left-handed, z from 0 to 1.
• _lh_no - left-handed, z from -1 to 1.
• _rh_zo - right-handed, z from 0 to 1.
• _rh_no - right-handed, z from -1 to 1 (the default).

The method used by the methods without a suffix is controlled by compiler flags. This is an ideal way to change the layout method globally. -Dleft_handed will use a left-handed coordinate system. -Dz_zero_one will normalize z between 0 and 1.

Indexing

Matrices use two indexing modes: row-column and flat.

Row-column indexing is the common way of referencing entries in a matrix. It uses i and j to represent the row and column indices respectively. i ranges from 0 to M - 1 and j ranges from 0 to N - 1. Entries can be accessed by using the #[] method with two arguments: i and j.

Flat indexing uses a single index from 0 to M x N - 1. It counts in row-major order. This indexing method is primarily used when dealing with Indexable methods provided by the Crystal standard library.

Methods and their documentation use the following conventions to distinguish between indexing modes:

• The word "indices" refers to row-column indexing, while "index" refers to flat indexing.
• The variables i and j are used for row-column indexing, while index is used for flat indexing.

matrix.each_indices do |i, j|
  # ...
end

matrix.each_index do |index|
  # ...
end

Extensions

There is a single extension method for matrices: *. This allows multiplying a matrix by a scalar, where the scalar is in front.

5 * Matrix[[1, 2, 3], [4, 5, 6]] # => [[5, 10, 15], [20, 25, 30]]

Without this extension, all matrix multiplication requires the matrix on the left of the * operator.

Considerations

The fixed-size matrices store their values on the stack. Generic matrices store their values on the heap. For side lengths 1-4, the fixed-size matrices are recommended. In general, they will be faster and provide more functions since size is explicit. For arbitrarily large matrices, a generic matrix should be used.

All matrices have their elements laid out in row-major order.

Angles

Geode provides types for some angle units. The currently supported units are: Degrees, Radians, Turns, Gradians

As a refresher, degrees are measured from 0 to 360; radians from 0 to 2π or τ; and gradians from 0 to 400. Turns is an angle from 0 to 1, like a revolution.

Angles are created by passing their numerical value to an initializer.

Degrees.new(90)
Radians.new(Math::PI / 2)
Turns.new(0.25)
Gradians.new(100)

The following common angles are available as constructors on all types: .zero, .quarter, .third, .half, .full

Radians(Float64).third

Angle types have a type parameter, which is the underlying numerical type. Keep this in mind when performing calculations.

Degrees.new(30) * 2 # 60 degrees (represented as Int32)

Usually you will want to use a floating point number.

Degrees.new(30.0) * 2 # 60.0 degrees (represented as Float64)

Angles can be converted by using a #to_x method, where x is the type to convert to (e.g. #to_radians). An angle can be converted to a numerical type in radians by calling #to_f. Anywhere in Geode where an angle is accepted, one of these unit types can be used, for instance Vector2#rotate.

All angle types have a base type of Angle. Angles can have basic math operations performed on them (+, -, *, /) even with different units. The #normalize method will correct an angle so that it is between 0 and 1 revolution.

Degrees.new(540).normalize # 180 degrees

Angles can be stepped with an iterator (see Steppable).

0.degrees.step to: 180, by: 5.degrees

Extensions

The angle extension methods provide syntax sugar for creating angles. Similar to how the Crystal's standard library exposes time span methods, such as #hours, the same can be done with angles. There are two groups of extensions.

The first simply creates an angle of the specified unit from the numerical value.

90.degrees
Math::PI.radians

is effectively the same as:

Degrees.new(90)
Radians.new(Math::PI)

There is a method for each unit type: #degrees, #radians, #turns, #gradians

Additionally, there are extension methods that convert their numerical value from radians to the desired unit.

(Math::PI / 2).to_degrees # 90 degrees
Math::PI.to_turns         # 0.5 turns

is effectively the same as:

(Math::PI / 2).radians.to_degrees
Math::PI.radians.to_turns

There is a method for each unit type: #to_degrees, #to_radians, #to_turns, #to_gradians

Considerations

At a low-level, angle types provide a wrapper around a numerical value. The methods in these wrappers are aware of their unit (radians, degrees, etc.). The numerical value is stored as-is and not converted. For instance, specifying 45.degrees will not convert to radians and will store the value 45 in memory. Units are converted only when necessary.

Development

This shard is still in active development. New features are being added and existing functionality improved.

Feature Progress

In no particular order, features that have been implemented and are planned. Items not marked as completed may have partial implementations.

• Vectors
  • Vector1
  • Vector2
  • Vector3
  • Vector4
  • Vector
  • Common
  • Operations
  • Geometry
  • Matrices
  • Comparison
  • Unit optimizations
• Matrices
  • Matrix1xN (1x1, 1x2, 1x3, 1x4)
  • Matrix2xN (2x1, 2x2, 2x3, 2x4)
  • Matrix3xN (3x1, 3x2, 3x3, 3x4)
  • Matrix4xN (4x1, 4x2, 4x3, 4x4)
  • Matrix
  • Common
  • Operations
  • Square
    • Diagonal
    • Trace
    • Determinant for generic matrices
    • Inverse
  • Vectors
  • Transforms
    • 2D
    • 3D
    • Projection
  • Iterators
  • Comparison
• Quaternions
• Polar
  • 2D
  • Spherical 3D
  • Cylindrical 3D
• Angles
  • Radians
  • Degrees
  • Turns
  • Gradians
  • Byte degrees
  • Extensions & conversions
• Primitives
  • Shapes
  • Lines
  • Points
  • Planes
• Curves
  • Polynomial
  • Bézier
  • Splines
• Functions
  • Lerp
  • Slerp
  • Edge
  • Min/max
• Extensions
  • Angles
  • Vector scalar
  • Matrix scalar

Contributing

1. Fork it (GitHub https://github.com/icy-arctic-fox/geode/fork or GitLab https://gitlab.com/arctic-fox/geode/fork/new)
2. Create your feature branch (git checkout -b my-new-feature)
3. Commit your changes (git commit -am 'Add some feature')
4. Push to the branch (git push origin my-new-feature)
5. Create a new Pull/Merge Request

Please make sure to run crystal tool format before submitting. The CI build checks for properly formatted code. Ameba is run to check for code style.

Documentation is automatically generated and published to GitLab pages. It can be found here: https://arctic-fox.gitlab.io/geode

This project's home is (and primarily developed) on GitLab. A mirror is maintained to GitHub. Issues, pull requests (merge requests), and discussion are welcome on both. Maintainers will ensure your contributions make it in.

Testing

Tests must be written for any new functionality.

The spec/ directory contains feature tests as well as unit tests. These demonstrate small bits of functionality. The feature tests are grouped into sub directories based on their type.

Spectator is used for testing. The test suite is broken apart for CI builds to reduce compilation time.