Scanline Polygon Rendering Woes

I’ve recently been recoding the bezier/polygon renderer for Silica (the old one was super buggy). I’m using a normal scanline method of filling them.


All seemed well, I found a few things online which (poorly) explained how to solve the single point/maxima issues and got that working. Bezier curves and straight lines work as you'd expect really. Here's an example screenshot of a non-simple path.



However, I then tried to draw a simple left/right arrow like below (this is from Photoshop, not a screenshot) and it stopped working. The shape is a single polygon with lines between each vertex as you'd expect it to be.



Here’s a diagram showing what the scanline should be doing. Green represents pixels where it will start filling, red where it will stop filling and orange where it will start and stop on the same pixel (i.e. it will only fill that one pixel).



However, everything I try messes up, here's what ends up happening (I can't show what it renders because it just crashes).



The above diagram will produce an error because on line 3 and line 5 there are an odd number of start/stop points, so it will draw between x = 1 and x = 4, and then start drawing again at x = 6, but it doesn't have an end point. The reason for this is at the intersection where the triangle section meets the rectangle it places a point as it’s a vertex with a change in slope.

When I plot the the points of a line the first pixel is ignored unless it’s a maxima (orange pixels), which is what most things online say to do. Hence, only one point is made at the intersection between the triangle section and rectangle.

If I make intersections with horizontal lines always place a start/stop point (orange) it draws correctly with the below points.



While this works for a right arrow, if I then change the shape to, for example, a left arrow it then breaks again.




Essentially, it in situations where the right angle is the first pixel it needs to start the scanline, but in situations where it's between and start and end point it needs to be ignored. Using the slopes alone this doesn't work, I can't tell if it's a convex or concave. Every way I can think of to get around this seems super hacky and specific and probably breaks something else, so does does anyone have any ideas, documents or code which might help?

I'm quite happy to completely redo the code, but it will need to support straight lines and bezier curves.

Here's the current code: https://github.com/oeed/Silica/blob/828fafbefe871a31052c93b6b0f29f18bf4f8897/src/classes/Graphics/Path.lua#L294

I'm a fan of this method.

Bomb Bloke, on 10 December 2015 - 07:27 AM said:

I'm a fan of this method.

I've converting his (hideously formatted) C code in to Lua essentially verbatim.

Spoiler

--[[

The polygon. A number represents the nth vertex, # represents other filled areas.

   1
   ##
6##7##
######2
5##4##
   ##
   3

]]

-- This input seems to be the correct format, looking at some of the linked pages
local polyCorners = 7
local polyX = {
	4,
	7,
	4,
	4,
	1,
	1,
	4
}
local polyY = {
	1,
	4,
	7,
	5,
	5,
	3,
	3
}

local height = 7
local width = 7

term.setBackgroundColour( colours.black )
term.clear()
term.setBackgroundColour( colours.red )

for pixelY = 1, height do
	--  Build a list of nodes.
	local nodeX = {}
	local j = polyCorners
	for i = 1, polyCorners do
		if polyY[i] < pixelY  and polyY[j] >= pixelY or polyY[j] < pixelY and polyY[i] >= pixelY then
			table.insert( nodeX, polyX[i] + ( pixelY - polyY[i] ) / ( polyY[j] - polyY[i] ) * ( polyX[j] - polyX[i] ) )
		end
		j = i
	end

	-- Sort the nodes, just use the built-in Lua table sort though
	table.sort( nodeX )

	--  Fill the pixels between node pairs.
	for i = 1, #nodeX, 2 do
		if nodeX[i] > width then
			break
		end

		if nodeX[i  + 1] > 1 then
			if nodeX[i] < 1 then
				nodeX[i] = 1
			end
			if nodeX[i + 1] > width then
				nodeX[i + 1] = width
			end

			for pixelX = nodeX[i], nodeX[i + 1] do
				term.setCursorPos( pixelX, pixelY )
				term.write( " " )
			end
		end
	end
end
term.setCursorPos( 1, 10 )

It's almost correct, but it's still not really working 100%.

The top vertex is skipped over, any ideas why?



I've triple checked the code and it's almost identical for the important logic, so is this a fault in the algorithm or have I done something wrong?

oeed, on 10 December 2015 - 12:11 PM said:

I've converting his (hideously formatted) C code in to Lua essentially verbatim.

Heh. I imagine you'd love my Java implementation.

oeed, on 10 December 2015 - 12:11 PM said:

The top vertex is skipped over, any ideas why?

You'll need to draw the rest of the poly in addition to "filling" it. You're actually plotting a little bit more than you should with what you've got, due to a couple of off-by-one errors in your conversion (eg that final "for" loop), but I doubt that'll cause you problems.

Bomb Bloke, on 10 December 2015 - 02:45 PM said:

You'll need to draw the rest of the poly in addition to "filling" it. You're actually plotting a little bit more than you should with what you've got, due to a couple of off-by-one errors in your conversion (eg that final "for" loop), but I doubt that'll cause you problems.

Oh, actually that's a good way to get around it, thanks! I'll need to figure out how to get bezier curves working with it though.

I'll check over the off my one errors (knew I'd hit those somewhere) and see if I can get it working.

The same basic rule should apply; for every row that needs to be filled, the number of points from your shape that intersects that row will be an even number.

So, as you draw the outline to your curve, stick the x-coords for each point you plot into one table for each row (omitting, say, the top-left-most point for each line, to prevent double-ups where they join). After that, the same "sort then join-the-dots" thing applies.

Yeah that worked out perfectly! Thanks!