[37] | 1 | /* |
---|
| 2 | * code to strip triangles in a binary PLY file |
---|
| 3 | * assumes PLY file contains two elements: vertex and face data |
---|
| 4 | * replaces face data with tri-strip-count and tri-strip elements |
---|
| 5 | * becomes unhappy if any of the faces have >3 vertices |
---|
| 6 | * |
---|
| 7 | * Matt Ginzton (magi@graphics), 1/21/98 |
---|
| 8 | */ |
---|
| 9 | |
---|
| 10 | |
---|
| 11 | #include <stdio.h> |
---|
| 12 | #include <string.h> |
---|
| 13 | #include <vector> |
---|
| 14 | #include <iostream> |
---|
| 15 | #include <ply.h> |
---|
| 16 | #include <cassert> |
---|
| 17 | |
---|
| 18 | |
---|
| 19 | enum ErrorCode { |
---|
| 20 | ERR_NONE, |
---|
| 21 | ERR_PARAMS, |
---|
| 22 | ERR_MISSINGINFILE, |
---|
| 23 | ERR_INVALIDELEMENT, |
---|
| 24 | ERR_MISSINGELEMENT, |
---|
| 25 | ERR_NOTALLTRIANGLES, |
---|
| 26 | ERR_FILE, |
---|
| 27 | }; |
---|
| 28 | |
---|
| 29 | |
---|
| 30 | |
---|
| 31 | |
---|
| 32 | typedef void PlyVertex; /* we'll treat these as opaque for simplicity |
---|
| 33 | and read speed*/ |
---|
| 34 | |
---|
| 35 | |
---|
| 36 | #undef BYTE_ALIGN_FACES |
---|
| 37 | |
---|
| 38 | |
---|
| 39 | #ifdef BYTE_ALIGN_FACES |
---|
| 40 | #pragma pack (1) |
---|
| 41 | #endif |
---|
| 42 | //need this struct to be byte-aligned to match what's on disk |
---|
| 43 | //if it's not, ReadFaces does the conversion, which is slower. |
---|
| 44 | //Because STL vector class doesn't appear to like unaligned data |
---|
| 45 | //(to the tune of seg-faulting). |
---|
| 46 | typedef struct PlyFace |
---|
| 47 | { |
---|
| 48 | unsigned char nverts; |
---|
| 49 | int verts[3]; |
---|
| 50 | } Face; |
---|
| 51 | #ifdef BYTE_ALIGN_FACES |
---|
| 52 | #pragma pack (0) |
---|
| 53 | #endif |
---|
| 54 | |
---|
| 55 | typedef struct PlyStrip |
---|
| 56 | { |
---|
| 57 | int length; |
---|
| 58 | int* vertices; |
---|
| 59 | } Strip; |
---|
| 60 | |
---|
| 61 | |
---|
| 62 | ErrorCode ReadVerticesAndFaces (char* pszPlyFile, |
---|
| 63 | PlyVertex*& ppVertices, int& pnVertices, |
---|
| 64 | int& pcbVertice, std::vector<int>& faces, |
---|
| 65 | bool& bHaveStrips, bool bForce); |
---|
| 66 | ErrorCode tris_to_strips (int nvertices, const std::vector<int>& tris, |
---|
| 67 | std::vector<int>& strips); |
---|
| 68 | ErrorCode strips_to_tris(const std::vector<int> &tstrips, |
---|
| 69 | std::vector<int>& tris, int nTris = 0); |
---|
| 70 | ErrorCode WriteStrippedPlyFile (char* pszInputPlyFile, char* pszOutputFile, |
---|
| 71 | PlyVertex* pVertices, int nVertices, |
---|
| 72 | int cbVertice, std::vector<int>& strips, |
---|
| 73 | bool bStripped); |
---|
| 74 | FILE* OpenHeadedCopy (char* pszInputPlyFile, char* pszOutputFile); |
---|
| 75 | bool ReadVertices (PlyFile* ply, int nVertices, PlyVertex*& pVertices, |
---|
| 76 | int& cbVertice); |
---|
| 77 | bool ReadFaces (PlyFile* ply, int nFaces, std::vector<int>& faces); |
---|
| 78 | bool ReadStrips (PlyFile* ply, int nFaces, std::vector<int>& faces); |
---|
| 79 | bool ReadLine (FILE* file, char* buffer); |
---|
| 80 | |
---|
| 81 | // ugly global added by lucas |
---|
| 82 | bool bQuiet = false; |
---|
| 83 | |
---|
| 84 | |
---|
| 85 | int main (int argc, char **argv) |
---|
| 86 | { |
---|
| 87 | ErrorCode error; |
---|
| 88 | PlyVertex* pVertices; |
---|
| 89 | int nVertices; |
---|
| 90 | int cbVertice; |
---|
| 91 | std::vector<int> faces; |
---|
| 92 | std::vector<int> strips; |
---|
| 93 | std::vector<int>* data; |
---|
| 94 | char* pszInput = NULL; |
---|
| 95 | char* pszOutput = NULL; |
---|
| 96 | bool bWantStrips = true; |
---|
| 97 | bool bForce = false; |
---|
| 98 | bool bHaveStrips; |
---|
| 99 | |
---|
| 100 | if (argc > 1 && !strcmp (argv[1], "-h")) { |
---|
| 101 | std::cerr << "Usage: plystrip infile outfile" << std::endl; |
---|
| 102 | std::cerr << "plystrip will strip things that aren't, " |
---|
| 103 | "and unstrip things that are, stripped." << std::endl; |
---|
| 104 | std::cerr << "-s will force strip; -u will force unstrip" << std::endl; |
---|
| 105 | std::cerr << "-q runs in quiet mode." << std::endl; |
---|
| 106 | return ERR_PARAMS; |
---|
| 107 | } |
---|
| 108 | |
---|
| 109 | // Parse -args |
---|
| 110 | while (argc > 1 && argv[1][0] == '-') { |
---|
| 111 | if (!strcmp (argv[1], "-u") || !strcmp (argv[1], "-s")) { |
---|
| 112 | bWantStrips = argv[1][1] == 's'; |
---|
| 113 | bForce = true; |
---|
| 114 | ++argv; |
---|
| 115 | --argc; |
---|
| 116 | } else if (!strcmp (argv[1], "-q")) { |
---|
| 117 | bQuiet = true; |
---|
| 118 | ++argv; |
---|
| 119 | --argc; |
---|
| 120 | } else { |
---|
| 121 | std::cerr << "Error: Unhandled argument " << argv[1] << "." << std::endl; |
---|
| 122 | return ERR_PARAMS; |
---|
| 123 | } |
---|
| 124 | } |
---|
| 125 | |
---|
| 126 | if (argc > 1 && argv[1]) |
---|
| 127 | pszInput = argv[1]; |
---|
| 128 | |
---|
| 129 | if (argc > 2 && argv[2]) |
---|
| 130 | pszOutput = argv[2]; |
---|
| 131 | |
---|
| 132 | if (!bQuiet) std::cerr << "Reading input file " << pszInput << "... " << std::flush; |
---|
| 133 | error = ReadVerticesAndFaces (pszInput, pVertices, nVertices, cbVertice, |
---|
| 134 | faces, bHaveStrips, bForce); |
---|
| 135 | if (!bQuiet) std::cerr << "done." << std::endl; |
---|
| 136 | |
---|
| 137 | if (!bForce) |
---|
| 138 | bWantStrips = !bHaveStrips; |
---|
| 139 | |
---|
| 140 | switch (error) { |
---|
| 141 | case ERR_NONE: |
---|
| 142 | if (bWantStrips == bHaveStrips) { |
---|
| 143 | if (!bQuiet) { |
---|
| 144 | std::cerr << "Doing nothing really fast, " |
---|
| 145 | << "because already in correct format... " |
---|
| 146 | << "done." << std::endl; |
---|
| 147 | } |
---|
| 148 | data = &faces; |
---|
| 149 | } else { |
---|
| 150 | if (bWantStrips) |
---|
| 151 | error = tris_to_strips (nVertices, faces, strips); |
---|
| 152 | else |
---|
| 153 | error = strips_to_tris (faces, strips); |
---|
| 154 | if (ERR_NONE != error) |
---|
| 155 | return error; |
---|
| 156 | data = &strips; |
---|
| 157 | } |
---|
| 158 | break; |
---|
| 159 | |
---|
| 160 | default: |
---|
| 161 | return error; |
---|
| 162 | } |
---|
| 163 | |
---|
| 164 | if (!bQuiet) std::cerr << "Writing output file " << std::flush; |
---|
| 165 | error = WriteStrippedPlyFile (pszInput, pszOutput, pVertices, |
---|
| 166 | nVertices, cbVertice, *data, bWantStrips); |
---|
| 167 | if (!bQuiet) std::cerr << "done." << std::endl; |
---|
| 168 | if (ERR_NONE != error) |
---|
| 169 | return error; |
---|
| 170 | |
---|
| 171 | return ERR_NONE; |
---|
| 172 | } |
---|
| 173 | |
---|
| 174 | |
---|
| 175 | ErrorCode ReadVerticesAndFaces (char* pszPlyFile, |
---|
| 176 | PlyVertex*& pVertices, int& nVertices, |
---|
| 177 | int& cbVertice, std::vector<int>& faces, |
---|
| 178 | bool& bHaveStrips, bool bForce) |
---|
| 179 | { |
---|
| 180 | PlyFile* ply; |
---|
| 181 | int nElems; |
---|
| 182 | char** pElemList; |
---|
| 183 | int file_type; |
---|
| 184 | float version; |
---|
| 185 | int i; |
---|
| 186 | |
---|
| 187 | pVertices = NULL; |
---|
| 188 | |
---|
| 189 | FILE* inFile; |
---|
| 190 | if (!pszPlyFile || 0 == strcmp (pszPlyFile, "-")) |
---|
| 191 | inFile = stdin; |
---|
| 192 | else |
---|
| 193 | inFile = fopen (pszPlyFile, "r"); |
---|
| 194 | |
---|
| 195 | if (!inFile) { |
---|
| 196 | std::cerr << "input file does not exist" << std::endl; |
---|
| 197 | return ERR_MISSINGINFILE; |
---|
| 198 | } |
---|
| 199 | |
---|
| 200 | ply = ply_read (inFile, &nElems, &pElemList); |
---|
| 201 | if (!ply) { |
---|
| 202 | fclose (inFile); |
---|
| 203 | std::cerr << "input can not be read as a ply file" << std::endl; |
---|
| 204 | return ERR_FILE; |
---|
| 205 | } |
---|
| 206 | |
---|
| 207 | ply_get_info (ply, &version, &file_type); |
---|
| 208 | |
---|
| 209 | /* |
---|
| 210 | std::cerr << "ply file " << argv[1] << " is type " << file_type |
---|
| 211 | << " version " << version << "; " << nElems << " elements." << std::endl; |
---|
| 212 | */ |
---|
| 213 | |
---|
| 214 | if (nElems != 2) |
---|
| 215 | { |
---|
| 216 | std::cerr << "Only expected 2 elements (vertex and face)." << std::endl; |
---|
| 217 | return ERR_INVALIDELEMENT; |
---|
| 218 | } |
---|
| 219 | |
---|
| 220 | for (i = 0; i < nElems; i++) |
---|
| 221 | { |
---|
| 222 | char* elem_name = pElemList[i]; |
---|
| 223 | int nInstances; |
---|
| 224 | int nProps; |
---|
| 225 | PlyProperty** plist = ply_get_element_description (ply, elem_name, |
---|
| 226 | &nInstances, &nProps); |
---|
| 227 | |
---|
| 228 | if (i == 0 && !strcmp (elem_name, "vertex")) |
---|
| 229 | { |
---|
| 230 | nVertices = nInstances; |
---|
| 231 | if (!ReadVertices (ply, nVertices, pVertices, cbVertice)) |
---|
| 232 | { |
---|
| 233 | std::cerr << "Invalid format." << std::endl; |
---|
| 234 | return ERR_INVALIDELEMENT; |
---|
| 235 | } |
---|
| 236 | } |
---|
| 237 | else if (i == 1 && !strcmp (elem_name, "face")) |
---|
| 238 | { |
---|
| 239 | bHaveStrips = false; |
---|
| 240 | if (!ReadFaces (ply, nInstances, faces)) { |
---|
| 241 | std::cerr << "Not all faces are triangles, aborting" << std::endl; |
---|
| 242 | ply_close (ply); |
---|
| 243 | return ERR_NOTALLTRIANGLES; |
---|
| 244 | } |
---|
| 245 | } |
---|
| 246 | else if (i == 1 && !strcmp (elem_name, "tristrips")) |
---|
| 247 | { |
---|
| 248 | bHaveStrips = true; |
---|
| 249 | if (!ReadStrips (ply, nInstances, faces)) { |
---|
| 250 | std::cerr << "Error reading strip data" << std::endl; |
---|
| 251 | ply_close (ply); |
---|
| 252 | return ERR_INVALIDELEMENT; |
---|
| 253 | } |
---|
| 254 | } |
---|
| 255 | else |
---|
| 256 | { |
---|
| 257 | std::cerr << "Unknown element " << elem_name |
---|
| 258 | << " (at pos " << i << "), aborting" << std::endl; |
---|
| 259 | ply_close (ply); |
---|
| 260 | return ERR_INVALIDELEMENT; |
---|
| 261 | } |
---|
| 262 | } |
---|
| 263 | |
---|
| 264 | ply_close (ply); |
---|
| 265 | |
---|
| 266 | if (!pVertices || !faces.size()) |
---|
| 267 | { |
---|
| 268 | std::cerr << "Did not find both vertices and faces." << std::endl; |
---|
| 269 | return ERR_MISSINGELEMENT; |
---|
| 270 | } |
---|
| 271 | |
---|
| 272 | return ERR_NONE; |
---|
| 273 | } |
---|
| 274 | |
---|
| 275 | |
---|
| 276 | ErrorCode WriteStrippedPlyFile (char* pszInputPlyFile, char* pszOutputFile, |
---|
| 277 | PlyVertex* pVertices, int nVertices, |
---|
| 278 | int cbVertice, std::vector<int>& strips, |
---|
| 279 | bool bStripped) |
---|
| 280 | { |
---|
| 281 | FILE* outfile; |
---|
| 282 | |
---|
| 283 | outfile = OpenHeadedCopy (pszInputPlyFile, pszOutputFile); |
---|
| 284 | if (outfile == NULL) { |
---|
| 285 | std::cerr << "The ply header could not be written." << std::endl; |
---|
| 286 | return ERR_PARAMS; |
---|
| 287 | } |
---|
| 288 | |
---|
| 289 | if (bStripped) |
---|
| 290 | fprintf (outfile, "element tristrips 1\n" |
---|
| 291 | "property list int int vertex_indices\n"); |
---|
| 292 | else |
---|
| 293 | fprintf (outfile, "element face %d\n" |
---|
| 294 | "property list uchar int vertex_indices\n", strips.size() / 3); |
---|
| 295 | fprintf (outfile, "end_header\n"); |
---|
| 296 | |
---|
| 297 | if (nVertices != fwrite (pVertices, cbVertice, nVertices, outfile)) { |
---|
| 298 | std::cerr << "Error writing vertices." << std::endl; |
---|
| 299 | fclose (outfile); |
---|
| 300 | return ERR_FILE; |
---|
| 301 | } |
---|
| 302 | |
---|
| 303 | if (bStripped) { |
---|
| 304 | int num = strips.size(); |
---|
| 305 | fwrite (&num, sizeof(int), 1, outfile); |
---|
| 306 | fwrite (&strips[0], sizeof(int), num, outfile); |
---|
| 307 | } else { |
---|
| 308 | char c = 3; |
---|
| 309 | for (int i = 0; i < strips.size(); i += 3) { |
---|
| 310 | fwrite (&c, sizeof(char), 1, outfile); |
---|
| 311 | fwrite (&strips[i], sizeof(int), 3, outfile); |
---|
| 312 | } |
---|
| 313 | } |
---|
| 314 | |
---|
| 315 | fclose (outfile); |
---|
| 316 | |
---|
| 317 | return ERR_NONE; |
---|
| 318 | } |
---|
| 319 | |
---|
| 320 | |
---|
| 321 | FILE* OpenHeadedCopy (char* pszInputPlyFile, char* pszOutputFile) |
---|
| 322 | { |
---|
| 323 | FILE* infile; |
---|
| 324 | FILE* outfile; |
---|
| 325 | |
---|
| 326 | if (pszOutputFile) { |
---|
| 327 | if (!bQuiet) std::cerr << pszOutputFile << "... " << std::flush; |
---|
| 328 | outfile = fopen (pszOutputFile, "w"); |
---|
| 329 | } else { |
---|
| 330 | if (!bQuiet) std::cerr << "(stdout)... " << std::flush; |
---|
| 331 | outfile = stdout; |
---|
| 332 | } |
---|
| 333 | |
---|
| 334 | if (!pszInputPlyFile || 0 == strcmp (pszInputPlyFile, "-")) { |
---|
| 335 | infile = stdin; |
---|
| 336 | // BUGBUG this doesn't work: have to find some other way to read the |
---|
| 337 | // header twice from stdin |
---|
| 338 | rewind (infile); |
---|
| 339 | } else { |
---|
| 340 | infile = fopen (pszInputPlyFile, "r"); |
---|
| 341 | |
---|
| 342 | } |
---|
| 343 | if (infile == NULL) { |
---|
| 344 | std::cerr << "Unable to open input file!" << std::endl; |
---|
| 345 | return NULL; |
---|
| 346 | } |
---|
| 347 | |
---|
| 348 | if (outfile != NULL) { |
---|
| 349 | char szLine[400]; |
---|
| 350 | while (true) { |
---|
| 351 | |
---|
| 352 | if (!ReadLine (infile, szLine)) { |
---|
| 353 | std::cerr << "Read error on input!" << std::endl; |
---|
| 354 | fclose (outfile); |
---|
| 355 | outfile = NULL; |
---|
| 356 | break; |
---|
| 357 | } |
---|
| 358 | |
---|
| 359 | if (strncmp (szLine, "element face", 12) |
---|
| 360 | && strncmp (szLine, "element tristrips", 17)) { |
---|
| 361 | // copy verbatim |
---|
| 362 | fprintf (outfile, szLine); |
---|
| 363 | } else { |
---|
| 364 | // we'll print the rest ourselves |
---|
| 365 | break; |
---|
| 366 | } |
---|
| 367 | } |
---|
| 368 | } |
---|
| 369 | |
---|
| 370 | fclose (infile); |
---|
| 371 | return outfile; |
---|
| 372 | } |
---|
| 373 | |
---|
| 374 | |
---|
| 375 | int CalcPropertySize (PlyElement* elem) |
---|
| 376 | { |
---|
| 377 | int i; |
---|
| 378 | int size = 0; |
---|
| 379 | int type; |
---|
| 380 | |
---|
| 381 | int SizeOf[] = { 0, 1, 2, 4, 1, 2, 4, 4, 8 }; |
---|
| 382 | for (i = 0; i < elem->nprops; i++) |
---|
| 383 | { |
---|
| 384 | type = elem->props[i]->external_type; |
---|
| 385 | if (type <= PLY_START_TYPE || type >= PLY_END_TYPE) |
---|
| 386 | { |
---|
| 387 | std::cerr << "Unknown type " << type << " found for property " |
---|
| 388 | << elem->props[i]->name << " in elem " << elem->name << std::endl; |
---|
| 389 | return 0; |
---|
| 390 | } |
---|
| 391 | size += SizeOf[type]; |
---|
| 392 | } |
---|
| 393 | |
---|
| 394 | return size; |
---|
| 395 | } |
---|
| 396 | |
---|
| 397 | |
---|
| 398 | bool ReadVertices (PlyFile* ply, int nVertices, |
---|
| 399 | PlyVertex*& pVertices, int& cbVertice) |
---|
| 400 | { |
---|
| 401 | PlyVertex* vchunk; |
---|
| 402 | int nr; |
---|
| 403 | |
---|
| 404 | /* for now, assume that vertices are first element in plyfile. */ |
---|
| 405 | PlyElement* elem = ply->elems[0]; |
---|
| 406 | if (strcmp (elem->name, "vertex")) |
---|
| 407 | { |
---|
| 408 | std::cerr << "Bad element name '" << elem->name << "'" << std::endl; |
---|
| 409 | return false; |
---|
| 410 | } |
---|
| 411 | if (elem->size > 0) |
---|
| 412 | cbVertice = elem->size; |
---|
| 413 | else |
---|
| 414 | cbVertice = CalcPropertySize (elem); |
---|
| 415 | |
---|
| 416 | vchunk = (PlyVertex*) malloc (cbVertice * nVertices); |
---|
| 417 | |
---|
| 418 | if (nVertices != (nr = fread (vchunk, cbVertice, nVertices, ply->fp))) |
---|
| 419 | { |
---|
| 420 | std::cerr << "Expected " << nVertices << " vertices, read " << nr << std::endl; |
---|
| 421 | return false; |
---|
| 422 | } |
---|
| 423 | |
---|
| 424 | pVertices = vchunk; |
---|
| 425 | return true; |
---|
| 426 | } |
---|
| 427 | |
---|
| 428 | |
---|
| 429 | bool ReadFaces (PlyFile* ply, int nFaces, std::vector<int>& faces) |
---|
| 430 | { |
---|
| 431 | struct { |
---|
| 432 | unsigned char padding[3]; |
---|
| 433 | unsigned char nv; |
---|
| 434 | int vert[3]; |
---|
| 435 | } diskvert; |
---|
| 436 | |
---|
| 437 | assert (sizeof (diskvert) == 16); |
---|
| 438 | faces.reserve (nFaces * 3); |
---|
| 439 | |
---|
| 440 | for (int iF = 0; iF < nFaces; iF++) { |
---|
| 441 | if (1 != fread (((char*)&diskvert) + 3, sizeof(diskvert) - 3, 1, ply->fp)) |
---|
| 442 | return false; |
---|
| 443 | |
---|
| 444 | assert (diskvert.nv == 3); |
---|
| 445 | if (diskvert.nv != 3) |
---|
| 446 | return false; |
---|
| 447 | |
---|
| 448 | for (int iV = 0; iV < 3; iV++) |
---|
| 449 | faces.push_back (diskvert.vert[iV]); |
---|
| 450 | } |
---|
| 451 | |
---|
| 452 | return true; |
---|
| 453 | } |
---|
| 454 | |
---|
| 455 | |
---|
| 456 | bool ReadStrips (PlyFile* ply, int nFaces, std::vector<int>& faces) |
---|
| 457 | { |
---|
| 458 | int count; |
---|
| 459 | fread (&count, sizeof(count), 1, ply->fp); |
---|
| 460 | faces = std::vector<int> (count, 0); |
---|
| 461 | |
---|
| 462 | // Used to say: |
---|
| 463 | // return (count == fread (&faces.begin(), sizeof(int), count, ply->fp)); |
---|
| 464 | // but begin is an iterator. On the other hand, is it legal to read a |
---|
| 465 | // vector in this manner, using front or other? B. Curless -- 8/15/05 |
---|
| 466 | |
---|
| 467 | // return (count == fread (&faces.begin(), sizeof(int), count, ply->fp)); |
---|
| 468 | // return (count == fread (&faces.front(), sizeof(int), count, ply->fp)); |
---|
| 469 | return (count == fread (&(*(faces.begin())), sizeof(int), count, ply->fp)); |
---|
| 470 | } |
---|
| 471 | |
---|
| 472 | |
---|
| 473 | bool ReadLine (FILE* file, char* buffer) |
---|
| 474 | { |
---|
| 475 | int c; |
---|
| 476 | |
---|
| 477 | while ((c = getc(file)) != EOF) |
---|
| 478 | { |
---|
| 479 | *buffer++ = (char)c; |
---|
| 480 | if (c == '\n') |
---|
| 481 | { |
---|
| 482 | *buffer = 0; /*terminate*/ |
---|
| 483 | return true; |
---|
| 484 | } |
---|
| 485 | } |
---|
| 486 | |
---|
| 487 | return false; |
---|
| 488 | } |
---|
| 489 | |
---|
| 490 | |
---|
| 491 | |
---|
| 492 | |
---|
| 493 | ////////////////////////////////////////////////////////////////////// |
---|
| 494 | // |
---|
| 495 | // smr's tstrip code |
---|
| 496 | // |
---|
| 497 | ////////////////////////////////////////////////////////////////////// |
---|
| 498 | |
---|
| 499 | typedef int* adjacentfacelist; |
---|
| 500 | |
---|
| 501 | adjacentfacelist* |
---|
| 502 | TriMesh_FindAdjacentFaces (int numvertices, |
---|
| 503 | const std::vector<int>& faces, |
---|
| 504 | int*& numadjacentfaces) |
---|
| 505 | { |
---|
| 506 | if (!bQuiet) std::cerr << " Computing vtx->face mappings..." << std::flush; |
---|
| 507 | |
---|
| 508 | // Step I - compute numadjacentfaces |
---|
| 509 | numadjacentfaces = new int[numvertices]; |
---|
| 510 | memset(numadjacentfaces, 0, numvertices*sizeof(int)); |
---|
| 511 | |
---|
| 512 | int numfaces = faces.size(); |
---|
| 513 | int i; |
---|
| 514 | for (i = 0; i < numfaces; i++) { |
---|
| 515 | numadjacentfaces[faces[i]]++; |
---|
| 516 | } |
---|
| 517 | |
---|
| 518 | // allocate one chunk of memory for all adjacent face lists |
---|
| 519 | // total number of adjacent faces is numfaces |
---|
| 520 | int* adjacentfacedata = new int [numfaces]; |
---|
| 521 | // this pointer will be incremented as needed but adjacentfaces[0] |
---|
| 522 | // will always point to the beginning so it can later be freed |
---|
| 523 | |
---|
| 524 | // Step II - compute the actual vertex->tri lists... |
---|
| 525 | adjacentfacelist* adjacentfaces = new adjacentfacelist[numvertices]; |
---|
| 526 | for (i = 0; i < numvertices; i++) { |
---|
| 527 | adjacentfaces[i] = adjacentfacedata; |
---|
| 528 | adjacentfacedata += numadjacentfaces[i]; |
---|
| 529 | |
---|
| 530 | //for (int j=0; j<numadjacentfaces[i]; j++) |
---|
| 531 | // adjacentfaces[i][j] = numfaces; |
---|
| 532 | } |
---|
| 533 | |
---|
| 534 | assert (adjacentfacedata == adjacentfaces[0] + numfaces); |
---|
| 535 | for (int* afdp = adjacentfaces[0]; afdp < adjacentfacedata; afdp++) |
---|
| 536 | *afdp = numfaces; |
---|
| 537 | |
---|
| 538 | for (i = 0; i < numfaces; i++) { |
---|
| 539 | int *p = adjacentfaces[faces[i]]; |
---|
| 540 | while (*p != numfaces) |
---|
| 541 | p++; |
---|
| 542 | // snap to nearest multiple of 3, the start of tri data for that face |
---|
| 543 | *p = (i/3) * 3; |
---|
| 544 | } |
---|
| 545 | |
---|
| 546 | return adjacentfaces; |
---|
| 547 | } |
---|
| 548 | |
---|
| 549 | |
---|
| 550 | |
---|
| 551 | |
---|
| 552 | #define FOR_EACH_VERTEX_OF_FACE(i,j) \ |
---|
| 553 | for (int jtmp = 0, j = faces[i]; \ |
---|
| 554 | jtmp < 3; \ |
---|
| 555 | jtmp++, j = faces[i + jtmp]) |
---|
| 556 | |
---|
| 557 | #define FOR_EACH_ADJACENT_FACE(i,j) \ |
---|
| 558 | for (int jtmp=0, j = adjacentfaces[i][0]; \ |
---|
| 559 | jtmp < numadjacentfaces[i]; \ |
---|
| 560 | jtmp++, j = adjacentfaces[i][jtmp]) |
---|
| 561 | |
---|
| 562 | static bool* done = NULL; |
---|
| 563 | static int* stripsp = NULL; |
---|
| 564 | static int* numadjacentfaces = NULL; |
---|
| 565 | static adjacentfacelist* adjacentfaces = NULL; |
---|
| 566 | static const int* faces = NULL; |
---|
| 567 | static int nstrips = 0; |
---|
| 568 | static int nEvilTriangles; |
---|
| 569 | |
---|
| 570 | |
---|
| 571 | |
---|
| 572 | // Figure out the next triangle we're headed for... |
---|
| 573 | static inline int |
---|
| 574 | Tstrip_Next_Tri(int tri, int v1, int v2) |
---|
| 575 | { |
---|
| 576 | FOR_EACH_ADJACENT_FACE(v1, f1) { |
---|
| 577 | if ((f1 == tri) || done[f1/3]) |
---|
| 578 | continue; |
---|
| 579 | FOR_EACH_ADJACENT_FACE(v2, f2) { |
---|
| 580 | if ((f2 == tri) || done[f2/3]) |
---|
| 581 | continue; |
---|
| 582 | if (f1 == f2) |
---|
| 583 | return f1; |
---|
| 584 | } |
---|
| 585 | } |
---|
| 586 | |
---|
| 587 | return -1; |
---|
| 588 | } |
---|
| 589 | |
---|
| 590 | // Build a whole strip of triangles, as long as possible... |
---|
| 591 | static void Tstrip_Crawl(int v1, int v2, int v3, |
---|
| 592 | int next) |
---|
| 593 | { |
---|
| 594 | // Insert the first tri... |
---|
| 595 | *stripsp++ = v1; |
---|
| 596 | *stripsp++ = v2; |
---|
| 597 | *stripsp++ = v3; |
---|
| 598 | |
---|
| 599 | int vlast1 = v3; |
---|
| 600 | int vlast2 = v2; |
---|
| 601 | |
---|
| 602 | bool shouldbeflipped = true; |
---|
| 603 | |
---|
| 604 | // Main loop... |
---|
| 605 | do { |
---|
| 606 | // Find the next vertex |
---|
| 607 | int vnext; |
---|
| 608 | FOR_EACH_VERTEX_OF_FACE(next,vnext_tmp) { |
---|
| 609 | if ((vnext_tmp == vlast1) || (vnext_tmp == vlast2)) |
---|
| 610 | continue; |
---|
| 611 | vnext = vnext_tmp; |
---|
| 612 | break; |
---|
| 613 | } |
---|
| 614 | |
---|
| 615 | bool thisflipped = true; |
---|
| 616 | if ((faces[next+0] == vlast2) && |
---|
| 617 | (faces[next+1] == vlast1) && |
---|
| 618 | (faces[next+2] == vnext)) |
---|
| 619 | thisflipped = false; |
---|
| 620 | if ((faces[next+2] == vlast2) && |
---|
| 621 | (faces[next+0] == vlast1) && |
---|
| 622 | (faces[next+1] == vnext)) |
---|
| 623 | thisflipped = false; |
---|
| 624 | if ((faces[next+1] == vlast2) && |
---|
| 625 | (faces[next+2] == vlast1) && |
---|
| 626 | (faces[next+0] == vnext)) |
---|
| 627 | thisflipped = false; |
---|
| 628 | |
---|
| 629 | if (thisflipped != shouldbeflipped) { |
---|
| 630 | if (nEvilTriangles-- > 0 && !bQuiet) { |
---|
| 631 | std::cerr << "Ugh! As Alice would say, this triangle \"" |
---|
| 632 | << "goes the wrong way\"!" << std::endl |
---|
| 633 | << " (Ran into inconsistent triangle orientation " |
---|
| 634 | << "during tstrip generation)" << std::endl |
---|
| 635 | << " (This triangle #" << next << ")" << std::endl << std::endl; |
---|
| 636 | } |
---|
| 637 | goto bail; |
---|
| 638 | } |
---|
| 639 | |
---|
| 640 | |
---|
| 641 | // Record it |
---|
| 642 | |
---|
| 643 | *stripsp++ = vnext; |
---|
| 644 | vlast2 = vlast1; |
---|
| 645 | vlast1 = vnext; |
---|
| 646 | done[next/3] = true; |
---|
| 647 | shouldbeflipped = !shouldbeflipped; |
---|
| 648 | |
---|
| 649 | // Try to find the next tri |
---|
| 650 | } while ((next = Tstrip_Next_Tri(next, vlast1, vlast2)) != -1); |
---|
| 651 | |
---|
| 652 | bail: |
---|
| 653 | // OK, done. Mark end of strip |
---|
| 654 | *stripsp++ = -1; |
---|
| 655 | ++nstrips; |
---|
| 656 | } |
---|
| 657 | |
---|
| 658 | // Begin a tstrip, starting with triangle tri |
---|
| 659 | // tri is ordinal, not index (counts by 1) |
---|
| 660 | static void Tstrip_Bootstrap(int tri) |
---|
| 661 | { |
---|
| 662 | done[tri] = true; |
---|
| 663 | |
---|
| 664 | // Find two vertices with which to start. |
---|
| 665 | // We do only a bit of lookahead, starting with vertices that will |
---|
| 666 | // let us form a strip of length at least 2... |
---|
| 667 | |
---|
| 668 | tri *= 3; |
---|
| 669 | int vert1 = faces[tri]; |
---|
| 670 | int vert2 = faces[tri+1]; |
---|
| 671 | int vert3 = faces[tri+2]; |
---|
| 672 | |
---|
| 673 | // Try vertices 1 and 2... |
---|
| 674 | int nextface = Tstrip_Next_Tri(tri, vert1, vert2); |
---|
| 675 | if (nextface != -1) { |
---|
| 676 | Tstrip_Crawl(vert3, vert1, vert2, nextface); |
---|
| 677 | return; |
---|
| 678 | } |
---|
| 679 | |
---|
| 680 | // Try vertices 2 and 3... |
---|
| 681 | nextface = Tstrip_Next_Tri(tri, vert2, vert3); |
---|
| 682 | if (nextface != -1) { |
---|
| 683 | Tstrip_Crawl(vert1, vert2, vert3, nextface); |
---|
| 684 | return; |
---|
| 685 | } |
---|
| 686 | |
---|
| 687 | // Try vertices 3 and 1... |
---|
| 688 | nextface = Tstrip_Next_Tri(tri, vert3, vert1); |
---|
| 689 | if (nextface != -1) { |
---|
| 690 | Tstrip_Crawl(vert2, vert3, vert1, nextface); |
---|
| 691 | return; |
---|
| 692 | } |
---|
| 693 | |
---|
| 694 | // OK, nothing we can do. Do a single-triangle-long tstrip. |
---|
| 695 | *stripsp++ = vert1; |
---|
| 696 | *stripsp++ = vert2; |
---|
| 697 | *stripsp++ = vert3; |
---|
| 698 | *stripsp++ = -1; |
---|
| 699 | ++nstrips; |
---|
| 700 | } |
---|
| 701 | |
---|
| 702 | |
---|
| 703 | static int *Build_Tstrips(int numvertices, |
---|
| 704 | const std::vector<int>& tris, |
---|
| 705 | int*& endstrips, |
---|
| 706 | int& outNstrips) |
---|
| 707 | { |
---|
| 708 | adjacentfaces = TriMesh_FindAdjacentFaces |
---|
| 709 | (numvertices, tris, numadjacentfaces); |
---|
| 710 | |
---|
| 711 | if (!bQuiet) std::cerr << " stripping... " << std::flush; |
---|
| 712 | int numfaces = tris.size() / 3; |
---|
| 713 | |
---|
| 714 | // Allocate more than enough memory |
---|
| 715 | int* strips = new int [4*numfaces+1]; |
---|
| 716 | stripsp = strips; |
---|
| 717 | nEvilTriangles = 10; |
---|
| 718 | |
---|
| 719 | // Allocate array to record what triangles we've already done |
---|
| 720 | done = new bool[numfaces]; |
---|
| 721 | memset(done, 0, numfaces*sizeof(bool)); |
---|
| 722 | faces = &tris[0]; |
---|
| 723 | nstrips = 0; |
---|
| 724 | |
---|
| 725 | // Build the tstrips |
---|
| 726 | for (int i = 0; i < numfaces; i++) { |
---|
| 727 | if (!done[i]) |
---|
| 728 | Tstrip_Bootstrap (i); |
---|
| 729 | } |
---|
| 730 | endstrips = stripsp; |
---|
| 731 | outNstrips = nstrips; |
---|
| 732 | |
---|
| 733 | if (nEvilTriangles < 0 && !bQuiet) { |
---|
| 734 | std::cerr << "And there were " << -nEvilTriangles |
---|
| 735 | << " more evil triangles for which no warnings were printed." |
---|
| 736 | << std::endl << std::endl; |
---|
| 737 | } |
---|
| 738 | |
---|
| 739 | // cleanup global arrays |
---|
| 740 | delete [] done; done = NULL; |
---|
| 741 | delete [] numadjacentfaces; numadjacentfaces = NULL; |
---|
| 742 | delete [] adjacentfaces[0]; // ptr to one chunk of data for all |
---|
| 743 | delete [] adjacentfaces; adjacentfaces = NULL; |
---|
| 744 | stripsp = NULL; |
---|
| 745 | faces = NULL; |
---|
| 746 | |
---|
| 747 | if (!bQuiet) std::cerr << " done." << std::endl; |
---|
| 748 | return strips; |
---|
| 749 | } |
---|
| 750 | |
---|
| 751 | |
---|
| 752 | ErrorCode |
---|
| 753 | tris_to_strips(int numvertices, |
---|
| 754 | const std::vector<int>& tris, |
---|
| 755 | std::vector<int>& tstripinds) |
---|
| 756 | { |
---|
| 757 | if (!bQuiet) |
---|
| 758 | std::cerr << "Tstripping " << tris.size()/3 << " triangles (" |
---|
| 759 | << tris.size() << " vertices)..." << std::endl; |
---|
| 760 | |
---|
| 761 | int *strips, *end; |
---|
| 762 | int nStrips; |
---|
| 763 | strips = Build_Tstrips (numvertices, tris, end, nStrips); |
---|
| 764 | |
---|
| 765 | tstripinds.clear(); |
---|
| 766 | |
---|
| 767 | // this is a hair faster... |
---|
| 768 | //tstripinds.reserve (end-strips); |
---|
| 769 | //memcpy (&tstripinds[0], strips, 4*(end-strips)); |
---|
| 770 | |
---|
| 771 | // but this is legal :) |
---|
| 772 | tstripinds.insert (tstripinds.end(), strips, end); |
---|
| 773 | |
---|
| 774 | if (!bQuiet) |
---|
| 775 | std::cerr << "Tstrip results: " << nstrips << " strips (" |
---|
| 776 | << tstripinds.size() - nStrips << " vertices, avg. length " |
---|
| 777 | << ((float)tstripinds.size()/nStrips) - 3 << ")." << std::endl; |
---|
| 778 | |
---|
| 779 | return ERR_NONE; |
---|
| 780 | } |
---|
| 781 | |
---|
| 782 | |
---|
| 783 | |
---|
| 784 | |
---|
| 785 | |
---|
| 786 | ErrorCode |
---|
| 787 | strips_to_tris(const std::vector<int> &tstrips, |
---|
| 788 | std::vector<int>& tris, int nTris) |
---|
| 789 | { |
---|
| 790 | assert(tstrips.back() == -1); |
---|
| 791 | tris.clear(); |
---|
| 792 | if (!nTris) |
---|
| 793 | nTris = tstrips.size() * 3; // estimate |
---|
| 794 | tris.reserve (nTris); |
---|
| 795 | |
---|
| 796 | if (!bQuiet) std::cerr << "Reyhdrating tris... " << std::flush; |
---|
| 797 | |
---|
| 798 | std::vector<int>::const_iterator vert; |
---|
| 799 | for (vert = tstrips.begin(); vert != tstrips.end(); vert++) { |
---|
| 800 | while (*vert == -1) { // handle 0-length strips |
---|
| 801 | ++vert; |
---|
| 802 | if (vert == tstrips.end()) break; |
---|
| 803 | } |
---|
| 804 | if (vert == tstrips.end()) break; |
---|
| 805 | |
---|
| 806 | vert += 2; //we'll look backwards at these |
---|
| 807 | |
---|
| 808 | int dir = 0; |
---|
| 809 | while (*vert != -1) { |
---|
| 810 | tris.push_back(vert[-2 + dir]); |
---|
| 811 | tris.push_back(vert[-1 - dir]); |
---|
| 812 | tris.push_back(vert[0]); |
---|
| 813 | vert++; |
---|
| 814 | dir ^= 1; |
---|
| 815 | } |
---|
| 816 | } |
---|
| 817 | |
---|
| 818 | if (!bQuiet) std::cerr << tris.size() << " tris. done." << std::endl; |
---|
| 819 | |
---|
| 820 | return ERR_NONE; |
---|
| 821 | } |
---|