davideberly / geometrictools Goto Github PK

Hello,

I think this function tests if a 2D point is on the Arc ? on the "line" of the arc, right ? not inside the surface of the "pie" ?

If i'm right, then i don't understand why the function returns "true" when i test if the Arc[ACB] Contains the point "D" :

Thank your for your advice,

Johan

I have created a ConstrainedDelaunay2 and added the following 7 vertices: (-1, -1), (-1, 1), (1, -1), (0, 0), (0, -1), (-1, 0), (0, 0).
When I insert the edge (3, 4) I get the error "Failed to find vertex in graph." in GetLinkEdges. I assume this has something to do with the duplicated vertex. The vmap in GetLinkEdges contains only 6 vertices. But GetNumVertices() and GetNumUniqueVertices() of ConstrainedDelaunay2 both return 7. Might this be a bug or isn't it allowed to add duplicated vertices or am I doing something else wrong? I would very appreciate any help.

Lack of them makes these tools inconvenient to work with in some situations.

Hi,
Thanks for fixing #16. I have a rigid body represented by an STL surface mesh. After having called void Update(Real t, Real dt) of RigidBody I would like to update the position, displacement, and linear velocity of an arbitrary point on the rigid body. I had two questions:

1. Are those functions taking an arbitrary point baked into GeometricTools somewhere that I could use? I could not find them in RigidBody.
2. If not, could you point me to the appropriate equations in Game Physics? I thought I had found them in section 2.2.2 but I'm not really sure on that.

Many thanks,
Andy

Possible bug if intervals do not overlap. iiQuery will return no intersection and zeros in overlap.
result.intersect still be true and result.numIntersections contains wrong value

In ApprQuadratic3.h the comments say

// ...K = C[0],
// B = (C[1],C[2],C[3]), and A is a 3x3 symmetric matrix with
// A00 = C[4], A11 = C[5], A22 = C[6], A01 = C[7]/2, A02 = C[8]/2, and
// A12 = C[9]/2 ...

and you pass the eigenvector as is into the coefficients

es.GetEigenvector(0, &coefficients[0]);

But in QuadricSurface.h the matrix A is filled with

mC = mCoefficient[0];
mB[0] = mCoefficient[1];
mB[1] = mCoefficient[2];
mB[2] = mCoefficient[3];
mA(0, 0) = mCoefficient[4];
mA(0, 1) = (Real)0.5 * mCoefficient[5];
mA(0, 2) = (Real)0.5 * mCoefficient[6];
mA(1, 0) = mA(0, 1);
mA(1, 1) = mCoefficient[7];
mA(1, 2) = (Real)0.5 * mCoefficient[8];
mA(2, 0) = mA(0, 2);
mA(2, 1) = mA(1, 2);
mA(2, 2) = mCoefficient[9];

The offdiagonal elements don't fit the comments, correct?

There is a problem with accuracy which leads to wrong results.
Here is an example. We have one circle and one ellipse. The ellipse intersects the circle in two points from the left and in one point from the right,

        Ellipse2<double> ellipses[2];
        ellipses[0].center = { 100.0, 100.0 };
        ellipses[0].extent = { 100.0, 100.0 };
        ellipses[1].center = { 75.0, 100.0 };
        ellipses[1].extent = { 125.0, 50.0 };

        FIQuery<double, Ellipse2<double>, Ellipse2<double>> query;
        auto area = query.AreaOfIntersection(ellipses[0], ellipses[1]);
        auto result = area.findResult;
        if (result.intersect) {
            std::cout << "!!!=== " << (result.intersect ? "Intersect" : "No intersection") << std::endl;
            std::cout << "!!!=== Number of points: " << result.numPoints << std::endl;
            std::cout << "!!!=== Area: " << area.area << std::endl;
            if (result.numPoints < 5) {
                for (int i = 0; i < result.numPoints; ++i) {
                    const auto &p = result.points[i];
                    std::cout << "!!!===   " << p[0] << ", " << p[1] << std::endl;
                }
            }
        }

But the intersector give 4 points:

!!!=== Intersect
!!!=== Number of points: 4
!!!=== Area: 16598.173372451663
!!!===   199.99999999999997, 100.00000238418579
!!!===   199.99999999999997, 99.999997615814209
!!!===   9.5238095238095184, 142.59177099999599
!!!===   9.5238095238095184, 57.408229000004013

In another case, when the ellipse is oriented vertically, it gives only 2 points instead of 3 points:

        ellipses[0].center = { 100.0, 100.0 };
        ellipses[0].extent = { 100.0, 100.0 };
        ellipses[1].center = { 100.0, 125.0 };
        ellipses[1].extent = { 50.0, 125.0 };

!!!=== Intersect
!!!=== Number of points: 2
!!!=== Area: 16598.173372451656
!!!===   57.408229000003651, 190.47619047619355
!!!===   142.5917709999963, 190.47619047619355

I can understand if the problem shows up on fractional numbers, say if we are trying to position the ellipse using trigonometric functions. But these are strong integer numbers and the correct result must obviously consist of 3 points.

Could you suggest any solution to this problem, please?

Hello.

