Thoughts about how to do Scratch-style collision detection?

I'm playing around with making an educational programming environment for kids coming from Scratch. So I'd like to recreate the semantics of that environment as much as possible.

Most of it is pretty easy... except for collision detection. Scratch has basically three collision check methods:

1. if touching <sprite>: checks whether any non-transparent pixel of this sprite is touching any non-transparent pixel of another sprite. But both sprites can be arbitrarily scaled and rotated.
2. if touching <color>: checks whether any non-transparent pixel of this sprite is touching a pixel of the specified color, whether that is in the background or from some other sprite.
3. if color <color1> is touching <color2>: checks whether there is any pixel of this sprite of color color1 that is touching the given color2 (in the background or from some other sprite), or vice versa.

None of these would be too difficult if sprites weren't rotated and scaled... but since they are, I'm at a bit of a loss as to how to implement them in any reasonably performant way.

Maybe we actually make a pixel buffer the size of the screen (or, perhaps, some bounding area around the sprite), draw the background and any other sprites in the area into it, and then draw our sprite with a custom shader that checks the contents of the pixel buffer as it draws? But how would we get the result of this test back out to the main code?

Or maybe there's a better approach I'm overlooking?

 

I did a pixel collision a while back and as far as I recall, it should handle rotation - but I did not care about scale, so that would need some adjustment. I implemented this over a tile map (background - also sprites) and cars (other sprites).

It basically goes like this
- find intercepting box of sprite textures (coordinate + bounds based)
- read textures of intercepting box + compare pixel colors
- i guess for scale one would need to read the pixels multiple times - but how to deal with antialias, etc. ?
- how many objects are you talking about? not sure if this is better done on GPU or CPU

 

Yeah, it's really the scaling that makes this hard. There is no antialiasing, but a sprite could be scaled up or down arbitrarily — turning a pixel into an arbitrary (non-axis-aligned) square of color, or (if scaling down) mixing several pixels down into one.

As for how many objects, it's hard to say... most Scratch projects probably have no more than 100 or so sprites, because that's about all it can handle. Typical projects have much fewer. And of course you would always do AABB tests to filter out all the sprites that couldn't possibly be involved in the collision check.

 

Thinking about it a bit more... I've noticed that the "touching color" test only checks the topmost color (excluding the sprite that's doing the test). So it really seems like drawing into a buffer is the way to go, for all three cases:

1. if touching <sprite>: start with an empty buffer; draw the other sprite; then draw this sprite, and if at any point the pixel we're about to draw over is nonempty, return true.
   
2. if touching <color>: draw the background and all relevant sprites into the buffer; then draw this sprite, and if at any point the pixel we're about to draw over is the specified color, return true.
   
3. if color <color1> is touching <color2>: draw the background and all relevant sprites into the buffer; then draw this sprite, and if at any point the pixel we're over and the color we're about to draw match color1 and color2, return true.

But how would I actually do that in Unity, short of writing my own rasterizer? I feel like it's something I ought to be able to do with a custom shader or camera or something. But it's got to be able to return a value (and perhaps even bail out early when it finds a hit). How do you do that?

 

Let me see if I can find something later...I kind of know that I will find the version without rotation because I used it in a prototype. The one with rotation I think aligned one sprite by axis and then looked for the intersection box, so for that sprite you have to use a transparent texture and then determine which positions are read from the sprite texture.

The actual collision detection is
- calculate interception box (use i.e. sprite SpriteRenderer.bounds - this should also work for scaling but the trick is later how to read the pixels from the sprite texture)
- Color[] sprite1 = GetPixels (interception box)
- Color[] sprite2 = GetPixels (interception box) // or an algorithm that creates this in case the sprite is not axis aligned
- for (int i = 0; i < sprite1.Length; i++)
- if (sprite1.a !=0 && sprite2.a !=0) return true

edit: not sure why but it is not taking [ i ] after sprite1 and sprite 2 in the loop

 

Don't worry about the [ i ]... that's the local markup for italics, so yeah, it causes some grief.

