Guest User

Untitled

a guest
Jun 25th, 2021
53
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using UnityEngine;
  2. using Unity.Collections;
  3. using Pathfinding.Voxels;
  4. using Unity.Mathematics;
  5. using Unity.Jobs;
  6. using Unity.Burst;
  7.  
  8. namespace Pathfinding.Voxels.Burst {
  9.     using Pathfinding.Util;
  10.  
  11.     /** VoxelMesh used for recast graphs.
  12.      * \astarpro
  13.      */
  14.     public struct VoxelMesh {
  15.         /** Vertices of the mesh */
  16.         public NativeList<Int3> verts;
  17.  
  18.         /** Triangles of the mesh.
  19.          * Each element points to a vertex in the #verts array
  20.          */
  21.         public NativeList<int> tris;
  22.  
  23.         /** Area index for each triangle */
  24.         public NativeList<int> areas;
  25.  
  26.         public void Dispose () {
  27.             verts.Dispose();
  28.             tris.Dispose();
  29.             areas.Dispose();
  30.         }
  31.     }
  32.  
  33.     /** Builds a polygon mesh from a contour set.
  34.      */
  35.     [BurstCompile]
  36.     public struct JobBuildMesh : IJob {
  37.         public NativeList<int> contourVertices;
  38.         /** contour set to build a mesh from. */
  39.         public NativeList<VoxelContour> contours;
  40.         /** Results will be written to this mesh. */
  41.         public VoxelMesh mesh;
  42.         public CompactVoxelField field;
  43.  
  44.         /** Returns T iff (v_i, v_j) is a proper internal
  45.          * diagonal of P.
  46.          */
  47.         static bool Diagonal (int i, int j, int n, NativeArray<int> verts, NativeArray<int> indices) {
  48.             return InCone(i, j, n, verts, indices) && Diagonalie(i, j, n, verts, indices);
  49.         }
  50.  
  51.         static bool InCone (int i, int j, int n, NativeArray<int> verts, NativeArray<int> indices) {
  52.             int pi = (indices[i] & 0x0fffffff) * 4;
  53.             int pj = (indices[j] & 0x0fffffff) * 4;
  54.             int pi1 = (indices[Next(i, n)] & 0x0fffffff) * 4;
  55.             int pin1 = (indices[Prev(i, n)] & 0x0fffffff) * 4;
  56.  
  57.             // If P[i] is a convex vertex [ i+1 left or on (i-1,i) ].
  58.             if (LeftOn(pin1, pi, pi1, verts))
  59.                 return Left(pi, pj, pin1, verts) && Left(pj, pi, pi1, verts);
  60.             // Assume (i-1,i,i+1) not collinear.
  61.             // else P[i] is reflex.
  62.             return !(LeftOn(pi, pj, pi1, verts) && LeftOn(pj, pi, pin1, verts));
  63.         }
  64.  
  65.         /** Returns true iff c is strictly to the left of the directed
  66.          * line through a to b.
  67.          */
  68.         static bool Left (int a, int b, int c, NativeArray<int> verts) {
  69.             return Area2(a, b, c, verts) < 0;
  70.         }
  71.  
  72.         static bool LeftOn (int a, int b, int c, NativeArray<int> verts) {
  73.             return Area2(a, b, c, verts) <= 0;
  74.         }
  75.  
  76.         static bool Collinear (int a, int b, int c, NativeArray<int> verts) {
  77.             return Area2(a, b, c, verts) == 0;
  78.         }
  79.  
  80.         public static int Area2 (int a, int b, int c, NativeArray<int> verts) {
  81.             return (verts[b] - verts[a]) * (verts[c+2] - verts[a+2]) - (verts[c+0] - verts[a+0]) * (verts[b+2] - verts[a+2]);
  82.         }
  83.  
  84.         /**
  85.          * Returns T iff (v_i, v_j) is a proper internal *or* external
  86.          * diagonal of P, *ignoring edges incident to v_i and v_j*.
  87.          */
  88.         static bool Diagonalie (int i, int j, int n, NativeArray<int> verts, NativeArray<int> indices) {
  89.             int d0 = (indices[i] & 0x0fffffff) * 4;
  90.             int d1 = (indices[j] & 0x0fffffff) * 4;
  91.  
  92.             /*int a = (i+1) % indices.Length;
  93.              * if (a == j) a = (i-1 + indices.Length) % indices.Length;
  94.              * int a_v = (indices[a] & 0x0fffffff) * 4;
  95.              *
  96.              * if (a != j && Collinear (d0,a_v,d1,verts)) {
  97.              *  return false;
  98.              * }*/
  99.  
  100.             // For each edge (k,k+1) of P
  101.             for (int k = 0; k < n; k++) {
  102.                 int k1 = Next(k, n);
  103.                 // Skip edges incident to i or j
  104.                 if (!((k == i) || (k1 == i) || (k == j) || (k1 == j))) {
  105.                     int p0 = (indices[k] & 0x0fffffff) * 4;
  106.                     int p1 = (indices[k1] & 0x0fffffff) * 4;
  107.  
  108.                     if (Vequal(d0, p0, verts) || Vequal(d1, p0, verts) || Vequal(d0, p1, verts) || Vequal(d1, p1, verts))
  109.                         continue;
  110.  
  111.                     if (Intersect(d0, d1, p0, p1, verts))
  112.                         return false;
  113.                 }
  114.             }
  115.  
  116.  
  117.             return true;
  118.         }
  119.  
  120.         //  Exclusive or: true iff exactly one argument is true.
  121.         //  The arguments are negated to ensure that they are 0/1
  122.         //  values.  Then the bitwise Xor operator may apply.
  123.         //  (This idea is due to Michael Baldwin.)
  124.         static bool Xorb (bool x, bool y) {
  125.             return !x ^ !y;
  126.         }
  127.  
  128.         //  Returns true iff ab properly intersects cd: they share
  129.         //  a point interior to both segments.  The properness of the
  130.         //  intersection is ensured by using strict leftness.
  131.         static bool IntersectProp (int a, int b, int c, int d, NativeArray<int> verts) {
  132.             // Eliminate improper cases.
  133.             if (Collinear(a, b, c, verts) || Collinear(a, b, d, verts) ||
  134.                 Collinear(c, d, a, verts) || Collinear(c, d, b, verts))
  135.                 return false;
  136.  
  137.             return Xorb(Left(a, b, c, verts), Left(a, b, d, verts)) && Xorb(Left(c, d, a, verts), Left(c, d, b, verts));
  138.         }
  139.  
  140.         // Returns T iff (a,b,c) are collinear and point c lies
  141.         // on the closed segement ab.
  142.         static bool Between (int a, int b, int c, NativeArray<int> verts) {
  143.             if (!Collinear(a, b, c, verts))
  144.                 return false;
  145.             // If ab not vertical, check betweenness on x; else on y.
  146.             if (verts[a+0] != verts[b+0])
  147.                 return ((verts[a+0] <= verts[c+0]) && (verts[c+0] <= verts[b+0])) || ((verts[a+0] >= verts[c+0]) && (verts[c+0] >= verts[b+0]));
  148.             else
  149.                 return ((verts[a+2] <= verts[c+2]) && (verts[c+2] <= verts[b+2])) || ((verts[a+2] >= verts[c+2]) && (verts[c+2] >= verts[b+2]));
  150.         }
  151.  
  152.         // Returns true iff segments ab and cd intersect, properly or improperly.
  153.         static bool Intersect (int a, int b, int c, int d, NativeArray<int> verts) {
  154.             if (IntersectProp(a, b, c, d, verts))
  155.                 return true;
  156.             else if (Between(a, b, c, verts) || Between(a, b, d, verts) ||
  157.                      Between(c, d, a, verts) || Between(c, d, b, verts))
  158.                 return true;
  159.             else
  160.                 return false;
  161.         }
  162.  
  163.         static bool Vequal (int a, int b, NativeArray<int> verts) {
  164.             return verts[a+0] == verts[b+0] && verts[a+2] == verts[b+2];
  165.         }
  166.  
  167.         /** (i-1+n) % n assuming 0 <= i < n */
  168.         static int Prev (int i, int n) { return i-1 >= 0 ? i-1 : n-1; }
  169.         /** (i+1) % n assuming 0 <= i < n */
  170.         static int Next (int i, int n) { return i+1 < n ? i+1 : 0; }
  171.  
  172.         public void Execute () {
  173.             // Maximum allowed vertices per polygon. Currently locked to 3.
  174.             var nvp = 3;
  175.  
  176.             int maxVertices = 0;
  177.             int maxTris = 0;
  178.             int maxVertsPerCont = 0;
  179.  
  180.             for (int i = 0; i < contours.Length; i++) {
  181.                 // Skip null contours.
  182.                 if (contours[i].nverts < 3) continue;
  183.  
  184.                 maxVertices += contours[i].nverts;
  185.                 maxTris += contours[i].nverts - 2;
  186.                 maxVertsPerCont = System.Math.Max(maxVertsPerCont, contours[i].nverts);
  187.             }
  188.  
  189.             mesh.verts.ResizeUninitialized(maxVertices);
  190.             mesh.tris.ResizeUninitialized(maxTris*nvp);
  191.             mesh.areas.ResizeUninitialized(maxTris);
  192.             var verts = mesh.verts;
  193.             var polys = mesh.tris;
  194.             var areas = mesh.areas;
  195.  
  196.             var indices = new NativeArray<int>(maxVertsPerCont, Allocator.Temp);
  197.             var tris = new NativeArray<int>(maxVertsPerCont*3, Allocator.Temp);
  198.  
  199.             int vertexIndex = 0;
  200.             int polyIndex = 0;
  201.             int areaIndex = 0;
  202.  
  203.             for (int i = 0; i < contours.Length; i++) {
  204.                 VoxelContour cont = contours[i];
  205.  
  206.                 // Skip degenerate contours
  207.                 if (cont.nverts < 3) {
  208.                     continue;
  209.                 }
  210.  
  211.                 for (int j = 0; j < cont.nverts; j++) {
  212.                     indices[j] = j;
  213.                     // Convert the z coordinate from the form z*voxelArea.width which is used in other places for performance
  214.                     contourVertices[cont.vertexStartIndex + j*4+2] /= field.width;
  215.                 }
  216.  
  217.                 // Triangulate the contour
  218.                 int ntris = Triangulate(cont.nverts, contourVertices.AsArray().GetSubArray(cont.vertexStartIndex, cont.nverts*4), ref indices, ref tris);
  219.  
  220.                 // Assign the correct vertex indices
  221.                 int startIndex = vertexIndex;
  222.                 for (int j = 0; j < ntris*3; polyIndex++, j++) {
  223.                     //@Error sometimes
  224.                     polys[polyIndex] = tris[j]+startIndex;
  225.                 }
  226.  
  227.                 // Mark all triangles generated by this contour
  228.                 // as having the area cont.area
  229.                 for (int j = 0; j < ntris; areaIndex++, j++) {
  230.                     areas[areaIndex] = cont.area;
  231.                 }
  232.  
  233.                 // Copy the vertex positions
  234.                 for (int j = 0; j < cont.nverts; vertexIndex++, j++) {
  235.                     verts[vertexIndex] = new Int3(
  236.                         contourVertices[cont.vertexStartIndex + j*4],
  237.                         contourVertices[cont.vertexStartIndex + j*4+1],
  238.                         contourVertices[cont.vertexStartIndex + j*4+2]
  239.                         );
  240.                 }
  241.             }
  242.  
  243.             if (vertexIndex != mesh.verts.Length) throw new System.Exception("Ended up at an unexpected vertex index");
  244.             if (areaIndex > mesh.areas.Length) throw new System.Exception("Ended up at an unexpected area index");
  245.             if (polyIndex > mesh.tris.Length) throw new System.Exception("Ended up at an unexpected poly index");
  246.  
  247.             // polyIndex might in rare cases not be equal to mesh.tris.Length.
  248.             // This can happen if degenerate triangles were generated.
  249.             // So we make sure the list is truncated to the right size here.
  250.             mesh.tris.ResizeUninitialized(polyIndex);
  251.             // Same thing for area index
  252.             mesh.areas.ResizeUninitialized(areaIndex);
  253.         }
  254.  
  255.         int Triangulate (int n, NativeArray<int> verts, ref NativeArray<int> indices, ref NativeArray<int> tris) {
  256.             int ntris = 0;
  257.  
  258.             var dst = tris;
  259.  
  260.             int dstIndex = 0;
  261.  
  262.             // Debug code
  263.             //int on = n;
  264.  
  265.             // The last bit of the index is used to indicate if the vertex can be removed.
  266.             const int CanBeRemovedBit = 0x40000000;
  267.             // Used to get only the index value, without any flag bits.
  268.             const int IndexMask = 0x0fffffff;
  269.  
  270.             for (int i = 0; i < n; i++) {
  271.                 int i1 = Next(i, n);
  272.                 int i2 = Next(i1, n);
  273.                 if (Diagonal(i, i2, n, verts, indices)) {
  274.                     indices[i1] |= CanBeRemovedBit;
  275.                 }
  276.             }
  277.  
  278.             while (n > 3) {
  279.                 #if ASTARDEBUG && !AstarRelease
  280.                 for (int j = 0; j < n; j++) {
  281.                     DrawLine(Prev(j, n), j, indices, verts, Color.red);
  282.                 }
  283.                 #endif
  284.  
  285.                 int minLen = -1;
  286.                 int mini = -1;
  287.  
  288.                 for (int q = 0; q < n; q++) {
  289.                     int q1 = Next(q, n);
  290.                     if ((indices[q1] & CanBeRemovedBit) != 0) {
  291.                         int p0 = (indices[q] & IndexMask) * 4;
  292.                         int p2 = (indices[Next(q1, n)] & IndexMask) * 4;
  293.  
  294.                         int dx = verts[p2+0] - verts[p0+0];
  295.                         int dz = verts[p2+2] - verts[p0+2];
  296.  
  297.                         #if ASTARDEBUG && !AstarRelease
  298.                         DrawLine(q, Next(q1, n), indices, verts, Color.blue);
  299.                         #endif
  300.  
  301.                         //Squared distance
  302.                         int len = dx*dx + dz*dz;
  303.  
  304.                         if (minLen < 0 || len < minLen) {
  305.                             minLen = len;
  306.                             mini = q;
  307.                         }
  308.                     }
  309.                 }
  310.  
  311.                 if (mini == -1) {
  312.                     Debug.LogWarning("Degenerate triangles might have been generated.\n" +
  313.                         "Usually this is not a problem, but if you have a static level, try to modify the graph settings slightly to avoid this edge case.");
  314.  
  315.                     // Can't run the debug stuff because we are likely running from a separate thread
  316.                     //for (int j=0;j<on;j++) {
  317.                     //  DrawLine (Prev(j,on),j,indices,verts,Color.red);
  318.                     //}
  319.  
  320.                     // Should not happen.
  321.                     /*          printf("mini == -1 ntris=%d n=%d\n", ntris, n);
  322.                      *          for (int i = 0; i < n; i++)
  323.                      *          {
  324.                      *              printf("%d ", indices[i] & IndexMask);
  325.                      *          }
  326.                      *          printf("\n");*/
  327.                     //yield break;
  328.                     return -ntris;
  329.                 }
  330.  
  331.                 int i = mini;
  332.                 int i1 = Next(i, n);
  333.                 int i2 = Next(i1, n);
  334.  
  335.                 #if ASTARDEBUG && !AstarRelease
  336.                 for (int j = 0; j < n; j++) {
  337.                     DrawLine(Prev(j, n), j, indices, verts, Color.red);
  338.                 }
  339.  
  340.                 DrawLine(i, i2, indices, verts, Color.magenta);
  341.                 for (int j = 0; j < n; j++) {
  342.                     DrawLine(Prev(j, n), j, indices, verts, Color.red);
  343.                 }
  344.                 #endif
  345.  
  346.                 dst[dstIndex] = indices[i] & IndexMask;
  347.                 dstIndex++;
  348.                 dst[dstIndex] = indices[i1] & IndexMask;
  349.                 dstIndex++;
  350.                 dst[dstIndex] = indices[i2] & IndexMask;
  351.                 dstIndex++;
  352.                 ntris++;
  353.  
  354.                 // Removes P[i1] by copying P[i+1]...P[n-1] left one index.
  355.                 n--;
  356.                 for (int k = i1; k < n; k++) {
  357.                     indices[k] = indices[k+1];
  358.                 }
  359.  
  360.                 if (i1 >= n) i1 = 0;
  361.                 i = Prev(i1, n);
  362.                 // Update diagonal flags.
  363.                 if (Diagonal(Prev(i, n), i1, n, verts, indices)) {
  364.                     indices[i] |= CanBeRemovedBit;
  365.                 } else {
  366.                     indices[i] &= IndexMask;
  367.                 }
  368.                 if (Diagonal(i, Next(i1, n), n, verts, indices)) {
  369.                     indices[i1] |= CanBeRemovedBit;
  370.                 } else {
  371.                     indices[i1] &= IndexMask;
  372.                 }
  373.             }
  374.  
  375.             dst[dstIndex] = indices[0] & IndexMask;
  376.             dstIndex++;
  377.             dst[dstIndex] = indices[1] & IndexMask;
  378.             dstIndex++;
  379.             dst[dstIndex] = indices[2] & IndexMask;
  380.             dstIndex++;
  381.             ntris++;
  382.  
  383.             return ntris;
  384.         }
  385.     }
  386. }
  387.  
RAW Paste Data