Cleanup: remove redundant doxygen \file argument
[blender.git] / source / blender / blenlib / intern / noise.c
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 \ingroup bli
21  */
22
23 #include <math.h>
24
25 #include "BLI_noise.h"
26
27 /* local */
28 static float noise3_perlin(float vec[3]);
29 //static float turbulence_perlin(const float point[3], float lofreq, float hifreq);
30 //static float turbulencep(float noisesize, float x, float y, float z, int nr);
31
32 /* UNUSED */
33 // #define HASHVEC(x, y, z) hashvectf + 3 * hash[(hash[(hash[(z) & 255] + (y)) & 255] + (x)) & 255]
34
35 /* needed for voronoi */
36 #define HASHPNT(x, y, z) hashpntf + 3 * hash[(hash[(hash[(z) & 255] + (y)) & 255] + (x)) & 255]
37 static const float hashpntf[768] = {
38         0.536902, 0.020915, 0.501445, 0.216316, 0.517036, 0.822466, 0.965315,
39         0.377313, 0.678764, 0.744545, 0.097731, 0.396357, 0.247202, 0.520897,
40         0.613396, 0.542124, 0.146813, 0.255489, 0.810868, 0.638641, 0.980742,
41         0.292316, 0.357948, 0.114382, 0.861377, 0.629634, 0.722530, 0.714103,
42         0.048549, 0.075668, 0.564920, 0.162026, 0.054466, 0.411738, 0.156897,
43         0.887657, 0.599368, 0.074249, 0.170277, 0.225799, 0.393154, 0.301348,
44         0.057434, 0.293849, 0.442745, 0.150002, 0.398732, 0.184582, 0.915200,
45         0.630984, 0.974040, 0.117228, 0.795520, 0.763238, 0.158982, 0.616211,
46         0.250825, 0.906539, 0.316874, 0.676205, 0.234720, 0.667673, 0.792225,
47         0.273671, 0.119363, 0.199131, 0.856716, 0.828554, 0.900718, 0.705960,
48         0.635923, 0.989433, 0.027261, 0.283507, 0.113426, 0.388115, 0.900176,
49         0.637741, 0.438802, 0.715490, 0.043692, 0.202640, 0.378325, 0.450325,
50         0.471832, 0.147803, 0.906899, 0.524178, 0.784981, 0.051483, 0.893369,
51         0.596895, 0.275635, 0.391483, 0.844673, 0.103061, 0.257322, 0.708390,
52         0.504091, 0.199517, 0.660339, 0.376071, 0.038880, 0.531293, 0.216116,
53         0.138672, 0.907737, 0.807994, 0.659582, 0.915264, 0.449075, 0.627128,
54         0.480173, 0.380942, 0.018843, 0.211808, 0.569701, 0.082294, 0.689488,
55         0.573060, 0.593859, 0.216080, 0.373159, 0.108117, 0.595539, 0.021768,
56         0.380297, 0.948125, 0.377833, 0.319699, 0.315249, 0.972805, 0.792270,
57         0.445396, 0.845323, 0.372186, 0.096147, 0.689405, 0.423958, 0.055675,
58         0.117940, 0.328456, 0.605808, 0.631768, 0.372170, 0.213723, 0.032700,
59         0.447257, 0.440661, 0.728488, 0.299853, 0.148599, 0.649212, 0.498381,
60         0.049921, 0.496112, 0.607142, 0.562595, 0.990246, 0.739659, 0.108633,
61         0.978156, 0.209814, 0.258436, 0.876021, 0.309260, 0.600673, 0.713597,
62         0.576967, 0.641402, 0.853930, 0.029173, 0.418111, 0.581593, 0.008394,
63         0.589904, 0.661574, 0.979326, 0.275724, 0.111109, 0.440472, 0.120839,
64         0.521602, 0.648308, 0.284575, 0.204501, 0.153286, 0.822444, 0.300786,
65         0.303906, 0.364717, 0.209038, 0.916831, 0.900245, 0.600685, 0.890002,
66         0.581660, 0.431154, 0.705569, 0.551250, 0.417075, 0.403749, 0.696652,
67         0.292652, 0.911372, 0.690922, 0.323718, 0.036773, 0.258976, 0.274265,
68         0.225076, 0.628965, 0.351644, 0.065158, 0.080340, 0.467271, 0.130643,
69         0.385914, 0.919315, 0.253821, 0.966163, 0.017439, 0.392610, 0.478792,
70         0.978185, 0.072691, 0.982009, 0.097987, 0.731533, 0.401233, 0.107570,
71         0.349587, 0.479122, 0.700598, 0.481751, 0.788429, 0.706864, 0.120086,
72         0.562691, 0.981797, 0.001223, 0.192120, 0.451543, 0.173092, 0.108960,
73         0.549594, 0.587892, 0.657534, 0.396365, 0.125153, 0.666420, 0.385823,
74         0.890916, 0.436729, 0.128114, 0.369598, 0.759096, 0.044677, 0.904752,
75         0.088052, 0.621148, 0.005047, 0.452331, 0.162032, 0.494238, 0.523349,
76         0.741829, 0.698450, 0.452316, 0.563487, 0.819776, 0.492160, 0.004210,
77         0.647158, 0.551475, 0.362995, 0.177937, 0.814722, 0.727729, 0.867126,
78         0.997157, 0.108149, 0.085726, 0.796024, 0.665075, 0.362462, 0.323124,
79         0.043718, 0.042357, 0.315030, 0.328954, 0.870845, 0.683186, 0.467922,
80         0.514894, 0.809971, 0.631979, 0.176571, 0.366320, 0.850621, 0.505555,
81         0.749551, 0.750830, 0.401714, 0.481216, 0.438393, 0.508832, 0.867971,
82         0.654581, 0.058204, 0.566454, 0.084124, 0.548539, 0.902690, 0.779571,
83         0.562058, 0.048082, 0.863109, 0.079290, 0.713559, 0.783496, 0.265266,
84         0.672089, 0.786939, 0.143048, 0.086196, 0.876129, 0.408708, 0.229312,
85         0.629995, 0.206665, 0.207308, 0.710079, 0.341704, 0.264921, 0.028748,
86         0.629222, 0.470173, 0.726228, 0.125243, 0.328249, 0.794187, 0.741340,
87         0.489895, 0.189396, 0.724654, 0.092841, 0.039809, 0.860126, 0.247701,
88         0.655331, 0.964121, 0.672536, 0.044522, 0.690567, 0.837238, 0.631520,
89         0.953734, 0.352484, 0.289026, 0.034152, 0.852575, 0.098454, 0.795529,
90         0.452181, 0.826159, 0.186993, 0.820725, 0.440328, 0.922137, 0.704592,
91         0.915437, 0.738183, 0.733461, 0.193798, 0.929213, 0.161390, 0.318547,
92         0.888751, 0.430968, 0.740837, 0.193544, 0.872253, 0.563074, 0.274598,
93         0.347805, 0.666176, 0.449831, 0.800991, 0.588727, 0.052296, 0.714761,
94         0.420620, 0.570325, 0.057550, 0.210888, 0.407312, 0.662848, 0.924382,
95         0.895958, 0.775198, 0.688605, 0.025721, 0.301913, 0.791408, 0.500602,
96         0.831984, 0.828509, 0.642093, 0.494174, 0.525880, 0.446365, 0.440063,
97         0.763114, 0.630358, 0.223943, 0.333806, 0.906033, 0.498306, 0.241278,
98         0.427640, 0.772683, 0.198082, 0.225379, 0.503894, 0.436599, 0.016503,
99         0.803725, 0.189878, 0.291095, 0.499114, 0.151573, 0.079031, 0.904618,
100         0.708535, 0.273900, 0.067419, 0.317124, 0.936499, 0.716511, 0.543845,
101         0.939909, 0.826574, 0.715090, 0.154864, 0.750150, 0.845808, 0.648108,
102         0.556564, 0.644757, 0.140873, 0.799167, 0.632989, 0.444245, 0.471978,
103         0.435910, 0.359793, 0.216241, 0.007633, 0.337236, 0.857863, 0.380247,
104         0.092517, 0.799973, 0.919000, 0.296798, 0.096989, 0.854831, 0.165369,
105         0.568475, 0.216855, 0.020457, 0.835511, 0.538039, 0.999742, 0.620226,
106         0.244053, 0.060399, 0.323007, 0.294874, 0.988899, 0.384919, 0.735655,
107         0.773428, 0.549776, 0.292882, 0.660611, 0.593507, 0.621118, 0.175269,
108         0.682119, 0.794493, 0.868197, 0.632150, 0.807823, 0.509656, 0.482035,
109         0.001780, 0.259126, 0.358002, 0.280263, 0.192985, 0.290367, 0.208111,
110         0.917633, 0.114422, 0.925491, 0.981110, 0.255570, 0.974862, 0.016629,
111         0.552599, 0.575741, 0.612978, 0.615965, 0.803615, 0.772334, 0.089745,
112         0.838812, 0.634542, 0.113709, 0.755832, 0.577589, 0.667489, 0.529834,
113         0.325660, 0.817597, 0.316557, 0.335093, 0.737363, 0.260951, 0.737073,
114         0.049540, 0.735541, 0.988891, 0.299116, 0.147695, 0.417271, 0.940811,
115         0.524160, 0.857968, 0.176403, 0.244835, 0.485759, 0.033353, 0.280319,
116         0.750688, 0.755809, 0.924208, 0.095956, 0.962504, 0.275584, 0.173715,
117         0.942716, 0.706721, 0.078464, 0.576716, 0.804667, 0.559249, 0.900611,
118         0.646904, 0.432111, 0.927885, 0.383277, 0.269973, 0.114244, 0.574867,
119         0.150703, 0.241855, 0.272871, 0.199950, 0.079719, 0.868566, 0.962833,
120         0.789122, 0.320025, 0.905554, 0.234876, 0.991356, 0.061913, 0.732911,
121         0.785960, 0.874074, 0.069035, 0.658632, 0.309901, 0.023676, 0.791603,
122         0.764661, 0.661278, 0.319583, 0.829650, 0.117091, 0.903124, 0.982098,
123         0.161631, 0.193576, 0.670428, 0.857390, 0.003760, 0.572578, 0.222162,
124         0.114551, 0.420118, 0.530404, 0.470682, 0.525527, 0.764281, 0.040596,
125         0.443275, 0.501124, 0.816161, 0.417467, 0.332172, 0.447565, 0.614591,
126         0.559246, 0.805295, 0.226342, 0.155065, 0.714630, 0.160925, 0.760001,
127         0.453456, 0.093869, 0.406092, 0.264801, 0.720370, 0.743388, 0.373269,
128         0.403098, 0.911923, 0.897249, 0.147038, 0.753037, 0.516093, 0.739257,
129         0.175018, 0.045768, 0.735857, 0.801330, 0.927708, 0.240977, 0.591870,
130         0.921831, 0.540733, 0.149100, 0.423152, 0.806876, 0.397081, 0.061100,
131         0.811630, 0.044899, 0.460915, 0.961202, 0.822098, 0.971524, 0.867608,
132         0.773604, 0.226616, 0.686286, 0.926972, 0.411613, 0.267873, 0.081937,
133         0.226124, 0.295664, 0.374594, 0.533240, 0.237876, 0.669629, 0.599083,
134         0.513081, 0.878719, 0.201577, 0.721296, 0.495038, 0.079760, 0.965959,
135         0.233090, 0.052496, 0.714748, 0.887844, 0.308724, 0.972885, 0.723337,
136         0.453089, 0.914474, 0.704063, 0.823198, 0.834769, 0.906561, 0.919600,
137         0.100601, 0.307564, 0.901977, 0.468879, 0.265376, 0.885188, 0.683875,
138         0.868623, 0.081032, 0.466835, 0.199087, 0.663437, 0.812241, 0.311337,
139         0.821361, 0.356628, 0.898054, 0.160781, 0.222539, 0.714889, 0.490287,
140         0.984915, 0.951755, 0.964097, 0.641795, 0.815472, 0.852732, 0.862074,
141         0.051108, 0.440139, 0.323207, 0.517171, 0.562984, 0.115295, 0.743103,
142         0.977914, 0.337596, 0.440694, 0.535879, 0.959427, 0.351427, 0.704361,
143         0.010826, 0.131162, 0.577080, 0.349572, 0.774892, 0.425796, 0.072697,
144         0.500001, 0.267322, 0.909654, 0.206176, 0.223987, 0.937698, 0.323423,
145         0.117501, 0.490308, 0.474372, 0.689943, 0.168671, 0.719417, 0.188928,
146         0.330464, 0.265273, 0.446271, 0.171933, 0.176133, 0.474616, 0.140182,
147         0.114246, 0.905043, 0.713870, 0.555261, 0.951333,
148 };
149
150 const unsigned char hash[512] = {
151         0xA2, 0xA0, 0x19, 0x3B, 0xF8, 0xEB, 0xAA, 0xEE, 0xF3, 0x1C, 0x67, 0x28, 0x1D, 0xED, 0x0,  0xDE, 0x95, 0x2E, 0xDC,
152         0x3F, 0x3A, 0x82, 0x35, 0x4D, 0x6C, 0xBA, 0x36, 0xD0, 0xF6, 0xC,  0x79, 0x32, 0xD1, 0x59, 0xF4, 0x8,  0x8B, 0x63,
153         0x89, 0x2F, 0xB8, 0xB4, 0x97, 0x83, 0xF2, 0x8F, 0x18, 0xC7, 0x51, 0x14, 0x65, 0x87, 0x48, 0x20, 0x42, 0xA8, 0x80,
154         0xB5, 0x40, 0x13, 0xB2, 0x22, 0x7E, 0x57, 0xBC, 0x7F, 0x6B, 0x9D, 0x86, 0x4C, 0xC8, 0xDB, 0x7C, 0xD5, 0x25, 0x4E,
155         0x5A, 0x55, 0x74, 0x50, 0xCD, 0xB3, 0x7A, 0xBB, 0xC3, 0xCB, 0xB6, 0xE2, 0xE4, 0xEC, 0xFD, 0x98, 0xB,  0x96, 0xD3,
156         0x9E, 0x5C, 0xA1, 0x64, 0xF1, 0x81, 0x61, 0xE1, 0xC4, 0x24, 0x72, 0x49, 0x8C, 0x90, 0x4B, 0x84, 0x34, 0x38, 0xAB,
157         0x78, 0xCA, 0x1F, 0x1,  0xD7, 0x93, 0x11, 0xC1, 0x58, 0xA9, 0x31, 0xF9, 0x44, 0x6D, 0xBF, 0x33, 0x9C, 0x5F, 0x9,
158         0x94, 0xA3, 0x85, 0x6,  0xC6, 0x9A, 0x1E, 0x7B, 0x46, 0x15, 0x30, 0x27, 0x2B, 0x1B, 0x71, 0x3C, 0x5B, 0xD6, 0x6F,
159         0x62, 0xAC, 0x4F, 0xC2, 0xC0, 0xE,  0xB1, 0x23, 0xA7, 0xDF, 0x47, 0xB0, 0x77, 0x69, 0x5,  0xE9, 0xE6, 0xE7, 0x76,
160         0x73, 0xF,  0xFE, 0x6E, 0x9B, 0x56, 0xEF, 0x12, 0xA5, 0x37, 0xFC, 0xAE, 0xD9, 0x3,  0x8E, 0xDD, 0x10, 0xB9, 0xCE,
161         0xC9, 0x8D, 0xDA, 0x2A, 0xBD, 0x68, 0x17, 0x9F, 0xBE, 0xD4, 0xA,  0xCC, 0xD2, 0xE8, 0x43, 0x3D, 0x70, 0xB7, 0x2,
162         0x7D, 0x99, 0xD8, 0xD,  0x60, 0x8A, 0x4,  0x2C, 0x3E, 0x92, 0xE5, 0xAF, 0x53, 0x7,  0xE0, 0x29, 0xA6, 0xC5, 0xE3,
163         0xF5, 0xF7, 0x4A, 0x41, 0x26, 0x6A, 0x16, 0x5E, 0x52, 0x2D, 0x21, 0xAD, 0xF0, 0x91, 0xFF, 0xEA, 0x54, 0xFA, 0x66,
164         0x1A, 0x45, 0x39, 0xCF, 0x75, 0xA4, 0x88, 0xFB, 0x5D, 0xA2, 0xA0, 0x19, 0x3B, 0xF8, 0xEB, 0xAA, 0xEE, 0xF3, 0x1C,
165         0x67, 0x28, 0x1D, 0xED, 0x0,  0xDE, 0x95, 0x2E, 0xDC, 0x3F, 0x3A, 0x82, 0x35, 0x4D, 0x6C, 0xBA, 0x36, 0xD0, 0xF6,
166         0xC,  0x79, 0x32, 0xD1, 0x59, 0xF4, 0x8,  0x8B, 0x63, 0x89, 0x2F, 0xB8, 0xB4, 0x97, 0x83, 0xF2, 0x8F, 0x18, 0xC7,
167         0x51, 0x14, 0x65, 0x87, 0x48, 0x20, 0x42, 0xA8, 0x80, 0xB5, 0x40, 0x13, 0xB2, 0x22, 0x7E, 0x57, 0xBC, 0x7F, 0x6B,
168         0x9D, 0x86, 0x4C, 0xC8, 0xDB, 0x7C, 0xD5, 0x25, 0x4E, 0x5A, 0x55, 0x74, 0x50, 0xCD, 0xB3, 0x7A, 0xBB, 0xC3, 0xCB,
169         0xB6, 0xE2, 0xE4, 0xEC, 0xFD, 0x98, 0xB,  0x96, 0xD3, 0x9E, 0x5C, 0xA1, 0x64, 0xF1, 0x81, 0x61, 0xE1, 0xC4, 0x24,
170         0x72, 0x49, 0x8C, 0x90, 0x4B, 0x84, 0x34, 0x38, 0xAB, 0x78, 0xCA, 0x1F, 0x1,  0xD7, 0x93, 0x11, 0xC1, 0x58, 0xA9,
171         0x31, 0xF9, 0x44, 0x6D, 0xBF, 0x33, 0x9C, 0x5F, 0x9,  0x94, 0xA3, 0x85, 0x6,  0xC6, 0x9A, 0x1E, 0x7B, 0x46, 0x15,
172         0x30, 0x27, 0x2B, 0x1B, 0x71, 0x3C, 0x5B, 0xD6, 0x6F, 0x62, 0xAC, 0x4F, 0xC2, 0xC0, 0xE,  0xB1, 0x23, 0xA7, 0xDF,
173         0x47, 0xB0, 0x77, 0x69, 0x5,  0xE9, 0xE6, 0xE7, 0x76, 0x73, 0xF,  0xFE, 0x6E, 0x9B, 0x56, 0xEF, 0x12, 0xA5, 0x37,
174         0xFC, 0xAE, 0xD9, 0x3,  0x8E, 0xDD, 0x10, 0xB9, 0xCE, 0xC9, 0x8D, 0xDA, 0x2A, 0xBD, 0x68, 0x17, 0x9F, 0xBE, 0xD4,
175         0xA,  0xCC, 0xD2, 0xE8, 0x43, 0x3D, 0x70, 0xB7, 0x2,  0x7D, 0x99, 0xD8, 0xD,  0x60, 0x8A, 0x4,  0x2C, 0x3E, 0x92,
176         0xE5, 0xAF, 0x53, 0x7,  0xE0, 0x29, 0xA6, 0xC5, 0xE3, 0xF5, 0xF7, 0x4A, 0x41, 0x26, 0x6A, 0x16, 0x5E, 0x52, 0x2D,
177         0x21, 0xAD, 0xF0, 0x91, 0xFF, 0xEA, 0x54, 0xFA, 0x66, 0x1A, 0x45, 0x39, 0xCF, 0x75, 0xA4, 0x88, 0xFB, 0x5D,
178 };
179
180
181 static const float hashvectf[768] = {
182         0.33783, 0.715698, -0.611206, -0.944031, -0.326599, -0.045624, -0.101074, -0.416443, -0.903503, 0.799286, 0.49411,
183         -0.341949, -0.854645, 0.518036, 0.033936, 0.42514, -0.437866, -0.792114, -0.358948, 0.597046, 0.717377, -0.985413,
184         0.144714, 0.089294, -0.601776, -0.33728, -0.723907, -0.449921, 0.594513, 0.666382, 0.208313, -0.10791, 0.972076,
185         0.575317, 0.060425, 0.815643, 0.293365, -0.875702, -0.383453, 0.293762, 0.465759, 0.834686, -0.846008, -0.233398,
186         -0.47934, -0.115814, 0.143036, -0.98291, 0.204681, -0.949036, -0.239532, 0.946716, -0.263947, 0.184326, -0.235596,
187         0.573822, 0.784332, 0.203705, -0.372253, -0.905487, 0.756989, -0.651031, 0.055298, 0.497803, 0.814697, -0.297363,
188         -0.16214, 0.063995, -0.98468, -0.329254, 0.834381, 0.441925, 0.703827, -0.527039, -0.476227, 0.956421, 0.266113,
189         0.119781, 0.480133, 0.482849, 0.7323, -0.18631, 0.961212, -0.203125, -0.748474, -0.656921, -0.090393, -0.085052,
190         -0.165253, 0.982544, -0.76947, 0.628174, -0.115234, 0.383148, 0.537659, 0.751068, 0.616486, -0.668488, -0.415924,
191         -0.259979, -0.630005, 0.73175, 0.570953, -0.087952, 0.816223, -0.458008, 0.023254, 0.888611, -0.196167, 0.976563,
192         -0.088287, -0.263885, -0.69812, -0.665527, 0.437134, -0.892273, -0.112793, -0.621674, -0.230438, 0.748566, 0.232422,
193         0.900574, -0.367249, 0.22229, -0.796143, 0.562744, -0.665497, -0.73764, 0.11377, 0.670135, 0.704803, 0.232605,
194         0.895599, 0.429749, -0.114655, -0.11557, -0.474243, 0.872742, 0.621826, 0.604004, -0.498444, -0.832214, 0.012756,
195         0.55426, -0.702484, 0.705994, -0.089661, -0.692017, 0.649292, 0.315399, -0.175995, -0.977997, 0.111877, 0.096954,
196         -0.04953, 0.994019, 0.635284, -0.606689, -0.477783, -0.261261, -0.607422, -0.750153, 0.983276, 0.165436, 0.075958,
197         -0.29837, 0.404083, -0.864655, -0.638672, 0.507721, 0.578156, 0.388214, 0.412079, 0.824249, 0.556183, -0.208832,
198         0.804352, 0.778442, 0.562012, 0.27951, -0.616577, 0.781921, -0.091522, 0.196289, 0.051056, 0.979187, -0.121216,
199         0.207153, -0.970734, -0.173401, -0.384735, 0.906555, 0.161499, -0.723236, -0.671387, 0.178497, -0.006226, -0.983887,
200         -0.126038, 0.15799, 0.97934, 0.830475, -0.024811, 0.556458, -0.510132, -0.76944, 0.384247, 0.81424, 0.200104,
201         -0.544891, -0.112549, -0.393311, -0.912445, 0.56189, 0.152222, -0.813049, 0.198914, -0.254517, -0.946381, -0.41217,
202         0.690979, -0.593811, -0.407257, 0.324524, 0.853668, -0.690186, 0.366119, -0.624115, -0.428345, 0.844147, -0.322296,
203         -0.21228, -0.297546, -0.930756, -0.273071, 0.516113, 0.811798, 0.928314, 0.371643, 0.007233, 0.785828, -0.479218,
204         -0.390778, -0.704895, 0.058929, 0.706818, 0.173248, 0.203583, 0.963562, 0.422211, -0.904297, -0.062469, -0.363312,
205         -0.182465, 0.913605, 0.254028, -0.552307, -0.793945, -0.28891, -0.765747, -0.574554, 0.058319, 0.291382, 0.954803,
206         0.946136, -0.303925, 0.111267, -0.078156, 0.443695, -0.892731, 0.182098, 0.89389, 0.409515, -0.680298, -0.213318,
207         0.701141, 0.062469, 0.848389, -0.525635, -0.72879, -0.641846, 0.238342, -0.88089, 0.427673, 0.202637, -0.532501,
208         -0.21405, 0.818878, 0.948975, -0.305084, 0.07962, 0.925446, 0.374664, 0.055817, 0.820923, 0.565491, 0.079102,
209         0.25882, 0.099792, -0.960724, -0.294617, 0.910522, 0.289978, 0.137115, 0.320038, -0.937408, -0.908386, 0.345276,
210         -0.235718, -0.936218, 0.138763, 0.322754, 0.366577, 0.925934, -0.090637, 0.309296, -0.686829, -0.657684, 0.66983,
211         0.024445, 0.742065, -0.917999, -0.059113, -0.392059, 0.365509, 0.462158, -0.807922, 0.083374, 0.996399, -0.014801,
212         0.593842, 0.253143, -0.763672, 0.974976, -0.165466, 0.148285, 0.918976, 0.137299, 0.369537, 0.294952, 0.694977,
213         0.655731, 0.943085, 0.152618, -0.295319, 0.58783, -0.598236, 0.544495, 0.203796, 0.678223, 0.705994, -0.478821,
214         -0.661011, 0.577667, 0.719055, -0.1698, -0.673828, -0.132172, -0.965332, 0.225006, -0.981873, -0.14502, 0.121979,
215         0.763458, 0.579742, 0.284546, -0.893188, 0.079681, 0.442474, -0.795776, -0.523804, 0.303802, 0.734955, 0.67804,
216         -0.007446, 0.15506, 0.986267, -0.056183, 0.258026, 0.571503, -0.778931, -0.681549, -0.702087, -0.206116, -0.96286,
217         -0.177185, 0.203613, -0.470978, -0.515106, 0.716095, -0.740326, 0.57135, 0.354095, -0.56012, -0.824982, -0.074982,
218         -0.507874, 0.753204, 0.417969, -0.503113, 0.038147, 0.863342, 0.594025, 0.673553, -0.439758, -0.119873, -0.005524,
219         -0.992737, 0.098267, -0.213776, 0.971893, -0.615631, 0.643951, 0.454163, 0.896851, -0.441071, 0.032166, -0.555023,
220         0.750763, -0.358093, 0.398773, 0.304688, 0.864929, -0.722961, 0.303589, 0.620544, -0.63559, -0.621948, -0.457306,
221         -0.293243, 0.072327, 0.953278, -0.491638, 0.661041, -0.566772, -0.304199, -0.572083, -0.761688, 0.908081, -0.398956,
222         0.127014, -0.523621, -0.549683, -0.650848, -0.932922, -0.19986, 0.299408, 0.099426, 0.140869, 0.984985, -0.020325,
223         -0.999756, -0.002319, 0.952667, 0.280853, -0.11615, -0.971893, 0.082581, 0.220337, 0.65921, 0.705292, -0.260651,
224         0.733063, -0.175537, 0.657043, -0.555206, 0.429504, -0.712189, 0.400421, -0.89859, 0.179352, 0.750885, -0.19696,
225         0.630341, 0.785675, -0.569336, 0.241821, -0.058899, -0.464111, 0.883789, 0.129608, -0.94519, 0.299622, -0.357819,
226         0.907654, 0.219238, -0.842133, -0.439117, -0.312927, -0.313477, 0.84433, 0.434479, -0.241211, 0.053253, 0.968994,
227         0.063873, 0.823273, 0.563965, 0.476288, 0.862152, -0.172516, 0.620941, -0.298126, 0.724915, 0.25238, -0.749359,
228         -0.612122, -0.577545, 0.386566, 0.718994, -0.406342, -0.737976, 0.538696, 0.04718, 0.556305, 0.82959, -0.802856,
229         0.587463, 0.101166, -0.707733, -0.705963, 0.026428, 0.374908, 0.68457, 0.625092, 0.472137, 0.208405, -0.856506,
230         -0.703064, -0.581085, -0.409821, -0.417206, -0.736328, 0.532623, -0.447876, -0.20285, -0.870728, 0.086945,
231         -0.990417, 0.107086, 0.183685, 0.018341, -0.982788, 0.560638, -0.428864, 0.708282, 0.296722, -0.952576, -0.0672,
232         0.135773, 0.990265, 0.030243, -0.068787, 0.654724, 0.752686, 0.762604, -0.551758, 0.337585, -0.819611, -0.407684,
233         0.402466, -0.727844, -0.55072, -0.408539, -0.855774, -0.480011, 0.19281, 0.693176, -0.079285, 0.716339, 0.226013,
234         0.650116, -0.725433, 0.246704, 0.953369, -0.173553, -0.970398, -0.239227, -0.03244, 0.136383, -0.394318, 0.908752,
235         0.813232, 0.558167, 0.164368, 0.40451, 0.549042, -0.731323, -0.380249, -0.566711, 0.730865, 0.022156, 0.932739,
236         0.359741, 0.00824, 0.996552, -0.082306, 0.956635, -0.065338, -0.283722, -0.743561, 0.008209, 0.668579, -0.859589,
237         -0.509674, 0.035767, -0.852234, 0.363678, -0.375977, -0.201965, -0.970795, -0.12915, 0.313477, 0.947327, 0.06546,
238         -0.254028, -0.528259, 0.81015, 0.628052, 0.601105, 0.49411, -0.494385, 0.868378, 0.037933, 0.275635, -0.086426,
239         0.957336, -0.197937, 0.468903, -0.860748, 0.895599, 0.399384, 0.195801, 0.560791, 0.825012, -0.069214, 0.304199,
240         -0.849487, 0.43103, 0.096375, 0.93576, 0.339111, -0.051422, 0.408966, -0.911072, 0.330444, 0.942841, -0.042389,
241         -0.452362, -0.786407, 0.420563, 0.134308, -0.933472, -0.332489, 0.80191, -0.566711, -0.188934, -0.987946, -0.105988,
242         0.112518, -0.24408, 0.892242, -0.379791, -0.920502, 0.229095, -0.316376, 0.7789, 0.325958, 0.535706, -0.912872,
243         0.185211, -0.36377, -0.184784, 0.565369, -0.803833, -0.018463, 0.119537, 0.992615, -0.259247, -0.935608, 0.239532,
244         -0.82373, -0.449127, -0.345947, -0.433105, 0.659515, 0.614349, -0.822754, 0.378845, -0.423676, 0.687195, -0.674835,
245         -0.26889, -0.246582, -0.800842, 0.545715, -0.729187, -0.207794, 0.651978, 0.653534, -0.610443, -0.447388, 0.492584,
246         -0.023346, 0.869934, 0.609039, 0.009094, -0.79306, 0.962494, -0.271088, -0.00885, 0.2659, -0.004913, 0.963959,
247         0.651245, 0.553619, -0.518951, 0.280548, -0.84314, 0.458618, -0.175293, -0.983215, 0.049805, 0.035339, -0.979919,
248         0.196045, -0.982941, 0.164307, -0.082245, 0.233734, -0.97226, -0.005005, -0.747253, -0.611328, 0.260437, 0.645599,
249         0.592773, 0.481384, 0.117706, -0.949524, -0.29068, -0.535004, -0.791901, -0.294312, -0.627167, -0.214447, 0.748718,
250         -0.047974, -0.813477, -0.57959, -0.175537, 0.477264, -0.860992, 0.738556, -0.414246, -0.53183, 0.562561, -0.704071,
251         0.433289, -0.754944, 0.64801, -0.100586, 0.114716, 0.044525, -0.992371, 0.966003, 0.244873, -0.082764,
252 };
253
254 /**************************/
255 /*  IMPROVED PERLIN NOISE */
256 /**************************/
257
258 static float lerp(float t, float a, float b)
259 {
260         return (a + t * (b - a));
261 }
262
263 static float npfade(float t)
264 {
265         return (t * t * t * (t * (t * 6.0f - 15.0f) + 10.0f));
266 }
267
268 static float grad(int hash_val, float x, float y, float z)
269 {
270         int h = hash_val & 15;                 /* CONVERT LO 4 BITS OF HASH CODE */
271         float u = h < 8 ? x : y;               /* INTO 12 GRADIENT DIRECTIONS. */
272         float v = h < 4 ? y : h == 12 || h == 14 ? x : z;
273         return ((h & 1) == 0 ? u : -u) + ((h & 2) == 0 ? v : -v);
274 }
275
276 /* instead of adding another permutation array, just use hash table defined above */
277 static float newPerlin(float x, float y, float z)
278 {
279         int A, AA, AB, B, BA, BB;
280         float u = floor(x), v = floor(y), w = floor(z);
281         int X = ((int)u) & 255,
282                 Y = ((int)v) & 255,
283                 Z = ((int)w) & 255;   /* FIND UNIT CUBE THAT CONTAINS POINT */
284         x -= u;             /* FIND RELATIVE X,Y,Z */
285         y -= v;             /* OF POINT IN CUBE. */
286         z -= w;
287         u = npfade(x);      /* COMPUTE FADE CURVES */
288         v = npfade(y);      /* FOR EACH OF X,Y,Z. */
289         w = npfade(z);
290         A = hash[X    ] + Y;  AA = hash[A] + Z;  AB = hash[A + 1] + Z;      /* HASH COORDINATES OF */
291         B = hash[X + 1] + Y;  BA = hash[B] + Z;  BB = hash[B + 1] + Z;      /* THE 8 CUBE CORNERS, */
292         return lerp(w, lerp(v, lerp(u, grad(hash[AA   ],  x,     y,     z    ),   /* AND ADD */
293                                        grad(hash[BA   ],  x - 1, y,     z    )),  /* BLENDED */
294                                lerp(u, grad(hash[AB   ],  x,     y - 1, z    ),   /* RESULTS */
295                                        grad(hash[BB   ],  x - 1, y - 1, z    ))), /* FROM  8 */
296                        lerp(v, lerp(u, grad(hash[AA + 1], x,     y,     z - 1),   /* CORNERS */
297                                        grad(hash[BA + 1], x - 1, y,     z - 1)),  /* OF CUBE */
298                                lerp(u, grad(hash[AB + 1], x,     y - 1, z - 1),
299                                        grad(hash[BB + 1], x - 1, y - 1, z - 1))));
300 }
301
302 /* for use with BLI_gNoise()/BLI_gTurbulence(), returns unsigned improved perlin noise */
303 static float newPerlinU(float x, float y, float z)
304 {
305         return (0.5f + 0.5f * newPerlin(x, y, z));
306 }
307
308
309 /**************************/
310 /* END OF IMPROVED PERLIN */
311 /**************************/
312
313 /* Was BLI_hnoise(), removed noisesize, so other functions can call it without scaling. */
314 static float orgBlenderNoise(float x, float y, float z)
315 {
316         register float cn1, cn2, cn3, cn4, cn5, cn6, i;
317         register const float *h;
318         float fx, fy, fz, ox, oy, oz, jx, jy, jz;
319         float n = 0.5;
320         int ix, iy, iz, b00, b01, b10, b11, b20, b21;
321
322         fx = floor(x);
323         fy = floor(y);
324         fz = floor(z);
325
326         ox = x - fx;
327         oy = y - fy;
328         oz = z - fz;
329
330         ix = (int)fx;
331         iy = (int)fy;
332         iz = (int)fz;
333
334         jx = ox - 1;
335         jy = oy - 1;
336         jz = oz - 1;
337
338         cn1 = ox * ox; cn2 = oy * oy; cn3 = oz * oz;
339         cn4 = jx * jx; cn5 = jy * jy; cn6 = jz * jz;
340
341         cn1 = 1.0f - 3.0f * cn1 + 2.0f * cn1 * ox;
342         cn2 = 1.0f - 3.0f * cn2 + 2.0f * cn2 * oy;
343         cn3 = 1.0f - 3.0f * cn3 + 2.0f * cn3 * oz;
344         cn4 = 1.0f - 3.0f * cn4 - 2.0f * cn4 * jx;
345         cn5 = 1.0f - 3.0f * cn5 - 2.0f * cn5 * jy;
346         cn6 = 1.0f - 3.0f * cn6 - 2.0f * cn6 * jz;
347
348         b00 = hash[hash[ix & 255] + (iy & 255)];
349         b10 = hash[hash[(ix + 1) & 255] + (iy & 255)];
350         b01 = hash[hash[ix & 255] + ((iy + 1) & 255)];
351         b11 = hash[hash[(ix + 1) & 255] + ((iy + 1) & 255)];
352
353         b20 = iz & 255; b21 = (iz + 1) & 255;
354
355         /* 0 */
356         i = (cn1 * cn2 * cn3);
357         h = hashvectf + 3 * hash[b20 + b00];
358         n += i * (h[0] * ox + h[1] * oy + h[2] * oz);
359         /* 1 */
360         i = (cn1 * cn2 * cn6);
361         h = hashvectf + 3 * hash[b21 + b00];
362         n += i * (h[0] * ox + h[1] * oy + h[2] * jz);
363         /* 2 */
364         i = (cn1 * cn5 * cn3);
365         h = hashvectf + 3 * hash[b20 + b01];
366         n += i * (h[0] * ox + h[1] * jy + h[2] * oz);
367         /* 3 */
368         i = (cn1 * cn5 * cn6);
369         h = hashvectf + 3 * hash[b21 + b01];
370         n += i * (h[0] * ox + h[1] * jy + h[2] * jz);
371         /* 4 */
372         i = cn4 * cn2 * cn3;
373         h = hashvectf + 3 * hash[b20 + b10];
374         n += i * (h[0] * jx + h[1] * oy + h[2] * oz);
375         /* 5 */
376         i = cn4 * cn2 * cn6;
377         h = hashvectf + 3 * hash[b21 + b10];
378         n += i * (h[0] * jx + h[1] * oy + h[2] * jz);
379         /* 6 */
380         i = cn4 * cn5 * cn3;
381         h = hashvectf + 3 * hash[b20 + b11];
382         n +=  i * (h[0] * jx + h[1] * jy + h[2] * oz);
383         /* 7 */
384         i = (cn4 * cn5 * cn6);
385         h = hashvectf + 3 * hash[b21 + b11];
386         n += i * (h[0] * jx + h[1] * jy + h[2] * jz);
387
388         if      (n < 0.0f) n = 0.0f;
389         else if (n > 1.0f) n = 1.0f;
390         return n;
391 }
392
393 /* as orgBlenderNoise(), returning signed noise */
394 static float orgBlenderNoiseS(float x, float y, float z)
395 {
396         return (2.0f * orgBlenderNoise(x, y, z) - 1.0f);
397 }
398
399 /* separated from orgBlenderNoise above, with scaling */
400 float BLI_hnoise(float noisesize, float x, float y, float z)
401 {
402         if (noisesize == 0.0f) return 0.0f;
403         x = (1.0f + x) / noisesize;
404         y = (1.0f + y) / noisesize;
405         z = (1.0f + z) / noisesize;
406         return orgBlenderNoise(x, y, z);
407 }
408
409
410 /* original turbulence functions */
411 float BLI_turbulence(float noisesize, float x, float y, float z, int nr)
412 {
413         float s, d = 0.5, div = 1.0;
414
415         s = BLI_hnoise(noisesize, x, y, z);
416
417         while (nr > 0) {
418
419                 s += d * BLI_hnoise(noisesize * d, x, y, z);
420                 div += d;
421                 d *= 0.5f;
422
423                 nr--;
424         }
425         return s / div;
426 }
427
428 float BLI_turbulence1(float noisesize, float x, float y, float z, int nr)
429 {
430         float s, d = 0.5, div = 1.0;
431
432         s = fabsf((-1.0f + 2.0f * BLI_hnoise(noisesize, x, y, z)));
433
434         while (nr > 0) {
435
436                 s += fabsf(d * (-1.0f + 2.0f * BLI_hnoise(noisesize * d, x, y, z)));
437                 div += d;
438                 d *= 0.5f;
439
440                 nr--;
441         }
442         return s / div;
443 }
444
445 /* ********************* FROM PERLIN HIMSELF: ******************** */
446
447 static const char g_perlin_data_ub[512 + 2] = {
448         0xA2, 0xA0, 0x19, 0x3B, 0xF8, 0xEB, 0xAA, 0xEE, 0xF3, 0x1C, 0x67, 0x28,
449         0x1D, 0xED, 0x0,  0xDE, 0x95, 0x2E, 0xDC, 0x3F, 0x3A, 0x82, 0x35, 0x4D,
450         0x6C, 0xBA, 0x36, 0xD0, 0xF6, 0xC,  0x79, 0x32, 0xD1, 0x59, 0xF4, 0x8,
451         0x8B, 0x63, 0x89, 0x2F, 0xB8, 0xB4, 0x97, 0x83, 0xF2, 0x8F, 0x18, 0xC7,
452         0x51, 0x14, 0x65, 0x87, 0x48, 0x20, 0x42, 0xA8, 0x80, 0xB5, 0x40, 0x13,
453         0xB2, 0x22, 0x7E, 0x57, 0xBC, 0x7F, 0x6B, 0x9D, 0x86, 0x4C, 0xC8, 0xDB,
454         0x7C, 0xD5, 0x25, 0x4E, 0x5A, 0x55, 0x74, 0x50, 0xCD, 0xB3, 0x7A, 0xBB,
455         0xC3, 0xCB, 0xB6, 0xE2, 0xE4, 0xEC, 0xFD, 0x98, 0xB,  0x96, 0xD3, 0x9E,
456         0x5C, 0xA1, 0x64, 0xF1, 0x81, 0x61, 0xE1, 0xC4, 0x24, 0x72, 0x49, 0x8C,
457         0x90, 0x4B, 0x84, 0x34, 0x38, 0xAB, 0x78, 0xCA, 0x1F, 0x1,  0xD7, 0x93,
458         0x11, 0xC1, 0x58, 0xA9, 0x31, 0xF9, 0x44, 0x6D, 0xBF, 0x33, 0x9C, 0x5F,
459         0x9,  0x94, 0xA3, 0x85, 0x6,  0xC6, 0x9A, 0x1E, 0x7B, 0x46, 0x15, 0x30,
460         0x27, 0x2B, 0x1B, 0x71, 0x3C, 0x5B, 0xD6, 0x6F, 0x62, 0xAC, 0x4F, 0xC2,
461         0xC0, 0xE,  0xB1, 0x23, 0xA7, 0xDF, 0x47, 0xB0, 0x77, 0x69, 0x5,  0xE9,
462         0xE6, 0xE7, 0x76, 0x73, 0xF,  0xFE, 0x6E, 0x9B, 0x56, 0xEF, 0x12, 0xA5,
463         0x37, 0xFC, 0xAE, 0xD9, 0x3,  0x8E, 0xDD, 0x10, 0xB9, 0xCE, 0xC9, 0x8D,
464         0xDA, 0x2A, 0xBD, 0x68, 0x17, 0x9F, 0xBE, 0xD4, 0xA,  0xCC, 0xD2, 0xE8,
465         0x43, 0x3D, 0x70, 0xB7, 0x2,  0x7D, 0x99, 0xD8, 0xD,  0x60, 0x8A, 0x4,
466         0x2C, 0x3E, 0x92, 0xE5, 0xAF, 0x53, 0x7,  0xE0, 0x29, 0xA6, 0xC5, 0xE3,
467         0xF5, 0xF7, 0x4A, 0x41, 0x26, 0x6A, 0x16, 0x5E, 0x52, 0x2D, 0x21, 0xAD,
468         0xF0, 0x91, 0xFF, 0xEA, 0x54, 0xFA, 0x66, 0x1A, 0x45, 0x39, 0xCF, 0x75,
469         0xA4, 0x88, 0xFB, 0x5D, 0xA2, 0xA0, 0x19, 0x3B, 0xF8, 0xEB, 0xAA, 0xEE,
470         0xF3, 0x1C, 0x67, 0x28, 0x1D, 0xED, 0x0,  0xDE, 0x95, 0x2E, 0xDC, 0x3F,
471         0x3A, 0x82, 0x35, 0x4D, 0x6C, 0xBA, 0x36, 0xD0, 0xF6, 0xC,  0x79, 0x32,
472         0xD1, 0x59, 0xF4, 0x8,  0x8B, 0x63, 0x89, 0x2F, 0xB8, 0xB4, 0x97, 0x83,
473         0xF2, 0x8F, 0x18, 0xC7, 0x51, 0x14, 0x65, 0x87, 0x48, 0x20, 0x42, 0xA8,
474         0x80, 0xB5, 0x40, 0x13, 0xB2, 0x22, 0x7E, 0x57, 0xBC, 0x7F, 0x6B, 0x9D,
475         0x86, 0x4C, 0xC8, 0xDB, 0x7C, 0xD5, 0x25, 0x4E, 0x5A, 0x55, 0x74, 0x50,
476         0xCD, 0xB3, 0x7A, 0xBB, 0xC3, 0xCB, 0xB6, 0xE2, 0xE4, 0xEC, 0xFD, 0x98,
477         0xB,  0x96, 0xD3, 0x9E, 0x5C, 0xA1, 0x64, 0xF1, 0x81, 0x61, 0xE1, 0xC4,
478         0x24, 0x72, 0x49, 0x8C, 0x90, 0x4B, 0x84, 0x34, 0x38, 0xAB, 0x78, 0xCA,
479         0x1F, 0x1,  0xD7, 0x93, 0x11, 0xC1, 0x58, 0xA9, 0x31, 0xF9, 0x44, 0x6D,
480         0xBF, 0x33, 0x9C, 0x5F, 0x9,  0x94, 0xA3, 0x85, 0x6,  0xC6, 0x9A, 0x1E,
481         0x7B, 0x46, 0x15, 0x30, 0x27, 0x2B, 0x1B, 0x71, 0x3C, 0x5B, 0xD6, 0x6F,
482         0x62, 0xAC, 0x4F, 0xC2, 0xC0, 0xE,  0xB1, 0x23, 0xA7, 0xDF, 0x47, 0xB0,
483         0x77, 0x69, 0x5,  0xE9, 0xE6, 0xE7, 0x76, 0x73, 0xF,  0xFE, 0x6E, 0x9B,
484         0x56, 0xEF, 0x12, 0xA5, 0x37, 0xFC, 0xAE, 0xD9, 0x3,  0x8E, 0xDD, 0x10,
485         0xB9, 0xCE, 0xC9, 0x8D, 0xDA, 0x2A, 0xBD, 0x68, 0x17, 0x9F, 0xBE, 0xD4,
486         0xA,  0xCC, 0xD2, 0xE8, 0x43, 0x3D, 0x70, 0xB7, 0x2,  0x7D, 0x99, 0xD8,
487         0xD,  0x60, 0x8A, 0x4,  0x2C, 0x3E, 0x92, 0xE5, 0xAF, 0x53, 0x7,  0xE0,
488         0x29, 0xA6, 0xC5, 0xE3, 0xF5, 0xF7, 0x4A, 0x41, 0x26, 0x6A, 0x16, 0x5E,
489         0x52, 0x2D, 0x21, 0xAD, 0xF0, 0x91, 0xFF, 0xEA, 0x54, 0xFA, 0x66, 0x1A,
490         0x45, 0x39, 0xCF, 0x75, 0xA4, 0x88, 0xFB, 0x5D, 0xA2, 0xA0,
491 };
492
493
494 static const float g_perlin_data_v3[512 + 2][3] = {
495         {0.33783, 0.715698, -0.611206},
496         {-0.944031, -0.326599, -0.045624},
497         {-0.101074, -0.416443, -0.903503},
498         {0.799286, 0.49411, -0.341949},
499         {-0.854645, 0.518036, 0.033936},
500         {0.42514, -0.437866, -0.792114},
501         {-0.358948, 0.597046, 0.717377},
502         {-0.985413, 0.144714, 0.089294},
503         {-0.601776, -0.33728, -0.723907},
504         {-0.449921, 0.594513, 0.666382},
505         {0.208313, -0.10791, 0.972076},
506         {0.575317, 0.060425, 0.815643},
507         {0.293365, -0.875702, -0.383453},
508         {0.293762, 0.465759, 0.834686},
509         {-0.846008, -0.233398, -0.47934},
510         {-0.115814, 0.143036, -0.98291},
511         {0.204681, -0.949036, -0.239532},
512         {0.946716, -0.263947, 0.184326},
513         {-0.235596, 0.573822, 0.784332},
514         {0.203705, -0.372253, -0.905487},
515         {0.756989, -0.651031, 0.055298},
516         {0.497803, 0.814697, -0.297363},
517         {-0.16214, 0.063995, -0.98468},
518         {-0.329254, 0.834381, 0.441925},
519         {0.703827, -0.527039, -0.476227},
520         {0.956421, 0.266113, 0.119781},
521         {0.480133, 0.482849, 0.7323},
522         {-0.18631, 0.961212, -0.203125},
523         {-0.748474, -0.656921, -0.090393},
524         {-0.085052, -0.165253, 0.982544},
525         {-0.76947, 0.628174, -0.115234},
526         {0.383148, 0.537659, 0.751068},
527         {0.616486, -0.668488, -0.415924},
528         {-0.259979, -0.630005, 0.73175},
529         {0.570953, -0.087952, 0.816223},
530         {-0.458008, 0.023254, 0.888611},
531         {-0.196167, 0.976563, -0.088287},
532         {-0.263885, -0.69812, -0.665527},
533         {0.437134, -0.892273, -0.112793},
534         {-0.621674, -0.230438, 0.748566},
535         {0.232422, 0.900574, -0.367249},
536         {0.22229, -0.796143, 0.562744},
537         {-0.665497, -0.73764, 0.11377},
538         {0.670135, 0.704803, 0.232605},
539         {0.895599, 0.429749, -0.114655},
540         {-0.11557, -0.474243, 0.872742},
541         {0.621826, 0.604004, -0.498444},
542         {-0.832214, 0.012756, 0.55426},
543         {-0.702484, 0.705994, -0.089661},
544         {-0.692017, 0.649292, 0.315399},
545         {-0.175995, -0.977997, 0.111877},
546         {0.096954, -0.04953, 0.994019},
547         {0.635284, -0.606689, -0.477783},
548         {-0.261261, -0.607422, -0.750153},
549         {0.983276, 0.165436, 0.075958},
550         {-0.29837, 0.404083, -0.864655},
551         {-0.638672, 0.507721, 0.578156},
552         {0.388214, 0.412079, 0.824249},
553         {0.556183, -0.208832, 0.804352},
554         {0.778442, 0.562012, 0.27951},
555         {-0.616577, 0.781921, -0.091522},
556         {0.196289, 0.051056, 0.979187},
557         {-0.121216, 0.207153, -0.970734},
558         {-0.173401, -0.384735, 0.906555},
559         {0.161499, -0.723236, -0.671387},
560         {0.178497, -0.006226, -0.983887},
561         {-0.126038, 0.15799, 0.97934},
562         {0.830475, -0.024811, 0.556458},
563         {-0.510132, -0.76944, 0.384247},
564         {0.81424, 0.200104, -0.544891},
565         {-0.112549, -0.393311, -0.912445},
566         {0.56189, 0.152222, -0.813049},
567         {0.198914, -0.254517, -0.946381},
568         {-0.41217, 0.690979, -0.593811},
569         {-0.407257, 0.324524, 0.853668},
570         {-0.690186, 0.366119, -0.624115},
571         {-0.428345, 0.844147, -0.322296},
572         {-0.21228, -0.297546, -0.930756},
573         {-0.273071, 0.516113, 0.811798},
574         {0.928314, 0.371643, 0.007233},
575         {0.785828, -0.479218, -0.390778},
576         {-0.704895, 0.058929, 0.706818},
577         {0.173248, 0.203583, 0.963562},
578         {0.422211, -0.904297, -0.062469},
579         {-0.363312, -0.182465, 0.913605},
580         {0.254028, -0.552307, -0.793945},
581         {-0.28891, -0.765747, -0.574554},
582         {0.058319, 0.291382, 0.954803},
583         {0.946136, -0.303925, 0.111267},
584         {-0.078156, 0.443695, -0.892731},
585         {0.182098, 0.89389, 0.409515},
586         {-0.680298, -0.213318, 0.701141},
587         {0.062469, 0.848389, -0.525635},
588         {-0.72879, -0.641846, 0.238342},
589         {-0.88089, 0.427673, 0.202637},
590         {-0.532501, -0.21405, 0.818878},
591         {0.948975, -0.305084, 0.07962},
592         {0.925446, 0.374664, 0.055817},
593         {0.820923, 0.565491, 0.079102},
594         {0.25882, 0.099792, -0.960724},
595         {-0.294617, 0.910522, 0.289978},
596         {0.137115, 0.320038, -0.937408},
597         {-0.908386, 0.345276, -0.235718},
598         {-0.936218, 0.138763, 0.322754},
599         {0.366577, 0.925934, -0.090637},
600         {0.309296, -0.686829, -0.657684},
601         {0.66983, 0.024445, 0.742065},
602         {-0.917999, -0.059113, -0.392059},
603         {0.365509, 0.462158, -0.807922},
604         {0.083374, 0.996399, -0.014801},
605         {0.593842, 0.253143, -0.763672},
606         {0.974976, -0.165466, 0.148285},
607         {0.918976, 0.137299, 0.369537},
608         {0.294952, 0.694977, 0.655731},
609         {0.943085, 0.152618, -0.295319},
610         {0.58783, -0.598236, 0.544495},
611         {0.203796, 0.678223, 0.705994},
612         {-0.478821, -0.661011, 0.577667},
613         {0.719055, -0.1698, -0.673828},
614         {-0.132172, -0.965332, 0.225006},
615         {-0.981873, -0.14502, 0.121979},
616         {0.763458, 0.579742, 0.284546},
617         {-0.893188, 0.079681, 0.442474},
618         {-0.795776, -0.523804, 0.303802},
619         {0.734955, 0.67804, -0.007446},
620         {0.15506, 0.986267, -0.056183},
621         {0.258026, 0.571503, -0.778931},
622         {-0.681549, -0.702087, -0.206116},
623         {-0.96286, -0.177185, 0.203613},
624         {-0.470978, -0.515106, 0.716095},
625         {-0.740326, 0.57135, 0.354095},
626         {-0.56012, -0.824982, -0.074982},
627         {-0.507874, 0.753204, 0.417969},
628         {-0.503113, 0.038147, 0.863342},
629         {0.594025, 0.673553, -0.439758},
630         {-0.119873, -0.005524, -0.992737},
631         {0.098267, -0.213776, 0.971893},
632         {-0.615631, 0.643951, 0.454163},
633         {0.896851, -0.441071, 0.032166},
634         {-0.555023, 0.750763, -0.358093},
635         {0.398773, 0.304688, 0.864929},
636         {-0.722961, 0.303589, 0.620544},
637         {-0.63559, -0.621948, -0.457306},
638         {-0.293243, 0.072327, 0.953278},
639         {-0.491638, 0.661041, -0.566772},
640         {-0.304199, -0.572083, -0.761688},
641         {0.908081, -0.398956, 0.127014},
642         {-0.523621, -0.549683, -0.650848},
643         {-0.932922, -0.19986, 0.299408},
644         {0.099426, 0.140869, 0.984985},
645         {-0.020325, -0.999756, -0.002319},
646         {0.952667, 0.280853, -0.11615},
647         {-0.971893, 0.082581, 0.220337},
648         {0.65921, 0.705292, -0.260651},
649         {0.733063, -0.175537, 0.657043},
650         {-0.555206, 0.429504, -0.712189},
651         {0.400421, -0.89859, 0.179352},
652         {0.750885, -0.19696, 0.630341},
653         {0.785675, -0.569336, 0.241821},
654         {-0.058899, -0.464111, 0.883789},
655         {0.129608, -0.94519, 0.299622},
656         {-0.357819, 0.907654, 0.219238},
657         {-0.842133, -0.439117, -0.312927},
658         {-0.313477, 0.84433, 0.434479},
659         {-0.241211, 0.053253, 0.968994},
660         {0.063873, 0.823273, 0.563965},
661         {0.476288, 0.862152, -0.172516},
662         {0.620941, -0.298126, 0.724915},
663         {0.25238, -0.749359, -0.612122},
664         {-0.577545, 0.386566, 0.718994},
665         {-0.406342, -0.737976, 0.538696},
666         {0.04718, 0.556305, 0.82959},
667         {-0.802856, 0.587463, 0.101166},
668         {-0.707733, -0.705963, 0.026428},
669         {0.374908, 0.68457, 0.625092},
670         {0.472137, 0.208405, -0.856506},
671         {-0.703064, -0.581085, -0.409821},
672         {-0.417206, -0.736328, 0.532623},
673         {-0.447876, -0.20285, -0.870728},
674         {0.086945, -0.990417, 0.107086},
675         {0.183685, 0.018341, -0.982788},
676         {0.560638, -0.428864, 0.708282},
677         {0.296722, -0.952576, -0.0672},
678         {0.135773, 0.990265, 0.030243},
679         {-0.068787, 0.654724, 0.752686},
680         {0.762604, -0.551758, 0.337585},
681         {-0.819611, -0.407684, 0.402466},
682         {-0.727844, -0.55072, -0.408539},
683         {-0.855774, -0.480011, 0.19281},
684         {0.693176, -0.079285, 0.716339},
685         {0.226013, 0.650116, -0.725433},
686         {0.246704, 0.953369, -0.173553},
687         {-0.970398, -0.239227, -0.03244},
688         {0.136383, -0.394318, 0.908752},
689         {0.813232, 0.558167, 0.164368},
690         {0.40451, 0.549042, -0.731323},
691         {-0.380249, -0.566711, 0.730865},
692         {0.022156, 0.932739, 0.359741},
693         {0.00824, 0.996552, -0.082306},
694         {0.956635, -0.065338, -0.283722},
695         {-0.743561, 0.008209, 0.668579},
696         {-0.859589, -0.509674, 0.035767},
697         {-0.852234, 0.363678, -0.375977},
698         {-0.201965, -0.970795, -0.12915},
699         {0.313477, 0.947327, 0.06546},
700         {-0.254028, -0.528259, 0.81015},
701         {0.628052, 0.601105, 0.49411},
702         {-0.494385, 0.868378, 0.037933},
703         {0.275635, -0.086426, 0.957336},
704         {-0.197937, 0.468903, -0.860748},
705         {0.895599, 0.399384, 0.195801},
706         {0.560791, 0.825012, -0.069214},
707         {0.304199, -0.849487, 0.43103},
708         {0.096375, 0.93576, 0.339111},
709         {-0.051422, 0.408966, -0.911072},
710         {0.330444, 0.942841, -0.042389},
711         {-0.452362, -0.786407, 0.420563},
712         {0.134308, -0.933472, -0.332489},
713         {0.80191, -0.566711, -0.188934},
714         {-0.987946, -0.105988, 0.112518},
715         {-0.24408, 0.892242, -0.379791},
716         {-0.920502, 0.229095, -0.316376},
717         {0.7789, 0.325958, 0.535706},
718         {-0.912872, 0.185211, -0.36377},
719         {-0.184784, 0.565369, -0.803833},
720         {-0.018463, 0.119537, 0.992615},
721         {-0.259247, -0.935608, 0.239532},
722         {-0.82373, -0.449127, -0.345947},
723         {-0.433105, 0.659515, 0.614349},
724         {-0.822754, 0.378845, -0.423676},
725         {0.687195, -0.674835, -0.26889},
726         {-0.246582, -0.800842, 0.545715},
727         {-0.729187, -0.207794, 0.651978},
728         {0.653534, -0.610443, -0.447388},
729         {0.492584, -0.023346, 0.869934},
730         {0.609039, 0.009094, -0.79306},
731         {0.962494, -0.271088, -0.00885},
732         {0.2659, -0.004913, 0.963959},
733         {0.651245, 0.553619, -0.518951},
734         {0.280548, -0.84314, 0.458618},
735         {-0.175293, -0.983215, 0.049805},
736         {0.035339, -0.979919, 0.196045},
737         {-0.982941, 0.164307, -0.082245},
738         {0.233734, -0.97226, -0.005005},
739         {-0.747253, -0.611328, 0.260437},
740         {0.645599, 0.592773, 0.481384},
741         {0.117706, -0.949524, -0.29068},
742         {-0.535004, -0.791901, -0.294312},
743         {-0.627167, -0.214447, 0.748718},
744         {-0.047974, -0.813477, -0.57959},
745         {-0.175537, 0.477264, -0.860992},
746         {0.738556, -0.414246, -0.53183},
747         {0.562561, -0.704071, 0.433289},
748         {-0.754944, 0.64801, -0.100586},
749         {0.114716, 0.044525, -0.992371},
750         {0.966003, 0.244873, -0.082764},
751         {0.33783, 0.715698, -0.611206},
752         {-0.944031, -0.326599, -0.045624},
753         {-0.101074, -0.416443, -0.903503},
754         {0.799286, 0.49411, -0.341949},
755         {-0.854645, 0.518036, 0.033936},
756         {0.42514, -0.437866, -0.792114},
757         {-0.358948, 0.597046, 0.717377},
758         {-0.985413, 0.144714, 0.089294},
759         {-0.601776, -0.33728, -0.723907},
760         {-0.449921, 0.594513, 0.666382},
761         {0.208313, -0.10791, 0.972076},
762         {0.575317, 0.060425, 0.815643},
763         {0.293365, -0.875702, -0.383453},
764         {0.293762, 0.465759, 0.834686},
765         {-0.846008, -0.233398, -0.47934},
766         {-0.115814, 0.143036, -0.98291},
767         {0.204681, -0.949036, -0.239532},
768         {0.946716, -0.263947, 0.184326},
769         {-0.235596, 0.573822, 0.784332},
770         {0.203705, -0.372253, -0.905487},
771         {0.756989, -0.651031, 0.055298},
772         {0.497803, 0.814697, -0.297363},
773         {-0.16214, 0.063995, -0.98468},
774         {-0.329254, 0.834381, 0.441925},
775         {0.703827, -0.527039, -0.476227},
776         {0.956421, 0.266113, 0.119781},
777         {0.480133, 0.482849, 0.7323},
778         {-0.18631, 0.961212, -0.203125},
779         {-0.748474, -0.656921, -0.090393},
780         {-0.085052, -0.165253, 0.982544},
781         {-0.76947, 0.628174, -0.115234},
782         {0.383148, 0.537659, 0.751068},
783         {0.616486, -0.668488, -0.415924},
784         {-0.259979, -0.630005, 0.73175},
785         {0.570953, -0.087952, 0.816223},
786         {-0.458008, 0.023254, 0.888611},
787         {-0.196167, 0.976563, -0.088287},
788         {-0.263885, -0.69812, -0.665527},
789         {0.437134, -0.892273, -0.112793},
790         {-0.621674, -0.230438, 0.748566},
791         {0.232422, 0.900574, -0.367249},
792         {0.22229, -0.796143, 0.562744},
793         {-0.665497, -0.73764, 0.11377},
794         {0.670135, 0.704803, 0.232605},
795         {0.895599, 0.429749, -0.114655},
796         {-0.11557, -0.474243, 0.872742},
797         {0.621826, 0.604004, -0.498444},
798         {-0.832214, 0.012756, 0.55426},
799         {-0.702484, 0.705994, -0.089661},
800         {-0.692017, 0.649292, 0.315399},
801         {-0.175995, -0.977997, 0.111877},
802         {0.096954, -0.04953, 0.994019},
803         {0.635284, -0.606689, -0.477783},
804         {-0.261261, -0.607422, -0.750153},
805         {0.983276, 0.165436, 0.075958},
806         {-0.29837, 0.404083, -0.864655},
807         {-0.638672, 0.507721, 0.578156},
808         {0.388214, 0.412079, 0.824249},
809         {0.556183, -0.208832, 0.804352},
810         {0.778442, 0.562012, 0.27951},
811         {-0.616577, 0.781921, -0.091522},
812         {0.196289, 0.051056, 0.979187},
813         {-0.121216, 0.207153, -0.970734},
814         {-0.173401, -0.384735, 0.906555},
815         {0.161499, -0.723236, -0.671387},
816         {0.178497, -0.006226, -0.983887},
817         {-0.126038, 0.15799, 0.97934},
818         {0.830475, -0.024811, 0.556458},
819         {-0.510132, -0.76944, 0.384247},
820         {0.81424, 0.200104, -0.544891},
821         {-0.112549, -0.393311, -0.912445},
822         {0.56189, 0.152222, -0.813049},
823         {0.198914, -0.254517, -0.946381},
824         {-0.41217, 0.690979, -0.593811},
825         {-0.407257, 0.324524, 0.853668},
826         {-0.690186, 0.366119, -0.624115},
827         {-0.428345, 0.844147, -0.322296},
828         {-0.21228, -0.297546, -0.930756},
829         {-0.273071, 0.516113, 0.811798},
830         {0.928314, 0.371643, 0.007233},
831         {0.785828, -0.479218, -0.390778},
832         {-0.704895, 0.058929, 0.706818},
833         {0.173248, 0.203583, 0.963562},
834         {0.422211, -0.904297, -0.062469},
835         {-0.363312, -0.182465, 0.913605},
836         {0.254028, -0.552307, -0.793945},
837         {-0.28891, -0.765747, -0.574554},
838         {0.058319, 0.291382, 0.954803},
839         {0.946136, -0.303925, 0.111267},
840         {-0.078156, 0.443695, -0.892731},
841         {0.182098, 0.89389, 0.409515},
842         {-0.680298, -0.213318, 0.701141},
843         {0.062469, 0.848389, -0.525635},
844         {-0.72879, -0.641846, 0.238342},
845         {-0.88089, 0.427673, 0.202637},
846         {-0.532501, -0.21405, 0.818878},
847         {0.948975, -0.305084, 0.07962},
848         {0.925446, 0.374664, 0.055817},
849         {0.820923, 0.565491, 0.079102},
850         {0.25882, 0.099792, -0.960724},
851         {-0.294617, 0.910522, 0.289978},
852         {0.137115, 0.320038, -0.937408},
853         {-0.908386, 0.345276, -0.235718},
854         {-0.936218, 0.138763, 0.322754},
855         {0.366577, 0.925934, -0.090637},
856         {0.309296, -0.686829, -0.657684},
857         {0.66983, 0.024445, 0.742065},
858         {-0.917999, -0.059113, -0.392059},
859         {0.365509, 0.462158, -0.807922},
860         {0.083374, 0.996399, -0.014801},
861         {0.593842, 0.253143, -0.763672},
862         {0.974976, -0.165466, 0.148285},
863         {0.918976, 0.137299, 0.369537},
864         {0.294952, 0.694977, 0.655731},
865         {0.943085, 0.152618, -0.295319},
866         {0.58783, -0.598236, 0.544495},
867         {0.203796, 0.678223, 0.705994},
868         {-0.478821, -0.661011, 0.577667},
869         {0.719055, -0.1698, -0.673828},
870         {-0.132172, -0.965332, 0.225006},
871         {-0.981873, -0.14502, 0.121979},
872         {0.763458, 0.579742, 0.284546},
873         {-0.893188, 0.079681, 0.442474},
874         {-0.795776, -0.523804, 0.303802},
875         {0.734955, 0.67804, -0.007446},
876         {0.15506, 0.986267, -0.056183},
877         {0.258026, 0.571503, -0.778931},
878         {-0.681549, -0.702087, -0.206116},
879         {-0.96286, -0.177185, 0.203613},
880         {-0.470978, -0.515106, 0.716095},
881         {-0.740326, 0.57135, 0.354095},
882         {-0.56012, -0.824982, -0.074982},
883         {-0.507874, 0.753204, 0.417969},
884         {-0.503113, 0.038147, 0.863342},
885         {0.594025, 0.673553, -0.439758},
886         {-0.119873, -0.005524, -0.992737},
887         {0.098267, -0.213776, 0.971893},
888         {-0.615631, 0.643951, 0.454163},
889         {0.896851, -0.441071, 0.032166},
890         {-0.555023, 0.750763, -0.358093},
891         {0.398773, 0.304688, 0.864929},
892         {-0.722961, 0.303589, 0.620544},
893         {-0.63559, -0.621948, -0.457306},
894         {-0.293243, 0.072327, 0.953278},
895         {-0.491638, 0.661041, -0.566772},
896         {-0.304199, -0.572083, -0.761688},
897         {0.908081, -0.398956, 0.127014},
898         {-0.523621, -0.549683, -0.650848},
899         {-0.932922, -0.19986, 0.299408},
900         {0.099426, 0.140869, 0.984985},
901         {-0.020325, -0.999756, -0.002319},
902         {0.952667, 0.280853, -0.11615},
903         {-0.971893, 0.082581, 0.220337},
904         {0.65921, 0.705292, -0.260651},
905         {0.733063, -0.175537, 0.657043},
906         {-0.555206, 0.429504, -0.712189},
907         {0.400421, -0.89859, 0.179352},
908         {0.750885, -0.19696, 0.630341},
909         {0.785675, -0.569336, 0.241821},
910         {-0.058899, -0.464111, 0.883789},
911         {0.129608, -0.94519, 0.299622},
912         {-0.357819, 0.907654, 0.219238},
913         {-0.842133, -0.439117, -0.312927},
914         {-0.313477, 0.84433, 0.434479},
915         {-0.241211, 0.053253, 0.968994},
916         {0.063873, 0.823273, 0.563965},
917         {0.476288, 0.862152, -0.172516},
918         {0.620941, -0.298126, 0.724915},
919         {0.25238, -0.749359, -0.612122},
920         {-0.577545, 0.386566, 0.718994},
921         {-0.406342, -0.737976, 0.538696},
922         {0.04718, 0.556305, 0.82959},
923         {-0.802856, 0.587463, 0.101166},
924         {-0.707733, -0.705963, 0.026428},
925         {0.374908, 0.68457, 0.625092},
926         {0.472137, 0.208405, -0.856506},
927         {-0.703064, -0.581085, -0.409821},
928         {-0.417206, -0.736328, 0.532623},
929         {-0.447876, -0.20285, -0.870728},
930         {0.086945, -0.990417, 0.107086},
931         {0.183685, 0.018341, -0.982788},
932         {0.560638, -0.428864, 0.708282},
933         {0.296722, -0.952576, -0.0672},
934         {0.135773, 0.990265, 0.030243},
935         {-0.068787, 0.654724, 0.752686},
936         {0.762604, -0.551758, 0.337585},
937         {-0.819611, -0.407684, 0.402466},
938         {-0.727844, -0.55072, -0.408539},
939         {-0.855774, -0.480011, 0.19281},
940         {0.693176, -0.079285, 0.716339},
941         {0.226013, 0.650116, -0.725433},
942         {0.246704, 0.953369, -0.173553},
943         {-0.970398, -0.239227, -0.03244},
944         {0.136383, -0.394318, 0.908752},
945         {0.813232, 0.558167, 0.164368},
946         {0.40451, 0.549042, -0.731323},
947         {-0.380249, -0.566711, 0.730865},
948         {0.022156, 0.932739, 0.359741},
949         {0.00824, 0.996552, -0.082306},
950         {0.956635, -0.065338, -0.283722},
951         {-0.743561, 0.008209, 0.668579},
952         {-0.859589, -0.509674, 0.035767},
953         {-0.852234, 0.363678, -0.375977},
954         {-0.201965, -0.970795, -0.12915},
955         {0.313477, 0.947327, 0.06546},
956         {-0.254028, -0.528259, 0.81015},
957         {0.628052, 0.601105, 0.49411},
958         {-0.494385, 0.868378, 0.037933},
959         {0.275635, -0.086426, 0.957336},
960         {-0.197937, 0.468903, -0.860748},
961         {0.895599, 0.399384, 0.195801},
962         {0.560791, 0.825012, -0.069214},
963         {0.304199, -0.849487, 0.43103},
964         {0.096375, 0.93576, 0.339111},
965         {-0.051422, 0.408966, -0.911072},
966         {0.330444, 0.942841, -0.042389},
967         {-0.452362, -0.786407, 0.420563},
968         {0.134308, -0.933472, -0.332489},
969         {0.80191, -0.566711, -0.188934},
970         {-0.987946, -0.105988, 0.112518},
971         {-0.24408, 0.892242, -0.379791},
972         {-0.920502, 0.229095, -0.316376},
973         {0.7789, 0.325958, 0.535706},
974         {-0.912872, 0.185211, -0.36377},
975         {-0.184784, 0.565369, -0.803833},
976         {-0.018463, 0.119537, 0.992615},
977         {-0.259247, -0.935608, 0.239532},
978         {-0.82373, -0.449127, -0.345947},
979         {-0.433105, 0.659515, 0.614349},
980         {-0.822754, 0.378845, -0.423676},
981         {0.687195, -0.674835, -0.26889},
982         {-0.246582, -0.800842, 0.545715},
983         {-0.729187, -0.207794, 0.651978},
984         {0.653534, -0.610443, -0.447388},
985         {0.492584, -0.023346, 0.869934},
986         {0.609039, 0.009094, -0.79306},
987         {0.962494, -0.271088, -0.00885},
988         {0.2659, -0.004913, 0.963959},
989         {0.651245, 0.553619, -0.518951},
990         {0.280548, -0.84314, 0.458618},
991         {-0.175293, -0.983215, 0.049805},
992         {0.035339, -0.979919, 0.196045},
993         {-0.982941, 0.164307, -0.082245},
994         {0.233734, -0.97226, -0.005005},
995         {-0.747253, -0.611328, 0.260437},
996         {0.645599, 0.592773, 0.481384},
997         {0.117706, -0.949524, -0.29068},
998         {-0.535004, -0.791901, -0.294312},
999         {-0.627167, -0.214447, 0.748718},
1000         {-0.047974, -0.813477, -0.57959},
1001         {-0.175537, 0.477264, -0.860992},
1002         {0.738556, -0.414246, -0.53183},
1003         {0.562561, -0.704071, 0.433289},
1004         {-0.754944, 0.64801, -0.100586},
1005         {0.114716, 0.044525, -0.992371},
1006         {0.966003, 0.244873, -0.082764},
1007         {0.33783, 0.715698, -0.611206},
1008         {-0.944031, -0.326599, -0.045624},
1009 };
1010
1011 #define SETUP(val, b0, b1, r0, r1)                                            \
1012         {                                                                         \
1013                 t = val + 10000.0f;                                                   \
1014                 b0 = ((int)t) & 255;                                                  \
1015                 b1 = (b0 + 1) & 255;                                                  \
1016                 r0 = t - floorf(t);                                                   \
1017                 r1 = r0 - 1.0f;                                                       \
1018         } (void)0
1019
1020
1021 static float noise3_perlin(float vec[3])
1022 {
1023         const char *p       = g_perlin_data_ub;
1024         const float (*g)[3] = g_perlin_data_v3;
1025         int bx0, bx1, by0, by1, bz0, bz1, b00, b10, b01, b11;
1026         float rx0, rx1, ry0, ry1, rz0, rz1, sx, sy, sz, a, b, c, d, t, u, v;
1027         const float *q;
1028         register int i, j;
1029
1030
1031         SETUP(vec[0],  bx0, bx1,  rx0, rx1);
1032         SETUP(vec[1],  by0, by1,  ry0, ry1);
1033         SETUP(vec[2],  bz0, bz1,  rz0, rz1);
1034
1035         i = p[bx0];
1036         j = p[bx1];
1037
1038         b00 = p[i + by0];
1039         b10 = p[j + by0];
1040         b01 = p[i + by1];
1041         b11 = p[j + by1];
1042
1043 #define VALUE_AT(rx, ry, rz) ((rx) * q[0] + (ry) * q[1] + (rz) * q[2])
1044 #define SURVE(t) ((t) * (t) * (3.0f - 2.0f * (t)))
1045
1046 /* lerp moved to improved perlin above */
1047
1048         sx = SURVE(rx0);
1049         sy = SURVE(ry0);
1050         sz = SURVE(rz0);
1051
1052
1053         q = g[b00 + bz0];
1054         u = VALUE_AT(rx0, ry0, rz0);
1055         q = g[b10 + bz0];
1056         v = VALUE_AT(rx1, ry0, rz0);
1057         a = lerp(sx, u, v);
1058
1059         q = g[b01 + bz0];
1060         u = VALUE_AT(rx0, ry1, rz0);
1061         q = g[b11 + bz0];
1062         v = VALUE_AT(rx1, ry1, rz0);
1063         b = lerp(sx, u, v);
1064
1065         c = lerp(sy, a, b);          /* interpolate in y at lo x */
1066
1067         q = g[b00 + bz1];
1068         u = VALUE_AT(rx0, ry0, rz1);
1069         q = g[b10 + bz1];
1070         v = VALUE_AT(rx1, ry0, rz1);
1071         a = lerp(sx, u, v);
1072
1073         q = g[b01 + bz1];
1074         u = VALUE_AT(rx0, ry1, rz1);
1075         q = g[b11 + bz1];
1076         v = VALUE_AT(rx1, ry1, rz1);
1077         b = lerp(sx, u, v);
1078
1079         d = lerp(sy, a, b);          /* interpolate in y at hi x */
1080
1081         return 1.5f * lerp(sz, c, d); /* interpolate in z */
1082
1083 #undef VALUE_AT
1084 #undef SURVE
1085 }
1086
1087 /* for use with BLI_gNoise/gTurbulence, returns signed noise */
1088 static float orgPerlinNoise(float x, float y, float z)
1089 {
1090         float v[3];
1091
1092         v[0] = x;
1093         v[1] = y;
1094         v[2] = z;
1095         return noise3_perlin(v);
1096 }
1097
1098 /* for use with BLI_gNoise/gTurbulence, returns unsigned noise */
1099 static float orgPerlinNoiseU(float x, float y, float z)
1100 {
1101         float v[3];
1102
1103         v[0] = x;
1104         v[1] = y;
1105         v[2] = z;
1106         return (0.5f + 0.5f * noise3_perlin(v));
1107 }
1108
1109 /* *************** CALL AS: *************** */
1110
1111 float BLI_hnoisep(float noisesize, float x, float y, float z)
1112 {
1113         float vec[3];
1114
1115         vec[0] = x / noisesize;
1116         vec[1] = y / noisesize;
1117         vec[2] = z / noisesize;
1118
1119         return noise3_perlin(vec);
1120 }
1121
1122 /******************/
1123 /* VORONOI/WORLEY */
1124 /******************/
1125
1126 /* distance metrics for voronoi, e parameter only used in Minkowski */
1127 /* Camberra omitted, didn't seem useful */
1128
1129 /* distance squared */
1130 static float dist_Squared(float x, float y, float z, float e)
1131 {
1132         (void)e; return (x * x + y * y + z * z);
1133 }
1134 /* real distance */
1135 static float dist_Real(float x, float y, float z, float e)
1136 {
1137         (void)e; return sqrtf(x * x + y * y + z * z);
1138 }
1139 /* manhattan/taxicab/cityblock distance */
1140 static float dist_Manhattan(float x, float y, float z, float e)
1141 {
1142         (void)e; return (fabsf(x) + fabsf(y) + fabsf(z));
1143 }
1144 /* Chebychev */
1145 static float dist_Chebychev(float x, float y, float z, float e)
1146 {
1147         float t;
1148         (void)e;
1149
1150         x = fabsf(x);
1151         y = fabsf(y);
1152         z = fabsf(z);
1153         t = (x > y) ? x : y;
1154         return ((z > t) ? z : t);
1155 }
1156
1157 /* minkowski preset exponent 0.5 */
1158 static float dist_MinkovskyH(float x, float y, float z, float e)
1159 {
1160         float d = sqrtf(fabsf(x)) + sqrtf(fabsf(y)) + sqrtf(fabsf(z));
1161         (void)e;
1162         return (d * d);
1163 }
1164
1165 /* minkowski preset exponent 4 */
1166 static float dist_Minkovsky4(float x, float y, float z, float e)
1167 {
1168         (void)e;
1169         x *= x;
1170         y *= y;
1171         z *= z;
1172         return sqrtf(sqrtf(x * x + y * y + z * z));
1173 }
1174
1175 /* Minkowski, general case, slow, maybe too slow to be useful */
1176 static float dist_Minkovsky(float x, float y, float z, float e)
1177 {
1178         return powf(powf(fabsf(x), e) + powf(fabsf(y), e) + powf(fabsf(z), e), 1.0f / e);
1179 }
1180
1181
1182 /* Not 'pure' Worley, but the results are virtually the same.
1183  * Returns distances in da and point coords in pa */
1184 void voronoi(float x, float y, float z, float *da, float *pa, float me, int dtype)
1185 {
1186         int xx, yy, zz, xi, yi, zi;
1187         float xd, yd, zd, d;
1188
1189         float (*distfunc)(float, float, float, float);
1190         switch (dtype) {
1191                 case 1:
1192                         distfunc = dist_Squared;
1193                         break;
1194                 case 2:
1195                         distfunc = dist_Manhattan;
1196                         break;
1197                 case 3:
1198                         distfunc = dist_Chebychev;
1199                         break;
1200                 case 4:
1201                         distfunc = dist_MinkovskyH;
1202                         break;
1203                 case 5:
1204                         distfunc = dist_Minkovsky4;
1205                         break;
1206                 case 6:
1207                         distfunc = dist_Minkovsky;
1208                         break;
1209                 case 0:
1210                 default:
1211                         distfunc = dist_Real;
1212                         break;
1213         }
1214
1215         xi = (int)(floor(x));
1216         yi = (int)(floor(y));
1217         zi = (int)(floor(z));
1218         da[0] = da[1] = da[2] = da[3] = 1e10f;
1219         for (xx = xi - 1; xx <= xi + 1; xx++) {
1220                 for (yy = yi - 1; yy <= yi + 1; yy++) {
1221                         for (zz = zi - 1; zz <= zi + 1; zz++) {
1222                                 const float *p = HASHPNT(xx, yy, zz);
1223                                 xd = x - (p[0] + xx);
1224                                 yd = y - (p[1] + yy);
1225                                 zd = z - (p[2] + zz);
1226                                 d = distfunc(xd, yd, zd, me);
1227                                 if (d < da[0]) {
1228                                         da[3] = da[2];  da[2] = da[1];  da[1] = da[0];  da[0] = d;
1229                                         pa[9] = pa[6];  pa[10] = pa[7];  pa[11] = pa[8];
1230                                         pa[6] = pa[3];  pa[7] = pa[4];  pa[8] = pa[5];
1231                                         pa[3] = pa[0];  pa[4] = pa[1];  pa[5] = pa[2];
1232                                         pa[0] = p[0] + xx;  pa[1] = p[1] + yy;  pa[2] = p[2] + zz;
1233                                 }
1234                                 else if (d < da[1]) {
1235                                         da[3] = da[2];  da[2] = da[1];  da[1] = d;
1236                                         pa[9] = pa[6];  pa[10] = pa[7];  pa[11] = pa[8];
1237                                         pa[6] = pa[3];  pa[7] = pa[4];  pa[8] = pa[5];
1238                                         pa[3] = p[0] + xx;  pa[4] = p[1] + yy;  pa[5] = p[2] + zz;
1239                                 }
1240                                 else if (d < da[2]) {
1241                                         da[3] = da[2];  da[2] = d;
1242                                         pa[9] = pa[6];  pa[10] = pa[7];  pa[11] = pa[8];
1243                                         pa[6] = p[0] + xx;  pa[7] = p[1] + yy;  pa[8] = p[2] + zz;
1244                                 }
1245                                 else if (d < da[3]) {
1246                                         da[3] = d;
1247                                         pa[9] = p[0] + xx;  pa[10] = p[1] + yy;  pa[11] = p[2] + zz;
1248                                 }
1249                         }
1250                 }
1251         }
1252 }
1253
1254 /* returns different feature points for use in BLI_gNoise() */
1255 static float voronoi_F1(float x, float y, float z)
1256 {
1257         float da[4], pa[12];
1258         voronoi(x, y, z, da, pa, 1, 0);
1259         return da[0];
1260 }
1261
1262 static float voronoi_F2(float x, float y, float z)
1263 {
1264         float da[4], pa[12];
1265         voronoi(x, y, z, da, pa, 1, 0);
1266         return da[1];
1267 }
1268
1269 static float voronoi_F3(float x, float y, float z)
1270 {
1271         float da[4], pa[12];
1272         voronoi(x, y, z, da, pa, 1, 0);
1273         return da[2];
1274 }
1275
1276 static float voronoi_F4(float x, float y, float z)
1277 {
1278         float da[4], pa[12];
1279         voronoi(x, y, z, da, pa, 1, 0);
1280         return da[3];
1281 }
1282
1283 static float voronoi_F1F2(float x, float y, float z)
1284 {
1285         float da[4], pa[12];
1286         voronoi(x, y, z, da, pa, 1, 0);
1287         return (da[1] - da[0]);
1288 }
1289
1290 /* Crackle type pattern, just a scale/clamp of F2-F1 */
1291 static float voronoi_Cr(float x, float y, float z)
1292 {
1293         float t = 10 * voronoi_F1F2(x, y, z);
1294         if (t > 1.f) return 1.f;
1295         return t;
1296 }
1297
1298
1299 /* Signed version of all 6 of the above, just 2x-1, not really correct though
1300  * (range is potentially (0, sqrt(6)).
1301  * Used in the musgrave functions */
1302 static float voronoi_F1S(float x, float y, float z)
1303 {
1304         float da[4], pa[12];
1305         voronoi(x, y, z, da, pa, 1, 0);
1306         return (2.0f * da[0] - 1.0f);
1307 }
1308
1309 static float voronoi_F2S(float x, float y, float z)
1310 {
1311         float da[4], pa[12];
1312         voronoi(x, y, z, da, pa, 1, 0);
1313         return (2.0f * da[1] - 1.0f);
1314 }
1315
1316 static float voronoi_F3S(float x, float y, float z)
1317 {
1318         float da[4], pa[12];
1319         voronoi(x, y, z, da, pa, 1, 0);
1320         return (2.0f * da[2] - 1.0f);
1321 }
1322
1323 static float voronoi_F4S(float x, float y, float z)
1324 {
1325         float da[4], pa[12];
1326         voronoi(x, y, z, da, pa, 1, 0);
1327         return (2.0f * da[3] - 1.0f);
1328 }
1329
1330 static float voronoi_F1F2S(float x, float y, float z)
1331 {
1332         float da[4], pa[12];
1333         voronoi(x, y, z, da, pa, 1, 0);
1334         return (2.0f * (da[1] - da[0]) - 1.0f);
1335 }
1336
1337 /* Crackle type pattern, just a scale/clamp of F2-F1 */
1338 static float voronoi_CrS(float x, float y, float z)
1339 {
1340         float t = 10 * voronoi_F1F2(x, y, z);
1341         if (t > 1.f) return 1.f;
1342         return (2.0f * t - 1.0f);
1343 }
1344
1345
1346 /***************/
1347 /* voronoi end */
1348 /***************/
1349
1350 /*************/
1351 /* CELLNOISE */
1352 /*************/
1353
1354 /* returns unsigned cellnoise */
1355 static float cellNoiseU(float x, float y, float z)
1356 {
1357         /* avoid precision issues on unit coordinates */
1358         x = (x + 0.000001f) * 1.00001f;
1359         y = (y + 0.000001f) * 1.00001f;
1360         z = (z + 0.000001f) * 1.00001f;
1361
1362         int xi = (int)(floor(x));
1363         int yi = (int)(floor(y));
1364         int zi = (int)(floor(z));
1365         unsigned int n = xi + yi * 1301 + zi * 314159;
1366         n ^= (n << 13);
1367         return ((float)(n * (n * n * 15731 + 789221) + 1376312589) / 4294967296.0f);
1368 }
1369
1370 /* idem, signed */
1371 float cellNoise(float x, float y, float z)
1372 {
1373         return (2.0f * cellNoiseU(x, y, z) - 1.0f);
1374 }
1375
1376 /* returns a vector/point/color in ca, using point hasharray directly */
1377 void cellNoiseV(float x, float y, float z, float ca[3])
1378 {
1379         /* avoid precision issues on unit coordinates */
1380         x = (x + 0.000001f) * 1.00001f;
1381         y = (y + 0.000001f) * 1.00001f;
1382         z = (z + 0.000001f) * 1.00001f;
1383
1384         int xi = (int)(floor(x));
1385         int yi = (int)(floor(y));
1386         int zi = (int)(floor(z));
1387         const float *p = HASHPNT(xi, yi, zi);
1388         ca[0] = p[0];
1389         ca[1] = p[1];
1390         ca[2] = p[2];
1391 }
1392
1393
1394 /*****************/
1395 /* end cellnoise */
1396 /*****************/
1397
1398 /* newnoise: generic noise function for use with different noisebases */
1399 float BLI_gNoise(float noisesize, float x, float y, float z, int hard, int noisebasis)
1400 {
1401         float (*noisefunc)(float, float, float);
1402
1403         switch (noisebasis) {
1404                 case 1:
1405                         noisefunc = orgPerlinNoiseU;
1406                         break;
1407                 case 2:
1408                         noisefunc = newPerlinU;
1409                         break;
1410                 case 3:
1411                         noisefunc = voronoi_F1;
1412                         break;
1413                 case 4:
1414                         noisefunc = voronoi_F2;
1415                         break;
1416                 case 5:
1417                         noisefunc = voronoi_F3;
1418                         break;
1419                 case 6:
1420                         noisefunc = voronoi_F4;
1421                         break;
1422                 case 7:
1423                         noisefunc = voronoi_F1F2;
1424                         break;
1425                 case 8:
1426                         noisefunc = voronoi_Cr;
1427                         break;
1428                 case 14:
1429                         noisefunc = cellNoiseU;
1430                         break;
1431                 case 0:
1432                 default:
1433                 {
1434                         noisefunc = orgBlenderNoise;
1435                         /* add one to make return value same as BLI_hnoise */
1436                         x += 1;
1437                         y += 1;
1438                         z += 1;
1439                         break;
1440                 }
1441         }
1442
1443         if (noisesize != 0.0f) {
1444                 noisesize = 1.0f / noisesize;
1445                 x *= noisesize;
1446                 y *= noisesize;
1447                 z *= noisesize;
1448         }
1449
1450         if (hard) return fabsf(2.0f * noisefunc(x, y, z) - 1.0f);
1451         return noisefunc(x, y, z);
1452 }
1453
1454 /* newnoise: generic turbulence function for use with different noisebasis */
1455 float BLI_gTurbulence(float noisesize, float x, float y, float z, int oct, int hard, int noisebasis)
1456 {
1457         float (*noisefunc)(float, float, float);
1458         float sum, t, amp = 1, fscale = 1;
1459         int i;
1460
1461         switch (noisebasis) {
1462                 case 1:
1463                         noisefunc = orgPerlinNoiseU;
1464                         break;
1465                 case 2:
1466                         noisefunc = newPerlinU;
1467                         break;
1468                 case 3:
1469                         noisefunc = voronoi_F1;
1470                         break;
1471                 case 4:
1472                         noisefunc = voronoi_F2;
1473                         break;
1474                 case 5:
1475                         noisefunc = voronoi_F3;
1476                         break;
1477                 case 6:
1478                         noisefunc = voronoi_F4;
1479                         break;
1480                 case 7:
1481                         noisefunc = voronoi_F1F2;
1482                         break;
1483                 case 8:
1484                         noisefunc = voronoi_Cr;
1485                         break;
1486                 case 14:
1487                         noisefunc = cellNoiseU;
1488                         break;
1489                 case 0:
1490                 default:
1491                         noisefunc = orgBlenderNoise;
1492                         x += 1;
1493                         y += 1;
1494                         z += 1;
1495                         break;
1496         }
1497
1498         if (noisesize != 0.0f) {
1499                 noisesize = 1.0f / noisesize;
1500                 x *= noisesize;
1501                 y *= noisesize;
1502                 z *= noisesize;
1503         }
1504
1505         sum = 0;
1506         for (i = 0; i <= oct; i++, amp *= 0.5f, fscale *= 2.0f) {
1507                 t = noisefunc(fscale * x, fscale * y, fscale * z);
1508                 if (hard) t = fabsf(2.0f * t - 1.0f);
1509                 sum += t * amp;
1510         }
1511
1512         sum *= ((float)(1 << oct) / (float)((1 << (oct + 1)) - 1));
1513
1514         return sum;
1515
1516 }
1517
1518
1519 /*
1520  * The following code is based on Ken Musgrave's explanations and sample
1521  * source code in the book "Texturing and Modeling: A procedural approach"
1522  */
1523
1524 /*
1525  * Procedural fBm evaluated at "point"; returns value stored in "value".
1526  *
1527  * Parameters:
1528  *    ``H''  is the fractal increment parameter
1529  *    ``lacunarity''  is the gap between successive frequencies
1530  *    ``octaves''  is the number of frequencies in the fBm
1531  */
1532 float mg_fBm(float x, float y, float z, float H, float lacunarity, float octaves, int noisebasis)
1533 {
1534         float rmd, value = 0.0, pwr = 1.0, pwHL = powf(lacunarity, -H);
1535         int i;
1536
1537         float (*noisefunc)(float, float, float);
1538         switch (noisebasis) {
1539                 case 1:
1540                         noisefunc = orgPerlinNoise;
1541                         break;
1542                 case 2:
1543                         noisefunc = newPerlin;
1544                         break;
1545                 case 3:
1546                         noisefunc = voronoi_F1S;
1547                         break;
1548                 case 4:
1549                         noisefunc = voronoi_F2S;
1550                         break;
1551                 case 5:
1552                         noisefunc = voronoi_F3S;
1553                         break;
1554                 case 6:
1555                         noisefunc = voronoi_F4S;
1556                         break;
1557                 case 7:
1558                         noisefunc = voronoi_F1F2S;
1559                         break;
1560                 case 8:
1561                         noisefunc = voronoi_CrS;
1562                         break;
1563                 case 14:
1564                         noisefunc = cellNoise;
1565                         break;
1566                 case 0:
1567                 default:
1568                 {
1569                         noisefunc = orgBlenderNoiseS;
1570                         break;
1571                 }
1572         }
1573
1574         for (i = 0; i < (int)octaves; i++) {
1575                 value += noisefunc(x, y, z) * pwr;
1576                 pwr *= pwHL;
1577                 x *= lacunarity;
1578                 y *= lacunarity;
1579                 z *= lacunarity;
1580         }
1581
1582         rmd = octaves - floorf(octaves);
1583         if (rmd != 0.f) value += rmd * noisefunc(x, y, z) * pwr;
1584
1585         return value;
1586
1587 } /* fBm() */
1588
1589
1590 /*
1591  * Procedural multifractal evaluated at "point";
1592  * returns value stored in "value".
1593  *
1594  * Parameters:
1595  *    ``H''  determines the highest fractal dimension
1596  *    ``lacunarity''  is gap between successive frequencies
1597  *    ``octaves''  is the number of frequencies in the fBm
1598  *    ``offset''  is the zero offset, which determines multifractality (NOT USED??)
1599  */
1600
1601 /* this one is in fact rather confusing,
1602  * there seem to be errors in the original source code (in all three versions of proc.text&mod),
1603  * I modified it to something that made sense to me, so it might be wrong... */
1604 float mg_MultiFractal(float x, float y, float z, float H, float lacunarity, float octaves, int noisebasis)
1605 {
1606         float rmd, value = 1.0, pwr = 1.0, pwHL = powf(lacunarity, -H);
1607         int i;
1608
1609         float (*noisefunc)(float, float, float);
1610         switch (noisebasis) {
1611                 case 1:
1612                         noisefunc = orgPerlinNoise;
1613                         break;
1614                 case 2:
1615                         noisefunc = newPerlin;
1616                         break;
1617                 case 3:
1618                         noisefunc = voronoi_F1S;
1619                         break;
1620                 case 4:
1621                         noisefunc = voronoi_F2S;
1622                         break;
1623                 case 5:
1624                         noisefunc = voronoi_F3S;
1625                         break;
1626                 case 6:
1627                         noisefunc = voronoi_F4S;
1628                         break;
1629                 case 7:
1630                         noisefunc = voronoi_F1F2S;
1631                         break;
1632                 case 8:
1633                         noisefunc = voronoi_CrS;
1634                         break;
1635                 case 14:
1636                         noisefunc = cellNoise;
1637                         break;
1638                 case 0:
1639                 default:
1640                 {
1641                         noisefunc = orgBlenderNoiseS;
1642                         break;
1643                 }
1644         }
1645
1646         for (i = 0; i < (int)octaves; i++) {
1647                 value *= (pwr * noisefunc(x, y, z) + 1.0f);
1648                 pwr *= pwHL;
1649                 x *= lacunarity;
1650                 y *= lacunarity;
1651                 z *= lacunarity;
1652         }
1653         rmd = octaves - floorf(octaves);
1654         if (rmd != 0.0f) value *= (rmd * noisefunc(x, y, z) * pwr + 1.0f);
1655
1656         return value;
1657
1658 } /* multifractal() */
1659
1660 /*
1661  * Heterogeneous procedural terrain function: stats by altitude method.
1662  * Evaluated at "point"; returns value stored in "value".
1663  *
1664  * Parameters:
1665  *       ``H''  determines the fractal dimension of the roughest areas
1666  *       ``lacunarity''  is the gap between successive frequencies
1667  *       ``octaves''  is the number of frequencies in the fBm
1668  *       ``offset''  raises the terrain from `sea level'
1669  */
1670 float mg_HeteroTerrain(float x, float y, float z, float H, float lacunarity, float octaves, float offset, int noisebasis)
1671 {
1672         float value, increment, rmd;
1673         int i;
1674         float pwHL = powf(lacunarity, -H);
1675         float pwr = pwHL;   /* starts with i=1 instead of 0 */
1676
1677         float (*noisefunc)(float, float, float);
1678         switch (noisebasis) {
1679                 case 1:
1680                         noisefunc = orgPerlinNoise;
1681                         break;
1682                 case 2:
1683                         noisefunc = newPerlin;
1684                         break;
1685                 case 3:
1686                         noisefunc = voronoi_F1S;
1687                         break;
1688                 case 4:
1689                         noisefunc = voronoi_F2S;
1690                         break;
1691                 case 5:
1692                         noisefunc = voronoi_F3S;
1693                         break;
1694                 case 6:
1695                         noisefunc = voronoi_F4S;
1696                         break;
1697                 case 7:
1698                         noisefunc = voronoi_F1F2S;
1699                         break;
1700                 case 8:
1701                         noisefunc = voronoi_CrS;
1702                         break;
1703                 case 14:
1704                         noisefunc = cellNoise;
1705                         break;
1706                 case 0:
1707                 default:
1708                 {
1709                         noisefunc = orgBlenderNoiseS;
1710                         break;
1711                 }
1712         }
1713
1714         /* first unscaled octave of function; later octaves are scaled */
1715         value = offset + noisefunc(x, y, z);
1716         x *= lacunarity;
1717         y *= lacunarity;
1718         z *= lacunarity;
1719
1720         for (i = 1; i < (int)octaves; i++) {
1721                 increment = (noisefunc(x, y, z) + offset) * pwr * value;
1722                 value += increment;
1723                 pwr *= pwHL;
1724                 x *= lacunarity;
1725                 y *= lacunarity;
1726                 z *= lacunarity;
1727         }
1728
1729         rmd = octaves - floorf(octaves);
1730         if (rmd != 0.0f) {
1731                 increment = (noisefunc(x, y, z) + offset) * pwr * value;
1732                 value += rmd * increment;
1733         }
1734         return value;
1735 }
1736
1737
1738 /* Hybrid additive/multiplicative multifractal terrain model.
1739  *
1740  * Some good parameter values to start with:
1741  *
1742  *      H:           0.25
1743  *      offset:      0.7
1744  */
1745 float mg_HybridMultiFractal(float x, float y, float z, float H, float lacunarity, float octaves, float offset, float gain, int noisebasis)
1746 {
1747         float result, signal, weight, rmd;
1748         int i;
1749         float pwHL = powf(lacunarity, -H);
1750         float pwr = pwHL;   /* starts with i=1 instead of 0 */
1751         float (*noisefunc)(float, float, float);
1752
1753         switch (noisebasis) {
1754                 case 1:
1755                         noisefunc = orgPerlinNoise;
1756                         break;
1757                 case 2:
1758                         noisefunc = newPerlin;
1759                         break;
1760                 case 3:
1761                         noisefunc = voronoi_F1S;
1762                         break;
1763                 case 4:
1764                         noisefunc = voronoi_F2S;
1765                         break;
1766                 case 5:
1767                         noisefunc = voronoi_F3S;
1768                         break;
1769                 case 6:
1770                         noisefunc = voronoi_F4S;
1771                         break;
1772                 case 7:
1773                         noisefunc = voronoi_F1F2S;
1774                         break;
1775                 case 8:
1776                         noisefunc = voronoi_CrS;
1777                         break;
1778                 case 14:
1779                         noisefunc = cellNoise;
1780                         break;
1781                 case 0:
1782                 default:
1783                 {
1784                         noisefunc = orgBlenderNoiseS;
1785                         break;
1786                 }
1787         }
1788
1789         result = noisefunc(x, y, z) + offset;
1790         weight = gain * result;
1791         x *= lacunarity;
1792         y *= lacunarity;
1793         z *= lacunarity;
1794
1795         for (i = 1; (weight > 0.001f) && (i < (int)octaves); i++) {
1796                 if (weight > 1.0f) weight = 1.0f;
1797                 signal = (noisefunc(x, y, z) + offset) * pwr;
1798                 pwr *= pwHL;
1799                 result += weight * signal;
1800                 weight *= gain * signal;
1801                 x *= lacunarity;
1802                 y *= lacunarity;
1803                 z *= lacunarity;
1804         }
1805
1806         rmd = octaves - floorf(octaves);
1807         if (rmd != 0.f) result += rmd * ((noisefunc(x, y, z) + offset) * pwr);
1808
1809         return result;
1810
1811 } /* HybridMultifractal() */
1812
1813
1814 /* Ridged multifractal terrain model.
1815  *
1816  * Some good parameter values to start with:
1817  *
1818  *      H:           1.0
1819  *      offset:      1.0
1820  *      gain:        2.0
1821  */
1822 float mg_RidgedMultiFractal(float x, float y, float z, float H, float lacunarity, float octaves, float offset, float gain, int noisebasis)
1823 {
1824         float result, signal, weight;
1825         int i;
1826         float pwHL = powf(lacunarity, -H);
1827         float pwr = pwHL;   /* starts with i=1 instead of 0 */
1828
1829         float (*noisefunc)(float, float, float);
1830         switch (noisebasis) {
1831                 case 1:
1832                         noisefunc = orgPerlinNoise;
1833                         break;
1834                 case 2:
1835                         noisefunc = newPerlin;
1836                         break;
1837                 case 3:
1838                         noisefunc = voronoi_F1S;
1839                         break;
1840                 case 4:
1841                         noisefunc = voronoi_F2S;
1842                         break;
1843                 case 5:
1844                         noisefunc = voronoi_F3S;
1845                         break;
1846                 case 6:
1847                         noisefunc = voronoi_F4S;
1848                         break;
1849                 case 7:
1850                         noisefunc = voronoi_F1F2S;
1851                         break;
1852                 case 8:
1853                         noisefunc = voronoi_CrS;
1854                         break;
1855                 case 14:
1856                         noisefunc = cellNoise;
1857                         break;
1858                 case 0:
1859                 default:
1860                 {
1861                         noisefunc = orgBlenderNoiseS;
1862                         break;
1863                 }
1864         }
1865
1866         signal = offset - fabsf(noisefunc(x, y, z));
1867         signal *= signal;
1868         result = signal;
1869
1870
1871         for (i = 1; i < (int)octaves; i++) {
1872                 x *= lacunarity;
1873                 y *= lacunarity;
1874                 z *= lacunarity;
1875                 weight = signal * gain;
1876                 if      (weight > 1.0f) weight = 1.0f;
1877                 else if (weight < 0.0f) weight = 0.0f;
1878                 signal = offset - fabsf(noisefunc(x, y, z));
1879                 signal *= signal;
1880                 signal *= weight;
1881                 result += signal * pwr;
1882                 pwr *= pwHL;
1883         }
1884
1885         return result;
1886 } /* RidgedMultifractal() */
1887
1888 /* "Variable Lacunarity Noise"
1889  * A distorted variety of Perlin noise.
1890  */
1891 float mg_VLNoise(float x, float y, float z, float distortion, int nbas1, int nbas2)
1892 {
1893         float rv[3];
1894         float (*noisefunc1)(float, float, float);
1895         float (*noisefunc2)(float, float, float);
1896
1897         switch (nbas1) {
1898                 case 1:
1899                         noisefunc1 = orgPerlinNoise;
1900                         break;
1901                 case 2:
1902                         noisefunc1 = newPerlin;
1903                         break;
1904                 case 3:
1905                         noisefunc1 = voronoi_F1S;
1906                         break;
1907                 case 4:
1908                         noisefunc1 = voronoi_F2S;
1909                         break;
1910                 case 5:
1911                         noisefunc1 = voronoi_F3S;
1912                         break;
1913                 case 6:
1914                         noisefunc1 = voronoi_F4S;
1915                         break;
1916                 case 7:
1917                         noisefunc1 = voronoi_F1F2S;
1918                         break;
1919                 case 8:
1920                         noisefunc1 = voronoi_CrS;
1921                         break;
1922                 case 14:
1923                         noisefunc1 = cellNoise;
1924                         break;
1925                 case 0:
1926                 default:
1927                 {
1928                         noisefunc1 = orgBlenderNoiseS;
1929                         break;
1930                 }
1931         }
1932
1933         switch (nbas2) {
1934                 case 1:
1935                         noisefunc2 = orgPerlinNoise;
1936                         break;
1937                 case 2:
1938                         noisefunc2 = newPerlin;
1939                         break;
1940                 case 3:
1941                         noisefunc2 = voronoi_F1S;
1942                         break;
1943                 case 4:
1944                         noisefunc2 = voronoi_F2S;
1945                         break;
1946                 case 5:
1947                         noisefunc2 = voronoi_F3S;
1948                         break;
1949                 case 6:
1950                         noisefunc2 = voronoi_F4S;
1951                         break;
1952                 case 7:
1953                         noisefunc2 = voronoi_F1F2S;
1954                         break;
1955                 case 8:
1956                         noisefunc2 = voronoi_CrS;
1957                         break;
1958                 case 14:
1959                         noisefunc2 = cellNoise;
1960                         break;
1961                 case 0:
1962                 default:
1963                 {
1964                         noisefunc2 = orgBlenderNoiseS;
1965                         break;
1966                 }
1967         }
1968
1969         /* get a random vector and scale the randomization */
1970         rv[0] = noisefunc1(x + 13.5f, y + 13.5f, z + 13.5f) * distortion;
1971         rv[1] = noisefunc1(x, y, z) * distortion;
1972         rv[2] = noisefunc1(x - 13.5f, y - 13.5f, z - 13.5f) * distortion;
1973         return noisefunc2(x + rv[0], y + rv[1], z + rv[2]);   /* distorted-domain noise */
1974 }
1975
1976 /****************/
1977 /* musgrave end */
1978 /****************/