JP3109585B2 - Method and apparatus for generating three-dimensional object data, and recording medium storing program for generating three-dimensional object data - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method and apparatus for generating three-dimensional object data and a recording medium on which a program for generating three-dimensional object data is recorded. ,
The present invention relates to a method and an apparatus for generating a three-dimensional object data by constructing a mesh, which is a set of triangles constituting the surface of a three-dimensional object, and a recording medium storing a program for generating the three-dimensional object data.

[0002]

2. Description of the Related Art When generating three-dimensional object data from two-dimensional contour data of characters and figures, it is necessary to divide an area surrounded by the contour into a plurality of triangles. A conventional example of this method is disclosed in Japanese Patent Application Laid-Open No. 7-72847 (hereinafter, referred to as Document 1).
Simple Polygons and Equivalent Problems ”, Ala
n Fournier and, Delfin Y. Montuno, ACM Transa
ctions of Graphics, Vol.3, No.2, April 1984 p
A technique described in p.153-174 (hereinafter referred to as reference 2) is known.

In the method described in Document 1, an area surrounded by two-dimensional contour data is regarded as a polygon, the polygon is divided into a large number of triangles, and input to a drawing device to display an image. Etc. are drawn at high speed on a display device.

In the technique described in Document 2, an area surrounded by contour data is divided by parallel lines, and an area inside the contour is divided by a number of trapezoids formed by the parallel lines and a part of the contour. A method is described. By dividing the trapezoid obtained here into triangles, character and graphic data can be divided into triangles.

[0005]

The examples of these conventional techniques are intended only to paint a region surrounded by contour data, and do not consider three-dimensionalization. It is also applied when the contour has a self-intersection.
However, in order to generate three-dimensional object data from a contour line, it is necessary to have a condition that the contour line does not cross the inside of the divided triangle, and there is a problem in that self intersection must be removed. When a conventional method is used to generate a three-dimensional image from crossed contour data, a portion where the divided triangles overlap each other occurs.

Further, when triangulation is performed by the conventional method, three line segments constituting one triangle are compared with all line segments on a contour line which does not constitute the triangle, and the triangle is determined by the contour. Since it is determined that the triangle is an effective triangle included in the area inside the line, the number of line segment intersection determinations increases as the square of the number of vertices as the number of vertices increases.

An object of the present invention is to reconstruct a contour having self-intersection into a contour having no self-intersection, thereby dividing the inside of the contour into a number of non-overlapping triangles, and extending the contour into a columnar shape. It is an object of the present invention to provide a method and an apparatus for generating three-dimensional object data, and a recording medium on which a program for generating three-dimensional object data is recorded.

[0008]

In order to achieve the above object, according to the present invention, there is provided a contour storage means for storing contour data, and whether data acquired from the contour storage means intersects itself. Contour analysis means for analysis, intersection storage means for storing the intersection when self-intersecting, and contour reconstructing means for correcting the contour data to self-intersection when self-intersecting Effective contour storage means for receiving and storing contours that do not intersect themselves from the contour analysis means and the contour reconstruction means, and acquiring vertex data from the contour analysis means and the contour reconstruction means, Vertex aligning means for aligning, aligned vertex storing means for storing aligned vertices output from the vertex aligning means, and vertex selection for selecting and storing three vertices from the effective contour line storing means It is determined whether or not the triangle formed by the three vertices stored in the vertex selecting means is a triangle included in the outline by using the step and the aligned vertex data stored in the aligned vertex storing means. Effective triangle determining means, effective triangle storing means for storing triangles determined to be valid by the effective triangle determining means, and upper and lower surfaces of a mesh which forms a surface of a three-dimensional object by a set of triangles. A mesh representing a columnar three-dimensional object is constructed by using contour data excluding the self-intersection of the upper surface and the lower surface on the side surface.

[0009]

Embodiments of the present invention will be described below in detail with reference to the drawings. FIG. 1 is a block diagram showing an embodiment of the configuration of the present invention.

