# Vector clipping...

Page 1/2
| 2

I was searching for vector clipping routine for MSX, but I was unable to find one... After some discussion with Artrag & co Wouter gave an idea that binary search would be much faster than any dividing & multiplying routine... After some thinking I found out that he was right, so here is my clipping routine based on binary search, in case someone else is looking for something like this as well...

As a proof of concept I also posted a video to display it actually works... The slowness is not caused by the clipping routine it self, but the pretty bad design of BASIC-program I use to demonstrate it.

Here is the code: (Improvement ideas are welcome)

```CLIP_VECTOR:

; VECTOR CLIP ROUTINE FOR Z80
;----------------------------
; Clip 16bit signed vector to window using binary search
; Feel free to use, but please give me credit
; Made By : NYYRIKKI (2016)
;
; EXTERNAL VARIABLES:
; DW SX = SOURCE X
; DW SY = SOURCE Y
; DW DX = DESTINATION X
; DW DY = DESTINATION Y
; DW USR= OUTPUT DRAW / NOT

LD HL,(SY)
LD DE,(DY)
EXX
LD HL,(SX)
LD DE,(DX)

LD BC,255   ;Upper limit X (lower =0)
CALL .CLIP
LD BC,211   ;Upper limit Y (lower =0)
CALL .CLIP

LD (SX),HL
LD (DX),DE
EXX
LD (SY),HL
LD (DY),DE

LD HL,#FFFF ; Vector is valid and should be drawn
LD (USR),HL
RET

.IGNOREVECTOR
POP HL
LD HL,0     ; Vector is outside visible area
LD (USR),HL
RET

.CLIP:

XOR A
SBC HL,DE
JP M,.NOSWAPSD

EXX
EX DE,HL
EXX
EX DE,HL

.NOSWAPSD

; HL < DE

JP M,.IGNOREVECTOR ; BIGGER < 0

SBC HL,BC
JP P,.IGNOREVECTOR ; smaller-BC >0
XOR A

EXX
EX DE,HL
EXX
EX DE,HL

; DE < HL
JP P,.SKIPLOW

PUSH HL
EXX
PUSH HL
CALL .BINSEARCH    ; If smaller < 0
EXX
POP DE
EXX
POP DE
.SKIPLOW
XOR A
SBC HL,BC
JP M,.SKIPHIGH
EX DE,HL
SBC HL,BC
EX DE,HL

PUSH DE
EXX
PUSH DE
CALL .BINSEARCH    ; If bigger => BC
EXX
POP DE
EXX
POP DE

EX DE,HL
EX DE,HL
.SKIPHIGH
EXX  ; Swap X/Y
RET

.BINSEARCH

;------------------------

XOR A
SBC HL,DE
EX DE,HL
PUSH DE
SRA D
RR E
POP DE    ;HL=middle point, DE=signed LEN
EXX

XOR A
SBC HL,DE
EX DE,HL
SRA D
RR E
ADD HL,DE ;HL=middle point, DE=unsigned LEN
JP .ENTRYBIN

;-------------------------

EXX
SRA D
RR E
CALL Z,.EARLYXSHIT
EXX
XOR A
.LOOPSUB:
RET Z
SRA D
RR E
CALL Z,.CHECK0
.ENTRYBIN
LD A,H
EXX
SRA D
RR E
CALL Z,.EARLYXSHIT
XOR A
SBC HL,DE
EXX
XOR A
SBC HL,DE
JP .LOOPSUB

.CHECK0
XOR D
RET NZ
INC E
RET

.EARLYXSHIT
LD A,D
OR E
RET NZ
EXX
POP HL
LD HL,0
RET
```

How can I say awesome 100 times without seeing repetitive ?

ARTRAG wrote:

How can I say awesome 100 times without seeing repetitive ?

Thank you, I value your opinions greatly. Indeed I'm quite happy, how I managed to get the values to "dance" inside Z80 in the end. I think I have not ever used so many JP M, and JP P, commands in a single routine in my life.

Also it always feels good when you realize that you can use a single command to do multiple things... Like that first ADC HL,BC that both restores HL from upper boundary check and sets P-flag for lower boundary check. That is the closest thing we can get to real multitasking on a Z80.

Amazing, congrats!

Very very nice, NYYRIKKI !
Doing that without multiplication or division is indeed a great achievement.

Metalion wrote:

Very very nice, NYYRIKKI !
Doing that without multiplication or division is indeed a great achievement.

