Line data Source code
1 : /*
2 : Minetest
3 : Copyright (C) 2010-2013 celeron55, Perttu Ahola <celeron55@gmail.com>
4 :
5 : This program is free software; you can redistribute it and/or modify
6 : it under the terms of the GNU Lesser General Public License as published by
7 : the Free Software Foundation; either version 2.1 of the License, or
8 : (at your option) any later version.
9 :
10 : This program is distributed in the hope that it will be useful,
11 : but WITHOUT ANY WARRANTY; without even the implied warranty of
12 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 : GNU Lesser General Public License for more details.
14 :
15 : You should have received a copy of the GNU Lesser General Public License along
16 : with this program; if not, write to the Free Software Foundation, Inc.,
17 : 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18 : */
19 :
20 : #include "numeric.h"
21 : #include "mathconstants.h"
22 :
23 : #include "log.h"
24 : #include "../constants.h" // BS, MAP_BLOCKSIZE
25 : #include "../noise.h" // PseudoRandom, PcgRandom
26 : #include <string.h>
27 : #include <iostream>
28 :
29 1 : std::map<u16, std::vector<v3s16> > FacePositionCache::m_cache;
30 : // Calculate the borders of a "d-radius" cube
31 0 : std::vector<v3s16> FacePositionCache::getFacePositions(u16 d)
32 : {
33 0 : if (m_cache.find(d) != m_cache.end())
34 0 : return m_cache[d];
35 :
36 0 : generateFacePosition(d);
37 0 : return m_cache[d];
38 :
39 : }
40 :
41 0 : void FacePositionCache::generateFacePosition(u16 d)
42 : {
43 0 : m_cache[d] = std::vector<v3s16>();
44 0 : if(d == 0) {
45 0 : m_cache[d].push_back(v3s16(0,0,0));
46 0 : return;
47 : }
48 0 : if(d == 1) {
49 : /*
50 : This is an optimized sequence of coordinates.
51 : */
52 0 : m_cache[d].push_back(v3s16( 0, 1, 0)); // top
53 0 : m_cache[d].push_back(v3s16( 0, 0, 1)); // back
54 0 : m_cache[d].push_back(v3s16(-1, 0, 0)); // left
55 0 : m_cache[d].push_back(v3s16( 1, 0, 0)); // right
56 0 : m_cache[d].push_back(v3s16( 0, 0,-1)); // front
57 0 : m_cache[d].push_back(v3s16( 0,-1, 0)); // bottom
58 : // 6
59 0 : m_cache[d].push_back(v3s16(-1, 0, 1)); // back left
60 0 : m_cache[d].push_back(v3s16( 1, 0, 1)); // back right
61 0 : m_cache[d].push_back(v3s16(-1, 0,-1)); // front left
62 0 : m_cache[d].push_back(v3s16( 1, 0,-1)); // front right
63 0 : m_cache[d].push_back(v3s16(-1,-1, 0)); // bottom left
64 0 : m_cache[d].push_back(v3s16( 1,-1, 0)); // bottom right
65 0 : m_cache[d].push_back(v3s16( 0,-1, 1)); // bottom back
66 0 : m_cache[d].push_back(v3s16( 0,-1,-1)); // bottom front
67 0 : m_cache[d].push_back(v3s16(-1, 1, 0)); // top left
68 0 : m_cache[d].push_back(v3s16( 1, 1, 0)); // top right
69 0 : m_cache[d].push_back(v3s16( 0, 1, 1)); // top back
70 0 : m_cache[d].push_back(v3s16( 0, 1,-1)); // top front
71 : // 18
72 0 : m_cache[d].push_back(v3s16(-1, 1, 1)); // top back-left
73 0 : m_cache[d].push_back(v3s16( 1, 1, 1)); // top back-right
74 0 : m_cache[d].push_back(v3s16(-1, 1,-1)); // top front-left
75 0 : m_cache[d].push_back(v3s16( 1, 1,-1)); // top front-right
76 0 : m_cache[d].push_back(v3s16(-1,-1, 1)); // bottom back-left
77 0 : m_cache[d].push_back(v3s16( 1,-1, 1)); // bottom back-right
78 0 : m_cache[d].push_back(v3s16(-1,-1,-1)); // bottom front-left
79 0 : m_cache[d].push_back(v3s16( 1,-1,-1)); // bottom front-right
80 : // 26
81 0 : return;
82 : }
83 :
84 : // Take blocks in all sides, starting from y=0 and going +-y
85 0 : for(s16 y=0; y<=d-1; y++) {
86 : // Left and right side, including borders
87 0 : for(s16 z=-d; z<=d; z++) {
88 0 : m_cache[d].push_back(v3s16(d,y,z));
89 0 : m_cache[d].push_back(v3s16(-d,y,z));
90 0 : if(y != 0) {
91 0 : m_cache[d].push_back(v3s16(d,-y,z));
92 0 : m_cache[d].push_back(v3s16(-d,-y,z));
93 : }
94 : }
95 : // Back and front side, excluding borders
96 0 : for(s16 x=-d+1; x<=d-1; x++) {
97 0 : m_cache[d].push_back(v3s16(x,y,d));
98 0 : m_cache[d].push_back(v3s16(x,y,-d));
99 0 : if(y != 0) {
100 0 : m_cache[d].push_back(v3s16(x,-y,d));
101 0 : m_cache[d].push_back(v3s16(x,-y,-d));
102 : }
103 : }
104 : }
105 :
106 : // Take the bottom and top face with borders
107 : // -d<x<d, y=+-d, -d<z<d
108 0 : for(s16 x=-d; x<=d; x++)
109 0 : for(s16 z=-d; z<=d; z++) {
110 0 : m_cache[d].push_back(v3s16(x,-d,z));
111 0 : m_cache[d].push_back(v3s16(x,d,z));
112 : }
113 : }
114 :
115 : /*
116 : myrand
117 : */
118 :
119 1 : PcgRandom g_pcgrand;
120 :
121 67 : u32 myrand()
122 : {
123 67 : return g_pcgrand.next();
124 : }
125 :
126 1 : void mysrand(unsigned int seed)
127 : {
128 1 : g_pcgrand.seed(seed);
129 1 : }
130 :
131 0 : void myrand_bytes(void *out, size_t len)
132 : {
133 0 : g_pcgrand.bytes(out, len);
134 0 : }
135 :
136 73862 : int myrand_range(int min, int max)
137 : {
138 73862 : return g_pcgrand.range(min, max);
139 : }
140 :
141 :
142 : /*
143 : 64-bit unaligned version of MurmurHash
144 : */
145 0 : u64 murmur_hash_64_ua(const void *key, int len, unsigned int seed)
146 : {
147 0 : const u64 m = 0xc6a4a7935bd1e995ULL;
148 0 : const int r = 47;
149 0 : u64 h = seed ^ (len * m);
150 :
151 0 : const u64 *data = (const u64 *)key;
152 0 : const u64 *end = data + (len / 8);
153 :
154 0 : while (data != end) {
155 : u64 k;
156 0 : memcpy(&k, data, sizeof(u64));
157 0 : data++;
158 :
159 0 : k *= m;
160 0 : k ^= k >> r;
161 0 : k *= m;
162 :
163 0 : h ^= k;
164 0 : h *= m;
165 : }
166 :
167 0 : const unsigned char *data2 = (const unsigned char *)data;
168 0 : switch (len & 7) {
169 0 : case 7: h ^= (u64)data2[6] << 48;
170 0 : case 6: h ^= (u64)data2[5] << 40;
171 0 : case 5: h ^= (u64)data2[4] << 32;
172 0 : case 4: h ^= (u64)data2[3] << 24;
173 0 : case 3: h ^= (u64)data2[2] << 16;
174 0 : case 2: h ^= (u64)data2[1] << 8;
175 0 : case 1: h ^= (u64)data2[0];
176 0 : h *= m;
177 : }
178 :
179 0 : h ^= h >> r;
180 0 : h *= m;
181 0 : h ^= h >> r;
182 :
183 0 : return h;
184 : }
185 :
186 : /*
187 : blockpos: position of block in block coordinates
188 : camera_pos: position of camera in nodes
189 : camera_dir: an unit vector pointing to camera direction
190 : range: viewing range
191 : */
192 240346 : bool isBlockInSight(v3s16 blockpos_b, v3f camera_pos, v3f camera_dir,
193 : f32 camera_fov, f32 range, f32 *distance_ptr)
194 : {
195 240346 : v3s16 blockpos_nodes = blockpos_b * MAP_BLOCKSIZE;
196 :
197 : // Block center position
198 : v3f blockpos(
199 240346 : ((float)blockpos_nodes.X + MAP_BLOCKSIZE/2) * BS,
200 240346 : ((float)blockpos_nodes.Y + MAP_BLOCKSIZE/2) * BS,
201 240346 : ((float)blockpos_nodes.Z + MAP_BLOCKSIZE/2) * BS
202 721038 : );
203 :
204 : // Block position relative to camera
205 240346 : v3f blockpos_relative = blockpos - camera_pos;
206 :
207 : // Total distance
208 240346 : f32 d = blockpos_relative.getLength();
209 :
210 240346 : if(distance_ptr)
211 240346 : *distance_ptr = d;
212 :
213 : // If block is far away, it's not in sight
214 240346 : if(d > range)
215 3256 : return false;
216 :
217 : // Maximum radius of a block. The magic number is
218 : // sqrt(3.0) / 2.0 in literal form.
219 237090 : f32 block_max_radius = 0.866025403784 * MAP_BLOCKSIZE * BS;
220 :
221 : // If block is (nearly) touching the camera, don't
222 : // bother validating further (that is, render it anyway)
223 237090 : if(d < block_max_radius)
224 8262 : return true;
225 :
226 : // Adjust camera position, for purposes of computing the angle,
227 : // such that a block that has any portion visible with the
228 : // current camera position will have the center visible at the
229 : // adjusted postion
230 228828 : f32 adjdist = block_max_radius / cos((M_PI - camera_fov) / 2);
231 :
232 : // Block position relative to adjusted camera
233 228828 : v3f blockpos_adj = blockpos - (camera_pos - camera_dir * adjdist);
234 :
235 : // Distance in camera direction (+=front, -=back)
236 228828 : f32 dforward = blockpos_adj.dotProduct(camera_dir);
237 :
238 : // Cosine of the angle between the camera direction
239 : // and the block direction (camera_dir is an unit vector)
240 228828 : f32 cosangle = dforward / blockpos_adj.getLength();
241 :
242 : // If block is not in the field of view, skip it
243 228828 : if(cosangle < cos(camera_fov / 2))
244 58468 : return false;
245 :
246 170360 : return true;
247 3 : }
|