Jump to content
• Advertisement

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

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

If you intended to correct an error in the post then please contact us.

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

##### Share on other sites
Advertisement
whats the actual problem you're trying to solve?

collision detection?

#### Share this 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,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 this 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

##### Share on other sites
See it in your What dot product means? thread.

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

#### Share this post

##### 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 this post

##### 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 this 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 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 this post

##### 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 this post

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

#### Share this post

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5
• Advertisement

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633736
• Total Posts
3013598
×

## Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!