But anyway, I totally get what you're doing there, but I don't think it's going to work in the case of scaled/rotated sprites, at least not in any simple manner. It also doesn't really handle the "touching color" case which is very commonly used.

As this has been rolling around in my head all morning, I'm starting to lean towards this approach:

• make a RenderTexture the size of our sprite renderer bounds, and draw either the other sprite of interest, or the background plus all other sprites into it
• make another RenderTexture of the same size, and draw our sprite into it
• iterate over the pixels of these two textures, comparing them appropriately

It's that last step that makes me cringe -- Scratch programmers often use very large sprites, so we would be potentially be looping (in C#) over thousands of pixels.

On the other hand, once we've got it to that point, it is what my wife calls an "embarrassingly parallel" problem; every pair of pixels can be checked independent of the others. So it ought to be ideal for putting on the GPU. Especially if we can keep the render textures there (where presumably they were just rendered to), rather than moving them to main memory. That level of GPU shenanigans is will outside my experience base... but I suppose that's part of the fun!

 

- I guess I do not understand the touching color case (I assume the background is a sprite / texture) so in my understanding it’s the same as sprite - sprite
- yes, render textures simplify the rotation/scale handling but would you not need one for each collision pair? If you fill one up with all other items, you could determine if there was a collision but not with what? (It feels like you would be back to the approach I outlined above, but instead of manually calculating the texture / color array you use the renderer)
- gpu would be interesting in particular since unity opened up this interface - it’s just something I am not experienced in and I also wonder how to get back the collision entities

Would be great if you could update this post with your findings, it’s a topic that interests me in general (i started programming on c64, where you had hardware support for this)

 

OK, here's what I've come up with... just hacked out, still needs cleaned up, etc... but it works.

Code (CSharp):

1.     public bool IsTouchingColor(Color32 targetColor, int tolerance=4) {
2.         SpriteRenderer rend = GetComponent<SpriteRenderer>();
3.         Bounds bounds = rend.bounds;
4.        
5.         RenderTexture rtex;
6.         if (debugRendTex != null) rtex = debugRendTex;
7.         else rtex = RenderTexture.GetTemporary(
8.             Mathf.CeilToInt(bounds.extents.x*2),
9.             Mathf.CeilToInt(bounds.extents.y*2),
10.             16,         // do we actually need a depth buffer?!
11.             RenderTextureFormat.ARGB32);
12.        
13.         testCamera.CopyFrom(Camera.main);
14.        
15.         Vector3 pos = transform.position;
16.         pos.z = testCamera.transform.position.z;
17.         testCamera.transform.position = pos;
18.        
19.         testCamera.aspect = (float)rtex.width / rtex.height;
20.         testCamera.orthographicSize = rtex.height/2;
21.        
22.         testCamera.targetTexture = rtex;
23.         testCamera.cullingMask &= ~LayerMask.GetMask("CollisionTestSubject");
24.            
25.         // disable this object, and render everything else
26.         int origLayer = gameObject.layer;
27.         gameObject.layer = LayerMask.NameToLayer("CollisionTestSubject");
28.         testCamera.Render();
29.        
30.         // Copy the rendering into something we can access
31.         Texture2D tex = new Texture2D(rtex.width, rtex.height, TextureFormat.ARGB32, false);
32.         RenderTexture.active = rtex;
33.         tex.ReadPixels(new Rect(0, 0, rtex.width, rtex.height), 0, 0, false);
34.         RenderTexture.active = null;
35.                
36.         Color32[] targetPixels = tex.GetPixels32();
37.        
38.         // Now, render again with just our own sprite.
39.         testCamera.cullingMask = ~testCamera.cullingMask;
40.         testCamera.Render();
41.         RenderTexture.active = rtex;
42.         tex.ReadPixels(new Rect(0, 0, rtex.width, rtex.height), 0, 0, false);
43.         RenderTexture.active = null;
44.        
45.         Color32[] selfPixels = tex.GetPixels32();    
46.        
47.         // Check now for where we are touching the target color.
48.         bool result = false;
49.         int count = selfPixels.Length;
50.        
51.         for (int i=0; i<count; i++) {
52.             if (selfPixels[i].a < 255) continue;    // not our pixel
53.             Color32 c = targetPixels[i];
54.             if (c.a < 255) continue;                // not a target pixel (nothing rendered here)
55.            
56.             // check for hitting target color
57.             if (c.r == targetColor.r && c.b == targetColor.b && c.g == targetColor.g && c.a == targetColor.a) {
58.                 result = true;
59.                 break;
60.             }
61.            
62.             if (tolerance > 0) {
63.                 // OK, let's check for *almost* hitting the target color.
64.                 int d = 0;        // manhattan distance
65.                 d += (c.r > targetColor.r ? c.r - targetColor.r : targetColor.r - c.r);
66.                 d += (c.g > targetColor.g ? c.g - targetColor.g : targetColor.g - c.g);
67.                 d += (c.b > targetColor.b ? c.b - targetColor.b : targetColor.b - c.b);
68.                 if (d < tolerance) {
69.                     result = true;
70.                     break;
71.                 }
72.             }
73.         }
74.        
75.         gameObject.layer = origLayer;
76.        
77.         return result;
78.     }

 

