CGAL users discussion list

[Peter Hachenberger <>]

On Tue, 2008-06-10 at 17:08 +0800, Max wrote:
> >Hi Max,
> >
> >> In one of my program, I use boolean operation of Nef_3 heavily, 
> >> and I found the efficiency of it became the bottleneck of the 
> >> program, because I need to compute the result of boolean for thousands 
> >> of times.
> >> 
> >> Now I want to know, if I don't need the result to be *exact*, which
> >> configuration(Kernel, Item, etc.) would be the most efficient?
> >
> >The best kernel usually is the
> >Exact_constructions_exact_predicates_kernel. I say usually, because this
> >kernel resolves into different kernels dependent upon your installation.
> >So, you should have gmp installed, otherwise this kernel will not be
> >efficient. 
> 
> I'm a little bit confused on 'whether I have installed GMP'. 
> I have selected to install the pre-compiled lib's during the installation 
> of CGAL.
> As a result, there's an auxiliary\gmp folder under the CGAL root folder. 
> There're
> header files and lib files of GMP and MPFR for VC71 and VC80 in this folder.
> 
> I guess this is not enough to considered as "GMP installed", then I
> downloaded GMP 4.2.1 and MPFR 2.2.0 and compiled with VC9.
> After a lot of efforts, I finally got to link by program with these 
> new libs. But I could hardly detect any increase of efficiency.
> 
> This lead me to the understanding - my previous condition could be 
> considered as 
> "GMP installed". Right?

Just try to use Gmpz or Gmpq as a number type. If you can compile, you
have Gmp. You can also look up in CGALHOME/make/makefile<yoursystem>

> >Remember to use the SNC_indexed_items together with every kernel you
> >use. That makes it faster. So
> >
> >typedef Nef_polyhedron_3<Kernel, SNC_indexed_items> Nef_3;
> >
> >I guess you are already doing that, aren't you? 
> 
> If your have told me the difference in efficiency of the default items type
> and the indexed items, I should have been using the indexed one. :-)
> 
> But the fact is 'no'.   :-(
> 
> The reason should be either I haven't been told of this or I have tried 
> with it but have met some difficulties.
> 
> Anyway, I shifted, back or not, :-), to the indexed items type. But I found 
> the program behaves differently - it can even not run correctly, error 
> arises 
> before it ends.
> 
> I will debug the program and report more details.

The system is supposed to behave the same way with the indexed items.
The only difference should be in input and output of coordinates. If you
have bugs, then send them to me. I will do the debugging. It's important
for me to make the indexed items as reliable as possible.

> >Explain your scenario. Then I might can help you to improve. Do you
> >always intersect a polyhedron with a plane? Do the polyhedra have
> >special properties? Are they small or large? Are they convex? Are they
> >two-manifold? What do you do with the resulting polygon?
> 
> Here are some aspects of my scenario:
> - I'm dealing with float type coordinates of vertices of the polyhedrons
> - I often intersect a nef_3 with a plane with such idiom:
>    Plane_3 p;
>    Nef_3 N = Nef_3(p).intersection(p).intersection(p.opposite());
> - the original polyhedron I'm dealing with is 2-manifold.
> - I convert back the resulting nef_3 of intersection into 
> polyhedron and calculate the geometric properties of it.
> (I now this is one unnecessary step which was consuming my precious CPU 
> cycles,
> but this should not be the bottole neck of the whole program. I've put this 
> in my 
> TODO list to handle nef_3 directly)
> - I don't need the operation to be _strictly_ exact, I could 
> accept some level of tolerance of real type computation
> - I want the configuration to be as efficient as possible.

I hope the indexed items speed up your program significantly. What I can
also do is, that I allow you to intersect with the plane and not twice
with halfspaces. That should give you a factor of two.

Peter