This is traditionally via code / math a pretty complex problem to solve for, given a set of coordinates, finding the bordering points.
From what I’ve researched alpha hull’s and convex hulls are algorithms used in graphic design to do this but implementing these have been a bit beyond my abilities, and most examples seem to be very library heavy.
Anyone have any ideas on a clever way to approach this problem that plays to touch’s strengths?
doesn’t have to be fast or real time, more just a matter of getting it to work somehow.
Not really an accurate solution, but if you use a copy SOP (or instancing) to render a large
polygon at each point, you might then capture the more ‘solid’ image in a render TOP, or
OP Viewer TOP, and use a Trace SOP to get the outline (assuming no interior holes).
The boundary will be bumpy and not line up with your original points, but will give you
a rough approximation.
Hey Rob, thanks for the suggestion, I was contemplating something similar with the edge TOP but I got somewhat stuck on generating some kind of triangulated mesh from the point set that didn’t look terrible.
The closest I got was using the ray SOP to shrink wrap a grid SOP to the points using nearest, but that left a lot of stretched triangles that caused the silhouette to be incorrect.
I tried to delete certain triangles via certain criteria like distance from neighboring points but nothing was really clean enough
I stumbled across a library I’ve not used before though: SciPy. A library that seems to have the tools already made to do exactly what I need built right in!
Does the solution need to be interactive/realtime?
If not, you could probably take your time with an executing Script SOP,
using Delaunay triangulation on the mesh points.
Likely several python solutions already out there I assume as well, or you could implement in a C++ CHOP.
Once its triangulated, you can use the Group SOP, Edges tab to select unshared edges.
Attached is a Script SOP implementation of the Graham Scan.
I may have an off-by-one error somewhere, but seems to work well from initial observation: graham_bounds.1.toe (6.1 KB)
Woa! that’s pretty amazing, I haven’t even heard of those two algorithms, I like them, much easier to wrap my art brain around
Thanks for the help on that, that works perfectly for convex hulls, which unfortunately as I’m finding out is only half the battle for the effect I’m going for…
What I’m actually doing with this is trying to come up with a way to mask the edges of led panels that have been mapped as points. the geometric panels are modular and several might form a larger cluster, that when viewed as a silhouette can form concavities, sometimes…
Sadly, the convex hull skips over these, so it doesn’t provide the desired effect in all situations.
Been working on this the last two days and not making much progress so THANK YOU!
I now have a planB, if concave doesn’t work, I can run this on a per panel basis and at least get a per panel outline that should work perfectly.
Also, it’s ironic you pointed out the Group SOP’s ability to select unshared edges… that’s exactly the thing I’ve been stuck on all morning with scipy implementation.
I’ve managed to calculate the Delauney triangulation as an array of triangle coordinates, but having trouble getting unshared edges, which marks the boundary edge.
Two problems still with this though is :
A) I have to talk to another python process outside of touch because of library version issues for numpy/sciPy
B) I don’t believe that even if I get the border edges/points that they will be ordered to form a loop or multiple loops, but that might be doable with some simple path finding algorithm?
So a little progress, I got the library working and generated this delauney mesh:
closer!
currently, each triangle by means of the script sop is a separate poly, so there are lots of overlapping identical points, and nothing is actually connected.
So what is the answer you’re looking to achieve in that specific case?
A single path/poly that outlines a thick letter ‘C’ ?
[EDIT: Or are you looking for 5 squares?]
A vertex is a reference to a single point.
Multiple vertices can all refer to the same point (shared vertices).
Since the squares are separated by a specified amount they’d be considered separately, but if they were within that threshold then ideally they’d be treated as one big unit.
I can see that with the script SOP I can add a polygon to the sop of N length, assuming that’s points. I can also see from your example how you can specify a polygon by making a loop, but if you want to create a tessellated surface with interconnected points, like the grid SOP is that possible?
Is there a way to define primitives and vertex’s on top of that?
Essentially I’m creating the points that were in the original mesh
then iterating through triangle table, creating a poly for each tri.
I leave addPoints=False, so that i can set vertex <> point reference right after
I try to set point reference but I get error saying “td.error: Invalid Vertex object.”
Is this a bug? Or am I using it wrong?
I dug around in the wiki for a while trying to piece it together, but there’s not a whole bunch of info at the point/vertex/prim/poly level so I might have mis understood something.
# create the points in a first pass, so that we don't have duplicates.
for point in range(triangulateThis.numRows):
# Create and move points, then append to master list of point objects for later reference.
pt = scriptOp.appendPoint()
pt.x = triangulateThis[point,0]
pt.y = triangulateThis[point,1]
listOfPointObjects.append(pt)
# Now that points are made, iterate through triangles table and create polys / vert references to the existing point table.
for x in range(triList.numRows):
# query point indicies from tri list (contains references to master point list)
pt1 = int(triList[x,0].val)
pt2 = int(triList[x,1].val)
pt3 = int(triList[x,2].val)
# create a single triangle poly, with out making new points.
poly = scriptOp.appendPoly(3, closed=True, addPoints=False)
# assign correct points to recently made poly. (This is doesn't work)
poly[0].point = pt1
poly[1].point = pt2
poly[2].point = pt3
return
Hi Lucas.
As just mentioned in the other thread, the vertex issue is now fixed in the next upcoming build (56080+). You’ll still have to assign points to the vertex.point members, not ints though.
Just to be clear though, would the previous example outputting 5 squares be the solution you’re looking for?
That previous example with 5 squares is an example layout I ripped straight from the network I’m working on. Of course the layout could be literally anything, those squares might be edge to edge in a long rectangle too, and then the edge of the whole cluster would need to get highlighted instead.
That distinction between islands I’m planning to handle with some threshold logic using the area of each triangle and deleting ones that are too big.
Then after that getting the bordering points using the SOP method you mentioned should result in exactly what I need I think
![http://www.enviral-design.com/blog/wp-content/uploads/2015/10/getBorder.png[/url]](http://www.enviral-design.com/blog/wp-content/uploads/2015/10/getBorder.png%5B/url%5D){kind=link}