CGAL users discussion list

["Max" <>]

>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. 

Another question, how can I determine the resolved type of 
Exact_constructions_exact_predicates_kernel at rune time or compile time?

>> 
>> 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>

Thank you for your clarification. I can and could use GmpX as Kernel after
and before I re-compiled the Gmp lib's.
In my CGALHOME/make folder, there's only a README file.

>
>> >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.

The context of the error is as the attached sreenshot.
If it's not enough, I'll prepare a minimum program that can reproduce the 
problem. 
One thing to note: I'm reading a nef_3 from a .nef file. 
And I've refreshed the .nef file from an identical .off model (very simple)
using the nef_3 type with the indexed items type. (I've not found any 
significant 
difference in format from the two .nef files written from two identical nef_3
with different items types)

>
>> >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());

Sorry, it's a typo, it should be:
    Plane_3 p;
        Nef_3 N;
    Nef_3 result = N.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.

I'm interested in your updated opinion on my correction above.

Thank you again, Peter.
B/Rgds
Max

>
>Peter
>
>-- 
>You are currently subscribed to cgal-discuss.
>To unsubscribe or access the archives, go to
>https://lists-sop.inria.fr/wws/info/cgal-discuss
>

Attachment: Snap1.png
Description: Binary data