Здравствуйте. Вот задался вопросом — как корректно сохранять историю в графическом редакторе (как Гимп) для использования в UNDO/REDO. Сам вижу три варианта:
1. Сохранять список действий.
Например, нарисовал линию такого-то цвета в таких координатах, применил фильтр «Блур», повернул изображение. В случае использования UNDO проходятся все действия от первого до необходимого. Преимущество: Занимает очень мало места в памяти. При сохранении проекта можно с легкостью восстановить всю историю. При желании можно даже хранить полное дерево (например сделали действие A, B, C, D, E, вернулись к С, сделали F, G. Итоговый путь получился ABCFG, но можно как в системе контроля версий сохранить и ветку DE) Недостаток: При использовании Undo или загрузке ранее сохраненного изображения проходится весь путь, а это может играть существенное время и если при обычном простом редактировании такой проход может занять каких-то 100-200 мс, что некритично, так при использовании тяжелых фильтров может замедлиться до десятков секунд.
2. Сохранять полный дамп проекта в bitmap
Каждое действие всю картинку мы сохраняем в память как готовый рисунок. Преимущество: Очень быстро работает. Сделали undo/redo и просто показали из памяти тот рисунок, который у нас был (уже отрендеренный). Даже тяжелый фильтр, что угодно. Недостаток: Занимает очень много места в памяти. Допустим, у нас рисунок размером 1k*1k. В каждом пикселе мы храним 32 бита информации (по 8 бит на r,g,b и 8 бит на альфаканал), то есть 4 байта, то есть такой битмап у нас будет занимать в идеале 4 метра, а история из 64 действий — 64*4 = 256 мб в памяти. А если допустить, что у нас графический редактор поддерживает слои и пусть их будет хотя бы пять… Аналогично, проекты с историей хранить тяжело.
Gimp
В Гимпе по косвенным признакам я опеределил, что используется второй подход. Признаки такие:
1. История ограничена
2. Тяжелые фильтры при ундо-редо возвращают статус кво очень быстро.
3. Совмещенный подход
Конечно, есть альтернатива. Храним историю первым способом, а последних, например, 8 действий храним вторым способом, т.к. редко используется такой дальний undo. Сохранять на винт можно только действия, из-за чего проект с множеством изменений будет долго открываться, но допустимо весить. Или еще добавить последнюю битмап дату. Преимущества обоих подходов Недостаток — значительно утяжеляется логика приложения. Фактически — надо реализовывать два механизма истории.
Тема для обсуждения
Что скажете вы? Может, есть еще какой-то подход. Если нет, то какой из подходов предпочли бы вы (в идеальном случае и в случае очень сжатых сроков)? Почему?
По моему третий способ было бы логично дополнить некими ключевыми кадрами (по аналогии с видео), по сути bitmap, которые бы сохранялись после тяжелых фильтров и хранились бы не в оперативе, а на винте (во временной папке). Т.е. как Вы и описали, несколько последних действий в оперативке в виде bitmap. История назад в виде списка действий от ключевых кадров (тяжелых фильтров). Да и такие ключевые кадры было бы логично хранить не в сыром виде, а хоть в том же png. Это позволит не так значительно тормозить при откате на далекую историю и экономить место на винте за счет сжатия png.
А вообще, идею с ключевыми кадрами можно было бы вообще полностью применить вместо третьего варианта. Т.е. мелкие действия хранить именно как действия, а более тяжелые, как ключевые кадры в виде bitmap в оперативке. Если более тяжелое действие отодвигается в прошлое, то паковать его в png и сбрасывать на винт.
И… по поводу слоёв… у нас же undo обычно применяется к конкретному действию на конкретном слое, а не ко всем слоям одновременно. Конечно есть live-фильтры, но это отдельная история. Я к тому, что число слоёв не увеличивает кол-во bitmap пропорционально.
Если сохранять вторым способом, то надо сохранять все слои как bitmap отдельно.
У меня ограничено место на жёстком диске тоже, но мне нравится ваша идея с ключевыми кадрами.
Наверное, так и сделаю. Спасибо!
А нельзя в каких-то случаях выстроить последовательность, обратную первой?
В смысле, бывают обратимые изменения, а бывают необратимые. Логично хранить ключевой кадр после необратимых, а от основного состояния достраиваться до ближайшего обратимого в обратном порядке, используя историю на уже имеющийся кадр, проходя путь с конца, а не с начала.
Необратимые бывают настолько редко, что такой подход не будет иметь смысла. Попробуйте нарисовать в Гимпе какую-либо картинку кисточками, а потом представьте алгоритм, которым это можно просчитать
А если использовать геометрическаю распределённость? Сохранять не ключевые кадры целиком, а только картинки из области изменений, а потом и накладывать их друг на друга?
То есть каждый мазок кисточкой — это сохранение битмэпа в пределах тех ячеек сетки, где он прошел, а не всей картины.
Сталкивался с такой задачей и именно так и сделал.
Кадр разбивается на N квадратов например по 40*40 пикселей.
Каждое хранимое состояние содержит все N квадратов, но если конкретный квадрат не изменился, то вместо новой копии сохраняется ссылка на соответствующий квадрат из предыдущего состояния.
Это очень удобный и достаточно простой в реализации способ. Я писал под айпад, где и памяти мало, и запись в ПЗУ медленно идет. В результате всё очень быстро работает, и глубина undo достаточная получилась.
Возможный недостаток: каждая операция должна содержать алгоритм определения квадратов, которые она затрагивает. Но обычно это не проблема.
если это простая линия, то, пожалуй, выгоднее будет просто записать её путь напрямую.
если это что-то потяжелее, то оно обычно затрагивает всю картинку.
с другой стороны. если взять фильтр, который работает с выделенной областью, то можно сохранять не всю картинку, а только измененную область, которая выделена)
Средний
