Geometry Library

Basic geometry library. More...

Collaboration diagram for Geometry Library:

Detailed Description

Basic geometry library.

The classes in this namespace each represent a basic geometric object. While they come with some basic functionality specific to the represented object, their main use case is passing geometric information between other pieces of code in a consistent manner. As such, all of these classes are designed to be lightweight and immutable. Note that they are assignable however.

Note

Unless the name of the class indicates otherwise, all of these objects can be abitrarily oriented in 3D space. In cases where the object is indeed 2D, the interface will not allow implicit conversions like z=0 and instead only deal with 2D data. When using both 3D and 2D objects, the calling code is responsible for setting up appropriate conversions.

Since it is usually possible to change the data in these classes in a way that preserves the represented geometric object, e.g. by doing a permutation of the 3 corners of a triangle, we provide the function isEquivalent(), which checks for equivalence of the represented object. The regular equality operator is also available and conversely checks for exact equality in the underlying data. To complement these further, there is also an isApprox() function which checks for equality in the underlying data using the same tolerance as Eigen::Vector3d::isApprox().

Additionally, the library provides free functions to determine if and how a given pair of these geometric objects intersects. These functions typically have a Utils::Variant return type, in order to properly handle all possible edge cases.

Provided geometric objects

The Geometry module consists of various files each dealing with a specific kind of geometric object. All of these are can be found in Core/Geometry:

• Box.h provides AlignedBox, which as the name implies does not support arbitrary orientation and instead always has edges parallel to the axes of the coordinate system. This class is typically used for bounding boxes or defining regions of interest.
• Circle.h contains the class of the same name, which represents a circle and the enclosed surface.
• Ellipse.h declares Ellipse2D, representing an ellipse of arbitrary orientation in a 2D vector space, as well as the area enclosed by it.
• Line.h contains the LineSegment and Line classes, for lines of finite and infinite length respectively. Both inherit from the abstract LineBase interface, which can be used for writing code that does not immediately care about the length.
• Plane.h defines a class of the same name representing a plane bisecting the 3D vector space. As such, this plane has infinite size. Note that there are 2 conflicting conventions to encode such a plane in a 4-component vector. The one commonly encountered in our framework is called the "computer vision normal form" here.
• Polygon.h contains Polygon2D, a planar polygon. Unlike the related (now deprecated) class in ImFusionLib, this always represents a closed contour. It also enforces all edges to be non-zero, so the constructor will filter out duplicate neighbouring points. Self-intersections are allowed in general, but not all member functions support such polygons. The isSimple() function can be used to check for this.
• Rectangle.h contains AlignedRectangle2D, which is basically the 2D version of AlignedBox.
• Finally, Triangle.h provides arbitrary 3D triangles in form of the Triangle class.

Intersections

The file Intersection.h provides free functions handling intersections between a pair of given geometric objects. These come in two distinct flavors:

The intersection() functions compute and return a geometric object defined by the overlap of the inputs. Since the type of this resulting object can vary depending on how these objects overlap (e.g. a line segment and a triangle can overlap in a line segment, a single point or not at all), these functions return a Utils::Variant covering all possible scenarios. It is left to the caller to determine which of these scenarios to handle and how.

The intersects() functions on the other hand only return if there is any spatial overlap between the inputs and can be used to save computation time when the shape and position of the overlap are not relevant. Touching at a single point on the boundary counts as sufficient intersection for these functions.

Note

In cases where one of the geometric objects involved in an intersection operation is not represented by a class in this module (yet), the intersection is a member function of the other object instead of a free function in Intersection.h. This avoids ambiguities arising from the missing object being represented by loose Eigen vectors.

Usage Examples

Computing intersections is straightforward, but you will have to check the type of the result and handle each case appropriately:

using namespace ImFusion;
Geometry::Triangle tri;
Geometry::LineSegment line;
Utils::Variant<LineSegment, vec3, std::nullptr_t> res = Geometry::intersection(tri, line);
if (LineSegment* l = res.getIf<LineSegment>())
    LOG_INFO("Intersected in-plane from " << l->start() << " to " << l->end());
