commit fe3dec09d6b681532192558ba4c61737f53578a5
Author: Leszek Koltunski <leszek@koltunski.pl>
Date:   Sat Jun 17 22:51:43 2023 +0200

    use MeshMultigon in puzzle cubits (FactoryCubit)

diff --git a/src/main/java/org/distorted/objectlib/helpers/FactoryCubit.java b/src/main/java/org/distorted/objectlib/helpers/FactoryCubit.java
index 29d46db8..4b62ca3c 100644
--- a/src/main/java/org/distorted/objectlib/helpers/FactoryCubit.java
+++ b/src/main/java/org/distorted/objectlib/helpers/FactoryCubit.java
@@ -17,6 +17,7 @@ import org.distorted.library.effect.VertexEffect;
 import org.distorted.library.helpers.QuatHelper;
 import org.distorted.library.mesh.MeshBase;
 import org.distorted.library.mesh.MeshJoined;
+import org.distorted.library.mesh.MeshMultigon;
 import org.distorted.library.mesh.MeshPolygon;
 import org.distorted.library.type.Static3D;
 import org.distorted.library.type.Static4D;
@@ -41,9 +42,10 @@ public class FactoryCubit
 
   public static final String NAME = EffectName.DEFORM.name();
 
-  public static class StickerCoords
+  private static class StickerCoords
     {
     float[] vertices;
+    float[][] fullVertices;
     float scale;
     boolean outer;
     }
