CGAL users discussion list

[Ben Supnik <>]

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

--
Scenery Home Page: http://scenery.x-plane.com/
Scenery blog: http://xplanescenery.blogspot.com/
Plugin SDK: http://www.xsquawkbox.net/xpsdk/
X-Plane Wiki: http://wiki.x-plane.com/
Scenery mailing list: 

Developer mailing list: