[code review][performance] Mon interpolateur 3D est trop lent

Version imprimable

Bonjour,
dans le cadre d'une librairie servant à piloter des LED par une arduino, j'ai réalisé une nouvelle fonctionnalité qui a comme objectif de corriger les couleurs demandées aux LED pour qu'elles émettent les bonnes couleurs.
Par exemple, quand je demande du blanc (255,255,255) je dois transformer la couleur demandée pour envoyer 255,182,81 aux leds à la place.

La fonctionnalité à l'air de fonctionner mais elle est beaucoup trop lente (d'un facteur 20) pour être utilisable. En effet, la lenteur du calcul va provoquer des scintillements chez les LEDs.
Comme je n'ai plus programmé en C depuis 10 ans, je sollicite votre aide pour savoir si mon objectif en terme de vitesse est atteignable sur une arduino ou sur un PC courant.

Le code fait une centaine de ligne est consultable sur github.

Code:

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
 
struct LUTCoord {
	union {
		struct {
			uint8_t redIndex;
			uint8_t greenIndex;
			uint8_t blueIndex;
		};
		uint8_t raw[3];
	};
 
	inline LUTCoord() __attribute__((always_inline))
    {
    }
 
    inline LUTCoord( uint8_t ir, uint8_t ig, uint8_t ib)  __attribute__((always_inline))
        : redIndex(ir), greenIndex(ig), blueIndex(ib)
    {
    }
};
 
/// 8 vertices of a cube
struct LUTSubcube {
	CRGB n000;
	CRGB n001;
	CRGB n010;
	CRGB n011;
	CRGB n100;
	CRGB n101;
	CRGB n110;
	CRGB n111;
};
 
/// This 3D LUT can be used provided that the space between entries is the same for all dimensions.
class Array3DLUT {
public:
	CRGB *entries;
	uint8_t size;
	float step;
	uint8_t maxSubcubeIndex;
 
	Array3DLUT(CRGB *entries, uint8_t size);
	virtual ~Array3DLUT();
 
	/// Retrieve an entry in the table.
	/// @param indexes - 3D index of entry
	/// @returns Entry value
	CRGB lookup(LUTCoord indexes);
 
	/// Returns the values of the 8 vertices of the target sub-cube.
	/// The given coordinates must be those of the lowest point.
	/// @param subcubeOriginCoord - lowest point coordinates of the desired subcube
	/// @returns Each (8) subcube values
	struct LUTSubcube lookup_subcube(LUTCoord subcubeOriginCoord);
 
	/// Similar to lookup but instead of a coordinate in the LUT,
	/// we pass a point and the result will be interpolated.
	/// @param input - RGB coordinates of a point in the LUT
	/// @returns Interpolated value in the LUT
	struct CRGB lookup3DTetrahedral(CRGB &input);
};
 
Array3DLUT::Array3DLUT(CRGB *entries, uint8_t size) {
	this->entries = entries;
	this->size = size;
	this->step = 255. / (size - 1);
	this->maxSubcubeIndex = size - 2;
}
 
Array3DLUT::~Array3DLUT() {
	// TODO Auto-generated destructor stub
}
 
CRGB Array3DLUT::lookup(LUTCoord indexes) {
	uint8_t offset =
			  (indexes.redIndex * this->size * this->size)
			+ (indexes.greenIndex * this->size)
			+ indexes.blueIndex;
	return this->entries[offset];
}
 
 
struct LUTSubcube Array3DLUT::lookup_subcube(LUTCoord subcubeOriginCoord) {
	struct LUTSubcube result;
 
