Can someone explain why the intersection cost is O(cube root N)? Thanks.
Tdog
Does N here represent the number of squares or the side length of the big square?
motoole2
@Tdog @ziqichen N represents the number of squares in the volume, which we assume to be proportional to the number of primitives. In 2D, the intersection cost would be the square root of N, since a line through this grid intersects approximately this number of grid cells. In 3D, the intersection cost would be the cube root of N.
Cube root of N grows faster than log(N).
Can someone explain why the intersection cost is O(cube root N)? Thanks.
Does N here represent the number of squares or the side length of the big square?
@Tdog @ziqichen
Nrepresents the number of squares in the volume, which we assume to be proportional to the number of primitives. In 2D, the intersection cost would be the square root ofN, since a line through this grid intersects approximately this number of grid cells. In 3D, the intersection cost would be the cube root ofN.