So I managed to think of a case where my idea (which I had partially, but nowhere near fully, implemented) would fail. See attached sketch. The black lines are intended to represent billboard sprites (perhaps lemmings), although pretty much the same thing would arise even from them merely being the front face of a block.
There is an objectively correct answer to the rendering order here. First, note that the two non-diagonal faces of the deflector block would not be rendered anyway due to facing away from the camera. With this in mind, the correct ordering for the remaining pieces is that the deflector block's diagonal face must be drawn before the billboard on the right; while it doesn't matter which order those two are drawn in relative to the billboard on the left. However, my idea would create a cyclic result here.
Newell's algorithm specifically relies on splitting polygons. This in turn would produce the appearance of lemmings disappearing into corner blocks that they're very close to (much like Z-buffering also does). Discarding the polygon splitting aspect and simply doing the overlap detection, my hunch is that this would not eliminate cases where cyclic results emerge in cases that do have a correct draw order. If this result were going to be accepted, it would be less effort (and better performance-wise) to at least have another go at resolving the Z-buffering issues - perhaps by trying the "render only a subset of Z depths at a time" approach.
Maybe it's worth giving that a go anyway. It shouldn't be particularly time-consuming to implement.
