# US 10,311,635 B2 · Method and apparatus for detecting repetitive structures in 3D mesh models > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,311,635 B2 - Document ID: US10311635B2 - Status: Granted - Kind: B2 - Application number: 13/807,322 - Filed: 2010-06-30 - Published: 2013-04-25 - Granted: 2019-06-04 - Earliest claimed: 2010-06-30 - Assignees: InterDigital VC Holdings, Inc. - Applicants: Kangying Cai; Weiwei Li; Zhibo Chen - Inventors: Kangying Cai; Weiwei Li; Zhibo Chen - Web page: https://patentgrep.com/patent/US10311635B2 ## CPC - G06T 17/10: Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes - G06T 19/00: Manipulating three-dimensional [3D] models or images for computer graphics - G06V 10/426: Graphical representations - G06V 10/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) - G06V 20/64: Three-dimensional [3D] objects - G06V 2201/11: Technique with transformation invariance effect - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING ## 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. ## Claims ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 2) The method according to claim 2, wherein the curvature descriptor comprises a mean curvature, Gaussian curvatures and principal curvatures. ### Claim 4 (depends on 2) The method according to claim 2, wherein the clustering uses the mean shift algorithm. ### Claim 5 (depends on 2) The method according to claim 2, wherein said set of transformations comprises at least one of a rotation, translation, reflection and uniform scaling. ### Claim 6 (depends on 1) 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. ### Claim 7 (depends on 1) The method according to claim 1, wherein the method is terminated if the detecting step yields no more repetitive structures. ### Claim 8 (depends on 1) 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. ### Claim 9 (depends on 8) 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. ### Claim 10 (depends on 1) 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. ### Claim 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. ### Claim 12 (depends on 11) 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. ### Claim 13 (depends on 11) 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. ### Claim 14 (depends on 11) 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. ### Claim 15 (depends on 11) 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. ### Claim 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. ### Claim 17 (depends on 16) The device according to claim 16, 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. ### Claim 18 (depends on 17) The device according to claim 17, wherein the curvature descriptor comprises a mean curvature, Gaussian curvatures and principal curvatures. ### Claim 19 (depends on 17) The device according to claim 17, wherein said clustering uses the mean shift algorithm. ### Claim 20 (depends on 17) The device according to claim 17, wherein said set of transformations comprises at least one of a rotation, translation, reflection and uniform scaling. ### Claim 21 (depends on 16) The device according to claim 16, 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. ### Claim 22 (depends on 16) The device according to claim 16, wherein the repeating is terminated if the detecting step yields no more repetitive structures. ### Claim 23 (depends on 16) The device according to claim 16, further comprising initially calculating the determined sampling step size, wherein the determined sampling step size is calculated from parameters of the 3D mesh model. ### Claim 24 (depends on 23) The device according to claim 23, 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. ### Claim 25 (depends on 16) The device according to claim 16, further comprising measuring the process run-time, wherein the method is terminated if the process run-time reaches a pre-defined time-out value.