Search

EP-3625771-B1 - A PARALLELIZED PIPELINE FOR VECTOR GRAPHICS AND IMAGE PROCESSING

EP3625771B1EP 3625771 B1EP3625771 B1EP 3625771B1EP-3625771-B1

Inventors

  • MACKINNON, ALLAN, STUART, JR.

Dates

Publication Date
20260506
Application Date
20180315

Claims (12)

  1. A method (1800) for rasterizing and compositing vector graphics in parallel on a data-parallel computing device comprising: loading (1801), by one or more parallel processors, vector data of the vector graphics into local memory accessible by the one or more parallel processors, wherein the vector data includes one or more paths comprised of one or more path segments of the vector graphics; rasterizing (1803), by the one or more parallel processors, the one or more path segments into respective rasters, wherein the rasterizing splits the path segments into subpixel line segments (1001a-1001i) which define locations of the path segments within bounds of raster pixel tiles having a predefined width and height, wherein the endpoints of each subpixel line segment (1001a-1001i) are defined by X and Y coordinate crossings and each subpixel line segment (1001a-1001i) has an axis width of less than or equal to one pixel, each respective raster corresponding to selected ones of the subpixel line segments (1001a-10011); assigning (1805), by the one or more parallel processors, each of the respective rasters into groups based on pixel coordinates of the respective rasters, wherein each group has an associated key and the rasters within each group represent a portion of the same vector graphic; placing (1807), by the one or more parallel processors, the rasters onto subpixels according to their respective pixel coordinates; and rendering (1809), by the one or more parallel processors, the rasters onto a display.
  2. The method of claim 1, wherein loading the vector data occurs in response to the one or more parallel processors receiving pull commands which identify a location of the vector data in a host memory.
  3. The method of claim 1, wherein loading the vector data further includes simultaneously building a path data structure for each of the one or more paths in the vector data.
  4. The method of claim 3, wherein each path data structure includes a respective path head as a root node to linked list data structures comprising blocks, each respective path head containing descriptive information about a total path calculated during pull commands.
  5. The method of claim 4, wherein, for each path head, the descriptive information about the total path includes one or more of (i) a total number of blocks which were required for a path, (ii) how many lines and curves are in the path, (iii) the total path's 2D bounds, and (iv) a head node indicating a location of a first path node in the linked list data structure.
  6. The method of claim 4, wherein each path head is associated with path nodes.
  7. The method of claim 6, wherein each path node includes a segment count block which stores a total number of segments within the respective path node and a next node block which stores a location of the next path node in the linked list.
  8. The method of claim 4, wherein each path node includes path segment blocks storing indices which point to blocks of data associated with the one or more path segments.
  9. The method of claim 8, wherein the path segment blocks include a type block which defines geometry of the path segments which make up the path represented by the path node, wherein the geometry may be curves or a line segment.
  10. The method of claim 1, wherein the rasterizing includes converting path segments into tile trace subpixels, TTSs, and packing the TTSs into tile trace subpixel blocks, TTSBs.
  11. A non-transitory computer readable medium storing instruction, which when executed by one or more parallel processors, cause the one or more parallel processors to perform the steps of the method defined in any of the claims 1 to 10.
  12. A system for rasterizing and compositing vector graphics in parallel comprising: one or more data-parallel computing devices; and memory storing instructions, the instructions executable by the one or more data-parallel computing devices, wherein the instructions comprise: loading (1801) vector data of vector graphics into local memory accessible by the one or more parallel processors, wherein the vector data includes one or more paths comprised of one or more path segments of the vector graphics; rasterizing (1803) the one or more path segments into respective rasters, wherein the rasterizing splits the path segments into subpixel line segments (1001a-1001i) which define locations of the path segments within bounds of raster pixel tiles having a predefined width and height, wherein the endpoints of each subpixel line segment (1001a-1001i) are defined by X and Y coordinate crossings and each subpixel line segment (1001a-1001i) has an axis width of less than or equal to one pixel, each respective raster corresponding to selected ones of the subpixel line segments (1001a-1001i); assigning (1805) each of the respective rasters into groups based on pixel coordinates of the respective rasters, wherein each group has an associated key and the rasters within each group represent a portion of the same vector graphic; placing (1807) rasters onto subpixels according to their respective pixel coordinates; and rendering (1809) the rasters onto a display.

