commit a60f7acf364f1a937d8d67fc1490f03cc9e3bf64
Author: Leszek Koltunski <leszek@koltunski.pl>
Date:   Thu Jun 15 15:25:41 2023 +0200

    MeshMultigon finished.

diff --git a/src/main/java/org/distorted/library/mesh/MeshMultigon.java b/src/main/java/org/distorted/library/mesh/MeshMultigon.java
index af76035..f439b19 100644
--- a/src/main/java/org/distorted/library/mesh/MeshMultigon.java
+++ b/src/main/java/org/distorted/library/mesh/MeshMultigon.java
@@ -20,6 +20,10 @@
 
 package org.distorted.library.mesh;
 
+import java.util.ArrayList;
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
 /**
  * Create a 'multigon' mesh - a union of several polygons.
  *
@@ -31,73 +35,204 @@ package org.distorted.library.mesh;
 public class MeshMultigon extends MeshBase
   {
   private static final float MAX_ERROR = 0.0001f;
+  private float[][] mOuterVertices;
 
-  private boolean isSame(float[] v1, float[] v2)
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+  private boolean isSame(float dx, float dy)
     {
-    float dx = v1[0]-v2[0];
-    float dy = v1[1]-v2[1];
     return (dx*dx + dy*dy < MAX_ERROR);
     }
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
-  private boolean isUp(float[][][] vertices, int polygon, int edge)
+  private boolean isUp(float[][] vertices, int polygon, int edge)
     {
-    float[][] p = vertices[polygon];
-    int lenP = p.length;
+    //android.util.Log.e("D", "checking polygon "+polygon+" edge "+edge);
+
+    float[] p= vertices[polygon];
+    int lenP = p.length/2;
     int len  = vertices.length;
     int next = (edge==lenP-1 ? 0 : edge+1);
 
-    float[] v1 = p[edge];
-    float[] v2 = p[next];
+    float v1x = p[2*edge  ];
+    float v1y = p[2*edge+1];
+    float v2x = p[2*next  ];
+    float v2y = p[2*next+1];
+
+    //android.util.Log.e("D", " v1="+v1x+" "+v1y+"  v2="+v2x+" "+v2y);
 
     for(int i=0; i<len; i++)
       if( i!=polygon )
         {
-        int num = vertices[i].length;
+        int num = vertices[i].length/2;
 
         for(int j=0; j<num; j++)
           {
           int n = (j==num-1 ? 0 : j+1);
-          if( isSame(v2,vertices[i][j]) && isSame(v1,vertices[i][n]) ) return true;
+          float[] v = vertices[i];
+          float x1 = v[2*j  ];
+          float y1 = v[2*j+1];
+          float x2 = v[2*n  ];
+          float y2 = v[2*n+1];
+
+          //android.util.Log.e("D", "comparing v2 to "+x1+" "+y1);
+          //android.util.Log.e("D", "comparing v1 to "+x2+" "+y2);
+
+          if( isSame(v2x-x1,v2y-y1) && isSame(v1x-x2,v1y-y2) ) return true;
           }
         }
 
+    //android.util.Log.e("D", "FALSE");
+
     return false;
     }
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
-  private boolean[][] computeUp(float[][] vertices, float[][] centers)
+  private boolean[][] computeEdgesUp(float[][] vertices)
     {
     int num = vertices.length;
     boolean[][] up = new boolean[num][];
-    float[][][] v = new float[num][][];
 
     for(int i=0; i<num; i++)
       {
       int len = vertices[i].length/2;
-      v[i] = new float[len][2];
-
+      up[i] = new boolean[len];
       for(int j=0; j<len; j++)
         {
-        v[i][j][0] = vertices[i][2*j  ] + centers[i][0];
-        v[i][j][1] = vertices[i][2*j+1] + centers[i][1];
+        up[i][j] = isUp(vertices,i,j);
+        //android.util.Log.e("D", "polygon "+i+" edge "+j+" up: "+up[i][j]);
         }
       }
 
-    for(int i=0; i<num; i++)
+    return up;
+    }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+  private float[] detectFirstOuterVertex(float[][] vertices)
+    {
+    float X = -Float.MAX_VALUE;
+    int I=0,J=0, len = vertices.length;
+
+    for(int i=0; i<len; i++ )
       {
-      int len = vertices[i].length/2;
-      up[i] = new boolean[len];
-      for(int j=0; j<len; j++)
+      float[] v = vertices[i];
+      int num = v.length/2;
+
+      for(int j=0; j<num; j++)
+        if(v[2*j]>X)
+          {
+          X = v[2*j];
+          I = i;
+          J = j;
+          }
+      }
+
+    float[] v = vertices[I];
+    return new float[] {v[2*J],v[2*J+1]};
+    }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+  private 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;
+    }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+  private float[] detectNextOuterVertex(float[][] vertices, float[] curr, float[] vect)
+    {
+    double minAngle = 2*Math.PI;
+    float x=0, y=0;
+
+    for( float[] v : vertices )
+      {
+      int num = v.length/2;
+
+      for( int j=0; j<num; j++)
         {
-        up[i][j] = isUp(v,i,j);
+        float xc = v[2*j];
+        float yc = v[2*j+1];
+
+        if( 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];
+
+          double angle = computeAngle(vect[0], vect[1], xn-xc, yn-yc);
+
+          if (angle < minAngle)
+            {
+            minAngle = angle;
+            x = xn;
+            y = yn;
+            }
 
-        android.util.Log.e("D", "polygon "+i+" edge "+j+" up: "+up[i][j]);
+          break;
+          }
         }
       }
 
+    return new float[] {x,y};
+    }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+  private void computeOuter(float[][] vertices)
+    {
+    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);
+      vect[0] = prev[0]-next[0];
+      vect[1] = prev[1]-next[1];
+      tmp.add(next);
+      }
+    while( next[0]!=first[0] || next[1]!=first[1] );
+
+    int num = tmp.size();
+    mOuterVertices = new float[num][];
+    for(int i=0; i<num; i++) mOuterVertices[i] = tmp.remove(0);
+    }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+  private boolean doesntBelongToOuter(float x, float y)
+    {
+    for( float[] v : mOuterVertices )
+      if( x==v[0] && y==v[1] ) return false;
+
+    return true;
+    }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+  private boolean[][] computeVertsUp(float[][] vertices)
+    {
+    computeOuter(vertices);
+
+    int num = vertices.length;
+    boolean[][] up = new boolean[num][];
+
+    for(int i=0; i<num; i++)
+      {
+      float[] v = vertices[i];
+      int len = v.length/2;
+      up[i] = new boolean[len];
+      for(int j=0; j<len; j++) up[i][j] = doesntBelongToOuter(v[2*j],v[2*j+1]);
+      }
+
     return up;
     }
 
@@ -121,10 +256,43 @@ public class MeshMultigon extends MeshBase
 
     int numPolygons = vertices.length;
     MeshPolygon[] meshes = new MeshPolygon[numPolygons];
-    boolean[][] up = computeUp(vertices,centers);
+    boolean[][] edgesUp = computeEdgesUp(vertices);
+    boolean[][] vertsUp = computeVertsUp(vertices);
+
+    for(int i=0; i<numPolygons; i++)
+      meshes[i] = new MeshPolygon(vertices[i],band,edgesUp[i],vertsUp[i],exIndex,exVertices,centers[i][0],centers[i][1]);
+
+    join(meshes);
+    }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ * Auto-create the centers to be the centers of gravity of each polygon.
+ */
+
+  public MeshMultigon(float[][] vertices, float[] band, int exIndex, int exVertices)
+    {
+    super();
+
+    int numPolygons = vertices.length;
+    MeshPolygon[] meshes = new MeshPolygon[numPolygons];
+    boolean[][] edgesUp = computeEdgesUp(vertices);
+    boolean[][] vertsUp = computeVertsUp(vertices);
 
     for(int i=0; i<numPolygons; i++)
-      meshes[i] = new MeshPolygon(vertices[i],band,up[i],exIndex,exVertices,centers[i][0],centers[i][1]);
+      {
+      float[] v = vertices[i];
+      int num = v.length/2;
+      float xsum=0, ysum = 0;
+
+      for(int j=0; j<num; j++)
+        {
+        xsum += v[2*j];
+        ysum += v[2*j+1];
+        }
+
+      meshes[i] = new MeshPolygon(v,band,edgesUp[i],vertsUp[i],exIndex,exVertices,xsum/num,ysum/num);
+      }
 
     join(meshes);
     }
