CGAL users discussion list

[Henrik Zimmer <>]

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

By the way, does "identical" include orientation and scale?

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.

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