Line data Source code
1 : /*
2 : Minetest
3 : Copyright (C) 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 : #ifndef VOXEL_HEADER
21 : #define VOXEL_HEADER
22 :
23 : #include "irrlichttypes.h"
24 : #include "irr_v3d.h"
25 : #include <iostream>
26 : #include "debug.h"
27 : #include "exceptions.h"
28 : #include "mapnode.h"
29 : #include <set>
30 : #include <list>
31 : #include <map>
32 :
33 : class INodeDefManager;
34 :
35 : // For VC++
36 : #undef min
37 : #undef max
38 :
39 : /*
40 : A fast voxel manipulator class.
41 :
42 : In normal operation, it fetches more map when it is requested.
43 : It can also be used so that all allowed area is fetched at the
44 : start, using ManualMapVoxelManipulator.
45 :
46 : Not thread-safe.
47 : */
48 :
49 : /*
50 : Debug stuff
51 : */
52 : extern u32 emerge_time;
53 : extern u32 emerge_load_time;
54 :
55 : /*
56 : This class resembles aabbox3d<s16> a lot, but has inclusive
57 : edges for saner handling of integer sizes
58 : */
59 14196 : class VoxelArea
60 : {
61 : public:
62 : // Starts as zero sized
63 14196 : VoxelArea():
64 : MinEdge(1,1,1),
65 14196 : MaxEdge(0,0,0)
66 : {
67 14196 : }
68 59869 : VoxelArea(v3s16 min_edge, v3s16 max_edge):
69 : MinEdge(min_edge),
70 59869 : MaxEdge(max_edge)
71 : {
72 59869 : }
73 17911023 : VoxelArea(v3s16 p):
74 : MinEdge(p),
75 17911023 : MaxEdge(p)
76 : {
77 17911023 : }
78 :
79 : /*
80 : Modifying methods
81 : */
82 :
83 0 : void addArea(const VoxelArea &a)
84 : {
85 0 : if (hasEmptyExtent())
86 : {
87 0 : *this = a;
88 0 : return;
89 : }
90 0 : if(a.MinEdge.X < MinEdge.X) MinEdge.X = a.MinEdge.X;
91 0 : if(a.MinEdge.Y < MinEdge.Y) MinEdge.Y = a.MinEdge.Y;
92 0 : if(a.MinEdge.Z < MinEdge.Z) MinEdge.Z = a.MinEdge.Z;
93 0 : if(a.MaxEdge.X > MaxEdge.X) MaxEdge.X = a.MaxEdge.X;
94 0 : if(a.MaxEdge.Y > MaxEdge.Y) MaxEdge.Y = a.MaxEdge.Y;
95 0 : if(a.MaxEdge.Z > MaxEdge.Z) MaxEdge.Z = a.MaxEdge.Z;
96 : }
97 0 : void addPoint(const v3s16 &p)
98 : {
99 0 : if(hasEmptyExtent())
100 : {
101 0 : MinEdge = p;
102 0 : MaxEdge = p;
103 0 : return;
104 : }
105 0 : if(p.X < MinEdge.X) MinEdge.X = p.X;
106 0 : if(p.Y < MinEdge.Y) MinEdge.Y = p.Y;
107 0 : if(p.Z < MinEdge.Z) MinEdge.Z = p.Z;
108 0 : if(p.X > MaxEdge.X) MaxEdge.X = p.X;
109 0 : if(p.Y > MaxEdge.Y) MaxEdge.Y = p.Y;
110 0 : if(p.Z > MaxEdge.Z) MaxEdge.Z = p.Z;
111 : }
112 :
113 : // Pad with d nodes
114 0 : void pad(const v3s16 &d)
115 : {
116 0 : MinEdge -= d;
117 0 : MaxEdge += d;
118 0 : }
119 :
120 : /*void operator+=(v3s16 off)
121 : {
122 : MinEdge += off;
123 : MaxEdge += off;
124 : }
125 :
126 : void operator-=(v3s16 off)
127 : {
128 : MinEdge -= off;
129 : MaxEdge -= off;
130 : }*/
131 :
132 : /*
133 : const methods
134 : */
135 :
136 116199124 : v3s16 getExtent() const
137 : {
138 116199124 : return MaxEdge - MinEdge + v3s16(1,1,1);
139 : }
140 :
141 : /* Because MaxEdge and MinEdge are included in the voxel area an empty extent
142 : * is not represented by (0, 0, 0), but instead (-1, -1, -1)
143 : */
144 35832513 : bool hasEmptyExtent() const
145 : {
146 35832513 : return MaxEdge - MinEdge == v3s16(-1, -1, -1);
147 : }
148 :
149 3550 : s32 getVolume() const
150 : {
151 3550 : v3s16 e = getExtent();
152 3550 : return (s32)e.X * (s32)e.Y * (s32)e.Z;
153 : }
154 17914483 : bool contains(const VoxelArea &a) const
155 : {
156 : // No area contains an empty area
157 : // NOTE: Algorithms depend on this, so do not change.
158 17914483 : if(a.hasEmptyExtent())
159 0 : return false;
160 :
161 : return(
162 53736907 : a.MinEdge.X >= MinEdge.X && a.MaxEdge.X <= MaxEdge.X &&
163 53733069 : a.MinEdge.Y >= MinEdge.Y && a.MaxEdge.Y <= MaxEdge.Y &&
164 53736512 : a.MinEdge.Z >= MinEdge.Z && a.MaxEdge.Z <= MaxEdge.Z
165 17914466 : );
166 : }
167 0 : bool contains(v3s16 p) const
168 : {
169 : return(
170 0 : p.X >= MinEdge.X && p.X <= MaxEdge.X &&
171 0 : p.Y >= MinEdge.Y && p.Y <= MaxEdge.Y &&
172 0 : p.Z >= MinEdge.Z && p.Z <= MaxEdge.Z
173 0 : );
174 : }
175 0 : bool contains(s32 i) const
176 : {
177 0 : return (i >= 0 && i < getVolume());
178 : }
179 0 : bool operator==(const VoxelArea &other) const
180 : {
181 0 : return (MinEdge == other.MinEdge
182 0 : && MaxEdge == other.MaxEdge);
183 : }
184 :
185 : VoxelArea operator+(v3s16 off) const
186 : {
187 : return VoxelArea(MinEdge+off, MaxEdge+off);
188 : }
189 :
190 : VoxelArea operator-(v3s16 off) const
191 : {
192 : return VoxelArea(MinEdge-off, MaxEdge-off);
193 : }
194 :
195 : /*
196 : Returns 0-6 non-overlapping areas that can be added to
197 : a to make up this area.
198 :
199 : a: area inside *this
200 : */
201 0 : void diff(const VoxelArea &a, std::list<VoxelArea> &result)
202 : {
203 : /*
204 : This can result in a maximum of 6 areas
205 : */
206 :
207 : // If a is an empty area, return the current area as a whole
208 0 : if(a.getExtent() == v3s16(0,0,0))
209 : {
210 0 : VoxelArea b = *this;
211 0 : if(b.getVolume() != 0)
212 0 : result.push_back(b);
213 0 : return;
214 : }
215 :
216 : assert(contains(a)); // pre-condition
217 :
218 : // Take back area, XY inclusive
219 : {
220 0 : v3s16 min(MinEdge.X, MinEdge.Y, a.MaxEdge.Z+1);
221 0 : v3s16 max(MaxEdge.X, MaxEdge.Y, MaxEdge.Z);
222 0 : VoxelArea b(min, max);
223 0 : if(b.getVolume() != 0)
224 0 : result.push_back(b);
225 : }
226 :
227 : // Take front area, XY inclusive
228 : {
229 0 : v3s16 min(MinEdge.X, MinEdge.Y, MinEdge.Z);
230 0 : v3s16 max(MaxEdge.X, MaxEdge.Y, a.MinEdge.Z-1);
231 0 : VoxelArea b(min, max);
232 0 : if(b.getVolume() != 0)
233 0 : result.push_back(b);
234 : }
235 :
236 : // Take top area, X inclusive
237 : {
238 0 : v3s16 min(MinEdge.X, a.MaxEdge.Y+1, a.MinEdge.Z);
239 0 : v3s16 max(MaxEdge.X, MaxEdge.Y, a.MaxEdge.Z);
240 0 : VoxelArea b(min, max);
241 0 : if(b.getVolume() != 0)
242 0 : result.push_back(b);
243 : }
244 :
245 : // Take bottom area, X inclusive
246 : {
247 0 : v3s16 min(MinEdge.X, MinEdge.Y, a.MinEdge.Z);
248 0 : v3s16 max(MaxEdge.X, a.MinEdge.Y-1, a.MaxEdge.Z);
249 0 : VoxelArea b(min, max);
250 0 : if(b.getVolume() != 0)
251 0 : result.push_back(b);
252 : }
253 :
254 : // Take left area, non-inclusive
255 : {
256 0 : v3s16 min(MinEdge.X, a.MinEdge.Y, a.MinEdge.Z);
257 0 : v3s16 max(a.MinEdge.X-1, a.MaxEdge.Y, a.MaxEdge.Z);
258 0 : VoxelArea b(min, max);
259 0 : if(b.getVolume() != 0)
260 0 : result.push_back(b);
261 : }
262 :
263 : // Take right area, non-inclusive
264 : {
265 0 : v3s16 min(a.MaxEdge.X+1, a.MinEdge.Y, a.MinEdge.Z);
266 0 : v3s16 max(MaxEdge.X, a.MaxEdge.Y, a.MaxEdge.Z);
267 0 : VoxelArea b(min, max);
268 0 : if(b.getVolume() != 0)
269 0 : result.push_back(b);
270 : }
271 :
272 : }
273 :
274 : /*
275 : Translates position from virtual coordinates to array index
276 : */
277 116087677 : s32 index(s16 x, s16 y, s16 z) const
278 : {
279 116087677 : v3s16 em = getExtent();
280 116083331 : v3s16 off = MinEdge;
281 116081196 : s32 i = (s32)(z-off.Z)*em.Y*em.X + (y-off.Y)*em.X + (x-off.X);
282 : //dstream<<" i("<<x<<","<<y<<","<<z<<")="<<i<<" ";
283 116081196 : return i;
284 : }
285 115878826 : s32 index(v3s16 p) const
286 : {
287 115878826 : return index(p.X, p.Y, p.Z);
288 : }
289 :
290 : // Translate index in the X coordinate
291 : void add_x(const v3s16 &extent, u32 &i, s16 a)
292 : {
293 : i += a;
294 : }
295 : // Translate index in the Y coordinate
296 0 : void add_y(const v3s16 &extent, u32 &i, s16 a)
297 : {
298 0 : i += a * extent.X;
299 0 : }
300 : // Translate index in the Z coordinate
301 : void add_z(const v3s16 &extent, u32 &i, s16 a)
302 : {
303 : i += a * extent.X*extent.Y;
304 : }
305 : // Translate index in space
306 0 : void add_p(const v3s16 &extent, u32 &i, v3s16 a)
307 : {
308 0 : i += a.Z*extent.X*extent.Y + a.Y*extent.X + a.X;
309 0 : }
310 :
311 : /*
312 : Print method for debugging
313 : */
314 0 : void print(std::ostream &o) const
315 : {
316 0 : v3s16 e = getExtent();
317 0 : o<<"("<<MinEdge.X
318 0 : <<","<<MinEdge.Y
319 0 : <<","<<MinEdge.Z
320 0 : <<")("<<MaxEdge.X
321 0 : <<","<<MaxEdge.Y
322 0 : <<","<<MaxEdge.Z
323 0 : <<")"
324 0 : <<"="<<e.X<<"x"<<e.Y<<"x"<<e.Z<<"="<<getVolume();
325 0 : }
326 :
327 : // Edges are inclusive
328 : v3s16 MinEdge;
329 : v3s16 MaxEdge;
330 : };
331 :
332 : // unused
333 : #define VOXELFLAG_UNUSED (1<<0)
334 : // no data about that node
335 : #define VOXELFLAG_NO_DATA (1<<1)
336 : // Algorithm-dependent
337 : #define VOXELFLAG_CHECKED1 (1<<2)
338 : // Algorithm-dependent
339 : #define VOXELFLAG_CHECKED2 (1<<3)
340 : // Algorithm-dependent
341 : #define VOXELFLAG_CHECKED3 (1<<4)
342 : // Algorithm-dependent
343 : #define VOXELFLAG_CHECKED4 (1<<5)
344 :
345 : enum VoxelPrintMode
346 : {
347 : VOXELPRINT_NOTHING,
348 : VOXELPRINT_MATERIAL,
349 : VOXELPRINT_WATERPRESSURE,
350 : VOXELPRINT_LIGHT_DAY,
351 : };
352 :
353 : class VoxelManipulator /*: public NodeContainer*/
354 : {
355 : public:
356 : VoxelManipulator();
357 : virtual ~VoxelManipulator();
358 :
359 : /*
360 : Virtuals from NodeContainer
361 : */
362 : /*virtual u16 nodeContainerId() const
363 : {
364 : return NODECONTAINER_ID_VOXELMANIPULATOR;
365 : }
366 : bool isValidPosition(v3s16 p)
367 : {
368 : addArea(p);
369 : return !(m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA);
370 : }*/
371 :
372 : /*
373 : These are a bit slow and shouldn't be used internally.
374 : Use m_data[m_area.index(p)] instead.
375 : */
376 0 : MapNode getNode(v3s16 p)
377 : {
378 0 : VoxelArea voxel_area(p);
379 0 : addArea(voxel_area);
380 :
381 0 : if(m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA)
382 : {
383 : /*dstream<<"EXCEPT: VoxelManipulator::getNode(): "
384 : <<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
385 : <<", index="<<m_area.index(p)
386 : <<", flags="<<(int)m_flags[m_area.index(p)]
387 : <<" is inexistent"<<std::endl;*/
388 : throw InvalidPositionException
389 0 : ("VoxelManipulator: getNode: inexistent");
390 : }
391 :
392 0 : return m_data[m_area.index(p)];
393 : }
394 17911023 : MapNode getNodeNoEx(v3s16 p)
395 : {
396 17911023 : VoxelArea voxel_area(p);
397 17911023 : addArea(voxel_area);
398 :
399 17911023 : if(m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA)
400 : {
401 5620 : return MapNode(CONTENT_IGNORE);
402 : }
403 :
404 17905403 : return m_data[m_area.index(p)];
405 : }
406 0 : MapNode getNodeNoExNoEmerge(v3s16 p)
407 : {
408 0 : if(m_area.contains(p) == false)
409 0 : return MapNode(CONTENT_IGNORE);
410 0 : if(m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA)
411 0 : return MapNode(CONTENT_IGNORE);
412 0 : return m_data[m_area.index(p)];
413 : }
414 : // Stuff explodes if non-emerged area is touched with this.
415 : // Emerge first, and check VOXELFLAG_NO_DATA if appropriate.
416 26296320 : MapNode & getNodeRefUnsafe(const v3s16 &p)
417 : {
418 26296320 : return m_data[m_area.index(p)];
419 : }
420 :
421 53766080 : const MapNode & getNodeRefUnsafeCheckFlags(const v3s16 &p)
422 : {
423 53766080 : s32 index = m_area.index(p);
424 :
425 53766080 : if (m_flags[index] & VOXELFLAG_NO_DATA)
426 839063 : return ContentIgnoreNode;
427 :
428 52927017 : return m_data[index];
429 : }
430 :
431 0 : u8 & getFlagsRefUnsafe(v3s16 p)
432 : {
433 0 : return m_flags[m_area.index(p)];
434 : }
435 0 : bool exists(v3s16 p)
436 : {
437 0 : return m_area.contains(p) &&
438 0 : !(getFlagsRefUnsafe(p) & VOXELFLAG_NO_DATA);
439 : }
440 : MapNode & getNodeRef(v3s16 p)
441 : {
442 : VoxelArea voxel_area(p);
443 : addArea(voxel_area);
444 : if(getFlagsRefUnsafe(p) & VOXELFLAG_NO_DATA)
445 : {
446 : /*dstream<<"EXCEPT: VoxelManipulator::getNode(): "
447 : <<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
448 : <<", index="<<m_area.index(p)
449 : <<", flags="<<(int)getFlagsRefUnsafe(p)
450 : <<" is inexistent"<<std::endl;*/
451 : throw InvalidPositionException
452 : ("VoxelManipulator: getNode: inexistent");
453 : }
454 : return getNodeRefUnsafe(p);
455 : }
456 0 : void setNode(v3s16 p, const MapNode &n)
457 : {
458 0 : VoxelArea voxel_area(p);
459 0 : addArea(voxel_area);
460 :
461 0 : m_data[m_area.index(p)] = n;
462 0 : m_flags[m_area.index(p)] &= ~VOXELFLAG_NO_DATA;
463 0 : }
464 : // TODO: Should be removed and replaced with setNode
465 0 : void setNodeNoRef(v3s16 p, const MapNode &n)
466 : {
467 0 : setNode(p, n);
468 0 : }
469 :
470 : /*void setExists(VoxelArea a)
471 : {
472 : addArea(a);
473 : for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
474 : for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
475 : for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
476 : {
477 : m_flags[m_area.index(x,y,z)] &= ~VOXELFLAG_NO_DATA;
478 : }
479 : }*/
480 :
481 : /*MapNode & operator[](v3s16 p)
482 : {
483 : //dstream<<"operator[] p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
484 : if(isValidPosition(p) == false)
485 : addArea(VoxelArea(p));
486 :
487 : return m_data[m_area.index(p)];
488 : }*/
489 :
490 : /*
491 : Set stuff if available without an emerge.
492 : Return false if failed.
493 : This is convenient but slower than playing around directly
494 : with the m_data table with indices.
495 : */
496 0 : bool setNodeNoEmerge(v3s16 p, MapNode n)
497 : {
498 0 : if(m_area.contains(p) == false)
499 0 : return false;
500 0 : m_data[m_area.index(p)] = n;
501 0 : return true;
502 : }
503 : bool setNodeNoEmerge(s32 i, MapNode n)
504 : {
505 : if(m_area.contains(i) == false)
506 : return false;
507 : m_data[i] = n;
508 : return true;
509 : }
510 : /*bool setContentNoEmerge(v3s16 p, u8 c)
511 : {
512 : if(isValidPosition(p) == false)
513 : return false;
514 : m_data[m_area.index(p)].d = c;
515 : }*/
516 :
517 : /*
518 : Control
519 : */
520 :
521 : virtual void clear();
522 :
523 : void print(std::ostream &o, INodeDefManager *nodemgr,
524 : VoxelPrintMode mode=VOXELPRINT_MATERIAL);
525 :
526 : void addArea(const VoxelArea &area);
527 :
528 : /*
529 : Copy data and set flags to 0
530 : dst_area.getExtent() <= src_area.getExtent()
531 : */
532 : void copyFrom(MapNode *src, const VoxelArea& src_area,
533 : v3s16 from_pos, v3s16 to_pos, v3s16 size);
534 :
535 : // Copy data
536 : void copyTo(MapNode *dst, const VoxelArea& dst_area,
537 : v3s16 dst_pos, v3s16 from_pos, v3s16 size);
538 :
539 : /*
540 : Algorithms
541 : */
542 :
543 : void clearFlag(u8 flag);
544 :
545 : // TODO: Move to voxelalgorithms.h
546 :
547 : void unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
548 : std::set<v3s16> & light_sources, INodeDefManager *nodemgr);
549 : void unspreadLight(enum LightBank bank,
550 : std::map<v3s16, u8> & from_nodes,
551 : std::set<v3s16> & light_sources, INodeDefManager *nodemgr);
552 :
553 : void spreadLight(enum LightBank bank, v3s16 p, INodeDefManager *nodemgr);
554 : void spreadLight(enum LightBank bank,
555 : std::set<v3s16> & from_nodes, INodeDefManager *nodemgr);
556 :
557 : /*
558 : Virtual functions
559 : */
560 :
561 : /*
562 : Member variables
563 : */
564 :
565 : /*
566 : The area that is stored in m_data.
567 : addInternalBox should not be used if getExtent() == v3s16(0,0,0)
568 : MaxEdge is 1 higher than maximum allowed position
569 : */
570 : VoxelArea m_area;
571 :
572 : /*
573 : NULL if data size is 0 (extent (0,0,0))
574 : Data is stored as [z*h*w + y*h + x]
575 : */
576 : MapNode *m_data;
577 :
578 : /*
579 : Flags of all nodes
580 : */
581 : u8 *m_flags;
582 :
583 : static const MapNode ContentIgnoreNode;
584 :
585 : //TODO: Use these or remove them
586 : //TODO: Would these make any speed improvement?
587 : //bool m_pressure_route_valid;
588 : //v3s16 m_pressure_route_surface;
589 :
590 : /*
591 : Some settings
592 : */
593 : //bool m_disable_water_climb;
594 :
595 : private:
596 : };
597 :
598 : #endif
599 :
|