Re: Finding closest Triangle to a point

First of all, thanks for answering

Kaba wrote:

That is an interesting idea. Unfortunately I don't have a solution for you, but here are my thoughts:

Considering the convexity problem, I can easily imagine what you mean. For your purposes, we can define:
a convex mesh is such that all its polygons are contained in the boundary of the convex hull formed by the vertices of the mesh.

We can define the inside of such an object as the set of points that are contained in the convex hull of the (points of the) mesh. To avoid the common misunderstanding, note that in general a convex hull in nD forms a volume (an nD object), not a surface (an (n-1)D object).

To define your actual problem: You have a scalar "potential" function, which is formed by the distance from your query point and a test point:
f(X, Y) = |X - Y|.
Given a point X, you aim to find a point Y on your mesh such that f(X, Y) is minimized.

You have thought of using a greedy approach to select a best approximation to the negative gradient direction (the direction with maximum decrease of the potential function) from a list of candidates (neighbouring polygons).

This approach has problems when the mesh contains such places where polygons share a vertex without sharing edges (a propeller). To avoid this, you should move along edges instead using the values of the potential function in the vertices. This also simplifies the evaluation of the potential function to a simple distance calculation between points. Additionally, the answer to the question "which is the closest triangle to a point?" is ambiguous, because there might be several polygons the same distance away (the closest point is a vertex).

Well such propellers won't apear. Or lets say: if so, there is at least one triangle between them sharing edges. But travelling along edges is an interesting idea. Unfortunately i got no structure which holds the edges belonging to a vertex directly. (I got an array of faces with pointers to vertices and neighboors, so walking through neighboorhood seemed like the easiest approach). I think with travelling through these face i also kind of travel edges to this point (distance to a triangle is in 3 of 7 cases the distance to a edge and in 3 other cases the distance to a vertex. last case is the simplest, because then i found my triangle)
And as these Meshes are only part of a complex object, the only situation when two (ore more) polygons could have the same distance to the point is when the shortest distance is to the shared edge of both triangles (shared vertex of these triangles). In this case it would make no difference for me which triangle is choosen, because later on i work with all of these triangles when going through neighboorhood again.
(trying to make this clear: This Mesh could be build by a non-closed NURB-Surface or said other way, you could find a plane to project this whole mesh on directly without getting edges crossing, hope this helps when trying to think of this situation)


Anyway, as with every minimizing problem, you should question whether the potential function along the edges (or polygons) is such that you won't be stuck in a local minimum. This is important especially when your initial guess is arbitrary. I am not sure if your convexity requirement is enough to guarantee this.

Well that gave me something to think of right now. It really could be that there will be an local minimum, because my initial guess is an triangle from a previous deformed area, if this is on the "wrong side" to the previous point it could fail.


As final words, I feel it is important to distinguish between finding a closest triangle w.r.t a point inside the mesh and outside the mesh. For edge based traversal, consider the pathological case of a mesh with vertices on a sphere with radius r centered on the test point X.

That would be a case, where my approach so far just gives one triangle (as i carry this list with triangles already checked, after some time all would be checked; although this wouldn't be really effiecient in this case). But as i have to work with all triangles later on, it would be no matter (again).


Right. Hope this helps to get your problem solved.


Another idea i can try, so sure it will help. And even if it won't work, it is at least one thing i sure will think of in later projects.

Thanks,
Maik
.

Relevant Pages

  • Re: Mesh Fitting
    ... to approximate the surface by a triangle mesh in some region ... The end result is a triangle mesh that approximates ... surface for the Euclidean distance transform F ...
    (comp.graphics.algorithms)
  • Re: Sets whose complement is easy to find.
    ... When H is a "manifold polytope mesh", a collection of polytopes ... of a triangle mesh whose boundary edges form a convex polygon. ... If P is inside a first triangle, then P is inside H and, therefore, not ...
    (comp.graphics.algorithms)
  • Re: Finding closest Triangle to a point
    ... i am working on a Triangle Mesh, ... To deform this geometry i have to find the closest triangle to a given ... (The Mesh can be called convex, so i thought this should work so far) ...
    (comp.graphics.algorithms)
  • Re: Questions about diamond distance.
    ... diamond "declared" distance? ... DIAMOND DISTANCE a distance flight of at least 500 kilometres. ... just one-up the 300K and do a 500K triangle or out-and-return. ...
    (rec.aviation.soaring)
  • Re: IntersectInformation Problem
    ... If you have a triangle v0, v1, v2 then u and v are barycentric coordinates ... > two questions - both to do with the age old question of picking a mesh ... > determine whether a specified mesh intersects with this ray or not). ... Then with the second problem I want to do the ...
    (microsoft.public.win32.programmer.directx.managed)
Loading