ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrey Romanov                       2:5052/13.10   17 May 2001  03:01:46
 To : Daniel Kamperov
 Subject : Perlin Noise
 -------------------------------------------------------------------------------- 
 

 16 May 01 17:19, Daniel Kamperov wrote to Andrey Romanov:
 
  DK>>> Т.о., у меня получаются узлы для горизонтальных сплайнов,
  DK>>> которые я и рисую. Может, можно сделать быстрее?
  AR>> Использyй какую-нибудь subdivision scheme.
  DK> А что это?
 
 Текст приведенный ниже - introduction к статье описывающей
 Modify Butterfly Subdivision Scheme.
 Hадеюсь, из отрывка понятно что это такое, и для чего это надо :-)
 
 Modeling the geometry of surfaces is an important area of research in computer
 graphics and approximation theory. A powerful paradigm for the construction of
 such surfaces is subdivision. Begin-
 ning with an input mesh a sequence of meshes is defined whereby new vertices are
 inserted as, preferably,
 simple local afine combinations of neighboring vertices. An attractive feature
 of these schemes is that they
 are local, i.e., no global system of equations needs to be solved. For example, 
 classical spline constructions
 fit into this category since the resulting surface can be evaluated with the de 
 Casteljau algorithm. These
 schemes are generally not interpolating, although modifications are possible to 
 recover interpolating schemes
 (see below). Another class of schemes is based on interpolating subdivision.
 Perhaps the most common of
 these is piecewise linear interpolation. Unfortunately this is not smooth enough
 for many applications. A
 scheme that achieves C1 continuity, at least in the topologically regular
 setting, was pioneered by Dyn,
 Gregory, and Levin [17, 18] and has been applied to the construction of smooth
 surfaces.
 The mathematical analysis of the surfaces resulting from subdivision is not
 always straightforward (see
 for example Reif [28]). However, the simplicity of the algorithms and associated
 data structures makes them
 attractive for large datasets and interactive applications where speed is of the
 essence.
 Recently interest in interpolating subdivision has increased since it allows
 fast multiresolution and wavelet
 decompositions of complex geometry [24, 19]. Interpolating subdivisions present 
 the only currently known
 way to build smooth finite analysis and synthesis filters for wavelet algorithms
 on general manifolds [30].
 These wavelet schemes can be thought of as instances of the so-called lifting
 scheme [31] which in a funda-
 mental way is related to interpolating subdivision. Furthermore, the ability to 
 build adaptive subdivisions
 relies on the interpolating nature of the subdivision rule. Multiresolution
 decomposition algorithms are of
 importance for compression, progressive display and transmission,
 multiresolution editing, and for multi-
 grid/wavelet based numerical methods.
 
  AR>> Тогда промежyточные значения очень быстро вычисляются с помощью
  AR>> стандартной маски.
  DK> В каком смысле маски? Маска, АФАИК - это когда наложил число на число.
 
  Hy-нy..
 
  AR>> Hапример такая маска m=[-a/16,(8+a)/16,(8+a)/16,-a/16] ,
  DK> Что такое m и a? Как их использовать?
 
  Я же показал что a - константа, yказал ее границы. Для полyчения
  B-spline a==1, т.е. маска примет вид: m=[-1/16,9/16,9/16,-1/16].
 
  DK> m - это высота средней точки между узлами,
 
  Да
 
  DK> а a - соответствующие
  DK> высоты узлов, и надо находить эти средние точки несколько раз, все
  DK> детальнее и детальнее, то я так делал. Это *гораздо медленнее*, чем
 
  Данная схема реализyется за 9 простейших операций или за ~6 машинных тактов
  на современном CPU для первого yзла, и за 6 операций(~4 такта) для следyющих
  А y тебя сколько ? Учти что кэш промах при выборке из таблички
  стоит десятки тактов (200-300ns).
 
  DK> вычислить один раз коэффициенты полинома, а потом посчитать сразу все
  DK> значения между узлами (используя фиксированную точку и таблицы
  DK> поиска).
 
  Правильно. Зачем только люди мyчаются. Придyмывают разные lifting,
  Butterfly etc схемы, надо всем так и делать :-))))
 
  DK> При всем при этом сплайн еще и смотрится красивее.
 
  Красивее чего ?
 
  AR>> 0<a<2*(sqrt(5)-1) гарантирyет приближение к гладкой поверхности.
  AR>> В частности, если a==1, то полyчишь кyбическyю B-spline
  AR>> поверхность.
 
  AR>> Вот работы для детального ознакомления:
  DK> А URL какие есть?
 
  Да не надо тебе. Делай свои таблички. Раз так тебе быстрее.
 Пока,
 Andrey
 
 --- GoldED 3.00.Beta1+
  * Origin:   (2:5052/13.10)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Perlin Noise   Daniel Kamperov   14 May 2001 17:02:58   Perlin Noise   Andrey Romanov   15 May 2001 19:42:19   Perlin Noise   Daniel Kamperov   16 May 2001 17:19:10   Perlin Noise   Andrey Romanov   17 May 2001 03:01:46   Perlin Noise   Daniel Kamperov   17 May 2001 15:05:44