| blob | a44787eaa5cf0ff37139474df0141badf4328544 |
1 // Ryzom - MMORPG Framework <http://dev.ryzom.com/projects/ryzom/>
2 // Copyright (C) 2010 Winch Gate Property Limited
3 //
4 // This program is free software: you can redistribute it and/or modify
5 // it under the terms of the GNU Affero General Public License as
6 // published by the Free Software Foundation, either version 3 of the
7 // License, or (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU Affero General Public License for more details.
13 //
14 // You should have received a copy of the GNU Affero General Public License
15 // along with this program. If not, see <http://www.gnu.org/licenses/>.
18 #ifndef CL_PRECIPITATION_CLIP_GRID_H
19 #define CL_PRECIPITATION_CLIP_GRID_H
27 /*
29 // *********************************************************************************
30 template <class T> class CArray2D
31 {
32 public:
33 typedef typename std::vector<T> TArrayContainer;
34 typedef typename TArrayContainer::iterator iterator;
35 typedef typename TArrayContainer::const_iterator const_iterator;
36 CArray2D() : _Width(0), _Height(0) {}
37 void init(uint width, uint height);
38 void init(uint width, uint height, const T &defaultValue);
39 bool empty() const { return _Array.empty(); }
40 typename iterator begin() { return _Array.begin(); }
41 typename iterator end() { return _Array.end(); }
42 typename const_iterator begin() const { return _Array.begin(); }
43 typename const_iterator end() const { return _Array.end(); }
45 // access element by column/row
46 T &operator()(uint x, uint y)
47 {
48 #ifdef NL_DEBUG
49 nlassert(x < _Width);
50 nlassert(y < _Height);
51 #endif
52 return _Array[x + y * _Width];
53 }
54 // access element by column/row (const version)
55 const T &operator()(uint x, uint y) const
56 {
57 #ifdef NL_DEBUG
58 nlassert(x < _Width);
59 nlassert(y < _Height);
60 #endif
61 return _Array[x + y * _Width];
62 }
63 // Return width of array
64 uint getWidth() const { return _Width; }
65 // Return height of array
66 uint getHeight() const { return _Height; }
67 // Move array content of the given offset. No wrapping is applied
68 // Example : move(1, 0) will move the array of one column to the left. The latest column is lost. The first column remains unchanged
69 //
70 void move(sint offsetX, sint offsetY);
71 // Move a part of the array. Values are clamped as necessary
72 void moveSubArray(sint dstX, sint dstY, sint srcX, sint srcY, sint width, sint height);
73 // get an iterator to the start of a row
74 iterator beginRow(uint row)
75 {
76 nlassert(row < _Height);
77 return _Array.begin() + row * _Width;
78 }
79 const_iterator beginRow(uint row) const
80 {
81 nlassert(row < _Height);
82 return _Array.begin() + row * _Width;
83 }
84 iterator endRow(uint row)
85 {
86 nlassert(row < _Height);
87 return _Array.begin() + (row + 1) * _Width;
88 }
89 const_iterator endRow(uint row) const
90 {
91 nlassert(row < _Height);
92 return _Array.begin() + (row + 1) * _Width;
93 }
94 // get an iterator at the given position
95 iterator getIteratorAt(uint x, uint y)
96 {
97 #ifdef NL_DEBUG
98 nlassert(x < _Width);
99 nlassert(y < _Height);
100 #endif
101 return _Array.begin() + x + (y * _Width);
102 }
103 // Get a const iterator at the given position
104 const iterator getIteratorAt(uint x, uint y) const
105 {
106 #ifdef NL_DEBUG
107 nlassert(x < _Width);
108 nlassert(y < _Height);
109 #endif
110 return _Array.begin() + x + (y * _Width);
111 }
112 // See which part of array should be updated after its content has been displaced by the given offset (by a call to move for example).
113 // Example: getUpdateRects(0, 1, result) will result the first row as a result
114 //
115 void getUpdateRects(sint moveOffsetX, sint moveOffsetY, std::vector<CRect> &rectsToUpdate);
116 // See which parts of array will be discarded if the array is displaced by the given offset
117 void getDiscardRects(sint moveOffsetX, sint moveOffsetY, std::vector<CRect> &discardedRects);
118 private:
119 TArrayContainer _Array;
120 uint _Width;
121 uint _Height;
122 private:
123 inline void checkRect(const CRect &r) const
124 {
125 nlassert(r.X >= 0 && r.X < (sint32) _Width);
126 nlassert(r.Y >= 0 && r.Y < (sint32) _Height);
127 nlassert(r.X + r.Width >= 0 && r.X + (sint32) r.Width <= (sint32) _Width);
128 nlassert(r.Y + r.Height >= 0 && r.Y + (sint32) r.Height <= (sint32) _Height);
129 }
130 };
133 // *********************************************************************************
134 template <class T>
135 void CArray2D<T>::getUpdateRects(sint moveOffsetX, sint moveOffsetY, std::vector<CRect> &rectsToUpdate)
136 {
137 rectsToUpdate.clear();
138 if (moveOffsetX < 0) // moved right ?
139 {
140 // the width to update
141 uint width = std::min((uint) moveOffsetX, _Width);
142 // the grid moved top or bottom, exclude this part
143 sint height = _Height - abs(moveOffsetY);
144 if (height > 0)
145 {
146 nlwarning("*1");
147 // complete column on the right
148 rectsToUpdate.push_back(CRect((sint32) (_Width - width), (sint32) (std::max(- moveOffsetY, 0)), (uint32) width, (uint32) height));
149 #ifdef NL_DEBUG
150 checkRect(rectsToUpdate.back());
151 #endif
152 }
153 }
154 else if (moveOffsetX > 0) // moved left ?
155 {
156 // the width to update
157 uint width = std::min((uint) (- moveOffsetX), _Width);
158 // the grid moved top or bottom.
159 sint height = _Height - abs(moveOffsetY);
160 if (height > 0)
161 {
162 //nlwarning("*2");
163 // complete column on the right
164 rectsToUpdate.push_back(CRect(0, (sint32) std::max(- moveOffsetY, 0), (uint32) width, (uint32) height));
165 #ifdef NL_DEBUG
166 checkRect(rectsToUpdate.back());
167 #endif
168 }
169 }
170 // update top or bottom part
171 if (moveOffsetY < 0)
172 {
173 sint height = std::min((uint) moveOffsetY, _Height);
174 //nlwarning("*3");
175 rectsToUpdate.push_back(CRect(0, _Height - height, _Width, height));
176 #ifdef NL_DEBUG
177 checkRect(rectsToUpdate.back());
178 #endif
179 }
180 else
181 if (moveOffsetY > 0)
182 {
183 sint height = std::min((uint) (- moveOffsetY), _Height);
184 //nlwarning("*4");
185 rectsToUpdate.push_back(CRect(0, 0, _Width, height));
186 #ifdef NL_DEBUG
187 checkRect(rectsToUpdate.back());
188 #endif
189 }
190 }
192 // *********************************************************************************
193 template <class T>
194 void CArray2D<T>::getDiscardRects(sint moveOffsetX, sint moveOffsetY,std::vector<CRect> &discardedRects)
195 {
196 getUpdateRects(- moveOffsetX, - moveOffsetY, discardedRects);
197 }
199 // *********************************************************************************
200 template <class T>
201 void CArray2D<T>::moveSubArray(sint dstX, sint dstY, sint srcX, sint srcY, sint width, sint height)
202 {
203 if (srcX >= (sint) getWidth()) return;
204 if (srcY >= (sint) getHeight()) return;
205 if (dstX >= (sint) getWidth()) return;
206 if (dstY >= (sint) getHeight()) return;
207 if (srcX < 0)
208 {
209 width += srcX;
210 if (width <= 0) return;
211 srcX = 0;
212 }
213 if (srcY < 0)
214 {
215 height += srcY;
216 if (height <= 0) return;
217 srcY = 0;
218 }
219 if (srcX + width > (sint) getWidth())
220 {
221 width = getWidth() - srcX;
222 }
223 if (srcY + height > (sint) getHeight())
224 {
225 height = getHeight() - srcY;
226 }
227 if (dstX < 0)
228 {
229 width += dstX;
230 if (width < 0) return;
231 srcX -= dstX;
232 dstX = 0;
233 }
234 if (dstY < 0)
235 {
236 height += dstY;
237 if (height < 0) return;
238 srcY -= dstY;
239 dstY = 0;
240 }
241 if (dstX + width > (sint) getWidth())
242 {
243 width = getWidth() - dstX;
244 }
245 if (dstY + height > (sint) getHeight())
246 {
247 height = getHeight() - dstY;
248 }
249 #ifdef NL_DEBUG
250 nlassert(width > 0);
251 nlassert(height > 0);
252 nlassert(srcX >= 0 && srcX < (sint) getWidth());
253 nlassert(srcY >= 0 && srcY < (sint) getHeight());
254 #endif
255 if (dstY < srcY)
256 {
257 const_iterator src = getIteratorAt(srcX, srcY);
258 iterator dst = getIteratorAt(dstX, dstY);
259 do
260 {
261 if (CTraits<T>::SupportRawCopy)
262 {
263 // type support fast copy
264 ::memcpy(&(*dst), &(*src), sizeof(T) * width);
265 }
266 else
267 {
268 std::copy(src, src + width, dst);
269 }
270 src += _Width;
271 dst += _Width;
272 }
273 while(--height);
274 }
275 else if (dstY > srcY)
276 {
277 // copy from top to bottom
278 const_iterator src = getIteratorAt(srcX, srcY + height - 1);
279 iterator dst = getIteratorAt(dstX, dstY + height - 1);
280 do
281 {
282 if (CTraits<T>::SupportRawCopy)
283 {
284 // type support fast copy
285 ::memcpy(&(*dst), &(*src), sizeof(T) * width);
286 }
287 else
288 {
289 std::copy(src, src + width, dst);
290 }
291 src -= _Width;
292 dst -= _Width;
293 }
294 while(--height);
295 }
296 else
297 {
298 const_iterator src = getIteratorAt(srcX, srcY);
299 iterator dst = getIteratorAt(dstX, dstY);
300 if (dstX < srcX)
301 {
302 do
303 {
304 if (CTraits<T>::SupportRawCopy)
305 {
306 // type support fast copy
307 ::memmove(&(*dst), &(*src), sizeof(T) * width);
308 }
309 else
310 {
311 std::reverse_copy(src, src + width, dst);
312 }
313 src += _Width;
314 dst += _Width;
315 }
316 while(--height);
317 }
318 else
319 {
320 do
321 {
322 if (CTraits<T>::SupportRawCopy)
323 {
324 // type support fast copy
325 ::memcpy(&(*dst), &(*src), sizeof(T) * width);
326 }
327 else
328 {
329 std::copy(src, src + width, dst);
330 }
331 src += _Width;
332 dst += _Width;
333 }
334 while(--height);
335 }
336 }
337 }
340 // *********************************************************************************
341 template <class T>
342 void CArray2D<T>::move(sint offsetX, sint offsetY)
343 {
344 moveSubArray(offsetX, offsetY, 0, 0, _Width, _Height);
345 }
347 // *********************************************************************************
348 template <class T>
349 void CArray2D<T>::init(uint width, uint height)
350 {
351 _Array.resize(width * height);
352 _Width = width;
353 _Height = height;
354 }
356 // *********************************************************************************
357 template <class T>
358 void CArray2D<T>::init(uint width,uint height, const T &defaultValue)
359 {
360 _Array.resize(width * height, defaultValue);
361 _Width = width;
362 _Height = height;
363 }
366 // *********************************************************************************
367 // A height grid with wrapping
369 class CHeightGridWrapped
370 {
371 public:
372 class CGridElem
373 {
374 public:
375 sint X;
376 sint Y;
377 float Z;
378 public:
379 bool operator == (const CGridElem &other) const
380 {
381 return X == other.X &&
382 Y == other.Y &&
383 Z == other.Z;
384 }
385 };
386 typedef std::list<CGridElem> TGridElemList;
387 // ctor
388 CHeightGridWrapped();
389 // Init with the given size
390 // The size is required to be a power of 2
391 void init(uint size, float cellSize);
392 inline void insert(const CGridElem &ge);
393 inline void remove(const CGridElem &ge);
394 const TGridElemList &getGridElemList(sint x, sint y) const { return _Grid(x & _SizeMask, y & _SizeMask); }
395 uint getSize() const { return _Grid.getWidth(); }
396 // tmp for debug
397 uint getListMaxLength() const;
398 private:
399 CArray2D<TGridElemList> _Grid;
400 float _CellSize;
401 float _InvCellSize;
402 uint _SizeMask;
403 };
407 // *********************************************************************************
408 inline void CHeightGridWrapped::insert(const CGridElem &ge)
409 {
410 _Grid(ge.X & _SizeMask, ge.Y & _SizeMask).push_back(ge);
411 }
413 // *********************************************************************************
414 inline void CHeightGridWrapped::remove(const CGridElem &ge)
415 {
416 TGridElemList &gel = _Grid(ge.X & _SizeMask, ge.Y & _SizeMask);
417 for(TGridElemList::iterator &it = gel.begin(); it != gel.end(); ++it)
418 {
419 if (*it == ge)
420 {
421 gel.erase(it);
422 return;
423 }
424 }
425 nlassert(0);
426 }
428 const float HEIGHT_GRID_MIN_Z = -10000.f;
430 // A height grid that give approximate z of geometry near the viewer.
431 // Useful to avoid precipitations in interiors / tunnels
432 //
433 class CHeightGrid : public NL3D::ULandscapeTileCallback
434 {
435 public:
436 // ctor
437 CHeightGrid();
438 // Init the grid before first use
439 // \param cellSize size of a cell of the height grid (in world unit)
440 // \param cellSize heightGridSize width/height of the height grid. It must be a power of 2
441 // \param cellSize wrappedHeightGridSize width/height of the wrapped height grid (for incoming geometry).
442 // It must be a power of 2.
443 // \param minZ Minimum possible Z
444 //
445 void init(float cellSize, uint heightGridSize, uint wrappedHeightGridSize, float minZ = HEIGHT_GRID_MIN_Z);
446 void update(const CVector &newPos);
447 // for debug, display the height grid on screen
448 void display(NL3D::UDriver &drv) const;
449 inline void gridCoordToWorld(sint x, sint y, CVector &dest) const;
450 inline CVector gridCoordToWorld(sint x, sint y) const;
451 // Remove a collision mesh (no op if not already added)
452 void removeCollisionMesh(uint id);
453 ///////////////////////////////////////////////////////////////////////
454 private:
455 typedef std::map<uint, UVisualCollisionManager::CMeshInstanceColInfo> TColMeshMap;
456 typedef std::vector<UVisualCollisionManager::CMeshInstanceColInfo> TColMeshVect;
457 CHeightGridWrapped _ZGridWrapped;
458 CArray2D<float> _ZGrid;
459 float _CellSize;
460 float _InvCellSize;
461 float _MinZ;
462 uint _GridSize;
463 uint _SizeMask;
464 sint _PosX;
465 sint _PosY;
466 std::vector<CRect> _UpdateRects;
467 CHashMap<uint64, CTileAddedInfo> _TileInfos;
468 CPolygon2D _Tri;
469 CPolygon2D::TRasterVect _Rasters;
470 TColMeshMap _Meshs; // meshs currenlty inserted in the wrapped grid
471 TColMeshVect _UpdateMeshs; // mesh to be removed / added to the wrapped grid during the update (keep there to avoid vector allocation)
472 std::vector<CVector> _CurrMeshVertices; // vertices of the mesh being inserted
473 CAABBox _BBox; // bbox containing current grid
474 private:
475 void updateBBox();
476 void updateRect(const CRect &rect);
477 void discardRect(const CRect &rect);
478 void updateCell(sint x, sint y);
479 // from ULandscapeTileCallback
480 virtual void tileAdded(const CTileAddedInfo &infos);
481 virtual void tileRemoved(uint64 id);
482 // add a tri in the height grid, and update height grid if necessary
483 void addTri(const CVector2f corners[3], float z);
484 void removeTri(const CVector2f corners[3], float z);
485 // Add a collision mesh (doesn't test if already inserted)
486 void addCollisionMesh(const UVisualCollisionManager::CMeshInstanceColInfo &colMesh);
487 };
489 // ***********************************************************************************
490 inline void CHeightGrid::gridCoordToWorld(sint x, sint y, CVector &dest) const
491 {
492 dest.set(x * _CellSize, y * _CellSize, 0.f);
493 }
495 // ***********************************************************************************
496 inline CVector CHeightGrid::gridCoordToWorld(sint x, sint y) const
497 {
498 CVector dest;
499 gridCoordToWorld(x, y, dest);
500 return dest;
501 }
506 // TMP TMP TMP TMP
507 // TMP TMP TMP TMP
508 // TMP TMP TMP TMP
509 // TMP TMP TMP TMP
510 extern CHeightGrid HeightGrid;
513 */
515 /**
516 * Class to know where precipitation can't fall
517 * This is a grid that is updated with the position of the player
518 * It tells when the quad is in an interior mesh, and gives the
519 * mean height for a point of the quad (for landscape)
520 * \author Nicolas Vizerie
521 * \author Nevrax France
522 * \date 2002
523 */
525 class CPrecipitationClipGrid
526 {
528 /** Point of the grid
529 */
530 struct CGridPoint
531 {
534 CGridPoint(float meanHeight = 0.f, bool clipped = true) : MeanHeight(meanHeight), Clipped(clipped)
535 {}
536 };
538 // ctor
540 /** init the grid
541 * \param size width & height of the grid so the grid has (size + 1) ^2 elements. For example if size is 1, the grid is a simple square and it has four corners.
542 * \param gridEltSize width & height of a grid element.
543 */
546 // Update the grid so that it match the position of the user. (this grid is centered at the user pos)
549 /** Get grid element point its grid coordinate in world
550 * \return NULL if the element is outside the grid
551 */
554 // for debug, display the clip grid on screen
557 // Force the whole grid to be recomputed
560 /////////////////////////////////////////////////////////
561 /////////////////////////////////////////////////////////
566 sint _XPos;
567 sint _YPos;
568 uint _Size;
571 TGrid _Grid;
574 void updateGridPart(sint worldX, sint worldY, uint gridX, uint gridY, uint width, uint height, NLPACS::UGlobalRetriever *globalRetriever);
579 {
584 }
586 {
591 }
592 };
595 #endif