Бугреев ПЗ (1231492), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

2.3 Моделирование движения поезда

При моделировании железнодорожного участка сплайнами возникает задача визуализировать движение модели поезда по участку. Решить задачу поиска точки на кривой в заданный момент времени t не составляет больших трудностей, при условии, что известны опорные точки параметрической кривой. Однако при вычислении точек методом перебора параметра t с заданным интервалом возникает ряд проблем. Во-первых, невозможно однозначно задать интервал перебора t, ввиду разных форм кривых. Во-вторых, на кривых участках сплайна вычисляется большее количество точек, чем на прямых участках. Поэтому при заданном шаге параметра t, сплайн разбивается на отрезки не равной длины.

Рисунок 2.7 – Неравномерность сплайна

Если осуществить движение модели тележки вагона по рассчитанным точкам кривой возникнет эффект «убегания» колесных пар или «растягивания» вагона, ввиду вышеописанных проблем. Можно допустить, что на кривых участках в реальности, действительно имеет место данный эффект, однако он не так велик и существенен, как в рассчитанном примере.

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

Для осуществления плавности движения и избавления от эффекта растягивания вагонов необходимо представить кривую Безье аппроксимированной прямой. Спрямление кривой отрезками малой длины позволит существенно снизить вычислительную нагрузку на машинный процессор, без вреда для визуализации. Однако проблема отыскание точек, которые будут соединены отрезками, требует так же менее ресурсоёмкого решения.

2.4 Методы аппроксимации кривых Безье

2.4.1 Метод «радиус-векторов»

Наиболее простым решением может являться метод радиусов окружностей. Если построить окружность с центром в первой опорной точке и провести радиус-вектор в точку пересечения дуги с кривой, а затем продолжать данный алгоритм, используя полученную точку в качестве нового центра окружности, можно получить кривую, сглаженную прямыми отрезками равной длины. При этом можно довольно легко изменять желаемую длину прямых отрезков. Пример аппроксимации кривой методом «радиус-векторов» показан на рисунке 2.8.

Рисунок 2.8 – Аппроксимация методом «радиус-векторов»

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

2.4.2 Метод на основе сплайнов Катмулл-Рома

При решении задачи аппроксимации кривых Безье, нельзя обратить внимание на метод аппроксимации сплайнами. Казалось бы, зачем моделировать кривые сплайнами, а затем аппроксимировать их теми же сплайнами. Дело в том, что все сплайны достаточно хороши при различных условиях применения и систематического подхода к выбору того или иного сплайна нет. Как упоминалось ранее, сплайны Безье были выбраны в силу их способности дать разработчику интуитивное представление о виде кривой по расположению опорных точек. Таким свойством не обладает сплайны Катмулл-Рома, однако они позволяют применять их при аппроксимации.

Сплайны Катмулл-Рома были разработаны Эдвином Катмулом и Рафаэлем Ромом и представляют собой интерполяционный сплайн, который задается четырьмя опорными точками. Особенностью такого сплайна является прохождение его через все опорные точки. Сплайны Катмулл-Рома определяются по формуле 2.9.

Матричная запись параметрических уравнений, описывающих элементарный сплайн Катмулл-Рома, имеет вид[3]:

где

матрица опорных точек;

базисная матрица;

матрица параметра t.

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

Рисунок 2.9 – Графическое представление аппроксимации сплайном Катмулл-Рома

Из рисунка 2.9. можно видеть, что имея четыре опорные точки, аппроксимации подвергается участок между двумя точками, находящимися «посередине». Что бы спрямить весь сплайн Безье сплайном Катмулл-Рома необходимо иметь достаточно большой набор определенных заранее опорных точек, а затем смещаться, всякий раз, когда промежуточный сплайн был построен.

При всей элегантности данного метода, у него есть существенный недостаток. Заключается он в параметре t. Во-первых мы не избавля-емся от параметра t вовсе, т.е получить на сплайне равные отрезки по длине, а не по параметру t не получится. Кроме того, мы получаем свой параметр t’ меняющийся в пределах от нуля до единицы для каждого сплайна Катмулл-Рома. Эти недостатки не позволяют использовать сплайны Катмулл-Рома, как эффективный и удобный инструмент ап-проксимации кривых Безье.

2.4.3 Метод де Кастельжо

2.4.3.1 Алгоритм метода де Кастельжо

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

Рисунок 2.10 – Аппроксимация методом де Кастельжо

У данного метода есть большие достоинства, в отличии от ранее описанного. Он позволяет значительно снизить вычислительную нагруз-ку и освободить ресурсы для трёхмерной визуализации в реальном мас-штабе времени.

Существуют и недостатки алгоритма де Кастельжо. Для отыскания точки на кривой Безье 3-го порядка, необходимо произвести как минимум шесть вычислений. Затем повторить те же операции для следующей точки и так далее. Это значительно замедляет быстро-действие программы. Однако этот недостаток легко перекрывается возможностью применения стандартных рекурсивных алгоритмов.