gtengine-5.5 does not compile with GCC-11.0.0 (i don't know if newer release of GCC is already supported):

[ 78%] Building CXX object Graphics/CMakeFiles/gtgraphics.dir/VisualEffect.cpp.o
cd /builddir/build/BUILD/GeometricTools-GTE-version-5.5/Graphics && /usr/bin/g++ -DGTE_DISABLE_PCH -DGTE_USE_LINUX -DGTE_USE_MAT_VEC -DGTE_USE_OPENGL -DGTE_USE_ROW_MAJOR -DNDEBUG -Dgtgraphics_EXPORTS -I/builddir/build/BUILD/GeometricTools-GTE-version-5.5/GTE/Graphics/.. -O2 -flto=auto -ffat-lto-objects -fexceptions -g -grecord-gcc-switches -pipe -Wall -Werror=format-security -Wp,-D_FORTIFY_SOURCE=2 -Wp,-D_GLIBCXX_ASSERTIONS -specs=/usr/lib/rpm/redhat/redhat-hardened-cc1 -fstack-protector-strong -specs=/usr/lib/rpm/redhat/redhat-annobin-cc1  -m64 -mtune=generic -fasynchronous-unwind-tables -fstack-clash-protection -fcf-protection -DNDEBUG -fPIC -c -Wall -Werror -O3 -std=c++14 -o CMakeFiles/gtgraphics.dir/VisualEffect.cpp.o -c /builddir/build/BUILD/GeometricTools-GTE-version-5.5/GTE/Graphics/VisualEffect.cpp
In file included from /usr/include/c++/11/string:40,
                 from /builddir/build/BUILD/GeometricTools-GTE-version-5.5/GTE/Graphics/../Graphics/DataFormat.h:10,
                 from /builddir/build/BUILD/GeometricTools-GTE-version-5.5/GTE/Graphics/../Graphics/VertexFormat.h:10,
                 from /builddir/build/BUILD/GeometricTools-GTE-version-5.5/GTE/Graphics/VertexFormat.cpp:9:
In function 'std::char_traits<char>::copy(char*, char const*, unsigned long)',
    inlined from 'std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_S_copy(char*, char const*, unsigned long)' at /usr/include/c++/11/bits/basic_string.h:351:21,
    inlined from 'std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_replace(unsigned long, unsigned long, char const*, unsigned long)' at /usr/include/c++/11/bits/basic_string.tcc:481:20,
    inlined from 'std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::replace(unsigned long, unsigned long, char const*, unsigned long)' at /usr/include/c++/11/bits/basic_string.h:1946:19,
    inlined from 'std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::insert(unsigned long, char const*)' at /usr/include/c++/11/bits/basic_string.h:1714:22,
    inlined from 'std::operator+<char, std::char_traits<char>, std::allocator<char> >(char const*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&&)std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >' at /usr/include/c++/11/bits/basic_string.h:6154:23,
    inlined from 'gte::Logger::Logger(char const*, char const*, int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&)' at /builddir/build/BUILD/GeometricTools-GTE-version-5.5/GTE/Graphics/../Mathematics/Logger.h:86:44:
/usr/include/c++/11/bits/char_traits.h:402:56: error: 'memcpy' reading 6 bytes from a region of size 1 [-Werror=stringop-overread]
  402 |         return static_cast<char_type*>(__builtin_memcpy(__s1, __s2, __n));
      |                                        ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
cc1plus: all warnings being treated as errors

Build log: https://kojipkgs.fedoraproject.org//work/tasks/6452/57876452/build.log

When triangulating a polygon with TriangulateCDT, I encountered an "Unexpected condition" error in FillRegion() stemming from the line auto titer = tmap.find(tkey). The polygon is correctly triangulated with TriangulateEC. The "modern" TriangulateCDT, using the internal numeric type rather than the ComputeType template argument, is being used.

The polygon can be defined with this set of points and indices. This occurs even after passing the polygon through a routine to resolve error cases such as invalid winding order, self-overlapping, etc., so I'm fairly confident that it's valid.

Points:
0.20121991354297877, 0.83965378024074844
0.201219880381723, 0.83965410225399539
0.20122084921399078, 0.83965414658535842
0.20122089424348549, 0.83965385337004406
0.20122188873209326, 0.839653916550963
0.20122183881567665, 0.83965419196391899
0.20122238492919961, 0.83965421692212727
0.20122228404916884, 0.83965495781439481
0.20122378014540365, 0.83965504926964751
0.20122424335578715, 0.8396548071924802
0.20122460498800815, 0.83965511716295549
0.20122501060252629, 0.83965490510545138
0.20122570524356861, 0.83965550148445667
0.20122529962905045, 0.83965571336742795
0.20122596948641736, 0.83965628810435056
0.20122641210191566, 0.8396560570227577
0.20122716311709279, 0.8396567013983175
0.20122672085066035, 0.83965693282897624
0.20122722018935935, 0.83965736113277478
0.2012269110915488, 0.83965752275026351
0.20122744341697066, 0.8396580210417649
0.20122877091439972, 0.83965823275020324
0.20122880739178112, 0.83965798072465914
0.20122969524077158, 0.83965804058945248
0.20122963764490628, 0.83965842421282211
0.20123060193931799, 0.8396584830304179
0.20123065848798577, 0.83965810673743124
0.20123228478578276, 0.8396582163441082
0.20123222963337842, 0.83965858251418535
0.20123283683342519, 0.83965861968969835
0.20123289216036244, 0.83965825194882493
0.20123435788786831, 0.83965835108352649
0.20123430395719441, 0.83965870922508901
0.20123531555002885, 0.83965877083521157
0.20123536075405649, 0.83965846976591563
0.20123639852682973, 0.83965853992815154
0.20123635628986181, 0.83965883471426217
0.20123812762451967, 0.83965882092616118
0.20123900116181029, 0.83965845388341942
0.20123975392231669, 0.83965805385395487
0.20123907411657302, 0.8396574801642297
0.20123972652064742, 0.83965713354184024
0.20123929018833445, 0.8396567652773681
0.20124001956142884, 0.83965637763974132
0.20124036251862687, 0.8396566671898642
0.20124135526190537, 0.83965613957683138
0.2012409646572188, 0.83965580988413546
0.20124185617140072, 0.83965533620177668
0.20124224677608729, 0.83965566589447238
0.20124272028391338, 0.83965541421799406
0.20124302868359217, 0.83965567462111856
0.20124327372781917, 0.83965568491856113
0.2012433903158132, 0.83965482918362888
0.20124444641454359, 0.83965489376081126
0.20124442058367067, 0.83965508400169975
0.20124589922661296, 0.83965517964574266
0.20124595752060997, 0.83965476547911111
0.20124690628159136, 0.83965483389601792
0.20124686858247953, 0.83965524300119454
0.20124804126920393, 0.83965533847070462
0.20124807879378284, 0.83965492866739622
0.2012490612396188, 0.83965502012264903
0.20124901184680097, 0.8396554018261565
0.2012498529209675, 0.83965546832320093
0.20124980352814967, 0.8396558358895414
0.20125167295031149, 0.83965741104919134
0.20125225152695853, 0.83965744892283611
0.2012521607698374, 0.83965801423498088
0.20125273568129301, 0.83965805210862554
0.20125264003725002, 0.83965874308447641
0.20125204156384949, 0.83965870032390977
0.20125192218332866, 0.83965945762227223
0.20125247545270153, 0.83965949636858161
0.201252381030389, 0.83966016971660706
0.20125180489720293, 0.8396601006015687
0.20125170349357338, 0.83966073433062005
0.2012521939310932, 0.83966079803513771
0.20125208432441616, 0.83966144171256596
0.20125165776594697, 0.83966141116930393
0.20125142895328205, 0.83966237773264374
0.20125192532492131, 0.83966242625279697
0.20125177906633002, 0.83966310239334918
0.20125134221041824, 0.83966307603887758
0.20125121515044869, 0.83966367049802071
0.20124812312514587, 0.83966344081269106
0.20124880467621875, 0.83965911169801455
0.20124932426073708, 0.83965914869899461
0.20124944660831764, 0.83965837900879448
0.20124909963686236, 0.83965835422511914
0.20124916962456535, 0.83965791387854893
0.20124982237770558, 0.83965796030430695
0.20124987194505634, 0.83965764806490373
0.20124892719833226, 0.83965691118689367
0.2012485758635538, 0.83965689670066079
0.20124854008430415, 0.83965728643268267
0.20124791019497712, 0.83965726042727695
0.20124792799733546, 0.83965706791746042
0.20124681465180563, 0.83965702184076818
0.20124678951906441, 0.83965729707919112
0.20124625963710349, 0.83965727526257561
0.20124629855794582, 0.83965685341649532
0.20124567966419307, 0.83965682793468821
0.20124566517796025, 0.83965698449072224
0.2012440816407299, 0.83965691921540808
0.20124372262650278, 0.8396571099798954
0.20124420154484954, 0.83965751454721593
0.20124375229710006, 0.8396577531337247
0.20124349067224523, 0.8396575323495743
0.20124263266838491, 0.83965798822957494
0.20124287998153992, 0.83965819714548651
0.20124239600173835, 0.8396584542324852
0.20124205636066589, 0.83965816764942203
0.20124156330515222, 0.83965842979787586
0.20124172736610191, 0.83965856802795247
0.20124007506289904, 0.83965944592856634
0.20123996196556351, 0.83966027827608647
0.20123967992035641, 0.83966026099732693
0.20123954936972835, 0.83966121831042162
0.20124041889276167, 0.83966127136843094
0.2012402775210923, 0.83966231053746754
0.20124079256775454, 0.83966234212792701
0.20124070966461508, 0.83966354029645851
0.20124046758744782, 0.83966352546115985
0.20124041435490561, 0.839663917113044
0.20124084091337482, 0.8396639500997668
0.20124082311101646, 0.8396643941115286
0.20124041452943855, 0.83966436897878738
0.20124025762433881, 0.83966499904264735
0.20124069151319085, 0.83966507932779288
0.20124055450484457, 0.83966597764875894
0.20124032080525772, 0.83966594361483848
0.20124019042916261, 0.83966646337388984
0.20124046235146006, 0.83966648728490056
0.20124030247930058, 0.83966750271745927
0.20124129469898033, 0.8396682745020545
0.20124271853858411, 0.83966824727491818
0.2012427363409425, 0.83966786155715356
0.20124372157930523, 0.83966793189392241
0.20124368667272019, 0.83966823994453532
0.20124519498625978, 0.83966833541404551
0.20124526829008835, 0.83966785073611216
0.2012472459226638, 0.83966801566972649
0.20124716127419509, 0.83966846928079908
0.20124796691817778, 0.83966853019278997
0.20124795749339985, 0.83966869879159567
0.20124878111427386, 0.83966877226995718
0.20124883417228312, 0.83966828287963502
0.20125083170161201, 0.83966843419968118
0.20125075159099937, 0.83966892865145826
0.20125156962681975, 0.83966898903985021
0.20125151238002029, 0.83966933740756899
0.20125234891633079, 0.8396693991922245
0.20125242623441664, 0.83966890316965115
0.20125342805340729, 0.83966897001576146
0.20125331862126319, 0.83966964057126015
0.20125953199340027, 0.83967023066708013
0.20125956498012315, 0.83967016486816737
0.20125964177461023, 0.83967004880377205
0.20125971403124127, 0.83967000656680424
0.20125984004401326, 0.83966996049011189
0.20125995226868415, 0.83966992715432331
0.20126009608381454, 0.83966992069660507
0.20126023553562175, 0.83966994373495119
0.20126085617470377, 0.83967014374968341
0.20126095321501017, 0.83967003344487479
0.20126106927940543, 0.83966996799502769
0.20126115724399976, 0.83966993919709521
0.20126137174496481, 0.83966992034753918
0.20126145744063106, 0.8396699304704488
0.20126160160482731, 0.8396699734055485
0.20126211595335786, 0.83966933374237751
0.20126223254135189, 0.83966896285991155
0.20126198906792125, 0.83966897507721627
0.20126188382456736, 0.83966895762392368
0.20126169463087643, 0.8396688879852866
0.20126161644012594, 0.83966883789433699
0.20126152638113656, 0.83966874766081478
0.20126148728576129, 0.83966867994203986
0.2012614637238164, 0.8396685361269095
0.20126152620660362, 0.83966837922180959
0.20126163528968186, 0.839668275723785
0.20126171662202502, 0.83966822790176343
0.20126180929900828, 0.83966819037718454
0.20126199220951388, 0.83966815686686302
0.20126219676210222, 0.83966818898092122
0.20126246222668145, 0.83966685502577387
0.2012620621972169, 0.83966560903522092
0.20126298338199611, 0.83966455433275389
0.20126319439230267, 0.83966314079059268
0.20126280640560992, 0.83966311321439058
0.20126266765193443, 0.83966275140763658
0.20126291967747839, 0.83966243864463463
0.20126323313861208, 0.83966246098484909
0.20126344240358937, 0.83966176390034586
0.20126399340403425, 0.83966178885855414
0.20126510378250434, 0.83966127084483211
0.20126518511484748, 0.83966082927653141
0.20126625814327162, 0.83966084236650074
0.20126629025732987, 0.83966064095550508
0.20126684143230764, 0.83966056119395827
0.20126735525723943, 0.83966075736896628
0.2012679603628911, 0.83966080728538273
0.20126961249156103, 0.83966141151836982
0.20126998511935631, 0.83966141797608806
0.20127003014885103, 0.839661271193898
0.20127011217932586, 0.83966117293186104
0.20127018653035203, 0.83966111673225918
0.20127039928598783, 0.83966102684780275
0.20127064712274159, 0.8396609990970676
0.20127086633609564, 0.83966102929126363
0.20127105675151705, 0.839661108005613
0.20127113372053707, 0.83966116263441848
0.20127124001108851, 0.83966129440677706
0.20127126601649437, 0.83966136753607268
0.20127126060597367, 0.83966151484186158
0.20127327209793661, 0.83966165935512371
0.20127507746651488, 0.83966133821454125
0.2012768721885847, 0.83966198642982548
0.20127872729904664, 0.8396621396697338
0.20127880863138978, 0.83966198049570606
0.20127887285950627, 0.8396619188855835
0.20127901981622928, 0.83966183196818667
0.20127919941060929, 0.83966177925924323
0.20127930988995096, 0.8396617661692739
0.20127947779062499, 0.83966177105619577
0.20127958617557154, 0.83966179042935041
0.20127978008165145, 0.83966186530397535
0.20127985931959946, 0.83966191853651762
0.20127994990218767, 0.83966201330789603
0.20128000784711883, 0.83966215799569088
0.20128000802165175, 0.83966223321938172
0.20127995129845108, 0.83966237668544619
0.20128044749555743, 0.83966242590373108
0.20128245043540699, 0.83966209272037695
0.20128295082130354, 0.83966220424691607
0.20128349972735329, 0.83966211296619619
0.20128393221994195, 0.83966224805468037
0.20128389295003377, 0.83966246046125026
0.20128500786635994, 0.83966255244010191
0.20128492409055587, 0.83966300849463549
0.20128572938547271, 0.839663730537347
0.20128642559731133, 0.83966378795867946
0.20128628230577975, 0.83966456602645989
0.20128650675512155, 0.83966458470148286
0.20128664184360565, 0.83966495680567943
0.20128646888147678, 0.83966524181794633
0.20128580914701955, 0.83966559245459305
0.20128590339479913, 0.8396662078576872
0.20128570547446195, 0.83966728385317113
0.20128532307282285, 0.83966771285510122
0.2012850595281058, 0.83966914472321963
0.2012845565242154, 0.8396698356990705
0.20128370183648067, 0.83967033783029632
0.20128252827709162, 0.8396702409645227
0.20128245497326305, 0.8396706390741252
0.20127917811759241, 0.83967036854809107
0.2012786293860756, 0.83967013048518113
0.20127889293079265, 0.83966977443801361
0.20127871141655046, 0.83966970741737046
0.20127859901734663, 0.8396696040938787
0.20127856899768348, 0.83966954667254623
0.20127855747851042, 0.8396694930909383
0.20127857632806634, 0.83966938592772222
0.20127865574054729, 0.83966928452409262
0.20127873044063929, 0.83966923303687979
0.20127940326506594, 0.83966852582946694
0.20127998637956904, 0.83966878588352534
0.20128084769955487, 0.83966885691842597
0.20128103113365928, 0.83966860192582227
0.2012820917702457, 0.83966840592534731
0.20128244607208387, 0.83966853001825703
0.2012827857131563, 0.8396680996200635
0.20128282288866936, 0.83966775736099719
0.20128266458730623, 0.83966775631379964
0.20128256178741327, 0.8396677402567706
0.20128246457257393, 0.83966771268056828
0.20128233576727514, 0.83966765107044572
0.20128220923090437, 0.83966753849670894
0.20128216961193035, 0.83966747269779618
0.20128214430465619, 0.83966733289692308
0.2012821589654219, 0.83966726290922011
0.20128224134496259, 0.8396671330567238
0.20128240627857691, 0.83966701943578947
0.20128254747571339, 0.83966697126470213
0.20128272881542267, 0.83966694874995473
0.2012828342333095, 0.83966695258967905
0.20128298153909838, 0.83966697929321654
0.20128342624899179, 0.83966461978260087
0.20128424585560853, 0.83966419531852676
0.20128383168897704, 0.83966384503094593
0.20128311907104343, 0.83966418083229388
0.201279382146582, 0.83966387243261509
0.20127878664024121, 0.83966396563319723
0.20127699052190798, 0.83966382705405462
0.20127632782039101, 0.83966353471140498
0.20127317278870216, 0.83966327413374753
0.20127221233401479, 0.83966337798083801
0.20127059895165425, 0.8396632448122161
0.20127015336909621, 0.83966299505560027
0.20126654804246039, 0.83966269154284323
0.20126595026719157, 0.83966216550060668
0.20126541584737459, 0.83966245854138821
0.20126607348743675, 0.83966299121587584
0.20126579580555276, 0.83966450022754702
0.20126546349486318, 0.83966476673932389
0.20126528442408192, 0.83966573818958545
0.2012653741340055, 0.83966590033067301
0.2012651936669608, 0.83966608219398109
0.20126502978054406, 0.83966697301003135
0.20126527395210642, 0.83966743901294161
0.20126509924464828, 0.83966838829752177
0.2012647217299311, 0.83966891905214724
0.20126448768127839, 0.83967023468133739
0.2012649025460416, 0.83967026906432363
0.20126513903815524, 0.83967098569651455
0.20126501477071251, 0.83967165956813883
0.20126432484205919, 0.83967160267040519
0.20126297413175107, 0.83967149131839891
0.20126243238155125, 0.83967144663797011
0.20126239258804432, 0.83967169587098733
0.20126048738663282, 0.83967151592754141
0.20125987215807148, 0.83967225594714423
0.20125940929675384, 0.83967222872000791
0.20125949115269579, 0.83967178296291689
0.20125299870241128, 0.83967120700426379
0.20125305682187539, 0.83967092059573356
0.20124788279330785, 0.8396705322599749
0.20124780914041343, 0.83967089476486056
0.2012466989364762, 0.83967082163556495
0.20124680243450085, 0.83967023729933132
0.20124491346465143, 0.83967008929541076
0.20124487803446761, 0.83967018773198066
0.20124227155976268, 0.83967000028361893
0.20124229861236609, 0.83966972260173489
0.20123998238591576, 0.8396695398657622
0.20123969283579285, 0.83966931332202532
0.20123729580059818, 0.83967070225504403
0.20123558398166783, 0.83967055180766259
0.20123547559672128, 0.83967114452147651
0.20123354997495754, 0.83967100768766323
0.20123360338203264, 0.83967067066458467
0.20123182698591996, 0.83967054447727973
0.20123170062408213, 0.83967134191821502
0.20123057383951704, 0.83967126180760221
0.20123064661974685, 0.83967080138974559
0.20122989961882701, 0.83967074501561079
0.20122995599296181, 0.83967040973786145
0.20122823335299012, 0.83967027971083208
0.20122817697885528, 0.83967061498858153
0.20122624821549892, 0.83967046942812185
0.20122631366534585, 0.83966991249355749
0.20122462383756409, 0.83966976763122958
0.20122267151226278, 0.8396681146298951
0.20122228527089933, 0.83966830591798103
0.20122062179758923, 0.83966819369331014
0.20122081360927405, 0.83966692047562086
0.2012212808339148, 0.83966695206608033
0.20122257918434536, 0.83966636615905033
0.20122267290852619, 0.8396660200602597
0.2012224859837633, 0.83966600731935626
0.20122259227431474, 0.83966530028647623
0.2012230685746676, 0.83966533240053443
0.20122314973247785, 0.83966473602152902
0.2012224512517112, 0.83966468889763923
0.20122261478906209, 0.83966360277924568
0.20122329791093133, 0.83966364868140508
0.20122338796992073, 0.83966298789975025
0.20122274394342676, 0.83966294444105183
0.20122283731854171, 0.83966232397650276
0.20122372761099316, 0.83966238227049972
0.2012238997004574, 0.83966111795398968
0.20122319231851157, 0.83966107013196822
0.20122329162774602, 0.83966041022297799
0.20122398975944683, 0.83966045734686778
0.20122403688333662, 0.83966011107354421
0.2012255673625577, 0.83966020462319202
0.20122572671111841, 0.83965903403086273
0.20122424457751761, 0.83965776220943689
0.20122393111638395, 0.83965792609585366
0.20122357978160552, 0.83965762467749183
0.20122389743152938, 0.83965742117210096
0.20122322146551008, 0.83965684102465776
0.20122287641391698, 0.83965702131716935
0.20122254270696399, 0.83965673490863912
0.20122312128361103, 0.83965636402617316
0.20122282475217113, 0.83965615650652503
0.20122124784719192, 0.8396560599898174
0.20122127594699288, 0.8396558529937681
0.20122067537919727, 0.83965581634185382
0.20122062284478678, 0.8396562027577501
0.20121995263835404, 0.83965616191704573
0.20121999696971704, 0.83965583501687679
0.20121900666989948, 0.83965577462848473
0.20121896425839864, 0.83965608582069029
0.20121837032285417, 0.83965604934330895
0.20121842407899512, 0.83965565664422726
0.20121786731896374, 0.8396556226103068
0.20121784305888715, 0.8396558008084235
0.20121623875223871, 0.83965566205474795
0.20121591377193199, 0.83965584897951073
0.20121634259932919, 0.83965619176217599
0.20121582737813401, 0.83965648061416709
0.20121562823606637, 0.83965632126560641
0.20121480304439601, 0.83965678395239118
0.20121499852127223, 0.83965694033389204
0.20121448521993923, 0.83965722796415276
0.20121412969637059, 0.8396569434754847
0.20121370034537461, 0.83965718433092151
0.20121389460052036, 0.83965733983975788
0.20121266117633796, 0.83965795524285214
0.20121261701950791, 0.83965827865236253
0.20121336402042775, 0.83965832420545605
0.20121330450470026, 0.83965876245763127
0.201212852464424, 0.83965873488142895
0.20121275682038098, 0.83965943580565661
0.20121315056666023, 0.83965945971666733
0.20121309105093274, 0.83965989796884255
0.20121253568716477, 0.8396598639349222
0.20121248472355061, 0.83966023673725032
0.20121276921221867, 0.8396602541905428
0.20121265018076367, 0.8396608388758422
0.20121029206641133, 0.8396606606777256
0.2012103840452629, 0.83966013760254876
0.20120979377490988, 0.83966010164876625
0.20120988819722241, 0.8396594082294544
0.20121036903543132, 0.83965944400870407
0.20121048597249122, 0.8396586825215514
0.20121003672474175, 0.83965862702008121
0.20121013935010176, 0.83965797252161178
0.2012105898195817, 0.83965800707913096
0.2012106784823077, 0.83965742954968148
0.20121125164843406, 0.83965748260769058
0.20121130976789817, 0.83965709846072234
0.20121096681070014, 0.83965679756595935
0.20121180334701061, 0.83965634325675498
0.20121239920241724, 0.83965600728087397
0.20121206025947652, 0.83965569539053664
0.20121285438428615, 0.83965527720964783
0.20121317325594049, 0.83965557112309397
0.20121405307641643, 0.83965507544958629
0.20121373472836088, 0.83965479602237314
0.20121454857539109, 0.83965435742113215
0.20121485121548335, 0.83965462550370518
0.20121551670952714, 0.8396542504324489
0.20121586629897634, 0.83965452881246461
0.20121629861703208, 0.83965428778249496
0.20121635935449003, 0.8396539186453581
0.20121821411588614, 0.83965404273826794
0.20121827066455389, 0.83965366836514332
0.20122964445169036, 0.83966047165856761
0.2012262448993733, 0.83966026413891959
0.20122610492396731, 0.83966129178878313
0.20122644055078245, 0.83966131238366826
0.20122626217813291, 0.83966262207873898
0.20122605448395195, 0.83966260951236849
0.2012260085817926, 0.83966294810624331
0.20122651228381475, 0.83966297899857101
0.20122644962649458, 0.83966343924189479
0.20122600701099627, 0.83966341236382436
0.20122590839989352, 0.83966413667546391
0.20122632064666285, 0.83966416180820513
0.20122620580399808, 0.83966500567489843
0.20122586162506959, 0.83966498455641447
0.2012257141447478, 0.83966606875494587
0.20122537537633997, 0.8396660479855278
0.20122533244124038, 0.83966636441372122
0.20122567330404328, 0.83966638500860635
0.20122561623177676, 0.83966680545842309
0.20122481442751838, 0.83966675641467114
0.20122476730362859, 0.83966710233892883
0.20122433009865098, 0.83966707546085839
0.20122428367289283, 0.83966728961275761
0.20122611173075139, 0.83966864433732302
0.20123626623087243, 0.83966929743952912
0.20123848506795047, 0.83966834553695513
0.20123897288747641, 0.83966872340073817
0.2012392894902027, 0.83966855253300443
0.2012379441904153, 0.83966730828778069
0.20123776040724506, 0.83966700686941886
0.2012378405178577, 0.83966641939159259
0.20123728881928118, 0.83966638570673802
0.20123768815061402, 0.83966345337906179
0.20123792865698495, 0.8396634680398275
0.20123824595784295, 0.83966113872340775
0.20123596760503742, 0.83966099944613348
0.2012359868036592, 0.83966089420277956
0.20123475460120727, 0.8396608188045559
0.20123480364495924, 0.83966045752140073
0.20123378053295174, 0.83966039503861345
0.20123376220699457, 0.83966053117429507
0.20123200064618055, 0.83966042366201321
0.20123202508079005, 0.83966024284590268
0.20123140409264223, 0.83966020497225791
0.20123135120916588, 0.83966059243535196
0.20123069234737326, 0.8396605521182462
0.20123074715071176, 0.83966014929625477
0.20122969698610085, 0.83966008506813827

Boundary:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400, 401, 402, 403, 404, 405, 406, 407, 408, 409, 410, 411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422, 423, 424, 425, 426, 427, 428, 429, 430, 431, 432, 433, 434, 435, 436, 437, 438, 439, 440, 441, 442, 443, 444, 445, 446, 447, 448

Hole:
449, 450, 451, 452, 453, 454, 455, 456, 457, 458, 459, 460, 461, 462, 463, 464, 465, 466, 467, 468, 469, 470, 471, 472, 473, 474, 475, 476, 477, 478, 479, 480, 481, 482, 483, 484, 485, 486, 487, 488, 489, 490, 491, 492, 493, 494, 495, 496

There is a bug causing undefined behavior (uninitialized Result::intersect member) due to an implicit conversion from bool to Real:

            // At least one pair of box axes was parallel, so the separation is
            // effectively in 2D.  The edge-edge axes do not need to be tested.
            if (existsParallelPair)
            {
                return true;
            }

@davideberly, do you test for floating point exceptions in GTE/GTL? If yes, what is your strategy? Do you have any recommendations?

In our application, we enable floating-point exceptions in our MSVC builds. Internal and third-party numerical/geometric codes frequently trigger such exceptions, e.g., due to bad triangle mesh quality (normals of zero area triangles, etc.).

Note: I have not observed any FP exceptions coming from your library (I have only had good experiences, thanks for creating it!).

Solving for the cubic polynomial 16t^3 - 24t^2 + 24t - 8 = 0 should give 0.5 as a real root, but looking at

Line 14 of PVWUpdater.cpp precipitates a warning during compilation of the static release build under g++ 12.2.1 on Fedora 37. The complaint appears to be related to the lambda appearing in the call to Set().

A trace of the error message appears below:

In copy constructor ‘std::function<_Res(_ArgTypes ...)>::function(const std::function<_Res(_ArgTypes ...)>&) [with _Res = void; _ArgTypes = {const std::shared_ptrgte::Buffer&}]’,
inlined from ‘std::function<_Res(_ArgTypes ...)>& std::function<_Res(_ArgTypes ...)>::operator=(const std::function<_Res(_ArgTypes ...)>&) [with _Res = void; _ArgTypes = {const std::shared_ptrgte::Buffer&}]’ at /usr/include/c++/12/bits/std_function.h:471:2,
inlined from ‘void gte::PVWUpdater::Set(const std::shared_ptrgte::Camera&, const gte::BufferUpdater&)’ at PVWWUpdater.cpp:25:16,
inlined from ‘gte::PVWUpdater::PVWUpdater()’ at PVWUpdater.cpp:14:9:
/usr/include/c++/12/bits/std_function.h:391:17: error: ‘’ may be used uninitialized [-Werror=maybe-uninitialized]
391 | __x._M_manager(_M_functor, __x._M_functor, __clone_functor);
| ~~~~^~~~~~~~~~
/usr/include/c++/12/bits/std_function.h: In constructor ‘gte::PVWUpdater::PVWUpdater()’:
/usr/include/c++/12/bits/std_function.h:267:7: note: by argument 2 of type ‘const std::_Any_data&’ to ‘static bool std::_Function_handler<_Res(_ArgTypes ...), _Functor>::_M_manager(std::_Any_data&, const std::_Any_data&, std::_Manager_operation) [with _Res = void; _Functor = gte::PVWUpdater::PVWUpdater()::<lambda(const std::shared_ptrgte::Buffer&)>; _ArgTypes = {const std::shared_ptrgte::Buffer&}]’ declared here
267 | _M_manager(_Any_data& __dest, const _Any_data& __source,
| ^~~~~~~~~~
PVWUpdater.cpp:14:9: note: ‘’ declared here
14 | Set(nullptr, [](std::shared_ptr const&) {});
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cc1plus: all warnings being treated as errors

the result point should be [2.0,2.0] but got [-2.0,-2.0]

  Line2<float_t> line2_3({0.0, 0.0}, {0.5, 0.5});

    Line2<float_t> line2_4({2.0, 0.0}, {2.0, 1.0});

   IntrPointLine2AndLine2<float_t> intrLine2AndLine2;

    auto result6 = intrLine2AndLine2(line2_3, line2_4);
    
   Vector2<float_t> respect = {2.0f, 2.0f};
    assert(result6.point == respect);

Hello... again!

I need a 2D geometric primitive that you don't have in your library. It is similar to a polygon2 composed of linear "segment2" and curved "arc2" (convex / concave). I somehow found a way to create this "2D potatoe" object, and use your functions independently to calculate intersections (loop through all the segment2/arc2, and test if anyone has an intersection with the other object, ...)

that's ok.

now i would like to create a Prism (extrusion through Z axis) of this Potatoe2D object, so it will be 3D. (with up and bottom equals, perpendicular to Z axis, all other sides parallel to Z axis).
And i need to calculate the intersection of this "PrismPotatoe" with a cylinder. The axis of my cylinders will always be in the XY plane, perpendicular to the Z axis.

Do you have any advice? maybe i could use "IntrTriangle3Cylinder3.h" to test each vertical rectangle (split in 2 triangles) with my cylinder...

but i still have no solution to calculate the instersection of a cylinder3 and an "extrudedArc3" (a part of a cylinder3). Any idea for this last question?

Thank you again, and don't worry if you don't have time to write this!!

Johan

Dear Eberly,
The DCPQuery for Oriented Bounding Boxes (we are using version 3) is running into the floating-point rounding error for lots of parallel configurations as described in the documentation and the source code comments. We tested those failure cases in version 5 and all the new results seem to be correct now.
However, since the floating-point rounding error still exists in the current doc, we want to check if this problem has been completely resolved. If not then how robust can we expect from the distance query with fixed-precision floating-point numbers? (We are running thousands of queries to check and compare the returned distance against a threshold in a simulation, and most of the time the bounding boxes are moving in parallel. So we'd need the returned distance to be a stream of continuous values)
Also, can you point us to the part on the update history that talks about the improvement made for the LCP solver since version 3 regarding this specific floating-point rounding error? I tried searching for changes from the LCPSolver.h but could not see any places that discuss that issue.
Thanks in advance,
Tuan

Hello David,

I noticed that the line or ray intersection routines with spheres don't work if the line/ray has a direction vector with magnitude other than one. This is in contrast with other geometries like boxes or cylinders where such direction vectors are allowed.
Do you think this could be improved and make the treatment of spheres more in line with other geometries?

Regards,
Manuel

The ellipse-ellipse intersection finding code (IntrEllipse2Ellipse2.h) produced inaccurate intersection points for 2 ellipses centered at the origin and each having extents a = 2 and b = 1. For an angle t, the first ellipse has major axis (cos(t),sin(t)) and minor axis (-sin(t),cos(t)). The second ellipse has major axis (-sin(t),cos(t)) and minor axis (-cos(t),-sin(t)). For t = 1e-8, the double-only code is inaccurate due to computation of the w-value on line 701; the numerator and denominator are nearly zero and approximately the same magnitude, leading to inaccuracy of the (x,y) intersection point. When using Rational type BSRational, the intersection points are accurate.

When t = GTE_C_QUARTER_PI+1e-08, both the double-only and the Rational output is inaccurate. The Rational inaccuracy is due to rounding errors in RootsPolynomial::SolveBiquadratic. This function correctly classifies the real-valued roots, but to compute the roots there are std::sqrt calls where the inputs are Rational, converted to 'double', std::sqrt is computed, and the result is converted back to Rational. The quadratic, cubic and quartic root finders need to be improved (perhaps by an iterative algorithm for root polishing).

I can't find GTL/Mathematics/Integration/IntgRomberg.h in master branch. But this file is used by ParametricCurve.h.

ParametricCurve(Real tmin, Real tmax)
:
mTime(2),
mSegmentLength(1),
mAccumulatedLength(1),
mRombergOrder(DEFAULT_ROMBERG_ORDER),
mMaxBisections(DEFAULT_MAX_BISECTIONS),
mConstructed(false)
{
mTime[0] = tmin;
mTime[1] = tmax;
mSegmentLength[0] = (Real)0;
mAccumulatedLength[0] = (Real)0;
}

ParametricCurve(int numSegments, Real const* times)
:
mTime(numSegments + 1),
mSegmentLength(numSegments),
mAccumulatedLength(numSegments),
mRombergOrder(DEFAULT_ROMBERG_ORDER),
mMaxBisections(DEFAULT_MAX_BISECTIONS),
mConstructed(false)
{
std::copy(times, times + numSegments + 1, mTime.begin());
mSegmentLength[0] = (Real)0;
mAccumulatedLength[0] = (Real)0; // maybe initializing the whole items to zeros is better?
}
Just the first elements are initialized to zero.

Real GetLength(Real t0, Real t1) const
{
std::function<Real(Real)> speed = [this](Real t)
{
return GetSpeed(t);
};

        if (mSegmentLength[0] == (Real)0) **// checks for the first item**
        {

Real GetTotalLength() const
{
if (mAccumulatedLength.back() == (Real)0) // checks for the last item, may be some undefined value
{

To be consistent, checking for the last item looks better. ^^
Thanks for the great code as always!!!

So, this mainly goes for the mathematics library, but it might apply to others. And I have no idea how feasible these suggestions are, given how large the library is. But here they are, anyway, for pondering purposes:

1. Replace all C-style casts with C++ casts.
2. If possible, try to employ constraints and concepts using the Concepts library. Both of these are C++20 only, so this would jump the standard of C++ to C++20, but it would also provide significant static checking for all the templates. Right now, the concept used is the auto concept, which is akin to the old typename T template style: allow any type, even if it's obviously not a type that's compatible with the class, and let the compiler yell at you for operations that you couldn't possibly do on, say, a struct that doesn't define arithmetic operators.

As an example of the concepts, the Vector class template could be changed from:

template <int32_t N, typename Real>

to:

#include <concepts>

// ...

template <unsigned_integral N, floating_point Real>

Or if you wanted to allow vectors to work with both integral types and FP types:

template <typename N, typename E>
requires unsigned_integral<N> && (floating_point<E> || integral<E>)

This would give much cleaner error messages if someone decided to try to violate the constraints, and it would also make the purpose of the template arguments a bit clearer.

There is some inconsistency in the naming of some of the intersection objects. For example, the Sphere3 class has a FIQuery object with fields like numIntersections and parameter[] . In contrast, the FIQuery for OrientedBox3 has numPoints and lineParameter[].

If the naming was consistent, it would be possible to write a generic intersection function:

template <typename GeometricObject>
bool intersect(const GeometricObject& object, const gte::Ray3<float>& ray)
{
    gte::FIQuery<float, gte::Ray3<float>, GeometricObject> query;
    auto intersection = query(ray, object);

    if(intersection.intersect)
    {
        float nearestT = intersection.parameter[0];
        unsigned numIntersections = intersection.numIntersections;
        ...
    }
}

I guess making this change would break already existing code so I'm not sure how viable it is but I thought I would mention it because, as I explained, it would allow for more consistent coding going forward.

Whether to support technology with a mixture of arcs and straight lines

When using the new TriangulateCDT that doesn't take a compute type template parameter, some polygons result in an error about creating a non-manifold mesh. These errors disappear when using an explicit compute type of gte::BSNumbergte::UIntegerAP32.

Here are two polygons that exhibit this problem, using double precision for the input type:

Points:
0.20209289058291205, 0.83965099469526228
0.20209236682654186, 0.83965205584045832
0.20209230684758409, 0.83965217735952036
0.20209193307206785, 0.83965293463927093
0.2020917065364263, 0.83965339360687763
0.20209164655746853, 0.83965351512593989
0.20209105940397842, 0.83965470471549097
0.20209099942502062, 0.83965482623455312
0.20209076954373811, 0.83965529198052291
0.20209041388543147, 0.83965601255429534
0.20209035390647367, 0.83965613407335749
0.20209004744156056, 0.83965675497992553
0.20208754708287416, 0.8396561976962954
0.20209026770211216, 0.83965044142588929

Boundary:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13

Points:
0.20208523411510296, 0.83966332777155461
0.20208662048756035, 0.83966364431603679
0.20208523411510293, 0.83966332777155461
0.20208513067452474, 0.83966330415341062
0.20208806073825292, 0.83966250884209193
0.20208753572284524, 0.83966352393632171
0.20208806073825289, 0.83966250884209193
0.2020881343533035, 0.83966236651062509
0.20208468229943993, 0.83966092265164638
0.20208614019546703, 0.83966121478929878
0.20208530381118656, 0.83966294583731527
0.20208351970988686, 0.83966254606591495
0.20208322023712552, 0.8396624789617404
0.20208286318159582, 0.83966217602346105
0.2020825274017701, 0.83966189113622602
0.20208235941987907, 0.83966174861457099
0.2020820471840965, 0.83966148370291771
0.20208157402887555, 0.83966108226163882
0.20208083238854183, 0.83966045302829051
0.20207971799980912, 0.8396595075422888
0.20207945912005715, 0.83965928789973998
0.20207894070151083, 0.83965884805548807
0.20207828889711815, 0.83965829504206368
0.20207721612996576, 0.83965738486925257
0.20207928277433304, 0.83965628513729085
0.20208849493616993, 0.83966166933949116
0.20208834809931403, 0.83966195324210235
0.2020884949361699, 0.83966166933949116
0.20208878569899102, 0.8396611071623481

Boundary:
8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24

A failed unit test in GTL development occurred for interval arithmetic when running in a release build. To avoid this using the Microsoft Visual Studio C++ compiler, you need the floating-point model to be "/fp:strict". The default model is "/fp:precise". The Intel C++ 20.x compiler requires "-fp-model strict". The default is "-fp-model precise".

GCC has an option "-frounding-math", which appears to be ignored by the compiler. This breaks interval arithmetic. This means avoiding the GTL FPInterval class and other code that uses std::fesetround(...), instead using GTL rational arithmetic.

In all cases, the C++ suggested #pragma STDC FENV_ACCESS produces a warning by the compilers that this is an unknown pragma, something which should be allowed to control rounding mode at a code-block level.

Details are found in Section 3.4 of https://www.geometrictools.com/Books/RobustAndErrorFreeGeometricComputing/RAEFGC_BookCorrections.pdf

I will keep this issue open until GCC on commonly used Linux platforms finally supports this. Also until then, the GTL code will contain conditional compilation to fall back to rational arithmetic only when the compiler does not support the "strict" option.

Thanks for your great book and tool box!

As a reader and learner, when i code by following your book examples,
sometimes i really need some way to see the intermediate results like printing some Vec/Matrix.
But they does not support operator<< or provide any print-like functions.
I know it is quite usual to DIY but if you can add some facilities it would be better.

Running this code:

  auto s0 = gte::Segment2<double>({2.2352092822407803, -1.7068004885705972}, {1.4357507764403734, -4.4188128129047435});
  auto s1 = gte::Segment2<double>({1.8515323877379666, -1.5936985848524166}, {1.2171034035398707, -3.7458793566829809});

  gte::DCPQuery<double, gte::Segment2<double>, gte::Segment2<double>> query;
  auto res = query.ComputeRobust(s0, s1);

  std::cout << res.parameter[0] << " " << res.parameter[1] << std::endl;

  std::cout << res.closest[0][0] << " ";
  std::cout << res.closest[0][1] << std::endl;
  std::cout << std::endl;
  std::cout << res.closest[1][0] << " ";
  std::cout << res.closest[1][1] << std::endl;
  std::cout << std::endl;

Gives the following output:

0 5.5132038956111662e-18
2.2352092822407803 -1.7068004885705972
1.8515323877379666 -1.5936985848524166

Returned values are not one of the closest pairs.

Hi,

Is there an implementation in GeometricTools of triangle-triangle intersection in 3D which also returns, if any, the closed line loops of the resulting polygons that result from the intersection? I found triangle-triangle in section 11.5.4 of your book Geometric Tools... which is great, but I wondered if the code was provided here?

I really need the resulting N closed-polygon-line-loops, if any, that define the N-polygons produced as a result of the intersection of the two triangles. Could you point me in the right direction for this?

Thanks,
Andy

How are all algorithms tested for correctness?
I do not see any tests.

How to generate B-spline curves from discrete points?
What's the difference from the B-spline basis function

Hello,
First of all, thanks for the amazing work on this library!

I recently faced the problem of rotating and aligning sets of points so that they occupy the least space along a single dimension, in the image below the "rectangle by width" case.

(image courtesy of ArcGIS)

Would it be possible for you to support such cases? For what I saw you already have an implementation of the rotating calipers algorithm, and the only relevant change would be to update the minimization criterium in MinimumAreaBox2.h from

template <typename InputType, typename ComputeType>
class MinimumAreaBox2 {
....
    if (box.area < minBox.area)
    {
         minBox = box;
    }
...
};

to something like

template <typename InputType, typename ComputeType, typename BoxComparatorType>
class MinimumBox2 {
....
    BoxComparatorType comparator{};
    if (comparator(box.area,minBox.area))
    {
         minBox = box;
    }
...
};

and then provide for example an AreaLessComparator and a SideLessComparator.

I suggest to rename GTE/Mathematics/Math.h to GTE/Mathematics/GTEMath.h because some system confuse your Math.h wit <math.h> and leads to errors (at least on MacOS).
BTW Your library (very pedagogic and quite simple to use).
If you have time I would suggest to allow a separate use of only Mathematics which is by far the most portable part of your library.

I believe the code below should read E1.sqrExtent = ellipse1.extent * ellipse1.extent;.
Fixing this gave me expected values when calculating intersection areas of ellipses, otherwise I sometimes end up with an intersecting area greater than any of the two ellipses referenced.

Also this is the first issue I ever opened, sorry if I missed anything.

I vaguely recall writing this code a long time ago. When I wrote it, I was either on drugs or else out of them. The Update function has a loop to find terminator edges. The idea is very simple but the performance is horrible. The loop is over all faces of the current hull and there is one loop per point insertion. For a dataset with a large number of points, many points becoming hull vertices, as the number of faces increases the computing time becomes enormous. A dataset with 120K points required more than 1 hour to compute the convex hull. Currently, I am implementing an algorithm that is much faster.

Hello, recently I use the newest released package GTE-version-6.5 to judge intersection of box and cylinder, but found something seems like a bug.

Problem

I downloaded the package and changed the cylinder property to run the box and cylinder intersection sample, the test result is wrong.

The test case

After change the function void IntersectBoxCylinderWindow3::CreateScene() in
GTE/Samples/Intersection/IntersectBoxCylinder/IntersectBoxCylinderWindow3.cpp to

void IntersectBoxCylinderWindow3::CreateScene()
{
    VertexFormat vformat;
    vformat.Bind(VASemantic::POSITION, DF_R32G32B32_FLOAT, 0);
    MeshFactory mf;
    mf.SetVertexFormat(vformat);

    // mCylinder.axis.origin = { 3.0f, 2.0f, 3.0f };
    // mCylinder.axis.direction = { 0.0f, 0.0f, 1.0f };
    // mCylinder.radius = 1.0f;
    // mCylinder.height = 8.0f;
    // I changed the cylinder property only
    mCylinder.axis.origin = { 6.0f, 0.0f, 0.0f };
    mCylinder.axis.direction = { -0.017459368f, -0.9998476f, 0.0f };
    mCylinder.radius = 0.5f;
    mCylinder.height = 2.0f;

    mCylinderMesh = mf.CreateCylinderClosed(16, 16, mCylinder.radius, mCylinder.height);
    mCylinderMesh->localTransform.SetTranslation(mCylinder.axis.origin);
    auto effect = std::make_shared<ConstantColorEffect>(mProgramFactory,
            Vector4<float>{ 0.0f, 0.5f, 0.0f, 0.5f });
    mCylinderMesh->SetEffect(effect);
    mPVWMatrices.Subscribe(mCylinderMesh->worldTransform, effect->GetPVWMatrixConstant());

    mRedEffect = std::make_shared<ConstantColorEffect>(mProgramFactory,
        Vector4<float>{ 0.5f, 0.0f, 0.0f, 0.5f });

    mBlueEffect = std::make_shared<ConstantColorEffect>(mProgramFactory,
        Vector4<float>{ 0.0f, 0.0f, 0.5f, 0.5f });

    mBox.center = { 0.0f, 0.0f, 0.0f };
    mBox.axis[0] = { 1.0f, 0.0f, 0.0f };
    mBox.axis[1] = { 0.0f, 1.0f, 0.0f };
    mBox.axis[2] = { 0.0f, 0.0f, 1.0f };
    mBox.extent = { 1.0f, 2.0f, 3.0f };

    mBoxMesh = mf.CreateBox(mBox.extent[0], mBox.extent[1], mBox.extent[2]);
    mBoxMesh->SetEffect(mBlueEffect);
    mPVWMatrices.Subscribe(mBoxMesh->worldTransform, mBlueEffect->GetPVWMatrixConstant());

    mTrackBall.Attach(mCylinderMesh);
    mTrackBall.Attach(mBoxMesh);
    mTrackBall.Update();
}

Result expected

The intersection test function gives intersected, but obviously they are not intersected.

Attachment

Here is the snapshot.

Hello

This is more a "feature request" ... I need a function to calculate the distance from a 2D point to a Arc2 ...
I can easily get the distance from the point to the full circle... but for an Arc2 it's more difficult :-)

can you help or give clue?

thank you ... again!

Johan

We have several matrices that cause the SymmetricEigensolver3x3 to compute NaNs when fast math is turned on in our code.

For example

| 90.270270270270231,       8.6380368027297633e-16,    -3.4176970386003999e-15 |
| 8.6380368027297633e-16,   179.99999999999986,        0.00000000000000000     |
| -3.4176970386003999e-15,  0.00000000000000000,       90.270270270270231      |

The eigen vectors are the x-, y-, and z-basis vectors and the eigen values are the diagonal, as the very small values are essentially zero.

This is because the fast math option replaces multiple divides by the same value as a 1.0/value followed by multiplications (a usually valid transformation). This is fine and does not indicate a bug, but it does show that the code is not robust to different methods of compilation.

The offending method is GetCosSin, specifically,

If the value of maxAbsComp is denormalized, as happens when solving the given matrix above, then 1.0/maxAbsComp (a value computed by the machine code generated by the compiler with fast math turned on), will be infinity. The result of the overall math with this transformation is NaN, resulting in NaNs for all eigen vectors.

For now we have mitigated the issue by compiling the entire header using precise math, as follows (in Visual Studio on Windows)

#pragma float_control( push )
#pragma float_control( precise, on )
#include "GteSymmetricEigensolver3x3.h"
#pragma  float_control(pop)

It is best, however, to not have to do this for all the code in the header.

Again, this does not indicate a bug with the code, but it does show that the code is not robust to different methods of compilation. This is usually the case for floating point libraries. We thought, instead, that you would be interested in this nuance.

Should we assume that the Geometric Tools library requires precise floating point math in order to be robust?

The project that reproduces this is :
Svd.zip

I created a simple rotation matrix of 30 degrees around X. Then I use SingularValueDecomposition to get the factoring A = U S Vt.
I assume that if I multiply the factors back together I'll get the original rotation matrix back. But that isn't true.

Original matrix A =
[ 1 0 0;
0 0.866025 -0.5;
0 0.5 0.866025]

Here A = U * S * transpose(V)
A = [ 1 0 0;
0 -0.866025 -0.5;
0 -0.5 0.866025 ]

Which is not a rotation matrix since the diagonal values 0.866 don't ​have the same sign.
I looked up "Matrix Computations" by Golub and on page 80 it shows that for the thin SVD where m >= n, A = U * S * Vt so that looks right. I posted this question to the Geometry3sharp where I originally encounted this, but that is C# port of this C++ code and now I've seen the same thing in the C++ code.
Any help is appreciated.

int main()
{
   ​double t = 30.0 * GTE_C_DEG_TO_RAD;
   ​double rot30X[] = { 1.0, 0.0, 0.0,
                       ​0.0, cos(t), -sin(t),
                       ​0.0, sin(t), cos(t) };

   ​//SingularValueDecomposition(int numRows, int numCols, unsigned int maxIterations)
   ​gte::SingularValueDecomposition<double> svd(3, 3, 100);
   ​svd.Solve(rot30X, -1);

   ​double U[9];
   ​double S[3];
   ​double V[9];

   ​svd.GetSingularValues(S);
   ​svd.GetU(U);
   ​svd.GetV(V);

   ​std::array<double, 9> Uarray;
   ​std::memcpy(Uarray.data(), U, 9 * sizeof(double));

   ​std::array<double, 9> Varray;
   ​std::memcpy(Varray.data(), V, 9 * sizeof(double));

   ​Matrix3x3<double> Umat(Uarray);
   ​Matrix3x3<double> Vmat(Varray);
   ​Matrix3x3<double> Smat = { S[0],  0.0, 0.0,
                               ​0.0,  S[1], 0.0,
                               ​0.0,  0.0 , S[2] };

   ​Matrix3x3<double> Amat = Umat * Smat * Transpose(Vmat);

``

Over several years, I have had reports that when an outer-polygon vertex is visible to multiple inner-polygon vertices, the x-sort is necessary to choose the first inner polygon to combine with the outer polygon. However, combining the remaining inner polygons using decreasing x-value does not always work. No reproducers were provided to me, apparently because the reporters implemented the algorithm from the PDF. In the Geometric Tools implementation, the problem does not occur with 2 inner polygons. It is possible to choose a configuration of 3 inner polygons to demonstrate the need for the additional sorting. This step requires a sort of the inner-polygon extreme vertices in a circular manner about the outer-polygon vertex. I had previously added SortPointsOnCircle.h to support this. The TriangulateEC code needs to include this sort.

https://github.com/davideberly/GeometricTools/blob/4a8f9d6803ed2210cfe8bb47343d3bb468b7dd34/GTL/Mathematics/Distance/3D/DistSegment3Triangle3.h#L42C55-L42C55

Hi, this is an excellent resource. I have Geometric Tools For Computer Graphics, Robust and Error Free.., and Game Physics so I'm familiar to your book provided source code, but I really like the GitHub release.
I have been trying to use with the aid of Game Physics, the RigidBody.h class and the associated void Update(Real t, Real dt). I know from your books and related resources that upon time marching (Update) at some frequency (not often noted, recommendation?) I should ensure I normalise the Quaternion. Here this is I guess the member variable Quaternion<Real> mQuatOrient;.
I can't find anywhere explicitly where the function Real Quaternion::Normalize(Quaternion<Real>& q) is called in Update.

I have therefore two questions:

1. Should I call Real Quaternion::Normalize(Quaternion<Real>& q) after a call to Update? If so after normalising Quaternion<Real> mQuatOrient;, should I perform any subsequent operations on the other member variables of RigidBody?
2. I suspect this is being normalised elsewhere through other mechanics, if that is so, could you point that out to me?

Thanks,
Andy

I don't know where to ask this question, sorry if i'm at the wrong place.

I work in 2D and I need a "Polygon2" object with some arc sides. (some or all Segment2 replaced by Arc2 objects). I think it is not yet possible. Do you have any advice? Will this feature be available one day?

In 3D, the class Cylinder3 has both Arc and Line segments ... so maybe it is "almost possible" ?

I need to do boolean operations like AND, OR, XOR, ... on those "2D arc polygons".

Thank you!

According to code, apart of the X and Y coordinates also the location (index inside the vector of available vertices) is hashed and used in comparation, so I think it will never detect the duplication.

The minimum-volume box sample application shows that MinimumVolumeBox3 is broken. The MVB3 code was modified late last year and unit tested, but I need to investigate.

Hi David.

I see you're using newer add_compile_definitions CMake commands in the CmakeLists.txt files; these new commands are not compatible with older (< 3.12) CMake versions still used in distribution like CentOS 8, and this prevents GTengine-5.1 builds:

+ /usr/bin/cmake -DCMAKE_C_FLAGS_RELEASE:STRING=-DNDEBUG -DCMAKE_CXX_FLAGS_RELEASE:STRING=-DNDEBUG -DCMAKE_Fortran_FLAGS_RELEASE:STRING=-DNDEBUG -DCMAKE_VERBOSE_MAKEFILE:BOOL=ON -DCMAKE_INSTALL_PREFIX:PATH=/usr -DINCLUDE_INSTALL_DIR:PATH=/usr/include -DLIB_INSTALL_DIR:PATH=/usr/lib64 -DSYSCONF_INSTALL_DIR:PATH=/etc -DSHARE_INSTALL_PREFIX:PATH=/usr/share -DLIB_SUFFIX=64 -DBUILD_SHARED_LIBS:BOOL=ON -DCMAKE_BUILD_TYPE:STRING=Release -DBUILD_RELEASE_LIB:BOOL=ON -DBUILD_SHARED_LIB:BOOL=ON .
-- The C compiler identification is GNU 8.3.1
-- The CXX compiler identification is GNU 8.3.1
-- Check for working C compiler: /usr/bin/cc
-- Check for working C compiler: /usr/bin/cc -- works
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Detecting C compile features
-- Detecting C compile features - done
-- Check for working CXX compiler: /usr/bin/c++
-- Check for working CXX compiler: /usr/bin/c++ -- works
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Detecting CXX compile features
-- Detecting CXX compile features - done
CMake Error at Applications/CMakeLists.txt:10 (add_compile_definitions):
  Unknown CMake command "add_compile_definitions".
-- Configuring incomplete, errors occurred!
See also "/builddir/build/BUILD/GeometricTools-GTE-version-5.1/GTE/CMakeFiles/CMakeOutput.log".

Using add_definitions should resolve this issue.

I am getting a very wrong result when using GTE for fitting a cone to the points from a mesh i created
I uploaded the mesh in question and I also provided a text file that contains only the points here:
https://drive.google.com/file/d/1Lhbuk2AkdTGUXaOuDZ03tlF4UC_-zWlJ/view?usp=sharing

Which looks like this (a simple cone)

I used the following code adapted from the sample here
https://github.com/davideberly/GeometricTools/blob/master/GTE/Samples/Mathematics/FitCone/FitConeWindow3.cpp

The input are ALL the vertices of the STL in question.

``
size_t const maxIterations = 4;
double const updateLengthTolerance = (double) 1e-04;
double const errorDifferenceTolerance = (double) 1e-08;
bool useConeInputAsInitialGuess = false;

double const lambdaFactor = (double) 0.001;
double const lambdaAdjust = (double) 10.0;
size_t const maxAdjustments = 8;

fitter(numPoints, conePoints, maxIterations, updateLengthTolerance, 
	errorDifferenceTolerance, lambdaFactor, lambdaAdjust, maxAdjustments, useConeInputAsInitialGuess,
	coneVertex, coneAxis, coneAngle);

the thing is, the resulting coneVertex is way off or wrong I rendered a point/circle on it just to demonstrate

my other test cases are OK except for this one, why is this? and how should I handle the issue.
I used the latest version from github.

Dear all,

I was just trying to compile the latest version of GTE using the provided CMake workflow, and I hit a lot of conflicts between the BaseEngine class and its daughters, especially due to the implicit overriding of some methods that now (from C++ 11) require the override keyword.
I could fix it and start a new Pull request, but I do not know whether you would rather mark the daughter methods as override or remove the inheritance or remove BaseEngine ....

Anyways, here is the cmake.log that I got by running:

mkdir -p build && cd build
#-
cmake \
-DCMAKE_BUILD_TYPE:STRING=Release \
-DCMAKE_C_COMPILER=clang \
-DCMAKE_CXX_COMPILER=clang++ \
-DBUILD_SHARED_LIBS=ON \
-DBUILD_RELEASE_LIB:BOOL=TRUE \
-DBUILD_SHARED_LIB:BOOL=TRUE \
-S .. -B .
#-
cmake --build . --config Release --parallel 16

I use LLVM v13 (AppleClang 13.0.0.13000029) on a MacBook Pro with an Intel i7 chip.

Looking forward to hearing from you,
Best,

Thibault

    Line2<float_t> line2_7({0.0f, 0.0f}, {1.0f, 1.0f});

    Circle2<float_t> circle2_2({0.0f, 0.0f}, 1.0f);


    IntrLine2Circle2<float_t> intrLine2Circle2;

    auto result9 = intrLine2Circle2(line2_7, circle2_2);

and the result is [-1,-1] [1,1], absolutely it's wrong and the line2 and arc2 intersection got the same wrong result.

When trying to calculate a plane to plane intersection with the below input, the origin point for the resulting line looks wrong:

Input: plane1: (origin=(0, 0, -6), normal vector=(1, 4, -1)), plane2:(origin(0, 0, 4), normal vector(1, -2, 1))

The point p=(5, 0, -1) is a known point that it is on the resulted intersecting line of the two planes so the next assert should be true:

gte::Vector3 vA{ 1.0, 4.0, -1.0 };
gte::Normalize(vA);
gte::Vector3 vB{ 1.0, -2.0, 1.0 };
gte::Normalize(vB);

gte::Plane3 A{ vA, 6.0 };
gte::Plane3 B{ vB, 4.0 };

gte::FIQuery<double, gte::Plane3, gte::Plane3> query;

const auto result = query(A, B);

assert(gte::Length(gte::Cross((gte::Vector3{ 5, 0, -1 } - result.line.origin), result.line.direction)) < 0.00000

but it fails. The direction of the intersection line is ok, it is only the origin line.

In the image the point B is the returned origin point for the intersection.