#!BPY

"""
Name: 'Cable Guy'
Blender: 248
Group: 'Misc'
Tooltip: 'free edges to cables'
"""

__author__ = ["Mathias Weitz"]
__url__ = ("http://wiki.blender.org/index.php/Extensions:Py/Scripts/Manual/Object/Cable_Guy")
__version__ = "0.0.2 28/8/06"

__bpydoc__ = """\
Make a Cable out of a several conected Edges.

In edit mode, select several connected edges.

The selected Edges are extruded to create a tube.

If the edges are at a right angle or less, the Cable will chose to optimize the path.

Thus following a smoother contour.
"""
# --------------------------------------------------------------------------
# Cable guy by Mathias Weitz
# --------------------------------------------------------------------------
# ***** BEGIN GPL LICENSE BLOCK *****
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 2
# of the License, or (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software Foundation,
# Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
#
# ***** END GPL LICENCE BLOCK *****
# --------------------------------------------------------------------------
import Blender
from Blender import *
from Blender import NMesh
from Blender.BGL import *
from Blender.Draw import *

import math
from math import *

# Events
EVENT_NOEVENT    = 1
EVENT_START      = 2
EVENT_EXIT       = 3
EVENT_SIZE       = 4
EVENT_VSEG       = 5
EVENT_USEG       = 6
EVENT_TENSION    = 7
EVENT_CMODE      = 8
EVENT_SPLINE     = 9
EVENT_ENDE       = 10

# Inits
V_SIZE = 0.1
V_VSEG = 20
V_USEG = 4
V_TENSION = 0.25
V_CMODE = 1
V_SPLINE = 1
V_ENDE = 1


######################################################
# GUI drawing
######################################################
def draw():
	global EVENT_NOEVENT,EVENT_START,EVENT_EXIT 
	global EVENT_SIZE, V_SIZE, B_SIZE
	global EVENT_VSEG, V_VSEG, B_VSEG
	global EVENT_USEG, V_USEG, B_USEG
	global EVENT_TENSION, V_TENSION, B_TENSION
	global EVENT_CMODE, V_CMODE, B_CMODE
	global EVENT_SPLINE, V_SPLINE, B_SPLINE
	global EVENT_ENDE, V_ENDE, B_ENDE
	
	########## Titles
	glClear(GL_COLOR_BUFFER_BIT)
	glColor3f(0,0,0)
	glRasterPos2d(10,285)
	Text ("Cable Guy v0.0.2")
	glColor3f(0.4,0.3,0)
	glRasterPos2d(10,270)
	Text ("Schnelles Erzeugen von Kabeln direkt in der Gitter-Struktur")
	glColor3f(0,0,0)
	glRasterPos2d(20,250)
	Text ("1. Selektiere einen oder mehrere Kantenzuege")
	glRasterPos2d(20,235)
	Text ("2. Die erzeugten Kabel verdrehen sich evetuell um ihre Laengsachse")
	glRasterPos2d(40,220)
	Text ("Auf die Verdrehung hat man Einfluss mit 'Kabel-Torsion'")
	glRasterPos2d(20,205)
	Text ("3. Die Kruemmung kann mit Tension eingestellt werden,")
	glRasterPos2d(40,190)
	Text ("jedoch ist 0.25 wohl der einzige Wert, der gut aussieht.")
	glRasterPos2d(20,175)
	Text ("4. Der Kabel-Abschluss verlaengert die Kabel-Enden, bis sie auf eine Flaeche treffen,")
	
	B_TENSION = Slider("Tension ",EVENT_TENSION , 10, 90, 240, 18, V_TENSION, 0.1, 0.33, 1)
	B_SPLINE = Menu ("SPLINE %t|B-Spline %x1|SB-Spline %x2|",EVENT_SPLINE, 10, 70, 240, 18 ,V_SPLINE)
	B_SIZE = Slider("Size ",EVENT_SIZE , 10, 110, 240, 18, V_SIZE, 0.001, 5.0, 1)
	B_VSEG = Slider("Seg Laenge ",EVENT_VSEG , 10, 130, 240, 18, V_VSEG, 10, 1500, 1)
	B_USEG = Slider("Seg Umfang ",EVENT_USEG , 10, 150, 240, 18, V_USEG, 3, 50, 1)
	B_CMODE = Menu ("Drehung des Kabels %t|Kabel-Torsion A-C-B %x1|Kabel-Torsion A-B-C %x2|Kabel-Torsion A-C-A %x3|",EVENT_CMODE, 10, 30, 240, 18 ,V_CMODE)
	B_ENDE = Menu ("Abschluss %t|Kabel-Abschluss offen %x1|Kabel-Abschluss verlaengert zur naechsten Oberflaeche %x2|Kabel-Abschluss verlaengert zur naechsten Oberflaeche und Ring %x3|",EVENT_ENDE, 10, 50, 240, 18 ,V_ENDE)
		
	Button("Exit",EVENT_EXIT , 130, 10, 120, 18)
	Button("Start",EVENT_START , 10, 10, 120, 18)

def event(evt, val):
	if (evt == QKEY and not val): 
		Exit()

