A set of primitives is divided into plural sub-sets of primitives, and a tree representation for representing the set of primitives in which each leaf node of the tree represents one of the sub-sets, and each parent node of the tree represents a sub-set of primitives corresponding to the combination of the sub-sets of primitives of all of its child nodes, is generated. For each node of the tree representation data indicating: the sub-set of primitives that the node represents; the vertices that are used by the primitives in the sub-set of primitives that the node represents; and the volume of space that the sub-set of primitives that the node represents falls within, is determined. The tree representation is then used to determine a set of primitives and a set of vertices to be processed when processing the set of primitives for the output frame.