Difference between Lazy_exact and Filtered_kernel?

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

Difference between Lazy_exact and Filtered_kernel?

Thomas Zangl - Home
 
Hi!

I am currently trying to figure out the difference between the
Lazy_exact<Simple_Cartesian<Gmpq> > > kernel and the          
Filtered_kernel<Simple_Cartesian<Gmpq> > > .

The Lazy_exact uses Interval Arithmetic which is some kind of dynamic
filtering - true?

The Filtered_kernel uses then what..? If compiled without
"NO_STATIC_FILTERS" it uses static filtering, and otherwise..? Please
elaborate a bit on this topic :-) I did not find anything in the 2D and
3D Geometry Kernel manual except class definitions etc. I also already
read the paper about Interval Arithmetic.  

What is the expected performance difference between those two kernel
types?

Thank you in advance!

Yours,
--
,yours Thomas Zangl, Bakk.rer.soc.oec. - [hidden email] -
- Freelancer - IT Consulting & Software Development -
- Student of Software Development-Economy (Master) -
            - http://blog.tzis.net -
--
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: Difference between Lazy_exact and Filtered_kernel?

andreas.fabri
Thomas Zangl - Home wrote:

>  
> Hi!
>
> I am currently trying to figure out the difference between the
> Lazy_exact<Simple_Cartesian<Gmpq> > > kernel and the          
> Filtered_kernel<Simple_Cartesian<Gmpq> > > .
>
> The Lazy_exact uses Interval Arithmetic which is some kind of dynamic
> filtering - true?
>
> The Filtered_kernel uses then what..? If compiled without
> "NO_STATIC_FILTERS" it uses static filtering, and otherwise..? Please
> elaborate a bit on this topic :-) I did not find anything in the 2D and
> 3D Geometry Kernel manual except class definitions etc. I also already
> read the paper about Interval Arithmetic.  
>
> What is the expected performance difference between those two kernel
> types?
>
> Thank you in advance
>
> Yours,


The lazy exact kernel stores DAGs (directed acyclic graph) of geometric and
arithmetic operations.
Each node of the DAG stores
- a geometric object or number with intervals of doubles,
- the type of the geometric or arithmetic operation
- pointers to the DAG nodes representing the operands of the geometric/arithmetic
   operation

When a predicate on a lazy object fails the postponed exact computation
is replayed from the information stored in the DAG.


The Filtered_kernel only  provides exact predicates, that is all constructions
are double constructions.

So to compare their performance doesn't really make sense. The latter is
faster but provides no exact constructions.

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:Difference between Lazy_exact and Filtered_kernel?

Thomas Zangl - Home
 
Am Thu, 03 Jul 2008 10:06:29 +0200, schrieb "Andreas Fabri" <[hidden email]>:

Hi!

>The lazy exact kernel stores DAGs (directed acyclic graph) of geometric and
>arithmetic operations.

Is that the expresion to compute some predicate?

>Each node of the DAG stores
>- a geometric object or number with intervals of doubles,
>- the type of the geometric or arithmetic operation
>- pointers to the DAG nodes representing the operands of the geometric/arithmetic
>   operation
>
>When a predicate on a lazy object fails the postponed exact computation
>is replayed from the information stored in the DAG.

So, the lazy object is more or less a caching?

E.g. if I query the lazy kernel for the intersection between two
identical segments a few times, only the first intersection test is
made and all subsequent tests are returned from the DAG but only if the
two segments remain unchanged?

>The Filtered_kernel only  provides exact predicates, that is all constructions
>are double constructions.

How can it be then that the Exact_constr._exact_pred. kernel uses a
defintion like this:

typedef Lazy_kernel<Simple_cartesian<Gmpq> >
        Exact_predicates_exact_constructions_kernel;

The constructions are done using Gmpq so they are considered exact,
arent they? If thats true, the filtered_kernel does only predicates and
needs an exact number type like Gmpq to produce exact construction,
true?

Is my conclusion true:

Filtered_kernel<Simple_cartesian<Lazy_exact_nt<Gmpq > > >  : first,
use a cheap (semi-)static filter, then fall back to the lazy kernel
(Interval arithmetic) and finally use exact computations.

Lazy_kernel<Simple_cartesian<Gmpq> > : first try to use the lazy
kernel and then fall back to exact computations.

>So to compare their performance doesn't really make sense. The latter is
>faster but provides no exact constructions.

Ok. My goal was to show that different kernels (and the way how
filters are chained) influence the runtime. So I can compare a
Simple_cartesian<Gmpq> along with a Lazy_kernel<Simple_cartesian<Gmpq>
and conclude about it effect (I bet it will give a speedup) ? Is this
true?

TIA,
--
,yours Thomas Zangl, Bakk.rer.soc.oec. - [hidden email] -
- Freelancer - IT Consulting & Software Development -
- Student of Software Development-Economy (Master) -
            - http://blog.tzis.net -
--
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: Difference between Lazy_exact and Filtered_kernel?

andreas.fabri
Thomas Zangl - Home wrote:

>  
> Am Thu, 03 Jul 2008 10:06:29 +0200, schrieb "Andreas Fabri" <[hidden email]>:
>
> Hi!
>
>> The lazy exact kernel stores DAGs (directed acyclic graph) of geometric and
>> arithmetic operations.
>
> Is that the expresion to compute some predicate?
>
>> Each node of the DAG stores
>> - a geometric object or number with intervals of doubles,
>> - the type of the geometric or arithmetic operation
>> - pointers to the DAG nodes representing the operands of the geometric/arithmetic
>>   operation
>>
>> When a predicate on a lazy object fails the postponed exact computation
>> is replayed from the information stored in the DAG.
>
> So, the lazy object is more or less a caching?

It's not a cache, but a tracking of history, for repeating
a sequence of operations for an exact type  if one cannot
securely evaluate a predicate with the interval approximations.

Maybe have a look at the following paper:
ftp://ftp-sop.inria.fr/geometrica/pion/publis/lazy-kernel.pdf

>
> E.g. if I query the lazy kernel for the intersection between two
> identical segments a few times, only the first intersection test is
> made and all subsequent tests are returned from the DAG but only if the
> two segments remain unchanged?
>
>> The Filtered_kernel only  provides exact predicates, that is all constructions
>> are double constructions.
>
> How can it be then that the Exact_constr._exact_pred. kernel uses a
> defintion like this:
>
> typedef Lazy_kernel<Simple_cartesian<Gmpq> >
>         Exact_predicates_exact_constructions_kernel;
>
> The constructions are done using Gmpq so they are considered exact,
> arent they? If thats true, the filtered_kernel does only predicates and
> needs an exact number type like Gmpq to produce exact construction,
> true?

The constructions are done with Cartesian<Interval_nt>
and the fallback is Simple_cartesian<Gmpq>

If the constructions were always done with Gmpq there would be no performance gain.

>
> Is my conclusion true:
>
> Filtered_kernel<Simple_cartesian<Lazy_exact_nt<Gmpq > > >  : first,
> use a cheap (semi-)static filter, then fall back to the lazy kernel
> (Interval arithmetic) and finally use exact computations.
>
> Lazy_kernel<Simple_cartesian<Gmpq> > : first try to use the lazy
> kernel and then fall back to exact computations.
>
>> So to compare their performance doesn't really make sense. The latter is
>> faster but provides no exact constructions.
>
> Ok. My goal was to show that different kernels (and the way how
> filters are chained) influence the runtime. So I can compare a
> Simple_cartesian<Gmpq> along with a Lazy_kernel<Simple_cartesian<Gmpq>
> and conclude about it effect (I bet it will give a speedup) ? Is this
> true?

It should give speedup.

As the Lazy_kernel is a recent feature we observed cases though
where Simple_cartesian<Lazy_exact_nt> was faster than Lazy_kernel<..>
Although one would expect the geometric expression tree of an algorithm
to have less nodes than an arithmetic expression tree this is not
always the case.

