Methods and apparatus for generating multi-level graphics data

• US 7,190,839 B1
• Filed: 06/12/2002
• Issued: 03/13/2007
• Est. Priority Date: 06/12/2002
• Status: Expired due to Fees

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Holmes, Richard, Feather, Heath
• Primary Examiner(s): Bella; Matthew C.
• Assistant Examiner(s): Rosario; Dennis
• Application Number:
  US10/171,047
• Time in Patent Office: 1,735 Days
• Field of Search: 382/299, 382/302, 382/276, 382/261, 382/263, 382/264, 382/144, 382/145, 382/147, 382/148, 382/240
• US Class Current: 382/240
• CPC Class Codes: G06T 3/4023 based on decimating pixels or lines of pixels; based on inserting pixels or lines of pixels
• CPC Class Codes: G09G 2340/0407 Resolution change, inclusive of the use of different resolutions for different screen areas

Abstract

A technique generates a pyramid of image tiles to represent a source image at different resolutions. A base image tile stores, in a plurality of elements, an “on” state or an “off” state to represent the source image at a first resolution. Additional image tiles, with image resolutions lower than the resolution of the base image tile, are generated. The base image tile is divided into groupings of elements, such that each level of the pyramid of image tiles is generated by mapping a grouping of elements from the base image tile to an image tile at different levels of the pyramid. A threshold density of elements in the grouping elements is selected. If the grouping of elements in the base image tile for a level has a threshold density of “on” elements, the image data for the element in the current level is set to an “on” state. Conversely, the image data for the element is set to an “off” state if the threshold density of “on” elements in the base image tile grouping is less than the threshold density.

Claims

1. A method for generating a plurality of abstract image tiles to represent a source image for an integrated circuit (IC) layout, said method comprising the steps of:

generating a first level of abstract image tiles within the IC layout, said first level of abstract image tiles having a first grouping of elements, each element having an “

on”

state or an “

off”

state to represent the source image with a first resolution;

generating a plurality of additional levels of abstract image tiles within the IC layout, based on said first level of abstract image tiles, wherein each particular level of additional abstract image tiles has a particular grouping of elements to represent the source image with a particular resolution, wherein each particular grouping of elements has at least an element, wherein for an integer n greater than 1, generating each of plurality of n additional levels of abstract image tiles includes the steps of;

directly generating a plurality of mappings between said first grouping of elements from said first level of abstract image tiles to said particular grouping of elements from said level n of abstract image tiles;

generating for an element in said particular grouping an “

on”

element if said first grouping of elements mapped from said first level of abstract image tiles comprises a threshold density of “

on”

elements; and

generating for an element in said particular grouping an “

off”

element if said first grouping of elements mapped from said first level of abstract image tiles does not comprise a threshold density of “

on”

elements.

2. The method as set forth in claim 1, wherein said threshold density comprises a subset of elements greater than twenty five percent of elements in a first grouping.

3. The method as set forth in claim 1, wherein said first grouping comprises four elements for each element in a second grouping.

4. The method as set forth in claim 1, wherein:

said source image comprises multiple layers; and

said first level of abstract image tiles and each of said additional level of abstract image tiles comprise a bit plane comprising a plurality of layers for each of said levels in said source image.

5. The method as set forth in claim 1 further comprising the steps of:

dividing said first level of abstract image tiles into a plurality of tiles, wherein each tile comprises a predetermined resolution; and

mapping a plurality of tiles from said first level of abstract image tiles to a single tile in a level n abstract image tiles.

6. A method of generating a hierarchical multi-level pyramid of abstract image tiles for an integrated circuit (IC) layout, said method comprising the steps of:

dividing an IC layout abstract image tiles of level 0 into level 0 groupings such that each of said level 0 groupings comprises a plurality of elements, each element having an “

on”

state or an “

off”

state to represent a source image with a first resolution;

dividing an IC layout abstract image tiles of level n into level n groupings such that each of said level n groupings comprises at least one element, wherein n comprises any integer value greater than 1;

directly generating a plurality of mappings between said level 0 groupings of elements from said level 0 abstract image tiles to said level n groupings of at least one element from said level n abstract image tiles;

generating for an element in said level n groupings an “

on”

element if said level 0 groupings of elements mapped from said level 0 abstract image tiles comprise a threshold density of “

