lib2geom-devel — development discussion

[Lib2geom-devel] 2Geom_trunk_scan-build - Build # 41 - Failure!

[Jenkins (b. tester) <ink...@gm...>]

Hi developers,
  I found a problem with one of the builds:
2Geom_trunk_scan-build - Build # 41 - Failure:

Check console output at http://jenkins.inkscape.org/job/2Geom_trunk_scan-build/41/ to view the results.

Your friend,
  Jenkins
  http://jenkins.inkscape.org

Re: [Lib2geom-devel] https://bugs.launchpad.net/inkscape/+bug/1482806

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

Okay, I'll get this patched then.

2015-08-13 16:39 GMT+02:00 Alvin Penner <pe...@va...>:
> Sounds like a good idea, a somewhat similar problem occurred recently in
> https://bugs.launchpad.net/inkscape/+bug/1473317
>
> Unfortunately, I don't know how to actually do this. My C programming skills
> are limited to microprocessors that are 15 years old and still use integer
> arithmetic.
>
> Alvin
>
>
> At 08:50 AM 8/13/2015, Krzysztof Kosiński wrote:
>>
>> Instead of changing the unary minus operator, the default constructor
>> for SBasis should be changed so that it creates an SBasis that is
>> identically zero (i.e. contains only one Linear(0, 0)). Null values
>> should not be representable in the SBasis object, and there should
>> assertions everywhere verifying that there is at least one element; no
>> member functions should ever remove the last Linear.
>>
>> Regards, Krzysztof
>>
>> 2015-08-13 2:11 GMT+02:00 Alvin Penner <pe...@va...>:
>> > Hi,
>> >         this is a request for comment on a proposed fix for Bug 1482806.
>> > The
>> > bug is apparently caused by returning a null value when attempting to
>> > take the unary negative of an sbasis which is zero. The proposed code
>> > returns the original sbasis instead. Any comments on whether this is
>> > acceptable? The code is fairly deeply embedded, so it may have
>> > implications elsewhere.
>> >
>> > Alvin Penner
>> >
>> >
>> >
>> > ------------------------------------------------------------------------------
>> > _______________________________________________
>> > Lib2geom-devel mailing list
>> > Lib...@li...
>> > https://lists.sourceforge.net/lists/listinfo/lib2geom-devel
>
>

Re: [Lib2geom-devel] https://bugs.launchpad.net/inkscape/+bug/1482806

[Alvin P. <pe...@va...>]

Sounds like a good idea, a somewhat similar problem occurred recently in
https://bugs.launchpad.net/inkscape/+bug/1473317

Unfortunately, I don't know how to actually do 
this. My C programming skills are limited to 
microprocessors that are 15 years old and still use integer arithmetic.

Alvin

At 08:50 AM 8/13/2015, Krzysztof Kosiński wrote:
>Instead of changing the unary minus operator, the default constructor
>for SBasis should be changed so that it creates an SBasis that is
>identically zero (i.e. contains only one Linear(0, 0)). Null values
>should not be representable in the SBasis object, and there should
>assertions everywhere verifying that there is at least one element; no
>member functions should ever remove the last Linear.
>
>Regards, Krzysztof
>
>2015-08-13 2:11 GMT+02:00 Alvin Penner <pe...@va...>:
> > Hi,
> >         this is a request for comment on a 
> proposed fix for Bug 1482806. The
> > bug is apparently caused by returning a null value when attempting to
> > take the unary negative of an sbasis which is zero. The proposed code
> > returns the original sbasis instead. Any comments on whether this is
> > acceptable? The code is fairly deeply embedded, so it may have
> > implications elsewhere.
> >
> > Alvin Penner
> >
> >
> > 
> ------------------------------------------------------------------------------
> > _______________________________________________
> > Lib2geom-devel mailing list
> > Lib...@li...
> > https://lists.sourceforge.net/lists/listinfo/lib2geom-devel

Re: [Lib2geom-devel] https://bugs.launchpad.net/inkscape/+bug/1482806

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

Instead of changing the unary minus operator, the default constructor
for SBasis should be changed so that it creates an SBasis that is
identically zero (i.e. contains only one Linear(0, 0)). Null values
should not be representable in the SBasis object, and there should
assertions everywhere verifying that there is at least one element; no
member functions should ever remove the last Linear.

Regards, Krzysztof

2015-08-13 2:11 GMT+02:00 Alvin Penner <pe...@va...>:
> Hi,
>         this is a request for comment on a proposed fix for Bug 1482806. The
> bug is apparently caused by returning a null value when attempting to
> take the unary negative of an sbasis which is zero. The proposed code
> returns the original sbasis instead. Any comments on whether this is
> acceptable? The code is fairly deeply embedded, so it may have
> implications elsewhere.
>
> Alvin Penner
>
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Lib2geom-devel mailing list
> Lib...@li...
> https://lists.sourceforge.net/lists/listinfo/lib2geom-devel

[Lib2geom-devel] https://bugs.launchpad.net/inkscape/+bug/1482806

[Alvin P. <pe...@va...>]

Hi,
	this is a request for comment on a proposed fix for Bug 1482806. The 
bug is apparently caused by returning a null value when attempting to 
take the unary negative of an sbasis which is zero. The proposed code 
returns the original sbasis instead. Any comments on whether this is 
acceptable? The code is fairly deeply embedded, so it may have 
implications elsewhere.

