JP3367506B2 - Image processing apparatus and image processing method - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an image processing apparatus and an image processing method, and more particularly to an image processing apparatus and an image processing method capable of high-speed processing.

[0002]

2. Description of the Related Art One of three-dimensional graphics rendering processing methods is a partitioning processing method in which an image memory corresponding to a display screen is divided into tiles, which are the minimum units, and rendering processing is performed for each tile. In this tile division processing method, the polygon rectangular area including the entire area of the triangular polygon is set by referring to the coordinate information of each vertex of the triangular polygon, and the drawing processing is performed for each tile existing in the polygon rectangular area.

A conventional tile processing method will be described with reference to FIG. 18. 811, 812 to 821 to 831 in FIG.
Are the tiles described above, and P1 to P3 represent the vertices that form the triangular polygon 800. The coordinates of each vertex are P1 (x1, y1), P2 (x2, y2), P, respectively.
3 (x3, y3), and from these coordinates, each vertex P1
Upper left coordinates (Xmin, Y) of rectangle 801 including P3
min) and the lower right coordinates (Xmax, Ymax) are calculated. Here, the coordinate origin (0,0) is set in the upper left corner of the screen.

The tiles forming the rectangle 801 set in this way are 822, 823 to 827, 832 to 83.
7, ... 872 to 877 are drawn in this order.

[0005]

The conventional tile processing method described above uses the X coordinate and the Y coordinate of each vertex of a triangular polygon.
The minimum value and the maximum value of the coordinates are obtained, and the polygon processing is sequentially performed on the tiles in the polygon rectangular area set from the minimum value and the maximum value.

Therefore, when a large triangular polygon exists in the polygon rectangular area, generally, there are many tiles in the polygon rectangular area that do not need to be drawn. However, polygon processing is also performed on these tiles. For example, tiles 822, 823, 826, 827, 832, 837, 8 in FIG.
72 and the like are tiles located outside the triangular polygon 800 and are tiles that should not be originally drawn. However, the conventional tile processing method actually carries out drawing processing.

As the image to be drawn has recently become complicated,
The polygon shapes of polygons forming an image are diversified, and the amount of polygon data is increasing remarkably. Therefore, in image processing apparatuses and image processing methods that require real-time processing, there is a strong demand for high-speed drawing processing. However,
The conventional tile processing method has a problem in that the processing speed of the drawing processing is low because the drawing processing is performed up to the tile that originally does not require the drawing processing.

Therefore, an object of the present invention is to set a polygon rectangular area including all vertices forming polygon data, and tiles included in this polygon rectangular area are present inside or outside the polygon. It is an object of the present invention to provide an image processing device and an image processing method capable of performing high-speed drawing processing by determining whether or not the tiles existing outside the polygon are not drawn.

[0009]

Therefore, according to the image processing method of the present invention , rectangular tiles arranged in a matrix are used.
Image memory that is composed of
Image processing that draws image data including gons for each tile
A method of processing the polygons in the image memory.
Generate a polygon rectangular area that is an area containing
Information that is the information of the tiles existing in the polygon rectangular area
Tile information output step, and the tile information
And the polygon coordinate information to refer to the polygon rectangle.
A tile containing the polygon from the tile in the shape region
A drawing tile selection process for selecting a drawing tile is provided.
Well, if the polygon is a triangular polygon consisting of triangles,
In the drawing tile selection step,
Select a vertex and each of the x and y directions through this vertex
Polygon that divides the polygon rectangular area into four by a straight line
A rectangular area dividing step, and a second area adjacent to the first vertex.
Which of the four divided planes the vertices of
The second vertex determination information that is the determination information and outputs the determination information
Two-vertex determination step, and from the first vertex to the second vertex
Search for a third vertex adjacent to the second vertex towards
And the third vertex is the first vertex and the second vertex
Which of the planes is divided by the straight line passing through
Is determined and the third vertex determination information, which is the determination information, is output.
A third vertex determining step, the position coordinates of the first vertex and the
Referring to the second vertex determination information and the third vertex determination information,
An edge composed of the first vertex and the second vertex
For the first determination point for calculating the tile determination vertex
The point calculation step and the above-mentioned judgment in the third vertex judgment step
The plane in which the third vertex is present is the x direction passing through the second vertex.
Plane divided by each straight line in the direction and y direction
Which of the three vertices there is, the determination
Second second which outputs second third vertex determination information which is information
3 vertex determination step, position coordinates of the first vertex and the first vertex
See 2 vertex determination information and the 2nd 3rd vertex determination information.
The second vertex and the third vertex.
The edge, the third vertex, and the first vertex.
Calculate the tile judgment vertices for each edge
The second determination vertex calculating step of
Coordinate information and the triangle corresponding to the tile determination vertex
By referring to the coordinate information of the sides of the polygon, each tile judgment
The triangular polygon whose point corresponds to the tile determination vertex
Exists on a plane divided by a straight line containing the edges of
Whether or not the tile is determined, which is the determination information.
The inside / outside determination process of the tile determination vertex that outputs constant information, and
Refer to the inside / outside judgment information of the tile judgment apex,
Whether the vertices of the exist inside the triangular polygon
And a step of determining the inside / outside of a tile to be judged, wherein the drawing tile is drawn in the image memory, and tiles other than the drawing tile are not drawn in the image memory.