Referring to FIG. 1, in the configuration of the present invention in the present embodiment, a contour storage unit 101 for storing contour data and contour data obtained from the contour storage unit 101 intersect with each other. A contour analysis unit 102 for analyzing whether or not there is a self-intersection, an intersection storage unit 111 for storing the intersection when the self-intersection is performed, and a contour having no self-intersection when the contour data is self-intersecting. A contour reconstruction unit 103; an effective contour storage unit 106 for receiving and storing contours that do not intersect themselves from the contour analysis unit 102 and the contour reconstruction unit 103;
2, a vertex aligning unit 104 for acquiring and aligning vertex data from the contour reconstructing unit 103;
4, a sorted vertex storage unit 105 that stores the sorted vertices output from step 4, a vertex selection unit 107 that selects and stores three vertices from the effective contour line storage unit 106, and a stored in the sorted vertex storage unit 105. Using the sorted vertex data, the valid triangle determining unit 108 that determines whether the triangle formed by the three vertices stored in the vertex selecting unit 107 is a triangle included in the contour, An effective triangle storage unit 109 that stores triangles determined to be valid by the triangle determination unit 108, and upper and lower surfaces of a mesh that configures the surface of a three-dimensional object with a set of triangles.
A three-dimensional object data constructing unit 110 is constructed that constructs a mesh representing a columnar three-dimensional object by using the contour data obtained by constructing the obtained effective triangle and excluding the self-intersection of the upper surface and the lower surface from the side surface. .

The embodiment of the present invention configured as described above will be described in more detail with reference to FIGS.

In order to achieve the object, the present invention holds pointer structure data, vertex structure data, and intersection structure data.

FIG. 2 is a diagram showing pointer structure data which plays a role in maintaining the connection of contour data. A sequential access pointer for constructing a one-way list and a position acquisition pointer for acquiring its own vertex coordinates are shown. Consists of

FIG. 3 is a diagram showing the vertex structure data, which is composed of vertex coordinates indicating the position of each vertex of the contour data and the pointer structure data shown in FIG.

FIG. 4 is a diagram showing intersection structure data representing information on intersections generated by self-intersection. The intersection structure data has one vertex coordinate indicating the intersection position, two pointer structure data, and two route cost data. Here, the route cost data is the number of vertices that pass when tracing the contour from the intersection held by the intersection structure data and reaching the next intersection of self-intersection.

FIG. 5 is a diagram showing the relationship between the outline of a character and the vertex structure. In this drawing, the outline is constituted by a connected vertex structure, and indicates that the next vertex can be sequentially accessed by a pointer structure included in the vertex structure.

FIG. 6 is a diagram for explaining the process of listing intersections in the contour analysis unit 102.

FIG. 7 shows an example of a flow showing the operation of the contour analysis unit 102.

FIG. 8 shows an example of an intersection structure obtained as a result of performing intersection enumeration processing on the outline of FIG. 6 in the outline analysis unit 102 and stored in the intersection storage unit 111.

FIG. 9 shows the outline reconstruction unit 103
FIG. 7 is a diagram for explaining reconstruction of a mutual closed curve found in the outline of FIG. 6.

FIG. 10 shows an example of a flow in which the contour reconstruction unit 103 receives the intersection structure and obtains a self-closed curve or a mutually closed curve.

FIG. 11 shows the outline analysis unit 102
An example of a self-closed curve in which a self-intersection is detected and the contour reconstruction unit 103 performs reconstruction is shown.

FIG. 12 shows an example of a flow when the contour reconstructing unit 103 reconstructs a self-closed curve using one intersection structure.

FIG. 13 shows an example of a flow in the case where the contour reconstruction unit 103 reconstructs a mutual closed curve using two intersection structures.

FIG. 14 shows an example in which the effective triangle judging section 108 determines whether or not the triangle composed of the three vertices received from the vertex selecting section 107 is an effective triangle.