Alvin Penner

Re: [Lib2geom-devel] [Inkscape-devel] Boolops progress

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

Not much to report unfortunately - I was taking care of final exams
for the past ~3 weeks.

Right now my first Inkscape-related priority is to finally commit the
2Geom sync, to avoid any further bitrot; then I will implement
handling of overlapping segments, and after that - attempt to
implement the conversion from nonzero fills to even-odd fills.

Regards, Krzysztof

2015-07-03 10:32 GMT+02:00 Tavmjong Bah <tav...@fr...>:
>
> Any updates?
>
>
> On Mon, 2015-06-01 at 15:05 +0200, Krzysztof Kosiński wrote:
>> 2015-05-31 3:21 GMT+02:00 Nathan Hurst <nj...@nj...>:
>> > Did you come up with the mu intersection approach?  that's rather neat.
>>
>> Nope, I mostly copied that from this document. No point reinventing the wheel :)
>> http://maptools.home.comcast.net/~maptools/BivariateQuadratics.pdf
>>
>> It can still be improved a little - when two very thin and long
>> ellipses intersect at two points, the results of one of the
>> ellipse-line intersections will have much better accuracy, because the
>> resulting line intersects it at less shallow angles. I could pick the
>> ellipse where the cross product of the unit versor of the major axis
>> and the unit versor of the line is larger, but it's not yet obvious to
>> me that this always gives the better result.
>>
>> In any case, for now I'm focusing on how to solve the problem of
>> overlapping segments, since it's the only major thing missing from the
>> algorithm. Then I'll focus on testing various edge cases, and
>> conversion from nonzero to even-odd fill rules.
>>
>> > Your approach made me wonder whether there is a nice analytic solution
>> > for nearest_point for conic section pairs too.  Basically you want to
>> > find points with matched normals, which is, in your notation,
>> > mu dQ + dR = 0.
>>
>> The derivative of an ellipse is another ellipse at the origin, so it
>> would definitely be doable for ellipses. I'm not yet sure about other
>> conic sections.
>>
>> Regards, Krzysztof
>>
>> ------------------------------------------------------------------------------
>> _______________________________________________
>> Lib2geom-devel mailing list
>> Lib...@li...
>> https://lists.sourceforge.net/lists/listinfo/lib2geom-devel
>
>

Re: [Lib2geom-devel] [Inkscape-devel] Boolops progress

[Tavmjong B. <tav...@fr...>]

Any updates?


On Mon, 2015-06-01 at 15:05 +0200, Krzysztof Kosiński wrote:
> 2015-05-31 3:21 GMT+02:00 Nathan Hurst <nj...@nj...>:
> > Did you come up with the mu intersection approach?  that's rather neat.
> 
> Nope, I mostly copied that from this document. No point reinventing the wheel :)
> http://maptools.home.comcast.net/~maptools/BivariateQuadratics.pdf
> 
> It can still be improved a little - when two very thin and long
> ellipses intersect at two points, the results of one of the
> ellipse-line intersections will have much better accuracy, because the
> resulting line intersects it at less shallow angles. I could pick the
> ellipse where the cross product of the unit versor of the major axis
> and the unit versor of the line is larger, but it's not yet obvious to
> me that this always gives the better result.
> 
> In any case, for now I'm focusing on how to solve the problem of
> overlapping segments, since it's the only major thing missing from the
> algorithm. Then I'll focus on testing various edge cases, and
> conversion from nonzero to even-odd fill rules.
> 
> > Your approach made me wonder whether there is a nice analytic solution
> > for nearest_point for conic section pairs too.  Basically you want to
> > find points with matched normals, which is, in your notation,
> > mu dQ + dR = 0.
> 
> The derivative of an ellipse is another ellipse at the origin, so it
> would definitely be doable for ellipses. I'm not yet sure about other
> conic sections.
> 
> Regards, Krzysztof
> 
> ------------------------------------------------------------------------------
> _______________________________________________
> Lib2geom-devel mailing list
> Lib...@li...
> https://lists.sourceforge.net/lists/listinfo/lib2geom-devel

Re: [Lib2geom-devel] Maximum distance between curves

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

I think I had a response to your earlier post but I don't think I ever
sent it.  Anyway, looks promising.  Why not implement it and we can
see how well it performs in practice.  That's always the real test :)

If you can get a reasonably tight bound root polishing will work well.

roots() is very fast for low order polynomials (e.g. cubic) btw (100 ns).  I
would suggest transforming problems into roots() and benchmarking
before spending time on other approaches, as it's very hard to beat.

hausdorf distance turns out to be a bad measure for curve comparison
because it induces zigzags.
https://en.wikipedia.org/wiki/Fr%C3%A9chet_distance is much better in
this regard.

I might be missing something, but you are computing and approximation
of argmin_t |p(t) - q(t)|, but what you actually need is argmin_{s,t}
|p(s) - q(t)|.  Consider a line broken into two touching segments:
although the distance is 0, your algorithm will find the distance to
be the length of the curve.  This could be solved with some kind of
subdivision algorithm, but then you're back to the frechet polygon
problem, with bounds.

njh

