# US 5,710,879 A · Method and apparatus for fast quadrilateral generation in a computer graphics system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 5,710,879 A
- Document ID: US5710879A
- Status: Granted
- Kind: A
- Application number: 08/488,644
- Filed: 1995-06-08
- Granted: 1998-01-20
- Earliest claimed: 1995-06-08
- Assignees: Hewlett-Packard Company
- Inventors: Jon L. Ashburn
- Web page: https://patentgrep.com/patent/US5710879A

## CPC

- G06T 11/40: Filling planar surfaces by adding surface attributes, e.g. adding colours or textures
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

A quadrilateral is divided into two triangles so that each of the two triangles may then be filled by a triangle fill scan converter. Additionally, the vertices of a triangle are sorted to generate inputs to a fill scan converter. A circuit combines the functions of dividing the quadrilateral into triangles and generating the plane equations for the triangle fill scan converter. Accordingly, similar operations which are performed for both triangles of the quadrilateral may be shared between the plane equations for the two triangles. A circuit also combines the functions of generating the plane equations for any one triangle with automatic sorting of the triangle vertices.

## Claims

### Claim 1

In a computer graphics system, apparatus for generating pixel data representative of a quadrilateral, comprising:
a processing circuit for generating plane equation data in response to vertex data defining a quadrilateral, said processing circuit including:
first means responsive to said vertex data for dividing the quadrilateral into vertex data representative of first and second triangles;
second means responsive to the vertex data representative of said first triangle for generating plane equation data for said first triangle, including shared data, that is shared by said first and second triangles; and
third means responsive to vertex data representative of the second triangle and the shared data for generating plane equation data for said second triangle, without generating at least some of the shared data twice; and
a fill scan converter responsive to said plane equation data for said first and second triangles for generating pixel data representative of said quadrilateral.

### Claim 2 (depends on 1)

The apparatus of claim 1, wherein the shared data includes edge data for an edge that is common to both said first triangle and said second triangle.

### Claim 3 (depends on 1)

The apparatus of claim 1, wherein the shared data includes vertex data fetched by the second means from a first memory into a second memory, and wherein the third means includes means for accessing at least some of the vertex data directly from the second memory, the second memory having a shorter access time than the first memory.

### Claim 4 (depends on 1)

The apparatus of claim 1, wherein the first means includes:
means for designating for the first triangle a first vertex, a second vertex, a third vertex, a first edge, a second edge, and a third edge; and
means for designating for the second triangle the first vertex of the first triangle, a fourth vertex, the third vertex of the first triangle, the first edge of the first triangle, a fourth edge, and a fifth edge.

### Claim 5

In a computer graphics system including a fill scan converter for generating pixel data representative of a quadrilateral in response to plane equation data, a method for generating the plane equation data comprising the steps of:
receiving vertex data representing the quadrilateral;
dividing the quadrilateral into vertex data representative of a first triangle and a second triangle;
generating plane equation data for the first triangle, including shared data;
providing the plane equation data for the first triangle to the fill scan converter for generating pixel data representative of the quadrilateral;
generating plane equation data for the second triangle using at least some of the shared data; and
providing the plane equation data for the second triangle to the fill scan converter for generating pixel data representative of the quadrilateral.

### Claim 6 (depends on 5)

The method of claim 5, wherein the step of dividing includes the steps of:
designating for the first triangle a first vertex, a second vertex, a third vertex, a first edge, a second edge, and a third edge; and
designating for the second triangle the first vertex of the first triangle, a fourth vertex, the third vertex of the first triangle, the first edge of the first triangle, a fourth edge, and a fifth edge.

### Claim 7 (depends on 5)

The method of claim 5, wherein the step of generating plane equation data for the first triangle includes storing some of the shared data fetched from a first memory into a second memory, and wherein the step of generating plane equation data for the second triangle includes accessing at least some of the shared data directly from the second memory, the second memory, having a shorter access time than that of the first memory.

### Claim 8 (depends on 7)

The method of claim 7, wherein the step of accessing at least some of the shared data includes accessing display parameter data of a first vertex and a second vertex that are shared by the first triangle and the second triangle.

### Claim 9 (depends on 5)

