summaryrefslogtreecommitdiff
path: root/target/ofps.h
blob: e2b1d5530a514094acf5c0dfb226f4d95a0d2425 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438

#ifndef OFPS_H

/* 
 * Argyll Color Correction System
 *
 * Optimised Farthest Point Sampling
 *
 * Author: Graeme W. Gill
 * Date:   6/9/2004
 *
 * Copyright 2004 Graeme W. Gill
 * All rights reserved.
 *
 * This material is licenced under the GNU AFFERO GENERAL PUBLIC LICENSE Version 3 :-
 * see the License.txt file for licencing details.
 */

#ifndef MXPD
#define MXPD 4			/* Maximum ofps dimentionality */
#endif

#define MXNIX (MXPD+3)	/* Maximum vertex node indexes + hash + ixm */ 

struct _acell;

/* A gamut surface plane equation. */
struct _pleq {
	double pe[MXPD+1];	/* Vertex plane equation. First di elements are normalized */
						/* outward pointing normal (from first sample point), last element */
						/* is constant. If point . pe > 0, then point is outside surface */
	int ix;				/* Index of fake node associated with gamut surface (-ve) */
}; typedef struct _pleq pleq;

/* A sub-surface set mask */
#define MXSMASKW 6		/* Maximum number of setmask words */
typedef struct {
	unsigned int m[MXSMASKW];
} setmask;

/* A vertex. This is a point that has the highest eserr within */
/* the local region of di+1 nodes. It is therefore a candidate for a new */
/* sample node during seeding, or a point at which the sampling */
/* error of the current node locations can be estimated. */
/* Vertexes are the vericies of the Voronoi polyhedra. */
/* Because these are based on the natural eserr neighborhood, */
/* they are not necessarily exactly poyhedra. */
/* (Non gamut boundary verticies are shared) */
struct _vtx {
	int    no;			/* Serial number for id */
	int nix[MXNIX];		/* di+1 Sample point node indexes involved in vertex */
						/* Index is -ve if it is a fake gamut boundary node, */
						/* sorted largest to smallest (so fake gamut nodes are last) */
						/* [MXPD+1] is hash of all the node indexes, */
						/* [MXPD+2] is the OR of all the node ixm's */
	double ce[MXPD+1];	/* Estimated curvature error from mid point to each real node */
						/* (ce's are compacted, skipping fake boundary nodes) */
	int nnv;			/* Number of neighbour verticies (vertex net) */ 
	int _nnv;			/* Number allocated */
	struct _vtx **nv;	/* List of neighbour verticies. This includes hidden verts. */
						/* (If we didn't have to support INDEP_SURFACE, then there would */
						/*  be exactly di neighbour verticies.) */

	double p[MXPD];		/* Vertex location */
	double v[MXPD];		/* Subjective value at vertex (Labj) ? */
	double eperr;		/* Estimated position error */
	double eserr;		/* Estimated sampling error */
	double p_eperr;		/* Previous estimated position error */
	char ghost;			/* Don't use for optimization or stats. */
	char ifake;			/* A fake inside node */
	char ofake;			/* A fake outside node */
	char used;			/* Set to nz if already used for seeding */
	char bch;			/* nz if added to batch update list */
	char del;			/* Marked for deletion (used by add_to_vsurf()) */
	char add;			/* 1 = add to node, 2 = update hm (used by add_to_vsurf()) */
	char par;			/* Marked for deletion because it's already a parent node */
	int sch;			/* Sanity check houskeeping */
	setmask buvm;		/* Batch update to sub-surface hidden setmask */
	setmask bdvm;		/* Batch delete change to sub-surface hidden setmask */
	struct _vtx *batch;	/* Batch update list */
	int nsp;			/* Number of gamut surface planes it touches */
	pleq *sp[MXPD+1];	/* List of gamut surface planes */
	unsigned int pmask;	/* Gamut surface plane mask, from its location */
	unsigned int cmask;	/* Gamut surface composition mask, from it's parent nodes */
	setmask vm;			/* Sub-surface visiblility setmask */
	struct _vtx *link;	/* Linked list of free/used vtx's */
	struct _vtx **plp;	/* Pointer to link pointer in used list */

	struct _vtx *n;		/* Next in acceleration list */
	struct _vtx **pn;	/* Pointer to link pointer in acceleration list */
	int pci;			/* Accelleration grid index */