On Wed, Jun 03, 2015 at 04:10:11PM +0200, Alexander Brock wrote:
> On 07/04/15 10:51, Alexander Brock wrote:
> > https://github.com/abrock/optimization (I'll give push rights to anyone
> > who asks)
> 
> I have two new estimations of the maximum distance, both do not depend
> on finding roots of polynomials (sections 0.3 and 0.4).
> 
> Regards
> Alexander
> 
> ------------------------------------------------------------------------------
> _______________________________________________
> Lib2geom-devel mailing list
> Lib...@li...
> https://lists.sourceforge.net/lists/listinfo/lib2geom-devel

Re: [Lib2geom-devel] Maximum distance between curves

[Alexander B. <Bro...@we...>]

On 07/04/15 10:51, Alexander Brock wrote:
> https://github.com/abrock/optimization (I'll give push rights to anyone
> who asks)

I have two new estimations of the maximum distance, both do not depend
on finding roots of polynomials (sections 0.3 and 0.4).

Regards
Alexander

Re: [Lib2geom-devel] [Inkscape-devel] Boolops progress

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

2015-05-31 3:21 GMT+02:00 Nathan Hurst <nj...@nj...>:
> Did you come up with the mu intersection approach?  that's rather neat.

Nope, I mostly copied that from this document. No point reinventing the wheel :)
http://maptools.home.comcast.net/~maptools/BivariateQuadratics.pdf

It can still be improved a little - when two very thin and long
ellipses intersect at two points, the results of one of the
ellipse-line intersections will have much better accuracy, because the
resulting line intersects it at less shallow angles. I could pick the
ellipse where the cross product of the unit versor of the major axis
and the unit versor of the line is larger, but it's not yet obvious to
me that this always gives the better result.

In any case, for now I'm focusing on how to solve the problem of
overlapping segments, since it's the only major thing missing from the
algorithm. Then I'll focus on testing various edge cases, and
conversion from nonzero to even-odd fill rules.

> Your approach made me wonder whether there is a nice analytic solution
> for nearest_point for conic section pairs too.  Basically you want to
> find points with matched normals, which is, in your notation,
> mu dQ + dR = 0.

The derivative of an ellipse is another ellipse at the origin, so it
would definitely be doable for ellipses. I'm not yet sure about other
conic sections.

Regards, Krzysztof

Re: [Lib2geom-devel] [Inkscape-devel] Boolops progress

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

Did you come up with the mu intersection approach?  that's rather neat.

Your approach made me wonder whether there is a nice analytic solution
for nearest_point for conic section pairs too.  Basically you want to
find points with matched normals, which is, in your notation, 
mu dQ + dR = 0.

njh

On Sat, May 23, 2015 at 03:26:00PM +0200, Krzysztof Kosiński wrote:
> Another update:
> 
> Boolops are now working correctly with elliptical arc segments. I will
> now work on ensuring that degenerate cases give sensible results.
> 
> A big remaining gap is the handling of nonzero-fill shapes. The best
> way to handle them will be to convert them to even-odd fill rule
> first. This will require adding a new method that checks whether an
> edge is inside or outside (I have this figured out) and methods that
> find self-intersections on Bezier curves of order 3 and higher (This
> is straightforward).
> 
> In the process, I fleshed out several classes, such as Ellipse and
> Circle, and added some new functionality to Line and AngleInterval.
> 
> The following intersection combinations are now implemented. Each of
> these methods returns std::vector of appropriate intersection
> structures that contain two time values and a cached intersection
> point that can be more precise than direct evaluation.
> 
> - Line - Line
> - Line - LineSegment
> - Line - Ray
> - LineSegment - LineSegment
> - LineSegment - BezierCurve
> - LineSegment - EllipticalArc
> - BezierCurve - LineSegment
> - BezierCurve - EllipticalArc
> - BezierCurve - BezierCurve
> - EllipticalArc - LineSegment
> - EllipticalArc - BezierCurve
> - EllipticalArc - EllipticalArc
> - Circle - Line
> - Circle - LineSegment
> - Circle - Circle
> - Ellipse - Line
> - Ellipse - LineSegment
> - Ellipse - Ellipse
> - Ellipse - D2<Bezier>
> 
> The code used for ellipse intersection is analytic and should
> generalize to other conic sections - it can be moved to the conic
> section class once conicsec.h is refactored. I'm also considering
> creating classes such as LineEquation, CircleEquation and
> EllipseEquation to store the implicit representation of those shapes.
> 
> Regards, Krzysztof
> 
> 2015-04-26 6:10 GMT+02:00 Nathan Hurst <nj...@nj...>:
> > On Mon, Apr 20, 2015 at 02:18:36PM +0200, Krzysztof Kosiński wrote:
> >> 2015-04-20 7:15 GMT+02:00 Nathan Hurst <nj...@nj...>:
> >> >> - Linear and Bezier segments of arbitrary degree
> >> >> - Code is fairly clean and understandable
> >> >> - Reasonably good performance, even though there are very few
> >> >> optimizations
> >> >
> >> > This is almost certainly an improvement on what we have, to gain
> >> > confidence can you also write some unit tests that capture the various
> >> > edge cases as per that svg (and anything else you can think of).
> >>
> >> The results will be slightly different than in that SVG, because the
> >> algorithm I used does not require uncrossing as a preprocessing step.
> >> I think this is a nice feature, since it preserves self-intersections
> >> in places where they don't affect the result. I wrote a short summary
> >> of the underlying algorithm on Wikipedia recently:
> >> https://en.wikipedia.org/wiki/Greiner%E2%80%93Hormann_clipping_algorithm
> >
> > Nice!
> >
> >> For the arc-Bezier case, my thesis advisor suggested to convert
> >> elliptical arcs to four rational quadratic Beziers, each representing
> >> 1/4 of the ellipse between its conjugate diameters and intersect that
> >> using well known algorithms, then go back to the elliptical arc
> >> representation by using the fact that the weight of the middle control
> >> point is related to the time on the elliptical arc (the angle in the
> >> untransformed unit circle). I'm not sure about this. I'll first try
> >> the conic equation route, since it's the simplest and requires minimal
> >> new code.
> >
> > Yeah, I think that is wise.  I'd forgotten about rational beziers
> > representing conics.
> >
> >> The conic code implements some interesting stuff that I could use, but
> >> it needs to be refactored first. I'm pretty certain that If I hadn't
> >> spent substantial time on refactoring, writing unit tests for existing
> >> stuff and fixing the uncovered bugs, I wouldn't have managed to get
> >> this far.
> >
> > Yes, this work has desperately need to be done.  I didn't grok the
> > value of unit tests when I wrote the initial code.  Now I do.  Please
> > refactor and unit test, it will make the library so much more
> > trustworthy.
> >
> > njh

Re: [Lib2geom-devel] [Inkscape-devel] Boolops progress

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

Another update:

Boolops are now working correctly with elliptical arc segments. I will
now work on ensuring that degenerate cases give sensible results.

A big remaining gap is the handling of nonzero-fill shapes. The best
way to handle them will be to convert them to even-odd fill rule
first. This will require adding a new method that checks whether an
edge is inside or outside (I have this figured out) and methods that
find self-intersections on Bezier curves of order 3 and higher (This
is straightforward).

In the process, I fleshed out several classes, such as Ellipse and
Circle, and added some new functionality to Line and AngleInterval.

The following intersection combinations are now implemented. Each of
these methods returns std::vector of appropriate intersection
structures that contain two time values and a cached intersection
point that can be more precise than direct evaluation.

- Line - Line
- Line - LineSegment
- Line - Ray
- LineSegment - LineSegment
- LineSegment - BezierCurve
- LineSegment - EllipticalArc
- BezierCurve - LineSegment
- BezierCurve - EllipticalArc
- BezierCurve - BezierCurve
- EllipticalArc - LineSegment
- EllipticalArc - BezierCurve
- EllipticalArc - EllipticalArc
- Circle - Line
- Circle - LineSegment
- Circle - Circle
- Ellipse - Line
- Ellipse - LineSegment
- Ellipse - Ellipse
- Ellipse - D2<Bezier>

The code used for ellipse intersection is analytic and should
generalize to other conic sections - it can be moved to the conic
section class once conicsec.h is refactored. I'm also considering
creating classes such as LineEquation, CircleEquation and
EllipseEquation to store the implicit representation of those shapes.

Regards, Krzysztof

2015-04-26 6:10 GMT+02:00 Nathan Hurst <nj...@nj...>:
> On Mon, Apr 20, 2015 at 02:18:36PM +0200, Krzysztof Kosiński wrote:
>> 2015-04-20 7:15 GMT+02:00 Nathan Hurst <nj...@nj...>:
>> >> - Linear and Bezier segments of arbitrary degree
>> >> - Code is fairly clean and understandable
>> >> - Reasonably good performance, even though there are very few
>> >> optimizations
>> >
>> > This is almost certainly an improvement on what we have, to gain
>> > confidence can you also write some unit tests that capture the various
>> > edge cases as per that svg (and anything else you can think of).
>>
>> The results will be slightly different than in that SVG, because the
>> algorithm I used does not require uncrossing as a preprocessing step.
>> I think this is a nice feature, since it preserves self-intersections
>> in places where they don't affect the result. I wrote a short summary
>> of the underlying algorithm on Wikipedia recently:
>> https://en.wikipedia.org/wiki/Greiner%E2%80%93Hormann_clipping_algorithm
>
> Nice!
>
>> For the arc-Bezier case, my thesis advisor suggested to convert
>> elliptical arcs to four rational quadratic Beziers, each representing
>> 1/4 of the ellipse between its conjugate diameters and intersect that
>> using well known algorithms, then go back to the elliptical arc
>> representation by using the fact that the weight of the middle control
>> point is related to the time on the elliptical arc (the angle in the
>> untransformed unit circle). I'm not sure about this. I'll first try
>> the conic equation route, since it's the simplest and requires minimal
>> new code.
>
> Yeah, I think that is wise.  I'd forgotten about rational beziers
> representing conics.
>
>> The conic code implements some interesting stuff that I could use, but
>> it needs to be refactored first. I'm pretty certain that If I hadn't
>> spent substantial time on refactoring, writing unit tests for existing
>> stuff and fixing the uncovered bugs, I wouldn't have managed to get
>> this far.
>
> Yes, this work has desperately need to be done.  I didn't grok the
> value of unit tests when I wrote the initial code.  Now I do.  Please
> refactor and unit test, it will make the library so much more
> trustworthy.
>
> njh

