source: trunk/src/opengl/glide/cvg/texus/diffuse.c

Last change on this file was 6653, checked in by bird, 24 years ago

Added $Id:$ keyword.
File size: 9.0 KB
Line 
1/* $Id: diffuse.c,v 1.2 2001-09-05 14:30:44 bird Exp $ */
2
3/*
4** THIS SOFTWARE IS SUBJECT TO COPYRIGHT PROTECTION AND IS OFFERED ONLY
5** PURSUANT TO THE 3DFX GLIDE GENERAL PUBLIC LICENSE. THERE IS NO RIGHT
6** TO USE THE GLIDE TRADEMARK WITHOUT PRIOR WRITTEN PERMISSION OF 3DFX
7** INTERACTIVE, INC. A COPY OF THIS LICENSE MAY BE OBTAINED FROM THE
8** DISTRIBUTOR OR BY CONTACTING 3DFX INTERACTIVE INC(info@3dfx.com).
9** THIS PROGRAM IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER
10** EXPRESSED OR IMPLIED. SEE THE 3DFX GLIDE GENERAL PUBLIC LICENSE FOR A
11** FULL TEXT OF THE NON-WARRANTY PROVISIONS.
12**
13** USE, DUPLICATION OR DISCLOSURE BY THE GOVERNMENT IS SUBJECT TO
14** RESTRICTIONS AS SET FORTH IN SUBDIVISION (C)(1)(II) OF THE RIGHTS IN
15** TECHNICAL DATA AND COMPUTER SOFTWARE CLAUSE AT DFARS 252.227-7013,
16** AND/OR IN SIMILAR OR SUCCESSOR CLAUSES IN THE FAR, DOD OR NASA FAR
17** SUPPLEMENT. UNPUBLISHED RIGHTS RESERVED UNDER THE COPYRIGHT LAWS OF
18** THE UNITED STATES.
19**
20** COPYRIGHT 3DFX INTERACTIVE, INC. 1999, ALL RIGHTS RESERVED
21**
22** $Revision: 1.2 $
23** $Date: 2001-09-05 14:30:44 $
24*/
25
26#include <stdio.h>
27#include <stdlib.h>
28#include <string.h>
29#include <math.h>
30
31#include "texusint.h"
32
33// Error diffusion is implemented here.
34
35static int ErrR[MAX_TEXWIDTH], ErrG[MAX_TEXWIDTH], ErrB[MAX_TEXWIDTH];
36
37#if FAST_DIFFUSION
38int nsorted;
39FxU32 sortR[256], sortG[256], sortB[256];
40FxU8 bestR[256], bestG[256], bestB[256];
41
42static int
43_txAscendingR(const void *a, const void *b)
44{
45 return ((*(FxI32 *)a) & 0x00FF0000) - ((*(FxI32 *)b) & 0x00FF0000);
46}
47
48
49static int
50_txAscendingG(const void *a, const void *b)
51{
52 return ((*(FxI32 *)a) & 0x0000ff00) - ((*(FxI32 *)b) & 0x0000ff00);
53}
54
55
56static int
57_txAscendingB(const void *a, const void *b)
58{
59 return ((*(FxI32 *)a) & 0x000000ff) - ((*(FxI32 *)b) & 0x000000ff);
60}
61
62static void
63_txMakeRange(const FxU32 *palette, int ncolors)
64{
65 int i, j, mindist, minpos, d;
66 FxU32 *pal;
67
68
69 for (i=0; i<ncolors; i++) {
70 sortR[i] = (palette[i] & 0x00ffffff) | (i<<24);
71 sortG[i] = (palette[i] & 0x00ffffff) | (i<<24);
72 sortB[i] = (palette[i] & 0x00ffffff) | (i<<24);
73 }
74
75 qsort(sortR, ncolors, sizeof(FxU32), _txAscendingR);
76 qsort(sortG, ncolors, sizeof(FxU32), _txAscendingG);
77 qsort(sortB, ncolors, sizeof(FxU32), _txAscendingB);
78 nsorted = ncolors;
79
80#if 0
81 for (i=0; i<ncolors; i++)
82 printf("[%3d] = R%.08x G%.08x B%.08x\n",
83 i, sortR[i], sortG[i], sortB[i]);
84#endif
85
86
87 for (i=0; i<256; i++) {
88
89 /* Find index of best matching Red component given r=i */
90 pal = sortR;
91 minpos = mindist = 0x7fffffff;
92 for (j=0; j < ncolors; j++) {
93 d = DISTANCE(i, 0, 0, (pal[j]>>16) & 0xff, 0, 0);
94 if (d < mindist) { mindist = d; minpos = j; }
95 }
96 bestR[i] = minpos;
97
98
99 /* Find index of best matching Grn component given g=i */
100 pal = sortG;
101 minpos = mindist = 0x7fffffff;
102 for (j=0; j < ncolors; j++) {
103 d = DISTANCE(0, i, 0, 0, (pal[j]>>8) & 0xff, 0);
104 if (d < mindist) { mindist = d; minpos = j; }
105 }
106 bestG[i] = minpos;
107
108
109 /* Find index of best matching Blu component given b=i */
110 pal = sortB;
111 minpos = mindist = 0x7fffffff;
112 for (j=0; j < ncolors; j++) {
113 d = DISTANCE(0, 0, i, 0, 0, (pal[j]) & 0xff);
114 if (d < mindist) { mindist = d; minpos = j; }
115 }
116 bestB[i] = minpos;
117 }
118}
119
120static int
121_txFastMatch(int r, int g, int b)
122{
123 int minpos, mindist, i, d, persist;
124 FxU32 *pal;
125
126 minpos = mindist = 0x7fffffff;
127
128 /* Walk backwards from bestR, tracking best index */
129 pal = sortR;
130 persist = 0;
131 for (i=bestR[r]; i>=0; i--) {
132 d = DISTANCE(r, g, b,
133 ((pal[i] >> 16) & 0xff), ((pal[i] >> 8) & 0xff), ((pal[i]) & 0xff));
134 if (d < mindist) { mindist = d; minpos = (pal[i] >> 24) & 0xff; }
135 else if (++persist > 3) break;
136 }
137
138 /* Walk forwards from bestR+1, tracking best index */
139 persist = 0;
140 for (i=bestR[r]+1; i < nsorted; i++) {
141 d = DISTANCE(r, g, b,
142 ((pal[i] >> 16) & 0xff), ((pal[i] >> 8) & 0xff), ((pal[i]) & 0xff));
143 if (d < mindist) { mindist = d; minpos = (pal[i] >> 24) & 0xff; }
144 else if (++persist > 3) break;
145 }
146
147
148 /* Walk backwards from bestG, tracking best index */
149 pal = sortG;
150 persist = 0;
151 for (i=bestG[g]; i>=0; i--) {
152 d = DISTANCE(r, g, b,
153 ((pal[i] >> 16) & 0xff), ((pal[i] >> 8) & 0xff), ((pal[i]) & 0xff));
154 if (d < mindist) { mindist = d; minpos = (pal[i]>>24) & 0xff; }
155 else if (++persist > 3) break;
156 }
157
158 /* Walk forwards from bestG+1, tracking best index */
159 persist = 0;
160 for (i=bestG[g]+1; i < nsorted; i++) {
161 d = DISTANCE(r, g, b,
162 ((pal[i] >> 16) & 0xff), ((pal[i] >> 8) & 0xff), ((pal[i]) & 0xff));
163 if (d < mindist) { mindist = d; minpos = (pal[i]>>24) & 0xff; }
164 else if (++persist > 3) break;
165 }
166
167 /* Walk backwards from bestB, tracking best index */
168 pal = sortB;
169 persist = 0;
170 for (i=bestB[b]; i>=0; i--) {
171 d = DISTANCE(r, g, b,
172 ((pal[i] >> 16) & 0xff), ((pal[i] >> 8) & 0xff), ((pal[i]) & 0xff));
173 if (d < mindist) { mindist = d; minpos = (pal[i]>>24) & 0xff; }
174 else if (++persist > 3) break;
175 }
176
177 /* Walk forwards from bestB+1, tracking best index */
178 persist = 0;
179 for (i=bestB[b]+1; i < nsorted; i++) {
180 d = DISTANCE(r, g, b,
181 ((pal[i] >> 16) & 0xff), ((pal[i] >> 8) & 0xff), ((pal[i]) & 0xff));
182 if (d < mindist) { mindist = d; minpos = (pal[i]>>24) & 0xff; }
183 else if (++persist > 3) break;
184 }
185 return minpos;
186}
187#endif // FAST_DIFFUSION
188
189
190static void
191_txToDiffuseIndex (FxU8 *opixels, int pixsize, const FxU32 *pal, int ncolors,
192 const FxU32 *ipixels, int width, int height)
193{
194 int y, x, i;
195 int qr, qg, qb;
196
197 for (y=0; y<height; y++) {
198
199 if( txVerbose )
200 {
201 if (y == (3*height)/4) { printf("."); fflush(stdout);}
202 if (y == (2*height)/4) { printf("."); fflush(stdout);}
203 if (y == (1*height)/4) { printf("."); fflush(stdout);}
204 if (y == (0*height)/4) { printf("."); fflush(stdout);}
205 }
206
207 qr = qg = qb = 0;
208 for (i=0; i<=width; i++) ErrR[i] = ErrG[i] = ErrB[i] = 0;
209
210 for (x=0; x<width; x++) {
211 int ia, ir, ig, ib, c;
212
213 // The input color, and add diffused errors to these.
214 ia = (*ipixels >> 24) & 0xFF;
215 ir = (*ipixels >> 16) & 0xFF;
216 ig = (*ipixels >> 8) & 0xFF;
217 ib = (*ipixels ) & 0xFF;
218 ipixels ++;
219
220 ir += qr + ErrR[x];
221 ig += qg + ErrG[x];
222 ib += qb + ErrB[x];
223
224 qr = ir; // quantized pixel values.
225 qg = ig; // qR is error from pixel to left, errR is
226 qb = ib; // error from pixel to the top & top left.
227
228 if (qr < 0) qr = 0; if (qr > 255) qr = 255; // clamp.
229 if (qg < 0) qg = 0; if (qg > 255) qg = 255;
230 if (qb < 0) qb = 0; if (qb > 255) qb = 255;
231
232 // Find closest color in the tables, and quantize.
233 c = txNearestColor(qr, qg, qb, pal, ncolors);
234#if FAST_DIFFUSION
235 // 3 times faster, but not as good quality.
236 c = _txFastMatch(qr, qg, qb);
237#endif
238
239 qr = (pal[c] & 0x00ff0000) >> 16;
240 qg = (pal[c] & 0x0000ff00) >> 8;
241 qb = (pal[c] & 0x000000ff) ;
242
243 // Diffuse the errors.
244 qr = ir - qr;
245 qg = ig - qg;
246 qb = ib - qb;
247
248 // 3/8 (=0.375) to the EAST, 3/8 to the SOUTH,
249 // 1/4 (0.25) to the SOUTH-EAST.
250 ErrR[x] = ((x == 0) ? 0 : ErrR[x]) + ((int) (qr * 0.375f));
251 ErrG[x] = ((x == 0) ? 0 : ErrG[x]) + ((int) (qg * 0.375f));
252 ErrB[x] = ((x == 0) ? 0 : ErrB[x]) + ((int) (qb * 0.375f));
253
254 ErrR[x+1] = (int) (qr * 0.250f);
255 ErrG[x+1] = (int) (qg * 0.250f);
256 ErrB[x+1] = (int) (qb * 0.250f);
257
258 qr = (int) (qr * 0.375f); // Carried to the right.
259 qg = (int) (qg * 0.375f);
260 qb = (int) (qb * 0.375f);
261
262 if (pixsize == 2) {
263 *(FxU16 *) opixels = (ia << 8) | c;
264 opixels += pixsize;
265 } else {
266 *opixels++ = (FxU8) c;
267 }
268 }
269 }
270}
271
272void
273txDiffuseIndex(TxMip *pxMip, TxMip *txMip, int pixsize, const FxU32 *palette,
274 int ncolors)
275{
276 int i, w, h;
277
278 if( txVerbose )
279 {
280 printf("EDiffusion:..."); fflush(stdout);
281 }
282
283#if FAST_DIFFUSION
284 _txMakeRange(palette, ncolors);
285#endif
286
287 /* Translate image to an indexed image using error diffusion */
288 w = txMip->width;
289 h = txMip->height;
290
291 for (i=0; i<txMip->depth; i++) {
292 _txToDiffuseIndex(pxMip->data[i], pixsize, palette, ncolors,
293 txMip->data[i], w, h);
294 if (w > 1) w >>= 1;
295 if (h > 1) h >>= 1;
296 }
297 if( txVerbose )
298 {
299 printf("done\n");
300 }
301}
Note: See TracBrowser for help on using the repository browser.