Trazando un arco en discretos pasos

Question

Buenas tardes,

Antecedentes
Mi pregunta está relacionada con el trazado de un arco arbitraria en el espacio mediante pasos discretos. Sin embargo, es único porque no estoy dibujando un lienzo en el sentido típico. El firmware que estoy diseñando es para un intérprete gcode para una fresadora CNC que traducirá los comandos en movimientos de motor paso a paso. Ahora, ya he encontrado una pregunta similar en este sitio, pero la metodología sugerida (Algoritmo de Bresenham) parece ser incompatible para mover un objeto en el espacio, ya que solo se basa en el cálculo de un octante de un círculo que luego se refleja sobre los ejes de simetría restantes. Además, el método prescrito para calcular un arco entre dos ángulos arbitrarios se basa en la trigonometría (estoy implementando en un microcontrolador y me gustaría evitar costosas funciones trigonométricas, si es posible) y simplemente no tomar los pasos que están fuera del rango. Finalmente, el algoritmo solo está diseñado para trabajar en una dirección de rotación (por ejemplo, en sentido antihorario).

Pregunta
Así, a la pregunta real: ¿alguien sabe de un algoritmo de propósito general que se puede utilizar para "dibujar" un arco arbitraria en pasos discretos, pero dando respecto a la dirección angular (CW/CCW)? La implementación final se realizará en C, pero el lenguaje para el propósito de la pregunta es irrelevante.

Gracias de antemano.

Referencias
SO publican en la elaboración de un círculo simple usando el algoritmo de Bresenham:
"Drawing" an arc in discrete x-y steps

página Wiki que describe el algoritmo de Bresenham para un círculo
http://en.wikipedia.org/wiki/Midpoint_circle_algorithm

instrucciones gcode a ser implementadas (ver. G2 y G3)
http://linuxcnc.org/docs/html/gcode.html

Answer 1

Puede resolver este problema de forma rápida y precisa de una curva racional arbitraria mediante la conversión a una curva de Bézier racional, a continuación, aplicar el algoritmo de de Casteljau. Esto se puede hacer fácilmente por las cónicas como círculos y hipérbolas:

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/NURBS/RB-conics.html

Una vez que tenga una curva de Bézier racional, volver a muestrear la curva en pasos discretos, se debe utilizar el algoritmo de de Casteljau. Este algoritmo usa programación dinámica, y es muy rápido y numéricamente robusto. Si usted no ha oído hablar de él antes, Verdaderamente recomiendo aprender sobre él, ya que es un poco algoritmo bastante inteligente:

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/Bezier/de-casteljau.html

Hay varias maneras que a continuación se pueden utilizar de algoritmo de Casteljau para conseguir una discreta muestreo de tu curva En primer lugar, puede simplemente aplicarlo ingenuamente para evaluar la curva a lo largo de su espacio de parámetros en incrementos uniformes. Si los incrementos deben ser espaciados uniformemente, usted tiene que cambiar su interpolación de coordenadas en unidades de longitud de arco:

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/curves/continuity.html#Arc-Length-Parameterization

Un refinamiento de esta técnica es la de convertir su lugar en una parametrización longitud de la cuerda, que se aproxima a la longitud del arco parametrización con el tiempo:

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/INT-APP/PARA-chord-length.html

por último, si usted necesita una gran cantidad de puntos de la curva, se puede simplemente aplicar el algoritmo de de Casteljau como un procedimiento de corte de la esquina para refinar el vector inicial punto de control en un límite de p olygon que arbitrariamente se aproxima a su curva deseada hasta algún usuario tolerancia especificada:

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/Bezier/bezier-sub.html

Estas notas fueron tomadas de Prof. C.K. notas del curso de Shene, que es un gran recurso para el aprendizaje de las estrías y superficies de subdivisión:

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/

Answer 2

esta es una idea tonta, pero podría funcionar
calcular círculos de todos los radios posibles en la computadora y mantener esta información en la memoria del micrococotón.
digamos que tiene círculos de 1 a 1000 píxeles de radio. eso es 1000 * (1000 + 1)/2 * 2 * pi = 3 millones de puntos en todos los círculos
para cada punto que realmente solo necesita el desplazamiento desde el punto anterior, hay 8 casos, estos pueden codificarse en 3 bits
dependiendo de cuántos bits tiene el microcontrolador, digamos 8/16 bits, tiene 2 píxeles/byte o 5 píxeles/palabra
necesitará 1,5 MB de memoria en un micro de 8 bits, 1,2 MB en un micro de 16 bits.
puede guardar círculos con incrementos de píxel k de radio, y usar solo memoria de 1.5MB/k.
Otra optimización sería modelar el círculo como un polígono con muchos lados, no mantener el desplazamiento al punto anterior, sino a un punto a dos pasos o más, e interpolar de algún modo los píxeles intermedios.
si mantiene la compensación de píxeles a dos pasos tiene 16 casos, codificados en 4 bits => 3/2million points => 750KBytes
si tiene píxeles cada pasos tiene s * 8 posibilidades que se pueden codificar en 3 + log2 (s) bits.
LE:
píxeles cada 32steps/8mils => 10 pulgadas círculo de radio 10 * 4000 * 2 * pi/32steps * 1 byte = 7.85KB, píxeles cada 128steps/32mils => 10 pulgadas círculo de radio 10 * 4000 * 2 * pi/128 * = 10bits 19634Kbits = 2,4 kb
LLE: que en realidad no tiene s * 8 posibilidades, hay menos que eso, porque el círculo zoom es una línea recta
todo se reduce a cómo bien puede empacar los datos, o usar la memoria externa
otra optimización: almacenar solo cuadrantes u octantes y calcular el resto de la simetría LLLE: cada