Cool - I will look at this tomorrow, I will also try to dig out my old version.

- did you check performance?
- this algorithm is not being able to say who was the collision partner, just that a pixel of color is being touched - is this enough?

 

No. I expect it to be rather poor, but I don't see how to improve it (short of delving into arcane GPU coding, which I'd like to do sometime, but not today).

Yes, that's all Scratch provides, and it's what that user base expects. There will be a separate function for testing against a specific other sprite, though.

 

Did not have time today but I found my old project, it has pixel collision between two sprites and works with rotated sprites. The script is messy though and needs some cleaning...overall it seems straight forward...
- step1: box collision (rotated bounding boxes)
- step2: pixel collision (walk through each pixel of sprite1 until collision detected, translate local coordinate of sprite1 pixel to local pixel coordinate of sprite2, compare colors)
- i see also various optimizations like caching the sprite textures + i left some notes in the script for unimplemented ideas

Let me know if this could interest you...and I will try to find some time this week to put this into something that is sharable. Looks to me like a pretty fast system, no need for GPU

 

No, I don't think that's useful in my case because scaled sprites make that approach unworkable. Thank you though.

 

I looked into it today and it was quite easy to make it work with scaled sprites as well...
- well kind of...it's not 100% perfect...it can miss pixels if it transforms between differently scaled sprites (it will work in most cases but say at scale 3 of source texture and scale 1 of hit texture, it will walk through hit texture in 3 pixel steps)
- i think the only way to fix this is to define the overlap box of the rotated sprites in world space and then step through the corresponding pixels of both textures (which at worst case rotation is double the amount of pixels to check * scale)

I hate my fascination to this retro stuff but I can't help it, grew up with it. I might work on the pixel collision and check how performant it is. I sometimes wonder if there would be a wider interest for an integrated retro toolkit, things like
- pixel perfect setup
- pixel collision (a full fledged solution, with scaled & rotated, brute-force vs. special contact points, color vs transparency, etc.)
- screen wrap with physics support
- mod / tracker support (recall the other thread you started)
- crt shader
- old school effects like tech-tech, raster-bars, scroll-texts, etc.

 

The approach with the overlap box works...
- very simple script, needs speed optimization now (I have a number of ideas)
- needs a thought on how to deal with "between pixel positions" for rotated sprites (sub pixel overlaps / gaps - false detections)
- I promise myself to finally look into the exact pixel mapping / rendering of Unity - there is a potential 0.5 pixel offset that I want to look into

 

@JoeStrout

Did you ever profile your pixel collision method? I wonder what results you are getting.

My one is cleaned up now but still has some room for improvement, it's less performant than one would wish. I have to look at it again and see if I missed something, but by the looks of it your are restricted to small sprites. 50 collision checks between 64x64 pixel sprites take about 6-7 ms on my Mac in the worst case (box collision but no pixel collision, so 50x64x64 checks). Will need to check mobile + also look at the performance of my old routine that only does axis aligned (i think it's much faster).

edit: i wish i had more knowledge with gpu stuff to test something like this with GPU support.

 

