?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Update checkRpItemsPosition and getTeam
[ryzomcore.git] / nel / tools / pacs / build_rbank / surface_splitter.h
blob3cf035e9d3263f7407b2ecc3287c0a9a6b32d994
1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
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/>.
16
17 #ifndef NL_SURFACE_SPLITTER_H
18 #define NL_SURFACE_SPLITTER_H
19
20 #include "nel/misc/types_nl.h"
21
22 #include "nel/pacs/local_retriever.h"
23 #include "nel/pacs/quad_grid.h"
24
25 #include <map>
26
27 /**
28 * TODO Class description
29 * \author Benjamin Legros
30 * \author Nevrax France
31 * \date 2002
32 */
33 class CSurfaceSplitter
34 {
35 public:
36
37 ///
38 class CVector2s64;
39 class CSurfaceId;
40 class CChain;
41 class CLoop;
42 class CSurface;
43
44 ///
45 class CFixed64
46 {
47 protected:
48 sint64 _Value;
49 public:
50 CFixed64() : _Value(0) {}
51 CFixed64(const sint64 &v) : _Value(v) {}
52 CFixed64(const double &v) : _Value((sint64)(v*4294967296.0)) {}
53 CFixed64(const CFixed64 &v) : _Value(v._Value) {}
54
55 operator double(void) const { return ((double)_Value) / 4294967296.0; }
56 operator float(void) const { return ((float)_Value) / 4294967296.0f; }
57 operator sint64(void) const { return _Value; }
58
59 CFixed64 operator + (const CFixed64 &f) const { return CFixed64(_Value + f._Value); }
60 CFixed64 operator - (const CFixed64 &f) const { return CFixed64(_Value - f._Value); }
61 CFixed64 operator - () const { return CFixed64(-_Value); }
62 CFixed64 operator * (const CFixed64 &f) const
63 {
64 sint64 vh = _Value>>32;
65 sint64 vl = _Value&0xffffffff;
66 sint64 uh = f._Value>>32;
67 sint64 ul = f._Value&0xffffffff;
68
69 sint64 res = ((vh*uh)<<32)+(vh*ul+uh*vl)+((uint64)(vl*ul)>>32);
70 double fres = ((double)res) / 4294967296.0;
71 double cfres = (double)(*this) * (double)f;
72 return CFixed64(res);
73 }
74 CFixed64 operator / (const CFixed64 &f) const
75 {
76 if (f._Value == 0)
77 return CFixed64();
78
79 sint sign = 0;
80 uint64 a = _Value;
81 uint64 b = f._Value;
82
83 if ((sint64)a < 0)
84 a = -(sint64)a, sign ^= 1;
85 if ((sint64)b < 0)
86 b = -(sint64)b, sign ^= 1;
87
88 uint64 lb = INT64_CONSTANT (0x8000000000000000);
89 uint64 q = 0;
90 uint64 nh = a>>32;
91 uint64 nl = a<<32;
92
93 while (lb != 0)
94 {
95 if (nh >= b)
96 {
97 q |= (lb+lb);
98 nh -= b;
99 }
100 nh = (nh+nh) + (nl&lb ? 1 : 0);
101 lb >>= 1;
102 }
103
104 // round final bit
105 if (nh >= b)
106 ++q;
107
108 CFixed64 result(sign ? -(sint64)q : +(sint64)q );
109 return result;
110 }
111
112 CFixed64 &operator += (const CFixed64 &f) { _Value+=f._Value; return *this; }
113 CFixed64 &operator -= (const CFixed64 &f) { _Value-=f._Value; return *this; }
114 CFixed64 &operator *= (const CFixed64 &f) { *this = *this*f; return *this; }
115 CFixed64 &operator /= (const CFixed64 &f) { *this = *this/f; return *this; }
116
117 bool operator == (const CFixed64 &f) const { return _Value == f._Value; }
118 bool operator != (const CFixed64 &f) const { return _Value != f._Value; }
119 bool operator < (const CFixed64 &f) const { return _Value < f._Value; }
120 bool operator <= (const CFixed64 &f) const { return _Value <= f._Value; }
121 bool operator >= (const CFixed64 &f) const { return _Value >= f._Value; }
122 bool operator > (const CFixed64 &f) const { return _Value > f._Value; }
123
124 double sqnorm() const { return (double)(*this * *this); }
125 double norm() const { return sqrt(sqnorm()); }
126 };
127
128 ///
129 class CVector2s64
130 {
131 public:
132 CFixed64 x;
133 CFixed64 y;
134
135 CVector2s64() : x(), y() {}
136 CVector2s64(const sint64 &X, const sint64 &Y) : x(X), y(Y) {}
137 CVector2s64(const CFixed64 &X, const CFixed64 &Y) : x(X), y(Y) {}
138 CVector2s64(const NLMISC::CVector &v) : x(v.x), y(v.y) {}
139 CVector2s64(const NLMISC::CVectorD &v) : x(v.x), y(v.y) {}
140 CVector2s64(const NLPACS::CVector2s &v) : x(((sint64)v.x) << 25), y(((sint64)v.y) << 25) {}
141
142 CVector2s64 operator + (const CVector2s64 &v) const { return CVector2s64(x+v.x, y+v.y); }
143 CVector2s64 operator - (const CVector2s64 &v) const { return CVector2s64(x-v.x, y-v.y); }
144 CVector2s64 operator * (sint64 s) const { return CVector2s64(x*CFixed64(s), y*CFixed64(s)); }
145 CVector2s64 operator * (CFixed64 s) const { return CVector2s64(x*s, y*s); }
146 CVector2s64 operator * (double s) const { return CVector2s64(x*CFixed64(s), y*CFixed64(s)); }
147 CVector2s64 operator / (sint64 s) const { return CVector2s64(x*CFixed64(s), y*CFixed64(s)); }
148 CVector2s64 operator / (CFixed64 s) const { return CVector2s64(x*s, y*s); }
149 CVector2s64 operator / (double s) const { return CVector2s64(x*CFixed64(s), y*CFixed64(s)); }
150 CFixed64 operator * (const CVector2s64 &v) const { return x*v.x + y*v.y; }
151 CFixed64 operator ^ (const CVector2s64 &v) const { return x*v.y - y*v.x; }
152
153 bool operator == (const CVector2s64 &v) const { return x == v.x && y == v.y; }
154 bool operator != (const CVector2s64 &v) const { return x != v.x || y != v.y; }
155
156 CVector2s64 &operator += (const CVector2s64 &v)
157 {
158 x += v.x;
159 y += v.y;
160 return *this;
161 }
162 CVector2s64 &operator -= (const CVector2s64 &v)
163 {
164 x -= v.x;
165 y -= v.y;
166 return *this;
167 }
168 CVector2s64 &operator *= (sint64 s)
169 {
170 CFixed64 ss(s);
171 x *= ss;
172 y *= ss;
173 return *this;
174 }
175 CVector2s64 &operator *= (double s)
176 {
177 CFixed64 ss(s);
178 x *= ss;
179 y *= ss;
180 return *this;
181 }
182
183 NLMISC::CVector asVector() const
184 {
185 return NLMISC::CVector((float)x, (float)y, 0.0f);
186 }
187 NLMISC::CVectorD asVectorD() const
188 {
189 return NLMISC::CVectorD((double)x, (double)y, 0.0);
190 }
191 };
192
193 ///
194 class CSurfaceId
195 {
196 public:
197 uint16 Instance;
198 uint16 Surface;
199 uint16 SubSurface;
200
201 CSurfaceId(uint16 instance=65535, uint16 surface=65535, uint16 subsurface=0) :
202 Instance(instance),
203 Surface(surface),
204 SubSurface(subsurface) {}
205
206 bool operator == (const CSurfaceId &id) const { return Instance == id.Instance && Surface == id.Surface && SubSurface == id.SubSurface; }
207 bool operator != (const CSurfaceId &id) const { return !(*this == id); }
208
209 bool operator < (const CSurfaceId &id) const
210 {
211 if (Instance < id.Instance)
212 return true;
213 else if (Instance > id.Instance)
214 return false;
215 else if (Surface < id.Surface)
216 return true;
217 else if (Surface > id.Surface)
218 return false;
219 else
220 return SubSurface < id.SubSurface;
221 }
222
223 bool operator > (const CSurfaceId &id) const { return id < *this; }
224 bool operator <= (const CSurfaceId &id) const { return *this == id || *this < id; }
225 bool operator >= (const CSurfaceId &id) const { return *this == id || id < *this; }
226 };
227
228 ///
229 class CChainId
230 {
231 public:
232 CChainId(uint32 id=0) : Id(id) {}
233 uint32 Id;
234
235 bool operator == (const CChainId &id) const { return Id == id.Id; }
236 bool operator != (const CChainId &id) const { return !(*this == id); }
237 bool operator < (const CChainId &id) const { return Id < id.Id; }
238 bool operator > (const CChainId &id) const { return id < *this; }
239 bool operator <= (const CChainId &id) const { return *this == id || *this < id; }
240 bool operator >= (const CChainId &id) const { return *this == id || id < *this; }
241 };
242
243
244 ///
245 class CEdgeId
246 {
247 public:
248 CEdgeId(const CChainId &chain=CChainId(), uint edge=0) : Chain(chain), Edge(edge) {}
249 CChainId Chain;
250 uint Edge;
251 };
252
253 typedef NLPACS::CQuadGrid<CEdgeId> TEdgeGrid;
254
255
256 ///
257 class CTipId
258 {
259 public:
260 CTipId(uint32 id=0) : Id(id) {}
261 uint32 Id;
262
263 bool operator == (const CTipId &id) const { return Id == id.Id; }
264 bool operator != (const CTipId &id) const { return !(*this == id); }
265 bool operator < (const CTipId &id) const { return Id < id.Id; }
266 bool operator > (const CTipId &id) const { return id < *this; }
267 bool operator <= (const CTipId &id) const { return *this == id || *this < id; }
268 bool operator >= (const CTipId &id) const { return *this == id || id < *this; }
269 };
270
271
272
273
274 ///
275 class CChain
276 {
277 public:
278 CChainId Id;
279 CSurfaceId Left;
280 CSurfaceId Right;
281 CTipId Start;
282 CTipId Stop;
283 std::vector<CVector2s64> Vertices;
284 std::vector<TEdgeGrid::CIterator> Iterators;
285 bool DontSplit;
286
287 ///
288 CChain() : DontSplit(false) {}
289
290 ///
291 void dump(bool forward) const
292 {
293 NLMISC::InfoLog->displayRawNL("Chain:%d[Left=%d:%d:%d,Right=%d:%d:%d]", Id.Id, Left.Instance, Left.Surface, Left.SubSurface, Right.Instance, Right.Surface, Right.SubSurface);
294 sint i, j=0;
295 if (forward)
296 {
297 for (i=0; i<(sint)Vertices.size(); ++i, ++j)
298 NLMISC::InfoLog->displayRawNL("%d;%.3f;%.3f", j, (double)Vertices[i].x, (double)Vertices[i].y);
299 }
300 else
301 {
302 for (i=(sint)Vertices.size()-1; i>=0; --i, ++j)
303 NLMISC::InfoLog->displayRawNL("%d;%.3f;%.3f", j, (double)Vertices[i].x, (double)Vertices[i].y);
304 }
305 }
306 };
307
308
309
310 ///
311 class CTip
312 {
313 public:
314 CTipId Id;
315 CVector2s64 Tip;
316 std::vector<CChainId> Chains;
317 };
318
319
320
321 ///
322 class CLoop
323 {
324 public:
325 CSurfaceId Surface;
326 std::vector<CChainId> Chains;
327
328 ///
329 void dump(const CSurfaceSplitter &splitter) const
330 {
331 uint i;
332 for (i=0; i<Chains.size(); ++i)
333 {
334 const CChain *chain = splitter.getChain(Chains[i]);
335 if (chain != NULL)
336 chain->dump(Surface == chain->Left);
337 }
338 }
339
340 ///
341 void removeChain(CChainId chain)
342 {
343 std::vector<CChainId>::iterator it;
344 for (it=Chains.begin(); it!=Chains.end(); )
345 {
346 if (*it == chain)
347 it = Chains.erase(it);
348 else
349 ++it;
350 }
351 }
352
353 ///
354 class iterator
355 {
356 public:
357 CSurfaceSplitter *pSplitter;
358 CLoop *pLoop;
359 sint Chain;
360 CChain *pChain;
361 sint ChainVertex;
362 sint8 Direction;
363 sint8 ChainDirection;
364
365 iterator(CSurfaceSplitter *splitter=NULL, CLoop *loop=NULL, bool forward=true) : pSplitter(splitter), pLoop(loop), Chain(0), pChain(NULL), ChainVertex(0), Direction(0), ChainDirection(0)
366 {
367 Direction = forward ? +1 : -1;
368 if (splitter == NULL || pLoop == NULL)
369 return;
370 Chain = (Direction>0 ? 0 : (sint)pLoop->Chains.size()-1);
371 resetChain();
372 }
373 iterator(const iterator &it)
374 {
375 *this = it;
376 }
377
378 iterator &operator = (const iterator &it)
379 {
380 pSplitter = it.pSplitter;
381 pLoop = it.pLoop;
382 Chain = it.Chain;
383 pChain = it.pChain;
384 ChainVertex = it.ChainVertex;
385 Direction = it.Direction;
386 return *this;
387 }
388 bool operator == (const iterator &it)
389 {
390 return pSplitter == it.pSplitter &&
391 pLoop == it.pLoop &&
392 Chain == it.Chain &&
393 ChainVertex == it.ChainVertex;
394 }
395 bool operator != (const iterator &it) { return !(*this == it); }
396
397 // ++it
398 iterator &operator ++ ()
399 {
400 ChainVertex += ChainDirection;
401 if (ChainVertex == 0 || ChainVertex == (sint)pChain->Vertices.size()-1)
402 {
403 Chain += Direction;
404 resetChain();
405 }
406
407 return *this;
408 }
409
410 // it++
411 iterator operator ++ (int)
412 {
413 iterator tmp(*this);
414
415 ChainVertex += ChainDirection;
416 if (ChainVertex == 0 || ChainVertex == (sint)pChain->Vertices.size()-1)
417 {
418 Chain += Direction;
419 resetChain();
420 }
421
422 return tmp;
423 }
424
425 void resetChain()
426 {
427 if (Chain < 0 || Chain == (sint)pLoop->Chains.size())
428 {
429 pSplitter = NULL;
430 pLoop = NULL;
431 Chain = 0;
432 pChain = NULL;
433 ChainVertex = 0;
434 Direction = 0;
435 ChainDirection = 0;
436 return;
437 }
438 pChain = pSplitter->getChain(pLoop->Chains[Chain]);
439 ChainDirection = (pChain->Left == pLoop->Surface ? Direction : -Direction);
440 ChainVertex = (ChainDirection>0 ? 0 : (sint)pChain->Vertices.size()-1);
441 }
442
443 CVector2s64 operator * () const
444 {
445 return pChain->Vertices[ChainVertex];
446 }
447 };
448 };
449
450
451
452 ///
453 class CSurface
454 {
455 public:
456 CSurfaceId Id;
457 std::vector<CLoop> Loops;
458
459 ///
460 void dump(const CSurfaceSplitter &splitter) const
461 {
462 NLMISC::InfoLog->displayRawNL("---Surface:%d:%d:%d", Id.Instance, Id.Surface, Id.SubSurface);
463 uint i;
464 for (i=0; i<Loops.size(); ++i)
465 {
466 NLMISC::InfoLog->displayRawNL("Loop:%d", i);
467 Loops[i].dump(splitter);
468 }
469 }
470
471 ///
472 void removeChain(CChainId chain)
473 {
474 uint i;
475 for (i=0; i<Loops.size(); ++i)
476 Loops[i].removeChain(chain);
477 }
478 };
479
480 protected:
481 typedef std::map<CSurfaceId, CSurface> TSurfaceMap;
482 typedef std::map<CChainId, CChain> TChainMap;
483 typedef std::map<CTipId, CTip> TTipMap;
484
485 TSurfaceMap _Surfaces;
486 uint _NumSurfaces;
487 TChainMap _Chains;
488 uint _NumChains;
489 TTipMap _Tips;
490 uint _NumTips;
491
492 TEdgeGrid _Edges;
493
494
495 public:
496
497 /// Constructor
498 CSurfaceSplitter();
499
500 ///
501 void build(NLPACS::CLocalRetriever &lr);
502
503 ///
504 CSurface *getSurface(const CSurfaceId &id)
505 {
506 TSurfaceMap::iterator it = _Surfaces.find(id);
507 return (it == _Surfaces.end() ? NULL : &((*it).second));
508 }
509
510 ///
511 CChain *getChain(const CChainId &id)
512 {
513 TChainMap::iterator it = _Chains.find(id);
514 return (it == _Chains.end() ? NULL : &((*it).second));
515 }
516
517 ///
518 const CSurface *getSurface(const CSurfaceId &id) const
519 {
520 TSurfaceMap::const_iterator it = _Surfaces.find(id);
521 return (it == _Surfaces.end() ? NULL : &((*it).second));
522 }
523
524 ///
525 const CChain *getChain(const CChainId &id) const
526 {
527 TChainMap::const_iterator it = _Chains.find(id);
528 return (it == _Chains.end() ? NULL : &((*it).second));
529 }
530
531
532
533 protected:
534
535 ///
536 void buildChain(NLPACS::CLocalRetriever &lr, uint chain);
537
538 ///
539 void buildSurface(NLPACS::CLocalRetriever &lr, uint surface);
540
541
542
543 ///
544 void initEdgeGrid();
545
546
547
548 ///
549 void splitChains();
550
551 ///
552 void splitChain(TChainMap::iterator it, uint &numInters);
553
554
555
556 ///
557 void dump() const
558 {
559 TSurfaceMap::const_iterator it;
560
561 for (it=_Surfaces.begin(); it!=_Surfaces.end(); ++it)
562 (*it).second.dump(*this);
563 }
564
565 ///
566 void dumpChain(CChainId chain) const
567 {
568 TChainMap::const_iterator it = _Chains.find(chain);
569 if (it == _Chains.end())
570 return;
571
572 (*it).second.dump(true);
573 }
574
575
576
577 ///
578 bool intersect(const CVector2s64 &v0, const CVector2s64 &v1,
579 const CVector2s64 &c0, const CVector2s64 &c1,
580 CVector2s64 &intersect, CFixed64 &ndist);
581
582
583
584
585 ///
586 CChainId addChain(const CSurfaceId &left, const CSurfaceId &right, const std::vector<CVector2s64> &points, bool dontSplit=false);
587
588 ///
589 void removeChain(CChainId chain);
590
591 ///
592 void replaceChain(CChainId chain, const std::vector<CChainId> &chains);
593 };
594
595
596 #endif // NL_SURFACE_SPLITTER_H
597
598 /* End of surface_splitter.h */