Vector clipping...

Enlighted (6067)

28-05-2016, 05:46

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
	ADD HL,DE
	JP M,.NOSWAPSD

        EXX
        EX DE,HL
        EXX
	EX DE,HL

.NOSWAPSD

	; HL < DE

	ADD A,D
	JP M,.IGNOREVECTOR ; BIGGER < 0

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

	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
	ADD HL,BC
	EX DE,HL
.SKIPHIGH
	ADD HL,BC
	EXX  ; Swap X/Y
	RET

.BINSEARCH

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

	XOR A
	SBC HL,DE
	EX DE,HL
	PUSH DE
	SRA D
	RR E
	ADD HL,DE
	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

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

.LOOPADD:
        EXX
        SRA D
        RR E
	CALL Z,.EARLYXSHIT
	ADD HL,DE
	EXX
	XOR A
	ADC HL,DE
.LOOPSUB:
	RET Z
        SRA D
        RR E
        CALL Z,.CHECK0
.ENTRYBIN
	LD A,H
	ADD A,A
	JP C,.LOOPADD
	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

By ARTRAG

Enlighted (6935)

28-05-2016, 09:04

How can I say awesome 100 times without seeing repetitive ?

By NYYRIKKI

Enlighted (6067)

28-05-2016, 12:56

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.

By ricbit

Champion (438)

28-05-2016, 13:31

Amazing, congrats!

By Metalion

Paragon (1625)

28-05-2016, 15:16

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

By NYYRIKKI

Enlighted (6067)

28-05-2016, 19:17

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)

By wouter_

Hero (522)

28-05-2016, 19:39

NYYRIKKI wrote:

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?

By NYYRIKKI

Enlighted (6067)

28-05-2016, 20:43

wouter_ wrote:

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:

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...

By NYYRIKKI

Enlighted (6067)

28-05-2016, 21:52

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
	ADD HL,DE
	JP M,.NOSWAPSD

        EXX
        EX DE,HL
        EXX
	EX DE,HL

.NOSWAPSD

	; HL < DE

	ADD A,D
	JP M,.IGNOREVECTOR ; bigger < 0

	SBC HL,BC
	JP P,.IGNOREVECTOR ; smaller-BC >0
	XOR A
	ADC HL,BC
        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

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

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

.BINSEARCH

	XOR A
	SBC HL,DE
	EX DE,HL
	PUSH DE
	SRA D
	RR E
	ADD HL,DE
	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

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

.LOOPADD:
        EXX
        SRA D
        RR E
	CALL Z,.EARLYXSHIT
	ADD HL,DE
	EXX
	XOR A
	ADC HL,DE
.LOOPSUB:
	RET Z
        SRA D
        RR E
.ENTRYBIN
	ADD A,H
	JP P,.LOOPADD
	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

By nitrofurano

Champion (303)

28-05-2016, 23:31

awesome!!!

By NYYRIKKI

Enlighted (6067)

29-05-2016, 00:43

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
	ADD HL,DE
	JP M,.NOSWAPSD

        EXX
        EX DE,HL
        EXX
	EX DE,HL

.NOSWAPSD

	; HL < DE

	ADD A,D
	JP M,.IGNOREVECTOR ; bigger < 0

	SBC HL,BC
	JP P,.IGNOREVECTOR ; smaller-BC >0
	XOR A
	ADC HL,BC
        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

	ADD HL,BC
	EX DE,HL
.SKIPHIGH
	ADD HL,BC
	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

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

.LOOPADD:
        EXX
        ADD HL,DE
        SRA D
        RR E
	CALL Z,.EARLYXSHIT
	EXX
	XOR A
	ADC HL,DE
.LOOPSUB:
	RET Z
        SRA D
        RR E
.ENTRYBIN
	ADD A,H
	JP P,.LOOPADD
	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