How to sort an Array of vertices to make an unbroken 'sensible' geometry

[Moe_Ibrahim]

Hi Guys,

I have this problem that i couldnt find solutions to anywhere else.

so I have an array of xyz positions. they should represents vertices points on a human face, so if i put those in a position attribute of a BufferGeometry they are meant to give me a face geometry. but the result is a very broken geometry with random triangles here and there.

am guessing that is because the points in the array are not in the right order.

if instead of creating a mesh, i put the geometry holding that position array in a points object + points material i get the right representation of the face i need but in points, image below. this means at least the points are in the correct xyz position.

my question, would it be possible to sort the points in the array in a way that renders the right face mesh?

is it posible to create the face surface in a way that ignores the order of the vertices in the array?

help is very appreciated.

[donmccurdy]

This process is called triangulation, the thread here might help:

3D Mesh from cloud of points

Maybe you are right, In fact I was trying that at the time you sent your post. Would you mind to explain the reason of this code in the HTML part of the jsfiddle? <script> THREE.Vector3.prototype.equals = function( v, epsilon = Number.EPSILON ) { return ( ( Math.abs( v.x - this.x ) < epsilon ) && ( Math.abs( v.y - this.y ) < epsilon ) && ( Math.abs( v.z - this.z ) < epsilon ) ); } </script> Without this part the code does not work at all…

For concave geometry the results may not be exactly what you want without some tweaking in modeling software like Blender though.

[vielzutun.ch]

@Moe_Ibrahim

is it posible to create the face surface in a way that ignores the order of the vertices in the array?

help is very appreciated.

The idea of “sorting” seems to be based on the assumption, that there is some inherent logic in the order of the vertices. I consider this a bold assumption, a.k.a. “wild guess”.

Instead of trying to fix an export from some source program, in the course of which crucial information got stripped off, I’d try to streamline my workflow in a way as to fix the export in a way, that vertex data gets exported along with the needed index data.

[Moe_Ibrahim]

thank you so much this is super informative !

[Moe_Ibrahim]

could you please elaborate more on how index data can be added ?
am getting the output from a tensorflow js face mesh model which tracks the face on each requestAnimationFrameand gives me the array of xyz points sorted in the way i described as random. so anything i can add would be after this step.

[vielzutun.ch]

Your question is manifold.

First please realise, that your point cloud contains points, which are passed to you at an arbitrary ordering. At least not an order, that you know of or which you can easily retrieve. Anyway, eventually you’ll end up having a point array, which does have an order, however arbitrary that may be. Meaning: you have point coordinates at position “0” of that array, point coordinates at position “1” of that array, point coordinates at position “2” of that array, and so on. Lets call those array positions “index”, or “indices”.

And you’ll want to have faces defined through those points. These will be triangle faces, because that’s the way three.js is organised. I’ve done that for a small part of your model:

Now you’ll need to tell three.js which points from your point coordinate array form the endpoints of each(!) triangle. You’ll end up with a series of triplets of indices:

Note, these are random numbers which I assigned to each vertex. Although they seem to be ordered, there’s no way you can rely on them being ordered like that.

The definition of triangles might look something like the following. Please note, these are triplets of integer indices into the points array having float coordinate values:

8, 9, 15,
9, 16, 15,
9, 10, 16,
10, 17, 16,
10, 11, 17,
…

and so on. You’ll get the idea.

Note, that the data model of BufferGeometry has (can have) both a “position” array and an “index” array:

A few things to consider:

All triangles need to be specified using the same winding order [clockwise | counterclockwise]. This determines the direction of the face normal (whether the face is facing you, or is facing away from you).

Depending on the complexity of your point cloud, to manually provide missing index data is a lot of work for just one frame. If you need to repeat that on every new frame, I’d call that approach not viable.

That’s why I advised you to start earlier in your workflow, and try to get the index information exported along with the point coordinates.

[Moe_Ibrahim]

this is super informative thank you very much !!!