commit 9ee850c533e5f8e3850e130c85309dbcf19fc117
Author: leszek <leszek@koltunski.pl>
Date:   Tue Aug 1 19:36:18 2023 +0200

    Major progress with supporting cubit faces with holes.

diff --git a/src/main/java/org/distorted/library/mesh/MeshMultigon.java b/src/main/java/org/distorted/library/mesh/MeshMultigon.java
index 2d6be59..6a2f940 100644
--- a/src/main/java/org/distorted/library/mesh/MeshMultigon.java
+++ b/src/main/java/org/distorted/library/mesh/MeshMultigon.java
@@ -35,20 +35,19 @@ import java.util.ArrayList;
 public class MeshMultigon extends MeshBase
   {
   private static final float MAX_ERROR = 0.000001f;
-  private float[][] mOuterVertices;
-  private float[][] mOuterVectors;
-  private int mNumOuter;
+  private float[][][] mOuterAndHoleVertices;
+  private float[][][] mEdgeVectors;
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
-  private boolean isSame(float dx, float dy)
+  private static boolean isSame(float dx, float dy)
     {
     return (dx*dx + dy*dy < MAX_ERROR);
     }
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
-  private int isUp(float[][] vertices, int polygon, int edge)
+  private static int isUp(float[][] vertices, int polygon, int edge)
     {
     float[] p= vertices[polygon];
     int lenP = p.length/2;
@@ -83,24 +82,7 @@ public class MeshMultigon extends MeshBase
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
-  private int[][] computeEdgesUp(float[][] vertices)
-    {
-    int num = vertices.length;
-    int[][] up = new int[num][];
-
-    for(int i=0; i<num; i++)
-      {
-      int len = vertices[i].length/2;
-      up[i] = new int[len];
-      for(int j=0; j<len; j++) up[i][j] = isUp(vertices,i,j);
-      }
-
-    return up;
-    }
-
-///////////////////////////////////////////////////////////////////////////////////////////////////
-
-  private float[] detectFirstOuterVertex(float[][] vertices)
+  private static float[] detectFirstOuterVertex(float[][] vertices)
     {
     float X = -Float.MAX_VALUE;
     int I=0,J=0, len = vertices.length;
@@ -125,7 +107,7 @@ public class MeshMultigon extends MeshBase
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
-  private double computeAngle(float x1,float y1, float x2, float y2)
+  private static double computeAngle(float x1,float y1, float x2, float y2)
     {
     double diff = Math.atan2(y2,x2)-Math.atan2(y1,x1);
     return diff<0 ? diff+(2*Math.PI) : diff;
@@ -133,31 +115,33 @@ public class MeshMultigon extends MeshBase
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
-  private float[] detectNextOuterVertex(float[][] vertices, float[] curr, float[] vect)
+  private static float[] detectNextOuterVertex(float[][] vertices, float[] curr, float[] vect, int[][] edgesUp)
     {
-    double minAngle = 2*Math.PI;
+    double maxAngle = 0;
     float x=0, y=0;
+    int numC = vertices.length;
 
-    for( float[] v : vertices )
+    for( int c=0; c<numC; c++ )
       {
-      int num = v.length/2;
+      float[] vert = vertices[c];
+      int numV = vert.length/2;
 
-      for( int j=0; j<num; j++)
+      for( int v=0; v<numV; v++)
         {
-        float xc = v[2*j];
-        float yc = v[2*j+1];
+        float xc = vert[2*v];
+        float yc = vert[2*v+1];
 
-        if( isSame(xc-curr[0],yc-curr[1]) )
+        if( edgesUp[c][v]<0 && isSame(xc-curr[0],yc-curr[1]) )
           {
-          int n = (j==num-1 ? 0 : j+1);
-          float xn = v[2*n];
-          float yn = v[2*n+1];
+          int n = (v==numV-1 ? 0 : v+1);
+          float xn = vert[2*n];
+          float yn = vert[2*n+1];
 
           double angle = computeAngle(vect[0], vect[1], xn-xc, yn-yc);
 
-          if (angle < minAngle)
+          if (angle > maxAngle)
             {
-            minAngle = angle;
+            maxAngle = angle;
             x = xn;
             y = yn;
             }
@@ -167,68 +151,304 @@ public class MeshMultigon extends MeshBase
         }
       }
 
+    //android.util.Log.e("D", "curr vert: "+curr[0]+" "+curr[1]+" vect "+vect[0]+" "+vect[1]+" : "+x+" "+y);
+
     return new float[] {x,y};
     }
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
-  private void computeOuterVectors()
+  private static int getNextIndex(float[][] vertices, int[][] unclaimedEdges, int currIndex, int numHoleVerts)
     {
-    mOuterVectors = new float[mNumOuter][];
+    int[] currEdge = unclaimedEdges[currIndex];
+    int currP = currEdge[0];
+    int currE = currEdge[1];
+    float[] polygon = vertices[currP];
+    int numV = polygon.length/2;
+    int nextE= currE<numV-1 ? currE+1 : 0;
 
-    for(int curr=0; curr<mNumOuter; curr++)
+    float x = polygon[2*nextE];
+    float y = polygon[2*nextE+1];
+
+    for(int e=0; e<numHoleVerts; e++)
       {
-      int prev = curr==0 ? mNumOuter-1 : curr-1;
-      int next = curr==mNumOuter-1 ? 0 : curr+1;
+      int[] edge = unclaimedEdges[e];
 
-      float[] vP = mOuterVertices[prev];
-      float[] vN = mOuterVertices[next];
+      if( edge[2]==1 )
+        {
+        int po = edge[0];
+        int ed = edge[1];
 
-      float dx = vP[0]-vN[0];
-      float dy = vP[1]-vN[1];
+        float cx = vertices[po][2*ed];
+        float cy = vertices[po][2*ed+1];
 
-      mOuterVectors[curr] = new float[] { dy,-dx };
+        if( isSame(cx-x,cy-y) )
+          {
+          edge[2] = 0;
+          return e;
+          }
+        }
       }
+
+    return -1;
     }
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
-  private void computeOuterVertices(float[][] vertices)
+  private static int generateHole(float[][] vertices, int[][] unclaimedEdges, float[][] output, int[][] edgesUp, int holeNumber, int numHoleVerts)
     {
-    ArrayList<float[]> tmp = new ArrayList<>();
+    int firstIndex=-1;
 
-    float[] vect = new float[] {1,0};
-    float[] first= detectFirstOuterVertex(vertices);
-    float[] next = first;
+    for(int e=0; e<numHoleVerts; e++)
+      if( unclaimedEdges[e][2]==1 )
+        {
+        firstIndex = e;
+        break;
+        }
 
-    do
+    int currIndex = firstIndex;
+    int nextIndex=-1;
+    int numAdded = 0;
+
+    while( nextIndex!=firstIndex )
       {
-      float[] prev = next;
-      next = detectNextOuterVertex(vertices,next,vect);
-      vect[0] = prev[0]-next[0];
-      vect[1] = prev[1]-next[1];
-      tmp.add(next);
+      nextIndex = getNextIndex(vertices,unclaimedEdges,currIndex,numHoleVerts);
+
+      int p = unclaimedEdges[nextIndex][0];
+      int v = unclaimedEdges[nextIndex][1];
+      edgesUp[p][v] = -holeNumber-2;
+
+      //printEdgeEnds("HOLE "+holeNumber,vertices, p, v);
+
+      currIndex = nextIndex;
+      int[] e = unclaimedEdges[nextIndex];
+      float[] polygon = vertices[e[0]];
+      output[numAdded][0] = polygon[2*e[1]];
+      output[numAdded][1] = polygon[2*e[1]+1];
+      numAdded++;
       }
-    while( !isSame(next[0]-first[0],next[1]-first[1]) );
 
-    mNumOuter = tmp.size();
-    mOuterVertices = new float[mNumOuter][];
-    for(int i=0; i<mNumOuter; i++) mOuterVertices[i] = tmp.remove(0);
+    return numAdded;
+    }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+  private static boolean doesNotBelongToOuter(float x, float y, float[][] outer)
+    {
+    for(float[] v : outer)
+      if(isSame(x-v[0], y-v[1])) return false;
+
+    return true;
+    }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+  private static float[][][] computeHoles(float[][] vertices, int[][] edgesUp, float[][] outer, int numHoleVerts)
+    {
+    int[][] unclaimedEdges = new int[numHoleVerts][];
+    int index = 0;
+    int numPoly = vertices.length;
+
+    for(int p=0; p<numPoly; p++)
+      {
+      float[] ve = vertices[p];
+      int numEdges = ve.length/2;
+
+      for(int e=0; e<numEdges; e++)
+        if( edgesUp[p][e]<0 )
+          {
+          float x1 = ve[2*e];
+          float y1 = ve[2*e+1];
+
+          int n = e<numEdges-1 ? e+1 : 0;
+          float x2 = ve[2*n];
+          float y2 = ve[2*n+1];
+
+          // yes, we need to check both ends of the edge - otherwise the
+          // following 3x3 situation (x - wall, o - hole ) does not work:
+          // x x x
+          // x o x
+          // o x x
+
+          if( doesNotBelongToOuter(x1,y1,outer) || doesNotBelongToOuter(x2,y2,outer) )
+            {
+            unclaimedEdges[index]=new int[] {p, e, 1};
+            index++;
+            }
+          }
+      }
+
+    int remaining = numHoleVerts;
+    ArrayList<float[][]> holes = new ArrayList<>();
+    float[][] output = new float[numHoleVerts][2];
+    int numHoles = 0;
+
+    while(remaining>0)
+      {
+      int num = generateHole(vertices,unclaimedEdges,output,edgesUp,numHoles,numHoleVerts);
+      remaining -= num;
+      numHoles++;
+
+      float[][] hole = new float[num][2];
+      for(int h=0; h<num; h++)
+        {
+        hole[h][0] = output[h][0];
+        hole[h][1] = output[h][1];
+        }
+
+      holes.add(hole);
+      }
+
+    float[][][] ret = new float[numHoles][][];
+    for(int h=0; h<numHoles; h++) ret[h] = holes.remove(0);
+
+    //android.util.Log.e("D", "Holes: "+numHoles+" HoleVertices: "+mNumHoleVerts+" numOuterVerts: "+mNumOuterVerts);
+
+    return ret;
+    }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+  private static int countEdgesDown(int[][] edgesUp)
+    {
+    int numEdgesDown = 0;
+
+    for(int[] edgeUp : edgesUp)
+      for(int edge : edgeUp)
+        if( edge<0 ) numEdgesDown++;
+
+    return numEdgesDown;
+    }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+  private float[] produceNormalVector(float[][] verts, float xs, float ys)
+    {
+    int vCurr,len = verts.length;
+
+    for(vCurr=0; vCurr<len; vCurr++)
+      {
+      float[] vs = verts[vCurr];
+      if( isSame(vs[0]-xs,vs[1]-ys) ) break;
+      }
+
+    if( vCurr==len ) android.util.Log.e("D", "ERROR in produceNormalVector!!");
+
+    int vPrev = vCurr==0 ? len-1 : vCurr-1;
+    int vNext = vCurr>=len-1 ? 0 : vCurr+1;
+    float[] vp = verts[vPrev];
+    float[] vn = verts[vNext];
+
+    return new float[] { vp[1]-vn[1], vn[0]-vp[0] };
     }
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
-  private int belongsToOuter(float x, float y)
+  private float[] produceNormalVector(float[][] verts, float xs, float ys, float xe, float ye)
     {
-    for( int i=0; i<mNumOuter; i++ )
+    int vCurr,len = verts.length;
+
+    for(vCurr=0; vCurr<len; vCurr++)
       {
-      float[] v = mOuterVertices[i];
-      if( isSame(x-v[0],y-v[1]) ) return i;
+      float[] vs = verts[vCurr];
+
+      if( isSame(vs[0]-xs,vs[1]-ys) )
+        {
+        int vNext = vCurr==len-1 ? 0 : vCurr+1;
+        float[] ve = verts[vNext];
+        if( isSame(ve[0]-xe,ve[1]-ye) ) break;
+        }
+      }
+
+    int vPrev = vCurr==0 ? len-1 : vCurr-1;
+    int vNext = vCurr>=len-1 ? 0 : vCurr+1;
+    float[] vp = verts[vPrev];
+    float[] vn = verts[vNext];
+
+    return new float[] { vp[1]-vn[1], vn[0]-vp[0] };
+    }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+  private void computeEdgeVectors(float[][] vertices, int[][] edgesUp)
+    {
+    int numComponents = vertices.length;
+    mEdgeVectors = new float[numComponents][][];
+
+    for(int c=0; c<numComponents; c++)
+      {
+      float[] polygon = vertices[c];
+      int numV = polygon.length/2;
+      mEdgeVectors[c] = new float[numV][];
+
+      for(int v=0; v<numV; v++)
+        {
+        int edgeUp = edgesUp[c][v];
+        float xs = polygon[2*v];
+        float ys = polygon[2*v+1];
+        int n = v==numV-1 ? 0 : v+1;
+        float xe = polygon[2*n];
+        float ye = polygon[2*n+1];
+
+        if( edgeUp<0 ) // external edge, normal vector
+          {
+          float[][] verts = mOuterAndHoleVertices[-edgeUp-1];
+          mEdgeVectors[c][v] = produceNormalVector(verts,xs,ys,xe,ye);
+          }
+        else // internal edge - but the vertex that begins it might still be outer!
+          {
+          int numComp = retIndexBelongs(xs,ys);
+
+          if( numComp<0 ) mEdgeVectors[c][v] = null;
+          else
+            {
+            float[][] verts = mOuterAndHoleVertices[numComp];
+            mEdgeVectors[c][v] = produceNormalVector(verts,xs,ys);
+            }
+          }
+        //android.util.Log.e("D", "edgeVectors "+c+" "+v+" null: "+(mEdgeVectors[c][v]==null) );
+        }
+      }
+    }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+  private void printEdgeEnds(String str, float[][] vertices, int p, int e)
+    {
+    float[] polygon = vertices[p];
+    int len = polygon.length/2;
+    int n = e<len-1 ? e+1 : 0;
+
+    android.util.Log.e("D", str+" edge "+p+" "+e+" : ("+polygon[2*e]+" "+polygon[2*e+1]+") - ("+polygon[2*n]+" "+polygon[2*n+1]+")");
+    }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+// ret:
+// -1  : vertex (x,y) is 'inner' (does not belong to outer vertices or any hole)
+// N>=0: vertex (x,y) is outer [ N==0 --> outer, 1--> 1sr hole, 2 --> 2nd hole, etc ]
+
+  private int retIndexBelongs(float x, float y)
+    {
+    int numOuterComponents = mOuterAndHoleVertices.length;
+
+    for(int c=0; c<numOuterComponents; c++)
+      {
+      float[][] comp = mOuterAndHoleVertices[c];
+
+      for(float[] v : comp)
+        if( isSame(x-v[0],y-v[1]) ) return c;
       }
 
     return -1;
     }
 
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+  private float[] retOuterVector(int component, int vert)
+    {
+    return mEdgeVectors[component][vert];
+    }
+
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
   private boolean[][] computeVertsUp(float[][] vertices)
@@ -244,8 +464,8 @@ public class MeshMultigon extends MeshBase
 
       for(int j=0; j<len; j++)
         {
-        int vert = belongsToOuter(v[2*j],v[2*j+1]);
-        up[i][j] = (vert==-1);
+        float[] vect = retOuterVector(i,j);
+        up[i][j] = (vect==null);
         }
       }
 
@@ -302,17 +522,15 @@ public class MeshMultigon extends MeshBase
       vT[0] = centers[component][0];
       vT[1] = centers[component][1];
 
-      int outerL = belongsToOuter(vL[0],vL[1]);
-      int outerR = belongsToOuter(vR[0],vR[1]);
+      float[] outerL = retOuterVector(component,curr);
+      float[] outerR = retOuterVector(component,next);
 
-      if( outerL>=0 && outerR>=0 )
+      if( outerL!=null && outerR!=null )
         {
-        float[] vl =mOuterVectors[outerL];
-        normL[0] = -vl[0];
-        normL[1] = -vl[1];
-        float[] vr =mOuterVectors[outerR];
-        normR[0] = -vr[0];
-        normR[1] = -vr[1];
+        normL[0] = -outerL[0];
+        normL[1] = -outerL[1];
+        normR[0] = -outerR[0];
+        normR[1] = -outerR[1];
         }
       else
         {
@@ -367,15 +585,14 @@ public class MeshMultigon extends MeshBase
         }
       else
         {
-        int outerT = belongsToOuter(vT[0],vT[1]);
+        float[] outerT = retOuterVector(component,curr);
 
-        if( outerT>=0 )
+        if( outerT!=null )
           {
-          float[] vt =mOuterVectors[outerT];
-          normL[0]= vt[0];
-          normL[1]= vt[1];
-          normR[0]= vt[0];
-          normR[1]= vt[1];
+          normL[0]= outerT[0];
+          normL[1]= outerT[1];
+          normR[0]= outerT[0];
+          normR[1]= outerT[1];
           }
         else
           {
@@ -394,6 +611,72 @@ public class MeshMultigon extends MeshBase
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 // PUBLIC API
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+  public static int[][] computeEdgesUp(float[][] vertices)
+    {
+    int numPoly = vertices.length;
+    int[][] up = new int[numPoly][];
+
+    for(int p=0; p<numPoly; p++)
+      {
+      int numEdges = vertices[p].length/2;
+      up[p] = new int[numEdges];
+
+      for(int e=0; e<numEdges; e++)
+        up[p][e] = isUp(vertices,p,e);
+      }
+
+    return up;
+    }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+  public static float[][][] computeOuterVertices(float[][] vertices, int[][] edgesUp)
+    {
+    ArrayList<float[]> tmp = new ArrayList<>();
+
+    float[] vect = new float[] {1,0};
+    float[] first= detectFirstOuterVertex(vertices);
+    float[] next = first;
+
+    do
+      {
+      float[] prev = next;
+      next = detectNextOuterVertex(vertices,next,vect,edgesUp);
+      vect[0] = prev[0]-next[0];
+      vect[1] = prev[1]-next[1];
+      tmp.add(next);
+      }
+    while( !isSame(next[0]-first[0],next[1]-first[1]) );
+
+    int numOuterVerts= tmp.size();
+    float[][] outerVertices = new float[numOuterVerts][];
+    for(int i=0; i<numOuterVerts; i++)
+      {
+      outerVertices[i] = tmp.remove(0);
+
+      //if( mNumOuterVerts>14 )
+      //  android.util.Log.e("D","outer: "+mOuterVertices[i][0]+" "+mOuterVertices[i][1]);
+      }
+
+    int numEdgesDown = countEdgesDown(edgesUp);
+    int numHoleVerts= numEdgesDown-numOuterVerts;
+    float[][][] holeVertices=null;
+
+    if( numHoleVerts>0 )
+      {
+      holeVertices = computeHoles(vertices,edgesUp,outerVertices,numHoleVerts);
+      }
+
+    int numHoles = holeVertices==null ? 0 : holeVertices.length;
+    float[][][] ret = new float[1+numHoles][][];
+    ret[0] = outerVertices;
+    for(int i=0; i<numHoles; i++) ret[i+1] = holeVertices[i];
+
+    return ret;
+    }
+
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 /**
  * Specify several lists of vertices. Each list defines one polygon. (@see MeshPolygon).
@@ -413,10 +696,11 @@ public class MeshMultigon extends MeshBase
     for(float[] vertex : vertices) numTriangles+=vertex.length/2;
     MeshBandedTriangle[] triangles = new MeshBandedTriangle[numTriangles];
 
-    computeOuterVertices(vertices);
-    computeOuterVectors();
-
     int[][] edgesUp = computeEdgesUp(vertices);
+    mOuterAndHoleVertices = computeOuterVertices(vertices,edgesUp);
+
+    computeEdgeVectors(vertices,edgesUp);
+
     boolean[][] vertsUp = computeVertsUp(vertices);
     float[][] centers = computeCenters(vertices);