my algorithm is almost identical to your recent one… just a little cleaner which makes it a bit faster and memory friendly
fn collectEdgePairs3 mesh =
(
local pairs = #()
local verts = #()
local edges = #()
pairs.count = mesh.numfaces * 3
opened = meshop.getopenedges mesh
for e in opened do pairs[e] = 0
fn putEdge e v pairs edges verts = if pairs[e] == undefined do
(
if (k = finditem verts [v[2],v[1]]) != 0 then
(
pairs[e] = edges[k]
pairs[edges[k]] = e
deleteitem verts k
deleteitem edges k
)
else
(
append verts v
append edges e
)
)
for f=1 to mesh.numfaces do
(
vv = getface mesh f
f *= 3
putEdge (f - 2) [vv[1],vv[2]] pairs edges verts
putEdge (f - 1) [vv[2],vv[3]] pairs edges verts
putEdge (f - 0) [vv[3],vv[1]] pairs edges verts
)
pairs
)
That’s what I was talking about. You see; lovely cleaver approach.
I believe mine is slow due to the degenerated faces test condition.
Regarding the memory usage, why did you say mine uses half the memory that yours when actually yours uses less memory?
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)…
i’ve optimized my previous version by setting all open edges first and processing only empty items…
I see. I though you would be showing your original approach which was 18 times faster than the Max function instead of your most optimized version which is over 80 times faster than meshop.getedgesreverseedge for a geosphere with 10 segments. Thank you for showing the latest update.
my previous test object didn’t have open edges… so the processing separately of open and not open edges didn’t make a difference. also for small meshes (< 2K edges) the ‘custom advanced’ algorithm doesn’t give this dramatic advantage.
and here is a test object:
(
delete objects
s = converttomesh (geosphere segments:20)
seed 0
ff = for k=1 to 400 collect (random 1 s.numfaces)
meshop.deletefaces s ff
update s
gc()
t1 = timestamp()
m1 = heapfree
format "%
" (edges = collectEdgePairs3 s)
format "edges:% time:% memory:%
" s.edges.count (timestamp() - t1) (m1 - heapfree)
)
here is a new challenge:
find a reverse edge index to the specified mesh edge. return Zero if there is no a reverse one
This one is for edges array:
(
fn collectEdgePairs mesh edges =
(
openEdges = (meshop.getopenedges mesh) * edges
validEdges = edges + (meshop.getedgesreverseedge mesh edges)
falidFaces = meshop.getfacesusingedge mesh validEdges
tmpEdges = #()
tmpVerts = #()
edges = #()
for f in falidFaces do (
faceVerts = getface mesh f
e3 = f*3
e2 = e3-1
e1 = e3-2
if validEdges[e1] do (
if openEdges[e1] then (
append edges #(e1, 0)
)else(
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
)
)
)
if validEdges[e2] do (
if openEdges[e2] then (
append edges #(e2, 0)
)else(
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
)
)
)
if validEdges[e3] do (
if openEdges[e3] then (
append edges #(e3, 0)
)else(
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
)
edges = collectEdgePairs $ (getedgeselection $)
)
no… i’m asking for only one edge. and the function must be faster than meshop.getEdgesReverseEdge
How fast is your current function compared with meshop.getEdgesReverseEdge?
(
s = converttomesh (geosphere segments:50)
t1 = timestamp()
m1 = heapfree
--reversededge = getReverseEdge s 1000
reversededge = meshop.getEdgesReverseEdge s 1000
format "edge:% time:% memory:%
" reversededge (timestamp() - t1) (m1 - heapfree)
)
my is about two times faster… probably it’s best what i can do
Would you mind showing some results so I have a base to compare with?
(
delete objects
s = converttomesh (geosphere segments:100)
re = for x = 1 to 100 collect random 1 (s.edges.count)
t1 = timestamp(); m1 = heapfree
reversededge = for x in re collect getReverseEdge s x
format "CUSTOM: time:% memory:%
edges:%
" (timestamp()-t1) (m1-heapfree) reversededge
t1 = timestamp(); m1 = heapfree
reversededge = for x in re collect ((meshop.getEdgesReverseEdge s x) as array)[1]
format "MESHOP: time:% memory:%
edges:%
" (timestamp()-t1) (m1-heapfree) reversededge
gc()
)
fn getReverseEdge0 mesh e =
(
ee = meshop.getedgesreverseedge mesh e
if ee.isempty then 0 else (ee as array)[1]
)
fn getReverseEdge1 mesh e =
(
vv = (meshop.getvertsusingedge mesh e) as array
ee = meshop.getedgesusingvert mesh vv[1] * meshop.getedgesusingvert mesh vv[2]
k = 0
for i in ee while k == 0 where i != e do k = i
k
)
(
delete objects
s = converttomesh (geosphere segments:50)
local edge
gc()
t1 = timestamp()
m1 = heapfree
for k=1 to 100 do edge = getReverseEdge0 s 1000
format "edges:% reverse:% time:% memory:%
" s.edges.count edge (timestamp() - t1) (m1 - heapfree)
gc()
t1 = timestamp()
m1 = heapfree
for k=1 to 100 do edge = getReverseEdge1 s 1000
format "edges:% reverse:% time:% memory:%
" s.edges.count edge (timestamp() - t1) (m1 - heapfree)
)
probably i can optimize the memory usage…
here is the better one:
fn getReverseEdge2 mesh e =
(
vv = meshop.getvertsusingedge mesh e
ff = meshop.getfacesusingvert mesh vv
k = 0
for f in ff while k == 0 do
(
v = getface mesh f
f *= 3
if k == 0 and (i = f - 2) != e and (vv * #{v[1],v[2]}).numberset == 2 do k = i
if k == 0 and (i = f - 1) != e and (vv * #{v[2],v[3]}).numberset == 2 do k = i
if k == 0 and (i = f - 0) != e and (vv * #{v[3],v[1]}).numberset == 2 do k = i
)
k
)
Here is my approach:
(
fn getReverseEdge0 mesh e =
(
ee = meshop.getedgesreverseedge mesh e
if ee.isempty then 0 else (ee as array)[1]
)
fn getReverseEdge1 mesh edge =
(
edgeFace = ceil (edge/3.0)
faceVerts = getface mesh edgeFace
e3 = edgeFace*3
e2 = e3-1
e1 = e3-2
if edge == e1 do edgeVerts = [faceVerts.y, faceVerts.x]
if edge == e2 do edgeVerts = [faceVerts.z, faceVerts.y]
if edge == e3 do edgeVerts = [faceVerts.x, faceVerts.z]
validFaces = meshop.getfacesusingvert mesh edgeVerts[1]
for f in validFaces do (
local faceVerts = getface mesh f
if edgeVerts == [faceVerts.x, faceVerts.y] do return f*3-2
if edgeVerts == [faceVerts.y, faceVerts.z] do return f*3-1
if edgeVerts == [faceVerts.z, faceVerts.x] do return f*3
)
return 0
)
delete objects
s = converttomesh (geosphere segments:50)
local edge
gc()
t1 = timestamp()
m1 = heapfree
for k=1 to 100 do edge = getReverseEdge0 s 1000
format "edges:% reverse:% time:% memory:%
" s.edges.count edge (timestamp() - t1) (m1 - heapfree)
gc()
t1 = timestamp()
m1 = heapfree
for k=1 to 100 do edge = getReverseEdge1 s 1000
format "edges:% reverse:% time:% memory:%
" s.edges.count edge (timestamp() - t1) (m1 - heapfree)
)
super!
fn getReverseEdge2 mesh e =
(
vv = meshop.getvertsusingedge mesh e
ff = meshop.getfacesusingvert mesh vv
k = 0
for f in ff while k == 0 do
(
v = getface mesh f
case of
(
(vv[v[1]]): case of
(
(vv[v[2]]): if (i = f*3 - 2) != e do k = i
(vv[v[3]]): if (i = f*3 - 0) != e do k = i
)
(vv[v[2]]): if vv[v[3]] and (i = f*3 - 1) != e do k = i
)
)
k
)
great time and good memory use!
superbly! great work!
HA! my method beats yours on smaller meshes
< 10K edges : ~1.5 times faster
< 1K edges : ~5 times faster