Wie soll das gehen? Wenn Du Sowohl Rotation als auch Translation hast, wird das meiner Meinung nach nicht mehr funktionieren. Falls Du eines davon kennst, dann gehts.
Ich postuliere hier mal, ohne es geprüft zu haben. Die X/Y-Verschiebung ist halt recht einfach zu ermitteln, man braucht nur Matrix-Zeilen und-Spalten zu verschieben, zu deutsch, einfach dien index um einen offset verschieben. (Die Matrix ist eigentlich eine Art Bitmap, die den Rundumscan darstellt)
Das blöde bei der Drehung ist, dass man dazu die Matrix rotieren muss... Und zwar in kleinen schritten. Wenn du also eine 400x400 Grafik in 1,8-Grad schritten drehen willst, dauet das ewig.

Vor allem hat mein ATmega8 ja kaum soviel RAM, als dass da sowas reinpassen würde...

Schau Dir das Winkel-Histogramm mal genauer an, dass ist KEINE Korrelation mit irgendwas.
Womit du recht hast - Asche auf mein Haupt... Aber der Vorgang ist der Korrelation sehr ähnlich, allerdings möglicherweise Rechenzeitsparsamer