gpalopt.cpp

Go to the documentation of this file.
00001 // $Id: gpalopt.cpp 809 2006-04-13 11:28:42Z phil $
00003 //
00004 // PalOpt.cpp
00005 //
00007 /* @@tag:xara-cn@@ DO NOT MODIFY THIS LINE
00008 ================================XARAHEADERSTART===========================
00009  
00010                Xara LX, a vector drawing and manipulation program.
00011                     Copyright (C) 1993-2006 Xara Group Ltd.
00012        Copyright on certain contributions may be held in joint with their
00013               respective authors. See AUTHORS file for details.
00014 
00015 LICENSE TO USE AND MODIFY SOFTWARE
00016 ----------------------------------
00017 
00018 This file is part of Xara LX.
00019 
00020 Xara LX is free software; you can redistribute it and/or modify it
00021 under the terms of the GNU General Public License version 2 as published
00022 by the Free Software Foundation.
00023 
00024 Xara LX and its component source files are distributed in the hope
00025 that it will be useful, but WITHOUT ANY WARRANTY; without even the
00026 implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
00027 See the GNU General Public License for more details.
00028 
00029 You should have received a copy of the GNU General Public License along
00030 with Xara LX (see the file GPL in the root directory of the
00031 distribution); if not, write to the Free Software Foundation, Inc., 51
00032 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
00033 
00034 
00035 ADDITIONAL RIGHTS
00036 -----------------
00037 
00038 Conditional upon your continuing compliance with the GNU General Public
00039 License described above, Xara Group Ltd grants to you certain additional
00040 rights. 
00041 
00042 The additional rights are to use, modify, and distribute the software
00043 together with the wxWidgets library, the wxXtra library, and the "CDraw"
00044 library and any other such library that any version of Xara LX relased
00045 by Xara Group Ltd requires in order to compile and execute, including
00046 the static linking of that library to XaraLX. In the case of the
00047 "CDraw" library, you may satisfy obligation under the GNU General Public
00048 License to provide source code by providing a binary copy of the library
00049 concerned and a copy of the license accompanying it.
00050 
00051 Nothing in this section restricts any of the rights you have under
00052 the GNU General Public License.
00053 
00054 
00055 SCOPE OF LICENSE
00056 ----------------
00057 
00058 This license applies to this program (XaraLX) and its constituent source
00059 files only, and does not necessarily apply to other Xara products which may
00060 in part share the same code base, and are subject to their own licensing
00061 terms.
00062 
00063 This license does not apply to files in the wxXtra directory, which
00064 are built into a separate library, and are subject to the wxWindows
00065 license contained within that directory in the file "WXXTRA-LICENSE".
00066 
00067 This license does not apply to the binary libraries (if any) within
00068 the "libs" directory, which are subject to a separate license contained
00069 within that directory in the file "LIBS-LICENSE".
00070 
00071 
00072 ARRANGEMENTS FOR CONTRIBUTION OF MODIFICATIONS
00073 ----------------------------------------------
00074 
00075 Subject to the terms of the GNU Public License (see above), you are
00076 free to do whatever you like with your modifications. However, you may
00077 (at your option) wish contribute them to Xara's source tree. You can
00078 find details of how to do this at:
00079   http://www.xaraxtreme.org/developers/
00080 
00081 Prior to contributing your modifications, you will need to complete our
00082 contributor agreement. This can be found at:
00083   http://www.xaraxtreme.org/developers/contribute/
00084 
00085 Please note that Xara will not accept modifications which modify any of
00086 the text between the start and end of this header (marked
00087 XARAHEADERSTART and XARAHEADEREND).
00088 
00089 
00090 MARKS
00091 -----
00092 
00093 Xara, Xara LX, Xara X, Xara X/Xtreme, Xara Xtreme, the Xtreme and Xara
00094 designs are registered or unregistered trademarks, design-marks, and/or
00095 service marks of Xara Group Ltd. All rights in these marks are reserved.
00096 
00097 
00098       Xara Group Ltd, Gaddesden Place, Hemel Hempstead, HP2 6EX, UK.
00099                         http://www.xara.com/
00100 
00101 =================================XARAHEADEREND============================
00102  */
00103 
00104 #include "camtypes.h"
00105 
00106 #include "gpalopt.h"
00107 
00108 //#include <stdlib.h>
00109 
00110 #pragma warning ( disable : 4554 )
00111 
00112 /***************************************************************************/
00113 
00114 inline PALETTEENTRY peRGB( cBYTE r,cBYTE g,cBYTE b, cBYTE f=0 )
00115 {
00116     PALETTEENTRY q = {r,g,b, f} ;
00117     return q ;
00118 }
00119 
00120 /***************************************************************************/
00121 
00122 cBYTE PaletteOptimiser::aSnap[0x132] = {
00123                                        0x00, 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
00124     0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00, 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
00125 
00126     0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00, 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
00127     0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00, 0x00,0x00,0x33,0x33,0x33,0x33,0x33,0x33,
00128     0x33,0x33,0x33,0x33,0x33,0x33,0x33,0x33, 0x33,0x33,0x33,0x33,0x33,0x33,0x33,0x33,
00129     0x33,0x33,0x33,0x33,0x33,0x33,0x33,0x33, 0x33,0x33,0x33,0x33,0x33,0x33,0x33,0x33,
00130     0x33,0x33,0x33,0x33,0x33,0x33,0x33,0x33, 0x33,0x33,0x33,0x33,0x33,0x66,0x66,0x66,
00131     0x66,0x66,0x66,0x66,0x66,0x66,0x66,0x66, 0x66,0x66,0x66,0x66,0x66,0x66,0x66,0x66,
00132     0x66,0x66,0x66,0x66,0x66,0x66,0x66,0x66, 0x66,0x66,0x66,0x66,0x66,0x66,0x66,0x66,
00133     0x66,0x66,0x66,0x66,0x66,0x66,0x66,0x66, 0x66,0x66,0x66,0x66,0x66,0x66,0x66,0x66,
00134     0x99,0x99,0x99,0x99,0x99,0x99,0x99,0x99, 0x99,0x99,0x99,0x99,0x99,0x99,0x99,0x99,
00135     0x99,0x99,0x99,0x99,0x99,0x99,0x99,0x99, 0x99,0x99,0x99,0x99,0x99,0x99,0x99,0x99,
00136     0x99,0x99,0x99,0x99,0x99,0x99,0x99,0x99, 0x99,0x99,0x99,0x99,0x99,0x99,0x99,0x99,
00137     0x99,0x99,0x99,0xCC,0xCC,0xCC,0xCC,0xCC, 0xCC,0xCC,0xCC,0xCC,0xCC,0xCC,0xCC,0xCC,
00138     0xCC,0xCC,0xCC,0xCC,0xCC,0xCC,0xCC,0xCC, 0xCC,0xCC,0xCC,0xCC,0xCC,0xCC,0xCC,0xCC,
00139     0xCC,0xCC,0xCC,0xCC,0xCC,0xCC,0xCC,0xCC, 0xCC,0xCC,0xCC,0xCC,0xCC,0xCC,0xCC,0xCC,
00140     0xCC,0xCC,0xCC,0xCC,0xCC,0xCC,0xFF,0xFF, 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
00141     0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF, 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
00142 
00143     0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF, 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
00144     0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF, 0xFF
00145 } ;
00146 
00147 #define S(n) 0x##n*0x##n
00148 
00149 const UINT32 PaletteOptimiser::aBDist[0x100] = {
00150     S(00),S(01),S(02),S(03),S(04),S(05),S(06),S(07), S(08),S(09),S(0a),S(0b),S(0c),S(0d),S(0e),S(0f),
00151     S(10),S(11),S(12),S(13),S(14),S(15),S(16),S(17), S(18),S(19),S(19),S(18),S(17),S(16),S(15),S(14),
00152     S(13),S(12),S(11),S(10),S(0f),S(0e),S(0d),S(0c), S(0b),S(0a),S(09),S(08),S(07),S(06),S(05),S(04),
00153     S(03),S(02),S(01),S(00),S(01),S(02),S(03),S(04), S(05),S(06),S(07),S(08),S(09),S(0a),S(0b),S(0c),
00154     S(0d),S(0e),S(0f),S(10),S(11),S(12),S(13),S(14), S(15),S(16),S(17),S(18),S(19),S(19),S(18),S(17),
00155     S(16),S(15),S(14),S(13),S(12),S(11),S(10),S(0f), S(0e),S(0d),S(0c),S(0b),S(0a),S(09),S(08),S(07),
00156     S(06),S(05),S(04),S(03),S(02),S(01),S(00),S(01), S(02),S(03),S(04),S(05),S(06),S(07),S(08),S(09),
00157     S(0a),S(0b),S(0c),S(0d),S(0e),S(0f),S(10),S(11), S(12),S(13),S(14),S(15),S(16),S(17),S(18),S(19),
00158     S(19),S(18),S(17),S(16),S(15),S(14),S(13),S(12), S(11),S(10),S(0f),S(0e),S(0d),S(0c),S(0b),S(0a),
00159     S(09),S(08),S(07),S(06),S(05),S(04),S(03),S(02), S(01),S(00),S(01),S(02),S(03),S(04),S(05),S(06),
00160     S(07),S(08),S(09),S(0a),S(0b),S(0c),S(0d),S(0e), S(0f),S(10),S(11),S(12),S(13),S(14),S(15),S(16),
00161     S(17),S(18),S(19),S(19),S(18),S(17),S(16),S(15), S(14),S(13),S(12),S(11),S(10),S(0f),S(0e),S(0d),
00162     S(0c),S(0b),S(0a),S(09),S(08),S(07),S(06),S(05), S(04),S(03),S(02),S(01),S(00),S(01),S(02),S(03),
00163     S(04),S(05),S(06),S(07),S(08),S(09),S(0a),S(0b), S(0c),S(0d),S(0e),S(0f),S(10),S(11),S(12),S(13),
00164     S(14),S(15),S(16),S(17),S(18),S(19),S(19),S(18), S(17),S(16),S(15),S(14),S(13),S(12),S(11),S(10),
00165     S(0f),S(0e),S(0d),S(0c),S(0b),S(0a),S(09),S(08), S(07),S(06),S(05),S(04),S(03),S(02),S(01),S(00)
00166 } ;
00167 
00168 const UINT32 PaletteOptimiser::aPDist[0x100] = {
00169     S(00),S(01),S(02),S(03),S(04),S(05),S(06),S(07), S(08),S(09),S(0a),S(0b),S(0c),S(0d),S(0e),S(0f),
00170     S(10),S(11),S(12),S(13),S(14),S(15),S(16),S(17), S(18),S(19),S(1a),S(1b),S(1c),S(1d),S(1e),S(1f),
00171     S(20),S(21),S(22),S(23),S(24),S(25),S(26),S(27), S(28),S(29),S(2a),S(2b),S(2c),S(2d),S(2e),S(2f),
00172     S(30),S(31),S(32),S(33),S(34),S(35),S(36),S(37), S(38),S(39),S(3a),S(3b),S(3c),S(3d),S(3e),S(3f),
00173     S(40),S(41),S(42),S(43),S(44),S(45),S(46),S(47), S(48),S(49),S(4a),S(4b),S(4c),S(4d),S(4e),S(4f),
00174     S(50),S(51),S(52),S(53),S(54),S(55),S(56),S(57), S(58),S(59),S(5a),S(5b),S(5c),S(5d),S(5e),S(5f),
00175     S(60),S(61),S(62),S(63),S(64),S(65),S(66),S(67), S(68),S(69),S(6a),S(6b),S(6c),S(6d),S(6e),S(6f),
00176     S(70),S(71),S(72),S(73),S(74),S(75),S(76),S(77), S(78),S(79),S(7a),S(7b),S(7c),S(7d),S(7e),S(7f),
00177     S(7f),S(7e),S(7d),S(7c),S(7b),S(7a),S(79),S(78), S(77),S(76),S(75),S(74),S(73),S(72),S(71),S(70),
00178     S(6f),S(6e),S(6d),S(6c),S(6b),S(6a),S(69),S(68), S(67),S(66),S(65),S(64),S(63),S(62),S(61),S(60),
00179     S(5f),S(5e),S(5d),S(5c),S(5b),S(5a),S(59),S(58), S(57),S(56),S(55),S(54),S(53),S(52),S(51),S(50),
00180     S(4f),S(4e),S(4d),S(4c),S(4b),S(4a),S(49),S(48), S(47),S(46),S(45),S(44),S(43),S(42),S(41),S(40),
00181     S(3f),S(3e),S(3d),S(3c),S(3b),S(3a),S(39),S(38), S(37),S(36),S(35),S(34),S(33),S(32),S(31),S(30),
00182     S(2f),S(2e),S(2d),S(2c),S(2b),S(2a),S(29),S(28), S(27),S(26),S(25),S(24),S(23),S(22),S(21),S(20),
00183     S(1f),S(1e),S(1d),S(1c),S(1b),S(1a),S(19),S(18), S(17),S(16),S(15),S(14),S(13),S(12),S(11),S(10),
00184     S(0f),S(0e),S(0d),S(0c),S(0b),S(0a),S(09),S(08), S(07),S(06),S(05),S(04),S(03),S(02),S(01),S(00)
00185 } ;
00186 
00187 const UINT32 PaletteOptimiser::aSqrs[0x100] = {
00188     S(00),S(01),S(02),S(03),S(04),S(05),S(06),S(07), S(08),S(09),S(0a),S(0b),S(0c),S(0d),S(0e),S(0f),
00189     S(10),S(11),S(12),S(13),S(14),S(15),S(16),S(17), S(18),S(19),S(1a),S(1b),S(1c),S(1d),S(1e),S(1f),
00190     S(20),S(21),S(22),S(23),S(24),S(25),S(26),S(27), S(28),S(29),S(2a),S(2b),S(2c),S(2d),S(2e),S(2f),
00191     S(30),S(31),S(32),S(33),S(34),S(35),S(36),S(37), S(38),S(39),S(3a),S(3b),S(3c),S(3d),S(3e),S(3f),
00192     S(40),S(41),S(42),S(43),S(44),S(45),S(46),S(47), S(48),S(49),S(4a),S(4b),S(4c),S(4d),S(4e),S(4f),
00193     S(50),S(51),S(52),S(53),S(54),S(55),S(56),S(57), S(58),S(59),S(5a),S(5b),S(5c),S(5d),S(5e),S(5f),
00194     S(60),S(61),S(62),S(63),S(64),S(65),S(66),S(67), S(68),S(69),S(6a),S(6b),S(6c),S(6d),S(6e),S(6f),
00195     S(70),S(71),S(72),S(73),S(74),S(75),S(76),S(77), S(78),S(79),S(7a),S(7b),S(7c),S(7d),S(7e),S(7f),
00196     S(80),S(81),S(82),S(83),S(84),S(85),S(86),S(87), S(88),S(89),S(8a),S(8b),S(8c),S(8d),S(8e),S(8f),
00197     S(90),S(91),S(92),S(93),S(94),S(95),S(96),S(97), S(98),S(99),S(9a),S(9b),S(9c),S(9d),S(9e),S(9f),
00198     S(a0),S(a1),S(a2),S(a3),S(a4),S(a5),S(a6),S(a7), S(a8),S(a9),S(aa),S(ab),S(ac),S(ad),S(ae),S(af),
00199     S(b0),S(b1),S(b2),S(b3),S(b4),S(b5),S(b6),S(b7), S(b8),S(b9),S(ba),S(bb),S(bc),S(bd),S(be),S(bf),
00200     S(c0),S(c1),S(c2),S(c3),S(c4),S(c5),S(c6),S(c7), S(c8),S(c9),S(ca),S(cb),S(cc),S(cd),S(ce),S(cf),
00201     S(d0),S(d1),S(d2),S(d3),S(d4),S(d5),S(d6),S(d7), S(d8),S(d9),S(da),S(db),S(dc),S(dd),S(de),S(df),
00202     S(e0),S(e1),S(e2),S(e3),S(e4),S(e5),S(e6),S(e7), S(e8),S(e9),S(ea),S(eb),S(ec),S(ed),S(ee),S(ef),
00203     S(f0),S(f1),S(f2),S(f3),S(f4),S(f5),S(f6),S(f7), S(f8),S(f9),S(fa),S(fb),S(fc),S(fd),S(fe),S(ff)
00204 } ;
00205 
00206 #undef S
00207 
00209 //
00210 // Call this function prior to calling AddStats the first time.
00211 // It initialises the statistics tables.
00212 //
00213 void PaletteOptimiser::Initialise()
00214 {
00215     for ( UINT32 i=0 ; i<AXIS3 ; i++ )
00216         m_aStats[i].W =
00217         m_aStats[i].R =
00218         m_aStats[i].G =
00219         m_aStats[i].B =
00220         m_aStats[i].S = 0.0 ;
00221 
00222     m_bMoments = false ;
00223     m_uTotalColours   =
00224     m_uPaletteEntries = 0 ;
00225 }
00226 
00228 //
00229 // This function processes the pixels of a bitmap and adds variaus statistics
00230 // to the internal tables. This function called be called several times, once
00231 // for each strip of a bitmap. Call Initialise prior to the first call to
00232 // this function to initialise the statistics tables.
00233 //
00234 //      pBitmap - pointer to bitmap
00235 //      nSize   - size of bitmap
00236 //
00237 void PaletteOptimiser::AddStats( cpcRGBQUAD pBitmap, cUINT32 uSize )
00238 {
00239     ASSERT(pBitmap) ;
00240     ASSERT(uSize) ;
00241     //
00242     // Determine the number of colours used within the bitmap
00243     //
00244     UINT32 i ;
00245     if ( m_uTotalColours<=MAXCOLOURS )
00246         for ( i=0 ; i<uSize ; i++ )
00247             if ( (DWORD&)pBitmap[i]<0xff000000u )
00248             {
00249                 cDWORD d = (DWORD&)pBitmap[i] & 0x00ffffff ;
00250                 for( UINT32 j=0 ; j<m_uTotalColours ; j++ )
00251                     if ( d==(DWORD&)m_aColours[j] )
00252                     {
00253                         m_aCount[j]++ ;
00254                         goto found ;
00255                     }
00256                 m_aColours[m_uTotalColours++] = (RGBQUAD&)d ;
00257                 if ( m_uTotalColours>MAXCOLOURS )
00258                     break ;
00259         found:  ;
00260             }
00261     //
00262     // Compile image statistics.
00263     //
00264     for ( i=0 ; i<uSize ; i++ )
00265         if ( pBitmap[i].rgbReserved!=0xff )
00266         {
00267             static cBYTE aIndex[0x100] = {
00268                 0x01,0x01,0x01,0x01,0x01,0x02,0x02,0x02, 0x02,0x02,0x02,0x02,0x02,0x03,0x03,0x03,
00269                 0x03,0x03,0x03,0x03,0x03,0x04,0x04,0x04, 0x04,0x04,0x04,0x04,0x04,0x05,0x05,0x05,
00270                 0x05,0x05,0x05,0x05,0x05,0x05,0x06,0x06, 0x06,0x06,0x06,0x06,0x06,0x06,0x07,0x07,
00271                 0x07,0x07,0x07,0x07,0x07,0x07,0x08,0x08, 0x08,0x08,0x08,0x08,0x08,0x08,0x09,0x09,
00272                 0x09,0x09,0x09,0x09,0x09,0x09,0x0A,0x0A, 0x0A,0x0A,0x0A,0x0A,0x0A,0x0A,0x0A,0x0B,
00273                 0x0B,0x0B,0x0B,0x0B,0x0B,0x0B,0x0B,0x0C, 0x0C,0x0C,0x0C,0x0C,0x0C,0x0C,0x0C,0x0D,
00274                 0x0D,0x0D,0x0D,0x0D,0x0D,0x0D,0x0D,0x0E, 0x0E,0x0E,0x0E,0x0E,0x0E,0x0E,0x0E,0x0E,
00275                 0x0F,0x0F,0x0F,0x0F,0x0F,0x0F,0x0F,0x0F, 0x10,0x10,0x10,0x10,0x10,0x10,0x10,0x10,
00276                 0x11,0x11,0x11,0x11,0x11,0x11,0x11,0x11, 0x12,0x12,0x12,0x12,0x12,0x12,0x12,0x12,
00277                 0x13,0x13,0x13,0x13,0x13,0x13,0x13,0x13, 0x13,0x14,0x14,0x14,0x14,0x14,0x14,0x14,
00278                 0x14,0x15,0x15,0x15,0x15,0x15,0x15,0x15, 0x15,0x16,0x16,0x16,0x16,0x16,0x16,0x16,
00279                 0x16,0x17,0x17,0x17,0x17,0x17,0x17,0x17, 0x17,0x17,0x18,0x18,0x18,0x18,0x18,0x18,
00280                 0x18,0x18,0x19,0x19,0x19,0x19,0x19,0x19, 0x19,0x19,0x1A,0x1A,0x1A,0x1A,0x1A,0x1A,
00281                 0x1A,0x1A,0x1B,0x1B,0x1B,0x1B,0x1B,0x1B, 0x1B,0x1B,0x1C,0x1C,0x1C,0x1C,0x1C,0x1C,
00282                 0x1C,0x1C,0x1C,0x1D,0x1D,0x1D,0x1D,0x1D, 0x1D,0x1D,0x1D,0x1E,0x1E,0x1E,0x1E,0x1E,
00283                 0x1E,0x1E,0x1E,0x1F,0x1F,0x1F,0x1F,0x1F, 0x1F,0x1F,0x1F,0x20,0x20,0x20,0x20,0x20
00284             } ;
00285             cUINT32 r = pBitmap[i].rgbRed ;
00286             cUINT32 g = pBitmap[i].rgbGreen ;
00287             cUINT32 b = pBitmap[i].rgbBlue ;
00288             cpStats p = m_aStats+(aIndex[r]*AXIS+aIndex[g])*AXIS+aIndex[b] ;
00289             p->W++ ;
00290             p->R += r ;
00291             p->G += g ;
00292             p->B += b ;
00293             p->S += aSqrs[r]+aSqrs[g]+aSqrs[b] ;
00294         }
00295 }
00296 
00298 //
00299 // Call this function to add a locked colour. Locked colours are always added
00300 // first to the optimal palette, but the order of the locked colours is not
00301 // relevant.
00302 //
00303 void PaletteOptimiser::AddLockedColour( cBYTE red,cBYTE green,cBYTE blue )
00304 {
00305     ASSERT(m_uLockedColours<0x100) ;
00306     m_aLockedColours[m_uLockedColours].peRed   = red   ;
00307     m_aLockedColours[m_uLockedColours].peGreen = green ;
00308     m_aLockedColours[m_uLockedColours].peBlue  = blue  ;
00309     m_uLockedColours++ ;
00310 }
00311 
00313 
00314 void PaletteOptimiser::Moments3D()
00315 {
00316     double lineW,areaW[AXIS] ;
00317     double lineR,areaR[AXIS] ;
00318     double lineG,areaG[AXIS] ;
00319     double lineB,areaB[AXIS] ;
00320     double lineS,areaS[AXIS] ;
00321 
00322     for ( UINT32 r=1 ; r<AXIS ; ++r )
00323     {
00324         for ( UINT32 i=0 ; i<AXIS ; ++i ) 
00325             areaW[i] = areaR[i] = areaG[i] = areaB[i] = areaS[i] = 0.0 ;
00326         for ( UINT32 g=1 ; g<AXIS ; ++g )
00327         {
00328             lineW = lineR = lineG = lineB = lineS = 0.0 ;
00329 
00330             pStats p = m_aStats+(r*AXIS+g)*AXIS ;    // [r][g][b]
00331             for ( UINT32 b=1 ; b<AXIS ; ++b )
00332             {
00333                 p++ ;
00334                 p->W = p[-AXIS2].W+(areaW[b]+=lineW+=p->W) ;    // ind-AXIS2 = [r-1][g][b]
00335                 p->R = p[-AXIS2].R+(areaR[b]+=lineR+=p->R) ;
00336                 p->G = p[-AXIS2].G+(areaG[b]+=lineG+=p->G) ;
00337                 p->B = p[-AXIS2].B+(areaB[b]+=lineB+=p->B) ;
00338                 p->S = p[-AXIS2].S+(areaS[b]+=lineS+=p->S) ;
00339             }
00340         }
00341     }
00342 }
00343 
00345 
00346 double PaletteOptimiser::Snap( cpBox pCube, cDOUBLE halfW,cDOUBLE halfR,cDOUBLE halfG,cDOUBLE halfB )
00347 {
00348     static cUINT32 aIndex[0x21] = {
00349         0x00,0x05,0x0D,0x15, 0x1D,0x26,0x2E,0x36,
00350         0x3E,0x46,0x4F,0x57, 0x5F,0x67,0x70,0x78,
00351         0x80,0x88,0x90,0x99, 0xA1,0xA9,0xB1,0xBA,
00352         0xC2,0xCA,0xD2,0xDA, 0xE3,0xEB,0xF3,0xFB, 0x100
00353     } ;
00354 
00355     if ( m_uAllLockedColours )
00356     {
00357         double max = -1e100 ;
00358         for ( UINT32 i=0 ; i<m_uAllLockedColours ; i++ )
00359         {
00360             Clr C = {
00361                 m_aLockedColours[i].peRed,
00362                 m_aLockedColours[i].peGreen,
00363                 m_aLockedColours[i].peBlue
00364             } ;
00365             if ( aIndex[pCube->r0]<=C.r && aIndex[pCube->r1]>C.r &&
00366                  aIndex[pCube->g0]<=C.g && aIndex[pCube->g1]>C.g &&
00367                  aIndex[pCube->b0]<=C.b && aIndex[pCube->b1]>C.b )
00368             {
00369                 cDOUBLE temp = 2*(halfR*C.r+halfG*C.g+halfB*C.b)-(C.r*C.r+C.g*C.g+C.b*C.b)*halfW ;
00370                 if ( max<temp )
00371                 {
00372                     max = temp ;
00373                     pCube->clr = C ;
00374                 }
00375             }
00376         }
00377         if ( max>-1e50 )
00378             return max ;
00379     }
00380 
00381     if ( halfW==0 )
00382         return -1e100 ;
00383     cDOUBLE invW = 1/halfW ;
00384     pCube->clr.r = (UINT32)(halfR*invW+0.5) ;
00385     pCube->clr.g = (UINT32)(halfG*invW+0.5) ;
00386     pCube->clr.b = (UINT32)(halfB*invW+0.5) ;
00387 
00388     if ( m_bUseBrowserPalette )
00389     {
00390         double max = -1e100 ;
00391         Clr C ;
00392         for (         C.r=aSnap[pCube->clr.r] ; C.r<=aSnap[pCube->clr.r+0x32] ; C.r+=0x33 )
00393             for (     C.g=aSnap[pCube->clr.g] ; C.g<=aSnap[pCube->clr.g+0x32] ; C.g+=0x33 )
00394                 for ( C.b=aSnap[pCube->clr.b] ; C.b<=aSnap[pCube->clr.b+0x32] ; C.b+=0x33 )
00395                     if ( aIndex[pCube->r0]<=C.r && aIndex[pCube->r1]>C.r &&
00396                          aIndex[pCube->g0]<=C.g && aIndex[pCube->g1]>C.g &&
00397                          aIndex[pCube->b0]<=C.b && aIndex[pCube->b1]>C.b )
00398                     {
00399                         cDOUBLE temp = 2*(halfR*C.r+halfG*C.g+halfB*C.b)-(C.r*C.r+C.g*C.g+C.b*C.b)*halfW ;
00400                         if ( max<temp )
00401                         {
00402                             max = temp ;
00403                             pCube->clr = C ;
00404                         }
00405                     }
00406         return max ;
00407     }
00408     if ( m_uSnapToBrowserPalette )
00409     {
00410         if ( aBDist[pCube->clr.r]+aBDist[pCube->clr.g]+aBDist[pCube->clr.b] <= m_uSnapToBrowserPalette2 )
00411         {
00412             Clr C = {
00413                 aSnap[pCube->clr.r+0x19],
00414                 aSnap[pCube->clr.g+0x19],
00415                 aSnap[pCube->clr.b+0x19]
00416             } ;
00417             if ( aIndex[pCube->r0]<=C.r && aIndex[pCube->r1]>C.r &&
00418                  aIndex[pCube->g0]<=C.g && aIndex[pCube->g1]>C.g &&
00419                  aIndex[pCube->b0]<=C.b && aIndex[pCube->b1]>C.b )
00420             {
00421                 pCube->clr = C ;
00422                 return 2*(halfR*C.r+halfG*C.g+halfB*C.b)-(C.r*C.r+C.g*C.g+C.b*C.b)*halfW ;
00423             }
00424         }
00425     }
00426     if ( m_uSnapToPrimaries )
00427     {
00428         if ( aPDist[pCube->clr.r]+aPDist[pCube->clr.g]+aPDist[pCube->clr.b] <= m_uSnapToPrimaries2 )
00429         {
00430             Clr C = {
00431                 pCube->clr.r<0x80 ? 0x00 : 0xFF,
00432                 pCube->clr.g<0x80 ? 0x00 : 0xFF,
00433                 pCube->clr.b<0x80 ? 0x00 : 0xFF,
00434             } ;
00435             if ( aIndex[pCube->r0]<=C.r && aIndex[pCube->r1]>C.r &&
00436                  aIndex[pCube->g0]<=C.g && aIndex[pCube->g1]>C.g &&
00437                  aIndex[pCube->b0]<=C.b && aIndex[pCube->b1]>C.b )
00438             {
00439                 pCube->clr = C ;
00440                 return 2*(halfR*C.r+halfG*C.g+halfB*C.b)-(C.r*C.r+C.g*C.g+C.b*C.b)*halfW ;
00441             }
00442         }
00443     }
00444     return (halfR*halfR+halfG*halfG+halfB*halfB)*invW ;
00445 }
00446 
00448 
00449 double PaletteOptimiser::Vol( cpcBox pCube, double Stats::* p ) const
00450 {
00451     return +LCube(p,pCube->r1,pCube->g1,pCube->b1)
00452            -LCube(p,pCube->r1,pCube->g1,pCube->b0)
00453            -LCube(p,pCube->r1,pCube->g0,pCube->b1)
00454            +LCube(p,pCube->r1,pCube->g0,pCube->b0)
00455            -LCube(p,pCube->r0,pCube->g1,pCube->b1)
00456            +LCube(p,pCube->r0,pCube->g1,pCube->b0)
00457            +LCube(p,pCube->r0,pCube->g0,pCube->b1)
00458            -LCube(p,pCube->r0,pCube->g0,pCube->b0) ;
00459 }
00460 
00461 double PaletteOptimiser::Bottom( cpcBox pCube, cUINT32 dir, double Stats::* p ) const
00462 {
00463     switch (dir)
00464     {
00465     case RED :   return +LCube(p,pCube->r0,pCube->g1,pCube->b0)
00466                         +LCube(p,pCube->r0,pCube->g0,pCube->b1)
00467                         -LCube(p,pCube->r0,pCube->g1,pCube->b1)
00468                         -LCube(p,pCube->r0,pCube->g0,pCube->b0) ;
00469     case GREEN : return +LCube(p,pCube->r1,pCube->g0,pCube->b0)
00470                         +LCube(p,pCube->r0,pCube->g0,pCube->b1)
00471                         -LCube(p,pCube->r1,pCube->g0,pCube->b1)
00472                         -LCube(p,pCube->r0,pCube->g0,pCube->b0) ;
00473     case BLUE :  return +LCube(p,pCube->r1,pCube->g0,pCube->b0)
00474                         +LCube(p,pCube->r0,pCube->g1,pCube->b0)
00475                         -LCube(p,pCube->r1,pCube->g1,pCube->b0)
00476                         -LCube(p,pCube->r0,pCube->g0,pCube->b0) ;
00477     }
00478     ASSERT(false) ;
00479     return 0 ;
00480 }
00481 
00482 double PaletteOptimiser::Top( cpcBox pCube, cUINT32 dir, cUINT32 pos, double Stats::* p ) const
00483 {
00484     switch (dir)
00485     {
00486     case RED :   return +LCube(p,pos,pCube->g1,pCube->b1)
00487                         +LCube(p,pos,pCube->g0,pCube->b0) 
00488                         -LCube(p,pos,pCube->g1,pCube->b0)
00489                         -LCube(p,pos,pCube->g0,pCube->b1) ;
00490     case GREEN : return +LCube(p,pCube->r1,pos,pCube->b1)
00491                         +LCube(p,pCube->r0,pos,pCube->b0) 
00492                         -LCube(p,pCube->r1,pos,pCube->b0)
00493                         -LCube(p,pCube->r0,pos,pCube->b1) ;
00494     case BLUE :  return +LCube(p,pCube->r1,pCube->g1,pos)
00495                         +LCube(p,pCube->r0,pCube->g0,pos)
00496                         -LCube(p,pCube->r1,pCube->g0,pos)
00497                         -LCube(p,pCube->r0,pCube->g1,pos) ;
00498     }
00499     ASSERT(false) ;
00500     return 0 ;
00501 }
00502 
00503 double PaletteOptimiser::Var( cpcBox pCube ) const
00504 {
00505     cDOUBLE ww = Vol(pCube,&Stats::W) ;
00506     cDOUBLE dr = Vol(pCube,&Stats::R) ;
00507     cDOUBLE dg = Vol(pCube,&Stats::G) ;
00508     cDOUBLE db = Vol(pCube,&Stats::B) ;
00509     cDOUBLE xx = Vol(pCube,&Stats::S) ;
00510     return xx+(pCube->clr.r*pCube->clr.r+pCube->clr.g*pCube->clr.g+pCube->clr.b*pCube->clr.b)*ww
00511            -2*(pCube->clr.r*dr          +pCube->clr.g*dg          +pCube->clr.b*db) ;
00512 }
00513 
00515 
00516 double PaletteOptimiser::Maximize(
00517                             cpBox pCube, 
00518                             cUINT32 dir, 
00519                             cUINT32 first,
00520                             cUINT32 last,
00521                             cpBox pCube1,
00522                             cpBox pCube2,
00523                             cDOUBLE wholeW,
00524                             cDOUBLE wholeR,
00525                             cDOUBLE wholeG,
00526                             cDOUBLE wholeB
00527                         )
00528 {
00529     cDOUBLE baseW = Bottom(pCube,dir,&Stats::W) ;
00530     cDOUBLE baseR = Bottom(pCube,dir,&Stats::R) ;
00531     cDOUBLE baseG = Bottom(pCube,dir,&Stats::G) ;
00532     cDOUBLE baseB = Bottom(pCube,dir,&Stats::B) ;
00533 
00534     Box cube1,cube2 ;
00535     cube1 = cube2 = *pCube ;
00536 
00537     double max = -1e100 ;
00538 
00539     //  Did the bottom of the pCube above.
00540     for ( UINT32 i=first+1 ; i<last ; ++i )
00541     {
00542         switch (dir)
00543         {
00544         case RED   : cube1.r1 = cube2.r0 = i ; break ;
00545         case GREEN : cube1.g1 = cube2.g0 = i ; break ;
00546         case BLUE  : cube1.b1 = cube2.b0 = i ; break ;
00547         }
00548         // Now half_x is sum over lower half of box, if split at i.
00549         double halfW = baseW+Top(pCube,dir,i,&Stats::W) ;
00550         double halfR = baseR+Top(pCube,dir,i,&Stats::R) ;
00551         double halfG = baseG+Top(pCube,dir,i,&Stats::G) ;
00552         double halfB = baseB+Top(pCube,dir,i,&Stats::B) ;
00553         cDOUBLE temp1 = Snap(&cube1,halfW,halfR,halfG,halfB) ;
00554         if ( temp1<-1e50 )
00555             continue ;
00556         halfW = wholeW-halfW ;
00557         halfR = wholeR-halfR ;
00558         halfG = wholeG-halfG ;
00559         halfB = wholeB-halfB ;
00560         cDOUBLE temp2 = Snap(&cube2,halfW,halfR,halfG,halfB) ;
00561         if ( temp2<-1e50 )
00562             continue ;
00563         if ( max<temp1+temp2 )
00564         {
00565             max = temp1+temp2 ;
00566             *pCube1 = cube1 ;
00567             *pCube2 = cube2 ;
00568         }
00569     }
00570     return max ;
00571 }
00572 
00573 bool PaletteOptimiser::Cut( cpBox pSet1,cpBox pSet2, cpDOUBLE pMax )
00574 {
00575     cDOUBLE wholeW = Vol(pSet1,&Stats::W) ;
00576     cDOUBLE wholeR = Vol(pSet1,&Stats::R) ;
00577     cDOUBLE wholeG = Vol(pSet1,&Stats::G) ;
00578     cDOUBLE wholeB = Vol(pSet1,&Stats::B) ;
00579 
00580     Box cubeR1,cubeR2, cubeG1,cubeG2, cubeB1,cubeB2 ;
00581     cDOUBLE maxR = Maximize( pSet1, RED  , pSet1->r0,pSet1->r1, &cubeR1,&cubeR2, wholeW,wholeR,wholeG,wholeB ) ;
00582     cDOUBLE maxG = Maximize( pSet1, GREEN, pSet1->g0,pSet1->g1, &cubeG1,&cubeG2, wholeW,wholeR,wholeG,wholeB ) ;
00583     cDOUBLE maxB = Maximize( pSet1, BLUE , pSet1->b0,pSet1->b1, &cubeB1,&cubeB2, wholeW,wholeR,wholeG,wholeB ) ;
00584 
00585     *pSet2 = *pSet1 ;
00586     if ( maxR>=maxG && maxR>=maxB )
00587     {
00588         if ( maxR<-1e50 )
00589             return false ; // can't split the box
00590         *pMax = maxR ;
00591         *pSet1 = cubeR1 ;
00592         *pSet2 = cubeR2 ;
00593     }
00594     else if ( maxG>=maxR && maxG>=maxB ) 
00595     {
00596         *pMax = maxG ;
00597         *pSet1 = cubeG1 ;
00598         *pSet2 = cubeG2 ;
00599     }
00600     else
00601     {
00602         *pMax = maxB ;
00603         *pSet1 = cubeB1 ;
00604         *pSet2 = cubeB2 ;
00605     }
00606     pSet1->vol = (pSet1->r1-pSet1->r0)*(pSet1->g1-pSet1->g0)*(pSet1->b1-pSet1->b0) ;
00607     pSet2->vol = (pSet2->r1-pSet2->r0)*(pSet2->g1-pSet2->g0)*(pSet2->b1-pSet2->b0) ;
00608     return true ;
00609 }
00610 
00611 double PaletteOptimiser::Maximize(
00612                             cpBox pCube,
00613                             cUINT32 dir, 
00614                             cUINT32 first,
00615                             cUINT32 last,
00616                             cpBox pCube1,
00617                             cpBox pCube2,
00618                             cpBox pCube3,
00619                             cDOUBLE wholeW,
00620                             cDOUBLE wholeR,
00621                             cDOUBLE wholeG,
00622                             cDOUBLE wholeB
00623                         )
00624 {
00625     cDOUBLE baseW = Bottom(pCube,dir,&Stats::W) ;
00626     cDOUBLE baseR = Bottom(pCube,dir,&Stats::R) ;
00627     cDOUBLE baseG = Bottom(pCube,dir,&Stats::G) ;
00628     cDOUBLE baseB = Bottom(pCube,dir,&Stats::B) ;
00629 
00630     Box cube1,cube2,cube3,cube4 ;
00631     cube1 = cube2 = *pCube ;
00632 
00633     double temp ;
00634     double max = -1e100 ;
00635 
00636     //  Did the bottom of the cube above.
00637     for ( UINT32 i=first+1 ; i<last ; ++i )
00638     {
00639         switch (dir)
00640         {
00641         case RED   : cube1.r1 = cube2.r0 = i ; break ;
00642         case GREEN : cube1.g1 = cube2.g0 = i ; break ;
00643         case BLUE  : cube1.b1 = cube2.b0 = i ; break ;
00644         }
00645 
00646         // half_x is sum over lower half of box, if split at i.
00647         double halfW = baseW+Top(pCube,dir,i,&Stats::W) ;
00648         double halfR = baseR+Top(pCube,dir,i,&Stats::R) ;
00649         double halfG = baseG+Top(pCube,dir,i,&Stats::G) ;
00650         double halfB = baseB+Top(pCube,dir,i,&Stats::B) ;
00651         cube3 = cube2 ;
00652         if ( Cut(&cube3,&cube4,&temp) )
00653         {
00654             temp += Snap(&cube1,halfW,halfR,halfG,halfB) ;
00655             if ( temp>-1e50 && max<temp )
00656             {
00657                 max = temp ;
00658                 *pCube1 = cube1 ;
00659                 *pCube2 = cube3 ;
00660                 *pCube3 = cube4 ;
00661             }
00662         }
00663 
00664         halfW = wholeW-halfW ;
00665         halfR = wholeR-halfR ;
00666         halfG = wholeG-halfG ;
00667         halfB = wholeB-halfB ;
00668         cube3 = cube1 ;
00669         if ( Cut(&cube3,&cube4,&temp) )
00670         {
00671             temp += Snap(&cube2,halfW,halfR,halfG,halfB) ;
00672             if ( temp>-1e50 && max<temp )
00673             {
00674                 max = temp ;
00675                 *pCube1 = cube2 ;
00676                 *pCube2 = cube3 ;
00677                 *pCube3 = cube4 ;
00678             }
00679         }
00680     }
00681     return max ;
00682 }
00683 
00684 bool PaletteOptimiser::Cut( cpBox pSet1,cpBox pSet2,cpBox pSet3 )
00685 {
00686     Box set12 ;
00687     set12.r0 = min(pSet1->r0,pSet2->r0) ;
00688     set12.r1 = max(pSet1->r1,pSet2->r1) ;
00689     set12.g0 = min(pSet1->g0,pSet2->g0) ;
00690     set12.g1 = max(pSet1->g1,pSet2->g1) ;
00691     set12.b0 = min(pSet1->b0,pSet2->b0) ;
00692     set12.b1 = max(pSet1->b1,pSet2->b1) ;
00693 
00694     cDOUBLE wholeW = Vol(&set12,&Stats::W) ;
00695     cDOUBLE wholeR = Vol(&set12,&Stats::R) ;
00696     cDOUBLE wholeG = Vol(&set12,&Stats::G) ;
00697     cDOUBLE wholeB = Vol(&set12,&Stats::B) ;
00698 
00699     Box cubeR1,cubeR2,cubeR3 ;
00700     Box cubeG1,cubeG2,cubeG3 ;
00701     Box cubeB1,cubeB2,cubeB3 ;
00702     cDOUBLE maxR = Maximize( &set12, RED  , set12.r0,set12.r1, &cubeR1,&cubeR2,&cubeR3, wholeW,wholeR,wholeG,wholeB ) ;
00703     cDOUBLE maxG = Maximize( &set12, GREEN, set12.g0,set12.g1, &cubeG1,&cubeG2,&cubeG3, wholeW,wholeR,wholeG,wholeB ) ;
00704     cDOUBLE maxB = Maximize( &set12, BLUE , set12.b0,set12.b1, &cubeB1,&cubeB2,&cubeB3, wholeW,wholeR,wholeG,wholeB ) ;
00705 
00706     if ( maxR>=maxG && maxR>=maxB )
00707     {
00708         if ( maxR<-1e50 )
00709             return false ; // can't split the box
00710         *pSet1 = cubeR1 ;
00711         *pSet2 = cubeR2 ;
00712         *pSet3 = cubeR3 ;
00713     }
00714     else if ( maxG>=maxR && maxG>=maxB ) 
00715     {
00716         *pSet1 = cubeG1 ;
00717         *pSet2 = cubeG2 ;
00718         *pSet3 = cubeG3 ;
00719     }
00720     else
00721     {
00722         *pSet1 = cubeB1 ;
00723         *pSet2 = cubeB2 ;
00724         *pSet3 = cubeB3 ;
00725     }
00726     pSet1->vol = (pSet1->r1-pSet1->r0)*(pSet1->g1-pSet1->g0)*(pSet1->b1-pSet1->b0) ;
00727     pSet2->vol = (pSet2->r1-pSet2->r0)*(pSet2->g1-pSet2->g0)*(pSet2->b1-pSet2->b0) ;
00728     pSet3->vol = (pSet3->r1-pSet3->r0)*(pSet3->g1-pSet3->g0)*(pSet3->b1-pSet3->b0) ;
00729     return true ;
00730 }
00731 
00733 //
00734 // This function generates the colours of an optimised palette. This function
00735 // is usually called once after calling AddStats. GetPalette can be called
00736 // several times to then obtain the actual palette of a particular size.
00737 //
00738 void PaletteOptimiser::GenPalette( cUINT32 uMaxColours )
00739 {
00740     ASSERT( uMaxColours<=0x100 ) ;
00741     //
00742     // Calculate the 3d moments of inertia within our field
00743     //
00744     if ( !m_bMoments )
00745     {
00746         Moments3D() ;
00747         m_bMoments = true ;
00748     }
00749 
00750     m_uPaletteEntries = 0 ;
00751 
00752     if ( m_bAddSystemColours )
00753     {
00754         AddLockedColour(0x00,0x00,0x00) ;
00755         AddLockedColour(0x00,0x00,0x80) ;
00756         AddLockedColour(0x00,0x80,0x00) ;
00757         AddLockedColour(0x00,0x80,0x80) ;
00758         AddLockedColour(0x80,0x00,0x00) ;
00759         AddLockedColour(0x80,0x00,0x80) ;
00760         AddLockedColour(0x80,0x80,0x00) ;
00761         AddLockedColour(0x80,0x80,0x80) ;
00762         AddLockedColour(0x00,0x00,0xFF) ;
00763         AddLockedColour(0x00,0xFF,0x00) ;
00764         AddLockedColour(0x00,0xFF,0xFF) ;
00765         AddLockedColour(0xFF,0x00,0x00) ;
00766         AddLockedColour(0xFF,0x00,0xFF) ;
00767         AddLockedColour(0xFF,0xFF,0x00) ;
00768         AddLockedColour(0xFF,0xFF,0xFF) ;
00769         AddLockedColour(0xC0,0xC0,0xC0) ;
00770         m_uAllLockedColours = m_uLockedColours ;
00771         m_uLockedColours -= 16 ;
00772     }
00773     else
00774         m_uAllLockedColours = m_uLockedColours ;
00775     m_uSnapToPrimaries2      = m_uSnapToPrimaries     *m_uSnapToPrimaries ;
00776     m_uSnapToBrowserPalette2 = m_uSnapToBrowserPalette*m_uSnapToBrowserPalette ;
00777     //
00778     // Initialise our first cube to encompass the entire volume
00779     //
00780     Box cube[MAXCOLOURS] ;
00781     cube[0].r0 = cube[0].g0 = cube[0].b0 = 0 ;
00782     cube[0].r1 = cube[0].g1 = cube[0].b1 = AXIS-1 ;
00783     cube[0].vol = (AXIS-1)*(AXIS-1)*(AXIS-1) ;
00784     cube[0].var = 0 ;
00785     cube[0].pPair = NULL ;
00786     cDOUBLE ww = Vol(cube,&Stats::W) ;
00787     if ( ww==0 )
00788         return ;
00789     cube[0].clr.r = (UINT32)(Vol(cube,&Stats::R)/ww+0.5) ;
00790     cube[0].clr.g = (UINT32)(Vol(cube,&Stats::G)/ww+0.5) ;
00791     cube[0].clr.b = (UINT32)(Vol(cube,&Stats::B)/ww+0.5) ;
00792 
00793     m_uPaletteEntries = 0 ;
00794     Store(0,cube) ;
00795 
00796     pBox pCubeO = cube ;
00797     for ( UINT32 i=1 ; i<uMaxColours ; )
00798     {
00799         double temp ;
00800         cpBox pCubeN = cube+i ;
00801         cpBox pCubeP = pCubeO->pPair ;
00802         if ( !m_bFast && pCubeP )
00803             if ( Cut(pCubeP,pCubeO,pCubeN) )
00804             {
00805                 pCubeP->pPair = NULL ;
00806                 pCubeO->pPair = pCubeN ;
00807                 pCubeN->pPair = pCubeO ;
00808                 Store(pCubeP-cube,pCubeP) ;
00809                 Store(pCubeO-cube,pCubeO) ;
00810                 Store(pCubeN-cube,pCubeN) ;
00811                 i++ ;
00812             }
00813             else
00814             {
00815                 pCubeP->pPair = NULL ;
00816                 pCubeO->pPair = NULL ;
00817                 pCubeO->vol = 0 ;
00818             }
00819         else
00820             if ( Cut(pCubeO,pCubeN,&temp) )
00821             {
00822                 pCubeN->pPair = pCubeO ;
00823                 pCubeO->pPair = pCubeN ;
00824                 Store(pCubeO-cube,pCubeO) ;
00825                 Store(pCubeN-cube,pCubeN) ;
00826                 i++ ;
00827             }
00828             else
00829                 pCubeO->vol = 0 ;
00830         //
00831         // Find box with maximum error.
00832         //
00833         pCubeO = cube ;
00834         temp = -1 ;
00835         for ( UINT32 k=0 ; k<i ; ++k )
00836             if ( temp<cube[k].var && cube[k].vol>1 )
00837             {
00838                 pCubeO = cube+k ;
00839                 temp = pCubeO->var ;
00840             }
00841         if ( temp<0 )
00842             break ;
00843     }
00844 }
00845 
00846 
00847 
00848 void PaletteOptimiser::Store( cUINT32 i, cpBox pCube )
00849 {
00850     pCube->var = Var(pCube) ;
00851     m_aPalette[m_uPaletteEntries  ].C = peRGB( pCube->clr.r,pCube->clr.g,pCube->clr.b, i ) ;
00852     m_aPalette[m_uPaletteEntries++].W = Vol(pCube,&Stats::W) ;
00853 }
00854 
00856 //
00857 // Call this function to obtain the optimised palette of a particalur size.
00858 //
00859 //      pPalette    - points to a logical palette. The palNumEntries entry
00860 //                    should previously have been initialised.
00861 //      nMaxColours - required number of optimised colours.
00862 //
00863 bool PaletteOptimiser::GetPalette( cpLOGPALETTE pPalette, cUINT32 uMaxColours )
00864 {
00865     ASSERT(pPalette) ;
00866     ASSERT(pPalette->palNumEntries>0 && pPalette->palNumEntries<=0x100) ;
00867     ASSERT(uMaxColours>0 && uMaxColours<=0x100) ;
00868     //
00869     // Check for zero colour case. This can occur if all colours in the image
00870     // were transparent.
00871     //
00872     if ( m_uPaletteEntries==0 )
00873     {
00874         pPalette->palNumEntries = 0 ;
00875         return true ;
00876     }
00877     //
00878     // n is current size of generated palette
00879     //
00880     PalEntry T[0x100] ;
00881     UINT32 i,j,n ;
00882     bool bFixed = false ;
00883     if ( !m_bUseBrowserPalette && m_bUseBitmapColours && m_uTotalColours<=MAXCOLOURS &&
00884          (m_uTotalColours<uMaxColours || m_uSnapToBrowserPalette || m_uSnapToPrimaries) )
00885     {
00886         bFixed = true ;
00887         for ( i=0,n=0 ; i<m_uTotalColours ; i++ )
00888         {
00889             Clr clr = {
00890                 m_aColours[i].rgbRed,
00891                 m_aColours[i].rgbGreen,
00892                 m_aColours[i].rgbBlue
00893             } ;
00894             for ( j=0 ; j<m_uAllLockedColours ; j++ )
00895                 if ( m_aLockedColours[j].peRed  ==clr.r &&
00896                      m_aLockedColours[j].peGreen==clr.g &&
00897                      m_aLockedColours[j].peBlue ==clr.b )
00898                     goto nosnap ;
00899             //
00900             // Shouldn't snap colour if it is a locked colour.
00901             //
00902             if ( m_uSnapToBrowserPalette &&
00903                  aBDist[clr.r]+aBDist[clr.g]+aBDist[clr.b]<=m_uSnapToBrowserPalette2 )
00904             {
00905                 clr.r = aSnap[clr.r] ;
00906                 clr.g = aSnap[clr.g] ;
00907                 clr.b = aSnap[clr.b] ;
00908             }
00909             if ( m_uSnapToPrimaries &&
00910                  aPDist[clr.r]+aPDist[clr.g]+aPDist[clr.b]<=m_uSnapToPrimaries2 )
00911             {
00912                 clr.r = clr.r<0x80 ? 0x00 : 0xFF ;
00913                 clr.g = clr.g<0x80 ? 0x00 : 0xFF ;
00914                 clr.b = clr.b<0x80 ? 0x00 : 0xFF ;
00915             }
00916     nosnap: //
00917             // Only add colour to palette if not already there.
00918             //
00919             for ( j=0 ; j<n ; j++ )
00920                 if ( T[j].C.peRed  ==clr.r &&
00921                      T[j].C.peGreen==clr.g &&
00922                      T[j].C.peBlue ==clr.b )
00923                     goto ignore ;
00924             if ( n==uMaxColours )
00925             {
00926                 bFixed = false ;
00927                 break ;
00928             }
00929             T[n].C.peRed   = clr.r ;
00930             T[n].C.peGreen = clr.g ;
00931             T[n].C.peBlue  = clr.b ;
00932             T[n].W = m_aCount[i] ;
00933             n++ ;
00934     ignore: ;
00935         }
00936     }
00937 
00938     if ( !bFixed )
00939         for ( i=0,n=0 ; i<m_uPaletteEntries && n<uMaxColours ; i++ )
00940         {
00941             j = m_aPalette[i].C.peFlags ;
00942             T[j] = m_aPalette[i] ;
00943             if ( j>=n )
00944                 n++ ;
00945         }
00946 
00947     qsort(T, n, sizeof(PalEntry), SortFn) ;
00948     for ( i=0 ; i<n ; i++ )
00949     {
00950         pPalette->palPalEntry[i] = T[i].C ;
00951         pPalette->palPalEntry[i].peFlags = 0 ;
00952     }
00953     pPalette->palNumEntries = n ;
00954 
00955 #ifdef DEBUG
00956 //  TRACE( _T("N : %i\n"),n) ;
00957 //  for ( i=0 ; i<n ; i++ )
00958 //      TRACE( _T("%2i : %02x,%02x,%02x\n"),i,pPalette->palPalEntry[i].peRed,pPalette->palPalEntry[i].peGreen,pPalette->palPalEntry[i].peBlue) ;
00959 #endif
00960     //
00961     // Fill in any remaining unused required colours with non-renderable black
00962     //
00963 //  for ( ; n<nMaxColours ; )
00964 //      pPalette->palPalEntry[n++] = peRGB(0,0,0, 0xFF) ;
00965 
00966     return bFixed ;
00967 }
00968 
00969 
00970 
00971 INT32 __cdecl PaletteOptimiser::SortFn( pcVOID elem1, pcVOID elem2 )
00972 {
00973     return (INT32)( ((cpcPalEntry)elem2)->W - ((cpcPalEntry)elem1)->W ) ;
00974 }
00975 
00976 /***************************************************************************/

Generated on Sat Nov 10 03:48:31 2007 for Camelot by  doxygen 1.4.4