Re: [Lib2geom-devel] Lib2geom-devel Digest, Vol 68, Issue 1

[Jabier A. <jab...@ma...>]

Great! I can focus in my current work in "switch" code.

Regards, Jabier.


On Wed, 2015-05-20 at 15:06 +0200, Krzysztof Kosiński wrote:
> 2015-05-19 21:33 GMT+02:00 Jabiertxo Arraiza Cenoz <jab...@ma...>:
> > El sáb, 16-05-2015 a las 08:15 +0000,
> > lib...@li... escribió:
> >> > What works:
> >> > - Union
> >> > - Intersection
> >> > - Adding difference and XOR is trivial
> >>
> >> Perhaps someone else could implement them as a learn-the-code
> >> experience, Jabier?
> >
> > Hi Nathan. Not sure if my basic math could do it but i could try. Still
> > on TODO?
> >
> > Regards, Jabier.
> 
> I went ahead and added those already, sorry :(
> 
> Boolops should be complete now, with the exception of handling
> degenerate cases such as overlapping segments and nodes exactly at
> segments. I will be working on that next.
> 
> Regards, Krzysztof

Re: [Lib2geom-devel] Lib2geom-devel Digest, Vol 68, Issue 1

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

2015-05-19 21:33 GMT+02:00 Jabiertxo Arraiza Cenoz <jab...@ma...>:
> El sáb, 16-05-2015 a las 08:15 +0000,
> lib...@li... escribió:
>> > What works:
>> > - Union
>> > - Intersection
>> > - Adding difference and XOR is trivial
>>
>> Perhaps someone else could implement them as a learn-the-code
>> experience, Jabier?
>
> Hi Nathan. Not sure if my basic math could do it but i could try. Still
> on TODO?
>
> Regards, Jabier.

I went ahead and added those already, sorry :(

Boolops should be complete now, with the exception of handling
degenerate cases such as overlapping segments and nodes exactly at
segments. I will be working on that next.

Regards, Krzysztof

Re: [Lib2geom-devel] Lib2geom-devel Digest, Vol 68, Issue 1

[Jabiertxo A. C. <jab...@ma...>]

El sáb, 16-05-2015 a las 08:15 +0000,
lib...@li... escribió:
> > What works:
> > - Union
> > - Intersection
> > - Adding difference and XOR is trivial
> 
> Perhaps someone else could implement them as a learn-the-code
> experience, Jabier?

Hi Nathan. Not sure if my basic math could do it but i could try. Still
on TODO?

Regards, Jabier.

[Lib2geom-devel] 2Geom_trunk_scan-build - Build # 28 - Failure!

[Jenkins (b. tester) <ink...@gm...>]

Hi developers,
  I found a problem with one of the builds:
2Geom_trunk_scan-build - Build # 28 - Failure:

Check console output at http://jenkins.inkscape.org/job/2Geom_trunk_scan-build/28/ to view the results.

Your friend,
  Jenkins
  http://jenkins.inkscape.org

[Lib2geom-devel] 2Geom_trunk_unittests - Build # 22 - Failure!

[Jenkins (b. tester) <ink...@gm...>]

Hi developers,
  I found a problem with one of the builds:
2Geom_trunk_unittests - Build # 22 - Failure:

Check console output at http://jenkins.inkscape.org/job/2Geom_trunk_unittests/22/ to view the results.

Your friend,
  Jenkins
  http://jenkins.inkscape.org

Re: [Lib2geom-devel] [Inkscape-devel] Boolops progress

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

On Mon, Apr 20, 2015 at 02:18:36PM +0200, Krzysztof Kosiński wrote:
> 2015-04-20 7:15 GMT+02:00 Nathan Hurst <nj...@nj...>:
> >> - Linear and Bezier segments of arbitrary degree
> >> - Code is fairly clean and understandable
> >> - Reasonably good performance, even though there are very few
> >> optimizations
> >
> > This is almost certainly an improvement on what we have, to gain
> > confidence can you also write some unit tests that capture the various
> > edge cases as per that svg (and anything else you can think of).
> 
> The results will be slightly different than in that SVG, because the
> algorithm I used does not require uncrossing as a preprocessing step.
> I think this is a nice feature, since it preserves self-intersections
> in places where they don't affect the result. I wrote a short summary
> of the underlying algorithm on Wikipedia recently:
> https://en.wikipedia.org/wiki/Greiner%E2%80%93Hormann_clipping_algorithm

Nice!

> For the arc-Bezier case, my thesis advisor suggested to convert
> elliptical arcs to four rational quadratic Beziers, each representing
> 1/4 of the ellipse between its conjugate diameters and intersect that
> using well known algorithms, then go back to the elliptical arc
> representation by using the fact that the weight of the middle control
> point is related to the time on the elliptical arc (the angle in the
> untransformed unit circle). I'm not sure about this. I'll first try
> the conic equation route, since it's the simplest and requires minimal
> new code.

Yeah, I think that is wise.  I'd forgotten about rational beziers
representing conics.

> The conic code implements some interesting stuff that I could use, but
> it needs to be refactored first. I'm pretty certain that If I hadn't
> spent substantial time on refactoring, writing unit tests for existing
> stuff and fixing the uncovered bugs, I wouldn't have managed to get
> this far.

Yes, this work has desperately need to be done.  I didn't grok the
value of unit tests when I wrote the initial code.  Now I do.  Please
refactor and unit test, it will make the library so much more
trustworthy.

njh

Re: [Lib2geom-devel] [Inkscape-devel] Boolops progress

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

2015-04-20 7:15 GMT+02:00 Nathan Hurst <nj...@nj...>:
>> - Linear and Bezier segments of arbitrary degree
>> - Code is fairly clean and understandable
>> - Reasonably good performance, even though there are very few
>> optimizations
>
> This is almost certainly an improvement on what we have, to gain
> confidence can you also write some unit tests that capture the various
> edge cases as per that svg (and anything else you can think of).

The results will be slightly different than in that SVG, because the
algorithm I used does not require uncrossing as a preprocessing step.
I think this is a nice feature, since it preserves self-intersections
in places where they don't affect the result. I wrote a short summary
of the underlying algorithm on Wikipedia recently:
https://en.wikipedia.org/wiki/Greiner%E2%80%93Hormann_clipping_algorithm

My modification is different in that it evaluates the even-odd rule
for every portion between two intersections. However, the extra
robustness this gives isn't used yet. I could have simply assigned
alternating flags like in the original algorithm, but at least now I
know that doing it this way won't be prohibitively expensive.

>> What remains to be done:
>> - Could be simplified a bit and better documented.
>> - Intersection procedures for arc-arc and arc-Bezier cases. Currently
>> they throw UnimplementedError.
>
> Two directions to consider:
>
> use the implicit formula for conics (AX^2 + BXY + CY^2 + DX + EY + F =
> 0) that we have code to generate, then substitute in the bezier for X,
> Y, and use roots().  This will double the degree of the curve, but
> should be quite stable.
>
> Or you could try and write something similar to bezier clipping
> algorithm by projecting a linear approximation of the bezier against
> the ellipse or vice versa.  More fiddly but potentially more accurate.
>
> Intersecting conics is already in 2geom I think.

For the arc-Bezier case, my thesis advisor suggested to convert
elliptical arcs to four rational quadratic Beziers, each representing
1/4 of the ellipse between its conjugate diameters and intersect that
using well known algorithms, then go back to the elliptical arc
representation by using the fact that the weight of the middle control
point is related to the time on the elliptical arc (the angle in the
untransformed unit circle). I'm not sure about this. I'll first try
the conic equation route, since it's the simplest and requires minimal
new code.

The conic code implements some interesting stuff that I could use, but
it needs to be refactored first. I'm pretty certain that If I hadn't
spent substantial time on refactoring, writing unit tests for existing
stuff and fixing the uncovered bugs, I wouldn't have managed to get
this far.

Regards, Krzysztof

Re: [Lib2geom-devel] [Inkscape-devel] Boolops progress

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

I'm very impressed.  For the other readers out there, this is a
problem that has stumped a long line of very smart people (including
professional mathematicians and academia) and CGAL, a widely cited
geometry library, has a broken implementation.  This is a surprisingly
hard problem to solve correctly.  I agree it's publication worthy.

More importantly, this is not some theoretically wonderful
implementation, this is a working, practical implementation.

It also enables many interesting other tools which have either had to
work around the existing broken boolops, or have had hacks to
approximate sepecial cases.  Being both fast and robust makes so
many things practical.

On Mon, Apr 20, 2015 at 02:04:32AM +0200, Krzysztof Kosiński wrote:
> There is a new toy "boolops-new" in 2Geom's source repository - it
> computes an union of two paths using my new boolops code based on the
> Greiner-Hormann algorithm.
> 
> What works:
> - Union
> - Intersection
> - Adding difference and XOR is trivial

Perhaps someone else could implement them as a learn-the-code
experience, Jabier?

> - Linear and Bezier segments of arbitrary degree
> - Code is fairly clean and understandable
> - Reasonably good performance, even though there are very few
> optimizations

This is almost certainly an improvement on what we have, to gain
confidence can you also write some unit tests that capture the various
edge cases as per that svg (and anything else you can think of).

> What remains to be done:
> - Could be simplified a bit and better documented.
> - Intersection procedures for arc-arc and arc-Bezier cases. Currently
> they throw UnimplementedError.

Two directions to consider:

use the implicit formula for conics (AX^2 + BXY + CY^2 + DX + EY + F =
0) that we have code to generate, then substitute in the bezier for X,
Y, and use roots().  This will double the degree of the curve, but
should be quite stable.

Or you could try and write something similar to bezier clipping
algorithm by projecting a linear approximation of the bezier against
the ellipse or vice versa.  More fiddly but potentially more accurate.

Intersecting conics is already in 2geom I think.

> - Handling of degeneracies and second-order intersections. I have this
> mostly planned out, except for a few nasty cases with overlapping
> Bezier segments.

Also useful are the various combinations with 1d topology - given
paths A and B it is useful to compute the set ops between A*B, dA*B
and dA*dB (where d refers to the outline).  This code implements A*B,
and we already have dA*dB.

> - Add &, |, / operators to PathVector. I think / will be better than
> minus for set subtraction.

Agreed.  It's sets, not arithmetic.

> - Function that converts a nonzero winding pathvector to even-odd
> winding pathvector with the same filled areas. It's a lot easier to do
> this conversion than it is to do Booleans on nonzero winding fills.

And uncross.

> I observed no crashes or hangs, though when two pathvectors overlap
> exactly, some paths can be skipped in the output.

Yep, my inextensive testing with the toy also didn't crash (or
suddenly take mysterious amounts of time).

> Since this code is already a lot better than the old attempts present
> in 2Geom (path-intersection.h, shape.h, region.h and the like), I'm
> going to remove them to reduce cruft.

Please do!

Very exciting work!

njh

[Lib2geom-devel] Boolops progress

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

There is a new toy "boolops-new" in 2Geom's source repository - it
computes an union of two paths using my new boolops code based on the
Greiner-Hormann algorithm.

What works:
- Union
- Intersection
- Adding difference and XOR is trivial
- Linear and Bezier segments of arbitrary degree
- Code is fairly clean and understandable
- Reasonably good performance, even though there are very few optimizations

What remains to be done:
- Could be simplified a bit and better documented.
- Intersection procedures for arc-arc and arc-Bezier cases. Currently
they throw UnimplementedError.
- Handling of degeneracies and second-order intersections. I have this
mostly planned out, except for a few nasty cases with overlapping
Bezier segments.
- Add &, |, / operators to PathVector. I think / will be better than
minus for set subtraction.
- Function that converts a nonzero winding pathvector to even-odd
winding pathvector with the same filled areas. It's a lot easier to do
this conversion than it is to do Booleans on nonzero winding fills.

I observed no crashes or hangs, though when two pathvectors overlap
exactly, some paths can be skipped in the output.

Since this code is already a lot better than the old attempts present
in 2Geom (path-intersection.h, shape.h, region.h and the like), I'm
going to remove them to reduce cruft.

Regards, Krzysztof

Re: [Lib2geom-devel] Maximum distance between curves

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

2015-04-07 22:28 GMT+02:00 Nathan Hurst <nj...@nj...>:
> I've attached a collection of cases that mentalguy came up with (along
> with an algorithm which is not too dissimilar to what you are
> proposing :)

