Vos retours sur mon algo Diamant-Carré pour création de monde

**der§en** · 23/09/2021, 15h24

Bonjour,

Je suis preneur de vos critiques et/ou suggestions sur mon algo personnalisé du Diamant-Carré pour créer des mondes.

L'idée c'est de créer des images qui pourraient être plaquées sur une sphère en 3D.

Ce code est la juste pour le fun, rien de commercial derrière.

Nom : Heightmap.png
Affichages : 135
Taille : 252,2 Ko

Voici la routine de base :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
 
procedure TForm1.Button4Click(Sender: TObject);
const
  LX = 1024;
  MX = 512;
  DX = 32;
  LY = 512;
var
  x, y, z, n, bloc: integer;
  tg, td, th, tb, tf: TPoint;
  hmap: array[0..LY, 0..LX - 1] of byte;
begin
  // Défini de façon aléatoire le niveau par défaut du monde.
  n := Random(256);
 
  // Initialise la carte de hauteur avec le niveau par défaut.
  for y := 0 to high(hmap) do
    for x := 0 to high(hmap[y]) do
      hmap[y, x] := n;
 
  // Initialise les 4 points du départ de l'algo Diamant-Carré.
  hmap[0, 0]   := Random(256);
  hmap[0, MX]  := Random(256);
  hmap[LY, 0]  := Random(256);
  hmap[LY, MX] := Random(256);
 
  // La taille du bloc de départ correspond a la maitié de la largeur du monde.
  bloc := MX;
 
  // Algo Diamant-Carré.
  while bloc > 1 do
  begin
    z := bloc div 2;
 
    // Boucle du carré
    y := z;
    while y < LY do
    begin
      x := z;
 
      while x < LX do
      begin
        {
           G-----D
           |     |
           |  F  |
           |     |
           H-----B
        }
 
        tf := ControlePosition(y, x);
        tg := ControlePosition(y - z, x - z);
        td := ControlePosition(y - z, x + z);
        th := ControlePosition(y + z, x - z);
        tb := ControlePosition(y + z, x + z);
 
        hmap[tf.Y, tf.X] := Limitation(((hmap[tg.Y, tg.X] + hmap[td.Y, td.X] + hmap[th.Y, th.X] + hmap[tb.Y, tb.X]) div 4) + Randomrange(-z, z));
 
        Inc(x, bloc);
      end;
 
      Inc(y, bloc);
    end;
 
    // Boucle du diamant
    y := z;
    while y < LY do
    begin
      x := z;
 
      while x < LX do
      begin
        {
           / H \
          /     \
         G   F   D
          \     /
           \ B /
        }
 
        // 1 - Début
        tf := ControlePosition(y, x - z);
        tg := ControlePosition(y, x - bloc);
        td := ControlePosition(y, x);
        th := ControlePosition(y - z, x - z);
        tb := ControlePosition(y + z, x - z);
 
        hmap[tf.Y, tf.X] := Limitation(((hmap[tg.Y, tg.X] + hmap[td.Y, td.X] + hmap[th.Y, th.X] + hmap[tb.Y, tb.X]) div 4) + Randomrange(-z, z));
        // 1 - Fin
 
        //2 - Début
        tf := ControlePosition(y - z, x);
        tg := ControlePosition(y - z, x - z);
        td := ControlePosition(y - z, x + z);
        th := ControlePosition(y - bloc, x);
        tb := ControlePosition(y, x);
 
        hmap[tf.Y, tf.X] := Limitation(((hmap[tg.Y, tg.X] + hmap[td.Y, td.X] + hmap[th.Y, th.X] + hmap[tb.Y, tb.X]) div 4) + Randomrange(-z, z));
        // 2 - Fin
 
        Inc(x, bloc);
      end;
 
      Inc(y, bloc);
    end;
 
    bloc := z;
  end;
end;

La routine qui m'assure de la cohérence des coordonnées :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
 
