JP2025048130A - Drawing data generating method, drawing data generating device, charged particle beam drawing device, and program - Google Patents

Abstract

PURPOSE: To provide a method that can reduce a time required for a division process for dividing a polygon into reference figures.CONSTITUTION: A drawing data generating method according to an embodiment of the present invention includes the steps of reading out drawing data for a convex polygon stored in a storage device, in which the coordinates of each vertex are defined in the order in which they form the figure, projecting the convex polygon onto a line drawn in a first direction to identify the two most distant vertices, forming a median line segment that bisects the convex polygon connecting the two most distant vertices, and using the median line segment to extract from the convex polygon a plurality of figures using any one of a plurality of preset reference figures, and generating drawing data.SELECTED DRAWING: Figure 21

Description

One aspect of the present invention relates to a drawing data generation method, a drawing data generation device, a charged particle beam drawing device, and a program, and relates to a method for dividing a polygon defined in drawing data used for multi-beam drawing, for example, into predetermined reference figures.

Lithography technology, which is responsible for the advancement of miniaturization of semiconductor devices, is an extremely important process in the semiconductor manufacturing process that is the only one that generates patterns. In recent years, with the increasing integration density of LSIs, the circuit line width required for semiconductor devices has become finer year by year. Here, electron beam (electron beam) drawing technology inherently has excellent resolution, and drawing is performed on wafers, etc. using an electron beam.

For example, there is a drawing device that uses multiple beams. Compared to drawing with a single electron beam, using multiple beams allows many beams to be irradiated at once, greatly improving throughput. In such a multi-beam drawing device, for example, an electron beam emitted from an electron gun is passed through a mask with multiple holes to form multiple beams, each of which is blanked and each beam that is not blocked is reduced in size by an optical system and deflected by a deflector to be irradiated at the desired position on the sample.

In single-beam drawing, such as the variable beam shaping (VSB) method, a desired pattern is drawn by combining trapezoidal, rectangular, and triangular graphic patterns, for example. For this reason, when inspecting the shape of each graphic pattern defined in the drawing data input to the drawing device, it was sufficient to check the width and height of each graphic pattern. On the other hand, in multi-beam drawing, drawing is performed using a raster method, so in addition to the above-mentioned figures, polygons with more vertices than quadrilaterals can be included in the graphic data. On the other hand, when actually drawing, in order to avoid complicating data processing, polygons are divided into preset reference figures such as trapezoids, rectangles, and triangles, and are drawn using the drawing data of these reference figures.

This requires a process to divide the polygon into reference figures, but in the past, this process took a long time. Therefore, it is desirable to reduce the time required for the process to divide the polygon into reference figures.

Here, although it is not a polygon division process, a technique has been disclosed for determining the monotonic direction of a monotonic polygon and determining the filling direction of the figure accordingly (see Patent Document 1).

Japanese Patent Application Publication No. 5-061987

One aspect of the present invention provides a method and device that can reduce the time required for a division process that divides a polygon into reference shapes.

A method for generating drawing data according to one aspect of the present invention includes:
A step of reading out rendering data of a convex polygon, the rendering data being stored in a storage device and defined in an order in which the coordinates of the vertices form a figure, and projecting the convex polygon onto a line segment drawn in a first direction to identify two vertices that are furthest apart;
forming a median segment that bisects a convex polygon connecting the two most distant vertices;
a step of extracting a plurality of figures using any one of a plurality of preset reference figures from the convex polygon by using the central line segment, and generating drawing data;
The present invention is characterized by comprising:

a step of forming, for each base vertex, a line segment parallel to a second direction perpendicular to the first direction from the base vertex to a central line segment, the remaining vertices being set in order except for the two vertices furthest from the first direction;
calculating, for each base vertex, coordinates of an intersection between a line segment extending from the base vertex and a center line segment;
It is preferable that the sensor further comprises:

In addition, it is preferable to use one of the +x, -x, +y, and -y directions in the coordinate system of the drawing data as the first direction.

It is also preferable that the multiple shapes to be extracted include sides that extend in the x- or y-direction in the coordinate system of the drawing data.

The storage device also stores rendering data for a plurality of polygons;
The method further comprises the steps of reading out rendering data of a plurality of polygons from the storage device, and determining, for each polygon, a shape type of the polygon;
If the determination result indicates that the polygon is a convex polygon, it is preferable to carry out the above-mentioned steps.

A drawing data generating device according to one aspect of the present invention comprises:
a storage device for storing drawing data of a convex polygon in which the coordinates of each vertex are defined in the order that the polygon is formed;
a specifying unit that reads out rendering data of a convex polygon, the coordinates of which are defined in the order that the coordinates of the vertices form a figure, stored in a storage device, and projects the convex polygon onto a line segment drawn in a first direction to specify two vertices that are most distant from each other;
a central line segment forming part that forms a central line segment that bisects a convex polygon connecting the two most distant vertices;
an extraction processing unit that extracts a plurality of figures using any one of a plurality of preset reference figures from the convex polygon by using the central line segment, and generates drawing data;
The present invention is characterized by comprising:

A charged particle beam drawing apparatus according to one aspect of the present invention comprises:
a storage device for storing drawing data of a convex polygon in which the coordinates of each vertex are defined in the order that the polygon is formed;
a specifying unit that reads out rendering data of a convex polygon, the coordinates of which are defined in the order that the coordinates of the vertices form a figure, stored in a storage device, and projects the convex polygon onto a line segment drawn in a first direction to specify two vertices that are most distant from each other;
a central line segment forming part that forms a central line segment that bisects a convex polygon connecting the two most distant vertices;
an extraction processing unit that extracts a plurality of figures using any one of a plurality of preset reference figures from the convex polygon by using the central line segment, and generates drawing data;
a writing mechanism for writing, on a sample, a pattern of the plurality of figures for which the writing data has been generated, using a charged particle beam;
The present invention is characterized by comprising:

A program for causing a computer to execute one aspect of the present invention comprises:
a function of reading out rendering data of a convex polygon, the rendering data being stored in a storage device and defined in the order in which the coordinates of each vertex form a figure, and projecting the convex polygon onto a line segment drawn in a first direction to identify the two vertices that are furthest apart;
The function of forming a median segment that bisects a convex polygon connecting the two most distant vertices;
a function of extracting a plurality of figures using any one of a plurality of preset reference figures from a convex polygon by using a central line segment, and generating drawing data;
The present invention is characterized by comprising:

According to one aspect of the present invention, it is possible to reduce the time required for the division process of dividing a polygon into reference shapes. This reduces the drawing time.

FIG. 1 is a conceptual diagram showing a configuration of a drawing device according to a first embodiment. 1 is a conceptual diagram showing a configuration of a shaping aperture array substrate in embodiment 1. 2 is a cross-sectional view showing a configuration of a blanking aperture array mechanism in the first embodiment. FIG. FIG. 2 is a diagram showing an example of drawing data 1 according to the first embodiment. FIG. 2 is a flowchart showing main steps of a drawing data generating method according to the first embodiment. FIG. 2 is a diagram showing an example of an X-monotonic polygon in the first embodiment; FIG. 2 is a diagram showing an example of a Y monotonic polygon in the first embodiment. 3 is a diagram showing an example of a convex polygon according to the first embodiment; FIG. FIG. 2 is a diagram showing an example of a general polygon in the first embodiment. 4 is a block diagram showing an example of an internal configuration of a division processing unit in the first embodiment. FIG. 13 is a block diagram showing an example of an internal configuration of a general polygon division processing unit in embodiment 1. FIG. 11A to 11C are diagrams for explaining a general polygon division process in the first embodiment. 5A to 5C are diagrams showing examples of vertex lists before and after sorting processing in embodiment 1. 5A to 5C are diagrams showing examples of line segment lists before and after a sorting process in the first embodiment. 13 is a block diagram showing an example of an internal configuration of an X-monotonic polygon division processing unit in the first embodiment. FIG. FIG. 11 is a flowchart showing an example of internal steps of an X-monotonic polygon division processing step in the first embodiment. 10A to 10C are diagrams for explaining a method of dividing an X-monotonic polygon in the first embodiment; 11A to 11C are diagrams for explaining a method of dividing a Y monotone polygon in the first embodiment. 4 is a block diagram showing an example of an internal configuration of a convex polygon division processing unit in embodiment 1. FIG. FIG. 11 is a flowchart showing an example of internal steps of a convex polygon division processing step in the first embodiment. 4A to 4C are diagrams for explaining an example of a convex polygon division technique in the first embodiment. 10A to 10C are diagrams for explaining another example of a convex polygon division technique in the first embodiment. 4A to 4C are conceptual diagrams for explaining an example of a drawing operation in the first embodiment. 3A and 3B are diagrams showing an example of a multi-beam irradiation area and a pixel to be written in the first embodiment; 4A to 4C are diagrams for explaining an example of a multi-beam writing operation in the first embodiment.

In the following embodiments, a configuration using an electron beam as an example of a charged particle beam will be described. However, the charged particle beam is not limited to an electron beam, and may be a beam using charged particles such as an ion beam. Furthermore, in the embodiments, a configuration using multiple beams as the charged particle beam will be described. However, the charged particle beam is not limited to multiple beams. It may be a single beam.

Embodiment 1.
FIG. 1 is a conceptual diagram showing the configuration of a drawing apparatus in the first embodiment. In FIG. 1, the drawing apparatus 100 includes a drawing mechanism 150 and a control circuit 160. The drawing apparatus 100 is an example of a charged particle beam drawing apparatus. The drawing apparatus 100 is also an example of a multi-charged particle beam drawing apparatus and an example of a multi-charged particle beam exposure apparatus. The drawing mechanism 150 includes an electron lens barrel 102 (electron beam column) and a drawing chamber 103. In the electron lens barrel 102, an electron gun 201, an illumination lens 202, a shaping aperture array substrate 203, a blanking aperture array mechanism 204, a reduction lens 205, a limiting aperture substrate 206, an objective lens 207, a deflector 208, and a deflector 209 are arranged.

An XY stage 105 is placed in the drawing chamber 103. A sample 101 such as a mask that will be the target substrate for drawing during drawing (exposure) is placed on the XY stage 105. The sample 101 includes an exposure mask used when manufacturing a semiconductor device, or a semiconductor substrate (silicon wafer) on which a semiconductor device is manufactured. The sample 101 also includes mask blanks that are coated with resist and on which nothing has yet been drawn.

Furthermore, a mirror 210 for measuring the position of the XY stage 105 is placed on the XY stage 105.

The control system circuit 160 includes a control computer 110, a memory 112, a deflection control circuit 130, digital-to-analog conversion (DAC) amplifier units 132, 134, a lens control circuit 136, a stage control mechanism 138, a stage position measurement device 139, and storage devices 140, 142, 144 such as magnetic disk devices. The control computer 110, the memory 112, the deflection control circuit 130, the lens control circuit 136, the stage control mechanism 138, the stage position measurement device 139, and the storage devices 140, 142, 144 are connected to each other via a bus (not shown). The deflection control circuit 130 is connected to DAC amplifier units 132, 134 and a blanking aperture array mechanism 204. The deflector 209 is composed of four or more electrodes, and each electrode is controlled by the deflection control circuit 130 via the DAC amplifier 132. The deflector 208 is composed of four or more electrodes, and each electrode is controlled by the deflection control circuit 130 via the DAC amplifier 134. The electromagnetic lens group, such as the illumination lens 202, the reduction lens 205, and the objective lens 207, is controlled by the lens control circuit 136.

For example, the control computer 110, the memory 112, and the storage devices 140, 142, and 144 constitute an example of a drawing data generating device.

The position of the XY stage 105 is controlled by driving motors for each axis (not shown) controlled by a stage control mechanism 138. A stage position measuring device 139 receives reflected light from a mirror 210 and measures the position of the XY stage 105 using the principle of laser interferometry.

