C++ Documentation

KDTree

class KDTree

A KDTree for given particles or shapes to for example speed up ray intersections or any other operation that requires * spatial partitioning.

It is thread safe.

Public Functions

KDTree(const std::vector<Vertex> &vertices, const std::vector<IndexVector> &shapes, PlaneSelectionAlgorithm::Algorithm algorithm = PlaneSelectionAlgorithm::Algorithm::LOG)

Call to build a KDTree to speed up intersections of rays with a polyhedron’s shapes.

Parameters:

vertices – The vertex coordinates of the polyhedron
shapes – The shapes of the polyhedron with a shape being a triplet of vertex indices
algorithm – Specifies which algorithm to use for finding optimal split planes.

Returns:

the lazily built KDTree.

explicit KDTree(const std::vector<Vertex> &particles, PlaneSelectionAlgorithm::Algorithm algorithm = PlaneSelectionAlgorithm::Algorithm::LOG)

KDTree(const std::string &nodeFilePath, const std::string &faceFilePath, PlaneSelectionAlgorithm::Algorithm algorithm = PlaneSelectionAlgorithm::Algorithm::LOG)

Call to build a KDTree to speed up intersections of rays with a polyhedron’s shapes.

Parameters:

nodeFilePath – The path to the .node file containing information about the polyhedron’s vertices.
faceFilePath – The path to the .face file containing information about the polyhedron’s shapes.
algorithm – Specifies which algorithm to use for finding optimal split planes.

Returns:

the lazily built KDTree.

KDTree(const std::tuple<std::vector<Vertex>, std::vector<IndexVector>> &polySource, PlaneSelectionAlgorithm::Algorithm algorithm)

Constructor overload that allows passing the paths for the .node and .face files in a std::pair.

Parameters:

polySource – The pair of the .node and .face file
algorithm – Specifies which algorithm to use for finding optimal split planes.

Returns:

the lazily built KDTree.

std::shared_ptr<TreeNode> getRootNode()

Creates the root tree node if not initialized and returns it.

Returns:: the root tree Node.

void getIntersections(const Vertex &origin, const Vertex &ray, std::set<Vertex> &intersections)

Used to calculate intersections of a ray and the polyhedron’s shapes contained in this node.

Parameters:

origin – The point where the ray originates from.
ray – Specifies the ray direction.
intersections – The set found intersection points are added to.

size_t countIntersections(const Vertex &origin, const Vertex &ray)

Calculates the number of intersections of a ray with the polyhedron.

Parameters:

origin – The origin point of the ray.
ray – The ray direction vector.

Returns:

the number of intersections.

KDTree &prebuildTree(): Prebuilds the whole KDTree bypassing lazy loading entirely.

Friends

friend std::ostream &operator<<(std::ostream &os, const KDTree &kdTree)

Overloads the output stream operator to print a representation of the KDTree.

Parameters:

os – The output stream.
kdTree – The KDTree to be printed.

Returns:

The output stream with the KDTree representation appended.

friend std::string to_string(const KDTree &kdTree)

Tree Nodes

class TreeNode

Abstract super class for nodes in the KDTree.

Subclassed by kdtree::LeafNode, kdtree::SplitNode

Public Functions

virtual ~TreeNode() = default

virtual std::string toString() const = 0

Converts the node to a string representation.

Returns:: the string representation of the node.

Public Members

const size_t nodeId

The current node’s id.

Follows the convention that the left child gets the id 2 * <current_id> + 1 and the right child 2 * <currrent_id> + 2. Starts with 0 at the root node.

Friends

friend std::ostream &operator<<(std::ostream &os, const TreeNode &node)

Overloads the output stream operator for TreeNode.

Parameters:

os – The output stream.
node – The TreeNode to be printed.

Returns:

The output stream with the TreeNode representation appended.

class SplitNode : public kdtree::TreeNode 

A TreeNode contained in a KDTree that splits the spatial hierarchy into two new sub boxes.

Intersection tests are delegated to the child nodes.

Public Functions

SplitNode(const SplitParam &splitParam, const Plane &plane, std::variant<ObjectIndexVectors<2>, PlaneEventVectors<2>> &shapeIndexLists, size_t nodeId)

Takes parameters from the parent node and stores them for lazy child node creation.

Parameters:

splitParam – Parameters produced during the split that resulted in the creation of this node.
plane – The plane that splits this node’s bounding box into two sub boxes. The child nodes are created based on these boxes.
shapeIndexLists – Index sets of the shapes contained in the lesser and greater child nodes. ObjectIndexVector
nodeId – Unique Id given by the TreeNodeFactory.

std::shared_ptr<TreeNode> getChildNode(size_t index)

Computes the child node decided by the given index (0 for lesser, 1 for greater) if not present already and returns it to the caller.

Parameters:: index – Specifies which node to build. 0 or LESSER for _lesser, 1 or GREATER for _greater.
Returns:: the built TreeNode.

std::vector<std::shared_ptr<TreeNode>> getChildrenForIntersection(const Vertex &origin, const Vertex &ray, const Vertex &inverseRay)

Gets the children of this node whose bounding boxes are hit by the ray.

Parameters:

origin – The point where the ray originates from.
ray – Specifies the ray direction.
inverseRay – The inverse of the ray (1/ray), used to speed up calculations where it is divided by ray. Instead, we multiply with inverseRay.

Returns:

the child nodes that intersect with the ray

virtual std::string toString() const override

Generates a string representation of this SplitNode.

Returns:: the string representation.

Friends

friend std::ostream &operator<<(std::ostream &os, const SplitNode &node)

Overloads the output stream operator for SplitNode.

Parameters:

os – The output stream.
node – The SplitNode to be printed.

Returns:

The output stream with the SplitNode representation appended.

class LeafNode : public kdtree::TreeNode 

A TreeNode contained in a KDTree that doesn’t split the spatial hierarchy any further.

Intersection tests are directly performed on the contained shapes here.

Public Functions

explicit LeafNode(const SplitParam &splitParam, size_t nodeId)

Takes parameters from the parent node and stores them for later intersection tests.

Parameters:

splitParam – Parameters produced during the split that resulted in the creation of this node.
nodeId – Unique Id given by the TreeNodeFactory.

void getIntersections(const Vertex &origin, const Vertex &ray, std::set<Vertex> &intersections)

Used to calculated intersections of a ray and the polyhedron’s shapes contained in this node.

Parameters:

origin – The point where the ray originates from.
ray – Specifies the ray direction.
intersections – The set intersection points are added to.

virtual std::string toString() const override

Converts the node to a string representation.

Returns:: the string representation of the node.

Friends

friend std::ostream &operator<<(std::ostream &os, const LeafNode &node)

Plane Selection Algorithms

Base Algorithm

class PlaneSelectionAlgorithm

Subclassed by kdtree::NoTreePlane, kdtree::PlaneEventAlgorithm, kdtree::SquaredPlane

Public Types

enum class Algorithm

Enum of available plane selection algorithms named after their runtimes.

Values:

enumerator NOTREE

enumerator QUADRATIC

enumerator LOGSQUARED

enumerator LOG

Public Functions

virtual ~PlaneSelectionAlgorithm() = default

virtual std::tuple<Plane, double, std::variant<ObjectIndexVectors<2>, PlaneEventVectors<2>>> findPlane(const SplitParam &splitParam) = 0

Finds the optimal split plane to split a provided rectangle section optimally.

Parameters:: splitParam – specifies the polyhedron section to be split Tuple of the optimal plane to split the specified bounding box, its cost as double and a list of shape sets with respective positions to the found plane. Refer to ObjectIndexVectors<2>} for more information.

template<template<size_t> typename ContainerVectors> inline ContainerVectors<2> addEqualPointsToSubset(ContainerVectors<3> subsets, const bool minSideChosen)

Takes subsets of shapes divided by a split plane and adds the shapes lying in the plane (planar) to one of the subsets.

Template Parameters:

ContainerVectors – An array type that contains a fixed number of vectors specified through generics.

Parameters:

subsets – The subsets of shapes divided by the split plane (min, max, planar).
minSideChosen – Whether to add the planar shapes to the min side subset.

Returns:

Public Static Attributes

static constexpr double traverseStepCost = {1.0}: Constant that describes the cost of traversing the KDTree by one step.

static constexpr double shapeIntersectionCost = {1.0}: Constant that describes the cost of intersecting a ray and a single object.

template<typename ...CallbackArgs> class OptimalPlane

Class to evaluate candidate split planes and keep track of the optimal plane found so far.

Template Parameters:: CallbackArgs – The argument types to be passed to the callback function when retrieving the geometry split through getPointsSplit().

Public Functions

