lib2geom-devel — development discussion

Re: [Lib2geom-devel] Boolean operations on adjacent cases

[Vincent B. <vin...@po...>]

> On Sun, Jul 1, 2012 at 4:42 PM, Krzysztof Kosiński <twe...@gm...> wrote:
>> It looks like the default copy constructor generated by the compiler
>> for GenericOptInterval doesn't work correctly

It sure looks like a compiler bug, I've managed to compile lib2geom
using msvc 2012 and didn't get this error. I'm attaching a patch with
the changes I've had to make to compile under msvc 2012. Is it the
proper way to submit code to lib2geom? Or should I publish my changes
on a branch on launchpad?

Regards,
Vincent

Re: [Lib2geom-devel] Boolean operations on adjacent cases

[Vincent B. <vin...@po...>]

Hi,

Here's the complete error log : http://pastebin.com/Y1Aq0d4F

--
Vincent

On Sun, Jul 1, 2012 at 4:42 PM, Krzysztof Kosiński <twe...@gm...> wrote:
> 2012/6/29 Vincent Barrielle <vin...@po...>:
>> I've been trying to link my application against lib2geom to try out
>> boolops, but the problem is, I'm using visual studio 2008 (have to,
>> unfortunately), and it fails when including lib2geom headers, problem
>> with boost optional as it seems :
>> "boost/optional/optional.hpp(392) : error C2664:
>> 'Geom::GenericInterval<C>::GenericInterval(C)' : cannot convert
>> parameter 1 from 'const Geom::GenericOptInterval<C>' to
>> 'Geom::IntCoord'"
>
> It looks like the default copy constructor generated by the compiler
> for GenericOptInterval doesn't work correctly, but I'm not 100% sure
> about it given the error message. Can you obtain a more verbose
> message?
>
> Regards, Krzysztof

Re: [Lib2geom-devel] Boolean operations on adjacent cases

[Krzysztof K. <twe...@gm...>]

2012/6/29 Vincent Barrielle <vin...@po...>:
> I've been trying to link my application against lib2geom to try out
> boolops, but the problem is, I'm using visual studio 2008 (have to,
> unfortunately), and it fails when including lib2geom headers, problem
> with boost optional as it seems :
> "boost/optional/optional.hpp(392) : error C2664:
> 'Geom::GenericInterval<C>::GenericInterval(C)' : cannot convert
> parameter 1 from 'const Geom::GenericOptInterval<C>' to
> 'Geom::IntCoord'"

It looks like the default copy constructor generated by the compiler
for GenericOptInterval doesn't work correctly, but I'm not 100% sure
about it given the error message. Can you obtain a more verbose
message?

Regards, Krzysztof

Re: [Lib2geom-devel] Boolean operations on adjacent cases

[Vincent B. <vin...@po...>]

On Wed, Jun 27, 2012 at 23:24 PM, Nathan Hurst wrote:
> The specific case of coincident polynomial curves is actually quite
> easy to detect - you just have to find more than m*n common points for
> a degree m and degree n curve.  In practice you probably need far
> fewer of these for a non equal curve because a randomly selected point
> has a low probability of being on both curves.  This includes conic
> sections (such as eliptical arcs).  To find partial overlaping bezier
> segments you can start with the existing intersector and when it finds
> sufficient matched points consider it equal.  (Note that
> mathematically equal curves can not share points due to rounding; in
> general floating point makes everything three times harder)

I've been using some other way to detect overlap : two bezier segments
overlap if at least one extremtity of each segment belongs to the
other. This test seems to work pretty well in my own framework, and I
guess it's faster than computing the intersections to find out there
are too many of them (especially as I'm using recursive method which
is not the fastest..). It allows generating intersections at the
extremities of the overlap, and can orient them correctly using the
next parts of the paths.

> The hardest problem to solve is correctly dealing with the imprecision
> around intersection points (determining the topology of the
> intersections).  We have not found a good answer to this problem,
> though we have many yet untried ideas.

