JP6375768B2 - Data output restriction device for 3D object modeling - Google Patents

Description

  In the present invention, when using a three-dimensional object forming apparatus such as a 3D printer that processes a resin or the like to form a three-dimensional object based on data representing the three-dimensional object, it is determined which is inappropriate for output from the three-dimensional object forming apparatus. It relates to technology.

  In recent years, 3D printers that process and model a resin, gypsum, or the like based on data representing a three-dimensional object have become widespread as three-dimensional object modeling apparatuses. As a medical application of 3D printers, modeling data for 3D printer output is created based on CT / MRI images (DICOM format 3D voxel data) taken by medical diagnosis, and organs for surgical simulation, medical education, and informed consent Attempts have been made to output models and create artificial organs (blood vessels, bones, joints, etc.) for implantation in the body.

  3D printers have an innovation that can propagate not only information but also things remotely to the remote location via the Internet. For this reason, there has been a problem that dangerous materials such as guns and swords that have been regulated by customs have been distributed across the border in the form of data and can be easily obtained as 3D printers.

  Specifically, STL (Standard Triangulated Language) that can manufacture a handgun of a predetermined model using a 3D printer is disclosed free of charge at a certain WEB site. Although the range is somewhat inferior to that of metal, bullets made with 3D printers have some killing ability. Furthermore, the material that can be formed by the current 3D printer is limited to resin and gypsum, and the disadvantage that metal cannot be used appears behind the scenes, and it is pointed out that it is overlooked by the metal detector at the airport. In the future, as 3D printers for consumer use become widespread, it is required to have security functions such as output authentication of output data input to the 3D printer and output regulation of dangerous goods.

  On the other hand, a method of constructing a system that determines whether or not output is possible using a method similar to that of an anti-virus tool is conceivable. Polygon matching technology is required to achieve this, but polygon matching has the following problems. It has been known. Polygon data for 3D printer output (STL format, etc.), the 3D coordinate value is not an absolute dimension, so the scale varies, and the coordinate origin and angle are also set according to the characteristics of the CAD that uses the printer and the printer to be output. Is done. Therefore, even if the source is the same 3D model, if the polygon data creation method is different, the total number of polygons to be expressed also changes, and it is generally difficult to determine the identity by comparing the coordinate values of the polygon data.

  Therefore, as in Patent Document 1, a comparison method that does not depend on an angle scale based on characteristic parameters such as a moment of inertia from the center of gravity has been proposed. Patent Document 2 proposes a method of extracting feature quantities such as a distance distribution from the center of gravity of a polygon model and a crease angle with an adjacent surface and performing a comparison independent of an angle scale. Patent Document 3 proposes a method of performing a Fourier transform on an image obtained by two-dimensionally projecting a three-dimensional model onto a plurality of angles, extracting features, and comparing them.

