Method of sorting two-dimensional graphic images for converting into raster lines

• US 5,929,865 A
• Filed: 06/14/1996
• Issued: 07/27/1999
• Est. Priority Date: 06/14/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kapfhammer, Mark W., Balz, James G., Long, David C., LaPlante, Mark J.
• Primary Examiner(s): Hong, Stephen S.
• Application Number:
  US08/663,828
• Time in Patent Office: 1,138 Days
• Field of Search: 345/440, 345/441, 345/442, 345/443, 345/421, 345/422, 345/433, 345/434, 345/435, 345/113, 345/118, 345/135
• US Class Current: 345/441
• CPC Class Codes: G06T 15/10 Geometric effects

Abstract

A method for sorting two-dimensional graphics data into raster lines is described. The method decomposes the graphic images into vector line and arc segments with their associated two-dimensional coordinates. A vector or sub-shape list is then established containing the coordinates of all the vector lines and arcs. Sorting is then performed on the vector data by organizing each vector based upon its X- or Y- coordinate information. Pixels that make up each sub-shape are then computed. This computation is performed for each sub-shape in the order given by the sorted, sub-shape list. The resultant pixel list is ordered according to the X- or Y- dimensional sort previously performed. Pixels generated in a partially pre-sorted arrangement are arranged in a pixel array. The stored pixel array is then used to form raster lines.

Claims

1. A method for processing data, comprising the steps of:

a) providing input data defining shapes in a two-dimensional plane, wherein said shapes are defined by points with a plurality of coordinates on an X-axis and a Y-axis;

b) decomposing the data defining each shape into two-dimensional vector data, wherein said vectors are defined by points with a plurality of coordinates on an X-axis and a plurality of coordinates on a Y-axis;

c) sorting said two-dimensional vector data according to a first predetermined order wherein said vectors are defined by points with a plurality of coordinates on an X-axis and a plurality of coordinates on a Y-axis;

d) thereafter determining pixel data for the vector data, the pixel data being in substantially the same order as the sorted vector data; and

,

e) forming raster lines from the sorted pixel data adaptable to compression such that pixel values less than a predetermined resolution are combined to form a single raster line.

2. The method as set forth in claim 1 further comprising step (e) of sorting the pixel data according to a second predetermined order.

3. The method as set forth in claim 1 wherein the input data further defines operation data that determines operations that are to be performed on the shape data, the method further comprising the step of performing the operations defined by the operation data on the vector data.

4. The method as set forth in claim 1 wherein the shape data defines at least one polygon, the decomposing step comprising decomposing the polygon into vector data defining line segments.

5. The method as set forth in claim 1 wherein the shape data defines at least one circle, the decomposing step comprises decomposing the circle into vector data defining arcs.

6. The method as set forth in claim 1 further including storing the sorted pixel data in a storage medium.

7. The method as set forth in claim 2 further including displaying the raster lines on a display device.

8. A method for processing data, comprising the steps of:

a) providing input data defining shapes in a two-dimensional plane, wherein said shapes are defined by points with a plurality of coordinates on an X-axis and a Y-axis;

b) decomposing the data defining each shape into two dimensional vector data wherein said vectors are defined by points with a plurality of coordinates on an X-axis and a plurality of coordinates on a Y-axis;

c) sorting said two-dimensional vector data according to a first predetermined order according to the defined X-axis coordinates or the defined Y-axis coordinates;

d) thereafter determining pixel data for the vector data, the pixel data being in substantially the same order as the sorted vector data;

e) sorting the pixel data according to a second predetermined order; and

f) forming raster lines from the sorted pixel data adaptable to compression such that pixel values less than a predetermined resolution are combined to form a single raster line.

9. A method for processing data, comprising the steps of:

a) providing input data defining shapes in a two-dimensional plane, wherein said shapes are defined by points with a plurality of coordinates on an X-axis and a Y-axis, and operations that are to be performed on the shape data;

b) performing the operations on the shape data;

c) decomposing the data defining each shape into two-dimensional vector data wherein said vectors are defined by points with a plurality of coordinates on an X-axis and a plurality of coordinates on a Y-axis;

d) sorting said two-dimensional vector data according to a first predetermined order according to the defined X-axis coordinates or the defined Y-axis coordinates;

e) thereafter determining pixel data for the vector data, the pixel data being in substantially the same order as the sorted vector data;

f) sorting the pixel data according to a second predetermined order; and

g) forming raster lines from the sorted pixel data adaptable to compression such that pixel values less than a predetermined resolution are combined to form a single raster line.

10. A method for processing data, comprising the steps of:

a) providing input data defining shapes in a two-dimensional plane, wherein said shapes are defined by points with a plurality of coordinates on an X-axis and a Y-axis, and operations that are to be performed on the shape data;

b) performing the operations on the shape data;

c) decomposing the data defining each shape into two-dimensional vector data wherein said vectors are defined by points with a plurality of coordinates on an X-axis and a plurality of coordinates on a Y-axis;

d) sorting said two-dimensional vector data according to a first predetermined order according to the defined X-axis coordinates or the defined Y-axis coordinates;

e) thereafter determining pixel data for the vector data, the pixel data being in substantially the same order as the sorted vector data;

f) sorting the pixel data according to a second predetermined order;

g) forming raster lines from the sorted pixel data adaptable to compression such that pixel values less than a predetermined resolution are combined to form a single raster line to effect continuous movement of a machining device; and

h) moving said machining device according to the raster lines formed in step (g).