Recursion challenge


#1

I think the problem I’m trying to solve requires recursion, or a more clever use of callbacks than my brute force attempt. The test code works if you assign values via the transform type in, but it’s really something that needs to work in real-time with the transform gizmo in the viewport to be most effective. My brute force use of callbacks is just too slow to fully work in the viewport–it becomes unreliable.

The goal is a rig that keeps the delta z height between any adjacent object, or the edge, below 1 unit. So the perimeter objects can be +/- 1 in height, and no object can be more than +/- 1 unit from another. So that, if you grab a middle object and move it up past 1, the adjacent 8 objects will move upwards to maintain the 1 unit delta.

Test code is posted below, I’d appreciate any hints or tips as to how to make this more efficient to work in realtime. If you set the line REALTIMEMODE = true, then it will continuously update, not only on redraw, and that’s when it will fall apart.

z_min = 0
z_max = 10
delta_z_limit = 1.0

z_pos = (z_max - z_min) * 0.5
	
x_grid_count = 9
y_grid_count = 21

spacing_x = 5.0
spacing_y = 5.0

REALTIMEMODE = false

function dist_from_edge input_cell axis_count = (
	midpoint = axis_count * .5 +.5
	dist = (midpoint - (abs (input_cell - midpoint) as integer)) as integer
)


function calc_max_delta x y = (
	-- calculate the maximum height this cell can be based on the dist from the edge
	max_x_delta = (dist_from_edge x x_grid_count) * delta_z_limit
	max_y_delta = (dist_from_edge y y_grid_count) * delta_z_limit
	-- use the lowest value
	max_delta = (z_max - z_min) * 0.5
	if max_x_delta < max_delta then max_delta = max_x_delta
	if max_y_delta < max_delta then max_delta = max_y_delta
	
	max_delta
)

function get_xy_from_objname objname = (
	y_grid = (substring objname 7 2) as integer
	x_grid = (substring objname 10 2) as integer

	#(x_grid,y_grid)
)


function get_adjacent_objs obj = (
	-- find all the objects within 1 grid cell
	xy_array = get_xy_from_objname obj.name
	x_grid = xy_array[1]
	y_grid = xy_array[2]
	
	selnames = #()
	for s in selection do appendifunique selnames s.name

	adjacent_list = #()
	
	for adj_y = y_grid - 1 to y_grid + 1 do(
		if adj_y > 0 and adj_y <= y_grid_count do(
			
			for adj_x = x_grid - 1 to x_grid + 1 do(
				if adj_x > 0 and adj_x <= x_grid_count do(
									
					x_string = (formattedPrint adj_x format:"02d")
					y_string = (formattedPrint adj_y format:"02d")
					
					adj_name = "Dummy_" + y_string + "_" + x_string		
					
					if not (adj_x == x_grid and adj_y == y_grid) do( 	-- don't add self
						if (finditem selnames adj_name) == 0 then( -- don't add selected
							append adjacent_list adj_name
						)
					 )
				)
			)
		)
	)
	for c in adjacent_list collect getnodebyname c
)

function conform_adj_objs obj = (
	-- make sure any adjacent object is within delta_z_limit of the z position
	adj = get_adjacent_objs obj
	zpos = obj.pos.z	
	for a in adj do(
		if a.pos.z < (zpos - delta_z_limit) then(
			a.pos.z = zpos - delta_z_limit
		)
		else if a.pos.z > (zpos + delta_z_limit) then(
			a.pos.z = zpos + delta_z_limit
		)
	)	
)


function limit_z objects_in = (
	-- set the max height of any grid cell to be no more than delta_z_limit * rows in from perimeter edge
	-- such that the slope of any adjacent object is no more than delta_z_limit
	for obj in objects_in do(
		
		xy_array = get_xy_from_objname obj.name
		max_delta = calc_max_delta xy_array[1] xy_array[2]
		
		if not REALTIMEMODE then obj.wirecolor = [0,255,0]
		
		half = (z_max - z_min) * 0.5
		
		cell_z_max = half + max_delta
		cell_z_min = half - max_delta
				
		if obj.pos.z > cell_z_max do(
			obj.pos.z = cell_z_max
		)
		if obj.pos.z < cell_z_min do(
			obj.pos.z = cell_z_min
		)

		if not REALTIMEMODE then(
			if obj.pos.z >= cell_z_max then obj.wirecolor = [255,64,64] -- upper limit, set to red
			else if obj.pos.z <= cell_z_min then obj.wirecolor = [64,64,255] -- lower limit, set to blue
		)		
		-- now make sure the adjacent objects conform to the slope of delta_z_limit for the new height
		conform_adj_objs obj
	)
	--redrawviews()
)




function create_helper_array = (
		
	for y = 1 to y_grid_count do(
		for x = 1 to x_grid_count do(
					
			x_string = (formattedPrint x format:"02d")
			y_string = (formattedPrint y format:"02d")
			
			point_name = "Dummy_" + y_string + "_" + x_string
			
			new_point = point name:point_name 
			new_point.box = true
			new_point.axistripod = false
			new_point.cross = false
			new_point.wirecolor = [0,255,0]
			new_point.size = spacing_x * .2

			new_point.pos = [(x - 1) * spacing_x,(y - 1) * -spacing_y, z_pos ]
			
			setTransformLockFlags new_point #{1,2,4,5,6,7,8,9} -- only allow z transform, lock everything else
			
			if REALTIMEMODE then when transform new_point changes selection  do limit_z selection -- REALTIME DOES NOT WORK WELL
			else when transform new_point changes handleAt: #redrawViews selection  do limit_z selection
			
		)
	)
)



delete $*
clearlistener()

create_helper_array()

Slow node renaming
#2

