The span arithmetic that traces a composition along a ray: each operand's spans (where the ray is inside it, see RaySpansT), combined by union, intersection and complement, mapped through affine maps, and read for the first crossing. The fused operations, BVHUnion and Tape all trace through it. More...

#include <cmath>
#include <cstdint>
#include "EBGeometry_Macros.hpp"
#include "EBGeometry_Math.hpp"
#include "EBGeometry_Ray.hpp"

Include dependency graph for EBGeometry_RaySpans.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	EBGeometry::RayDetail::MappedRay< T >
	A ray seen through an affine map, with the interval it is traced over: what the operand of the map is traced with. More...

struct	EBGeometry::RayDetail::CrossingPairer< T >
	Pairs crossings, in order, into spans: a span from each crossing the ray enters at to the next it leaves at. More...

Namespaces
namespace	EBGeometry
	Namespace containing all of EBGeometry's functionality.

Functions
template<class T >
SpanEndT< T >	EBGeometry::RayDetail::openAt (const T a_t) noexcept
	An end that is no crossing.

template<class T >
SpanEndT< T >	EBGeometry::RayDetail::endOf (const HitT< T > &a_hit) noexcept
	The end a hit is.

template<class T >
void	EBGeometry::RayDetail::copySpans (const RaySpansT< T > &a_from, RaySpansT< T > &a_to) noexcept
	Copy a list, only as many spans as it holds.

template<class T >
RaySpansT< T >::Span	EBGeometry::RayDetail::cut (const typename RaySpansT< T >::Span &a_span, const T a_horizon) noexcept
	A span cut to a horizon: an end beyond it becomes an Open end there.

template<class T >
void	EBGeometry::RayDetail::unite (const RaySpansT< T > &a_a, const RaySpansT< T > &a_b, RaySpansT< T > &a_out) noexcept
	The union of two lists: where the ray is inside either.

template<class T >
void	EBGeometry::RayDetail::intersect (const RaySpansT< T > &a_a, const RaySpansT< T > &a_b, RaySpansT< T > &a_out) noexcept
	The intersection of two lists: where the ray is inside both.

template<class T >
void	EBGeometry::RayDetail::cutTo (const T a_horizon, RaySpansT< T > &a_spans) noexcept
	Cut a list to a horizon: spans that begin beyond it dropped, and ends beyond it Open ends there.

template<class T >
void	EBGeometry::RayDetail::keepFirst (RaySpansT< T > &a_spans) noexcept
	Keep a list only up to its first crossing, which is all a union asked for its first crossing needs: the horizon there.

template<class T >
void	EBGeometry::RayDetail::uniteInto (RaySpansT< T > &a_spans, const RaySpansT< T > &a_operand) noexcept
	Unite a list into another, in place: each of the operand's spans merged with the spans it meets, or inserted between them.

template<class T >
void	EBGeometry::RayDetail::intersectInto (RaySpansT< T > &a_spans, const RaySpansT< T > &a_operand, RaySpansT< T > &a_scratch) noexcept
	Intersect a list with another, in place.

template<class T >
void	EBGeometry::RayDetail::complement (const RaySpansT< T > &a_a, const T a_t0, RaySpansT< T > &a_out) noexcept
	The complement of a list over [a_t0, a_t1]: where the ray is outside. A crossing is the same crossing seen from the other side; its normal, worked out at the end, is reversed then.

template<class T >
MappedRay< T >	EBGeometry::RayDetail::mapRay (const T *a_map, const RayT< T > &a_ray, const T a_t0, const T a_t1) noexcept
	A ray mapped by an affine map (CSGOps::affinePoint()'s coefficients: the matrix's rows, then the shift).

template<class T >
void	EBGeometry::RayDetail::mapBack (const MappedRay< T > &a_mapped, const T a_t0, const T a_t1, RaySpansT< T > &a_spans) noexcept
	Map an operand's list, traced along a mapped ray, back to the original ray: distances divided by the scale.

template<class T >
Vec3T< T >	EBGeometry::RayDetail::mapNormalBack (const T *a_map, const Vec3T< T > &a_normal) noexcept
	A normal of the operand of an affine map, mapped back to the original frame: by the transposed matrix, and normalized.

