CGAL users discussion list

[Karl Gaize <>]

It probably is possible to run my algorithm in the original 3d plane, however at this point in time it would probably take me a while to revise it to do this, and I'm under pressure to get something 
working as fast as possible. I may have to go down that route.

essentially, what I want to be using is a boolean subtract operation on a 3d 
polyhedral surfaces, but without being able to get extra funding to license 
the required modules, it isn't going to happen.
What I decided to do was implement a context specific algorithm in 2d to 
handle the specific subtraction that I want (knowing the specific layout and 
structure of the source geometry(s) helps)

It's annoying that I know the algorithm works, when given data in the correct plane, it's just the translation to/from the plane that causes the errors and causes the final mesh facets to be 
non-planar when I return them to my host application.

On 19/03/2010 14:51, Andreas Fabri wrote:
> Hi Karl,
>
> As Ben pointed out, iterative algorithms are nothing you should
> run with an exact constructions kernel.
>
> You say that you rotate something in order to get it into the 2D
> plane, run a 2D algorithm and then rotate it back.
>
> Sometimes it is possible to avoid that and run the 2D algorithm
> directly in the slanted plane.
>
> For one commercial customer we developed a 2D Delaunay triangulation
> for points on a slanted plane, that instead of in-circle predicates
> uses in-sphere predicates. In this way it works on the 3D input
> without any transformation going on. Maybe something similar
> might work for your application.
>
> Concerning GMP, it is not part of CGAL, but a third-party library
> distributed under the LGPL, that is, it can be used freely in
> commercial applications.
>
> best regards,
>
> andreas
>
>
> On 19/03/2010 15:26, Karl Gaize wrote:
> > thanks for the input Ben, let me just throw a few things back at you
> > though....
> >
> > I've tried using a filtered kernel and couldn't find any difference in
> > its working, my algorithm failed the same way, at the same point as it
> > did with the non-filtered kernel.
> >
> > I've looked at the exact predicates inexact constructions kernel, and I
> > don't think that it would help in this case, the main problem being that
> > I'm inherently working with constructed
> > geometry, as I have to do a couple of affine transformations to get the
> > geometry from its original 3d into the XY plane for my algorithm to work.
> >
> > I can't use GMP unless I can get a commercial license for it, which we
> > have for CGAL, but due to limited finances, we only have licenses for
> > the CGAL core and HalfedgeDS data structures.
> > this also means we can't use the polygon and polyhedron operations,
> > arrangements or anything like that.
> >
> > It's definitely the "infinite" mantissas that are causing me the
> > problems in an exact kernel though, as an inspection of the data
> > structures reveals mantissa lengths of anywhere upwards of 50,000
> > entries. This is primarily caused by, as you say, my algorithm being
> > highly constructive. I'll have a look through to see if there are any
> > natural breakpoints where I can apply an approximation rounding before
> > carrying on, but my feeling is that even between the rounding steps, my
> > mantissas are going to go through the roof as I need to use a *lot* of
> > line/line intersections to generate new vertices within the mesh.
> >
> > your point about leveraging the other CGAL algorithms is a good one, but
> > again I'm limited by our license and whatever functionality I can bolt
> > on top of it
> >
> > Karl
> >
> > On 19/03/2010 13:47, Ben Supnik wrote:
> > > Hi Karl,
> > >
> > > One or two thoughts from my own experience on speed. Basic stuff:
> > >
> > > - Fundamentally an infinite precision operation is going to be a lot
> > > more expensive than floating point.
> > >
> > > - The various filtering and lazy kernels _do_ help a lot. They're all
> > > adapters that defer the cost of the heavy op until it is really needed.
> > >
> > > - Depending on your algorithm can you use an exact predicates, inexact
> > > constructions kernel? Only part of CGAL will tolerate this, but it is a
> > > lot faster than exact constructions.
> > >
> > > - You might want to try GIMP instead of MP_float...when I tested both,
> > > GIMP was faster, although not by astoundingly large margins.
> > >
> > > More subtle:
> > >
> > > - If you can accept rounding error in your app, and you can identify
> > > points where you can round without breaking CGAL, "truncating" your CGAL
> > > results before they go back into CGAL can be a big speed win.
> > >
> > > The issue is that CGAL is going to build up longer and longer mantissas
> > > as it continues to construct exact geometry. If you are doing a highly
> > > constructive algorithm (like inserting all sorts of derived segments
> > > into an arrangement) the new points that you are "building" may have
> > > very long mantissas due to the way the math works out.
> > >
> > > CGAL will never simplify them, and your calculations become
> > > proportionally more expensive. If you know you don't need that kind of
> > > precision AND you can find a step where you can round without breaking a
> > > CGAL assumption, building a new CGAL structure off of th approximation
> > > of the old one will help.
> > >
> > > (In my code I was building an inset polygon out of the faces of an
> > > arrangement. Since the arrangement is already the intersection of many
> > > lines, most of its "discovered" vertices are going to have long
> > > mantissas. The inset/buffer operation was thus being run on very
> > > expensive exact input data. Since my buffer code could handle degenerate
> > > polygons and other ugly cases, I simply took my input faces, rounded
> > > their contours to double, and then work on those. The resulting inset
> > > operation was _much_ faster.)
> > >
> > > - I have found CGAL's speed to be very good, but in my own conversion to
> > > CGAL from my own proprietary floating point code, it has taken a while
> > > to discover that speed. The reason is that CGAL is very strong
> > > _algorithmically_ whereas my code tended to be very constructive. As I
> > > stepped back and replaced whole algorithms with superior CGAL versions I
> > > ended up getting more work out of the computer in less time, but the
> > > first "direct" port was fairly unusable.
> > >
> > > For example, my old arrangement code could do some copy and insert
> > > operations faster than CGAL (because the underlying calculation was
> > > double - a CGAL arrangement based on cartesian double would probably
> > > have been just as fast as mine, were that a legal instantiation).
> > >
> > > But CGAL has sweep-based algorithms that let you do things like
> > > whole-arrangement merges very efficiently. As I started leveraging these
> > > wider algorithms, whole chunks of slow code were replaced by something
> > > with a better O(N).
> > >
> > > Anyway, hope that helps.
> > >
> > > cheers
> > > ben
> > >
> > > Vicomt wrote:
> > > > OK, so I have a problem, a couple of problems in fact.
> > > >
> > > > The current project I'm working on works as a plugin DLL within another
> > > > application, this other application is a double based CAD engine, it
> > > > has
> > > > it's won problems with precision which it gets round by using
> > > > tolerances.
> > > >
> > > > I wanted to go away from toleranced or inherently inaccurate geometry,
> > > > so I
> > > > started off using the exact_predicates_exact_construction kernel
> > > > based on
> > > > the internal MP_Float type. thisngs seems to go well until I started
> > > > noticing some serious problems with speed, not 25% or even 50% slower,
> > > > these
> > > > algorithms seemed to run considerably slower, somwhere in the region of
> > > > 10-20 times the amount of time taken. so I gave up for a while. I
> > > > dropped
> > > > back to using a cartesian<double> kernel and started building my own
> > > > methods
> > > > with would allow me to use tolerances when I needed them.
> > > >
> > > > I got everything working - success, or so I thought, until I realised I
> > > > wasn't correctly handling certain geometrical cases, to fix this I
> > > > had to
> > > > introduce a couple of transformations (rotation around an axis) to
> > > > get my
> > > > geometry in a known format before I processed the algorithm. That's
> > > > when it
> > > > all fell apart.
> > > >
> > > > with a double precision kernel, rotating a facet a couple of times,
> > > > then
> > > > modifying that facet, and rotating back to my original coordinate space
> > > > introduced errors. errors big enough for various CGAL functions to stop
> > > > working - like plane_3::has_on() which returns false when my point is
> > > > literally 1exp-15 units away from the plane.
> > > >
> > > > so I went back to an exact kernel again, and I'm still sat here over
> > > > an hour
> > > > after I started the run. when the double kernel runs in approximately 2
> > > > tenths of a second.
> > > >
> > > > I'm confused. Is there something I could be doing which results in
> > > > MP_Float
> > > > based calculations being thousands of times slower? is there any way I
> > > > can
> > > > make CGAL tolerant of tiny distances in case there's nothing I can do
> > > > with
> > > > the complex numbers?
> > > >
> > > > I hope someone can send some enlightenment my way.
> > > >
> > > > Karl