First, In my opinion, the task is set in such a way that it has no solution.

Take three objects - A, B, C, where B is in the middle between A and C, so it is adjacent to both A and C. If we move A more than one unit up and C more than one unit down, how can we do we keep the relative distance of B one unit to both A and C?

The second problem is what “adjacent” means… Are all objects on a fixed projected grid? Otherwise, how can we get neighbors (or adjacent objects)?


#3

Maybe we can only move one object at a time? In this case, the first problem can have a solution.


#4

It’s a good point. There are a few assumptions to operate on, which may avoid the condition you raise:

  1. Assume that a selection (single or multiple) can only move in one direction at a time. Done manually by the user, not programmatic. In that way, if A and C moved up more than 1 unit, B would move up along with them to be within 1 of A and C’s height.

  2. Assume the state of the grid/array is conformed before each move, so we only need to worry about the selected objects being moved, then the adjacent ones, etc. So, as long as each new movement conforms to the rules, we don’t need to go back and fix things.

  3. Another assumption I was operating under, which I think simplifies things, is that for each cell, the maximum delta, up or down, can be calculated at any time, and is deterministic based on the distance from the outer perimeter.

Regardless, it could absolutely be a compromise and limitation to only allow one item to move at a time. It would be convenient to be able to move multiple, but not a hard requirement. Even if we only allow for one object to move via the transform gizmo, it could end up moving everything if translated high enough.

As for the layout, It can be a perfect grid as in the example, or one in which the rows are staggered in more of a hexagon arrangement. Those are the only two options. But, the layout is always known and fixed ahead of time, never dynamic. The staggered layout actually reduces the number of adjacent cells to 6 from 8 for a grid, but I chose the gird to test on for simplicity.

If you get a chance to run the code, try setting REALTIMEMODE = true to get an idea of how the motions of adjacent objects are restricted. It works well enough to get an idea, but it’s not reliable because I believe the callbacks are getting overwhelmed due to in-elegant brute force method.


#5

Here’s an animated gif showing the expected operation. In this case, it’s near a corner so the callbacks don’t get overwhelmed with the number of adjacent items growing out of control, since one row in can only raise or lower to a height of +/- 2, therefore a maximum of 8 adjacent cells to consider.

Height%20Conform%20Animation

And the maximum heights any cell can be:


#6

Since finding the best algorithm for getting neighbors is not the subject of the task, we can stick to a simple test setup:

delete objects 
gc()
	
layout = plane name:#layout widthsegs:10 lengthsegs:10 width:100 length:100 wirecolor:brown
converttopoly layout

nodes = for k=1 to layout.numverts collect (dummy boxsize:[5,5,5] pos:(layout.getvertex  k))
	

fn findNodeNeighbors node = 
(
	k = finditem nodes node
	ff = polyop.getfacesusingvert layout k  
	vv = polyop.getvertsusingface layout ff - #{k} 
	for v in vv collect nodes[v]
)

select (findNodeNeighbors nodes[25])

can we work with this setup?


#7

I think that should be fine, as long as I can adapt any solution back to a name based scheme, or something pre-computed.


#8

this will be a challenge for you :stuck_out_tongue_winking_eye:


#9

Here is the working version. It includes some intricate solutions, but unfortunately I don’t have enough time to explain each of them in detail. If anyone has questions and is interested in getting answers, please feel free to ask.

