JPH07160905A - Drawing method and drawing apparatus for contour line and edge line - Google Patents

Abstract

(57) [Abstract] [Purpose] In order to display the object shape in a three-dimensional figure display by a computer in an easy-to-understand manner without damaging the object shape, the contour line and the ridge line are detected without error and added to the displayed figure. To provide a method and an apparatus thereof. [Structure] From the three-dimensional object shape given by the polyhedron approximation,
The CPU creates information on the degree of connection between polygons and polygons, and at the same time determines the type of the side based on the normal vector,
Memorize in correspondence with the side. Further, which polygon is displayed in each pixel of the display screen is stored. And
Tracing the side, the case where the displayed polygon does not maintain connection on both sides of the side is detected and drawn as a contour line.
Further, when the connection condition is maintained, only when the side type is a ridge line, it is detected and drawn as a ridge line.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a graphic display method using a computer, and more particularly to a contour line and edge drawing method and apparatus for displaying an object shape in an easily understandable manner.

[0002]

2. Description of the Related Art Conventionally, when a three-dimensional object shape is displayed as a two-dimensional image by a computer, the object shape is given as data that approximates a polygon, and the contour of the given polygon is displayed as a line. (Display method by line drawing) and a method of drawing by painting the inside of the polygon by changing the shading and color (display method by plane drawing) have been adopted.

For the purpose of generating a realistic image, the brightness of each point on the object surface is calculated based on the position of the light source, the reflectance of the object surface, etc., and displayed as a shaded screen. Methods are commonly used. As a typical method, the Z-buffer method (edited by the Institute of Electronics, Information and Communication Engineers, New Media Technology Series computer graphics,
P121-P122) and ray tracing method (The Japanese Society for Graphic Studies, CG)
Handbook, see P417-P418).

Further, in an image generated by the Z-buffer method or the like, depending on the position of the light source, the reflectance, etc.,
In some cases, it may be difficult to recognize the shape of an object, the arrangement state when a plurality of objects are arranged, and the like. In order to solve this, it has been conventionally known that emphasis on contour lines and ridge lines is effective, and a method of automatically adding contour lines and ridge lines by a computer has been proposed. That is,
As described in JP-B-3-123985, a method has been proposed in which a contour line and a ridge line are detected based on a distance image generated by the Z-buffer method, and the contour line and the ridge line are added and displayed. Here, the contour line refers to a boundary line between a visible portion and a non-visible portion of a certain object, and the ridge line refers to an inner shape line representing an angular portion of the object other than the contour line.

[0005]

The method of detecting the contour line and the ridge line based on the range image of the above-mentioned prior art has the following problems.

(1) First-order differential values and second-order differential values of a distance image are taken, and the peaks of these values are detected as contour lines and ridge lines. However, since this range image is usually an integer value, it contains a quantization error. For example, in a range image of a plane that is nearly parallel to the screen, a stepwise change occurs at a certain portion. In such a portion that changes stepwise, the differential value takes a peak value and is detected as a contour line or a ridge line, so an error occurs in the detection.

(2) Since the contour line is detected on both the inside and outside of the object boundary, the outline becomes thick regardless of the shape and size of the display object. For this reason, for example, if the color of the contour line is the same as the background, the display object looks a little smaller, and the color of the contour line is significantly different from the background (for example, when the contour line is black and the background is white). Some people see the boundary of an object as the outside or inside of the line, and see it as one size larger or smaller. This is remarkable as the smaller the object is displayed, the larger the proportion of the contour line and the ridge line in the area of the display object becomes.

An object of the present invention is to solve the above problems, detect the contour line and the ridge line of a display object without error, and add the contour line and the ridge line so as not to make the image thick, thereby making it easy to understand the object shape. Is to provide a method of generating.

[0009]

In order to achieve the above object, according to the present invention, the continuity between polygons and polygons, that is, which polygons and which polygons are calculated from the three-dimensional object shape data given by the polyhedral approximation. Check if the polygon and the square touch each other,
At the same time as making this continuity data correspond to the sides of a polygon, it is also determined whether this side is an angled side (ridge line) or whether a plane or curved surface is divided by polyhedral approximation (hereinafter referred to as an approximate line). These are stored as an edge attribute table. Then, when these sides are displayed, on both sides of this side on the display image, the sides that do not satisfy the continuity of the polygon are contour lines. If the continuity is satisfied, it is already determined whether the line is the ridge line or the approximate line, so the ridge line can be detected. Also, if the drawing of the side is one pixel wide, the line width does not become thick. This achieves the above purpose.

[0010]

In the present invention, first, the side attribute table is created, and an image in which the polygon identifier is stored instead of the normal display image and color, that is, a polygon ID image is created. Then, by comparing the side attribute table with the polygon ID image, the continuity of the polygon is determined, and if it is discontinuous, it is determined as a contour line, and as a contour line, a normal display image differs from other portions. Add in different colors. If it is continuous, it is checked whether it is a ridge line, and if it is a ridge line, it is added as a ridge line to a normal display image in a color different from that of other portions. In this way, the contour line and the ridge line of the object can be detected and added without error, the line width can be displayed with one pixel width, and the object shape is not damaged.

[0011]

Embodiments of the present invention will be described below with reference to FIGS.

FIG. 1 is a flowchart showing the overall processing flow of the present invention. First, an outline of the overall process 100 will be shown, and details will be described later. First, in step 101, a side attribute table necessary for detecting a contour line and a ridge line is created from the given three-dimensional shape data. Next, in step 102, an image with hidden surfaces removed is generated. Next, in step 103, a polygonal ID image is created. Then, in step 104, by comparing the edge attribute table created in step 101 with the polygon ID image created in step 103, it is possible to determine whether each pixel is a contour line or a ridge line. Then, in step 105, an image in which the object shape is easy to understand is generated by synthesizing the contour line and the ridge line with the image in which the hidden surface is removed. Further, by displaying only the detected contour line and ridge line, a wire frame image with hidden lines removed can be generated.

Next, an embodiment of a system incorporating the present invention will be described with reference to FIG. This system comprises a CPU 1001, a main memory 1002, a graphics processor 1005, a Z-buffer 1008, a frame memory 1009, a polygon ID memory 1010, a display device 1011 and a system bus 1012.

Here, the CPU 1001 issues a drawing command to the graphics processor 1005 and performs processing such as creation of an edge attribute table (step 101), and the main memory 1002 stores a program for display and graphic data. Area 1003, side attribute table area 1004
including. The graphics processor 1005 is a CPU
The drawing command received from 1001 is executed to generate an image in the frame memory 1009 and the polygon ID memory 1010, and the normal drawing unit 1006 and the contour line ridge line generation unit 1007 are included. The Z-buffer 1008 stores data necessary for executing hidden surface removal, the frame memory 1009 stores color information for displaying a figure, and the polygon ID memory 1010 detects contour lines and ridge lines. The display device 1011 displays the image on the frame memory 1009.

The details of each step of the overall process 100 will be described below.

Description of Step 101: Next, Step 101 of creating an edge attribute table will be described with reference to FIGS. 2 and 4 to 7.

