CGAL users discussion list

[Dimitris Tzionas <>]

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