CGAL users discussion list

[khaldon hmesheh <>]

Thanks again,

actually in my case is the decision that two parts are identical is very critical.

I know that to get the two parts into a common orientation/position is a complex task,

therefore I searched for some algorithms which are invariance to translation, rotation, scale etc.

According to my knowledge Hausdorff distance is applicable for 2D cases but for 3D I have no idea.

The problem is that I am using C# instead of C++ to build my application, therefore I can't use AABB from CGAL.

I will try to implement the best algorithm by myself, therefore I am searching the best choice before I start to programming.

Thanks

On Wednesday, October 9, 2013 12:16 AM, Henrik Zimmer <> wrote:

See [2] for the Hausdorff distance.

What do you mean by 100% precise? [1] is 100% precise if the two input
meshes are the same. But this is not what you have right? At least
judging by the two shapes shown in your original post, which do not
appear 100% equal (judging e.g. by the normals/flat-shading).
Between the meshes in your example the values would vary slightly.
This has not yet been investigated in detail and you would have to find
out a suitable threshold for yourself.

Note, that if the AABB-based distance computation in CGAL is fast enough
you don't need a descriptor-based pre-decision.
But you still might need to bring the two meshes into a common
orientation/position. E.g. by an iterative closest point algorithm such
as [3].

[1] http://www.rwth-graphics.de/software/spc
[2] http://en.wikipedia.org/wiki/Hausdorff_distance
[3] closest-form solution of absolute orientation using unit
quaternions, Berthold Horn, 1987

good luck

On Di, 2013-10-08 at 13:28 -0700, khaldon hmesheh wrote:
> thank you for reply
>
>        From: Henrik Zimmer <>
>        To:
>        Sent: Tuesday, October 8, 2013 9:15 PM
>        Subject: Re: [cgal-discuss] 3D Identity
>       
>       
>        >The actual 1mm test could be quite costly to compute if you>        have fine
>        >tessellations. But it could be possible to use a two-sided
>        hausdorff
>        >distance as already suggested.
>        What is meant hier with two-sided hausdorff distance? (any
>        papers, Websites etc..)
>       
>       
>        >Now, even if a 3d shape descriptor does not completely solve
>        your
>        >problem, you could still use some (efficient) descriptor as a
>        pre-test,
>        >and only if the shapes are "similar enough" you switch to the
>        actual
>        >test for the 1mm distance.
>        Which (effecient) descriptors did you mean?
>        I have used for example Shape distribution which is quite easy
>        to implement, but the result itself is not quite descriptive
>        and discriminative
>       
>        >By the way, does "identical" include orientation and scale?
>        No, I want to decide just if the two parts are geometric
>        identical. (one to one independent from the position in space)
>        The parts may lie freely in the 3d space and I search some
>        ways not to tackle with such problems
>       
>        >One suggestion could be to use the concavity-based
>        descriptors in [1]
>        >which are "invariant" to tessellation, orientation and scale.
>        >(and the scale-invariance could be disabled by removing the
>        >normalization)
>        >There is source code available, which is already partly
>        implemented
>        >using CGAL.
>        very nice job, is that result quite satisfactory? I mean the
>        result is 100% precise
>       
>        Hope it helps
>       
>        [1] http://www.rwth-graphics.de/software/spc
>       
>       
>        On Do, 2013-10-03 at 02:48 -0700, khaldon hmesheh wrote:
>        > Thanks for reply
>        >       
>        >>        ______________________________________________________________
>        >        From: Laurent Rineau (CGAL/GeometryFactory)
>        >        <>
>        >        To: "" <>
>        >        Sent: Thursday, October 3, 2013 10:55 AM
>        >        Subject: Re: [cgal-discuss] 3D Identity
>        >       
>        >       
>        >        Le jeudi 03 octobre 2013 01:43:37 khaldon hmesheh a
>        écrit :
>        >        > Hello,
>        >        >
>        >        > I am searching for some algorithms to check if two
>        3D
>        >        triangulated Shapes
>        >        > are identical. See attachement. Any suggestions or
>        help.
>        >       
>        >        >Search the web for "3d shape descriptors". There are
>        a lot of
>        >        articles! On the
>        >        >other hand, that also means that the subject is not
>        fully
>        >        solved with a single
>        >        >solution that fits all needs.
>        >       
>        >        I searched for such algorithms but as you said it is
>        not fully
>        >        solved and my problem is to decide if two parts are
>        identical
>        >        for tolerances less than 1mm.
>        >       
>        >        >Anyway, there is nothing ready to use in CGAL, as
>        far as I
>        >        know, but you can
>        >        >use CGAL to implement any algorithm found in one of
>        the
>        >        articles on the
>        >        >subject.
>        >       
>        >       
>        >        >With a second though, it seems that your problem may
>        be more
>        >        simple that the
>        >        >general shape recognition. You could use the AABB
>        Tree from>        >        CGAL to compute
>        >        >the Haussdorf between your two surfaces, and decide
>        that they
>        >        are sufficiently
>        >        >similar if that distance is lower that a given
>        bound.
>        >       
>        >        I have applied Fréchet distance  for 2D shapes and it
>        returned
>        >        a very satisfactory result.
>        >        But I never used for 3D shapes.  You mean that
>        Hausdorff
>        >        Distance is also applicable for 3D surfaces.
>        >       
>        >        --
>        >        Laurent Rineau, PhD
>        >        R&D Engineer at GeometryFactory
>        >        http://www.geometryfactory.com/
>        >        Release Manager of the CGAL Project
>        http://www.cgal.org/
>        >       
>        >       
>        >        --
>        >        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
>       
>       
>       
>       
>       



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