lib2geom-devel

[Lib2geom-devel] some todos and wishes

[<Jea...@ma...>]

Hi!

After playing a bit with the library, I came up with some todos and
wishes, that I submit before I forget them; some might already be there
but I was not aware, or some might be bad ideas for some other reason...
These are just suggestions:

First, things would be more pleasant if we had:
- automatic conversions: sb to pw<sb> (Linear to sb, double to Linear).
- allow +,-,* between double,sb,pw<sb>,d2<pw<sb>>,d2<pw<sb>>.
- allow composition sb(pw<sb>)
- allow composition d2<pw<sb>>(sb) and pw<d2<sb>>(sb)
- define a plotter function for d2<pw<sb>> and pw<d2<sb>> (for toys/tests)

I noticed some function are out of age (this is my fault!!)
- update 'unit-vector'
- update 'arc-length-sb'

Some remarks about our conventions:
- define "bridges" between d2<pw<sb>> and pw<d2<sb>>.
  Although d2<pw<sb>> is usefull in some situations (plotting a function
  for instance), many operations require synchronous cuts, so pw<d2<sb>>
  instead. Note that once a d2<pw<sb>> has synchronous cuts, there is no
  synchronizing for each new operation... To make this implicit, our
  functions should accept both d2<pw<sb>> and pw<d2<sb>>, and do some
  conversion if needed. Or should we get rid of d2<pw<sb>>?
- fix convention about empty sb/pw<sb>: an empty sb is the constant 0
  while empty pw<sb> are not allowed. How do we represent 0 in pw<sb>
  world? as (pw<sb>)Linear(0)?

Some less relevant todos:
- define some standard functions for pw<sb>: sqrt, cos, sin...
- define pw<sb> and d2<pw<sb>> bounds.

What do you think?
JF.

Re: [Lib2geom-devel] some todos and wishes

[mgsloan <mg...@gm...>]

Hmm, I think i may not have sent it to the lists...

After playing a bit with the library, I came up with some todos and
> wishes, that I submit before I forget them; some might already be there
> but I was not aware, or some might be bad ideas for some other reason...
> These are just suggestions:
>
> First, things would be more pleasant if we had:
> - automatic conversions: sb to pw<sb> (Linear to sb, double to Linear).
> - allow +,-,* between double,sb,pw<sb>,d2<pw<sb>>,d2<pw<sb>>.
> - allow composition sb(pw<sb>)
> - allow composition d2<pw<sb>>(sb) and pw<d2<sb>>(sb)
> - define a plotter function for d2<pw<sb>> and pw<d2<sb>> (for toys/tests)
>


Sounds good!  There's at least an explicit constructor for sb -> pw<sb>, and
I know there is a Linear -> SBasis.  I think I have an accidental double ->
Linear too.  Turns out single parameter constructors are interpreted as
conversions!  At somepoint I'll probably switch the single param
constructors over to explicit conversions, and stick explicit on all
non-conversion constructors.

One thing I'd like to avoid is too many operators.  Often times when it
can't figure out what you mean by a particular operator, it'll print out all
of the declerations associated with it.  However, we certainly want a
complete, predictable set of operations across all.  It's possible we might
be able to leverage implicit conversion to minimize operator numbers.

As far as the plotters, cairo_md_sb can handle D2<Piecewise<SBasis> >.
Actually, Piecewise<D2<SBasis> > would be loads easier to implement - will
do next time.

Some remarks about our conventions:
> - define "bridges" between d2<pw<sb>> and pw<d2<sb>>.
>   Although d2<pw<sb>> is usefull in some situations (plotting a function
>   for instance), many operations require synchronous cuts, so pw<d2<sb>>
>   instead. Note that once a d2<pw<sb>> has synchronous cuts, there is no
>   synchronizing for each new operation... To make this implicit, our
>   functions should accept both d2<pw<sb>> and pw<d2<sb>>, and do some
>   conversion if needed. Or should we get rid of d2<pw<sb>>?


