=begin
#-------------------------------------------------------------------------------------------------------------------------------------------------
#*************************************************************************************************
# Copyright 2009 - Designed September 2009 by Fredo6

# Permission to use this software for any purpose and without fee is hereby granted
# Distribution of this software for commercial purpose is subject to:
#  - the expressed, written consent of the author
#  - the inclusion of the present copyright notice in all copies.

# THIS SOFTWARE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR
# IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
#-----------------------------------------------------------------------------
# Name			:   CurviloftAlgo.rb
# Original Date	:   25 Sep 2009 - version 1.0
# Description	:   Main Algorithm for Curviloft Loft
#-------------------------------------------------------------------------------------------------------------------------------------------------
#*************************************************************************************************
=end

module F6_Curviloft

T6[:LOFT_TIP_EditValid_Slide] = "SLIDE"
T6[:LOFT_TIP_EditValid_Opposite] = "OPPOSITE"
T6[:LOFT_TIP_EditValid_Remove] = "REMOVE (double-click)"
	
T6[:LOFT_ACTION_BrotherAdd] = "Add a forced Pair"
T6[:LOFT_ACTION_BrotherRemove] = "Remove a forced Pair"
T6[:LOFT_ACTION_AutoTwinRemove] = "Remove an Auto-Pair"
T6[:LOFT_ACTION_BrotherMakeAs] = "Make as a forced Pair"
T6[:LOFT_ACTION_AutoRemoveBut] = "Remove all auto pairs but this one"

T6[:LOFT_MNU_EditionUndo] = "Undo change [%1]"
T6[:LOFT_MNU_EditionRedo] = "Redo last action [%1]"
T6[:LOFT_MNU_EditionReset] = "Cancel all changes"
T6[:LOFT_MNU_EditionRestore] = "Restore all changes"

T6[:MSG_Edition_ClickCurVertex] = "Click on vertex to edit it"
T6[:MSG_Edition_SeeContextual] = "See Contextual menu for more options"
T6[:MSG_Edition_ActivateLink] = "Click to activate section"
T6[:MSG_Edition_SelectVertex] = "Select a vertex for edition"

T6[:LOFT_COLOR_Red] = "Red"
T6[:LOFT_COLOR_Blue] = "Blue"

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# CVL_LoftAlgo: Computation class and methods for managing Visual Loft constructions
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
					
class CVL_LoftAlgo 

#----------------------------------------------------------------------------
#  Data structures used by the Algorithm
#----------------------------------------------------------------------------

#Describe a contour
CVL__LOFT_Plate6 = Struct.new :pts, :loop, :plane, :quasi_plane, :vecnormal, :normal, :vecdir, :bary, :punctual,
                              :links, :vecrail

#Describe the relation and generated shape between two contours
CVL__LOFT_Link6 = Struct.new :plates, :normals, :pairs, :tr_morphs, :axes, :trigo, :brothers, :nodes, :twins, 
                            :tot_len, :ztot_len, :biloop, :rails_native, :rails, :contours, :hiborders, 
							:native_nodes, :all_nodes, :rails_tot_len, :rails_sample_index, :rails_raw,
                            :lbz_pts, :lbz_pts_s, :lbz_type, :lschunks, :auto_twins, :hard_twins, :computed,
							:lquads, :llines, :ltriangles, :box2d, :lquads2d, :llinesd, 
							:ldiagsq1, :ldiagsq2, :ldiagsq1d, :ldiagsq2d, :lst_diagos,
							:tr_axes, :pts_proj, :pts_morph, :lverts, :inv_twins, :lbz_inter, :lbz_inter_d,
							:lbz_pairs, :hprop, :binodes1, :binodes2, :history, :ihistory, 
							:no_edition, :flat, :quad_corners, :key_corners, :istart_corner,
							:igroup, :tr_preview_2d, :tr_preview_3d, :tr_preview_2d_s,
							:instruction_base_2d, :instruction_base_3d, :instruction_pair_2d, :instruction_pair_3d,
							:twist_angle, :angles_min, :tr_boxs, :tr_scales, :tr_basic, :hbase_auto_twins, 
							:eff_twins, :eff_twins_hard, :eff_twins_auto, :eff_twins_forced,
							:hbase_auto_twins_nat, :duplicated, :prepared,
							:hbase_auto_twins_any, :hbase_auto_twins_any_nat,
							:twist_dangles, :twist_rangles, :twist_nbmax, :twist_nb,
				            :borders, :borders_s, :borders_len,
							:lhsh_lex, :lhsh_lex_nat, :lhsh_tr_twist, :lhsh_tr_twist_nat, :angle_offset,
							:rail_param, :draw_junction, :draw_inter, :draw_quads

#Describe a vertex of the contour
CVL__LOFT_Node6 = Struct.new :iplate, :plate, :pt, :iseg, :tdist, :zdist, :type, :native, :pt_proj, :pt_morph, :same,
                             :acute_angle, :signature

#Describe a vertex pair of the contour
CVL__LOFT_Knot6 = Struct.new :pt, :dist, :type, :knot_prev, :knot_next, :node

#Describe a matching vertex of the contour
CVL__LOFT_Vertex6 = Struct.new :link, :iplate, :node, :pt, :pt2, :pt_2d, :pt2_2d, :ibz, 
                               :lthick_node, :lthick, :skip, :type, :square2d, :square3d
												  
#Describe a portion of the matching between the two contours
CVL__LOFT_Chunk6 = Struct.new :link, :ibeg1, :iend1, :ibeg2, :iend2

#Extrenal attributes
attr_reader :color_plates, :tcolor_plates, :color_plates_light

#----------------------------------------------------------------------------
#  Initialization
#----------------------------------------------------------------------------

def initialize(*args)
	#Parsing the arguments
	args.each { |arg| arg.each { |key, value|  parse_args(key, value) } if arg.class == Hash }

	#Initializing texts and colors
	init_text
	init_color
	
	#initializing global properties
	init_hprop
	
	#Initialization	
	@model = Sketchup.active_model
	@view = @model.active_view
	@tr_id = Geom::Transformation.new
	
	reset_all
	
	@plane_vec = Z_AXIS
	@dside = 300
	@node_proximity = 0.01
	@pt_trace = []
	
	@match_natural = 0
	@match_bezier = 1
	@match_cubic = 2
	@match_same = 3
	
	@angle_twist = 0
	
	@stickiness = 6
	@precision_edit = 50
	@ip = Sketchup::InputPoint.new
	@ph = @view.pick_helper	
			
	#Creating the normalized square box
	@ubox = []
	@ubox.push Geom::Point3d.new(0, 0, 0)
	@ubox.push Geom::Point3d.new(@dside, 0, 0)
	@ubox.push Geom::Point3d.new(@dside, @dside, 0)
	@ubox.push Geom::Point3d.new(0, @dside, 0)
	@ubox_ptmid = Geom.linear_combination 0.5, @ubox[0], 0.5, @ubox[2]
	@ubox_trcenter = Geom::Transformation.translation ORIGIN.vector_to(@ubox_ptmid)
	
