(no subject)

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

(no subject)

Kwok Jasper
Excuse me, may I ask something about 3D Delaunay triangulation in CGAL?

I have tried to use the following types.

typedef CGAL::Cartesian<double> K1;
typedef CGAL::Delaunay_triangulation_3<K1> Triangulation;
typedef Triangulation::Point Point_tr;


when I insert about 300000 points into the triangulation,
I got a stack overflow problem.

May I ask what may be the possible reason for the stack overflow to occur?



Reply | Threaded
Open this post in threaded view
|

Re:

Laurent Rineau (GeometryFactory)
On Tuesday 20 January 2009 11:06:17 Kwok Jasper wrote:

> Excuse me, may I ask something about 3D Delaunay triangulation in CGAL?
>
> I have tried to use the following types.
>
> typedef CGAL::Cartesian<double> K1;
> typedef CGAL::Delaunay_triangulation_3<K1> Triangulation;
> typedef Triangulation::Point Point_tr;
>
>
> when I insert about 300000 points into the triangulation,
> I got a stack overflow problem.
>
> May I ask what may be the possible reason for the stack overflow to occur?

That could be a recursive function in CGAL code. In CGAL-3.3.1, some member
functions of Triangulation_3 were recursive, and that could lead to stack  
overflow in some special cases. That has been fixed in CGAL-3.4. What version
are you using?

--
Laurent Rineau, PhD
Engineer at GeometryFactory
http://www.geometryfactory.com/

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

Kwok Jasper
Thank you for your reply.
I am using version 3.3.1

May I ask instead of installing 3.4,
is there still any alternative way for inserting the huge number of points into the triangulation?

Thank you

> From: [hidden email]
> To: [hidden email]
> Date: Tue, 20 Jan 2009 11:12:19 +0100
> Subject: Re: [cgal-discuss]
>
> On Tuesday 20 January 2009 11:06:17 Kwok Jasper wrote:
> > Excuse me, may I ask something about 3D Delaunay triangulation in CGAL?
> >
> > I have tried to use the following types.
> >
> > typedef CGAL::Cartesian<double> K1;
> > typedef CGAL::Delaunay_triangulation_3<K1> Triangulation;
> > typedef Triangulation::Point Point_tr;
> >
> >
> > when I insert about 300000 points into the triangulation,
> > I got a stack overflow problem.
> >
> > May I ask what may be the possible reason for the stack overflow to occur?
>
> That could be a recursive function in CGAL code. In CGAL-3.3.1, some member
> functions of Triangulation_3 were recursive, and that could lead to stack
> overflow in some special cases. That has been fixed in CGAL-3.4. What version
> are you using?
>
> --
> Laurent Rineau, PhD
> Engineer at GeometryFactory
> http://www.geometryfactory.com/
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss


利用 Windows Live™ Photos 輕?分享相片。 簡易上載及分享照片
Reply | Threaded
Open this post in threaded view
|

Re:

andreas.fabri
In reply to this post by Kwok Jasper
Kwok Jasper wrote:

> Excuse me, may I ask something about 3D Delaunay triangulation in CGAL?
>
> I have tried to use the following types.
>
> typedef CGAL::Cartesian<double> K1;
> typedef CGAL::Delaunay_triangulation_3<K1> Triangulation;
> typedef Triangulation::Point Point_tr;
>
>
> when I insert about 300000 points into the triangulation,
> I got a stack overflow problem.
>
> May I ask what may be the possible reason for the stack overflow to occur?
>
>
> ------------------------------------------------------------------------

With Cartesian<double> anything can go on.  In order to avoid
floiting point arithmetic related problems you should use the

typedef CGAL::Exact_predicates_inexact_constructions_kernel K1;

andreas





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

Kwok Jasper
Thanks

I have used
typedef CGAL::Exact_predicates_inexact_constructions_kernel K1

before.

However, it takes nearly 1 hour to insert about 300000 points.
Therefore, I have switched from

Exact_predicates_inexact_constructions_kernel to Cartesian.

And except by using exact predicate,
may I ask if it still exist some other ways to prevent the stack overflow in version 3.3.1 of CGAL?

Thank you