andreas

>
> TIA,

--
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:Difference between Lazy_exact and Filtered_kernel?

Thomas Zangl - Home
 
Am Thu, 03 Jul 2008 14:03:55 +0200, schrieb "Andreas Fabri" <[hidden email]>:


Hi!

>>> The lazy exact kernel stores DAGs (directed acyclic graph) of geometric and
>>> arithmetic operations.

And the Filtered_Kernel only uses interval arithmetic for some
pre-defined predicates?

Sorry, but I did not get yet what the *main* difference between the
Lazy_kernel and Filtered_kernel is.

As far as I was able to extract from docs, sources and papers is:

Filtered_kernel:

* Interval arithmetic and maybe static-filters (if not disabled)

Lazy_kernel:

* Stores DAGs of arithmetic operations, geometric constructions  
and predicates.
* Uses interval arithmetic (''Approximate'') and reverts back to exact
computations if the IA is unsure

Is that correct? So, is the use of caching DAGs the only difference
between the Lazy_kernel and the Filtered_kernel?

TIA!,
--
,yours Thomas Zangl, Bakk.rer.soc.oec. - [hidden email] -
- Freelancer - IT Consulting & Software Development -
- Student of Software Development-Economy (Master) -
            - http://blog.tzis.net -
--
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: Difference between Lazy_exact and Filtered_kernel?

andreas.fabri
Thomas Zangl - Home wrote:

>  
> Am Thu, 03 Jul 2008 14:03:55 +0200, schrieb "Andreas Fabri" <[hidden email]>:
>
>
> Hi!
>
>>>> The lazy exact kernel stores DAGs (directed acyclic graph) of geometric and
>>>> arithmetic operations.
>
> And the Filtered_Kernel only uses interval arithmetic for some
> pre-defined predicates?

For all predicates

>
> Sorry, but I did not get yet what the *main* difference between the
> Lazy_kernel and Filtered_kernel is.

The main difference is that
The lazy kernel is exact_predicates_exact_constructions
The Filtered kernel is only exact_predicates

andreas

>
> As far as I was able to extract from docs, sources and papers is:
>
> Filtered_kernel:
>
> * Interval arithmetic and maybe static-filters (if not disabled)
>
> Lazy_kernel:
>
> * Stores DAGs of arithmetic operations, geometric constructions  
> and predicates.
> * Uses interval arithmetic (''Approximate'') and reverts back to exact
> computations if the IA is unsure
>
> Is that correct? So, is the use of caching DAGs the only difference
> between the Lazy_kernel and the Filtered_kernel?
>
> TIA!,

--
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:Difference between Lazy_exact and Filtered_kernel?

Thomas Zangl - Home
 
Am Thu, 03 Jul 2008 15:21:43 +0200, schrieb "Andreas Fabri" <[hidden email]>:

Hi!

>The main difference is that
>The lazy kernel is exact_predicates_exact_constructions
>The Filtered kernel is only exact_predicates

But, if I typedef the Filtered_kernel as done by the predefined
Exact_constructions_exact_predicates kernel, I also have exact
constructions.

However, is it true that the constructions are not ''optimized'' but
always done using exact arithmetic? Because the Filtered_kernel is
parametrized using the Gmpq number type.

Thank you for patiently answering my questions :-)

Best regards,
--
,yours Thomas Zangl, Bakk.rer.soc.oec. - [hidden email] -
- Freelancer - IT Consulting & Software Development -
- Student of Software Development-Economy (Master) -
            - http://blog.tzis.net -
--
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:Difference between Lazy_exact and Filtered_kernel?

Thomas Zangl - Home
In reply to this post by andreas.fabri
 
Am Thu, 03 Jul 2008 15:21:43 +0200, schrieb "Andreas Fabri" <[hidden email]>:

Hi!

Another question which arise during testing:

in ftp://ftp-sop.inria.fr/geometrica/pion/publis/lazy-kernel.pdf you
make a comparison between different kernels. Now, I ask myself:

if I use:
typedef CGAL::Simple_cartesian<CGAL::Gmpq> K;
typedef CGAL::Gmpq dbl;

all predicates and operations are done exactly? Like if the
filter of the Filtered_Kernel always returns "NO_IDEA"?

The reason is, if I use the plain Exact_pred_exact_constr. kernel, my
test app does not produce any degenerate cases. If I use the kernel
typedef'd above, I get a lot of them. It seems, computation accuracy is
far worse with the Simple_cartesian<CGAL::Gmpq> in my case.

Any idea why this can happen? How can I clarify that all computations
are done using exact arithmetic like described in your paper?

TIA,
--
,yours Thomas Zangl, Bakk.rer.soc.oec. - [hidden email] -
- Freelancer - IT Consulting & Software Development -
- Student of Software Development-Economy (Master) -
            - http://blog.tzis.net -
--
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: Difference between Lazy_exact and Filtered_kernel?

andreas.fabri
Thomas Zangl - Home wrote:

>  
> Am Thu, 03 Jul 2008 15:21:43 +0200, schrieb "Andreas Fabri" <[hidden email]>:
>
> Hi!
>
> Another question which arise during testing:
>
> in ftp://ftp-sop.inria.fr/geometrica/pion/publis/lazy-kernel.pdf you
> make a comparison between different kernels. Now, I ask myself:
>
> if I use:
> typedef CGAL::Simple_cartesian<CGAL::Gmpq> K;
> typedef CGAL::Gmpq dbl;
>
> all predicates and operations are done exactly? Like if the
> filter of the Filtered_Kernel always returns "NO_IDEA"?
>
> The reason is, if I use the plain Exact_pred_exact_constr. kernel, my
> test app does not produce any degenerate cases. If I use the kernel
> typedef'd above, I get a lot of them. It seems, computation accuracy is
> far worse with the Simple_cartesian<CGAL::Gmpq> in my case.

Can you give a minimalistic code example.

andreas

> Any idea why this can happen? How can I clarify that all computations
> are done using exact arithmetic like described in your paper?
>
> TIA,

--
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:Difference between Lazy_exact and Filtered_kernel?

Thomas Zangl - Home
In reply to this post by andreas.fabri
 
Am Thu, 03 Jul 2008 15:21:43 +0200, schrieb "Andreas Fabri" <[hidden email]>:

Hi!

>> Sorry, but I did not get yet what the *main* difference between the
>> Lazy_kernel and Filtered_kernel is.
>
>The main difference is that
>The lazy kernel is exact_predicates_exact_constructions
>The Filtered kernel is only exact_predicates

I tried to summarize your explainations about the lazy kernel and the
DAG of the geometric operations:

If geometric and arithmetic operations are carried out using the exact number type, the lazy kernel stores a DAG (''directed acyclic graph'') for every operation. Each node of the DAG stores:

* A geometric object or number with intervals of doubles,
* The type of the geometric or arithmetic operation,
* Pointers to the DAG nodes representing the operands of the
geometric/arithmetic operation.

The DAG for each operation is stored in a history-like way. If a
predicate on the lazy kernel fails, the postponed exact computation is
replayed from the information stored in the DAG. The lazy kernel fails
if e.g., a comparison is performed using Interval arithmetic and the
interval overlaps, hence, the filter cannot securely decide.

-----

However, some questions arise:

-> Is a Geometric object something like a point, line, segment, plane,
triangle?
-> The type of geometric or artihmetic operation is: +,-, etc. or
"intersection(x,y)"?

How are the constructions filtered? Can you please give me an example?

Thank you!
--
,yours Thomas Zangl, Bakk.rer.soc.oec. - [hidden email] -
- Freelancer - IT Consulting & Software Development -
- Student of Software Development-Economy (Master) -
            - http://blog.tzis.net -
--
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: Difference between Lazy_exact and Filtered_kernel?

