developing a script from start to finish

I was asked by a member of the BlenderArtist community to write a script that can intersect all selected edges. So here i'll stick my development notes / code. More code less talk.

p4

	import bpy
	import bmesh
	obj = bpy.context.active_object
	bm = bmesh.from_edit_mesh(obj.data)
	selected_edges = [edge for edge in bm.edges if edge.select]
	count_edges = len(selected_edges)
	edge_indices = [i.index for i in selected_edges]
	print('num edges selected: {}'.format(count_edges))
	print('edge indices: {}'.format(edge_indices))
	for edge in selected_edges:
	print('edge index: {}'.format(edge.index), end=' / ')
	print('vert indices: ', (edge.verts[0].index, edge.verts[1].index))
	'''
	- we need to go through all permutations of the selected indices.
	- we can dismiss the possibility of intersection between two edges
	if the edge shares a vertex index.
	edge_indices might look like [1,2,10,11]
	'''
	import itertools
	raw_permutations = itertools.permutations(edge_indices, 2)
	# we should remove duplicates from the raw_permutations
	permutations = [result for result in raw_permutations if result[0] < result[1]]
	print(permutations)
	# result : [(1, 2), (1, 10), (1, 11), (2, 10), (2, 11), (10, 11)]
	'''
	with unique permutations left we can remove combinations that share a vertex
	'''
	print("---")
	final_permutations = []
	for edge in permutations:
	edge_index_1 = edge[0]
	edge_index_2 = edge[1]
	v_idx_1 = bm.edges[edge_index_1].verts[0].index
	v_idx_2 = bm.edges[edge_index_1].verts[1].index
	v_idx_3 = bm.edges[edge_index_2].verts[0].index
	v_idx_4 = bm.edges[edge_index_2].verts[1].index
	# this displays the vertex indices of the verts on the two edges
	raw_vert_indices = v_idx_1, v_idx_2, v_idx_3, v_idx_4
	print(edge, ' -> ', raw_vert_indices)
	# if we do a set() on this collection, and the size of the set becomes
	# smaller then we know there is a duplicate and can disguard this edge combo.
	if len(set(raw_vert_indices)) < len(raw_vert_indices):
	continue
	final_permutations.append(edge)
	print('\n>', final_permutations)

view raw part4.py hosted with ❤ by GitHub

The above code is hardly involved, but without it the next part isn't possible. The task is now to go through the remaining combinations -- stored as tuples -- and for every tuple that results in a valid intersection we store the tuple with the coordinate of the intersection. Something like (edge1, edge2, intersection_coordinate).

Then the theoretically easy, but practically more demanding, part is to add extra vertices to the edges that have an intersection. I think this is where I drew a blank last time I thought about this problem.

p5+6

if you are trying to follow along, the scene used to test this looks like this.
It appears that parallel lines can return the tuple (Vector((nan, nan, nan)), Vector((nan, nan, nan))) or None. At this stage of the development the script looks like this (fully commented) and i'm testing with this .blend to debug. It prints out the coordinates of all proper intersections found.

[(1, 2), (1, 10), (1, 11), (2, 10), (2, 11), (10, 11)]
---
(1, 2)  ->  (1, 0, 2, 1)
(1, 10)  ->  (1, 0, 6, 4)
(1, 11)  ->  (1, 0, 12, 10)
(2, 10)  ->  (2, 1, 6, 4)
(2, 11)  ->  (2, 1, 12, 10)
(10, 11)  ->  (6, 4, 12, 10)

> [(1, 10), (1, 11), (2, 10), (2, 11), (10, 11)]
[((1, 10), (Vector((3.1274282932281494, 3.220184564590454, -1.0)), 
            Vector((3.1274282932281494, 3.220184564590454, -1.0)))), 
((1, 11), (Vector((3.027259588241577, 3.220184564590454, -1.0)), 
           Vector((3.027259588241577, 3.220184564590454, -1.0)
)))]
number of intersections: 2

As it turns out, this .blend is not a reasonable representation of a real world example.
The coordinates of the expected intersections will be used to chop each edge. I think recursion would be an elegant solution, but it can be tricky to debug. Perhaps check each found intersection against every selected edge, and create list of tuples (edge_index, intersections_on_this_edge)

, from this list pick one point/vertex of the edge amd arrange the intersections_on_this_edge with respect to that point. Then create a new temporary edge geometry list, then delete all selected edges and build new edges from the temo list -- even if the edge didn't have any intersections ( algorithmically simpler). bam. then select all newly create geometry and remove doubles.

last part