template<class T >
void	EBGeometry::RayDetail::nameLeaf (const uint32_t a_leaf, RaySpansT< T > &a_spans) noexcept
	Name the leaf every crossing of a list lies on.

template<class T >
void	EBGeometry::RayDetail::offsetLeaves (const uint32_t a_offset, RaySpansT< T > &a_spans) noexcept
	Shift the leaves every crossing of a list names by an offset: an operand's own leaves, numbered among its composition's.

template<class T , class S >
bool	EBGeometry::RayDetail::insideAt (const S &a_shape, const Vec3T< T > &a_point) noexcept
	Whether a point is inside a shape: within its box, and its value negative.

template<class T , class S >
HitT< T >	EBGeometry::RayDetail::shapeHit (const S &a_shape, const RayT< T > &a_ray, const T a_t0, const T a_t1, const RayOptions< T > &a_options) noexcept
	A shape's first crossing along a ray (firstHit()).

template<class T , class S >
void	EBGeometry::RayDetail::firstSpan (const S &a_shape, const RayT< T > &a_ray, const T a_t0, const T a_t1, const RayOptions< T > &a_options, RaySpansT< T > &a_spans) noexcept
	The list up to a shape's first crossing, from firstHit(): a span from it if the ray enters there, or to it if the ray starts inside; the horizon there.

template<class T , class S >
void	EBGeometry::RayDetail::crossingSpans (const S &a_shape, const RayT< T > &a_ray, const T a_t0, const T a_t1, const RayOptions< T > &a_options, RaySpansT< T > &a_spans) noexcept
	Every span of a shape over an interval, from firstHit() called from one crossing to the next.

template<class T , class S >
void	EBGeometry::RayDetail::shapeSpans (const S &a_shape, const RayT< T > &a_ray, const T a_t0, const T a_t1, const RayOptions< T > &a_options, const bool a_firstOnly, RaySpansT< T > &a_spans) noexcept
	A shape's list over an interval: from its ray form's spans() if it has one, and otherwise from firstHit(), up to the first crossing (firstSpan()) or from crossing to crossing (crossingSpans()).

template<class T , class S >
void	EBGeometry::RayDetail::spansWithin (const S &a_shape, const RayT< T > &a_ray, const RaySpansT< T > &a_within, const RayOptions< T > &a_options, const bool a_firstOnly, RaySpansT< T > &a_piece, RaySpansT< T > &a_spans) noexcept
	A marched operand's list within another list's spans: what an intersection asks a marched operand for once its other operands are known, since outside their spans the intersection is empty whatever the operand does.

template<class T , class S >
HitT< T >	EBGeometry::RayDetail::leafHit (const S &a_shape, const RayT< T > &a_ray, const T a_t, const RayOptions< T > &a_options) noexcept
	A shape's crossing at a distance along a ray, with its normal and primitive: what a composition asks the leaf its trace ended on.

template<class T , class Trace , class Resolve >
HitT< T >	EBGeometry::RayDetail::traceSpans (const Trace &a_trace, const Resolve &a_resolve, const RayT< T > &a_ray, const T a_tMin, const T a_tMax) noexcept
	The first crossing of a composition along a ray, from its lists: the first crossing in the list, if it comes no later than the list's horizon; otherwise the trace starts again from the horizon.

Detailed Description

The span arithmetic that traces a composition along a ray: each operand's spans (where the ray is inside it, see RaySpansT), combined by union, intersection and complement, mapped through affine maps, and read for the first crossing. The fused operations, BVHUnion and Tape all trace through it.

Every list is complete up to its horizon. A combination is complete up to the smaller of its operands' horizons, and a span that reaches past it ends there with an Open end. The first crossing of the whole is read from the final list; where the list's horizon comes before any crossing, the trace starts again from the horizon (traceSpans()). An operand under unions only needs its first crossing (the union's first crossing is the nearest of its operands', unless the ray starts inside one), so it is asked for that alone, and its horizon is there; an operand of an intersection or a complement is asked for all its spans.

Author: Robert Marskar

Function Documentation

◆ complement()

template<class T >

void EBGeometry::RayDetail::complement	(	const RaySpansT< T > &	a_a,
		const T	a_t0,
		RaySpansT< T > &	a_out
	)

inlinenoexcept

The complement of a list over [a_t0, a_t1]: where the ray is outside. A crossing is the same crossing seen from the other side; its normal, worked out at the end, is reversed then.

Internal helper; not part of the public API. Complete up to the list's horizon.

Template Parameters

T	Floating-point precision.

Parameters

[in]	a_a	The list.
[in]	a_t0	Start of the interval.
[out]	a_out	The complement; not the list.

◆ copySpans()

template<class T >

void EBGeometry::RayDetail::copySpans	(	const RaySpansT< T > &	a_from,
		RaySpansT< T > &	a_to
	)

inlinenoexcept

Copy a list, only as many spans as it holds.

Internal helper; not part of the public API.

Template Parameters

T	Floating-point precision.

Parameters

[in]	a_from	The list.
[out]	a_to	The copy.

◆ crossingSpans()

template<class T , class S >

void EBGeometry::RayDetail::crossingSpans	(	const S &	a_shape,
		const RayT< T > &	a_ray,
		const T	a_t0,
		const T	a_t1,
		const RayOptions< T > &	a_options,
		RaySpansT< T > &	a_spans
	)

inlinenoexcept

Every span of a shape over an interval, from firstHit() called from one crossing to the next.

Internal helper; not part of the public API. What a shape without spans() (see RayForm) gives an intersection or a complement: each search starts a step (RayOptions::m_tolerance, times the scale) past the last crossing.

Template Parameters

T	Floating-point precision.
S	Shape type.

Parameters

[in]	a_shape	The shape.
[in]	a_ray	The ray.
[in]	a_t0	Start of the interval.
[in]	a_t1	End of the interval.
[in]	a_options	How to march.
[out]	a_spans	The list.

◆ cut()

template<class T >

RaySpansT< T >::Span EBGeometry::RayDetail::cut	(	const typename RaySpansT< T >::Span &	a_span,
		const T	a_horizon
	)

inlinenoexcept

A span cut to a horizon: an end beyond it becomes an Open end there.

Internal helper; not part of the public API.

Template Parameters

T	Floating-point precision.

Parameters

[in]	a_span	The span; it begins at or before the horizon.
[in]	a_horizon	The horizon.

Returns: The span.

◆ cutTo()

template<class T >

void EBGeometry::RayDetail::cutTo	(	const T	a_horizon,
		RaySpansT< T > &	a_spans
	)

inlinenoexcept

Cut a list to a horizon: spans that begin beyond it dropped, and ends beyond it Open ends there.

Internal helper; not part of the public API.

Template Parameters

T	Floating-point precision.

Parameters

[in]	a_horizon	The horizon; no later than the list's.
[in,out]	a_spans	The list.

◆ endOf()

template<class T >

SpanEndT< T > EBGeometry::RayDetail::endOf ( const HitT< T > & a_hit )

inlinenoexcept

The end a hit is.

Internal helper; not part of the public API.

Template Parameters

T	Floating-point precision.

Parameters

[in] a_hit The hit.

Returns: The end.

◆ firstSpan()

template<class T , class S >

void EBGeometry::RayDetail::firstSpan	(	const S &	a_shape,
		const RayT< T > &	a_ray,
		const T	a_t0,
		const T	a_t1,
		const RayOptions< T > &	a_options,
		RaySpansT< T > &	a_spans
	)

inlinenoexcept

The list up to a shape's first crossing, from firstHit(): a span from it if the ray enters there, or to it if the ray starts inside; the horizon there.

Internal helper; not part of the public API. Where the ray crosses nothing, the list is the whole interval if the ray is inside throughout, and empty otherwise. An unresolved query leaves the horizon where it stopped.

Template Parameters

T	Floating-point precision.
S	Shape type.

Parameters

[in]	a_shape	The shape.
[in]	a_ray	The ray.
[in]	a_t0	Start of the interval.
[in]	a_t1	End of the interval.
[in]	a_options	How to march.
[out]	a_spans	The list.

