newfct.cpp

普林斯顿开发的快速球面调和变换算法

// newFCT.cpp: implementation of the newFCT class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "newFCT.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

static const int OUR4[4] = {0, 3, 2, 1};

static const int OUR8[8] = {0, 7, 4, 3, 2, 5, 6, 1};

static const int OUR16[16] =
{0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1};

static const int OUR32[32] = 
{0, 31, 16, 15, 8, 23, 24, 7, 4, 27, 20, 11, 12, 19, 28, 3, 2, 29, 18, 13, 
  10, 21, 26, 5, 6, 25, 22, 9, 14, 17, 30, 1};

static const int OUR64[64] = 
{0, 63, 32, 31, 16, 47, 48, 15, 8, 55, 40, 23, 24, 39, 56, 7, 4, 59, 36, 27, 
  20, 43, 52, 11, 12, 51, 44, 19, 28, 35, 60, 3, 2, 61, 34, 29, 18, 45, 50, 
  13, 10, 53, 42, 21, 26, 37, 58, 5, 6, 57, 38, 25, 22, 41, 54, 9, 14, 49, 
  46, 17, 30, 33, 62, 1};

static const int OUR128[128] = 
{0, 127, 64, 63, 32, 95, 96, 31, 16, 111, 80, 47, 48, 79, 112, 15, 8, 119, 
  72, 55, 40, 87, 104, 23, 24, 103, 88, 39, 56, 71, 120, 7, 4, 123, 68, 59, 
  36, 91, 100, 27, 20, 107, 84, 43, 52, 75, 116, 11, 12, 115, 76, 51, 44, 83, 
  108, 19, 28, 99, 92, 35, 60, 67, 124, 3, 2, 125, 66, 61, 34, 93, 98, 29, 
  18, 109, 82, 45, 50, 77, 114, 13, 10, 117, 74, 53, 42, 85, 106, 21, 26, 
  101, 90, 37, 58, 69, 122, 5, 6, 121, 70, 57, 38, 89, 102, 25, 22, 105, 86, 
  41, 54, 73, 118, 9, 14, 113, 78, 49, 46, 81, 110, 17, 30, 97, 94, 33, 62, 
  65, 126, 1};

static const int OUR256[256] = 
{0, 255, 128, 127, 64, 191, 192, 63, 32, 223, 160, 95, 96, 159, 224, 31, 16, 
  239, 144, 111, 80, 175, 208, 47, 48, 207, 176, 79, 112, 143, 240, 15, 8, 
  247, 136, 119, 72, 183, 200, 55, 40, 215, 168, 87, 104, 151, 232, 23, 24, 
  231, 152, 103, 88, 167, 216, 39, 56, 199, 184, 71, 120, 135, 248, 7, 4, 
  251, 132, 123, 68, 187, 196, 59, 36, 219, 164, 91, 100, 155, 228, 27, 20, 
  235, 148, 107, 84, 171, 212, 43, 52, 203, 180, 75, 116, 139, 244, 11, 12, 
  243, 140, 115, 76, 179, 204, 51, 44, 211, 172, 83, 108, 147, 236, 19, 28, 
  227, 156, 99, 92, 163, 220, 35, 60, 195, 188, 67, 124, 131, 252, 3, 2, 253, 
  130, 125, 66, 189, 194, 61, 34, 221, 162, 93, 98, 157, 226, 29, 18, 237, 
  146, 109, 82, 173, 210, 45, 50, 205, 178, 77, 114, 141, 242, 13, 10, 245, 
  138, 117, 74, 181, 202, 53, 42, 213, 170, 85, 106, 149, 234, 21, 26, 229, 
  154, 101, 90, 165, 218, 37, 58, 197, 186, 69, 122, 133, 250, 5, 6, 249, 
  134, 121, 70, 185, 198, 57, 38, 217, 166, 89, 102, 153, 230, 25, 22, 233, 
  150, 105, 86, 169, 214, 41, 54, 201, 182, 73, 118, 137, 246, 9, 14, 241, 
  142, 113, 78, 177, 206, 49, 46, 209, 174, 81, 110, 145, 238, 17, 30, 225, 
  158, 97, 94, 161, 222, 33, 62, 193, 190, 65, 126, 129, 254, 1};

