### 16 bits linear interpolation, anyone ?

Posted:

**Wed Sep 10, 2008 8:55 pm**Hi.

This question is a bit hardcore, but if we can manage to find a solution to it, I will be able to finish my line and polygon clipping, and Chema will be able to continue is 3D game !

Basically, imagine you have two 16 bits (signed) coordinates (let's say in the -32000 to +32000 range), that represent a line or the border of a polygon.

Obviously, you need to clip that to something that fits into the screen.

There are a lot of well known algorithm, and I'm using one of these designed by Cohen & Sutherland.

The code is working fine, except that in the implementation I ran in an overflow issue when the lines are in certain positions, and this is not solvable in the current way, because the clipping involves doing some linear interpolation (X0+(Width*position)/Height), and unfortunately the result of the multiplication of two 16 bits numbers can easily require more than 16 bits.

Of course, both the multiplication and the divide could be replaced by 24 or 32 bits variants (16*16 to 32 and 32/16 to 16) but the existing 16 bits variants are already of killing the performance anyway, so it would be nice to get rid of them entirely.

This week end I will try something doing some dichotomy loop, but I wanted to ask if anyone would have an idea on how to implement efficiently (and accurately) this operation.

So, what I need, is the following.

Given X0,Y0,X1,Y1 (all 16 bits, the coordinates of both points of a line), if I give some value Xn (with Xn some value between X0 and X1) I need to get the corresponding Yn (and if given some Yn, need to find Xn).

It's the equivalent of these formula:
Example:

With
Then
With
Then
I guess everybody can agree that the formula is simple, it's just a variant of the Cross-multiplication.

Thanks for any suggestion !

This question is a bit hardcore, but if we can manage to find a solution to it, I will be able to finish my line and polygon clipping, and Chema will be able to continue is 3D game !

Basically, imagine you have two 16 bits (signed) coordinates (let's say in the -32000 to +32000 range), that represent a line or the border of a polygon.

Obviously, you need to clip that to something that fits into the screen.

There are a lot of well known algorithm, and I'm using one of these designed by Cohen & Sutherland.

The code is working fine, except that in the implementation I ran in an overflow issue when the lines are in certain positions, and this is not solvable in the current way, because the clipping involves doing some linear interpolation (X0+(Width*position)/Height), and unfortunately the result of the multiplication of two 16 bits numbers can easily require more than 16 bits.

Of course, both the multiplication and the divide could be replaced by 24 or 32 bits variants (16*16 to 32 and 32/16 to 16) but the existing 16 bits variants are already of killing the performance anyway, so it would be nice to get rid of them entirely.

This week end I will try something doing some dichotomy loop, but I wanted to ask if anyone would have an idea on how to implement efficiently (and accurately) this operation.

So, what I need, is the following.

Given X0,Y0,X1,Y1 (all 16 bits, the coordinates of both points of a line), if I give some value Xn (with Xn some value between X0 and X1) I need to get the corresponding Yn (and if given some Yn, need to find Xn).

It's the equivalent of these formula:

Code: Select all

```
Yn=Y0+((Y1-Y0)*(Xn-X0))/(X1-X0)
Xn=X0+((X1-X0)*(Yn-Y0))/(Y1-Y0)
```

With

Code: Select all

```
(X0,Y0)=(0,0)
(X1,Y1)=(200,200)
```

Code: Select all

```
If Xn=50 -> get Yn=0+(200-0)*(50-0))/(200-0)=0+(200*50)/200=50
If Xn=75 -> get Yn=0+(200-0)*(75-0))/(200-0)=0+(200*75)/200=75
```

Code: Select all

```
(X0,Y0)=(30,90)
(X1,Y1)=(15,160)
```

Code: Select all

```
If Xn=20 -> get Yn=90+(160-90)*(20-30))/(15-30)=90+(70*-10)/-15=136
If Yn=100 -> get Xn=30+(15-30)*(100-90))/(90-160)=30+(-15*10)/-70=27
```

Thanks for any suggestion !