I've got exactly the same problem in my framework right now, I've got
some cases were I handle the topology right, and some where I don't.
Right now my boolop procedure looks similar to the one you have in
lib2geom, though a bit different it seems as I'm implementing a
connected components on the graph defined by the two paths and their
crossings. Right now it works if there is no too long overlaping
portion (more than 3 consecutive bezier segments overlaping I'd say).
The problem that arises in that case is that I can't find a way to
orient the intersections in the middle of the path, as there's no way
to tell wether the intersection leads inside or outside the other
curve. I was thinking of possibly caching the orientation of previous
intersections during the visit of the graph, but I didn't try and
implement this method yet.

> If you want to try boolops we are all very happy to help, but be
> warned, it's one of the hardest problems in 2d geometry processing we
> know of :)

I've been trying to link my application against lib2geom to try out
boolops, but the problem is, I'm using visual studio 2008 (have to,
unfortunately), and it fails when including lib2geom headers, problem
with boost optional as it seems :
"boost/optional/optional.hpp(392) : error C2664:
'Geom::GenericInterval<C>::GenericInterval(C)' : cannot convert
parameter 1 from 'const Geom::GenericOptInterval<C>' to
'Geom::IntCoord'"
So I can't try it right now, but perhaps there's a way around this
compiling issue? That would be great, as it would allow me pushing my
firm into using lib2geom, and I could contribute what I've already
done on boolops if you're interested.

--
Vincent

Re: [Lib2geom-devel] Boolean operations on adjacent cases

[Nathan H. <nj...@nj...>]

On Wed, Jun 27, 2012 at 09:16:34PM +0200, Vincent Barrielle wrote:
> Hello,
> 
> I'm considering using lib2geom in my vector graphics tool to implement
> boolean operations. But before I try that I'd like to know how it
> handles hard cases such as computing intersections between two bezier
> segments that overlap, ie that have (mathematically) an infinite
> number of intersections. This case happens quite often in my project,
> so it's really important.
> 
> For what I've read of lib2geom's code, I haven't seen code dedicated
> to handling such cases, but perhaps I'm missing something?
> 
> If lib2geom does not handle this case, I'd be glad to try and
> contribute so that it is handled (I'm already trying to tackle this
> issue in my own boolops framework right now, but integrating lib2geom
> would be a great thing for my project).

The existing boolops code is in a some what disappointing state as it
turned out harder than anyone thought.

The specific case of coincident polynomial curves is actually quite
easy to detect - you just have to find more than m*n common points for
a degree m and degree n curve.  In practice you probably need far
fewer of these for a non equal curve because a randomly selected point
has a low probability of being on both curves.  This includes conic
sections (such as eliptical arcs).  To find partial overlaping bezier
segments you can start with the existing intersector and when it finds
sufficient matched points consider it equal.  (Note that
mathematically equal curves can not share points due to rounding; in
general floating point makes everything three times harder)

The hardest problem to solve is correctly dealing with the imprecision
around intersection points (determining the topology of the
intersections).  We have not found a good answer to this problem,
though we have many yet untried ideas.

If you want to try boolops we are all very happy to help, but be
warned, it's one of the hardest problems in 2d geometry processing we
know of :)

njh

[Lib2geom-devel] Boolean operations on adjacent cases

[Vincent B. <vin...@po...>]

Hello,

I'm considering using lib2geom in my vector graphics tool to implement
boolean operations. But before I try that I'd like to know how it
handles hard cases such as computing intersections between two bezier
segments that overlap, ie that have (mathematically) an infinite
number of intersections. This case happens quite often in my project,
so it's really important.

For what I've read of lib2geom's code, I haven't seen code dedicated
to handling such cases, but perhaps I'm missing something?

If lib2geom does not handle this case, I'd be glad to try and
contribute so that it is handled (I'm already trying to tackle this
issue in my own boolops framework right now, but integrating lib2geom
would be a great thing for my project).

Best regards,

Vincent Barrielle

