Recursion challenge


#21

I am not sure I understand the issue correctly, but could it be related to the “border” nodes being able to move the same distance of the second ring of nodes?

I don’t know if I implemented it correctly., because It is supposed that no outer node should be higher than an inner node?

But this line treat the first (outer) and second ring of nodes the same:

limit = (neighbors.count * pDragDistance) + 1

EDIT:

Just added an optional line to fix the outer ring distance.
So now, from out-in, each ring will move 1 unit distance.

Please let me know if this is correct or if the outer ring should have a fixed position. In that case we may be able to simplify other functions.

--limit = (neighbors.count * pDragDistance) + 1
limit = (neighbors.count * pDragDistance) + 1 - (mod neighbors[1].count 2)

#22

nice!

but, as I said above, there is a problem with the “clamped” affective zone, which causes “holes” in the system:


#23

I also decided to switch to a “weighted” moving algorithm instead of a “cascading” one…
so there will be a lot of changes in the new version.


#24

Yes, I also noticed that, but I assumed it should be that way, because I don’t see a way to fix it (if it needs to be fixed), using the current logic.


#25

Though the same thing. It might be better to weight the nodes, kind of soft selection, but not.

I’ve tried to improve the Update Z Pos Callback, but it is a nightmare of “not working properly” code. I can’t figure out what am I missing, but as usual have that felling that it is much simple than what I think, yet I don’t see it.

So, perhaps Weights is the answer. :+1:


#26

Here is an example of the discontinuity. I was mistaken that it was at the x-axis. In this example, I selected a single object near the center and pulled down to the extent, and that works perfectly. Next, I grabbed the object selected in the image and pulled up. The colored objects behaved correctly, but the conformation should extend recursively so that there isn’t a gap where objects are more than 1 unit from the adjacent ones–as shown between the yellow and grey objects in the image.


#27

In studying the code from @denisT and @PolyTools3D I was able to speed up my original test code. There are many gems in the combined efforts to learn from. Thank you both!

This is the expected functionality:


(red means a grid is at the upper limit, blue is lower limit)


#28

Yes, that’s the same issue Denis and I mentioned. So, how should it be handled?

The problem is that, as you defined, the maximum influence distance, is determined by the distance from the selected node to the outer nodes. Or should any node affect the whole grid, regardless of their distance to the border?

I probably got the idea wrong.


#29

Ah, it appears the node’s influence should go as far as it can, regardless of its distance to the perimeter. That’s a different story. Will check the code. That would prevent the gaps you mentioned.


#30

I apologize for not making that more clear. I was thinking about it recursively, where it’s technically true that each cell has up to only 8 adjacent cells to conform, but if those cells get moved, they each have 8, etc. The way I had it setup with the callback, it was self managing in that regard at least.


#31

it would be good to share the code…


#32

Adding undo skipping helped the speed. Eliminating a finditem also seemed to help. I also changed the when callback parameter to obj from selection. I didn’t profile any of these individually, but the combination makes it work well enough.

Only minor issue now is that the cursor can get far away from where the object is supposed to be limited in height. The object still gets limited to the correct position, it just feels a little janky.

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


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]
	
	--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  -- this is slow
							append adjacent_list adj_name
						--)
					 )
				)
			)
		)
	)
	for c in adjacent_list collect getnodebyname c
)

function conform_adj_objs obj adj = (
	-- 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 = (
	with undo off(
		-- 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]
			
			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
					else obj.wirecolor = [0,255,0]
			)		
			-- now make sure the adjacent objects conform to the slope of delta_z_limit for the new height
			conform_adj_objs obj adj
		)
		redrawviews()
		--forcecompleteredraw()
	)
)

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
			
			when transform new_point changes handleAt: #redrawViews obj  do limit_z obj
		)
	)
)


delete $*
clearlistener()

create_helper_array()

#33

Some advances, not finished yet. The Grid is 41x41.


#34

That looks really responsive and quick. Very nice.


#35

temporary deleted


