Log In  

Hi,

I am trying to come up with a simple algorithm for filling an area of the screen a particular color.

I have a "path" in my game defined by the thin white lines shown above. Lines are represented with the following data structures:

function mkvec(x,y)
    local v=
    {
        x=x,
        y=y,

        getlength=function(self)
            return sqrt(self.x^2+self.y^2)
        end,

        getnorm=function(self)
            local l = self:getlength()
            return mkvec(self.x / l, self.y / l);
        end,
    }
    return v
end

----------------------------

function mkline(x1,y1,x2,y2)
    local l=
    {
        a=mkvec(x1,y1),
        b=mkvec(x2,y2),

        draw=function(l,col)
            line(l.a.x,l.a.y,l.b.x,l.b.y,col)
        end,

        drawnear=function(l,o,col)
            local lp=closestpointalongline(
                l.a,l.b,mkvec(o.x,o.y))
            circ(lp.x,lp.y,2,col)           
        end,

        closest=function(l,o)
            return closestpointalongline(
                l.a,l.b,mkvec(o.x,o.y))
        end,
    }

    return l
end

I would like for the areas on the left and right of the path (the part with red thick lines scribbled in) to be filled a different color.

My current plan is to define a directional vector for corner to corner, and walk the line one pixel at a time, draw a line from there to the edge of the screen.

These feels a little hackish, so I'm wondering if there is something better! I suspect this may be a polygon fill algorithm, but since this problem set is some limited, I thought there might be a simpler way.

I also suspect that my pixels wont like up with the edge of the line, leaving small single pixel gaps.

Thanks!

P#32721 2016-11-23 19:02 ( Edited 2016-11-25 00:05)

Given the start and end points for each segment (x1,y1) and (x2,y2), find the equation for the line: y = mx + b, or x = (y - b) / m. m is the slope of the line = (y2-y1)/(x2-x1). Solve for b using one of the points: b = y1 - x1 * (y2-y1)/(x2-x1)

For each y between y1 and y2, find x using x = (y - b) / m. Alternatively for each x find y using y = mx - b. To fill to the right, draw a line from (x, y) to (127, y). To fill to the left, draw a line from (0, y) to (x, y).

P#32723 2016-11-23 20:12 ( Edited 2016-11-24 01:12)

Here's a demo:

function fill_side(x1, y1, x2, y2, col, is_left)
  local x, y

  -- offset for rounding
  if not is_left then
    x1 += 1
    x2 += 1
  end

  local m = (y2-y1)/(x2-x1)
  local b = y1 - x1 * m      

  for y=min(y1,y2),max(y1,y2) do
    x = (y-b)/m
    if is_left then
      line(0,y,x,y,col)
    else
      line(x,y,127,y,col)
    end
  end
end

function _init()
  px = 30
  py = 30
  ex = 60
  ey = 90
  side = false
end

function _update()
  if (btn(0)) px -= 1
  if (btn(1)) px += 1
  if (btn(2)) py -= 1
  if (btn(3)) py += 1
  if (btnp(4)) side = not side
end

function _draw()
  cls()
  fill_side(px, py, ex, ey, 8, side)
  line(px, py, ex, ey, 7)
end

I offset the fill by +1 when filling to the right because rounding puts the fill over the line by one pixel. This doesn't happen when filling to the left.

This version doesn't correctly handle the edge cases where y2=y1 or x2=x1. This is left as an exercise. ;)

(edit: cleaned it up some)

P#32724 2016-11-23 20:25 ( Edited 2016-11-24 01:45)

Thanks Dan!

P#32725 2016-11-23 20:27 ( Edited 2016-11-24 01:27)

Might be faster and fewer tokens to draw the background over the whole screen, then fill the path over it.

P#32727 2016-11-24 02:16 ( Edited 2016-11-24 07:16)

You'd have to figure out which left and right segments are involved for each y. You could sort them into left and right sets and march down them as you cross each boundary. Whether that's fewer tokens I don't know. It would be one less line() call.

P#32728 2016-11-24 03:18 ( Edited 2016-11-24 08:18)

Rectfill commands are faster than horizontal lines for this sort of rasterization. If you want to get really fast, memset screams, but you are stuck filling in 2 pixel wide blocks unless you add code for the end pixels which would surely slow things right down again.

P#32735 2016-11-24 13:56 ( Edited 2016-11-24 18:56)

If this is a vertical scroller after all, another idea to consider is storing each raster line in a 128-element array, push new rows to the bottom, and pop off the top with DEL(). (Or do a rolling index.) Then you can use the array for drawing and collision.

P#32738 2016-11-24 19:05 ( Edited 2016-11-25 00:05)

[Please log in to post a comment]

Follow Lexaloffle:          
Generated 2023-03-27 06:58:35 | 0.006s | Q:18