~OptimalPlane() = default

inline explicit OptimalPlane(const SplitParam &splitParam, const std::function<std::variant<ObjectIndexVectors<2>, PlaneEventVectors<2>>(const OptimalPlane&, CallbackArgs...)> &boundPointsSplit)

inline void evaluatePlane(const Plane &candidatePlane, const double candidateCost, CallbackArgs... args)

Evaluates a candidate split plane and updates the optimal plane if the candidate is better.

Parameters:

candidatePlane – The candidate split plane to evaluate.
candidateCost – The cost of the candidate split plane.
args – The arguments to be passed to the callback function when retrieving the geometry split (should the candidate be optimal).

inline Plane getOptimalPlane() const

Retrieves the optimal split plane found so far.

Returns:: The optimal split plane.

inline double getCost() const

Retrieves the cost of the optimal split plane found so far.

Returns:: The cost of the optimal split plane.

inline std::variant<ObjectIndexVectors<2>, PlaneEventVectors<2>> getPointsSplit()

Retrieves the geometry split for the optimal split plane found so far.

Returns:: The geometry split for the optimal split plane.

Public Members

const SplitParam &splitParam: The parameters of the scene to find the optimal plane for.

Implementations

class LogNPlane : public kdtree::PlaneEventAlgorithm 

A strategy for calculating optimal planes.

Part of the Strategy Software pattern.

Public Functions

virtual std::tuple<Plane, double, std::variant<ObjectIndexVectors<2>, PlaneEventVectors<2>>> findPlane(const SplitParam &splitParam) override

Finds the optimal split plane to split a provided rectangle section optimally.

Parameters:: splitParam – specifies the polyhedron section to be split Tuple of the optimal plane to split the specified bounding box, its cost as double and a list of shape sets with respective positions to the found plane. Refer to ObjectIndexVectors<2>} for more information.

class LogNSquaredPlane : public kdtree::PlaneEventAlgorithm 

A strategy for calculating optimal planes.

Part of the Strategy Software pattern.

Public Functions

virtual std::tuple<Plane, double, std::variant<ObjectIndexVectors<2>, PlaneEventVectors<2>>> findPlane(const SplitParam &splitParam) override

Finds the optimal split plane to split a provided rectangle section optimally.

Parameters:: splitParam – specifies the polyhedron section to be split Tuple of the optimal plane to split the specified bounding box, its cost as double and a list of shape sets with respective positions to the found plane. Refer to ObjectIndexVectors<2>} for more information.

class SquaredPlane : public kdtree::PlaneSelectionAlgorithm 

A strategy for calculating optimal planes.

Part of the Strategy Software pattern. O(N^2) time complexity.

class NoTreePlane : public kdtree::PlaneSelectionAlgorithm 

class PlaneEventAlgorithm : public kdtree::PlaneSelectionAlgorithm : Subclassed by kdtree::LogNPlane, kdtree::LogNSquaredPlane

Factory

class PlaneSelectionAlgorithmFactory

Public Static Functions

static std::shared_ptr<PlaneSelectionAlgorithm> create(PlaneSelectionAlgorithm::Algorithm algorithm)

Factory method to return the plane finding selection algorithm specified by the enum parameter.

Parameters:: algorithm – Specifies which algorithm to return.
Returns:: The algorithm which executes the requested strategy.

Geometry and Data Structures

class GeometryObject

This class contains a collection of vertices, representing the corners of a geometrical shape and provides the abstraction on which the kdtree operates.

Public Functions

explicit GeometryObject(IndexVector objVertices)

Vertex operator[](size_t index) const

Returns the index-th vertex of the shape represented by this GeometryObject.

Parameters:: index – The n-th node which to return
Returns:: a vertex

const IndexVector &getIndexVector() const

Get the indices of the corner vertices.

Returns:: the indices stored in a std::vector

std::vector<Vertex> getVertices() const

Get the corner vertices.

Returns:: a std::vector of Vertex objects

Public Members

const size_t objIndex: This index uniquely identifies a GeometryObject during kdtree construction.

const IndexVector objVertices: Stores information on the corner vertices of this GeometryObject by storing their respective indices referencing the static vertices.

Public Static Attributes

static size_t runningIndex = {0}: This field stores the index of the next GeometryObject and is increased whenever a new Object is increased.

static std::vector<Vertex> vertices: The global vertices of the scene on which the GeometryObjects are built on.