In the control computer 110, the shape determination processing unit 50, the division processing unit 80, the shot data generation unit 70, the data processing unit 72, the transfer processing unit 74, and the drawing control unit 76 are arranged. Each "~ unit" such as the shape determination processing unit 50, the division processing unit 80, the shot data generation unit 70, the data processing unit 72, the transfer processing unit 74, and the drawing control unit 76 has a processing circuit. Such a processing circuit includes, for example, an electric circuit, a computer, a processor, a circuit board, a quantum circuit, or a semiconductor device. Each "~ unit" may use a common processing circuit (the same processing circuit) or may use different processing circuits (separate processing circuits). Information input/output to/from the shape determination processing unit 50, the division processing unit 80, the shot data generation unit 70, the data processing unit 72, the transfer processing unit 74, and the drawing control unit 76 and information being calculated are stored in the memory 112 each time.

The drawing operation of the drawing device 100 is controlled by the drawing control unit 76. In addition, the transfer process of the irradiation time data for each shot to the deflection control circuit 130 is controlled by the transfer processing unit 74.

In addition, drawing data 1 (chip data) of multiple graphic patterns constituting the chip pattern is input from outside the drawing device 100 and stored in the memory device 140. The chip data defines information on the multiple graphic patterns constituting the chip pattern. Specifically, for example, a coordinate sequence of each vertex coordinate is defined for each graphic pattern. The multiple graphic patterns include multiple polygons in addition to triangles, rectangles, and trapezoids.

Here, FIG. 1 shows the configuration necessary for explaining the first embodiment. The drawing device 100 may also be provided with other configurations that are normally required.

2 is a conceptual diagram showing the configuration of the shaping aperture array substrate in the first embodiment. In FIG. 2, holes (openings) 22 are formed in a matrix of p columns (y direction) x q columns (x direction) (p, q≧2) at a predetermined arrangement pitch in the shaping aperture array substrate 203. In the example of FIG. 2, for example, 512×512 columns of holes 22 are formed in the vertical and horizontal directions (x, y directions). The number of holes 22 is not limited to this. For example, 32×32 columns of holes 22 may be formed. Each hole 22 is formed as a rectangle of the same dimensions. Alternatively, it may be a circle of the same diameter. A part of the electron beam 200 passes through each of these multiple holes 22, thereby forming a multibeam 20. In other words, the shaping aperture array substrate 203 forms and emits the multibeam 20. The shaping aperture array substrate 203 is an example of an emission source of the multibeam 20.

Figure 3 is a cross-sectional view showing an example of the configuration of the blanking aperture array mechanism in the first embodiment. As shown in Figure 3, the blanking aperture array mechanism 204 has a blanking aperture array substrate 31 using a semiconductor substrate made of silicon or the like arranged on a support stand 33. In the membrane region 330 in the center of the blanking aperture array substrate 31, a through hole 25 (opening) for each beam of the multi-beam 20 is opened at a position corresponding to each hole 22 of the shaping aperture array substrate 203 shown in Figure 2. Then, a pair of a control electrode 24 and a counter electrode 26 (blanker: blanking deflector) is arranged at a position facing each other across the corresponding through hole 25 among the multiple through holes 25. In addition, a control circuit 41 (logic circuit) that applies a deflection voltage to the control electrode 24 for each through hole 25 is arranged inside the blanking aperture array substrate 31 near each through hole 25. The counter electrode 26 for each beam is connected to ground.

An amplifier (an example of a switching circuit) (not shown) is arranged in the control circuit 41. As an example of an amplifier, a CMOS (Complementary MOS) inverter circuit serving as a switching circuit is arranged. Either an L (low) potential (e.g., ground potential) lower than the threshold voltage or an H (high) potential (e.g., 1.5 V) equal to or higher than the threshold voltage is applied as a control signal to the input (IN) of the CMOS inverter circuit. In the first embodiment, when an L potential is applied to the input (IN) of the CMOS inverter circuit, the output (OUT) of the CMOS inverter circuit applied to the control circuit 41 becomes a positive potential (Vdd), and the corresponding beam is deflected by the electric field due to the potential difference with the ground potential of the opposing electrode 26, and the beam is controlled to be turned OFF by being shielded by the limiting aperture substrate 206. On the other hand, when an H potential is applied to the input (IN) of the CMOS inverter circuit (active state), the output (OUT) of the CMOS inverter circuit becomes ground potential, and since there is no potential difference with the ground potential of the opposing electrode 26 and the corresponding beam is not deflected, the beam is controlled to be ON by passing through the limiting aperture substrate 206. Blanking control is performed by such deflection.

Next, a specific example of the operation of the drawing mechanism 150 will be described. The electron beam 200 emitted from the electron gun 201 (emission source) illuminates the entire shaping aperture array substrate 203 almost perpendicularly through the illumination lens 202. A plurality of rectangular holes 22 (openings) are formed in the shaping aperture array substrate 203, and the electron beam 200 illuminates an area including all of the plurality of holes 22. Each part of the electron beam 200 irradiated at the position of the plurality of holes 22 passes through each of the plurality of holes 22 of the shaping aperture array substrate 203, thereby forming, for example, a rectangular multi-beam (multiple electron beams) 20. The multi-beam 20 passes through the corresponding blankers of the blanking aperture array mechanism 204. Each of the blankers performs blanking control on the beams passing through individually so that the beams are in the ON state for the set drawing time (irradiation time).

The multi-beam 20 that has passed through the blanking aperture array mechanism 204 is reduced by the reduction lens 205 and advances toward the central hole formed in the limiting aperture substrate 206. Here, the electron beam deflected by the blanker of the blanking aperture array mechanism 204 is displaced from the central hole of the limiting aperture substrate 206 and is blocked by the limiting aperture substrate 206. On the other hand, the electron beam that has not been deflected by the blanker of the blanking aperture array mechanism 204 passes through the central hole of the limiting aperture substrate 206 as shown in FIG. 1. In this way, the limiting aperture substrate 206 blocks each beam that has been deflected by the blanker of the blanking aperture array mechanism 204 to be in a beam OFF state. Then, each beam of one shot is formed by the beam that has passed through the limiting aperture substrate 206 and has been formed from the time the beam is turned ON to the time the beam is turned OFF. The multi-beams 20 that have passed through the limiting aperture substrate 206 are focused by the objective lens 207 to become a pattern image with the desired reduction ratio, and the entire multi-beams 20 that have passed through the limiting aperture substrate 206 are deflected in the same direction by the deflectors 208 and 209, and each beam is irradiated at its respective irradiation position on the sample 101. Also, for example, when the XY stage 105 is moving continuously, the deflector 208 performs tracking control so that the irradiation position of the beam follows the movement of the XY stage 105. Ideally, the multi-beams 20 irradiated at one time are arranged at a pitch obtained by multiplying the arrangement pitch of the multiple holes 22 in the shaping aperture array substrate 203 by the desired reduction ratio described above.

Figure 4 is a diagram showing an example of drawing data 1 in embodiment 1. In the example of Figure 4, a pentagonal figure pattern i is shown. i indicates an index assigned to multiple figures. The pentagonal figure pattern i is formed by connecting five vertices 0, 1, 2, 3, and 4 in order. The drawing data of figure pattern i defines the coordinates of these vertices in, for example, a clockwise order.

As shown in FIG. 4, the multiple graphic patterns defined as drawing data include polygonal graphic patterns, which have more vertices than a quadrilateral. For this reason, polygonal graphic patterns are divided into preset reference graphic patterns such as triangles, rectangles, and trapezoids before drawing processing. Therefore, in the first embodiment, of the multiple graphic pattern data defined as drawing data 1 stored in the storage device 140, polygonal drawing data is divided into reference graphics and regenerated as drawing data 2 of the reference graphics.

Figure 5 is a flow chart showing the main steps of the drawing data generation method in embodiment 1. In Figure 5, the drawing data generation method in embodiment 1 performs a series of steps including a figure type determination step (S100), a general polygon division processing step (S110), an X-monotonic polygon division processing step (S200), a Y-monotonic polygon division processing step (S300), and a convex polygon division processing step (S400). The figure type determination step (S100) performs a determination step (S102) and a determination step (S104) as internal steps.

In the determination step (S100), the shape determination processing unit 50 reads out the drawing data 1 of a polygon from among the drawing data 1 of multiple figure patterns stored in the storage device 140, and determines the shape type of each polygon. Here, first, in the determination step (S102), it is determined whether the polygon is a monotonic polygon. If it is not a monotonic polygon, it is determined to be another general polygon. Then, if it is a monotonic polygon, in the determination step (S104), the shape determination processing unit 50 further determines whether it is an X-monotonic polygon, a Y-monotonic polygon, or a convex polygon. For an X-monotonic polygon, the x-direction in the coordinate system of the drawing data is used as the monotonic direction. For a Y-monotonic polygon, the y-direction in the coordinate system of the drawing data is used as the monotonic direction.

Figure 6 is a diagram showing an example of an X-monotonic polygon in the first embodiment. An X-monotonic polygon refers to a figure that does not have crossings (self-intersections) between its own sides and does not include a hole pattern within the figure, in which the x-component of the point sequence from the leftmost point to the rightmost point of the vertex sequence increases monotonically, and the x-component of the point sequence from the rightmost point to the leftmost point increases monotonically. Alternatively, an X-monotonic polygon refers to a figure that does not have crossings (self-intersections) between its own sides and does not have a hole pattern within the figure, and in which the sign of the x-direction displacement of each vertex arranged in the order in which the figure is formed by connecting the vertices in order is inverted from positive to negative, or from negative to positive, two or less times. In the example of Figure 6, for example, the displacement amount decreases in the -x direction clockwise from the vertex immediately to the right of the lower left end, reaches the vertex at the lower left end, and continues to the vertex at the upper left end. Then, from the vertex at the upper left end, the displacement amount increases in the +x direction in order, reaching the vertex at the upper right end. Then, it continues to the vertex at the lower right end. Then, the amount of displacement in the x direction decreases from the vertex at the bottom right in the -x direction, returning to the vertex immediately to the right of the bottom left. Therefore, the sign of the displacement is inverted twice in total: once from the -x direction to the +x direction, and once from the +x direction to the -x direction. Furthermore, there are no self-intersections between the sides of the polygon in the example of Figure 6, and there are no hole patterns within the polygon. Therefore, the polygon in Figure 6 is an X-monotonic polygon.

Figure 7 is a diagram showing an example of a Y-monotonic polygon in the first embodiment. A Y-monotonic polygon refers to a figure that does not have crossings (self-intersections) between its own sides and does not include a hole pattern within the figure, in which the y component of the point sequence from the lowest point of the vertex sequence to the highest point is monotonically increasing, and the y component of the point sequence from the highest point to the lowest point is monotonically decreasing. Alternatively, a Y-monotonic polygon refers to a figure that does not have crossings (self-intersections) between its own sides and does not have a hole pattern within the figure, and in which the sign of the y-direction displacement of each vertex arranged in the order in which the figure is formed by connecting the vertices in order is inverted from positive to negative, or from negative to positive, two or less times. In the example of Figure 7, for example, the displacement amount decreases in the -y direction clockwise from the vertex next to the lower right part, reaches the vertex at the lower right part, and continues to the vertex at the lower left part. Then, from the vertex at the lower left part, the displacement amount in the y direction increases in order in the +y direction until it reaches the vertex at the upper left part. Then, it continues to the vertex at the upper right part. Then, the amount of displacement in the y direction decreases in the -y direction from the vertex at the top right, returning to the vertex next above at the bottom right. Therefore, the sign of the displacement is inverted only twice in total: once from the -y direction to the +y direction, and once from the +y direction to the -y direction. Furthermore, there are no self-intersections between the sides of the polygon in the example of Figure 7, and there are no hole patterns within the polygon. Therefore, the polygon in Figure 7 is a Y-monotonic polygon.

FIG. 8 is a diagram showing an example of a convex polygon according to the first embodiment. In FIG.
A convex polygon refers to a figure in which there are no self-intersections between its own sides, no hole patterns within the figure, and all interior angles are less than 180 degrees. There are no self-intersections between the sides of the polygon in the example of FIG. 8, and there are no hole patterns within the polygon. Also, all interior angles are less than 180 degrees. Therefore, the polygon in FIG. 8 is a convex polygon. Note that a convex polygon is an xy monotonic polygon. This is because even if all interior angles are less than 180 degrees, they will self-intersect if they are not xy monotonic.