Seems to me that Mental's idea for boolops was based on the
Weiler-Atherton algorithm, which uses the invariant that the inside is
always in the direction of on of the normals (the left one or the
right one). I use a modified Greiner-Hormann algorithm, which assumes
that shapes have even-odd winding and does not need the uncrossing
step. I have a suspicion that my modified version may also work for
nonzero winding shapes, but I'll have to verify this.

I also know of a modification of this algorithm that correctly solves
all possible degenerate cases for polygons, but it doesn't generalize
to curves.

Regards, Krzysztof

Re: [Lib2geom-devel] Maximum distance between curves

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

On Tue, Apr 07, 2015 at 09:33:44PM +0200, Krzysztof Kosiński wrote:

> Another idea I had is to somehow use the fact that Bezier curves are
> polynomial. It is well known that if two polynomials of degree n are
> equal at n+1 points, then they are equal everywhere. Perhaps this
> observation can be generalized to images of Bezier curves. It's very
> easy to see that this is the case for linear segments: if the
> endpoints of two linear segments are no further than delta apart, then
> no point on one segment is further than delta away from the nearest
> point on the other segment.

This is true for beziers because of the variation diminishing
property.  It is used for interval beziers.

> It's also true if the corresponding control points of Bezier curves
> are no further than delta away, but unfortunately the converse does
> not hold, i.e. there are some curves of equal images which have
> completely different control points.

