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 | } |
---|