@@ -187,6 +189,113 @@ public class FactoryCubit
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
+  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++ )
+      {
+      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++)
+        {
+        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;
+            }
+
+          break;
+          }
+        }
+      }
+
+    return new float[] {x,y};
+    }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+// same as in MeshMultigon
+
+  private float[] computeOuterEdge(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();
+    float[] ret = new float[2*num];
+
+    for(int i=0; i<num; i++)
+      {
+      float[] t = tmp.remove(0);
+      ret[2*i  ] = t[0];
+      ret[2*i+1] = t[1];
+      }
+
+    return ret;
+    }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+// polygon
+
   private void fitInSquare(FaceTransform info, float[][] vert3D, boolean isOuter)
     {
     float minX = Float.MAX_VALUE;
@@ -221,6 +330,7 @@ public class FactoryCubit
     sInfo.outer = isOuter;
     sInfo.scale = info.scale;
     sInfo.vertices = new float[2*len];
+    sInfo.fullVertices = null;
 
     for( int vertex=0; vertex<len; vertex++ )
       {
@@ -233,7 +343,69 @@ public class FactoryCubit
     info.sticker = mStickerCoords.size() -1;
     }
 
+
 ///////////////////////////////////////////////////////////////////////////////////////////////////
+// multigon
+
+  private void fitInSquare(FaceTransform info, float[][][] vert3D, boolean isOuter)
+    {
+    float minX = Float.MAX_VALUE;
+    float maxX =-Float.MAX_VALUE;
+    float minY = Float.MAX_VALUE;
+    float maxY =-Float.MAX_VALUE;
+
+    for( float[][] vert : vert3D)
+      for( float[] v : vert)
+        {
+        float x = v[0];
+        float y = v[1];
+
+        if (x > maxX) maxX = x;
+        if (x < minX) minX = x;
+        if (y > maxY) maxY = y;
+        if (y < minY) minY = y;
+        }
+
+    minX = minX<0 ? -minX:minX;
+    maxX = maxX<0 ? -maxX:maxX;
+    minY = minY<0 ? -minY:minY;
+    maxY = maxY<0 ? -maxY:maxY;
+
+    float max1 = Math.max(minX,minY);
+    float max2 = Math.max(maxX,maxY);
+    float max3 = Math.max(max1,max2);
+
+    info.scale = max3/0.5f;
+
+    int len = vert3D.length;
+    StickerCoords sInfo = new StickerCoords();
+    sInfo.outer = isOuter;
+    sInfo.scale = info.scale;
+    sInfo.fullVertices = new float[len][];
+
+    for( int comp=0; comp<len; comp++ )
+      {
+      float[][] vert = vert3D[comp];
+      int num = vert.length;
+      sInfo.fullVertices[comp] = new float[2*num];
+      float[] t = sInfo.fullVertices[comp];
+
+      for( int vertex=0; vertex<num; vertex++)
+        {
+        t[2*vertex  ] = vert[vertex][0] / info.scale;
+        t[2*vertex+1] = vert[vertex][1] / info.scale;
+        }
+      }
+
+    sInfo.vertices = computeOuterEdge(sInfo.fullVertices);
+
+    mStickerCoords.add(sInfo);
+
+    info.sticker = mStickerCoords.size() -1;
+    }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+// polygon
 
   private FaceTransform constructNewTransform(final float[][] vert3D, boolean isOuter, int face, int numFaces)
     {
@@ -355,14 +527,144 @@ public class FactoryCubit
     return ft;
     }
 
+///////////////////////////////////////////////////////////////////////////////////////////////////
+// multigon
+
+  private FaceTransform constructNewTransform(final float[][][] vert3D, boolean isOuter, int face, int numFaces)
+    {
+    FaceTransform ft = new FaceTransform();
+    ft.face = face;
+    ft.numFaces = numFaces;
+
+    // compute center of gravity
+    ft.vx = 0.0f;
+    ft.vy = 0.0f;
+    ft.vz = 0.0f;
+    int len = 0;
+
+    for( float[][] vert : vert3D )
+      for( float[] v : vert )
+        {
+        ft.vx += v[0];
+        ft.vy += v[1];
+        ft.vz += v[2];
+        len++;
+        }
+
+    ft.vx /= len;
+    ft.vy /= len;
+    ft.vz /= len;
+
+    // move all vertices so that their center of gravity is at (0,0,0)
+    for( float[][] vert : vert3D )
+      for( float[] v : vert )
+        {
+        v[0] -= ft.vx;
+        v[1] -= ft.vy;
+        v[2] -= ft.vz;
+        }
+
+    // find 3 non-colinear vertices
+    int foundIndex = -1;
+    len = vert3D[0].length;
+
+    for(int vertex=2; vertex<len; vertex++)
+      {
+      if( !areColinear(vert3D[0],0,1,vertex) )
+        {
+        foundIndex = vertex;
+        break;
+        }
+      }
+
+    // compute the normal vector
+    if( foundIndex==-1 )
+      {
+      StringBuilder sb = new StringBuilder();
+
+      for (float[] v : vert3D[0])
+        {
+        sb.append(' ');
+        sb.append("(");
+        sb.append(v[0]);
+        sb.append(" ");
+        sb.append(v[1]);
+        sb.append(" ");
+        sb.append(v[2]);
+        sb.append(")");
+        }
+      android.util.Log.e("D", "verts: "+sb);
+
+      throw new RuntimeException("all vertices colinear");
+      }
+
+    computeNormalVector(vert3D[0],0,1,foundIndex);
+
+    // rotate so that the normal vector becomes (0,0,1)
+    float axisX, axisY, axisZ;
+
+    if( mBuffer[0]!=0.0f || mBuffer[1]!=0.0f )
+      {
+      axisX = -mBuffer[1];
+      axisY =  mBuffer[0];
+      axisZ = 0.0f;
+
+      float axiLen = axisX*axisX + axisY*axisY;
+      axiLen = (float)Math.sqrt(axiLen);
+      axisX /= axiLen;
+      axisY /= axiLen;
+      axisZ /= axiLen;
+      }
+    else
+      {
+      axisX = 0.0f;
+      axisY = 1.0f;
+      axisZ = 0.0f;
+      }
+
+    float cosTheta = mBuffer[2];
+    float sinTheta = (float)Math.sqrt(1-cosTheta*cosTheta);
+    float sinHalfTheta = computeSinHalf(cosTheta);
+    float cosHalfTheta = computeCosHalf(sinTheta,cosTheta);
+
+    mQuat1[0] = axisX*sinHalfTheta;
+    mQuat1[1] = axisY*sinHalfTheta;
+    mQuat1[2] = axisZ*sinHalfTheta;
+    mQuat1[3] = cosHalfTheta;
+    mQuat2[0] =-axisX*sinHalfTheta;
+    mQuat2[1] =-axisY*sinHalfTheta;
+    mQuat2[2] =-axisZ*sinHalfTheta;
+    mQuat2[3] = cosHalfTheta;
+
+    for( float[][] vert : vert3D)
+      for( float[] v : vert)
+        {
+        QuatHelper.quatMultiply(mQuat3, mQuat1, v  );
+        QuatHelper.quatMultiply(  v, mQuat3, mQuat2);
+        }
+
+    // fit the whole thing in a square and remember the scale & 2D vertices
+    fitInSquare(ft, vert3D, isOuter);
+
+    // remember the rotation
+    ft.qx =-mQuat1[0];
+    ft.qy =-mQuat1[1];
+    ft.qz =-mQuat1[2];
+    ft.qw = mQuat1[3];
+
+    return ft;
+    }
+
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
   private void rotateAllVertices(float[] result, int len, float[] vertices, float sin, float cos)
     {
     for(int i=0; i<len; i++)
       {
-      result[2*i  ] = vertices[2*i  ]*cos - vertices[2*i+1]*sin;
-      result[2*i+1] = vertices[2*i  ]*sin + vertices[2*i+1]*cos;
+      float x = vertices[2*i];
+      float y = vertices[2*i+1];
+      result[2*i  ] = x*cos - y*sin;
+      result[2*i+1] = x*sin + y*cos;
       }
     }
 
@@ -577,6 +879,7 @@ public class FactoryCubit
     }
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
+// polygon
 
   private float[][] constructVert(float[][] vertices, int[] index)
     {
@@ -595,6 +898,34 @@ public class FactoryCubit
     return ret;
     }
 
