JPH0330189B2 - - Google Patents

Description

[Detailed Description of the Invention] [Table of Contents] Overview Industrial Field of Application Conventional Technology Problems to be Solved by the Invention Means for Solving the Problems Working Examples Structure of the Examples (Figure 2) Two-dimensional transformation Processing and edge division processing (Fig. 3, Fig. 4) Acute angle processing (Fig. 5) Hypotenuse processing (Fig. 6) Sorting processing (Fig. 7) Rectangle generation processing (Fig. 8, Fig. 9) Redivision processing (Fig. 10) Effects of the three-dimensional conversion processing invention [Summary] Regarding the improvement of the curved surface display processing method used for graphic processing in computer graphics, etc., for the purpose of improving processing efficiency, the present invention is stored in the first memory. When the edge line data read out is a curve, a sequence of points is generated on the curve to identify the curve. an edge line division/two-dimensional transformation processing step of converting the point sequence into a straight line segment connecting the point sequence, and converting the coordinate values of the point sequence into coordinate values in a two-dimensional space to convert the edge line into a polygon in the two-dimensional space; , when a triangle connecting three adjacent vertices of the polygon is formed inside the polygon and the opening angle of the central vertex is an acute angle, the triangle is separated into the formed triangle and the polygon excluding the triangle. an acute angle processing step, and for the side of the separated polygon that is not parallel to the two-dimensional space coordinate axis, a right triangle with that side as the hypotenuse and the other two sides parallel to the coordinate axis is formed inside the polygon; a hypotenuse processing step of separating the formed triangle and a polygon excluding the triangle; and a hypotenuse processing step of separating the formed triangle into a polygon excluding the triangle; a rectangle generation step in which rectangles included in the three-dimensional solid are formed without overlapping or missing, and when the surface of the three-dimensional solid is a curved surface with a total curvature of non-zero, the formed rectangle is further divided into a set of rectangles and triangles. a three-dimensional conversion processing step of inversely converting the set information of triangles and polygons obtained from each processing step into the three-dimensional information and storing it in a second memory; A three-dimensional shape image is displayed on the screen of the display unit by supplying the three-dimensional information read from the memory to a display control device that has the function of clipping non-displayed parts and erasing hidden surfaces and developing it into display pixels. It consists of steps.

[Industrial application field]

The present invention relates to improvements in curved surface display processing methods used for graphic processing in computer graphics and the like.

Graphic processing involves a large amount of data, so
There is a need to improve processing efficiency when processing figures such as curved surfaces.

[Conventional technology]

Displaying solid objects, including flat surfaces as well as curved surfaces such as cylindrical surfaces, conical surfaces, spherical surfaces, and free-form surfaces, on graphic displays is widely used in fields such as computer graphics and three-dimensional CAD (computer-aided design). ing. At that time, in order to reduce the amount of figure data to be processed and the time required for display processing, solids including curved surfaces are converted into simple planar polygons such as triangles and rectangles (called basic polygons or polygons). It is common practice to approximate using a polyhedron consisting of a collection of , and display each basic polygon. This is called a split display method. Fig. 12 shows an example in which a solid is approximated by a polyhedron, Fig. 12 a shows an example in which a cylinder is approximated, and b
is the case when a sphere is approximated.

FIG. 13 is a diagram illustrating display processing according to the prior art.

As shown in Figure 13a, the solid is divided into several planes by its edges. A curved surface is approximated by a polyhedron made up of a collection of basic polygons, and the division of a curved surface into basic polygons is usually performed for each surface. FIG. 13b shows an example of the front curved surface on the cylindrical surface of FIG. 13a.

When performing division, as shown in Figure 13c,
A lattice is set on the curved surface to be displayed as shown in FIG. If the figure that has entered the grid becomes a triangle or a quadrangle, that figure is transferred to a display device and displayed. However, if the figure within the grid is a polygonal figure that is more complex than a rectangle, as shown in the shaded area in Figure c, a finer grid is set within the grid and the grid is subdivided. Calculate the intersections between the grid and the figure, and continue dividing until the figure in the subdivided grid becomes a triangle or quadrilateral. FIG. 13d shows the result of extracting and subdividing the hatched area in FIG. 13c.