Yes.

> Intuitively, it seems to me that the 'problematic' curves, such as
> Bezier curves with image equal to a line segment, may all be
> "redundant"; i.e. they can be represented exactly by a Bezier curve of
> lower degree.

You can transform any bezier into a higher order (only) by composing
with another polynomial (which is what these linelike segments are).
I'm not sure from your description whether you are aware that two
curves can be equal with completely different control points (compose
with an arbitrary linear polynomial = portion()); though I'm sure you
realise it.  You are correct that all 'problematic' curves have a
common factor and hence are under-constrained/degenerate because of
http://en.wikipedia.org/wiki/B%C3%A9zout%27s_theorem (and thus can be
degree reduced).

To prove two parameteric polynomial curves are equal requires sampling
at degree+1 points.  I think for bernstein basis the best points are
equaly spaced, as per
http://en.wikipedia.org/wiki/Bernstein_polynomial uniform
approximation theory.

> From the practical standpoint, I may be overthinking this - maybe I
> should just detect the most obvious cases, such as nearly-linear
> Bezier curves, and ignore the rest. I could simply use Alexander's
> idea b) and test the control points for nearness.

Thats certainly an excellent starting point - it should work in many
useful cases, and could potentially avoid a lot of expensive
numerics.  subdivision algorithms are generally very robust.  Do you
have a test set?

I've attached a collection of cases that mentalguy came up with (along
with an algorithm which is not too dissimilar to what you are
proposing :)

njh
p.s. I'm delighted you're working on this again :)

Re: [Lib2geom-devel] Maximum distance between curves

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