struct Box

Defines a rectangular box by taking two opposite corner points.

First is the point closest to the origin and second is the point farthest away.

Public Functions

std::pair<double, double> rayBoxIntersection(const Vertex &origin, const Vertex &inverseRay) const

Calculates the intersection points of a ray and a box.

Parameters:

origin – The origin of the ray.
inverseRay – The inverse ray direction vector of the ray to be intersected (used for faster calculations).

Returns:

Parameters t of the equation $ intersection_point = origin + t * ray $ for the entry and exit intersection points.

double surfaceArea() const

Calculates the surface area of a box.

Returns:: the surface area

std::pair<Box, Box> splitBox(const Plane &plane) const

Splits this box into two new boxes.

Parameters:: plane – the plane by which to split the original box.
Returns:: a pair of boxes that result by splitting this box.

std::vector<Vertex> clipToVoxel(const std::vector<Vertex> &points) const

Takes points of a shape of a polyhedron and clips them to this box.

If all the points lie in the box no changes are made but if points lie outside of the box they are linearly interpolated onto the box. Uses the Sutherland-Hodgman-Algorithm.

Parameters:: points – The corner points of the shape to be clipped.
Returns:: The new corner points of the clipped shape.

explicit Box(const std::pair<Vertex, Vertex> &pair)

Box()

Public Members

Vertex minPoint: The point closer to the origin, thus minimal.

Vertex maxPoint: The point further away from the origin, thus maximal.

Public Static Functions

template<typename Container> static inline Box getBoundingBox(const Container &vertices)

Finds the minimal bounding box for a set of vertices.

Parameters:: vertices – the set of vertex coordinates for which to find the box
Returns:: the bounding box Box

struct Plane

Defines a plane that is parallel to one of the coordinate planes, by taking the fixed axis coordinate value for the plane and the coordinate index (Direction) that is fixed for every \ point on the plane.

E.g. Specifying 0.0 and Direction::X would describe the YZ plane that goes through the origin. The direction is equivalent to the coordinate that is 1 in the normal vector of the plane, the others are 0.

Public Functions

Vertex normal(bool returnFlipped = false) const

Returns the normal vector for this plane.

Parameters:: returnFlipped – Whether to return the normal pointing in the opposite direction.
Returns:: The normal vector.

Vertex originPoint() const

Returns the origin point of a plane, meaning a point that lies on the plane.

Returns:: The origin point.

double rayPlaneIntersection(const Vertex &origin, const Vertex &inverseRay) const

Intersects a ray with the splitPlane.

Parameters:

origin – The point where the ray originates from.
inverseRay – The inverse ray direction vector of the ray to be intersected (used for faster calculations).

Returns:

Returns the t parameter for the intersection point, with t being from the equation $intersection_point = orig + t * ray$. t is +-infinity if no intersection point is present.

bool operator==(const Plane &other) const: Equality operator used for testing purposes.

bool operator!=(const Plane &other) const: Inequality operator used for testing purposes.

Plane() = default

Plane(const Vertex &point, Direction direction)

Constructs a Plane from a point (vertex) and orientation.

Parameters:

point – The point that lies on the plane.
direction – The orientation in which the plane spans.

Plane(double point, Direction direction)

Constructs a plane from a coordinate on the axis that is given by the plane orientation.

Parameters:

point – The plane anchor point coordinate.
direction – The orientation in which the plane spans.

Public Members

double axisCoordinate: Each point lying on the plane has to have this value in the dimension specified in the orientation parameter.

Direction orientation: Specifies which coordinate dimension is fixed for every point on the plane.

Friends

friend std::ostream &operator<<(std::ostream &os, const Plane &plane)

Used to print to a Plane an ostream.

Parameters:

os – The stream to print to.
plane – The plane that is printed.

Returns:

The ostream for chaining calls.

struct PlaneEvent

Generated when traversing the vector of shapes and building their candidate planes.

Public Functions

PlaneEvent(PlaneEventType type, Plane plane, unsigned objIndex)

PlaneEvent() = default

bool operator<(const PlaneEvent &other) const

Less operator used for sorting an PlaneEvent vector.

Parameters:: other – the PlaneEvent to compare this to.
Returns:: true if this should precede the other argument.

bool operator==(const PlaneEvent &other) const: Equality operator used for testing purposes.

Public Members

PlaneEventType type

Plane plane: The candidate plane suggested by the shape included in this struct.