[Problem to be solved by the invention]

As explained above, in the conventional split display method, calculation of intersections between figures and grids in three-dimensional space is essential. These are calculations on three-dimensional coordinate data, and since the display range of fixed-point numbers is limited, calculations must be performed in floating-point format.

Floating-point calculations take several times as long as fixed-point calculations, so there is a problem in that a large amount of time is required to divide a figure.

[Means to solve the problem]

FIG. 1 is a block diagram showing the process of the present invention.

In the figure, 1 is a first memory, which stores three-dimensional information to be displayed.

Reference numeral 4 denotes a display control device, which performs processing for developing display data into display pixels, such as coordinate conversion, clipping, hidden surface processing, etc. of display data.

10 and 11 are edge line division/two-dimensional conversion processing steps, in which when the edge line data read from the first memory 1 is a curve, a sequence of points is generated on the curve and the curve is converted into a straight line connecting the sequence of points. At the same time, the coordinate values of the point sequence are converted into coordinate values in a two-dimensional space, and the edge line is converted into a polygon in the two-dimensional space.

13 is an acute angle processing step, in which when a triangle connecting three adjacent vertices of a polygon converted into two-dimensional form is formed inside the first polygon and the opening angle of the central vertex is an acute angle, the formed triangle and a polygon excluding the triangle.

14 is a hypotenuse processing step in which, among the sides of the polygon separated in the acute angle processing step 13, for the side that is not parallel to the two-dimensional space coordinate axis, a right triangle is formed with that side as the hypotenuse and the other two sides parallel to the coordinate axis. is formed inside the polygon and separated into the formed triangle and a polygon excluding the triangle.

16 is a rectangle generation step, in which from the polygon separated in the hypotenuse processing step 14, rectangles that are parallel to the two-dimensional coordinate axis and include the sides of the polygon as part of the sides are formed without overlapping or missing each other. do.

17 is a re-division processing step, and when the surface of the three-dimensional solid is a curved surface whose total curvature is not zero, the rectangle formed in the rectangle generation step 16 is further divided into a set of rectangles and triangles.

18 is a three-dimensional conversion processing step, which inversely converts the set information of triangles and polygons obtained from each step of acute angle processing 13, hypotenuse processing 14, rectangle generation 16, and re-division processing 17 into the three-dimensional information. The data is stored in the second memory 19.

A second memory 19 stores the restored three-dimensional information.

A display section 21 displays images under the control of the display control device 4.

[Effect]

The present invention converts curved surface image information (three-dimensional data) to be displayed three-dimensionally into two-dimensional information in a two-dimensional conversion processing step 10, and then performs an acute angle processing step 13, a hypotenuse processing step 14, a rectangle generation step 16, and a rectangle generation step 16. The division process step 17 divides the information into basic polygons (triangles and quadrilaterals), and the three-dimensional conversion process 18 converts the divided two-dimensional information back into three-dimensional information and supplies it to the display device. This is designed to display a curved surface image in three dimensions.

In this way, the present invention eliminates the need to calculate intersection points at three-dimensional grid points, which required the longest processing time, and instead performs division processing on two-dimensional information, so the numerical representation of the required calculation target is fixed. This can be done in decimal format, improving processing efficiency.

〔Example〕

[Configuration of Examples] The present invention will be specifically described below using Examples.

FIG. 2 is a diagram showing the configuration of an embodiment of the present invention. FIGS. 3 to 10 are diagrams showing examples of graphic processing according to an embodiment of the present invention. Further, FIG. 11 is a flowchart showing processing according to an embodiment of the present invention.

