1 /*
2 * Copyright (C) 2010-2011 Dmitry Marakasov
3 *
4 * This file is part of glosm.
5 *
6 * glosm is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * glosm is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with glosm. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include <glosm/TileManager.hh>
21
22 #include <glosm/Viewer.hh>
23 #include <glosm/Geometry.hh>
24 #include <glosm/GeometryDatasource.hh>
25 #include <glosm/GeometryOperations.hh>
26 #include <glosm/Tile.hh>
27 #include <glosm/Exception.hh>
28
29 #include <glosm/util/gl.h>
30
31 #include <algorithm>
32 #include <cstdio>
33
TileManager(const Projection projection)34 TileManager::TileManager(const Projection projection): projection_(projection), loading_(-1, -1, -1) {
35 generation_ = 0;
36 thread_die_flag_ = false;
37
38 int errn;
39
40 if ((errn = pthread_mutex_init(&tiles_mutex_, 0)) != 0)
41 throw SystemError(errn) << "pthread_mutex_init failed";
42
43 if ((errn = pthread_mutex_init(&queue_mutex_, 0)) != 0) {
44 pthread_mutex_destroy(&tiles_mutex_);
45 throw SystemError(errn) << "pthread_mutex_init failed";
46 }
47
48 if ((errn = pthread_cond_init(&queue_cond_, 0)) != 0) {
49 pthread_mutex_destroy(&tiles_mutex_);
50 pthread_mutex_destroy(&queue_mutex_);
51 throw SystemError(errn) << "pthread_cond_init failed";
52 }
53
54 if ((errn = pthread_create(&loading_thread_, NULL, LoadingThreadFuncWrapper, (void*)this)) != 0) {
55 pthread_mutex_destroy(&tiles_mutex_);
56 pthread_mutex_destroy(&queue_mutex_);
57 pthread_cond_destroy(&queue_cond_);
58 throw SystemError(errn) << "pthread_create failed";
59 }
60
61 level_ = 12;
62 range_ = 1000.0f;
63 flags_ = GeometryDatasource::EVERYTHING;
64 height_effect_ = false;
65
66 total_size_ = 0;
67 tile_count_ = 0;
68 }
69
70
~TileManager()71 TileManager::~TileManager() {
72 thread_die_flag_ = true;
73 pthread_cond_signal(&queue_cond_);
74
75 /* @todo check exit code? */
76 pthread_join(loading_thread_, NULL);
77
78 pthread_cond_destroy(&queue_cond_);
79 pthread_mutex_destroy(&queue_mutex_);
80 pthread_mutex_destroy(&tiles_mutex_);
81
82 fprintf(stderr, "Tile statistics before cleanup: %d tiles, %d bytes\n", tile_count_, total_size_);
83 RecDestroyTiles(&root_);
84 fprintf(stderr, "Tile statistics after cleanup: %d tiles, %d bytes\n", tile_count_, total_size_);
85 }
86
87 /*
88 * recursive quadtree processing
89 */
90
RecLoadTilesBBox(RecLoadTilesInfo & info,QuadNode ** pnode,int level,int x,int y)91 void TileManager::RecLoadTilesBBox(RecLoadTilesInfo& info, QuadNode** pnode, int level, int x, int y) {
92 QuadNode* node;
93
94 if (*pnode == NULL) {
95 /* no node; check if it's in bbox and if yes, create it */
96 BBoxi bbox = BBoxi::ForGeoTile(level, x, y);
97 if (!info.bbox->Intersects(bbox))
98 return;
99 node = *pnode = new QuadNode;
100 node->bbox = bbox;
101 } else {
102 /* node exists, visit it if it's in bbox */
103 node = *pnode;
104 if (!info.bbox->Intersects(node->bbox))
105 return;
106 }
107 /* range check passed and node exists */
108
109 node->generation = generation_;
110
111 if (level == level_) {
112 if (node->tile)
113 return; /* tile already loaded */
114
115 if (info.flags & SYNC) {
116 node->tile = SpawnTile(node->bbox, flags_);
117 tile_count_++;
118 total_size_ += node->tile->GetSize();
119 } else if (loading_ != TileId(level, x, y)) {
120 if (info.queue_size < 100) {
121 queue_.push_front(TileTask(TileId(level, x, y), node->bbox));
122 info.queue_size++;
123 }
124 }
125
126 /* no more recursion is needed */
127 return;
128 }
129
130 /* recurse */
131 RecLoadTilesBBox(info, node->childs, level+1, x * 2, y * 2);
132 RecLoadTilesBBox(info, node->childs + 1, level+1, x * 2 + 1, y * 2);
133 RecLoadTilesBBox(info, node->childs + 2, level+1, x * 2, y * 2 + 1);
134 RecLoadTilesBBox(info, node->childs + 3, level+1, x * 2 + 1, y * 2 + 1);
135
136 return;
137 }
138
RecLoadTilesLocality(RecLoadTilesInfo & info,QuadNode ** pnode,int level,int x,int y)139 void TileManager::RecLoadTilesLocality(RecLoadTilesInfo& info, QuadNode** pnode, int level, int x, int y) {
140 QuadNode* node;
141 float thisdist;
142
143 if (*pnode == NULL) {
144 /* no node; check if it's in view and if yes, create it */
145 BBoxi bbox = BBoxi::ForGeoTile(level, x, y);
146 thisdist = ApproxDistanceSquare(bbox, info.viewer_pos);
147 if (thisdist > range_ * range_)
148 return;
149 node = *pnode = new QuadNode;
150 node->bbox = bbox;
151 } else {
152 /* node exists, visit it if it's in view */
153 node = *pnode;
154 thisdist = ApproxDistanceSquare(node->bbox, info.viewer_pos);
155 if (thisdist > range_ * range_)
156 return;
157 }
158 /* range check passed and node exists */
159
160 node->generation = generation_;
161
162 if (level == level_) {
163 if (node->tile)
164 return; /* tile already loaded */
165
166 if (info.flags & SYNC) {
167 node->tile = SpawnTile(node->bbox, flags_);
168 tile_count_++;
169 total_size_ += node->tile->GetSize();
170 } else if (loading_ != TileId(level, x, y)) {
171 if (queue_.empty()) {
172 info.closest_distance = thisdist;
173 queue_.push_front(TileTask(TileId(level, x, y), node->bbox));
174 info.queue_size++;
175 } else {
176 if (thisdist < info.closest_distance) {
177 /* this tile is closer than the best we have in the queue - push to front so it's downloaded faster */
178 queue_.push_front(TileTask(TileId(level, x, y), node->bbox));
179 info.closest_distance = thisdist;
180 info.queue_size++;
181 } else if (info.queue_size < 100) {
182 /* push into the back of the queue, but not if queue is too long */
183 queue_.push_back(TileTask(TileId(level, x, y), node->bbox));
184 info.queue_size++;
185 }
186 }
187 }
188
189 /* no more recursion is needed */
190 return;
191 }
192
193 /* recurse */
194 RecLoadTilesLocality(info, node->childs, level+1, x * 2, y * 2);
195 RecLoadTilesLocality(info, node->childs + 1, level+1, x * 2 + 1, y * 2);
196 RecLoadTilesLocality(info, node->childs + 2, level+1, x * 2, y * 2 + 1);
197 RecLoadTilesLocality(info, node->childs + 3, level+1, x * 2 + 1, y * 2 + 1);
198
199 return;
200 }
201
RecPlaceTile(QuadNode * node,Tile * tile,int level,int x,int y)202 void TileManager::RecPlaceTile(QuadNode* node, Tile* tile, int level, int x, int y) {
203 if (node == NULL) {
204 /* part of quadtree was garbage collected -> tile
205 * is no longer needed and should just be dropped */
206 delete tile;
207 return;
208 }
209
210 if (level == 0) {
211 if (node->tile != NULL) {
212 /* tile already loaded for some reason (sync loading?)
213 * -> drop copy */
214 delete tile;
215 return;
216 }
217 node->tile = tile;
218 tile_count_++;
219 total_size_ += tile->GetSize();
220 } else {
221 int mask = 1 << (level-1);
222 int nchild = (!!(y & mask) << 1) | !!(x & mask);
223 RecPlaceTile(node->childs[nchild], tile, level-1, x, y);
224 }
225 }
226
RecDestroyTiles(QuadNode * node)227 void TileManager::RecDestroyTiles(QuadNode* node) {
228 if (!node)
229 return;
230
231 if (node->tile) {
232 tile_count_--;
233 total_size_ -= node->tile->GetSize();
234 delete node->tile;
235 node->tile = NULL;
236 }
237
238 for (int i = 0; i < 4; ++i) {
239 RecDestroyTiles(node->childs[i]);
240 if (node->childs[i]) {
241 delete node->childs[i];
242 node->childs[i] = NULL;
243 }
244 }
245 }
246
RecGarbageCollectTiles(QuadNode * node,GCQueue & gcqueue)247 void TileManager::RecGarbageCollectTiles(QuadNode* node, GCQueue& gcqueue) {
248 /* simplest garbage collection that drops all inactive
249 * tiles. This should become much more clever */
250 for (int i = 0; i < 4; ++i) {
251 if (node->childs[i] == NULL)
252 continue;
253
254 if (node->childs[i]->generation != generation_) {
255 gcqueue.push_back(&node->childs[i]);
256 } else {
257 RecGarbageCollectTiles(node->childs[i], gcqueue);
258 }
259 }
260 }
261
RecRenderTiles(QuadNode * node,const Viewer & viewer)262 void TileManager::RecRenderTiles(QuadNode* node, const Viewer& viewer) {
263 if (!node || node->generation != generation_)
264 return;
265
266 RecRenderTiles(node->childs[0], viewer);
267 RecRenderTiles(node->childs[1], viewer);
268 RecRenderTiles(node->childs[2], viewer);
269 RecRenderTiles(node->childs[3], viewer);
270
271 if (node->tile && node->tile->GetSize() != 0) {
272 glMatrixMode(GL_MODELVIEW);
273 glPushMatrix();
274
275 /* prepare modelview matrix for the tile: position
276 * it in the right place given that viewer is always
277 * at (0, 0, 0) */
278 Vector3f offset = projection_.Project(node->tile->GetReference(), Vector2i(viewer.GetPos(projection_))) +
279 projection_.Project(Vector2i(viewer.GetPos(projection_)), viewer.GetPos(projection_));
280
281 glTranslatef(offset.x, offset.y, offset.z);
282
283 /* same for rotation */
284 Vector3i ref = node->tile->GetReference();
285 Vector3i pos = viewer.GetPos(projection_);
286
287 /* normal at tile's reference point */
288 Vector3d refnormal = (
289 (Vector3d)projection_.Project(Vector3i(ref.x, ref.y, std::numeric_limits<osmint_t>::max()), pos) -
290 (Vector3d)projection_.Project(Vector3i(ref.x, ref.y, 0), pos)
291 ).Normalized();
292
293 /* normal at reference point projected to equator */
294 Vector3d refeqnormal = (
295 (Vector3d)projection_.Project(Vector3i(ref.x, 0, std::numeric_limits<osmint_t>::max()), pos) -
296 (Vector3d)projection_.Project(Vector3i(ref.x, 0, 0), pos)
297 ).Normalized();
298
299 /* normal at north pole */
300 Vector3d polenormal = (
301 (Vector3d)projection_.Project(Vector3i(ref.x, 900000000, std::numeric_limits<osmint_t>::max()), pos) -
302 (Vector3d)projection_.Project(Vector3i(ref.x, 900000000, 0), pos)
303 ).Normalized();
304
305 /* @todo IsValid() check basically detects
306 * MercatorProjection and does no rotation for it.
307 * While is's ok for now, this may need more generic
308 * approach in future */
309 if (polenormal.IsValid()) {
310 Vector3d side = refnormal.CrossProduct(polenormal).Normalized();
311
312 glRotatef((double)((osmlong_t)ref.y - (osmlong_t)pos.y) / 10000000.0, side.x, side.y, side.z);
313 glRotatef((double)((osmlong_t)ref.x - (osmlong_t)pos.x) / 10000000.0, polenormal.x, polenormal.y, polenormal.z);
314 }
315
316 node->tile->Render();
317
318 glMatrixMode(GL_MODELVIEW);
319 glPopMatrix();
320 }
321 }
322
323 /*
324 * loading queue - related
325 */
326
LoadingThreadFunc()327 void TileManager::LoadingThreadFunc() {
328 pthread_mutex_lock(&queue_mutex_);
329 while (!thread_die_flag_) {
330 /* found nothing, sleep */
331 if (queue_.empty()) {
332 pthread_cond_wait(&queue_cond_, &queue_mutex_);
333 continue;
334 }
335
336 /* take a task from the queue */
337 TileTask task = queue_.front();
338 queue_.pop_front();
339
340 /* mark it as loading */
341 loading_ = task.id;
342
343 pthread_mutex_unlock(&queue_mutex_);
344
345 /* load tile */
346 Tile* tile = SpawnTile(task.bbox, flags_);
347
348 pthread_mutex_lock(&tiles_mutex_);
349 RecPlaceTile(&root_, tile, task.id.level, task.id.x, task.id.y);
350
351 pthread_mutex_unlock(&tiles_mutex_);
352
353 /* The following happens:
354 * - main thread finishes Render and unlocks tiles_mutex_
355 * - this thread wakes up and loads MANY tiles without main
356 * thread able to run
357 * - main thread finally runs after ~0.1 sec delay, which
358 * is noticeable lag in realtime renderer
359 *
360 * Nut sure yet how to fix ot properly, but this sched_yield
361 * works for now.
362 */
363 sched_yield();
364
365 pthread_mutex_lock(&queue_mutex_);
366 loading_ = TileId(-1, -1, -1);
367 }
368 pthread_mutex_unlock(&queue_mutex_);
369 }
370
LoadingThreadFuncWrapper(void * arg)371 void* TileManager::LoadingThreadFuncWrapper(void* arg) {
372 static_cast<TileManager*>(arg)->LoadingThreadFunc();
373 return NULL;
374 }
375
376 /*
377 * protected interface
378 */
379
Render(const Viewer & viewer)380 void TileManager::Render(const Viewer& viewer) {
381 pthread_mutex_lock(&tiles_mutex_);
382 RecRenderTiles(&root_, viewer);
383 pthread_mutex_unlock(&tiles_mutex_);
384 }
385
Load(RecLoadTilesInfo & info)386 void TileManager::Load(RecLoadTilesInfo& info) {
387 QuadNode* root = &root_;
388
389 /* @todo add guard here instead of implicit locking,
390 * so we don't deadlock on exception */
391 if (!(info.flags & SYNC)) {
392 pthread_mutex_lock(&queue_mutex_);
393 queue_.clear();
394 }
395
396 pthread_mutex_lock(&tiles_mutex_);
397
398 switch (info.mode) {
399 case RecLoadTilesInfo::BBOX:
400 RecLoadTilesBBox(info, &root);
401 break;
402 case RecLoadTilesInfo::LOCALITY:
403 info.viewer_pos = height_effect_ ? info.viewer->GetPos(projection_) : info.viewer->GetPos(projection_).Flattened();
404 RecLoadTilesLocality(info, &root);
405 break;
406 }
407
408 pthread_mutex_unlock(&tiles_mutex_);
409
410 if (!(info.flags & SYNC)) {
411 pthread_mutex_unlock(&queue_mutex_);
412
413 if (!queue_.empty())
414 pthread_cond_signal(&queue_cond_);
415 }
416 }
417
418 /*
419 * public interface
420 */
421
LoadArea(const BBoxi & bbox,int flags)422 void TileManager::LoadArea(const BBoxi& bbox, int flags) {
423 RecLoadTilesInfo info;
424
425 info.bbox = &bbox;
426 info.flags = flags;
427 info.mode = RecLoadTilesInfo::BBOX;
428
429 Load(info);
430 }
431
LoadLocality(const Viewer & viewer,int flags)432 void TileManager::LoadLocality(const Viewer& viewer, int flags) {
433 RecLoadTilesInfo info;
434
435 info.viewer = &viewer;
436 info.flags = flags;
437 info.mode = RecLoadTilesInfo::LOCALITY;
438
439 Load(info);
440 }
441
GenerationCompare(QuadNode ** x,QuadNode ** y)442 bool TileManager::GenerationCompare(QuadNode** x, QuadNode** y) {
443 return (*x)->generation < (*y)->generation;
444 }
445
GarbageCollect()446 void TileManager::GarbageCollect() {
447 pthread_mutex_lock(&tiles_mutex_);
448 if (total_size_ > size_limit_) {
449 GCQueue gcqueue;
450 gcqueue.reserve(tile_count_);
451
452 /* collect tiles for garbage collecting */
453 RecGarbageCollectTiles(&root_, gcqueue);
454
455 /* sort by generation */
456 std::sort(gcqueue.begin(), gcqueue.end(), GenerationCompare);
457
458 for (GCQueue::iterator i = gcqueue.begin(); i != gcqueue.end() && total_size_ > size_limit_; ++i) {
459 RecDestroyTiles(**i);
460 delete **i;
461 **i = NULL;
462 }
463 }
464
465 generation_++;
466 pthread_mutex_unlock(&tiles_mutex_);
467 }
468
Clear()469 void TileManager::Clear() {
470 pthread_mutex_lock(&tiles_mutex_);
471 RecDestroyTiles(&root_);
472 generation_++;
473 pthread_mutex_unlock(&tiles_mutex_);
474 }
475
SetLevel(int level)476 void TileManager::SetLevel(int level) {
477 level_ = level;
478 }
479
SetRange(float range)480 void TileManager::SetRange(float range) {
481 range_ = range;
482 }
483
SetFlags(int flags)484 void TileManager::SetFlags(int flags) {
485 flags_ = flags;
486 }
487
SetHeightEffect(bool enabled)488 void TileManager::SetHeightEffect(bool enabled) {
489 height_effect_ = enabled;
490 }
491
SetSizeLimit(size_t limit)492 void TileManager::SetSizeLimit(size_t limit) {
493 size_limit_ = limit;
494 }
495