Skip to content

Speed up packing #303

@meganrm

Description

@meganrm

Jitter was really fast, but we discovered some issues with it allowing small overlaps (for some use cases it might be good enough). Our new system has zero overlaps, but is a lot slower.

Are there ways we can speed up our current system by making use of parts of the jitter algorithm without losing the accuracy? look at search tree?

what are ways we could use jitter with additional checks at the end to avoid the tiny overlaps?

After some discussion involving @meganrm, @gj210, @mogres, @toloudis, we came to the conclusion that the jitter algorithm essentially uses a signed distance function created by the grid to recreate the shapes of already packed objects. This recreation is imperfect due to the inherent granularity of the grid, and it is possible for a grid-object check to pass even when it should identify a collision. This is illustrated by the following applet created by @toloudis: https://editor.p5js.org/toloudis/sketches/3JIhRhpHZ

image

Suggestions for moving forward:

  1. Store the identity of the nearest object (in addition to the distance to the nearest surface) within the grid points

  2. Implement a local object-object collision check

Originally posted by @mogres in #134

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions