Boolean operations (WIP)

[Harikrishnan G.]

Finally after 136 rewrites, paper paths are now joining and intersecting each other!

Try out the Tests / Demo

And here is the source
The source is well commented (I hope! or else, just post here)

The source file  has a list of what is implemented so far and what is to be done.

--
hari

[Jürg Lehni]

Hey Hari,

Wow, that's really impressive! Thank you for your hard work on this. I will check it out more closely later today, but am confident that this will find it's way into the core shortly. I'd like to address the issue in #getIntersections() that causes you to call getNearestLocation. Without the need for that, speed should improve *a lot*!

So first we need to merge this, and the way to do so is by creating a pull request.

Please read through this to see the requirements for contributions, and make sure you sign the CLA:

https://github.com/paperjs/paper.js/#contributing
https://github.com/paperjs/paper.js/#contributor-license-agreement

Once we have a pull request, we can move all discussions there.

Sounds good?

Exciting!

Jürg

On Apr 18, 2013, at 06:30 , Harikrishnan G. <hari.e...@gmail.com> wrote:

>
>
> Finally after 136 rewrites, paper paths are now joining and intersecting each other!
>
>
>
>
>
>
>
>

> Try out the Tests / Demo
>
> And here is the source
> The source is well commented (I hope! or else, just post here)
>
> The source file has a list of what is implemented so far and what is to be done.
>
> --
> hari
>
>
>
>
>

> --
> You received this message because you are subscribed to the Google Groups "Paper.js" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to paperjs+u...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Jono Brandel]

Looks really awesome. Nice work!

--

http://jonobr1.com/

jonob...@gmail.com

[Harikrishnan G.]

Thanks guys!

@jLehni please don't bother about getNearestLocation. I rewrote that part, and I am not using CurveLocation objects anymore.
Speed improvements can happen, if we could merge few of the passes together (it's a multi pass operation, as you can see in the code.)

I would like to have the api something along the lines of:
var result = path1.add( path2 );
var result = path1.intersect( path2 );
var result = path1.subtract( path2 );
var result = path2.subtract( path2 );

(goes with the paperjs Point object operations, I guess. Please post suggestions!)

In order to do that I would add this to PathItem object (am I right?) and it can be inherited by Paths and CompoundPaths etc.
So, I am working on extending this to handle CompoundPaths as input and defining Subtract operations. This shouldn't take longer than a few weeks!
will keep you posted.
 
After that I can do a pull request! :)

[philip wasserman]

 

Hi

You  are awesome! :>  

Philip

[Jürg Lehni]

Hi Hari,

> @jLehni please don't bother about getNearestLocation. I rewrote that part, and I am not using CurveLocation objects anymore.

Interesting. Do you still use getIntersections() though? I was thinking that ideally it would be built on top of that and CurveLocation, to avoid duplicating code. How were you able to eliminate that? Is the new code online?

Also, there are some questions regarding coding style, scoping and other things that we should discuss when you're ready. Those can happen at the end though, when you've done the pull request.

> Speed improvements can happen, if we could merge few of the passes together (it's a multi pass operation, as you can see in the code.)

A good point. But this can wait, first it should work.

On a related note, Skia very recently got boolean operations, and it might be interesting for you to look at their implementation. Maybe they also have good unit tests. The thread about it is here:

https://groups.google.com/a/chromium.org/forum/?fromgroups=#!topic/graphics-dev/fZuCeQ2Ach4

> I would like to have the api something along the lines of:
> var result = path1.add( path2 );
> var result = path1.intersect( path2 );
> var result = path1.subtract( path2 );
> var result = path2.subtract( path2 );

I agree. #add() is unfortunate, as it adds points already. #unite() seems to way to go, as that is closer to what it's actually doing (it's not simply adding the path, it's building the union).

So how about:

path1.unite(path2);
path1.intersect(path2);
path1.subtract(path2);
path1.exclude(path2);

> In order to do that I would add this to PathItem object (am I right?) and it can be inherited by Paths and CompoundPaths etc.

Yes that's correct. As long as all your functionality is abstracted in ways that makes it function for both CompoundPaths and Paths.

> So, I am working on extending this to handle CompoundPaths as input and defining Subtract operations. This shouldn't take longer than a few weeks!
> will keep you posted.

Very exciting! A few explanations about that:

CompoundPath#getCurves() is implemented in a way that it returns alls curves of all contained paths, in one long array. Path#getCurves() just returns the curves for the specific path, obviously. PathItem#getIntersections() then just called this, on either CompoundPath or Path, and works for both. I am not sure what other Path related methods you rely on for the boolean operations, so we should start by looking at this, and see if there are ways to abstract those, if there are any.

Sounds good?

> After that I can do a pull request! :)

Very nice! Looking forward to that moment,

Jürg

[Harikrishnan G.]

Interesting. Do you still use getIntersections() though? I was thinking that ideally it would be built on top of that and CurveLocation, to avoid duplicating code. How were you able to eliminate that? Is the new code online?

 

