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

Patent metadata

Field	Value
Publication number	US-10311635-B2
Application number	US-201013807322-A
Country	US
Kind code	B2
Filing date	Jun 30, 2010
Priority date	Jun 30, 2010
Publication date	Jun 4, 2019
Grant date	Jun 4, 2019

Abstract

Discovering repetitive structures in 3D models is a challenging task. A method for detecting repetitive structures in 3D models comprises sampling the 3D model using a current sampling step size, detecting repetitive structures and remaining portions of the model, determining a representative for each of the one or more repetitive structures, and as long as the detecting step yields one or more repetitive structures, reducing the current sampling step size and repeating the steps of sampling and detecting for each detected representative of a detected repetitive structure and for the remaining portions of the model, wherein the reduced sampling step size is used. The described method and device can e.g. be used for 3D model compression, 3D model repairing, or geometry synthesis.

First claim

The invention claimed is:

1. A method for detecting repetitive structures in 3D mesh models, comprising
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 structure and a remaining portion of the model having no detected repetitive structure using the reduced sampling step size to obtain sampling points;
f) repeating 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.

2. The method according to claim 1 , wherein pairs of sampling points whose transformation belongs to a common cluster in the transformation space are defined as two instances of a repetitive structure.

3. The method according to claim 2 , wherein the curvature descriptor comprises a mean curvature, Gaussian curvatures and principal curvatures.

4. The method according to claim 2 , wherein the clustering uses the mean shift algorithm.

5. The method according to claim 2 , wherein said set of transformations comprises at least one of a rotation, translation, reflection and uniform scaling.

6. The method according to claim 1 , further comprising encoding the 3D model, wherein a reference model for the repetitive structure is encoded only once, and instances of the repetitive structure are encoded by reference to the encoded reference model.

7. The method according to claim 1 , wherein the method is terminated if the detecting step yields no more repetitive structures.

8. The method according claim 1 , further comprising an initial step of calculating the determined sampling step size, wherein the determined sampling step size is calculated from parameters of the 3D mesh model.

9. The method according to claim 8 , wherein a bounding box around the 3D mesh model is constructed, the length of a diagonal of said bounding box is calculated and the determined sampling step size is set as a fraction of the diagonal length.

10. The method according to claim 1 , further comprising measuring the process run-time, wherein the method is terminated if the process run-time reaches a pre-defined time-out value.

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

12. The device according to claim 11 , wherein pairs of sampling points whose transformation belongs to a common cluster in the transformation space are defined as two instances of a repetitive structure.

13. The device according to claim 11 , further comprising an encoder for encoding the 3D model, wherein a reference model for the repetitive structure is encoded only once, and instances of the repetitive structure are encoded by reference to the encoded reference model.

14. The device according to claim 11 , further comprising comparator means for comparing the reduced sampling step size with a pre-defined minimum sampling step size.

15. The device according to claim 11 , further comprising a time measuring unit for measuring the process run-time, wherein the method is terminated if the process run-time reaches a pre-defined time-out value.

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

17. The device according to claim 16 , wherein pairs of sampling points whose transformation b

Assignees

• Cai Kangying
• Li Weiwei
• Chen Zhibo
• Interdigital Vc Holdings Inc

Inventors

• Cai Kangying
• Li Weiwei
• Chen Zhibo

Classifications

• G06T19/00 Primary

  Manipulating three-dimensional [3D] models or images for computer graphics · CPC title

• G06T17/10 Primary

  Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes · CPC title

• G06V10/426

  Graphical representations · CPC title

• G06V10/46

  Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features (colour feature extraction G06V10/56) · CPC title

• G06K9/469

  Physics · mapped topic