The method of claim 5, wherein the step of generating plane equation data for the first triangle includes generating data describing a shared edge between the first triangle and the second triangle, and wherein the step of generating plane equation data for the second triangle includes using at least some of the data describing the shared edge.

### Claim 10 (depends on 9)

The method of claim 9, wherein the step of using at least some of the data describing the shared edge includes using data that includes a slope of the shared edge and a change of a display parameter along the shared edge.

### Claim 11 (depends on 5)

The method of claim 5, wherein the step of generating plane equation data for the second triangle is performed during at least part of the step of generating plane equation data for the first triangle.

### Claim 12 (depends on 5)

The method of claim 5, wherein the step of generating plane equation data for the first triangle includes the steps of:
generating an amount of change of a display parameter with respect to a first axis of a display upon which the first triangle is to be rendered;
generating an amount of change of the display parameter with respect to a second axis of a display upon which the first triangle is to be rendered;
generating a starting value for the display parameter for a first pixel of the first triangle to be generated by the fill scan converter;
generating a slope of each edge of the first triangle;
generating a starting value and a stopping value of the second axis of one of the edges of the first triangle;
generating a stopping value of the second axis of another of the edges of the first triangle;
generating a starting value of the first axis of each of the edges of the first triangle; and
generating a flag indicative of an orientation of the first triangle.

### Claim 13

In a computer graphics system including a fill scan converter for generating pixel data representative of a quadrilateral in response to plane equation data, an apparatus for generating the plane equation data comprising:
means for receiving vertex data representing the quadrilateral;
means for dividing the quadrilateral into vertex data representative of a first triangle and a second triangle;
means for generating plane equation data for the first triangle, including shared data;
means for providing the plane equation data for the first triangle to the fill scan converter;
means for generating plane equation data for the second triangle using at least some of the shared data; and
means for providing the plane equation data for the second triangle to the fill scan converter for generating pixel data representative of the quadrilateral.

### Claim 14 (depends on 13)

The apparatus of claim 13, wherein the means for dividing includes:
means for designating for the first triangle a first vertex, a second vertex, a third vertex, a first edge, a second edge, and a third edge; and
means for designating for the second triangle the first vertex of the first triangle, a fourth vertex, the third vertex of the first triangle, the first edge of the first triangle, a fourth edge, and a fifth edge.

### Claim 15 (depends on 13)

The apparatus of claim 13, wherein the means for generating plane equation data for the first triangle includes means for storing some of the shared data fetched from a first memory into a second memory, and wherein the means for generating data for the second triangle includes means for accessing at least some of the shared data directly from the second memory, the second memory having a shorter access time than that of the first memory.

### Claim 16 (depends on 15)

The apparatus of claim 15, wherein the shared data includes display parameter data of a first vertex and a second vertex that are shared by the first triangle and the second triangle.

### Claim 17 (depends on 13)

The apparatus of claim 13, wherein the means for generating plane equation data for the first triangle includes means for generating data describing a shared edge between the first triangle and the second triangle, and wherein the means for generating plane equation data for the second triangle includes means for using at least some of the data describing the shared edge.

### Claim 18 (depends on 17)

The apparatus of claim 17, wherein the data describing the shared edge includes a slope of the shared edge and a change of a display parameter along the shared edge.

### Claim 19 (depends on 13)

The apparatus of claim 13, wherein the means for generating plane equation data for the second triangle includes means for generating plane equation data during a time in which the means for generating the plane equation data for the first triangle is generating plane equation data.

### Claim 20 (depends on 13)

The apparatus of claim 13, wherein the means for generating plane equation data for the first triangle includes:
means for generating an amount of change of a display parameter with respect to a first axis of a display upon which the first triangle is to be rendered;
means for generating an amount of change of the display parameter with respect to a second axis of a display upon which the first triangle is to be rendered;
means for generating a starting value for the display parameter for a first pixel of the first triangle to be generated by the fill scan converter;
means for generating a slope of each edge of the first triangle;
means for generating a starting value and a stopping value of the second axis of one of the edges of the first triangle;
means for generating a stopping value of the second axis of another of the edges of the first triangle;
means for generating a starting value of the first axis of each of the edges of the first triangle; and
means for generating a flag indicative of an orientation of the first triangle.