I am actially using, getNearestLocation though, (I'd forgotten earlier). But not for finding intersections, for calculating the parameter for sorting. —line nr: 256 at http://hkrish.com/playground/paperjs/Boolean.js

as for calculating intersections, i modified the Curve._addIntersections slightly to inject a unique intersectionID. This is because I am using a fully traversible graph structure as the basis of boolean operation. this is quite similar to the graph structure used in vatti's clipping algorithm, except that we cannot use scanline approach, that will work in polygon boolean operations.

my attempts at reusing the structure of Path objects failed mainly because of it's dependence on indices rather than absolute references for connectivity information between nodes and links. As far as possible I am reusing the existing code for intersections. You can see the modified function at around line nr. 460 in the same file.

Also, there are some questions regarding coding style, scoping and other things that we should discuss when you're ready. Those can happen at the end though, when you've done the pull request.

sure thing. 

https://groups.google.com/a/chromium.org/forum/?fromgroups=#!topic/graphics-dev/fZuCeQ2Ach4

thanks for this. I'll look into it.

> I would like to have the api something along the lines of:
> var result = path1.add( path2 );
> var result = path1.intersect( path2 );
> var result = path1.subtract( path2 );
> var result = path2.subtract( path2 );

* path2.subtract( path2 ); 
I meant path2.subtract( path1 ); for subtracting first path, I just included to remind myself that among these operations subtract is not commutative! sorry for the confusion

I agree. #add() is unfortunate, as it adds points already. #unite() seems to way to go, as that is closer to what it's actually doing (it's not simply adding the path, it's building the union).

So how about:

path1.unite(path2);
path1.intersect(path2);
path1.subtract(path2);
path1.exclude(path2);

I agree to unite, sounds better. I forgot about the exisiting add()!
also what is the difference between path1.subtract and  path1.exclude? 

CompoundPath#getCurves() is implemented in a way that it returns alls curves of all contained paths, in one long array. Path#getCurves() just returns the curves for the specific path, obviously. PathItem#getIntersections() then just called this, on either CompoundPath or Path, and works for both. I am not sure what other Path related methods you rely on for the boolean operations, so we should start by looking at this, and see if there are ways to abstract those, if there are any.

I'll look more into this.
About other path methods that I use, path.contains(), Curve.getNearectLocation().parameter, comes to mind.

Sounds good?  

 
>  After that I can do a pull request! :)

Very nice! Looking forward to that moment,

Me too!

Hari

[Harikrishnan G.]

Also, I ran into a small issue, when extending this to include CompoundPaths.

If I use Path.transform and then get all the curves from a Path, it returns the transformed curves (atleast for translate, it does), so that we can compute intersections on the transformed curves (as expected).

However doing so for CompoundPath, doesnot apply the transform immediately (which could be optimal in other cases). So is there a way that I can make sure that CompoundPath.getCurves() will give me all the curves after applying the transform?

Thanks!

[Harikrishnan G.]

I am doing
var transformMat = path1._matrix;
for (i = 0, l = path1Children.length; i < l; i++) {
    path1Children[i].transform( transformMat, true );

I guess there is a better way!

[Jürg Lehni]

On Apr 18, 2013, at 14:12 , Harikrishnan G. <hari.e...@gmail.com> wrote:

> I am actially using, getNearestLocation though, (I'd forgotten earlier). But not for finding intersections, for calculating the parameter for sorting. —line nr: 256 at http://hkrish.com/playground/paperjs/Boolean.js

Yes, I saw that. The reason still is that the CurveLocations returned by getIntersection don't always have a parameter defined, right? That's the bug I wanted to look into, and where I think we'll get quite a bit of performance improvement from.

> as for calculating intersections, i modified the Curve._addIntersections slightly to inject a unique intersectionID. This is because I am using a fully traversible graph structure as the basis of boolean operation. this is quite similar to the graph structure used in vatti's clipping algorithm, except that we cannot use scanline approach, that will work in polygon boolean operations.
>
> my attempts at reusing the structure of Path objects failed mainly because of it's dependence on indices rather than absolute references for connectivity information between nodes and links. As far as possible I am reusing the existing code for intersections. You can see the modified function at around line nr. 460 in the same file.

Would you have suggestions as to what should be added to core structures to facilitate this? It would surely make sense.

> > I would like to have the api something along the lines of:
> > var result = path1.add( path2 );
> > var result = path1.intersect( path2 );
> > var result = path1.subtract( path2 );
> > var result = path2.subtract( path2 );
>
> * path2.subtract( path2 );
> I meant path2.subtract( path1 ); for subtracting first path, I just included to remind myself that among these operations subtract is not commutative! sorry for the confusion
>
>
> I agree. #add() is unfortunate, as it adds points already. #unite() seems to way to go, as that is closer to what it's actually doing (it's not simply adding the path, it's building the union).
>
> So how about:
>
> path1.unite(path2);
> path1.intersect(path2);
> path1.subtract(path2);
> path1.exclude(path2);
>
> I agree to unite, sounds better. I forgot about the exisiting add()!
> also what is the difference between path1.subtract and path1.exclude?

Check this page for all possible boolean operations:

http://www.angelfire.com/mi/kevincharles/inkscape/p7c4.html

Combine = #unite(), Difference = #subtract(). We could also discuss Division = #divide(), which is Difference and Intersection combined.

> CompoundPath#getCurves() is implemented in a way that it returns alls curves of all contained paths, in one long array. Path#getCurves() just returns the curves for the specific path, obviously. PathItem#getIntersections() then just called this, on either CompoundPath or Path, and works for both. I am not sure what other Path related methods you rely on for the boolean operations, so we should start by looking at this, and see if there are ways to abstract those, if there are any.
>
> I'll look more into this.
> About other path methods that I use, path.contains(), Curve.getNearectLocation().parameter, comes to mind.

path.contains() is defined for CombinedPath too, so you can call it on both. The big question will be how you will deal with the compound path filling rules.

> If I use Path.transform and then get all the curves from a Path, it returns the transformed curves (atleast for translate, it does), so that we can compute intersections on the transformed curves (as expected).
>
> However doing so for CompoundPath, doesnot apply the transform immediately (which could be optimal in other cases). So is there a way that I can make sure that CompoundPath.getCurves() will give me all the curves after applying the transform?

Yes, Paths are special in that way: They always directly apply transformations to their segments, rather than storing them in the internal matrix. All other items store them in the matrix. This makes a lot of sense for Group,to allow flash-like behavior of nested coordinate systems, and is the only option for Raster and PlacedItems, but we should use the Path-way of ding things for CompoundPaths too, since they are paths as well. I just committed that change, I hope it helps:

https://github.com/paperjs/paper.js/commit/0ab43e130b06a86d1a6c340b846f91358017ce8b

Best,

Jürg

[Jürg Lehni]

Very cool!

[Jonathan Puckey]

Just wanted to chime in on the awesomeness of this. : )

[Harikrishnan Gopalakrishnan]

Sorry for all the repeated posts earlier! :D

On 19-Apr-2013, at 1:22 AM, Jürg Lehni wrote:

On Apr 18, 2013, at 14:12 , Harikrishnan G. <hari.e...@gmail.com> wrote:

Yes, I saw that. The reason still is that the CurveLocations returned by getIntersection don't always have a parameter defined, right? That's the bug I wanted to look into, and where I think we'll get quite a bit of performance improvement from.

Yup.

as for calculating intersections, i modified the Curve._addIntersections slightly to inject a unique intersectionID. This is because I am using a fully traversible graph structure as the basis of boolean operation. this is quite similar to the graph structure used in vatti's clipping algorithm, except that we cannot use scanline approach, that will work in polygon boolean operations.

my attempts at reusing the structure of Path objects failed mainly because of it's dependence on indices rather than absolute references for connectivity information between nodes and links. As far as possible I am reusing the existing code for intersections. You can see the modified function at around line nr. 460 in the same file.

Would you have suggestions as to what should be added to core structures to facilitate this? It would surely make sense.

I would try to write that down sometime next week. It's great if we can reuse, Curve and Segment objects. I have been iterating through the segments to make the graph. (thought that would be faster than getCurves creating a list of curve objects first and then creating a list of Links separately from that!) but if curves and segments have enough connectivity and identity information, I can just replace #makeGraph with calls to getCurves (which already works on Paths and CompoundPaths)! 

This should be a nice way to improve performance as well, since #computeBoolean as of now has lots of calls to create and cache Curve and Segment objects just to use their built-in methods such as Curve.subdivide!

I agree to unite, sounds better. I forgot about the exisiting add()!

also what is the difference between path1.subtract and  path1.exclude?  

Check this page for all possible boolean operations:

http://www.angelfire.com/mi/kevincharles/inkscape/p7c4.html

Combine = #unite(), Difference = #subtract(). We could also discuss Division = #divide(), which is Difference and Intersection combined.

Now I understand (I had xor in mind! :) )

