/* See {salamic_closer_trivial.h} */
/* Last edited on 2015-11-16 01:25:54 by stolfilocal */

#define _GNU_SOURCE
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>

#include <bool.h>
#include <vec.h>
#include <jsfile.h>
#include <affirm.h>

#include <stmesh.h>

#include <salamic_closer.h>

#include <salamic_closer_trivial.h>

void salamic_closer_trivial_get_path
  ( stmesh_t mesh, 
    int32_t pZ, 
    uint32_t mf,
    stmesh_face_t f[],
    bool_t used[],
    uint32_t kf, 
    uint32_t *mepP,
    stmesh_edge_t ep[],
    uint32_t mep_max, 
    salamic_stats_t *st
  );
  /* Extracts a closed loop or maximal open path from a cross-section of
    the mesh {mesh} with a slicing plane at quantized {Z}-coordinate
    {pZ}.
    
    Expects that the {f[0..mf-1]} are the triangles of the mesh that
    intercept the slicing plane, and {used[0..mf-1]} are boolean flags
    that tell which of those faces have been used in previous loops or
    paths.
    
    The extracted path will include the segment defined by the face
    {f[kf]}, that should be unused. The path is extended in both
    directions from that segment, with zero or more unused faces of {f},
    until it closes or reaches an open edge of the mesh. The procedure
    sets {used[k]} for each face {f[k]} that it included in the
    path.
    
    The path (or loop) is returned as a list {ep[0..mep-1]} of mesh edges
    in {mesh.e}. The intersection of each edge with the slicing plane is
    a vertex of the path. The path is a closed loop if and only if {ep[0]
    == ep[mep-1]}. The value of {mep} is returned in {*mepP}, whose previous
    value is ignored. The procedure assumes that {ep} was allocated 
    with {mep_max} elements. */

void salamic_closer_trivial_extend_path
  ( stmesh_t mesh, 
    int32_t pZ, 
    uint32_t mf,
    stmesh_face_t f[],
    bool_t used[], 
    uint32_t *mepP,
    stmesh_edge_t ep[],
    uint32_t mep_max
  );
  /* Extends a path from a cross-section of the mesh {mesh} with a
    slicing plane at quantized {Z}-coordinate {pZ}, until it closes or
    reaches an open edge.
    
    Assumes that the path's vertices obtained so far are the
    intersections of the slicing plane with the edges {ep[0..mep-1]} where
    {mep = (*mepP)}. The path must have at least two vertices. Expects
    that the unused elements in {f[0..mf-1]} are the triangles of the
    mesh that intercept the slicing plane, and have not been used in
    previous loops or paths.
    
    The path is extended forwards, appending edges and incrementing {mep},
    until it closes or reaches an open
    edge of the mesh. If it closes, it will return with {ep[0] ==
    ep[mep-1]}. Assumes {ep} was allocated with {mep_max} elements. The
    procedure marks each face {f[k]} that it adds to the path by setting
    {used[k]} true. */
    

void salamic_closer_trivial_close
  ( stmesh_t mesh,
    int32_t pZ,
    uint32_t mf,
    stmesh_face_t f[], 
    uint32_t *ncP, 
    uint32_t estart[],
    stmesh_edge_t e[],
    salamic_stats_t *st
  )
  {
    bool_t *used = notnull(malloc(mf*sizeof(bool_t)), "no mem"); /* Marks used faces. */
    uint32_t jf; /* Next segment that may be the start of a new path/loop. */
    for(jf = 0; jf < mf; jf++) { used[jf] = FALSE; }
    
    /* Each edge of an {f} triangle that crosses the slicing plane
      defines a vertex of the cross-section. Allocate a vector {e}
      big enough to hold all edge indices that correspond to vertices of
      a single path or loop of the cross-section: */

    uint32_t me_max = 2*mf; /* Assumes that {e} was allocated with {me_max} elements. */
    uint32_t kf = 0; /* Next segment that may be the start of a new path/loop is {f[kf]}. */
    uint32_t nc = 0; /* Number of loops/paths found. */
    uint32_t ini = 0;       /* Start of next path in {e} array. */
    estart[0] = ini;
    while (TRUE) 
      { /* Look for the first unused segment: */
        while ((kf < mf) && used[kf]) { kf++; }
        if (kf >= mf) { break; }
        /* Collect another loop/path that includes this segment, mark used faces: */
        uint32_t mep;
        uint32_t mep_max = me_max - ini;
        stmesh_edge_t *ep = &(e[ini]);
        salamic_closer_trivial_get_path(mesh, pZ, mf, f, used, kf, &mep, ep, mep_max, st);
        /* Got one more loop, prepare for the next one: */
        nc++;
        ini = ini + mep;
        estart[nc] = ini;
      }
    free(used);
    
    (*ncP) = nc;
  }