try(destroydialog rol) catch()
rollout rol "RO:1C9B41E4 by denisT" width:220 --height:150
(
	local updating = off
	
	local cell_color = gray * 1.25
	
	local numcols = 40
	local numrows = 40
	local unit = 10.0
	local range = (amax numcols numrows)/2 * unit
	
	spinner num_cols_sp "Cells X: " type:#integer fieldwidth:44 range:[2,300,numcols] align:#right offset:[0,4]
	spinner num_rows_sp "Cells Y: " type:#integer fieldwidth:44 range:[2,300,numrows] align:#right offset:[0,0]
	
	button create_bt "Create System" width:200 align:#center offset:[0,6] \
		tooltip:"Create System\n RC\t- Reset\n RC+CTRL\t- Reset Unselected Only"

	label shift_dn "LOWER" align:#left offset:[0,4] across:2
	label sfift_up "UPPER" align:#right offset:[0,4]
	
	slider shift_sl width:204 orient:#horizontal range:[-range, range, 0] ticks:0 align:#left offset:[0,-2]

	button grow_bt "Grow" width:99 align:#left offset:[-3,0] across:2
	button shrink_bt "Shrink" width:99 align:#right offset:[3,0]
	
	checkbutton use_calback_cb "Use Transform Callback" highlightcolor:orange width:200 align:#center offset:[0,8]
	button adjust_bt "Manual Adjust" width:200 align:#center offset:[0,4]
	
	label emp_00 height:0

	local layout
	local nodes = #()
	local drivers = #()
	
	local done = #{}, moved = #{}
	
	
	local getvertfacecount
	local getvertface
	local getfacedeg
	local getfacevert

	fn definePolyMethods = 
	(
		getvertfacecount = layout.GetVertexFaceCount
		getvertface = layout.GetVertexFace
		getfacedeg = layout.GetFaceDegree
		getfacevert = layout.GetFaceVertex
	)		

	fn getNodeID node = (finditem nodes node)
	fn getNeighbours id =
	(
		verts = #{}
		for k=1 to getvertfacecount id do
		(
			f = getvertface id k
			for i=1 to getfacedeg f do 
			(
				v = getfacevert f i
				if v != id do append verts v
			)
		)
		verts
	)
	
	fn growNeighbours = 
	(
		xx = #{}
		for k=1 to nodes.count where nodes[k].isselected do append xx k
		ss = copy xx
		for i in xx do ss += getneighbours i
		
		nn = for k in ss collect nodes[k]
		select nn
		ss
	)
	fn shrinkNeighbours = 
	(
		xx = #{}
		for k=1 to nodes.count where nodes[k].isselected do append xx k
		xx.count = nodes.count
			
		ss = -xx 
		for k=1 to nodes.count do if nodes[k].isselected then append xx k else append ss k
		for i in ss do ss += getneighbours i
			
		nn = for i in (xx - ss) collect nodes[i]
		select nn
		ss
	)
	
	on grow_bt pressed do undo "Grow" on growNeighbours()
	on shrink_bt pressed do undo "Shrink" on shrinkNeighbours()
	
	fn sort_z_nds n1 n2 = if n1.pos.z > n2.pos.z then -1 else if n1.pos.z < n2.pos.z then 1 else 0 
	fn sort_z_ids i k = if nodes[i].pos.z > nodes[k].pos.z then -1 else if nodes[i].pos.z < nodes[k].pos.z then 1 else 0 
	
	fn makeSetup columns: rows: = 
	(
		delete objects 
		--gc()

		cx = columns - 1
		cy = rows - 1
		
		layout = plane name:#layout widthsegs:cx lengthsegs:cy width:(cx*unit) length:(cy*unit) wirecolor:brown isfrozen:on -- pos:[0,0,0.1]
		converttopoly layout
		layout.boxmode = on
		definepolymethods()
		
		seed 0
		ref = chamferbox width:unit length:unit height:unit fillet:(unit/10) fillet_segments:1 smooth:off wirecolor:cell_color
		nodes = for k=1 to layout.numverts collect 
		(
			node = instance ref wirecolor:cell_color --wirecolor:(random black white)
			centerpivot node
			node.pos = polyop.getvert layout k
			settransformlockflags node #{1,2,4..9}
			node
		)
		delete ref
		forceCompleteRedraw()
	)
	
	on create_bt pressed do undo "Create" on, redraw off
	(
		max create mode 
		makeSetup columns:num_cols_sp.value rows:num_rows_sp.value
	)
	on create_bt rightclick do undo "Reset" on 
	(
		updating = on
		sel = #()
		non = #()
		for n in nodes do append (if n.isselected then sel else non) n
			
		nn = if keyboard.controlPressed then non else (sel + non)
		nn.pos.z = 0
		
		forceCompleteRedraw()
		updating = off
	)
	
	----------- recursive methods are slower and unstable due to the nature of MXS 
	----------- non recursive method (could be possibly optimized)
	
	fn adjustDrivenCascade done:#{} movers:#() unit:unit = 
	(
		qsort movers sort_z_ids
		
		for id in movers do
		(
			append done id
			ids = getNeighbours id
		
			z = nodes[id].pos.z
	
			for i in ids where not done[i] do
			(
				n = nodes[i]
				p = n.pos.z
				
				dist = abs (z - p)
				if (dist > unit) do
				(
					delta = mod dist unit
					if delta == 0 do delta = unit
					_z = if (p < z) then (z - delta) else (z + delta)
					
					n.pos.z = _z 
					append movers i
				)
			)
		)
	)
	
	fn updateSystemCascade node: = if not updating do
	(
		drivers = selection as array		
		if drivers.count do
		(
			qsort drivers sort_z_nds

			movers = for node in drivers collect (getnodeid node)
			done = movers as bitarray
			adjustDrivenCascade movers:movers done:done unit:unit
		)
	)
	
	local positions = #()
	
	on shift_sl buttondown do
	(
		drivers = selection as array
		qsort drivers sort_z_nds
		
		positions = #()
		positions.count = nodes.count
		for driver in drivers do positions[getnodeid driver] = driver.pos.z
		theHold.Begin()
		forceCompleteRedraw()
	)
	on shift_sl changed val do 
	(
		if drivers.count do --and not use_calback_cb.state do
		(
			for driver in drivers do driver.pos.z = positions[getnodeid driver] + val
			movers = for node in drivers collect (getnodeid node)
			done = movers as bitarray
			adjustDrivenCascade movers:movers done:done unit:unit
			redrawviews()
		)
	)
	on shift_sl buttonup do if theHold.Holding() do 
	(
		shift_sl.value = 0
		theHold.Accept "Shift"
	)

	fn deleteHandlers =
	(
		deleteAllChangeHandlers id:#cascade_sys_sel
		deleteAllChangeHandlers id:#cascade_sys_pos
	)
	fn setupTransformHandler =
	(
		deleteAllChangeHandlers id:#cascade_sys_pos
		drivers = selection as array
		if drivers.count do
		(
			z = when transform selection change id:#cascade_sys_pos node do updateSystemCascade node:node
		)
	)
	fn setupSelectHandler =
	(
		deleteHandlers()

		when select nodes changes id:#cascade_sys_sel do setupTransformHandler()
		
		setupTransformHandler()
	)
	on use_calback_cb changed state do
	(
		deleteHandlers()
		if state then
		(
			setupSelectHandler()
		)
		else
		(
			forceCompleteRedraw()
		)
	)
	on use_calback_cb rightclick do if use_calback_cb.state do
	(
		setupTransformHandler()
	)
	
	on adjust_bt pressed do undo "Adjust" on
	(
		updateSystemCascade()
	)
	
	on rol close do
	(
		deleteHandlers()
	)
	on rol open do
	(
		deleteHandlers()
		
		layout = getnodebyname #layout
		if layout != undefined do definepolymethods()

		nodes = for node in objects where matchpattern node.name pattern:("chamferbox*") collect node

		gc light:on
	)
)
createdialog rol

I have some ideas on how to improve the “callback part” to make it faster, but that’s for the next release. And, of course, I’m open to any suggestions.