def bevent(evt):
	global EVENT_NOEVENT,EVENT_START,EVENT_EXIT 
	global EVENT_SIZE, V_SIZE, B_SIZE
	global EVENT_VSEG, V_VSEG, B_VSEG
	global EVENT_USEG, V_USEG, B_USEG
	global EVENT_TENSION, V_TENSION, B_TENSION
	global EVENT_CMODE, V_CMODE, B_CMODE
	global EVENT_SPLINE, V_SPLINE, B_SPLINE
	global EVENT_ENDE, V_ENDE, B_ENDE
	global me
	if evt == EVENT_EXIT:
		Exit()	
	elif evt == EVENT_TENSION:
		V_TENSION = B_TENSION.val
	elif evt == EVENT_SIZE:
		V_SIZE = B_SIZE.val
	elif evt == EVENT_VSEG:
		V_VSEG = B_VSEG.val
	elif evt == EVENT_USEG:
		V_USEG = B_USEG.val	
	elif evt == EVENT_CMODE:
		V_CMODE = B_CMODE.val	
	elif evt == EVENT_SPLINE:
		V_SPLINE = B_SPLINE.val		
	elif evt == EVENT_ENDE:
		V_ENDE = B_ENDE.val	
	elif evt == EVENT_START:
		startTest(V_VSEG,V_USEG,V_TENSION,V_SIZE, V_CMODE, V_SPLINE, V_ENDE)
		Blender.Redraw()
	
#################################
# Die Routinen fuer Points
#################################

def projPointA(p1,p2,p3,pt,dir,mode):
	"berechnet die senkrechten bzw durch dir(ection) bestimmte Projektion vom KoordinatenArray p \
	 auf der Ebene, die durch p2-p1 und p3-p1 aufgespannt wird \
	 Rueckgabe ist ein Array[xyz] der Koordinaten auf der Ebene \
	 und True, falls der Punkt in der Ebene liegt. \
	 mode = 1 wird auf die Kontrolle bei dreieckigen Flaechen verzichtet \
	 damit bekommt man viereckige Flaechen besser im Griff, aber es gibt auch mehr Fehler"	 
	erg = [pt[0], pt[1], pt[2], True,0]
	abw = 0.001
	d1x = p2[0] - p1[0]
	d1y = p2[1] - p1[1]
	d1z = p2[2] - p1[2]
	d2x = p3[0] - p1[0]
	d2y = p3[1] - p1[1]
	d2z = p3[2] - p1[2]
	ddx = pt[0] - p1[0]
	ddy = pt[1] - p1[1]
	ddz = pt[2] - p1[2]
	if dir[0] == 0 and dir[1] == 0 and dir[2] == 0:
		ec = crossProd([d1x,d1y,d1z], [d2x,d2y,d2z])
	else:
		ec = dir
	e =  norm(ec)
	m = matrix3x3([d1x,d1y,d1z], [d2x,d2y,d2z],e)
	m.t()	
	detm = m.det()
	if 0.000001 < abs(detm):
		so =m.solve([ddx, ddy, ddz])
		b = True
		c1x = p2[0]*so[0] + p1[0]*(1-so[0])
		c1y = p2[1]*so[0] + p1[1]*(1-so[0])
		c1z = p2[2]*so[0] + p1[2]*(1-so[0])
		c2x = p3[0]*so[1] + p1[0]*(1-so[1])
		c2y = p3[1]*so[1] + p1[1]*(1-so[1])
		c2z = p3[2]*so[1] + p1[2]*(1-so[1])
		# Test, ob Punkt in der Ebene liegt
		if so[0] < -abw or (1+abw) < so[0] or so[1] < -abw or (1+abw) < so[1]:
			b = False
		if mode == 0 and (1+abw) < abs(so[0]) + abs(so[1]):
			b = False 
		erg = [c1x+c2x-p1[0], c1y+c2y-p1[1], c1z+c2z-p1[2], b, so[2]]
	
	return erg	


def projPoint(p1,p2,p3,pt,dir,mode):
	return projPointA(pointToArray(p1), pointToArray(p2), pointToArray(p3), \
		pointToArray(pt), dir, mode)
	 

def projPointEA(faceP, p, dir=[0,0,0]):
	"berechnet die senkrechten Projektion vom KoordinatenArray p \
	 auf der Ebene. Bei einer Ebene mit 4 Punkten wird \
	 der Punkt und der Abstand gemittelt."
	erg = [0,0,0,False,0]
	c = len(faceP.v)
	#print c,
	if (3 < c):
		# bei mehr als 3 Ecken wird das Ergebnis gemittelt	 
		sumx = 0;
		sumy = 0;
		sumz = 0;
		sumdir = 0
		hit = False
		rc = 0
		for i in range(c):
			im = (i-1)%c
			ip = (i+1)%c
			pjt = projPointA( \
				pointToArray(faceP.v[i]), \
				pointToArray(faceP.v[im]), \
				pointToArray(faceP.v[ip]), \
				p, dir ,0)
			if pjt[3]:
				rc += 1
				sumx += pjt[0]
				sumy += pjt[1]
				sumz += pjt[2]
				sumdir += pjt[4]
			hit |= pjt[3]
			
		if 0 < rc:
			erg = [sumx / rc, sumy / rc, sumz / rc, hit, sumdir / rc]
	else:
		pjt = projPointA( \
			pointToArray(faceP.v[0]), \
			pointToArray(faceP.v[1]), \
			pointToArray(faceP.v[2]), \
			p, dir ,0)
		erg = [pjt[0], pjt[1], pjt[2], pjt[3], pjt[4]]
	return erg 

