1 //---------------------------------------------------------------------------------
3 // Little Color Management System
4 // Copyright (c) 1998-2011 Marti Maria Saguer
6 // Permission is hereby granted, free of charge, to any person obtaining
7 // a copy of this software and associated documentation files (the "Software"),
8 // to deal in the Software without restriction, including without limitation
9 // the rights to use, copy, modify, merge, publish, distribute, sublicense,
10 // and/or sell copies of the Software, and to permit persons to whom the Software
11 // is furnished to do so, subject to the following conditions:
13 // The above copyright notice and this permission notice shall be included in
14 // all copies or substantial portions of the Software.
16 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO
18 // THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
19 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
20 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
21 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
22 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24 //---------------------------------------------------------------------------------
27 #include "lcms2_internal.h"
30 // ------------------------------------------------------------------------
32 // Gamut boundary description by using Jan Morovic's Segment maxima method
33 // Many thanks to Jan for allowing me to use his algorithm.
39 #define SECTORS 16 // number of divisions in alpha and theta
41 // Spherical coordinates
45 cmsFloat64Number alpha
;
46 cmsFloat64Number theta
;
61 cmsSpherical p
; // Keep also alpha & theta of maximum
69 cmsGDBPoint Gamut
[SECTORS
][SECTORS
];
74 // A line using the parametric form
84 // A plane using the parametric form
96 // --------------------------------------------------------------------------------------------
98 // ATAN2() which always returns degree positive numbers
101 cmsFloat64Number
_cmsAtan2(cmsFloat64Number y
, cmsFloat64Number x
)
105 // Deal with undefined case
106 if (x
== 0.0 && y
== 0.0) return 0;
108 a
= (atan2(y
, x
) * 180.0) / M_PI
;
117 // Convert to spherical coordinates
119 void ToSpherical(cmsSpherical
* sp
, const cmsVEC3
* v
)
122 cmsFloat64Number L
, a
, b
;
128 sp
->r
= sqrt( L
*L
+ a
*a
+ b
*b
);
131 sp
->alpha
= sp
->theta
= 0;
135 sp
->alpha
= _cmsAtan2(a
, b
);
136 sp
->theta
= _cmsAtan2(sqrt(a
*a
+ b
*b
), L
);
140 // Convert to cartesian from spherical
142 void ToCartesian(cmsVEC3
* v
, const cmsSpherical
* sp
)
144 cmsFloat64Number sin_alpha
;
145 cmsFloat64Number cos_alpha
;
146 cmsFloat64Number sin_theta
;
147 cmsFloat64Number cos_theta
;
148 cmsFloat64Number L
, a
, b
;
150 sin_alpha
= sin((M_PI
* sp
->alpha
) / 180.0);
151 cos_alpha
= cos((M_PI
* sp
->alpha
) / 180.0);
152 sin_theta
= sin((M_PI
* sp
->theta
) / 180.0);
153 cos_theta
= cos((M_PI
* sp
->theta
) / 180.0);
155 a
= sp
->r
* sin_theta
* sin_alpha
;
156 b
= sp
->r
* sin_theta
* cos_alpha
;
157 L
= sp
->r
* cos_theta
;
165 // Quantize sector of a spherical coordinate. Saturate 360, 180 to last sector
166 // The limits are the centers of each sector, so
168 void QuantizeToSector(const cmsSpherical
* sp
, int* alpha
, int* theta
)
170 *alpha
= (int) floor(((sp
->alpha
* (SECTORS
)) / 360.0) );
171 *theta
= (int) floor(((sp
->theta
* (SECTORS
)) / 180.0) );
173 if (*alpha
>= SECTORS
)
175 if (*theta
>= SECTORS
)
180 // Line determined by 2 points
182 void LineOf2Points(cmsLine
* line
, cmsVEC3
* a
, cmsVEC3
* b
)
185 _cmsVEC3init(&line
->a
, a
->n
[VX
], a
->n
[VY
], a
->n
[VZ
]);
186 _cmsVEC3init(&line
->u
, b
->n
[VX
] - a
->n
[VX
],
187 b
->n
[VY
] - a
->n
[VY
],
188 b
->n
[VZ
] - a
->n
[VZ
]);
192 // Evaluate parametric line
194 void GetPointOfLine(cmsVEC3
* p
, const cmsLine
* line
, cmsFloat64Number t
)
196 p
->n
[VX
] = line
->a
.n
[VX
] + t
* line
->u
.n
[VX
];
197 p
->n
[VY
] = line
->a
.n
[VY
] + t
* line
->u
.n
[VY
];
198 p
->n
[VZ
] = line
->a
.n
[VZ
] + t
* line
->u
.n
[VZ
];
204 Closest point in sector line1 to sector line2 (both are defined as 0 <=t <= 1)
205 http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm
207 Copyright 2001, softSurfer (www.softsurfer.com)
208 This code may be freely used and modified for any purpose
209 providing that this copyright notice is included with it.
210 SoftSurfer makes no warranty for this code, and cannot be held
211 liable for any real or imagined damage resulting from its use.
212 Users of this code must verify correctness for their application.
217 cmsBool
ClosestLineToLine(cmsVEC3
* r
, const cmsLine
* line1
, const cmsLine
* line2
)
219 cmsFloat64Number a
, b
, c
, d
, e
, D
;
220 cmsFloat64Number sc
, sN
, sD
;
221 cmsFloat64Number tc
, tN
, tD
;
224 _cmsVEC3minus(&w0
, &line1
->a
, &line2
->a
);
226 a
= _cmsVEC3dot(&line1
->u
, &line1
->u
);
227 b
= _cmsVEC3dot(&line1
->u
, &line2
->u
);
228 c
= _cmsVEC3dot(&line2
->u
, &line2
->u
);
229 d
= _cmsVEC3dot(&line1
->u
, &w0
);
230 e
= _cmsVEC3dot(&line2
->u
, &w0
);
232 D
= a
*c
- b
* b
; // Denominator
233 sD
= tD
= D
; // default sD = D >= 0
235 if (D
< MATRIX_DET_TOLERANCE
) { // the lines are almost parallel
237 sN
= 0.0; // force using point P0 on segment S1
238 sD
= 1.0; // to prevent possible division by 0.0 later
242 else { // get the closest points on the infinite lines
247 if (sN
< 0.0) { // sc < 0 => the s=0 edge is visible
253 else if (sN
> sD
) { // sc > 1 => the s=1 edge is visible
260 if (tN
< 0.0) { // tc < 0 => the t=0 edge is visible
263 // recompute sc for this edge
273 else if (tN
> tD
) { // tc > 1 => the t=1 edge is visible
277 // recompute sc for this edge
280 else if ((-d
+ b
) > a
)
287 // finally do the division to get sc and tc
288 sc
= (fabs(sN
) < MATRIX_DET_TOLERANCE
? 0.0 : sN
/ sD
);
289 tc
= (fabs(tN
) < MATRIX_DET_TOLERANCE
? 0.0 : tN
/ tD
);
291 GetPointOfLine(r
, line1
, sc
);
297 // ------------------------------------------------------------------ Wrapper
300 // Allocate & free structure
301 cmsHANDLE CMSEXPORT
cmsGBDAlloc(cmsContext ContextID
)
303 cmsGDB
* gbd
= (cmsGDB
*) _cmsMallocZero(ContextID
, sizeof(cmsGDB
));
304 if (gbd
== NULL
) return NULL
;
306 gbd
-> ContextID
= ContextID
;
308 return (cmsHANDLE
) gbd
;
312 void CMSEXPORT
cmsGBDFree(cmsHANDLE hGBD
)
314 cmsGDB
* gbd
= (cmsGDB
*) hGBD
;
316 _cmsFree(gbd
->ContextID
, (void*) gbd
);
320 // Auxiliar to retrieve a pointer to the segmentr containing the Lab value
322 cmsGDBPoint
* GetPoint(cmsGDB
* gbd
, const cmsCIELab
* Lab
, cmsSpherical
* sp
)
328 _cmsAssert(gbd
!= NULL
);
329 _cmsAssert(Lab
!= NULL
);
330 _cmsAssert(sp
!= NULL
);
332 // Center L* by substracting half of its domain, that's 50
333 _cmsVEC3init(&v
, Lab
->L
- 50.0, Lab
->a
, Lab
->b
);
335 // Convert to spherical coordinates
338 if (sp
->r
< 0 || sp
->alpha
< 0 || sp
->theta
< 0) {
339 cmsSignalError(gbd
->ContextID
, cmsERROR_RANGE
, "spherical value out of range");
343 // On which sector it falls?
344 QuantizeToSector(sp
, &alpha
, &theta
);
346 if (alpha
< 0 || theta
< 0 || alpha
>= SECTORS
|| theta
>= SECTORS
) {
347 cmsSignalError(gbd
->ContextID
, cmsERROR_RANGE
, " quadrant out of range");
351 // Get pointer to the sector
352 return &gbd
->Gamut
[theta
][alpha
];
355 // Add a point to gamut descriptor. Point to add is in Lab color space.
356 // GBD is centered on a=b=0 and L*=50
357 cmsBool CMSEXPORT
cmsGDBAddPoint(cmsHANDLE hGBD
, const cmsCIELab
* Lab
)
359 cmsGDB
* gbd
= (cmsGDB
*) hGBD
;
364 // Get pointer to the sector
365 ptr
= GetPoint(gbd
, Lab
, &sp
);
366 if (ptr
== NULL
) return FALSE
;
368 // If no samples at this sector, add it
369 if (ptr
->Type
== GP_EMPTY
) {
371 ptr
-> Type
= GP_SPECIFIED
;
377 // Substitute only if radius is greater
378 if (sp
.r
> ptr
-> p
.r
) {
380 ptr
-> Type
= GP_SPECIFIED
;
388 // Check if a given point falls inside gamut
389 cmsBool CMSEXPORT
cmsGDBCheckPoint(cmsHANDLE hGBD
, const cmsCIELab
* Lab
)
391 cmsGDB
* gbd
= (cmsGDB
*) hGBD
;
395 // Get pointer to the sector
396 ptr
= GetPoint(gbd
, Lab
, &sp
);
397 if (ptr
== NULL
) return FALSE
;
399 // If no samples at this sector, return no data
400 if (ptr
->Type
== GP_EMPTY
) return FALSE
;
402 // In gamut only if radius is greater
404 return (sp
.r
<= ptr
-> p
.r
);
407 // -----------------------------------------------------------------------------------------------------------------------
409 // Find near sectors. The list of sectors found is returned on Close[].
410 // The function returns the number of sectors as well.
418 // Those are the relative movements
419 // {-2,-2}, {-1, -2}, {0, -2}, {+1, -2}, {+2, -2},
420 // {-2,-1}, {-1, -1}, {0, -1}, {+1, -1}, {+2, -1},
421 // {-2, 0}, {-1, 0}, {0, 0}, {+1, 0}, {+2, 0},
422 // {-2,+1}, {-1, +1}, {0, +1}, {+1, +1}, {+2, +1},
423 // {-2,+2}, {-1, +2}, {0, +2}, {+1, +2}, {+2, +2}};
427 const struct _spiral
{
431 } Spiral
[] = { {0, -1}, {+1, -1}, {+1, 0}, {+1, +1}, {0, +1}, {-1, +1},
432 {-1, 0}, {-1, -1}, {-1, -2}, {0, -2}, {+1, -2}, {+2, -2},
433 {+2, -1}, {+2, 0}, {+2, +1}, {+2, +2}, {+1, +2}, {0, +2},
434 {-1, +2}, {-2, +2}, {-2, +1}, {-2, 0}, {-2, -1}, {-2, -2} };
436 #define NSTEPS (sizeof(Spiral) / sizeof(struct _spiral))
439 int FindNearSectors(cmsGDB
* gbd
, int alpha
, int theta
, cmsGDBPoint
* Close
[])
446 for (i
=0; i
< NSTEPS
; i
++) {
448 a
= alpha
+ Spiral
[i
].AdvX
;
449 t
= theta
+ Spiral
[i
].AdvY
;
455 // Cycle at the begin
456 if (a
< 0) a
= SECTORS
+ a
;
457 if (t
< 0) t
= SECTORS
+ t
;
459 pt
= &gbd
->Gamut
[t
][a
];
461 if (pt
-> Type
!= GP_EMPTY
) {
463 Close
[nSectors
++] = pt
;
471 // Interpolate a missing sector. Method identifies whatever this is top, bottom or mid
473 cmsBool
InterpolateMissingSector(cmsGDB
* gbd
, int alpha
, int theta
)
480 cmsGDBPoint
* Close
[NSTEPS
+ 1];
481 cmsSpherical closel
, templ
;
485 // Is that point already specified?
486 if (gbd
->Gamut
[theta
][alpha
].Type
!= GP_EMPTY
) return TRUE
;
489 nCloseSectors
= FindNearSectors(gbd
, alpha
, theta
, Close
);
492 // Find a central point on the sector
493 sp
.alpha
= (cmsFloat64Number
) ((alpha
+ 0.5) * 360.0) / (SECTORS
);
494 sp
.theta
= (cmsFloat64Number
) ((theta
+ 0.5) * 180.0) / (SECTORS
);
497 // Convert to Cartesian
498 ToCartesian(&Lab
, &sp
);
500 // Create a ray line from centre to this point
501 _cmsVEC3init(&Centre
, 50.0, 0, 0);
502 LineOf2Points(&ray
, &Lab
, &Centre
);
504 // For all close sectors
509 for (k
=0; k
< nCloseSectors
; k
++) {
511 for(m
= k
+1; m
< nCloseSectors
; m
++) {
513 cmsVEC3 temp
, a1
, a2
;
515 // A line from sector to sector
516 ToCartesian(&a1
, &Close
[k
]->p
);
517 ToCartesian(&a2
, &Close
[m
]->p
);
519 LineOf2Points(&edge
, &a1
, &a2
);
522 ClosestLineToLine(&temp
, &ray
, &edge
);
524 // Convert to spherical
525 ToSpherical(&templ
, &temp
);
528 if ( templ
.r
> closel
.r
&&
529 templ
.theta
>= (theta
*180.0/SECTORS
) &&
530 templ
.theta
<= ((theta
+1)*180.0/SECTORS
) &&
531 templ
.alpha
>= (alpha
*360.0/SECTORS
) &&
532 templ
.alpha
<= ((alpha
+1)*360.0/SECTORS
)) {
539 gbd
->Gamut
[theta
][alpha
].p
= closel
;
540 gbd
->Gamut
[theta
][alpha
].Type
= GP_MODELED
;
547 // Interpolate missing parts. The algorithm fist computes slices at
548 // theta=0 and theta=Max.
549 cmsBool CMSEXPORT
cmsGDBCompute(cmsHANDLE hGBD
, cmsUInt32Number dwFlags
)
552 cmsGDB
* gbd
= (cmsGDB
*) hGBD
;
554 _cmsAssert(hGBD
!= NULL
);
557 for (alpha
= 0; alpha
< SECTORS
; alpha
++) {
559 if (!InterpolateMissingSector(gbd
, alpha
, 0)) return FALSE
;
563 for (alpha
= 0; alpha
< SECTORS
; alpha
++) {
565 if (!InterpolateMissingSector(gbd
, alpha
, SECTORS
-1)) return FALSE
;
570 for (theta
= 1; theta
< SECTORS
; theta
++) {
571 for (alpha
= 0; alpha
< SECTORS
; alpha
++) {
573 if (!InterpolateMissingSector(gbd
, alpha
, theta
)) return FALSE
;
580 cmsUNUSED_PARAMETER(dwFlags
);
586 // --------------------------------------------------------------------------------------------------------
588 // Great for debug, but not suitable for real use
591 cmsBool
cmsGBDdumpVRML(cmsHANDLE hGBD
, const char* fname
)
595 cmsGDB
* gbd
= (cmsGDB
*) hGBD
;
598 fp
= fopen (fname
, "wt");
602 fprintf (fp
, "#VRML V2.0 utf8\n");
604 // set the viewing orientation and distance
605 fprintf (fp
, "DEF CamTest Group {\n");
606 fprintf (fp
, "\tchildren [\n");
607 fprintf (fp
, "\t\tDEF Cameras Group {\n");
608 fprintf (fp
, "\t\t\tchildren [\n");
609 fprintf (fp
, "\t\t\t\tDEF DefaultView Viewpoint {\n");
610 fprintf (fp
, "\t\t\t\t\tposition 0 0 340\n");
611 fprintf (fp
, "\t\t\t\t\torientation 0 0 1 0\n");
612 fprintf (fp
, "\t\t\t\t\tdescription \"default view\"\n");
613 fprintf (fp
, "\t\t\t\t}\n");
614 fprintf (fp
, "\t\t\t]\n");
615 fprintf (fp
, "\t\t},\n");
616 fprintf (fp
, "\t]\n");
619 // Output the background stuff
620 fprintf (fp
, "Background {\n");
621 fprintf (fp
, "\tskyColor [\n");
622 fprintf (fp
, "\t\t.5 .5 .5\n");
623 fprintf (fp
, "\t]\n");
626 // Output the shape stuff
627 fprintf (fp
, "Transform {\n");
628 fprintf (fp
, "\tscale .3 .3 .3\n");
629 fprintf (fp
, "\tchildren [\n");
631 // Draw the axes as a shape:
632 fprintf (fp
, "\t\tShape {\n");
633 fprintf (fp
, "\t\t\tappearance Appearance {\n");
634 fprintf (fp
, "\t\t\t\tmaterial Material {\n");
635 fprintf (fp
, "\t\t\t\t\tdiffuseColor 0 0.8 0\n");
636 fprintf (fp
, "\t\t\t\t\temissiveColor 1.0 1.0 1.0\n");
637 fprintf (fp
, "\t\t\t\t\tshininess 0.8\n");
638 fprintf (fp
, "\t\t\t\t}\n");
639 fprintf (fp
, "\t\t\t}\n");
640 fprintf (fp
, "\t\t\tgeometry IndexedLineSet {\n");
641 fprintf (fp
, "\t\t\t\tcoord Coordinate {\n");
642 fprintf (fp
, "\t\t\t\t\tpoint [\n");
643 fprintf (fp
, "\t\t\t\t\t0.0 0.0 0.0,\n");
644 fprintf (fp
, "\t\t\t\t\t%f 0.0 0.0,\n", 255.0);
645 fprintf (fp
, "\t\t\t\t\t0.0 %f 0.0,\n", 255.0);
646 fprintf (fp
, "\t\t\t\t\t0.0 0.0 %f]\n", 255.0);
647 fprintf (fp
, "\t\t\t\t}\n");
648 fprintf (fp
, "\t\t\t\tcoordIndex [\n");
649 fprintf (fp
, "\t\t\t\t\t0, 1, -1\n");
650 fprintf (fp
, "\t\t\t\t\t0, 2, -1\n");
651 fprintf (fp
, "\t\t\t\t\t0, 3, -1]\n");
652 fprintf (fp
, "\t\t\t}\n");
653 fprintf (fp
, "\t\t}\n");
656 fprintf (fp
, "\t\tShape {\n");
657 fprintf (fp
, "\t\t\tappearance Appearance {\n");
658 fprintf (fp
, "\t\t\t\tmaterial Material {\n");
659 fprintf (fp
, "\t\t\t\t\tdiffuseColor 0 0.8 0\n");
660 fprintf (fp
, "\t\t\t\t\temissiveColor 1 1 1\n");
661 fprintf (fp
, "\t\t\t\t\tshininess 0.8\n");
662 fprintf (fp
, "\t\t\t\t}\n");
663 fprintf (fp
, "\t\t\t}\n");
664 fprintf (fp
, "\t\t\tgeometry PointSet {\n");
666 // fill in the points here
667 fprintf (fp
, "\t\t\t\tcoord Coordinate {\n");
668 fprintf (fp
, "\t\t\t\t\tpoint [\n");
670 // We need to transverse all gamut hull.
671 for (i
=0; i
< SECTORS
; i
++)
672 for (j
=0; j
< SECTORS
; j
++) {
676 pt
= &gbd
->Gamut
[i
][j
];
677 ToCartesian(&v
, &pt
->p
);
679 fprintf (fp
, "\t\t\t\t\t%g %g %g", v
.n
[0]+50, v
.n
[1], v
.n
[2]);
681 if ((j
== SECTORS
- 1) && (i
== SECTORS
- 1))
688 fprintf (fp
, "\t\t\t\t}\n");
692 // fill in the face colors
693 fprintf (fp
, "\t\t\t\tcolor Color {\n");
694 fprintf (fp
, "\t\t\t\t\tcolor [\n");
696 for (i
=0; i
< SECTORS
; i
++)
697 for (j
=0; j
< SECTORS
; j
++) {
701 pt
= &gbd
->Gamut
[i
][j
];
704 ToCartesian(&v
, &pt
->p
);
707 if (pt
->Type
== GP_EMPTY
)
708 fprintf (fp
, "\t\t\t\t\t%g %g %g", 0.0, 0.0, 0.0);
710 if (pt
->Type
== GP_MODELED
)
711 fprintf (fp
, "\t\t\t\t\t%g %g %g", 1.0, .5, .5);
713 fprintf (fp
, "\t\t\t\t\t%g %g %g", 1.0, 1.0, 1.0);
717 if ((j
== SECTORS
- 1) && (i
== SECTORS
- 1))
722 fprintf (fp
, "\t\t\t}\n");
725 fprintf (fp
, "\t\t\t}\n");
726 fprintf (fp
, "\t\t}\n");
727 fprintf (fp
, "\t]\n");