I was thinking to put Unite, Intersect, Subtract –in sort of an A list. Once we've done that, we can think about integrating this with the paperjs api . Then from there we can implement Exclude, Division etc. 

What do you think? Or should we develop it al the way before trying to integrate this?

CompoundPath#getCurves() is implemented in a way that it returns alls curves of all contained paths, in one long array. Path#getCurves() just returns the curves for the specific path, obviously. PathItem#getIntersections() then just called this, on either CompoundPath or Path, and works for both. I am not sure what other Path related methods you rely on for the boolean operations, so we should start by looking at this, and see if there are ways to abstract those, if there are any.

I'll look more into this.

About other path methods that I use, path.contains(), Curve.getNearectLocation().parameter, comes to mind.

path.contains() is defined for CombinedPath too, so you can call it on both. The big question will be how you will deal with the compound path filling rules.

I am using CompoundPath.contains and it works great.

About the filling rules —I ran into this problem already! 

CompoundPath #insertChild() keeps the first child wound clockwise, and the rest wound counter-clockwise for holes right?

But when, I do all the intersections, merge the graph together, and try to retrieve paths back from the graph to add to the resulting CompoundPath, I need to know which contour to insert first!

In the image posted earlier, I am marking the curves that belonged to the base path each input CompoundPaths, and then after all the calculation, for generate the resulting paths, I look for a curve that was part of one of the base paths to start from, so that the other paths in the result of the boolean operations will be correctly handled by the CompundPath. Is this a good approach? What else would you recommend. (I can upload the code in a short while)

If I use Path.transform and then get all the curves from a Path, it returns the transformed curves (atleast for translate, it does), so that we can compute intersections on the transformed curves (as expected).

However doing so for CompoundPath, doesnot apply the transform immediately (which could be optimal in other cases). So is there a way that I can make sure that CompoundPath.getCurves() will give me all the curves after applying the transform?

Yes, Paths are special in that way: They always directly apply transformations to their segments, rather than storing them in the internal matrix. All other items store them in the matrix. This makes a lot of sense for Group,to allow flash-like behavior of nested coordinate systems, and is the only option for Raster and PlacedItems, but we should use the Path-way of ding things for CompoundPaths too, since they are paths as well. I just committed that change, I hope it helps:

https://github.com/paperjs/paper.js/commit/0ab43e130b06a86d1a6c340b846f91358017ce8b

I just pulled this in, and tried after removing my transformation hack! 

Works as expected. Thank you!

Thanks!

Hari

[Harikrishnan Gopalakrishnan]

Thanks!

I am going to complain more! :)

I found a new bug. https://github.com/paperjs/paper.js/issues/202

You received this message because you are subscribed to a topic in the Google Groups "Paper.js" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/paperjs/OWiSAoj8w90/unsubscribe?hl=en.
To unsubscribe from this group and all its topics, send an email to paperjs+u...@googlegroups.com.

[Jürg Lehni]

Keep em coming! :)

On Apr 19, 2013, at 07:28 , Harikrishnan Gopalakrishnan <hari.e...@gmail.com> wrote:

> Thanks!
>
> I am going to complain more! :)
> I found a new bug. https://github.com/paperjs/paper.js/issues/202
>
>
> On 19-Apr-2013, at 1:24 PM, Jonathan Puckey wrote:
>
>> Just wanted to chime in on the awesomeness of this. : )
>>
>> On Apr 18, 2013, at 3:30 PM, Harikrishnan G. <hari.e...@gmail.com> wrote:
>>
>>>
>>>
>>> Finally after 136 rewrites, paper paths are now joining and intersecting each other!
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>

[Jürg Lehni]

>>> as for calculating intersections, i modified the Curve._addIntersections slightly to inject a unique intersectionID. This is because I am using a fully traversible graph structure as the basis of boolean operation. this is quite similar to the graph structure used in vatti's clipping algorithm, except that we cannot use scanline approach, that will work in polygon boolean operations.
>>>
>>> my attempts at reusing the structure of Path objects failed mainly because of it's dependence on indices rather than absolute references for connectivity information between nodes and links. As far as possible I am reusing the existing code for intersections. You can see the modified function at around line nr. 460 in the same file.
>>
>> Would you have suggestions as to what should be added to core structures to facilitate this? It would surely make sense.
>
> I would try to write that down sometime next week. It's great if we can reuse, Curve and Segment objects. I have been iterating through the segments to make the graph. (thought that would be faster than getCurves creating a list of curve objects first and then creating a list of Links separately from that!) but if curves and segments have enough connectivity and identity information, I can just replace #makeGraph with calls to getCurves (which already works on Paths and CompoundPaths)!

