# US 12,602,874 B2 · Fragmentation model generation method and apparatus, and device and storage medium > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,602,874 B2 - Document ID: US12602874B2 - Status: Granted - Kind: B2 - Application number: 18/568,677 - Filed: 2022-06-22 - Published: 2024-06-27 - Granted: 2026-04-14 - Earliest claimed: 2021-07-07 - Assignees: Beijing Zitiao Network Technology Co., Ltd. - Applicants: Beijing Zitiao Network Technology Co., Ltd. - Inventors: Xuanmeng Xie - Web page: https://patentgrep.com/patent/US12602874B2 ## CPC - G06T 17/20: Finite element generation, e.g. wire-frame surface description, {tesselation} - G06T 7/11: Region-based segmentation - G06T 7/70: Determining position or orientation of objects or cameras (camera calibration G06T7/80) - G06T 17/205: {Re-meshing} - G06T 19/20: Editing of three-dimensional [3D] images, e.g. changing shapes or colours, aligning objects or positioning parts - G06T 2207/20021: Dividing image into blocks, subimages or windows - G06T 2210/12: Bounding box - G06T 2210/21: Collision detection, intersection - G06T 2210/56: Particle system, point based geometry or rendering - G06T 2219/2021: Shape modification - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## Abstract Provided are a fragmentation model generation method and apparatus, an electronic device, and a storage medium. The method comprises: obtaining a three-dimensional mesh model of an object to be fragmented (S110); randomly sampling a plurality of three-dimensional points on the surface of the three-dimensional mesh model (S120); determining a cutting model on the basis of the plurality of three-dimensional points (S130); determining a first bounding box corresponding to a first surface patch of the surface of the three-dimensional mesh model, and determining a second bounding box corresponding to a second surface patch of the surface of the cutting model (S140); determining interaction information between the first surface patch and the second surface patch according to the coordinate information of the first bounding box and the coordinate information of the second bounding box (S150); and generating a fragmentation model corresponding to the three-dimensional mesh model on the basis of the interaction information (S160). ## Claims ### Claim 1 A fragmentation model generation method, comprising: acquiring a three-dimensional mesh model for an object to be fragmented; randomly sampling a plurality of three-dimensional points on a surface of the three-dimensional mesh model; determining a cutting model on the basis of the plurality of three-dimensional points; determining a first bounding box corresponding to a first facet of the surface of the three-dimensional mesh model, and determining a second bounding box corresponding to a second facet of a surface of the cutting model; determining information about intersection between the first facet and the second facet based on coordinate information of the first bounding box and coordinate information of the second bounding box; and generating a fragmentation model corresponding to the three-dimensional mesh model on the basis of the information about intersection, wherein randomly sampling the plurality of three-dimensional points on the surface of the three-dimensional mesh model comprises: determining a first cumulative area of the first facet of the surface of the three-dimensional mesh model, determining a second cumulative area of each three-dimensional point based on a number of three-dimensional points and a total area of the surface of the three-dimensional mesh model, and determining a position of each three-dimensional point on the surface of the three-dimensional mesh model based on the first cumulative area and the second cumulative area. ### Claim 2 (depends on 1) The method of claim 1, wherein the determining a second cumulative area of each three-dimensional point based on the number of three-dimensional points and a total area of the surface of the three-dimensional mesh model, comprising: generating a random initial area based on the number of three-dimensional points and the total area of the surface of the three-dimensional mesh model; and determining a second cumulative area of each three-dimensional point based on the random initial area, the number of three-dimensional points and the total area of the surface of the three-dimensional mesh model. ### Claim 3 (depends on 2) The method of claim 2, wherein the random initial area is positively correlated with an average area, wherein the average area is determined based on a total area of the surface of the three-dimensional mesh model and the number of three-dimensional points; and wherein the second cumulative area of any three-dimensional point is the sum of the random initial area and an increment corresponding to the three-dimensional point, wherein the increment corresponding to the three-dimensional point is positively correlated with the serial number of the three-dimensional point, and positively correlated with the average area. ### Claim 4 (depends on 1) The method of claim 1, wherein the determining a position of each three-dimensional point on the surface of the three-dimensional mesh model based on the first cumulative area and the second cumulative area, comprises: determining, based on the first cumulative area and the second cumulative area, a first facet in which each three-dimensional point is located and information about area offset for each three-dimensional point within the first facet; and determine, based on the area offset information, a position of each three-dimensional point within the first facet. ### Claim 5 (depends on 4) The method of claim 4, wherein the first facet is a triangle, and the determining, based on the area offset information, a position of each three-dimensional point within the first facet, comprises: generating a parallelogram corresponding to the triangle, uniformly dividing the parallelogram into a plurality of sub-parallelograms with the same area, determining a third cumulative area of each sub-parallelogram, and determining a position of each three-dimensional point within the first facet based on the area offset information and the third cumulative area. ### Claim 6 (depends on 5) The method of claim 5, wherein the determining a position of each three-dimensional point within the first facet based on area offset information and the third cumulative area, comprises: in response to it being determined that the three-dimensional point is outside of the first facet by using the area offset information and the third cumulative area, performing central symmetrization based on the center point of the parallelogram to obtain the position of each three-dimensional point within the first facet. ### Claim 7 (depends on 1) The method of claim 1, wherein the determining information about intersection between the first facet and the second facet based on coordinate information of the first bounding box and coordinate information of the second bounding box, comprises: determining a bounding box for the three-dimensional mesh model; dividing the bounding box for the three-dimensional mesh model into a plurality of voxels; determining a first correspondence between the first bounding box and the voxels based on coordinate information of the first bounding box; determining a second correspondence between the second bounding box and the voxels based on coordinate information of the second bounding box; and determining information about intersection between the first facet and the second facet based on the first correspondence and the second correspondence. ### Claim 8 (depends on 7) The method of claim 7, wherein the determining information about intersection between the first facet and the second facet based on the first correspondence and the second correspondence, comprises: based on the first correspondence and the second correspondence, determining a candidate facet pair that may have an intersection relationship, wherein the candidate facet pair is composed of a first facet and a second facet, based on vertex distribution of the first facet and vertex distribution of the second facet, excluding facet pairs that do not intersect from the candidate facet pairs that may have intersection relationships to obtain facet pairs with intersection relationships, and based on the facet pairs with intersection relationships, determining the information about intersection between the first facet and the second facet. ### Claim 9 An electronic device comprising: a processor and a memory; the processor is configured to, when invoking programs or instructions stored in the memory, perform: acquiring a three-dimensional mesh model for an object to be fragmented; randomly sampling a plurality of three-dimensional points on a surface of the three-dimensional mesh model; determining a cutting model on the basis of the plurality of three-dimensional points; determining a first bounding box corresponding to a first facet of the surface of the three-dimensional mesh model, and determining a second bounding box corresponding to a second facet of a surface of the cutting model; determining information about intersection between the first facet and the second facet based on coordinate information of the first bounding box and coordinate information of the second bounding box; and generating a fragmentation model corresponding to the three-dimensional mesh model on the basis of the information about intersection, wherein the processor is configured to, when invoking programs or instructions stored in the memory, randomly sample the plurality of three-dimensional points on the surface of the three-dimensional mesh model by: determining a first cumulative area of the first facet of the surface of the three-dimensional mesh model, determining a second cumulative area of each three-dimensional point based on a number of three-dimensional points and a total area of the surface of the three-dimensional mesh model, and determining a position of each three-dimensional point on the surface of the three-dimensional mesh model based on the first cumulative area and the second cumulative area. ### Claim 10 (depends on 9) The electronic device of claim 9, wherein the processor is configured to, when invoking programs or instructions stored in the memory, determine a second cumulative area of each three-dimensional point based on the number of three-dimensional points and a total area of the surface of the three-dimensional mesh model, by generating a random initial area based on the number of three-dimensional points and the total area of the surface of the three-dimensional mesh model; and determining a second cumulative area of each three-dimensional point based on the random initial area, the number of three-dimensional points and the total area of the surface of the three-dimensional mesh model. ### Claim 11 (depends on 9) The electronic device of claim 9, wherein the processor is configured to, when invoking programs or instructions stored in the memory, determine a position of each three-dimensional point on the surface of the three-dimensional mesh model based on the first cumulative area and the second cumulative area, by: determining, based on the first cumulative area and the second cumulative area, a first facet in which each three-dimensional point is located and information about area offset for each three-dimensional point within the first facet; and determine, based on the area offset information, a position of each three-dimensional point within the first facet. ### Claim 12 (depends on 11) The electronic device of claim 11, wherein the first facet is a triangle, and the processor is configured to, when invoking programs or instructions stored in the memory, determine, based on the area offset information, a position of each three-dimensional point within the first facet, by: generating a parallelogram corresponding to the triangle, uniformly dividing the parallelogram into a plurality of sub-parallelograms with the same area, determining a third cumulative area of each sub-parallelogram, and determining a position of each three-dimensional point within the first facet based on the area offset information and the third cumulative area. ### Claim 13 (depends on 9) The electronic device of claim 9, wherein the processor is configured to, when invoking programs or instructions stored in the memory, determine information about intersection between the first facet and the second facet based on coordinate information of the first bounding box and coordinate information of the second bounding box, by: determining a bounding box for the three-dimensional mesh model; dividing the bounding box for the three-dimensional mesh model into a plurality of voxels; determining a first correspondence between the first bounding box and the voxels based on coordinate information of the first bounding box; determining a second correspondence between the second bounding box and the voxels based on coordinate information of the second bounding box; and determining information about intersection between the first facet and the second facet based on the first correspondence and the second correspondence. ### Claim 14 (depends on 13) The electronic device of claim 13, wherein the processor is configured to, when invoking programs or instructions stored in the memory, determine information about intersection between the first facet and the second facet based on the first correspondence and the second correspondence, by: based on the first correspondence and the second correspondence, determining a candidate facet pair that may have an intersection relationship, wherein the candidate facet pair is composed of a first facet and a second facet, based on vertex distribution of the first facet and vertex distribution of the second facet, excluding facet pairs that do not intersect from the candidate facet pairs that may have intersection relationships to obtain facet pairs with intersection relationships, and based on the facet pairs with intersection relationships, determining the information about intersection between the first facet and the second facet. ### Claim 15 A non-transitory computer-readable storage medium, storing programs or instructions, the programs or instructions causing a computer to perform: acquiring a three-dimensional mesh model for an object to be fragmented; randomly sampling a plurality of three-dimensionally points on a surface of the three-dimensional mesh model; determining a cutting model on the basis of the plurality of three-dimensional points; determining a first bounding box corresponding to a first facet of the surface of the three-dimensional mesh model, and determining a second bounding box corresponding to a second facet of a surface of the cutting model; determining information about intersection between the first facet and the second facet based on coordinate information of the first bounding box and coordinate information of the second bounding box; and generating a fragmentation model corresponding to the three-dimensional mesh model on the basis of the information about intersection, wherein the programs or instructions causing a computer to randomly sample the plurality of three-dimensional points on the surface of the three-dimensional mesh model by: determining a first cumulative area of the first facet of the surface of the three-dimensional mesh model, determining a second cumulative area of each three-dimensional point based on a number of three-dimensional points and a total area of the surface of the three-dimensional mesh model, and determining a position of each three-dimensional point on the surface of the three-dimensional mesh model based on the first cumulative area and the second cumulative area. ### Claim 16 (depends on 15) The non-transitory computer-readable storage medium of claim 15, wherein the programs or instructions causing a computer to determine information about intersection between the first facet and the second facet based on coordinate information of the first bounding box and coordinate information of the second bounding box, by: determining a bounding box for the three-dimensional mesh model; dividing the bounding box for the three-dimensional mesh model into a plurality of voxels; determining a first correspondence between the first bounding box and the voxels based on coordinate information of the first bounding box; determining a second correspondence between the second bounding box and the voxels based on coordinate information of the second bounding box; and determining information about intersection between the first facet and the second facet based on the first correspondence and the second correspondence. ### Claim 17 (depends on 16) The non-transitory computer-readable storage medium of claim 16, wherein the programs or instructions causing a computer to determine information about intersection between the first facet and the second facet based on the first correspondence and the second correspondence by: based on the first correspondence and the second correspondence, determining a candidate facet pair that may have an intersection relationship, wherein the candidate facet pair is composed of a first facet and a second facet, based on vertex distribution of the first facet and vertex distribution of the second facet, excluding facet pairs that do not intersect from the candidate facet pairs that may have intersection relationships to obtain facet pairs with intersection relationships, and based on the facet pairs with intersection relationships, determining the information about intersection between the first facet and the second facet.