#include "ref.h"

#include "dk_gce_spline.h"
#include "dk_misc.h"

CCubicSpline::CCubicSpline() {
    a = b = c = d = 0.0f;
}

void CCubicSpline::Init(float p0, float d0, float p1, float d1, float t) {
    d = p0;
    c = d0;

    float u, v, w, x, y, z;
    u = 3 * t * t;
    v = 2 * t;
    w = d1 - c;

    x = t * t * t;
    y = t * t;
    z = p1 - c * t - d;

    y *= u / x;
    z *= u / x;

    y -= v;
    z -= w;

    b = z / y;
    a = (w - v * b) / u;
}

void CCubicSpline::Init(CCubicSpline &other) {
    a = other.a;
    b = other.b;
    c = other.c;
    d = other.d;
}

float CCubicSpline::Value(float time) {
    return time * (time * (a * time + b) + c) + d;
}

float CCubicSpline::Dir(float time) {
    return time * (3 * a * time + 2 * b) + c;
}

CPointSpline::CPointSpline() {

}

void CPointSpline::Init(point &p0, point &d0, point &p1, point &d1, float time) {
    x.Init(p0.x, d0.x, p1.x, d1.x, time);
    y.Init(p0.y, d0.y, p1.y, d1.y, time);
    z.Init(p0.z, d0.z, p1.z, d1.z, time);
}

void CPointSpline::Init(CPointSpline *other) {
    x.Init(other->x);
    y.Init(other->y);
    z.Init(other->z);
}

void CPointSpline::Pos(float time, point &pos) {
    pos.eq(x.Value(time), y.Value(time), z.Value(time));
}

void CPointSpline::Dir(float time, point &dir) {
    dir.eq(x.Dir(time), y.Dir(time), z.Dir(time));

    //normalize it.
    dir.normalize();
}

float CPointSpline::Len(float end_time) {
    //get the beginning of spline.
    point start;
    Pos(0.0f, start);

    //the length of the spline.
    float len = 0.0f;

    //break the spline up into small chunks.
    for (float time = 0.05f; time < end_time + 0.001; time += 0.05f) {
        //get the end of this small segment.
        point end;
        Pos(time, end);

        point line;
        line.sub(end, start);

        len += line.length();

        //move end to start.
        start = end;
    }

    return len;
}

CSplineSequence::CSplineSequence() {
    position_only = false;

    num_points = 0;

    points = NULL;
    velocity_norm = NULL;
    velocity = NULL;

    directions = NULL;
    dir_vel_norm = NULL;
    dir_vel = NULL;

    times = NULL;

    total_time = 0.0f;

    cache_segment = 0;
    cache_time = 0.0f;

    pos_splines = NULL;
    dir_splines = NULL;

    velocity_start = velocity_end = EV_ZERO;
}

CSplineSequence::~CSplineSequence() {
    Reset();
}

void CSplineSequence::Reset() {
    //delete our splines.
    for (int i = 0; i < num_points - 1; i++) {
        delc(pos_splines[i]);

        if (dir_splines != NULL) {
            delc(dir_splines[i]);
        }
    }

    delca(points);
    delca(velocity_norm);
    delca(velocity);

    delca(directions);
    delca(dir_vel_norm);
    delca(dir_vel);

    delca(times);

    delca(pos_splines);
    delca(dir_splines);

    num_points = 0;
    total_time = 0.0f;

    cache_segment = 0;
    cache_time = 0.0f;

    velocity_start = velocity_end = EV_ZERO;

    position_only = false;
}

void CSplineSequence::operator=(const CSplineSequence &other) {
    //reset ourself first.
    Reset();

    //copy over each member.
    position_only = other.position_only;
    num_points = other.num_points;
    total_time = other.total_time;
    velocity_start = other.velocity_start;
    velocity_end = other.velocity_end;

    if (num_points > 0) {
        points = new point[num_points];
        velocity_norm = new point[num_points];
        velocity = new float[num_points];

        directions = new point[num_points];
        dir_vel_norm = new point[num_points];
        dir_vel = new float[num_points];

        for (int i = 0; i < num_points; i++) {
            points[i] = other.points[i];
            velocity_norm[i] = other.velocity_norm[i];
            velocity[i] = other.velocity[i];

            directions[i] = other.directions[i];
            dir_vel_norm[i] = other.dir_vel_norm[i];
            dir_vel[i] = other.dir_vel[i];
        }
    }

    if (num_points > 1) {
        times = new float[num_points - 1];

        pos_splines = new CPointSpline *[num_points - 1];
        dir_splines = new CPointSpline *[num_points - 1];

        for (int i = 0; i < num_points - 1; i++) {
            times[i] = other.times[i];

            pos_splines[i] = new CPointSpline();
            dir_splines[i] = new CPointSpline();

            pos_splines[i]->Init(other.pos_splines[i]);
            dir_splines[i]->Init(other.dir_splines[i]);
        }
    }
}

void CSplineSequence::Init(const point &start, const point &dir) {
    position_only = false;
    num_points = 1;
    total_time = 0.0f;
    cache_segment = 0;
    cache_time = 0.0f;

    //allocate arrays.
    points = new point[1];
    velocity_norm = new point[1];
    velocity = new float[1];

    directions = new point[1];
    dir_vel_norm = new point[1];
    dir_vel = new float[1];

    //set the values for the first point.
    points[0] = start;
    velocity_norm[0].zero();
    velocity[0] = 0.0f;

    directions[0] = dir;
    dir_vel_norm[0].zero();
    dir_vel[0] = 0.0f;
}

//adds a point to the sequence.  time is the time it takes to get from the previous point to this point.
void CSplineSequence::Add(const point &loc, const point &dir, float time) {
    if (position_only == true) return;

    if (num_points < 1) {
        Init(loc, dir);
        return;   
    }

    //get new arrays.
    point *newpoints = new point[num_points + 1];
    point *newvelocity_norm = new point[num_points + 1];
    float *newvelocity = new float[num_points + 1];

    point *newdirections = new point[num_points + 1];
    point *newdir_vel_norm = new point[num_points + 1];
    float *newdir_vel = new float[num_points + 1];

    float *newtimes = new float[num_points];

    CPointSpline **newpos = new CPointSpline *[num_points];
    CPointSpline **newdir = new CPointSpline *[num_points];

    //copy the existing data over.
    for (int i = 0; i < num_points; i++) {
        newpoints[i] = points[i];
        newvelocity_norm[i] = velocity_norm[i];
        newvelocity[i] = velocity[i];

        newdirections[i] = directions[i];
        newdir_vel_norm[i] = dir_vel_norm[i];
        newdir_vel[i] = dir_vel[i];
    }

    for (i = 0; i < num_points - 1; i++) {
        newtimes[i] = times[i];

        newpos[i] = pos_splines[i];
        newdir[i] = dir_splines[i];
    }

    //delete the old arrays.
    delca(points);
    delca(velocity_norm);
    delca(velocity);

    delca(directions);
    delca(dir_vel_norm);
    delca(dir_vel);

    delca(times);
    delca(pos_splines);
    delca(dir_splines);

    //swap in the new arrays.
    points = newpoints;
    velocity_norm = newvelocity_norm;
    velocity = newvelocity;

    directions = newdirections;
    dir_vel_norm = newdir_vel_norm;
    dir_vel = newdir_vel;

    times = newtimes;

    pos_splines = newpos;
    dir_splines = newdir;

    //add in the new point and direction.
    points[num_points] = loc;
    directions[num_points] = dir;

    //add in the new time.
    times[num_points - 1] = time;

    //initialize our pointers to the new splines.
    pos_splines[num_points - 1] = new CPointSpline();
    dir_splines[num_points - 1] = new CPointSpline();

    //increase num_points
    num_points++;

    //compute the splines for the position and direction sequence.
    ComputeSplines(points, velocity_norm, velocity, pos_splines, false);
    ComputeSplines(directions, dir_vel_norm, dir_vel, dir_splines, true);

    ComputeTime();
}

float MixVelocity(float oldv, float newv);