Figure 9 is a diagram showing an example of a general polygon in embodiment 1. In the example of Figure 9, the polygon is neither x-monotonic nor y-monotonic, and none of the interior angles are less than 180 degrees. Therefore, the polygon in the example of Figure 9 is determined to be another general polygon. Also, the example of Figure 9 shows a case where, for example, a hole pattern is placed inside.

In the above example, the type of polygon is determined from the actual shape of the polygon, but this is not limiting. It is also preferable to configure the format of the drawing data 1 so that an identifier is defined to indicate whether the figure is an X-monotonic polygon, a Y-monotonic polygon, or a convex polygon. In such a case, the shape determination processing unit 50 can determine the figure type of the figure from the defined identifier. There may also be an identifier for other general polygons. If there is no identifier, then for figure patterns with five or more vertices, a figure pattern without an identifier can be determined to be another general polygon.

Figure 10 is a block diagram showing an example of the internal configuration of the division processing unit in the first embodiment. In Figure 10, the division processing unit 80 includes the X monotonic polygon division processing unit 52, the Y monotonic polygon division processing unit 54, the convex polygon division processing unit 56, and the general polygon division processing unit 57. Each "~ unit" such as the X monotonic polygon division processing unit 52, the Y monotonic polygon division processing unit 54, the convex polygon division processing unit 56, and the general polygon division processing unit 57 has a processing circuit. Such a processing circuit includes, for example, an electric circuit, a computer, a processor, a circuit board, a quantum circuit, or a semiconductor device. Each "~ unit" may use a common processing circuit (the same processing circuit) or may use different processing circuits (separate processing circuits). Information input to and output from the X monotonic polygon division processing unit 52, the Y monotonic polygon division processing unit 54, the convex polygon division processing unit 56, and the general polygon division processing unit 57, and information during calculation are stored in the memory 112 each time.

In the general polygon division processing step (S110), if the general polygon division processing unit 57 determines that the polygon is a general polygon, it divides the general polygon into multiple figures in the shape of one of multiple preset reference figures, and generates drawing data 2 of the reference figures for the multiple divided figures. This is explained in detail below.

Figure 11 is a block diagram showing an example of the internal configuration of the general polygon division processing unit 57 in the first embodiment. In Figure 11, the general polygon division processing unit 57 includes a vertex list creation unit 60, a line segment list creation unit 61, a vertex sorting processing unit 62, a line segment sorting processing unit 63, a straight line formation unit 64, an intersection calculation unit 65, and a figure extraction unit 66. Each "~ unit" such as the vertex list creation unit 60, the line segment list creation unit 61, the vertex sorting processing unit 62, the line segment sorting processing unit 63, the straight line formation unit 64, the intersection calculation unit 65, and the figure extraction unit 66 has a processing circuit. Such a processing circuit includes, for example, an electric circuit, a computer, a processor, a circuit board, a quantum circuit, or a semiconductor device. Each "~ unit" may use a common processing circuit (the same processing circuit) or may use different processing circuits (separate processing circuits). Information input to and output from the vertex list creation unit 60, line segment list creation unit 61, vertex sorting unit 62, line segment sorting unit 63, straight line formation unit 64, intersection calculation unit 65, and figure extraction unit 66, as well as information being calculated, are stored in memory 112 each time.

Figure 12 is a diagram for explaining the general polygon division process in embodiment 1. The example in Figure 12 shows a general polygon in which a hole pattern formed by connecting four vertices 13 to 16 is placed inside a 13-gon formed by connecting 13 vertices 0 to 12. In the example in Figure 12, the vertex at the top left end is vertex 0, but the first vertex of each vertex coordinate defined in the drawing data does not necessarily indicate the position of the left end, etc. Meanwhile, the division process into reference shapes proceeds in one direction, either the x direction or the y direction.

For this reason, in the general polygon division process, the vertex list creation unit 60 first creates a vertex list for the general polygon.

Figure 13 shows an example of a vertex list before and after sorting in embodiment 1. As shown in the diagram on the left side of Figure 13, the vertex list created by the vertex list creation unit 60 starts with vertex 0 and is arranged in the order of vertices 1, 2, 3, ..., 12, in the order in which the vertex numbers are defined in the drawing data. Then, the vertices of the hole pattern are arranged in the order of 13, 14, 15, 16. The hole pattern is defined in the drawing data, for example, in a counterclockwise direction. Such a vertex list is not arranged along the x direction, for example.

The vertex sorting unit 62 then sorts the vertex list in ascending order of x coordinate. Vertices with the same x coordinate are sorted in ascending order of y coordinate, for example. As a result, the vertices are sorted in the order of vertex 0, vertex 11, vertex 9, vertex 12, ..., vertex 7, as shown in the right diagram of Figure 13.

Then, the line segment list creation unit 61 creates a line segment list that indicates the sides of the polygon.

Figure 14 shows an example of a line segment list before and after sorting in the first embodiment. As shown in the left diagram of Figure 14, the line segment list created by the line segment list creation unit 61 has line segment numbers arranged in the order of the vertices defined in the drawing data, in the order of line segment 0-1 connecting vertex 0 and vertex 1, line segment 1-2 connecting vertex 1 and vertex 2, line segment 3-2, line segment 3-4, line segment 5-4, ..., line segment 0-12. The hole pattern is similarly arranged in the order of line segment 13-14, line segment 15-14, ..., line segment 13-16. It is preferable to define the names of each line segment so that, for example, vertex 3, which has the smaller x-coordinate of the two points 2 and 3, is displayed first, such as line segment 3-2. Such a line segment list is not arranged, for example, along the x-direction.

The line segment sorting processing unit 63 then sorts the line segment list in ascending order of the x-coordinate of the starting point. Line segments with the same x-coordinate of the starting point are arranged, for example, in ascending order of the y-coordinate. Next, if there are multiple line segments with the same x-coordinate of the starting point, they are sorted in ascending order of the x-coordinate of the end point. As a result, as shown in the right diagram of Figure 14, the lines are rearranged in the following order: line segment 0-12, line segment 11-12, line segment 11-10, line segment 9-10, line segment 0-1, ..., line segment 6-7.

Next, the line forming unit 64 forms y-direction lines passing through the vertices in the order of the sorted vertex list. Note that for vertices 0, 11, and 9, which have the same x coordinate at the left end, extending a y-direction line does not form a reference figure that can be divided from a polygon, so there is no need to form a y-direction line. Similarly, for vertex 7, which has the rightmost x coordinate, extending a y-direction line does not form a reference figure that can be divided from a polygon, so there is no need to form a y-direction line.

Next, the intersection calculation unit 65 extracts sides that intersect with the y-direction straight line passing through the vertices in the order of the sorted vertex list, and calculates the coordinates of the intersections with the sides. In this case, the sorted line segment list can be used to calculate the intersecting sides (line segments).
For example, a y-direction line extended from vertices 12 and 10 at the same x-coordinate intersects with line segments 0-1 and 9-8 at points other than the vertices. Therefore, the coordinates of the intersections of the y-direction line and line segment 0-1 and the coordinates of the intersections of the y-direction line and line segment 9-8 are calculated.

The graphic extraction unit 66 extracts a triangle surrounded by the three intersections of vertices 0, 12, and line segment 0-1 (the intersection of the y-direction line and line segment 0-1), and generates drawing data 2. Similarly, it extracts a triangle surrounded by the three intersections of vertices 11, 12, and 10, and generates drawing data 2. Similarly, it extracts a triangle surrounded by the three intersections of vertices 9, 10, and line segment 9-8 (the intersection of the y-direction line and line segment 9-8), and generates drawing data 2.

Then, for the vertex with the next largest x coordinate in the sorted vertex list, y-direction line formation processing, intersection calculation processing, and shape extraction processing are performed. The same process is repeated below.

For example, the y-direction line passing through vertex 1 intersects with line segment 9-8. Therefore, the coordinates of the intersection of the y-direction line and line segment 9-8 are calculated. Then, a trapezoid enclosed by four intersections - the intersection of the y-direction line passing through vertex 12 with line segment 0-1, the intersection of the y-direction line passing through vertex 12 with line segment 9-8, and the intersection of vertex 1 and the y-direction line passing through vertex 1 with line segment 9-8 - is extracted, and drawing data 2 is generated.

By repeating the above process, a general polygon can be divided into multiple base figures, and multiple base figures can be extracted from the general polygon.

Conventionally, the above-mentioned general polygon division process was performed on all polygons, regardless of the type of polygon shape. However, in this general polygon division process, as described above, the creation and sorting of a vertex list, and the creation and sorting of a line segment list were performed, which took time for processing. In addition, a process was required to identify which line segments intersect with the y-direction line using the line segment list, and this identification process was also a factor in increasing the processing time. Furthermore, when a line intersects with multiple line segments, such as a y-direction line passing through vertex 15, for example, it was necessary to perform multiple intersection calculations, which was another factor in increasing the processing time.

Therefore, in the first embodiment, the method of division into reference figures is changed for each type of polygon shape. In the first embodiment, the method of division into reference figures for X-monotonic polygons, Y-monotonic polygons, and convex polygons is changed from general polygon division processing to individual division processing for each.

In the X-monotonic polygon division processing step (S200), if the polygon is determined to be an X-monotonic polygon that is monotonic in the x direction (first direction), the X-monotonic polygon division processing unit 52 divides the X-monotonic polygon into multiple figures in the shape of one of multiple preset reference figures, and generates drawing data 2 of the reference figures for the multiple divided figures. A specific description is given below.

Figure 15 is a block diagram showing an example of the internal configuration of the X-monotonic polygon division processing unit in embodiment 1. In Figure 15, within the X-monotonic polygon division processing unit 52, a start point/final point identification unit 170, a previous point/next point setting unit 171, a coordinate comparison unit 172, a coordinate comparison unit 173, a base vertex setting unit 174, an opposing vertex setting unit 175, a line segment formation unit 176, an intersection calculation unit 178, a figure extraction unit 180, a figure extraction unit 181, an adjacent point identification unit 182, and a determination unit 184 are arranged. Each of the "~ units" such as the start point/last point identification unit 170, the previous point/next point setting unit 171, the coordinate comparison unit 172, the coordinate comparison unit 173, the base vertex setting unit 174, the opposing vertex setting unit 175, the line segment formation unit 176, the intersection calculation unit 178, the figure extraction unit 180, the figure extraction unit 181, the adjacent point identification unit 182, and the determination unit 184 has a processing circuit. Such a processing circuit includes, for example, an electric circuit, a computer, a processor, a circuit board, a quantum circuit, or a semiconductor device. Each of the "~ units" may use a common processing circuit (the same processing circuit) or may use different processing circuits (separate processing circuits). Information input to and output from the start point/final point identification unit 170, previous point/next point setting unit 171, coordinate comparison unit 172, coordinate comparison unit 173, base vertex setting unit 174, opposite vertex setting unit 175, line segment formation unit 176, intersection calculation unit 178, figure extraction unit 180, figure extraction unit 181, adjacent point identification unit 182, and determination unit 184, as well as information being calculated, are stored in memory 112 each time.

Figure 16 is a flow chart showing an example of the internal steps of the X-monotonic polygon division processing step in the first embodiment. In Figure 16, the X-monotonic polygon division processing step (S200) in the first embodiment performs a series of steps including a start point/final point identification step (S201), a previous point/next point setting step (S202), a coordinate comparison step (S204), a base vertex setting step (S206), an opposing vertex setting step (S208), a judgment step (S209), a line segment formation step (S210), an intersection calculation step (S212), a figure extraction step (S214), an adjacent point identification step (S216), a coordinate comparison step (S220), and a final figure extraction step (S222).

If the result of the determination in the determination step (S100) is that the polygon is an X-monotonic polygon that is monotonic in the x direction, the processing in each step of Figure 16 is carried out.

