I need to select objects next to selected object by same vertices position

[denisT]

I have thousands of objects in the scene and by selecting 1 I want all nearest by vertices would be selected too

upload your scene, and tell what you want to select and what should be selected with it

[Tosyk]

here’s an example of the scene:
https://drive.google.com/open?id=17DEGbh5wHWa5aQmnJ6KQYDCsA4i9d3zs

there’s two overlayed roads and other objects. I want to by selecting object “Mesh_3173” all of these objects to be selected:

"Mesh_2444"
"Mesh_2455"
"Mesh_2463"
"Mesh_2750"
"Mesh_2773"
"Mesh_2778"
"Mesh_2996"
"Mesh_3001"
"Mesh_3008"
"Mesh_3178"
"Mesh_3184"
"Mesh_2349"
"Mesh_2988"
"Mesh_3165"
"Mesh_2343"
"Mesh_2347"
"Mesh_2396"
"Mesh_2977"
"Mesh_3011"
"Mesh_3187"
"Mesh_2335"
"Mesh_2774"
"Mesh_2995"
"Mesh_3172"
"Mesh_2454"
"Mesh_2777"
"Mesh_2989"
"Mesh_3166"
"Mesh_2348"

EDIT: I add mentioned object list to the layer and reupload scene

[denisT]

as soon as i have a time i will take a look

[denisT]

well … i looked into the file and its setup and requirements.

as i expected the straightforward position comparison is very slow because of pretty big meshes and pure algorithm

anyway here is the code:

fn getOpenEdgeVerts mesh = 
(
	ee = meshop.getopenedges mesh
	meshop.getvertsusingedge mesh ee
)
fn isMeshCloseEnough source target threshold:10 open:off = 
(
	near = off
	sv = if open then getOpenEdgeVerts source else source.verts as bitarray
	tv = if open then getOpenEdgeVerts target else target.verts as bitarray
	
	for s in sv while not near do
	(
		p = getvert source s
		for t in tv while not near do 
		(
			near = distance p (getvert target t) <= threshold
		)
	)
	near
)

fn findMeshesCloseEnough sources: targets: threshold:10 open:on = 
(
	if sources == unsupplied do sources = selection as array
	sources = for source in sources where iskindof source Editable_mesh collect source
	if targets == unsupplied do targets = for target in geometry where iskindof target Editable_mesh collect target
	targets = for target in targets where (finditem sources target == 0) collect target
	
	format ">> s:% t:%\n" sources.count targets.count
	
	_sources = deepcopy (sources as array)
	
	for source in _sources do
	(
		format "% >>" (finditem sources source)
		
		for i = targets.count to 1 by -1 while not keyboard.escpressed do
		(
			target = targets[i]
			if (isMeshCloseEnough source target threshold:threshold open:open) do
			(
				append sources target
				deleteitem targets i
			)
		)
		format " s:% t:%\n" sources.count targets.count
	)
	sources
)

fn findAllMeshesCloseEnough sources: targets: threshold:10 open:on = 
(
	if sources == unsupplied do sources = selection as array
	sources = for source in sources where iskindof source Editable_mesh collect source
		
	if targets == unsupplied do targets = for target in geometry where iskindof target Editable_mesh collect target
	targets = for target in targets where (finditem sources target == 0) collect target

	format ">> s:% t:%\n" sources.count targets.count
	
	data = [0,0]
	curr = [sources.count, targets.count]
	for source in sources while not keyboard.escpressed do
	(
		data = copy curr
		
		format "% >>" (finditem sources source)
				
		for i = targets.count to 1 by -1 while not keyboard.escpressed do
		(
			target = targets[i]
			if (isMeshCloseEnough source target threshold:threshold open:open) do
			(
				append sources target
				deleteitem targets i
			)
		)
		format " s:% t:%\n" sources.count targets.count
		curr = [sources.count, targets.count]
	)
	sources
)

you can select the first mesh and run (with a specified threshold):

all = findAllMeshesCloseEnough threshold:10
select all

this function recursively adds close enough meshes to the list and grows the search. it stops when no new target was added.

the function shows the trace (where you can see timing and algorithm working)

i found that most meshes are ‘connected’ by open edges, so there is no reason to search all verts.
the function has an option <open: true/false>, which controls what set of verts to use (open or all). so, see the difference

the possible optimization could be:
#1 check meshes bounding box intersection before verts searching to ensure that the searching is needed at all
#2 of course it’s better to use Kd-tree search algorithm … but it’s a subject of another topic
(with a smart Kd-tree full search takes about 0.1 sec on my machine)

good luck!

[denisT]

… and of course any suggestions of possible optimization are welcome. i will be interested to see them too

[Tosyk]

thanks Denis, just launch it on my machine - still processing this example file.

I just thought if selection of all scene meshes and then searching for the meshes with shared vertices positions and then deviding those groups somehowe (by putting into different layers maybe?) would speed up the process

btw the process is finished: in around 5-7 minutes it does exactly what needs

edit: I’ve read the k-dimensional-tree wiki and this is quite interesting technology, how did you applied to my example file?

[denisT]

this is quite interesting technology, how did you applied to my example file?

Kd-tree algorithms are included in my MXS extension

[Tosyk]

Kd-tree algorithms are included in my MXS extension

it is private I suppose?

[denisT]

it is private I suppose?

it’s still private at the moment … but I think I can open it for free. It all depends on my time and ongoing interest in MXS as a whole… which I doubt very much lately

[Tosyk]

could it be used out of the box or it’s need to be wraped in the code search algoritm for the topic task?

[denisT]

maybe it can… but it’s more what i want to show in this topic

[Tosyk]

Thanks again for the help, Denis!

[miauu]

I have one question regarding the bounding box intersection. For not rotated Box primitive the corners of the boundingbox have the same position as the vertices of the mesh. The built-in intersects command do not offer threshold parameter, so if the two boxes are positioned as the yellow and red object in the image below, the intersects command will return false.

So, what is the real code behind the “intersects” command, and is the maxscript version of this code faster enough to be used with custom bboxes? For example, using the same image, the user will use the real bbox of the yellow object but as bbox of the red object will provide a “bbox” 10 units larger in all directions, so the maxscript code to detect the intersection before to go to vertex by vertex comparison.

[denisT]

sure we have to enlarge bboxes if we take some threshold into account

[miauu]

And can this be done with built-in intersects command?

[denisT]

correct… but for this specific scene it will not help. most of searching objects intersect by their bb

there is more complicated but more accurate solution - check intersection of ‘local’ bboxes in world space

[miauu]

I am asking for general cases. I have done a quick search in the internet but was unable to find the code for 3d bbox intersection. Tomorrow I will continue searching.

there is more complicated but more accurate solution - check intersection of ‘local’ bboxes in world space
For non rotated Box primitives the local and world bboxs have the same corner points, right?

[denisT]

right… but usually objects are rotated why ‘world’ bboxes are not correct to the intersection check

[vusta]

ok, so the way I read it is it’s a recursive Path finding/branching algo, within threshold…not that I can solve anything but at least the premise is now clearly defined.

[miauu]

For situation like in the image:

The cage shows the world BBOx of the box object. All spheres are inside this world Bbox, so intersects will return true for all of them. Only the red sphere is in 10 units thresold. If we have a way to find intersection of local bboxes with threshold parameter then the code will find only the red sphere as intersected object to the box.
We can use distance between the box and the spheres to find the closest object(which also intersects), but in this case the blue sphere is closer to the pivotPoint/center of the box than the red sphere.

I am not sure that I am right but the intersects command uses the world bboxes, right?