Setting up Triangulation_3 datastructure with no neighboring information

classic Classic list List threaded Threaded
32 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Setting up Triangulation_3 datastructure with no neighboring information

Daniel Weber
Hi at all!

I'm using the Triangulation_3 data structure for simulating deformable models. The advantage of that data structure is the simple access for information about neighbors.

I constructed different models, in my case simple bars, by inserting equidistant points in a Delaunaytriangulation. Using the I/O functionality of the data structures i can load and save these Triangulations.

Now i want to simulate other models. I've got the tetrahedral mesh as list of points and tetrahedra referring to the points. I've already spent a long time for an incremental construction of the tetrahedral mesh. But i failed, because of the very complex neighbor information especially of infinite tetrahedrons.

Is there any existing algorithm for that kind of problem? Or can anybody give me a hint how to construct the tetrahedral mesh properly?

Best regards,
Daniel Weber
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Setting up Triangulation_3 datastructure with no neighboring information

Nico Kruithof
Hi Daniel,

I did the same for the skin surface package, where I have the vertices
and tetrahedra of the triangulation and want to reconstruct the neighbor
information. The class is not documented and there is no guarantee that
it works for your cases as well.
You could have a look at that. It's in the file
CGAL/Triangulation_incremental_builder_3.h

You give the triangulation in the constructor, then you start building
the triangulation with "begin_triangulation(int dim)". I don't remember
whether dim<3 works as I don't use it.
You build the triangulation with the functions:
  Vertex_handle add_vertex();

  Cell_handle add_cell(Vertex_handle vh0, Vertex_handle vh1,
                       Vertex_handle vh2, Vertex_handle vh3);

Finally, you build the triangulation with
  void end_triangulation()
which also creates the infinite cells and might do some validity
checking.

Let me know whether you find it usefull and whether it could be
improved.

Bests,
Nico

On Tue, 2008-06-03 at 16:13 +0200, [hidden email] wrote:

> Hi at all!
>
> I'm using the Triangulation_3 data structure for simulating deformable models. The advantage of that data structure is the simple access for information about neighbors.
>
> I constructed different models, in my case simple bars, by inserting equidistant points in a Delaunaytriangulation. Using the I/O functionality of the data structures i can load and save these Triangulations.
>
> Now i want to simulate other models. I've got the tetrahedral mesh as list of points and tetrahedra referring to the points. I've already spent a long time for an incremental construction of the tetrahedral mesh. But i failed, because of the very complex neighbor information especially of infinite tetrahedrons.
>
> Is there any existing algorithm for that kind of problem? Or can anybody give me a hint how to construct the tetrahedral mesh properly?
>
> Best regards,
> Daniel Weber

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Setting up Triangulation_3 datastructure with no neighboring information

Daniel Weber
Hi Nico,

thats exactly what i needed! It works fine, thanks a lot!

If i encounter any problems, i will let you know!
Daniel

-------- Original-Nachricht --------
> Datum: Tue, 03 Jun 2008 16:27:08 +0200
> Von: Nico Kruithof <[hidden email]>
> An: [hidden email]
> Betreff: Re: [cgal-discuss] Setting up Triangulation_3 datastructure with no neighboring information

