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