Japanese Patent No. 3610270 JP 2000-222428 A Japanese Patent No. 5024767 Japanese Patent Application No. 2014-38076

  The above conventional techniques are all used for similar shape search, and it is left to human judgment whether or not to adopt the searched data. In the case where no judgment is made by humans, if these existing methods are applied, there is a problem that the accuracy is too rough and the output rejection determination is excessively performed. Further, the applicant has developed a technique for solving these problems and appropriately regulating output (see Patent Document 4), but there is room for improvement in accuracy.

  Therefore, an object of the present invention is to provide a three-dimensional object modeling data output regulation device capable of accurately regulating polygon model output without performing human judgment.

  In order to solve the above-mentioned problem, in the first aspect of the present invention, an apparatus for determining whether or not to regulate when outputting a polygon model expressed as a set of polygons as three-dimensional object modeling data to a three-dimensional object modeling apparatus. The restriction model database in which restriction models, which are polygon models whose output should be restricted, is registered, and polygons are included so that the number of polygons included in the target model, which is the polygon model to be output, is equal to or less than a predetermined value. Polygon reduction means for reduction and the target model from which the polygon has been reduced, the target model is moved so that the reference point of the target model is the origin of the three-dimensional coordinates, and the polygon farthest from the reference point A plurality of polygons included in a range reduced from the longest distance by a predetermined minute amount (d) as a principal axis candidate are extracted from the reference point. One of the extracted main spindle candidates that satisfies a predetermined condition is selected as a main axis, the target model is scaled and adjusted so that the selected main axis has a predetermined length, and the direction of the main axis is determined. Polygon normalization means for creating a normalized target model by rotating the target model to coincide with the first axis, and the normalized target model are registered in the regulatory model database There is provided a three-dimensional object shaping data output restriction device comprising: a polygon model matching means for checking with a restriction model and determining whether or not the output should be restricted.

  According to the first aspect of the present invention, there is provided a restriction model database in which restriction models are registered, and polygons are reduced so that the number of polygons included in the target model is equal to or less than a predetermined value. The target model is moved with respect to the model so that the reference point of the target model is the origin of the three-dimensional coordinates, and included in a range reduced by a predetermined minute amount (d) from the longest distance from the reference point to the farthest polygon. A plurality of polygons are extracted from the reference point as the main axis candidates, one main axis candidate satisfying a predetermined condition is selected as the main axis candidates, and the selected main axis has a predetermined length. The target model is scaled and adjusted so that the direction of the main axis coincides with the first axis (for example, the Z-axis), so that the predetermined position, scale, Anti-virus measures were created by creating a normalized target model and comparing the normalized target model with the regulatory model registered in the regulatory model database to determine whether the output should be regulated. Each polygon model registered in the black list (regulated model database) for the polygon model scheduled to be output to a 3D object shaping apparatus such as a 3D printer is constructed using a method similar to the tool. It is possible to collate and determine whether output is possible. In particular, since a plurality of main axis candidates that are slightly shorter than the longest distance are extracted as main axes for aligning the orientation, and one of them is selected as the main axis, the possibility that the orientation of the target model and the restriction model is increased. For this reason, even if the scale or angle of the polygon model scheduled to be output to the three-dimensional object shaping apparatus is different from that of the regulated model registered in the regulated model database, it can be determined whether or not it is appropriate. Even without making a determination, it is possible to accurately regulate the output of the polygon model.

  In the second aspect of the present invention, the reference point of the target model is a polygon average coordinate that is an average of the vertex coordinates of each polygon, which is given as an average value calculated for the polygons included in the target model. It is characterized by that.

  According to the second aspect of the present invention, since the reference point of the target model is given as the average value calculated for the polygons included in the target model, the average polygon coordinates that are the average of the vertex coordinates of each polygon are given. Even if each vertex of the polygon model scheduled to be output to the three-dimensional object shaping device is slightly different from that of the regulated model registered in the regulated model database, it can be judged whether it is appropriate or not. It is possible to quickly calculate a close position as a reference point.

  Also, in the third aspect of the present invention, the polygon normalization means selects the principal axis candidate corresponding to the polygon located at the head on the polygon array in which polygons are arranged in a predetermined order in the target model. One spindle candidate that satisfies the condition is used.

  According to the third aspect of the present invention, among the plurality of extracted spindle candidates, the spindle candidate corresponding to the first polygon on the polygon array in which polygons are arranged in a predetermined order in the target model is selected as the spindle. As a result, it is possible to select a single candidate as a main axis from multiple main axis candidates that have the longest distance, and to accurately check against the regulatory model without causing variations in the selection of main axes. Can be performed.

  In the fourth aspect of the present invention, the polygon normalization means adjusts the scaling of the target model so that the principal axis candidate has a predetermined length for each of the extracted plurality of principal axis candidates, After the target model is rotated so that the direction of the main axis candidate coincides with the first axis (for example, the Z axis), the rotated target model has the second axis (for example, the X axis) and the third axis. The longest distance direction from the reference point projected on the (XY) two-dimensional coordinate system (for example, the Y axis) to the farthest polygon is selected as a sub-axis candidate for each main axis candidate, and the reference point The sub-axis candidate with the longest three-dimensional distance or the largest inner product value with the corresponding main axis candidate is identified, and the main axis candidate corresponding to the sub-axis candidate satisfies the predetermined condition To be one main axis candidate And wherein the are.

  According to the fourth aspect of the present invention, scaling adjustment is performed on each of the extracted plurality of principal axis candidates so that the principal axis candidate has a predetermined length, and the direction of the principal axis candidate coincides with the first axis. And the longest distance direction from the reference point projected to the two-dimensional coordinate system formed by the second axis and the third axis to the farthest polygon as a sub-axis candidate. Select for each main spindle candidate, specify the sub axis candidate with the longest three-dimensional distance from the reference point, or the inner product value with the corresponding main axis candidate, and select the main axis corresponding to that sub axis candidate Since the candidate is selected as the main axis, the main axis candidate having a long three-dimensional distance of the sub-axis and a close three-dimensional direction to the sub-axis can be selected as the main axis. It is possible to perform accurately.

  In the fifth aspect of the present invention, the polygon normalizing means matches the direction of the selected main axis with one of the positive and negative specific directions of the first axis (for example, the Z axis). The direction of the principal axis projected on the (XZ) two-dimensional coordinate system formed by the first axis and the second axis (for example, the X axis) matches the specific direction of the first axis. After rotating the target model, the direction of the principal axis projected on the (YZ) two-dimensional coordinate system formed by the first axis and the third axis (for example, the Y axis) is the first axis. The target model is rotated so as to coincide with a specific direction.

  According to the fifth aspect of the present invention, in order to make the direction of the selected main axis coincide with the specific direction of the first axis (for example, the Z axis), the first axis and the second axis (for example, the X axis) After rotating the target model so that the direction of the principal axis projected on the formed (XZ) two-dimensional coordinate system matches the specific direction of the first axis, the first axis and the third axis (for example, Y The target model is rotated so that the direction of the principal axis projected on the (YZ) two-dimensional coordinate system formed by (axis) coincides with the specific direction of the first axis. It is possible to collate each of the polygon model and the restriction model registered in the restriction model database after aligning at least the longitudinal angle of the three-dimensional object.

  In the sixth aspect of the present invention, the polygon normalizing means rotates the target model so that the direction of the main axis coincides with the specific direction of the first axis (for example, the Z axis), The longest distance direction from the reference point projected on the (XY) two-dimensional coordinate system formed by the second axis (for example, the X axis) and the third axis (for example, the Y axis) to the farthest polygon is the first axis. The target model is further rotated so as to coincide with the specific direction of the three axes.

  According to the sixth aspect of the present invention, after rotating the target model so that the direction of the main axis coincides with the specific direction of the first axis (for example, the Z axis), the second axis (for example, the X axis) and the second axis The target model is set such that the longest distance direction from the reference point projected on the (XY) two-dimensional coordinate system formed by three axes (for example, the Y axis) to the farthest polygon coincides with the specific direction of the third axis. Since it is further rotated, it is possible to collate the polygon model that is scheduled to be output to the three-dimensional object shaping apparatus and the restriction model registered in the restriction model database with their angles completely matched. Become.

  Further, in the seventh aspect of the present invention, the polygon collating means is composed of two types of processes for performing an angle-independent collation process that does not depend on an angle (angle) and an angle-dependent collation process that depends on an angle. The angle-dependent collation process is executed only when it is matched by the independent collation process.

  According to the seventh aspect of the present invention, as the polygon matching, first, the angle-independent matching process that does not depend on the angle (angle) is performed, and the angle-dependent matching process is executed only when the angle-independent matching process is matched (similar). As a result, models that are significantly different can be quickly determined as dissimilar with a small processing load, and as a whole, efficient determination is possible.

  In the eighth aspect of the present invention, as the angle-independent collation processing, the polygon collating unit may calculate a total area value of polygons constituting the target model and a total area value of polygons constituting the restriction model. Is calculated, and when the absolute value of the difference between the two total values is smaller than a predetermined threshold value, the conformity determination is performed.

  According to the eighth aspect of the present invention, as the angle-independent collation processing, the total value of the areas of the polygons constituting the target model and the total value of the areas of the polygons constituting the restriction model are calculated, and the two sum values are calculated. Since the determination of conformity (similarity) is made when the absolute value of the difference is smaller than a predetermined threshold value, a value to be compared with the threshold value can be calculated by a relatively simple calculation, and quick determination of appropriateness can be made. It becomes possible.

  In the ninth aspect of the present invention, as the angle-independent collation processing, the polygon collating unit includes a sum total value of pyramid volumes having the polygon constituting the target model as a bottom surface and the reference point as a vertex, The sum of the volume of the pyramid with the polygon constituting the restriction model as the base and the reference point as the apex is calculated, and the conformity determination is made when the absolute value of the difference between the two sums is smaller than a predetermined threshold value. It is characterized by.

  According to the ninth aspect of the present invention, as the angle-independent collation processing, the total value of the pyramid volumes whose base point is the polygon constituting the target model and the reference point is the vertex, and the polygon that constitutes the restriction model is the base Since the sum total value of the pyramid volumes with the point at the apex is calculated and the absolute value of the difference between the two sum values is smaller than a predetermined threshold value, it is determined to be compatible (similar), so a relatively simple calculation As a result, a value to be compared with the threshold value can be calculated, and quick determination of suitability can be made.

  In the tenth aspect of the present invention, as the angle-independent collation processing, the polygon collating unit may calculate a total area value of polygons constituting the target model and a total area value of polygon areas constituting the restriction model. When the absolute value of the difference between the two sums is smaller than a predetermined threshold value, it is determined to be compatible (similar), and only when it is determined to be compatible, the polygon constituting the target model is used as the bottom and the reference point The sum of the volume of the pyramid with the apex as the vertex and the sum of the volume of the pyramid with the reference point as the apex with the polygon constituting the regulation model as the bottom are calculated, and the absolute value of the difference between the two sums is predetermined It is characterized in that a conformity (similarity) determination is made when the threshold value is smaller than.

  According to the tenth aspect of the present invention, as the angle-independent collation processing, a total value of the areas of the polygons constituting the target model and a total value of the areas of the polygons constituting the restriction model are calculated, and the two sum values are calculated. When the absolute value of the difference is smaller than a predetermined threshold value, a conformity (similarity) determination is made, and only when the conformance determination is made, Calculating the sum of the pyramid volume with the base of the polygon that makes up the regulation model and the reference point as the apex, and determining whether the absolute value of the difference between the two sums is smaller than a predetermined threshold As a result, a value to be compared with the threshold value can be calculated quickly and reliably, and a quick determination of suitability can be made.

  In the eleventh aspect of the present invention, as the angle-dependent collation processing, the polygon collating unit may include a polygon having the closest average polygon coordinates that are averages of vertex coordinates of the polygons constituting the target model and the restriction model. Calculate the distance between the average polygon coordinates between each other, calculate the sum of the distances between the average polygon coordinates, and determine if the average value per polygon of the total value is smaller than a predetermined threshold value. It is characterized by doing so.

  According to the eleventh aspect of the present invention, as the angle-dependent collation process, for each of the target model and the restriction model, the distance between the polygon average coordinates is calculated between the polygons whose polygon average coordinates that are the average of the vertex coordinates of the polygons that are the closest to each other. Since the total value of the distances between the average polygon coordinates is calculated and the average value per polygon of the total value is smaller than a predetermined threshold value, it is determined to be suitable (similar). Re-determination is performed on models that are determined to be similar by the dependency collation, and the determination accuracy can be improved so that polygon models that do not need to be regulated are not erroneously regulated. If the polygon model to be regulated is overlooked and output is permitted, at least no complaint from the user will occur, but in the opposite case, the 3D printer apparatus equipped with the present technology will lead to the occurrence of complaint from the user Reliability is also lost. According to the eleventh aspect of the present invention, it is possible to contribute to preventing such loss of trust.

  In the twelfth aspect of the present invention, as the angle-dependent collation processing, the polygon collating unit may determine whether the polygon average coordinate that is the average of the vertex coordinates of the polygons constituting the target model and the restriction model is the closest. The distance between corresponding vertices is calculated between each other, the total value for all the polygons of the distance is calculated, and the case where the average value per polygon of the total value is smaller than a predetermined threshold value (similar) It is characterized by making it judge.

  According to the twelfth aspect of the present invention, as the angle-dependent collation processing, for each of the target model and the regulation model, the distance between the corresponding vertices between the polygons having the closest polygon average coordinates, which is the average of the vertex coordinates of the polygons constituting the target model, Since the total value for all the polygons of the distance is calculated, and the average value per polygon of the total value is smaller than a predetermined threshold value, the conformity (similarity) is determined. It is possible to improve the determination accuracy further than the ninth aspect of the present invention so that the model determined to be similar by the dependency collation is re-determined and the polygon model that does not need to be regulated is not erroneously regulated. Become.

  According to a thirteenth aspect of the present invention, there is provided a second polygon reduction means for reducing polygons so that the number of polygons included in the restriction model is a predetermined value or less, and a restriction model with the polygons reduced. The restriction model is moved so that the reference point of the restriction model becomes the origin of the three-dimensional coordinates, and is included in a range reduced by a predetermined minute amount (d) from the longest distance from the reference point to the farthest polygon. A plurality of polygon directions that are the distance to be measured are extracted as main axis candidates, and one main axis candidate that satisfies a predetermined condition is selected as the main axis candidate from the extracted main axis candidates, so that the selected main axis has a predetermined length. The regulation model is scaled, and the regulation model is rotated so that the direction of the main axis coincides with a first axis (for example, the Z-axis), thereby obtaining a normalized regulation model. And a restriction model registration means for receiving a restriction model normalized by a restriction model normalization device comprising: a second polygon normalization means for creating a restriction model registration means for registering the received restriction model in the restriction model database. It is characterized by that.

  According to the thirteenth aspect of the present invention, the second polygon reduction means for reducing polygons so that the number of polygons included in the restriction model is equal to or less than a predetermined value, the restriction model with reduced polygons is restricted. The restriction model is moved so that the reference point of the model is the origin of the three-dimensional coordinates, and the polygon that has the distance included in the range that is reduced by a predetermined minute amount (d) from the longest distance from the reference point to the farthest polygon. Extract multiple directions as main axis candidates, select one main axis candidate that satisfies a predetermined condition from the extracted main axis candidates, and adjust the scaling of the regulation model so that the selected main axis has a predetermined length Then, by rotating the restriction model so that the direction of the main axis coincides with the first axis (for example, Z axis), a restriction model normalized to a predetermined position, scale, and inclination is created. A regulation model normalizing device having a second polygon normalizing means is separately prepared, and the normalized regulation model is received from the regulation model normalizing device, and the received regulation model is registered in the regulation model database. Therefore, it becomes possible to quickly update the regulatory model database from a remote location.

  Further, in the fourteenth aspect of the present invention, in parallel to the means for outputting the target model before polygon reduction by the polygon reduction means to the connected three-dimensional object shaping apparatus, and the three-dimensional object shaping process by the three-dimensional object shaping apparatus. Means for outputting an output stop command of the target model before the polygon reduction to the three-dimensional object shaping apparatus when it is determined by the polygon model matching means that is executed that the output should be restricted. It is further provided with the feature.

  According to the fourteenth aspect of the present invention, the target model before polygon reduction should be output to the connected three-dimensional object shaping apparatus, and the output should be regulated as a result of the collation performed by the polygon model collation means executed in parallel. When it is determined that there is an output stop command for the target model before polygon reduction, it is output to the three-dimensional object modeling device, so if it is inappropriate to output without delaying the modeling of the three-dimensional object that takes time Only the output can be canceled.

  In the fifteenth aspect of the present invention, the target model receiving means for receiving the target model via the network, and the output for transmitting data based on the output suitability determined by the polygon model matching means to the transmission source of the target model And a suitability data transmission means.

  According to the fifteenth aspect of the present invention, the target model is received via the network, and data based on the output propriety obtained by the output propriety determination is transmitted to the transmission source of the target model. Can be provided in cloud form, and there is no need to perform complicated processing on the output side. In addition, the regulation model database can be centrally managed on the cloud side, and it is not necessary to manage the regulation model database in the output control PC connected to each 3D object shaping apparatus such as a 3D printer. It is possible to determine whether or not output is appropriate based on the above.

  According to the present invention, it is possible to accurately control the output of a polygon model without performing human judgment.

1 is a hardware configuration diagram of a three-dimensional object formation system including a three-dimensional object formation data output restriction device 100 according to an embodiment of the present invention. It is a functional block diagram which shows the structure of the data output control apparatus for solid object modeling which concerns on one Embodiment of this invention. It is a flowchart which shows the process outline | summary of the data output control apparatus for solid object shaping which concerns on one Embodiment of this invention. It is a flowchart which shows the detail of the polygon reduction process of step S100. 4 is a flowchart showing details of group classification processing by polygon reduction means 10. It is a figure which shows the basic principle of polygon deletion. It is a flowchart which shows the detail of a polygon deletion process. It is a figure for demonstrating the problem which arises by a polygon deletion process. It is a flowchart which shows the detail of the deletion process of the isolated small volume group. It is a flowchart which shows the detail of the calculation process of the minimum space | interval in step S44 of FIG. It is a figure which shows the problem of the conventional polygon normalization. It is a flowchart which shows the 1st method of the polygon normalization process of step S200. It is a figure which shows the outline | summary of the polygon normalization process by a 1st method. It is a figure which shows the outline | summary of the polygon normalization process by a 1st method. It is a flowchart which shows the 2nd method of the polygon normalization process of step S200. It is a figure which shows the outline | summary of the polygon normalization process by a 2nd method. It is a figure which shows the outline | summary of the polygon normalization process by a 2nd method. It is a figure which shows the outline | summary of the polygon normalization process by a 2nd method. It is a flowchart which shows the outline | summary of a polygon collation process. It is a flowchart which shows the detail of the polygon collation process based on a total area. It is a flowchart which shows the detail of the polygon collation process based on a volume. It is a flowchart which shows the detail of the polygon collation process based on a coordinate value. It is a hardware block diagram of the solid object modeling system containing the data output control apparatus for solid object modeling in a modification. It is a hardware block diagram of a cloud type solid thing modeling system. It is a functional block diagram of a cloud type solid thing modeling system. It is a figure which shows the original polygon model before normalization. It is a figure which shows the state which normalized by the conventional system with respect to the restriction | limiting model and object model of FIG. It is a figure which shows the state which normalized by the 1st method of this embodiment with respect to the restriction | limiting model and object model of FIG.

DESCRIPTION OF EXEMPLARY EMBODIMENTS Hereinafter, preferred embodiments of the invention will be described in detail with reference to the drawings.
<1. Device configuration>
FIG. 1 is a hardware configuration diagram of a three-dimensional object formation system including a three-dimensional object formation data output restriction device 100 according to an embodiment of the present invention. The three-dimensional object modeling data output restriction device 100 according to the present embodiment can be realized by a general-purpose computer. As shown in FIG. 1, a CPU (Central Processing Unit) 1 and a RAM (a main memory of the computer) Random Access Memory) 2, a large-capacity storage device 3 such as a hard disk or flash memory for storing programs and data executed by the CPU 1, a key input I / F (interface) 4 such as a keyboard and a mouse, and 3D A data input / output I / F (interface) 5 for data communication with an external device such as a printer or a data storage medium and a display unit 6 which is a display device such as a liquid crystal display are connected to each other via a bus. ing.

  The 3D printer 7 is a general-purpose 3D printer, and is a three-dimensional object forming apparatus that forms a three-dimensional object by processing a material such as resin or gypsum based on three-dimensional object modeling data that is a polygon model representing a three-dimensional object. . The 3D printer 7 includes a data processing unit 7a and an output unit 7b. The data processing unit 7a of the 3D printer 7 is connected to the data input / output I / F 5 so that the output unit 7b models the three-dimensional object based on the three-dimensional object modeling data received from the data input / output I / F 5. It has become. In FIG. 1, the three-dimensional object formation data output restriction device 100 and the 3D printer 7 are shown in a separated form, but most of the 3D printer products currently on the market include the three-dimensional object formation data output restriction device 100. Constituent elements, such as CPU1, RAM2, storage device 3, key input I / F4 (not a keyboard / mouse for general-purpose computers, but several buttons at a numeric keypad level), data input / output I / F5, display unit 6 (several lines) A small liquid crystal panel capable of displaying the above characters and a touch panel are often superimposed to serve as a key input I / F 4). Accordingly, the 3D printer 7 itself can directly receive the three-dimensional object modeling data via the external storage medium, and can be operated to model the three-dimensional object alone (particularly this is more common in a 3D printer for consumer use). ). That is, the three-dimensional object modeling system shown in FIG. 1 is often housed in one housing and distributed as a product called “3D printer”.

  FIG. 2 is a functional block diagram illustrating a configuration of the three-dimensional object formation data output restriction device according to the present embodiment. In FIG. 2, 10 is a polygon reduction means, 20 is a polygon normalization means, 30 is a polygon model collation means, 40 is a target model storage means, and 50 is a restriction model database.

  The polygon reduction unit 10 reduces the polygons constituting the target model that is a polygon model stored in the target model storage unit 40. The polygon normalization means 20 performs processing for normalizing the polygon model from which polygons are reduced to a predetermined position, scale, and angle. The polygon model collating unit 30 collates the normalized polygon model with each regulation model, which is a polygon model in the regulation model database 50, and determines whether or not the output is appropriate.

  The polygon reduction unit 10, the polygon normalization unit 20, and the polygon model collation unit 30 are realized by the CPU 1 executing a program stored in the storage device 3. The target model storage unit 40 is a storage unit that stores a target model, which is a polygon model that is a determination target of output suitability, and is realized by the storage device 3. The polygon model is data representing a predetermined three-dimensional shape in a three-dimensional space by a set of polygons, and is output as three-dimensional object modeling data to a three-dimensional object modeling apparatus such as a 3D printer. In this embodiment, STL (Standard Triangulated Language) is adopted as the data format of the polygon model. The restriction model database 50 stores a restriction model, which is a polygon model to be restricted, into a database, and is realized by the storage device 3.

  Each component shown in FIG. 2 is actually realized by installing a dedicated program in hardware such as a computer and its peripheral devices as shown in FIG. That is, the computer executes the contents of each means according to a dedicated program. In this specification, the computer means an apparatus having an arithmetic processing unit such as a CPU and capable of data processing, and is incorporated not only in a general-purpose computer such as a personal computer but also in a “3D printer” as a product. Board computer included.

  In the storage device 3 shown in FIG. 1, a dedicated program for operating the CPU 1 and causing the computer to function as a three-dimensional object formation data output restriction device is mounted. By executing this dedicated program, the CPU 1 realizes functions as the polygon reduction means 10, the polygon normalization means 20, and the polygon model matching means 30. The storage device 3 not only functions as the target model storage unit 40 and the restriction model database 50 but also stores various data necessary for processing as the three-dimensional object formation data output restriction device.