I actually think pw<d2<sb>> might be a good way to handle that.  currently
i've got a sectionize function that does d2<pw<sb>> -> vector<d2<sb>> but
that's not very good.  pw<d2<sb>> would be a much better output for it.

- fix convention about empty sb/pw<sb>: an empty sb is the constant 0
>   while empty pw<sb> are not allowed. How do we represent 0 in pw<sb>
>   world? as (pw<sb>)Linear(0)?


The thing is, either way there's going to be a check.  I suppose the good
thing about disallowing it is that it doesn't matter what the function
actually does.  The current convention is that it is indeed constant zero,
but i suppose concat does need a bit of work in that respect.  Yes, that's
the main way to reasonably represent 0.

Some less relevant todos:
> - define some standard functions for pw<sb>: sqrt, cos, sin...
> - define pw<sb> and d2<pw<sb>> bounds.


Sounds good.  yeah, I never really put much time into d2, more of a copy
paste and modify of multidim

What do you think?


some good ideas!

Re: [Lib2geom-devel] some todos and wishes

[njh <nj...@nj...>]

On Fri, 13 Apr 2007, mgsloan wrote:

> As far as the plotters, cairo_md_sb can handle D2<Piecewise<SBasis> >.
> Actually, Piecewise<D2<SBasis> > would be loads easier to implement - will
> do next time.

I think JF has swayed me to only using pw<d2 for the bulk of operations 
and use sectionize to convert d2<pw to pw<d2.  I can't think of any 
compelling d2<pw cases really, other than perhaps avoiding excessing 
segmentation.  That suggests better joining algorithms.

> The thing is, either way there's going to be a check.  I suppose the good
> thing about disallowing it is that it doesn't matter what the function
> actually does.  The current convention is that it is indeed constant zero,
> but i suppose concat does need a bit of work in that respect.  Yes, that's
> the main way to reasonably represent 0.

My biggest dislike of empty = 0 is that there is no analogous constant 
vale version.

>> - define some standard functions for pw<sb>: sqrt, cos, sin...

- general purpose bezier to sbasis (essentially a sparse matrix multiply)
- pow of various forms (pow(sb, double), pow(double, sb) etc)
- solve boundary value ODE (which is essentially what exp and sin do
     already)
- compose with periodic function
- geometric conversion to beziers (raph's algorithm perhaps?)

There is also a fair amount of old code which can be removed or simplified 
with Path2

njh

Re: [Lib2geom-devel] some todos and wishes

[mgsloan <mg...@gm...>]

>
>
> I think JF has swayed me to only using pw<d2 for the bulk of operations
> and use sectionize to convert d2<pw to pw<d2.  I can't think of any
> compelling d2<pw cases really, other than perhaps avoiding excessing
> segmentation.  That suggests better joining algorithms.


Sounds good!  Yeah, one thing that might be nice would be an algorithm to
find combinable, adjacent segments, and do combine them.  Hopefully it can
be written in such a way that it works for both 1d and 2d (eg, write 1d
accuracy and combination algos, then do a 1d and 2d optimizer).


> My biggest dislike of empty = 0 is that there is no analogous constant
> vale version.


Well, there's always Linear(x) from 0 to 1.  I guess that's what your
talking about.  I think SBasis has a similar situation in that empty = 0.
However, empty = 0 isn't as pure for pw - with polynomials it makes sense.
So, I guess I agree :)

- general purpose bezier to sbasis (essentially a sparse matrix multiply)


I think yesterday you mentioned needing to re-write this.  I've committed a
bezier.h, which is basically just a 1D version of path2's bezer.  It may be
renamed to BezierComponent or something like that in the future, but anyway,
this would be a good spot to add the code.