[0010] The image processing method according to the invention, Matricaria
Display image composed of rectangular tiles arranged in the shape of a box
Image data including polygons in the image memory corresponding to the surface
Is an image processing method for drawing for each tile,
This is the area containing the polygon in the image memory.
Generates a polygon rectangular area and exists in this polygon rectangular area.
It outputs tile information that is information of the existing tiles.
File selection step, the tile information and the coordinates of the polygon
Referring to information, the tiles in the polygon rectangular area
Select the drawing tile that is the tile containing the polygon from
And a drawing tile selection step for
It is a triangular polygon consisting of shapes, and the drawing tile selection
The step is to calculate the lengths of the three sides forming the triangular polygon.
And a step of calculating the added value of the lengths of these three sides,
Connect each vertex of the tile and the vertex of the triangle polygon
Calculate the length of the line segment for each vertex of the tile,
Calculating the added value of the lengths of the line segments,
The added value of the length of the three sides of the gon and the added value of the length of the line segment
There is a vertex of the tile that satisfies the following formula calculated based on
If present, the tile containing this vertex is
The tiles that satisfy the following equation
If there are no points, the corresponding tile is
It is characterized by having a process of not drawing in memory
It Addition value of length of 3 sides> Addition value of length of line segment> Length of 3 sides
Addition value / 2

[0011]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Next, embodiments of the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram showing an embodiment of an image processing apparatus of the present invention. It latches image data and x seat lengths x1, x2, x3 and y of each vertex of a triangular polygon.
Latch circuits 101 to 106 for latching the coordinates y1, y2, y3 respectively and outputting these data, and the coordinate x1
-X3 are compared with each other, and the maximum value xmax and the minimum value xmi
From the comparison circuit 11 that outputs n, the comparison circuit 12 that compares the coordinates y1 to y3 with each other and outputs the maximum value ymax and the minimum value ymin, and the maximum value xmax and the minimum value xmin,
With tile as a unit, the maximum value Xmax and the minimum value Xmin in the x direction of a polygon rectangular area in which a triangular polygon exists
From the maximum value ymax and the minimum value ymin, and the maximum value Yma in the y direction of the polygon rectangular area in which the triangular polygons exist, in units of tiles.
x area and a Y area generation circuit 22 for generating a minimum value Ymin.

In the image processing apparatus according to the embodiment of the present invention, the maximum value Xma output from the X area generation circuit 21 is set.
A polygon rectangular area that generates a polygon rectangular area including a triangular polygon from x and the minimum value Xmin, and the maximum value Ymax and the minimum value Ymin output from the Y area generation circuit 22, and sequentially outputs tile information of the polygon rectangular area. A generation circuit 31 is provided.

Here, each vertex coordinate forming a triangular polygon is input from the comparison circuits 11 and 12, the X area generating circuit 21, the Y area generating circuit 22, and the polygon rectangular area generating circuit 31, and the triangular polygon exists. A tile selection circuit 51 that determines a tile in the polygon rectangular area and outputs tile information such as a tile number for this tile is configured.

Further, the image processing apparatus according to the embodiment of the present invention is arranged such that x seat lengths x1, x2 of respective vertices of a triangular polygon.
By inputting x3 and y coordinates y1, y2, y3 and the tile information output from the tile selection circuit 51, only tiles in the polygon rectangular area, which are drawing target tiles including polygons, are selected, Drawing tile selection circuit 41 that outputs information on the selected tile, that is, drawing tile information.
Is equipped with.

Next, the operation of the image processing apparatus according to the embodiment of the present invention shown in FIG. 1 will be specifically described with reference to FIG.

FIG. 3 is an image processing apparatus of the present invention in which image data including triangular polygons 30 is drawn for each tile in an image memory which is composed of rectangular tiles arranged in a matrix and corresponds to a display screen. 3 is an explanatory diagram showing tiles and triangular polygons in a memory. FIG.

In FIG. 3, 30 is three vertices P1 (x1,
y1, z1), P2 (x2, y2, z2), P3 (x
3, y3, z3) and a triangular polygon. The data of this triangular polygon 30 is the latch circuit 1
01 to 106, these latch circuits 101
To 106 output two-dimensional coordinates x1 to x3 and y1 to y3 of the vertex coordinates of the triangular polygon 30, respectively.

Next, the comparison circuit 11 compares the coordinates x1 to x3 with each other and outputs the maximum value xmax and the minimum value xmin of the coordinates x1 to x3. In FIG. 3, x3 is xmax and x2 is xmin.

Similarly, the comparison circuit 12 compares the coordinates y1 to y3 with each other and outputs the maximum value ymax and the minimum value ymin of the coordinates y1 to y3. In FIG. 3, y3 is ymax
And y1 becomes ymin. Here, the upper left corner is the origin of the x-axis and the y-axis, the right direction is the positive direction of the x-axis, and the downward direction is the positive direction of the y-axis.

