Patent US1264564A successfully refreshed from Google Patents.
US5745121A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Methods and apparatus for optimizing the composition of graphical elements
Assignee: Canon Inc
•
Filing: 1995-07-21
•
Granted: 1998-04-28
•
Expires: 2015-07-21
Abstract
Abstract A system, method and language for compositing or creating images is disclosed. The images typically comprise a plurality of graphical elements each including color and opacity information, The system utilizes operators having the graphical elements as operands in which the operators combine the operands according to a function defined by the operators, the color information, and the opacity information, to produce new graphical elements. One part of the system includes interpreting the language by parsing and executing a sequence of statements and forming an expression tree the nodes of which comprise the graphical elements. Instructions are then derived from the tree. Another part permits the compositing of opaque graphical elements and associated clipping operations. Bounding box methods are used for locating active areas of graphical elements from the nodes. Manipulation of the expression tree is used to reduce the expected execution time of the compositing commands. An architecture is disclosed for implementing the system.
Inventors
- 👤 George Politis
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 23:14
CPC Classifications
G; G06; G06T; G06T11/00; G06T11/60
Claims Analysis
Total Claims: 37
Claim 1
Independent Claim
97 words
A method of compositing two graphical elements together utilizing a compositing operator wherein one of the graphical elements is opaque, said method being performed by a computer and comprising the steps of: (a) determining an outline of said at least one opaque object, (b) determining a corresponding clipping operation for said compositing operator when used in conjunction with said opaque object, (c) utilizing said clipping operation and said opaque object outline to derive a final clipped graphical element which is substantially the same as that produced by compositing said two graphical elements together utilizing said compositing operator.
Claim 2
Independent Claim
97 words
A method of compositing two graphical elements together utilizing a compositing operator wherein one of the graphical elements is opaque, said method being performed by a computer and comprising the steps of: (a) determining an outline of said at least one opaque object, (b) determining a corresponding clipping operation for said compositing operator when used in conjunction with said opaque object, (c) utilizing said clipping operation and said opaque object outline to derive a final clipped graphical element which is substantially the same as that produced by compositing said two graphical elements together utilizing said compositing operator.
Claim 3
Dependent Claim
27 words
A method of compositing two graphical elements together as claimed in claim 1, wherein said graphical elements and said compositing operator form part of an expression tree.
Claim 4
Dependent Claim
25 words
A method of compositing two graphical elements together as claimed in claim 1, wherein said compositing operator is an in operator or an out operator.
Claim 5
Independent Claim
144 words
A method of optimizing an expression tree for the compiling of a series of statements in a graphical programming language into a series or lower level instructions, said method being performed by a computer and comprising the steps of: (a) determining candidate nodes of said expression tree utilizing a compositing operator and which are to be composited with opaque objects, (b) storing a list of outlines of said opaque objects, (c) determining a corresponding clipping operation for at least one of said compositing operators when used in conjunction with a corresponding opaque object, (d) altering said expression tree so as to define a clipping operation between said outline of said opaque object and the graphical element represented by said candidate nodes, such that said clipping operation produces substantially the same result as that produced by compositing said graphical elements together utilizing said compositing operator.
Claim 6
Independent Claim
144 words
A method of optimizing an expression tree for the compiling of a series of statements in a graphical programming language into a series or lower level instructions, said method being performed by a computer and comprising the steps of: (a) determining candidate nodes of said expression tree utilizing a compositing operator and which are to be composited with opaque objects, (b) storing a list of outlines of said opaque objects, (c) determining a corresponding clipping operation for at least one of said compositing operators when used in conjunction with a corresponding opaque object, (d) altering said expression tree so as to define a clipping operation between said outline of said opaque object and the graphical element represented by said candidate nodes, such that said clipping operation produces substantially the same result as that produced by compositing said graphical elements together utilizing said compositing operator.
Claim 7
Dependent Claim
24 words
A method of optimizing an expression tree as claimed in claim 4, wherein said compositing operator is an in operator or an out operator.
Claim 8
Dependent Claim
43 words
A method of optimizing an expression tree as claimed in claim 4 further comprising the step of: (e) utilizing the distributive properties of said clipping operation to apply said clipping operation to all graphical elements belonging to descendant nodes of said candidate node.
Claim 9
Dependent Claim
26 words
A method of optimizing an expression tree as claimed in claim 6 wherein each descendant node utilizes the intersection of said outlines as a bounding box.
Claim 10
Dependent Claim
65 words
A method of producing a series of opcode instructions from an expression tree as claimed in claim 7, said method comprising at least one push opcode instruction for each of said opaque objects to be clipped with respect to a descendant node, said push opcode being produced to push a corresponding outline of said opaque object onto a clipping stack containing outlines of opaque objects.
Claim 11
Dependent Claim
43 words
A method of optimizing an expression tree as claimed in claim 8 wherein the object outlines pushed on said stack comprises the intersection of said opaque object corresponding to said push instruction and each of the other objects contained on said clipping stack.
Claim 12
Independent Claim
107 words
A method of compositing two graphical elements together utilizing a compositing operator wherein one of the graphical elements is opaque and causes the other to be at least partially obscured, said method being performed by a computer and comprising the steps of: (a) determining an outline of said at least one opaque object, (b) determining a corresponding clipping operation for said compositing operator when used in conjunction with said opaque object, (c) utilizing said clipping operation and said opaque object outline to derive a final clipped graphical element which is substantially the same as that produced by compositing said two graphical elements together utilizing said compositing operator.
Claim 13
Independent Claim
107 words
A method of compositing two graphical elements together utilizing a compositing operator wherein one of the graphical elements is opaque and causes the other to be at least partially obscured, said method being performed by a computer and comprising the steps of: (a) determining an outline of said at least one opaque object, (b) determining a corresponding clipping operation for said compositing operator when used in conjunction with said opaque object, (c) utilizing said clipping operation and said opaque object outline to derive a final clipped graphical element which is substantially the same as that produced by compositing said two graphical elements together utilizing said compositing operator.
Claim 14
Dependent Claim
25 words
A method of compositing two graphical elements together as claimed in claim 10, wherein said compositing operator is an in operator or an out operator.
Claim 15
Dependent Claim
91 words
Apparatus for compositing two graphical elements together utilizing a compositing operator wherein one of the graphical elements is opaque, said apparatus comprising: means for determining an outline of said at least one opaque object; means for determining a corresponding clipping operation for said compositing operator when used in conjunction with said opaque object; and means for utilizing said clipping operation and said opaque object outline to derive a final clipped graphical element which is substantially the same as that produced by compositing said two graphical elements together utilizing said compositing operator.
Claim 16
Dependent Claim
91 words
Apparatus for compositing two graphical elements together utilizing a compositing operator wherein one of the graphical elements is opaque, said apparatus comprising: means for determining an outline of said at least one opaque object; means for determining a corresponding clipping operation for said compositing operator when used in conjunction with said opaque object; and means for utilizing said clipping operation and said opaque object outline to derive a final clipped graphical element which is substantially the same as that produced by compositing said two graphical elements together utilizing said compositing operator.
Claim 17
Dependent Claim
24 words
Apparatus for compositing two graphical elements together as claimed in claim 12, wherein said compositing operator is an in operator or an out operator.
Claim 18
Dependent Claim
20 words
Apparatus as claimed in claim 12, wherein said graphical elements and said compositing operator form part of an expression tree.
Claim 19
Dependent Claim
140 words
Apparatus for optimizing an expression tree from the compiling of a series of statements in a graphical programming language into a series of lower level instructions, said apparatus comprising: means for determining candidate nodes of said expression tree utilizing a compositing operator and which are to be composited with opaque objects; means for storing a list of outlines of said opaque objects; means for determining a corresponding clipping operation for at least one of said compositing operators when used in conjunction with a corresponding opaque object; and means for altering said expression tree so as to define a clipping operation between said outline of said opaque object and the graphical element represented by said candidate nodes, such that said clipping operation produces substantially the same result as that produced by compositing said two graphical elements together utilizing said compositing operator.
Claim 20
Dependent Claim
140 words
Apparatus for optimizing an expression tree from the compiling of a series of statements in a graphical programming language into a series of lower level instructions, said apparatus comprising: means for determining candidate nodes of said expression tree utilizing a compositing operator and which are to be composited with opaque objects; means for storing a list of outlines of said opaque objects; means for determining a corresponding clipping operation for at least one of said compositing operators when used in conjunction with a corresponding opaque object; and means for altering said expression tree so as to define a clipping operation between said outline of said opaque object and the graphical element represented by said candidate nodes, such that said clipping operation produces substantially the same result as that produced by compositing said two graphical elements together utilizing said compositing operator.
Claim 21
Dependent Claim
23 words
Apparatus for optimizing an expression tree as claimed in claim 15, wherein said compositing operator is an in operator or an out operator.
Claim 22
Dependent Claim
35 words
Apparatus as claimed in claim 15, further comprising means for utilizing the distributive properties of said clipping operation to apply said clipping operation to all graphical elements belonging to descendant nodes of said candidate node.
Claim 23
Dependent Claim
21 words
Apparatus as claimed in claim 17, wherein each descendant node utilizes the intersection of said clipping operations as a bounding box.
Claim 24
Dependent Claim
68 words
Apparatus as claimed in claim 18, further comprising means for producing a series of opcode instructions from said expression tree, said means for producing at least one push opcode instruction for each of said opaque objects to be clipped with respect to a descendant node, said push opcode being produced to push a corresponding outline of said opaque object onto a clipping stack containing outlines of opaque objects.
Claim 25
Dependent Claim
37 words
Apparatus as claimed in claim 19, wherein the object outlines pushed on said stack comprise the intersection of said opaque object corresponding to said push instruction and each of the other objects contained on said clipping stack.
Claim 26
Dependent Claim
101 words
Apparatus for compositing two graphical elements together utilizing a compositing operator wherein one of the graphical elements is opaque and causes the other to be at least partially obscured, said apparatus comprising: means for determining an outline of said at least one opaque object; means for determining a corresponding clipping operation for said compositing operator when used in conjunction with said opaque object; and means for utilizing said clipping operation and said opaque object outline to derive a final clipped graphical element which is substantially the same as that produced by compositing said two graphical elements together utilizing said compositing operator.
Claim 27
Dependent Claim
101 words
Apparatus for compositing two graphical elements together utilizing a compositing operator wherein one of the graphical elements is opaque and causes the other to be at least partially obscured, said apparatus comprising: means for determining an outline of said at least one opaque object; means for determining a corresponding clipping operation for said compositing operator when used in conjunction with said opaque object; and means for utilizing said clipping operation and said opaque object outline to derive a final clipped graphical element which is substantially the same as that produced by compositing said two graphical elements together utilizing said compositing operator.
Claim 28
Dependent Claim
24 words
Apparatus for compositing two graphical elements together as claimed in claim 21, wherein said compositing operator is an in operator or an out operator.
Claim 29
Dependent Claim
101 words
A computer readable medium having recorded thereon a computer implementable method of compositing two graphical elements together utilizing a compositing operator wherein one of the graphical elements is opaque, said method comprising the steps of: (a) determining an outline of said at least one opaque object, (b) determining a corresponding clipping operation for said compositing operator when used in conjunction with said opaque object, and (c) utilizing said clipping operation and said opaque object outline to derive a final clipped graphical element which is substantially the same as that produced by compositing said two graphical elements together utilizing said compositing operator.
Claim 30
Dependent Claim
101 words
A computer readable medium having recorded thereon a computer implementable method of compositing two graphical elements together utilizing a compositing operator wherein one of the graphical elements is opaque, said method comprising the steps of: (a) determining an outline of said at least one opaque object, (b) determining a corresponding clipping operation for said compositing operator when used in conjunction with said opaque object, and (c) utilizing said clipping operation and said opaque object outline to derive a final clipped graphical element which is substantially the same as that produced by compositing said two graphical elements together utilizing said compositing operator.
Claim 31
Dependent Claim
21 words
A computer readable medium as claimed in claim 23, wherein said compositing operator is an in operator or an out operator.
Claim 32
Dependent Claim
149 words
A computer readable medium having recorded thereon a computer implementable method of optimizing an expression tree for the compiling of a series of statements in a graphical programming language into a series of lower level instructions, said method comprising the steps of: (a) determining candidate nodes of said expression tree utilizing a compositing operator and which are to be composed with opaque objects; (b) storing a list of outline of said opaque objects; (c) determining a corresponding clipping operation for at least one of said compositing operators when used in conjunction with a corresponding opaque object; and (d) altering said expression tree so as to define a clipping operation between said outline of said opaque object and the graphical element represented by said candidate nodes, such that said clipping operation produces substantially the same result as that produced by compositing said two graphical elements together utilizing said compositing operator.
Claim 33
Dependent Claim
149 words
A computer readable medium having recorded thereon a computer implementable method of optimizing an expression tree for the compiling of a series of statements in a graphical programming language into a series of lower level instructions, said method comprising the steps of: (a) determining candidate nodes of said expression tree utilizing a compositing operator and which are to be composed with opaque objects; (b) storing a list of outline of said opaque objects; (c) determining a corresponding clipping operation for at least one of said compositing operators when used in conjunction with a corresponding opaque object; and (d) altering said expression tree so as to define a clipping operation between said outline of said opaque object and the graphical element represented by said candidate nodes, such that said clipping operation produces substantially the same result as that produced by compositing said two graphical elements together utilizing said compositing operator.
Claim 34
Dependent Claim
21 words
A computer readable medium as claimed in claim 25, wherein said compositing operator is an in operator or an out operator.
Claim 35
Dependent Claim
110 words
A computer readable medium having recorded thereon a computer implementable method of compositing two graphical elements together utilizing a compositing operator wherein one of the graphical elements is opaque and causes the other to be at least partially obscured, said method comprising the steps of: (a) determining an outline of said at least one opaque object; (b) determining a corresponding clipping operation for said compositing operator when used in conjunction with said opaque object; and (c) utilizing said clipping operation and said opaque outline to derive a final clipped graphical element which is substantially the same as that produced by compositing said two graphical elements together utilizing said compositing operator.
Claim 36
Dependent Claim
110 words
A computer readable medium having recorded thereon a computer implementable method of compositing two graphical elements together utilizing a compositing operator wherein one of the graphical elements is opaque and causes the other to be at least partially obscured, said method comprising the steps of: (a) determining an outline of said at least one opaque object; (b) determining a corresponding clipping operation for said compositing operator when used in conjunction with said opaque object; and (c) utilizing said clipping operation and said opaque outline to derive a final clipped graphical element which is substantially the same as that produced by compositing said two graphical elements together utilizing said compositing operator.
Claim 37
Dependent Claim
21 words
A computer readable medium as claimed in claim 27, wherein said compositing operator is an in operator or an out operator.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-04-27 | 2001-10-27 | 2002-04-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-04-27 | 2005-10-27 | 2006-04-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-04-27 | 2009-10-27 | 2010-04-28 | $7700.00 | Window Closed / Lapsed |