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

This topic is 3292 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites
whats the actual problem you're trying to solve?

collision detection?

##### 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,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.

##### 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 on other sites

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

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

##### Share on other sites
Quote:
 Original post by rytszecs:-> distance = sqrt(dot_product(other_pt-mesh_pt,other_pt-mesh_pt)), I hope that's clearI 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 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 dmatterIt 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 on other sites
Do you know the equation of a plane?
wiki, as always
You will find the point-plane distance there too.

##### Share on other sites
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.

1. 1
2. 2
Rutin
23
3. 3
4. 4
frob
16
5. 5

• 9
• 33
• 13
• 12
• 10
• ### Forum Statistics

• Total Topics
632578
• Total Posts
3007171

×