BVB Source Codes

CRYENGINE Show MergedMeshRenderNode.cpp Source code

Return Download CRYENGINE: download MergedMeshRenderNode.cpp Source code - Download CRYENGINE Source code - Type:.cpp
  1. // Copyright 2001-2016 Crytek GmbH / Crytek Group. All rights reserved.
  2.  
  3. #include "StdAfx.h"
  4.  
  5. #include <numeric>
  6. #include <algorithm>
  7. #include <unordered_map>
  8.  
  9. #include <CryMath/Cry_Geo.h>
  10. #include <CryMath/Cry_GeoIntersect.h>
  11. #include <CryThreading/IJobManager_JobDelegator.h>
  12. #include <CrySystem/Profilers/IStatoscope.h>
  13. #include <CryAnimation/ICryAnimation.h>
  14. #include <Cry3DEngine/IIndexedMesh.h>
  15. #include <CryMath/QTangent.h>
  16. #include <CryString/StringUtils.h>
  17.  
  18. #include "MergedMeshRenderNode.h"
  19. #include "MergedMeshGeometry.h"
  20. #include "DeformableNode.h"
  21.  
  22. #define FSL_CREATE_MODE FSL_VIDEO_CREATE
  23.  
  24. #include <CryCore/StlUtils.h>
  25.  
  26. namespace
  27. {
  28. static IGeneralMemoryHeap* s_MergedMeshPool = NULL;
  29. static CryCriticalSection s_MergedMeshPoolLock;
  30.  
  31. static inline SMeshBoneMapping_uint8 _SortBoneMapping(const SMeshBoneMapping_uint8& a)
  32. {
  33.         SMeshBoneMapping_uint8 r;
  34.         memset(&r, 0, sizeof(r));
  35.         for (size_t i = 0, j = 0; i < 4; ++i)
  36.         {
  37.                 if (a.weights[i])
  38.                 {
  39.                         r.weights[j] = a.weights[i];
  40.                         r.boneIds[j] = a.boneIds[i];
  41.                         ++j;
  42.                 }
  43.         }
  44.         return r;
  45. }
  46. static inline bool operator==(const SMeshBoneMapping_uint8& a, const SMeshBoneMapping_uint8& b)
  47. {
  48.         const SMeshBoneMapping_uint8 _a = _SortBoneMapping(a);
  49.         const SMeshBoneMapping_uint8 _b = _SortBoneMapping(b);
  50.         return memcmp(&_a, &_b, sizeof(_a)) == 0;
  51. }
  52.  
  53. static inline bool operator!=(const SMeshBoneMapping_uint8& a, const SMeshBoneMapping_uint8& b)
  54. {
  55.         return !(a == b);
  56. }
  57.  
  58. // A hash function with multiplier 65599 (from Red Dragon book)
  59. static inline size_t hasher(const char* s, size_t len)
  60. {
  61.         size_t hash = 0;
  62.         for (size_t i = 0; i < len; ++i)
  63.                 hash = 65599 * hash + s[i];
  64.         return hash ^ (hash >> 16);
  65. }
  66.  
  67. #if MMRM_RENDER_DEBUG && MMRM_VISUALIZE_WINDFIELD
  68. void VisualizeWindField(const Vec3* samples, const AABB& bbox, bool wind_dir, bool trace)
  69. {
  70.         IRenderAuxGeom* pAuxGeomRender = gEnv->pRenderer->GetIRenderAuxGeom();
  71.         pAuxGeomRender->DrawAABB(bbox, false, Col_Green, eBBD_Faceted);
  72.         const Vec3& size = bbox.GetSize();
  73.         if (wind_dir)
  74.         {
  75.                 for (size_t x = 0; x < MMRM_WIND_DIM; ++x)
  76.                         for (size_t y = 0; y < MMRM_WIND_DIM; ++y)
  77.                                 for (size_t z = 0; z < MMRM_WIND_DIM; ++z)
  78.                                 {
  79.                                         Vec3 pos, w;
  80.                                         pos.x = bbox.min.x + ((float)x / (float)((MMRM_WIND_DIM))) * size.x;
  81.                                         pos.y = bbox.min.y + ((float)y / (float)((MMRM_WIND_DIM))) * size.y;
  82.                                         pos.z = bbox.min.z + ((float)z / (float)((MMRM_WIND_DIM))) * size.z;
  83.                                         pAuxGeomRender->DrawLine(pos, Col_Green, pos + samples[x + y * MMRM_WIND_DIM + z * sqr(MMRM_WIND_DIM)].GetNormalized(), Col_Pink, 1.f);
  84.                                 }
  85.         }
  86.         if (trace)
  87.         {
  88.                 std::vector<std::pair<Vec3, Vec3>> points;
  89.                 const size_t count = MMRM_WIND_DIM * 4;
  90.                 for (size_t x = 0; x < count; ++x)
  91.                         for (size_t y = 0; y < count; ++y)
  92.                                 for (size_t z = 0; z < count; ++z)
  93.                                 {
  94.                                         Vec3 pos;
  95.                                         pos.x = ((float)x / (float)(count));
  96.                                         pos.y = ((float)y / (float)(count));
  97.                                         pos.z = ((float)z / (float)(count));
  98.                                         points.push_back(std::make_pair(pos, Vec3(0, 0, 0)));
  99.                                 }
  100.                 for (size_t i = 0; i < 16; ++i)
  101.                 {
  102.                         ColorB col0;
  103.                         col0.lerpFloat(Col_Blue, Col_Red, i / 16.f);
  104.                         ColorB col1;
  105.                         col1.lerpFloat(Col_Blue, Col_Red, (i + 1) / 16.f);
  106.                         for (size_t j = 0; j < count * count * count; ++j)
  107.                         {
  108.                                 const Vec3& pos = points[j].first;
  109.                                 const Vec3& vel = points[j].second;
  110.                                 Vec3 realpos;
  111.                                 realpos.x = bbox.min.x + pos.x * size.x;
  112.                                 realpos.y = bbox.min.y + pos.y * size.y;
  113.                                 realpos.z = bbox.min.z + pos.z * size.z;
  114.  
  115.                                 const Vec3& nvel = vel + ::SampleWind(pos, samples) * (1.f / 8.f);
  116.                                 Vec3 npos = realpos + nvel * 0.3333f;
  117.                                 pAuxGeomRender->DrawLine(realpos, col0, npos, col1, 1.f);
  118.  
  119.                                 npos.x = (realpos.x - bbox.min.x) / size.x;
  120.                                 npos.y = (realpos.y - bbox.min.y) / size.y;
  121.                                 npos.z = (realpos.z - bbox.min.z) / size.z;
  122.                                 points[j].first = npos;
  123.                                 points[j].second = nvel;
  124.                         }
  125.                 }
  126.         }
  127. }
  128. #endif
  129.  
  130. // Three points are a counter-clockwise turn if turn() > 0, clockwise if
  131. // turn() < 0, and collinear if turn() == 0.
  132. static inline float turn(const Vec2& p1, const Vec2& p2, const Vec2& p3)
  133. {
  134.         return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
  135. }
  136.  
  137. // Weirdo functions for DynArray
  138. // NOTE: Can't make these static, gcc wants an external for a template parameter in graham_reduce
  139. inline void graham_increment(Vec2*& iter) { ++iter; }
  140. inline void graham_decrement(Vec2*& iter) { --iter; }
  141.  
  142. // Create and maintain a convex hull while iterating over a sorted list of points
  143. template<void(Advance)(Vec2*&)>
  144. static size_t graham_reduce(Vec2* begin, Vec2* end, DynArray<Vec2>& hull)
  145. {
  146.         while (begin != end)
  147.         {
  148.                 while (hull.size() > 1 && turn(*(hull.rbegin() - 1), *(hull.rbegin()), *begin) > 0)
  149.                         hull.pop_back();
  150.                 if (!hull.size() || *hull.rbegin() != *begin)
  151.                         hull.push_back(*begin);
  152.                 Advance(begin);
  153.         }
  154.         return hull.size();
  155. }
  156.  
  157. static inline bool vec_compare_lex(const Vec2& a, const Vec2& b)
  158. {
  159.         if (a.x < b.x)
  160.                 return true;
  161.         if (a.x > b.x)
  162.                 return false;
  163.         return a.y < b.y;
  164. }
  165.  
  166. // Basic Graham scan implementation. Note this variant does not sort the points by
  167. // polar angle but rather performs the ccw-reduction pass on the sorted point list
  168. // twice, once in regular and once in reversed order producing the upper and lower
  169. // convex hull which get merged as a last step.
  170. //
  171. // The original algorithm (as can be seen on wikipedia) calculates the hull
  172. // in-place in the input list, but has to deal with searching for the lowest
  173. // y-coordinate and sorting the input list by polar angles of each point in respect to the
  174. // x-axis, so (apart from the additional allocations) the running time should be roughly
  175. // identical.
  176. static size_t convexhull_graham_scan(DynArray<Vec2>& points)
  177. {
  178.         // If we have less than 4 points, we already have our hull implicitly
  179.         if (points.size() < 4)
  180.                 return points.size();
  181.  
  182.         // Sort the point list by x-coordinate
  183.         std::sort(points.begin(), points.end(), vec_compare_lex);
  184.         Vec2* begin = points.begin();
  185.         Vec2* end = std::unique(begin, points.end());
  186.  
  187.         // Calculate the lower and upper half of the hull
  188.         DynArray<Vec2> lower, upper;
  189.         graham_reduce<graham_increment>(begin, end, lower);
  190.         graham_reduce<graham_decrement>(end - 1, begin - 1, upper);
  191.  
  192.         // Merge the two hulls and swap it with input array
  193.         // Note: it's safe to skip the first and the last points as they will
  194.         // in lower already
  195.  
  196.         // Note: The insert method of our moronic dynarray<T> DOES NOT COMPILE!
  197.         for (size_t i = 1, end = upper.size() - 1; i < end; lower.push_back(upper[i++]))
  198.                 ;
  199.  
  200.         std::swap(points, lower);
  201.         return points.size();
  202. };
  203.  
  204. static size_t convexhull_giftwrap(DynArray<Vec2>& points)
  205. {
  206.         size_t i = 0, h = 0, n = points.size();
  207.         for (size_t j = 0; j < n; ++j)
  208.                 if (points[j].y < points[i].y)
  209.                         i = j;
  210.         do
  211.         {
  212.                 std::swap(points[i], points[h]);
  213.                 for (size_t j = 0; j < n; ++j)
  214.                         if (turn(points[h], points[i], points[j]) < 0)
  215.                                 i = j;
  216.                 h++;
  217.         }
  218.         while (i > 0);
  219.  
  220.         points.erase(points.begin() + h, points.end());
  221.         return points.size();
  222. }
  223.  
  224. // *INDENT-OFF* - To keep the cube in the comment unchanged
  225.     /*
  226.      int edgeTable[256].  It corresponds to the 2^8 possible combinations of
  227.      of the eight (n) vertices either existing inside or outside (2^n) of the
  228.      surface.  A vertex is inside of a surface if the value at that vertex is
  229.      less than that of the surface you are scanning for.  The table index is
  230.      constructed bitwise with bit 0 corresponding to vertex 0, bit 1 to vert
  231.      1.. bit 7 to vert 7.  The value in the table tells you which edges of
  232.      the table are intersected by the surface.  Once again bit 0 corresponds
  233.      to edge 0 and so on, up to edge 12.
  234.      Constructing the table simply consisted of having a program run thru
  235.      the 256 cases and setting the edge bit if the vertices at either end of
  236.      the edge had different values (one is inside while the other is out).
  237.      The purpose of the table is to speed up the scanning process.  Only the
  238.      edges whose bit's are set contain vertices of the surface.
  239.      Vertex 0 is on the bottom face, back edge, left side.
  240.      The progression of vertices is clockwise around the bottom face
  241.      and then clockwise around the top face of the cube.  Edge 0 goes from
  242.      vertex 0 to vertex 1, Edge 2 is from 2->3 and so on around clockwise to
  243.      vertex 0 again. Then Edge 4 to 7 make up the top face, 4->5, 5->6, 6->7
  244.      and 7->4.  Edge 8 thru 11 are the vertical edges from vert 0->4, 1->5,
  245.      2->6, and 3->7.
  246.          4--------5     *---4----*
  247.         /|       /|    /|       /|
  248.        / |      / |   7 |      5 |
  249.       /  |     /  |  /  8     /  9
  250.      7--------6   | *----6---*   |
  251.      |   |    |   | |   |    |   |
  252.      |   0----|---1 |   *---0|---*
  253.      |  /     |  /  11 /     10 /
  254.      | /      | /   | 3      | 1
  255.      |/       |/    |/       |/
  256.      3--------2     *---2----*
  257.   */
  258. // *INDENT-ON*
  259.  
  260. static uint16 s_marching_cubes_edge_table[256] =
  261. {
  262.         0x0,   0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c,
  263.         0x80c, 0x905, 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09, 0xf00,
  264.         0x190, 0x99,  0x393, 0x29a, 0x596, 0x49f, 0x795, 0x69c,
  265.         0x99c, 0x895, 0xb9f, 0xa96, 0xd9a, 0xc93, 0xf99, 0xe90,
  266.         0x230, 0x339, 0x33,  0x13a, 0x636, 0x73f, 0x435, 0x53c,
  267.         0xa3c, 0xb35, 0x83f, 0x936, 0xe3a, 0xf33, 0xc39, 0xd30,
  268.         0x3a0, 0x2a9, 0x1a3, 0xaa,  0x7a6, 0x6af, 0x5a5, 0x4ac,
  269.         0xbac, 0xaa5, 0x9af, 0x8a6, 0xfaa, 0xea3, 0xda9, 0xca0,
  270.         0x460, 0x569, 0x663, 0x76a, 0x66,  0x16f, 0x265, 0x36c,
  271.         0xc6c, 0xd65, 0xe6f, 0xf66, 0x86a, 0x963, 0xa69, 0xb60,
  272.         0x5f0, 0x4f9, 0x7f3, 0x6fa, 0x1f6, 0xff,  0x3f5, 0x2fc,
  273.         0xdfc, 0xcf5, 0xfff, 0xef6, 0x9fa, 0x8f3, 0xbf9, 0xaf0,
  274.         0x650, 0x759, 0x453, 0x55a, 0x256, 0x35f, 0x55,  0x15c,
  275.         0xe5c, 0xf55, 0xc5f, 0xd56, 0xa5a, 0xb53, 0x859, 0x950,
  276.         0x7c0, 0x6c9, 0x5c3, 0x4ca, 0x3c6, 0x2cf, 0x1c5, 0xcc,
  277.         0xfcc, 0xec5, 0xdcf, 0xcc6, 0xbca, 0xac3, 0x9c9, 0x8c0,
  278.         0x8c0, 0x9c9, 0xac3, 0xbca, 0xcc6, 0xdcf, 0xec5, 0xfcc,
  279.         0xcc,  0x1c5, 0x2cf, 0x3c6, 0x4ca, 0x5c3, 0x6c9, 0x7c0,
  280.         0x950, 0x859, 0xb53, 0xa5a, 0xd56, 0xc5f, 0xf55, 0xe5c,
  281.         0x15c, 0x55,  0x35f, 0x256, 0x55a, 0x453, 0x759, 0x650,
  282.         0xaf0, 0xbf9, 0x8f3, 0x9fa, 0xef6, 0xfff, 0xcf5, 0xdfc,
  283.         0x2fc, 0x3f5, 0xff,  0x1f6, 0x6fa, 0x7f3, 0x4f9, 0x5f0,
  284.         0xb60, 0xa69, 0x963, 0x86a, 0xf66, 0xe6f, 0xd65, 0xc6c,
  285.         0x36c, 0x265, 0x16f, 0x66,  0x76a, 0x663, 0x569, 0x460,
  286.         0xca0, 0xda9, 0xea3, 0xfaa, 0x8a6, 0x9af, 0xaa5, 0xbac,
  287.         0x4ac, 0x5a5, 0x6af, 0x7a6, 0xaa,  0x1a3, 0x2a9, 0x3a0,
  288.         0xd30, 0xc39, 0xf33, 0xe3a, 0x936, 0x83f, 0xb35, 0xa3c,
  289.         0x53c, 0x435, 0x73f, 0x636, 0x13a, 0x33,  0x339, 0x230,
  290.         0xe90, 0xf99, 0xc93, 0xd9a, 0xa96, 0xb9f, 0x895, 0x99c,
  291.         0x69c, 0x795, 0x49f, 0x596, 0x29a, 0x393, 0x99,  0x190,
  292.         0xf00, 0xe09, 0xd03, 0xc0a, 0xb06, 0xa0f, 0x905, 0x80c,
  293.         0x70c, 0x605, 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x0
  294. };
  295.  
  296. /*
  297.    int8 s_triTable[256][16] also corresponds to the 256 possible combinations
  298.    of vertices.
  299.    The [16] dimension of the table is again the list of edges of the cube
  300.    which are intersected by the surface.  This time however, the edges are
  301.    enumerated in the order of the vertices making up the triangle mesh of
  302.    the surface.  Each edge contains one vertex that is on the surface.
  303.    Each triple of edges listed in the table contains the vertices of one
  304.    triangle on the mesh.  The are 16 entries because it has been shown that
  305.    there are at most 5 triangles in a cube and each "edge triple" list is
  306.    terminated with the value -1.
  307.    For example triTable[3] contains
  308.    {1, 8, 3, 9, 8, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
  309.    This corresponds to the case of a cube whose vertex 0 and 1 are inside
  310.    of the surface and the rest of the verts are outside (00000001 bitwise
  311.    OR'ed with 00000010 makes 00000011 == 3).  Therefore, this cube is
  312.    intersected by the surface roughly in the form of a plane which cuts
  313.    edges 8,9,1 and 3.  This quadrilateral can be constructed from two
  314.    triangles: one which is made of the intersection vertices found on edges
  315.    1,8, and 3; the other is formed from the vertices on edges 9,8, and 1.
  316.    Remember, each intersected edge contains only one surface vertex.  The
  317.    vertex triples are listed in counter clockwise order for proper facing.
  318.  */
  319. static int8 s_marching_cubes_tri_table[256][16] =
  320. {
  321.         { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  322.         { 0,  8,  3,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  323.         { 0,  1,  9,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  324.         { 1,  8,  3,  9,  8,  1,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  325.         { 1,  2,  10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  326.         { 0,  8,  3,  1,  2,  10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  327.         { 9,  2,  10, 0,  2,  9,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  328.         { 2,  8,  3,  2,  10, 8,  10, 9,  8,  -1, -1, -1, -1, -1, -1, -1 },
  329.         { 3,  11, 2,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  330.         { 0,  11, 2,  8,  11, 0,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  331.         { 1,  9,  0,  2,  3,  11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  332.         { 1,  11, 2,  1,  9,  11, 9,  8,  11, -1, -1, -1, -1, -1, -1, -1 },
  333.         { 3,  10, 1,  11, 10, 3,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  334.         { 0,  10, 1,  0,  8,  10, 8,  11, 10, -1, -1, -1, -1, -1, -1, -1 },
  335.         { 3,  9,  0,  3,  11, 9,  11, 10, 9,  -1, -1, -1, -1, -1, -1, -1 },
  336.         { 9,  8,  10, 10, 8,  11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  337.         { 4,  7,  8,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  338.         { 4,  3,  0,  7,  3,  4,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  339.         { 0,  1,  9,  8,  4,  7,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  340.         { 4,  1,  9,  4,  7,  1,  7,  3,  1,  -1, -1, -1, -1, -1, -1, -1 },
  341.         { 1,  2,  10, 8,  4,  7,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  342.         { 3,  4,  7,  3,  0,  4,  1,  2,  10, -1, -1, -1, -1, -1, -1, -1 },
  343.         { 9,  2,  10, 9,  0,  2,  8,  4,  7,  -1, -1, -1, -1, -1, -1, -1 },
  344.         { 2,  10, 9,  2,  9,  7,  2,  7,  3,  7,  9,  4,  -1, -1, -1, -1 },
  345.         { 8,  4,  7,  3,  11, 2,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  346.         { 11, 4,  7,  11, 2,  4,  2,  0,  4,  -1, -1, -1, -1, -1, -1, -1 },
  347.         { 9,  0,  1,  8,  4,  7,  2,  3,  11, -1, -1, -1, -1, -1, -1, -1 },
  348.         { 4,  7,  11, 9,  4,  11, 9,  11, 2,  9,  2,  1,  -1, -1, -1, -1 },
  349.         { 3,  10, 1,  3,  11, 10, 7,  8,  4,  -1, -1, -1, -1, -1, -1, -1 },
  350.         { 1,  11, 10, 1,  4,  11, 1,  0,  4,  7,  11, 4,  -1, -1, -1, -1 },
  351.         { 4,  7,  8,  9,  0,  11, 9,  11, 10, 11, 0,  3,  -1, -1, -1, -1 },
  352.         { 4,  7,  11, 4,  11, 9,  9,  11, 10, -1, -1, -1, -1, -1, -1, -1 },
  353.         { 9,  5,  4,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  354.         { 9,  5,  4,  0,  8,  3,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  355.         { 0,  5,  4,  1,  5,  0,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  356.         { 8,  5,  4,  8,  3,  5,  3,  1,  5,  -1, -1, -1, -1, -1, -1, -1 },
  357.         { 1,  2,  10, 9,  5,  4,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  358.         { 3,  0,  8,  1,  2,  10, 4,  9,  5,  -1, -1, -1, -1, -1, -1, -1 },
  359.         { 5,  2,  10, 5,  4,  2,  4,  0,  2,  -1, -1, -1, -1, -1, -1, -1 },
  360.         { 2,  10, 5,  3,  2,  5,  3,  5,  4,  3,  4,  8,  -1, -1, -1, -1 },
  361.         { 9,  5,  4,  2,  3,  11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  362.         { 0,  11, 2,  0,  8,  11, 4,  9,  5,  -1, -1, -1, -1, -1, -1, -1 },
  363.         { 0,  5,  4,  0,  1,  5,  2,  3,  11, -1, -1, -1, -1, -1, -1, -1 },
  364.         { 2,  1,  5,  2,  5,  8,  2,  8,  11, 4,  8,  5,  -1, -1, -1, -1 },
  365.         { 10, 3,  11, 10, 1,  3,  9,  5,  4,  -1, -1, -1, -1, -1, -1, -1 },
  366.         { 4,  9,  5,  0,  8,  1,  8,  10, 1,  8,  11, 10, -1, -1, -1, -1 },
  367.         { 5,  4,  0,  5,  0,  11, 5,  11, 10, 11, 0,  3,  -1, -1, -1, -1 },
  368.         { 5,  4,  8,  5,  8,  10, 10, 8,  11, -1, -1, -1, -1, -1, -1, -1 },
  369.         { 9,  7,  8,  5,  7,  9,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  370.         { 9,  3,  0,  9,  5,  3,  5,  7,  3,  -1, -1, -1, -1, -1, -1, -1 },
  371.         { 0,  7,  8,  0,  1,  7,  1,  5,  7,  -1, -1, -1, -1, -1, -1, -1 },
  372.         { 1,  5,  3,  3,  5,  7,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  373.         { 9,  7,  8,  9,  5,  7,  10, 1,  2,  -1, -1, -1, -1, -1, -1, -1 },
  374.         { 10, 1,  2,  9,  5,  0,  5,  3,  0,  5,  7,  3,  -1, -1, -1, -1 },
  375.         { 8,  0,  2,  8,  2,  5,  8,  5,  7,  10, 5,  2,  -1, -1, -1, -1 },
  376.         { 2,  10, 5,  2,  5,  3,  3,  5,  7,  -1, -1, -1, -1, -1, -1, -1 },
  377.         { 7,  9,  5,  7,  8,  9,  3,  11, 2,  -1, -1, -1, -1, -1, -1, -1 },
  378.         { 9,  5,  7,  9,  7,  2,  9,  2,  0,  2,  7,  11, -1, -1, -1, -1 },
  379.         { 2,  3,  11, 0,  1,  8,  1,  7,  8,  1,  5,  7,  -1, -1, -1, -1 },
  380.         { 11, 2,  1,  11, 1,  7,  7,  1,  5,  -1, -1, -1, -1, -1, -1, -1 },
  381.         { 9,  5,  8,  8,  5,  7,  10, 1,  3,  10, 3,  11, -1, -1, -1, -1 },
  382.         { 5,  7,  0,  5,  0,  9,  7,  11, 0,  1,  0,  10, 11, 10, 0,  -1 },
  383.         { 11, 10, 0,  11, 0,  3,  10, 5,  0,  8,  0,  7,  5,  7,  0,  -1 },
  384.         { 11, 10, 5,  7,  11, 5,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  385.         { 10, 6,  5,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  386.         { 0,  8,  3,  5,  10, 6,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  387.         { 9,  0,  1,  5,  10, 6,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  388.         { 1,  8,  3,  1,  9,  8,  5,  10, 6,  -1, -1, -1, -1, -1, -1, -1 },
  389.         { 1,  6,  5,  2,  6,  1,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  390.         { 1,  6,  5,  1,  2,  6,  3,  0,  8,  -1, -1, -1, -1, -1, -1, -1 },
  391.         { 9,  6,  5,  9,  0,  6,  0,  2,  6,  -1, -1, -1, -1, -1, -1, -1 },
  392.         { 5,  9,  8,  5,  8,  2,  5,  2,  6,  3,  2,  8,  -1, -1, -1, -1 },
  393.         { 2,  3,  11, 10, 6,  5,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  394.         { 11, 0,  8,  11, 2,  0,  10, 6,  5,  -1, -1, -1, -1, -1, -1, -1 },
  395.         { 0,  1,  9,  2,  3,  11, 5,  10, 6,  -1, -1, -1, -1, -1, -1, -1 },
  396.         { 5,  10, 6,  1,  9,  2,  9,  11, 2,  9,  8,  11, -1, -1, -1, -1 },
  397.         { 6,  3,  11, 6,  5,  3,  5,  1,  3,  -1, -1, -1, -1, -1, -1, -1 },
  398.         { 0,  8,  11, 0,  11, 5,  0,  5,  1,  5,  11, 6,  -1, -1, -1, -1 },
  399.         { 3,  11, 6,  0,  3,  6,  0,  6,  5,  0,  5,  9,  -1, -1, -1, -1 },
  400.         { 6,  5,  9,  6,  9,  11, 11, 9,  8,  -1, -1, -1, -1, -1, -1, -1 },
  401.         { 5,  10, 6,  4,  7,  8,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  402.         { 4,  3,  0,  4,  7,  3,  6,  5,  10, -1, -1, -1, -1, -1, -1, -1 },
  403.         { 1,  9,  0,  5,  10, 6,  8,  4,  7,  -1, -1, -1, -1, -1, -1, -1 },
  404.         { 10, 6,  5,  1,  9,  7,  1,  7,  3,  7,  9,  4,  -1, -1, -1, -1 },
  405.         { 6,  1,  2,  6,  5,  1,  4,  7,  8,  -1, -1, -1, -1, -1, -1, -1 },
  406.         { 1,  2,  5,  5,  2,  6,  3,  0,  4,  3,  4,  7,  -1, -1, -1, -1 },
  407.         { 8,  4,  7,  9,  0,  5,  0,  6,  5,  0,  2,  6,  -1, -1, -1, -1 },
  408.         { 7,  3,  9,  7,  9,  4,  3,  2,  9,  5,  9,  6,  2,  6,  9,  -1 },
  409.         { 3,  11, 2,  7,  8,  4,  10, 6,  5,  -1, -1, -1, -1, -1, -1, -1 },
  410.         { 5,  10, 6,  4,  7,  2,  4,  2,  0,  2,  7,  11, -1, -1, -1, -1 },
  411.         { 0,  1,  9,  4,  7,  8,  2,  3,  11, 5,  10, 6,  -1, -1, -1, -1 },
  412.         { 9,  2,  1,  9,  11, 2,  9,  4,  11, 7,  11, 4,  5,  10, 6,  -1 },
  413.         { 8,  4,  7,  3,  11, 5,  3,  5,  1,  5,  11, 6,  -1, -1, -1, -1 },
  414.         { 5,  1,  11, 5,  11, 6,  1,  0,  11, 7,  11, 4,  0,  4,  11, -1 },
  415.         { 0,  5,  9,  0,  6,  5,  0,  3,  6,  11, 6,  3,  8,  4,  7,  -1 },
  416.         { 6,  5,  9,  6,  9,  11, 4,  7,  9,  7,  11, 9,  -1, -1, -1, -1 },
  417.         { 10, 4,  9,  6,  4,  10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  418.         { 4,  10, 6,  4,  9,  10, 0,  8,  3,  -1, -1, -1, -1, -1, -1, -1 },
  419.         { 10, 0,  1,  10, 6,  0,  6,  4,  0,  -1, -1, -1, -1, -1, -1, -1 },
  420.         { 8,  3,  1,  8,  1,  6,  8,  6,  4,  6,  1,  10, -1, -1, -1, -1 },
  421.         { 1,  4,  9,  1,  2,  4,  2,  6,  4,  -1, -1, -1, -1, -1, -1, -1 },
  422.         { 3,  0,  8,  1,  2,  9,  2,  4,  9,  2,  6,  4,  -1, -1, -1, -1 },
  423.         { 0,  2,  4,  4,  2,  6,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  424.         { 8,  3,  2,  8,  2,  4,  4,  2,  6,  -1, -1, -1, -1, -1, -1, -1 },
  425.         { 10, 4,  9,  10, 6,  4,  11, 2,  3,  -1, -1, -1, -1, -1, -1, -1 },
  426.         { 0,  8,  2,  2,  8,  11, 4,  9,  10, 4,  10, 6,  -1, -1, -1, -1 },
  427.         { 3,  11, 2,  0,  1,  6,  0,  6,  4,  6,  1,  10, -1, -1, -1, -1 },
  428.         { 6,  4,  1,  6,  1,  10, 4,  8,  1,  2,  1,  11, 8,  11, 1,  -1 },
  429.         { 9,  6,  4,  9,  3,  6,  9,  1,  3,  11, 6,  3,  -1, -1, -1, -1 },
  430.         { 8,  11, 1,  8,  1,  0,  11, 6,  1,  9,  1,  4,  6,  4,  1,  -1 },
  431.         { 3,  11, 6,  3,  6,  0,  0,  6,  4,  -1, -1, -1, -1, -1, -1, -1 },
  432.         { 6,  4,  8,  11, 6,  8,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  433.         { 7,  10, 6,  7,  8,  10, 8,  9,  10, -1, -1, -1, -1, -1, -1, -1 },
  434.         { 0,  7,  3,  0,  10, 7,  0,  9,  10, 6,  7,  10, -1, -1, -1, -1 },
  435.         { 10, 6,  7,  1,  10, 7,  1,  7,  8,  1,  8,  0,  -1, -1, -1, -1 },
  436.         { 10, 6,  7,  10, 7,  1,  1,  7,  3,  -1, -1, -1, -1, -1, -1, -1 },
  437.         { 1,  2,  6,  1,  6,  8,  1,  8,  9,  8,  6,  7,  -1, -1, -1, -1 },
  438.         { 2,  6,  9,  2,  9,  1,  6,  7,  9,  0,  9,  3,  7,  3,  9,  -1 },
  439.         { 7,  8,  0,  7,  0,  6,  6,  0,  2,  -1, -1, -1, -1, -1, -1, -1 },
  440.         { 7,  3,  2,  6,  7,  2,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  441.         { 2,  3,  11, 10, 6,  8,  10, 8,  9,  8,  6,  7,  -1, -1, -1, -1 },
  442.         { 2,  0,  7,  2,  7,  11, 0,  9,  7,  6,  7,  10, 9,  10, 7,  -1 },
  443.         { 1,  8,  0,  1,  7,  8,  1,  10, 7,  6,  7,  10, 2,  3,  11, -1 },
  444.         { 11, 2,  1,  11, 1,  7,  10, 6,  1,  6,  7,  1,  -1, -1, -1, -1 },
  445.         { 8,  9,  6,  8,  6,  7,  9,  1,  6,  11, 6,  3,  1,  3,  6,  -1 },
  446.         { 0,  9,  1,  11, 6,  7,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  447.         { 7,  8,  0,  7,  0,  6,  3,  11, 0,  11, 6,  0,  -1, -1, -1, -1 },
  448.         { 7,  11, 6,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  449.         { 7,  6,  11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  450.         { 3,  0,  8,  11, 7,  6,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  451.         { 0,  1,  9,  11, 7,  6,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  452.         { 8,  1,  9,  8,  3,  1,  11, 7,  6,  -1, -1, -1, -1, -1, -1, -1 },
  453.         { 10, 1,  2,  6,  11, 7,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  454.         { 1,  2,  10, 3,  0,  8,  6,  11, 7,  -1, -1, -1, -1, -1, -1, -1 },
  455.         { 2,  9,  0,  2,  10, 9,  6,  11, 7,  -1, -1, -1, -1, -1, -1, -1 },
  456.         { 6,  11, 7,  2,  10, 3,  10, 8,  3,  10, 9,  8,  -1, -1, -1, -1 },
  457.         { 7,  2,  3,  6,  2,  7,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  458.         { 7,  0,  8,  7,  6,  0,  6,  2,  0,  -1, -1, -1, -1, -1, -1, -1 },
  459.         { 2,  7,  6,  2,  3,  7,  0,  1,  9,  -1, -1, -1, -1, -1, -1, -1 },
  460.         { 1,  6,  2,  1,  8,  6,  1,  9,  8,  8,  7,  6,  -1, -1, -1, -1 },
  461.         { 10, 7,  6,  10, 1,  7,  1,  3,  7,  -1, -1, -1, -1, -1, -1, -1 },
  462.         { 10, 7,  6,  1,  7,  10, 1,  8,  7,  1,  0,  8,  -1, -1, -1, -1 },
  463.         { 0,  3,  7,  0,  7,  10, 0,  10, 9,  6,  10, 7,  -1, -1, -1, -1 },
  464.         { 7,  6,  10, 7,  10, 8,  8,  10, 9,  -1, -1, -1, -1, -1, -1, -1 },
  465.         { 6,  8,  4,  11, 8,  6,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  466.         { 3,  6,  11, 3,  0,  6,  0,  4,  6,  -1, -1, -1, -1, -1, -1, -1 },
  467.         { 8,  6,  11, 8,  4,  6,  9,  0,  1,  -1, -1, -1, -1, -1, -1, -1 },
  468.         { 9,  4,  6,  9,  6,  3,  9,  3,  1,  11, 3,  6,  -1, -1, -1, -1 },
  469.         { 6,  8,  4,  6,  11, 8,  2,  10, 1,  -1, -1, -1, -1, -1, -1, -1 },
  470.         { 1,  2,  10, 3,  0,  11, 0,  6,  11, 0,  4,  6,  -1, -1, -1, -1 },
  471.         { 4,  11, 8,  4,  6,  11, 0,  2,  9,  2,  10, 9,  -1, -1, -1, -1 },
  472.         { 10, 9,  3,  10, 3,  2,  9,  4,  3,  11, 3,  6,  4,  6,  3,  -1 },
  473.         { 8,  2,  3,  8,  4,  2,  4,  6,  2,  -1, -1, -1, -1, -1, -1, -1 },
  474.         { 0,  4,  2,  4,  6,  2,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  475.         { 1,  9,  0,  2,  3,  4,  2,  4,  6,  4,  3,  8,  -1, -1, -1, -1 },
  476.         { 1,  9,  4,  1,  4,  2,  2,  4,  6,  -1, -1, -1, -1, -1, -1, -1 },
  477.         { 8,  1,  3,  8,  6,  1,  8,  4,  6,  6,  10, 1,  -1, -1, -1, -1 },
  478.         { 10, 1,  0,  10, 0,  6,  6,  0,  4,  -1, -1, -1, -1, -1, -1, -1 },
  479.         { 4,  6,  3,  4,  3,  8,  6,  10, 3,  0,  3,  9,  10, 9,  3,  -1 },
  480.         { 10, 9,  4,  6,  10, 4,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  481.         { 4,  9,  5,  7,  6,  11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  482.         { 0,  8,  3,  4,  9,  5,  11, 7,  6,  -1, -1, -1, -1, -1, -1, -1 },
  483.         { 5,  0,  1,  5,  4,  0,  7,  6,  11, -1, -1, -1, -1, -1, -1, -1 },
  484.         { 11, 7,  6,  8,  3,  4,  3,  5,  4,  3,  1,  5,  -1, -1, -1, -1 },
  485.         { 9,  5,  4,  10, 1,  2,  7,  6,  11, -1, -1, -1, -1, -1, -1, -1 },
  486.         { 6,  11, 7,  1,  2,  10, 0,  8,  3,  4,  9,  5,  -1, -1, -1, -1 },
  487.         { 7,  6,  11, 5,  4,  10, 4,  2,  10, 4,  0,  2,  -1, -1, -1, -1 },
  488.         { 3,  4,  8,  3,  5,  4,  3,  2,  5,  10, 5,  2,  11, 7,  6,  -1 },
  489.         { 7,  2,  3,  7,  6,  2,  5,  4,  9,  -1, -1, -1, -1, -1, -1, -1 },
  490.         { 9,  5,  4,  0,  8,  6,  0,  6,  2,  6,  8,  7,  -1, -1, -1, -1 },
  491.         { 3,  6,  2,  3,  7,  6,  1,  5,  0,  5,  4,  0,  -1, -1, -1, -1 },
  492.         { 6,  2,  8,  6,  8,  7,  2,  1,  8,  4,  8,  5,  1,  5,  8,  -1 },
  493.         { 9,  5,  4,  10, 1,  6,  1,  7,  6,  1,  3,  7,  -1, -1, -1, -1 },
  494.         { 1,  6,  10, 1,  7,  6,  1,  0,  7,  8,  7,  0,  9,  5,  4,  -1 },
  495.         { 4,  0,  10, 4,  10, 5,  0,  3,  10, 6,  10, 7,  3,  7,  10, -1 },
  496.         { 7,  6,  10, 7,  10, 8,  5,  4,  10, 4,  8,  10, -1, -1, -1, -1 },
  497.         { 6,  9,  5,  6,  11, 9,  11, 8,  9,  -1, -1, -1, -1, -1, -1, -1 },
  498.         { 3,  6,  11, 0,  6,  3,  0,  5,  6,  0,  9,  5,  -1, -1, -1, -1 },
  499.         { 0,  11, 8,  0,  5,  11, 0,  1,  5,  5,  6,  11, -1, -1, -1, -1 },
  500.         { 6,  11, 3,  6,  3,  5,  5,  3,  1,  -1, -1, -1, -1, -1, -1, -1 },
  501.         { 1,  2,  10, 9,  5,  11, 9,  11, 8,  11, 5,  6,  -1, -1, -1, -1 },
  502.         { 0,  11, 3,  0,  6,  11, 0,  9,  6,  5,  6,  9,  1,  2,  10, -1 },
  503.         { 11, 8,  5,  11, 5,  6,  8,  0,  5,  10, 5,  2,  0,  2,  5,  -1 },
  504.         { 6,  11, 3,  6,  3,  5,  2,  10, 3,  10, 5,  3,  -1, -1, -1, -1 },
  505.         { 5,  8,  9,  5,  2,  8,  5,  6,  2,  3,  8,  2,  -1, -1, -1, -1 },
  506.         { 9,  5,  6,  9,  6,  0,  0,  6,  2,  -1, -1, -1, -1, -1, -1, -1 },
  507.         { 1,  5,  8,  1,  8,  0,  5,  6,  8,  3,  8,  2,  6,  2,  8,  -1 },
  508.         { 1,  5,  6,  2,  1,  6,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  509.         { 1,  3,  6,  1,  6,  10, 3,  8,  6,  5,  6,  9,  8,  9,  6,  -1 },
  510.         { 10, 1,  0,  10, 0,  6,  9,  5,  0,  5,  6,  0,  -1, -1, -1, -1 },
  511.         { 0,  3,  8,  5,  6,  10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  512.         { 10, 5,  6,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  513.         { 11, 5,  10, 7,  5,  11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  514.         { 11, 5,  10, 11, 7,  5,  8,  3,  0,  -1, -1, -1, -1, -1, -1, -1 },
  515.         { 5,  11, 7,  5,  10, 11, 1,  9,  0,  -1, -1, -1, -1, -1, -1, -1 },
  516.         { 10, 7,  5,  10, 11, 7,  9,  8,  1,  8,  3,  1,  -1, -1, -1, -1 },
  517.         { 11, 1,  2,  11, 7,  1,  7,  5,  1,  -1, -1, -1, -1, -1, -1, -1 },
  518.         { 0,  8,  3,  1,  2,  7,  1,  7,  5,  7,  2,  11, -1, -1, -1, -1 },
  519.         { 9,  7,  5,  9,  2,  7,  9,  0,  2,  2,  11, 7,  -1, -1, -1, -1 },
  520.         { 7,  5,  2,  7,  2,  11, 5,  9,  2,  3,  2,  8,  9,  8,  2,  -1 },
  521.         { 2,  5,  10, 2,  3,  5,  3,  7,  5,  -1, -1, -1, -1, -1, -1, -1 },
  522.         { 8,  2,  0,  8,  5,  2,  8,  7,  5,  10, 2,  5,  -1, -1, -1, -1 },
  523.         { 9,  0,  1,  5,  10, 3,  5,  3,  7,  3,  10, 2,  -1, -1, -1, -1 },
  524.         { 9,  8,  2,  9,  2,  1,  8,  7,  2,  10, 2,  5,  7,  5,  2,  -1 },
  525.         { 1,  3,  5,  3,  7,  5,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  526.         { 0,  8,  7,  0,  7,  1,  1,  7,  5,  -1, -1, -1, -1, -1, -1, -1 },
  527.         { 9,  0,  3,  9,  3,  5,  5,  3,  7,  -1, -1, -1, -1, -1, -1, -1 },
  528.         { 9,  8,  7,  5,  9,  7,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  529.         { 5,  8,  4,  5,  10, 8,  10, 11, 8,  -1, -1, -1, -1, -1, -1, -1 },
  530.         { 5,  0,  4,  5,  11, 0,  5,  10, 11, 11, 3,  0,  -1, -1, -1, -1 },
  531.         { 0,  1,  9,  8,  4,  10, 8,  10, 11, 10, 4,  5,  -1, -1, -1, -1 },
  532.         { 10, 11, 4,  10, 4,  5,  11, 3,  4,  9,  4,  1,  3,  1,  4,  -1 },
  533.         { 2,  5,  1,  2,  8,  5,  2,  11, 8,  4,  5,  8,  -1, -1, -1, -1 },
  534.         { 0,  4,  11, 0,  11, 3,  4,  5,  11, 2,  11, 1,  5,  1,  11, -1 },
  535.         { 0,  2,  5,  0,  5,  9,  2,  11, 5,  4,  5,  8,  11, 8,  5,  -1 },
  536.         { 9,  4,  5,  2,  11, 3,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  537.         { 2,  5,  10, 3,  5,  2,  3,  4,  5,  3,  8,  4,  -1, -1, -1, -1 },
  538.         { 5,  10, 2,  5,  2,  4,  4,  2,  0,  -1, -1, -1, -1, -1, -1, -1 },
  539.         { 3,  10, 2,  3,  5,  10, 3,  8,  5,  4,  5,  8,  0,  1,  9,  -1 },
  540.         { 5,  10, 2,  5,  2,  4,  1,  9,  2,  9,  4,  2,  -1, -1, -1, -1 },
  541.         { 8,  4,  5,  8,  5,  3,  3,  5,  1,  -1, -1, -1, -1, -1, -1, -1 },
  542.         { 0,  4,  5,  1,  0,  5,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  543.         { 8,  4,  5,  8,  5,  3,  9,  0,  5,  0,  3,  5,  -1, -1, -1, -1 },
  544.         { 9,  4,  5,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  545.         { 4,  11, 7,  4,  9,  11, 9,  10, 11, -1, -1, -1, -1, -1, -1, -1 },
  546.         { 0,  8,  3,  4,  9,  7,  9,  11, 7,  9,  10, 11, -1, -1, -1, -1 },
  547.         { 1,  10, 11, 1,  11, 4,  1,  4,  0,  7,  4,  11, -1, -1, -1, -1 },
  548.         { 3,  1,  4,  3,  4,  8,  1,  10, 4,  7,  4,  11, 10, 11, 4,  -1 },
  549.         { 4,  11, 7,  9,  11, 4,  9,  2,  11, 9,  1,  2,  -1, -1, -1, -1 },
  550.         { 9,  7,  4,  9,  11, 7,  9,  1,  11, 2,  11, 1,  0,  8,  3,  -1 },
  551.         { 11, 7,  4,  11, 4,  2,  2,  4,  0,  -1, -1, -1, -1, -1, -1, -1 },
  552.         { 11, 7,  4,  11, 4,  2,  8,  3,  4,  3,  2,  4,  -1, -1, -1, -1 },
  553.         { 2,  9,  10, 2,  7,  9,  2,  3,  7,  7,  4,  9,  -1, -1, -1, -1 },
  554.         { 9,  10, 7,  9,  7,  4,  10, 2,  7,  8,  7,  0,  2,  0,  7,  -1 },
  555.         { 3,  7,  10, 3,  10, 2,  7,  4,  10, 1,  10, 0,  4,  0,  10, -1 },
  556.         { 1,  10, 2,  8,  7,  4,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  557.         { 4,  9,  1,  4,  1,  7,  7,  1,  3,  -1, -1, -1, -1, -1, -1, -1 },
  558.         { 4,  9,  1,  4,  1,  7,  0,  8,  1,  8,  7,  1,  -1, -1, -1, -1 },
  559.         { 4,  0,  3,  7,  4,  3,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  560.         { 4,  8,  7,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  561.         { 9,  10, 8,  10, 11, 8,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  562.         { 3,  0,  9,  3,  9,  11, 11, 9,  10, -1, -1, -1, -1, -1, -1, -1 },
  563.         { 0,  1,  10, 0,  10, 8,  8,  10, 11, -1, -1, -1, -1, -1, -1, -1 },
  564.         { 3,  1,  10, 11, 3,  10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  565.         { 1,  2,  11, 1,  11, 9,  9,  11, 8,  -1, -1, -1, -1, -1, -1, -1 },
  566.         { 3,  0,  9,  3,  9,  11, 1,  2,  9,  2,  11, 9,  -1, -1, -1, -1 },
  567.         { 0,  2,  11, 8,  0,  11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  568.         { 3,  2,  11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  569.         { 2,  3,  8,  2,  8,  10, 10, 8,  9,  -1, -1, -1, -1, -1, -1, -1 },
  570.         { 9,  10, 2,  0,  9,  2,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  571.         { 2,  3,  8,  2,  8,  10, 0,  1,  8,  1,  10, 8,  -1, -1, -1, -1 },
  572.         { 1,  10, 2,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  573.         { 1,  3,  8,  9,  1,  8,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  574.         { 0,  9,  1,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  575.         { 0,  3,  8,  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
  576.         { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }
  577. };
  578.  
  579. static inline Vec3 interpolate(float val0, float val1, const Vec3& p0, const Vec3& p1)
  580. {
  581.         if (std::abs(val0) < FLT_EPSILON)
  582.                 return p0;
  583.         if (std::abs(val1) < FLT_EPSILON)
  584.                 return p1;
  585.         if (std::abs(val0 - val1) < FLT_EPSILON)
  586.                 return p1;
  587.         float alpha = (0 - val0) / (val1 - val0);
  588.         Vec3 p;
  589.         p.x = p0.x + alpha * (p1.x - p0.x);
  590.         p.y = p0.y + alpha * (p1.y - p0.y);
  591.         p.z = p0.z + alpha * (p1.z - p0.z);
  592.         return p;
  593. }
  594.  
  595. static inline void DisplayDensity(IMergedMeshesManager* manager, AABB _bbox, uint8 dim)
  596. {
  597.         const AABB& bbox = _bbox;
  598.         const Vec3 extents = (bbox.max - bbox.min);
  599.         IRenderAuxGeom* pAuxGeom = gEnv->pRenderer->GetIRenderAuxGeom();
  600.         SAuxGeomRenderFlags old_flags = pAuxGeom->GetRenderFlags();
  601.         SAuxGeomRenderFlags new_flags = old_flags;
  602.         new_flags.SetCullMode(e_CullModeNone);
  603.         new_flags.SetAlphaBlendMode(e_AlphaBlended);
  604.         pAuxGeom->SetRenderFlags(new_flags);
  605.  
  606.         Vec3 vertlist[12], v[8], e[2];
  607.         float d[8][MMRM_MAX_SURFACE_TYPES];
  608.         ISurfaceType* surfaceTypes[8][MMRM_MAX_SURFACE_TYPES];
  609.         const float rcp = 1.f / (float)(dim - 1);
  610.         size_t c[8];
  611.  
  612.         ColorF col0, col1, col2;
  613.         col0.r = 0.8f;
  614.         col0.g = 0.1f;
  615.         col0.b = 0.2f;
  616.         col0.a = 0.85f;
  617.  
  618.         col1.r = 0.1f;
  619.         col1.g = 0.1f;
  620.         col1.b = 0.6f;
  621.         col1.a = 0.80f;
  622.  
  623.         col1.r = 0.1f;
  624.         col1.g = 0.8f;
  625.         col1.b = 0.1f;
  626.         col1.a = 0.90f;
  627.  
  628.         // Extract a surface from each grid cell if the cell straddles
  629.         // the boundary of the cell
  630.         for (uint8 i = 0; i < dim; ++i)
  631.                 for (uint8 j = 0; j < dim; ++j)
  632.                         for (uint8 k = 0; k < dim; ++k)
  633.                         {
  634.                                 const float min_x = bbox.min.x + ((i + 0) * rcp) * extents.x;
  635.                                 const float min_y = bbox.min.y + ((j + 0) * rcp) * extents.y;
  636.                                 const float min_z = bbox.min.z + ((k + 0) * rcp) * extents.z;
  637.  
  638.                                 const float max_x = bbox.min.x + ((i + 1) * rcp) * extents.x;
  639.                                 const float max_y = bbox.min.y + ((j + 1) * rcp) * extents.y;
  640.                                 const float max_z = bbox.min.z + ((k + 1) * rcp) * extents.z;
  641.  
  642.                                 memset(surfaceTypes, 0, sizeof(surfaceTypes));
  643.                                 memset(d, 0, sizeof(d));
  644.  
  645.                                 v[0] = Vec3(min_x, min_y, min_z);
  646.                                 v[1] = Vec3(max_x, min_y, min_z);
  647.                                 v[2] = Vec3(min_x, max_y, min_z);
  648.                                 v[3] = Vec3(max_x, max_y, min_z);
  649.                                 v[4] = Vec3(min_x, min_y, max_z);
  650.                                 v[5] = Vec3(max_x, min_y, max_z);
  651.                                 v[6] = Vec3(min_x, max_y, max_z);
  652.                                 v[7] = Vec3(max_x, max_y, max_z);
  653.  
  654.                                 c[0] = manager->QueryDensity(v[0], surfaceTypes[0], d[0]);
  655.                                 c[1] = manager->QueryDensity(v[1], surfaceTypes[1], d[1]);
  656.                                 c[2] = manager->QueryDensity(v[2], surfaceTypes[2], d[2]);
  657.                                 c[3] = manager->QueryDensity(v[3], surfaceTypes[3], d[3]);
  658.                                 c[4] = manager->QueryDensity(v[4], surfaceTypes[0], d[4]);
  659.                                 c[5] = manager->QueryDensity(v[5], surfaceTypes[1], d[5]);
  660.                                 c[6] = manager->QueryDensity(v[6], surfaceTypes[2], d[6]);
  661.                                 c[7] = manager->QueryDensity(v[7], surfaceTypes[3], d[7]);
  662.  
  663.                                 for (size_t s = 0; s < MMRM_MAX_SURFACE_TYPES; ++s)
  664.                                 {
  665.                                         int32 inside = 0;
  666.                                         inside |= (1 << 0) & - (d[0][s] > 0.f);
  667.                                         inside |= (1 << 1) & - (d[1][s] > 0.f);
  668.                                         inside |= (1 << 2) & - (d[2][s] > 0.f);
  669.                                         inside |= (1 << 3) & - (d[3][s] > 0.f);
  670.                                         inside |= (1 << 4) & - (d[4][s] > 0.f);
  671.                                         inside |= (1 << 5) & - (d[5][s] > 0.f);
  672.                                         inside |= (1 << 6) & - (d[6][s] > 0.f);
  673.                                         inside |= (1 << 7) & - (d[7][s] > 0.f);
  674.                                         if (inside == 0x0 || inside == 0xff)
  675.                                                 continue;
  676.  
  677.                                         int32 cubeindex = 0;
  678.                                         cubeindex |= 1 & - iszero(inside & (1 << (0 + 0 * 2 + 0 * 4)));
  679.                                         cubeindex |= 2 & - iszero(inside & (1 << (1 + 0 * 2 + 0 * 4)));
  680.                                         cubeindex |= 4 & - iszero(inside & (1 << (1 + 1 * 2 + 0 * 4)));
  681.                                         cubeindex |= 8 & - iszero(inside & (1 << (0 + 1 * 2 + 0 * 4)));
  682.                                         cubeindex |= 16 & - iszero(inside & (1 << (0 + 0 * 2 + 1 * 4)));
  683.                                         cubeindex |= 32 & - iszero(inside & (1 << (1 + 0 * 2 + 1 * 4)));
  684.                                         cubeindex |= 64 & - iszero(inside & (1 << (1 + 1 * 2 + 1 * 4)));
  685.                                         cubeindex |= 128 & - iszero(inside & (1 << (0 + 1 * 2 + 1 * 4)));
  686.  
  687.                                         e[0].x = min_x;
  688.                                         e[0].y = min_y;
  689.                                         e[0].z = min_z;
  690.                                         e[1].x = max_x;
  691.                                         e[1].y = max_y;
  692.                                         e[1].z = max_z;
  693.  
  694.                                         // Define vertices on the edges intersecting the surface
  695.                                         const uint16 edge_code = s_marching_cubes_edge_table[cubeindex];
  696.                                         if (edge_code & 1) vertlist[0] = interpolate(d[(0 + 0 * 2 + 0 * 4)][s], d[(1 + 0 * 2 + 0 * 4)][s], Vec3(e[0].x, e[0].y, e[0].z), Vec3(e[1].x, e[0].y, e[0].z));
  697.                                         if (edge_code & 2) vertlist[1] = interpolate(d[(1 + 0 * 2 + 0 * 4)][s], d[(1 + 1 * 2 + 0 * 4)][s], Vec3(e[1].x, e[0].y, e[0].z), Vec3(e[1].x, e[1].y, e[0].z));
  698.                                         if (edge_code & 4) vertlist[2] = interpolate(d[(1 + 1 * 2 + 0 * 4)][s], d[(0 + 1 * 2 + 0 * 4)][s], Vec3(e[1].x, e[1].y, e[0].z), Vec3(e[0].x, e[1].y, e[0].z));
  699.                                         if (edge_code & 8) vertlist[3] = interpolate(d[(0 + 1 * 2 + 0 * 4)][s], d[(0 + 0 * 2 + 0 * 4)][s], Vec3(e[0].x, e[1].y, e[0].z), Vec3(e[0].x, e[0].y, e[0].z));
  700.                                         if (edge_code & 16) vertlist[4] = interpolate(d[(0 + 0 * 2 + 1 * 4)][s], d[(1 + 0 * 2 + 1 * 4)][s], Vec3(e[0].x, e[0].y, e[1].z), Vec3(e[1].x, e[0].y, e[1].z));
  701.                                         if (edge_code & 32) vertlist[5] = interpolate(d[(1 + 0 * 2 + 1 * 4)][s], d[(1 + 1 * 2 + 1 * 4)][s], Vec3(e[1].x, e[0].y, e[1].z), Vec3(e[1].x, e[1].y, e[1].z));
  702.                                         if (edge_code & 64) vertlist[6] = interpolate(d[(1 + 1 * 2 + 1 * 4)][s], d[(0 + 1 * 2 + 1 * 4)][s], Vec3(e[1].x, e[1].y, e[1].z), Vec3(e[0].x, e[1].y, e[1].z));
  703.                                         if (edge_code & 128) vertlist[7] = interpolate(d[(0 + 1 * 2 + 1 * 4)][s], d[(0 + 0 * 2 + 1 * 4)][s], Vec3(e[0].x, e[1].y, e[1].z), Vec3(e[0].x, e[0].y, e[1].z));
  704.                                         if (edge_code & 256) vertlist[8] = interpolate(d[(0 + 0 * 2 + 0 * 4)][s], d[(0 + 0 * 2 + 1 * 4)][s], Vec3(e[0].x, e[0].y, e[0].z), Vec3(e[0].x, e[0].y, e[1].z));
  705.                                         if (edge_code & 512) vertlist[9] = interpolate(d[(1 + 0 * 2 + 0 * 4)][s], d[(1 + 0 * 2 + 1 * 4)][s], Vec3(e[1].x, e[0].y, e[0].z), Vec3(e[1].x, e[0].y, e[1].z));
  706.                                         if (edge_code & 1024) vertlist[10] = interpolate(d[(1 + 1 * 2 + 0 * 4)][s], d[(1 + 1 * 2 + 1 * 4)][s], Vec3(e[1].x, e[1].y, e[0].z), Vec3(e[1].x, e[1].y, e[1].z));
  707.                                         if (edge_code & 2048) vertlist[11] = interpolate(d[(0 + 1 * 2 + 0 * 4)][s], d[(0 + 1 * 2 + 1 * 4)][s], Vec3(e[0].x, e[1].y, e[0].z), Vec3(e[0].x, e[1].y, e[1].z));
  708.  
  709.                                         // Extract triangles
  710.                                         for (size_t l = 0; s_marching_cubes_tri_table[cubeindex][l] != -1; l += 3)
  711.                                         {
  712.                                                 pAuxGeom->DrawTriangle(
  713.                                                   vertlist[s_marching_cubes_tri_table[cubeindex][l + 0]], col0,
  714.                                                   vertlist[s_marching_cubes_tri_table[cubeindex][l + 1]], col1,
  715.                                                   vertlist[s_marching_cubes_tri_table[cubeindex][l + 2]], col2);
  716.                                         }
  717.                                 }
  718.                         }
  719.         pAuxGeom->SetRenderFlags(old_flags);
  720. }
  721.  
  722. static inline void DisplayDensitySpheres(IMergedMeshesManager* manager, AABB _bbox, int dim)
  723. {
  724.         const AABB& bbox = _bbox;
  725.         const Vec3 extents = (bbox.max - bbox.min);
  726.         IRenderAuxGeom* pAuxGeom = gEnv->pRenderer->GetIRenderAuxGeom();
  727.         SAuxGeomRenderFlags old_flags = pAuxGeom->GetRenderFlags();
  728.         SAuxGeomRenderFlags new_flags = old_flags;
  729.         new_flags.SetCullMode(e_CullModeNone);
  730.         new_flags.SetAlphaBlendMode(e_AlphaBlended);
  731.         pAuxGeom->SetRenderFlags(new_flags);
  732.  
  733.         Vec3 vertlist[12], v[8], e[2];
  734.         float d[8][MMRM_MAX_SURFACE_TYPES];
  735.         ISurfaceType* surfaceTypes[8][MMRM_MAX_SURFACE_TYPES];
  736.         const float rcp = 1.f / (float)(dim - 1);
  737.         size_t c[8];
  738.  
  739.         ColorF col0, col1, col2;
  740.         col0.r = 0.8f;
  741.         col0.g = 0.1f;
  742.         col0.b = 0.2f;
  743.         col0.a = 0.85f;
  744.  
  745.         col1.r = 0.1f;
  746.         col1.g = 0.1f;
  747.         col1.b = 0.6f;
  748.         col1.a = 0.80f;
  749.  
  750.         col1.r = 0.1f;
  751.         col1.g = 0.8f;
  752.         col1.b = 0.1f;
  753.         col1.a = 0.90f;
  754.  
  755.         // Extract a surface from each grid cell if the cell straddles
  756.         // the boundary of the cell
  757.         for (int i = 0; i < dim; ++i)
  758.                 for (int j = 0; j < dim; ++j)
  759.                         for (int k = 0; k < dim; ++k)
  760.                         {
  761.                                 const float min_x = bbox.min.x + ((i + 0) * rcp) * extents.x + extents.x * rcp * 0.5f;
  762.                                 const float min_y = bbox.min.y + ((j + 0) * rcp) * extents.y + extents.y * rcp * 0.5f;
  763.                                 const float min_z = bbox.min.z + ((k + 0) * rcp) * extents.z + extents.z * rcp * 0.5f;
  764.                                 c[0] = manager->QueryDensity(Vec3(min_x, min_y, min_z), surfaceTypes[0], d[0]);
  765.  
  766.                                 for (size_t s = 0; s < MMRM_MAX_SURFACE_TYPES; ++s)
  767.                                 {
  768.                                         if (s < c[0] && d[0][s] > 0.f)
  769.                                         {
  770.                                                 pAuxGeom->DrawSphere(Vec3(min_x, min_y, min_z), extents.x * rcp * 0.5f, Col_Red, true);
  771.                                         }
  772.                                         else
  773.                                         {
  774.                                                 //pAuxGeom->DrawSphere(Vec3(min_x, min_y, min_z), extents.x*rcp*0.05f, Col_Green, false);
  775.                                         }
  776.                                 }
  777.                         }
  778.         pAuxGeom->SetRenderFlags(old_flags);
  779. }
  780.  
  781. }
  782.  
  783. #include <CryCore/TypeInfo_impl.h>
  784.  
  785. STRUCT_INFO_BEGIN(SMergedMeshInstanceCompressed)
  786. STRUCT_VAR_INFO(pos_x, TYPE_INFO(uint32))
  787. STRUCT_VAR_INFO(pos_y, TYPE_INFO(uint32))
  788. STRUCT_VAR_INFO(pos_z, TYPE_INFO(uint32))
  789. STRUCT_VAR_INFO(scale, TYPE_INFO(uint8))
  790. STRUCT_VAR_INFO(rot, TYPE_ARRAY(4, TYPE_INFO(int8)))
  791. STRUCT_INFO_END(SMergedMeshInstanceCompressed)
  792.  
  793. STRUCT_INFO_BEGIN(SMergedMeshSectorChunk)
  794. STRUCT_VAR_INFO(ver, TYPE_INFO(uint32))
  795. STRUCT_VAR_INFO(i, TYPE_INFO(uint32))
  796. STRUCT_VAR_INFO(j, TYPE_INFO(uint32))
  797. STRUCT_VAR_INFO(k, TYPE_INFO(uint32))
  798. STRUCT_VAR_INFO(m_StatInstGroupID, TYPE_INFO(uint32))
  799. STRUCT_VAR_INFO(m_nSamples, TYPE_INFO(uint32))
  800. STRUCT_INFO_END(SMergedMeshSectorChunk)
  801.  
  802. DECLARE_JOB(
  803.   "PVRNCullSamples"
  804.   , TPVRNCullRenderMesh
  805.   , SMMRMGroupHeader::CullInstances);
  806.  
  807. DECLARE_JOB(
  808.   "PVRNUpdateSpines"
  809.   , TPVRNUpdateRenderMeshSpines
  810.   , SMMRMUpdateContext::MergeInstanceMeshesSpines);
  811.  
  812. DECLARE_JOB(
  813.   "PVRNUpdateDeform"
  814.   , TPVRNUpdateRenderMeshDeform
  815.   , SMMRMUpdateContext::MergeInstanceMeshesDeform);
  816.  
  817. DECLARE_JOB(
  818.   "MMRM_SortActiveInstances"
  819.   , TMMRM_SortActiveInstances
  820.   , CMergedMeshesManager::SortActiveInstances_Async);
  821.  
  822. DECLARE_JOB(
  823.   "MergedMesh_InitializeSamples"
  824.   , TMergedMesh_InitializeSamples
  825.   , CMergedMeshRenderNode::InitializeSamples);
  826.  
  827. DECLARE_JOB(
  828.   "MergedMesh_InitializeSpines"
  829.   , TMergedMesh_InitializeSpines
  830.   , CMergedMeshRenderNode::InitializeSpines);
  831.  
  832. // ToDo: pack into struct to ensure better locality in data segment
  833. struct SMergedMeshGlobals
  834. {
  835.         CRY_ALIGN(16) CCamera camera;
  836.         Vec3   lastFramesCamPos;
  837.         uint32 frameId;
  838.         float  dt;
  839.         float  dtscale;
  840.         float  abstime;
  841. };
  842. static CRY_ALIGN(128) SMergedMeshGlobals s_mmrm_globals;
  843.  
  844. template<typename T>
  845. static inline void resize_list(T*& list, size_t nsize, size_t align)
  846. {
  847.         MEMORY_SCOPE_CHECK_HEAP();
  848.         list = (T*) CryModuleReallocAlign(list, (nsize * sizeof(T) + (align - 1)) & ~(align - 1), align);
  849. }
  850.  
  851. template<typename T>
  852. static inline void pool_resize_list(T*& list, size_t nsize, size_t align)
  853. {
  854.         MEMORY_SCOPE_CHECK_HEAP();
  855.         AUTO_LOCK(s_MergedMeshPoolLock);
  856.  
  857.         if (nsize == 0)
  858.         {
  859.                 if (s_MergedMeshPool && !gEnv->IsEditor() && s_MergedMeshPool->UsableSize(list))
  860.                 {
  861.                         s_MergedMeshPool->Free(list);
  862.                         list = NULL;
  863.                         return;
  864.                 }
  865.                 CryModuleMemalignFree(list);
  866.                 list = NULL;
  867.                 return;
  868.         }
  869.  
  870.         if (s_MergedMeshPool && !gEnv->IsEditor())
  871.         {
  872.                 size_t osize = 0;
  873.                 if (!list || (osize = s_MergedMeshPool->UsableSize(list)) != 0u)
  874.                 {
  875.                         T* nList = (T*) s_MergedMeshPool->ReallocAlign(list, (nsize * sizeof(T) + (align - 1)) & ~(align - 1), align, "mergedmesh");
  876.                         if (nList == NULL)
  877.                         {
  878.                                 memcpy(nList = (T*)CryModuleMemalign((nsize * sizeof(T) + (align - 1)) & ~(align - 1), align), list, osize);
  879.                                 if (osize && list)
  880.                                         s_MergedMeshPool->Free(list);
  881.                                 else if (list)
  882.                                         CryModuleMemalignFree(list);
  883.                         }
  884.                         if ((list = nList) != NULL)
  885.                                 return;
  886.                 }
  887.         }
  888.         resize_list(list, nsize, align);
  889.         return;
  890. }
  891.  
  892. static inline void pool_free(void* ptr)
  893. {
  894.         AUTO_LOCK(s_MergedMeshPoolLock);
  895.         if (s_MergedMeshPool && s_MergedMeshPool->UsableSize(ptr))
  896.         {
  897.                 s_MergedMeshPool->Free(ptr);
  898.                 return;
  899.         }
  900.         CryModuleMemalignFree(ptr);
  901. }
  902.  
  903. static void BuildSphereSet(
  904.   AABB& bbox
  905.   , primitives::sphere* pColliders
  906.   , int& nColliders
  907.   , const Vec3& pos
  908.   , const quaternionf& q
  909.   , const AABB& visibleAABB)
  910. {
  911.         Vec3 centre = ((bbox.max + bbox.min) * 0.5f);
  912.         Vec3 size = (bbox.max - bbox.min) * 0.5f;
  913.  
  914.         int max_axis = size[0] > size[1] ? 0 : 1;
  915.         max_axis = size[max_axis] > size[2] ? max_axis : 2;
  916.         int min_axis =
  917.           size[inc_mod3[max_axis]] < size[dec_mod3[max_axis]]
  918.           ? inc_mod3[max_axis]
  919.           : dec_mod3[max_axis];
  920.  
  921.         if (size[min_axis] / (max(size[max_axis], FLT_EPSILON)) > 0.75f)
  922.         {
  923.                 if (nColliders < MMRM_MAX_COLLIDERS)
  924.                 {
  925.                         float radius = size[min_axis];
  926.                         centre = pos + q * centre;
  927.                         if (Overlap::Sphere_AABB(Sphere(centre, radius), visibleAABB))
  928.                         {
  929.                                 pColliders[nColliders].center = centre;
  930.                                 pColliders[nColliders++].r = radius;
  931.                         }
  932.                 }
  933.         }
  934.         else
  935.         {
  936.                 int plane_axis[2] = { max_axis, ((inc_mod3[max_axis] != min_axis) ? inc_mod3[max_axis] : dec_mod3[max_axis]) };
  937.  
  938.                 Vec3 base;
  939.                 base[min_axis] = centre[min_axis];
  940.                 base[plane_axis[0]] = centre[plane_axis[0]] - size[plane_axis[0]] + size[plane_axis[0]] * 0.5f;
  941.                 base[plane_axis[1]] = centre[plane_axis[1]] - size[plane_axis[1]] + size[plane_axis[1]] * 0.5f;
  942.                 ;
  943.                 float radius = size[min_axis] * 1.5f;
  944.  
  945.                 Vec3 sphcent = pos + q * centre;
  946.                 if (Overlap::Sphere_AABB(Sphere(sphcent, radius), visibleAABB) && nColliders < MMRM_MAX_COLLIDERS)
  947.                 {
  948.                         pColliders[nColliders].center = sphcent;
  949.                         pColliders[nColliders++].r = radius;
  950.                 }
  951.                 for (float i = 0; i < 2.f; i += 1.f)
  952.                         for (float j = 0; j < 2.f && nColliders < MMRM_MAX_COLLIDERS; j += 1.f)
  953.                         {
  954.                                 sphcent[min_axis] = base[min_axis];
  955.                                 sphcent[plane_axis[0]] = base[plane_axis[0]] + ((float)i * 0.5f) * size[plane_axis[0]] * 2.f;
  956.                                 sphcent[plane_axis[1]] = base[plane_axis[1]] + ((float)j * 0.5f) * size[plane_axis[1]] * 2.f;
  957.  
  958.                                 sphcent = pos + q * sphcent;
  959.                                 if (Overlap::Sphere_AABB(Sphere(sphcent, radius), visibleAABB))
  960.                                 {
  961.                                         pColliders[nColliders].center = sphcent;
  962.                                         pColliders[nColliders++].r = radius;
  963.                                 }
  964.                         }
  965.         }
  966. }
  967.  
  968. static inline void ExtractSphereSet(
  969.   IPhysicalEntity* pent
  970.   , primitives::sphere* pColliders
  971.   , int& nColliders
  972.   , const AABB& visibleAABB
  973.   , bool partsOnly = false)
  974. {
  975.         primitives::cylinder cylinder;
  976.         pe_status_pos statusPos;
  977.         pe_status_nparts statusNParts;
  978.         int nParts = 0;
  979.         Vec3 delta, pos;
  980.         quaternionf q;
  981.         if (pent->GetStatus(&statusPos) == 0)
  982.                 return;
  983.         pos = statusPos.pos;
  984.         q = statusPos.q;
  985.         float scale = statusPos.scale;
  986.         switch (pent->GetType())
  987.         {
  988.         case PE_LIVING:
  989.                 if ((delta = (statusPos.BBox[1] - statusPos.BBox[0])).len2() < sqr(3.5f))
  990.                 {
  991.                         nParts = pent->GetStatus(&statusNParts);
  992.                         for (statusPos.ipart = 0; statusPos.ipart < nParts && nColliders < MMRM_MAX_COLLIDERS; ++statusPos.ipart)
  993.                         {
  994.                                 if (!pent->GetStatus(&statusPos))
  995.                                         continue;
  996.                                 if (!statusPos.pGeom)
  997.                                         continue;
  998.                                 switch (statusPos.pGeom->GetType())
  999.                                 {
  1000.                                 case GEOM_CAPSULE:
  1001.                                 case GEOM_CYLINDER:
  1002.                                         statusPos.pGeom->GetPrimitive(0, &cylinder);
  1003.                                         for (int i = 0; i < 2 && nColliders < MMRM_MAX_COLLIDERS; ++i)
  1004.                                         {
  1005.                                                 pColliders[nColliders].center = statusPos.pos + statusPos.q * (cylinder.center + ((float)(i - 1) * cylinder.axis * cylinder.hh * 2.75f));
  1006.                                                 pColliders[nColliders++].r = cylinder.r * statusPos.scale * scale * 1.75f;
  1007.                                         }
  1008.                                         break;
  1009.                                 case GEOM_SPHERE:
  1010.                                         statusPos.pGeom->GetPrimitive(0, &pColliders[nColliders++]);
  1011.                                         break;
  1012.                                 default:
  1013.                                         break;
  1014.                                 }
  1015.                         }
  1016.                 }
  1017.                 else
  1018.                 {
  1019.                         if (pent->GetiForeignData() == PHYS_FOREIGN_ID_ENTITY)
  1020.                         {
  1021.                                 IEntity* pEntity = (IEntity*)pent->GetForeignData(PHYS_FOREIGN_ID_ENTITY);
  1022.                                 IF (!pEntity, 0)
  1023.                                         return;
  1024.                                 ICharacterInstance* pCharInstance = pEntity->GetCharacter(0);
  1025.                                 IF (!pCharInstance, 0)
  1026.                                         return;
  1027.                                 ISkeletonPose* pSkeletonPose = pCharInstance->GetISkeletonPose();
  1028.                                 IF (!pSkeletonPose, 0)
  1029.                                         return;
  1030.                                 IPhysicalEntity* pEnt = pSkeletonPose->GetCharacterPhysics();
  1031.                                 IF (!pEnt || pEnt->GetType() != PE_ARTICULATED, 0)
  1032.                                         return;
  1033.                                 ExtractSphereSet(pEnt, pColliders, nColliders, visibleAABB, true);
  1034.                         }
  1035.                 }
  1036.                 break;
  1037.         case PE_ARTICULATED:
  1038.                 partsOnly = true;
  1039.         default:   // fallthrough Z
  1040.                 if ((delta = (statusPos.BBox[1] - statusPos.BBox[0])).len2() > sqr(3.5f))
  1041.                 {
  1042.                         primitives::box box;
  1043.                         bool added = false;
  1044.                         AABB bbox = AABB(AABB::RESET);
  1045.                         nParts = pent->GetStatus(&statusNParts);
  1046.                         for (statusPos.ipart = 0; statusPos.ipart < nParts; ++statusPos.ipart)
  1047.                         {
  1048.                                 statusPos.flags = status_local;
  1049.                                 if (!pent->GetStatus(&statusPos))
  1050.                                         continue;
  1051.                                 if (!statusPos.pGeom || (statusPos.flagsAND & geom_squashy))
  1052.                                         continue;
  1053.                                 statusPos.pGeom->GetBBox(&box);
  1054.  
  1055.                                 Vec3 centre = box.center * statusPos.scale;
  1056.                                 Vec3 size = box.size * statusPos.scale;
  1057.  
  1058.                                 centre = statusPos.pos + statusPos.q * centre;
  1059.                                 Matrix33 orientationTM = Matrix33(statusPos.q) * box.Basis.GetTransposed();
  1060.  
  1061.                                 if (partsOnly)
  1062.                                 {
  1063.                                         AABB lbbox = AABB(AABB::RESET);
  1064.                                         lbbox.Add(centre + orientationTM * Vec3(size.x, size.y, size.z));
  1065.                                         lbbox.Add(centre + orientationTM * Vec3(size.x, size.y, -size.z));
  1066.                                         lbbox.Add(centre + orientationTM * Vec3(size.x, -size.y, size.z));
  1067.                                         lbbox.Add(centre + orientationTM * Vec3(size.x, -size.y, -size.z));
  1068.                                         lbbox.Add(centre + orientationTM * Vec3(-size.x, size.y, size.z));
  1069.                                         lbbox.Add(centre + orientationTM * Vec3(-size.x, size.y, -size.z));
  1070.                                         lbbox.Add(centre + orientationTM * Vec3(-size.x, -size.y, size.z));
  1071.                                         lbbox.Add(centre + orientationTM * Vec3(-size.x, -size.y, -size.z));
  1072.                                         BuildSphereSet(lbbox, pColliders, nColliders, pos, q, visibleAABB);
  1073.                                         continue;
  1074.                                 }
  1075.                                 else
  1076.                                 {
  1077.                                         bbox.Add(centre + orientationTM * Vec3(size.x, size.y, size.z));
  1078.                                         bbox.Add(centre + orientationTM * Vec3(size.x, size.y, -size.z));
  1079.                                         bbox.Add(centre + orientationTM * Vec3(size.x, -size.y, size.z));
  1080.                                         bbox.Add(centre + orientationTM * Vec3(size.x, -size.y, -size.z));
  1081.                                         bbox.Add(centre + orientationTM * Vec3(-size.x, size.y, size.z));
  1082.                                         bbox.Add(centre + orientationTM * Vec3(-size.x, size.y, -size.z));
  1083.                                         bbox.Add(centre + orientationTM * Vec3(-size.x, -size.y, size.z));
  1084.                                         bbox.Add(centre + orientationTM * Vec3(-size.x, -size.y, -size.z));
  1085.                                         added = true;
  1086.                                 }
  1087.                         }
  1088.                         if (added)
  1089.                         {
  1090.                                 BuildSphereSet(bbox, pColliders, nColliders, pos, q, visibleAABB);
  1091.                         }
  1092.                 }
  1093.                 else
  1094.                 {
  1095.                         pColliders[nColliders].center = pos + ((statusPos.BBox[0] + statusPos.BBox[1]) * 0.5f);
  1096.                         pColliders[nColliders++].r = (statusPos.BBox[0] - statusPos.BBox[1]).len() * 0.25f * scale;
  1097.                 }
  1098.                 break;
  1099.         }
  1100. }
  1101.  
  1102. static inline bool SortCollider(const primitives::sphere& a, const primitives::sphere& b)
  1103. {
  1104.         return a.r > b.r;
  1105. }
  1106.  
  1107. static inline void QueryColliders(primitives::sphere*& pColliders, int& nColliders, const AABB& visibleAABB)
  1108. {
  1109.         if (!pColliders) resize_list(pColliders, MMRM_MAX_COLLIDERS, 16);
  1110.         nColliders = 0;
  1111.         IPhysicalEntity* pents[MMRM_MAX_COLLIDERS];
  1112.         IPhysicalEntity** pentList = &pents[0];
  1113.         int nents = gEnv->pPhysicalWorld->GetEntitiesInBox(
  1114.           visibleAABB.min, visibleAABB.max,
  1115.           pentList,
  1116.           ent_sleeping_rigid | ent_rigid | ent_living | ent_allocate_list,
  1117.           MMRM_MAX_COLLIDERS);
  1118.         nColliders = 0;
  1119.         for (int j = 0; j < min(nents, MMRM_MAX_COLLIDERS) && nColliders < MMRM_MAX_COLLIDERS; ++j)
  1120.         {
  1121.                 if (!pentList[j])
  1122.                         continue;
  1123.                 ExtractSphereSet(pentList[j], pColliders, nColliders, visibleAABB);
  1124.         }
  1125.         std::sort(pColliders, pColliders + nColliders, SortCollider);
  1126.         if (pents != pentList)
  1127.                 gEnv->pPhysicalWorld->GetPhysUtils()->DeletePointer(pentList);
  1128. }
  1129.  
  1130. inline void QueryProjectiles(SMMRMProjectile*& pColliders, int& nColliders, const AABB& visibleAABB)
  1131. {
  1132.         if (!pColliders) resize_list(pColliders, MMRM_MAX_PROJECTILES, 16);
  1133.         nColliders = 0;
  1134.         ReadLock lock(Cry3DEngineBase::m_pMergedMeshesManager->m_ProjectileLock);
  1135.         CMergedMeshesManager* pMM = Cry3DEngineBase::m_pMergedMeshesManager;
  1136.         for (size_t i = 0, end = pMM->m_Projectiles.size(); nColliders < MMRM_MAX_PROJECTILES && i < end; ++i)
  1137.         {
  1138.                 const SProjectile& projectile = pMM->m_Projectiles[i];
  1139.                 if (Overlap::Lineseg_AABB(Lineseg(projectile.initial_pos, projectile.current_pos), visibleAABB) == false)
  1140.                         continue;
  1141.                 pColliders[nColliders].pos[0] = projectile.initial_pos;
  1142.                 pColliders[nColliders].pos[1] = projectile.current_pos;
  1143.                 pColliders[nColliders].dir = projectile.direction;
  1144.                 pColliders[nColliders++].r = projectile.size;
  1145.         }
  1146. }
  1147.  
  1148. static inline void SampleWind(Vec3*& wind, const AABB& bbox)
  1149. {
  1150.         if (!wind) resize_list(wind, cube(MMRM_WIND_DIM), 16);
  1151.         for (size_t x = 0; x < MMRM_WIND_DIM; ++x)
  1152.                 for (size_t y = 0; y < MMRM_WIND_DIM; ++y)
  1153.                         for (size_t z = 0; z < MMRM_WIND_DIM; ++z)
  1154.                         {
  1155.                                 wind[x + y * MMRM_WIND_DIM + z * MMRM_WIND_DIM * MMRM_WIND_DIM].x = bbox.min.x + (x / (MMRM_WIND_DIM - 1.f)) * ((bbox.max.x - bbox.min.x));
  1156.                                 wind[x + y * MMRM_WIND_DIM + z * MMRM_WIND_DIM * MMRM_WIND_DIM].y = bbox.min.y + (y / (MMRM_WIND_DIM - 1.f)) * ((bbox.max.y - bbox.min.y));
  1157.                                 wind[x + y * MMRM_WIND_DIM + z * MMRM_WIND_DIM * MMRM_WIND_DIM].z = bbox.min.z + (z / (MMRM_WIND_DIM - 1.f)) * ((bbox.max.z - bbox.min.z));
  1158.                         }
  1159. #if MMRM_VISUALIZE_WINDSAMPLES
  1160.         Vec3* copy = new Vec3[cube(MMRM_WIND_DIM)];
  1161.         memcpy(copy, wind, sizeof(Vec3) * cube(MMRM_WIND_DIM));
  1162. #endif
  1163.         if (!Cry3DEngineBase::Get3DEngine()->SampleWind(wind, (MMRM_WIND_DIM)*(MMRM_WIND_DIM)*(MMRM_WIND_DIM), bbox, false))
  1164.         {
  1165.                 for (size_t x = 0; x < MMRM_WIND_DIM; ++x)
  1166.                         for (size_t y = 0; y < MMRM_WIND_DIM; ++y)
  1167.                                 for (size_t z = 0; z < MMRM_WIND_DIM; ++z)
  1168.                                 {
  1169.                                         wind[x + y * MMRM_WIND_DIM + z * MMRM_WIND_DIM * MMRM_WIND_DIM] = Vec3(0, 0, 0);
  1170.                                 }
  1171.         }
  1172. #if MMRM_VISUALIZE_WINDSAMPLES
  1173.         for (size_t x = 0; x < MMRM_WIND_DIM; ++x)
  1174.                 for (size_t y = 0; y < MMRM_WIND_DIM; ++y)
  1175.                         for (size_t z = 0; z < MMRM_WIND_DIM; ++z)
  1176.                         {
  1177.                                 Vec3 start = copy[x + y * MMRM_WIND_DIM + z * sqr(MMRM_WIND_DIM)];
  1178.                                 Vec3 end = start + wind[x + y * MMRM_WIND_DIM + z * MMRM_WIND_DIM * MMRM_WIND_DIM];
  1179.                                 gEnv->pRenderer->GetIRenderAuxGeom()->DrawLine(start, Col_Black, end, Col_White);
  1180.                         }
  1181.         delete[] copy;
  1182.         gEnv->pRenderer->GetIRenderAuxGeom()->DrawAABB(bbox, false, Col_Red, eBBD_Faceted);
  1183. #endif
  1184. }
  1185.  
  1186. struct RenderMeshMeta
  1187. {
  1188.         IMaterial* material;
  1189.         uint32     vertices;
  1190.         uint32     indices;
  1191. };
  1192.  
  1193. ////////////////////////////////////////////////////////////////////////////////
  1194. // Local geometry manager that contains the preprocessed geometry for the job
  1195. class CGeometryManager : public Cry3DEngineBase
  1196. {
  1197.         typedef size_t                              str_hash_t;
  1198.         typedef std::map<str_hash_t, SMMRMGeometry> GeometryMapT;
  1199.  
  1200.         // The geometry map of the geometry manager
  1201.         GeometryMapT m_geomMap;
  1202.  
  1203.         // The size in bytes of all preproccessed meshes
  1204.         size_t m_PreprocessedSize;
  1205.  
  1206.         // Bakes the lod into a special structure for efficient runtime merging
  1207.         bool PrepareLOD(SMMRMGeometry* geometry, CStatObj* host, size_t nLod, bool& rResubmit);
  1208.  
  1209.         // If statobj has "mergedmesh_autodeform" property set, extract deform info
  1210.         // to perform quick&dirty deform sim
  1211.         bool ExtractDeformLOD(SMMRMGeometry* geometry, CStatObj* host, size_t nLod);
  1212.  
  1213. public:
  1214.         CGeometryManager();
  1215.         ~CGeometryManager();
  1216.  
  1217.         void Initialize(int nThreads);
  1218.         void Shutdown();
  1219.  
  1220.         SMMRMGeometry* GetGeometry(uint32, uint16);
  1221.         SMMRMGeometry* GetGeometry(CStatObj*, uint16);
  1222.  
  1223.         void ReleaseGeometry(SMMRMGeometry*);
  1224.  
  1225.         // Returns the main memory size of the geometry stored in the geometry manager
  1226.         size_t Size() const { return m_PreprocessedSize; }
  1227.  
  1228.         // Important Note: This method should not be called from any client code,
  1229.         // it is called implicitly from GetGeometry. Sadly, it has to be public
  1230.         // because DECLARE_CLASS_JOB macros only work on public methods.
  1231.         void                 PrepareGeometry(SMMRMGeometry*);
  1232.  
  1233.         void                 GetUsedMeshes(DynArray<string>& names);
  1234.  
  1235.         bool                 SyncPreparationStep();
  1236.  
  1237.         ILINE StatInstGroup& GetStatObjGroup(const SMMRMGeometry* geometry) const
  1238.         {
  1239. #ifdef SEG_WORLD
  1240.                 return GetObjManager()->m_lstStaticTypes[geometry->m_nStaticTypeSlot][geometry->srcGroupId];
  1241. #else
  1242.                 return GetObjManager()->m_lstStaticTypes[0][geometry->srcGroupId];
  1243. #endif
  1244.         }
  1245.         ILINE CStatObj* GetStatObj(const SMMRMGeometry* geometry) const
  1246.         {
  1247. #ifdef SEG_WORLD
  1248.                 return GetObjManager()->m_lstStaticTypes[geometry->m_nStaticTypeSlot][geometry->srcGroupId].GetStatObj();
  1249. #else
  1250.                 return GetObjManager()->m_lstStaticTypes[0][geometry->srcGroupId].GetStatObj();
  1251. #endif
  1252.         }
  1253. };
  1254.  
  1255. DECLARE_JOB(
  1256.   "PVRNPrepGeom"
  1257.   , TPVRNPrepGeomJob
  1258.   , CGeometryManager::PrepareGeometry);
  1259.  
  1260. static size_t s_jobQueueIndex[2] = { 0, 0 };
  1261.  
  1262. CGeometryManager::CGeometryManager() : m_PreprocessedSize() {}
  1263. CGeometryManager::~CGeometryManager() {}
  1264.  
  1265. void CGeometryManager::Shutdown()
  1266. {
  1267.         m_geomMap.clear();
  1268.         m_PreprocessedSize = 0;
  1269. }
  1270.  
  1271. void CGeometryManager::Initialize(int nWorkers)
  1272. {
  1273. }
  1274.  
  1275. bool CGeometryManager::ExtractDeformLOD(SMMRMGeometry* geometry, CStatObj* host, size_t nLod)
  1276. {
  1277.         MEMORY_SCOPE_CHECK_HEAP();
  1278.         strided_pointer<Vec3> vtx;
  1279.         strided_pointer<ColorB> colour;
  1280.         vtx_idx* indices;
  1281.         size_t constraints_alloc = 0, nconstraints = 0,
  1282.                nvertices = 0, nvertices_alloc = 0;
  1283.         vtx_idx* mapping = 0;
  1284.         std::set<uint32> edges, tris;
  1285.         SMMRMDeform* deform = new SMMRMDeform();
  1286.         Vec3* vertices = NULL;
  1287.         float* mass = NULL;
  1288.         SMMRMDeformConstraint* constraints = NULL;
  1289.         const int endian = 0;
  1290.         resize_list(constraints, constraints_alloc = geometry->numVtx, 16);
  1291.         resize_list(vertices, nvertices_alloc = geometry->numVtx, 16);
  1292.         resize_list(mass, nvertices_alloc, 16);
  1293.         resize_list(mapping, geometry->numVtx, 16);
  1294.  
  1295.         // Map incoming mesh vertices to collapsed simulation vertices
  1296.         for (size_t i = 0; i < geometry->numChunks[nLod]; ++i)
  1297.         {
  1298.                 SMMRMChunk& chunk = geometry->pChunks[nLod][i];
  1299.                 vtx = strided_pointer<Vec3>(&chunk.general[0].xyz, sizeof(chunk.general[0]));
  1300.                 colour = strided_pointer<ColorB>(reinterpret_cast<ColorB*>(&chunk.general[0].color), sizeof(chunk.general[0]));
  1301.                 indices = chunk.indices;
  1302.                 for (size_t k = 0; k < chunk.nindices; k++)
  1303.                 {
  1304.                         const Vec3& pos = vtx[indices[k]];
  1305.                         const uint8 c[2] = { colour[indices[k]].g, colour[indices[k]].b };
  1306.                         const float m = (float)c[endian] / 255.f;
  1307.                         size_t v_idx = (size_t)-1;
  1308.                         for (size_t n = 0; n < nvertices; ++n)
  1309.                         {
  1310.                                 if (fabs(pos.x - vertices[n].x) < FLT_EPSILON &&
  1311.                                     fabs(pos.y - vertices[n].y) < FLT_EPSILON &&
  1312.                                     fabs(pos.z - vertices[n].z) < FLT_EPSILON &&
  1313.                                     fabsf(mass[n] - m) < FLT_EPSILON)
  1314.                                 {
  1315.                                         v_idx = n;
  1316.                                         break;
  1317.                                 }
  1318.                         }
  1319.                         if (v_idx == (size_t)-1)
  1320.                         {
  1321.                                 v_idx = nvertices;
  1322.                                 vertices[nvertices] = pos;
  1323.                                 mass[nvertices++] = m;
  1324.                         }
  1325.                         mapping[indices[k]] = v_idx;
  1326.                 }
  1327.         }
  1328.         bool collapse_ring = true;
  1329.         // Construct constraint based topology
  1330.         for (size_t i = 0; i < geometry->numChunks[nLod]; ++i)
  1331.         {
  1332.                 SMMRMChunk& chunk = geometry->pChunks[nLod][i];
  1333.                 indices = chunk.indices;
  1334.                 // Extract bending constraints
  1335.                 for (size_t j = 0; j < chunk.nvertices; ++j)
  1336.                 {
  1337.                         if (mass[mapping[j]] == 0.f)
  1338.                                 continue;
  1339.                         size_t buddy[2] = { (size_t)-1, (size_t)-1 };
  1340.                         std::vector<size_t> ring;
  1341.                         for (size_t k = 0; k < chunk.nindices; k += 3)
  1342.                         {
  1343.                                 size_t centre = (size_t)-1;
  1344.                                 for (size_t l = 0; centre == (size_t)-1 && l < 3; ++l)
  1345.                                         if (mapping[indices[k + l]] == mapping[j])
  1346.                                                 centre = l;
  1347.                                 if (centre == (size_t)-1)
  1348.                                         continue;
  1349.                                 buddy[0] = mapping[indices[k + dec_mod3[centre]]];
  1350.                                 buddy[1] = mapping[indices[k + inc_mod3[centre]]];
  1351.                                 for (size_t l = 0; l < 2; ++l)
  1352.                                 {
  1353.                                         std::vector<size_t>::iterator where = std::lower_bound(ring.begin(), ring.end(), buddy[l]);
  1354.                                         if (where != ring.end() && *where == buddy[l])
  1355.                                                 continue;
  1356.                                         ring.insert(where, buddy[l]);
  1357.                                 }
  1358.                         }
  1359.                         buddy[0] = (size_t)-1;
  1360.                         buddy[1] = (size_t)-1;
  1361.                         if (collapse_ring)
  1362.                         {
  1363.                                 for (size_t k = 0; k < ring.size(); ++k)
  1364.                                 {
  1365.                                         Vec3 d[2];
  1366.                                         d[0] = (vertices[ring[k]] - vertices[mapping[j]]).GetNormalized();
  1367.                                         float cbest = 0.f;
  1368.                                         for (size_t l = 0; l < ring.size(); ++l)
  1369.                                         {
  1370.                                                 if (l == k)
  1371.                                                         continue;
  1372.                                                 d[1] = (vertices[ring[l]] - vertices[mapping[j]]).GetNormalized();
  1373.                                                 float angle = d[1] | d[0];
  1374.                                                 if (angle < cbest)
  1375.                                                 {
  1376.                                                         cbest = angle;
  1377.                                                         buddy[0] = ring[k];
  1378.                                                         buddy[1] = ring[l];
  1379.                                                 }
  1380.                                         }
  1381.                                 }
  1382.                                 if (buddy[0] != (size_t)-1 && buddy[1] != (size_t)-1)
  1383.                                 {
  1384.                                         for (size_t o = 0; o < nconstraints; ++o)
  1385.                                         {
  1386.                                                 if (constraints[o].type == SMMRMDeformConstraint::DC_BENDING
  1387.                                                     && constraints[o].bending[0] == buddy[0]
  1388.                                                     && constraints[o].bending[1] == mapping[j]
  1389.                                                     && constraints[o].bending[2] == buddy[1])
  1390.                                                         continue;
  1391.                                         }
  1392.                                         if (mass[buddy[0]] + mass[mapping[j]] + mass[buddy[1]] == 0.f)
  1393.                                                 continue;
  1394.                                         if (nconstraints + 1 > constraints_alloc)
  1395.                                                 resize_list(constraints, constraints_alloc += 0xff, 16);
  1396.                                         Vec3 tri[3] =
  1397.                                         {
  1398.                                                 vertices[buddy[0]],
  1399.                                                 vertices[mapping[j]],
  1400.                                                 vertices[buddy[1]]
  1401.                                         };
  1402.                                         constraints[nconstraints].bending[0] = buddy[0];
  1403.                                         constraints[nconstraints].bending[1] = mapping[j];
  1404.                                         constraints[nconstraints].bending[2] = buddy[1];
  1405.                                         constraints[nconstraints].displacement = (tri[1] - (1.f / 3.f) * (tri[0] + tri[1] + tri[2])).len();
  1406.                                         constraints[nconstraints].k = (1.f - mass[mapping[j]]);
  1407.                                         constraints[nconstraints++].type = SMMRMDeformConstraint::DC_BENDING;
  1408.                                 }
  1409.                         }
  1410.                         else
  1411.                         {
  1412.                                 for (size_t k = 0; k < ring.size(); ++k)
  1413.                                 {
  1414.                                         for (size_t l = 0; l < ring.size(); ++l)
  1415.                                         {
  1416.                                                 if (l == k)
  1417.                                                         continue;
  1418.                                                 for (size_t o = 0; o < nconstraints; ++o)
  1419.                                                 {
  1420.                                                         if (constraints[o].type == SMMRMDeformConstraint::DC_BENDING
  1421.                                                             && constraints[o].bending[0] == ring[k]
  1422.                                                             && constraints[o].bending[1] == mapping[j]
  1423.                                                             && constraints[o].bending[2] == ring[l])
  1424.                                                                 continue;
  1425.                                                 }
  1426.                                                 if (mass[ring[k]] + mass[mapping[j]] + mass[ring[1]] == 0.f)
  1427.                                                         continue;
  1428.                                                 if (nconstraints + 1 > constraints_alloc)
  1429.                                                         resize_list(constraints, constraints_alloc += 0xff, 16);
  1430.                                                 Vec3 tri[3] =
  1431.                                                 {
  1432.                                                         vertices[ring[k]],
  1433.                                                         vertices[mapping[j]],
  1434.                                                         vertices[ring[l]]
  1435.                                                 };
  1436.                                                 constraints[nconstraints].bending[0] = (vtx_idx)ring[k];
  1437.                                                 constraints[nconstraints].bending[1] = (vtx_idx)mapping[j];
  1438.                                                 constraints[nconstraints].bending[2] = (vtx_idx)ring[l];
  1439.                                                 constraints[nconstraints].displacement = (tri[1] - (1.f / 3.f) * (tri[0] + tri[1] + tri[2])).len();
  1440.                                                 constraints[nconstraints].k = (1.f - mass[mapping[j]]);
  1441.                                                 constraints[nconstraints++].type = SMMRMDeformConstraint::DC_BENDING;
  1442.                                         }
  1443.                                 }
  1444.                         }
  1445.                 }
  1446.                 // Extract edge length constraints
  1447.                 for (size_t j = 0; j < chunk.nindices; j += 3)
  1448.                         for (size_t k = 0; k < 3; ++k)
  1449.                         {
  1450.                                 uint32 index[2] = { mapping[indices[j + k]], mapping[indices[j + inc_mod3[k]]] };
  1451.                                 uint32 hash = min(index[0], index[1]) + max(index[0], index[1]) * nvertices;
  1452.                                 std::set<uint32>::iterator where = edges.lower_bound(hash);
  1453.                                 if (where != edges.end() && *where == hash)
  1454.                                         continue;
  1455.                                 if (mass[index[0]] + mass[index[1]] == 0.f)
  1456.                                         continue;
  1457.                                 edges.insert(where, hash);
  1458.                                 if (nconstraints + 1 > constraints_alloc)
  1459.                                         resize_list(constraints, constraints_alloc += 0xff, 16);
  1460.                                 constraints[nconstraints].edge[0] = index[0];
  1461.                                 constraints[nconstraints].edge[1] = index[1];
  1462.                                 constraints[nconstraints].edge_distance = (vertices[index[0]] - vertices[index[1]]).len();
  1463.                                 constraints[nconstraints].k = 1.f;
  1464.                                 constraints[nconstraints++].type = SMMRMDeformConstraint::DC_EDGE;
  1465.                         }
  1466.         }
  1467.         // Truncate the lists to final size
  1468.         resize_list(constraints, nconstraints, 16);
  1469.         resize_list(vertices, nvertices, 16);
  1470.         resize_list(mass, nvertices, 16);
  1471.         deform->invmass = mass;
  1472.         deform->initial = vertices;
  1473.         deform->mapping = mapping;
  1474.         deform->constraints = constraints;
  1475.         deform->nconstraints = nconstraints;
  1476.         deform->nvertices = nvertices;
  1477.         geometry->deform = deform;
  1478.  
  1479.         // Recalculate approximate bounding volume
  1480.         geometry->aabb.Reset();
  1481.         for (size_t i = 0; i < nvertices; ++i)
  1482.         {
  1483.                 if (mass[i] > 0.f)
  1484.                 {
  1485.                         float distance = FLT_MAX, d;
  1486.                         Vec3 centre;
  1487.                         for (size_t j = 0; j < nvertices; ++j)
  1488.                                 if (mass[j] == 0.f && (d = (vertices[i] - vertices[j]).len()) < distance)
  1489.                                 {
  1490.                                         distance = d;
  1491.                                         centre = vertices[j];
  1492.                                 }
  1493.                         geometry->aabb.Add(centre + Vec3(distance, distance, distance));
  1494.                         geometry->aabb.Add(centre - Vec3(distance, distance, distance));
  1495.                 }
  1496.         }
  1497.  
  1498.         return true;
  1499. }
  1500.  
  1501. bool CGeometryManager::PrepareLOD(SMMRMGeometry* geometry, CStatObj* host, size_t nLod, bool& rResubmit)
  1502. {
  1503.         MEMORY_SCOPE_CHECK_HEAP();
  1504.         IRenderMesh* renderMesh = NULL;
  1505.         strided_pointer<Vec2> uv;
  1506.         strided_pointer<SPipTangents> tangs;
  1507.         strided_pointer<Vec3> vtx;
  1508.         strided_pointer<Vec3f16> norm;
  1509.         strided_pointer<uint32> colour;
  1510.         SPipQTangents* qtangents = NULL;
  1511.         SMeshBoneMapping_uint8* weights;
  1512.         bool weightsAllocated = false;
  1513.         vtx_idx* indices;
  1514.         CStatObj* statObj = (CStatObj*)host->GetLodObject(nLod, false);
  1515.         if (!statObj)
  1516.                 return true;
  1517.  
  1518.         // ChrisR: The below block is disabled for now as it requires all levels to be re-exported
  1519.         // It will be enabled in two weeks and the above comment removed
  1520.         IF ((!(renderMesh = statObj->GetRenderMesh())) || (!gEnv->IsEditor() && (Cry3DEngineBase::m_p3DEngine->m_bInShutDown || Cry3DEngineBase::m_p3DEngine->m_bInUnload)), 0)
  1521.         {
  1522.                 geometry->state = SMMRMGeometry::NO_RENDERMESH;
  1523.                 return false;
  1524.         }
  1525.  
  1526.         renderMesh->LockForThreadAccess();
  1527.         int nvertices = renderMesh->GetVerticesCount();
  1528.         EVertexFormat vtx_fmt = renderMesh->GetVertexFormat();
  1529.  
  1530.         vtx.data = (Vec3*)renderMesh->GetPosPtr(vtx.iStride, FSL_READ);
  1531.         colour.data = (uint32*)renderMesh->GetColorPtr(colour.iStride, FSL_READ);
  1532.         uv.data = (Vec2*)renderMesh->GetUVPtr(uv.iStride, FSL_READ);
  1533.         tangs.data = (SPipTangents*)renderMesh->GetTangentPtr(tangs.iStride, FSL_READ);
  1534.         norm.data = (Vec3f16*)renderMesh->GetNormPtr(norm.iStride, FSL_READ);
  1535.         indices = renderMesh->GetIndexPtr(FSL_READ);
  1536.         weights = statObj->m_pBoneMapping;
  1537.  
  1538.         if (Cry3DEngineBase::GetCVars()->e_MergedMeshesTesselationSupport == 0)
  1539.         {
  1540.                 norm.data = NULL;
  1541.                 norm.iStride = 0;
  1542.         }
  1543.         else
  1544.                 norm.data = (Vec3f16*)renderMesh->GetNormPtr(norm.iStride, FSL_READ);
  1545.  
  1546.         if (tangs)
  1547.         {
  1548.                 resize_list(qtangents, renderMesh->GetVerticesCount(), 16);
  1549.                 MeshTangentsFrameToQTangents(
  1550.                   tangs.data, tangs.iStride, nvertices,
  1551.                   qtangents, sizeof(qtangents[0]));
  1552.         }
  1553.  
  1554.         TRenderChunkArray& renderChunks = renderMesh->GetChunks();
  1555.         for (int i = 0; i < renderChunks.size(); ++i)
  1556.         {
  1557.                 const CRenderChunk renderChunk = renderChunks[i];
  1558.                 SMMRMChunk* chunk = NULL;
  1559.                 if (renderChunks[i].m_nMatFlags & (MTL_FLAG_NODRAW | MTL_FLAG_COLLISION_PROXY | MTL_FLAG_RAYCAST_PROXY))
  1560.                         continue;
  1561.                 for (size_t j = 0; j < geometry->numChunks[nLod]; ++j)
  1562.                 {
  1563.                         if (geometry->pChunks[nLod][j].matId == renderChunk.m_nMatID)
  1564.                         {
  1565.                                 chunk = &geometry->pChunks[nLod][j];
  1566.                                 break;
  1567.                         }
  1568.                 }
  1569.                 if (!chunk)
  1570.                 {
  1571.                         resize_list(geometry->pChunks[nLod], (geometry->numChunks[nLod] + 1) * sizeof(SMMRMChunk), 16);
  1572.                         chunk = new(&geometry->pChunks[nLod][geometry->numChunks[nLod]++])SMMRMChunk(renderChunk.m_nMatID);
  1573.                 }
  1574.                 chunk->nvertices_alloc += renderChunk.nNumVerts;
  1575.                 chunk->nindices_alloc += renderChunk.nNumIndices;
  1576.         }
  1577.         // Patch envelope based weighting into geometry if RC skipped weighting step for lower lods.
  1578.         if (weights == NULL && host->m_pBoneMapping)
  1579.         {
  1580.                 int nvertices = renderMesh->GetVerticesCount();
  1581.                 weights = new SMeshBoneMapping_uint8[nvertices];
  1582.  
  1583.                 weightsAllocated = true;
  1584.                 for (int i = 0; i < nvertices; ++i)
  1585.                 {
  1586.                         float dist = FLT_MAX;
  1587.                         size_t idx = (size_t)-1;
  1588.                         for (int j = 0, boneIdx = 1; j < host->m_nSpines; boneIdx += host->m_pSpines[j++].nVtx - 1)
  1589.                         {
  1590.                                 for (int k = 0; k < host->m_pSpines[j].nVtx - 1; ++k)
  1591.                                 {
  1592.                                         float t = 0.f, dp = Distance::Point_Lineseg(
  1593.                                           vtx[i], Lineseg(host->m_pSpines[j].pVtx[k], host->m_pSpines[j].pVtx[k + 1]), t);
  1594.                                         if (dp < dist)
  1595.                                         {
  1596.                                                 dist = dp;
  1597.                                                 idx = boneIdx + k;
  1598.                                         }
  1599.                                 }
  1600.                         }
  1601.  
  1602.                         weights[i].boneIds[0] = static_cast<uint8>(idx);
  1603.                         weights[i].weights[0] = 255;
  1604.                         for (int j = 1; j < 4; ++j)
  1605.                         {
  1606.                                 weights[i].boneIds[j] = 0;
  1607.                                 weights[i].weights[j] = 0;
  1608.                         }
  1609.                 }
  1610.         }
  1611.         for (size_t i = 0; i < geometry->numChunks[nLod]; ++i)
  1612.         {
  1613.                 SMMRMChunk* chunk = &geometry->pChunks[nLod][i];
  1614.                 resize_list(chunk->general, chunk->nvertices_alloc, 16);
  1615.                 resize_list(chunk->indices, chunk->nindices_alloc, 16);
  1616.                 if (qtangents)  resize_list(chunk->qtangents, chunk->nvertices_alloc, 16);
  1617.                 if (norm) resize_list(chunk->normals, chunk->nvertices_alloc, 16);
  1618.                 if (weights) resize_list(chunk->weights, chunk->nvertices_alloc, 16);
  1619.         }
  1620.         for (int i = 0; i < renderChunks.size(); ++i)
  1621.         {
  1622.                 const CRenderChunk renderChunk = renderChunks[i];
  1623.                 SMMRMChunk* chunk = NULL;
  1624.                 if (renderChunks[i].m_nMatFlags & (MTL_FLAG_NODRAW | MTL_FLAG_COLLISION_PROXY | MTL_FLAG_RAYCAST_PROXY))
  1625.                         continue;
  1626.                 for (size_t j = 0; j < geometry->numChunks[nLod]; ++j)
  1627.                 {
  1628.                         if (geometry->pChunks[nLod][j].matId == renderChunk.m_nMatID)
  1629.                         {
  1630.                                 chunk = &geometry->pChunks[nLod][j];
  1631.                                 break;
  1632.                         }
  1633.                 }
  1634.                 assert(chunk);
  1635.                 PREFAST_ASSUME(chunk);
  1636.                 for (size_t j = renderChunk.nFirstIndexId; j < renderChunk.nFirstIndexId + renderChunk.nNumIndices; ++j)
  1637.                 {
  1638.                         vtx_idx index = indices[j];
  1639.                         vtx_idx chkidx = (vtx_idx) - 1;
  1640.                         SMMRMBoneMapping weightsForIndex;
  1641.                         if (weights) weightsForIndex = weights[index];
  1642.                         for (size_t k = 0; k < chunk->nvertices; ++k)
  1643.                         {
  1644.                                 IF (vtx[index] != chunk->general[k].xyz, 1) continue;
  1645.                                 IF (colour && colour[index] != chunk->general[k].color.dcolor, 1) continue;
  1646.                                 IF (uv && uv[index] != chunk->general[k].st, 1) continue;
  1647.                                 IF (qtangents && qtangents[index] != chunk->qtangents[k], 1) continue;
  1648.                                 IF (norm && norm[index].ToVec3() != chunk->normals[k], 1) continue;
  1649.                                 IF (weights && chunk->weights[k] != weightsForIndex, 1) continue;
  1650.                                 chkidx = (vtx_idx)k;
  1651.                                 break;
  1652.                         }
  1653.                         if (chkidx == (vtx_idx) - 1)
  1654.                         {
  1655.                                 assert(chunk->nvertices < chunk->nvertices_alloc);
  1656.                                 size_t usedSpines = 0;
  1657.                                 chunk->general[chunk->nvertices].xyz = vtx[index];
  1658.                                 if (colour) chunk->general[chunk->nvertices].color.dcolor = colour[index];
  1659.                                 if (uv) chunk->general[chunk->nvertices].st = uv[index];
  1660.                                 if (qtangents) chunk->qtangents[chunk->nvertices] = qtangents[index];
  1661.                                 if (weights) chunk->weights[chunk->nvertices] = weightsForIndex;
  1662.                                 if (norm) chunk->normals[chunk->nvertices] = norm[index].ToVec3();
  1663.                                 for (size_t k = 0; weights && k < 4; ++k)
  1664.                                         if (weights[index].weights[k]) ++usedSpines;
  1665.                                 geometry->maxSpinesPerVtx = max(geometry->maxSpinesPerVtx, usedSpines);
  1666.                                 chkidx = (vtx_idx)(chunk->nvertices++);
  1667.                         }
  1668.                         assert(chunk->nindices < chunk->nindices_alloc);
  1669.                         chunk->indices[chunk->nindices++] = chkidx;
  1670.                 }
  1671.         }
  1672.         for (size_t i = 0; i < geometry->numChunks[nLod]; ++i)
  1673.         {
  1674.                 SMMRMChunk* chunk = &geometry->pChunks[nLod][i];
  1675.                 resize_list(chunk->general, chunk->nvertices, 16);
  1676.                 resize_list(chunk->indices, chunk->nindices, 16);
  1677.                 if (qtangents) resize_list(chunk->qtangents, chunk->nvertices, 16);
  1678.                 if (weights) resize_list(chunk->weights, chunk->nvertices, 16);
  1679.                 if (norm) resize_list(chunk->normals, chunk->nvertices, 16);
  1680.                 if (nLod == 0)
  1681.                 {
  1682.                         geometry->numVtx += (chunk->nvertices_alloc = chunk->nvertices);
  1683.                         geometry->numIdx += (chunk->nindices_alloc = chunk->nindices);
  1684.                 }
  1685.                 resize_list(chunk->skin_vertices, nvertices, SMMRMSkinVertex_ALIGN);
  1686.                 for (size_t j = 0; j < chunk->nvertices; ++j)
  1687.                 {
  1688.                         memset(&chunk->skin_vertices[j], 0, sizeof(chunk->skin_vertices[j]));
  1689.                         chunk->skin_vertices[j].pos = chunk->general[j].xyz;
  1690.                         chunk->skin_vertices[j].uv = chunk->general[j].st;
  1691.                         chunk->skin_vertices[j].colour = chunk->general[j].color;
  1692.                         if (chunk->normals)
  1693.                                 chunk->skin_vertices[j].normal = chunk->normals[j];
  1694.                         if (chunk->weights)
  1695.                         {
  1696.                                 chunk->skin_vertices[j].SetWeights(chunk->weights[j].weights);
  1697.                                 chunk->skin_vertices[j].SetBoneIds(chunk->weights[j].boneIds);
  1698.                         }
  1699.                         if (chunk->qtangents)
  1700.                                 chunk->skin_vertices[j].qt = chunk->qtangents[j];
  1701.                 }
  1702.         }
  1703.  
  1704.         if (qtangents) CryModuleMemalignFree(qtangents);
  1705.         renderMesh->UnlockStream(VSF_GENERAL);
  1706.         renderMesh->UnlockStream(VSF_TANGENTS);
  1707.         renderMesh->UnlockStream(VSF_QTANGENTS);
  1708.         renderMesh->UnlockIndexStream();
  1709.         renderMesh->UnLockForThreadAccess();
  1710.         if (weightsAllocated) delete[] weights;
  1711.         MEMORY_CHECK_HEAP();
  1712.         return true;
  1713. }
  1714.  
  1715. void CGeometryManager::PrepareGeometry(SMMRMGeometry* geometry)
  1716. {
  1717.         if (!geometry)
  1718.         {
  1719.                 return;
  1720.         }
  1721.         CStatObj* statObj = NULL;
  1722.         if (geometry->is_obj)
  1723.                 statObj = geometry->srcObj;
  1724.         else
  1725.         {
  1726.                 statObj = GetStatObj(geometry);
  1727.         }
  1728.         if (!statObj)
  1729.         {
  1730.                 geometry->state = SMMRMGeometry::NO_STATINSTGROUP;
  1731.                 return;
  1732.         }
  1733.         bool success =