Method and apparatus for performing path rendering

• US 10,366,532 B2
• Filed: 03/16/2017
• Issued: 07/30/2019
• Est. Priority Date: 04/06/2016
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Yoo, Jeongjoon, Sundeep, Krishnadasan, Lee, Jaedon
• Primary Examiner(s): Hoang, Phi
• Application Number:
  US15/461,109
• Publication Number:
  US 20170294043A1
• Time in Patent Office: 866 Days
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree

Abstract

A method of rendering an object including a path formed by a primitive includes: generating a tree corresponding to spaces partitioned by the primitive; selecting a pixel from the partitioned spaces; and acquiring a winding number of the selected pixel by detecting the tree.

Claims

1. A method of rendering an object comprising a path formed by a primitive, the method comprising:

executing, by one or more processors, operations comprising;

generating a tree corresponding to spaces partitioned by the primitive, wherein the primitive includes a part of the path or an extension of a line of the path;

selecting a pixel from the partitioned spaces;

acquiring a winding number of the selected pixel by detecting the tree, wherein the winding number corresponds to a leaf node of the tree comprising plurality of pixels, and

determining whether to perform rendering with respect to the selected pixel based on the acquired winding number.

2. The method of claim 1, wherein the acquiring of the winding number of the selected pixel comprises:

detecting, based on location information of the selected pixel, the tree until the leaf node is reached; and

acquiring a winding number allocated to the leaf node.

3. The method of claim 2, wherein the acquiring of the winding number allocated to the leaf node comprises:

computing a winding number of the selected pixel; and

allocating the computed winding number to the leaf node.

4. The method of claim 2, wherein the detecting of the tree comprises detecting, based on location information of the selected pixel, a node corresponding to a space including the selected pixel.

5. The method of claim 1, wherein the generating of the tree comprises generating a binary space partitioning tree (BSP Tree) corresponding to the spaces partitioned by the primitive.

6. The method of claim 5, wherein the generating of the tree comprises:

partitioning a space comprising the object based on a first primitive in the primitive;

generating a node corresponding to the first primitive; and

adding the node to the tree.

7. The method of claim 6, wherein the generating of the tree comprises, in response to the partitioned space excluding another primitive:

generating a node corresponding to the partitioned space; and

adding the node corresponding to the partitioned space to the tree.

8. The method of claim 7, further comprising:

computing a winding number of an arbitrary pixel from the partitioned space; and

allocating the winding number of the arbitrary pixel to the node corresponding to the partitioned space.

9. A non-transitory computer-readable medium storing instructions that, when executed by a processor, cause the processor to perform the method of claim 1.

10. A rendering apparatus to render an object comprising a path formed by a plurality of primitives, the rendering apparatus comprising:

a tree generator configured to partition a space including the object based on the plurality of primitives, wherein each of the plurality of primitives includes a part of the path or an extension of a line of the path;

a selector configured to generate a sample of pixels to be rendered, wherein the rendering apparatus is configured to process the sample of pixels in parallel; and

a detector configured to acquire a winding number of each pixel of the sample based at least in part on the partitioned space, wherein the winding number corresponds to a portion of the partitioned space comprising a plurality of pixels.

11. The rendering apparatus of claim 10, wherein the detector is further configured to detect a tree until a leaf node is reached and acquire a winding number allocated to the leaf node based on location information of each pixel of the sample.

12. The rendering apparatus of claim 11, further comprising:

a computation processor configured to allocate the winding number to the leaf node by computing a winding number of each pixel of the sample and allocating the computed winding number to the leaf node.

13. The rendering apparatus of claim 12, further comprising:

a central processing unit (CPU) comprising any one or any combination of two or more of a tree generator, a selector, a detector, and a computation processor.

14. The rendering apparatus of claim 11, wherein the detector is further configured to detect a node corresponding to a space comprising each pixel of the sample based on location information of the pixel.

15. The rendering apparatus of claim 10, further comprising:

a GPU comprising any one or any combination of two or more of a tree generator, a selector, a detector, and a calculator.

16. The rendering apparatus of claim 10, wherein the tree generator is further configured to select a first primitive in the plurality of primitives, generate a node corresponding to the first primitive, and add the node to a tree.

17. The rendering apparatus of claim 16, wherein the tree generator is further configured to generate a node corresponding to the partitioned space and add the node corresponding to the partitioned space to a tree in response to the partitioned space comprising another primitive.

18. The rendering apparatus of claim 17, further comprising:

a computation processor configured to compute a winding of an arbitrary pixel from the partitioned space and allocate the winding number of the arbitrary pixel to the node corresponding to the partitioned space.

19. The rendering apparatus of claim 10, further comprising:

a rendering processor configured to determine whether to perform rendering with respect to each pixel of the sample based on the acquired winding number.