Yes, I just realized it. Also this would produce the same results:
verts = #([-10,-10,0], [-10,10,0], [10,10,0])
faces = #([1,2,3], [1,2,3], [1,2,3])
tmesh = mesh vertices:verts faces:faces
Here “meshop.getedgesreverseedge” also fails, as it only returns one reversed edge per edge.
The issue with the teapot is different though. The code fails due to degenerate faces.
Denis, what was your original idea?
I mean, were you asking to improve the meshop function speed or also to improve the results?
Ideally both I guess, but as “getedgesreverseedge” does not work when an edge is shared by more than 2 faces you may only wanted to improve the speed.
Ruramuq,
Reading your last post again, I realize I may not understand what the function should return.
Using your test mesh:
(
fn collectEdgePairs mesh =
(
edges = (mesh.edges as bitarray) - (meshop.getopenedges mesh)
for e in edges collect #(e, ((meshop.getedgesreverseedge mesh e) as array)[1])
)
pln = plane widthsegs:2 lengthsegs:1
convertToMesh pln
meshop.extrudeEdges pln #{4} 10
collectEdgePairs pln
)
The result is:
#(#(2, 5), #(4, 16), #(5, 2), #(7, 4), #(8, 11), #(11, 8), #(15, 18), #(16, 4), #(18, 15))
Is that result correct or do you mean it should be something like:
#(#(2, 5), #(4, 7, 16), #(8, 11), #(15, 18))
I understand the last one is not an array of reversed edges, but edges sharing the same points, but I want to confirm what should be the expected result from the function.
Other considerations:
Should the function work with degenerate faces or should it avoid them? i.e. face [2,2,1]
How do we know which reverse edge belongs to another?
edgeA = [1,2]
edgeB = [2,1]
edgeC = [1,2]
edgeD = [2,1]
Is edgeB the reversed edge of edgeA or edgeC?
That was a suggestion, or question, because that seems more logical, for the reason that and edge can have more than 1 reversed edge.
But if the goal is to replicate exactly what GetEdgeReverseEdge does, then I think it’s fine.
Similarly for the case of degenerated faces.
Other considerations:
Should the function work with degenerate faces or should it avoid them? i.e. face [2,2,1]
How do we know which reverse edge belongs to another?
edgeA = [1,2]
edgeB = [2,1]
edgeC = [1,2]
edgeD = [2,1]Is edgeB the reversed edge of edgeA or edgeC?
The way I see it is that all edges sharing the same 2 edgeVertices should be considered a single edge.
▬
About my previous post, I was noticing that maybe your code would not work for these non-manifold meshes.
For example:
Using the edge in the middle(3 edges) : #{4, 7, 16}
for e in #{4, 7, 16} collect meshop.getedgesreverseedge $ e
But, your function returns, #(#(2, 5), #(4, 16), #(8, 11), #(15, 18))
If I’m not missing something, I think It’s not giving us the reverseEdge of edge #7
Well, it was 99% a question and 1% a suggestion, as I really did not understand what your idea was, because you said:
“…the 3 quads share the same edge(actually 3 edges) each should return a reverseEdge…”
What I understand for reversed edge is an edge sharing the same vertices as another edge but with reversed order, due to the faces being built in the same order.
In this case, edge [1, 2] could only have one reversed edge [2, 1], but when there are several edges sharing the same vertices I do not know which should be the logic to determine which edge is the reversed edge of which. One way could be to use the face number so if face1 has edge1 [1, 2], face3 has edge2 [2, 1] and face5 has edge3 [2, 1], the reverse edge of face1 should be edge2. But this also seems wrong, because which one would be the reverse edge for edge3?
This is why I believe the max function returns wrong results in these particular cases.
#(#(2, 5), #(4, 16), #(5, 2), #(7, 4), #(8, 11), #(11, 8), #(15, 18), #(16, 4), #(18, 15))
How it is possible that the reversed edge of 4 is 16 and the reversed edge of 7 is 4?
I agree with you, perhaps all the edges sharing the same two vertices should be treated as reversed edges.
I would like to hear from Denis what was his original idea, and also continuing this constructive discussion so we can arrive to a useful result.
About my previous post, I was noticing that maybe your code would not work for these non-manifold meshes.
For example:Using the edge in the middle(3 edges) : #{4, 7, 16}
for e in #{4, 7, 16} collect meshop.getedgesreverseedge $ eBut, your function returns, #(#(2, 5), #(4, 16), #(8, 11), #(15, 18))
If I’m not missing something, I think It’s not giving us the reverseEdge of edge #7
You are absolutely right. The function does not work in these cases because I was not aware of them at the time of coding it. Thats why I am trying to be on the same page as far as what kind of results are expected to be returned by the function.
Ok, to sum it up, what we are looking here is to build a function that returns all the edges sharing the same two vertices, which by itself would be an improvement over the meshop.getedgesreverseedge function, and also make it run faster than it.
Following this, I would also remove the degenerated faces, as they are not valid geometry.
Is that correct?
Well, it was 99% a question and 1% a suggestion, as I really did not understand what your idea was, because you said:
“…the 3 quads share the same edge(actually 3 edges) each should return a reverseEdge…”
It’s my fault, for not clarifying well. When I say “edge”, is was in abstract sense, because for a modeler, knowing that the mesh, in fact has 2+ edges in the same place, is confusing.
What I understand for reversed edge is an edge sharing the same vertices as another edge but with reversed order, due to the faces being built in the same order.
In this case, edge [1, 2] could only have one reversed edge [2, 1], but when there are several edges sharing the same vertices I do not know which should be the logic to determine which edge is the reversed edge of which. One way could be to use the face number so if face1 has edge1 [1, 2], face3 has edge2 [2, 1] and face5 has edge3 [2, 1], the reverse edge of face1 should be edge2. But this also seems wrong, because which one would be the reverse edge for edge3?
All edges going in opposite direction. I would say. Even if that means more than one.
For example next case,
Face 1 and face 2 and face 3, all share '2 vertices',
All these faces are created counter-clockwise,
Face 2 normal, and face 3 normal, are continuous with face 1 normal.(no flip)
Then we can say that face2 and face 3 'edges', are going in reversed direction if we compare them to face 1 'edge'.
This means that the edge of face 1 has 2 reversed edges.
But if face 1 is connected to a face with normal flip (due to different order), then I suppose that technically that's not a reverseEdge, because we could see that the 'edges' are going in the same direction.
The question is, in what cases we need this distinction?
Ok, to sum it up, what we are looking here is to build a function that returns all the edges sharing the same two vertices, which by itself would be an improvement over the meshop.getedgesreverseedge function, and also make it run faster than it.
Following this, I would also remove the degenerated faces, as they are not valid geometry.Is that correct?
I don't know exactly, maybe I'm missing something obvious, but to me that seems correct, and easier for any future edit_mesh operation.
About degenerated faces, I would probably try to work with them. I'm not sure if it's the best idea to remove them in this case.Here is an optimized version of my first script. Same as the original script, it does not work when more than two edges shared the same two vertices, but seems to work with other geometries. Even though, I won’t claim it has no bugs, so is up to the reader to test it further.
(
fn collectEdgePairs mesh =
(
tmpEdges = #()
tmpVerts = #()
edges = #()
validEdges = (mesh.edges as bitarray) - (meshop.getopenedges mesh)
for f = 1 to mesh.numfaces do (
faceVerts = getface mesh f
e3 = f*3
e2 = e3-1
e1 = e3-2
if faceVerts.x != faceVerts.y and faceVerts.y != faceVerts.z and faceVerts.z != faceVerts.x do (
-- edge 1
if validEdges[e1] do (
found = finditem tmpVerts [faceVerts.y, faceVerts.x]
if found == 0 then (
append tmpVerts [faceVerts.x, faceVerts.y]
append tmpEdges #(e1, undefined)
)else(
append edges #(tmpEdges[found][1], e1)
deleteitem tmpEdges found
deleteitem tmpVerts found
)
)
-- edge 2
if validEdges[e2] do (
found = finditem tmpVerts [faceVerts.z, faceVerts.y]
if found == 0 then (
append tmpVerts [faceVerts.y, faceVerts.z]
append tmpEdges #(e2, undefined)
)else(
append edges #(tmpEdges[found][1], e2)
deleteitem tmpEdges found
deleteitem tmpVerts found
)
)
-- edge 3
if validEdges[e3] do (
found = finditem tmpVerts [faceVerts.x, faceVerts.z]
if found == 0 then (
append tmpVerts [faceVerts.z, faceVerts.x]
append tmpEdges #(e3, undefined)
)else(
append edges #(tmpEdges[found][1], e3)
deleteitem tmpEdges found
deleteitem tmpVerts found
)
)
)
)
return edges
)
)
Results for geosphere segments 10-15-20-25:
edges:6000 time:15 memory:936784L
edges:13500 time:47 memory:2106784L
edges:24000 time:78 memory:3744784L
edges:37500 time:156 memory:5850848L
[b] Results using 'meshop.getedgesreverseedge' for geosphere segments 10-15-20-25[/b]
(
fn collectEdgePairs mesh =
(
for e in mesh.edges as bitarray collect #(e, ((meshop.getedgesreverseedge mesh e) as array)[1])
)
s = converttomesh (geosphere segments:25)
t1 = timestamp()
m1 = heapfree
edges = collectEdgePairs s
format "edges:% time:% memory:%
" s.edges.count (timestamp() - t1) (m1 - heapfree)
)
edges:6000 time:1545 memory:2304448L
edges:13500 time:7893 memory:5184488L
edges:24000 time:24789 memory:9216448L
edges:37500 time:60715 memory:14473696L
Here is a function that should return all edges sharing the same two vertices. Unfortunately it is much slower than the previous code, yet much faster than meshop.getedgesreverseedge.
If you are interested in this topic, please contribute with testing or ideas.
(
fn collectEdgePairs mesh =
(
tmpVerts = #()
edges = for x = 1 to mesh.edges.count collect #()
validEdges = (mesh.edges as bitarray) - (meshop.getopenedges mesh)
for f = 1 to mesh.numfaces do (
faceVerts = getface mesh f
e3 = f*3
e2 = e3-1
e1 = e3-2
vx = faceVerts.x
vy = faceVerts.y
vz = faceVerts.z
if vx != vy and vy != vz and vz != vx do (
-- edge 1
if validEdges[e1] do (
found = finditem tmpVerts [vy, vx]
if found == 0 do found = finditem tmpVerts [vx, vy]
if found == 0 then (
tmpVerts[e1] = [vx, vy]
append edges[e1] e1
)else(
append edges[found] e1
)
)
-- edge 2
if validEdges[e2] do (
found = finditem tmpVerts [vz, vy]
if found == 0 do found = finditem tmpVerts [vy, vz]
if found == 0 then (
tmpVerts[e2] = [vy, vz]
append edges[e2] e2
)else(
append edges[found] e2
)
)
-- edge 3
if validEdges[e3] do (
found = finditem tmpVerts [vx, vz]
if found == 0 do found = finditem tmpVerts [vz, vx]
if found == 0 then (
tmpVerts[e3] = [vz, vx]
append edges[e3] e3
)else(
append edges[found] e3
)
)
)
)
edges for i in edges where i.count > 0 collect i
return edges
)
)
I have that feeling that this code could be greatly optimized. For instance, getting a unique value for swapped numbers would simplify the finditem procedure and speed it up a bit.
I wonder the same thing. Besides the fact that these kind of meshes are rare to see this days.
I don’t know either. Might someone else bring some ideas on this.
I have updated both functions to work with or without degenerated faces, with a little impact in performance.
Fastest version (dont work with 3+ reversed edges):
(
fn collectEdgePairs mesh ignoreDegenerateFaces:true =
(
tmpEdges = #()
tmpVerts = #()
edges = #()
validEdges = (mesh.edges as bitarray) - (meshop.getopenedges mesh)
for f = 1 to mesh.numfaces do (
faceVerts = getface mesh f
e3 = f*3
e2 = e3-1
e1 = e3-2
validFace = true
if ignoreDegenerateFaces do (
if faceVerts.x==faceVerts.y or faceVerts.y==faceVerts.z or faceVerts.z==faceVerts.x do validFace = not validFace
)
if validFace do (
-- edge 1
if validEdges[e1] do (
found = finditem tmpVerts [faceVerts.y, faceVerts.x]
if found == 0 then (
append tmpVerts [faceVerts.x, faceVerts.y]
append tmpEdges #(e1, undefined)
)else(
append edges #(tmpEdges[found][1], e1)
deleteitem tmpEdges found
deleteitem tmpVerts found
)
)
-- edge 2
if validEdges[e2] do (
found = finditem tmpVerts [faceVerts.z, faceVerts.y]
if found == 0 then (
append tmpVerts [faceVerts.y, faceVerts.z]
append tmpEdges #(e2, undefined)
)else(
append edges #(tmpEdges[found][1], e2)
deleteitem tmpEdges found
deleteitem tmpVerts found
)
)
-- edge 3
if validEdges[e3] do (
found = finditem tmpVerts [faceVerts.x, faceVerts.z]
if found == 0 then (
append tmpVerts [faceVerts.z, faceVerts.x]
append tmpEdges #(e3, undefined)
)else(
append edges #(tmpEdges[found][1], e3)
deleteitem tmpEdges found
deleteitem tmpVerts found
)
)
)
)
return edges
)
)
Slower version (works with 3+ reversed edges):
(
fn collectEdgePairs mesh ignoreDegenerateFaces:false =
(
tmpVerts = #()
edges = for x = 1 to mesh.edges.count collect #()
validEdges = (mesh.edges as bitarray) - (meshop.getopenedges mesh)
for f = 1 to mesh.numfaces do (
faceVerts = getface mesh f
e3 = f*3
e2 = e3-1
e1 = e3-2
vx = faceVerts.x
vy = faceVerts.y
vz = faceVerts.z
validFace = true
if ignoreDegenerateFaces do if vx==vy or vy==vz or vz==vx do validFace = not validFace
if validFace do (
-- edge 1
if validEdges[e1] do (
found = finditem tmpVerts [vy, vx]
if found == 0 do found = finditem tmpVerts [vx, vy]
if found == 0 then (
tmpVerts[e1] = [vx, vy]
append edges[e1] e1
)else(
append edges[found] e1
)
)
-- edge 2
if validEdges[e2] do (
found = finditem tmpVerts [vz, vy]
if found == 0 do found = finditem tmpVerts [vy, vz]
if found == 0 then (
tmpVerts[e2] = [vy, vz]
append edges[e2] e2
)else(
append edges[found] e2
)
)
-- edge 3
if validEdges[e3] do (
found = finditem tmpVerts [vx, vz]
if found == 0 do found = finditem tmpVerts [vz, vx]
if found == 0 then (
tmpVerts[e3] = [vz, vx]
append edges[e3] e3
)else(
append edges[found] e3
)
)
)
)
edges = for i in edges where i.count > 0 collect i
return edges
)
)
first of all… we have the winner – Jorge Rodríguez…
his algorithm is fast and memory friendly (mine is a bit faster but it’s two times worse of memory use)…
the question is … why do we need it’s being better than max does do it? (be continued…)
Where should I claim my prize?
Joking aside, I am glad we arrived to a useful solution, even when my logic initially failed as mentioned by Ruramuq.
Now, as you know the code does not work with 3+ reversed edges, neither does the Max build in function. At this point and besides 3+ reversed edges are not the most common of the geometries; Ruramuq has a good point bringing this to the discussion.
How I see it is the same as he mention, all edges sharing the same two vertices should be in the same group, but I am unsure of how useful it is in real life.
On a side, are you going to publish your code? Even if you say it is less memory efficient, you have a very cleaver programming approach from where I (and many of us here, I believe) constantly learn. You know how much difference one line of code can make.
Did I mention I would like to claim my prize?
before i show my algorithm could you change your function output to look like:
an array of edge indexes in order of edge index where item index corresponds to reverse edge index or 0 if the edges doesn’t have a reverse edge.
so #(0, 3, 2, 0…) means:
edge 1 doesn’t have a reverse edge,
edge 2 has reverse edge 3,
edge 3 has reverse edge 2,
edge 4 doesn’t have a reverse edge, etc.
I guess you are referring to the code that does not work with 3+ reversed edges?
Ok, here is one quick update, probably a better implementation would lead to a more efficient function, but it takes almost the same time (a bit slower) and uses almost the same memory as the original function.
(
fn collectEdgePairs mesh ignoreDegenerateFaces:true =
(
tmpEdges = #()
tmpVerts = #()
edges = #()
validEdges = (mesh.edges as bitarray) - (meshop.getopenedges mesh)
for f = 1 to mesh.numfaces do (
faceVerts = getface mesh f
e3 = f*3
e2 = e3-1
e1 = e3-2
validFace = true
if ignoreDegenerateFaces do (
if faceVerts.x==faceVerts.y or faceVerts.y==faceVerts.z or faceVerts.z==faceVerts.x do validFace = not validFace
)
if validFace do (
-- edge 1
if validEdges[e1] do (
found = finditem tmpVerts [faceVerts.y, faceVerts.x]
if found == 0 then (
append tmpVerts [faceVerts.x, faceVerts.y]
append tmpEdges #(e1, undefined)
)else(
append edges #(tmpEdges[found][1], e1)
deleteitem tmpEdges found
deleteitem tmpVerts found
)
)
-- edge 2
if validEdges[e2] do (
found = finditem tmpVerts [faceVerts.z, faceVerts.y]
if found == 0 then (
append tmpVerts [faceVerts.y, faceVerts.z]
append tmpEdges #(e2, undefined)
)else(
append edges #(tmpEdges[found][1], e2)
deleteitem tmpEdges found
deleteitem tmpVerts found
)
)
-- edge 3
if validEdges[e3] do (
found = finditem tmpVerts [faceVerts.x, faceVerts.z]
if found == 0 then (
append tmpVerts [faceVerts.z, faceVerts.x]
append tmpEdges #(e3, undefined)
)else(
append edges #(tmpEdges[found][1], e3)
deleteitem tmpEdges found
deleteitem tmpVerts found
)
)
)
)
result = for j = 1 to mesh.edges.count collect 0
for e in edges do (
result[e[1]] = e[2]
result[e[2]] = e[1]
)
return result
)