In FIG. 2, 1 is a file in which solid model (mathematical model expressing a three-dimensional shape) data SD is stored. The surface data included in this solid model data SD or the edge line data constituting the boundary line are all three-dimensional data. Information management including information changes of the solid model data SD is performed by the solid modeling section 3.

When graphic processing (such as changing a three-dimensional shape) is performed using the keyboard 5 or light pen 6 of the display control device 4, the solid data handler 2 is activated by the processing section 7.

The solid data handler 2 transfers the solid model data SD retrieved from the file 1 to the bus 8.
After that, it is sent to the polygon dividing section 9.

Hereinafter, the operation of the polygon dividing section 9 will be described in detail according to the flowchart shown in FIG.

[Two-dimensional conversion process and edge line division process] The polygon division unit 9 converts solid model data
A process of dividing each curved surface constituting the SD into a set of basic polygons is performed, but first, three-dimensional data is converted into two-dimensional data by two-dimensional conversion process 10.
As mentioned above, the surface data and edge data included in the solid model data SD are all three-dimensional data, which is converted into two-dimensional data.

For example, a rectangular parallelepiped is a three-dimensional real space (x, y, z)
Although it can only be expressed as data within, if it is limited to the surface of this rectangular parallelepiped, it can be considered in a two-dimensional parameter space (u, v). This conversion from three-dimensional data to two-dimensional data can be processed using mathematical methods. As an example, in the case of plane transformation, the normal vector n is set as n→=(n _x , _ny , _nz ), and the one with the maximum absolute value among each component is set as n _nax =Max｜｜n _x ｜ , |n _y |, |n _z ||, then n _nax = |n _x | then (u, v)=(y, z) n _nax = |n _y | If (z, x) n _nax = |n _z |, then (u, v) = (x, y) from the three-dimensional real space (x, y, z) to the two-dimensional parameter space (u, v) conversion becomes possible.

FIG. 3a shows a figure on a plane in a three-dimensional real space (x, y, z) and a figure after being converted into a two-dimensional parameter space (u, v).

Also, when the figure in the three-dimensional space is not on a plane but on a cylindrical surface, as shown in Figure 3b, the height h in the cylinder axis direction and the angle θ in the circumferential direction are set on the cylindrical surface. By adopting it as a coordinate system to represent the position,
Similarly, a figure can be transformed into a two-dimensional parameter space (u, v).

The transformation coordinate system at this time is, for example, if the origin of the (x, y, z) coordinate system is placed on the central axis of the cylindrical surface, (z, (y/|y|)cos ^-1 (x/ r)) = (h, θ) = (u, v). (In the above equation, r is the radius of the cylindrical surface, and |y| is the absolute value of y.) Also, if the figure in the three-dimensional space is on a conical surface, as shown in Figure 3c, Assuming the height h and the circumferential angle θ as a coordinate system representing the position on the conical surface,
It can be transformed into a two-dimensional parameter space (u,v). In addition, if it is on a spherical surface, as shown in Figure 3d, the angle θ in the latitude direction and the angle φ in the longitude direction are used as a coordinate system representing the position on the spherical surface, and the two-dimensional parameter space (u, v) is created. can be converted.

As for the above-mentioned transformed coordinate system, it is also possible to use other more complicated coordinate systems. For example, instead of the angle θ, -cos(θ/2),
Function f(θ) that increases monotonically within the range 0゜≦θ＜360゜
You can also use

Next, regarding the edge line data extracted from the solid model data SD, (1) the coordinate values of the start and end points of each side, (2) the center coordinate values and radius for circular arcs, and (3) the control values for free curves. This is three-dimensional data consisting of information, that is, information expressed by parameters t (0 to 1).

In the case of item (1) above, the coordinate values (x, y, z) of the start point and end point of each side are converted by the two-dimensional conversion unit 10 into coordinate values in the (u, v) space. Also(2)
Regarding the arc in term (3) and the free curve in term (3), the edge line division unit 11 generates and divides a series of points on the side as shown in FIG. 3e, and approximates it with a polygonal line, The coordinate values (x, y, z) are converted by the two-dimensional conversion unit 10 into coordinate values (u, v) in the two-dimensional parameter space.

