1 /***********************************************************************/
2 /* Open Visualization Data Explorer */
3 /* (C) Copyright IBM Corp. 1989,1999 */
4 /* ALL RIGHTS RESERVED */
5 /* This code licensed under the */
6 /* "IBM PUBLIC LICENSE - Open Visualization Data Explorer" */
7 /***********************************************************************/
8
9 #include <dxconfig.h>
10
11
12 /*
13 * $Source: /src/master/dx/src/exec/hwrender/hwTmesh.c,v $
14 */
15
16 #if defined(HAVE_STRING_H)
17 #include <string.h>
18 #endif
19
20 #if defined(HAVE_STRINGS_H)
21 #include <strings.h>
22 #endif
23
24 #include <stdio.h>
25 #include "hwDeclarations.h"
26 #include "hwXfield.h"
27 #include "hwTmesh.h"
28 #include "hwMemory.h"
29 #include "hwWindow.h"
30
31 #include "hwDebug.h"
32
33 extern dxObject _dxf_QueryObject(HashTable, dxObject);
34 extern void _dxf_InsertObject(HashTable, dxObject, dxObject);
35
36 typedef struct _Triple
37 {
38 int p[3] ;
39 } Triple ;
40
41
42 /* add point i in triangle tri to the strip */
43 #define AddPoint(tri,i) (point[nPtsInStrip++] = triangles[tri].p[i])
44
45
46 /*
47 * Make a "swap marker" in the strip telling where to swap. The swap
48 * marker needs to be right before the last vertex we added.
49 * so ... (5,4,3,2,1,?,...) => (5,4,3,2,-1,1,...)
50 */
51 #define DoSwap() \
52 { \
53 point[nPtsInStrip] = point[nPtsInStrip-1]; \
54 point[nPtsInStrip-1] = -1; \
55 nPtsInStrip++; \
56 } \
57
58
59 /*
60 * Make a "swap marker" in the strip telling where to swap, and then swap
61 * the 2 previous numbers.
62 *
63 * (5,4,3,2,1,?,...) => (5,4,-1,2,3,1,...)
64 *
65 * This is assuming all the numbers below are numbers added during the
66 * reverse search... if they include normal numbers it should be like
67 * this... (someday)
68 *
69 * (f1,f2,f3,f4,r2,r1) f4 f3 f2 -1 r2 f1 r1
70 * 3 4 5 6 2 1 => 6 5 4 -1 2 3 1
71 *
72 * ...because r2 and f1 are really going to be adjacent after the
73 * reversed numbers are switched around. Someday we should handle the
74 * cases of rev_pts = 0, 1, or 2. (see RevTryToSwap())
75 */
76 #define RevDoSwap() \
77 { \
78 point[nPtsInStrip ] = point[nPtsInStrip-1]; \
79 point[nPtsInStrip-1] = point[nPtsInStrip-3]; \
80 point[nPtsInStrip-3] = -1; \
81 nPtsInStrip++; \
82 } \
83
84
85 /* return the triangle index that refers to point pt in triangle tri */
86 #define LookUp(tri,pt) \
87 ( \
88 triangles[tri].p[0] == pt ? 0 : \
89 triangles[tri].p[1] == pt ? 1 : \
90 triangles[tri].p[2] == pt ? 2 : -1 \
91 )
92
93
94 /*
95 * Return the index not present of the set [0,1,2] so that
96 * other_index[0][1] = 2, and other_index[2][1] = 0, etc.
97 */
98 static int other_index[3][3] =
99 { {-1, 2, 1},
100 { 2,-1, 0},
101 { 1, 0,-1} };
102
103
104 #if defined(DXD_HW_TMESH_SWAP_OK)
105 /*
106 * If the hardware allows orientation swapping in strip, we have more
107 * flexibility in choosing directions to propagate the strip.
108 */
109 #define TryToSwap(try) tri = neighbors[prev_tri].p[prev_i1];
110 /*
111 * We can't do the swap until we have a few reverse points... else we
112 * would need to swap the beginning of the forward points, not the end.
113 * Maybe someday... (see RevDoSwap()).
114 */
115 #define RevTryToSwap(try) \
116 { \
117 if (rev_pts >= 3) /* had a few reverse points? */ \
118 tri = neighbors[prev_tri].p[prev_i1]; /* proceed with the swap */ \
119 else /* very few reverse points? */ \
120 tri = -1; /* don't let it swap */ \
121 }
122 #else
123 #define TryToSwap(try) tri = -1;
124 #define RevTryToSwap(try) tri = -1;
125 #endif /* defined(DXD_HW_TMESH_SWAP_OK) */
126
127
128 #define UsedTri(n) (usedArray[Byte(n)] & Mask(n))
129 #define ValidTri(ich, n) (ich ? DXIsElementValid(ich, n) : 1)
130 #define GoodTri(n) (n != -1 && !UsedTri(n) && ValidTri(xf->invCntns, n))
131
132
133 /* jump to neighbor across from i0 or across from i1 */
134 #define NextTri(tri) \
135 { \
136 /* the "MaxTstripSize-1" is because there might be a swap coming up too */ \
137 if (nPtsInStrip >= MaxTstripSize-1) /* if strip is too long... */ \
138 tri = -1; /* ...chop it off */ \
139 else \
140 { \
141 prev_tri = tri; \
142 prev_i0 = i0; \
143 prev_i1 = i1; \
144 prev_i2 = i2; \
145 tri = neighbors[prev_tri].p[prev_i0]; /* jump to adjacent triangle */ \
146 if (GoodTri(tri)) /* valid and not used? */ \
147 { /* adjust indices to new tri */ \
148 i0 = LookUp(tri,triangles[prev_tri].p[prev_i1]); \
149 i1 = LookUp(tri,triangles[prev_tri].p[prev_i2]); \
150 i2 = other_index[i0][i1]; \
151 } \
152 else /* can't jump to next normal triangle... maybe we can swap? */ \
153 { \
154 TryToSwap(try); /* jump to adj tri with swap */ \
155 if (GoodTri(tri)) /* valid and not used? */ \
156 { \
157 DoSwap(); /* put mark (-1) in point array to indicate a swap */ \
158 i0 = LookUp(tri,triangles[prev_tri].p[prev_i0]); \
159 i1 = LookUp(tri,triangles[prev_tri].p[prev_i2]); \
160 i2 = other_index[i0][i1]; \
161 } \
162 else \
163 tri = -1; /* dead end...end the strip */ \
164 } \
165 } \
166 }
167
168
169 /*
170 * If the hardware does not require that the initial triangles in all the
171 * strips are oriented consistently, then we can try to lengthen the
172 * strip by working in the opposite direction from the initial triangle.
173 * The new initial triangle may have a different orientation from the
174 * original.
175 */
176 #define RevNextTri(tri) \
177 { \
178 /* the "MaxTstripSize-1" is because there might be a swap coming up too */ \
179 if (nPtsInStrip >= MaxTstripSize-1) /* if strip is too long... */ \
180 tri = -1; /* ...chop it off */ \
181 else \
182 { \
183 prev_tri = tri; \
184 prev_i0 = i0; \
185 prev_i1 = i1; \
186 prev_i2 = i2; \
187 tri = neighbors[prev_tri].p[prev_i2]; /* jump BACK to PREV triangle */ \
188 if (GoodTri(tri)) /* valid and not used? */ \
189 { /* adjust indices to new tri */ \
190 i2 = LookUp(tri,triangles[prev_tri].p[prev_i1]); \
191 i1 = LookUp(tri,triangles[prev_tri].p[prev_i0]); \
192 i0 = other_index[i1][i2]; \
193 } \
194 else /* can't jump to next normal triangle... maybe we can swap? */ \
195 { \
196 RevTryToSwap(try); /* jump to adj tri with swap */ \
197 if (GoodTri(tri)) /* valid and not used? */ \
198 { \
199 RevDoSwap(); /* put mark (-1) in point array to indicate a swap */ \
200 i2 = LookUp(tri,triangles[prev_tri].p[prev_i2]); \
201 i1 = LookUp(tri,triangles[prev_tri].p[prev_i0]); \
202 i0 = other_index[i1][i2]; \
203 } \
204 else \
205 tri = -1; /* dead end...end the strip */ \
206 } \
207 } \
208 }
209
210
211 #define Bytes(ntri) (int)(ntri/8+1)
212 #define Byte(tri) (int)(tri/8)
213 #define Mask(tri) (unsigned char)(1<<(tri%8))
214 #define MarkTri(tri) usedArray[Byte(tri)] |= Mask(tri)
215
216
217 /*
218 * Choose the indices for the 1st triangle in a strip. Look ahead 2
219 * triangles (the 1st 3 if's) to try to force a 3-triangle strip. If
220 * this fails, then try to get at least a 2-triangle strip (the next 2
221 * if's).
222 *
223 * This macro was revised in version 5.0.2.3 to always produce a
224 * clockwise orientation of vertices for the initial triangle, since this
225 * was required by the Sun XGL graphics programming interface. This
226 * seems to be desirable for all architectures since it allows hardware
227 * to compute consistent normals when producing flat shading from fields
228 * with position-dependent normals.
229 *
230 * With the demise of the "flat shade" rendering approximation it may be
231 * more efficient to add an architecture dependency to this macro, since
232 * that would allow for more flexibility in choosing the initial triangle
233 * indices that will produce the longest strip.
234 */
235 #define InitFirstTri(i0,i1,i2) \
236 { \
237 if (GoodTri( neighbors[tri].p[2] ) && \
238 GoodTri(neighbors[neighbors[tri].p[2]].p[LookUp(neighbors[tri].p[2], \
239 triangles[tri].p[0])])) \
240 {i0 = 2; i1 = 0; i2 = 1;} \
241 else \
242 if (GoodTri( neighbors[tri].p[1] ) && \
243 GoodTri(neighbors[neighbors[tri].p[1]].p[LookUp(neighbors[tri].p[1], \
244 triangles[tri].p[2])])) \
245 {i0 = 1; i1 = 2; i2 = 0;} \
246 else \
247 if (GoodTri( neighbors[tri].p[0] ) && \
248 GoodTri(neighbors[neighbors[tri].p[0]].p[LookUp(neighbors[tri].p[0], \
249 triangles[tri].p[1])])) \
250 {i0 = 0; i1 = 1; i2 = 2;} \
251 else \
252 if (GoodTri(neighbors[tri].p[2])) \
253 {i0 = 2; i1 = 0; i2 = 1;} \
254 else \
255 if (GoodTri(neighbors[tri].p[1])) \
256 {i0 = 1; i1 = 2; i2 = 0;} \
257 else \
258 {i0 = 0; i1 = 1; i2 = 2;} \
259 }
260
261
262 /************************************************************
263 prev_i0 prev_i2
264 i1 triangles = 0 1 6, 5 6 1,...
265 6-----------5-----------4 strip = 0,6,1,5,2...
266 / \ prev_tri/ \ / \
267 / \ / \ / \
268 / \ / \ / \
269 / \ / tri \ / \
270 / \ / \ / \
271 0-----------1-----------2-----------3
272 i0 i2
273 prev_i1
274 *************************************************************/
275
276
277 static Triple
getNeighbors(xfieldT * xf)278 *getNeighbors (xfieldT *xf)
279 {
280 /*
281 * Gets an array giving all the neighbors of a given triangle.
282 * neighbor[tri].p[n] is the triangle adjacent to triangle tri, across
283 * from triangle tri's nth point. A -1 indicates no triangle is
284 * adjacent across from the nth point.
285 */
286
287 ENTRY(("getNeighbors(0x%x)", xf));
288
289 if (!xf->neighbors_array)
290 {
291 EXIT(("couldn't get neighbors from field"));
292 DXErrorReturn (ERROR_INTERNAL, "#13870") ;
293 }
294
295 if (!DXTypeCheck (xf->neighbors_array, TYPE_INT, CATEGORY_REAL, 1, 3))
296 {
297 EXIT(("neighbors array has bad type"));
298 DXErrorReturn (ERROR_INTERNAL, "#13870") ;
299 }
300
301 EXIT((""));
302 return (Triple *) DXGetArrayData(xf->neighbors_array) ;
303 }
304
305
306 #define FreeTempStrips() \
307 { \
308 for (i = 0 ; i < nStrips ; i++) \
309 if (stripArray[i].point) \
310 tdmFree((Pointer) stripArray[i].point) ; \
311 \
312 tdmFree((Pointer) stripArray) ; \
313 }
314
315 typedef struct
316 {
317 int *meshes;
318 int nmeshes;
319 int *connections;
320 int nconnections;
321 Array meshArray;
322 Array connectionArray;
323 } TMeshS, *TMesh;
324
325 static Error
_deleteTMesh(void * p)326 _deleteTMesh(void *p)
327 {
328 TMesh t = (TMesh)p;
329 if (t->connectionArray)
330 DXDelete((dxObject)t->connectionArray);
331 if (t->meshArray)
332 DXDelete((dxObject)t->meshArray);
333
334 DXFree(p);
335
336 return OK;
337 }
338
339 static Error
_newTMesh(int nStrips,int nStrippedPts,TMesh * mesh,dxObject * o)340 _newTMesh(int nStrips, int nStrippedPts, TMesh *mesh, dxObject *o)
341 {
342 Private priv = NULL;
343 TMesh tmp = NULL;
344
345 *mesh = NULL;
346 *o = NULL;
347
348 tmp = (TMesh)DXAllocateZero(sizeof(TMeshS));
349 if (! tmp)
350 return ERROR;
351
352 tmp->meshArray = DXNewArray(TYPE_INT, CATEGORY_REAL, 1, 2);
353 if (! tmp->meshArray)
354 goto error;
355
356 DXReference((dxObject)tmp->meshArray);
357
358 if ( !DXAllocateArray (tmp->meshArray, nStrips))
359 goto error;
360
361 tmp->connectionArray = DXNewArray(TYPE_INT, CATEGORY_REAL, 0);
362 if (! tmp->connectionArray)
363 goto error;
364
365 DXReference((dxObject)tmp->connectionArray);
366
367 if ( !DXAllocateArray (tmp->connectionArray, nStrippedPts))
368 goto error;
369
370 tmp->meshes = (int *)DXGetArrayData(tmp->meshArray);
371 tmp->connections = (int *)DXGetArrayData(tmp->connectionArray);
372 tmp->nmeshes = nStrips;
373 tmp->nconnections = nStrippedPts;
374
375 priv = (Private)DXNewPrivate((Pointer)tmp, _deleteTMesh);
376 if (! priv)
377 goto error;
378
379 *mesh = tmp;
380 *o = (dxObject)priv;
381
382 return OK;
383
384 error:
385 if (tmp)
386 {
387 if (tmp->connectionArray)
388 DXDelete((dxObject)tmp->connectionArray);
389 if (tmp->meshArray)
390 DXDelete((dxObject)tmp->meshArray);
391
392 DXFree((Pointer)tmp);
393 }
394
395 return ERROR;
396 }
397
398 static void
_installTMeshInfo(xfieldT * xf,TMesh tmesh)399 _installTMeshInfo(xfieldT *xf, TMesh tmesh)
400 {
401 if (xf->connections)
402 DXFreeArrayHandle(xf->connections);
403
404 if (xf->connections_array)
405 DXDelete((dxObject)xf->connections_array);
406
407 xf->connections = NULL;
408 xf->connections_array = (Array)DXReference((dxObject)tmesh->connectionArray);
409 xf->nconnections = tmesh->nconnections;
410 xf->meshes = (Array)DXReference((dxObject)tmesh->meshArray);
411 xf->nmeshes = tmesh->nmeshes;
412 xf->posPerConn = 1;
413 xf->connectionType = ct_tmesh;
414 }
415
416
417 Error
_dxf_trisToTmesh(xfieldT * xf,tdmChildGlobalP globals)418 _dxf_trisToTmesh (xfieldT *xf, tdmChildGlobalP globals)
419 {
420 DEFGLOBALDATA(globals) ;
421 Triple *neighbors ; /* neighbors array gives a tri's neighbors */
422 Tstrip *stripArray = 0 ; /* temp array of strips */
423 int point[MaxTstripSize] ; /* temp array in which to build point list */
424 char *usedArray = 0 ; /* temp array to mark triangles already used */
425 int nStrips = 0 ; /* number of strips generated */
426 int nStrippedPts = 0 ; /* number of points stripped */
427 int nPtsInStrip ; /* number of points in current strip */
428 int start_tri ; /* first triangle of the strip */
429 int tri ; /* the current triangle */
430 int i0, i1, i2 ; /* the 3 indexes into triangles[tri].p[?] */
431 int init_tri, init_i0, /* initial triangle and index configuration */
432 init_i1, init_i2 ;
433 int prev_tri, prev_i0, /* used to determine the same current info */
434 prev_i1, prev_i2 ;
435 int rev_start ; /* index of first of the reversed point list */
436 int rev_pts ; /* keeps count of how many rev points */
437 /* we've collected to avoid swapping */
438 /* reverse stage... see RevDoSwap() */
439 Triple *triangles ; /* array of original triangle connections */
440 int ntriangles ; /* number of original triangle connections */
441 int i, j, k, p, tp ; /* misc. loop indices */
442 TMesh tmesh = NULL;
443 dxObject tmesho = NULL;
444 char * tmesh_or_sens;
445 int orsens = 0;
446
447 ENTRY(("_dxf_trisToTmesh(0x%x)", xf));
448 tmesh_or_sens = (char *)getenv("DX_HW_TMESH_ORIENT_SENSITIVE");
449 if(tmesh_or_sens) {
450 sscanf(tmesh_or_sens, "%d", &orsens);
451 }
452
453 tmesho = (dxObject)_dxf_QueryObject(MESHHASH, (dxObject)xf->field);
454 if (tmesho)
455 {
456 xf->meshObject = DXReference(tmesho);
457 tmesh = (TMesh)DXGetPrivateData((Private)tmesho);
458 _installTMeshInfo(xf, tmesh);
459
460 return OK;
461 }
462
463 if (xf->connectionType != ct_triangles)
464 {
465 EXIT(("xf->connectionType not ct_triangles"));
466 return OK ;
467 }
468
469 PRINT(("invalid connections: %d",
470 xf->invCntns? DXGetInvalidCount(xf->invCntns): 0));
471
472 /* get triangle connection info */
473 triangles = DXGetArrayData(xf->connections_array) ;
474 ntriangles = xf->nconnections ;
475 /*npoints = xf->npositions ;*/
476
477 xf->origNConnections = ntriangles;
478 xf->origConnections_array = xf->connections_array;
479 xf->connections_array = NULL;
480
481 /* get array containing connection neighbors */
482 if (!(neighbors = getNeighbors(xf)))
483 {
484 PRINT(("could not obtain mesh neighbors"));
485 DXErrorGoto (ERROR_INTERNAL, "#13870") ;
486 }
487
488 /* allocate temporary data structures of maximum possible size */
489 if (!(usedArray = tdmAllocateZero(sizeof(char)*Bytes(ntriangles))) ||
490 !(stripArray = (Tstrip *) tdmAllocate(sizeof(Tstrip)*ntriangles)))
491 {
492 PRINT(("out of memory"));
493 DXErrorGoto(ERROR_NO_MEMORY, "#13000") ;
494 }
495
496 /* strip the field, placing strip info into temporary arrays */
497 for (start_tri = 0 ; start_tri < ntriangles ; start_tri++)
498 {
499 if (GoodTri(start_tri))
500 {
501 nPtsInStrip = 0;
502 tri = start_tri;
503 InitFirstTri(i0,i1,i2); /* pick initial vertices for 1st triangle */
504 init_tri = tri; /* remember where we started */
505 init_i0 = i0; init_i1 = i1; init_i2 = i2;
506 AddPoint(tri,i0); /* add the 1st two... */
507 AddPoint(tri,i1); /* ...points to the mesh */
508 while (tri >= 0) /* while there's a valid triangle to add...*/
509 {
510 AddPoint(tri,i2); /* add another triangle to the strip */
511 MarkTri(tri); /* mark it as used */
512 NextTri(tri); /* move on to next triangle */
513 }
514
515 /* now go the other way out of the initial triangle... */
516 tri = init_tri; /* go back to initial triangle */
517 i0 = init_i0; i1 = init_i1; i2 = init_i2;
518 rev_start = nPtsInStrip ;
519 rev_pts = 0; /* keep track of pts we collect backwards */
520 if(orsens)
521 tri = -1;
522 else
523 {
524 RevNextTri(tri); /* move BACK to PREV triangle */
525 }
526
527 while (tri >= 0) /* while there's a valid triangle to add...*/
528 {
529 AddPoint(tri,i0); /* add another triangle to the strip */
530 rev_pts++; /* another backward point */
531 MarkTri(tri); /* mark it as used */
532 if(orsens)
533 tri = -1;
534 else {
535 RevNextTri(tri); /* move BACK to PREV triangle */
536 }
537 }
538
539 /* allocate temporary points of appropriate size */
540 if (!(stripArray[nStrips].point =
541 (int*) tdmAllocate(nPtsInStrip * sizeof(int))))
542 {
543 PRINT(("out of memory"));
544 DXErrorGoto(ERROR_NO_MEMORY, "#13000") ;
545 }
546
547 /* copy and reverse reversed points from "point" to "tstrip->point" */
548 for (tp=nPtsInStrip-1, p=0 ; tp>=rev_start ; tp--, p++)
549 stripArray[nStrips].point[p] = point[tp] ;
550
551 /* copy forward points from "point" to "tstrip->point" */
552 bcopy (point, &(stripArray[nStrips].point[p]),
553 (nPtsInStrip-p) * sizeof(int)) ;
554
555 /* record tstrip info */
556 stripArray[nStrips].points = nPtsInStrip ;
557 nStrips++ ;
558 nStrippedPts += nPtsInStrip ;
559 }
560 }
561
562 PRINT(("stripped %d triangles", nStrippedPts - 2*nStrips));
563 PRINT(("generated %d strips", nStrips));
564 PRINT(("average number of triangles per strip: %f",
565 nStrips? (nStrippedPts - 2*nStrips)/(float)nStrips: 0));
566
567 if (! _newTMesh(nStrips, nStrippedPts, &tmesh, &tmesho))
568 goto error;
569
570 for (i=j=k=0 ; i<nStrips ; i++)
571 {
572 /* record start index and number of points in strip */
573
574 tmesh->meshes[j++] = k;
575 tmesh->meshes[j++] = stripArray[i].points ;
576 memcpy(tmesh->connections+k, stripArray[i].point, stripArray[i].points*sizeof(int));
577 k += stripArray[i].points;
578 }
579
580 _dxf_InsertObject(MESHHASH, (dxObject)xf->field, (dxObject)tmesho);
581 xf->meshObject = DXReference(tmesho);
582 _installTMeshInfo(xf, tmesh);
583
584 /* free temporary arrays */
585 tdmFree((Pointer)usedArray) ;
586 FreeTempStrips() ;
587
588 EXIT(("OK"));
589 return OK ;
590
591 error:
592 if (tmesho)
593 DXDelete(tmesho);
594 if (usedArray)
595 tdmFree((Pointer)usedArray);
596 if (stripArray)
597 FreeTempStrips() ;
598
599 EXIT(("ERROR"));
600 return 0 ;
601 }
602