How to efficiently find verts by 3D position...

Scripting in Blender with Python, and working on the API

Moderators: jesterKing, stiv

Post Reply
dvochin
Posts: 0
Joined: Mon Aug 20, 2012 9:39 pm

How to efficiently find verts by 3D position...

Post by dvochin » Mon Jul 29, 2013 12:40 am

Hi, is there a way from blender python to quickly find the vert at a given position (without forcing python to iterate through all verts)?

Alternatively, C-based code that would return the closest vert would be good too.

So far the closest call is closest_point_on_mesh() but that gives me the closest FACE and forces me to iterate throught that face's verts to find the one I need. Since that call is much more expensive than the closest vert I'd though I asked if the simpler vert version is available...

(The call could be in the bmesh (preferred!) or editmesh libraries.)

Thanks! :)

CoDEmanX
Posts: 0
Joined: Sun Apr 05, 2009 7:42 pm
Location: Germany

Post by CoDEmanX » Tue Jul 30, 2013 4:55 pm

you need an algorithm for this. BSP is probably not working well here, better look into BVH or similar approaches, maybe Octrees. What this basically does is pre-processing the data (vertex coords), in order to have it structured in a way that let's you find vertices by coord efficiently. There is a script that matches vertices by UV map, and there's also a GSoC project which aims to implement just that in C, so you might wanna look into that.
I'm sitting, waiting, wishing, building Blender in superstition...

dvochin
Posts: 0
Joined: Mon Aug 20, 2012 9:39 pm

Post by dvochin » Tue Jul 30, 2013 6:45 pm

Hi CoDEmanX, thanks for that response. BVH would indeed be awesome for this and offer best overall performance... I'm just surprised given the sophistication of the Blender API that vert-search by position is not already a uber-optimized service used by tons of higher-up Blender functionality (like that closest_point_on_mesh())

Could you comment on the algorithm efficiency of closest_point_on_mesh()? It does give me much more info than I need but if its efficient I'll use it for now while the GSoC student works on the simpler function... :)

CoDEmanX
Posts: 0
Joined: Sun Apr 05, 2009 7:42 pm
Location: Germany

Post by CoDEmanX » Tue Jul 30, 2013 7:28 pm

not sure what you would use search by coordinate for actually...

and the point on mesh function does use bvh:

Code: Select all

static void rna_Object_closest_point_on_mesh(Object *ob, ReportList *reports, float point_co[3], float max_dist,
                                             float n_location[3], float n_normal[3], int *index)
{
	BVHTreeFromMesh treeData = {NULL};
	
	if (ob->derivedFinal == NULL) {
		BKE_reportf(reports, RPT_ERROR, "Object '%s' has no mesh data to be used for finding nearest point",
		            ob->id.name + 2);
		return;
	}

	/* no need to managing allocation or freeing of the BVH data. this is generated and freed as needed */
	bvhtree_from_mesh_faces(&treeData, ob->derivedFinal, 0.0f, 4, 6);

	if (treeData.tree == NULL) {
		BKE_reportf(reports, RPT_ERROR, "Object '%s' could not create internal data for finding nearest point",
		            ob->id.name + 2);
		return;
	}
	else {
		BVHTreeNearest nearest;

		nearest.index = -1;
		nearest.dist = max_dist * max_dist;

		if (BLI_bvhtree_find_nearest(treeData.tree, point_co, &nearest, treeData.nearest_callback, &treeData) != -1) {
			copy_v3_v3(n_location, nearest.co);
			copy_v3_v3(n_normal, nearest.no);
			*index = nearest.index;
			return;
		}
	}

	zero_v3(n_location);
	zero_v3(n_normal);
	*index = -1;
}
I'm sitting, waiting, wishing, building Blender in superstition...

dvochin
Posts: 0
Joined: Mon Aug 20, 2012 9:39 pm

Post by dvochin » Wed Jul 31, 2013 6:22 pm

Ah very cool! closest_point_on_mesh() is then probably fast enough for me although if that student could just strip the extra work of finding the related face and the closest point on that face it would be even more useful.

I need to search verts by coordinates because the boolean modifier I use heavily destroys basically any meta info I can store in a mesh to find my verts again... vertex groups are destroyed, any tagging I can stuff into verts, edges, polys are gone, IDs or references with bmesh or editmesh are changed, with the only thing that really survives are the material index of the polys and the UVs which I don't want to change.

In other words I haven't found any other way to find a vert again past a boolean modifier than remembering their position and then iterating to find them after boolean.

(If you happen to know a way that would be fantastic... have a day trying to overcome this and so far only coordinates work!)

Post Reply