[Ohrrpgce] SVN: teeemcee/10535 Huge update to lib/gif.h from my upstream gif.h repo (commit c674b32e)

Thu Aug 30 07:16:00 PDT 2018

teeemcee
2018-08-30 07:15:59 -0700 (Thu, 30 Aug 2018)
7574
Huge update to lib/gif.h from my upstream gif.h repo (commit c674b32e)

Upstream is at https://github.com/rversteegen/gif-h/

This fixes the way that palettes are selected and Floyd-Steinberg dithering is
performed for 32-bit input frames. Previously, the results were atrocious and
flickered badly. This actually was mostly the fault of changes I'd made and others
I'd merged in rather than original upstream.
Also various other fixes and improvements, such as when you resize the window
while recording, and add GifOverwriteLastDelay.

The 23 commits:

commit c674b32e82984fe1d2104ce58c7df3b322be0983
Author: Ralph Versteegen <teeemcee at gmail.com>
Date:   Thu Aug 30 20:56:34 2018 +1200

    If the image size shrinks, erase the parts of the image outside the new frame

commit 96eb38104112cc13ca9d659129bd111e3c0cc028
Author: Ralph Versteegen <teeemcee at gmail.com>
Date:   Thu Aug 30 20:19:12 2018 +1200

    Add GifOverwriteLastDelay function

    In practice, this function is needed whenever the framerate is not constant.

    Based on code by @Bluenaxela, at
    https://github.com/WohlSoft/LunaLua/commit/873932f5dcfcfcb4206638bfcd77f1fba66611ba#diff-174726267941ab7bd442fb0021700c13

commit 90e055daadaa1db8f7b8536da8ac4012f4b5506d
Author: Ralph Versteegen <teeemcee at gmail.com>
Date:   Thu Aug 30 20:10:08 2018 +1200

    Just a little code simplification

commit b0ea7028145562af579aeeee27cdf8090dfa14b5
Author: Ralph Versteegen <teeemcee at gmail.com>
Date:   Thu Aug 30 20:07:22 2018 +1200

    Fix transReplacement color being picked which was equal to kGifTransIndex

commit e4099e38a581e1a786c0b3e19bc466598482f5de
Author: Ralph Versteegen <teeemcee at gmail.com>
Date:   Thu Aug 30 20:05:34 2018 +1200

    Fix node.splitVal being slightly wrong some of the time

commit c3edca26b5765d9e96eb4303fa467ea83e057246
Author: Ralph Versteegen <teeemcee at gmail.com>
Date:   Sat May 26 19:24:09 2018 +1200

    Replace inefficient recursive k-d tree splitting algorithm with the standard algorithm for building a palette

    The difference is that instead of ensuring that each palette colour corresponds
    to equal numbers of pixels with a balanced k-d tree, which is awful if most of
    the image is a single color, the node of the k-d tree which has the largest
    cost (quantisation error) is split. This uses a priority queue instead of
    the simpler recursive splitting.

    The cost metric could probably be improved substantially (variance instead
    of max range?)

commit 3d3cf0ce4d451edfa4fbfbb559924d02d3fa8e39
Author: Ralph Versteegen <teeemcee at gmail.com>
Date:   Sat May 26 19:23:10 2018 +1200

    Minor fixes to comments and whitespace

commit b6f0c99389681e882fa8f3595379a029ede9589b
Author: Ralph Versteegen <teeemcee at gmail.com>
Date:   Wed Jan 3 18:08:50 2018 +1300

    Add a priority queue implementation, GifHeapQueue

commit 0fcf96aacdc652c35e6f0860671541a3390623ed
Author: Ralph Versteegen <teeemcee at gmail.com>
Date:   Mon May 21 21:41:08 2018 +1200

    Add GIF_ASSERT (only used in one place so far)