void CSplineSequence::ComputeSplines(point *pts, point *vel_norms, float *vel, CPointSpline **splines, bool wrap) {
    //check how many points we have in our sequence.
    if (num_points < 2) {
        //no segments, no work
        return;
    }

    point line;
    point wrapped_end, wrapped_end2;
    point vel_start, vel_end;

    if (num_points == 2) {
        //check if we should wrap.
        (wrap == true) ? ComputeEndAngleWrap(pts[0], pts[1], wrapped_end) : wrapped_end = pts[1];

        //compute the position spline velocities.
        line.sub(wrapped_end, pts[0]);
        vel[0] = vel[1] = line.normalize() / times[0];

        vel_norms[0] = line;
        vel_norms[1] = line;

        //make the position velocity vectors and position spline.
        vel_start.eq(vel_norms[0], (velocity_start == EV_ZERO) ? 0.0f : vel[0]);
        vel_end.eq(vel_norms[1], (velocity_end == EV_ZERO) ? 0.0f : vel[1]);
        splines[0]->Init(pts[0], vel_start, wrapped_end, vel_end, times[0]);

        return;
    }

    if (num_points == 3) {
        //we need to make both segments.
        //get the direction for the middle point.
        SplineDirection(pts[0], pts[1], pts[2], vel_norms[1], wrap);

        //get the begin and end direction.
        SplineStartDir(pts[0], pts[1], vel_norms[1], vel_norms[0], wrap);
        SplineEndDir(pts[1], pts[2], vel_norms[1], vel_norms[2], wrap);

        //check if we need to wrap
        (wrap == true) ? ComputeEndAngleWrap(pts[0], pts[1], wrapped_end) : wrapped_end = pts[1];
        (wrap == true) ? ComputeEndAngleWrap(pts[1], pts[2], wrapped_end2) : wrapped_end2 = pts[2];

        //get the velocities for the points.
        line.sub(wrapped_end, pts[0]);
        float len = line.length();
        vel[0] = len / times[0];

        line.sub(wrapped_end2, pts[1]);
        len = line.length();
        vel[2] = len / times[1];

        vel[1] = MixVelocity(vel[1], vel[2]);

        //init the splines.
        vel_start.eq(vel_norms[0], (velocity_start == EV_ZERO) ? 0.0f : vel[0]);
        vel_end.eq(vel_norms[1], vel[1]);
        splines[0]->Init(pts[0], vel_start, wrapped_end, vel_end, times[0]);

        vel_start = vel_end;
        vel_end.eq(vel_norms[2], (velocity_end == EV_ZERO) ? 0.0f : vel[2]);
        splines[1]->Init(pts[1], vel_start, wrapped_end2, vel_end, times[1]);
        return;
    }

    //we need an array to store the wrapped end points for each of the segments.
    point *wrapped_ends = new point[num_points - 1];
    //another array to store the separations between the points.
    float *segment_len = new float[num_points - 1];

    //get all of the wrapped ends.
    for (int i = 0; i < num_points - 1; i++) {
        (wrap == true) ? ComputeEndAngleWrap(pts[i], pts[i + 1], wrapped_ends[i]) : wrapped_ends[i] = pts[i + 1];
    }

    //get all the lengths of the segments.
    for (i = 0; i < num_points - 1; i++) {
        line.sub(wrapped_ends[i], pts[i]);
        segment_len[i] = line.length();
    }

    //compute the velocity norms for all of the middle points.
    for (i = 1; i < num_points - 1; i++) {
        SplineDirection(pts[i - 1], pts[i], pts[i + 1], vel_norms[i], wrap);
    }

    //compute the start and the end velocity norms
    SplineStartDir(pts[0], pts[1], vel_norms[1], vel_norms[0], wrap);
    SplineEndDir(pts[num_points - 2], pts[num_points - 1], vel_norms[num_points - 2], vel_norms[num_points - 1], wrap);

    //compute the velocity at the first point and second point.
    vel[0] = vel[1] = segment_len[0] / times[0];

    //compute the velocities at the remaining points.
    for (i = 1; i < num_points - 1; i++) {
        //get the velocity at the end of this segment.
        vel[i + 1] = segment_len[i] / times[i];

        //mix this velocity with the velocity already at the beginning of this segment.
        vel[i] = MixVelocity(vel[i], vel[i + 1]);
    }

    //compute the first spline.
    vel_start.eq(vel_norms[0], (velocity_start == EV_ZERO) ? 0.0f : vel[0]);
    vel_end.eq(vel_norms[1], vel[1]);
    splines[0]->Init(pts[0], vel_start, wrapped_ends[0], vel_end, times[0]);

    //do the splines between the first and the last.
    for (i = 1; i < num_points - 2; i++) {
        //get the start and end initial velocity
        vel_start.eq(vel_norms[i], vel[i]);
        vel_end.eq(vel_norms[i + 1], vel[i + 1]);
        splines[i]->Init(pts[i], vel_start, wrapped_ends[i], vel_end, times[i]);
    }

    //compute the last spline.
    vel_start.eq(vel_norms[num_points - 2], vel[num_points - 2]);
    vel_end.eq(vel_norms[num_points - 1], (velocity_end == EV_ZERO) ? 0.0f : vel[num_points - 1]);
    splines[num_points - 2]->Init(pts[num_points - 2], vel_start, wrapped_ends[num_points - 2], vel_end, times[num_points - 2]);

    //delete our temporary arrays.
    delca(wrapped_ends);
    delca(segment_len);
}

