1// Aseprite
2// Copyright (c) 2020-2022 Igara Studio S.A.
3//
4// This file is released under the terms of the MIT license.
5// Read LICENSE.txt for more information.
6
7#ifndef DOC_OCTREEMAP_H_INCLUDED
8#define DOC_OCTREEMAP_H_INCLUDED
9#pragma once
10
11#include "doc/color.h"
12#include "doc/image_impl.h"
13#include "doc/palette.h"
14#include "doc/rgbmap.h"
15
16#include <array>
17#include <memory>
18#include <vector>
19
20// When this DOC_OCTREE_IS_OPAQUE 'color' is asociated with
21// some variable which represents a mask color, it tells us that
22// there isn't any transparent color in the sprite, i.e.
23// there is a background layer in the sprite.
24#define DOC_OCTREE_IS_OPAQUE 0x00FFFFFF
25
26namespace doc {
27
28class OctreeNode;
29using OctreeNodes = std::vector<OctreeNode*>;
30
31class OctreeNode {
32private:
33 class LeafColor {
34 public:
35 LeafColor() :
36 m_r(0),
37 m_g(0),
38 m_b(0),
39 m_a(0),
40 m_pixelCount(0) {
41 }
42
43 LeafColor(int r, int g, int b, int a, size_t pixelCount) :
44 m_r((double)r),
45 m_g((double)g),
46 m_b((double)b),
47 m_a((double)a),
48 m_pixelCount(pixelCount) {
49 }
50
51 void add(color_t c) {
52 m_r += rgba_getr(c);
53 m_g += rgba_getg(c);
54 m_b += rgba_getb(c);
55 m_a += rgba_geta(c);
56 ++m_pixelCount;
57 }
58
59 void add(LeafColor leafColor) {
60 m_r += leafColor.m_r;
61 m_g += leafColor.m_g;
62 m_b += leafColor.m_b;
63 m_a += leafColor.m_a;
64 m_pixelCount += leafColor.m_pixelCount;
65 }
66
67 color_t rgbaColor() const {
68 int auxR = (((int)m_r) % m_pixelCount > m_pixelCount / 2) ? 1: 0;
69 int auxG = (((int)m_g) % m_pixelCount > m_pixelCount / 2) ? 1: 0;
70 int auxB = (((int)m_b) % m_pixelCount > m_pixelCount / 2) ? 1: 0;
71 int auxA = (((int)m_a) % m_pixelCount > m_pixelCount / 2) ? 1: 0;
72 return rgba(int(m_r / m_pixelCount + auxR),
73 int(m_g / m_pixelCount + auxG),
74 int(m_b / m_pixelCount + auxB),
75 int(m_a / m_pixelCount + auxA));
76 }
77
78 size_t pixelCount() const { return m_pixelCount; }
79
80private:
81 double m_r;
82 double m_g;
83 double m_b;
84 double m_a;
85 size_t m_pixelCount;
86 };
87
88public:
89 OctreeNode* parent() const { return m_parent; }
90 bool hasChildren() const { return m_children != nullptr; }
91 LeafColor leafColor() const { return m_leafColor; }
92
93 void addColor(color_t c, int level, OctreeNode* parent,
94 int paletteIndex = 0, int levelDeep = 7);
95
96 int mapColor(int r, int g, int b, int a, int mask_index, const Palette* palette, int level) const;
97
98 void collectLeafNodes(OctreeNodes& leavesVector, int& paletteIndex);
99
100 // removeLeaves(): remove leaves from a common parent
101 // auxParentVector: i/o addreess of an auxiliary parent leaf Vector from outside.
102 // rootLeavesVector: i/o address of the m_root->m_leavesVector
103 int removeLeaves(OctreeNodes& auxParentVector,
104 OctreeNodes& rootLeavesVector);
105
106private:
107 bool isLeaf() { return m_leafColor.pixelCount() > 0; }
108 void paletteIndex(int index) { m_paletteIndex = index; }
109
110 static int getHextet(color_t c, int level);
111 static int getHextet(int r, int g, int b, int a, int level);
112 static color_t hextetToBranchColor(int hextet, int level);
113
114 LeafColor m_leafColor;
115 mutable int m_paletteIndex = -1;
116 mutable std::unique_ptr<std::array<OctreeNode, 16>> m_children;
117 OctreeNode* m_parent = nullptr;
118};
119
120class OctreeMap : public RgbMap {
121public:
122 void addColor(color_t color, int levelDeep = 7) {
123 m_root.addColor(color, 0, &m_root, 0, levelDeep);
124 }
125
126 // makePalette returns true if a 7 level octreeDeep is OK, and false
127 // if we can add ONE level deep.
128 bool makePalette(Palette* palette,
129 int colorCount,
130 const int levelDeep = 7);
131
132 void feedWithImage(const Image* image,
133 const bool withAlpha,
134 const color_t maskColor,
135 const int levelDeep = 7);
136
137 // RgbMap impl
138 void regenerateMap(const Palette* palette, const int maskIndex) override;
139 int mapColor(color_t rgba) const override;
140 int maskIndex() const override { return m_maskIndex; }
141 int mapColor(const int r, const int g,
142 const int b, const int a) const
143 {
144 ASSERT(r >= 0 && r < 256);
145 ASSERT(g >= 0 && g < 256);
146 ASSERT(b >= 0 && b < 256);
147 ASSERT(a >= 0 && a < 256);
148 return mapColor(rgba(r, g, b, a));
149 }
150
151 int moodifications() const { return m_modifications; };
152
153private:
154 OctreeNode m_root;
155 OctreeNodes m_leavesVector;
156 const Palette* m_palette = nullptr;
157 int m_modifications = 0;
158 int m_maskIndex = 0;
159 color_t m_maskColor = 0;
160};
161
162} // namespace doc
163#endif
164