Compute surfaces of objects

#2

Hi, welcome to the forum.

Youā€™ll need to use the triangle information to know which triangles are neighbours of which ones, and also know the angles between them, to separate the boundary that forms the feature you want.

I will write you an algorithm in pseudocode (which means it is not written in any programming language, but more like english). You can ask later how to implement specific algorithm lines.

The algorithm starts with the selected triangle and basically grows the set of processed triangles by finding the neighbours to active triangles. A neighbour is added only if the angle between the selected triangle and the new one is less than a threshold. When no more triangles can be added, the algorithm stops and returns the set of triangles which form the selected mesh feature.

Let angleThreshold = 35 degrees
Let T = the set of triangles of the object.
Let t be the selected triangle in T
Let U be a set, initially equal to T. It is the set of unprocessed triangles.
Let A be a set, which initially contains only the triangle t. It is the set of active triangles.
Let R be the result triangle set, initially empty.
While A is not empty do:

    Take out the triangle t from A.
    Take out the triangle t from U.
    Put the triangle t into R.

    Let N be the set of triangles from U which are neighbours of t and its normal form an angle less than angleThreshold degrees whith the normal of t.

    If N is not empty:
        Add the triangles in N to the set A, if they are not already.
    End If

    Let t be a triangle of A, if A is not empty.

End While

Return R.
2 Likes
#3

Hello yombo,
First i want to thank you very much. Its awesome that ppl like you are so kind and take their time to help others.

Iā€™ve been analysing your code and except a little thing i think it should work.
After: if N is not empty:
Add N to A, if they are not already in AND if they are in U.

So thank you very much, i have no an idea of what i want to došŸ˜Š. A few questions in my mind right now are:

  1. All these vectors are stored in geometry.attributes.position.array. When i now click on the object, i have to somehow get nearest triangle. I have to think about it tomorrow again, but right now (at midnight) i dont know how :smiley:
    (I think the solution of this question should be easy)
  2. When i have a triangle (3 vectors in my array), where are my x neighbors? How can i know how many i have? This questions seems kind of hardā€¦ maybe some vector dimensions have to be similarā€¦ but the search algorithm would take quite alot of time to go through every triangle, wouldnt it?

Thank you again!

#4

Hi, you are welcome :slight_smile:

I wrote ā€œLet N be the set of triangles from Uā€¦ā€, so no need to check if they are in U, we took them from U already.

1 . The THREE.Raycaster gives you information on the intersection point, the face intersected and more.

2 . For this to work it is much more useful to work with an indexed mesh. Look at examples/BufferGeometryUtils on how to convert between indexed and non-indexed.

Once you have an indexed mesh, it means you not only have geometry.attributes.position, but also geometry.attributes.index. Now the main array is the index, which tells you (with every three numbers) the indices of the triangle vectors in the position.array.

To know the neighbours you compare indices of triangles. For example given the triangle with vertex indices (a, b, c), you search other triangles with indices (b, a, ?), (?, a, b), (a, ?, b) (This would be neighbours in the first segment, a-b) and so on.

Yes, it can be slow depending on the triangle count and how it is programmed.

#5

Thank you very much again.
On monday i am going to start implementing this. Is it necessary to convert to an indexed array? when i have to search for these 6 combinations (a,b,?),(b,a,?),(a,?,b),(b,?,a),(?,a,b),(?,b,a) by going through the whole array, it doesnt matter if its sorted, except i donā€™t have to search through everything:).
What changes with an indexed array?
Im excited for monday:)

#6

Yes, there are lots of possible optimizations, as that one.

About using indexed mesh: Without it you have only vertex positions, so to find neighbours you need to compare positions instead of just integer indices. That is commonly called ā€œtriangle soupā€. With indices you have the common vertices joined already and it is much faster, as I say, to compare two indices than two vectors.

#7

And btw, good luck with it :slight_smile:

#8

Thank you! I will let you know of course if i was successful or notšŸ˜Š. Also thank you very much for your time! Very kind!

#9

So i started implementing today and i already have some questions. I donā€™t find a method for transforming BufferGeometry to an indexed one here https://threejs.org/docs/index.html#examples/en/utils/BufferGeometryUtils, so I use this code https://threejs.org/examples/webgl_buffergeometry_indexed.html
to understand how to convert my object.geometry into an indexed geometry.
I think i have to copy the ā€œgenerate indicesā€ code and only have to set the parameter:
var segments = ?;

In the example segments is set to 10 and the object has a geometry.position.length of 363 and count of 121 and a index.length and count of 600.
So my first question is:
How can i calculate the segments variable for my object? my object has f.e. a position.length of 5568 and a count of 1856.

I watched the index array of the example object and the first values look like this:
0: 1
1: 0
2: 12
3: 0
4: 11
5: 12
6: 2
7: 1
8: 13
9: 1

So my goal is to get neighbours and the angle to each others areas out of this data.

My second question is: How can i get neighbours and angles out of these numbers?
i understand how i can get the information out of the position.array (by finding other combinations (a,b,?), (b,a,?) ā€¦ but i donā€™t understand the princip of the indices)
EDIT: I think i can get angles by ā€œ.computeVertexNormalsā€. But i still donā€™t know how to find neighbours. I also donā€™t understand why the indices are much more values then the geometry.position ones.