end
	
#initialize the current environment	
def reset_all
	@lst_links = []
	@lst_contours = nil
	@hsh_plates = []

	#Initialization for edition	
	@active_link = nil
	@edit_link = false
	@current_vertex = nil
	
	@hsh_interdictions = {}
end
	
#Parse the arguments of the initialize method
def parse_args(key, value)
	skey = key.to_s
	case skey
	when /method/i
		@method = value
	when /palman/i
		@palman = value
	when /proc_please_wait/i
		@proc_please_wait = value
	when /proc_get_vertex/i
		@proc_get_vertex = value
	end	
end	

#Initialize all texts used by the tool
def init_text
	@tip_valid_slide = T6[:LOFT_TIP_EditValid_Slide]
	@tip_valid_opposite = T6[:LOFT_TIP_EditValid_Opposite]
	@tip_valid_remove = T6[:LOFT_TIP_EditValid_Remove]
	
	@hsh_actions = {}
	@hsh_actions[:brother_add] = [T6[:LOFT_ACTION_BrotherAdd]]
	@hsh_actions[:brother_remove] = [T6[:LOFT_ACTION_BrotherRemove]]
	@hsh_actions[:auto_twin_remove] = [T6[:LOFT_ACTION_AutoTwinRemove]]
	@hsh_actions[:brother_make_as] = [T6[:LOFT_ACTION_BrotherMakeAs]]
	@hsh_actions[:auto_remove_but] = [T6[:LOFT_ACTION_AutoRemoveBut]]
	
	@tip_edition_undo = Traductor.encode_tip T6[:LOFT_MNU_EditionUndo], [:escape, :arrow_left]
	@mnu_edition_undo = Traductor.encode_menu @tip_edition_undo
	@tip_edition_redo = Traductor.encode_tip T6[:LOFT_MNU_EditionRedo], [:arrow_right]
	@mnu_edition_redo = Traductor.encode_menu @tip_edition_redo
	@tip_edition_reset = Traductor.encode_tip T6[:LOFT_MNU_EditionReset], [:arrow_down]
	@mnu_edition_reset = Traductor.encode_menu @tip_edition_reset
	@tip_edition_restore = Traductor.encode_tip T6[:LOFT_MNU_EditionRestore], [:arrow_up]
	@mnu_edition_restore = Traductor.encode_menu @tip_edition_restore
	
	@msg_edition_click_cur_vertex = T6[:MSG_Edition_ClickCurVertex]
	@msg_edition_see_contextual = T6[:MSG_Edition_SeeContextual]
	@msg_edition_activate_link = T6[:MSG_Edition_ActivateLink]
	@msg_edition_select_vertex = T6[:MSG_Edition_SelectVertex]
end

#initialize all colors used by the Interactive Edition
def init_color
	@color_line_interpol = Sketchup::Color.new 120, 120, 0
	@color_plates = ['red', 'Dodgerblue']
	@color_plates_light = ['pink', 'lightblue']
	@tcolor_plates = [T6[:LOFT_COLOR_Red], T6[:LOFT_COLOR_Blue]]

	@color_current_vertex = 'orange'
	@color_opposite_vertex = 'red'
	@color_twin_hard = 'magenta'
	@color_twin_hard_3d = 'magenta'
	@color_twin_auto = 'lightgreen'
	@color_twin_auto_3d = 'green'
	@color_twin_forced = 'lightcoral'
	@color_twin_forced_3d = 'lightcoral'
	@color_twin_none = 'gray'
	@color_line_active = 'yellow'
	@color_line_active_3d = 'yellow'
	@color_line_passive = SU_MAJOR_VERSION >= 7 ? 'gainsboro' : 'gray'
	@color_line_interpol = SU_MAJOR_VERSION >= 7 ? 'gold' : 'goldenrod'
end	

#----------------------------------------------------------------------------
#  Prop Management
#----------------------------------------------------------------------------

#Initialize parameters and properties
def init_hprop
	@hprop = {}
	
	#Common parameters
	@hprop[:option_simplify]= true
	@hprop[:factor_simplify]= 0.05
	@hprop[:option_interpolate]= false
	@hprop[:factor_interpolate] = 5
	@hprop[:option_sample]= false
	@hprop[:factor_sample] = 5
	@hprop[:type_match] = :same
	@hprop[:option_match_best] = true
	@hprop[:param_geometry] = ''
	@hprop[:preview_mode] = 3
	
	#Bezier
	if @method == :splineloft
		@hprop[:spline_method] = :cubic
		@hprop[:num_bz] = 5
		@hprop[:num_bz_global] = 15
		@hprop[:num_bz_ortho] = 10
		@hprop[:flag_tension] = true
		@hprop[:tension1] = 0.2
		@hprop[:tension2] = 0.2
		@hprop[:tension] = 0.2
		@hprop[:option_global_loop] = false
		
	#Lof Along
	elsif @method == :along_path
		@hprop[:along_method] = :stretch
		@hprop[:offset_normal] = nil

	elsif @method == :sweep
		@hprop[:along_method] = :sweep
		@hprop[:offset_normal] = nil
		
	#Skinning
	elsif @method == :skinning
	
	end
	
end

#Return a parameter, either at level of active link or for the whole model
def hprop_get(symb_prop, link=nil)
	link = @active_link if link == true
	if link 
		val = link.hprop[symb_prop]
		return val unless val == nil
	end	
	@hprop[symb_prop]
end

def hprop_set(symb_prop, val, link=nil)
	link = @active_link if link == true
	return hprop_reset_to_default(symb_prop, link) if val == nil
	(link) ? (link.hprop[symb_prop] = val) : (@hprop[symb_prop] = val)
	
	if @lst_links.length == 1
		(link) ? @hprop[symb_prop] = val : @lst_links[0].hprop[symb_prop] = val			
	end
end

def hprop_toggle(symb_prop, link=nil)
	link = @active_link if link == true
	(link) ? (link.hprop[symb_prop] = !hprop_get(symb_prop, true)) : (@hprop[symb_prop] = !@hprop[symb_prop])
	if @lst_links.length == 1
		(link) ? @hprop[symb_prop] = link.hprop[symb_prop] : @lst_links[0].hprop[symb_prop] = @hprop[symb_prop]			
	end
end

#Check if the property is defined locally to the link
def hprop_local?(symb_prop, link)
	return false if @lst_links.length == 1
	link = @active_link if link == true
	(link && link.hprop[symb_prop] != nil)
end

#Reset th elink property to the global default
def hprop_reset_to_default(symb_prop, link)
	link = nil if @lst_links.length == 1
	link = @active_link if link == true
	if link
		link.hprop[symb_prop] = nil
	else
		@lst_links.each { |link| link.hprop[symb_prop] = nil }
	end	
end

#----------------------------------------------------------------------------
#  Top level methods
#----------------------------------------------------------------------------

def check_contours(lst_contours, manual_selection=false)
	return false if lst_contours.length == 0
	@lst_contours = lst_contours
	
	begin
		status = generic_check_contours lst_contours, manual_selection
	rescue StandardError => e
		puts "exception = #{e}"
		e.backtrace.each { |a| puts "#{a}" }
		#UI.messagebox "Error Rescue"
	end	
	
	return status
