Removed C++-style "//" comments to allow C sources to be built with C compilers.
[dyninst.git] / visiClients / terrain / src / colorize.c
1 /*
2  * Copyright (c) 1989, 1990 Barton P. Miller, Morgan Clark, Timothy Torzewski
3  *     Jeff Hollingsworth, and Bruce Irvin. All rights reserved.
4  *
5  * This software is furnished under the condition that it may not
6  * be provided or otherwise made available to, or used by, any
7  * other person.  No title to or ownership of the software is
8  * hereby transferred.  The name of the principals
9  * may not be used in any advertising or publicity related to this
10  * software without specific, written prior authorization.
11  * Any use of this software must include the above copyright notice.
12  *
13  */
14
15 /*
16  * colorize.c - colorize surfaces according to their height.
17  *
18  * $Id: colorize.c,v 1.6 1998/03/30 01:22:20 wylie Exp $
19  */
20
21 #include <stdio.h>
22 #include <string.h>
23 #include <stdlib.h>
24    
25 #include "misc.h"
26 #include "graph3d.h"
27 #include "terrain.h"
28 #include "colorize.h"
29    
30 #define TRUE    1
31 #define FALSE   0
32
33 /* Internal representation of polygon -- a linked list of points */
34
35 struct ptLstNode_t {
36    float x,y,z;
37    struct ptLstNode_t *next;
38 };
39
40 typedef struct ptLstNode_t *ptLst_t;
41
42 /* The z-tic list -- map height (z coord) to colors */
43
44 struct ticNode_t {
45    float z;
46    int color;
47    struct ticNode_t *next;
48 };
49
50 typedef struct ticNode_t *ticLst_t;
51
52 void draw_colorPoly();
53 void colorPoly(ptLst_t, int);
54 void colorize(ptLst_t, ticLst_t);
55 void colorizeLayers(ptLst_t, ticLst_t);
56  
57 ptLst_t findGoUnder(/*ptLst_t, ptLst_t, float*/);
58 ptLst_t findGoAbove(/*ptLst_t, ptLst_t, float*/);
59 ptLst_t makeMidPt(/*ptLst_t, float*/);
60 ptLst_t copyPt(/*ptLst_t*/);
61 void freePtLst(/*ptLst_t*/);
62
63 extern float zmin, zmax;        /* Max & min points of the graph */
64 extern int Ntcolors;            /* Number of colors available */
65
66 static int pix = 0;
67
68 /*******************************************************************
69 * draw_colorPoly - Draw a colorized polygon.
70 *
71 * draw_colorPoly takes 4 points and draw it with colors.  The colors
72 * used are determined by the z dimension of the polygon the the z-tics.
73 * If the polygon run accross more than one z-tics, the polygon will
74 * be cut up and assigned with diffrernt colors.
75 *
76 *******************************************************************/
77
78 void draw_colorPoly(x1,y1,z1,x2,y2,z2,x3,y3,z3,x4,y4,z4, remap, pix_map)
79 float x1,y1,z1,x2,y2,z2,x3,y3,z3,x4,y4,z4;
80 int remap;
81 int pix_map;
82 {
83    static ticLst_t tics=NULL;
84    ticLst_t curTic;
85    ptLst_t drawLst, curPt;
86    ticLst_t next;
87
88    int i;
89    float curZ, ticSize;
90
91    /* Initialize the tic list (mapping between z and colors if that */
92    /* has not been done yet or there is change in maxz.             */
93
94    if (remap == -1 && tics != NULL)
95    {
96       while(tics->next != NULL)
97       {
98            next = tics->next;
99            free(tics);
100            tics = next;
101       }
102
103       free(tics);
104       tics = NULL;
105    }
106       
107    if (tics==NULL) {
108       curTic = tics = (ticLst_t) terrain_alloc(sizeof(struct ticNode_t));
109        
110       curZ = zmin;
111       ticSize = (zmax - zmin)/Ntcolors;
112       for (i=0; i<Ntcolors - 1; i++) {
113          curTic->z = curZ+=ticSize;
114          curTic->color = i;
115          curTic->next = (ticLst_t) terrain_alloc(sizeof(struct ticNode_t));
116          curTic = curTic->next;
117       }
118       curTic->z = curZ+=ticSize;
119       curTic->color = i;
120       curTic->next = NULL;
121    }
122    
123 #ifdef COLORIZE_DEBUG
124    
125    printf("(%1.2lf %1.2lf %1.1lf)-(%1.2lf %1.2lf %1.1lf)-(%1.2lf %1.2lf %1.1lf)-(%1.2lf %1.2lf %1.1lf)\n", x1,y1,z1,x2,y2,z2,x3,y3,z3,x4,y4,z4);
126    
127 #endif
128
129    /* Convert the points into internation representation */
130
131    drawLst = (ptLst_t) terrain_alloc(sizeof(struct ptLstNode_t));
132    drawLst->x = x1;
133    drawLst->y = y1;
134    drawLst->z = z1;
135    drawLst->next = (ptLst_t) terrain_alloc(sizeof(struct ptLstNode_t));
136    
137    curPt = drawLst->next;
138
139    curPt->x = x2;
140    curPt->y = y2;
141    curPt->z = z2;
142    curPt->next = (ptLst_t) terrain_alloc(sizeof(struct ptLstNode_t));
143
144    curPt = curPt->next;
145
146    curPt->x = x3;
147    curPt->y = y3;
148    curPt->z = z3;
149    curPt->next = (ptLst_t) terrain_alloc(sizeof(struct ptLstNode_t));
150
151    curPt = curPt->next;
152
153    curPt->x = x4;
154    curPt->y = y4;
155    curPt->z = z4;
156    curPt->next = NULL;
157
158    /* set whether draw on pixmap or on actual window */
159    pix = pix_map;
160
161    /* Do the real job */
162
163    colorize(drawLst, tics);
164    
165 #ifdef COLORIZE_DEBUG
166    
167    printf("\n");
168    
169 #endif
170    
171 }
172
173
174
175 /*********************************************************************
176 *
177 * colorPoly - draw the polygon defined by "pts" with "color"
178 *             This routine calls the X driver.
179 *
180 *********************************************************************/
181
182
183 void colorPoly(pts, color)
184 ptLst_t pts;
185 int color;
186 {
187    ptLst_t curPt;
188    int i, size=0;
189    unsigned *dpts;
190
191    /* Check how many points the polygon has */
192
193    for(curPt = pts; curPt->next != pts; curPt = curPt->next) {
194       
195 #ifdef COLORIZE_DEBUG
196       
197       printf("  %10.6lf %10.6lf %10.6lf -- %d\n",
198              curPt->x, curPt->y, curPt->z, color);
199       
200 #endif
201       
202       size++;
203    }
204    
205 #ifdef COLORIZE_DEBUG
206    
207    printf("     %10.6lf %10.6lf %10.6lf -- %d\n",
208           curPt->x, curPt->y, curPt->z, color);
209    
210 #endif
211    
212    size++;
213
214    dpts = (unsigned *)terrain_alloc(sizeof(unsigned)*size*2);
215    
216    for (i=0, curPt = pts; i<size; i++, curPt = curPt->next)
217       map3d_xy(curPt->x, curPt->y, curPt->z, 
218                &(dpts[i<<1]), &(dpts[(i<<1)+1]));
219    
220
221    if (pix > 0)
222       X11_colorPoly_window(dpts, size, color);
223
224       X11_colorPoly(dpts, size, color);
225
226    free(dpts);
227 }
228
229
230
231 /*********************************************************************
232 *
233 * colorize - find out the lowerest point of the polygon and start
234 *            the colorization rolling from there.
235 *
236
237 *********************************************************************/
238
239
240 void colorize(pts, tics)
241 ptLst_t pts;                    /* Points of the polygon */
242 ticLst_t tics;                  /* List of all tics  */
243 {
244    ticLst_t curTic;
245    ptLst_t curPt;
246    float minZ;
247    
248    /* Search for the lowerest point */
249    curPt = pts;
250    minZ = curPt->z;
251    for (curPt = pts; curPt->next != NULL; curPt = curPt->next)
252       minZ = (curPt->next->z < minZ)? curPt->next->z : minZ;
253    
254    /* Make the list circular */
255    curPt->next = pts;
256    
257    /* Skip irrevalent tics */
258    curTic = tics;
259    while ((curTic->next != NULL) && (curTic->z <= minZ))
260       curTic = curTic->next;
261    
262    if (curTic->next == NULL)
263       colorPoly(pts, curTic->color);
264    else
265       colorizeLayers(pts, curTic);
266    
267    return;
268 }
269
270
271
272
273
274 /*********************************************************************
275 *
276 * colorizeLayers - cut the polygon into levels accroding to the z-tics,
277 *                  and draw them with colors.
278 *
279 *********************************************************************/
280
281
282 void colorizeLayers(pts, tic)
283 ptLst_t pts;
284 ticLst_t tic;
285 {
286    ptLst_t curPt, startPt, goUnderPt, goAbovePt, drawPt, newPt;
287    ticLst_t curTic;
288    int done = FALSE;
289    
290    curTic = tic;
291    startPt = pts;               /* Keep the while loop happy */
292    
293    /* Start filling the surface now */
294    while((curTic->next != NULL) && (startPt != NULL)) {
295       
296       /* Find a start point */
297       if ((curPt = findGoUnder(startPt, startPt, curTic->z)) == NULL) {
298          /* All points are under the current tic */
299          colorPoly(startPt, curTic->color);
300          freePtLst(startPt);
301          startPt = NULL;
302       } else {
303          /* Calculate the real start point and add that to the list */
304          startPt = curPt;
305          if (startPt->z != curTic->z) {
306             newPt = makeMidPt(startPt, curTic->z);
307             newPt->next = startPt->next;
308             startPt->next = newPt;
309             curPt = startPt = goUnderPt = newPt;
310          } else {
311             curPt = goUnderPt = startPt;
312          }
313          
314          /* Walk through all points in that level and form sub-polygons */
315          /* Note that there can be more than one sub-polygon in one level */
316
317          done = FALSE;
318          while(!done) {
319             if ((goAbovePt = findGoAbove(curPt, startPt, curTic->z)) == NULL) {
320
321                /* Done if we run out of points */
322
323                colorPoly(startPt, curTic->color);
324                freePtLst(startPt);
325                return;
326             } else {
327
328                /* Find the end point of the sub-polygon */
329
330                if (goAbovePt->z != curTic->z) {
331                   newPt = makeMidPt(goAbovePt, curTic->z);
332                   newPt->next = goAbovePt->next;
333                   drawPt = copyPt(goUnderPt);
334                   curPt = goUnderPt->next = newPt;
335                   goAbovePt->next = copyPt(newPt);
336                   goAbovePt->next->next = drawPt;
337                } else {
338                   newPt = copyPt(goAbovePt);
339                   curPt = goAbovePt->next = newPt;
340                   drawPt = copyPt(goUnderPt);
341                   goUnderPt->next = newPt;
342                   goAbovePt->next = drawPt;
343                }
344                
345                /* Draw it ! */
346
347                colorPoly(drawPt, curTic->color);
348                freePtLst(drawPt);
349             }
350             
351             /* Search for next point under the tic and start over */
352             if ((goUnderPt = findGoUnder(curPt, startPt, curTic->z)) == NULL)
353                done = TRUE;
354             else {
355                if (goUnderPt->z != curTic->z) {
356                   newPt = makeMidPt(goUnderPt, curTic->z);
357                   newPt->next = goUnderPt->next;
358                   goUnderPt->next = newPt;
359                   curPt = goUnderPt = newPt;
360                } else {
361                   curPt = goUnderPt;
362                }
363             }
364          }
365          
366 #ifdef COLORIZE_DEBUG
367          
368          for (curPt=startPt; curPt->next!=startPt; curPt=curPt->next)
369             printf("   (%1.1lf,%1.1lf,%1.1lf)-", curPt->x, curPt->y, curPt->z);
370          
371          printf("   (%1.1lf,%1.1lf,%1.1lf)\n", curPt->x, curPt->y, curPt->z);
372          
373 #endif
374          
375       }
376       
377       curTic = curTic->next;
378    }
379    
380    /* If there are remaining points, they must be above all the tics */
381    if (startPt != NULL) {
382       colorPoly(startPt, curTic->color);
383       freePtLst(startPt);
384    }
385    
386    return;
387 }
388
389
390
391
392 /*********************************************************************
393 *
394 * findGoUnder - walk along the current sub-polygon and find a coordinate
395 *               which has the z coordinate value of "z" and its last point
396 *               is above the surface z and its next point below z.
397 *               Note that the point may not be a existing point.  It can
398 *               be somewhere between the existing points.
399 *
400 * Returns:
401 *    ptLst_t : The new point found.
402 *              NULL means all points of the current sun-polygon are
403 *              above z.
404 *
405 *********************************************************************/
406
407
408 ptLst_t
409 findGoUnder(startPt, endPt, z)
410 ptLst_t startPt, endPt;         /* Range of the search */
411 float z;                        /* the z coordinate of the new point */
412 {
413    ptLst_t curPt;
414    
415 #ifdef COLORIZE_DEBUG
416    printf("V          ");
417    
418    for (curPt=startPt; curPt->next!=startPt; curPt=curPt->next) {
419       if (curPt==endPt)
420          printf("[%1.1lf,%1.1lf,%1.1lf]-", curPt->x, curPt->y, curPt->z);
421       else
422          printf("(%1.1lf,%1.1lf,%1.1lf)-", curPt->x, curPt->y, curPt->z);
423    }
424    
425    if (curPt==endPt)
426       printf("[%1.1lf,%1.1lf,%1.1lf]\n", curPt->x, curPt->y, curPt->z);
427    else
428       printf("(%1.1lf,%1.1lf,%1.1lf)\n", curPt->x, curPt->y, curPt->z);
429    
430 #endif
431    
432    if (startPt->z >= z && startPt->next->z < z) {
433       
434 #ifdef COLORIZE_DEBUG
435       
436       printf("V            %1.1lf >= %1.1lf, %1.1lf < %1.1lf\n",
437              startPt->z, z, startPt->next->z, z);
438       
439 #endif
440       
441       return startPt;
442    }
443    
444    for (curPt=startPt->next;
445         (curPt != endPt) && !(curPt->z >= z && curPt->next->z < z);
446         curPt = curPt->next)
447       
448 #ifdef COLORIZE_DEBUG
449       
450       printf("V            %1.1lf >= %1.1lf, %1.1lf < %1.1lf\n",
451              curPt->z, z, curPt->next->z, z);
452    
453    printf("V            The anser is : %c\n", (curPt != endPt)?'T':'F');
454    
455 #else
456    ;
457 #endif
458    
459    return (curPt != endPt)? curPt : NULL;
460 }
461
462
463
464
465 /*********************************************************************
466 *
467 * findGoAbove - walk along the current sub-polygon and find a coordinate
468 *               which has the z coordinate value of "z" and its last point
469 *               is below the surface z and its next point is above z.
470 *               Note that the point may not be a existing point.  It can
471 *               be somewhere between the existing points.
472 *
473 * Returns:
474 *    ptLst_t : The new point found.
475 *              NULL means all points of the current sun-polygon are
476 *              above z.
477 *
478 *********************************************************************/
479
480
481 ptLst_t
482 findGoAbove(startPt, endPt, z)
483 ptLst_t startPt, endPt;         /* Start & end pts of the current polygon */
484 float z;                        /* The z coordinate value to be tested */
485 {
486    ptLst_t curPt;
487    
488 #ifdef COLORIZE_DEBUG
489    printf("^          ");
490    
491    for (curPt=startPt; curPt->next!=startPt; curPt=curPt->next) {
492       if (curPt==endPt)
493          printf("[%1.1lf,%1.1lf,%1.1lf]-", curPt->x, curPt->y, curPt->z);
494       else
495          printf("(%1.1lf,%1.1lf,%1.1lf)-", curPt->x, curPt->y, curPt->z);
496    }
497    
498    if (curPt==endPt)
499       printf("[%1.1lf,%1.1lf,%1.1lf]\n", curPt->x, curPt->y, curPt->z);
500    else
501       printf("(%1.1lf,%1.1lf,%1.1lf)\n", curPt->x, curPt->y, curPt->z);
502    
503 #endif
504    
505    if (startPt->z < z && startPt->next->z >= z)
506       return startPt;
507    
508 #ifdef COLORIZE_DEBUG
509    
510    printf("^            %1.1lf <= %1.1lf, %1.1lf > %1.1lf\n",
511           startPt->z, z, startPt->next->z, z);
512    
513 #endif
514    
515    for (curPt=startPt->next;
516         (curPt != endPt) && !(curPt->z < z && curPt->next->z >= z);
517         curPt = curPt->next)
518       
519 #ifdef COLORIZE_DEBUG
520       
521       printf("^            %1.1lf <= %1.1lf, %1.1lf > %1.1lf\n",
522              curPt->z, z, curPt->next->z, z);
523    
524    printf("^            The anser is : %c\n", (curPt != endPt)?'T':'F');
525    
526 #else
527    ;
528 #endif
529    
530    return (curPt != endPt)? curPt : NULL;
531    
532 }
533
534
535
536
537
538 /*********************************************************************
539 *
540 * makeMidPt - produce a new point which is between two given points and
541 *             with it has the value "z" as its z coordinate.
542 *             One can think of the point as the intersection between
543 *             the line pt, pts->next and a horizontal line z.
544 *
545 * Returns:
546 *    ptLst_t : The new point.
547 *
548 *********************************************************************/
549
550
551 ptLst_t
552 makeMidPt(pts, z)
553 ptLst_t pts;
554 float z;
555 {
556    ptLst_t newPt;               /* The new 'middle' point */
557    float zIndex;
558    
559    if ((newPt = (ptLst_t) terrain_alloc(sizeof(struct ptLstNode_t))) == NULL) {
560       printf("Memory allocation error\n");
561       exit(-1);
562    }
563
564    /* x & y coordinate are between pts and pts->next and weighted by z */
565    
566    zIndex = (pts->z - z)/(pts->z -  pts->next->z);
567    newPt->z = z;
568    newPt->x = pts->x + ((pts->next->x - pts->x) * zIndex);
569    newPt->y = pts->y + ((pts->next->y - pts->y) * zIndex);
570    newPt->next = NULL;
571    
572    return newPt;
573 }
574
575
576
577
578 /*********************************************************************
579 *
580 * freePtLst - Free a list of points.
581 *
582 *********************************************************************/
583
584
585 void freePtLst(pts)
586 ptLst_t pts;
587 {
588    ptLst_t lastPt, curPt;
589    
590    curPt = pts;
591    while(curPt->next != pts) {
592       lastPt = curPt;
593       curPt = curPt->next;
594       free(lastPt);
595    }
596    
597    free(curPt);
598    
599    return;
600 }
601
602
603
604
605 /*********************************************************************
606 *
607 * copyPt - duplicate a point.
608 *
609 * Returns:
610 *  ptLst_t  : The new copy of the point given
611 *
612 *********************************************************************/
613
614 ptLst_t
615 copyPt(source)
616 ptLst_t source;
617 {
618    ptLst_t target;
619    
620    if ((target = (ptLst_t) terrain_alloc(sizeof(struct ptLstNode_t))) == NULL) {
621       printf("Memory allocation error.\n");
622       exit(-1);
623    }
624    
625 #ifdef BCOPY
626    bcopy(source, target, sizeof(struct ptLstNode_t));
627 #else
628    memcpy(target, source, sizeof(struct ptLstNode_t));
629 #endif
630    
631    return target;
632 }