Построение дуги в дискретных шагах

Question

Добрый день,

Фон
Мой вопрос касается построения произвольной дуги в пространстве с использованием дискретных шагов. Однако он уникален тем, что я не рисую на холсте в обычном смысле. Прошивка, которую я разрабатываю, предназначена для интерпретатора gcode для станка с ЧПУ, который преобразует команды в движения шагового двигателя. Теперь, я уже нашел подобный вопрос на этом самом сайте, но предложенная методология (алгоритм Брезенхэма) кажется несовместимой для перемещения объекта в пространстве, поскольку она основывается только на расчете одного октанта круга, который затем отражается об остальных осях симметрии. Кроме того, предписанный метод вычисления дуги между двумя произвольными углами основан на тригонометрии (я использую микроконтроллер и хотел бы по возможности избежать дорогостоящих функций триггера) и просто не предпринимал шагов, выходящих за пределы диапазона. Наконец, алгоритм предназначен только для работы в одном направлении вращения (например, против часовой стрелки).

Вопрос
Итак, к актуальному вопросу: кто-нибудь знает алгоритм общего назначения, который можно использовать для «рисования» произвольной дуги дискретными шагами, при этом все же учитывая угловое направление (CW / CCW)? Окончательная реализация будет сделана на C, но язык для цели вопроса не имеет значения.

Заранее спасибо.

Ссылки
Сообщение С.О. о построении простого круга по алгоритму Брезенхэма:
«Рисование» дуги дискретными x-y шагами

Вики-страница, описывающая алгоритм Брезенхема для круга
http://en.wikipedia.org/wiki/Midpoint_circle_algorithm

инструкции Gcode, которые должны быть реализованы (см. G2 и G3)
http://linuxcnc.org/docs/html/gcode.html

Answer 1

Вы можете точно и быстро решить эту проблему для произвольной рациональной кривой, преобразовав ее в рациональную кривую Безье, а затем применив алгоритм де Кастельжау. Это легко сделать для коников, таких как круги и гиперболы:

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

Если у вас есть рациональная кривая Безье, для повторной выборки кривой в дискретные шаги вы должны использовать алгоритм де Кастельжау. Этот алгоритм использует динамическое программирование и является очень быстрым и численно устойчивым. Если вы не слышали об этом раньше, я действительно рекомендовал бы узнать об этом, так как это довольно умный маленький алгоритм:

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

Есть несколько способов, которыми вы можете использовать алгоритм де Кастельжау, чтобы получить дискретную выборку вашей кривой. Во-первых, вы можете просто наивно применять его для оценки кривой вдоль ее пространства параметров с равномерными приращениями. Если приращения должны быть равномерно распределены, вы должны изменить координаты интерполяции на единицы длины дуги:

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

Уточнение этого метода состоит в том, чтобы вместо этого преобразовать в параметризацию длины хорды, которая со временем приближается к параметризации длины дуги:

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

Наконец, если вам нужно много точек на кривой, вы можете просто применить алгоритм де Кастельжау в качестве процедуры резки угла, чтобы уточнить начальный вектор контрольной точки в предельный многоугольник, который произвольно приближает желаемую кривую до некоторого указанного пользователем допуск:

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

Эти записи были взяты у профессора К.К. Заметки к курсу Шене, которые являются отличным ресурсом для изучения сплайнов и поверхностей подразделений:

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

Answer 2

это глупая идея, но она может сработать
вычислить круги каждого возможного радиуса на компьютере и сохранить эту информацию в памяти микроконтроллера.
скажем, у вас есть круги от 1 до 1000 пикселей в радиусе. это 1000 * (1000 + 1) / 2 * 2 * пи = 3 миллиона очков на всех кругах
для каждой точки фактически требуется только смещение от предыдущей точки, есть 8 случаев, они могут быть закодированы в 3 бита
в зависимости от того, сколько бит у вашего микроконтроллера, скажем, 8/16 бит, есть 2 пикселя / байт или 5 пикселей / слово
вам понадобится 1,5 МБ памяти на 8-битном микро, 1,2 МБ на 16-битном микро.
Вы можете хранить круги с шагом радиуса k пикселей и использовать только 1,5 МБ / к памяти.
другая оптимизация состояла бы в том, чтобы смоделировать круг как многоугольник со многими сторонами, вы не держите смещение относительно предыдущей точки, а только точку в двух шагах или более, и каким-то образом интерполируете пиксели между ними.
если вы держите смещение для пикселей в двух шагах, у вас будет 16 случаев, закодированных в 4 бита => 3/2 миллиона точек => 750 КБайт
если вы удерживаете пиксели каждые s шагов, у вас есть s * 8 возможностей, которые могут быть закодированы в 3 + log2 (s) битах.
LE:
пикселей каждые 32 шага / 8 мил = = 10-дюймовый радиус круга 10 *4000* 2 * пи / 32 шага * 1 байт = 7,85 КБ, пиксели каждые 128 шагов / 32 мили => 10-дюймовый радиусный круг 10 *4000* 2 * пи / 128 * 10 бит = 19634 Кбит = 2,4 КБ
LLE: у вас на самом деле нет s * 8 возможностей, их меньше, потому что увеличенный круг - это прямая линия
все зависит от того, насколько хорошо вы можете упаковать данные или использовать внешнюю память
другая оптимизация: хранить только квадранты или октанты и вычислять остальное от симметрии LLLE: каждый