You are right. And even faster you can compute left and right border at the same time you are filling objects (routine is not so easy to code but a bit faster, because you save many read/write to memory). TCB use that great trick with another one in their "flashback" 3d introduction. TCB use a great trick for speed up polygons where lines are "almost vertical". If the two left/right border does not change, they "jump" directly in the same filling routine.When using convex 3D objects, you just have to test if an object is visible with 2 multiplications, then all lines that go down are right borders, and all lines that go up are left borders (if you use clockwise order).
Once you computed all left and right borders, you just have to fill horizontal lines.
I use it in my really fast ARM polygon filler used for a speed contest with a friend. it's actually (I guess) the fastest flat-shaded polygon filler on GBA (ARM7)