Решение формулы Ordered Dither

Подскажите как перевести эту формулу в псевдокод?

https://dl.dropboxusercontent.com/u/6439155/or1.png

https://dl.dropboxusercontent.com/u/6439155/or2.png

https://www.cs.princeton.edu/courses...her/sld024.htm

Ты по PureBasic прикалываешься, погугли што ли..
Не нашел файлика, осталась выдранная текстовка

Спасибо. Но я все равно не понял:

откуда 4 и что такое D и U

У меня конечная цель не конвертировать картинки, а получить именно сам узор "чанок" в зависимости от произвольно заданного размера матрицы (чанка).

То есть на выходе псевдо кода хотелось бы получать массив типа:

0 8 2 10 12 4 14 6 3 11 1 9 15 7 13 5

Писал я код по статейке, но куда-то потерял( Вот код, который гоблин написал(для ужясм):

Код:

---

;69 bytes -2
        device zxspectrum128
        ORG #6000
begin
matrix:
 db 0*8,8*8,2*8,10*8
 db 12*8,4*8,14*8,6*8
 db 3*8,11*8,1*8,9*8
 db 15*8,7*8,13*8,5*8
gench:
;  For y=0 To 128;;;;;+8
;  For x=0 To 7
;      i=x&3
;      j=y&3
;      II=y>>3
;      If II <= D(i,j)
;        Plot(x,y,0)
;      Else
;        Plot(y,x,RGB(255,255,255))
;      EndIf
;    Next x
;  Next y

 ld hl,$4000
 ld b,$80;bit weight
 ld e,0;y
for_y:
 ld d,0;x
 push hl
for_x:
 push hl
;      i=x&3
;      j=y&3
 ld a,e;y
 and 3
 ld c,a
 add a,a
 add a,a;c
 ld c,a
 ld a,d;x
 and 3
 add a,c
 ld l,a
 ld h,matrix/256
 ld a,e;II=y>>3
; and %11111000
; rra:rra:rra
 cp (hl);      If II <= D(i,j)
 pop hl
;; jr z,plot
 jr c,noplot
plot:
 ld a,b:or (hl):ld (hl),a
noplot:
 inc h
 inc d
 bit 3,d:jr z,for_x
 pop hl
 or a:rrc b:jr nc,nonextp
 inc l
nonextp:

 inc e:bit 7,e:jr z,for_y
 
 jr $
end
        display /d,end-begin
        savesna "!gc.sna",gench;;begin

---

- - - Добавлено - - -

упс, нашол.

На выходе получаешь chunk.png

Спасибо. Но мне все таки нужен код именно для получения вот этого

Data.i 0,8,2,10
Data.i 12,4,14,6
Data.i 3,11,1,9
Data.i 15,7,13,5

остальное то отрисовать не сложно. )

Не особо заморачивался алгоритмом, брал готовые матрицы

здесь http://caca.zoy.org/wiki/libcaca/study/2 тожно не особо ясно.

В принципе вроде не сложно, но размерность чанок степени двойки(4х4,8х8,16х16...). Подходит? Если да могу в меру своего косноязычия описать что то типа алгоритма.

Цитата:

---

Сообщение от krt17

Подходит? Если да могу в меру своего косноязычия описать что то типа алгоритма.

---

Ага, было бы интересно хотя бы с такими поиграться.

Побаловался немного на ассемблере Z80.
Начинается всё с матрицы 1х1 содержащий нолик.
Все промежуточные матрицы хранятся в углу массива 8х8. "Matrix" 8080H
Следующая матрица получается так: (матрица умножается на константу 4, потом 3 раза копируется: (по диагонали с добавлением единички, и по ортам с добавлением 2 и 3) )
Прилагаю ассемблер (sjasmplus) с небольшими комментариями, говорящими метками и нарочитыми подпрограммами, и снапшот.

Вкратце
e(n,x,y) - элемент матрицы размерностью 2^n в строке y столбца x
рекурсивная формула

e(n,x,y)=e(n-1,x div 2,y div 2)+e(1,x mod 2,y mod 2)*2^n

матрица E(1)=[[3,1],[0,2]] определяет изначальный паттерн и соответственно элементы e(1,x,y) берутся из нее.
Разница с формулой в стартовом сообщении в использовании в качестве индекса степени, а не размерности.

исправления http://zx-pk.ru/showthread.php?t=263...l=1#post863984

add
Кстати переделать под другую размерность изначального паттерна проще простого, немного обобщаем и

e(n,x,y)=e(n-1,x div r,y div r)+e(1,x mod r,y mod r)*r^n

где r соответственно размерность

krt17, в каждой следующей матрице в 4 раза больше чисел. Напрашивается не 2 в степени, а 4^(n-1).

Цитата:

---

Сообщение от Reobne

krt17, в каждой следующей матрице в 4 раза больше чисел. Напрашивается не 2 в степени, а 4^(n-1).

