summaryrefslogtreecommitdiff
path: root/rspl/rev.h
diff options
context:
space:
mode:
Diffstat (limited to 'rspl/rev.h')
-rw-r--r--rspl/rev.h222
1 files changed, 153 insertions, 69 deletions
diff --git a/rspl/rev.h b/rspl/rev.h
index b947cbe..6fc79cb 100644
--- a/rspl/rev.h
+++ b/rspl/rev.h
@@ -37,21 +37,22 @@
* with a cartesian coordinate, but the parameter order corresponds with
* the baricentric order.
*
- * For example, given cartesian coordinates D0, D1, D2
- * these should be sorted from smallest to largest, thereby
- * choosing a particular simplex within a cube, and allowing
- * a correspondence to the parameter coordinates, ie:
+ * For example, given cartesian sub-coordinates D0, D1, D2
+ * into a (3D) forward interpolation cube, these should be sorted
+ * from smallest to largest, thereby choosing a particular
+ * simplex within a cube, and allowing a correspondence to
+ * the parameter coordinates, ie:
*
- * D1 D0 D2 Smallest -> Largest cartesian sort
- * P2 P1 P0 Corresponding Parameter coordinates (note reverse order!)
+ * D2 D0 D1 Smallest -> Largest cartesian sort
+ * P0 P1 P2 Corresponding Parameter coordinates
*
- * B0 = P0 Conversion to Baricentric coordinates
+ * B0 = P0 Conversion to Baricentric weighting/coordinates
* B1 = P1 - P0
* B2 = P2 - P1
* B3 = 1 - P2
*
- * The vertex values directly correspond to Baricentric coordinates,
- * giving the usual interpolation equation of:
+ * The 4 (tetrahedron) vertex values directly correspond to Baricentric
+ * weighting/coordinates, giving the usual interpolation equation of:
*
* VV0 * B0
* + VV1 * B1
@@ -66,21 +67,42 @@
* + VV2 - VV3 * P2
* + VV3
*
+ * Note that withing the simplex, 0 <= P0 && P0 <= P1 && P1 <= P2 && P2 <= 1
+ *
* It is this which is used in rev.c for solving the reverse
* interpolation problem.
*/
-/* A structure to hold per simplex coordinate and vertex mapping */
+/* - - - - - - - - - - - - - - - - - - - - - */
+/* Group size information for nn LCh weighted quick accept/reject testing */
+typedef struct {
+ double bcent[MXRO]; /* Group center location in output space */
+ double brad; /* Output value bounding shere radius */
+ double bradsq; /* Output value bounding shere radius squared */
+
+ double maxDlc; /* Maximum members weighted delta LC (+extra dims) squared */
+ double maxDh; /* Maximum members delta h squared */
+ double maxDh_; /* Maximum members delta h (not squared) */
+ double sratio; /* Minimum members C ratio to Gc squared */
+ double bratio; /* Maximum members C ratio to Gc squared */
+ double Wsratio; /* Minimum members C ratio to Gc squared - pre-weighted */
+ double Wbratio; /* Maximum members C ratio to Gc squared - pre-weighted */
+ double Gc; /* Group center Chrominance squared */
+ double Gc_; /* Group center Chrominance (not squared) */
+} nn_grp;
+
+/* - - - - - - - - - - - - - - - - - - - - - */
+/* A structure to hold per simplex coordinate and vertex mapping for ssxinfo. */
/* This is relative to the construction cube. A face sub-simplex */
/* that is common between cubes, will have a different psxinfo */
/* depending on which cube created it. */
typedef struct {
int face; /* Flag, nz if simplex lies on cube surface */
- int icomb[MXDI]; /* Index by Absolute[di] -> Simplex Parameter[sdi], */
+ int icomb[MXDI]; /* icomb[] specifies the equation to convert simplex space */
+ /* coordinates back into cartesian space. */
+ /* Index by Absolute[di] -> Simplex Parameter[sdi], */
/* -1 == value 0, -2 == value 1 */
/* Note that many Abs can map to one Param to form a sum. */
- /* icomb[] specifies the equation to convert simplex space */
- /* coordinates back into cartesian space. */
int offs[MXDI+1]; /* Offsets to simplex verticies within cube == bit per dim */
int goffs[MXDI+1]; /* Offsets to simplex verticies within grid */
int foffs[MXDI+1]; /* Fwd grid floating offsets to simplex verticies from cube base */
@@ -97,9 +119,9 @@ typedef struct {
/* - - - - - - - - - - - - - - - - - - - - - */
/* NOTE :- This should really be re-arranged to be per-sub-simplex caching, */
-/* rather than cell caching. Rather than stash the simplex info in the cells, */
+/* rather than fxcell caching. Rather than stash the simplex info in the fxcells, */
/* create a separate cache or some other way of sharing the common simplexes. */
-/* The code that ignores common face simplexes in cells could then be removed. */
+/* The code that ignores common face simplexes in fxcells could then be removed (?). */
/* Simplex definition. Each top level fwd interpolation cell, */
/* is decomposed into sub-simplexes. Sub-simplexes are of equal or */
@@ -111,12 +133,12 @@ struct _simplex {
int si; /* Diagnostic - simplex number within level */
int sdi; /* Sub-simplex dimensionality */
int efdi; /* Effective fdi. This will be = fdi for a non clip */
- /* plane simplex, and fdi+1 for a clip plane simplex */
- /* The DOF (Degress of freedom) withing this simplex = sdi - efdi */
+ /* plane simplex, and fdi+1 for a clip plane simplex. */
+ /* The DOF (Degress of freedom) within this simplex = sdi - efdi */
psxinfo *psxi; /* Generic per simplex info (construction cube relative) */
int vix[MXRI+1]; /* fwd cell vertex indexes of this simplex [sdi+1] */
- /* This is a universal identification of this simplex */
+ /* This is a universal identification of this simplex. */
struct _simplex *hlink; /* Link to other cells with this hash */
unsigned int touch; /* Last touch count. */
short flags; /* Various flags */
@@ -130,7 +152,6 @@ struct _simplex {
#define SPLX_FLAG_5 0x40 /* auxiliary lu/svd initialised */
#define SPLX_FLAG_5F 0x80 /* auxiliary lu/svd init. failed */
-
#define SPLX_FLAGS (SPLX_FLAG_1 | SPLX_FLAG_2 | SPLX_FLAG_2F \
| SPLX_FLAG_4 | SPLX_FLAG_5 | SPLX_FLAG_5F)
@@ -151,7 +172,7 @@ struct _simplex {
double min[MXRO+1], max[MXRO+1]; /* Simplex vertex output space [fdi+1] and */
/* ink limit bounding values at minmax[fdi] */
- /* If sdi == efdi, this holds the LU decomposition */
+ /* If sdi == efdi, this holds the LU decomposition, */
/* else this holds the SVD and solution locus info */
char *aloc2; /* Memory allocation for #2 & #4 */
@@ -187,27 +208,31 @@ struct _simplex {
}; typedef struct _simplex simplex;
-/* A candidate search cell (cell cache entry structure) */
-struct _cell {
+/* A candidate search (fwd) fxcell (cell cache entry structure) */
+struct _fxcell {
struct _rspl *s; /* Pointer to parent rspl */
/* Cache information */
- int ix; /* Fwd cell index */
- struct _cell *hlink; /* Link to other cells with this hash */
- struct _cell *mrudown; /* Links to next most recently used cell */
- struct _cell *mruup;
+ int ix; /* Corresponding fwd cell index */
+ struct _fxcell *hlink; /* Link to other cells with this hash */
+ struct _fxcell *mrudown;/* Links to next most recently used fxcell */
+ struct _fxcell *mruup;
int refcount; /* Reference count */
- int flags; /* Non-zero if the cell has been initialised */
-#define CELL_FLAG_1 0x01 /* Basic initialisation */
+ int flags; /* Non-zero if the fxcell has been initialised */
+#define CELL_FLAG_1 0x01 /* Basic initialisation, including nn_grp */
#define CELL_FLAG_2 0x02 /* Simplex information initialised */
/* Use information */
double sort; /* Sort key */
+ double limmin, limmax; /* limit() min/max for this fxcell */
- double limmin, limmax; /* limit() min/max for this cell */
- double bcent[MXRO]; /* Output value bounding shere center */
- double brad; /* Output value bounding shere radius */
- double bradsq; /* Output value bounding shere radius squared */
+ /* Quick nn distance information */
+ nn_grp g;
+
+// double bcent[MXRO]; /* Output value bounding shere center */
+// double brad; /* Output value bounding shere radius */
+// double bradsq; /* Output value bounding shere radius squared */
+// double wbrad; /* Output value weighted bounding shere radius */
double p[POW2MXRI][MXRI]; /* Vertex input positions for this cube. */
/* Copied to x->pmin/pmax[] & ink limit */
@@ -215,18 +240,61 @@ struct _cell {
double v[POW2MXRI][MXRO+1]; /* Vertex data for this cube. Copied to x->v[] */
/* v[][fdi] is the ink limit values, if relevant */
- simplex **sx[MXRI+1]; /* Lists of simplexes that make up this cell. */
+ simplex **sx[MXRI+1]; /* Lists of simplexes that make up this fxcell. */
/* Each list indexed by the non-limited simplex */
/* dimensionality (similar to sspxi[]) */
/* Each list will be NULL if it hasn't been created yet */
int sxno[MXRI+1]; /* Corresponding count of each list */
-}; typedef struct _cell cell;
+}; typedef struct _fxcell fxcell;
+
+/* surface bxcell sl status */
+typedef enum {
+ bx_uninit = 0, /* sl is not initialised */
+ bx_filled = 1, /* sl has been filled with initial fwd cell vertexes */
+ bx_rethinnd = 2, /* sl vertexes need to be re-thinned */
+ bx_thinned = 3, /* sl vertexes have been thinned */
+ bx_conv = 4 /* sl vertexes have been converted to fwd cell indexes */
+} bxstat;
+
+/* Structure to hold bwd cell information for surface list, and also */
+/* for seed fill bwd cell propogation. (Cells on surface will have two */
+/* of these) */
+struct _bxcell{
+ int ix; /* nnrev[] index of this bwd cell */
+ int gc[MXRO]; /* coordinate of this bwd cell */
+ nn_grp g; /* Group nn calculation info */
+ struct _bxcell *ss; /* bwd surface cell to start search from */
+ double sdist; /* Est. wtd distance from this cell to ss */
+ int tix; /* target rev[] index being filled (visited check) */
+
+ bxstat status; /* State of sl list */
+ int *sl; /* fwd vertex seed list for surface bxcells */
+ int *dl; /* deleted fwd vertex list for this bxcell */
+
+ int *scell; /* If non-NULL, this is a (non-surface) */
+ /* seeding super bxcell, and scell contains */
+ /* the list of bxcells covered */
+
+ struct _bxcell *slist; /* Linked list of all surface bxcells */
+ struct _bxcell *hlink; /* Linked list of surface bxcells with same ix hash */
+ struct _bxcell *xlist; /* Linked list of surface exploration search region */
+ double emin; /* estimated minimum wtd distance of this cell in current search */
+ struct _bxcell *tlist; /* Linked list of solution surface cells for current search. */
+
+ struct _bxcell *flist; /* Linked list for nnrev[] fill seeds */
+
+ double cc; /* Distance of group from gamut center */
+ double dw; /* Delta width from ocent of furthest point */
+ struct _bxcell *wlist; /* Linked list for shadow bxcells during thinning */
+
+ int debug; /* debug flag - for VRML tagging */
+}; typedef struct _bxcell bxcell;
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
-/* Enough space is needed to cache all the cells/simplexes */
+/* Enough space is needed to cache all the fxcells/simplexes */
/* for a full aux. locus, or the query will be processed in */
/* several "chunks" and will be slower. */
/* This sets the basic memory usage of the rev code. */
@@ -239,20 +307,20 @@ struct _cell {
/* rev as a fraction of the System RAM. */
#define HASH_FILL_RATIO 3 /* 3 Ratio of entries to hash size */
-/* The structure where cells are allocated and cached. */
+/* The structure where fxcells and simplexes are allocated and cached. */
-/* Holds the cell and simplex match cache specific information */
+/* Holds the fxcell and simplex match cache specific information */
typedef struct {
struct _rspl *s; /* Pointer to parent rspl */
int nacells; /* Number of allocated cells */
int nunlocked; /* Number of unlocked cells that could be freed */
int cell_hash_size; /* Current size of cell hash list */
- cell **hashtop; /* Top of hash list [cell_hash_size] */
- cell *mrutop, *mrubot; /* Top and bottom pointers of mru list */
- /* that tracks allocated cells */
+ fxcell **hashtop; /* Top of hash list [cell_hash_size] */
+ fxcell *mrutop, *mrubot; /* Top and bottom pointers of mru list */
+ /* that tracks allocated fxcells */
- int spx_hash_size; /* Current size of simplex hash list */
- simplex **spxhashtop; /* Face simplex hash index list */
+ int spx_hash_size; /* Current size of shared face simplex hash list */
+ simplex **spxhashtop; /* Shared face simplex hash index list */
int nspx; /* Number of simplexes in hash list */
} revcache;
@@ -296,8 +364,8 @@ struct _schbase {
int ixc; /* Cube index of corner that holds maximum input values */
int snsdi, ensdi; /* Start and end extra sub-simplex dimensionality */
- int (*setsort)(struct _schbase *b, cell *c); /* Function to triage & set cube sort index */
- int (*check)(struct _schbase *b, cell *c); /* Function to recheck cube worth keeping */
+ int (*setsort)(struct _schbase *b, fxcell *c); /* Function to triage & set cube sort index */
+ int (*check)(struct _schbase *b, fxcell *c); /* Function to recheck cube worth keeping */
int (*compute)(struct _schbase *b, simplex *x); /* Function to compute a simplex solution */
double v[MXRO+1]; /* Target output value, + ink limit */
@@ -314,7 +382,7 @@ struct _schbase {
double ncdir[MXRO]; /* Normalised clip vector */
double **cla; /* Clip vector LHS implicit equation matrix [fdi][fdi+1] (inc. ink tgt.) */
double clb[MXRO+1]; /* Clip vector RHS implicit equation vector [fdi+1] (inc. ink tgt.) */
- double cdist; /* Best clip locus distance found (aim is min +ve) */
+ double cdist; /* Best clip locus distance found (aim is min +ve) :- weighted for nn */
int iclip; /* NZ if result is above (disabled) ink limit */
int mxsoln; /* Maximum number of solutions that we want */
@@ -328,20 +396,17 @@ struct _schbase {
int axislz; /* Space allocated to axisl[] */
axisec *axisl; /* Auxiliary intersections */
- int lclistz; /* Allocated space to cell sort list */
- cell **lclist; /* Sorted list of pointers to candidate cells */
+ int lclistz; /* Allocated space to fxcell sort list */
+ fxcell **lclist; /* Sorted list of pointers to candidate fxcells */
- int pauxcell; /* Indexe of previous call solution cell, -1 if not relevant */
- int plmaxcell; /* Indexe of previous call solution cell, -1 if not relevant */
- int plmincell; /* Indexe of previous call solution cell, -1 if not relevant */
+ int pauxcell; /* Indexe of previous call solution fxcell, -1 if not relevant */
+ int plmaxcell; /* Indexe of previous call solution fxcell, -1 if not relevant */
+ int plmincell; /* Indexe of previous call solution fxcell, -1 if not relevant */
int lsxfilt; /* Allocated space of simplex filter list */
- char *sxfilt; /* Flag for simplexes that should be in a cell */
+ char *sxfilt; /* Flag for simplexes that should be in an fxcell */
- double crad; /* nn current radius distance */
- double bw; /* nn current window distance */
- int wex[MXRO * 2]; /* nn current window edge indexes */
- double wed[MXRO * 2]; /* nn current window edge distances */
+ int rix; /* Diagnostic - rev[] or nnrev[] index for this point */
}; typedef struct _schbase schbase;
@@ -376,7 +441,12 @@ struct _rev_struct {
/* All other sections depend on this. */
int fastsetup; /* Flag - NZ if fast setup at cost of slow throughput */
- struct _rev_struct *next; /* Linked list of instances sharing memory */
+ int lchweighted; /* Non-zero if nearest search is LCh weighted */
+ double lchw[MXRO]; /* LCh nearest weighting */
+ double lchw_sq[MXRO]; /* LCh nearest weighting squared */
+ double lchw_chsq; /* lchw_sq[1] - lchw_sq[2] */
+
+ struct _rev_struct *next; /* Linked list of global instances sharing memory */
size_t max_sz; /* Maximum size permitted */
size_t sz; /* Total memory current allocated by rev */
@@ -385,32 +455,38 @@ struct _rev_struct {
#endif
/* Reverse grid lookup information */
- int ares; /* Reverse grid allocated resolution, = res + 1, */
- /* allows for extra row used during construction */
int res; /* Reverse grid resolution == ncells on a side */
int no; /* Total number of points in reverse grid = rev.ares ^ fdi */
int coi[MXRO]; /* Coordinate increments for each dimension */
int hoi[1 << MXRO]; /* Coordinate increments for progress through cube */
- datao gl,gh,gw; /* Reverse grid low, high, grid cell width */
+ datao gl,gh,gw; /* Reverse grid low, high, grid bwd cell width */
/* Second section, accelleration information that changes with ink limit. */
int rev_valid; /* nz if this information in rev[] and nnrev[] is valid */
int **rev; /* Exact reverse lookup starting list. */
- /* rev.no pointers to lists of fwd grid indexes. */
- /* First int is allocation length */
- /* Second int is reference count */
- /* Then follows cube indexes */
- /* Last int is -1 */
int **nnrev; /* Nearest reverse lookup starting list. */
- /* rev.no pointers to lists of fwd grid indexes. */
+ /* These lists are of fwd grid indexes. */
/* [0] is allocation length */
- /* [1] is the next free entry index */
- /* [2] is reference count */
+ /* [1] is the next free entry index (length + 3, not counting -1) */
+ /* [2] is index into share lists, -1 if not shared. */
/* Then follows cube indexes */
- /* The last entry is marked with -1 */
+ /* Last entry is marked with -1 */
+
+ double ocent[MXRO]; /* rev cell gamut "center" point for thinning and shadow testing. */
+
+ bxcell *surflist; /* Linked list of rev[] bwd cells that contain gamut surface fwd cells. */
+ /* Used to speed up fill_nncell() when rev.fastsetup is set, else NULL */
+ int surf_hash_size; /* Current size of bxcell hash list */
+ bxcell **surfhash; /* bxcell hash index list */
+
+ int **sharelist; /* Array of pointers to shared (fwd grid list sharer) records. */
+ /* Each record is same format as rev[]/nnrev[], except */
+ /* [2] is used to detect scanning the same list. */
+ int sharellen; /* Size of sharelist */
+ int sharelaloc; /* Allocation size of sharelist */
/* Third section */
- revcache *cache; /* Where cells are allocated and cached */
+ revcache *cache; /* Where fxcells and simplexes are allocated and cached */
/* Sub-dimension simplex information */
ssxinfo sspxi[MXRI+1];/* One per sub dimenstionality at offset sdi */
@@ -425,6 +501,14 @@ struct _rev_struct {
int primsecwarn; /* Not primary or secondary warning has been issued */
+#ifdef CHECK_NNLU
+int cknn_no; /* Number checked */
+double cknn_we; /* Worst DE */
+int cknn_noerrs; /* Number not as good as closet vertex */
+int cknn_nobsb; /* Number not as good as second closest vertex */
+int cknn_nonis; /* Number not in surface */
+#endif /* CHECK_NNLU */
+
}; typedef struct _rev_struct rev_struct;