void salamic_closer_trivial_get_path
  ( stmesh_t mesh, 
    int32_t pZ, 
    uint32_t mf,
    stmesh_face_t f[],
    bool_t used[],
    uint32_t kf, 
    uint32_t *mepP,
    stmesh_edge_t ep[], 
    uint32_t mep_max,
    salamic_stats_t *st
  )
  {
    bool_t verbose = FALSE;
    bool_t debug = FALSE;
    
    uint32_t mep = 0;
    
    /* Get the starting face {f0} and mark it: */
    demand(kf < mf, "invalid start face index");
    stmesh_face_t f0 = f[kf];
    stmesh_face_unx_t uxf0 = stmesh_face_get_unx(mesh, f0);
    used[kf] = TRUE;
    
    /* Get the first two mesh edges {e[0],e[1]}: */
    assert(mep_max >= 2);
    stmesh_face_get_sliced_sides(mesh, f0, pZ, &(ep[0]));
    mep = 2;

    if (debug) 
      { stmesh_edge_unx_t uxe0 = stmesh_edge_get_unx(mesh, ep[0]);
        stmesh_edge_unx_t uxe1 = stmesh_edge_get_unx(mesh, ep[1]);
        fprintf(stderr, "starting path with face %u mesh edges %u and %u\n", uxf0, uxe0, uxe1);
      }

    /* Collect a path whose first two edges are {e[0],e[1]}: */
    salamic_closer_trivial_extend_path(mesh, pZ, mf, f, used, &mep, ep, mep_max);
    
    if (ep[0] != ep[mep-1])
      { /* Path did not close: reverse it and extend from other end: */
        if (debug) { fprintf(stderr, "  got %d vertices, not closed: reversing...\n", mep); }
        uint32_t iv, jv;
        for (iv = 0, jv = mep-1; iv < jv; iv++, jv--)
          { stmesh_edge_t t = ep[iv]; ep[iv] = ep[jv]; ep[jv] = t; }
        if (debug) { fprintf(stderr, "  extending the other end...\n"); }
        salamic_closer_trivial_extend_path(mesh, pZ, mf, f, used, &mep, ep, mep_max);
        assert(ep[0] != ep[mep-1]);
      }
      
    if (verbose) 
      { assert(mep >= 2);
        stmesh_edge_unx_t uxe0 = stmesh_edge_get_unx(mesh, ep[0]);
        stmesh_edge_unx_t uxe1 = stmesh_edge_get_unx(mesh, ep[1]);
        stmesh_edge_unx_t uxef = stmesh_edge_get_unx(mesh, ep[mep-1]);
        fprintf(stderr, "got path with %6d corners - edges %u", mep, uxe0);
        if (mep >= 3) { fprintf(stderr, " %u", uxe1); }
        fprintf(stderr, " ... %u\n", uxef);
      }

    (*mepP) = mep;
  }
    
void salamic_closer_trivial_extend_path
  ( stmesh_t mesh, 
    int32_t pZ, 
    uint32_t mf,
    stmesh_face_t f[],
    bool_t used[], 
    uint32_t *mepP,
    stmesh_edge_t ep[],
    uint32_t mep_max
  )
  { 
    uint32_t mep = (*mepP);
    
    stmesh_edge_t e_ini = ep[0];     /* First vertex of path. */
    stmesh_edge_t e_fin = ep[mep-1]; /* Current last vertex of path. */
    while(TRUE)
      { /* Find another unmarked face {f[jf]} that uses edge {e_fin}:, return other edge {e_nxt} */
        stmesh_edge_t e_nxt = NULL;  /* Next vertex of path. */ 
        uint32_t jf;
        for (jf = 0; jf < mf; jf++)
          { if (! used[jf]) 
             { stmesh_face_t fj = f[jf];
               stmesh_edge_t ej[2];
               stmesh_face_get_sliced_sides(mesh, fj, pZ, &(ej[0]));
               if (ej[0] == e_fin)
                 { e_nxt = ej[1]; break; }
               else if (ej[1] == e_fin)
                 { e_nxt = ej[0]; break; }
             }
          }

        /* Check for open edge of mesh: */
        if (e_nxt == NULL) { break; }
        
        /* Mark the face as used: */
        used[jf] = TRUE;
        
        /* Append the new {e_nxt} to the path: */
        demand (mep < mep_max, "too many vertices in loop/path");
        ep[mep] = e_nxt;
        e_fin = e_nxt;
        mep++;
        
        /* Check for closure: */
        if (e_fin == e_ini) { break; }
      }
      
    (*mepP) = mep;
  }