Through the above processing, a "curved surface in a three-dimensional space surrounded by straight lines, circles, and free curves" extracted from a solid is converted into a "polygon in a two-dimensional space surrounded only by straight lines". Ru. FIG. 3f shows an example in which three curved surfaces (s ₁ , s ₂ , s ₃ ) constituting one solid are converted into polygons in separate (u, v) spaces. In the figure, solid C is composed of three surfaces s ₁ , s ₂ , and s ₃ , and the top surface s ₁ is a shape in (u, v) space.
s ₁₀ , the circumferential surface s ₂ becomes a developed figure s ₂₀ in (u, v) space, and the base s ₃ becomes (u, v).
v) It is expanded in space like a figure s ₃₀ . The periphery of this developed figure is approximated as a polygonal line, and the starting point and end point on each polygonal line are shown as a series of points.

As shown in FIG. 4a, these point sequences are connected counterclockwise for the outer periphery of the surface P _put and clockwise for the periphery P _io of the hole using pointers (addresses indicating storage locations).

[Acute angle processing] The surface division processing 12 in FIG. 2 is the acute angle processing 1.
3. Processed by hypotenuse processing 14, sorting processing 15, rectangle processing 16, and redivision processing 17.
This surface division 12 performs a process of converting the "polygon in the two-dimensional parameter space" shown in FIG. 4b into a set of basic polygons such as triangles and rectangles.

First, the acute angle processing 13 performs the following processing on the point sequence (P ₁ to _{P 22} ) connected by the pointer shown in Figure 5a, generates a triangle that is a basic polygon, and stores its data. is transferred to the three-dimensional conversion process 18.

(1) Interior angle θ of all vertices from P ₁ to P ₂₂ in order
Find out. The interior angle here is the angle that goes around inside the surface. That is, for the point P ₁ that constitutes the outer circumference P _put of the surface, the interior angle ∠
P ₁₅ P ₁ P ₂ means 90°, not 270°. Interior angle ∠ of point P ₂₀ that makes up the perimeter P _io of the hole
P ₁₉ P ₂₀ P ₂₁ is at 270°, not at 90°.

(2) If the interior angle θ of the vertex P _i is an acute angle (0°<θ<90°), a triangle is generated by combining the two points P _i-1 and P _i+1 that sandwich the point P _i . Specifically, the (u, v) coordinate values of three points P _i-1 , P _i , and P _i+1 are transferred to the three-dimensional transformation unit 18 . Then delete point P _i , points P _i-1 and P _i-1
Connect with pointers.

In the example shown in FIG. 5a, the interior angles θ of points P ₃ , P ₇ , and P ₁₁ are acute angles, and ΔP ₂ P ₃ P ₄ , ΔP ₆ P ₇ P ₈ ,
Three triangles ΔP ₁₀ P ₁₁ P ₁₂ are generated, P ₃ , P ₇ ,
Three points on P ₁₁ were deleted.

By the above processing, the "polygon consisting of only right angles and obtuse angles without including any acute angles among interior angles" is obtained as shown in FIG. 5b.

[Hypotenuse processing]

The hypotenuse processing 14 in FIG. 2 is as shown in FIG.
The following processing is performed on the "polygon consisting of only right angles and obtuse angles as interior angles" shown in , to generate a right triangle which is a basic polygon, and the data is transferred to the three-dimensional conversion process 18.

(1) Check whether each side of a ``polygon consisting only of right angles and obtuse angles'' as shown in Figure 6a is parallel to the u- and v-axes, starting from side P ₁ P ₂ .

