Canvas renderings have previously relied on a cellMatrix of size (numValues, numCells), which is both memory inefficient and led to very slow responsiveness due to the reliance on looping through the matrix even in the gpu.js kernel
We replace cellMatrix with a cell-value mapping { mappings, lengths }. Here is the format of the data structure:
mappings: An array of arrays where the i th array contains all cells that map to value i. The array is then padded with zeroes such that each array is the same length
lengths: An array where the i th element denotes how many cells value i maps to
Now, we have a very simple and fast algorithm to color cell label interiors for a given pixel:
value = labelArray[y][x]
numCells = numCellsArray[value]
for (let i = 0; i < numCells; i++) {
cell = cellMapping[numCells[i]]
color = colorMap[cell]
appendColorToOverlap(color)
}
Anecdotally, on a Keren dataset this led to changing label opacity taking almost 3 seconds to less than 0.3 seconds (more than an order of magnitude speedup)
The algorithm for anything involving outlines is a bit more complicated, and looks quite ugly, but it should still be significantly faster even with the nested for loops, due to the fact that overlaps should basically always be very sparse.
Memory-wise, this is also more efficient, even with the padding (which is required for these algorithms to work with gpu.js, since jagged arrays result in incorrect array lookups since the GPU is probably just looking forward by a set amount of memory to a pointer or something)--in the worst, case, even with a certain pixel where every cell in the entire frame overlaps at that point, the mappings array is actually the exact same size as cellMatrix :D
Areas of improvement
It is likely that the ugly outline algorithms could be cleaned up a bit or made more efficient
cellSelectionCanvas.js may need some work; it still loops through the total number of selected cells, which can be quite a bit (as much as the number of cells in a canvas), and the max loop iteration is still 5000, so any selection with more than 5000 cells will have invisible selections
… for cell types
What
mappings: An array of arrays where the i th array contains all cells that map to value i. The array is then padded with zeroes such that each array is the same lengthlengths: An array where the i th element denotes how many cells value i maps tomappingsarray is actually the exact same size as cellMatrix :DAreas of improvement