JPH0241576A - Polygon picking processing device and method - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed Description of the Invention] <Industrial Application Field> The present invention relates to a polygon picking processing device and method, and more specifically, to a method for identifying a polygon to be picked that matches cursor data. The present invention relates to a picking processing device and a method thereof.

<Prior art and problems to be solved by the invention> In a graphic display device, when a large number of figures are displayed simultaneously, it is difficult to erase, move, enlarge, reduce, rotate, etc. only a specific figure. Since there are frequent requests for picking, a picking processing device that identifies a specific shape that includes cursor data as a designated shape by setting desired cursor data, and highlights the designated shape based on the identification result as necessary. is required.

FIG. 6 is a block diagram showing a schematic configuration of a graphic display device, in which drawing command data supplied directly from a higher-level processor (not shown) or through a communication line is input to create a structure containing graphic information on a display memory. The graphic information management section to be constructed (5■),
The display memory (5) is stored by the graphic information management unit (51).
The graphic drawing unit (53) receives the graphic information read from 2) and performs coordinate conversion processing, clipping processing, etc., and the data obtained by performing necessary processing in the graphic drawing unit (53) is written. The image memory (54) has an image memory (54), and a CRT display (55) that visually displays the contents of the image memory (54). and,
The graphic drawing section (53) feeds back designated graphic identification result data to the graphic information management section (51) during the picking process. Note that (56) is an instruction unit for inputting cursor data to be picked, and is composed of, for example, a stylus pen and a tablet.

To explain in more detail, the graphic information management section (51)
, struture data (hereinafter abbreviated as figure name) is generated based on sequentially supplied drawing command data, and is written into the display memory (52) together with figure information. When performing a graphic drawing operation, the graphic information read from the display memory (52) is supplied to the graphic drawing section (53), and when performing a picking operation, the graphic information is read from the display memory (52). The figure drawing unit (53) displays the figure name along with the read figure information.
At the same time, the cursor data input by the instruction section (56) is supplied as is to the graphic drawing section (53).

The graphic drawing unit (53) includes the graphic information management unit (51).
) is used to generate pixel-by-pixel drawing data based on graphic information sequentially supplied from the seventh
As shown in the figure, the X and Y coordinate values of the cursor specified by the instruction unit (5B) are respectively stored in the X register (
62), the x-coordinate value and y-coordinate value of each pixel held in the y register (61) and sequentially output from a line segment interpolation calculator (not shown) are compared with the above-mentioned x-coordinate value and y-coordinate value, respectively. (84), and the comparison result signal is A.
The signal is supplied to the ND gate (65) to obtain a hit signal. When performing a graphic drawing operation, coordinate conversion processing, clipping processing, etc. are performed based on the graphic information supplied from the graphic information management section (51), and the obtained data is written to the image memory (54). When performing a picking operation, it is determined whether the data obtained as described above matches the cursor data, and if it is determined that they match, the shape to which the data belongs is The figure information management unit (
51).

Therefore, when the instruction section (5B) supplies cursor data to be picked, the cursor data is directly supplied to the graphic drawing section (53) through the graphic information management section (51). After that, the graphic information management department (
51) reads the graphic information together with the graphic base from the display memory (52) and sequentially supplies it to the graphic drawing section (53). Note that even if the drawing command data added to the figure information supplied to the figure drawing unit (53) is the same drawing command data as in the normal case, the figure drawing unit (53) performs picking by being supplied with cursor data. Since the operation mode is entered and the picking process is instructed, pixel data should be generated sequentially without writing pixel data to the image memory (54) and compared with the cursor data. will be instructed.

The graphic drawing unit (53) performs a pixel data generation operation based on the supplied graphic information without writing to the image memory (54), and matches the pixel data generated sequentially with the cursor data. Determine whether or not the

If it is determined that the generated pixel data matches the cursor data, the graphic base of the graphic to which the pixel data belongs is fed back to the graphic information management section (51) as specified graphic identification result data.

The figure information management unit (51) to which the figure base is fed back as specified figure identification result data searches for the storage address of the corresponding figure data in the display memory (52) based on the figure base, and stores only the corresponding figure. The figure drawing unit (53
).

Therefore, pixel data sequentially generated in the graphic drawing section (53) can be written into the image memory (54), and visual display can be performed based on the pixel data written into the image memory (54). By doing so, it is possible to emphasize only the specified figure by displaying blinking or the like.

Thereafter, by visually recognizing the highlighted figure and supplying processing commands such as erasing, enlarging, reducing, and moving, it is possible to perform necessary processing only on the picked figure.

