Кривые и криволинейные поверхности

10.9.1. Методы вычисления полиномов Рассмотрим полиномиальную форму задания кривой на стандартном интервале:

m

Р(") = £с/м'. 0<м<1.

;=0

Можно вычислить значения р(и) для некоторого множества значений параметра {ик} и затем использовать кусочно-линейную аппроксимацию кривой (в OpenGL это делается с помощью примитива типа GL_LINE_STRIP). Вместо того чтобы вычислять независимо каждый член, содержащий их можно сгруппировать следующим образом: р(и) = С0+м(с,+и(С2+м(-"+С,,«)))После такой группировки для вычисления значения полинома р{ик) потребуется только п умножений. Этот алгоритм известен под названием схемы Горнера {Horner's method). Типовой кубический полином р(и) группируется по этой схеме следующим образом: Р(м) = Со+«(С,+«(С2+«Сз)).

Если отсчеты значения параметра {«,} распределены равномерно на заданном интервале представления полинома, то для вычисления р(ик) можно использовать метод правых разностей (forward differences), который требует О(п) сложений и ни единого умножения. Этот метод реализуется следующей итерационной процедурой: Д(0)р("*) = Р("*), Д(1)р("*) = р(ижЬр("*Х

А('и+,)р(«*) = А('и)Р(«*+.ЬА,'")р("*)Если u^-uirh , то несложно показать, что для полинома р(м) степени п значение А("}р(ик) будет постоянным при любом к. Из этого результата следует вычислительная схема, вариант которой для скалярного кубического полинома представлен на рис. 10.30: р(и)= \+Зи+2и2+и.

Для вычислений по этой схеме значения А^р(ио) требуется знать первые п+\ значений функции р(ик). Располагая значением Д(")/?(м0), можно скопировать его в ячейки таблицы и работать дальше по схеме, представленной на рис. 10.31. Последующие значения р(ик) вычисляются по рекуррентной формуле, полученной перестановкой членов в приведенном выше соотношении:

A(m-])p(uk+i) = А(т)р(ик)+А(т-])р(ик).

Этот метод довольно эффективен, но, к сожалению, его можно применять только на равномерной сетке, и он склонен к накоплению ошибок вычислений.

⇐ Предыдущая| |Следующая ⇒