FIG. 15 shows a flow in which the effective triangle judging section 108 judges whether or not a triangle composed of three vertex coordinates received from the vertex selecting section 107 is satisfied as a triangle constituting an area inside the contour. An example is shown.

FIG. 16 is a diagram showing an example in which the present invention is applied to contour data having a self-intersection of Hiragana "A".

Here, an operation of generating three-dimensional object data from the contour data shown in FIG. 6A using the present invention will be described.

FIG. 6A shows data in which the area to the right becomes the inside of the contour when the contour is traced clockwise, and is composed of 25 vertices.

First, the intersection enumeration process will be described.

The contour storage unit 101 stores 25 pieces of contour data holding the positions of vertices 0 to 24 and their order. This data is stored in the contour analysis unit 102
Is forwarded to

The contour analyzing unit 102 selects a basic line segment from the received contour data, and determines intersection with all the line segments on the contour. This will be described with reference to FIG.

In FIG. 6- (b), a line segment composed of a vertex 0 and a vertex 1 is defined as a basic line segment. The first line segment to be compared with this basic line segment is a line segment composed of vertices 2 and 3. It is determined whether or not the basic line segment and the comparison line segment intersect. If they do not intersect, then the line segment formed by the vertices 3 and 4 is determined as the comparison line segment. This is repeated until the comparison line segment becomes a line segment composed of the vertices 23 and 24. In FIG. 6- (b), 0,
It can be seen that the basic line segment constituted by 1 does not intersect with any other line segment.

Next, the basic line segment is replaced with a line segment composed of vertices 1 and 2. Similarly, it is sequentially determined whether or not the comparison line segment intersects the basic line segment. With this operation, it is possible to determine whether or not there is a self-intersection on the contour line.

In FIG. 6C, the basic line segment is composed of vertices 5 and 6. Vertex 18 and vertex 19
In this case, since these two straight lines intersect, the intersection structure data is generated and registered in the intersection storage unit 111. For the sake of explanation, this intersection is referred to as a vertex P. Information shown in FIG. 8A is set in the intersection structure data. However, the path cost is not set at this time, but is set at the end of the process of listing the intersections of the contour lines. In addition, two elements of the vertex structure are added to the list of vertex structures forming the contour by newly inserting a vertex structure having the coordinate value of the intersection between each line segment generating the intersection. .

In FIG. 6- (d), an intersection is found in the same manner as in FIG. 6- (c), and this intersection is referred to as an intersection Q for explanation. When the state shown in FIG. 6- (e) is reached, the investigation of the intersection enumeration ends.

Next, all the intersection structures in the intersection storage unit 111 are compared with the coordinate value data in the intersection storage device, and the path cost between the intersections is calculated. Two path costs are set for one intersection.

In the case of FIG. 6, the route cost at the intersection P is P-6.
―7-8-Q and the cost via 4, P-19-20-
値 Two values of -5-P and the cost 13 to be passed are set. In addition to the intersection enumeration, the vertex aligning unit 104 aligns the y-coordinates of all vertices constituting the contour and registers them in the aligned vertex storage unit 105.

FIG. 7 shows an example of a flow in which the intersection enumeration processing in FIG. 6 is performed.

In the drawing, s and t represent the starting points of the basic line segment and the comparison line segment, respectively, and L1 and L2 are the basic line segment and the comparison line segment, respectively. The basic line segment L1 is composed of a vertex s and a vertex s + 1,
The comparison line segment L2 includes a vertex t and a vertex t + 1. n
Is the number of vertices included in the contour.

Each line segment is set in step S72, and an intersection is determined in step S73. If the intersection exists, the coordinates are obtained and the intersection structure data is stored in the intersection storage device in step S74.

In steps S75, S76, S77, and S71, the intersection can be determined for all the line segments on the contour line.

In steps S78 and S80, vertex alignment processing is performed, and in step S79 a path cost is calculated. Here, the alignment processing is performed on the y coordinate of the vertex, but may be performed on the x coordinate.