unsigned int objIndex: The index of the shape that generated this candidate plane.

struct SplitParam

Helper struct to bundle important parameters required for splitting a Polyhedron for better readability.

Public Functions

inline SplitParam(const std::vector<GeometryObject> &geometryObjects, const Box &boundingBox, const Direction splitDirection, const std::shared_ptr<PlaneSelectionAlgorithm> &planeSelectionStrategy)

Constructor that initializes all fields.

Intended for the use with std::make_unique. See SplitParam fields for further information.

inline SplitParam(const std::vector<GeometryObject> &geometryObjects, const std::variant<ObjectIndexVector, PlaneEventVector> &boundObjects, const Box &boundingBox, const Direction splitDirection, const std::shared_ptr<PlaneSelectionAlgorithm> &planeSelectionStrategy): Constructor manually initializing boundObjects, used for testing.

Public Members

const std::vector<GeometryObject> &geometryObjects: The vertices that compose the Polyhedron.

std::variant<ObjectIndexVector, PlaneEventVector> boundObjects

Either an index list of shapes that are included in the current bounding box of the KDTree or a list of PlaneEvents containing the information about thr bound shapes.

Important when building deeper levels of a KDTree.

Box boundingBox: The current bounding box that should be divided further by the KDTree.

mutable Direction splitDirection

The direction in which the current bounding box should be divided by further.

Refer to Plane on how to interpret the Direction.

const std::shared_ptr<PlaneSelectionAlgorithm> planeSelectionStrategy: The algorithm used to create new child TreeNodes after splitting the parent.

struct Meshes

Public Functions

inline explicit Meshes(const std::vector<std::string> &filePaths)

inline std::tuple<const std::vector<Vertex>&, const std::vector<IndexVector>&, const std::vector<Vertex>&> operator[](const size_t index) const

inline long long size() const

Public Members

std::vector<std::vector<Vertex>> vertices = {}

std::vector<std::vector<IndexVector>> faces = {}

std::vector<std::vector<Vertex>> centroids = {}

Public Static Functions

static inline std::vector<std::string> buildCompleteFilePaths(const std::string &filePath)

Utilities

class ShapeCounter

Helper class to keep count of shapes that straddle split planes, while PlaneEvents are iterated over.

Public Functions

void updateMax(Direction direction, size_t p_planar, size_t p_end)

Update the shape count for the max side of the plane.

Parameters:

direction – For which dimension to update values.
p_planar – Amount of shapes lying in the plane.
p_end – Amount of shapes ending in the plane.

void updateMin(Direction direction, size_t p_planar, size_t p_start)

Update the shape count for the min side of the plane.

Parameters:

direction – For which dimension to update values.
p_planar – Amount of shapes lying in the plane.
p_start – Amount of shapes starting in the plane.

void setPlanar(Direction direction, size_t p_planar)

Sets the amount of planar shapes for a specific dimension.

Parameters:

direction – For which dimension to update values.
p_planar – Amount of shapes lying in the plane.

size_t getMin(Direction direction) const

Returns min value for a specific dimension.

Parameters:: direction – The dimension.
Returns:: The min value.

size_t getMax(Direction direction) const

Returns max value for a specific dimension.

Parameters:: direction – The dimension.
Returns:: The max value.

size_t getPlanar(Direction direction) const

Returns the amount of planar shapes for a specific dimension.

Parameters:: direction – The dimension.
Returns:: The planar shape amount.

ShapeCounter(size_t dimensionCount, const std::array<size_t, 3> &initialValues)

class TetgenAdapter

An adapter to the Tetgen Library.

This is the interface between tetgen’s data structures and I/O capabilities and the here implemented polyhedral gravity model. The adapter always converts tetgen’s datastructure into the structure utilized by the Polyhedral Gravity Model.

The Adapter further keeps en eye on the already read in files in order to give feedback if data is in conflict.

Public Functions

inline explicit TetgenAdapter(std::vector<std::string> fileNames)

Constructs a new TetgenAdapter from a vector of filenames.

These filenames should end on the supported suffixes

Parameters:: fileNames – vector of filenames

std::tuple<std::vector<Vertex>, std::vector<IndexVector>> getPolyhedralSource()

Use this function to get a Polyhedron.

This functions consists of two steps. First, the Adapter will delegate I/O to the tetgen library and read in the Polyhedron data in the library’s datastructure. Second, tetgen’s datastructure is then converted to a Polyhedron.