Re: [Lib2geom-devel] python bindings and GSoC

[Johan E. <jbc...@sw...>]

On 24-5-2012 20:34, Nathan Hurst wrote:
> On Thu, May 24, 2012 at 07:39:46PM +0200, Johan Engelen wrote:
>> Hi all,
>>     Is there a branch that I can checkout to follow the progress of the
>> Python bindings?
> At this stage we're checking into the main branch - the changes will
> not affect the C++ code (apart from bug fixes), so there is no benefit
> to branching (and a significant cost).

Cool. I'll try to test this on Windows from time to time.

I have fixed Cython compiling on windows, but it does not link. [1]

"make install" also does not work.

Cheers,
   Johan


[1]
Linking CXX shared module cy2geom.pyd
c:/mingw32/bin/../lib/gcc/mingw32/4.6.1/../../../libmingw32.a(main.o): 
In function `main':
C:\MinGW\msys\1.0\src\mingwrt/../mingw/main.c:73: undefined reference to 
`WinMain@16'
collect2: ld returned 1 exit status
make[2]: *** [src/2geom/cython-bindings/cy2geom.pyd] Error 1
make[1]: *** [src/2geom/cython-bindings/CMakeFiles/cy2geom.dir/all] Error 2

Re: [Lib2geom-devel] python bindings and GSoC

[Nathan H. <nj...@nj...>]

On Thu, May 24, 2012 at 07:39:46PM +0200, Johan Engelen wrote:
> Hi all,
>    Is there a branch that I can checkout to follow the progress of the 
> Python bindings?

At this stage we're checking into the main branch - the changes will
not affect the C++ code (apart from bug fixes), so there is no benefit
to branching (and a significant cost).

njh

Re: [Lib2geom-devel] python bindings and GSoC

[Johan E. <jbc...@sw...>]

Hi all,
   Is there a branch that I can checkout to follow the progress of the 
Python bindings?

Thanks,
   Johan


On 12-4-2012 2:00, jan pulmann wrote:
> Hi,
> I would like to ask if lib2Geom would be interested in mentoring me as
> a student working on python bindings on lib2geom. I initially applied
> to inkscape, but I found out that working on internals is now the
> priority (contrary to my feature-adding proposal). I have experience
> with python and C++, I use them mainly for smaller projects and
> simulations - I study physics. Little bit of math wouldn't scare me
> off.
>
> I was also looking for some not very difficult bugfix or addition to
> your code, but you seem to get rid of reported bugs successfully,
> could someone point me to the right direction?
>
> Best regards
> Jan Pulmann
>
> ------------------------------------------------------------------------------
> For Developers, A Lot Can Happen In A Second.
> Boundary is the first to Know...and Tell You.
> Monitor Your Applications in Ultra-Fine Resolution. Try it FREE!
> http://p.sf.net/sfu/Boundary-d2dvs2
> _______________________________________________
> Lib2geom-devel mailing list
> Lib...@li...
> https://lists.sourceforge.net/lists/listinfo/lib2geom-devel
>

[Lib2geom-devel] python bindings and GSoC

[jan p. <jan...@gm...>]

Hi,
I would like to ask if lib2Geom would be interested in mentoring me as
a student working on python bindings on lib2geom. I initially applied
to inkscape, but I found out that working on internals is now the
priority (contrary to my feature-adding proposal). I have experience
with python and C++, I use them mainly for smaller projects and
simulations - I study physics. Little bit of math wouldn't scare me
off.

I was also looking for some not very difficult bugfix or addition to
your code, but you seem to get rid of reported bugs successfully,
could someone point me to the right direction?

Best regards
Jan Pulmann

Re: [Lib2geom-devel] isZero ...

[Johan E. <jbc...@sw...>]

On 10-4-2012 21:18, Johan Engelen wrote:
> Hi guys,
>    As a result from my changing the definition of isZero (a==0 to
> are_near) on Linear, a bug popped up in Inkscape:
> http://pastie.org/pastes/3763503/text?key=mj3yosx9rrc2xkqgzkow
>
> I fixed the issue in Inkscape rev 11212:
> http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/revision/11212