PS: I’m sure PolyTools3D, as a great master of optimization, can optimize this well, or suggest a better algorithm. :wink:


#10

I want to inform you right away that this code should not be regarded as an example of how to create tools. It is simply a ‘test bed’ used for testing algorithms. When creating tools, it is important to follow the other guidelines that I have described in my previous posts.


#11

I’m in.:crossed_fingers:

Here is my approach, although I’m not sure if I got the requirements right.

There are many ways to tackle this. We could use structs, CA, scripted controllers, etc., but since I haven’t done something like this before, I will move forward with callbacks.

The main idea is to build a LUT of neighbor’s rings or loops for faster processing later, and then just add the “move” callbacks when needed, instead of having them hooked all the time for every node.

There are four main parts:

    1. Build the nodes grid
    1. Build the neighbors LUT
    1. Process the selections
    1. Process the movements

Notes:

  1. I don’t think it can be optimized much more. Most of the time is consumed by Max while creating the nodes.
  2. This could be optimized. I am currently using a sort of blur algorithm, but it could probably be much faster by avoiding the inner iterations. Have to give it a try.
  3. It’s not that bad, could be better though.
  4. There are many nodes processed more than once when multiple selection involves the same nodes. I think this could be avoided but I’m not sure about the cost of isolating those nodes vs. processing them, while keeping the undo system functional.

Next move, I’ll try to improve the LUT creation, and will check Denis’ code although it’s always hard to get my head around it.:confused:

