Suggestion: Per Pixel Collision

[guFalcon]

I used the MonoGame.Extended demo project named 'Demo.Sprites' as a baseline and went from there. So here it is: 2D per-pixel collision testing with translation, scale and rotation.

PerPixelCollision

Should be straightforward to incorporate into MG.Extended. Suggestions welcome (API look&feel, helper data-structures, maybe hold the collision-data in the sprite, etc...)

[craftworkgames]

We've had requests for per pixel collision before. It looks like you've put a lot of effort into this which is great.

I do wonder about the usefulness of PPC though since there's a pretty heavy performance penalty. I'm sure it's useful in some games but in my experience, simple shape based collision detection is more than enough.

It think we could incorporate this into the library somehow, but I'd be careful to make sure people understand that it should only be used with careful consideration.

[guFalcon]

Yeah. I think you're right. That's why I have the CollisionGrid as well. But all in all the performance isn't so bad at all. My engine does this check all the time but I don't have hard numbers on that.

Shall I branch MG.Ext and try to place my code into your class-structure?

[craftworkgames]

Shall I branch MG.Ext and try to place my code into your class-structure?

You can if you want. To be honest I'm feeling a little overwhelmed by all the stuff going on in the project at the moment. It all feels a little unstructured and chaotic.

I'd like to sit down and really think about the overall vision of MonoGame.Extended. In my mind it's always intended to be something along the lines of LibGDX but I sometimes wonder which direction we are really heading. Maybe it's time to put a well defined API plan in place.

[guFalcon]

Hmmm. I understand and frankly, I see the same thing in my game-code.

I don't think that the problem is the large amount of features; I think you could keep them separated quite well if you put some emphasis on that concept, like you've said before (or something along the lines): "MonoGame.Extended shouldn't be an all-in-one solution. It's purpose is to offer various strategies and small frameworks which you may use or not." So that should probably go into the vision of this project (maybe re-phrase it ;) )

The points I see problems arising are the 'glue' objects of such frameworks, like for instance the Sprite class. Even in my game it's a huge mess containing far too many concepts and fields, partly because of laziness, partly because of performance reasons. So you should probably keep an eye on those constructs. (Maybe there's a general solution for that like object-composition).

As long as we keep the rest small, nice and separated, I really don't see a problem.

[lithiumtoast]

@guFalcon Per pixel collision would be a Narrowphase collision algorithm. It's an expensive technique that can take quite a few CPU cycles when looping through each pixel of a texture's copied data. The worst case is that the all or the majority of pixels are transparent and the algorithm has to power through the array every frame to find if there is a collision. That being said, it could be very useful in certain scenarios, but often enough a convex polygon is adequate for a collision detection and even necessary in certain scenarios. Per pixel collision also it makes it difficult to figure out the collision response for physics.

public static Matrix GetTransformationMatrix(Vector2 position, Vector2 origin, Vector2 scale, float rotation)
        {
            Matrix result = Matrix.Identity;
            result *= Matrix.CreateTranslation(-origin.X, -origin.Y, 0f);
            result *= Matrix.CreateScale(new Vector3(scale.X, scale.Y, 1f));
            result *= Matrix.CreateRotationZ(rotation);
            result *= Matrix.CreateTranslation(position.X, position.Y, 0);
            return result;
        }

@guFalcon Re-creating the Matrix every time it is needed is a waste of CPU cycles. I understand in the demo you created it is required since rotation changes every frame for the sprite but the sprite could of easily not changed it's transformation for the frame. The Matrix should be cached somewhere and updated when needed. Matrix is also a very large struct with 16 floats (64 bytes) and should be passed by ref (4 bytes on x86, 8 bytes on x64) instead by value where possible.

[guFalcon]

@LithiumToast I fully understand the consequences of per-pixel-collision-testing. I just use it quite often (compared with other people, obviously) and I find that it really doesn't have any performance impact even when I'm profiling. I always try to do no premature performance optimization. Of course I always narrow down the candidates... Well... Maybe that's the reason... ;)