2.4.3.2 Рекурсия и сортировка данных

Многие задачи, решение которых зависит от применения методов проб и ошибок и алгоритмов с возвратом, характеризуются отсутствием аналитического решения. Они требуют изнурительной и кропотливой работы в течении долгого времени. Поэтому решение таких задач, в большинстве, отдано вычислительным машинам, поскольку они, в отличии от человека, могут часами производить одну и ту же операцию, ни разу не допустив ошибки. Так, например, вычислительные машины достаточно просто и быстро находят значения факториала числа 196 рекурсивным методом, чем не может похвастаться человеческий мозг.

Рекурсия это определение какого-либо объекта или процесса внутри самого этого процесса. Для выражения рекурсивных программ необходимо и достаточно иметь понятие процедуры, или подпрограммы, поскольку они позволяют дать любому оператору имя, с помощью которого можно к нему обращаться. Если некоторая процедура A содержит явную ссылку на саму себя, то такая процедура называется прямо рекурсивной. Если же A ссылается на другую процедуру B, содер-жащую ссылку на A, то такая процедура именуется косвенно рекурсивной.

При работе с рекурсией необходимо помнить, что рекурсия, подобно операторам цикла, может приводить к незаканчивающимся вычислениям. Поэтому всегда необходимо помнить о необходимости создания условия выхода из рекурсии. Кроме того, необходимо рационально оценивать насколько далеко «уйдет» рекурсия, т.е сопоставлять глубину рекурсии с поставленными задачами[7].

Применение рекурсии в алгоритме де Кастельжо значительно упрощает текст программы и позволяет регулировать количество точек-маркеров на кривой посредством определения лишь глубины рекурсии.

Все точки-маркеры заносятся в некий массив записей T типа Tp в порядке их рекурсивного создания. Сама запись Tp содержит в себе поля X,Y и S. Первые два используются для хранения координат точек-маркеров, последнее для хранения расстояния от данной точки до следующей. Конечно, рекурсивный поиск точек не может упорядочить точки по порядку, например по возрастанию параметра t. Поэтому после поиска достаточного количества точек необходимо воспользоваться алгоритмами сортировки.

Одним из вариантов сортировки данных может быть сортировка использующая алгоритм прямого обмена, который основывается на сравнении и смене мест для пары соседних элементов и продолжения этого процесса до тех пор, пока не будут упорядочены все элементы. Элементы сортировки, в нашем случае это записи, можно интер-претировать как пузырьки в чане с водой, причем вес каждого соответствует его ключу и при каждом проходе один пузырек как бы поднимается до уровня, соответствующего его весу[8].

Если поставить задачу отыскания от каждой точки в массиве записей T, наименьшего расстояния S до какой-либо точки, а затем соединить их, то, казалось бы, мы получим достаточно простой и эффективный метод сортировки и аппроксимации. Однако существует особенность при использовании такого подхода. У каждой точки сущес-твует две соседних точки. Расстояния до них может быть различным. Выбирая наименьшее расстояние до соседних точек, мы не застрахованы от случая, когда возможен пропуск нескольких рас-стояний, как показано на рисунке 2.12.

Рисунок 2.11 – Алгоритм пузырьковой сортировки

Рисунок 2.12 – Пропуск расстояния, при аппроксимации прямой

Очевидно, что применение дополнительных условий создает сложности при разработке программы. Избавиться от лишних проверок позволяет другой подход к сортировке данных. Он предполагает зане-сение в поле S массива T расстояний от первой опорной точки до каждой из точек, полученных рекурсивно. Соединив опорную точку со всеми, получим следующую картину, показанную на рисунке 2.13.

Рисунок 2.13 – Наглядное изображение значений S массива T

Из рисунка 2.13 видно, что полученные точки-маркеры можно отсортировать в порядке возрастания длин поля S. Так как поле S является частью записи в массиве T, который, в свою очередь имеет порядковую индексацию, то можно отсортировать все записи массива T сортируя по полю S.

При использовании данного метода и алгоритма сортировки необходимо учесть маловероятную, но все же возможную, конфигу-рацию оси верхнего строения ж.д. пути, как показано на рисунке 2.14.

Рисунок 2.14 – Вариант кривой и применение к ней сортировки по длинам S

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

Применение рекурсивного метода для аппроксимации кривой позволяет варьировать глубину рекурсии посредством некоторой константы n типа Integer. Количество точек P будет равно выражению . Но не всегда для аппроксимации кривой Безье необходимо жестко закрепленное количество точек. Например, для сплайна, у кото-рого опорные точки расположены на одной линии нет необходимости применять алгоритмы аппроксимации, потому как этот сплайн и есть прямая. Или же, если сплайн имеет форму хоккейной клюшки: необходи-мо и достаточно спрямить только изгиб такого сплайна.

Поэтому возникает задача определение и внесения в программу некого условия выхода из рекурсивного алгоритма, которое не будет жестко регламентировано и будет меняться исходя из вида кривой.

Характеристики

Список файлов ВКР