(2) As shown in the figure, for a side that is not flat with either the u-axis or the v-axis, form a right triangle with that side as the hypotenuse and the two sides that sandwich the right angle parallel to the u-axis and the v-axis, respectively. Generate on the side that does. Figure 6a
In , the side indicated by a double line (=) is u
This is a side that is not parallel to either the axis or the v-axis. For example, for side P ₂ P ₄ , a new point P ₂₃ with the same u coordinate value as point P ₂ and the same v coordinate value as point P ₄ is generated, and a triangle consisting of the three points P ₂ P ₄ P ₂₃ is created. generate. Specifically, the (u, v) coordinate values of these three points are transferred to the three-dimensional transformation unit 18, and point P ₂₃ is inserted between points P ₂ and P ₄ using a pointer. In the example shown in FIG. 6a, the side P ₂ P ₄ , the side P ₄ P ₅ to P ₁₆ P ₁₇ , the side P ₂₂ P ₁₈
From the 8 sides of , △P ₂ P ₄ P ₂₃ , △P ₄ P ₅ P ₂₄ ~ △
Eight right triangles P ₁₆ P ₁₇ P ₂₉ and ΔP ₂₂ P ₁₆ P ₃₀ are generated.

Through the above processing, the "polygon composed only of sides parallel to the u-axis or the v-axis" shown in Figure 6b is created.
is obtained.

[Sort processing]