I haven't profiled it — but my intuition is that for what I'm trying to do, there's no way iterating and checking pixels (especially if done accurately with arbitrary scaling & rotation) is going to come close.

Keep in mind that what we're testing for here is touching a particular color, and that color could come from the background, the drawing layer (e.g. in a light-cycles game, what you collide with is the trail drawn by the sprites as they move around), or any other sprite — but only the topmost sprite at any point. It's goofy, I know, but it's how Scratch works, and it's actually very powerful and easy to use, at least for some things. (You should spend an afternoon playing with Scratch sometime, if you haven't yet. It's good fun.)

So, I think there's no good substitute for the rendering approach. This ensures that what you're testing matches what the user sees, and lets the graphics hardware do most of the heavy lifting. It's just the final stage where we have to iterate over the pixels that's slow... but even that is still pretty fast, because we just do GetPixels32, and zip right along the array. No actual computations are needed at that point.

So the bottleneck, I suspect, is in transferring the render texture to main memory. If we could do compare the two render textures on the GPU, then that'd go away too. I suspect that's possible, but like you, I don't have enough levels in GPU wizardry to take on that monster yet. Maybe someday.

 

Hi there, I don't have time today but will look at your function on the weekend. I am curious as to the performance.
- in your approach you have to readpixels every frame but given the camera support the collision check is somewhat simple
- in my approach, I only read the texture at start and therefore have a somewhat more complicated collision check - I can also test any color (i just use transparency but it could be any color)

This is how i run the speed test I use 50 iterations - in my case I use a 1024x1024 background texture and a 64x64 collision texture that bounds overlap but no pixel overlaps

Spoiler

Code (CSharp):

1.     void Update ()
2.     {
3.         sw.Start();
4.         for (int i = 0; i < iterations; i++)
5.         {
6.             goIndicator.SetActive(CollisionExtension.PixelCollision(rendA, colorsA, rendB, colorsB, 1f));
7.         }
8.         sw.Stop();
9.         text.text = (sw.ElapsedMilliseconds + " ms for " + iterations);
10.         sw.Reset();
11.     }

 

@JoeStrout

I am a little short of time these days...just looked at the profiler and optimized the expensive loop through the colors. Replaced a function call & changed Vector2 into floats. I now get in the worst case scenario with 64x64 pixels 200 collision checks in 8-9ms on my Mac (820,000 pixels at 8-9ms vs. 200,000 pixels at 6-7ms). It also does not allocate. I think the few performance optimizations I have left are pretty much neglectable now and I will leave it there...that was a fun little experiment.

I still want to check out your approach on the weekend, I like the idea of it very much. Is the code above your latest version? I doubt that it is in general faster than my approach, but they do different things and have different use cases. It might be even possible to blend them...

 

Yes, the above is the latest.

When comparing, be sure to include a case where there are a half-dozen sprites overlapping, and the color we're looking for is actually in the background. I know it sounds crazy but this is actually a very common situation in Scratch projects.

 

Hi there...

I tested your code (not very thoroughly)

My findings are:
- it works well!
- it allocates quite a bit
- its key bottleneck like you said is readpixels

I think there is no point in benchmarking the two approaches against each other because they do different things.

• Your approach: useful for object to background collision (not able to identify collision target, using finally rendered pixels)
• My approach: useful for object to object collision (identifying collision targets, using original textures)
• Only the special case of a static background (i.e. no shader effects, particles, other visual effects) is covered by my approach.

Ideas

• My approach: pretty much out of ideas how to improve the collision loop for the worst case (bounds overlap but no pixel collision), I have a note in there on how to possibly optimize a collision scenario
• Your approach: it would be very interesting if there is a way to speed up readpixels that works for all platforms, i googled and came across glreadpixels....is this something you want to look at?
• GPU approach: this should be somehow possible, the question possible is, if there is a frame delay in getting the results back and how much that delay is. Is it platform depended? How to implement it?

Spoiler: per pixel loop

Code (CSharp):