andreas.fabri
Hi Thomas,

Thomas Zangl - Home wrote:

>  
> Am Thu, 03 Jul 2008 15:21:43 +0200, schrieb "Andreas Fabri" <[hidden email]>:
>
> Hi!
>
>>> Sorry, but I did not get yet what the *main* difference between the
>>> Lazy_kernel and Filtered_kernel is.
>> The main difference is that
>> The lazy kernel is exact_predicates_exact_constructions
>> The Filtered kernel is only exact_predicates
>
> I tried to summarize your explainations about the lazy kernel and the
> DAG of the geometric operations:
>
> If geometric and arithmetic operations are carried out using the exact number type, the lazy kernel stores a DAG (''directed acyclic graph'') for every operation. Each node of the DAG stores:
>
> * A geometric object or number with intervals of doubles,
> * The type of the geometric or arithmetic operation,
> * Pointers to the DAG nodes representing the operands of the
> geometric/arithmetic operation.
>
> The DAG for each operation is stored in a history-like way. If a
> predicate on the lazy kernel fails, the postponed exact computation is
> replayed from the information stored in the DAG. The lazy kernel fails
> if e.g., a comparison is performed using Interval arithmetic and the
> interval overlaps, hence, the filter cannot securely decide.
>
> -----
>
> However, some questions arise:
>
> -> Is a Geometric object something like a point, line, segment, plane,
> triangle?

right
> -> The type of geometric or artihmetic operation is: +,-, etc. or
> "intersection(x,y)"?

It's not 'or' but 'and'. Also the lazy geometric objects have
a lazy number type for the coordinates, that is

Lazy_exact_nt   Lazy<Point>::x();


The DAG of the number stores the DAG of the point.


>
> How are the constructions filtered? Can you please give me an example?
>

When you perform an orientation test for three lazy points
it is first performed on the approximate points with double intervals.
If this cannot been done the exact versions of the points are
computed by applying the exact constructions of the DAG.

andreas

> Thank you!

--
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:Difference between Lazy_exact and Filtered_kernel?

Thomas Zangl - Home
 
Hi!

>> How are the constructions filtered? Can you please give me an example?
>>
>
>When you perform an orientation test for three lazy points
>it is first performed on the approximate points with double intervals.
>If this cannot been done the exact versions of the points are
>computed by applying the exact constructions of the DAG.

I thought an orientation test is a predicate not a construction? I
assumed that a construction ''computess'' a new geometric object like:
mySegment = dt.dual(myDelaunayFacet) (dual method of a Delaunay
triangulation).

What is the exact difference between a predicate and a construction?

Thank you!

Best regards,
--
,yours Thomas Zangl, Bakk.rer.soc.oec. - [hidden email] -
- Freelancer - IT Consulting & Software Development -
- Student of Software Development-Economy (Master) -
            - http://blog.tzis.net -
--
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: Difference between Lazy_exact and Filtered_kernel?

andreas.fabri
Thomas Zangl - Home wrote:

>  
> Hi!
>
>>> How are the constructions filtered? Can you please give me an example?
>>>
>> When you perform an orientation test for three lazy points
>> it is first performed on the approximate points with double intervals.
>> If this cannot been done the exact versions of the points are
>> computed by applying the exact constructions of the DAG.
>
> I thought an orientation test is a predicate not a construction? I
> assumed that a construction ''computess'' a new geometric object like:
> mySegment = dt.dual(myDelaunayFacet) (dual method of a Delaunay
> triangulation).
>
> What is the exact difference between a predicate and a construction?
>
> Thank you!
>
> Best regards,

Hi Thomas,

Did you read   "A Generic Lazy Evaluation Scheme for Exact Geometric Computations"
Sylvain Pion and Andreas Fabri,
In Proc. 2nd Library-Centric Software Design, pages 75-84, Portland, Oregon, 2006.

ftp://ftp-sop.inria.fr/geometrica/pion/publis/lazy-kernel.pdf

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