//gets the velocity at the given point.
float CSplineSequence::Velocity(int pnt) const {
    if (pnt < 0 || pnt >= num_points) return 0.0f;

    return velocity[pnt];
}

void CSplineSequence::Velocity(int pnt, point &vel) const {
    if (pnt < 0 || pnt >= num_points) return;

    vel.eq(velocity_norm[pnt], velocity[pnt]);
}

//sets the velocity at the given point.
void CSplineSequence::Time(int index, float time) {
    //check to make sure this is a valid index.
    if (index < 0 || index >= num_points - 1) return;
    //make sure we have a valid time value.
    if (time < 0.01) return;

    //change the time.
    times[index] = time;

    //recompute the splines.... i'm lazy and dont want to just update the ones that are
    //really affected, so redo them all.
    ComputeSplines(points, velocity_norm, velocity, pos_splines, false);
    if (position_only == false) {
        ComputeSplines(directions, dir_vel_norm, dir_vel, dir_splines, true);
    }

    ComputeTime();
}

//sets the angles at the given point.
void CSplineSequence::Angle(int index, const point &angle) {
    if (index < 0 || index >= num_points) return;

    //change the value.
    directions[index] = angle;

    //recompute the splines.... i'm lazy and dont want to just update the ones that are
    //really affected, so redo them all.
    ComputeSplines(points, velocity_norm, velocity, pos_splines, false);
    if (position_only == false) {
        ComputeSplines(directions, dir_vel_norm, dir_vel, dir_splines, true);
    }
}

//sets the position of the given point.
void CSplineSequence::Pos(int index, const point &pos) {
    if (index < 0 || index >= num_points) return;

    //change the value.
    points[index] = pos;

    //recompute the splines.... i'm lazy and dont want to just update the ones that are
    //really affected, so redo them all.
    ComputeSplines(points, velocity_norm, velocity, pos_splines, false);
    if (position_only == false) {
        ComputeSplines(directions, dir_vel_norm, dir_vel, dir_splines, true);
    }
}

int CSplineSequence::NumPoints() const {
    return num_points;
}

void CSplineSequence::ComputeTime() {
    total_time = 0.0f;

    for (int i = 0; i < num_points - 1; i++) {
        total_time += times[i];
    }

    //reset our sequence number computation cache.
    cache_segment = 0;
    cache_time = 0.0f;
}

int CSplineSequence::Segment(float &time) {
    //the index and time we start searching at.
    int index = 0;
    float segment_time = 0.0f;

    //check if the time is after our cached time.
    if (cache_time <= time) {
        index = cache_segment;
        segment_time = cache_time;
    }

    //loop through the remainder of the segments.
    for (; index < num_points - 1; index++) {
        //check if the time is before the next.
        if (segment_time + times[index] >= time) {
            //this is the index we will return.  cache the time and index value.
            cache_segment = index;
            cache_time = segment_time;

            time -= segment_time;
            return index;
        }

        //add the segment time to our total time.
        segment_time += times[index];
    }

    //bad, the time is past all the segments, return the last segment.
    time -= segment_time;
    return num_points - 2;
}