2015-04-07 10:51 GMT+02:00 Alexander Brock <Bro...@we...>:
> On 30/03/15 04:25, Krzysztof Kosiński wrote:
>> For the new Boolean operations algorithm, I could use a routine which
>> calculates the following: Given two curves, or even better two
>> sequences of curves, find a time value on one of them that maximizes
>> the distance from the other. In other words, I want to find t on c1
>> such that the distance from c1.poinAt(t) to the nearest point on c2 is
>> maximal. It can be assumed that the endpoints of both curve sequences
>> are exactly equal.
>>
>> Is there some clever way to calculate this?
>>
>> I need this to determine whether the fragments of paths between two
>> intersections are sufficiently similar to one another that they can be
>> considered the same.
>
> Do I understand correctly that you don't actually need the exact
> distance but instead an algorithm which always gives one of the
> following two results would be sufficient?
> a) The curves are guaranteed to have a maximum distance of smaller than x
> b) The curves are guaranteed to have a maximum distance of greater (or
> equal) than x

Yes.

However, maybe there is a simpler solution. What my boolops does is
the following:
- Compute all intersections.
- For each portion of the path between two intersections, pick a time
value that is somewhere not on the edge of the corresponding time
value interval. Compute the corresponding point.
- Compute the winding number of the other path at that point.
- Use that information to determine whether the relevant segment will
be in the result or not.

This algorithm works correctly even if there are second-order intersections.

The winding computation may return random results if the point is
exactly on the edge of the path. The only cases where my modification
of the Greiner-Hormann algorithm fails are:
- Shapes have common edges.
- By accident, a time value is picked which lies exactly at a
second-order intersection, which was not reported in step 1 due to
numeric precision issues.

Therefore, I need some way to determine whether two portions of the
path are sufficiently similar to consider them a common edge. If they
are, I can determine whether to include them in the result based on
the winding results for the surrounding portions. Otherwise the result
of the Boolean operation might be incorrect for this edge. For
instance, unioning two paths with a common edge may result in a path
which still has two subpaths.

> b) Let's assume curve A is a single bezier segment and curve B composed
> of two bezier segments. Find the point Z on A which minimizes the
> distance between the curve A and the point on B where the first segment
> ends and the second starts. If that difference is greater than x you're
> finished.
> Otherwise decompose A at the point Z into two bezier segments which exactly
> represent A and use idea a).

I also had an idea of this kind, probably I will use this.

Another idea I had is to somehow use the fact that Bezier curves are
polynomial. It is well known that if two polynomials of degree n are
equal at n+1 points, then they are equal everywhere. Perhaps this
observation can be generalized to images of Bezier curves. It's very
easy to see that this is the case for linear segments: if the
endpoints of two linear segments are no further than delta apart, then
no point on one segment is further than delta away from the nearest
point on the other segment. It's also true if the corresponding
control points of Bezier curves are no further than delta away, but
unfortunately the converse does not hold, i.e. there are some curves
of equal images which have completely different control points.

Intuitively, it seems to me that the 'problematic' curves, such as
Bezier curves with image equal to a line segment, may all be
"redundant"; i.e. they can be represented exactly by a Bezier curve of
lower degree.

>From the practical standpoint, I may be overthinking this - maybe I
should just detect the most obvious cases, such as nearly-linear
Bezier curves, and ignore the rest. I could simply use Alexander's
idea b) and test the control points for nearness.

Regards, Krzysztof

Re: [Lib2geom-devel] Maximum distance between curves

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

On Tue, Apr 07, 2015 at 10:51:42AM +0200, Alexander Brock wrote:
> I have ideas:
> a) If the endpoints of the bezier _segments_ are identical things get a
> lot less complex. I experimented with two ideas on how to get an upper
> bound for the distance and wrote them both down. The second looks
> promising to me, it only involves calculating the roots of a square
> polynomial and the distances of the control points and gives you upper
> and lower bounds for the maximum distance.
> 
> b) Let's assume curve A is a single bezier segment and curve B composed
> of two bezier segments. Find the point Z on A which minimizes the
> distance between the curve A and the point on B where the first segment
> ends and the second starts. If that difference is greater than x you're
> finished.
> Otherwise decompose A at the point Z into two bezier segments which exactly
> represent A and use idea a).
> 
> c) Any two curves A and B which are exactly the same but composed
> differently can be decomposed into smaller bezier segments such that
> every segment in A' has an exactly equal corresponding segment in B'
> 
> https://github.com/abrock/optimization (I'll give push rights to anyone
> who asks)

Your pdf is written in terms of only $t$, but Krys needs argmin over
$t,s$ of $||P(t) - Q(s)||_2$.  If it were only 1 domain, transforming
the problem into root(Bezier) would be very fast and very robust.

I think your subdivsion approach has merit though.  It is very similar
to a common approach for computing
https://en.wikipedia.org/wiki/Fr%C3%A9chet_distance that uses dynamic
programming in the free space diagram.

There is some code written I think by Marco which gives minimum
distances.  From memory it worked by formulating the inter curve
extrema as normal matching, and hence being able to use bezier
clipping to efficiently find solutions.  But I also remember it being
quite slow.

The overall problem can be solved as dp over sequences of beziergons,
subdividing and potentially bounding using the curve-curve distance
once you are down to plausible pairs.  But I think this code exists :)

> One problem is that different control points can parameterize similar
> curves. Extreme example:

Yes, this single factor makes many otherwise simple problems very
difficult with parametric curves.  :(

As a result, I suspect that performing everything for boolops in the
implicit domain is a more tractable approach.  Especially with careful
bounding a la libaffa or interval bezier arithmetic.

njh