<2. Processing action>
<2.1. Pretreatment>
Next, the processing operation of the three-dimensional object formation data output restriction device shown in FIGS. 1 and 2 will be described. First, a restriction model that is a polygon model to be registered in the restriction model database 50 is created. This is performed by reducing polygons and normalizing polygons for a restriction model that is a polygon model to be restricted. As a result, the number of polygons constituting the restriction model becomes equal to or less than the predetermined number, and is normalized and registered in the restriction model database 50. The polygon reduction and normalization of the restriction model can be performed in the same manner as the processing in the three-dimensional object formation data output restriction device described later. The polygon reduction and normalization of the restriction model may be performed by the three-dimensional object formation data output restriction device or by executing the same program on another computer.

<2.2. Process Overview>
Next, the processing operation of the three-dimensional object formation data output restriction device shown in FIGS. 1 and 2 will be described. FIG. 3 is a flowchart showing a processing outline of the three-dimensional object formation data output restriction device according to the embodiment of the present invention. First, the polygon reduction unit 10 reads a target model, which is a polygon model subject to suitability determination, from the target model storage unit 40, and reduces the polygons constituting the target model (step S100). Next, normalization of the target model from which polygons are reduced is performed (step S200). Subsequently, the normalized target model is collated with a restriction model that is a polygon model registered in the restriction model database 50 (step S300).

<2.3. Polygon reduction processing>
First, the polygon reduction process in step S100 will be described. FIG. 4 is a flowchart showing details of the polygon reduction process. The example of FIG. 4 shows a case where the target model is classified into a plurality of areas and recorded as a polygon set for each area. The region is a region obtained by dividing one solid object into a plurality of parts, and corresponds to each part as long as it is an article assembled by parts. First, the polygon reduction unit 10 reads the polygon set of the target model for one region from the target model storage unit 40 and classifies it into a plurality of groups (step S110). Next, the polygon reduction means 10 performs a polygon deletion process with respect to the polygon set of each group (step S120). The polygon reduction means 10 determines whether or not the polygon deletion process has been completed for all groups (step S130). If the polygon deletion process has not been completed for all groups, the polygon deletion process of step S120 is performed on the unprocessed group. Run. When the polygon deletion processing for all groups is completed, the polygon reduction unit 10 deletes the isolated small volume group (step S140). Subsequently, the polygon reduction means 10 synthesizes the polygon set of all groups (step S150). The polygon reduction unit 10 determines whether or not the process has been completed for all the areas (step S160). If the process has not been completed for all the areas, the processes of steps S110 to S150 are performed on the unprocessed areas. . When the processing for all the regions is completed, the polygon reduction unit 10 synthesizes the region-specific polygon set for all regions (step S170).

<2.3.1. Group classification processing>
First, the group classification process in step S110 will be described. FIG. 5 is a flowchart showing details of the group classification processing by the polygon reduction means 10. The polygon reduction means 10 first performs an initial setting (step S11). Specifically, the number of polygons P constituting the read area-specific polygon set, variables p (p = 0,..., P−1) for specifying the polygons, search status St (p), group attribute G (p ), A variable g for specifying the group is set. The search status St (p) takes one of 0, 1, and 2. St (p) = 0 is an unclassified group state, St (p) = 1 is a grouped state, and St (p) = 2 is an adjacent polygon that is a polygon adjacent to the polygon. Indicates the state that has been performed. Further, in step S11, all p of p = 0,..., P−1 are initially set as St (p) = G (p) = 0 and g = 1.

  Next, one polygon p satisfying St (p) = G (p) = 0 is extracted from all the polygons (step S12). In the initial state, all are St (p) = G (p) = 0, so that the first extraction is always performed. When there are a plurality of polygons p with St (p) = G (p) = 0, for example, the one having the smallest value of p is extracted. In step S12, when there is no polygon p with St (p) = G (p) = 0, that is, when all p = 0,..., P−1, St (p) = 2. , The group classification process is terminated assuming that it has been separated into g−1 groups. In step S12, since there is no state where St (p) = 1, St (p) is either “0” or “2”. When a polygon p satisfying St (p) = G (p) = 0 can be extracted, the search status St (p) = 1 corresponding to the extracted polygon p is set to group attribute G (p) = g.

  In step S12, one polygon p with St (p) = G (p) = 0 is extracted, the search status St (p) = 1 corresponding to the extracted polygon p, and the group attribute G (p) = g are set. If set, one polygon q satisfying St (q) = 1 is extracted from all polygons (step S13). q is a variable for specifying a polygon, and takes an integer value in q = 0,... When there are a plurality of polygons q with St (q) = 1, for example, the one having the smallest q value is extracted. In step S13, if there is no polygon q satisfying St (q) = 1, that is, if all St (q) = 0 or 2, the variable g for specifying the group is incremented by 1 (g ← g + 1). (Step S14). And it returns to step S12 and classify | categorizes into the following group.

  In step S13, when one polygon q with St (q) = 1 is extracted, St (r) = G (r) = 0 from all the polygons, and the extracted polygon q and two vertices are shared. All adjacent polygons r are extracted (step S15). r is a variable for specifying a polygon, and takes an integer value in r = 0,..., P−1, similarly to polygons p and q. “Share two vertices with polygon q” means that one side is shared with polygon q. That is, the adjacent polygon r is a polygon adjacent to the polygon q by sharing one side. The extracted adjacent polygons are set to search status St (r) = 1 and group attribute G (r) = g, respectively.

  Next, the search status St (q) = 2 for the polygon q is set (step S16). That is, the polygon q is in a state after the adjacent polygon is set. Then, returning to step S13, one polygon q satisfying St (q) = 1 is extracted from all the polygons.

  In the flowchart shown in FIG. 5, there are two loop processes: a loop constituted by steps S12, S13 and S14 and a loop constituted by steps S13, S15 and S16. In the loop composed of steps S12, S13, and S14, polygons that are not classified into groups are extracted and classified into groups (step S12), and one of the polygons that have been classified into groups is searched for adjacent polygons. If it cannot be extracted as (step S13), it is assumed that there is no polygon to be classified into the group, and the process proceeds to the next group (g ← g + 1) (step S14). In the loop composed of steps S12, S13, and S14, a group of continuous polygons is classified as one group. Therefore, in step S13, if there is no polygon with St (q) = 1, there is no polygon adjacent to any polygon already classified in the group, so the classification into group g is finished. , The process proceeds to the group g + 1 classification.

  In the loop composed of steps S13, S15, and S16, one of the polygons classified into groups is extracted as a polygon q for searching for adjacent polygons (step S13), and polygon q and two vertices are extracted from all the polygons. Is extracted as an adjacent polygon r (step S15), and the search status St (q) of the search polygon q is finished regardless of whether it can be extracted or not. In this state, St (q) = 2 is set.

  By using two loop processes, a loop composed of steps S12, S13, and S14, and a loop composed of steps S13, S15, and S16, all P polygons are continuous polygons sharing two vertices. Each group is classified into groups. When only polygons that share only one vertex are adjacent to each other, they are classified as another group. By executing the processing according to FIG. 5, the polygons constituting the region-specific polygon set are classified into a plurality of groups.

<2.3.2. Polygon deletion processing>
Next, the polygon deletion process by the polygon reduction means 10 in step S120 will be described. FIG. 6 is a diagram showing the basic principle of polygon deletion. The polygon set is actually a polygon group having a three-dimensional value in space, but the example of FIG. 6 shows a polygon group having a two-dimensional value for convenience of explanation. In the example of FIG. 6A, a polygon group consisting of 18 polygons is shown before deletion.

  FIG. 7 is a flowchart showing details of polygon deletion processing by the polygon reduction means 10. First, the polygon reduction means 10 calculates the area and perimeter of each polygon for all polygons constituting the polygon set (step S21). Next, the polygon reduction unit 10 selects a polygon having a minimum value obtained by multiplying the calculated area and circumference as a polygon to be deleted (step S22). In the example of FIG. 6, as shown in FIG. 6B, a polygon EJK composed of three vertices E, J, and K is selected as a deletion target polygon.

  Subsequently, the polygon reduction unit 10 selects the shortest one of the three sides of the deletion target polygon as the deletion target side, and calculates the midpoint of the selected deletion target side (step S23). In the example of FIG. 6, as shown in FIG. 6C, the side JK of the deletion target polygon EJK is selected as the deletion target side. Further, the midpoint O of the side JK is calculated.

  Next, the polygon reduction unit 10 deletes the deletion target polygon (step S24). As a result, the number of polygons is reduced by one. Next, the polygon reduction unit 10 sequentially selects the deleted vertex shared polygons that share the vertex with the deletion target side of the deletion target polygon (step S25). When a deleted vertex shared polygon is selected that shares two vertices with the deletion target side of the polygon to be deleted (that is, the side is shared), the polygon reduction means 10 deletes the deleted vertex shared polygon (step S26). ). In the example of FIG. 6, a polygon JKN composed of three vertices J, K, and N is deleted. This further reduces the number of polygons by one. When a deleted vertex shared polygon that shares one vertex with the deletion target side of the deletion target polygon is selected, the polygon reduction means 10 corrects the shared vertex to the midpoint calculated in step S23, The circumference is recalculated (step S27). In the example of FIG. 6, as can be seen by comparing FIG. 6C and FIG. 6D, the polygon EHJ → polygon EHO, the polygon EFK → polygon EFO, the polygon HJM → polygon HOM, the polygon JMN → polygon OMN, and the polygon FKN. → Changed to polygon FON. As a result, in the example of FIG. 6, the 18 polygons at the time of FIG. 6A are reduced to 16 at the time of FIG. 6D.

  When the processes of steps S25 to S27 are completed, the polygon reduction unit 10 determines whether the total number of polygons after the reduction is equal to or less than the set target value (step S28). As the target value, an arbitrary value can be set in advance. As a result of the determination, if the total number of polygons is not less than or equal to the target value, the process returns to step S22, and the polygon reduction means 10 minimizes the value obtained by multiplying the remaining polygons by the area and the circumference. A polygon is selected as a polygon to be deleted. If the result of determination in step S28 is that the total number of polygons is less than or equal to the target value, the polygon reduction process is terminated. By executing the processing according to the flowchart of FIG. 7, the number of polygons is reduced so as to be equal to or less than the target value set for each group.

<2.3.3. Small volume group deletion processing>
Next, the process of deleting the isolated small volume group by the polygon reduction unit 10 in step S140 will be described. Here, prior to the description of the processing for deleting the isolated small volume group, the reason for performing the processing for deleting the isolated small volume group will be described. FIG. 8 is a diagram for explaining a problem caused by polygon deletion processing. FIG. 8A shows two groups of polygon groups immediately after the group classification process in step S110 is completed. In the example of FIG. 8A, there are a left group including vertices D, E, and K and a right group including vertices D ′, E ′, and K ′. If the vertices D and D ′, the vertices E and E ′, and the vertices K and K ′ are less than the resolution of the 3D printer, respectively, when these two groups of polygons are output by the 3D printer, the vertices D and D ′, E ′, vertices K and K ′ are connected by resin or the like, and the two groups are output as connected objects. That is, the two groups are physically bonded.

  When the polygon deletion process in step S120 is performed on the right-side group of polygons shown in FIG. 8A, the polygon E′FK ′ is selected as the deletion target polygon as shown in FIG. 8B. The Further, as shown in FIG. 8C, the shortest side E'F of the deletion target polygon E'FK 'is selected as the deletion target side, and the midpoint O of the side E'F is calculated. Then, as shown in FIG. 8D, the deletion target polygon E'FK 'and the deletion vertex shared polygon D'E'F are deleted.

  As can be seen from a comparison between FIG. 8A and FIG. 8D, the two groups on the left and right sides are further apart after the polygon deletion process than before the polygon deletion process. When the distance between the two groups shown in FIG. 8D exceeds the resolution of the 3D printer, when the two groups of polygons are output by the 3D printer, the two groups are output as different objects. If the two groups are both large objects, there is no problem. However, when one becomes a very small object, for example, when one group is a main body and the other group is like a beard attached to the main body, the whiskers output separately from the main body are 3D. There is a risk that it may get into the printer and cause problems such as machine clogging. In order to eliminate such a problem, an isolated small volume group such as the above-mentioned beard is deleted.

  FIG. 9 is a flowchart showing details of the processing for deleting the isolated small volume group by the polygon reduction means 10. First, the polygon reduction unit 10 calculates the maximum value and the minimum value in the X, Y, and Z directions for all vertices of all polygons for each group (step S41). As a result, for group g, minimum value Xmin (g), maximum value Xmax (g), minimum value Ymin (g), maximum value Ymax (g), minimum value Zmin (g), maximum value Zmax (g) Is obtained. Next, the polygon reduction means 10 calculates the volume of the circumscribed cuboid for each group (step S42). Specifically, the volume V (g) of the circumscribed cuboid of the group g is calculated by executing the processing according to the following [Formula 1].

