Concave path to multiple convex paths

thehen · Post by **thehen** » Mon Jun 11, 2012 8:31 pm

Hi all,

This is a toughie to say the least.

I'm building a level editor for a game using Photoshop scripting. It's going well with layer positions, sprites and even physics coordinates being generated.

Something that is a bit beyond me however, is converting a single concave path to multiple convex paths (necessary for complex physics geometry). I was wondering if anyone has tackled anything similar in Photoshop before?

Any help would be greatly appreciated

jacobolus · Post by **jacobolus** » Tue Jun 12, 2012 12:47 am

This is a math question, not a Photoshop scripting question. What kind of paths are we talking about? Polygons? Bezier-curve edges? (For arbitrary curves, it’s not always possible to break them into only convex parts, though you could get arbitrarily close by increasing the number of parts.) There has been some good work on breaking polygons into convex parts, and there are several algorithms to choose from. Google (or do a google scholar search) for "decomposition convex parts" or similar, and you’ll find some good resources & papers.

Mike Hale · Post by **Mike Hale** » Tue Jun 12, 2012 2:46 am

And be aware that scripting paths is very limited. You may not be able to do what you want with scripting even if you know the math.

jacobolus · Post by **jacobolus** » Tue Jun 12, 2012 3:56 am

Limited in which ways? At the very least it’s possible to retrieve a lot of information from a path’s ActionDescriptor. I haven’t really tried to play with manipulating the points of existing paths / creating new ones yet, so I don’t know how much can be done there, or how easily.

Code: Select all$desc {
pathName: 'Work Path'
pathContents: $desc 'pathClass', {
pathComponents: $list [
$desc 'pathComponent', {
shapeOperation: $enum 'shapeOperation.intersect'
subpathListKey: $list [
$desc 'subpathsList', {
points: $list [
$desc 'pathPoint', {
anchor: $desc 'point', {
horizontal: $unit 'pixelsUnit', 38
vertical: $unit 'pixelsUnit', 67
}
forward: $desc 'point', {
horizontal: $unit 'pixelsUnit', 39.1171378951985
vertical: $unit 'pixelsUnit', 56.3871899956139
}
backward: $desc 'point', {
horizontal: $unit 'pixelsUnit', 36
vertical: $unit 'pixelsUnit', 86
}
smooth: true
}
$desc 'pathPoint', {
anchor: $desc 'point', {
horizontal: $unit 'pixelsUnit', 57.1225898602079
vertical: $unit 'pixelsUnit', 48.3163088044102
}
forward: $desc 'point', {
horizontal: $unit 'pixelsUnit', 62.8255834265548
vertical: $unit 'pixelsUnit', 49.3388891869069
}
backward: $desc 'point', {
horizontal: $unit 'pixelsUnit', 49.9062531362839
vertical: $unit 'pixelsUnit', 47.0223770681164
}
smooth: true
}
$desc 'pathPoint', {
anchor: $desc 'point', {
horizontal: $unit 'pixelsUnit', 61
vertical: $unit 'pixelsUnit', 76
}
forward: $desc 'point', {
horizontal: $unit 'pixelsUnit', 49
vertical: $unit 'pixelsUnit', 119
}
backward: $desc 'point', {
horizontal: $unit 'pixelsUnit', 66.2971726288088
vertical: $unit 'pixelsUnit', 57.0184647467686
}
smooth: true
}
]
}
]
}
$desc 'pathComponent', {
shapeOperation: $enum 'shapeOperation.intersect'
subpathListKey: $list [
$desc 'subpathsList', {
points: $list [
$desc 'pathPoint', {
anchor: $desc 'point', {
horizontal: $unit 'pixelsUnit', 18
vertical: $unit 'pixelsUnit', 46
}
forward: $desc 'point', {
horizontal: $unit 'pixelsUnit', 19.1171378951985
vertical: $unit 'pixelsUnit', 35.3871899956139
}
backward: $desc 'point', {
horizontal: $unit 'pixelsUnit', 16
vertical: $unit 'pixelsUnit', 65
}
smooth: true
}
$desc 'pathPoint', {
anchor: $desc 'point', {
horizontal: $unit 'pixelsUnit', 37.1225898602079
vertical: $unit 'pixelsUnit', 27.3163088044102
}
forward: $desc 'point', {
horizontal: $unit 'pixelsUnit', 42.8255834265548
vertical: $unit 'pixelsUnit', 28.3388891869069
}
backward: $desc 'point', {
horizontal: $unit 'pixelsUnit', 29.9062531362839
vertical: $unit 'pixelsUnit', 26.0223770681164
}
smooth: true
}
$desc 'pathPoint', {
anchor: $desc 'point', {
horizontal: $unit 'pixelsUnit', 41
vertical: $unit 'pixelsUnit', 55
}
forward: $desc 'point', {
horizontal: $unit 'pixelsUnit', 29
vertical: $unit 'pixelsUnit', 98
}
backward: $desc 'point', {
horizontal: $unit 'pixelsUnit', 46.2971726288088
vertical: $unit 'pixelsUnit', 36.0184647467686
}
smooth: true
}
]
}
]
}
]
}
itemIndex: $int 1
count: $int 1
kind: $enum 'pathKind.workPathIndex'
targetPath: true
ID: $int 50
}

