Splines!

[Ref]

For CatMullRom spline all you need is:

Code: Select all

function smooth( points, steps )
   if #points < 3 then return points end
   local steps = steps or 5
   local spline = {}
   local count = #points - 1
   local p0, p1, p2, p3, x, y
   for i = 1, count do
      if i == 1 then
         p0, p1, p2, p3 = points[i], points[i], points[i + 1], points[i + 2]
         elseif
         i == count then
         p0, p1, p2, p3 = points[#points - 2], points[#points - 1], points[#points], points[#points]
         else
         p0, p1, p2, p3 = points[i - 1], points[i], points[i + 1], points[i + 2]
         end
      for t = 0, 1, 1 / steps do
         x = 0.5*((2*p1.x)+(p2.x-p0.x)*t+(2*p0.x-5*p1.x+4*p2.x-p3.x)*t*t+(3*p1.x-p0.x-3*p2.x+p3.x)*t*t*t)
         y = 0.5*((2*p1.y)+(p2.y-p0.y)*t+(2*p0.y-5*p1.y+4*p2.y-p3.y)*t*t+(3*p1.y-p0.y-3*p2.y+p3.y )*t*t*t)
         --prevent duplicate entries
         if not(#spline > 0 and spline[#spline].x == x and spline[#spline].y == y) then
            table.insert( spline , { x = x , y = y } ) -- table of indexed points
            end
         end
      end
   return spline
 end

where points are the points you want the curve to go through and steps is the number of point to interpolate between.

[Taehl]

So they only way to have a spline is in discrete steps? You can't just ask it for an arbitrary "position in the spline" (maybe a percentage or something) and get one point?

[Ref]

Anything's possible, if you’re devious enough.
Just requires a little coding and at least four points into the spline.
Edit:
Just put something together that I think simulates what you want.
FPS not too bad.
Be warned that there is a problem with what happens at the end of the spline - needs some more head scratching.

[MarekkPie]

I actually had to implement arbitrary splines are any degree for a graphics class this semester. I believe the method Ref is describing will only give you cubic Catmull-Rom splines. Granted, that's what most people use, but if you want something a bit more robust, here is some Lua code. I quickly converted my C++ code for the project to Lua, so there may be some mistakes, but hopefully the general idea is there:

Code: Select all

local CatmullRom = {}
CatmullRom.__index = CatmullRom

-- http://en.wikipedia.org/wiki/De_Boor%27s_algorithm
local function deBoor(time, values, degree, sep, start)
  start = start or 1

  local newValues = {}
  for i = 0, #values - 1 do
    local lhs = (start + i + sep - time) / sep * values[i + 1]
    local rhs = (time - (start + i))     / sep * values[i + 2]

    table.insert(newValues, lhs + rhs)
  end

  if sep == 1 then
    if #newValues == 1 then
      return newValues[0]
    else
      local i = math.floor(time - degree)
      return newValues[i < #newValues and i or i - 1]
    end
  else
    return deBoor(time, newValues, sep - 1, start + 1)
  end
end

-- http://en.wikipedia.org/wiki/Neville_algorithm
local function neville(time, values, degree, sep)
  sep = sep or 1

  local newValues = {}
  for i = 0, #values - 1 do
    local lhs = (i + sep - time) / sep * values[i + 1]
    local rhs = (time - i)       / sep * values[i + 2]

    table.insert(newValues, lhs + rhs)
  end

  if sep == degree + 1 then
    return deBoor(time, newValues, degree, sep - 1)
  else
    return neville(time, newValues, degree, sep + 1)
  end
end

function CatmullRom:new(controlPoints, degree)
  return setmetatable({
    controlPoints = controlPoints,
    degree = degree,
    interpolants = {},
  }, self)
end

function CatmullRom:initialize()
  for i = self.degree, #controlPoints - degree, 0.1 do
    table.insert(self.interpolants, self:interpolate(i))
  end
end

-- Gets an arbitrary point of the Catmull-Rom spline
function CatmullRom:interpolate(time)
  -- Separate the x- and y-coordinates of the points
  local x, y = {}, {}
  for _,v in ipairs(self.controlPoints) do
    table.insert(x, v[0])
    table.insert(y, v[1])
  end

  -- Catmull-Rom splines are a combination of Lagrange curves and B-Splines,
  -- so we use Neville's algorithm to build the Lagrange steps
  -- and deBoor's algorithm to build the B-Spline steps
  return { neville(time, x, self.degree), neville(time, y, self.degree) }
end

function CatmullRom:draw()
  love.graphics.line(self.interpolants)
end

return setmetatable(CatmullRom, { __call = CatmullRom.new })

[Ref]

Would really appreciate a Love demo so that we can see the difference 'degree' makes.
Not obvious as to the feeding and care required by your library (at least for the mentally challenged.)

Didn't mean to imply that the cubic CatMullRom I posted first was unstable (it isn't!) only that my hack job to get % along curve didn't handle the last control point properly (a common problem with curve fitting).

[MarekkPie]

I'll try and make a similar library to what vrld has over Spring Break (which is next week for my school). To the human eye, there isn't much difference between the continuity (smoothness) a cubic Catmull-Rom spline provides and higher degree Catmull-Rom splines, but when you start getting into shading and reflections on Catmull-Rom surfaces, higher order smoothness becomes a factor (since there is some derivation of the curve going on in those calculations).

I'm really just regurgitating what my professor has talked about this semester. If you'd like to read the notes yourself, they're freely available online at his course website.