Бикубический участок поверхности Безье представляет собой массив трехмерных точек 4x4. Да, четыре угла касаются поверхности; а строки - это кривые Безье, а столбцы - тоже кривые Безье. Но алгоритм де Кастельжау основан на вычислении медианы между двумя точками и имеет одинаковое значение как в 3D, так и в 2D.
Следующим шагом в завершении приведенного выше кода является разделение патчей для покрытия меньших частей. Тогда простое извлечение граничной кривой выше становится подходящей полигональной сеткой.
Начните с выравнивания патчей, вставляя данные вершин напрямую, вместо использования отдельного кеша. Этот код выполняет итерацию по патчам, ищет точки в массиве вершин и создает новый массив патчей, который затем переопределяется с тем же именем.
/patch[ patch{ [exch { 1 sub vert exch get }forall ] }forall ]def
Затем нам понадобится алгоритм де Кастельжау для разделения кривых Безье. vop поступает из библиотеки матриц и применяет бинарную операцию к соответствующим элементам вектора и в результате создает новый вектор.
/median { % [x0 y0 z0] [x1 y1 z1]
{add 2 div} vop % [ (x0+x1)/2 (y0+y1)/2 (z0+z1)/2 ]
} def
/decasteljau { % [P0] P1 P2 P3 . P0 P1' P2' P3' P3' P4' P5' P3
{p3 p2 p1 p0}{exch def}forall
/p01 p0 p1 median def
/p12 p1 p2 median def
/p23 p2 p3 median def
/p012 p01 p12 median def
/p123 p12 p23 median def
/p0123 p012 p123 median def
p0 p01 p012 p0123 % first half-curve
p0123 p123 p23 p3 % second half-curve
} def
Затем некоторые манипуляции со стеком применяются к каждой строке патча и объединяют результаты в 2 новых патча.
/splitrows { % [b0 .. b15] . [c0 .. c15] [d0 .. d15]
aload pop % b0 .. b15
4 { % on each of 4 rows
16 12 roll decasteljau % roll the first 4 to the top
8 4 roll % exch left and right halves (probably unnecessary)
20 4 roll % roll new curve to below the patch (pushing earlier ones lower)
} repeat
16 array astore % pack the left patch
17 1 roll 16 array astore % roll, pack the right patch
} def
Уродливая утилита позволяет нам повторно использовать код строки для столбцов. Комментарии стека были необходимы для написания этой процедуры, поэтому они, вероятно, необходимы для ее чтения. n j roll перекатывает n элементов (влево) j раз; == верхние j элементов над n-м элементом (считая от 1). Таким образом, n постоянно уменьшается, выбирая куда для размещения элемента, а j выбирает, какой элемент поместить туда (перетаскивая за собой все остальное). Если бы было применено bind, эта процедура была бы значительно быстрее, чем процедура на основе словаря.
% [ 0 1 2 3
% 4 5 6 7
% 8 9 10 11
% 12 13 14 15 ]
/xpose {
aload pop % 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
15 12 roll % 0 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3
14 11 roll % 0 4 8 9 10 11 12 13 14 15 1 2 3 5 6 7
13 10 roll % 0 4 8 12 13 14 15 1 2 3 5 6 7 9 10 11
12 9 roll % 0 4 8 12 1 2 3 5 6 7 9 10 11 13 14 15
11 9 roll % 0 4 8 12 1 5 6 7 9 10 11 13 14 15 2 3
10 8 roll % 0 4 8 12 1 5 9 10 11 13 14 15 2 3 6 7
9 7 roll % 0 4 8 12 1 5 9 13 14 15 2 3 6 7 10 11
8 6 roll % 0 4 8 12 1 5 9 13 2 3 6 7 10 11 14 15
7 6 roll % 0 4 8 12 1 5 9 13 2 6 7 10 11 14 15 3
6 5 roll % 0 4 8 12 1 5 9 13 2 6 10 11 14 15 3 7
5 4 roll % 0 4 8 12 1 5 9 13 2 6 10 14 15 3 7 11
4 3 roll % 0 4 8 12 1 5 9 13 2 6 10 14 3 7 11 15
16 array astore
} def
% [ 0 4 8 12
% 1 5 9 13
% 2 6 10 14
% 3 7 11 15 ]
/splitcols {
xpose
splitrows
xpose
} def
Затем примените эти функции к данным патча. Опять же, каждый раз заново определяя патч.
/patch[ patch{ splitrows }forall ]def
/patch[ patch{ splitrows }forall ]def
/patch[ patch{ splitcols }forall ]def
/patch[ patch{ splitcols }forall ]def
Это дает возможность работать с более мелкими фрагментами.
Добавьте тест на видимость.
/visible { % patch . patch boolean
dup % p p
dup 3 get exch dup 0 get exch 12 get % p p3 p0 p12
1 index {sub} vop % p p3 p0 v0->12
3 1 roll {sub} vop % p v0->12 v0->3
cross /normal exch def
dup
[ exch dup 0 get exch dup 3 get exch dup 12 get exch 15 get ]
{ Cam {sub} vop normal dot 0 ge } forall
%add add add 4 div 0 lt
or or or
} def
Производство
Обновление: тест был выполнен в обратном направлении.
Обновление: Тест бесполезен! На изображении видно, что нижняя часть не ориентирована наружу, и, конечно, отбраковка обратной стороны не препятствует тому, чтобы ручка была видна через горшок. Это требует удаления скрытой поверхности. А поскольку Postscript не поддерживает Z-буфер, я предполагаю, что это должен быть раздел двоичного пространства. Так что это возвращение к книгам для меня.
Обновление: добавьте преобразование Модель-> Мир, чтобы повернуть вещь вертикально.
/Model -90 rotx def % model->world transform
/proj {
Model matmul 0 get % perform model->world transform
Cam {sub} vop % translate to camera coords
...
Продюсирую это.
Полная программа на данный момент. (использует библиотеку матриц: mat.ps.) В ghostscript вы можете просмотреть анимированное вращение, удерживая [enter].
%!
%%BoundingBox: 109 246 492 487
%-109 -246 translate
(mat.ps)run %include matrix library
(det.ps)run %supplementary determinant function
/tok{ token pop exch pop }def
/s{(,){search{ tok 3 1 roll }{ tok exit }ifelse }loop }def
/f(teapot)(r)file def
/patch[ f token pop { [ f 100 string readline pop s ] } repeat ]def
/vert[ f token pop { [ f 100 string readline pop s ] } repeat ]def
/patch[ patch{ [exch { 1 sub vert exch get }forall ] }forall ]def
%vert == patch == %test data input flush quit
/I3 3 ident def % 3D identity matrix
/Cam [ 0 0 10 ] def % world coords of camera center viewpoint
/Theta [ 0 0 0 ] def % y-rotation x-rotation z-rotation
/Eye [ 0 0 15 ] def % eye relative to camera vp
/Rot I3 def % initial rotation seq
/Model -90 rotx def % model->world transform
/makerot {
Theta 0 get roty % pan
Theta 1 get rotx matmul % tilt
Theta 2 get rotz matmul % twist
} def
/proj {
Model matmul 0 get % perform model->world transform
Cam {sub} vop % translate to camera coords
Rot matmul % perform camera rotation
0 get aload pop Eye aload pop % extract dot x,y,z and eye xyz
4 3 roll div exch neg % perform perspective projection
4 3 roll add 1 index mul
4 1 roll 3 1 roll sub mul exch % (ez/dz)(dx-ex) (ez/dz)(dy-ey)
} def
/median { % [x0 y0 z0] [x1 y1 z1]
{add 2 div} vop % [ (x0+x1)/2 (y0+y1)/2 (z0+z1)/2 ]
} def
/decasteljau { % [P0] P1 P2 P3 . P0 P1' P2' P3' P3' P4' P5' P3
{p3 p2 p1 p0}{exch def}forall
/p01 p0 p1 median def
/p12 p1 p2 median def
/p23 p2 p3 median def
/p012 p01 p12 median def
/p123 p12 p23 median def
/p0123 p012 p123 median def
p0 p01 p012 p0123
p0123 p123 p23 p3
} def
/splitrows { % [b0 .. b15] . [c0 .. c15] [d0 .. d15]
aload pop % b0 .. b15
4 {
16 12 roll decasteljau
%8 4 roll
20 4 roll
} repeat
16 array astore
17 1 roll 16 array astore
} def
/xpose {
aload pop % 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
15 12 roll % 0 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3
14 11 roll % 0 4 8 9 10 11 12 13 14 15 1 2 3 5 6 7
13 10 roll % 0 4 8 12 13 14 15 1 2 3 5 6 7 9 10 11
12 9 roll % 0 4 8 12 1 2 3 5 6 7 9 10 11 13 14 15
11 9 roll % 0 4 8 12 1 5 6 7 9 10 11 13 14 15 2 3
10 8 roll % 0 4 8 12 1 5 9 10 11 13 14 15 2 3 6 7
9 7 roll % 0 4 8 12 1 5 9 13 14 15 2 3 6 7 10 11
8 6 roll % 0 4 8 12 1 5 9 13 2 3 6 7 10 11 14 15
7 6 roll % 0 4 8 12 1 5 9 13 2 6 7 10 11 14 15 3
6 5 roll % 0 4 8 12 1 5 9 13 2 6 10 11 14 15 3 7
5 4 roll % 0 4 8 12 1 5 9 13 2 6 10 14 15 3 7 11
4 3 roll % 0 4 8 12 1 5 9 13 2 6 10 14 3 7 11 14
16 array astore
} def
/splitcols {
xpose
splitrows
xpose exch xpose
} def
/patch[ patch{ splitrows }forall ]def
/patch[ patch{ splitrows }forall ]def
/patch[ patch{ splitrows }forall ]def
/patch[ patch{ splitrows }forall ]def
/patch[ patch{ splitcols }forall ]def
/patch[ patch{ splitcols }forall ]def
/color {normal light dot 1 add 4 div
%1 exch sub
setgray} def
/visible { % patch . patch boolean
dup % p p
dup 3 get exch dup 0 get exch 12 get % p p3 p0 p12
1 index {sub} vop % p p3 p0 v0->12
3 1 roll {sub} vop % p v0->12 v0->3
cross /normal exch def
dup
[ exch dup 0 get exch dup 3 get exch dup 12 get exch 15 get ]
{ Cam {sub} vop normal dot 0 ge } forall
%add add add 4 div 0 lt
or or or
} def
/drawpatch {
% Four corners
%[ exch dup 0 get exch dup 3 get exch dup 12 get exch 15 get ]
visible {
[ exch
% control rows
%dup 4 get exch dup 5 get exch dup 6 get exch dup 7 get exch
%dup 11 get exch dup 10 get exch dup 9 get exch dup 8 get exch
% control columns
%dup 1 get exch dup 5 get exch dup 9 get exch dup 13 get exch
%dup 14 get exch dup 10 get exch dup 6 get exch dup 2 get exch
% Boundary curves
dup 8 get exch dup 4 get exch dup 0 get exch %curveto4
dup 14 get exch dup 13 get exch dup 12 get exch %curveto3
dup 7 get exch dup 11 get exch dup 15 get exch %curveto2
dup 1 get exch dup 2 get exch dup 3 get exch %curveto1
dup 0 get exch %moveto
pop ]
{ proj } forall
moveto curveto curveto curveto curveto
%moveto lineto lineto lineto lineto lineto lineto lineto closepath
%moveto lineto lineto lineto lineto lineto lineto lineto closepath
stroke
%flushpage flush (%lineedit)(r)file pop
}{
pop
}ifelse
} def
/R 20 def
/H -3 def
/ang 10 def
{
300 700 translate
1 70 dup dup scale div setlinewidth
% camera revolves around Y axis at height H, dist R
/Cam [ ang sin R mul H ang cos R mul ] def
/Theta [ ang H R atan 0 ] def % rotate camera back to origin
/Rot makerot def % squash rotation sequence into a matrix
patch {
drawpatch
} forall
pstack
showpage
%exit
/ang ang 10 add def
} loop
person
luser droog
schedule
30.01.2013