float CSplineSequence::TotalTime() const {
    return total_time;
}

float CSplineSequence::Time(int segment) const {
    if (segment < 0 || segment >= num_points - 1) return 0.0f;

    return times[segment];
}

void CSplineSequence::Pos(float time, point &pos) {
    if (num_points < 1) return;
    if (num_points == 1) {
        //return the point we have.
        pos = points[0];
        return;
    }

    //get the segment that this time is on.
    int segment = Segment(time);

    //check to make sure the time isnt more than the spline has.
    bound_max(time, times[segment]);
    bound_min(time, 0.0f);

    //get the position from the segment.
    pos_splines[segment]->Pos(time, pos);
}

void CSplineSequence::Vel(float time, point &vel) {
    if (num_points < 1) return;
    if (num_points == 1) {
        //return the direction we have.
        vel = directions[0];
        return;
    }

    int segment = Segment(time);

    //check to make sure the time isnt more than the spline has.
    bound_max(time, times[segment]);
    bound_min(time, 0.0f);

    //get the vel from the segment.
    pos_splines[segment]->Dir(time, vel);
}

void CSplineSequence::Dir(float time, point &dir) {
    if (position_only == true) return;
    if (num_points < 1) return;
    if (num_points == 1) {
        //return the dir we have.
        dir = directions[0];
        return;
    }

    //get the segment that this time is on.
    int segment = Segment(time);

    //check to make sure the time isnt more than the spline has.
    bound_max(time, times[segment]);
    bound_min(time, 0.0f);

    //get the direction from the segment.
    dir_splines[segment]->Pos(time, dir);
}

static point bad_index;

point &CSplineSequence::Point(int index) const {
    if (index < 0 || index >= num_points) return bad_index;
    return points[index];
}

point &CSplineSequence::Angle(int index) const {
    if (index < 0 || index >= num_points) return bad_index;
    if (position_only == true) return bad_index;
    return directions[index];
}

end_vel CSplineSequence::VelStart() const {
    return velocity_start;
}

end_vel CSplineSequence::VelEnd() const {
    return velocity_end;
}

void CSplineSequence::VelStart(end_vel vel) {
    velocity_start = vel;

    //recompute the splines.... i'm lazy and dont want to just update the ones that are
    //really affected, so redo them all.
    ComputeSplines(points, velocity_norm, velocity, pos_splines, false);
    ComputeSplines(directions, dir_vel_norm, dir_vel, dir_splines, true);
}

void CSplineSequence::VelEnd(end_vel vel) {
    velocity_end = vel;

    //recompute the splines.... i'm lazy and dont want to just update the ones that are
    //really affected, so redo them all.
    ComputeSplines(points, velocity_norm, velocity, pos_splines, false);
    ComputeSplines(directions, dir_vel_norm, dir_vel, dir_splines, true);
}

//returns the smooth direction a spline should take when passing through loc from before, towards after.
void SplineDirection(point &before, point &loc, point &after, point &dir, bool wrap) {
    point wrapped;

    //get the direction from loc to after.
    //check if we have to wrap after.
    (wrap == true) ? ComputeEndAngleWrap(loc, after, wrapped) : wrapped = after;
    point out;
    out.sub(wrapped, loc);
    out.normalize();

    //get the direction from before to loc.
    //check if we have to wrap loc.
    (wrap == true) ? ComputeEndAngleWrap(before, loc, wrapped) : wrapped = loc;
    point in;
    in.sub(wrapped, before);
    in.normalize();

    //get the average.
    dir.add(out, in);
    dir.normalize();
}

void SplineStartDir(point &loc, point &after, point &after_dir, point &dir, bool wrap) {
    point wrapped;

    //get the direction from loc to after.
    //check if we need to wrap after.
    (wrap == true) ? ComputeEndAngleWrap(loc, after, wrapped) : wrapped = after;
    point out;
    out.sub(wrapped, loc);
    out.normalize();

    //get the reflection of after direction across out.
    PointReflection(after_dir, out, dir);
    dir.normalize();
}