else if (vec3* p = res.getIf<vec3>())
    LOG_INFO("Clipped through point " << *p);
else
    LOG_INFO("No intersection");

When combining 2D and 3D data, the caller is responsible for making the conversion between vector spaces:

Geometry::Ellipse2D ellipse;
std::vector<vec3> points3D;
std::function<vec2(const vec3&)> someProjectionFunction;
double minDist = std::numeric_limits<double>::max();
for (const auto& p : points3D)
    minDist = std::min(minDist, ellipse.distanceToPoint(someProjectionFunction(p)));

As mentioned above, the Line and LineSegment classes derive from a shared interface. This can be used to avoid duplicate code when writing functions that do not depend on whether the line is finite:

bool isParallel(const Geometry::Plane& plane, const Geometry::LineBase& someKindOfLine)
{
    return std::abs(plane.normal().dot(someKindOfLine.direction())) < 1e-6;
}

Namespaces
namespace	ImFusion::Geometry
	Classes to represent geometric primitives like lines or polygons, as well as functions dealing exclusively with such objects.

Classes
class	AlignedBox
	Class representing an axis aligned rectangular cuboid in 3D space. More...
class	Circle
	Class representing a circle (actually a disk, so including the inner part) in 3D space. More...
class	Ellipse2D
	Class representing an ellipse in 2D space. More...
class	LineBase
	Common interface of Line and LineSegment. More...
class	Line
	Class representing a full line, i.e. More...
class	LineSegment
	Class representing a line segment, i.e. More...
class	Plane
	Class representing an oriented plane in 3D space defined by a base point and a normal direction. More...
class	Polygon2D
	Class representing a planar polygon. More...
class	AlignedRectangle2D
	Class representing an axis aligned rectangle in 2D space. More...
class	Rectangle
	Arbitrary rectangle in 3D space. More...
class	Triangle
	Class representing a triangle in 3D space. More...

Find intersection points or overlapping parts
If the result has the same type as one of the arguments, it is a copy of the first such argument. In all other cases, the choice of variables that do not change the represented object (e.g. sign of normal) is arbitrary. Objects involving NAN or infinity will never intersect.
Utils::Variant< Line, vec3, std::nullptr_t >	intersection (const Line &l1, const Line &l2)
	Compute the intersection between two Lines or LineSegments.
Utils::Variant< Line, vec3, std::nullptr_t >	intersection (const Line &l, const Plane &p)
	Compute the intersection between a Line or LineSegment and a Plane.
Utils::Variant< LineSegment, vec3, std::nullptr_t >	intersection (const Line &l, const Triangle &p)
	Compute the intersection between a Line or LineSegment and a Triangle.
Utils::Variant< LineSegment, vec3, std::nullptr_t >	intersection (const Line &l, const AlignedBox &c)
	Compute the intersection between a Line or LineSegment and a AlignedBox.
std::vector< vec3 >	intersection (const AlignedBox &cuboid, const Plane &plane)
	Compute the intersection between a AlignedBox and a Plane.
Utils::Variant< LineSegment, vec3, std::nullptr_t >	intersection (const Rectangle &p, const LineSegment &l)
	Compute the intersection between a LineSegment and a Rectangle.
Utils::Variant< LineSegment, vec3, std::nullptr_t >	intersection (const Rectangle &p, const Line &l)
	Compute the intersection between a Line and a Rectangle.
Utils::Variant< std::vector< vec3 >, LineSegment, vec3, std::nullptr_t >	intersection (const Rectangle &l, const Rectangle &p)
	Compute the intersection between two Rectangles.
Utils::Variant< AlignedBox, LineSegment, vec3, std::nullptr_t >	intersection (const AlignedBox &c, const AlignedBox &c2)
	Returns intersection between 2 boxes or nullptr in case of no intersection.
Utils::Variant< Plane, Line, std::nullptr_t >	intersection (const Plane &p1, const Plane &p2)
	Compute the intersection between multiple planes.
Utils::Variant< Triangle, LineSegment, vec3, std::nullptr_t >	intersection (const Plane &p, const Triangle &t)
	Compute the intersection between a Plane and a Triangle.
