Skip to content

Commit

Permalink
Cubic spline
Browse files Browse the repository at this point in the history
  • Loading branch information
@BSVino
BSVino committed Mar 13, 2016
1 parent 4145578 commit 7523d2e
Show file tree
Hide file tree
Showing 4 changed files with 214 additions and 27 deletions.
84 changes: 84 additions & 0 deletions game/game.cpp
View file
Original file line number Diff line number Diff line change
Expand Up @@ -44,6 +44,28 @@ LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON A

#include "seaweed.h"

#include "spline.h"

Vector g_spline_points[SPLINE_POINTS] =
{
Vector(0, 1, 0),
Vector(5, 1, 0),
Vector(10, 1, 10),
Vector(40, 1, 15),
Vector(15, 1, -10),
Vector(-50, 1, 30),
Vector(-40, 1, 19),
Vector(-20, 1, -5),
Vector(8, 1, 17),
Vector(9, 1, 16),
Vector(10, 1, 15),
Vector(11, 1, 14),
Vector(12, 1, 13),
Vector(13, 1, 12),
Vector(14, 1, 11),
Vector(15, 1, -15),
};

CGame::CGame(int argc, char** argv)
: CApplication(argc, argv)
{
Expand Down Expand Up @@ -79,6 +101,9 @@ void CGame::Load()
for (int n = 1; n < SEAWEED_LINKS; n++)
g_seaweed[k].m_positions[0][n] = g_seaweed[k].m_positions[1][n] = g_seaweed[k].m_positions[0][n - 1] + vec3(0, g_seaweed_link_length, 0);
}

memcpy(g_spline.m_points, g_spline_points, sizeof(g_spline_points));
g_spline.InitializeSpline();
}

void CGame::MakePuff(const Point& p)
Expand Down Expand Up @@ -315,6 +340,7 @@ void CGame::Update(float dt)
// Update position and vecMovement. http://www.youtube.com/watch?v=c4b9lCfSDQM
m_hPlayer->SetTranslation(m_hPlayer->GetGlobalOrigin() + m_hPlayer->m_vecVelocity * dt);
m_hPlayer->m_vecVelocity = m_hPlayer->m_vecVelocity + m_hPlayer->m_vecGravity * dt;
//m_hPlayer->SetTranslation(g_spline.SplineAtTime(fmod(Application()->GetTime()/2, SPLINE_POINTS-1)));

// Make sure the player doesn't fall through the floor. The y dimension is up/down, and the floor is at 0.
Vector vecTranslation = m_hPlayer->GetGlobalOrigin();
Expand Down Expand Up @@ -583,6 +609,62 @@ void CGame::Draw()

RenderSeaweed();

{
CRenderingContext c(Game()->GetRenderer(), true);

Vector camera = Game()->m_hPlayer->GetGlobalView();

c.UseProgram("model");

c.SetUniform("vecColor", Vector4D(0, 0, 0, 1));

for (int k = 0; k < SPLINE_POINTS; k++)
{
float offset = (float)((2 * k) % 5) * (float)M_TAU / 5;

Matrix4x4 m;
m.SetTranslation(g_spline_points[k]);
c.LoadTransform(m);
c.RenderBox(Vector(-0.1, -0.1, -0.1), Vector(0.1, 0.1, 0.1));
}

c.ResetTransformations();

c.BeginRenderLines();

float segments_per_spline = 60.0f;
for (int k = 0; k < (SPLINE_POINTS - 1) * segments_per_spline - 1; k++)
{
float t0 = (float)k/segments_per_spline;
float t1 = (float)(k+1)/segments_per_spline;

Vector p0 = g_spline.SplineAtTime(t0);
Vector p1 = g_spline.SplineAtTime(t1);

c.Vertex(p0);
c.Vertex(p1);
}

c.EndRender();

Matrix4x4 m;
m.SetTranslation(g_spline.SplineAtTime(fmod(Application()->GetTime()/2, SPLINE_POINTS-1)));
c.LoadTransform(m);
c.RenderBox(Vector(-0.1, -0.1, -0.1), Vector(0.1, 0.1, 0.1));

m.SetTranslation(g_spline.SplineAtTime(fmod((Application()->GetTime()+0.1f)/2, SPLINE_POINTS-1)));
c.LoadTransform(m);
c.RenderBox(Vector(-0.1, -0.1, -0.1), Vector(0.1, 0.1, 0.1));

m.SetTranslation(g_spline.SplineAtTime(fmod((Application()->GetTime()+0.2f)/2, SPLINE_POINTS-1)));
c.LoadTransform(m);
c.RenderBox(Vector(-0.1, -0.1, -0.1), Vector(0.1, 0.1, 0.1));

m.SetTranslation(g_spline.SplineAtTime(fmod((Application()->GetTime()+0.3f)/2, SPLINE_POINTS-1)));
c.LoadTransform(m);
c.RenderBox(Vector(-0.1, -0.1, -0.1), Vector(0.1, 0.1, 0.1));
}