+///////////////////////////////////////////////////////////////////////////////////////////////////
+// multigon
+
+  private float[][][] constructVert(float[][] vertices, int[][] index)
+    {
+    int len = index.length;
+    float[][][] ret = new float[len][][];
+
+    for(int i=0; i<len; i++)
+      {
+      int[] ind = index[i];
+      int num = ind.length;
+      ret[i] = new float[num][4];
+
+      for(int j=0; j<num; j++)
+        {
+        float[] r = ret[i][j];
+        float[] v = vertices[ind[j]];
+        r[0] = v[0];
+        r[1] = v[1];
+        r[2] = v[2];
+        r[3] = 1.0f;
+        }
+      }
+
+    return ret;
+    }
+
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
   private void applyVertexEffects(MeshBase mesh, ObjectVertexEffects effects, int meshState)
@@ -796,7 +1127,6 @@ public class FactoryCubit
   public static FactoryCubit getInstance()
     {
     if( mThis==null ) mThis = new FactoryCubit();
-
     return mThis;
     }
 
@@ -982,6 +1312,8 @@ public class FactoryCubit
     {
     float[][] vertices = shape.getVertices();
     int[][] indices = shape.getVertIndices();
+    int[][][] fullIndices = shape.getMultigonIndices();
+    boolean isMultigon = shape.isMultigon();
     FaceTransform ft;
     int numNew = mNewFaceTransf.size();
 
@@ -991,15 +1323,25 @@ public class FactoryCubit
       mOldFaceTransf.add(ft);
       }
 