static const int OUR512[512] = 
{0, 511, 256, 255, 128, 383, 384, 127, 64, 447, 320, 191, 192, 319, 448, 63, 
  32, 479, 288, 223, 160, 351, 416, 95, 96, 415, 352, 159, 224, 287, 480, 31, 
  16, 495, 272, 239, 144, 367, 400, 111, 80, 431, 336, 175, 208, 303, 464, 
  47, 48, 463, 304, 207, 176, 335, 432, 79, 112, 399, 368, 143, 240, 271, 
  496, 15, 8, 503, 264, 247, 136, 375, 392, 119, 72, 439, 328, 183, 200, 311, 
  456, 55, 40, 471, 296, 215, 168, 343, 424, 87, 104, 407, 360, 151, 232, 
  279, 488, 23, 24, 487, 280, 231, 152, 359, 408, 103, 88, 423, 344, 167, 
  216, 295, 472, 39, 56, 455, 312, 199, 184, 327, 440, 71, 120, 391, 376, 
  135, 248, 263, 504, 7, 4, 507, 260, 251, 132, 379, 388, 123, 68, 443, 324, 
  187, 196, 315, 452, 59, 36, 475, 292, 219, 164, 347, 420, 91, 100, 411, 
  356, 155, 228, 283, 484, 27, 20, 491, 276, 235, 148, 363, 404, 107, 84, 
  427, 340, 171, 212, 299, 468, 43, 52, 459, 308, 203, 180, 331, 436, 75, 
  116, 395, 372, 139, 244, 267, 500, 11, 12, 499, 268, 243, 140, 371, 396, 
  115, 76, 435, 332, 179, 204, 307, 460, 51, 44, 467, 300, 211, 172, 339, 
  428, 83, 108, 403, 364, 147, 236, 275, 492, 19, 28, 483, 284, 227, 156, 
  355, 412, 99, 92, 419, 348, 163, 220, 291, 476, 35, 60, 451, 316, 195, 188, 
  323, 444, 67, 124, 387, 380, 131, 252, 259, 508, 3, 2, 509, 258, 253, 130, 
  381, 386, 125, 66, 445, 322, 189, 194, 317, 450, 61, 34, 477, 290, 221, 
  162, 349, 418, 93, 98, 413, 354, 157, 226, 285, 482, 29, 18, 493, 274, 237, 
  146, 365, 402, 109, 82, 429, 338, 173, 210, 301, 466, 45, 50, 461, 306, 
  205, 178, 333, 434, 77, 114, 397, 370, 141, 242, 269, 498, 13, 10, 501, 
  266, 245, 138, 373, 394, 117, 74, 437, 330, 181, 202, 309, 458, 53, 42, 
  469, 298, 213, 170, 341, 426, 85, 106, 405, 362, 149, 234, 277, 490, 21, 
  26, 485, 282, 229, 154, 357, 410, 101, 90, 421, 346, 165, 218, 293, 474, 
  37, 58, 453, 314, 197, 186, 325, 442, 69, 122, 389, 378, 133, 250, 261, 
  506, 5, 6, 505, 262, 249, 134, 377, 390, 121, 70, 441, 326, 185, 198, 313, 
  454, 57, 38, 473, 294, 217, 166, 345, 422, 89, 102, 409, 358, 153, 230, 
  281, 486, 25, 22, 489, 278, 233, 150, 361, 406, 105, 86, 425, 342, 169, 
  214, 297, 470, 41, 54, 457, 310, 201, 182, 329, 438, 73, 118, 393, 374, 
  137, 246, 265, 502, 9, 14, 497, 270, 241, 142, 369, 398, 113, 78, 433, 334, 
  177, 206, 305, 462, 49, 46, 465, 302, 209, 174, 337, 430, 81, 110, 401, 
  366, 145, 238, 273, 494, 17, 30, 481, 286, 225, 158, 353, 414, 97, 94, 417, 
  350, 161, 222, 289, 478, 33, 62, 449, 318, 193, 190, 321, 446, 65, 126, 
  385, 382, 129, 254, 257, 510, 1};