function TForm1.ControlePosition(const y, x: integer): TPoint;
begin
  Result.Y := y;
  Result.X := (LX + x) mod LX;
 
  if Result.Y < 0 then
  begin
    Result.Y := ABS(y);
    Result.X := (LX + (LX - x)) mod LX;
  end;
 
  if Result.Y > LY then
  begin
    Result.Y := (LY - (y - LY));
    Result.X := (LX + (LX - x)) mod LX;
  end;
end;

La routine qui m'assure que je reste bien dans les limites de ma palette de couleurs :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
 
function TForm1.Limitation(const AValue: integer): byte;
begin
  Result := Max(Min(AValue, 255), 0);
end;

J'ai ausi créé une routine de lissage :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
procedure TForm1.LissageCarte;
var
  x, y, z: integer;
  P1, P2, P3, P4, P5, P6, P7, P8, P9: TPoint;
begin
  for y := 0 to high(hmap) do
    for x := 0 to high(hmap[y]) do
    begin
      P1 := ControlePosition(y - 1, x - 1);
      P2 := ControlePosition(y - 1, x);
      P3 := ControlePosition(y - 1, x + 1);
      P4 := ControlePosition(y, x - 1);
      P5 := ControlePosition(y, x);
      P6 := ControlePosition(y, x + 1);
      P7 := ControlePosition(y + 1, x - 1);
      P8 := ControlePosition(y + 1, x);
      P9 := ControlePosition(y + 1, x + 1);
 
      z := (hmap[P1.Y, P1.X] + hmap[P2.Y, P2.X] + hmap[P3.Y, P3.X] + hmap[P4.Y, P4.X] + hmap[P5.Y, P5.X] + hmap[P6.Y, P6.X] + hmap[P7.Y, P7.X] + hmap[P8.Y, P8.X] + hmap[P9.Y, P9.X]) div 9;
 
      hmap[y, x] := Limitation(z);
    end;
end;

Merci d'avance de vos participations pour améliorer les routines ou bien pour les optimiser !

**BeanzMaster** · 23/09/2021, 17h31

Salut

Mis a part précalculer dans les boucles certaines valeurs qui se répètent comme y - z, x - z, y - 1, y + 1, ect... et d'intégrer ta fonction controlposition directement dans tes boucles.
Remplacer ton div 4 par un shr 2. Et enfin choisir un meilleur algo de lissage, je ne vois d'autres choses dans l'immédiat.

Ton algo est très similaire à ce que l'on avais déja discuté ici

A+
Jérôme

**der§en** · 24/09/2021, 07h14

Envoyé par BeanzMaster

Salut

Mis a part précalculer dans les boucles certaines valeurs qui se répètent comme y - z, x - z, y - 1, y + 1, ect... et d'intégrer ta fonction controlposition directement dans tes boucles.
Remplacer ton div 4 par un shr 2. Et enfin choisir un meilleur algo de lissage, je ne vois d'autres choses dans l'immédiat.

Ton algo est très similaire à ce que l'on avais déja discuté ici

A+
Jérôme

Merci de tes retours.

Oui, cela fait suite à une discussion antérieure, mais que veux-tu à chacun ces petites marottes

Je retient, de prendre en compte l’idée dès pré calculer.

par contre, je ne vois pas trop l’intérêt d’intégrer le code de la fonction ControlePosition dans les boucle à part le fait d’alourdir la lecture du code ?

Tu penses qu’un SHR 2 est plus optimisé qu’un DIV 4 de nos jours ?

Coté lissage, as-tu une meilleure routine/algo ?

**BeanzMaster** · 24/09/2021, 19h58

Salut

Envoyé par der§en

Merci de tes retours.

Avec plaisir

Envoyé par der§en

par contre, je ne vois pas trop l’intérêt d’intégrer le code de la fonction ControlePosition dans les boucle à part le fait d’alourdir la lecture du code ?

C'est une question de porté. Le fait de mettre la fonction ControlePosition, et limitation dans ta fonction principale, te feras gagner quelques millisecondes. Car les appels a celles-ci sont moins éloignées. Surtout quelles sont appelées de nombreuses fois. Après mettre ces vérifications dans le code, certes va alourdir la lecture du code, mais te fera gagner en performance. Faudrait juste revoir la façon dont sont gérer les bornes.

