Wow! Those are so cool! Would be a dream for a screensaver in SymbOS 
Awesome David, very interesting.
Storing the face normal is a nice one, I was already thinking on how to tackle backface culling. In screen space it involves a cross product I think, but this seems simpler because you can do it in model space way earlier in the process. Costs three multiplications rather than two, but I’m sure that can be won back, like skipping the transform of culled vertices.
The middle point is also nice. My depth calculation currently goes as follows: average z of each vertex pair is stored on the edges, and for each scanline the z is the average of the two edges. My way to avoid an annoying divide by 3 
. It’s still a bit flaky though (see z-fighting in the video), but I hope backface culling will help, or maybe 16-bit depth… Anyway, doing it once upfront may be cheaper, perhaps also more exact. Although I saw from the Sandstone beta code that you were also struggling with z-fighting.
To update spans which changed between frames, currently I do everything with the CPU but parallelising with the VDP could be interesting; if the span exceeds a certain minimum length I could issue a VDP command for it, and just let it run while I continue. Drawing vertical lines will be difficult though I think with my horizontal scanline-based spans approach.
Painter’s is effectively what I’d be doing if I would z-sort before inserting into the span buffer, I could skip the depth comparisons as well as omit storing depth info in the span buffer… Hmm.
The blockfill I don’t need because I don’t clear the previous frame, rather I use it. This means I have a ton of spare VDP command engine time… what to do :D.
The multiplication you mentioned, I was looking at it earlier, but is there a way to do something like that for 16-bit multiplications without needing a 256K lookup-table? And would perchance a similar trick exist for division or reciprocal? :)
Oh, did you use any divisions at all? Maybe you used orthogonal projection so no need for perspective divide?
Some questions on tracing the edges;
Did you use Bresenham for interpolating the x or fixed point additions? I’m currently using the former but have some code shelved which does the latter, the lines still look nice despite floating point error, but that 16-bit divide is a bit scary. I think the simplified tracing might not compensate for the extra overhead of the division (need to measure).
Also, how did you deal with x-major Bresenham stepping? I currently do an 8-bit division to determine the step size, and then use Bresenham with the remainder to decide when I need to add 1 more (Bresenham’s Run-Slice algorithm). However if I could avoid that division… Also the lines I get are a bit misaligned (acceptable, but still), because the spans are rounded up, if you understand what I mean.
About division, yes I have a few of them but if possible I try to avoid them since the multiplication routine is faster.
In calculus I draw wireframes with depth correction, so there I use the z of the vertex to lookup the multiplication factor in a nice table. That factor is applied to both x and y components. Using an extra offset with the z-component in this lookup table will create a simply way to implement the zoom in that demo part. So the division for depth correction is mitigated by using the lookup and a fast multiplication.
In SandStone there is no depth correction, since this would screw up using the z-component of the normalvector as visible vs non-visible indicator. Think of a default wireframe cube:
+------+ |\ /| | +--+ | | | | | | +--+ | |/ \| +------+
If you twist it a few degrees the side panels will still not be visible if you apply depth correction, while the z-component would indicate that you need to draw it...
+------+ || /| |+--+ | || | | |+--+ | || \| +------+
The lookup table is still used for the zoom but the z-component of the vertex is ignored in that engine.
Bresenham.
No fixed point additions, no run-slice algorithm is used. There is some self-modifying code in my engine and there are 4 routines depending on the angle that the line is drawn (0-45, 45-90, 90-135,135-180) the first and last simply loop a few times until a new y is calculated. This keeps the code simpler and is still fast enough. If this loop is needed then it also implies that the VDP is drawing longer lines, so a little more time can be spend anyway, otherwise the code could simply be waiting for the VDP command to end anyway 
In SandStone there is no depth correction, since this would screw up using the z-component of the normalvector as visible vs non-visible indicator.
Ah, right... that’s very good to know, I didn’t realise that.
I think there’s a way that does work with perspective projection; take the dot product of the face normal with the camera-to-face vector (any face vertex will do). If the result is positive or zero, then the camera is looking at the rear or the side of the polygon.
Bresenham. There are 4 routines depending on the angle that the line is drawn (0-45, 45-90, 90-135,135-180) the first and last simply loop a few times until a new y is calculated. This keeps the code simpler and is still fast enough. If this loop is needed then it also implies that the VDP is drawing longer lines, so a little more time can be spend anyway, otherwise the code could simply be waiting for the VDP command to end anyway
I definitely get the simplicity argument. It was my initial implementation before I read about run-slice.
I figured if a horizontal line goes right across the screen, that’s a lot of add-and-compare loops . The loop of the 8-bit divide is pretty similar in size, but has a fixed 8 iterations. Long horizontal lines should benefit, but short or sloped lines become slower. I wonder for an average scene which performs better.
Btw, I realised I can skip the division in the second and third octant, because it’ll always be 0. D’oh.