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