cell.intersects() functionality in 0.9.7? (i.e. GTS dependencies)
Hi All,
I've implemented a rather nifty semilagrangian advection scheme in dolfin that requires rapid checking to see if a point intersects a cell (without necessarily firing up the full intersection operator). Pre 0.9.7 this was implemented as cell.intersects
Everything works fine in 0.9.6 with the new CGAL intersection operator replacing the GTS intersection operator (with about a 20% speedup). However, in 0.9.7 the code breaks because cell.intersects() has been removed as a GTS dependency (actually, looking at TriangleCell.
The question is... is there is any equivalent functionality in CGAL and is anyone interested in implementing it (either as cell.intersects(??) or some other interface). The functionality should be straightforward (and I'd be surprised if it didn't exist), given a *known cell* and a point, does the cell intersect the point. This would be useful for particle based methods as well.
On a related note...are there any plans for a parallel implementation of Function:
by release 1.0?
All assistance greatly appreciated
marc
Question information
 Language:
 English Edit question
 Status:
 Solved
 For:
 DOLFIN Edit question
 Assignee:
 No assignee Edit question
 Last query:
 20100219
 Last reply:
 20100830
Andre Massing (massing) said :  #1 
On Friday 19. February 2010 18.33.47 marc spiegelman wrote:
> New question #101686 on DOLFIN:
> https:/
>
> Hi All,
> I've implemented a rather nifty semilagrangian advection scheme in
> dolfin that requires rapid checking to see if a point intersects a
> cell
> (without necessarily firing up the full intersection operator). Pre
> 0.9.7
> this was implemented as cell.intersects
>
> Everything works fine in 0.9.6 with the new CGAL intersection
> operator
> replacing the GTS intersection operator (with about a 20% speedup).
Did you only use the intersection between meshentities and points or did
you
use also the new mesh intersection operator? Just curious, because the
former
code for intersection between points og e.g. triangles did not change.
> However, in 0.9.7 the code breaks because cell.intersects() has been
> removed as a GTS dependency (actually, looking at
> TriangleCell.
> GTS
> code but wasn't actually dependent on GTS)
Yep that's true, the intersection functions was removed and there is a new
PrimitiveInters
the intersection between rather arbitrary mesh entities (exact or only
using
doubling precision). The functions are exposed as do_intersect and
do_intersect_exact in the python interface. But you are right, a point 
meshentity intersection is not provided. I attached a patch against the
recent
0.9.7 release. Could you can apply to you sources and see whether it
works for
you?
>
> The question is... is there is any equivalent functionality in CGAL
and is
> anyone interested in implementing it (either as cell.intersects(??)
> or some other interface). The functionality should be straightforward
> (and I'd be surprised if it didn't exist), given a *known cell* and a
> point, does the cell intersect the point. This would be useful for
> particle based methods as well.
>
> On a related note...are there any plans for a parallel implementation
> of Function:
> release 1.0?
>
> All assistance greatly appreciated
Any feedback as well :)
> marc
>
Garth Wells (garthwells) said :  #2 
Andre Massing wrote:
> Question #101686 on DOLFIN changed:
> https:/
>
> Status: Open => Answered
>
> Andre Massing proposed the following answer:
> On Friday 19. February 2010 18.33.47 marc spiegelman wrote:
> > New question #101686 on DOLFIN:
> > https:/
> >
> > Hi All,
> > I've implemented a rather nifty semilagrangian advection scheme in
> > dolfin that requires rapid checking to see if a point intersects a
> > cell
> > (without necessarily firing up the full intersection operator). Pre
> > 0.9.7
> > this was implemented as cell.intersects
> >
> > Everything works fine in 0.9.6 with the new CGAL intersection
> > operator
> > replacing the GTS intersection operator (with about a 20% speedup).
>
> Did you only use the intersection between meshentities and points or did
> you
> use also the new mesh intersection operator? Just curious, because the
> former
> code for intersection between points og e.g. triangles did not change.
>
> > However, in 0.9.7 the code breaks because cell.intersects() has been
> > removed as a GTS dependency (actually, looking at
> > TriangleCell.
> > GTS
> > code but wasn't actually dependent on GTS)
>
> Yep that's true, the intersection functions was removed and there is a new
> PrimitiveInters
> the intersection between rather arbitrary mesh entities (exact or only
> using
> doubling precision). The functions are exposed as do_intersect and
> do_intersect_exact in the python interface. But you are right, a point 
> meshentity intersection is not provided. I attached a patch against the
> recent
> 0.9.7 release. Could you can apply to you sources and see whether it
> works for
> you?
>
Andre: Did you forget to attach it?
> >
> > The question is... is there is any equivalent functionality in CGAL
> and is
> > anyone interested in implementing it (either as cell.intersects(??)
> > or some other interface). The functionality should be straightforward
> > (and I'd be surprised if it didn't exist), given a *known cell* and a
> > point, does the cell intersect the point. This would be useful for
> > particle based methods as well.
> >
> > On a related note...are there any plans for a parallel implementation
> > of Function:
> > release 1.0?
I've just pushed a change for this, although it won't work for
offprocess points.
Garth
> >
> > All assistance greatly appreciated
>
> Any feedback as well :)
>
> > marc
> >
>
Andre Massing (massing) said :  #3 
Garth N. Wells wrote:
>
> Andre Massing wrote:
>> Question #101686 on DOLFIN changed:
>> https:/
>>
>> Status: Open => Answered
>>
>> Andre Massing proposed the following answer:
>> On Friday 19. February 2010 18.33.47 marc spiegelman wrote:
>> > New question #101686 on DOLFIN:
>> > https:/
>> >
>> > Hi All,
>> > I've implemented a rather nifty semilagrangian advection scheme in
>> > dolfin that requires rapid checking to see if a point intersects a
>> > cell
>> > (without necessarily firing up the full intersection operator). Pre
>> > 0.9.7
>> > this was implemented as cell.intersects
>> >
>> > Everything works fine in 0.9.6 with the new CGAL intersection
>> > operator
>> > replacing the GTS intersection operator (with about a 20% speedup).
>>
>> Did you only use the intersection between meshentities and points or did
>> you
>> use also the new mesh intersection operator? Just curious, because the
>> former
>> code for intersection between points og e.g. triangles did not change.
>>
>> > However, in 0.9.7 the code breaks because cell.intersects() has been
>> > removed as a GTS dependency (actually, looking at
>> > TriangleCell.
>> > GTS
>> > code but wasn't actually dependent on GTS)
>>
>> Yep that's true, the intersection functions was removed and there is a new
>> PrimitiveInters
>> the intersection between rather arbitrary mesh entities (exact or only
>> using
>> doubling precision). The functions are exposed as do_intersect and
>> do_intersect_exact in the python interface. But you are right, a point 
>> meshentity intersection is not provided. I attached a patch against the
>> recent
>> 0.9.7 release. Could you can apply to you sources and see whether it
>> works for
>> you?
>>
>
> Andre: Did you forget to attach it?
Hmm, I did not, at least in my sent box it also appeared with
attachment. Strange... resend it (CC to the DOLFINml).
>
>> >
>> > The question is... is there is any equivalent functionality in CGAL
>> and is
>> > anyone interested in implementing it (either as cell.intersects(??)
>> > or some other interface). The functionality should be straightforward
>> > (and I'd be surprised if it didn't exist), given a *known cell* and a
>> > point, does the cell intersect the point. This would be useful for
>> > particle based methods as well.
>> >
>> > On a related note...are there any plans for a parallel implementation
>> > of Function:
>> > release 1.0?
>
> I've just pushed a change for this, although it won't work for
> offprocess points.
>
> Garth
>
>> >
>> > All assistance greatly appreciated
>>
>> Any feedback as well :)
>>
>> > marc
>> >
>>
>
>
>
> _______
> Mailing list: https:/
> Post to : <email address hidden>
> Unsubscribe : https:/
> More help : https:/
Andre Massing (massing) said :  #4 
Attachments seems to be filtered out when replying via email. Manually copied here for convenience, patch also available on the ml.
=== modified file 'dolfin/
 dolfin/
+++ dolfin/
@@ 6,7 +6,7 @@
// Modified by André Massing, 2010
//
// First added: 20100209
// Last changed: 20100211
+// Last changed: 20100219
//
//Author: André Massing (am), <email address hidden>
//Company: Simula Research Laboratory, Fornebu, Norway
@@ 26,13 +26,22 @@
{
return PrimitiveInters
}

+//
+bool PrimitiveInters
+{
+ return PrimitiveInters
+}
+//
bool PrimitiveInters
{

return PrimitiveInters
}
//
+bool PrimitiveInters
+{
+ return PrimitiveInters
+}
+//
template <typename K, typename T, typename U >
bool PrimitiveInters
{
=== modified file 'dolfin/
 dolfin/
+++ dolfin/
@@ 6,7 +6,7 @@
// Modified by André Massing, 2010
//
// First added: 20100209
// Last changed: 20100210
+// Last changed: 20100219
//
//Author: André Massing (am), <email address hidden>
//Company: Simula Research Laboratory, Fornebu, Norway
@@ 19,6 +19,7 @@
namespace dolfin
{
class MeshEntity;
+ class Point;
/// This class implements an intersection detection, detecting whether two given (arbitrary) meshentities intersect.
class PrimitiveInters
@@ 28,10 +29,12 @@
///kernel which is faster but may suffer from floating point precision
//issues.
static bool do_intersect(const MeshEntity & entity_1, const MeshEntity & entity_2);
+ static bool do_intersect(const MeshEntity & entity_1, const Point & point);
///Computes whether two mesh entities intersect. Uses an exact geometry
///kernel which is slower but detects intersection always correctly.
static bool do_intersect_
+ static bool do_intersect_
private:
//@{
Anders Logg (logg) said :  #5 
On Sat, Feb 20, 2010 at 01:06:17AM 0000, Andre Massing wrote:
> Question #101686 on DOLFIN changed:
> https:/
>
> Andre Massing proposed the following answer:
>
> Garth N. Wells wrote:
> >
> > Andre Massing wrote:
> >> Question #101686 on DOLFIN changed:
> >> https:/
> >>
> >> Status: Open => Answered
> >>
> >> Andre Massing proposed the following answer:
> >> On Friday 19. February 2010 18.33.47 marc spiegelman wrote:
> >> > New question #101686 on DOLFIN:
> >> > https:/
> >> >
> >> > Hi All,
> >> > I've implemented a rather nifty semilagrangian advection scheme in
> >> > dolfin that requires rapid checking to see if a point intersects a
> >> > cell
> >> > (without necessarily firing up the full intersection operator). Pre
> >> > 0.9.7
> >> > this was implemented as cell.intersects
> >> >
> >> > Everything works fine in 0.9.6 with the new CGAL intersection
> >> > operator
> >> > replacing the GTS intersection operator (with about a 20% speedup).
> >>
> >> Did you only use the intersection between meshentities and points or did
> >> you
> >> use also the new mesh intersection operator? Just curious, because the
> >> former
> >> code for intersection between points og e.g. triangles did not change.
> >>
> >> > However, in 0.9.7 the code breaks because cell.intersects() has been
> >> > removed as a GTS dependency (actually, looking at
> >> > TriangleCell.
> >> > GTS
> >> > code but wasn't actually dependent on GTS)
> >>
> >> Yep that's true, the intersection functions was removed and there is a new
> >> PrimitiveInters
> >> the intersection between rather arbitrary mesh entities (exact or only
> >> using
> >> doubling precision). The functions are exposed as do_intersect and
> >> do_intersect_exact in the python interface. But you are right, a point 
> >> meshentity intersection is not provided. I attached a patch against the
> >> recent
> >> 0.9.7 release. Could you can apply to you sources and see whether it
> >> works for
> >> you?
> >>
> >
> > Andre: Did you forget to attach it?
>
> Hmm, I did not, at least in my sent box it also appeared with
> attachment. Strange... resend it (CC to the DOLFINml).
We also need to add back the simple interface
bool MeshEntity:
where foo can be either a Point or another MeshEntity.
do_intersect looks a bit strange to me. (But it might be good for the
lowlevel interface that interacts with the CGAL templates.)

Anders
Andre Massing (massing) said :  #6 
Anders Logg wrote:
> Question #101686 on DOLFIN changed:
> https:/
>
> Anders Logg proposed the following answer:
> On Sat, Feb 20, 2010 at 01:06:17AM 0000, Andre Massing wrote:
>> Question #101686 on DOLFIN changed:
>> https:/
>>
>> Andre Massing proposed the following answer:
>>
>> Garth N. Wells wrote:
>>> Andre Massing wrote:
>>>> Question #101686 on DOLFIN changed:
>>>> https:/
>>>>
>>>> Status: Open => Answered
>>>>
>>>> Andre Massing proposed the following answer:
>>>> On Friday 19. February 2010 18.33.47 marc spiegelman wrote:
>>>> > New question #101686 on DOLFIN:
>>>> > https:/
>>>> >
>>>> > Hi All,
>>>> > I've implemented a rather nifty semilagrangian advection scheme in
>>>> > dolfin that requires rapid checking to see if a point intersects a
>>>> > cell
>>>> > (without necessarily firing up the full intersection operator). Pre
>>>> > 0.9.7
>>>> > this was implemented as cell.intersects
>>>> >
>>>> > Everything works fine in 0.9.6 with the new CGAL intersection
>>>> > operator
>>>> > replacing the GTS intersection operator (with about a 20% speedup).
>>>>
>>>> Did you only use the intersection between meshentities and points or did
>>>> you
>>>> use also the new mesh intersection operator? Just curious, because the
>>>> former
>>>> code for intersection between points og e.g. triangles did not change.
>>>>
>>>> > However, in 0.9.7 the code breaks because cell.intersects() has been
>>>> > removed as a GTS dependency (actually, looking at
>>>> > TriangleCell.
>>>> > GTS
>>>> > code but wasn't actually dependent on GTS)
>>>>
>>>> Yep that's true, the intersection functions was removed and there is a new
>>>> PrimitiveInters
>>>> the intersection between rather arbitrary mesh entities (exact or only
>>>> using
>>>> doubling precision). The functions are exposed as do_intersect and
>>>> do_intersect_exact in the python interface. But you are right, a point 
>>>> meshentity intersection is not provided. I attached a patch against the
>>>> recent
>>>> 0.9.7 release. Could you can apply to you sources and see whether it
>>>> works for
>>>> you?
>>>>
>>> Andre: Did you forget to attach it?
>> Hmm, I did not, at least in my sent box it also appeared with
>> attachment. Strange... resend it (CC to the DOLFINml).
>
> We also need to add back the simple interface
>
> bool MeshEntity:
>
> where foo can be either a Point or another MeshEntity.
Of course we can do this. But before I removed it, we discussed it a bit
and concluded that intersects should not be a member function of an
entity (IIRC :), because it is a symmetric operation between geometric
objects and calculation of intersection detection is dependent on both
involved types.
>
> do_intersect looks a bit strange to me. (But it might be good for the
> lowlevel interface that interacts with the CGAL templates.)
Why exactly? It takes two entities or an entity and a point and just
returns a boolean value, stating, whether to entities "do intersect" :)
But what might be a better, more meaningful name? Just "intersects"? Or
what did you think of?
>
> 
> Anders
>
Anders Logg (logg) said :  #7 
On Sat, Feb 20, 2010 at 05:54:18PM 0000, Andre Massing wrote:
> Question #101686 on DOLFIN changed:
> https:/
>
> Andre Massing proposed the following answer:
>
> Anders Logg wrote:
> > Question #101686 on DOLFIN changed:
> > https:/
> >
> > Anders Logg proposed the following answer:
> > On Sat, Feb 20, 2010 at 01:06:17AM 0000, Andre Massing wrote:
> >> Question #101686 on DOLFIN changed:
> >> https:/
> >>
> >> Andre Massing proposed the following answer:
> >>
> >> Garth N. Wells wrote:
> >>> Andre Massing wrote:
> >>>> Question #101686 on DOLFIN changed:
> >>>> https:/
> >>>>
> >>>> Status: Open => Answered
> >>>>
> >>>> Andre Massing proposed the following answer:
> >>>> On Friday 19. February 2010 18.33.47 marc spiegelman wrote:
> >>>> > New question #101686 on DOLFIN:
> >>>> > https:/
> >>>> >
> >>>> > Hi All,
> >>>> > I've implemented a rather nifty semilagrangian advection scheme in
> >>>> > dolfin that requires rapid checking to see if a point intersects a
> >>>> > cell
> >>>> > (without necessarily firing up the full intersection operator). Pre
> >>>> > 0.9.7
> >>>> > this was implemented as cell.intersects
> >>>> >
> >>>> > Everything works fine in 0.9.6 with the new CGAL intersection
> >>>> > operator
> >>>> > replacing the GTS intersection operator (with about a 20% speedup).
> >>>>
> >>>> Did you only use the intersection between meshentities and points or did
> >>>> you
> >>>> use also the new mesh intersection operator? Just curious, because the
> >>>> former
> >>>> code for intersection between points og e.g. triangles did not change.
> >>>>
> >>>> > However, in 0.9.7 the code breaks because cell.intersects() has been
> >>>> > removed as a GTS dependency (actually, looking at
> >>>> > TriangleCell.
> >>>> > GTS
> >>>> > code but wasn't actually dependent on GTS)
> >>>>
> >>>> Yep that's true, the intersection functions was removed and there is a new
> >>>> PrimitiveInters
> >>>> the intersection between rather arbitrary mesh entities (exact or only
> >>>> using
> >>>> doubling precision). The functions are exposed as do_intersect and
> >>>> do_intersect_exact in the python interface. But you are right, a point 
> >>>> meshentity intersection is not provided. I attached a patch against the
> >>>> recent
> >>>> 0.9.7 release. Could you can apply to you sources and see whether it
> >>>> works for
> >>>> you?
> >>>>
> >>> Andre: Did you forget to attach it?
> >> Hmm, I did not, at least in my sent box it also appeared with
> >> attachment. Strange... resend it (CC to the DOLFINml).
> >
> > We also need to add back the simple interface
> >
> > bool MeshEntity:
> >
> > where foo can be either a Point or another MeshEntity.
>
> Of course we can do this. But before I removed it, we discussed it a bit
> and concluded that intersects should not be a member function of an
> entity (IIRC :), because it is a symmetric operation between geometric
> objects and calculation of intersection detection is dependent on both
> involved types.
>
> >
> > do_intersect looks a bit strange to me. (But it might be good for the
> > lowlevel interface that interacts with the CGAL templates.)
>
> Why exactly? It takes two entities or an entity and a point and just
> returns a boolean value, stating, whether to entities "do intersect" :)
> But what might be a better, more meaningful name? Just "intersects"? Or
> what did you think of?
I'm thinking we should reserve free functions for a few main
operations like assemble, solve, plot, refine. It would be more
natural to have intersects() as a member function in MeshEntity and
Point. They can be inlined and just call
PrimitiveInters

Anders
Andre Massing (massing) said :  #8 
Hi Marc!
Just for your information, the code has been merged into the main trunk of DOLFIN, so there is again a intersects() member function available, now being member of the MeshEntity class. It computes exactly without limit precision related errors.
Hence it is slower then its inexact counterpart (which uses only double precision). If you need more speed you can also access the static do_intersect function of the PrimitiveInters
Any feedback is highly appreciated!
Anders Logg (logg) said :  #9 
On Fri, Mar 05, 2010 at 09:55:35AM 0000, Andre Massing wrote:
> Question #101686 on DOLFIN changed:
> https:/
>
> Andre Massing posted a new comment:
> Hi Marc!
>
> Just for your information, the code has been merged into the main trunk of DOLFIN, so there is again a intersects() member function available, now being member of the MeshEntity class. It computes exactly without limit precision related errors.
> Hence it is slower then its inexact counterpart (which uses only double precision). If you need more speed you can also access the static do_intersect function of the PrimitiveInters
>
> Any feedback is highly appreciated!
I just added two new functions:
intersects_
intersects_
which map to do_intersect_exact and changed intersects() to map to the
fast version.

Anders
Andre Massing (massing) said :  #10 
Anders Logg wrote:
> On Fri, Mar 05, 2010 at 09:55:35AM 0000, Andre Massing wrote:
>> Question #101686 on DOLFIN changed:
>> https:/
>>
>> Andre Massing posted a new comment:
>> Hi Marc!
>>
>> Just for your information, the code has been merged into the main trunk of DOLFIN, so there is again a intersects() member function available, now being member of the MeshEntity class. It computes exactly without limit precision related errors.
>> Hence it is slower then its inexact counterpart (which uses only double precision). If you need more speed you can also access the static do_intersect function of the PrimitiveInters
>>
>> Any feedback is highly appreciated!
>
> I just added two new functions:
>
> intersects_
> intersects_
>
> which map to do_intersect_exact and changed intersects() to map to the
> fast version.
Ok, cool, was going to ask about that, but you replied faster then I ask :)
>
> 
> Anders
>
>
> 
>
> _______
> Mailing list: https:/
> Post to : <email address hidden>
> Unsubscribe : https:/
> More help : https:/
Garth Wells (garthwells) said :  #11 
Present in latest release.