Page 2 of 2

Posted: Fri Sep 12, 2008 10:57 pm
by waskol
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:

Posted: Sun Sep 14, 2008 4:23 pm
by Dbug
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

Posted: Mon Sep 15, 2008 9:21 am
by Chema
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.