#! /usr/bin/env python
"""
Fill is a script to fill the slices of a gcode file.

To run fill, install python 2.x on your machine, which is avaliable from http://www.python.org/download/

To use the preferences dialog you'll also need Tkinter, which probably came with the python installation.  If it did not, look for it at:
www.tcl.tk/software/tcltk/

To export a GNU Triangulated Surface file from Art of Illusion, you can use the Export GNU Triangulated Surface script at:
http://members.axion.net/~enrique/Export%20GNU%20Triangulated%20Surface.bsh

To bring it into Art of Illusion, drop it into the folder ArtOfIllusion/Scripts/Tools/.

The GNU Triangulated Surface format is supported by Mesh Viewer, and it is described at:
http://gts.sourceforge.net/reference/gts-surfaces.html#GTS-SURFACE-WRITE

To turn an STL file into filled gcode, first import the file using the STL import plugin in the import submenu of the file menu of Art of Illusion.
Then from the Scripts submenu in the Tools menu, choose Skeinforge and select the imported STL shape.  In the Fill radio button group,
choose Slice and click the 'Export Selected' checkbox.  Set the parameters and click OK.  Then type 'python fill.py' in a shell in the folder
which fill is in and when the dialog pops up, then click 'Fill', choose the file which you exported in
Export GNU Triangulated Surface and the filled file will be saved with the suffix '_fill'.

To write documentation for this program, open a shell in the fill.py directory, then type 'pydoc -w fill', then open 'fill.html' in a browser
or click on the '?' button in the dialog.  To use other functions of fill, type 'python' in a shell to run the python interpreter, then type 'import fill'
to import this program.

The computation intensive python modules will use psyco if it is available and run about twice as fast.  Psyco is described at:
http://psyco.sourceforge.net/index.html

The psyco download page is:
http://psyco.sourceforge.net/download.html

The following examples fillet the files Hollow Square.gcode & Hollow Square.gts.  The examples are run in a terminal in the folder which contains
Hollow Square.gcode, Hollow Square.gts and fill.py.  The preferences can be set in the dialog or by changing the preferences file 'fill.csv' with a text editor
or a spreadsheet program set to separate tabs.


> pydoc -w fill
wrote fill.html


> python fill.py
This brings up the dialog, after clicking 'Fill', the following is printed:
File Hollow Square.gts is being chain filled.
The filled file is saved as Hollow Square_fill.gcode


>python
Python 2.5.1 (r251:54863, Sep 22 2007, 01:43:31)
[GCC 4.2.1 (SUSE Linux)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import fill
>>> fill.main()
File Hollow Square.gts is being filled.
The filled file is saved as Hollow Square_fill.gcode
It took 3 seconds to fill the file.


>>> fill.fillChainFile()
File Hollow Square.gts is being filled.
The filled file is saved as Hollow Square_fill.gcode
It took 3 seconds to fill the file.


>>> fill.fillFile()
File Hollow Square.gcode is being filled.
The filled file is saved as Hollow Square_fill.gcode
It took 3 seconds to fill the file.


>>> fill.getFillChainGcode("
( GCode generated by May 8, 2008 slice.py )
( Extruder Initialization )
..
many lines of gcode
..
")


>>> fill.getFillGcode("
( GCode generated by May 8, 2008 slice.py )
( Extruder Initialization )
..
many lines of gcode
..
")
"""

try:
	import psyco
	psyco.full()
except:
	pass
from vec3 import Vec3
import cStringIO
import euclidean
import gcodec
import intercircle
import math
import preferences
import slice
import sys
import time
import vectorwrite


__author__ = "Enrique Perez (perez_enrique@yahoo.com)"
__date__ = "$Date: 2008/28/04 $"
__license__ = "GPL 3.0"

#bring into tower
#raft
#export
#infill first
#one direction for while, split to weave, hex fill, loop inside sparse fill or run along sparse infill
#transform, variable precision
#fillet should have just amount a choice is unneeded, stack, raft, export plugin
#custom inclined plane, inclined plane from model, screw, fillet travel as well maybe
#later maybe addAroundClosest around arounds and check for closeness to other infills
#much afterwards make congajure multistep view
#maybe bridge supports although staggered spans are probably better
#maybe update slice to add perimeter path intersection information to the large loop also
def addAroundClosest( arounds, layerExtrusionWidth, paths, removedEndpoint ):
	"Add the closest removed endpoint to the path, with minimal twisting."
	removedEndpointPoint = removedEndpoint.point
	closestDistanceSquared = 999999999999999999.0
	closestPathIndex = None
	shortestPathLength = 999999999999999999.0
	for pathIndex in range( len( paths ) ):
		path = paths[ pathIndex ]
		for pointIndex in range( len( path ) ):
			point = path[ pointIndex ]
			distanceSquared = point.distance2( removedEndpointPoint )
			if distanceSquared < closestDistanceSquared:
				closestDistanceSquared = distanceSquared
				closestPathIndex = pathIndex
	if closestPathIndex == None:
		return
	closestPath = paths[ closestPathIndex ]
	if closestDistanceSquared < 0.8 * layerExtrusionWidth * layerExtrusionWidth:
		return
	closestPointIndex = getWithLeastLength( closestPath, removedEndpointPoint )
	if closestPointIndex == 0 or closestPointIndex == len( closestPath ):
		closestPath.insert( closestPointIndex, removedEndpointPoint )
		return
	otherPaths = paths[ 0 : closestPathIndex ] + paths[ closestPathIndex + 1 : len( paths ) ]
	if not isIntersectingLoopsPaths( arounds, otherPaths, removedEndpointPoint, closestPath[ closestPointIndex - 1 ] ):
		if not isIntersectingLoopsPaths( arounds, otherPaths, removedEndpointPoint, closestPath[ closestPointIndex ] ):
			closestPath.insert( closestPointIndex, removedEndpointPoint )

