GifMotion by Warren Galyen

<PackageReference Include="GifMotion" Version="1.0.4" />

 OctreeQuantizer

public class OctreeQuantizer : Quantizer
using System; using System.Collections; using System.Drawing; using System.Drawing.Imaging; namespace GifMotion { public class OctreeQuantizer : Quantizer { private class Octree { protected class OctreeNode { private int _blue; private int _green; private bool _leaf; private int _paletteIndex; private int _pixelCount; private int _red; public OctreeNode NextReducible { get; } private OctreeNode[] Children { get; } public OctreeNode(int level, int colorBits, Octree octree) { _leaf = (level == colorBits); _red = (_green = (_blue = 0)); _pixelCount = 0; if (_leaf) { octree.Leaves++; NextReducible = null; Children = null; } else { NextReducible = octree.ReducibleNodes[level]; octree.ReducibleNodes[level] = this; Children = new OctreeNode[8]; } } public void AddColor(Color32 pixel, int colorBits, int level, Octree octree) { if (_leaf) { Increment(pixel); octree.TrackPrevious(this); } else { int num = 7 - level; int num2 = ((pixel.Red & Mask[level]) >> num - 2) | ((pixel.Green & Mask[level]) >> num - 1) | ((pixel.Blue & Mask[level]) >> num); OctreeNode octreeNode = Children[num2]; if (octreeNode == null) { octreeNode = new OctreeNode(level + 1, colorBits, octree); Children[num2] = octreeNode; } octreeNode.AddColor(pixel, colorBits, level + 1, octree); } } public int Reduce() { _red = (_green = (_blue = 0)); int num = 0; for (int i = 0; i < 8; i++) { if (Children[i] != null) { _red += Children[i]._red; _green += Children[i]._green; _blue += Children[i]._blue; _pixelCount += Children[i]._pixelCount; num++; Children[i] = null; } } _leaf = true; return num - 1; } public void ConstructPalette(ArrayList palette, ref int paletteIndex) { if (_leaf) { _paletteIndex = paletteIndex++; palette.Add(Color.FromArgb(_red / _pixelCount, _green / _pixelCount, _blue / _pixelCount)); } else { for (int i = 0; i < 8; i++) { if (Children[i] != null) Children[i].ConstructPalette(palette, ref paletteIndex); } } } public int GetPaletteIndex(Color32 pixel, int level) { int paletteIndex = _paletteIndex; if (!_leaf) { int num = 7 - level; int num2 = ((pixel.Red & Mask[level]) >> num - 2) | ((pixel.Green & Mask[level]) >> num - 1) | ((pixel.Blue & Mask[level]) >> num); if (Children[num2] == null) throw new Exception("Didn't expect this!"); paletteIndex = Children[num2].GetPaletteIndex(pixel, level + 1); } return paletteIndex; } public void Increment(Color32 pixel) { _pixelCount++; _red += pixel.Red; _green += pixel.Green; _blue += pixel.Blue; } } private static readonly int[] Mask = new int[8] { 128, 64, 32, 16, 8, 4, 2, 1 }; private readonly int _maxColorBits; private readonly OctreeNode _root; private int _previousColor; private OctreeNode _previousNode; private int Leaves { get; set; } protected OctreeNode[] ReducibleNodes { get; } public Octree(int maxColorBits) { _maxColorBits = maxColorBits; Leaves = 0; ReducibleNodes = new OctreeNode[9]; _root = new OctreeNode(0, _maxColorBits, this); _previousColor = 0; _previousNode = null; } public void AddColor(Color32 pixel) { if (_previousColor == pixel.ARGB) { if (_previousNode == null) { _previousColor = pixel.ARGB; _root.AddColor(pixel, _maxColorBits, 0, this); } else _previousNode.Increment(pixel); } else { _previousColor = pixel.ARGB; _root.AddColor(pixel, _maxColorBits, 0, this); } } private void Reduce() { int num = _maxColorBits - 1; while (num > 0 && ReducibleNodes[num] == null) { num--; } OctreeNode octreeNode = ReducibleNodes[num]; ReducibleNodes[num] = octreeNode.NextReducible; Leaves -= octreeNode.Reduce(); _previousNode = null; } protected void TrackPrevious(OctreeNode node) { _previousNode = node; } public ArrayList Palletize(int colorCount) { while (Leaves > colorCount) { Reduce(); } ArrayList arrayList = new ArrayList(Leaves); int paletteIndex = 0; _root.ConstructPalette(arrayList, ref paletteIndex); return arrayList; } public int GetPaletteIndex(Color32 pixel) { return _root.GetPaletteIndex(pixel, 0); } } private readonly int _maxColors; private readonly Octree _octree; public OctreeQuantizer(int maxColors, int maxColorBits) : base(false) { if (maxColors > 255) throw new ArgumentOutOfRangeException("maxColors", maxColors, "The number of colors should be less than 256"); if ((maxColorBits < 1) | (maxColorBits > 8)) throw new ArgumentOutOfRangeException("maxColorBits", maxColorBits, "This should be between 1 and 8"); _octree = new Octree(maxColorBits); _maxColors = maxColors; } protected override void InitialQuantizePixel(Color32 pixel) { _octree.AddColor(pixel); } protected override byte QuantizePixel(Color32 pixel) { byte result = (byte)_maxColors; if (pixel.Alpha > 0) result = (byte)_octree.GetPaletteIndex(pixel); return result; } protected override ColorPalette GetPalette(ColorPalette original) { ArrayList arrayList = _octree.Palletize(_maxColors - 1); for (int i = 0; i < arrayList.Count; i++) { original.Entries[i] = (Color)arrayList[i]; } original.Entries[_maxColors] = Color.FromArgb(0, 0, 0, 0); return original; } } }