Drawing Everything AROUND A Polygon (Reversing Mesh Vertices)

Hello all,
In my latest project I am working on lighting. The code will overcomplicate my question, so I’ll just explain it here: my code currently casts rays from a center point to each vertex in the world map, which generate the points of a convex polygon that represents what the player can see from the center of the map. The thing is, after I have this polygon, I can very easily map a mesh onto it by using triangulate(). The problem is that because this is a visibility polygon, I want to draw over everything EXCEPT the polygon. In other words, I want to take these vertices and create a mesh that covers the area around the polygon. Is there any way anyone knows of doing this? Thanks!


EDIT: I forgot to mention this is in two dimensions. If you still don’t know what I mean by lighting, look at a game called Monaco: What’s Yours Is Mine.

I’m not sure I can think of a better solution than using setContext to draw your convex polygon to an image in memory, then using that image as a mask with blend, to only draw what is outside it.

Or, instead of triangulating it as a convex shape, add the four corners of the viewable area to the roster of points, and triangulate it as a concave shape. You’d need to triangulate it in 2 stages, as 2 concave shapes (the halves of a mold), as triangulate can’t handle a shape with a hole in the middle.

Good idea, but if you only include corners, the shape may not be convex in some cases, so I think you might have to add the mid points of the mold where it is split (eg if the mold is split vertically, you would need to include the points halfway along x, at top and bottom of the screen, for each half of the mold).

The two halves don’t have to be even. In my experience, triangulate is fine with complex concave shapes, as long as the points are in order. So if part of the shape is predictable, eg if you want a 120 degree PoV of the player, than perhaps the area directly behind the player is a relatively simple primitive, and you just use triangulate for the complex area within the character’s 120 degree PoV.

Thanks, both of you!
@Ignatz, I think I will have to go with your solution (how slow would that be though? I thought setContext was fairly slow and I don’t think I should be using it every frame which would be a prerequisite). @yojimbo2000, I would love to use your solution but a lot of the time the corners may not be a part of the visibility polygon and I don’t know what to do then; expand the corners outwards? Thanks both of you again, but I think I’ll have to MacGyver a solution for now.

No, add the 4 corner vertices to the roster of points that you pass to triangulate.its only 4 extra vec2s, I can’t imagine it’s that much extra work, for you or the processor! :stuck_out_tongue:

I’m not sure I understand; I might just be being dense, but as the player can sometimes see the corners but sometimes not, I’m not exactly sure that would work. You do mean corners of the screen, correct?

By inverting the visibility polygon, you’re creating a shadow polygon. You need some points that surround the visible area to turn it into a concave shape. I think I was assuming that the player’s visibility had a certain range, a certain falloff (ie the range of a flashlight that you see in these kinds of stealth games), and that range was less than the distance to the screen edge (otherwise you’d be pointlessly drawing the flashlight fall-off off-screen). So yes, whichever 4 points you pass have to completely enclose the visibility polygon. It was my assumption that the visibility polygon didn’t extend off-screen, but if it does, the 4 points would just be whatever bounding box completely encloses the polygon (ie work out the extreme leftmost/rightmost etc points). Could you show us a screenshot of your game? I looked at shots of that Monaco game.

That’s what it looks like. As you can see, the corners aren’t certain

@yojimbo2000, I’ve been trying to implement your solution but nothing I do seems to work. Where in the list should I include the vertices? I wrote some code that shuffles the vertices around of a smaller polygon inside of a larger one then triangulates it, but I never get the shape I’m looking for. Here is my sample code:

-- TestLight

-- Use this function to perform your initial setup
function setup()
    print("Hello World!")
    m = mesh()
    verts = {
    m.vertices = triangulate(verts)
    parameter.action("Shuffle", function() 
        nums = {}
    for i = 1, #verts do
        table.insert(nums, i)
        rverts = {}
        while #nums > 0 do
            local r = math.random(1,#nums)
            rverts[#rverts+1] = verts[nums[r]]
        verts = rverts
        m.vertices = triangulate(verts)

-- This function gets called once every frame
function draw()
    -- This sets a dark background color 
    background(40, 40, 50)

    -- This sets the line thickness

    -- Do your drawing here
    vec = vec2(3*WIDTH/4,HEIGHT/4) -vec2(WIDTH/2,HEIGHT/2)
    vec = vec:normalize()
    line(WIDTH/2,HEIGHT/2,WIDTH/2 + vec.x * WIDTH, HEIGHT/2 + vec.y * WIDTH)

I’m not really sure what I’m looking at with the test code above. The shuffle seems to randomly mix the vertices, but triangulate needs the verts to be in clockwise/ anti-clockwise order.

With the Dropbox screenshot, it looks like the player has an unlimited 360 degree field of view. I’m not sure I would describe the visibility polygon in that shot as “convex”. The approach I was suggesting above would be more appropriate for a bounded visibility polygon (eg a 120 degree “fan” extending 500 pixels or whatever). In your case though, it might be easier to treat each shadow as a separate convex shape.

Sorry to necro-post my own thread(sort-of, is 16 days considered necro-posting?) but I have not been able to come up with a solution on my own. Can anyone post any code or pseudo-code to get me started at least with separating the different polygons? If posting code would help I will but the code is essentially a port of http://ncase.me/sight-and-light/ so I’m not sure how helpful that would be. I can find where the visibility polygon intersects corners of shapes and also where it intersects the boundaries of the level, but as of yet have not been able to use this to separate the visibility polygon into separate polygons around the edges of the level. Thanks in advance for any help!

@TheSolderKing - so you have a starburst of vertices, and you want to shade everything outside them. Triangulating these vertices will of course fill the inside.

I was thinking of a solution along the lines of youjimbo2000’s suggestion, like this.

  1. Assume you have a circular but jagged set of points in clockwise or anti clockwise order, centered on the player position.

  2. Mentally draw a vertical line through the player position, which will cut through the set of points twice, above and below the player. Call these points v1 and v2.

  3. Calculate the intersection points by interpolation

  4. Split the vertices into two meshes, m1 for the points on the left of the player, and m2 for the points on the right, and include v1 and v2 as new points on the end of each mesh

  5. Add points to both meshes to take in the rest of the screen, as shown below

  6. Triangulate

The picture below illustrates the steps for the left hand side of the screen.


Does it work? The very simple sample code underneath suggests it does (the code doesn’t do the calculations for you, it just does step 6).

function setup()
    --after step 5
    local v={vec2(0,0),vec2(400,0),vec2(400,100),vec2(340,70),

function draw()

Thanks @Ignatz, that’s a better response than I could have hoped for! I will try that out to see if I can get that working!