Fill bezier curve pixel by pixel

awsumben13 and I have been experimenting with drawing bezier curves for when Dan hopefully unveils these shiny new graphic options.

Drawing the line is almost trivial really (although note while in this code we do each point one by one we'll be using less points and drawing lines between them).


Here's the code for that:

Spoiler

term.clear()

function calculateBezierPoint( t, p1, p2, p3, p4 )
	local u = 1 - t
	local tt = t * t
	local ttt = tt * t
	local uu = u * u
	local uuu = uu * u
	return uuu * p1.x + 3 * uu * t * p2.x + 3 * u * tt * p3.x + ttt * p4.x, -- x
		   uuu * p1.y + 3 * uu * t * p2.y + 3 * u * tt * p3.y + ttt * p4.y -- y
end

local SEGMENT_COUNT = 1000

local p1 = { x = 2, y = 2 }
local p2 = { x = 17,y = 2 }
local p3 = { x = 50,y = 19 }
local p4 = { x = 7,y = 12 }

term.setBackgroundColour( colours.green )

for i = 0, SEGMENT_COUNT do
	t = i / SEGMENT_COUNT;
	local x, y = calculateBezierPoint( t, p1, p2, p3, p4)
	term.setCursorPos( x, y )
	term.write( ' ' )
end

term.setCursorPos( 1,1 )

That hard bit is filling them. We'll have closed subdivided paths later.

This page linked to by Bomb Bloke on SquidDev's Font API is the kind of technique we are thinking of using. The issue is actually finding the intersection points and y = 2, for example.

Is there some maths wizardry we can use, or do we have to use triangles, which most other libraries seem to use. We thought that using triangles would be far slower in Lua. Although asking Mr Wolfram Alpha shows that solving for t (I used x here) isn't really that… friendly.

Personally, I'd draw the shape into a "display buffer" of some sort (one which lets you inspect its contents), then apply the "fill" functionality once it's finished - inspect each row one after the other, top to bottom. This way, the fill code should be quite simple, and will operate the same no matter how your shape was initially generated.

If I understand correctly, you're trying to fill shapes made out of bezier curves in a similar way you would do for polygons. If that's the case, you can basically use the approach you would do for polygons, and for each row you compute the intersections using line-cubic bezier curve intersection. This page seems to explain pretty well how to do that.

Bomb Bloke, on 11 June 2015 - 05:33 PM said:

Personally, I'd draw the shape into a "display buffer" of some sort (one which lets you inspect its contents), then apply the "fill" functionality once it's finished - inspect each row one after the other, top to bottom. This way, the fill code should be quite simple, and will operate the same no matter how your shape was initially generated.

That's actually a really nice simply way to do it. Thanks!

Yevano, on 12 June 2015 - 03:47 AM said:

If I understand correctly, you're trying to fill shapes made out of bezier curves in a similar way you would do for polygons. If that's the case, you can basically use the approach you would do for polygons, and for each row you compute the intersections using line-cubic bezier curve intersection. This page seems to explain pretty well how to do that.

Thanks for the response, that does indeed have all the maths to solve this. The reason why I think we'll just use Bomb Blokes method is speed and simplicity of it, as well as being able to reuse it for other things. Having to do multiple pow, cos, sqrt, etc. isn't ideal.

oeed, on 12 June 2015 - 08:39 AM said:

Thanks for the response, that does indeed have all the maths to solve this. The reason why I think we'll just use Bomb Blokes method is speed and simplicity of it, as well as being able to reuse it for other things. Having to do multiple pow, cos, sqrt, etc. isn't ideal.

That makes sense, but your current method of drawing the bezier curve itself in the first place isn't ideal. With my method, you only have to calculate the solutions for every row. With the one you're using now, you have to increase the iterations until you get something which looks "good enough." Plus, I doubt there's an easy way to figure out how many iterations you actually need for any given curve for it to look good.

Yevano, on 12 June 2015 - 09:19 PM said:

oeed, on 12 June 2015 - 08:39 AM said:

Thanks for the response, that does indeed have all the maths to solve this. The reason why I think we'll just use Bomb Blokes method is speed and simplicity of it, as well as being able to reuse it for other things. Having to do multiple pow, cos, sqrt, etc. isn't ideal.

That makes sense, but your current method of drawing the bezier curve itself in the first place isn't ideal. With my method, you only have to calculate the solutions for every row. With the one you're using now, you have to increase the iterations until you get something which looks "good enough." Plus, I doubt there's an easy way to figure out how many iterations you actually need for any given curve for it to look good.

Actually that's quite true, using the lines isn't ideal. I'll try that out now.