In the start point/final point identification step (S201), the start point/final point identification unit 170 reads out drawing data 1 of an X-monotonic polygon that is monotonic in the x direction (first direction) and in which the coordinates of each vertex are defined in the order that they form the figure, stored in, for example, memory 112 (storage device), and identifies the vertex that is the leftmost point on the near side in the x direction in the X-monotonic polygon and the vertex that is the rightmost point on the far side in the x direction. The vertex with the smallest x coordinate of each vertex defined in the drawing data 1 can be identified as the leftmost point, and the vertex with the largest x coordinate can be identified as the rightmost point.

Figure 17 is a diagram for explaining how an X-monotonic polygon is divided in embodiment 1. In the example of Figure 17, for example, a 12-sided X-monotonic polygon with vertices 0 to 11 is shown. In the example of Figure 17, vertex 0 is the leftmost point, and vertex 7 is the rightmost point.

In the previous point/next point setting step (S202), the previous point/next point setting unit 171 sets vertex 11 adjacent to the starting point, which is the leftmost vertex 0 on the front side in the x direction, and vertex 11 adjacent to the starting point, which is the vertex 1 behind the starting point, in the order of the coordinates of each vertex 0 to 11 that constitutes the X monotonic polygon (figure) defined in the drawing data 1. Here, we show a case where the vertices of each figure are defined in the drawing data 1 in the order in which they form the figure in a clockwise direction.

In the coordinate comparison step (S204), the coordinate comparison unit 172 reads out drawing data 1 of a monotonic polygon that is monotonic in the x direction and is defined in the order in which the coordinates 0 to 11 of each vertex constitute a figure, which is stored in, for example, the memory 112 (storage device), and in the first comparison process, starting from the vertex 0 on the front side in the x direction of the X monotonic polygon, compares the x coordinates of the vertex 11 adjacent to the starting point and the vertex 1 adjacent to the starting point in the order of the coordinates of each vertex 0 to 11 that constitute the X monotonic polygon defined in the drawing data 1. For example, the vertex preceding the leftmost vertex 0 is P_lower, and the next vertex is P_upper. In the example of FIG. 17, vertex 11 is the first P_lower, and vertex 1 is the first P_upper. Then, the x coordinates of P_lower and P_upper are compared.

In the base vertex setting step (S206), the base vertex setting unit 174 sets the vertex with the smaller x coordinate as the base vertex as a result of the comparison in the nth (n is a natural number) round of base vertex setting processing. In the example of Figure 17, vertex 11 is set as the base vertex in the first round of base vertex setting processing.

As the opposing vertex setting step (S208), the vertex with the larger x coordinate as a result of the comparison is set as the opposing vertex in the nth (n is a natural number) opposing vertex setting process. In the example of Figure 17, vertex 1 is set as the opposing vertex in the first opposing vertex setting process.

In the determination step (S209), the determination unit 184 determines whether the set base vertex is the final point (rightmost point) as the nth (n is a natural number) determination process. For example, in the first determination process, the first base vertex is vertex 11, and therefore it is determined that it is not vertex 7, which is the rightmost point. If the set base vertex is not the final point (rightmost point), the process proceeds to the line segment formation step (S210). If the set base vertex is the final point (rightmost point), the process proceeds to the final figure extraction step (S222).

As the line segment forming step (S210), the line segment forming unit 176 forms a line segment parallel to the y direction (second direction) perpendicular to the x direction from the base vertex to the opposite side connecting the opposite vertex and the vertex adjacent to the opposite vertex, with the vertex having a smaller coordinate than the base vertex, as the nth (n is a natural number) line segment forming process. In the first line segment forming process, a line segment parallel to the y direction perpendicular to the x direction is formed from vertex 11, which is the base vertex, to the opposite side 0-1 connecting vertex 1, which is the opposite vertex, and vertex 0, which is adjacent to vertex 1 and has a smaller x coordinate than the base vertex. In other words, the line segment connecting the point with a larger x coordinate than the base vertex and its previous point as the opposite side is used as the opposite side, and a line segment parallel to the Y axis is drawn from the base vertex to the opposite side.

As an intersection calculation step (S212), the intersection calculation unit 178 calculates the coordinates of the intersection between the line segment extending from the base vertex and the opposite side as the nth coordinate calculation process. In the first coordinate calculation process, it calculates the coordinates of the intersection between the line segment extending in the y direction from vertex 11 and the opposite side 0-1.

As a figure extraction step (S214), the figure extraction unit 180 extracts, as an n-th reference figure extraction process, a figure surrounded by a line segment extending in the y direction, a line segment extending in the y direction formed in the n-1th line segment formation process immediately preceding the line segment extending in the y direction in the x direction, and at least a part of two sides of an X-monotonic polygon to which the line segment extending in the y direction is connected, as one of a plurality of preset reference figures, and generates drawing data 2. Alternatively, when there is no line segment extending in the y direction formed in the n-1th line segment formation process immediately preceding the line segment extending in the x direction, a figure surrounded by a vertex having a smaller x-coordinate than the line segment extending in the y direction, and at least a part of two sides of an X-monotonic polygon to which the line segment extending in the y direction is connected, as one of a plurality of preset reference figures, and generates drawing data 2. The drawing data 2 is defined, for example, in a clockwise order, so that the coordinates of each vertex of the reference figure constitute a figure. The generated drawing data 2 is stored in the storage device 144 .
17, in the first reference figure extraction process, since there is no line segment extending in the y direction immediately before the vertex 11 in the x direction, a figure enclosed by vertex 0, which has a smaller x coordinate than the line segment extending in the y direction from vertex 11, and at least a part of line segments 0-11 and 0-1, which are two sides connecting the line segment extending in the y direction of the X monotonic polygon, is divided from the X monotonic polygon as one of the reference figures, for example, a triangle, and extracted. Then, drawing data 2 is generated that defines the coordinates of the intersections of vertex 0, vertex 11, and the calculated line segment 0-1, arranged, for example, in a clockwise direction, and output to the storage device 144.

In the adjacent point identification process (S216), the adjacent point identification unit 182 identifies the vertices adjacent in the x direction of the base vertex as adjacent points in the nth adjacent point identification process. In the first adjacent point identification process, vertex 10 adjacent in the x direction of vertex 11, which is the base vertex, is identified as an adjacent point. Then, since vertex 1, which is P_upper, remains as the opposite vertex, vertex 10 is newly set as P_lower.

In the coordinate comparison step (S220), the coordinate comparison unit 173 compares the x-coordinates of the vertex adjacent to the base vertex in the x-direction with the opposing vertex whose coordinate was larger in the nth comparison process as the (n+1)th comparison process. In the second comparison process, vertex 10, which has newly become P_lower, is compared with vertex 1, which remains as the opposing vertex.

Then, the process returns to the base vertex setting process (S206), and the processes from the base vertex setting process (S206) to the coordinate comparison process (S220) are repeated until the base vertex that is set becomes the rightmost point (final point). Note that the vertex with the larger x coordinate in the coordinate comparison process (S220) returns to the opposite vertex setting process (S208).

Therefore, in the example of FIG. 17, the base vertex of the second round is vertex 1. Also, the opposing vertex is vertex 10. Then, a line segment parallel to the y direction from vertex 1 is extended to the opposite side 11-10, and the intersection point is calculated. Then, as the second reference figure extraction process, a trapezoid surrounded by a line segment extending in the y direction from vertex 1, a line segment extending in the y direction from vertex 1 formed in the first line segment formation process that is one line segment in the x direction before the line segment extending in the y direction from vertex 1, and at least a part of line segment 0-1 and line segment 11-10 that are two sides connecting the line segment extending in the y direction from vertex 1 of the X monotone polygon is extracted as one of a plurality of preset reference figures, and drawing data 2 is generated. Then, in the second adjacent point identification process, vertex 2 adjacent in the x direction to vertex 1, which is the base vertex, is identified as an adjacent point. Then, since vertex 10, which is P_lower, remains as an opposing vertex, vertex 2 is newly set as P_upper.
Then, in the third comparison process, vertex 2, which has newly become P_upper, is compared with vertex 10, which remains as the opposing vertex. Then, the base vertex for the third comparison becomes vertex 10. Also, the opposing vertex becomes vertex 2. Thereafter, this operation is repeated.

In the final figure extraction step (S222), when the vertex adjacent to the base vertex in the x direction reaches the most forward vertex in the x direction as the final reference figure extraction process, the figure extraction unit 181 extracts a figure surrounded by the line segment formed in the previous line segment formation process, the most forward vertex, and at least a part of the two sides connecting the line segment formed in the previous line segment formation process of the X monotone polygon as one of the multiple reference figures, and generates drawing data 2. In the example of FIG. 17, when the base vertex is vertex 6, vertex 7 adjacent to vertex 6 becomes the rightmost point in the next adjacent point identification process, so when this is reached, a triangle, for example, surrounded by the line segment extending parallel to the y direction from vertex 6, the rightmost vertex 7, and at least a part of the line segments 6-7 and 8-7 that are the sides connecting the line segment extending parallel to the y direction from vertex 6 is extracted as one of the reference figures. Then, drawing data 2 is generated.

According to the X-monotonic polygon division processing step (S200), the base vertex is shifted in the x direction from the leftmost point, making it unnecessary to create a vertex list and sort the vertices. In addition, the opposite side that intersects with the line segment extending from the base vertex in the y direction is the side that connects the opposite vertex and the vertex immediately before it, making it unnecessary to create a line segment list and sort the line segments. Therefore, the processing time for dividing an X-monotonic polygon can be significantly reduced compared to the general polygon division processing (S110) method. In the general polygon division processing (S110) method, when the number of vertices is n, the amount of calculation is generally greater than O(n), whereas the X-monotonic polygon division processing step (S200) can reduce the amount of calculation to O(n). O indicates the Landau symbol.

In the above example, the leftmost point is set as the start point and the rightmost point, the base vertex is set in ascending order of x coordinate in the +x direction in the coordinate system of the drawing data 1, and the reference figure is extracted in the +x direction. However, this is not limited to the above. For example, it is also suitable to set the rightmost point as the start point and the leftmost point as the end point, the base vertex is set in ascending order of x coordinate in the -x direction (another example of the first direction) in the coordinate system of the drawing data 1, and the reference figure is extracted in the -x direction. The ascending order of x coordinate in the -x direction is synonymous with the ascending order of x coordinate in the +x direction.

In the above example, the reference figures are extracted in order from the leftmost point to the rightmost point of the X monotone polygon, but this is not limited to the above. The reference figures may be extracted in order from both the leftmost and rightmost points of the X monotone polygon toward the center in the x direction.

In the Y-monotonic polygon division processing step (S300), if the polygon is determined to be a Y-monotonic polygon that is monotonic in the y direction (another example of the first direction), the Y-monotonic polygon division processing unit 54 divides the Y-monotonic polygon into multiple figures in the shape of one of multiple preset reference figures, and generates drawing data 2 of the reference figures for the multiple divided figures. This will be explained in detail below.

An example of the internal configuration of the Y monotone polygon division processing unit 54 in embodiment 1 is similar to that shown in FIG. 15. Also, an example of the internal process of the Y monotone polygon division processing step (S300) in embodiment 1 is similar to that shown in FIG. 16.

If the result of the determination in the determination step (S100) is that the polygon is a Y-monotonic polygon that is monotonic in the y direction, the processing in each step of Figure 16 is carried out.

In the start point/final point identification step (S201), the start point/final point identification unit 170 reads out drawing data 1 of a Y-monotonic polygon that is monotonic in the y direction (another example of the first direction) and in which the coordinates of each vertex are defined in the order that the figure is formed, stored in, for example, the memory 112 (storage device), and identifies the vertex that is the lowest point on the nearest side in the y direction in the Y-monotonic polygon and the vertex that is the highest point on the farthest side in the y direction. The vertex with the smallest y coordinate of each vertex defined in the drawing data 1 may be identified as the lowest point, and the vertex with the largest y coordinate may be identified as the highest point.
Here, the direction from bottom to top is defined as the y direction, but the direction from top to bottom may be defined as the y direction. In such a case, the starting point is the topmost point, and the final point is the bottommost point.

