System and method of converting edge record based graphics to polygon based graphics

• US 20040208370A1
• Filed: 04/16/2004
• Published: 10/21/2004
• Est. Priority Date: 04/17/2003
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Blackberry Limited
• Inventors: Whatmough, Ken
• Granted Patent: US 7,525,544 B2
• Time in Patent Office: Days
• US Class Current: 382/173
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00

Abstract

A method for converting graphic object data that defines a graphic object, including converting the graphic object data from a path format to a second format, the path format including path elements that are each associated with a fill style and define one or more polygon shapes at least partially filled with the associated fill style, the path elements collectively defining the graphic object. The conversion includes (i) redefining the polygon shapes defined by the path elements as groups of triangles, and (ii) combining at least some of triangles in the groups of triangles into further polygon shapes that fall within predetermined complexity thresholds.

Claims

1. A method for converting graphic object data that defines a graphic object, comprising steps of:

(a) converting the graphic object data from a path format to a second format, the path format including path elements that are each associated with a fill style and define one or more polygon shapes at least partially filled with the associated fill style, the path elements collectively defining the graphic object, the conversion including;

(i) redefining the polygon shapes defined by the path elements as groups of triangles; and

(ii) combining at least some of triangles in the groups of triangles into further polygon shapes that fall within predetermined complexity thresholds.

2. The method of claim 1 including, prior to step (a), a first converting step of converting first graphic object data defining the graphic object from an edge record based format to the path format, the edge record based format including a plurality of edge records each defining an edge of the graphic object, the edge records including information associating the defined edges with fill styles that the edges border against.

3. The method of claim 2 wherein the first converting step includes:

for each fill style, identifying from the edge records each unique vertex that borders on the fill style and identifying each of the outgoing edges from the identified vertices that border on the fill style; and

for each fill style, creating the associated path element, based on the identified vertices and outgoing edges.

4. The method of claim 3 wherein the path format is an SVG compatible format.

5. The method of claim 3 wherein the edge record based format is an edge record based flash file format.

6. The method of claim 1 wherein the second format graphic object data includes information defining the further polygons, the method including a step of sending the second format graphic object data over a communications link to a viewing device having predetermined capabilities, and wherein the complexity thresholds are based on the predetermined capabilities of the viewing device.

7. The method of claim 1 wherein the complexity thresholds are selected so that the further polygons each have a continuous interior fill style region without internal island contours.

8. The method of claim 1 wherein the complexity thresholds are selected so that the further polygons each have only convex vertices.

9. The method of claim 1 wherein the complexity thresholds are selected so that the further polygons each have under a predetermined number of sides.

10. The method of claim 1 wherein the complexity thresholds are selected so that the further polygons are each simple polygons.

11. A method for converting graphic object data defining a graphic object from an edge record based format to a path format, the edge record based format including a plurality of edge records each defining an edge of the graphic object, the edge records including information associating the defined edges with fill styles that the edges border against, the path format including path elements that each define one or more polygon shapes that are filled with an associated fill style, the path elements collectively defining the graphic object, the method including steps of:

for each fill style, identifying from the edge records each unique vertex that borders on the fill style and identifying each of the outgoing edges from the identified vertices that border on the fill style; and

for each fill style, creating an associated path element defining one or more polygon shapes that are filled with the identified unique fill style, based on the identified vertices and outgoing edges.

12. The method of claim 11, including converting the graphic object data from the path format to a triangulated format by redefining the polygon shapes defined by the path elements as groups of triangles.

13. The method of claim 12, including converting the graphic object data from the triangulated format to a further format by combining at least some of triangles in the groups of triangles into further polygon shapes that fall within predetermined complexity thresholds.

14. A system for converting graphic object data defining a graphic object having associated fill styles from a path format to a second format, the path format including path elements that are each associated with a fill style and define one or more polygon shapes at least partially filled with the associated fill style, the path elements collectively defining the graphic object, the system comprising:

a triangulation module for redefining the polygon shapes defined by the path elements as groups of triangles; and

a combining module for combining at least some of triangles in the groups of triangles into further polygon shapes that fall within predetermined complexity thresholds.

15. The system of claim 14 including a first format converter for converting initial graphic object data defining the graphic object from an edge record based format to the path format, the edge record based format including a plurality of edge records each defining an edge of the graphic object, the edge records including information associating the defined edges with fill styles that the edges border against, the fist format converter including:

a first sub-converter for identifying each unique fill style in the edge record based format initial graphic object data, and for each identified unique fill style, identifying from the edge records each unique vertex that borders on the fill style and identifying each of the outgoing edges from the identified vertices that border on the fill style; and

a second sub-converter for creating the associated path element, based on the identified vertices and outgoing edges, for each identified unique fill style.

16. The system of claim 14 wherein the complexity thresholds are configured so that the further polygons each are selected from the group consisting of polygons that have a continuous interior fill style region without internal island contours, polygons that have only convex vertices, polygons that have under a predetermined number of sides, and polygons that are simple polygons.

17. A computer software product having a computer-readable medium tangibly embodying computer executable instructions for converting graphic object data that defines a graphic object, the computer executable instructions comprising:

computer executable instructions for converting the graphic object data from a path format to a second format (104), the path format including path elements that are each associated with a fill style and define one or more polygon shapes at least partially filled with the associated fill style, the path elements collectively defining the graphic object, the conversion characterized by;

(i) redefining the polygon shapes defined by the path elements as groups of triangles; and

(ii) combining at least some of triangles in the groups of triangles into further polygon shapes that fall within predetermined complexity thresholds.

18. The computer software product of claim 17 further including computer executable instructions for converting initial the graphic object data defining the graphic object from an edge record based format to the path format, the edge record based format including a plurality of edge records each defining an edge of the graphic object, the edge records including information associating the defined edges with fill styles that the edges border against.