Page 1 of 2
Catmull-Rom Spline Rendering Function (curves)
Posted: Wed Mar 10, 2010 6:48 am
by Thustrust
Alrighty LOVE community, here's something to play with. It's a single function that takes a table of point values as an input and draws a nice curve, which is technically a Catmull-Rom Spline. As such it's a function you'll want to use in your draw loop. Although I did my best to make it optimized while preserving readability and utility, I'm sure there are still optimizations that could be done... which I'd be happy to hear about.
Features:
-Curves correctly pass through every point in the specified table.
-Detail is a parameter. Try changing the curve detail with time or mouse position!
-Detail automatically scales down in places that aren't very curvy, so there are isn't any time wasted on drawing a bunch of parallel lines instead of one.
-Takes a line drawing function as a parameter, meaning that ANYTHING can be drawn in a spline-fashion. (see the example .love file)
The function code:
Code: Select all
function RenderSpline(tab, detail, func) --takes a table in the form [x1, y1, x2, y2, etc.]
if(tab and (#tab >= 4)) then
local Points = {}
for i=1, (#tab-2), 2 do
local p1x = tab[i]
local p1y = tab[i+1]
local p2x = tab[i+2]
local p2y = tab[i+3]
local p0x = tab[i-2]
local p0y = tab[i-1]
local p3x = tab[i+4]
local p3y = tab[i+5]
--Create a colinearity function to test how colinear three points are:
local colinearity = 0
local function GetColinearity(x1, y1, x2, y2, x3, y3)
local ux = x2 - x1
local uy = y2 - y1
local vx = x3 - x2
local vy = y3 - y2
local udv = (ux*vx + uy*vy)
local udu = (ux*ux + uy*uy)
local vdv = (vx*vx + vy*vy)
local scalar = 1
if(udv < 0) then --the angle is greater than 90 degrees.
scalar = 0
end
return scalar * ((udv*udv) / (udu*vdv))
end
--Calculate the colinearity and the control points for the section:
local t1x = 0
local t1y = 0
local colin1 = 0
if(p0x and p0y) then
t1x = 0.5 * (p2x - p0x)
t1y = 0.5 * (p2y - p0y)
colin1 = GetColinearity(p0x, p0y, p1x, p1y, p2x, p2y)
else
colin1 = nil
end
local t2x = 0
local t2y = 0
local colin2 = 0
if(p3x and p3y) then
t2x = 0.5 * (p3x - p1x)
t2y = 0.5 * (p3y - p1y)
colin2 = GetColinearity(p1x, p1y, p2x, p2y, p3x, p3y)
else
colin2 = nil
end
if(colin1 and colin2) then
colinearity = ((colin1+colin2)/2)
elseif(colin1) then
colinearity = colin1
elseif(colin2) then
colinearity = colin2
else
colinearity = 0
end
--Get the proper detail using the computed colinearity, then calculate the spline points:
local rdetail = (detail * (1-colinearity))
for j=0, rdetail do
local s = j/rdetail
local s2 = s*s
local s3 = s*s*s
local h1 = 2*s3 - 3*s2 + 1
local h2 = -2*s3 + 3*s2
local h3 = s3 - 2*s2 + s
local h4 = s3 - s2
local px = (h1*p1x) + (h2*p2x) + (h3*t1x) + (h4*t2x)
local py = (h1*p1y) + (h2*p2y) + (h3*t1y) + (h4*t2y)
table.insert(Points, px)
table.insert(Points, py)
end
if(math.ceil(rdetail) > rdetail) then
table.insert(Points, p2x)
table.insert(Points, p2y)
end
end
func(Points) --Draws the spline using the function specified.
end
end
There is an example .love attached as well. Check it out to see how the func parameter works.
Controls: Left click a couple times.
Re: Catmull-Rom Spline Rendering Function (curves)
Posted: Wed Mar 10, 2010 4:18 pm
by pekka
This is a nice code snippet!
I'd like to point out here that I've found a passable way to make thicker lines have good-looking meeting points: I drawa circle with a radius half the width of the line at the points where lines end and new lines begin. This method should work easily with this code too, and overall I've found that thicker polylines look quite good when done this way. Without doing something about the gaps in the meeting points, thicker lines tend to look bad. However, this is not always compatible with alpha blending, because there is some overlap where different shapes are drawn.
I have some things to say about the code.
I suggest you change the function to pass the whole table of points to the drawing function instead of unpacking it. Since the drawing function will receive an unknown number of arguments, it will have to use them as a table anyway.
Your example code uses the
arg table to access these arguments in
CustomDraw(...), which you very likely picked up from the
Programming in Lua book's web version. Unfortunately the book is not up to date on this part. The
arg table is deprecated in Lua 5.1 and you should use
{...} to collect the variable number of arguments into a table if you need them in a table. If this is the case, you should really pass them as a table in the first place. There's no need to unpack and then pack the same data again.
The
arg does not exist at all in the LuaJIT version of Lua. It's kept in plain Lua 5.1 for backwards compability. Here is a message from Lua mailing list about this change:
http://lua-users.org/lists/lua-l/2004-08/msg00273.html
Other than these minor issues, I like you code. Thanks for posting it.
Re: Catmull-Rom Spline Rendering Function (curves)
Posted: Wed Mar 10, 2010 8:36 pm
by rude
Cool. How about making a splines library? I would be great to be able to move stuff along the curve with constant speed (relative to the screen).
Re: Catmull-Rom Spline Rendering Function (curves)
Posted: Thu Mar 11, 2010 12:09 am
by ljdp
This made me remember I had my own version around somewhere.
Re: Catmull-Rom Spline Rendering Function (curves)
Posted: Thu Mar 11, 2010 3:28 am
by Thustrust
Thanks for the responses guys!
I'm gonna fix the 'arg' thing right away. I had no idea it was deprecated. Also, I see what you mean about unpacking a table just to make a new one later. I guess the reason it ended up like that was because originally the code just did the love.graphics.line function, and at the last minute I realized I could swap that out for anything. I'll fix that up as well.
As far as the library idea goes, that sounds pretty simple. All it would take to get a point on a spline is to determine where a float between 0 and 1 lies on the spline and then run the same calculation that is used to get all the points inside the spline. I'll definitely look into it.
EDIT: I updated the first post with a new .love file and code for the function. It doesn't unpack the table that it passes any more, it just passes the table. The downside--which I just realized--is that you can't just give it the default love function; you'll have to write a little wrapper function that takes a table and unpacks it before calling the line function. Still, the beauty of this thing is the custom draw function, so I don't think it's a big deal. There was also no need to use arg or {...} any more, so I fixed that up.
I haven't started on the animation idea yet, but in time I'll put something up probably.
Re: Catmull-Rom Spline Rendering Function (curves)
Posted: Thu Mar 11, 2010 11:19 pm
by ljdp
Re: Catmull-Rom Spline Rendering Function (curves)
Posted: Fri Mar 12, 2010 12:48 am
by bmelts
We're (slowly) headed toward 0.7.0, so why not
file a feature request?
Re: Catmull-Rom Spline Rendering Function (curves)
Posted: Fri Mar 12, 2010 1:14 am
by ljdp
Done 8-)
Re: Catmull-Rom Spline Rendering Function (curves)
Posted: Fri Mar 12, 2010 5:49 am
by Thustrust
I'm assuming you put in a request for bezier curves then and not the catmull-rom ones? The only real difference actually is that catmull-rom curves calculate the control points from adjacent points in the list rather than having the user define them. I guess as long as the implementation is good then catmull-rom curves will be an easy little addition.
I'd definitely like to see support for either/both in LOVE though!
By the way, I wrote a nice function that takes a table of points and float from 0-1 and returns the position along the spline. But currently it uses the points in the table to get the proper position and disregards the distance between the points, which is not geometrically correct. I don't know if there's a way to do it properly that is acceptably fast enough...
Here's the function. It doesn't require the other function in this state. Just give it a linear array of point positions and a number from 0-1 and it'll return a position.
Code: Select all
function GetSplinePos(tab, percent) --returns the position at 'percent' distance along the spline.
if(tab and (#tab >= 4)) then
local pos = (((#tab)/2) - 1) * percent
local lowpnt, percent_2 = math.modf(pos)
local i = (1+lowpnt*2)
local p1x = tab[i]
local p1y = tab[i+1]
local p2x = tab[i+2]
local p2y = tab[i+3]
local p0x = tab[i-2]
local p0y = tab[i-1]
local p3x = tab[i+4]
local p3y = tab[i+5]
local t1x = 0
local t1y = 0
if(p0x and p0y) then
t1x = 0.5 * (p2x - p0x)
t1y = 0.5 * (p2y - p0y)
end
local t2x = 0
local t2y = 0
if(p3x and p3y) then
t2x = 0.5 * (p3x - p1x)
t2y = 0.5 * (p3y - p1y)
end
local s = percent_2
local s2 = s*s
local s3 = s*s*s
local h1 = 2*s3 - 3*s2 + 1
local h2 = -2*s3 + 3*s2
local h3 = s3 - 2*s2 + s
local h4 = s3 - s2
local px = (h1*p1x) + (h2*p2x) + (h3*t1x) + (h4*t2x)
local py = (h1*p1y) + (h2*p2y) + (h3*t1y) + (h4*t2y)
return px, py
end
end
Re: Catmull-Rom Spline Rendering Function (curves)
Posted: Fri Mar 12, 2010 6:08 am
by ljdp
Cool.
I've made it so text can run along a path
Thanks to this site:
http://www.planetclegg.com/projects/War ... lines.html
The function could be optimized by splitting it in half, so it only updates the positions when it needs to.