[Feat] CollideExtension

[felixpalmer]

Target Use Case

When a layer(s) is rendered with many dense features, the features will overlap, which results in a cluttered visualization.

This is especially a problem with text labels, but applies in general with other layers like the ScatterplotLayer:

There is a solution for the label case in this demo, however it is implemented on the CPU and doesn't support rotating or tilting the camera. https://github.com/visgl/deck.gl/issues/6417 is also relevant for background.

Inspired by the approach taken with the MaskExtension, the CollideExtension would allow a layer to be rendered with a new operation, OPERATION.COLLIDE, so that overlapping features would be hidden, with only the frontmost features being visible.

Proposal

To perform the collision detection, a Layer is created with the OPERATION.COLLIDE and then also rendered normally. This allows the collision hit areas to be defined independently. This is similar to a layer can be drawn with OPERATION.MASK and then read by other layers. The difference is that there is no analogue of maskId - that it, there is only one global collision render target.

API

const pointsProps = {
  data: PLACES, 
  pointType: 'circle', 
  getText: f => f.properties.name, 
  getTextSize: 18
};

const layers = [
  new GeoJsonLayer({
    id: 'hit-areas',
    operation: OPERATION.COLLIDE,
    ...pointsProps,
    getPointRadius: 2 * pointsProps.getPointRadius // Enlarge point to increase hit area
  }),
  new GeoJsonLayer({
    id: 'points',
    extensions: [new CollideExtension()],
    collideEnabled: true, // Defaults to true
    ...pointsProps
  })
];

Technical details

To implement this effect, all layers marked with OPERATION.COLLIDE are rendered into a off-screen framebuffer in a separate rendering pass. Rather than being drawn normally, they are drawn using the picking colors in order to distinguish them from each other. When layers which have the CollideExtension enabled are drawn, they read the collision framebuffer and only draw features whose picking color matches that which is present in the framebuffer.

https://user-images.githubusercontent.com/453755/199731911-aca792ad-6732-4a1f-80a2-21653b897744.mov

The above visual shows how this works for two points. The points with the white stroke are using the CollideExtension, the vertical bars represent the texture lookup, and the larger circles the contents in the framebuffer. DEMO

This approach provides a number of benefits over the CPU approach:

• Multiple layers can write using OPERATION.COLLIDE allowing collision avoidance between different layers
• TileLayers and CompositeLayers are supported
• Realtime performace. Tests with 7000 points run at 120fps
• No processing necessary in JavaScript
• Possible future integration with other deck extensions: Mask, DataFilter etc

Demo

These two videos show how the extension works for a dataset of ~7000 points.

https://user-images.githubusercontent.com/453755/199730527-883133b4-0acb-4d27-b0c6-9d027dc67563.mov

https://user-images.githubusercontent.com/453755/199936900-fdae0243-3a95-40df-bd3e-3039a78c4ac1.mov

[Pessimistress]

This is very cool!

A few thoughts:

• Looks like this only support a single dataset? I would think for most layers you want a "hit area" layer that is the same type as the "draw" layer. Would it be more flexible if the extension works along the lines of:

  new ScatterplotLayer({
      id: 'points',
      extensions: [new CollideExtension()],
      radiusScale: 10,
  
      // These will be merged with the props of this layer when drawing to the collide buffer
      collisionTestProps: {
        radiusScale: 20
      }
    })

• I would like to be able set the "priority" for each object - when overlapped with others, the one with the highest priority should be picked. This should be doable via some depth test / blending tricks.

[felixpalmer]

Looks like this only support a single dataset

Not sure I understand this comment. In the PoC multiple layers with different datasets can be collided at the same time

most layers you want a "hit area" layer that is the same type as the "draw" layer

Agreed, I also considered this API. All my examples basically have two very similar layers, which is somewhat cumbersome. On the other hand, it is the same mental model as the MaskExtension. The one reason to do it the way I've proposed is to allow another layer to be used for the collide pass for performance reasons. For example, a SimpleMeshLayer could use ScatterplotLayer for the collisions. That said, it is very tempting to just have an API where the CollideExtension is added to a layer and it just works.

