1823.sagews

This sheet aims at illustrating a subdivision process to draw splines. A smooth curve is generated from a set of control points, and the subdivision process is used as an efficient way to approximate and draw the curve. It consists in recursively refining the set of control points, such that the polygonal line joining them tends to the spline.

This works is concerned about the way the subdivision scheme is defined, and illustrates an automatic process to generate one using an L-System.

 

Code

The following code intends to build a subdivision scheme from an input L-System describing the different intervals, and the way they are subdivided. It works as follows:

• From the provided L-System, a set of compatible lengths is computed for all the intervals present in the L-system (this length is the distance between two knots separated by the interval in parametric space).
  
• All the pole configuration are built. A pole configuration corresponds to a sequence of intervals, whose length depends on the desired continuity of the corresponding spline curve.
• For each pole configuration, its sequence of intervals is subdivided, to derive all the new poles resulting in the subdivision of this pole.
• For each new pole derived from an old pole, its stencil with respect to the old pole is computed (i.e. the influence coefficient of the old pole position in the new pole position). This uses knot insertion theory
• For each pole configuration its mask is built by collecting the new poles it influences with the associated influence coefficient
  

Examples

We here build two examples of subdivision schemes:

• The bisecting-trisecting scheme $B \rightarrow TT, T \rightarrow BBB$

• The Fibonacci scheme $S \rightarrow L, L \rightarrow SL$

#bisecting and trisecting scheme rules
bitriRules = {'T':['B','B','B'],'B':['T','T']}
#generate subdivision mask
bitriMask = buildSubdivision(bitriRules,2)
#color of each interval for the plots
bitriColors = {'B':(0.6,0.6,1),'T':(1,0.6,0.6)}

#fibonacci scheme rules
fiboRules = {'S':['L'],'L':['S','L']}
#generate subdivision mask
fiboMask = buildSubdivision(fiboRules,2)
#color of each interval for the plots
fiboColors = {'S':(0.6,0.6,1),'L':(1,0.6,0.6)}

#random initialization of the control points
poles = generateExample(fiboRules,20,2)

#plot the initial control points
plotPoles(poles,fiboColors).show(axes=False,xmin=0,xmax=1,ymin=0,ymax=1,figsize=(3,3))

mask = fiboMask
colors = fiboColors

subdivPoles  = applySubdivision(mask,poles)
subdivPoles1 = applySubdivision(mask,subdivPoles)
subdivPoles2 = applySubdivision(mask,subdivPoles1)
subdivPoles3 = applySubdivision(mask,subdivPoles2)
subdivPoles4 = applySubdivision(mask,subdivPoles3)
subdivPoles5 = applySubdivision(mask,subdivPoles4)
subdivPoles6 = applySubdivision(mask,subdivPoles5)
graphs = [plotPoles(poles,colors)]
graphs.extend([plotPoles(p,colors) for p in [subdivPoles,subdivPoles1,subdivPoles2,subdivPoles3,subdivPoles4,subdivPoles5,subdivPoles6]])
graphics_array(graphs,2,3).show(axes=False,xmin=0,xmax=1,ymin=0,ymax=1,figsize=(12,8))
graphics_array(graphs,2,3).save(filename='phiSpline.pdf',axes=False,xmin=0,xmax=1,ymin=0,ymax=1,figsize=(12,8))

The complete subdivision mask contains all the possible pole configurations. However, after several subdivision steps, only a few configurations are usefull. These can be found as part of the strongly connected components of the directed graph derived from the subdivision mask. Here is an example with the case of the Fibonacci mask computed above. The after a few subdivision steps, the blue labelled configurations are the only ones used for the subdivided poles.

#create a string from an interval sequence
def label(config):
    return(''.join(config))

#turn the subdivision mask into a directed graph
def graphFromMask(mask):
    d = {}
    for source,ends in mask.items():
        d[label(source)] = map(lambda x: label(x[3]),ends)
    return(DiGraph(d))
    
#Creates colors to mark the strongly connected components
ccColor = (0.6,0.6,1)
noColor = (1,0.6,0.6)

def colorComponents(graph):
    c = graph.strongly_connected_components()
    colors = {noColor:[],ccColor:[]}
    for component in c:
        if len(component)==1:
            colors[noColor].extend(component)
        else:
            colors[ccColor].extend(component)
    return colors

g = graphFromMask(fiboMask)
c = colorComponents(g)
p = g.plot(vertex_colors=c)
p.show(figsize=(10,10))
p.save(filename='maskComponents.pdf',figsize=[10,10])

Interactive Application

The following is an interactive application demonstrating the computation of a subdivision scheme from an input L-System. The L-System must be given in the form of a python dictionnary as done in the above code for the bitriRules and the fiboRules variables. It is currently not possible to use the interactive application in the published version, since it requires effectively running the present code. To do so, you must either download the sheet and run it in your local sage installation, or edit your own copy of the present document, which requires creating a (free) user account on this server.

rules  continuity  points_in_example  steps  [removed] [removed] [removed] [removed]