def addPath( extrusionWidth, fill, path, rotationPlaneAngle ):
	"Add simplified path to fill."
	planeRotated = euclidean.getPathRoundZAxisByPlaneAngle( rotationPlaneAngle, getSimplifiedPath( path, extrusionWidth ) )
	fill.append( planeRotated )

def addSparseEndpoints( doubleExtrusionWidth, endpoints, fillLine, horizontalSegments, infillDensity, removedEndpoints, surroundingXIntersections ):
	"Add sparse endpoints."
	horizontalEndpoints = horizontalSegments[ fillLine ]
	for segment in horizontalEndpoints:
		addSparseEndpointsFromSegment( doubleExtrusionWidth, endpoints, fillLine, horizontalSegments, infillDensity, removedEndpoints, segment, surroundingXIntersections )

def addSparseEndpointsFromSegment( doubleExtrusionWidth, endpoints, fillLine, horizontalSegments, infillDensity, removedEndpoints, segment, surroundingXIntersections ):
	"Add sparse endpoints from a segment."
	endpointFirstPoint = segment[ 0 ].point
	endpointSecondPoint = segment[ 1 ].point
	shouldFill = fillLine < 1 or fillLine >= len( horizontalSegments ) - 1 or surroundingXIntersections == None
	if infillDensity > 0.0:
		if int( round( round( fillLine * infillDensity ) / infillDensity ) ) == fillLine:
			shouldFill = True
	if endpointFirstPoint.distance( endpointSecondPoint ) < doubleExtrusionWidth:
		shouldFill = True
	if shouldFill:
		endpoints += segment
		return
	if not isSegmentAround( horizontalSegments[ fillLine - 1 ], segment ):
		endpoints += segment
		return
	if not isSegmentAround( horizontalSegments[ fillLine + 1 ], segment ):
		endpoints += segment
		return
	for surroundingIndex in range( 0, len( surroundingXIntersections ), 2 ):
		surroundingXFirst = surroundingXIntersections[ surroundingIndex ]
		surroundingXSecond = surroundingXIntersections[ surroundingIndex + 1 ]
		if euclidean.isSegmentCompletelyInX( segment, surroundingXFirst, surroundingXSecond ):
			removedEndpoints += segment
			return
	endpoints += segment

def createFillForSurroundings( surroundingLoops ):
	"Create extra fill loops for surrounding loops."
	for surroundingLoop in surroundingLoops:
		createExtraFillLoops( surroundingLoop )

def createExtraFillLoops( surroundingLoop ):
	"Create extra fill loops."
	for innerSurrounding in surroundingLoop.innerSurroundings:
		createFillForSurroundings( innerSurrounding.innerSurroundings )
#	if len( surroundingLoop.perimeterPaths ) > 0:
#		return
	outsides = []
	insides = euclidean.getInsidesAddToOutsides( surroundingLoop.getFillLoops(), outsides )
	allFillLoops = []
	for outside in outsides:
		transferredLoops = euclidean.getTransferredPaths( insides, outside )
		allFillLoops += getExtraFillLoops( transferredLoops, outside, surroundingLoop.extrusionWidth )
	if len( allFillLoops ) > 0:
		surroundingLoop.lastFillLoops = allFillLoops
	surroundingLoop.extraLoops += allFillLoops

def fillChainFile( filename = '' ):
	"Fill the slices of a gcode file.  Chain slice the file if it is a GNU TriangulatedSurface file.  If no filename is specified, fill the first unmodified gcode file in this folder."
	if filename == '':
		unmodified = gcodec.getGNUGcode()
		if len( unmodified ) == 0:
			print( "There are no unmodified gcode files in this folder." )
			return
		filename = unmodified[ 0 ]
	startTime = time.time()
	fillPreferences = FillPreferences()
	preferences.readPreferences( fillPreferences )
	print( 'File ' + gcodec.getSummarizedFilename( filename ) + ' is being chain filled.' )
	gcodeText = gcodec.getFileText( filename )
	if gcodeText == '':
		return
	suffixFilename = filename[ : filename.rfind( '.' ) ] + '_fill.gcode'
	gcodec.writeFileText( suffixFilename, getFillChainGcode( gcodeText, fillPreferences ) )
	print( 'The filled file is saved as ' + suffixFilename )
	vectorwrite.writeSkeinforgeVectorFile( suffixFilename )
	print( 'It took ' + str( int( round( time.time() - startTime ) ) ) + ' seconds to fill the file.' )