> Hi Daniel,
>
> I did the same for the skin surface package, where I have the vertices
> and tetrahedra of the triangulation and want to reconstruct the neighbor
> information. The class is not documented and there is no guarantee that
> it works for your cases as well.
> You could have a look at that. It's in the file
> CGAL/Triangulation_incremental_builder_3.h
>
> You give the triangulation in the constructor, then you start building
> the triangulation with "begin_triangulation(int dim)". I don't remember
> whether dim<3 works as I don't use it.
> You build the triangulation with the functions:
>   Vertex_handle add_vertex();
>
>   Cell_handle add_cell(Vertex_handle vh0, Vertex_handle vh1,
>                        Vertex_handle vh2, Vertex_handle vh3);
>
> Finally, you build the triangulation with
>   void end_triangulation()
> which also creates the infinite cells and might do some validity
> checking.
>
> Let me know whether you find it usefull and whether it could be
> improved.
>
> Bests,
> Nico
>
> On Tue, 2008-06-03 at 16:13 +0200, [hidden email] wrote:
> > Hi at all!
> >
> > I'm using the Triangulation_3 data structure for simulating deformable
> models. The advantage of that data structure is the simple access for
> information about neighbors.
> >
> > I constructed different models, in my case simple bars, by inserting
> equidistant points in a Delaunaytriangulation. Using the I/O functionality of
> the data structures i can load and save these Triangulations.
> >
> > Now i want to simulate other models. I've got the tetrahedral mesh as
> list of points and tetrahedra referring to the points. I've already spent a
> long time for an incremental construction of the tetrahedral mesh. But i
> failed, because of the very complex neighbor information especially of
> infinite tetrahedrons.
> >
> > Is there any existing algorithm for that kind of problem? Or can anybody
> give me a hint how to construct the tetrahedral mesh properly?
> >
> > Best regards,
> > Daniel Weber
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss

--
Ist Ihr Browser Vista-kompatibel? Jetzt die neuesten
Browser-Versionen downloaden: http://www.gmx.net/de/go/browser
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

What't the most efficient configuration for Bool Op of Nef_3

Max-151
Hello,

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?

More questions:

- If I need to get the intersection of a Plane_3 and a Nef_3,
should I use exact kernels? I can accept float errors of the
coordinates of the vertices, as long as I could get the 'correct'
polygon.

- To improve the computational efficiency, could I combine different
kernels in one program? e.g, use exact kernels to get the correct result
of bool operations, then use different, simpler, kernels for other operations
and for storage? What rules should I keep in mind when doing such things?

Thanks & B/Rgds.
Max



--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: What't the most efficient configuration for

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

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?

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?

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
Reply | Threaded
Open this post in threaded view
|

3D surface Mesh Generation

Hui Ding-3
Hi all,
 
I have this file of 3D points whose data are from an image depth, which means those 3D points define an object 3D non-closed. I want to mesh this object, is it possible that i can use the make_surface_mesh to do that? and how? for example, how to define the sphere_3, the centre, etc?
Can anybody give an idea? Thanx!!
 
Hui


Invite your mail contacts to join your friends list with Windows Live Spaces. It's easy! Try it!
Reply | Threaded
Open this post in threaded view
|

Re: 3D surface Mesh Generation

Laurent Rineau-3
On Monday 09 June 2008 18:07:18 Hui Ding wrote:
> Hi all,
>
> I have this file of 3D points whose data are from an image depth, which
> means those 3D points define an object 3D non-closed. I want to mesh this
> object, is it possible that i can use the make_surface_mesh to do that? and
> how? for example, how to define the sphere_3, the centre, etc? Can anybody
> give an idea? Thanx!!