-    int numFaces = indices.length;
+    int numFaces = shape.getNumFaces();
     int numOld = mOldFaceTransf.size();
 
     for (int face=0; face<numFaces; face++)
       {
       boolean collapsed = false;
       boolean isOuter = (outer!=null && outer[face]>0);
-      float[][] vert = constructVert(vertices, indices[face]);
-      FaceTransform newT = constructNewTransform(vert,isOuter,face,numFaces);
+      FaceTransform newT;
+
+      if( !isMultigon )
+        {
+        float[][] vert = constructVert(vertices, indices[face]);
+        newT = constructNewTransform(vert,isOuter,face,numFaces);
+        }
+      else
+        {
+        float[][][] vert = constructVert(vertices, fullIndices[face]);
+        newT = constructNewTransform(vert,isOuter,face,numFaces);
+        }
 
       for (int old=0; !collapsed && old<numOld; old++)
         {
@@ -1022,12 +1364,12 @@ public class FactoryCubit
   public MeshBase createRoundedSolid(final ObjectShape shape, final ObjectFaceShape faceShape,
                                      final ObjectVertexEffects effects, int meshState, int numComponents)
     {
-    int[][] vertIndexes     = shape.getVertIndices();
     float[][] bands         = faceShape.getBands();
     int[]   bandIndexes     = faceShape.getBandIndices();
     float[] convexityCenter = faceShape.getConvexityCenter();
 
-    int numFaces = vertIndexes.length;
+    int numFaces = shape.getNumFaces();
+    boolean multigonMode = shape.isMultigon();
     float[] band, bandsComputed;
     MeshBase[] meshes = new MeshBase[numFaces];
     FaceTransform fInfo;
@@ -1039,13 +1381,6 @@ public class FactoryCubit
     for(int face=0; face<numFaces; face++)
       {
       fInfo = mNewFaceTransf.get(face);
-      sInfo = mStickerCoords.get(fInfo.sticker);
-
-      float[] verts = sInfo.vertices;
-      int lenVerts = verts.length;
-      float[] copiedVerts = new float[lenVerts];
-      System.arraycopy(verts, 0, copiedVerts, 0, lenVerts);
-
       computeConvexityCenter(convexXY,convexityCenter,fInfo);
 
       int index = bandIndexes[face];
@@ -1073,7 +1408,34 @@ public class FactoryCubit
         }
 
       bandsComputed = computeBands(height,alpha,dist,K,N);
-      meshes[face] = new MeshPolygon(copiedVerts,bandsComputed,null,null,exIndex,exVertices, convexXY[0], convexXY[1]);
+
+      if( !multigonMode )
+        {
+        sInfo = mStickerCoords.get(fInfo.sticker);
+        float[] verts = sInfo.vertices;
+        int lenVerts = verts.length;
+        float[] copiedVerts = new float[lenVerts];
+        System.arraycopy(verts, 0, copiedVerts, 0, lenVerts);
+        meshes[face] = new MeshPolygon(copiedVerts,bandsComputed,null,null,exIndex,exVertices, convexXY[0], convexXY[1]);
+        }
+      else
+        {
+        sInfo = mStickerCoords.get(fInfo.sticker);
+        float[][] verts = sInfo.fullVertices;
+        int lenVerts = verts.length;
+        float[][] copiedVerts = new float[lenVerts][];
+
+        for(int i=0; i<lenVerts; i++)
+          {
+          float[] v = verts[i];
+          int len = v.length;
+          copiedVerts[i] = new float[len];
+          System.arraycopy(v, 0, copiedVerts[i], 0, len);
+          }
+
+        meshes[face] = new MeshMultigon(copiedVerts,bandsComputed,exIndex,exVertices);
+        }
+
       meshes[face].setEffectAssociation(0,0,face);
       }
 
diff --git a/src/main/java/org/distorted/objectlib/helpers/ObjectShape.java b/src/main/java/org/distorted/objectlib/helpers/ObjectShape.java
index 09b75e3f..815b1a94 100644
--- a/src/main/java/org/distorted/objectlib/helpers/ObjectShape.java
+++ b/src/main/java/org/distorted/objectlib/helpers/ObjectShape.java
@@ -24,12 +24,44 @@ public class ObjectShape
   private final float[][] mVertices;
   private final int[][] mVertIndices;
 
+  private final boolean mFacesMultigon;
+  private final int mNumFaces;
+  private final int[][][] mMultigonIndices;
+
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
   public ObjectShape(float[][] vertices, int[][] vertIndices)
     {
-    mVertices   = vertices;
-    mVertIndices= vertIndices;
+    mVertices        = vertices;
+    mVertIndices     = vertIndices;
+    mMultigonIndices = null;
+    mFacesMultigon   = false;
+    mNumFaces        = vertIndices.length;
+    }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+  public ObjectShape(float[][] vertices, int[][][] vertIndices)
+    {
+    mVertices       = vertices;
+    mVertIndices    = null;
+    mMultigonIndices= vertIndices;
+    mFacesMultigon  = true;
+    mNumFaces       = vertIndices.length;
+    }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+  public int getNumFaces()
+    {
+    return mNumFaces;
+    }
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+  public boolean isMultigon()
+    {
+    return mFacesMultigon;
     }
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
@@ -46,6 +78,13 @@ public class ObjectShape
     return mVertIndices;
     }
 
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+  public int[][][] getMultigonIndices()
+    {
+    return mMultigonIndices;
+    }
+
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
   public static int computeNumComponents(ObjectShape[] shapes)