I ended up with this

	import bpy
	import bmesh
	from mathutils import Vector
	from mathutils.geometry import intersect_line_line as LineIntersect
	import itertools
	from collections import defaultdict
	VTX_PRECISION = 1.0e-5 # Epsilon. or 1.0e-6 ..if you need
	VTX_DOUBLES_THRSHLD = 0.0001
	obj = bpy.context.active_object
	if obj.mode == "EDIT":
	bm = bmesh.from_edit_mesh(obj.data)
	''' helpers '''
	# returns distance between two given points
	def mDist(A, B): return (A-B).length
	def isPointOnEdge(point, A, B):
	''' returns True / False if a point happens to lie on an edge '''
	eps = ((mDist(A, B) - mDist(point,B)) - mDist(A,point))
	if abs(eps) < VTX_PRECISION: return True
	else:
	print('distance is ' + str(eps))
	return False
	def CountPointOnEdges(point, edges):
	''' returns the number of edges that a point lies on. '''
	v1, v2, v3, v4 = edges
	count = 0
	if(isPointOnEdge(point, v1, v2)): count+=1
	if(isPointOnEdge(point, v3, v4)): count+=1
	return count
	def vertex_indices_from_edges_tuple(edge):
	''' find the vertex indices of a 2-tuple of edges '''
	k = lambda v, w: bm.edges[edge[v]].verts[w].index
	return [k(i>>1, i%2)for i in range(4)]
	def vector_from_indices(raw_vert_indices):
	return [bm.verts[i].co for i in raw_vert_indices]
	def order_points(edge, point_list):
	''' - order these edges from distance to v1,
	- then sandwhich the sorted list with v1, v2
	'''
	v1, v2 = edge
	dist = lambda co: (v1-co).length
	point_list = sorted(point_list, key=dist)
	point_list.insert(0, v1)
	point_list.append(v2)
	print(point_list)
	return point_list
	def remove_permutations_that_share_a_vertex(permutations):
	''' Get useful Permutations '''
	final_permutations = []
	for edges in permutations:
	# this displays the vertex indices of the verts on the two edges
	raw_vert_indices = vertex_indices_from_edges_tuple(edges)
	print(edges, ' -> ', raw_vert_indices)
	# check shared indices
	if len(set(raw_vert_indices)) < len(raw_vert_indices):
	continue
	final_permutations.append(edges)
	# print('\n>', final_permutations)
	return final_permutations
	def get_unique_intersections(final_permutations):
	''' Enumerate all intersections found in the selection '''
	intersections = []
	for edges in final_permutations:
	raw_vert_indices = vertex_indices_from_edges_tuple(edges)
	vert_vectors = vector_from_indices(raw_vert_indices)
	# Returns a tuple with the points on each line respectively closest to the other.
	closest_points = LineIntersect(*vert_vectors)
	# closest_points may be
	# (Vector((nan, nan, nan)), Vector((nan, nan, nan))) or None
	# Whatever the reason (parallel, not coplanar), this response
	# is used to drop combinations from the permutations list
	if not closest_points: continue
	if not isinstance(closest_points[0].x, float): continue
	# count how many edges this closest_points[0] lies on, if <2, skip on.
	test_point_1, test_point_2 = closest_points
	if CountPointOnEdges(test_point_1, vert_vectors) < 2: continue
	# only valid vector tuples should reach this point.
	distance = (test_point_1 - test_point_2).length
	# the edges intersect if the distance is lower than (epsilon precision)
	if distance < VTX_PRECISION:
	if not test_point_1 in intersections:
	intersections.append(test_point_1)
	print('intersections: ', intersections)
	num_intersections = len(intersections)
	print('number of intersections: {}'.format(num_intersections))
	return intersections
	def dictify_edge_with_sorted_pointlists(intersections, edge_indices):
	''' Combine all selected edges with the intersections found on those edges '''
	d = defaultdict(list)
	origin = Vector((0,0,0))
	for edge in edge_indices:
	tv1, tv2 = bm.edges[edge].verts
	v1 = bm.verts[tv1.index].co
	v2 = bm.verts[tv2.index].co
	print(edge, ': ', tv1.index, tv2.index)
	unordered_points = []
	for point in intersections:
	vr1, vr2 = LineIntersect(origin, point, v1, v2)
	pdist = (vr1-vr2).length
	if pdist < VTX_PRECISION and isPointOnEdge(point, v1, v2):
	unordered_points.append(point)
	print(point, pdist)
	ordered_points = order_points((v1,v2), unordered_points)
	d[edge].extend(ordered_points)
	print(d)
	return d
	def update_mesh(obj, d):
	''' Make new geometry (delete old first) '''
	bpy.ops.mesh.delete(type='EDGE')
	bpy.ops.object.editmode_toggle()
	oe = obj.data.edges
	ov = obj.data.vertices
	vert_count = len(ov)
	edge_count = len(oe)
	for old_edge, point_list in d.items():
	num_points = len(point_list)
	num_edges_to_add = num_points-1
	for i in range(num_edges_to_add):
	oe.add(1)
	ov.add(2)
	ov[vert_count].co = point_list[i]
	ov[vert_count+1].co = point_list[i+1]
	oe[edge_count].vertices = [vert_count, vert_count+1]
	vert_count = len(ov)
	edge_count = len(oe)
	# set edit mode
	bpy.ops.object.editmode_toggle()
	bpy.ops.mesh.remove_doubles(threshold=VTX_DOUBLES_THRSHLD, use_unselected=False)
	if obj.mode == "EDIT":
	selected_edges = [edge for edge in bm.edges if edge.select]
	count_edges = len(selected_edges)
	# edge_indices might look like [1,2,10,11]
	edge_indices = [i.index for i in selected_edges]
	# get all permutations, then remove duplicates (1,3 <==> 3,1)
	raw_permutations = itertools.permutations(edge_indices, 2)
	permutations = [result for result in raw_permutations if result[0] < result[1]]
	final_permutations = remove_permutations_that_share_a_vertex(permutations)
	intersections = get_unique_intersections(final_permutations)
	d = dictify_edge_with_sorted_pointlists(intersections, edge_indices)
	update_mesh(obj, d)
	else:
	print('must be in edit mode')

view raw part16.py hosted with ❤ by GitHub

testing the algorithm

To the best of my knowledge these steps are the core of the algorithm. I have intentionally not implemented the bmesh way of adding geometry to the mesh yet. For now I can focus on trying to break the algorithm. Once I am confident about the accuracy I will refactor.

refactor

after some time, and some testing by several users i'm happy the core algorithm does as intended. Also wrapped some addon boilerplate code around it to turn it into an addon for convenience. Find the addon here ... found a small bug, must deselect edges that aren't intersected by any other edges (or duplicate it)