Figure 18 is a diagram for explaining how a Y monotonic polygon is divided in the first embodiment. In the example of Figure 18, for example, a 12-sided X monotonic polygon with vertices 0 to 11 is shown. In the example of Figure 18, vertex 0 is the lowest point and vertex 7 is the highest point.

In the previous point/next point setting step (S202), the previous point/next point setting unit 171 sets vertex 11 adjacent to the starting point, which is the lowest vertex 0 on the nearest side in the y direction, and vertex 11 adjacent to the starting point and vertex 1 adjacent to the starting point, in the order of the coordinates of each vertex 0 to 11 constituting the Y monotonic polygon (figure) defined in the drawing data 1. Here, we show a case where the vertices of each figure are defined in the drawing data 1 in the order in which they form the figure in a clockwise direction.

In the coordinate comparison step (S204), the coordinate comparison unit 172 reads out drawing data 1 of a monotonic polygon that is monotonic in the y direction and is defined in the order in which the coordinates 0 to 11 of each vertex constitute a figure, which is stored in, for example, the memory 112 (storage device), and as a first comparison process, it compares the y coordinates of the vertex 11 that is one position before the starting point and the vertex 1 that is one position after the starting point in the order of the coordinates of each vertex 0 to 11 that constitute the Y monotonic polygon defined in the drawing data 1, starting from the vertex 0 that is the foremost position in the y direction in the Y monotonic polygon. For example, the vertex that is the previous point of the vertex 0 that is the lowest point is P_right, and the vertex that is the next point is P_left. In the example of FIG. 18, vertex 11 is the first P_right, and vertex 1 is the first P_left. Then, it compares the y coordinates of P_right and P_left.

In the base vertex setting step (S206), the base vertex setting unit 174 sets the vertex with the smaller y coordinate as the base vertex as a result of the comparison in the nth (n is a natural number) base vertex setting process. In the example of Figure 18, in the first base vertex setting process, vertex 11 is set as the base vertex.

As the opposing vertex setting step (S208), the vertex with the larger y coordinate as a result of the comparison is set as the opposing vertex in the nth (n is a natural number) opposing vertex setting process. In the example of Figure 18, vertex 1 is set as the opposing vertex in the first opposing vertex setting process.

In the determination step (S209), the determination unit 184 determines whether the set base vertex is the final point (topmost point) as the nth (n is a natural number) determination process. For example, in the first determination process, the first base vertex is vertex 11, and therefore it is determined that it is not vertex 7, which is the topmost point. If the set base vertex is not the final point (topmost point), the process proceeds to the line segment formation step (S210). If the set base vertex is the final point (topmost point), the process proceeds to the final figure extraction step (S222).

As the line segment forming step (S210), the line segment forming unit 176 forms a line segment parallel to the x direction (another example of the second direction) perpendicular to the y direction from the base vertex to the opposite side connecting the opposite vertex and the vertex adjacent to the opposite vertex, with the vertex having a smaller coordinate than the base vertex, as the nth (n is a natural number) line segment forming process. In the first line segment forming process, a line segment parallel to the x direction perpendicular to the y direction is formed from vertex 11, which is the base vertex, to the opposite side 0-1 connecting vertex 1, which is the opposite vertex, and vertex 0, which is adjacent to vertex 1 and has a smaller y coordinate than the base vertex. In other words, the line segment connecting the point with a larger y coordinate than the base vertex and its previous point as the opposite side is used as the opposite side, and a line segment parallel to the X axis is drawn from the base vertex to the opposite side.

As an intersection calculation step (S212), the intersection calculation unit 178 calculates the coordinates of the intersection between the line segment extending from the base vertex and the opposite side as the nth coordinate calculation process. In the first coordinate calculation process, it calculates the coordinates of the intersection between the line segment extending from vertex 11 in the x direction and the opposite side 0-1.

As a figure extraction step (S214), the figure extraction unit 180 extracts, as an n-th reference figure extraction process, a figure surrounded by a line segment extending in the x direction, a line segment extending in the x direction formed in the n-1th line segment formation process immediately before the line segment extending in the x direction, and at least a part of two sides of a Y monotone polygon connected by the line segment extending in the x direction, as one of a plurality of preset reference figures, and generates drawing data 2. Alternatively, when there is no line segment extending in the x direction formed in the n-1th line segment formation process immediately before the y direction, a figure surrounded by a vertex having a smaller x coordinate than the line segment extending in the x direction, and at least a part of two sides of a Y monotone polygon connected by the line segment extending in the x direction, as one of a plurality of preset reference figures, and generates drawing data 2. The drawing data 2 is defined, for example, in a clockwise order, so that the coordinates of each vertex of the reference figure constitute a figure. The generated drawing data 2 is stored in the storage device 144 .
18, in the first reference figure extraction process, since there is no line segment extending in the x direction immediately before the y direction, a figure surrounded by vertex 0, which has a smaller y coordinate than the line segment extending in the x direction from vertex 11, and at least a part of line segments 0-11 and 0-1, which are two sides connecting the line segment extending in the x direction of the Y monotonic polygon, is divided and extracted from the Y monotonic polygon as one of the reference figures, for example, a triangle. Then, drawing data 2 is generated that defines the coordinates of the intersections of vertex 0, vertex 11, and the calculated line segment 0-1, arranged, for example, in a clockwise direction, and output to the storage device 144.

In the adjacent point identification step (S216), the adjacent point identification unit 182 identifies the vertices adjacent in the y direction of the base vertex as adjacent points in the nth adjacent point identification process. In the first adjacent point identification process, vertex 10 adjacent in the y direction of vertex 11, which is the base vertex, is identified as an adjacent point. Then, since vertex 1, which is P_left, remains as the opposite vertex, vertex 10 is newly set as P_right.

In the coordinate comparison step (S220), the coordinate comparison unit 173 compares the y coordinates of the vertex adjacent to the base vertex in the y direction with the opposing vertex whose coordinate was larger in the nth comparison process as the (n+1)th comparison process. In the second comparison process, it compares vertex 10, which has newly become P_right, with vertex 1, which remains as the opposing vertex.

Then, the process returns to the base vertex setting process (S206), and the processes from the base vertex setting process (S206) to the coordinate comparison process (S220) are repeated until the base vertex that is set becomes the uppermost point (final point). Note that the vertex with the larger y coordinate in the coordinate comparison process (S220) returns to the opposite vertex setting process (S208).

Therefore, in the example of FIG. 18, the base vertex of the second round is vertex 1. Also, the opposing vertex is vertex 10. Then, a line segment parallel to the x direction from vertex 1 is extended to the opposite side 11-10, and the intersection point is calculated. Then, as the second reference figure extraction process, a trapezoid surrounded by a line segment extending in the x direction from vertex 1, a line segment extending in the x direction from vertex 11 formed in the first line segment formation process immediately preceding the line segment extending in the x direction from vertex 1 in the y direction, and at least a part of line segment 0-1 and line segment 11-10, which are two sides connecting the line segment extending in the x direction from vertex 1 of the Y monotone polygon, is extracted as one of a plurality of preset reference figures, and drawing data 2 is generated. Then, in the second adjacent point identification process, vertex 2 adjacent in the y direction to vertex 1, which is the base vertex, is identified as an adjacent point. Then, since vertex 10, which is P_right, remains as an opposing vertex, vertex 2 is newly set as P_left.
Then, in the third comparison process, vertex 2, which has newly become P_left, is compared with vertex 10, which remains as the opposing vertex. Then, the base vertex for the third comparison becomes vertex 10. Also, the opposing vertex becomes vertex 2. Thereafter, this operation is repeated.

In the final figure extraction step (S222), when the vertex adjacent to the base vertex in the y direction reaches the most forward vertex in the y direction as the final reference figure extraction process, the figure extraction unit 181 extracts a figure surrounded by the line segment formed in the previous line segment formation process, the most forward vertex, and at least a part of the two sides connecting the line segment formed in the previous line segment formation process of the Y monotone polygon as one of the multiple reference figures, and generates drawing data 2. In the example of FIG. 18, when the base vertex is vertex 6, vertex 7 adjacent to vertex 6 becomes the top point in the next adjacent point identification process, so when this is reached, a triangle, for example, surrounded by the line segment extending parallel to the x direction from vertex 6, vertex 7 becoming the top point, and at least a part of the line segments 6-7 and 8-7 that are the sides connecting the line segment extending parallel to the x direction from vertex 6 is extracted as one of the reference figures. Then, drawing data 2 is generated.

According to the Y monotonic polygon division processing step (S300), the base vertex is shifted in the y direction from the lowest point, making it unnecessary to create a vertex list and sort the vertices. In addition, the opposite side that intersects with the line segment extending from the base vertex in the x direction is the side that connects the opposite vertex and the vertex immediately before it, making it unnecessary to create a line segment list and sort the line segments. Therefore, the processing time for dividing a Y monotonic polygon can be significantly reduced compared to when the general polygon division processing (S110) method is used. In the general polygon division processing (S110) method, when the number of vertices is n, the amount of calculation is generally greater than O(n), whereas the Y monotonic polygon division processing step (S300) can reduce the amount of calculation to O(n).

In the above example, the X monotonic polygon division process (S200) and the Y monotonic polygon division process step (S300) are performed separately, but this is not the only option. If a Y monotonic polygon is determined to be a Y monotonic polygon, the Y monotonic polygon may be rotated 90 degrees by the rotation process (S106) in FIG. 5 to become an X monotonic polygon, and the X monotonic polygon division process (S200) may be performed. In this case, after the division process, the divided multiple reference figures are all rotated -90 degrees to create drawing data 2 that is returned to the original coordinates. When the rotation process (S106) in FIG. 5 is performed, the Y monotonic polygon division process step (S300) is omitted.

In the above example, the base vertex is set in ascending order of y coordinates in the +y direction in the coordinate system of the drawing data 1, with the start point being the lowest point and the end point being the highest point, and the reference figure is extracted in the +y direction. However, this is not limited to the above. For example, it is also suitable to set the base vertex in ascending order of y coordinates in the -y direction (another example of the first direction) in the coordinate system of the drawing data 1, with the start point being the highest point and the end point being the lowest point, and extract the reference figure in the -y direction. The ascending order of y coordinates in the -y direction is synonymous with the ascending order of y coordinates in the +y direction.

In the above example, the reference figures are extracted in order from the lowest point to the highest point of the Y monotone polygon, but this is not limited to the above. The reference figures may be extracted in order from both the lowest and highest points of the Y monotone polygon toward the center in the y direction.

In the convex polygon division processing step (S400), if the polygon is determined to be a convex polygon, the convex polygon division processing unit 56 divides the convex polygon into multiple figures in the shape of one of multiple preset reference figures, and generates drawing data 2 of the reference figure for each of the multiple divided figures. In the convex polygon division processing, the convex polygon is divided using a median line segment that bisects the convex polygon, connecting the vertex closest to the front in the x direction (or y direction) and the vertex furthest away in the x direction. A specific description is given below.

19 is a block diagram showing an example of the internal configuration of the convex polygon division processing unit in the first embodiment. In FIG. 19, the convex polygon division processing unit 56 includes a start point/farthest point identification unit 270, a central line segment formation unit 272, a base vertex setting unit 274, a line segment formation unit 276, an intersection calculation unit 278, a figure extraction unit 280, a figure extraction unit 281, an adjacent point identification unit 282, a determination unit 283, a determination unit 284, and a figure extraction unit 286. Each of the "~ units" such as the start point/farthest point identification unit 270, the central line segment formation unit 272, the base vertex setting unit 274, a line segment formation unit 276, an intersection calculation unit 278, a figure extraction unit 280, a figure extraction unit 281, an adjacent point identification unit 282, a determination unit 283, a determination unit 284, and a figure extraction unit 286 has a processing circuit. Such a processing circuit includes, for example, an electric circuit, a computer, a processor, a circuit board, a quantum circuit, or a semiconductor device. Each "~ unit" may use a common processing circuit (the same processing circuit), or may use different processing circuits (separate processing circuits). Information input to and output from the start point/farthest point identification unit 270, the central line segment formation unit 272, the base vertex setting unit 274, the line segment formation unit 276, the intersection calculation unit 278, the figure extraction unit 280, the figure extraction unit 281, the adjacent point identification unit 282, the judgment unit 283, the judgment unit 284, and the figure extraction unit 286, as well as information being calculated, are stored in the memory 112 each time.

