[sugar] collisions in free form layouts

[Wade Brainerd]

I'm not familiar with Eben's algorithm, but I thought I would chime in
that IMO the ideal algorithm for these kinds of layouts is what is
called a "relaxation algorithm".  It's the basis of most physics
engines like Box2D.

You define a set of rules, called constraints, which define the order
of the layout.  For example "no two icons can oversect", "no icon can
intersect the XO", and "no icon can leave the screen".

To process, you iterate over the constraints, "relaxing" them by some
percentage, for a fixed number K iterations.  For constraints
involving intersecting objects, this involves moving them each apart
along their separating axis by 0.5*penetration/K.  This "relaxes" the
system over time by resolving each constraint a little bit at a time
until all are satisfied.

Implemented naively the complexity is O(N^2), but plenty of
optimizations exist to make it very quick.  The simplest would be a
grid based spacial subdivision.

Best,
Wade

On Sun, Jun 15, 2008 at 1:33 AM, Tomeu Vizoso <tomeu at tomeuvizoso.net> wrote:
> On Sun, Jun 15, 2008 at 10:23 AM, Marco Pesenti Gritti
> <mpgritti at gmail.com> wrote:
>> On Sun, Jun 15, 2008 at 9:48 AM, Tomeu Vizoso <tomeu at tomeuvizoso.net> wrote:
>>> I have some ideas, but I'm not sure how big an advantage they are
>>> because the actual code in SpreadLayout is not resolving collisions.
>>>
>>> I will look at your demo now, but if someone involved in
>>> SpreadLayout/_Grid could explain why the implementation never got
>>> complete, that could save me quite some time.
>>
>> The usual reason, not enough time :)
>
> Ok, then if there's no known problem with the approach in Eben's demo,
> I'll tackle it next.
>
> Regards,
>
> Tomeu
> _______________________________________________
> Sugar mailing list
> Sugar at lists.laptop.org
> http://lists.laptop.org/listinfo/sugar
>