end


def proceed
	@proc_please_wait.call
	prepare_all
end

#Calcule and recalculate the complete configuration
def prepare_all
	#Computing and constructing the links
	link_prepare_all
	link_calculate_all
end

#Calcule and recalculate the complete configuration
def link_prepare_all(current=nil)
	if current && @active_link
		link_prepare @active_link
	else
		@lst_links.each { |link| link_prepare link }
	end	
end

#Calcule and recalculate the complete configuration
def link_calculate_all(current=nil)
	return unless @lst_links && @lst_links.length > 0
	@proc_please_wait.call
	@state_recalculate = false
	current = nil if generic_switch_links()
	
	#Options enabled or disabled
	compute_interdictions

	if current && @active_link
		link_calculate @active_link
	else
		@lst_links.each { |link| link_calculate link }
	end
	link_construct_all	
end

#Construct the lines between plates
def link_construct_all(current=nil)
	#Calculating the configuration of links	
	@state_reconstruct = false
	
	if current && @active_link
		junction_construct @active_link
	else
		@lst_links.each { |link| junction_construct link }
	end	
	@proc_please_wait.call true
end

#Method to be called when the view is changed (event Resume)
def refresh_when_view_changed
	return unless @lst_contours
	@refresh_timer = UI.start_timer(0) { refreshing_links } unless @refresh_timer
end

def refreshing_links
	@lst_links.each do |link|
		link_compute_2D_footprint link
	end	
	@refresh_timer = nil
	@view.invalidate
end

#Roll back
def roll_back
	if @top_group
		@top_group.erase!
		@top_group = nil
	end	
end

#Call back to be called when tool is deactivated
def deactivate
	zoom_terminate
	return unless @suops
	if @top_group && @top_group.valid? && @top_group.hidden?
		@suops.abort_operation
	else
		@suops.commit_operation
	end	
end

#----------------------------------------------------------------------------
# Generic Communication with method modules
#----------------------------------------------------------------------------

#Check contours and build all links and plates
def generic_check_contours(lst_contours, manual_selection=false)
	case @method
	when :along_path, :sweep
		along_check_contours lst_contours, manual_selection
	when :skinning
		skinning_check_contours lst_contours, manual_selection
	else
		spline_check_contours lst_contours, manual_selection
	end	
end

#Return the reordered list of contours (for rollback)
def generic_actual_order(lst_contours)
	return nil if lst_contours.length == 0
	
	lorder = nil
	case @method
	when :splineloft
		lorder = spline_get_order
	when :along_path
		lorder = spline_get_order
	end	
	
	return lorder
end

#Check if the change of parameters imposes to change the links
def generic_switch_links
	case @method
	when :splineloft
		spline_verify_master?
	when :along_path
		along_switch_links
	else
		false
	end	
end

#Construct the preview model
def generic_junction_construct(link)
	#Computing the curve
	case @method
	when :skinning
		skinning_junction_construct link
	when :along_path, :sweep
		along_junction_construct link
	else	
		spline_junction_construct link
	end
end

#----------------------------------------------------------------------------
#  Management of Options and Properties
#----------------------------------------------------------------------------

#Callback method to reset the properties from the palette (when long click)
def option_reset_prop(scope, prop)
	option_set_prop scope, prop, nil, true
end

#Callback method to set the properties from the palette
def option_set_prop(scope, prop, *args)
	val = args[0]
	link = (scope != 0) ? true : nil

	if args[1]
		hprop_reset_to_default prop, link
	elsif prop.to_s =~ /\Aflag/i || prop.to_s =~ /\Aoption/i
		hprop_toggle prop, link
	else	
		hprop_set prop, val, link
	end
	
	#Reconstruction or full recalculation only
	case prop.to_s
	when /\Aparam_/, /\Apreview/
	
	when /\Anum_/
		link_construct_all link
	else
		link_calculate_all link
	end	
end

#Callback method to get the value of properties from the palette
def option_get_prop(scope, prop, local=false)
	return hprop_local?(prop, true) if local
	val = nil
	link = (scope != 0) ? true : nil
	hprop_get prop, link
end

#Compute the options allowed or not with current state
def compute_interdictions
	hsh = @hsh_interdictions
	hsh[:tension] = (@method != :splineloft) || (hprop_get(:spline_method).to_s !~ /bezier/)
	hsh[:master] = @single_link
	hsh[:loop] = @single_link
end

def check_interdictions(prop)
	@hsh_interdictions[prop]
end

def no_vertex_matching?(current=nil)
	(current && @active_link) ? @active_link.duplicated : @all_duplicated
end

#----------------------------------------------------------------------------
#  Plate Management
#----------------------------------------------------------------------------
	
#Create a plate from a given curve	
def plate_create(pts)
	#initialization
	plate = CVL__LOFT_Plate6.new
	plate_reset(plate, pts)
	plate
end

def plate_reset(plate, pts)
	#initialization
	plate.links = []
	plate.normal = nil
	plate.vecnormal = nil
	plate.bary = nil
	plate.quasi_plane = 0
	
	#List of vertices
	if pts.first == pts.last && pts.length > 1
		plate.loop = true
		plate.pts = pts[0..-2]
	else
		plate.loop = false
		plate.pts = pts.clone
	end	
		
	#Computing the configuration	
	plate_compute_plane plate
	
	plate
end

#Compute the average plane for a plate
def plate_compute_plane(plate)
	pts = plate.pts
	pts = pts + [pts.first] if plate.loop && pts.length > 2
	
	#Degraded curve - linear
	if pts.length == 1
		plate.bary = pts[0]
		plate.plane = plate.vecnormal = nil
		plate.punctual = true

	#Degraded curve - linear
	elsif pts.length < 3 || G6.curl_is_aligned?(pts)
		plate.bary = G6.curve_barycenter pts
		plate.plane = plate.vecnormal = nil

	#Curve in 3D
	else
		plane = Geom.fit_plane_to_points pts
		bary = G6.curve_barycenter pts
		plate.quasi_plane, = G6.curve_quasi_plane pts, plane, bary, 0.1
		vec = Geom::Vector3d.new plane[0], plane[1], plane[2]
		plate.bary = bary.project_to_plane plane
		plate.plane = plane
		plate.vecnormal = vec
	end	
end


#Compute the Tangent Direction to the plate, based on other plates	
def plate_vecdir(plate)
	link1 = plate.links[0]
	link2 = plate.links[1]
	
	vec1 = nil
	if link1
		plate1 = link1.plates[0]
		vec1 = plate1.bary.vector_to plate.bary
	end

	vec2 = nil
	if link2
		plate2 = link2.plates[1]
		vec2 = plate.bary.vector_to plate2.bary
	end

	if vec1 && vec2
		plate.vecdir = Geom.linear_combination 0.5, vec1, 0.5, vec2
	elsif vec1
		plate.vecdir = vec1
	else
		plate.vecdir = vec2
	end		
end

