User:Hirogen2/VectorAngle StaticLookup

Before I noticed there was the VectorAngle function, I actually implemented it myself. Posted here for historic purposes, and perhaps to spark ideas for how to add complex functions with ACS alone. ACS being Turing-complete is an important factor :-)  —j.eng 21:47, 26 May 2009 (UTC)

VectorAngle, at its core, calculats atan(dy/dx), with a bit of extra logic to handle cases like dx=0. Since ACS does not offer an atan function, nor is it feasible to use any of the fancy math (imaginary numbers! integrals! infinite series! continued fractions! all expensive computations! see Wikipedia for details...). The simplest way is to use a static coarse-granularity lookup table. I chose a resolution somewhere near 1° (the “fixed” datatype has a resolution of 1/256 °). This is acceptable, as is the cost of space involved with this. Due to the periodicity of trigonometric functions, a reduced number of values need only be stored (e.g. 90 instead of 360).

atan implementation

int tan_table[90] = {
	/*   0° */ 0.0000,
	/*   1° */ 0.0174,
	/*   2° */ 0.0349,
	/*   3° */ 0.0524,
	/*   4° */ 0.0699,
	/*   5° */ 0.0874,
	/*   6° */ 0.1051,
	/*   7° */ 0.1227,
	/*   8° */ 0.1405,
	/*   9° */ 0.1583,
	/*  10° */ 0.1763,
	/*  11° */ 0.1943,
	/*  12° */ 0.2125,
	/*  13° */ 0.2308,
	/*  14° */ 0.2493,
	/*  15° */ 0.2679,
	/*  16° */ 0.2867,
	/*  17° */ 0.3057,
	/*  18° */ 0.3249,
	/*  19° */ 0.3443,
	/*  20° */ 0.3639,
	/*  21° */ 0.3838,
	/*  22° */ 0.4040,
	/*  23° */ 0.4244,
	/*  24° */ 0.4452,
	/*  25° */ 0.4663,
	/*  26° */ 0.4877,
	/*  27° */ 0.5095,
	/*  28° */ 0.5317,
	/*  29° */ 0.5543,
	/*  30° */ 0.5773,
	/*  31° */ 0.6008,
	/*  32° */ 0.6248,
	/*  33° */ 0.6494,
	/*  34° */ 0.6745,
	/*  35° */ 0.7002,
	/*  36° */ 0.7265,
	/*  37° */ 0.7535,
	/*  38° */ 0.7812,
	/*  39° */ 0.8097,
	/*  40° */ 0.8391,
	/*  41° */ 0.8692,
	/*  42° */ 0.9004,
	/*  43° */ 0.9325,
	/*  44° */ 0.9656,
	/*  45° */ 1.0000,
	/*  46° */ 1.0355,
	/*  47° */ 1.0723,
	/*  48° */ 1.1106,
	/*  49° */ 1.1503,
	/*  50° */ 1.1917,
	/*  51° */ 1.2348,
	/*  52° */ 1.2799,
	/*  53° */ 1.3270,
	/*  54° */ 1.3763,
	/*  55° */ 1.4281,
	/*  56° */ 1.4825,
	/*  57° */ 1.5398,
	/*  58° */ 1.6003,
	/*  59° */ 1.6642,
	/*  60° */ 1.7320,
	/*  61° */ 1.8040,
	/*  62° */ 1.8807,
	/*  63° */ 1.9626,
	/*  64° */ 2.0503,
	/*  65° */ 2.1445,
	/*  66° */ 2.2460,
	/*  67° */ 2.3558,
	/*  68° */ 2.4750,
	/*  69° */ 2.6050,
	/*  70° */ 2.7474,
	/*  71° */ 2.9042,
	/*  72° */ 3.0776,
	/*  73° */ 3.2708,
	/*  74° */ 3.4874,
	/*  75° */ 3.7320,
	/*  76° */ 4.0107,
	/*  77° */ 4.3314,
	/*  78° */ 4.7046,
	/*  79° */ 5.1445,
	/*  80° */ 5.6712,
	/*  81° */ 6.3137,
	/*  82° */ 7.1153,
	/*  83° */ 8.1443,
	/*  84° */ 9.5143,
	/*  85° */ 11.4300,
	/*  86° */ 14.3006,
	/*  87° */ 19.0811,
	/*  88° */ 28.6362,
	/*  89° */ 57.2899,
};

function int abs(int x)
{
	if (x < 0)
		return -x;
	return x;
}

function int atan_lookup(/*fixed*/ int value)
{
	int low = 0, mid, high = 90, cand = -1;

	while (low < high) {
		mid = low + ((high - low) / 2);
		if (cand == -1 ||
		    abs(tan_table[mid] - value) < abs(tan_table[cand] - value))
			cand = mid;

		if (tan_table[mid] < value)
			low = mid + 1;
		else
			high = mid;
	}
	return cand;
}

A binary search is used for faster lookup than a linear search. Lookup is already expensive enough because ACS is interpreted.

VectorAngle implementation

It got called “pointangle” because the C function in the Doom source is called “R_PointAngle2”.

function /*fixed*/ int pointangle(/*fixed*/ int dx, /*fixed*/ int dy)
{
	/*fixed*/ int y;
	int deg;

	if (dx == 0) {
		if (dy >= 0)
			return 0.25;
		else
			return 0.75;
	}

	y = FixedDiv(dy, dx);
	if (dy > 0) {
		if (dx > 0)
			/* quadrant 1 (0-90°) */
			deg = atan_lookup(y);
		else
			/* quadrant 2 (90-180°) */
			deg = 180 - atan_lookup(-y);
	} else {
		if (dx < 0)
			/* quadrant 3 (180-270°) */
			deg = 180 + atan_lookup(y);
		else
			/* quadrant 4 (270-360°) */
			deg = 360 - atan_lookup(-y);
	}

	return (deg << 16) / 360;
}