[Formula 1]
V (g) = (Xmax (g) −Xmin (g)) × (Ymax (g) −Ymin (g)) × (Zmax (g) −Zmin (g))

  The polygon reduction unit 10 executes the processes of steps S41 and S42 for all groups. Thereby, the volume of a circumscribed rectangular parallelepiped is obtained for all groups. Next, the polygon reduction unit 10 identifies a group in which the volume of the circumscribed rectangular parallelepiped is the smallest among all the groups (Step S43). Then, the polygon reduction unit 10 calculates the minimum interval between the identified group and all other groups (step S44). Details of the minimum interval calculation process in step S44 will be described later.

  Subsequently, the polygon reduction unit 10 determines whether or not the minimum interval calculated in step S44 is equal to or greater than a predetermined threshold value (step S45). The predetermined threshold for comparison with the minimum interval is preferably a numerical value corresponding to 0.2 mm at the time of 3D printer output. As a result of the determination, if the minimum interval is equal to or greater than a predetermined threshold value, the minimum volume group is separated from the nearest group by a predetermined distance or more. Is deleted (step S46). If the result of determination in step S45 is that the minimum interval is less than the predetermined threshold value, the group with the smallest volume is close to the closest group and below the resolution of the 3D printer. Does not perform the process of deleting the smallest volume group.

  When the group is deleted in step S46, the group is processed in any case where the deletion is not performed. And it returns to step S43 and specifies the group from which the volume of a circumscribed rectangular parallelepiped becomes the smallest among unprocessed groups. When the processing of step S43 to step S46 is repeated and the processing for all the groups is completed, the processing for deleting the isolated small volume group is ended.

  Details of the minimum interval calculation processing in step S44 will be described. FIG. 10 is a flowchart showing details of the minimum interval calculation processing in step S44 of FIG. The polygon reduction means 10 sets a value greater than or equal to a predetermined value for the variable dmin indicating the minimum interval as an initial value. As an initial value given to dmin, a large value that cannot be set as a minimum interval between groups may be set. Then, the polygon reduction unit 10 extracts one group h having a volume larger than that of the group g from all the groups (Step S47). As a result, the minimum value Xmin (h), the maximum value Xmax (h), the minimum value Ymin (h), the maximum value Ymax (h), the minimum value Zmin (h), and the maximum value Zmax (h) are obtained for the group h. It is done. Next, the polygon reduction means 10 calculates the minimum value of the difference between the two groups for each of the X, Y, and Z directions (step S48). Specifically, the minimum value dx of the difference in the X direction, the minimum value dy of the difference in the Y direction, and the minimum value dz of the difference in the Z direction are calculated by executing processing according to the following [Equation 2]. .

[Formula 2]
dx = Min {| Xmax (g) -Xmin (h) |, | Xmin (g) -Xmax (h) |}
dy = Min {| Ymax (g) -Ymin (h) |, | Ymin (g) -Ymax (h) |}
dz = Min {| Zmax (g) -Zmin (h) |, | Zmin (g) -Zmax (h) |}

  Subsequently, the polygon reduction unit 10 sets the maximum value among the calculated minimum values for each direction as the minimum value between groups, and compares the minimum value between groups with the minimum value between all groups among other groups that have already been processed. Then, the process of setting the smaller one as the minimum value between all groups is performed (step S49). Specifically, among the three direction-specific minimum values dx, dy, and dz calculated in step S48, the inter-group minimum value Max (dx, dy, dz) that takes the maximum value is compared with dmin, and Max ( When dx, dy, dz) <dmin, dmin = Max (dx, dy, dz). As a result, the minimum value between all groups, which is the minimum value among the minimum values between groups, is recorded in dmin.

  When the processes of steps S47, S48, and S49 are repeatedly executed and the processes for all the groups having a volume larger than the group g are finished, the minimum interval calculation process shown in FIG. Thus, the minimum interval dmin is compared with the threshold value.

<2.3.4. Polygon set composition>
As shown in the flowchart of FIG. 4, in step S150, the polygon reduction unit 10 combines the polygon sets of all groups to obtain an updated polygon set by region. Further, in step S170, the polygon reduction means 10 synthesizes a polygon set for each region of all areas to obtain a composite polygon set. Both synthesis processes are performed by simply combining the polygon sets for each area excluding the header portion and recording the total number of polygons in the header portion. The composite polygon set is a target model from which polygons are reduced.

<2.4. Polygon normalization processing>
Next, the polygon normalization process in step S200 will be described. In the above-mentioned Patent Document 4, the applicant adjusts the scale of the target model so that the longest distance from the reference point of the target model to the farthest polygon becomes a predetermined length so that the direction of the longest distance matches the Z axis. A technique is proposed in which the target model is normalized to a predetermined position, scale and inclination by rotating the target model, and collated with the regulation model. In Patent Document 4, since the direction of the longest distance is the main axis, if the target model has symmetry, the reference point is uniquely determined, but there are a plurality of polygons having the same distance from the reference point. The main axis defined in the direction of the longest distance polygon average point is determined by the size of the error component included in the distance calculation from the multiple main axis candidates, so the selected main axis varies from model to model. Not uniquely determined (Because the XYZ coordinates of each polygon are recorded as real values, errors accumulate due to arithmetic operations involving real number multiplication such as scaling and rotation, and how errors are accumulated varies from polygon to polygon) . For example, if there are six principal axis candidates having the same longest distance in each of the restriction model and the target model, when trying to determine only by the magnitude relationship of the distance from the reference point to the polygon average point, Predicting which one will be selected is mathematically difficult and is determined by the feeling of rolling the dice. Search for candidate spindles from the top of the polygon array (usually the polygon with the smallest polygon number) where polygons are arranged in the specified order in the target model, and unify the method to select the longest distance polygon found first as the spindle. However, even if the distance is physically the same, if the subsequent polygon is slightly longer by a calculation error, the direction of the subsequent polygon may be selected as the main axis. Then, different spindles may be selected for the regulation model and the target model. In this case, angle correction is performed with reference to different principal axes. However, in the case of perfect symmetry, the shape corrected with reference to different principal axes is the same, so there is no problem in verification. However, if there is an asymmetric part, there is a problem that a part of the shape corrected with respect to different main axes becomes inconsistent and proper matching cannot be performed.

  FIG. 11 is a diagram showing problems of conventional polygon normalization. 11A and 11B, the left side shows the target model, and the right side shows the restriction model. FIG. 11A shows a case where the target model and the regulation model are both completely symmetric. In the example of FIG. 11A, the two longest distance directions of the main axis candidate 1 and the main axis candidate 2 may be selected as the main axes. At this time, as shown in FIG. 11 (a), even if the main axis candidate 1 indicated by the solid line is selected as the main axis in the target model and the main axis candidate 2 indicated by the broken line is selected as the main axis in the restriction model, appropriate verification is performed. Is possible. However, as shown in FIG. 11 (b), when it is not completely symmetric, in the target model, the principal axis candidate 1 indicated by the solid line is selected as the principal axis, and in the restriction model, the candidate main axis candidate 2 indicated by the broken line is selected as the principal axis. It is difficult to perform proper verification. In order to deal with such a problem, the present invention proposes two new methods for polygon normalization processing.

<2.4.1. Polygon normalization processing (first method)>
There are two methods for polygon normalization processing in step S200. First, the first method will be described. FIG. 12 is a flowchart showing a first method of polygon normalization processing in step S200. Here, the number N of polygons of the target model in which the number of polygons has been reduced in step S100, and the variable i (i = 0,..., N−1) for specifying the polygon are set, and the vertex of each polygon i is set to (Xk (i ), Yk (i), Zk (i)). k indicates a vertex number, and in this embodiment, since the polygon is a triangle, it takes three values, k = 0, 1, and 2.

  First, a reference point in the target model in which the number of polygons is reduced in step S100 is calculated (step S201). Specifically, for each polygon constituting the polygon model, an average point that is the average of the vertices is calculated, and an average value of the average points of N polygons that constitute the polygon model is calculated as a reference point of the polygon model. Specifically, first, an average point (Xc (i), Yc (i), Zc (i)) of each polygon is calculated by executing processing according to the following [Equation 3].

[Formula 3]
Xc (i) = {X0 (i) + X1 (i) + X2 (i)} / 3
Yc (i) = {Y0 (i) + Y1 (i) + Y2 (i)} / 3
Zc (i) = {Z0 (i) + Z1 (i) + Z2 (i)} / 3

  Next, a reference point (Xg, Yg, Zg) of the polygon model is calculated by executing processing according to the following [Equation 4].

[Formula 4]
Xg = {Σ _{i = 0, N−1} Xc (i)} / N
Yg = {Σi = _{0, N−1} Yc (i)} / N
Zg = {Σ _{i = 0, N−1} Zc (i)} / N

  In the above [Expression 4], the subscript “i = 0, N−1” of Σ indicates that the sum is obtained when i is an integer from 0 to N−1. The same applies to the following equations. 13 and 14 are diagrams showing an outline of the first method of polygon normalization processing. The object shown in FIG. 13 and FIG. 14 as a large cuboid and a small cuboid is an example of a target model. FIG. 13A shows a target model before normalization in an XYZ three-dimensional space.

  Next, the target model is moved (step S202). Specifically, all the polygons constituting the target model are moved so that the reference point (Xg, Yg, Zg) is located at the origin (0, 0, 0) of the three-dimensional coordinates. Specifically, the target model is moved by executing processing according to the following [Equation 5].

[Formula 5]
Xk (i) ← Xk (i) -Xg
Yk (i) ← Yk (i) −Yg
Zk (i) ← Zk (i) -Zg

  After the movement, the average point (Xc (i), Yc (i), Zc (i)) of each polygon is recalculated by executing the processing according to the above [Equation 3].

  Next, the distance from the reference point (Xg, Yg, Zg) after moving to the origin to the average point of each polygon is calculated, and the longest longest distance is obtained (step S203). Specifically, the longest distance Lmax is calculated by executing processing according to the following [Equation 6].

[Formula 6]
Lmax
= Max _{i = 0, N-1} {(Xc (i)) ² + (Yc (i)) ² + (Zc (i)) ² } ^1/2
= {(Xc (im)) ² + (Yc (im)) ² + (Zc (im)) ² } ^1/2

  In the above [Expression 6], the subscript “i = 0, N−1” of Max indicates that the maximum value is selected when i takes all integers from 0 to N−1. The same applies to the following equations. “Im” indicates the polygon number of the farthest polygon which is the polygon having the maximum distance from the reference point.

  Next, a plurality of spindle candidates are extracted (step S204). Specifically, all the spindle candidates whose distance from the reference point (Xg, Yg, Zg) to the average point of each polygon is equal to or greater than the longest distance Lmax−the minute amount d are extracted. The minute amount d has a certain difference in fraction due to an error in floating-point arithmetic, etc., and can be set so as to be physically coincident with the longest distance Lmax. Therefore, the minute amount d can be set in the range of Lmax × 0.00001 to Lmax × 0.001, but in this embodiment, it is set to d = Lmax × 0.0001. In step S204, candidate spindles corresponding to the polygon i satisfying the condition shown in [Formula 7] below are extracted.

[Formula 7]
{(Xc (i)) ² + (Yc (i)) ² + (Zc (i)) ² } ^1/2 ≧ Lmax−d

  As the main axis candidates, all those whose lengths of the line segment connecting the reference point and the average point of the extracted polygon i satisfy the condition shown in [Formula 7] are extracted. Therefore, the principal axis candidate is a line segment having a direction and a length. The spindle candidate naturally includes the longest distance candidate. That is, the one corresponding to the farthest polygon im is also selected as the principal axis candidate. As a result, as shown in FIG. 13B, the reference point coincides with the origin (0, 0, 0), and a plurality of spindle candidates are extracted. FIG. 13B shows an example in which two main spindle candidates 1 and 2 are extracted as main spindle candidates, and one of them shows the farthest polygon im having the longest distance. .

  Next, the spindle is selected and scaled (step S205). Specifically, first, if the restriction model and the target model have the same polygon configuration, or if they are not the same, it can be assumed that there is no significant change in the polygon arrangement order (reverse conversion to CAD data format and editing). In this case, a simple method can be adopted in which a main axis candidate corresponding to the polygon located at the head of the polygon array is selected as the main axis. Here, the principal axis candidate corresponding to the polygon located at the head does not necessarily match the principal axis candidate (whose length matches Lmax) extracted first when searching for the principal axis candidate. The main axis candidate is processed in association with the polygon number of the polygon because one of the end points is the average point of the polygon. The search for the spindle candidate and the spindle selection process are performed over two processes. In the first process, one polygon having the longest distance from the reference point is specified, and this longest distance is set to Lmax. The polygon specified at this stage is only one of the main axis candidates. At this time, when there are a plurality of polygons having the same longest distance Lmax, if the processing is performed in order from the smallest polygon number, the one with the smallest polygon number corresponds to the main polygon corresponding to the first polygon on the polygon array. It will be selected as a candidate. In the second process, all polygons whose length from the reference point satisfies Lmax-d or more are extracted as main axis candidates. From the plural (two or more) principal axis candidates extracted at this stage, the one having the smallest polygon number is selected as the principal axis. If there is only one main axis candidate extracted at this stage, that is, if no other polygons other than the polygon specified in the first process are found, the direction to the average point of the polygon is the main axis. It is determined. As long as it is within the predetermined range from the longest distance, it is the same regardless of the choice, so according to the rules set in advance, for example, the polygon with the second smallest polygon number, the one with the largest polygon number, etc. It is also possible to do. When the polygon T having the average point (Xc (T), Yc (T), Zc (T)) is selected as the main axis, the main axis length LT is obtained by executing the processing according to the following [Equation 8]. Is calculated.

[Formula 8]
LT = {(Xc (T)) ² + (Yc (T)) ² + (Zc (T)) ² } ^1/2

  Subsequently, scaling is performed. Specifically, by executing processing according to the following [Equation 9], the vertex coordinates and average point coordinates of each polygon are corrected so that the spindle length LT becomes the reference length.