FIG. 2 shows the configuration of a cube, which has V1 ...
V8 indicates the vertices of a cube, and P1 to P6 indicate the polygons (squares here) that make up the cube. A cube like this
For example, as shown in FIG. 4, a set of several polygons is given by the vertices (V1, V2, etc.) of each polygon and the normal vector (n1, n2, etc.) of each vertex. However, only the data of the polygons P1 to P3 of the cube in FIG. 2 are shown here. On the other hand, FIG. 5 shows a curved surface given by dividing it into a plurality of polygons, and shows a polygon obtained by dividing a part delimited by a solid line and a broken line, and an arrow shows a normal vector of each vertex. FIG. 6 shows the structure of the side attribute table used here and the cube of FIG. 2 expanded into this side attribute table. However, it is assumed that the cube of FIG. 2 is given by the graphic data as shown in FIG. Here, in the side attribute table, coordinate 1, normal vector 1, coordinate 2, normal vector 2
Indicates the coordinates of the start point of the side, the normal vector of the start point, the coordinates of the end point, and the normal vector of the end point, respectively.
Indicates the starting point and the ending point when detecting the contour line and the ridge line, and the normal vectors 1 and 2 are used when determining the ridge line and the approximate line. The polygon ID is, for example, the polygons P1 and P shown in FIG.
Numbers for identifying 2, ..., Polygon IDs 1 and 2
Enter the identifier of the polygon that touches that edge, and use this value when determining the contour line or ridge line. The edge type indicates how the edges forming the polygon connect the two polygons. Here, the variants are classified into three types, that is, a single side, a ridge line that polygons are in contact with a polygon, and an approximate line, and are 0, 1 and 2, respectively. Here, the single side is shown in FIG.
The side that is not sandwiched by polygons as shown by the solid line of
A ridge line is a side that forms the cube of FIG. 2, is sandwiched by polygons, and has sides having normals in two directions at the start point and the end point of the side, and the approximate line is The sides as indicated by the broken lines in FIG. 5 are respectively sandwiched by polygons and have a normal line in only one direction at each of the start point and the end point of the side.

FIG. 7 shows the flow of processing for creating the edge attribute table of FIG. 6 from the data shown in FIGS. 2, 4 and 5. It should be noted that this process corresponds to the CP in FIG.
This is executed in U1001, and the graphic data shown in FIGS. 4 and 5 are stored in the graphic data area 1003, and the side attribute table shown in FIG. 6 is stored in the side attribute table area 1004. First, in the determination 701, it is checked whether or not the side that is the target of the current determination and the side whose coordinates of the start point and the end point match have been registered so far. If there is no matching edge, processing 707 and 708 for adding as a new edge is executed. If there is a matching side, the process 702 is executed for the matched side, and then it is determined by the determination 703 whether it is a ridge line or an approximate line. If it is a ridge line, the process 705 is performed. If not), process 704 is executed. As shown in FIGS. 4 and 5, this determination is made to be a ridge line when the normal vectors of the start point and the end point are different values (FIG. 4), and an approximate line when they are the same value (FIG. 5). . The edge attribute table is completed by executing these processes for all the edges of all the surfaces.

When the above-mentioned treatment is applied to the cube shown in FIG. 2, it becomes as follows. Regarding sides V1 and V2, coordinates 1 and coordinates 2 are V1 and V2, respectively, and polygon ID1 and polygon ID2 are P1 and P2, respectively. Also from FIG. 4, the vertex of the polygon P1
The normal vector n1 of V1 and the normal vector n1 'of the vertex V1 of the polygon P2 have different directions, and the normal vector n2 of the vertex V2 of the polygon P1 and the normal vector of the vertex V2 of the polygon P2. Since the direction is different from the vector n2 ', the edge type is 1. On the other hand, in the case of the curved surface data given in FIG. 5, the side type is 2 in the broken line portion and the side type is 0 in the solid line portion.

Description of step 102: step 102
Is generation of an image subjected to hidden surface removal and smooth shading by the Z-buffer method, and the graphic data stored in the graphic data area 1003 is processed by the CPU 100.
1 converts it into a drawing command, sends this drawing command to the graphics processor 1005, the normal drawing unit 1006 in the graphics processor 1005 generates an image, and stores the color information in the frame memory 1009. For the display of polygons by the Z-buffer method, refer to the above New Media Technology Series Computer Graphics.

Description of step 103: step 103
Uses the Z-buffer method to generate a polygon ID image having the polygon ID displayed in each pixel as information instead of color information. FIG. 3 shows this polygonal ID image,
2 shows a display example of the cube shown in FIG. 2 viewed from a certain direction,
P1, P2, and P3 indicate polygon IDs of the part surrounded by the solid line.
This image generation is the same as the conventional image generation method. The CPU 1001 converts the graphic data stored in the graphic data area 1003 into a drawing command, and sends this drawing command to the graphics processor 1005. Normal drawing unit 10 in the normal drawing unit 1005
An image is generated in 06, and the polygon ID is stored in the polygon ID memory 1010 instead of the color information.

Description of steps 104 and 105: Next, the contour line and ridge line detection processing of step 104, step 10
The combination processing of No. 5 will be described. Before that, Fig. 1
Details of the contour line ridge line generation unit 1007 of 0 will be described with reference to FIG. 11. This includes a line drawing unit 1103, a surrounding pixel reading unit 1104, a contour line ridge line determination unit 1105, and a contour line ridge line writing unit 1106. FIG. 8 is a flowchart of a contour line / ridge line detection process.

First, in process 801, the CPU 1001 converts the side attribute table of the side i in the side attribute table area 1004 into a drawing command, and the graphics processor 1005.
The contour line ridge generation unit 1007 inside receives this command.

Next, the line drawing unit 1103 executes the pixel generation processing 802 for the side i. The line drawing unit 1103 receives the coordinates 1101 of the end point and the start point and generates a pixel address using a drawing algorithm (DDA or the like). Then, the surrounding pixel reading unit 1104 reads the polygon IDs of the pixel addresses corresponding to the eight pixels around the pixel position from the polygon ID memory 1010. Here, the eight pixels around the pixel position are the enlarged view 301 of FIG.
When the pixel position is 901, 901 of the square 902
8 pixels other than are shown.

Then, the contour line ridge determining unit 1105 compares the polygon ID of the surrounding 8 pixels read by the surrounding pixel reading unit 1104 with the polygon IDs 1 and 2 of the side attribute table received from the CPU 1001. Run. If neither of the polygon IDs 1 and 2 of the side attribute table is included in the surrounding 8 pixels, the contour line ridge determination unit 1105 does not issue a drawing command to the contour line ridge writing unit 1106, that is, does not display. The process 805 is executed. However, if one of them is included, the processing 807 of adding it to the image as an outline is executed, and if both are included, the edge type determination processing 804 is executed. If the value is 2, the process 805 of not displaying is executed, and in this case, the contour line ridge line determination unit 1105 issues a contour line or ridge line drawing command to the contour line ridge line writing unit 1106.

As an example of ridge line detection, an enlarged view of 301 in FIG. 3 is shown in FIG. In this figure, and are respectively P
The polygon IDs 1 and P2 are shown, and the straight line drawn from the lower left to the upper right corresponds to the side V1V2 in FIG. This side attribute table is registered in side 1 of FIG. It is now assumed that the side 1 in FIG. 6 is drawn and the pixel 901 in FIG. 9 is generated.
At this time, 8 pixels around the generated pixel are 8 pixels except 901 surrounded by a square 902. The pixel 901 includes both the polygon IDs 1 and 2 of the side attribute table of side 1 in the surrounding 8 pixels, and since the side type of this side is 1, it becomes a ridge.

By drawing only the contour lines and ridge lines detected by using this apparatus in the frame memory, a wire frame image with hidden lines removed can be created, and an image with smooth shading in the frame memory, If you combine this contour line and ridge line with a color different from other parts and write it,
An image in which the shape of an object is easy to understand can be generated.

If the above processing is performed for all sides, the contour line and the ridge line can be detected without mistake, and an image in which the object shape is easy to understand can be generated.

[0029]

As described above, according to the present invention, the data necessary for detecting the contour line and the ridge line is created and the contour line and the ridge line are detected, so that noise is not picked up by the differential value or the like. , There is no detection error. Further, since the contour line and the ridge line are treated as a straight line having a width of 1 pixel, these lines are not thickened.

[Brief description of drawings]

FIG. 1 is a diagram showing a flow of processing of the present invention.

FIG. 2 is a configuration diagram of a cube.

FIG. 3 is a diagram showing a polygon ID image.

FIG. 4 is a diagram showing data of a given cube.

FIG. 5 is a diagram showing data of a given curved surface.

FIG. 6 is a configuration diagram of an edge attribute table.

FIG. 7 is a diagram showing a flow of processing for creating an edge attribute table.

FIG. 8 is a diagram showing a flow of processing for detecting a contour line and a ridge line.

