?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Merge branch 'main/rendor-staging' into fixes
[ryzomcore.git] / nel / src / 3d / packed_zone.cpp
blobfc8fa9a8a1813815b66d5af79b1be576ac42bccf
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) 2020 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
21
22 #include "std3d.h"
23 //
24 #include "nel/3d/packed_zone.h"
25 #include "nel/3d/driver.h"
26 #include "nel/3d/material.h"
27 //
28 #include "nel/misc/matrix.h"
29 #include "nel/misc/polygon.h"
30 #include "nel/misc/path.h"
31 #include "nel/misc/grid_traversal.h"
32 #include "nel/misc/bit_mem_stream.h"
33 //
34 #include <limits>
35 #include <iterator>
36 //
37
38
39 using namespace NLMISC;
40
41 #ifdef DEBUG_NEW
42 #define new DEBUG_NEW
43 #endif
44
45 namespace NL3D
46 {
47
48 #define PACKED_COL_RANGE 4095
49
50 class CVectorPacker
51 {
52 public:
53 struct CFormat
54 {
55 uint Rel0NumBits; // 2 for - 2 .. + 1 range
56 uint Rel1NumBits; // 4 for - 8 .. + 7 range
57 uint Rel2NumBits; // 8 for - 128 .. + 127 range
58 uint AbsNumBits; // num bits for absolute value
59 };
60 void serialPackedVector16(std::vector<uint16> &v, NLMISC::IStream &f, const CFormat &format);
61
62
63 private:
64 // format is stored as 2 bits at each entry
65 enum TFormat
66 {
67 Rel0 = 0, // - 2 .. + 1 range
68 Rel1 = 1, // - 8 .. + 7 range
69 Rel2 = 2, // - 128 .. + 127 range
70 AbsOrRLE = 3 // full precision absolute value
71 };
72 //
73 std::vector<sint32> _LastDeltas;
74 uint32 _LastTag;
75 uint _ReadIndex;
76 uint _Count[4]; // statistics
77 uint _Repeated[4]; // statistics
78 CFormat _Format;
79 private:
80 void bufferizeDelta(uint32 tag, sint32 delta, CBitMemStream &bits);
81 void flush(CBitMemStream &bits);
82 void writeSimpleValue(CBitMemStream &bits, sint32 delta);
83 void readSimpleValue(uint32 tag, std::vector<uint16> &v, CBitMemStream &bits);
84 static sint32 getMax(uint numBits)
85 {
86 return (uint32) ((1 << (numBits - 1)) - 1);
87 }
88 static sint32 getMin(uint numBits)
89 {
90 return (uint32) (0xfffffffe << (numBits - 2));
91 }
92 static void extendSign(uint numBits, uint32 &value)
93 {
94 if (value & (1 << (numBits - 1)))
95 {
96 value |= (uint32) (0xfffffffe << (numBits - 1));
97 }
98 }
99 };
100
101 // ********************************************************************************************
102 void CVectorPacker::writeSimpleValue(CBitMemStream &bits, sint32 delta)
103 {
104 uint32 croppedDelta = (uint32) delta;
105 switch(_LastTag)
106 {
107 case Rel0:
108 {
109 bits.serial(croppedDelta, _Format.Rel0NumBits);
110 }
111 break;
112 case Rel1:
113 {
114 bits.serial(croppedDelta, _Format.Rel1NumBits);
115 }
116 break;
117 case Rel2:
118 {
119 bits.serial(croppedDelta, _Format.Rel2NumBits);
120 }
121 break;
122 case AbsOrRLE:
123 {
124 // not a delta but a value ...
125 uint32 value = (uint16) delta;
126 bits.serial(value, _Format.AbsNumBits);
127 }
128 break;
129 default:
130 nlassert(0);
131 break;
132 }
133 if (_LastTag == AbsOrRLE)
134 {
135 //nlwarning("writing simple value %d (tag = %d)", (int) (uint16) delta, (int) _LastTag);
136 }
137 else
138 {
139 //nlwarning("writing simple delta %d (tag = %d)", (int) delta, (int) _LastTag);
140 }
141 ++ _Count[_LastTag];
142 }
143
144 // ********************************************************************************************
145 void CVectorPacker::readSimpleValue(uint32 tag, std::vector<uint16> &v, CBitMemStream &bits)
146 {
147 uint32 croppedDelta;
148 switch(tag)
149 {
150 case Rel0:
151 bits.serial(croppedDelta, _Format.Rel0NumBits);
152 extendSign(_Format.Rel0NumBits, croppedDelta);
153 v[_ReadIndex] = (uint16) (v[_ReadIndex - 1] + (sint16) croppedDelta);
154 break;
155 case Rel1:
156 bits.serial(croppedDelta, _Format.Rel1NumBits);
157 extendSign(_Format.Rel1NumBits, croppedDelta);
158 v[_ReadIndex] = (uint16) (v[_ReadIndex - 1] + (sint16) croppedDelta);
159 break;
160 case Rel2:
161 bits.serial(croppedDelta, _Format.Rel2NumBits);
162 extendSign(_Format.Rel2NumBits, croppedDelta);
163 v[_ReadIndex] = (uint16) (v[_ReadIndex - 1] + (sint16) croppedDelta);
164 break;
165 default:
166 nlassert(0);
167 break;
168 }
169 //nlwarning("reading simple delta %d (tag = %d)", (int) (v[_ReadIndex] - v[_ReadIndex - 1]), (int) tag);
170 ++ _ReadIndex;
171 }
172
173 // ********************************************************************************************
174 void CVectorPacker::flush(CBitMemStream &bits)
175 {
176 if (_LastDeltas.empty()) return;
177 if (_LastDeltas.size() > 4)
178 {
179 // put a 'repeat tag'
180 uint32 repeatTag = AbsOrRLE;
181 bits.serial(repeatTag, 2);
182 uint32 isRLE = 1;
183 bits.serial(isRLE, 1);
184 bits.serial(_LastTag, 2);
185 nlassert(_LastDeltas.size() <= 255);
186 uint8 length = (uint8)_LastDeltas.size();
187 //nlwarning("begin RLE, length = %d, tag = %d", (int) length, (int) repeatTag);
188 bits.serial(length);
189 for(uint k = 0; k < _LastDeltas.size(); ++k)
190 {
191 writeSimpleValue(bits, _LastDeltas[k]);
192 }
193 _LastDeltas.clear();
194 ++_Repeated[_LastTag];
195 }
196 else
197 {
198 // flush separate values
199 for(uint k = 0; k < _LastDeltas.size(); ++k)
200 {
201 //nlwarning("write single value tag %d", (int) _LastTag);
202 bits.serial(_LastTag, 2);
203 if (_LastTag == (uint32) AbsOrRLE)
204 {
205 uint32 isRLE = 0;
206 bits.serial(isRLE, 1);
207 }
208 writeSimpleValue(bits, _LastDeltas[k]);
209 }
210 _LastDeltas.clear();
211 }
212 }
213
214 // ********************************************************************************************
215 void CVectorPacker::bufferizeDelta(uint32 tag, sint32 delta, CBitMemStream &bits)
216 {
217 if (tag != _LastTag || _LastDeltas.size() == 255)
218 {
219 flush(bits);
220 _LastTag = tag;
221 }
222 _LastDeltas.push_back(delta);
223 }
224
225 // ********************************************************************************************
226 void CVectorPacker::serialPackedVector16(std::vector<uint16> &v,NLMISC::IStream &f, const CFormat &format)
227 {
228 _Format = format;
229 if (f.isReading())
230 {
231 CBitMemStream bits(true);
232 std::vector<uint8> datas;
233 f.serialCont(datas);
234 bits.fill(&datas[0], (uint32)datas.size());
235 uint32 numValues = 0;
236 bits.serial(numValues);
237 v.resize(numValues);
238 _ReadIndex = 0;
239 while (_ReadIndex != numValues)
240 {
241 if (_ReadIndex == 0)
242 {
243 uint32 value;
244 bits.serial(value, _Format.AbsNumBits);
245 v[0] = (uint16) value;
246 //nlwarning("v[0] = %d", (int) v[0]);
247 ++ _ReadIndex;
248 }
249 else
250 {
251 uint32 tag;
252 bits.serial(tag, 2);
253 //nlwarning("read tag %d", (int) tag);
254 switch(tag)
255 {
256
257 case Rel0:
258 case Rel1:
259 case Rel2:
260 readSimpleValue(tag, v, bits);
261 break;
262 case AbsOrRLE:
263 {
264 // serial one more bit to see if there's RLE here
265 uint32 isRLE = 0;
266 bits.serial(isRLE, 1);
267 if (isRLE)
268 {
269 uint32 repeatTag;
270 bits.serial(repeatTag, 2);
271 uint8 length = 0;
272 bits.serial(length);
273 //nlwarning("begin RLE, length = %d", (int) length);
274 for(uint l = 0; l < length; ++l)
275 {
276 switch(repeatTag)
277 {
278 case Rel0:
279 case Rel1:
280 case Rel2:
281 readSimpleValue(repeatTag, v, bits);
282 break;
283 case AbsOrRLE:
284 uint32 value;
285 bits.serial(value, _Format.AbsNumBits);
286 v[_ReadIndex] = (uint16) value;
287 //nlwarning("reading abs 16 value : %d", (int) v[_ReadIndex]);
288 ++ _ReadIndex;
289 break;
290 default:
291 throw NLMISC::EInvalidDataStream();
292 break;
293 }
294 }
295 }
296 else
297 {
298 // absolute value
299 uint32 value = 0;
300 bits.serial(value, _Format.AbsNumBits);
301 v[_ReadIndex] = (uint16) value;
302 //nlwarning("reading abs 16 value : %d", (int) v[_ReadIndex]);
303 ++ _ReadIndex;
304 }
305 }
306 break;
307 }
308 }
309 }
310 }
311 else
312 {
313 _Count[Rel0] = 0;
314 _Count[Rel1] = 0;
315 _Count[Rel2] = 0;
316 _Count[AbsOrRLE] = 0;
317 _Repeated[Rel0] = 0;
318 _Repeated[Rel1] = 0;
319 _Repeated[Rel2] = 0;
320 _Repeated[AbsOrRLE] = 0;
321 //
322 CBitMemStream bits(false);
323 uint32 numValues = (uint32)v.size();
324 bits.serial(numValues);
325 _LastTag = std::numeric_limits<uint32>::max();
326 _LastDeltas.clear();
327 for(uint k = 0; k < v.size(); ++k)
328 {
329 if (k == 0)
330 {
331 uint32 value = v[0];
332 bits.serial(value, _Format.AbsNumBits);
333 //nlwarning("v[0] = %d", (int) v[0]);
334 }
335 else
336 {
337 sint32 delta = v[k] - v[k - 1];
338 if (delta >= getMin(_Format.Rel0NumBits) && delta <= getMax(_Format.Rel0NumBits))
339 {
340 bufferizeDelta(Rel0, delta, bits);
341 }
342 else if (delta >= getMin(_Format.Rel1NumBits) && delta <= getMax(_Format.Rel1NumBits))
343 {
344 bufferizeDelta(Rel1, delta, bits);
345 }
346 else if (delta >= getMin(_Format.Rel2NumBits) && delta <= getMax(_Format.Rel2NumBits))
347 {
348 bufferizeDelta(Rel2, delta, bits);
349 }
350 else
351 {
352 bufferizeDelta(AbsOrRLE, v[k], bits); // absolute value here ...
353 }
354 }
355 }
356 flush(bits);
357 std::vector<uint8> datas(bits.buffer(), bits.buffer() + bits.length());
358 f.serialCont(datas);
359 /*
360 if (_Count[Rel0] != 0 || _Count[Rel1] != 0 || _Count[Rel2] != 0 || _Count[AbsOrRLE] != 0)
361 {
362 nlwarning("count0 = %d", _Count[Rel0]);
363 nlwarning("count1 = %d", _Count[Rel1]);
364 nlwarning("count2 = %d", _Count[Rel2]);
365 nlwarning("countAbs = %d", _Count[AbsOrRLE]);
366 nlwarning("*");
367 nlwarning("repeat 0 = %d", _Repeated[Rel0]);
368 nlwarning("repeat 1 = %d", _Repeated[Rel1]);
369 nlwarning("repeat 2 = %d", _Repeated[Rel2]);
370 nlwarning("repeat Abs = %d", _Repeated[AbsOrRLE]);
371 nlwarning("*");
372 }
373 */
374 }
375 }
376
377
378
379 // helper function : serialize a uint16 vector
380 void serialPackedVector16(std::vector<uint16> &v, NLMISC::IStream &f)
381 {
382 CVectorPacker packer;
383 CVectorPacker::CFormat format;
384 format.Rel0NumBits = 2;
385 format.Rel1NumBits = 4;
386 format.Rel2NumBits = 8;
387 format.AbsNumBits = 16;
388 packer.serialPackedVector16(v, f, format);
389 /*
390 if (!v.empty())
391 {
392 nlwarning("*");
393 uint num = std::min((uint) v.size(), (uint) 1000);
394 for(uint k = 0; k < num; ++k)
395 {
396 nlwarning("[%d] = %d", (int) k, (int) v[k]);
397 }
398 nlwarning("*");
399 }
400 */
401 }
402
403
404 void serialPackedVector12(std::vector<uint16> &v, NLMISC::IStream &f)
405 {
406 CVectorPacker packer;
407 CVectorPacker::CFormat format;
408 format.Rel0NumBits = 2;
409 format.Rel1NumBits = 6;
410 format.Rel2NumBits = 9;
411 format.AbsNumBits = 12;
412 packer.serialPackedVector16(v, f, format);
413 /*
414 if (!v.empty())
415 {
416 nlwarning("*");
417 uint num = std::min((uint) v.size(), (uint) 1000);
418 for(uint k = 0; k < num; ++k)
419 {
420 nlwarning("[%d] = %d", (int) k, (int) v[k]);
421 }
422 nlwarning("*");
423 }
424 */
425 }
426
427 // some function to ease writing of some primitives into a vertex buffer
428 static inline void pushVBLine2D(NLMISC::CVector *&dest, const NLMISC::CVector &v0, const NLMISC::CVector &v1)
429 {
430 dest->x = v0.x;
431 dest->y = v0.y;
432 dest->z = -0.5f;
433 ++ dest;
434 dest->x = v1.x;
435 dest->y = v1.y;
436 dest->z = -0.5f;
437 ++ dest;
438 dest->x = v0.x;
439 dest->y = v0.y;
440 dest->z = -0.5f;
441 ++ dest;
442 }
443
444 static inline void pushVBTri2D(NLMISC::CVector *&dest, const NLMISC::CTriangle &tri)
445 {
446 dest->x = tri.V0.x;
447 dest->y = tri.V0.y;
448 dest->z = -0.5f;
449 ++ dest;
450 dest->x = tri.V1.x;
451 dest->y = tri.V1.y;
452 dest->z = -0.5f;
453 ++ dest;
454 dest->x = tri.V2.x;
455 dest->y = tri.V2.y;
456 dest->z = -0.5f;
457 ++ dest;
458 }
459
460
461 static inline void pushVBQuad2D(NLMISC::CVector *&dest, const NLMISC::CQuad &quad)
462 {
463 dest->x = quad.V0.x;
464 dest->y = quad.V0.y;
465 dest->z = -0.5f;
466 ++ dest;
467 dest->x = quad.V1.x;
468 dest->y = quad.V1.y;
469 dest->z = -0.5f;
470 ++ dest;
471 dest->x = quad.V2.x;
472 dest->y = quad.V2.y;
473 dest->z = -0.5f;
474 ++ dest;
475 dest->x = quad.V3.x;
476 dest->y = quad.V3.y;
477 dest->z = -0.5f;
478 ++ dest;
479 }
480
481 static inline void pushVBQuad(NLMISC::CVector *&dest, const NLMISC::CQuad &quad)
482 {
483 *dest++ = quad.V0;
484 *dest++ = quad.V1;
485 *dest++ = quad.V2;
486 *dest++ = quad.V3;
487 }
488
489
490 // compute rasters union.
491 static void computeRastersUnion(const CPolygon2D::TRasterVect &inRaster0, CPolygon2D::TRasterVect &inRaster1, sint minY0, sint minY1,
492 CPolygon2D::TRasterVect &outRaster, sint &finalMinY)
493 {
494 if (inRaster0.empty())
495 {
496 if (inRaster1.empty())
497 {
498 outRaster.clear();
499 finalMinY = -1;
500 return;
501 }
502 outRaster = inRaster1;
503 finalMinY = minY1;
504 return;
505 }
506 else if (inRaster1.empty())
507 {
508 outRaster = inRaster0;
509 finalMinY = minY0;
510 return;
511 }
512 nlassert(&outRaster != &inRaster0);
513 nlassert(&outRaster != &inRaster1);
514 finalMinY = std::min(minY0, minY1);
515 sint maxY = std::max(minY0 + (sint) inRaster0.size(), minY1 + (sint) inRaster1.size());
516 outRaster.resize(maxY - finalMinY);
517 for(sint y = 0; y < (sint) outRaster.size(); ++y)
518 {
519 outRaster[y].first = INT_MAX;
520 outRaster[y].second = INT_MIN;
521 sint raster0Y = y + finalMinY - minY0;
522 if (raster0Y >= 0 && raster0Y < (sint) inRaster0.size())
523 {
524 //if (inRaster0[raster0Y].second >= inRaster0[raster0Y].first)
525 {
526 outRaster[y].first = std::min(outRaster[y].first, inRaster0[raster0Y].first);
527 outRaster[y].second = std::max(outRaster[y].second, inRaster0[raster0Y].second);
528 }
529 }
530 sint raster1Y = y + finalMinY - minY1;
531 if (raster1Y >= 0 && raster1Y < (sint) inRaster1.size())
532 {
533 //if (inRaster1[raster1Y].second >= inRaster1[raster1Y].first)
534 {
535 outRaster[y].first = std::min(outRaster[y].first, inRaster1[raster1Y].first);
536 outRaster[y].second = std::max(outRaster[y].second, inRaster1[raster1Y].second);
537 }
538 }
539 }
540 }
541
542 static void addQuadToSilhouette(const CVector &v0, const CVector &v1, const CVector &v2, CVector &v3, CPolygon2D::TRasterVect &sil, sint &minY, float cellSize)
543 {
544 static CPolygon2D quad;
545 quad.Vertices.resize(4);
546 quad.Vertices[0] = v0 / cellSize;
547 quad.Vertices[1] = v1 / cellSize;
548 quad.Vertices[2] = v2 / cellSize;
549 quad.Vertices[3] = v3 / cellSize ;
550 //
551 static CPolygon2D::TRasterVect newQuad;
552 static CPolygon2D::TRasterVect result;
553 sint newMinY = -1;
554 sint resultMinY;
555 quad.computeOuterBorders(newQuad, newMinY);
556 computeRastersUnion(sil, newQuad, minY, newMinY, result, resultMinY);
557 minY = resultMinY;
558 sil.swap(result);
559 }
560
561 uint16 CPackedZone16::UndefIndex = 0xffff;
562
563 // ***************************************************************************************
564 CPackedZone16::CPackedZone16()
565 {
566 CellSize = 0.f;
567 _Origin = CVector::Null;
568 }
569
570 // ***************************************************************************************
571 void CPackedZone32::unpackTri(const CPackedTri &src, CVector dest[3]) const
572 {
573 // TODO: add 'multiply-add' operator
574 dest[0].set(Verts[src.V0].X * _PackedLocalToWorld.x + _Origin.x,
575 Verts[src.V0].Y * _PackedLocalToWorld.y + _Origin.y,
576 Verts[src.V0].Z * _PackedLocalToWorld.z + _Origin.z);
577 dest[1].set(Verts[src.V1].X * _PackedLocalToWorld.x + _Origin.x,
578 Verts[src.V1].Y * _PackedLocalToWorld.y + _Origin.y,
579 Verts[src.V1].Z * _PackedLocalToWorld.z + _Origin.z);
580 dest[2].set(Verts[src.V2].X * _PackedLocalToWorld.x + _Origin.x,
581 Verts[src.V2].Y * _PackedLocalToWorld.y + _Origin.y,
582 Verts[src.V2].Z * _PackedLocalToWorld.z + _Origin.z);
583
584 }
585
586 uint32 CPackedZone32::UndefIndex = 0xffffffff;
587
588 // ***************************************************************************************
589 CPackedZone32::CPackedZone32()
590 {
591 CellSize = 0;
592 _Origin = CVector::Null;
593 }
594
595 // ***************************************************************************************
596 void CPackedZone32::serial(NLMISC::IStream &f)
597 {
598 f.serialVersion(0);
599 f.serial(Box);
600 f.serialCont(Verts);
601 f.serialCont(Tris);
602 f.serialCont(TriLists);
603 f.serial(Grid);
604 f.serial(CellSize);
605 f.serial(_Origin);
606 f.serial(_WorldToLocal);
607 f.serial(ZoneX);
608 f.serial(ZoneY);
609 if (f.isReading())
610 {
611 _PackedLocalToWorld.set(1.f / (_WorldToLocal.x * (float) PACKED_COL_RANGE),
612 1.f / (_WorldToLocal.y * (float) PACKED_COL_RANGE),
613 1.f / (_WorldToLocal.z * (float) PACKED_COL_RANGE));
614 }
615 }
616
617 // used by CPackedZone::build
618 struct CZoneInstance
619 {
620 const CShapeInfo *SI;
621 CMatrix WorldMat;
622 };
623
624 // ***************************************************************************************
625 void CPackedZone32::build(std::vector<const CTessFace*> &leaves,
626 float cellSize,
627 std::vector<CInstanceGroup *> igs,
628 const TShapeCache &shapeCache,
629 const NLMISC::CAABBox &baseZoneBBox,
630 sint32 zoneX,
631 sint32 zoneY
632 )
633 {
634 nlassert(cellSize > 0);
635 Verts.clear();
636 Tris.clear();
637 TriLists.clear();
638 Grid.clear();
639 if (leaves.empty()) return;
640 for(uint k = 0; k < leaves.size(); ++k)
641 {
642 if (k == 0)
643 {
644 Box.setMinMax(leaves[k]->VBase->EndPos, leaves[k]->VBase->EndPos);
645 Box.extend(leaves[k]->VLeft->EndPos);
646 Box.extend(leaves[k]->VRight->EndPos);
647 }
648 else
649 {
650 Box.extend(leaves[k]->VBase->EndPos);
651 Box.extend(leaves[k]->VLeft->EndPos);
652 Box.extend(leaves[k]->VRight->EndPos);
653 }
654 }
655 CAABBox landBBox = Box;
656 landBBox.extend(baseZoneBBox.getMin());
657 landBBox.extend(baseZoneBBox.getMax());
658 // list of instances that contribute to that zone
659 std::vector<CZoneInstance> instances;
660 // extends with instances that intersect the land bbox with respect to x/y
661 for(uint k = 0; k < igs.size(); ++k)
662 {
663 if (!igs[k]) continue;
664 for(uint l = 0; l < igs[k]->getNumInstance(); ++l)
665 {
666 CMatrix instanceMatrix;
667 igs[k]->getInstanceMatrix(l, instanceMatrix);
668 if (NLMISC::toLowerAscii(NLMISC::CFile::getExtension(igs[k]->getShapeName(l))) == "pacs_prim") continue;
669 std::string stdShapeName = standardizeShapeName(igs[k]->getShapeName(l));
670 TShapeCache::const_iterator it = shapeCache.find(stdShapeName);
671 if (it != shapeCache.end())
672 {
673 CAABBox xformBBox = CAABBox::transformAABBox(instanceMatrix, it->second.LocalBBox);
674 if (xformBBox.getMin().x < landBBox.getMax().x &&
675 xformBBox.getMin().y < landBBox.getMax().y &&
676 xformBBox.getMax().y >= landBBox.getMin().y &&
677 xformBBox.getMax().x >= landBBox.getMin().x)
678 {
679 Box.extend(xformBBox.getMin());
680 Box.extend(xformBBox.getMax());
681 CZoneInstance zi;
682 zi.SI = &(it->second);
683 zi.WorldMat = instanceMatrix;
684 instances.push_back(zi);
685 }
686 }
687 }
688 }
689 //
690 /*float delta = 5.f;
691 Box.extend(Box.getMin() + CVector(- delta, - delta, - delta));
692 Box.extend(Box.getMax() + CVector(delta, delta, delta));*/
693 //
694 CVector cornerMin = Box.getMin();
695 CVector cornerMax = Box.getMax();
696 //
697 uint width = (uint) ceilf((cornerMax.x - cornerMin.x) / cellSize);
698 uint height = (uint) ceilf((cornerMax.y - cornerMin.y) / cellSize);
699 float depth = cornerMax.z - cornerMin.z;
700 if (width == 0 || height == 0) return;
701 Grid.init(width, height, UndefIndex);
702 //
703 TVertexGrid vertexGrid; // grid for fast sharing of vertices
704 TTriListGrid triListGrid; // grid for list of tris per grid cell (before packing in a single vector)
705 vertexGrid.init(width, height);
706 triListGrid.init(width, height);
707 CellSize = cellSize;
708 //
709 _Origin = cornerMin;
710 _WorldToLocal.x = 1.f / (width * cellSize);
711 _WorldToLocal.y = 1.f / (height * cellSize);
712 _WorldToLocal.z = depth != 0 ? 1.f / depth : 0.f;
713 //
714 for(uint k = 0; k < leaves.size(); ++k)
715 {
716 CTriangle tri;
717 tri.V0 = leaves[k]->VBase->EndPos;
718 tri.V1 = leaves[k]->VLeft->EndPos;
719 tri.V2 = leaves[k]->VRight->EndPos;
720 addTri(tri, vertexGrid, triListGrid);
721 }
722 // add each ig
723 for(uint k = 0; k < instances.size(); ++k)
724 {
725 addInstance(*instances[k].SI, instances[k].WorldMat, vertexGrid, triListGrid);
726 }
727 // pack tri lists
728 for (uint y = 0; y < height; ++y)
729 {
730 for (uint x = 0; x < width; ++x)
731 {
732 if (!triListGrid(x, y).empty())
733 {
734 Grid(x, y) = (uint32)TriLists.size();
735 std::copy(triListGrid(x, y).begin(), triListGrid(x, y).end(), std::back_inserter(TriLists));
736 TriLists.push_back(UndefIndex); // mark the end of the list
737 }
738 }
739 }
740 //
741 ZoneX = zoneX;
742 ZoneX = zoneY;
743 //
744 _PackedLocalToWorld.set(1.f / (_WorldToLocal.x * (float) PACKED_COL_RANGE),
745 1.f / (_WorldToLocal.y * (float) PACKED_COL_RANGE),
746 1.f / (_WorldToLocal.z * (float) PACKED_COL_RANGE));
747 // reorder vertices by distance for better compression : start with first vertex then found closest vertex
748 //
749 /*
750 std::vector<uint32> triRemapping(Verts.size());
751 std::vector<uint32> vertRemapping(Verts.size());
752 std::vector<uint32> todo(Verts.size());
753 for(uint k = 0; k < Verts.size(); ++k)
754 {
755 todo[k] = k;
756 }
757 CPackedVertex lastPos;
758 for(uint k = 0; k < Verts.size(); ++k)
759 {
760 // find vertex with closest dist
761 uint best;
762 if (k == 0)
763 {
764 best = 0;
765 }
766 else
767 {
768 uint32 bestDist = INT_MAX;
769 for(uint l = 0; l < todo.size(); ++l)
770 {
771 uint32 dist = (uint32) abs((sint32) Verts[todo[l]].X - (sint32) lastPos.X)
772 + (uint32) abs((sint32) Verts[todo[l]].Y - (sint32) lastPos.Y)
773 + (uint32) abs((sint32) Verts[todo[l]].Z - (sint32) lastPos.Z);
774 if (dist < bestDist)
775 {
776 bestDist = dist;
777 best = l;
778 }
779 }
780 }
781 lastPos = Verts[todo[best]];
782 vertRemapping[k] = todo[best];
783 triRemapping[todo[best]] = k;
784 todo[best] = todo[todo.size() - 1];
785 todo.pop_back();
786 }
787 // remap all tris
788 for(uint k = 0; k < Tris.size(); ++k)
789 {
790 Tris[k].V0 = triRemapping[Tris[k].V0];
791 Tris[k].V1 = triRemapping[Tris[k].V1];
792 Tris[k].V2 = triRemapping[Tris[k].V2];
793 }
794 // reorder vertices
795 std::vector<CPackedVertex> remappedVerts(Verts.size());
796 for(uint k = 0; k < Verts.size(); ++k)
797 {
798 remappedVerts[k] = Verts[vertRemapping[k]];
799 }
800 Verts.swap(remappedVerts);
801 /////////////////////////////////////////////////////////////////////
802 // reorder tris
803 triRemapping.resize(Tris.size());
804 std::vector<uint32> triListRemapping(Tris.size());
805 //
806 todo.resize(Tris.size());
807 for(uint k = 0; k < Tris.size(); ++k)
808 {
809 todo[k] = k;
810 }
811 uint32 lastIndex = 0;
812 for(uint k = 0; k < Tris.size(); ++k)
813 {
814 uint32 best = 0;
815 uint32 bestScore = INT_MAX;
816 for(uint l = 0; l < todo.size(); ++l)
817 {
818 uint32 score = abs(Tris[todo[l]].V0 - lastIndex) +
819 abs(Tris[todo[l]].V1 - Tris[todo[l]].V0) +
820 abs(Tris[todo[l]].V2 - Tris[todo[l]].V1);
821 if (score < bestScore)
822 {
823 bestScore = score;
824 best = l;
825 }
826 }
827 lastIndex = Tris[todo[best]].V2;
828 triRemapping[k] = todo[best];
829 triListRemapping[todo[best]] = k;
830 todo[best] = todo[todo.size() - 1];
831 todo.pop_back();
832 }
833 // remap tri lists
834 for(uint k = 0; k < TriLists.size(); ++k)
835 {
836 if (TriLists[k] != std::numeric_limits<uint32>::max())
837 {
838 TriLists[k] = triListRemapping[TriLists[k]];
839 }
840 }
841 // reorder tris
842 std::vector<CPackedTri> remappedTris(Tris.size());
843 for(uint k = 0; k < Tris.size(); ++k)
844 {
845 remappedTris[k] = Tris[triRemapping[k]];
846 }
847 Tris.swap(remappedTris);
848 */
849
850 // reorder tri lists for better compression
851 std::vector<uint32>::iterator firstIt = TriLists.begin();
852 std::vector<uint32>::iterator currIt = firstIt;
853 std::vector<uint32>::iterator lastIt = TriLists.end();
854
855 while (currIt != lastIt)
856 {
857 if (*currIt == UndefIndex)
858 {
859 std::sort(firstIt, currIt);
860 ++ currIt;
861 if (currIt == lastIt) break;
862 firstIt = currIt;
863 }
864 else
865 {
866 ++ currIt;
867 }
868 }
869 //
870 /*int vertsSize = sizeof(CPackedVertex) * Verts.size();
871 int trisSize = sizeof(CPackedTri) * Tris.size();
872 int triListSize = sizeof(uint32) * TriLists.size();
873 int gridSize = sizeof(uint32) * Grid.getWidth() * Grid.getHeight();
874 */
875 /*printf("Verts Size = %d\n", vertsSize);
876 printf("Tris Size = %d\n", trisSize);
877 printf("Tri List Size = %d\n", triListSize);
878 printf("Grid size = %d\n", gridSize);
879 printf("Total = %d\n", vertsSize + trisSize + triListSize + gridSize);*/
880 }
881
882 // ***************************************************************************************
883 void CPackedZone32::addTri(const CTriangle &tri, TVertexGrid &vertexGrid, TTriListGrid &triListGrid)
884 {
885 CPackedTri pt;
886 pt.V0 = allocVertex(tri.V0, vertexGrid);
887 pt.V1 = allocVertex(tri.V1, vertexGrid);
888 pt.V2 = allocVertex(tri.V2, vertexGrid);
889
890 //
891 static CPolygon2D::TRasterVect rasters;
892 static CPolygon2D polyTri;
893 sint minY;
894 polyTri.Vertices.resize(3);
895 //
896 polyTri.Vertices[0].set((tri.V0.x - _Origin.x) / CellSize, (tri.V0.y - _Origin.y) / CellSize);
897 polyTri.Vertices[1].set((tri.V1.x - _Origin.x) / CellSize, (tri.V1.y - _Origin.y) / CellSize);
898 polyTri.Vertices[2].set((tri.V2.x - _Origin.x) / CellSize, (tri.V2.y - _Origin.y) / CellSize);
899 //
900 polyTri.computeOuterBorders(rasters, minY);
901 if (rasters.empty()) return;
902 Tris.push_back(pt);
903 //
904 for (sint y = 0; y < (sint) rasters.size(); ++y)
905 {
906 sint gridY = y + minY;
907 if (gridY < 0) continue;
908 if (gridY >= (sint) triListGrid.getHeight()) break;
909 for (sint x = rasters[y].first; x <= rasters[y].second; ++x)
910 {
911 if (x < 0) continue;
912 if (x >= (sint) triListGrid.getWidth()) break;
913 triListGrid(x, gridY).push_back((uint32)Tris.size() - 1);
914 }
915 }
916 }
917
918
919
920 // ***************************************************************************************
921 uint32 CPackedZone32::allocVertex(const CVector &src, TVertexGrid &vertexGrid)
922 {
923 CVector local((src.x - _Origin.x) * _WorldToLocal.x,
924 (src.y - _Origin.y) * _WorldToLocal.y,
925 (src.z - _Origin.z) * _WorldToLocal.z);
926 sint x = (sint) (local.x * vertexGrid.getWidth());
927 sint y = (sint) (local.y * vertexGrid.getHeight());
928 if (x == (sint) vertexGrid.getWidth()) x = (sint) vertexGrid.getWidth() - 1;
929 if (y == (sint) vertexGrid.getHeight()) y = (sint) vertexGrid.getHeight() - 1;
930 //
931 CPackedVertex pv;
932 sint32 ix = (sint32) (local.x * PACKED_COL_RANGE);
933 sint32 iy = (sint32) (local.y * PACKED_COL_RANGE);
934 sint32 iz = (sint32) (local.z * PACKED_COL_RANGE);
935 clamp(ix, 0, PACKED_COL_RANGE);
936 clamp(iy, 0, PACKED_COL_RANGE);
937 clamp(iz, 0, PACKED_COL_RANGE);
938 pv.X = (uint16) ix;
939 pv.Y = (uint16) iy;
940 pv.Z = (uint16) iz;
941 //
942 std::list<uint32> &vertList = vertexGrid(x, y);
943 for(std::list<uint32>::iterator it = vertexGrid(x, y).begin(); it != vertexGrid(x, y).end(); ++it)
944 {
945 if (Verts[*it] == pv) return *it; // exists already
946 }
947
948
949 // create a new vertex
950 Verts.push_back(pv);
951 vertList.push_front((uint32)Verts.size() - 1);
952 return (uint32)Verts.size() - 1;
953 }
954
955 // ***************************************************************************************
956 void CPackedZone32::render(CVertexBuffer &vb, IDriver &drv, CMaterial &material, CMaterial &wiredMaterial, const CMatrix &camMat, uint batchSize, const CVector localFrustCorners[8])
957 {
958 if (Tris.empty()) return;
959 IDriver::TPolygonMode oldPolygonMode = drv.getPolygonMode();
960 //
961 CVector frustCorners[8];
962 for(uint k = 0; k < sizeofarray(frustCorners); ++k)
963 {
964 frustCorners[k] = camMat * localFrustCorners[k];
965 frustCorners[k].x -= _Origin.x;
966 frustCorners[k].y -= _Origin.y;
967 }
968 // project frustum on x/y plane to see where to test polys
969 sint minY = INT_MAX;
970 static CPolygon2D::TRasterVect silhouette;
971 silhouette.clear();
972 addQuadToSilhouette(frustCorners[0], frustCorners[1], frustCorners[2], frustCorners[3], silhouette, minY, CellSize);
973 addQuadToSilhouette(frustCorners[1], frustCorners[5], frustCorners[6], frustCorners[2], silhouette, minY, CellSize);
974 addQuadToSilhouette(frustCorners[4], frustCorners[5], frustCorners[6], frustCorners[7], silhouette, minY, CellSize);
975 addQuadToSilhouette(frustCorners[0], frustCorners[4], frustCorners[7], frustCorners[3], silhouette, minY, CellSize);
976 addQuadToSilhouette(frustCorners[0], frustCorners[1], frustCorners[5], frustCorners[4], silhouette, minY, CellSize);
977 addQuadToSilhouette(frustCorners[3], frustCorners[7], frustCorners[6], frustCorners[2], silhouette, minY, CellSize);
978 //
979 {
980 CVertexBufferReadWrite vba;
981 vb.setNumVertices(batchSize * 3);
982 vb.lock(vba);
983 CVector *dest = vba.getVertexCoordPointer(0);
984 const CVector *endDest = dest + batchSize * 3;
985 for(sint y = 0; y < (sint) silhouette.size(); ++y)
986 {
987 sint gridY = y + minY;
988 if (gridY < 0) continue;
989 if (gridY >= (sint) Grid.getHeight()) continue;
990 sint minX = silhouette[y].first;
991 sint maxX = silhouette[y].second;
992 for (sint x = minX; x <= maxX; ++x)
993 {
994 if (x < 0) continue;
995 if (x >= (sint) Grid.getWidth()) break;
996 uint32 triRefIndex = Grid(x, gridY);
997 if (triRefIndex == UndefIndex) continue;
998 for (;;)
999 {
1000 uint32 triIndex = TriLists[triRefIndex];
1001 if (triIndex == UndefIndex) break; // end of list
1002 unpackTri(Tris[triIndex], dest);
1003 dest += 3;
1004 if (dest == endDest)
1005 {
1006 // flush batch
1007 vba.unlock();
1008 drv.setPolygonMode(IDriver::Filled);
1009 drv.activeVertexBuffer(vb);
1010 drv.renderRawTriangles(material, 0, batchSize);
1011 drv.setPolygonMode(IDriver::Line);
1012 //drv.renderRawTriangles(wiredMaterial, 0, batchSize);
1013 // reclaim a new batch
1014 vb.setNumVertices(batchSize * 3);
1015 vb.lock(vba);
1016 dest = vba.getVertexCoordPointer(0);
1017 endDest = dest + batchSize * 3;
1018 }
1019 ++ triRefIndex;
1020 }
1021 }
1022 }
1023 vba.unlock();
1024 uint numRemainingTris = batchSize - (uint)((endDest - dest) / 3);
1025 if (numRemainingTris)
1026 {
1027 drv.setPolygonMode(IDriver::Filled);
1028 drv.activeVertexBuffer(vb);
1029 drv.renderRawTriangles(material, 0, numRemainingTris);
1030 drv.setPolygonMode(IDriver::Line);
1031 //drv.renderRawTriangles(wiredMaterial, 0, numRemainingTris);
1032 }
1033 }
1034 drv.setPolygonMode(oldPolygonMode);
1035 }
1036
1037 // ***************************************************************************************
1038 void CPackedZone32::addInstance(const CShapeInfo &si, const NLMISC::CMatrix &matrix, TVertexGrid &vertexGrid, TTriListGrid &triListGrid)
1039 {
1040 for(uint k = 0; k < si.Tris.size(); ++k)
1041 {
1042 CTriangle worldTri;
1043 si.Tris[k].applyMatrix(matrix, worldTri);
1044 addTri(worldTri, vertexGrid, triListGrid);
1045 }
1046 }
1047
1048 // ***************************************************************************************
1049 CSmartPtr<CPackedZone16> CPackedZone32::buildPackedZone16()
1050 {
1051 if (Verts.size() > 65535) return NULL;
1052 if (Tris.size() > 65534) return NULL; // NB : not 65534 here because -1 is used to mark the end of a list
1053 if (TriLists.size() > 65534) return NULL;
1054 // can convert
1055 CSmartPtr<CPackedZone16> dest = new CPackedZone16;
1056 dest->Box = Box;
1057 dest->Verts = Verts;
1058 dest->Tris.resize(Tris.size());
1059 for(uint k = 0; k < Tris.size(); ++k)
1060 {
1061 dest->Tris[k].V0 = (uint16) Tris[k].V0;
1062 dest->Tris[k].V1 = (uint16) Tris[k].V1;
1063 dest->Tris[k].V2 = (uint16) Tris[k].V2;
1064 }
1065 dest->TriLists.resize(TriLists.size());
1066 for(uint k = 0; k < TriLists.size(); ++k)
1067 {
1068 dest->TriLists[k] = (uint16) TriLists[k];
1069 }
1070 dest->CellSize = CellSize;
1071 dest->Grid.init(Grid.getWidth(), Grid.getHeight());
1072 for (sint y = 0; y < (sint) Grid.getHeight(); ++y)
1073 {
1074 for (sint x = 0; x < (sint) Grid.getWidth(); ++x)
1075 {
1076 dest->Grid(x, y) = (uint16) Grid(x, y);
1077 }
1078 }
1079 dest->_Origin = _Origin;
1080 dest->_WorldToLocal = _WorldToLocal;
1081 dest->ZoneX = ZoneX;
1082 dest->ZoneY = ZoneY;
1083
1084 dest->_PackedLocalToWorld.set(1.f / (dest->_WorldToLocal.x * (float) PACKED_COL_RANGE),
1085 1.f / (dest->_WorldToLocal.y * (float) PACKED_COL_RANGE),
1086 1.f / (dest->_WorldToLocal.z * (float) PACKED_COL_RANGE));
1087
1088 return dest;
1089 }
1090
1091 // ***************************************************************************************
1092 void CPackedZone16::serial(NLMISC::IStream &f)
1093 {
1094 f.serialVersion(0);
1095 f.serial(Box);
1096 std::vector<uint16> datas;
1097 if (f.isReading())
1098 {
1099 // vertices
1100 serialPackedVector12(datas, f);
1101 Verts.resize(datas.size() / 3);
1102 for(uint k = 0; k < Verts.size(); ++k)
1103 {
1104 Verts[k].X = datas[k];
1105 Verts[k].Y = datas[Verts.size() + k];
1106 Verts[k].Z = datas[2 * Verts.size() + k];
1107 }
1108 // triangles
1109 serialPackedVector16(datas, f);
1110 Tris.resize(datas.size() / 3);
1111 for(uint k = 0; k < Tris.size(); ++k)
1112 {
1113 Tris[k].V0 = datas[3 * k];
1114 Tris[k].V1 = datas[3 * k + 1];
1115 Tris[k].V2 = datas[3 * k + 2];
1116 }
1117 // tris list
1118 serialPackedVector16(TriLists, f);
1119 // grid
1120 uint16 width = (uint16) Grid.getWidth();
1121 uint16 height = (uint16) Grid.getHeight();
1122 f.serial(width, height);
1123 Grid.init(width, height);
1124 serialPackedVector16(datas, f);
1125 if ((uint) datas.size() != (uint) width * (uint) height)
1126 {
1127 throw NLMISC::EInvalidDataStream();
1128 }
1129 std::copy(datas.begin(), datas.end(), Grid.begin());
1130 }
1131 else
1132 {
1133 // vertices
1134 datas.resize(Verts.size() * 3);
1135 for(uint k = 0; k < Verts.size(); ++k)
1136 {
1137 datas[k] = Verts[k].X;
1138 datas[Verts.size() + k ] = Verts[k].Y;
1139 datas[2 * Verts.size() + k] = Verts[k].Z;
1140 }
1141 //nlwarning("serial verts");
1142 serialPackedVector12(datas, f);
1143 // triangles
1144 datas.resize(Tris.size() * 3);
1145 for(uint k = 0; k < Tris.size(); ++k)
1146 {
1147 datas[3 * k] = Tris[k].V0;
1148 datas[3 * k + 1] = Tris[k].V1;
1149 datas[3 * k + 2] = Tris[k].V2;
1150 }
1151 //nlwarning("serial tris");
1152 serialPackedVector16(datas, f);
1153 // tris list
1154 //nlwarning("serial tri lists");
1155 serialPackedVector16(TriLists, f);
1156 // grid
1157 uint16 width = (uint16) Grid.getWidth();
1158 uint16 height = (uint16) Grid.getHeight();
1159 f.serial(width, height);
1160 datas.resize((uint) width * (uint) height);
1161 std::copy(Grid.begin(), Grid.end(), datas.begin());
1162 //nlwarning("serial grid");
1163 serialPackedVector16(datas, f);
1164 }
1165 f.serial(CellSize);
1166 f.serial(_Origin);
1167 f.serial(_WorldToLocal);
1168 f.serial(ZoneX);
1169 f.serial(ZoneY);
1170
1171 if (f.isReading())
1172 {
1173 _PackedLocalToWorld.set(1.f / (_WorldToLocal.x * (float) PACKED_COL_RANGE),
1174 1.f / (_WorldToLocal.y * (float) PACKED_COL_RANGE),
1175 1.f / (_WorldToLocal.z * (float) PACKED_COL_RANGE));
1176 }
1177 }
1178
1179 // ***************************************************************************************
1180 void CPackedZone16::render(CVertexBuffer &vb, IDriver &drv, CMaterial &material, CMaterial &wiredMaterial, const CMatrix &camMat, uint batchSize, const CVector localFrustCorners[8])
1181 {
1182 if (Tris.empty()) return;
1183 IDriver::TPolygonMode oldPolygonMode = drv.getPolygonMode();
1184 CVector frustCorners[8];
1185 for(uint k = 0; k < sizeofarray(frustCorners); ++k)
1186 {
1187 frustCorners[k] = camMat * localFrustCorners[k];
1188 frustCorners[k].x -= _Origin.x;
1189 frustCorners[k].y -= _Origin.y;
1190 }
1191 // project frustum on x/y plane to see where to test polys
1192 sint minY = INT_MAX;
1193 static CPolygon2D::TRasterVect silhouette;
1194 silhouette.clear();
1195 addQuadToSilhouette(frustCorners[0], frustCorners[1], frustCorners[2], frustCorners[3], silhouette, minY, CellSize);
1196 addQuadToSilhouette(frustCorners[1], frustCorners[5], frustCorners[6], frustCorners[2], silhouette, minY, CellSize);
1197 addQuadToSilhouette(frustCorners[4], frustCorners[5], frustCorners[6], frustCorners[7], silhouette, minY, CellSize);
1198 addQuadToSilhouette(frustCorners[0], frustCorners[4], frustCorners[7], frustCorners[3], silhouette, minY, CellSize);
1199 addQuadToSilhouette(frustCorners[0], frustCorners[1], frustCorners[5], frustCorners[4], silhouette, minY, CellSize);
1200 addQuadToSilhouette(frustCorners[3], frustCorners[7], frustCorners[6], frustCorners[2], silhouette, minY, CellSize);
1201 //
1202 {
1203 CVertexBufferReadWrite vba;
1204 vb.setNumVertices(batchSize * 3);
1205 vb.lock(vba);
1206 CVector *dest = vba.getVertexCoordPointer(0);
1207 const CVector *endDest = dest + batchSize * 3;
1208 for(sint y = 0; y < (sint) silhouette.size(); ++y)
1209 {
1210 sint gridY = y + minY;
1211 if (gridY < 0) continue;
1212 if (gridY >= (sint) Grid.getHeight()) continue;
1213 sint minX = silhouette[y].first;
1214 sint maxX = silhouette[y].second;
1215 for (sint x = minX; x <= maxX; ++x)
1216 {
1217 if (x < 0) continue;
1218 if (x >= (sint) Grid.getWidth()) break;
1219 uint32 triRefIndex = Grid(x, gridY);
1220 if (triRefIndex == UndefIndex) continue;
1221 for (;;)
1222 {
1223 uint16 triIndex = TriLists[triRefIndex];
1224 if (triIndex == UndefIndex) break; // end of list
1225 unpackTri(Tris[triIndex], dest);
1226 dest += 3;
1227 if (dest == endDest)
1228 {
1229 // flush batch
1230 vba.unlock();
1231 drv.setPolygonMode(IDriver::Filled);
1232 drv.activeVertexBuffer(vb);
1233 drv.renderRawTriangles(material, 0, batchSize);
1234 drv.setPolygonMode(IDriver::Line);
1235 //drv.renderRawTriangles(wiredMaterial, 0, batchSize);
1236 // reclaim a new batch
1237 vb.setNumVertices(batchSize * 3);
1238 vb.lock(vba);
1239 dest = vba.getVertexCoordPointer(0);
1240 endDest = dest + batchSize * 3;
1241 }
1242 ++ triRefIndex;
1243 }
1244 }
1245 }
1246 vba.unlock();
1247 uint numRemainingTris = batchSize - (uint)((endDest - dest) / 3);
1248 if (numRemainingTris)
1249 {
1250 drv.setPolygonMode(IDriver::Filled);
1251 drv.activeVertexBuffer(vb);
1252 drv.renderRawTriangles(material, 0, numRemainingTris);
1253 drv.setPolygonMode(IDriver::Line);
1254 //drv.renderRawTriangles(wiredMaterial, 0, numRemainingTris);
1255 }
1256 }
1257 drv.setPolygonMode(oldPolygonMode);
1258 }
1259
1260
1261
1262
1263
1264 // ***************************************************************************************
1265 void CPackedZone16::unpackTri(const CPackedTri16 &src, CVector dest[3]) const
1266 {
1267 // yes this is ugly code duplication of CPackedZone16::unpackTri but this code is temporary anyway...
1268 // TODO: add 'multiply-add' operator
1269 dest[0].set(Verts[src.V0].X * _PackedLocalToWorld.x + _Origin.x,
1270 Verts[src.V0].Y * _PackedLocalToWorld.y + _Origin.y,
1271 Verts[src.V0].Z * _PackedLocalToWorld.z + _Origin.z);
1272 dest[1].set(Verts[src.V1].X * _PackedLocalToWorld.x + _Origin.x,
1273 Verts[src.V1].Y * _PackedLocalToWorld.y + _Origin.y,
1274 Verts[src.V1].Z * _PackedLocalToWorld.z + _Origin.z);
1275 dest[2].set(Verts[src.V2].X * _PackedLocalToWorld.x + _Origin.x,
1276 Verts[src.V2].Y * _PackedLocalToWorld.y + _Origin.y,
1277 Verts[src.V2].Z * _PackedLocalToWorld.z + _Origin.z);
1278
1279 }
1280
1281 // raytrace code, common to CPackedZone32 & CPackedZone16
1282 template <class T> bool raytrace(T &packedZone, const NLMISC::CVector &start, const NLMISC::CVector &end, NLMISC::CVector &inter, std::vector<CTriangle> *testedTriangles = NULL, NLMISC::CVector *normal = NULL)
1283 {
1284 if (packedZone.Grid.empty()) return false;
1285 CVector2f start2f((start.x - packedZone.Box.getMin().x) / packedZone.CellSize, (start.y - packedZone.Box.getMin().y) / packedZone.CellSize);
1286 CVector2f dir2f((end.x - start.x) / packedZone.CellSize, (end.y - start.y) / packedZone.CellSize);
1287 sint x, y;
1288 CGridTraversal::startTraverse(start2f, x, y);
1289 do
1290 {
1291 if (x < 0) continue;
1292 if (x >= (sint) packedZone.Grid.getWidth()) continue;
1293 if (y < 0) continue;
1294 if (y >= (sint) packedZone.Grid.getHeight()) continue;
1295 typename T::TIndexType triListIndex = packedZone.Grid(x, y);
1296 if (triListIndex != T::UndefIndex)
1297 {
1298 CTriangle tri;
1299 CPlane triPlane;
1300 float bestInterDist = FLT_MAX;
1301 CVector bestNormal(0.f, 0.f, 0.f);
1302 CVector currInter;
1303 do
1304 {
1305 packedZone.unpackTri(packedZone.Tris[packedZone.TriLists[triListIndex]], &tri.V0);
1306 if (testedTriangles)
1307 {
1308 testedTriangles->push_back(tri);
1309 }
1310 triPlane.make(tri.V0, tri.V1, tri.V2);
1311 if (tri.intersect(start, end, currInter, triPlane))
1312 {
1313 float dist = (currInter - start).norm();
1314 if (dist < bestInterDist)
1315 {
1316 bestInterDist = dist;
1317 inter = currInter;
1318 bestNormal.set(triPlane.a, triPlane.b, triPlane.c);
1319 }
1320 }
1321 ++ triListIndex;
1322 }
1323 while (packedZone.TriLists[triListIndex] != T::UndefIndex);
1324 if (bestInterDist != FLT_MAX)
1325 {
1326 if (normal)
1327 {
1328 *normal = bestNormal.normed();
1329 }
1330 return true;
1331 }
1332 }
1333 }
1334 while(CGridTraversal::traverse(start2f, dir2f, x, y));
1335 return false;
1336 }
1337
1338 // ***************************************************************************************
1339 bool CPackedZone32::raytrace(const NLMISC::CVector &start, const NLMISC::CVector &end, NLMISC::CVector &inter, std::vector<CTriangle> *testedTriangles /*= NULL*/, NLMISC::CVector *normal /*= NULL*/) const
1340 {
1341 return NL3D::raytrace(*this, start, end, inter, testedTriangles, normal);
1342 }
1343
1344 // ***************************************************************************************
1345 bool CPackedZone16::raytrace(const NLMISC::CVector &start, const NLMISC::CVector &end, NLMISC::CVector &inter, std::vector<CTriangle> *testedTriangles /*= NULL*/, NLMISC::CVector *normal /*= NULL*/) const
1346 {
1347 return NL3D::raytrace(*this, start, end, inter, testedTriangles, normal);
1348 }
1349
1350 // ***************************************************************************************
1351 void CPackedZone16::appendSelection(const NLMISC::CPolygon2D &poly, std::vector<NLMISC::CTriangle> &selectedTriangles) const
1352 {
1353 // compute covered zones
1354 NLMISC::CPolygon2D localPoly = poly;
1355 for (uint k = 0; k < localPoly.Vertices.size(); ++k)
1356 {
1357 localPoly.Vertices[k].x = (localPoly.Vertices[k].x - Box.getMin().x) / CellSize;
1358 localPoly.Vertices[k].y = (localPoly.Vertices[k].y - Box.getMin().y) / CellSize;
1359 }
1360 NLMISC::CPolygon2D::TRasterVect borders;
1361 sint minY;
1362 localPoly.computeOuterBorders(borders, minY);
1363 CTriangle newTri;
1364 //
1365 std::vector<bool> done(Tris.size(), false); // avoid double insertion
1366 //
1367 for (sint y = minY; y < (sint) (minY + borders.size()); ++y)
1368 {
1369 if (y < 0 || y >= (sint) Grid.getHeight()) continue;
1370 for (sint x = borders[y - minY].first; x <= borders[y - minY].second; ++x)
1371 {
1372 if (x < 0 || x >= (sint) Grid.getWidth()) continue;
1373 {
1374 if (Grid(x, y) != UndefIndex)
1375 {
1376 uint16 currTriIndex = Grid(x, y);
1377 while (TriLists[currTriIndex] != UndefIndex)
1378 {
1379 if (!done[TriLists[currTriIndex]])
1380 {
1381 unpackTri(Tris[TriLists[currTriIndex]], &newTri.V0);
1382 selectedTriangles.push_back(newTri);
1383 done[TriLists[currTriIndex]] = true;
1384 }
1385 ++ currTriIndex;
1386 }
1387 }
1388 }
1389 }
1390 }
1391 }
1392
1393 // ***************************************************************************************
1394 void CPackedZone32::appendSelection(const NLMISC::CPolygon2D &poly, std::vector<NLMISC::CTriangle> &selectedTriangles) const
1395 {
1396 // TODO nico : factorize with CPackedZone16::appendSelection
1397 selectedTriangles.clear();
1398 // compute covered zones
1399 NLMISC::CPolygon2D localPoly = poly;
1400 for (uint k = 0; k < localPoly.Vertices.size(); ++k)
1401 {
1402 localPoly.Vertices[k].x = (localPoly.Vertices[k].x - Box.getMin().x) / CellSize;
1403 localPoly.Vertices[k].y = (localPoly.Vertices[k].y - Box.getMin().y) / CellSize;
1404 }
1405 NLMISC::CPolygon2D::TRasterVect borders;
1406 sint minY;
1407 localPoly.computeOuterBorders(borders, minY);
1408 CTriangle newTri;
1409 //
1410 std::vector<bool> done(Tris.size(), false); // avoid double insertion
1411 //
1412 for (sint y = minY; y < (sint) (minY + borders.size()); ++y)
1413 {
1414 if (y < 0 || y >= (sint) Grid.getHeight()) continue;
1415 for (sint x = borders[y - minY].first; x <= borders[y - minY].second; ++x)
1416 {
1417 if (x < 0 || x >= (sint) Grid.getWidth()) continue;
1418 {
1419 if (Grid(x, y) != UndefIndex)
1420 {
1421 uint32 currTriIndex = Grid(x, y);
1422 while (TriLists[currTriIndex] != UndefIndex)
1423 {
1424 if (!done[TriLists[currTriIndex]])
1425 {
1426 unpackTri(Tris[TriLists[currTriIndex]], &newTri.V0);
1427 selectedTriangles.push_back(newTri);
1428 done[TriLists[currTriIndex]] = true;
1429 }
1430 ++ currTriIndex;
1431 }
1432 }
1433 }
1434 }
1435 }
1436 }
1437
1438 } // NL3D