---

число столбцов/строк 2^n (n=2...), число элементов будет (2^n)*(2^n)=2^(2n)=4^n зачем делить еще на 4 я не очень понял.
Для случая n=3 число строк/столбцов будет 2^3=8 элементов 4^3=64
n=4 - 16, 256
видимо у тебя n немного другое обозначает.

Внезапно на подобной хрене возможен многомерный детеринг :)

add
так да стоп я что то упустил. Сейчас шлифанем.

- - - Добавлено - - -

Все верно Reobne, был прав, я затупил
правильная формула:

e(n,x,y)=e(n-1,x div 2,y div 2)+e(1,x mod 2,y mod 2)*4^(n-1)

e(n,x,y)=e(n-1,x div r,y div r)+e(1,x mod r,y mod r)*r^2(n-1)

- - - Добавлено - - -

Ну и до кучи Lua демо

Код:

---

function elem(n,y,x)
--print (n,y,x)
if n==1 then return pattern[y+1][x+1]
  else return elem(n-1,math.floor(y/2),math.floor(x/2))+elem(1,y%2,x%2)*4^(n-1)
end

end
pattern={{3,1},{0,2}}
cur=3
for y=0,2^cur-1 do
  io.write (y.."\t")
for x=0,2^cur-1 do
  io.write (elem(cur,y,x).."\t")
  end
  io.write ("\n")
  end

---

Цитата:

---

Сообщение от krt17

Ну и до кучи Lua демо

---

Попробовал перевести на PureBasic. Получается что-то не то...

PHP код:

---

Global Dim Pattern.l(16,16)

Procedure elem(n,y,x)
  
 ; Print( Str(n) )
 ; Print( Str(x) )
 ; PrintN( Str(y) )
  
  If n=1
    
    ProcedureReturn Pattern(y+1,x+1)
    
  Else
    
    ProcedureReturn elem(n-1, Round(y/2,#PB_Round_Down), Round(x/2,#PB_Round_Down)) + elem(1, y%2, x%2) * Pow(4,(n-1))
    
  EndIf
  
EndProcedure

OpenConsole("")


 ; Pattern={{3,1},{0,2}}
Pattern(0,0) = 3
Pattern(0,1) = 1
Pattern(1,0) = 0
Pattern(1,1) = 2

cur = 3

For y=0 To Pow(2,cur-1)
   
  Print( Str(y) ); io.write (y.."\t")
  
  For x=0 To Pow(2,cur-1)
     
    Print( Str(elem(cur,y,x)) ); io.write (elem(cur,y,x).."\t")
    
    elem(cur,y,x)
  Next x
  
  PrintN(""); io.write ("\n")
Next y

CallDebugger 


---

Цитата:

---

Сообщение от newart

Получается что-то не то...

---

Для деления воспользуйся >> , видимо что то там с округлением суровое . Я не в курсе что там с басиком, на lua 100% рабочий вариант, проверял с разными cur.

- - - Добавлено - - -

О а на фига еще один elem(cur,y,x) ? Это не нужно. И что собственно получается то?

- - - Добавлено - - -

Мое при cur=4

Код:

---

D:\Dropbox\lua>lua53.exe test1.lua
0      255    127    223    95      247    119    215    87      253    125    221    93      245    117    213    85
1      63      191    31      159    55      183    23      151    61      189    29      157    53      181    21      149
2      207    79      239    111    199    71      231    103    205    77      237    109    197    69      229    101
3      15      143    47      175    7      135    39      167    13      141    45      173    5      133    37      165
4      243    115    211    83      251    123    219    91      241    113    209    81      249    121    217    89
5      51      179    19      147    59      187    27      155    49      177    17      145    57      185    25      153
6      195    67      227    99      203    75      235    107    193    65      225    97      201    73      233    105
7      3      131    35      163    11      139    43      171    1      129    33      161    9      137    41      169
8      252    124    220    92      244    116    212    84      254    126    222    94      246    118    214    86
9      60      188    28      156    52      180    20      148    62      190    30      158    54      182    22      150
10      204    76      236    108    196    68      228    100    206    78      238    110    198    70      230    102
11      12      140    44      172    4      132    36      164    14      142    46      174    6      134    38      166
12      240    112    208    80      248    120    216    88      242    114    210    82      250    122    218    90
13      48      176    16      144    56      184    24      152    50      178    18      146    58      186    26      154
14      192    64      224    96      200    72      232    104    194    66      226    98      202    74      234    106
15      0      128    32      160    8      136    40      168    2      130    34      162    10      138    42      170

---

Цитата:

---

Сообщение от krt17

О а на фига еще один elem(cur,y,x) ? Это не нужно. И что собственно получается то?

---

Да затупил, там еще в цикле -1 не туда поставил.

Теперь получается вот что:

PHP код:

---


0  170 042 138 010 162 034 130 002 168 040 136 008 160 032 128 000
1  042 042 010 010 034 034 002 002 040 040 008 008 032 032 000 000
2  138 010 138 010 130 002 130 002 136 008 136 008 128 000 128 000
3  010 010 010 010 002 002 002 002 008 008 008 008 000 000 000 000
4  162 034 130 002 162 034 130 002 160 032 128 000 160 032 128 000
5  034 034 002 002 034 034 002 002 032 032 000 000 032 032 000 000
6  130 002 130 002 130 002 130 002 128 000 128 000 128 000 128 000
7  002 002 002 002 002 002 002 002 000 000 000 000 000 000 000 000
8  168 040 136 008 160 032 128 000 168 040 136 008 160 032 128 000
9  040 040 008 008 032 032 000 000 040 040 008 008 032 032 000 000
10 136 008 136 008 128 000 128 000 136 008 136 008 128 000 128 000
11 008 008 008 008 000 000 000 000 008 008 008 008 000 000 000 000
12 160 032 128 000 160 032 128 000 160 032 128 000 160 032 128 000
13 032 032 000 000 032 032 000 000 032 032 000 000 032 032 000 000
14 128 000 128 000 128 000 128 000 128 000 128 000 128 000 128 000
15 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 


---

код такой

PHP код:

---

Global Dim Pattern.l(16,16)

Procedure elem(n,y,x)
  
  If n=1
    
    ProcedureReturn Pattern(y+1,x+1)
    
  Else
   
    ProcedureReturn elem(n-1, y>>1, x>>1) + elem(1, y%2, x%2) * Pow(4,(n-1))
    
  EndIf
  
EndProcedure

OpenConsole("")


Pattern(0,0) = 3
Pattern(0,1) = 1
Pattern(1,0) = 0
Pattern(1,1) = 2

cur = 4

For y=0 To Pow(2,cur)-1
   
  Print(  LSet(Str(y), 3, " ") )
  
  For x=0 To Pow(2,cur)-1
     
    Print( RSet( Str(elem(cur,y,x)),3, "0") + " " )
    
  Next x
  
  PrintN("")
  
Next y

CallDebugger 


---

Pattern(y+1,x+1) не то, у тебя индексы массива с 0, а в луа с 1 поэтому я прибавлял поменяй на
Pattern(y,x)

Цитата:

---

Сообщение от krt17

Pattern(y+1,x+1) не то, у тебя индексы массива с 0, а в луа с 1 поэтому я прибавлял поменяй на
Pattern(y,x)

---

Ага! Теперь результаты совпали.

Осталось понять что за массив я получил. ))
Что это за куча чисел?