on”

elements; and

generating for a element in said level n groupings an “

off”

element if said level 0 groupings of elements mapped from said level 0 abstract image tiles does not comprise a threshold density of “

on”

elements.

7. A computer readable medium storing a plurality of instructions, which when executed by a computer, causes the computer to perform the steps of:

generating a first level of abstract image tiles within an integrated circuit (IC) layout, said first level of abstract image tiles having a first grouping of elements, each element having an “

on”

state or an “

off”

state to represent a source image with a first resolution;

generating a plurality of additional levels of abstract image tiles within the IC layout, based on said first level of abstract image tiles, wherein each particular level of additional abstract image tiles has a particular grouping of elements to represent the source image with a particular resolution, wherein each particular grouping of elements has at least an element, wherein for an integer n greater than 1, generating each of plurality of n additional levels of abstract image tiles includes the steps of;

directly generating a plurality of mappings between said first grouping of elements from said first level of abstract image tiles to said particular groupings of elements from said level n of abstract image tiles;

generating for an element in said particular grouping an “

on”

element if said first grouping of elements mapped from said first level of abstract image tiles comprise a threshold density of “

on”

elements; and

generating for an element in said particular grouping an “

off”

element if said first grouping of elements mapped from said first level of abstract image tiles does not comprise a threshold density of “

on”

elements.

8. The computer readable medium as set forth in claim 7, wherein said threshold density comprises a subset of elements greater than twenty five percent of elements in a first grouping.

9. The computer readable medium as set forth in claim 7, wherein said first grouping comprises four elements for each element in a second grouping.

10. The computer readable medium as set forth in claim 7, wherein:

said source image comprises multiple layers; and

said first level of abstract image tiles and each of said additional level of abstract image tiles comprise a bit plane comprising a plurality of layers for each of said levels in said source image.

11. The computer readable medium as set forth in claim 7, further storing a plurality of instructions, which when executed by a computer, causes the computer to perform the steps of:

dividing said first level of abstract image tiles into a plurality of tiles, wherein each tile comprises a predetermined resolution; and

mapping a plurality of tiles from said first level of abstract image tiles to a single tile in a level n abstract image tiles.

12. A computer readable medium storing a plurality of instructions, which when executed by a computer, causes the computer to generate a hierarchical pyramid of abstract image tiles for an IC layout by executing the steps of:

dividing an IC layout abstract image tiles of level 0 into level 0 groupings such that each of said level 0 groupings comprises a plurality of elements, each element having an “

on”

state or an “

off”

state to represent a source image with s first resolution;

dividing an IC layout abstract image tiles of level n into level n groupings such that each of said level n groupings comprises at least one element, wherein n comprises any integer value greater than 1;

generating a plurality of mappings between said level 0 groupings of elements from said level 0 abstract image tiles to said level n groupings of at least one element from said level n abstract image tiles;

directly generating for an element in said level n groupings an “

on”

element if said level 0 groupings of elements mapped from said level 0 abstract image tiles comprise a threshold density of “

on”

elements; and

generating for a element in said level n groupings an “

off”

element if said level 0 groupings of elements mapped from said level 0 abstract image tiles does not comprise a threshold density of “

on”

elements.

13. A computer graphics system for an IC layout comprising:

a memory for storing a first level of abstract image tiles within an integrated circuit (IC) layout, said first level of abstract images having a first grouping of elements, each element having “

on” and

“

off”

states to represent a source image with a first resolution, and for storing a a plurality of additional levels of abstract image tiles within the IC layout, based on said first level of abstract image tiles, wherein each level n of additional abstract image tiles has a particular grouping of elements to represent the source image with a particular resolution, wherein n is an integer greater than 1, wherein each particular grouping of elements has at least an element; and

a processor unit, coupled to said memory, for generating directly a plurality of mappings between said first grouping of elements from said first level of abstract image tiles to said particular grouping of elements from said level n of abstract image tiles, generating for an element in said particular grouping an “

on”

element if said first grouping of elements mapped from said first level of abstract image tiles comprise a threshold density of “

on”

elements, and generating for an element in said particular grouping an “

off”

element if said first grouping of elements mapped from said first level of abstract image tiles does not comprise a threshold density of “

on”

elements.