	result.n000 = this->lookup(subcubeOriginCoord);
	result.n001 = this->lookup(LUTCoord(subcubeOriginCoord.redIndex, subcubeOriginCoord.greenIndex, subcubeOriginCoord.blueIndex+1));
	result.n010 = this->lookup(LUTCoord(subcubeOriginCoord.redIndex, subcubeOriginCoord.greenIndex+1, subcubeOriginCoord.blueIndex));
	result.n011 = this->lookup(LUTCoord(subcubeOriginCoord.redIndex, subcubeOriginCoord.greenIndex+1, subcubeOriginCoord.blueIndex+1));
	result.n100 = this->lookup(LUTCoord(subcubeOriginCoord.redIndex+1, subcubeOriginCoord.greenIndex, subcubeOriginCoord.blueIndex));
	result.n101 = this->lookup(LUTCoord(subcubeOriginCoord.redIndex+1, subcubeOriginCoord.greenIndex, subcubeOriginCoord.blueIndex+1));
	result.n110 = this->lookup(LUTCoord(subcubeOriginCoord.redIndex+1, subcubeOriginCoord.greenIndex+1, subcubeOriginCoord.blueIndex));
	result.n111 = this->lookup(LUTCoord(subcubeOriginCoord.redIndex+1, subcubeOriginCoord.greenIndex+1, subcubeOriginCoord.blueIndex+1));
 
	return result;
}
 
// Ref implem: https://github.com/ampas/CLF/blob/master/python/aces/clf/Array.py
struct CRGB Array3DLUT::lookup3DTetrahedral(CRGB &input) {
	LUTCoord subcubeOrigin; // Store the subcube's origin coordinates
	float dimensionalDistances[3]; // Distance for each dimensions
 
	for (int i = 0; i < 3; i++) { // for each rgb channel
		dimensionalDistances[i] = input.raw[i] / this->step; // Not yet valid. We should remove int part
		subcubeOrigin.raw[i] = uint8_t(dimensionalDistances[i]); // we put a guessed coordinate
		if (subcubeOrigin.raw[i] > maxSubcubeIndex) {
			// But, if we are on an upper border then we must take the
			// inner border or the subcube will not exist.
			subcubeOrigin.raw[i] = maxSubcubeIndex;
		}
 
		dimensionalDistances[i] -= subcubeOrigin.raw[i]; // Remove the int part
	}
 
	// Rebind for consistency with Truelight paper
	#define fx dimensionalDistances[0]
	#define fy dimensionalDistances[1]
	#define fz dimensionalDistances[2]
 
	struct CRGB result;
	struct LUTSubcube cube = this->lookup_subcube(subcubeOrigin);
	if (fx > fy) {
		if (fy > fz) {
			for (int i=0; i < 3; i++) {
				result.raw[i] = (
						(1-fx)  * cube.n000.raw[i] +
						(fx-fy) * cube.n100.raw[i] +
						(fy-fz) * cube.n110.raw[i] +
						(fz)    * cube.n111.raw[i] );
			}
		} else {
			if (fx > fz) {
				for (int i=0; i < 3; i++) {
					result.raw[i] = (
							(1-fx)  * cube.n000.raw[i] +
							(fx-fz) * cube.n100.raw[i] +
							(fz-fy) * cube.n101.raw[i] +
							(fy)    * cube.n111.raw[i] );
				}
			} else {
				for (int i=0; i < 3; i++) {
					result.raw[i] = (
							(1-fz)  * cube.n000.raw[i] +
							(fz-fx) * cube.n001.raw[i] +
							(fx-fy) * cube.n101.raw[i] +
							(fy)    * cube.n111.raw[i] );
				}
			}
		}
	} else {
		if (fz > fy) {
			for (int i=0; i < 3; i++) {
				result.raw[i] = (
						(1-fz)  * cube.n000.raw[i] +
						(fz-fy) * cube.n001.raw[i] +
						(fy-fx) * cube.n011.raw[i] +
						(fx)    * cube.n111.raw[i] );
			}
		} else {
			if (fz > fx) {
				for (int i=0; i < 3; i++) {
					result.raw[i] = (
							(1-fy)  * cube.n000.raw[i] +
							(fy-fz) * cube.n010.raw[i] +
							(fz-fx) * cube.n011.raw[i] +
							(fx)    * cube.n111.raw[i] );
				}
			} else {
				for (int i=0; i < 3; i++) {
					result.raw[i] = (
							(1-fy)  * cube.n000.raw[i] +
							(fy-fx) * cube.n010.raw[i] +
							(fx-fz) * cube.n011.raw[i] +
							(fz)    * cube.n111.raw[i] );
				}
			}
		}
	}
 