Some explanations regarding the relationship between Segment and Curve, and their arrays:

- The main data structure that describes the paths are Segment and the Path#segments array.
- As soon as you ask for a curve, wether through Path#curves or Segment#curve (or others), the whole Path#curves list is created.
- Once created, Path#curves is cached and kept in sync with Path#segments, meaning new elements will be inserted, old ones removed as soon as Path#segments has changed.

This means that your optimization to avoid the #curves array does not improve speed if you later on access Curve objects anyway. Also, getIntersections internally asks for #curves already, so the lists will be created then and are cached from there onwards.

>>> I agree to unite, sounds better. I forgot about the exisiting add()!
>>> also what is the difference between path1.subtract and path1.exclude?
>>
>> Check this page for all possible boolean operations:
>>
>> http://www.angelfire.com/mi/kevincharles/inkscape/p7c4.html
>>
>> Combine = #unite(), Difference = #subtract(). We could also discuss Division = #divide(), which is Difference and Intersection combined.
>
> Now I understand (I had xor in mind! :) )
> I was thinking to put Unite, Intersect, Subtract –in sort of an A list. Once we've done that, we can think about integrating this with the paperjs api . Then from there we can implement Exclude, Division etc.
> What do you think? Or should we develop it al the way before trying to integrate this?

I think this plan makes sense. We'll probably embed this similarly to the SvgImport / Export functionality. That code is built in a private function scope, and then injected into the Item classes from there, using inject. You can see that in the code here:

https://github.com/paperjs/paper.js/blob/master/src/svg/SvgImport.js#L469

>> path.contains() is defined for CombinedPath too, so you can call it on both. The big question will be how you will deal with the compound path filling rules.
>
> I am using CompoundPath.contains and it works great.
>
> About the filling rules —I ran into this problem already!
> CompoundPath #insertChild() keeps the first child wound clockwise, and the rest wound counter-clockwise for holes right?
> But when, I do all the intersections, merge the graph together, and try to retrieve paths back from the graph to add to the resulting CompoundPath, I need to know which contour to insert first!

Yeah this problem keeps hunting us. The issue is that the only way to control fill rules is in Canvas right now is by using path orientation (even-odd fill rules are not supported yet). This is why we added this feature, because users would otherwise get confused about why compound paths do not appear as such. If you look for the _cloning parameter across the paper.js source, you will find many insertion related methods defining it. This was needed for CompoundPath#clone() to work properly, since SVG imported compound paths would not necessarily follow our clockwise rules.

I think we should rename that parameter to _preserve, (the "_" suggesting it should be a non-documented internal feature), and you could set it to true in your calls to insertChild().

But I have a feeling we need to come up with a better way of handling this anyway. I don't like it when things like path orientation get changed "magically". One way would be to fix orientation only when drawing, by reversing the loop, not the data structure. But this might still break SVG import... a tricky one!

> In the image posted earlier, I am marking the curves that belonged to the base path each input CompoundPaths, and then after all the calculation, for generate the resulting paths, I look for a curve that was part of one of the base paths to start from, so that the other paths in the result of the boolean operations will be correctly handled by the CompundPath. Is this a good approach? What else would you recommend. (I can upload the code in a short while)

That's hard to tell! I'll have to look into the approach more to be able to answer that. It doesn't sound like a huge penalty on performance, so if the approach works, why not? :)

> I just pulled this in, and tried after removing my transformation hack!
> Works as expected. Thank you!

Great! I'll hopefully be able to look into the imprecisions of getIntersection later on. You wouldn't have a simple test-case for me with coordinates where this is happening, would you? That would really help chasing it!

Jürg

[Jürg Lehni]

PS:

> This means that your optimization to avoid the #curves array does not improve speed if you later on access Curve objects anyway. Also, getIntersections internally asks for #curves already, so the lists will be created then and are cached from there onwards.

By this I mean you should totally rely on #segments and #curves, and not have to build your own caching structures.

[Jürg Lehni]

PS:

> This means that your optimization to avoid the #curves array does not improve speed if you later on access Curve objects anyway. Also, getIntersections internally asks for #curves already, so the lists will be created then and are cached from there onwards.

[Harikrishnan Gopalakrishnan]

Thanks for the explanation.

I really hope we can reuse the Curves and Segments for this. The main thing is that my implementation needs a properly connected graph structure with individual paths as connected subgraphs within. I will try to write down the requirements based on the boolean code, so we can look into how to make that happen.

