CGAL users discussion list

[Efi Fogel <>]

On Wed, Oct 21, 2015 at 10:20 PM, Ronald Paloschi <> wrote:

Hi Everybody,

Well, as I imagined, it was easy to implement that way.

Now, I would like to optimize it on the Beziers case.

My definitions:

<code>

using Nt_traits = CGAL::CORE_algebraic_number_traits;

using Rational = Nt_traits::Rational;

using Algebraic = Nt_traits::Algebraic;

using Rat_kernel = CGAL::Cartesian<Rational>;

using Alg_kernel = CGAL::Cartesian<Algebraic>;

using Bezier_Traits =

         CGAL::Arr_Bezier_curve_traits_2<Rat_kernel, Alg_kernel, Nt_traits>;

</code>

My application limits the beziers to cubic Beziers, two points and two control points.

If I want to intersect two Bezier_Traits::Curve_2 objects:

* Convert them both to  Bezier_Traits::X_monotone_curve_2 using Make_x_monotone_2. (it can result in any number of X_monotone_curve_2 curves).

* Then I try to intersect, using Intersect_2.

Something like this:

<code>

Bezier_Traits bzTraits;

auto intersectToObject = bzTraits.intersect_2_object();

std::vector<CGAL::Object> results;

intersectToObject(curve1, curve2, std::back_inserter(results));

</code>

Now 'results' contains std::pair<Bezier_Traits::Point_2, unsigned int> objects.

With the first element of the pair (a Bezier_Traits::Point_2), I can approximate every point of intersection. In fact, I found myself calling the refine() method to get a better approximation.

It works like a charm! But two things are slow:

1) the intersectToObject call.

2) several calls to refine() to get a better approximation.

I think this sums up what I'm trying to do... maybe it is a little naive because I learned by your Efi,s instructions, the online docs and hacking the code.

The questions are:

- Is this reasonable at least?

Yrs, it is.
 

- How can I improve performance? (I have a test suite that I run against a proprietary implementation of ours that runs in 0.085s. Running it against OpenCasCade takes 0.033s. My CGAL implementation takes over 2s. to run. (Results of OpenCascade and CGAL after refining the solutions are quite the same for my application).

First, you need to realize that the CGAL implementation is robust. That is, you can apply all sorts of operations on the arrangement and things will work---not sometimes, but always! This comes with a penalty, that is an overhead. I'm not familiar with OpenCascade; it might be doing a wonderful job, but any library that  exhibits faster running times, might be doing it at the expense of robustness.

Secondly, you can try to expedite the running time. One thing you can try is using a geometry traits class different than an instance of the Arr_Bezier_traits_2, for example, an instance of the Arr_algebraic_segment_traits_2 class. You can try to simplify the Arr_Bezier_traits_2 traits class to support just the type of Bezier curves that you need, or develop your own traits class altogether...

Thanks a lot for your help!

---

From: <> on behalf of Ronald Paloschi <>
Sent: Tuesday, October 13, 2015 8:20 AM

To:
Subject: Re: [cgal-discuss] Intersection of geometries

 

Hi Efi,

Thanks for answering!

I've made some experiments and this approach of approximating circles and arcs with bezier curves seems to be the way to go (and not difficult to be done ATM).

The book on arrangements is a great Resource!

Well, on to coding! Thanks for your help!

Ronald

---

From: <> on behalf of Efi Fogel <>
Sent: Saturday, October 10, 2015 12:51 PM
To:
Subject: Re: [cgal-discuss] Intersection of geometries

 

Hi Ronald,

There is no immediate way to handle all three types at the same time.

You need to define an appropriate instance of the Arrangement_2

CGAL 4.6.3 - 2D Arrangements: CGAL::Arrangement_2< Traits ...

Types: typedef Arrangement_2 < Traits_2, Dcel > Self a private type used as an abbreviation of the Arrangement_2 type hereafter. typedef unspecified_type

Read more...

<Geom_traits, Dcel=...> class template.

There is no immediate geometry traits that handle all 3 types at the same.

You can use the Arr_algebraic_segment_traits_2 geometry traits class. Essentially, this traits class handles all algebraic curves. However, defining the input curves you are interested in may not be intuitive. Secondly, while Arr_algebraic_segment_traits_2 was designed and implemented to achieve maximum efficiency, a traits class that is dedicated to handle bounded degree algebraic curves like those you are interested in could be more efficient. You are welcome to implement such a traits class on your own. In addition to the online help, you will find our book, entitled CGAL Arrangements and Their Applications, a good source of information. If you are considering purchasing a commercial license, directly consulting GeometryFactory can be useful.

BW, if, for example, you are willing to approximate circles with cubic Bézier curves, you can use the Arr_Bezier_curve_traits_2 geometry traits, but again, this may be not intuitive or even desired.

Best,

Efi

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/

On Thu, Oct 8, 2015 at 3:25 PM, Ronald Paloschi <> wrote:

Hi,

In our company, we are experiencing around with CGAL, it is such an amazing library!

I need some advice that I think you fellows can give me.

First, context: We have a legacy CAD system with an in-house geometric library. We would like to start experiencing with cgal to replace this library.

Our model has 3 main types of geometries (Line segments, Arcs and Bezier curves).

It was really easy to move around and start using things.

Now I have a new challenge: Intersections. The Arrangements package seems the way to go, I'm still studying it.

My question: How can I setup an Arrangement that is able to manage those 3 types together (if possible)?

Thanks in advance!