[Formula 9]
Xk ′ (i) = Xk (i) × 100 / LT
Yk ′ (i) = Yk (i) × 100 / LT
Zk ′ (i) = Zk (i) × 100 / LT
Xc ′ (i) = {X0 ′ (i) + X1 ′ (i) + X2 ′ (i)} / 3
Yc ′ (i) = {Y0 ′ (i) + Y1 ′ (i) + Y2 ′ (i)} / 3
Zc ′ (i) = {Z0 ′ (i) + Z1 ′ (i) + Z2 ′ (i)} / 3

  [Equation 9] shows a case where the reference length is set to “100”. By the processing of step S205, the vertexes of each polygon i are (Xk ′ (i), Yk ′ (i), Zk ′ (i)), and the average points of each polygon i are (Xc ′ (i), Yc ′ ( i), Zc ′ (i)). Further, as shown in FIG. 13C, the target model is selected as the main shaft, and the length of the selected main shaft is changed to the reference length.

  Next, the Y-axis center rotation is performed so that the main axis is aligned in the positive Z-axis direction on the XZ coordinate (step S206). Specifically, first, an angle Ang between the main axis and the positive direction of the Z axis and an average point Z coordinate Zc ″ T of the main axis polygon T are obtained by executing processing according to the following [Equation 10]. The main-axis polygon is a polygon in which one end point of the main axis is an average point of the polygon.

[Formula 10]
Ang = −tan ⁻¹ (Xc ′ (T) / Zc ′ (T))
Zc ″ (T) = cos (Ang) × Zc ′ (T) −sin (Ang) × Xc ′ (T)

  Further, the target model after rotation is obtained by performing processing according to the following [Equation 11] depending on the value of Zc ″ (T).

[Formula 11]
i = 0,..., N−1, k = 0, 1, 2
1) When Zc ″ (T) ≧ 0 Zk ″ (i) = cos (Ang) × Zk ′ (i) −sin (Ang) × Xk ′ (i)
Xk ″ (i) = sin (Ang) × Zk ′ (i) + cos (Ang) × Xk ′ (i)
Zc ″ (T) = cos (Ang) × Zc ′ (T) −sin (Ang) × Xc ′ (T)
Xc ″ (T) = sin (Ang) × Zc ′ (T) + cos (Ang) × Xc ′ (T)
2) When Zc ″ (T) <0 Zk ″ (i) = − cos (Ang) × Zk ′ (i) + sin (Ang) × Xk ′ (i)
Xk ″ (i) = − sin (Ang) × Zk ′ (i) −cos (Ang) × Xk ′ (i)
Zc ″ (T) = − cos (Ang) × Zc ′ (T) + sin (Ang) × Xc ′ (T)
Xc ″ (T) = − sin (Ang) × Zc ′ (T) −cos (Ang) × Xc ′ (T)
The average score is updated regardless of the value of Zc ″ (T).
Xc ″ (i) = {X0 ″ (i) + X1 ″ (i) + X2 ″ (i)} / 3
Zc ″ (i) = {Z0 ″ (i) + Z1 ″ (i) + Z2 ″ (i)} / 3

  As a result of the processing in step S206, as shown in FIG. 13D, the target model is such that the main axis overlaps the positive Z-axis direction on the XZ plane.

  Next, X-axis center rotation is performed so that the main axis is aligned with the Z-axis positive direction on the YZ coordinates (step S207). Specifically, first, an angle Ang between the main axis and the positive direction of the Z axis and an average point Z coordinate Zc ′ ″ (m) of the main axis polygon are obtained by executing the processing according to the following [Equation 12]. .

[Formula 12]
Ang = −tan ⁻¹ (Yc ′ (T) / Zc ″ (T))
Zc ′ ″ (T) = cos (Ang) × Zc ″ (T) −sin (Ang) × Yc ′ (T)

  Further, the target model after rotation is obtained by performing processing according to the following [Equation 13] depending on the value of Zc ′ ″ (T).

[Formula 13]
i = 0,..., N−1, k = 0, 1, 2
1) When Zc ′ ″ (T) ≧ 0 Zk ′ ″ (i) = cos (Ang) × Zk ″ (i) −sin (Ang) × Yk ′ (i)
Yk ″ (i) = sin (Ang) × Zk ″ (i) + cos (Ang) × Yk ′ (i)
2) When Zc ′ ″ (T) <0 Zk ′ ″ (i) = − cos (Ang) × Zk ″ (i) + sin (Ang) × Yk ′ (i)
Yk ″ (i) = − sin (Ang) × Zk ″ (i) −cos (Ang) × Yk ′ (i)
The average score is updated regardless of the value of Zc ″ (T).
Yc ″ (i) = {Y0 ″ (i) + Y1 ″ (i) + Y2 ″ (i)} / 3
Zc ′ ″ (i) = {Z0 ′ ″ (i) + Z1 ′ ″ (i) + Z2 ′ ″ (i)} / 3

  As a result of the processing in step S207, as shown in FIG. 13E, the target model is such that the main axis overlaps the positive Z-axis direction on the YZ plane. Thereby, in the three-dimensional space, the main axis of the target model overlaps with the positive direction of the Z axis. In the present embodiment, the main axis is overlapped in the positive direction of the Z axis, but may be overlapped in the negative direction.

  Next, the secondary axis of the target model is obtained (step S208). Specifically, the distance from the origin (0, 0, 0) to the average point of each polygon is calculated on the XY plane, and the longest longest line segment is used as the secondary axis. Specifically, the sub-axis length Lmax2 is calculated by executing processing according to the following [Equation 14].

[Formula 14]
Lmax2 = Max _{i = 0, N−1} {(Xc ″ (i)) ² + (Yc (i) ″) ² } ^1/2
= {(Xc ″ (T2)) ² + (Yc (T2) ″) ² } ^1/2

  In the above [Equation 14], “T2” indicates the polygon number of the polygon having the maximum two-dimensional distance to the reference point (origin) on the XY plane. The minor axis is specified as a line segment connecting the reference point (origin) and the two-dimensional average point of the extracted polygon T2. Therefore, the minor axis is a line segment having a direction and a length. By the processing in step S208, the secondary axis of the target model is determined as shown in FIG.

  Next, Z-axis center rotation is performed so that the sub-axis is aligned with the Y-axis positive direction on the XY coordinates (step S209). Specifically, first, by executing processing according to the following [Formula 15], the angle Ang between the secondary axis and the positive direction of the Z axis, the average point Y coordinate Yc ′ ″ (T2) of the secondary axis polygon Ask for. The minor axis polygon is a polygon in which one end point of the minor axis is the average point of the polygons.

[Formula 15]
Ang = −tan ⁻¹ (Xc ″ (T2) / Yc ″ (T2))
Yc ′ ″ (T2) = cos (Ang) × Yc ″ (T2) −sin (Ang) × Xc ″ (T2)

  Further, the target model after rotation is obtained by performing a process according to the following [Equation 16] according to the value of Yc ′ ″ (T2).

[Formula 16]
i = 0,..., N−1, k = 0, 1, 2
1) When Yc ′ ″ (T2) ≧ 0 Yk ′ ″ (i) = cos (Ang) × Yk ″ (i) −sin (Ang) × Xk ″ (i)
Xk ′ ″ (i) = sin (Ang) × Yk ″ (i) + cos (Ang) × Xk ″ (i)
2) When Yc ′ ″ (T2) <0 Yk ′ ″ (i) = − cos (Ang) × Yk ″ (i) + sin (Ang) × Xk ″ (i)
Xk ′ ″ (i) = − sin (Ang) × Yk ″ (i) −cos (Ang) × Xk ″ (i)
The average score is updated regardless of the value of Yc ′ ″ (T2).
Xc ″ ′ (i) = {X0 ′ ″ (i) + X1 ′ ″ (i) + X2 ′ ″ (i)} / 3
Yc ′ ″ (i) = {Y0 ′ ″ (i) + Y1 ′ ″ (i) + Y2 ′ ″ (i)} / 3

  As a result of the processing in step S209, the target model is such that the secondary axis overlaps the positive Y-axis direction on the XY plane, as shown in FIG. In the present embodiment, the auxiliary shaft is overlapped in the positive direction of the Y axis, but may be overlapped in the negative direction.

  As a result of the above processing, a normalized target model is obtained. The normalized target model has a polygon number N and a variable i (i = 0,..., N−1) for specifying the polygon, and the vertex of each polygon i is (Xk ′ ″ (i), Yk ′). '' (I), Zk ′ '' (i)). k indicates a vertex number, and in this embodiment, since the polygon is a triangle, it takes three values, k = 0, 1, and 2. The average point of each polygon i is defined as (Xc ′ ″ (i), Yc ′ ″ (i), Zc ′ ″ (i)). As a result of the polygon normalization process, the target model is normalized to a predetermined position, scale, and inclination as shown in FIG.

<2.4.2. Polygon normalization processing (second method)>
Next, a second method of polygon normalization processing in step S200 will be described. In the first method described above, there is an application condition that it is possible to assume that the polygon arrangement order is not changed even if the restriction model and the target model have the same polygon configuration or not, and all cases where this assumption does not hold. The second method described below is applied. FIG. 15 is a flowchart showing a second method of polygon normalization processing in step S200. As in the case of the first method, the number N of polygons of the target model in which the number of polygons has been reduced in step S100 and the variable i (i = 0,..., N−1) for specifying the polygon are used. The vertices are defined as (Xk (i), Yk (i), Zk (i)). k indicates a vertex number, and in this embodiment, since the polygon is a triangle, it takes three values, k = 0, 1, and 2.

  First, a reference point in the target model in which the number of polygons is reduced in step S100 is calculated (step S211). Specifically, the average point (Xc (i), Yc (i) of each polygon is obtained by executing the processing according to the above [Equation 3] as in step S201 of the first method shown in FIG. , Zc (i)).

  Next, the polygon model reference point (Xg, Yg, Zg) is calculated by executing the processing according to the above [Equation 4] as in step S201 of the first method.

  16 to 18 are diagrams showing an outline of the second method of polygon normalization processing. In FIGS. 16 to 18, an object represented by a large cuboid and a small cuboid is an example of a target model. FIG. 16A shows a target model before normalization in an XYZ three-dimensional space.

  Next, the target model is moved (step S212). Specifically, as in step S202 of the first method shown in FIG. 12, the target model is moved by executing the process according to [Formula 5].

  After the movement, the average point (Xc (i), Yc (i), Zc (i)) of each polygon is recalculated by executing the processing according to the above [Equation 3].

  Next, the distance from the reference point (Xg, Yg, Zg) after moving to the origin to the average point of each polygon is calculated, and the longest distance among them is obtained (step S213). Specifically, the longest distance Lmax is calculated by executing the process according to the above [Equation 6] as in step S203 of the first method shown in FIG.

  Next, a plurality of spindle candidates are extracted (step S214). Specifically, as in step S204 of the first method shown in FIG. 12, all spindle candidates corresponding to polygons that satisfy the condition shown in [Formula 7] are extracted.

  As the main axis candidates, all those whose lengths of the line segment connecting the reference point and the average point of the extracted polygons satisfy the condition shown in [Formula 7] are extracted. Therefore, the principal axis candidate is a line segment having a direction and a length. The spindle candidate naturally includes the longest distance candidate. That is, the one corresponding to the farthest polygon im is also selected as the principal axis candidate. As a result, as shown in FIG. 16B, the reference point coincides with the origin (0, 0, 0), and a plurality of spindle candidates are extracted. FIG. 16B shows an example in which two main spindle candidates 1 and 2 are extracted as main spindle candidates, and one of them shows the farthest polygon im having the longest distance. .

  Next, scaling is performed for each spindle candidate (step S215). Specifically, the spindle candidate m is sequentially selected from the M spindle candidates (M = 2 in the example of FIG. 16) (m = 1,..., M). First, candidate spindle 1 (m = 1) is selected as shown in FIG. Assuming that the polygon corresponding to the main spindle candidate m is tm, the main spindle candidate length L (tm) is calculated for tm by executing the processing according to the following [Equation 17].

[Formula 17]
L (tm) = {(Xc (tm)) ² + (Yc (tm)) ² + (Zc (tm)) ² } ^1/2

  Subsequently, scaling is performed. Specifically, by executing processing according to the following [Equation 18], the vertex coordinates and average point coordinates of each polygon are corrected so that the principal axis candidate length L (tm) becomes the reference length.

[Formula 18]
Xk ′ (i) = Xk (i) × 100 / L (tm)
Yk ′ (i) = Yk (i) × 100 / L (tm)
Zk ′ (i) = Zk (i) × 100 / L (tm)
Xc ′ (i) = {X0 ′ (i) + X1 ′ (i) + X2 ′ (i)} / 3
Yc ′ (i) = {Y0 ′ (i) + Y1 ′ (i) + Y2 ′ (i)} / 3
Zc ′ (i) = {Z0 ′ (i) + Z1 ′ (i) + Z2 ′ (i)} / 3

  The above [Formula 18] shows a case where the reference length is “100”. Through the processing in step S215, the vertices of each polygon i are (Xk ′ (i), Yk ′ (i), Zk ′ (i)), and the average points of each polygon i are (Xc ′ (i), Yc ′ ( i), Zc ′ (i)). In the target model, as shown in FIG. 16C, the length of one principal axis candidate m is a reference length.

  Next, the Y-axis center rotation is performed so that the principal axis candidate m is aligned in the positive Z-axis direction on the XZ coordinate (step S216). Specifically, first, by executing the processing according to the following [Equation 19], the angle Ang between the principal axis candidate m and the positive Z-axis direction, the average point Z coordinate Zc ″ (tm) of the principal axis candidate polygon tm ) The spindle candidate polygon tm is a polygon in which one end point of the spindle candidate m is an average point of the polygons.

[Formula 19]
Ang = −tan ⁻¹ (Xc ′ (tm) / Zc ′ (tm))
Zc ″ (tm) = cos (Ang) × Zc ′ (tm) −sin (Ang) × Xc ′ (tm)

  Further, the target model after rotation is obtained by performing processing according to the following [Equation 20] according to the case according to the value of Zc ″ (tm).