Next, the X area generation circuit 21 determines the maximum value xma.
From x and the minimum value xmin, the maximum value Xmax and the minimum value Xmin in the x direction of the polygon rectangular area in which the triangular polygon exists are generated in units of tiles.

That is, the x coordinate of the left side of the tile where the vertex P2 exists is Xmin, the x coordinate of the right side of the tile where the vertex P3 exists is Xmax, and the range of Xmin to Xmax is set as the x region of the polygon rectangular region. In this way, the x coordinate of the left side of the tile including the vertex corresponding to the minimum value xmin is set to the minimum value Xmin, and the maximum value xmax is set.
The x coordinate of the right side of the tile including the vertex corresponding to is set to the maximum value Xmax.

Similarly, the y coordinate of the upper side of the tile having the vertex P1 is Ymin, the y coordinate of the lower side of the tile having the vertex P3 is Ymax, and the range of Ymin to Ymax is set as the y region of the polygon rectangular region. To do. In this way, the y coordinate of the upper side of the tile including the vertex corresponding to the minimum value ymin is set to the minimum value Ymin, and the maximum value ymax
The y coordinate of the lower side of the tile including the vertex corresponding to is set to the maximum value Ymax.

Next, the polygon rectangular area generation circuit 31 outputs X
From the maximum value Xmax and the minimum value Xmin output from the area generation circuit 21, and the maximum value Ymax and the minimum value Ymin output from the Y area generation circuit 22, a tile in the polygon rectangular area in which the triangular polygon exists is determined, The tile information such as the tile number of this tile is output.

In FIG. 3, a polygon rectangular area 300 is generated from the x area and the y area.
The tile number is added to the tile existing in 00. That is, the row of the tile including the vertex P1 has 31 in order.
The tile numbers 1, 312 to 312 are added, and the tile number 314 is added to the vertex P1.

Similarly, the tile number 331 is added to the vertex P2, and the tile number 366 is added to the vertex P3.

Next, the drawing tile selection circuit 41 causes the x seat lengths x1, x2, x3 and y of the respective vertices of the triangular polygon 30.
By inputting the coordinates y1, y2, y3 and the tile number output from the tile selection circuit 51, the polygon rectangular area 30
Only tiles within 0 that are drawing targets in which triangular polygon data exist are selected, and information on the selected tiles, for example, drawing tile numbers are output. In FIG. 3, tile numbers 313, 314, 322 to 325, 33 are used.
1-335, 342-345, 353-356, 36
5, 366 are tiles to be drawn, and the drawing tile selection circuit 41 outputs information on these selected tiles, for example, drawing tile numbers.

Next, a drawing circuit (not shown) refers to the drawing tile number output from the drawing tile selection circuit 41, and performs drawing processing in the image memory for the tile corresponding to this drawing tile number. .

As described above, the image processing apparatus according to the embodiment of the present invention sets a polygon rectangular area that includes all the vertices that form a polygon, and tiles included in this polygon rectangular area exist inside the polygon. It is possible to perform the drawing process at high speed by determining whether the tile exists outside the polygon and not performing the drawing process in the image memory for the tile existing outside the polygon.

Next, with reference to FIG. 2, the circuit configuration of the drawing tile selection circuit 41 constituting the image processing apparatus of the present invention will be described.

The drawing tile selection circuit 41 uses the x seat lengths x1, x2, x3 and the y coordinate y of each vertex of the triangular polygon.
1, y2, y3 and tile information are input, the tile determination vertices that are the vertices of the tile closest to each side of the triangular polygon are calculated for each side, and the tiles are output as tile determination vertex information. A vertex determination circuit 411,
By inputting tile determination vertex information and tile information, it is determined for each side of the triangular polygon which of the planes the tile determination vertex belongs to is divided by the corresponding polygon sides, and tile determination is performed. When it is determined that the vertex is inside the triangle polygon, the tile to which the tile determination vertex belongs is selected as the tile to be drawn, the drawing tile information is output, and when it is determined that the tile determination vertex is outside the triangle polygon, A tile determination circuit 41 that selects a tile to which this tile determination vertex belongs as a tile that is not drawn.
2 and.

Next, an image processing method according to the first embodiment of the present invention will be described with reference to FIGS.

FIG. 4 is a flow chart showing an image processing method according to the first embodiment of the present invention. In step S1, the screen display sizes Lx, Ly, tile sizes Tx, Ty, etc. are set. Here, Lx and Ly represent the sizes of the screen in the x direction and the y direction, respectively, and Tx and Ty represent the sizes of the tile in the x direction and the y direction, respectively.
Image data including triangular polygons is drawn for each tile in an image memory that is composed of rectangular tiles arranged in a matrix and corresponds to a display screen.

Next, in step S2, x on the display screen
The number of tiles in the direction nx and the number of tiles in the y direction ny are calculated by the following equation.

Nx = Lx / Tx, ny = Ly / Ty (1) That is, the image memory corresponding to the display screen is n in the x direction.
It is composed of tiles arranged in x and ny in the y direction.

