8 Replies Latest reply on May 22, 2008 10:14 AM by Rothrock

    Finding Edges

    Rothrock Level 5
      I'm trying to approximate the edges of a arbitrarily shaped movie clip using Flash 7. These shapes are not compound, but they could be a little complex.

      My idea was to "place" some points around the bounding box of the clip and then "move" each point on a line through the center until it hitTested on the shape. This works well enough for shapes like a circle or square, but not so well if there are recessed areas in the shape -- imagine the inside of a "G".

      You can use the code below to see what I mean. Paste it on the first frame and make sure to have your shape (of a decent size, maybe around 100 to 200 pixels in either direction) on the stage with an instance name of "clip" and have a small round dot in the library set to export with the linkage id of "dot".

      I'm just wondering if anybody has any interesting ideas on other approaches or how I could do this. Remember that I don't have the BitmapData class. Thanks.
        • 1. Finding Edges
          Greg Dove Level 4
          The only other way I can think to do it is again to use the coordinate type hitTest... and do 'radar' style scan lines within the bounding box with coord hitTests.
          So that would be something like a loop that performs sweep checks at a certain angle precision and each of those 'checks' would be a loop that does hitTesting for coordinates in a straight line extending away from a point at the sweep angle to determine the boundary(ies) in that specific direction. This could be quite CPU intensive I think. I guess you could do it from one location inside the bounding box, but in terms of precision it would perhaps be possible/easier to 'map' shapes this way by performing the sweep analysis in parallel from each corner of the bounding box looking for changes in hitTest coords results that would give a set of edge points. To map the cut-out areas e.g. inside the G will be easier this way I think, but still far from trivial.
          • 2. Re: Finding Edges
            kglad Adobe Community Professional & MVP
            actually, i think the most computationally efficient method for a general shape is going to be a monte carlo method. (the proof is left to the reader.)

            some additional efficiencies can be introduced if you know something about the shape. for example, if you know the shape occupies more than 1/2 the area of the bounding box, you should compute the negative of the shape:

            • 3. Re: Finding Edges
              clbeech Level 3
              lol - dang it!!! kglad you're just too fast!

              I had been thinking similarly, but i don't have a fancy name for it... PHA HA!! ( jk - kg ;) it had occurred to me that since pixels are grid based that one could determine if a coordinate position is on the edge by testing the eight surrounding poistions - if any return false (after a shape hit is determined) then that pixel is a edge location.

              I used this generic-no-namebrand method (sample fla
              HERE ):
              • 4. Re: Finding Edges
                kglad Adobe Community Professional & MVP
                if you're trying to find exact edges (as opposed to approximating those edges), checking the surrounding pixels is mandatory. but then you need to check all pixels in the bounding rectangle (like you're doing) and that's computationally intensive.

                i did just that when i made an as2 shape tween (kglad.com/snippets/shape tween) and you can see it takes a few seconds for the tween to get started as it's running through the first round of calculations.
                • 5. Re: Finding Edges
                  clbeech Level 3
                  for sure kg - totally intensive system in mine above. took me a bit really to understand what you had there - finally got it though, LOL!!

                  was thinking that it would be nice to be able to read the vector control points and simply 'redraw' the exterior shape - wonder why we can't access that kind of thing readily - that would be quite handy for a lot of things, like shape tweening for instance or adjusting guided tween paths.
                  • 6. Re: Finding Edges
                    Rothrock Level 5
                    I've been playing with this a bit and it is interesting. For convoluted shapes this works much better, but for nearly regular shapes (almost circles, almost squares -- maybe with rounded corners) it takes too many points to be sure you have good coverage.

                    This isn't a high precision need, so some slop is fine and I think I have plenty of directions to explore. I agree the big secret is to know something about the types of shapes I will be using.

                    Thank for all your support and ideas!
                    • 7. Re: Finding Edges
                      kglad Adobe Community Professional & MVP
                      for regular shapes compute the negative of the image.
                      • 8. Re: Finding Edges
                        Rothrock Level 5
                        Okay, I'm taking this a bit further. I've come across the marching squares algorithm and trying to use it. So far it is working great.

                        So here is what I'm doing. I've got an arbitrary black shape in a movieclip.

                        I start checking a four pixels square (x,y) and (x+1,y+1) define the corners, for hits. The pattern of the hits define one of 16 patterns for that square. As long as there are no hits we move along to the right until we find at least one pixel that is a hit.

                        The one pixel means we have found the edge of the shape. Pushing the x,y coordinates of the marching square into an array that will define the edges of the shape. From there we move clockwise around the edge of the shape testing and moving appropriately until we come back to the start.

                        It actually works quite well.

                        So here is my next question. What if my shape is compound? So inside the same clip there are two shapes. I'm trying to figure out how to keep checking for more shapes. So for example if my shape is a lower case letter "i." I will nicely trace out the dot over the i, but then it is done.

                        Any suggestions on how to get it to find the lower part?

                        I'm thinking of picking up the first bit of testing again while somehow keeping track of which bits of grid I've visited and not testing those again. But I'm not sure how one would go about doing that -- especially quickly. Any ideas?