Next, a process for generating a contour line having no self-intersection will be described. In order to generate a contour line without self-intersection from the enumerated intersections, the registered intersection structure data is combined. One intersection structure data is acquired in the order registered in the intersection storage unit 111, and a pointer structure having a low path cost is selected. In FIG. 8A, the one with the smaller path cost is the pointer to the vertex 6, so that FIG.
In (a), the vertices after the vertex 6 are sequentially accessed with P as a starting point, this operation is continued until the next intersection, and the intersection structure data at that time is acquired. In FIG. 9- (b), since the vertex Q is the next intersection, from the intersection structure data of the self-intersection intersection Q in FIG.
7 is obtained and the direction of the route is changed.

In this case, since the position of the vertex P and the position of the vertex Q are different, this path becomes a part of the area surrounded by the mutual closed curve. A mutual closed curve is a closed curve surrounded by two parts of the contour.

It is determined whether the direction of tracing the mutual closed curve thus obtained in ascending vertex order is clockwise or counterclockwise. If it is clockwise, since the area surrounded by the closed curve is an internal area to be triangulated, it becomes a target of a route change, and a route reconstruction described later is performed. If the area is counterclockwise, since the area is an external area, the path is not changed and the structure of the self-intersection P is referred to, and the same processing is performed from FIG.

In FIG. 9, since the direction of the mutual closed curve is clockwise, it becomes an object of the route change.

The set of intersection structure data or one set of intersection structure data that has been subjected to the route change is deleted from the intersection storage unit 111. If the intersection structure data remains in the intersection storage unit 111, the above processing is continued until the intersection storage unit 111 has no more intersection structure data.

In the case of a mutually closed curve, there are two paths for moving from the intersection structure data to the other intersection structure data, and the path having the higher moving cost following the path is deleted. Here, the movement cost is specifically set to the number of vertices included in the route, but another cost calculation method such as smoothness of the route may be introduced.

In FIG. 9- (d), the route P-6-7-8-
Since the cost of the route Q-17-18-P is lower than that of Q, the former route is deleted and the route P-18-17-Q is inserted instead of the route P-6-7-8-Q. .

In FIG. 9, particularly regarding the example of the mutual closed curve,
After reconstructing, the self-closed curve shown in FIG.
The reconstruction of the contour data can be performed by the flow shown in FIG.

In the above method, the contour line 0-1--2--4--4-5-P-18-17-Q-9-1 from which self-intersection is eliminated.
0-11-12-13-14-15-16-Q-17-
18-P-19-20-21-22-23-24 is obtained.

FIGS. 10, 12, and 13 show the outline reconstructing unit 1.
It is an example of the flow showing the operation of No. 03.

FIG. 10 shows a process of following the path from the acquisition of the intersection structure data to the next intersection.

FIG. 12 is a detailed flow of the self-closed curve processing of FIG. 10, and FIG. 13 is a detailed flow of the mutual closed curve processing of FIG.

In the figure, A and B indicate two pointer structure data of the intersection structure data, and it is assumed that A is a pointer structure having a smaller path cost. d is the vertex pointed by the sequential access pointer of A, and k is the intersection storage unit 11
Pointing to the intersection structure data stored in No. 1.

In order to find the intersection Q in FIG. 9- (b), it is determined in step S05 whether the vertex d is equal to the position of the intersection structure data Q. Step S05, Step S
It is determined whether the vertex d is an intersection by repeating steps S06 and S09. If the vertex d is not an intersection, step S0
7. It is determined whether the next vertex is an intersection by processing step S04.

In FIG. 9- (c), the process of searching for the route of Q-17-18-P is performed in steps S21 and S21 of FIG.
Step 22 is performed in step S23.

In FIG. 9- (d), the process for deleting the route is as follows.
Steps S27, S28, and S in FIG.
Perform at 29.

Next, a process of dividing the obtained contour data having no self-intersection into triangles will be described.