The real beauty of this approach is that we don't have to handle digits at all... How many loops we have to execute depends of the short side of the vector. Even if the long side would be still +- dozen of pixels from the goal, we can just say "Yeah, it's close enough" and move on to next task... Sure this will cause some rounding errors, but from visual point that is not relevant. Unfortunately this optimization now works for positive lengths only, can this be a problem? I don't know yet... How ever even in worst case the loop is anyway quite a fast as the maximum numbers of loops can be calculated with PRINT log(long side length)/log(2)

NYYRIKKI wrote:

I was searching for vector clipping routine for MSX, but I was unable to find one... After some discussion with Artrag & co Wouter gave an idea that binary search would be much faster than any dividing & multiplying routine...

I'm glad my idea turned out to be useful. Actually it's not fully my idea ... over 15 years ago, right before explaining the 'traditional' line segment clipping algorithms my CG teacher mentioned that bisection was sometimes used on very old machines that lack hardware division/multiplication instructions. Your routine demonstrates it's indeed a good approach for such ancient machines ;-)

Maybe the following ideas could be useful as well?

1) Very often the to-be clipped line segment is not too far outside the visible screen (or after a few bisect-steps this will likely be the case). In that case the inner loop of the bisect routine can work with 8-bit instead of 16-bit coordinates (e.g. we know the high byte of SX is 0xFF and the high byte of DX is 0x00). Though I'm not sure it's actually beneficial to exploit this.

2) Currently the .BINSEARCH inner loop has two exit paths. One when the border is hit (let's say this is X=0), and another when the orthogonal direction doesn't change anymore (let's call this delta-y = 0). I think the latter is only possible when the line-border intersection angle is more than 45 degrees, and in this case the former exit condition is much less likely to trigger. Testing whether the intersection angle is more or less than 45 degrees is relatively easy (and has to be done only once upfront). So maybe it's faster to have two separate smaller inner loops with each only one exit condition?

wouter_ wrote:

1) Very often the to-be clipped line segment is not too far outside the visible screen (or after a few bisect-steps this will likely be the case). In that case the inner loop of the bisect routine can work with 8-bit instead of 16-bit coordinates (e.g. we know the high byte of SX is 0xFF and the high byte of DX is 0x00). Though I'm not sure it's actually beneficial to exploit this.

I'm quite sure this kind of special cases can be relatively easy to recognize and you can probably get some boost by implementing simplified versions for those, but I'll leave this kind of special case implementations for user to consider. When code size & complexity starts to go in ^2 steps while benefit gain is something like 10-15% You really need to profile your whole program to know if it is worth the extra hassle.

Quote:

2) Currently the .BINSEARCH inner loop has two exit paths. One when the border is hit (let's say this is X=0), and another when the orthogonal direction doesn't change anymore (let's call this delta-y = 0). I think the latter is only possible when the line-border intersection angle is more than 45 degrees, and in this case the former exit condition is much less likely to trigger. Testing whether the intersection angle is more or less than 45 degrees is relatively easy (and has to be done only once upfront). So maybe it's faster to have two separate smaller inner loops with each only one exit condition?

Yes, actually it has 2 exit paths, but you can't rely to delta-y exit path... This is kind of a compromise... As I have already Z-flag the .EARLYXSHIT call to make the check is relatively inexpensive. How ever it would not be enough on it's own as in this case 1/2=0, but -1/2=-1 You could naturally make sure that negative numbers are not used, but that also causes some costs...

NYYRIKKI wrote:

How ever it would not be enough on it's own as in this case 1/2=0, but -1/2=-1

Actually it is good to brainstorm with people every now and then

When I now turned the whole thing in to negative numbers, I managed to get rid of .CHECK0 routine + few EX etc. instructions from here and there:

```; VECTOR CLIP ROUTINE FOR Z80
;----------------------------
; Clip 16bit signed vector to window using binary search
; Feel free to use, but please give credits
; Made By : NYYRIKKI (2016)
;
; EXTERNAL VARIABLES:
; DW SX = SOURCE X
; DW SY = SOURCE Y
; DW DX = DESTINATION X
; DW DY = DESTINATION Y
; DW USR= OUTPUT DRAW / NOT

LD HL,(SY)
LD DE,(DY)
EXX
LD HL,(SX)
LD DE,(DX)

LD BC,255   ;Upper limit X (lower =0)
CALL .CLIP
LD BC,211   ;Upper limit Y (lower =0)
CALL .CLIP

LD (SX),HL
LD (DX),DE
EXX
LD (SY),HL
LD (DY),DE

LD HL,#FFFF ; Vector is valid and should be drawn
LD (USR),HL
RET

.IGNOREVECTOR
POP HL
LD HL,0     ; Vector is outside visible area
LD (USR),HL
RET

.CLIP:

XOR A
SBC HL,DE
JP M,.NOSWAPSD

EXX
EX DE,HL
EXX
EX DE,HL

.NOSWAPSD

; HL < DE

JP M,.IGNOREVECTOR ; bigger < 0

SBC HL,BC
JP P,.IGNOREVECTOR ; smaller-BC >0
XOR A
JP P,.SKIPLOW

PUSH DE
EXX
PUSH DE
CALL .BINSEARCH    ; If smaller < 0
EXX
POP DE
EXX
POP DE

.SKIPLOW
XOR A
EX DE,HL
SBC HL,BC
JP M,.SKIPHIGH
EX DE,HL
SBC HL,BC

PUSH HL
EXX
PUSH HL
CALL .BINSEARCH    ; If bigger => BC
EXX
POP DE
EXX
POP DE

EX DE,HL
.SKIPHIGH
EX DE,HL
EXX  ; Swap X/Y
RET

;-------------------------

.BINSEARCH

XOR A
SBC HL,DE
EX DE,HL
PUSH DE
SRA D
RR E
POP DE    ;HL=middle point, DE=signed LEN
EXX

XOR A
SBC HL,DE
EX DE,HL
SRA D
RR E
ADD HL,DE ;HL=middle point, DE=negative LEN
JP .ENTRYBIN

;-------------------------

EXX
SRA D
RR E
CALL Z,.EARLYXSHIT
EXX
XOR A
.LOOPSUB:
RET Z
SRA D
RR E
.ENTRYBIN
EXX
SRA D
RR E
CALL Z,.EARLYXSHIT
XOR A
SBC HL,DE
EXX
XOR A
SBC HL,DE
JP .LOOPSUB

.EARLYXSHIT
LD A,D
OR E
RET NZ
EXX
POP HL
LD HL,0
RET
```

awesome!!!

Ok, last 34 clocks snipped away... I think I'm done unless someone else sees something...

```CLIP_VECTOR:

; VECTOR CLIP ROUTINE FOR Z80
;----------------------------
; Clip 16bit signed vector to window using binary search
; Feel free to use, but please give credits
; Made By : NYYRIKKI (2016)
;
; EXTERNAL VARIABLES:
; DW SX = SOURCE X
; DW SY = SOURCE Y
; DW DX = DESTINATION X
; DW DY = DESTINATION Y
; DW USR= OUTPUT DRAW / NOT

LD HL,(SY)
LD DE,(DY)
LD BC,211   ;Upper limit Y (lower =0)
EXX
LD HL,(SX)
LD DE,(DX)
LD BC,255   ;Upper limit X (lower =0)

CALL .CLIPCLIP
EXX
CALL .CLIPCLIP

LD (SY),HL
LD (DY),DE
EXX
LD (SX),HL
LD (DX),DE

LD HL,#FFFF ; Vector is valid and should be drawn
LD (USR),HL
RET

.IGNOREVECTOR
POP HL
LD HL,0     ; Vector is outside visible area
LD (USR),HL
RET

.CLIPCLIP:

XOR A
SBC HL,DE
JP M,.NOSWAPSD

EXX
EX DE,HL
EXX
EX DE,HL

.NOSWAPSD

; HL < DE

JP M,.IGNOREVECTOR ; bigger < 0

SBC HL,BC
JP P,.IGNOREVECTOR ; smaller-BC >0
XOR A
JP P,.SKIPLOW

PUSH DE
EXX
PUSH DE
CALL .BINSEARCH    ; If smaller < 0
EXX
POP DE
EXX
POP DE

.SKIPLOW
XOR A
EX DE,HL
SBC HL,BC
JP M,.SKIPHIGH
EX DE,HL
SBC HL,BC

PUSH HL
EXX
PUSH HL
CALL .BINSEARCH    ; If bigger => BC
EXX
POP DE
EXX
POP DE

EX DE,HL
.SKIPHIGH
EX DE,HL
RET

;-------------------------

.BINSEARCH

XOR A
SBC HL,DE
EX DE,HL
SRA D
RR E
ADD HL,DE  ;HL=middle point, DE=signed half LEN
EXX

XOR A
SBC HL,DE
EX DE,HL
SRA D
RR E
ADD HL,DE ;HL=middle point, DE=negative half LEN
JP .ENTRYBIN

;-------------------------

EXX
SRA D
RR E
CALL Z,.EARLYXSHIT
EXX
XOR A
.LOOPSUB:
RET Z
SRA D
RR E
.ENTRYBIN
EXX
SBC HL,DE
SRA D
RR E
CALL Z,.EARLYXSHIT
EXX
XOR A
SBC HL,DE
JP .LOOPSUB

.EARLYXSHIT
LD A,D
OR E
RET NZ
EXX
POP HL
LD H,A
LD L,A
RET
```
Page 1/2
| 2