CGAL users discussion list

[Dimitris Tzionas <>]

PS - I wonder if there is a nice way to compare two AABB trees and find in a more elegant solution the closest distance + vertices of two meshes

On Tue, Jul 29, 2014 at 6:49 PM, Dimitris Tzionas <> wrote:

This is true, I forgot to write that for the next experiments I will also have other objects. My mistake.

However they will be again simple in the sense that they will be convex (or almost convex, if there is a modeling imperfectness).

What you say is great for a ball though, but for other object one should resort to a more general approach.

Thanks for the email and the pointer!

dimitris

On Tue, Jul 29, 2014 at 6:40 PM, Jeffrey Bush <> wrote:

If one of your meshes is always a ball, you can find the closest point in the other mesh to the center of the ball using either an AABB-tree with distance queries accelerated or just a KD-Tree (which AABB-tree uses internally for optimized distance queries). Once you have the closest point in the other mesh, do the reverse: find the closest point on the ball mesh to that point. It reduces the problem to simply searching for the closest point to a single point (twice) and you get the closest points in the two meshes (with some slight off results depending on how many triangles the ball is made out of).

Jeff

On Tue, Jul 29, 2014 at 9:32 AM, Dimitris Tzionas <> wrote:

OK, so here is the solution that I found.

It's not super-ideal, but at least for now it makes things up and running.

I use Giles proposal in order to find the closest point between two meshes.

http://doc.cgal.org/latest/Polytope_distance_d/group__PkgOptimalDistances.html

One of the meshes is a ball (rather nice for this algorithm that finds distance between approximate convex hulls) but the other mesh (human body) is non-convex.

So I divide it into convex parts, and find the closest vertex of each body part to the ball.

Then I compare the results of different parts to find the best of them (smallest distance).

At the same time, when I need a specific human body vertex-ID, I create an AABB tree of the mesh,

and use the point found above in order to find the exact vertex.

http://doc.cgal.org/latest/AABB_tree/classCGAL_1_1AABB__tree.html#a1ae2a47f70d3d9511a65b8c40c8985a4

One shouldn't do a greedy search, even if runtime is not important, because the point returned from the first algorithm is not always part of the mesh (convex hull approximation is not perfect all the time or a tiny part of the body-part destroys convexity).

Maybe it's not the most efficient solution, but for now it's a good enough solution.

But if anyone has another proposal feel free to drop a line :)

Thanks for the hints!

Best,

dimitris

On Mon, Jul 28, 2014 at 2:14 PM, Giles Bathgate <> wrote:

Maybe this would be a good start:

http://en.wikipedia.org/wiki/Closest_pair_of_points

Regards,
Giles

On 28 July 2014 13:04, Dimitris Tzionas <> wrote:
> Thanks for the link Giles!
> It is interesting, following a different approach than what I was expecting,
> but I'm afraid it's not exactly what I need.
> I would really need the id's of the vertices (or triangles), not just the
> distance.
> If I'm not mistaken this method finds the distance between the two convex
> hulls, without really finding the hulls.
> So in the end of the day vertex-IDs are probably still missing.
>
> I think that CGAL::all_furthest_neighbors_2 does kind of what I need, but in
> the opposite way.
>
> Any other thought or hint on this problem would be highly appreciated.
>
>
>
> On Mon, Jul 28, 2014 at 12:27 PM, Giles Bathgate <>
> wrote:
>>
>> Is this what you are looking for?
>>
>>
>> http://doc.cgal.org/latest/Polytope_distance_d/group__PkgOptimalDistances.html
>>
>> On 28 July 2014 11:19, Dimitris Tzionas <> wrote:
>> > Hi all,
>> >
>> > I would like to find two vertices of two meshes (1 vertex per mesh) that
>> > define the closest distance between them. Or the two triangles would be
>> > fine
>> > I guess.
>> >
>> > However I'm not sure how to search for this in CGAL's documentation, I'm
>> > sure that this is doable with some existing tool (probably based on a 3d
>> > distance field and/or AABBs). Could I please get a hint (keywords/link)
>> > on
>> > what to look for?
>> >
>> > I've already implemented a collision detection with CGAL to find the
>> > triangle-triangle intersection in a triangle-soup, using AABB-trees. I
>> > guess
>> > that I should be somehow close to this, although now a simple soup with
>> > all
>> > me object-triangles wouldn't do the job.
>> >
>> > Best,
>> > dimitris
>>
>> --
>> You are currently subscribed to cgal-discuss.
>> To unsubscribe or access the archives, go to
>> https://sympa.inria.fr/sympa/info/cgal-discuss
>>
>>
>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss