From c2f434aec82cde13b201fdcb7871e3dadd6424ca Mon Sep 17 00:00:00 2001 From: John Tsiombikas Date: Sun, 14 Mar 2021 14:09:57 +0200 Subject: [PATCH] suzanne --- .gitignore | 1 + src/main.c | 3 +- src/meshdata.h | 1220 ++++++++++++++++++++++++++++++++- tools/meshdump/Makefile | 13 + tools/meshdump/cmesh.c | 1638 +++++++++++++++++++++++++++++++++++++++++++++ tools/meshdump/cmesh.h | 138 ++++ tools/meshdump/dynarr.c | 141 ++++ tools/meshdump/dynarr.h | 80 +++ tools/meshdump/main.c | 52 ++ tools/meshdump/meshload.c | 398 +++++++++++ tools/meshdump/rbtree.c | 503 ++++++++++++++ tools/meshdump/rbtree.h | 78 +++ 12 files changed, 4263 insertions(+), 2 deletions(-) create mode 100644 tools/meshdump/Makefile create mode 100644 tools/meshdump/cmesh.c create mode 100644 tools/meshdump/cmesh.h create mode 100644 tools/meshdump/dynarr.c create mode 100644 tools/meshdump/dynarr.h create mode 100644 tools/meshdump/main.c create mode 100644 tools/meshdump/meshload.c create mode 100644 tools/meshdump/rbtree.c create mode 100644 tools/meshdump/rbtree.h diff --git a/.gitignore b/.gitignore index 100346d..2cbce91 100644 --- a/.gitignore +++ b/.gitignore @@ -7,3 +7,4 @@ *.raw *.pal pngdump +meshdump diff --git a/src/main.c b/src/main.c index f95428f..bd0b287 100644 --- a/src/main.c +++ b/src/main.c @@ -92,7 +92,8 @@ int main(void) xgl_translate(0, 0, 5 << 16); xgl_rotate_x(cam_phi); xgl_rotate_y(cam_theta); - xgl_draw(XGL_QUADS, cube, sizeof cube / sizeof *cube); +// xgl_draw(XGL_QUADS, cube, sizeof cube / sizeof *cube); + xgl_draw(XGL_TRIANGLES, suzanne, sizeof suzanne / sizeof *suzanne); wait_vblank(); present(backbuf); diff --git a/src/meshdata.h b/src/meshdata.h index 72a3042..5800e89 100644 --- a/src/meshdata.h +++ b/src/meshdata.h @@ -3,7 +3,7 @@ #include "xgl.h" -static struct xvertex cube[] = { +static struct xvertex cube[] __attribute__((section(".rodata"))) = { /* front */ {-0x10000, -0x10000, -0x10000, 0, 0, -0x10000, 128}, {0x10000, -0x10000, -0x10000, 0, 0, -0x10000, 128}, @@ -36,5 +36,1223 @@ static struct xvertex cube[] = { {0x10000, -0x10000, 0x10000, 0, -0x10000, 0, 133} }; +/* suz.obj (0 submeshes): 1215 vertices, 405 faces */ +static struct xvertex suzanne[] __attribute__((section(".rodata"))) = { + {30805, 15813, 50108, 49787, -11711, 40973, 0xff}, + {28750, 9658, 50846, 49787, -11711, 40973, 0xff}, + {41501, 15861, 37125, 49787, -11711, 40973, 0xff}, + {-28750, 9658, 50846, -49787, -11711, 40973, 0xff}, + {-30805, 15813, 50108, -49787, -11711, 40973, 0xff}, + {-41501, 15861, 37125, -49787, -11711, 40973, 0xff}, + {28750, 9658, 50846, 30303, -44459, 37421, 0xff}, + {22860, -2614, 41035, 30303, -44459, 37421, 0xff}, + {35840, 3584, 37888, 30303, -44459, 37421, 0xff}, + {-22860, -2614, 41035, -30303, -44459, 37421, 0xff}, + {-28750, 9658, 50846, -30303, -44459, 37421, 0xff}, + {-35840, 3584, 37888, -30303, -44459, 37421, 0xff}, + {23522, 8413, 53136, -21771, -45088, 42283, 0xff}, + {15934, 12004, 53058, -21771, -45088, 42283, 0xff}, + {22860, -2614, 41035, -21771, -45088, 42283, 0xff}, + {-15934, 12004, 53058, 21771, -45088, 42283, 0xff}, + {-23522, 8413, 53136, 21771, -45088, 42283, 0xff}, + {-22860, -2614, 41035, 21771, -45088, 42283, 0xff}, + {4300, 15825, 43537, -43109, -24562, 42821, 0xff}, + {10240, 3584, 42496, -43109, -24562, 42821, 0xff}, + {15934, 12004, 53058, -43109, -24562, 42821, 0xff}, + {15934, 12004, 53058, -40402, 4967, 51360, 0xff}, + {17110, 21655, 53050, -40402, 4967, 51360, 0xff}, + {4300, 15825, 43537, -40402, 4967, 51360, 0xff}, + {-17110, 21655, 53050, 40402, 4967, 51360, 0xff}, + {-15934, 12004, 53058, 40402, 4967, 51360, 0xff}, + {-4300, 15825, 43537, 40402, 4967, 51360, 0xff}, + {-17110, 21655, 53050, 43004, 23416, 43561, 0xff}, + {-4300, 15825, 43537, 43004, 23416, 43561, 0xff}, + {-10240, 28672, 42496, 43004, 23416, 43561, 0xff}, + {41501, 15861, 37125, 50082, 19916, 37283, 0xff}, + {35840, 28672, 37888, 50082, 19916, 37283, 0xff}, + {28828, 22209, 50756, 50082, 19916, 37283, 0xff}, + {-30805, 15813, 50108, -49813, 11232, 41077, 0xff}, + {-28828, 22209, 50756, -49813, 11232, 41077, 0xff}, + {-41501, 15861, 37125, -49813, 11232, 41077, 0xff}, + {23522, 8413, 53136, 26627, -1710, 59860, 0xff}, + {28750, 9658, 50846, 26627, -1710, 59860, 0xff}, + {30805, 15813, 50108, 26627, -1710, 59860, 0xff}, + {-30805, 15813, 50108, -26627, -1710, 59860, 0xff}, + {-28750, 9658, 50846, -26627, -1710, 59860, 0xff}, + {-23522, 8413, 53136, -26627, -1710, 59860, 0xff}, + {23522, 8413, 53136, -616, 124, 65536, 0xff}, + {17110, 21655, 53050, -616, 124, 65536, 0xff}, + {15934, 12004, 53058, -616, 124, 65536, 0xff}, + {-15934, 12004, 53058, 616, 124, 65536, 0xff}, + {-17110, 21655, 53050, 616, 124, 65536, 0xff}, + {-23522, 8413, 53136, 616, 124, 65536, 0xff}, + {23522, 8413, 53136, 9155, 4856, 64710, 0xff}, + {22663, 24387, 52059, 9155, 4856, 64710, 0xff}, + {17110, 21655, 53050, 9155, 4856, 64710, 0xff}, + {-17110, 21655, 53050, -9155, 4856, 64710, 0xff}, + {-22663, 24387, 52059, -9155, 4856, 64710, 0xff}, + {-23522, 8413, 53136, -9155, 4856, 64710, 0xff}, + {23522, 8413, 53136, 15237, 5098, 63537, 0xff}, + {28828, 22209, 50756, 15237, 5098, 63537, 0xff}, + {22663, 24387, 52059, 15237, 5098, 63537, 0xff}, + {-22663, 24387, 52059, -15237, 5098, 63537, 0xff}, + {-28828, 22209, 50756, -15237, 5098, 63537, 0xff}, + {-23522, 8413, 53136, -15237, 5098, 63537, 0xff}, + {23522, 8413, 53136, 24064, 1258, 60948, 0xff}, + {30805, 15813, 50108, 24064, 1258, 60948, 0xff}, + {28828, 22209, 50756, 24064, 1258, 60948, 0xff}, + {-28828, 22209, 50756, -24064, 1258, 60948, 0xff}, + {-30805, 15813, 50108, -24064, 1258, 60948, 0xff}, + {-23522, 8413, 53136, -24064, 1258, 60948, 0xff}, + {17889, -58077, 42583, 13015, -55725, 31948, 0xff}, + {0, -64120, 39331, 13015, -55725, 31948, 0xff}, + {23886, -61271, 34567, 13015, -55725, 31948, 0xff}, + {10717, 45254, 49982, -11495, 54322, 34819, 0xff}, + {16522, 42544, 56125, -11495, 54322, 34819, 0xff}, + {20576, 48728, 47817, -11495, 54322, 34819, 0xff}, + {-10717, 45254, 49982, 38757, 23868, 47153, 0xff}, + {-16522, 42544, 56125, 38757, 23868, 47153, 0xff}, + {-6655, 28160, 55296, 38757, 23868, 47153, 0xff}, + {-18675, 32472, 49395, -33770, -26030, 49768, 0xff}, + {-6655, 28160, 55296, -33770, -26030, 49768, 0xff}, + {-16522, 42544, 56125, -33770, -26030, 49768, 0xff}, + {38730, -56, 40521, 22865, -13107, 59998, 0xff}, + {35596, 13941, 44774, 22865, -13107, 59998, 0xff}, + {26259, 723, 45445, 22865, -13107, 59998, 0xff}, + {7184, -8347, 51436, 17275, 5282, 62999, 0xff}, + {26259, 723, 45445, 17275, 5282, 62999, 0xff}, + {12499, 6571, 48727, 17275, 5282, 62999, 0xff}, + {-7184, -8347, 51436, -23343, -9083, 60561, 0xff}, + {-26259, 723, 45445, -23343, -9083, 60561, 0xff}, + {-38730, -56, 40521, -23343, -9083, 60561, 0xff}, + {12499, 6571, 48727, -3604, 12930, 64146, 0xff}, + {0, 5276, 48287, -3604, 12930, 64146, 0xff}, + {7184, -8347, 51436, -3604, 12930, 64146, 0xff}, + {0, 5276, 48287, 3604, 12930, 64146, 0xff}, + {-12499, 6571, 48727, 3604, 12930, 64146, 0xff}, + {-7184, -8347, 51436, 3604, 12930, 64146, 0xff}, + {-12499, 6571, 48727, 1133, -11042, 64592, 0xff}, + {0, 5276, 48287, 1133, -11042, 64592, 0xff}, + {-10870, 21498, 51250, 1133, -11042, 64592, 0xff}, + {5321, -56373, 46002, 14398, -17308, 61544, 0xff}, + {17889, -58077, 42583, 14398, -17308, 61544, 0xff}, + {6576, -48050, 48049, 14398, -17308, 61544, 0xff}, + {9270, -15610, 48065, 26856, -2260, 59736, 0xff}, + {6576, -48050, 48049, 26856, -2260, 59736, 0xff}, + {17889, -58077, 42583, 26856, -2260, 59736, 0xff}, + {-6576, -48050, 48049, -26856, -2260, 59736, 0xff}, + {-9270, -15610, 48065, -26856, -2260, 59736, 0xff}, + {-17889, -58077, 42583, -26856, -2260, 59736, 0xff}, + {7184, -8347, 51436, 63412, 15289, 6311, 0xff}, + {8547, -14728, 53199, 63412, 15289, 6311, 0xff}, + {9270, -15610, 48065, 63412, 15289, 6311, 0xff}, + {-8547, -14728, 53199, -63412, 15289, 6311, 0xff}, + {-7184, -8347, 51436, -63412, 15289, 6311, 0xff}, + {-9270, -15610, 48065, -63412, 15289, 6311, 0xff}, + {3406, -8432, 52239, -3702, 64572, -10557, 0xff}, + {7184, -8347, 51436, -3702, 64572, -10557, 0xff}, + {0, -9216, 48640, -3702, 64572, -10557, 0xff}, + {0, -12288, 52224, -65536, 0, 0, 0xff}, + {0, -9216, 48640, -65536, 0, 0, 0xff}, + {0, -12799, 49152, -65536, 0, 0, 0xff}, + {0, -12288, 52224, 42795, 37683, 32302, 0xff}, + {0, -9216, 48640, 42795, 37683, 32302, 0xff}, + {-3406, -8432, 52239, 42795, 37683, 32302, 0xff}, + {-9270, -15610, 48065, -38200, -51321, 14201, 0xff}, + {0, -22071, 49653, -38200, -51321, 14201, 0xff}, + {-8547, -14728, 53199, -38200, -51321, 14201, 0xff}, + {0, -9216, 48640, -23920, 1487, 60994, 0xff}, + {7184, -8347, 51436, -23920, 1487, 60994, 0xff}, + {0, 5276, 48287, -23920, 1487, 60994, 0xff}, + {-7184, -8347, 51436, 23920, 1487, 60994, 0xff}, + {0, -9216, 48640, 23920, 1487, 60994, 0xff}, + {0, 5276, 48287, 23920, 1487, 60994, 0xff}, + {13735, -11853, 34559, 54532, 26102, 25290, 0xff}, + {9270, -15610, 48065, 54532, 26102, 25290, 0xff}, + {20480, -28672, 37375, 54532, 26102, 25290, 0xff}, + {-5321, -56373, 46002, 20289, 44243, 43882, 0xff}, + {0, -57030, 44204, 20289, 44243, 43882, 0xff}, + {-6289, -52090, 42131, 20289, 44243, 43882, 0xff}, + {26259, 723, 45445, 21338, -19516, 58812, 0xff}, + {30196, 7872, 46389, 21338, -19516, 58812, 0xff}, + {24499, 5671, 47725, 21338, -19516, 58812, 0xff}, + {-30196, 7872, 46389, -21338, -19516, 58812, 0xff}, + {-26259, 723, 45445, -21338, -19516, 58812, 0xff}, + {-24499, 5671, 47725, -21338, -19516, 58812, 0xff}, + {26259, 723, 45445, 44531, -29537, 37938, 0xff}, + {35596, 13941, 44774, 44531, -29537, 37938, 0xff}, + {30196, 7872, 46389, 44531, -29537, 37938, 0xff}, + {-35596, 13941, 44774, -44531, -29537, 37938, 0xff}, + {-26259, 723, 45445, -44531, -29537, 37938, 0xff}, + {-30196, 7872, 46389, -44531, -29537, 37938, 0xff}, + {-18675, 32472, 49395, -25460, 29890, 52474, 0xff}, + {-37532, 23949, 45101, -25460, 29890, 52474, 0xff}, + {-27064, 25462, 49318, -25460, 29890, 52474, 0xff}, + {18675, 32472, 49395, 16207, 18730, 60673, 0xff}, + {21074, 28557, 49962, 16207, 18730, 60673, 0xff}, + {27064, 25462, 49318, 16207, 18730, 60673, 0xff}, + {-21074, 28557, 49962, -16207, 18730, 60673, 0xff}, + {-18675, 32472, 49395, -16207, 18730, 60673, 0xff}, + {-27064, 25462, 49318, -16207, 18730, 60673, 0xff}, + {18675, 32472, 49395, 1179, 10105, 64743, 0xff}, + {10870, 21498, 51250, 1179, 10105, 64743, 0xff}, + {21074, 28557, 49962, 1179, 10105, 64743, 0xff}, + {-10870, 21498, 51250, -1179, 10105, 64743, 0xff}, + {-18675, 32472, 49395, -1179, 10105, 64743, 0xff}, + {-21074, 28557, 49962, -1179, 10105, 64743, 0xff}, + {10870, 21498, 51250, -5511, 19346, 62370, 0xff}, + {18413, 25989, 50524, -5511, 19346, 62370, 0xff}, + {21074, 28557, 49962, -5511, 19346, 62370, 0xff}, + {-21074, 28557, 49962, -9299, 4508, 64716, 0xff}, + {-27064, 25462, 49318, -9299, 4508, 64716, 0xff}, + {-18413, 25989, 50524, -9299, 4508, 64716, 0xff}, + {27064, 25462, 49318, 21843, -15545, 59801, 0xff}, + {36154, 18883, 44288, 21843, -15545, 59801, 0xff}, + {37532, 23949, 45101, 21843, -15545, 59801, 0xff}, + {-37532, 23949, 45101, 55253, 9581, 33914, 0xff}, + {-35596, 13941, 44774, 55253, 9581, 33914, 0xff}, + {-36154, 18883, 44288, 55253, 9581, 33914, 0xff}, + {24499, 5671, 47725, 1428, 42939, -49492, 0xff}, + {15872, 8192, 49663, 1428, 42939, -49492, 0xff}, + {12284, 9600, 50782, 1428, 42939, -49492, 0xff}, + {12284, 9600, 50782, 28613, 35520, 47054, 0xff}, + {15872, 8192, 49663, 28613, 35520, 47054, 0xff}, + {13098, 11318, 48991, 28613, 35520, 47054, 0xff}, + {-15872, 8192, 49663, -28613, 35520, 47054, 0xff}, + {-12284, 9600, 50782, -28613, 35520, 47054, 0xff}, + {-13098, 11318, 48991, -28613, 35520, 47054, 0xff}, + {10870, 21498, 51250, 20394, -25028, 57029, 0xff}, + {12799, 19456, 49663, 20394, -25028, 57029, 0xff}, + {18413, 25989, 50524, 20394, -25028, 57029, 0xff}, + {-12799, 19456, 49663, -20394, -25028, 57029, 0xff}, + {-10870, 21498, 51250, -20394, -25028, 57029, 0xff}, + {-18413, 25989, 50524, -20394, -25028, 57029, 0xff}, + {10717, 45254, 49982, -50646, 30690, -28075, 0xff}, + {17135, 46467, 39730, -50646, 30690, -28075, 0xff}, + {7168, 30208, 39936, -50646, 30690, -28075, 0xff}, + {-17135, 46467, 39730, 50646, 30690, -28075, 0xff}, + {-10717, 45254, 49982, 50646, 30690, -28075, 0xff}, + {-7168, 30208, 39936, 50646, 30690, -28075, 0xff}, + {20576, 48728, 47817, -23049, 60922, -7222, 0xff}, + {17135, 46467, 39730, -23049, 60922, -7222, 0xff}, + {10717, 45254, 49982, -23049, 60922, -7222, 0xff}, + {-20576, 48728, 47817, -29563, 51845, -27072, 0xff}, + {-17135, 46467, 39730, -29563, 51845, -27072, 0xff}, + {-29979, 34639, 31110, -29563, 51845, -27072, 0xff}, + {52680, 10582, 27526, 58254, 7792, -28993, 0xff}, + {48630, 26065, 23550, 58254, 7792, -28993, 0xff}, + {55891, 27603, 38552, 58254, 7792, -28993, 0xff}, + {0, -31857, 19566, -16030, -55325, -31260, 0xff}, + {-16045, -30052, 24599, -16030, -55325, -31260, 0xff}, + {-11434, -27191, 17172, -16030, -55325, -31260, 0xff}, + {0, -52736, 22528, -1369, -36909, -54132, 0xff}, + {21330, -59803, 26806, -1369, -36909, -54132, 0xff}, + {0, -63999, 30208, -1369, -36909, -54132, 0xff}, + {23886, -61271, 34567, 62088, 9646, -18625, 0xff}, + {21330, -59803, 26806, 62088, 9646, -18625, 0xff}, + {16045, -30052, 24599, 62088, 9646, -18625, 0xff}, + {-21330, -59803, 26806, -62088, 9646, -18625, 0xff}, + {-23886, -61271, 34567, -62088, 9646, -18625, 0xff}, + {-16045, -30052, 24599, -62088, 9646, -18625, 0xff}, + {-13735, -11853, 34559, -15276, -54958, -32263, 0xff}, + {-38159, -5503, 35305, -15276, -54958, -32263, 0xff}, + {-34586, -3098, 29517, -15276, -54958, -32263, 0xff}, + {11434, -27191, 17172, 56492, 17045, -28508, 0xff}, + {14336, -18432, 28160, 56492, 17045, -28508, 0xff}, + {16045, -30052, 24599, 56492, 17045, -28508, 0xff}, + {30128, 26936, -46502, 42860, 11062, -48326, 0xff}, + {50190, 37864, -26209, 42860, 11062, -48326, 0xff}, + {54646, 23084, -25639, 42860, 11062, -48326, 0xff}, + {10240, 28672, 42496, -13598, 50036, 40081, 0xff}, + {22663, 24387, 52059, -13598, 50036, 40081, 0xff}, + {23039, 33792, 40448, -13598, 50036, 40081, 0xff}, + {-48630, 26065, 23550, -28193, 59106, 2503, 0xff}, + {-29979, 34639, 31110, -28193, 59106, 2503, 0xff}, + {-41471, 29696, 18432, -28193, 59106, 2503, 0xff}, + {7168, 30208, 39936, -25526, 14909, -58490, 0xff}, + {17135, 46467, 39730, -25526, 14909, -58490, 0xff}, + {29979, 34639, 31110, -25526, 14909, -58490, 0xff}, + {-17135, 46467, 39730, 25526, 14909, -58490, 0xff}, + {-7168, 30208, 39936, 25526, 14909, -58490, 0xff}, + {-29979, 34639, 31110, 25526, 14909, -58490, 0xff}, + {7168, 30208, 39936, 14424, 33803, 54257, 0xff}, + {29979, 34639, 31110, 14424, 33803, 54257, 0xff}, + {0, 37375, 37375, 14424, 33803, 54257, 0xff}, + {-29979, 34639, 31110, -14424, 33803, 54257, 0xff}, + {-7168, 30208, 39936, -14424, 33803, 54257, 0xff}, + {0, 37375, 37375, -14424, 33803, 54257, 0xff}, + {0, 26624, 39423, -10590, 12104, 63530, 0xff}, + {7168, 30208, 39936, -10590, 12104, 63530, 0xff}, + {0, 37375, 37375, -10590, 12104, 63530, 0xff}, + {0, 37375, 37375, 10590, 12104, 63530, 0xff}, + {-7168, 30208, 39936, 10590, 12104, 63530, 0xff}, + {0, 26624, 39423, 10590, 12104, 63530, 0xff}, + {-52680, 10582, 27526, -61092, 19464, 13572, 0xff}, + {-48630, 26065, 23550, -61092, 19464, 13572, 0xff}, + {-56241, 17046, 2221, -61092, 19464, 13572, 0xff}, + {56241, 17046, 2221, 62141, 11704, 17229, 0xff}, + {51216, 37752, 6281, 62141, 11704, 17229, 0xff}, + {48630, 26065, 23550, 62141, 11704, 17229, 0xff}, + {-51216, 37752, 6281, -62141, 11704, 17229, 0xff}, + {-56241, 17046, 2221, -62141, 11704, 17229, 0xff}, + {-48630, 26065, 23550, -62141, 11704, 17229, 0xff}, + {19456, -20480, -17408, 39498, -52284, -983, 0xff}, + {29162, -13292, -9698, 39498, -52284, -983, 0xff}, + {11434, -27191, 17172, 39498, -52284, -983, 0xff}, + {29162, -13292, -9698, 30579, -57901, 2726, 0xff}, + {38912, -8192, -10751, 30579, -57901, 2726, 0xff}, + {47823, -2804, 3726, 30579, -57901, 2726, 0xff}, + {34586, -3098, 29517, 24766, -59473, 12032, 0xff}, + {29162, -13292, -9698, 24766, -59473, 12032, 0xff}, + {47823, -2804, 3726, 24766, -59473, 12032, 0xff}, + {-29162, -13292, -9698, -24766, -59473, 12032, 0xff}, + {-34586, -3098, 29517, -24766, -59473, 12032, 0xff}, + {-47823, -2804, 3726, -24766, -59473, 12032, 0xff}, + {14336, -18432, 28160, 52107, -36621, 15433, 0xff}, + {11434, -27191, 17172, 52107, -36621, 15433, 0xff}, + {29162, -13292, -9698, 52107, -36621, 15433, 0xff}, + {-29162, -13292, -9698, -52107, -36621, 15433, 0xff}, + {-11434, -27191, 17172, -52107, -36621, 15433, 0xff}, + {-14336, -18432, 28160, -52107, -36621, 15433, 0xff}, + {34990, 3085, -35283, 39898, -15250, -49702, 0xff}, + {30128, 26936, -46502, 39898, -15250, -49702, 0xff}, + {54646, 23084, -25639, 39898, -15250, -49702, 0xff}, + {29162, -13292, -9698, 24884, -53477, -28560, 0xff}, + {34990, 3085, -35283, 24884, -53477, -28560, 0xff}, + {38912, -8192, -10751, 24884, -53477, -28560, 0xff}, + {-79147, 32074, -25975, -10164, -8755, 64146, 0xff}, + {-89343, 20376, -29188, -10164, -8755, 64146, 0xff}, + {-80904, 16297, -28407, -10164, -8755, 64146, 0xff}, + {77984, 6266, -28588, 10413, 32204, 56118, 0xff}, + {68018, -4978, -20287, 10413, 32204, 56118, 0xff}, + {83968, 3584, -28160, 10413, 32204, 56118, 0xff}, + {68018, -4978, -20287, 38954, -18867, 49210, 0xff}, + {55385, -3250, -9623, 38954, -18867, 49210, 0xff}, + {50688, -9216, -8192, 38954, -18867, 49210, 0xff}, + {-55385, -3250, -9623, -38954, -18867, 49210, 0xff}, + {-68018, -4978, -20287, -38954, -18867, 49210, 0xff}, + {-50688, -9216, -8192, -38954, -18867, 49210, 0xff}, + {77984, 6266, -28588, -17825, 46910, 42146, 0xff}, + {67766, 376, -26353, -17825, 46910, 42146, 0xff}, + {68018, -4978, -20287, -17825, 46910, 42146, 0xff}, + {-67766, 376, -26353, 17825, 46910, 42146, 0xff}, + {-77984, 6266, -28588, 17825, 46910, 42146, 0xff}, + {-68018, -4978, -20287, 17825, 46910, 42146, 0xff}, + {76699, 22655, -30212, -40108, -12229, 50364, 0xff}, + {80904, 16297, -28407, -40108, -12229, 50364, 0xff}, + {79147, 32074, -25975, -40108, -12229, 50364, 0xff}, + {-38912, -8192, -10751, -43823, -47860, -9161, 0xff}, + {-47823, -2804, 3726, -43823, -47860, -9161, 0xff}, + {-46721, -944, -11257, -43823, -47860, -9161, 0xff}, + {54169, 18593, -12979, 18677, 9410, 62108, 0xff}, + {64283, 24671, -16941, 18677, 9410, 62108, 0xff}, + {60188, 28534, -16295, 18677, 9410, 62108, 0xff}, + {-64283, 24671, -16941, -18677, 9410, 62108, 0xff}, + {-54169, 18593, -12979, -18677, 9410, 62108, 0xff}, + {-60188, 28534, -16295, -18677, 9410, 62108, 0xff}, + {55385, -3250, -9623, 12818, 61466, 18789, 0xff}, + {55861, -126, -20169, 12818, 61466, 18789, 0xff}, + {46721, -944, -11257, 12818, 61466, 18789, 0xff}, + {-55861, -126, -20169, -12818, 61466, 18789, 0xff}, + {-55385, -3250, -9623, -12818, 61466, 18789, 0xff}, + {-46721, -944, -11257, -12818, 61466, 18789, 0xff}, + {46721, -944, -11257, 45239, 6402, 46982, 0xff}, + {55861, -126, -20169, 45239, 6402, 46982, 0xff}, + {55793, 3702, -20626, 45239, 6402, 46982, 0xff}, + {-54169, 18593, -12979, -60823, -22315, 9869, 0xff}, + {-50746, 6427, -19395, -60823, -22315, 9869, 0xff}, + {-46721, -944, -11257, -60823, -22315, 9869, 0xff}, + {-54169, 18593, -12979, -36726, -33043, 43063, 0xff}, + {-64283, 24671, -16941, -36726, -33043, 43063, 0xff}, + {-50746, 6427, -19395, -36726, -33043, 43063, 0xff}, + {50746, 6427, -19395, 48830, -38908, 19916, 0xff}, + {63071, 20046, -23006, 48830, -38908, 19916, 0xff}, + {64283, 24671, -16941, 48830, -38908, 19916, 0xff}, + {67766, 376, -26353, 7130, 62377, 18802, 0xff}, + {55861, -126, -20169, 7130, 62377, 18802, 0xff}, + {55385, -3250, -9623, 7130, 62377, 18802, 0xff}, + {55861, -126, -20169, 19555, 1802, 62527, 0xff}, + {72755, 15982, -25917, 19555, 1802, 62527, 0xff}, + {63071, 20046, -23006, 19555, 1802, 62527, 0xff}, + {-72755, 15982, -25917, -19555, 1802, 62527, 0xff}, + {-55861, -126, -20169, -19555, 1802, 62527, 0xff}, + {-63071, 20046, -23006, -19555, 1802, 62527, 0xff}, + {55793, 3702, -20626, 16488, 1893, 63399, 0xff}, + {63071, 20046, -23006, 16488, 1893, 63399, 0xff}, + {50746, 6427, -19395, 16488, 1893, 63399, 0xff}, + {-63071, 20046, -23006, -16488, 1893, 63399, 0xff}, + {-55793, 3702, -20626, -16488, 1893, 63399, 0xff}, + {-50746, 6427, -19395, -16488, 1893, 63399, 0xff}, + {72755, 15982, -25917, 19287, -6737, 62272, 0xff}, + {77984, 6266, -28588, 19287, -6737, 62272, 0xff}, + {80904, 16297, -28407, 19287, -6737, 62272, 0xff}, + {76699, 22655, -30212, 16469, 27158, 57324, 0xff}, + {72755, 15982, -25917, 16469, 27158, 57324, 0xff}, + {80904, 16297, -28407, 16469, 27158, 57324, 0xff}, + {-72755, 15982, -25917, -16469, 27158, 57324, 0xff}, + {-76699, 22655, -30212, -16469, 27158, 57324, 0xff}, + {-80904, 16297, -28407, -16469, 27158, 57324, 0xff}, + {63071, 20046, -23006, 25808, 21069, 56439, 0xff}, + {72755, 15982, -25917, 25808, 21069, 56439, 0xff}, + {76699, 22655, -30212, 25808, 21069, 56439, 0xff}, + {-76699, 22655, -30212, -25808, 21069, 56439, 0xff}, + {-72755, 15982, -25917, -25808, 21069, 56439, 0xff}, + {-63071, 20046, -23006, -25808, 21069, 56439, 0xff}, + {-83968, 3584, -28160, -60194, -18133, 18520, 0xff}, + {-89343, 20376, -29188, -60194, -18133, 18520, 0xff}, + {-86016, 3584, -34816, -60194, -18133, 18520, 0xff}, + {89343, 20376, -29188, 49833, 42388, 3820, 0xff}, + {80412, 31511, -36230, 49833, 42388, 3820, 0xff}, + {79147, 32074, -25975, 49833, 42388, 3820, 0xff}, + {79147, 32074, -25975, -14588, 63668, -5295, 0xff}, + {80412, 31511, -36230, -14588, 63668, -5295, 0xff}, + {60188, 28534, -16295, -14588, 63668, -5295, 0xff}, + {-60188, 28534, -16295, 26135, 57357, -17950, 0xff}, + {-54646, 23084, -25639, 26135, 57357, -17950, 0xff}, + {-80412, 31511, -36230, 26135, 57357, -17950, 0xff}, + {80412, 31511, -36230, -6881, -4672, -65005, 0xff}, + {86016, 3584, -34816, -6881, -4672, -65005, 0xff}, + {68095, -5632, -32256, -6881, -4672, -65005, 0xff}, + {-86016, 3584, -34816, 6881, -4672, -65005, 0xff}, + {-80412, 31511, -36230, 6881, -4672, -65005, 0xff}, + {-68095, -5632, -32256, 6881, -4672, -65005, 0xff}, + {80412, 31511, -36230, 45324, 6723, -46858, 0xff}, + {89343, 20376, -29188, 45324, 6723, -46858, 0xff}, + {86016, 3584, -34816, 45324, 6723, -46858, 0xff}, + {-86016, 3584, -34816, -45324, 6723, -46858, 0xff}, + {-89343, 20376, -29188, -45324, 6723, -46858, 0xff}, + {-80412, 31511, -36230, -45324, 6723, -46858, 0xff}, + {-54169, 18593, -12979, 53641, 36077, 10774, 0xff}, + {-54646, 23084, -25639, 53641, 36077, 10774, 0xff}, + {-60188, 28534, -16295, 53641, 36077, 10774, 0xff}, + {54646, 23084, -25639, 36778, -10485, -53215, 0xff}, + {51711, -8192, -21504, 36778, -10485, -53215, 0xff}, + {34990, 3085, -35283, 36778, -10485, -53215, 0xff}, + {-51711, -8192, -21504, -36778, -10485, -53215, 0xff}, + {-54646, 23084, -25639, -36778, -10485, -53215, 0xff}, + {-34990, 3085, -35283, -36778, -10485, -53215, 0xff}, + {41501, 15861, 37125, 49938, -20729, 37034, 0xff}, + {28750, 9658, 50846, 49938, -20729, 37034, 0xff}, + {35840, 3584, 37888, 49938, -20729, 37034, 0xff}, + {-35840, 3584, 37888, -49938, -20729, 37034, 0xff}, + {-28750, 9658, 50846, -49938, -20729, 37034, 0xff}, + {-41501, 15861, 37125, -49938, -20729, 37034, 0xff}, + {28750, 9658, 50846, 27774, -44623, 39144, 0xff}, + {23522, 8413, 53136, 27774, -44623, 39144, 0xff}, + {22860, -2614, 41035, 27774, -44623, 39144, 0xff}, + {-22860, -2614, 41035, -27774, -44623, 39144, 0xff}, + {-23522, 8413, 53136, -27774, -44623, 39144, 0xff}, + {-28750, 9658, 50846, -27774, -44623, 39144, 0xff}, + {22860, -2614, 41035, -16816, -44800, 44780, 0xff}, + {15934, 12004, 53058, -16816, -44800, 44780, 0xff}, + {10240, 3584, 42496, -16816, -44800, 44780, 0xff}, + {-10240, 3584, 42496, 16816, -44800, 44780, 0xff}, + {-15934, 12004, 53058, 16816, -44800, 44780, 0xff}, + {-22860, -2614, 41035, 16816, -44800, 44780, 0xff}, + {-4300, 15825, 43537, 43109, -24562, 42821, 0xff}, + {-15934, 12004, 53058, 43109, -24562, 42821, 0xff}, + {-10240, 3584, 42496, 43109, -24562, 42821, 0xff}, + {17110, 21655, 53050, -43004, 23416, 43561, 0xff}, + {10240, 28672, 42496, -43004, 23416, 43561, 0xff}, + {4300, 15825, 43537, -43004, 23416, 43561, 0xff}, + {-10240, 28672, 42496, 15938, 47664, 42061, 0xff}, + {-22663, 24387, 52059, 15938, 47664, 42061, 0xff}, + {-17110, 21655, 53050, 15938, 47664, 42061, 0xff}, + {23039, 33792, 40448, 26234, 46707, 37748, 0xff}, + {28828, 22209, 50756, 26234, 46707, 37748, 0xff}, + {35840, 28672, 37888, 26234, 46707, 37748, 0xff}, + {-23039, 33792, 40448, -24700, 46779, 38685, 0xff}, + {-28828, 22209, 50756, -24700, 46779, 38685, 0xff}, + {-22663, 24387, 52059, -24700, 46779, 38685, 0xff}, + {17889, -58077, 42583, 47421, 3807, 45075, 0xff}, + {20480, -28672, 37375, 47421, 3807, 45075, 0xff}, + {9270, -15610, 48065, 47421, 3807, 45075, 0xff}, + {-41501, 15861, 37125, -50082, 19916, 37283, 0xff}, + {-28828, 22209, 50756, -50082, 19916, 37283, 0xff}, + {-35840, 28672, 37888, -50082, 19916, 37283, 0xff}, + {30805, 15813, 50108, 49813, 11232, 41077, 0xff}, + {41501, 15861, 37125, 49813, 11232, 41077, 0xff}, + {28828, 22209, 50756, 49813, 11232, 41077, 0xff}, + {-17889, -58077, 42583, -13015, -55725, 31948, 0xff}, + {-23886, -61271, 34567, -13015, -55725, 31948, 0xff}, + {0, -64120, 39331, -13015, -55725, 31948, 0xff}, + {-20480, -28672, 37375, -47421, 3807, 45075, 0xff}, + {-17889, -58077, 42583, -47421, 3807, 45075, 0xff}, + {-9270, -15610, 48065, -47421, 3807, 45075, 0xff}, + {38730, -56, 40521, 10367, -45318, 46189, 0xff}, + {13735, -11853, 34559, 10367, -45318, 46189, 0xff}, + {38159, -5503, 35305, 10367, -45318, 46189, 0xff}, + {-13735, -11853, 34559, -10367, -45318, 46189, 0xff}, + {-38730, -56, 40521, -10367, -45318, 46189, 0xff}, + {-38159, -5503, 35305, -10367, -45318, 46189, 0xff}, + {52680, 10582, 27526, 50141, -21148, 36516, 0xff}, + {45997, 26631, 45998, 50141, -21148, 36516, 0xff}, + {38730, -56, 40521, 50141, -21148, 36516, 0xff}, + {38159, -5503, 35305, 50121, -31824, 27747, 0xff}, + {52680, 10582, 27526, 50121, -31824, 27747, 0xff}, + {38730, -56, 40521, 50121, -31824, 27747, 0xff}, + {-38730, -56, 40521, -50121, -31824, 27747, 0xff}, + {-52680, 10582, 27526, -50121, -31824, 27747, 0xff}, + {-38159, -5503, 35305, -50121, -31824, 27747, 0xff}, + {-45997, 26631, 45998, -50141, -21148, 36516, 0xff}, + {-52680, 10582, 27526, -50141, -21148, 36516, 0xff}, + {-38730, -56, 40521, -50141, -21148, 36516, 0xff}, + {45997, 26631, 45998, 34078, 35651, 43162, 0xff}, + {20576, 48728, 47817, 34078, 35651, 43162, 0xff}, + {16522, 42544, 56125, 34078, 35651, 43162, 0xff}, + {-45997, 26631, 45998, -31968, 32925, 46786, 0xff}, + {-20576, 48728, 47817, -31968, 32925, 46786, 0xff}, + {-55891, 27603, 38552, -31968, 32925, 46786, 0xff}, + {6655, 28160, 55296, -37840, 37840, 37840, 0xff}, + {0, 28160, 48640, -37840, 37840, 37840, 0xff}, + {0, 23039, 53759, -37840, 37840, 37840, 0xff}, + {-10717, 45254, 49982, 11495, 54322, 34819, 0xff}, + {-20576, 48728, 47817, 11495, 54322, 34819, 0xff}, + {-16522, 42544, 56125, 11495, 54322, 34819, 0xff}, + {10717, 45254, 49982, -38757, 23868, 47153, 0xff}, + {6655, 28160, 55296, -38757, 23868, 47153, 0xff}, + {16522, 42544, 56125, -38757, 23868, 47153, 0xff}, + {-6655, 28160, 55296, 43207, 23697, 43207, 0xff}, + {0, 28160, 48640, 43207, 23697, 43207, 0xff}, + {-10717, 45254, 49982, 43207, 23697, 43207, 0xff}, + {37532, 23949, 45101, -4436, -36975, 53923, 0xff}, + {16522, 42544, 56125, -4436, -36975, 53923, 0xff}, + {18675, 32472, 49395, -4436, -36975, 53923, 0xff}, + {18675, 32472, 49395, 33770, -26030, 49768, 0xff}, + {16522, 42544, 56125, 33770, -26030, 49768, 0xff}, + {6655, 28160, 55296, 33770, -26030, 49768, 0xff}, + {-16522, 42544, 56125, 4436, -36975, 53923, 0xff}, + {-37532, 23949, 45101, 4436, -36975, 53923, 0xff}, + {-18675, 32472, 49395, 4436, -36975, 53923, 0xff}, + {35596, 13941, 44774, -6638, -845, 65195, 0xff}, + {45997, 26631, 45998, -6638, -845, 65195, 0xff}, + {37532, 23949, 45101, -6638, -845, 65195, 0xff}, + {-45997, 26631, 45998, 6638, -845, 65195, 0xff}, + {-35596, 13941, 44774, 6638, -845, 65195, 0xff}, + {-37532, 23949, 45101, 6638, -845, 65195, 0xff}, + {10870, 21498, 51250, 9201, -29327, 57881, 0xff}, + {6655, 28160, 55296, 9201, -29327, 57881, 0xff}, + {0, 23039, 53759, 9201, -29327, 57881, 0xff}, + {-38730, -56, 40521, -22865, -13107, 59998, 0xff}, + {-26259, 723, 45445, -22865, -13107, 59998, 0xff}, + {-35596, 13941, 44774, -22865, -13107, 59998, 0xff}, + {7184, -8347, 51436, 23343, -9083, 60561, 0xff}, + {38730, -56, 40521, 23343, -9083, 60561, 0xff}, + {26259, 723, 45445, 23343, -9083, 60561, 0xff}, + {-7184, -8347, 51436, -17275, 5282, 62999, 0xff}, + {-12499, 6571, 48727, -17275, 5282, 62999, 0xff}, + {-26259, 723, 45445, -17275, 5282, 62999, 0xff}, + {-10870, 21498, 51250, -32086, -13428, 55541, 0xff}, + {-6655, 28160, 55296, -32086, -13428, 55541, 0xff}, + {-18675, 32472, 49395, -32086, -13428, 55541, 0xff}, + {0, -64120, 39331, -13375, -36339, 52874, 0xff}, + {5321, -56373, 46002, -13375, -36339, 52874, 0xff}, + {0, -57030, 44204, -13375, -36339, 52874, 0xff}, + {10870, 21498, 51250, 11540, -18992, 61649, 0xff}, + {0, 23039, 53759, 11540, -18992, 61649, 0xff}, + {0, 5276, 48287, 11540, -18992, 61649, 0xff}, + {0, 5276, 48287, -11540, -18992, 61649, 0xff}, + {0, 23039, 53759, -11540, -18992, 61649, 0xff}, + {-10870, 21498, 51250, -11540, -18992, 61649, 0xff}, + {12499, 6571, 48727, -1133, -11042, 64592, 0xff}, + {10870, 21498, 51250, -1133, -11042, 64592, 0xff}, + {0, 5276, 48287, -1133, -11042, 64592, 0xff}, + {-5321, -56373, 46002, 13375, -36339, 52874, 0xff}, + {0, -64120, 39331, 13375, -36339, 52874, 0xff}, + {0, -57030, 44204, 13375, -36339, 52874, 0xff}, + {6576, -48050, 48049, 334, -3951, 65418, 0xff}, + {0, -22071, 49653, 334, -3951, 65418, 0xff}, + {0, -50426, 47939, 334, -3951, 65418, 0xff}, + {-5321, -56373, 46002, -14398, -17308, 61544, 0xff}, + {-6576, -48050, 48049, -14398, -17308, 61544, 0xff}, + {-17889, -58077, 42583, -14398, -17308, 61544, 0xff}, + {0, -22071, 49653, -334, -3951, 65418, 0xff}, + {-6576, -48050, 48049, -334, -3951, 65418, 0xff}, + {0, -50426, 47939, -334, -3951, 65418, 0xff}, + {3406, -8432, 52239, 12582, 19614, 61256, 0xff}, + {8547, -14728, 53199, 12582, 19614, 61256, 0xff}, + {7184, -8347, 51436, 12582, 19614, 61256, 0xff}, + {-3406, -8432, 52239, 3702, 64572, -10557, 0xff}, + {0, -9216, 48640, 3702, 64572, -10557, 0xff}, + {-7184, -8347, 51436, 3702, 64572, -10557, 0xff}, + {0, -12288, 52224, -42795, 37683, 32302, 0xff}, + {3406, -8432, 52239, -42795, 37683, 32302, 0xff}, + {0, -9216, 48640, -42795, 37683, 32302, 0xff}, + {9270, -15610, 48065, 38200, -51321, 14201, 0xff}, + {8547, -14728, 53199, 38200, -51321, 14201, 0xff}, + {0, -22071, 49653, 38200, -51321, 14201, 0xff}, + {0, -12288, 52224, -46668, 41150, 20578, 0xff}, + {0, -13312, 54272, -46668, 41150, 20578, 0xff}, + {3406, -8432, 52239, -46668, 41150, 20578, 0xff}, + {-3406, -8432, 52239, 46668, 41150, 20578, 0xff}, + {0, -13312, 54272, 46668, 41150, 20578, 0xff}, + {0, -12288, 52224, 46668, 41150, 20578, 0xff}, + {-3406, -8432, 52239, -10806, 18277, 61997, 0xff}, + {-8547, -14728, 53199, -10806, 18277, 61997, 0xff}, + {0, -13312, 54272, -10806, 18277, 61997, 0xff}, + {6576, -48050, 48049, -2496, -54027, 37008, 0xff}, + {0, -51200, 43008, -2496, -54027, 37008, 0xff}, + {6289, -52090, 42131, -2496, -54027, 37008, 0xff}, + {0, -13312, 54272, 2208, -30546, 57940, 0xff}, + {0, -22071, 49653, 2208, -30546, 57940, 0xff}, + {8547, -14728, 53199, 2208, -30546, 57940, 0xff}, + {-8547, -14728, 53199, -2208, -30546, 57940, 0xff}, + {0, -22071, 49653, -2208, -30546, 57940, 0xff}, + {0, -13312, 54272, -2208, -30546, 57940, 0xff}, + {-13735, -11853, 34559, -54532, 26102, 25290, 0xff}, + {-20480, -28672, 37375, -54532, 26102, 25290, 0xff}, + {-9270, -15610, 48065, -54532, 26102, 25290, 0xff}, + {13735, -11853, 34559, 61210, 7261, 22249, 0xff}, + {7184, -8347, 51436, 61210, 7261, 22249, 0xff}, + {9270, -15610, 48065, 61210, 7261, 22249, 0xff}, + {-9270, -15610, 48065, -61210, 7261, 22249, 0xff}, + {-7184, -8347, 51436, -61210, 7261, 22249, 0xff}, + {-13735, -11853, 34559, -61210, 7261, 22249, 0xff}, + {5321, -56373, 46002, -20289, 44243, 43882, 0xff}, + {6289, -52090, 42131, -20289, 44243, 43882, 0xff}, + {0, -57030, 44204, -20289, 44243, 43882, 0xff}, + {5321, -56373, 46002, -64507, 10761, -4213, 0xff}, + {6576, -48050, 48049, -64507, 10761, -4213, 0xff}, + {6289, -52090, 42131, -64507, 10761, -4213, 0xff}, + {-6289, -52090, 42131, 64507, 10761, -4213, 0xff}, + {-6576, -48050, 48049, 64507, 10761, -4213, 0xff}, + {-5321, -56373, 46002, 64507, 10761, -4213, 0xff}, + {0, -51200, 43008, 2496, -54027, 37008, 0xff}, + {-6576, -48050, 48049, 2496, -54027, 37008, 0xff}, + {-6289, -52090, 42131, 2496, -54027, 37008, 0xff}, + {24499, 5671, 47725, 3008, -26522, 59854, 0xff}, + {12499, 6571, 48727, 3008, -26522, 59854, 0xff}, + {26259, 723, 45445, 3008, -26522, 59854, 0xff}, + {0, -51200, 43008, 10662, 12995, 63340, 0xff}, + {0, -57030, 44204, 10662, 12995, 63340, 0xff}, + {6289, -52090, 42131, 10662, 12995, 63340, 0xff}, + {-6289, -52090, 42131, -10662, 12995, 63340, 0xff}, + {0, -57030, 44204, -10662, 12995, 63340, 0xff}, + {0, -51200, 43008, -10662, 12995, 63340, 0xff}, + {10870, 21498, 51250, -64874, -7897, 4856, 0xff}, + {12499, 6571, 48727, -64874, -7897, 4856, 0xff}, + {12284, 9600, 50782, -64874, -7897, 4856, 0xff}, + {-12284, 9600, 50782, 64874, -7897, 4856, 0xff}, + {-12499, 6571, 48727, 64874, -7897, 4856, 0xff}, + {-10870, 21498, 51250, 64874, -7897, 4856, 0xff}, + {-12499, 6571, 48727, -3008, -26522, 59854, 0xff}, + {-24499, 5671, 47725, -3008, -26522, 59854, 0xff}, + {-26259, 723, 45445, -3008, -26522, 59854, 0xff}, + {12799, 19456, 49663, 59683, -52, 27066, 0xff}, + {12284, 9600, 50782, 59683, -52, 27066, 0xff}, + {13098, 11318, 48991, 59683, -52, 27066, 0xff}, + {18675, 32472, 49395, 25460, 29890, 52474, 0xff}, + {27064, 25462, 49318, 25460, 29890, 52474, 0xff}, + {37532, 23949, 45101, 25460, 29890, 52474, 0xff}, + {-10870, 21498, 51250, 5511, 19346, 62370, 0xff}, + {-21074, 28557, 49962, 5511, 19346, 62370, 0xff}, + {-18413, 25989, 50524, 5511, 19346, 62370, 0xff}, + {21074, 28557, 49962, 9299, 4508, 64716, 0xff}, + {18413, 25989, 50524, 9299, 4508, 64716, 0xff}, + {27064, 25462, 49318, 9299, 4508, 64716, 0xff}, + {-27064, 25462, 49318, -21843, -15545, 59801, 0xff}, + {-37532, 23949, 45101, -21843, -15545, 59801, 0xff}, + {-36154, 18883, 44288, -21843, -15545, 59801, 0xff}, + {37532, 23949, 45101, -55253, 9581, 33914, 0xff}, + {36154, 18883, 44288, -55253, 9581, 33914, 0xff}, + {35596, 13941, 44774, -55253, 9581, 33914, 0xff}, + {-24499, 5671, 47725, -1428, 42939, -49492, 0xff}, + {-12284, 9600, 50782, -1428, 42939, -49492, 0xff}, + {-15872, 8192, 49663, -1428, 42939, -49492, 0xff}, + {-12799, 19456, 49663, -43601, 3257, 48817, 0xff}, + {-12284, 9600, 50782, -43601, 3257, 48817, 0xff}, + {-10870, 21498, 51250, -43601, 3257, 48817, 0xff}, + {7168, 30208, 39936, -47526, 32269, -31542, 0xff}, + {0, 28160, 48640, -47526, 32269, -31542, 0xff}, + {10717, 45254, 49982, -47526, 32269, -31542, 0xff}, + {0, 28160, 48640, 47526, 32269, -31542, 0xff}, + {-7168, 30208, 39936, 47526, 32269, -31542, 0xff}, + {-10717, 45254, 49982, 47526, 32269, -31542, 0xff}, + {29979, 34639, 31110, 20951, 59926, -16285, 0xff}, + {55891, 27603, 38552, 20951, 59926, -16285, 0xff}, + {48630, 26065, 23550, 20951, 59926, -16285, 0xff}, + {-20576, 48728, 47817, 23049, 60922, -7222, 0xff}, + {-10717, 45254, 49982, 23049, 60922, -7222, 0xff}, + {-17135, 46467, 39730, 23049, 60922, -7222, 0xff}, + {20576, 48728, 47817, 29563, 51845, -27072, 0xff}, + {29979, 34639, 31110, 29563, 51845, -27072, 0xff}, + {17135, 46467, 39730, 29563, 51845, -27072, 0xff}, + {-29979, 34639, 31110, -23291, 52658, -31299, 0xff}, + {-55891, 27603, 38552, -23291, 52658, -31299, 0xff}, + {-20576, 48728, 47817, -23291, 52658, -31299, 0xff}, + {0, -52736, 22528, 12038, -2634, -64369, 0xff}, + {16045, -30052, 24599, 12038, -2634, -64369, 0xff}, + {21330, -59803, 26806, 12038, -2634, -64369, 0xff}, + {-52680, 10582, 27526, -58254, 7792, -28993, 0xff}, + {-55891, 27603, 38552, -58254, 7792, -28993, 0xff}, + {-48630, 26065, 23550, -58254, 7792, -28993, 0xff}, + {52680, 10582, 27526, 29904, -44957, -37139, 0xff}, + {38159, -5503, 35305, 29904, -44957, -37139, 0xff}, + {34586, -3098, 29517, 29904, -44957, -37139, 0xff}, + {-34586, -3098, 29517, -29904, -44957, -37139, 0xff}, + {-38159, -5503, 35305, -29904, -44957, -37139, 0xff}, + {-52680, 10582, 27526, -29904, -44957, -37139, 0xff}, + {0, -31857, 19566, 16030, -55325, -31260, 0xff}, + {11434, -27191, 17172, 16030, -55325, -31260, 0xff}, + {16045, -30052, 24599, 16030, -55325, -31260, 0xff}, + {-16045, -30052, 24599, -12038, -2634, -64369, 0xff}, + {0, -52736, 22528, -12038, -2634, -64369, 0xff}, + {-21330, -59803, 26806, -12038, -2634, -64369, 0xff}, + {0, -63999, 30208, 7589, -65090, -858, 0xff}, + {23886, -61271, 34567, 7589, -65090, -858, 0xff}, + {0, -64120, 39331, 7589, -65090, -858, 0xff}, + {0, -52736, 22528, 1369, -36909, -54132, 0xff}, + {0, -63999, 30208, 1369, -36909, -54132, 0xff}, + {-21330, -59803, 26806, 1369, -36909, -54132, 0xff}, + {-23886, -61271, 34567, -7589, -65090, -858, 0xff}, + {0, -63999, 30208, -7589, -65090, -858, 0xff}, + {0, -64120, 39331, -7589, -65090, -858, 0xff}, + {20480, -28672, 37375, 59821, 21266, -16246, 0xff}, + {14336, -18432, 28160, 59821, 21266, -16246, 0xff}, + {13735, -11853, 34559, 59821, 21266, -16246, 0xff}, + {20480, -28672, 37375, 61131, 8290, -22111, 0xff}, + {23886, -61271, 34567, 61131, 8290, -22111, 0xff}, + {16045, -30052, 24599, 61131, 8290, -22111, 0xff}, + {-16045, -30052, 24599, -61131, 8290, -22111, 0xff}, + {-23886, -61271, 34567, -61131, 8290, -22111, 0xff}, + {-20480, -28672, 37375, -61131, 8290, -22111, 0xff}, + {-14336, -18432, 28160, -59821, 21266, -16246, 0xff}, + {-20480, -28672, 37375, -59821, 21266, -16246, 0xff}, + {-13735, -11853, 34559, -59821, 21266, -16246, 0xff}, + {0, 4607, -54272, 24451, -30828, -52409, 0xff}, + {22528, -9728, -35327, 24451, -30828, -52409, 0xff}, + {0, -12799, -44032, 24451, -30828, -52409, 0xff}, + {13735, -11853, 34559, 15276, -54958, -32263, 0xff}, + {34586, -3098, 29517, 15276, -54958, -32263, 0xff}, + {38159, -5503, 35305, 15276, -54958, -32263, 0xff}, + {-22528, -9728, -35327, -24451, -30828, -52409, 0xff}, + {0, 4607, -54272, -24451, -30828, -52409, 0xff}, + {0, -12799, -44032, -24451, -30828, -52409, 0xff}, + {0, -25087, -23039, 21384, -54670, -29137, 0xff}, + {22528, -9728, -35327, 21384, -54670, -29137, 0xff}, + {19456, -20480, -17408, 21384, -54670, -29137, 0xff}, + {0, -25087, -23039, -19569, -53975, -31594, 0xff}, + {-22528, -9728, -35327, -19569, -53975, -31594, 0xff}, + {0, -12799, -44032, -19569, -53975, -31594, 0xff}, + {11434, -27191, 17172, 17216, -62704, -8172, 0xff}, + {0, -25087, -23039, 17216, -62704, -8172, 0xff}, + {19456, -20480, -17408, 17216, -62704, -8172, 0xff}, + {0, -25087, -23039, -17216, -62704, -8172, 0xff}, + {-11434, -27191, 17172, -17216, -62704, -8172, 0xff}, + {-19456, -20480, -17408, -17216, -62704, -8172, 0xff}, + {47823, -2804, 3726, 39085, -48857, 19503, 0xff}, + {52680, 10582, 27526, 39085, -48857, 19503, 0xff}, + {34586, -3098, 29517, 39085, -48857, 19503, 0xff}, + {-11434, -27191, 17172, -56492, 17045, -28508, 0xff}, + {-16045, -30052, 24599, -56492, 17045, -28508, 0xff}, + {-14336, -18432, 28160, -56492, 17045, -28508, 0xff}, + {-52680, 10582, 27526, -39085, -48857, 19503, 0xff}, + {-47823, -2804, 3726, -39085, -48857, 19503, 0xff}, + {-34586, -3098, 29517, -39085, -48857, 19503, 0xff}, + {0, 4607, -54272, 29084, -20034, -55200, 0xff}, + {30128, 26936, -46502, 29084, -20034, -55200, 0xff}, + {34990, 3085, -35283, 29084, -20034, -55200, 0xff}, + {0, 4607, -54272, -18415, -2988, -62822, 0xff}, + {-30128, 26936, -46502, -18415, -2988, -62822, 0xff}, + {0, 36864, -55807, -18415, -2988, -62822, 0xff}, + {0, 64512, -5120, 7333, 63084, 16174, 0xff}, + {29696, 55807, 15360, 7333, 63084, 16174, 0xff}, + {29696, 60928, -4607, 7333, 63084, 16174, 0xff}, + {0, 64512, -5120, -8336, 63294, 14811, 0xff}, + {-29696, 55807, 15360, -8336, 63294, 14811, 0xff}, + {0, 58880, 18943, -8336, 63294, 14811, 0xff}, + {29696, 56832, -25087, 7916, 63792, -12759, 0xff}, + {0, 64512, -5120, 7916, 63792, -12759, 0xff}, + {29696, 60928, -4607, 7916, 63792, -12759, 0xff}, + {0, 64512, -5120, -7916, 63792, -12759, 0xff}, + {-29696, 56832, -25087, -7916, 63792, -12759, 0xff}, + {-29696, 60928, -4607, -7916, 63792, -12759, 0xff}, + {30128, 26936, -46502, 20755, 36398, -50390, 0xff}, + {0, 58880, -35840, 20755, 36398, -50390, 0xff}, + {29696, 56832, -25087, 20755, 36398, -50390, 0xff}, + {0, 58880, -35840, -20755, 36398, -50390, 0xff}, + {-30128, 26936, -46502, -20755, 36398, -50390, 0xff}, + {-29696, 56832, -25087, -20755, 36398, -50390, 0xff}, + {51586, 40861, -9829, 42506, 48916, -9784, 0xff}, + {29696, 56832, -25087, 42506, 48916, -9784, 0xff}, + {29696, 60928, -4607, 42506, 48916, -9784, 0xff}, + {41471, 29696, 18432, 1140, 54185, 36844, 0xff}, + {48630, 26065, 23550, 1140, 54185, 36844, 0xff}, + {51216, 37752, 6281, 1140, 54185, 36844, 0xff}, + {-51216, 37752, 6281, -1140, 54185, 36844, 0xff}, + {-48630, 26065, 23550, -1140, 54185, 36844, 0xff}, + {-41471, 29696, 18432, -1140, 54185, 36844, 0xff}, + {-30128, 26936, -46502, -42860, 11062, -48326, 0xff}, + {-54646, 23084, -25639, -42860, 11062, -48326, 0xff}, + {-50190, 37864, -26209, -42860, 11062, -48326, 0xff}, + {30128, 26936, -46502, 29261, 34426, -47467, 0xff}, + {29696, 56832, -25087, 29261, 34426, -47467, 0xff}, + {50190, 37864, -26209, 29261, 34426, -47467, 0xff}, + {-50190, 37864, -26209, -29261, 34426, -47467, 0xff}, + {-29696, 56832, -25087, -29261, 34426, -47467, 0xff}, + {-30128, 26936, -46502, -29261, 34426, -47467, 0xff}, + {-29696, 56832, -25087, -42506, 48916, -9784, 0xff}, + {-51586, 40861, -9829, -42506, 48916, -9784, 0xff}, + {-29696, 60928, -4607, -42506, 48916, -9784, 0xff}, + {51216, 37752, 6281, 44308, 46779, 11993, 0xff}, + {29696, 60928, -4607, 44308, 46779, 11993, 0xff}, + {29696, 55807, 15360, 44308, 46779, 11993, 0xff}, + {-29696, 60928, -4607, -44308, 46779, 11993, 0xff}, + {-51216, 37752, 6281, -44308, 46779, 11993, 0xff}, + {-29696, 55807, 15360, -44308, 46779, 11993, 0xff}, + {41471, 29696, 18432, 49230, 26247, 34386, 0xff}, + {29696, 55807, 15360, 49230, 26247, 34386, 0xff}, + {29979, 34639, 31110, 49230, 26247, 34386, 0xff}, + {-29696, 55807, 15360, -49230, 26247, 34386, 0xff}, + {-41471, 29696, 18432, -49230, 26247, 34386, 0xff}, + {-29979, 34639, 31110, -49230, 26247, 34386, 0xff}, + {0, 58880, 18943, 10262, 38725, 51865, 0xff}, + {29979, 34639, 31110, 10262, 38725, 51865, 0xff}, + {29696, 55807, 15360, 10262, 38725, 51865, 0xff}, + {48630, 26065, 23550, 28193, 59106, 2503, 0xff}, + {41471, 29696, 18432, 28193, 59106, 2503, 0xff}, + {29979, 34639, 31110, 28193, 59106, 2503, 0xff}, + {0, 58880, 18943, -13965, 41667, 48614, 0xff}, + {-29979, 34639, 31110, -13965, 41667, 48614, 0xff}, + {0, 37375, 37375, -13965, 41667, 48614, 0xff}, + {51586, 40861, -9829, 64487, 8598, -7916, 0xff}, + {56241, 17046, 2221, 64487, 8598, -7916, 0xff}, + {54169, 18593, -12979, 64487, 8598, -7916, 0xff}, + {52680, 10582, 27526, 61092, 19464, 13572, 0xff}, + {56241, 17046, 2221, 61092, 19464, 13572, 0xff}, + {48630, 26065, 23550, 61092, 19464, 13572, 0xff}, + {-56241, 17046, 2221, -64487, 8598, -7916, 0xff}, + {-51586, 40861, -9829, -64487, 8598, -7916, 0xff}, + {-54169, 18593, -12979, -64487, 8598, -7916, 0xff}, + {54646, 23084, -25639, 64992, 6848, 4882, 0xff}, + {51586, 40861, -9829, 64992, 6848, 4882, 0xff}, + {54169, 18593, -12979, 64992, 6848, 4882, 0xff}, + {-51586, 40861, -9829, -64992, 6848, 4882, 0xff}, + {-54646, 23084, -25639, -64992, 6848, 4882, 0xff}, + {-54169, 18593, -12979, -64992, 6848, 4882, 0xff}, + {14336, -18432, 28160, 27479, -40173, 43882, 0xff}, + {34586, -3098, 29517, 27479, -40173, 43882, 0xff}, + {13735, -11853, 34559, 27479, -40173, 43882, 0xff}, + {-19456, -20480, -17408, -39498, -52284, -983, 0xff}, + {-11434, -27191, 17172, -39498, -52284, -983, 0xff}, + {-29162, -13292, -9698, -39498, -52284, -983, 0xff}, + {-29162, -13292, -9698, -30579, -57901, 2726, 0xff}, + {-47823, -2804, 3726, -30579, -57901, 2726, 0xff}, + {-38912, -8192, -10751, -30579, -57901, 2726, 0xff}, + {-34586, -3098, 29517, -27479, -40173, 43882, 0xff}, + {-14336, -18432, 28160, -27479, -40173, 43882, 0xff}, + {-13735, -11853, 34559, -27479, -40173, 43882, 0xff}, + {29162, -13292, -9698, 45239, -43941, -17819, 0xff}, + {22528, -9728, -35327, 45239, -43941, -17819, 0xff}, + {34990, 3085, -35283, 45239, -43941, -17819, 0xff}, + {-34990, 3085, -35283, -39898, -15250, -49702, 0xff}, + {-54646, 23084, -25639, -39898, -15250, -49702, 0xff}, + {-30128, 26936, -46502, -39898, -15250, -49702, 0xff}, + {-29162, -13292, -9698, -24884, -53477, -28560, 0xff}, + {-38912, -8192, -10751, -24884, -53477, -28560, 0xff}, + {-34990, 3085, -35283, -24884, -53477, -28560, 0xff}, + {-29162, -13292, -9698, -46084, -43017, -17910, 0xff}, + {-22528, -9728, -35327, -46084, -43017, -17910, 0xff}, + {-19456, -20480, -17408, -46084, -43017, -17910, 0xff}, + {83968, 3584, -28160, -4607, 163, 65372, 0xff}, + {80904, 16297, -28407, -4607, 163, 65372, 0xff}, + {77984, 6266, -28588, -4607, 163, 65372, 0xff}, + {60188, 28534, -16295, 25971, 17937, 57435, 0xff}, + {64283, 24671, -16941, 25971, 17937, 57435, 0xff}, + {79147, 32074, -25975, 25971, 17937, 57435, 0xff}, + {-79147, 32074, -25975, -25971, 17937, 57435, 0xff}, + {-64283, 24671, -16941, -25971, 17937, 57435, 0xff}, + {-60188, 28534, -16295, -25971, 17937, 57435, 0xff}, + {79147, 32074, -25975, 10164, -8755, 64146, 0xff}, + {80904, 16297, -28407, 10164, -8755, 64146, 0xff}, + {89343, 20376, -29188, 10164, -8755, 64146, 0xff}, + {-83968, 3584, -28160, -4856, 2444, 65313, 0xff}, + {-80904, 16297, -28407, -4856, 2444, 65313, 0xff}, + {-89343, 20376, -29188, -4856, 2444, 65313, 0xff}, + {64283, 24671, -16941, 40416, -29530, 42303, 0xff}, + {76699, 22655, -30212, 40416, -29530, 42303, 0xff}, + {79147, 32074, -25975, 40416, -29530, 42303, 0xff}, + {-77984, 6266, -28588, -10413, 32204, 56118, 0xff}, + {-83968, 3584, -28160, -10413, 32204, 56118, 0xff}, + {-68018, -4978, -20287, -10413, 32204, 56118, 0xff}, + {68018, -4978, -20287, 35717, 41923, 35520, 0xff}, + {67766, 376, -26353, 35717, 41923, 35520, 0xff}, + {55385, -3250, -9623, 35717, 41923, 35520, 0xff}, + {-55385, -3250, -9623, -35717, 41923, 35520, 0xff}, + {-67766, 376, -26353, -35717, 41923, 35520, 0xff}, + {-68018, -4978, -20287, -35717, 41923, 35520, 0xff}, + {-76699, 22655, -30212, 40108, -12229, 50364, 0xff}, + {-79147, 32074, -25975, 40108, -12229, 50364, 0xff}, + {-80904, 16297, -28407, 40108, -12229, 50364, 0xff}, + {-76699, 22655, -30212, -40416, -29530, 42303, 0xff}, + {-64283, 24671, -16941, -40416, -29530, 42303, 0xff}, + {-79147, 32074, -25975, -40416, -29530, 42303, 0xff}, + {46721, -944, -11257, -6402, 19942, 62095, 0xff}, + {50688, -9216, -8192, -6402, 19942, 62095, 0xff}, + {55385, -3250, -9623, -6402, 19942, 62095, 0xff}, + {38912, -8192, -10751, 43823, -47860, -9161, 0xff}, + {46721, -944, -11257, 43823, -47860, -9161, 0xff}, + {47823, -2804, 3726, 43823, -47860, -9161, 0xff}, + {-46721, -944, -11257, 11993, 17255, 62075, 0xff}, + {-50688, -9216, -8192, 11993, 17255, 62075, 0xff}, + {-38912, -8192, -10751, 11993, 17255, 62075, 0xff}, + {56241, 17046, 2221, 60109, -23848, -10623, 0xff}, + {46721, -944, -11257, 60109, -23848, -10623, 0xff}, + {54169, 18593, -12979, 60109, -23848, -10623, 0xff}, + {-46721, -944, -11257, -45239, 6402, 46982, 0xff}, + {-55793, 3702, -20626, -45239, 6402, 46982, 0xff}, + {-55861, -126, -20169, -45239, 6402, 46982, 0xff}, + {50746, 6427, -19395, 30185, 34891, 46543, 0xff}, + {46721, -944, -11257, 30185, 34891, 46543, 0xff}, + {55793, 3702, -20626, 30185, 34891, 46543, 0xff}, + {-55793, 3702, -20626, -30185, 34891, 46543, 0xff}, + {-46721, -944, -11257, -30185, 34891, 46543, 0xff}, + {-50746, 6427, -19395, -30185, 34891, 46543, 0xff}, + {54169, 18593, -12979, 60823, -22315, 9869, 0xff}, + {46721, -944, -11257, 60823, -22315, 9869, 0xff}, + {50746, 6427, -19395, 60823, -22315, 9869, 0xff}, + {54169, 18593, -12979, 36726, -33043, 43063, 0xff}, + {50746, 6427, -19395, 36726, -33043, 43063, 0xff}, + {64283, 24671, -16941, 36726, -33043, 43063, 0xff}, + {-46721, -944, -11257, -60109, -23848, -10623, 0xff}, + {-56241, 17046, 2221, -60109, -23848, -10623, 0xff}, + {-54169, 18593, -12979, -60109, -23848, -10623, 0xff}, + {67766, 376, -26353, 30133, -11226, 57101, 0xff}, + {72755, 15982, -25917, 30133, -11226, 57101, 0xff}, + {55861, -126, -20169, 30133, -11226, 57101, 0xff}, + {-50746, 6427, -19395, -48830, -38908, 19916, 0xff}, + {-64283, 24671, -16941, -48830, -38908, 19916, 0xff}, + {-63071, 20046, -23006, -48830, -38908, 19916, 0xff}, + {-67766, 376, -26353, -7130, 62377, 18802, 0xff}, + {-55385, -3250, -9623, -7130, 62377, 18802, 0xff}, + {-55861, -126, -20169, -7130, 62377, 18802, 0xff}, + {55793, 3702, -20626, 3702, 7811, 64965, 0xff}, + {55861, -126, -20169, 3702, 7811, 64965, 0xff}, + {63071, 20046, -23006, 3702, 7811, 64965, 0xff}, + {-63071, 20046, -23006, -3702, 7811, 64965, 0xff}, + {-55861, -126, -20169, -3702, 7811, 64965, 0xff}, + {-55793, 3702, -20626, -3702, 7811, 64965, 0xff}, + {-67766, 376, -26353, -18009, -7503, 62567, 0xff}, + {-72755, 15982, -25917, -18009, -7503, 62567, 0xff}, + {-77984, 6266, -28588, -18009, -7503, 62567, 0xff}, + {51711, -8192, -21504, 12930, -64126, -3938, 0xff}, + {68018, -4978, -20287, 12930, -64126, -3938, 0xff}, + {50688, -9216, -8192, 12930, -64126, -3938, 0xff}, + {-72755, 15982, -25917, -19287, -6737, 62272, 0xff}, + {-80904, 16297, -28407, -19287, -6737, 62272, 0xff}, + {-77984, 6266, -28588, -19287, -6737, 62272, 0xff}, + {-68018, -4978, -20287, -12930, -64126, -3938, 0xff}, + {-51711, -8192, -21504, -12930, -64126, -3938, 0xff}, + {-50688, -9216, -8192, -12930, -64126, -3938, 0xff}, + {68095, -5632, -32256, 32224, -56970, 3316, 0xff}, + {83968, 3584, -28160, 32224, -56970, 3316, 0xff}, + {68018, -4978, -20287, 32224, -56970, 3316, 0xff}, + {-83968, 3584, -28160, -32224, -56970, 3316, 0xff}, + {-68095, -5632, -32256, -32224, -56970, 3316, 0xff}, + {-68018, -4978, -20287, -32224, -56970, 3316, 0xff}, + {54646, 23084, -25639, -35461, -3945, -54971, 0xff}, + {68095, -5632, -32256, -35461, -3945, -54971, 0xff}, + {51711, -8192, -21504, -35461, -3945, -54971, 0xff}, + {83968, 3584, -28160, 60194, -18133, 18520, 0xff}, + {86016, 3584, -34816, 60194, -18133, 18520, 0xff}, + {89343, 20376, -29188, 60194, -18133, 18520, 0xff}, + {-89343, 20376, -29188, -49833, 42388, 3820, 0xff}, + {-79147, 32074, -25975, -49833, 42388, 3820, 0xff}, + {-80412, 31511, -36230, -49833, 42388, 3820, 0xff}, + {-79147, 32074, -25975, 14588, 63668, -5295, 0xff}, + {-60188, 28534, -16295, 14588, 63668, -5295, 0xff}, + {-80412, 31511, -36230, 14588, 63668, -5295, 0xff}, + {60188, 28534, -16295, -26135, 57357, -17950, 0xff}, + {80412, 31511, -36230, -26135, 57357, -17950, 0xff}, + {54646, 23084, -25639, -26135, 57357, -17950, 0xff}, + {-54646, 23084, -25639, 25454, 1985, -60358, 0xff}, + {-68095, -5632, -32256, 25454, 1985, -60358, 0xff}, + {-80412, 31511, -36230, 25454, 1985, -60358, 0xff}, + {51711, -8192, -21504, -19719, -57920, -23474, 0xff}, + {38912, -8192, -10751, -19719, -57920, -23474, 0xff}, + {34990, 3085, -35283, -19719, -57920, -23474, 0xff}, + {54169, 18593, -12979, -53641, 36077, 10774, 0xff}, + {60188, 28534, -16295, -53641, 36077, 10774, 0xff}, + {54646, 23084, -25639, -53641, 36077, 10774, 0xff}, + {-38912, -8192, -10751, 19719, -57920, -23474, 0xff}, + {-51711, -8192, -21504, 19719, -57920, -23474, 0xff}, + {-34990, 3085, -35283, 19719, -57920, -23474, 0xff}, + {10240, 28672, 42496, -15938, 47664, 42061, 0xff}, + {17110, 21655, 53050, -15938, 47664, 42061, 0xff}, + {22663, 24387, 52059, -15938, 47664, 42061, 0xff}, + {-10240, 28672, 42496, 13598, 50036, 40081, 0xff}, + {-23039, 33792, 40448, 13598, 50036, 40081, 0xff}, + {-22663, 24387, 52059, 13598, 50036, 40081, 0xff}, + {23039, 33792, 40448, 24700, 46779, 38685, 0xff}, + {22663, 24387, 52059, 24700, 46779, 38685, 0xff}, + {28828, 22209, 50756, 24700, 46779, 38685, 0xff}, + {-23039, 33792, 40448, -26234, 46707, 37748, 0xff}, + {-35840, 28672, 37888, -26234, 46707, 37748, 0xff}, + {-28828, 22209, 50756, -26234, 46707, 37748, 0xff}, + {17889, -58077, 42583, 52861, 2195, 38679, 0xff}, + {23886, -61271, 34567, 52861, 2195, 38679, 0xff}, + {20480, -28672, 37375, 52861, 2195, 38679, 0xff}, + {-20480, -28672, 37375, -52861, 2195, 38679, 0xff}, + {-23886, -61271, 34567, -52861, 2195, 38679, 0xff}, + {-17889, -58077, 42583, -52861, 2195, 38679, 0xff}, + {38730, -56, 40521, 22413, -57986, 20748, 0xff}, + {7184, -8347, 51436, 22413, -57986, 20748, 0xff}, + {13735, -11853, 34559, 22413, -57986, 20748, 0xff}, + {-13735, -11853, 34559, -22413, -57986, 20748, 0xff}, + {-7184, -8347, 51436, -22413, -57986, 20748, 0xff}, + {-38730, -56, 40521, -22413, -57986, 20748, 0xff}, + {52680, 10582, 27526, 35631, -34478, 42853, 0xff}, + {55891, 27603, 38552, 35631, -34478, 42853, 0xff}, + {45997, 26631, 45998, 35631, -34478, 42853, 0xff}, + {-45997, 26631, 45998, -35631, -34478, 42853, 0xff}, + {-55891, 27603, 38552, -35631, -34478, 42853, 0xff}, + {-52680, 10582, 27526, -35631, -34478, 42853, 0xff}, + {45997, 26631, 45998, 31968, 32925, 46786, 0xff}, + {55891, 27603, 38552, 31968, 32925, 46786, 0xff}, + {20576, 48728, 47817, 31968, 32925, 46786, 0xff}, + {-45997, 26631, 45998, -34078, 35651, 43162, 0xff}, + {-16522, 42544, 56125, -34078, 35651, 43162, 0xff}, + {-20576, 48728, 47817, -34078, 35651, 43162, 0xff}, + {6655, 28160, 55296, -43207, 23697, 43207, 0xff}, + {10717, 45254, 49982, -43207, 23697, 43207, 0xff}, + {0, 28160, 48640, -43207, 23697, 43207, 0xff}, + {-6655, 28160, 55296, 37840, 37840, 37840, 0xff}, + {0, 23039, 53759, 37840, 37840, 37840, 0xff}, + {0, 28160, 48640, 37840, 37840, 37840, 0xff}, + {37532, 23949, 45101, 3493, -30402, 57953, 0xff}, + {45997, 26631, 45998, 3493, -30402, 57953, 0xff}, + {16522, 42544, 56125, 3493, -30402, 57953, 0xff}, + {-16522, 42544, 56125, -3493, -30402, 57953, 0xff}, + {-45997, 26631, 45998, -3493, -30402, 57953, 0xff}, + {-37532, 23949, 45101, -3493, -30402, 57953, 0xff}, + {35596, 13941, 44774, 12386, -16154, 62291, 0xff}, + {38730, -56, 40521, 12386, -16154, 62291, 0xff}, + {45997, 26631, 45998, 12386, -16154, 62291, 0xff}, + {-45997, 26631, 45998, -12386, -16154, 62291, 0xff}, + {-38730, -56, 40521, -12386, -16154, 62291, 0xff}, + {-35596, 13941, 44774, -12386, -16154, 62291, 0xff}, + {10870, 21498, 51250, 32086, -13428, 55541, 0xff}, + {18675, 32472, 49395, 32086, -13428, 55541, 0xff}, + {6655, 28160, 55296, 32086, -13428, 55541, 0xff}, + {-10870, 21498, 51250, -9201, -29327, 57881, 0xff}, + {0, 23039, 53759, -9201, -29327, 57881, 0xff}, + {-6655, 28160, 55296, -9201, -29327, 57881, 0xff}, + {0, -64120, 39331, 6684, -45114, 47061, 0xff}, + {17889, -58077, 42583, 6684, -45114, 47061, 0xff}, + {5321, -56373, 46002, 6684, -45114, 47061, 0xff}, + {-5321, -56373, 46002, -6684, -45114, 47061, 0xff}, + {-17889, -58077, 42583, -6684, -45114, 47061, 0xff}, + {0, -64120, 39331, -6684, -45114, 47061, 0xff}, + {6576, -48050, 48049, 11744, -1009, 64467, 0xff}, + {9270, -15610, 48065, 11744, -1009, 64467, 0xff}, + {0, -22071, 49653, 11744, -1009, 64467, 0xff}, + {0, -22071, 49653, -11744, -1009, 64467, 0xff}, + {-9270, -15610, 48065, -11744, -1009, 64467, 0xff}, + {-6576, -48050, 48049, -11744, -1009, 64467, 0xff}, + {3406, -8432, 52239, 10806, 18277, 61997, 0xff}, + {0, -13312, 54272, 10806, 18277, 61997, 0xff}, + {8547, -14728, 53199, 10806, 18277, 61997, 0xff}, + {-3406, -8432, 52239, -12582, 19614, 61256, 0xff}, + {-7184, -8347, 51436, -12582, 19614, 61256, 0xff}, + {-8547, -14728, 53199, -12582, 19614, 61256, 0xff}, + {6576, -48050, 48049, 21882, -61027, 9581, 0xff}, + {0, -50426, 47939, 21882, -61027, 9581, 0xff}, + {0, -51200, 43008, 21882, -61027, 9581, 0xff}, + {0, -51200, 43008, -21882, -61027, 9581, 0xff}, + {0, -50426, 47939, -21882, -61027, 9581, 0xff}, + {-6576, -48050, 48049, -21882, -61027, 9581, 0xff}, + {24499, 5671, 47725, 1782, -36693, 54270, 0xff}, + {12284, 9600, 50782, 1782, -36693, 54270, 0xff}, + {12499, 6571, 48727, 1782, -36693, 54270, 0xff}, + {-12499, 6571, 48727, -1776, -36693, 54270, 0xff}, + {-12284, 9600, 50782, -1776, -36693, 54270, 0xff}, + {-24499, 5671, 47725, -1776, -36693, 54270, 0xff}, + {12799, 19456, 49663, 43601, 3257, 48817, 0xff}, + {10870, 21498, 51250, 43601, 3257, 48817, 0xff}, + {12284, 9600, 50782, 43601, 3257, 48817, 0xff}, + {-12799, 19456, 49663, -59683, -52, 27066, 0xff}, + {-13098, 11318, 48991, -59683, -52, 27066, 0xff}, + {-12284, 9600, 50782, -59683, -52, 27066, 0xff}, + {7168, 30208, 39936, -28429, 58248, -9705, 0xff}, + {0, 26624, 39423, -28429, 58248, -9705, 0xff}, + {0, 28160, 48640, -28429, 58248, -9705, 0xff}, + {0, 28160, 48640, 28429, 58248, -9705, 0xff}, + {0, 26624, 39423, 28429, 58248, -9705, 0xff}, + {-7168, 30208, 39936, 28429, 58248, -9705, 0xff}, + {29979, 34639, 31110, 23291, 52658, -31299, 0xff}, + {20576, 48728, 47817, 23291, 52658, -31299, 0xff}, + {55891, 27603, 38552, 23291, 52658, -31299, 0xff}, + {-29979, 34639, 31110, -20951, 59926, -16285, 0xff}, + {-48630, 26065, 23550, -20951, 59926, -16285, 0xff}, + {-55891, 27603, 38552, -20951, 59926, -16285, 0xff}, + {0, -52736, 22528, 20335, -8749, -61682, 0xff}, + {0, -31857, 19566, 20335, -8749, -61682, 0xff}, + {16045, -30052, 24599, 20335, -8749, -61682, 0xff}, + {-16045, -30052, 24599, -20335, -8749, -61682, 0xff}, + {0, -31857, 19566, -20335, -8749, -61682, 0xff}, + {0, -52736, 22528, -20335, -8749, -61682, 0xff}, + {0, -63999, 30208, 9968, -62966, -15197, 0xff}, + {21330, -59803, 26806, 9968, -62966, -15197, 0xff}, + {23886, -61271, 34567, 9968, -62966, -15197, 0xff}, + {-23886, -61271, 34567, -9968, -62966, -15197, 0xff}, + {-21330, -59803, 26806, -9968, -62966, -15197, 0xff}, + {0, -63999, 30208, -9968, -62966, -15197, 0xff}, + {20480, -28672, 37375, 59585, 15623, -22367, 0xff}, + {16045, -30052, 24599, 59585, 15623, -22367, 0xff}, + {14336, -18432, 28160, 59585, 15623, -22367, 0xff}, + {-14336, -18432, 28160, -59585, 15623, -22367, 0xff}, + {-16045, -30052, 24599, -59585, 15623, -22367, 0xff}, + {-20480, -28672, 37375, -59585, 15623, -22367, 0xff}, + {0, 4607, -54272, 27643, -26699, -53084, 0xff}, + {34990, 3085, -35283, 27643, -26699, -53084, 0xff}, + {22528, -9728, -35327, 27643, -26699, -53084, 0xff}, + {-22528, -9728, -35327, -27643, -26699, -53084, 0xff}, + {-34990, 3085, -35283, -27643, -26699, -53084, 0xff}, + {0, 4607, -54272, -27643, -26699, -53084, 0xff}, + {0, -25087, -23039, 19569, -53975, -31594, 0xff}, + {0, -12799, -44032, 19569, -53975, -31594, 0xff}, + {22528, -9728, -35327, 19569, -53975, -31594, 0xff}, + {0, -25087, -23039, -21384, -54670, -29137, 0xff}, + {-19456, -20480, -17408, -21384, -54670, -29137, 0xff}, + {-22528, -9728, -35327, -21384, -54670, -29137, 0xff}, + {11434, -27191, 17172, 22747, -60699, -9640, 0xff}, + {0, -31857, 19566, 22747, -60699, -9640, 0xff}, + {0, -25087, -23039, 22747, -60699, -9640, 0xff}, + {0, -25087, -23039, -22747, -60699, -9640, 0xff}, + {0, -31857, 19566, -22747, -60699, -9640, 0xff}, + {-11434, -27191, 17172, -22747, -60699, -9640, 0xff}, + {47823, -2804, 3726, 60358, -25447, 1992, 0xff}, + {56241, 17046, 2221, 60358, -25447, 1992, 0xff}, + {52680, 10582, 27526, 60358, -25447, 1992, 0xff}, + {-52680, 10582, 27526, -60358, -25447, 1992, 0xff}, + {-56241, 17046, 2221, -60358, -25447, 1992, 0xff}, + {-47823, -2804, 3726, -60358, -25447, 1992, 0xff}, + {0, 4607, -54272, 18415, -2988, -62822, 0xff}, + {0, 36864, -55807, 18415, -2988, -62822, 0xff}, + {30128, 26936, -46502, 18415, -2988, -62822, 0xff}, + {0, 4607, -54272, -29084, -20034, -55200, 0xff}, + {-34990, 3085, -35283, -29084, -20034, -55200, 0xff}, + {-30128, 26936, -46502, -29084, -20034, -55200, 0xff}, + {0, 64512, -5120, 8336, 63294, 14811, 0xff}, + {0, 58880, 18943, 8336, 63294, 14811, 0xff}, + {29696, 55807, 15360, 8336, 63294, 14811, 0xff}, + {0, 64512, -5120, -7333, 63084, 16174, 0xff}, + {-29696, 60928, -4607, -7333, 63084, 16174, 0xff}, + {-29696, 55807, 15360, -7333, 63084, 16174, 0xff}, + {29696, 56832, -25087, 8650, 63897, -11717, 0xff}, + {0, 58880, -35840, 8650, 63897, -11717, 0xff}, + {0, 64512, -5120, 8650, 63897, -11717, 0xff}, + {0, 64512, -5120, -8650, 63897, -11717, 0xff}, + {0, 58880, -35840, -8650, 63897, -11717, 0xff}, + {-29696, 56832, -25087, -8650, 63897, -11717, 0xff}, + {30128, 26936, -46502, 26902, 40147, -44263, 0xff}, + {0, 36864, -55807, 26902, 40147, -44263, 0xff}, + {0, 58880, -35840, 26902, 40147, -44263, 0xff}, + {0, 58880, -35840, -26902, 40147, -44263, 0xff}, + {0, 36864, -55807, -26902, 40147, -44263, 0xff}, + {-30128, 26936, -46502, -26902, 40147, -44263, 0xff}, + {51586, 40861, -9829, 43345, 47566, -12399, 0xff}, + {50190, 37864, -26209, 43345, 47566, -12399, 0xff}, + {29696, 56832, -25087, 43345, 47566, -12399, 0xff}, + {-29696, 56832, -25087, -43345, 47566, -12399, 0xff}, + {-50190, 37864, -26209, -43345, 47566, -12399, 0xff}, + {-51586, 40861, -9829, -43345, 47566, -12399, 0xff}, + {51216, 37752, 6281, 45049, 46537, 10013, 0xff}, + {51586, 40861, -9829, 45049, 46537, 10013, 0xff}, + {29696, 60928, -4607, 45049, 46537, 10013, 0xff}, + {-29696, 60928, -4607, -45049, 46537, 10013, 0xff}, + {-51586, 40861, -9829, -45049, 46537, 10013, 0xff}, + {-51216, 37752, 6281, -45049, 46537, 10013, 0xff}, + {41471, 29696, 18432, 39334, 23265, 46969, 0xff}, + {51216, 37752, 6281, 39334, 23265, 46969, 0xff}, + {29696, 55807, 15360, 39334, 23265, 46969, 0xff}, + {-29696, 55807, 15360, -39334, 23265, 46969, 0xff}, + {-51216, 37752, 6281, -39334, 23265, 46969, 0xff}, + {-41471, 29696, 18432, -39334, 23265, 46969, 0xff}, + {0, 58880, 18943, 13965, 41667, 48614, 0xff}, + {0, 37375, 37375, 13965, 41667, 48614, 0xff}, + {29979, 34639, 31110, 13965, 41667, 48614, 0xff}, + {0, 58880, 18943, -10262, 38725, 51865, 0xff}, + {-29696, 55807, 15360, -10262, 38725, 51865, 0xff}, + {-29979, 34639, 31110, -10262, 38725, 51865, 0xff}, + {51586, 40861, -9829, 63740, 14627, 4286, 0xff}, + {51216, 37752, 6281, 63740, 14627, 4286, 0xff}, + {56241, 17046, 2221, 63740, 14627, 4286, 0xff}, + {-56241, 17046, 2221, -63740, 14627, 4286, 0xff}, + {-51216, 37752, 6281, -63740, 14627, 4286, 0xff}, + {-51586, 40861, -9829, -63740, 14627, 4286, 0xff}, + {54646, 23084, -25639, 62285, 18441, -8683, 0xff}, + {50190, 37864, -26209, 62285, 18441, -8683, 0xff}, + {51586, 40861, -9829, 62285, 18441, -8683, 0xff}, + {-51586, 40861, -9829, -62285, 18441, -8683, 0xff}, + {-50190, 37864, -26209, -62285, 18441, -8683, 0xff}, + {-54646, 23084, -25639, -62285, 18441, -8683, 0xff}, + {14336, -18432, 28160, 38902, -52101, 8159, 0xff}, + {29162, -13292, -9698, 38902, -52101, 8159, 0xff}, + {34586, -3098, 29517, 38902, -52101, 8159, 0xff}, + {-34586, -3098, 29517, -38902, -52101, 8159, 0xff}, + {-29162, -13292, -9698, -38902, -52101, 8159, 0xff}, + {-14336, -18432, 28160, -38902, -52101, 8159, 0xff}, + {29162, -13292, -9698, 46084, -43017, -17910, 0xff}, + {19456, -20480, -17408, 46084, -43017, -17910, 0xff}, + {22528, -9728, -35327, 46084, -43017, -17910, 0xff}, + {-29162, -13292, -9698, -45239, -43941, -17819, 0xff}, + {-34990, 3085, -35283, -45239, -43941, -17819, 0xff}, + {-22528, -9728, -35327, -45239, -43941, -17819, 0xff}, + {83968, 3584, -28160, 4856, 2444, 65313, 0xff}, + {89343, 20376, -29188, 4856, 2444, 65313, 0xff}, + {80904, 16297, -28407, 4856, 2444, 65313, 0xff}, + {-83968, 3584, -28160, 4607, 163, 65372, 0xff}, + {-77984, 6266, -28588, 4607, 163, 65372, 0xff}, + {-80904, 16297, -28407, 4607, 163, 65372, 0xff}, + {64283, 24671, -16941, 26889, -49990, 32754, 0xff}, + {63071, 20046, -23006, 26889, -49990, 32754, 0xff}, + {76699, 22655, -30212, 26889, -49990, 32754, 0xff}, + {-76699, 22655, -30212, -26889, -49990, 32754, 0xff}, + {-63071, 20046, -23006, -26889, -49990, 32754, 0xff}, + {-64283, 24671, -16941, -26889, -49990, 32754, 0xff}, + {46721, -944, -11257, -11993, 17255, 62075, 0xff}, + {38912, -8192, -10751, -11993, 17255, 62075, 0xff}, + {50688, -9216, -8192, -11993, 17255, 62075, 0xff}, + {-46721, -944, -11257, 6402, 19942, 62095, 0xff}, + {-55385, -3250, -9623, 6402, 19942, 62095, 0xff}, + {-50688, -9216, -8192, 6402, 19942, 62095, 0xff}, + {56241, 17046, 2221, 59716, -25899, -7608, 0xff}, + {47823, -2804, 3726, 59716, -25899, -7608, 0xff}, + {46721, -944, -11257, 59716, -25899, -7608, 0xff}, + {-46721, -944, -11257, -59716, -25899, -7608, 0xff}, + {-47823, -2804, 3726, -59716, -25899, -7608, 0xff}, + {-56241, 17046, 2221, -59716, -25899, -7608, 0xff}, + {67766, 376, -26353, 18009, -7503, 62567, 0xff}, + {77984, 6266, -28588, 18009, -7503, 62567, 0xff}, + {72755, 15982, -25917, 18009, -7503, 62567, 0xff}, + {-67766, 376, -26353, -30133, -11226, 57101, 0xff}, + {-55861, -126, -20169, -30133, -11226, 57101, 0xff}, + {-72755, 15982, -25917, -30133, -11226, 57101, 0xff}, + {51711, -8192, -21504, 12392, -64251, 3584, 0xff}, + {68095, -5632, -32256, 12392, -64251, 3584, 0xff}, + {68018, -4978, -20287, 12392, -64251, 3584, 0xff}, + {-68018, -4978, -20287, -12392, -64251, 3584, 0xff}, + {-68095, -5632, -32256, -12392, -64251, 3584, 0xff}, + {-51711, -8192, -21504, -12392, -64251, 3584, 0xff}, + {68095, -5632, -32256, 30723, -57114, 9450, 0xff}, + {86016, 3584, -34816, 30723, -57114, 9450, 0xff}, + {83968, 3584, -28160, 30723, -57114, 9450, 0xff}, + {-83968, 3584, -28160, -30723, -57114, 9450, 0xff}, + {-86016, 3584, -34816, -30723, -57114, 9450, 0xff}, + {-68095, -5632, -32256, -30723, -57114, 9450, 0xff}, + {54646, 23084, -25639, -25454, 1985, -60358, 0xff}, + {80412, 31511, -36230, -25454, 1985, -60358, 0xff}, + {68095, -5632, -32256, -25454, 1985, -60358, 0xff}, + {-54646, 23084, -25639, 35461, -3945, -54971, 0xff}, + {-51711, -8192, -21504, 35461, -3945, -54971, 0xff}, + {-68095, -5632, -32256, 35461, -3945, -54971, 0xff}, + {51711, -8192, -21504, -4502, -65162, -5360, 0xff}, + {50688, -9216, -8192, -4502, -65162, -5360, 0xff}, + {38912, -8192, -10751, -4502, -65162, -5360, 0xff}, + {-38912, -8192, -10751, 4502, -65162, -5360, 0xff}, + {-50688, -9216, -8192, 4502, -65162, -5360, 0xff}, + {-51711, -8192, -21504, 4502, -65162, -5360, 0xff} +}; #endif /* MESHDATA_H_ */ diff --git a/tools/meshdump/Makefile b/tools/meshdump/Makefile new file mode 100644 index 0000000..880ae96 --- /dev/null +++ b/tools/meshdump/Makefile @@ -0,0 +1,13 @@ +src = $(wildcard *.c) +obj = $(src:.c=.o) +bin = meshdump + +CFLAGS = -pedantic -Wall -g -DNO_OPENGL +LDFLAGS = -lm + +$(bin): $(obj) + $(CC) -o $@ $(obj) $(LDFLAGS) + +.PHONY: clean +clean: + rm -f $(obj) $(bin) diff --git a/tools/meshdump/cmesh.c b/tools/meshdump/cmesh.c new file mode 100644 index 0000000..483b1f9 --- /dev/null +++ b/tools/meshdump/cmesh.c @@ -0,0 +1,1638 @@ +#include +#include +#include +#include +#include +#include "cmesh.h" + +#ifndef NO_OPENGL +#include "opengl.h" +#endif + + +struct cmesh_vattrib { + int nelem; /* num elements per attribute [1, 4] */ + float *data; + unsigned int count; + unsigned int vbo; + int vbo_valid, data_valid; +}; + +/* istart,icount are valid only when the mesh is indexed, otherwise icount is 0. + * vstart,vcount are define the submesh for non-indexed meshes. + * For indexed meshes, vstart,vcount denote the range of vertices used by each + * submesh. + */ +struct submesh { + char *name; + int nfaces; /* derived from either icount or vcount */ + int istart, icount; + int vstart, vcount; + struct submesh *next; +}; + +struct cmesh { + char *name; + unsigned int nverts, nfaces; + + struct submesh *sublist; + int subcount; + + /* current value for each attribute for the immediate mode interface */ + cgm_vec4 cur_val[CMESH_NUM_ATTR]; + + unsigned int buffer_objects[CMESH_NUM_ATTR + 1]; + struct cmesh_vattrib vattr[CMESH_NUM_ATTR]; + + unsigned int *idata; + unsigned int icount; + unsigned int ibo; + int ibo_valid, idata_valid; + + /* index buffer for wireframe rendering (constructed on demand) */ + unsigned int wire_ibo; + int wire_ibo_valid; + + /* axis-aligned bounding box */ + cgm_vec3 aabb_min, aabb_max; + int aabb_valid; + /* bounding sphere */ + cgm_vec3 bsph_center; + float bsph_radius; + int bsph_valid; +}; + + +static int clone(struct cmesh *cmdest, struct cmesh *cmsrc, struct submesh *sub); +static int pre_draw(struct cmesh *cm); +static void post_draw(struct cmesh *cm, int cur_sdr); +static void update_buffers(struct cmesh *cm); +static void update_wire_ibo(struct cmesh *cm); +static void calc_aabb(struct cmesh *cm); +static void calc_bsph(struct cmesh *cm); + +static int def_nelem[CMESH_NUM_ATTR] = {3, 3, 3, 2, 4, 4, 4, 2}; + +static int sdr_loc[CMESH_NUM_ATTR] = {0, 1, 2, 3, 4, 5, 6, 7}; +static int use_custom_sdr_attr; + + +/* global state */ +void cmesh_set_attrib_sdrloc(int attr, int loc) +{ + sdr_loc[attr] = loc; +} + +int cmesh_get_attrib_sdrloc(int attr) +{ + return sdr_loc[attr]; +} + +void cmesh_clear_attrib_sdrloc(void) +{ + int i; + for(i=0; icur_val + CMESH_ATTR_COLOR, 1, 1, 1, 1); + +#ifndef NO_OPENGL + glGenBuffers(CMESH_NUM_ATTR + 1, cm->buffer_objects); + + for(i=0; ivattr[i].vbo = cm->buffer_objects[i]; + } + + cm->ibo = cm->buffer_objects[CMESH_NUM_ATTR]; +#endif + return 0; +} + +void cmesh_destroy(struct cmesh *cm) +{ + int i; + + free(cm->name); + + for(i=0; ivattr[i].data); + } + free(cm->idata); + + cmesh_clear_submeshes(cm); + +#ifndef NO_OPENGL + glDeleteBuffers(CMESH_NUM_ATTR + 1, cm->buffer_objects); + if(cm->wire_ibo) { + glDeleteBuffers(1, &cm->wire_ibo); + } +#endif +} + +void cmesh_clear(struct cmesh *cm) +{ + int i; + + for(i=0; ivattr[i].nelem = 0; + cm->vattr[i].vbo_valid = 0; + cm->vattr[i].data_valid = 0; + free(cm->vattr[i].data); + cm->vattr[i].data = 0; + cm->vattr[i].count = 0; + } + cm->ibo_valid = cm->idata_valid = 0; + free(cm->idata); + cm->idata = 0; + cm->icount = 0; + + cm->wire_ibo_valid = 0; + cm->nverts = cm->nfaces = 0; + + cm->bsph_valid = cm->aabb_valid = 0; + + cmesh_clear_submeshes(cm); +} + +int cmesh_clone(struct cmesh *cmdest, struct cmesh *cmsrc) +{ + return clone(cmdest, cmsrc, 0); +} + +static int clone(struct cmesh *cmdest, struct cmesh *cmsrc, struct submesh *sub) +{ + int i, nelem, vstart, vcount, istart, icount; + char *srcname, *name = 0; + float *varr[CMESH_NUM_ATTR] = {0}; + float *vptr; + unsigned int *iptr, *iarr = 0; + + /* try do anything that can fail first, before making any changes to cmdest + * so we have the option of recovering gracefuly + */ + + srcname = sub ? sub->name : cmsrc->name; + if(srcname) { + if(!(name = malloc(strlen(srcname) + 1))) { + return -1; + } + strcpy(name, srcname); + } + + if(sub) { + vstart = sub->vstart; + vcount = sub->vcount; + istart = sub->istart; + icount = sub->icount; + } else { + vstart = istart = 0; + vcount = cmsrc->nverts; + icount = cmsrc->icount; + } + + if(cmesh_indexed(cmsrc)) { + if(!(iarr = malloc(icount * sizeof *iarr))) { + free(name); + return -1; + } + } + + for(i=0; ivattr[i].nelem; + if(!(varr[i] = malloc(vcount * nelem * sizeof(float)))) { + while(--i >= 0) { + free(varr[i]); + } + free(iarr); + free(name); + return -1; + } + } + } + + /* from this point forward nothing can fail */ + cmesh_clear(cmdest); + + for(i=0; ivattr[i].data); + + if(cmesh_has_attrib(cmsrc, i)) { + cmesh_attrib(cmsrc, i); /* force validation of the actual data on the source mesh */ + + nelem = cmsrc->vattr[i].nelem; + cmdest->vattr[i].nelem = nelem; + cmdest->vattr[i].data = varr[i]; + cmdest->vattr[i].count = vcount; + vptr = cmsrc->vattr[i].data + vstart * nelem; + memcpy(cmdest->vattr[i].data, vptr, vcount * nelem * sizeof(float)); + cmdest->vattr[i].data_valid = 1; + cmdest->vattr[i].vbo_valid = 0; + } else { + memset(cmdest->vattr + i, 0, sizeof cmdest->vattr[i]); + } + } + + if(cmesh_indexed(cmsrc)) { + cmesh_index(cmsrc); /* force validation .... */ + + cmdest->idata = iarr; + cmdest->icount = icount; + if(sub) { + /* need to offset all vertex indices by -vstart */ + iptr = cmsrc->idata + istart; + for(i=0; iidata[i] = *iptr++ - vstart; + } + } else { + memcpy(cmdest->idata, cmsrc->idata + istart, icount * sizeof *cmdest->idata); + } + cmdest->idata_valid = 1; + } else { + cmdest->idata = 0; + cmdest->idata_valid = cmdest->ibo_valid = 0; + } + + free(cmdest->name); + cmdest->name = name; + + cmdest->nverts = cmsrc->nverts; + cmdest->nfaces = sub ? sub->nfaces : cmsrc->nfaces; + + memcpy(cmdest->cur_val, cmsrc->cur_val, sizeof cmdest->cur_val); + + cmdest->aabb_min = cmsrc->aabb_min; + cmdest->aabb_max = cmsrc->aabb_max; + cmdest->aabb_valid = cmsrc->aabb_valid; + cmdest->bsph_center = cmsrc->bsph_center; + cmdest->bsph_radius = cmsrc->bsph_radius; + cmdest->bsph_valid = cmsrc->bsph_valid; + + /* copy sublist only if we're not cloning a submesh */ + if(!sub) { + struct submesh *sm, *n, *head = 0, *tail = 0; + + sm = cmsrc->sublist; + while(sm) { + if(!(n = malloc(sizeof *n)) || !(name = malloc(strlen(sm->name) + 1))) { + free(n); + sm = sm->next; + continue; + } + strcpy(name, sm->name); + *n = *sm; + n->name = name; + n->next = 0; + + if(head) { + tail->next = n; + tail = n; + } else { + head = tail = n; + } + + sm = sm->next; + } + + cmdest->sublist = head; + cmdest->subcount = cmsrc->subcount; + } + + return 0; +} + +int cmesh_set_name(struct cmesh *cm, const char *name) +{ + int len = strlen(name); + char *tmp = malloc(len + 1); + if(!tmp) return -1; + free(cm->name); + cm->name = tmp; + memcpy(cm->name, name, len + 1); + return 0; +} + +const char *cmesh_name(struct cmesh *cm) +{ + return cm->name; +} + +int cmesh_has_attrib(struct cmesh *cm, int attr) +{ + if(attr < 0 || attr >= CMESH_NUM_ATTR) { + return 0; + } + return cm->vattr[attr].vbo_valid | cm->vattr[attr].data_valid; +} + +int cmesh_indexed(struct cmesh *cm) +{ + return cm->ibo_valid | cm->idata_valid; +} + +/* vdata can be 0, in which case only memory is allocated + * returns pointer to the attribute array + */ +float *cmesh_set_attrib(struct cmesh *cm, int attr, int nelem, unsigned int num, + const float *vdata) +{ + float *newarr; + + if(attr < 0 || attr >= CMESH_NUM_ATTR) { + return 0; + } + if(cm->nverts && num != cm->nverts) { + return 0; + } + + if(!(newarr = malloc(num * nelem * sizeof *newarr))) { + return 0; + } + if(vdata) { + memcpy(newarr, vdata, num * nelem * sizeof *newarr); + } + + cm->nverts = num; + + free(cm->vattr[attr].data); + cm->vattr[attr].data = newarr; + cm->vattr[attr].count = num * nelem; + cm->vattr[attr].nelem = nelem; + cm->vattr[attr].data_valid = 1; + cm->vattr[attr].vbo_valid = 0; + return newarr; +} + +float *cmesh_attrib(struct cmesh *cm, int attr) +{ + if(attr < 0 || attr >= CMESH_NUM_ATTR) { + return 0; + } + cm->vattr[attr].vbo_valid = 0; + return (float*)cmesh_attrib_ro(cm, attr); +} + +const float *cmesh_attrib_ro(struct cmesh *cm, int attr) +{ + void *tmp; + int nelem; + + if(attr < 0 || attr >= CMESH_NUM_ATTR) { + return 0; + } + + if(!cm->vattr[attr].data_valid) { +#if defined(GL_ES_VERSION_2_0) || defined(NO_OPENGL) + return 0; +#else + if(!cm->vattr[attr].vbo_valid) { + return 0; + } + + /* local data copy unavailable, grab the data from the vbo */ + nelem = cm->vattr[attr].nelem; + if(!(cm->vattr[attr].data = malloc(cm->nverts * nelem * sizeof(float)))) { + return 0; + } + cm->vattr[attr].count = cm->nverts * nelem; + + glBindBuffer(GL_ARRAY_BUFFER, cm->vattr[attr].vbo); + tmp = glMapBuffer(GL_ARRAY_BUFFER, GL_READ_ONLY); + memcpy(cm->vattr[attr].data, tmp, cm->nverts * nelem * sizeof(float)); + glUnmapBuffer(GL_ARRAY_BUFFER); + + cm->vattr[attr].data_valid = 1; +#endif + } + return cm->vattr[attr].data; +} + +float *cmesh_attrib_at(struct cmesh *cm, int attr, int idx) +{ + float *vptr = cmesh_attrib(cm, attr); + return vptr ? vptr + idx * cm->vattr[attr].nelem : 0; +} + +const float *cmesh_attrib_at_ro(struct cmesh *cm, int attr, int idx) +{ + const float *vptr = cmesh_attrib_ro(cm, attr); + return vptr ? vptr + idx * cm->vattr[attr].nelem : 0; +} + +int cmesh_attrib_count(struct cmesh *cm, int attr) +{ + return cmesh_has_attrib(cm, attr) ? cm->nverts : 0; +} + +int cmesh_push_attrib(struct cmesh *cm, int attr, float *v) +{ + float *vptr; + int i, cursz, newsz; + + if(!cm->vattr[attr].nelem) { + cm->vattr[attr].nelem = def_nelem[attr]; + } + + cursz = cm->vattr[attr].count; + newsz = cursz + cm->vattr[attr].nelem; + if(!(vptr = realloc(cm->vattr[attr].data, newsz * sizeof(float)))) { + return -1; + } + cm->vattr[attr].data = vptr; + cm->vattr[attr].count = newsz; + vptr += cursz; + + for(i=0; ivattr[attr].nelem; i++) { + *vptr++ = *v++; + } + cm->vattr[attr].data_valid = 1; + cm->vattr[attr].vbo_valid = 0; + + if(attr == CMESH_ATTR_VERTEX) { + cm->nverts = newsz / cm->vattr[attr].nelem; + } + return 0; +} + +int cmesh_push_attrib1f(struct cmesh *cm, int attr, float x) +{ + float v[4]; + v[0] = x; + v[1] = v[2] = 0.0f; + v[3] = 1.0f; + return cmesh_push_attrib(cm, attr, v); +} + +int cmesh_push_attrib2f(struct cmesh *cm, int attr, float x, float y) +{ + float v[4]; + v[0] = x; + v[1] = y; + v[2] = 0.0f; + v[3] = 1.0f; + return cmesh_push_attrib(cm, attr, v); +} + +int cmesh_push_attrib3f(struct cmesh *cm, int attr, float x, float y, float z) +{ + float v[4]; + v[0] = x; + v[1] = y; + v[2] = z; + v[3] = 1.0f; + return cmesh_push_attrib(cm, attr, v); +} + +int cmesh_push_attrib4f(struct cmesh *cm, int attr, float x, float y, float z, float w) +{ + float v[4]; + v[0] = x; + v[1] = y; + v[2] = z; + v[3] = w; + return cmesh_push_attrib(cm, attr, v); +} + +/* indices can be 0, in which case only memory is allocated + * returns pointer to the index array + */ +unsigned int *cmesh_set_index(struct cmesh *cm, int num, const unsigned int *indices) +{ + unsigned int *tmp; + int nidx = cm->nfaces * 3; + + if(nidx && num != nidx) { + return 0; + } + + if(!(tmp = malloc(num * sizeof *tmp))) { + return 0; + } + if(indices) { + memcpy(tmp, indices, num * sizeof *tmp); + } + + free(cm->idata); + cm->idata = tmp; + cm->icount = num; + cm->idata_valid = 1; + cm->ibo_valid = 0; + return tmp; +} + +unsigned int *cmesh_index(struct cmesh *cm) +{ + cm->ibo_valid = 0; + return (unsigned int*)cmesh_index_ro(cm); +} + +const unsigned int *cmesh_index_ro(struct cmesh *cm) +{ + int nidx; + unsigned int *tmp; + + if(!cm->idata_valid) { +#if defined(GL_ES_VERSION_2_0) || defined(NO_OPENGL) + return 0; +#else + if(!cm->ibo_valid) { + return 0; + } + + /* local copy is unavailable, grab the data from the ibo */ + nidx = cm->nfaces * 3; + if(!(tmp = malloc(nidx * sizeof *cm->idata))) { + return 0; + } + free(cm->idata); + cm->idata = tmp; + cm->icount = nidx; + + glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, cm->ibo); + tmp = glMapBuffer(GL_ELEMENT_ARRAY_BUFFER, GL_READ_ONLY); + memcpy(cm->idata, tmp, nidx * sizeof *cm->idata); + glUnmapBuffer(GL_ELEMENT_ARRAY_BUFFER); + + cm->idata_valid = 1; +#endif + } + return cm->idata; +} + +int cmesh_index_count(struct cmesh *cm) +{ + return cm->nfaces * 3; +} + +int cmesh_push_index(struct cmesh *cm, unsigned int idx) +{ + unsigned int *iptr; + unsigned int cur_sz = cm->icount; + if(!(iptr = realloc(cm->idata, (cur_sz + 1) * sizeof *iptr))) { + return -1; + } + iptr[cur_sz] = idx; + cm->idata = iptr; + cm->icount = cur_sz + 1; + cm->idata_valid = 1; + cm->ibo_valid = 0; + + cm->nfaces = cm->icount / 3; + return 0; +} + +int cmesh_poly_count(struct cmesh *cm) +{ + if(cm->nfaces) { + return cm->nfaces; + } + if(cm->nverts) { + return cm->nverts / 3; + } + return 0; +} + +/* attr can be -1 to invalidate all attributes */ +void cmesh_invalidate_vbo(struct cmesh *cm, int attr) +{ + int i; + + if(attr >= CMESH_NUM_ATTR) { + return; + } + + if(attr < 0) { + for(i=0; ivattr[i].vbo_valid = 0; + } + } else { + cm->vattr[attr].vbo_valid = 0; + } +} + +void cmesh_invalidate_index(struct cmesh *cm) +{ + cm->ibo_valid = 0; +} + +int cmesh_append(struct cmesh *cmdest, struct cmesh *cmsrc) +{ + int i, nelem, newsz, origsz, srcsz; + float *vptr; + unsigned int *iptr; + unsigned int idxoffs; + + if(!cmdest->nverts) { + return cmesh_clone(cmdest, cmsrc); + } + + for(i=0; ivattr[i].nelem == cmsrc->vattr[i].nelem); + nelem = cmdest->vattr[i].nelem; + origsz = cmdest->nverts * nelem; + newsz = cmdest->nverts + cmsrc->nverts * nelem; + + if(!(vptr = realloc(cmdest->vattr[i].data, newsz * sizeof *vptr))) { + return -1; + } + memcpy(vptr + origsz, cmsrc->vattr[i].data, cmsrc->nverts * nelem * sizeof(float)); + cmdest->vattr[i].data = vptr; + cmdest->vattr[i].count = newsz; + } + } + + if(cmesh_indexed(cmdest)) { + assert(cmesh_indexed(cmsrc)); + /* force validation ... */ + cmesh_index(cmdest); + cmesh_index_ro(cmsrc); + + idxoffs = cmdest->nverts; + origsz = cmdest->icount; + srcsz = cmsrc->icount; + newsz = origsz + srcsz; + + if(!(iptr = realloc(cmdest->idata, newsz * sizeof *iptr))) { + return -1; + } + cmdest->idata = iptr; + cmdest->icount = newsz; + + /* copy and fixup all the new indices */ + iptr += origsz; + for(i=0; iidata[i] + idxoffs; + } + } + + cmdest->wire_ibo_valid = 0; + cmdest->aabb_valid = 0; + cmdest->bsph_valid = 0; + return 0; +} + +void cmesh_clear_submeshes(struct cmesh *cm) +{ + struct submesh *sm; + + while(cm->sublist) { + sm = cm->sublist; + cm->sublist = cm->sublist->next; + free(sm->name); + free(sm); + } + cm->subcount = 0; +} + +int cmesh_submesh(struct cmesh *cm, const char *name, int fstart, int fcount) +{ + int i; + unsigned int minv = UINT_MAX, maxv = 0; + unsigned int *iptr; + struct submesh *sm; + + if(fstart < 0 || fcount < 1 || fstart + fcount > cm->nfaces) { + return -1; + } + + if(!(sm = malloc(sizeof *sm)) || !(sm->name = malloc(strlen(name) + 1))) { + free(sm); + return -1; + } + strcpy(sm->name, name); + sm->nfaces = fcount; + + if(cmesh_indexed(cm)) { + sm->istart = fstart * 3; + sm->icount = fcount * 3; + + /* find out which vertices are used by this submesh */ + iptr = cm->idata + sm->istart; + for(i=0; iicount; i++) { + unsigned int vidx = *iptr++; + if(vidx < minv) minv = vidx; + if(vidx > maxv) maxv = vidx; + } + sm->vstart = minv; + sm->vcount = maxv - minv + 1; + } else { + sm->istart = sm->icount = 0; + sm->vstart = fstart * 3; + sm->vcount = fcount * 3; + } + + sm->next = cm->sublist; + cm->sublist = sm; + cm->subcount++; + return 0; +} + +int cmesh_remove_submesh(struct cmesh *cm, int idx) +{ + struct submesh dummy; + struct submesh *prev, *sm; + + if(idx >= cm->subcount) { + return -1; + } + + dummy.next = cm->sublist; + prev = &dummy; + + while(prev->next && idx-- > 0) { + prev = prev->next; + } + + if(!(sm = prev->next)) return -1; + + prev->next = sm->next; + free(sm->name); + free(sm); + + cm->subcount--; + assert(cm->subcount >= 0); + + cm->sublist = dummy.next; + return 0; +} + +int cmesh_find_submesh(struct cmesh *cm, const char *name) +{ + int idx = 0; + struct submesh *sm = cm->sublist; + while(sm) { + if(strcmp(sm->name, name) == 0) { + assert(idx <= cm->subcount); + return idx; + } + idx++; + sm = sm->next; + } + return -1; +} + +int cmesh_submesh_count(struct cmesh *cm) +{ + return cm->subcount; +} + +static struct submesh *get_submesh(struct cmesh *m, int idx) +{ + struct submesh *sm = m->sublist; + while(sm && --idx >= 0) { + sm = sm->next; + } + return sm; +} + +int cmesh_clone_submesh(struct cmesh *cmdest, struct cmesh *cm, int subidx) +{ + struct submesh *sub; + + if(!(sub = get_submesh(cm, subidx))) { + return -1; + } + return clone(cmdest, cm, sub); +} + + +/* assemble a complete vertex by adding all the useful attributes */ +int cmesh_vertex(struct cmesh *cm, float x, float y, float z) +{ + int i, j; + + cgm_wcons(cm->cur_val + CMESH_ATTR_VERTEX, x, y, z, 1.0f); + cm->vattr[CMESH_ATTR_VERTEX].data_valid = 1; + cm->vattr[CMESH_ATTR_VERTEX].nelem = 3; + + for(i=0; ivattr[i].data_valid) { + int newsz = cm->vattr[i].count + cm->vattr[i].nelem; + float *tmp = realloc(cm->vattr[i].data, newsz * sizeof *tmp); + if(!tmp) return -1; + tmp += cm->vattr[i].count; + + cm->vattr[i].data = tmp; + cm->vattr[i].count = newsz; + + for(j=0; jvattr[i].nelem; j++) { + *tmp++ = *(&cm->cur_val[i].x + j); + } + } + cm->vattr[i].vbo_valid = 0; + cm->vattr[i].data_valid = 1; + } + + if(cm->idata_valid) { + free(cm->idata); + cm->idata = 0; + cm->icount = 0; + } + cm->ibo_valid = cm->idata_valid = 0; + return 0; +} + +void cmesh_normal(struct cmesh *cm, float nx, float ny, float nz) +{ + cgm_wcons(cm->cur_val + CMESH_ATTR_NORMAL, nx, ny, nz, 1.0f); + cm->vattr[CMESH_ATTR_NORMAL].nelem = 3; +} + +void cmesh_tangent(struct cmesh *cm, float tx, float ty, float tz) +{ + cgm_wcons(cm->cur_val + CMESH_ATTR_TANGENT, tx, ty, tz, 1.0f); + cm->vattr[CMESH_ATTR_TANGENT].nelem = 3; +} + +void cmesh_texcoord(struct cmesh *cm, float u, float v, float w) +{ + cgm_wcons(cm->cur_val + CMESH_ATTR_TEXCOORD, u, v, w, 1.0f); + cm->vattr[CMESH_ATTR_TEXCOORD].nelem = 3; +} + +void cmesh_boneweights(struct cmesh *cm, float w1, float w2, float w3, float w4) +{ + cgm_wcons(cm->cur_val + CMESH_ATTR_BONEWEIGHTS, w1, w2, w3, w4); + cm->vattr[CMESH_ATTR_BONEWEIGHTS].nelem = 4; +} + +void cmesh_boneidx(struct cmesh *cm, int idx1, int idx2, int idx3, int idx4) +{ + cgm_wcons(cm->cur_val + CMESH_ATTR_BONEIDX, idx1, idx2, idx3, idx4); + cm->vattr[CMESH_ATTR_BONEIDX].nelem = 4; +} + +static float *get_vec4(struct cmesh *cm, int attr, int idx, cgm_vec4 *res) +{ + int i; + float *sptr, *dptr; + cgm_wcons(res, 0, 0, 0, 1); + if(!(sptr = cmesh_attrib_at(cm, attr, idx))) { + return 0; + } + dptr = &res->x; + + for(i=0; ivattr[attr].nelem; i++) { + *dptr++ = sptr[i]; + } + return sptr; +} + +static float *get_vec3(struct cmesh *cm, int attr, int idx, cgm_vec3 *res) +{ + int i; + float *sptr, *dptr; + cgm_vcons(res, 0, 0, 0); + if(!(sptr = cmesh_attrib_at(cm, attr, idx))) { + return 0; + } + dptr = &res->x; + + for(i=0; ivattr[attr].nelem; i++) { + *dptr++ = sptr[i]; + } + return sptr; +} + +/* dir_xform can be null, in which case it's calculated from xform */ +void cmesh_apply_xform(struct cmesh *cm, float *xform, float *dir_xform) +{ + unsigned int i; + int j; + cgm_vec4 v; + cgm_vec3 n, t; + float *vptr; + + for(i=0; inverts; i++) { + if(!(vptr = get_vec4(cm, CMESH_ATTR_VERTEX, i, &v))) { + return; + } + cgm_wmul_m4v4(&v, xform); + for(j=0; jvattr[CMESH_ATTR_VERTEX].nelem; j++) { + *vptr++ = (&v.x)[j]; + } + + if(cmesh_has_attrib(cm, CMESH_ATTR_NORMAL)) { + if((vptr = get_vec3(cm, CMESH_ATTR_NORMAL, i, &n))) { + cgm_vmul_m3v3(&n, dir_xform); + for(j=0; jvattr[CMESH_ATTR_NORMAL].nelem; j++) { + *vptr++ = (&n.x)[j]; + } + } + } + if(cmesh_has_attrib(cm, CMESH_ATTR_TANGENT)) { + if((vptr = get_vec3(cm, CMESH_ATTR_TANGENT, i, &t))) { + cgm_vmul_m3v3(&t, dir_xform); + for(j=0; jvattr[CMESH_ATTR_TANGENT].nelem; j++) { + *vptr++ = (&t.x)[j]; + } + } + } + } +} + +void cmesh_flip(struct cmesh *cm) +{ + cmesh_flip_faces(cm); + cmesh_flip_normals(cm); +} + +void cmesh_flip_faces(struct cmesh *cm) +{ + int i, j, idxnum, vnum, nelem; + unsigned int *indices; + float *verts, *vptr; + + if(cmesh_indexed(cm)) { + if(!(indices = cmesh_index(cm))) { + return; + } + idxnum = cmesh_index_count(cm); + for(i=0; ivattr[CMESH_ATTR_VERTEX].nelem; + for(i=0; inverts * cm->vattr[CMESH_ATTR_NORMAL].nelem; + for(i=0; ivattr[i].nelem * sizeof(float)))) { + return -1; + } + dstptr = tmpbuf; + + for(j=0; jvattr[i].nelem; + + for(k=0; kvattr[i].nelem; k++) { + *dstptr++ = *srcptr++; + } + } + + free(cm->vattr[i].data); + cm->vattr[i].data = tmpbuf; + cm->vattr[i].count = nnverts * cm->vattr[i].nelem; + cm->vattr[i].data_valid = 1; + } + + cm->ibo_valid = 0; + cm->idata_valid = 0; + free(cm->idata); + cm->idata = 0; + cm->icount = 0; + + cm->nverts = nnverts; + cm->nfaces = idxnum / 3; + return 0; +} + +void cmesh_calc_face_normals(struct cmesh *cm) +{ + /* TODO */ +} + +#ifndef NO_OPENGL +static int pre_draw(struct cmesh *cm) +{ + int i, loc, cur_sdr; + + glGetIntegerv(GL_CURRENT_PROGRAM, &cur_sdr); + + update_buffers(cm); + + if(!cm->vattr[CMESH_ATTR_VERTEX].vbo_valid) { + return -1; + } + + if(cur_sdr && use_custom_sdr_attr) { + if(sdr_loc[CMESH_ATTR_VERTEX] == -1) { + return -1; + } + + for(i=0; i= 0 && cm->vattr[i].vbo_valid) { + glBindBuffer(GL_ARRAY_BUFFER, cm->vattr[i].vbo); + glVertexAttribPointer(loc, cm->vattr[i].nelem, GL_FLOAT, GL_FALSE, 0, 0); + glEnableVertexAttribArray(loc); + } + } + } else { +#ifndef GL_ES_VERSION_2_0 + glBindBuffer(GL_ARRAY_BUFFER, cm->vattr[CMESH_ATTR_VERTEX].vbo); + glVertexPointer(cm->vattr[CMESH_ATTR_VERTEX].nelem, GL_FLOAT, 0, 0); + glEnableClientState(GL_VERTEX_ARRAY); + + if(cm->vattr[CMESH_ATTR_NORMAL].vbo_valid) { + glBindBuffer(GL_ARRAY_BUFFER, cm->vattr[CMESH_ATTR_NORMAL].vbo); + glNormalPointer(GL_FLOAT, 0, 0); + glEnableClientState(GL_NORMAL_ARRAY); + } + if(cm->vattr[CMESH_ATTR_TEXCOORD].vbo_valid) { + glBindBuffer(GL_ARRAY_BUFFER, cm->vattr[CMESH_ATTR_TEXCOORD].vbo); + glTexCoordPointer(cm->vattr[CMESH_ATTR_TEXCOORD].nelem, GL_FLOAT, 0, 0); + glEnableClientState(GL_TEXTURE_COORD_ARRAY); + } + if(cm->vattr[CMESH_ATTR_COLOR].vbo_valid) { + glBindBuffer(GL_ARRAY_BUFFER, cm->vattr[CMESH_ATTR_COLOR].vbo); + glColorPointer(cm->vattr[CMESH_ATTR_COLOR].nelem, GL_FLOAT, 0, 0); + glEnableClientState(GL_COLOR_ARRAY); + } + if(cm->vattr[CMESH_ATTR_TEXCOORD2].vbo_valid) { + glClientActiveTexture(GL_TEXTURE1); + glBindBuffer(GL_ARRAY_BUFFER, cm->vattr[CMESH_ATTR_TEXCOORD2].vbo); + glTexCoordPointer(cm->vattr[CMESH_ATTR_TEXCOORD2].nelem, GL_FLOAT, 0, 0); + glEnableClientState(GL_TEXTURE_COORD_ARRAY); + glClientActiveTexture(GL_TEXTURE0); + } +#endif /* GL_ES_VERSION_2_0 */ + } + glBindBuffer(GL_ARRAY_BUFFER, 0); + return cur_sdr; +} + +void cmesh_draw(struct cmesh *cm) +{ + int cur_sdr; + + if((cur_sdr = pre_draw(cm)) == -1) { + return; + } + + if(cm->ibo_valid) { + glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, cm->ibo); + glDrawElements(GL_TRIANGLES, cm->nfaces * 3, GL_UNSIGNED_INT, 0); + glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0); + } else { + glDrawArrays(GL_TRIANGLES, 0, cm->nverts); + } + + post_draw(cm, cur_sdr); +} + +void cmesh_draw_range(struct cmesh *cm, int start, int count) +{ + int cur_sdr; + + if((cur_sdr = pre_draw(cm)) == -1) { + return; + } + + if(cm->ibo_valid) { + glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, cm->ibo); + glDrawElements(GL_TRIANGLES, count, GL_UNSIGNED_INT, (void*)(start * 4)); + glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0); + } else { + glDrawArrays(GL_TRIANGLES, start, count); + } + + post_draw(cm, cur_sdr); +} + +void cmesh_draw_submesh(struct cmesh *cm, int subidx) +{ + struct submesh *sm = cm->sublist; + + while(sm && subidx-- > 0) { + sm = sm->next; + } + if(!sm) return; + + if(sm->icount) { + cmesh_draw_range(cm, sm->istart, sm->icount); + } else { + cmesh_draw_range(cm, sm->vstart, sm->vcount); + } +} + +static void post_draw(struct cmesh *cm, int cur_sdr) +{ + int i; + + if(cur_sdr && use_custom_sdr_attr) { + for(i=0; i= 0 && cm->vattr[i].vbo_valid) { + glDisableVertexAttribArray(loc); + } + } + } else { +#ifndef GL_ES_VERSION_2_0 + glDisableClientState(GL_VERTEX_ARRAY); + if(cm->vattr[CMESH_ATTR_NORMAL].vbo_valid) { + glDisableClientState(GL_NORMAL_ARRAY); + } + if(cm->vattr[CMESH_ATTR_TEXCOORD].vbo_valid) { + glDisableClientState(GL_TEXTURE_COORD_ARRAY); + } + if(cm->vattr[CMESH_ATTR_COLOR].vbo_valid) { + glDisableClientState(GL_COLOR_ARRAY); + } + if(cm->vattr[CMESH_ATTR_TEXCOORD2].vbo_valid) { + glClientActiveTexture(GL_TEXTURE1); + glDisableClientState(GL_TEXTURE_COORD_ARRAY); + glClientActiveTexture(GL_TEXTURE0); + } +#endif /* GL_ES_VERSION_2_0 */ + } +} + +void cmesh_draw_wire(struct cmesh *cm, float linesz) +{ + int cur_sdr, nfaces; + + if((cur_sdr = pre_draw(cm)) == -1) { + return; + } + update_wire_ibo(cm); + + nfaces = cmesh_poly_count(cm); + glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, cm->wire_ibo); + glDrawElements(GL_LINES, nfaces * 6, GL_UNSIGNED_INT, 0); + glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0); + + post_draw(cm, cur_sdr); +} + +void cmesh_draw_vertices(struct cmesh *cm, float ptsz) +{ + int cur_sdr; + if((cur_sdr = pre_draw(cm)) == -1) { + return; + } + + glPushAttrib(GL_POINT_BIT); + glPointSize(ptsz); + glDrawArrays(GL_POINTS, 0, cm->nverts); + glPopAttrib(); + + post_draw(cm, cur_sdr); +} + +void cmesh_draw_normals(struct cmesh *cm, float len) +{ +#ifndef GL_ES_VERSION_2_0 + int i, cur_sdr, vert_nelem, norm_nelem; + int loc = -1; + const float *varr, *norm; + + varr = cmesh_attrib_ro(cm, CMESH_ATTR_VERTEX); + norm = cmesh_attrib_ro(cm, CMESH_ATTR_NORMAL); + if(!varr || !norm) return; + + vert_nelem = cm->vattr[CMESH_ATTR_VERTEX].nelem; + norm_nelem = cm->vattr[CMESH_ATTR_NORMAL].nelem; + + glGetIntegerv(GL_CURRENT_PROGRAM, &cur_sdr); + if(cur_sdr && use_custom_sdr_attr) { + if((loc = sdr_loc[CMESH_ATTR_VERTEX]) < 0) { + return; + } + } + + glBegin(GL_LINES); + for(i=0; inverts; i++) { + float x, y, z, endx, endy, endz; + + x = varr[i * vert_nelem]; + y = varr[i * vert_nelem + 1]; + z = varr[i * vert_nelem + 2]; + endx = x + norm[i * norm_nelem] * len; + endy = y + norm[i * norm_nelem + 1] * len; + endz = z + norm[i * norm_nelem + 2] * len; + + if(loc == -1) { + glVertex3f(x, y, z); + glVertex3f(endx, endy, endz); + } else { + glVertexAttrib3f(loc, x, y, z); + glVertexAttrib3f(loc, endx, endy, endz); + } + } + glEnd(); +#endif /* GL_ES_VERSION_2_0 */ +} + +void cmesh_draw_tangents(struct cmesh *cm, float len) +{ +#ifndef GL_ES_VERSION_2_0 + int i, cur_sdr, vert_nelem, tang_nelem; + int loc = -1; + const float *varr, *tang; + + varr = cmesh_attrib_ro(cm, CMESH_ATTR_VERTEX); + tang = cmesh_attrib_ro(cm, CMESH_ATTR_TANGENT); + if(!varr || !tang) return; + + vert_nelem = cm->vattr[CMESH_ATTR_VERTEX].nelem; + tang_nelem = cm->vattr[CMESH_ATTR_TANGENT].nelem; + + glGetIntegerv(GL_CURRENT_PROGRAM, &cur_sdr); + if(cur_sdr && use_custom_sdr_attr) { + if((loc = sdr_loc[CMESH_ATTR_VERTEX]) < 0) { + return; + } + } + + glBegin(GL_LINES); + for(i=0; inverts; i++) { + float x, y, z, endx, endy, endz; + + x = varr[i * vert_nelem]; + y = varr[i * vert_nelem + 1]; + z = varr[i * vert_nelem + 2]; + endx = x + tang[i * tang_nelem] * len; + endy = y + tang[i * tang_nelem + 1] * len; + endz = z + tang[i * tang_nelem + 2] * len; + + if(loc == -1) { + glVertex3f(x, y, z); + glVertex3f(endx, endy, endz); + } else { + glVertexAttrib3f(loc, x, y, z); + glVertexAttrib3f(loc, endx, endy, endz); + } + } + glEnd(); +#endif /* GL_ES_VERSION_2_0 */ +} + +static void update_buffers(struct cmesh *cm) +{ + int i; + + for(i=0; ivattr[i].vbo_valid) { + glBindBuffer(GL_ARRAY_BUFFER, cm->vattr[i].vbo); + glBufferData(GL_ARRAY_BUFFER, cm->nverts * cm->vattr[i].nelem * sizeof(float), + cm->vattr[i].data, GL_STATIC_DRAW); + cm->vattr[i].vbo_valid = 1; + } + } + glBindBuffer(GL_ARRAY_BUFFER, 0); + + if(cm->idata_valid && !cm->ibo_valid) { + glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, cm->ibo); + glBufferData(GL_ELEMENT_ARRAY_BUFFER, cm->nfaces * 3 * sizeof(unsigned int), + cm->idata, GL_STATIC_DRAW); + cm->ibo_valid = 1; + glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0); + } +} + +static void update_wire_ibo(struct cmesh *cm) +{ + int i, num_faces; + unsigned int *wire_idxarr, *dest; + + update_buffers(cm); + + if(cm->wire_ibo_valid) return; + + if(!cm->wire_ibo) { + glGenBuffers(1, &cm->wire_ibo); + } + num_faces = cmesh_poly_count(cm); + + if(!(wire_idxarr = malloc(num_faces * 6 * sizeof *wire_idxarr))) { + return; + } + dest = wire_idxarr; + + if(cm->ibo_valid) { + /* we're dealing with an indexed mesh */ + const unsigned int *idxarr = cmesh_index_ro(cm); + + for(i=0; iwire_ibo); + glBufferData(GL_ELEMENT_ARRAY_BUFFER, num_faces * 6 * sizeof(unsigned int), + wire_idxarr, GL_STATIC_DRAW); + free(wire_idxarr); + cm->wire_ibo_valid = 1; + glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0); +} +#endif /* !def NO_OPENGL */ + +static void calc_aabb(struct cmesh *cm) +{ + int i, j; + + if(!cmesh_attrib_ro(cm, CMESH_ATTR_VERTEX)) { + return; + } + + cgm_vcons(&cm->aabb_min, FLT_MAX, FLT_MAX, FLT_MAX); + cgm_vcons(&cm->aabb_max, -FLT_MAX, -FLT_MAX, -FLT_MAX); + + for(i=0; inverts; i++) { + const float *v = cmesh_attrib_at_ro(cm, CMESH_ATTR_VERTEX, i); + for(j=0; j<3; j++) { + if(v[j] < (&cm->aabb_min.x)[j]) { + (&cm->aabb_min.x)[j] = v[j]; + } + if(v[j] > (&cm->aabb_max.x)[j]) { + (&cm->aabb_max.x)[j] = v[j]; + } + } + } + cm->aabb_valid = 1; +} + +void cmesh_aabbox(struct cmesh *cm, cgm_vec3 *vmin, cgm_vec3 *vmax) +{ + if(!cm->aabb_valid) { + calc_aabb(cm); + } + *vmin = cm->aabb_min; + *vmax = cm->aabb_max; +} + +static void calc_bsph(struct cmesh *cm) +{ + int i; + float s, dist_sq; + + if(!cmesh_attrib_ro(cm, CMESH_ATTR_VERTEX)) { + return; + } + + cgm_vcons(&cm->bsph_center, 0, 0, 0); + + /* first find the center */ + for(i=0; inverts; i++) { + const float *v = cmesh_attrib_at_ro(cm, CMESH_ATTR_VERTEX, i); + cm->bsph_center.x += v[0]; + cm->bsph_center.y += v[1]; + cm->bsph_center.z += v[2]; + } + s = 1.0f / (float)cm->nverts; + cm->bsph_center.x *= s; + cm->bsph_center.y *= s; + cm->bsph_center.z *= s; + + cm->bsph_radius = 0.0f; + for(i=0; inverts; i++) { + const cgm_vec3 *v = (const cgm_vec3*)cmesh_attrib_at_ro(cm, CMESH_ATTR_VERTEX, i); + if((dist_sq = cgm_vdist_sq(v, &cm->bsph_center)) > cm->bsph_radius) { + cm->bsph_radius = dist_sq; + } + } + cm->bsph_radius = sqrt(cm->bsph_radius); + cm->bsph_valid = 1; +} + +float cmesh_bsphere(struct cmesh *cm, cgm_vec3 *center, float *rad) +{ + if(!cm->bsph_valid) { + calc_bsph(cm); + } + *center = cm->bsph_center; + *rad = cm->bsph_radius; + return cm->bsph_radius; +} + +/* TODO */ +void cmesh_texcoord_apply_xform(struct cmesh *cm, float *xform); +void cmesh_texcoord_gen_plane(struct cmesh *cm, cgm_vec3 *norm, cgm_vec3 *tang); +void cmesh_texcoord_gen_box(struct cmesh *cm); +void cmesh_texcoord_gen_cylinder(struct cmesh *cm); + +int cmesh_dump(struct cmesh *cm, const char *fname) +{ + FILE *fp = fopen(fname, "wb"); + if(fp) { + int res = cmesh_dump_file(cm, fp); + fclose(fp); + return res; + } + return -1; +} + +int cmesh_dump_file(struct cmesh *cm, FILE *fp) +{ + static const char *label[] = { "pos", "nor", "tan", "tex", "col", "bw", "bid", "tex2" }; + static const char *elemfmt[] = { 0, " %s(%g)", " %s(%g, %g)", " %s(%g, %g, %g)", " %s(%g, %g, %g, %g)", 0 }; + int i, j; + + if(!cmesh_has_attrib(cm, CMESH_ATTR_VERTEX)) { + return -1; + } + + fprintf(fp, "VERTEX ATTRIBUTES\n"); + + for(i=0; inverts; i++) { + fprintf(fp, "%5u:", i); + for(j=0; jvattr[j].nelem; + fprintf(fp, elemfmt[nelem], label[j], v[0], nelem > 1 ? v[1] : 0.0f, + nelem > 2 ? v[2] : 0.0f, nelem > 3 ? v[3] : 0.0f); + } + } + fputc('\n', fp); + } + + if(cmesh_indexed(cm)) { + const unsigned int *idx = cmesh_index_ro(cm); + int numidx = cmesh_index_count(cm); + int numtri = numidx / 3; + assert(numidx % 3 == 0); + + fprintf(fp, "FACES\n"); + + for(i=0; ivattr[CMESH_ATTR_VERTEX].nelem; + if((num = cm->vattr[CMESH_ATTR_VERTEX].count) != cm->nverts * nelem) { + fprintf(stderr, "vertex array size (%d) != nverts (%d)\n", num, cm->nverts); + } + for(i=0; inverts; i++) { + const float *v = cmesh_attrib_at_ro(cm, CMESH_ATTR_VERTEX, i); + fprintf(fp, "v %f %f %f\n", v[0], nelem > 1 ? v[1] : 0.0f, nelem > 2 ? v[2] : 0.0f); + } + + if(cmesh_has_attrib(cm, CMESH_ATTR_NORMAL)) { + aflags |= HAS_VN; + nelem = cm->vattr[CMESH_ATTR_NORMAL].nelem; + if((num = cm->vattr[CMESH_ATTR_NORMAL].count) != cm->nverts * nelem) { + fprintf(stderr, "normal array size (%d) != nverts (%d)\n", num, cm->nverts); + } + for(i=0; inverts; i++) { + const float *v = cmesh_attrib_at_ro(cm, CMESH_ATTR_NORMAL, i); + fprintf(fp, "vn %f %f %f\n", v[0], nelem > 1 ? v[1] : 0.0f, nelem > 2 ? v[2] : 0.0f); + } + } + + if(cmesh_has_attrib(cm, CMESH_ATTR_TEXCOORD)) { + aflags |= HAS_VT; + nelem = cm->vattr[CMESH_ATTR_TEXCOORD].nelem; + if((num = cm->vattr[CMESH_ATTR_TEXCOORD].count) != cm->nverts * nelem) { + fprintf(stderr, "texcoord array size (%d) != nverts (%d)\n", num, cm->nverts); + } + for(i=0; inverts; i++) { + const float *v = cmesh_attrib_at_ro(cm, CMESH_ATTR_TEXCOORD, i); + fprintf(fp, "vt %f %f\n", v[0], nelem > 1 ? v[1] : 0.0f); + } + } + + if(cmesh_indexed(cm)) { + const unsigned int *idxptr = cmesh_index_ro(cm); + int numidx = cmesh_index_count(cm); + int numtri = numidx / 3; + assert(numidx % 3 == 0); + + for(i=0; inverts / 3; + unsigned int idx = 1 + voffs; + for(i=0; i +#include "cgmath/cgmath.h" + +enum { + CMESH_ATTR_VERTEX, + CMESH_ATTR_NORMAL, + CMESH_ATTR_TANGENT, + CMESH_ATTR_TEXCOORD, + CMESH_ATTR_COLOR, + CMESH_ATTR_BONEWEIGHTS, + CMESH_ATTR_BONEIDX, + CMESH_ATTR_TEXCOORD2, + + CMESH_NUM_ATTR +}; + +struct cmesh; + +/* global state */ +void cmesh_set_attrib_sdrloc(int attr, int loc); +int cmesh_get_attrib_sdrloc(int attr); +void cmesh_clear_attrib_sdrloc(void); + +/* mesh functions */ +struct cmesh *cmesh_alloc(void); +void cmesh_free(struct cmesh *cm); + +int cmesh_init(struct cmesh *cm); +void cmesh_destroy(struct cmesh *cm); + +void cmesh_clear(struct cmesh *cm); +int cmesh_clone(struct cmesh *cmdest, struct cmesh *cmsrc); + +int cmesh_set_name(struct cmesh *cm, const char *name); +const char *cmesh_name(struct cmesh *cm); + +int cmesh_has_attrib(struct cmesh *cm, int attr); +int cmesh_indexed(struct cmesh *cm); + +/* vdata can be 0, in which case only memory is allocated + * returns pointer to the attribute array + */ +float *cmesh_set_attrib(struct cmesh *cm, int attr, int nelem, unsigned int num, + const float *vdata); +float *cmesh_attrib(struct cmesh *cm, int attr); /* invalidates VBO */ +const float *cmesh_attrib_ro(struct cmesh *cm, int attr); /* doesn't invalidate */ +float *cmesh_attrib_at(struct cmesh *cm, int attr, int idx); +const float *cmesh_attrib_at_ro(struct cmesh *cm, int attr, int idx); +int cmesh_attrib_count(struct cmesh *cm, int attr); +int cmesh_push_attrib(struct cmesh *cm, int attr, float *v); +int cmesh_push_attrib1f(struct cmesh *cm, int attr, float x); +int cmesh_push_attrib2f(struct cmesh *cm, int attr, float x, float y); +int cmesh_push_attrib3f(struct cmesh *cm, int attr, float x, float y, float z); +int cmesh_push_attrib4f(struct cmesh *cm, int attr, float x, float y, float z, float w); + +/* indices can be 0, in which case only memory is allocated + * returns pointer to the index array + */ +unsigned int *cmesh_set_index(struct cmesh *cm, int num, const unsigned int *indices); +unsigned int *cmesh_index(struct cmesh *cm); /* invalidates IBO */ +const unsigned int *cmesh_index_ro(struct cmesh *cm); /* doesn't invalidate */ +int cmesh_index_count(struct cmesh *cm); +int cmesh_push_index(struct cmesh *cm, unsigned int idx); + +int cmesh_poly_count(struct cmesh *cm); + +/* attr can be -1 to invalidate all attributes */ +void cmesh_invalidate_vbo(struct cmesh *cm, int attr); +void cmesh_invalidate_ibo(struct cmesh *cm); + +int cmesh_append(struct cmesh *cmdest, struct cmesh *cmsrc); + +/* submeshes */ +void cmesh_clear_submeshes(struct cmesh *cm); +/* a submesh is defined as a consecutive range of faces */ +int cmesh_submesh(struct cmesh *cm, const char *name, int fstart, int fcount); +int cmesh_remove_submesh(struct cmesh *cm, int idx); +int cmesh_find_submesh(struct cmesh *cm, const char *name); +int cmesh_submesh_count(struct cmesh *cm); +int cmesh_clone_submesh(struct cmesh *cmdest, struct cmesh *cm, int subidx); + +/* immediate-mode style mesh construction interface */ +int cmesh_vertex(struct cmesh *cm, float x, float y, float z); +void cmesh_normal(struct cmesh *cm, float nx, float ny, float nz); +void cmesh_tangent(struct cmesh *cm, float tx, float ty, float tz); +void cmesh_texcoord(struct cmesh *cm, float u, float v, float w); +void cmesh_boneweights(struct cmesh *cm, float w1, float w2, float w3, float w4); +void cmesh_boneidx(struct cmesh *cm, int idx1, int idx2, int idx3, int idx4); + +/* dir_xform can be null, in which case it's calculated from xform */ +void cmesh_apply_xform(struct cmesh *cm, float *xform, float *dir_xform); + +void cmesh_flip(struct cmesh *cm); /* flip faces (winding) and normals */ +void cmesh_flip_faces(struct cmesh *cm); +void cmesh_flip_normals(struct cmesh *cm); + +int cmesh_explode(struct cmesh *cm); /* undo all vertex sharing */ + +/* this is only guaranteed to work on an exploded mesh */ +void cmesh_calc_face_normals(struct cmesh *cm); + +void cmesh_draw(struct cmesh *cm); +void cmesh_draw_range(struct cmesh *cm, int start, int count); +void cmesh_draw_submesh(struct cmesh *cm, int subidx); /* XXX only for indexed meshes currently */ +void cmesh_draw_wire(struct cmesh *cm, float linesz); +void cmesh_draw_vertices(struct cmesh *cm, float ptsz); +void cmesh_draw_normals(struct cmesh *cm, float len); +void cmesh_draw_tangents(struct cmesh *cm, float len); + +/* get the bounding box in local space. The result will be cached and subsequent + * calls will return the same box. The cache gets invalidated by any functions that + * can affect the vertex data + */ +void cmesh_aabbox(struct cmesh *cm, cgm_vec3 *vmin, cgm_vec3 *vmax); + +/* get the bounding sphere in local space. The result will be cached ... see above */ +float cmesh_bsphere(struct cmesh *cm, cgm_vec3 *center, float *rad); + +/* texture coordinate manipulation */ +void cmesh_texcoord_apply_xform(struct cmesh *cm, float *xform); +void cmesh_texcoord_gen_plane(struct cmesh *cm, cgm_vec3 *norm, cgm_vec3 *tang); +void cmesh_texcoord_gen_box(struct cmesh *cm); +void cmesh_texcoord_gen_cylinder(struct cmesh *cm); + +/* FILE I/O */ +int cmesh_load(struct cmesh *cm, const char *fname); + +int cmesh_dump(struct cmesh *cm, const char *fname); +int cmesh_dump_file(struct cmesh *cm, FILE *fp); +int cmesh_dump_obj(struct cmesh *cm, const char *fname); +int cmesh_dump_obj_file(struct cmesh *cm, FILE *fp, int voffs); + + + +#endif /* CMESH_H_ */ diff --git a/tools/meshdump/dynarr.c b/tools/meshdump/dynarr.c new file mode 100644 index 0000000..59bbf8c --- /dev/null +++ b/tools/meshdump/dynarr.c @@ -0,0 +1,141 @@ +/* dynarr - dynamic resizable C array data structure + * author: John Tsiombikas + * license: public domain + */ +#include +#include +#include +#include "dynarr.h" + +/* The array descriptor keeps auxilliary information needed to manipulate + * the dynamic array. It's allocated adjacent to the array buffer. + */ +struct arrdesc { + int nelem, szelem; + int max_elem; + int bufsz; /* not including the descriptor */ +}; + +#define DESC(x) ((struct arrdesc*)((char*)(x) - sizeof(struct arrdesc))) + +void *dynarr_alloc(int elem, int szelem) +{ + struct arrdesc *desc; + + if(!(desc = malloc(elem * szelem + sizeof *desc))) { + return 0; + } + desc->nelem = desc->max_elem = elem; + desc->szelem = szelem; + desc->bufsz = elem * szelem; + return (char*)desc + sizeof *desc; +} + +void dynarr_free(void *da) +{ + if(da) { + free(DESC(da)); + } +} + +void *dynarr_resize(void *da, int elem) +{ + int newsz; + void *tmp; + struct arrdesc *desc; + + if(!da) return 0; + desc = DESC(da); + + newsz = desc->szelem * elem; + + if(!(tmp = realloc(desc, newsz + sizeof *desc))) { + return 0; + } + desc = tmp; + + desc->nelem = desc->max_elem = elem; + desc->bufsz = newsz; + return (char*)desc + sizeof *desc; +} + +int dynarr_empty(void *da) +{ + return DESC(da)->nelem ? 0 : 1; +} + +int dynarr_size(void *da) +{ + return DESC(da)->nelem; +} + + +void *dynarr_clear(void *da) +{ + return dynarr_resize(da, 0); +} + +/* stack semantics */ +void *dynarr_push(void *da, void *item) +{ + struct arrdesc *desc; + int nelem; + + desc = DESC(da); + nelem = desc->nelem; + + if(nelem >= desc->max_elem) { + /* need to resize */ + struct arrdesc *tmp; + int newsz = desc->max_elem ? desc->max_elem * 2 : 1; + + if(!(tmp = dynarr_resize(da, newsz))) { + fprintf(stderr, "failed to resize\n"); + return da; + } + da = tmp; + desc = DESC(da); + desc->nelem = nelem; + } + + if(item) { + memcpy((char*)da + desc->nelem * desc->szelem, item, desc->szelem); + } + desc->nelem++; + return da; +} + +void *dynarr_pop(void *da) +{ + struct arrdesc *desc; + int nelem; + + desc = DESC(da); + nelem = desc->nelem; + + if(!nelem) return da; + + if(nelem <= desc->max_elem / 3) { + /* reclaim space */ + struct arrdesc *tmp; + int newsz = desc->max_elem / 2; + + if(!(tmp = dynarr_resize(da, newsz))) { + fprintf(stderr, "failed to resize\n"); + return da; + } + da = tmp; + desc = DESC(da); + desc->nelem = nelem; + } + desc->nelem--; + + return da; +} + +void *dynarr_finalize(void *da) +{ + struct arrdesc *desc = DESC(da); + memmove(desc, da, desc->bufsz); + return desc; +} diff --git a/tools/meshdump/dynarr.h b/tools/meshdump/dynarr.h new file mode 100644 index 0000000..8690b5a --- /dev/null +++ b/tools/meshdump/dynarr.h @@ -0,0 +1,80 @@ +/* dynarr - dynamic resizable C array data structure + * author: John Tsiombikas + * license: public domain + */ +#ifndef DYNARR_H_ +#define DYNARR_H_ + +/* usage example: + * ------------- + * int *arr = dynarr_alloc(0, sizeof *arr); + * + * int x = 10; + * arr = dynarr_push(arr, &x); + * x = 5; + * arr = dynarr_push(arr, &x); + * x = 42; + * arr = dynarr_push(arr, &x); + * + * for(i=0; i +#include +#include +#include "cmesh.h" + +int main(int argc, char **argv) +{ + int i; + struct cmesh *cm; + + for(i=1; i +#include +#include +#include +#include "cmesh.h" + +#ifdef USE_ASSIMP +#include +#include +#include +#include +#include +#else +#include "dynarr.h" +#include "rbtree.h" +#endif + + +#ifdef USE_ASSIMP + +static int add_mesh(struct cmesh *mesh, struct aiMesh *aimesh); + +#define AIPPFLAGS \ + (aiProcess_JoinIdenticalVertices | aiProcess_PreTransformVertices | \ + aiProcess_Triangulate | aiProcess_SortByPType | aiProcess_FlipUVs) + +int cmesh_load(struct cmesh *mesh, const char *fname) +{ + int i; + const struct aiScene *aiscn; + + if(!(aiscn = aiImportFile(fname, AIPPFLAGS))) { + fprintf(stderr, "failed to open mesh file: %s\n", fname); + return -1; + } + + for(i=0; i<(int)aiscn->mNumMeshes; i++) { + add_mesh(mesh, aiscn->mMeshes[i]); + } + + aiReleaseImport(aiscn); + return 0; +} + +static int add_mesh(struct cmesh *mesh, struct aiMesh *aim) +{ + int i, j, voffs, foffs; + + voffs = cmesh_attrib_count(mesh, CMESH_ATTR_VERTEX); + foffs = cmesh_poly_count(mesh); + + for(i=0; imNumVertices; i++) { + struct aiVector3D *v = aim->mVertices + i; + cmesh_push_attrib3f(mesh, CMESH_ATTR_VERTEX, v->x, v->y, v->z); + + if(aim->mNormals) { + v = aim->mNormals + i; + cmesh_push_attrib3f(mesh, CMESH_ATTR_NORMAL, v->x, v->y, v->z); + } + if(aim->mTangents) { + v = aim->mTangents + i; + cmesh_push_attrib3f(mesh, CMESH_ATTR_TANGENT, v->x, v->y, v->z); + } + if(aim->mColors[0]) { + struct aiColor4D *col = aim->mColors[0] + i; + cmesh_push_attrib4f(mesh, CMESH_ATTR_COLOR, col->r, col->g, col->b, col->a); + } + if(aim->mTextureCoords[0]) { + v = aim->mTextureCoords[0] + i; + cmesh_push_attrib2f(mesh, CMESH_ATTR_TEXCOORD, v->x, v->y); + } + if(aim->mTextureCoords[1]) { + v = aim->mTextureCoords[1] + i; + cmesh_push_attrib2f(mesh, CMESH_ATTR_TEXCOORD2, v->x, v->y); + } + } + + if(aim->mFaces) { + for(i=0; imNumFaces; i++) { + assert(aim->mFaces[i].mNumIndices == 3); + for(j=0; j<3; j++) { + cmesh_push_index(mesh, aim->mFaces[i].mIndices[j] + voffs); + } + } + cmesh_submesh(mesh, aim->mName.data, foffs, aim->mNumFaces); + } + return 0; +} + +#else + +struct vertex_pos { + float x, y, z; +}; + +struct facevertex { + int vidx, tidx, nidx; +}; + +static char *clean_line(char *s); +static char *parse_face_vert(char *ptr, struct facevertex *fv, int numv, int numt, int numn); +static int cmp_facevert(const void *ap, const void *bp); +static void free_rbnode_key(struct rbnode *n, void *cls); + +/* merge of different indices per attribute happens during face processing. + * + * A triplet of (vertex index/texcoord index/normal index) is used as the key + * to search in a balanced binary search tree for vertex buffer index assigned + * to the same triplet if it has been encountered before. That index is + * appended to the index buffer. + * + * If a particular triplet has not been encountered before, a new vertex is + * appended to the vertex buffer. The index of this new vertex is appended to + * the index buffer, and also inserted into the tree for future searches. + */ +int cmesh_load(struct cmesh *mesh, const char *fname) +{ + int i, line_num = 0, result = -1; + int found_quad = 0; + FILE *fp = 0; + char buf[256]; + struct vertex_pos *varr = 0; + cgm_vec3 *narr = 0; + cgm_vec2 *tarr = 0; + struct rbtree *rbtree = 0; + char *subname = 0; + int substart = 0, subcount = 0; + + if(!(fp = fopen(fname, "rb"))) { + fprintf(stderr, "load_mesh: failed to open file: %s\n", fname); + goto err; + } + + if(!(rbtree = rb_create(cmp_facevert))) { + fprintf(stderr, "load_mesh: failed to create facevertex binary search tree\n"); + goto err; + } + rb_set_delete_func(rbtree, free_rbnode_key, 0); + + if(!(varr = dynarr_alloc(0, sizeof *varr)) || + !(narr = dynarr_alloc(0, sizeof *narr)) || + !(tarr = dynarr_alloc(0, sizeof *tarr))) { + fprintf(stderr, "load_mesh: failed to allocate resizable vertex array\n"); + goto err; + } + + while(fgets(buf, sizeof buf, fp)) { + char *line = clean_line(buf); + ++line_num; + + if(!*line) continue; + + switch(line[0]) { + case 'v': + if(isspace(line[1])) { + /* vertex */ + struct vertex_pos v; + int num; + + num = sscanf(line + 2, "%f %f %f", &v.x, &v.y, &v.z); + if(num < 3) { + fprintf(stderr, "%s:%d: invalid vertex definition: \"%s\"\n", fname, line_num, line); + goto err; + } + if(!(varr = dynarr_push(varr, &v))) { + fprintf(stderr, "load_mesh: failed to resize vertex buffer\n"); + goto err; + } + + } else if(line[1] == 't' && isspace(line[2])) { + /* texcoord */ + cgm_vec2 tc; + if(sscanf(line + 3, "%f %f", &tc.x, &tc.y) != 2) { + fprintf(stderr, "%s:%d: invalid texcoord definition: \"%s\"\n", fname, line_num, line); + goto err; + } + tc.y = 1.0f - tc.y; + if(!(tarr = dynarr_push(tarr, &tc))) { + fprintf(stderr, "load_mesh: failed to resize texcoord buffer\n"); + goto err; + } + + } else if(line[1] == 'n' && isspace(line[2])) { + /* normal */ + cgm_vec3 norm; + if(sscanf(line + 3, "%f %f %f", &norm.x, &norm.y, &norm.z) != 3) { + fprintf(stderr, "%s:%d: invalid normal definition: \"%s\"\n", fname, line_num, line); + goto err; + } + if(!(narr = dynarr_push(narr, &norm))) { + fprintf(stderr, "load_mesh: failed to resize normal buffer\n"); + goto err; + } + } + break; + + case 'f': + if(isspace(line[1])) { + /* face */ + char *ptr = line + 2; + struct facevertex fv; + struct rbnode *node; + int vsz = dynarr_size(varr); + int tsz = dynarr_size(tarr); + int nsz = dynarr_size(narr); + + for(i=0; i<4; i++) { + if(!(ptr = parse_face_vert(ptr, &fv, vsz, tsz, nsz))) { + if(i < 3 || found_quad) { + fprintf(stderr, "%s:%d: invalid face definition: \"%s\"\n", fname, line_num, line); + goto err; + } else { + break; + } + } + + if((node = rb_find(rbtree, &fv))) { + unsigned int idx = (unsigned int)node->data; + assert(idx < cmesh_attrib_count(mesh, CMESH_ATTR_VERTEX)); + if(cmesh_push_index(mesh, idx) == -1) { + fprintf(stderr, "load_mesh: failed to resize index array\n"); + goto err; + } + subcount++; /* inc number of submesh indices, in case we have submeshes */ + } else { + unsigned int newidx = cmesh_attrib_count(mesh, CMESH_ATTR_VERTEX); + struct facevertex *newfv; + struct vertex_pos *vptr = varr + fv.vidx; + + if(cmesh_push_attrib3f(mesh, CMESH_ATTR_VERTEX, vptr->x, vptr->y, vptr->z) == -1) { + fprintf(stderr, "load_mesh: failed to resize vertex array\n"); + goto err; + } + if(fv.nidx >= 0) { + float nx = narr[fv.nidx].x; + float ny = narr[fv.nidx].y; + float nz = narr[fv.nidx].z; + if(cmesh_push_attrib3f(mesh, CMESH_ATTR_NORMAL, nx, ny, nz) == -1) { + fprintf(stderr, "load_mesh: failed to resize normal array\n"); + goto err; + } + } + if(fv.tidx >= 0) { + float tu = tarr[fv.tidx].x; + float tv = tarr[fv.tidx].y; + if(cmesh_push_attrib2f(mesh, CMESH_ATTR_TEXCOORD, tu, tv) == -1) { + fprintf(stderr, "load_mesh: failed to resize texcoord array\n"); + goto err; + } + } + + if(cmesh_push_index(mesh, newidx) == -1) { + fprintf(stderr, "load_mesh: failed to resize index array\n"); + goto err; + } + subcount++; /* inc number of submesh indices, in case we have submeshes */ + + if((newfv = malloc(sizeof *newfv))) { + *newfv = fv; + } + if(!newfv || rb_insert(rbtree, newfv, (void*)newidx) == -1) { + fprintf(stderr, "load_mesh: failed to insert facevertex to the binary search tree\n"); + goto err; + } + } + } + if(i > 3) found_quad = 1; + } + break; + + case 'o': + if(subcount > 0) { + printf("adding submesh: %s\n", subname); + cmesh_submesh(mesh, subname, substart / 3, subcount / 3); + } + free(subname); + if((subname = malloc(strlen(line)))) { + strcpy(subname, clean_line(line + 2)); + } + substart += subcount; + subcount = 0; + break; + + default: + break; + } + } + + if(subcount > 0) { + /* don't add the final submesh if we never found another. an obj file with a + * single 'o' for the whole list of faces, is a single mesh without submeshes + */ + if(cmesh_submesh_count(mesh) > 0) { + printf("adding submesh: %s\n", subname); + cmesh_submesh(mesh, subname, substart / 3, subcount / 3); + } else { + /* ... but use the 'o' name as the name of the mesh instead of the filename */ + if(subname && *subname) { + cmesh_set_name(mesh, subname); + } + } + } + + result = 0; /* success */ + + printf("loaded %s mesh: %s (%d submeshes): %d vertices, %d faces\n", + found_quad ? "quad" : "triangle", fname, cmesh_submesh_count(mesh), + cmesh_attrib_count(mesh, CMESH_ATTR_VERTEX), cmesh_poly_count(mesh)); + +err: + if(fp) fclose(fp); + dynarr_free(varr); + dynarr_free(narr); + dynarr_free(tarr); + rb_free(rbtree); + free(subname); + return result; +} + + +static char *clean_line(char *s) +{ + char *end; + + while(*s && isspace(*s)) ++s; + if(!*s) return 0; + + end = s; + while(*end && *end != '#') ++end; + *end-- = 0; + + while(end > s && isspace(*end)) { + *end-- = 0; + } + + return s; +} + +static char *parse_idx(char *ptr, int *idx, int arrsz) +{ + char *endp; + int val = strtol(ptr, &endp, 10); + if(endp == ptr) return 0; + + if(val < 0) { /* convert negative indices */ + *idx = arrsz + val; + } else { + *idx = val - 1; /* indices in obj are 1-based */ + } + return endp; +} + +/* possible face-vertex definitions: + * 1. vertex + * 2. vertex/texcoord + * 3. vertex//normal + * 4. vertex/texcoord/normal + */ +static char *parse_face_vert(char *ptr, struct facevertex *fv, int numv, int numt, int numn) +{ + if(!(ptr = parse_idx(ptr, &fv->vidx, numv))) + return 0; + if(*ptr != '/') return (!*ptr || isspace(*ptr)) ? ptr : 0; + + if(*++ptr == '/') { /* no texcoord */ + fv->tidx = -1; + ++ptr; + } else { + if(!(ptr = parse_idx(ptr, &fv->tidx, numt))) + return 0; + if(*ptr != '/') return (!*ptr || isspace(*ptr)) ? ptr : 0; + ++ptr; + } + + if(!(ptr = parse_idx(ptr, &fv->nidx, numn))) + return 0; + return (!*ptr || isspace(*ptr)) ? ptr : 0; +} + +static int cmp_facevert(const void *ap, const void *bp) +{ + const struct facevertex *a = ap; + const struct facevertex *b = bp; + + if(a->vidx == b->vidx) { + if(a->tidx == b->tidx) { + return a->nidx - b->nidx; + } + return a->tidx - b->tidx; + } + return a->vidx - b->vidx; +} + +static void free_rbnode_key(struct rbnode *n, void *cls) +{ + free(n->key); +} +#endif diff --git a/tools/meshdump/rbtree.c b/tools/meshdump/rbtree.c new file mode 100644 index 0000000..e595885 --- /dev/null +++ b/tools/meshdump/rbtree.c @@ -0,0 +1,503 @@ +/* +rbtree - simple balanced binary search tree (red-black tree) library. +Copyright (C) 2011-2014 John Tsiombikas + +rbtree is free software, feel free to use, modify, and redistribute it, under +the terms of the 3-clause BSD license. See COPYING for details. + */ +#include +#include +#include +#include +#include "rbtree.h" + +#define INT2PTR(x) ((void*)(intptr_t)(x)) +#define PTR2INT(x) ((int)(intptr_t)(x)) + +struct rbtree { + struct rbnode *root; + + rb_alloc_func_t alloc; + rb_free_func_t free; + + rb_cmp_func_t cmp; + rb_del_func_t del; + void *del_cls; + + struct rbnode *rstack, *iter; +}; + +static int cmpaddr(const void *ap, const void *bp); +static int cmpint(const void *ap, const void *bp); + +static int count_nodes(struct rbnode *node); +static void del_tree(struct rbnode *node, void (*delfunc)(struct rbnode*, void*), void *cls); +static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data); +static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key); +/*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key);*/ +static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls); + +struct rbtree *rb_create(rb_cmp_func_t cmp_func) +{ + struct rbtree *rb; + + if(!(rb = malloc(sizeof *rb))) { + return 0; + } + if(rb_init(rb, cmp_func) == -1) { + free(rb); + return 0; + } + return rb; +} + +void rb_free(struct rbtree *rb) +{ + rb_destroy(rb); + free(rb); +} + + +int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func) +{ + memset(rb, 0, sizeof *rb); + + if(!cmp_func) { + rb->cmp = cmpaddr; + } else if(cmp_func == RB_KEY_INT) { + rb->cmp = cmpint; + } else if(cmp_func == RB_KEY_STRING) { + rb->cmp = (rb_cmp_func_t)strcmp; + } else { + rb->cmp = cmp_func; + } + + rb->alloc = malloc; + rb->free = free; + return 0; +} + +void rb_destroy(struct rbtree *rb) +{ + del_tree(rb->root, rb->del, rb->del_cls); +} + +void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free) +{ + rb->alloc = alloc; + rb->free = free; +} + + +void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func) +{ + rb->cmp = func; +} + +void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls) +{ + rb->del = func; + rb->del_cls = cls; +} + + +void rb_clear(struct rbtree *rb) +{ + del_tree(rb->root, rb->del, rb->del_cls); + rb->root = 0; +} + +int rb_copy(struct rbtree *dest, struct rbtree *src) +{ + struct rbnode *node; + + rb_clear(dest); + rb_begin(src); + while((node = rb_next(src))) { + if(rb_insert(dest, node->key, node->data) == -1) { + return -1; + } + } + return 0; +} + +int rb_size(struct rbtree *rb) +{ + return count_nodes(rb->root); +} + +int rb_insert(struct rbtree *rb, void *key, void *data) +{ + rb->root = insert(rb, rb->root, key, data); + rb->root->red = 0; + return 0; +} + +int rb_inserti(struct rbtree *rb, int key, void *data) +{ + rb->root = insert(rb, rb->root, INT2PTR(key), data); + rb->root->red = 0; + return 0; +} + + +int rb_delete(struct rbtree *rb, void *key) +{ + if((rb->root = delete(rb, rb->root, key))) { + rb->root->red = 0; + } + return 0; +} + +int rb_deletei(struct rbtree *rb, int key) +{ + if((rb->root = delete(rb, rb->root, INT2PTR(key)))) { + rb->root->red = 0; + } + return 0; +} + + +struct rbnode *rb_find(struct rbtree *rb, void *key) +{ + struct rbnode *node = rb->root; + + while(node) { + int cmp = rb->cmp(key, node->key); + if(cmp == 0) { + return node; + } + node = cmp < 0 ? node->left : node->right; + } + return 0; +} + +struct rbnode *rb_findi(struct rbtree *rb, int key) +{ + return rb_find(rb, INT2PTR(key)); +} + + +void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls) +{ + traverse(rb->root, func, cls); +} + + +struct rbnode *rb_root(struct rbtree *rb) +{ + return rb->root; +} + +void rb_begin(struct rbtree *rb) +{ + rb->rstack = 0; + rb->iter = rb->root; +} + +#define push(sp, x) ((x)->next = (sp), (sp) = (x)) +#define pop(sp) ((sp) = (sp)->next) +#define top(sp) (sp) + +struct rbnode *rb_next(struct rbtree *rb) +{ + struct rbnode *res = 0; + + while(rb->rstack || rb->iter) { + if(rb->iter) { + push(rb->rstack, rb->iter); + rb->iter = rb->iter->left; + } else { + rb->iter = top(rb->rstack); + pop(rb->rstack); + res = rb->iter; + rb->iter = rb->iter->right; + break; + } + } + return res; +} + +void *rb_node_key(struct rbnode *node) +{ + return node ? node->key : 0; +} + +int rb_node_keyi(struct rbnode *node) +{ + return node ? PTR2INT(node->key) : 0; +} + +void *rb_node_data(struct rbnode *node) +{ + return node ? node->data : 0; +} + +static int cmpaddr(const void *ap, const void *bp) +{ + return ap < bp ? -1 : (ap > bp ? 1 : 0); +} + +static int cmpint(const void *ap, const void *bp) +{ + return PTR2INT(ap) - PTR2INT(bp); +} + + +/* ---- left-leaning 2-3 red-black implementation ---- */ + +/* helper prototypes */ +static int is_red(struct rbnode *tree); +static void color_flip(struct rbnode *tree); +static struct rbnode *rot_left(struct rbnode *a); +static struct rbnode *rot_right(struct rbnode *a); +static struct rbnode *find_min(struct rbnode *tree); +static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree); +/*static struct rbnode *move_red_right(struct rbnode *tree);*/ +static struct rbnode *move_red_left(struct rbnode *tree); +static struct rbnode *fix_up(struct rbnode *tree); + +static int count_nodes(struct rbnode *node) +{ + if(!node) + return 0; + + return 1 + count_nodes(node->left) + count_nodes(node->right); +} + +static void del_tree(struct rbnode *node, rb_del_func_t delfunc, void *cls) +{ + if(!node) + return; + + del_tree(node->left, delfunc, cls); + del_tree(node->right, delfunc, cls); + + if(delfunc) { + delfunc(node, cls); + } + free(node); +} + +static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data) +{ + int cmp; + + if(!tree) { + struct rbnode *node = rb->alloc(sizeof *node); + node->red = 1; + node->key = key; + node->data = data; + node->left = node->right = 0; + return node; + } + + cmp = rb->cmp(key, tree->key); + + if(cmp < 0) { + tree->left = insert(rb, tree->left, key, data); + } else if(cmp > 0) { + tree->right = insert(rb, tree->right, key, data); + } else { + tree->data = data; + } + + /* fix right-leaning reds */ + if(is_red(tree->right)) { + tree = rot_left(tree); + } + /* fix two reds in a row */ + if(is_red(tree->left) && is_red(tree->left->left)) { + tree = rot_right(tree); + } + + /* if 4-node, split it by color inversion */ + if(is_red(tree->left) && is_red(tree->right)) { + color_flip(tree); + } + + return tree; +} + +static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key) +{ + int cmp; + + if(!tree) { + return 0; + } + + cmp = rb->cmp(key, tree->key); + + if(cmp < 0) { + if(!is_red(tree->left) && !is_red(tree->left->left)) { + tree = move_red_left(tree); + } + tree->left = delete(rb, tree->left, key); + } else { + /* need reds on the right */ + if(is_red(tree->left)) { + tree = rot_right(tree); + } + + /* found it at the bottom (XXX what certifies left is null?) */ + if(cmp == 0 && !tree->right) { + if(rb->del) { + rb->del(tree, rb->del_cls); + } + rb->free(tree); + return 0; + } + + if(!is_red(tree->right) && !is_red(tree->right->left)) { + tree = move_red_left(tree); + } + + if(key == tree->key) { + struct rbnode *rmin = find_min(tree->right); + tree->key = rmin->key; + tree->data = rmin->data; + tree->right = del_min(rb, tree->right); + } else { + tree->right = delete(rb, tree->right, key); + } + } + + return fix_up(tree); +} + +/*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key) +{ + int cmp; + + if(!node) + return 0; + + if((cmp = rb->cmp(key, node->key)) == 0) { + return node; + } + return find(rb, cmp < 0 ? node->left : node->right, key); +}*/ + +static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls) +{ + if(!node) + return; + + traverse(node->left, func, cls); + func(node, cls); + traverse(node->right, func, cls); +} + +/* helpers */ + +static int is_red(struct rbnode *tree) +{ + return tree && tree->red; +} + +static void color_flip(struct rbnode *tree) +{ + tree->red = !tree->red; + tree->left->red = !tree->left->red; + tree->right->red = !tree->right->red; +} + +static struct rbnode *rot_left(struct rbnode *a) +{ + struct rbnode *b = a->right; + a->right = b->left; + b->left = a; + b->red = a->red; + a->red = 1; + return b; +} + +static struct rbnode *rot_right(struct rbnode *a) +{ + struct rbnode *b = a->left; + a->left = b->right; + b->right = a; + b->red = a->red; + a->red = 1; + return b; +} + +static struct rbnode *find_min(struct rbnode *tree) +{ + if(!tree) + return 0; + + while(tree->left) { + tree = tree->left; + } + return tree; +} + +static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree) +{ + if(!tree->left) { + if(rb->del) { + rb->del(tree->left, rb->del_cls); + } + rb->free(tree->left); + return 0; + } + + /* make sure we've got red (3/4-nodes) at the left side so we can delete at the bottom */ + if(!is_red(tree->left) && !is_red(tree->left->left)) { + tree = move_red_left(tree); + } + tree->left = del_min(rb, tree->left); + + /* fix right-reds, red-reds, and split 4-nodes on the way up */ + return fix_up(tree); +} + +#if 0 +/* push a red link on this node to the right */ +static struct rbnode *move_red_right(struct rbnode *tree) +{ + /* flipping it makes both children go red, so we have a red to the right */ + color_flip(tree); + + /* if after the flip we've got a red-red situation to the left, fix it */ + if(is_red(tree->left->left)) { + tree = rot_right(tree); + color_flip(tree); + } + return tree; +} +#endif + +/* push a red link on this node to the left */ +static struct rbnode *move_red_left(struct rbnode *tree) +{ + /* flipping it makes both children go red, so we have a red to the left */ + color_flip(tree); + + /* if after the flip we've got a red-red on the right-left, fix it */ + if(is_red(tree->right->left)) { + tree->right = rot_right(tree->right); + tree = rot_left(tree); + color_flip(tree); + } + return tree; +} + +static struct rbnode *fix_up(struct rbnode *tree) +{ + /* fix right-leaning */ + if(is_red(tree->right)) { + tree = rot_left(tree); + } + /* change invalid red-red pairs into a proper 4-node */ + if(is_red(tree->left) && is_red(tree->left->left)) { + tree = rot_right(tree); + } + /* split 4-nodes */ + if(is_red(tree->left) && is_red(tree->right)) { + color_flip(tree); + } + return tree; +} diff --git a/tools/meshdump/rbtree.h b/tools/meshdump/rbtree.h new file mode 100644 index 0000000..8688c7f --- /dev/null +++ b/tools/meshdump/rbtree.h @@ -0,0 +1,78 @@ +/* +rbtree - simple balanced binary search tree (red-black tree) library. +Copyright (C) 2011-2014 John Tsiombikas + +rbtree is free software, feel free to use, modify, and redistribute it, under +the terms of the 3-clause BSD license. See COPYING for details. + */ +#ifndef RBTREE_H_ +#define RBTREE_H_ + +struct rbtree; + + +struct rbnode { + void *key, *data; + int red; + struct rbnode *left, *right; + struct rbnode *next; /* for iterator stack */ +}; + + +typedef void *(*rb_alloc_func_t)(size_t); +typedef void (*rb_free_func_t)(void*); + +typedef int (*rb_cmp_func_t)(const void*, const void*); +typedef void (*rb_del_func_t)(struct rbnode*, void*); + +#define RB_KEY_ADDR (rb_cmp_func_t)(0) +#define RB_KEY_INT (rb_cmp_func_t)(1) +#define RB_KEY_STRING (rb_cmp_func_t)(3) + + +#ifdef __cplusplus +extern "C" { +#endif + +struct rbtree *rb_create(rb_cmp_func_t cmp_func); +void rb_free(struct rbtree *rb); + +int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func); +void rb_destroy(struct rbtree *rb); + +void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free); +void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func); +void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls); +/* TODO add user deep copy function */ + +void rb_clear(struct rbtree *rb); +int rb_copy(struct rbtree *dest, struct rbtree *src); + +int rb_size(struct rbtree *rb); + +int rb_insert(struct rbtree *rb, void *key, void *data); +int rb_inserti(struct rbtree *rb, int key, void *data); + +int rb_delete(struct rbtree *rb, void *key); +int rb_deletei(struct rbtree *rb, int key); + +struct rbnode *rb_find(struct rbtree *rb, void *key); +struct rbnode *rb_findi(struct rbtree *rb, int key); + +void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls); + +struct rbnode *rb_root(struct rbtree *rb); + +void rb_begin(struct rbtree *rb); +struct rbnode *rb_next(struct rbtree *rb); + +void *rb_node_key(struct rbnode *node); +int rb_node_keyi(struct rbnode *node); +void *rb_node_data(struct rbnode *node); + +#ifdef __cplusplus +} +#endif + + +#endif /* RBTREE_H_ */ -- 1.7.10.4