1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
17  * All rights reserved.
18  */
19 
20 /** \file
21  * \ingroup bli
22  * \brief Jitter offset table
23  */
24 
25 #include "MEM_guardedalloc.h"
26 #include <math.h>
27 #include <string.h>
28 
29 #include "BLI_jitter_2d.h"
30 #include "BLI_rand.h"
31 
32 #include "BLI_strict_flags.h"
33 
BLI_jitterate1(float (* jit1)[2],float (* jit2)[2],int num,float radius1)34 void BLI_jitterate1(float (*jit1)[2], float (*jit2)[2], int num, float radius1)
35 {
36   int i, j, k;
37   float vecx, vecy, dvecx, dvecy, x, y, len;
38 
39   for (i = num - 1; i >= 0; i--) {
40     dvecx = dvecy = 0.0;
41     x = jit1[i][0];
42     y = jit1[i][1];
43     for (j = num - 1; j >= 0; j--) {
44       if (i != j) {
45         vecx = jit1[j][0] - x - 1.0f;
46         vecy = jit1[j][1] - y - 1.0f;
47         for (k = 3; k > 0; k--) {
48           if (fabsf(vecx) < radius1 && fabsf(vecy) < radius1) {
49             len = sqrtf(vecx * vecx + vecy * vecy);
50             if (len > 0 && len < radius1) {
51               len = len / radius1;
52               dvecx += vecx / len;
53               dvecy += vecy / len;
54             }
55           }
56           vecx += 1.0f;
57 
58           if (fabsf(vecx) < radius1 && fabsf(vecy) < radius1) {
59             len = sqrtf(vecx * vecx + vecy * vecy);
60             if (len > 0 && len < radius1) {
61               len = len / radius1;
62               dvecx += vecx / len;
63               dvecy += vecy / len;
64             }
65           }
66           vecx += 1.0f;
67 
68           if (fabsf(vecx) < radius1 && fabsf(vecy) < radius1) {
69             len = sqrtf(vecx * vecx + vecy * vecy);
70             if (len > 0 && len < radius1) {
71               len = len / radius1;
72               dvecx += vecx / len;
73               dvecy += vecy / len;
74             }
75           }
76           vecx -= 2.0f;
77           vecy += 1.0f;
78         }
79       }
80     }
81 
82     x -= dvecx / 18.0f;
83     y -= dvecy / 18.0f;
84     x -= floorf(x);
85     y -= floorf(y);
86     jit2[i][0] = x;
87     jit2[i][1] = y;
88   }
89   memcpy(jit1, jit2, 2 * (unsigned int)num * sizeof(float));
90 }
91 
BLI_jitterate2(float (* jit1)[2],float (* jit2)[2],int num,float radius2)92 void BLI_jitterate2(float (*jit1)[2], float (*jit2)[2], int num, float radius2)
93 {
94   int i, j;
95   float vecx, vecy, dvecx, dvecy, x, y;
96 
97   for (i = num - 1; i >= 0; i--) {
98     dvecx = dvecy = 0.0;
99     x = jit1[i][0];
100     y = jit1[i][1];
101     for (j = num - 1; j >= 0; j--) {
102       if (i != j) {
103         vecx = jit1[j][0] - x - 1.0f;
104         vecy = jit1[j][1] - y - 1.0f;
105 
106         if (fabsf(vecx) < radius2) {
107           dvecx += vecx * radius2;
108         }
109         vecx += 1.0f;
110         if (fabsf(vecx) < radius2) {
111           dvecx += vecx * radius2;
112         }
113         vecx += 1.0f;
114         if (fabsf(vecx) < radius2) {
115           dvecx += vecx * radius2;
116         }
117 
118         if (fabsf(vecy) < radius2) {
119           dvecy += vecy * radius2;
120         }
121         vecy += 1.0f;
122         if (fabsf(vecy) < radius2) {
123           dvecy += vecy * radius2;
124         }
125         vecy += 1.0f;
126         if (fabsf(vecy) < radius2) {
127           dvecy += vecy * radius2;
128         }
129       }
130     }
131 
132     x -= dvecx / 2.0f;
133     y -= dvecy / 2.0f;
134     x -= floorf(x);
135     y -= floorf(y);
136     jit2[i][0] = x;
137     jit2[i][1] = y;
138   }
139   memcpy(jit1, jit2, (unsigned int)num * sizeof(float[2]));
140 }
141 
BLI_jitter_init(float (* jitarr)[2],int num)142 void BLI_jitter_init(float (*jitarr)[2], int num)
143 {
144   float(*jit2)[2];
145   float num_fl, num_fl_sqrt;
146   float x, rad1, rad2, rad3;
147   RNG *rng;
148   int i;
149 
150   if (num == 0) {
151     return;
152   }
153 
154   num_fl = (float)num;
155   num_fl_sqrt = sqrtf(num_fl);
156 
157   jit2 = MEM_mallocN(12 + (unsigned int)num * sizeof(float[2]), "initjit");
158   rad1 = 1.0f / num_fl_sqrt;
159   rad2 = 1.0f / num_fl;
160   rad3 = num_fl_sqrt / num_fl;
161 
162   rng = BLI_rng_new(31415926 + (unsigned int)num);
163 
164   x = 0;
165   for (i = 0; i < num; i++) {
166     jitarr[i][0] = x + rad1 * (float)(0.5 - BLI_rng_get_double(rng));
167     jitarr[i][1] = (float)i / num_fl + rad1 * (float)(0.5 - BLI_rng_get_double(rng));
168     x += rad3;
169     x -= floorf(x);
170   }
171 
172   BLI_rng_free(rng);
173 
174   for (i = 0; i < 24; i++) {
175     BLI_jitterate1(jitarr, jit2, num, rad1);
176     BLI_jitterate1(jitarr, jit2, num, rad1);
177     BLI_jitterate2(jitarr, jit2, num, rad2);
178   }
179 
180   MEM_freeN(jit2);
181 
182   /* finally, move jittertab to be centered around (0, 0) */
183   for (i = 0; i < num; i++) {
184     jitarr[i][0] -= 0.5f;
185     jitarr[i][1] -= 0.5f;
186   }
187 }
188