../ Back to Fractal Racer
. edit .
Interpolation

Version: 1 2 3 4 5 6

Version 1.0:

Cubic Interpolation in Rectangular Cooridantes [easy]:

Cubic Interpolation in Rectangular Cooridantes
float interpolate(float y0, float y1, float y2, float y3, float mu) {
	double a0, a1, a2, a3;
	a0 = y3 - y2 - y0 + y1;
	a1 = y0 - y1 - a0;
	a2 = y2 - y0;
	a3 = y1;
	return a0*mu*mu*mu + a1*mu*mu + a2*mu + a3;
}

Discusion: Not a bad start. Cubic interpolation connects the points in a nice, smooth curvy kind of way.

Verdict: See what it looks like in polar coordinates to form a looping track.


Version 2.0:

Cubic Interpolation in Polar Coordinates [just as easy]:


Cubic Interpolation in Polar Cooridantes

The math is the same as rectangular coordinates. Simply replace the y's with r's and mu represents a step in theta instead of x.

Discusion: Not what was expected, though looking at it as simply mapping the rectangular function to polar coordinates, causes the above results to make more sense. The expanded curves on outside turns and pinching on inside turns makes this unusable.

Verdict: Try 2D Cubic Interpolation.


Version 3.0:

2D Cubic Interpolation [slightly more difficult]:


2D Cubic Interpolation
point interpolate(point p0, point p1, point p2, point p3, float mu) {
	point p;
	float a0, a1, a2, a3;
	a0 = p3.y - p2.y - p0.y + p1.y;
	a1 = p0.y - p1.y - a0;
	a2 = p2.y - p0.y;
	a3 = p1.y;
	p.y = a0*mu*mu*mu + a1*mu*mu + a2*mu + a3;
	a0 = p3.x - p2.x - p0.x + p1.x;
	a1 = p0.x - p1.x - a0;
	a2 = p2.x - p0.x;
	a3 = p1.x;
	p.x = a0*mu*mu*mu + a1*mu*mu + a2*mu + a3;
	return p;
}

Discusion: At first pass, it appears as though we have a winner, but upon further inspection, their arrises the problem of looping. Either some kind of control will have to be built into the control point placement function to prevent this, or an intersection needs to be detectable, and upon detection, throw out the track and build another. The looping phenomena are rare, with an occurence appearing in about 1 in every 20 or so generated tracks.

Verdict: It just doesn't look good and causes too many problems. Try 2D Hermite Interpolation.


Version 4.0:

2D Hermite Interpolation [slightly more difficult still]:


2D Hermite Interpolation
point interpolate(point p0, point p1, point p2, point p3, float mu) {
	float tension = 0;
	float bias = 0;
	float m0, m1, mu2, mu3;
	float a0, a1, a2, a3;
	point p;
	m0  = (p1.x - p0.x) * (1 + bias) * (1 - tension) / 2;
	m0 += (p2.x - p1.x) * (1 - bias) * (1 - tension) / 2;
	m1  = (p2.x - p1.x) * (1 + bias) * (1 - tension) / 2;
	m1 += (p3.x - p2.x) * (1 - bias) * (1 - tension) / 2;
	mu2 = mu  * mu;
	mu3 = mu2 * mu;
	a0 =  2 *  mu3 - 3 * mu2 + 1;
	a1 =       mu3 - 2 * mu2 + mu;
	a2 =       mu3 -     mu2;
	a3 = - 2 * mu3 + 3 * mu2;
	p.x = a0*p1.x + a1*m0 + a2*m1 + a3*p2.x;
	m0  = (p1.y - p0.y) * (1 + bias) * (1 - tension) / 2;
	m0 += (p2.y - p1.y) * (1 - bias) * (1 - tension) / 2;
	m1  = (p2.y - p1.y) * (1 + bias) * (1 - tension) / 2;
	m1 += (p3.y - p2.y) * (1 - bias) * (1 - tension) / 2;
	mu2 = mu  * mu;
	mu3 = mu2 * mu;
	a0 =  2 *  mu3 - 3 * mu2 + 1;
	a1 =       mu3 - 2 * mu2 + mu;
	a2 =       mu3 -     mu2;
	a3 = - 2 * mu3 + 3 * mu2;
	p.y = a0*p1.y + a1*m0 + a2*m1 + a3*p2.y;
	return p;
}

Discusion: Looks nice.

Verdict: I think we have a winner.


Version 5.0:

Full track [far harder than it should have been]:


2D Hermite Interpolation

Discussion: First, the track path (Green dots) were generated using the method described in Version 4. Then, the inner and outer loops (Yellow and Blue dots respectively) where calculated using some simple vector math to get the vector representing the bisected angle between the vectors composed of the the previous and next points in the direction of the current point. The problem was getting the "inner" and "outer" points to stay on the inside and outside of the path points respectively. Even though the points are not placed using polar coordinates, the inner loop points still generaly tended to be closer to the origin than the outer loop points. I say generally because in testing, there were far too many "special" cases where this simply wasn't true. Luckily though, it was true enough to get 9 tracks generated that should be renderable without any flaws.

Verdict: The number of "problem cases" is directly related to the width of the track, making the track narrower would decrease the number of problems, but may make the track un-racable. That point not withstanding, this method qualifies as good enough for Version 1.0 of the game. A significant overhaul will be required before this method can be used when playing on randomly generated tracks instead of hand picked tracks.


Version 6.0:

Full track part II [a much better approach]:


... to be implemented ...

Discussion: This version replaces the use of quadrance for determining inside and outside with cross detection. If two sets of control point are on the correct side of the track, then the line segments between each pair of control points will not cross. If they are on the wrong side, then the line segments between each pair will cross, thus requiring the points to be flipped. This will produce correct side determination every time and doesn't produce any special cases.

Verdict: Pending implementation.

 
Celtrenic Designs   Caffeine Powered   © 2006 - 2017 Celtrenic Designs   PHP Powered   Get Firefox