JPH0368428B2 - - Google Patents

Description

[Detailed Description of the Invention] <Industrial Application Field> The present invention relates to a digital figure data processing method that fills the inside of the figure with a designated color for digital figure data such as a polygon given from a host computer. This is related to the filling method.

<Prior art> In various fields of processing digital figures, the interior of so-called general polygons including concave polygons (a) and polygons with holes (b) as shown in Fig. 6 is used. It is often necessary to quickly fill in a specified color.

In the fields of CAD, CG, etc., the method of filling the inside of a polygon is generally used, for example, “Fundamentals of Interactive Computer
Graphics”JDFoley/A.Van Dam Addison−
Area-filling algorithms, such as those described in Wesley, 1982, are often used.

This area painting algorithm imports boundary line figures (closed curve polygons) as shown in Fig. 6 a and b into the image memory, and sets one point inside the closed curve as a seed point P as shown in Fig. 6 c and d. ₁ and _P2 , and pixels adjacent to the seed points _P1 and _P2 are sequentially filled in.

In this method, the algorithm itself is simple and suitable for high-speed processing, but the seed point for filling in the inside of the polygon is specified using a pointing device such as a light pen or mouse each time the filling process is performed. must give. . Therefore, the method using this filling algorithm requires the work of specifying seed points, and it is not possible to quickly fill the interior of a general polygon.

<Problems to be Solved by the Invention> The problems to be solved by the present invention are to automatically generate seed points for polygons to be filled, and to rapidly fill the interior of general polygons. The purpose is to realize a method that can crush them.

<Means for Solving the Problems> The present invention solves the above-mentioned problems in a digital figure filling method for filling the inside of polygonal digital figure data given from a host computer with a specified color. (b) A procedure for determining the first circumscribed rectangle from the vertex coordinates of the given polygon data and defining it as a white pixel set on the work memory; (c) raster scanning an area corresponding to the first circumscribed rectangle on the work memory to form a black pixel area by sequentially connecting a series of vertices with four connected line segments; Find the point where a pixel changes to a white pixel, use this change point as a starting point, trace the boundary of the white pixel area adjacent to the polygonal boundary line found in (b), and calculate the second boundary line of this white pixel area. (d) a step of comparing the positional relationship between the second circumscribed rectangle and the first circumscribed rectangle; and (e) a step of determining whether the second circumscribed rectangle is included in the first circumscribed rectangle. If not, repeat the procedure from (c), and if the second circumscribed rectangle is included in the first circumscribed rectangle, the workpiece is A procedure for changing the inside of the boundary line of a white pixel area inside the memory into black pixels, and (f) Raster scanning of the first circumscribed rectangle defined in the work memory and coordinate positions corresponding to all black pixels. A method for filling in a digital figure, comprising: a procedure for writing prespecified color information into a color image memory section; and a method for filling in a digital figure.

<Embodiment> FIG. 1 is a block diagram of an apparatus suitable for implementing the digital image filling method of the present invention.

In this figure, 1 is a host computer interface circuit, 2 is a segment buffer into which data related to the figure to be displayed (for example, commands, coordinate data, color information, etc.) is written from the host computer interface circuit 1, and 3 is for overall control. A graphic generation control unit including a processor unit ₃₀ , a color image memory unit 4 consisting of a plurality of memory planes (multiple bits/pixel) for storing two-dimensional figures;
5 reads out the contents of the color image memory section 4;
Video interface circuit that generates each video signal such as RGB, 6 can display multicolor
It is a CRT monitor.

Furthermore, in the figure generation control unit 3, there is a processor 3 ₁ which is the core of figure generation and executes the control and filling algorithm inside the polygon, a ROM 3 2 which stores a program describing the control and algorithm execution procedure, and a ROM 3 ₂ which executes the control and filling algorithm inside the polygon. At the same time, a processor section ₃₀ having a RAM ₃₃ for temporarily storing information necessary for the filling process is installed, and at the same time a work memory having a capacity of 1 bit/1 pixel for storing boundary pixels forming a polygon is installed. 3 ₄ , a boundary that performs the process of extracting a closed curve and the process of calculating the circumscribed rectangle of the closed curve at high speed by executing a boundary line tracing algorithm starting from a point on the work memory _{3 4 given} by the processor unit 3 0. A line tracing processing section 3 ₅ and a filling processing section 3 ₆ that executes an area filling algorithm using a point on the work memory 3 ₄ given from the processor 3 ₀ as a seed point are installed.

Incidentally, access to the segment buffer 2 and color image memory section 4 is performed via the processor ₃₁ .

