if you OK to have a solution for editable poly only, everything becomes much easier:
get all edges of any of these two verts
select an edge and run loop:
if result contains the second vert – this is right direction
if it doesn’t contain – try another edge
if you didn’t find any direction – these two vertices can’t be connected with ‘loop logic’
if you get a direction:
use ‘direction edge’ and do setLoopShift (see the mxs help for details).
try both shifts – negative and positive and
count how many steps to reach the second vertex. the shorter is better
I haven’t measured setLoopShift() but I am aware it is very slow and would kill any algorithm, even with a few thousand polys. So I would go with a custom function just for this.
you might be surprised but setLoopShift is very fast method. all loops and rings in editable poly are PRECALCULATED. what makes a difference. setLoopShift just takes ‘next’ edge in ‘loop’ structure.
i’m absolutely sure that originally the task is to select verts between two specified. so it’s never thousands of polys.
the algorithm described above i use in my skinning tool to ‘interpolate’ weights between specified two groups of verts connected by rings.
How do you use it? Perhaps I am using it wrong, but this is pretty dam slow:
(
gc()
delete objects
segs = 50
node = converttopoly (box lengthsegs:segs widthsegs:segs heightsegs:segs isSelected:on)
polyop.setedgeselection node #{2}
max modify mode
st = timestamp(); sh = heapfree
for j = 1 to (segs*4) do node.setLoopShift 1 false true
format "time:% edges:%
" (timestamp()-st) (segs*4)
)
– time:3876 edges:200
you are right. it’s very slow for big meshes. i was wrong thinking that it just takes an edge from some pre-built poly structure. no! it builds this struct on-the-fly for every shift.
you can see that almost no difference how many edges you shift.
definitively the method needs a review.
Ok I think I have found a solution for this kind of problem. The main problem in this scenario is that you have to think in steps and not in distances, which means you need the least steps to reach the second target. So this is much more a topological based problem and not a geometrical.
Since I’m not at my computer I can’t make the code for you, but I can tell you the base of the idea.
On the last post I told you about the grow selection, so we might call this the growing selection method.
First you have to select the two vertices. Let´s call our vertices vertS (starting), vertN (next) and vertT (target). After that get the first vertices edges, and than their vertices one by one. Do growth on these vertices one by one and get the one that needs the least steps to reach the target vertex.
This vertex will be our next vertex which will be our new vertN. now we have to repeat the growth with vertN’s neighbour vertices, to find our new vertN. We have to do this until the necessary steps will be 1.
This is a method that will work only on Editable Poly objects because Edit Poly methods are much slower sadly. The method I have written is working with any kind of topology even if it hasn’t got a quad topo or if it has no loops at all.
(But anyway there is a proper method for this problem in unrwap uvw that works similiar to this one. The only problem is that we can’t get it to work with editable poly.) The only interesting part of this is the performance… (Which I think won’t be fast)
Hope that solution works properly . (or not… No chance to try it… I’m on holiday, and a tablet is not a proper device for it, especially with android… :))
If you wanted to implement a “flooding” algorithm, you might want to do it at a trimesh level and then send the result back to a Poly, Mesh or modifier.
However, I am not sure that such algorithm would be the right solution for this problem. There is no much information from the OP to be sure what to do, but it looks like simply selecting the vertices from a loop, which can have two or one solution, depending is they are in a closed or open loop. If there are two solutions you can decide if you want the longest or the shortest path.
If that is the case, I think the solution described by Denis would be more appropriate but without using setLoopShift() of course.
I think the get A using B methods are slow for the same reason. What happens when you try it with undo off? My experience is when you are using one of these methods they are consuming a high amount of memory… No idea why.
(For example the mid edge vertices example script found in the maxscript help file)
If you mean the KillMidEdgeVerts MacroScript, it is probably slow and use a lot of memory due to the calls to the structures.
If you cache them, most of the times memory will go down and for some methods there will be a huge improve in speed.
Whenever you need to call a method in a structure too many times, it needs to be cached for performance.
MeshOp structure does not have a big impact in speed, but in memory. PolyOp has benefits in memory and speed. Others like SkinOps also have huge benefits in both memory and speed.
I have made a simple mid edge selector script for mesh cleanup purposes, and I pre-cached the polyop method and predefined the array as well as the count for the array, but the performance is still not the one that would expected…
As i got home i’m gonna share.
Caching the methods is no guarantee that your algorithm will perform as good as you would expect, but it will certainly run much faster and use much less memory (depending on the method) than the same algorithm without caching the methods.
Also, the performance and memory usage might not be noticeable for a few iterations. You might need to run hundreds, thousands or millions of iterations to see a real benefit, again depending on what you are doing.
All that if there is no bug in the method itself. As we have seen, there are many of them that are very slow and leaks memory. There is no solution for this other than rewriting them.
If after doing all common optimizations your algorithm still does not performs as you would expect, then it could be:
- The algorithm is wrong.
- The nature of the algorithm is slow by itself, even if it is perfect in concept and execution.
Other than that, you could look for LUTs optimizations, avoiding selections, doing calculations at a trimesh level if possible, among other things.
I think the problem posted by simchris (he hasn’t posted again) needs more definition or explanation.
Path between two vertex… what for? In what cases? Vertex in the same plane? The shortest one? The straightest one?
Knowing the problem better, surely it’s easier to find the answer. And surely it’s simpler than the general situation.
This is one of those cases where one picture doesn’t worth a thousand words.
Based just on that image, it looks like it is a quad poly and we need to find the vertices between two vertices belonging to a loop.
I don’t understand what the shortest path (generally speaking) could be used for. That’s why I don’t think this is a problem for an A* or any other pathfinding algorithm.
However, if the situation is as we can barely deduct from the image it could be useful, for example, for aligning or relaxing the vertices.
In a more complex topology, it can be a little tedious to manually select a bunch of vertices, moreover if this is a repeated process.
But I agree that a better description of the problem would be required to find the best approach.
Yes, it’s one of those cases where one picture doesn’t worth a thousand words… but it can help!
In the above case, it seems that the solution is the path “A”. But it is the case with most steps! Thinking in steps might not be the right solution either.
Path “D” is the shortest in steps. Paths “B” and “C” are the same geometrically and topologically.
That’s why I think knowing better the problem, the solution might be different. I still think that what we human do to find the path is try to find the most direct route.
If we have to think in quads, (why not? It’s pretty common isn’t it?) It makes things much more simple. (And in the example we have a quad topology)
So basically the example you have shown is not really this case…