pRenderer->FinishRendering(&r);

// Call this last. Your rendered stuff won't appear on the screen until you call this.
Expand Down Expand Up @@ -751,6 +833,7 @@ void CGame::GameLoop()
Vector vecMonsterMin = Vector(-1, 0, -1);
Vector vecMonsterMax = Vector(1, 2, 1);

/*
CCharacter* pTarget1 = CreateCharacter();
pTarget1->SetTransform(Vector(2, 2, 2), 0, Vector(0, 1, 0), Vector(6, 0, 6));
pTarget1->m_aabbSize.vecMin = vecMonsterMin;
Expand All @@ -774,6 +857,7 @@ void CGame::GameLoop()
pTarget3->m_iBillboardTexture = m_iMonsterTexture;
pTarget3->m_bEnemyAI = true;
pTarget3->m_bTakesDamage = true;
*/

Vector vecPropMin = Vector(-.1f, 0, -.1f);
Vector vecPropMax = Vector(.1f, .2f, .1f);
Expand Down
26 changes: 0 additions & 26 deletions game/main.cpp
View file
Original file line number Diff line number Diff line change
Expand Up @@ -44,32 +44,6 @@ using std::vector;

int main(int argc, char* argv[])
{
for (int k = -6; k <= 14; k++)
{
float number = pow(2, k);
printf("invsqrt(%f) = %f\n", number, 1/sqrt(number));

int32_t* l = (int32_t*)&number;
int32_t exponent = (*l)>>23;
printf("my estimate: 2^%d*s -> 2^%d*s\n", exponent-127, 62 - exponent/2);

int32_t int_estimate = 0x5F000000 - ((*l)>>1);
float my_estimate = *(float*)&int_estimate;

int_estimate = 0x5f3759df - ((*l)>>1);
float orig_estimate = *(float*)&int_estimate;

printf("my: %f orig: %f\n", my_estimate, orig_estimate);

my_estimate = 1.5f*my_estimate - 0.5f*my_estimate*my_estimate*my_estimate*number;
orig_estimate = 1.5f*orig_estimate - 0.5f*orig_estimate*orig_estimate*orig_estimate*number;
printf("my: %f orig: %f\n\n", my_estimate, orig_estimate);
}




return 0;
mtsrand(0);

// Create a game
Expand Down
3 changes: 2 additions & 1 deletion game/seaweed.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -80,7 +80,8 @@ struct Seaweed
vec3 m_positions[2][SEAWEED_LINKS];
};

#define NUM_SEAWEEDS 29
//#define NUM_SEAWEEDS 29
#define NUM_SEAWEEDS 0
Seaweed g_seaweed[NUM_SEAWEEDS];
float g_seaweed_link_length = 3.5f;
float g_mass_per_link = 1.0f;
Expand Down
128 changes: 128 additions & 0 deletions math/spline.h
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,128 @@
#pragma once

#define SPLINE_POINTS 16