	struct _vtx *chn;	/* Next in cache index list */
	struct _vtx **pchn;	/* Pointer to link pointer in cache index list */

	int fflag;			/* fchl set flag set from s->fflag */
	struct _vtx *fchl;	/* Next in fixup check list */
	struct _vtx **pfchl;/* Pointer to link pointer */
	int fupcount;		/* Number of times vertex has fixed in a round */
	double fuptol;		/* Tollerance for fixing this vertex */
	struct _node *hnode;/* Hit node */
	double hitmarg;		/* Hit margine to node */
	struct _vtx **psvtxs;	/* Pointer to entry in s->svtxs[] */

	int cflag;			/* Vertex checked for hit flag, set from s->flag */
	int sflag;			/* Vertex search before flag, set from s->flag */
	int hflag;			/* Vertex search after hit flag, set from s->flag */
	char opqsq;			/* flag, on post hit search queue */
	struct _vtx *slist;	/* Breadth first search list link */
	int disth;			/* Search distance from hit vertex, valid when hflag == s->flag */
	struct _vtx *nxh;	/* Vtxs hit by node (to be deleted) list set by ofps_check_vtx_vn() */
	double nba_eperr;	/* node being added eperr, valid if cflag == s->flag */

	struct _vtx *dell;	/* Deleted/Not Deleted list */
}; typedef struct _vtx vtx;

/* A mid point. This is a point that has the highest eserr directly */
/* between two neighboring nodes. It is used during optimization */
/* to try and encourage even spacing between nodes. */
struct _mid {
	int    no;			/* Serial number for id */
	double p[MXPD];		/* Midpoint location */
	int nix[2];			/* The two sample point node indexes involved in midpoint */
	double ce[2];		/* Estimated curvature error from mid point to two nodes */
	double np;			/* Interpolation point between nux[0] and nix[1] */
	double v[MXPD];		/* Subjective value at midpoint (Labj) ? */
	double eperr;		/* Estimated position error */
	double eserr;		/* Estimated sampling error */
	int refc;			/* Reference count */
	struct _mid *link;	/* Linked list of free/used mid's */
	struct _mid **plp;	/* Pointer to link pointer in used list */
}; typedef struct _mid mid;


/* A measurement sample point node. */
/* Sample points are the points around which the Voronoi polyhedra */
/* are constructed. If a network is constructed between nodes that */
/* form a vertex, the netork will be the Delaunay tesselation. */
struct _node {
	int    ix;			/* Index of node in s->n[] */
	int    ixm;			/* Hash mask of node ix */
	int    fx;			/* nz if point is fixed */
	double p[MXPD];		/* Device coordinate position */
	double v[MXPD];		/* Subjective value (Labk) ? */

	double np[MXPD];	/* Next device coordinates during opt */
	double nv[MXPD];	/* Next subjective coordinates during opt */

	double op[MXPD];	/* Previous device coordinates during opt */

	int nvv;			/* Number of Voronoi surface verticies */ 
	int _nvv;			/* Number allocated */
	vtx **vv;			/* List of Voronoi surface verticies */

	int nvn;			/* Number of Voronoi nodes & midpoints */ 
	int _nvn;			/* Number allocated */
	int *vn;			/* List of Voronoi nodes indexes. Doesn't include this node. */
						/* Index is -ve if it is a fake gamut boundary node. */
	mid **mm;			/* List of midpoints. Midpoints will be NULL if not created yet. */

	int nsp;			/* Number of touched gamut surface planes */
	pleq *sp[MXPD+1];	/* List of touched gamut surface planes */
	unsigned int pmask;	/* Gamut surface plane mask */

	struct _acell *cell;/* Pointer to cell vertex is in */
	struct _node *n;	/* Next in acceleration list */
	struct _node **pn;	/* Pointer to link pointer in acceleration list */
	int pci;			/* Accelleration grid index */

	int flag;			/* Node being added access flag, set from s->flag */
	int nvnflag;		/* node_recomp_nvn_dmxs access flag */
	struct _node *na;	/* Next in 'to be added' list */
	int upflag;			/* Set to s->flag if node has been added to ->nup list */
	struct _node *nup;	/* Next node in 'recomp_nvn' list */

}; typedef struct _node node;