Next, in step S3, the three vertex coordinates P1 (x1, y1), P2 (x
2, y2) and P3 (x3, y3) are input.

Subsequently, in step S4, the tile selection circuit 5
By 1, all tiles in the polygon rectangular area including the triangular polygon are determined, and the tile number for this tile is generated.

Next, in step S51, the vertices forming the tile are selected. Then, in step S52, two vertices of the three vertices of the triangular polygon are selected, and the plane is divided into two by a straight line 1 connecting these vertices.

Next, in step S53, step S
In which of the planes divided in step S52 the vertex selected in 51 exists, that is, in the same plane as the third vertex of the triangular polygon that is not on the straight line l, or in the opposite direction to the straight line l. It is determined whether or not it exists in, and this determination information is stored.

Next, in step S54, it is determined whether or not the processing of step S53 is completed for the three sides of the triangular polygon. If it is determined that the processing is not completed,
Returning to step S52, the next two vertices are selected, the processes of step S52 and subsequent steps are performed, and when it is determined in step S54 that the process of step S53 is completed for the three sides of the triangular polygon, the next step The process of S55 is performed.

Next, in step S55, it is determined whether or not the processes of steps S52 to S54 have been completed for all the vertices of the tile. If it is determined that the processes have not been completed, the process returns to step S51. And select the next vertex forming the tile, and step S52 to step S52.
When it is determined that the process of 54 is completed, the process of the next step S56 is performed.

In step S56, step S53
Based on the determination information calculated in step 1, it is determined whether or not the apex of the tile included inside the triangular polygon exists.
Specifically, when the determination condition that the vertices that form the tile are on the same plane as the third vertex that is not on the side that forms the triangular polygon is satisfied for three different sides,
It can be determined that this vertex is included inside the triangular polygon.

When it is determined in step S56 that the vertices of tiles included in the triangular polygon are present, in step S57 a tile satisfying the conditions of step S56 is selected as a drawing tile to be drawn,
If it is determined in step S56 that the vertices of the tile included inside the triangular polygon do not exist, in step S58, the steps S51 to S are performed.
The tile determined in 56 is selected as a non-drawing tile for which drawing is not performed.

Then, in step S59, information about the drawing tile, for example, drawing tile information such as the drawing tile number is output, and in the next processing step not shown in FIG.
Drawing processing is performed on the drawing tile.

Next, the processing of step S4 will be described with reference to the flowchart shown in FIG.

In step S41, the comparison circuit 11 shown in FIG.
Compares the three vertex coordinates of a triangular polygon with each other,
The maximum value xmax and the minimum value xmin in the x direction are calculated.

Next, in step S42, the X area generation circuit 21 shown in FIG. 1 sets the maximum value X in the x direction in tile units in the polygon rectangular area including the triangular polygon.
Calculate max and minimum value Xmin.

Similarly, in step S43, the comparison circuit 12 shown in FIG. 1 compares the three vertex coordinates of the triangular polygon with each other to calculate the maximum value ymax and the minimum value ymin in the y direction.

Next, at step S44, the Y area generation circuit 22 shown in FIG. 1 determines the maximum value Y in the y direction in tile units in the polygon rectangular area including the triangular polygon.
Calculate max and minimum value Ymin.

Then, in step S45, step S42
The maximum value Xmax and the minimum value Xmin calculated in step S44, and the maximum value Ymax and the minimum value Ymi calculated in step S44.
A polygon rectangular area including a triangular polygon is set based on n, and tile information such as tile numbers for all tiles in the set polygon rectangular area is output.

Next, in the processing flow of FIG. 4, the processing content for determining whether the tile is inside or outside the triangular polygon will be specifically described with reference to FIG.

In FIG. 6, 60 is a vertex P1 (x1, y
1), P2 (x2, y2), P3 (x3, y3), which is a triangular polygon, where the straight line connecting the vertices P1 and P2 is l1, the straight line connecting the vertices P2 and P3 is l2, and the vertices P3 and P1 are P1. Let the straight line connecting the lines be l3. Further, as shown in FIG. 6, the vertices existing inside the triangular polygon 60 and forming the tile are w (x ″, y ″), and the triangular polygon 60
The vertices that are outside of and that make up the tile are u (x, y),
Let v (x ', y').

In step S51 of FIG. 4, the vertex u of the tile is
One of (x, y), v (x ', y'), w (x ", y"), for example u (x, y), is selected, and then, in step S52, the vertices P1 and P2 are selected. A straight line l1 is generated and the plane is divided into two by the straight line l1.

Next, in step S53, the vertex u (x, y)
Is determined not to be on the same plane as the third vertex P3 which is not on the side forming the triangular polygon 60, and this determination information is stored.

Here, which one of the planes the vertex u (x, y) on the display screen is divided by the straight line l1 connecting the vertex P1 (x1, y1) and the vertex P2 (x2, y2) belongs to. Whether or not is determined by the following inequality.

