The algorithm was, roughly, to render 16x16 pixels at random in the scene. If the variance in colors was low, you're done. If it's high, you cut it in half (kd-tree). Pick a region at random and a random 16x16 pixels and render them. If it's low variance you're good, otherwise split. Eventually things like a wall would have maybe 4 regions describing it, though taking up a large portion of the final image. You repeat this random selection and rendering continuously. There was also a way to merge regions should the scene change and they have a similar color though I've forgotten the details.
It was quite fast on commodity hardware from 2004/2005.