def fillFile( filename = '' ):
	"Fill the slices of a gcode file.  If no filename is specified, fill the first unmodified gcode file in this folder."
	if filename == '':
		unmodified = gcodec.getUnmodifiedGCodeFiles()
		if len( unmodified ) == 0:
			print( "There are no unmodified gcode files in this folder." )
			return
		filename = unmodified[ 0 ]
	startTime = time.time()
	fillPreferences = FillPreferences()
	preferences.readPreferences( fillPreferences )
	print( 'File ' + gcodec.getSummarizedFilename( filename ) + ' is being filled.' )
	gcodeText = gcodec.getFileText( filename )
	if gcodeText == '':
		return
	suffixFilename = filename[ : filename.rfind( '.' ) ] + '_fill.gcode'
	gcodec.writeFileText( suffixFilename, getFillGcode( gcodeText, fillPreferences ) )
	print( 'The filled file is saved as ' + gcodec.getSummarizedFilename( suffixFilename ) )
	vectorwrite.writeSkeinforgeVectorFile( suffixFilename )
	print( 'It took ' + str( int( round( time.time() - startTime ) ) ) + ' seconds to fill the file.' )

def getExtraFillLoops( insideLoops, outsideLoop, radius ):
	"Get extra loops between inside and outside loops."
	greaterThanRadius = 1.4 * radius
	muchGreaterThanRadius = 2.5 * radius
	extraFillLoops = []
	circleNodes = intercircle.getCircleNodesFromLoop( outsideLoop, greaterThanRadius )
	for inside in insideLoops:
		circleNodes += intercircle.getCircleNodesFromLoop( inside, greaterThanRadius )
	centers = intercircle.getCentersFromCircleNodes( circleNodes )
	otherLoops = insideLoops + [ outsideLoop ]
	for center in centers:
		inset = intercircle.getInsetFromClockwiseLoop( center, radius )
		if euclidean.isLargeSameDirection( inset, center, muchGreaterThanRadius ):
			if isPathAlwaysInsideLoop( outsideLoop, inset ):
				if isPathAlwaysOutsideLoops( insideLoops, inset ):
					if not euclidean.isLoopIntersectingLoops( inset, otherLoops ):
						extraFillLoops.append( inset )
	return extraFillLoops

def getFillChainGcode( gcodeText, fillPreferences = None ):
	"Fill the slices of a gcode text.  Chain fill the gcode if it is not already sliced."
	if not gcodec.isProcedureDone( gcodeText, 'slice' ):
		gcodeText = slice.getSliceGcode( gcodeText )
	return getFillGcode( gcodeText, fillPreferences )

def getFillGcode( gcodeText, fillPreferences = None ):
	"Fill the slices of a gcode text."
	if gcodeText == '':
		return ''
	if gcodec.isProcedureDone( gcodeText, 'fill' ):
		return gcodeText
	if fillPreferences == None:
		fillPreferences = FillPreferences()
		preferences.readPreferences( fillPreferences )
	skein = FillSkein()
	skein.parseGcode( fillPreferences, gcodeText )
	return skein.output.getvalue()

def getHalfSimplifiedPath( path, radius, remainder ):
	"Get the path with half of the points inside the channel removed."
	if len( path ) < 2:
		return path
	channelRadius = radius * .01
	simplified = []
	addIndex = len( path ) - 1
	for pointIndex in range( len( path ) ):
		point = path[ pointIndex ]
		if pointIndex % 2 == remainder or pointIndex == 0 or pointIndex == addIndex:
			simplified.append( point )
		elif not euclidean.isWithinChannel( channelRadius, pointIndex, path ):
			simplified.append( point )
	return simplified

def getHorizontalSegments( fillLoops, alreadyFilledArounds, y ):
	"Get horizontal segments inside loops."
	solidXIntersectionList = []
	euclidean.addXIntersectionsFromLoops( fillLoops, - 1, solidXIntersectionList, y )
	euclidean.addXIntersectionsFromLoopLists( alreadyFilledArounds, solidXIntersectionList, y )
	return euclidean.getSegmentsFromIntersections( solidXIntersectionList, y, fillLoops[ 0 ][ 0 ].z )

