// Last edited on 2024-07-25 18:03:48 by stolfi #debug "!! Loading fan_convexify.inc ...\n" #macro fan_convexify(V, E, Neo,Nei, oshape, subdiv) // Decomposes all faces of the fan into convex polygons. 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 convex tiling. // 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 convex tiling edges ...\n" #if ((subdiv != 5) & (subdiv != 6)) kaboom("bad {subfirg}") #end #local Nv = dimension_size(V, 1) - 1; #local Ne = dimension_size(E, 1) - 1; #local Nf = (Neo + Nei + 2) + 2; // Inferred number of original faces. #local Nvh = int(Nv/2); // Number of vertices per plaza. #if (Nv != 2*Nvh) kaboom("{Nv} is not even") #end #if (Nvh != Neo+Nei+2) kaboom("{Neo,Nei,Nv} inconsistent") #end // Can't predict {Nd} easily... #local Nd_max = 2*(Nvh - 3); // Max number of diagonals. #local D = array[Nd_max+1]; #local D[0] = < -1, -1, -1 >; #local nd = 0; // Count of diagonals created. #if (subdiv = 5) fan_convexify_plazas_dumb(Neo,Nei,oshape, D,nd) #elseif (subdiv = 6) fan_convexify_plazas_smart(Neo,Nei,oshape, D,nd) #else kaboom("Invalid {subdiv}") #end #local Nd = nd; // Trim the array: #local D_trim = array[Nd+1] #for (kd,1,Nd) #local D_trim[kd] = D[kd]; #end D_trim #end #macro fan_convexify_plazas_dumb(Neo,Nei,oshape, D,nd) // Chooses diagonals that break the plazas into convex polygons, the dumb way. // Stores the diagonals in {D} starting at {D[nd+1]} and increments {nd}. #debug "!! Dumb convexification of the plazas ...\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) #if (oshape = 0) #if (Nei = 0) // Nothing to do. #else #if (Nei != Neo) kaboom("{Nei,Neo} inconsistent") #end // Connect each interior inner vertex to the matching outer one: #local kva = kvi_ini + 1 + km*Nvh; #local kvb = kvi_fin - 1 + km*Nvh; #local kvc = kvo_ini + 1 + km*Nvh; #local kvd = kvo_fin - 1 + km*Nvh; fan_partition_zipper(V, kva,kvb,+1, kvc,kvd,+1, D,nd) #end #elseif (oshape = 1) // Outer chain is dented. #if (Nei = 0) // Connect the inner chain vertex to every dent tip: #local kvir = kvi_ini + km*Nvh; #local kvoa = kvo_ini + 1 + km*Nvh; #local kvob = kvo_fin - 1 + km*Nvh; fan_partition_one_to_many(V, kvir, kvoa,kvob,+2, D,nd) #else // Connect every interior inner vertex to the corresp outer one: #if (Nei != Neo) kaboom("{Nei,Neo} inconsistent") #end #local kva = kvi_ini + 1 + km*Nvh; #local kvb = kvi_fin - 1 + km*Nvh; #local kvc = kvo_ini + 1 + km*Nvh; #local kvd = kvo_fin - 1 + km*Nvh; fan_partition_zipper(V, kva,kvb,+1, kvc,kvd,+1, D,nd) #end #elseif (oshape = 2) // Outer chain is concave. #if (Nei = 0) // Connect every internal outer vertex to the inner chain vertex: #local kvir = kvi_ini + km*Nvh; #local kvoa = kvo_ini + 1 + km*Nvh; #local kvob = kvo_fin - 1 + km*Nvh; fan_partition_one_to_many(V, kvir, kvoa,kvob,+1, D,nd) #else // Connect every interior inner vertex to the corresp outer one: #if (Nei != Neo) kaboom("{Nei,Neo} inconsistent") #end #local kva = kvi_ini + 1 + km*Nvh; #local kvb = kvi_fin - 1 + km*Nvh; #local kvc = kvo_ini + 1 + km*Nvh; #local kvd = kvo_fin - 1 + km*Nvh; fan_partition_zipper(V, kva,kvb,+1, kvc,kvd,+1, D,nd) #end #elseif (oshape = 3) #if (Nei = 0) // Connect the inner chain vertex to every dent tip: #local kvir = kvi_ini + km*Nvh; #local kvoa = kvo_ini + 1 + km*Nvh; #local kvob = kvo_fin - 1 + km*Nvh; fan_partition_one_to_many(V, kvir, kvoa,kvob,+2, D,nd) #else // Connect every other interior inner vertex to the corresp outer one: #if (Nei != Neo) kaboom("{Nei,Neo} inconsistent") #end #local kva = kvi_ini + 1 + km*Nvh; #local kvb = kvi_fin - 1 + km*Nvh; #local kvc = kvo_ini + 1 + km*Nvh; #local kvd = kvo_fin - 1 + km*Nvh; fan_partition_zipper(V, kva,kvb,+2, kvc,kvd,+2, D,nd) #end #else kaboom("Invalid {oshape}") #end #end #end #macro fan_convexify_plazas_smart(Neo,Nei,oshape, D,nd) // Chooses diagonals that break the plazas into convex polygons, // so as to minimize new edge-plane crossings. // Stores the diagonals in {D} starting at {D[nd+1]} and increments {nd}. #debug "!! Smart convexification of the plazas ...\n" #if (mod(Neo,2) != 0) kaboom("{Neo} is not even") #end #if (mod(Nei,2) != 0) kaboom("{Nei} is not even") #end #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]. #local kvi_mid = kvi_ini + Nei/2; // Index of middle vertex on inner chain of plaza [0]. #for (km,0,1) #if (oshape = 0) // Outer chain convex, inner chain concave. #if (Nei = 0) // Nothing to do: plazas are convex. #else // Connect first outer vertex to every interior inner vertex? #local kvor = kvo_ini + km*Nvh; #local kvia = kvi_ini + 1 + km*Nvh; #local kvib = kvi_fin - 1 + km*Nvh; fan_partition_one_to_many(V, kvor, kvia,kvib,+1, D,nd) #end #elseif (oshape = 1) // Dented outer chain. // Cut the dents off: #local kvoa = kvo_ini + 1 + km*Nvh; #local kvob = kvo_fin - 3 + km*Nvh; #local kvoc = kvo_ini + 3 + km*Nvh; #local kvod = kvo_fin - 1 + km*Nvh; fan_partition_zipper(V, kvoa,kvob,+2, kvoc,kvod,+2, D,nd) #if (Nei = 0) // Connect first outer concave vertex to single inner vertex: #local kvos = kvo_ini + 1 + km*Nvh; #local kvis = kvi_ini + km*Nvh; fan_partition_one(V, kvos,kvis, D,nd) // Connect last outer concave vertex to mid inner vertex: #local kvot = kvo_fin - 1 + km*Nvh; #local kvit = kvi_fin + km*Nvh; fan_partition_one(V, kvot,kvit, D,nd) #else // Connect second outer vertex to interior inner ones, minus last: #local kvor = kvo_ini + 1 + km*Nvh; #local kvia = kvi_ini + 1 + km*Nvh; #local kvib = kvi_fin - 2 + km*Nvh; fan_partition_one_to_many(V, kvor, kvia,kvib,+1, D,nd) // Connect last outer concave vertex to mid inner vertex: #local kvos = kvo_fin - 1 + km*Nvh; #local kvit = kvi_fin - 1 + km*Nvh; fan_partition_one(V, kvos,kvit, D,nd) #end #elseif (oshape = 2) // Concave outer chain. #if (Nei = 0) // Can't do any better than a triangulation: #local Nw = Neo-1; #for (km,0,1) #local kv0 = kvi_mid; #for (kw,0,Nw-1) #local kv1 = kvo_ini + 1 + kw; #local nd = nd + 1; #local D[nd] = < kv0 + km*Nvh, kv1 + km*Nvh, 0 >; #end #end #else // Connect interior inner vertices to matching outer vertices: #if (Nei != Neo) kaboom("{Nei,Neo} inconsistent") #end #local kva = kvi_ini + 1 + km*Nvh; #local kvb = kvi_fin - 1 + km*Nvh; #local kvc = kvo_ini + 1 + km*Nvh; #local kvd = kvo_fin - 1 + km*Nvh; fan_partition_zipper(V, kva,kvb,+1, kvc,kvd,+1, D,nd) #end #elseif (oshape = 3) // Deeply dented inner and outer chains #if (Nei = 0) // Cut the outer dents off: #local kvoa = kvo_ini + 1 + km*Nvh; #local kvob = kvo_fin - 3 + km*Nvh; #local kvoc = kvo_ini + 3 + km*Nvh; #local kvod = kvo_fin - 1 + km*Nvh; fan_partition_zipper(V, kvoa,kvob,+2, kvoc,kvod,+2, D,nd) // Connect first outer concave vertex to single inner vertex: #local kvos = kvo_ini + 1 + km*Nvh; #local kvis = kvi_ini + km*Nvh; fan_partition_one(V, kvos,kvis, D,nd) // Connect last outer concave vertex to single inner vertex: #local kvot = kvo_fin - 1 + km*Nvh; #local kvit = kvi_fin + km*Nvh; fan_partition_one(V, kvot,kvit, D,nd) #else // Connect interior inner concave vertices to matching outer vertices: #if (Nei != Neo) kaboom("{Nei,Neo} inconsistent") #end #local kva = kvi_ini + 1 + km*Nvh; #local kvb = kvi_fin - 1 + km*Nvh; #local kvc = kvo_ini + 1 + km*Nvh; #local kvd = kvo_fin - 1 + km*Nvh; fan_partition_zipper(V, kva,kvb,+2, kvc,kvd,+2, D,nd) #end #else kaboom("Invalid {oshape}") #end #end #end