Getting the list of border vertices

[unicorn]

Hi all,

I am new to the amazing Babylon.js and this is my first post in the forum!

Here's my problem. Let's say that I have two meshes (these meshes might be randomly generated irregular polygons but for simplicity I am using two boxes). I merge them using CGS and then I flatten them by scaling the Y to zero (I am not sure if it is the correct way. I basically need to convert the 3D mesh to a 2D irregular polygon). I use a function to show the normals of the generated mesh and it shows me all the vertices. I only need to get the list of border vertices not the ones that falls inside the mesh. Upon getting the list, I would like to calculate the length of each border edges. I created a playground to demonstrate the issue.

https://playground.babylonjs.com/#HCH1F4

I appreciate your help.

 

[d13]

This is a fascinating problem!!!

Does no one here have any ideas on how to solve it?

[Wingnut]

Not only no one here, but no one anywhere.   I've done some serious web-searches... trying to nail this too-long-zero-reply subject... and failed nicely.

I have an idea... but it's mega-sloppy.

The mesh must be Y-scaled to 0 (smashed flat) as Unicorn's example does.

Then... sigh... https://www.babylonjs-playground.com/#1VITHH#18

See the pickInfo.distance down there in line 81?.  Although this is using camera-to-object ray, it could use someOrbitingMesh-to-object.

Perhaps, concentrically orbit the testMesh (with another ray-shooter mesh or cam), and do a pick-distance check every 1 degree of orbit.  You end with a database of 360 distances.  Possibly, you could gather worldSpace vec3 points-of-intersect, too... handy later.

(Perhaps use a box-shaped encircling, and not circular?  *shrug*)

Now, get(positionKind) data for the testMesh... and go to work.  I think... you would have enough data at that point (ar ar)... to determine WHICH of the verts... are positioned on the outer edges.

Maybe.    (Bad method, eh?  *nod*) 

The testMesh could have no "caves", where outer-edge points could be hidden from an encircling pickingRay. 

Sort of like laser-scanning.  Somewhat like the "lasso selection tool" in CorelPaint and other paint apps.  Just... painful. 

[unicorn]

That's a brilliant idea Wingnut.

I think there should be a more mathematical workaround for this. One possible approach may be to get the position of normals. Then we convert them to 2D space by ignoring the Y values. We may be able to use convex hull algorithm to get to outer points. The following links may be good starting points.

https://en.wikipedia.org/wiki/Gift_wrapping_algorithm

https://github.com/indy256/convexhull-js

https://github.com/AndriiHeonia/hull

https://github.com/mauriciopoppe/quickhull3d

However, one delicate issue that is happening here is that essentially I would like to remove all redundant vertices. If you take a look at the playground, the desired result would be that the outer rectangle have only 4 vertices. But now it show them as 8 ( 2 vertices on the left and right edges are redundant as they are on the same path)

[heavymetalmonk]

Since we're talking about irregular polygons,  Convex Hull Algorithms might give issues, since they might leave out certain vertices that are towards the center. I think Concave Hull Algorithms would work better.