#! /usr/bin/python3
# Last edited on 2024-09-18 21:43:06 by stolfi
 
from math import sin, cos, tan, sqrt, pi, inf, floor, sqrt
import rn
import sys
import re

from slicing_lib import make_edge, make_face, check_repeated_edge, prte, prtf

def triangulate(Ni, Vind, Vlst, Elst, Flst, prec, verbose):
  # See the main program and {make_vertices} for the description of the object.
  #
  # Subdivides the faces of the original mesh of the object Into
  # triangles. Assumes that the vertices are given by the structured
  # table {Vind} and flat list {Vlst}, the edges are given by the flat
  # list {Elst},and the faces are given by the flat list {Flst}. The
  # lists {Vlst,Elst,Flst} are indexed from 1; element 0 is not used.
  #
  # Returns new flat lists {Ftri} and {Etri} of faces and edges
  # of the triangulation.  No new vertices are created. The
  # original edges are preserved with their original indices,
  # and the new diagonal edges are appended after them, with {etype=1}.
  # The faces are replaced by the triangles.
  #
  # Original faces "fi.{ks}{kz}.{ki}" (indentation), "fc.{ks}{kr}"
  # (chamfer), and "fh.{ks}{kz}" (bottom/top horizontal corner) are
  # split into two triangles, with the same label plus ".{kt}" appended
  # where {kt} is either 0 or 1. Each plaza "fp.{ks}{kr}" is split into
  # {4*Ni} triangles, with labels "fp.{ks}{kr}.{ki}.{kt}" where {ki} is
  # in {0..2*Ni-1} and {kt} is 0 or 1.
  # 
  # The diagonal added to a quadrangular face will have the same label
  # as the face, with "d" instead of "f". The diagonals of plazas will
  # have labels "dp.{ks}{kr}.{ki}.{kd}" where {ki} ranges in {0..2*Ni}
  # and {kd} is 0 for vertical, 1 for oblique (except that {ki} goes
  # only up to {2*Ni-1} for vertical edges).

  Nv = len(Vlst)-1     # Total vertex count (input and output).
  Ne_in = len(Elst)-1  # Total input edge count.
  Nf_in = len(Flst)-1  # Total input faces.
  
  # Output element counts PER WALL:
  Nv_w = 2*2*(2*Ni+1)        # Indentation vertices, inner/outer, lower/upper.

  Nd_w_i = 2*(2*Ni)          # Added diagonals in indentation faces, upper/lower.
  Nd_w_h = 2                 # Added diagonals in horizontal corner faces, upper/lower.
  Nd_w_c = 2                 # Added diagonals in chamfer faces, inner/outer.
  Nd_w_p = 2*(2*Ni-1 + 2*Ni) # Added diagonals in plaza faces, inner/outer, vertical/oblique
  
  Nf_w_i = 2*(2*2*Ni)        # Triangles from indentation faces, upper/lower.
  Nf_w_h = 2*2               # Triangles from horizontal corner faces, upper/lower.
  Nf_w_c = 2*2               # Triangles from chamfer faces, inner/outer.
  Nf_w_p = 2*(2*2*Ni)        # Triangles from plaza faces, inner/outer
  
  assert Nv == 4*Nv_w, "{Ni,Vlst} inconsistent"
  Ne_ot = Ne_in + 4*(Nd_w_i + Nd_w_h + Nd_w_c + Nd_w_p)  # Expected total output edge count.
  Nf_ot = 4*(Nf_w_i + Nf_w_h + Nf_w_c + Nf_w_p)          # Expected total output face (triangle) count.

  Etri = Elst.copy() + [None]*(Ne_ot-Ne_in)
  Ftri = [None]*(Nf_ot+1)
  
  Eset = set()  # Set of edges as pairs, to check for repetitions.
  for je in range(1,Ne_in+1): 
    e = Elst[je]
    Eset.add((e[0],e[1]))
  
  ne = Ne_in # Number of edges created so far.
  nf = 0     # Number of faces created so far.
 
  def Svdi(kv_org, kv_dst, elab):
    # Adds the diagonal edge from {Vlst[kv_org]} to {Vlst[kv_dst]} to {Etri},
    # reoriented in increasing index sense.
    nonlocal ne, nf
    if kv_org > kv_dst: kv_org, kv_dst = kv_dst, kv_org
    etype = 1
    e = make_edge(Vlst[kv_org], Vlst[kv_dst], ne+1, etype, elab, prec)
    assert e != None
    if verbose: prte(e, prec)
    ne += 1
    Etri[ne] = e
    check_repeated_edge(ne, Etri, Eset, prec)
    return None
    
  def Tri(kva,kvb,kvc,flab):
    # Adds to {Etri} the triangle with vertices {Vlst[kva],Vlst[kvb],Vlst[kvc]}
    # assumed to be CCW seen from outside.
    nonlocal ne, nf
    nf += 1
    t = make_face((kva,kvb,kvc), nf, flab, Vlst, prec)
    if verbose: prtf(t, Vlst, prec)
    Ftri[nf] = t

  for f in Flst[1:]:
    Nx,Ny,Nz,Fiv,kf,flab = f;
    if verbose: 
      sys.stderr.write("\n")
      sys.stderr.write("  IN: ")
      prtf(f, Vlst, prec)
      sys.stderr.write("\n")
    
    ks = int(flab[3]); assert ks >= 0 and ks < 4
    if flab[0:2] == "fi":
      # Indentation face.
      kz = int(flab[4]); assert kz == 0 or kz == 1
      ki = int(flab[6:]); assert ki >= 0 and ki < 2*Ni
      # Half the diagonals go one way, half the other way:
      assert len(Fiv) == 4;
      kk = 0 if ki < Ni else 1
      if (ks + kz + kk) % 2 == 0:
        Tri(Fiv[0],Fiv[1],Fiv[2],flab + ".0")
        Tri(Fiv[2],Fiv[3],Fiv[0],flab + ".1")
        Svdi(Fiv[0],Fiv[2],"d" + flab[1:])
      else:
        Tri(Fiv[0],Fiv[1],Fiv[3],flab + ".0")
        Tri(Fiv[1],Fiv[2],Fiv[3],flab + ".1")
        Svdi(Fiv[1],Fiv[3],"d" + flab[1:])
    elif flab[0:2] == "fc":
      # Chamfer face:
      kr = int(flab[4]); assert kr == 0 or kr == 1
      assert len(Fiv) == 4;
      if (ks + kr) % 2 == 0:
        Tri(Fiv[0],Fiv[1],Fiv[2],flab + ".0")
        Tri(Fiv[2],Fiv[3],Fiv[0],flab + ".1")
        Svdi(Fiv[0],Fiv[2],"d" + flab[1:])
      else:
        Tri(Fiv[0],Fiv[1],Fiv[3],flab + ".0")
        Tri(Fiv[1],Fiv[2],Fiv[3],flab + ".1")
        Svdi(Fiv[1],Fiv[3],"d" + flab[1:])
    elif flab[0:2] == "fh":
      # Horizontal corner face:
      kz = int(flab[4]); assert kz == 0 or kz == 1
      assert len(Fiv) == 4;
      if (ks + kz) % 2 == 0:
        Tri(Fiv[0],Fiv[1],Fiv[2],flab + ".0")
        Tri(Fiv[2],Fiv[3],Fiv[0],flab + ".1")
        Svdi(Fiv[0],Fiv[2],"d" + flab[1:])
      else:
        Tri(Fiv[0],Fiv[1],Fiv[3],flab + ".0")
        Tri(Fiv[1],Fiv[2],Fiv[3],flab + ".1")
        Svdi(Fiv[1],Fiv[3],"d" + flab[1:])
    elif flab[0:2] == "fp":
      # Plaza face:
      kr = int(flab[4]); assert kr == 0 or kr == 1
      assert len(Fiv) == 2*(2*Ni+1);
      # Assume that the vertices are lower chain then upper chain.
      for jv in range(2*Ni):
        if verbose: sys.stderr.write("\n")
        iv = len(Fiv) - 1 - jv;
        kv0 = Fiv[jv]
        kv1 = Fiv[jv+1]
        kv2 = Fiv[iv-1]
        kv3 = Fiv[iv]
        if jv < 2*Ni-1:
          assert (jv+1) + 1 < (iv-1)
          Svdi(kv1,kv2,"d" + flab[1:] + f".{jv}.0")
        dlab = "d" + flab[1:] + f".{jv}.1"
        kk = 0 if jv < Ni else 1
        if (kk + ks) % 2 == 0:
          Tri(kv0,kv1,kv2,flab + f".{jv}.0")
          Tri(kv2,kv3,kv0,flab + f".{jv}.1")
          Svdi(kv0,kv2,dlab)
        else:
          Tri(kv0,kv1,kv3,flab + f".{jv}.0")
          Tri(kv1,kv2,kv3,flab + f".{jv}.1")
          Svdi(kv1,kv3,dlab)
    else:
      assert False, f"invalid face label '{flab}'"

  sys.stderr.write("generated %d faces (expected %d)\n" % (nf, Nf_ot))
  if nf < Nf_ot: sys.stderr.write("!! missing some faces\n")
  assert nf <= Nf_ot

  sys.stderr.write("generated %d edges (expected %d)\n" % (ne, Ne_ot))
  if ne < Ne_ot: sys.stderr.write("!! missing some edges\n")
  assert ne <= Ne_ot

  return Etri, Ftri