Method and system for fast clipping of polygons

• US 8,767,010 B2
• Filed: 12/07/2012
• Issued: 07/01/2014
• Est. Priority Date: 07/03/2008
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Blackberry Limited
• Inventors: Rajagopalan, Ramgopal
• Primary Examiner(s): Xiao, Ke
• Assistant Examiner(s): TRAN, KIM THANH THI
• Application Number:
  US13/708,197
• Publication Number:
  US 20130093772A1
• Time in Patent Office: 571 Days
• Field of Search: 345/672, 345/674, 345/678, 345/686, 345/687, 345/620, 345/624
• US Class Current: 345/620
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 15/30 Clipping
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

A method for rendering static graphics in a mobile device in applications such as map applications. Panning increments are received for panning a previously rendered frame to a panned frame. A rendering region is then determined based on the panning increment. A candidate polygon is then clipped to create clipped polygons contained within the rendering region. The clipped polygons can then be rendered, and a portion of the previously rendered frame can be copied, to provide the panned frame.

Claims

1. An electronic device comprising:

a display; and

a processor, the processor configured to;

receive panning increments for panning a previously rendered frame to a panned frame;

determine an L-shaped rendering region based on the panning increments;

clip a candidate polygon against the rendering region to determine one or more clipped portions of the candidate polygon contained within the rendering region; and

render the panned frame on the display by rending the one or more clipped portions of the candidate polygon and copying a portion of the previously rendered frame.

2. The electronic device of claim 1, wherein the panning increments comprise horizontal and vertical panning increments.

3. The electronic device of claim 1, wherein determining the rendering region comprises determining an L-shaped region having inner horizontal and vertical boundaries collinear with respective horizontal and vertical boundaries of the previously rendered frame and outer boundaries collinear with respective horizontal and vertical boundaries of the panned frame.

4. The electronic device of claim 3, wherein clipping the candidate polygon comprises:

performing a rectangular clipping operation on the candidate polygon, based on a rectangle determined by horizontal and vertical boundaries of the panned frame, to obtain one or more intermediate polygons; and

clipping the one or more intermediate polygons against the L-shaped rendering region to determine the one or more clipped portions of the candidate polygon.

5. The electronic device of claim 4, wherein clipping the one or more intermediate polygons comprises:

splitting the one or more intermediate polygons with respect to one of an interior horizontal axis and an interior vertical axis of the L-shaped rendering region to obtain one or more split polygons;

determining those of the one or more split polygons that fall within the L-shaped rendering region to be clipped portions of the candidate polygon;

clipping others of the split polygons with respect to the other one of the interior horizontal axis and the interior vertical axis of the L-shaped rendering region to form one or more further clipped polygons; and

determining those of the further clipped polygons falling within the L-shaped rendering region to be clipped portions of the candidate polygon.

6. A method of rendering in a mobile device, comprising:

receiving panning increments for panning a previously rendered frame to a panned frame;

determining an L-shaped rendering region based on the panning increments;

clipping a candidate polygon against the rendering region to determine one or more clipped portions of the candidate polygon contained within the rendering region; and

rendering the panned frame by rending the one or more clipped portions of the candidate polygon and copying a portion of the previously rendered frame.

7. The method of claim 6, wherein the panning increments comprise horizontal and vertical panning increments.

8. The method of claim 6, wherein determining the rendering region comprises determining an L-shaped region having inner horizontal and vertical boundaries collinear with respective horizontal and vertical boundaries of the previously rendered frame and outer boundaries collinear with respective horizontal and vertical boundaries of the panned frame.

9. The method of claim 8, wherein clipping the candidate polygon comprises:

performing a rectangular clipping operation on the candidate polygon, based on a rectangle determined by horizontal and vertical boundaries of the panned frame, to obtain one or more intermediate polygons; and

clipping the one or more intermediate polygons against the L-shaped rendering region to determine the one or more clipped portions of the candidate polygon.

10. The method of claim 9, wherein clipping the one or more intermediate polygons comprises:

splitting the one or more intermediate polygons with respect to one of an interior horizontal axis and an interior vertical axis of the L-shaped rendering region to obtain one or more split polygons;

determining those of the one or more split polygons that fall within the L-shaped rendering region to be clipped portions of the candidate polygon;

clipping others of the split polygons with respect to the other one of the interior horizontal axis and the interior vertical axis of the L-shaped rendering region to form one or more further clipped polygons; and

determining those of the further clipped polygons falling within the L-shaped rendering region to be clipped portions of the candidate polygon.

11. A non-transitory computer-readable medium having computer-readable code embodied therein for execution by a processor at a computing device for:

receiving panning increments for panning a previously rendered frame to a panned frame;

determining an L-shaped rendering region based on the panning increments;

clipping a candidate polygon against the rendering region to determine one or more clipped portions of the candidate polygon contained within the rendering region; and

rendering the panned frame by rending the one or more clipped portions of the candidate polygon and copying a portion of the previously rendered frame.

12. The non-transitory computer-readable medium of claim 11, wherein the panning increments comprise horizontal and vertical panning increments.

13. The non-transitory computer-readable medium of claim 11, wherein determining the rendering region comprises determining an L-shaped region having inner horizontal and vertical boundaries collinear with respective horizontal and vertical boundaries of the previously rendered frame and outer boundaries collinear with respective horizontal and vertical boundaries of the panned frame.

14. The non-transitory computer-readable medium of claim 13, wherein clipping the candidate polygon comprises:

performing a rectangular clipping operation on the candidate polygon, based on a rectangle determined by horizontal and vertical boundaries of the panned frame, to obtain one or more intermediate polygons; and

clipping the one or more intermediate polygons against the L-shaped rendering region to determine the clipped portions of the intermediate polygons for rendering.

15. The non-transitory computer-readable medium of claim 14, wherein clipping the one or more intermediate polygons comprises:

splitting the intermediate polygons with respect to one of an interior horizontal axis and an interior vertical axis of the L-shaped rendering region to form one or more split polygons;

accepting those of the split polygons that fall within the L-shaped rendering region for rendering;

clipping others of the split polygons with respect to other one of the interior horizontal axis and the interior vertical axis of the L-shaped rendering region to form one or more further clipped polygons; and

accepting those of the further clipped polygons falling within the L-shaped rendering region for rendering.