Corte Automático

Essa semana começamos a testar uma das primeiras funcionalidades das ferramentas que utilizaremos para desenvolver nosso motor para jogos no estilo Ação-RPG. O corte automático de uma imagem em múltiplos sprites através da análise dos seus pixels.

Inicialmente percorremos cada pixel da imagem, da esquerda para direita, ignorando pixels transparentes, ao final de cada linha, seguimos para a próxima, iniciando novamente da esquerda. Ao encontrarmos um pixel não transparente recorremos a outra parte do código que é responsável por retornar um objeto Rectangle contendo as informações da posição do sprite na imagem.

private GraphicsDeviceManager _graphics;
private SpriteBatch _spriteBatch;

private readonly List _sources;
private Texture2D _texture;
private Color[] _pixelColours;

public Game1()
{
    _graphics = new GraphicsDeviceManager(this)
    {
        PreferredBackBufferWidth = 800,
        PreferredBackBufferHeight = 600
    };
    Content.RootDirectory = "Content";
    _sources = new List();
}

protected override void LoadContent()
{
    _spriteBatch = new SpriteBatch(GraphicsDevice);

    // http://www.hoshi.trinitymugen.net/dcuseitem.png
    _texture = Content.Load("item");
    _pixelColours = _texture.GetPixels();

    GenerateSources();
}

private void GenerateSources()
{
    for (var y = 0; y < _texture.Height; y++)
    {
        for (var x = 0; x < _texture.Width; x++) { if (_pixelColours.IsTransparent(x, y, _texture.Width)) continue; if (_sources.Any(r => r.Contains(new Point(x, y)))) continue;

            _sources.Add(new SourceRectangle(_texture, _pixelColours, x, y).Generate());
        }
    }
}

Nessa classe recebemos em qual posição foi encontrado esse pixel e os dados da textura. No método Generate() é onde a mágica acontece. Utilizando o conceito do algoritmo de inundação (Flood Fill) adicionamos em uma fila o ponto inicial (x,y) do pixel com a estrutura Point. O código é repetido enquanto a fila possuir itens. A cada iteração que ultrapassa as validações adicionamos na fila os pixels que estão em volta do atual.

public class SourceRectangle
{
    private readonly Texture2D _texture;
    private readonly Color[] _pixelColours;
    private readonly int _x;
    private readonly int _y;
    private readonly Queue _queue;
    private readonly HashSet _points;

    public SourceRectangle(Texture2D texture, Color[] pixelColours, int x, int y)
    {
        _texture = texture;
        _pixelColours = pixelColours;
        _x = x;
        _y = y;
        _queue = new Queue();
        _points = new HashSet();
    }

    public Rectangle Generate()
    {
        _queue.Enqueue(new Point(_x, _y));
        while (_queue.Any())
        {
            var p = _queue.Dequeue();

            if (_points.Contains(p))
                continue;

            if (p.X < 0 || p.Y < 0 || p.X >= _texture.Width || p.Y >= _texture.Height)
                continue;

            if (_pixelColours.IsTransparent(p.X, p.Y, _texture.Width))
                continue;

            _points.Add(p);

            // UP
            _queue.Enqueue(new Point(p.X, p.Y + 1));
            // UP-RIGHT
            _queue.Enqueue(new Point(p.X + 1, p.Y + 1));
            // RIGHT
            _queue.Enqueue(new Point(p.X + 1, p.Y));
            // RIGHT-DOWN
            _queue.Enqueue(new Point(p.X + 1, p.Y - 1));
            // DOWN
            _queue.Enqueue(new Point(p.X, p.Y - 1));
            // DOWN-LEFT
            _queue.Enqueue(new Point(p.X - 1, p.Y - 1));
            // LEFT
            _queue.Enqueue(new Point(p.X - 1, p.Y));
            // LEFT-UP
            _queue.Enqueue(new Point(p.X - 1, p.Y + 1));
        }

        var left = _points.Min(r => r.X);
        var top = _points.Min(r => r.Y);
        var right = _points.Max(r => r.X);
        var bottom = _points.Max(r => r.Y);
        var width = right - left + 1;
        var height = bottom - top + 1;

        return new Rectangle(left, top, width, height);
    }
}

Com uma imagem de 2048×2048 o código demora em média 48 segundos para achar 798 objetos.

corte automatico

Link do projeto