Polygonal mouseover in canvas? Help!


  • Tiger Hat

    By which I mean, there is an area, bounded by a complex line, on the canvas. You want to detect if the user has clicked inside, or is hovering there. Is this a thing? Can you do this?

    All I can think of at the moment is breaking it down into more simple shapes, e.g. squares, and testing each independently.

    Given a mousedown event, e:

    var clicked = false;
    if (e.x > 30 && e.x < 50 && e.y > 10 && e.y < 40) {clicked = true;}
    if (e.x > 50 && e.x < 55 && e.y > 10 && e.y < 15) {clicked = true;}
    

    The above would (in my mind, at least!) check an area of 20px by 20px and an attached area of 5px by 5px.
    It’s not pretty, and it’s not clever, so i wondered if anyone had a better idea.
    I’m prepared to look like an idiot here - it’s probably a really obvious thing that I’ve just never heard of…


  • Tiger Hat

    Hmm as far as I know there isn’t an easy way to do it, unless the object name gets bubbled up in the touch event of the canvas?

    The other thing you could do is similar to what you suggested except you could analyse the pixel data using get image data on the canvas and check if the alpha channel is greater than 0.


  • LDG

    It’s probably not so obvious, but what you want is to test whether a given point (x, y) is within a complex polygon. I haven’t implemented this sort of hit detection myself, but this Stack Overflow question might be a good place to start. It appears that ray casting is the preferred method for determining if a point is within a polygon. In short, you trace a ray from outside the polygon to your desired point and count the number of times it intersects with the edges of the polygon. If the number is odd, it’s inside the polygon, otherwise it’s outside (even).

    This is the kind of algorithm that’s good to have as a generic function somewhere because it can be useful for UI hit detection as well as general game collision/hit test logic.


  • LDG

    @the_fisk said:

    The other thing you could do is similar to what you suggested except you could analyse the pixel data using get image data on the canvas and check if the alpha channel is greater than 0.

    This is another interesting method and should work provided you have a “mask” of your shape drawn to a hidden canvas. You can draw the shape as full black and test the pixel coordinates as @the_fisk mentions. The downsides to this approach are that it may not be very fast to sample pixel data every frame, and storing/managing your masks is some extra overhead in terms of memory and code.

    The purely mathematical solution is more complex to understand, but should result in a pretty short function that can test hit detection quickly and without dealing with graphics/masks.


  • Patron

    Well, as @the_fisk and @geoffb already said, you can use pixel perfect collision, but it’s kinda slow.
    If you’re dealing only with convex polygons, it will probably be easy to use the Hyperplane separation theorem (aka SAT).
    You can find lots o’ good tutorials about SAT in the interwebs…
    I’m pretty sure there are algorithms for breaking concave and complex polygons into smaller convex polygons, so you can use SAT with them.
    What is great about SAT, besides the speed, is that it’s pretty popular, so, it’s easy to find help online.
    Also, someone already did a Javascript library which implements SAT, obviously called SAT.js.
    Phaser uses SAT.js under the hood to do collisions since version 1.1.6


  • Tiger Hat

    Awesome guys, that’s really helpful! I’ll get to work on implementing something :)


  • Tiger Hat

    @Josue said:

    If you’re dealing only with convex polygons, it will probably be easy to use the Hyperplane separation theorem (aka SAT).

    How do you know this stuff?!?!?!


  • Patron

    @cheersphilip said:

    @Josue said:

    If you’re dealing only with convex polygons, it will probably be easy to use the Hyperplane separation theorem (aka SAT).

    How do you know this stuff?!?!?!

    Well, it’s actually a quite interesting story (at least I think it is).
    After listening to Lostcast episode 2 I was super excited about Crafty, so, I obviously started to read stuff on the site and play the demos.
    And I saw this thing on the site:
    what?

    Coincidentally, I was having lots of collision problems with the platformers I was trying to implement, so I was instantly all over SAT.
    And then… Google!


  • Tiger Hat

    So do you actually use Crafty?
    Because it does look very tempting, but I always feel a bit allergic to frameworks… not for any clever reason, I just don’t want/don’t have the time to trawl through someone else’s API before I can start making anything…
    A great reason to revisit an early Loscast though!


  • LDG

    @josue: Any story that begins with “After listening to Lostcast…” is an interesting story! :)

    Unless it ends with “…and then I wanted to punch Geoff in the face.”

    Back on topic, though: SAT is super useful, not just for detecting collisions, but for collision response as well. With SAT, you’re calculating the axis of least separation and pushing your game objects apart based on that axis. This leads to more consistent collision behaviors, in general. I recently switched over some AWL code to use SAT and it was a big improvement. I’ve been mulling over using SAT.js for Djinn 3. In fact, @richtaur and I were talking about that just yesterday.


  • Patron

    @cheersphilip said:

    So do you actually use Crafty?

    Well, no. I tryed it out, but I didn’t quite like the way the entity/component system is structured in Crafty.

    Because it does look very tempting, but I always feel a bit allergic to frameworks… not for any clever reason, I just don’t want/don’t have the time to trawl through someone else’s API before I can start making anything…

    Yeah, I kinda feel like that about Phaser. Sure, it has billions of cool features, but I have to get through the HUGE api documentation before I can use them.

    A great reason to revisit an early Loscast though!

    Every time I think about revisiting one of the oldest lostcasts, I’m immediately turned off by the low audio quality…
    Well, at least that’s a sign of improvement!


  • Patron

    @geoffb said:

    @josue: Any story that begins with “After listening to Lostcast…” is an interesting story! :)

    Unless it ends with “…and then I wanted to punch Geoff in the face.”

    Actually, all the stories I have about Lostcast are interesting, even those which end with wanting to punch someone XD

    Back on topic, though: SAT is super useful, not just for detecting collisions, but for collision response as well. With SAT, you’re calculating the axis of least separation and pushing your game objects apart based on that axis. This leads to more consistent collision behaviors, in general.

    Yeah, collision detection is relatively easy, but doing realistic collision response sure isn’t.
    Well, if I were working on a game heavily physically-based, I would probably go for Box2dWeb, PhysicsJS or Newton.


  • Tiger Hat

    Yay-us. I got this.

    It doesn’t work with concave polygons (change the 30,90 to 80,80), but hey I don’t need it to atm so yay!


  • Tiger Hat

    @cheersphilip said:

    Yay-us. I got this.

    It doesn’t work with concave polygons (change the 30,90 to 80,80), but hey I don’t need it to atm so yay!

    Actually it doesn’t even work very well at all. Dammit.

    I got the code from stackoverflow and this article. Originally in C, so…

    fail :(

    #edit:

    got it working (damned padding) here.

    Also, that moment when you realise that you’ve spent an hour editing a snippet, only to find that if you’d scrolled further down that stackoverflow article you would have found that someone had already done this for you… all part of the process I guess!


  • Tiger Hat

    I’m on a roll! Just going to leave this here

    smiles



  • Good to see more code being posted now as I always felt this could be a developer centric forum. It’ll be nice to see a “New Projects/What are you working on” thread pop at some point once you’ve got your first concept ready to start working on @cheersphilip. What kind of games would you actually like to make? Broadly speaking of course.


  • Tiger Hat

    @Affordable_Desk said:

    Good to see more code being posted now as I always felt this could be a developer centric forum. It’ll be nice to see a “New Projects/What are you working on” thread pop at some point once you’ve got your first concept ready to start working on @cheersphilip. What kind of games would you actually like to make? Broadly speaking of course.

    &quot;Whatever I feel like I wanna do. Gosh!


  • Patron

      for (i = 0; i < vertx.length; i++) {
        if ( ((verty[i]>testy) != (verty[j]>testy)) && (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) ){
           c = !c;
        }
        j=i;
      }
    

    Ok… what the heck is going on here?

    @cheersphilip, help!


  • Tiger Hat

    @Josue said:

      for (i = 0; i < vertx.length; i++) {
        if ( ((verty[i]>testy) != (verty[j]>testy)) && (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) ){
           c = !c;
        }
        j=i;
      }
    

    Ok… what the heck is going on here?

    @cheersphilip, help!

    Could…could it be? Has he solved… Impossible… I’ve checked and rechecked and I can’t find an error in his proof.


  • Tiger Hat

    @Affordable_Desk said:

    @Josue said:

      for (i = 0; i < vertx.length; i++) {
        if ( ((verty[i]>testy) != (verty[j]>testy)) && (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) ){
           c = !c;
        }
        j=i;
      }
    

    Ok… what the heck is going on here?

    @cheersphilip, help!

    Could…could it be? Has he solved… Impossible… I’ve checked and rechecked and I can’t find an error in his proof.

    You guys didn’t check my sources! This found just by looking at the original response from @geoffb :)
    ##Jordan curve theorem FTW!


  • Patron

    @cheersphilip said:

    ##Jordan curve theorem FTW!

    Hum… interesting…

    That is far from being how I thought one would implement this theorem, but also looks to be way more effective than the implementation I thought of.

    The only part I can’t understand right now is how do you know if the ray crossed a line.

    I thought it would be something like this:

    
    // My Vector class, just for reference.    
    Vector = function(frstcord,sndcord)
    {
        if(frstcord && sndcord)
        {
        var xcord = sndcord.x - frstcord.x;
        var ycord = sndcord.y - frstcord.y;
        var startCord = frstcord;
        this.x = xcord;
        this.y = ycord;
        this.startCord = startCord;
        }
        else
        {
            this.x = 0;
            this.y = 0;
        }
    
        this.rotate = function(angle)
        {
    	    var result = new game.Vector();
    	    result.startCord = {x : this.startCord.x, y : this.startCord.y};
    	    result.x = this.x * Math.cos(angle) - this.y * Math.sin(angle); 
            result.y = this.x * Math.sin(angle) + this.y * Math.cos(angle);
    	    return result
        }
        
        this.add = function(vector)
        {
            var result = new game.Vector();
            result.x = this.x + vector.x;
            result.y = this.y + vector.y;
            result.startCord = {x : this.startCord.x, y : this.startCord.y};
            return result;
        }
        this.invert = function()
        {
            var result = new game.Vector();
            result.x = -this.x;
            result.y = -this.y;
            result.startCord = {x : this.startCord.x, y : this.startCord.y};
            return result;
        }
        this.multiply = function(number)
        {
            var result = new game.Vector();
            result.x = this.x * number;
            result.y = this.y * number;
            result.startCord = {x : this.startCord.x, y : this.startCord.y};
            return result;
        }
        this.divide = function(number)
        {
            var result = new game.Vector();
            result.x = this.x * (1 / number);
            result.y = this.y * (1 / number);
            result.startCord = {x : this.startCord.x, y : this.startCord.y};
            return result;
        }
        this.length = function()
        {
            var tamanho = Math.sqrt((this.x * this.x) + (this.y * this.y));
            return tamanho;
        }
        this.perp = function()
        {
            var result = new game.Vector();
            result.x = -this.y;
            result.y = this.x;
            result.startCord = {x : this.startCord.x, y : this.startCord.y};
            return result;
        }
    };
    
    // Create a unit vector representing the line
    var vector = new Vector({x : vertex1.x, y : vertex1.y},{x : vertex2.x, y : vertex2.y});
    var originalLength = vector.length();
    vector = vector.divide(vector.length());
    
    //Array which stores the pixels in the line
    var pointsInEdge = [];
    
    for(x = 0; x < originalLength; x++)
    {
     var point = vector.multiply(x);
     pointsInEdge.push({x : point.startCord.x + point.x, y : point.startCord.y + point.y});
    }
    

    Doing that with each edge, you would have an array with the coordinates of each point in the edges of the polygon, so, when casting your ray you would check if it’s current coordinate corresponds to one of the coordinates on the array.


Log in to reply