def getSimplifiedPath( path, radius ):
	"Get path with points inside the channel removed."
	if len( path ) < 2:
		return path
	simplificationMultiplication = 256
	simplificationRadius = radius / float( simplificationMultiplication )
	maximumIndex = len( path ) * simplificationMultiplication
	pointIndex = 1
	while pointIndex < maximumIndex:
		path = getHalfSimplifiedPath( path, simplificationRadius, 0 )
		path = getHalfSimplifiedPath( path, simplificationRadius, 1 )
		simplificationRadius += simplificationRadius
		simplificationRadius = min( simplificationRadius, radius )
		pointIndex += pointIndex
	return euclidean.getAwayPath( path, radius )

def getSurroundingXIntersections( alreadyFilledSize, doubleSolidSurfaceThickness, surroundingSlices, y ):
	"Get x intersections from surrounding layers."
	if len( surroundingSlices ) < doubleSolidSurfaceThickness:
		return None
	joinedX = []
	solidXIntersectionList = []
	for surroundingIndex in range( len( surroundingSlices ) ):
		surroundingSlice = surroundingSlices[ surroundingIndex ]
		euclidean.addXIntersectionsFromLoops( surroundingSlice, surroundingIndex, joinedX, y )
	solidTable = {}
	solid = False
	joinedX.sort()
	for solidX in joinedX:
		euclidean.toggleHashtable( solidTable, solidX.index, "" )
		oldSolid = solid
		solid = len( solidTable ) >= doubleSolidSurfaceThickness
		if oldSolid != solid:
			solidXIntersectionList.append( solidX.x )
	return solidXIntersectionList

def getWithLeastLength( path, point ):
	"Insert a point into a path, at the index at which the path would be shortest."
	shortestPointIndex = None
	shortestPathLength = 999999999999999999.0
	for pointIndex in range( len( path ) + 1 ):
		concatenation = path[ : ]
		concatenation.insert( pointIndex, point )
		concatenationLength = euclidean.getPathLength( concatenation )
		if concatenationLength < shortestPathLength:
			shortestPathLength = concatenationLength
			shortestPointIndex = pointIndex
	return shortestPointIndex

def isIntersectingLoopsPaths( loops, paths, pointBegin, pointEnd ):
	"Determine if the segment between the first and second point is intersecting the loop list."
	normalizedSegment = pointEnd.dropAxis( 2 ) - pointBegin.dropAxis( 2 )
	normalizedSegmentLength = abs( normalizedSegment )
	if normalizedSegmentLength == 0.0:
		return False
	normalizedSegment /= normalizedSegmentLength
	segmentYMirror = complex( normalizedSegment.real, - normalizedSegment.imag )
	pointBeginRotated = euclidean.getRoundZAxisByPlaneAngle( segmentYMirror, pointBegin )
	pointEndRotated = euclidean.getRoundZAxisByPlaneAngle( segmentYMirror, pointEnd )
	if euclidean.isLoopListIntersectingInsideXSegment( loops, pointBeginRotated.x, pointEndRotated.x, segmentYMirror, pointBeginRotated.y ):
		return True
	return euclidean.isXSegmentIntersectingPaths( paths, pointBeginRotated.x, pointEndRotated.x, segmentYMirror, pointBeginRotated.y )

def isPathAlwaysInsideLoop( loop, path ):
	"Determine if all points of a path are inside another loop."
	for point in path:
		if euclidean.getNumberOfIntersectionsToLeft( point, loop ) % 2 == 0:
			return False
	return True

def isPathAlwaysOutsideLoops( loops, path ):
	"Determine if all points in a path are outside another loop in a list."
	for loop in loops:
		for point in path:
			if euclidean.getNumberOfIntersectionsToLeft( point, loop ) % 2 == 1:
				return False
	return True

def isPerimeterPathInSurroundLoops( surroundingLoops ):
	"Determine if there is a perimeter path in the surrounding loops."
	for surroundingLoop in surroundingLoops:
		if len( surroundingLoop.perimeterPaths ) > 0:
			return True
	return False

def isSegmentAround( aroundSegments, segment ):
	"Determine if there is another segment around."
	for aroundSegment in aroundSegments:
		endpoint = aroundSegment[ 0 ]
		if isSegmentInX( segment, endpoint.point.x, endpoint.otherEndpoint.point.x ):
			return True
	return False

def isSegmentInX( segment, xFirst, xSecond ):
	"Determine if the segment overlaps within x."
	segmentFirstX = segment[ 0 ].point.x
	segmentSecondX = segment[ 1 ].point.x
	if min( segmentFirstX, segmentSecondX ) > max( xFirst, xSecond ):
		return False
	return max( segmentFirstX, segmentSecondX ) > min( xFirst, xSecond )

class FillSkein:
	"A class to fill a skein of extrusions."
	def __init__( self ):
		self.extruderActive = False
		self.isPerimeter = False
		self.lastExtraShells = - 1
		self.lineIndex = 0
		self.oldLocation = None
		self.oldOrderedLocation = Vec3()
		self.output = cStringIO.StringIO()
		self.rotatedLayer = None
		self.rotatedLayers = []
		self.shutdownLineIndex = sys.maxint
		self.surroundingLoop = None
		self.thread = None

	def addFill( self, layerIndex ):
		"Add fill to the slice layer."
