I was reading/poking around here for the last day or two trying to find info on this topic. I found a couple threads on the idea, and tried to wrap my head around it, but couldn’t quite do it.
So I just had the idea of using RayMeshGridIntersect() to do it, and gave it a shot. It actually wasn’t that hard to do, and it works!
I’m not sure if making my own voxel grid and doing the whole process would be faster/much faster or not, but using this method, I have sped up the distance searching process/moving verts by 2x the speed. My standard method of doing distance checks against all verts in a mesh took like 20-30 seconds in 1 example, but using my Voxel method, it only took around 8-9 seconds.
Here is my code for anyone who is interested. Right now it’s moving verts in an Epoly mesh that are selected, to their closest vert in the rest of the scene geo. There might be some other optimizations I could make in this to make it faster too…Enjoy!
(
start = timeStamp()
SetCommandPanelTaskMode #create --Makes the script run faster when the modify panel is closed.
--Copy whatever mesh is 1st in the scene, convert to a Mesh, and then attach the rest of the mesh in the scene so we can do a rayCheck without having to choose a mesh.
local sceneGeo = #()
local theMesh
local theVertArray = #()
--Append all visible (Frozen and not) Scene Geo into an array, so we can collapse to 1 object.
for o in geometry where o.ishidden == false do (append sceneGeo o)
local theSource = finditem sceneGeo selection[1]
deleteitem sceneGeo theSource
if sceneGeo.count > 0 then
(
theMesh = copy (sceneGeo[1])
addModifier theMesh (Edit_Mesh())
collapseStack theMesh
)
------------------------------------------------------
-------STARTING THE STITCH PROCESS-------
------------------------------------------------------
if sceneGeo.count > 0 then
(
for o in sceneGeo do
(
local meshCopy = copy o
attach theMesh meshCopy
)
local newTargetMesh -- NEW TARGET MESH
--REPARING TARGET MESH
local targetMesh = snapshotAsMesh theMesh
newTargetMesh = Editable_mesh() --create an empty EMesh
newTargetMesh.mesh = targetMesh --assign TriMesh value to the EMesh
delete targetMesh --free up memory
rm = RayMeshGridIntersect() --create an instance of the Reference Target
rm.Initialize 250 --init. the voxel grid size to 10x10x10
rm.addNode newTargetMesh --add the Object to the grid
rm.buildGrid() --build the grid data (collecting faces into the grid voxels)
if classof selection[1] != Editable_Poly do convertToPoly Selection[1] --Convert to EPoly if necessary
local theGSMesh = snapshotasmesh selection[1] --grab the TriMesh of the Object, so we get proper positions
for theVert in (theGSMesh.selectedverts as bitarray) while not keyboard.escpressed do
(
local thePos = polyop.getvert selection[1] theVert node:Selection[1] --get the position of the vertex
local theHitsCount = rm.intersectSphere thePos 100000 --Preform a sphere intersection of all the geo in the scene
if theHitsCount != undefined then --if have hit anything...
(
local closestHit = rm.getClosestHit() --Get the Face Index of the closest hit in the scene
local theVerts = meshop.getVertsUsingFace newTargetMesh closestHit -- Get the verts associated with the face
local closestVert = meshop.getvert newTargetMesh ((theVerts as array)[1]) --Use the 1st vert in the bitarray as the closest vert
local theDist = distance (polyop.getvert selection[1] theVert node:Selection[1]) (meshop.getvert newTargetMesh (theVerts as array)[1]) --Get the distance from the selected vert in the selected object, and check the distance to the vert found in the scene.
for targetVert in theVerts do -- Loop through the verts from the hit face
(
if distance (polyop.getvert selection[1] theVert node:Selection[1] ) (meshop.getvert newTargetMesh targetVert) < theDist do closestVert = (meshop.getvert newTargetMesh targetVert) --If a vert in the bitarray has a closer distance to the selected objects vert, use that one.
)
polyop.setvert selection[1] theVert closestVert --Move the selected objects vert to the closest vert pos in the scene.
)
)
delete newTargetMesh -- Deleting our temp meshes
delete theMesh
rm.free() -- Free the Voxel Data from Ram
end = timeStamp()
format "Processing took % seconds
" ((end - start) / 1000.0)
)
)
the code is pretty clean. the maximum optimization that i can do might make it just ~two times faster.
correction. three times faster.
Optimization using the same RayMeshGridIntersect(), or a custom Voxel setup/2D Grid?
I saw your 2D one, but I was confused by it.
You gonna leave me hangin… I’ll take a look over it again in the meantime and see what I can do… :wip:
Well I’ve been looking at this examaple from the Day in the life of a TD, and I modified it somewhat to try to get it to work for me, but it keeps saying that
Runtime error: array index must be positive number, got: 0.0
So… do I need to convert the address to a string to get rid of this or something? I thought Bobo mentioned that at some point, because of 0 and negative values.
(
local theVoxelGrid = #()
local theVoxelGridSize= 10
local theVoxelOrigin = $Teapot01.center
local theMesh = $Teapot01
fn getVoxelAddress origin pos =
(
local theAddress = (pos-origin)/theVoxelGridSize
[1+(ceil theAddress.x) as integer, 1+(ceil theAddress.y) as integer, 1+(ceil theAddress.z) as integer ]
)
fn getVoxelCoords origin address =
(
origin + (address*theVoxelGridSize)
)
fn VoxelGrid_BuildVoxelGrid =
(
local st = timestamp()
local vcount = theMesh.numverts
local grid_x = ceil ((theMesh.max.x - theMesh.min.x)/theVoxelGridSize) as integer + 1
local grid_y = ceil ((theMesh.max.y - theMesh.min.y)/theVoxelGridSize) as integer + 1
local grid_z = ceil ((theMesh.max.z - theMesh.min.z)/theVoxelGridSize) as integer + 1
for z = 1 to grid_z do
(
theVoxelGrid[z] = #()
for y = 1 to grid_y do
(
theVoxelGrid[z][y] = #()
for x = 1 to grid_x do
theVoxelGrid[z][y][x] = #()
)
)
for v = 1 to vcount do
(
theAddress = getVoxelAddress theVoxelOrigin ((getVert theMesh v))
append theVoxelGrid[theAddress.z][theAddress.y][theAddress.x] v
)
format "VoxelGrid Built in % ms
" (timestamp()-st)
)
fn VoxelGrid_FindClosestVertex pos =
(
local minDist = 10^10
local minVert = 1
local thePos = [0,0,0]
local theAddress = getVoxelAddress pos
for z = theAddress.z-1 to theAddress.z+1 do
(
for y = theAddress.y-1 to theAddress.y+1 do
(
for x = theAddress.x-1 to theAddress.x+1 do
(
try
(
for v in theVoxelGrid[z][y][x] do
(
thePos = getVert theMesh v
if (theDist = distance thePos pos) < minDist then
(
minDist = theDist
minVert = v
)
)--end v loop
)catch()
)--end x loop
)--end y loop
)--end z loop
print (minVert)
)
VoxelGrid_BuildVoxelGrid()
VoxelGrid_FindClosestVertex ($.pos)
)
The getVoxelAdress method sometimes return a 0 coordinate.
This will make it work.
[amax 1 (1+(ceil theAddress.x) as integer), amax 1 (1+(ceil theAddress.y) as integer), amax 1 (1+(ceil theAddress.z) as integer) ]
Don’t know if it gives the correct point3 value though, I have not properly looked at the code.
Also, the call for the same function in the voxelGrid_BuildVoxelGrid method is missing an argument.
That worked, at least it didn’t give an error and it runs now.
But I’ve gotta be doing this part wrong\
local theAddress = getVoxelAddress pos $Teapot01.pos
for z = theAddress.z-1 to theAddress.z+1 do
(
for y = theAddress.y-1 to theAddress.y+1 do
(
for x = theAddress.x-1 to theAddress.x+1 do
(
try
(
for v in theVoxelGrid[z][y][x] do
(
thePos = getVert theMesh v
if (theDist = distance thePos pos) < minDist then
(
minDist = theDist
minVert = v
)
)--end v loop
)catch()
)--end x loop
)--end y loop
)--end z loop
print (minVert)
I must be doing the getVert wrong… now that I look at it, that wouldn’t work. Right? I tried just doing Print thePos, but it doesn’t do anything, Unless I select the Teapot itself, wihch is the object I’m trying to collect/sort through.
Sorry for the confusion… I accidentally overwrote the original script Bobo had, and I don’t have a backup for some stupid reason… :banghead:
Thanks!
have you seen this post
http://forums.cgsociety.org/showpost.php?p=6108222&postcount=6
Yes, I was trying to use your method before doing a 3D Voxel Grid. But the Voxel setup almost makes more sense to me, lol.
So you are only using their Z Distances.... but would this method work as quickly sorting by X,Y,Z? I will look at your code again, for probably the third time, and see if I can't figure it out yet...
Edit:
Ok, so I changed some things a little, and my script works as fast/faster than what you had, except it’s grabbing the wrong vert. It’s not grabbing the closest one to the point on Plane01
with undo off
(
obj = selection[1]
fn sortByZ v1 v2 = if v1[2].x < v2[2].x then -1 else if v1[2].x > v2[2].x then 1 else 0
fn compareFN v1 v2 =
(
local d = (length v1[2])-(length v2[2])
case of
(
(d < 0.): -1
(d > 0.): 1
default: 0
)
)
t1 = timestamp()
h1 = heapfree
verts = obj.verts as bitarray
vlist = for v in verts collect #(v, getvert obj v) --v
qsort vlist compareFN
klist = deepcopy vlist
local dist = distance (getvert $plane01 21) vlist[1][2]
local theVert = (getvert $plane01 21)
local 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 theVert k[2]) < dist do --v[2]
(
--append list v[1]
list = #{k[1]}
klist[j] = undefined
)
out = abs (theVert.x - k[2].x) > dist --v[2]
)
)
obj.selectedverts = list
setselectionlevel obj #vertex
t2 = timestamp()
format "Processing took % seconds
" ((t2 - t1) / 1000.0)
gc light:on
)
Thankswhere is the difference between my and yours methods? yours is not working…
you are sorting by Length but going out from loop by X distance. it’s why your methods is faster.
if you want to sort by Length you have to know that the method will not work for sphere.
and sorting by Z doesn’t work for plane.
so the fastest method is to use 3D voxel grid. It’s about 1.2 times faster than 2D grid ( 6.3 faster than Z-Sort) but it needs about 1.8 times more memory than 2D.
actually 3D grid method not always faster than 2D. it depends on geometry. But 3D grid method always needs more memory.