Patent ID: 8692825

Claim:
A method comprising: during initial population of a spatial data structure with data usable to render an image of a three-dimensional model: receiving primitive data from a primitive generator, wherein the primitive data comprises properties of a primitive; partially traversing the spatial data structure, using a master processing element, to identify an internal node of the spatial data structure, wherein the internal node represents a portion of the three-dimensional model, wherein the internal node is identified based on the primitive data; selecting a slave processing element from a plurality of slave processing elements, wherein the selected slave processing element is associated with the internal node; sending the primitive data to the selected slave processing element, wherein the selected slave processing element traverses a portion of the spatial data structure to identify a leaf node of the spatial data structure; determining whether the leaf node includes a threshold number of primitives, wherein: when the leaf node does not include the threshold number of primitives, the selected slave processing element sends information identifying the leaf node to the master processing element; when the leaf node does include the threshold number of primitives, the selected slave processing element determines whether expanding the leaf node will cause the leaf node to extend into a portion of the three-dimensional model that is not associated with the selected slave processing element; when expanding the leaf node will cause the leaf node to extend into a portion of the three-dimensional model that is not associated with the selected slave processing element, the selected slave processing element selects a second slave processing element to which to send the primitive data, the second slave processing element being a slave processing element associated with the portion of the three-dimensional model into which the leaf node extends when expanded and being the slave processing element that is to send a path of the leaf node to the master processing element as information identifying the leaf node; and when expanding the leaf node will not cause the leaf node to extend into a portion of the three-dimensional model that is not associated with the selected slave processing element, the selected slave processing element expands the leaf node and sends a path of the leaf node to the master processing element as the information identifying the leaf node; receiving information identifying the leaf node from one of the plurality of slave processing elements; and inserting the primitive data into the leaf node.