Цитата:

---

Сообщение от newart

Подскажите как перевести эту формулу в псевдокод?

---

Цитата:

---

Сообщение от newart

Осталось понять что за массив я получил. ))
Что это за куча чисел?

---

Всё, это уже решение. Теперь надо сделать RET. :)
Для чего это решение было нужно?
Если конвертер картинок, то картинку нужно масштабировать, цвета нормировать от 0 до (4^n)+1, заменить цветные пиксели на чанки.
Однобитные пиксели внутри чанок получаются после сравнения цвета и соответствующего элемента матрицы.

Цитата:

---

Сообщение от Reobne

Всё, это уже решение. Теперь надо сделать RET.
Для чего это решение было нужно?
Если конвертер картинок, то картинку нужно масштабировать, цвета нормировать от 0 до (4^n)+1, заменить цветные пиксели на чанки.
Однобитные пиксели внутри чанок получаются после сравнения цвета и соответствующего элемента матрицы.

---

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

Ну то есть есть чанк (кубик 4х4х4), в нем каждый пиксель это тоже чанк, в котором каждый пиксель тоже чанк и т.п.

Это интересно! :)
Для начала надо изобрести 3Д паттерн 2х2х2.

- - - Добавлено - - -

Возможно (((0,4),(6,2)),((3,7),(5,1)))

- - - Добавлено - - -

А в формулу добавим координату:
e(n,x,y,z)=e(n-1,x div 2,y div 2,z div 2)+e(1,x mod 2,y mod 2,z mod 2)*8^(n-1)

Раз пошел такой замес обобщу
d - измерения
v - вектор в d пространстве ( грубо массив координат v(d))
остальное как прежде
e(n,v)=e(n-1,v div r)+e(1,v mod r)*r^d(n-1)
можно я думаю обобщить для случая не равностороннего паттерна если это нужно

Ещё-бы придумать алгоритм генерации наиболее небанальных паттернов, для полной автоматизации. :)

А чем не устраивает Floyd-Steinberg dithering? Красивей же.

Не совсем по теме
просто оставлю это сдеся
тк прикольно и стабильно выглядит
http://3909.co/dev/od/img/Dither2-SplitCompare.gif
https://forums.tigsource.com/index.p...742#msg1363742

- - - Добавлено - - -

Как бы такого добиться
одной постобработкой...

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