Method and system for fast clipping of line segments

• US 8,624,919 B2
• Filed: 01/17/2013
• Issued: 01/07/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): Yang, Ryan R
• Application Number:
  US13/743,991
• Publication Number:
  US 20130127871A1
• Time in Patent Office: 355 Days
• Field of Search: 345/581, 345/620, 345/624
• 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. An electronic device, comprising:

a display; and

a processor, the processor configured to;

determine a refresh region and a copy region of a panned frame based on panning increments between the panned frame and a previously rendered frame;

clip a candidate segment against the refresh region to obtain one or more clipped segments within the refresh region; and

render the panned frame on the display by rendering the one or more clipped segments in the refresh region of the panned frame and copying a portion of the previously rendered frame to the copy region of the panned frame.

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

3. The electronic device of claim 2, wherein the refresh region is L-shaped.

4. The electronic device according to claim 3, wherein determining the L-shaped refresh 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.

5. The electronic device according to claim 4, wherein clipping the candidate segment comprises:

performing a 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 segments; and

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

6. The electronic device according to claim 5, wherein clipping the one or more intermediate 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 refresh region;

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

clipping those intermediate 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 refresh region.

7. The electronic device according to claim 6, wherein determining, for each of the one or more intermediate segments, if said intermediate 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 segments, based on the region in which the respective end point is located; and

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

8. The electronic device according to claim 7, 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.

9. A computer-implemented method, comprising:

determining a refresh region and a copy region of a panned frame based on panning increments between the panned frame and a previously rendered frame;

clipping a candidate segment against the refresh region to obtain one or more clipped segments within the refresh region; and

rendering the panned frame by rendering the one or more clipped segments in the refresh region of the panned frame and copying a portion of the previously rendered frame to the copy region of the panned frame.

10. The method of claim 9, wherein the panning increments comprise horizontal and vertical panning increments.

11. The method of claim 10, wherein the refresh region is L-shaped.

12. The method according to claim 11, wherein determining the L-shaped refresh 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.

13. The method according to claim 12, wherein clipping the candidate segment comprises:

performing a 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 segments; and

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

14. The method according to claim 13, wherein clipping the one or more intermediate 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 refresh region;

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

clipping those intermediate 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 refresh region.

15. The method according to claim 14, wherein determining, for each of the one or more intermediate segments, if said intermediate 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 segments, based on the region in which the respective end point is located; and

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

16. The method according to claim 15, 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.

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

determining a refresh region and a copy region of a panned frame based on panning increments between the panned frame and a previously rendered frame;

clipping a candidate segment against the refresh region to obtain one or more clipped segments within the refresh region; and

rendering the panned frame by rendering the one or more clipped segments in the refresh region of the panned frame and copying a portion of the previously rendered frame to the copy region of the panned frame.

18. The computer-readable medium according to claim 17, wherein determining the refresh 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.

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

performing a 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 segments; and

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

20. The computer-readable medium according to claim 19, wherein clipping the one or more intermediate 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 refresh region;

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

clipping those intermediate 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 refresh region.