Several times on this forum was asked about getting ‘ordered chain of edges’
There are some solutions here, but they are not complete or done well.
So the challenge is:
we have an poly edge selection.
we need to:
split them on continuous groups (every group doesn’t have a connection to another group)
make them ordered (where one edge goes after another from side to side)
…
there is another condition … but i will tell about it later
The easy part is to keep growing/checking by picking one edge and its vert and expanding until we reach the same vert/border (in which case we’d need to go the other direction from the 1st vert as well), then remove from candidate edges and repeat until those are empty. However testing if the next connected selected edge is a part of this loop or part of another loop feels quite tricky since there are a few corner cases there… testing for each means it will be quite expensive, especially on complex meshes – I think you have to check if next edge doesn’t share any polygon with the current edge, and exactly four edges meet at their connection (or three, if they’re both border edges).
it’s almost the same idea I’ve had and implemented:
fn getvertedges node v =
(
for k=1 to (node.getVertexEdgeCount v) collect node.getvertexedge v k
)
fn addLoopEdge node edge edges done_verts loop dir:0 =
(
if edges[edge] do
(
edges[edge] = off
if dir >= 0 then append loop edge
else insertitem edge loop 1
vv = polyop.getedgeverts node edge
if not done_verts[vv[1]] do
(
done_verts[vv[1]] = on
ee = getvertedges node vv[1]
for e in ee do addLoopEdge node e edges done_verts loop dir:(if dir == 0 then 1 else dir)
)
if not done_verts[vv[2]] do
(
done_verts[vv[2]] = on
ee = getvertedges node vv[2]
for e in ee do addLoopEdge node e edges done_verts loop dir:(if dir == 0 then -1 else dir)
)
)
)
fn getEdgeLoops node edges: =
(
if edges == unsupplied do edges = node.selectededges as bitarray
loops = #()
done_verts = #{}
while (edge = firstbit edges) != undefined do
(
loop = #()
append loops loop
addLoopEdge node edge edges done_verts loop dir:0
)
loops
)
it works… but…
later i’ve found something better
should be able to use this from EditablePoly source
bool CreateCurveFromMeshEdges (MNMesh & mesh, INode *onode, Interface *ip, TSTR & name, bool curved, DWORD flag) {
SuspendAnimate();
AnimateOff();
HoldSuspend hs; // LAM - 6/12/04 - defect 571821
SplineShape *shape = (SplineShape*)GetSplineShapeDescriptor()->Create(0);
BitArray done;
done.SetSize (mesh.nume);
for (int i=0; i<mesh.nume; i++) {
if (done[i]) continue;
if (mesh.e[i].GetFlag (MN_DEAD)) continue;
if (!mesh.e[i].GetFlag (flag)) continue;
// The array of points for the spline
Tab<Point3> pts;
// Add the first two points.
pts.Append(1,&mesh.v[mesh.e[i].v1].p,10);
pts.Append(1,&mesh.v[mesh.e[i].v2].p,10);
int nextv = mesh.e[i].v2, start = mesh.e[i].v1;
// Mark this edge as done
done.Set(i);
// Trace along selected edges
// Use loopcount/maxLoop just to avoid a while(1) loop.
int loopCount, maxLoop=mesh.nume;
for (loopCount=0; loopCount<maxLoop; loopCount++) {
Tab<int> & ve = mesh.vedg[nextv];
int j;
for (j=0; j<ve.Count(); j++) {
if (done[ve[j]]) continue;
if (mesh.e[ve[j]].GetFlag (flag)) break;
}
if (j==ve.Count()) break;
if (mesh.e[ve[j]].v1 == nextv) nextv = mesh.e[ve[j]].v2;
else nextv = mesh.e[ve[j]].v1;
// Mark this edge as done
done.Set(ve[j]);
// Add this vertex to the list
pts.Append(1,&mesh.v[nextv].p,10);
}
int lastV = nextv;
// Now trace backwards
nextv = start;
for (loopCount=0; loopCount<maxLoop; loopCount++) {
Tab<int> & ve = mesh.vedg[nextv];
int j;
for (j=0; j<ve.Count(); j++) {
if (done[ve[j]]) continue;
if (mesh.e[ve[j]].GetFlag (flag)) break;
}
if (j==ve.Count()) break;
if (mesh.e[ve[j]].v1 == nextv) nextv = mesh.e[ve[j]].v2;
else nextv = mesh.e[ve[j]].v1;
// Mark this edge as done
done.Set(ve[j]);
// Add this vertex to the list
pts.Insert(0,1,&mesh.v[nextv].p);
}
int firstV = nextv;
// Now weve got all th points. Create the spline and add points
Spline3D *spline = new Spline3D(KTYPE_AUTO,KTYPE_BEZIER);
int max = pts.Count();
if (firstV == lastV) {
max--;
spline->SetClosed ();
}
if (curved) {
for (int j=0; j<max; j++) {
int prvv = j ? j-1 : ((firstV==lastV) ? max-1 : 0);
int nxtv = (max-1-j) ? j+1 : ((firstV==lastV) ? 0 : max-1);
float prev_length = Length(pts[j] - pts[prvv])/3.0f;
float next_length = Length(pts[j] - pts[nxtv])/3.0f;
Point3 tangent = Normalize (pts[nxtv] - pts[prvv]);
SplineKnot sn (KTYPE_BEZIER, LTYPE_CURVE, pts[j],
pts[j] - prev_length*tangent, pts[j] + next_length*tangent);
spline->AddKnot(sn);
}
} else {
for (int j=0; j<max; j++) {
SplineKnot sn(KTYPE_CORNER, LTYPE_LINE, pts[j],pts[j],pts[j]);
spline->AddKnot(sn);
}
spline->ComputeBezPoints();
}
shape->shape.AddSpline(spline);
}
shape->shape.InvalidateGeomCache();
shape->shape.UpdateSels();
hs.Resume();
INode *node = ip->CreateObjectNode (shape);
hs.Suspend();
INode *nodeByName = ip->GetINodeByName (name);
if (nodeByName != node) {
if (nodeByName) ip->MakeNameUnique(name);
node->SetName (name);
}
Matrix3 ntm = onode->GetNodeTM(ip->GetTime());
node->SetNodeTM (ip->GetTime(),ntm);
node->FlagForeground (ip->GetTime(),FALSE);
node->SetMtl (onode->GetMtl());
node->SetObjOffsetPos (onode->GetObjOffsetPos());
node->SetObjOffsetRot (onode->GetObjOffsetRot());
node->SetObjOffsetScale (onode->GetObjOffsetScale());
ResumeAnimate();
return true;
}
Shape from edges behaves very weird with the intersecting edgeloops
You can compare to what I have
fn growEdge obj index edges = (
edg = #{ index }
edgeVerts = polyop.getVertsUsingEdge obj index
vertsEdges = (polyop.getEdgesUsingVert obj edgeVerts) * edges
for ve in vertsEdges do (
edg += growEdge obj ve (edges - edg)
)
edg
)
fn splitByLoops obj edges = (
tmpEdgesSel = copy edges
edgeGroups = #()
for edg in tmpEdgesSel where tmpEdgesSel[edg] do (
polyop.setEdgeSelection obj edg
obj.EditablePoly.SelectEdgeLoop()
gr = polyop.getEdgeSelection obj
append edgeGroups (gr * edges)
tmpEdgesSel -= (gr * edges)
)
edgeGroups
)
delete objects
obj = convertToPoly (Cylinder heightsegs:1 capsegs:5 sides:40 height:10 radius:100 isSelected:on wirecolor:black)
polyop.setEdgeSelection obj #{3, 7, 10, 13, 19, 22, 25, 28, 31, 34, 43, 46, 49, 55, 58, 61, 64, 67, 70, 73, 76, 88, 91, 94, 97, 100, 103, 106, 109, 112, 120, 482, 485, 489, 491, 495, 497..499, 501, 503, 507, 509, 511, 513, 515, 517, 519, 521, 523, 525, 527, 529, 531, 533, 541, 543, 545, 547, 549, 551, 553, 562, 565, 567, 569, 571, 575, 577..579, 581, 583, 585, 587, 589, 591, 593, 597, 599, 601, 603, 605, 607, 609, 611, 613, 623, 625, 627, 629, 631, 633, 639..640, 642, 645, 647, 649, 651, 653, 658..659, 661, 663, 665, 667, 669, 671, 673, 675, 677, 679, 689, 691, 693, 695, 697, 699, 701, 703, 705, 707, 709, 711, 713, 715, 720, 738}
sel = polyop.getEdgeSelection obj
split = splitByLoops obj sel
edgeGroups = #()
for spl in split do (
copysel = copy spl
for s in copysel where copysel[s] do (
gr = growEdge obj s copysel
copysel -= gr
append edgeGroups gr
)
)
select obj
max modify mode
subobjectlevel = 2
iters = 2
while not keyboard.escPressed and (iters -=1) > 0 do (
polyop.setEdgeSelection obj sel
ForceCompleteRedraw()
sleep 1
for eg in edgeGroups do (
polyop.setEdgeSelection obj eg
redrawViews()
sleep 0.25
)
)
for eg in edgeGroups do (
polyop.createShape obj eg
)
select shapes
of course i saw this… does anyone want to post a mxs version of this algorithm to make it easy for discussion?
You’re a tease The only other thing that comes to my mind is:
- while candidates not empty get edge from candidate edges (separate copy from selectedEdges)
- get edgeFaces, get edgeVerts
- get faceEdges and for both verts get vertEdges
- continue while ((selectedEdges * vertEdges on any side) – faceEdges) yields .numberSet one (and candidates[edge] is true), collect that (appending/prepending as usual), remove from candidates and continue in that direction
But I’m not sure if there’s any advantage.
What times do you get with the code from post #5 and the better one for this model?
(
delete objects
obj = converttopoly (Torus segs:100 sides:25 radius1:50 radius2:10)
obj.EditablePoly.SetSelection #Edge #{2}
obj.EditablePoly.SelectEdgeRing()
obj.EditablePoly.SelectEdgeLoop()
)
#5 is only mxs implementation of the algorithm… it’s very slow for my case
~3300 ms
c++ implementation of almost the same algorithm ~23 ms for loop of 100
(recursion in MXS kills performance)
new version c++ has the same speed but also sorts loops and calculate distances and length params.
second algorithm is a modified code from polyedops.cpp (#3 shown by Klvnk)
Code from post #5 takes 2552ms on my end. I have an old MXS prototype that takes 20ms (for unconnected loops), but it does not sort the edges. If I can make it sort the edges I’ll post it.
Reading a little of Graphic Schema Theory, I have found a method -using something similar to an Adjacency Matrix that becomes triangular- that gives to me, just for the case of closed-unconnected loops as in Jorge’s example, 90ms with sorted edges and verts (that should be 60ms aprox. in Jorge’s PC).
It shouldn’t be too difficult to do it work for open-unconnected edge selections.
(
fn findLoops obj &loop_edge &loop_vert =
(
edges_b = polyop.getEdgeSelection obj
edgeVerts_b = polyop.getVertsUsingEdge obj edges_b
edges = edges_b as array
edgeVerts = edgeVerts_b as array
edgeVerts_index = #{1..edgeVerts.count} as array
fn compareFn val index valArray: =
(
arrayVal = valArray[index]
case of (
(val < arrayVal): -1
(val > arrayVal): 1
default: 0
)
)
data = #()
start = #()
for i = 1 to edges.count do
(
vv = polyop.getedgeverts obj edges[i]
v1_index = bsearch vv[1] edgeVerts_index compareFn valArray:edgeVerts
v2_index = bsearch vv[2] edgeVerts_index compareFn valArray:edgeVerts
vv_index = if v1_index<v2_index then #(v1_index,v2_index) else #(v2_index,v1_index)
if data[vv_index[1]] == undefined then data[vv_index[1]] = #(edges[i], vv_index[2]) else (append start vv_index[1]; data[vv_index[1]][3] = edges[i])
)
loop_vert = #()
loop_edge = #()
for k = 1 to start.count do
(
loop_vert[k] = #(edgeVerts[start[k]])
loop_edge[k] = #(data[start[k]][1])
next = data[start[k]][2]
while not keyboard.escPressed and data[next] != undefined do
(
append loop_vert[k] edgeVerts[next]
append loop_edge[k] data[next][1]
next = data[next][2]
)
append loop_vert[k] edgeVerts[next]
append loop_edge[k] data[start[k]][3]
)
)
--- PolyTools3D TEST ----
delete objects
obj = converttopoly (Torus segs:100 sides:25 radius1:50 radius2:10)
obj.EditablePoly.SetSelection #Edge #{2}
obj.EditablePoly.SelectEdgeRing()
obj.EditablePoly.SelectEdgeLoop()
t1 = timestamp()
loop_edge = #()
loop_vert = #()
findLoops obj &loop_edge &loop_vert
t2 = timestamp(); format "Time= %
" (t2-t1)
-- loop_edge[k] ==> holds the sorted edges for the number 'k' loop: polyop.setEdgeSelection obj loop_edge[k] to select the edge loop
-- loop_vert[k] ==> holds the sorted verts for the number 'k' loop: polyop.setVertSelection obj loop_vert[k] to select the vert loop
)
It is fast. I actually get 36ms for the torus test
You may want to modify it to also work with this cases:
(
delete objects
obj = converttopoly (plane pos:[0,0,1] length:100 width:100 lengthsegs:9 widthsegs:9 wirecolor:yellow)
polyop.setedgeselection obj #{34, 36, 38, 40, 42, 52, 55, 57, 59, 62, 71, 73, 76, 79, 81, 90, 92, 94..96, 98, 100, 109, 111..112, 114, 116..117, 119, 128..129, 131, 133, 135, 137..138}
)
However, the other example posted by Denis is completely different. I got the algorithm to solve most cases, but there are a few that are a little hard. They can be solved, but needs more analysis of the path in question, especially if they are closed shapes.
EDIT:
Tried it with this object and it didn’t work.
(
delete objects
obj = converttopoly (torus segs:12 sides:8 wirecolor:yellow)
obj.EditablePoly.SetSelection #Face #{1..96}
obj.EditablePoly.meshsmooth #Face
obj.EditablePoly.SetSelection #Edge #{2}
obj.EditablePoly.SelectEdgeRing()
obj.EditablePoly.SelectEdgeLoop()
)
for me is interesting to solve this task:
(
delete objects
obj = converttopoly (plane length:80 width:80 lengthsegs:6 widthsegs:6)
obj.editablepoly.setselection #edge #{25, 27, 37, 41, 49..51, 53..54, 63}
)
where i want to have one loop from side to side
I thought you where talking about unconnected loops. I may got it wrong from the description.
But the code from post #5 does not solve the problem from post #10, and there are 2 possible solutions I can see. Which one would be the correct one?