static const int OUR1024[1024] = 
{0, 1023, 512, 511, 256, 767, 768, 255, 128, 895, 640, 383, 384, 639, 896, 
  127, 64, 959, 576, 447, 320, 703, 832, 191, 192, 831, 704, 319, 448, 575, 
  960, 63, 32, 991, 544, 479, 288, 735, 800, 223, 160, 863, 672, 351, 416, 
  607, 928, 95, 96, 927, 608, 415, 352, 671, 864, 159, 224, 799, 736, 287, 
  480, 543, 992, 31, 16, 1007, 528, 495, 272, 751, 784, 239, 144, 879, 656, 
  367, 400, 623, 912, 111, 80, 943, 592, 431, 336, 687, 848, 175, 208, 815, 
  720, 303, 464, 559, 976, 47, 48, 975, 560, 463, 304, 719, 816, 207, 176, 
  847, 688, 335, 432, 591, 944, 79, 112, 911, 624, 399, 368, 655, 880, 143, 
  240, 783, 752, 271, 496, 527, 1008, 15, 8, 1015, 520, 503, 264, 759, 776, 
  247, 136, 887, 648, 375, 392, 631, 904, 119, 72, 951, 584, 439, 328, 695, 
  840, 183, 200, 823, 712, 311, 456, 567, 968, 55, 40, 983, 552, 471, 296, 
  727, 808, 215, 168, 855, 680, 343, 424, 599, 936, 87, 104, 919, 616, 407, 
  360, 663, 872, 151, 232, 791, 744, 279, 488, 535, 1000, 23, 24, 999, 536, 
  487, 280, 743, 792, 231, 152, 871, 664, 359, 408, 615, 920, 103, 88, 935, 
  600, 423, 344, 679, 856, 167, 216, 807, 728, 295, 472, 551, 984, 39, 56, 
  967, 568, 455, 312, 711, 824, 199, 184, 839, 696, 327, 440, 583, 952, 71, 
  120, 903, 632, 391, 376, 647, 888, 135, 248, 775, 760, 263, 504, 519, 1016, 
  7, 4, 1019, 516, 507, 260, 763, 772, 251, 132, 891, 644, 379, 388, 635, 
  900, 123, 68, 955, 580, 443, 324, 699, 836, 187, 196, 827, 708, 315, 452, 
  571, 964, 59, 36, 987, 548, 475, 292, 731, 804, 219, 164, 859, 676, 347, 
  420, 603, 932, 91, 100, 923, 612, 411, 356, 667, 868, 155, 228, 795, 740, 
  283, 484, 539, 996, 27, 20, 1003, 532, 491, 276, 747, 788, 235, 148, 875, 
  660, 363, 404, 619, 916, 107, 84, 939, 596, 427, 340, 683, 852, 171, 212, 
  811, 724, 299, 468, 555, 980, 43, 52, 971, 564, 459, 308, 715, 820, 203, 
  180, 843, 692, 331, 436, 587, 948, 75, 116, 907, 628, 395, 372, 651, 884, 
  139, 244, 779, 756, 267, 500, 523, 1012, 11, 12, 1011, 524, 499, 268, 755, 
  780, 243, 140, 883, 652, 371, 396, 627, 908, 115, 76, 947, 588, 435, 332, 
  691, 844, 179, 204, 819, 716, 307, 460, 563, 972, 51, 44, 979, 556, 467, 
  300, 723, 812, 211, 172, 851, 684, 339, 428, 595, 940, 83, 108, 915, 620, 
  403, 364, 659, 876, 147, 236, 787, 748, 275, 492, 531, 1004, 19, 28, 995, 
  540, 483, 284, 739, 796, 227, 156, 867, 668, 355, 412, 611, 924, 99, 92, 
  931, 604, 419, 348, 675, 860, 163, 220, 803, 732, 291, 476, 547, 988, 35, 
  60, 963, 572, 451, 316, 707, 828, 195, 188, 835, 700, 323, 444, 579, 956, 
  67, 124, 899, 636, 387, 380, 643, 892, 131, 252, 771, 764, 259, 508, 515, 
  1020, 3, 2, 1021, 514, 509, 258, 765, 770, 253, 130, 893, 642, 381, 386, 
  637, 898, 125, 66, 957, 578, 445, 322, 701, 834, 189, 194, 829, 706, 317, 
  450, 573, 962, 61, 34, 989, 546, 477, 290, 733, 802, 221, 162, 861, 674, 
  349, 418, 605, 930, 93, 98, 925, 610, 413, 354, 669, 866, 157, 226, 797, 
  738, 285, 482, 541, 994, 29, 18, 1005, 530, 493, 274, 749, 786, 237, 146, 
  877, 658, 365, 402, 621, 914, 109, 82, 941, 594, 429, 338, 685, 850, 173, 
  210, 813, 722, 301, 466, 557, 978, 45, 50, 973, 562, 461, 306, 717, 818, 
  205, 178, 845, 690, 333, 434, 589, 946, 77, 114, 909, 626, 397, 370, 653, 
  882, 141, 242, 781, 754, 269, 498, 525, 1010, 13, 10, 1013, 522, 501, 266, 
  757, 778, 245, 138, 885, 650, 373, 394, 629, 906, 117, 74, 949, 586, 437, 
  330, 693, 842, 181, 202, 821, 714, 309, 458, 565, 970, 53, 42, 981, 554, 
  469, 298, 725, 810, 213, 170, 853, 682, 341, 426, 597, 938, 85, 106, 917, 
  618, 405, 362, 661, 874, 149, 234, 789, 746, 277, 490, 533, 1002, 21, 26, 
  997, 538, 485, 282, 741, 794, 229, 154, 869, 666, 357, 410, 613, 922, 101, 
  90, 933, 602, 421, 346, 677, 858, 165, 218, 805, 730, 293, 474, 549, 986, 
  37, 58, 965, 570, 453, 314, 709, 826, 197, 186, 837, 698, 325, 442, 581, 
  954, 69, 122, 901, 634, 389, 378, 645, 890, 133, 250, 773, 762, 261, 506, 
  517, 1018, 5, 6, 1017, 518, 505, 262, 761, 774, 249, 134, 889, 646, 377, 
  390, 633, 902, 121, 70, 953, 582, 441, 326, 697, 838, 185, 198, 825, 710, 
  313, 454, 569, 966, 57, 38, 985, 550, 473, 294, 729, 806, 217, 166, 857, 
  678, 345, 422, 601, 934, 89, 102, 921, 614, 409, 358, 665, 870, 153, 230, 
  793, 742, 281, 486, 537, 998, 25, 22, 1001, 534, 489, 278, 745, 790, 233, 
  150, 873, 662, 361, 406, 617, 918, 105, 86, 937, 598, 425, 342, 681, 854, 
  169, 214, 809, 726, 297, 470, 553, 982, 41, 54, 969, 566, 457, 310, 713, 
  822, 201, 182, 841, 694, 329, 438, 585, 950, 73, 118, 905, 630, 393, 374, 
  649, 886, 137, 246, 777, 758, 265, 502, 521, 1014, 9, 14, 1009, 526, 497, 
  270, 753, 782, 241, 142, 881, 654, 369, 398, 625, 910, 113, 78, 945, 590, 
  433, 334, 689, 846, 177, 206, 817, 718, 305, 462, 561, 974, 49, 46, 977, 
  558, 465, 302, 721, 814, 209, 174, 849, 686, 337, 430, 593, 942, 81, 110, 
  913, 622, 401, 366, 657, 878, 145, 238, 785, 750, 273, 494, 529, 1006, 17, 
  30, 993, 542, 481, 286, 737, 798, 225, 158, 865, 670, 353, 414, 609, 926, 
  97, 94, 929, 606, 417, 350, 673, 862, 161, 222, 801, 734, 289, 478, 545, 
  990, 33, 62, 961, 574, 449, 318, 705, 830, 193, 190, 833, 702, 321, 446, 
  577, 958, 65, 126, 897, 638, 385, 382, 641, 894, 129, 254, 769, 766, 257, 
  510, 513, 1022, 1};


