It's pretty efficient, O(N), where N is the number of cells (partially) covered by something (which means some pruning of the cells that need to be processed is

It's pretty efficient, O(N), where N is the number of cells (partially) covered by something (which means some pruning of the cells that need to be processed is desirable otherwise you'd have to evaluate all of them for quadratic complexity). The algorithm is also embarassingly parallel, every cell can be processed independently so it scales perfectly with the number of processors available (if you forget about contention effects).