#----------------------------------------------------------------------------
#  Node Management
#----------------------------------------------------------------------------

#Create a node
def node_create(link, iplate, pt, type=:native, signature=nil)
	node = CVL__LOFT_Node6.new
	node.iplate = iplate
	node.plate = link.plates[iplate]
	node.pt = pt
	pt = pt.project_to_plane node.plate.plane
	node.pt_morph = link.tr_morphs[iplate] * pt if link.tr_morphs
	node.tdist = 0
	node.zdist = 0
	node.iseg = 0
	node.acute_angle = Math::PI
	node.type = type
	node.signature = [] unless node.signature
	node.signature.push signature if signature
	node
end

#Create a node
def node_insert(link, iplate, pt, type, signature=nil)
	nodes = link.all_nodes[iplate]
	
	#Node already exist
	node_found = nodes.find { |node| node.pt == pt }
	if node_found
		node_found.signature.push signature if signature
		return node_found
	end	
	
	#Looking for where to insert the node
	dtot = link.tot_len[iplate]
	nodes += [nodes.first] if link.plates[iplate].loop
	for i in 0..nodes.length-2
		n1 = nodes[i]
		pt1 = n1.pt
		n2 = nodes[i+1]
		pt2 = n2.pt
		if pt.on_line?([pt1, pt2]) && pt.vector_to(pt1) % pt.vector_to(pt2) <= 0
			node_found = nil
			if pt.distance(pt1) < @node_proximity * dtot
				node_found = n1
			elsif pt.distance(pt2) < @node_proximity * dtot
				node_found = n2
			end	
			if node_found
				node_found.signature.push signature if signature
				return node_found
			end	
			node_found = node_create link, iplate, pt, type, signature
			link.all_nodes[iplate][i+1, 0] = node_found
			return node_found
		end
	end
	nil
end

#----------------------------------------------------------------------------
#  Link Management
#----------------------------------------------------------------------------

#Create a plate from a given curve	
def link_create(*plates)
	link = CVL__LOFT_Link6.new
	link_reset link
	
	#Associating the plates to the link, if valid
	link.plates = plates
	link_associate_plates link, plates
	
	@lst_links.push link	
	link
end

#Reset the variables for the link
def link_reset(link)
	#initiliazing the structure
	link.computed = false
	link.hprop = {}
	link.nodes = []
	link.native_nodes = []
	link.all_nodes = []
	link.twins = []
	link.brothers = []
	link.inv_twins = []
	link.history = []
	link.ihistory = 0
	link.rails = []
	link.rails_native = []
	link.rails_tot_len = []
	link.no_edition = false
	link.hprop[:nb_twisting1] = 0
	link.hprop[:nb_twisting2] = 0
	
	link.lhsh_lex = [{}, {}]
	link.lhsh_lex_nat = [{}, {}]
	link.lhsh_tr_twist = [{}, {}]
	link.lhsh_tr_twist_nat = [{}, {}]
	
	link.hbase_auto_twins = {}
	link.hbase_auto_twins_nat = {}
	link.hbase_auto_twins_any = {}
	link.hbase_auto_twins_any_nat = {}
end

#Associate Plates to a link
def link_associate_plates(link, plates)
	return unless plates && plates.length > 1
	
	#Computing the plane
	plates[0].links[1] = plates[1].links[0] = link
	vec = plates[0].bary.vector_to(plates[1].bary)
	link.plates.each do |plate| 
		if plate.vecnormal == nil
			unless vec.valid?
				vecl = plate.pts[0].vector_to(plate.pts[-1])
				vec = (vecl.valid?) ? vecl.axes[0] : Z_AXIS
			end
			plate.vecnormal = vec
			if plate.punctual
				plate.plane = [plate.pts[0], Z_AXIS]
			else	
				plate.plane = [plate.bary, plate.pts[0].vector_to(plate.bary) * vec]
			end	
		end	
	end		
	
	#Computing the overall direction between plates
	vecnormal = nil
	link.plates.each do |plate| 
		next if plate.normal
		vecnormal = plate.vecnormal
		if @method == :along_path || @method == :sweep
			vec = plate.vecrail
		end	
		plate.normal = (vecnormal % vec < 0) ? vecnormal.reverse : vecnormal
	end	
end

#Top routine to prepare a link (done once)
def link_prepare(link)
	morph_prepare_link link
	link.prepared = true
end

#Create the vertex nodes for a link
def link_create_nodes(link)
	[0, 1].each do |iplate|
		pts = link.plates[iplate].pts
		link.nodes[iplate] = pts.collect { |pt| node_create link, iplate, pt, :native }
		link_order_nodes link, iplate
	end
	link.all_nodes = [link.nodes[0].clone, link.nodes[1].clone]
	link.native_nodes = [link.nodes[0].clone, link.nodes[1].clone]
	link.biloop = link.plates[0].loop || link.plates[1].loop
end

#Top routine to calculate or recalculate a link
def link_calculate(link)
	#Preparing the link if not done
	link_prepare link unless link.prepared
	
	#Filtering auto twins
	if link.duplicated
		link.auto_twins = []
	else
		link_arrange_auto_twins link
	end	
	
	#Ordering the nodes
	link_build_current_nodes link
	[0, 1].each { |iplate| link_order_nodes link, iplate }
	
	#Matching twins to compute pairs
	link_compute_pairs link
end	

#Arrange the auto Twins
def link_arrange_auto_twins(link)
	@signature = nil
	twins = morph_compute_auto_twin(link)
	link.auto_twins = morph_compute_auto_twin(link).clone
	link.inv_twins.each do |lpt|
		link.auto_twins.delete_if { |twin| twin[0].pt == lpt[0] && twin[1].pt == lpt[1] }
	end
end

def link_build_current_nodes(link)
	key_twisting, lnb_twisting = morph_get_twisting_info link
	best = hprop_get :option_match_best, link
	signature = morph_signature link, key_twisting, best
	
	[0, 1].each do |iplate|
		link.nodes[iplate] = link.all_nodes[iplate].find_all do |node|
			node.type != :transient || node.signature.include?(signature)
		end	
	end	
end

def node_in_auto_twin?(link, node)
	link.auto_twins.find { |twin| twin[0] == node || twin[1] == node }
end