jacobolus · Post by **jacobolus** » Tue Jun 12, 2012 6:53 am

By the way, is there any comprehensive list anywhere of what kinds of things people have found to be possible/impossible with PS scripting? Adobe doesn’t really provide that documentation, and looking via google search, or grepping through Adobe-provided sample code or e.g. the xtools source is a bit hit or miss. It would be pretty neat if, when trying to figure out questions like “how much can be done with paths via a script”, there were some definitive description of what could and couldn’t be accomplished in the past.

thehen · Post by **thehen** » Tue Jun 12, 2012 1:09 pm

Thanks for the replies!

I'm looking at polygons for this.

Hmm I've been looking at some algorithms and it looks to be a bit beyond me. There seems to be a lot of vector math - how would one approach this when scripting for Photoshop? I can't find any resources.

This is the algorithm I've looked at specifically: http://mnbayazit.com/406/bayazit
As I'm not familiar with C++ I've then been looking at this .Lua port: http://giderosmobile.com/forum/discussi ... -algorithm

Any resources or examples of existing code that deals with similar mathematical complexity would be greatly appreciated.

Thanks!

jacobolus · Post by **jacobolus** » Tue Jun 12, 2012 1:50 pm

There seems to be a lot of vector math - how would one approach this when scripting for Photoshop?
You’re going to need to find the list of points in your polygons (maybe this is available in the Photoshop DOM? Otherwise, you can get it via ActionDescriptor code), and put it into some Javascript array. Then you’ll need to find an implementation of one of those algorithms and port it to Javascript, or else find a mathematical description and implement it yourself. There are lots of examples on the web of sophisticated Javascript code, including various kinds of number crunching & graphics stuff. Not sure whether there’s anything specifically solving this problem. Your algorithm will probably produce several new arrays of points for the new polygons. You’ll take these and turn them into new paths or path components, again either by scripting the DOM or using ActionDescriptor code.

The best place to ask for help with the algorithm implementation would probably be someplace like Stack Overflow or IRC, where people familiar with these kinds of algorithms might see it. You could also try browsing the computer graphics sections of a nearby university library. Lots of books have been written about this sort of thing. I’ve never thought about this specific problem, but if you get stuck on some particular point I’d be glad to take a glance.

There are some interesting links from http://stackoverflow.com/questions/3033 ... operations ... operations

Here’s a not-very-fast but pretty simple looking algorithm http://mnbayazit.com/406/keil

Here are a couple (not Javascript) of polygon partition packages:
http://www.cgal.org/Manual/latest/doc_h ... titioning2 ... titioning2
http://code.google.com/p/polypartition/

Mike Hale · Post by **Mike Hale** » Tue Jun 12, 2012 2:07 pm

jacobolus wrote:Limited in which ways?

You can get the path point info using either the DOM or Action Manager code but there are some complex paths where you can't get all the info. I think those paths were created in Illustrator or some other vector program. It seems that some paths have sub-paths that also have sub-paths. Photoshop scripting does not let you access that sub-sub path info. I think somewhere in the upload section is an example path another user that brought this to my attention posted.

Even if you can get all the point info you can not edit a existing path via scripting. The best you can do is get the info, edit as needed and create a new path from the edited data.

jacobolus · Post by **jacobolus** » Tue Jun 12, 2012 2:11 pm

It seems that some paths have sub-paths that also have sub-paths. Photoshop scripting does not let you access that sub-sub path info.
Interesting. I’ll play around with this and see if I can come up with some. Do you remember specifically how to create those in Illustrator?

Even if you can get all the point info you can not edit a existing path via scripting. The best you can do is get the info, edit as needed and create a new path from the edited data.
Is there other information stored in a path such that its identity is important? It seems like being able to make arbitrary new paths and delete the old one is sufficient for most cases, no?

Mike Hale · Post by **Mike Hale** » Tue Jun 12, 2012 2:22 pm

Yes, creating a new path from edited data of an existing path works most of the time. It just adds a layer of complexity that would not be needed if the original path could be edited. For example think of the steps needed to make a simple edit to a vector mask.