#define BOUND_GFLAG ((unsigned int)-1)		/* Boundary cell gflag */

/* An acceleration structure cube */
struct _acell {
	unsigned int gflag;	/* Acceleration grid search touched & boundary flag */
	node *head;			/* List of nodes inside acceleration cell */
	vtx  *vhead;		/* List of verticies with all real nodes inside acceleration cell */
	int co[MXPD];		/* coordinate of cell */
	double p[MXPD];		/* Device position of base of cell */
	double v[MXPD];		/* Corresponfing perceptual value of base of cell */
	double cp[MXPD];	/* Device position of center of cell */
	double cv[MXPD];	/* Corresponfing perceptual value of center of cell */
	double eperr;		/* Worst case eperr from a corner to the center */
	struct _acell *slist;	/* Search list */
}; typedef struct _acell acell;

/* Storage for a node combination/new position */
struct _nodecomb {
	int nix[MXNIX];		/* di+1 Sample point node indexes involved in vertex */
	double ce[MXPD+1];	/* Estimated curvature error from mid point to two nodes */
	vtx **v1, **v2;		/* Deleted and non-deleted vertex involved */
	int _count;			/* v1/v2 allocation */
	int count;			/* Number of times this is generated, used of v1/v2 */
	double p[MXPD];		/* Position of resulting vertex or */
	double v[MXPD];		/* Value of resulting vertex or */
	double eperr;
	double eserr;
	double weserr;
	int pvalid;			/* Valid new position, else use deleted location & eserr */
	vtx *vv;			/* Existing vertex at this combination (if opt) */
	double ceperr;		/* Current eperr to be bettered */
	double oog;			/* Out of gamut value */
	setmask vm;			/* Sub-surface visibility setmask */
	int startex;		/* nz if existing p[] should be starting dnsqe point */
}; typedef struct _nodecomb nodecomb;

/* Vertex cache hash index/table size */
#define VTXCHSIZE 33037
//#define VTXCHSIZE 67493

/* Record of a set of gamut surface plane combination */
struct _surfcomb {
	unsigned int co;		/* Surface combination mask */
	int valid;				/* Valid flag */
	int nos;				/* Number surfaces */
	int smset;				/* i_sm has been set */
	setmask i_sm;			/* Indiviual set of this surface combination */
	setmask a_sm;			/* Accumulated set of this and higher dimensions */
	struct _surfcomb *ds;	/* Circular list of the disjoint set */
}; typedef struct _surfcomb surfcomb;

/* Main sample point object */
struct _ofps {
/* private: */
	int verb;		/* Verbose */

	int di;			/* Point dimensionality */
	double ilimit;	/* Ink limit - limit on sum of p[] */
	double imin[MXPD];	/* Ink limit - limit on min of p[], must be >= 0.0 */
	double imax[MXPD];	/* Ink limit - limit on min of p[], must be <= 1.0  */
	int good;			/* 0 = fast, 1 = good flag */
	double surftol;		/* Surface tollerance distance */
	int maxits;			/* Maximum itterative improvement passes */
	double lperterb;	/* level of random peturbation */
	double ssurfpref, esurfpref;	/* Start and end surface preference weightig */ 

	/* Error estimate model parameters */
	double devd_wght;	/* Device space weighting */
	double perc_wght;	/* Perceptual space weighting */
	double curv_wght;	/* Curvature weighting */

	int fxno;		/* Total number of fixed points provided, possibly non-unique */
	fxpos **ufx;	/* fnp randomized unique fixed points to add */

	int gnp;		/* Number of fake gamut nodes (-ve index) */
					/* -1 to -2di-1 are fake boundary node indexes, */
					/* with -2di-1 being the ink limit boundary. */
					/* -2di-2 is the fake inside node, */
					/* -2di-3 is the fake outside node, */
	int fnp;		/* Number of unique fixed points in list */
	int tinp;		/* Target number of total points in list, including fnp */
	int np;			/* Number of points currently in list */
	node *_n, **n;	/* tinp allocation of points, list of pointers to points */
	int nv;			/* Current number of verticies */
	int nxvno;		/* Next vertex serial number */
	int nxmno;		/* Next midpoint serial number */

