16 bits linear interpolation, anyone ?

Here you can ask questions or provide insights about how to use efficiently 6502 assembly code on the Oric.
User avatar
waskol
Flight Lieutenant
Posts: 331
Joined: Wed Jun 13, 2007 8:20 pm
Location: FRANCE, Paris

Post by waskol » Fri Sep 12, 2008 10:57 pm

Dbug wrote:
waskol wrote:Chema.... Dbug...
I think we can use dichotomy without a loss of precision....
(...)
Dbug wrote:In that case, a solution for me would be to use three bytes and do some fixed point operations like 16.8 shift and add. The additional cost is very light, and the accuracy probably a lot better.
The trick is to simulate the floating point division with the use of an extra byte for Xa,Xb,Ya,Yb,Xc and Yc. We will work with 16 bits for the integer part plus an extra 8 bits for fractional part.
(...)
For sure we will have the exact result, and no pixel shift.
Fast, straight, without any division or multiplication :D
:)

Looks like we are talking of the same thing.

24 bits based dichotomy, 16 bits integer part, 8 bits decimals.
:lol: OK

The precision is very good, no problem :wink:

User avatar
Dbug
Site Admin
Posts: 2322
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Post by Dbug » Sun Sep 14, 2008 4:23 pm

Ok, apparently it's not as simple as we said.

There's need for some additional tests, because:
- We have no guarantee that X0<X1 or Y0<Y1 at the start of the routine
- If one of the two values is equal to the value we are looking for, the routine will never exit, so there's a need for a trivial test at the beginning

I also tried in 16 bits versus 24 bits, 16 bits is definitely not accurate enough, the lack of accuracy appears when trying to animate the line (kind of jumpy).

I started by doing it as C routine, with specialized variants for top, bottom, left and right (just to make things simpler during prototyping), and it looks like that:

Code: Select all

void DichoTop()
{
	if (LargeY0==CLIP_TOP)
	{
		LargeX=LargeX0;
		LargeY=LargeY0;
		return;
	}
	if (LargeY1==CLIP_TOP)
	{
		LargeX=LargeX1;
		LargeY=LargeY1;
		return;
	}
	
	if (LargeY0<LargeY1)
	{
		x0=LargeX0;
		y0=LargeY0;
		
		x1=LargeX1;	
		y1=LargeY1;
	}
	else
	{
		x0=LargeX1;
		y0=LargeY1;
		
		x1=LargeX0;	
		y1=LargeY0;
	}
		
	while (1)
	{
		xc=(x0+x1)>>1;
		yc=(y0+y1)>>1;
		
		if (yc==CLIP_TOP)
		{
			LargeX=xc;
			LargeY=yc;
			
			return;
		}
		else
		if (yc>CLIP_TOP)
		{
			x1=xc;
			y1=yc;
		}
		else
		{
			x0=xc;
			y0=yc;
		}		
	}
}
It's already quite long in C... the 24 bits assembler version is even worse :(

I really hate doing 16 bits signed comparisons in assembler :p

User avatar
Chema
Game master
Posts: 1972
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Post by Chema » Mon Sep 15, 2008 9:21 am

waskol wrote: Sorry Chema, bu I think that your fast div routine will be beaten up as if Manchester United was playing against Porstmouth :P
Yep. And I am quite happy about that, because else many cycles will be eaten and we are already quite stressed by speed concerns. Even if the multiplication routine is quite fast, the division is not... :(

Of course any trick that avoid doing multis or divs would be fantastic. Let's see if it can be done in a compact way and not many iterations are needed.

Cheers.

Post Reply

Who is online

Users browsing this forum: No registered users and 2 guests