That is, by simply picking a figure by inputting cursor data, visually recognizing it, and then inputting a necessary processing command, it is possible to process only the desired figure.

However, in the picking processing device with the above configuration,
When the figure to be identified is a polygon, it is necessary to sequentially generate a large amount of pixel data that makes up the polygon and compare the sequentially generated pixel data and cursor data. There is a problem in that it takes a long time to identify whether a polygon is a figure to be picked. To explain in more detail, when the cursor is located outside the polygon as shown in FIG. Since it cannot be determined that it is not a figure, the longest time is required.

Further, when the cursor is located inside the polygon as shown in FIGS. 8B and 8C, it is not necessary to generate all pixel data, so the required time can be shortened. That is, since there is no need to perform any discrimination processing after pixel data that matches the cursor data is generated, a significantly shorter time is required when the cursor is located at the location shown in FIG. 8B. On the other hand, when the cursor is located at the location shown in FIG. 8C, a considerably long time is required. However, since the location of the cursor in the polygon is not determined in advance, on average it is approximately 1/2 of the total pixels that make up the polygon.
A much larger number of pixel data would need to be generated and compared with the cursor data, which would significantly increase the amount of time required to identify which polygon is the object to be picked. It is.

Although only the case where the picking target figure is displayed in blinking mode has been described above, the same problem occurs even when the figure to be picked is not displayed in blinking mode.

<Object of the invention> This invention was made in view of the above problems,
It is an object of the present invention to provide a polygon picking processing device and method that can significantly reduce the time required to identify which polygon is a figure to be picked.

Means for Solving the Problems> In order to achieve the above object, the polygon picking processing device of the present invention comprises coordinate value generation means for generating coordinate values of a large number of line segments constituting a polygon; , determines whether the coordinate values of the corresponding cursor match the coordinate values that do not change over the entire range of the line segment generated by the cursor value holding means for holding the coordinate values of the cursor and the coordinate value generating means. a match determining means for determining whether or not a corresponding cursor coordinate value exists within a range of mutually different coordinate values of the end points of a line segment generated by the coordinate value generating means; hit signal generating means for generating a hit signal on the condition that a match state is determined by the means and that the coordinate value of the cursor is determined to be within the range of the coordinate value of the end point by the size determining means. I'm here.

However, the size determining means performs the determining operation only when the matching determining means determines that they are in a matching state, and the hit signal indicates that the coordinate value of the cursor is within the range of the coordinate value of the end point. It is preferable that the output signal is an output signal from the size determining means indicating that the object exists in the area.

Further, it is preferable that the coordinate values that do not change over the entire range of the line segment are coordinate values in a direction perpendicular to the scan line.

In order to achieve the above object, the polygon picking processing method of the present invention generates the coordinate values of the line segments that make up the polygon, one of which does not change in coordinate value, , extracting the coordinate values corresponding to the above-mentioned unchanged coordinate values and comparing them with the above-mentioned unchanged coordinate values,
Compare the other coordinate value of the end point of the line segment and the corresponding coordinate value of the cursor, provided that both coordinate values match,
This is a method for identifying a hit state on the condition that the corresponding coordinate value of the cursor is located between the coordinate values of the end points of the line segment.

In the polygon picking processing device with the above configuration, the cursor coordinate values set by external operations are held in the cursor value holding means, and the coordinate value generating means is used to pick up a large number of polygons forming the polygon. Sequentially generate coordinate values of line segments.

Then, among the coordinate values of the line segments that are sequentially generated, the coincidence determining means determines whether or not the coordinate values that do not change over the entire range match the coordinate values of the corresponding cursor. The size determining means determines whether or not a corresponding cursor coordinate value exists within a range of mutually different coordinate values of the end point among the coordinate values of the line segment. As a result, it is determined whether the coordinate values that do not change over the entire range are equal to the cursor coordinate values and whether the cursor coordinate values exist within the range of mutually different coordinate values of the end points. A hit signal can be generated by the hit signal generating means on the condition that the coordinate value that does not change over time is equal to the coordinate value of the cursor, and that the coordinate value of the cursor exists within the range of mutually different coordinate values of the end points. Therefore, there is no need to generate a large amount of pixel data, and the time required to identify whether a polygon is a picking target polygon can be significantly shortened.

The size determining means performs the determining operation only when the matching determining means determines that there is a match, and the hit signal indicates that the coordinate value of the cursor is within the range of the coordinate value of the end point. If the output signal from the size determining means indicates that the polygon exists in a The required time can be further shortened, and the configuration can be simplified since no hit signal generating means is required.