void SplineEndDir(point &before, point &loc, point &before_dir, point &dir, bool wrap) {
    point wrapped;

    //get direction from before to loc.
    //check if we need to wrap loc.
    (wrap == true) ? ComputeEndAngleWrap(before, loc, wrapped) : wrapped = loc;
    point in;
    in.sub(wrapped, before);
    in.normalize();

    //get reflection of before dir across in.
    PointReflection(before_dir, in, dir);
    dir.normalize();
}

//returns the reflection of a point through a line.  Line should be normalized.
void PointReflection(point &pnt, point &line, point &reflect) {
    //get dot of pnt and line, the component of pnt along line.
    float dot = pnt.dot(line);

    //stretch line out to dot length.
    point ref_pnt;
    ref_pnt.eq(line, dot);

    //subtract pnt from ref_pnt;
    point ray;
    ray.sub(pnt, ref_pnt);

    //subtract ray from ref_pnt.
    reflect.sub(ref_pnt, ray);
}

void ComputeEndAngleWrap(point &angle_start, point &angle_end, point &wrapped_end) {
    wrapped_end = angle_end;

    //check the difference between the components.
    if (angle_end.x - angle_start.x > 180.0f) {
        //wrap the x.
        wrapped_end.x = angle_end.x - 360.0f;
    }
    else if (angle_end.x - angle_start.x < -180.0f) {
        //wrap the x.
        wrapped_end.x = angle_end.x + 360.0f;
    }

    if (angle_end.y - angle_start.y > 180.0f) {
        //wrap the y.
        wrapped_end.y = angle_end.y - 360.0f;
    }
    else if (angle_end.y - angle_start.y < -180.0f) {
        //wrap the y.
        wrapped_end.y = angle_end.y + 360.0f;
    }

    if (angle_end.z - angle_start.z > 180.0f) {
        //wrap the z.
        wrapped_end.z = angle_end.z - 360.0f;
    }
    else if (angle_end.z - angle_start.z < -180.0f) {
        //wrap the z.
        wrapped_end.z = angle_end.z + 360.0f;
    }
}

float MixVelocity(float oldv, float newv) {
    if (oldv < 0.01 && newv < 0.01) {
        return newv;
    }

    if (oldv < newv) {
        return oldv + (newv - oldv) * (oldv / newv);
    }

    //oldv is greater.
    return newv + (oldv - newv) * (newv / oldv);
}

//Initializes the position splines with the given array of positions and velocities.
void CSplineSequence::InitPositions(int num_positions, const vec3_t *positions, const vec3_t *velocities) {
    if (num_positions < 2) return;
    if (positions == NULL || velocities == NULL) return;

    //get rid of all the old data.
    Reset();

    //set our flag to tell us that this spline only has position data.
    position_only = true;

    //set the number of points.
    num_points = num_positions;

    //set other misc data.
    velocity_start = velocity_end = EV_DEFAULT;
    
    //allocate our arrays.
    times = new float[num_points - 1];
    points = new point[num_points];
    velocity_norm = new point[num_points];
    pos_splines = new CPointSpline *[num_points - 1];

    //intialize data for each point
    for (int i = 0; i < num_points; i++) {
        //set the point.
        points[i] = positions[i];

        //do not normalize the velocities...... ya, ya, bad code.
        velocity_norm[i] = velocities[i];
    }

    //construct the splines.
    for (i = 0; i < num_points - 1; i++) {
        //get the distance from the start point to end point for this spline.
        point line;
        line.sub(points[i + 1], points[i]);

        //use a default time.
        times[i] = line.length();

        pos_splines[i] = new CPointSpline();

        pos_splines[i]->Init(points[i], velocity_norm[i], points[i + 1], velocity_norm[i + 1], times[i]);
    }

    ComputeTime();
}