[Formula 20]
i = 0,..., N−1, k = 0, 1, 2
1) When Zc ″ (tm) ≧ 0 Zk ″ (i) = cos (Ang) × Zk ′ (i) −sin (Ang) × Xk ′ (i)
Xk ″ (i) = sin (Ang) × Zk ′ (i) + cos (Ang) × Xk ′ (i)
Zc ″ (tm) = cos (Ang) × Zc ′ (tm) −sin (Ang) × Xc ′ (tm)
Xc ″ (tm) = sin (Ang) × Zc ′ (tm) + cos (Ang) × Xc ′ (tm)
2) When Zc ″ (tm) <0 Zk ″ (i) = − cos (Ang) × Zk ′ (i) + sin (Ang) × Xk ′ (i)
Xk ″ (i) = − sin (Ang) × Zk ′ (i) −cos (Ang) × Xk ′ (i)
Zc ″ (tm) = − cos (Ang) × Zc ′ (tm) + sin (Ang) × Xc ′ (tm)
Xc ″ (tm) = − sin (Ang) × Zc ′ (tm) −cos (Ang) × Xc ′ (tm)
The average score is updated regardless of the value of Zc ″ (tm).
Xc ″ (i) = {X0 ″ (i) + X1 ″ (i) + X2 ″ (i)} / 3
Zc ″ (i) = {Z0 ″ (i) + Z1 ″ (i) + Z2 ″ (i)} / 3

  As a result of the processing in step S216, in the target model, as shown in FIG. 16D, the main axis candidate m overlaps with the positive Z-axis direction on the XZ plane.

  Next, X-axis center rotation is performed so that the main axis candidate m is aligned in the Z-axis positive direction on the YZ coordinates (step S217). Specifically, first, by executing the processing according to the following [Formula 21], the angle Ang between the main axis and the positive direction of the Z axis, the average point Z coordinate Zc ′ ″ (tm) of the main axis candidate polygon tm Ask for.

[Formula 21]
Ang = −tan ⁻¹ (Yc ′ (tm) / Zc ″ (tm))
Zc ′ ″ (t) = cos (Ang) × Zc ″ (t) −sin (Ang) × Yc ′ (t)

  Further, the target model after rotation is obtained by performing processing according to the following [Equation 22] depending on the value of Zc ′ ″ (tm).

[Formula 22]
i = 0,..., N−1, k = 0, 1, 2
1) When Zc ′ ″ (tm) ≧ 0 Zk ′ ″ (i) = cos (Ang) × Zk ″ (i) −sin (Ang) × Yk ′ (i)
Yk ″ (i) = sin (Ang) × Zk ″ (i) + cos (Ang) × Yk ′ (i)
2) When Zc ′ ″ (tm) <0 Zk ′ ″ (i) = − cos (Ang) × Zk ″ (i) + sin (Ang) × Yk ′ (i)
Yk ″ (i) = − sin (Ang) × Zk ″ (i) −cos (Ang) × Yk ′ (i)
The average score is updated regardless of the value of Zc ″ (tm).
Yc ″ (i) = {Y0 ″ (i) + Y1 ″ (i) + Y2 ″ (i)} / 3
Zc ′ ″ (i) = {Z0 ′ ″ (i) + Z1 ′ ″ (i) + Z2 ′ ″ (i)} / 3

  As a result of the processing in step S217, as shown in FIG. 16E, in the target model, the main axis candidate m overlaps with the positive Z-axis direction on the YZ plane. Thereby, in the three-dimensional space, the principal axis candidate m of the target model overlaps with the positive direction of the Z axis. In the present embodiment, the principal axis candidate m is overlapped in the positive direction of the Z axis, but may be overlapped in the negative direction.

  Next, a sub-axis candidate m corresponding to the main-axis candidate m currently being processed is obtained (step S218). Specifically, the two-dimensional distance from the origin (0, 0, 0) to the average point of each polygon is calculated on the XZ plane, and the direction of the average point of the polygon tm2 having the longest longest distance Lmax3 among them is calculated. Is a sub-axis candidate m. Specifically, by executing the processing according to the following [Equation 23], the length Lmax3 (longest distance) of the sub-axis candidate m is calculated using tm2 as the polygon corresponding to the sub-axis candidate m.

[Formula 23]
Lmax3 = Max _{i = 0, N−1} {(Xc ″ (i)) ² + (Yc ″ (i)) ² } ^1/2
= {(Xc ″ (tm2)) ² + (Yc ″ (tm2)) ² } ^1/2

  By the process of step S218, the sub-axis candidate m is determined for the target model as shown in FIG. Subsequently, the process returns to step S215, and the next main spindle candidate main spindle candidate 2 (m = 2) is selected. The process returns to the target model in the initial state shown in FIG. Scaling is performed in the same way. The result is shown in FIG. Similarly, the process proceeds to step S216, and as shown in FIG. 17H, the principal axis candidate 2 is overlapped with the positive direction of the Z axis in the XZ plane. Then, the process proceeds to step S217, and as shown in FIG. 17 (i), the main axis candidate 2 overlaps the Z axis positive direction on the YZ plane, and the main axis candidate 2 of the target model overlaps the Z axis positive direction in the three-dimensional space. Like that. Further, the process proceeds to step S218, and a sub-axis candidate 2 corresponding to the main axis candidate 2 is obtained as shown in FIG. In the model examples shown in FIGS. 16 and 17, it is only necessary to select a set of two types of main axis candidates and sub axis candidates, but in general, M main axis candidates m (m) extracted in step S214. = 1,..., M), it is necessary to repeatedly execute steps S215 to S218 to obtain sub-axis candidates m corresponding to the respective main-axis candidates m.

  Next, a sub-axis is determined from the plurality of sub-axis candidates obtained (step S219). Specifically, for each sub-axis candidate m (m = 1,..., M), a three-dimensional distance L (m) is calculated on the XYZ coordinates, and the sub-axis having the maximum distance L (m) is calculated. The axis candidate m is determined as the secondary axis. However, when the difference from the second largest distance L (ms) is less than the predetermined value dd, the distance L (m) is ML (m) when the maximum L (m) is ML (m). Extract all sub-axis candidates m that are equal to or greater than -dd, and for each extracted sub-axis candidate m, the inner product S (m) = (main-axis candidate m vector, sub-axis) with the main-axis candidate m corresponding to the sub-axis candidate m (Candidate m vector) is calculated, and the sub-axis candidate m having the maximum value is determined as the sub-axis in consideration of the sign of the inner product S (m), and the corresponding main-axis candidate m is determined as the main axis. That is, the main axis candidate is long, the sub axis candidate is long, and the sub axis candidate m whose angle between the main axis candidate and the sub axis candidate is close to 0 is easily determined as the sub axis. Here, the predetermined value dd can be set in a range of ML (m) × 0.00001 to ML (m) × 0.001, where ML (m) is the maximum L (m). In this embodiment, dd = ML (m) × 0.0001 is set. The distance L (m) and the inner product S (m) are calculated by executing processing according to the following [Equation 24].

[Formula 24]
L (m) = {(Xc (tm2)) ² + (Yc (tm2)) ² + (Zc (tm2)) ² } ^1/2
S (m) = Xc (tm) × Xc (tm2) + Yc (tm) × Yc (tm2) + Zc (tm) × Zc (tm2)

  Since the minor axis is selected from M minor axis candidates m, the minor axis is specified as a line segment connecting the reference point (origin) and the two-dimensional average point of the extracted polygon. It becomes a line segment with length. Through the processing in step S219, the target model is determined such that the sub-axis candidate 1 extracted in FIG. 16 (f) is the sub-axis in the example shown in FIG. 17 (k).

  When the sub-axis is determined, the main axis candidate m from which the sub-axis candidate m (m = 1 in the example of FIG. 17) is extracted is selected as the main axis. Since the main axis is selected from the main axis candidates, it is specified as a line segment connecting the reference point and the average point of the extracted polygons, and is a line segment having a direction and a length.

  When the main axis and the sub axis are determined, the process returns to step S215, returns to the target model in the initial state shown in FIG. 16B, and similarly from step S215 to step S219 based on the determined main axis (main axis candidate 1). Although the processing will be performed again, these series of processing based on the spindle candidate 1 have already been executed as shown in FIG. 16C to FIG. 16F, so that these processing histories are stored. If so, it is possible to proceed to the next step S220 using the result. Specifically, after returning from the state of FIG. 17 (k) to the state of FIG. 16 (f), the process proceeds to step S220, and the Z-axis rotation is performed so that the sub-axis is aligned in the Y-axis positive direction on the XY coordinates. This is performed (step S220). Specifically, as in the first method, first, the polygon T2 is replaced with tm2 in [Formula 15], and then the process according to [Formula 15] is executed, so An angle Ang with the direction and an average point Y coordinate Yc ′ ″ (tm2) of the farthest polygon are obtained.

  Further, the case is classified according to the value of Yc ′ ″ (tm2). Similarly to the first method, the polygon T2 is replaced with tm2 in the above [Expression 16], and then the process according to [Expression 16] is performed. By executing, the target model after rotation is obtained.

  As a result of the processing in step S220, as shown in FIG. 17L, the target model is such that the minor axis overlaps with the positive Y-axis direction on the XY plane. In the present embodiment, the auxiliary shaft is overlapped in the positive direction of the Y axis, but may be overlapped in the negative direction.

  As a result of the above process, a target model normalized based on the main axis and the sub axis uniquely determined for each given target model is obtained. The normalized target model has a polygon number N and a variable i (i = 0,..., N−1) for specifying the polygon, and the vertex of each polygon i is (Xk ′ ″ (i), Yk ′). '' (I), Zk ′ '' (i)). k indicates a vertex number, and in this embodiment, since the polygon is a triangle, it takes three values, k = 0, 1, and 2. The average point of each polygon i is defined as (Xc ′ ″ (i), Yc ′ ″ (i), Zc ′ ″ (i)). As a result of the polygon normalization process, the target model is normalized to a predetermined position, scale, and inclination as shown in FIG.

<2.5. Polygon matching process>
Next, the polygon matching process in step S300 will be described. FIG. 19 is a flowchart showing an outline of the polygon matching process. In the polygon matching process, the polygon model matching unit 30 extracts the regulation models registered in the regulation model database 50 one by one (step S301), and performs matching with the target model normalized in step S200. In the present embodiment, as shown in FIG. 19, the polygon model matching unit 30 performs a matching process based on the total area (step S310), a matching process based on the volume (step S320), and a matching process based on the coordinate values (step S330). The three matching processes are performed in order. Only when it is determined that the result is the matching (ie, similar) as a result of the matching process performed earlier, the process proceeds to the next matching process. When it is determined as non-conforming (that is, dissimilar), the process returns to step S301 and collation with the next restriction model is performed. Of the three matching processes, the matching process based on the total area and the matching process based on the volume are angle-independent matching processes that do not depend on the angle, and the matching process based on the coordinate values is an angle-dependent matching process that depends on the angle. is there. If it is determined that all three matching processes are suitable (that is, similar), the target model is similar to the restriction model, and therefore, it is determined that the output is inappropriate. If the comparison with all the restriction models registered in the restriction model database 50 is incompatible, the target model is dissimilar to any restriction model, and therefore it is determined that the output is appropriate.

<2.5.1. Polygon matching based on total area>
First, among the three matching processes shown in FIG. 19, the polygon matching process based on the total area in step S310 will be described. FIG. 20 is a flowchart showing details of the polygon matching process based on the total area. In step S200, the normalized target model is indicated by (Xk ′ ″ (i), Yk ′ ″ (i), Zk ′ ″ (i)), but avoids complicated expressions. Therefore, in step S300, the normalized target model is set to the polygon number N, the variable i (i = 0,..., N−1) for specifying the polygon, and the vertex of each polygon i is set to (Xk). (I), Yk (i), Zk (i)). k is a vertex number having three values of k = 0, 1, and 2.

  The polygon model matching means 30 first calculates the area Sp (i) of each polygon i constituting the normalized target model and the total area SN which is the sum of the areas Sp (i) of N polygons as follows: 25] is executed by executing the processing according to (25).

[Formula 25]
Vx = [Y1 (i) -Y0 (i)] * [Z2 (i) -Z0 (i)]-[Z1 (i) -Z0 (i)] * [Y2 (i) -Y0 (i)]
Vy = [Z1 (i) -Z0 (i)] * [X2 (i) -X0 (i)]-[X1 (i) -X0 (i)] * [Z2 (i) -Z0 (i)]
Vz = [X1 (i) -X0 (i)] * [Y2 (i) -Y0 (i)]-[Y1 (i) -Y0 (i)] * [X2 (i) -X0 (i)]
Sp (i) = 0.5 × [Vx (i) ² + Vy (i) ² + Vz (i) ² ] ^1/2
SN = Σ _{i = 0, N-1} Sp (i)

  Next, the polygon model matching means 30 executes the process according to the above [Equation 25] on the restriction model composed of H polygons by changing the variable, similarly to the process in step S311. The total area SH of the regulation model is calculated. (Step S312).

  Subsequently, the polygon model matching means 30 calculates the area difference dS between the total area SN of the normalized target model and the total area SH of the restriction model by executing processing according to the following [Equation 26]. (Step S313).