I think it's a useful addition to a library as MG.Extended. Feel free to write an appropriate warning we can incorporate into the documentation. That would be great.

Another point against it would be that it takes special pre-processing for the Sprite's texture (the .GetData()-part since that has to be done before the level starts or whatever. If it's an animated sprite I'd have to do that for every single picture of the animation frame)

As for the Matrix... Thanks for pointing out the size. That point completely eluded me blushing. I will change that accordingly. In order to know whether to update the matrix or not one would have to cache the former values and compare them or do some sort of change-listener on the values in the sprite... Correct? What would you do? I'd really value your input.

[lithiumtoast]

I find that it really doesn't have any performance impact even when I'm profiling.

@guFalcon On what machine and specs did you profile with? Also did you profile with Debug and Release complies? Did you try mobile platforms? Did you observe running time and memory consumption with different input sizes, like small, medium, large textures and textures with no, some or all transparent pixels?

I think it's a useful addition to a library as MG.Extended.

Yup, some people would probably want to have it. Though I'm a little worried it doesn't provide much benefit compared to simple geometric primitives (rectangles, circles, etc) or separating axis theorem for certain scenarios in a game's collision detection. Can you elaborate on a scenario where pixel collision detection is necessary? Also I just think it would be a waste of memory to have each sprite have a copy of a pixel grid for collision detection. For example, a 100x100 pixel collision grid where each pixel is a byte is 10,000 bytes or 9.7~ kilobytes, a 200x200 pixel collision grid is 39~ kilobytes. Having a pixel collision grid for each texture would be better, but then how does it work with texture atlases? Obviously not the whole texture for the texture atlas needs to be used, but consider if it did. The texture of a texture atlas could easily get really large such as 4196x4196 and would require 16.7~ megabytes for the collision grid.

Writing something for a specific game is different then writing a library which other people will use.

Feel free to write an appropriate warning we can incorporate into the documentation. That would be great.

Unless it finds it's way into the rest of collision code I'm working towards, I'm not going to write documentation for this.

In order to know whether to update the matrix or not one would have to cache the former values and compare them or do some sort of change-listener on the values in the sprite...

Every time any of the variables used to calculate the Matrix are updated a dirty boolean flag could be set indicating that on the next update pass the Matrix needs to be-recalculated.

[guFalcon]

@LithiumToast

On what machine and specs did you profile with?

Yup. You're absolutely right; again.

Can you elaborate on a scenario where pixel collision detection is necessary?

I once had to use it to do collisions with a large texture fading in and out (sort of a chequers-board), but I admit that's a bit of a corner case. Most people would intuitively go for it I suppose. So if there's an equally accurate method, like a separating axis theorem with a automatically generated convex polygon, then I think there won't be any real need for per-pixel-collision. But then again, what do you really need in a game-engine and what is bells'n'whistles... I thought this library should be a collection of useful tools and it should be up to the programmer to choose the ones he/she wants to use.

(I wrote it in order to get the sprite I clicked on in Throbax TD and it's a waste on memory, but I don't rewrite it now because the game is HUGE and there are more pressing things to do. I put it on GitHub because most of the people out there seem to implement it; But they don't seem to get the matrix transformations right. At least not if they're going for the rotation. Read it 10 times out there in the last month.)

a 100x100 pixel collision grid where each pixel is a byte

In my implementation it's a bool[]. But that just mitigates the general problem a bit. Your assessment is correct. Again.

the documentation...

I didn't want to aggravate you; Of course I would write that myself. It was merely a proposal that you could read that comment and change it to something you see fit so that we can be sure that the user of the library gets the right idea about that particular method.

...on the next update pass the Matrix needs to be-recalculated.

Then we're thinking along the same lines here.

A general thing: Please don't get me wrong. If you all decide it's not for MG.Extended then so be it. I'm putting this up here exactly for this reason. For people to argue about if it's fit to become part of the library or not. Just wanna help.

