CGAL users discussion list

[Rostislav Khlebnikov <>]

Hello Sebastien,

I made some more experiments and here are the results.
First, the debug version for MSVS 2013. It seems to me that the fact that the release version works might be just a lucky coincidence. Please refer to the code attached (I tried to keep it as clean as possible and even removed any references to VTK, but maintained the overall iterator structure). What I witnessed when debugging is that the triangle returned for bbox computation (see AABB_traits.h, Line 356) is invalidated before the bbox() method is called. Diving deeper into the code I noticed that the problem (if it is in fact a problem) is in property_map.h, Line 54. The get() method accepts iterator by value, meaning in my case that the iterator is created, the within-iterator cache is created, and then upon return from get() function, the iterator is destroyed, making the cached triangle (returned by reference) invalid! When I changed this line to accept the iterator by const reference, the debug version also started working well. Note, that changing the Reference type in the iterator_facade to K::Triangle_3 also solves the problem (at some expense of performance I assume).

For Linux version, however, this changes nothing, but something tells me that there is still something wrong with the iterator. I am completely lost what though.
With Linux, I decided to start afresh and installed Ubuntu 14.04 LTS. The default compiler that comes with this version is gcc 4.8.2. Once I had no luck with it, I installed 4.9.1 although I don't think the compiler is the issue. As an additional measure, I removed the -std=c++11 flag (just in case). I have also used CGAL 4.5-beta1. I have attached the code with a #define within that show what I observe. Notice that this experiments use the Reference type of iterator_facade set to K::Triangle_3 (if SHOW_WORKING_VERSION is set to 0), so the aforementioned issue within property_map.h should have no effect. Basically the only code that doesn't hang for me is: when the Reference type of iterator_facade is left as default, and my iterator has the copy constructor which writes something about the _cache variable to the std::out. I would guess that this is a similar "lucky coincidence" as with the MSVS 2013 release version. Some combinations of writing to std::cout or not, having a copy constructor or not, and setting the Reference type to Value type or leaving it at Value& lead to seg fault, but something tells me that this is quite irrelevant.

Anyway, what I would like to know is: does my iterator not satisfy some requirements of the AABB_Tree? Or perhaps my "proposed" change to property_map makes sense?
Also, it seems to me that the whole thing with this caching iterator is pretty useless - originally I thought that it would help save memory (which it would if the triangles were to be built on the fly), but I think at least for now performance is more important for me. In this case, it would be easier and less code if I basically just converted the triangles from VTK to CGAL and stored them in an std::vector<K::Triangle_3> which would likely work just as fast and 100% correctly. Do you think this is correct?

Thank you,
   Rostislav.

On 22/09/2014 14:50, Sebastien Loriot (GeometryFactory) wrote:

On 09/18/2014 08:08 PM, Khlebnikov, Rostislav wrote:

Please let me know if a minimal code with data would help - I'd be happy to send it.

Yes please.

Sebastien.

Rostislav.

On 18 Sep 2014, at 18:25, "Rostislav Khlebnikov" <> wrote:

Hello,

I have some very weird behavior of the same code on different platforms and for different build types.

So basically the code works fine only on one configuration out of four for me. It is Release version on Windows (Windows, MSVS 2013, x64, CGAL 4.4 installed with the CGAL-4.4-Setup.exe installer and then built with CMake and MSVS 2013).
The Debug version always returns zero intersections. The code and the data are literally the same.

I have also tried to build the Linux version. I used Ubuntu 13.10 x64, gcc 4.8.1, libgmp and libmpfr installed using apt-get, and CGAL 4.4 compiled from source using CMake. The only flag I changed when building CGAL and my test application  is adding -std=c++11 - i.e. they are compiled with -frounding-math.
Here, none of the versions actually work. The Debug version reports incorrect (I mean not even close to the windows ones) results or crashes with segfault, and the Release version hangs on building the AABB tree if I use my custom iterator or crashes with segfault is I use a simple std::list of triangles.

Do you have any hints why this might happen?

Thank you for your help,
   Rostislav.

On 10/08/2014 15:24, Rostislav Khlebnikov wrote:
Hello Sebastien,

yes, indeed - it is the tree.build() call that makes everything logical.
Honestly, I just should RTFM better - I thought that accelerate_distance_queries() call was responsible for this, which does no good for intersections anyway and just eats more memory for KD tree.
So, I reverted to the iterator which returns triangles by value constructing them on-the-fly and set the CGAL::Tag_true as the last template parameter for primitive.
The test results with are mixed (Isect shows the average over 100 all_intersections() calls, timed with QueryPerformanceCounter):

NO CACHE:
Build tree: 8.97505s
nConversions: 82950772
Isect: 2.97875ms

CGAL CACHE:
Build tree: 8.69819s
nConversions: 72620628
Isect: 1.97289ms

WITHIN-ITERATOR CACHE:
Build tree: 0.647395s
nConversions: 568938
Isect: 1.81151ms

Hope this helps,
   Rostislav.

On 10/08/2014 14:39, Sebastien Loriot (GeometryFactory) wrote:

On 08/09/2014 05:59 PM, Rostislav Khlebnikov wrote:
Hello again,

