Patent ID: 9495792
Filing Date: 2016-11-15
CPC Classification: G06T

Claim Text:
1. A method of image generation implemented by traversing a binary tree in a ray tracing system having a processor, so as to generate an image, the method comprising: intersection testing, using the processor, whether child nodes intersect a ray while traversing the binary tree, wherein one-bit stacks are respectively assigned to levels of the binary tree; in response to the intersection testing revealing that a number of child nodes intersecting the ray is two, using the processor to perform a setting of a bit of the one-bit stack assigned to a tree level of a parent node to a first value and a pushing of one node of the child nodes to a stack; in response to a traversed node being a leaf node or no child node intersecting the ray, using the processor to perform a setting of a highest level among levels of the one-bit stack having bit values set to the first value to be a pop level and a changing of a bit of the one-bit stack corresponding to the pop level to a second value; using the processor to perform a beginning of the traversal again starting from a root node, and a traversing of a node that has not yet been traversed among child nodes intersecting a ray at the pop level when the pop level is reached so as to generate graphics of the image in accordance with a bit value of all of the one-bit stacks at the pop level corresponding to the second value; and displaying the image based on the generated graphics.