In addition, if the coordinate values that do not change over the entire range of the line segment are the coordinate values in the direction perpendicular to the scan line, it can be easily applied to a rusk scan type graphic ◆ display device, and the polygon to be picked It is possible to significantly shorten the time required to identify whether the

In the above picking processing method for a polygon, the coordinate values of the line segments that make up the polygon do not change are generated, and it is determined whether or not they match the coordinate values of the corresponding cursor. Only when it is determined that they match, generate mutually different coordinate values of the end points of the line segment, determine whether the corresponding cursor coordinate values exist within the range of the above coordinate values, and determine if they do exist. Since the hit state is identified only when the polygon to be picked It is possible to significantly shorten the time required to identify whether the

<Example> Hereinafter, embodiments will be described in detail with reference to the accompanying drawings showing examples.

FIG. 2 is a block diagram showing a schematic configuration of a graphic display device incorporating the picking processing device of the present invention. A graphic information management unit (1) constructs a structure containing graphic information on the spray memory, and the graphic information management unit (1) receives the graphic information read from the display memory port and performs coordinate conversion processing, clip processing, etc. a graphic drawing unit (3) that performs the necessary processing; an image memory (4) into which data obtained by performing necessary processing in the graphic drawing unit (3) is written; The graphic drawing unit G) is configured to feed back designated graphic identification result data to the graphic information management unit (1) during picking processing. ing. still,
(6) is an instruction unit for inputting cursor data to be picked, and is composed of, for example, a stylus pen and a tablet.

To explain in more detail, the graphic information management section (1) writes graphic information into the display memory (2) based on sequentially supplied drawing command data, and also writes graphic information as graphic identification data, for example, 1. The graphic name of the hierarchical structure consisting of one view data, at least one class data, one segment data, and one identification data is also written. Therefore, the display memory (2) can be accessed using the graphic storage address as graphic identification data, and the display memory (2) can also be accessed if necessary using the graphic name as graphic identification data. When a figure drawing operation is to be performed, the generated drawing command data is supplied to the figure drawing section (3) together with the figure information read out from the display memory (2), and conversely, the figure drawing unit (3) is caused to perform a picking operation. In this case, the figure storage address in the display memory (2) is stored in the figure drawing unit (3) together with the figure information read from the display memory (2).
), and the cursor data input by the instruction section (6) is supplied as is to the graphic drawing section (3).

The graphic drawing section (3) generates pixel-by-pixel drawing data based on the graphic information sequentially supplied from the graphic information management section (1). When performing a graphic drawing operation, coordinate conversion processing, clipping processing, etc. are performed based on the graphic information supplied from the graphic information management unit (1) and drawing command data, and the obtained data is stored in the image memory ( 4), and conversely, when performing a picking operation, it is determined whether or not the data in the direction perpendicular to the scan line matches the cursor data among the data obtained as described above. , determines whether the cursor data is included within the range of end point data in the scan line direction, and if it is determined that they match and is included, the figure storage address of the polygon to which the data belongs is determined. The data is fed back to the graphic information management section (1) as designated graphic identification result data.

FIG. 1 is a block diagram showing the main parts of an embodiment of the picking processing device of the present invention, in which coordinate values (hereinafter referred to as y to hold the X coordinate value)
A register (31) and an X register (32) that holds the coordinate value in the scan line direction (hereinafter abbreviated as the
), an interpolation calculator (33) that interpolates two sides facing each other in the scan line direction of the polygon, and a line segment y register () that temporarily holds the X coordinate value generated by the interpolation calculator (33). 34) and a pair of line segment X registers (
35) (3B) and a comparator (37) that compares the contents of the y register (31) and the contents of the line segment y register (34).
, the contents of the X register (32) and the line segment X register (3
5) A comparator (38) for determining the magnitude relationship with the contents of (3B), and an AND game that receives the comparison result data output from both comparators (37) and (88))
(39).

The operation of the graphic display device having the above configuration will be explained in detail with reference to FIG.

When cursor data to be picked is supplied according to instruction H (6), the cursor data is directly supplied to the graphic drawing unit (3) through the graphic information management unit (1). Thereafter, the graphic information management section (1) reads out the graphic information together with the graphic storage address from the display memory (2) and sequentially supplies it to the graphic drawing section (3).

Note that the drawing command data added to the graphic information supplied to the graphic drawing section (3) may be the same drawing command data as in the normal case.