struct CubicSpline
{
vec3 m_points[SPLINE_POINTS];
vec3 m_coeffs[SPLINE_POINTS-1][4];
float m_lengths[SPLINE_POINTS - 1];

// Spline construction, Burden & Faires - Numerical Analysis 9th, algorithm 3.4
void InitializeSpline()
{
int n = SPLINE_POINTS - 1;

vec3 a[SPLINE_POINTS];
for (int i = 1; i <= n - 1; i++)
a[i] = 3 * ((m_points[i + 1] - 2*m_points[i] + m_points[i - 1]));

float l[SPLINE_POINTS];
float mu[SPLINE_POINTS];
vec3 z[SPLINE_POINTS];

l[0] = l[n] = 1;
mu[0] = 0;
z[0] = z[n] = vec3();
m_coeffs[n][2] = vec3();

for (int i = 1; i <= n - 1; i++)
{
l[i] = 4 - mu[i-1];
mu[i] = 1 / l[i];
z[i] = (a[i] - z[i-1]) / l[i];
}

for (int i = 0; i < SPLINE_POINTS; i++)
m_coeffs[i][0] = m_points[i];

for (int j = n - 1; j >= 0; j--)
{
m_coeffs[j][2] = z[j] - mu[j] * m_coeffs[j + 1][2];
m_coeffs[j][3] = (1.0f / 3.0f)*(m_coeffs[j + 1][2] - m_coeffs[j][2]);
m_coeffs[j][1] = m_points[j + 1] - m_points[j] - m_coeffs[j][2] - m_coeffs[j][3];
}

for (int k = 0; k < SPLINE_POINTS - 1; k++)
m_lengths[k] = Integrate(k, 1);
}

vec3 SplineAtTime(float t)
{
if (t > SPLINE_POINTS)
t = SPLINE_POINTS;

if (t == SPLINE_POINTS)
t = SPLINE_POINTS - 0.0000f;

int spline = (int)t;
float fractional = t - spline;

spline = spline % (SPLINE_POINTS-1);

float x = fractional;
float xx = x*x;
float xxx = x*xx;

vec3 result = m_coeffs[spline][0] + m_coeffs[spline][1]*x + m_coeffs[spline][2]*xx + m_coeffs[spline][3]*xxx;
return result;
}

float ArcLengthIntegrand(int spline, float t)
{
float tt = t*t;

vec3 dv = m_coeffs[spline][1] + 2 * m_coeffs[spline][2] * t + 3 * m_coeffs[spline][3] * tt;
float xx = dv.x*dv.x;
float yy = dv.y*dv.y;
float zz = dv.z*dv.z;

return sqrt(xx + yy + zz);
}

// Composite Simpson's Rule, Burden & Faires - Numerical Analysis 9th, algorithm 4.1
float Integrate(int spline, float t)
{
int n = 16;
float h = t / n;
float XI0 = ArcLengthIntegrand(spline, t);
float XI1 = 0;
float XI2 = 0;

for (int i = 0; i < n; i++)
{
float X = i*h;
if (i % 2 == 0)
XI2 += ArcLengthIntegrand(spline, X);
else
XI1 += ArcLengthIntegrand(spline, X);
}

float XI = h * (XI0 + 2 * XI2 + 4 * XI1) * (1.0f / 3);
return XI;
}

vec3 ConstVelocitySplineAtTime(float t)
{
int spline = 0;
while (t > m_lengths[spline])
{
t -= m_lengths[spline];
spline += 1;
}

float s = t / m_lengths[spline]; // Here's our initial guess.

// Do some Newton-Rhapsons.
s = s - (Integrate(spline, s) - t) / ArcLengthIntegrand(spline, s);
s = s - (Integrate(spline, s) - t) / ArcLengthIntegrand(spline, s);
s = s - (Integrate(spline, s) - t) / ArcLengthIntegrand(spline, s);
s = s - (Integrate(spline, s) - t) / ArcLengthIntegrand(spline, s);
s = s - (Integrate(spline, s) - t) / ArcLengthIntegrand(spline, s);
s = s - (Integrate(spline, s) - t) / ArcLengthIntegrand(spline, s);

return SplineAtTime(spline + s);
}
};

CubicSpline g_spline;

0 comments on commit 7523d2e

Please sign in to comment.