@LithiumToast Thanks for your insight. Really appreciate that. Maybe, when you have some time, you could have a quick look at the CollisionGrid. I'm sure I could profit from your expertise.

[lithiumtoast]

On what machine and specs did you profile with? Yup. You're absolutely right; again.

@guFalcon ??? You didn't answer the question?

If you all decide it's not for MG.Extended then so be it.

Though it's ultimately up to owner @craftworkgames, this is open source coding... If there are scenarios where pixel collision detection could be used in games I'm sure it would be a great addition to the library. I'm just having trouble seeing a game scenario where pixel perfect collision is a better fit than simple geometric shapes or convex polygons.

I once had to use it to do collisions with a large texture fading in and out (sort of a chequers-board)

Couldn't each checker be a rectangle hit box or a circle? I still don't quite see a good reason to use pixel collision.

I wrote it in order to get the sprite I clicked on in Throbax TD and it's a waste on memory, but I don't rewrite it now because the game is HUGE and there are more pressing things to do.

So if you had to re-write it would you use basic shapes for collision on each sprite?

But then again, what do you really need in a game-engine and what is bells'n'whistles... I thought this library should be a collection of useful tools and it should be up to the programmer to choose the ones he/she wants to use.

MonoGame.Extended is not an engine. Though it does have individual pieces of a game engine with some pieces naturally fitting together. For example, texture atlases and pixel collision detection are two separate pieces but a programmer might want to use both together and expect it to just work efficiently somehow. See the existing code for texture atlases.

In my implementation it's a bool[].

Same thing as byte[] as far memory goes.

I didn't want to aggravate you; Of course I would write that myself. It was merely a proposal that you could read that comment and change it to something you see fit so that we can be sure that the user of the library gets the right idea about that particular method.

I'm not aggravated, I'm just saying I don't have the intention to document code that anyone hands over without thinking how it fits with the rest of the code. I don't want my name on the documentation when people get frustrated that it doesn't do what they want 😉

Maybe, when you have some time, you could have a quick look at the CollisionGrid.

I'll take a look sometime, but I'm pretty busy this week.

[guFalcon]

@LithiumToast

??? You didn't answer the question?

Oh. Sorry. Maybe I wasn't clear enough on that one. English is not my first language. When you asked:

Did you try mobile platforms? Did you observe running time and memory consumption with different input sizes, like small, medium, large textures and textures with no, some or all transparent pixels?

I had to acknowledge that this framework extension has many target platforms I initially didn't think about and that I always use it in a 'smart' way (small, cropped textures or very few checks) and that's what I was trying to tell you. That I got your point.

the bool[]

Right again. Thanks.

documentation and your name...

I perfectly understand that. np

CollisionGrid...

Take your time, I would really appreciate it.

So I take it that we don't want it in MonoGame (which, as I said before, is perfectly fine with me, especially as there is obviously a much cooler implementation coming up using convex polygons, which I'm really looking forward to).

[craftworkgames]

If there are scenarios where pixel collision detection could be used in games I'm sure it would be a great addition to the library. I'm just having trouble seeing a game scenario where pixel perfect collision is a better fit than simple geometric shapes or convex polygons.

This pretty much sums up my feelings on this. If there's a legitimate reason to add it to the library then we'll do it. In my experience, simple geometric shapes are a better fit for most games. There's obviously going to be exceptions to the rule. No doubt it's got some usefulness.

The thing is, there's no lack of feature requests for the library. This one probably doesn't come at the top of the list. My job is to figure out how we are going to incorporate the features in a controlled way. What has worked in the past isn't really working now. What we really need to do is come up with a plan for how to manage all these incoming requests.

[guFalcon]

Yup. Alright. NP. Learned something today... again ;) Will hold a reference to this thread for future discussions about PPC elsewhere :D Thanks @LithiumToast for your patience on this one.