Dedicated Rect Atlas Class

[deanljohnson]

Summary & Analysis

Duality currently uses a List<Rect> for image atlases to store the position of individual sprites within a Pixmap. This approach is lacking many features such as sprite pivots and sprite string tags that would be helpful for developers and necessary to implement higher level animation functionality. Consider creating an RectAtlas class

This issue was first discussed in #650. Below is some relevant information from that discussion:

So there are two spots where atlases are currently used, one being Pixmap (pixel coordinates) and the other being Texture (texture / UV coordinates). Aside from differing coordinate spaces they behave exactly the same and should provide the same featureset. Right now, they're just a List<Rect>, but with new features to be added, it might make sense to create an actual ImageAtlas class that is used by both Pixmap and Texture, and exposed using their Atlas property.

Since atlas lookups happen a lot on a per-frame basis (every text glyph, every tile, every sprite), performance is a priority - probably not a problem, just something to keep in mind. For example, fast-path atlas indexing using an int for some internal array is a feature we might want to keep regardless of other lookup methods.

On the top of my head, I'd probably go with the following featureset for a potential ImageAtlas:

* **Fast-path atlas rect retrieval via direct indexing.** Probably still via `int` that can go directly to some internal array.

* **The possibility to tag individual rects, or groups of rects, with a string.** Could be done manually in the slicer, in the object inspector, or automatically during import when importing sprite sheets from other applications.

* **Lookup of an index or index list via tag string.** Doesn't need to be super-fast, as it's probably more of a one-off-per-object operation.

* **Optional definition of rect borders** for each rect side for 9-patch support, but could be used for other purposes as well.

* **Optional definition of a rect pivot**, allowing renderers to position the sprite relative to its own position. Would grant some extra robustness for animations, but also simplify regular `SpriteRenderer` setups, so we don't need to specify the exact rect / offset for every single renderer, and adjust that everywhere when it changes at some point.