The graphic drawing unit (3) enters a picking operation mode by being supplied with cursor data, enters a state where it is instructed to perform picking processing, and enters the y register (
31) and an X register (32) respectively hold the X coordinate value (yc) and the X coordinate value (xc) of the cursor. Then, based on the supplied graphic information, the interpolation calculator (33) interpolates the opposite sides of the polygon, and the X coordinate value (
yL ) and the X coordinate value of the end point (xLl), (xL
2) are generated and held in the line segment Y register (34) and line segment X register (35) (3B), respectively.

Therefore, the comparator (37) determines whether or not both y-coordinate values match, and the comparator (3B)
, it is determined whether the X coordinate value (xc) is between the X coordinate value (x Ll) and the X coordinate value (x L2), and the determination result signals (ah) and (cb
) is output. Then, the above discrimination result signal (ch)
.

(cb) are both supplied to the AND gate (39), so as shown in FIG. 3A, both y-coordinate values match, and moreover, the L
A hit signal (H) is output from the AND gate (39) on the condition that the value is between the X coordinate value (x L2) and the X coordinate value (x L2). That is, in the cases shown in FIGS. 3B and 3C, no hit signal (H) is output.

Therefore, on condition that the hit signal (H) is output, the figure name as designated figure identification result data is fed back to the figure information management section (1), and the picking process is completed. However, when displaying a figure specified by the picking process in a blinking manner, drawing command data instructing that the figure determined by the fed back figure name should be displayed in a blinking manner is added and the figure information is sent to the figure drawing section. (3), and since a large number of pixel data constituting the polygon are sequentially generated and stored in the image memory (4), the data can be displayed on the CRT display (5) based on the contents of the image memory (4). It is possible to visually display that the picking process has been carried out.

As is clear from the above explanation, when performing picking processing, it is only necessary to generate the end point coordinate data of multiple line segments in the scan line direction and compare it with the cursor coordinate data. The amount of data can be significantly reduced, and as a result, the time required for the picking process can be significantly reduced.

<Embodiment 2> Fig. 4 is a block diagram showing another embodiment of the picking processing device, and the difference from the embodiment shown in Fig. 1 is that the comparator (3
7) The discrimination result signal output from the line segment X register (
35) The configuration of the other parts is the same except that the data output control signal for (3B) is used and the AND gate (39) is omitted.

Therefore, in this example, the X-coordinate value of the line segment (
yL) and the cursor's X coordinate value (yc), the cursor's X coordinate value (xc) is the X coordinate value of the end point of the line segment (xLl).

It is possible to determine whether the value is between (x L2) and use the determination result signal as a hit signal (H).

As a result, the number of comparison operations performed by the comparator (38) can be significantly reduced, so that both comparators (37)
When the comparison operations according to (38) are not performed simultaneously, the time required for the picking process can be further reduced.

Furthermore, if it is possible to identify in advance that it is a polygon whose two opposing sides are parallel to the scan line, the magnitude comparison can be made not only for the X coordinate value but also for the X coordinate value. The time required can be further reduced by generating a hit signal based on the size comparison result signals of both sides, but this requires processing to identify polygons, so it is difficult to use general It cannot be concluded that it is also suitable for picking processing.

FIG. 5 is a flowchart illustrating an example of the operation when the picking process is performed by software.

The X coordinate value (x
c) and the X coordinate value (yc) - Temporarily hold the X coordinate value (yL) of the line segment in the scan line direction that constitutes the polygon specified in step (■) and the X coordinate value (xLl) of the end point , (xL2) is obtained, and in step (2) it is determined whether both y-coordinate values are equal. If it is determined that both y-coordinate values are equal, then in step 2 the X-coordinate value (xc) becomes both the
It is determined whether the value is between (xL2). In this step ■, the X coordinate value (xc) is changed to both X coordinate values (x
Ll).

If it is determined that the value is between (x L2), a hit signal (H) is generated in step (3), and the picking process is immediately terminated.

Further, if it is determined in step (2) that the two y-coordinate values are different, the next line segment is specified in step (2), and the determination and processing in step (2) and subsequent steps are performed. Furthermore, in step (2) above, the X coordinate value (xc) is both the X coordinate value (xLl).

If it is determined that the value is not between (x L2),
In step (2), the next polygon is specified, and the determination and processing in step (2) and subsequent steps are performed.