I created a bug, fixed in:
http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/revision/11214#src/2geom/sbasis.cpp

[Lib2geom-devel] isZero ...

[Johan E. <jbc...@sw...>]

Hi guys,
  As a result from my changing the definition of isZero (a==0 to 
are_near) on Linear, a bug popped up in Inkscape:
http://pastie.org/pastes/3763503/text?key=mj3yosx9rrc2xkqgzkow

I fixed the issue in Inkscape rev 11212:
http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/revision/11212

Please review and confirm that the fix is correct.

I am in doubt whether at the end of the for-loop,
     Pk.truncate(order);
     Qk.truncate(order);
     r.truncate(order);
should be followed by
     Pk.resize(order,Linear(0.));
     Qk.resize(order,Linear(0.));
     r.resize(order,Linear(0.));
Just to be absolutely sure they have the correct size. The bug happened 
because for some paths, a whole bunch of things were zero, causing 'sg' 
to be zero with zero order.

After this fix, we hit upon another exception, ...
lib2geom exception: Invariants violation (src/2geom/piecewise.h:144)

Note, everthing works fine when changing
    Linear::  inline bool isZero(double eps=EPSILON) const { return 
are_near(a[0], 0., eps) && are_near(a[1], 0., eps); }
to
   a[0]==0 && a[1]==0

Thanks,
   Johan

Re: [Lib2geom-devel] Error on warnings

[Krzysztof K. <twe...@gm...>]

W dniu 8 kwietnia 2012 21:08 użytkownik Johan Engelen
<jbc...@sw...> napisał:
> Hi all,
>  I am thinking about adding "-Werror" by default to our builds, in
> order to force us to fix all warnings. Many warnings signify errors, and
> I would like to have the enforcement of coding warning-free.
> Is there any good reason not to do -Werror ?

There is a bug in GCC 4.something that generates a spurious aliasing
rules violation warning on every use of boost::optional.

Regards, Krzysztof

[Lib2geom-devel] Error on warnings

[Johan E. <jbc...@sw...>]

Hi all,
  I am thinking about adding "-Werror" by default to our builds, in 
order to force us to fix all warnings. Many warnings signify errors, and 
I would like to have the enforcement of coding warning-free.
Is there any good reason not to do -Werror ?

Ciao,
   Johan

Re: [Lib2geom-devel] isZero and isConstant

[Nathan H. <nj...@nj...>]

On Fri, Mar 09, 2012 at 11:58:22PM +0100, Krzysztof Kosiński wrote:
> W dniu 5 marca 2012 00:34 użytkownik Nathan Hurst <nj...@nj...> napisał:
> > On Sun, Mar 04, 2012 at 07:01:50PM +0100, Johan Engelen wrote:
> >> Hi all,
> >>    I've just run into trouble with SBasis::isZero and isConstant.
> >> See e.g. linear.h, lines 75 and 76. Shouldn't the comparisons be
> >> "are_near" comparisons?
> >> For example:
> >>     inline bool isConstant(double eps=EPSILON) const { return
> >> are_near(a[0], a[1], eps); }
> >
> > I guess they should, though I wonder if we should have
> > isNearlyConstant?
> 
> This is not a good pattern. There are already many functions, such as
> hasZeroArea in Rect, that take an epsilon parameter despite having an
> "exact" name. I think using isSomething(0) is an acceptable notation
> for an exact check.

Ok, I agree.

njh

Re: [Lib2geom-devel] isZero and isConstant

[Krzysztof K. <twe...@gm...>]

W dniu 5 marca 2012 00:34 użytkownik Nathan Hurst <nj...@nj...> napisał:
> On Sun, Mar 04, 2012 at 07:01:50PM +0100, Johan Engelen wrote:
>> Hi all,
>>    I've just run into trouble with SBasis::isZero and isConstant.
>> See e.g. linear.h, lines 75 and 76. Shouldn't the comparisons be
>> "are_near" comparisons?
>> For example:
>>     inline bool isConstant(double eps=EPSILON) const { return
>> are_near(a[0], a[1], eps); }
>
> I guess they should, though I wonder if we should have
> isNearlyConstant?