Envoyé par der§en

Tu penses qu’un SHR 2 est plus optimisé qu’un DIV 4 de nos jours ?

Oui une DIV reste toujours plus couteux en cycle cpu qu'un shr et la aussi le fait que c'est appelé de nombreuses fois, au final te fera gagner quelques millisecondes. C'est pour cela que dans mon code j'utilises des "float" ce qui me permet de me remplacer la division par une multiplication qui est plus rapide. (car mon code utilises les instructions SSE) dans l'exemple sur l'autre topic, la génération et l'affichage est quasi instantané en 512x512 (mais je n'ai pas de controlPosition) faudrait faire un programme de bench pour mesurer efficacement.

Envoyé par der§en

Coté lissage, as-tu une meilleure routine/algo ?

Oui il existe, de meilleurs algos, plus rapide et meilleurs, et plus rapide avec une qualité moindre. Ici la seul optimisation est de diviser par 8 (shr 3) au lieu de 9 sans prendre en compte le pixel central (le flou sera un légèrement moins précis)

Sinon, tu peux jeter un oeil ici et la

Une autre optimisation possible serait peut de passer par un tableau 1D, ou un tableau de PByte.

Ta fonction limitation peux également être optimisée, en la remplaçant par ça (à toi de voir si tu veux utiliser l'ASM, qui est un poil meilleur en terme de perf) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
{$IFNDEF NO_ASM_OPTIMIZATIONS}
function ClampByte(Const Value : Integer) : Byte; assembler; nostackframe;
asm
{$IFDEF CPU64}
  {$IFDEF UNIX}
     MOV     EAX,EDI
  {$ELSE}
     // in win x64 calling convention parameters are passed in ECX, EDX, R8 & R9
     MOV     EAX,ECX
  {$ENDIF}
{$ENDIF}
        TEST    EAX,$FFFFFF00
        JNZ     @above
        RET
@above:
        JS      @below
        MOV     EAX,$FF
        RET
@Below:     XOR     EAX,EAX
end;
{$ELSE}
function ClampByte(const Value: Integer): Byte; inline;
begin
 Result := Value;
 if Value > 255 then Result := 255
 else if Value < 0 then Result := 0;
end;
{$ENDIF}

A+
Jérôme

**der§en** · 24/09/2021, 21h32

Tu es grand

je vais remplacer les DIV par des SHR, faire le SHR 3 au lieu du div 9, intégrer les 2 routines dans ma procédure peut-être avec un ‘inline;’ en plus.

Pour le lissage, selon toi, quel est l’algorithme qui donne le meilleur rendu ?

**BeanzMaster** · 25/09/2021, 09h24

Envoyé par der§en

Tu es grand

je vais remplacer les DIV par des SHR, faire le SHR 3 au lieu du div 9, intégrer les 2 routines dans ma procédure peut-être avec un ‘inline;’ en plus.

Pour le lissage, selon toi, quel est l’algorithme qui donne le meilleur rendu ?

Parmi les algos de lissage de mes sources, les meilleurs dans ce cas de figure serait le GaussianBoxBlur rapide et de qualité (équivalent à photoshop) et le ThresholdBlur. L' AverageBlur pourrait faire l'affaire aussi, en terme de résultat, il ressemblerait presque au ton algo en un peu mieux en qualité et en terme de perf il doit être pratiquement semblable.
L'avantage de ces algos, c'est que tu peux contrôler la force du lissage. Ils sont surement un peu moins performant que ton algo car plus complexe, mais fourniront une meilleur qualité.

Si tu comptes créer tes textures en temps réel, dans ce cas mieux vaut se tourner vers les algos LinearBlur et FastBlur mais là tu ne peux pas contrôler le taux de lissage. Le FXAABlur donne des résultats pas mal surtout sur les "edge" et est assez performant en terme de vitesse (mais beaucoup moins que les deux précèdent).

A+
Jérôme

Vos retours sur mon algo Diamant-Carré pour création de monde

Lazarus Pascal

Discussions similaires

Partager

Partager