Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Алгоритм Брезенхе́ма
Форум разработчиков электроники ELECTRONIX.ru > Цифровая обработка сигналов - ЦОС (DSP) > Алгоритмы ЦОС (DSP)
Maverick
есть алгоритм
как с помощью него рисовать дуги например с углом 20 или 5 градусов, т.е. не кратно 45 градусам
Как это делается, если это возможно?
Maverick
Цитата(Maverick @ Jul 1 2013, 11:48) *
есть алгоритм
как с помощью него рисовать дуги например с углом 20 или 5 градусов, т.е. не кратно 45 градусам
Как это делается, если это возможно?

спасибо, разобрался...
Вопрос снят...
Сергей Борщ
Так расскажите. Может кому-то еще будет полезно.
Maverick
Цитата(Сергей Борщ @ Jul 1 2013, 20:10) *
Так расскажите. Может кому-то еще будет полезно.

Расскажу...
Этот алгоритм мне нужен для реализации G-code , т.е. реализации
G02 -круговая интерполяция по часовой стрелки,
G03 - круговая интерполяция против часовой стрелки.
Входными данными являются начальная точка, конечная точка и радиус.
Вопрос возник как рисовать дуги не кратные 45 градусам (по алгоритму).
Ответ:
1) из чистой геометрии определяю координаты центра - придется решать квадратное уравнение;
2) Для работы алгоритма необходимо сдвинуть центр окружности в (0, 0);
3) Начинаем алгоритм из первой точки, заканчиваем, когда дойдет до второй точки.
Это работает без модификации для любых 2-х точек, расположенных на опорной дуге.
Да, еще такой момент: если там маленький угол, т.е. очень большой радиус, то возможны некоторые проблемы с разрядностью, т.е. надо будет этот момент особо проконтролировать.
Над этим пока думаю...
khach
Если это интерпертатр G-cod, то очень желательно в алгориме поддерживать постоянную линейную скорость обрабатываюшего инструмента на дуге. А перед крутыми дугами с мелким радиусом еще и притормозить.
Maverick А чем интепретатор из Linux-CNC не подходит? Его же давно "выкусили" в отдельную библиотеку.
Tiro
Цитата(Maverick @ Jul 1 2013, 21:15) *
Да, еще такой момент: если там маленький угол, т.е. очень большой радиус, то возможны некоторые проблемы с разрядностью, т.е. надо будет этот момент особо проконтролировать.

Так преимущество Брезенхема в том, что достаточно вычислять целочисленные значения, поэтому все расчеты ведутся в целых числах. Разрядность расчета равна разрядности вывода, что там контролировать кроме переполнения? Или, теоретически, Вы собираетесь использовать в расчетах иррациональные числа?
Maverick
Цитата(khach @ Jul 1 2013, 21:44) *
Если это интерпертатр G-cod, то очень желательно в алгориме поддерживать постоянную линейную скорость обрабатываюшего инструмента на дуге. А перед крутыми дугами с мелким радиусом еще и притормозить.
Maverick А чем интепретатор из Linux-CNC не подходит? Его же давно "выкусили" в отдельную библиотеку.

Как мне показалось при первом просмотре, что там вообще оно ПК-ориентированное.
А хотелось бы положить на более медленный процессор, чем ПК или ARM9 (и выше).
Вы с этим линуксом работали? Если да, то на какой платформе? Раскажите впечатления.

Цитата(Tiro @ Jul 1 2013, 21:50) *
... контролировать кроме переполнения?

именно их, а лучще сделать так чтобы их вообще не было sm.gif

Цитата(khach @ Jul 1 2013, 21:44) *
Если это интерпертатр G-cod, то очень желательно в алгориме поддерживать постоянную линейную скорость обрабатываюшего инструмента на дуге. А перед крутыми дугами с мелким радиусом еще и притормозить.