#		if layerIndex > 0:
#			return
#		print( 'layerIndex ' + str( layerIndex ) )
		alreadyFilledArounds = []
		arounds = []
		back = - 999999999.0
		layerExtrusionWidth = self.extrusionWidth
		layerFillInset = self.fillInset
		self.addLine( '(<layerStart> ' + str( self.rotatedLayers[ layerIndex ].surroundingLoops[ 0 ].boundary[ 0 ].z ) + ' )' ) # Indicate that a new layer is starting.
		if self.rotatedLayers[ layerIndex ].rotation != None:
			layerExtrusionWidth = self.extrusionWidth * self.bridgeExtrusionWidthOverSolid
			layerFillInset = self.fillInset * self.bridgeExtrusionWidthOverSolid
			self.addLine( '(<bridgeLayer> )' ) # Indicate that this is a bridge layer.
		doubleExtrusionWidth = 2.0 * layerExtrusionWidth
		muchGreaterThanLayerFillInset = 2.5 * layerFillInset
		endpoints = []
		fill = []
		aroundInset = 0.7 * layerFillInset
		front = - back
		slightlyGreaterThanFill = 1.01 * layerFillInset
		layerRotationAroundZAngle = self.getLayerRoundZ( layerIndex )
		reverseRotationAroundZAngle = complex( layerRotationAroundZAngle.real, - layerRotationAroundZAngle.imag )
		rotatedExtruderLoops = []
		stretch = 0.5 * layerExtrusionWidth
		loops = []
		for surroundingLoop in self.rotatedLayers[ layerIndex ].surroundingLoops:
			loops.append( surroundingLoop.boundary )
		surroundingSlices = []
		layerRemainder = layerIndex % int( round( self.fillPreferences.diaphragmPeriod.value ) )
		if layerRemainder >= int( round( self.fillPreferences.diaphragmThickness.value ) ):
			for surroundingIndex in range( 1, self.solidSurfaceThickness + 1 ):
				self.addRotatedSlice( layerIndex - surroundingIndex, reverseRotationAroundZAngle, surroundingSlices )
				self.addRotatedSlice( layerIndex + surroundingIndex, reverseRotationAroundZAngle, surroundingSlices )
		extraShells = self.fillPreferences.extraShellsSparseLayer.value
		if len( surroundingSlices ) < self.doubleSolidSurfaceThickness:
			extraShells = self.fillPreferences.extraShellsAlternatingSolidLayer.value
			if self.lastExtraShells != self.fillPreferences.extraShellsBase.value:
				extraShells = self.fillPreferences.extraShellsBase.value
			self.lastExtraShells = extraShells
		else:
			self.lastExtraShells = - 1
		surroundingLoops = euclidean.getOrderedSurroundingLoops( layerExtrusionWidth, self.rotatedLayers[ layerIndex ].surroundingLoops )
		if isPerimeterPathInSurroundLoops( surroundingLoops ):
			extraShells = 0
		for extraShellIndex in range( extraShells ):
			createFillForSurroundings( surroundingLoops )
		fillLoops = euclidean.getFillOfSurroundings( surroundingLoops )
		for loop in fillLoops:
			alreadyFilledLoop = []
			alreadyFilledArounds.append( alreadyFilledLoop )
			planeRotatedPerimeter = euclidean.getPathRoundZAxisByPlaneAngle( reverseRotationAroundZAngle, loop )
			rotatedExtruderLoops.append( planeRotatedPerimeter )
			circleNodes = intercircle.getCircleNodesFromLoop( planeRotatedPerimeter, slightlyGreaterThanFill )
			centers = intercircle.getCentersFromCircleNodes( circleNodes )
			for center in centers:
				alreadyFilledInset = intercircle.getInsetFromClockwiseLoop( center, layerFillInset )
				if euclidean.getMaximumSpan( alreadyFilledInset ) > muchGreaterThanLayerFillInset or euclidean.isWiddershins( alreadyFilledInset ):
					alreadyFilledLoop.append( alreadyFilledInset )
				around = intercircle.getInsetFromClockwiseLoop( center, aroundInset )
				if euclidean.isPathInsideLoop( planeRotatedPerimeter, around ) != euclidean.isWiddershins( planeRotatedPerimeter ):
					if euclidean.getMaximumSpan( alreadyFilledInset ) > muchGreaterThanLayerFillInset:
						arounds.append( around )
						for point in around:
							back = max( back, point.y )
							front = min( front, point.y )
		fillWidth = back - front
		numberOfIntervals = int( math.floor( fillWidth / layerExtrusionWidth ) )
		fillRemainder = fillWidth - float( numberOfIntervals ) * layerExtrusionWidth
		halfFillRemainder = 0.5 * fillRemainder
		back -= halfFillRemainder
		front += halfFillRemainder
		horizontalSegments = []
		for fillLine in range( numberOfIntervals + 1 ):
			y = front + float( fillLine ) * layerExtrusionWidth
			lineSegments = getHorizontalSegments( rotatedExtruderLoops, alreadyFilledArounds, y )
			horizontalSegments.append( lineSegments )
		removedEndpoints = []
		for fillLine in range( len( horizontalSegments ) ):
			y = front + float( fillLine ) * layerExtrusionWidth
			horizontalEndpoints = horizontalSegments[ fillLine ]
			surroundingXIntersections = getSurroundingXIntersections( len( alreadyFilledArounds ), self.doubleSolidSurfaceThickness, surroundingSlices, y )
			addSparseEndpoints( doubleExtrusionWidth, endpoints, fillLine, horizontalSegments, self.infillDensity, removedEndpoints, surroundingXIntersections )
		if len( endpoints ) < 1:
			euclidean.addToThreadsRemoveFromSurroundings( self.oldOrderedLocation, surroundingLoops, self )
			return
		stretchedXSegments = []
		for beginningEndpoint in endpoints[ : : 2 ]:
			beginningPoint = beginningEndpoint.point
			stretchedXSegment = StretchedXSegment().getFromXYStretch( beginningPoint.x, beginningPoint.y, beginningEndpoint.otherEndpoint.point.x, stretch )
			stretchedXSegments.append( stretchedXSegment )
		endpointFirst = endpoints[ 0 ]
		endpoints.remove( endpointFirst )
		otherEndpoint = endpointFirst.otherEndpoint
		endpoints.remove( otherEndpoint )
		nextEndpoint = None
		path = []
		paths = []
		if len( endpoints ) > 1:
			nextEndpoint = otherEndpoint.getNearestMiss( arounds, endpoints, layerExtrusionWidth, path, paths, stretchedXSegments )
			if nextEndpoint != None:
				if nextEndpoint.point.distance2( endpointFirst.point ) < nextEndpoint.point.distance2( otherEndpoint.point ):
					endpointFirst = endpointFirst.otherEndpoint
					otherEndpoint = endpointFirst.otherEndpoint
		paths.append( path )
		path.append( endpointFirst.point )
		path.append( otherEndpoint.point )
		while len( endpoints ) > 1:
			nextEndpoint = otherEndpoint.getNearestMiss( arounds, endpoints, layerExtrusionWidth, path, paths, stretchedXSegments )
			if nextEndpoint == None:
				path = []
				paths.append( path )
				nextEndpoint = otherEndpoint.getNearestEndpoint( endpoints )
			path.append( nextEndpoint.point )
			endpoints.remove( nextEndpoint )
			otherEndpoint = nextEndpoint.otherEndpoint
			hop = nextEndpoint.getHop( layerFillInset, path )
			if hop != None:
				path = [ hop ]
				paths.append( path )
			path.append( otherEndpoint.point )
			endpoints.remove( otherEndpoint )
		for removedEndpoint in removedEndpoints:
			addAroundClosest( arounds, layerExtrusionWidth, paths, removedEndpoint )
		for path in paths:
			addPath( layerFillInset, fill, path, layerRotationAroundZAngle )
		euclidean.transferPathsToSurroundingLoops( fill, surroundingLoops )
		euclidean.addToThreadsRemoveFromSurroundings( self.oldOrderedLocation, surroundingLoops, self )

	def addGcodeFromThread( self, thread ):
		"Add a gcode thread to the output."
		if len( thread ) > 0:
			self.addGcodeMovement( thread[ 0 ] )
		else:
			print( "zero length vertex positions array which was skipped over, this should never happen" )
		if len( thread ) < 2:
			return
		self.addLine( 'M101' )
		for point in thread[ 1 : ]:
			self.addGcodeMovement( point )
		self.addLine( "M103" ) # Turn extruder off.

	def addGcodeMovement( self, point ):
		"Add a movement to the output."
		self.lastOutputPoint = point
		self.output.write( "G1 X" + euclidean.getRoundedToThreePlaces( point.x ) + " Y" + euclidean.getRoundedToThreePlaces( point.y ) )
		self.addLine( " Z" + euclidean.getRoundedToThreePlaces( point.z ) + " F" + euclidean.getRoundedToThreePlaces( self.feedratePerMinute ) )

	def addLine( self, line ):
		"Add a line of text and a newline to the output."
		self.output.write( line + "\n" )

	def addRotatedSlice( self, layerIndex, reverseRotationAroundZAngle, surroundingSlices ):
		"Add a rotated slice to the surrounding slices."
		if layerIndex < 0 or layerIndex >= len( self.rotatedLayers ):
			return
		layer = self.rotatedLayers[ layerIndex ].boundaries
		rotatedSlice = []
		for thread in layer:
			planeRotatedLoop = euclidean.getPathRoundZAxisByPlaneAngle( reverseRotationAroundZAngle, thread )
			rotatedSlice.append( planeRotatedLoop )
		surroundingSlices.append( rotatedSlice )

	def addShutdownToOutput( self ):
		"Add shutdown gcode to the output."
		for line in self.lines[ self.shutdownLineIndex : ]:
			self.addLine( line )

	def addToThread( self, location ):
		"Add a location to thread."
		if self.oldLocation == None:
			return
		if self.surroundingLoop != None:
			if self.isPerimeter:
				if self.surroundingLoop.loop == None:
					self.surroundingLoop.loop = []
				self.surroundingLoop.loop.append( location )
				return
			elif self.thread == None:
				self.thread = [ self.oldLocation ]
				self.surroundingLoop.perimeterPaths.append( self.thread )
		self.thread.append( location )

	def getLayerRoundZ( self, layerIndex ):
		"Get the plane angle around z that the layer is rotated by."
		rotation = self.rotatedLayers[ layerIndex ].rotation
		if rotation != None:
			return rotation
		return euclidean.getPolar( self.infillBeginRotation + float( ( layerIndex % 2 ) * self.infillOddLayerExtraRotation ), 1.0 )

	def getRotatedLayer( self ):
		"Get the rotated layer, making a new one if necessary."
		if self.rotatedLayer == None:
			self.rotatedLayer = RotatedLayer()
			self.rotatedLayers.append( self.rotatedLayer )
		return self.rotatedLayer

	def linearMove( self, splitLine ):
		"Add a linear move to the thread."
		location = gcodec.getLocationFromSplitLine( self.oldLocation, splitLine )
		if self.extruderActive:
			self.addToThread( location )
		self.oldLocation = location

	def parseGcode( self, fillPreferences, gcodeText ):
		"Parse gcode text and store the bevel gcode."
		self.fillPreferences = fillPreferences
		self.lines = gcodec.getTextLines( gcodeText )
		self.parseInitialization()
		self.feedratePerMinute = 60.0 * fillPreferences.feedratePerSecond.value
		self.infillDensity = fillPreferences.infillDensity.value
		self.infillBeginRotation = math.radians( fillPreferences.infillBeginRotation.value )
		self.infillOddLayerExtraRotation = math.radians( fillPreferences.infillOddLayerExtraRotation.value )
		self.solidSurfaceThickness = int( round( self.fillPreferences.solidSurfaceThickness.value ) )
		self.doubleSolidSurfaceThickness = self.solidSurfaceThickness + self.solidSurfaceThickness
		for lineIndex in range( self.lineIndex, len( self.lines ) ):
			self.parseLine( lineIndex )
		for layerIndex in range( len( self.rotatedLayers ) ):
			self.addFill( layerIndex )
		self.addShutdownToOutput()

	def parseInitialization( self ):
		"Parse gcode initialization and store the parameters."
		for self.lineIndex in range( len( self.lines ) ):
			line = self.lines[ self.lineIndex ]
			splitLine = line.split( ' ' )
			firstWord = ''
			if len( splitLine ) > 0:
				firstWord = splitLine[ 0 ]
			if firstWord == '(<extrusionWidth>':
				self.extrusionWidth = float( splitLine[ 1 ] )
				self.fillInset = 0.5 * self.extrusionWidth * ( 2.0 - self.fillPreferences.infillPerimeterOverlap.value )
				self.addLine( '(<fillInset> ' + str( self.fillInset ) + ' )' ) # Set fill inset.
			elif firstWord == '(<bridgeExtrusionWidthOverSolid>':
				self.bridgeExtrusionWidthOverSolid = float( splitLine[ 1 ] )
			elif firstWord == '(<extrusionStart>':
				self.addLine( '(<procedureDone> fill )' )
				self.addLine( line )
				return
			self.addLine( line )

	def parseLine( self, lineIndex ):
		"Parse a gcode line and add it to the fill skein."
		splitLine = self.lines[ lineIndex ].split( ' ' )
		if len( splitLine ) < 1:
			return
		firstWord = splitLine[ 0 ]
		if firstWord == 'G1':
			self.linearMove( splitLine )
		elif firstWord == 'M101':
			self.extruderActive = True
		elif firstWord == 'M103':
			self.extruderActive = False
			self.thread = None
			self.isPerimeter = False
		elif firstWord == '(<bridgeDirection>':
			secondWordWithoutBrackets = splitLine[ 1 ].replace( '(', '' ).replace( ')', '' )
			self.getRotatedLayer().rotation = complex( secondWordWithoutBrackets )
		elif firstWord == '(<boundaryPoint>':
			location = gcodec.getLocationFromSplitLine( None, splitLine )
			self.surroundingLoop.boundary.append( location )
		elif firstWord == '(<extruderShutDown>':
			self.shutdownLineIndex = lineIndex
		elif firstWord == '(<layerStart>':
			self.rotatedLayer = None
			self.thread = None
		elif firstWord == '(<perimeter>':
			self.isPerimeter = True
		elif firstWord == '(<surroundingLoop>':
			self.surroundingLoop = euclidean.SurroundingLoop()
			rotatedLayer = self.getRotatedLayer()
			rotatedLayer.surroundingLoops.append( self.surroundingLoop )
			rotatedLayer.boundaries.append( self.surroundingLoop.boundary )
		elif firstWord == '(</surroundingLoop>':
			self.surroundingLoop = None

