1. To simplify things, draw triangles instead of polygons, it's a lot simpler. Each triangle is divided up into 2 triangles (one upper and one lower).
2. Don't use Bresenham to scan the edges, use DDA with fixed point arithmetic.
3. Sorting of y coordinates is done only once per triangle.
4. Identification of the left and right edges is only done once per triangle.
5. Look-up tables with pre-calculated lines for the edges require quite a lot of memory and will lead to imperfections (Omega did this for the Grotesque demo, look carefully and you'll be able to spot the imperfect edges and sometimes odd looking objects). It's a trade-off I guess.
6. There's quite a few ways of speeding things up. Draw triangles/polygons that are side by side on different planes to avoid having to perform 'or' operations on begin/end words. Use the blitter if available. Fill triangles/polygons vertically rather than horizontally, and so on. A lot of time were put into developing fast routines. It wasn't done over night.