3D Printing – Abhishek Kumar, Naveen Prakash Goel, Mayur Hemani, Adobe Inc
Abstract for “Methods and apparatus to preserve structural integrity of 3-dimensional models printed at different scales”
“A computer-implemented method and apparatus to preserve structural integrity of 3-D models printed at different scales using a cueing model.”
Background for “Methods and apparatus to preserve structural integrity of 3-dimensional models printed at different scales”
“Field of Invention”
“Embodiments” refer to 3-Dimensional (3D) printing and, more specifically, to a method or apparatus for maintaining structural integrity of 3-D model when printed at different scales.
“Description of Related Art”
“3D printing is an additive? A 3-D printer works like a layering machine in manufacturing. Each layer can be viewed as a 2-Dimensional (2D), (x-y), area that is quantified into discrete points by a?printhead?. The 3-D printer. The 3-D printer’s print head can emit light and material in a grid or raster format (i.e. x-y). Each point and each 2D layer typically have a uniform height z. Multiple layers of quantized data with height z are used to print a 3-D model in an “x-y-z” voxel grid. This allows for printing the model layer by layer. The original 3-D mesh format contains infinite data. However, when the 3-D surface data is converted into layers for 3-D printing (as described below), there is a loss in data integrity due to alignment and quantization errors during digital conversion. Printing may not accurately reproduce fine details from the 3-D model.
“Since the 3-D printer can only print layers up to 250 mm thick, and the detail in the 3-D model is 1000 m high, then only four layers (that is 1000/250) of voxel data are available to reproduce the 1000 m detail. A limit of four layers will result in a poor and inconsistent reproduction of any part of the 1000 m detail that is not aligned to the z-axis of voxel grid. If the 3-D printing process had voxel layers 15 m in each direction of the grid, then 66 layers (1000/15), of voxel data would be available to incrementally replicate any portion of the 1000?m detail not aligned with z axis. The 3-D model details will be reproduced more accurately if there are 66 layers instead of just 4 layers. Unfaithful reproduction can also be caused by alignment and quantization errors in the directions x-axis, y-axis of the voxelized 3D model and the printed voxel grid. Quantization errors, as those with ordinary art skills will know, are called “rounding off”. Quantization errors are mistakes that occur when converting (quantifying) a value within a digital domain. Alignment errors are when you try to align two coordinate axes in a digital domain. For example, the x-y,y,z axis of the volume representation of a 3D model with the x-y,z voxel grid the 3-D printer’s head is required to follow when printing because of its physical design. The differences in scale between the volume representation and the voxel grid on the 3-D printer can lead to both quantization and alignment errors.
The possibility of unfaithful reproduction is made even more complicated by the fact 3-D printer software that allows users to choose a scale when printing to adjust the size and dimensions of the 3-D model. The size of the printed 3-D model will affect the reproduction of details, but not the number of layers. A model with fewer layers can lead to increased alignment and quantization errors, as shown in the above example.
“There is therefore a need to develop a method and apparatus that preserves the structural integrity of 3-D models printed at different scales.
“A method and apparatus to preserve the structural integrity of 3-D models printed at different scales. This method extracts structural elements from a 3-D model of original scale. These structural features give details about the original 3-D model’s shape. These structural elements are then grouped together to create a 3-D cueing modeling. For printing the 3-D model, the original 3-D model and the 3-D cueing models are combined.
“An apparatus to preserve the structural integrity of 3-D models printed at different scales. The apparatus comprises a computer with one or more processors. It also includes a 3-D modeling module that extracts structural features from a scaled-down 3-D model. These structural features are used to group the extracted features together to create a 3-D cueing template. A 3-D printing module is also included in the apparatus. It allows you to create a test model using the original 3-D model. The test model can then be adjusted based on the comparison of the extracted structures from the test models with the 3-D cueing features. Finally, the modified test model can be used as a 3-D print model.
A non-transient computer-readable medium for storing computer instruction that, when executed at least by one processor, causes the processor to perform a method of preserving the structural integrity of an original 3-D model when printing at different scales. This method extracts structural elements from an original 3-D model. These structural features give detail about the shape of the original 3-D model. For printing, the extracted structural features can be combined with the original 3-D model to create a 3-D cueing template.
These and other features and benefits of the present disclose may be appreciated by a review the following detailed description and the accompanying figures, in which like reference numbers refer to like parts throughout.
“The Summary presents a few concepts in simplified form. These concepts are described in detail in the Detailed Description. This Summary does not identify the key features or essential characteristics of claimed subject matter. It is also not meant to be used to determine the scope of claimed subject matter.
“The 3D Printing Process.”
As previously mentioned, 3-D printing refers to additive manufacturing. A 3-D printer works like a layering machine. The virtual blueprint is created by computer-aided design (CAD), or animation modeling software. It then?slices’ the 3-D model. The 3-D model is converted into digital cross-sections that the 3-D printer can use to guide printing. Depending on which 3-D printer is used, material or binding material are deposited onto a build platform or bed using a multi-layering method until the material/binder layering has been completed and the final 3-D model is printed.
A Standard Tessellation Language (.STL), file format, is a standard data interface between CAD software to the 3-D printer. An STL file is used to approximate the surface of a 3D model. It contains information about the position, size and shape of a triangular mesh. A surface with fewer facets is more durable.
“Before you perform a?print? The 3-D printer first accesses the 3-D model’s surface shape from an STL file and then converts it into a volume representation. Voxelization is a method that converts STL files. Voxelization is a process that converts geometric objects, which are a continuous surface representation found in a 3-D model, into a set volume elements (or “voxels”) that best approximates the structure of a continuous object’s surface. Voxelization results in a series discrete points. Each point has a specific depth in a spatial grid called a “voxel grid”. Every point in the voxel grid has volume. Therefore, 3-D models created by voxelization can have both a surface as well as a core.
Once a voxel grid is created for the 3-D model, it can be sliced into layers with a height that the user has determined in conjunction with the resolution capabilities of the 3-D printer. Layer thickness is measured in micrometers (??) and in the direction of the z-axis. The typical layer thickness is between 15 and 100 micrometers (??m). To build the model, the 3-D printer places successive layers of liquid, powder or paper (typically plastic), based on cross-sections of the 3-D model. These layers correspond to the virtual cross-sections of the CAD model and are then joined or automatically fused together to form the final 3-D model. This technique has the advantage of being able to create virtually any shape or feature.
“Problems of Scaling”
A user usually scales a 3-D model to print from a larger size, such as an 11-foot long dimension for a model of an automobile, to a smaller one (such as 1/40). While it is possible to print the original 3-D model at 1/40 scale with a printer that has a standard resolution, the printer will need 1/40th the number of layers in order to reproduce the model accurately in the z-axis. The 3-D model might not print accurately if there are fewer layers than necessary, as described elsewhere in this application.
“For example, FIG. 1A shows a top view showing a 3-D original scale model. It includes two concentric toruses: a first torus 1 and a second one 2. FIG. FIG. 1B shows the concentric toruses 1 & 2 of FIG. 1A after scaling and voxelization to print in accordance with standard methods. For example, the original 3-D model can be downloaded from a CAD software program. FIG. The FIG. 1A representation is a continuous-surface format and accurately represents the original scale 3-D model. After resizing the original 3-D model to the desired scale, and digitizing the model information into a quantization (e.g. 100 layers) suitable for 3-D printing such as by voxelization or quantization, spatial errors can naturally occur in the voxelized data (the 3-D model’s voxel grid). These spatial errors are caused by alignment and quantization errors in the various directions between the 3-D model and the printed voxel grid. These spatial errors could easily lead to structural distortions which can cause an unfaithful reproduction on printing of the 3-D model. As shown in FIG. As shown in FIG. 1B, voxelization caused the curved surfaces of larger toruses and smaller toruses to look similar. 1A now has a different shape in voxel grid. This can be seen by comparing area 102 and area 104’s voxels, as well as comparing area 106 and area 108’s voxels. Similar distortions can be found in the voxel grid’s diagonal and axial directions. These distortions in surfaces and structural features result in a poor reproduction of the printed 3-D models.
“There is a need to develop a method and apparatus that preserves the structural integrity of 3-D models printed at different scales.
“Overview of Description”
“As mentioned above, to?print? a 3-D model, the 3-D printer accesses the surface shape of the 3-D model from an STL file and converts it into a volume representation. A 3-D model can be printed by accessing the STL file containing the model’s surface. The 3-D printer then converts that surface into a volume representation. A cueing model for the 3-D model is packaged with an STL file. Cueing models are also available as STL files and provide?cues? This file is used to prepare the 3-D model for printing. The cues are a list of important features in the 3-D model. To faithfully reproduce the printed 3-D model, the significant features should be retained in any resized version of the 3-D model.
“The volume representation of a 3-D model is usually scaled by the user before printing. This allows for a different size from the original 3-D model and introduces the possibility of unfaithful reproduction.
“Three basic steps can be taken to describe embodiments of the apparatus and method of maintaining structural integrity of 3-D models printed at different scales using a 3-D cueing modeling.
“1. “1.
“2. “2.
“3. “3.
“Step 1 – Creation of the Cueing Model
The author of the cueing models scales the original 3-D modeling to a 3-D model that can be printed. This helps to ensure that the important features remain in their original relative positions, sizes, and shapes. The author might resize the original 3-D model to 1/10th of its original size using known digital processing techniques and then extract important features from the resized 1-tenth 3-D model. The author then reduces the size of the significant features by 10/1 to match the original 3-D-model size.
“Step 2 – Adjustment, If Necessary, Of The Created Cueing Model Into a Final Cueing Model
If the position, shape, and size of the resized extracted significant features results in a difference greater that a threshold, then at least one of these significant features is adjusted to minimize the difference. This process is repeated for several scale changes to the original 3-D model. If necessary, it is adjusted in order to create one or more optimized cueing modeling models. Each cueing model consists of a collection of important features that have a relative size, shape and position. This allows for comparison with the significant features of a 3-D model of similar sizes.
“Step 3 – Creation of an optimal 3-D model for printing, using the final cueing model”
A user may print a 3-D digital model they have accessed or received. The 3-D model is typically resized by the user prior to printing to extract important features. The process of extracting the important features from the 3-D model that has been resized for printing follows the same procedure as the extraction the significant features of the original 3-D modeling to create the cueing model. Details of this process are given later in the description. Compare the dimensions, shapes, and positions of the important features extracted from the 3-D model that has been resized for printing with those of the cueing models. This is important because features that are considered to be significant for faithful reproduction may not be the same size, shape, and position in the 3-D printed model. The 3-D model will then be visible as a different 3-D print of the original digital 3-D model. Based on this comparison, the embodiments adjust the 3-D modeling re-sized to print so that the relative positions, sizes and shapes of the significant features extracted from the 3-D model are in line with the position, dimensions and shapes of the cueing model’s corresponding significant features. These adjustments aim to maintain a consistent cross sectional area of the extracted features across multiple layers in the 3-D printed model. If the significant features of the 3-D model that are being resized for printing don’t have a consistent cross-sectional area between their layers, their positions, sizes, and shapes will not match the positions, sizes, and shapes of the cueing models. This lack of correspondence, as noted above, can lead to inaccurate reproduction.
The volume representation of the 3-D printed model is then adjusted and re-sized. It can then be applied to a 3D printer. After printing the volume representation of 3-D model, you should reproduce it faithfully.
“Advantages”
The “Embodiments” described herein create a 3-D cueing modeling that can be accessed by 3-D printer software. It also includes an original 3-D model. The 3-D model and 3-D cueing models are accessed by the printing software. This allows the software to adapt the processing of the 3-D modeling to make sure that the final printed model at a given scale will accurately reproduce the original 3-D model. The 3-D cueing modeling is used as a guide in the printing process. This helps to ensure that the original 3-D model does not suffer from the effects of quantization or voxel grid alignment mistakes when it is reduced to a smaller size. A tessellated mesh created from precise parametric geometry can result in a loss in precision. This is because many small flat surfaces are mangled together to create a curved surface. When a 3-D model’s tessellated mesh is scaled to a larger size, the differences between the enlarged tessellated surface and the original parametric form are magnified. To ensure that surface differences between the 3-D model and the printed version are not exacerbated, it is recommended that the 3-D cueing model be used when the 3-D model is increased in size.
“Some embodiments also allow the author to adjust the 3-D-cueing model iteratively, as mentioned above, in order to make specific sets (i.e., resizings) of cueing models data that correspond to specific print scales (i.e. scaling of the original 3-D model). Correlation of a specific 3-D cueing model to a specific range of print scale helps protect detail in the printed 3-D model from distortion/unfaithful reproduction upon printing.”
The 3-D printed 3-D model should retain the same relative size, shape and position as the original 3-D mesh representation. This will ensure that there is a consistent cross-sectional area between layers and within each layer during 3-D printing. These structural features may vary due to layering without the use of a 3-D cueing modeling to guide 3-D printing. This is dependent on how the mesh representation spatially aligns with a layer in the voxel grid, as well the resolution limitations of the 3-D printer.
As described above, the embodiments use a 3-D cueing modeling model to improve 3-D printing quality. This scale adaptive adjustment uses a digitized volume representation to access the 3-D model before printing. It preserves the structural integrity of the model when printed at the desired scale. The 3-D model has been resized to the desired scale by the printer software before printing. This resized 3-D version is now called a test model. It extracts the location, size, and shape of the structural features. The 3-D cueing model is a collection of the extracted structural features from the original 3-D model. This 3-D model is then used by the printer software to adjust the test model. After any adjustments, the test model becomes the resized 3-D print model. The printer software adjusts the printing process to ensure that the extracted structural features from the test model are proportionally placed, sized, and spaced in relation to the original scale 3-D models. Each set of extracted structural features may be used to indicate a variety of print scales. The adjusted test model can be used as the 3-D printing model after it has been adjusted so that the extracted structural elements are proportionally positioned and sized substantially the same way as in the cueing models.
“In some embodiments, the 3-D models may not need specialized cueing (hinting), when printing the model at any of a plurality scales and slicing factors. In such cases, a single cueing method is applicable when printing at any scale.
“In the illustrated embodiments, the extracted structural elements are blocks. The size, position, and shape of these blocks are used to control the layering process of the printing portion. This is done by maintaining: 1) Alignment or grid fitting of the extracted structures features; 2) Weight (consistent blocks cross-section area); and 3) Spacing, which ensures consistent inter-block separation of the extracted structurive features. Other structural features, other than blocks, could be extracted from the 3D model and used for cueing the voxelization procedure during printing.
The primary function of 3-D cueing, according to the manufacturer, is to adjust how the vector mesh of the 3-D modeling fits onto or is aligned on the cubic grid of Voxels. This alignment is used to transform the 3-D model into a solid form using 3-D printing’s multi-layering process. Because each voxel represents a greater portion of the vector mesh, the less voxels you have to work with will make 3-D cueing more important. The cueing model can also consider different resolution (layer height), restrictions that are presented by different quality 3-D printers, and user-setted layer thickness. The illustrated embodiments include model size scaling (resolution/layer high) and voxel sizes (resolution/layer tall) as coupled properties. These are because the illustrated embodiments focus on the number of layers that the voxel grid will be divided during 3-D printing. It is important to note that once a resolution has been specified, it can’t be modified mid-print for any part of the job. In the illustrated embodiments, the user can specify a voxel (corresponding to a layer height or resolution) during the creation of the default voxel grid that will be used for printing the 3-D model. The illustrated embodiments can use a first cueing sets for voxel grids with a total height of 100 voxels. For voxel networks having heights of 1000 voxels or more, they may use another cueing setting.
“Advantageously with the illustrated embodiments, authored 3D models can be faithfully reproduced without regard to scaling issues. Also, 3-D cueing can optimize detail preservation for printers with low resolution capabilities.
“Several embodiments of a method or apparatus that preserves the structural integrity of 3-D models printed at different scales are described. The following description will provide an in-depth understanding of the claimed subject matter. It will be apparent to those skilled in art that the claimed subject matter can be practiced without these details. Other times, methods, apparatuses, and systems that are known to an ordinary skilled person have not been described in sufficient detail to not obscure claimed subject matter.
“Some parts of the following description are written in terms of algorithms and symbolic representations of operations using binary digital signals stored within a memory device, special-purpose computing device or platform. The term “specific apparatus” or the like is used in this specific specification to refer to a computer that has been programmed to perform certain functions according to instructions from software. Algorithmic descriptions and symbolic representations are two examples of techniques that ordinary people of skill in signal processing or the related arts use to communicate the substance of their work. An algorithm can be described as a sequence of operations that results in a desired result. This refers to physical manipulation of physical quantities. These quantities can be stored, transferred or combined with magnetic or other signals. Common usage has made it convenient to refer to signals such as bits, data and values, elements, symbols or characters. These terms and similar terms should not be confused with physical quantities. They are simply labels. It is understood that, unless otherwise stated, all discussions using terms like?processing? will be included in this specification. ?computing,? ?calculating,? ?determining? The actions and processes of a particular apparatus such as a special-purpose computer or similar special purpose electronic computing devices, or the like, are referred to as “determining”. A special purpose computer, or a similar special-purpose electronic computing device, is capable of manipulating and transforming signals. These signals are typically represented as physical or magnetic quantities in memories, registers or other information storage devices or transmission devices or display devices of the special-purpose computer or similar special-purpose electronic computing device.
The computer 202 can be described as a type or device that uses computing devices such as a computer desktop, laptop, tablet, smartphone, and so on. The computer 202 contains a Central Processing Unit (CPU), 208, support circuits, 210, as well as a memory of 212. One or more commercially-available microprocessors, or microcontrollers, may be included in the CPU 208 to facilitate data processing and storage. The CPU 208 is supported by various support circuits 210. These circuits include power supplies, clock circuits and input/output circuits. The memory 212 contains at least one of Read Only Memory, Random Access Memory, Disk Drive Storage, Optic Storage, Removable Storage, and/or the Like.
“The memory 221 includes an operating system, a 3-D modeling module 216, and a 3-D printing modules 218 and 220. The 3-D model creation module 216, in some embodiments, is located on a separate computer to the supply module 220 and 3-D printing module 218. These separate computers are controlled by two people: an author who creates the 3-D-cueing model and a user, who then prints the 3-D model from that 3-D cueing. There may be several commercially available operating systems that are part of the operating system 214.
The 3-D modeling creation module 216 allows an author to create a 3-D cueing models 221 and package this cueing models 221 with the original 3-D model 221. This will form a package 227 which includes both the original 3-D model 231, and the original cueing mod 221 in one package. The supply module 220 makes the package 227 available to other users. The supply module 220 can either supply package 227 directly to the 3-D printer (204 via connection 207) for consumption, or indirectly by providing package 227 through the optional server 2206. This server 206 allows access to package 227 on one or more printers 204.
“The 3-D modeling creation module 216 first accesses a file containing a 3-D model 222. The 3-D model 222 typically contains a file that provides a continuous surface representation of the 3-D model. It may also include a computer-aided design (CAD), or a tessellated file format. The author of the original scale 3-D modeling 222 is usually the one who is best able to create the 3-D cueing models 221 but the author does not have to do so. Anyone can create the 3-D cueing model 221. To create the 3-D cueing cueing modeling model 221, the creator uses the cueing module creation module 224. This cueing model 221 includes the extracted structural features of the original 3-D model 222. These are the structural features that have been determined to be important and should be preserved so that any printed resized version 222 of the original 3-D model 222 can be faithfully reproduced. Additional details about the operation of cueing model creation module 228 will be provided in conjunction with FIG. 400. 4 below. After the 3-D cueing models 221 and 222 are created, a packaging module 226 bundles the 2-D cueing models 221 and 222 together in one package 227. This allows both models to be used by the 3-D printer 204. It is preferable, but not necessary, that both the original scale 3-D cueing model 221 and the 2-D cueing model 221 are in the same file format such as the STL.
“The 3-D printing module 218, in certain embodiments, includes a desktop application that allows a user to print the 3-D model faithfully by using the 3-D cueing to adjust the 3-D model prior to printing. The model access module 228 allows a user to access the package 227, which includes a 3-D model 223. The 3-D printing module 218, which is not part of computer 202, may be accessed by the model access module 228, via server 206. Or, package 227 can be input directly into the memory 212 using a portable storage device such as a USB thumb drive or computer disk.
“Test model creator module 230 creates an e-digitized 3-D representation of the model 222 in a format suitable for printing on the 3-D printer. This is in accordance to standard techniques such as voxelization (converting the original 3-D model into one grid). This 3-D digitized representation will be called a test model 231. The 3-D printing module 218 controls the creation of test model 231. This model is scaled to the scale that the user wants to print. It is usually not in one-to-one correspondence with the original 3-D model. The output will not match the original scale 3-D model due to the discretization (sometimes called quantizing). Unfaithful reproduction can often be achieved, as described previously.
The test model adjustment module 231 processes the test model 231 the same way that the original 3-D model 222 was processed. This is to extract important structural features for the creation of the cueing model 221. The same structural features are then extracted from the original 3-D model that was resized after digitization and converted into the test model. The test model adjustment module 231 then compares each extracted structural feature from the test model 231, with the corresponding cueing model 221. If there are differences in the position, shape, and size of the extracted structural elements of the test models 231 and the cueing models 221, the voxel grid is adjusted so that the test model’s position, shape, and size compare favorably with the position, shape, and size of the cueing features 221. The aspect ratios of the extracted structural features from the test model can be adjusted to match those in the cueing model 221 by adjusting their position, size, and shape. This adjustment of the location, size, and shape of the extracted structures features preserves their shape/structural integrity so that it can be printed faithfully reproducing the most important features of scale 3-D model 221.
“In some embodiments multiple sets of extracted structural elements are provided in the cueing modeling 221, one set per scale or range of scales that the 3-D model 221 may be printed. After being resized and sliced into a number of layers (e.g. 100 to 1000 layers), a first set may be used for printing the original 3-D model 222. After being resized, sliced into a second layer range (e.g. 1001 to 10,000 layers), a second set of extracted features could be used for printing the original 3-D model 222. After being resized, sliced into third-range layers (e.g., 10,000 to 100,000 layers), a third set of extracted features could be used for printing the original 3-D model.
“Once the test models are adjusted using the 3-D cueing modeling model 221, the modified test model 234 can be saved in memory 220 and made available by the supply module 220. It is then ready for consumption by the 3-D printer (204), as described previously.”
“FIG. “FIG. 2. According to one or more embodiments. The 3-D model creation module 218 performs steps 304 through 308 of method 300. It supplies a original 3-D model, packaged with a 3-D cueing template. The 3-D printing module 218 performs steps 310-314 to faithfully reproduce the original 3D model. This is done by adjusting a 3-D cueing test model using the package 3-D cueing model before printing the modified 3-D test models.
The method 300 proceeds to step 306, where the method 300 creates an 3-D cueing model. The method 300 extracts structural features from the 3-D model that represent the structural integrity of its 3-D counterpart. These structural features include 2-D plates and cuboidal blocks that are internal to 3-D models. FIG. 4 provides further details about how to extract the structural features from the 3D model. 4 below. A list of STL files is used to provide information about the position, size and form of each extracted structural feature. This creates the 3-D cueing model. This information can be provided in some cases by indicating the position and size of the vertices (which could include blocks of cubes), using a reference point to a 0,0.0 point in a standard volume x,y.z coordinate axes volume. This information can be divided into sets, which correspond to different sizes of the 3-D model after it has been resized from the original scale 3-D model.
“The method 300 continues to step 308, where method 300 bundles the created 3-D cueing modeling with the 3-D model. This allows for as faithful reproduction of the 3-D models as possible upon printing, regardless of how large the original 3-D model was. It also takes into consideration a printer’s resolution capabilities.
“The method 300 continues to step 310 where the method 300 accesses a packaged 3-D model and 3-D cueing models for printing. The method 300 moves to step 312, where method 300 creates a test model that is appropriate in size for printing using the 3-D model. 5, below. These structural features, which were used to create the cueing models, can also be extracted from the test model. The method 300 extracts structural features from the test-model and compares their size, shape, and location with the feature information in cueing. This comparison is used to determine whether adjustment is required before printing. If the aspect ratios of the extracted structural elements of the test model differ from or are within a predetermined threshold, (determined as a matter design choice), of the aspect ratios of the extracted structural components of the original scale 3D model that make up the cueing model, adjustment is required. If the aspect ratios are within a predetermined threshold or equal, it indicates that the structural integrity and ability to print the test model is preserved. This means that the test model can be printed and will faithfully reproduce the original scale 3D model.
“The method 300 proceeds into step 314 where the method 300 generates the 3-D test model that can be used for printing. The method 300 proceeds to step 314 and then ends.
“FIG. “FIG. 2. According to one or more embodiments. The method 400 extracts the structural features from the original 3D model. It then gives the location, size, and shape of these structural features as a 3-D cueing model. The 400 method begins at step 402 then proceeds to step 402. The 3-D model is converted into cubes using an octree representation. The surface representation of the original 3-D model is typically a tessellated mesh. FIG. FIG. 6 shows a top view showing a 3-D model consisting of two concentrically placed toruses. The first torus 602 is surrounded by the second torus 604. The torus 602 and 604 can each be illustrated as a tessellated mesh. Each torus 602 and 604 is represented as a plurality adjacently connected polygons. In this case, squares are used, but other shapes such tetrahedrons and octagons may also be used. FIG. FIG. 7 shows a 3-D model for the toruses in FIG. 6. The 3-D model’s surface is represented in an octree. FIG. FIG. 8 shows the 3-D model of toruses 602 & 604 as illustrated in FIG. 6 shows the interior of the 3-D model in an octree representation. An octree, a tree data structure that has eight children per node, is well-known. Octrees can be used to subdivide a space into eight octants. To create blocks of cubes, the octree representation uses known techniques to identify neighbouring nodes (cubes). Large blocks are of greater volume and therefore have structural significance in the 3-D model. These large blocks are also known as “structural features” Or?feature blocks? The 3-D model. These structural features are important because they must be preserved after the 3-D model has been resized and sliced in preparation for printing. This will ensure that the printed 3-D model is faithfully reproduced. FIG. FIG. 8 shows horizontally aligned blocks 806 & 810, vertically aligned block 808 & 812 and diagonally aligned blocks 814, 812 and 816.
“The method 400 moves to step 406, where method 400 determines the shape, size and position of the blocks that are significant structural features. Combinatorial optimization is used to identify neighboring nodes that can be combined to create larger blocks. This process is sometimes called the “knapsack problem?” FIG. FIG. 7. This illustrates combinatorial optimization. A block 702 can be formed by identifying nodes close to the surface of a 3-D model aligned with an angle of the model. A block 704 can be formed by identifying nodes that are placed diagonally to an axis. Blocks 702 and 704 are significant structural features within the model. They must be retained after resizing so that the resized model can faithfully reproduce the original 3-D model. FIG. FIG. 8 shows a block that is made up of a group of nodes with a cross-section consisting of four nodes, as indicated by 802. The block extends in the direction arrow 803 and covers the entire length of the spaceship model. Block 802 aligns with the model’s axis. Block 804 is also a sign of a large collection, which has a longitudinal direction that runs diagonally to the model’s axis. The blocks 802 and 804 represent two of the most important structural features that were extracted from the model. These must be preserved after resizing so that the resized model can faithfully reproduce the original 3-D model.
“To automatically create and identify the positions of the cuboidal blocks that are axially aligned, we specified the following constraints in the combinatorial optimization for each block:
“1. All octree nosdes Ni (N1 N2 . . . Nk), with coordinates (xi yi zi) have the property:\nXmin