This is not a good pattern. There are already many functions, such as
hasZeroArea in Rect, that take an epsilon parameter despite having an
"exact" name. I think using isSomething(0) is an acceptable notation
for an exact check.

Regards, Krzysztof

Re: [Lib2geom-devel] parallel build?

[Johan E. <jbc...@sw...>]

On 4-3-2012 16:34, Johan Engelen wrote:
> Hi all,
>     If you run "make -j 4", does that actually spawn parallel build
> processes?
> Here on Windows, it does not seem to do anything different than just
> "make" ...

I just found that "make -j" on Windows *does* work and builds 2geom 
pretty fast :)

Ciao,
   Johan

Re: [Lib2geom-devel] isZero and isConstant

[Nathan H. <nj...@nj...>]

On Sun, Mar 04, 2012 at 07:01:50PM +0100, Johan Engelen wrote:
> Hi all,
>    I've just run into trouble with SBasis::isZero and isConstant.
> See e.g. linear.h, lines 75 and 76. Shouldn't the comparisons be 
> "are_near" comparisons?
> For example:
>     inline bool isConstant(double eps=EPSILON) const { return 
> are_near(a[0], a[1], eps); }

I guess they should, though I wonder if we should have
isNearlyConstant?

njh

[Lib2geom-devel] isZero and isConstant

[Johan E. <jbc...@sw...>]

Hi all,
   I've just run into trouble with SBasis::isZero and isConstant.
See e.g. linear.h, lines 75 and 76. Shouldn't the comparisons be 
"are_near" comparisons?
For example:
    inline bool isConstant(double eps=EPSILON) const { return 
are_near(a[0], a[1], eps); }

Regards,
   Johan

[Lib2geom-devel] parallel build?

[Johan E. <jbc...@sw...>]

Hi all,
   If you run "make -j 4", does that actually spawn parallel build 
processes?
Here on Windows, it does not seem to do anything different than just 
"make" ...

Thanks,
   Johan

Re: [Lib2geom-devel] [Inkscape-devel] Fwd: Re: [CREATE] LGM 2012 workshop -- lib2geom

[Igor N. <igo...@gm...>]

Wow! Great!
I think you will have plenty of questions! lib2geom workshop of high demand.

-- 
Regards,

Igor Novikov
sK1 Project
http://sk1project.org

On Thu, Mar 1, 2012 at 12:51 PM, <jbc...@sw...> wrote:

> I just submitted a workshop request for LGM2012.
> Hope to see you (and hear your questions!) there.
>
> Cheers,
>  Johan
>
>
> ---- Jasper van de Gronde <th....@hc...> wrote:
> > This came up on the CREATE mailing list, and I'm not sure how many
> > people in Inkscape/lib2geom are reading that, so I'm forwarding it.
> > Basically it has been suggested that it might be a good idea to have a
> > lib2geom workshop at LGM, essentially to encourage people to use it
> > (outside of Inkscape).
> >
> > -------- Original Message --------
> > Subject: Re: [CREATE] LGM 2012 workshop -- lib2geom
> > Date: Thu, 1 Mar 2012 09:34:36 +0100
> > From: ale rimoldi <ale...@xo...>
> > To: cr...@li...
> >
> > hi
> >
> > > Would any of our fabulous graphics programmers like to
> > > have a workshop on using lib2geom at LGM?
> >
> > if somebody wants to make this true, he or she should submit a
> > proposal to
> >
> > http://libregraphicsmeeting.org/2012/submit-a-talk
> >
> > today!
> >
> > ciao
> > a.l.e
>
>
>
>
> ------------------------------------------------------------------------------
> Virtualization & Cloud Management Using Capacity Planning
> Cloud computing makes use of virtualization - but cloud computing
> also focuses on allowing computing to be delivered as a service.
> http://www.accelacomm.com/jaw/sfnl/114/51521223/
> _______________________________________________
> Inkscape-devel mailing list
> Ink...@li...
> https://lists.sourceforge.net/lists/listinfo/inkscape-devel
>