Utils::Variant< AlignedRectangle2D, vec3, std::nullptr_t >	intersection (const AlignedRectangle2D &r1, const AlignedRectangle2D &r2)
	Returns the intersection of 2 rectangles.
Utils::Variant< LineSegment, vec3, std::nullptr_t >	intersectionFast (const Line &l, const Triangle &t)
	Compute the intersection between a Line and a Triangle.
Utils::Variant< LineSegment, vec3, std::nullptr_t >	intersection (const Line &l1, const LineSegment &l2)
	Compute the intersection between two Lines or LineSegments.
Utils::Variant< LineSegment, vec3, std::nullptr_t >	intersection (const LineSegment &l1, const Line &l2)
	Compute the intersection between two Lines or LineSegments.
Utils::Variant< LineSegment, vec3, std::nullptr_t >	intersection (const LineSegment &l1, const LineSegment &l2)
	Compute the intersection between two Lines or LineSegments.
Utils::Variant< LineSegment, vec3, std::nullptr_t >	intersection (const LineSegment &l, const Plane &p)
	Compute the intersection between a Line or LineSegment and a Plane.
Utils::Variant< Line, vec3, std::nullptr_t >	intersection (const Plane &p, const Line &l)
	Compute the intersection between a Line or LineSegment and a Plane.
Utils::Variant< LineSegment, vec3, std::nullptr_t >	intersection (const Plane &p, const LineSegment &l)
	Compute the intersection between a Line or LineSegment and a Plane.
Utils::Variant< LineSegment, vec3, std::nullptr_t >	intersection (const LineSegment &l, const Triangle &p)
	Compute the intersection between a Line or LineSegment and a Triangle.
Utils::Variant< LineSegment, vec3, std::nullptr_t >	intersection (const Triangle &t, const Line &l)
	Compute the intersection between a Line or LineSegment and a Triangle.
Utils::Variant< LineSegment, vec3, std::nullptr_t >	intersection (const Triangle &t, const LineSegment &l)
	Compute the intersection between a Line or LineSegment and a Triangle.
Utils::Variant< LineSegment, vec3, std::nullptr_t >	intersection (const LineSegment &l, const AlignedBox &c)
	Compute the intersection between a Line or LineSegment and a AlignedBox.
Utils::Variant< LineSegment, vec3, std::nullptr_t >	intersection (const AlignedBox &c, const Line &l)
	Compute the intersection between a Line or LineSegment and a AlignedBox.
Utils::Variant< LineSegment, vec3, std::nullptr_t >	intersection (const AlignedBox &c, const LineSegment &l)
	Compute the intersection between a Line or LineSegment and a AlignedBox.
std::vector< vec3 >	intersection (const Plane &plane, const AlignedBox &cuboid)
	Compute the intersection between a AlignedBox and a Plane.
Utils::Variant< LineSegment, vec3, std::nullptr_t >	intersection (const LineSegment &l, const Rectangle &p)
	Compute the intersection between a LineSegment and a Rectangle.
Utils::Variant< LineSegment, vec3, std::nullptr_t >	intersection (const Line &l, const Rectangle &p)
	Compute the intersection between a Line and a Rectangle.
Utils::Variant< Plane, Line, vec3, std::nullptr_t >	intersection (const Plane &p1, const Plane &p2, const Plane &p3)
	Compute the intersection between multiple planes.
Utils::Variant< Triangle, LineSegment, vec3, std::nullptr_t >	intersection (const Triangle &t, const Plane &p)
	Compute the intersection between a Plane and a Triangle.
Utils::Variant< LineSegment, vec3, std::nullptr_t >	intersectionFast (const Triangle &t, const Line &l)
	Compute the intersection between a Line and a Triangle.

Check if, but not how, a pair of objects intersects
Touching at a single point counts as intersection for the purpose of these functions. These are faster than computing the full intersection. Objects involving NAN or infinity will never intersect.
bool	intersects (const AlignedRectangle2D &r1, const AlignedRectangle2D &r2)
	Checks if the two rectangles intersect.
bool	intersects (const AlignedBox &c, const Triangle &t)
	Checks if the box and triangle intersect.