The vertices forming the triangle are denoted as A, B, and C, and these three points select vertices that are continuous on the contour. As shown in FIG. 14A, first, vertices 0, 1,
2 is selected. In this figure, since these three points are clockwise and are a part of the inside region of the contour, the triangulation is successful. Successful three vertices are registered in the effective triangle storage unit 109, and vertex 1 is removed from the effective contour. Fig. 14-
After the division in (a), it is determined whether the vertices 0, 2, and 3 are valid triangles.

When the triangulation is successful, the second vertex B is deleted, the vertex C is newly set as the vertex B, and the next point after the vertex C is set as the new vertex C, and the same processing is performed.

FIGS. 14 (b) and (c) show a case where the triangulation fails.

In FIG. 14- (b), triangulation fails because the vertices on the contour line are included in the triangle 0-3-4. In FIG. 14- (c), the triangle 14-15-16 is Triangulation fails because of clockwise configuration.

If the triangulation fails, each vertex is replaced with the next point on the contour line, and the valid three triangles are again determined as valid triangles.

This process is performed recursively, and when the number of vertices of the contour line data becomes three, the triangle composed of the three points is registered in the effective triangle storage unit 109 and the processing is terminated.

If the triangulation shown in FIG. 14- (a) is successful, the processing of steps S48, S49 and S51 of FIG. 15 is performed. If the division of FIG. 14- (b) fails, steps S46 and S5 in FIG.
0 processing is performed. If it fails in FIG. 14- (c), the processing of steps S41 and S42 in FIG. 15 is performed.

Whether the triangle extracted by the triangle construction is included in the region inside the contour can be replaced by the problem of whether or not a point on the contour exists inside the triangle. Is obtained in step S43 in FIG. 15 and only the vertices existing in this range are selected from the sorted vertex storage unit 105 and the determination is performed. Therefore, the calculation amount can be significantly reduced and the triangle construction can be performed at high speed.

In the embodiment of the present invention, data is assumed such that, when the contour is traced clockwise, the area on the right side is inside the contour. However, the present invention is not limited to this. Instead, it can be processed even in a counterclockwise direction. In this case, the criterion “clockwise” in the closed curve processing and the triangulation processing is “counterclockwise”.

Finally, the three-dimensional object data constructing unit 110 constructs the upper and lower surfaces of the three-dimensional data object from the triangles stored in the effective triangle storage unit 109 and stores them in the effective contour line storage unit 106. Three-dimensional object data is generated by forming a side surface from a triangle formed by diagonally dividing a rectangle connecting corresponding points on the upper surface and the lower surface of the effective contour line.

FIG. 16 shows a result of generating three-dimensional object data from Hiragana “A” by applying the present invention.

Further, in order to realize the function of generating the three-dimensional object data by a computer, a computer-readable recording medium such as a CD-ROM or a floppy disk has a program for realizing the function of the present invention. May be stored and provided.

[0073]

According to the present invention, even when the contour data has self-intersection, three-dimensional object data can be generated by eliminating the self-intersection and generating contour data without self-intersection. In addition, by arranging the vertex data constituting the contour line, triangulation can be performed efficiently.

[Brief description of the drawings]

FIG. 1 is a block diagram showing an embodiment of the configuration of the present invention.

FIG. 2 is a diagram showing an example of pointer structure data used for sequentially following vertices constituting a contour line in the present invention.

FIG. 3 is a diagram showing an example of vertex structure data used to represent vertices forming a contour line in the present invention.

FIG. 4 is a diagram illustrating an example of intersection structure data used to represent an intersection on a contour line when a self-intersection occurs in the present invention.

FIG. 5 is a diagram illustrating an example of a relationship between a contour line of a character and vertex structure data.

FIG. 6 is a diagram illustrating an operation of enumerating intersections in a contour analysis unit according to the present invention.

FIG. 7 is a flowchart showing the operation of the contour analysis unit 102 in the present invention.

FIG. 8 is a diagram showing an example of information set in intersection structure data in the present invention.