#Computing the order index and cumulated distance of the nodes
def link_order_nodes(link, iplate)
	#initialization
	link.tot_len = [] unless link.tot_len
	link.ztot_len = [] unless link.ztot_len
	loop = link.plates[iplate].loop

	#Natural order and distance
	nodes = link.nodes[iplate]
	nodes[0].iseg = 0
	nodes[0].tdist = 0
	nodes[0].zdist = 0
	ptnodes = nodes.collect { |node| node.pt }
	n = nodes.length - 1
	
	#Calculating the standard distance
	tdist = 0
	for i in 1..n
		tdist += ptnodes[i-1].distance ptnodes[i]
		nodes[i].iseg = i
		nodes[i].tdist = tdist
		nodes[i].zdist = tdist
	end
	tdist += ptnodes[-1].distance ptnodes[0] if loop
	link.tot_len[iplate] = link.ztot_len[iplate] = tdist
	
	#Spline distance	
	type_match = hprop_get :type_match, link
	
	if type_match == :bezier || type_match == :cubic
		ptnodes += [ptnodes[0]] if loop
		m = ptnodes.length - 1
		ubz = (type_match == :cubic) ? G6::UniformBSpline.compute(ptnodes, m, 3) : G6::BezierCurve.compute(ptnodes, m)
		zdist = 0
		for i in 1..n
			zdist += ubz[i-1].distance ubz[i]
			nodes[i].zdist = zdist
		end	
		zdist += ubz[-2].distance ubz[0] if loop
		link.ztot_len[iplate] = zdist
	end	
	
	#Calculating the acute angles
	for i in 1..n-1
		nodes[i].acute_angle = nodes[i].pt.vector_to(nodes[i-1].pt).angle_between nodes[i].pt.vector_to(nodes[i+1].pt)
	end	
end

#Compute an extended node list for a plate contour. It is easier to manipulate through the algorithm
def link_compute_binodes(link, iplate)	
	#Both curves are not loops
	plate = link.plates[iplate]
	loop = plate.loop
	biloop = link.biloop
	nodes = link.nodes[iplate]
	return nodes unless loop || biloop
	
	#Doubling the nodes, and calculating cumulative distance for appended ones	
	tdist0 = link.tot_len[iplate]
	zdist0 = link.ztot_len[iplate]
	
	#Plate is in true loop
	if loop
		base_nodes = nodes + [nodes[0]]
		
		supp_nodes = base_nodes.collect do |node| 
			nd = node.clone
			nd.same = node
			nd.tdist += tdist0
			nd.zdist += zdist0
			nd
		end	
		supp_nodes[-1].tdist = 2 * tdist0
		supp_nodes[-1].zdist = 2 * zdist0
		
	#Plate contour is open - we fold it on itself	
	else
		n = nodes.length - 1
		supp_nodes = []
		for i in 0..n-1
			k = n - 1 - i
			node = nodes[k]
			nd = node.clone
			nd.same = node
			nd.tdist = tdist0 + tdist0 - node.tdist
			nd.zdist = zdist0 + zdist0 - node.zdist
			supp_nodes.push nd
		end	
	end
	
	nodes + supp_nodes
end

#Add a brother or twin to the link
def link_add_brother(link, brother)
	chunk_add_brother link, link.lschunks, brother
end

#Build all matching sequences
def link_compute_pairs(link)
	#Preparing the binodes lists
	biloop = link.plates[0].loop || link.plates[1].loop
	link.binodes1 = link_compute_binodes link, 0
	link.binodes2 = link_compute_binodes link, 1
	
	#Constructing the chunkls from each brother and auto-twin
	link.eff_twins = []
	link.twins = link.hard_twins + link.brothers + link.auto_twins
	link.lschunks = []
	lpairs = []
	if link.twins.length > 0
		link.twins.each { |twin| link_add_brother(link, twin) }
	else
		link_add_brother link, [link.binodes1[0], link.binodes2[0], :twin_type_none]
	end	
	
	#Creating the pairs from each chunks
	type_match = hprop_get :type_match, link
	same = (type_match == :same) || link.duplicated
	link.lschunks.each do |chunk|
		lpairs += chunk_match_sequences chunk, same
	end
	
	#Deduplicating the pairs
	lpairs = link_deduplicate_pairs link, lpairs
	
	#Filtering the nodes
	link.binodes1 = nil
	
	#Simplifying the pairs
	if hprop_get(:option_simplify, link)
		lpairs = link_simplify_pairs link, lpairs
		lpairs = link_rebalance_pairs link, lpairs
	end

	#Interpolating the pairs
	if hprop_get(:option_interpolate, link)
		lpairs = link_interpolate_pairs link, lpairs
	end
		
	#Storing the list of pairs
	link.pairs = lpairs
	
	#Recompute distance
	link_recompute_distances link
end

def link_filter_auto_pairs(link, lpairs)
	lpairs_new = []
	del_nodes1 = []
	del_nodes2 = []
	lpairs.each do |pair|
		node1 = pair[0].node
		node2 = pair[1].node
		if node1 && node2 == nil && node1.type == :transient
			del_nodes1.push node1
		elsif node2 && node1 == nil && node2.type == :transient
			del_nodes2.push node2
		else
			lpairs_new.push pair
		end	
	end
	
	if del_nodes1.length > 0
		del_nodes1.each { |node| link.nodes[0].delete node }
		link_order_nodes link, 0
	end
	if del_nodes2.length > 0
		del_nodes2.each { |node| link.nodes[1].delete node }
		link_order_nodes link, 1
	end
	
	lpairs_new
end

#Deduplicate the pairs
def link_deduplicate_pairs(link, lpairs)
	pt1 = lpairs.last[0].pt
	pt2 = lpairs.last[1].pt
	pair_prev = lpairs.last
	lpairs_final = []
	lpairs.each do |pair|
		if pair[0].pt == pt1 && pair[1].pt == pt2
			pair_prev[0].type = pair[0].type if pair[0].type
			pair_prev[1].type = pair[1].type if pair[1].type
		else
			lpairs_final.push pair
		end	
		pt1 = pair[0].pt
		pt2 = pair[1].pt
		pair_prev = pair
	end	
	lpairs_final
end

#Simplify the pairs by grouping them at nodes
def link_simplify_pairs(link, lpairs)
	#initialization
	factor = hprop_get(:factor_simplify, link)
	ratio1 = 1.0 / link.tot_len[0]
	ratio2 = 1.0 / link.tot_len[1]
	
	#Scanning the pairs to check which one should be merged
	lmerge = []
	lp = lpairs + ((link.biloop) ? [lpairs.first] : [])
	n = lp.length - 1
	for i in 1..n
		pair_prev = lp[i-1]
		pair = lp[i]
		d1 = pair[0].pt.distance(pair_prev[0].pt) * ratio1
		d2 = pair[1].pt.distance(pair_prev[1].pt) * ratio2
		
		if d1 <= factor && d2 <= factor
			if pair[0].type && !pair[1].type && pair_prev[1].type && !pair_prev[0].type
			   lmerge.push [i, i-1, d1, d2]
			elsif !pair[0].type && pair[1].type && !pair_prev[1].type && pair_prev[0].type
			   lmerge.push [i-1, i, d1, d2]
			 end
		end
	end

	#Filtering the merges
	lmerge.sort! { |a, b| (a[2] + a[3]) <=> (b[2] + b[3]) }
	
	hexclude = {}
	htreated = {}
	lmerge.each do |lm|
		i1 = lm[0]
		i2 = lm[1]
		pair1 = lp[i1]
		pair2 = lp[i2]
		next if htreated[i1] || htreated[i2]
		d1 = lm[2]
		d2 = lm[3]
		if d1 < d2
			pair1[1].type = :node
			pair1[1].pt = pair2[1].pt
			pair1[1].dist = pair2[1].dist
			hexclude[i2] = true
		else
			pair2[0].type = :node
			pair2[0].pt = pair1[0].pt
			pair2[0].dist = pair1[0].dist
			hexclude[i1] = true
		end
		htreated[i1] = htreated[i2] = true
	end
	
	#Executing the merge
	lpairs_final = []
	for i in 0..lpairs.length-1
		lpairs_final.push lpairs[i] unless hexclude[i]
	end	
	
	lpairs_final
