Dug up my notes on the line clipping algorithm I wrote back in the day. I ended up doing a divide and conquer using line midpoints. Midpoints are easy; (x1+x2)/2 and (y1+y2)/2, and it suits 8 bits as it just uses addition and shift operations - no pesky multiply or divides required.
Aha - "line clipping" isn't a term I'd heard before, but it's exactly the sort of technique I was thinking about for a webpage that tells you where your nearest West Midlands bus stop is if you are outside their service area. Thanks! PS. That's abstraction, kids! ;-)
Yeah midpoint was the way I went on the 8 bits, but used divides on 16 bits. Potentially Elite's method with 8 bit logs for divides is faster in most cases over midpoint, but I wasn't smart enough to realise in '85!
Oh, I probably should explain the "no divides required" when there are two "/2"'s in the equations. In binary, a divide by two is the same as shifting right one bit, an easy operation in Z80. Similarly multiply by two is the same as shifting left one bit....
For anyone who'd like to try that... www.advanced-ict.info/interactive/...
Cool! I like that.
There's a bitwise logic page too: www.advanced-ict.info/interactive/...
More specifically, multiplying or dividing a number (N) in a given base (B) by B is the same as shifting that number (N) left and right along its number columns. For example, multiplying 1234 by 10 in decimal.
There is a deep dive on Elite's line clipping here, btw.
My brain isn't functioning and I can't follow the 6502 line clipping algorithm in the Elite deep dive. When it says "move the point along the line until it's on screen", it makes it sound as if it literally moves one step at a time until x is on screen. Which sounds mad.
I don’t think it does that. But only glanced at the code.
Is this similar to the way Elite on the Beeb does it @markmoxon.bsky.social?
Been a while since I looked at this bit of code, but Elite does the whole division thing. Not surprising really - the authors were super-proud of their maths routines, so they used them! Deepish dive: elite.bbcelite.com/deep_dives/l... The clipping code: elite.bbcelite.com/cassette/mai...
Might take a closer look at their code to see if there are any tricks i can borrow.
Yeah I just had a quick scan of the code. Don’t blame them tbh.
I'm slightly puzzled. They are doing a load of division, but surely it's more efficient to do the chop that you describe?
Maybe. But it is probably quicker than drawing the entire line and writing a 16 bit plot routine that checks each point is on screen.
With each iteration, you choose the two points on the line whose midpoint is closest to the desired intersection. I'll have a crack at coding an example in BASIC later.
Divide And Conquer !!
You're going to get wonky results. Each midpoint will get rounded to your integer coord space, and if that's pixels you're in for a world of pain - jittery intercepts and gaps in meshes.
It worked out fine back in the day. It’s only the point off screen that is changed, so no gaps in meshes.
If you keep splitting the line and keep the clipped half until it's 1px, each successive subline could be a different angle until the clip intercept is significantly off the original line. You may well be happy enough with the result; your line lengths and angles may be kind in your case;
your meshes may mitigate co-linearity (ie no node colinear with an edge); but this is a mathematical fact - you WILL get distortion. I can give mathematical examples if you want.
No it's fine thanks. The 3D routine I wrote was designed for performance at low resolutions using 8 and 16 bit integer maths. And the algorithm I wrote was acceptable in that respect.
The RISC OS Draw module has a similar problem when "dashing" a line - it keeps using the calculated intercept as the new end of line, which changes the angle as it goes. It's working with fixed point coords 1/512 of a px. At whole pixels the problem is really bad straight away.
(I keep meaning to fix that and then I forget about it)
In this pic the blue and white lines are the SAME line - the exact same endpoints - but the successive quantisation during incremental clipping (effectively) of the dashed line results in this massive failure if co-linearity:
Hmm. Did you optimise it by having four near-duplicate routines for lines that overflowed left, right, top, bottom?
1/ Also, you only need the midpoint of x to determine how many iterations are needed to get x/equal to the screen boundary. Each iteration is a half-step in one of two directions. Is there a shortcut for calculating y based on this accumulated info such that...
2/ You iterate x (in your example) and flag 0/1 bits for each iteration plus an iteration count, and then calculate y afterwards - if there is a condensed way of doing it not in the main iteration loop? Just a thought. Could end up being slower if generally only half a dozen iterations, mind.
I can't remember exactly how I wrote the code, though remember capping it at a handful of iterations if X didn't reach 0, and used the Y (in the example given) as a good estimate.