Here is an answer I made in another thread of this list, last year ("3D
surface meshing", 2007/06/08):

« You seem to have a set of points, as input. Surface_mesher in CGAL-3.3 is a
package to mesh a implicit function. What you need is a surface
reconstruction algorithm (from a set of points). You cannot use
Surface_mesher.

However, there exists some algorithm to compute an implicit function, from a
set of points, whose zero level represents a smooth surface interpoling the
points. If you have such a function, then you can use the Surface_mesher
package. »

As far as I know, there are not any code in current CGAL-3.3.1 for such a
task.

--
Laurent Rineau
INRIA - Sophia Antipolis
BP 93, 2004 Route des Lucioles
06902 Sophia Antipolis Cedex FRANCE
Tel: +33 4 92 38 78 62 (Fax: +33.4.97.15.53.95)
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: 3D surface Mesh Generation

Santosh Tiwari
If you want mesh re-construction from point cloud. You have following
options.

1. If you want to use CGAL, you may create an alpha complex of the shape
and output all the surface facets. This method works but is not very
reliable and may not always give you the mesh you want.

2. If you know the approximate direction of normals at every vertex, use
something like poisson surface reconstruction. It is a powerful and
reliable method.

3. If you do not have the normals, you can use the program provided at the
following link.
http://www.den.rcast.u-tokyo.ac.jp/~yu-ohtake/software/index.html
This method also is not very reliable. It works on most standard models
but for complex data sets, it does not do a good job.






> On Monday 09 June 2008 18:07:18 Hui Ding wrote:
>> Hi all,
>>
>> I have this file of 3D points whose data are from an image depth, which
>> means those 3D points define an object 3D non-closed. I want to mesh
>> this
>> object, is it possible that i can use the make_surface_mesh to do that?
>> and
>> how? for example, how to define the sphere_3, the centre, etc? Can
>> anybody
>> give an idea? Thanx!!
>
> Here is an answer I made in another thread of this list, last year ("3D
> surface meshing", 2007/06/08):
>
> « You seem to have a set of points, as input. Surface_mesher in CGAL-3.3
> is a
> package to mesh a implicit function. What you need is a surface
> reconstruction algorithm (from a set of points). You cannot use
> Surface_mesher.
>
> However, there exists some algorithm to compute an implicit function, from
> a
> set of points, whose zero level represents a smooth surface interpoling
> the
> points. If you have such a function, then you can use the Surface_mesher
> package. »
>
> As far as I know, there are not any code in current CGAL-3.3.1 for such a
> task.
>
> --
> Laurent Rineau
> INRIA - Sophia Antipolis
> BP 93, 2004 Route des Lucioles
> 06902 Sophia Antipolis Cedex FRANCE
> Tel: +33 4 92 38 78 62 (Fax: +33.4.97.15.53.95)
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>


--
Santosh Tiwari
Fluor Daniel EIB 326
Clemson University, Clemson, SC 29634
http://www.clemson.edu/~stiwari/
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Is there a data structure for non-manifold 3D

calvin_cw
In reply to this post by Hui Ding-3



Hi all,
 
    I was searching thru the various data structure for 3D surfaces and the only one there is is the polyhedron class. However, within that class the connectivity of the nodes and faces are maintained properly, giving a 3D surface manifold (with or without boundaries).
 
   However, what if I have a dirty mesh which I obtained from somewhere which I want to use CGAL to perform cleaning up operations, but I will not be able to load it into the polyhedron class. By dirty mesh, I meant that it is possible for an edge to be adjacent to 3 or more faces.
 
  
 
thanks all.
Calvin 


Enrich your blog with Windows Live Writer. Windows Live Writer
Reply | Threaded
Open this post in threaded view
|

Re: Is there a data structure for non-manifold 3D

Laurent Rineau-3
Please stop reply to a message when you want to open a NEW discussion!!

On Tuesday 10 June 2008 03:35:18 Calvin Lim wrote:

> Hi all,
>
>     I was searching thru the various data structure for 3D surfaces and the
> only one there is is the polyhedron class. However, within that class the
> connectivity of the nodes and faces are maintained properly, giving a 3D
> surface manifold (with or without boundaries).
>
>    However, what if I have a dirty mesh which I obtained from somewhere
> which I want to use CGAL to perform cleaning up operations, but I will not
> be able to load it into the polyhedron class. By dirty mesh, I meant that
> it is possible for an edge to be adjacent to 3 or more faces.
>
>
>
> thanks all.
> Calvin
> _________________________________________________________________
> Easily edit your photos like a pro with Photo Gallery.
> http://get.live.com/photogallery/overview--
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss



--
Laurent Rineau
INRIA - Sophia Antipolis
BP 93, 2004 Route des Lucioles
06902 Sophia Antipolis Cedex FRANCE
Tel: +33 4 92 38 78 62 (Fax: +33.4.97.15.53.95)
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Is there a data structure for non-manifold 3D

Marco Attene
In reply to this post by calvin_cw
I suggest you to try a free software called ReMESH
(http://remesh.sourceforge.net). If you load your mesh into this
software and re-save it, the resulting file represents a surface which
is exactly coincident with your input, but it is combinatorially
manifold, so you can load it into a CGAL polyhedron. Also, if you want
to try, ReMESH proposes you to fix the geometry too (by removing
degenerate and skinny triangles), but this might slightly modify the
surface.
BTW, you may save to several formats, just specify the correct extension.
Hope it helps.

marco


Calvin Lim ha scritto:

>
>
>
> Hi all,
>
> I was searching thru the various data structure for 3D surfaces and
> the only one there is is the polyhedron class. However, within that
> class the connectivity of the nodes and faces are maintained properly,
> giving a 3D surface manifold (with or without boundaries).
>
> However, what if I have a dirty mesh which I obtained from somewhere
> which I want to use CGAL to perform cleaning up operations, but I will
> not be able to load it into the polyhedron class. By dirty mesh, I
> meant that it is possible for an edge to be adjacent to 3 or more faces.
>
>
>
> thanks all.
> Calvin
>
> ------------------------------------------------------------------------
> Enrich your blog with Windows Live Writer. Windows Live Writer
> <http://get.live.com/writer/overview>


--
--
----------------------------------------------------------

Marco Attene
Istituto di Matematica Applicata e Tecnologie Informatiche
Consiglio Nazionale delle Ricerche
Via de Marini 6 - 16149 - Genova - ITALY

Tel. +39(0)106475691
Fax. +39(0)106475660

----------------------------------------------------------

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Re: What't the most efficient configuration for

Max-151
In reply to this post by Peter Hachenberger
>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?

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

Thank you so much for you help, 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
>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Re: What't the most efficient configuration for

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

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: What's the most efficient configuration for nef_3

Max-151
>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
>--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

Snap1.png (69K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

A couple of questions on Nef_x

Max-151
In reply to this post by Peter Hachenberger
Hi,

I'm curious on these questions:

- is there a nef_1 representation of a nef in 1 dimension?
  (yes, it's just a combinition of any open or close ranges. What I mean is
  a universal representation as nef_3)
- is there a function to elevate the number of dimensions to higher dimension,
  e.g., convert a nef_2 into a nef_3?
- is there a convenient way to perform some well-know geometric operation, such as
  glide, extrude, etc., with an existing nef_X?
- is there a function to glide a nef_3 to get the swept nef_3?
- is there a machanism to shift the kernel types of one nef_3 (and any other
  CGAL data structure) at runtime?
- is there a function to incrementally build a (not necessarily 2-manifold) nef_3?

Thanks for you time.
B/Rgds
Max



--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

A problem found by accident

Max-151
In reply to this post by Peter Hachenberger
Hi,

I accidently found the following phenomenom:

I was feeding an off model (as attached) to a nef_3,
(my intention was to use a nef model)
I found the program swallows the memory continuously
without any error message.

Should this be considered normal?

B/Rgds
Max



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


--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Is there a data structure for non-manifold 3D

Max-151
In reply to this post by Marco Attene
hi Calvin,

CGAL::Nef_polyhedron_3 is capable of repesenting 2-manifold data structure

B/Rgds
Max

>>
>> Hi all,
>>
>> I was searching thru the various data structure for 3D surfaces and
>> the only one there is is the polyhedron class. However, within that
>> class the connectivity of the nodes and faces are maintained properly,
>> giving a 3D surface manifold (with or without boundaries).
>>
>> However, what if I have a dirty mesh which I obtained from somewhere
>> which I want to use CGAL to perform cleaning up operations, but I will
>> not be able to load it into the polyhedron class. By dirty mesh, I
>> meant that it is possible for an edge to be adjacent to 3 or more faces.
>>
>>
>>
>> thanks all.
>> Calvin
>>
>> ------------------------------------------------------------------------
>> Enrich your blog with Windows Live Writer. Windows Live Writer
>> <http://get.live.com/writer/overview>
>
>
>--
>--
>----------------------------------------------------------
>
>Marco Attene
>Istituto di Matematica Applicata e Tecnologie Informatiche
>Consiglio Nazionale delle Ricerche
>Via de Marini 6 - 16149 - Genova - ITALY
>
>Tel. +39(0)106475691
>Fax. +39(0)106475660
>
>----------------------------------------------------------
>
>--
>You are currently subscribed to cgal-discuss.
>To unsubscribe or access the archives, go to
>https://lists-sop.inria.fr/wws/info/cgal-discuss
>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: What's the most efficient configuration for

Peter Hachenberger
In reply to this post by Max-151
> >> >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.

That would be good. I'm curious about 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)

What is the question of this paragraph? Are you wondering that the nef
files are the same although you use different kernels? That's intended.
I spent lots of time to write input and output functions that convert
and normalize coordinates. Actually I have code that even sorts the
output such that it is always the same, but I only use that for testing
purpose.

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

I got that fault in the first place. My comments where on the corrected
version. Do you already have an impression of how much the indexed items
help you? Is Nef still a bad bottleneck? How much of a speed up do you
need?

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
Reply | Threaded
Open this post in threaded view
|

Re: A couple of questions on Nef_x

Peter Hachenberger
In reply to this post by Max-151

> I'm curious on these questions:
>
> - is there a nef_1 representation of a nef in 1 dimension?
>   (yes, it's just a combinition of any open or close ranges. What I mean is
>   a universal representation as nef_3)

We don't have that in CGAL and it does not seem interesting to have.

> - is there a function to elevate the number of dimensions to higher dimension,
>   e.g., convert a nef_2 into a nef_3?

Not yet.

> - is there a convenient way to perform some well-know geometric operation, such as
>   glide, extrude, etc., with an existing nef_X?

Sorry to say, but I don't know glide and extrude.

> - is there a function to glide a nef_3 to get the swept nef_3?

if glide means to compute the area swept by a nef_3 moved along a
polygonal line, then you can do that with the Minkowski_sum_3 package
that hopefully will be in the next CGAL release.

> - is there a machanism to shift the kernel types of one nef_3 (and any other
>   CGAL data structure) at runtime?

No.

> - is there a function to incrementally build a (not necessarily 2-manifold) nef_3?

No, I neither have an idea how it might work, nor the manpower to do
realize that at the moment.

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
Reply | Threaded
Open this post in threaded view
|

Re: What's the most efficient configuration for nef_3

Max-151
In reply to this post by Peter Hachenberger
>> >

>> >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.
>
>That would be good. I'm curious about the problem.
I attach the test program for reproducing the problem.
To make the code as small in size as possible, I've commented out
the irrelevant code. The sample data file is also attached.
I hope I'm not making stupid mistake. :-)

>
>> 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)
>
>What is the question of this paragraph? Are you wondering that the nef
>files are the same although you use different kernels? That's intended.

I already know the content of .nef files written with different kernels
are different. and I also guess there's difference in contents between 2
.nef files written with different items types. But I cannot detect any
significant diff's.

>I spent lots of time to write input and output functions that convert
>and normalize coordinates.
Yes, writting the i/o module of nef_3 is a hard work.

>Actually I have code that even sorts the
>output such that it is always the same, but I only use that for testing
>purpose.

That's a good news. And I think it's a good idea to make it open.
It's a good idea to keep a uniform format of .nef files for different
kernel types and items types, as long as it's possible practically
and theoritically.
 

>
>>
>> Sorry, it's a typo, it should be:
>>     Plane_3 p;
>> Nef_3 N;
>>     Nef_3 result = N.intersection(p).intersection(p.opposite());
>
>I got that fault in the first place. My comments where on the corrected
>version. Do you already have an impression of how much the indexed items
>help you? Is Nef still a bad bottleneck? How much of a speed up do you
>need?
You mean this idiom is ok for my need?

I have not got an impression of the indexed items yet, because
the program just refused to work. I hope, after I get the indexed items
working, it will not be the bottleneck. :-)

>
>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
>--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

tmp.cpp (4K) Download Attachment
1.off (324 bytes) Download Attachment
12