Designing a modeled volume represented by dexels

Patent metadata

Field	Value
Publication number	US-10217291-B2
Application number	US-201213666900-A
Country	US
Kind code	B2
Filing date	Nov 1, 2012
Priority date	Nov 3, 2011
Publication date	Feb 26, 2019
Grant date	Feb 26, 2019

Abstract

It is provided a computer-implemented method for designing a modeled volume. The method comprises providing a set of dexels that represents the modeled volume, each dexel comprising a set of at least one segment representing the intersection between a line and the modeled volume, wherein the set of dexels is partitioned into groups of neighboring dexels, and wherein a memory space depending on the maximum number of segments comprised in each of the dexels of the group is allocated to each group; providing a sculpting operation on the modeled volume; and updating the set of dexels in response to the sculpting operation. Such a method improves the design of a modeled volume represented by a set of dexels.

First claim

The invention claimed is:

1. A computer-implemented method of optimizing memory allocation for designing a modeled volume, wherein the method comprises:
with respect to a subject modeled volume representing a physical product, providing at least one data structure having a grid of grids format and representing a set of dexels that represents the modeled volume, each dexel of the set of dexels comprising a set of at least one segment representing an intersection between a line of a set of lines and the modeled volume, each dexel being distinct from each line,
wherein each line of the set of lines corresponds to at most one dexel of the set of dexels, wherein each segment of the set of segments comprises a pair of boundary points on the respective line,
and wherein:
the set of lines comprises at least one subset of lines which are parallel and organized on a respective rectangular grid,
a given subset of lines being partitioned into groups of neighboring lines, each group of neighboring lines being organized on a respective rectangular grid which is a two-dimensional subpart of the rectangular grid respective to the given subset of lines, resulting in a data structure representing a subset of dexels corresponding to the given subset of lines,
the subset of dexels being partitioned into groups of neighboring dexels, each group of neighboring dexels being represented by a respective grid in the grid of grids format of the data structure representing the set of dexels,
wherein a memory space depending on maximum number of segments comprised in each respective dexel of a respective group of neighboring dexels is allocated to the respective group, and wherein memory space is allocated to each respective group of neighboring dexels to provide an optimized allocation of memory space to the set of dexels, the memory space allocated to each respective group being by one or more processors as a function of the maximum number of segments comprised in each respective dexel of the group, the function being an increasing function;
providing a sculpting operation on the modeled volume by processing the set of dexels from the optimally allocated memory space;
updating the set of dexels in response to the sculpting operation, the updating designing the modeled volume representing the physical product, wherein the designed modeled volume is usable to manufacture the physical product, wherein updating the set of dexels comprises updating groups of neighboring dexels that are impacted by the sculpting operation; and
adapting the memory space allocated to an updated group when the maximum number of segments comprised in each of the dexels of the updated group is modified;
the updating the set of dexels and the adapting the memory space being automatically implemented by the one or more processors.

2. The method of claim 1 , wherein updating the set of dexels comprises determining the groups of neighboring dexels that are impacted by the sculpting operation and updating each of the determined groups.

3. The method of claim 2 , wherein updating each of the determined groups comprises, for a respective group, updating the dexels of the respective group by parallel processing.

4. The method of claim 2 , wherein updating dexels of a respective group of the determined groups, comprises, for a respective dexel of the respective group, evaluating impact of the sculpting operation on the respective dexel, and modifying the respective dexel based on the evaluated impact.

5. The method of claim 4 , wherein evaluating the impact of the sculpting operation on the respective dexel comprises evaluating the impact of the sculpting operation on the segments of the respective dexel.

6. The method of claim 5 , wherein updating the dexels of the respective group is performed by SIMD (Single Instruction Multiple Data) parallel processing.

7. The method of claim 1 , wherein the set of dexels is partitioned into the groups of neighboring dexels in adaptation to a hardware implied in execution of the method and/or a sculpting context.

8. A system that optimizes memory allocation for designing a modeled volume, wherein the system comprises:
a memory having recorded thereon instructions for designing modeled volume;
a processor coupled to the memory and designing a subject modeled volume representing a physical product by the processor being configured to:
provide at least one data structure having a grid of grids format and representing a set of dexels that represents the modeled volume, each dexel of the set of dexels comprising a set of at least one segment representing an intersection between a line of a set of lines and the modeled volume, each dexel being distinct from each line,
wherein each line of the set of lines corresponds to at most one dexel of the set of dexels, wherein each segment of the set of segments comprises a pair of boundary points on the respective line,
and wherein:
the set of lines comprises at least one subset of lines which are parallel and organized on a respective rectangular grid,
a given subset of lines being partitioned into groups of neighboring lines, each group of neighboring lines being organized on a respective rectangular grid which is a two-dimensional subpart of the rectangular grid respective to the given subset of lines, resulting in a data structure representing a subset of dexels corresponding to the given subset of lines,
the subset of dexels being partitioned into groups of neighboring dexels, each group of neighboring dexels being represented by a respective grid in the grid of grids format of the data structure representing the set of dexels,
wherein a memory space depending on maximum number of segments comprised in each respective dexel of a respective group of neighboring dexels is allocated to the respective group, and wherein memory space is allocated to each respective group of neighboring dexels to provide an optimized allocation of memory space to the set of dexels, the memory space allocated to each respective group is a function of the maximum number of segments comprised in each respective dexel of the group, the function being an increasing function;
provide a sculpting operation on the modeled volume by processing the set of dexels from the optimally allocated memory space;
update the set of dexels in response to the sculpting operation, the updating designing the modeled volume representing the physical product, wherein the designed modeled volume is usable to manufacture the physical product, wherein updating the set of dexels comprises updating groups of neighboring dexels that are impacted by the sculpting operation; and
adapting the memory space allocated to an updated group when the maximum number of segments comprised in each of the dexels of the updated group is modified.

9. The system of claim 8 , wherein the processor is a massive parallel processing unit.

10. The system of claim 8 , wherein the system comprises a graphical user interface (GUI) communicatively configured to the processor and configured to request designing of the subject modeled volume.

11. The system of claim 10 , wherein the processor is a Graphics Processing Unit (GPU).

12. A computer program product comprising:
a non-transitory computer readable storage medium, the computer readable storage medium having instructions configured to optimize memory allocation for designing a modeled volume representing a physical product by:
providing at least one data structure having a grid of grids format and representing a set of dexels that represents the modeled volume, each dexel of the set of dexels comprising a set of at least one segment representing the intersection between

Assignees

• Dassault Systemes

Inventors

• Montana Nicolas
• Monteil Marc
• Nosenzo Romain
• Lieutier Andre

Classifications

• G06T17/00

  Three-dimensional [3D] modelling for computer graphics · CPC title

• G06T19/20 Primary

  Editing of three-dimensional [3D] images, e.g. changing shapes or colours, aligning objects or positioning parts · CPC title

• G06F30/00

  Computer-aided design [CAD] · CPC title

• G06T2219/2021

  Shape modification · CPC title

• G06F17/50

  Physics · mapped topic