static const int OUR2048[2048] = 
{0, 2047, 1024, 1023, 512, 1535, 1536, 511, 256, 1791, 1280, 767, 768, 1279, 
  1792, 255, 128, 1919, 1152, 895, 640, 1407, 1664, 383, 384, 1663, 1408, 
  639, 896, 1151, 1920, 127, 64, 1983, 1088, 959, 576, 1471, 1600, 447, 320, 
  1727, 1344, 703, 832, 1215, 1856, 191, 192, 1855, 1216, 831, 704, 1343, 
  1728, 319, 448, 1599, 1472, 575, 960, 1087, 1984, 63, 32, 2015, 1056, 991, 
  544, 1503, 1568, 479, 288, 1759, 1312, 735, 800, 1247, 1824, 223, 160, 
  1887, 1184, 863, 672, 1375, 1696, 351, 416, 1631, 1440, 607, 928, 1119, 
  1952, 95, 96, 1951, 1120, 927, 608, 1439, 1632, 415, 352, 1695, 1376, 671, 
  864, 1183, 1888, 159, 224, 1823, 1248, 799, 736, 1311, 1760, 287, 480, 
  1567, 1504, 543, 992, 1055, 2016, 31, 16, 2031, 1040, 1007, 528, 1519, 
  1552, 495, 272, 1775, 1296, 751, 784, 1263, 1808, 239, 144, 1903, 1168, 
  879, 656, 1391, 1680, 367, 400, 1647, 1424, 623, 912, 1135, 1936, 111, 80, 
  1967, 1104, 943, 592, 1455, 1616, 431, 336, 1711, 1360, 687, 848, 1199, 
  1872, 175, 208, 1839, 1232, 815, 720, 1327, 1744, 303, 464, 1583, 1488, 
  559, 976, 1071, 2000, 47, 48, 1999, 1072, 975, 560, 1487, 1584, 463, 304,