#36
(
	try destroydialog ::RO_BLUR_SELECTION catch()
	
	rollout RO_BLUR_SELECTION "v0.4 - PolyTools3D" width:166 height:258
	(
		groupbox grp1           "Grid Count:"       pos:[ 8,  8] width:150 height:44
		spinner  sp_count_x     "X:"                pos:[16, 28] fieldwidth:40 range:[3, 50,  9] type:#integer
		spinner  sp_count_y     "Y:"                pos:[88, 28] fieldwidth:40 range:[3, 50, 21] 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.25] 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
		
		button   bt_create_grid "Create Grid"       pos:[ 8,186] width:150 height:32
		button   bt_reset_z_pos "Rese Z Pos"        pos:[ 8,218] width:150 height:32
		
		local pAllNodes     = #()				-- Array of all the grid nodes.
		local pNeighborsLUT = #()				-- LUT of each node neighbors.
		local pLimitsLUT    = #()				-- LUT of each node Z limits.
		
		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 pNodeScale    = 0.5				-- The scale of each point node
		
		local pColorDefault = [130,230, 50]
		local pColorTop     = [230, 50, 50]
		local pColorBottom  = [ 40,130,240]
		
		-- FUNCTIONS
		local CallbackUpdateNeighborsPos
		local CallbackUpdateColors
		local CallbackSelectionChanged
		local CallbackNodeDeleted
		
		function CreateGridHelpers = with undo off
		(
			pAllNodes = #()
			
			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:(pSpacingX*2)
			
			for y = 0 to pGridCountY-1 do
			(
				for x = 0 to pGridCountX-1 do
				(
					x_pos = x*pSpacingX - grid_offset_x
					y_pos = y*pSpacingY - grid_offset_y
					
					obj = instance tmp pos:[x_pos, y_pos, pGridPosZ] wirecolor:pColorDefault
					
					append pAllNodes obj
				)
			)
			
			delete tmp
			
			settransformlockflags pAllNodes #{1,2,4..9}
			
			pAllNodes.scale = [1, 1, 1] * pNodeScale
			for j = 1 to pAllNodes.count do pAllNodes[j].name = j as string
		)
		
		/*
			This will build a LUT of neighbor rings. Note that it will add some neighbors that will never be affected
			by a given node, and so the real-time performance will later be worse. For small grids, it doesn't represent
			a big issue, but for large grids, a better algorithm should be used to find out only the affected neighbors.
			
			This function is roughly 2-3 X faster than the previous version
		*/
		fn BuildNeighborsLUT =
		(
			maxRings  = int (amax pGridCountX pGridCountY)
			maxDepth  = int (maxRings / 2)
			maxDepthX = (amin maxRings pGridCountX) / 2
			maxDepthY = (amin maxRings pGridCountY) / 2
			
			pNeighborsLUT = #()
			
			delta = if pGridCountX < pGridCountY then amin pGridCountX pGridCountY else amax pGridCountX pGridCountY
			
			for idx = 1 to pGridCountX*pGridCountY do
			(
				node_x = int (mod (idx-1)   delta + 1)
				node_y = int (    (idx-1) / delta + 1)
				
				if node_x <= maxDepthX then
				(
					left  = int (node_x - 1)
					right = maxDepthX
				)else(
					left  = maxDepthX
					right = int (abs (pGridCountX-node_x))
				)
				
				if node_y <= maxDepthY then
				(
					top    = int (node_y - 1)
					bottom = maxDepthY
				)else(
					top    = maxDepthY
					bottom = int (abs (pGridCountY-node_y))
				)
				
				sx = int (node_x - left  )
				ex = int (node_x + right )
				sy = int (node_y - top   )
				ey = int (node_y + bottom)
				
				neighbors = for j = 1 to maxDepth collect #()
				
				for y = sy to ey do
				(
					y2   = (y-1)*pGridCountX
					absy = abs (y-node_y)
					
					for x = sx to ex do
					(
						level = amax 1 (abs (x-node_x)) absy
						append neighbors[level] pAllNodes[y2+x]
					)
				)
				
				for j = 1 to neighbors[1].count where neighbors[1][j] == pAllNodes[idx] do deleteitem neighbors[1] j
				
				pNeighborsLUT[idx] = neighbors
				
				limit  = amin node_x node_y (pGridCountX+1-node_x) (pGridCountY+1-node_y)
				top    =  limit * pDragDistance
				bottom = -limit * pDragDistance
				
				pLimitsLUT[idx] = [top, bottom]
			)
		)
		
		fn PaintNodes obj selectedOnly:true = with undo on
		(
			if not obj.isselected or not selectedOnly do
			(
				idx    = obj.name as integer
				top    = pLimitsLUT[idx][1] + pGridPosZ
				bottom = pLimitsLUT[idx][2] + pGridPosZ
				
				if obj.pos.z <= bottom then
				(
					obj.wirecolor = pColorBottom
				)
				else if obj.pos.z >= top then
				(
					obj.wirecolor = pColorTop
				)
				else
				(
					obj.wirecolor = pColorDefault
				)
			)
		)
		
		fn CallbackUpdateColors obj = PaintNodes obj
		
		fn CallbackSelectionChanged = with undo off
		(
			st=timestamp()
			
			deleteallchangehandlers id:#ID_0X7BAD0113
			
			-- We could keep track of the selected nodes and only update those
			for obj in pAllNodes do PaintNodes obj selectedOnly:false
			
			for obj in selection where finditem pAllNodes obj != 0 do
			(
				when transform obj changes id:#ID_0X7BAD0113 obj do CallbackUpdateNeighborsPos obj
			)
			
			-- Let's keep the heap low
			gc light:on
		)
		
		-- This callback process "unnecessarily" the same nodes more than once when having multiple selection
		fn CallbackUpdateNeighborsPos node =
		(
			idx       = node.name as integer
			neighbors = pNeighborsLUT[idx]
			limits    = pLimitsLUT[idx]
			top       = limits[1] + pGridPosZ
			bottom    = limits[2] + pGridPosZ
			
			if node.pos.z >= top then
			(
				node.pos.z = top
			)
			else if node.pos.z <= bottom then
			(
				node.pos.z = bottom
			)
			
			nodez = node.pos.z
			done  = false
			
			for level = 1 to neighbors.count while not done do
			(
				delta = level * pDragDistance
				done  = true
				
				for obj in neighbors[level] where not obj.isselected do
				(
					-- Limit Z Position -------------------
					if (obj.pos.z - nodez) > delta then
					(
						obj.pos.z = nodez + delta
						done = false
					)
					else if (nodez - obj.pos.z) > delta then
					(
						obj.pos.z = nodez - delta
						done = false
					)
				)
			)
		)
		
		-- If we delete one node, then dewlete the whole grid and clear the arrays
		fn CallbackNodeDeleted =
		(
			nodes = callbacks.notificationparam()
			if finditem pAllNodes nodes[1] != 0 do pAllNodes = pNeighborsLUT = pLimitsLUT = #()
		)
		
		fn RemoveCallbacks =
		(
			deleteallchangehandlers id:#ID_0X7BAD0113
			deleteallchangehandlers id:#ID_0X7BAD0114
			
			callbacks.removescripts id:#ID_0X7BAD0113
		)
		
		/* ######################################################################################################################## */
		/* ######################################################################################################################## */
		/* ######################################################################################################################## */
		
		on RO_BLUR_SELECTION oktoclose do
		(
			if pAllNodes.count > 0 do
			(
				answer = yesNoCancelBox "Would you like delete the grid nodes?"
				
				if answer == #cancel do return false
				
				try (pAllNodes.wirecolor = pColorDefault) catch()
				RemoveCallbacks()
				
				if answer == #yes do try (delete pAllNodes) catch()
				
				return true
			)
		)
		
		on RO_BLUR_SELECTION open do RemoveCallbacks()
		
		on bt_create_grid pressed do
		(
			RemoveCallbacks()
			
			if keyboard.controlPressed then delete pAllNodes 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
			
			CreateGridHelpers()
			completeredraw()
			BuildNeighborsLUT()
			
			callbacks.addscript #selectionSetChanged    "::RO_BLUR_SELECTION.CallbackSelectionChanged()" id:#ID_0X7BAD0113
			callbacks.addscript #selectedNodesPreDelete "::RO_BLUR_SELECTION.CallbackNodeDeleted()"      id:#ID_0X7BAD0113
			
			when transform pAllNodes changes handleAt:#redrawViews id:#ID_0X7BAD0114 obj do CallbackUpdateColors obj
			
			setarrowcursor()
			completeredraw()
		)
		
		on sp_node_scale changed arg do with undo off
		(
			pNodeScale = arg
			pAllNodes.scale = [1, 1, 1] * pNodeScale
			redrawviews()
		)
		
		on sp_drag_dist changed arg do pDragDistance = arg
		
		on sp_pos_z changed arg do with undo off
		(
			pGridPosZ = arg
			pAllNodes.pos.z = pGridPosZ
			redrawviews()
		)
		
		on bt_reset_z_pos pressed do with undo off
		(
			pAllNodes.pos.z     = pGridPosZ
			pAllNodes.wirecolor = pColorDefault
			redrawviews()
		)
	)
	
	createdialog RO_BLUR_SELECTION
)

#37

good job!

But as I see it, there is the same problem that I have… UNDO/REDO does not work correctly. The problem “when transform” handling is always tricky and complex to solve it in general.


#38

Yes, it was missing one undo on context. I’ve updated it and seems to work now. But as you say, in general, the callbacks are very tricky, either due to performance or redrawing issues.

Hope this one works correctly.


#39

Here is a video using a relative height color scheme, 41 x 41 grid.

Coloring the selected nodes is much more tricky and there is an small redrawing issue that I can’t solve right away while dragging the selection, but it is solved once you release the mouse button.

This one uses the default color scheme, top/bottom limits.


#40

Here is a neighbor’s LUT comparison between the current algorithm and an optimal one.

EDIT: After some attempts, got the correct algorithm to find the optimal neighbors, but it’s 30% slower.