	return result;
}

(si c'est codé comme un cochon, n'hésitez à le faire savoir ^^ )

Edit 1: Ajout des sources dans le post

14/12/2017, 12h37
Matt_Houston
1. Édite ton message pour coller ton code entre balises [code], Github c'est bien mais si le lien meurt le sujet n'aura plus aucune pertinence ;
2. c'est du C++.
Combien y'a-t-il de LEDs ? Quelle taille font les LUTs ? Nous n'avons pas la boucle principale. De quel compilateur te sers-tu, et quelles options lui passes-tu ?

Là comme ça, outre les méthodes de Array3DLUT que tu pourrais inline, il n'y a que le contenu de lookup_subcube qui me fait tiquer : tu appelles plusieurs fois lookup avec des indices décalés d'une unité et tu recalcules plusieurs fois la même chose. Pas mal de multiplications et quelques additions peuvent sans doute être évitées. Mais peut-être le compilateur le fait-il déjà : il faudra jeter un œil à la sortie assembleur pour en être sûr.
14/12/2017, 13h01
Delias

Bonjour

Utilises-tu un Arduino à base de AVR 8bits (et pas l'un des derniers avec un 32bits)?
Dans ce cas il faut exclure tout usage des nombres à virgule flottante et surtout leur division et multiplication. Car cela prend un nombre astronomique de cycles possesseur. Sur le dernier micro de se genre où j'avais mesuré cela la routine en virgule fixe, était 20 à 30 fois plus rapide! (mais ce n'était pas de l'AVR!)

Il te faut modifier ton algorithme pour travailler uniquement avec des entiers, quitte à faire de la virgule fixe sur 16 ou 32bits (mais attention aux décalages lors des multiplications et divisions).

Delias

Merci beaucoup d'être intervenu.

Citation:

Envoyé par Matt_Houston

Combien y'a-t-il de LEDs ? Quelle taille font les LUTs ? Nous n'avons pas la boucle principale. De quel compilateur te sers-tu, et quelles options lui passes-tu ?

Il y aura entre 400 et 500 leds.
Je teste avec une arduino nano ATmega328P mais j'ai une teensy 3.2 qui peut-être utilisée à la place.
Je compile avec Sloeber (Eclipse) car je ne sais plus comment faire (surtout sous windows). Voici ce qu'il appelle

Code:

arduino/tools/avr-gcc/4.9.2-atmel3.5.4-arduino2/bin/avr-g++ -c -g -Os -Wall -Wextra -std=gnu++11 -fpermissive -fno-exceptions -ffunction-sections -fdata-sections -fno-threadsafe-statics -flto -mmcu=atmega328p -DF_CPU=16000000L -DARDUINO=10802 -DARDUINO_AVR_NANO -DARDUINO_ARCH_AVR

J'ai testé avec une LUT 5x5x5, je vous en propose une un peu plus bas au cas où.
D'après moi, comme la LUT est un tableau est qu'il n'y pas de recherche à réaliser, la taille de la LUT n'a pas d'impact autre que spatial.

J'ai réalisé des tests avec 300 leds (j'ai pas réussi plus, je crains le manque d'espace). Je traite ces 300 LEDs en 157ms. Voici le code pour tester (il contient une LUT 5x5x5):
Code:

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 struct TICKS { unsigned long epoch; unsigned long lutTick; unsigned long showTick; }; void printTicks(struct TICKS t) { char str[64]; sprintf(str, "lut: %lu", t.lutTick - t.epoch); Serial.println(str); sprintf(str, "shw: %lu", t.showTick - t.lutTick); Serial.println(str); } void init(CRGB *l, size_t count) { for (size_t i=0; i < count; i++) { l[i].r = random8(); l[i].g = random8(); l[i].b = random8(); } } // main function that setups and runs the code void setup() { Serial.begin(9600); CRGB data[5][5][5] = { { { CRGB(0,0,0), CRGB(6,3,59), CRGB(10,1,121), CRGB(17,0,187), CRGB(40,0,253) }, { CRGB(2,54,4), CRGB(8,54,53), CRGB(11,53,119), CRGB(19,51,183), CRGB(48,48,253) }, { CRGB(8,117,12), CRGB(12,117,52), CRGB(19,117,116), CRGB(19,117,180), CRGB(48,114,253) }, { CRGB(5,179,28), CRGB(4,179,57), CRGB(19,179,115), CRGB(25,179,178), CRGB(46,179,252) }, { CRGB(56,249,52), CRGB(55,249,70), CRGB(59,248,120), CRGB(62,249,179), CRGB(68,251,253) } }, { { CRGB(54,3,3), CRGB(54,5,57), CRGB(54,4,120), CRGB(55,0,183), CRGB(63,0,253) }, { CRGB(51,54,8), CRGB(51,52,47), CRGB(54,51,118), CRGB(55,48,183), CRGB(70,48,253) }, { CRGB(48,116,16), CRGB(49,115,51), CRGB(56,117,115), CRGB(55,115,178), CRGB(66,113,253) }, { CRGB(47,178,34), CRGB(45,177,57), CRGB(54,177,113), CRGB(56,177,176), CRGB(64,179,253) }, { CRGB(74,248,50), CRGB(70,249,68), CRGB(74,248,120), CRGB(74,250,178), CRGB(76,251,252) } }, { { CRGB(121,3,3), CRGB(121,3,54), CRGB(122,1,119), CRGB(120,6,183), CRGB(120,1,253) }, { CRGB(119,51,9), CRGB(118,52,51), CRGB(119,50,117), CRGB(119,47,181), CRGB(122,48,253) }, { CRGB(118,116,17), CRGB(119,116,49), CRGB(118,117,112), CRGB(119,115,181), CRGB(118,112,252) }, { CRGB(116,180,34), CRGB(116,178,55), CRGB(118,179,112), CRGB(117,179,178), CRGB(119,179,253) }, { CRGB(123,247,51), CRGB(121,248,69), CRGB(121,250,118), CRGB(123,251,179), CRGB(121,251,252) } }, { { CRGB(180,10,6), CRGB(181,10,52), CRGB(182,0,118), CRGB(183,0,182), CRGB(183,2,253) }, { CRGB(179,51,12), CRGB(178,51,50), CRGB(179,48,115), CRGB(180,44,181), CRGB(182,46,253) }, { CRGB(181,116,20), CRGB(179,115,50), CRGB(180,117,114), CRGB(178,116,179), CRGB(181,112,253) }, { CRGB(183,184,30), CRGB(183,182,53), CRGB(180,179,108), CRGB(182,180,176), CRGB(180,178,253) }, { CRGB(178,249,47), CRGB(178,249,59), CRGB(180,251,110), CRGB(182,251,177), CRGB(182,252,253) } }, { { CRGB(251,32,14), CRGB(254,32,55), CRGB(254,33,116), CRGB(255,36,179), CRGB(255,39,250) }, { CRGB(250,62,17), CRGB(253,60,54), CRGB(254,60,114), CRGB(255,59,179), CRGB(254,59,251) }, { CRGB(251,117,23), CRGB(251,115,57), CRGB(251,116,115), CRGB(253,115,178), CRGB(254,114,252) }, { CRGB(249,181,32), CRGB(248,177,51), CRGB(250,178,111), CRGB(252,179,178), CRGB(253,179,253) }, { CRGB(250,254,46), CRGB(251,253,55), CRGB(251,250,98), CRGB(253,252,172), CRGB(255,254,253) } } }; #define TEST_SIZE 300 CRGB leds[TEST_SIZE]; init(leds, TEST_SIZE); Array3DLUT lut = Array3DLUT(&data[0][0][0], 5); FastLED.addLeds<APA102, 11, 13, RGB>(leds, TEST_SIZE); for (;;) { struct TICKS t; t.epoch = millis(); for (size_t i=0; i < TEST_SIZE; i++) { leds[i] = lut.lookup3DTetrahedral(leds[i]); } t.lutTick = millis(); FastLED.show(); t.showTick = millis(); printTicks(t); init(leds, TEST_SIZE); } Serial.flush(); Serial.end(); } // end of setup
Citation:

Là comme ça, outre les méthodes de Array3DLUT que tu pourrais inline, il n'y a que le contenu de lookup_subcube qui me fait tiquer : tu appelles plusieurs fois lookup avec des indices décalés d'une unité et tu recalcules plusieurs fois la même chose. Pas mal de multiplications et quelques additions peuvent sans doute être évitées. Mais peut-être le compilateur le fait-il déjà : il faudra jeter un œil à la sortie assembleur pour en être sûr.

Je vois. Ma LUT est un tableau à 3 dimensions mais pour des questions de mémoire, je passe ça à Array3DLUT via un pointeur (j'ai pas réussi à le faire avec une ref de tableau 3D). Du coup je dois calculer des coordonnées 1D pour un tableau qui est en réalité en 3D ; c'est ce que fait lookup et ses multiplications.

Tu penses qu'avec des templates je pourrais manipuler un tableau 3D plutôt que son pointeur et que cela éviterai les multiplications?
Sur les 8 points retournés par lookup_subcube, je n'en utilise que 4. Je devrais exploiter ça.

Citation:

Envoyé par Delias

Utilises-tu un Arduino à base de AVR 8bits (et pas l'un des derniers avec un 32bits)?
Dans ce cas il faut exclure tout usage des nombres à virgule flottante et surtout leur division et multiplication. Car cela prend un nombre astronomique de cycles possesseur. Sur le dernier micro de se genre où j'avais mesuré cela la routine en virgule fixe, était 20 à 30 fois plus rapide! (mais ce n'était pas de l'AVR!)

Whao! En effet, j'avais lu quelque chose comme ça à propos des AVR 8 bits qu'il fallait travailler avec des entiers 8bits.
Je ne pensais pas que c'était aussi flagrant. Je ne connaissais pas le concept de virgule fixe, je vais potasser pour voir si je peux améliorer cet axe.

Merci encore pour vos pistes, ça m'a l'air super prometteur et intéressant!

14/12/2017, 14h25
Delias

Citation:

Envoyé par lildadou

Whao! En effet, j'avais lu quelque chose comme ça à propos des AVR 8 bits qu'il fallait travailler avec des entiers 8bits.
Je ne pensais pas que c'était aussi flagrant. Je ne connaissais pas le concept de virgule fixe, je vais potasser pour voir si je peux améliorer cet axe.

Le cœur AVR travaille encore pas trop mal avec les entiers 16 et 32bits (le système de carry est relativement bien pensé pour cela). Par contre le travail sur les nombres à virgule flottante n'est pas implémenté matériellement. Au final c'est donc une implémentation par le code et c'est cela qui coute autant de temps.

La virgule fixe, je ne l'ai travaillée que sur deux projets consécutif pendant les études et c'était sur un DSP 32bits à virgule fixe de TI qui avait toutes les bibliothèques pour cela. Donc côté implémentation je suis largué.

Delias

J'interrogeais à propos de la taille surtout pour d'éventuels problèmes avec le cache, mais je ne sais pas comment ça se comporte en embarqué.

Citation:

Envoyé par lildadou

Je vois. Ma LUT est un tableau à 3 dimensions mais pour des questions de mémoire, je passe ça à Array3DLUT via un pointeur (j'ai pas réussi à le faire avec une ref de tableau 3D). Du coup je dois calculer des coordonnées 1D pour un tableau qui est en réalité en 3D ; c'est ce que fait lookup et ses multiplications.

Tu penses qu'avec des templates je pourrais manipuler un tableau 3D plutôt que son pointeur et que cela éviterai les multiplications?
Sur les 8 points retournés par lookup_subcube, je n'en utilise que 4. Je devrais exploiter ça.

Je pensais plutôt à quelque chose du style de :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 LUTSubcube Array3DLUT::lookup_subcube(LUTCoord subcubeOriginCoord) { static const auto size_sq = size * size; const uint8_t index_base = subcubeOriginCoord. redIndex * size_sq, subcubeOriginCoord.greenIndex * size, subcubeOriginCoord. blueIndex; return LUTSubcube{ entries[index_base ], // n000 entries[index_base + 1], // n001 entries[index_base + size ], // n010 entries[index_base + size + 1], // n011 entries[index_base + size_sq ], // n100 entries[index_base + size_sq + 1], // n101 entries[index_base + size_sq + size ], // n110 entries[index_base + size_sq + size + 1] // n111 }; }
Bien évidemment si tu n'as besoin que de la moitié des infos, ne va chercher que la moitié des infos.

Explore en premier lieu les pistes données par Delias : rien ne sert d'économiser 5 cycles à un endroit alors qu'une seule opération sur des flottants ailleurs en consomme toujours 300.. ;) Pour évaluer ça, tu peux vite écrire un petit programme de test qui compare le même traitement arithmétique sur le même jeu de données, mais d'un côté en entiers et de l'autre en virgule flottante.

14/12/2017, 14h40
Kannagi

Citation:

Envoyé par lildadou

Whao! En effet, j'avais lu quelque chose comme ça à propos des AVR 8 bits qu'il fallait travailler avec des entiers 8bits.
Je ne pensais pas que c'était aussi flagrant. Je ne connaissais pas le concept de virgule fixe, je vais potasser pour voir si je peux améliorer cet axe.

A une époque pas si lointaine les virgules fixe c’était assez courant , après tout dépend de combien de bits tu veux en virgule , dans ton cas je dirait 8 bits pour les entiers et 8bits pour les virgules ;)
Tu peux très bien faire des macro pour convertir virgule fixe en entier et inversement :p

Par contre la multiplication ou la division , sur AVR c'est effectivement lent donc je te conseille personnellement si possible de passer par une table precalculer si possible !

Citation:

La virgule fixe, je ne l'ai travaillée que sur deux projets consécutif pendant les études et c'était sur un DSP 32bits à virgule fixe de TI qui avait toutes les bibliothèques pour cela. Donc côté implémentation je suis largué.

Pour ma part je l'ai bosser sur les vielles machines et plus récemment sur .... PS2 ! :mrgreen:
14/12/2017, 15h01
Delias

Sur les AVR, il n'y a pas de cache à proprement parlé:
Eventuellement 12 des 32 registres peuvent être utilisé comme cache par le compilateur GCC AVR.
La SRAM met 2 cycles pour être copiée de ou vers les registres. Le compilateur est "optimisé" pour le travail jusqu'à 32 bits en utilisant les registres par groupes de 4.
Il y a quelques application notes de Atmel là dessus, certaines avec de bons conseils!

Citation:

Envoyé par Kannagi

Par contre la multiplication ou la division , sur AVR c'est effectivement lent donc je te conseille personnellement si possible de passer par une table precalculer si possible !

Euhh la multiplication de 2 nombres entiers 8bits avec résultat en 16 bits c'est 2 cycles (après je ne sais pas quels sont les opérations de vérification ajoutées par le compilateur), C'est un ajout des ATMega par rapport aux ATTiny.

Et avant de poser la question: pas d'optimisation côté pipeline non plus.

Delias

Encore une fois, un grand merci pour vos conseils.

J'ai réalisé les modifications suivantes:
- remplacer la méthode de calcul d'index 3D vers 1D par l'utilisation des templates
- suppression de l'utilisation des nombres à virgules. Au lieu d'utiliser la partie flottante, j'utilise directement le reste. Mais ça entraine une division par 255 du coup.
- remplacer la division par 255 par un décalage de 8 bits vers la droite. Je crois que j'introduis une toute petite erreur (1bit) mais ça me fait gagner 40% de perf

Le résultat est extrêmement concluant car vos conseils m'ont permis de diviser le temps de calcul par 10!

Code:

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
 
#ifndef ARRAY3DLUT_H_
#define ARRAY3DLUT_H_
 
#include "FastLED.h"
#include "pixeltypes.h"
 
FASTLED_NAMESPACE_BEGIN
 
 
/// 3D array index
struct LUTCoord {
	union {
		struct {
			uint8_t redIndex;
			uint8_t greenIndex;
			uint8_t blueIndex;
		};
		uint8_t raw[3];
	};
 
	inline LUTCoord() __attribute__((always_inline))
    {
    }
 
    inline LUTCoord( uint8_t ir, uint8_t ig, uint8_t ib)  __attribute__((always_inline))
        : redIndex(ir), greenIndex(ig), blueIndex(ib)
    {
    }
};
 
 
/// This 3D LUT can be used provided that the space between entries is the same for all dimensions.
template<uint8_t SIZE>
class Array3DLUT {
public:
	CRGB (*cube)[SIZE][SIZE];
 
	Array3DLUT(CRGB entries[SIZE][SIZE][SIZE]);
	virtual ~Array3DLUT();
 
	/// Similar to lookup but instead of a coordinate in the LUT,
	/// we pass a point and the result will be interpolated.
	/// @param input - RGB coordinates of a point in the LUT
	/// @returns Interpolated value in the LUT
	struct CRGB lookup3DTetrahedral(CRGB &input);
};
 
 
 
 
template<uint8_t SIZE>
Array3DLUT<SIZE>::Array3DLUT(CRGB (*entries)[SIZE][SIZE]) {
	this->cube = entries;
}
 
template<uint8_t SIZE>
Array3DLUT<SIZE>::~Array3DLUT() {
	// TODO Auto-generated destructor stub
}
 
// Ref implem: https://github.com/ampas/CLF/blob/master/python/aces/clf/Array.py
template<uint8_t SIZE>
struct CRGB Array3DLUT<SIZE>::lookup3DTetrahedral(CRGB &input) {
	LUTCoord subcubeDarkestVertice; // Store the subcube's origin coordinates
	uint8_t darkSpotDistances[3]; // Distance input <-> subcube's darkest vertice
 
	#define STEP (255/(SIZE-1))
	#define MAX_INDEX SIZE-2
	for (int i = 0; i < 3; i++) { // for each rgb channel
		subcubeDarkestVertice.raw[i] = input.raw[i] / STEP;
		darkSpotDistances[i] = input.raw[i] % STEP;
 
		if (subcubeDarkestVertice.raw[i] > MAX_INDEX) {
			// But, if we are on an upper border then we must take the
			// inner border or the subcube will not exist.
			subcubeDarkestVertice.raw[i] = MAX_INDEX;
			darkSpotDistances[i] = 255;
		}
	}
 
	// Rebind for consistency with Truelight paper
	#define fx darkSpotDistances[0]
	#define fy darkSpotDistances[1]
	#define fz darkSpotDistances[2]
	#define N000 this->cube[subcubeDarkestVertice.redIndex  ][subcubeDarkestVertice.greenIndex  ][subcubeDarkestVertice.blueIndex  ]
	#define N001 this->cube[subcubeDarkestVertice.redIndex  ][subcubeDarkestVertice.greenIndex  ][subcubeDarkestVertice.blueIndex+1]
	#define N010 this->cube[subcubeDarkestVertice.redIndex  ][subcubeDarkestVertice.greenIndex+1][subcubeDarkestVertice.blueIndex  ]
	#define N011 this->cube[subcubeDarkestVertice.redIndex  ][subcubeDarkestVertice.greenIndex+1][subcubeDarkestVertice.blueIndex+1]
	#define N100 this->cube[subcubeDarkestVertice.redIndex+1][subcubeDarkestVertice.greenIndex  ][subcubeDarkestVertice.blueIndex  ]
	#define N101 this->cube[subcubeDarkestVertice.redIndex+1][subcubeDarkestVertice.greenIndex  ][subcubeDarkestVertice.blueIndex+1]
	#define N110 this->cube[subcubeDarkestVertice.redIndex+1][subcubeDarkestVertice.greenIndex+1][subcubeDarkestVertice.blueIndex  ]
	#define N111 this->cube[subcubeDarkestVertice.redIndex+1][subcubeDarkestVertice.greenIndex+1][subcubeDarkestVertice.blueIndex+1]
 
	struct CRGB result;
	if (fx > fy) {
		if (fy > fz) {
			for (int i=0; i < 3; i++) {
				result.raw[i] = (
						(uint16_t)(255-fx) * N000.raw[i] +
						(uint16_t)(fx-fy)  * N100.raw[i] +
						(uint16_t)(fy-fz)  * N110.raw[i] +
						(uint16_t)(fz)     * N111.raw[i] ) >> 8;
			}
		} else {
			if (fx > fz) {
				for (int i=0; i < 3; i++) {
					result.raw[i] = (
							(uint16_t)(255-fx) * N000.raw[i] +
							(uint16_t)(fx-fz)  * N100.raw[i] +
							(uint16_t)(fz-fy)  * N101.raw[i] +
							(uint16_t)(fy)     * N111.raw[i] ) >> 8;
				}
			} else {
				for (int i=0; i < 3; i++) {
					result.raw[i] = (
							(uint16_t)(255-fz) * N000.raw[i] +
							(uint16_t)(fz-fx)  * N001.raw[i] +
							(uint16_t)(fx-fy)  * N101.raw[i] +
							(uint16_t)(fy)     * N111.raw[i] ) >> 8;
				}
			}
		}
	} else {
		if (fz > fy) {
			for (int i=0; i < 3; i++) {
				result.raw[i] = (
						(uint16_t)(255-fz) * N000.raw[i] +
						(uint16_t)(fz-fy)  * N001.raw[i] +
						(uint16_t)(fy-fx)  * N011.raw[i] +
						(uint16_t)(fx)     * N111.raw[i] ) >> 8;
			}
		} else {
			if (fz > fx) {
				for (int i=0; i < 3; i++) {
					result.raw[i] = (
							(uint16_t)(255-fy) * N000.raw[i] +
							(uint16_t)(fy-fz)  * N010.raw[i] +
							(uint16_t)(fz-fx)  * N011.raw[i] +
							(uint16_t)(fx)     * N111.raw[i] ) >> 8;
				}
			} else {
				for (int i=0; i < 3; i++) {
					result.raw[i] = (
							(uint16_t)(255-fy) * N000.raw[i] +
							(uint16_t)(fy-fx)  * N010.raw[i] +
							(uint16_t)(fx-fz)  * N011.raw[i] +
							(uint16_t)(fz)     * N111.raw[i] ) >> 8;
				}
			}
		}
	}
 
	return result;
}
 
#endif /* ARRAY3DLUT_H_ */