I am just quite curious that the first call to the all_intersections is
very very slow compared to the rest. For example for mesh with about
500k triangles, the first call takes about 10 seconds, while the all the
following ones with the same cutting query take about 3 milliseconds,
giving the difference of 3000 times! Is there some lazy processing going
on that are triggered by the first call? Is this normal anyway?

Try to call tree.build() before, it is probably the construction of the
tree that is happening at the first call.

Sebastien.

Additionally, by adding the cached converted triangle as a member of
Triangles_const_iterator, setting the reference template parameter to
default and returning K::Triangle_3 const& from derefence() will speed
up the first 10 times (down to 1 second) and also speed up the
subsequent calls to about 2 milliseconds. It is clear why this happens,
but I just wanted to mention it.

Note that the last template parameter of AABB_triangle_primitive can be
used to cache the triangle in the primitive. Could you give it a try
and confirm it is as fast as your setting?

Thanks,

Sebastien.

So, if you could answer the questions in the first paragraph - that
would be absolutely great!

Thank you,
    Rostislav.

On 08/08/2014 00:30, Rostislav Khlebnikov wrote:
Hello Sebastien,

yes, indeed changing the signature of the Triangles_const_iterator to

class Triangles_const_iterator
    : public boost::iterator_facade<
      Triangles_const_iterator
    , K::Triangle_3 const           // Value
    , boost::forward_traversal_tag  // CategoryOrTraversal
    , *K::Triangle_3*
    >

helped resolving the issue. Just writing this to say thanks to you and
perhaps help anyone looking into similar problem.

Thanks again,
  Rostislav.

PS: still weird that it worked in release :)

On 07/08/2014 23:33, Sebastien Loriot (GeometryFactory) wrote:
Thanks for the minimal reproducible example!

Actually, if you read again the doc of boost::iterator_facade
you'll see you're using the default for reference, which is
value&. In your case, reference should be value (Triangle is a
temporary).

Sebastien.

On 08/07/2014 11:14 PM, Rostislav Khlebnikov wrote:
Hi everyone,

I'm using AABB_tree to compute intersections of a VTK poly data with a
plane. When I just convert the triangles from VTK to CGAL and store
them
in std list, everything works fine. However, I would like to reduce
storage requirements by creating a triangle iterator that iterates over
the VTK triangle data.
Code in main.cpp here shows how I do it http://pastebin.com/kNLQevXV
<http://pastebin.com/sKPFHTT2>

In Release version everything works fine, but in Debug version -
intersections are never found! (Funnily enough it's a debug version
that
fails). I tried finding the problem - but I don't seem to understand
it.
What I found is that when CGAL uses the kernel to convert from
Triangle_3 to TriangleC3 with rep() and then uses this TriangleC3's
vertex() method on line 1909 in function_objects.h, the TriangleC3
'base' variable becomes corrupted during get(base) call at line 94 in
Triangle_3.h (i.e. correct coordinates are overwritten in what seems to
be stack initialization in function call when I looked at disassembly).

