/* Draws the next view of a 3-d plot. The physical coordinates of */
/* the points for the next view are placed in the n points of arrays  */
/* u and v. The silhouette found so far is stored in the heap as a */
/* set of m peak points. */

/* Define the heap size.  This can be increased if necessary.  Someday */
/* I hope to just allocate a heap space of minimum required size.      */
#define  heaps    4000

#include <stdio.h>
#include <stdlib.h>
#include "plplot.h"
#include "declare.h"

static int m, x, y;

void plnxtv(u,v,n,init)
int u[], v[], n, init;
{
      int xx;
      int i, j, first;
      int sx1, sx2, sy1, sy2;
      int su1, su2, sv1, sv2;
      int cx, cy, px, py;
      int seg, ptold, lstold, pthi, pnewhi, newhi, change, ochange;
      
      first = 1;
      pnewhi = 0;
      
      /* For the initial set of points, just display them and store them as */
      /* the peak points. */

      if (init == 1) {
         if( heap3 == NULL)  /* heap not yet allocated so ... */
            if(( heap3 = (int *)malloc(heaps*sizeof(int))) == NULL)
               fatal("Not enough heap space in PLNXTV.");
         y = heaps - n;
         x = y - n;
         movphy(u[0],v[0]);
         heap3[x] = u[0];
         heap3[y] = v[0];
         for (i=1; i<n; i++){
           draphy(u[i],v[i]);
           heap3[x+i] = u[i];
           heap3[y+i] = v[i];
         }
         m = n;
         return;
      }

      /* Otherwise, we need to consider hidden-line removal problem. We scan */
      /* over the points in both the old (i.e. heap3[x...] and heap3[y...]) and */
      /* new (i.e. u[] and v[]) arrays in order of increasing x coordinate. */
      /* At each stage, we find the line segment in the other array (if one */
      /* exists) that straddles the x coordinate of the point. We */
      /* have to determine if the point lies above or below the line segment, */
      /* and to check if the below/above status has changed since the last */
      /* point. */

      /* If init = 2 we do not update the view, this is useful for drawing */
      /* lines on the graph after we are done plotting points.  Hidden line */
      /* removal is still done, but the view is not updated. */
      xx = 0;
      i = 0;
      j = 0;

      /* (heap3[x+i], heap3[y+i]) is the i'th point in the old array */
      /* (u[j], v[j])           is the j'th point in the new array */

      while (i < m || j < n) {

        /* The coordinates of the point under consideration are (px,py). */
        /* The line segment joins (sx1,sy1) to (sx2,sy2). */

        /* "ptold" is true if the point lies in the old array. We set it */
        /*  by comparing the x coordinates of the i'th old point */
        /*  and the j'th new point, being careful if we have fallen past */
        /*  the edges. Having found the point, load up the point and */
        /*  segment coordinates appropriately. */
 
        ptold = ((heap3[x+i] < u[j] && i<m) || j>= n);
        if (ptold) {
          px = heap3[x+i];
          py = heap3[y+i];
          seg = j>0 && j<n;
          if (seg) {
            sx1 = u[j-1];
            sy1 = v[j-1];
            sx2 = u[j];
            sy2 = v[j];
          }
        }
        else {
          px = u[j];
          py = v[j];
          seg = i>0 && i<m;
          if (seg) {
            sx1 = heap3[x+i-1];
            sy1 = heap3[y+i-1];
            sx2 = heap3[x+i];
            sy2 = heap3[y+i];
          }
        }

        /* Now determine if the point is higher than the segment, using the */
        /* logical function "above". We also need to know if it is */
        /* the old view or the new view that is higher. "newhi" is set true */
        /* if the new view is higher than the old */

        if(seg)
            pthi = plabv(px,py,sx1,sy1,sx2,sy2);
        else
            pthi = 1;

        newhi = (ptold && !pthi) || (!ptold && pthi);
        change = (newhi && !pnewhi) || (!newhi && pnewhi);

        /* There is a new intersection point to put in the peak array if the */
        /* state of "newhi" changes */

        if (first) {
          movphy(px,py);
          first = 0;
          lstold = ptold;
          if (init != 2) {
            heap3[xx] = px;
            heap3[xx+1] = py;
            xx = xx + 2;
          }
          pthi = 0;
          ochange = 0;
        }
        else if (change) {
          /* Take care of special cases at end of arrays.  If init is 2 the */
          /* endpoints are not connected to the old view. */
          if (init==2 && ((!ptold && j==0)||(ptold && i==0))) {
            movphy(px,py);
            lstold = ptold;
            pthi = 0;
            ochange = 0;
          }
          else if (init==2 && ((!ptold && i>=m)||(ptold && j>=n))) {
            movphy(px,py);
            lstold = ptold;
            pthi = 0;
            ochange = 0;
          }
          /* If init is not 2 then we do want to connect the current line */
          /* with the previous view at the endpoints.  */
          /* Also find intersection point with old view. */
          else  {
            if (i == 0) {
              sx1 = heap3[x];
              sy1 = -1;
              sx2 = heap3[x];
              sy2 = heap3[y];
            }
            else if (i >= m) {
              sx1 = heap3[x+m-1];
              sy1 = heap3[y+m-1];
              sx2 = heap3[x+m-1];
              sy2 = -1;
            }
            else {
              sx1 = heap3[x+i-1];
              sy1 = heap3[y+i-1];
              sx2 = heap3[x+i];
              sy2 = heap3[y+i];
            }

            if (j == 0) {
              su1 = u[0];
              sv1 = -1;
              su2 = u[0];
              sv2 = v[0];
            }
            else if (j >= n) {
              su1 = u[n-1];
              sv1 = v[n-1];
              su2 = u[n];
              sv2 = -1;
            }
            else  {
              su1 = u[j-1];
              sv1 = v[j-1];
              su2 = u[j];
              sv2 = v[j];
            }

            /* Determine the intersection */
            pl3cut(sx1,sy1,sx2,sy2,su1,sv1,su2,sv2,&cx,&cy);
            if (cx == px && cy == py)  {
              if (lstold && !ochange)
                movphy(px,py);
              else 
                draphy(px,py); 

              if (init != 2) {
                heap3[xx] = px;
                heap3[xx+1] = py;
                xx = xx+2;
              }
              lstold = 1;
              pthi = 0;
            }
            else {
              if (lstold && !ochange)
                 movphy(cx,cy);
              else
                 draphy(cx,cy);

              lstold = 1;
              if (init != 2) {
                heap3[xx] = cx;
                heap3[xx+1] = cy;
                xx = xx+2;
              }
            }
            ochange =1;
          }
        }

        /* If point is high then draw plot to point and update view. */
        if (pthi) {
          if (lstold && ptold)
            movphy(px,py);
          else 
            draphy(px,py); 

          if (init != 2) {
            heap3[xx] = px;
            heap3[xx+1] = py;
            xx = xx+2;
          }
          lstold = ptold;
          ochange = 0;
        }

        pnewhi = newhi;

        if (ptold)
          i = i+1;
        else
          j = j+1;

        if (xx>=x) fatal("Heap overflow in plnxtv.");
      }

      /* Transfer the peak points to the RHS of the heap */

      if(init != 2) {
        m = xx/2;
        xx = 0;
        y = heaps - m;
        x = y - m;
        for(i=0; i<m; i++) {
          heap3[x+i] = heap3[xx];
          heap3[y+i] = heap3[xx+1];
          xx = xx+2;
        }
      }
}