Method and apparatus for detecting repetitive structures in 3D mesh models

A device for detecting repetitive structures in 3D mesh models, comprising means for

• a) generating sampling points from the 3D mesh model by sampling said 3D mesh model using a current sampling step size;
• b) clustering said sampling points into a set of sampling point clusters according to curvature descriptors associated with said sampling points;
• c) for each sampling point cluster:
• pairing the sampling points, a first and a second sampling points being paired when a value representative of the curvature descriptor associated with each of said first and second sampling point is invariant under a determined transformation,
• determining a transformation space that comprises a set of transformations used to pair said sampling points,
• clustering said transformations of said transformation space into a set of transformation clusters,
• detecting, within each transformation cluster, one or more repetitive structures from the pairs of sampling points associated with said each transformation cluster and determining a representative for each of the one or more repetitive structures,
• d) reducing the current sampling step size to obtain a reduced sampling step size,
• e) sampling each determined representative of each of the one or more detected repetitive structures and a remaining portion of the model having no detected repetitive structure using the reduced sampling step size to obtain sampling points;
• f) repeating steps b) to e) until a determined sampling step size is reached;
• and
• g) generating a compact representation of said 3D mesh model using a result of said detecting one or more repetitive structures.

A device for detecting repetitive structures in 3D mesh models, comprising a processor and a memory adapted for storing instructions that when executed by the processor cause the processor to perform

• a) generating sampling points from the 3D mesh model by sampling said 3D mesh model using a current sampling step size;
• b) clustering said sampling points into a set of sampling point clusters according to curvature descriptors associated with said sampling points;
• c) for each sampling point cluster:
• pairing the sampling points, a first and a second sampling points being paired when a value representative of the curvature descriptor associated with each of said first and second sampling point is invariant under a determined transformation,
• determining a transformation space that comprises a set of transformations used to pair said sampling points,
• clustering said transformations of said transformation space into a set of transformation clusters,
• detecting, within each transformation cluster, one or more repetitive structures from the pairs of sampling points associated with said each transformation cluster and determining a representative for each of the one or more repetitive structures,
• d) reducing the current sampling step size to obtain a reduced sampling step size,
• e) sampling each determined representative of each of the one or more detected repetitive structures and a remaining portion of the model having no detected repetitive structure using the reduced sampling step size to obtain sampling points;
• f) repeating steps b) to e) until a determined sampling step size is reached;
• and
• g) generating a compact representation of said 3D mesh model using a result of said detecting one or more repetitive structures.