// Last edited on 2024-07-25 18:03:04 by stolfi #debug "!! Loading fan_triangulate.inc ...\n" #macro fan_triangulate(V,E, Neo,Nei, oshape, subdiv) // Triangulates all faces of the fan. Parameters: // // {V} Array of vertex coordinates {V[1..Nv]}. // {E} Array of edges {E[1..Ne]}. // {Neo} Number of edges in each outer chain. // {Nei} Number of edges in each inner chain. // {oshape} Type of outer chain: 0 = convex, 1 = dented, 2 = concave. // {subdiv} Which sub-figure we are generating. // Assumes each entry {E[ke]} is a triple of integers {} // where {kv_org,kv_dst} are indices into {V}, and {ty} is a edge type code. // Entry {E[0]} is not used // Assumes that {V[1..Neo+1]} are the vertices of the outer chain of plaza [0], // then {V[Neo+2..Neo+Nei+2} are the inner chain vertices of the same, // both in incresing order of elevation; // and these are followed by the {Neo+Nei+2} vertices of of plaza [1]. // Returns an array {D[1..Nd]} with the diagonals that define the triangulafions. // Each entry {D[kd]} is a triple {}, like the entries of {E}, // where the type is 0 for now. Entry {D[0]} is not used. #debug "!! Generating triangulation edges ...\n" #if ((subdiv != 1) & (subdiv != 2)) kaboom("bad {subdiv}") #end #debug concat("!! Neo = ", str(Neo,0,0), "\n") #debug concat("!! Nei = ", str(Nei,0,0), "\n") #local Nv = dimension_size(V, 1) - 1; #debug concat("!! Nv = ", str(Nv,0,0), "\n") #local Ne = dimension_size(E, 1) - 1; #debug concat("!! Ne = ", str(Ne,0,0), "\n") // Number of vertices per plaza: #local Nvh = int(Nv/2); #debug concat("!! Nvh = ", str(Nvh,0,0), "\n") #if (Nv != 2*Nvh) kaboom("{Nv} is not even") #end #if (Nvh != Neo+Nei+2) kaboom("{Neo,Nei,Nv} inconsistent") #end #local kvo_ini = 1; // Index of first vertex on outer chain of plaza [0]. #local kvo_fin = kvo_ini + Neo; // Index of last vertex on outer chain of plaza [0]. #local kvi_ini = kvo_fin + 1; // Index of first vertex on inner chain of plaza [0]. #local kvi_fin = kvi_ini + Nei; // Index of last vertex on inner chain of plaza [0]. #local Nf = (Neo + Nei + 2) + 2; // Expected number of original faces. #local Nd_max = 2*(Nvh-3) + Nvh; // Expected number of diagonals. #local nd = 0; // Counts diagonals added so far. #debug concat("!! Nd expected = ", str(Nd_max,0,0), "\n") #local D = array[Nd_max+1]; // Diagonals found so far are {D[1..nd]}. #local D[0] = < -1, -1, -1 >; // Unused entry. #debug "!! --- triangulating walls ---\n" // Triangulate all outer strip faces: #local kvoa = kvo_ini; #local kvob = kvo_fin - 1; #local kvoc = kvo_ini + 1 + Nvh; #local kvod = kvo_fin + Nvh; fan_partition_zipper(V, kvoa,kvob,1, kvoc,kvod,1, D,nd) #if (Nei > 0) // Triangulate all inner strip faces: #local kvia = kvi_ini; #local kvib = kvi_fin - 1; #local kvic = kvi_ini + 1 + Nvh; #local kvid = kvi_fin + Nvh; fan_partition_zipper(V, kvia,kvib,1, kvic,kvid,1, D,nd) #end // Triangulate the lower spoke face: #local kv0 = kvo_ini; // Outer corner of lower spoke on plaza [0]. #local kv1 = kvi_ini + Nvh; // Opposite corner of that face, on plaza [1]. fan_partition_one(V, kv0,kv1, D,nd) // Triangulate the upper spoke face: #local kv0 = kvo_fin; // Outer corner of upper spoke on plaza [0]. #local kv1 = kvi_fin + Nvh; // Opposite corner of that face, on plaza [1]. fan_partition_one(V, kv0,kv1, D,nd) #debug concat("!! -- triangulating the plazas - nd = ", str(nd,0,0), "...\n") #if (subdiv = 1) fan_triangulate_plazas_dumb(Neo,Nei,oshape, D,nd) #elseif (subdiv = 2) fan_triangulate_plazas_smart(Neo,Nei,oshape, D,nd) #else kaboom("Bad subdiv") #end #debug concat("!! nd = ", str(nd,0,0), "\n") #local Nd = nd; #if (Nd != Nd_max) #debug concat("!! ** WARNING EXPECTED Nd = ", str(Nd_max,0,0), " **\n") kaboom("Inconsistent {Nd_max,Nd}") #local D_trim = array[Nd+1] #for (kv,0,Nd) #local D_trim[kv] = D[kv]; #end #local D = D_trim; #end // #for (kd,1,Nd) // #debug concat(" diag[", str(kd,0,0), "] = < ", str(D[kd].x,0,0), ", ", str(D[kd].y,0,0), ">\n") // #end #local Nd = nd; D #end #macro fan_triangulate_plazas_dumb(Neo,Nei,oshape, D,nd) #debug "!! [dumb triangulation]\n" #local Nvh = Neo+Nei+2; // Number of vertices per plaza. #local kvo_ini = 1; // Index of first vertex on outer chain of plaza [0]. #local kvo_fin = kvo_ini + Neo; // Index of last vertex on outer chain of plaza [0]. #local kvi_ini = kvo_fin + 1; // Index of first vertex on inner chain of plaza [0]. #local kvi_fin = kvi_ini + Nei; // Index of last vertex on inner chain of plaza [0]. #for (km,0,1) #debug concat("!! --- triangulating plaza ", str(km,0,0)) #debug concat(" vertices {", str(km*Nvh+1,0,0), "..", str(km*Nvh+Nvh,0,0), "} ---\n") #local kvom_ini = kvo_ini+km*Nvh; #local kvom_fin = kvo_fin+km*Nvh; #local kvim_ini = kvi_ini+km*Nvh; #local kvim_fin = kvi_fin+km*Nvh; fan_triangulate_one_plaza_dumb(V, kvom_ini, kvom_fin, kvim_ini, kvim_fin, D,nd) #end #end #macro fan_triangulate_one_plaza_dumb(V, kvo_ini,kvo_fin, kvi_ini,kvi_fin, D,nd) // Triangulates one of the plazas, given the vertex index ranges of the // outer and inner chains on that plaza. #if (kvi_ini = kvi_fin) // Connect middle inner vertex with all internal outer vertices: #local kvr = kvi_ini; #local kva = kvo_ini + 1; #local kvb = kvo_fin - 1; fan_partition_one_to_many(V, kvr, kva,kvb,+1, D,nd) #else #if (Nei != Neo) kaboom("{Nei,Neo} inconsistent") #end // Connect each internal inner vertex with its matching outer vertex: #local kvia = kvi_ini + 1; #local kvib = kvi_fin - 1; #local kvoc = kvo_ini + 1; #local kvod = kvo_fin - 1; fan_partition_zipper(V, kvia,kvib,+1, kvoc,kvod,+1, D,nd) // Split the quadrilaterals: #local ns_0 = int(Nei/2); // Number of quadrilaterals in first lot: #local kvia_0 = kvi_ini + 1; #local kvib_0 = kvia_0 + ns_0 - 1; #local kvoc_0 = kvo_ini; #local kvod_0 = kvoc_0 + ns_0 - 1; fan_partition_zipper(V, kvia_0,kvib_0,+1, kvoc_0,kvod_0,+1, D,nd) #local ns_1 = Nei - ns_0; // Number of quadrilaterals in second lot: #local kvia_1 = kvi_fin - 1; #local kvib_1 = kvia_1 - ns_1 + 1; #local kvoc_1 = kvo_fin; #local kvod_1 = kvoc_1 - ns_1 + 1; fan_partition_zipper(V, kvia_1,kvib_1,-1, kvoc_1,kvod_1,-1, D,nd) #end #end #macro fan_triangulate_plazas_smart(Neo,Nei,oshape, D,nd) #local Nvh = Neo+Nei+2; // Number of vertices per plaza. #local kvo_ini = 1; // Index of first vertex on outer chain of plaza [0]. #local kvo_fin = kvo_ini + Neo; // Index of last vertex on outer chain of plaza [0]. #local kvi_ini = kvo_fin + 1; // Index of first vertex on inner chain of plaza [0]. #local kvi_fin = kvi_ini + Nei; // Index of last vertex on inner chain of plaza [0]. #debug "!! [smart (balanced binary) triangulation]\n" #for (km,0,1) #debug concat("!! --- triangulating plaza ", str(km,0,0)) #debug concat(" vertices {", str(km*Nvh+1,0,0), "..", str(km*Nvh+Nvh,0,0), "} ---\n") #if (oshape = 0) // Connect outer vertices in steps of {2^k}, starting with {kvo_ini}: #local kva = kvo_ini + km*Nvh; #local kvb = kvo_fin + km*Nvh; fan_partition_binary(V, kva,kvb, D,nd) #if (Nei > 0) // Triangulate the remaining face: #local kvr = kvo_ini + km*Nvh; #local kva = kvi_ini + 1 + km*Nvh; #local kvb = kvi_fin + km*Nvh; fan_partition_one_to_many(V, kvr, kva,kvb,+1, D,nd) #end #elseif (oshape = 1) // Binary triangulation of outer dents: #local kva = kvo_ini + 1 + km*Nvh; #local kvb = kvo_fin - 1 + km*Nvh; fan_partition_binary(V, kva,kvb, D,nd) #if (Nei = 0) #local kvi_mid = kvi_ini; // Connect {kvi_mid} to {kvo_ini+1} and {kvo_fin-1}: #local kvi0 = kvi_mid + km*Nvh; #local kvo1a = kvo_ini + 1 + km*Nvh; #local kvo1b = kvo_fin - 1 + km*Nvh; fan_partition_one(V, kvi0,kvo1a, D,nd) fan_partition_one(V, kvi0,kvo1b, D,nd) #else // Triangulate the remaining face: #local kvr = kvo_ini + 1 + km*Nvh; #local kva = kvi_ini + km*Nvh; #local kvb = kvi_fin + km*Nvh; fan_partition_one_to_many(V, kvr, kva,kvb,+1, D,nd) #end #elseif (oshape = 2) // No smart solution, same as dumb one: #local kvom_ini = kvo_ini+km*Nvh; #local kvom_fin = kvo_fin+km*Nvh; #local kvim_ini = kvi_ini+km*Nvh; #local kvim_fin = kvi_fin+km*Nvh; fan_triangulate_one_plaza_dumb(V, kvom_ini, kvom_fin, kvim_ini, kvim_fin, D,nd) #elseif (oshape = 3) // Binary triangulation of outer dents: #local kva = kvo_ini + 1 + km*Nvh; #local kvb = kvo_fin - 1 + km*Nvh; fan_partition_binary(V, kva,kvb, D,nd) #if (Nei = 0) #local kvi_mid = kvi_ini; // Connect {kvi_mid} to {kvo_ini+1} and {kvo_fin-1}: #local kvi0 = kvi_mid + km*Nvh; #local kvo1a = kvo_ini + 1 + km*Nvh; #local kvo1b = kvo_fin - 1 + km*Nvh; fan_partition_one(V, kvi0,kvo1a, D,nd) fan_partition_one(V, kvi0,kvo1b, D,nd) #else // Cut off inner dents: #local ns = int(Nei/2); #if (Nei != ns*2) kaboom("{Nei} is not even") #end #for (iv,0,ns-2) #local kv0 = kvi_ini + 1 + 2*iv + km*Nvh; #local kv1 = kvi_ini + 3 + 2*iv + km*Nvh; fan_partition_one(V, kv0,kv1, D,nd) #end // Connect first nd last outer dents to inner dents: #local kvr = kvo_ini + 1 + km*Nvh; #local kvs = kvo_fin - 1 + km*Nvh; #local kva = kvi_ini + 1 + km*Nvh; #local kvb = kvi_fin - 1 + km*Nvh; fan_partition_two_to_many(V, kvr,kvs, kva,kvb,+2, D,nd) // Connect first outer dent to first inner vertex: #local kvia = kvo_ini + 1 + km*Nvh; #local kvoa = kvi_ini + km*Nvh; fan_partition_one(V, kvia,kvoa, D,nd) // Connect last outer dent to last inner vertex: #local kvib = kvo_fin - 1 + km*Nvh; #local kvob = kvi_fin + km*Nvh; fan_partition_one(V, kvib,kvob, D,nd) #end #else kabom("invalid {oshape}") #end #end #end