Now, the procedure of the method of the present invention using the apparatus constructed as described above will be explained with reference to the block diagram of FIG. 1 and the flowchart of FIG. 2.

First, the host computer writes vertex coordinate information, color designation information, and commands of digital figure data (polygon) to the segment buffer 2 via the host computer interface circuit 1, and fills the polygon to the figure generation control unit 3. start.

Here, the target is, for example, a polygon with a hole as shown in FIG.

(a) The processor 3 ₁ uses the segment buffer 2 to obtain the polygon's vertex coordinates P _i (X _pi , Y _pi ) (i=1 to
n), Q _i (X _gi , Y _gi ) (i = 1 to m) and write them to RAM 3 ₃ , and from these values calculate the vertex.
Maximum values of X and Y coordinates of P _i and Q _i (X _nax , Y _nax ),
By calculating the minimum values (X _nio , Y _nio ), the circumscribed rectangle BLOUT of the polygon is obtained and stored in the RAM _{3 3} . If it is known that the vertex Pi is an outer vertex of the polygon, it is only necessary to calculate the X and Y coordinates of this vertex Pi.

(b) The processor ₃₁ stores an area on the work memory ₃₄ corresponding to the size of this circumscribed rectangle BLOUT.
ROUT (X _nio ≦X≦X _nax , Y _nio ≦Y≦Y _nax ) is defined, and a white pixel (pixel value "0") is written in this area ROUT to initialize it.

(c) The processor 3 ₁ sequentially connects the vertex rows P _i and Q _i in the area ROUT on the work memory 3 ₄ with four line segments (the positional relationship of adjacent pixels is defined in four directions, horizontal and vertical). area by tying
Write the outer boundary line BCOUT and inner boundary line BCIN of the polygon in ROUT using black pixels (pixel value "1").

(d) The processor ₃₁ has a circumscribed rectangular area ROUT on the work memory ₃₄ (X _nio ≦X≦X _nax , Y _nio ≦
Sequentially raster scan Y≦Y _nax ) to find the point P _s (X _s , Y _s ) where a black pixel (pixel value “1”) changes to a white pixel (pixel value “0”) and store it in _RAM33. do.

(e) The processor 3 ₁ provides the change point P _s (X _s , Y _s ) obtained in step (d) to the boundary line tracing processing unit 3 ₅ .
Start execution. As a result, the boundary tracing processing unit ₃₅ traces the boundary line WCOUT of the white pixel area adjacent to the outer boundary line BCOUT of the polygon as a starting point at the change point _Ps , and traces the boundary line WCOUT of the white pixel area adjacent to the outer boundary line BCOUT of the polygon,
Upper and lower limit values WX _nio of X and Y coordinates of WLOUT,
Find WX _nax , WY _nio , WY _nax .

The processor 3 ₁ receives the circumscribed rectangle WLOUT of the white pixel boundary line WCOUT from the boundary line tracing processing unit 3 ₅ .
Upper and lower limit value coordinates WX _nio , WX _nax , WY _nio ,
Read WY _{nax from} RAM _{3 3} , _read the upper and _lower limit coordinate values X _nio , By, the bounding rectangle WLOUT and the bounding rectangle
Compare the positional relationship of BLOUT.

Conditions _{X nio < WX nio} < _{X nax and} X _{nio <} WX _{nax <}
Check whether the circumscribed rectangle WLOUT of WCOUT is included in the circumscribed rectangle BLOUT of the polygon.

The condition holds, i.e. the circumscribed rectangle WLOUT
is included in the circumscribed rectangle BLOUT, move to the next step (f).

Condition does not hold, i.e. circumscribed rectangle
If WLOUT is not included in the circumscribed rectangle BLOUT, the process from step (d) is repeated again.

(f) The processor 3 ₁ reads the coordinates (X _s , Y _s ) of the white pixel change point P _s from the RAM _{3 3} , gives this value to the filling process 3 ₆ , and starts execution.
As a result, the filling processing unit ₃₆ uses the change point _Ps as a seed point to execute an area filling algorithm using 8 connections (the positional relationship of adjacent pixels is defined in eight directions: horizontal, vertical, and diagonal), and・Change the white pixels inside the polygon in memory 3 to ₄ to black pixels.

