?  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 / edge_quad.cpp
blob11053f09bbe88e97abc6f6727044e20ea43cd3e7
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 #include "stdpacs.h"
18
19 #include "nel/pacs/edge_quad.h"
20 #include "nel/pacs/global_retriever.h"
21
22 using namespace std;
23 using namespace NLMISC;
24
25
26 namespace NLPACS
27 {
28
29
30 // ***************************************************************************
31 const float CEdgeQuad::_QuadElementSize= 4; // = 4 meters.
32
33
34 // ***************************************************************************
35 CEdgeQuad::CEdgeQuad()
36 {
37 _QuadData= NULL;
38 _QuadDataLen= 0;
39 }
40 // ***************************************************************************
41 CEdgeQuad::~CEdgeQuad()
42 {
43 clear();
44 }
45 // ***************************************************************************
46 CEdgeQuad::CEdgeQuad(const CEdgeQuad &o)
47 {
48 _QuadData= NULL;
49 _QuadDataLen= 0;
50 *this= o;
51 }
52 // ***************************************************************************
53 CEdgeQuad &CEdgeQuad::operator=(const CEdgeQuad &o)
54 {
55 // Alloc good quaddata.
56 _QuadDataLen= o._QuadDataLen;
57 delete [] _QuadData;
58 if(_QuadDataLen>0)
59 {
60 _QuadData= (uint8*)new uint8[_QuadDataLen];
61 // copy contents.
62 memcpy(_QuadData, o._QuadData, _QuadDataLen);
63 }
64 else
65 _QuadData= NULL;
66
67 // copy infos.
68 _Width= o._Width;
69 _Height= o._Height;
70 _X= o._X;
71 _Y= o._Y;
72 _EdgeEntries = o._EdgeEntries;
73
74 // copy good pointers.
75 _Quad.clear();
76 _Quad.resize(o._Quad.size(), NULL);
77 for(sint i=0; i<(sint)_Quad.size(); i++)
78 {
79 if(o._Quad[i])
80 {
81 uint32 off= (uint32)(o._Quad[i]-o._QuadData);
82 _Quad[i]= _QuadData+off;
83 }
84 }
85
86
87 return *this;
88 }
89
90 // ***************************************************************************
91 void CEdgeQuad::clear()
92 {
93 delete [] _QuadData;
94 _QuadData= NULL;
95 _QuadDataLen= 0;
96
97 _Quad.clear();
98 _EdgeEntries.clear();
99 _Width = 0;
100 _Height = 0;
101 _X = 0;
102 _Y = 0;
103 }
104
105 // ***************************************************************************
106 void CEdgeQuad::getGridBounds(sint32 &x0, sint32 &y0, sint32 &x1, sint32 &y1, const CVector &minP, const CVector &maxP) const
107 {
108 x0= (sint32)floor(minP.x / _QuadElementSize) - _X;
109 y0= (sint32)floor(minP.y / _QuadElementSize) - _Y;
110 x1= (sint32) ceil(maxP.x / _QuadElementSize) - _X;
111 y1= (sint32) ceil(maxP.y / _QuadElementSize) - _Y;
112 x0= max(x0, (sint32)0);
113 y0= max(y0, (sint32)0);
114 x1= min(x1, (sint32)_Width);
115 y1= min(y1, (sint32)_Height);
116 }
117
118
119
120 // ***************************************************************************
121 void CEdgeQuad::build(const CExteriorMesh &em,
122 const CGlobalRetriever &global,
123 CCollisionSurfaceTemp &cst,
124 uint32 thisInstance)
125 {
126 const std::vector<CExteriorMesh::CEdge> &edges = em.getEdges();
127
128 vector< list<uint16> > tempQuad;
129 sint i, j;
130
131 // first, clear any pr-build.
132 contReset(_Quad);
133 delete [] _QuadData;
134 _QuadData= NULL;
135 _QuadDataLen= 0;
136
137 // don't care about the origin of the instance
138 CVector origin = global.getInstance(thisInstance).getOrigin();
139
140 // 0. Find BBox of the grid. Allocate grid.
141 //=========================================
142 bool first=true;
143 CAABBox chainquadBBox;
144 // run all chains.
145 for (i=0; i<(sint)edges.size()-1; i++)
146 {
147 // enlarge bbox.
148 if (first)
149 first= false, chainquadBBox.setCenter(edges[i].Start);
150 else
151 chainquadBBox.extend(edges[i].Start);
152 }
153
154 // compute X,Y,Width, Height.
155 _X= (sint32)floor(chainquadBBox.getMin().x / _QuadElementSize);
156 _Y= (sint32)floor(chainquadBBox.getMin().y / _QuadElementSize);
157 _Width= (sint32)ceil(chainquadBBox.getMax().x / _QuadElementSize) - _X;
158 _Height= (sint32)ceil(chainquadBBox.getMax().y / _QuadElementSize) - _Y;
159
160 tempQuad.resize(_Width*_Height);
161 _Quad.resize(_Width*_Height, NULL);
162
163
164 // 1. For each edge, add them to the quadgrid.
165 //=========================================
166 // run all chains.
167 for (i=0; i<(sint)edges.size()-1; i++)
168 {
169 if (edges[i].Link == -2)
170 continue;
171
172 float dnorm = (edges[i+1].Start-edges[i].Start).norm();
173 uint numStep = (uint)(dnorm/0.1f)+1;
174 uint step;
175
176 CVector pbegin = edges[i].Start+origin,
177 pend = edges[i+1].Start+origin;
178
179 CVector opbegin = edges[i].Start,
180 opend = edges[i+1].Start;
181
182 for (step=0; step<numStep; ++step)
183 {
184 float lambda0 = (float)(step)/(float)(numStep);
185 float lambda1 = (float)(step+1)/(float)(numStep);
186 CVector p0 = pbegin*(1.0f-lambda0)+pend*(lambda0),
187 p1 = pbegin*(1.0f-lambda1)+pend*(lambda1);
188 CVector op0 = opbegin*(1.0f-lambda0)+opend*(lambda0),
189 op1 = opbegin*(1.0f-lambda1)+opend*(lambda1);
190 CVector s0, s1,
191 mins, maxs;
192
193 uint prevEdge = (i-1)%(edges.size()-1);
194 bool prio0 = (edges[i].Link!=-1) || (edges[prevEdge].Link!=-1);
195
196 UGlobalPosition gp0 = global.retrievePosition(p0);
197 global.updateHeight(gp0);
198 UGlobalPosition gp1 = global.retrievePosition(p1);
199 global.updateHeight(gp1);
200
201 if (!prio0)
202 {
203 swap(p0, p1);
204 swap(op0, op1);
205 swap(gp0, gp1);
206 }
207
208 if (gp0.InstanceId == -1)
209 {
210 swap(p0, p1);
211 swap(op0, op1);
212 swap(gp0, gp1);
213 }
214
215 const TCollisionSurfaceDescVector *pcd = global.testCylinderMove(gp0, p1-p0, 0.01f, cst);
216
217 if (pcd == NULL)
218 {
219 // nlwarning("in CEdgeQuad::build(): testCylinderMove() returned NULL");
220 continue;
221 }
222
223 TCollisionSurfaceDescVector cd = (*pcd);
224
225 if (edges[i].Link != -1 && !cd.empty())
226 {
227 nlwarning ("In NLPACS::CEdgeQuad::build()");
228 nlwarning ("ERROR: exterior edge %d with interior link crosses some surfaces", i);
229 cd.clear ();
230 }
231
232 // add start surface to the collision description
233 CCollisionSurfaceDesc stcd;
234 stcd.ContactTime = 0.0f;
235 stcd.ContactSurface.RetrieverInstanceId = gp0.InstanceId;
236 stcd.ContactSurface.SurfaceId = gp0.LocalPosition.Surface;
237 cd.insert(cd.begin(), stcd);
238
239 // get the surface, chain ...
240 sint edgeId = i;
241 uint16 chainId;
242
243 CSurfaceIdent interior;
244 if (edges[i].Link == -1)
245 {
246 interior.RetrieverInstanceId = -1;
247 interior.SurfaceId = -1;
248 chainId = 0xFFFF;
249 }
250 else
251 {
252 interior.RetrieverInstanceId = thisInstance;
253 interior.SurfaceId = em.getLink(edges[i].Link).SurfaceId;
254 chainId = em.getLink(edges[i].Link).ChainId;
255 }
256
257
258 // add end point to the collision description
259 stcd = cd.back();
260 stcd.ContactTime = 1.0f;
261 cd.push_back(stcd);
262
263 for (j=0; j<(sint)cd.size()-1; ++j)
264 {
265 s0 = op0*(float)(1.0-cd[j].ContactTime) + op1*(float)(cd[j].ContactTime);
266 s1 = op0*(float)(1.0-cd[j+1].ContactTime) + op1*(float)(cd[j+1].ContactTime);
267
268 mins.minof(s0, s1);
269 maxs.maxof(s0, s1);
270
271 // PrecisionPb: extend a little this edge. This is important for special case like borders on zones.
272 if(mins.x-maxs.x==0)
273 mins.x-=0.001f, maxs.x+=0.001f;
274 if(mins.y-maxs.y==0)
275 mins.y-=0.001f, maxs.y+=0.001f;
276
277 // get bounding coordinate of this edge in the quadgrid.
278 sint32 x0, y0, x1, y1;
279 sint x, y;
280 getGridBounds(x0, y0, x1, y1, mins, maxs);
281
282 CSurfaceIdent exterior = cd[j].ContactSurface;
283
284 uint entry;
285 for (entry=0; entry<_EdgeEntries.size(); ++entry)
286 {
287 if (_EdgeEntries[entry].EdgeId == edgeId &&
288 _EdgeEntries[entry].Exterior == exterior)
289 {
290 if (_EdgeEntries[entry].ChainId != chainId ||
291 _EdgeEntries[entry].Interior != interior)
292 {
293 nlwarning("In NLPACS::CEdgeQuad::build()");
294 nlerror("exterior edge %d has different interior linkage", edgeId);
295 }
296
297 break;
298 }
299 }
300
301 // if this entry didn't exist before create a new one...
302 if (entry == _EdgeEntries.size())
303 {
304 _EdgeEntries.push_back(CExteriorEdgeEntry());
305 _EdgeEntries.back().EdgeId = uint16(edgeId);
306 _EdgeEntries.back().ChainId = chainId;
307 _EdgeEntries.back().Interior = interior;
308 _EdgeEntries.back().Exterior = exterior;
309 }
310
311 // add this edge to all the quadnode it touches.
312 for(y=y0; y<y1; y++)
313 {
314 for(x=x0; x<x1; x++)
315 {
316 // check we don't push this entry twice
317 list<uint16>::iterator it;
318 for (it=tempQuad[y*_Width+x].begin(); it!=tempQuad[y*_Width+x].end(); ++it)
319 if (entry == *it)
320 break;
321 if (it == tempQuad[y*_Width+x].end())
322 tempQuad[y*_Width+x].push_back(uint16(entry));
323 }
324 }
325 }
326 }
327
328 }
329
330 nlinfo("Built ExteriorEdgeQuad, linked following doors:");
331 for (i=0; i<(sint)_EdgeEntries.size(); ++i)
332 {
333 if (edges[_EdgeEntries[i].EdgeId].Link != -1 &&
334 (_EdgeEntries[i].Interior.RetrieverInstanceId == -1 || _EdgeEntries[i].Interior.SurfaceId == -1 ||
335 _EdgeEntries[i].Exterior.RetrieverInstanceId == -1 || _EdgeEntries[i].Exterior.SurfaceId == -1))
336 {
337 nlwarning("In NLPACS::CEdgeQuad::build(): exterior door %d has corrupted link", i);
338 }
339 else if (edges[_EdgeEntries[i].EdgeId].Link != -1)
340 {
341 nlinfo("Inst=%d ExtEdge=%d IntInst=%d IntSurf=%d IntChain=%d ExtInst=%d ExtSurf=%d", thisInstance, _EdgeEntries[i].EdgeId,
342 _EdgeEntries[i].Interior.RetrieverInstanceId, _EdgeEntries[i].Interior.SurfaceId, _EdgeEntries[i].ChainId,
343 _EdgeEntries[i].Exterior.RetrieverInstanceId, _EdgeEntries[i].Exterior.SurfaceId);
344 }
345 }
346
347 // 2. Mem optimisation: Use only 1 block for ALL quads of the grid.
348 //=========================================
349 sint memSize= 0;
350 // run all quads.
351 for(i=0;i<(sint)tempQuad.size();i++)
352 {
353 list<uint16> &quadNode= tempQuad[i];
354
355 if(!quadNode.empty())
356 {
357 // add an entry for Len.
358 memSize+= sizeof(uint16);
359 // add N entry of CEdgeChainEntry.
360 memSize+= (sint)quadNode.size()*sizeof(uint16);
361 }
362 }
363
364 // allocate.
365 _QuadData= (uint8*)new uint8[memSize];
366 _QuadDataLen= memSize;
367
368
369 // 3. Fill _QuadData with lists.
370 //=========================================
371 uint8 *ptr= _QuadData;
372 for(i=0;i<(sint)tempQuad.size();i++)
373 {
374 list<uint16> &srcQuadNode= tempQuad[i];
375 list<uint16>::iterator it;
376
377 if(!srcQuadNode.empty())
378 {
379 _Quad[i]= ptr;
380
381 // write len.
382 uint16 len= uint16(srcQuadNode.size());
383 *((uint16*)ptr)= len;
384 ptr+= sizeof(uint16);
385
386 // add entries.
387 it= srcQuadNode.begin();
388 for(j=0; j<len; j++, it++)
389 {
390 *((uint16 *)ptr)= *it;
391 ptr+= sizeof(uint16);
392 }
393 }
394 }
395
396 // End.
397 }
398
399
400 // ***************************************************************************
401 sint CEdgeQuad::selectEdges(const NLMISC::CAABBox &bbox, CCollisionSurfaceTemp &cst) const
402 {
403 sint nRes=0;
404 sint i;
405 uint16 *indexLUT = cst.OChainLUT;
406
407 // start: no edge found.
408 cst.ExteriorEdgeIndexes.clear();
409
410 // get bounding coordinate of this bbox in the quadgrid.
411 sint32 x0, y0, x1, y1;
412 getGridBounds(x0, y0, x1, y1, bbox.getMin(), bbox.getMax());
413
414
415 // run all intersected quads.
416 for (sint y= y0; y<y1; y++)
417 {
418 for (sint x= x0; x<x1; x++)
419 {
420 uint8 *quadNode= _Quad[y*_Width+x];
421
422 // no edgechain entry??
423 if(!quadNode)
424 continue;
425
426 // get edgechain entries
427 sint numExteriorEdgeIndexes= *((uint16*)quadNode);
428 quadNode+= sizeof(uint16);
429 uint16 *ptrExteriorEdgeIndex= (uint16*)quadNode;
430
431 // For each one, add it to the result list.
432 for (i=0;i<numExteriorEdgeIndexes;i++)
433 {
434 uint16 index = ptrExteriorEdgeIndex[i];
435
436 // if ochain not yet inserted.
437 if (indexLUT[index]==0xFFFF)
438 {
439 // inc the list.
440 indexLUT[index]= uint16(nRes);
441 cst.ExteriorEdgeIndexes.push_back(index);
442 nRes++;
443 }
444 }
445 }
446 }
447
448
449 // reset LUT to 0xFFFF for all ochains selected.
450 for(i=0;i<nRes;i++)
451 indexLUT[cst.ExteriorEdgeIndexes[i]]= 0xFFFF;
452
453 return nRes;
454 }
455
456 sint CEdgeQuad::selectEdges(CVector start, CVector end, CCollisionSurfaceTemp &cst) const
457 {
458 sint nRes=0;
459 sint i;
460 uint16 *indexLUT= cst.OChainLUT;
461
462 // start: no edge found.
463 cst.ExteriorEdgeIndexes.clear();
464
465 if (end.x < start.x)
466 swap(start, end);
467
468 float minx = _X*_QuadElementSize,
469 miny = _Y*_QuadElementSize,
470 maxx = minx + _Width*_QuadElementSize,
471 maxy = miny + _Height*_QuadElementSize;
472
473 if (start.x > maxx || end.x < minx || start.y > maxy || end.y < miny)
474 return nRes;
475
476 if (start.x < minx)
477 {
478 start.y = start.y+(end.y-start.y)*(minx-start.x)/(end.x-start.x);
479 start.x = minx;
480 }
481
482 if (start.y < miny)
483 {
484 start.x = start.x+(end.x-start.x)*(miny-start.y)/(end.y-start.y);
485 start.y = miny;
486 }
487
488 if (end.x > maxx)
489 {
490 end.y = start.y+(end.y-start.y)*(minx-start.x)/(end.x-start.x);
491 end.x = maxx;
492 }
493
494 if (end.y > maxy)
495 {
496 end.x = start.x+(end.x-start.x)*(miny-start.y)/(end.y-start.y);
497 end.y = maxy;
498 }
499
500 sint32 x0, x1, ya, yb;
501 sint x, y;
502 float fx, fxa, fxb, fya, fyb;
503
504 x0 = (sint32)floor(start.x / _QuadElementSize) - _X;
505 x1 = (sint32)ceil(end.x / _QuadElementSize) - _X;
506 fx = (x0+_X)*_QuadElementSize;
507
508 for (x=x0; x<x1; ++x)
509 {
510 fxa = (fx < start.x) ? start.x : fx;
511 fxb = (fx+_QuadElementSize > end.x) ? end.x : fx+_QuadElementSize;
512
513 fya = start.y+(end.y-start.y)*(fxa-start.x)/(end.x-start.x);
514 fyb = start.y+(end.y-start.y)*(fxb-start.x)/(end.x-start.x);
515
516 if (fya > fyb)
517 swap (fya, fyb);
518
519 ya = (sint32)floor(fya / _QuadElementSize) - _Y;
520 yb = (sint32)ceil(fyb / _QuadElementSize) - _Y;
521
522 fx += _QuadElementSize;
523
524 for (y=ya; y<yb; ++y)
525 {
526 uint8 *quadNode= _Quad[y*_Width+x];
527
528 // no edgechain entry??
529 if(!quadNode)
530 continue;
531
532 // get edgechain entries
533 sint numExteriorEdgeIndexes= *((uint16 *)quadNode);
534 quadNode+= sizeof(uint16);
535 uint16 *ptrExteriorEdgeIndex = (uint16 *)quadNode;
536
537 // For each one, add it to the result list.
538 for(i=0;i<numExteriorEdgeIndexes;i++)
539 {
540 uint16 index = ptrExteriorEdgeIndex[i];
541
542 // if ochain not yet inserted.
543 if(indexLUT[index]==0xFFFF)
544 {
545 // inc the list.
546 indexLUT[index]= uint16(nRes);
547 cst.ExteriorEdgeIndexes.push_back(ptrExteriorEdgeIndex[i]);
548 nRes++;
549 }
550 }
551 }
552 }
553
554 // reset LUT to 0xFFFF for all ochains selected.
555 for(i=0;i<nRes;i++)
556 indexLUT[cst.ExteriorEdgeIndexes[i]]= 0xFFFF;
557
558 return nRes;
559 }
560
561 // ***************************************************************************
562 void CEdgeQuad::serial(NLMISC::IStream &f)
563 {
564 /*
565 Version 0:
566 - base version.
567 */
568 (void)f.serialVersion(0);
569 uint i;
570
571 // serial basics.
572 f.serial(_X, _Y, _Width, _Height, _QuadDataLen);
573 f.serialCont(_EdgeEntries);
574
575 // serial _QuadData.
576 if(f.isReading())
577 {
578 delete [] _QuadData;
579 if(_QuadDataLen>0)
580 _QuadData= (uint8*)new uint8[_QuadDataLen];
581 else
582 _QuadData= NULL;
583 }
584 // Since we have only uint16 (see CEdgeChainEntry), serial them in a single block.
585 uint16 *ptrQData= (uint16*)_QuadData;
586 for(i=0;i<_QuadDataLen/2; i++, ptrQData++)
587 {
588 f.serial(*ptrQData);
589 }
590
591
592 // serial _Quad.
593 std::vector<uint32> offsets;
594 uint32 len;
595 uint32 val;
596 if(f.isReading())
597 {
598 // len/resize.
599 f.serial(len);
600 offsets.resize(len);
601 contReset(_Quad);
602 _Quad.resize(len);
603
604 // read offsets -> ptrs.
605 for(i=0; i<len; i++)
606 {
607 f.serial(val);
608 if(val== 0xFFFFFFFF)
609 _Quad[i]= NULL;
610 else
611 _Quad[i]= _QuadData+val;
612 }
613 }
614 else
615 {
616 // len/resize.
617 len= (uint32)_Quad.size();
618 f.serial(len);
619
620 // write offsets.
621 for(i=0; i<len; i++)
622 {
623 uint8 *ptr= _Quad[i];
624 if(ptr==NULL)
625 val= 0xFFFFFFFF;
626 else
627 val= (uint32)(ptr-_QuadData);
628 f.serial(val);
629 }
630 }
631
632 }
633
634
635
636 } // NLPACS