btw. Boolean Difference operation was not that hard to figure out! This just reinforced my faith in the graph structure and I think we can very easily implement the other operations just be making the correct strategies to traverse the graph (as in #BooleanOps)

I'll upload the code soon. Right now it depends on a monkey patch, that solves the issue with #contains -> #getCrossings (I am counting the crossings on y and x simultaneously, but not a very robust solution!)

also, you were right about getNearestLocation. It seems like the main culprit so far in slowing this down!

hari

--
You received this message because you are subscribed to a topic in the Google Groups "Paper.js" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/paperjs/OWiSAoj8w90/unsubscribe?hl=en.
To unsubscribe from this group and all its topics, send an email to paperjs+u...@googlegroups.com.

[Jürg Lehni]

Just quickly regarding getNearestLocation: Would you have a simple test-case with specific path coordinates for me to reproduce this imprecision?

Jürg

On Apr 19, 2013, at 12:04 , Harikrishnan Gopalakrishnan <hari.e...@gmail.com> wrote:

> Thanks for the explanation.
>
> I really hope we can reuse the Curves and Segments for this. The main thing is that my implementation needs a properly connected graph structure with individual paths as connected subgraphs within. I will try to write down the requirements based on the boolean code, so we can look into how to make that happen.
>
> btw. Boolean Difference operation was not that hard to figure out! This just reinforced my faith in the graph structure and I think we can very easily implement the other operations just be making the correct strategies to traverse the graph (as in #BooleanOps)
>

> <PastedGraphic-1.png>

>
> I'll upload the code soon. Right now it depends on a monkey patch, that solves the issue with #contains -> #getCrossings (I am counting the crossings on y and x simultaneously, but not a very robust solution!)
>
>
> also, you were right about getNearestLocation. It seems like the main culprit so far in slowing this down!
>

> <Screen Shot 2013-04-19 at 7.44.42 PM.png>

>
>
> hari
>
>
> On 19-Apr-2013, at 8:45 PM, Jürg Lehni wrote:
>
>> PS:
>>
>>> This means that your optimization to avoid the #curves array does not improve speed if you later on access Curve objects anyway. Also, getIntersections internally asks for #curves already, so the lists will be created then and are cached from there onwards.
>>
>> By this I mean you should totally rely on #segments and #curves, and not have to build your own caching structures.
>>
>>
>> --
>> You received this message because you are subscribed to a topic in the Google Groups "Paper.js" group.
>> To unsubscribe from this topic, visit https://groups.google.com/d/topic/paperjs/OWiSAoj8w90/unsubscribe?hl=en.
>> To unsubscribe from this group and all its topics, send an email to paperjs+u...@googlegroups.com.
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>
>
> --

> You received this message because you are subscribed to the Google Groups "Paper.js" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to paperjs+u...@googlegroups.com.

[Jürg Lehni]

One last note for today:

Your code currently overrides Curve._addIntersections not only to define _intersectionID, but also to return a list of Point objects rather than CurveLocation objects, which makes it incompatible with our current implementation.

It would be good to switch back to using CurveLocation in the code, also since CurveLocation#parameter will be get way to solve the issue with getNearestLocation(), once the imprecision there is solved.

Does this make sense?

I will not add support for _intersectionID to Point directly, but CurveLocation can easily receive a unique _id, just like Item already has. I will add that right now, so you can switch to using that.

Lastly, I'm not sure this is of use, but CurveLocation has methods to directly split and divide in their location, through CurveLocation#split() / #divide().

Best,

Jürg

On Apr 19, 2013, at 12:04 , Harikrishnan Gopalakrishnan <hari.e...@gmail.com> wrote:

>
>

> Thanks for the explanation.
>
> I really hope we can reuse the Curves and Segments for this. The main thing is that my implementation needs a properly connected graph structure with individual paths as connected subgraphs within. I will try to write down the requirements based on the boolean code, so we can look into how to make that happen.
>
> btw. Boolean Difference operation was not that hard to figure out! This just reinforced my faith in the graph structure and I think we can very easily implement the other operations just be making the correct strategies to traverse the graph (as in #BooleanOps)
>

> <PastedGraphic-1.png>

>
> I'll upload the code soon. Right now it depends on a monkey patch, that solves the issue with #contains -> #getCrossings (I am counting the crossings on y and x simultaneously, but not a very robust solution!)
>
>
> also, you were right about getNearestLocation. It seems like the main culprit so far in slowing this down!
>

> <Screen Shot 2013-04-19 at 7.44.42 PM.png>
>
>

> hari
>
>
> On 19-Apr-2013, at 8:45 PM, Jürg Lehni wrote:
>
>> PS:
>>
>>> This means that your optimization to avoid the #curves array does not improve speed if you later on access Curve objects anyway. Also, getIntersections internally asks for #curves already, so the lists will be created then and are cached from there onwards.
>>
>> By this I mean you should totally rely on #segments and #curves, and not have to build your own caching structures.
>>
>>
>> --
>> You received this message because you are subscribed to a topic in the Google Groups "Paper.js" group.
>> To unsubscribe from this topic, visit https://groups.google.com/d/topic/paperjs/OWiSAoj8w90/unsubscribe?hl=en.
>> To unsubscribe from this group and all its topics, send an email to paperjs+u...@googlegroups.com.
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>
>
> --

> You received this message because you are subscribed to the Google Groups "Paper.js" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to paperjs+u...@googlegroups.com.

[Harikrishnan G.]

#getNearestLocation isn't needed after all! I replaced it with #getParameterOf, and it works, is quite fast now! (I am uploading the code!)

Thanks for following this up  and sorry for the false alarm!

A little background on why I reported the issue earlier:
I have an implementation that I tried brfor which used paperjs's native data structure. Finding intersections was the easy part (because I used the Path.getIntersections method) except that there was not enough connectivity information (curveLocation has info on one curve and is completely oblivious about  which other curve it intersected with!), but merging paths together very very hard, not to mention, it couldn't handle holes at all! So in my earlier implementation the Curve.divide would sometimes return null ( especially after the curve has been split once and if there are more intersections to deal with ), and it worked when I changed to #getNearestLocation.
You can find one of my old trials here http://hkrish.com/playground/paperjs/old/boolean4_old.js

Thanks,
Hari

[Harikrishnan G.]

Progress update:

I updated the Tests/Demo

The implementation now can handle paperjs CompoundPaths as well as Subtraction as a boolean Operation. Also should run faster!

Thanks for all the kind support Jürg. Hope you would continue to help me on extending and integrating this into the core library!
:)

Cheers,
Hari

[Jürg Lehni]

Hi Hari,

On Apr 20, 2013, at 05:19 , Harikrishnan G. <hari.e...@gmail.com> wrote:

> The implementation now can handle paperjs CompoundPaths as well as Subtraction as a boolean Operation. Also should run faster!
>
> Thanks for all the kind support Jürg. Hope you would continue to help me on extending and integrating this into the core library!
> :)

Those are great news!

And of course, I'm more than happy to help you along the way. I can't wait to merge this in really :)

