Three-dimensional object division output apparatus and its application

Patent metadata

Field	Value
Publication number	US-10150281-B2
Application number	US-201514833884-A
Country	US
Kind code	B2
Filing date	Aug 24, 2015
Priority date	Sep 12, 2014
Publication date	Dec 11, 2018
Grant date	Dec 11, 2018

Abstract

An extraction unit extracts, from volume data, a three-dimensional object having a tree-structure including plural end-points, plural branch-points, at least one edge each connecting an end-point and a branch-point, and at least one edge each connecting two branch-points. A division position search unit searches for a division candidate position that maximizes, with respect to an output range of a three-dimensional object creation apparatus, the size of at least one of division objects obtainable by dividing the three-dimensional object at the division candidate position on one of the edges of the tree-structure. A division unit divides, at a position on the one of the edges on which the division candidate position is present, the three-dimensional object into division objects the size of at least one of which is within the output range. An output unit outputs the at least one of the division objects to the three-dimensional object creation apparatus.

First claim

What is claimed is:

1. A three-dimensional object division output apparatus comprising:
an extraction unit that extracts, from volume data, a three-dimensional object having a tree structure including a plurality of end points, a plurality of branch points, at least one edge each connecting one of the plurality of end points and one of the plurality of branch points to each other, and at least one edge each connecting two of the plurality of branch points to each other;
a division position search unit that searches for a division candidate position that maximizes, within the size of an output range of a three-dimensional object creation apparatus, the size of at least one of division objects obtainable by dividing the three-dimensional object at the division candidate position on one of the edges of the tree structure of the three-dimensional object;
a division unit that divides, at a division position on one of the edges on which the division candidate position is present, the three-dimensional object into division objects the size of at least one of which is within the output range; and
an output unit that outputs the at least one of the division objects to the three-dimensional object creation apparatus.

2. The three-dimensional object division output apparatus, as defined in claim 1 , the apparatus further comprising:
a multiplicity obtainment unit that obtains, based on all paths reaching the plurality of end points from at least one point on the tree structure of the three-dimensional object, a multiplicity for each edge by counting the number of times of passage of each path through each edge, and
wherein the division position search unit searches for the division candidate position in order of the multiplicity from an edge having a highest multiplicity.

3. The three-dimensional object division output apparatus, as defined in claim 1 , the apparatus further comprising:
a repetition control unit that repeatedly generates, with respect to the tree structure of the three-dimensional object excluding the at least one of the division objects, a new division object by the division position search unit and the division unit.

4. The three-dimensional object division output apparatus, as defined in claim 2 , the apparatus further comprising:
a repetition control unit that repeatedly generates, with respect to the tree structure of the three-dimensional object excluding the at least one of the division objects, a new division object by the multiplicity obtainment unit, the division position search unit and the division unit.

5. The three-dimensional object division output apparatus, as defined in claim 1 , wherein the division position search unit searches for the division candidate position that maximizes, with respect to the output range, a circumscribed rectangular parallelepiped that is circumscribed around a convex hull formed by envelope surfaces obtained by using end points of the tree structure included in the at least one of the division objects.

6. The three-dimensional object division output apparatus, as defined in claim 5 , wherein the circumscribed rectangular parallelepiped is a smallest rectangular parallelepiped, which is circumscribed around the convex hull and has a smallest volume.

7. The three-dimensional object division output apparatus, as defined in claim 5 , wherein the output unit outputs the at least one of the division objects by rotating the at least one of the division objects to a direction in which an edge of the circumscribed rectangular parallelepiped is parallel to an edge of a rectangular parallelepiped of the output range of the three-dimensional object creation apparatus and also the circumscribed rectangular parallelepiped is within the rectangular parallelepiped of the output range.

8. The three-dimensional object division output apparatus, as defined in claim 2 , wherein the multiplicity obtainment unit obtains, based on all paths reaching, from one of the plurality end points of the tree-structure of the three-dimensional object, the plurality of end points other than the one of the plurality of end points, the multiplicity for each edge by counting the number of times of passage of each path through each edge.

9. The three-dimensional object division output apparatus, as defined in claim 2 , wherein the multiplicity obtainment unit obtains, based on all paths reaching, from a specific one of the plurality of end points, the plurality of end points other than the specific end point or all paths reaching, from a specific point on the tree structure of the three-dimensional object other than the plurality of end points, the plurality of end points, the multiplicity for each edge by counting the number of times of passage of each path through each edge.

10. The three-dimensional object division output apparatus, as defined in claim 2 , wherein the multiplicity obtainment unit obtains, with respect to each of two partial tree structures obtained by dividing the tree structure of the three-dimensional object into two at a point on an edge selected from the at least one edge each connecting two branch points of the tree structure of the three-dimensional object to each other, the multiplicity based on all paths reaching, from the point on the selected edge, end points of the respective partial tree structures, and determines, as the multiplicity of the selected edge, the multiplicity having a smaller value of the multiplicities obtained for the two partial tree structures.

11. The three-dimensional object division output apparatus, as defined in claim 2 , wherein the multiplicity obtainment unit obtains the multiplicity for each edge by adding all of the numbers of times of passage of each path through each edge, and each of the numbers of times having been obtained for each of the plurality of end points by performing count based on all paths reaching, from one of the plurality of end points, the plurality of end points other than the one of the plurality of end points.

12. The three-dimensional object division output apparatus, as defined in claim 1 , wherein the division unit divides the three-dimensional object at the division position that makes the size of the at least one of the division objects within the output range, and at which the three-dimensional object is widest on the edge on which the division candidate position is present.

13. The three-dimensional object division output apparatus, as defined in claim 1 , wherein the division position search unit searches for the division candidate position on one of the at least one edge each connecting two branch points to each other at which the size of at least one of division objects obtainable by performing division at the one of the at least one edge changes from a size within the output range to a size exceeding the output range.

14. An operation method of a three-dimensional object division output apparatus including an extraction unit, a division position search unit, a division unit and an output unit, the method comprising:
an extraction step in which the extraction unit extracts, from volume data, a three-dimensional object having a tree structure including a plurality of end points, a plurality of branch points, at least one edge each connecting one of the plurality of end points and one of the plurality of branch points to each other, and at least one edge each connecting two of the plurality of branch points to each other;
a division position search step in which the division position search unit searches for a division candidate position that maximizes, within the size of an output range of a three-dimensional object creation apparatus, the siz

Assignees

• Fujifilm Corp

Inventors

• Sagawa Masafumi

Classifications

• B33Y50/02 Primary

  for controlling or regulating additive manufacturing processes · CPC title

• B29C64/386 Primary

  Data acquisition or data processing for additive manufacturing · CPC title