FIG. 9 is a diagram showing an example of a process for eliminating self-intersection in the present invention.

FIG. 10 is a flowchart showing an operation of combining intersection structure data in the contour analysis unit 102 in the present invention.

FIG. 11 is a diagram showing an example of a self-closed curve in which contour data self-intersects at only one intersection in the present invention.

FIG. 12 is a flowchart showing an operation of reconstructing a self-closed curve by the contour reconstruction unit 103 in the present invention.

FIG. 13 is a flowchart showing an operation of reconstructing a mutual closed curve by the contour reconstruction unit 103 in the present invention.

FIG. 14 is a diagram for explaining whether or not the triangle is effective when the contour inner region is divided into triangles in the present invention.

FIG. 15 is a flowchart illustrating an operation of the effective triangle determining unit according to the present invention.

FIG. 16 is a diagram showing an example applied to Hiragana “A” in the present invention.

[Explanation of symbols]

 101 contour storage unit 102 contour analysis unit 103 contour reconstruction unit 104 vertex alignment unit 105 sorted vertex storage unit 106 effective contour storage unit 107 vertex selection unit 108 effective triangle determination unit 109 effective triangle storage unit 110 3D object Data construction unit 111 Intersection storage unit S01 Intersection structure acquisition process S02 Route cost calculation process S03 Route search vertex initialization process S04 Intersection search initialization process S05 Intersection coordinate determination process S06 Intersection search end determination process S07 Route search vertex movement process S08 Contour Line intersection start point determination processing S09 Intersection search vertex movement processing S10 Path direction determination processing S11 Self-closed curve path correction processing S12 Self-closed curve path deletion processing S13 Contour restructuring end determination processing S20 Path search direction initialization processing S21 Path search vertex initialization processing S22 exchange Coordinate determination process S23 Route search vertex movement process S24 Route direction determination process S25 Route direction completed determination process S26 Route direction conversion process S27 Route cost determination process S28 Route change process 1 S29 Route change process 2 S30 Intersection structure removal process S31 Reconstruction end Judgment process S40 Vertex initialization process S41 Vertex direction judgment process S42 Vertex movement process S43 Comparison vertex region setting process S44 Comparison vertex reception process S45 Comparison vertex index initialization process S46 Triangle inside region judgment process S47 Comparison vertex index increase process S48 Successful division Availability determination processing S49 Effective triangle registration processing S50 All selected vertex movement processing S51 Selected vertex movement processing S52 Triangulation division end determination processing S70 Intersection enumeration initialization processing S71 Intersection enumeration end determination processing S72 Line segment determination processing S73 Line segment intersection determination processing S74 Intersection registration processing S75 Comparative vertex update processing S76 Comparative vertex end determination processing S77 Reference vertex update processing S78 Final vertex alignment processing processing S79 Path cost calculation processing S80 Vertex alignment processing

──────────────────────────────────────────────────続 き Continued on the front page (58) Field surveyed (Int. Cl. ⁷ , DB name) G06T 1/00-17/50 G09G 1/00-5/42

Claims (6)

