CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

It would help if you write small answers.
I'm not able to reproduce any pb.
Please tell me what should I do to reproduce the error.

Note that AABB-tree does not have specific about the iterator
except that it must be a valid ForwardIterator.

Thanks,

Sebastien.

On 09/22/2014 06:09 PM, Rostislav Khlebnikov wrote:
> 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