("Optional" meaning we define default values that behave as if the feature wasn't there)

With the above features, we do get some low-key animation support, but don't actually go too far into that territory. Most of the features that can be used for easing flipbook animation workflows might as well be used for different cases and are (hopefully) general purpose enough to not feel weird in a general image atlas definition.

Proposed RectAtlas API

• IList<Rect> implementation so that RectAtlas can be used identically to the current List<Rect> implementation.
• Indexer that takes a string for looking up the first rect with a given tag.
• TagIndices(string, int[]) - tags a set of indices.
• GetTaggedRects(string) - returns an IEnumerable of rects with the given tag. Empty enumerable if no rects with the given tag exist.
• GetTaggedIndices(string) - returns an IEnumerable of indexes with the given tag. Empty enumerable if no indexes with the given tag exist.
• UntagIndices(string, int[]) - removes the given tag for the indices.
• IList<Vector2> Pivots Property - stores the pivots for every rect in the atlas. Defaults to whatever amounts to a non-op in the current rendering code.

Other Considerations

Beyond the creation of this class and refactoring of existing core code to support this, there is a decent amount of editor work to be done in terms of property editors and related forms such as importers and PixmapSlicer.

• Ability to tag rects and specify pivots from the PixmapSlicer window.
• Ability to tag rects and specify pivots from the Pixmap and Texture editors.
• Ability to tag rects on import according to a specified naming convention.

---

I've started taking a look at creating the RectAtlas class. It delegates most IList functions to a private List<Rect> instance with some additional code to manage a Dictionary<string, List<int>> that stores tagged indices. The dictionary instance is created only when needed so we only have a dynamic allocation when necessary.

Would there be any expectation or desire to create/modify RectAtlas objects at runtime? If not, we could save a bit of memory by using perfectly sized arrays rather than lists at the expense of more complicated code and slower modifying operations (resizing of internal arrays by +1/-1 on add/remove).

Might also be worth benchmarking the use of BinarySearch over a list of string to find the list that tracks tagged indices rather than relying on Dictionary and hashing. I've found some references online to this being faster on similar problems. Sorting on strings might be sub-par when we consider that collections of sprites tend to have similar names in terms of alphabetical sorting ("anim_fire_1", "anim_fire_2", etc.).

Not sure how we should address storing 9-patch data yet.

[SirePi]

Agreed with the need to have a specific storage for Atlases that includes a string-based lookup, for use with big spritesheets.

Would there be any expectation or desire to create/modify RectAtlas objects at runtime?

For me, yes - if only to keep consistency with the "everything that's done in the editor can also be done programmatically" approach (plus I often do things programmatically myself so... win-win)

Not sure how we should address storing 9-patch data yet.

Don't know if it helps, but for my UI plugin I manage it with a Border class, which is nothing more than a struct containing 4 ints (probably ushorts would actually suffice) that indicate the thickness, in pixels of the 4 "sides" of the 9-patch. (see here)

[deanljohnson]

Having trouble making a decision on how to approach something with this issue and was hoping to get some feedback/suggestions. Right now, the RectAtlas class I have created stores three separate data structures internally:

• List<Rect> - the rects of the pixmap/texture
• Vector2[] - the pivots for each rect.
• Dictionary<string, List<int>> - stores tags and their associated indices. Only allocated when needed.

There are really two main issues I see here. One issue is that any operation that asks for the tag of a certain index can't be performant - not sure is this is an issue to worry about since I think things are typically done the other way around (that is, finding the rects/indices with a given tag). The other issue I am running into is how to structure the property editor for this setup. Right now I have the following for editing rects and pivots:

The editor and RectAtlas class themselves make sure that these two properties always have the same number of elements.

I'm not sure how to add tags into this kind of setup and make the editor easily usable. We could rely on the Pixmap Slicer to provide nice editing capabilities and leave the RectAtlasPropertyEditor bare bones, but that seems less than ideal. The other option would be to store all the data in some structure that contains the rect, pivot, and tag list of a single index. The problem with that is that now every rect gets a possible dynamic list allocation (unless we want to say that each index can only have a single tag). It also makes tag lookups slower. I could write the RectAtlasPropertyEditor in such a way that it transforms the RectAtlas instance into a list of these alternative structures and then displays an editor for that list of structs which would provide a great editor experience but then the editor would portray a different interface than the underlying class. That could potentially be confusing to users because the PropertyGrid tends to reflect the structure of the objects its displaying.

Thoughts?

[Barsonax]

One issue is that any operation that asks for the tag of a certain index can't be performant - not sure is this is an issue to worry about since I think things are typically done the other way around (that is, finding the rects/indices with a given tag).

For fast index lookups you could store a reference to the list in both a dictionary and a array. You just have to wrap these collections to abstract this complexity.

[ilexp]

The other option would be to store all the data in some structure that contains the rect, pivot, and tag list of a single index.

I think this is generally a good idea - maybe without the tags list to avoid the list allocation per element you mentioned. Having a whole lot of elements is the expected case after all. Here's a possible iteration of your draft above:

public class RectAtlas
{
    // RawList allows direct array access for efficiency if needed. Use List otherwise.
    private RawList<RectAtlasItem> items; 
    private Dictionary<string, List<int>> indicesByTag; // null by default

    // ...
}

public struct RectAtlasItem
{
    public Rect Region;
    public Vector2 LocalPivot;

    // ...
}

With an explicit RectAtlasItem, we have the easily digestible base information in one spot, an easy way to add more data later on if ever needed, and a data model that is both easily editable in the inspector and slightly more explicit in what it does and is meant for. No need to keep multiple collections in sync to store everything.

As for the tags, that is indeed tricky. I think that a custom PropertyEditor and relying on the slicer would be a good solution when data-generated UI usability vs data efficiency becomes an issue. But before we enter that level of complexity: Do we really need multiple tags per atlas item? Right now I'd go with "no" and have only one tag string per item like you mentioned. Use cases:

• Tagging an item with a name: Makes it easily retrievable, allows named, stable access even when indices change.
• Tagging multiple items with the same name: Defines an (index) ordered sequence and allows defining named groups or flipbook animations.
• Retrieving multiple differently named items by tag: No longer supported in RectAtlas directly, but easily emulated in game code and probably not that common of a use case either. Could also be added to RectAtlas later on as a separate grouping functionality based on a Dictionary<string, List<string>> mapping a "multi-tag" to multiple individual tags to be retrieved, but I would honestly just leave this functionality out for now.

With that in mind:

public class RectAtlas
{
    private RawList<RectAtlasItem> items; 
    private Dictionary<string, List<int>> indicesByTag; // null by default

    // ...
}

public struct RectAtlasItem
{
    public Rect Region;
    public Vector2 LocalPivot;
    public string Tag; // null by default

    // ...
}

The indicesByTag field would not be writable via API, but internally updated based on changes to the items list.

For inspector access, something like this could be an option:

public class RectAtlas
{
    // ...

    // Private property that's only accessible via inspector and invokes 
    // the setter for validation when changing its contents

    /// <summary>
    /// Display text for the inspector.
    /// </summary>
    [EditorHintFlags(MemberFlags.ForceWriteback)]
    [EditorHintFlags(MemberFlags.Visible)]
    private RawList<RectAtlasItem> Items
    {
        get { return this.items; }
        set
        {
            // Maybe even validate inspector-provided value contents here?
            this.items = value;
            this.UpdateLookup();
        }
    }

    // ...
}

This would keep all the data display- and editable in the inspector directly when needed, without additional transformation for display only.

As usual, thoughts appreciated.

[deanljohnson]

One tag per item sounds good to me - makes things a lot easier because I can go with the RectAtlasItem implementation. With that I think the editor side of things will become a lot easier which was the only part giving me any trouble.

Thanks for the ideas.