(
	
	try destroydialog ::RO_BLUR_SELECTION catch()
	
	rollout RO_BLUR_SELECTION "v0.2d - PolyTools3D" width:166 height:276
	(
		GroupBox    grp1               "Grid Count:"       pos:[ 8,  8] width:150 height:44
		spinner     sp_count_x         "X:"                pos:[16, 28] fieldwidth:40 range:[3, 50, 15] type:#integer
		spinner     sp_count_y         "Y:"                pos:[88, 28] fieldwidth:40 range:[3, 50, 15] type:#integer
		
		GroupBox    grp2               "Grid Spacing:"     pos:[ 8, 60] width:150 height:44
		spinner     sp_space_x         "X:"                pos:[16, 80] fieldwidth:40 range:[0, 100, 5] type:#float
		spinner     sp_space_y         "Y:"                pos:[88, 80] fieldwidth:40 range:[0, 100, 5] type:#float
		
		spinner     sp_node_scale      "Node Scale: "      pos:[23,112] fieldwidth:63 range:[ 0.1, 1.0, 0.5] type:#float scale:0.01
		spinner     sp_pos_z           "Grid Position Z: " pos:[ 8,136] fieldwidth:63 range:[-1E4, 1E2, 0.0] type:#float
		spinner     sp_drag_dist       "Drag Distance: "   pos:[ 9,160] fieldwidth:63 range:[   0, 100, 1.0] type:#float
		
		colorPicker cp_nodes_color     "Nodes Color:"      pos:[20,184] fieldwidth:72 height:18 color:[128,128,128]
		checkbox    chk_prev_neighbors "Preview Neighbors" pos:[ 8,214] checked:true
		button      bt_create_grid     "Create Grid"       pos:[ 8,236] width:150 height:32
		
		local pGRID_NODES   = #()				-- Store the grid points nodes
		local pNeighborsLUT = #()				-- LUT of each node's neighbors
		
		local pGridPosZ         = 0.0			-- Grid Z positoin "floor"
		local pGridCountX       = 15			-- Amount of nodes in X
		local pGridCountY       = 15			-- Amount of nodes in Y
		local pSpacingX         = 5.0			-- X Distance between nodes
		local pSpacingY         = 5.0			-- Y Distance between nodes
		local pDragDistance     = 1.0			-- The distance at which the neighbors start moving
		local pNodeSize         = 1				-- The size of each point node
		local pNodeScale        = 0.5			-- The scale of each point node
		local pMaxLoops         = 1				-- Maximum amount of loops "rings" of neighbors a node can have
		local pDefaultColor     = [128,128,128]	-- Default color for the points
		local pPreviewNeighbors = true			-- Preview the neighbors of the selected points
		local pSelectionColors  = #()			-- Array of color for selection previewing
		
		-- FUNCTIONS
		local UpdateNeighborsPos
		local CallbackSelectionChanged
		
		function CreateGridHelpers = with undo off
		(
			pGRID_NODES = #()
			result      = #()
			
			grid_offset_x = ((pGridCountX-1)*pSpacingX) * 0.5
			grid_offset_y = ((pGridCountY-1)*pSpacingY) * 0.5
			
			tmp = point box:on axistripod:off cross:off size:pNodeSize
			
			for y = 0 to pGridCountY-1 do
			(
				row = for x = 0 to pGridCountX-1 collect
				(
					x_pos = x*pSpacingX - grid_offset_x
					y_pos = y*pSpacingY - grid_offset_y
					
					instance tmp pos:[x_pos, y_pos, pGridPosZ] wirecolor:pDefaultColor
				)
				
				append result row
				join pGRID_NODES row
			)
			
			delete tmp
			
			settransformlockflags pGRID_NODES #{1,2,4..9} -- only allow z move
			
			-- Use name as ID. CA and UserProps are much slower !
			for j = 1 to pGRID_NODES.count do pGRID_NODES[j].name = j as string
			
			return result
		)
		
		-- This function needs a cleanup and a huge optimization
		fn BuildNeighborsLUT mHelpers =
		(
			local LUT = for j = 1 to pGridCountX*pGridCountY collect
			(
				depth = for k = 1 to pMaxLoops collect #()
				depth
			)
			
			for y = 1 to mHelpers.count do
			(
				row = mHelpers[y]
				xy  = (y-1)*row.count
				
				for x = 1 to row.count do
				(
					current = mHelpers[y][x]
					
					idx1  = xy + x
					depth = 1
					done  = #{}
					
					for k = 1 to pMaxLoops while depth != 0 do
					(
						count = 0
						
						for yy = y-depth to y+depth do
						(
							xxyy  = (yy-1)*row.count
							
							for xx = x-depth to x+depth do
							(
								if yy > 0 and xx > 0 and not done[xxyy+xx] do
								(
									if xx <= row.count and yy <= mHelpers.count do
									(
										if mHelpers[yy][xx] != current do
										(
											append LUT[idx1][depth] mHelpers[yy][xx]
											count += 1
											done[xxyy+xx] = true
										)
									)
								)
							)
						)
						
						if (mod count 8) != 0 then
						(
							LUT[idx1].count = depth
							
							if depth > 1 do
							(
								if LUT[idx1][depth].count < LUT[idx1][depth-1].count do LUT[idx1].count = depth - 1
							)
							depth = 0
						)else(
							depth += 1
						)
					)
				)
			)
			
			return LUT
		)
		
		fn CallbackSelectionChanged =
		(
			--st=timestamp(); sh=heapfree
			
			validNodes = for obj in selection where finditem pGRID_NODES obj != 0 collect
			(
				if isvalidnode obj then obj else dontcollect
			)
			
			if pPreviewNeighbors==true then
			(
				levels  = for k = 1 to pMaxLoops collect #()
				ordered = for k = 1 to pMaxLoops collect #()
				
				for obj in validNodes do
				(
					loops = pNeighborsLUT[obj.name as integer].count
					join ordered[pMaxLoops - loops + 1] obj
				)
				
				selected = #()
				for obj in ordered do join selected obj
				
				done = #{}
				
				for obj in selected do
				(
					neighbors = pNeighborsLUT[obj.name as integer]
					
					for l = 1 to neighbors.count do
					(
						for n = 1 to neighbors[l].count where not neighbors[l][n].isselected do
						(
							id = neighbors[l][n].name as integer
							
							if not done[id] do
							(
								done[id] = true
								append levels[l] neighbors[l][n]
							)
						)
					)
				)
				
				with undo off
				(
					for j in pGRID_NODES where not j.isselected do j.wirecolor = pDefaultColor
					for j = 1 to levels.count do levels[j].wirecolor = pSelectionColors[j]
				)
			)
			
			deleteallchangehandlers id:#ID_0X7BAD0113
			
			for obj in validNodes do
			(
				when transform obj changes id:#ID_0X7BAD0113 obj do UpdateNeighborsPos obj
			)
			
			--format "time:% heap:%\n" (timestamp()-st) (sh-heapfree)
		)
		
		-- This callback process "unnecessarily" the same nodes when having multiple selection
		-- Needs more work to find out if it would be faster when avoiding multiple processing
		fn UpdateNeighborsPos obj =
		(
			if obj.isselected do
			(
				neighbors = pNeighborsLUT[obj.name as integer]
				
				limit        = (neighbors.count * pDragDistance) + 1
				limit_top    = pGridPosZ + limit
				limit_bottom = pGridPosZ - limit
				
				if obj.pos.z > limit_top    do obj.pos.z = limit_top
				if obj.pos.z < limit_bottom do obj.pos.z = limit_bottom
				
				nodez = obj.pos.z
				
				for j = 1 to neighbors.count do
				(
					D = j * pDragDistance
					loops = neighbors[j]
					
					for k = 1 to loops.count where not loops[k].isselected do
					(
						if (loops[k].pos.z - nodez) > D then
						(
							loops[k].pos.z = nodez + D
						)
						else if (nodez - loops[k].pos.z) > D then
						(
							loops[k].pos.z = nodez - D
						)
					)
				)
			)
		)
		
		fn BuildColorPalette maxHue:128 =
		(
			pSelectionColors = for j = 1 to pMaxLoops collect
			(
				base   = red
				base.h = j*maxHue/pMaxLoops
				base
			)
		)
		
		fn RemoveCallbacks =
		(
			deleteallchangehandlers id:#ID_0X7BAD0113
			callbacks.removescripts id:#ID_0X7BAD0113
		)
		
		/* ######################################################################################################################## */
		/* ######################################################################################################################## */
		/* ######################################################################################################################## */
		
		on RO_BLUR_SELECTION open  do RemoveCallbacks()
		
		on RO_BLUR_SELECTION close do
		(
			try (pGRID_NODES.wirecolor = pDefaultColor) catch()
			RemoveCallbacks()
			
			if pGRID_NODES.count > 0 do
			(
				answer = querybox "Would you like delete the grid nodes?"
				if answer do delete pGRID_NODES
			)
		)
		
		on bt_create_grid pressed do
		(
			RemoveCallbacks()
			
			if keyboard.controlPressed then delete pGRID_NODES else delete objects
			gc()
			
			completeredraw()
			setwaitcursor()
			
			pGridCountX   = sp_count_x.value
			pGridCountY   = sp_count_y.value
			pSpacingX     = sp_space_x.value
			pSpacingY     = sp_space_y.value
			pNodeScale    = sp_node_scale.value
			pGridPosZ     = sp_pos_z.value
			pDragDistance = sp_drag_dist.value

			pDefaultColor = cp_nodes_color.color
			
			pNodeSize     = (amin pSpacingX pSpacingY) * pNodeScale
			pMaxLoops     = int ((amin pGridCountX pGridCountY) / 2)
			
			BuildColorPalette maxHue:160
			
			st=timestamp(); sh=heapfree
			nodes = CreateGridHelpers()
			format "creating nodes:%ms heap:%\n" (timestamp()-st) (sh-heapfree)
			
			st=timestamp(); sh=heapfree
			pNeighborsLUT = BuildNeighborsLUT nodes
			format "building LUT:%ms heap:%\n" (timestamp()-st) (sh-heapfree)
			
			callbacks.addscript #selectionSetChanged "::RO_BLUR_SELECTION.CallbackSelectionChanged()" id:#ID_0X7BAD0113
			
			setarrowcursor()
			completeredraw()
		)
		
		on sp_node_scale changed arg do
		(
			pNodeScale = arg
			pNodeSize  = (amin pSpacingX pSpacingY) * pNodeScale
			pGRID_NODES.size = pNodeSize
			redrawviews()
		)
		
		on chk_prev_neighbors changed arg do
		(
			pPreviewNeighbors = arg
			if not arg then pGRID_NODES.wirecolor = pDefaultColor else CallbackSelectionChanged()
		)
		
		on sp_drag_dist changed arg do pDragDistance = arg
		
	)
	
	createdialog RO_BLUR_SELECTION
)


