LÖVE

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

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 })