Y> ((y1-y2) / (x1-x2)). (X-x1) + y1 .. (2) If the point u (x, y) satisfies the above equation, the point u (x, y)
Is determined to be within the range of the shaded portion in FIG. 6, and when the above expression is not satisfied, it is determined to be on the plane opposite to the straight line l1 indicated by the shaded portion. In this way, which of the planes divided by the straight line belongs to can be easily determined using the inequality similar to the equation (2).

Next, in step S51, the vertex v of the tile
If (x ', y') or w (x ", y") is selected, these vertices v (x ',
It is determined that y ′) and w (x ″, y ″) exist on the same plane as the third vertex P3 that is not on the side forming the triangular polygon 60, and this determination information is stored.

Next, in step S54, the triangular polygon 6
Since it is determined that the process of step S53 has not been completed for the three sides of 0, the process returns to step S52 and the straight line l
2 is generated and the plane is divided into two by the straight line l2.

In step S53, the vertex v (x ', y')
Is determined not to be on the same plane as the third vertex P1 which does not exist on the side 12 of the triangular polygon 60, but the vertex w (x ″, y ″) is on the same plane as the third vertex P1. It is determined to exist, and these pieces of determination information are stored.

Subsequently, in step S54, since it is determined that the processing of step S53 has not been completed for the three sides of the triangular polygon 60, the process returns to step S52 to generate the straight line l3, and the plane is defined by the straight line l3. Divide into two.

Next, in step S53, the vertex w (x ",
It is determined that y ″) exists on the same plane as the third vertex P2 that does not exist on the side l3 forming the triangular polygon 60, and this determination information is stored.

Next, in step S54, the straight line l1,
It is determined that the processes of steps S52 and S53 for 12 and 13 are finished, and the process of the next step S55 is performed.

Next, in step S55, when it is determined that the processes in steps S52 to S54 have been completed for all the vertices of the tile, in step S56,
Based on the determination information calculated in step S53, it is determined whether or not the apex of the tile included inside the triangular polygon 60 exists. The vertex w (x ″, y ″) satisfies the determination condition that the vertex w (x ″, y ″) exists on the same plane as the third vertex that does not exist on the side forming the triangular polygon 60, for the three different sides. , Y ″) can be determined to be included inside the triangular polygon 60.

As described above, the processes of steps S51 to S55 are sequentially executed for the four vertices forming the tile, and the determination process of step S56 is performed based on the determination information obtained in step S53.

In step S56, the vertex w (x ",
Since it is determined that y ″) is included inside the triangular polygon 60, in step S57, the vertex w (x ″,
The tile formed by y ″) is selected as the drawing tile.

Next, an image processing method according to the second embodiment of the present invention will be described with reference to FIGS.

FIG. 7 is a flow chart showing an image processing method according to the second embodiment of the present invention.
At 71, for each side of the triangular polygon, the tile determination vertex which is the closest to the side of the triangular polygon among the respective vertices of the tile is calculated.

Explaining with reference to FIG. 8, the vertices P1 to P1
Straight lines l1 to l3 including each side of a triangular polygon having 3
On the other hand, the tile determination vertices are as follows. That is,
The tile determination vertex for the straight line l1 is c, and the straight line l2
The tile determination apex for the line is a ′, and the tile determination apex for the straight line l3 is b ″.

Next, in step S72 of FIG. 7, the positional relationship of the tile determination vertices with respect to each side of the triangular polygon is determined.

Referring to FIG. 9, from the positional relationship between the straight line l1 connecting the vertices P1 and P2 of the triangular polygon and the tile determination vertices of the tiles 81, 91, 92, the tile determination vertex c of the tile 81 is divided by the straight line l1. It is determined that the tiles 91 and 92 are located in the left plane, and the tile determination vertices of the tiles 91 and 92 are the same planes to the right of the planes divided by the straight line l1, that is, the planes in which the vertex P3 exists. Is determined to exist.

Next, in step S73 of FIG. 7, it is determined whether the tile is inside or outside the triangular polygon based on the result of the determination in step 72 for the three sides forming the triangular polygon.

Next, referring to FIGS. 10 and 11, FIG.
The processing flow of is specifically described.

First, as shown in FIG. 11A, in step 101, the first vertex of a triangular polygon is selected, and the polygon rectangular area is divided into four by the straight lines in the x and y directions passing through this vertex (A). ~ D). Here, the horizontal direction and the vertical direction are the x-axis and the y-axis, respectively, and the right side is the x-axis.
The positive direction of the axis is defined as the positive direction of the y-axis, and the lower left corner is defined as the coordinate origin (0,0). Further, the first vertex is selected under the condition that the y coordinate of the first vertex is smaller than the y coordinate of the second vertex selected next.

Next, in step S102 shown in FIG. 10, when the vertices of the triangular polygon are searched counterclockwise, it is determined where the second vertex is in the four-divided area. As shown in FIGS. 11B and 11C, the second
The vertex P2 (x2, y2) of P exists in either the region B or the region C.

Next, in step 103 in FIG. 10, it is determined which of the two planes the third vertex of the triangular polygon is divided by the straight line passing through the first vertex and the second vertex. To do.

