topic Re: Script to create new vertices on shared coordinate edges? in 3ds Max Programming Forum

Script to create new vertices on shared coordinate edges?

chroma123 — Thu, 17 Sep 2020 09:07:07 GMT

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!

Re: Script to create new vertices on shared coordinate edges?

senorpablo — Sat, 19 Sep 2020 01:02:09 GMT

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.

Re: Script to create new vertices on shared coordinate edges?

klvnk — Sat, 19 Sep 2020 06:42:54 GMT

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

Re: Script to create new vertices on shared coordinate edges?

chroma123 — Sat, 19 Sep 2020 07:03:41 GMT

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.

Re: Script to create new vertices on shared coordinate edges?

chroma123 — Sat, 19 Sep 2020 07:15:04 GMT

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?

Re: Script to create new vertices on shared coordinate edges?

klvnk — Sat, 19 Sep 2020 07:58:44 GMT

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

Re: Script to create new vertices on shared coordinate edges?

klvnk — Sat, 19 Sep 2020 08:20:08 GMT

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;

Re: Script to create new vertices on shared coordinate edges?

Serejah — Mon, 21 Sep 2020 12:11:43 GMT

There's always a hope!

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

Re: Script to create new vertices on shared coordinate edges?

chroma123 — Mon, 21 Sep 2020 20:54:37 GMT

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?

Re: Script to create new vertices on shared coordinate edges?

chroma123 — Mon, 21 Sep 2020 20:55:52 GMT

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

Re: Script to create new vertices on shared coordinate edges?

Serejah — Tue, 22 Sep 2020 12:19:15 GMT

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 )

Re: Script to create new vertices on shared coordinate edges?

chroma123 — Tue, 22 Sep 2020 15:12:56 GMT

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.

Re: Script to create new vertices on shared coordinate edges?

Serejah — Tue, 22 Sep 2020 16:04:11 GMT

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

Re: Script to create new vertices on shared coordinate edges?

chroma123 — Tue, 22 Sep 2020 16:15:12 GMT

... Like I said. Embarrasingly simple. 😀

Re: Script to create new vertices on shared coordinate edges?

denisT.MaxDoctor — Tue, 22 Sep 2020 21:40:45 GMT

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

Re: Script to create new vertices on shared coordinate edges?

denisT.MaxDoctor — Tue, 22 Sep 2020 22:12:46 GMT

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

Re: Script to create new vertices on shared coordinate edges?

denisT.MaxDoctor — Wed, 23 Sep 2020 00:35:47 GMT

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)

Re: Script to create new vertices on shared coordinate edges?

chroma123 — Wed, 23 Sep 2020 07:41:20 GMT

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?

Re: Script to create new vertices on shared coordinate edges?

denisT.MaxDoctor — Wed, 23 Sep 2020 23:04:44 GMT

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.

Re: Script to create new vertices on shared coordinate edges?

Anonymous — Wed, 14 Oct 2020 07:39:03 GMT

whoa, super interested in this!