> #getNearestLocation isn't needed after all! I replaced it with #getParameterOf, and it works, is quite fast now! (I am uploading the code!)
>
> Thanks for following this up and sorry for the false alarm!
>
> A little background on why I reported the issue earlier:
> I have an implementation that I tried brfor which used paperjs's native data structure. Finding intersections was the easy part (because I used the Path.getIntersections method) except that there was not enough connectivity information (curveLocation has info on one curve and is completely oblivious about which other curve it intersected with!), but merging paths together very very hard, not to mention, it couldn't handle holes at all! So in my earlier implementation the Curve.divide would sometimes return null ( especially after the curve has been split once and if there are more intersections to deal with ), and it worked when I changed to #getNearestLocation.
> You can find one of my old trials here http://hkrish.com/playground/paperjs/old/boolean4_old.js

CurveLocation is using #getParameterOf internally as well.

We should still work towards merging parts of your changes back into CurveLocation. Because the way you currently overload getIntersections, we won't be able to merge this back in since it's returning different values (points instead of locations). So the way to go I think is to add the functionality you require to implement boolean operations through CurveLocation.

So let's make a list of what exactly do you need to be added to CurveLocation, so it can be used as the core to your algorithm:

- Link to the intersecting curve
- ?

And yes, what you mention about Curve.divide sometimes returning null after the first divide sounds familiar. But I believe I have fixed that bug to actually avoid that. So if this is still happening, there is indeed a bug somewhere, that I would like to fix!

Jürg

[Harikrishnan Gopalakrishnan]

On 20-Apr-2013, at 8:18 PM, Jürg Lehni wrote:

We should still work towards merging parts of your changes back into CurveLocation. Because the way you currently overload getIntersections, we won't be able to merge this back in since it's returning different values (points instead of locations). So the way to go I think is to add the functionality you require to implement boolean operations through CurveLocation.

The source is now updated. I am using CurveLocation right now.

Also added more tests to the test suit. Some new ones including, resolving self-intersections, correctly handling holes and islands in CompoundPaths etc.

https://github.com/hkrish/boolean2 

So let's make a list of what exactly do you need to be added to CurveLocation, so it can be used as the core to your algorithm:

- Link to the intersecting curve
- ?

CurveLocation has to have an ID. And that's enough I guess. (ID should possibly be mutable —since we have two CurveLocations on each Intersecting curves, but can have the same id, so their resulting split nodes can be tracked in later passes;  I noticed that I can set Path._id but not Path.id, so probably it's ok)

Cheers

Hari

[Harikrishnan Gopalakrishnan]

What is the intersection strategy (as returned by #getIntersections/#Curve._addIntersections) on curves that overlap exactly on top of each other?
Is it 'undefined' as of yet?

Is it appropriate to say, that the cures intersect at both start and end of the curve?

Right now, this is the main failure case for this algorithm! (at least as far as I can say. It will almost surely fail on such cases!)

Thanks,
hari

[Jürg Lehni]

As always, great news Hari! I'm really excited about where this is heading. It seems we're almost there!

> CurveLocation has to have an ID. And that's enough I guess. (ID should possibly be mutable —since we have two CurveLocations on each Intersecting curves, but can have the same id, so their resulting split nodes can be tracked in later passes; I noticed that I can set Path._id but not Path.id, so probably it's ok)

I have already added the #_id property, feel free to use it!

Item#id (= Path#id) is read-only since it is supposed to be a unique identifier that is also used internally to link to items, and my previous post to this list explains why setting _id is not normally supported. But CurveLocation is a different animal, and _id is only there for your case right now, so yes you could change it.

But I would like to add support for linking to the intersecting curve in CurveLocation. How about:

CurveLocation#intersection (through the CurveLocation#getIntersection() getter)

Returning another CurveLocation object, pointing to the same location on the other curve. Now this other CurveLocation object could point back to the original one too, through its #intersection property.

Wouldn't this remove the need for mutable _ids? And perhaps even the _id all together?

Another question: Is there a reason why you don't use Path#getIntersections(), but call Curve._addIntersections() directly? Once I would add enough features to CurveLocation I believe more of your code can merge with Path#getIntersections(), right? I'd like to reduce as much code duplication as possible, for obvious reasons.

> What is the intersection strategy (as returned by #getIntersections/#Curve._addIntersections) on curves that overlap exactly on top of each other?
> Is it 'undefined' as of yet?

That's a very good question! I haven't looked into it yet.

> Is it appropriate to say, that the cures intersect at both start and end of the curve?
>
> Right now, this is the main failure case for this algorithm! (at least as far as I can say. It will almost surely fail on such cases!)

I haven't defined its behavior yet, and I think whatever is useful for boolean operations should be the way it behaves. Would the start & end be of use?

Lastly, I have looked into performance, and found that 30% of the time is spent in my #getIntersections() code. I know that we could speed that up a lot if we did not use the current simple divide and conquer approach, but switched to fat line bezier clipping [1]. Perhaps tackling this next step might be an interesting challenge for you once this is merged in? :)

Jürg

[1] http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf

[Harikrishnan Gopalakrishnan]

On 23-Apr-2013, at 7:35 PM, Jürg Lehni wrote:

I have already added the #_id property, feel free to use it!

Thanks Jürg!

Item#id (= Path#id) is read-only since it is supposed to be a unique identifier that is also used internally to link to items, and my previous post to this list explains why setting _id is not normally supported. But CurveLocation is a different animal, and _id is only there for your case right now, so yes you could change it.

I am not changing Path.id/Curve.id. I just tried setting it in firebug, just to know ;)

But I would like to add support for linking to the intersecting curve in CurveLocation. How about:

CurveLocation#intersection (through the CurveLocation#getIntersection() getter)

Returning another CurveLocation object, pointing to the same location on the other curve. Now this other CurveLocation object could point back to the original one too, through its #intersection property.

Wouldn't this remove the need for mutable _ids? And perhaps even the _id all together?

This is of source a nicer way of doing this. But right now the bottleneck is the sorting and recalculating the parameters part. When we detect an intersection, we cannot split it straight away, or else we split it and check for further intersections in the Path including the split curves as well. Which would be complicated and inefficient!

The algorithm:

1. Prepare the graph data structure for the operands. data structure is a complete directed-graph (digraph), with a number of cyclic connected components (one for each closed contour)
2. Merge all operands together to a bigger graph. All operation from this point on take place in this graph.
3. The algorithm is the data structure itself. The rest of the algorithm is merely a set of conditional additions and deletions in this graph.
4. Get all possible intersections on a per curve basis and store them in the link itself temporarily
5. Then after looping through the entire graph, 
1. for each curve, start splitting it from the intersection that has the lowest t (so we sort here if we have more than one intersection)
2. get the intersection id from the CurveLocation here and assign it to the new node where we split (actually the intersectionIDs are used to find the corresponding node after all curves have been split)
3. push the left part back to the graph (we sorted the intersections before, so all the other intersections on this curve should fall on the right curve )
4. Also correctly hook up the links and nodes in the graph with the new curves
5. recalculate t (parameter) of all the remaining intersections, since the original curve has changed after the split.
6. repeat with the right part of the curve and remaining intersections
6. For each node that has an Intersection ID, search in the graph for another node which has the same intersection id and merge them together.
1. So the intersecting nodes will become a four way node
2. i.e. these type of nodes will have two sets of curveIns and curveOuts and associated handles
7. In the next pass, we discard links according to the operator.
1. in case of Union, discard all links that is inside both operands
2. etc.
8. after discarding, in each of the four-way nodes (intersections), at most two of the links will be discarded, so gather two of the valid links. 
1. This will make this four-way node a normal node with just one CurveIn and curveOut (and associated handles) each.
9. Now the graph should only contain, the result of the boolean.
10. Walk the graph and form connected contours
11. Repeat until all the nodes are visited.

This is it in a nutshell.

I tried porting this to use the segments and Curves instead, (by doing a bit of monkey patching). But didn't work :(

You can look in the api branch at  https://github.com/hkrish/boolean2.git

(a warning: the tests on the api branch probably will loop forever!)

Another question: Is there a reason why you don't use Path#getIntersections(), but call Curve._addIntersections() directly? Once I would add enough features to CurveLocation I believe more of your code can merge with Path#getIntersections(), right? I'd like to reduce as much code duplication as possible, for obvious reasons.

The reason is the same as above. I can't seem to think of a nice way to reuse this part of the code. I am very much in favour of reusing the code as much as possible. Can you please look at it and make some suggestions so as to what changes can we make?! 

Another note, I am doing the same routines as in the Path#getIntersections; but in a way that it will help forming the data structure correctly. A big list of intersections —as opposed to, retrieving intersections curve by curve basis, probably will only make this code heavier ( at least two more passes as I can think of, one for separating this list of intersections into smaller lists for each curve and then sorting and them per curve as before, and also recalculating parameter and splitting is not going anywhere! ). 

On the plus side, any improvements and bug squashing we make on the Curve#_addIntersections will be independent of this at least.

What is the intersection strategy (as returned by #getIntersections/#Curve._addIntersections) on curves that overlap exactly on top of each other?

Is it 'undefined' as of yet?

That's a very good question! I haven't looked into it yet.

Is it appropriate to say, that the cures intersect at both start and end of the curve?

Right now, this is the main failure case for this algorithm! (at least as far as I can say. It will almost surely fail on such cases!)

I haven't defined its behavior yet, and I think whatever is useful for boolean operations should be the way it behaves. Would the start & end be of use?

At first I though so. I don't have a good answer at this point. I am working on this.

Meanwhile to conclude that this is indeed the case, we need to resolve some ambiguities in Curve._addIntersections and Path.contains. I filed two issues with test cases on these https://github.com/paperjs/paper.js/issues/207 and https://github.com/paperjs/paper.js/issues/208. Could you take a look at them when you have some time?

Lastly, I have looked into performance, and found that 30% of the time is spent in my #getIntersections() code.

I added a check for calculating plain old line intersections, if the curves are linear. It sped up some of the test cases by more than 100% ( stars example etc.)

I know that we could speed that up a lot if we did not use the current simple divide and conquer approach, but switched to fat line bezier clipping [1]. Perhaps tackling this next step might be an interesting challenge for you once this is merged in? :)

You really don't want to see some of my older code!! ;)

Fat line clipping indeed seems a possibly better approach.

Hari

Jürg

[1] http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf

[Harikrishnan Gopalakrishnan]

>
> Lastly, I have looked into performance, and found that 30% of the time is spent in my #getIntersections() code. I know that we could speed that up a lot if we did not use the current simple divide and conquer approach, but switched to fat line bezier clipping [1]. Perhaps tackling this next step might be an interesting challenge for you once this is merged in? :)
>

http://tom.cs.byu.edu/~557/text/cagd.pdf

on page 98 has a relative comparison of timings for different bezier clipping algorithms
Sub-division seems to be the slowest!

[Jürg Lehni]

> http://tom.cs.byu.edu/~557/text/cagd.pdf
>
> on page 98 has a relative comparison of timings for different bezier clipping algorithms
> Sub-division seems to be the slowest!

Yes, but also the easiest to implement :)

J

[Harikrishnan Gopalakrishnan]

Hi Jürg,

I have pushed the latest version to https://github.com/hkrish/boolean2.git
I think we can start integrating this.

I hope I will get some time next week to make a pull request! :)

Cheers,
Hari

[Jürg Lehni]

Hi Hari,

That's great!

I am still looking into issue #207. Your solution for line intersections works for the cases that you are using them in, but there are problems with it too: If you have for example a square at 45°, of which a corner overlaps with a line of another square, then you receive the solution twice.

I am looking into how to merge this in, and also how to handle that edge case elegantly.

BTW, there already is code for line intersection in Paper.js, through the internal Line class. It offers fine grained control over wether to intersect finite or infinite lines, and weather to include the ends or not (as needed by line intersection).

To explain the issue in more detail: I exclude beginnings of lines / curves, and include ends, to avoid overlaps in corners and double solutions. Now the problem emerges from lines that have infinite solutions since they overlap. In that case, the next curve needs to include both beginning and end.

But yes, please make a pull request as soon as possible, since it's time to wrap things up!

Jürg

> --

