Java-Gaming.org Hi !
Featured games (81)
games approved by the League of Dukes
Games in Showcase (513)
Games in Android Showcase (119)
games submitted by our members
Games in WIP (576)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Algorithms for Image Shapes  (Read 1138 times)
0 Members and 1 Guest are viewing this topic.
Offline Troncoso

JGO Coder


Medals: 20



« Posted 2013-04-18 04:39:47 »

I'm exploring the idea of converting images into bounding shapes, using a transparency color (or alpha for png's), as a method for doing pixel perfect collision.

Of course, this can quickly turn into a CPU taxing problem. I could just hit every pixel, and add all non-transparent ones to a polygon. But, that's far too many points, and it's just a slow process to go through every pixel in an image.

Another though would be to check every pixel, but only add the bordering pixels to create an outline. This reduces the point count, but is still checking every pixel.

A third thought was scanning until I found the first non-transparent pixel, as this would definitely be on an edge, and then only checking pixels around it for other border pixels, And just making my way around the image. I could use a scalar to reduce the number of points actually added.

Finally, my question is if this is an accepted approach to pixel perfect collision. Or, do people generally just use the pixel colors directly to check for overlap?
Offline relminator
« Reply #1 - Posted 2013-04-18 05:10:25 »

What I did about 10 years ago was to upload all image data as a single color in an 8 bit array with with the first and second elements as width and height.

Then at runtime scan all overlapping pixels (scans only the overlapping bounding boxes and not the whole box) by "clipping" one sprite to the other.  Fast enough on a 486DX 66mhz but that's DOS and I did it in x86 ASM.

Here's a more recent version (still old) using inline x86 ASM.

http://rel.phatcode.net/index.php?action=contents&item=FJ-RX

Try "replay" mode to see an auto-game.
Offline pjt33
« Reply #2 - Posted 2013-04-18 06:51:50 »

If you want something faster than a full scan of the bounding box, it seems to me that the best way to do it is likely to be runlength-encoding the alpha channel as a pre-processing step. If your shapes are convex then you only need to store 3 numbers per row, and the overlap check would be two comparisons.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Online philfrei
« Reply #3 - Posted 2013-04-18 08:41:38 »

I don't fully understand the question, and may be clueless as to what you are asking, but when you write: "Or, do people generally just use the pixel colors directly to check for overlap?" it gets me wondering, why make colors serve two purposes? Will you be putting constraints on future graphics decisions if the color data is being used for collision checking?

A second array, representing each pixel location of the screen is not that large. Fill it with bytes that are pointers to the objects occupying the space, instead of colors. I did this on a kind of loony experiment where I had about 500 threads going, each at its own sleep loop, and all the objects checking against this representation for collisions. It worked. The "interesting" concurrency issues can be avoided by moving all objects in turn rather than having them in independent loops, which should make it even more performant.

It is a little cumbersome to set up, but it scales linearly Shocked as you add more objects for collision checking. A crazy idea perhaps, but I'd like to go back to it and explore some more, look for possible optimizations.

"It's after the end of the world! Don't you know that yet?"
Online SHC
« Reply #4 - Posted 2013-04-18 08:56:03 »

Found this.
http://www.gamedev.net/topic/632646-simplifying-dynamic-2d-bounding/#post_id_5053404

I had reposted the source since it's not visible.

Offline Troncoso

JGO Coder


Medals: 20



« Reply #5 - Posted 2013-04-18 14:59:02 »

The thought on using the pixel colors for the actual collision checking was just a query about the more excepted method of achieving pixel perfect collision. Doing some research, there isn't all that much information on the topic, and there really isn't a consensus on an accepted method for it.

To me, using the pixels to test for overlap doesn't seem efficient at all. That's why I'm opting for building a polygon to represent the non-transparent pixels of the image. Though, scanning through every single pixel and adding all non-transparent pixels to the polygon is also very cumbersome. So, if I can develop a method of collecting just the bordering pixels of the image, or something like that, maybe this would be efficient enough to be practical. Maybe adding an options for an offset, so that it only gets every other border pixel, or so.

SHC's link seems to be something like what I'm looking for. I'll mess with that and see if it proves useful.
Offline Troncoso

JGO Coder


Medals: 20



« Reply #6 - Posted 2013-04-19 01:36:34 »

Just thought I'd update this with my findings:

I was able to write a method that created a shape from the outline of an image. Here are a couple screen shots:





The method to create this has a parameter for "precision", which basically just means it only adds a point to the polygon once every x number of pixel hits. So, for a precision of 2, every second border pixel is added to the polygon. There is also a parameter for the value of the alpha to check against.
For this image the time to create the shape was:

Image size: 384x384
Precision   Time (in ms)
--------    ----
    1           87
    2           66
    4           55
    8           42
    16         33

These are all on separate run times, so there is no optimization between each. The image above uses a precision of 2. One part of my algorithm that I know plays a big part in the creation time is converting the image to an array of Pix (inner class). I do this for convenience, so I'm sure by just accessing the image pixels directly, that time can be lowered more.

A couple limitations I haven't fixed:
If there is an edge of the non-transparent pixels on any border of the whole image, an out of bounds exception occurs.

It doesn't account for transparent pixels within the non-transparent pixels.

So, anyway, that's what I've found that I think will suite my needs. I'm sure there is still a better way to do this, but I'm satisfied. Here is the pastebin link http://pastebin.com/Wvatq5Bk. It is in the form of a singleton class. When you create a shape, you also pass in a name, so that you can access the shape again without having to re-create it. It's done this way for personal need. Also, this was done using the Slick2D Image, Shape, and Polygon classes. I'm sure converting it to Java2D would require minimal changes. Further more, it's written to quit the program if the user tries to use an image that isn't a png.
Feel free to use the code, abuse it, criticize, or whatever. Hopefully this helps someone.

Update: Redid method to cut out all the code duplication, and fixed typo indicated by SHC.
Online SHC
« Reply #7 - Posted 2013-04-19 04:35:30 »

Found one typo in code.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
private class Pix
{
    public int r;
    public int g;
    public int b;
    public int a;
 
    public boolean checked;
 
    public Pix(Color c)
    {
        r = c.getRed();
-       g = c.getBlue();
+       g = c.getGreen();
        b = c.getBlue();
        a = c.getAlpha();
        checked = false;
    }
}

Offline Troncoso

JGO Coder


Medals: 20



« Reply #8 - Posted 2013-04-19 06:00:56 »

Oh man. Thanks for that. Haha. The color fields in Pix are for another version of this method that uses a specific color as the transparent color, which I haven't implemented yet, so I haven't used those fields to realize it was typed wrong.
Offline Danny02
« Reply #9 - Posted 2013-04-19 06:44:44 »

for all interested take a look at this particle trimmer
http://www.humus.name/index.php?page=Cool&ID=8
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Longarmx (38 views)
2014-10-17 03:59:02

Norakomi (28 views)
2014-10-16 15:22:06

Norakomi (24 views)
2014-10-16 15:20:20

lcass (28 views)
2014-10-15 16:18:58

TehJavaDev (53 views)
2014-10-14 00:39:48

TehJavaDev (54 views)
2014-10-14 00:35:47

TehJavaDev (42 views)
2014-10-14 00:32:37

BurntPizza (64 views)
2014-10-11 23:24:42

BurntPizza (36 views)
2014-10-11 23:10:45

BurntPizza (78 views)
2014-10-11 22:30:10
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!