In the case of FIG. 11B, the vertices of the triangular polygon are sequentially searched in the counterclockwise direction, so that the third vertex P3 (x3, y3) of the triangular polygon is the shaded area in FIG. 11D. , And similarly in the case of FIG. 11 (c), the third
The vertex P3 (x3, y3) exists in the shaded area of FIG. 11 (e).

Next, in step S104 of FIG.
All tile determination vertices existing in the polygon rectangular area are calculated with respect to the side formed by the vertices P1 and P2 of the triangular polygon. Referring to FIG. 12A, x1> x2
, The tile vertex c of the tiles 121 and 122 becomes the tile determination vertex, and when x1 ≦ x2, the tiles 123 and 1
The tile vertex d of 24 becomes the tile determination vertex.

Next, in step S105 of FIG.
The plane in which the third apex existing in the processing step S103 exists is further divided by each straight line in the x direction and the y direction passing through the apex P2.
The determination information indicating whether 3 exists is output. FIG.
As shown in FIG. 12A, the shaded area in FIG.
It is divided into three regions 131 to 133 by the straight lines in the x direction and the y direction that pass through the vertex P2.

Next, in step S106 of FIG.
The tile determination vertices are calculated for the side formed by the vertices P2 and P3 of the triangular polygon. With reference to FIG. 13A, when the vertex P3 (x3, y3) exists in the area 131, that is, when y2 <y3 and x2> x3, the tile determination vertex is c and the vertex P3 ′ in the area 132.
When (x3 ′, y3 ′) exists, that is, y2 <y
If 3 ′ and x2 ≦ x3 ′, the tile determination vertex is d, and if the area 133 has a vertex P3 ″ (x3 ″, y3 ″), that is, y2 ≧ y3 ″ and x2 ≦ x3 ″.
In this case, the tile determination vertex is a.

Next, in step S107 of FIG.
The tile determination vertices are calculated with respect to the side formed by the vertices P3 and P1 of the triangular polygon. Referring to FIG. 13A, x3 ≦ for the side connecting the vertices P3 and P1.
The tile determination vertex is a when x1 and the tile determination vertex is b when x3> x1.

Similarly, in the case of FIG. 13B, y2 <y3 and x2 ≦ x with respect to the side connecting the vertices P2 and P3.
When 3, the tile determination vertex is d, when y2 ≧ y3 and x2 ≦ x3, the tile determination vertex is a, and y2 ≧ y
When 3 and x2> x3, the tile determination vertex is b.

Further, with respect to the side connecting the vertices P3 and P1, the tile determination vertex is d when x3 ≦ x1, and x3
When> x1, the tile determination vertex is c.

As described above, step S in FIG.
101 to step S107 are step S71 in FIG.
Corresponds to the processing flow of. The tile determination vertices for the sides P1P2, P2P3, P3P1 forming the triangular polygon described above are summarized as shown in FIG.

Next, the determination method of step S72 of FIG. 7 will be described.