	/* Gamut surface definition planes. */
	int nbp;			/* Number of boundary planes. Either 2di or 2di+1 */
	pleq gpeqs[2 + MXPD * 2 + 1];		/* Plane equations associated */
						/* with the fake gamut surface/boundary nodes */
						/* points. Index is 1-ix */
						/* (allow for other fakes, just in case) */
	int sminit;			/* Flag, nz if sc has been inited */
	surfcomb *sc;		/* Array of (1 << nbp) surface combinations */
	int smbits;			/* Total set mask bits */
	int bpsmw;			/* Bits per set mask word */
	int nsmw;			/* Number of setmask words */
	unsigned int lwmask;	/* Last word mask */

	/* Perceptual function handed in. All device values must have been */
	/* clipped before calling this, otherwise use It is assumed that */
	void (*percept)(void *od, double *out, double *in);
	void *od;			/* Opaque data for perceptual point */

	rspl *pcache;		/* cache of perceptual lookup */
	
	/* Other info */
	int rix;			/* Next read index */
	double mn,mx,av;	/* serr stats */
	double smns;		/* Closest node spacing */
	double mxmvsq;		/* Maximum movement during optimisation */
	int optit;			/* Optimization itteration */
	vtx *nxh;			/* Vtxs hit by node (to be deleted) list set by ofps_check_vtx_vn() */
	vtx *nxp;			/* Vtxs that are already parents of added node list (fixups) */
	struct _vtx *batch;	/* Batch update list */
	int checklev;		/* check node recursion level */
	struct _vtx *fchl;	/* Next vertex in fixup check list */
	struct _vtx **svtxs;/* Vertex "to be fixed" list */ 
	int nsvtxs;			/* Number in vertex "to be fixed" list */
	int _nsvtxs;		/* Allocated size of vertex "to be fixed" list */
	struct _node *nup;	/* Next node in 'recomp_nvn' list */

	/* Used and free lists */
	struct _vtx *uvtx;	/* Linked list of used vtx's */
	struct _vtx *fvtx;	/* Linked list of free vtx's */
	struct _vtx *hvtx;	/* Linked list of hidden vtx's */
	struct _mid *umid;	/* Linked list of used mid's */
	struct _mid *fmid;	/* Linked list of free mid's */

	/* Unbounded perceptual model */
	double pmod[MXPD * (1 << MXPD)];
	int pmod_init;		/* It's been initialised */

	/* Acceleration structure */
	int agres;			/* Acceleration grid resolution (not including extra row) */
	double gw; 			/* Grid cell width */
	int gim[MXPD];		/* Grid index multiplier */
	double gcd;			/* Grid cell diagonal */
	int nig;			/* Number of cells in grid (including guard rows) */
	acell *_grid;		/* Pointer to allocated array of grid structures */
	acell *grid;		/* Pointer to base of array of grid structures */
	int agrid_init;		/* accell grid p[] and v[] have been inited */
	unsigned int gflag;	/* Acceleration grid search flag */
	int nacnl;			/* Number of bytes in Accelleration cell neighbour offset list */
	int *acnl;			/* Accelleration cell neighbour offset list */

	int flag;		/* Access flag associated with node being added */
	int nvnflag;	/* node_recomp_nvn_dmxs access flag */
	int fflag;		/* Fixup round flag */
	vtx *vch[VTXCHSIZE];	/* Vertex cache index */

	aat_atree_t *vtreep;	/* Binary tree of vertexes sorted by eperr */
	aat_atree_t *vtrees[MXPD+2];	/* Per nsp, binary tree of vertexes sorted by eserr */
							/* We get di+2 planes for fake initial nodes */

	/* Utility - avoid re-allocation/initialization */
	sobol *sob;
	nodecomb *combs;	/* New node combinations being created in add_to_vsurf() */
	int _ncombs;  /* Number of node combinations allocated. */

