3 Copyright (C) 2010-2013 celeron55, Perttu Ahola <celeron55@gmail.com>
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.
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.
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.
21 #include "mathconstants.h"
24 #include "../constants.h" // BS, MAP_BLOCKSIZE
25 #include "../noise.h" // PseudoRandom, PcgRandom
26 #include "../threading/mutex_auto_lock.h"
30 UNORDERED_MAP<u16, std::vector<v3s16> > FacePositionCache::m_cache;
31 Mutex FacePositionCache::m_cache_mutex;
32 // Calculate the borders of a "d-radius" cube
33 // TODO: Make it work without mutex and data races, probably thread-local
34 std::vector<v3s16> FacePositionCache::getFacePositions(u16 d)
36 MutexAutoLock cachelock(m_cache_mutex);
37 if (m_cache.find(d) != m_cache.end())
40 generateFacePosition(d);
45 void FacePositionCache::generateFacePosition(u16 d)
47 m_cache[d] = std::vector<v3s16>();
49 m_cache[d].push_back(v3s16(0,0,0));
54 This is an optimized sequence of coordinates.
56 m_cache[d].push_back(v3s16( 0, 1, 0)); // top
57 m_cache[d].push_back(v3s16( 0, 0, 1)); // back
58 m_cache[d].push_back(v3s16(-1, 0, 0)); // left
59 m_cache[d].push_back(v3s16( 1, 0, 0)); // right
60 m_cache[d].push_back(v3s16( 0, 0,-1)); // front
61 m_cache[d].push_back(v3s16( 0,-1, 0)); // bottom
63 m_cache[d].push_back(v3s16(-1, 0, 1)); // back left
64 m_cache[d].push_back(v3s16( 1, 0, 1)); // back right
65 m_cache[d].push_back(v3s16(-1, 0,-1)); // front left
66 m_cache[d].push_back(v3s16( 1, 0,-1)); // front right
67 m_cache[d].push_back(v3s16(-1,-1, 0)); // bottom left
68 m_cache[d].push_back(v3s16( 1,-1, 0)); // bottom right
69 m_cache[d].push_back(v3s16( 0,-1, 1)); // bottom back
70 m_cache[d].push_back(v3s16( 0,-1,-1)); // bottom front
71 m_cache[d].push_back(v3s16(-1, 1, 0)); // top left
72 m_cache[d].push_back(v3s16( 1, 1, 0)); // top right
73 m_cache[d].push_back(v3s16( 0, 1, 1)); // top back
74 m_cache[d].push_back(v3s16( 0, 1,-1)); // top front
76 m_cache[d].push_back(v3s16(-1, 1, 1)); // top back-left
77 m_cache[d].push_back(v3s16( 1, 1, 1)); // top back-right
78 m_cache[d].push_back(v3s16(-1, 1,-1)); // top front-left
79 m_cache[d].push_back(v3s16( 1, 1,-1)); // top front-right
80 m_cache[d].push_back(v3s16(-1,-1, 1)); // bottom back-left
81 m_cache[d].push_back(v3s16( 1,-1, 1)); // bottom back-right
82 m_cache[d].push_back(v3s16(-1,-1,-1)); // bottom front-left
83 m_cache[d].push_back(v3s16( 1,-1,-1)); // bottom front-right
88 // Take blocks in all sides, starting from y=0 and going +-y
89 for(s16 y=0; y<=d-1; y++) {
90 // Left and right side, including borders
91 for(s16 z=-d; z<=d; z++) {
92 m_cache[d].push_back(v3s16(d,y,z));
93 m_cache[d].push_back(v3s16(-d,y,z));
95 m_cache[d].push_back(v3s16(d,-y,z));
96 m_cache[d].push_back(v3s16(-d,-y,z));
99 // Back and front side, excluding borders
100 for(s16 x=-d+1; x<=d-1; x++) {
101 m_cache[d].push_back(v3s16(x,y,d));
102 m_cache[d].push_back(v3s16(x,y,-d));
104 m_cache[d].push_back(v3s16(x,-y,d));
105 m_cache[d].push_back(v3s16(x,-y,-d));
110 // Take the bottom and top face with borders
111 // -d<x<d, y=+-d, -d<z<d
112 for(s16 x=-d; x<=d; x++)
113 for(s16 z=-d; z<=d; z++) {
114 m_cache[d].push_back(v3s16(x,-d,z));
115 m_cache[d].push_back(v3s16(x,d,z));
127 return g_pcgrand.next();
130 void mysrand(unsigned int seed)
132 g_pcgrand.seed(seed);
135 void myrand_bytes(void *out, size_t len)
137 g_pcgrand.bytes(out, len);
140 int myrand_range(int min, int max)
142 return g_pcgrand.range(min, max);
147 64-bit unaligned version of MurmurHash
149 u64 murmur_hash_64_ua(const void *key, int len, unsigned int seed)
151 const u64 m = 0xc6a4a7935bd1e995ULL;
153 u64 h = seed ^ (len * m);
155 const u64 *data = (const u64 *)key;
156 const u64 *end = data + (len / 8);
158 while (data != end) {
160 memcpy(&k, data, sizeof(u64));
171 const unsigned char *data2 = (const unsigned char *)data;
173 case 7: h ^= (u64)data2[6] << 48;
174 case 6: h ^= (u64)data2[5] << 40;
175 case 5: h ^= (u64)data2[4] << 32;
176 case 4: h ^= (u64)data2[3] << 24;
177 case 3: h ^= (u64)data2[2] << 16;
178 case 2: h ^= (u64)data2[1] << 8;
179 case 1: h ^= (u64)data2[0];
191 blockpos_b: position of block in block coordinates
192 camera_pos: position of camera in nodes
193 camera_dir: an unit vector pointing to camera direction
195 distance_ptr: return location for distance from the camera
197 bool isBlockInSight(v3s16 blockpos_b, v3f camera_pos, v3f camera_dir,
198 f32 camera_fov, f32 range, f32 *distance_ptr)
200 // Maximum radius of a block. The magic number is
201 // sqrt(3.0) / 2.0 in literal form.
202 const f32 block_max_radius = 0.866025403784 * MAP_BLOCKSIZE * BS;
204 v3s16 blockpos_nodes = blockpos_b * MAP_BLOCKSIZE;
206 // Block center position
208 ((float)blockpos_nodes.X + MAP_BLOCKSIZE/2) * BS,
209 ((float)blockpos_nodes.Y + MAP_BLOCKSIZE/2) * BS,
210 ((float)blockpos_nodes.Z + MAP_BLOCKSIZE/2) * BS
213 // Block position relative to camera
214 v3f blockpos_relative = blockpos - camera_pos;
217 f32 d = MYMAX(0, blockpos_relative.getLength() - block_max_radius);
222 // If block is far away, it's not in sight
226 // If block is (nearly) touching the camera, don't
227 // bother validating further (that is, render it anyway)
231 // Adjust camera position, for purposes of computing the angle,
232 // such that a block that has any portion visible with the
233 // current camera position will have the center visible at the
235 f32 adjdist = block_max_radius / cos((M_PI - camera_fov) / 2);
237 // Block position relative to adjusted camera
238 v3f blockpos_adj = blockpos - (camera_pos - camera_dir * adjdist);
240 // Distance in camera direction (+=front, -=back)
241 f32 dforward = blockpos_adj.dotProduct(camera_dir);
243 // Cosine of the angle between the camera direction
244 // and the block direction (camera_dir is an unit vector)
245 f32 cosangle = dforward / blockpos_adj.getLength();
247 // If block is not in the field of view, skip it
248 // HOTFIX: use sligthly increased angle (+10%) to fix too agressive
249 // culling. Somebody have to find out whats wrong with the math here.
250 // Previous value: camera_fov / 2
251 if(cosangle < cos(camera_fov * 0.55))