Method and system for fast clipping of line segments

• US 8,384,737 B2
• Filed: 05/25/2012
• Issued: 02/26/2013
• 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): Yang, Ryan R
• Application Number:
  US13/480,911
• Publication Number:
  US 20120229502A1
• Time in Patent Office: 277 Days
• Field of Search: None
• US Class Current: 345/620
• CPC Class Codes: G01C 21/367 Details, e.g. road map scale, orientation, zooming, illumination, level of detail, scrolling of road map or positioning of current position marker
• CPC Class Codes: G06T 11/20 Drawing from basic elements, e.g. lines or circles
• CPC Class Codes: G06T 15/30 Clipping
• CPC Class Codes: G09G 5/346 for systems having a bit-mapped display memory

Abstract

A method of static graphics rendering in a mobile device. Panning increments are received for panning a previously rendered frame to a panned frame. A rendering region is then determined based on the panning increments. A candidate line segment or polyline is then clipped to create clipped line segments contained within the rendering region. The clipped line segments can then be rendered, and a portion of the previously rendered frame can be copied, to provide the panned frame.

Claims

1. A computer-implemented method, comprising:

determining a rendering region based on panning increments received for panning a previously rendered frame of a static graphic image;

clipping a candidate segment against the rendering region to obtain at least one clipped segment contained within the rendering region; and

rendering the at least one clipped segment and copying a portion of the previously rendered frame to provide a panned frame.

2. The method according to 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.

3. The method according to claim 2, wherein clipping the candidate segment comprises:

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

clipping the one or more intermediate line segments against the L-shaped rendering region to determine the one or more clipped line segments.

4. The method according to claim 3, wherein clipping the one or more intermediate line segments comprises:

dividing a 2-dimensional plane containing the candidate segment into four regions with respect to the horizontal and vertical inner boundaries of the L-shaped rendering region;

determining, for each of the one or more intermediate line segments, if said intermediate line segment is wholly included or wholly excluded, based upon the respective regions in which the endpoints of said intermediate line segment are located; and

clipping those intermediate line segments that are not wholly included or wholly excluded with respect to at least one of the horizontal and vertical inner boundaries of the L-shaped rendering region.

5. The method according to claim 4, wherein determining, for each of the one or more intermediate line segments, if said intermediate line segment is wholly included or wholly excluded comprises:

assigning unique codes to each of the four regions;

assigning one of the unique codes to each end point of the intermediate line segments, based on the region in which the respective end point is located; and

determining if said intermediate line segment is wholly included or wholly excluded based on the unique codes assigned to each respective endpoint.

6. The method according to claim 4, wherein assigning unique codes to each of the four regions comprises assigning a respective one of codes (00), (01), (11) and (10) to each of the four regions.

7. The method according to claim 1, wherein the candidate segment is a candidate line segment or a candidate polyline.

8. A mobile device comprising a rendering engine for performing the method of claim 1.

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

determining a rendering region based on panning increments received for panning a previously rendered frame of a static graphic image;

clipping a candidate segment against the rendering region to obtain at least one clipped segment contained within the rendering region; and

rendering the at least one clipped segment and copying a portion of the previously rendered frame to provide a panned frame.

10. The computer-readable medium according to claim 9, 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.

11. The computer-readable medium according to claim 10, wherein clipping the candidate segment comprises:

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

clipping the one or more intermediate line segments against the rendering region to determine the one or more clipped line segments.

12. The computer-readable medium according to claim 11, wherein clipping the one or more intermediate line segments comprises:

dividing a 2-dimensional plane containing the candidate segment into four regions with respect to the horizontal and vertical inner boundaries of the L-shaped rendering region;

determining, for each of the one or more intermediate line segments, if said intermediate line segment is wholly included or wholly excluded, based on the respective regions in which the endpoints of said intermediate line segment are located; and

clipping those intermediate line segments, that are not wholly included or wholly excluded, with respect to at least one of the horizontal and vertical inner boundaries of the L-shaped rendering region.

13. The computer-readable medium according to claim 12, wherein determining, for each of the one or more intermediate line segments, if said intermediate line segment is wholly included or wholly excluded comprises:

assigning unique codes to each of the four regions;

assigning one of the unique codes to each end point of the intermediate line segments, based on the region in which the respective end point is located; and

determining if said intermediate line segment is wholly included or wholly excluded based on the unique codes assigned to each respective end point.

14. The computer-readable medium according to claim 13, wherein assigning unique codes to each of the four regions comprises assigning a respective one of codes (00), (01), (11) and (10) to each of the four regions.

15. The computer-readable medium according to claim 9, wherein the candidate segment is a candidate line segment or a candidate polyline.