Script to create new vertices on shared coordinate edges?

[chroma123]

We are processing loads of CAD geometry from ArchiCAD, but are struggling with the same errors from ArchiCAD all the time, which we need to address to be able to use other tools. The real solution would be to weld vertices that shares coordinates automatically, as there is open geometry all over the place. However, it isn't that easy, because there are also edges sharing coordinates where one has a vertex while the other doesn't have. (see image for visual explanation)

In this image, I have moved one of the vertices down a bit just to show that the shared edge doesn't have a vertex, which means I won't be able to complete/weld this geometry easily without creating a new vertex on the edge that is missing a vertex, and then target weld it to that existing vertex. Welding is of course not a problem to do, but how can I create those new vertices with maxscript? Hopefully some guru out there knows the answer!

[senorpablo]

I've done something similar in one of my tools, it's not a trivial task. There is no built in method to do it so it requires   custom math functions.

Every edge edge must be tested against every vertex to see if they lie along and within an edge, and then use the built in function to add vertices along that edge based on the distances. 

[klvnk]

is the vert at the other end always shared/welded ? and are there mapping channels to deal with ?

[chroma123]

I am not sure about mapping coords, actually, but I wonder if there are some options in the export from archicad. No mapping channels applied in max at this point. Specifically we use this type of geometry to create cladding with a custom script, but the base mesh from archicad sucks so much. I came to the conclusion that closing the geometry fixes the problem, but cannot do that without adding vertices on the edges that is missing one. Do you think mapping could fix it somehow? 

The other vertex in such cases seems to be shared but not welded. 

[chroma123]

Makes sense. But distance. Wouldn't the problem be that these edges has different lengths? Hm. What if just save one vertex coordinate, and check all edges if they have eighter x, y or z placed on along this coordinate, and if yes then add vertex. And then off to the next vertex and same procedure, and then at the end, welding.

Let's say that it is the "check all edges if they have eighter x, y or z placed on along this coordinate" part that gets me stuck with this option, because how do you check if an exact vertex position exist on a whole edge? 

[klvnk]

---

---

The other vertex in such cases seems to be shared but not welded.

so you don't have this going on ?



don't think mapping helps it was just something that could have to be dealt with

---

[klvnk]

perhaps something like this can find the them (assuming theres always a shared welded vert)

fn get_tjunction poly epsilon =
(
	polyop.setVertSelection poly #{}; -- illustration 
	polyop.setEdgeSelection poly #{};
	
	open_edgs = polyop.getopenEdges poly;
	open_verts = polyop.getvertsUsingEdge poly open_edgs;	
	
	for v in open_verts do
	(
		vedges = polyop.getEdgesUsingVert poly v;	
		openvedges = for ve in vedges where open_edgs[ve] == true collect ve;	
		
		if openvedges.count == 2 then -- does an open "used" vert always have 2 edges ?
		(	
			edgeverts = polyop.getEdgeVerts poly openvedges[1];
			end_v1 = if edgeverts[1] == v then  edgeverts[2] else edgeverts[1];
			
			edgeverts = polyop.getEdgeVerts poly openvedges[2];
			end_v2 = if edgeverts[1] == v then  edgeverts[2] else edgeverts[1];
				
			a = polyop.getvert poly v;
			ab = (polyop.getvert poly end_v1) - a;
			ac = (polyop.getvert poly end_v2) - a;
			
			d = dot (normalize ab) (normalize ac);

			if	d > 1.0 - epsilon then
			(	
				tvert = end_v1;
				insert_edge = openvedges[1];
				if length ab > length ac then
				(
					tvert = end_v2;
					insert_egde = openvedges[2];
				)
				
				vsel = polyop.getVertSelection poly;
				vsel[tvert] = true;
				polyop.setVertSelection poly vsel;
					
				esel = polyop.getEdgeSelection poly;
				esel[insert_edge] = true;
				polyop.setEdgeSelection poly esel;	
			)
		)	
	)
)

get_tjunction $ 0.0001;

[Serejah]

There's always a hope!

But can't say if I'm able to release it anytime soon...

[chroma123]

YES! Exactly like that, only in an automatic under-the-hood operation. Looks like you've done quite a bit work to achieve this though, since you put the effort to create a new modifier. Am I right? If you are thinking about commercializing it, I won't ask you for how you did it, but otherwise; can you share some insight on how you did it?

[chroma123]

Thanks for the script snippet @klvnk, but it didn't do anything, at least to my edges and vertices.

[Serejah]

Actually there's not much to add to senorpablo's answer.
In worst case scenario OpenVertsCount * OpenEdgesCount operations have to be made to find all 'missing' vertex positions. It's not optimal and is slow on high poly meshes.

Pseudocode of what's under the hood:

obj               = $
radius            = 1.0
open_edge_indexes = polyop.getOpenEdges obj
open_vert_indexes = polyop.getVertsUsingEdge obj open_edge_indexes
edges_to_divide = #()
edges_to_divide_indexes = #{}

for v in open_vert_indexes do
(
	pt  = polyop.getVert obj v	
		
	for index in open_edge_indexes where PointSegmentDistance pt obj index <= radius do
	(
		ev = polyop.getEdgeVerts obj
		v1 = polyop.getVert obj ev[1]
		v2 = polyop.getVert obj ev[2]
		
		proj_pt = ProjectPointOnSegment pt v1 v2
		
		if PointsBelongsToSegment proj_pt v1 v2 do
		(
			fraction = distance v1 proj_pt / distance v1 v2			
			append edges_to_divide #( index, fraction )
			
			edges_to_divide_indexes[ index ] = true 
		)
	)
	
)