def projPointE(faceP,p, dir=[0,0,0]):
	return projPointEA(faceP, pointToArray(p), dir)

def edgeDistA (a1s,a1e,a2s,a2e,d = [0,0,0]):
	"wie edgeDistP, nur es werden 3-Array statt Verts uebergeben"
	erg = [0,0,0,False]
	# e ist das normierte Kreuzprodukt
	
	d1 = vecSub(a1e, a1s)
	d1neg = vecSub(a1s, a1e)
	d2 = vecSub(a2e, a2s)
	d2neg = vecSub(a2s, a2e)
	dd = vecSub(a1s, a2s)	
	ddneg = vecSub(a2s, a1s)
	de = d
	if d == [0,0,0]:
		de = crossProd(d1,d2)
	e = norm(de)
	m = matrix3x3(d1neg,d2,e)
	if abs(m.det()) == 0:
		if d == [0,0,0]:
			# beide Geraden laufen parallel
			# es gibt eventuell viele Loesungen
			# TODO
			pass
		else:
			# es Geraden laufen aus Sicht von d parallel
			pass
	else:
		m.t()
		so = m.solve(dd)
		erg[0] = so[0]
		erg[1] = so[1]
		erg[2] = so[2]
		if 0 <= so[0] and so[0] <= 1 and 0 <= so[1] and so[1] <= 1:
			erg[3] = True
	return erg	

def edgeDistP (p1s,p1e,p2s,p2e,d = [0,0,0]):
	"Kuerzeste Distanz zweier Geraden \
	  das Ergebniss ist ein Array mit \
		0. m1 = Verhaeltniss auf der ersten Geraden \
		1. m2 = Verhaeltniss auf der zweiten Geraden \
		2. dist = Distanz der beiden Geraden \
		3. b = True, wenn die kuerzeste Distanz innerhalb der Kanten liegt"
	return edgeDistA (pointToArray(p1s),pointToArray(p1e),pointToArray(p2s),pointToArray(p2e),d)

def edgeDistQ (p1s,p1e,p2s,p2e):
	"Suche naechsten Punkt zur Geraden \
	 p1e-p1s und p2e-p2s \
	 Ergebniss ist ein Array mit\
	   1. der Punkt auf der Geraden p2e-p2s \
	   2. True, falls sich der Punkt innerhalb von p1e-p1s befindet"
	erg = [0,False]
	z =  edgeDistP (p1s,p1e,p2s,p2e)
	mo = z[0]
	mb = False
	if 0 <= mo and mo <= 1:
		mb = True
	m = z[1]
	if m < 0:
		m = 0
	if 1 < m:
		m = 1
	erg[0] = propEdge(p2s, p2e, m)
	erg[1] = mb
	return erg 

def findClosestFace(me, co, dir):
	"Sucht das Face, das in der Richtung dir dem \
	Koordinaten in co am naechsten ist \
	Rueckgabe [face, coProj, dist]"
	T_Dir = 0
	coProj = [0,0,0]
	minAbw = 0.00001
	bestFace = 0
	besth = 10000	
	for ff in me.faces:
		pjt1 = projPointEA(ff,co, dir)
		if pjt1[3]:												
			d = dist([co[0] - pjt1[0], co[1] - pjt1[1], co[2] - pjt1[2]])
			if minAbw < d and d < besth and (pjt1[4] <= 0 or (pjt1[4] != 0 and T_Dir == 1)):
				besth = d
				bestFace = ff
				coProj[0] = pjt1[0]
				coProj[1] = pjt1[1]
				coProj[2] = pjt1[2]
	if bestFace != 0:
		pass
		#pc1 = NMesh.Vert(coProj[0], coProj[1], coProj[2])
		#pc2 = NMesh.Vert(co[0], co[1], co[2])
		#me.verts.append(pc1)
		#me.verts.append(pc2)
		#e = me.addEdge(pc1,pc2)
		#po[i][1] = bestFace
		#po[i][2] = pc1
	else:
		print "found no bestFace: ", besth
	return [bestFace, coProj, besth]

def findAllEdges(me, v1, v2, dir):
	"Gibt eine Liste aller Edges zurueck \
	 die Listenelemente enthaelt folgende Infos \
	 0. ProjEdge \
	 1. Koordinaten auf der Ausgangsgeraden \
	 2. Distanz"
	crossEdges = []
	mminAbw = 0.0001
	for ee in me.edges:
		vv1 = pointToArray(ee.v1)
		vv2 = pointToArray(ee.v2)
		if not arrayEqual(v1, vv1) and not arrayEqual(v1, vv2) and not arrayEqual(v2, vv1) and not arrayEqual(v2, vv2): 
			er = edgeDistA(v1, v2, vv1, vv2,dir)
			if er[3] and 0 < er[2]:
				# Test, ob Kante verdeckt wird durch ein Face
				bestPoint1 = ratioPoint (v1, v2, er[0])
				erf = findClosestFace(me, bestPoint1, dir)
				if er[2] < erf[2] + mminAbw:
					crossEdges.append(ee)
	
	erg = [[0,v1,0],[0,v2,0]]
	b = True
	sec = 0
	while b:
		b = False
		newerg = []
		newerg.append(erg[0])
		for i in range(len(erg)-1):
			best = 100000
			targetEdge = 0
			bestRatio1 = 0
			bestPoint1 = [0,0,0]
			bestPoint2 = [0,0,0]
			for ee in crossEdges:
				vv1 = pointToArray(ee.v1)
				vv2 = pointToArray(ee.v2)
				er = edgeDistA(erg[i][1], erg[i+1][1], vv1, vv2,dir)
				if er[3]:		
					if er[2] < best and mminAbw < er[0] and er[0] < 1 - mminAbw:
						best = er[2]
						targetEdge = ee
						bestRatio1 = er[0]
						bestPoint1 = ratioPoint (erg[i][1],erg[i+1][1],er[0])	
						bestPoint2 = ratioPoint (vv1,vv2,er[1])
		
			if best < 100000:	
				#print sec, bestRatio1, best	
				#pc1 = NMesh.Vert(bestPoint1[0], bestPoint1[1], bestPoint1[2])
				#pc2 = NMesh.Vert(bestPoint2[0], bestPoint2[1], bestPoint2[2])
				#me.verts.append(pc1)
				#me.verts.append(pc2)
				#e = me.addEdge(pc1,pc2)
				newerg.append([targetEdge, bestPoint1, best, bestPoint2])
				sec += 1
				if sec < 3500:
					b = True
			newerg.append(erg[i+1])
		erg = newerg
	return erg
		
				