Description

BACKGROUND Processing and displaying vector graphics, such as a web page's type on a laptop's display or a map on a smartphone's touch screen, requires significant processing resources. As the number and size of displays continue to grow, faster, more efficient processing of vector graphics becomes necessary. However, declining advances in processing performance using current vector graphics processing techniques threatens to reduce the use of vector graphics. Many methods of processing vector graphics data rely on a computing device's central processing unit (CPU), with or without assistance from a graphical processing unit (GPU). For decades, vector graphics processing has been seen as being incompatible with data-parallel computing devices like GPUs. As such, most vector graphics processing techniques fail to take advantage of the GPU's ability to process data in parallel. Current vector graphics processing techniques tend to focus on accelerating only a fraction of a complete vector graphics processing pipeline using parallel processing, with the remainder continuing to be processed with scalar CPU algorithms. While modest speedups relative to the available computing power of the GPU have been realized by performing a portion of the vector graphics processing pipeline in parallel, the bulk of the GPU's computing power is not utilized. Additionally, energy inefficiencies are prevalent in in current vector graphics techniques due to the continual utilization of both the scalar CPU and the GPU. Moreover, most of these vector graphics techniques sacrifice visual quality with imprecise antialiasing. WANG YAFEI ET AL: "Parallel scanline algorithm for rapid rasterization of vector geographic data", COMPUTERS AND GEOSCIENCES, vol. 59, September 2013 (2013-09), pages 31-40, XP028685384, ISSN: 0098-3004, DOI: 10.1016/J.CAGEO.2013.05.005 discloses parallel rasterization algorithms on polygon data. SUMMARY The invention is defined by the independent claims. The dependent claims specify embodiments thereof. Embodiments within the disclosure relate generally to processing vector graphics on a computer system. One aspect includes a method for rasterizing and compositing vector graphics in parallel on a data-parallel computing device. The method comprising loading, by one or more parallel processors, vector data of the vector graphics into local memory accessible by the one or more parallel processors, wherein the vector data includes one or more paths comprised of one or more path segments of the vector graphics; rasterizing, by the one or more parallel processors, the one or more path segments into respective rasters; assigning, by the one or more parallel processors, each of the rasters into groups based on pixel coordinates of the respective rasters, wherein each group has an associated key and the rasters within each group represent a portion of the same vector graphic; placing, by the one or more parallel processors, the rasters onto subpixels according to their respective pixel coordinates; and rendering, by the one or more parallel processors, the rasters onto a display. In some examples, loading the vector data occurs in response to the one or more parallel processors receiving pull commands which identify a location of the vector data in a host memory. In some examples, loading the vector data further includes simultaneously building a path data structure for each of the one or more paths in the vector data. In some examples, each path data structure includes a respective path head as a root node to linked list data structures comprising blocks, each respective path head containing descriptive information about a total path calculated during pull commands. In some examples, for each path head, the descriptive information about the total path includes one or more of (i) a total number of blocks which were required for a path, (ii) how many lines and curves are in the path, (iii) the total path's 2D bounds, and (iv) a head node indicating a location of a first path node in the linked list data structure. In some examples, each path head is associated with path nodes. In some examples, each path node includes a segment count block which stores a total number of segments within the respective path node and a next node block which stores a location of the next path node in the linked list. In some examples, each path node includes path segment blocks storing indices which point to blocks of data associated with the one or more path segments. In some examples, the path segment blocks include a type block which defines geometry of the path segments which make up the path represented by the path node, wherein the geometry may be curves or a line segments. In some examples, the rasterizing includes converting path segments into tile trace subpixels (TTSs), and packing the TTSs into tile trace subpixel blocks (TTSBs). Another aspect includes a non-transitory computer readable medium according to claim 11. Another aspec