set the "priority" for each object

This already works automatically based on the ordering of the data within a single layer, which covers many use cases. Are you thinking about interleaving multiple layers? If you could elaborate on depth test / blending tricks that would be great. My first approach would be adjust the z-coordinate in the vertex shader, bringing higher priority objects forward.

[Pessimistress]

multiple layers with different datasets can be collided at the same time

How do you make a TextLayer detect overlap within itself, and then a ScatterplotLayer with a different dataset also detect overlap within itself? I don't see any API to associate an operation: 'collide' layer with another specific layer.

This already works automatically based on the ordering of the data within a single layer, which covers many use cases. Are you thinking about interleaving multiple layers?

Consider this use case: I have generated labels along a path and I want to "sample" them at appropriate intervals for the current zoom.

If you draw them in order, only the last label will be considered "not occluded":

With custom priority applied, I can control which one to pick when two objects overlap:

It is common in maps for point features to have ranks for this exact reason. You could require the user to sort their data by rank on the CPU, but it will be much more convenient to do it on the GPU.

My first approach would be adjust the z-coordinate in the vertex shader, bringing higher priority objects forward.

Yes, I was thinking of shifting the vertex position in clipspace.

[felixpalmer]

I have updated the PoC to include sorting functionality via a getCollidePriority accessor. As for independent "collide groups" I think we could follow the same pattern as with multiple shadows, i.e. run separate CollidePasses for each group. The PoC doesn't yet implement the collideGroup API.

I would propose this updated API:

new ScatterplotLayer({
    id: 'points',
    extensions: [new CollideExtension()],
    collideGroup: 'labels', // Other layers with this group will be rendered to the same target
    getCollidePriority: f => f.properties.scalerank // Optional, default 0. Must return value in range -1000 to 1000
    radiusScale: 10,

    // These will be merged with the props of this layer when drawing to the collide buffer
    collideTestProps: {
        radiusScale: 20
    }
})

Note the removal of OPERATION.COLLIDE

[IvanSanchez]

I've been exchanging a few words with @felixpalmer off github, and I see a few problems with this approach.

This works well for circles of the same size (or rectangles of the same aspect ratio), but fails if that's not the case.

So let me state the (mathematically) obvious: two circles overlap if the sum of their radii is larger than the distance between their centers (or r1+r2>d12). Also, the collision operation is reflexive: if circle1 collides with circle2, then circle2 collides with circle1.

This algorithm works by discarding circle2 whenever the distance to circle1 is less than 2*r1 away. This has the consequence of making the collision operation non-reflexive (when r1>r2 then there's a range of distances r1>d>r2 where r1 collides with r2 but r2 doesn't collide with r1).

In order to avoid that, it'd be possible to give higher priority to bigger symbols. But that still wouldn't work as a "collision detector", but rather as a margin around the symbol (since smaller symbols not colliding with the large one but close enough to it would be skipped as well).

But giving higher priority to bigger symbols would invalidate user-specified weights.

The only alternative I see would be to use the depth buffer as a SDF, so that each texel would store the distance to the edge, and if the result of the texel query is lower than (zero minus) own radius, then there's no collision. But I'm unsure whether this (specifically, reading back the depth buffer) can be done within the WebGL pipeline.

[felixpalmer]

The problem this extension is trying to solve is to hide objects until those that remain do not overlap. Perhaps it would benefit from a better name.

The operation is inherently non-reflexive in that only the object with the higher priority is shown while the others are hidden. If the use case was to highlight overlaps in a hypothetical OverlapExtension then reflexivity would be required. As it is it doesn't matter if circle1 doesn't know it hid circle2, as long as circle2 knows it is hidden by circle1.

[marcodelpercio-oneocean]

This is incredibly cool! Excellent work. I'd love to see more documentation and examples

[chrisgervang]

Could this be extended to reposition text colliding with another point layer such that they don't collide? I see that text can be hidden (with a fade-out effect?) if it collides, but can other behavior be specified when a collision is detected?