Figure 20 is a flow chart showing an example of the internal steps of the convex polygon division processing step in the first embodiment. In Figure 20, the convex polygon division processing step (S400) in the first embodiment performs a series of steps including a start point/farthest point identification step (S401), a central line segment formation step (S402), a base vertex setting step (S404), a judgment step (S408), a line segment formation step (S410), an intersection calculation step (S412), a figure extraction step (S414), a figure extraction step (S416), an adjacent point identification step (S420), a judgment step (S422), and a final figure extraction step (S424).

If the result of the determination in the determination step (S100) is that the polygon is a convex polygon, the processing in each step of Figure 20 is carried out.

As the start point/furthest point identification step (S401), the start point/furthest point identification unit 270 reads out the drawing data of a convex polygon in which the coordinates of each vertex are defined in the order that the figure is formed, stored in, for example, the memory 112 (storage device), and projects the convex polygon onto a line segment drawn in, for example, the x direction (an example of the first direction) to identify the two most distant vertices. In other words, the start point/furthest point identification unit 270 reads out the drawing data 1 of a convex polygon in which the coordinates of each vertex are defined in the order that the figure is formed, stored in, for example, the memory 112 (storage device), and identifies the vertex that is the leftmost point (start point) on the front side in, for example, the x direction (an example of the first direction) of the convex polygon and the vertex that is the rightmost point (furthest point) farthest in, for example, the x direction. The vertex with the smallest x coordinate of each vertex defined in the drawing data 1 may be identified as the leftmost point, and the vertex with the largest x coordinate may be identified as the rightmost point.

Figure 21 is a diagram for explaining an example of a convex polygon division method in embodiment 1. In Figure 21, for example, a 10-sided convex polygon with vertices 0 to 9 is shown. In the example of Figure 21, vertex 0 is the leftmost point and vertex 5 is the rightmost point.

As the central line segment forming step (S402), the central line segment forming unit 272 forms a central line segment that bisects the convex polygon connecting the two identified most distant vertices. In other words, the central line segment forming unit 272 forms a central line segment that bisects the convex polygon connecting the leftmost vertex that is furthest from the leftmost vertex in the x direction and the rightmost vertex that is furthest from the leftmost vertex in the x direction. In the example of FIG. 21, a central line segment that connects vertices 0 and 5 is formed.

In the base vertex setting step (S404), the base vertex setting unit 274 sets the next vertex of the vertex set as the base vertex in the n-1th base vertex setting process as the base vertex in the n-1th base vertex setting process. Alternatively, if there is no vertex set as the base vertex in the n-1th base vertex setting process, the next vertex of the leftmost point is set as the base vertex. In the first base vertex setting process, since there is no vertex set as the base vertex in the n-1th base vertex setting process, the base vertex setting unit 274 sets the vertex 1, which is the next vertex of the leftmost point 0 on the front side in the x direction, as the base vertex. In other words, the base vertex setting unit 274 sets the vertex 1 adjacent to the starting point in the order of the coordinates of each vertex 0 to 9 constituting the convex polygon (figure) defined in the drawing data 1, as the base vertex, starting from the leftmost point 0 on the front side in the x direction. Here, a case is shown in which the vertices of each figure are defined in the drawing data 1 in the order in which the figure is constituted in a clockwise direction.

In the determination step (S408), the determination unit 283 determines whether the set base vertex is the rightmost point (the farthest point) as the nth farthest point determination process. If the base vertex is not the rightmost point, the process proceeds to the line segment formation step (S410). If the base vertex is the rightmost point, the process proceeds to the figure extraction step (S416). In the first determination process, the base vertex is vertex 1, so it is determined that it is not vertex 5, which is the rightmost point.

As the line segment formation step (S410), the line segment formation unit 276 forms a line segment that extends from the base vertex to the central line segment in parallel to the y direction (an example of the second direction) that is perpendicular to the x direction, as the nth line segment formation process. In the first line segment formation process, a line segment that is parallel to the y direction from vertex 1 to the central line segment is formed.

As an intersection calculation step (S412), the intersection calculation unit 278 calculates the coordinates of the intersection between the center line segment and a line segment extending parallel to the y direction from the base vertex as the nth intersection calculation process.

As a figure extraction step (S414), the figure extraction unit 280 extracts multiple figures using any one of multiple preset reference figures from the convex polygon using the central line segment as the nth reference figure extraction process, and generates drawing data 2. From the convex polygon, it divides and extracts a figure surrounded by a line segment connecting the nth base vertex and the n-1th base vertex, a y-direction line segment extending from the nth base vertex to the central line segment, a y-direction line segment extending from the n-1th base vertex to the central line segment, and a part of the central line segment connecting the nth intersection of the y-direction line segment extending from the nth base vertex and the central line segment and the n-1th intersection of the y-direction line segment extending from the n-1th base vertex and the central line segment. Alternatively, if there is no y-direction line segment extending from the (n-1)th base vertex, a figure enclosed by a line segment connecting the nth base vertex and the vertex immediately preceding the nth base vertex, a y-direction line segment extending from the nth base vertex to the center line segment, and a portion of the center line segment connecting the vertex immediately preceding the nth base vertex and the nth intersection of the y-direction line segment extending from the nth base vertex and the center line segment is divided and extracted from the convex polygon. In the first figure extraction process, since there is no n-1th base vertex, a triangle enclosed by a line segment 0-1 connecting vertex 1, which is the first base vertex, and vertex 0 immediately preceding vertex 1, a y-direction line segment extending from vertex 1 to the center line segment, and a portion of the center line segment connecting vertex 0 and the intersection of the y-direction line segment extending from vertex 1 and the center line segment is divided and extracted from the convex polygon. Here, drawing data 2 is generated in which the coordinates of vertex 0, vertex 1, and the coordinates of the intersection between the y-direction line segment extending from vertex 1 and the center line segment are arranged, for example, in a clockwise direction. The generated drawing data 2 is stored in the storage device 144.

In the figure extraction step (S416), as one of the nth reference figure extraction processes, when the base vertex is the rightmost point, the figure extraction unit 281 divides and extracts from the convex polygon a triangle enclosed by a line segment connecting the base vertex and the vertex immediately before the base vertex, a y-direction line segment extending from the vertex immediately before the base vertex to the center line segment, and a line segment connecting the intersection of the y-direction line segment with the center line segment and the rightmost point. Then, drawing data 2 is generated in which the vertices are arranged clockwise, and is stored in the storage device 144.

In the adjacent point identification process (S420), the adjacent point identification unit 282 identifies the next vertex adjacent to the base vertex as an adjacent point in the n-th adjacent point identification process. In the first adjacent point identification process, vertex 2 is the adjacent point.

In the determination step (S422), the determination unit 284 determines whether the identified adjacent point is the leftmost point that will be the starting point as the nth start point determination process. If the identified adjacent point is the leftmost point that will be the starting point, the process proceeds to the final figure extraction step (S424). If the identified adjacent point is not the leftmost point that will be the starting point, the process returns to the base vertex setting step (S404) and repeats each step from the base vertex setting step (S404) to the determination step (S422) until the identified adjacent point becomes the leftmost point that will be the starting point.

As a result, the remaining vertices, excluding the two vertices furthest from each other in the x direction, are sequentially set as base vertices, and for each base vertex, a line segment parallel to the y direction (second direction) perpendicular to the x direction is formed from the base vertex to the center line segment. In other words, the remaining vertices, excluding the leftmost vertex and the rightmost vertex, are sequentially set as base vertices, and a line segment parallel to the y direction perpendicular to the x direction is formed from the base vertex to the center line segment. Then, the coordinates of the intersection between the y direction line segment extending from the base vertex and the center line segment are calculated.
Then, a reference figure having a line segment in the y direction as one side is extracted. Therefore, the extracted reference figures each include a side extending in the y direction in the coordinate system of the drawing data.

For example, in the second reference figure extraction process, a trapezoid surrounded by a y-direction line segment extending from vertex 2 to the center line segment, a y-direction line segment extending from vertex 1 to the center line segment, line segment 1-2 connecting vertex 1 and vertex 2, and a line segment connecting the intersection of the y-direction line segment extending from vertex 2 with the center line segment and the intersection of the y-direction line segment extending from vertex 1 with the center line segment is extracted as one of multiple preset reference figures, and drawing data 2 is generated. Then, in the second adjacent point identification process, vertex 3, which is adjacent to vertex 2, the base vertex, is identified as an adjacent point. This operation is then repeated.

For example, in the ninth reference figure extraction process, a trapezoid surrounded by a y-direction line segment extending from vertex 9 to the center line segment, a y-direction line segment extending from vertex 8 to the center line segment, a line segment 9-8 connecting vertex 9 and vertex 8, and a line segment connecting the intersection of the y-direction line segment extending from vertex 9 with the center line segment and the intersection of the y-direction line segment extending from vertex 8 with the center line segment is extracted as one of multiple preset reference figures, and drawing data 2 is generated. Then, in the ninth adjacent point identification process, vertex 0, which is the next vertex adjacent to vertex 0, the base vertex, is identified as the adjacent point. Because vertex 0 is the starting point, the process proceeds to the final figure extraction step (S424).

In the final geometrical figure extraction step (S424), when the base vertex is the leftmost point, the geometrical figure extraction unit 286 divides and extracts from the convex polygon a triangle enclosed by a line segment connecting the base vertex and the vertex immediately before the base vertex, a y-direction line segment extending from the vertex immediately before the base vertex to the center line segment, and a line segment connecting the intersection of the y-direction line segment with the center line segment and the leftmost point. Then, drawing data 2 is generated in which the vertices are arranged clockwise, and is stored in the storage device 144.

In the above example, the frontmost vertex and the farthest vertex in the +x direction in the coordinate system of the drawing data were identified, but this is not limiting. It is sufficient to identify the farthest vertex in the same direction as the frontmost vertex in either the +x direction or the -x direction in the coordinate system of the drawing data. Therefore, the central line segment is formed by connecting the leftmost point and the rightmost point that are one and the other of the vertices that are the farthest in the same direction as the frontmost vertex in either the +x direction or the -x direction in the coordinate system of the drawing data.

In the above example, a case was described in which the central line segment is formed by connecting the leftmost point and the rightmost point, which are one of the vertices that are the furthest in the same direction as the frontmost vertex in either the +x direction or the -x direction in the coordinate system of the drawing data, to the other, but this is not limited to this. The central line segment may also be formed by connecting the lowest point and the highest point, which are one of the vertices that are the furthest in the same direction as the frontmost vertex in either the +y direction or the -y direction in the coordinate system of the drawing data, to the other, to the other. For example, a case will be described in which the central line segment is formed by connecting the lowest point, which is the vertex that is the frontmost in the y direction in the coordinate system of the drawing data, to the highest point, which is the vertex that is the furthest from this lowest point in the +y direction. A specific explanation will be given below.

In this case, as a start point/furthest point identification step (S401), the start point/furthest point identification unit 270 reads out drawing data 1 of a convex polygon in which the coordinates of each vertex are defined in the order that constitutes the figure, stored, for example, in the memory 112 (storage device), and identifies the vertex that is the lowest point (start point) closest to the user in, for example, the y direction (another example of the first direction) in the convex polygon and the vertex that is the top point (furthest point) furthest in, for example, the y direction. Of the vertices defined in the drawing data 1, the vertex with the smallest y coordinate may be identified as the leftmost point, and the vertex with the largest y coordinate may be identified as the rightmost point.
In this example, the y direction is from bottom to top, but the y direction may be from top to bottom. In this case, the starting point is the uppermost point, and the farthest point is the lowermost point.

Figure 22 is a diagram illustrating another example of a convex polygon division method in embodiment 1. In Figure 22, for example, a 10-sided convex polygon with vertices 0 to 9 is shown. In the example of Figure 22, vertex 0 is the lowest point and vertex 5 is the highest point.

