How to optimize undo/redo for canvas drawing in react

Question

I'm implementing undo/redo functionality (with this hook) for html-canvas drawing on medical (.nii) images in react. These images are a series of images that represents slices stored in a Uint8ClampedArray. The array is typically about 500 (cols) x 500 (rows) x 250 (slices), in other words, a quite big array.

My current solution simply creates a new Uint8ClampedArray from the current array on the mouseup event, and adds it to the undo/redo array. However, this is slow and creates a noticeable hiccup on the mouseup event. I was thinking of implementing a more complex undo/redo which only saves the affected voxels as opposed to the whole array on mouse up, but before i get ahead of myself i was wondering if there's an easier way to optimize the current solution?

This is my current code:

// State that stores the array of voxels for the image series.
// This updates on every brush stroke
const canvasRef = useRef(undefined);
const initialArray = canvasRef?.current?.getContext("2d")?.getImageData(canvas.width, canvas.height);
const [currentArray, setCurrentArray] = useState<Uint8ClampedArray | undefined>(initialArray);

// undo & redo states
const {
  state,
  setState,
  resetState,
  index,
  lastIndex,
  goBack,
  goForward,
} = useUndoableState();

// Update currentArray on index change (undo/redo and draw)
useEffect(() => {
  setCurrentArray(state);
}, [index]);

// Activates on mouse movement combined with left-click on canvas
function handleDrawing(){
    // Logic for drawing onto the canvas
    // ...

    // Adds the stroke from the canvas onto the corresponding slice in the array-state
    const newArray = addCanvasStrokeToArrayState(imageData, slice);
    setCurrentArray(newArray);
}

function handleMouseUp() {
   // This causes a hiccup every time the current state of the array is saved to the undoable array
   setState(Uint8ClampedArray.from(currentArray));
}

This is the code for the undo/redo hook:

export default function useUndoableState(init?: TypedArray | undefined) {
  const historySize = 10; // How many states to store at max
  const [states, setStates] = useState([init]); // Used to store history of all states
  const [index, setIndex] = useState<number>(0); // Index of current state within `states`
  const state = useMemo(() => states[index], [states, index]); // Current state

  const setState = (value: TypedArray) => {
    // remove oldest state if history size is exceeded
    let startIndex = 0;
    if (states.length >= historySize) {
      startIndex = 1;
    }

    const copy = states.slice(startIndex, index + 1); // This removes all future (redo) states after current index
    copy.push(value);
    setStates(copy);
    setIndex(copy.length - 1);
  };
  // Clear all state history
  const resetState = (init: TypedArray) => {
    setIndex(0);
    setStates([init]);
  };
  // Allows you to go back (undo) N steps
  const goBack = (steps = 1) => {
    setIndex(Math.max(0, index - steps));
  };
  // Allows you to go forward (redo) N steps
  const goForward = (steps = 1) => {
    setIndex(Math.min(states.length - 1, index + steps));
  };
  return {
    state,
    setState,
    resetState,
    index,
    lastIndex: states.length - 1,
    goBack,
    goForward,
  };
}

Answer 1

Here are three approaches to undo, along with their performance.

First, this fiddle contains a baseline by calling a draw function 10,000 times, providing average draw time of 0.0018 ms on my computer.

This fiddle both calls the draw function and stores a record of the call in a history array, giving an average time to both draw and store the function call as 0.002 ms on my computer, which is very close to the baseline time.

history.push({function: drawFunction, parameters: [i]});
drawFunction(i);

The history can then be replayed to a certain point. On my computer, replaying the 10,000 history items took 400 ms, but this would vary depending upon how many operations had been performed.

for (let i = 0; i < history.length - 1; i++) {
  history[i].function(...history[i].parameters);
}

This fiddle stores ImageData objects before every call to the draw function, with the average time to both store an ImageData and call the draw function of 7 ms, about 3,800 times slower than just calling the draw function.

history.push(context.getImageData(0, 0, 500, 500));
if (history.length > historyLimit) {
  history.splice(0, 1);
}

Drawing the stored image data back to the canvas only takes above takes about 0.002 ms, which is faster than rerunning everything.

Finally, this fiddle demonstrates using createPattern before every call to the draw function to store the current state of the canvas as a pattern, giving an average time to both store a pattern and draw of 0.3 ms on my computer, 167 slower than the baseline but 23 times faster than using getImageData.

history.push(context.createPattern(canvas, 'no-repeat'));

This can then be drawn back to the canvas like this, which was so fast on my computer that it could not be measured:

context.fillStyle = history[history.length - 1];
context.fillRect(0, 0, 500, 500);

Although createPattern is quite fast, it does have a memory overhead. The example does 20 runs, calling it 1,000 times each run, and the later runs can take more twice as long as the earlier runs.

An optimum approach could be to combine the pattern and function storage methods, occasionally storing a pattern to allow the list of function calls to be truncated.