Returns:: a Polyhedron

void readNode(const std::string &filename)

Reads nodes from a .node file.

Parameters:: filename – of the input source without suffix
Throws:: an – exception if the nodes already have been defined

void readFace(const std::string &filename)

Reads faces from a .face file.

Parameters:: filename – of the input source without suffix
Throws:: an – exception if the faces already have been defined

void readOff(const std::string &filename)

Reads elements from a .off file (Geomview’s polyhedral file format)

Parameters:: filename – of the input source without suffix
Throws:: an – exception if the elements already have been defined

void readPly(const std::string &filename)

Reads elements from a .ply file (Polyhedral file format)

Parameters:: filename – of the input source without suffix
Throws:: an – exception if the elements already have been defined

void readStl(const std::string &filename)

Reads elements from a .stl file (Stereolithography format)

Parameters:: filename – of the input source without suffix
Throws:: an – exception if the elements already have been defined

void readMesh(const std::string &filename)

Reads elements from a .mesh file (Medit’s mesh file format)

Parameters:: filename – of the input source without suffix
Throws:: an – exception if the elements already have been defined

Utility Namespaces

namespace util

Typedefs

template<typename T, size_t M, size_t N> using Matrix = std::array<std::array<T, N>, M>

Alias for two-dimensional array with size M and N.

M is the major size.

Functions

template<Container C, typename BinOp> C applyBinaryFunction(const C &lhs, const C &rhs, BinOp binOp)

Applies a binary function to elements of two containers piece by piece.

The objects must be iterable and should have the same size!

Template Parameters:

Container – an iterable object like an array or vector
BinOp – a binary function to apply

Parameters:

lhs – the first container
rhs – the second container
binOp – a binary function like +, -, *, /

Returns:

a container containing the result

template<Container C, typename Scalar, typename BinOp> C applyBinaryFunction(const C &lhs, const Scalar &scalar, BinOp binOp)

Applies a binary function to elements of one container piece by piece.

The objects must be iterable. The resulting container consist of the containers’ object after the application of the binary function with the scalar as parameter.

Template Parameters:

Container – a iterable object like an array or vector
Scalar – a scalar to use on each element
BinOp – a binary function to apply

Parameters:

lhs – the first container
scalar – a scalar to use on each element
binOp – a binary function like +, -, *, /

Returns:

a container containing the result

template<Container C> C operator-(const C &lhs, const C &rhs)

template<Container C> C operator+(const C &lhs, const C &rhs)

template<Container C> C operator*(const C &lhs, const C &rhs)

template<Container C> C operator/(const C &lhs, const C &rhs)

template<Container C, typename Scalar> C operator+(const C &lhs, const Scalar &scalar)

template<Container C, typename Scalar> C operator*(const C &lhs, const Scalar &scalar)

template<Container C, typename Scalar> C operator/(const C &lhs, const Scalar &scalar)

template<Container C> double euclideanNorm(const C &container)

Applies the euclidean norm/ L2-norm to a Container (e.g.

a vector)

Template Parameters:: Container – must be iterable
Parameters:: container – e.g. a vector
Returns:: an double containing the L2 norm

template<Container C> C abs(const C &container)

Computes the absolute value for each value in the given container.

Template Parameters:: Container – a iterable container, containing numerical values
Parameters:: container – the container
Returns:: a container with the modified values

template<typename T> T det(const Matrix<T, 3, 3> &matrix)

Computes the determinant with the Sarrus rule for a 3x3 matrix.

Notice that for square matrices det(A) = det(A^T).

Template Parameters:: T – a numerical value
Parameters:: matrix – the 3x3 matrix
Returns:: the determinant

template<typename T, size_t M, size_t N> Matrix<T, M, N> transpose(const Matrix<T, M, N> &matrix)

Computes the transposed of a mxn matrix.

Template Parameters:

T – the type of the matrix elements
M – the row number
N – the column number

Parameters:

matrix – the matrix to transpose

Returns:

the transposed

template<typename T> std::array<T, 3> cross(const std::array<T, 3> &lhs, const std::array<T, 3> &rhs)

Returns the cross product of two cartesian vectors.

Template Parameters:

T – a number

Parameters:

lhs – left vector
rhs – right vector

Returns:

cross product

template<typename T> std::array<T, 3> normal(const std::array<T, 3> &first, const std::array<T, 3> &second)

