soimy / maxrects-packer Goto Github PK

Hi,

i found two edge cases where the library is not placing the rects as intended.

Unrotated rect will not fit, rotated will fit but it moves to a new bin.

This is a test for maxrects-bin.ts describing the edge case:

test("edge case: only rotated version fits and should be set", () => {
        const edgeCaseBin = new MaxRectsBin(256, 1024, 0, {allowRotation: true, pot: false});
        edgeCaseBin.add(260, 80);
        edgeCaseBin.add(260, 80);
        edgeCaseBin.add(260, 80);
        edgeCaseBin.add(260, 80);
        expect(edgeCaseBin.rects).toHaveLength(4);
});

The reason for this bug is here:

With Padding, four rects only placeable rotated. First three rotate, fourth not. This is should be impossible.

This is a test for maxrects-bin.ts describing the edge case:

test("edge case: multiple rects with slightly bigger size then maxWidth should be placed rotated", () => {
        const edgeCaseBin = new MaxRectsBin(256, 1024, padding, {allowRotation: true, pot: false, square: false, smart: true});
        edgeCaseBin.add(260, 80);
        edgeCaseBin.add(260, 80);
        edgeCaseBin.add(260, 80);
        edgeCaseBin.add(260, 80);

        expect(edgeCaseBin.rects).toHaveLength(4);
        expect(edgeCaseBin.rects[3].rot).toBeTruthy();
        expect(edgeCaseBin.rects[3].width).toBe(80);
    });

This bug occures only on the given options. The fourth rect is not placed rotated when width is bigger then maxWidth + padding

Here i am not sure why this happens. I guess that the reason is in here:

The tmpHeight and tmpWidth values are without padding compared to the maxWidth and maxHeight plus padding.

I will provide a PR with the fixes.

This repro will completely hang the library until it crashes:

const maxRectsPacker = new MaxRectsPacker(512, 512, {
          padding: 1,
          // exclusiveTag: false,
        });
        const rects2 = [
          {
            width: 512,
            height: 512,
          },
          {
            width: 512,
            height: 512,
          },
        ];
        for (const rect of rects2) {
          maxRectsPacker.add(rect);  
        }

As far as I understand, this should set oversized flags but bail out. Instead it just loops forever doing some sort of placement/freeing procedure.

This makes the library dangerous to use in any situation where the input sizes can be user-controlled, since it risks total application hang.

If you pause you can get a sense of the infinite loop.

Hi, i run into an issue. I want to save my packer by using packer.save() but the rect property of my bins are empty.
So i dug into the code and found that the rect prop is not filld here:

To understand the problem i created a sandbox with the problem:
https://codesandbox.io/s/musing-sound-vedd2b?file=/src/index.ts

version 2.7.3

I tried different width and heights of a packer like 1500 or 800. But each bins width and height is reduced to the closest number of bineric like 800 is down to 512 and 1500 down to 1024.

Maybe it is not the purpose of this library but i need an option to force the algorithm to use the complete width or the complete height. Is this possible?

Enhancement despide if yes or no: describe this behavior in the readme.

Thanks!

Would it be possible to get a 2.7.3 release out with my recursion fix in there? I don't mind building and running my stuff locally but it might be nice to have that in an official npm package. Thanks!

Thus adding an alternative way than just as an algorithm npm module.

Thanks for the library! Is there any plans to allow rotation of the rects to pack more in a given bin?

It appears that the addArray function only accepts types extended from IRectangle. This appears to be an issue because IRectangle includes values that should not be set during addition of rectangles (such as x and y).

e.g.

// packer: MaxRectsPacker<IRectangle>
packer.addArray([{width: 1, height: 1}]) // Type '{ width: number; height: number; }' is missing the following properties from type 'IRectangle': x, y ts(2739)

I think the generic needs to be more narrowed to something like

interface IRectangleInput {
  width: number
  height: number
  [propName: string]: any
}

perhaps porting the tests to typescript would catch this?

Thanks for making this lib either way 🙏

I'm searching the web dry for a texture packer that's a bit more modular, but i can't figure out how this would generate an image - does anything support it?

When adding a rect that oversizes the exclusively tagged bin using addArray, It hangs and after some time crashes with RangeError: Maximum call stack size exceeded

const opt = { smart: true, pot: false, square: false, allowRotation: false, 
    tag: true,
    exclusiveTag: false
}         
const packer = new MaxRectsPacker(1024, 1024, 0, opt)
let input = [
    {width: 2000, height: 1000, data: { tag: 'bla' }} 
];
packer.addArray(input); // Never returns / RangeError: Maximum call stack size exceeded

The same happens when the sum of the rects ends up oversized

let input = [
    {width: 1000, height: 1000, data: { number:1, tag: 'bla' }},
    {width: 1000, height: 1000, data: { number:2, tag: 'bla' }} 
];
packer.addArray(input); // Never returns / RangeError: Maximum call stack size exceeded

No big issue, just annoying when trying to reduce the size of the output bins.

Otherwise great stuff 👍

It is not a critical issue but is a case of inconsistent behavior under different settings.

To reproduce:

const Packer = require('maxrects-packer').MaxRectsPacker;
const packer = new Packer(atlasWidth, atlasHeight, 0, {
    pot: true,
    square: true,
    tag: true,
    exclusiveTag: false
});
packer.addArray([]); // Bazinga! Cannot read property 'data' of undefined
                     // Does work if you remove `exclusiveTag: false`

toJSON() method shall be implemented.
Related disscussion: #52

Wondering if there's a way to do this? don't want to spend time digging into the source code if not needed, but if this isn't possible I'll implement it myself- anything insightful that'll help me implement this if I need to dig in?

I have a set of rectangles that have to be packed into some bins.
But there are some rects that have to be together in the same bin (to prevent multiple textures in a shader)

Is there a way to achieve this using tags?
I noticed currently each tag creates a new bin, and a bin with a tag does not accept any untagged rects.

Related to odrick/free-tex-packer-core#14

Data to reproduce:

maxWidth: 1780
maxHeight: 1780
padding: 0
options: {
    "smart": true,
    "pot": false,
    "square": false,
    "allowRotation": false,
    "logic": 1
}

[
    {
        "width": 18,
        "height": 209
    },
    {
        "width": 50,
        "height": 215
    },
    {
        "width": 81,
        "height": 219
    },
    {
        "width": 115,
        "height": 221
    },
    {
        "width": 149,
        "height": 225
    },
    {
        "width": 177,
        "height": 227
    },
    {
        "width": 192,
        "height": 231
    },
    {
        "width": 207,
        "height": 233
    },
    {
        "width": 221,
        "height": 235
    },
    {
        "width": 236,
        "height": 219
    },
    {
        "width": 252,
        "height": 199
    },
    {
        "width": 271,
        "height": 203
    },
    {
        "width": 317,
        "height": 218
    },
    {
        "width": 326,
        "height": 240
    },
    {
        "width": 334,
        "height": 267
    },
    {
        "width": 336,
        "height": 295
    },
    {
        "width": 359,
        "height": 290
    },
    {
        "width": 379,
        "height": 284
    },
    {
        "width": 389,
        "height": 259
    },
    {
        "width": 92,
        "height": 209
    },
    {
        "width": 94,
        "height": 228
    },
    {
        "width": 106,
        "height": 247
    },
    {
        "width": 119,
        "height": 267
    },
    {
        "width": 131,
        "height": 287
    },
    {
        "width": 139,
        "height": 301
    },
    {
        "width": 150,
        "height": 215
    },
    {
        "width": 163,
        "height": 213
    },
    {
        "width": 166,
        "height": 213
    },
    {
        "width": 152,
        "height": 215
    },
    {
        "width": 138,
        "height": 218
    },
    {
        "width": 132,
        "height": 220
    },
    {
        "width": 129,
        "height": 221
    },
    {
        "width": 136,
        "height": 223
    },
    {
        "width": 138,
        "height": 225
    },
    {
        "width": 138,
        "height": 226
    },
    {
        "width": 134,
        "height": 226
    },
    {
        "width": 128,
        "height": 222
    },
    {
        "width": 122,
        "height": 219
    },
    {
        "width": 115,
        "height": 216
    },
    {
        "width": 108,
        "height": 215
    },
    {
        "width": 111,
        "height": 215
    },
    {
        "width": 120,
        "height": 216
    },
    {
        "width": 131,
        "height": 214
    },
    {
        "width": 141,
        "height": 212
    },
    {
        "width": 141,
        "height": 210
    },
    {
        "width": 143,
        "height": 209
    },
    {
        "width": 168,
        "height": 208
    },
    {
        "width": 227,
        "height": 206
    },
    {
        "width": 259,
        "height": 205
    },
    {
        "width": 262,
        "height": 204
    },
    {
        "width": 291,
        "height": 202
    },
    {
        "width": 309,
        "height": 201
    },
    {
        "width": 326,
        "height": 200
    },
    {
        "width": 341,
        "height": 199
    },
    {
        "width": 317,
        "height": 200
    },
    {
        "width": 289,
        "height": 197
    },
    {
        "width": 262,
        "height": 154
    },
    {
        "width": 234,
        "height": 68
    },
    {
        "width": 206,
        "height": 29
    },
    {
        "width": 180,
        "height": 20
    },
    {
        "width": 151,
        "height": 20
    },
    {
        "width": 122,
        "height": 18
    },
    {
        "width": 96,
        "height": 16
    },
    {
        "width": 95,
        "height": 16
    },
    {
        "width": 95,
        "height": 16
    },
    {
        "width": 93,
        "height": 15
    }
]

result width: 1596
result height: 1756
result area: 2802576

maxWidth: 1780
maxHeight: 1780
padding: 0
options: {
    "smart": true,
    "pot": false,
    "square": false,
    "allowRotation": true,
    "logic": 1
}

input: same

result width: 1660
result height: 1759
result area: 2919940

So, packing result area is worse when rotation allowed. However, this should not be.

Is there a way to somehow fix certain rectangles into fixed {x, y} positions when doing (re)packing?

Is there a way to add pad on glyphs that are on the edges ? like a border-padding ?

( W @ % etc.. )

The main example has this invalid object in the input:
{width: 2000, height: 2000, name: "oversized background", {frameWidth: 500, frameHeight: 500}},