◆ insideAt()

template<class T , class S >

bool EBGeometry::RayDetail::insideAt	(	const S &	a_shape,
		const Vec3T< T > &	a_point
	)

inlinenoexcept

Whether a point is inside a shape: within its box, and its value negative.

Internal helper; not part of the public API. What a list needs where the ray crosses nothing in the interval: whether it is inside throughout.

Template Parameters

T	Floating-point precision.
S	Shape type.

Parameters

[in]	a_shape	The shape.
[in]	a_point	The point.

Returns: True if inside.

◆ intersect()

template<class T >

void EBGeometry::RayDetail::intersect	(	const RaySpansT< T > &	a_a,
		const RaySpansT< T > &	a_b,
		RaySpansT< T > &	a_out
	)

inlinenoexcept

The intersection of two lists: where the ray is inside both.

Internal helper; not part of the public API. Complete up to the smaller horizon. Where two ends meet, the crossing wins, since the ray crosses the other operand's surface there.

Template Parameters

T	Floating-point precision.

Parameters

[in]	a_a	One list.
[in]	a_b	The other.
[out]	a_out	The intersection; not one of the two.

◆ intersectInto()

template<class T >

void EBGeometry::RayDetail::intersectInto	(	RaySpansT< T > &	a_spans,
		const RaySpansT< T > &	a_operand,
		RaySpansT< T > &	a_scratch
	)

inlinenoexcept

Intersect a list with another, in place.

Internal helper; not part of the public API.

Template Parameters

T	Floating-point precision.

Parameters

[in,out]	a_spans	The list.
[in]	a_operand	The list to intersect it with.
[in,out]	a_scratch	Scratch.

◆ keepFirst()

template<class T >

void EBGeometry::RayDetail::keepFirst ( RaySpansT< T > & a_spans )

inlinenoexcept

Keep a list only up to its first crossing, which is all a union asked for its first crossing needs: the horizon there.

Internal helper; not part of the public API. A shorter list makes the next union cheaper, and the next operand is traced only up to it.

Template Parameters

T	Floating-point precision.

Parameters

[in,out] a_spans The list.

◆ leafHit()

template<class T , class S >

HitT< T > EBGeometry::RayDetail::leafHit	(	const S &	a_shape,
		const RayT< T > &	a_ray,
		const T	a_t,
		const RayOptions< T > &	a_options
	)

inlinenoexcept

A shape's crossing at a distance along a ray, with its normal and primitive: what a composition asks the leaf its trace ended on.

Internal helper; not part of the public API. Calls the shape's firstHit() over a window of RayOptions::m_tolerance times its scale around a_t, and takes the crossing nearest a_t. Where rounding leaves the window empty, the normal is the shape's gradient.

Template Parameters

T	Floating-point precision.
S	Shape type.

Parameters

[in]	a_shape	The shape.
[in]	a_ray	The ray.
[in]	a_t	The crossing's distance.
[in]	a_options	How to march.

Returns: The crossing (its m_normal, m_primitive and m_exact).

◆ mapBack()

template<class T >

void EBGeometry::RayDetail::mapBack	(	const MappedRay< T > &	a_mapped,
		const T	a_t0,
		const T	a_t1,
		RaySpansT< T > &	a_spans
	)

inlinenoexcept

Map an operand's list, traced along a mapped ray, back to the original ray: distances divided by the scale.

Internal helper; not part of the public API. The ends of the interval map back to exactly the ends of the original one, so that a list complete over the mapped interval is complete over the original, and every distance stays inside it.

Template Parameters

T	Floating-point precision.

Parameters

[in]	a_mapped	The mapped ray.
[in]	a_t0	Start of the original interval.
[in]	a_t1	End of the original interval.
[in,out]	a_spans	The operand's list, mapped in place.

◆ mapNormalBack()

template<class T >

Vec3T< T > EBGeometry::RayDetail::mapNormalBack	(	const T *	a_map,
		const Vec3T< T > &	a_normal
	)

inlinenoexcept

A normal of the operand of an affine map, mapped back to the original frame: by the transposed matrix, and normalized.

Internal helper; not part of the public API.

Template Parameters