bool	intersects (const AlignedBox &c, const AlignedBox &c2)
	Checks if the two boxes intersect.
bool	intersects (const AlignedBox &cub, const Plane &plane)
	Checks if the box and plane intersect.

Function Documentation

intersection() [1/21]

Utils::Variant< LineSegment, vec3, std::nullptr_t > intersection	(	const Line &	l,
		const Triangle &	p )

#include <ImFusion/Core/Geometry/Intersection.h>

Compute the intersection between a Line or LineSegment and a Triangle.

See also

intersectionFast(const Line&, const Triangle&) for a faster variant in case the input data maintains certain invariants.

intersection() [2/21]

std::vector< vec3 > intersection	(	const AlignedBox &	cuboid,
		const Plane &	plane )

#include <ImFusion/Core/Geometry/Intersection.h>

Compute the intersection between a AlignedBox and a Plane.

Will return between 0 and 6 points which are already sorted to form a convex polygon.

intersection() [3/21]

Utils::Variant< AlignedBox, LineSegment, vec3, std::nullptr_t > intersection	(	const AlignedBox &	c,
		const AlignedBox &	c2 )

#include <ImFusion/Core/Geometry/Intersection.h>

Returns intersection between 2 boxes or nullptr in case of no intersection.

Note that the returned AlignedBox may be flat if the intersection results in a rectangle.

intersection() [4/21]

Utils::Variant< AlignedRectangle2D, vec3, std::nullptr_t > intersection	(	const AlignedRectangle2D &	r1,
		const AlignedRectangle2D &	r2 )

#include <ImFusion/Core/Geometry/Intersection.h>

Returns the intersection of 2 rectangles.

In the case of the intersection being a line, a very slim rectangle is returned.

intersectionFast() [1/2]

Utils::Variant< LineSegment, vec3, std::nullptr_t > intersectionFast	(	const Line &	l,
		const Triangle &	t )

#include <ImFusion/Core/Geometry/Intersection.h>

Compute the intersection between a Line and a Triangle.

Note

This version is faster, but neither object may have values of NAN or infinity, the line must have a proper direction and the triangle must span a non-zero area. Otherwise the behavior is undefined.

If the result is a LineSegment, the sign of the direction vector is arbitrary.

See also

intersection(const Line&, const Triangle&) for a slower but more generic and stable variant of this function.

intersection() [5/21]

Utils::Variant< LineSegment, vec3, std::nullptr_t > intersection	(	const Line &	l1,
		const LineSegment &	l2 )

#include <ImFusion/Core/Geometry/Intersection.h>

Compute the intersection between two Lines or LineSegments.

intersection() [6/21]

Utils::Variant< LineSegment, vec3, std::nullptr_t > intersection	(	const LineSegment &	l1,
		const Line &	l2 )

#include <ImFusion/Core/Geometry/Intersection.h>

Compute the intersection between two Lines or LineSegments.

intersection() [7/21]

Utils::Variant< LineSegment, vec3, std::nullptr_t > intersection	(	const LineSegment &	l1,
		const LineSegment &	l2 )

#include <ImFusion/Core/Geometry/Intersection.h>

Compute the intersection between two Lines or LineSegments.

intersection() [8/21]

Utils::Variant< LineSegment, vec3, std::nullptr_t > intersection	(	const LineSegment &	l,
		const Plane &	p )

#include <ImFusion/Core/Geometry/Intersection.h>

Compute the intersection between a Line or LineSegment and a Plane.

intersection() [9/21]

Utils::Variant< Line, vec3, std::nullptr_t > intersection	(	const Plane &	p,
		const Line &	l )

#include <ImFusion/Core/Geometry/Intersection.h>

Compute the intersection between a Line or LineSegment and a Plane.

intersection() [10/21]

Utils::Variant< LineSegment, vec3, std::nullptr_t > intersection	(	const Plane &	p,
		const LineSegment &	l )

#include <ImFusion/Core/Geometry/Intersection.h>

Compute the intersection between a Line or LineSegment and a Plane.

intersection() [11/21]