	/* Debug/stats */
	int nopstop;	/* Number of optimization passes before stopping with diagnostics */
	int ntostop;	/* Number of points before stopping with diagnostics */
	int positions;	/* Number of calls to locate vertex */
	int dnsqs;		/* Number of dnsq is called */
	int funccount;	/* Number of times dnsq callback function is called */
	int maxfunc;	/* Maximum function count per dnsq */
	int sucfunc;	/* Function count per sucessful dnsq */
	int sucdnsq;	/* Number of sucessful dnsqs */
	int maxretries;	/* Maximum retries used on sucessful dnsq */
	int posfails;	/* Number of position_vtx failures */
	int posfailstp;	/* Number of position_vtx failures this pass */
	int nvtxcreated;	/* Number of vertexes created */
	int nvtxdeleted;	/* Number of vertexes deleted */
	int add_hit;	/* Number of add_to_vsurf hits */
	int add_mis;	/* Number of add_to_vsurf misses */
	int fadd_hit;	/* Number of fixup add_to_vsurf hits */
	int fadd_mis;	/* Number of fixup add_to_vsurf misses */

	int nvcheckhits;	/* Number of vertexes hit durint ofps_check_node() */
	int vvchecks;		/* Number of vertexes checked for hit */
	int vvpchecks;		/* Number of vertexes that would be exaustively checked for hits */
	int naccsrch;		/* Number of accellerated searches */
	int ncellssch;		/* Number of accelleration cells searched */
	int nnschd;			/* Number of nodes nearest searched */
	int nnfschd;		/* Number of nodes for full nearest searched */
	int nvschd;			/* Number of vertexes nearest searched */
	int nvfschd;		/* Number of vertexes for full nearest searched */
	
	int nsurfadds;		/* Number of add_to_vsurf() calls */
	int nhitv;			/* Number of hit vertexes in add_to_vsurf() */
	int maxhitv;		/* Maximum number of hit vertexes in add_to_vsurf() */

	int nfseeds;		/* Number of times searched for vtx with largest eserr */
	int nfseedsvtx;		/* Number of vertexes searched for vtx with largest eserr */
	
	unsigned int l_mstime;	/* Last create surface pass timestamp */
	int l_positions;	/* Last Number of calls to locate vertex */
	int l_nvtxcreated;	/* Last Number of vertexes created */
	int l_nvtxdeleted;	/* Last Number of vertexes deleted */

	struct _vtx *i_uvtx;	/* Incrementallu created vertexes used by DEBUG_RESEED_AFTER_FIXUPS */

/* public: */
	/* return non-zero if the perceptual point is within the device gammut */
	int (*pig)(struct _ofps *s, double *p);

	/* Initialise, ready to read out all the points */
	void (*reset)(struct _ofps *s);

	/* Read the next set of non-fixed points values */
	/* return non-zero when no more points */
	/* p = position, v = value, either may be NULL */
	int (*read)(struct _ofps *s, double *p, double *v);

	/* Calculate and print stats */
	void (*stats)(struct _ofps *s);

	/* Destroy ourselves */
	void (*del)(struct _ofps *s);

	}; typedef struct _ofps ofps;


/* Constructor */
extern ofps *new_ofps(
	int verb,
	int di, double ilimit, int npoints,
	int good,
	double dadaptation,
	double devd_wght,
	double perc_wght,
	double curv_wght,
	fxpos *fxlist, int fxno, 		/* Existing, fixed point list */
	void (*percept)(void *od, double *out, double *in), void *od);

/* Extended constructor */
ofps *new_ofps_ex(
int verb,				/* Verbosity */
int di,					/* Dimensionality of device space */
double ilimit,			/* Ink limit (sum of device coords max) */
double *imin,			/* Ink limit - limit on min of p[], normally >= 0.0 */
double *imax,			/* Ink limit - limit on min of p[], normally <= 1.0  */
int tinp,				/* Total number of points to generate, including fixed */
int good,				/* 0 = fast, 1 = good */
double dadaptation,		/* Degree of adaptation to device characteristic 0.0 - 1.0, */
						/* use -ve value for explicit weightings: */
double devd_wght,		/* Device space weighting (if dad < 0) */
double perc_wght,		/* Perceptual space weighting (if dad < 0) */
double curv_wght,		/* Curvature weighting (if dad < 0) */
fxpos *fxlist,			/* List of existing fixed points (may be NULL) */
int fxno,				/* Number of existing fixes points */
void (*percept)(void *od, double *out, double *in),		/* Perceptual lookup func. */
void *od,				/* context for Perceptual function */
int ntostop,			/* Debug - number of points until diagnostic stop */
int nopstop				/* Debug - number of optimizations until diagnostic stop, -1 = not */
);

#define OFPS_H
#endif /* OFPS_H */