Как построить кривую Безье?

← →
WondeRu © (2005-02-17 10:03) [0]

Здравствуйте, уважаемые!

Вот задался проблемой, как построить кривую Безье! Но алгоритмов готовых так и не нахожу. В OpenGL для этого существует специальня функция...

Glu.gluNurbsCurve(theNurb, KnotCounter, //количество праметрических узлов кривой curveKnots, //указатель на массив этих узлов, array[0..N] of float; 2, // сколько элементов на одну точку (здесь 2 - X, Y) ctrlPoints, // массив опорных точек, array[0..K, 2] of float; 4, // порядок степени кривой + 1 Gl.GL_MAP1_VERTEX_3);

как реализовать похожую функцию без OpenGL, чтобы получить массив вершин кривой. (на С или Делфи)

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

← →
Alx2 © (2005-02-17 10:05) [1]

А что такое "вершина кривой"?

← →
Kerk © (2005-02-17 10:07) [2]

> WondeRu

У меня дома исходник на делфи есть.. для лабы писал.. позже скину, если надо

← →
Cosinus © (2005-02-17 10:07) [3]

Это не подойдет?
http://www.delphirus.com.ru/delphi-sovetid-1250.html

ПыСы Первая ссылка в яндексе :)

← →
MBo © (2005-02-17 10:08) [4]

gluNurbsCurve, насколько я понимаю из названия и хелпа, строит Non-Uniform Rational B-Spline - кривую более общего вида, чем Безье. Так что именно тебе требуется?

← →
Cosinus © (2005-02-17 10:11) [5]

Вот еще
http://alglib.manual.ru/interpolation/beziercurve.php
http://softsearch.ru/programs/10394.shtml

← →
WondeRu © (2005-02-17 10:31) [6]

MBo © (17.02.05 10:08) [4]
Так что именно тебе требуется?

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

Kerk © (17.02.05 10:07) [2]
У меня дома исходник на делфи есть.. для лабы писал.. позже скину, если надо
"а Маккона есть у меня дома"(с) )))
обязательно скинь!

Cosinus © - пасиба за ссылки!

← →
MBo © (2005-02-17 12:12) [7]

>WondeRu
Так ты задачу опиши

← →
TUser © (2005-02-17 12:14) [8]

Если практически говорить, то - PolyBezier и PolyDraw.
Если попрактиковаться в алгоритмах охота - то построение кБ описано в любом учебнике и на любом сайте. Делается это рекурсией - построение кривой зассматривается, как построение двух кривых меньшего размера.

← →
вредитель © (2005-02-17 12:26) [9]

Делается это рекурсией - построение кривой зассматривается, как построение двух кривых меньшего размера.
Это при автоматической минимизации погрешности. Однако, при реализации этого способа есть такая проблема: при дихотомии может попасться отрезок, содержащий точку перигиба (вторая производная равна нулю), в результате чего, на этом отрезке погрешность может быть весьма большой, поэтому, при дихотомии необходимо делить отрезки так, чтобы точка перегиба лежала на одном из концов отрезка. Вычислить ее можно лишь численными методами (что зело долго) и в зависимости от начальных условий, таких точек может быть несколько. Решений этой проблемы на сайтах а не встречал, интересно было бы увидеть.

← →
Digitman © (2005-02-17 12:36) [10]

> Как построить кривую Безье?

хм .. чья кривая, тот пусть сам и строит ее)
а то ить не напасешься на каждого - у одного кривая, у другого косая ..

← →
WondeRu w/o client (2005-02-17 13:57) [11]

>Так ты задачу опиши

задача такая: вышеприведенная функция через модуль OpenGL.pas в Delphi работает замечательно, а сейчас перевожу весь код на C#, используя сторонние компоненты Tao.OpenGL. Эти компоненты реализованы довольно кривоавто, но зато избавляют от мороки самому писать wraper"ы для OpenGL32.dll, Glu32.dll...

видимо из-за "косяка" в Tao данная функция не работает... поэтому приходится реализовывать самому отрисовку сплайна через отрезки...

вредитель © (17.02.05 12:26) [9]
ничего не понял)

найти книжку Э. Эйнджела... названия не помню, но их там два издания, необходимо второе...
там как раз эти сплайны хорошо разжеваны....

Дональд Кнут в книге "Всё о метафонт" пишет об этом. Книги у меня под рукой нет, опишу своими словами идею, которая геометрически довольно проста.

Кривая начинается в точке A, идет по направлению к точке B и приходит к точке D с направления на точку С. Алгоритм предлагается следующий: Берем ломаную ABCD. X1 - середина отрезка AB, X2 - середина BC, X3 - середина CD. Заменяем ломаную ABCD на A-X1-X2-X3-D. Снова в получившейся ломаной берем середины отрезков и соединяем их от начала к концу очередной ломаной. И так, пока очередная ломаная не будет отличаться от предыдущей при прорисовке на пиксельной сетке.

Петзолд в своем двухтомнике по Windows 95 приводит описывает кривую Безье формулой:

До появления Windows 95 сплайны Безье создавались с помощью функции Polyline. Вам следовало также знать параметрические уравнения, описывающие сплайны Безье. Начальная точка (x0,y0), конечная точка (x3, y3). Две контрольные точки (x1, y1) и (x2, y2). Кривая, отображаемая в интервале t от 0 до 1 описывалась так:

x(t) = (1-t)3x0 + 3t(1-t)2x1 + 3t2(1-t)x2 +t3x3
y(t) = (1-t)3y0 + 3t(1-t)2y1 + 3t2(1-t)y2 +t3y3

WondeRu w/o client (17.02.05 13:57) [11]
ничего не понял)

Ээээ... попробую на пальцах. Ежели вычислять все точки кривой с одинаковым шагом, то в зависимости от кривизны, точек может быть больше или меньше чем надо и кривая получается некрасивой (толстая или ломаная). Дабы этого избежать ея строят сначала с большим шагом, вычисляя погрешность соответствия теоретической кривой, каждого полученного сегмента, и если она больше заранее установленной минимальной погрешности, то отрезок рубят на два и продолжают так рекурсивно. Погрешность, в простейшем случае, вычисляют как расстояние от точки лежащей в середине аппроксимируемого куска теоритической кривой, до точки, лежащей на середине полученного в результате аппроксимации сегмента. Т.е. Если левая точка куска (x(t), y(t)) [1], а правая (x(t + 2), y(t + 2)) [2], то находят значение (x(t + 1), y(t + 1)) [3] и вычисляют расстояние до середины прямой, проходящей через точки [1] и [2], что сделать не сложно. Если вдруг [3] оказывается точкой перегиба (или близкой к ней), то погрешность в этой точке оказывается равной нулю (аппроксимирующий отрезок пересекает кривую), и отрезок принимается, как соответствующий условиям аппроксимации, хотя погрешности у его концов могут превышать минимальную. Проблема состоит в отлове точек перегиба и поведении при их обнаружении.

вредитель © (17.02.05 15:01) [14]
мысль понял...

Реализацию я все-таки сделаю на OpenGL, выяснил же все-таки обойти (не решить) даную проблему, используя стандартную функцию gluNurbsCurve...

Как построить кривую Безье? Найти похожие ветки