Adding support for more primitives checks

[DavidWeiss2]

Hi, because the Quadtree is used in collision detection systems, and not all colliders have a rectangle shape. It would be awesome to see support for more primitives as colliders and maybe even support mesh shapes.

Here some info about how to implement this feature:
https://www.youtube.com/watch?v=ajv46BSqcK4

[DavidWeiss2]

And also:
https://ora.ox.ac.uk/objects/uuid:69c743d9-73de-4aff-8e6f-b4dd7c010907/download_file?safe_filename=GJK.PDF&file_format=application%2Fpdf&type_of_work=Journal+article

[timohausmann]

Thanks for the links, very interesting.

I'm open to support more primitives, primarily points, lines and ellipses in this codebase.

I think polygons would require precise collision checks but the Quadtree – by design – would still return all objects inside the matched leaf nodes, even if they don't collide. So the Quadtree would first perform e.g. GJK to find all leaf nodes that match the polygon and return their objects. But the matched leaf nodes may contain objects that don't actually intersect with the queried polygon, so the rest of the program would have to perform collision checks on the objects again.

Maybe polygon support could be a plugin or a wrapper, that implements GJK and does actual collision detection.

[DavidWeiss2]

I would work on this in the next week. Thanks.

[ben-at-sahmri]

I'm interested in this feature too, and could possibly help work on a plugin or implementation.

For my use, I'm mostly interested in finding polygons underneath a given coordinate. In the meantime, I might take a look at using bounding rects to find candidates and then testing their internal polygons to find the final result. Should still be much better than what I've been doing.

[timohausmann]

Checking for polygon collisions is an interesting issue, I could imagine it as another npm package that implements GJK and uses quadtree-js as a dependency to narrow down collision candidates. The main goal of this library is to implement a quadtree.

[ben-at-sahmri]

Yeah, that’s fair enough, and agreed that it’s not really suitable to be packed into this lib. My use case (use bounding rects for a shortlist, then check their internal geometry for an exact match) works really well and is very simple for the “point collision” case. ~2ms for the quad tree retrieve and 1ms for the final check over 4500 triangles.

Thanks for the great lib - saved me a ton of work!

[timohausmann]

I put together a demo that supports circle and line primitives: https://timohausmann.de/quadtree.js/primitives.html

To easily differentiate the types I implemented Quadtree.Rect, Quadtree.Circle, Quadtree.Line.

If you have any thoughts or feedback about this "API" or the attribute names please let me know (especially data, qtype).

const rect = new Quadtree.Rect({
    x: 0,
    y: 0,
    width: 40,
    height: 40
});

const circle = new Quadtree.Circle({
    x: 0, 
    y: 0, 
    r: 42
});

const line = new Quadtree.Line({
    x1: 50, 
    y1: 50, 
    x2: 150,
    y2: 150,
    data: {
        //you can put your custom data here ...
        centerX: 100,
        centerY: 100
    }
});

You could also use custom objects and specifiy what they are with qtype:

const bigObject = {
    qtype: Quadtree.Circle,
    x: 0, 
    y: 0, 
    r: 42,
    foo: 'bar'
    //100 more custom attributes ...
};

I would probably put each primitive in it's own source file, this needs some refactoring, could use the opportunity to switch to ES6. This way it would be easy to add a Quadtree.Poly or similar later, too ;-)

The only part in the Quadtree logic that needs to be different per-primitive is the getIndex function, therefore I would attach a getIndex function to each primitive "class".

[timohausmann]

FYI there is a 2.0 beta release that supports lines, circles and rectangles and can be extended with other primitives.
It also uses Typescript and has tests. It uses classes and new and I'm currently wondering if this is a good dev experience (you seldom see new in the wild).
https://github.com/timohausmann/quadtree-js/tree/typescript

Edit: I think a good solution would be shortcuts for new Quadtree(), new Rectangle() etc. with quadtree(), rectangle().

[timohausmann]

FYI this and more is now possible with this fork https://github.com/timohausmann/quadtree-ts/

I just like the minimalism of this repo too much to overwrite it!