MeshLib C++ Docs
Loading...
Searching...
No Matches
Classes | Functions
Triangle intersection
Math group

Classes

struct  MR::TriIntersectResult
 

Functions

template<typename T >
bool MR::doTrianglesIntersect (Vector3< T > a, Vector3< T > b, Vector3< T > c, Vector3< T > d, Vector3< T > e, Vector3< T > f)
 
template<typename T >
bool MR::isPointInPlane (const Vector3< T > &p, const Vector3< T > &a, const Vector3< T > &b, const Vector3< T > &c)
 returns true if ABC plane contains point P
 
template<typename T >
bool MR::isPointInLine (const Vector3< T > &p, const Vector3< T > &a, const Vector3< T > &b)
 returns true if AB line contains point P
 
template<typename T >
bool MR::isPointInLine (const Vector2< T > &p, const Vector2< T > &a, const Vector2< T > &b)
 returns true if AB line contains point P
 
template<typename T >
bool MR::isPointInSegm (const Vector3< T > &p, const Vector3< T > &a, const Vector3< T > &b)
 returns true if AB segment contains point P
 
template<typename T >
bool MR::isPointInSegm (const Vector2< T > &p, const Vector2< T > &a, const Vector2< T > &b)
 returns true if AB segment contains point P
 
template<typename T >
bool MR::isPointInTriangle (const Vector3< T > &p, const Vector3< T > &a, const Vector3< T > &b, const Vector3< T > &c)
 returns true if ABC triangle contains point P
 
template<typename T >
bool MR::isPointInTriangle (const Vector2< T > &p, const Vector2< T > &a, const Vector2< T > &b, const Vector2< T > &c)
 returns true if ABC triangle contains point P
 
template<typename T >
bool MR::doesEdgeXySeparate (const Vector3< T > &x, const Vector3< T > &y, const Vector3< T > &z, const Vector3< T > &u, const Vector3< T > &v, const Vector3< T > &w, Vector3< T > d)
 returns true if a plane containing edge XY separates point Z from triangle UVW
 
template<typename T >
bool MR::doTrianglesIntersectExt (const Vector3< T > &a, const Vector3< T > &b, const Vector3< T > &c, const Vector3< T > &d, const Vector3< T > &e, const Vector3< T > &f)
 
template<typename T >
bool MR::doTriangleLineIntersect (const Vector3< T > &a, const Vector3< T > &b, const Vector3< T > &c, const Vector3< T > &d, const Vector3< T > &e)
 checks whether triangle ABC and infinite line DE intersect
 
template<typename T >
bool MR::doTriangleSegmentIntersect (const Vector3< T > &a, const Vector3< T > &b, const Vector3< T > &c, const Vector3< T > &d, const Vector3< T > &e)
 checks whether triangle ABC and segment DE intersect
 
template<typename T >
Vector3< T > MR::findTriangleSegmentIntersection (const Vector3< T > &a, const Vector3< T > &b, const Vector3< T > &c, const Vector3< T > &d, const Vector3< T > &e)
 this function input should have intersection
 
template<typename T >
std::optional< Vector3< T > > MR::findTriangleTriangleIntersection (const Vector3< T > &a, const Vector3< T > &b, const Vector3< T > &c, const Vector3< T > &d, const Vector3< T > &e, const Vector3< T > &f)
 
template<typename T >
std::optional< TriIntersectResult > MR::rayTriangleIntersect (const Vector3< T > &oriA, const Vector3< T > &oriB, const Vector3< T > &oriC, const IntersectionPrecomputes< T > &prec)
 
template<typename T >
std::optional< TriIntersectResult > MR::rayTriangleIntersect (const Vector3< T > &oriA, const Vector3< T > &oriB, const Vector3< T > &oriC, const Vector3< T > &dir)
 
template<typename T >
bool MR::doTrianglesOverlap (const Vector2< T > &a, const Vector2< T > &b, const Vector2< T > &c, const Vector2< T > &d, const Vector2< T > &e, const Vector2< T > &f)
 returns true if ABC and DEF overlaps or touches
 