Is it something wrong that I do with my custom iterator? Or perhaps
it's
a bug in VS2013 compiler (I saw some bug reports regarding stack
corruption for VS2012 such as this
<http://stackoverflow.com/questions/11000798/structure-parameter-corrupted-on-function-call>,

so perhaps it's not completely resolved).

I attached all the code, input files and cmake file, so if someone who
has VTK and CGAL could quitckly test it on their platform. For me the
release version returns 54 intersections and debug - 0.

Thank you in advance,
    Rostislav.

CGAL installation info:
Windows 8.1, MSVS 2013, x64
CGAL 4.4 installed with the CGAL-4.4-Setup.exe installer and then
built
with CMake and MSVS 2013.

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss

// Author : Pierre Alliez
#include <iostream>
#include <list>
#include <CGAL/Simple_cartesian.h>
#include <CGAL/AABB_tree.h>
#include <CGAL/AABB_traits.h>
#include <CGAL/AABB_triangle_primitive.h>


double coords[] = {
    29.18630027770996, 174.8886260986328, -62.78001022338867, 
28.372425079345703, 162.0009307861328, -65.0921859741211, 25.67314338684082, 
174.9927520751953, -49.503562927246094,
    0.2103467881679535, 159.42037963867188, -277.2245788574219, 
13.64248275756836, 161.1861572265625, -276.2463073730469, 0.3464265763759613, 
160.7919464111328, -264.30694580078125,
    31.606674194335938, 159.23736572265625, -79.44971466064453, 
24.031925201416016, 159.91285705566406, -88.17604064941406, 
28.51704216003418, 174.669921875, -79.99639129638672,
    -2.4768929481506348, 150.18797302246094, -108.59989929199219, 
-12.030159950256348, 143.54347229003906, -109.60794830322266, 
-10.126791954040527, 139.50340270996094, -98.82649230957031,
    9.395136833190918, 134.27203369140625, -95.49534606933594, 
-1.4869920015335083, 131.2742156982422, -93.83939361572266, 
11.852248191833496, 129.7545623779297, -109.76504516601562,
    -2.6369524002075195, 127.79691314697266, -124.92886352539062, 
-11.963970184326172, 132.1261749267578, -109.15593719482422, 
-11.131210327148438, 134.17269897460938, -120.17386627197266,
    10.668848991394043, 194.10964965820312, -154.51881408691406, 
10.066263198852539, 193.6329803466797, -171.33009338378906, 
5.664018630981445, 191.9407196044922, -156.27230834960938,
    11.698558807373047, 149.77438354492188, -67.33330535888672, 
14.544828414916992, 142.69973754882812, -78.03868865966797, 
25.19605255126953, 148.98193359375, -79.51082611083984,
    -2.4768929481506348, 150.18797302246094, -108.59989929199219, 
-3.365452766418457, 146.0531463623047, -93.46614837646484, 
1.8753833770751953, 152.99168395996094, -104.65605163574219,
    1.7841202020645142, 130.89108276367188, -137.36697387695312, 
15.414437294006348, 127.06056213378906, -123.71853637695312, 
-2.6369524002075195, 127.79691314697266, -124.92886352539062,
    9.83181381225586, 192.99082946777344, -186.9521026611328, 
13.714397430419922, 201.11087036132812, -170.16375732421875, 
10.066263198852539, 193.6329803466797, -171.33009338378906,
    14.992523193359375, 145.1206817626953, -93.64944458007812, 
14.544828414916992, 142.69973754882812, -78.03868865966797, 
9.395136833190918, 134.27203369140625, -95.49534606933594,
    28.755552291870117, 203.8203582763672, -93.77369689941406, 
26.64963150024414, 204.46548461914062, -108.61288452148438, 
18.69825553894043, 200.91824340820312, -110.31458282470703,
    2.6021358966827393, 173.62451171875, -247.70054626464844, 
-0.5297830104827881, 158.86598205566406, -252.25892639160156, 
9.064677238464355, 163.0745849609375, -265.5377502441406,
    32.49477005004883, 156.94677734375, -507.7084655761719, 
34.496185302734375, 156.0312042236328, -521.6897583007812, 37.86516189575195, 
156.7658233642578, -513.381103515625,
    36.2860107421875, 151.49594116210938, -524.5477294921875, 
34.496185302734375, 156.0312042236328, -521.6897583007812, 38.43404769897461, 
152.02105712890625, -530.784423828125,
    8.097879409790039, 187.4866485595703, -232.36233520507812, 
4.315632343292236, 186.48275756835938, -231.96592712402344, 
3.4246609210968018, 187.8110809326172, -217.2212371826172,
    2.5345685482025146, 172.4355926513672, -262.2419738769531, 
2.6021358966827393, 173.62451171875, -247.70054626464844, 8.077503204345703, 
184.8253631591797, -247.26480102539062,
    9.007757186889648, 161.76893615722656, -324.61798095703125, 
3.429384708404541, 160.6028594970703, -323.5035705566406, 4.853285789489746, 
168.54629516601562, -325.0062561035156,
    -11.521470069885254, 149.80848693847656, -50.379573822021484, 
-11.550424575805664, 157.72024536132812, -49.84595489501953, 
-9.887701988220215, 154.5082244873047, -56.29947280883789,
    5.960109233856201, 149.5780029296875, -358.83203125, 11.39888858795166, 
158.1283416748047, -353.8124694824219, 10.722811698913574, 149.6037139892578, 
-354.39154052734375,
    10.422451972961426, 174.78964233398438, -263.82684326171875, 
8.244054794311523, 174.72669982910156, -247.31585693359375, 
2.6021358966827393, 173.62451171875, -247.70054626464844,
    32.49477005004883, 156.94677734375, -507.7084655761719, 
40.070308685302734, 155.63668823242188, -523.67138671875, 36.2860107421875, 
151.49594116210938, -524.5477294921875,
    38.763797760009766, 175.7540283203125, -68.37883758544922, 
39.341758728027344, 175.20016479492188, -76.29432678222656, 
39.72635269165039, 190.09410095214844, -77.21231842041016,
    -0.04478957876563072, 156.5264892578125, -60.68000411987305, 
12.453887939453125, 160.12025451660156, -49.74186325073242, 
13.793533325195312, 159.62319946289062, -63.151756286621094,
    0.32879209518432617, 136.0102081298828, -84.23665618896484, 
14.544828414916992, 142.69973754882812, -78.03868865966797, 
0.4302023947238922, 145.18849182128906, -78.6853256225586,
    26.64963150024414, 204.46548461914062, -108.61288452148438, 
28.755552291870117, 203.8203582763672, -93.77369689941406, 
26.893264770507812, 193.40029907226562, -91.689453125,
    -2.1577908992767334, 146.2375946044922, -266.4775695800781, 
-1.99563467502594, 145.8889923095703, -274.2352600097656, 8.580360412597656, 
142.18040466308594, -269.999267578125,
    -11.521470069885254, 149.80848693847656, -50.379573822021484, 
-1.4327821731567383, 147.3152313232422, -48.19434356689453, 
-11.550424575805664, 157.72024536132812, -49.84595489501953,
    32.49477005004883, 156.94677734375, -507.7084655761719, 
40.070308685302734, 155.63668823242188, -523.67138671875, 37.86516189575195, 
156.7658233642578, -513.381103515625,
    3.429384708404541, 160.6028594970703, -323.5035705566406, 
2.614022970199585, 160.56338500976562, -308.92919921875, 7.482606410980225, 
167.59194946289062, -321.3027038574219,
    8.33150863647461, 189.7926788330078, -217.17889404296875, 
1.9665356874465942, 179.02220153808594, -218.0140380859375, 
8.467718124389648, 179.02940368652344, -222.98666381835938,
    40.070308685302734, 155.63668823242188, -523.67138671875, 
40.298152923583984, 150.8389892578125, -526.1549682617188, 38.43404769897461, 
152.02105712890625, -530.784423828125,
    2.074990749359131, 181.18576049804688, -205.4715576171875, 
9.010037422180176, 191.89877319335938, -202.2879180908203, 2.887479782104492, 
187.14349365234375, -201.91880798339844,
    2.5345685482025146, 172.4355926513672, -262.2419738769531, 
0.3464265763759613, 160.7919464111328, -264.30694580078125, 
-0.5297830104827881, 158.86598205566406, -252.25892639160156,
    8.363688468933105, 149.29444885253906, -429.6105651855469, 
-1.001146674156189, 146.45069885253906, -415.33294677734375, 
-1.2460546493530273, 146.16213989257812, -430.76678466796875,
    28.9470157623291, 189.64215087890625, -79.90576171875, 39.72635269165039, 
190.09410095214844, -77.21231842041016, 37.976112365722656, 
200.32350158691406, -79.22931671142578,
    13.793533325195312, 159.62319946289062, -63.151756286621094, 
13.05890941619873, 161.63307189941406, -78.92259216308594, 4.964365005493164, 
154.19720458984375, -79.58180236816406,
    13.778759002685547, 146.31710815429688, -138.42466735839844, 
13.977355003356934, 128.6435546875, -138.47573852539062, 1.7841202020645142, 
130.89108276367188, -137.36697387695312,
    -10.773425102233887, 134.0447540283203, -97.55136108398438, 
-10.126791954040527, 139.50340270996094, -98.82649230957031, 
-11.963970184326172, 132.1261749267578, -109.15593719482422,
    4.964365005493164, 154.19720458984375, -79.58180236816406, 
-3.365452766418457, 146.0531463623047, -93.46614837646484, 
0.4302023947238922, 145.18849182128906, -78.6853256225586,
    4.158769607543945, 190.48501586914062, -171.66477966308594, 
3.241682529449463, 188.3593292236328, -187.84942626953125, 
10.066263198852539, 193.6329803466797, -171.33009338378906,
    -19.546314239501953, 134.98312377929688, -339.40753173828125, 
-18.855146408081055, 138.1035614013672, -354.1989440917969, 
-19.420299530029297, 138.7296142578125, -338.2610168457031,
    -18.971982955932617, 134.06002807617188, -354.68914794921875, 
-19.820068359375, 134.29212951660156, -369.31573486328125, 
-19.23091697692871, 137.72413635253906, -368.3957214355469,
    15.414437294006348, 127.06056213378906, -123.71853637695312, 
13.977355003356934, 128.6435546875, -138.47573852539062, 25.288803100585938, 
132.9503173828125, -128.03854370117188,
    2.074990749359131, 181.18576049804688, -205.4715576171875, 
1.9665356874465942, 179.02220153808594, -218.0140380859375, 
2.887479782104492, 187.14349365234375, -201.91880798339844,
    14.681483268737793, 148.12326049804688, -123.89007568359375, 
-2.4768929481506348, 150.18797302246094, -108.59989929199219, 
11.527284622192383, 144.68577575683594, -109.43207550048828,
    10.133068084716797, 154.2608642578125, -415.2780456542969, 
0.13050885498523712, 155.7189178466797, -430.0703125, 0.6555322408676147, 
155.9097137451172, -415.5462646484375,
    28.755552291870117, 203.8203582763672, -93.77369689941406, 
18.69825553894043, 200.91824340820312, -110.31458282470703, 
21.321714401245117, 201.83338928222656, -92.69882202148438,
    13.465243339538574, 172.83975219726562, -276.4399108886719, 
13.64248275756836, 161.1861572265625, -276.2463073730469, 9.064677238464355, 
163.0745849609375, -265.5377502441406,
    -3.365452766418457, 146.0531463623047, -93.46614837646484, 
0.32879209518432617, 136.0102081298828, -84.23665618896484, 
0.4302023947238922, 145.18849182128906, -78.6853256225586,
    -12.030159950256348, 143.54347229003906, -109.60794830322266, 
-2.4768929481506348, 150.18797302246094, -108.59989929199219, 
-2.286804676055908, 147.21705627441406, -124.9409408569336,
    9.010037422180176, 191.89877319335938, -202.2879180908203, 
8.33150863647461, 189.7926788330078, -217.17889404296875, 2.887479782104492, 
187.14349365234375, -201.91880798339844,
    23.64198875427246, 196.23199462890625, -106.87743377685547, 
15.198822975158691, 195.23143005371094, -124.12861633300781, 
23.879322052001953, 204.50381469726562, -123.33671569824219,
    15.198822975158691, 195.23143005371094, -124.12861633300781, 
23.879322052001953, 204.50381469726562, -123.33671569824219, 
17.010997772216797, 202.59329223632812, -124.53376007080078,
    0.4510499835014343, 148.75099182128906, -444.157958984375, 
1.124375820159912, 156.97035217285156, -446.11761474609375, 
5.041719913482666, 158.33346557617188, -455.47528076171875,
    -15.47876262664795, 147.13807678222656, -296.1484069824219, 
-4.002422332763672, 149.16915893554688, -291.32452392578125, 
0.8906582593917847, 159.33848571777344, -292.2961730957031,
    38.763797760009766, 175.7540283203125, -68.37883758544922, 
29.18630027770996, 174.8886260986328, -62.78001022338867, 28.372425079345703, 
162.0009307861328, -65.0921859741211,
    12.997486114501953, 148.2761688232422, -369.91314697265625, 
13.168941497802734, 146.0584716796875, -384.6397399902344, 
12.536482810974121, 154.69451904296875, -384.7591247558594,
    -1.4869920015335083, 131.2742156982422, -93.83939361572266, 
-2.4928367137908936, 124.77111053466797, -108.73846435546875, 
11.852248191833496, 129.7545623779297, -109.76504516601562,
    28.9470157623291, 189.64215087890625, -79.90576171875, 
39.341758728027344, 175.20016479492188, -76.29432678222656, 
39.72635269165039, 190.09410095214844, -77.21231842041016 };
int nCoords = sizeof(coords) / sizeof(coords[0]);

typedef CGAL::Simple_cartesian<double> K;
typedef K::FT FT;
typedef K::Point_3 Point;
typedef K::Vector_3 Vector;
typedef K::Plane_3 Plane;
typedef K::Segment_3 Segment;
typedef K::Triangle_3 Triangle;

class Triangles_const_iterator
    : public boost::iterator_facade<
      Triangles_const_iterator
    , K::Triangle_3 const           // Value
    , boost::forward_traversal_tag  // CategoryOrTraversal
//    , K::Triangle_3 const           // Reference
    >
{
public:
    Triangles_const_iterator()
        : firstPointId(-1) {}

    static Triangles_const_iterator begin()
    {
        return Triangles_const_iterator(0);
    }

    static Triangles_const_iterator end()
    {
        return Triangles_const_iterator(nCoords);
    }

private:
    explicit Triangles_const_iterator(int index)
        : firstPointId(index)
    {
        _cache = createCache();
    }


    friend class boost::iterator_core_access;
    void increment() {
        firstPointId += 9;
        _cache = createCache();
    }

    K::Triangle_3 createCache() 
    {
        if (firstPointId < nCoords) {
            // Convert triangle to CGAL
            return K::Triangle_3(
                K::Point_3(coords[firstPointId + 0], coords[firstPointId + 
1], coords[firstPointId + 2]),
                K::Point_3(coords[firstPointId + 3], coords[firstPointId + 
4], coords[firstPointId + 5]), 
                K::Point_3(coords[firstPointId + 6], coords[firstPointId + 
7], coords[firstPointId + 8]));
        }
        return K::Triangle_3();
    }

    K::Triangle_3 const& dereference() const { return _cache; }

    bool equal(Triangles_const_iterator const& other) const
    {
        return firstPointId == other.firstPointId;
    }

    int firstPointId;
    K::Triangle_3 _cache;
};

typedef CGAL::AABB_triangle_primitive<K, Triangles_const_iterator> Primitive;
typedef CGAL::AABB_traits<K, Primitive> Traits;
typedef CGAL::AABB_tree<Traits> Tree;


int main()
{
    Point points[] = { Point(13.961, 167.000, -286.0), Point(13.500, 0, 
-286.5), Point(13.000, 167.500, 0) };
    Vector normal = CGAL::cross_product<K>(points[2] - points[0], points[1] - 
points[0]);
    normal = normal / sqrt(normal.squared_length());

    std::cout << "Building tree\n";

    Triangle t(Point(0, 0, 0), Point(0, 1, 0), Point(1, 1, 0));
    CGAL::Bbox_3 b = t.bbox();

    Tree tree(Triangles_const_iterator::begin(), 
Triangles_const_iterator::end());
        tree.build();

    std::cout << "Done\n";

    // counts #intersections with a plane query
    Plane plane_query(points[0], normal);

    std::vector<Tree::Intersection_and_primitive_id<Plane>::Type> segments;

    tree.all_intersections(plane_query, std::back_inserter(segments));

    std::cout << segments.size() << " intersections(s) with plane\n";

    return EXIT_SUCCESS;
}
// Author : Pierre Alliez
#include <iostream>
#include <list>
#include <CGAL/Simple_cartesian.h>
#include <CGAL/AABB_tree.h>
#include <CGAL/AABB_traits.h>
#include <CGAL/AABB_triangle_primitive.h>


double coords[] = {
    29.18630027770996, 174.8886260986328, -62.78001022338867, 
28.372425079345703, 162.0009307861328, -65.0921859741211, 25.67314338684082, 
174.9927520751953, -49.503562927246094,
    0.2103467881679535, 159.42037963867188, -277.2245788574219, 
13.64248275756836, 161.1861572265625, -276.2463073730469, 0.3464265763759613, 
160.7919464111328, -264.30694580078125,
    31.606674194335938, 159.23736572265625, -79.44971466064453, 
24.031925201416016, 159.91285705566406, -88.17604064941406, 
28.51704216003418, 174.669921875, -79.99639129638672,
    -2.4768929481506348, 150.18797302246094, -108.59989929199219, 
-12.030159950256348, 143.54347229003906, -109.60794830322266, 
-10.126791954040527, 139.50340270996094, -98.82649230957031,
    9.395136833190918, 134.27203369140625, -95.49534606933594, 
-1.4869920015335083, 131.2742156982422, -93.83939361572266, 
11.852248191833496, 129.7545623779297, -109.76504516601562,
    -2.6369524002075195, 127.79691314697266, -124.92886352539062, 
-11.963970184326172, 132.1261749267578, -109.15593719482422, 
-11.131210327148438, 134.17269897460938, -120.17386627197266,
    10.668848991394043, 194.10964965820312, -154.51881408691406, 
10.066263198852539, 193.6329803466797, -171.33009338378906, 
5.664018630981445, 191.9407196044922, -156.27230834960938,
    11.698558807373047, 149.77438354492188, -67.33330535888672, 
14.544828414916992, 142.69973754882812, -78.03868865966797, 
25.19605255126953, 148.98193359375, -79.51082611083984,
    -2.4768929481506348, 150.18797302246094, -108.59989929199219, 
-3.365452766418457, 146.0531463623047, -93.46614837646484, 
1.8753833770751953, 152.99168395996094, -104.65605163574219,
    1.7841202020645142, 130.89108276367188, -137.36697387695312, 
15.414437294006348, 127.06056213378906, -123.71853637695312, 
-2.6369524002075195, 127.79691314697266, -124.92886352539062,
    9.83181381225586, 192.99082946777344, -186.9521026611328, 
13.714397430419922, 201.11087036132812, -170.16375732421875, 
10.066263198852539, 193.6329803466797, -171.33009338378906,
    14.992523193359375, 145.1206817626953, -93.64944458007812, 
14.544828414916992, 142.69973754882812, -78.03868865966797, 
9.395136833190918, 134.27203369140625, -95.49534606933594,
    28.755552291870117, 203.8203582763672, -93.77369689941406, 
26.64963150024414, 204.46548461914062, -108.61288452148438, 
18.69825553894043, 200.91824340820312, -110.31458282470703,
    2.6021358966827393, 173.62451171875, -247.70054626464844, 
-0.5297830104827881, 158.86598205566406, -252.25892639160156, 
9.064677238464355, 163.0745849609375, -265.5377502441406,
    32.49477005004883, 156.94677734375, -507.7084655761719, 
34.496185302734375, 156.0312042236328, -521.6897583007812, 37.86516189575195, 
156.7658233642578, -513.381103515625,
    36.2860107421875, 151.49594116210938, -524.5477294921875, 
34.496185302734375, 156.0312042236328, -521.6897583007812, 38.43404769897461, 
152.02105712890625, -530.784423828125,
    8.097879409790039, 187.4866485595703, -232.36233520507812, 
4.315632343292236, 186.48275756835938, -231.96592712402344, 
3.4246609210968018, 187.8110809326172, -217.2212371826172,
    2.5345685482025146, 172.4355926513672, -262.2419738769531, 
2.6021358966827393, 173.62451171875, -247.70054626464844, 8.077503204345703, 
184.8253631591797, -247.26480102539062,
    9.007757186889648, 161.76893615722656, -324.61798095703125, 
3.429384708404541, 160.6028594970703, -323.5035705566406, 4.853285789489746, 
168.54629516601562, -325.0062561035156,
    -11.521470069885254, 149.80848693847656, -50.379573822021484, 
-11.550424575805664, 157.72024536132812, -49.84595489501953, 
-9.887701988220215, 154.5082244873047, -56.29947280883789,
    5.960109233856201, 149.5780029296875, -358.83203125, 11.39888858795166, 
158.1283416748047, -353.8124694824219, 10.722811698913574, 149.6037139892578, 
-354.39154052734375,
    10.422451972961426, 174.78964233398438, -263.82684326171875, 
8.244054794311523, 174.72669982910156, -247.31585693359375, 
2.6021358966827393, 173.62451171875, -247.70054626464844,
    32.49477005004883, 156.94677734375, -507.7084655761719, 
40.070308685302734, 155.63668823242188, -523.67138671875, 36.2860107421875, 
151.49594116210938, -524.5477294921875,
    38.763797760009766, 175.7540283203125, -68.37883758544922, 
39.341758728027344, 175.20016479492188, -76.29432678222656, 
39.72635269165039, 190.09410095214844, -77.21231842041016,
    -0.04478957876563072, 156.5264892578125, -60.68000411987305, 
12.453887939453125, 160.12025451660156, -49.74186325073242, 
13.793533325195312, 159.62319946289062, -63.151756286621094,
    0.32879209518432617, 136.0102081298828, -84.23665618896484, 
14.544828414916992, 142.69973754882812, -78.03868865966797, 
0.4302023947238922, 145.18849182128906, -78.6853256225586,
    26.64963150024414, 204.46548461914062, -108.61288452148438, 
28.755552291870117, 203.8203582763672, -93.77369689941406, 
26.893264770507812, 193.40029907226562, -91.689453125,
    -2.1577908992767334, 146.2375946044922, -266.4775695800781, 
-1.99563467502594, 145.8889923095703, -274.2352600097656, 8.580360412597656, 
142.18040466308594, -269.999267578125,
    -11.521470069885254, 149.80848693847656, -50.379573822021484, 
-1.4327821731567383, 147.3152313232422, -48.19434356689453, 
-11.550424575805664, 157.72024536132812, -49.84595489501953,
    32.49477005004883, 156.94677734375, -507.7084655761719, 
40.070308685302734, 155.63668823242188, -523.67138671875, 37.86516189575195, 
156.7658233642578, -513.381103515625,
    3.429384708404541, 160.6028594970703, -323.5035705566406, 
2.614022970199585, 160.56338500976562, -308.92919921875, 7.482606410980225, 
167.59194946289062, -321.3027038574219,
    8.33150863647461, 189.7926788330078, -217.17889404296875, 
1.9665356874465942, 179.02220153808594, -218.0140380859375, 
8.467718124389648, 179.02940368652344, -222.98666381835938,
    40.070308685302734, 155.63668823242188, -523.67138671875, 
40.298152923583984, 150.8389892578125, -526.1549682617188, 38.43404769897461, 
152.02105712890625, -530.784423828125,
    2.074990749359131, 181.18576049804688, -205.4715576171875, 
9.010037422180176, 191.89877319335938, -202.2879180908203, 2.887479782104492, 
187.14349365234375, -201.91880798339844,
    2.5345685482025146, 172.4355926513672, -262.2419738769531, 
0.3464265763759613, 160.7919464111328, -264.30694580078125, 
-0.5297830104827881, 158.86598205566406, -252.25892639160156,
    8.363688468933105, 149.29444885253906, -429.6105651855469, 
-1.001146674156189, 146.45069885253906, -415.33294677734375, 
-1.2460546493530273, 146.16213989257812, -430.76678466796875,
    28.9470157623291, 189.64215087890625, -79.90576171875, 39.72635269165039, 
190.09410095214844, -77.21231842041016, 37.976112365722656, 
200.32350158691406, -79.22931671142578,
    13.793533325195312, 159.62319946289062, -63.151756286621094, 
13.05890941619873, 161.63307189941406, -78.92259216308594, 4.964365005493164, 
154.19720458984375, -79.58180236816406,
    13.778759002685547, 146.31710815429688, -138.42466735839844, 
13.977355003356934, 128.6435546875, -138.47573852539062, 1.7841202020645142, 
130.89108276367188, -137.36697387695312,
    -10.773425102233887, 134.0447540283203, -97.55136108398438, 
-10.126791954040527, 139.50340270996094, -98.82649230957031, 
-11.963970184326172, 132.1261749267578, -109.15593719482422,
    4.964365005493164, 154.19720458984375, -79.58180236816406, 
-3.365452766418457, 146.0531463623047, -93.46614837646484, 
0.4302023947238922, 145.18849182128906, -78.6853256225586,
    4.158769607543945, 190.48501586914062, -171.66477966308594, 
3.241682529449463, 188.3593292236328, -187.84942626953125, 
10.066263198852539, 193.6329803466797, -171.33009338378906,
    -19.546314239501953, 134.98312377929688, -339.40753173828125, 
-18.855146408081055, 138.1035614013672, -354.1989440917969, 
-19.420299530029297, 138.7296142578125, -338.2610168457031,
    -18.971982955932617, 134.06002807617188, -354.68914794921875, 
-19.820068359375, 134.29212951660156, -369.31573486328125, 
-19.23091697692871, 137.72413635253906, -368.3957214355469,
    15.414437294006348, 127.06056213378906, -123.71853637695312, 
13.977355003356934, 128.6435546875, -138.47573852539062, 25.288803100585938, 
132.9503173828125, -128.03854370117188,
    2.074990749359131, 181.18576049804688, -205.4715576171875, 
1.9665356874465942, 179.02220153808594, -218.0140380859375, 
2.887479782104492, 187.14349365234375, -201.91880798339844,
    14.681483268737793, 148.12326049804688, -123.89007568359375, 
-2.4768929481506348, 150.18797302246094, -108.59989929199219, 
11.527284622192383, 144.68577575683594, -109.43207550048828,
    10.133068084716797, 154.2608642578125, -415.2780456542969, 
0.13050885498523712, 155.7189178466797, -430.0703125, 0.6555322408676147, 
155.9097137451172, -415.5462646484375,
    28.755552291870117, 203.8203582763672, -93.77369689941406, 
18.69825553894043, 200.91824340820312, -110.31458282470703, 
21.321714401245117, 201.83338928222656, -92.69882202148438,
    13.465243339538574, 172.83975219726562, -276.4399108886719, 
13.64248275756836, 161.1861572265625, -276.2463073730469, 9.064677238464355, 
163.0745849609375, -265.5377502441406,
    -3.365452766418457, 146.0531463623047, -93.46614837646484, 
0.32879209518432617, 136.0102081298828, -84.23665618896484, 
0.4302023947238922, 145.18849182128906, -78.6853256225586,
    -12.030159950256348, 143.54347229003906, -109.60794830322266, 
-2.4768929481506348, 150.18797302246094, -108.59989929199219, 
-2.286804676055908, 147.21705627441406, -124.9409408569336,
    9.010037422180176, 191.89877319335938, -202.2879180908203, 
8.33150863647461, 189.7926788330078, -217.17889404296875, 2.887479782104492, 
187.14349365234375, -201.91880798339844,
    23.64198875427246, 196.23199462890625, -106.87743377685547, 
15.198822975158691, 195.23143005371094, -124.12861633300781, 
23.879322052001953, 204.50381469726562, -123.33671569824219,
    15.198822975158691, 195.23143005371094, -124.12861633300781, 
23.879322052001953, 204.50381469726562, -123.33671569824219, 
17.010997772216797, 202.59329223632812, -124.53376007080078,
    0.4510499835014343, 148.75099182128906, -444.157958984375, 
1.124375820159912, 156.97035217285156, -446.11761474609375, 
5.041719913482666, 158.33346557617188, -455.47528076171875,
    -15.47876262664795, 147.13807678222656, -296.1484069824219, 
-4.002422332763672, 149.16915893554688, -291.32452392578125, 
0.8906582593917847, 159.33848571777344, -292.2961730957031,
    38.763797760009766, 175.7540283203125, -68.37883758544922, 
29.18630027770996, 174.8886260986328, -62.78001022338867, 28.372425079345703, 
162.0009307861328, -65.0921859741211,
    12.997486114501953, 148.2761688232422, -369.91314697265625, 
13.168941497802734, 146.0584716796875, -384.6397399902344, 
12.536482810974121, 154.69451904296875, -384.7591247558594,
    -1.4869920015335083, 131.2742156982422, -93.83939361572266, 
-2.4928367137908936, 124.77111053466797, -108.73846435546875, 
11.852248191833496, 129.7545623779297, -109.76504516601562,
    28.9470157623291, 189.64215087890625, -79.90576171875, 
39.341758728027344, 175.20016479492188, -76.29432678222656, 
39.72635269165039, 190.09410095214844, -77.21231842041016 };
int nCoords = sizeof(coords) / sizeof(coords[0]);

typedef CGAL::Simple_cartesian<double> K;
typedef K::FT FT;
typedef K::Point_3 Point;
typedef K::Vector_3 Vector;
typedef K::Plane_3 Plane;
typedef K::Segment_3 Segment;
typedef K::Triangle_3 Triangle;

// If set to 0, the original hang will be shown
#define SHOW_WORKING_VERSION 1

class Triangles_const_iterator
    : public boost::iterator_facade<
      Triangles_const_iterator
    , K::Triangle_3 const           // Value
    , boost::forward_traversal_tag  // CategoryOrTraversal
#if !SHOW_WORKING_VERSION
    , K::Triangle_3            // Reference
#endif
    >
{
public:
    Triangles_const_iterator() 
        : Triangles_const_iterator::iterator_facade_()
        , firstPointId(-1) {}

#if SHOW_WORKING_VERSION
    Triangles_const_iterator(const Triangles_const_iterator& other)
        : Triangles_const_iterator::iterator_facade_(other)
    {
        firstPointId = other.firstPointId;
        _cache = other._cache;
        //std::cout << _cache.vertex(0).x() << " ";
    }
#endif // SHOW_WORKING_VERSION

    static Triangles_const_iterator begin()
    {
        return Triangles_const_iterator(0);
    }

    static Triangles_const_iterator end()
    {
        return Triangles_const_iterator(nCoords);
    }

private:
    explicit Triangles_const_iterator(int index)
        : Triangles_const_iterator::iterator_facade_()
        , firstPointId(index)
    {
        _cache = createCache();
    }


    friend class boost::iterator_core_access;
    void increment() {
        firstPointId += 9;
        _cache = createCache();
    }

    K::Triangle_3 createCache() 
    {
        if (firstPointId >= 0 && firstPointId < nCoords) {
            // Convert triangle to CGAL
            return K::Triangle_3(
                K::Point_3(coords[firstPointId + 0], coords[firstPointId + 
1], coords[firstPointId + 2]),
                K::Point_3(coords[firstPointId + 3], coords[firstPointId + 
4], coords[firstPointId + 5]), 
                K::Point_3(coords[firstPointId + 6], coords[firstPointId + 
7], coords[firstPointId + 8]));
        }
        return K::Triangle_3();
    }

    K::Triangle_3 const& dereference() const { return _cache; }

    bool equal(Triangles_const_iterator const& other) const
    {
        return firstPointId == other.firstPointId;
    }

    int firstPointId;
    K::Triangle_3 _cache;
};

typedef CGAL::AABB_triangle_primitive<K, Triangles_const_iterator, 
CGAL::Tag_true> Primitive;
typedef CGAL::AABB_traits<K, Primitive> Traits;
typedef CGAL::AABB_tree<Traits> Tree;


int main()
{
    Point points[] = { Point(13.961, 167.000, -286.0), Point(13.500, 0, 
-286.5), Point(13.000, 167.500, 0) };
    Vector normal = CGAL::cross_product<K>(points[2] - points[0], points[1] - 
points[0]);
    normal = normal / sqrt(normal.squared_length());

    std::cout << "Building tree\n";

    Tree tree(Triangles_const_iterator::begin(), 
Triangles_const_iterator::end());
    tree.build();

    std::cout << "Done\n";

    // counts #intersections with a plane query
    Plane plane_query(points[0], normal);

    std::vector<Tree::Intersection_and_primitive_id<Plane>::Type> segments;

    tree.all_intersections(plane_query, std::back_inserter(segments));

    std::cout << "\n\n" << segments.size() << " intersections(s) with 
plane\n";

    return EXIT_SUCCESS;
}