> Date: Tue, 20 Jan 2009 11:16:04 +0100
> From: [hidden email]
> To: [hidden email]
> Subject: Re: [cgal-discuss]
>
> Kwok Jasper wrote:
> > Excuse me, may I ask something about 3D Delaunay triangulation in CGAL?
> >
> > I have tried to use the following types.
> >
> > typedef CGAL::Cartesian<double> K1;
> > typedef CGAL::Delaunay_triangulation_3<K1> Triangulation;
> > typedef Triangulation: :Point Point_tr;
> >
> >
> > when I insert about 300000 points into the triangulation,
> > I got a stack overflow problem.
> >
> > May I ask what may be the possible reason for the stack overflow to occur?
> >
> >
> > ------------------------------------------------------------------------
>
> With Cartesian<double> anything can go on. In order to avoid
> floiting point arithmetic related problems you should use the
>
> typedef CGAL::Exact_predicates_inexact_constructions_kernel K1;
>
> andreas
>
>
>
>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss


想同MSN Buddy傾計了解佢多d? 參觀MSN Buddy部屋啦!
Reply | Threaded
Open this post in threaded view
|

Re:

Sylvain Pion
Administrator
Kwok Jasper wrote:

> Thanks
>
> I have used
> typedef CGAL::Exact_predicates_inexact_constructions_kernel K1
>
> before.
>
> However, it takes nearly 1 hour to insert about 300000 points.
> Therefore, I have switched from
>
> Exact_predicates_inexact_constructions_kernel to Cartesian.
>
> And except by using exact predicate,
> may I ask if it still exist some other ways to prevent the stack
> overflow in version 3.3.1 of CGAL?
I don't think so.

What is special about your data set that it triggers this stack overflow?
Is it a lot of points on a sphere, or something like that?
I would be glad to get access to it to see what going wrong and if we can
do something about it.


> Thank you
>  > Date: Tue, 20 Jan 2009 11:16:04 +0100
>  > From: [hidden email]
>  > To: [hidden email]
>  > Subject: Re: [cgal-discuss]
>  >
>  > Kwok Jasper wrote:
>  > > Excuse me, may I ask something about 3D Delaunay triangulation in CGAL?
>  > >
>  > > I have tried to use the following types.
>  > >
>  > > typedef CGAL::Cartesian<double> K1;
>  > > typedef CGAL::Delaunay_triangulation_3<K1> Triangulation;
>  > > typedef Triangulation: :Point Point_tr;
>  > >
>  > >
>  > > when I insert about 300000 points into the triangulation,
>  > > I got a stack overflow problem.
>  > >
>  > > May I ask what may be the possible reason for the stack overflow to
> occur?
>  > >
>  > >
>  > >
> ------------------------------------------------------------------------
>  >
>  > With Cartesian<double> anything can go on. In order to avoid
>  > floiting point arithmetic related problems you should use the
>  >
>  > typedef CGAL::Exact_predicates_inexact_constructions_kernel K1;
>  >
>  > andreas
>  >
>  >
>  >
>  >
>  >
>  > --
>  > You are currently subscribed to cgal-discuss.
>  > To unsubscribe or access the archives, go to
>  > https://lists-sop.inria.fr/wws/info/cgal-discuss
>
> ------------------------------------------------------------------------
> 想同MSN Buddy傾計了解佢多d? 參觀MSN Buddy部屋啦!
> <http://buddy.hk.msn.com/>

--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/