The vertices Pm (x
The equation of the straight line connecting (m, ym, zm) and Pn (xn, yn, zn) is as the following equation (3).

Y1-yn = ((yn-ym) / (xn-xm)). (X-xn). (3) Further, the tile determination vertex (xt,
The equation of a straight line passing through yt) is as shown in the following equation (4).

Y2-yt = ((yn-ym) / (xn-xm)). (X-xt) .. (4) Therefore, from the equations (3) and (4), the y intercept with x = 0 is obtained. The positional relationship between the side PmPn and the tile determination vertex can be determined based on the magnitude relationship. Specifically, (3),
By setting y = 0 in the equation (4) and calculating y1-y2, the determination equation D = (ym-yt) (xn-xm)-(yn
The positional relationship of the tile determination vertices with respect to each side of the triangular polygon can be determined by the positive / negative determination of -ym) (xn-xt). That is, with reference to FIG. 15, the positional relationship of the tile determination vertices with respect to each side is determined.

For example, in FIG. 14, x1 ≦ for the P1P2 side.
In the case of x2, the tile determination vertex is d. Therefore, the vertex P
The determination expressions D and (xn-xm) are calculated from the coordinates of 1 and P2, and the determination result is calculated from FIG.

This is repeated for the P2P3 side and the P3P1 side, and if the three determination results are within the polygon, it is determined that the tile and the triangular polygon overlap.
It is selected as a drawing tile in step S57 of FIG.
If even one is determined to be outside the polygon, it is determined that the tile and the triangular polygon do not overlap each other, and the tile is selected as a non-drawing tile in step S56 of FIG.

The image processing method of the second embodiment according to the present invention is
A procedure for calculating the tile determination vertices in different cases is necessary, and this procedure is more complicated than the image processing method of the first embodiment. However, unlike the image processing method of the first embodiment, it is not necessary to make determinations for all the vertices of a tile three times each, and only the tile determination vertices are considered as edges that form a triangular polygon. Since the positional relationship of is determined, the overall processing can be performed at high speed.

In the above description, the vertices of the triangular polygon are sequentially searched in the counterclockwise direction, but the same processing can be performed in the clockwise search.

Next, an image processing method according to the third embodiment of the present invention will be described with reference to FIGS.
It should be noted that common reference characters / numerals are attached to components common to FIG.

FIG. 16 is a flow chart showing the image processing method of the third embodiment according to the present invention. Since the processes from step S1 to step S4 are the same as those in FIG. 4, the description thereof will be omitted. The description will be given from step S161.

At step S161, the vertices P1, P2, P
The lengths a and b of each side of a triangular polygon composed of 3
c and the added value (a + b + c) thereof are calculated.

Next, in step S162, the lengths t11 to t13, ... Of the line segments between vertices, which are line segments connecting the four vertices t1 to t4 of the tile and the vertices P1 to P3 of the triangular polygon.
t41 to t43 and the sum of the lengths of the line segments between the vertices (t11 +
t12 + t13) to (t41 + t42 + t43) are calculated.

Next, in step S163, it is determined whether or not there is a vertex satisfying the following expression among the four vertices of the tile.

A + b + c> ti1 + ti2 + ti3> (a + b + c) / 2 (5) where i = 1 to 4 and tij is the i-th vertex of the tile,
It is the length of the line segment between the j-th vertex of the triangular polygon and the vertex.

If it is determined in step S163 that among the four vertices of the tile, a vertex satisfying the equation (5) exists, it can be determined that a vertex satisfying the equation (5) exists inside the triangular polygon. In step S164,
A tile including a vertex that satisfies the expression (5) is selected as a drawing tile.

If it is determined in step S163 that none of the four vertices of the tile satisfy the expression (5), it can be determined that all four vertices of the tile are outside the triangular polygon. Step S165
Is selected as a non-drawing tile.

Next, the processing contents described above will be described in detail with reference to FIG. 17. The vertices P1 (x1, y1), P2
Let the lengths of the three sides of the triangular polygon composed of (x2, y2) and P3 (x3, y3) be a, b, and c, respectively. In addition, the vertex t (x, y) of the tile and the vertices P1 and P
The length of the line segment generated by connecting 2 and P3 is t1
1 + t12 + t13.

Here, the lengths a, b, c, t11, t1
2, t13 can be calculated by the following equation (6).

A = square root ((x1-x2) ² + (y1-y2) ² ) t11 = square root ((x1-x) ² + (y1-y) ² ) ... (6) Length b, c , T12, t13 can be calculated in the same manner as in the equation (6).

The vertex t (x, y) is determined by step S in FIG.
Since it is determined in step 163 that the expression (6) is satisfied, the tile including the vertex t (x, y) is selected as the drawing tile in step S164.

The image processing method according to this embodiment has a feature that the processing speed can be increased because the judgment condition is simple.

In the above description, the polygon has been described by taking a triangular polygon as an example. However, the image processing apparatus and the image processing method according to the present invention can be similarly applied to a polygonal polygon having a quadrangle or more.

[0106]

As described above, according to the image processing apparatus and the image processing method of the present invention, a polygon rectangular area including all vertices forming a polygon is set, and tiles included in this polygon rectangular area are polygons. It is possible to perform high-speed drawing processing by determining whether the tiles are inside or outside and not performing drawing processing for tiles outside the polygon. When the triangular polygons shown in FIG. 3 are input as image data to the latch circuits 101 to 106 of FIG. 1, the total number of tiles included in the polygon rectangular area is 6 × 6 = 36, but there are 14 non-drawing tiles. With these non-drawing tiles, the image processing apparatus and the image processing method according to the present invention do not perform the drawing processing, so that a performance improvement of about 40% is expected compared to the conventional image processing apparatus and the image processing method.

[Brief description of drawings]

FIG. 1 is a block diagram showing an embodiment of an image processing apparatus of the present invention.

FIG. 2 is a block diagram showing an internal circuit of a drawing tile selection circuit 41 of FIG.

FIG. 3 is an explanatory diagram for explaining processing of an image processing apparatus and an image processing method according to the present invention.

FIG. 4 is a flowchart for explaining an image processing method according to the first embodiment of the present invention.

5 is a detailed flowchart for explaining the process in step S4 of FIG.

FIG. 6 is an explanatory diagram illustrating an image processing method according to the first embodiment of the present invention.

FIG. 7 is a flowchart illustrating an image processing method according to a second embodiment of the present invention.

FIG. 8 is an explanatory diagram illustrating an image processing method according to a second embodiment of the present invention.

FIG. 9 is an explanatory diagram illustrating an image processing method according to a second embodiment of the present invention.

FIG. 10 is a flowchart for explaining detailed processing contents of step S71 of FIG.

FIG. 11 is an explanatory diagram for explaining the processing content of step S71 of FIG.

FIG. 12 is an explanatory diagram for explaining the processing content of step S71 of FIG.

FIG. 13 is an explanatory diagram for explaining the processing content of step S71 of FIG. 7.

FIG. 14 is an explanatory diagram for explaining the processing content of step S71 of FIG.

FIG. 15 is an explanatory diagram for explaining the processing content of step S73 of FIG. 7.

FIG. 16 is a flowchart illustrating an image processing method according to a third embodiment of the present invention.

FIG. 17 is an explanatory diagram illustrating a process of the image processing method according to the third embodiment of the present invention.

FIG. 18 is an explanatory diagram illustrating a process of a conventional image processing method.

[Explanation of symbols]

101 to 106 Latch circuits 11 and 12 Comparison circuit 21 X region generation circuit 22 Y region generation circuit 30 and 800 Triangle polygon 31 Polygon rectangular region generation circuit 41 Drawing tile selection circuit 411 Tile vertex determination circuit 412 Tile determination circuit 51 Tile selection circuit 300 Polygon rectangular areas 81-83, 91, 92, 121-124, 311-3
15, 321 to 326, 331 to 335, 341 to 34
5,353-356,361-366,811-81
3,821-827,831-832,871-873
Tiles 131-133, 134-136 areas

─────────────────────────────────────────────────── --- Continuation of the front page (56) Reference JP-A-5-290175 (JP, A) JP-A-7-152357 (JP, A) JP-A-8-77367 (JP, A) JP-A-8- 293021 (JP, A) JP 9-16144 (JP, A) JP 9-161085 (JP, A) JP 10-207766 (JP, A) JP 2000-149055 (JP, A) Open 2000-338959 (JP, A) Special table 4-501777 (JP, A) Special table 8-502845 (JP, A) (58) Fields surveyed (Int.Cl. ⁷ , DB name) G06T 15 / 00 100 JISST file (JOIS)

Claims (2)

(57) [Claims] 1. A rectangular tie arranged in a matrix.
Image memory that is composed of
Image processing that draws image data including gons for each tile
In the area including the polygon in the image memory,
Generate a certain polygon rectangular area,
The tile information that is the information of the tile existing in
A tile selection step that, with reference to the coordinate information of the tile information and the polygon,
From the tiles in the polygon rectangular area to the polygon
Select a drawing tile that is a tile that contains
A-option step, said polygon is a triangle polygon consisting of a triangle, the rendering tile selection process, first vertex of the polygon
And select each straight line in the x and y directions that passes through this vertex
The polygon rectangular area that divides the polygon rectangular area into four
Shape region dividing step, and the second vertex adjacent to the first vertex is divided into four.
It is the judgment information by judging which of the two existing planes exists.
A second apex determination step of outputting second apex determination information, and the second apex toward the second apex from the first apex
Search for a third vertex adjacent to the vertex of
Split by a straight line passing through the first vertex and the second vertex
It is determined which of the planes that exist and the judgment information
A third vertex determining step of outputting certain third vertex determining information,
The position coordinates of the first vertex and the second vertex determination information and
And the third vertex determination information, the first vertex and
The tile with respect to the side composed of the second vertex
There is a first determination vertex calculating step of calculating a determination vertex and the third vertex determined in the third vertex determination step.
The existing plane is defined as the x direction and the y direction passing through the second vertex.
Which is divided by each straight line of
It is determined whether there is a third vertex,
Second third vertex determining step of outputting third vertex determining information of
And the position coordinates of the first vertex, the second vertex determination information, and
And the second third vertex determination information, the second
An edge composed of a vertex and the third vertex and the third edge
For the edge consisting of the vertex of and the first vertex
And a second determination vertex for calculating each of the tile determination vertices.
The calculation step, the coordinate information of each tile determination vertex, and the tile determination vertex
Refer to the coordinate information of the side of the triangular polygon corresponding to the point
And each tile determination vertex corresponds to the tile determination vertex
Is divided by a straight line including the sides of the triangular polygon
It is the judgment information by judging which of the two existing planes exists.
Tile judgment The tile judgment vertex that outputs the inside / outside judgment information of the vertex
By referring to the inside / outside determination step of the point and the inside / outside determination information of the tile determination vertex,
Whether the vertex of the rule exists inside the triangular polygon
And a step of determining the inside / outside of the tile, the drawing tile is drawn in the image memory, and the drawing tile is drawn.
For tiles other than tiles, draw in the image memory
An image processing method characterized by not doing . 2. A rectangular tie arranged in a matrix.
Image memory that is composed of
Image processing that draws image data including gons for each tile
In the area including the polygon in the image memory,
Generate a certain polygon rectangular area,
The tile information that is the information of the tile existing in
A tile selection step that, with reference to the coordinate information of the tile information and the polygon,
From the tiles in the polygon rectangular area to the polygon
Select a drawing tile that is a tile that contains
A selecting step , wherein the polygon is a triangular polygon consisting of triangles, and the drawing tile selecting step configures the triangular polygon.
Calculate the length of the three sides, and add the values of these three sides
The calculation process and the vertices of the tile and the vertices of the triangular polygon are connected.
The length of the line segment is calculated for each vertex of the tile,
Calculating the added value of the lengths of the line segments, the added value of the lengths of the three sides of the triangular polygon, and the line segments.
The following equation calculated based on the added value of the length of
If there is an apex of the
Selected as the drawing tile and satisfies the following equation
If the top point of the tile does not exist, the corresponding said data
Image is not drawn in the image memory.
An image processing method characterized by: Addition value of length of 3 sides> Addition value of length of line segment> Length of 3 sides
Addition value / 2