edges_with_fractions = for i in edges_to_divide_indexes collect
(
	all_fractions_of_edge = for item in edges_to_divide where item[1] == i collect item[2]
	sort all_fractions_of_edge
	
	DataPair edge_index:i fractions:all_fractions_of_edge
)

qsort edges_with_fractions SortByEdgeIndexHighToLow

for item in edges_with_fractions do
(
	DividePolyEdge obj item.edge_index item.fractions
)

[chroma123]

Wow. I am impressed by the level of this forum, and grateful for the detail of sharing. Thank you so much. The script does kinda make sense to me, but when tested straight out on a mesh, I get an error, allegedly Call needs function or class, got undefined, somewhere in "for index in open_edge_indexes where PointSegmentDistance pt obj index <= radius do".

I am eager to dive deeper into this, but first I need to understand what's undefined. Perhaps the pt = polyop.getVert obj v  failed. My geometry is editable poly, and it is selected, so no need to be undefined, me thinks. 😄 Probably the answer is embarrassingly easy.

[Serejah]

Pseudocode is just a description of how the thing works. It's not a real script so it won't work.

[chroma123]

... Like I said. Embarrasingly simple. 😀

[denisT.MaxDoctor]

my algorithm is almost identical to the Serejah's:

fn distanceToSegment p A B &param: &dist: =
(
	v = B - A
	param = dot v (p - A) / dot v v
	proj = A + v * param
	
	dist = distance p proj
	
	if (param < 0) then distance p A else if (param > 1) then distance p B else dist
)
fn getPolyEdgeParamPoint poly edge param = 
(
	vv = polyop.getEdgeVerts poly edge
	v1 = polyop.getVert poly vv[1]
	v2 = polyop.getVert poly vv[2]
	
	v1 * (1 - param) + v2 * param
)	

fn dividePolyEdgeAt poly edge point = 
(
	vv = polyop.getEdgeVerts poly edge
	v1 = polyop.getVert poly vv[1]
	v2 = polyop.getVert poly vv[2]
	
	param = distance v1 point / distance v1 v2
	polyop.divideEdge poly edge param
)	

fn multiDividePolyEdge poly edge params = 
(
	sort params

	points = for param in params collect (getPolyEdgeParamPoint poly edge param)
	new_verts = #()
	nume = poly.edges.count
	for point in points do 
	(
		v = dividePolyEdgeAt poly edge point
		if (v > 0) do
		(
			nume += 1
			edge = nume
			
			append new_verts v
		)
	)
	new_verts
)

fn weldClosePolyEdges poly threshold:0.5 weld:on select:on =
(
	if threshold != unsupplied then poly.weldThreshold = threshold else threshold = poly.weldThreshold

	open_ee = polyop.getOpenEdges poly
	open_vv = polyop.getVertsUsingEdge poly open_ee

	ee_table = #()
	weld_vv = #{}

	getvertpos = polyop.getVert
	getvertedges = polyop.getEdgesUsingVert 
	getedgeverts = polyop.getEdgeVerts 
	
	for v in open_vv do
	(
		pt = getvertpos poly v	
		ee = getvertedges poly v  
		
		found = off
		
		for e in open_ee while not found where not ee[e] do
		(
			vv = getedgeverts poly e
			v1 = getvertpos poly vv[1]
			v2 = getvertpos poly vv[2]

			distanceToSegment pt v1 v2 param:&p dist:&d
			if (found = (p > 0 and p < 1 and d < threshold)) do
			(
				if ee_table[e] == undefined do ee_table[e] = #()
				append ee_table[e] p

				append weld_vv v
			)
		)
	)

	for e=1 to ee_table.count where (params = ee_table[e]) != undefined do
	(
		vv = multiDividePolyEdge poly e params
		if vv.count > 0 do join weld_vv (tobits vv)
	)
	
	if select do poly.selectedverts = weld_vv
	
	if weld do polyop.weldVertsByThreshold poly weld_vv
		
	ok
)

a test scene:

delete objects
(
	p0 = plane width:30 length:10 pos:[-4,0,10.1] dir:y_axis wirecolor:yellow
	p1 = plane width:20 length:10 pos:[0,0,0] dir:y_axis wirecolor:orange
	p2 = plane width:40 length:10 pos:[3.5,0,-10.1] dir:y_axis wirecolor:brown

	converttopoly p0
	polyop.attach p0 p1
	polyop.attach p0 p2

	polyop.deletefaces p0 #{17, 20, 30..31}
	update p0
	p0.vertexticks = on
	select p0
)

the using:

weldClosePolyEdges $ threshold:0.2 weld:off select:on -- or use weld ON

[denisT.MaxDoctor]

hmm... it looks like multiDividePolyEdge method needs to be reviewed. 

[denisT.MaxDoctor · Accepted solution]

line:

if vv.count > 0 do join weld_vv (tobits vv)

must be changed to:

if vv.count > 0 do join weld_vv (vv as bitarray)

tobits is my function. we should use the built-in one (as bitarray) 

[chroma123]

Holy how. It works. Thank you so much. The concept is kind of simple, but in the reality it seems not quite so. I am taking a closer look at this script to understand all of it's nature. 🙂 Thanks again! This should be implemented as a base functionality in 3ds max. Hopefully it's already covered in one of the remesh functions that was mentioned in the beta/roadmap, but if not... @brentscannell?

[denisT.MaxDoctor]

The biggest problem with the above algorithm is its performance. For high poly objects with a lot of open edges, this will be slow. The only algorithmic solution I see is using an R-Tree ... but that's not for this topic.

Another small improvement we can make is to change the line:

ee = getvertedges poly v

and exclude all edges of surrounded faces for a processing vertex.

[Anonymous]

whoa, super interested in this!