smime.p7s (5K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re:

Camille Wormser-2
In reply to this post by Kwok Jasper
typedef CGAL::Exact_predicates_inexact_constructions_kernel K1

before.

However, it takes nearly 1 hour to insert about 300000 points.

Considering your (extremely slow) timing, I imagine that your points are not at all in general position, but in a very degenerate one. Could it be, for example, that all your points lie on a sphere? That would explain the slow computation.

Furthermore, the stack overflow in CGAL 3.3 would then come from (you or CGAL) calling incident_vertices() on the infinite vertex, which has too many neighbors (all the points).

This issue of stack overflow has been solved in CGAL-3.4, as Laurent said.

However, your slowness issue has nothing to do with this. You should tell us more about your input data.
-- 
Camille

Reply | Threaded
Open this post in threaded view
|

RE:

Kwok Jasper
In reply to this post by Sylvain Pion
Thank you very much.

The points that I input is from a bunny model

The input points are from here
http://www.cse.ust.hk/~jamesjjx/bunny_final.pts

May I ask what may I do with the stack overflow ?
Thank you very much for your help.


> Date: Tue, 20 Jan 2009 11:30:21 +0100
> From: [hidden email]
> To: [hidden email]
> Subject: Re: [cgal-discuss]
>
> Kwok Jasper wrote:
> > Thanks
> >
> > I have used
> > typedef CGAL::Exact_predicates_inexact_constructions_kernel K1
> >
> > before.
> >
> > However, it takes nearly 1 hour to insert about 300000 points.
> > Therefore, I have switched from
> >
> > Exact_predicates_inexact_constructions_kernel to Cartesian.
> >
> > And except by using exact predicate,
> > may I ask if it still exist some other ways to prevent the stack
> > overflow in version 3.3.1 of CGAL?
>
> I don't think so.
>
> What is special about your data set that it triggers this stack overflow?
> Is it a lot of points on a sphere, or something like that?
> I would be glad to get access to it to see what going wrong and if we can
> do something about it.
>
>
> > Thank you
> > > Date: Tue, 20 Jan 2009 11:16:04 +0100
> > > From: [hidden email]
> > > To: [hidden email]
> > > Subject: Re: [cgal-discuss]
> > >
> > > Kwok Jasper wrote:
> > > > Excuse me, may I ask something about 3D Delaunay triangulation in CGAL?
> > > >
> > > > I have tried to use the following types.
> > > >
> > > > typedef CGAL::Cartesian<double> K1;
> > > > typedef CGAL::Delaunay_triangulation_3<K1> Triangulation;
> > > > typedef Triangulation: :Point Point_tr;
> > > >
> > > >
> > > > when I insert about 300000 points into the triangulation,
> > > > I got a stack overflow problem.
> > > >
> > > > May I ask what may be the possible reason for the stack overflow to
> > occur?
> > > >
> > > >
> > > >
> > ------------------------------------------------------------------------
> > >
> > > With Cartesian<double> anything can go on. In order to avoid
> > > floiting point arithmetic related problems you should use the
> > >
> > > typedef CGAL::Exact_predicates_inexact_constructions_kernel K1;
> > >
> > > andreas
> > >
> > >
> > >
> > >
> > >
> > > --
> > > You are currently subscribed to cgal-discuss.
> > > To unsubscribe or access the archives, go to
> > > https://lists-sop.inria.fr/wws/info/cgal-discuss
> >
> > ------------------------------------------------------------------------
> > 想同MSN Buddy傾計了解佢多d? 參觀MSN Buddy部屋啦!
> > <http://buddy.hk.msn.com/>
>
>
> --
> Sylvain Pion
> INRIA Sophia-Antipolis
> Geometrica Project-Team
> CGAL, http://cgal.org/
>


收發郵件以外 - 了解更多Windows Live™卓越功能 收發郵件以外更多功能
Reply | Threaded
Open this post in threaded view
|

Re:

Camille Wormser-2


I tested your dataset with CGAL 3.4 on a 1.8 GHz Intel computer, it returns
"triangulation of 362272 points computed in 11.85 s". 

I tested it with CGAL 3.3 on the same computer, it returns
"triangulation of 362272 points computed in 12.21 s".

Did you forget to compile your code with optimizations turned on?

May I ask what may I do with the stack overflow ?

There is no point in repeating the same question over and over. We told you that the incident_XXX functions had been fixed for a stackoverflow problem in CGAL 3.4. If you do not want to update to 3.4, you can copy all incident_XXX functions (and related helper functions) from the 3.4 file to your file.

However, in the current case, the problem does not seem to come from CGAL. You should check your code and probably turn the optimizations on.
-- 
Camille

Reply | Threaded
Open this post in threaded view
|

RE:

Kwok Jasper
Thanks.

Thanks

I have tried again but still cannot return the triangulation with the short period of time.
May I ask if it is that it may be related to the memory that is left in the PC ?

Currently, I am using Window XP and I have about 4 GB left in the C drive.
May I ask if increasing the spaces in the C drive may be a possible way to increase the speed?

Thanks very much
 


From: [hidden email]
To: [hidden email]
Date: Wed, 21 Jan 2009 11:24:08 +0100
Subject: Re: [cgal-discuss]



I tested your dataset with CGAL 3.4 on a 1.8 GHz Intel computer, it returns
"triangulation of 362272 points computed in 11.85 s". 

I tested it with CGAL 3.3 on the same computer, it returns
"triangulation of 362272 points computed in 12.21 s".

Did you forget to compile your code with optimizations turned on?

May I ask what may I do with the stack overflow ?

There is no point in repeating the same question over and over. We told you that the incident_XXX functions had been fixed for a stackoverflow problem in CGAL 3.4. If you do not want to update to 3.4, you can copy all incident_XXX functions (and related helper functions) from the 3.4 file to your file.

However, in the current case, the problem does not seem to come from CGAL. You should check your code and probably turn the optimizations on.
-- 
Camille



利用 Windows Live™ Photos 輕?分享相片。 簡易上載及分享照片