Is there any efficient way to find all voxels indexes that are intersect or touch the red zone?
I need to do a lot of point-to-segment distance checks, so I put all points into uniform accel grid, but can’t find any info on how to effectively get grid indexes. Especially for 3d grid case.
does a uniform grid help much here ? if the segment is fixed you can reduce it to 2 dot products max… something like (in mxs)
fn Point2SegmentDistsq a b c &t =
(
ab = b - a; -- this can be cached
ac = c - a;
ee = dot ac ab;
if ee < 0.0 then
(
t = 0.0;
return dot ac ac;
)
ff = dot ab ab -- this value can be cached for the segment
if ee >= ff then
(
bc = c - b;
t = 1.0;
return dot bc bc
)
t = ee/ff;
dot ac ac - ee * t;
)
which doesn’t seem overly “expensive” no more than having to compute the grid a compute the distances within it.
Thanks, Klvnk.
I’m writing my first c++ mod that changes mesh topology and inserts verts in nearby open edges.
It works pretty good right now, but I still want to push it further for it to be able to process any amount of verts and edges instantaneously .
I can’t see any other way rather than using grid to optimize 100k edges to 100k+ verts distance checks.
Building grid will definitely take some tiny fraction of overall initialization time, but also will heavily reduce the amount of unneeded checks.
And that’s why I’m looking for some algo to help getting these grid voxel indexes.
ps. I did some tests with J. Amanatides Fast Voxel Traversal in mxs, but it returns only the segment-intersected voxels and not the surrounding. Guess it could be modified to my needs, but maybe there’s already some other way to get the same thing without reinventing the wheel?
I guess go with the voxel traversal to collect all the seg voxel intersections then iterate through those doing a spherical test from each one (there will be overlapping but some “previous” tagging can eliminate that) to generate the voxel “volume” required.
If you just want to eliminate some voxels and not get the exact ones that touch the red zone, you can go by checking distance from the center of each voxel to your segment plus the cube half diagonal.
You will get a few more voxels, but you won’t loose anyone and this selection should be quick.
A second level voxel subdivision may help in some cases for a second level checking.
There can potentially be a lot (size^3) of voxels to check against so it might be slow, since we need to do it for each segment again and again.
Something like this might work for excluding the rest of the voxels, but it is good for short/orthogonal segments only ( compared to grid size ). Long diagonal segment ruins all the optimization we can get this way.
_min = GridIndexFromPoint (seg_pt1 - [ searchRadius, searchRadius, searchRadius ])
_max = GridIndexFromPoint (seg_pt2 + [ searchRadius, searchRadius, searchRadius ])
for z = _min.z to _max.z do
for y=_min.y to _max.y do
for x=_min.x to _max.x do
...Anyway. Here’s some quick mxs code to play with if anyone is interested.
Capsule node linked to two dummies to help visualize what voxels are actually intersected at certain distance.
upd added voxel growth
try (destroydialog ShowIntersectionsRollout ) catch ()
rollout ShowIntersectionsRollout "" (
CheckButton showIntesections "show voxel intersections" width:150
fn ShowIntersectionPoints =
(
if ::GridIntersectionPoints != undefined do
(
gw.setTransform (matrix3 1)
for pt in GridIntersectionPoints do
(
gw.Marker pt #smallHollowBox color:yellow
)
)
)
on ShowIntersectionsRollout open do unregisterRedrawViewsCallback ShowIntersectionPoints
on showIntesections changed state do
(
if state then
(
unregisterRedrawViewsCallback ShowIntersectionPoints
registerRedrawViewsCallback ShowIntersectionPoints
) else unregisterRedrawViewsCallback ShowIntersectionPoints
redrawViews()
)
on ShowIntersectionsRollout close do unregisterRedrawViewsCallback ShowIntersectionPoints
)
fn VoxelTraversal pt_start pt_end size:1.0 intersections: maxcount:50 =
(
dirr = pt_end - pt_start
dir = normalize dirr
local visited_voxels = #()
current_voxel = [ floor ( pt_start.x / size ), floor ( pt_start.y / size ), floor ( pt_start.z / size ) ]
last_voxel = [ floor ( pt_end.x / size ), floor ( pt_end.y / size ), floor ( pt_end.z / size ) ]
format "FROM % TO %\n" current_voxel last_voxel
vec = pt_end - pt_start
stepX = if vec.x >= 0 then 1 else -1
stepY = if vec.y >= 0 then 1 else -1
stepZ = if vec.z >= 0 then 1 else -1
next_voxel_boundary_x = (current_voxel.x + stepX) * size;
next_voxel_boundary_y = (current_voxel.y + stepY) * size;
next_voxel_boundary_z = (current_voxel.z + stepZ) * size;
if stepX < 0 do next_voxel_boundary_x += size
if stepY < 0 do next_voxel_boundary_y += size
if stepZ < 0 do next_voxel_boundary_z += size
tMaxX = if vec.x != 0 then (next_voxel_boundary_x - pt_start.x) / vec.x else 1e10
tMaxY = if vec.y != 0 then (next_voxel_boundary_y - pt_start.y) / vec.y else 1e10
tMaxZ = if vec.z != 0 then (next_voxel_boundary_z - pt_start.z) / vec.z else 1e10
tDeltaX = if vec.x != 0 then size / vec.x * stepX else 1e10
tDeltaY = if vec.y != 0 then size / vec.y * stepY else 1e10
tDeltaZ = if vec.z != 0 then size / vec.z * stepZ else 1e10
diff = [0, 0, 0]
append visited_voxels (copy current_voxel)
count = 0
while (last_voxel != current_voxel) and count < maxcount do
(
count += 1
if (tMaxX < tMaxY) then
(
if (tMaxX < tMaxZ) then
(
intersection_point = pt_start + tMaxX * dirr
if intersections != unsupplied do append intersections intersection_point
current_voxel.x += stepX;
tMaxX += tDeltaX;
)
else
(
intersection_point = pt_start + tMaxZ * dirr
if intersections != unsupplied do append intersections intersection_point
current_voxel.z += stepZ;
tMaxZ += tDeltaZ;
)
)
else
(
if (tMaxY < tMaxZ) then
(
intersection_point = pt_start + tMaxY * dirr
if intersections != unsupplied do append intersections intersection_point
current_voxel.y += stepY;
tMaxY += tDeltaY;
)
else
(
intersection_point = pt_start + tMaxZ * dirr
if intersections != unsupplied do append intersections intersection_point
current_voxel.z += stepZ;
tMaxZ += tDeltaZ;
)
)
append visited_voxels (copy current_voxel)
)
visited_voxels
)
deleteAllChangeHandlers id:#gridUpdate
resetMaxFile #noprompt
max tool maximize
delete objects
delete helpers
gc()
viewport.SetGridVisibility viewport.activeViewport false
mtl = Standardmaterial opacity:1.0
mtl2 = Standardmaterial opacity:0.5
R = 6.0 -- voxel search radius
p1 = dummy pos:[2.42709,37.7306,51.936]
p2 = dummy pos:[55,65,45]
c = Capsule radius:R sides:8 name:#tmppt parent:p1 wirecolor:green
c.pivot += [0,0,c.radius]
c.pos = p1.pos
c.rotation.controller = LookAt_Constraint()
c.rotation.controller.target_axis = 2
c.rotation.controller.appendTarget p2 100.0
c.rotation.controller.upnode_axis = 1
c.material = mtl
dist_ctl = float_script()
dist_ctl.addNode "p1" p1
dist_ctl.addNode "p2" p2
dist_ctl.script = "distance p1.pos p2.pos"
c.height.controller = dist_ctl
c.rotation.controller.lookat_vector_length.controller = dist_ctl
CELL_SIZE = 10.0
MIN = [0,0,0]
DIMENSIONS = [10,10,10]
BOUNDS = (DIMENSIONS*CELL_SIZE)
EXPAND = 1
box width:BOUNDS.x length:BOUNDS.y height:BOUNDS.z pos:(MIN + [BOUNDS.x * 0.5, BOUNDS.y * 0.5,0]) wirecolor:green isfrozen:true showFrozenInGray:off boxmode:true
VOXELS = #()
VOXELS_COUNT = int (DIMENSIONS.x * DIMENSIONS.y * DIMENSIONS.z)
for z=1 to DIMENSIONS.z do
(
for y=1 to DIMENSIONS.y do
(
for x=1 to DIMENSIONS.x do
(
b = box width:CELL_SIZE length:CELL_SIZE height:CELL_SIZE pos:(MIN + [CELL_SIZE,CELL_SIZE,CELL_SIZE] * [x-1,y-1,z-1] + [CELL_SIZE * 0.5, CELL_SIZE * 0.5,0]) wirecolor:yellow material:mtl2 isfrozen:true showFrozenInGray:off ishidden:true
append VOXELS b
)
)
)
fn GetVoxelIndex index size =
(
1 + index.x + index.y * size.x + index.z * size.x * size.y
)
fn UpdateGRID =
(
times = [0,0,0,0]
t2 = timestamp()
try ( hide ::VOXELS ) catch()
times[1] += timeStamp() - t2
t2 = timestamp()
::GridIntersectionPoints = #()
intersected_voxels = VoxelTraversal p1.pos p2.pos size:CELL_SIZE intersections:GridIntersectionPoints
times[1] += timeStamp() - t2
processed_cells = #{}
for rawindex in intersected_voxels do
(
t2 = timestamp()
indexes = #()
for z=-EXPAND to EXPAND do
( for y=-EXPAND to EXPAND do
( for x=-EXPAND to EXPAND do
(
index = ([x,y,z] + rawindex)
if not (index.x < 0 or index.x >= DIMENSIONS.x or index.y < 0 or index.y >= DIMENSIONS.y or index.z < 0 or index.z >= DIMENSIONS.z) do
(
cell_index = GetVoxelIndex ([x,y,z] + rawindex) DIMENSIONS
append indexes cell_index
)
)
)
)
times[3] += timeStamp() - t2
t2 = timestamp()
unhide (
for index in indexes where not processed_cells[ index ] and index <= VOXELS_COUNT collect
(
processed_cells[ index ] = true
VOXELS[index]
)
)
times[4] += timeStamp() - t2
)
format "1. %\n2. %\n3. %\n4. %\n" (times[1]/1000 as float) (times[2]/1000 as float) (times[3]/1000 as float) (times[4]/1000 as float)
)
when transform c changes id:#gridUpdate do UpdateGRID()
UpdateGRID()
createDialog ShowIntersectionsRolloutthinking about it, if you can, use the PolyObject as your pipe object for the modifier then use the
MNMesh::PropegateComponentFlags to grow your “initial” selection out to the required distance. (though I hate the SDK MNMesh with a passion buggy load of garbage) It’s relatively fast approach.
Will it work if vert has no relation to the edge I’m checking it against? I mean It can be a vert of another element for example.
I need to get all open-edge-verts that are close to that particular edge. And then repeat this process for thousands of edges.
I would:
- put capsule object into scene,
- find its bounding volume
- make rays from bounding volume faces for every grid node
- find every intersection of rays with capsule
- check every voxel if any intersection point belongs to its edge
- fill the volume inside intersected voxels
As I said above this capsule node is used for visualization of voxel traversal purposes only.
It makes no sense to use in calculations. You can run the example I posted above and check yourself.
There’s no need to rayintersect anything really.