Yes, you must do Bresenham (or variation thereon) on the Arduino because it needs to happen for every step. It's a simple algorithm; the hard part is not the calculations but all the jumping through hoops to schedule the timing events accurately and reliably using interrupts. That hard part is unavoidable.