T	Floating-point precision.

Parameters

[in]	a_map	The map's coefficients.
[in]	a_normal	The operand's normal.

Returns: The normal.

◆ mapRay()

template<class T >

MappedRay< T > EBGeometry::RayDetail::mapRay	(	const T *	a_map,
		const RayT< T > &	a_ray,
		const T	a_t0,
		const T	a_t1
	)

inlinenoexcept

A ray mapped by an affine map (CSGOps::affinePoint()'s coefficients: the matrix's rows, then the shift).

Internal helper; not part of the public API.

Template Parameters

T	Floating-point precision.

Parameters

[in]	a_map	The map's coefficients.
[in]	a_ray	The ray.
[in]	a_t0	Start of the interval.
[in]	a_t1	End of the interval.

Returns: The mapped ray.

◆ nameLeaf()

template<class T >

void EBGeometry::RayDetail::nameLeaf	(	const uint32_t	a_leaf,
		RaySpansT< T > &	a_spans
	)

inlinenoexcept

Name the leaf every crossing of a list lies on.

Internal helper; not part of the public API.

Template Parameters

T	Floating-point precision.

Parameters

[in]	a_leaf	The leaf.
[in,out]	a_spans	The list.

◆ offsetLeaves()

template<class T >

void EBGeometry::RayDetail::offsetLeaves	(	const uint32_t	a_offset,
		RaySpansT< T > &	a_spans
	)

inlinenoexcept

Shift the leaves every crossing of a list names by an offset: an operand's own leaves, numbered among its composition's.

Internal helper; not part of the public API.

Template Parameters

T	Floating-point precision.

Parameters

[in]	a_offset	The operand's first leaf.
[in,out]	a_spans	The list.

◆ openAt()

template<class T >

SpanEndT< T > EBGeometry::RayDetail::openAt ( const T a_t )

inlinenoexcept

An end that is no crossing.

Internal helper; not part of the public API.

Template Parameters

T	Floating-point precision.

Parameters

[in] a_t Where it is.

Returns: The end.

◆ shapeHit()

template<class T , class S >

HitT< T > EBGeometry::RayDetail::shapeHit	(	const S &	a_shape,
		const RayT< T > &	a_ray,
		const T	a_t0,
		const T	a_t1,
		const RayOptions< T > &	a_options
	)

inlinenoexcept

A shape's first crossing along a ray (firstHit()).

Internal helper; not part of the public API. What the span code and leafHit() call on an operand or a leaf: out of line on a device for every shape, so that a kernel holds one copy of each shape's trace (see CalledOutOfLine).

Template Parameters

T	Floating-point precision.
S	Shape type.

Parameters

[in]	a_shape	The shape.
[in]	a_ray	The ray, with a unit direction.
[in]	a_t0	Start of the interval.
[in]	a_t1	End of the interval.
[in]	a_options	How to march.

Returns: The crossing, a miss, or an unresolved query.

◆ shapeSpans()

template<class T , class S >

void EBGeometry::RayDetail::shapeSpans	(	const S &	a_shape,
		const RayT< T > &	a_ray,
		const T	a_t0,
		const T	a_t1,
		const RayOptions< T > &	a_options,
		const bool	a_firstOnly,
		RaySpansT< T > &	a_spans
	)

inlinenoexcept

A shape's list over an interval: from its ray form's spans() if it has one, and otherwise from firstHit(), up to the first crossing (firstSpan()) or from crossing to crossing (crossingSpans()).

Internal helper; not part of the public API. What a composition asks of each operand.

Template Parameters

T	Floating-point precision.
S	Shape type.

Parameters

[in]	a_shape	The shape.
[in]	a_ray	The ray.
[in]	a_t0	Start of the interval.
[in]	a_t1	End of the interval.
[in]	a_options	How to march.
[in]	a_firstOnly	Whether only the first crossing is needed.
[out]	a_spans	The list.

◆ spansWithin()

template<class T , class S >

void EBGeometry::RayDetail::spansWithin	(	const S &	a_shape,
		const RayT< T > &	a_ray,
		const RaySpansT< T > &	a_within,
		const RayOptions< T > &	a_options,
		const bool	a_firstOnly,
		RaySpansT< T > &	a_piece,
		RaySpansT< T > &	a_spans
	)

