Sign in to follow this  
ryt

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

Recommended Posts

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.

Share this post


Link to post
Share on other sites
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[i],other_pt-mesh_pt[i]))
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
A straightforward way to do without using any sqrt it would be:

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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) );
}

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this