FIG. 9 is an enlarged view of 301.

FIG. 10 is a system configuration diagram showing an embodiment of the present invention.

FIG. 11 is a detailed view of a contour line / ridge line generation unit.

[Explanation of symbols]

Reference numeral 100 indicates the overall processing, 101 to 105 indicates the outline of the processing procedure of the present invention, 301 indicates the arrangement of the pixels of the ridge line, 701 to 708 indicates the processing procedure for creating the edge attribute table, 801 to 809 indicates the contour. 901 ... Pixels used as an example, 902 ... 8 pixels surrounding pixel 901, 1001 ... CPU, 1002 ... Main memory, 1003 ... Graphic data area, 1004 ... Edge attribute table area , 1005 ... Graphics processor, 1006 ... Normal drawing unit, 1007 ... Contour line ridge generation unit, 1008 ... Z-buffer, 1009 ... Frame memory, 1010 ... Polygon ID memory, 1011 ... Display device, 1012 ... System bus, 1101 , 1102 ... Data received by the contour line ridge generation unit, 1103 ... Line drawing unit, 1 04 ... peripheral pixel reading unit, 1105 ... contour ridge determination unit, 1106 ... contour ridge write unit.

Claims (8)

[Claims] 1. When displaying a three-dimensional object given by polygon approximation data as a two-dimensional image, which polygon is connected to the polygon approximation information, that is, which polygon on the polyhedron approximation data? A method to obtain information on whether polygons are in contact with each other, detect where the graphic display does not maintain the connection condition as a contour line, and display it as a contour line in a different color from other parts. 2. The method for detecting a contour line according to claim 1, wherein all the sides of all the given polygons are traced, and the information on the degree of connection between the polygons is associated with the sides of the polygon. A polygon identifier stored in pixels surrounding the pixel that is being traced is generated by generating an image in which the polygon identifier stored in each pixel of the screen is stored.
A method that determines whether the connection is maintained and uses the outline that is not maintained. 3. A method for determining the connection degree of an image storing the polygon identifier according to claim 2, wherein the connection degree is determined in pixel units, and two polygons connected to eight pixels around the pixel to be determined. If both are displayed with 1 pixel or more, it is determined that the connection is maintained, and if only one of the polygons is displayed with 1 pixel or more, it is not maintained. 4. When a three-dimensional object given by polygon approximation data is displayed as a two-dimensional image, it is classified whether the tangent line between polygons is originally an angular line or a line appearing by approximation, and is originally classified. A method in which only angular lines are detected as ridgelines and displayed as a ridgeline in a different color from other parts. 5. The method for classifying tangents between polygons according to claim 4, wherein there are two directional normals on the tangents between the polygons, and only one ridge is present. To classify as a line that appears by approximation. 6. A method for simultaneously realizing both the method for detecting and displaying a contour line according to claim 2 and the method for detecting and displaying a ridge line according to claim 4. 7. A graphic generation device and a display device for displaying a three-dimensional object given by polyhedral approximation data as a two-dimensional image, and means for converting the graphic data into a drawing command and receiving the drawing command. A graphics processor for generating a display screen, a means for sending a command thereto, a frame memory for storing color information for display, a means for displaying the color information of the frame memory and a display polygon. A memory for storing the polygon identifier for each pixel of the display screen, a means for generating polygon connection information from the given polyhedron approximation data in correspondence with the sides of the polygon, and a polygon connection condition. And the memory storing the polygon ID to detect the contour line or the ridge line, and add the contour line or the ridge line to the display image in a color different from that of the other portions, Figure generating apparatus characterized by having. 8. A means for detecting a contour line or a ridge line according to claim 7, and adding the contour line or the ridge line to a display image in a color different from that of other portions, the means for generating straight line pixels, and the generating means. Means for reading the polygon IDs of the pixels surrounding the selected pixel, and means for determining and detecting whether the polygon ID is a contour line or a ridge line by determining whether the polygon ID satisfies the information of the connection condition of the polygon. And a means for adding the contour line or the ridge line to a display image in a color different from that of other portions.