Detailed Description

Function Documentation

◆ doesEdgeXySeparate()

template<typename T >
bool MR::doesEdgeXySeparate ( const Vector3< T > & x,
const Vector3< T > & y,
const Vector3< T > & z,
const Vector3< T > & u,
const Vector3< T > & v,
const Vector3< T > & w,
Vector3< T > d )

#include <MRTriangleIntersection.h>

returns true if a plane containing edge XY separates point Z from triangle UVW

now d is orthogonal to xy

Parameters
dapproximate normal of the plane

◆ doTriangleLineIntersect()

template<typename T >
bool MR::doTriangleLineIntersect ( const Vector3< T > & a,
const Vector3< T > & b,
const Vector3< T > & c,
const Vector3< T > & d,
const Vector3< T > & e )

#include <MRTriangleIntersection.h>

checks whether triangle ABC and infinite line DE intersect

segment AC is located at one side of the plane DEB

segment AB is located at one side of the plane DEC

segment BC is located at one side of the plane DEA

◆ doTriangleSegmentIntersect()

template<typename T >
bool MR::doTriangleSegmentIntersect ( const Vector3< T > & a,
const Vector3< T > & b,
const Vector3< T > & c,
const Vector3< T > & d,
const Vector3< T > & e )

#include <MRTriangleIntersection.h>

checks whether triangle ABC and segment DE intersect

segment DE is located at one side of the plane ABC

◆ doTrianglesIntersect()

template<typename T >
bool MR::doTrianglesIntersect ( Vector3< T > a,
Vector3< T > b,
Vector3< T > c,
Vector3< T > d,
Vector3< T > e,
Vector3< T > f )

#include <MRTriangleIntersection.h>

checks whether triangles ABC and DEF intersect returns false if ABC and DEF are coplanar

segment DE is located at one side of the plane ABC

segment FD is located at one side of the plane ABC

triangle DEF is located at one side of the plane ABC

segment AB is located at one side of the plane DEF

segment CA is located at one side of the plane DEF

triangle ABC is located at one side of the plane DEF

now segments DE and FD are crossed by the plane ABC: D at one side and EF at the other

now segments AB and CA are crossed by the plane DEF: A at one side and BC at the other

AB segment penetrates triangle DEF since points E and F are at distinct sides of ABD

DE segment penetrates triangle ABC since points B and C are at distinct sides of ADE

AB and DF segments are in the same plane, and AC and DE segments are in other same plane => triangles intersect, but no edge intersect the interior of other triangle

AC segment penetrates triangle DEF since points E and F are at distinct sides of ACD

DF segment penetrates triangle ABC since points B and C are at distinct sides of ADF

AB and DE segments are in the same plane, and AC and DF segments are in other same plane => triangles intersect, but no edge intersect the interior of other triangle

◆ doTrianglesIntersectExt()

template<typename T >
bool MR::doTrianglesIntersectExt ( const Vector3< T > & a,
const Vector3< T > & b,
const Vector3< T > & c,
const Vector3< T > & d,
const Vector3< T > & e,
const Vector3< T > & f )

#include <MRTriangleIntersection.h>

checks whether triangles ABC and DEF intersect; performs more checks to avoid false positives of simple doTrianglesIntersect

direction from center to center

◆ doTrianglesOverlap()

template<typename T >
bool MR::doTrianglesOverlap ( const Vector2< T > & a,
const Vector2< T > & b,
const Vector2< T > & c,
const Vector2< T > & d,
const Vector2< T > & e,
const Vector2< T > & f )

#include <MRTriangleIntersection.h>

returns true if ABC and DEF overlaps or touches

TODO: probably some of the checks are excessive?

check if AB intersects any of DEF sides

check if AC intersects any of DEF sides

check if BC intersects any of DEF sides

no sides intersection: either ABC fully inside DEF or vice versa

◆ findTriangleSegmentIntersection()

