Optimize `isTouchingDrawables`?

[DNin01]

Update: See #18 (comment)

---

As you know, TurboWarp is all about speeding up Scratch projects, so when I saw a function, isTouchingDrawables, with this comment...

scratch-render/src/RenderWebGL.js

Lines 1274 to 1275 in dd5d399

	// This is an EXTREMELY brute force collision detector, but it is
	// still faster than asking the GPU to give us the pixels.

...I saw potential for improvement.

If I'm understanding the code right, Scratch checks for collisions between every single pixel to be sure that the sprites appear to be precisely touching each other. This can slow things down a lot when overused.

Instead of colliding individual pixels, combining groups of pixels to form rectangles, as shown in the video below, would reduce the number of regions that need to be accounted for, increasing performance in the long run.

optimized.touching.detector.webm

Some projects may see performance improvements of over 10x or even 50x in circumstances that would normally cause lag spikes.

@GarboMuffin

[DNin01]

Well, my video doesn't exactly demonstrate how Scratch's touching detection works, but it probably gives you an idea of what we're dealing with here.

[DNin01]

It looks like Scratch scans the region encompassing all touching candidates—the sprites (including clones) that need to be checked.

1. It defines a rectangular area that is the unity of the bounds of all candidates.
2. It scans every pixel in that area. If both the base sprite and at least one candidate overlap a scanned pixel, the touching check passes.

union.touching.detector.webm

I may still be wrong about that, but just scanning bounding box intersections between the base sprite and the candidates without using unities might be faster.

intersect.touching.detector.webm

[GarboMuffin]

it works like your last video