end

#Rebalance the internediate pairs by grouping them at nodes
def link_rebalance_pairs(link, lpairs)
	lp = lpairs + ((link.biloop) ? [lpairs.first] : [])
	n = lp.length - 2
	for i in 1..n
		pair_prev = lp[i-1]
		pair_next = lp[i+1]
		pair = lp[i]
		if pair[0].type && pair[1].type == nil
			d1 = pair_next[0].pt.distance(pair[0].pt) + pair_prev[0].pt.distance(pair[0].pt)
			d = pair[0].pt.distance(pair_prev[0].pt)
			ratio = d / d1
			pair[1].pt = Geom.linear_combination 1.0 - ratio, pair_prev[1].pt, ratio, pair_next[1].pt
		
		elsif pair[0].type == nil && pair[1].type
			d2 = pair_next[1].pt.distance(pair[1].pt) + pair_prev[1].pt.distance(pair[1].pt)
			d = pair[1].pt.distance(pair_prev[1].pt)
			ratio = d / d2
			pair[0].pt = Geom.linear_combination 1.0 - ratio, pair_prev[0].pt, ratio, pair_next[0].pt		
		end
	end
	lpairs
end


#Interpolate between pairs
def link_interpolate_pairs(link, lpairs)
	#initialization
	finter = hprop_get(:factor_interpolate, link)
	return lpairs if finter < 1
	factor = 2 * finter
	biloop = link.biloop
	ratio1 = (link.tot_len[0] > 0) ? 1.0 / link.tot_len[0] : 1.0
	ratio2 = (link.tot_len[1] > 0) ? 1.0 / link.tot_len[1] : 1.0
	
	#Scanning the pairs to check which one should be interpolated
	lpairs_final = [lpairs[0]]
	lp = lpairs + ((biloop) ? [lpairs.first] : [])
	len = lp.length - 1
	for i in 1..len
		pair_prev = lp[i-1]
		pair = lp[i]
		d1 = pair[0].pt.distance(pair_prev[0].pt)
		d2 = pair[1].pt.distance(pair_prev[1].pt)
		
		n1 = (d1 * ratio1 * factor).round
		n2 = (d2 * ratio2 * factor).round
		n = [n1, n2].max
		
		unless n > 0
			lpairs_final.push pair
			next
		end	
		
		d01 = pair[0].dist - pair_prev[0].dist
		d02 = pair[1].dist - pair_prev[1].dist
		rd1 = (d1 == 0) ? 0 : d01 / d1
		rd2 = (d2 == 0) ? 0 : d02 / d2
		
		step = 1.0 / (n + 1)
		for j in 1..n
			f = j * step
			pt1 = Geom.linear_combination 1-f, pair_prev[0].pt, f, pair[0].pt
			pt2 = Geom.linear_combination 1-f, pair_prev[1].pt, f, pair[1].pt
			zd1 = pair_prev[0].dist + rd1 * pair_prev[0].pt.distance(pt1)
			zd2 = pair_prev[1].dist + rd2 * pair_prev[1].pt.distance(pt2)
			lpairs_final.push pair_create(pt1, zd1, :interpol, pt2, zd2, :interpol)
		end	
		lpairs_final.push pair unless biloop && i == len

	end
	
	lpairs_final
end

#Recalibrate the distance for links
def link_recompute_distances(link)
	pairs = link.pairs
	return if pairs.length == 0
	d1 = d2 = 0
	pairs[0][0].dist = pairs[0][1].dist = 0
	for i in 1..pairs.length-1
		pair = pairs[i]
		pairprev = pairs[i-1]
		d1 += pair[0].pt.distance(pairprev[0].pt)
		d2 += pair[1].pt.distance(pairprev[1].pt)
		pair[0].dist = d1
		pair[1].dist = d2
	end
end

#Compute the Quads and Triangles to build the shape
def link_compute_polygons(link)
	lquads = []
	ltriangles = []
	llines = []
	ldiagsq1 = []
	ldiagsq2 = []
	lpts = link.lbz_pts
	ltype = link.lbz_type
	if link.biloop
		ltype += [ltype.first]
		lpts += [lpts.first]
	end	
	n = lpts.length - 1
	
	#Computing the quads and triangles
	for i in 1..n
		lpt1 = lpts[i-1]
		lpt2 = lpts[i]
		skip1 = ltype[i-1]
		skip2 = ltype[i]	
		m = lpt1.length - 1
		for j in 1.. m
			ltriangles.push lpt1[j-1], lpt2[j-1], lpt1[j] unless lpt1[j-1] == lpt1[j]
			ltriangles.push lpt1[j], lpt2[j], lpt2[j-1] unless lpt1[j] == lpt2[j-1]
			quad = [lpt1[j-1], lpt2[j-1], lpt2[j], lpt1[j]]
			lquads.push quad
			ldiagsq1.push quad[0], quad[2]
			ldiagsq2.push quad[1], quad[3]
			llines.push lpt1[j-1], lpt2[j-1]
			llines.push lpt1[j], lpt1[j-1] unless skip1
			llines.push lpt2[j-1], lpt2[j] unless skip2
		end	
	end
	
	#Transfering the values
	link.lquads = lquads
	link.llines = llines
	link.ltriangles = ltriangles
	link.ldiagsq1 = ldiagsq1
	link.ldiagsq2 = ldiagsq2
	
	#Borders
	link.borders = []
	link.borders_len = []
	[0, 1].each do |iplate|
		ip = -iplate
		borders = lpts.collect { |bz| bz[ip] }
		d = 0
		for i in 1..borders.length-1
			d += borders[i-1].distance borders[i]
		end	
		link.borders[iplate] = borders
		link.borders_len[iplate] = d
	end
	
	#Computing the vertices
	link_compute_vertices link
	
	#Computing the 2D footprint
	link_compute_2D_footprint link
end

def link_compute_quads(link)
	lquads = []
	lpts = link.lbz_pts	
	lpts = lpts + [lpts.first] if link.biloop
	n = lpts.length - 1
	
	#Computing the quads and triangles
	for i in 1..n
		lpt1 = lpts[i-1]
		lpt2 = lpts[i]
		m = lpt1.length - 1
		for j in 1.. m
			quad = [lpt1[j-1], lpt2[j-1], lpt2[j], lpt1[j]]
			lquads.push [lpt1[j-1], lpt2[j-1], lpt2[j], lpt1[j]]
		end	
	end
	link.lquads = lquads
end