For Raycaster i use this codeline: intersects = raycaster.intersectObjects( scene.children, true );
All my objects are stored in scene.children, which i want to select.
By selecting an object, i get back ā€œFaceā€ and ā€œFaceindexā€ (see https://threejs.org/docs/#api/en/core/Raycaster).

So my third question is: do i have to compare these indicices with the ones reated?

#10

Hey i have some new knowledge:
Finding neighbours should probably be done by comparing vectors. So you canā€™t compare indices and find out neighbours because they are not sorted like that in the array. So you have to search them in the position array. The problem is now, i want f.e. to splice out a triangle from the array, i canā€™t do that because i would have to splice out vertices which make other triangles work (and i would destroy other triangles). So to make this work i would have to make a hybridā€¦ I think i need to save three vertices and a index so im able to say something like: ā€œindex 123 processed, so splice itā€

#11

The (a,b,?), (b,a,?) thing is with indices. The indices array works 3 by 3, with each three indices forming a triangle. For example:
If you have triangle (15, 16, 30) and find a triangle (112, 16, 15), you know the two triangles are neighbours. (Concretely, the first one shares the first side or segment, while the second one shares the second segment)

The indices of those triangles could be:
[ a, b, c, ā€¦, 15, 16, 30, ā€¦ 112, 16, 15, ā€¦ ]
So each triangle have an index. The triangle with index 0 in this example is (a, b, c). The faceIndex that the raycaster gives to you should be the selected triangle index.
Yes, you can store a list of triangles to delete afterwards, as you say.

About the angle and normals, yes, you can compute the face normals. But for this application they are not useful, is is better to use the face normals. See how to compute it in THREE.Face3.

Once you have the normals of two triangles, you just make if ( normal1.angleTo( normal2 ) < threshold) { and so on.

#12

Thank you, you are right. But do you know how to index a complex object? In the three.js ā€œindexedā€ example it looks pretty easy because the triangles are all known, but how can i generate an indexed buffergeometry, by not knowing, which vertices in geometry.attributes.positions are building a triangle? I understand that all vertices in a non-indexed geometry are represented once, so i donā€™t understand, which vertices are building a triangle.

#13

@derseitzer Three consequent vertices define a triangle/face in a non-indexed buffer geometry.

#14

Then the ā€œBufferGeometry, Indexedā€ - example in three.js confuses me. It has 121 vertices (plane of 11 x 11), but if your right, vertices should be represented more often in the array because they are used for multiple triangles, or what am i missing hereā€¦

#15

In an indexed buffer geometry faces are defined with indices of vertices in its .index property.

The simplest thing - quad:
Non-indexed buffer geometry: .index is null, position attribute contains information for 6 vertices (3 vertices per face, as a quad is built with 2 faces)
Indexed buffer geometry: position attribute contains information about 4 vertices and index has 6 indices (3 indices of vertices for each of 2 faces)

[0]------[1]
 |      / |
 |    /   |
 |  /     |
[2]------[3]

4 vertices and .index is [0, 2, 1, 2, 3, 1]

#16

Perhaps the very simple examples help. :slightly_smiling_face:

https://hofk.de/main/discourse.threejs/2017/BufferGeometry/BufferGeometry.html
https://hofk.de/main/discourse.threejs/2017/Indexed%20BufferGeometry/Indexed%20BufferGeometry.html

from
https://hofk.de/main/discourse.threejs/2017/index2017.html

or
https://hofk.de/main/discourse.threejs/2019/ColorStripeChanging2/ColorStripeChanging2.html

see

#17

Okay thank you very much. So i have my non-indexed mesh and want to compute the facenormals now (i read that attributes.normal of a non-indexed mesh are usually vertexnormals https://github.com/mrdoob/three.js/issues/12559). But thereā€™s sadly no function for that. Do i have to filter out the vertex normals manually and compute face normals myself?

Edit. copied this from THREE.Geometry, so i should have my facenormals

cb.subVectors( vC, vB );
ab.subVectors( vA, vB );
cb.cross( ab );

cb.normalize();

#18

Itā€™s just a matter of practice. One can work with Geometry, indexed BufferGeometry and non-indexed Buffergeometry

But Geometry is no longer recommended. See e.g. Will Geometry be deprecated or maintained along BufferGeometry?

In my addon THREEf.js I used all three possibilities in parallel. There you can compare well. But the thing there is quite complex.
Addon. Produces almost infinite many time-varying geometries with functions
https://github.com/hofk/THREEf.js/blob/b263d88d9b783b5dca4f5008e718997b6a3e75f0/THREEf_90/THREEf.js
There you can see what is achievable. https://hofk.de/main/threejs/sandboxthreef/

Maybe thereā€™s something for you? https://github.com/hofk/THREEg.js

#19

i actually have to use Buffergeometry, because my imported stl-object is one by default. So by calculating face normals i think i have all i want.

#20

Good luck to you. :slightly_smiling_face:

#21

Using of THREE.Triangle() can be helpful.
Something like this:

var pos = geometry.attributes.position;
var tri = new THREE.Triangle(); // for re-use
var a = new THREE.Vector3(); // for re-use
var b = new THREE.Vector3(); // for re-use
var c = new THREE.Vector3(); // for re-use
var normals = [];
var faces = pos.count / 3;

for (let i = 0; i < faces; i++){
  a.fromBufferAttribute(pos, i * 3 + 0);
  b.fromBufferAttribute(pos, i * 3 + 1);
  c.fromBufferAttribute(pos, i * 3 + 2);
  tri.set(a, b, c);
  let n = new THREE.Vector3();
  tri.getNormal(n);
  normals.push(n);
}
2 Likes