def propEdge(p1, p2, m):
	"Gibt die Verhaeltnisskoordinaten \
	 zwischen den beiden Punkten zurueck"
	return [p2.co.x*m + p1.co.x*(1-m), p2.co.y*m + p1.co.y*(1-m), p2.co.z*m + p1.co.z*(1-m)]

def findFaces(me, ar):
	"die Faces, das die angegebenen Punkte enthaelt, \
	rueckgabe ist ein Array mit den faces \
	die Komplexitaet ist |f|*|ar|*|aveEdges| also etwa Anzahl der Faces * 16"
	global T_Ign
	erg = []
	for f in me.faces:
		if T_Ign != 1 or f.hide != 1:
			b = True
			for j in ar:
				found = False
				for k in f.v:
					if j == k:
						found = True
				b &= found
			if b:
				erg.append(f)
	return erg

def getConnected(me, v):
	"gibt eine Liste der verbundenen Punkte zurueck"
	erg = []
	for ee in me.edges:
		if ee.v1 == v:
			erg.append(ee.v2)
		if ee.v2 == v:
			erg.append(ee.v1)
	return erg

def crossProdP(p, p1, p2):
	"berechnet das Kreuzprodukt zwischen p1-p und p2-p"
	v1 = vecSub(pointToArray(p),pointToArray(p1))
	v2 = vecSub(pointToArray(p),pointToArray(p2))
	return crossProd(v1,v2)

def cosP(p, p1, p2):
	"berechnet den Cosinus p1-p und p2-p"
	v1 = vecSub(pointToArray(p),pointToArray(p1))
	v2 = vecSub(pointToArray(p),pointToArray(p2))
	return vecCos(v1,v2)

def queueIndexDist(i1,i2, plen):
	"die Distanz zweier Indezes in einer zyklischen Liste"
	min = abs(i1-i2)
	if i1 + plen - i2 < min:
		min = i1 + plen - i2
	if i2 + plen - i1 < min:
		min = i2 + plen - i1
	return min

def minA (li):
	erg = 0
	if 0 < len(li):
		erg = li[0]
	for w in li:
		if w < erg:
			erg = w
	return erg

def maxA (li):
	erg = 0
	if 0 < len(li):
		erg = li[0]
	for w in li:
		if erg < w:
			erg = w
	return erg

def arrayEqual(a1,a2):
	erg = False
	if len(a1) == len(a2):
		erg = True
		for i in range(len(a1)):
			if 0.0000001 < abs(a1[i] - a2[i]):
				erg = False
	return erg


def ratioPoint(a1,a2,r):
	return [a1[0]*(1-r)+a2[0]*r, a1[1]*(1-r)+a2[1]*r, a1[2]*(1-r)+a2[2]*r]


######################################
# mathematische Routinen
######################################

class matrix3x3:
    "Wird zum losen linearer Systeme der Grobe 3 benutzt. \
    Parameter sind 3 Array mit je 3 Elementen, \
    die wichtigste Routine ist solve(Point)"
    def __init__(self,p1,p2,p3):
        self.p1 = p1
        self.p2 = p2
        self.p3 = p3
    def det(self):
	"Determinante nach der sarrusschen Regel"
        return \
            self.p1[0] * (self.p2[1] * self.p3[2] - self.p2[2] * self.p3[1]) \
            - self.p2[0] * (self.p1[1] * self.p3[2] - self.p3[1] * self.p1[2]) \
            + self.p3[0] * (self.p1[1] * self.p2[2] - self.p2[1] * self.p1[2])
    def t(self):
        h = self.p1[1]
        self.p1[1] = self.p2[0]
        self.p2[0] = h
        h = self.p1[2]
        self.p1[2] = self.p3[0]
        self.p3[0] = h
       	h = self.p2[2]
        self.p2[2] = self.p3[1]
       	self.p3[1] = h
        return self
    def write(self):
        print "[(" , self.p1[0] , ","  , self.p1[1] , "," , self.p1[2] , \
			") (" , self.p2[0] , ","  , self.p2[1] , "," , self.p2[2] , \
			") (" , self.p3[0] , ","  , self.p3[1] , "," , self.p3[2] ,  ")]"
        return self
    def solve(self,e):
        self.t()
        m = self.det()
        mx = matrix3x3(e, self.p2, self.p3)
        my = matrix3x3(self.p1, e, self.p3)
        mz = matrix3x3(self.p1, self.p2, e)
        erg = [0, 0, 0]
        if m != 0:
            erg = [mx.det()/m, my.det()/m, mz.det()/m]
        return erg