- pow of various forms (pow(sb, double), pow(double, sb) etc)
> - solve boundary value ODE (which is essentially what exp and sin do
>      already)
> - compose with periodic function
> - geometric conversion to beziers (raph's algorithm perhaps?)


Sounds like most of that is yours/jfs domain.  As for the compose with
periodics, first off, we'd need a periodics class which stores offset,
period, and a pw or an sb for the period.  Given a portion operation which
returns a pw of an interval of the periodic, composing (periodic . pw) would
become (pw . pw).  Composing (pw . periodic) would result in a periodic, and
would essentially be the inner sb/pw composed with the first pw.  So, I
think periodic stuff can be managed fairly quickly.  They allow fairly easy
segment count explosion, though, if you go high-frequency and compose with a
pw.

There is also a fair amount of old code which can be removed or simplified
> with Path2


Yep.  While I like how path2 keeps itself within a few files, I think it's
time to proliferate it out a bit, as the classes get more code-heavy.  We
really want to avoid using multiple structures for the same kinds of data.

Then that old code can either be moved to the new structures or deleted.
I'm pretty sure we could remove all of the old path code right now and still
compile, but there might still be some good stuff to mine.

-mgsloan

Re: [Lib2geom-devel] some todos and wishes

[njh <nj...@nj...>]

On Sat, 14 Apr 2007, mgsloan wrote:

> Sounds good!  Yeah, one thing that might be nice would be an algorithm to
> find combinable, adjacent segments, and do combine them.  Hopefully it can
> be written in such a way that it works for both 1d and 2d (eg, write 1d
> accuracy and combination algos, then do a 1d and 2d optimizer).

Compute the all the left and right derivative on the edge and if they are 
sufficiently equal, the curves are sufficiently equal.

> Sounds like most of that is yours/jfs domain.  As for the compose with
> periodics, first off, we'd need a periodics class which stores offset,
> period, and a pw or an sb for the period.  Given a portion operation which
> returns a pw of an interval of the periodic, composing (periodic . pw) would
> become (pw . pw).  Composing (pw . periodic) would result in a periodic, and
> would essentially be the inner sb/pw composed with the first pw.  So, I
> think periodic stuff can be managed fairly quickly.  They allow fairly easy
> segment count explosion, though, if you go high-frequency and compose with a
> pw.

Right, the main value is for things like wiggles, which are periodic.  The 
other discus-ed idea was lazy sbs such as pseudo-random, perlin, most 
higher functions (sqrt, e.g.) etc.

njh

Re: [Lib2geom-devel] some todos and wishes

[mgsloan <mg...@gm...>]

>
> > Sounds good!  Yeah, one thing that might be nice would be an algorithm
> to
> > find combinable, adjacent segments, and do combine them.  Hopefully it
> can
> > be written in such a way that it works for both 1d and 2d (eg, write 1d
> > accuracy and combination algos, then do a 1d and 2d optimizer).
>
> Compute the all the left and right derivative on the edge and if they are
> sufficiently equal, the curves are sufficiently equal.


That's what I thought at first, however, I'm not sure how that interacts
with combining sbasis.  This would mean that any C0, C1 pw could be a single
sbasis.  This may indeed be possible, however, we will need to do some cost
weighing in the function - a combination isn't valuable if it produces a
large coefficient count while reducing precision.

> Sounds like most of that is yours/jfs domain.  As for the compose with
> > periodics, first off, we'd need a periodics class which stores offset,
> > period, and a pw or an sb for the period.  Given a portion operation
> which
> > returns a pw of an interval of the periodic, composing (periodic . pw)
> would
> > become (pw . pw).  Composing (pw . periodic) would result in a periodic,
> and
> > would essentially be the inner sb/pw composed with the first pw.  So, I
> > think periodic stuff can be managed fairly quickly.  They allow fairly
> easy
> > segment count explosion, though, if you go high-frequency and compose
> with a
> > pw.
>
> Right, the main value is for things like wiggles, which are periodic.  The
> other discus-ed idea was lazy sbs such as pseudo-random, perlin, most
> higher functions (sqrt, e.g.) etc.


Lazy pw<sb>s are hard.  Maybe for 2geom scala.

The nice thing about having a periodic class like this is that you can
control what can be done with periodics - you can't perform an operation on
two periodics (might have nearly irrational period ratios), you can't cast
periodics to anything else.  All it can do is render itself useful to
something finite.  There are still problems though.  Lets say, pw +
periodic.  Outside the pw's intended domain, the periodicity will dissapear.

Anyway, progress report:
Completed - define a plotter function for d2<pw<sb>> and pw<d2<sb>> (for
toys/tests)

I've also done half of some of the other ones, like d2pw bridges and pw/d2pw
bounds.

I've modified Pw's concat to hopefully deal with emptys gracefully, however,
it is untested.

Oh, and now interval's functions look like this:
Interval::unionWith(Interval)
unify(Interval, Interval)
intersect(Interval, Interval)

Hopefully at some point rect will mostly be replaced by D2<Interval>

-mgsloan

Re: [Lib2geom-devel] some todos and wishes

[njh <nj...@nj...>]

On Sat, 14 Apr 2007, mgsloan wrote:

>> 
>> > Sounds good!  Yeah, one thing that might be nice would be an algorithm
>> to
>> > find combinable, adjacent segments, and do combine them.  Hopefully it
>> can
>> > be written in such a way that it works for both 1d and 2d (eg, write 1d
>> > accuracy and combination algos, then do a 1d and 2d optimizer).
>> 
>> Compute the all the left and right derivative on the edge and if they are
>> sufficiently equal, the curves are sufficiently equal.
>
>
> That's what I thought at first, however, I'm not sure how that interacts
> with combining sbasis.  This would mean that any C0, C1 pw could be a single
> sbasis.  This may indeed be possible, however, we will need to do some cost
> weighing in the function - a combination isn't valuable if it produces a
> large coefficient count while reducing precision.

Sorry, I managed to leave an 's' off:
  Compute the all the left and right derivatives on the edge and if they
  are sufficiently equal, the curves are sufficiently equal.

> The nice thing about having a periodic class like this is that you can
> control what can be done with periodics - you can't perform an operation on
> two periodics (might have nearly irrational period ratios), you can't cast
> periodics to anything else.  All it can do is render itself useful to
> something finite.  There are still problems though.  Lets say, pw +
> periodic.  Outside the pw's intended domain, the periodicity will dissapear.

Whereas lazy pws are always mergable.

sounds good.
njh

Re: [Lib2geom-devel] some todos and wishes

[mgsloan <mg...@gm...>]

> Sorry, I managed to leave an 's' off:
>   Compute the all the left and right derivatives on the edge and if they
>   are sufficiently equal, the curves are sufficiently equal.


Ahah, that would make more sense!  I think I'll still leave it to you though
- might want to factor the order of the derivative into the error equation.

> The nice thing about having a periodic class like this is that you can
> > control what can be done with periodics - you can't perform an operation
> on
> > two periodics (might have nearly irrational period ratios), you can't
> cast
> > periodics to anything else.  All it can do is render itself useful to
> > something finite.  There are still problems though.  Lets say, pw +
> > periodic.  Outside the pw's intended domain, the periodicity will
> dissapear.
>
> Whereas lazy pws are always mergable.


I suppose that is true.  However, as far as I know it would be hard for most
lazy languages to do what we want.  The problem is that in most, all data
types are a known size - multi size things like lists comes from nesting.
There are no pointers.  So, everything must be 'based' from some point.
This creates huge problems for structures that go infinitely both ways.  The
best solution is to pick an arbitrary split point, and have two lists.
Binary trees won't make any sense, because where do you pick a split when
the domain is infinite?  I suppose some wonky logarithmic binary tree might
work.  Anyway, the point is that it'd have to be some custom, new-style
laziness.

The true solution is to have a class for every operation, which extends the
class that the operation would normally return.  Then all of the methods
would be overloaded to figure out what they need to know to be performed,
check the memo cache, and ask for anything unknown.  Operations built on top
of the atomic ones would essentially construct operation trees.  This would
all be quite cool, in a horrifyingly convoluted sort of way.  I almost want
to implement it, but rationality holds me back.

-mgsloan