class FillPreferences:
	"A class to handle the fill preferences."
	def __init__( self ):
		"Set the default preferences, execute title & preferences filename."
		#Set the default preferences.
		self.diaphragmPeriod = preferences.IntPreference().getFromValue( 'Diaphragm Period (layers):', 999 )
		self.diaphragmThickness = preferences.IntPreference().getFromValue( 'Diaphragm Thickness (layers):', 0 )
		self.extraShellsAlternatingSolidLayer = preferences.IntPreference().getFromValue( 'Extra Shells on Alternating Solid Layer (layers):', 1 )
		self.extraShellsBase = preferences.IntPreference().getFromValue( 'Extra Shells on Base (layers):', 0 )
		self.extraShellsSparseLayer = preferences.IntPreference().getFromValue( 'Extra Shells on Sparse Layer (layers):', 1 )
		self.feedratePerSecond = preferences.FloatPreference().getFromValue( 'Feedrate (mm/s):', 16.0 )
		self.filenameInput = preferences.Filename().getFromFilename( [ ( 'GNU Triangulated Surface text files', '*.gts' ), ( 'Gcode text files', '*.gcode' ) ], 'Open File to be Filled', '' )
		self.infillBeginRotation = preferences.FloatPreference().getFromValue( 'Infill Begin Rotation (degrees):', 45.0 )
		self.infillDensity = preferences.FloatPreference().getFromValue( 'Infill Density (ratio):', 0.25 )
		self.infillOddLayerExtraRotation = preferences.FloatPreference().getFromValue( 'Infill Odd Layer Extra Rotation (degrees):', 90.0 )
		self.infillPerimeterOverlap = preferences.FloatPreference().getFromValue( 'Infill Perimeter Overlap (ratio):', 0.5 )
		self.solidSurfaceThickness = preferences.IntPreference().getFromValue( 'Solid Surface Thickness (layers):', 3 )
		directoryRadio = []
		self.directoryPreference = preferences.RadioLabel().getFromRadioLabel( 'Fill All Unmodified Files in a Directory', 'File or Directory Choice:', directoryRadio, False )
		self.filePreference = preferences.Radio().getFromRadio( 'Fill File', directoryRadio, True )
		#Create the archive, title of the execute button, title of the dialog & preferences filename.
		self.archive = [
			self.diaphragmPeriod,
			self.diaphragmThickness,
			self.extraShellsAlternatingSolidLayer,
			self.extraShellsBase,
			self.extraShellsSparseLayer,
			self.feedratePerSecond,
			self.filenameInput,
			self.infillBeginRotation,
			self.infillDensity,
			self.infillOddLayerExtraRotation,
			self.infillPerimeterOverlap,
			self.solidSurfaceThickness,
			self.directoryPreference,
			self.filePreference ]
		self.executeTitle = 'Fill'
		self.filenamePreferences = preferences.getPreferencesFilePath( 'fill.csv' )
		self.filenameHelp = 'fill.html'
		self.title = 'Fill Preferences'

	def execute( self ):
		"Fill button has been clicked."
		filenames = gcodec.getGcodeDirectoryOrFile( self.directoryPreference.value, self.filenameInput.value, self.filenameInput.wasCancelled )
		for filename in filenames:
			fillChainFile( filename )


class RotatedLayer:
	"A rotated layer."
	def __init__( self ):
		self.boundaries = []
		self.rotation = None
		self.surroundingLoops = []

	def __repr__( self ):
		"Get the string representation of this RotatedLayer."
		return '%s, %s, %s' % ( self.rotation, self.surroundingLoops, self.boundaries )


class StretchedXSegment:
	"A stretched x segment."
	def __repr__( self ):
		"Get the string representation of this StretchedXSegment."
		return str( self.xMinimum ) + ' ' + str( self.xMaximum ) + ' ' + str( self.y )

	def getFromXYStretch( self, firstX, y, secondX, stretch ):
		"Initialize from x, y, and stretch."
		self.xMaximum = max( firstX, secondX ) + stretch
		self.xMinimum = min( firstX, secondX ) - stretch
		self.y = y
		return self


def main( hashtable = None ):
	"Display the fill dialog."
	preferences.displayDialog( FillPreferences() )

if __name__ == "__main__":
	main()