template<typename T >
Vector3< T > MR::findTriangleSegmentIntersection ( const Vector3< T > & a,
const Vector3< T > & b,
const Vector3< T > & c,
const Vector3< T > & d,
const Vector3< T > & e )

#include <MRTriangleIntersection.h>

this function input should have intersection

◆ findTriangleTriangleIntersection()

template<typename T >
std::optional< Vector3< T > > MR::findTriangleTriangleIntersection ( const Vector3< T > & a,
const Vector3< T > & b,
const Vector3< T > & c,
const Vector3< T > & d,
const Vector3< T > & e,
const Vector3< T > & f )

#include <MRTriangleIntersection.h>

returns any intersection point of triangle ABC and triangle DEF, if they intersects returns nullopt if they do not intersect (also might return nullopt in degenerated cases)

◆ isPointInLine() [1/2]

template<typename T >
bool MR::isPointInLine ( const Vector2< T > & p,
const Vector2< T > & a,
const Vector2< T > & b )

#include <MRTriangleIntersection.h>

returns true if AB line contains point P

◆ isPointInLine() [2/2]

template<typename T >
bool MR::isPointInLine ( const Vector3< T > & p,
const Vector3< T > & a,
const Vector3< T > & b )

#include <MRTriangleIntersection.h>

returns true if AB line contains point P

◆ isPointInPlane()

template<typename T >
bool MR::isPointInPlane ( const Vector3< T > & p,
const Vector3< T > & a,
const Vector3< T > & b,
const Vector3< T > & c )

#include <MRTriangleIntersection.h>

returns true if ABC plane contains point P

◆ isPointInSegm() [1/2]

template<typename T >
bool MR::isPointInSegm ( const Vector2< T > & p,
const Vector2< T > & a,
const Vector2< T > & b )

#include <MRTriangleIntersection.h>

returns true if AB segment contains point P

◆ isPointInSegm() [2/2]

template<typename T >
bool MR::isPointInSegm ( const Vector3< T > & p,
const Vector3< T > & a,
const Vector3< T > & b )

#include <MRTriangleIntersection.h>

returns true if AB segment contains point P

◆ isPointInTriangle() [1/2]

template<typename T >
bool MR::isPointInTriangle ( const Vector2< T > & p,
const Vector2< T > & a,
const Vector2< T > & b,
const Vector2< T > & c )

#include <MRTriangleIntersection.h>

returns true if ABC triangle contains point P

ab parallel ac

fully degenerated

ab ac looking in the opposite directions so check BC segm

ab ac looking in the same direction and AB is longer so check AB segm

ab ac looking in the same direction and AC is longer so check AC segm

◆ isPointInTriangle() [2/2]

template<typename T >
bool MR::isPointInTriangle ( const Vector3< T > & p,
const Vector3< T > & a,
const Vector3< T > & b,
const Vector3< T > & c )

#include <MRTriangleIntersection.h>

returns true if ABC triangle contains point P

ab parallel ac

fully degenerated

ab ac looking in the opposite directions so check BC segm

ab ac looking in the same direction and AB is longer so check AB segm

ab ac looking in the same direction and AC is longer so check AC segm

◆ rayTriangleIntersect() [1/2]

template<typename T >
std::optional< TriIntersectResult > MR::rayTriangleIntersect ( const Vector3< T > & oriA,
const Vector3< T > & oriB,
const Vector3< T > & oriC,
const IntersectionPrecomputes< T > & prec )

#include <MRTriangleIntersection.h>

due to fused multiply-add (FMA): (A*B-A*B) can be different from zero, so we need epsilon

U,V,W have clearly different signs, so the ray misses the triangle

◆ rayTriangleIntersect() [2/2]

template<typename T >
std::optional< TriIntersectResult > MR::rayTriangleIntersect ( const Vector3< T > & oriA,
const Vector3< T > & oriB,
const Vector3< T > & oriC,
const Vector3< T > & dir )

#include <MRTriangleIntersection.h>