[Formula 26]
dS = | SH-SN | / (SH + SN)

  In the above [Equation 26], normalization is performed by dividing by the sum of the total areas (SH + SN) for later comparison with the determination threshold. As shown in the above [Equation 26], the area difference dS is an absolute value of the difference of the total area.

  When the area difference dS is obtained, the polygon model matching unit 30 compares the area difference dS with the determination threshold value (step S314). When the area difference dS is smaller than the determination threshold value, it is determined as conforming, and when the area difference dS is equal to or larger than the determination threshold value, it is determined as nonconforming. The determination threshold can be set as appropriate, but here it is set to 0.01.

<2.5.2. Verification based on volume>
Next, the polygon matching process based on the volume in step S320 will be described. FIG. 21 is a flowchart showing details of a polygon matching process based on volume. In step S300, the normalized target model is set to the number of polygons N, the variable i for specifying the polygons (i = 0,..., N−1), and the vertices of each polygon i are set to (Xk (i), Yk (i), Zk (i)) and the average point of each polygon i is defined as (Xc (i), Yc (i), Zc (i)).

  The polygon model matching means 30 calculates, for each polygon, a pyramid volume V (i) with each polygon as a bottom surface and a reference point (centroid) as a vertex, and the sum of the volumes V (i) for N polygons. VN is calculated (step S321). Specifically, first, processing according to the above [Equation 25] is executed to calculate the area Sp (i) of each polygon i. Then, the normal vector (Nx (i), Ny (i), Nz (i)) of each polygon is calculated by executing processing according to the following [Equation 27].

[Formula 27]
Vs (i) = [Vx (i) ² + Vy (i) ² + Vz (i) ² ] ^1/2
Nx (i) = Vx (i) / Vs (i)
Ny (i) = Vy (i) / Vs (i)
Nz (i) = Vz (i) / Vs (i)

  The height of the pyramid can be calculated by the absolute value of the inner product of the vector in the origin direction from the average point and the normal vector of the polygon. Therefore, by executing the processing according to [Equation 28] below, the polygon i is A pyramid volume V (i) and a pyramid volume sum VN for N polygons are calculated.

[Formula 28]
V (i) = Sp (i) | Xc (i) * Nx (i) + Yc (i) * Ny (i) + Zc (i) * Nz (i) | / 3
VN = Σ _{i = 0, N-1} V (i)

  Next, the polygon model collating means 30 changes the processing according to the above [Equation 27] and [Equation 28] to a restriction model composed of H polygons by changing the variables, similarly to the processing in step S321. This is executed for the volume sum VH of the regulation model. (Step S322).

  Subsequently, the polygon model matching means 30 calculates a volume difference dV between the normalized volume sum VN of the polygon model and the volume sum VH of the restriction model by executing a process according to the following [Equation 29]. (Step S323).

[Formula 29]
dV = | VH−VN | / (VH + VN)

  In the above [Equation 29], normalization is performed by dividing by the sum of volume sums (VH + VN) for later comparison with the determination threshold. As shown in the above [Equation 29], the volume difference dV is an absolute value of the difference of the volume sum.

  When the volume difference dV is obtained, the polygon model matching unit 30 compares the volume difference dV with the determination threshold value (step S324). When the volume difference dV is smaller than the determination threshold value, it is determined as conforming, and when the volume difference dV is equal to or larger than the determination threshold value, it is determined as non-conforming. The determination threshold can be set as appropriate, but here it is 0.001.

<2.5.3. Collation processing based on coordinate values>
Next, polygon matching processing based on the coordinate values in step S330 will be described. FIG. 22 is a flowchart showing details of polygon matching processing based on coordinate values. Here, the average point of each polygon i of the target model is defined as (Xcn (i), Ycn (i), Zcn (i)) (i: polygon number = 0,..., N−1), The average point of each polygon j of the restriction model is defined as (Xch (j), Ych (j), Zch (j)) (j: polygon number = 0,..., H−1).

  First, the polygon model matching unit 30 performs initial setting to set D = 0 and i = 0 (step S331). D is a variable that is output as the total distance when compared with the determination threshold. i = 0 is the polygon number of the polygon processed first in the target model. Next, j = 0 and dmin = BIG are set (step S332). j = 0 is the polygon number of the polygon processed first in the restriction model. dmin is set to the initial value BIG. BIG is set to a large value that cannot be taken as dmin.

  Next, the average point coordinate distance dK between the polygons specified in both models is calculated (step S333). Specifically, it is calculated by executing processing according to the following [Equation 30].

[Formula 30]
dK = [(Xch (j) −Xcn (i)) ² + (Ych (j) −Ycn (i)) ² + (Zch (j) −Zcn (i)) ² ] ^1/2

  As shown in the above [Equation 30], the average point coordinate distance dK is the square root of the difference between the average point coordinates, and indicates the distance between the average point coordinates. Next, the calculated average point coordinate distance dK and dmin are compared (step S334). If dK is smaller than dmin, dmin = dK is set (step S335). Then, j is incremented by 1 to change the processing target polygon of the restriction model (step S336), and the polygon number j and the polygon number H of the restriction model are compared (step S337).

  As a result of comparison, if j is smaller than H, the processing of all the polygons of the restriction model for one polygon of the target model has not been completed, so the process returns to step S333 to calculate the average point coordinate distance. Since j = H after executing the processing of step S333 to step S336 for all polygons of the restriction model for one polygon of the target model, the process proceeds to step S338.

  By repeating the processing of steps S333 to S336, the minimum distance value that is the minimum value among the distances between one polygon of the target model and each polygon of the restriction model is recorded in dmin. This is the distance between one polygon of the target model and the polygon of the nearest restriction model. Next, this distance minimum value dmin is added to D (step S338). Then, i is incremented by 1 to change the processing target polygon of the target model, and the polygon number i and the polygon number N of the target model are compared (step S339).

  If i is smaller than N as a result of the comparison, the processing has not been completed for all polygons of the target model, so the process returns to step S332 to perform processing for the next polygon of the target model. After all the polygons of the target model have been processed in steps S332 to S338, i = N, so the process proceeds to step S340.

  By repeating the processing of steps S332 to S338, the total of the minimum distance values dmin for each polygon of the target model is recorded in D.

  When the distance sum D is obtained, the polygon model collating means 30 compares a value D / N obtained by dividing the distance sum D by the number N of polygons of the target model with a determination threshold value (step S340). D / N is the average distance per polygon of the distance sum D, which is the sum of the distances. When D / N is smaller than the determination threshold, it is determined as conforming, and when D / N is equal to or greater than the determination threshold, it is determined as non-conforming. The determination threshold can be set as appropriate, but is 10.0 here.

  In this embodiment, the distance between the average point coordinates of the polygons and the total sum thereof are calculated. However, instead of the average point, the distance between the corresponding vertices of the polygons and the total sum thereof are calculated. Also good.

<Data output to 3.3D printer>
When the polygon model matching means 30 determines that the output is appropriate, the target polygon model is output to the 3D printer 7 which is a three-dimensional object shaping apparatus. On the other hand, if the polygon model matching means 30 determines that the output is inappropriate, the target model is not output to the 3D printer that is a three-dimensional object forming apparatus. If it takes time to determine whether or not the output is appropriate, the 3D printer 7 starts outputting the target model, and whether or not the output is appropriate in parallel with the output process (three-dimensional object modeling process) of the 3D printer 7. If it is determined that the output is inappropriate, an output stop command may be output to the 3D printer 7. At this time, from the viewpoint of the operator, it is only possible to confirm that the three-dimensional object shaping process in the 3D printer is started by issuing a single command to output the target model, and in parallel to determine whether the output is appropriate or not. It is not noticed that the execution of the process is started.

<4. About normalization and registration of regulatory models>
In the above embodiment, a case has been described in which a regulation model that has already been normalized is registered in the regulation model database 50. However, a regulation model that has not been normalized is registered in the regulation model database 50, and the regulation model is registered in this regulation model. On the other hand, polygon reduction and normalization are performed as in the above-described embodiment, and matching is performed using the normalized regulation model and the normalized target model. Good. In this case, each regulation model that is not normalized and registered in the regulation model database 50 has polygons reduced by the polygon reduction means 10 and normalized by the polygon normalization means 20 and then is normalized by the polygon model matching means 30. The collation with the target model after normalization is performed.

  Further, as a modification, the three-dimensional object modeling data output restriction device provided with the polygon model matching means 30 is different from the three-dimensional object shaping data obtained by normalizing the restriction model at a different location. You may make it transmit and register to an output control apparatus via a network.

  FIG. 23 is a hardware configuration diagram of a three-dimensional object formation system including a three-dimensional object formation data output restriction device according to a modification. In the three-dimensional object formation system shown in FIG. 23, the three-dimensional object formation data output restriction device 101 communicates with the public network such as the Internet in the configuration of the three-dimensional object formation data output restriction device 100 shown in FIG. 1. The network communication unit 8 is provided. The regulation model normalization apparatus 102 can be realized by a general-purpose computer. As shown in FIG. 23, a CPU (Central Processing Unit) 1a, a RAM (Random Access Memory) 2a that is a main memory of the computer, and a CPU 1a A large-capacity storage device 3a such as a hard disk or flash memory for storing programs and data executed by the computer, a key input I / F (interface) 4a such as a keyboard and a mouse, and an external device such as a data storage medium and data A data input / output I / F (interface) 5a for communication, a display unit 6a, which is a display device such as a liquid crystal display, and a network communication unit 8a for communicating with a public network such as the Internet, are connected via a bus. Connected. The network communication unit 8 of the three-dimensional object formation data output restriction device 101 and the network communication unit 8a of the restriction model normalization device 102 communicate with each other, and the restriction model normalization device 102 transfers the data to the three-dimensional object formation data output restriction device 101. It is possible to send a regulated model.

  In FIG. 23, the three-dimensional object formation data output restriction device 101 and the 3D printer 7 are shown in a separated form, but most of the 3D printer products currently on the market include the three-dimensional object formation data output restriction device 101. Constituent elements, such as CPU1, RAM2, storage device 3, key input I / F4 (not a keyboard / mouse for general-purpose computers, but several buttons at a numeric keypad level), data input / output I / F5, display unit 6 (several lines) A small liquid crystal panel capable of displaying the above characters, a touch panel is often superimposed to serve also as a key input I / F 4), and a network communication unit 8 (wireless LAN function) is provided in a small but overlapping manner. Therefore, the 3D printer 7 itself can directly receive the data for modeling a three-dimensional object via an external storage medium or the Internet, and can be operated to model a three-dimensional object alone (particularly in the case of a consumer 3D printer, this form Many). That is, the three-dimensional object formation data output restriction device 101 and the 3D printer 7 shown in FIG. 23 are often housed in one housing and distributed as a product called “3D printer”.

  In the restriction model normalization apparatus 102, the CPU 1a executes the program stored in the storage device 3a, thereby realizing the second polygon reduction means, the second polygon normalization means, and the restriction model transmission means. . The second polygon reduction means and the second polygon normalization means realized by the restriction model normalization device 102 are the polygon reduction means 10 and the polygon normalization means 20 realized by the three-dimensional object formation data output restriction device 100. It has the same function, reduces the restriction model polygon, and normalizes the restriction model. The restriction model transmission means transmits the normalized restriction model to the three-dimensional object formation data output restriction device 101. In the three-dimensional object formation data output restriction device 101, when the network communication unit 8 receives the restriction model from the restriction model normalization apparatus 102, the CPU 1 executes a predetermined program to function as a restriction model registration unit, and the received restriction is received. The model is registered in the regulation model database 50 realized by the storage device 3.

