CGAL users discussion list

[Andreas Fabri <>]

Thomas Zangl - Home wrote:
>  
> Am Thu, 03 Jul 2008 10:06:29 +0200, schrieb "Andreas Fabri" <>:
>
> 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,