#Compute the Edition vertices for a link
def link_compute_vertices(link)
	lverts = []
	nodes1 = link.all_nodes[0]
	nodes2 = link.all_nodes[1]
	link.lbz_pts.each_with_index do |lpt, ibz|
		node1 = nodes1.find { |node| node.pt == lpt[0] }
		node2 = nodes2.find { |node| node.pt == lpt[-1] }
		skip = !(node1 || node2) || link.lbz_type[ibz] == :link_type_interpol
		lverts.push vertex_create(link, 0, node1, lpt[0], lpt[1], ibz, skip)
		lverts.push vertex_create(link, 1, node2, lpt[-1], lpt[-2], ibz, skip)
	end
	
	link.quad_corners = [nodes1[0].pt, nodes2[0].pt, nodes1[-1].pt, nodes2[-1].pt]
	
	link.lverts = lverts	
end

#Create a vertex
def vertex_create(link, iplate, node, pt, pt2, ibz, skip)
	vert = CVL__LOFT_Vertex6.new
	vert.link = link
	vert.iplate = iplate
	vert.node = node
	vert.pt = pt
	vert.pt2 = pt2
	vert.ibz = ibz
	vert.skip = skip
	vert.type = link.lbz_type[ibz]
	vert
end

#Compute the 2D footprint (refreshed when view changed)
def link_compute_2D_footprint(link, refresh=false)
	t0 = Time.now.to_f
	
	#Bounding box 2d and Quads 2d
	t4 = Time.now.to_f
	lquads2d = link.lquads.collect { |quad| quad.collect { |pt| coords_2d pt } }
	box2d = Geom::BoundingBox.new
	link.lbz_pts.each { |lpt| box2d.add lpt.collect { |pt| coords_2d pt } }
	link.lquads2d = lquads2d
	link.box2d = box2d	
	@t4 += Time.now.to_f - t4 if @t4
	
	#Computing the vertices in 2D
	t1 = Time.now.to_f
	link_refresh_2d link
	@t1 += Time.now.to_f - t1 if @t1
	
	t2 = Time.now.to_f
	link.llinesd = link.llines.collect { |pt| G6.small_offset @view, pt } unless refresh
	@t2 += Time.now.to_f - t2 if @t2
	
	#Computing the interpolated lines in 2D
	lb = []
	link.lbz_inter.each do |lpt|
		lb.push lpt.collect { |pt| G6.small_offset @view, pt } if lpt && lpt.length > 1
	end
	link.lbz_inter_d = lb
	
	#Resetting quads lines
	link.ldiagsq1d = nil
	link.ldiagsq2d = nil
	
	#Resetting the Preview mode
	link.instruction_base_2d = nil
	link.instruction_pair_2d = nil
	link.instruction_base_3d = nil
	link.instruction_pair_3d = nil
	@t0 += Time.now.to_f - t0 if @t1
end

def link_refresh_2d(link)
	link.lverts.each do |vert| 
		unless vert.skip
			if vert.node
				vert.lthick_node = thick_at_vertex(vert.pt, vert.pt2)
			else
				vert.lthick = thick_at_vertex(vert.pt, vert.pt2)
			end	
		end	
		vert.pt_2d = coords_2d vert.pt
		vert.pt2_2d = coords_2d vert.pt2
	end	
end

def preview_zone_hidden?
	!@edit_link #|| hprop_get(:preview_mode) == 0
end

#Identify if the curve is a twin
def link_qualify_as_twin?(link, bzpts)
	link.twins.each do |twin|
		pt1 = twin[0].pt
		pt2 = twin[1].pt
		if bzpts[0] == pt1 && bzpts[-1] == pt2 
			link.lbz_pairs.push [bzpts, twin[2], twin]
			return twin[2]
		end	
	end
	
	false
end

#Calculate the effective twins
def link_effective_twins(link)
	link.eff_twins = []
	link.eff_twins_hard = []
	link.eff_twins_auto = []
	link.eff_twins_forced = []
	
	link.lbz_pairs.each do |lp|
		twin = lp[2]
		case lp[1]
		when :twin_type_auto
			link.eff_twins_auto.push twin
		when :twin_type_forced
			link.eff_twins_forced.push twin
		when :twin_type_hard
			link.eff_twins_hard.push twin
		end
		link.eff_twins.push twin
	end	
end

#----------------------------------------------------------------------------
# Calculation of Junction curves
#----------------------------------------------------------------------------

def junction_construct(link)
	return unless link.pairs

	#Computing the curve
	lbz_pts = generic_junction_construct link
	
	#Qualifying the junctions
	junction_qualify link, lbz_pts
	
	#Computing the polygons and Quads
	link_compute_polygons link	
	
	#Link is computed
	link.instruction_pair_3d = nil

	link.computed = true
end

#Construct a flat junction
def junction_construct_flat(link)

end

#Qualify the junction curves
def junction_qualify(link, lbz_pts)
	link.lbz_type = []
	link.lbz_pts = []
	link.lbz_pairs = []
	link.lbz_inter = []
	link.pairs.each_with_index do |pair, i|
		bz = lbz_pts[i]
		if pair[0].type == :interpol || pair[1].type == :interpol
			link.lbz_type.push :link_type_interpol
			link.lbz_inter.push lbz_pts[i]
		else	
			a = link_qualify_as_twin?(link, bz)
			link.lbz_type.push a
		end	
		link.lbz_pts.push bz
	end
	
	link_effective_twins link
end


#----------------------------------------------------------------------------
# Utilities for Link Management
#----------------------------------------------------------------------------

def thick_at_vertex(pt, pt2)
	vec = pt.vector_to pt2
	return nil unless vec.valid?
	size = @view.pixels_to_model 8, pt
	pt1 = pt
	pt2 = pt.offset vec, size
	[G6.small_offset(@view, pt1), G6.small_offset(@view, pt2)]
end

#Compute screen_coordinates, making sure Z is set to 0
def coords_2d(pt)
	pt2d = @view.screen_coords pt
	puts "Coord pt #{pt} = nil" if pt2d == nil
	pt2d.z = 0
	pt2d
end

#----------------------------------------------------------------------------
# Knot Management
#----------------------------------------------------------------------------

#Create a structure for a point in a pair
def knot_create(pt, d, type, node=nil)
	knot = CVL__LOFT_Knot6.new
	knot.pt = pt
	knot.dist = d
	knot.type = type
	knot.node = node
	knot
end

#Create the pair from 2 knots specifications
def pair_create(pt1, d1, type1, pt2, d2, type2, node1=nil, node2=nil)
	[knot_create(pt1, d1, type1, node1), knot_create(pt2, d2, type2, node2)]
end

#----------------------------------------------------------------------------
# Chunk Management
#----------------------------------------------------------------------------

#Create a chunk data structure
def chunk_create(link, ibeg1, iend1, ibeg2, iend2)
	chunk = CVL__LOFT_Chunk6.new
	chunk.link = link
	chunk.ibeg1 = ibeg1
	chunk.iend1 = iend1
	chunk.ibeg2 = ibeg2
	chunk.iend2 = iend2
	chunk
end

