TwistyPuzzleLib

import org.distorted.library.mesh.MeshMultigon;

  private static class StickerCoords

    float[][] fullVertices;

  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

    sInfo.fullVertices = null;

// 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

///////////////////////////////////////////////////////////////////////////////////////////////////

// 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;

    }

      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;

// polygon

///////////////////////////////////////////////////////////////////////////////////////////////////

// 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;

    }

    int[][][] fullIndices = shape.getMultigonIndices();

    boolean isMultigon = shape.isMultigon();

    int numFaces = shape.getNumFaces();

      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);

        }

    int numFaces = shape.getNumFaces();

    boolean multigonMode = shape.isMultigon();

      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);

        }

  private final boolean mFacesMultigon;

  private final int mNumFaces;

  private final int[][][] mMultigonIndices;

    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;

///////////////////////////////////////////////////////////////////////////////////////////////////

  public int[][][] getMultigonIndices()

    {

    return mMultigonIndices;

    }