Three dimensional modeling

• US 10,217,276 B2
• Filed: 04/16/2015
• Issued: 02/26/2019
• Est. Priority Date: 04/17/2014
• Status: Active Grant

• Current Assignee: 3D Slash, Co.
• Original Assignee: 3D Slash, Co.
• Inventors: Huet, Sylvain
• Primary Examiner(s): Yang, Yi
• Application Number:
  US15/303,962
• Publication Number:
  US 20170039759A1
• Time in Patent Office: 1,412 Days
• CPC Class Codes: B29C 64/386 Data acquisition or data processing for additive manufacturing
• CPC Class Codes: B33Y 50/00 Data acquisition or data processing for additive manufacturing
• CPC Class Codes: B33Y 50/02 for controlling or regulating additive manufacturing processes
• CPC Class Codes: G05B 19/4099 Surface or curve machining, making 3D objects, e.g. desktop manufacturing
• CPC Class Codes: G05B 2219/35134 3-D cad-cam
• CPC Class Codes: G05B 2219/49007 Making, forming 3-D object, model, surface
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree
• CPC Class Codes: G06T 17/10 Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes
• CPC Class Codes: G06T 19/20 Editing of 3D images, e.g. changing shapes or colours, aligning objects or positioning parts
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/60 Analysis of geometric attributes
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80
• CPC Class Codes: G06T 7/90 Determination of colour characteristics
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: G06T 9/40 Tree coding, e.g. quadtree, octree
• CPC Class Codes: H04N 19/426 using memory downsizing methods

Abstract

Systems and methods of creating a 3 Dimensional (3D) model of an object suitable for 3D printing are described. A method comprises defining an initial cuboid of edge lengths Lx, Ly, Lz for creating the 3D model, wherein the initial cuboid implicitly includes inner cuboids such that starting from the initial cuboid each cuboid is recursively splitable into eight identical inner cuboids. Further, the method comprises iteratively, receiving an input specifying a size of an inner cuboid to be modified and a selection of a point on the screen. Based on the received user input, at least one inner cuboid which is to be modified is identified. Once the inner cube to be modified is identified, the inner cube may be modified by marking the at least one inner cuboid as filled or empty.

Claims

1. A method of creating a 3 Dimensional (3D) model of an object suitable for 3D printing, the method comprising:

defining, by a processor, an initial cuboid of edge lengths Lx, Ly, Lz for creating the 3D model, wherein the initial cuboid implicitly comprises inner cuboids such that starting from the initial cuboid each cuboid is recursively splittable into eight identical inner cuboids, wherein the initial cuboid corresponds to the root node of an octree and the inner cuboids correspond to child nodes or leaves of the octree;

iteratively receiving, through input from a user, a size of an inner cuboid to be modified and a selection of a point on the screen;

identifying at least one inner cuboid to be modified based on the size of the inner cuboid and x, y, z coordinates of the point on the screen, received through user input, wherein the at least one inner cuboid to be modified is related to an inner cuboid that is rendered at the selected point on the screen;

modifying by marking the at least one inner cuboid as filled or empty; and

creating a compressed octree representing the 3D model by modifying the octree, for each input from the user, to incorporate the modification of the at least one inner cuboid in the compressed octree; and

wherein;

each leaf of the compressed octree corresponds to an inner cuboid that is either fully filled with a particular color or fully empty; and

the modifying comprises;

replacing a node by a full leaf of a particular color when all the child nodes of the node correspond to filled inner cuboids of the particular color;

replacing a node by an empty leaf when all the child nodes of the node correspond to empty inner cuboids;

replacing a full leaf of the particular color by a node with eight child nodes when at least one of the eight child nodes of the full leaf corresponds to an inner cuboid that is marked as empty or as a different color; and

replacing an empty leaf by a node with eight child nodes when at least one of the eight child nodes of the empty leaf corresponds to an inner cuboid that is marked as filled.

2. The method according to claim 1, wherein each leaf of the compressed octree corresponds to an inner cuboid that is either fully filled or fully empty and wherein the modifying comprises:

replacing a node by a full leaf when all the child nodes of the node correspond to filled inner cuboids;

replacing a node by an empty leaf when all the child nodes of the node correspond to empty inner cuboids;

replacing a full leaf by a node with eight child nodes when at least one of the eight child nodes of the full leaf corresponds to an inner cuboid that is marked as empty; and

replacing an empty leaf by a node with eight child nodes when at least one of the eight child nodes of the empty leaf corresponds to an inner cuboid that is marked as filled.