diff --git a/src/main/java/org/distorted/library/mesh/MeshPolygon.java b/src/main/java/org/distorted/library/mesh/MeshPolygon.java
index 3a7ba31..b46e58c 100644
--- a/src/main/java/org/distorted/library/mesh/MeshPolygon.java
+++ b/src/main/java/org/distorted/library/mesh/MeshPolygon.java
@@ -45,12 +45,14 @@ public class MeshPolygon extends MeshBase
   private float[] mPolygonBands;
   private int mNumPolygonBands;
   private boolean[] mEdgeUp;
+  private boolean[] mVertUp;
 
   private int remainingVert;
   private int numVertices;
   private int extraIndex, extraVertices;
 
   private float[] mCurveCache;
+  private float[] mEdgeQuots;
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 // polygonVertices>=3 , polygonBands>=2
@@ -116,6 +118,34 @@ public class MeshPolygon extends MeshBase
     mCurveCache[NUM_CACHE-1] = tmpD[mNumPolygonBands];
     }
 
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+  private void computeQuots()
+    {
+    mEdgeQuots = new float[mNumPolygonVertices];
+
+    for(int i=0; i<mNumPolygonVertices; i++)
+      {
+      int n = (i==mNumPolygonVertices-1 ? 0:i+1);
+
+      float x1 = mPolygonVertices[2*i];
+      float y1 = mPolygonVertices[2*i+1];
+      float x2 = mPolygonVertices[2*n];
+      float y2 = mPolygonVertices[2*n+1];
+      float A = x1-x2;
+      float B = y1-y2;
+      float C = A*A+B*B;
+
+      float x = (B*B*x1-A*B*y1)/C;
+      float y = (A*A*y1-A*B*x1)/C;
+
+      float dx = x1-x;
+      float dy = y1-y;
+
+      mEdgeQuots[i] = (float)Math.sqrt((dx*dx+dy*dy)/C);
+      }
+    }
+
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
   private float getSpecialQuot(int index)