спасибо, в принципе это я знал, но еще я хочу попробовать реализовать алгоритм во вложении (пока не знаю платформу для реализации ПК или МК).
Но пока не придумал как это сделать...
Tiro
Цитата(Maverick @ Jul 1 2013, 22:28) *
...я хочу попробовать реализовать алгоритм во вложении (пока не знаю платформу для реализации ПК или МК).
Но пока не придумал как это сделать...

Пробовать лучше на ПК, средств отладки больше, с переносом на МК. А вообще в управлении установками обычно уставками ограничивают максимальную скорость и ускорение привода, возможно, тогда не придется считать вперед, как в статье.
Maverick
Цитата(Tiro @ Jul 1 2013, 22:51) *
Пробовать лучше на ПК, средств отладки больше, с переносом на МК. А вообще в управлении установками обычно уставками ограничивают максимальную скорость и ускорение привода, возможно, тогда не придется считать вперед, как в статье.

мне казалось, что в статье приведен алгоритм что пока нет "сильного" изменения траектории движения, то несколько G-code могут двигателями обрабатываться "одновременно", т.е. для них один профиль движения (одна трапеция работы двигателей), а не для каждого G-code свой профиль движения (трапеция)
PS См рис 4.15 и текст сразу после рисунка 4.17

Цитата(Tiro @ Jul 1 2013, 22:51) *

не поделитесь алгоритмами, где/как выбирается/объясняется, где "крутая" дуга с мелким радиусом, "крутой" поворот, а где нет...
От чего это зависит? Как снижать скорость шагового двигателя в зависимости от угла поворота, радиуса дуги?
PS Пожалуйста, хотя бы намекните где "копать", чего читать...
Tiro
Цитата
(Maverick @ Jul 1 2013, 23:17) *
мне казалось, что в статье приведен алгоритм что пока нет "сильного" изменения траектории движения, то несколько G-code могут двигателями обрабатываться "одновременно", т.е. для них один профиль движения


Цитата
не поделитесь алгоритмами, где/как выбирается/объясняется, где "крутая" дуга с мелким радиусом, "крутой" поворот, а где нет...

В статье описано про заглядывание-вперед, это не сильно поможет, если ограничить скорость и ускорение. Сразу скажу, что не машиностроитель. Могу помочь только теоретически из собственных соображений, без пруфлинков. Поскольку математика дискретная по времени и перемещению, то можно из этих ограничений вывести формулы перемещения приводов, не превышающие лимиты скорости и т.д. Скорее всего кто-то владеет вопросом лучше и глубже. Вы смотрели форум http://www.fsapr2000.ru/? А вообще инструменты обработки обычно режущие с большой нагрузкой и там произвольно менять подачу или скорость чревато разрушением.
khach
Цитата(Maverick @ Jul 1 2013, 21:28) *
Как мне показалось при первом просмотре, что там вообще оно ПК-ориентированное.
А хотелось бы положить на более медленный процессор, чем ПК или ARM9 (и выше).
Вы с этим линуксом работали? Если да, то на какой платформе? Раскажите впечатления.

