A method performed by a graphics processor for updating a bouding volume hierarchy, BVH, the method comprising the steps of: obtaining a starting BVH, being a data structure comprising nodes (202, 204, 206) representing different 3D regions of space in a modelled environment, the data structure comprising a tree in which the nodes are arranged hierarchically from a root node down to a plurality of leaf nodes, wherein the region modelled by each leaf node encompasses at least one primitive or part of a primitive; performing one or more iterations, starting with a first of the one or more iterations which starts with the starting BVH as a current BVH, each iteration comprising: - a search phase comprising, for each respective one of a plurality of input nodes in the tree of the current BVH, searching for at least one respective candidate reinsertion which would move the respective input node from an old parent to a new parent in the tree, and which compared to the current BVH would reduce an expected computational cost that would be incurred by searching the tree to determine whether a modelled ray would intersect with one of the primitives, according to a metric for estimating said computational cost; and - performing a first update to update the current BVH with one or more selected reinsertions from among the candidate reinsertions; wherein the selection comprises a conflict check to determine whether any group of the candidate reinsertions would affect a same part of the tree of the current BVH as one another, and if so selecting only one of the group to include in the first update; and characterized in that at least one of the iterations further comprises, after the first update, performing a second update within the same iteration to update the current BVH with another of said group from the search phase of the same iteration. obtaining a starting BVH, being a data structure comprising nodes (202, 204, 206) representing different 3D regions of space in a modelled environment, the data structure comprising a tree in which the nodes are arranged hierarchically from a root node down to a plurality of leaf nodes, wherein the region modelled by each leaf node encompasses at least one primitive or part of a primitive; performing one or more iterations, starting with a first of the one or more iterations which starts with the starting BVH as a current BVH, each iteration comprising: - a search phase comprising, for each respective one of a plurality of input nodes in the tree of the current BVH, searching for at least one respective candidate reinsertion which would move the respective input node from an old parent to a new parent in the tree, and which compared to the current BVH would reduce an expected computational cost that would be incurred by searching the tree to determine whether a modelled ray would intersect with one of the primitives, according to a metric for estimating said computational cost; and - performing a first update to update the current BVH with one or more selected reinsertions from among the candidate reinsertions; - a search phase comprising, for each respective one of a plurality of input nodes in the tree of the current BVH, searching for at least one respective candidate reinsertion which would move the respective input node from an old parent to a new parent in the tree, and which compared to the current BVH would reduce an expected computational cost that would be incurred by searching the tree to determine whether a modelled ray would intersect with one of the primitives, according to a metric for estimating said computational cost; and - performing a first update to update the current BVH with one or more selected reinsertions from among the candidate reinsertions; wherein the selection comprises a conflict check to determine whether any group of the candidate reinsertions would affect a same part of the tree of the current BVH as one another, and if so selecting only one of the group to include in the first update; and characterized in that at least one of the iterations further comprises, after the first update, performing a second update within the same iteration to update the current BVH with another of said group from the search phase of the same iteration.