3. The method according to claim 1, wherein the identifying the at least one inner cuboid to be modified comprises:

determining a ray from an origin outside the initial cuboid to the point; and

considering the initial cuboid to be divided by mutually perpendicular planes forming sides of the inner cuboids of the octree, identifying at most three candidate inner cuboids by performing, in directions of each of the x, y, z coordinates, the steps comprising;

ascertaining a nearest plane intersecting the ray at a minimal distance from the point and a farthest plane intersecting the ray at a maximal distance from the point;

iteratively computing, for each plane from the nearest plane to the farthest plane, an intersection between the ray and the each plane, until the intersection corresponds to a point on an edge of an inner cuboid marked as full and then considered as a candidate inner cuboid;

identifying a nearest cuboid of the at most three candidate inner cuboids, wherein the nearest cuboid of the at most three candidate inner cuboids has least distance between the corresponding intersection and the origin; and

identifying the at least one inner cuboid to be modified, wherein the at least one inner cuboid to be modified is the inner cuboid of the size input by the user that contains the nearest of the at most three candidate inner cuboids.

4. The method according to claim 1, the method further comprising:

identifying a volume of inner cuboids from the initial cuboid wherein the volume is a cuboid made of inner cuboids of the same size; and

clipping the volume of inner cuboids from the initial cuboid for independent rendering and modification of the inner cuboids in the volume.

5. The method according to claim 4 further comprising moving the volume of inner cuboids accordingly to a translation vector within the initial cuboid, wherein the moving the volume of inner cuboids comprises creating a second compressed octree for the 3D model in which:

inner cuboids which are outside the clipping volume are copied in the same position; and

inner cuboids which are inside the clipping volume are copied in their translated position inside the clipping volume.

6. The method according to claim 1, the method further comprising projecting a texture provided by the user on the initial cuboid and retaining the projection while the initial cuboid is modified to form the 3D model.

7. The method according to claim 1, the method further comprising rendering a 3 Dimensional (3D) model of an object suitable for 3D printing, wherein the rendering comprises:

receiving a file including a compressed octree representing the 3D model, wherein the compressed octree comprises a root node, child nodes, full leaves, and empty leaves;

traversing the compressed octree from a highest depth full leaf; and

for each side S of each full leaf, performing steps of;

identifying an adjacent cuboid of the side S in the octree;

determining whether the adjacent cuboid corresponds to a leaf; and

rendering the side S based on the determining, wherein the rendering comprises;

when the adjacent cuboid corresponds to the leaf, rendering the side S when the leaf is empty and not rendering the side S when the leaf is full; and

when the adjacent cuboid does not correspond to the leaf, recursively splitting the side S into equal rectangles to obtain split sides S′ and

repeating, for each split side S′

, the steps performed for the side S.

8. The method according to claim 1, the method further comprising identifying a floating vertex among the rendered surfaces and splitting a surface including the floating vertex, wherein the identifying the floating vertex comprises:

building a vertex octree, wherein each leaf of the vertex octree corresponds to a vertex of the rendered surfaces; and

traversing the vertex octree to identify the floating vertex, wherein the floating vertex is a vertex not lying at any intersection of edges.

9. A system for creating a 3 Dimensional (3D) model of an object suitable for 3D printing, the system comprising:

a processor;

one or more modules coupled to the processor, wherein any one of the modules from amongst the one or more modules is to;

define, by a processor, an initial cuboid of edge lengths Lx, Ly, Lz for creating the 3D model, wherein the initial cuboid implicitly comprises inner cuboids such that starting from the initial cuboid each cuboid is recursively splittable into eight identical inner cuboids, wherein the initial cuboid corresponds to the root node of an octree and the inner cuboids correspond to child nodes or leaves of the octree;

iteratively receive, through input from a user, a size of an inner cuboid to be modified and a selection of a point on the screen;

identify at least one inner cuboid to be modified based on the size of the inner cuboid and x, y, z coordinates of the point on the screen, received through user input, wherein the at least inner cuboid to be modified is related to an inner cuboid that is rendered at the selected point on the screen; and

modify by marking the at least one inner cuboid as filled or empty; and

wherein;

any one of the modules is to further create a compressed octree representing the 3D model by modifying the octree, for each input from the user, to incorporate the modification of the at least one inner cuboid in the compressed octree;

each leaf of the compressed octree corresponds to an inner cuboid that is either fully filled with a particular color or fully empty; and

