MeshLib C++ Docs
Loading...
Searching...
No Matches
MRTriMath.h
Go to the documentation of this file.
1#pragma once
2// triangle-related mathematical functions are here
3
4#include "MRVector3.h"
5#include <algorithm>
6#include <cassert>
7#include <cmath>
8#include <limits>
9#include <optional>
10
11namespace MR
12{
13
16template <typename T>
17[[nodiscard]] T circumcircleDiameterSq( const Vector3<T> & a, const Vector3<T> & b, const Vector3<T> & c )
18{
19 const auto ab = ( b - a ).lengthSq();
20 const auto ca = ( a - c ).lengthSq();
21 const auto bc = ( c - b ).lengthSq();
22 if ( ab <= 0 )
23 return ca;
24 if ( ca <= 0 )
25 return bc;
26 if ( bc <= 0 )
27 return ab;
28 const auto f = cross( b - a, c - a ).lengthSq();
29 if ( f <= 0 )
30 return std::numeric_limits<T>::infinity();
31 return ab * ca * bc / f;
32}
33
36template <typename T>
37[[nodiscard]] inline T circumcircleDiameter( const Vector3<T> & a, const Vector3<T> & b, const Vector3<T> & c )
38{
39 return std::sqrt( circumcircleDiameterSq( a, b, c ) );
40}
41
43template <typename T>
44[[nodiscard]] Vector3<T> circumcircleCenter( const Vector3<T> & a, const Vector3<T> & b )
45{
46 const auto xabSq = cross( a, b ).lengthSq();
47 const auto aa = a.lengthSq();
48 const auto bb = b.lengthSq();
49 if ( xabSq <= 0 )
50 {
51 if ( aa <= 0 )
52 return b / T(2);
53 // else b == 0 || a == b
54 return a / T(2);
55 }
56 const auto ab = dot( a, b );
57 return ( bb * ( aa - ab ) * a + aa * ( bb - ab ) * b ) / ( 2 * xabSq );
58}
59
61template <typename T>
62[[nodiscard]] inline Vector3<T> circumcircleCenter( const Vector3<T> & a, const Vector3<T> & b, const Vector3<T> & c )
63{
64 return circumcircleCenter( a - c, b - c ) + c;
65}
66
69template <typename T>
70[[nodiscard]] bool circumballCenters( const Vector3<T> & a, const Vector3<T> & b, const Vector3<T> & c, T radius,
71 Vector3<T> & centerPos, // ball's center from the positive side of triangle
72 Vector3<T> & centerNeg )// ball's center from the negative side of triangle
73{
74 const auto rr = sqr( radius );
75 const auto circRadSq = circumcircleDiameterSq( a, b, c ) / T( 4 );
76 if ( rr < circRadSq )
77 return false;
78
79 const auto x = std::sqrt( rr - circRadSq );
80 const auto xn = x * normal( a, b, c );
81 const auto circCenter = circumcircleCenter( a, b, c );
82 centerPos = circCenter + xn;
83 centerNeg = circCenter - xn;
84
85 return true;
86}
87
90template <typename T>
91[[nodiscard]] T minTriangleAngleSin( const Vector3<T> & a, const Vector3<T> & b, const Vector3<T> & c )
92{
93 const auto ab = ( b - a ).length();
94 const auto ca = ( a - c ).length();
95 const auto bc = ( c - b ).length();
96 if ( ab <= 0 || ca <= 0 || bc <= 0 )
97 return 0;
98 const auto f = cross( b - a, c - a ).length();
99 return f * std::min( { ab, ca, bc } ) / ( ab * ca * bc );
100}
101
102template <typename T>
103[[nodiscard]] T minTriangleAngle( const Vector3<T> & a, const Vector3<T> & b, const Vector3<T> & c )
104{
105 return std::asin( minTriangleAngleSin( a, b, c ) );
106}
107
110template<typename T>
111[[nodiscard]] T triangleAspectRatio( const Vector3<T> & a, const Vector3<T> & b, const Vector3<T> & c )
112{
113 const auto bc = ( c - b ).length();
114 const auto ca = ( a - c ).length();
115 const auto ab = ( b - a ).length();
116 auto halfPerimeter = ( bc + ca + ab ) / 2;
117 auto den = 8 * ( halfPerimeter - bc ) * ( halfPerimeter - ca ) * ( halfPerimeter - ab );
118 if ( den <= 0 )
119 return std::numeric_limits<T>::max();
120
121 return bc * ca * ab / den;
122}
123
125template<typename T>
126[[nodiscard]] inline Vector3<T> dirDblArea( const Triangle3<T> & t )
127{
128 return cross( t[1] - t[0], t[2] - t[0] );
129}
130
132template<typename T>
133[[nodiscard]] inline Vector3<T> dirDblArea( const Vector3<T> & q, const Vector3<T> & r )
134{
135 return cross( q, r );
136}
137
139template<typename T>
140[[nodiscard]] inline Vector3<T> dirDblArea( const Vector3<T> & p, const Vector3<T> & q, const Vector3<T> & r )
141{
142 return cross( q - p, r - p );
143}
144
146template<typename T>
147[[nodiscard]] inline Vector3<T> normal( const Vector3<T> & q, const Vector3<T> & r )
148{
149 return dirDblArea( q, r ).normalized();
150}
151
153template<typename T>
154[[nodiscard]] inline Vector3<T> normal( const Vector3<T> & p, const Vector3<T> & q, const Vector3<T> & r )
155{
156 return normal( q - p, r - p );
157}
158
160template<typename T>
161[[nodiscard]] inline T dblAreaSq( const Vector3<T> & p, const Vector3<T> & q, const Vector3<T> & r )
162{
163 return dirDblArea( p, q, r ).lengthSq();
164}
165
167template<typename T>
168[[nodiscard]] inline T dblArea( const Triangle3<T> & t )
169{
170 return dirDblArea( t ).length();
171}
172
174template<typename T>
175[[nodiscard]] inline T dblArea( const Vector3<T> & p, const Vector3<T> & q, const Vector3<T> & r )
176{
177 return dirDblArea( p, q, r ).length();
178}
179
181template<typename T>
182[[nodiscard]] inline T area( const Vector3<T> & p, const Vector3<T> & q, const Vector3<T> & r )
183{
184 return dblArea( p, q, r ) / 2;
185}
186
188template<typename T>
189[[nodiscard]] inline T dblArea( const Vector2<T> & p, const Vector2<T> & q, const Vector2<T> & r )
190{
191 return std::abs( cross( q - p, r - p ) );
192}
193
195template<typename T>
196[[nodiscard]] inline T area( const Vector2<T> & p, const Vector2<T> & q, const Vector2<T> & r )
197{
198 return dblArea( p, q, r ) / 2;
199}
200
202template <typename T>
203[[nodiscard]] Triangle3<T> makeDegenerate( const Triangle3<T> & t )
204{
205 const auto c = ( t[0] + t[1] + t[2] ) / T(3);
206 int longest = 0;
207 T longestSq = 0;
208 for ( int i = 0; i < 3; ++i )
209 {
210 const auto sq = ( t[i] - c ).lengthSq();
211 if ( longestSq >= sq )
212 continue;
213 longest = i;
214 longestSq = sq;
215 }
216 const auto d = ( t[longest] - c ).normalized();
217
218 // project triangle on the line (c, d)
219 Triangle3<T> res;
220 for ( int i = 0; i < 3; ++i )
221 res[i] = c + d * dot( d, t[i] - c );
222 return res;
223}
224
227template <typename T>
228[[nodiscard]] Triangle3<T> triangleWithNormal( const Triangle3<T> & t, const Vector3<T> & n )
229{
230 const auto c = ( t[0] + t[1] + t[2] ) / T(3);
231 Triangle3<T> res;
232 for ( int i = 0; i < 3; ++i )
233 res[i] = t[i] - n * dot( n, t[i] - c );
234
235 if ( dot( n, dirDblArea( res ) ) < 0 ) // projected triangle has inversed normal
236 res = makeDegenerate( res );
237 return res;
238}
239
245template <typename T>
246[[nodiscard]] T dihedralAngleSin( const Vector3<T>& leftNorm, const Vector3<T>& rightNorm, const Vector3<T>& edgeVec )
247{
248 auto edgeDir = edgeVec.normalized();
249 return dot( edgeDir, cross( leftNorm, rightNorm ) );
250}
251
257template <typename T>
258[[nodiscard]] T dihedralAngleCos( const Vector3<T>& leftNorm, const Vector3<T>& rightNorm )
259{
260 return dot( leftNorm, rightNorm );
261}
262
269template <typename T>
270[[nodiscard]] T dihedralAngle( const Vector3<T>& leftNorm, const Vector3<T>& rightNorm, const Vector3<T>& edgeVec )
271{
272 auto sin = dihedralAngleSin( leftNorm, rightNorm, edgeVec );
273 auto cos = dihedralAngleCos( leftNorm, rightNorm );
274 return std::atan2( sin, cos );
275}
276
280template <typename T>
281[[nodiscard]] std::optional<Vector2<T>> posFromTriEdgeLengths( T a, T b, T c )
282{
283 if ( c == 0 )
284 {
285 if ( a == b )
286 return Vector2<T>{ a, 0 };
287 else
288 return {};
289 }
290 const auto aa = sqr( a );
291 const auto y = ( aa - sqr( b ) + sqr( c ) ) / ( 2 * c );
292 const auto yy = sqr( y );
293 if ( yy > aa )
294 return {};
295 const auto x = std::sqrt( aa - yy );
296 return Vector2<T>{ x, y };
297}
298
302template <typename T>
303[[nodiscard]] std::optional<T> quadrangleOtherDiagonal( T a, T b, T c, T a1, T b1 )
304{
305 const auto p = posFromTriEdgeLengths( a, b, c );
306 if ( !p )
307 return {};
308 auto p1 = posFromTriEdgeLengths( a1, b1, c );
309 if ( !p1 )
310 return {};
311 p1->x = -p1->x;
312 //where the other diagonal crosses axis Oy
313 auto y = ( p->x * p1->y - p1->x * p->y ) / ( p->x - p1->x );
314 if ( y < 0 || y > c )
315 return {};
316 return ( *p - *p1 ).length();
317}
318
322template <typename T>
323[[nodiscard]] inline T tanSqOfHalfAngle( T a, T b, T c )
324{
325 const T den = ( a + b + c ) * ( b + c - a );
326 if ( den <= 0 )
327 return std::numeric_limits<T>::infinity();
328 const T num = ( a + c - b ) * ( a + b - c );
329 if ( num <= 0 )
330 return 0;
331 return num / den;
332}
333
336template <typename T>
337[[nodiscard]] inline T cotan( const Triangle3<T> & t, T absMaxVal = std::numeric_limits<T>::max() )
338{
339 auto a = t[0] - t[2];
340 auto b = t[1] - t[2];
341 auto nom = dot( a, b );
342 auto den = cross( a, b ).length();
343 if ( fabs( nom ) >= absMaxVal * den )
344 return absMaxVal * sgn( nom );
345 return nom / den;
346}
347
351template <typename T>
352[[nodiscard]] inline T cotan( T a, T b, T c )
353{
354 const T den = ( a + b + c ) * ( b + c - a );
355 if ( den <= 0 )
356 return -std::numeric_limits<T>::infinity();
357 const T num = ( a + c - b ) * ( a + b - c );
358 if ( num <= 0 )
359 return std::numeric_limits<T>::infinity();
360 const auto tanSq = num / den;
361 return ( 1 - tanSq ) / ( 2 * std::sqrt( tanSq ) );
362}
363
366template <typename T>
367[[nodiscard]] std::optional<Vector3<T>> gradientInTri( const Vector3<T> & b, const Vector3<T> & c, T vb, T vc )
368{
369 const auto bb = dot( b, b );
370 const auto bc = dot( b, c );
371 const auto cc = dot( c, c );
372 const auto det = bb * cc - bc * bc;
373 if ( det <= 0 )
374 return {};
375 const auto kb = ( 1 / det ) * ( cc * vb - bc * vc );
376 const auto kc = ( 1 / det ) * (-bc * vb + bb * vc );
377 return kb * b + kc * c;
378}
379
382template <typename T>
383[[nodiscard]] std::optional<Vector3<T>> gradientInTri( const Vector3<T> & a, const Vector3<T> & b, const Vector3<T> & c, T va, T vb, T vc )
384{
385 return gradientInTri( b - a, c - a, vb - va, vc - va );
386}
387
388// consider triangle 0BC, where gradient of linear scalar field is given;
389// computes the intersection of the ray (org=0, dir=-grad) with the open line segment BC
390template <typename T>
391[[nodiscard]] std::optional<T> findTriExitPos( const Vector3<T> & b, const Vector3<T> & c, const Vector3<T> & grad )
392{
393 const auto gradSq = grad.lengthSq();
394 if ( gradSq <= 0 )
395 return {};
396 const auto d = c - b;
397 // gort is a vector in the triangle plane orthogonal to grad
398 const auto gort = d - ( dot( d, grad ) / gradSq ) * grad;
399 const auto god = dot( gort, d );
400 if ( god <= 0 )
401 return {};
402 const auto gob = -dot( gort, b );
403 if ( gob <= 0 || gob >= god )
404 return {};
405 const auto a = gob / god;
406 assert( a < std::numeric_limits<T>::max() );
407 const auto ip = a * c + ( 1 - a ) * b;
408 if ( dot( grad, ip ) >= 0 )
409 return {}; // (b,c) is intersected in the direction +grad
410 return a;
411}
412
419template <typename T>
420[[nodiscard]] std::optional<Vector3<T>> tangentPlaneNormalToSpheres( const Vector3<T> & b, const Vector3<T> & c, T rb, T rc )
421{
422 auto grad = gradientInTri( b, c, rb, rc );
423 if ( !grad.has_value() )
424 return {}; // degenerate triangle
425 auto gradSq = grad->lengthSq();
426 if ( gradSq >= 1 )
427 return {}; // the larger of the spheres contains the origin inside - no touch plane exists
428 return sqrt( 1 - gradSq ) * normal( b, c ) - *grad; // unit normal
429}
430
437template <typename T>
438[[nodiscard]] std::optional<Plane3<T>> tangentPlaneToSpheres( const Vector3<T> & a, const Vector3<T> & b, const Vector3<T> & c, T ra, T rb, T rc )
439{
440 if ( auto n = tangentPlaneNormalToSpheres( b - a, c - a, rb - ra, rc - ra ) )
441 return Plane3<T>( *n, dot( *n, a ) + ra );
442 return {}; // the larger of the spheres contains another sphere inside - no touch plane exists
443}
444
445} // namespace MR
length
Definition MRObjectDimensionsEnum.h:14
T minTriangleAngleSin(const Vector3< T > &a, const Vector3< T > &b, const Vector3< T > &c)
Definition MRTriMath.h:91
float area(const MeshTopology &topology, const VertCoords &points, FaceId f)
returns the area of given face
Definition MRMeshMath.h:166
constexpr T sqr(T x) noexcept
squared value
Definition MRMesh/MRMeshFwd.h:666
MRMESH_API float circumcircleDiameter(const MeshTopology &topology, const VertCoords &points, FaceId f)
returns circumcircle diameter of given mesh triangle
MRMESH_API float dihedralAngle(const MeshTopology &topology, const VertCoords &points, UndirectedEdgeId e)
Vector3< T > circumcircleCenter(const Vector3< T > &a, const Vector3< T > &b)
Computes the center of the the triangle's 0AB circumcircle.
Definition MRTriMath.h:44
MRMESH_API float dihedralAngleCos(const MeshTopology &topology, const VertCoords &points, UndirectedEdgeId e)
std::optional< T > findTriExitPos(const Vector3< T > &b, const Vector3< T > &c, const Vector3< T > &grad)
Definition MRTriMath.h:391
std::optional< T > quadrangleOtherDiagonal(T a, T b, T c, T a1, T b1)
Definition MRTriMath.h:303
Triangle3< T > makeDegenerate(const Triangle3< T > &t)
make degenerate triangle (all 3 points on a line) that maximally resembles the input one and has the ...
Definition MRTriMath.h:203
T tanSqOfHalfAngle(T a, T b, T c)
Definition MRTriMath.h:323
Triangle3< T > triangleWithNormal(const Triangle3< T > &t, const Vector3< T > &n)
Definition MRTriMath.h:228
Vector3f dirDblArea(const MeshTopology &topology, const VertCoords &points, FaceId f)
computes directed double area for a triangular face from its vertices
Definition MRMeshMath.h:151
MRMESH_API float triangleAspectRatio(const MeshTopology &topology, const VertCoords &points, FaceId f)
returns aspect ratio of given mesh triangle equal to the ratio of the circum-radius to twice its in-r...
constexpr int sgn(T x) noexcept
sign of given value in { -1, 0, 1 }
Definition MRMesh/MRMeshFwd.h:670
std::optional< Vector3< T > > gradientInTri(const Vector3< T > &b, const Vector3< T > &c, T vb, T vc)
Definition MRTriMath.h:367
std::optional< Plane3< T > > tangentPlaneToSpheres(const Vector3< T > &a, const Vector3< T > &b, const Vector3< T > &c, T ra, T rb, T rc)
Definition MRTriMath.h:438
MRMESH_API float circumcircleDiameterSq(const MeshTopology &topology, const VertCoords &points, FaceId f)
returns squared circumcircle diameter of given mesh triangle
bool circumballCenters(const Vector3< T > &a, const Vector3< T > &b, const Vector3< T > &c, T radius, Vector3< T > &centerPos, Vector3< T > &centerNeg)
Definition MRTriMath.h:70
std::optional< Vector3< T > > tangentPlaneNormalToSpheres(const Vector3< T > &b, const Vector3< T > &c, T rb, T rc)
Definition MRTriMath.h:420
float dblArea(const MeshTopology &topology, const VertCoords &points, FaceId f)
returns twice the area of given face
Definition MRMeshMath.h:160
T minTriangleAngle(const Vector3< T > &a, const Vector3< T > &b, const Vector3< T > &c)
Definition MRTriMath.h:103
std::optional< Vector2< T > > posFromTriEdgeLengths(T a, T b, T c)
Definition MRTriMath.h:281
float cotan(const MeshTopology &topology, const VertCoords &points, UndirectedEdgeId ue)
Definition MRMeshMath.h:306
T dblAreaSq(const Vector3< T > &p, const Vector3< T > &q, const Vector3< T > &r)
computes the square of double area of given triangle
Definition MRTriMath.h:161
MRMESH_API float dihedralAngleSin(const MeshTopology &topology, const VertCoords &points, UndirectedEdgeId e)
Definition MRPlane3.h:17
Definition MRVector2.h:25
Definition MRMesh/MRVector3.h:26
Vector3 normalized() const
Definition MRMesh/MRVector3.h:62
T lengthSq() const
Definition MRMesh/MRVector3.h:53