Lasso tool for 3D mesh

Hello

Kindly, I would like someone help me with the “lasso tool” development in 3D world.
Just like this image:

User will click and drag the mouse for selecting “closed area” on the surface of any mesh.
And based on the selection, he can delete the “closed area” from the mesh.

I think that it is possible. But unfortunately, I don’t know how to do.

Hope to hear your feedback.
Thank

Related: Finding shortest path on mesh

Once you have the loop, you will need to separate the mesh in two sets of triangles (assuming the mesh is connected, with no separate “islands”), using the loop as a border. I think I would do this by “flood-filling” the graph (actually, depth-first or breadth-frist does not matter) that you need for the path searches.

When you have two sets, separating them may have to be done by making two new geometries.

Hi, @EliasHasle

Thanks for your indication.
So you are sure that it’s related to “finding shortest path”.

Actually, I am not fluent with JS.
Well, could you please let me clearer?

Thanks

I am not sure it will require finding the shortest path however you do it. E.g. if you can split polygons you may not have to, but I think it may turn out to be easier to search for the shortest path, especially since you will need a graph representation for the separation step anyway.

I certainly welcome other suggestions, as searches will contribute to the heavy load of raycasting. Live “drawing” on a high-res mesh is one of those cases where a custom raycasting method may come in handy (hints: spatial indexing, local tracking?)

I think someone should mention that this is not a trivial task. It would benefit from being broken into smaller tasks / problems.

Being somewhat fluent with JS would be a good first task to tackle.
Understanding how the mouse interacts with a 3d world (raycasting meshes) would be a good next step.
From there on this seems to fall in the realm of algorithms, and it sounds like there would be quite a few going on here.
I’d start by doing a naive approach first (not optimized) and then move to optimization (spatial indexing and such).

2 Likes

Humm, seems it’s easy or difficult.

I think that the “triangle geometries” of the mesh should be manipulated.
In my opinion:

  1. user click and moves the mouse.
  2. And getting “triangle geometry” which has “raycaster” following the mouse movement.
  3. Setting the center point of the “triangle geometry” as the one point which build the “lasso path”
  4. When the distance between first and last point is smaller than the “defined minimum distance”, it will inform that the path can be closed by releasing the mouse. (as dotted line)
  5. Removing the “triangles” involved within the “lasso area”.

I think like that. (Hope you to understand what I mean.)

If my thinking is near to the purpose, how can I do that?

If the geometry is indexed, all you have to do in this step may be to reorder/rebuild the index and make two renderGroups.

Problem 1: Raycasting upon mouse move by default iterates over all triangles of the mesh. Possible solution: Optimized raycast for your object.
Problem 2: If the mouse moves past multiple triangles before the mousemove event is fired and handled, you don’t know where to connect. This is made worse by problem 1. Possible solution: Searching for shortest path.
Problem 3: Using triangle centers will require you to split triangles, which complicates the work further. Possible solution: select nearest vertex instead.

@pailhead is right that this is far from trivial. It is doable, but will require a significant effort. If you can pull this off, I am sure the community will be happy to se something useful shared. :smiley:

1 Like

Thanks.

But can’t be sure.
If possible, I would like to solve together.
:slightly_smiling_face:

Solving together may be nice too. I don’t have time now. I think I would need at least a day or two alone to get a prototype working (or “working”)… I suggest you do some more research and share what you have and what you think you will be able to solve on your own, and then ask for more narrow help. It doesn’t hurt to gather more advice either, including evaluations of my proposed problems and solutions.

Hi, @EliasHasle

I have sent you invitation on my git repository.

https://github.com/DevArt002/3d-editor
This is the project what I did.

I would like to hear your opinion.

1 Like

I cloned it, and ran the example. Haven’t looked at the code yet. It appears you have raycasting working smoothly on a low-polygon mesh. If you want to split it smoothly, I think you will have to split the triangles, not only follow the vertices. It is really not straightforward in any way I can think of. :thinking:

Edit: I have some unfinished code related to triangle splitting lying around, intended for my solution to this game: https://www.codingame.com/ide/puzzle/shadows-of-the-knight-episode-2
Making a list of triangles to add to each new geometry is certainly not impossible.

Hi, @EliasHasle.

How was your weekend?
Just saw your message.

Yeah, I know that the line is not aligned on the surface of the model.


I found this. What do you think of that. I didn’t understand this yet.

I thought that once I can draw the line on the surface, I can extrude mesh from the line and subtract the mesh from the model by using ThreeCSG.js and csg.js. But I think that it’s difficult to implement, also.

If you are on my side, I would like to know what you think.

Thanks.

I didn’t notice the line drawing before now, when I tried the demo with a proper mouse. It seems drawing works only when the camera is at some minimum distance or more.

The SO link you posted refers to the same method I have outlined, that is using search algorithms for shortest path. A* is much better suited than Dijkstra or Breadth-first search, though, since it focuses on finding the path to one specific point, rather than to all.

Hi, @EliasHasle

Great.

But I found that it’s a little out of the target.
Kindly, I would like you to check this also.

Thanks for your attention.

I never used this technique, so pardon me if I’m telling rubbish… But wouldn’t this be easier with GPU picking ? The area you draw defines an array of pixel, then each face is given a unique color, then you check the color in every pixel to retrieve all the faces in the defined area ?
Edit: wouldn’t pick the faces in background though…

Hi, @felixmariotto

Thanks for your advice. But because I am new at Three.js, seems I didn’t you get you.
You mean GLSL?

Yes, like this
Again I never used this trick myself so it’s entirely theoritical…

Thanks, @felixmariotto

But, I am new at GLSL…

@felixmariotto’s suggestion is not bad. The reference provides a straightforward way to do GPU-based picking, which is an alternative to advanced raycasting methods. I would suggest using the knowledge of the mouse position to modify the camera projection (only of the camera being used for picking) so that it renders only the clicked pixel, though. This would also involve setting the render target dimensions to 1x1.

Anyway, GPU picking does not necessarily solve the fundamendal challenges of connecting points.

1 Like