In the central line segment forming step (S402), the central line segment forming unit 272 forms a central line segment that bisects the convex polygon, connecting the lowest vertex closest to the front in the y direction and the furthest vertex from the lowest vertex in the y direction. In the example of Figure 22, a central line segment is formed that connects vertices 0 and 5.

In the base vertex setting step (S404), the base vertex setting unit 274 sets the next vertex of the vertex set as the base vertex in the n-1th base vertex setting process as the base vertex in the n-1th base vertex setting process. Alternatively, if there is no vertex set as the base vertex in the n-1th base vertex setting process, the next vertex of the leftmost point is set as the base vertex. In the first base vertex setting process, since there is no vertex set as the base vertex in the n-1th base vertex setting process, the base vertex setting unit 274 sets the vertex 1, which is the next vertex of the lowest vertex 0 on the nearest side in the y direction, as the base vertex. In other words, the base vertex setting unit 274 sets the vertex 1 next to the starting point in the order of the coordinates of each vertex 0 to 9 constituting the convex polygon (figure) defined in the drawing data 1, as the base vertex, starting from the lowest vertex 0 on the nearest side in the y direction. Here, a case is shown in which the vertices of each figure are defined in the drawing data 1 in the order in which the figure is constituted in a clockwise direction.

In the determination step (S408), the determination unit 283 determines whether the set base vertex is the topmost point (the farthest point) as the nth farthest point determination process. If the base vertex is not the topmost point, the process proceeds to the line segment formation step (S410). If the base vertex is the topmost point, the process proceeds to the figure extraction step (S416). In the first determination process, the base vertex is vertex 1, so it is determined that it is not vertex 5, which is the topmost point.

As the line segment formation step (S410), the line segment formation unit 276 forms a line segment that extends from the base vertex to the central line segment in parallel to the x direction (an example of the second direction) that is perpendicular to the y direction as the nth line segment formation process. In the first line segment formation process, a line segment that is parallel to the x direction from vertex 1 to the central line segment is formed.

As an intersection calculation step (S412), the intersection calculation unit 278 calculates the coordinates of the intersection between the center line segment and a line segment extending parallel to the x direction from the base vertex as the nth intersection calculation process.

As a figure extraction step (S414), the figure extraction unit 280 extracts multiple figures using any one of multiple preset reference figures from a convex polygon using a central line segment as the nth reference figure extraction process, and generates drawing data 2. From the convex polygon, it divides and extracts a figure surrounded by a line segment connecting the nth base vertex and the n-1th base vertex, an x-direction line segment extending from the nth base vertex to the central line segment, an x-direction line segment extending from the n-1th base vertex to the central line segment, and a part of a central line segment connecting the nth intersection of the x-direction line segment extending from the nth base vertex and the central line segment and the n-1th intersection of the x-direction line segment extending from the n-1th base vertex and the central line segment. Alternatively, if there is no x-direction line segment extending from the (n-1)th base vertex, a figure enclosed by a line segment connecting the nth base vertex and the vertex immediately preceding the nth base vertex, an x-direction line segment extending from the nth base vertex to the center line segment, and a portion of the center line segment connecting the vertex immediately preceding the nth base vertex and the nth intersection point of the x-direction line segment extending from the nth base vertex and the center line segment is divided and extracted from the convex polygon. In the first figure extraction process, since there is no n-1th base vertex, a triangle enclosed by a line segment 0-1 connecting vertex 1, which is the first base vertex, and vertex 0 immediately preceding vertex 1, an x-direction line segment extending from vertex 1 to the center line segment, and a portion of the center line segment connecting vertex 0 and the intersection point of the x-direction line segment extending from vertex 1 and the center line segment is divided and extracted from the convex polygon. Here, drawing data 2 is generated in which the coordinates of vertex 0, vertex 1, and the coordinates of the intersection between the x-direction line segment extending from vertex 1 and the center line segment are arranged, for example, in a clockwise direction. The generated drawing data 2 is stored in the storage device 144.

In the figure extraction step (S416), as one of the nth reference figure extraction processes, when the base vertex is the uppermost point, the figure extraction unit 281 divides and extracts from the convex polygon a triangle enclosed by a line segment connecting the base vertex and the vertex immediately before the base vertex, an x-direction line segment extending from the vertex immediately before the base vertex to the center line segment, and a line segment connecting the intersection of the x-direction line segment with the center line segment and the uppermost point. Then, drawing data 2 is generated in which each vertex is arranged clockwise, and is stored in the storage device 144.

In the adjacent point identification process (S420), the adjacent point identification unit 282 identifies the next vertex adjacent to the base vertex as an adjacent point in the n-th adjacent point identification process. In the first adjacent point identification process, vertex 2 is the adjacent point.

In the determination step (S422), the determination unit 284 determines whether the identified adjacent point is the lowest point that will be the starting point as the nth start point determination process. If the identified adjacent point is the lowest point that will be the starting point, the process proceeds to the final figure extraction step (S424). If the identified adjacent point is not the lowest point that will be the starting point, the process returns to the base vertex setting step (S404) and repeats each step from the base vertex setting step (S404) to the determination step (S422) until the identified adjacent point is the lowest point that will be the starting point.

As a result, the remaining vertices except for the lowest vertex and the highest vertex are set as base vertices in order, and line segments parallel to the x direction and perpendicular to the y direction are formed from the base vertices to the center line segment. Then, the coordinates of the intersection of the x direction line segment extending from the base vertex and the center line segment are calculated.
Then, a reference figure having a line segment in the x direction as one side is extracted. Therefore, the extracted reference figures each include a side extending in the x direction in the coordinate system of the drawing data.

For example, in the second reference figure extraction process, a trapezoid surrounded by an x-direction line segment extending from vertex 2 to the center line segment, an x-direction line segment extending from vertex 1 to the center line segment, line segment 1-2 connecting vertex 1 and vertex 2, and a line segment connecting the intersection of the x-direction line segment extending from vertex 2 with the center line segment and the intersection of the x-direction line segment extending from vertex 1 with the center line segment is extracted as one of multiple preset reference figures, and drawing data 2 is generated. Then, in the second adjacent point identification process, vertex 3, which is adjacent to vertex 2, the base vertex, is identified as an adjacent point. Thereafter, such operations are repeated.

For example, in the ninth reference figure extraction process, a trapezoid surrounded by an x-direction line segment extending from vertex 9 to the center line segment, an x-direction line segment extending from vertex 8 to the center line segment, a line segment 9-8 connecting vertex 9 and vertex 8, and a line segment connecting the intersection of the x-direction line segment extending from vertex 9 with the center line segment and the intersection of the x-direction line segment extending from vertex 8 with the center line segment is extracted as one of multiple preset reference figures, and drawing data 2 is generated. Then, in the ninth adjacent point identification process, vertex 0, which is the next point adjacent to vertex 0, the base vertex, is identified as the adjacent point. Because vertex 0 is the starting point, the process proceeds to the final figure extraction step (S424).

In the final figure extraction step (S424), when the base vertex is the lowest point, the figure extraction unit 286 divides and extracts from the convex polygon a triangle enclosed by a line segment connecting the base vertex and the vertex immediately before the base vertex, an x-direction line segment extending from the vertex immediately before the base vertex to the center line segment, and a line segment connecting the intersection of the x-direction line segment with the center line segment and the lowest point. Then, drawing data 2 is generated in which each vertex is arranged clockwise, and is stored in the storage device 144.

According to the convex polygon division processing step (S400), the base vertex is shifted from the start point of the convex polygon toward the farthest point and from the farthest point toward the start point for each vertex on the opposite side of the central line segment, so that the creation of a vertex list and the vertex sorting process are unnecessary. In addition, the side that intersects with the line segment extending from the base vertex in the y direction (or x direction) becomes the central line segment, so that the creation of a line segment list and the line segment sorting process are unnecessary. Furthermore, in the case of a convex polygon, the opposite side is only the central line segment, so the opposite side needs to be found only once. Therefore, the processing time for dividing a convex polygon can be significantly reduced compared to the case where the general polygon division processing method (S110) is used. In the general polygon division processing method (S110), when the number of vertices is n, the amount of calculation is generally larger than O(n), whereas the convex polygon division processing step (S400) can reduce the amount of calculation to O(n).

In the above example, the reference figures are extracted in sequence from the start point of the convex polygon toward the farthest point, and from the farthest point toward the start point for each vertex on the opposite side of the central line segment, but this is not limited to the above. Reference figures may also be extracted in sequence from both the start point and the farthest point of the convex polygon toward the center in the direction in which the start point and the farthest point are identified. Alternatively, the base vertices may be shifted in sequence in the same direction for each vertex on both sides of the central line segment.

When generating shot data, which will be described later, a rasterization process (conversion to pixel data) is performed. In this rasterization process, when determining the start and end points of pixels with gradation values on one pixel line, if the input figure is complex, the process also becomes complex. For this reason, in the first embodiment, the polygon is divided into reference figures before processing. In this case, a figure with as few diagonal lines as possible can be processed more efficiently. In the first embodiment, a line segment extending in the x or y direction constitutes at least one side of the figure, so the shot data generation process can be carried out efficiently.

As described above, drawing processing is performed using drawing data 2, which is obtained by dividing drawing data 1, which includes polygons, into reference shapes.

23 is a conceptual diagram for explaining an example of the writing operation in the embodiment 1. As shown in Fig. 23, the position of a writing region 30 (bold line) of the sample 101 is defined based on the position of the alignment mark 14.
The writing area 30 (bold line) is virtually divided into a plurality of rectangular stripe areas 32 with a predetermined width in the y direction, for example. The example of Fig. 23 shows a case where the writing area 30 of the sample 101 is divided into a plurality of stripe areas 32 with a width size substantially equal to the size of a designed irradiation area 34 (writing field) that can be irradiated by one irradiation of the multibeam 20, for example, in the y direction. The size in the x direction of the designed irradiation area 34 of the multibeam 20 can be defined by the number of beams in the x direction x the beam pitch in the x direction. The size in the y direction of the rectangular irradiation area 34 can be defined by the number of beams in the y direction x the beam pitch in the y direction.

First, the XY stage 105 is moved and adjusted so that the irradiation area 34 of the multi-beam 20 is positioned at the left end of the first stripe region 32, or further to the left, and the first stripe region 32 is drawn. When drawing the first stripe region 32, the XY stage 105 is moved, for example, in the -x direction, so that drawing proceeds relatively in the x direction. The XY stage 105 is moved continuously, for example, at a constant speed. After drawing the first stripe region 32 is completed, the stage position is moved in the -y direction by an amount equal to the width of the stripe region 32.

Then, the irradiation area 34 of the multi-beam 20 is adjusted to be located at the left end of the second stripe area 32, or at a position further to the left, and the XY stage 105 is moved, for example, in the -x direction, so that drawing proceeds relatively in the x direction, thereby drawing the second stripe area 32.

In the example of FIG. 23, the drawing of each stripe region 32 proceeds in the same direction, but this is not limited to this. For example, the next stripe region 32 to be drawn after the stripe region 32 drawn in the x direction may be drawn in the -x direction by moving the XY stage 105 in the x direction, for example. By drawing while alternating directions in this way, the stage movement time can be shortened, and thus the drawing time can be shortened. In one shot, the multi-beam 20 formed by passing through each hole 22 in the shaping aperture array substrate 203 forms multiple shot patterns at once, up to the same number as each hole 22.

In the example of FIG. 23, the stage is moved once for the drawing process of each stripe region, but this is not limited to the above. It is also preferable to perform multiple drawing by moving the stage multiple times over the same position. In this case, it is preferable to perform multiple drawing while shifting the stage in the y direction by an amount that is 1/n of the width of the stripe region, for example.

