Create a "select" mode

[Michael-F-Bryan]

This follows on from #9 (comment):

I would like to add to this another mode for selecting or picking already drawn geometry.

This is probably the most used functionality and can probably also be implemented as a mode.

As an algorithm for finding things under the mouse cursor we have the most important thing already, as we can do a quick sort of all DrawingObjects whose BoundingBox contains the MousePosition in WorldSpace and do some fine-grained checks afterwards

---

We need an interactive mode which lets us mark an object as selected and move them around the drawing by clicking and dragging.

This will necessitate a couple new concepts on top of #9:

• Selected component (see specs::storage::NullStorage)
• The SelectMode itself
• An efficient way to see what is under the cursor

[Michael-F-Bryan]

Regarding the lookup mechanism, I was thinking of creating a new System which will detects when an entity's BoundingBox has changed (kinda like arcs::systems::SyncBounds) and use those change notifications to update a lookup data structure (e.g. QuadTree). That way we have a really fast (approx O(log n)) way to find out which objects are within a certain area.

This data structure can also be used to make rendering easier by clipping objects that lie off screen.

[DerLando]

I think I found a nice crate for this: https://crates.io/crates/quadtree_rs

I'm thinking of implementing this on top of the Bounded trait:

• everything that can be bounded can be inserted in the quadtree
• implement Bounded for Window, so we can query a region intersection between the screens viewport and all DrawingObjects in World

EDIT:
From my first tests I'm not too hot on this crate anymore, as it does not support floating point values and it's hard to query the data structure for points.

[Michael-F-Bryan]

Yeah... I'm not a massive fan of that API either. Something similar to ntree would work well, otherwise aabb_quadtree looks quite promising.

We need the ability to associate a BoundingBox with an Entity and then over time tell the QuadTree that our Entity has moved so it can re-balance its bookkeeping internally. The vanilla QuadTree implementation just maps BoundingBox -> Entity, but to avoid checking every object in the tree we'd also need to maintain some Entity -> BoundingBox mapping. I think that's what aabb_quadtree is doing under the hood with ItemId.

I have a feeling in the long run we'll end up implementing our own QuadTree type so it can be tailored to arcs's needs, but for now it'd be nice to reuse an existing implementation.

Implement Bounded for Window, so we can query a region intersection between the screens viewport and all DrawingObjects in World

This gets problematic because you need to know the window dimensions in pixels. I don't think we currently do that, although it shouldn't be too hard to create a WindowDimensions component which is a newtype around kurbo::Size. We also need to make sure the WebAssembly demo listens to resize events so it can be kept in sync.

That said, we kinda do this already in an ad-hoc way. Turning it into a proper Component would just formalise things. We'd probably do this by giving Window a fn on_resize(&self, world: &World, new_dimensions: kurbo::Size) method.

[DerLando]

I'll give aabb_quadtree a go for now, although it hasn't been updated in 8 months.

I agree that in the long run an arcs specific implementation would be nice, especially since the implementations I could find aren't too long (under 500 loc)

[DerLando]

I see some problems:

• aabb_quadtree is initialized with a fixed boundingbox which can never change, if you try to insert geometry outside of this bounds, it fails:
• the insert and query methods both rely on euclids TypedRect.contains() method, TypedRect is deprecated so we would be version-locked to 0.19.8.
• TypeRect has some questionable rules for when it contains a point:

  /// Returns true if this rectangle contains the point. Points are considered
  /// in the rectangle if they are on the left or top edge, but outside if they
  /// are on the right or bottom edge.

Other then that, it will work for now! I can submit a PR later where we can discuss further implementation details ;)