@@ -209,7 +239,7 @@ public class MeshPolygon extends MeshBase
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
   private void doNormals(float[] attribs1, int index, float quot, int edgeShape,
-                         float xEdge, float yEdge, float zEdge, int polyBand)
+                         float xEdge, float yEdge, float zEdge, int polyVertex, int polyBand)
     {
     if( ( quot<=0.5f && (edgeShape==SHAPE_UD || edgeShape==SHAPE_UU) ) ||
         ( quot> 0.5f && (edgeShape==SHAPE_DU || edgeShape==SHAPE_UU) )  )
@@ -220,11 +250,23 @@ public class MeshPolygon extends MeshBase
       }
     else
       {
-      float t = mPolygonBands[2*mNumPolygonBands-1];
-      float x = 1.0f - mPolygonBands[2*polyBand];
-      float d = derivative(x);
+      float d,x = 1-mPolygonBands[2*polyBand];
 
-      d *= ((t-zEdge)/t);
+      if( /*quot==0.0f || quot==1.0f ||*/ edgeShape==SHAPE_DD )
+        {
+        float t = mPolygonBands[2*mNumPolygonBands-1];
+        d = ((t-zEdge)/t)*derivative(x);
+        }
+      else
+        {
+        float q = quot + x*(mEdgeQuots[polyVertex]-quot);
+        d = (q<0.5f ? derivative(2*q) : -derivative(2-2*q));
+        int nextVertex = polyVertex==mNumPolygonVertices-1 ? 0:polyVertex+1;
+        xEdge = mPolygonVertices[2*polyVertex  ] - mPolygonVertices[2*nextVertex  ];
+        yEdge = mPolygonVertices[2*polyVertex+1] - mPolygonVertices[2*nextVertex+1];
+
+        //android.util.Log.e("D", "normals: edgeQuot="+mEdgeQuots[polyVertex]+" vertex="+polyVertex+" d="+d+" xEdge="+xEdge+" yEdge="+yEdge+" q="+q+" quot="+quot);
+        }
 
       float vx = d*xEdge;
       float vy = d*yEdge;
@@ -275,7 +317,7 @@ public class MeshPolygon extends MeshBase
     attribs1[VERT1_ATTRIBS*vertex + POS_ATTRIB+2] = z;
 
     int index = VERT1_ATTRIBS*vertex + NOR_ATTRIB;
-    doNormals(attribs1,index, quot, edgeShape, xEdge, yEdge, zEdge, polyBand);
+    doNormals(attribs1,index, quot, edgeShape, xEdge, yEdge, zEdge, polyVertex, polyBand);
 
     attribs2[VERT2_ATTRIBS*vertex + TEX_ATTRIB  ] = x+0.5f;
     attribs2[VERT2_ATTRIBS*vertex + TEX_ATTRIB+1] = y+0.5f;
@@ -330,10 +372,10 @@ public class MeshPolygon extends MeshBase
     int prev = (curr==0 ? mNumPolygonVertices-1 : curr-1);
     int next = (curr==mNumPolygonVertices-1 ? 0 : curr+1);
 
-    boolean l = mEdgeUp[prev];
-    boolean r = mEdgeUp[next];
+    boolean rd = ( !mEdgeUp[next] || mVertUp==null || !mVertUp[next] );
+    boolean ld = ( !mEdgeUp[prev] || mVertUp==null || !mVertUp[curr] );
 
-    return l ? (r ? SHAPE_UU : SHAPE_UD) : (r ? SHAPE_DU : SHAPE_DUD);
+    return rd ? (ld ? SHAPE_DUD : SHAPE_UD) : (ld ? SHAPE_DU : SHAPE_UU);
     }
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
@@ -377,6 +419,11 @@ public class MeshPolygon extends MeshBase
  *                   If the 'previous' edge is also up, then the Z is up horizontally from its middle
  *                   to the left vertex; else it goes down along the same function it goes along the bands.
  *                   Same with the right half of the edge.