#Add a brother to a chunk
def chunk_add_brother(link, lschunk, brother)
	if lschunk.length == 0
		lschunk[0, 0] = chunk_first_add(link, brother)
		return true
	end

	notouch = (brother[2] == :twin_type_auto || brother[2] == :twin_type_hard)
	n = lschunk.length - 1
	for i in 0..n
		lchk = chunk_fit_node link, lschunk[i], brother, notouch
		if lchk
			lschunk[i, 1] = lchk
			return true
		end
	end	
	false
end

#Insert the very first brother in the list of chunks
def chunk_first_add(link, brother)
	binodes1 = link.binodes1
	binodes2 = link.binodes2
	b1 = brother[0]
	b2 = brother[1]
	
	#Finding the middle and end position
	n1 = binodes1.length - 1
	iseg1 = brother[0].iseg
	imid1 = (0..n1).to_a.find { |i| binodes1[i].iseg == iseg1 }
	iend1 = (imid1 == n1) ? imid1 : (imid1+1..n1).to_a.find { |i| binodes1[i].iseg == iseg1 }

	n2 = binodes2.length - 1
	iseg2 = brother[1].iseg
	imid2 = (0..n2).to_a.find { |i| binodes2[i].iseg == iseg2 }
	iend2 = (imid2 == n2) ? imid2 : (imid2+1..n2).to_a.find { |i| binodes2[i].iseg == iseg2 }
	
	#when loops, there is only one chunk
	return [chunk_create(link, imid1, iend1, imid2, iend2)] if iend1 && iend2

	#Adding the front chunk
	iend1 = n1 unless iend1
	iend2 = n2 unless iend2

	chunkA = (imid1 != 0 || imid2 != 0) ? chunk_create(link, 0, imid1, 0, imid2) : nil
	chunkB = (imid1 != n1 || imid2 != n2) ? chunk_create(link, imid1, n1, imid2, n2) : nil
	
	return [chunkA] unless chunkB
	return [chunkB] unless chunkA
	[chunkA, chunkB]
end

#Check if a given brother would fit in the chunk
def chunk_fit_node(link, chunk, brother, notouch=false)
	binodes1 = link.binodes1
	binodes2 = link.binodes2

	iseg1 = brother[0].iseg
	imid1 = (chunk.ibeg1..chunk.iend1).to_a.find { |i| binodes1[i].iseg == iseg1 }
	return nil unless imid1
	iseg2 = brother[1].iseg
	imid2 = (chunk.ibeg2..chunk.iend2).to_a.find { |i| binodes2[i].iseg == iseg2 }
	return nil unless imid2
	
	if notouch && (imid1 == chunk.ibeg1 || imid2 == chunk.ibeg2 || imid1 == chunk.iend1 || imid2 == chunk.iend2)
		return nil
	elsif (imid1 == chunk.ibeg1 && imid2 == chunk.ibeg2) || (imid1 == chunk.iend1 && imid2 == chunk.iend2)
		return nil
	end
	
	len1 = link.nodes[0].length
	len2 = link.nodes[1].length
	if chunk.ibeg1 == imid1 && chunk.iend2.modulo(len2) <= chunk.ibeg2.modulo(len2)
		chunkA = chunk_create link, chunk.ibeg1, imid1, imid2, chunk.iend2
		chunkB = chunk_create link, imid1, chunk.iend1, chunk.ibeg2, imid2
	elsif chunk.ibeg2 == imid2 && chunk.iend1.modulo(len1) <= chunk.ibeg1.modulo(len1)
		chunkA = chunk_create link, chunk.ibeg1, imid1, chunk.ibeg2, imid2
		chunkB = chunk_create link, imid1, chunk.iend1, imid2, chunk.iend2
	else
		chunkA = chunk_create link, chunk.ibeg1, imid1, chunk.ibeg2, imid2
		chunkB = chunk_create link, imid1, chunk.iend1, imid2, chunk.iend2
	end	
	[chunkA, chunkB]
end

#Match the sequences for a link
def chunk_match_sequences(chunk, same)
	#Computing the sequences
	pairs = []
	link = chunk.link
	seq1 = (chunk.ibeg1..chunk.iend1).to_a.collect { |i| link.binodes1[i] }
	seq2 = (chunk.ibeg2..chunk.iend2).to_a.collect { |i| link.binodes2[i] }
	
	dbeg1 = seq1.first.zdist
	dbeg2 = seq2.first.zdist
	dtot1 = seq1.last.zdist - dbeg1
	dtot2 = seq2.last.zdist - dbeg2
	
	#Special case when section is reduced to a single node
	if dtot1 == 0.0
		node1 = seq1.first
		ptsingle = node1.pt
		pairs = seq2.collect { |node| pair_create ptsingle, seq1.first.zdist, :node, node.pt, node.zdist, :node, node1, node }
		return pairs
	elsif dtot2 == 0.0
		node2 = seq2.first
		ptsingle = node2.pt
		pairs = seq1.collect { |node| pair_create node.pt, node.zdist, :node, ptsingle, seq2.first.zdist, :node, node, node2 }	
		return pairs
	end

	#Matching same pais
	if same
		n1 = chunk.iend1 - chunk.ibeg1
		n2 = chunk.iend2 - chunk.ibeg2
		if n1 == n2
			for i in 0..n1
				node1 = seq1[i]
				node2 = seq2[i]
				pairs.push pair_create(node1.pt, node1.zdist, :node, node2.pt, node2.zdist, :node, node1, node2)
			end
			return pairs
		end
	end
	
	#Sequence 1 with Sequence 2
	ibeg = 0
	ratio = dtot2 / dtot1
	n = seq1.length - 1
	for i in 0..n
		node = seq1[i]
		d = node.zdist - dbeg1
		dr = d * ratio
		pt, ibeg, type = chunk_sequence_interpolate seq2, ibeg, dbeg2, dr
		pairs.push pair_create(node.pt, node.zdist, :node, pt, dr + dbeg2, type, node, type)
	end

	#Sequence 2 with Sequence 1
	ibeg = 0
	ratio = dtot1 / dtot2
	n = seq2.length - 1
	for i in 0..n
		node = seq2[i]
		d = node.zdist - dbeg2
		dr = d * ratio
		pt, ibeg, type = chunk_sequence_interpolate seq1, ibeg, dbeg1, dr
		pairs.push pair_create(pt, dbeg1 + dr, type, node.pt, node.zdist, :node, type, node)
	end

	#Sorting the pairs
	pairs.sort! { |a, b| a[0].dist <=> b[0].dist }
	
	pairs	
end


#Interpolate within a  sequence at a given distance ratio
def chunk_sequence_interpolate(seq, ibeg, dbeg, dist)
	n = seq.length - 1
	for i in ibeg..n
		node = seq[i]
		d = node.zdist - dbeg
		if d > dist 
			ratio = (dist - seq[i-1].zdist + dbeg) / (seq[i].zdist - seq[i-1].zdist)
			pt1 = seq[i-1].pt
			return [pt1, i, :node] if ratio == 0
			pt = Geom.linear_combination 1- ratio, pt1, ratio, seq[i].pt
			return [pt, i]
		end
	end
	[seq[n].pt, n]
end

end	#End Class CVL_LoftAlgo

end	#End Module F6_Curviloft