Re: [Lib2geom-devel] [Inkscape-devel] Fwd: Re: [CREATE] LGM 2012 workshop -- lib2geom

[<jbc...@sw...>]

I just submitted a workshop request for LGM2012.
Hope to see you (and hear your questions!) there.

Cheers,
  Johan


---- Jasper van de Gronde <th....@hc...> wrote: 
> This came up on the CREATE mailing list, and I'm not sure how many
> people in Inkscape/lib2geom are reading that, so I'm forwarding it.
> Basically it has been suggested that it might be a good idea to have a
> lib2geom workshop at LGM, essentially to encourage people to use it
> (outside of Inkscape).
> 
> -------- Original Message --------
> Subject: Re: [CREATE] LGM 2012 workshop -- lib2geom
> Date: Thu, 1 Mar 2012 09:34:36 +0100
> From: ale rimoldi <ale...@xo...>
> To: cr...@li...
> 
> hi
> 
> > Would any of our fabulous graphics programmers like to
> > have a workshop on using lib2geom at LGM?
> 
> if somebody wants to make this true, he or she should submit a
> proposal to
> 
> http://libregraphicsmeeting.org/2012/submit-a-talk
> 
> today!
> 
> ciao
> a.l.e

[Lib2geom-devel] Fwd: Re: [CREATE] LGM 2012 workshop -- lib2geom

[Jasper v. de G. <th....@hc...>]

This came up on the CREATE mailing list, and I'm not sure how many
people in Inkscape/lib2geom are reading that, so I'm forwarding it.
Basically it has been suggested that it might be a good idea to have a
lib2geom workshop at LGM, essentially to encourage people to use it
(outside of Inkscape).

-------- Original Message --------
Subject: Re: [CREATE] LGM 2012 workshop -- lib2geom
Date: Thu, 1 Mar 2012 09:34:36 +0100
From: ale rimoldi <ale...@xo...>
To: cr...@li...

hi

> Would any of our fabulous graphics programmers like to
> have a workshop on using lib2geom at LGM?

if somebody wants to make this true, he or she should submit a
proposal to

http://libregraphicsmeeting.org/2012/submit-a-talk

today!

ciao
a.l.e
_______________________________________________
CREATE mailing list
CR...@li...
http://lists.freedesktop.org/mailman/listinfo/create

Re: [Lib2geom-devel] Reflect transform

[Johan E. <jbc...@sw...>]

On 25-2-2012 20:32, Krzysztof Kosiński wrote:
> Hello
>
> I saw that a Reflect transform was added to 2geom recently. It does
> not satisfy the requirements of TransformConcept:
> 1. Reflect * Reflect != Reflect (in fact there is no multiplication
> operator at all)
> 2. There is no identity element.
>
> Transforms are intended to be subgroups of Affine. Reflections are not
> a subgroup, so they should not be represented as a transform class.
> Instead, a function called Geom::reflection should return an Affine
> that represents the requested reflection.

Ah yes, I see I was way to quick in creating a whole class out of it.

Thanks for keeping me in check!

Fixed,
   Johan

[Lib2geom-devel] Reflect transform

[Krzysztof K. <twe...@gm...>]

Hello

I saw that a Reflect transform was added to 2geom recently. It does
not satisfy the requirements of TransformConcept:
1. Reflect * Reflect != Reflect (in fact there is no multiplication
operator at all)
2. There is no identity element.

Transforms are intended to be subgroups of Affine. Reflections are not
a subgroup, so they should not be represented as a transform class.
Instead, a function called Geom::reflection should return an Affine
that represents the requested reflection.

Regards, Krzysztof