+ * @param vertUp     N booleans - one for each vertex. The first is about vertex 0, then vertex 1, etc.
+ *                   If this is null or false, the vertex is down; otheerwise - it is 'up'.
+ *                   This is taken into account only in one case: if both edges the vertex is the end of
+ *                   are 'up', then the vertex can be 'up' or 'down'; otherwise - if at least one of
+ *                   those edges is 'down' - then the vertex must be 'down' as well and this is ignored.
  * @param exIndex    This and the next parameter describe how to make the mesh denser at the
  *                   polyVertices. If e.g. exIndex=3 and exVertices=2, then 3 triangles of the
  *                   outermost band (and 2 triangles of the next band, and 1 triangle of the third
@@ -386,7 +433,7 @@ public class MeshPolygon extends MeshBase
  *                   all bands go to.
  * @param centerY    Y coordinate of the center.
  */
-  public MeshPolygon(float[] verticesXY, float[] bands, boolean[] edgeUp, int exIndex, int exVertices, float centerX, float centerY)
+  public MeshPolygon(float[] verticesXY, float[] bands, boolean[] edgeUp, boolean[] vertUp, int exIndex, int exVertices, float centerX, float centerY)
     {
     super();
 
@@ -395,6 +442,7 @@ public class MeshPolygon extends MeshBase
     mNumPolygonVertices= mPolygonVertices.length /2;
     mNumPolygonBands   = mPolygonBands.length /2;
     mEdgeUp            = edgeUp;
+    mVertUp            = vertUp;
     extraIndex         = exIndex;
     extraVertices      = exVertices;
 
@@ -409,6 +457,7 @@ public class MeshPolygon extends MeshBase
 
     computeNumberOfVertices();
     computeCache();
+    computeQuots();
 
     float[] attribs1= new float[VERT1_ATTRIBS*numVertices];
     float[] attribs2= new float[VERT2_ATTRIBS*numVertices];
@@ -436,7 +485,7 @@ public class MeshPolygon extends MeshBase
 
   public MeshPolygon(float[] verticesXY, float[] bands, int exIndex, int exVertices)
     {
-    this(verticesXY,bands,null,exIndex,exVertices,0.0f,0.0f);
+    this(verticesXY,bands,null,null,exIndex,exVertices,0.0f,0.0f);
     }
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
@@ -446,7 +495,7 @@ public class MeshPolygon extends MeshBase
  */
   public MeshPolygon(float[] verticesXY, float[] bands)
     {
-    this(verticesXY,bands,null,0,0,0.0f,0.0f);
+    this(verticesXY,bands,null,null,0,0,0.0f,0.0f);
     }
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////