inlinenoexcept

A marched operand's list within another list's spans: what an intersection asks a marched operand for once its other operands are known, since outside their spans the intersection is empty whatever the operand does.

Internal helper; not part of the public API. The operand is traced (shapeSpans()) over each span of the other list in turn, and the list is its spans there: the intersection with the other list is the same as with the operand's whole list. With a_firstOnly, it stops at the first span it finds, its horizon where that trace stopped: the intersection's first crossing comes no later. It also stops where a trace is known no further, or the list is full.

Template Parameters

T	Floating-point precision.
S	Shape type.

Parameters

[in]	a_shape	The operand.
[in]	a_ray	The ray.
[in]	a_within	The other list.
[in]	a_options	How to march.
[in]	a_firstOnly	Whether only the intersection's first crossing is needed.
[out]	a_piece	Scratch for one span's trace.
[out]	a_spans	The list; not the other list.

◆ traceSpans()

template<class T , class Trace , class Resolve >

HitT< T > EBGeometry::RayDetail::traceSpans	(	const Trace &	a_trace,
		const Resolve &	a_resolve,
		const RayT< T > &	a_ray,
		const T	a_tMin,
		const T	a_tMax
	)

inlinenoexcept

The first crossing of a composition along a ray, from its lists: the first crossing in the list, if it comes no later than the list's horizon; otherwise the trace starts again from the horizon.

Internal helper; not part of the public API. A_trace(t0, t1, allSpans, spans) writes the composition's list over [t0, t1]; allSpans asks every operand for all its spans, which a trace that gets no further (its horizon at its start) is repeated with. A query that still gets no further, or starts again too many times (64 passes), is unresolved. A_resolve(t, leaf) then gives the crossing's normal and primitive, from the leaf its end names.

Template Parameters

T	Floating-point precision.
Trace	Callable writing the list.
Resolve	Callable giving the crossing on a leaf.

Parameters

[in]	a_trace	The trace.
[in]	a_resolve	The crossing on a leaf.
[in]	a_ray	The ray.
[in]	a_tMin	Start of the interval.
[in]	a_tMax	End of the interval.

Returns: The crossing, a miss, or an unresolved query.

◆ unite()

template<class T >

void EBGeometry::RayDetail::unite	(	const RaySpansT< T > &	a_a,
		const RaySpansT< T > &	a_b,
		RaySpansT< T > &	a_out
	)

inlinenoexcept

The union of two lists: where the ray is inside either.

Internal helper; not part of the public API. Complete up to the smaller horizon. Where two ends meet, the one that is no crossing wins, since the ray is inside the other operand there.

Template Parameters

T	Floating-point precision.

Parameters

[in]	a_a	One list.
[in]	a_b	The other.
[out]	a_out	The union; not one of the two.

◆ uniteInto()

template<class T >

void EBGeometry::RayDetail::uniteInto	(	RaySpansT< T > &	a_spans,
		const RaySpansT< T > &	a_operand
	)

inlinenoexcept

Unite a list into another, in place: each of the operand's spans merged with the spans it meets, or inserted between them.

Internal helper; not part of the public API. Complete up to the smaller horizon. No list is copied: on a device every span copied is local memory traffic, which is most of what tracing costs there.

Template Parameters

T	Floating-point precision.

Parameters

[in,out]	a_spans	The list.
[in]	a_operand	The list to unite into it.

Classes

Namespaces

Functions

Detailed Description

Function Documentation

◆ complement()

◆ copySpans()

◆ crossingSpans()

◆ cut()

◆ cutTo()

◆ endOf()

◆ firstSpan()

◆ insideAt()

◆ intersect()

◆ intersectInto()

◆ keepFirst()

◆ leafHit()

◆ mapBack()

◆ mapNormalBack()

◆ mapRay()

◆ nameLeaf()

◆ offsetLeaves()

◆ openAt()

◆ shapeHit()

◆ shapeSpans()

◆ spansWithin()

◆ traceSpans()

◆ unite()

◆ uniteInto()