b311480e |
1 | // Copyright (c) 1999-2012 OPEN CASCADE SAS |
2 | // |
3 | // The content of this file is subject to the Open CASCADE Technology Public |
4 | // License Version 6.5 (the "License"). You may not use the content of this file |
5 | // except in compliance with the License. Please obtain a copy of the License |
6 | // at http://www.opencascade.org and read it completely before using this file. |
7 | // |
8 | // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its |
9 | // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France. |
10 | // |
11 | // The Original Code and all software distributed under the License is |
12 | // distributed on an "AS IS" basis, without warranty of any kind, and the |
13 | // Initial Developer hereby disclaims all such warranties, including without |
14 | // limitation, any warranties of merchantability, fitness for a particular |
15 | // purpose or non-infringement. Please see the License for the specific terms |
16 | // and conditions governing the rights and limitations under the License. |
17 | |
7fd59977 |
18 | #include <Graphic3d_Strips.ixx> |
19 | |
20 | /* |
21 | TRIANGLE_STRIP |
22 | */ |
23 | |
24 | |
25 | /* |
26 | Algorithm to find Triangle-Strips in a triangles graph. |
27 | |
28 | A triangle graph is a set of vertices (numbered from 1 to nvertices) |
29 | and of triangles (numbered from 1 to ntriangles), each triangle is a |
30 | triplet of vertices. |
31 | |
32 | A triangle-strip is a strip of adjacent triangles that can be |
33 | described as a list of vertices. The strip v1,v2,v3,v4,v5,v6,... |
34 | describes the triangles (v1,v2,v3), (v2,v3,v4), (v3,v4,v5), (v4,v5,v6) |
35 | ... |
36 | |
37 | Triangle-strips are an economic way to pass around triangles to a |
38 | hardware shader as they require an average of one vertex per triangle. |
39 | |
40 | The purpose of this algorithm is to break a triangle graph into a |
41 | (minimal cardinality) set of triangle strips. |
42 | |
43 | It is purely topological, triangles are triplets of long integers. |
44 | There is no limit of size, memory is allocated from free store. |
45 | The quantity allocated during the algorithm is about |
46 | 66 * t bytes where t is the number of triangles. |
47 | |
48 | ( the description of the algorithm can be found at the end of the file |
49 | starting with "COMMENTS") |
50 | */ |
51 | |
52 | |
53 | /*******************************/ |
54 | /* GLOBAL TYPES AND VARIABLES */ |
55 | /*******************************/ |
56 | |
57 | #include <stddef.h> |
58 | #include <Standard.hxx> |
59 | |
60 | #define NULLTRIANGLE 0 |
61 | #define DELETED 0 |
62 | |
63 | /* the array of triangles is the basic data structure to folow strips |
64 | it is allocated from free store */ |
65 | typedef struct { |
66 | int v[3]; /* the three vertices of the triangle */ |
67 | int tn[3]; /* neighbouring triangles */ |
68 | int ivn[3]; /* the index of the neigbouring vertex */ |
69 | int state; /* the last strip crossing the triangle, 0 means deleted */ |
70 | } triangle; |
71 | |
72 | triangle *trianglesptr; |
73 | int TrianglesPtrSize; |
74 | |
75 | /* remarks about the above structure : |
76 | Triangles are ranging from 1 two nbtriangles, triangle 0 will always |
77 | be deleted. |
78 | A state of 0 means the triangle is deleted from the graph. |
79 | The vertices are v[0],v[1],v[2] |
80 | To get the neigbour of the triangle on the other side of the edge |
81 | v[i],v[j] just pick tn[i+j-1] and ivn[i+j-1]. |
82 | If tn[i+j-1] is 0 there is no neighbour. |
83 | ivn is the index (0,1,2) of the vertex of the neighbouring triangle |
84 | tn[] which is not shared with this triangle. |
85 | */ |
86 | |
87 | /* the number of triangles */ |
88 | int nbtriangles; |
89 | |
90 | /* a strip is described by a triangle and the index of the two last |
91 | NBVERTICES of the triangle in the strip */ |
92 | typedef struct { |
93 | int t; /* the triangle */ |
94 | int iv1,iv2; /* the last NBVERTICES of t in the strip, in 0,1,2 */ |
95 | } stript; |
96 | |
97 | /* the current strip position is saved in this variable */ |
98 | /* between calls to to GET_VERTEX */ |
99 | static stript current_stript; |
100 | |
101 | /* this index is used to label the last strip under exploration */ |
102 | static int last_stript; |
103 | |
104 | /* tell this dumb compiler that stript_next returns nothing */ |
105 | void stript_next(stript *st); |
106 | int stript_score(stript* pstrip, int *plength); |
107 | |
108 | /********************************************************************/ |
109 | /* */ |
110 | /* STRIPT_INIT : get data and build the triangles array */ |
111 | /* */ |
112 | /********************************************************************/ |
113 | |
114 | void Graphic3d_Strips :: STRIPT_INIT ( const Standard_Integer NBVERTICES, |
115 | const TColStd_Array1OfInteger& TABTRIANGLES ) |
116 | { |
117 | /* In order to build the triangles array we will use a temporary |
118 | array : edges. This array is of length NBVERTICES. Each entry is a |
119 | pointer to a list of structures of the type edge. This structure |
120 | describes an edge by : the second vertex of the edge and the two |
121 | triangles adjacent to the edge, the starting vertex of the edge is the |
122 | entry of the array edges. The smallest vertex index of an edge is used |
123 | to index it in the edges array */ |
124 | |
125 | |
126 | int NBTRIANG = (int) TABTRIANGLES.Length() / 3; |
127 | |
128 | typedef struct edg { |
129 | struct edg *next; /* next edge in the list for a vertex */ |
130 | int v; /* the second vertex of the edge */ |
131 | int tn[2]; /* neighbour triangles */ |
132 | int ivn[2]; /* index of third vertex of neighbour triangles */ |
133 | } edge; |
134 | |
135 | edge **edges; |
136 | edge *cedge; |
137 | int ivert,triang; |
138 | int vmin,vmax; |
139 | int ivthird; |
140 | int TedgesSize; |
141 | |
142 | int i,j; |
143 | |
144 | /* copy the number and initialize a few */ |
145 | nbtriangles = NBTRIANG; |
146 | last_stript = 1; |
147 | |
148 | /* allocate the array edges |
149 | vertices are ranging from 1 to NBVERTICES */ |
150 | TedgesSize = (NBVERTICES+1) * sizeof(edge*); |
151 | edges = (edge**) Standard::Allocate(TedgesSize); |
152 | for (ivert=0;ivert<= NBVERTICES; ivert++) { |
153 | edges[ivert] = NULL; |
154 | } |
155 | |
156 | /* allocate the array triangles from 0 to nbtriangles */ |
157 | TrianglesPtrSize = (nbtriangles+1)*sizeof(triangle); |
158 | trianglesptr = (triangle*) Standard::Allocate (TrianglesPtrSize); |
159 | trianglesptr[0].state = DELETED; |
160 | trianglesptr[0].tn[0] = NULLTRIANGLE; |
161 | trianglesptr[0].tn[1] = NULLTRIANGLE; |
162 | trianglesptr[0].tn[2] = NULLTRIANGLE; |
163 | trianglesptr[0].ivn[0] = 0; |
164 | trianglesptr[0].ivn[1] = 0; |
165 | trianglesptr[0].ivn[2] = 0; |
166 | |
167 | |
168 | /* copy the triangles into the arrays */ |
169 | for (triang=1;triang<=nbtriangles;triang++) { |
170 | |
171 | /* copy the vertices */ |
172 | trianglesptr[triang].state = 1; |
173 | for (j=0;j<3;j++) |
174 | trianglesptr[triang].v[j] = TABTRIANGLES(3*(triang-1)+j+1); |
175 | |
176 | /* insert the edges in the edges array */ |
177 | for (j=0;j<3;j++) { |
178 | if (trianglesptr[triang].v[j] <= trianglesptr[triang].v[(j+1)%3]) |
179 | { |
180 | vmin = trianglesptr[triang].v[j]; |
181 | vmax = trianglesptr[triang].v[(j+1)%3]; |
182 | } |
183 | else |
184 | { |
185 | vmax = trianglesptr[triang].v[j]; |
186 | vmin = trianglesptr[triang].v[(j+1)%3]; |
187 | } |
188 | ivthird = (j+2)%3; |
189 | |
190 | /* the edge is inserted in the array at the entry for the |
191 | smallest vertex */ |
192 | |
193 | /* first search if there is an entry for this edge */ |
194 | cedge = edges[vmin]; |
195 | while(cedge != NULL) { |
196 | if (cedge->v == vmax) |
197 | break; |
198 | cedge = cedge->next; |
199 | } |
200 | /* if the edge was not found, create it */ |
201 | if (cedge == NULL) { |
202 | cedge = (edge*) Standard::Allocate (sizeof(edge)); |
203 | cedge->next = edges[vmin]; |
204 | edges[vmin] = cedge; |
205 | cedge->v = vmax; |
206 | cedge->tn[0] = triang; |
207 | cedge->ivn[0] = ivthird; |
208 | cedge->tn[1] = 0; |
209 | cedge->ivn[1] = 0; |
210 | } |
211 | else { |
212 | cedge->tn[1] = triang; |
213 | cedge->ivn[1] = ivthird; |
214 | } |
215 | } |
216 | } |
217 | |
218 | /* now complete the triangles array (neighbours) using the edges */ |
219 | /* array */ |
220 | |
221 | for (triang=1;triang<=nbtriangles;triang++) { |
222 | /* on each edge of the triangle : find the neighbour */ |
223 | for (j=0;j<3;j++) { |
224 | if (trianglesptr[triang].v[j] <= trianglesptr[triang].v[(j+1)%3]) { |
225 | vmin = trianglesptr[triang].v[j]; |
226 | vmax = trianglesptr[triang].v[(j+1)%3]; |
227 | } |
228 | else { |
229 | vmax = trianglesptr[triang].v[j]; |
230 | vmin = trianglesptr[triang].v[(j+1)%3]; |
231 | } |
232 | |
233 | /* search the entry for the edge */ |
234 | cedge = edges[vmin]; |
235 | while(cedge->v != vmax) { |
236 | cedge = cedge->next; |
237 | } |
238 | |
239 | /* find the neighbouring triangle */ |
240 | i = 0; |
241 | if (cedge->tn[0] == triang) i = 1; |
242 | trianglesptr[triang].tn[(2*j)%3] = cedge->tn[i]; |
243 | trianglesptr[triang].ivn[(2*j)%3] = cedge->ivn[i]; |
244 | } |
245 | } |
246 | |
247 | /* destroy the edges array which has done it's duty */ |
248 | for (ivert = 1; ivert <= NBVERTICES; ivert++) { |
249 | while(edges[ivert] != NULL) { |
250 | cedge = edges[ivert]; |
251 | edges[ivert] = cedge->next; |
252 | Standard::Free((void*&)cedge); |
253 | } |
254 | } |
255 | Standard::Free((void*&)edges); |
256 | } |
257 | |
258 | |
259 | /********************************************************************/ |
260 | /* */ |
261 | /* STRIPT_GET_STRIP : find the next strip */ |
262 | /* */ |
263 | /********************************************************************/ |
264 | |
265 | void Graphic3d_Strips :: STRIPT_GET_STRIP ( Standard_Integer& NBTRIANGLES, |
266 | Standard_Integer& V1, |
267 | Standard_Integer& V2 ) |
268 | { |
269 | |
270 | int btriang; /* the triangle with the lowest number of neigbours */ |
271 | int triang; |
272 | int tr; |
273 | int bneib,neib; |
274 | stript cstrip; /* the current strip */ |
275 | int cscore; /* it's score */ |
276 | int cleng; /* it's length */ |
277 | /* the best strip is stored in current_strip */ |
278 | int blength; /* the best strip length */ |
279 | int bscore; /* the best strip score */ |
280 | |
281 | int i; |
282 | |
283 | /* first find the triangle with the lowest number of neighbours */ |
284 | btriang = 0; |
285 | bneib = 4; |
286 | for (triang=1; triang<=nbtriangles; triang++) { |
287 | if (trianglesptr[triang].state != 0) { |
288 | neib = 0; |
289 | for (i=0;i<3;i++) { |
290 | tr = trianglesptr[triang].tn[i]; |
291 | if ((tr != 0) && (trianglesptr[tr].state != 0)) { |
292 | neib++; |
293 | } |
294 | } |
295 | if (neib < bneib) { |
296 | bneib = neib; |
297 | btriang = triang; |
298 | /* a triangle with 0 or one neighbours is fine */ |
299 | if (neib <= 1) break; |
300 | } |
301 | } |
302 | } |
303 | |
304 | /* if none was found stop the process and free the memory */ |
305 | if (btriang == 0) |
306 | { |
307 | NBTRIANGLES = 0; |
308 | current_stript.t = 0; |
309 | Standard::Free((void*&)trianglesptr); |
310 | return; |
311 | } |
312 | |
313 | /* now search the best strip from this triangle |
314 | the strip with the biggest score. |
315 | If score are even the biggest length win */ |
316 | |
317 | /* try 0,1,2 */ |
318 | current_stript.t = btriang; |
319 | current_stript.iv1 = 1; |
320 | current_stript.iv2 = 2; |
321 | bscore = stript_score(¤t_stript,&blength); |
322 | |
323 | /* try 1,2,0 */ |
324 | cstrip.t = btriang; |
325 | cstrip.iv1 = 2; |
326 | cstrip.iv2 = 0; |
327 | cscore = stript_score(&cstrip,&cleng); |
328 | if ((cscore > bscore) || |
329 | ((cscore == bscore) && (cleng > blength))){ |
330 | bscore = cscore; |
331 | blength = cleng; |
332 | current_stript.t = cstrip.t; |
333 | current_stript.iv1 = cstrip.iv1; |
334 | current_stript.iv2 = cstrip.iv2; |
335 | } |
336 | |
337 | /* try 2,0,1 */ |
338 | cstrip.t = btriang; |
339 | cstrip.iv1 = 0; |
340 | cstrip.iv2 = 1; |
341 | cscore = stript_score(&cstrip,&cleng); |
342 | if ((cscore > bscore) || |
343 | ((cscore == bscore) && (cleng > blength))){ |
344 | bscore = cscore; |
345 | blength = cleng; |
346 | current_stript.t = cstrip.t; |
347 | current_stript.iv1 = cstrip.iv1; |
348 | current_stript.iv2 = cstrip.iv2; |
349 | } |
350 | |
351 | /* return the best strip */ |
352 | NBTRIANGLES = blength; |
353 | triang = current_stript.t; |
354 | V2 = trianglesptr[triang].v[current_stript.iv1]; |
355 | V1 = trianglesptr[triang].v[3-current_stript.iv1-current_stript.iv2]; |
356 | return; |
357 | } |
358 | |
359 | |
360 | /********************************************************************/ |
361 | /* */ |
362 | /* STRIPT_GET_VERTEX : get next vertex & triangle in current strip */ |
363 | /* */ |
364 | /********************************************************************/ |
365 | |
366 | void Graphic3d_Strips :: STRIPT_GET_VERTEX ( Standard_Integer& VERTEX, |
367 | Standard_Integer& TRIANGLE ) |
368 | { |
369 | int triang; |
370 | triang = current_stript.t; |
371 | /* delete this triangle */ |
372 | trianglesptr[triang].state = 0; |
373 | TRIANGLE = triang; |
374 | VERTEX = trianglesptr[triang].v[current_stript.iv2]; |
375 | stript_next(¤t_stript); |
376 | return; |
377 | } |
378 | |
379 | |
380 | |
381 | /********************************************************************/ |
382 | /* */ |
383 | /* stript_score : find the start of a strip and it's lenght */ |
384 | /* returns the score of the strip */ |
385 | /* */ |
386 | /********************************************************************/ |
387 | |
388 | int stript_score(stript* pstrip, int *plength) |
389 | { |
390 | /* st is set to the beginning of the strip and the length of the strip |
391 | is returned. The strip is explored in two directions, if it loops |
392 | on itself it is detected. */ |
393 | /* the score is a value to optimise. The number of boundary triangles */ |
394 | /* in a strip seems to be a nice choice. */ |
395 | stript cstrip,savstrip; |
396 | int length; |
397 | int score; |
398 | int i; |
399 | int triang; |
400 | |
401 | length = 0; |
402 | score = 0; |
403 | last_stript++; /* this is used to mark triangles in this strip */ |
404 | |
405 | /* go in the first direction */ |
406 | cstrip.t = pstrip->t; |
407 | cstrip.iv1 = pstrip->iv1; |
408 | cstrip.iv2 = pstrip->iv2; |
409 | while ((cstrip.t != 0) && /* - on a boundary */ |
410 | (trianglesptr[cstrip.t].state != 0) && /* - deleted */ |
411 | (trianglesptr[cstrip.t].state != last_stript)) { /* - on the same */ |
412 | /* strip */ |
413 | trianglesptr[cstrip.t].state = last_stript; |
414 | /* increment the length */ |
415 | length++; |
416 | /* compute the score */ |
417 | /* increment the score if the triangle has less than three */ |
418 | /* neigbours */ |
419 | for (i=0;i<3;i++) { |
420 | triang = trianglesptr[cstrip.t].tn[i]; |
421 | if ((triang == 0) || (trianglesptr[triang].state == 0)) { |
422 | score++; |
423 | break; |
424 | } |
425 | } |
426 | /* next in the strip */ |
427 | stript_next(&cstrip); |
428 | } |
429 | /* go in the reversed direction */ |
430 | cstrip.t = pstrip->t; |
431 | cstrip.iv1 = pstrip->iv1; |
432 | cstrip.iv2 = 3 - pstrip->iv2 - pstrip->iv1; |
433 | /* save the position of the strip before moving */ |
434 | savstrip.t = cstrip.t; |
435 | savstrip.iv1 = cstrip.iv1; |
436 | savstrip.iv2 = cstrip.iv2; |
437 | stript_next(&cstrip); |
438 | while ((cstrip.t != 0) && |
439 | (trianglesptr[cstrip.t].state != 0) && |
440 | (trianglesptr[cstrip.t].state != last_stript)) { |
441 | trianglesptr[cstrip.t].state = last_stript; |
442 | /* save the position of the strip before moving */ |
443 | savstrip.t = cstrip.t; |
444 | savstrip.iv1 = cstrip.iv1; |
445 | savstrip.iv2 = cstrip.iv2; |
446 | /* increment the length */ |
447 | length++; |
448 | /* compute the score */ |
449 | /* increment the score if the triangle has less than three */ |
450 | /* neigbours */ |
451 | for (i=0;i<3;i++) { |
452 | triang = trianglesptr[cstrip.t].tn[i]; |
453 | if ((triang == 0) || (trianglesptr[triang].state == 0)) { |
454 | score++; |
455 | break; |
456 | } |
457 | } |
458 | /* next in the strip */ |
459 | stript_next(&cstrip); |
460 | } |
461 | |
462 | /* reverse in the good direction the saved position */ |
463 | pstrip->t = savstrip.t; |
464 | pstrip->iv1 = savstrip.iv1; |
465 | pstrip->iv2 = 3 - savstrip.iv1 - savstrip.iv2; |
466 | *plength = length; |
467 | return score; |
468 | } |
469 | |
470 | /********************************************************************/ |
471 | /* */ |
472 | /* stript_next : jump to next triangle in a strip */ |
473 | /* */ |
474 | /********************************************************************/ |
475 | |
476 | void stript_next(stript *st) |
477 | { |
478 | /* st points toward a triangle and a vertex ordering defining a unique */ |
479 | /* it's content is changed for the next triangle in the strip */ |
480 | /* the triangle may becomes 0 if there was no neighbour */ |
481 | |
482 | int triang,ntriang; |
483 | int i,j; |
484 | |
485 | triang = st->t; |
486 | |
487 | if (triang == 0) { |
488 | st->t = 0; |
489 | st->iv1 = 0; |
490 | st->iv2 = 0; |
491 | return; |
492 | } |
493 | /* get the neighbouring triangle */ |
494 | i = st->iv1+st->iv2-1; |
495 | ntriang = trianglesptr[triang].tn[i]; |
496 | /* if there is no neighbour */ |
497 | if (ntriang == 0) { |
498 | st->t = 0; |
499 | st->iv1 = 0; |
500 | st->iv2 = 0; |
501 | return; |
502 | } |
503 | /* compute the new index for the last vertex */ |
504 | j = 0; |
505 | while(trianglesptr[triang].v[st->iv2] != trianglesptr[ntriang].v[j]) { |
506 | j++; |
507 | } |
508 | st->t = ntriang; |
509 | st->iv1 = j; |
510 | st->iv2 = trianglesptr[triang].ivn[i]; |
511 | |
512 | return; |
513 | } |
514 | |
515 | /*******************************************************************/ |
516 | /********* **********/ |
517 | /********* COMMENTS **********/ |
518 | /********* **********/ |
519 | /*******************************************************************/ |
520 | |
521 | |
522 | /* |
523 | Architecture |
524 | ************ |
525 | |
526 | The present C implementation was designed to be called from FORTRAN |
527 | with the following syntaxes : |
528 | |
529 | 1. STRIP_INIT(int * NBVERTICES,int * NBTRIANGLES,int * TABTRIANGLES) |
530 | |
531 | This is the initiating call where : |
532 | NBVERTICES is the number of vertices |
533 | NBTRIANGLES is the number of triangles |
534 | TABTRIANGLES is the table describing the triangles |
535 | |
536 | This function copies the arguments to nvertices, ntriangles, and |
537 | build an inner table of triangles (triangles) were the neighbours of a |
538 | triangle can be found easily. |
539 | |
540 | |
541 | IMPORTANT WARNINGS |
542 | Vertices and Triangles are in the range 1...NBVERTICES |
543 | 1...NBTRIANGLES |
544 | Double arrays are FORTRAN arrays so the three vertices of triangle I |
545 | are found in TABTRIANGLES[I+J-1] where J = 0,1,2 |
546 | The FORTRAN array is declared as TABTRIANGLES(3,NBTRIANGLES) |
547 | |
548 | |
549 | 2. STRIP_GET_STRIP(int * NBTRIANGLES,int * V1,int * V2) |
550 | STRIP_GET_VERTEX(int * VERTEX,int * TRIANGLE) |
551 | |
552 | Both functions are used to get the strips. each iteration of the |
553 | GET_STRIP brings a new strip wre NBTRIANGLES is the number of triangles |
554 | in the strip (i.e the number of vertices is NBTRIANGLES plus two) and V1, V2 |
555 | are the two first vertices. NBTRIANGLES becomes zero when the last |
556 | strip has been read. GET_VERTEX is used two get the successives |
557 | vertices of a strip, each vertex is associated with a triangle. |
558 | This start with the third vertex, the two first are given by |
559 | GET_STRIP. |
560 | |
561 | An example of correct call from C to read the strips is |
562 | |
563 | while(1) { |
564 | STRIP_GET_STRIP(&nb_triangles,&v[1],&v[2]); |
565 | if (nb_triangles == 0) break; |
566 | for (i=3;i <= ( nb_triangles+2 ); i++) { |
567 | STRIP_GET_VERTEX(&v[i],&t[i]); |
568 | } |
569 | } |
570 | |
571 | Unwise calls to those functions will generally return zero but |
572 | are not recommanded. |
573 | |
574 | The data are not checked for coherence, but a zero |
575 | number of triangle will give a zero number of strips. |
576 | |
577 | */ |
578 | |
579 | /* |
580 | OUTLINE OF THE ALGORITHM |
581 | ************************ |
582 | |
583 | The algorithm is purely topological. No coordinates are given, it's |
584 | input are the number of vertices, the number of triangles, and for |
585 | each triangle a triplet of vertices indices. |
586 | |
587 | Let us consider a triangle T = (V1, V2, V3), this triangle has |
588 | neighbours in the triangle graphs, let us call them T12, T23, T31. T12 |
589 | is the triangle sharing the edge V1,V2 with T, etc... Of course those |
590 | three triangles may not exist in the graph in this case T is "on the |
591 | border" or even "in a corner". |
592 | |
593 | The key remark is that at most three triangle-strips may cross T they |
594 | are : T12-T-T23, T23-T-T31, T31-T-T12. Once three adjacent triangles |
595 | are given the entire strip is uniquely defined, the orientation of a |
596 | strip is meaningless as if you reverse it you get the same strip. |
597 | To describe a current position in a strip you need a triangle and the |
598 | two last vertices of the triangle in the strip. |
599 | |
600 | Our algorithm (more precisely heuristic) is the following : |
601 | - Find a triangle with the lowest number of neighbours. |
602 | - List the three (or less) strips crossing this triangle. |
603 | - Chose the best among them and remove from the graph all the |
604 | triangles in this strip. |
605 | The best strip is rated with a "score", the score we used is the |
606 | number of triangles in the strip which have less than three |
607 | neighbours (they are on the "border") in case of score equality the |
608 | longest strip is selected. |
609 | - Reiterate the process until there are no triangles left. |
610 | |
611 | There are no demonstrations of the optimality of this algorithm, but |
612 | it seems to give expected results on regular graphs which are the most |
613 | commonly fed to it. On a rectangular array of squares, each square cut |
614 | in two triangles, it will generate strips parallels to the longest |
615 | side of the rectangle. |
616 | |
617 | */ |
618 | |
619 | /* |
620 | Implementation |
621 | ************** |
622 | |
623 | First the STRIP_INIT function stores the triangles in a data structure |
624 | (the triangles array allocated on free store), containing for each |
625 | triangle it's three neighbours and the third vertex for each neighbour |
626 | (a zero neighbour is inexistant), a triangle get's also a state 1. To |
627 | build this array a temporary array "edges" is build giving for each |
628 | edge (pair of vertices) the two neghbouring triangles. |
629 | |
630 | Then at each call of STRIP_GET_STRIP a triangle with minimum |
631 | neighbours is first chosen. For the three possible strips crossing |
632 | the triangle the strip_score function is called which brings back the |
633 | start of the strip, the length and the score. The strip-next function |
634 | is used to jump to the next triangle in a strip. The best strip is |
635 | chosen, stored in the current_strip and returned. |
636 | |
637 | |
638 | Each call to STRIP_GET_VERTEX increment the the current-strip |
639 | structure to the next triangle in the strip, using the strip_next |
640 | function. The triangle is deleted from the graph and returned. |
641 | |
642 | The last call to STRIP_GET_STRIP returns the triangles array to the |
643 | free store. |
644 | |
645 | |
646 | */ |
647 | |
648 | |
649 | /* |
650 | QUADRANGLE_STRIP |
651 | */ |
652 | |
653 | /* |
654 | Algorithm to find Quadragle-Strips in a quadrangles graph. |
655 | |
656 | A quadrangle graph is a set of vertices (numbered from 1 to nbvertices) |
657 | and of quadrangles (numbered from 1 to nbquadrangles), each quadrangle is a |
658 | quadruplet of vertices. |
659 | |
660 | A quadrangle-strip is a strip of adjacent quadrangles that can be |
661 | described as a list of vertices. |
662 | The strip v1, v2, v3, v4, v5, v6, v7, v8 ... |
663 | describes quadrangles (v1, v2, v4, v3), (v4, v3, v5, v6), (v5, v6, v8, v7) ... |
664 | 1-3-5-7 |
665 | | | | | |
666 | 2-4-6-8 |
667 | |
668 | Quadrangle-strips are an economic way to pass quadrangles to a |
669 | hardware renderer as they require an average of two vertex per quadrangle. |
670 | |
671 | The purpose of this algorithm is to break a quadrangle graph into a |
672 | (minimal cardinality) set of quadrangle strips. |
673 | |
674 | It is purely topological, quadrangles are quadruplets of integers. |
675 | There is no limit of size, memory is allocated from free store. |
676 | The quantity allocated during the algorithm is about |
677 | (17*sizeof(int)+align)*q bytes where q is the number of quadrangles |
678 | and align is system-dependent alignment. |
679 | |
680 | ( the description of the algorithm can be found at the end of the file |
681 | starting with "COMMENTS") |
682 | */ |
683 | |
684 | |
685 | /*******************************/ |
686 | /* GLOBAL TYPES AND VARIABLES */ |
687 | /*******************************/ |
688 | |
689 | #define NULLQUADRANGLE 0 |
690 | |
691 | /* the array of quadrangles is the basic data structure to follow strips |
692 | it is allocated from free store */ |
693 | typedef struct { |
694 | int v[4]; /* the four vertices of the quadrangle */ |
695 | int qn[4]; /* neighbouring quadrangles */ |
696 | int ivn[4][2]; /* the index of two neighbouring vertice [q][v]*/ |
697 | int state; /* the last strip crossing the quadrangle, 0 means deleted */ |
698 | } quadrangle; |
699 | |
700 | quadrangle *quadranglesptr; |
701 | int QuadranglesPtrSize; |
702 | |
703 | /* the number of quadrangles */ |
704 | int nbquadrangles; |
705 | |
706 | /* remarks about the above structure : |
707 | Quadrangles are ranging from 1 two nbquadrangles, quadrangle 0 will always |
708 | be deleted. |
709 | A state of 0 means the quadrangle is deleted from the graph. |
710 | The NBVERTICES are v[0], v[1], v[2], v[3]. |
711 | To get the neigbour of the quadrangle on the other side of the edge |
712 | v[i], v[j] just pick qn[i+j-1] and ivn[i+j-1][0], ivn[i+j-1][1]. |
713 | If qn[i+j-1] is 0 there is no neighbour. |
714 | ivn is the index (0, 1, 2, 3)(0, 1) of two vertice of the neighbouring |
715 | quadrangle qn[] which are not shared with this quadrangle. |
716 | */ |
717 | |
718 | /* a strip is described by a quadrangle and the index of the two last |
719 | NBVERTICES of the quadrangle in the strip */ |
720 | typedef struct { |
721 | int q; /* the quadrangle */ |
722 | int iv2, iv3; /* the last NBVERTICES of q in the strip, in (0, 1, 2, 3) */ |
723 | } stripq; |
724 | |
725 | /* the current strip position is saved in this variable */ |
726 | /* between calls to to STRIPQ_GET_NEXT */ |
727 | static stripq current_stripq; |
728 | |
729 | /* this index is used to label the last strip under exploration */ |
730 | static int last_stripq; |
731 | |
732 | /* tell this dumb compiler that stripq_next returns nothing */ |
733 | void stripq_next(stripq *st); |
734 | int stripq_score(stripq *pstrip, int *plength); |
735 | |
736 | /********************************************************************/ |
737 | /* */ |
738 | /* STRIPQ_INIT : get data and build the quadrangles array */ |
739 | /* */ |
740 | /********************************************************************/ |
741 | |
742 | void Graphic3d_Strips :: STRIPQ_INIT ( const Standard_Integer NBNBVERTICES, |
743 | const Standard_Integer NBQUADRANG, |
744 | const TColStd_SequenceOfInteger& TABQUADRANGLES ) |
745 | { |
746 | |
747 | /* In order to build the quadrangles array we will use a temporary |
748 | array: edges. This array is of length NBNBVERTICES. Each entry is a |
749 | pointer to a list of structures of the type edge. This structure |
750 | describes an edge by: the second vertex of the edge and the two |
751 | quadrangles adjacent to the edge, the starting vertex of the edge is the |
752 | entry of the array edges. The smallest vertex index of an edge is used |
753 | to index it in the edges array */ |
754 | |
755 | typedef struct edg { |
756 | struct edg *next; /* next edge in the list for a vertex */ |
757 | int v; /* the second vertex of the edge */ |
758 | int qn[2]; /* neighbour quadrangles */ |
759 | int ivn[2][2]; /* index of two vertice of neighbour quadrangles [q][v]*/ |
760 | } edge; |
761 | |
762 | edge **edges; |
763 | edge *cedge; |
764 | int ivert, quadrang; |
765 | int vmin, vmax; |
766 | int iv3, iv4; |
767 | int QedgesSize; |
768 | |
769 | int i, j; |
770 | |
771 | /* copy the number and initialize a few */ |
772 | nbquadrangles = NBQUADRANG; |
773 | last_stripq = 1; |
774 | |
775 | /* allocate the array edges |
776 | NBVERTICES are ranging from 1 to NBNBVERTICES */ |
777 | QedgesSize = (NBNBVERTICES+1) * sizeof(edge*); |
778 | edges = (edge**) Standard::Allocate (QedgesSize); |
779 | for (ivert=0; ivert<= NBNBVERTICES; ivert++) { |
780 | edges[ivert] = NULL; |
781 | } |
782 | |
783 | /* allocate the array quadrangles from 0 to nbquadrangles */ |
784 | QuadranglesPtrSize = (nbquadrangles+1)*sizeof(quadrangle); |
785 | quadranglesptr = (quadrangle*) Standard::Allocate (QuadranglesPtrSize); |
786 | quadranglesptr[0].v[0] = 0; |
787 | quadranglesptr[0].v[1] = 0; |
788 | quadranglesptr[0].v[2] = 0; |
789 | quadranglesptr[0].v[3] = 0; |
790 | quadranglesptr[0].qn[0] = NULLQUADRANGLE; |
791 | quadranglesptr[0].qn[1] = NULLQUADRANGLE; |
792 | quadranglesptr[0].qn[2] = NULLQUADRANGLE; |
793 | quadranglesptr[0].qn[3] = NULLQUADRANGLE; |
794 | quadranglesptr[0].ivn[0][0] = 0; |
795 | quadranglesptr[0].ivn[0][1] = 0; |
796 | quadranglesptr[0].ivn[1][0] = 0; |
797 | quadranglesptr[0].ivn[1][1] = 0; |
798 | quadranglesptr[0].ivn[2][0] = 0; |
799 | quadranglesptr[0].ivn[2][1] = 0; |
800 | quadranglesptr[0].ivn[3][0] = 0; |
801 | quadranglesptr[0].ivn[3][1] = 0; |
802 | quadranglesptr[0].state = DELETED; |
803 | |
804 | /* copy the quadrangles into the arrays */ |
805 | for (quadrang=1; quadrang<=nbquadrangles; quadrang++) |
806 | { |
807 | /* copy the NBVERTICES */ |
808 | quadranglesptr[quadrang].state = 1; |
809 | for (j=0; j<4; j++) |
810 | quadranglesptr[quadrang].v[j] = TABQUADRANGLES(4*(quadrang-1)+j+1); |
811 | /* insert the edges in the edges array */ |
812 | for (j=0; j<4; j++) |
813 | { |
814 | if (quadranglesptr[quadrang].v[j] <= quadranglesptr[quadrang].v[(j+1)%4]) |
815 | { |
816 | vmin = quadranglesptr[quadrang].v[j]; |
817 | vmax = quadranglesptr[quadrang].v[(j+1)%4]; |
818 | } |
819 | else |
820 | { |
821 | vmax = quadranglesptr[quadrang].v[j]; |
822 | vmin = quadranglesptr[quadrang].v[(j+1)%4]; |
823 | } |
824 | iv3 = (j+2)%4; |
825 | iv4 = (j+3)%4; |
826 | /* the edge is inserted in the array at the entry for the |
827 | smallest vertex */ |
828 | /* first search if there is an entry for this edge */ |
829 | cedge = edges[vmin]; |
830 | while(cedge != NULL) |
831 | { |
832 | if (cedge->v == vmax) |
833 | break; |
834 | cedge = cedge->next; |
835 | } |
836 | /* if the edge was not found, create it */ |
837 | if (cedge == NULL) { |
838 | cedge = (edge*) Standard::Allocate (sizeof(edge)); |
839 | cedge->next = edges[vmin]; |
840 | edges[vmin] = cedge; |
841 | cedge->v = vmax; |
842 | cedge->qn[0] = quadrang; |
843 | cedge->ivn[0][0] = iv3; |
844 | cedge->ivn[0][1] = iv4; |
845 | cedge->qn[1] = 0; |
846 | cedge->ivn[1][0] = 0; |
847 | cedge->ivn[1][1] = 0; |
848 | } |
849 | else |
850 | { |
851 | cedge->qn[1] = quadrang; |
852 | cedge->ivn[1][0] = iv3; |
853 | cedge->ivn[1][1] = iv4; |
854 | } |
855 | } |
856 | } |
857 | /* now complete the quadrangles array (neighbours) using the edges array */ |
858 | for (quadrang=1; quadrang<=nbquadrangles; quadrang++) |
859 | { |
860 | /* on each edge of the quadrangle: find the neighbour */ |
861 | for (j=0; j<4; j++) |
862 | { |
863 | if (quadranglesptr[quadrang].v[j] <= quadranglesptr[quadrang].v[(j+1)%4]) |
864 | { |
865 | vmin = quadranglesptr[quadrang].v[j]; |
866 | vmax = quadranglesptr[quadrang].v[(j+1)%4]; |
867 | } |
868 | else |
869 | { |
870 | vmax = quadranglesptr[quadrang].v[j]; |
871 | vmin = quadranglesptr[quadrang].v[(j+1)%4]; |
872 | } |
873 | /* search the entry for the edge */ |
874 | cedge = edges[vmin]; |
875 | while(cedge->v != vmax) |
876 | cedge = cedge->next; |
877 | /* find the neighbouring quadrangle */ |
878 | i = 0; |
879 | if (cedge->qn[0] == quadrang) |
880 | i = 1; |
881 | quadranglesptr[quadrang].qn[j] = cedge->qn[i]; |
882 | quadranglesptr[quadrang].ivn[j][0] = cedge->ivn[i][0]; |
883 | quadranglesptr[quadrang].ivn[j][1] = cedge->ivn[i][1]; |
884 | } |
885 | } |
886 | /* destroy the edges array which has done it's duty */ |
887 | for (ivert = 1; ivert <= NBNBVERTICES; ivert++) |
888 | { |
889 | while(edges[ivert] != NULL) |
890 | { |
891 | cedge = edges[ivert]; |
892 | edges[ivert] = cedge->next; |
893 | Standard::Free((void*&)cedge); |
894 | } |
895 | } |
896 | Standard::Free((void*&)edges); |
897 | } |
898 | |
899 | |
900 | /********************************************************************/ |
901 | /* */ |
902 | /* STRIPQ_GET_STRIP : find the next strip */ |
903 | /* */ |
904 | /********************************************************************/ |
905 | |
906 | void Graphic3d_Strips :: STRIPQ_GET_STRIP ( Standard_Integer& NBQUAD,Standard_Integer& V1, |
907 | Standard_Integer& V2 ) |
908 | { |
909 | int bquadrang; /* the quadrangle with the lowest number of neigbours */ |
910 | int quadrang; |
911 | int quad; |
912 | int bneib, neib; |
913 | stripq cstrip; /* the current strip */ |
914 | int cscore; /* it's score */ |
915 | int cleng; /* it's length */ |
916 | /* the best strip is stored in current_strip */ |
917 | int blength; /* the best strip length */ |
918 | int bscore; /* the best strip score */ |
919 | int i; |
920 | |
921 | /* first find the quadrangle with the lowest number of neighbours */ |
922 | bquadrang = 0; |
923 | bneib = 5; |
924 | for (quadrang=1; quadrang<=nbquadrangles; quadrang++) |
925 | { |
926 | if (quadranglesptr[quadrang].state != 0) |
927 | { |
928 | neib = 0; |
929 | for (i=0; i<4; i++) |
930 | { |
931 | quad = quadranglesptr[quadrang].qn[i]; |
932 | if ((quad != 0) && (quadranglesptr[quad].state != 0)) |
933 | neib++; |
934 | } |
935 | if (neib < bneib) |
936 | { |
937 | bneib = neib; |
938 | bquadrang = quadrang; |
939 | /* a quadrangle with 0 or one neighbours is fine */ |
940 | if (neib <= 1) |
941 | break; |
942 | } |
943 | } |
944 | } |
945 | /* if none was found stop the process and free the memory */ |
946 | if (bquadrang == 0) |
947 | { |
948 | NBQUAD = 0; |
949 | current_stripq.q = 0; |
950 | Standard::Free((void*&)quadranglesptr); |
951 | return; |
952 | } |
953 | /* Now search the best strip from this quadrangle |
954 | the strip with the biggest score. |
955 | If score were even the biggest length win. */ |
956 | /* try 0, 1, 2, 3 */ |
957 | current_stripq.q = bquadrang; |
958 | current_stripq.iv2 = 2; |
959 | current_stripq.iv3 = 3; |
960 | bscore = stripq_score(¤t_stripq, &blength); |
961 | /* try 1, 2, 3, 0 */ |
962 | cstrip.q = bquadrang; |
963 | cstrip.iv2 = 3; |
964 | cstrip.iv3 = 0; |
965 | cscore = stripq_score(&cstrip, &cleng); |
966 | if ((cscore > bscore) || |
967 | ((cscore == bscore) && (cleng > blength))) |
968 | { |
969 | bscore = cscore; |
970 | blength = cleng; |
971 | current_stripq.q = cstrip.q; |
972 | current_stripq.iv2 = cstrip.iv2; |
973 | current_stripq.iv3 = cstrip.iv3; |
974 | } |
975 | /* return the best strip */ |
976 | NBQUAD = blength; |
977 | quadrang = current_stripq.q; |
978 | |
979 | V1 = quadranglesptr[quadrang].v[(current_stripq.iv2+2)%4]; |
980 | V2 = quadranglesptr[quadrang].v[(current_stripq.iv3+2)%4]; |
981 | return; |
982 | } |
983 | |
984 | /********************************************************************/ |
985 | /* */ |
986 | /* STRIPQ_GET_NEXT : get next vertex & quadrangle in current strip */ |
987 | /* */ |
988 | /********************************************************************/ |
989 | void Graphic3d_Strips :: STRIPQ_GET_NEXT ( Standard_Integer& VERTEX1, |
990 | Standard_Integer& VERTEX2, |
991 | Standard_Integer& QUADRANGLE ) |
992 | { |
993 | int quadrang = current_stripq.q; |
994 | /* delete this quadrangle */ |
995 | quadranglesptr[quadrang].state = 0; |
996 | QUADRANGLE = quadrang; |
997 | /* reversed */ |
998 | VERTEX2 = quadranglesptr[quadrang].v[current_stripq.iv2]; |
999 | VERTEX1 = quadranglesptr[quadrang].v[current_stripq.iv3]; |
1000 | stripq_next(¤t_stripq); |
1001 | return; |
1002 | } |
1003 | |
1004 | /********************************************************************/ |
1005 | /* */ |
1006 | /* stripq_score : find the start of a strip and it's length */ |
1007 | /* returns the score of the strip */ |
1008 | /* */ |
1009 | /********************************************************************/ |
1010 | int stripq_score(stripq *pstrip, int *plength) |
1011 | { |
1012 | /* st is set to the beginning of the strip and the length of the strip |
1013 | is returned. The strip is explored in two directions, if it loops |
1014 | on itself it is detected. */ |
1015 | /* The score is a value to optimise. The number of boundary quadrangles */ |
1016 | /* in a strip seems to be a nice choice. */ |
1017 | stripq cstrip, savstrip; |
1018 | int length; |
1019 | int score; |
1020 | int i; |
1021 | int quadrang; |
1022 | |
1023 | length = 0; |
1024 | score = 0; |
1025 | last_stripq++; /* this is used to mark quadrangles in this strip */ |
1026 | |
1027 | /* go forwards till possible... */ |
1028 | cstrip.q = pstrip->q; |
1029 | cstrip.iv2 = pstrip->iv2; |
1030 | cstrip.iv3 = pstrip->iv3; |
1031 | while ((cstrip.q != 0) && /* on a boundary */ |
1032 | (quadranglesptr[cstrip.q].state != 0) && /* deleted */ |
1033 | (quadranglesptr[cstrip.q].state != last_stripq))/* on the same strip */ |
1034 | { |
1035 | quadranglesptr[cstrip.q].state = last_stripq; |
1036 | /* increment the length */ |
1037 | length++; |
1038 | /* compute the score */ |
1039 | /* increment the score if the quadrangle has less than four neighbours */ |
1040 | for (i=0; i<4; i++) |
1041 | { |
1042 | quadrang = quadranglesptr[cstrip.q].qn[i]; |
1043 | if ((quadrang == 0) || (quadranglesptr[quadrang].state == 0)) |
1044 | { |
1045 | score++; |
1046 | break; |
1047 | } |
1048 | } |
1049 | /* next in the strip */ |
1050 | stripq_next(&cstrip); |
1051 | } |
1052 | /* turn back... */ |
1053 | cstrip.q = pstrip->q; |
1054 | cstrip.iv2 = (pstrip->iv2+2)%4; |
1055 | cstrip.iv3 = (pstrip->iv3+2)%4; |
1056 | /* ... but save the position of the strip before moving */ |
1057 | savstrip.q = cstrip.q; |
1058 | savstrip.iv2 = cstrip.iv2; |
1059 | savstrip.iv3 = cstrip.iv3; |
1060 | stripq_next(&cstrip); |
1061 | while ((cstrip.q != 0) && |
1062 | (quadranglesptr[cstrip.q].state != 0) && |
1063 | (quadranglesptr[cstrip.q].state != last_stripq)) |
1064 | { |
1065 | quadranglesptr[cstrip.q].state = last_stripq; |
1066 | /* save the position of the strip each time before moving */ |
1067 | savstrip.q = cstrip.q; |
1068 | savstrip.iv2 = cstrip.iv2; |
1069 | savstrip.iv3 = cstrip.iv3; |
1070 | /* increment the length */ |
1071 | length++; |
1072 | /* compute the score */ |
1073 | /* increment the score if the quadrangle has less than four neighbours */ |
1074 | for (i=0; i<4; i++) |
1075 | { |
1076 | quadrang = quadranglesptr[cstrip.q].qn[i]; |
1077 | if ((quadrang == 0) || (quadranglesptr[quadrang].state == 0)) |
1078 | { |
1079 | score++; |
1080 | break; |
1081 | } |
1082 | } |
1083 | /* next in the strip */ |
1084 | stripq_next(&cstrip); |
1085 | } |
1086 | /* ... back end reached. Now turn forward again at recent saved position. */ |
1087 | pstrip->q = savstrip.q; |
1088 | pstrip->iv2 = (savstrip.iv2+2)%4; |
1089 | pstrip->iv3 = (savstrip.iv3+2)%4; |
1090 | *plength = length; |
1091 | return score; |
1092 | } |
1093 | |
1094 | /********************************************************************/ |
1095 | /* */ |
1096 | /* stripq_next : jump to next quadrangle in a strip */ |
1097 | /* */ |
1098 | /********************************************************************/ |
1099 | |
1100 | void stripq_next(stripq *st) |
1101 | { /* st points toward a quadrangle and a vertex ordering defining a unique. */ |
1102 | /* Its content is changed for the next quadrangle in the strip. */ |
1103 | /* The quadrangle may become 0 if there was no neighbour. */ |
1104 | int quadrang=st->q; /* current */ |
1105 | int i=st->iv2; |
1106 | int nquadrang=quadranglesptr[quadrang].qn[i]; /* neighbour */ |
1107 | |
1108 | if (!quadrang || !nquadrang) |
1109 | { /* There is no neighbour on this edge. */ |
1110 | st->q = 0; |
1111 | st->iv2 = 0; |
1112 | st->iv3 = 0; |
1113 | } |
1114 | else |
1115 | { /* Compute the new index for the last vertex. */ |
1116 | st->q = nquadrang; |
1117 | st->iv2 = quadranglesptr[quadrang].ivn[i][0]; |
1118 | st->iv3 = quadranglesptr[quadrang].ivn[i][1]; |
1119 | } |
1120 | } |
1121 | |
1122 | /*******************************************************************/ |
1123 | /********* **********/ |
1124 | /********* COMMENTS **********/ |
1125 | /********* **********/ |
1126 | /*******************************************************************/ |
1127 | |
1128 | |
1129 | /* |
1130 | Architecture |
1131 | ************ |
1132 | |
1133 | The present C implementation was designed to be called from FORTRAN |
1134 | with the following syntaxes: |
1135 | |
1136 | 1. STRIPQ_INIT(int *NBNBVERTICES, int *NBQUADRANGLES, int *TABQUADRANGLES) |
1137 | |
1138 | This is the initiating call where: |
1139 | NBNBVERTICES is the number of NBVERTICES |
1140 | NBQUADRNGLES is the number of quadrangles |
1141 | TABQUADRANGLES is the table describing quadrangles |
1142 | |
1143 | This function copies its arguments to nbNBVERTICES, nquadrangles, and |
1144 | build an inner table of quadrangles, where neighbours of a |
1145 | quadrangle can be found easily. |
1146 | |
1147 | |
1148 | IMPORTANT WARNINGS |
1149 | NBVERTICES and Quadrangles are in the range 1...NBNBVERTICES and 1...NBQUADRANGLES |
1150 | Double arrays are FORTRAN arrays so the three NBVERTICES of quadrangle I |
1151 | are found in TABQUADRANGLES[I+J-1] where J = 0, 1, 2, 3. |
1152 | The FORTRAN array is declared as TABQUADRANGLES(4, NBQUADRANGLES) |
1153 | |
1154 | |
1155 | 2. STRIPQ_GET_STRIP(int *NBQUAD, int *V1, int *V2) |
1156 | STRIPQ_GET_NEXT(int *VERTEX1, int *VERTEX2, int *QUADRANGLE) |
1157 | ??? |
1158 | Both functions are used to get the strips. Each iteration of the |
1159 | GET_STRIP brings a new strip where NBQUAD is the number of quadrangles |
1160 | in the strip (NB: number of NBVERTICES would be NBQUADS*2+2) and V1, V2 |
1161 | are the two first NBVERTICES. NBQUADS becomes zero when the last |
1162 | strip has been read. STRIPQ_GET_NEXT is used to get the successive |
1163 | NBVERTICES of a strip, each two vertice are associated with next quadrangle. |
1164 | This start with the 3d and 4th vertice, the two first are given by |
1165 | STRIPQ_GET_STRIP. |
1166 | |
1167 | An example of correct call from C to read the strips is |
1168 | |
1169 | while(1) |
1170 | { |
1171 | STRIPQ_GET_STRIP(&nbquad, &v[0], &v[1]); |
1172 | if (nbquad == 0) |
1173 | break; |
1174 | for (i=1; i <= nbquad; i++) |
1175 | { |
1176 | STRIPQ_GET_NEXT(&v[i*2], &v[i*2+1], &q[i]); |
1177 | } |
1178 | } |
1179 | |
1180 | Unwise calls to those functions will generally return zero but |
1181 | are not recommanded. |
1182 | |
1183 | The data are not checked for coherence, but a zero |
1184 | number of quadrangle will give a zero number of strips. |
1185 | |
1186 | */ |
1187 | |
1188 | /* |
1189 | OUTLINE OF THE ALGORITHM |
1190 | ************************ |
1191 | |
1192 | The algorithm is purely topological. No coordinates are given, its |
1193 | input are the number of NBVERTICES, the number of quadangles, and for |
1194 | each quadrangle a quadruplet of NBVERTICES indices. |
1195 | |
1196 | Let us consider a quadrangle Q=(V1, V2, V3, V4), this quadrangle has |
1197 | neighbours in the quadrangle graphs, let us call them Q12, Q23, Q34 and Q41. |
1198 | Q12 is the quadrangle sharing the edge [V1, V2] with T, etc... Of course those |
1199 | fouree quadrangles may not exist in the graph, in this case T is "on the |
1200 | border" or even "in a corner". |
1201 | |
1202 | The key remark is that at most two quadrangle-strips may cross Q, they |
1203 | are: Q12-Q-Q34, Q23-Q-Q41. Once four adjacent quadrangles |
1204 | are given the entire strip is uniquely defined. The orientation of a |
1205 | strip is meaningless as if you reverse it you would get the same strip. |
1206 | To describe a current position in a strip you need a quadrangle and the |
1207 | two last NBVERTICES of the quadrangle in the strip. |
1208 | |
1209 | Our algorithm (more precisely heuristic) is the following: |
1210 | - Find a quadrangle with the lowest number of neighbours. |
1211 | - List the four (or less) strips crossing this quadrangle. |
1212 | - Chose the best among them and remove from the graph all the |
1213 | quadrangles in this strip. |
1214 | The best strip is rated with a "score", the score we used is the |
1215 | number of quadrangles in the strip which have less than four |
1216 | neighbours (they are on the "border") in case of score equality the |
1217 | longest strip is selected. |
1218 | - Reiterate the process until there are no quadrangles left. |
1219 | |
1220 | There are no demonstrations of the optimality of this algorithm, but |
1221 | it seems to give expected results on regular graphs which are the most |
1222 | commonly fed to it. |
1223 | */ |
1224 | |
1225 | /* |
1226 | Implementation |
1227 | ************** |
1228 | |
1229 | First the STRIPQ_INIT function stores the quadrangles in a data structure |
1230 | (the quadrangles array allocated on free store), containing for each |
1231 | quadrangle its four neighbours, then third and fourth vertice for each neighbour |
1232 | (a zero neighbour is inexistant), a quadrangle gets also a state 1. To |
1233 | build this array a temporary array "edges" is build giving for each |
1234 | edge (pair of NBVERTICES) the two neghbouring quadrangles. |
1235 | |
1236 | Then at each call of STRIPQ_GET_STRIP a quadrangle with minimum |
1237 | neighbours is first chosen. For the four possible strips crossing |
1238 | the quadrangle the strip_score function is called which brings back the |
1239 | start of the strip, the length and the score. The strip-next function |
1240 | is used to jump to the next quadrangle in a strip. The best strip is |
1241 | chosen, stored in the current_strip and returned. |
1242 | |
1243 | |
1244 | Each call to STRIPQ_GET_NEXT increments the current-strip |
1245 | structure to the next quadrangle in the strip, using the strip_next |
1246 | function. The quadrangle is deleted from the graph and returned. |
1247 | |
1248 | The last call to STRIPQ_GET_STRIP frees the quadrangles array to the |
1249 | free store. |
1250 | |
1251 | |
1252 | */ |