(57) [Claims] An arbitrary contour data is obtained from one or more contour data constituting a character or a graphic represented by a vertex data array as a two-dimensional point sequence of three or more points stored in a storage device. It is determined whether or not there is a self-intersection that is an intersection with an arbitrary part constituting the acquired contour data and another part of the same contour, and when it is determined that the self-intersection exists, the intersection is determined. It is stored in the intersection storage unit, generates contour data from which the self-intersection of the contour data is eliminated, generates triangle data from the contour data from which the self-intersection is eliminated, and stores the triangle data in the pre-aligned vertex storage unit. Further, the vertex data of the contour line aligned at the coordinate position is compared with the triangle data, the validity of the triangle is determined, and when the triangle is determined to be a valid triangle, the triangle data is stored in the valid triangle storage unit. Record Then, the stored triangle data is applied to the upper surface and the lower surface of the columnar figure, and the side surface is a triangle formed by connecting the corresponding points of the contour data excluding the self-intersection of the upper surface and the lower surface by a diagonal triangle. A method for generating three-dimensional object data, comprising generating three-dimensional object data. 2. The three-dimensional object data generation according to claim 1, wherein vertex data aligned at the coordinate position is created using information output when the process of eliminating the self-intersection is performed. Method. 3. A three-dimensional object data generating apparatus for generating columnar three-dimensional object data from one or more contour data constituting a character or a figure, wherein an arbitrary part constituting one contour data is provided. However, if there is a self-intersection that intersects another part of the same contour, the contour data excluding the self-intersection of the contour data is generated, and the contour data of the character or the figure has three or more points. When represented by a vertex data array that is a two-dimensional point sequence, by preparing data aligned in advance at the coordinate position of the vertex data, it is determined whether or not the triangle to be divided is a valid triangle. The triangle data divided by using the triangulation method of characters and figures to be applied to the upper and lower surfaces of the columnar figure, and the side surface is a ring in which the self-intersection of the upper and lower surfaces is eliminated. Three-dimensional object data generating device and generating a three-dimensional object data rectangle formed by connecting the corresponding points of the line data from the triangles that can be divided by a diagonal line. 4. The three-dimensional object data generating apparatus according to claim 3, wherein data aligned at said coordinate position is created using information output when said self-intersection is eliminated. . 5. An outline storing means for storing one or more outline data constituting a character or a figure, and wherein the outline data obtained from the outline storing means is:
Contour analyzing means for analyzing whether or not self-intersecting; intersection storing means for storing the intersection when the contour data self-intersects; self-intersecting when the contour data self-intersecting Contour reconstructing means for correcting a contour having no contour, effective contour storage means for receiving and storing contours that do not intersect themselves from the contour analyzing means and the contour reconstructing means, the contour analyzing means, Vertex alignment means for obtaining and aligning vertex data from the contour reconstructing means, aligned vertex storage means for storing aligned vertices output from the vertex aligning means, and three vertices from the effective contour line storing means A vertex selecting unit that selects and stores the three vertices stored in the vertex selecting unit using the aligned vertex data stored in the aligned vertex storing unit. Valid triangle determining means for determining whether or not the triangle is a triangle included in the contour; effective triangle storing means for storing the triangle determined to be valid by the valid triangle determining means; and a surface of the columnar three-dimensional object. Mesh construction for constructing a mesh representing a columnar three-dimensional object using the contour data excluding the self-intersection of the upper and lower surfaces, constructing the upper and lower surfaces of the constituting mesh with the obtained effective triangles Means for generating three-dimensional object data. 6. A contour storage function for storing one or more contour data constituting a character or a figure, and wherein the contour data acquired from the contour storage means is:
A contour analysis function for analyzing whether or not the intersection is self-intersecting; an intersection storage function for storing the intersection when the contour data is self-intersecting; and a self-intersection when the contour data is self-intersecting. A contour reconstructing function for correcting a contour having no contour, an effective contour storing function for receiving and storing contours that do not self-intersect from the contour analyzing function and the contour reconstructing function, and the contour analyzing function and A vertex alignment function for obtaining and aligning vertex data from the contour reconstructing function, an aligned vertex storing function for storing the aligned vertices output from the vertex aligning function, and three vertices from the effective contour storing function A vertex selection function for selecting and storing the three vertices stored in the vertex selection function using the aligned vertex data stored in the sorted vertex storage function. An effective triangle determining function for determining whether a triangle is a triangle included in a contour; an effective triangle storing function for storing a triangle determined to be effective by the effective triangle determining function; and a surface of a columnar three-dimensional object. Mesh construction for constructing a mesh representing a columnar three-dimensional object using the contour data excluding the self-intersection of the upper and lower surfaces, constructing the upper and lower surfaces of the constituting mesh with the obtained effective triangles A recording medium storing a program for generating three-dimensional object data, wherein the program causes a computer to generate functions.