> You received this message because you are subscribed to the Google Groups "Paper.js" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to paperjs+u...@googlegroups.com.

[Jürg Lehni]

I have fixed #207 now.

As far as I can tell, no duplicate solutions are returned, but for some reason this change has broken two of your examples. I can't figure out why, it's probably easier if you look at what's changed, and wether the mistake is at your end or mine:

https://github.com/paperjs/paper.js/commit/c513a24f4653276becdb2cc0a3ec5565e425b685

Also, this should allow you now to switch back to only using Curve.getIntersections() without your own getLineIntersections()

Best,

Jürg

On Apr 26, 2013, at 02:27 , Harikrishnan Gopalakrishnan <hari.e...@gmail.com> wrote:

> --

> You received this message because you are subscribed to the Google Groups "Paper.js" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to paperjs+u...@googlegroups.com.

[Harikrishnan Gopalakrishnan]

Hi Jürg,

Thanks for the fix. It does it for the issues I submitted. But it now returns duplicate results for curves when they overlap exactly on segments (do you remember the old issue that I posted)

For now I am working around this by adding another pass to filter out the duplicates. So that I can continue working on the pull request.

Also you are right about the case where the corner of a square falls exactly on another path's contour. But that could be also thought as a problem with the boolean case; where two contours share only one point. I will have to modify my code a bit to handle that. I added a test case for it for now!

Best,

Hari

ps. Did I tell you that I have a very crude version of fat-line clipping working! :) Thanks for that paper, it had lots of pictures to make things clear! 

It's much slower that what it could be though!

You received this message because you are subscribed to a topic in the Google Groups "Paper.js" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/paperjs/OWiSAoj8w90/unsubscribe?hl=en.
To unsubscribe from this group and all its topics, send an email to paperjs+u...@googlegroups.com.

[Jürg Lehni]

Hi Hari,

I think the reason why it returns duplicates is because you are collecting the locations on a per curve basis, and the new algorithm counts on all locations being in the same array, so it can check the immediately preceding solutions for overlaps.

This was the only way I could make your new edge cases with overlapping lines work. If I go back to the previous approach, those would fail again.

I need to spend some proper time to understand your algorithm fully. But I do again wonder:

If CurveLocation would hold more information and link to the intersecting curve as well, like I proposed earlier through a property called CurveLocation#intersection which links to another CurveLocation on the second curve, wouldn't you be able to write the algorithm differently, using Path.getIntersections rather than Curve.getIntersections?

You mentioned you tried to go down that route, but ended up in endless recursions.

Would it help if I added this additional information?

I am also wondering if Node could not merge wit Segment if you were able to store additional information on existing Segments. Path already has a property called #data, which is there just for that. We could add the same to Segment.

Also, Path#getCurves() and CompoundPath#getCurves() already behave the same, and return all curves in the path, wether it's a compound path or not. And Curves hold information about their Segments. And Segments are basically the same as your Nodes, minus some additional information. I have a feeling that we could simplify things quite a bit if we started merging more. Don't you agree?

And lastly, one observation about your new test: This is currently failing, no? I think the 2nd situation should result in all shapes being red.

More soon!

Jürg

On Apr 29, 2013, at 00:00 , Harikrishnan Gopalakrishnan <hari.e...@gmail.com> wrote:

Hi Jürg,

Thanks for the fix. It does it for the issues I submitted. But it now returns duplicate results for curves when they overlap exactly on segments (do you remember the old issue that I posted)
For now I am working around this by adding another pass to filter out the duplicates. So that I can continue working on the pull request.

<PastedGraphic-2.png>

[Jürg Lehni]

Hi Hari,

Don't worry about the proposed code changes for now. Let's first get the pull request together, and then I can see if I can convert the code in the proposed way later on.

It'll be much easier to work on it together once it's merged in.

Jürg

On Apr 29, 2013, at 00:00 , Harikrishnan Gopalakrishnan <hari.e...@gmail.com> wrote:

>
> Hi Jürg,
>

> Thanks for the fix. It does it for the issues I submitted. But it now returns duplicate results for curves when they overlap exactly on segments (do you remember the old issue that I posted)
> For now I am working around this by adding another pass to filter out the duplicates. So that I can continue working on the pull request.
>

> <PastedGraphic-2.png>

[Harikrishnan Gopalakrishnan]

Hi Jürg,

What the appropriate way to define a constant in paperjs?
I need to define INTERSECTION_NODE and NORMAL_NODE for differentiating node types.
I could hard code 1, 2 etc. but didn't seem like the best way to do it.

Also I am planning to use Base._uid instead of UNIQUE_ID, INTERSECTION_ID etc.
is that alright?

Thanks,
Hari

>
> Don't worry about the proposed code changes for now. Let's first get the pull request together, and then I can see if I can convert the code in the proposed way later on.
>
> It'll be much easier to work on it together once it's merged in.

Yes.

[Jürg Lehni]

Hey Hari,

Don't worry too much about these things, as I will have to consolidate things anyhow. But to answer your questions:

> What the appropriate way to define a constant in paperjs?
> I need to define INTERSECTION_NODE and NORMAL_NODE for differentiating node types.
> I could hard code 1, 2 etc. but didn't seem like the best way to do it.

Look at SelectionState.js to see how we handle constants through "enums". You can do the same, and then use the substitution feature of prepro.js (the mini-lib that dynamically loads / builds the library). Here an example of that in use in the code:

if (selected || (state & /*#=*/ SelectionState.HANDLE_IN))
drawHandle(2);

In the built library, thanks to the /*#=*/, this then gets translated to:

if (selected || (state & 1))
drawHandle(2);

> Also I am planning to use Base._uid instead of UNIQUE_ID, INTERSECTION_ID etc.
> is that alright?

Actually, Base._uid is gone now, since we wanted to have different ranges across different classes. Here is what we do now, it's one line of code from Item that handles it all and does not rely on external variables.

// Define this Item's unique id.
this._id = Item._id = (Item._id || 0) + 1;

And here the same for Symbol : )

// Define this Symbols's unique id.
this._id = Symbol._id = (Symbol._id || 0) + 1;

J