Catmull-Rom Spline Rendering Function (curves)

[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.

[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.

[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).

[ljdp]

This made me remember I had my own version around somewhere.

[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.

[ljdp]

Would it be quicker to implement this into love source?
Aka, love.graphics.bezier( ... )

http://cs1.bradley.edu/public/jcm/cs535BezierCurve.html
http://nehe.gamedev.net/data/lessons/le ... ?lesson=28

[bmelts]

We're (slowly) headed toward 0.7.0, so why not file a feature request?

[ljdp]

Done 8-)

[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

[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.