the one or more modules is to modify by;

replacing a node by a full leaf of a particular color when all the child nodes of the node correspond to filled inner cuboids of the particular color;

replacing a node by an empty leaf when all the child nodes of the node correspond to empty inner cuboids;

replacing a full leaf of the particular color by a node with eight child nodes when at least one of the eight child nodes of the full leaf corresponds to an inner cuboid that is marked as empty or as a different color; and

replacing an empty leaf by a node with eight child nodes when at least one of the eight child nodes of the empty leaf corresponds to an inner cuboid that is marked as filled.

10. The system according to claim 9, wherein each leaf of the compressed octree corresponds to an inner cuboid that is either fully filled or fully empty and wherein the one or more modules is to further modify by:

replacing a node by a full leaf when all the child nodes of the node correspond to filled inner cuboids;

replacing a node by an empty leaf when all the child nodes of the node correspond to empty inner cuboids;

replacing a full leaf by a node with eight child nodes when at least one of the eight child nodes of the full leaf corresponds to an inner cuboid that is marked as empty; and

replacing an empty leaf by a node with eight child nodes when at least one of the eight child nodes of the empty leaf corresponds to an inner cuboid that is marked as filled.

11. The system according to claim 9, wherein the one or more modules is to further identify the at least one inner cuboid to be modified by:

determining a ray from an origin outside the initial cuboid to the point; and

considering the initial cuboid to be divided by mutually perpendicular planes forming sides of the inner cuboids of the octree, identifying at most three candidate inner cuboids by performing, in directions of each of the x, y, z coordinates, the steps comprising;

ascertaining a nearest plane intersecting the ray at a minimal distance from the point and a farthest plane intersecting the ray at a maximal distance from the point;

iteratively computing, for each plane from the nearest plane to the farthest plane, an intersection between the ray and the each plane, until the intersection corresponds to a point on an edge of an inner cuboid marked as full and then considered as a candidate inner cuboid;

identifying a nearest cuboid of the at most three candidate inner cuboids, wherein the nearest cuboid of the at most three candidate inner cuboids has least distance between the corresponding intersection and the origin; and

identifying the at least one inner cuboid to be modified, wherein the at least one inner cuboid to be modified is the inner cuboid of the size input by the user that contains the nearest of the at most three candidate inner cuboids.

12. The system according to claim 9, wherein the one or more modules is to further:

identify a volume of inner cuboids from the initial cuboid wherein the volume is a cuboid made of inner cuboids of the same size; and

clip the volume of inner cuboids from the initial cuboid for independent rendering and modification of the inner cuboids in the volume.

13. The system according to claim 12 wherein the one or more modules is to further move the volume of inner cuboids accordingly to a translation vector within the initial cuboid, wherein to move the volume of inner cuboids the one or more modules is to create a second compressed octree for the 3D model in which:

inner cuboids which are outside the clipping volume are copied in the same position; and

inner cuboids which are inside the clipping volume are copied in their translated position inside the clipping volume.

14. The system according to claim 9, wherein the one or more modules is to further project a texture provided by the user on the initial cuboid and retain the projection while the initial cuboid is modified to form the 3D model.

15. The system according to claim 9, with one or more of the one or more modules being a rendering module, wherein the rendering module is to render a 3 Dimensional (3D) model of an object suitable for 3D printing, wherein the rendering module is to:

receive a file including a compressed octree representing the 3D model, wherein the compressed octree comprises a root node, child nodes, full leaves, and empty leaves;

traverse the compressed octree from a highest depth full leaf; and

for each side S of each full leaf, perform steps of;

identifying an adjacent cuboid of the side S in the octree;

determining whether the adjacent cuboid corresponds to a leaf; and

rendering the side S based on the determining, wherein the rendering comprises;

when the adjacent cuboid corresponds to the leaf, rendering the side S when the leaf is empty and not rendering the side S when the leaf is full; and

when the adjacent cuboid does not correspond to the leaf, recursively splitting the side S into equal rectangles to obtain split sides S′ and

repeating, for each split side S′

, the steps performed for the side S.

16. The system according to claim 9, wherein the one or more modules is to further identify a floating vertex among the rendered surfaces and split a surface including the floating vertex, wherein to identify the floating vertex the one or more modules is to:

build a vertex octree, wherein each leaf of the vertex octree corresponds to a vertex of the rendered surfaces; and

traverse the vertex octree to identify the floating vertex, wherein the floating vertex is a vertex not lying at any intersection of edges.