24 is a diagram showing an example of the irradiation area of the multibeam and the pixel to be drawn in the first embodiment. In FIG. 24, the stripe area 32 is divided into a plurality of mesh areas in a mesh shape by the beam size of the multibeam 20, for example. Each of these mesh areas becomes the pixel 36 to be drawn (unit irradiation area, irradiation position, or drawing position). The size of the pixel 36 to be drawn is not limited to the beam size, and may be any size regardless of the beam size. For example, it may be configured with a size of 1/n (n is an integer equal to or greater than 1) of the beam size. In the example of FIG. 24, the drawing area of the sample 101 is divided into a plurality of stripe areas 32 with a width size substantially the same as the size of the irradiation area 34 (drawing field) that can be irradiated by one irradiation of the multibeam 20, for example, in the y direction. The size of the rectangular irradiation area 34 in the x direction can be defined by the number of beams in the x direction x the beam pitch in the x direction. The size of the rectangular irradiation area 34 in the y direction can be defined by the number of beams in the y direction x the beam pitch in the y direction. In the example of FIG. 24, for example, a 512×512 array of multi-beams is shown in an abbreviated form to an 8×8 array of multi-beams. A plurality of pixels 28 (beam drawing positions) that can be irradiated with one shot of the multi-beam 20 are shown within the irradiation area 34. The pitch between adjacent pixels 28 is the pitch between each beam of the multi-beam. A rectangular area surrounded by the size of the beam pitch in the x and y directions constitutes one sub-irradiation area 29 (pitch cell). In the example of FIG. 24, each sub-irradiation area 29 is shown to be composed of, for example, 4×4 pixels.

As a shot data generation process, first, the shot data generation unit 70 generates shot data for each pixel 36. Specifically, it operates as follows. First, the shot data generation unit 70 reads the drawing data 2 from the storage device 144, and calculates the pattern area density ρ' within each pixel 36 for each pixel 36. This process corresponds to a rasterization process, and is executed, for example, for each stripe region 32.

Next, the shot data generation unit 70 first virtually divides the drawing area (here, for example, the stripe area 32) into a plurality of proximity mesh areas (mesh areas for calculating proximity effect correction) of a predetermined size in a mesh shape. The size of the proximity mesh area is preferably set to about 1/10 of the range of influence of the proximity effect, for example, about 1 μm. The shot data generation unit 70 reads the drawing data 2 from the storage device 144, and calculates, for each proximity mesh area, the pattern area density ρ″ of the pattern to be placed within that proximity mesh area.

Next, the shot data generation unit 70 calculates a proximity effect correction irradiation coefficient Dp(x) (corrected dose) for correcting the proximity effect for each proximity mesh region. The unknown proximity effect correction irradiation coefficient Dp(x) can be defined by a threshold model for proximity effect correction similar to the conventional method, using the backscattering coefficient η, the dose threshold Dth of the threshold model, the pattern area density ρ", and the distribution function g(x).

Next, the shot data generation unit 70 calculates the incident irradiation amount D(x) (dose amount) for irradiating each pixel 36. The incident irradiation amount D(x) may be calculated, for example, as a value obtained by multiplying the base irradiation amount Dbase by the proximity effect correction irradiation coefficient Dp and the pattern area density ρ'. The base irradiation amount Dbase can be defined, for example, as Dth/(1/2 + η). In this way, the incident irradiation amount D(x) for each pixel 36 with the proximity effect corrected based on the layout of the multiple graphic patterns defined in the drawing data can be obtained.

Next, the shot data generation unit 70 calculates the irradiation time for each pixel 36. The irradiation time for each pixel 36 can be calculated by dividing the incident irradiation amount D(x) of the pixel by the current density J.

As a data processing step, the data processing unit 72 rearranges the obtained irradiation time data for each pixel 36 in shot order and stores it in the storage device 142. The transfer processing unit 74 transfers the irradiation time data to the deflection control circuit 130 in shot order.

In the drawing process, under the control of the drawing control unit 76, the drawing mechanism 150 draws a pattern on the sample 101 on the XY stage 105 using the multi-beam 20 while moving the XY stage 105. In multi-beam drawing, while the drawing process is being performed, shot data for the area to be subjected to the drawing process later is generated in parallel. For example, while drawing the kth stripe area 32, shot data for the k+2th stripe area 32 is generated in parallel. By repeating this operation, drawing is performed on all stripe areas 32.

Figure 25 is a diagram for explaining an example of a multi-beam drawing operation in embodiment 1. The example of Figure 25 shows a case where drawing is performed with four different beams in each sub-irradiation area 29 that includes one beam irradiation position of each of the multi-beams 20 and is surrounded by the inter-beam pitch. The example of Figure 25 also shows a drawing operation in which the XY stage 105 moves continuously at a speed that moves a distance of, for example, two beam pitches while drawing an area of 1/4 (one of the number of beams used for irradiation) in each sub-irradiation area 29. The example of Figure 25 shows a case where each sub-irradiation area 29 is composed of, for example, 4 x 4 pixels.

In the drawing operation shown in the example of FIG. 25, for example, while the XY stage 105 moves a distance of two beam pitches in the x direction, the deflector 209 shifts the irradiation position (pixel 36) in sequence, and four shots of the multi-beam 20 are shot in the shot cycle T to draw (expose) four different pixels 36 in the same sub-irradiation area 29. While drawing (exposing) these four pixels 36, the deflector 208 deflects the entire multi-beam 20 collectively so that the relative position of the irradiation area 34 to the sample 101 does not shift due to the movement of the XY stage 105, thereby making the irradiation area 34 follow the movement of the XY stage 105. In other words, tracking control is performed. When one tracking cycle is completed, tracking is reset and the device returns to the previous tracking start position. Since the drawing of the first pixel row from the left in each sub-irradiation region 29 has been completed, after the tracking reset, in the next tracking cycle, the deflector 209 first deflects to align (shift) the drawing position of the beam different from the first pixel row so as to draw an undrawn pixel row, for example the second pixel row from the left, in each sub-irradiation region 29. By repeating this operation while drawing the stripe region 32, the position of the irradiation region 34 (34a to 34o) of the multi-beam 20 moves in sequence as shown in the lower diagram of FIG. 23, and drawing is performed.

As described above, according to the first embodiment, the time required for the division process to divide a polygon into reference shapes can be reduced. This reduces the drawing time.

Although the embodiments have been described above with reference to specific examples, the present invention is not limited to these specific examples.
Furthermore, the processing described in the first embodiment may be executed by a computer. A program for causing a computer to execute such processing may be stored in a non-transitory, tangible, readable recording medium, such as a magnetic disk device.

In addition, although the description of the device configuration, control method, and other parts that are not directly necessary for the explanation of the present invention have been omitted, the required device configuration and control method can be appropriately selected and used. For example, although the description of the control unit configuration that controls the drawing device 100 has been omitted, it goes without saying that the required control unit configuration can be appropriately selected and used.

All other drawing data generation methods, drawing data generation devices, charged particle beam drawing devices, and programs that incorporate the elements of the present invention and that can be modified as appropriate by a person skilled in the art are included within the scope of the present invention.

20 Multi-beam 22 Hole 24 Control electrode 25 Passage hole 26 Counter electrode 29 Sub-irradiation area 30 Drawing area 31 Blanking aperture array substrate 32 Stripe area 34 Irradiation area 36 Pixel 41 Control circuit 50 Shape determination processing unit 52 X-monotonic polygon division processing unit 54 Y-monotonic polygon division processing unit 56 Convex polygon division processing unit 57 General polygon division processing unit 60 Vertex list creation unit 61 Line segment list creation unit 62 Vertex sorting processing unit 63 Line segment sorting processing unit 64 Straight line formation unit 65 Intersection calculation unit 66 Figure extraction unit 70 Shot data generation unit 72 Data processing unit 74 Transfer processing unit 76 Drawing control unit 80 Division processing unit 100 Drawing device 101 Sample 102 Electron lens column 103 Drawing chamber 105 XY stage 110 Control computer 112 Memory 130 Deflection control circuits 132, 134 DAC amplifier unit 136 Lens control circuit 138 Stage control mechanism 139 Stage position measurement device 140, 142 Memory device 150 Drawing mechanism 160 Control system circuit 170 Start point/final point identification unit 171 Previous point/next point setting unit 172 Coordinate comparison unit 173 Coordinate comparison unit 174 Base vertex setting unit 175 Opposite vertex setting unit 176 Line segment formation unit 178 Intersection calculation unit 180 Figure extraction unit 181 Figure extraction unit 182 Adjacent point identification unit 184 Determination unit 200 Electron beam 201 Electron gun 202 Illumination lens 203 Shaping aperture array substrate 204 Blanking aperture array mechanism 205 Reduction lens 206 Limiting aperture substrate 207 Objective lens 208 Deflector 209 Deflector 210 Mirror 270 Start point/farthest point identification unit 272 Central line segment forming section 274 Base vertex setting section 276 Line segment forming section 278 Intersection calculation section 280 Figure extraction section 281 Figure extraction section 282 Adjacent point identification section 283 Determination section 284 Determination section 286 Figure extraction section 330 Membrane region

Claims (8)

A step of reading out rendering data of a convex polygon, the rendering data being stored in a storage device and defined in the order in which the coordinates of the vertices form a figure, and projecting the convex polygon onto a line segment drawn in a first direction to identify two vertices that are most distant from each other;
forming a median line segment that bisects the convex polygon connecting the two most distant vertices;
extracting a plurality of figures using any one of a plurality of preset reference figures from the convex polygon using the central line segment, and generating drawing data;
A drawing data generating method comprising: a step of sequentially setting the remaining vertices, except for the two vertices that are the furthest from each other in the first direction, as base vertices, and forming, for each base vertex, a line segment that is parallel to a second direction perpendicular to the first direction from the base vertex to the central line segment;
calculating, for each of the base vertices, coordinates of an intersection between the line segment extending from the base vertex and the center line segment;
2. The drawing data generating method according to claim 1, further comprising: The drawing data generation method according to claim 1, wherein the first direction is one of the +x direction, -x direction, +y direction, and -y direction in the coordinate system of the drawing data. The drawing data generation method according to claim 1, wherein the extracted figures include sides extending in the x-direction or y-direction in the coordinate system of the drawing data. The storage device stores rendering data for a plurality of polygons,
reading out rendering data of the plurality of polygons from the storage device, and determining, for each polygon, a shape type of the polygon;
2. The drawing data generating method according to claim 1, wherein when the result of the determination is that the polygon is a convex polygon, each of the steps according to claim 1 is carried out. a storage device for storing drawing data of a convex polygon in which the coordinates of each vertex are defined in the order that the polygon is formed;
a specification unit that reads out rendering data of a convex polygon, the rendering data being stored in the storage device and defined in the order in which the coordinates of the vertices form a figure, and projects the convex polygon onto a line segment drawn in a first direction to specify two vertices that are most distant from each other;
a central line segment forming portion that forms a central line segment that bisects the convex polygon connecting the two most distant vertices;
an extraction processing unit that uses the central line segment to extract a plurality of figures using any one of a plurality of preset reference figures from the convex polygon, and generates drawing data;
A drawing data generating device comprising: a storage device for storing drawing data of a convex polygon in which the coordinates of each vertex are defined in the order that the polygon is formed;
a specification unit that reads out rendering data of a convex polygon, the rendering data being stored in the storage device and defined in the order in which the coordinates of the vertices form a figure, and projects the convex polygon onto a line segment drawn in a first direction to specify two vertices that are most distant from each other;
a central line segment forming portion that forms a central line segment that bisects the convex polygon connecting the two most distant vertices;
an extraction processing unit that uses the central line segment to extract a plurality of figures using any one of a plurality of preset reference figures from the convex polygon, and generates drawing data;
a writing mechanism for writing, on a sample, a pattern of the plurality of figures, for which writing data has been generated, using a charged particle beam;
A charged particle beam drawing apparatus comprising: a function of reading out rendering data of a convex polygon, the rendering data being stored in a storage device and defined in the order in which the coordinates of the vertices form a figure, and projecting the convex polygon onto a line segment drawn in a first direction to identify the two vertices that are furthest apart;
forming a median line segment that bisects the convex polygon connecting the two most distant vertices;
a function of extracting a plurality of figures using any one of a plurality of preset reference figures from the convex polygon by using the central line segment, and generating drawing data;
A program for causing a computer to execute the following.

Images