Utils::Variant< LineSegment, vec3, std::nullptr_t > intersection	(	const LineSegment &	l,
		const Triangle &	p )

#include <ImFusion/Core/Geometry/Intersection.h>

Compute the intersection between a Line or LineSegment and a Triangle.

See also

intersectionFast(const Line&, const Triangle&) for a faster variant in case the input data maintains certain invariants.

intersection() [12/21]

Utils::Variant< LineSegment, vec3, std::nullptr_t > intersection	(	const Triangle &	t,
		const Line &	l )

#include <ImFusion/Core/Geometry/Intersection.h>

Compute the intersection between a Line or LineSegment and a Triangle.

See also

intersectionFast(const Line&, const Triangle&) for a faster variant in case the input data maintains certain invariants.

intersection() [13/21]

Utils::Variant< LineSegment, vec3, std::nullptr_t > intersection	(	const Triangle &	t,
		const LineSegment &	l )

#include <ImFusion/Core/Geometry/Intersection.h>

Compute the intersection between a Line or LineSegment and a Triangle.

See also

intersectionFast(const Line&, const Triangle&) for a faster variant in case the input data maintains certain invariants.

intersection() [14/21]

Utils::Variant< LineSegment, vec3, std::nullptr_t > intersection	(	const LineSegment &	l,
		const AlignedBox &	c )

#include <ImFusion/Core/Geometry/Intersection.h>

Compute the intersection between a Line or LineSegment and a AlignedBox.

intersection() [15/21]

Utils::Variant< LineSegment, vec3, std::nullptr_t > intersection	(	const AlignedBox &	c,
		const Line &	l )

#include <ImFusion/Core/Geometry/Intersection.h>

Compute the intersection between a Line or LineSegment and a AlignedBox.

intersection() [16/21]

Utils::Variant< LineSegment, vec3, std::nullptr_t > intersection	(	const AlignedBox &	c,
		const LineSegment &	l )

#include <ImFusion/Core/Geometry/Intersection.h>

Compute the intersection between a Line or LineSegment and a AlignedBox.

intersection() [17/21]

std::vector< vec3 > intersection	(	const Plane &	plane,
		const AlignedBox &	cuboid )

#include <ImFusion/Core/Geometry/Intersection.h>

Compute the intersection between a AlignedBox and a Plane.

Will return between 0 and 6 points which are already sorted to form a convex polygon.

intersection() [18/21]

Utils::Variant< LineSegment, vec3, std::nullptr_t > intersection	(	const LineSegment &	l,
		const Rectangle &	p )

#include <ImFusion/Core/Geometry/Intersection.h>

Compute the intersection between a LineSegment and a Rectangle.

intersection() [19/21]

Utils::Variant< LineSegment, vec3, std::nullptr_t > intersection	(	const Line &	l,
		const Rectangle &	p )

#include <ImFusion/Core/Geometry/Intersection.h>

Compute the intersection between a Line and a Rectangle.

intersection() [20/21]

Utils::Variant< Plane, Line, vec3, std::nullptr_t > intersection	(	const Plane &	p1,
		const Plane &	p2,
		const Plane &	p3 )

#include <ImFusion/Core/Geometry/Intersection.h>

Compute the intersection between multiple planes.

intersection() [21/21]

Utils::Variant< Triangle, LineSegment, vec3, std::nullptr_t > intersection	(	const Triangle &	t,
		const Plane &	p )

#include <ImFusion/Core/Geometry/Intersection.h>

Compute the intersection between a Plane and a Triangle.

intersectionFast() [2/2]

Utils::Variant< LineSegment, vec3, std::nullptr_t > intersectionFast	(	const Triangle &	t,
		const Line &	l )

#include <ImFusion/Core/Geometry/Intersection.h>

Compute the intersection between a Line and a Triangle.

Note

This version is faster, but neither object may have values of NAN or infinity, the line must have a proper direction and the triangle must span a non-zero area. Otherwise the behavior is undefined.

If the result is a LineSegment, the sign of the direction vector is arbitrary.

See also

intersection(const Line&, const Triangle&) for a slower but more generic and stable variant of this function.