src/math/spline.cpp

   1 /*
   2  * Copyright (C) Volition, Inc. 1999.  All rights reserved.
   3  *
   4  * All source code herein is the property of Volition, Inc. You may not sell
   5  * or otherwise commercially exploit the source or things you created based on
   6  * the source.
   7  */
   8
   9 /*
  10  * $Logfile: /Freespace2/code/Math/spline.cpp $
  11  * $Revision$
  12  * $Date$
  13  * $Author$
  14  *
  15  *
  16  * $Log$
  17  * Revision 1.4  2002/06/17 06:33:09  relnev
  18  * ryan's struct patch for gcc 2.95
  19  *
  20  * Revision 1.3  2002/06/09 04:41:22  relnev
  21  * added copyright header
  22  *
  23  * Revision 1.2  2002/05/03 13:34:33  theoddone33
  24  * More stuff compiles
  25  *
  26  * Revision 1.1.1.1  2002/05/03 03:28:09  root
  27  * Initial import.
  28  *
  29  *
  30  * 3     7/08/99 10:53a Dave
  31  * New multiplayer interpolation scheme. Not 100% done yet, but still
  32  * better than the old way.
  33  *
  34  * 2     7/06/99 4:24p Dave
  35  * Mid-level checkin. Starting on some potentially cool multiplayer
  36  * smoothness crap.
  37  *
  38  *
  39  * $NoKeywords: $
  40  */
  41
  42 #include "vecmat.h"
  43 #include "2d.h"
  44 #include "3d.h"
  45 #include "alphacolors.h"
  46 #include "spline.h"
  47
  48 // -------------------------------------------------------------------------------------------------
  49 // SPLINE DEFINES/VARS
  50 //
  51
  52
  53 // -------------------------------------------------------------------------------------------------
  54 // SPLINE FUNCTIONS
  55 //
  56
  57 // integer factorial. =o
  58 int bez_fact(int n)
  59 {
  60         int idx;
  61         int product = 1;
  62
  63         // do eet
  64         for(idx=1; idx<=n; idx++){
  65                 product *= idx;
  66         }
  67
  68         return product;
  69 }
  70
  71 // bez constructor
  72 bez_spline::bez_spline()
  73 {
  74         int idx;
  75
  76         // zero all points
  77         for(idx=0; idx<MAX_BEZ_PTS; idx++){
  78                 pts[idx] = vmd_zero_vector;
  79         }
  80         num_pts = 0;
  81 }
  82
  83 // bez constructor
  84 bez_spline::bez_spline(int _num_pts, vector *_pts[MAX_BEZ_PTS])
  85 {
  86         bez_set_points(_num_pts, _pts);
  87 }
  88
  89 // set control points
  90 void bez_spline::bez_set_points(int _num_pts, vector *_pts[MAX_BEZ_PTS])
  91 {
  92         int idx;
  93
  94         // store the points
  95         num_pts = _num_pts;
  96         for(idx=0; idx<_num_pts; idx++){
  97                 SDL_assert(_pts[idx] != NULL);
  98                 if(_pts[idx] != NULL){
  99                         pts[idx] = *_pts[idx];
 100                 }
 101         }
 102 }
 103
 104 // blend function
 105 #define COMB(_n, _k)            ( (float)bez_fact(_n) / (float)(bez_fact(_k) * bez_fact(_n - _k)) )
 106 float bez_spline::BEZ(int k, int n, float u)
 107 {
 108         float a = (float)COMB(n, k);
 109         float b = (float)pow(u, (float)k);
 110         float c = (float)pow(1.0f - u, (float)(n - k));
 111
 112         return a * b * c;
 113 }
 114
 115 // get a point on the curve
 116 void bez_spline::bez_get_point(vector *out, float u)
 117 {
 118         int idx;
 119         float bez_val;
 120
 121         SDL_assert(out != NULL);
 122         if(out == NULL){
 123                 return;
 124         }
 125
 126         // calc
 127         out->xyz.x = 0.0f;
 128         out->xyz.y = 0.0f;
 129         out->xyz.z = 0.0f;
 130         for(idx=0; idx<num_pts; idx++){
 131                 // bez val
 132                 bez_val = BEZ(idx, num_pts-1, u);
 133
 134                 // x component
 135                 out->xyz.x += pts[idx].xyz.x * bez_val;
 136
 137                 // y component
 138                 out->xyz.y += pts[idx].xyz.y * bez_val;
 139
 140                 // z component
 141                 out->xyz.z += pts[idx].xyz.z * bez_val;
 142         }
 143 }
 144
 145 // render a bezier
 146 void bez_spline::bez_render(int divs, color *c)
 147 {
 148         float inc;
 149         int idx;
 150         vertex a, b;
 151         vector pt;
 152
 153         // bleh
 154         if(divs <= 0){
 155                 return;
 156         }
 157         inc = 1.0f / (float)divs;
 158
 159         // draw in red
 160         gr_set_color_fast(c);
 161
 162         // draw that many divisions
 163         bez_get_point(&pt, 0.0f);
 164         g3_rotate_vertex(&a, &pt);
 165         for(idx=1; idx<=divs; idx++){
 166                 // second point
 167                 bez_get_point(&pt, (float)idx * inc);
 168                 g3_rotate_vertex(&b, &pt);
 169
 170                 // draw the line
 171                 g3_draw_line(&a, &b);
 172
 173                 // store b
 174                 a = b;
 175         }
 176
 177         // draw the control points
 178         gr_set_color_fast(&Color_bright_green);
 179         for(idx=0; idx<num_pts; idx++){
 180                 g3_draw_sphere_ez(&pts[idx], 0.75f);
 181         }
 182 }
 183
 184
 185 // --------------------------------------------------------------------------
 186 // HERMITE splines
 187
 188 // constructor
 189 herm_spline::herm_spline()
 190 {
 191         int idx;
 192
 193         // zero all points
 194         for(idx=0; idx<MAX_HERM_PTS; idx++){
 195                 pts[idx] = vmd_zero_vector;
 196                 d_pts[idx] = vmd_zero_vector;
 197         }
 198         num_pts = 0;
 199 }
 200
 201 // constructor
 202 herm_spline::herm_spline(int _num_pts, vector *_pts[MAX_HERM_PTS], vector *_d_pts[MAX_HERM_PTS])
 203 {
 204         herm_set_points(_num_pts, _pts, _d_pts);
 205 }
 206
 207 // set the points
 208 void herm_spline::herm_set_points(int _num_pts, vector *_pts[MAX_HERM_PTS], vector *_d_pts[MAX_HERM_PTS])
 209 {
 210         int idx;
 211
 212         // store the points
 213         num_pts = _num_pts;
 214         for(idx=0; idx<_num_pts; idx++){
 215                 SDL_assert(_pts[idx] != NULL);
 216                 if(_pts[idx] != NULL){
 217                         pts[idx] = *_pts[idx];
 218                 }
 219                 SDL_assert(_d_pts[idx] != NULL);
 220                 if(_d_pts[idx] != NULL){
 221                         d_pts[idx] = *_d_pts[idx];
 222                 }
 223         }
 224 }
 225
 226 // get a point on the hermite curve.
 227 void herm_spline::herm_get_point(vector *out, float u, int k)
 228 {
 229         float a = ( (2.0f * u * u * u) - (3.0f * u * u) + 1 );
 230         float b = ( (-2.0f * u * u * u) + (3.0f * u * u) );
 231         float c = ( (u * u * u) - (2.0f * u * u) + u );
 232         float d = ( (u * u * u) - (u * u) );
 233
 234         vector va;
 235         vm_vec_copy_scale(&va, &pts[k], a);
 236
 237         vector vb;
 238         vm_vec_copy_scale(&vb, &pts[k+1], b);
 239
 240         vector vc;
 241         vm_vec_copy_scale(&vc, &d_pts[k], c);
 242
 243         vector vd;
 244         vm_vec_copy_scale(&vd, &d_pts[k+1], d);
 245
 246         vm_vec_add(out, &va, &vb);
 247         vm_vec_add2(out, &vc);
 248         vm_vec_add2(out, &vd);
 249 }
 250
 251 // the derivative of a point on the hermite curve
 252 void herm_spline::herm_get_deriv(vector *deriv, float u, int k)
 253 {
 254         float a = ( (6.0f * u * u) - (6.0f * u) );
 255         float b = ( (-6.0f * u * u) + (6.0f * u) );
 256         float c = ( (3.0f * u * u) - (4.0f * u) + 1 );
 257         float d = ( (3.0f * u * u) - (2.0f * u) );
 258
 259         vector va;
 260         vm_vec_copy_scale(&va, &pts[k], a);
 261
 262         vector vb;
 263         vm_vec_copy_scale(&vb, &pts[k+1], b);
 264
 265         vector vc;
 266         vm_vec_copy_scale(&vc, &d_pts[k], c);
 267
 268         vector vd;
 269         vm_vec_copy_scale(&vd, &d_pts[k+1], d);
 270
 271         vm_vec_add(deriv, &va, &vb);
 272         vm_vec_add2(deriv, &vc);
 273         vm_vec_add2(deriv, &vd);
 274 }
 275
 276 // render a bezier
 277 void herm_spline::herm_render(int divs, color *clc)
 278 {
 279         int idx;
 280         int s_idx;
 281         float inc = 1.0f / (float)divs;
 282
 283         vertex a, b, c;
 284         vector pt, d_pt;
 285
 286         // draw in red
 287         gr_set_color_fast(clc);
 288
 289         // render each section
 290         for(idx=0; idx<num_pts-1; idx++){
 291                 // render this piece
 292                 herm_get_point(&pt, 0.0f, idx);
 293                 g3_rotate_vertex(&a, &pt);
 294
 295                 // draw the deriv
 296                 herm_get_deriv(&d_pt, 0.0f, idx);
 297                 vm_vec_add2(&d_pt, &pt);
 298                 g3_rotate_vertex(&c, &d_pt);
 299                 g3_draw_line(&a, &c);
 300
 301                 for(s_idx=1; s_idx<divs * 2; s_idx++){
 302                         // second point
 303                         herm_get_point(&pt, (float)s_idx * inc, idx);
 304
 305                         // 2nd point on the line
 306                         g3_rotate_vertex(&b, &pt);
 307
 308                         // draw the line
 309                         g3_draw_line(&a, &b);
 310
 311                         // draw the deriv line
 312                         herm_get_deriv(&d_pt, (float)s_idx * inc, idx);
 313                         vm_vec_add2(&d_pt, &pt);
 314                         g3_rotate_vertex(&c, &d_pt);
 315                         g3_draw_line(&b, &c);
 316
 317                         // store b
 318                         a = b;
 319                 }
 320         }
 321
 322         // draw the control points
 323         gr_set_color_fast(&Color_bright_green);
 324         for(idx=0; idx<num_pts; idx++){
 325                 g3_draw_sphere_ez(&pts[idx], 0.75f);
 326         }
 327 }
 328