#12

Good job, PolyTools3D!

Could we use the same settings to simplify visual comparison and debugging?

	rollout RO_BLUR_SELECTION "v0.2d - PolyTools3D" width:166 height:276
	(
		local pGridPosZ         = 0.0			-- Grid Z positoin "floor"
		local pGridCountX       = 40			-- Amount of nodes in X
		local pGridCountY       = 40			-- Amount of nodes in Y
		local pSpacingX         = 10.0			-- X Distance between nodes
		local pSpacingY         = 10.0			-- Y Distance between nodes
		local pDragDistance     = 10.0			-- The distance at which the neighbors start moving
		local pNodeSize         = 10			-- The size of each point node
		local pNodeScale        = 1.0			-- The scale of each point node
		local pMaxLoops         = 1				-- Maximum amount of loops "rings" of neighbors a node can have
		local pDefaultColor     = [128,128,128]	-- Default color for the points
		local pPreviewNeighbors = true			-- Preview the neighbors of the selected points
		local pSelectionColors  = #()			-- Array of color for selection previewing

		GroupBox    grp1               "Grid Count:"       pos:[ 8,  8] width:150 height:44
		spinner     sp_count_x         "X:"                pos:[16, 28] fieldwidth:40 range:[3, 500, pGridCountX] type:#integer
		spinner     sp_count_y         "Y:"                pos:[88, 28] fieldwidth:40 range:[3, 500, pGridCountY] type:#integer
		
		GroupBox    grp2               "Grid Spacing:"     pos:[ 8, 60] width:150 height:44
		spinner     sp_space_x         "X:"                pos:[16, 80] fieldwidth:40 range:[0, 100, pSpacingX] type:#float
		spinner     sp_space_y         "Y:"                pos:[88, 80] fieldwidth:40 range:[0, 100, pSpacingY] type:#float
		
		spinner     sp_node_scale      "Node Scale: "      pos:[23,112] fieldwidth:63 range:[ 0.1, 2.0, pNodeScale] type:#float scale:0.01
		spinner     sp_pos_z           "Grid Position Z: " pos:[ 8,136] fieldwidth:63 range:[-1E4, 1E2, pGridPosZ] type:#float
		spinner     sp_drag_dist       "Drag Distance: "   pos:[ 9,160] fieldwidth:63 range:[   0, 100, pDragDistance] type:#float
		
		colorPicker cp_nodes_color     "Nodes Color:"      pos:[20,184] fieldwidth:72 height:18 color:[128,128,128]
		checkbox    chk_prev_neighbors "Preview Neighbors" pos:[ 8,214] checked:true
		button      bt_create_grid     "Create Grid"       pos:[ 8,236] width:150 height:32
		
		local pGRID_NODES   = #()				-- Store the grid points nodes
		local pNeighborsLUT = #()				-- LUT of each node's neighbors
		
		
		-- FUNCTIONS
		local UpdateNeighborsPos
		local CallbackSelectionChanged
		
		function CreateGridHelpers = with undo off
		(
			pGRID_NODES = #()
			result      = #()
			
			grid_offset_x = ((pGridCountX-1)*pSpacingX) * 0.5
			grid_offset_y = ((pGridCountY-1)*pSpacingY) * 0.5
			
			tmp = chamferbox width:pNodeSize length:pNodeSize height:pNodeSize fillet:(pNodeSize/20) smooth:off fillet_segments:1

#13

Secondly, I assume that every node should affect all recursive neighbors, no matter how far it is from the center of the grid.


#14

Thirdly, I assume that the selected nodes should maintain their relative positions when moved (the entire selection stays solid).


#15

Wow, two alternative solutions. I’m learning a great deal from both examples, thank you both! I’m digesting them now. I want to understand what was making my attempt too slow to function correctly, versus these better performing options.

@denisT:
Assumptions are correct. I do observe in testing your version that the neighbors are limited in z and “snap” to increments, as opposed to smoothly moving with the selection. It is not a requirement that neighbors z position is fixed to a grid.

@PolyTools3D:
I think there’s an issue that can happen at the origin. By dragging various selections up and down, I was able to get a discontinuity on the x axis where the delta z was beyond the limit.

Very minor issues which I should be able to fix. The performance of both is fantastic, and that was the crux of the problem.


#16

there is a clear contradiction here … if the nearest neighbors move smoothly along with the selection, then the whole system must move simultaneously … this is not right


#17

The whole system can move, if the selection is far enough from the edge and depending on the grid size.

Assuming delta z = 1:

  • The outer grid perimeter can be +/- 1
  • Next ring in can be +/- 2
  • and so on

And:

  • Any adjacent cell must be no more than +/- 1 from another

The animated image Polytools posted shows the expected behavior, same as my test code(though mine is unreliable due to being slow).


#18


show me how the red guy’s neighbors should be positioned in all five cases


#19

Here is an update. The process of creating the neighbors LUT is now around 4X faster than previous version. For 40x40 grid I got 2500ms with v0.2d and 630ms with v0.3

Status:
Nodes creation: Good
LUT creation: OK
Selection Callback: OK
Update Z Pos Callback: Bad

(
	
	try destroydialog ::RO_BLUR_SELECTION catch()
	
	rollout RO_BLUR_SELECTION "v0.3 - PolyTools3D" width:166 height:308
	(
		GroupBox    grp1               "Grid Count:"       pos:[ 8,  8] width:150 height:44
		spinner     sp_count_x         "X:"                pos:[16, 28] fieldwidth:40 range:[3, 50, 15] type:#integer
		spinner     sp_count_y         "Y:"                pos:[88, 28] fieldwidth:40 range:[3, 50, 15] type:#integer
		
		GroupBox    grp2               "Grid Spacing:"     pos:[ 8, 60] width:150 height:44
		spinner     sp_space_x         "X:"                pos:[16, 80] fieldwidth:40 range:[0, 100, 5] type:#float
		spinner     sp_space_y         "Y:"                pos:[88, 80] fieldwidth:40 range:[0, 100, 5] type:#float
		
		spinner     sp_node_scale      "Node Scale: "      pos:[23,112] fieldwidth:63 range:[ 0.1, 1.0, 0.5] type:#float scale:0.01
		spinner     sp_pos_z           "Grid Position Z: " pos:[ 8,136] fieldwidth:63 range:[-1E4, 1E2, 0.0] type:#float
		spinner     sp_drag_dist       "Drag Distance: "   pos:[ 9,160] fieldwidth:63 range:[   0, 100, 1.0] type:#float
		
		colorPicker cp_nodes_color     "Nodes Color:"      pos:[20,184] fieldwidth:72 height:18 color:[128,128,128]
		checkbox    chk_prev_neighbors "Preview Neighbors" pos:[ 8,214] checked:true
		button      bt_create_grid     "Create Grid"       pos:[ 8,236] width:150 height:32
		button      bt_reset_z_pos     "Rese Z Pos"        pos:[ 8,268] width:150 height:32
		
		local pGRID_NODES   = #()				-- Store the grid points nodes
		local pNeighborsLUT = #()				-- LUT of each node's neighbors
		
		local pGridPosZ         = 0.0			-- Grid Z positoin "floor"
		local pGridCountX       = 15			-- Amount of nodes in X
		local pGridCountY       = 15			-- Amount of nodes in Y
		local pSpacingX         = 5.0			-- X Distance between nodes
		local pSpacingY         = 5.0			-- Y Distance between nodes
		local pDragDistance     = 1.0			-- The distance at which the neighbors start moving
		local pNodeSize         = 1				-- The size of each point node
		local pNodeScale        = 0.5			-- The scale of each point node
		local pMaxLoops         = 1				-- Maximum amount of loops "rings" of neighbors a node can have
		local pDefaultColor     = [128,128,128]	-- Default color for the points
		local pPreviewNeighbors = true			-- Preview the neighbors of the selected points
		local pSelectionColors  = #()			-- Array of color for selection previewing
		
		-- FUNCTIONS
		local UpdateNeighborsPos
		local CallbackSelectionChanged
		
		function CreateGridHelpers = with undo off
		(
			pGRID_NODES = #()
			result      = #()
			
			grid_offset_x = ((pGridCountX-1)*pSpacingX) * 0.5
			grid_offset_y = ((pGridCountY-1)*pSpacingY) * 0.5
			
			tmp = point box:on axistripod:off cross:off size:pNodeSize
			
			for y = 0 to pGridCountY-1 do
			(
				row = for x = 0 to pGridCountX-1 collect
				(
					x_pos = x*pSpacingX - grid_offset_x
					y_pos = y*pSpacingY - grid_offset_y
					
					instance tmp pos:[x_pos, y_pos, pGridPosZ] wirecolor:pDefaultColor
				)
				
				append result row
				join pGRID_NODES row
			)
			
			delete tmp
			
			settransformlockflags pGRID_NODES #{1,2,4..9}
			
			for j = 1 to pGRID_NODES.count do pGRID_NODES[j].name = j as string
			
			return result
		)
		
		fn BuildNeighborsLUT mHelpers =
		(
			loops = for j = 1 to pMaxLoops collect #()
			
			for y = -pMaxLoops to pMaxLoops do
			(
				for x = -pMaxLoops to pMaxLoops do
				(
					depth = amax (abs x) (abs y)
					if depth != 0 do append loops[depth] [x,y]
				)
			)
			
			local LUT = for j = 1 to pGridCountX*pGridCountY collect
			(
				for k = 1 to pMaxLoops collect #()
			)
			
			columns = mHelpers.count
			rows    = mHelpers[1].count
			
			for y = 1 to columns do
			(
				for x = 1 to rows do
				(
					idx = (y-1)*rows + x
					
					max_depth = amin x y (rows+1-x) (columns+1-y)
					if max_depth > 1 do max_depth -= 1
					
					for depth = 1 to max_depth do
					(
						for n in loops[depth] do
						(
							n += [x, y]
							
							if n[1] > 0 and n[2] > 0 and n[1] <= rows and n[2] <= columns do
							(
								append LUT[idx][depth] mHelpers[n[2]][n[1]]
							)
						)
					)
					
					LUT[idx].count = max_depth
				)
			)
			
			return LUT
		)
		
		fn CallbackSelectionChanged =
		(
			validNodes = for obj in selection where finditem pGRID_NODES obj != 0 collect
			(
				if isvalidnode obj then obj else dontcollect
			)
			
			if pPreviewNeighbors==true then
			(
				levels  = for k = 1 to pMaxLoops collect #()
				ordered = for k = 1 to pMaxLoops collect #()
				
				for obj in validNodes do
				(
					loops = pNeighborsLUT[obj.name as integer].count
					join ordered[pMaxLoops - loops + 1] obj
				)
				
				selected = #()
				for obj in ordered do join selected obj
				
				done = #{}
				
				for obj in selected do
				(
					neighbors = pNeighborsLUT[obj.name as integer]
					
					for l = 1 to neighbors.count do
					(
						for n = 1 to neighbors[l].count where not neighbors[l][n].isselected do
						(
							id = neighbors[l][n].name as integer
							
							if not done[id] do
							(
								done[id] = true
								append levels[l] neighbors[l][n]
							)
						)
					)
				)
				
				with undo off
				(
					for j in pGRID_NODES where not j.isselected do j.wirecolor = pDefaultColor
					for j = 1 to levels.count do levels[j].wirecolor = pSelectionColors[j]
				)
			)
			
			deleteallchangehandlers id:#ID_0X7BAD0113
			
			for obj in validNodes do
			(
				when transform obj changes id:#ID_0X7BAD0113 obj do UpdateNeighborsPos obj
			)
		)
		
		-- This callback process "unnecessarily" the same nodes when having multiple selection
		-- Needs more work to find out if it would be faster when avoiding multiple processing
		fn UpdateNeighborsPos obj =
		(
			if obj.isselected do
			(
				neighbors = pNeighborsLUT[obj.name as integer]
				
				--limit        = (neighbors.count * pDragDistance) + 1
				limit        = (neighbors.count * pDragDistance) + 1 - (mod neighbors[1].count 2)		-- Fix borders limit
				limit_top    = pGridPosZ + limit
				limit_bottom = pGridPosZ - limit
				
				if obj.pos.z > limit_top    do obj.pos.z = limit_top
				if obj.pos.z < limit_bottom do obj.pos.z = limit_bottom
				
				nodez = obj.pos.z
				
				for j = 1 to neighbors.count do
				(
					D = j * pDragDistance
					loops = neighbors[j]
					
					for k = 1 to loops.count where not loops[k].isselected do
					(
						if (loops[k].pos.z - nodez) > D then
						(
							loops[k].pos.z = nodez + D
						)
						else if (nodez - loops[k].pos.z) > D then
						(
							loops[k].pos.z = nodez - D
						)
					)
				)
			)
		)
		
		fn BuildColorPalette maxHue:128 =
		(
			pSelectionColors = for j = 1 to pMaxLoops collect
			(
				base   = red
				base.h = j*maxHue/pMaxLoops
				base
			)
		)
		
		fn RemoveCallbacks =
		(
			deleteallchangehandlers id:#ID_0X7BAD0113
			callbacks.removescripts id:#ID_0X7BAD0113
		)
		
		/* ######################################################################################################################## */
		/* ######################################################################################################################## */
		/* ######################################################################################################################## */
		
		on RO_BLUR_SELECTION open  do RemoveCallbacks()
		
		on RO_BLUR_SELECTION close do
		(
			try (pGRID_NODES.wirecolor = pDefaultColor) catch()
			RemoveCallbacks()
			
			if pGRID_NODES.count > 0 do
			(
				answer = querybox "Would you like delete the grid nodes?"
				if answer do delete pGRID_NODES
			)
		)
		
		on bt_create_grid pressed do
		(
			RemoveCallbacks()
			
			if keyboard.controlPressed then delete pGRID_NODES else delete objects
			gc()
			
			completeredraw()
			setwaitcursor()
			
			pGridCountX   = sp_count_x.value
			pGridCountY   = sp_count_y.value
			pSpacingX     = sp_space_x.value
			pSpacingY     = sp_space_y.value
			pNodeScale    = sp_node_scale.value
			pGridPosZ     = sp_pos_z.value
			pDragDistance = sp_drag_dist.value

			pDefaultColor = cp_nodes_color.color
			
			pNodeSize     = (amin pSpacingX pSpacingY) * pNodeScale
			pMaxLoops     = int (((amin pGridCountX pGridCountY) / 2.0)+0.0)
			
			BuildColorPalette maxHue:160
			
			st=timestamp(); sh=heapfree
			nodes = CreateGridHelpers()
			format "creating nodes:%ms heap:%\n" (timestamp()-st) (sh-heapfree)
			
			st=timestamp(); sh=heapfree
			pNeighborsLUT = BuildNeighborsLUT nodes
			format "building LUT:%ms heap:%\n" (timestamp()-st) (sh-heapfree)
			
			callbacks.addscript #selectionSetChanged "::RO_BLUR_SELECTION.CallbackSelectionChanged()" id:#ID_0X7BAD0113
			
			setarrowcursor()
			completeredraw()
		)
		
		on sp_node_scale changed arg do with undo off
		(
			pNodeScale = arg
			pNodeSize  = (amin pSpacingX pSpacingY) * pNodeScale
			pGRID_NODES.size = pNodeSize
			redrawviews()
		)
		
		on chk_prev_neighbors changed arg do with undo off
		(
			pPreviewNeighbors = arg
			if not arg then pGRID_NODES.wirecolor = pDefaultColor else CallbackSelectionChanged()
			redrawviews()
		)
		
		on sp_drag_dist changed arg do pDragDistance = arg
		
		on bt_reset_z_pos pressed do
		(
			pGRID_NODES.pos.z = 0
			redrawviews()
		)
	)
	
	createdialog RO_BLUR_SELECTION
)

#20

Sure, maybe smaller node size? Because at that size it is a mess of lines on the viewport.