TwistyPuzzleLib

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

// Copyright 2021 Leszek Koltunski                                                               //

//                                                                                               //

// This file is part of Magic Cube.                                                              //

//                                                                                               //

// Magic Cube is proprietary software licensed under an EULA which you should have received      //

// along with the code. If not, check https://distorted.org/magic/License-Magic-Cube.html        //

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

package org.distorted.objectlib.touchcontrol;

import org.distorted.library.helpers.QuatHelper;

import org.distorted.library.type.Static3D;

import org.distorted.library.type.Static4D;

import org.distorted.objectlib.helpers.ObjectShape;

import org.distorted.objectlib.main.TwistyObject;

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

public class TouchControlShapeChanging extends TouchControl

  {

  private static final float NOT_TOUCHED = 1000000.0f;

  static final float[] mTmp = new float[4];

  static class FaceInfo

    {

    private final float[] normal;      // vector normal to the surface of the face, pointing outside.

    private final float distance;      // distance from (0,0,0) to the surface of the face

    private final float[][] vertices;  // vertices of the face. Already rotated by the initQuat and

                                       // moved by 'position' (arithmetic average of all positions)

    private final float[][] rotated;   // temp array to store vertices times rotation quaternion.

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

    FaceInfo(float[][] verts, float size)

      {

      int numV = verts.length;

      vertices = new float[numV][];

      rotated  = new float[numV][];

      for(int i=0; i<numV; i++)

        {

        int len = verts[i].length;

        vertices[i]= new float[len];

        rotated[i] = new float[len];

        for(int j=0; j<len; j++) vertices[i][j] = verts[i][j]/size;

        }

      // assuming the first three vertices are linearly independent

      float[] v0 = vertices[0];

      float[] v1 = vertices[1];

      float[] v2 = vertices[2];

      float a1 = v0[0] - v1[0];

      float a2 = v0[1] - v1[1];

      float a3 = v0[2] - v1[2];

      float b1 = v1[0] - v2[0];

      float b2 = v1[1] - v2[1];

      float b3 = v1[2] - v2[2];

      float vx = a2*b3-a3*b2;

      float vy = a3*b1-a1*b3;

      float vz = a1*b2-a2*b1;

      float len = (float)Math.sqrt(vx*vx+vy*vy+vz*vz);

      vx/=len;

      vy/=len;

      vz/=len;

      normal = new float[4];

      normal[0] = vx;

      normal[1] = vy;

      normal[2] = vz;

      normal[3] = 0.0f;

      if( totalAngle(vertices,normal)<0 )

        {

        normal[0] *= -1;

        normal[1] *= -1;

        normal[2] *= -1;

        }

      distance = normal[0]*v0[0] + normal[1]*v0[1] + normal[2]*v0[2];

      }

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

    // this returns the total angle we get rotated about when

    // we travel from the first vert to the last.

    // It's always should be +2PI or -2PI, depending on if the

    // verts are CW or CCW (when looking at the plane formed by

    // the vertices from the direction the 'normal' vector

    // points towards)

    //

    // The point: this way we can detect if the 'normal' vector

    // is correct, i.e. if it points in the right direction.

    // Sometimes it does not, when the first three vertices

    // (from which the vector is computed) are 'concave'.

    private float totalAngle(float[][] vert, float[] normal)

      {

      float ret = 0;

      int num = vert.length;

      for(int c=0; c<num; c++)

        {

        int n = (c==num-1 ? 0 : c+1);

        int m = (n==num-1 ? 0 : n+1);

        ret += angle( vert[c],vert[n],vert[m], normal);

        }

      return ret;

      }

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

    private float angle(float[] v0, float[] v1, float[] v2, float[] normal)

      {

      float px = v1[0] - v0[0];

      float py = v1[1] - v0[1];

      float pz = v1[2] - v0[2];

      float rx = v2[0] - v1[0];

      float ry = v2[1] - v1[1];

      float rz = v2[2] - v1[2];

      float l1 = (float)Math.sqrt(px*px + py*py + pz*pz);

      float l2 = (float)Math.sqrt(rx*rx + ry*ry + rz*rz);

      px /= l1;

      py /= l1;

      pz /= l1;

      rx /= l2;

      ry /= l2;

      rz /= l2;

      float s = px*rx + py*ry + pz*rz;

      if( s> 1 ) s= 1;

      if( s<-1 ) s=-1;

      float a = (float) Math.acos(s);

      float[] cross = crossProduct(px,py,pz,rx,ry,rz);

      float ax = cross[0] + normal[0];

      float ay = cross[1] + normal[1];

      float az = cross[2] + normal[2];

      float bx = cross[0] - normal[0];

      float by = cross[1] - normal[1];

      float bz = cross[2] - normal[2];

      float f1 = ax*ax + ay*ay + az*az;

      float f2 = bx*bx + by*by + bz*bz;

      return f1>f2 ? a : -a;

      }

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

    private float[] crossProduct(float a1, float a2, float a3, float b1, float b2, float b3)

      {

      float[] ret = new float[3];

      ret[0] = a2*b3 - a3*b2;

      ret[1] = a3*b1 - a1*b3;

      ret[2] = a1*b2 - a2*b1;

      return ret;

      }

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

    public float[] getNormal()

      {

      return normal;

      }

    }

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

  // end FaceInfo

  private final float[] mTouch, mLastT;

  private final Static4D mTmpAxis;

  private int mNumCubits;

  private int[] mNumFaces;

  private boolean mPreparationDone;

  private boolean[][] mRotatable;

  private float[][] mCuts;

  final float[] mCamera, mPoint;

  final Static3D[] mRotAxis;

  final TwistyObject mObject;

  int mTouchedCubit, mTouchedCubitFace, mNumAxis;

  FaceInfo[][] mInfos;

  float[][] mQuats;

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

  public TouchControlShapeChanging(TwistyObject object)

    {

    super(object);

    mPoint = new float[3];

    mCamera= new float[3];

    mTouch = new float[3];

    mLastT = new float[3];

    mObject= object;

    mPreparationDone = false;

    mTmpAxis = new Static4D(0,0,0,0);

    mGhostAxisEnabled = -1;

    if( object!=null )

      {

      int[] numL  = object.getNumLayers();

      mRotAxis    = object.getRotationAxis() ;

      mNumAxis    = mRotAxis.length;

      mRotatable  = object.getLayerRotatable(numL);

      mCuts       = object.getCuts(numL);

      float size  = object.getSize();

      computeBorders(mCuts,mRotatable,size);

      }

    else

      {

      mRotAxis = null;

      mNumAxis = 0;

      }

    }

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

// mesh multigon

  private FaceInfo[] computeInfos(float[][] vertices, int[][][] indices, float[] position, Static4D quat, float size)

    {

    int len = position.length/3;

    float avgX = 0.0f;

    float avgY = 0.0f;

    float avgZ = 0.0f;

    for(int i=0; i<len; i++)

      {

      avgX += position[3*i  ];

      avgY += position[3*i+1];

      avgZ += position[3*i+2];

      }

    avgX /= len;

    avgY /= len;

    avgZ /= len;

    int numFaces = indices.length;

    FaceInfo[] infos = new FaceInfo[numFaces];

    Static4D tmp;

    for(int f=0; f<numFaces; f++)

      {

      int[][] inds = indices[f];

      int numSegments = inds.length;

      int numVerts = 0;

      for(int[] ind : inds) numVerts += ind.length;

      float[][] verts = new float[numVerts][4];

      int pointer = 0;

      for(int s=0; s<numSegments; s++)

        {

        int numV = inds[s].length;

        for(int v=0; v<numV; v++)

          {

          int index = indices[f][s][v];

          float x = vertices[index][0];

          float y = vertices[index][1];

          float z = vertices[index][2];

          float w = 1.0f;

          tmp = QuatHelper.rotateVectorByQuat(x,y,z,w,quat);

          verts[pointer][0] = tmp.get0() + avgX;

          verts[pointer][1] = tmp.get1() + avgY;

          verts[pointer][2] = tmp.get2() + avgZ;

          verts[pointer][3] = 1.0f;

          pointer++;

          }

        }

      infos[f] = new FaceInfo(verts,size);

      }

    return infos;

    }

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

// mesh polygon

  private FaceInfo[] computeInfos(float[][] vertices, int[][] indices, float[] position, Static4D quat, float size)

    {

    int len = position.length/3;

    float avgX = 0.0f;

    float avgY = 0.0f;

    float avgZ = 0.0f;

    for(int i=0; i<len; i++)

      {

      avgX += position[3*i  ];

      avgY += position[3*i+1];

      avgZ += position[3*i+2];

      }

    avgX /= len;

    avgY /= len;

    avgZ /= len;

    int numFaces = indices.length;

    FaceInfo[] infos = new FaceInfo[numFaces];

    Static4D tmp;

    for(int f=0; f<numFaces; f++)

      {

      int numVerts = indices[f].length;

      float[][] verts = new float[numVerts][4];

      for(int v=0; v<numVerts; v++)

        {

        int index = indices[f][v];

        float x = vertices[index][0];

        float y = vertices[index][1];

        float z = vertices[index][2];

        float w = 1.0f;

        tmp = QuatHelper.rotateVectorByQuat(x,y,z,w,quat);

        verts[v][0] = tmp.get0() + avgX;

        verts[v][1] = tmp.get1() + avgY;

        verts[v][2] = tmp.get2() + avgZ;

        verts[v][3] = 1.0f;

        }

      infos[f] = new FaceInfo(verts,size);

      }

    return infos;

    }

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

// software implementation of DistortedLibrary.mainVertexShader.degree() function.

// (limited to regions centered at [0,0,0])

  private float computeVertexDegree(float radius, float[] vert)

    {

    float x = vert[0];

    float y = vert[1];

    float z = vert[2];

    float len = (float)Math.sqrt(x*x + y*y + z*z);

    return len>radius ? 0.0f : 1.0f-len/radius;

    }

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

// software implementation of DistortedLibrary.VertexEffectSink

  private float[] adjustVert(float pillow, float radius, float[] vert)

    {

    float[] output = new float[3];

    float deg = computeVertexDegree(radius,vert);

    float t = 1.0f - deg*(1.0f-pillow)/pillow;

    output[0] = t*vert[0];

    output[1] = t*vert[1];

    output[2] = t*vert[2];

    return output;

    }

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

  private float[][] adjustVerticesForPillow(float pillow, float radius, float[][] verts)

    {

    int num = verts.length;

    float[][] output = new float[num][3];

    for(int i=0; i<num; i++) output[i] = adjustVert(pillow,radius,verts[i]);

    return output;

    }

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

  private void prepare()

    {

    int[] numLayers = mObject.getNumLayers();

    float[][] positions = mObject.getCubitPositions(numLayers);

    float size = mObject.getSize();

    mNumCubits = positions.length;

    mNumFaces  = new int[mNumCubits];

    mInfos = new FaceInfo[mNumCubits][];

    float pillow = mObject.getPillowCoeff();

    float radius = mObject.getCircumscribedRadius();

    for(int i=0; i<mNumCubits; i++)

      {

      int variant = mObject.getCubitVariant(i,numLayers);

      ObjectShape shape = mObject.getObjectShape(variant);

      Static4D quat = mObject.getCubitQuats(i,numLayers);

      float[][] vertices = shape.getVertices();

      if( pillow!=1.0f ) vertices = adjustVerticesForPillow(pillow,radius,vertices);

      mNumFaces[i] =shape.getNumFaces();

      int[][] indices = shape.getVertIndices();

      if( indices!=null )

        {

        mInfos[i] = computeInfos(vertices, indices, positions[i], quat, size);

        }

      else

        {

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

        mInfos[i] = computeInfos(vertices, ind, positions[i], quat, size);

        }

      }

    Static4D[] quats = mObject.getQuats();

    int numQuats = quats.length;

    mQuats = new float[numQuats][4];

    for(int i=0; i<numQuats; i++)

      {

      Static4D q = quats[i];

      mQuats[i][0] = q.get0();

      mQuats[i][1] = q.get1();

      mQuats[i][2] = q.get2();

      mQuats[i][3] = q.get3();

      }

    mPreparationDone = true;

    }

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

// points A, B, C are co-linear. Return true iff B is between A and C on this line.

// Compute D1 = A-B, D2=C-B. Then D1 and D2 are parallel vectors.

// They disagree in direction iff |D1+D2|<|D1-D2|

  private boolean isBetween(float ax, float ay, float az,

                            float bx, float by, float bz,

                            float cx, float cy, float cz)

    {

    float d1x = ax-bx;

    float d1y = ay-by;

    float d1z = az-bz;

    float d2x = cx-bx;

    float d2y = cy-by;

    float d2z = cz-bz;

    float sx = d1x+d2x;

    float sy = d1y+d2y;

    float sz = d1z+d2z;

    float dx = d1x-d2x;

    float dy = d1y-d2y;

    float dz = d1z-d2z;

    return sx*sx+sy*sy+sz*sz < dx*dx+dy*dy+dz*dz;

    }

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

// General algorithm: shoot a half-line from the 'point' and count how many

// sides of the polygon it intersects with. The point is inside iff this number

// is odd. Note that this works also in case of concave polygons.

//

// Arbitrarily take point P on the plane ( we have decided on P=(vert[0]+vert[1])/2 )

// as the other point defining the half-line.

// 'point' and 'P' define a line L1 in 3D. Then for each side the pair of its vertices

// defines a line L2. If L1||L2 return false. Otherwise, the lines are skew so it's

// possible to compute points C1 and C2 on lines L1 and L2 which are closest to the

// other line and check if

//

// a) C1 and P are on the same side of 'point'

//    (which happens iff 'point' is not in between of C1 and P)

// b) C2 is between the two vertices.

//

// Both a) and b) together mean that the half-line intersects with side defined by (p2,d2)

//

// C1 and C2 can be computed in the following way:

// Let n = d1 x d2 - then vector n is perpendicular to both d1 and d2 --> (c1-c2) is

// parallel to n.

// There exist real numbers A,B,C such that

// c1 = p1 + A*d1

// c2 = p2 + B*d2 and

// c2 = c1 + C*n so that

// p1 + A*d1 + C*n = p2 + B*d2  --> (p1-p2) + A*d1 = B*d2 - C*n (*)

// Let n2 = n x d2. Let's multiply both sides of (*) by n2. Then

// (p1-p2)*n2 + A*(d1*n2) = 0 (0 because d1*n2 = n*n2 = 0)

// and from that A = [(p1-p2)*n2]/[d1*n2]

// Similarly     B = [(p2-p1)*n1]/[d2*n1]  where n1 = n x d1.

  private boolean isInside(float[] point, float[][] vertices)

    {

    float e1x = (vertices[0][0]+vertices[1][0])/2;

    float e1y = (vertices[0][1]+vertices[1][1])/2;

    float e1z = (vertices[0][2]+vertices[1][2])/2;

    float d1x = e1x - point[0];

    float d1y = e1y - point[1];

    float d1z = e1z - point[2];

    float ax = vertices[0][0] - vertices[1][0];

    float ay = vertices[0][1] - vertices[1][1];

    float az = vertices[0][2] - vertices[1][2];

    float normX = d1y*az - d1z*ay;

    float normY = d1z*ax - d1x*az;

    float normZ = d1x*ay - d1y*ax;

    float n1x = d1y*normZ - d1z*normY;

    float n1y = d1z*normX - d1x*normZ;

    float n1z = d1x*normY - d1y*normX;

    float p1x = point[0];

    float p1y = point[1];

    float p1z = point[2];

    int len = vertices.length;

    int numCrossings = 0;

    for(int side=0; side<len; side++)

      {

      float p2x = vertices[side][0];

      float p2y = vertices[side][1];

      float p2z = vertices[side][2];

      int next = side==len-1 ? 0 : side+1;

      float e2x = vertices[next][0];

      float e2y = vertices[next][1];

      float e2z = vertices[next][2];

      float d2x = e2x-p2x;

      float d2y = e2y-p2y;

      float d2z = e2z-p2z;

      float nx = d2y*d1z - d2z*d1y;

      float ny = d2z*d1x - d2x*d1z;

      float nz = d2x*d1y - d2y*d1x;

      float n2x = d2y*nz - d2z*ny;

      float n2y = d2z*nx - d2x*nz;

      float n2z = d2x*ny - d2y*nx;

      float dpx = p1x-p2x;

      float dpy = p1y-p2y;

      float dpz = p1z-p2z;

      float A1 =-dpx*n2x-dpy*n2y-dpz*n2z;

      float B1 = d1x*n2x+d1y*n2y+d1z*n2z;

      float A2 = dpx*n1x+dpy*n1y+dpz*n1z;

      float B2 = d2x*n1x+d2y*n1y+d2z*n1z;

      if( B1==0 || B2==0 ) continue;

      float C1 = A1/B1;

      float C2 = A2/B2;

      float c1x = p1x + C1*d1x;

      float c1y = p1y + C1*d1y;

      float c1z = p1z + C1*d1z;

      float c2x = p2x + C2*d2x;

      float c2y = p2y + C2*d2y;

      float c2z = p2z + C2*d2z;

      if( !isBetween(c1x,c1y,c1z, p1x,p1y,p1z, e1x,e1y,e1z ) &&

           isBetween(p2x,p2y,p2z, c2x,c2y,c2z, e2x,e2y,e2z )  )

        {

        numCrossings++;

        }

      }

    return (numCrossings%2)==1;

    }

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

  private void rotateVertices(float[][] points, float[][] rotated, float[] quat)

    {

    int numPoints = points.length;

    for(int i=0; i<numPoints; i++)

      {

      QuatHelper.rotateVectorByQuat(rotated[i],points[i],quat);

      }

    }

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

// given precomputed mCamera and mPoint, respectively camera and touch point positions in ScreenSpace,

// a normalVec (nx,ny,nz) and distance (which together define a plane) compute point 'output[]' which:

// 1) lies on this plane

// 2) is co-linear with mCamera and mPoint

//

// output = camera + alpha*(point-camera), where alpha = [dist-normalVec*camera] / [normalVec*(point-camera)]

  void castTouchPointOntoFace(float nx, float ny, float nz, float distance, float[] output)

    {

    float d0 = mPoint[0]-mCamera[0];

    float d1 = mPoint[1]-mCamera[1];

    float d2 = mPoint[2]-mCamera[2];

    float denom = nx*d0 + ny*d1 + nz*d2;

    if( denom != 0.0f )

      {

      float axisCam = nx*mCamera[0] + ny*mCamera[1] + nz*mCamera[2];

      float alpha = (distance-axisCam)/denom;

      output[0] = mCamera[0] + d0*alpha;

      output[1] = mCamera[1] + d1*alpha;

      output[2] = mCamera[2] + d2*alpha;

      }

    }

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

  private boolean cubitFaceIsVisible(float nx, float ny, float nz, float distance)

    {

    return mCamera[0]*nx + mCamera[1]*ny + mCamera[2]*nz > distance;

    }

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

// FaceInfo defines a 3D plane (by means of a unit normal vector 'vector' and distance from the origin

// 'distance') and a list of points on the plane ('vertices').

//

// 0) rotate the face normal vector by quat

// 1) see if the face is visible. If not, return NOT_TOUCHED

// 2) else, cast the line passing through mPoint and mCamera onto this plane

// 3) if Z of this point is further from us than the already computed closestSoFar, return NOT_TOUCHED

// 4) else, rotate 'vertices' by quat and see if the casted point lies inside the polygon defined by them

// 5) if yes, return the distance from this point to the camera; otherwise, return NOT_TOUCHED

  private float cubitFaceTouched(FaceInfo info, float[] quat, float closestSoFar)

    {

    QuatHelper.rotateVectorByQuat(mTmp,info.normal,quat);

    float nx = mTmp[0];

    float ny = mTmp[1];

    float nz = mTmp[2];

    if( cubitFaceIsVisible(nx,ny,nz,info.distance) )

      {

      castTouchPointOntoFace(nx,ny,nz,info.distance,mTouch);

      float dx = mTouch[0]-mCamera[0];

      float dy = mTouch[1]-mCamera[1];

      float dz = mTouch[2]-mCamera[2];

      float dist = dx*dx + dy*dy + dz*dz;

      if( dist<closestSoFar )

        {

        rotateVertices(info.vertices,info.rotated,quat);

        if( isInside(mTouch,info.rotated) ) return dist;

        }

      }

    return NOT_TOUCHED;

    }

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

// This is in order to support non-rotatable rows.

// If mTouchedCubit ( as computed by objectTouched() ) turns out to be not rotatable with respect to

// the rotAxis, we need to figure out which of the neighbouring 'rotatable' cubits is the closest.

//

// Note that we cannot do it in objectTouched(), because then we do not yet know which axis we are

// going to be rotating along.

  private float distanceToRow(int rotIndex, int row)

    {

    float closestSoFar = NOT_TOUCHED;

    int numQuats = mQuats.length;

    int bmp = (1<<row);

    for(int cubit=0; cubit<mNumCubits; cubit++)

      {

      int rowBitmap = mObject.getCubitRotRow(cubit,rotIndex);

      if( (rowBitmap&bmp) != 0 )

        {

        int quatIndex = mObject.getCubitQuatIndex(cubit);

        if( quatIndex<numQuats )

          {

          float[] quat = mQuats[quatIndex];

          for(int face=0; face<mNumFaces[cubit]; face++)

            {

            float dist = cubitFaceTouched(mInfos[cubit][face],quat,closestSoFar);

            if( dist!=NOT_TOUCHED ) closestSoFar = dist;

            }

          }

        }

      }

    return closestSoFar;

    }

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

  private int notRotatable(int axis)

    {

    Static3D a = mRotAxis[axis];

    float x = mLastT[0]*a.get0() + mLastT[1]*a.get1() + mLastT[2]*a.get2();

    x *= mObject.getSize();

    float[] cuts = mCuts[axis];

    if( cuts==null ) return -1;

    int l = cuts.length;

    if( l>0 && x<=cuts[0]   ) return (l>=2 && x>=(3*cuts[  0]-cuts[  1])/2) ?   1 : -1;

    if( l>0 && x>=cuts[l-1] ) return (l>=2 && x<=(3*cuts[l-2]-cuts[l-1])/2) ? l-1 : -1;

    for(int i=1; i<l; i++)

      if( x<=cuts[i] )

        return x<((cuts[i-1]+cuts[i])/2) ? i-1 : i+1;

    return -1;

    }

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

  int computeRow(int cubit, int axis)

    {

    int row = mObject.getCubitRotRow(cubit,axis);

    for(int r=0; r<32; r++)

      {

      if( (row&1)==1 )

        return mRotatable[axis][r] ? r : notRotatable(axis);

      row>>=1;

      }

    return -1;

    }

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

// PUBLIC API

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

  public boolean objectTouched(Static4D rotatedTouchPoint, Static4D rotatedCamera)

    {

    if( !mPreparationDone ) prepare();

    mPoint[0]  = rotatedTouchPoint.get0()/mObjectRatio;

    mPoint[1]  = rotatedTouchPoint.get1()/mObjectRatio;

    mPoint[2]  = rotatedTouchPoint.get2()/mObjectRatio;

    mCamera[0] = rotatedCamera.get0()/mObjectRatio;

    mCamera[1] = rotatedCamera.get1()/mObjectRatio;