Project

General

Profile

« Previous | Next » 

Revision c87e42df

Added by Leszek Koltunski 9 months ago

Fix SkewbSolver.

View differences:

src/main/java/org/distorted/objectlib/objects/TwistySkewb.java
32 32

  
33 33
public class TwistySkewb extends ShapeHexahedron
34 34
{
35
  static final Static3D[] ROT_AXIS = new Static3D[]
35
  public static final Static3D[] ROT_AXIS = new Static3D[]
36 36
         {
37 37
           new Static3D( SQ3/3, SQ3/3, SQ3/3),
38 38
           new Static3D( SQ3/3, SQ3/3,-SQ3/3),
src/main/java/org/distorted/objectlib/tablebases/TBSkewb.java
9 9

  
10 10
package org.distorted.objectlib.tablebases;
11 11

  
12
import static org.distorted.objectlib.main.TwistyObject.SQ3;
13

  
12
import org.distorted.library.helpers.QuatHelper;
14 13
import org.distorted.library.type.Static3D;
14
import org.distorted.library.type.Static4D;
15 15
import org.distorted.objectlib.R;
16 16
import org.distorted.objectlib.helpers.OperatingSystemInterface;
17
import org.distorted.objectlib.helpers.QuatGroupGenerator;
18
import org.distorted.objectlib.objects.TwistySkewb;
17 19

  
18 20
///////////////////////////////////////////////////////////////////////////////////////////////////
19 21

  
......
24 26

  
25 27
  private static final int[][] freeIndex = { {1,3,2},{0,2,3},{3,1,0},{2,0,1} };
26 28

  
29
  // [1][] are the 3 quats the 1st 'fixed' corner will have when twisted with respectively twist 0,1,2.
30
  private static final int[][] fixedQuats = { {0,1,2},{0,7,8},{0,6,5},{0,4,3} };
31

  
32
  private static int[][] tetradPerm, divideTable, multiplyTable, locationTable;
33

  
34
  // centerQuats[0][1] are the two quats the 0th center might have when rotated to the position of
35
  // the 1st center.
36
  // Warning! Order of the centers follows the order from TwistySkewb, i.e. +z,-z,+y,-y,+x,-x
27 37
  private static final int[][][] centerQuats =
28 38
    {
29 39
        { {0,10},{9,11},{1,7},{4,6},{2,5},{3,8} },
......
34 44
        { {4,7},{1,6},{5,8},{2,3},{10,11},{0,9} }
35 45
    };
36 46

  
37
  // [1][] are the 3 quats the 1st 'fixed' corner will have when 'fakeTwisted' (which in case of
38
  // the fixed corners is the same as the final twist) with respectively twist 0,1,2.
39

  
40
  private static final int[][] fixedQuats = { {0,1,2},{0,7,8},{0,6,5},{0,4,3} };
41

  
42
  // [1][2][] are the 3 quats the 1st free corner, when permuted to the location of the 2nd corner,
43
  // will have when it is 'fakeTwisted' with fakeTwist 0,1,2.
44
  // fakeTwist is an intermediate twist which needs yet to be translated to the final twist of the
45
  // corners (which needs to sum up to something divisible by 3).
46

  
47
  private static final int[][][] freeQuats=
48
    {
49
        { {0,3,4},{9,8,1},{6,11,2},{7,10,5} },
50
        { {9,2,7},{0,5,6},{1,10,3},{4,11,8} },
51
        { {5,1,11},{2,4,10},{0,8,7},{9,3,6} },
52
        { {8,6,10},{3,7,11},{9,5,4},{0,2,1} }
53
    };
47
  private static Static4D[] mQuats;
48
  private static final Static3D[] ROT_AXIS = TwistySkewb.ROT_AXIS;
49
  private static final int[][] BASIC_ANGLES = { {3,3},{3,3},{3,3},{3,3} };
54 50

  
55 51
///////////////////////////////////////////////////////////////////////////////////////////////////
56 52

  
......
70 66

  
71 67
  int[][] getBasicAngles()
72 68
    {
73
    int[] tmp = {3,3};
74
    return new int[][] { tmp,tmp,tmp,tmp };
69
    return BASIC_ANGLES;
75 70
    }
76 71

  
77 72
///////////////////////////////////////////////////////////////////////////////////////////////////
78 73

  
79 74
  Static3D[] getRotationAxis()
80 75
    {
81
    return new Static3D[]
82
         {
83
           new Static3D( SQ3/3, SQ3/3, SQ3/3),
84
           new Static3D( SQ3/3, SQ3/3,-SQ3/3),
85
           new Static3D( SQ3/3,-SQ3/3, SQ3/3),
86
           new Static3D( SQ3/3,-SQ3/3,-SQ3/3)
87
         };
76
    return ROT_AXIS;
88 77
    }
89 78

  
90 79
///////////////////////////////////////////////////////////////////////////////////////////////////
......
174 163

  
175 164
///////////////////////////////////////////////////////////////////////////////////////////////////
176 165

  
177
  public static int computeLocation(int index, int quat)
166
  private static int figureOutLocation(float[] loc, float[][] vectors)
178 167
    {
168
    float minDiff = Float.MAX_VALUE;
169
    int index = -1;
170

  
179 171
    for(int i=0; i<4; i++)
180 172
      {
181
      int[] q = freeQuats[index][i];
182
      if( quat==q[0] || quat==q[1] || quat==q[2] ) return i;
173
      float[] v = vectors[i];
174
      float dx = v[0]-loc[0];
175
      float dy = v[1]-loc[1];
176
      float dz = v[2]-loc[2];
177
      float diff = dx*dx + dy*dy + dz*dz;
178

  
179
      if( diff<minDiff )
180
        {
181
        minDiff = diff;
182
        index = i;
183
        }
183 184
      }
184 185

  
185
    android.util.Log.e("D", "error in computeLocation, quat="+quat);
186
    return -1;
186
    return index;
187
    }
188

  
189
///////////////////////////////////////////////////////////////////////////////////////////////////
190

  
191
  private static void generateLocation()
192
    {
193
    locationTable = new int[4][12];
194

  
195
    if( mQuats==null )
196
      mQuats = QuatGroupGenerator.computeGroup(ROT_AXIS,BASIC_ANGLES);
197

  
198
    float[][] vectors = new float[][]
199
      {
200
        { 1, 1,-1, 0},
201
        { 1,-1, 1, 0},
202
        {-1, 1, 1, 0},
203
        {-1,-1,-1, 0}
204
      };
205

  
206
    float[] output = new float[4];
207

  
208
    for(int i=0; i<4; i++)
209
      {
210
      float[] v = vectors[i];
211

  
212
      for(int q=0; q<12; q++)
213
        {
214
        Static4D quat = mQuats[q];
215
        QuatHelper.rotateVectorByQuat(output,v[0],v[1],v[2],v[3],quat);
216
        int loc = figureOutLocation(output,vectors);
217
        locationTable[i][q] = loc;
218
        }
219
      }
220
    }
221

  
222
///////////////////////////////////////////////////////////////////////////////////////////////////
223

  
224
  public static int computeLocation(int index, int quat)
225
    {
226
    if( locationTable==null ) generateLocation();
227
    return locationTable[index][quat];
187 228
    }
188 229

  
189 230
///////////////////////////////////////////////////////////////////////////////////////////////////
190 231

  
191
  private static int retFixed(int index, int quat)
232
  private static int fixedQuatToTwist(int index, int quat)
192 233
    {
193 234
    int[] qs = fixedQuats[index];
194 235

  
......
196 237
    if( quat==qs[1]) return 1;
197 238
    if( quat==qs[2]) return 2;
198 239

  
199
    android.util.Log.e("D", "error in retFixed, index="+index+" quat="+quat);
240
    android.util.Log.e("D", "error in fixedQuatToTwist, index="+index+" quat="+quat);
241
    return -1;
242
    }
243

  
244
///////////////////////////////////////////////////////////////////////////////////////////////////
245

  
246
  private static int fixedTwistToQuat(int index, int twist)
247
    {
248
    return fixedQuats[index][twist];
249
    }
250

  
251
///////////////////////////////////////////////////////////////////////////////////////////////////
252

  
253
  private static int figureOutTetrad(int q0, int q1, int q2, int q3)
254
    {
255
    int[] quats = fixedQuats[3];
256

  
257
    int s00 = divideFromRight(q0,quats[0]);
258
    int s01 = divideFromRight(q0,quats[1]);
259
    int s02 = divideFromRight(q0,quats[2]);
260

  
261
    quats = fixedQuats[1];
262

  
263
    int s10 = divideFromRight(q2,quats[0]);
264
    int s11 = divideFromRight(q2,quats[1]);
265
    int s12 = divideFromRight(q2,quats[2]);
266

  
267
    quats = fixedQuats[2];
268

  
269
    int s20 = divideFromRight(q1,quats[0]);
270

  
271
    if( s20==s00 || s20==s01 || s20==s02 )
272
      return ( s20==s10 || s20==s11 || s20==s12 ) ? s20 : -1;
273

  
274
    int s21 = divideFromRight(q1,quats[1]);
275

  
276
    if( s21==s00 || s21==s01 || s21==s02 )
277
      return ( s21==s10 || s21==s11 || s21==s12 ) ? s21 : -1;
278

  
279
    int s22 = divideFromRight(q1,quats[2]);
280

  
281
    if( s22==s00 || s22==s01 || s22==s02 )
282
      return ( s22==s10 || s22==s11 || s22==s12 ) ? s22 : -1;
283

  
200 284
    return -1;
201 285
    }
202 286

  
203 287
///////////////////////////////////////////////////////////////////////////////////////////////////
204 288

  
205
  private static int retFree(int index, int quat)
289
  private static void generateDivideTable()
290
    {
291
    divideTable = new int[12][12];
292

  
293
    for(int i=0; i<12; i++)
294
      for(int j=0; j<12; j++)
295
        {
296
        int res = multiplyQuat(i,j);
297
        divideTable[res][j] = i;
298
        }
299
    }
300

  
301
///////////////////////////////////////////////////////////////////////////////////////////////////
302
// double cover!
303

  
304
  private static int findQuat(Static4D quat)
305
    {
306
    float minDiff = Float.MAX_VALUE;
307
    int bestindex = -1;
308
    float dx,dy,dz,dw,diff;
309

  
310
    float x= quat.get0();
311
    float y= quat.get1();
312
    float z= quat.get2();
313
    float w= quat.get3();
314

  
315
    for(int i=0; i<12; i++)
316
      {
317
      Static4D q = mQuats[i];
318
      dx = x-q.get0();
319
      dy = y-q.get1();
320
      dz = z-q.get2();
321
      dw = w-q.get3();
322

  
323
      diff = dx*dx + dy*dy + dz*dz + dw*dw;
324

  
325
      if( diff<minDiff )
326
        {
327
        minDiff = diff;
328
        bestindex = i;
329
        }
330

  
331
      dx = x+q.get0();
332
      dy = y+q.get1();
333
      dz = z+q.get2();
334
      dw = w+q.get3();
335

  
336
      diff = dx*dx + dy*dy + dz*dz + dw*dw;
337

  
338
      if( diff<minDiff )
339
        {
340
        minDiff = diff;
341
        bestindex = i;
342
        }
343
      }
344

  
345
    return bestindex;
346
    }
347

  
348
///////////////////////////////////////////////////////////////////////////////////////////////////
349

  
350
  private static void generateMultiplyTable()
351
    {
352
    multiplyTable = new int[12][12];
353

  
354
    if( mQuats==null )
355
      mQuats = QuatGroupGenerator.computeGroup(ROT_AXIS,BASIC_ANGLES);
356

  
357
    for(int i=0; i<12; i++)
358
      {
359
      Static4D q0 = mQuats[i];
360

  
361
      for(int j=0; j<12; j++)
362
        {
363
        Static4D q1 = mQuats[j];
364
        Static4D res= QuatHelper.quatMultiply(q0,q1);
365
        int index   = findQuat(res);
366
        multiplyTable[i][j] = index;
367
        }
368
      }
369
    }
370

  
371
///////////////////////////////////////////////////////////////////////////////////////////////////
372

  
373
  private static void generateTetradPerm()
206 374
    {
207
    int[][] qs = freeQuats[index];
375
    tetradPerm = new int[4][4];
208 376

  
209 377
    for(int i=0; i<4; i++)
378
      for(int j=0; j<4; j++) tetradPerm[i][j] = -1;
379

  
380
    for(int q=0; q<12; q++)
210 381
      {
211
      if( quat==qs[i][0]) return 0;
212
      if( quat==qs[i][1]) return 1;
213
      if( quat==qs[i][2]) return 2;
382
      int loc0 = computeLocation(0,q);
383
      int loc1 = computeLocation(1,q);
384
      tetradPerm[loc0][loc1] = q;
214 385
      }
386
    }
215 387

  
216
    android.util.Log.e("D", "error in retFree, index="+index+" quat="+quat);
217
    return -1;
388
///////////////////////////////////////////////////////////////////////////////////////////////////
389

  
390
  public static int figureOutTetrad(int[] perm)
391
    {
392
    if( tetradPerm==null ) generateTetradPerm();
393
    return tetradPerm[perm[0]][perm[1]];
394
    }
395

  
396
///////////////////////////////////////////////////////////////////////////////////////////////////
397
// return (r^-1) * q
398

  
399
  private static int divideFromLeft(int q, int r)
400
    {
401
    if( divideTable==null ) generateDivideTable();
402
    return multiplyTable[divideTable[0][r]][q];
403
    }
404

  
405
///////////////////////////////////////////////////////////////////////////////////////////////////
406
// return q * (r^-1)
407

  
408
  private static int divideFromRight(int q, int r)
409
    {
410
    if( divideTable==null ) generateDivideTable();
411
    return divideTable[q][r];
412
    }
413

  
414
///////////////////////////////////////////////////////////////////////////////////////////////////
415

  
416
  private static int multiplyQuat(int q, int r)
417
    {
418
    if( multiplyTable==null ) generateMultiplyTable();
419
    return multiplyTable[q][r];
218 420
    }
219 421

  
220 422
///////////////////////////////////////////////////////////////////////////////////////////////////
......
225 427
// tetrahedron. And so, for example the twist of free corner 1 (whose 0th face is orange) is equal
226 428
// to 0 if free corner 7 is on the same face like 0th face of corner 1 (which is the case in init
227 429
// position); then once free corners 2,4,7 permute CW, twist of corner 1 increases by 1 mod 3.
430
//
431
// Way to figure out the 'free' twists: notice their final quat must be a product of initial
432
// 'in place' quat and a common quat which rotates the tetrad of all 4 'free' corners.
433
// Figure out the tetrad quat and divide free quats by it, then do the same like with fixed corners.
228 434

  
229 435
  public static void computeCornerTwists(int[] twists, int[] quats)
230 436
    {
231
    for(int i=0; i<4; i++) twists[FIXED[i]] = retFixed(i,quats[FIXED[i]]);
232
    for(int i=0; i<4; i++) twists[FREE[i]]  = retFree(i,quats[FREE[i]]);
437
    for(int i=0; i<4; i++) twists[FIXED[i]] = fixedQuatToTwist(i,quats[FIXED[i]]);
438

  
439
    int free0 = quats[FREE[0]];
440
    int free1 = quats[FREE[1]];
441
    int free2 = quats[FREE[2]];
442
    int free3 = quats[FREE[3]];
443

  
444
    int tetradQuat = figureOutTetrad(free0,free1,free2,free3);
445

  
446
    if( tetradQuat>=0 )
447
      {
448
      int quat0 = divideFromLeft(free0, tetradQuat);
449
      int quat1 = divideFromLeft(free1, tetradQuat);
450
      int quat2 = divideFromLeft(free2, tetradQuat);
451
      int quat3 = divideFromLeft(free3, tetradQuat);
452

  
453
      twists[FREE[0]] = fixedQuatToTwist(3, quat0);
454
      twists[FREE[1]] = fixedQuatToTwist(2, quat1);
455
      twists[FREE[2]] = fixedQuatToTwist(1, quat2);
456
      twists[FREE[3]] = fixedQuatToTwist(0, quat3);
457
      }
458
    else
459
      {
460
      android.util.Log.e("D", "ERROR in computeCornerTwists: "+free0+" "+free1+" "+free2+" "+free3);
461
      }
233 462
    }
234 463

  
235 464
///////////////////////////////////////////////////////////////////////////////////////////////////
......
239 468
    for(int i=0; i<4; i++)
240 469
      {
241 470
      int fixed = FIXED[i];
242
      int free  = FREE[i];
243 471
      int twFi  = twist[fixed];
244
      int twFr  = twist[free];
245
      int pe    = perm[i];
246

  
247 472
      quats[fixed] = fixedQuats[i][twFi];
248
      quats[free ] = freeQuats[i][pe][twFr];
249 473
      }
474

  
475
    int q0 = fixedTwistToQuat(3,twist[FREE[0]]);
476
    int q1 = fixedTwistToQuat(2,twist[FREE[1]]);
477
    int q2 = fixedTwistToQuat(1,twist[FREE[2]]);
478
    int q3 = fixedTwistToQuat(0,twist[FREE[3]]);
479

  
480
    int tetradQuat = figureOutTetrad(perm);
481

  
482
    quats[FREE[0]] = multiplyQuat(tetradQuat,q0);
483
    quats[FREE[1]] = multiplyQuat(tetradQuat,q1);
484
    quats[FREE[2]] = multiplyQuat(tetradQuat,q2);
485
    quats[FREE[3]] = multiplyQuat(tetradQuat,q3);
250 486
    }
251 487

  
252 488
///////////////////////////////////////////////////////////////////////////////////////////////////
......
301 537

  
302 538
///////////////////////////////////////////////////////////////////////////////////////////////////
303 539

  
304
  public int[] getQuats(int index)
540
  public static int permFree1(int permFree0, int sumFixedTwists)
541
    {
542
    return freeIndex[permFree0][sumFixedTwists%3];
543
    }
544

  
545
///////////////////////////////////////////////////////////////////////////////////////////////////
546

  
547
  int[] getQuats(int index)
305 548
    {
306 549
    int[] permFree = new int[4];
307 550
    int center_perm_num = (index%360);
......
316 559
    TablebaseHelpers.getEvenPermutationFromNum(center_perm, center_perm_num);
317 560
    fillCenterQuats(quats,center_perm);
318 561

  
562
    int total = 0;
563

  
319 564
    for(int i=0; i<7; i++)
320 565
      {
321 566
      twist[i] = (totalTwist%3);
322 567
      totalTwist /= 3;
568
      total += twist[i];
323 569
      }
324 570

  
325
    int total = twist[FREE[0]]+twist[FREE[1]]+twist[FREE[2]];
326
    twist[7] = ((6-total)%3);
571
    twist[7] = ((24-total)%3);
327 572
    int sumFixedTwists = twist[FIXED[0]]+twist[FIXED[1]]+twist[FIXED[2]]+twist[FIXED[3]];
328
    permFree[1] = freeIndex[permFree[0]][sumFixedTwists%3];
573

  
574
    permFree[1] = permFree1(permFree[0],sumFixedTwists);
329 575
    fillUpToEvenPerm(permFree);
330 576
    fillInQuats(quats,permFree,twist);
331 577

  
......
334 580

  
335 581
///////////////////////////////////////////////////////////////////////////////////////////////////
336 582

  
337
  public int getIndex(int[] quats)
583
  int getIndex(int[] quats)
338 584
    {
339 585
    int[] center_perm = computeCenterPerm(quats);
340 586
    int center_perm_num = TablebaseHelpers.computeEvenPermutationNum(center_perm);

Also available in: Unified diff