# US 7,746,355 B1 · Method for distributed clipping outside of view volume

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

- Number: US 7,746,355 B1
- Document ID: US7746355B1
- Status: Granted
- Kind: B1
- Application number: 11/657,966
- Filed: 2007-01-24
- Granted: 2010-06-29
- Earliest claimed: 2007-01-24
- Assignees: Vivante Corporation
- Inventors: Mike Cai; Lin Tan; Frido Garritsen; Ming Chen
- Web page: https://patentgrep.com/patent/US7746355B1

## CPC

- G06T 15/30: Clipping
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

A distributed clipping scheme is provided, view frustum culling is distributed in several places in a graphics processing pipeline to simplify hardware implementation and improve performance. In general, many 3D objects are outside viewing frustum. In one embodiment, clipping is performed on these objects with a simple algorithm in the PA module, such as near Z clipping, trivial rejection and trivial acceptance. In one embodiment, the SE and RA modules perform the rest of clipping, such as X, Y and far Z clipping. In one embodiment, the SE module performs clipping by way of computing a initial point of rasterization. In one embodiment, the RA module performs clipping by way of conducting the rendering step of the rasterization process. This approach distributes the complexity in the graphics processing pipeline and makes the design simpler and faster, therefore design complexity, cost and performance may all be improved in hardware implementation.

## Claims

### Claim 1

A method for clipping in a 3D computer graphics processing pipeline, the 3D computer graphics processing pipeline comprises a view frustum, a clipping window, a primitive assembly (PA) module, a set up (SE) module, and a rasterization (RA) module, the method comprising:
obtaining a primitive using the PA module;
performing a first clipping of the primitive with respect to the view frustum using the PA module, wherein the first clipping includes culling based on trivial rejection and clipping based on near-Z plane only;
determining an initial point of rasterization for the using the SE module;
performing a second clipping of the primitive with respect to the view frustum using the SE module;
rendering the primitive using the RA module; and
performing a third clipping of the primitive using the RA module.

### Claim 2 (depends on 1)

The method of claim 1, wherein the primitive comprises one or more vertex, and wherein the first clipping removes the primitive if the primitive has no vertex inside the view frustum.

### Claim 3 (depends on 1)

The method of claim 1, wherein the primitive comprises one or more vertices, and wherein the second clipping comprises removing the primitive if the initial point of rasterization for the primitive can not be determined inside the clipping window.

### Claim 4 (depends on 1)

The method of claim 1, wherein the third clipping comprises:
(a) inputting the initial point of rasterization for the primitive;
(b) determining if the primitive is a line or a triangle; and
(c) if the primitive is a triangle, rasterizing the triangle in a hierarchical manner, comprising:
(c1) walking a plurality of tiles of pixels and determining if each tile is valid;
(c2) breaking each valid tile into a plurality of subtiles and determining if each subtile is valid;
(c3) breaking each valid subtile into a plurality of quads and determining if each quad is valid; and
(c4) rendering pixels for each valid quad, wherein steps (c1) through (c4) are performed in parallel.

### Claim 5 (depends on 4)

The method of claim 4, wherein the breaking step (c2) comprises:
(c2i) breaking each valid tile into the plurality of subtiles;
(c2ii) walking the plurality of subtiles; and
(c2iii) determining if each subtile is valid.

### Claim 6 (depends on 5)

The method of claim 5, wherein the walking of the plurality of subtiles is performed in a same manner as the walking of the plurality of tiles.

### Claim 7 (depends on 4)

The method of claim 4, wherein the breaking step (c3) comprises:
(c3i) breaking each valid subtile into the plurality of quads;
(c3ii) walking the plurality of quads; and
(c3iii) determining if each quad is valid.

### Claim 8 (depends on 7)

The method of claim 7, wherein the walking of the plurality of quads is performed in a same manner as the walking of the plurality of tiles and a walking of the plurality of subtiles.

### Claim 9 (depends on 4)

The method of claim 4, wherein validation of a block, wherein the block comprises a tile, a subtile, or a quad, comprises:
checking if a pixel in the block sits on the left, right, or exactly on a line of a triangle using edge equations;
checking four corners of the block against three edges of the triangle and returning a combined result;
determining if the block contains any pixels inside the triangle, based on the combined result; and
determining that the block is valid, if the block contains at least one valid pixel inside the triangle.

### Claim 10 (depends on 9)

The method of claim 9, further comprising:
abandoning the block, if the block does not contain at least one valid pixel inside the triangle.

### Claim 11 (depends on 4)

The method of claim 4, further comprising:
(d) if the primitive is a line, computing pixels for each quad of pixels for the line; and
(e) rendering pixels for each valid quad.

### Claim 12 (depends on 1)

The method of claim 1, wherein the primitive has a position and a size, and wherein the first clipping removes the primitive if the position is outside of the view frustum.

### Claim 13 (depends on 12)

The method of claim 12,
wherein the primitive is converted into a polygon according to the size,
wherein the polygon is converted into a plurality of triangles in the SE module, and
wherein the second clipping removes a triangle if the triangle has no vertex inside the clipping window.

### Claim 14 (depends on 13)

The method of claim 13, wherein the third clipping comprises:
(a) inputting the initial point of rasterization for the triangle; and
(b) rasterizing the triangle in a hierarchical manner, comprising:
(b1) walking a plurality of tiles of pixels and determining if each tile is valid;
(b2) breaking each valid tile into a plurality of subtiles and determining if each subtile is valid;
(b3) breaking each valid subtile into a plurality of quads and determining if each quad is valid; and
(b4) rendering pixels for each valid quad, wherein steps (b1) through
(b4) are performed in parallel.

### Claim 15 (depends on 14)

The method of claim 14, wherein the breaking step (b2) comprises:
(b2i) breaking each valid tile into the plurality of subtiles;
(b2ii) walking the plurality of subtiles; and
(b2iii) determining if each subtile is valid.

### Claim 16 (depends on 15)

The method of claim 15, wherein the walking of the plurality of subtiles is performed in a same manner as the walking of the plurality of tiles.

### Claim 17 (depends on 14)

The method of claim 14, wherein the breaking step (b3) comprises:
(b3i) breaking each valid subtile into the plurality of quads;
(b3ii) walking the plurality of quads; and
(b3iii) determining if each quad is valid.

### Claim 18 (depends on 17)

The method of claim 17, wherein the walking of the plurality of quads is performed in a same manner as the walking of the plurality of tiles and a walking of the plurality of subtiles.

### Claim 19 (depends on 14)

The method of claim 14, wherein validation of a block, wherein the block comprises a tile, a subtile, or a quad, comprises:
checking if a pixel in the block sits on the left, right, or exactly on a line of a triangle using edge equations;
checking four corners of the block against three edges of the triangle and returning a combined result;
determining if the block contains any pixels inside the triangle, based on the combined result; and
determining that the block is valid, if the block contains at least one valid pixel inside the triangle.

### Claim 20 (depends on 19)

The method of claim 19, further comprising:
abandoning the block, if the block does not contain at least one valid pixel inside the triangle.