#!BPY

"""
Name: 'Compute Edge Intersection'
Blender: 248
Group: 'Mesh'
Tooltip: 'Select 2 edges, then run this script.'
"""

__author__ = "FourMadMen.com (FourMadMen)"
__url__ = ["Script's homepage, http://www.fourmadmen.com/blender/scripts/4mm_edge_intersection.html", "http://wiki.blender.org/index.php/Extensions:Py/Scripts/Manual/Mesh/4mm_edge_intersection", "elysiun"]
__version__ = "1.1 2005/08/14"

__bpydoc__ = """\
This script will compute the intersection of two intersecting edges or if the selected edges 
don't intersect will create a new edge that represents the shortest distance between them.

The possible outcomes of running this script are as follows:

1)  If the edges intersect, the user is asked if they wish to Subdivide Edges.
	a)  If "Yes", then a new vertex is created and the effected edges 
	    are subdivided (effected faces are removed leaving the user to fill 
	    as desired).
	b)  If "No", then only a new vertex is created.
	c)  If "Cancel", then script terminates

2)  If the edges do not intersect, the script will attempt to determine the
    shortest distance between the selected edges and create a new edge.

3)  There are some conditions where #1 and #2 are not possible.  In this case the 
    script will terminate after informing the user that it can not proceed.
    For example:  If the selected edges share a vertex or a face the computation can not proceed.

Usage:<br>
  From edit mode, select two edges and run this script.
  Script link is under Script -> Mesh -> Computer Edge Intersection
"""

# --------------------------------------------------------------------------
# $Id: 4mm_edge_intersection.py,v 1.1 2005/08/14 00:45:00
# --------------------------------------------------------------------------
#
# --------------------------------------------------------------------------
# Compute Edge Intersection v1.1
# by FourMadMen, 2005
# This script is protected by the GPL: Gnu Public Licence
# GPL - http://www.gnu.org/copyleft/gpl.html
# --------------------------------------------------------------------------
# ***** 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 *****
# --------------------------------------------------------------------------

#Press Alt-P to run

import Blender
from Blender import NMesh, Window, Draw, Object

SELECTED_EDGE = NMesh.EdgeFlags['SELECT']
Epsilon = 0.00001

def message(msg):
	Draw.PupMenu(msg)
#end message

def process(me):
	selected = []
	for v in me.verts:
		if v.sel == 1:
			selected.append(v)
	
	if me.edges == None: me.addEdgesData()
	
	edgeOps = 0
	ctr = 0
	
	for e in me.edges:
		if e.v1 in selected and e.v2 in selected:
			if ctr == 0:
				e1v1 = e.v1
				p1_x = e.v1.co[0]
				p1_y = e.v1.co[1]
				p1_z = e.v1.co[2]
				
				e1v2 = e.v2
				p2_x = e.v2.co[0]
				p2_y = e.v2.co[1]
				p2_z = e.v2.co[2]
				
				ctr+=1
			elif ctr == 1:
				e2v1 = e.v1
				p3_x = e.v1.co[0]
				p3_y = e.v1.co[1]
				p3_z = e.v1.co[2]
				
				e2v2 = e.v2
				p4_x = e.v2.co[0]
				p4_y = e.v2.co[1]
				p4_z = e.v2.co[2]
				
				ctr+=1
	
	if ctr != 2: 
		message('Must select exactly two edges')
		return
		
	p13_x = p1_x - p3_x
	p13_y = p1_y - p3_y
	p13_z = p1_z - p3_z
	p43_x = p4_x - p3_x
	p43_y = p4_y - p3_y
	p43_z = p4_z - p3_z
	
	if abs(p43_x)<Epsilon and abs(p43_y)<Epsilon and abs(p43_z)<Epsilon:
		message('Edges do not intersect')
		return

	p21_x = p2_x - p1_x
	p21_y = p2_y - p1_y
	p21_z = p2_z - p1_z
	
	if abs(p21_x)<Epsilon and abs(p21_y)<Epsilon and abs(p21_z)<Epsilon:
		message('Edges do not intersect')
		return

	d1343 = p13_x * p43_x + p13_y * p43_y + p13_z * p43_z
	d4321 = p43_x * p21_x + p43_y * p21_y + p43_z * p21_z
	d1321 = p13_x * p21_x + p13_y * p21_y + p13_z * p21_z
	d4343 = p43_x * p43_x + p43_y * p43_y + p43_z * p43_z
	d2121 = p21_x * p21_x + p21_y * p21_y + p21_z * p21_z
	
	denom = d2121 * d4343 - d4321 * d4321
	if abs(denom)<Epsilon:
		message('Edges do not intersect')
		return
	
	numer = d1343 * d4321 - d1321 * d4343
	
	mua = numer / denom;
	mub = (d1343 + d4321 * (mua)) / d4343
	
	pa_x = p1_x + mua * p21_x;
	pa_y = p1_y + mua * p21_y;
	pa_z = p1_z + mua * p21_z;
	pb_x = p3_x + mub * p43_x;
	pb_y = p3_y + mub * p43_y;
	pb_z = p3_z + mub * p43_z;
	
	print 'New Vertex Data:'
	print round(pa_x,3)
	print round(pa_y,3)
	print round(pa_z,3)
	print round(pb_x,3)
	print round(pb_y,3)
	print round(pb_z,3)
	
	nv1 = NMesh.Vert(pa_x, pa_y, pa_z)
	nv2 = NMesh.Vert(pb_x, pb_y, pb_z)
		
	for v in me.verts:
		if v.sel == 1: v.sel = 0
	
	if abs(nv1.co[0]-nv2.co[0])<Epsilon and abs(nv1.co[1]-nv2.co[1])<Epsilon and abs(nv1.co[2]-nv2.co[2])<Epsilon:
		for v in selected:
			if abs(nv1.co[0]-v[0])<Epsilon and abs(nv1.co[1]-v[1])<Epsilon and abs(nv1.co[2]-v[2])<Epsilon:
				message('Edges share a vertex or do not intersect and they share a face')
				return
		
		print 'add vert'
		nv1.sel = 1
		me.verts.append(nv1)
		
		stitch = Draw.PupMenu('Subdivide Edges?%t|Yes (will remove effected faces)|No|Cancel')
		if stitch == 3 or stitch<0: return

		#   Removes selected edges and stitches new vert to orginal vertex selections
		#   TODO: Face Filling (?)
		if stitch==1:
			me.removeEdge(e1v1, e1v2)
			me.removeEdge(e2v1, e2v2)
			me.addEdge(nv1, e1v1)
			me.addEdge(nv1, e1v2)
			me.addEdge(nv1, e2v1)
			me.addEdge(nv1, e2v2)
			edgeOps = 1
	else:
		print 'add edge'
		edgeOps = 1
		
		me.verts.append(nv1)
		me.verts.append(nv2)
		me.addEdge(nv1, nv2)
	
	# after calling addEdge the ending vertex seletions 
	# are not as expected (hurm).
	if edgeOps:
		me.update(store_edges=1)
	else:
		me.update(store_edges=0)
	
#end process

#main
is_editmode = Window.EditMode()
if is_editmode:	Window.EditMode(0)

mesh = None
if len(Object.GetSelected()) > 0:
	object = Object.GetSelected()[0]
	
	if object.getType() == 'Mesh':
		mesh = Object.GetSelected()[0].getData()
	else:
		message('Selected object is not a Mesh')
else:
	message('No object selected.')			

if mesh != None:
	process(mesh)
	Window.EditMode(1)
	
#end main