(g) Processor ₃₁ reads out color specification information from segment buffer ₂ , and further calculates the area ROUT (X _nio ≦X≦X _nax , Y _nio ≦
Raster scanning is performed again (Y≦Y _nax ), and the color designation information is written in the coordinate positions in the color image memory unit 4 corresponding to all black pixels.

By using the algorithm described above, it is possible to automatically determine the seed point _Ps as the starting point for filling, and it is possible to perform the filling process inside the given digital image data (polygon) at high speed.

Next, for the polygon shown in Figure 3,
The concept when the method of the present invention is actually applied will be specifically explained using FIG. 4.

The figures shown in FIGS. 4(a) to 4(g) correspond to the steps in the flowchart (a) to (g) of FIG. 2 described above, respectively.

(a) For the polygon shown in FIG. 3, find its circumscribed rectangle BLOUT from its vertex coordinates P _i (i=1 to n) and Q _i (i=1 to m).

(b) Save this circumscribed rectangle BLOUT to work memory 3
₄ as a region ROUT, and initialize this as a set of white pixels.

(c) Connect the outer boundary line BCOUT and inner boundary line BCIN of the polygon with four connected line segments in the area ROUT on work memory ₃₄ , and write them as black pixels.

(d) Raster scan the circumscribed rectangle BLOUT of the polygon on the work memory ₃₄ to find the point of change from a black pixel to a white pixel.

(e) If a change point P _s from a black pixel to a white pixel is detected, start from this point P _s and start from the boundary of the white pixel area adjacent to the outer boundary line BCOUT of the polygon.
Track WCOUT and its bounding rectangle WLOUT
seek.

(e)−(1) The circumscribed rectangle WLOUT is a circumscribed rectangle
Indicates when it is not included in BLOUT.

(e)-(2) Here, if the circumscribed rectangle WLOUT is included in the circumscribed rectangle BLOUT, this white pixel change point P _s is set as the filling seed point.

(f)-(1) Using the change point _Ps as a seed point, the white pixels inside this polygon are changed to black pixels as shown in (f)-(2).

(g)-(1) This area ROUT is raster-scanned again, and points corresponding to black pixels are scanned according to the color information specified in advance in the color image memory section 4 as shown in (g)-(2). Write it down.

Further, according to the image information stored in the color image memory unit 4, the video interface circuit 5
A filled-in display is performed on the CRT monitor 6 via.

FIG. 5 is a diagram showing the actual state of digital figures (polygons) on the work memory ₃₄ .

In this figure, the hatched points represent black pixels on the outer boundary line BCOUT and inner boundary line BCIN of the polygon. Here, an area painting algorithm using 8-connection is executed using the point P _s where a black pixel changes to a white pixel as a seed point. This makes it possible to completely fill out the white pixels inside the polygon.

<Effects of the Invention> According to the digital image filling method of the present invention, the interior of a polygon can be filled in using a work memory having a capacity of 1 bit/1 pixel for storing boundary line pixels forming a polygon. Since seed points for filling are automatically generated, the interior of polygons can be filled at high speed using conventional area filling algorithms.

[Brief explanation of drawings]

FIG. 1 is a block diagram of a digital image processing device suitable for carrying out the digital image filling method of the present invention, and FIG. 2 is a flowchart showing the digital image filling method of the present invention.
FIG. 3 is a diagram showing a polygon (digital figure) that is the object of the method of the present invention, FIGS. 4 a to g-2 are diagrams representing the concept when using the method of the present invention, and FIG.
The figure shows digital image data when the method of the present invention is actually used, and FIGS. 6a to 6d are diagrams for explaining a conventional polygon filling method. 1...Host computer interface circuit, 2
...Segment buffer, 3...Graphic generation control section, ₃₀ ...Processor section, ₃₁ ...Processor,
3 ₂ ...ROM, 3 ₃ ...RAM, 3 ₄ ...Work
Memory, 3 ₅ ... Border tracing processing section, 3 ₆ ... Filling processing section, 4 ... Color image memory section, 5 ......
Video interface circuit, 6...CRT monitor.

[Claims]

1. A memory that stores instructions and data, multiple functional units that execute instructions, a node driving register that indicates executable instructions, and a function that specifies whether each of the above functional units performs Neumann processing or parallel processing. During parallel processing, when a functional unit retrieves from memory an executable instruction pointed to by a word in a node driving register, that instruction signifies the start of Neumann processing. If so, write "N" to the mode register to indicate von Neumann processing, temporarily allocate the above word to a certain functional unit, and use the word to function in the same way as the program counter of a Neumann computer. means for controlling such that, during Neumann processing, when a certain functional unit retrieves from memory an executable instruction indicated by the word, that instruction signifies a return to parallel processing; If it is, it has means for writing "P", which means parallel processing, into the mode register, and each functional unit has

Claims (1)

A method for filling a digital figure, comprising: performing raster scanning on a rectangle and writing color information specified in advance for coordinate positions corresponding to all black pixels into a color image memory unit;