?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Fix game:addSpawnShapesByZone
[ryzomcore.git] / nel / tools / 3d / zone_welder / internal_weld.cpp
blobeed56934d2f19241168024e866437eb96969c24b
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 "../zone_lib/zone_utility.h"
18 //
19 #include "nel/misc/types_nl.h"
20 #include "nel/misc/path.h"
21 #include "nel/misc/file.h"
22 #include "nel/misc/aabbox.h"
23 //
24 #include "nel/3d/quad_grid.h"
25 #include "nel/3d/bezier_patch.h"
26 #include "nel/3d/zone.h"
27
28 //
29 #include <vector>
30 #include <algorithm>
31 #include <memory>
32 #include <set>
33
34
35
36
37 using namespace NLMISC;
38 using namespace NL3D;
39
40 // a patch vertex info, for quadtree insertion
41 struct CPatchVertexInfo
42 {
43 uint ZoneIndex; // this zone index, 0 for the midlle zone, and from 1 to 8 for the zones around
44 uint PatchIndex; // the Patch of this zone
45 uint PatchVertex; // the vertex of thi patch 0..3
46
47 CVector Pos;
48 CPatchVertexInfo() {}
49 CPatchVertexInfo(uint zoneIndex,
50 uint patchIndex,
51 uint patchVertex,
52 const CVector &pos
53 )
54 : ZoneIndex(zoneIndex),
55 PatchIndex(patchIndex),
56 PatchVertex(patchVertex),
57 Pos(pos)
58 {
59 }
60 };
61
62 typedef std::vector<CPatchVertexInfo *> TPVVect;
63 typedef CQuadGrid<CPatchVertexInfo> TPVQuadGrid;
64
65 // ***************************************************************************
66
67 void bind_1_1 (std::vector<CPatchInfo> &zoneInfos, uint patch0, uint edge0, uint patch1, uint edge1, uint zoneId)
68 {
69 // Bind type
70 zoneInfos[patch0].BindEdges[edge0].NPatchs = 1;
71 zoneInfos[patch1].BindEdges[edge1].NPatchs = 1;
72
73 // Zone ID
74 zoneInfos[patch0].BindEdges[edge0].ZoneId = zoneId;
75 zoneInfos[patch1].BindEdges[edge1].ZoneId = zoneId;
76
77 // Next
78 zoneInfos[patch0].BindEdges[edge0].Next[0] = patch1;
79 zoneInfos[patch1].BindEdges[edge1].Next[0] = patch0;
80
81 // Edge
82 zoneInfos[patch0].BindEdges[edge0].Edge[0] = edge1;
83 zoneInfos[patch1].BindEdges[edge1].Edge[0] = edge0;
84 }
85
86 // ***************************************************************************
87
88 void bind_1_2 (std::vector<CPatchInfo> &zoneInfos, uint patch, uint edge, uint patch0, uint edge0, uint patch1, uint edge1, uint zoneId)
89 {
90 // Bind type
91 zoneInfos[patch].BindEdges[edge].NPatchs = 2;
92 zoneInfos[patch0].BindEdges[edge0].NPatchs = 5;
93 zoneInfos[patch1].BindEdges[edge1].NPatchs = 5;
94
95 // Zone ID
96 zoneInfos[patch].BindEdges[edge].ZoneId = zoneId;
97 zoneInfos[patch0].BindEdges[edge0].ZoneId = zoneId;
98 zoneInfos[patch1].BindEdges[edge1].ZoneId = zoneId;
99
100 // Next
101 zoneInfos[patch].BindEdges[edge].Next[0] = patch0;
102 zoneInfos[patch].BindEdges[edge].Next[1] = patch1;
103 zoneInfos[patch0].BindEdges[edge0].Next[0] = patch;
104 zoneInfos[patch1].BindEdges[edge1].Next[0] = patch;
105
106 // Edge
107 zoneInfos[patch].BindEdges[edge].Edge[0] = edge0;
108 zoneInfos[patch].BindEdges[edge].Edge[1] = edge1;
109 zoneInfos[patch0].BindEdges[edge0].Edge[0] = edge;
110 zoneInfos[patch1].BindEdges[edge1].Edge[0] = edge;
111 }
112
113 // ***************************************************************************
114
115 void bind_1_4 (std::vector<CPatchInfo> &zoneInfos, uint patch, uint edge, uint patch0, uint edge0, uint patch1, uint edge1, uint patch2, uint edge2, uint patch3, uint edge3, uint zoneId)
116 {
117 // Bind type
118 zoneInfos[patch].BindEdges[edge].NPatchs = 4;
119 zoneInfos[patch0].BindEdges[edge0].NPatchs = 5;
120 zoneInfos[patch1].BindEdges[edge1].NPatchs = 5;
121 zoneInfos[patch2].BindEdges[edge2].NPatchs = 5;
122 zoneInfos[patch3].BindEdges[edge3].NPatchs = 5;
123
124 // Zone ID
125 zoneInfos[patch].BindEdges[edge].ZoneId = zoneId;
126 zoneInfos[patch0].BindEdges[edge0].ZoneId = zoneId;
127 zoneInfos[patch1].BindEdges[edge1].ZoneId = zoneId;
128 zoneInfos[patch2].BindEdges[edge2].ZoneId = zoneId;
129 zoneInfos[patch3].BindEdges[edge3].ZoneId = zoneId;
130
131 // Next
132 zoneInfos[patch].BindEdges[edge].Next[0] = patch0;
133 zoneInfos[patch].BindEdges[edge].Next[1] = patch1;
134 zoneInfos[patch].BindEdges[edge].Next[2] = patch2;
135 zoneInfos[patch].BindEdges[edge].Next[3] = patch3;
136 zoneInfos[patch0].BindEdges[edge0].Next[0] = patch;
137 zoneInfos[patch1].BindEdges[edge1].Next[0] = patch;
138 zoneInfos[patch2].BindEdges[edge2].Next[0] = patch;
139 zoneInfos[patch3].BindEdges[edge3].Next[0] = patch;
140
141 // Edge
142 zoneInfos[patch].BindEdges[edge].Edge[0] = edge0;
143 zoneInfos[patch].BindEdges[edge].Edge[1] = edge1;
144 zoneInfos[patch].BindEdges[edge].Edge[2] = edge2;
145 zoneInfos[patch].BindEdges[edge].Edge[3] = edge3;
146 zoneInfos[patch0].BindEdges[edge0].Edge[0] = edge;
147 zoneInfos[patch1].BindEdges[edge1].Edge[0] = edge;
148 zoneInfos[patch2].BindEdges[edge2].Edge[0] = edge;
149 zoneInfos[patch3].BindEdges[edge3].Edge[0] = edge;
150 }
151
152 // ***************************************************************************
153
154 /** Test whether 2 vertices could be welded */
155
156 static inline bool CanWeld(const CVector &v1, const CVector &v2, float weldThreshold)
157 {
158 return (v1 - v2).norm() < weldThreshold;
159 }
160
161 // ***************************************************************************
162
163 uint getOtherCountAndPos (const std::vector<CPatchInfo> &zoneInfo, uint patch, uint edge, uint &otherPos)
164 {
165 // Must be a multiple patch bind
166 if (zoneInfo[patch].BindEdges[edge].NPatchs == 5)
167 {
168 uint i;
169 const CPatchInfo &otherPatchRef = zoneInfo[zoneInfo[patch].BindEdges[edge].Next[0]];
170 uint otherEdge = zoneInfo[patch].BindEdges[edge].Edge[0];
171 for (i=0; i<otherPatchRef.BindEdges[otherEdge].NPatchs; i++)
172 {
173 if ( (otherPatchRef.BindEdges[otherEdge].Next[i] == patch) && (otherPatchRef.BindEdges[otherEdge].Edge[i] == edge) )
174 {
175 otherPos = i;
176 return otherPatchRef.BindEdges[otherEdge].NPatchs;
177 }
178 }
179 }
180 return 1;
181 }
182
183 // ***************************************************************************
184
185 /** Get all vertices that are near the given one */
186
187 static void GetCandidateVertices(const CVector &pos,
188 TPVQuadGrid &qg,
189 TPVVect &dest,
190 uint patchToExclude,
191 uint patchToExcludeZone,
192 float weldThreshold,
193 bool exclude
194 )
195 {
196 dest.clear();
197 const CVector half(weldThreshold, weldThreshold, weldThreshold);
198 float weldThresholdSrt = weldThreshold * weldThreshold;
199 qg.select(pos - half, pos + half);
200 for (TPVQuadGrid::CIterator it = qg.begin(); it != qg.end(); ++it)
201 {
202 if ( ::CanWeld((*it).Pos, pos, weldThreshold) )
203 {
204 if ( (!exclude) || (! ((*it).ZoneIndex == patchToExcludeZone && (*it).PatchIndex == patchToExclude) ) )
205 {
206 // Final distance test
207 if ( (pos - (*it).Pos).sqrnorm () <= weldThresholdSrt )
208 dest.push_back(&(*it));
209 }
210 }
211 }
212 }
213
214 // ***************************************************************************
215
216 bool isBinded (std::vector<CPatchInfo> &zoneInfos, uint patch0, uint edge0, uint patch1, uint edge1)
217 {
218 // Binded ?
219 if ( (zoneInfos[patch0].BindEdges[edge0].NPatchs != 0) && (zoneInfos[patch1].BindEdges[edge1].NPatchs != 0) )
220 {
221 // Binded ?
222 return (zoneInfos[patch0].BindEdges[edge0].Next[0] == patch1) ||
223 (zoneInfos[patch1].BindEdges[edge1].Next[0] == patch0);
224 }
225 return false;
226 }
227
228 // ***************************************************************************
229
230 CVector evalPatchEdge (CPatchInfo &patch, uint edge, float lambda)
231 {
232 // index of this border vertices
233 static const float indexToST[][2] = {{0, 0}, {0, 1}, {1, 1}, {1, 0}};
234 const uint vIndex[] = { edge, (edge + 1) & 0x03 };
235
236 return patch.Patch.eval((1.f - lambda) * indexToST[vIndex[0]][0] + lambda * indexToST[vIndex[1]][0],
237 (1.f - lambda) * indexToST[vIndex[0]][1] + lambda * indexToST[vIndex[1]][1]);
238 }
239
240 // ***************************************************************************
241
242 void getFirst (CVector &a, CVector &b, CVector &c, CVector &d)
243 {
244 // ab
245 CVector ab = (a+b)/2.f;
246
247 // bc
248 CVector bc = (b+c)/2.f;
249
250 // cd
251 CVector cd = (c+d)/2.f;
252
253 b = ab;
254 c = (ab + bc) / 2.f;
255 d = ( (bc + cd) / 2.f + c ) / 2.f;
256 }
257
258 // ***************************************************************************
259
260 void getSecond (CVector &a, CVector &b, CVector &c, CVector &d)
261 {
262 // ab
263 CVector ab = (a+b)/2.f;
264
265 // bc
266 CVector bc = (b+c)/2.f;
267
268 // cd
269 CVector cd = (c+d)/2.f;
270
271 c = cd;
272 b = (bc + cd) / 2.f;
273 a = ( (ab + bc) / 2.f + b ) / 2.f;
274 }
275
276 // ***************************************************************************
277
278 void CleanZone ( std::vector<CPatchInfo> &zoneInfos, uint zoneId, const CAABBoxExt &zoneBBox, float weldThreshold)
279 {
280 uint l, m, n, p, q; // some loop counters
281
282 ///////////////////////////////
283 // retrieve datas from zones //
284 ///////////////////////////////
285
286 // fill the quad grid
287 float zoneSize = 2.f * weldThreshold + std::max(zoneBBox.getMax().x - zoneBBox.getMin().x,
288 zoneBBox.getMax().y - zoneBBox.getMin().y);
289
290 TPVQuadGrid qg;
291 const uint numQGElt = 128;
292 qg.create (numQGElt, zoneSize / numQGElt);
293
294 for (l = 0; l < zoneInfos.size(); ++l)
295 {
296 CPatchInfo &patch = zoneInfos[l];
297 // for each base vertex of the patch
298 for (m = 0; m < 4; ++m)
299 {
300 CVector &pos = patch.Patch.Vertices[m];
301
302 // yes, insert it in the tree
303 const CVector half(weldThreshold, weldThreshold, weldThreshold);
304 qg.insert(pos - half, pos + half, CPatchVertexInfo(zoneId, l, m, pos));
305 }
306 }
307
308 /////////////////////////////////////////////////
309 // check whether each patch is correctly bound //
310 /////////////////////////////////////////////////
311 uint pass = 0;
312 while (1)
313 {
314 uint bind1Count = 0;
315 uint bind2Count = 0;
316 uint bind4Count = 0;
317 for (l = 0; l < zoneInfos.size(); ++l)
318 {
319 // Ref on patch
320 CPatchInfo &patch = zoneInfos[l];
321
322 // deals with each border
323 for (m = 0; m < 4; ++m)
324 {
325 const uint vIndex[] = { m, (m + 1) & 0x03 };
326
327 // if this border is said to be bound, no need to test..
328 if (patch.BindEdges[m].NPatchs == 0)
329 {
330 static TPVVect verts[2];
331
332 // Get vertices from other patch that could be welded with this patch boder's vertices.
333 for (q = 0; q < 2; ++q)
334 {
335 ::GetCandidateVertices(patch.Patch.Vertices[vIndex[q]], qg, verts[q], l, zoneId, weldThreshold, true);
336 }
337
338 uint bindCount;
339 for (bindCount = 1; bindCount<5; bindCount<<=1)
340 {
341 // Float middle
342 float middle = 1.f / (float)bindCount; // 0 = 0.5; 1 = 0.25
343
344 // Try to find a patch that shares 2 consecutives vertices
345 static TPVVect binded4[5];
346 binded4[0] = verts[0];
347 binded4[bindCount] = verts[1];
348
349 // Compute points along the border and found list of vertex binded to it.
350 float lambda = middle;
351 for (n = 1; n <bindCount; ++n)
352 {
353 CVector borderPos = evalPatchEdge (patch, m, lambda);
354 ::GetCandidateVertices(borderPos, qg, binded4[n], l, zoneId, weldThreshold, true);
355 lambda += middle;
356 }
357
358 // Binded patches and edges
359 uint neighborPatches[4];
360 uint neighborEdges[4];
361
362 // Patch binded
363 for (q = 0; q < bindCount; q++)
364 {
365 for (n = 0; n < binded4[q].size(); n++)
366 {
367 for (p = 0; p < binded4[q+1].size(); p++)
368 {
369 // Ref on the two patches
370 const CPatchVertexInfo &pv0 = *(binded4[q][n]);
371 const CPatchVertexInfo &pv1 = *(binded4[q+1][p]);
372
373 // Direct or indirect ?
374 // Vertex id
375 uint v0 = pv0.PatchVertex;
376 uint v1 = pv1.PatchVertex;
377 if ( pv0.ZoneIndex == pv1.ZoneIndex && pv0.PatchIndex == pv1.PatchIndex )
378 {
379 // Direct edge ?
380 if ( ( ( pv0.PatchVertex - pv1.PatchVertex) & 3 ) == 1 )
381 {
382 // Patch id
383 uint patchId2 = pv0.PatchIndex;
384
385 // Edge id
386 uint edge = v1;
387
388 // Edge not binded ?
389 if (zoneInfos[patchId2].BindEdges[edge].NPatchs == 0)
390 {
391 // Save the patch
392 neighborPatches[q] = patchId2;
393 neighborEdges[q] = edge;
394 goto exit24;
395 }
396 }
397 }
398 }
399 }
400 if (n == binded4[q].size())
401 // No bind found, stop
402 break;
403 exit24:;
404 }
405
406 // Find all binded patches ?
407 if (q == bindCount)
408 {
409 // Check The patches are binded together
410 for (q=0; q<bindCount-1; q++)
411 {
412 if (!isBinded (zoneInfos, neighborPatches[q], (neighborEdges[q]-1)&3, neighborPatches[q+1], (neighborEdges[q+1]+1)&3))
413 break;
414 }
415
416 // Not breaked ?
417 if (q == (bindCount-1) )
418 {
419 // Bind it
420 if (bindCount == 1)
421 {
422 bind_1_1 (zoneInfos, l, m, neighborPatches[0], neighborEdges[0], zoneId);
423 bind1Count++;
424 }
425 else if (bindCount == 2)
426 {
427 bind_1_2 (zoneInfos, l, m, neighborPatches[0], neighborEdges[0], neighborPatches[1], neighborEdges[1], zoneId);
428 bind2Count++;
429 }
430 else
431 {
432 bind_1_4 (zoneInfos, l, m, neighborPatches[0], neighborEdges[0], neighborPatches[1], neighborEdges[1],
433 neighborPatches[2], neighborEdges[2], neighborPatches[3], neighborEdges[3], zoneId);
434 bind4Count++;
435 }
436 // Exit connectivity loop
437 break;
438 }
439 }
440 }
441 }
442 }
443 }
444
445 // Print binds
446 if (bind1Count || bind2Count || bind4Count)
447 {
448 printf ("Internal bind pass %d: ", pass);
449 if (bind1Count)
450 printf ("bind1-1 %d; \n", bind1Count);
451 if (bind2Count)
452 printf ("bind1-2 %d; \n", bind2Count);
453 if (bind4Count)
454 printf ("bind1-4 %d; \n", bind4Count);
455 }
456 else
457 // No more bind, stop
458 break;
459
460 // Next pass
461 pass++;
462 }
463
464 // Insert vertex binded in the map
465 for (l = 0; l < zoneInfos.size(); ++l)
466 {
467 CPatchInfo &patch = zoneInfos[l];
468
469 // for each edge
470 int edge;
471 for (edge = 0; edge < 4; ++edge)
472 {
473 // Binded ?
474 uint bindCount = patch.BindEdges[edge].NPatchs;
475 if ( (bindCount == 2) || (bindCount == 4) )
476 {
477 // Start
478 float middle = 1.f / (float)bindCount; // 0 = 0.5; 1 = 0.25
479 float lambda = middle;
480
481 // For all binded vertices
482 uint vert;
483 for (vert = 1; vert < bindCount; vert++)
484 {
485 // Eval the binded position
486 CVector borderPos = evalPatchEdge (patch, edge, lambda);
487
488 // yes, insert it in the tree
489 const CVector half(weldThreshold, weldThreshold, weldThreshold);
490 qg.insert (borderPos - half, borderPos + half, CPatchVertexInfo(zoneId, l, 5, borderPos));
491
492 // New position
493 lambda += middle;
494 }
495 }
496 }
497 }
498
499 // Weld all the vertices !
500 uint weldCount = 0;
501 for (l = 0; l < zoneInfos.size(); ++l)
502 {
503 CPatchInfo &patch = zoneInfos[l];
504
505 // for each edge
506 int vert;
507 for (vert = 0; vert < 4; ++vert)
508 {
509 // Not on an opened edge ?
510 if ( (patch.BindEdges[vert].NPatchs != 0) && (patch.BindEdges[(vert-1)&3].NPatchs != 0) )
511 {
512 // Welded ?
513 bool welded = false;
514
515 // Get the vertex to weld
516 static TPVVect toWeld;
517 CVector pos = patch.Patch.Vertices[vert];
518 ::GetCandidateVertices (pos, qg, toWeld, l, zoneId, weldThreshold, false);
519
520 // Weld it
521 CVector average (0,0,0);
522 uint w;
523 bool absolutePosition = false;
524 for (w = 0; w < toWeld.size (); w++)
525 {
526 // Welded vertex ?
527 if (toWeld[w]->PatchVertex == 5)
528 {
529 absolutePosition = true;
530 average = toWeld[w]->Pos;
531 }
532
533 // Add it;
534 if (!absolutePosition)
535 average += toWeld[w]->Pos;
536
537 // Not the same ?
538 float dist = (pos - toWeld[w]->Pos).norm();
539 if ( (pos - toWeld[w]->Pos).sqrnorm() > 0.0001 )
540 welded = true;
541 }
542
543 // Average
544 if (!absolutePosition)
545 average /= (float)toWeld.size ();
546
547 // Weld ?
548 if (welded)
549 {
550 // Welded
551 weldCount++;
552
553 // Set the pos
554 for (w = 0; w < toWeld.size (); w++)
555 {
556 if (toWeld[w]->PatchVertex != 5)
557 {
558 toWeld[w]->Pos = average;
559 zoneInfos[toWeld[w]->PatchIndex].Patch.Vertices[toWeld[w]->PatchVertex] = average;
560 }
561 }
562 }
563 }
564 }
565 }
566
567 if (weldCount)
568 printf ("Internal vertices welded: %d\n", weldCount);
569
570 // Weld all the Tangents !
571 weldCount = 0;
572 for (l = 0; l < zoneInfos.size(); ++l)
573 {
574 CPatchInfo &patch = zoneInfos[l];
575
576 // for each edge
577 int edge;
578 for (edge = 0; edge < 4; ++edge)
579 {
580 // Binded ?
581 uint bindCount = patch.BindEdges[edge].NPatchs;
582 if ( /*(bindCount == 1) || */(bindCount == 5) )
583 {
584 // Neighbor patch
585 uint otherPatch = patch.BindEdges[edge].Next[0];
586 uint otherEdge = patch.BindEdges[edge].Edge[0];
587 nlassert (otherPatch<zoneInfos.size ());
588 nlassert (otherEdge<4);
589
590 // Get the vertices
591 CVector A, B, C, D;
592 A = zoneInfos[otherPatch].Patch.Vertices[otherEdge];
593 B = zoneInfos[otherPatch].Patch.Tangents[otherEdge*2];
594 C = zoneInfos[otherPatch].Patch.Tangents[otherEdge*2+1];
595 D = zoneInfos[otherPatch].Patch.Vertices[(otherEdge+1)&3];
596
597 // Pos
598 uint otherPos;
599 uint otherCount = getOtherCountAndPos (zoneInfos, l, edge, otherPos);
600 nlassert ( ( (bindCount == 1) && (otherCount == 1) ) || ( (bindCount == 5) && ( (otherCount == 2) || (otherCount == 4) ) ) );
601
602 // Calc tangents
603 if (otherCount == 2)
604 {
605 if (otherPos == 0)
606 getFirst (A, B, C, D);
607 else
608 getSecond (A, B, C, D);
609 }
610 else if (otherCount == 4)
611 {
612 if (otherPos == 0)
613 {
614 getFirst (A, B, C, D);
615 getFirst (A, B, C, D);
616 }
617 else if (otherPos == 1)
618 {
619 getFirst (A, B, C, D);
620 getSecond (A, B, C, D);
621 }
622 else if (otherPos == 2)
623 {
624 getSecond (A, B, C, D);
625 getFirst (A, B, C, D);
626 }
627 else if (otherPos == 3)
628 {
629 getSecond (A, B, C, D);
630 getSecond (A, B, C, D);
631 }
632 }
633
634 // 2 tangents
635 uint tang;
636 for (tang=0; tang<2; tang++)
637 {
638 nlassert (2*edge+tang < 8);
639
640 // Eval the binded position
641 const CVector &tangVect = (tang==0) ? C : B;
642
643 // Next offset
644 float dist = (patch.Patch.Tangents[2*edge+tang] - tangVect).norm();
645 if ( (patch.Patch.Tangents[2*edge+tang] - tangVect).sqrnorm() > 0.0001 )
646 weldCount++;
647
648 // Fix it!
649 if (bindCount == 1)
650 {
651 patch.Patch.Tangents[2*edge+tang] += tangVect;
652 patch.Patch.Tangents[2*edge+tang] /= 2;
653 }
654 else
655 patch.Patch.Tangents[2*edge+tang] = tangVect;
656 }
657 }
658 }
659 }
660
661 if (weldCount)
662 printf ("Internal tangents welded: %d\n", weldCount);
663 }