<5. Cloud-type 3D object modeling system>
The present invention can also be applied to a cloud-type three-dimensional object modeling system. FIG. 24 is a hardware configuration diagram of a cloud-type three-dimensional object modeling system. In the three-dimensional object formation system shown in FIG. 24, the output control PC 201 has the same hardware configuration as the computer shown as the three-dimensional object formation data output restriction device 101 in FIG. That is, the output control PC 201 includes a CPU 11, a RAM 12, a storage device 13, a key input I / F 14, a data input / output I / F 15, a display unit 16, and a network communication unit 18, which are connected to each other via a bus.

  The processing server 202 has a function as a three-dimensional object modeling data output restriction device according to the present invention, and can be realized by incorporating a dedicated program into a general-purpose computer. As shown in FIG. 24, a CPU 11a, a RAM 12a, a storage device 13a, a key input I / F 14a, a data input / output I / F 15a, a display unit 16a, and a network communication unit 18a are connected to each other via a bus. Yes. The network communication unit 18 of the output control PC 201 and the network communication unit 18a of the processing server 202 communicate with each other and can transmit output suitability data from the processing server 202 to the output control PC 201 based on the judgment of output suitability. It has become. In FIG. 24, the output control PC 201 and the 3D printer 7 are shown in a separated form. However, as in the example of FIG. 23, the CPU 11, RAM 12, and storage device that are components of the output control PC 201 in the 3D printer product. 13, a key input I / F 14, a data input / output I / F 15, a display unit 16, and a network communication unit 18 may be provided.

  FIG. 25 is a functional block diagram of a cloud-type three-dimensional object modeling system. The processing server 202 constituting the cloud-type three-dimensional object modeling system includes a target model receiving unit 60 and an output suitability data transmitting unit 70 in addition to each unit of the three-dimensional object modeling data output restriction device shown in FIG. It has a configuration. Components having the same functions as those of the three-dimensional object formation data output restriction device shown in FIG. The target model receiving unit 60 is a unit that receives the target model transmitted from the output control PC 201 and registers it in the target model storage unit 40. The CPU 11a executes a predetermined program and controls the network communication unit 18a. Is realized. The output suitability data transmitting means 70 is means for sending data based on the output suitability determined by the polygon model matching means 30 to the output control PC 201, and the CPU 11a executes a predetermined program and controls the network communication section 18a. It is realized by doing.

  The processing server 202 is connected to a network such as the Internet and can be accessed from a number of output control PCs. The “cloud type” of the cloud-type three-dimensional object modeling system is to determine whether or not to regulate on the remote computer via the network from the output side, not the output side that outputs the three-dimensional object by the 3D printer. Means. In conventional server-type computers, when many users' access concentrates, responsiveness slows down and often inconveniences users. However, in cloud-type computers, the physical configuration of computers can be changed dynamically using virtualization technology. Since it becomes possible, there is a feature that a stable response can always be maintained. Generally, the processing server 202 is physically realized by a plurality of computers.

  The processing operation of the cloud-type three-dimensional object modeling system shown in FIGS. 24 and 25 will be described. In the output control PC 201, when the user specifies a target model to be output via the key input I / F 14, the CPU 11 extracts the specified target model stored in the storage device 13 and specifies the target model. A model ID, which is identification information, is assigned. Then, the CPU 11 transmits the target model to which the model ID is assigned to an address such as a URL set in advance in the storage device 13 via the network communication unit 18. In parallel, the CPU 11 transmits the target model to which the model ID is assigned to the data processing unit 7a of the 3D printer 7 via the data input / output I / F 15. The target model received from the output control PC 201 is held in the printer queue in the data processing unit 7a, and is in a standby state as an output job. At this time, it is possible to execute only the process of converting the polygon format data, which is the pre-processing in the 3D printer output, into the data in the stack format, and to enter the standby state when the data is converted into the stack format data. . Since this data processing load is also reasonably high, if the output propriety determination is completed during this time, it is possible to prevent the user from feeling an extra waiting time.

  In the processing server 202, when the target model receiving unit 60 receives the target model transmitted from the output control PC 201, the target model is stored in the target model storage unit 40. From here, according to the flowchart shown in FIG. 3, the polygon reduction means 10, the polygon normalization means 20, and the polygon model collation means 30 perform processing to determine whether the received target model is suitable for output. Output propriety data, which is a result of output propriety, is transferred from the polygon model matching unit 30 to the output propriety data transmitting unit 70. Then, the output suitability data transmitting means 70 transmits the output suitability data with the model ID added to the output control PC 201 which is the transmission source (access source) of the target model.

  In the output control PC 201, when the network communication unit 18 receives the output suitability data from the processing server 202, the CPU 11 sends the received output suitability data to the data processing unit 7 a of the 3D printer 7 via the data input / output I / F 15. Send to. The data processing unit 7a refers to the output job in the printer queue by using the model ID given to the received output suitability data. When the output suitability data is “suitable”, the data processing unit 7a changes the output job from the standby state to the output state, and outputs the target model to the output unit 7b. If the output suitability data is “NO”, the data processing unit 7a discards the output job. That is, it is deleted from the printer queue.

<6. Polygon model normalization example>
26 to 28 show comparative examples of polygon normalization processing according to the prior art and the present invention. In any of FIGS. 26 to 28, the restriction model is shown on the left side and the target model is shown on the right side. FIG. 26 is a diagram showing an original polygon model before normalization (actually after polygon reduction). In FIG. 26, the restriction model and the target model are the same model, but the coordinate system is aligned with respect to the paper surface. However, since they are before normalization, they are different in position, scale, and inclination. When the longest distance is simply used as the main axis, two main axis candidates 1 and main axis candidate 2 exist in the example of FIG.

  FIG. 27 is a diagram illustrating a state in which normalization is performed on the restriction model and the target model in FIG. 26 by the conventional method. Even in the case where there are two main axis candidates, in the conventional method, a main axis candidate corresponding to the farthest polygon is selected as the main axis, and therefore, different main axes may be selected due to an error in calculation processing. In the example of FIG. 27, the candidate spindle 1 is selected as the spindle in the restriction model, and the candidate spindle 2 is selected as the spindle in the target model. For this reason, the position and inclination of both models are not aligned. Therefore, even if the matching process is performed as it is, it is determined as non-conforming.

  FIG. 28 is a diagram illustrating a state in which the regulation model and the target model in FIG. 26 are normalized by the first method of the present embodiment. Even in the case where there are two main axis candidates, the first method of the present embodiment is likely to be selected other than the main axis corresponding to the farthest polygon, so that it is affected by the error of the arithmetic processing. Therefore, the possibility that the same main axis is selected increases. In the example of FIG. 28, the candidate spindle 1 is selected as the spindle in the restriction model, and the candidate spindle 1 is also selected as the spindle in the target model. For this reason, the position and inclination of both models are aligned. Therefore, it is determined to be compatible when the matching process is performed.

<7. Modified example>
The preferred embodiments of the present invention have been described above. However, the present invention is not limited to the above embodiments, and various modifications can be made. For example, in the above embodiment, the processing target polygon is a triangle, but it may be a quadrilateral or more.

  In the above-described embodiment, the polygon model matching unit 30 performs the three matching processes of the matching process based on the total area, the matching process based on the volume, and the matching process based on the coordinate values. Of these, one or two matching processes may be executed.

  In the above embodiment, the polygon normalizing means 20 is configured to rotate the main axis to the Z axis and the sub axis to the Y axis. However, if the main axis and the sub axis are respectively adjusted to different axes, The main axis may be aligned with the X axis or Y axis, and the secondary axis may be aligned with the X axis or Z axis.

1, 1a, 11, 11a... CPU (Central Processing Unit)
2, 2a, 12, 12a ... RAM (Random Access Memory)
3, 3a, 13, 13a ... Storage device 4, 4a, 14, 14a ... Key input I / F
5, 5a, 15, 15a ... Data I / O I / F
6, 6a, 16, 16a ... display unit 7 ... 3D printer (three-dimensional object modeling apparatus)
7a ... Data processing unit 7b ... Output unit 8, 8a, 18, 18a ... Network communication unit 10 ... Polygon reduction means 20 ... Polygon normalization means 30 ... Polygon model matching means 40 ... Target model storage means 50 ... Restriction model database 60 ... Target model reception means 70 ... Output propriety data transmission means 100, 101 ... Data output restriction device for three-dimensional object formation 102 ... Restriction Model normalizer 201 ... PC for output control
202... Processing server (three-dimensional object shaping data output restriction device)

Claims (16)

A device for determining whether or not to regulate when outputting a polygon model expressed as a set of polygons to a three-dimensional object modeling apparatus as three-dimensional object modeling data,
A regulation model database in which a regulation model, which is a polygon model whose output should be regulated, is registered;
Polygon reduction means for reducing polygons so that the number of polygons included in the target model which is a polygon model to be output is a predetermined value or less;
The target model is moved so that the reference point of the target model is the origin of the three-dimensional coordinates with respect to the target model from which the polygons are reduced, and a predetermined minute distance from the longest distance to the polygon farthest from the reference point. A plurality of polygons included in a range reduced by an amount are extracted as main axis candidates in the direction viewed from the reference point, and one main axis candidate that satisfies a predetermined condition is selected and selected from the extracted main axis candidates. Create a normalized target model by scaling the target model so that the main axis has a predetermined length, and rotating the target model so that the direction of the main axis matches the first axis Polygon normalization means to
A polygon model collating means for collating the normalized target model with a regulation model registered in the regulation model database and determining whether or not to regulate the output;
A data output restriction device for three-dimensional object modeling, comprising:   The reference point of the target model is a polygon average coordinate that is an average of vertex coordinates of each polygon, and is given as an average value calculated for polygons included in the target model. 3D object shaping data output regulation device.   The polygon normalization means sets a candidate for a spindle corresponding to the first polygon on the polygon array in which polygons are arranged in a predetermined order in the target model as one spindle candidate that satisfies the predetermined condition. The three-dimensional object formation data output restriction device according to claim 1 or 2, wherein the three-dimensional object formation data output restriction device is configured as described above.   The polygon normalization means adjusts the scale of the target model so that the principal axis candidate has a predetermined length for each of the extracted plurality of principal axis candidates, and the direction of the principal axis candidate is the first axis. After rotating the target model so as to coincide with the target model, the rotated target model is a polygon farthest from the reference point projected on the two-dimensional coordinate system formed by the second axis and the third axis. Is selected for each main spindle candidate as a sub-axis candidate, and the sub-axis candidate has the longest three-dimensional distance from the reference point or the inner product value with the corresponding main axis candidate. The three-dimensional object modeling according to claim 1 or 2, wherein a principal axis candidate corresponding to the sub-axis candidate is set as one principal axis candidate that satisfies the predetermined condition. Data output rules Apparatus.   The polygon normalization means is formed of the first axis and the second axis in order to match the direction of the selected main axis with one of the positive and negative specific directions of the first axis. 2 formed by the first axis and the third axis after rotating the target model so that the direction of the principal axis projected onto the dimensional coordinate system matches the specific direction of the first axis. 5. The object model according to claim 1, wherein the target model is rotated so that a direction of the principal axis projected onto a dimensional coordinate system coincides with the specific direction of the first axis. The three-dimensional object modeling data output restriction device according to claim 1.   The polygon normalizing means rotates the target model so that the direction of the selected principal axis coincides with the specific direction of the first axis, and then uses the second axis and the third axis. The target model is further rotated so that the longest distance direction from the reference point projected on the formed two-dimensional coordinate system to the farthest polygon coincides with the specific direction of the third axis. The three-dimensional object formation data output restriction device according to claim 5,   The polygon collating means is composed of two types of processes for performing an angle-independent collation process that does not depend on an angle and an angle-dependent collation process that depends on an angle. The collation processing is executed, and the three-dimensional object formation data output restriction device according to any one of claims 1 to 6.   The polygon matching means calculates, as the angle-independent matching process, a total area value of polygons constituting the target model and a total area value of polygons constituting the restriction model, and a difference between the two total values 8. The three-dimensional object formation data output restriction device according to claim 7, wherein the conformity determination is performed when the absolute value of the three-dimensional object is smaller than a predetermined threshold value.   The polygon collating means, as the angle-independent collating process, uses a total value of pyramid volumes having the polygon constituting the target model as a bottom surface and the reference point as a vertex, and a polygon constituting the restriction model as a bottom surface. 8. The sum of volume values of a pyramid having a reference point as an apex is calculated, and conformity determination is performed when the absolute value of the difference between the two sum values is smaller than a predetermined threshold value. The data output regulation device for three-dimensional object modeling described in 1. The polygon matching means calculates, as the angle-independent matching process, a total area value of polygons constituting the target model and a total area value of polygons constituting the restriction model, and a difference between the two total values If the absolute value of is less than a predetermined threshold,
Only when the conformity is judged
Calculates the sum of the pyramid volume with the polygon constituting the target model as the base and the reference point as the apex, and the sum of the pyramid volumes with the reference point as the apex and the polygon constituting the restriction model as the base 8. The three-dimensional object formation data output restriction device according to claim 7, wherein the conformity determination is performed when the absolute value of the difference between the two total values is smaller than a predetermined threshold value.   The polygon matching means calculates the distance between the polygon average coordinates of the polygons closest to the average vertex coordinates of the polygons constituting each of the target model and the restriction model as the angle-dependent matching process. 8. A sum total value of distances between polygon average coordinates is calculated, and the conformity determination is performed when the average value per polygon of the sum total value is smaller than a predetermined threshold value. The data output regulation apparatus for three-dimensional object shaping | molding as described in any one of Claim 10.   The polygon matching means, as the angle-dependent matching process, calculates the distance between corresponding vertices between polygons having the closest polygon average coordinates, which is the average of the vertex coordinates of the polygons constituting each of the target model and the restriction model. The total value of all the polygons at the distance is calculated, and when the average value per polygon of the total value is smaller than a predetermined threshold value, the conformity determination is performed. The data output restriction device for three-dimensional object modeling according to any one of claims 7 to 10. A second polygon reduction means for reducing polygons so that the number of polygons included in the restriction model is a predetermined value or less;
The restriction model is moved with respect to the restriction model in which the polygon is reduced so that the reference point of the restriction model becomes the origin of the three-dimensional coordinates, and a predetermined minute distance is obtained from the longest distance to the polygon farthest from the reference point. A plurality of polygon directions corresponding to the distance included in the range reduced by the amount are extracted as main axis candidates, and one main axis candidate satisfying a predetermined condition is selected as the main axis candidate from the extracted main axis candidates, and the selected main axis is selected. Second, creating a normalized regulation model by adjusting the scaling of the regulation model to a predetermined length and rotating the regulation model so that the direction of the main axis coincides with the first axis A regulation model normalized by a regulation model normalization device, and the received regulation model is registered in the regulation model database. Three-dimensional object modeling data output regulation device as claimed in any one of claims 12, characterized by further comprising a regulating model registration means for. Means for outputting the target model before polygon reduction by the polygon reduction means to a connected three-dimensional object shaping apparatus;
When it is determined that the output should be regulated by the polygon model collating unit executed in parallel with the three-dimensional object modeling process by the three-dimensional object modeling apparatus, the three-dimensional object modeling apparatus before the polygon reduction is performed. Means for outputting an output stop command for the target model of
The data output regulation device for three-dimensional object formation according to any one of claims 1 to 12, further comprising: A target model receiving means for receiving a target model via a network;
Output propriety data transmitting means for transmitting data based on the output propriety determined by the polygon model matching means to the transmission source of the target model;
The data output regulation device for three-dimensional object formation according to any one of claims 1 to 14, further comprising:   A program for causing a computer to function as the three-dimensional object formation data output restriction device according to any one of claims 1 to 15.