Hi
Can anybody look to my script and help me if is it possible make my search faster or use different way which do the same but faster ? I try simulate something like weld function but in my case I want select all vertex which got smaller distance for which I am looking but not weld them. In my script I just go through all mesh and try find distance between all vertex and catch these which are under range, but unfortunately it start to be very slow over 5000 vertex and I am sure must to be different way how I can do this but faster. Thanks for your help [font=Wingdings]J[/font]
VertFrom = 1
VertTo = 2
vertlist = #{}
VertSet = #{}
vertCount = meshop.getNumVerts $
vertlist = $.verts as bitarray
for i = 2 to vertcount do
(
for j = VertFrom to vertcount-1 do
(
VertDistance = meshop.minVertexDistanceFrom $ VertFrom VertTo
--print VertFrom
--print VertTo
--print VertDistance
if VertDistance < 0.5 then (appendIfUnique vertSet VertFrom)
if VertDistance < 0.5 then (appendIfUnique vertSet VertTo)
VertTo = VertTo + 1
)
VertTo = i + 1
VertFrom = VertFrom +1
)
$.selectedverts = vertSet
subobjectlevel = 1
Well you can use an oct tree type method. I’m not sure it will make what you are doing faster if it only has to happen once how ever. At some point you need to check every vertex. I’m going to guess that the appendIfUnique will be slowing things down a bit as it is having to do a test each time. As the array grows that test will get slower. Instead of that you need to find a way to know that you have not duplicated a vert or place the vert in the index of the array that is the same as the index of the vert. Set the array size to the size of the number of verts first as It will not have to grow the array during the loop either. Try and avoid append for arrays, use collect instead.
Thanks for reply and direction but problem of this search is much more in distance search part how in appendIfUnique command. I run this script without collection of vertex just only for test speed how much time is necessary for search distances between vertex and that is slow because it is from my point of view VertexCount ! because for 10 vertex mesh it is 10+9+8+7+6+5+4+3+2+1 calculation and of course in 5000 vertex is a lot [font=Wingdings]J[/font] I am really sure must be faster way because weld function looking for distance between all vertex either just on end vertex which are in range colapse together and I would like use weld but in my case will be select these vertex. So it must be way [font=Wingdings]J[/font]
If you have access to Subscription, you also have access to a Siggraph Masterclass I held in 2006 that shows how to build and use a voxel grid to speed up searches significantly. (That year there were two classes, the second one was “A Day In The Life of a Technical Director”, that had the example).
Here is the short version of the approach:
*The position of any 3D point can be converted very easily to a voxel address by just dividing it by the voxel size and rounding up.
*A loop through all vertices has to be performed just once to calculate that address and register each vertex into its voxel. You create an array (let’s call it the Voxel Data array) where each voxel is stored as a sub-array containing the vertices residing in it, and a second array where each element is the actual voxel address (the point3 converted to string) and the index of the element corresponds to the index of the voxel in the other array (this is for accessing data by address, let’s call it Index Array).
*Then if you want to know all vertices that are in the vicinity of a certain vertex, you do this:
**Calculate the voxel address of the vertex you are interested in.
**Access the voxel with the same address by finding the index of the address in the Index Array and then reading the data from the Voxel Data array.
Now you have ALL vertices that reside inside the same voxel as your vertex by just doing a findItem() in the Index array and a single read from the Voxel Data. Depending on the voxel size and the search radius, you might want to also check all neighboring voxels by incrementing the X, Y and Z address values and getting all vertex indices found in the voxels left, right, front, back, above, below and at the diagonals of your current voxel.
It sounds complicated, but it is actually quite simple and orders of magnitude faster than comparing each vertex with every other vertex. If your voxel size was 10.0 and your search threshold is less than that, you never have to check any vertices that are in voxels farther away than the threshold.
How always Bobo safe situation [font=Wingdings]J[/font] Yes I think that is solution for which I am looking for I think . I try take a look to these voxel stuff but it sounds to me like really good way how make my search faster and I can use it for my one of my next script which I got in my mind [font=Wingdings]J[/font] For all other before I finish this new voxel stuff here is my script for find vertex in define distance, maybe will be useful for somebody and one another which looking for face area which is good to use if you cutting poly and that sometime dont create vertex on edge but closer to edge [font=Wingdings]J[/font] Once again thanks for help and direction guys.
try destroydialog VertexDistance catch ()
rollout VertexDistance "Vertex Distance" --width:160 height:300
(
groupBox grp1 "Vertex distace" pos:[5,0] width:152 height:45
spinner spn1 "Vertex distanc " range:[0,100000,1] scale:0.001 pos:[15,24]
groupBox grp2 "Vertex distance jump" pos:[5,48] width:152 height:50
radioButtons rdo2 "" labels:#("100","10","1",".1",".01",".001") columns:3 default:3 pos:[15,63]
button bt1 "Find vertex" width:100 height:20 pos:[30,101]
on rdo2 changed state do
(
Sfb = rdo2.state
if Sfb== 1 then spn1.value = 100 else
if Sfb== 2 then spn1.value = 10 else
if Sfb== 3 then spn1.value = 1 else
if Sfb == 4 then spn1.value = 0.1 else
if Sfb == 5 then spn1.value = 0.01 else
if Sfb == 6 then spn1.value = 0.001
)
on bt1 pressed do
(
if selection.count !=1 then messagebox "Select just one object" else
(
sfc = spn1.value
obj = $
convertToMesh obj
a = 1
c = 2
vertlist = #{}
VertSet = #()
vertCount = meshop.getNumVerts $
vertlist = $.verts as bitarray
for i =2 to vertcount do
(
for j=a to vertcount-1 do
(
b = meshop.minVertexDistanceFrom $ a c
--print a
--print c
--print b
if b < sfc then (appendIfUnique vertSet a)
if b < sfc then (appendIfUnique vertSet c)
c = c + 1
)
c = i + 1
a = a +1
)
$.selectedverts = vertSet
if vertSet.count == 0 then messagebox "No vertex under distance" else
(
subobjectlevel = 1
)
)
)
)
createdialog VertexDistance
for this kind of tasks i’m usually use 2D grid (not 3D voxel grid). For meshes with big amount of vertices 3D buffer is very expensive by memory usage. But algorithm that I show below works without any grid and it is pretty fast. Does any one else want to challenge?
the best algorithm is the best balance between execution time and memory leaking…
try destroydialog VertexDistance catch ()
global testSettings = if testSettings == undefined then #(1.0,10.,32) else testSettings
rollout VertexDistance "Vertex Distance"
(
group "Create: "
(
button create "Create Test Mesh" width:120 align:#left across:3
spinner radius "Radius: " range:[0,1e9,testSettings[2]] scale:0.01 fieldwidth:60 align:#right offset:[-12,3]
spinner segments "Segments: " range:[1,1e9,testSettings[3]] scale:1 type:#integer fieldwidth:60 align:#right offset:[0,3]
)
group "Vertices: "
(
spinner threshold "Distance: " range:[0,1e9,testSettings[1]] scale:0.001 fieldwidth:60 align:#left offset:[2,0] across:3
edittext amount "Amount:" fieldwidth:70 readonly:on align:#right offset:[-12,0]
edittext selected "Selected:" fieldwidth:70 readonly:on align:#right offset:[0,0]
)
group "Algorithms: "
(
button bt1 "by Thorn444" width:120 align:#left across:3
edittext tt1 "Execution Time:" fieldwidth:70 readonly:on align:#right offset:[-12,2]
edittext mm1 "Memory Leak:" fieldwidth:70 readonly:on align:#right offset:[0,2]
button bt2 "by denisT" width:120 align:#left across:3
edittext tt2 "Execution Time:" fieldwidth:70 readonly:on align:#right offset:[-12,2]
edittext mm2 "Memory Leak:" fieldwidth:70 readonly:on align:#right offset:[0,2]
)
on bt1 pressed do if iskindof (obj = selection[1]) Editable_Mesh do with undo off
(
sfc = testSettings[1]
a = 1
c = 2
t1 = timestamp()
h1 = heapfree
vertlist = #{}
VertSet = #()
vertCount = meshop.getNumVerts $
vertlist = obj.verts as bitarray
for i =2 to vertcount while not keyboard.escpressed do
(
for j=a to vertcount-1 do
(
b = meshop.minVertexDistanceFrom $ a c
if b < sfc then (appendIfUnique vertSet a)
if b < sfc then (appendIfUnique vertSet c)
c = c + 1
)
c = i + 1
a = a +1
)
tt1.text = (timestamp() - t1) as string
mm1.text = ((h1 - heapfree) as integer) as string
obj.selectedverts = vertSet
selected.text = obj.selectedverts.count as string
subobjectlevel = 1
gc light:on
)
on bt2 pressed do if iskindof (obj = selection[1]) Editable_Mesh do with undo off
(
fn sortByZ v1 v2 = if v1[2].z < v2[2].z then -1 else if v1[2].z > v2[2].z then 1 else 0
dist = testSettings[1]
t1 = timestamp()
h1 = heapfree
verts = obj.verts as bitarray
vlist = for v in verts collect #(v, getvert obj v)
qsort vlist sortByZ
klist = deepcopy vlist
list = #{}
for i=1 to vlist.count while not keyboard.escpressed do
(
v = vlist[i]
out = off
for j=i+1 to klist.count while not out where (k = klist[j]) != undefined do
(
if (distance v[2] k[2]) < dist do
(
append list v[1]
append list k[1]
klist[j] = undefined
)
out = abs (v[2].z - k[2].z) > dist
)
)
tt2.text = (timestamp() - t1) as string
mm2.text = ((h1 - heapfree) as integer) as string
obj.selectedverts = list
selected.text = obj.selectedverts.count as string
setselectionlevel obj #vertex
gc light:on
)
on threshold changed value do testSettings[1] = value
on radius changed value do testSettings[2] = value
on segments changed value do testSettings[3] = value
on create pressed do undo "Create Test" on
(
suspendEditing()
if objects.count > 0 do delete objects
converttomesh (obj = sphere name:"findVerts" radius:testSettings[2] segs:testSettings[3] isSelected:on)
if getCommandPanelTaskMode() != #modify do setCommandPanelTaskMode mode:#modify
setselectionlevel obj #vertex
amount.text = obj.numverts as string
selected.text = obj.selectedverts.count as string
resumeEditing()
)
on VertexDistance open do if iskindof (obj = selection[1]) Editable_Mesh do
(
amount.text = obj.numverts as string
selected.text = obj.selectedverts.count as string
)
)
createdialog VertexDistance width:480 height:200
man that’s really good and so fast How i see is so much to learn be master but I am just starting. Maybe after few years i will write something so fast and efficiany how i can see here. Once again thanks and i appreciate your help and explanation.