commit 43483319087059618c78a9bb9816b8d718953086
Author: Ralph Versteegen <teeemcee at gmail.com>
Date:   Tue Jan 2 04:11:56 2018 +1300

    Fix erroneous k-d tree implementation

    The way it was implemented (before and after jacobly0's changes), points lying
    on a splitting hyperplane would be randomly put in either child. But the whole
    point of a k-d tree is that you know which child needs to be checked. Aside from
    being less efficient, it also caused unnecessary mixing of colours. It could
    select a palette of X colours from an image with Y colours, with Y << X.

    So, this provides another speedup to finding the nearest colour.

commit 2805438f237ecdbdc3cd422102800b141ab3a975
Author: Ralph Versteegen <teeemcee at gmail.com>
Date:   Tue Jan 2 04:03:45 2018 +1300

    Fix awful k-d tree bug which meant it failed to find nearest colours and ran ~2x slower

    This was introduced in fa9bdd4f: the splitting hyperplane (component) values
    recorded didn't equal the ones used to construct the tree

commit f7b4324131ca2fece8ea661658dab035807c8e13
Author: Ralph Versteegen <teeemcee at gmail.com>
Date:   Tue Jan 2 03:59:31 2018 +1300

    Fix a bug causing unnecessary GifPartition iterations

    Not too significant though

commit db3791b7e79cb431b55f7d742dc4496334409446
Author: Ralph Versteegen <teeemcee at gmail.com>
Date:   Sun Dec 31 22:32:47 2017 +1300

    Get rid of special case selection of "darkest" and "lightest" colors for the palette when dithering

    No longer needed because color bleeding is properly handled

commit 1d665d9a8282effcdc28ed0f22720e56a0b189e9
Author: Ralph Versteegen <teeemcee at gmail.com>
Date:   Sun Dec 31 20:25:38 2017 +1300

    Shift k-d tree stuff from GifPalette to new structs GifKDTree and GifKDNode

commit f01c982c43ec60e7db534a4e0ff7aaadd15b06df
Author: Ralph Versteegen <teeemcee at gmail.com>
Date:   Sat Dec 30 23:24:14 2017 +1300

    Fix nondeterministic results due to reading uninitialised memory

    This only happened if less than a full palette was selected, and a leaf node
    was unused but its parent node was used.

commit 95aaf24fd00252f947962f2db05dedcb44fffdf8
Author: Ralph Versteegen <teeemcee at gmail.com>
Date:   Sun Dec 31 16:50:44 2017 +1300

    Only diffuse 87.5% of the error in Floyd-Steinberg. This removes the remaining colour bleeding

    Also, this leads to less speckling occurring due to having to mix dissimilar
    colours to get the target colour.
    However, removal of these speckles change will increase image contrast.

commit 41b20a7ce6abb2807832f7e4f854e283a81ff213
Author: Ralph Versteegen <teeemcee at gmail.com>
Date:   Sun Dec 31 16:49:46 2017 +1300

    An optimisation

commit fef293fbd9179d40cfcdd32fd458301badbbb2a6
Author: Ralph Versteegen <teeemcee at gmail.com>
Date:   Sun Dec 31 15:43:32 2017 +1300

    GifPalette now has an array of GifRGBA colors instead of separate r, g, b

    Simpler and better locality, so probably faster

    Also, this fixes a major bug which occurs if you try to reorder the components
    of GifRGBA, where GifGetClosestPaletteColor often failed to give the right
    answer

commit 75cda0869bcb985962a7a23957a222cd5c711725
Author: Ralph Versteegen <teeemcee at gmail.com>
Date:   Sun Dec 31 00:03:45 2017 +1300

    Fix most of the color bleeding by capping values in the dithering accumulation buffer above instead of just below

    Also, cap values only the end instead of after each accumulation; both faster
    and fixes even more artifacts.
    But allow values to go a bit below 0 and above 255 (controlled by kAccumMargin,
    which I set to 64 but I didn't experiment with different values), so as to not
    throw away large errors. This seems to improve results.

commit 9eca45737a9a36ed2e9d98ca1bb4874dba346299
Author: Ralph Versteegen <teeemcee at gmail.com>
Date:   Sat Dec 30 23:22:24 2017 +1300

    Compile-time option to collect and print statistics on the quality of the palette

commit a72561b2439bf845b7f49f9ee3b374efc9ade916
Author: Ralph Versteegen <teeemcee at gmail.com>
Date:   Sun Dec 31 00:35:36 2017 +1300

    Fix GifRGBA.comps() not allowing reordering of RGBA, and was unnecessarily slow

commit 8c14ddf2ccb1dc21676b3dd1f27498fceebf1ca4
Merge: 9a3c4dd 465cc02
Author: rversteegen <teeemcee at gmail.com>
Date:   Mon Dec 25 11:48:29 2017 +1300

    Merge pull request #1 from Wohlstand/rversteegen

    Warnings fixes

commit 465cc02a499c1a9452a1d126c6a552370d3eb884
Author: Vitaly Novichkov <admin at wohlnet.ru>
Date:   Mon Dec 25 01:38:42 2017 +0300

    Warning fixes
---
U   wip/lib/gif.h