/* See dgmakegrid.h */
/* Last edited on 2004-06-19 21:25:00 by stolfi */

#include <dgmakegrid.h>
#include <dgtree.h>
#include <dgbezier.h>
#include <stdio.h>
#include <math.h>
#include <js.h>

dg_Node *dg_make_grid
  ( dg_Dim d,
    dg_CellIndex k,
    dg_Rank r,
    bz_Patch *b,
    dg_Node *p,
    dg_CellPredicate *omit,
    dg_CellPredicate *split
  )
  { dg_Node *n = NULL;
    fprintf(stderr, "+ dg_make_grid  cell = %lld  rank = %d\n", k, r); 
    affirm(r < DG_MAX_RANK, "max rank exceeded");
    if (! omit(k, r, b, p))
      { dg_Node *ch[2];
        if (split(k, r, b, p))
          { dg_Node *pch[2];  /* Enclosing nodes of children */
            int i;
            /* Node is not a leaf: */
            dg_Axis ax = dg_split_axis(d, r); /* Splitting axis. */
            /* Split Bézier patch: */
            bz_Patch bzch[2], *bch[2];
            if (b == NULL)
              { bch[0] = bch[1] = NULL; }
            else
              { bzch[0] = bz_Patch_new(b->m, b->n, b->g); bch[0] = &(bzch[0]);
                bzch[1] = bz_Patch_new(b->m, b->n, b->g); bch[1] = &(bzch[1]);
                bz_split(b, ax, 0.5, bch[0], bch[1]);
              }
            /* Generate subtrees: */
            dg_node_enclose_children(p, pch);
            for (i = 0; i < 2; i++)
              { ch[i] = dg_make_grid(d, 2*k + i, r+1, bch[i], pch[i], omit, split);
                if (b != NULL) { bz_Patch_free(bzch[i]); }
              }
            /* If both subtrees are empty, omit cell too: */
            if ((ch[BLO] != NULL) || (ch[BHI] != NULL))
              { n = dg_Node_new(NULL, k);
                affirm ((ch[BLO] != NULL) && (ch[BHI] != NULL), "lame tree");
                for (i = 0; i < 2; i++)
                  { n->ch[i] = ch[i];
                    if (ch[i] != NULL) 
                      { n->nodes += ch[i]->nodes;
                        ch[i]->pa = n;
                      }
                  }
              } 
          }
        else
          { /* Node is a leaf: */
            n = dg_Node_new(NULL, k);
          }
      }
    fprintf(stderr, "- dg_make_grid  cell = %lld  rank = %d\n", k, r); 
    return n;
  }