1.             // loop through each pixel position within the intersectBounds
2.             // to-do: likely less comparisons requried if walking through texture from outside to inside (i.e. shrinking border) - depends on textures and collision depth
3.             for (int pixelRow = 0; pixelRow <= pixelRows; pixelRow++)
4.             {
5.                 // set texture position to beginning of each pixel row
6.                 float texPosxA = texPosStartXA;
7.                 float texPosyA = texPosStartYA;
8.                 float texPosxB = texPosStartXB;
9.                 float texPosyB = texPosStartYB;
10.                 for (int pixelColumn = 0; pixelColumn <= pixelColumns; pixelColumn++)
11.                 {
12.                     // round texture positions to next pixel
13.                     int xA = (int) (texPosxA + 0.5f);
14.                     int yA = (int) (texPosyA + 0.5f);
15.                     int xB = (int) (texPosxB + 0.5f);
16.                     int yB = (int) (texPosyB + 0.5f);
17.  
18.                     // check if calculated texture position is within the sprite texture of both collision textures
19.                     if (0 <= xA && xA < textureWidthA && 0 <= yA && yA < textureHeightA && 0 <= xB && xB < textureWidthB && 0 <= yB && yB < textureHeightB)
20.                     {
21.                         if (colorsA[xA + yA * textureWidthA].a != 0)
22.                         {
23.                             if (colorsB[xB + yB * textureWidthB].a != 0)
24.                             {
25.                                 return true;
26.                             }
27.                         }
28.                     }
29.  
30.                     // apply world x-step to texture x-step
31.                     texPosxA += texStepXA.x;
32.                     texPosyA += texStepXA.y;
33.                     texPosxB += texStepXB.x;
34.                     texPosyB += texStepXB.y;
35.                 }
36.                 // apply world y-step to texture y-step
37.                 texPosStartYA += texStepYA.x;
38.                 texPosStartYA += texStepYA.y;
39.                 texPosStartXB += texStepYB.x;
40.                 texPosStartYB += texStepYB.y;
41.             }

 

We can probably reduce the allocations by recycling some things such as the temp texture. But yeah, it's that ReadPixels... I hadn't heard of glreadpixels before, so that's definitely something I want to look into!

Thanks,
- Joe

 

Cool - I am interested in this as well. Here are the bookmarks I saved when I googled...I might look into this myself, but not before next weekend. In case you try this earlier, it would be great if you could ping me with the results.

https://answers.unity.com/questions/1305191/glreadpixels-from-a-rendertexture.html
-> there is a comment at the bottom that says you can point it directly to a float array, this would be cool because you can then skip both readpixels & getpixels32

https://answers.unity.com/questions/1249679/glreadpixels-in-native-plugin-shows-different-resu.html

 

Ah, it looks like that's something for use in a native plugin. I prefer to keep this code in C# land, at least for now.

 

I downloaded 2018 yesterday and tried:
- IL2CPP on Mac
- Threading & Job System

Results for 200 collision pairs in worst case (200 simultaneous box collisions with no overlapping pixels in a 256x256 sprite bitmap):
- 2017.3.0p4 (mono): approx. 115ms
- 2018.1.0b8 (mono): approx. 115ms
- 2018.1.0b8 (IL2CPP): approx. 45ms
- 2018.1.0b8 (IL2CPP, C-Jobs): need to do again (was worse at 80ms)
- 2018.1.0b8 (IL2CPP, Threads): 11ms

NOTE: in the last test I realized that I forgot to rotate the sprites to really account for the worst-worst case across the board in above figures. It worsens the result in the last case to about 19ms (256x256 source texture but rotated by 45 -> doubles the collision area)

It's the first time I work with Threads / C Job System and it's quite hacked together...i have to do this properly in the next couple of days, cleaning up some mess I created like allocating lists, debug code, etc --- I also need to understand all features like abort conditions that could come in handy.... I also have no clue how portable this is to other platforms and how it performs there...

 

I just tried out C-Jobs with burst...this seems to have potential --- at the moment no build support though.

2018.0.1f1

• Editor, Threads: 50ms (this was the 11ms in build above)
• Editor, IJob: 122ms
• Editor, IJob, Burst: 13ms

I still have to get my head around IJobParallelForBatch, which could help speed things further up.