In other words, the X coordinate values of the line segments that make up the polygon and the X
Since it is possible to identify whether the polygon is a polygon to be picked simply by comparing the coordinate value with the X coordinate value and the X coordinate value of the cursor, it is possible to identify whether the polygon is a polygon to be picked or not. Although the time required for picking is somewhat longer, compared to the conventional example, the time required can be significantly shortened.

Note that the present invention is not limited to the above-described embodiments. For example, when cursor data is supplied to the figure drawing section (3), command data instructing the picking operation mode is added to draw a figure. In addition to being able to supply data to the drawing unit (3), it is also possible to input cursor data using a numeric keypad instead of using a stylus pen and tablet, and to change the brightness value instead of blinking. By doing so, it is possible to perform highlighted display, and various other design changes can be made without changing the gist of the present invention.

<Effects of the Invention> As described above, the first invention eliminates the need to generate a large amount of pixel data and allows picking processing to be performed based only on the coordinate values of the end points of the line segments that make up the polygon. This has the unique effect of significantly shortening the time required to identify whether or not the polygon is a picking target polygon.

The second invention can significantly reduce the number of times the operation of determining whether or not the coordinate value of the cursor exists within the range of the coordinate value of the end point, thereby identifying whether or not it is a polygon to be picked. This has the unique effect of further reducing the time required to generate the hit signal and simplifying the configuration since no hit signal generating means is required.

The third invention has a unique feature in that it can be easily applied to a rusk scan type graphic display device and can significantly shorten the time required to identify whether or not it is a polygon to be picked. be effective.

The fourth invention not only reduces the number of data to be generated, but also reduces the number of times the discrimination process is performed, so the time required to identify whether or not it is a polygon to be picked. It has the unique effect of being able to significantly shorten the time.

[Brief Description of the Drawings] Fig. 1 is a block diagram showing the main parts of an embodiment of the picking processing device of the present invention, and Fig. 2 is a schematic configuration of a graphic display device incorporating the picking processing device of the present invention. 3 is a diagram schematically showing the relationship between a polygon and a cursor, FIG. 4 is a block diagram showing another embodiment of the picking processing device, and FIG. 5 is a picking processing operation of the present invention. 6 is a schematic block diagram showing the configuration of a graphic display device incorporating a conventional picking processing device; FIG. 7 is a block diagram showing the configuration of a conventional picking processing device; FIG. 8 is a schematic diagram illustrating the time required for conventional picking processing. (31)...X register, (32)...X register, (33)...interpolation calculator, (34)...X for line segment
Register, (35) (3B)...X register for line segment, (37) (38)...Comparator, (39)...A
ND gate, (xc) (xLl) (xL2) = x coordinate value, (yc) (yL)...y coordinate value Figure 3 (A) Patent applicant: Agent of Daikin Industries, Ltd.

Claims (1)

[Claims] 1. Coordinate value generation means (33) for generating coordinate values (xL1) (xL2) (yL) of a large number of line segments constituting a polygon; ) and a coordinate value generating means (33).
Coincidence determining means (37) for determining whether or not the coordinate value (yL) that does not change over the entire range of the line segment generated by and the coordinate value (yc) of the corresponding cursor match; size determining means (33) for determining whether or not a corresponding cursor coordinate value (xc) exists within the range of mutually different coordinate values (xL1) (xL2) of the end points of the line segment generated by the means (33); 38) and a match determination means (
37), and the size determining means (38) determines that the cursor coordinate value (xc) is within the range of the end point coordinate values (xL1) (xL2). a hit signal generating means (39) for generating a hit signal (H) as a polygon. 2. The size determination means (38) performs the determination operation only when the coincidence determination means determines that they are in a matching state, and the hit signal (H) indicates that the coordinate values of the cursor are the coordinates of the end point. A picking processing device for a polygon according to claim 1, wherein the output signal is an output signal from a size determining means (38) indicating that the polygon exists within a value range. 3. Picking processing for a polygon according to claim 1 or 2, wherein the coordinate value (yL) that does not change over the entire range of the line segment is a coordinate value in a direction perpendicular to the scan line. Device. 4. Generate the coordinate values of the line segments that make up the polygon and whose coordinate values (yL) do not change, and calculate the coordinate values (yc) of the cursor set by external operation that correspond to the coordinate values that do not change. Extract and compare with the above unchanged coordinate value (yL), and on the condition that both coordinate values match, the other coordinate value (xL1) (xL2) of the end point of the line segment and the corresponding coordinate value of the cursor ( xc), and a hit state is identified on the condition that the corresponding coordinate value (xc) of the cursor is located between the coordinate values (xL1) (xL2) of the end points of the line segment. Picking processing method for polygons.