Sub-volume octrees

Patent metadata

Field	Value
Publication number	US-11003166-B2
Application number	US-201616339824-A
Country	US
Kind code	B2
Filing date	Oct 12, 2016
Priority date	Oct 12, 2016
Publication date	May 11, 2021
Grant date	May 11, 2021

Abstract

In an example, a method includes receiving a first data model of an object to be generated in additive manufacturing, at a processor. Using the processor, a second data model may be determined. Determining the second data model may include generating for each of plurality of contiguous, non-overlapping sub-volumes of a volume containing the object, a sub-volume octree characterising the sub-volume and having a root node. Determining the second data model may further include generating a volume octree characterising the volume containing the object, the volume octree characterising in its lowest nodes the root nodes of the sub-volume octrees.

First claim

The invention claimed is:

1. A method comprising:
receiving, at a processor, a first data model of an object;
generating using the processor, a second data model, wherein generating the second data model comprises building a volume octree in a bottom up manner that starts with sub-volumes and proceeds to form a larger volume, the building of the volume octree comprising:
generating, for each respective sub-volume of a plurality of contiguous, non-overlapping sub-volumes of a volume containing the object, a respective sub-volume octree characterising the respective sub-volume and having a root node, the generating producing a plurality of sub-volume octrees for the plurality of continuous, non-overlapping sub-volumes; and
generating the volume octree characterising the volume containing the object based on merging sub-volume octrees of the plurality of sub-volume octrees, the volume octree characterising in its lowest nodes the root nodes of the plurality of sub-volume octrees.

2. The method of claim 1 , wherein the generating of the volume octree comprises:
inspecting groups of eight sub-volumes of a first size in the first data model, and
for each respective group of the groups:
in response to determining that the respective group includes sub-volumes that share a predetermined attribute, merging the sub-volumes of the respective group to define a volume of a second size that has the predetermined attribute;
otherwise, in response to determining that the sub-volumes of the respective group lack the predetermined attribute, merging the sub-volumes of the respective group to define a volume of the second size that lacks the predetermined attribute; and
otherwise, defining a node indicative of a volume of the second size that comprises the predetermined attribute in a sub-portion thereof.

3. The method of claim 2 , wherein the predetermined attribute comprises an indication of whether a sub-volume is entirely interior to the object.

4. The method of claim 2 , wherein generating a sub-volume octree of the plurality of sub-volume octrees comprises inspecting sub-volumes defined in a preceding iteration and defining new sub-volumes until a root node is defined.

5. The method of claim 4 , further comprising storing a sub-volume octree of the plurality of sub-volume octrees.

6. The method of claim 1 , further comprising:
extracting data from the second data model to provide a data representation of each of a plurality of layers to be generated in additive manufacturing; and
generating the object based on the data representation.

7. The method of claim 1 , wherein the merging of the sub-volume octrees comprises merging the sub-volume octrees that share an attribute.

8. The method of claim 1 , wherein the merging of the sub-volume octrees comprises merging the sub-volume octrees that lack an attribute.

9. A non-transitory machine-readable storage medium comprising instructions that upon execution cause a system to:
receive a first data model of an object;
generate a second data model, wherein generating the second data model comprises:
generating, for each respective sub-volume of a plurality of contiguous, non-overlapping sub-volumes of a volume containing the object, a sub-volume octree characterising the respective sub-volume and having a root node; and
generating a volume octree characterising the volume containing the object, the volume octree characterising in its lowest nodes the root nodes of the sub-volume octrees,
wherein generating an octree of the plurality of sub-volume octrees or the volume octree comprises forming a serialised octree representation of the object such that, in the serialised octree representation of the object, nodes are ordered such that
a node representing a sub-volume that includes a layer of the object to be generated earlier in an intended order of object generation precedes a node representing a sub-volume including a layer of the object to be generated subsequently;
nodes representing a sub-volume that includes a given layer of the object are ordered based on a level of the nodes within the octree, wherein parent nodes appear before descendent nodes; and
nodes representing a sub-volume that includes a given layer of the object and being of a same level within the octree are serialised according to a location encoding pattern.

10. The non-transitory machine-readable medium of claim 9 , wherein the location encoding pattern is a Morton code pattern.

11. A non-transitory machine-readable medium comprising instructions that upon execution cause a system to:
receive a first data model of an object;
generate a second data model, wherein generating the second data model comprises building a volume octree in a bottom up manner that starts with sub-volumes and proceeds to form a larger volume, the building of the volume octree comprising:
generating, for each respective sub-volume of a plurality of contiguous, non-overlapping sub-volumes of a volume containing the object, a respective sub-volume octree characterising the respective sub-volume and having a root node, the generating producing a plurality of sub-volume octrees for the plurality of continuous, non-overlapping sub-volumes; and
generating the volume octree characterising the volume containing the object based on merging sub-volume octrees of the plurality of sub-volume octrees, the volume octree characterising in its lowest nodes the root nodes of the plurality of sub-volume octrees.

12. The non-transitory machine-readable medium of claim 11 , wherein generating an octree of the plurality of sub-volume octrees comprises forming the octree such that:
a node representing a sub-volume that includes a layer of the object to be generated earlier in an intended order of object generation precedes a node representing a volume including a layer of the object to be generated subsequently;
for nodes representing a sub-volume that includes a given layer of the object, nodes at a coarser volumetric resolution precede nodes at a finer volumetric resolution; and
nodes representing a sub-volume that includes a given layer and being of a same resolution are serialised according to a predetermined location encoding pattern.

13. The non-transitory machine-readable medium of claim 11 , wherein the instructions upon execution cause the system to generate, based on the second model, a representation of at least part of an object to be manufactured in a layer-by-layer manufacturing process.

14. The non-transitory machine-readable medium of claim 11 , wherein each node of a sub-volume octree is represented by a bit-string of a predetermined common length and categorises a respective sub-volume as one of:
having a consistent predetermined attribute throughout the respective sub-volume,
lacking the predetermined attribute throughout the respective sub-volume, or
having the predetermined attribute in a sub-portion of the respective sub-volume.

15. The non-transitory machine-readable storage medium of claim 11 , wherein the generating of the volume octree comprises:
inspecting groups of eight sub-volumes of a first size in the first data model, and for each respective group of the groups:
in response to determining that the respective group includes sub-volumes that share a predetermined attribute, merging the sub-volumes of the respective group to define a volume of a second size that has the predetermined attribute;
otherwise, in response to determining that the sub-volumes of the respective group lack the predetermined attribute, merging the sub-volumes of the respective group to define a volume of the second size that

Assignees

• Hewlett Packard Development Co

Inventors

• Carruesco Llorens Alex
• Vinacua Alvar
• Brunet Pere
• Gonzalez Sergio
• Gonzalez Rogel Jordi
• Comino Marc
• Giralt Adroher Josep
• Abello Rosello Lluis
• Cortes I Herms Sebastia

Classifications

• Y02P10/25

  Process efficiency · CPC title

• B33Y50/00 Primary

  Data acquisition or data processing for additive manufacturing · CPC title

• G06T17/005 Primary

  Tree description, e.g. octree, quadtree · CPC title

• H04N1/46

  Colour picture communication systems · CPC title

• G05B2219/35134

  3-D cad-cam · CPC title