Так положили уже давно- взять тот же GRBL https://github.com/grbl - он вообще под атмегу создавался, под АРМы его потом перекомпилировали.
Основу linux-cnc сотавлял независимый код интерператора от NIST http://code.google.com/p/rs274ngc/ Его конечно расширили и привязали к философии HAL linux-cnc, но ведь можно все это выкинуть. Т.е интерпретатор кода генерит траекторию (у linux-cnc 6 координат для 6 осей за квант времени, но одновременно только 3 работают) и складывает их в очередь. А уже motion controller выбирает из этой очереди кванты положения и управляет двигателями осей через таймера.
Как пример минималистическйо конструкции - вот проект автономного контроллера на STM32, исходники есть в теме. http://www.cnczone.ru/forums/index.php?showtopic=3334
FPU начинает требоваться при сложных движениях- например нарезка резьбы фрезой резьбовой. Когда подача должна быть синхронизирована со шпинделем, а замедлить обороты шпинделя нельзя- начнет наволакивать металл при низкой скорости.
Вот кстати пример использования FPU cortex LPC43xx для интерпертайии G-кода http://www.lpcware.com/content/contribproj/jdurand-lpc4300ex (ссылка на код внизу темы)
rat
Рисовал по этому алгоритму окружность на ПЛИС. Только + и -, без умножений или делений, квадратов.
Maverick
Делаю интерполяцию...
у меня простой вопрос как для сплайна 5 степени найти коэффициенты, например зная 5-6 точек через которые должна пройти интерполирующая функция.
Интересует решение в символьном виде, нахождения коеффициентов. Пытался решить в SMath, но увы...
Для 3 степени решение в символьном виде осилил...
PS знаю вопрос простой, но что-то не получается, знаю что нужно решить систему уравнений
PS PS Хочу проверить эту статью и понять правда написана или нет. Стоит или не стоит такое решение применять на практике... Может достаточно кубического сплайна...

Также понимаю и знаю, что
Вычисление коэффициентов полинома посредством решения системы в вычислительной практике используется крайне редко. Причиной этого является плохая обусловленность матрицы, приводящая к заметному росту погрешности в выполнении условий интерполирования уже при сравнительно невысоких порядках полинома. К этому следует добавить, что вычислительные затраты реализации метода пропорциональны n^3.
_pv
наименьшие квадраты:
http://mathworld.wolfram.com/LeastSquaresF...Polynomial.html
решение получившийся матрицы 5х5 конечно можно попробовать и расписать, как для 2х2 LinearSolve[{{a, b}, {c, d}}, {x, y}] => {(d x - b y)/(-b c + a d), (c x - a y)/(b c - a d)}
но проще и быстрее будет по Гауссу.
http://mathworld.wolfram.com/GaussianElimination.html
Maverick
Цитата(_pv @ Sep 25 2013, 16:19) *
наименьшие квадраты:
http://mathworld.wolfram.com/LeastSquaresF...Polynomial.html
решение получившийся матрицы 5х5 конечно можно попробовать и расписать, как для 2х2 LinearSolve[{{a, b}, {c, d}}, {x, y}] => {(d x - b y)/(-b c + a d), (c x - a y)/(b c - a d)}
но проще и быстрее будет по Гауссу.
http://mathworld.wolfram.com/GaussianElimination.html

спасибо.
но мне решение мне нужно в символьном виде, так мне матлаб или SMath без проблем решает...
может кто-то подскажет как это сделать в матлабе или в SMath (ссылку на который давал ранее)
_pv
решение матрицы 5х5 в символьном виде?

Цитата(Maverick @ Sep 25 2013, 19:25) *
PS PS Хочу проверить эту статью и понять правда написана или нет. Стоит или не стоит такое решение применять на практике... Может достаточно кубического сплайна...

статья странная, взяли траекторию ввиде двух дуг окружностей с разными радиусами, соответственно при переходе с одной на другую понятно что будет скачёк во второй и более высоких производных, натянули на это кубический сплайн, который требует непрерывность только второй производной, и смотря на график третьей, говорят: ой как плохо, лучше возмем сплайн 5го порядка у которого и третья производная будет непрерывна, и по тогда графику третьей производной стало: ой как хорошо, мы убрали рывки.
только вот неплохо бы при этом на ошибку непосредственно траектории посмотреть, да через точки сетки она конечно проидёт, но вот что будет на стыке двух окружностей между узлами сетки где они сгладили третью производную, которая обязана рваться, потому что геометрия так задана - про это почему-то умолчали.
Maverick
Цитата(_pv @ Sep 25 2013, 17:50) *
...статья странная...

согласен из-за этого и появилось желание проверить ее...

вопрос снят - решил...
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Invision Power Board © 2001-2025 Invision Power Services, Inc.