def printArray(v):
	print "[",
	for i in range(len(v)):
		print "%5.3f" % v[i],
	print "]",

def pointToArray(p1):
	return [p1.co.x, p1.co.y, p1.co.z]

def pointPrint(p1):
	return "[" + "%5.2f"%p1.co.x + "," + "%5.2f"%p1.co.y + "," + "%5.2f"%p1.co.z + "]"

def vecAdd(v1,v2):
	"subtraktion"
	return [v2[0]+v1[0], v2[1]+v1[1], v2[2]+v1[2]]

def vecSub(v1,v2):
	"subtraktion"
	return [v2[0]-v1[0], v2[1]-v1[1], v2[2]-v1[2]]
	
def scalarMul(v,a):
	"multiplikation mit einem Skalar"
	return [a*v[0], a*v[1], a*v[2]]

def propEdgeV(v1, v2, m):
	"Gibt die Verhaeltnisskoordinaten \
	 zwischen den beiden Punkten zurueck"
	return [v2[0]*m + v1[0]*(1-m), v2[1]*m + v1[1]*(1-m), v2[2]*m + v1[2]*(1-m)]

def dist(v1):
	"quadratische Norm"
	return math.sqrt(v1[0]*v1[0]+v1[1]*v1[1]+v1[2]*v1[2])

def norm(v1):
	"normalisierter Norm"
	d = dist(v1)
	if d == 0: d = 1
	return [v1[0]/d,v1[1]/d,v1[2]/d]

def scalarProd(v1,v2):
	"zwei 3-Arrays, es wird das Scalarprodukt berechnet"
	return v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2]

def crossProd(v1,v2):
	"zwei 3-Arrays, es wird das Kreuzprodukt berechnet"
	return [v1[1]*v2[2]-v1[2]*v2[1],v1[2]*v2[0]-v1[0]*v2[2],v1[0]*v2[1]-v1[1]*v2[0]]

def vecCos(v1,v2):
	"berechnet den Cosinus des Winkels zwischen zwei Vektoren"
	d1 = dist(v1)
	d2 = dist(v2)
	if d1 == 0:
		d1 = 1.0
	if d2 == 0:
		d2 = 1.0
	return scalarProd(v1,v2) / (d1 * d2)

def projPointV(k1,k2,pj):
	"Projektion von pj auf die durch k1,k2 aufgespannte Ebene \
	 Ergebniss ist der Punkt, die Verhaeltnisse, die Hoehe, \
	 und ein Flag, falls pj auf die Ebene projeziert wird"	 
	erg = True
	
	ec = crossProd(k1, k2)
	e =  norm(ec)
	m = matrix3x3(k1, k2, e)
	m.t()
	so =m.solve(pj)
	
	cx = k1[0]*(1-so[0]) + k2[0]*(1-so[1])
	cy = k1[1]*(1-so[0]) + k2[1]*(1-so[1])
	cz = k1[2]*(1-so[0]) + k2[2]*(1-so[1])
	rp = [cx, cy, cz]
	# Test, ob Punkt in der Ebene liegt
	if so[0] < 0 or so[1] < 0:
		erg = False
		
	return [rp,so[0],so[1],so[2],erg] 



def edgeProj(startPunkt, m, endPunkt):
	"Gibt den Projektionspunkt von m auf die Gerade |startPunkt, endPunkt|"
	p = vecSub(startPunkt, endPunkt)
	v = vecSub(startPunkt, m)
	d = dist(p)
	if d == 0:
		d = 1.0
	#return vecAdd(startPunkt, norm(p))
	return vecAdd(startPunkt, scalarMul(norm(p), scalarProd(p,v) / d))
	#return vecAdd(startPunkt, scalarMul(p, scalarProd(p,v) / dp))
	
	
def lineDir(me, v1, d1):
	p1 = NMesh.Vert(v1[0], v1[1], v1[2])
	v2 = vecAdd(v1, d1)
	p2 = NMesh.Vert(v2[0], v2[1], v2[2])
			
	me.verts.append(p1)
	me.verts.append(p2)
	me.addEdge(p1, p2)
			
###########################################
# Start Test
###########################################

me = 0
	