Calculates the normal N as (first * second) / |first * second| with * being the cross product and first, second as cartesian vectors.

Template Parameters:

T – numerical type

Parameters:

first – first cartesian vector
second – second cartesian vector

Returns:

the normal (normed)

template<typename T> T dot(const std::array<T, 3> &lhs, const std::array<T, 3> &rhs)

Returns the dot product of two cartesian vectors.

Template Parameters:

T – a number

Parameters:

lhs – left vector
rhs – right vector

Returns:

dot product

template<typename T> int sgn(T val, double cutoffEpsilon)

Implements the signum function with a certain EPSILON to absorb rounding errors.

Template Parameters:

T – a numerical (floating point) value

Parameters:

val – the value itself
cutoffEpsilon – the cut-off radius around zero to return 0

Returns:

-1, 0, 1 depending on the sign an the given EPSILON

template<typename T, size_t M, size_t N> std::array<T, M + N> concat(const std::array<T, M> &first, const std::array<T, N> &second)

Concatenates two std::array of different sizes to one array.

Template Parameters:

T – the shared type of the arrays
M – the size of the first container
N – the size of the second container

Parameters:

first – the first array
second – the second array

Returns:

a new array of size M+N with type T

template<typename T> T surfaceArea(const Matrix<T, 3, 3> &triangle)

Calculates the surface area of a triangle consisting of three cartesian vertices.

Template Parameters:: T – numerical type
Returns:: surface area

template<typename T> bool isCriticalDifference(const T &first, const T &second)

Calculates the magnitude between two values and return true if the magnitude between the exponents in greater than 17.

Template Parameters:

T – numerical type

Parameters:

first – first number
second – second number

Returns:

true if the difference is too be huge, so that floating point absorption will happen

template<class ...Ts> overloaded(Ts...) -> overloaded<Ts...>

This function template provides deduction guides for the overloaded struct.

It deduces the template arguments for overloaded based on its constructor arguments thus saving you from explicitly mentioning them while instantiation. https://en.cppreference.com/w/cpp/utility/variant/visit

Template Parameters:: Ts – A template parameter pack representing all types that will be passed to the overloaded struct.
Parameters:: Ts – Variable numbers of parameters to pass to the overloaded struct.
Returns:: This doesn’t return a value, but rather assists in the creation of an overloaded object. The type of the object will be overloaded<Ts…>.

template<typename ...Ts> auto operator+(const std::tuple<Ts...> &t1, const std::tuple<Ts...> &t2)

Adds the contents of two tuples of the same size and types with the operator +.

Template Parameters:

Ts – types of the tuples

Parameters:

t1 – first tuple
t2 – second tuple

Returns:

a new tuple with the added values

template<typename T, size_t N> std::ostream &operator<<(std::ostream &os, const std::array<T, N> &array)

Operator << for an array of any size.

Template Parameters:

T – type of the array, must have an << operator overload
N – size of the array

Parameters:

os – the ostream
array – the array itself

Returns:

ostream

template<typename T> std::ostream &operator<<(std::ostream &os, const std::set<T> &set)

Operator << for a set.

Template Parameters:

T – type of the set, must have an << operator overload

Parameters:

os – the ostream
set – the set itself

Returns:

ostream

template<Container C> std::pair<typename C::value_type, typename C::value_type> findMinMaxCoordinates(C elements)

Calculates the min and max coordinate values for each dimension of the elements supplied.

Parameters:: elements – the container of whose elements to search for min and max ccordinates
Returns:: the findings formatted in a pair of new elements. E.g <(0,0,0) , (1,1,1)> if the container {(0,0,1), (1,1,0)} is passed.

template<typename FloatType> bool almostEqualUlps(FloatType lhs, FloatType rhs, int ulpDistance)

template bool almostEqualUlps< float > (float lhs, float rhs, int ulpDistance)

template bool almostEqualUlps< double > (double lhs, double rhs, int ulpDistance)

template<typename FloatType> bool almostEqualRelative(FloatType lhs, FloatType rhs, double epsilon = EPSILON_ALMOST_EQUAL)

Function to check if two floating point numbers are relatively equal to each other within a given error range or tolerance.

C++ Documentation

KDTree

Tree Nodes

Plane Selection Algorithms

Base Algorithm

Implementations

Factory

Geometry and Data Structures

Utilities

Utility Namespaces

Indices and tables