//Makes as many entities as are needed to represent the sequence position splines.
//Uses the given function for allocating entities.  reference_entity is used
//to initialize data memebers in the entity that are not actually needed by the function
//to position the laser entities.  max_angle (in degrees) affects the smoothness of the curve by specifying
//the maximum allowed angle between adjacent entities.  max_length specifies the maximum length of
//any entity
int CSplineSequence::MakeCurveEntities(entity_t *reference_entity, entity_t *(*entity_alloc)(), 
    float max_angle, float max_length) 
{
    if (reference_entity == NULL) return 0;
    if (entity_alloc == NULL) return 0;

    //the number of entities we have actually used to make the curve.
    int num_entities = 0;

    //check the parameters passed in.
    bound_min(max_angle, 1.0f);
    bound_max(max_angle, 80.0f);

    bound_min(max_length, 1.0f);

    //square the length.
    max_length = max_length * max_length;

    //compute the cos of the tolerance angle that was passed in.
    float angle_tolerance = cos(max_angle / 180.0f * PI);

    //move along the spline and construct lasers to approximate the path.
    //get the initial velocity direction.
    point begin_vel;
    point begin_pos;
    float begin_time = 0.0f;
    int begin_seg = 0;

    Pos(begin_time, begin_pos);
    Vel(begin_time, begin_vel);

    //compute the step length, based on the time of the current segment.
    float step = times[begin_seg] / 50;
    bound_min(step, 0.01f);

    for (float time = 0.0f; time <= TotalTime(); time += step) {
        //get the position at this time.
        point pos;
        Pos(time, pos);

        //get the distance since the last position.
        point line;
        line.sub(pos, begin_pos);
        float distance = line.dot(line);

        //check if we have moved far enough to allow a new entity.
        if (distance < 1.0f) {
            //we havent move far enough in the world.
            continue;
        }

        //we use this copy of the current time because our call to Segment below will modify the value
        //we pass it.
        float segment_time = time;

        //get the segment number for the current time.
        int cur_seg = Segment(segment_time);

        //get the velocity vector at this time
        point vel;
        Vel(time, vel);

        //check if we should make a laser from the last point to the current point.
        if ((vel.dot(begin_vel) > angle_tolerance) &&   //the spline is still on a straight course.
            (distance < max_length) &&                  //we haven't gone too far since the end of the last piece.
            (cur_seg == begin_seg))                     //we are still on the same segment.
        {
            //we should go farther before making the next laser.
            continue;
        }

        //the angles are far enough apart, make a marker.
        //get the begin and ending time we use to find positions from the spline.
        float time_start = begin_time;
        float time_end = time;
        if (time_end - time_start < 0.005f) {
            time_start = time_end - 0.005f;
        }

        //save the current data for next time.
        begin_pos = pos;
        begin_vel = vel;
        begin_time = time;
        begin_seg = cur_seg;

        //recompute our step.
        step = times[begin_seg] / 50;
        bound_min(step, 0.01f);

        //make an entity.
        MakeCurveEntity(time_start, time_end, begin_seg, reference_entity, entity_alloc);

        num_entities++;
    }

    //get the end point of the spline.
    point end_pos;
    Pos(TotalTime(), end_pos);

    //get the distance since the end of the last laser.
    point line;
    line.sub(end_pos, begin_pos);
    float distance = line.dot(line);

    //if the last marker we placed was too far back, make one last marker.
    if (distance > 1.0f) {
        //make an entity from the previous time to the ending time of the sequence.
        MakeCurveEntity(begin_time, TotalTime(), begin_seg, reference_entity, entity_alloc);

        num_entities++;
    }

    return num_entities;
}

void CSplineSequence::MakeCurveEntity(float time_start, float time_end, int segment_num,
    entity_t *reference_entity, entity_t *(*entity_alloc)()) 
{
    //allocate an entity.
    entity_t *entity = entity_alloc();
    if (entity == NULL) return;

    //copy default data from the reference entity to our new entity.
    memcpy(entity, reference_entity, sizeof(entity_t));

    //get the initial and ending positions of the laser.
    point loc, endloc;
    Pos(time_start, loc);
    Pos(time_end, endloc);

    //set the entity model.
    entity->model = NULL;

    //position the entity.
    loc.copyto(entity->origin);
    endloc.copyto(entity->oldorigin);

    //set the render scale.
    static point unity(1.0f, 1.0f, 1.0f);
    unity.copyto(entity->render_scale);

    //store the segment number in the oldframe field
    entity->oldframe = segment_num;
}