def startTest(vseg, useg, tension, size, mode=1, spline_mode = 1, mode_ende = 1):
	global me
	print "*** start ***"
	time_start = sys.time()
	Blender.Window.EditMode(0)
	
	if me == 0:
		scn = Scene.GetCurrent()
		ob = scn.objects.active
		me = ob.getData()
			
	dir = [0, 0, 0]
		
	allNodes = []
	# allCables enthlt die einzelnen Kabel, die Kabel wiederum 
	# sind eine Liste von Elementen mit folgenden Infos
	# 0. Koordinaten
	# 1. Distanz in Richtung d bis zum naechsten festen Gegenstand
	# 2. Art des Zieles (0 = unbekannt, 1 = edge, 2 = face)
	# 3. Zielobject
	# 4. Zielpunkt
	allCables = []
	
	kv = useg
	kw = vseg	
	radius = size
	
	for v in me.verts:
		if v.sel == 1 and allNodes.count(v) == 0:
			vc = getConnected(me, v)
			
			# Testen, ob Startpunkt
			# dazu darf nur ein einziger weiterer Punkt Nachbar markiert sein
			countSel = 0
			for vcc in vc:
				if vcc.sel == 1:
					countSel += 1
			
			# Ist Endpunkt, dann die markierten Punkte abgehen
			erg = []
			if countSel == 1:
				vv = v
				erg.append([pointToArray(vv),0,0,0,0])
				allNodes.append(v)
				b = True
				while b:
					b = False
					vc = getConnected(me, vv)
					for vcc in vc:
						if vcc.sel == 1 and allNodes.count(vcc) == 0 and not b:
							vv = vcc
							allNodes.append(vv)
							erg.append([pointToArray(vv),0,0,0,0])
							b = True
			if 1 < len(erg):
				allCables.append(erg)
				
	# Splining und des Kabels
	# und Physics
	bigb = True
	allCablesNew = []
	firstSpline = False
	if spline_mode == 2:
		firstSpline = True
		
	while bigb:
		print "Splining : %.2f"  % (sys.time() - time_start)
		bigb = False
		# Splining
		for cable in allCables:
			b = True
			doFirstSpline = firstSpline
			#b = False
			while b:
				b = False
				newCable = []
				newCable.append(cable[0])
				if doFirstSpline:
					# S-Spline start
					d = vecAdd(cable[0][0],scalarMul(vecSub(cable[0][0],cable[1][0]), 0.2))
					newCable.append([d,0,0,0,0])
					
				for j in range(1,len(cable)-1):
					if doFirstSpline:
						# S-Spline
						d1 = vecSub(cable[j][0],cable[j-1][0])
						d2 = vecSub(cable[j][0],cable[j+1][0])
						v1 = norm(d1)
						v2 = norm(d2)
						v1p = vecAdd(cable[j][0],scalarMul(vecSub(v2,v1), 0.2 * dist(d1)))
						v2p = vecAdd(cable[j][0],scalarMul(vecSub(v1,v2), 0.2 * dist(d2)))
							
						#lineDir(me, cable[j][0], scalarMul(vecSub(cable[j][0], v1p),1))
						#lineDir(me, cable[j][0], scalarMul(vecSub(cable[j][0], v2p),1))
						
						newCable.append([v1p,0,0,0,0])
						newCable.append([v2p,0,0,0,0])
						b = True
							
					else:
						v1 = vecSub(cable[j][0],cable[j-1][0])
						v2 = vecSub(cable[j][0],cable[j+1][0])
						vc = vecCos(v1,v2)
						d1 = dist(v1)
						d2 = dist(v2)
						dm = d1
						if d2 < dm:
							dm = d2
				
						# Unterteilung nach Winkel oder Distanz
						if dm < 0.02 and vc < -0.97:
							newCable.append(cable[j])
						else:
							b = True	
							newCable.append([vecAdd(cable[j][0], scalarMul(v1,tension)),0,0,0,0])
							newCable.append([vecAdd(cable[j][0], scalarMul(v2,tension)),0,0,0,0])
				
				if doFirstSpline:
					# S-Spline start
					d = vecAdd(cable[len(cable)-1][0],scalarMul(vecSub(cable[len(cable)-1][0],cable[len(cable)-2][0]), 0.2))
					newCable.append([d,0,0,0,0])
				newCable.append(cable[len(cable)-1])
				del cable[:]
				cable.extend(newCable)
				doFirstSpline = False	
			allCablesNew.append(cable)
			#allCables = allCablesNew
		firstSpline = False
		
		del allCables[:]
		for cable in allCablesNew:
			allCables.append(cable)
		del allCablesNew[:]
		
		if 0 < dist(dir):
			print "Physics 1 : %.2f"  % (sys.time() - time_start)
			# Physics 1, finden des Bodens
			for cable in allCables:
				# kreuzende Kanten finden
				newCable = []
				newCable.append(cable[0])
				for vi in range(len(cable)-1):
					erg = findAllEdges(me,cable[vi][0],cable[vi+1][0],dir)
					#print vi,
					#printArray(cable[vi][0]) 
					#print
					for vii in range(1,len(erg)-1):
						#print "   " , vii ,
						#printArray(erg[vii][1]) 
						#print 
						newCable.append([erg[vii][1],erg[vii][2],1,erg[vii][0],erg[vii][3]])
					
					newCable.append(cable[vi+1])
				
				# faces
				for v in newCable:
					if v[2] == 0:
						erg = findClosestFace(me, [v[0][0], v[0][1], v[0][2]], dir)
						if erg[0] != 0:
							v[2] = 2
							v[1] = erg[2]
							v[3] = erg[0]
							v[4] = erg[1]
						
				# Die neuen Punkte		
				for vi in range(len(newCable)):
					print vi, newCable[vi][2], "%.3f" % newCable[vi][1],
					printArray(newCable[vi][0])
					print
		
				allCablesNew.append(newCable)
			
			print len(allCablesNew)
			del allCables[:]
			for cable in allCablesNew:
				allCables.append(cable)
		
			print "Physics 2 : %.2f"  % (sys.time() - time_start)
			# Physics 2, Haengekurve
			for cable in allCables:
				for iv in range(len(cable)):
					v = cable[iv]
					if 0 < v[2]:
						test = []
						if 0 < iv:
							test.append(cable[iv-1][4])
						if iv < len(cable) - 1:
							test.append(cable[iv+1][4])	
						
						# Schraege des Punktes fuer den Restabstand bestimmen
						smw = 0
					
						for jk in test:
							m = vecSub(jk,v[4])
							w = abs(vecCos(m,dir))
						
							print "   w:",
							printArray(m)
							print "%.2f" % w
							if smw < w:
								smw = w
							
						sma = sqrt(1-smw*smw)
						if 0 < sma:
							smw = radius / sma
						else:
							smw = radius	
							
						print "m:",
						print "%.2f" % smw
								
						printArray(v[0])
						newKoor = vecAdd(v[0], scalarMul(dir,v[1]-smw))
						v[0] = newKoor
						printArray(v[0])
					
						print
				
	# surf enthaelt die endgueltigen Punkte der Oberflaeche
	
	print "Segmenting : %.2f"  % (sys.time() - time_start)
	for cable in allCables:	
		# Laenge des Kabels bestimmen 
		length = 0
		for j in range(len(cable)-1):
			length += dist(vecSub(cable[j][0],cable[j+1][0]))
		
		# Kabel neu Segmentieren
		parts = length / kw
		
		newCable = []
		newCable.append(cable[0])
		
		countSegs = 0
		partsum = 0
		for j in range(len(cable)-1):
			aktu = cable[j][0]
			b = True
			while b:
				b = False
				dr = vecSub(aktu,cable[j+1][0])
				d = dist(dr)
				if parts < partsum + d:
					#print countSegs, partsum
					countSegs += 1
					vh = (parts - partsum) / d
					aktu = vecAdd(aktu, scalarMul(dr,vh))
					newCable.append([aktu,cable[j+1][1],cable[j+1][2]])
					partsum = 0
					b = True	
			dr = vecSub(aktu,cable[j+1][0])
			partsum += dist(dr)
				
		if countSegs < kw:
			newCable.append(cable[len(cable)-1])		 
		del cable[:]
		cable.extend(newCable)
		
		print "make Cable : %.2f"  % (sys.time() - time_start)
		# Kabel Durchmesser
		wa = 0
		cosx = 0
		sinx = 0
		cosy = 0
		siny = 0
		cosz = 0
		sinz = 0
		surf = []
		for j in range(len(cable)):
			v1 = [0,0,0]
			v2 = [0,0,0]
			if 0 < j:
				v1 = vecSub(cable[j][0],cable[j-1][0])
			if j < len(cable)-1:
				v2 = vecSub(cable[j+1][0],cable[j][0])
			# vv = durchschnittliche Richtung an der Verbindung
			vv = norm(vecAdd(norm(v1),norm(v2)))
			#printArray(vv)
		
			oldcosx = cosx
			oldsinx = sinx
			oldcosy = cosy
			oldsiny = siny
			oldcosz = cosz
			oldsinz = sinz
			
			if mode == 1:
				absz = sqrt(vv[0]*vv[0]+vv[1]*vv[1])
				siny = vv[2]
				cosy = absz
				sinz = 0
				cosz = 1
				if 0 < absz:
					sinz = vv[1] / absz
					cosz = vv[0] / absz
				# Test Vorzeichenwechsel
				if (0.99 < (oldcosz * oldcosz + oldsinz * oldsinz)) and ((cosz * oldcosz + sinz * oldsinz) < -0.99):
					wa += pi
				abszs = cosz * oldcosz + sinz * oldsinz
				if (0.99 < (oldcosz * oldcosz + oldsinz * oldsinz)) and (abs(abszs) < 0.0001):
					if cosz > 0.999:
						if siny < 0:
							wa += 0.5 * pi
						else:
							wa += 1.5 * pi
					else:
						if siny < 0:
							wa += 1.5 * pi
						else:
							wa += 0.5 * pi
			elif mode == 2:
				absy = sqrt(vv[0]*vv[0]+vv[2]*vv[2])
				sinz = vv[1]
				cosz = absy
				siny = 0
				cosy = 1
				if 0 < absy:
					siny = vv[2] / absy
					cosy = vv[0] / absy
				# Test Vorzeichenwechsel
				if (0.99 < (oldcosy * oldcosy + oldsiny * oldsiny)) and ((cosy * oldcosy + siny * oldsiny) < -0.99):
					wa += pi
				absys = cosy * oldcosy + siny * oldsiny
				if (0.99 < (oldcosy * oldcosy + oldsiny * oldsiny)) and (abs(absys) < 0.0001):
					if cosy > 0.999:
						if sinz < 0:
							wa += 0.5 * pi
						else:
							wa += 1.5 * pi
					else:
						if sinz < 0:
							wa += 0.5 * pi
						else:
							wa += 1.5 * pi
			elif mode == 3:
				absx = sqrt(vv[2]*vv[2]+vv[1]*vv[1])
				cosz = vv[0]
				sinz = absx
				sinx = 0
				cosx = 1
				if 0 < absx:
					sinx = vv[2] / absx
					cosx = vv[1] / absx
				# Test Vorzeichenwechsel
				if (0.99 < (oldcosx * oldcosx + oldsinx * oldsinx)) and ((cosx * oldcosx + sinx * oldsinx) < -0.99):
					wa += pi
				#absys = cosy * oldcosy + siny * oldsiny
				#if (0.99 < (oldcosy * oldcosy + oldsiny * oldsiny)) and (abs(absys) < 0.0001):
				#	if cosy > 0.999:
				#		if sinz < 0:
				#			wa += 0.5 * pi
				#		else:
				#			wa += 1.5 * pi
				#	else:
				#		if sinz < 0:
				#			wa += 0.5 * pi
				#		else:
				#			wa += 1.5 * pi
			
			# print "%5.2f"%cosx, "%5.2f"%sinx, "%5.2f"%cosy, "%5.2f"%siny, "%5.2f"%cosz, "%5.2f"%sinz, "%5.2f"%wa	
			
			surf1 = []
			for ww in range(kv):
				w = (2 * ww * pi) / kv
				cw = cos(w + wa)
				sw = sin(w + wa)
				d = [0,0,0]
				if mode == 1:
					d[0] = -cosz*siny*sw - sinz*cw
					d[1] = -sinz*siny*sw + cosz*cw
					d[2] = cosy*sw
				elif mode == 2:
					d[0] = -cosy*sinz*cw - siny*sw
					d[1] = cosz*cw
					d[2] = -siny*sinz*cw + cosy*sw	
				elif mode == 3:
					d[0] = - sinz*cw
					d[1] = cosx*cosz*cw - sinx*sw
					d[2] = sinx*cosz*cw + cosx*sw	
					
				dd = scalarMul(d, radius)
						
				#p1 = NMesh.Vert(cable[j][0], cable[j][1], cable[j][2])
				p2 = NMesh.Vert(cable[j][0][0] + dd[0], cable[j][0][1] + dd[1], cable[j][0][2] + dd[2])
			
				#me.verts.append(p1)
				me.verts.append(p2)
				#me.addEdge(p1, p2)
				surf1.append(p2)
				
			surf.append(surf1)
				
		# spline darstellen		
		#erg = []		
		#for v in cable:
		#	pp = NMesh.Vert(v[0][0], v[0][1], v[0][2])
		#	me.verts.append(pp)
		#	erg.append(pp)
		#for i in range(len(erg)-1):
		#	me.addEdge(erg[i], erg[i+1])
		
		#print "endMode" , mode_ende, mode_ende - 2
		# Anpassen der letzten Elemente an die zugehoerige Ebene
		if mode_ende == 2 or mode_ende == 3:  
			
			mAdapt = [[0,1,0],[len(surf)-1,len(surf)-2,len(surf)-1]]
			if mode_ende == 3:
				# Anfangs und End-Kante hinzufuegen 
				newSurf = []
				surfm = []
				for i in range(kv):
					p = NMesh.Vert(surf[0][i].co.x, surf[0][i].co.y, surf[0][i].co.z)
					me.verts.append(p)
					surfm.append(p)
				newSurf.append(surfm)
		
				newSurf.extend(surf)		
				surfm = []
				e = len(surf)-1
				for i in range(kv):
					p = NMesh.Vert(surf[e][i].co.x, surf[e][i].co.y, surf[e][i].co.z)
					me.verts.append(p)
					surfm.append(p)
				newSurf.append(surfm)
			
				del surf[:]
				surf.extend(newSurf)
				mAdapt = [[1,2,0],[len(surf)-2,len(surf)-3,len(surf)-1]]
				
			if mode_ende == 3:
				# Anfangs und End-Kante verlaengern
				pAdapt = [[0,1,0],[len(surf)-1,len(surf)-2,len(cable)-1]]
				for pA in pAdapt:
					middlePoint = cable[pA[2]][0]
					for i in range(kv):
						print middlePoint, pointToArray(surf[pA[1]][i])
						d = vecSub(middlePoint, pointToArray(surf[pA[1]][i]))
						d = vecAdd(middlePoint, scalarMul(d,2))
						surf[pA[0]][i].co.x = d[0]
						surf[pA[0]][i].co.y = d[1]
						surf[pA[0]][i].co.z = d[2]
			
			for mA in mAdapt:
				endIndex = mA[0]
				startIndex = mA[1]
				#print endIndex, startIndex
				for i in range(kv):
					p1 = surf[endIndex][i]
					p2 = surf[startIndex][i]
					p1a = pointToArray(p1)
					p2a = pointToArray(p2)
					d = vecSub(p2,p1)
					a = findClosestFace(me, p2a, d)
					p1.co.x = a[1][0]
					p1.co.y = a[1][1]
					p1.co.z = a[1][2]
					if mode_ende == 3:
						pIndex = mA[2]
						p3 = surf[pIndex][i]
						p3a = pointToArray(p3)
						a = findClosestFace(me, p3a, d)
						p3.co.x = a[1][0]
						p3.co.y = a[1][1]
						p3.co.z = a[1][2]
						
					#lineDir(me, p2, scalarMul(d,2))
					
				
				
		for i1 in range(len(surf)-1):
			for i2 in range(kv):
				i2p = (i2+1) % kv
				
				ff = NMesh.Face()
				ff.v.append(surf[i1][i2])
				ff.v.append(surf[i1+1][i2])
				ff.v.append(surf[i1+1][i2p])
				ff.v.append(surf[i1][i2p])
				me.addFace(ff)	 
						
	me.update()
	Blender.Window.EditMode(1)
	me = 0
	print "finished : %.2f"  % (sys.time() - time_start)


#Draw.Register 
Register(draw, event, bevent)