🔒 Locked

How to find nearest vertex of a mesh to some other point?

Started by ryt Sep 13, 2009 at 5:58 AM 13 replies 8.2k views

Original Post

Sep 13, 2009 at 5:58 AM

How can I find a nearest vertex of a mesh to some other vertex in a space? One approach came into my mind, to loop trough all vertices of a mesh, calculate the every distance to some vertex in space and pick the smallest one. But this approach seems very slow so I wonder if it can be done some other way.

AndyFirth

Sep 13, 2009 at 10:32 AM

whats the actual problem you're trying to solve?

collision detection?

szecs

Sep 13, 2009 at 10:37 AM

I think you have to loop through anyways.
distance = sqrt(dot_product(other_pt-mesh_pt,other_pt-mesh_pt)), I hope that's clear

index = 0;min_distance = sqrt(dot_product(other_pt-mesh_pt[0],other_pt-mesh_pt[0]));for(i=1; i < max_mesh_pts; i++){   distance = sqrt(dot_product(other_pt-mesh_pt,other_pt-mesh_pt))    if(distance<min_distance)    {   min_distance=distance        index=i;    }}

i is the index you are looking for, and min_distance is the distance of the closest point
If you don't use sqrt in the loop, (because if a<b then a^2<b^2 too), it will be much faster.

ryt

Sep 13, 2009 at 10:52 AM

AndyFirth:
for eg. I want to deform a mesh when it approaches a wall or some other point. But I need to deform nearest side of mesh to a wall not just some arbitrary.

szecs:
-> distance = sqrt(dot_product(other_pt-mesh_pt,other_pt-mesh_pt)), I hope that's clear

I dont understand why do you put this in dot_product()? I understand why are you subtracting, so you could get a vector from mesh_pt to other_pt and with other code I see what are you trying to accomplish.

szecs

Sep 13, 2009 at 11:03 AM

See it in your What dot product means? thread.

But if you want to check it against a wall (plane) that's another story.

Waterwalker

Sep 13, 2009 at 11:15 AM

Note that having a hierarchical bounding volume structure representing your mesh can significantly improve performance if you are dealing with big meshes.

dmatter

Sep 13, 2009 at 11:33 AM

Quote:
Original post by ryt
szecs:
-> distance = sqrt(dot_product(other_pt-mesh_pt,other_pt-mesh_pt)), I hope that's clear

I dont understand why do you put this in dot_product()?

As I explained in your other thread, if you take the dot product of a vector with itself the result is equal to the square of its magnitude. szecs then takes the square root of this to find the actual magnitude/distance quantity but, as he mentions in his post, this isn't strictly necessary since you're only interested in comparing magnitudes you might as well just compare the squared magnitudes and save yourself the sqrt each time.

It sounds to me though that you don't want to be finding the distance between vertex points and another point, rather you want to be finding the distance between vertex points and a plane.

ryt

Sep 13, 2009 at 11:58 AM

Now I understand, instead of (other_pt-mesh_pt)*(other_pt-mesh_pt) plus (other_pt-mesh_pt)*(other_pt-mesh_pt) he used dot_product().

Quote:
Original post by dmatter
It sounds to me though that you don't want to be finding the distance between vertex points and another point, rather you want to be finding the distance between vertex points and a plane.

Yea I want to find the distance to another point, that was just a bad eg.

szecs

Sep 13, 2009 at 12:04 PM

Do you know the equation of a plane?
wiki, as always
You will find the point-plane distance there too.

ryt

Sep 13, 2009 at 12:15 PM

Actualy here is something that I wanted to do:

", target="_blank">shape change

You can see how the shape changes (at beginning vertices go away from a sphere) of yellow mesh as a sphere aproaches.

CarlML

Sep 14, 2009 at 7:25 AM

A straightforward way to do without using any sqrt it would be:

int closestVert = 0;float closestDist = 100000000.0f; //Arbitraty large numberPoint3 pos(0,0,0); //The position to compare withfor (int i=0;i<numVerts;i++){    Point3 v = vertPos - pos;    float dist = (v.x * v.x) + (v.y * v.y) + (v.z * v.z); //Squared distance    if (dist < closestDist)    {        closestDist = dist;        closestVert = i;    }}

David_pb

Sep 14, 2009 at 11:04 AM

Maybe you can get it faster with a bit preprocessing. Some time ago I saw an approach, used in ASSIMP. They used an arbitrary plane to create a sorted list (the sort key was the distance of vertex to plane), after the list is created you simply take the distance of your reference vertex to the plane and search the closest entry, since the list is sorted you can do a binary search to gather some speed.

David Neubelt

Sep 14, 2009 at 3:52 PM

Is the mesh convex or concave?

If it's convex then it's simple. Pick a vertex and walk towards the point you want to go to. That is walk in the direction of smaller distance. You'll find the point much faster then comparing all distances.

You will have to maintain connectivity in your mesh though.

Concave walking can also be done but it is a little more complicated.

-= Dave

RobTheBloke

Sep 15, 2009 at 12:47 AM

Quote:
Original post by ryt
I dont understand why do you put this in dot_product()? I understand why are you subtracting, so you could get a vector from mesh_pt to other_pt and with other code I see what are you trying to accomplish.

dot(a,b){  return a.x*b.x + a.y*b.y + a.z*b.z;}lengthSquared(a){#if 0  return a.x*a.x + a.y*a.y + a.z*a.z;#else  // or....  return dot(a,a);#endif}length(a){ return sqrt( lengthSquared(a,a) );}

AndyFirth

Sep 15, 2009 at 8:18 AM

if you're trying to deform mesh A based on proximity to a plane then do it in the vertex shader.

Use the planar distance and smoothstep towards the centre of the model along the normal to the vertex... this will also give you a "bouncy" look.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.