The sorting process 15 in FIG.
The following processing is performed on the polygon shown in Figure b, and the point sequence P _i connected in a circular manner along the periphery of the surface by the pointer is sorted in ascending order of v coordinate values (in the case of the same v coordinate value, u (in ascending order of coordinate values) and connect them with new pointers.

(1) Compare the v coordinate values of each vertex P _i of the polygon shown in Figure 6b, rearrange them in ascending order, and connect them with a pointer.

(2) For vertices P _i that have the same v coordinate value, compare the u coordinate values, rearrange them in ascending order, and connect them with pointers.

(3) Type classification is performed at the same time depending on the position of each vertex P _i on the edge, and a symbol (,,) is added to each vertex P _i .

If it is in a corner, add the symbol ().

If it is on a side parallel to the v coordinate value (excluding both end points), the symbol () is added.

If it is on the side parallel to the u coordinate value (excluding both end points), add the symbol ().

Through the above processing, the connection of the polygonal pointers shown in FIG. 6b changes from the shape shown in FIG. 7a to the shape shown in FIG. 7b, that is, as follows.

Before processing:
P ₁ P ₂ P ₂₃ P ₄ P ₂₄ P ₅ P ₆ P ₂₅ P ₈ P ₉ P ₂₆ P ₁₀ P ₂₇ P ₁₂ P ₁₃ P ₂₈
P ₁₄ P ₁₅ P ₁₆ P ₂₉ P ₁₇ P ₁₈ P ₁₉ P ₂₀ P
₂₁ P ₂₂ P ₃₀ (Figure 7a
The circular pointer structure shown in ) After processing:
P ₁ P ₂ P ₁₅ P ₁₄ P ₂₃ P ₄ P ₂₉ P ₁₆ P ₃₀ P ₁₃ P ₂₈ P ₁₇ P ₂₄ P ₅ P ₁₂ P
₂₇ P ₁₈ P ₁₉ P ₂₂ P ₂₀ P ₂₁ P ₂₅ P ₆ P ₁₀
P ₂₆ P ₉ P ₈ (Ascending pointer structure shown in FIG. 7b) This sorting process 15 is a process for efficiently performing the rectangle generation process in the next rectangle generation 16.

[Rectangle generation]

The rectangle generation 16 in FIG.
The following processing is performed on the polygons that are connected using the ascending pointer structure shown in Figure b and have type symbols added to generate rectangles that are basic polygons one after another, and the data is transferred to the re-division process 17. do.

FIG. 8a schematically represents the outline of the process of rectangle generation 16. Follow the point sequence P _i along the pointer to find the side Q ₁ Q ₂ that is the base of the rectangle. Next, move the edge Q ₁ Q ₂ until it collides with another vertex v
Lift in the positive direction of the coordinate axes to generate a rectangle.
This process depends only on the sides Q ₁ Q ₂ and the shape above them, so even if the polygon splits into two or into two or more shapes, as in the example in Figure 8a, the process will not be processed. It is possible. The generation procedure is shown below in Figures 8 and 9.
This will be explained with reference to the figures.

(1) Take the first point of the point sequence P _i connected by the ascending pointer. Let this point be Q ₁ and its coordinates be (u ₁ ,
v ₁ ). If point P _i is the final point, the process of rectangle generation 16 ends.

(2) Take the next point connected to Q ₁ with an ascending pointer. Let this point be Q ₂ and its coordinates be (u ₂ ,
v ₂ ). At this time, since sides Q ₁ and Q ₂ are parallel to the u coordinate axis, the relationship v ₁ = v ₂ is established, and the coordinate values of point Q ₂ are (u ₂ , v ₁ ).

(3) Check the coordinate values of the points connected to point Q ₂ by the ascending pointer and find the first point that has a u coordinate value greater than or equal to u ₁ and less than or equal to u ₂ and a v coordinate value greater than v ₁ . Let this be a point Q ₃ and its coordinate values be (u ₃ , v ₃ ). That is, u ₁ ≦u ₃ ≦u ₂ and v ₁ <
v ₃ . This condition corresponds to the shaded area in FIG. 8b.

(4) When u ₃ = u ₂ , that is, point Q ₃ is directly above point Q ₂ (v
coordinate values (u ₁ , v ₃ )
, that is, directly above point Q ₁ and to the left of point Q _{3 ,} and generates a rectangle Q ₁ Q ₂ Q ₃ Q ₄ . Specifically, the (u, v) coordinate values of these four points are transferred to the redivision processing unit 17, points Q ₁ and Q ₂ are deleted from the point sequence, and the type of point Q ₃ is changed (point Q If the type of ₃ is ni, then ni) and add a symbol to point Q ₄ .

(5) When u ₁ ≦ u ₃ < u ₂ , process as follows.

When u ₃ =u ₁ , that is, when point Q ₃ is directly above point Q ₁ , point Q ₃ found in the above section (3) is used as is for subsequent processing. The first rectangle generated in FIG. 8b corresponds to this case.

When u ₁ < u ₃ < u ₂ , that is, when point Q ₃ is above side Q ₁ Q ₂ , the position of coordinate values (u ₁ , v ₃ ), that is, directly above point Q ₁ , point Q Create a point _A to the left of ₃ and make it a new point Q ₃ . The second rectangle generated in Figure 8c corresponds to this case.

Check the coordinate values of the points connected to point Q ₃ with the ascending pointer, and find the u coordinate value greater than or equal to u ₂ , or
Find the first point with v coordinate value greater than v ₃ . Let this be Q ₄ and its coordinate values are (u ₄ ,
v ₄ ).

When u ₂ = u ₄ , that is, point Q ₄ is directly above point Q ₂ ,
If it is to the right of point Q ₃ , use the point Q ₄ found above for subsequent processing as is.

When u ₂ < u ₄ or v ₃ < v ₄ , that is, when point Q ₄ is not at the position (u ₂ , v ₃ ), the coordinate value (u ₂ ,
v ₃ ) and create a new point.
_Q4 .

Rectangle consisting of four points Q ₁ , Q ₂ , Q ₄ , Q ₃
Generate Q ₁ Q ₂ Q ₄ Q ₃ . Specifically, the (u, v) coordinate values of these four points are transferred to the re-division processing 17, and points Q ₁ and Q ₂ are deleted from the point sequence.

Change the type of point _Q3 .

As shown in FIG. 9a, when the point _Q3 is a type, the process moves to post-processing where the type is changed to . As shown in Figure 9b, if the type of point _Q3 is , and it is an even number among the types with the same v coordinate value, counting from the smaller u coordinate value, the type is changed to . After that, move on to processing. As shown in Figure 9c, when the type is and it is an odd number, the point
Delete the data of Q ₃ from the point sequence and move on to processing.

Change the type of point _Q4 .

As shown in FIG. 9d, when the type of point _Q4 is , the type is changed to , and the process returns to item (1). As shown in Figure 9e, if the type of point Q ₄ is , and it is an odd number among types with the same v coordinate value, counting from the smaller u coordinate value, then the type of point Q ₄ is After changing to , return to the process in section (1). As shown in FIG. 9e, if the type of point _Q4 is , and it is an even number, the data of point _Q4 is deleted from the point sequence, and then the process returns to item (1).

[Re-splitting process]

The rectangle output by the rectangle generator 16 has been divided in the v-coordinate axis direction, but has only been minimally divided in the u-coordinate axis direction to divide the polygon into a set of rectangles.

As shown in FIG. 10a, since the curvature of a cylindrical surface in the u coordinate axis direction (cylindrical axis direction h) is 0, the curved surface can be approximated only by division in the v coordinate axis direction (circumferential direction θ). However, as shown in Figure 10b, the curvature of the spherical surface is not zero in both the v-coordinate axis direction (longitude direction θ) and the u-coordinate axis direction (latitude direction φ), so the second
In the re-division process 17 shown in the figure, it is necessary to perform division again in the u-coordinate axis direction.

In the re-division process 17 in FIG. 2, information on the surface type of the surface being processed is obtained from the file 1 through the solid data handler 2. Then, the following processing is performed depending on the surface type.

(1) In the case of a surface with a total curvature of 0, such as a plane, a cylindrical surface, or a conical surface, the rectangle information output by the rectangle generation 16 is transferred as is to the three-dimensional conversion processing 18.

(2) In the case of a curved surface such as a spherical surface or a free-form surface whose total curvature is not 0, the re-division process 17 divides the rectangle transferred from the rectangle generation unit 16 in the u-coordinate axis direction through the following processes,
The newly generated rectangular data is transferred to the three-dimensional conversion process 18. An example in which the second rectangle shown in FIG. 8a is subdivided is shown in FIG. 10c.

Points of the type that exist on the bottom side (side Q ₁ Q ₂ ) and the top side (side Q ₃ Q ₄ ) of the rectangle output by the rectangle generator 16 are searched from the side with the smaller u coordinate value.

Divide the rectangle at the u coordinate value where the type point is located.

The (u, v) coordinate values of the four points of the rectangle generated by the division are transferred to the three-dimensional transformation process 18.

[Three-dimensional conversion process] The three-dimensional conversion process 18 in FIG. 2 converts (u, v) Convert the coordinate value data into coordinate values (x, y, z) in a three-dimensional space based on the geometric information of the surface being processed obtained from the file 1 through the solid data handler 2.

(1) In the case of a plane, one coordinate value among x, y, and z erased by the two-dimensional transformation unit 10 is transformed into the following equation, which is a transformation of the equation representing a plane, f(x, y, z) = 0. x=g ₁ (y, z), y=g ₂ (z, x), z=g ₃
Reproduction is performed by substituting the (u, v) coordinate value into one of (x, y).

(2) In the case of a cylinder, similarly to two-dimensional transformation process 10,
Place the origin of the (x, y, z) coordinate system on the central axis of the cylindrical surface, and change the (u, v) coordinates as (r・cosθ,r・sinθ,h)=(x,y,z) From the system (x, y, z)
Convert to coordinate system.

In the above processing, solid model data SD from file 1 is stored in file 19, and division processing is performed on the data SD.
Therefore, the processed data, that is, the display data TD, is also stored in the file 19.

The data TD in the file 19 is extracted by the display data handler 20 and then sent to the display control device 4 via the bus 8 and displayed on the display section 21. Display control device 4 and display unit 2 in FIG. 2
1 is the three-dimensional coordinate value (x,
A raster scanning type three-dimensional system equipped with a storage device that stores display data TD consisting of a set of y, z), and a processing device that performs processing to develop the display data into display pixels, such as coordinate transformation, clipping, and hidden surface processing. It is a color graphic display. The technology for display processing in this type of device is a well-known technology.

With respect to the three-dimensional display image displayed on the screen 22 of the display unit 21, the three-dimensional shape of the figure is changed by operating the light pen 6 or the keyboard 5.

[Effects of the Invention] As is clear from the above description, according to the present invention, the process of dividing an arbitrary curved surface into basic polygons in a three-dimensional real space (x, y, z) is performed in a two-dimensional parameter space (u, After converting to v), it can be processed by tracing between each point sequence, and then the processed data is back-converted to three-dimensional data again, so
This eliminates the need for a large amount of processing such as calculation of intersection points as in the past, resulting in the effect of significantly increasing processing efficiency.
Furthermore, the fact that it is not necessary to calculate the intersection points at the grid points is as follows.
The calculation data at this time must be in floating point format for numerical calculations, and in order to prevent calculation errors caused by digit loss due to the effective digit length, rounding of point sequence coordinates etc. This means that there will be no positional shift caused by this.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing the processing of the present invention, and FIG.
The figure is a diagram showing the configuration of an embodiment of the present invention, Figures 3 to 10 are diagrams showing an example of graphic processing according to an embodiment of the present invention, and Figure 11 is a flowchart showing processing according to an embodiment of the present invention. The charts, FIGS. 12 and 13 are diagrams showing processing according to a conventional example. In the figure, 1 and 19 are files (memory),
2 is a solid data handler, 3 is a solid modeling section, 4 is a display control device, 5 is a keyboard,
6 is a light pen, 7 is a processing unit, 8 is a bus, 9 is a polygon division unit, 10 is a two-dimensional conversion process, 11 is an edge division process, 12 is a surface division process, 13 is an acute angle process, 14 is a hypotenuse process, 15 16 is a sorting process, 16 is a rectangle generation process, 17 is a re-division process, 18 is a three-dimensional conversion process, 20 is a display data handler, 21 is a display section, 22 is a screen, and 23 is a processing device.

Claims (1)

[Scope of Claims] 1. Three-dimensional three-dimensional information consisting of surface data including curved surfaces and edge line data including curves in a three-dimensional space stored in the first memory 1 is read out, and the read edge line data is a curved line. At some point, a sequence of points is generated on the curve, the curve is converted into a straight line segment connecting the sequence of points, and the coordinate values of the sequence of points are converted into coordinate values in a two-dimensional space to transform the ridge line into a two-dimensional space. Edge division/two-dimensional conversion processing steps 10 and 11 for converting into a polygon in space, and a triangle connecting three adjacent vertices of the polygon is formed inside the first polygon, and the opening angle of the central vertex is a vertical angle. At some point, a lead angle processing step 1 is performed to separate the formed triangle and a polygon excluding the triangle.
3. Among the sides of the separated polygon, for the side that is not parallel to the two-dimensional space coordinate axis, a right triangle is formed inside the polygon, with that side as the hypotenuse and the other two sides parallel to the coordinate axis; a hypotenuse processing step 14 of separating the formed triangle and a polygon excluding the triangle; and converting the separated polygon into a part of the side parallel to the two-dimensional coordinate axis and of the polygon. a rectangle generation step 16 in which the rectangles containing the rectangles are formed without overlapping or missing, and when the surface of the three-dimensional solid is a curved surface with a total curvature other than zero, the formed rectangle is further divided into a set of rectangles and triangles. The set information of triangles and polygons obtained from each step of the acute angle processing 13, hypotenuse processing 14, rectangle generation 16, and redivision processing 17 is inversely converted into the three-dimensional information. a three-dimensional conversion processing step 18 for storing the three-dimensional information in the second memory 19; and a function for developing the three-dimensional information read from the second memory 19 into display pixels by clipping non-displayed parts and erasing hidden surfaces. A curved surface display processing method characterized by comprising the step of displaying a three-dimensional shape image on the screen of a display unit 21 by supplying it to a display control device 4 having a three-dimensional shape image.