?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Merge branch 'fixes' into main/rendor-staging
[ryzomcore.git] / nel / src / pacs / local_retriever.cpp
blob9a73e8b2832b8f7ef5c4988bb5a78cff3a893618
1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
2 // Copyright (C) 2010 Winch Gate Property Limited
3 //
4 // This source file has been modified by the following contributors:
5 // Copyright (C) 2015-2019 Jan BOON (Kaetemi) <jan.boon@kaetemi.be>
6 //
7 // This program is free software: you can redistribute it and/or modify
8 // it under the terms of the GNU Affero General Public License as
9 // published by the Free Software Foundation, either version 3 of the
10 // License, or (at your option) any later version.
11 //
12 // This program is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU Affero General Public License for more details.
16 //
17 // You should have received a copy of the GNU Affero General Public License
18 // along with this program. If not, see <http://www.gnu.org/licenses/>.
19
20 #include "stdpacs.h"
21
22 #include <sstream>
23
24 #include "nel/misc/plane.h"
25
26 #include "nel/pacs/local_retriever.h"
27 #include "nel/pacs/collision_desc.h"
28 #include "nel/pacs/retriever_instance.h"
29
30 #include "nel/misc/hierarchical_timer.h"
31
32
33 using namespace std;
34 using namespace NLMISC;
35
36 /// The max distance allowed to merge tips.
37 const float NLPACS::CLocalRetriever::_TipThreshold = 0.1f;
38 const float NLPACS::CLocalRetriever::_EdgeTipThreshold = 0.1f;
39
40 /// The threshold distance to insure a position belongs to a surface
41 const float InsurePositionThreshold = 2.0e-2f;
42
43 //static float hybrid2dNorm(const CVector &v)
44 //{
45 // return (float)(sqrt(sqr(v.x)+sqr(v.y))+fabs(v.z)*0.1);
46 //}
47
48
49
50
51
52 NLPACS::CLocalRetriever::CLocalRetriever()
53 {
54 _Type = Landscape;
55 _Loaded = false;
56 LoadCheckFlag = false;
57 }
58
59
60 void NLPACS::CLocalRetriever::clear()
61 {
62 contReset(_OrderedChains);
63 contReset(_FullOrderedChains);
64 contReset(_Chains);
65 contReset(_Surfaces);
66 contReset(__Tips);
67 contReset(_BorderChains);
68 uint i;
69 for (i=0; i<NumMaxCreatureModels; ++i)
70 contReset(_Topologies[i]);
71 _ChainQuad.clear();
72 _ExteriorMesh.clear();
73 contReset(_InteriorVertices);
74 contReset(_InteriorFaces);
75 _FaceGrid.clear();
76 _Id.resize(0);
77 _Loaded = false;
78 LoadCheckFlag = false;
79 }
80
81
82 const CVector &NLPACS::CLocalRetriever::getStartVector(uint32 chain) const
83 {
84 const COrderedChain3f &ochain = _FullOrderedChains[_Chains[chain].getSubChains().front()];
85 return (ochain.isForward()) ? ochain.getVertices().front() : ochain.getVertices().back();
86 }
87
88 const CVector &NLPACS::CLocalRetriever::getStopVector(uint32 chain) const
89 {
90 const COrderedChain3f &ochain = _FullOrderedChains[_Chains[chain].getSubChains().back()];
91 return (ochain.isForward()) ? ochain.getVertices().back() : ochain.getVertices().front();
92 }
93
94
95
96
97 const CVector &NLPACS::CLocalRetriever::getStartVector(uint32 chain, sint32 surface) const
98 {
99 bool onLeft = _Chains[chain].getLeft() == surface;
100 const COrderedChain3f &ochain = onLeft ? _FullOrderedChains[_Chains[chain].getSubChains().front()] :
101 _FullOrderedChains[_Chains[chain].getSubChains().back()];
102
103 if (ochain.isForward() == onLeft)
104 return ochain.getVertices().front();
105 else
106 return ochain.getVertices().back();
107 }
108
109 const CVector &NLPACS::CLocalRetriever::getStopVector(uint32 chain, sint32 surface) const
110 {
111 bool onLeft = _Chains[chain].getLeft() == surface;
112 const COrderedChain3f &ochain = onLeft ? _FullOrderedChains[_Chains[chain].getSubChains().back()] :
113 _FullOrderedChains[_Chains[chain].getSubChains().front()];
114
115 if (ochain.isForward() == onLeft)
116 return ochain.getVertices().back();
117 else
118 return ochain.getVertices().front();
119 }
120
121
122
123 /*
124 uint16 NLPACS::CLocalRetriever::getStartTip(uint32 chain, sint32 surface) const
125 {
126 return (_Chains[chain].getLeft() == surface) ? _Chains[chain].getStartTip() : _Chains[chain].getStopTip();
127 }
128
129 uint16 NLPACS::CLocalRetriever::getStopTip(uint32 chain, sint32 surface) const
130 {
131 return (_Chains[chain].getLeft() == surface) ? _Chains[chain].getStopTip() : _Chains[chain].getStartTip();
132 }
133
134
135
136
137
138 void NLPACS::CLocalRetriever::setStartTip(uint32 chain, sint32 surface, uint16 startTip)
139 {
140 if (_Chains[chain].getLeft() == surface)
141 _Chains[chain]._StartTip = startTip;
142 else
143 _Chains[chain]._StopTip = startTip;
144 }
145
146 void NLPACS::CLocalRetriever::setStopTip(uint32 chain, sint32 surface, uint16 stopTip)
147 {
148 if (_Chains[chain].getLeft() == surface)
149 _Chains[chain]._StopTip = stopTip;
150 else
151 _Chains[chain]._StartTip = stopTip;
152 }
153 */
154
155
156
157 uint32 NLPACS::CLocalRetriever::getPreviousChain(uint32 chain, sint32 surface) const
158 {
159 uint loop;
160 uint loopIndex;
161
162 if (_Chains[chain].getLeft() == surface)
163 {
164 loop = _Chains[chain]._LeftLoop;
165 loopIndex = _Chains[chain]._LeftLoopIndex;
166 }
167 else
168 {
169 loop = _Chains[chain]._RightLoop;
170 loopIndex = _Chains[chain]._RightLoopIndex;
171 }
172
173 const CRetrievableSurface &surf = _Surfaces[surface];
174 const CRetrievableSurface::TLoop &sLoop = surf._Loops[loop];
175 return surf._Chains[sLoop[(loopIndex+sLoop.size()-1)%sLoop.size()]].Chain;
176 }
177
178 uint32 NLPACS::CLocalRetriever::getNextChain(uint32 chain, sint32 surface) const
179 {
180 uint loop;
181 uint loopIndex;
182
183 if (_Chains[chain].getLeft() == surface)
184 {
185 loop = _Chains[chain]._LeftLoop;
186 loopIndex = _Chains[chain]._LeftLoopIndex;
187 }
188 else
189 {
190 loop = _Chains[chain]._RightLoop;
191 loopIndex = _Chains[chain]._RightLoopIndex;
192 }
193
194 const CRetrievableSurface &surf = _Surfaces[surface];
195 const CRetrievableSurface::TLoop &sLoop = surf._Loops[loop];
196 return surf._Chains[sLoop[(loopIndex+1)%sLoop.size()]].Chain;
197 }
198
199
200
201
202 void NLPACS::CLocalRetriever::unify()
203 {
204 /*
205 uint i, j;
206
207 for (i=0; i<_Chains.size(); ++i)
208 _Chains[i].unify(_OrderedChains);
209
210 for (i=0; i<_Tips.size(); ++i)
211 {
212 NLPACS::CLocalRetriever::CTip &tip = _Tips[i];
213 CVector2s ptip = tip.Point;
214
215 for (j=0; j<tip.Chains.size(); ++j)
216 {
217 if (tip.Chains[j].Start)
218 {
219 if (_Chains[tip.Chains[j].Chain].getStartVector(_OrderedChains) != ptip)
220 nlwarning("chain %d is not stuck to tip %d", tip.Chains[j].Chain, i);
221 _Chains[tip.Chains[j].Chain].setStartVector(ptip, _OrderedChains);
222 }
223 else
224 {
225 if (_Chains[tip.Chains[j].Chain].getStopVector(_OrderedChains) != ptip)
226 nlwarning("chain %d is not stuck to tip %d", tip.Chains[j].Chain, i);
227 _Chains[tip.Chains[j].Chain].setStopVector(ptip, _OrderedChains);
228 }
229 }
230 }
231
232 _FullOrderedChains.resize(_OrderedChains.size());
233 for (i=0; i<_OrderedChains.size(); ++i)
234 _FullOrderedChains[i].unpack(_OrderedChains[i]);
235 */
236 }
237
238
239
240
241
242
243
244 void NLPACS::CLocalRetriever::dumpSurface(uint surf, const CVector &vect) const
245 {
246 const CRetrievableSurface &surface = _Surfaces[surf];
247
248 nlinfo("dump surf %d", surf);
249 nlinfo("%d chains, %d loops", surface._Chains.size(), surface._Loops.size());
250
251 uint i, j, k;
252
253 for (i=0; i<surface._Chains.size(); ++i)
254 {
255 uint chainId = surface._Chains[i].Chain;
256 const CChain &chain = _Chains[chainId];
257 nlinfo("-- chain %d[%d]: %d sub left=%d right=%d start=%d stop=%d", i, chainId, chain.getSubChains().size(), chain.getLeft(), chain.getRight(), chain.getStartTip(), chain.getStopTip());
258
259 for (j=0; j<chain.getSubChains().size(); ++j)
260 {
261 const COrderedChain3f &ochain = _FullOrderedChains[chain.getSubChain(j)];
262 const COrderedChain &ochains = _OrderedChains[chain.getSubChain(j)];
263 nlinfo(" subchain %d[%d]: fwd=%d parent=%d idx=%d", j, chain.getSubChain(j), ochain.isForward(), ochain.getParentId(), ochain.getIndexInParent());
264 for (k=0; k<ochain.getVertices().size(); ++k)
265 nlinfo(" v[%d]=(%.3f,%.3f,%.3f) (%d,%d)", k, ochain.getVertices()[k].x+vect.x, ochain.getVertices()[k].y+vect.y, ochain.getVertices()[k].z+vect.z, ochains.getVertices()[k].x, ochains.getVertices()[k].y);
266 }
267
268 }
269
270 for (i=0; i<surface._Loops.size(); ++i)
271 {
272 const CRetrievableSurface::TLoop &loop = surface._Loops[i];
273 nlinfo("-- loop %d: %d chains length=%.2f", i, loop.size(), loop.Length);
274 char wbuffer[256];
275 stringstream ss;
276 sprintf(wbuffer, " chains:");
277 ss << wbuffer;
278 for (j=0; j<loop.size(); ++j)
279 {
280 sprintf(wbuffer, " %d[%d]", loop[j], surface._Chains[loop[j]].Chain);
281 ss << wbuffer;
282 }
283 nlinfo("%s", ss.str().c_str());
284 }
285 }
286
287
288 float NLPACS::CLocalRetriever::distanceToBorder(const ULocalPosition &pos) const
289 {
290 if (!isLoaded())
291 return 0.0f;
292
293 const CRetrievableSurface &surf = _Surfaces[pos.Surface];
294 uint i, j;
295 float minDist = 1.0e10f, dist;
296
297 for (i=0; i<surf._Chains.size(); ++i)
298 {
299 const CChain &chain = _Chains[surf._Chains[i].Chain];
300 for (j=0; j<chain.getSubChains().size(); ++j)
301 {
302 dist = _OrderedChains[chain.getSubChain(j)].distance(pos.Estimation);
303 if (dist < minDist)
304 {
305 minDist = dist;
306 }
307 }
308 }
309
310 return minDist;
311 }
312
313
314
315
316
317 sint32 NLPACS::CLocalRetriever::addSurface(uint8 normalq, uint8 orientationq,
318 uint8 mat, uint8 charact, uint8 level,
319 bool isUnderWater, float waterHeight,
320 bool clusterHint,
321 const CVector &center,
322 const NLPACS::CSurfaceQuadTree &quad,
323 sint8 quantHeight)
324 {
325 // creates a new surface...
326 sint32 newId = (sint32)_Surfaces.size();
327 _Surfaces.resize(newId+1);
328 CRetrievableSurface &surf = _Surfaces.back();
329
330 // ... and fills it
331 surf._NormalQuanta = normalq;
332 surf._OrientationQuanta = orientationq;
333 surf._Material = mat;
334 surf._Character = charact;
335 surf._Level = level;
336 surf._Quad = quad;
337 surf._Center = center;
338 surf._QuantHeight = quantHeight;
339
340 // WARNING!! MODIFY THESE IF QUANTAS VALUES CHANGE !!
341 surf._IsFloor = (surf._NormalQuanta <= 1);
342 surf._IsCeiling = (surf._NormalQuanta >= 3);
343
344 surf._Flags = 0;
345 surf._Flags |= (surf._IsFloor) ? (1<<CRetrievableSurface::IsFloorBit) : 0;
346 surf._Flags |= (surf._IsCeiling) ? (1<<CRetrievableSurface::IsCeilingBit) : 0;
347 surf._Flags |= (!surf._IsFloor && !surf._IsCeiling) ? (1<<CRetrievableSurface::IsSlantBit) : 0;
348 surf._Flags |= clusterHint ? (1<<CRetrievableSurface::ClusterHintBit) : 0;
349
350 surf._Flags |= (isUnderWater) ? (1<<CRetrievableSurface::IsUnderWaterBit) : 0;
351 surf._WaterHeight = waterHeight;
352
353 surf._Flags |= ((0xffffffff<<(CRetrievableSurface::NormalQuantasStartBit)) & CRetrievableSurface::NormalQuantasBitMask);
354
355 return newId;
356 }
357
358 sint32 NLPACS::CLocalRetriever::addChain(const vector<CVector> &verts,
359 sint32 left, sint32 right)
360 {
361 vector<CVector> vertices = verts;
362 uint i;
363
364 if (vertices.size() < 2)
365 {
366 nlwarning("in NLPACS::CLocalRetriever::addChain()");
367 nlwarning("The chain has less than 2 vertices");
368 return -1;
369 }
370
371 // Remove doubled vertices due to CVector2s snapping
372 vector<CVector2s> converts;
373
374 for (i=0; i<vertices.size(); ++i)
375 converts.push_back(CVector2s(vertices[i]));
376
377 vector<CVector2s>::iterator next2s = converts.begin(), it2s, prev2s;
378 prev2s = next2s; ++next2s;
379 it2s = next2s; ++next2s;
380
381 vector<CVector>::iterator it3f = vertices.begin();
382 CVector prev3f = *it3f;
383 ++it3f;
384
385
386 for (; it2s != converts.end() && next2s != converts.end(); )
387 {
388 // if the next point is equal to the previous
389 if (*it2s == *prev2s || *it2s == *next2s)
390 {
391 // then remove the next point
392 it2s = converts.erase(it2s);
393 it3f = vertices.erase(it3f);
394
395 prev2s = it2s;
396 --prev2s;
397 next2s = it2s;
398 ++next2s;
399 }
400 else
401 {
402 // else remember the next point, and step to the next...
403 ++prev2s;
404 ++it2s;
405 ++next2s;
406 ++it3f;
407 prev3f = *it3f;
408 }
409 }
410
411 if (vertices.size() < 2)
412 {
413 nlwarning("in NLPACS::CLocalRetriever::addChain()");
414 nlwarning("The chain was snapped to a single point");
415 return -1;
416 }
417
418 sint32 newId = (sint32)_Chains.size();
419 _Chains.resize(newId+1);
420 CChain &chain = _Chains.back();
421
422 if (left>(sint)_Surfaces.size())
423 nlerror ("left surface id MUST be id<%d (id=%d)", _Surfaces.size(), left);
424 if (right>(sint)_Surfaces.size())
425 nlerror ("right surface id MUST be id<%d (id=%d)", _Surfaces.size(), right);
426
427 // checks if we can build the chain.
428 if (newId > 65535)
429 nlerror("in NLPACS::CLocalRetriever::addChain(): reached the maximum number of chains");
430
431 CRetrievableSurface *leftSurface = (left>=0) ? &(_Surfaces[left]) : NULL;
432 CRetrievableSurface *rightSurface = (right>=0) ? &(_Surfaces[right]) : NULL;
433
434 // adds the chain and the link to the surface links vector.
435 if (leftSurface != NULL)
436 leftSurface->_Chains.push_back(CRetrievableSurface::CSurfaceLink(newId, right));
437 if (rightSurface != NULL)
438 rightSurface->_Chains.push_back(CRetrievableSurface::CSurfaceLink(newId, left));
439
440 chain._StartTip = 0xffff;
441 chain._StopTip = 0xffff;
442
443 // make the chain and its subchains.
444 vector<uint> empty;
445 chain.make(vertices, left, right, _OrderedChains, (uint16)newId, _FullOrderedChains, empty);
446
447 return newId;
448 }
449
450
451
452
453 void NLPACS::CLocalRetriever::computeLoopsAndTips()
454 {
455 // for each surface,
456 // examine each chain tip to match another tip inside the surface tips
457 // if there is no matching tip, then creates a new one
458
459 uint i, j;
460
461 for (i=0; i<_Surfaces.size(); ++i)
462 {
463 CRetrievableSurface &surface = _Surfaces[i];
464
465 vector<bool> chainFlags;
466 chainFlags.resize(surface._Chains.size());
467 for (j=0; j<chainFlags.size(); ++j)
468 chainFlags[j] = false;
469
470 uint totalAdded = 0;
471
472 for(;;)
473 {
474 for (j=0; j<chainFlags.size() && chainFlags[j]; ++j)
475 ;
476
477 if (j == chainFlags.size())
478 break;
479
480 uint32 loopId = (uint32)surface._Loops.size();
481 surface._Loops.push_back(CRetrievableSurface::TLoop());
482 CRetrievableSurface::TLoop &loop = surface._Loops.back();
483
484 CVector loopStart = getStartVector(surface._Chains[j].Chain, i);
485 CVector currentEnd = getStopVector(surface._Chains[j].Chain, i);
486 _Chains[surface._Chains[j].Chain].setLoopIndexes(i, loopId, (uint)loop.size());
487 loop.push_back(uint16(j));
488 chainFlags[j] = true;
489
490 float loopCloseDistance;
491
492 for(;;)
493 {
494 // loopCloseDistance = hybrid2dNorm(loopStart-currentEnd);
495 loopCloseDistance = (loopStart-currentEnd).norm();
496
497 // choose the best matching start vector
498 sint bestChain = -1;
499 float best = 1.0e10f;
500 CVector thisStart;
501 for (j=0; j<chainFlags.size(); ++j)
502 {
503 if (chainFlags[j])
504 continue;
505 thisStart = getStartVector(surface._Chains[j].Chain, i);
506 // float d = hybrid2dNorm(thisStart-currentEnd);
507 float d = (thisStart-currentEnd).norm();
508 if (d < best)
509 {
510 best = d;
511 bestChain = j;
512 }
513 }
514
515 if ((bestChain == -1 || best > 4.0e-2f)&& loopCloseDistance > 4.0e-2f)
516 {
517 nlwarning("in NLPACS::CLocalRetriever::computeTips()");
518
519 dumpSurface(i);
520
521 for (j=0; j<surface._Chains.size(); ++j)
522 {
523 CVector start = getStartVector(surface._Chains[j].Chain, i);
524 CVector end = getStopVector(surface._Chains[j].Chain, i);
525 nlinfo("surf=%d chain=%d", i, surface._Chains[j].Chain);
526 nlinfo("start=(%f,%f,%f)", start.x, start.y, start.z);
527 nlinfo("end=(%f,%f,%f)", end.x, end.y, end.z);
528 }
529
530 nlwarning("bestChain=%d best=%f", bestChain, best);
531 nlwarning("loopCloseDistance=%f", loopCloseDistance);
532 nlerror("Couldn't close loop on surface=%d", i);
533 }
534 else if ((best > 1.0e0f && loopCloseDistance < 3.0e-2f) ||
535 loopCloseDistance < 1.0e-3f)
536 {
537 break;
538 }
539
540 currentEnd = getStopVector(surface._Chains[bestChain].Chain, i);
541 _Chains[surface._Chains[bestChain].Chain].setLoopIndexes(i, loopId, (uint)loop.size());
542 loop.push_back(uint16(bestChain));
543 chainFlags[bestChain] = true;
544 ++totalAdded;
545 }
546 }
547 }
548 /*
549 dumpSurface(9);
550 dumpSurface(10);
551
552 for (i=0; i<_Chains.size(); ++i)
553 {
554 if (i == 127)
555 nlinfo("");
556
557 uint whichTip;
558 // for both tips (start and stop)
559 for (whichTip=0; whichTip<=1; ++whichTip)
560 {
561 // get the tip id
562 uint thisTip = (whichTip) ? _Chains[i].getStopTip() : _Chains[i].getStartTip();
563
564 if (thisTip != 0xffff && thisTip >= _Tips.size())
565 {
566 nlwarning("in NLPACS::CLocalRetriever::computeLoopsAndTips()");
567 nlerror("checked a tip that doesn't exist on chain %d (tipId=%d)", i, thisTip);
568 }
569
570 // if it is unaffected yet creates an new tip and affect it to the common chains
571 if (thisTip == 0xffff)
572 {
573 uint turn;
574 uint tipId = _Tips.size();
575
576 if (tipId == 62)
577 nlinfo("");
578
579 _Tips.resize(tipId+1);
580 CTip &tip = _Tips[tipId];
581 tip.Point = (whichTip) ? getStopVector(i) : getStartVector(i);
582
583 for (turn=0; turn<=1; ++turn)
584 {
585 uint chain = i;
586
587 //
588 if (whichTip)
589 _Chains[chain]._StopTip = tipId;
590 else
591 _Chains[chain]._StartTip = tipId;
592
593 sint32 surf = (!turn && !whichTip || turn && whichTip) ? _Chains[chain].getLeft() : _Chains[chain].getRight();
594
595 while (surf >= 0)
596 {
597
598 CChain &nextChain = (turn) ? _Chains[chain = getNextChain(chain, surf)] : _Chains[chain = getPreviousChain(chain, surf)];
599 bool isForward = (nextChain.getLeft() == surf); // tells if the left surf is the current surf
600 bool selectTip = isForward && !turn || !isForward && turn;
601 uint16 &tipRef = selectTip ? nextChain._StopTip : nextChain._StartTip;
602 surf = (isForward) ? nextChain.getRight() : nextChain.getLeft();
603
604 if (tipRef != 0xffff && tipRef != tipId)
605 {
606 nlwarning("in NLPACS::CLocalRetriever::computeLoopsAndTips()");
607 nlerror("Trying to setup a already created tip (tipId=%d, previous=%d)", tipId, tipRef);
608 }
609 else if (tipRef != 0xffff)
610 {
611 break;
612 }
613
614 tipRef = tipId;
615 }
616 }
617 }
618 }
619 }
620
621 for (i=0; i<_Chains.size(); ++i)
622 {
623 uint startTip = _Chains[i].getStartTip(),
624 stopTip = _Chains[i].getStopTip();
625
626
627 // if (_Chains[i].getEdge() >= 0 && startTip == stopTip)
628 // {
629 // nlwarning("NLPACS::CLocalRetriever::computeLoopsAndTips(): chain %d on edge %d has same StartTip and StopTip", i, _Chains[i].getEdge(), startTip, stopTip);
630 // }
631
632
633 _Tips[startTip].Chains.push_back(CTip::CChainTip(i, true));
634 _Tips[stopTip].Chains.push_back(CTip::CChainTip(i, false));
635 }
636 */
637 for (i=0; i<_Surfaces.size(); ++i)
638 {
639 for (j=0; j<_Surfaces[i]._Loops.size(); ++j)
640 {
641 _Surfaces[i]._Loops[j].Length = 0.0f;
642 uint k;
643
644 for (k=0; k<_Surfaces[i]._Loops[j].size(); ++k)
645 _Surfaces[i]._Loops[j].Length += _Chains[_Surfaces[i]._Chains[_Surfaces[i]._Loops[j][k]].Chain].getLength();
646 }
647 }
648 }
649
650
651 //
652 void NLPACS::CLocalRetriever::buildSurfacePolygons(uint32 surface, list<CPolygon> &polygons) const
653 {
654 const CRetrievableSurface &surf = _Surfaces[surface];
655
656 uint i, j, k, l;
657
658 for (i=0; i<surf._Loops.size(); ++i)
659 {
660 polygons.push_back(CPolygon());
661 CPolygon &poly = polygons.back();
662
663 for (j=0; j<surf._Loops[i].size(); ++j)
664 {
665 const CChain &chain = _Chains[surf._Loops[i][j]];
666 bool chainforward = ((uint32)chain._Left == surface);
667
668 if (chainforward)
669 {
670 for (k=0; k<chain._SubChains.size(); ++k)
671 {
672 const COrderedChain &ochain = _OrderedChains[chain._SubChains[k]];
673 bool ochainforward = ochain.isForward();
674
675 if (ochainforward)
676 {
677 for (l=0; l<ochain.getVertices().size()-1; ++l)
678 poly.Vertices.push_back(ochain[l].unpack3f());
679 }
680 else
681 {
682 for (l=(uint)ochain.getVertices().size()-1; l>0; --l)
683 poly.Vertices.push_back(ochain[l].unpack3f());
684 }
685 }
686 }
687 else
688 {
689 for (k=(uint)chain._SubChains.size(); (sint)k>0; --k)
690 {
691 const COrderedChain &ochain = _OrderedChains[chain._SubChains[k]];
692 bool ochainforward = ochain.isForward();
693
694 if (ochainforward)
695 {
696 for (l=(uint)ochain.getVertices().size()-1; (sint)l>0; --l)
697 poly.Vertices.push_back(ochain[l].unpack3f());
698 }
699 else
700 {
701 for (l=0; l<ochain.getVertices().size()-1; ++l)
702 poly.Vertices.push_back(ochain[l].unpack3f());
703 }
704 }
705 }
706 }
707 }
708 }
709
710 //
711 void NLPACS::CLocalRetriever::build3dSurfacePolygons(uint32 surface, list<CPolygon> &polygons) const
712 {
713 const CRetrievableSurface &surf = _Surfaces[surface];
714
715 uint i, j, k, l;
716
717 for (i=0; i<surf._Loops.size(); ++i)
718 {
719 polygons.push_back(CPolygon());
720 CPolygon &poly = polygons.back();
721
722 for (j=0; j<surf._Loops[i].size(); ++j)
723 {
724 const CRetrievableSurface::TLoop &loop = surf._Loops[i];
725 const CChain &chain = _Chains[surf._Chains[loop[j]].Chain];
726 bool chainforward = ((uint32)chain._Left == surface);
727
728 if (chainforward)
729 {
730 for (k=0; k<chain._SubChains.size(); ++k)
731 {
732 const COrderedChain3f &ochain = _FullOrderedChains[chain._SubChains[k]];
733 bool ochainforward = ochain.isForward();
734
735 if (ochainforward)
736 {
737 for (l=0; l<ochain.getVertices().size()-1; ++l)
738 poly.Vertices.push_back(ochain[l]);
739 }
740 else
741 {
742 for (l=(uint)ochain.getVertices().size()-1; l>0; --l)
743 poly.Vertices.push_back(ochain[l]);
744 }
745 }
746 }
747 else
748 {
749 for (k=(uint)chain._SubChains.size()-1; (sint)k>=0; --k)
750 {
751 const COrderedChain3f &ochain = _FullOrderedChains[chain._SubChains[k]];
752 bool ochainforward = ochain.isForward();
753
754 if (ochainforward)
755 {
756 for (l=(uint)ochain.getVertices().size()-1; (sint)l>0; --l)
757 poly.Vertices.push_back(ochain[l]);
758 }
759 else
760 {
761 for (l=0; l<ochain.getVertices().size()-1; ++l)
762 poly.Vertices.push_back(ochain[l]);
763 }
764 }
765 }
766 }
767 }
768 }
769
770
771 // not implemented...
772 void NLPACS::CLocalRetriever::sortTips()
773 {
774 }
775
776
777
778
779 void NLPACS::CLocalRetriever::findBorderChains()
780 {
781 uint chain;
782
783 // for each chain, if it belongs to an edge of the
784 // local retriever, then adds it to the _BorderChains.
785 for (chain=0; chain<_Chains.size(); ++chain)
786 if (_Chains[chain].isBorderChain())
787 {
788 sint32 index = (sint32)_BorderChains.size();
789 _BorderChains.push_back(uint16(chain));
790 _Chains[chain].setBorderChainIndex(index);
791 }
792 }
793
794 void NLPACS::CLocalRetriever::updateChainIds()
795 {
796 uint surf, link;
797
798 for (surf=0; surf<_Surfaces.size(); ++surf)
799 {
800 CRetrievableSurface &surface = _Surfaces[surf];
801
802 for (link=0; link<surface._Chains.size(); ++link)
803 {
804 sint32 chain = surface._Chains[link].Chain;
805
806 if (_Chains[chain]._Left == (sint32)surf)
807 surface._Chains[link].Surface = _Chains[chain]._Right;
808 else if (_Chains[chain]._Right == (sint32)surf)
809 surface._Chains[link].Surface = _Chains[chain]._Left;
810 else
811 {
812 nlwarning("in NLPACS::CLocalRetriever::updateEdgesOnSurfaces()");
813 nlerror("Can't find back point to surface %d on chain %d", surf, chain);
814 }
815 }
816 }
817 }
818
819 void NLPACS::CLocalRetriever::computeTopologies()
820 {
821 //nlinfo("compute topologies");
822
823 // Find topologies out...
824 uint character;
825 for (character=0; character<NumCreatureModels; ++character)
826 {
827 // for each type of creature, flood fill surfaces...
828 sint32 surface;
829 uint topology = 0;
830
831 for (surface=0; surface<(sint)_Surfaces.size(); ++surface)
832 {
833 if (_Surfaces[surface]._Topologies[character] == -1 &&
834 _Surfaces[surface]._Character == character)
835 {
836 vector<sint32> surfacesStack;
837 surfacesStack.push_back(surface);
838
839 while (!surfacesStack.empty())
840 {
841 CRetrievableSurface &current = _Surfaces[surfacesStack.back()];
842 surfacesStack.pop_back();
843 current._Topologies[character] = topology;
844
845 uint i;
846 for (i=0; i<current._Chains.size(); ++i)
847 {
848 CChain &chain = _Chains[current._Chains[i].Chain];
849 sint32 link = (chain.getLeft() == surface) ? chain.getRight() : chain.getLeft();
850 if (link>=0 && link<(sint)_Surfaces.size() &&
851 _Surfaces[link]._Topologies[character] == -1 &&
852 _Surfaces[link]._Character >= character)
853 {
854 surfacesStack.push_back(link);
855 _Surfaces[link]._Topologies[character] = topology;
856 }
857 }
858 }
859
860 ++topology;
861 }
862 }
863
864 _Topologies[character].resize(topology);
865 //nlinfo("generated %d topologies for character %d", topology, character);
866 }
867
868 uint surface;
869 for (surface=0; surface<_Surfaces.size(); ++surface)
870 {
871 CRetrievableSurface &current = _Surfaces[surface];
872
873 for (character=0; character<NumCreatureModels; ++character)
874 if (current._Topologies[character] >= 0)
875 _Topologies[character][current._Topologies[character]].push_back(surface);
876 }
877 }
878
879 void NLPACS::CLocalRetriever::translate(const NLMISC::CVector &translation)
880 {
881 uint i;
882 for (i=0; i<_OrderedChains.size(); ++i)
883 _OrderedChains[i].translate(translation);
884 for (i=0; i<_Surfaces.size(); ++i)
885 _Surfaces[i].translate(translation);
886 /*
887 for (i=0; i<_Tips.size(); ++i)
888 _Tips[i].translate(translation);
889 */
890 }
891
892 void NLPACS::CLocalRetriever::serial(NLMISC::IStream &f)
893 {
894 /*
895 Version 0:
896 - base version (with collision info).
897 Version 1:
898 - interior vertices and faces, for interior ground snapping
899 Version 2:
900 - face grid added.
901 Version 3:
902 - identifier added.
903 Version 4:
904 - topologies no more in stream (obsolete)
905 */
906 sint ver= f.serialVersion(4);
907
908 if (ver < 4)
909 throw EOlderStream();
910
911 uint i;
912 f.serialCont(_Chains);
913 f.serialCont(_OrderedChains);
914 f.serialCont(_FullOrderedChains);
915 f.serialCont(_Surfaces);
916 f.serialCont(__Tips);
917 f.serialCont(_BorderChains);
918 if (ver < 4)
919 {
920 for (i=0; i<NumMaxCreatureModels; ++i)
921 f.serialCont(_Topologies[i]);
922 }
923 f.serial(_ChainQuad);
924 f.serial(_BBox);
925 f.serialEnum(_Type);
926 f.serial(_ExteriorMesh);
927
928 // a fix for old versions (with wrong _Type value)
929 if (_Type != CLocalRetriever::Interior) _Type = CLocalRetriever::Landscape;
930
931 if (ver >= 1)
932 {
933 f.serialCont(_InteriorVertices);
934 f.serialCont(_InteriorFaces);
935
936 }
937 if (ver >= 2)
938 {
939 f.serial(_FaceGrid);
940 }
941 if (ver >= 3)
942 {
943 f.serial(_Id);
944 }
945
946 _Loaded = true;
947 LoadCheckFlag = false;
948 }
949
950
951
952
953
954
955
956
957 bool NLPACS::CLocalRetriever::insurePosition(NLPACS::ULocalPosition &local) const
958 {
959 if (!_Loaded)
960 return false;
961
962 if (local.Surface < 0 || local.Surface >= (sint)_Surfaces.size())
963 {
964 nlwarning("PACS: can't insure position to inexistant surface %d", local.Surface);
965 return false;
966 }
967
968 // the surface
969 const NLPACS::CRetrievableSurface &surface = _Surfaces[local.Surface];
970
971 uint i, j, k;
972 CVector2f M = CVector2f(local.Estimation);
973 bool moved = false;
974
975 // for each chain and each subchain of the surface,
976 // check if point is located on the good side of the border (and far enough to avoid accuracy issues)
977 for (i=0; i<surface.getChains().size(); ++i)
978 {
979 uint ichain = surface.getChain(i).Chain;
980 const NLPACS::CChain &chain = _Chains[ichain];
981
982 for (j=0; j<chain.getSubChains().size(); ++j)
983 {
984 uint iochain = chain.getSubChain(j);
985 const NLPACS::COrderedChain &ochain = _OrderedChains[iochain];
986
987 uint isAtLeft = ((chain.getLeft() == local.Surface) ? 1 : 0);
988 uint isForward = (ochain.isForward() ? 1 : 0);
989 bool shouldBeUpper = !((isAtLeft ^ isForward) != 0); // shouldBeAtLeft for vertical segment
990
991 for (k=0; (sint)k<(sint)(ochain.getVertices().size()-1); ++k)
992 {
993 CVector2f A = ochain[k].unpack();
994 CVector2f B = ochain[k+1].unpack();
995 CVector2f AB = B-A;
996
997 float lambda = ((M-A)*AB)/AB.sqrnorm();
998
999 if (lambda<0.0f || lambda>1.0f)
1000 continue;
1001
1002 CVector2f n = (shouldBeUpper ? CVector2f(-AB.y, AB.x) : CVector2f(AB.y, -AB.x)).normed();
1003 float d = (M-A)*n;
1004
1005 // if point is too close of the border or on the wrong side
1006 // move it far enough
1007 if (d < InsurePositionThreshold && d > -InsurePositionThreshold)
1008 {
1009 M += (InsurePositionThreshold*1.1f-d)*n;
1010 moved = true;
1011 }
1012 }
1013 }
1014 }
1015
1016 NLPACS::CRetrieverInstance::snapVector(M);
1017
1018 local.Estimation.x = M.x;
1019 local.Estimation.y = M.y;
1020
1021 {
1022 float fx1024 = local.Estimation.x * 1024.0f;
1023 float fy1024 = local.Estimation.x * 1024.0f;
1024 sint32 ix1024 = (sint32)floor(fx1024);
1025 sint32 iy1024 = (sint32)floor(fy1024);
1026
1027 nlassert ((float)ix1024 == fx1024);
1028 nlassert ((float)iy1024 == fy1024);
1029 }
1030
1031 return moved;
1032 }
1033
1034
1035 bool NLPACS::CLocalRetriever::testPosition(NLPACS::ULocalPosition &local, CCollisionSurfaceTemp &cst) const
1036 {
1037 if (!_Loaded)
1038 return false;
1039
1040 if (local.Surface < 0 || local.Surface >= (sint)_Surfaces.size())
1041 {
1042 nlwarning("PACS: can't test inexistant surface %d", local.Surface);
1043 return false;
1044 }
1045
1046 if (fabs(local.Estimation.x) >= 256.0 || fabs(local.Estimation.y) >= 256.0)
1047 return false;
1048
1049 retrievePosition(local.Estimation, cst);
1050
1051 bool result = (cst.SurfaceLUT[local.Surface].Counter == 2 || cst.SurfaceLUT[local.Surface].OnVerticalEdge);
1052
1053 uint i;
1054 for (i=0; i<cst.PossibleSurfaces.size(); ++i)
1055 cst.SurfaceLUT[cst.PossibleSurfaces[i]].reset();
1056
1057 return result;
1058 }
1059
1060
1061 void NLPACS::CLocalRetriever::retrievePosition(CVector estimated, CCollisionSurfaceTemp &cst) const
1062 {
1063 if (!_Loaded)
1064 return;
1065
1066 CAABBox box;
1067 const double BorderThreshold = 2.0e-2f;
1068 box.setMinMax(CVector(estimated.x-(float)BorderThreshold, _BBox.getMin().y, 0.0f), CVector(estimated.x+(float)BorderThreshold, _BBox.getMax().y, 0.0f));
1069 uint numEdges = _ChainQuad.selectEdges(box, cst);
1070
1071 uint ochain, i;
1072 CVector2s estim = CVector2s(estimated);
1073
1074 cst.PossibleSurfaces.clear();
1075
1076 // WARNING!!
1077 // cst.SurfaceLUT is assumed to be 0 filled !!
1078
1079 //nldebug("estim=(%d,%d)", estim.x, estim.y);
1080
1081 // for each ordered chain, checks if the estimated position is between the min and max.
1082 for (i=0; i<numEdges; ++i)
1083 {
1084 ochain = cst.EdgeChainEntries[i].OChainId;
1085
1086 const COrderedChain &sub = _OrderedChains[ochain];
1087 const CVector2s &min = sub.getMin(),
1088 &max = sub.getMax();
1089
1090 // checks the position against the min and max of the chain
1091 if (estim.x < min.x || estim.x > max.x)
1092 continue;
1093
1094 bool isUpper;
1095 bool isOnBorder = false;
1096
1097 sint32 left = _Chains[sub.getParentId()].getLeft(),
1098 right = _Chains[sub.getParentId()].getRight();
1099
1100 if (estim.y < min.y)
1101 {
1102 if (estim.x == max.x)
1103 continue;
1104 isUpper = false;
1105 // nlinfo("Box: min(%d,%d) max(%d,%d) forward=%d left=%d right=%d upper=false", min.x, min.y, max.x, max.y, sub.isForward(), left, right);
1106 }
1107 else if (estim.y > max.y)
1108 {
1109 if (estim.x == max.x)
1110 continue;
1111 isUpper = true;
1112 // nlinfo("Box: min(%d,%d) max(%d,%d) forward=%d left=%d right=%d upper=true", min.x, min.y, max.x, max.y, sub.isForward(), left, right);
1113 }
1114 else
1115 {
1116 const vector<CVector2s> &vertices = sub.getVertices();
1117 uint start = 0, stop = (uint)vertices.size()-1;
1118
1119 // then finds the smallest segment of the chain that includes the estimated position.
1120 while (stop-start > 1)
1121 {
1122 uint mid = (start+stop)/2;
1123
1124 if (vertices[mid].x > estim.x)
1125 stop = mid;
1126 else
1127 start = mid;
1128 }
1129
1130 // if a vertical edge
1131 if (vertices[start].x == vertices[stop].x)
1132 {
1133 // look for maximal bounds
1134 while (start > 0 && vertices[start].x == vertices[start-1].x)
1135 --start;
1136
1137 while (stop < vertices.size()-1 && vertices[stop].x == vertices[stop+1].x)
1138 ++stop;
1139
1140 // if upper or lower the bounds, do nothing
1141 if ((estim.y > vertices[start].y && estim.y > vertices[stop].y) ||
1142 (estim.y < vertices[start].y && estim.y < vertices[stop].y))
1143 continue;
1144
1145 isOnBorder = true;
1146 if (left >= 0)
1147 {
1148 cst.SurfaceLUT[left].FoundCloseEdge = true;
1149 cst.SurfaceLUT[left].OnVerticalEdge = true;
1150 }
1151 if (right >= 0)
1152 {
1153 cst.SurfaceLUT[right].FoundCloseEdge = true;
1154 cst.SurfaceLUT[right].OnVerticalEdge = true;
1155 }
1156 // nlinfo("Edge: start(%d,%d) stop(%d,%d) forward=%d left=%d right=%d border=true", vertices[start].x, vertices[start].y, vertices[stop].x, vertices[stop].y, sub.isForward(), left, right);
1157 continue;
1158 }
1159 else if (vertices[stop].x == estim.x)
1160 {
1161 // if (yes)
1162 continue;
1163 }
1164
1165 // and then checks if the estimated position is up or down the chain.
1166
1167 // first trivial case (up both tips)
1168 if (estim.y > vertices[start].y && estim.y > vertices[stop].y)
1169 {
1170 isUpper = true;
1171 // nlinfo("Edge: start(%d,%d) stop(%d,%d) forward=%d left=%d right=%d upper=true", vertices[start].x, vertices[start].y, vertices[stop].x, vertices[stop].y, sub.isForward(), left, right);
1172 }
1173 // second trivial case (down both tips)
1174 else if (estim.y < vertices[start].y && estim.y < vertices[stop].y)
1175 {
1176 isUpper = false;
1177 // nlinfo("Edge: start(%d,%d) stop(%d,%d) forward=%d left=%d right=%d upper=false", vertices[start].x, vertices[start].y, vertices[stop].x, vertices[stop].y, sub.isForward(), left, right);
1178 }
1179 // full test...
1180 else
1181 {
1182 const CVector2s &vstart = vertices[start],
1183 &vstop = vertices[stop];
1184
1185 sint16 intersect = vstart.y + (vstop.y-vstart.y)*(estim.x-vstart.x)/(vstop.x-vstart.x);
1186
1187 isUpper = estim.y > intersect;
1188 //isOnBorder = (fabs(estim.y - intersect)<BorderThreshold*Vector2sAccuracy);
1189 isOnBorder = (fabs((double)(estim.y - intersect))<(double)(BorderThreshold*Vector2sAccuracy));
1190 // nlinfo("Edge: start(%d,%d) stop(%d,%d) forward=%d left=%d right=%d upper=%s border=%s", vertices[start].x, vertices[start].y, vertices[stop].x, vertices[stop].y, sub.isForward(), left, right, isUpper ? "true":"false", isOnBorder ? "true":"false");
1191 }
1192 }
1193
1194 if (isOnBorder)
1195 {
1196 cst.incSurface(left);
1197 cst.incSurface(right);
1198 if (left >= 0) cst.SurfaceLUT[left].FoundCloseEdge = true;
1199 if (right >= 0) cst.SurfaceLUT[right].FoundCloseEdge = true;
1200 continue;
1201 }
1202
1203 // Depending on the chain is forward, up the position, increase/decrease the surface table...
1204 if (sub.isForward())
1205 {
1206 if (isUpper)
1207 {
1208 cst.incSurface(left);
1209 cst.decSurface(right);
1210 }
1211 else
1212 {
1213 cst.decSurface(left);
1214 cst.incSurface(right);
1215 }
1216 }
1217 else
1218 {
1219 if (isUpper)
1220 {
1221 cst.decSurface(left);
1222 cst.incSurface(right);
1223 }
1224 else
1225 {
1226 cst.incSurface(left);
1227 cst.decSurface(right);
1228 }
1229 }
1230 }
1231 }
1232
1233
1234 void NLPACS::CLocalRetriever::retrieveAccuratePosition(CVector2s estim, CCollisionSurfaceTemp &cst, bool &onBorder) const
1235 {
1236 if (!_Loaded)
1237 return;
1238
1239 CAABBox box;
1240 CVector estimated = estim.unpack3f();
1241 const double BorderThreshold = 2.0e-2f;
1242 box.setMinMax(CVector(estimated.x-(float)BorderThreshold, _BBox.getMin().y, 0.0f),
1243 CVector(estimated.x+(float)BorderThreshold, _BBox.getMax().y, 0.0f));
1244 uint numEdges = _ChainQuad.selectEdges(box, cst);
1245
1246 uint ochain, i;
1247
1248 onBorder = false;
1249
1250 cst.PossibleSurfaces.clear();
1251
1252 // WARNING!!
1253 // cst.SurfaceLUT is assumed to be 0 filled !!
1254
1255 //nldebug("estim=(%d,%d)", estim.x, estim.y);
1256
1257 // for each ordered chain, checks if the estimated position is between the min and max.
1258 for (i=0; i<numEdges; ++i)
1259 {
1260 ochain = cst.EdgeChainEntries[i].OChainId;
1261
1262 const COrderedChain &sub = _OrderedChains[ochain];
1263 const CVector2s &min = sub.getMin(),
1264 &max = sub.getMax();
1265
1266 // checks the position against the min and max of the chain
1267 if (estim.x < min.x || estim.x > max.x)
1268 continue;
1269
1270 bool isUpper;
1271 //bool isOnBorder = false;
1272
1273 sint32 left = _Chains[sub.getParentId()].getLeft(),
1274 right = _Chains[sub.getParentId()].getRight();
1275
1276 if (estim.y < min.y)
1277 {
1278 if (estim.x == max.x)
1279 continue;
1280 isUpper = false;
1281 }
1282 else if (estim.y > max.y)
1283 {
1284 if (estim.x == max.x)
1285 continue;
1286 isUpper = true;
1287 }
1288 else
1289 {
1290 const vector<CVector2s> &vertices = sub.getVertices();
1291 uint start = 0, stop = (uint)vertices.size()-1;
1292
1293 // then finds the smallest segment of the chain that includes the estimated position.
1294 while (stop-start > 1)
1295 {
1296 uint mid = (start+stop)/2;
1297
1298 if (vertices[mid].x > estim.x)
1299 stop = mid;
1300 else
1301 start = mid;
1302 }
1303
1304 // if a vertical edge
1305 if (vertices[start].x == vertices[stop].x)
1306 {
1307 // look for maximal bounds
1308 while (start > 0 && vertices[start].x == vertices[start-1].x)
1309 --start;
1310
1311 while (stop < vertices.size()-1 && vertices[stop].x == vertices[stop+1].x)
1312 ++stop;
1313
1314 // if upper or lower the bounds, do nothing
1315 if ((estim.y > vertices[start].y && estim.y > vertices[stop].y) ||
1316 (estim.y < vertices[start].y && estim.y < vertices[stop].y))
1317 continue;
1318
1319 onBorder = true;
1320 continue;
1321 }
1322 else if (vertices[stop].x == estim.x)
1323 {
1324 // if (yes)
1325 continue;
1326 }
1327
1328 // and then checks if the estimated position is up or down the chain.
1329
1330 // first trivial case (up both tips)
1331 if (estim.y > vertices[start].y && estim.y > vertices[stop].y)
1332 {
1333 isUpper = true;
1334 }
1335 // second trivial case (down both tips)
1336 else if (estim.y < vertices[start].y && estim.y < vertices[stop].y)
1337 {
1338 isUpper = false;
1339 }
1340 // full test...
1341 else
1342 {
1343 const CVector2s &vstart = vertices[start],
1344 &vstop = vertices[stop];
1345
1346 // this test is somewhat more accurate
1347 // no division performed
1348 sint32 det = (estim.y-vstart.y)*(vstop.x-vstart.x) - (estim.x-vstart.x)*(vstop.y-vstart.y);
1349
1350 isUpper = (det > 0);
1351
1352 if (det == 0)
1353 onBorder = true;
1354 }
1355 }
1356
1357 // Depending on the chain is forward, up the position, increase/decrease the surface table...
1358 if (sub.isForward())
1359 {
1360 if (isUpper)
1361 {
1362 cst.incSurface(left);
1363 cst.decSurface(right);
1364 }
1365 else
1366 {
1367 cst.decSurface(left);
1368 cst.incSurface(right);
1369 }
1370 }
1371 else
1372 {
1373 if (isUpper)
1374 {
1375 cst.decSurface(left);
1376 cst.incSurface(right);
1377 }
1378 else
1379 {
1380 cst.incSurface(left);
1381 cst.decSurface(right);
1382 }
1383 }
1384 }
1385 }
1386
1387
1388
1389 void NLPACS::CLocalRetriever::initFaceGrid()
1390 {
1391 CFaceGrid::CFaceGridBuild fgb;
1392 fgb.init(64, 4.0f);
1393
1394 uint i;
1395 for (i=0; i<_InteriorFaces.size(); ++i)
1396 {
1397 CAABBox box;
1398 CInteriorFace &f = _InteriorFaces[i];
1399 box.setCenter(_InteriorVertices[f.Verts[0]]);
1400 box.extend(_InteriorVertices[f.Verts[1]]);
1401 box.extend(_InteriorVertices[f.Verts[2]]);
1402
1403 fgb.insert(box.getMin(), box.getMax(), i);
1404 }
1405
1406 _FaceGrid.create(fgb);
1407 }
1408
1409 void NLPACS::CLocalRetriever::snapToInteriorGround(NLPACS::ULocalPosition &position, bool &snapped) const
1410 {
1411 if (!_Loaded)
1412 return;
1413
1414 // first preselect faces around the (x, y) position (CQuadGrid ?)
1415 vector<uint32> selection;
1416 _FaceGrid.select(position.Estimation, selection);
1417
1418 // from the preselect faces, look for the only face that belongs to the surface
1419 // and that contains the position
1420 CVector pos = position.Estimation;
1421 CVector posh = pos+CVector(0.0f, 0.0f, 1.0f);
1422 CVector2f pos2d = position.Estimation;
1423 float bestDist = 1.0e10f;
1424 CVector best(0.0f, 0.0f, 0.0f);
1425 vector<uint32>::iterator it;
1426 snapped = false;
1427 for (it=selection.begin(); it!=selection.end(); ++it)
1428 {
1429 const CInteriorFace &f = _InteriorFaces[*it];
1430 if (f.Surface == (uint32)position.Surface)
1431 {
1432 CVector v[3];
1433 v[0] = _InteriorVertices[f.Verts[0]];
1434 v[1] = _InteriorVertices[f.Verts[1]];
1435 v[2] = _InteriorVertices[f.Verts[2]];
1436
1437 CVector2f n;
1438 float c; // 2D cartesian coefficients of line in plane X/Y.
1439 // Line p0-p1.
1440 n = CVector2f(-(v[1].y-v[0].y), (v[1].x-v[0].x)).normed();
1441 c = -(v[0].x*n.x + v[0].y*n.y);
1442 if (n*pos2d + c < -1.0f/Vector2sAccuracy) continue;
1443 // Line p1-p2.
1444 n = CVector2f(-(v[2].y-v[1].y), (v[2].x-v[1].x)).normed();
1445 c = -(v[1].x*n.x + v[1].y*n.y);
1446 if (n*pos2d + c < -1.0f/Vector2sAccuracy) continue;
1447 // Line p2-p0.
1448 n = CVector2f(-(v[0].y-v[2].y), (v[0].x-v[2].x)).normed();
1449 c = -(v[2].x*n.x + v[2].y*n.y);
1450 if (n*pos2d + c < -1.0f/Vector2sAccuracy) continue;
1451
1452 CPlane p;
1453 p.make(v[0], v[1], v[2]);
1454
1455 CVector i = p.intersect(pos, posh);
1456
1457 float d = (float)fabs(pos.z-i.z);
1458
1459 if (d < bestDist)
1460 {
1461 bestDist = d;
1462 best = i;
1463 }
1464 }
1465 }
1466
1467 // and computes the real position on this face
1468 if (bestDist < 400.0f)
1469 {
1470 snapped = true;
1471 position.Estimation = best;
1472 }
1473 }
1474
1475 // ***************************************************************************
1476 float NLPACS::CLocalRetriever::getHeight(const NLPACS::ULocalPosition &position) const
1477 {
1478 if (!_Loaded)
1479 return 0.0f;
1480
1481 if (_Type == Interior)
1482 {
1483 // first preselect faces around the (x, y) position (CQuadGrid ?)
1484 vector<uint32> selection;
1485 _FaceGrid.select(position.Estimation, selection);
1486
1487 // from the preselect faces, look for the only face that belongs to the surface
1488 // and that contains the position
1489 CVector pos = position.Estimation;
1490 CVector posh = pos+CVector(0.0f, 0.0f, 1.0f);
1491 float bestDist = 1.0e10f;
1492 CVector best(0.0f, 0.0f, 0.0f);
1493 vector<uint32>::iterator it;
1494 for (it=selection.begin(); it!=selection.end(); ++it)
1495 {
1496 const CInteriorFace &f = _InteriorFaces[*it];
1497 if (f.Surface == (uint32)position.Surface)
1498 {
1499 CVector v[3];
1500 v[0] = _InteriorVertices[f.Verts[0]];
1501 v[1] = _InteriorVertices[f.Verts[1]];
1502 v[2] = _InteriorVertices[f.Verts[2]];
1503
1504 float a,b,c; // 2D cartesian coefficients of line in plane X/Y.
1505 // Line p0-p1.
1506 a = -(v[1].y-v[0].y);
1507 b = (v[1].x-v[0].x);
1508 c = -(v[0].x*a + v[0].y*b);
1509 if (a*pos.x + b*pos.y + c < 0) continue;
1510 // Line p1-p2.
1511 a = -(v[2].y-v[1].y);
1512 b = (v[2].x-v[1].x);
1513 c = -(v[1].x*a + v[1].y*b);
1514 if (a*pos.x + b*pos.y + c < 0) continue;
1515 // Line p2-p0.
1516 a = -(v[0].y-v[2].y);
1517 b = (v[0].x-v[2].x);
1518 c = -(v[2].x*a + v[2].y*b);
1519 if (a*pos.x + b*pos.y + c < 0) continue;
1520
1521 CPlane p;
1522 p.make(v[0], v[1], v[2]);
1523
1524 CVector i = p.intersect(pos, posh);
1525
1526 float d = (float)fabs(pos.z-i.z);
1527
1528 if (d < bestDist)
1529 {
1530 bestDist = d;
1531 best = i;
1532 }
1533 }
1534 }
1535
1536 // and computes the real position on this face
1537 return (bestDist < 200.0f) ? best.z : position.Estimation.z;
1538 }
1539 else
1540 {
1541 if (_Surfaces[position.Surface].getQuadTree().getRoot() != NULL)
1542 {
1543 // find quad leaf.
1544 const CQuadLeaf *leaf = _Surfaces[position.Surface].getQuadTree().getLeaf(position.Estimation);
1545
1546 // if there is no acceptable leaf, just give up
1547 if (leaf == NULL)
1548 {
1549 //nlinfo("COL: quadtree: don't find the quadLeaf!");
1550 return position.Estimation.z;
1551 }
1552 else
1553 {
1554 // else return mean height.
1555 float meanHeight = (leaf->getMinHeight()+leaf->getMaxHeight())*0.5f;
1556 return meanHeight;
1557 }
1558 }
1559 else if (_Surfaces[position.Surface].isUnderWater())
1560 {
1561 return _Surfaces[position.Surface].getWaterHeight();
1562 }
1563 else
1564 {
1565 sint8 qh = _Surfaces[position.Surface].getQuantHeight();
1566 return qh*2.0f + 1.0f;
1567 }
1568 }
1569 }
1570
1571
1572 // ***************************************************************************
1573 float NLPACS::CLocalRetriever::getInteriorHeightAround(const ULocalPosition &position, float outsideTolerance) const
1574 {
1575 if (!_Loaded)
1576 return 0.0f;
1577
1578 if (_Type == Interior)
1579 {
1580 // first preselect faces around the (x, y) position (CQuadGrid ?)
1581 vector<uint32> selection;
1582 _FaceGrid.select(position.Estimation, selection);
1583
1584 // from the preselect faces, look for the only face that belongs to the surface
1585 // and that contains the position
1586 CVector pos = position.Estimation;
1587 CVector posh = pos+CVector(0.0f, 0.0f, 1.0f);
1588 float bestDist = 1.0e10f;
1589 CVector best(0.0f, 0.0f, 0.0f);
1590 vector<uint32>::iterator it;
1591 for (it=selection.begin(); it!=selection.end(); ++it)
1592 {
1593 const CInteriorFace &f = _InteriorFaces[*it];
1594 if (f.Surface == (uint32)position.Surface)
1595 {
1596 CVector v[3];
1597 v[0] = _InteriorVertices[f.Verts[0]];
1598 v[1] = _InteriorVertices[f.Verts[1]];
1599 v[2] = _InteriorVertices[f.Verts[2]];
1600
1601 // Test if out of this triangle (+ tolerance)
1602 float a,b; // 2D cartesian coefficients of line in plane X/Y.
1603 float len;
1604 // Line p0-p1.
1605 a = -(v[1].y-v[0].y);
1606 b = (v[1].x-v[0].x);
1607 len= sqrtf(a*a+b*b); // norm of the normal vector
1608 if (a*(pos.x-v[0].x) + b*(pos.y-v[0].y) < -len*outsideTolerance) continue;
1609 // Line p1-p2.
1610 a = -(v[2].y-v[1].y);
1611 b = (v[2].x-v[1].x);
1612 len= sqrtf(a*a+b*b); // norm of the normal vector
1613 if (a*(pos.x-v[1].x) + b*(pos.y-v[1].y) < -len*outsideTolerance) continue;
1614 // Line p2-p0.
1615 a = -(v[0].y-v[2].y);
1616 b = (v[0].x-v[2].x);
1617 len= sqrtf(a*a+b*b); // norm of the normal vector
1618 if (a*(pos.x-v[2].x) + b*(pos.y-v[2].y) < -len*outsideTolerance) continue;
1619
1620
1621 // Ok IN => compute z and keep nearest to wanted one
1622 CPlane p;
1623 p.make(v[0], v[1], v[2]);
1624
1625 CVector i = p.intersect(pos, posh);
1626
1627 float d = (float)fabs(pos.z-i.z);
1628
1629 if (d < bestDist)
1630 {
1631 bestDist = d;
1632 best = i;
1633 }
1634 }
1635 }
1636
1637 // and computes the real position on this face
1638 return (bestDist < 200.0f) ? best.z : position.Estimation.z;
1639 }
1640
1641 return 0.f;
1642 }
1643
1644
1645 // ***************************************************************************
1646 #ifdef NL_OS_WINDOWS
1647 //#pragma optimize( "", off )
1648 #endif // NL_OS_WINDOWS
1649
1650 void NLPACS::CLocalRetriever::findPath(const NLPACS::CLocalRetriever::CLocalPosition &A,
1651 const NLPACS::CLocalRetriever::CLocalPosition &B,
1652 std::vector<NLPACS::CVector2s> &path,
1653 NLPACS::CCollisionSurfaceTemp &cst) const
1654 {
1655 if (A.Surface != B.Surface)
1656 {
1657 nlwarning("in NLPACS::CLocalRetriever::findPath()");
1658 nlerror("Try to find a path between 2 points that are not in the same surface (A=%d, B=%d)", A.Surface, B.Surface);
1659 }
1660
1661 CVector a = A.Estimation,
1662 b = B.Estimation,
1663 n = CVector(a.y-b.y, b.x-a.x, 0.0f);
1664
1665 _ChainQuad.selectEdges(a, b, cst);
1666
1667 vector<CIntersectionMarker> intersections;
1668
1669 uint i, j;
1670 sint32 surfaceId = A.Surface;
1671 const CRetrievableSurface &surface = _Surfaces[surfaceId];
1672
1673 for (i=0; i<cst.EdgeChainEntries.size(); ++i)
1674 {
1675 CEdgeChainEntry &entry = cst.EdgeChainEntries[i];
1676 const COrderedChain &chain = _OrderedChains[entry.OChainId];
1677
1678 if (_Chains[chain.getParentId()].getLeft() != surfaceId &&
1679 _Chains[chain.getParentId()].getRight() != surfaceId)
1680 continue;
1681
1682 for (j=entry.EdgeStart; j<entry.EdgeEnd; ++j)
1683 {
1684 // here the edge collision test
1685
1686 CVector p0 = chain[j].unpack3f(),
1687 p1 = chain[j+1].unpack3f();
1688
1689 float vp0 = (p0-a)*n,
1690 vp1 = (p1-a)*n;
1691
1692 if (vp0*vp1 <= 0.0f)
1693 {
1694 CVector np = CVector(p0.y-p1.y, p1.x-p0.x, 0.0f);
1695
1696 float va = (a-p0)*np,
1697 vb = (b-p0)*np;
1698
1699 // here we have an intersection
1700 if (va*vb <= 0.0f)
1701 {
1702 const CChain &parent = _Chains[chain.getParentId()];
1703 bool isIn = (va-vb < 0.0f) ^ (parent.getLeft() == surfaceId) ^ chain.isForward();
1704
1705 intersections.push_back(CIntersectionMarker(va/(va-vb), entry.OChainId, uint16(j), isIn));
1706 }
1707 }
1708 }
1709 }
1710
1711 sort(intersections.begin(), intersections.end());
1712
1713 uint intersStart = 0;
1714 uint intersEnd = (uint)intersections.size();
1715
1716 if (intersEnd > 0)
1717 {
1718 while (intersStart < intersections.size() &&
1719 intersections[intersStart].In && intersections[intersStart].Position < 1.0e-4f)
1720 ++intersStart;
1721
1722 while (intersStart < intersEnd &&
1723 !intersections[intersEnd-1].In && intersections[intersEnd-1].Position > 1.0f-1.0e-4f)
1724 --intersEnd;
1725
1726 // Check intersections have a valid order
1727 if ((intersEnd-intersStart) & 1)
1728 {
1729 nlwarning("in NLPACS::CLocalRetriever::findPath()");
1730 nlerror("Found an odd (%d) number of intersections", intersections.size());
1731 }
1732
1733 for (i=intersStart; i<intersEnd; )
1734 {
1735 uint exitLoop, enterLoop;
1736
1737 const CChain &exitChain = _Chains[_OrderedChains[intersections[i].OChain].getParentId()];
1738 exitLoop = (exitChain.getLeft() == surfaceId) ? exitChain.getLeftLoop() : exitChain.getRightLoop();
1739
1740 if (intersections[i++].In)
1741 {
1742 nlwarning("in NLPACS::CLocalRetriever::findPath()");
1743 nlerror("Entered the surface before exited", intersections.size());
1744 }
1745
1746 const CChain &enterChain = _Chains[_OrderedChains[intersections[i].OChain].getParentId()];
1747 enterLoop = (enterChain.getLeft() == surfaceId) ? enterChain.getLeftLoop() : enterChain.getRightLoop();
1748
1749 if (!intersections[i++].In)
1750 {
1751 nlwarning("in NLPACS::CLocalRetriever::findPath()");
1752 nlerror("Exited twice the surface", intersections.size());
1753 }
1754
1755 if (exitLoop != enterLoop)
1756 {
1757 nlwarning("in NLPACS::CLocalRetriever::findPath()");
1758 nlerror("Exited and rentered by a different loop");
1759 }
1760 }
1761 }
1762
1763 // dumpSurface(surfaceId);
1764
1765 path.push_back(CVector2s(A.Estimation));
1766
1767 for (i=intersStart; i<intersEnd; )
1768 {
1769 uint exitChainId = _OrderedChains[intersections[i].OChain].getParentId(),
1770 enterChainId = _OrderedChains[intersections[i+1].OChain].getParentId();
1771 const CChain &exitChain = _Chains[exitChainId],
1772 &enterChain = _Chains[enterChainId];
1773 uint loopId, exitLoopIndex, enterLoopIndex;
1774
1775 if (exitChain.getLeft() == surfaceId)
1776 {
1777 loopId = exitChain.getLeftLoop();
1778 exitLoopIndex = exitChain.getLeftLoopIndex();
1779 }
1780 else
1781 {
1782 loopId = exitChain.getRightLoop();
1783 exitLoopIndex = exitChain.getRightLoopIndex();
1784 }
1785
1786 const CRetrievableSurface::TLoop &loop = surface._Loops[loopId];
1787
1788 if (enterChain.getLeft() == surfaceId)
1789 enterLoopIndex = enterChain.getLeftLoopIndex();
1790 else
1791 enterLoopIndex = enterChain.getRightLoopIndex();
1792
1793 float forwardLength = (exitChain.getLength()+enterChain.getLength())*0.5f;
1794
1795 sint loopIndex = exitLoopIndex;
1796 uint thisChainId = exitChainId;
1797 bool thisChainForward = (enterChain.getLeft() == surfaceId);
1798 uint thisOChainId = intersections[i].OChain;
1799 sint thisOChainIndex = _OrderedChains[thisOChainId].getIndexInParent();
1800 bool forward;
1801
1802 if (exitChainId != enterChainId)
1803 {
1804 for (j=(exitLoopIndex+1)%loop.size(); j!=enterLoopIndex; j=(j+1)%loop.size())
1805 forwardLength += _Chains[surface._Chains[loop[j]].Chain].getLength();
1806 forward = (forwardLength <= loop.Length-forwardLength);
1807 }
1808 else
1809 {
1810 forward = !thisChainForward ^ (_OrderedChains[intersections[i].OChain].getIndexInParent() < _OrderedChains[intersections[i+1].OChain].getIndexInParent());
1811 }
1812
1813 path.push_back(CVector2s(A.Estimation+intersections[i].Position*(B.Estimation-A.Estimation)));
1814
1815 for(;;)
1816 {
1817 sint from = (thisOChainId == intersections[i].OChain) ? intersections[i].Edge : -1,
1818 to = (thisOChainId == intersections[i+1].OChain) ? intersections[i+1].Edge : -1;
1819 bool oforward = thisChainForward ^ forward ^ _OrderedChains[thisOChainId].isForward();
1820
1821 if (from != -1 && to != -1)
1822 oforward = (intersections[i].Edge < intersections[i+1].Edge);
1823
1824 _OrderedChains[thisOChainId].traverse(from, to, oforward, path);
1825
1826 if (thisOChainId == intersections[i+1].OChain)
1827 break;
1828
1829 thisOChainIndex = (thisChainForward ^ forward) ? thisOChainIndex-1 : thisOChainIndex+1;
1830
1831 if (thisOChainIndex < 0 || thisOChainIndex >= (sint)_Chains[thisChainId]._SubChains.size())
1832 {
1833 if (forward)
1834 {
1835 loopIndex++;
1836 if (loopIndex == (sint)loop.size())
1837 loopIndex = 0;
1838 }
1839 else
1840 {
1841 loopIndex--;
1842 if (loopIndex < 0)
1843 loopIndex = (sint)loop.size()-1;
1844 }
1845
1846 thisChainId = surface._Chains[loop[loopIndex]].Chain;
1847 thisChainForward = (_Chains[thisChainId].getLeft() == surfaceId);
1848 thisOChainIndex = (thisChainForward == forward) ?
1849 0 : (sint)_Chains[thisChainId]._SubChains.size()-1;
1850 }
1851
1852 thisOChainId = _Chains[thisChainId]._SubChains[thisOChainIndex];
1853 }
1854
1855 path.push_back(CVector2s(A.Estimation+intersections[i+1].Position*(B.Estimation-A.Estimation)));
1856 i += 2;
1857 }
1858
1859 path.push_back(CVector2s(B.Estimation));
1860 }
1861 #ifdef NL_OS_WINDOWS
1862 //#pragma optimize( "", on )
1863 #endif // NL_OS_WINDOWS
1864
1865 // ***************************************************************************
1866 // ***************************************************************************
1867 // Collisions part.
1868 // ***************************************************************************
1869 // ***************************************************************************
1870
1871
1872 // ***************************************************************************
1873 void NLPACS::CLocalRetriever::computeCollisionChainQuad()
1874 {
1875 _ChainQuad.build(_OrderedChains);
1876 }
1877
1878
1879 // ***************************************************************************
1880 void NLPACS::CLocalRetriever::testCollision(CCollisionSurfaceTemp &cst, const CAABBox &bboxMove, const CVector2f &transBase) const
1881 {
1882 if (!_Loaded)
1883 return;
1884
1885 // H_AUTO(PACS_LR_testCollision);
1886
1887 sint i;
1888
1889 // 0. select ordered chains in the chainquad.
1890 //=====================================
1891 // H_BEFORE(PACS_LR_testCol_selEdges);
1892 sint nEce= _ChainQuad.selectEdges(bboxMove, cst);
1893 // H_AFTER(PACS_LR_testCol_selEdges);
1894 // NB: cst.OChainLUT is assured to be full of 0xFFFF after this call (if was right before).
1895
1896
1897 // 1. regroup them in chains. build cst.CollisionChains
1898 //=====================================
1899 // NB: use cst.OChainLUT to look if a Chain has been inserted before.
1900 uint16 *chainLUT= cst.OChainLUT;
1901
1902 // bkup where we begin to add chains.
1903 uint firstChainAdded= (uint)cst.CollisionChains.size();
1904
1905 // For all edgechain entry.
1906 for(i=0;i<nEce;i++)
1907 {
1908 CEdgeChainEntry &ece= cst.EdgeChainEntries[i];
1909 // this is the ordered chain in the retriever.
1910 const COrderedChain &oChain= this->getOrderedChains()[ece.OChainId];
1911 // this is the id of the chain is the local retriever.
1912 uint16 chainId= oChain.getParentId();
1913
1914 // test if edge is interior and points to another instance
1915 if (_Type == Interior && CChain::isBorderChainId(this->getChains()[chainId].getRight()))
1916 {
1917 // then look for a door that match this edge
1918 uint l;
1919 for (l=0; l<_ExteriorMesh.getLinks().size() && _ExteriorMesh.getLink(l).ChainId != chainId; ++l)
1920 ;
1921
1922 // if found a door, then leave the edge as is
1923 if (l < _ExteriorMesh.getLinks().size())
1924 continue;
1925 }
1926
1927
1928 // add/retrieve the id in cst.CollisionChains.
1929 //=================================
1930 uint ccId;
1931 // if never added.
1932 if(chainLUT[chainId]==0xFFFF)
1933 {
1934 // H_AUTO(PACS_LR_testCol_addToLUT);
1935 // add a new CCollisionChain.
1936 ccId= (uint)cst.CollisionChains.size();
1937 cst.CollisionChains.push_back(CCollisionChain());
1938 // Fill it with default.
1939 cst.CollisionChains[ccId].Tested= false;
1940 cst.CollisionChains[ccId].ExteriorEdge = false;
1941 cst.CollisionChains[ccId].FirstEdgeCollide= 0xFFFFFFFF;
1942 cst.CollisionChains[ccId].ChainId= chainId;
1943 // Fill Left right info.
1944 cst.CollisionChains[ccId].LeftSurface.SurfaceId= this->getChains()[chainId].getLeft();
1945 cst.CollisionChains[ccId].RightSurface.SurfaceId= this->getChains()[chainId].getRight();
1946 // NB: cst.CollisionChains[ccId].*Surface.RetrieverInstanceId is not filled here because we don't have
1947 // this info at this level.
1948
1949 // store this Id in the LUT of chains.
1950 chainLUT[chainId]= uint16(ccId);
1951 }
1952 else
1953 {
1954 // get the id of this collision chain.
1955 ccId= chainLUT[chainId];
1956 }
1957
1958 // add edge collide to the list.
1959 //=================================
1960 // H_BEFORE(PACS_LR_testCol_addToList);
1961 CCollisionChain &colChain= cst.CollisionChains[ccId];
1962 const std::vector<CVector2s> &oChainVertices= oChain.getVertices();
1963 for(sint edge=ece.EdgeStart; edge<ece.EdgeEnd; edge++)
1964 {
1965 CVector2f p0= oChainVertices[edge].unpack();
1966 CVector2f p1= oChainVertices[edge+1].unpack();
1967
1968 // alloc a new edgeCollide.
1969 uint32 ecnId= cst.allocEdgeCollideNode();
1970 CEdgeCollideNode &ecn= cst.getEdgeCollideNode(ecnId);
1971
1972 // append to the front of the list.
1973 ecn.Next= colChain.FirstEdgeCollide;
1974 colChain.FirstEdgeCollide= ecnId;
1975
1976 // build this edge.
1977 p0+= transBase;
1978 p1+= transBase;
1979 ecn.make(p0, p1);
1980 }
1981 // H_AFTER(PACS_LR_testCol_addToList);
1982 }
1983
1984
1985
1986 // 2. Reset LUT to 0xFFFF.
1987 //=====================================
1988
1989 // H_BEFORE(PACS_LR_testCol_resetLUT);
1990 // for all collisions chains inserted (starting from firstChainAdded), reset LUT.
1991 for(i=firstChainAdded; i<(sint)cst.CollisionChains.size(); i++)
1992 {
1993 uint ccId= cst.CollisionChains[i].ChainId;
1994 chainLUT[ccId]= 0xFFFF;
1995 }
1996 // H_AFTER(PACS_LR_testCol_resetLUT);
1997 }
1998
1999
2000 // ***************************************************************************
2001 // ***************************************************************************
2002 // ***************************************************************************
2003 // ***************************************************************************
2004
2005
2006 // ***************************************************************************
2007 void NLPACS::CLocalRetriever::buildInteriorSurfaceBBoxes(std::vector<NLMISC::CAABBox> &surfaceBBoxes) const
2008 {
2009 // resize dest, and init.
2010 vector<bool> firstTriangle;
2011 surfaceBBoxes.clear();
2012 surfaceBBoxes.resize(_Surfaces.size());
2013 firstTriangle.resize(_Surfaces.size(), true);
2014
2015 // For all _InteriorFaces.
2016 for(uint iIntFace=0; iIntFace<_InteriorFaces.size(); iIntFace++)
2017 {
2018 const CInteriorFace &intFace= _InteriorFaces[iIntFace];
2019
2020 // Extend the surface of this face with her 3 points.
2021
2022 // check good id.
2023 if(intFace.Surface==(uint)-1)
2024 continue;
2025 nlassert(intFace.Surface<_Surfaces.size());
2026
2027 // If first time we extend the bbox of this surface
2028 if(firstTriangle[intFace.Surface])
2029 {
2030 surfaceBBoxes[intFace.Surface].setCenter(_InteriorVertices[intFace.Verts[0]] );
2031 firstTriangle[intFace.Surface]= false;
2032 }
2033 else
2034 surfaceBBoxes[intFace.Surface].extend(_InteriorVertices[intFace.Verts[0]] );
2035
2036 // extend with other 2 points
2037 surfaceBBoxes[intFace.Surface].extend(_InteriorVertices[intFace.Verts[1]] );
2038 surfaceBBoxes[intFace.Surface].extend(_InteriorVertices[intFace.Verts[2]] );
2039 }
2040
2041 }
2042
2043
2044 // ***************************************************************************
2045 void NLPACS::CLocalRetriever::replaceChain(uint32 chainId, const std::vector<NLPACS::CLocalRetriever::CChainReplacement> &replacement)
2046 {
2047 // free subchains
2048 uint i, j;
2049 for (i=0; i<_Chains[chainId]._SubChains.size(); ++i)
2050 {
2051 FreeOChains.push_back(_Chains[chainId]._SubChains[i]);
2052 _OrderedChains[_Chains[chainId]._SubChains[i]] = COrderedChain();
2053 _FullOrderedChains[_Chains[chainId]._SubChains[i]] = COrderedChain3f();
2054 }
2055
2056 // create new chains in replacement of this chain
2057
2058 for (i=0; i<replacement.size(); ++i)
2059 {
2060 vector<CVector> vertices = replacement[i].Vertices;
2061 sint left = replacement[i].Left;
2062 sint right = replacement[i].Right;
2063
2064 if (CChain::isBorderChainId(right))
2065 {
2066 // check border already exists for this particular chain
2067 sint32 border = CChain::convertBorderChainId(right);
2068
2069 if (border < (sint)_BorderChains.size() && (chainId != _BorderChains[border] || chainId != replacement[i].Chain))
2070 {
2071 nlwarning("replaceChain(): replacement of a border is forced whereas this border is already used and not replaced!");
2072 }
2073
2074 if (border >= (sint)_BorderChains.size())
2075 {
2076 if (border > (sint)_BorderChains.size())
2077 {
2078 nlwarning("replaceChain(): _BorderChains size increased of more than 1 step, holes may result!");
2079 }
2080
2081 _BorderChains.resize(border+1, 0xffff);
2082 }
2083
2084 _BorderChains[border] = uint16(replacement[i].Chain);
2085 }
2086
2087 nlassert(vertices.size() >= 2);
2088
2089 // Remove doubled vertices due to CVector2s snapping
2090 vector<CVector2s> converts;
2091
2092 for (j=0; j<vertices.size(); ++j)
2093 converts.push_back(CVector2s(vertices[j]));
2094
2095 vector<CVector2s>::iterator next2s = converts.begin(), it2s, prev2s;
2096 prev2s = next2s; ++next2s;
2097 it2s = next2s; ++next2s;
2098
2099 vector<CVector>::iterator it3f = vertices.begin();
2100 CVector prev3f = *it3f;
2101 ++it3f;
2102
2103
2104 for (; it2s != converts.end() && next2s != converts.end(); )
2105 {
2106 // if the next point is equal to the previous
2107 if (*it2s == *prev2s || *it2s == *next2s)
2108 {
2109 // then remove the next point
2110 it2s = converts.erase(it2s);
2111 it3f = vertices.erase(it3f);
2112
2113 prev2s = it2s;
2114 --prev2s;
2115 next2s = it2s;
2116 ++next2s;
2117 }
2118 else
2119 {
2120 // else remember the next point, and step to the next...
2121 ++prev2s;
2122 ++it2s;
2123 ++next2s;
2124 ++it3f;
2125 prev3f = *it3f;
2126 }
2127 }
2128
2129 nlassert(vertices.size() >= 2);
2130
2131 sint32 newId = replacement[i].Chain;
2132 if (newId >= (sint)_Chains.size())
2133 _Chains.resize(newId+1);
2134
2135 //CChain &nchain = _Chains[newId];
2136
2137 if (left>(sint)_Surfaces.size())
2138 nlerror ("left surface id MUST be id<%d (id=%d)", _Surfaces.size(), left);
2139 if (right>(sint)_Surfaces.size())
2140 nlerror ("right surface id MUST be id<%d (id=%d)", _Surfaces.size(), right);
2141
2142 // checks if we can build the chain.
2143 if (newId > 65535)
2144 nlerror("in NLPACS::CLocalRetriever::addChain(): reached the maximum number of chains");
2145
2146 //CRetrievableSurface *leftSurface = (left>=0) ? &(_Surfaces[left]) : NULL;
2147 //CRetrievableSurface *rightSurface = (right>=0) ? &(_Surfaces[right]) : NULL;
2148
2149 CChain &chain = _Chains[newId];
2150
2151 chain._StartTip = 0xffff;
2152 chain._StopTip = 0xffff;
2153
2154 // make the chain and its subchains.
2155 chain.make(vertices, left, right, _OrderedChains, (uint16)newId, _FullOrderedChains, FreeOChains);
2156 }
2157
2158 for (i=0; i<_Surfaces.size(); ++i)
2159 {
2160 // remove old chain and replace by new chains in surface links
2161 for (j=0; j<_Surfaces[i]._Chains.size(); ++j)
2162 {
2163 if (_Surfaces[i]._Chains[j].Chain == (sint)chainId)
2164 {
2165 _Surfaces[i]._Chains.erase(_Surfaces[i]._Chains.begin()+j);
2166
2167 uint k;
2168 for (k=0; k<replacement.size(); ++k)
2169 {
2170 CRetrievableSurface::CSurfaceLink link;
2171
2172 link.Chain = replacement[k].Chain;
2173 link.Surface = (replacement[k].Left == (sint)i ? replacement[k].Right : replacement[k].Left);
2174 _Surfaces[i]._Chains.push_back(link);
2175 }
2176
2177 break;
2178 }
2179 }
2180
2181 // remove old chain and replace by new chains in surface loops
2182 for (j=0; j<_Surfaces[i]._Loops.size(); ++j)
2183 {
2184 uint k;
2185
2186 for (k=0; k<_Surfaces[i]._Loops[j].size(); ++k)
2187 {
2188 if (_Surfaces[i]._Loops[j][k] == chainId)
2189 {
2190 _Surfaces[i]._Loops[j].erase(_Surfaces[i]._Loops[j].begin()+k);
2191 uint m;
2192
2193 for (m=0; m<replacement.size(); ++m)
2194 _Surfaces[i]._Loops[j].insert(_Surfaces[i]._Loops[j].begin()+k+m, uint16(replacement[m].Chain));
2195
2196 break;
2197 }
2198 }
2199 }
2200 }
2201 }
2202
2203
2204
2205
2206 /*
2207 * Check surface integrity
2208 */
2209 bool NLPACS::CLocalRetriever::checkSurfacesIntegrity(NLMISC::CVector translation, bool verbose) const
2210 {
2211 bool success = true;
2212 uint surf;
2213
2214 for (surf=0; surf<_Surfaces.size(); ++surf)
2215 {
2216 if (!checkSurfaceIntegrity(surf, translation, verbose))
2217 {
2218 success = false;
2219 if (verbose)
2220 {
2221 dumpSurface(surf, translation);
2222 }
2223 }
2224
2225 }
2226
2227 return success;
2228 }
2229
2230
2231 /**
2232 * Check surface integrity
2233 */
2234 bool NLPACS::CLocalRetriever::checkSurfaceIntegrity(uint surf, NLMISC::CVector translation, bool verbose) const
2235 {
2236 if (surf >= _Surfaces.size())
2237 return false;
2238
2239 const CRetrievableSurface& surface = _Surfaces[surf];
2240
2241 uint nloops = (uint)surface.getLoops().size();
2242
2243 std::vector<std::pair<CVector2s, CVector2s> > edges;
2244
2245 uint iloop;
2246 uint i, j, k;
2247 for (iloop=0; iloop<nloops; ++iloop)
2248 {
2249 const CRetrievableSurface::TLoop& loop = surface.getLoop(iloop);
2250
2251 for (i=0; i<loop.size(); ++i)
2252 {
2253 // loop[i] is the index in the surface list of chains
2254 // so surface._Chains[loop[i]].Chain is really the chain id !!!
2255 const CChain& chain = _Chains[ surface._Chains[loop[i]].Chain ];
2256 for (j=0; j<chain.getSubChains().size(); ++j)
2257 {
2258 const COrderedChain& ochain = _OrderedChains[chain.getSubChain(j)];
2259
2260 for (k=0; k+1<ochain.getVertices().size(); ++k)
2261 {
2262 edges.push_back(std::pair<CVector2s, CVector2s>(ochain[k], ochain[k+1]));
2263 }
2264 }
2265 }
2266 }
2267
2268 bool success = true;
2269
2270 for (i=0; i+1<edges.size(); ++i)
2271 {
2272 for (j=i+1; j<edges.size(); ++j)
2273 {
2274 CVector2s a0 = edges[i].first,
2275 a1 = edges[i].second;
2276 CVector2s b0 = edges[j].first,
2277 b1 = edges[j].second;
2278
2279 double a, b;
2280 bool inters = CVector2s::intersect(a0, a1, b0, b1, &a, &b);
2281
2282 if (!inters)
2283 continue;
2284
2285 double da = (a1-a0).norm();
2286 double db = (b1-b0).norm();
2287
2288 bool tipa = (fabs(a)*da < 4.0e-2 || fabs(1.0-a)*da < 4.0e-2);
2289 bool tipb = (fabs(b)*db < 4.0e-2 || fabs(1.0-b)*db < 4.0e-2);
2290
2291 if (tipa && tipb)
2292 continue;
2293
2294 CVector2s ip = a0 + (a1-a0)*(float)a;
2295 CVector p = ip.unpack3f() - translation;
2296 nlwarning("Surface %d has issue at position (%f,%f)", surf, p.x, p.y);
2297 if (verbose)
2298 {
2299 NLMISC::CVector v;
2300 v = a0.unpack3f() - translation;
2301 nlwarning(" -- a0: (%f,%f)", v.x, v.y);
2302 v = a1.unpack3f() - translation;
2303 nlwarning(" -- a1: (%f,%f)", v.x, v.y);
2304 v = b0.unpack3f() - translation;
2305 nlwarning(" -- b0: (%f,%f)", v.x, v.y);
2306 v = b1.unpack3f() - translation;
2307 nlwarning(" -- b1: (%f,%f)", v.x, v.y);
2308 }
2309
2310 success = false;
2311 }
2312 }
2313
2314 return success;
2315 }