Why are there 2N-2 splitting positions for node with N primitives (referencing the same slide last year here: http://15462.courses.cs.cmu.edu/fall2015/lecture/acceleration/slide_025)
joel
In 2D, we can split the space on either the left or right of each triangle's centroid, as shown in the diagram above. This gives us 2N possible splits for N triangles in total, assuming that the triangles have distinct centroids. Then, we observe that the split to the left of the leftmost triangle and the split to the right of the rightmost triangle don't make any difference and are kind of useless. So we have 2N-2 splits we might actually want to make.
keenan
@Cake because you can put the split plane at either extreme point of each primitive along the given axis. The minus-two comes from the fact that putting the split plane to the "right" or "left" of all the primitives isn't actually a splitting. ;-)
This count is basically indicated in the figure: notice that each vertical line touches the leftmost or rightmost point of some triangle. But the very leftmost and very rightmost point in the entire collection is omitted (no vertical line).
keenan
Whoops, look like @joel and I responded at the same time. ;-)
strikeskids
Shouldn't this really be N-2 split points in a single axis? If we have primitives a, b, c in order, choosing to split on the right side of a would give us the same construction as choosing to split on the left side of b.
keenan
@strikekids: Yes, but only because we're determining the partition by the centroid of the primitive.
Why are there 2N-2 splitting positions for node with N primitives (referencing the same slide last year here: http://15462.courses.cs.cmu.edu/fall2015/lecture/acceleration/slide_025)
In 2D, we can split the space on either the left or right of each triangle's centroid, as shown in the diagram above. This gives us 2N possible splits for N triangles in total, assuming that the triangles have distinct centroids. Then, we observe that the split to the left of the leftmost triangle and the split to the right of the rightmost triangle don't make any difference and are kind of useless. So we have 2N-2 splits we might actually want to make.
@Cake because you can put the split plane at either extreme point of each primitive along the given axis. The minus-two comes from the fact that putting the split plane to the "right" or "left" of all the primitives isn't actually a splitting. ;-)
This count is basically indicated in the figure: notice that each vertical line touches the leftmost or rightmost point of some triangle. But the very leftmost and very rightmost point in the entire collection is omitted (no vertical line).
Whoops, look like @joel and I responded at the same time. ;-)
Shouldn't this really be N-2 split points in a single axis? If we have primitives a, b, c in order, choosing to split on the right side of a would give us the same construction as choosing to split on the left side of b.
@strikekids: Yes, but only because we're determining the partition by the centroid of the primitive.