Subdivision of Geometry Vertices in Three

Originally this subdivision code was a branch off a tech test I did for a rudimentary loop cut. Funny how other things crop up when you aren’t searching for them!

This is going to be very practical and go through the code and less about more general theory. Let me know if you have any questions. Below is the sandbox and demo.

Below is the code for the subdivison:

1//  Loop cut at the mid points of triangles, either do onClick event on the mesh
2// or do onPointMove and get the effect of painting verticies onto the mesh.
3
4const Box = memo(() => {
5  const geom = useRef();
6  const mesh = useRef();
7  const pointsGeom = useRef();
8  const { scene } = useThree();
9
10  // This is the main function, it deals with the buffer geometry and all of the complexities that
11  // go with dealing with orders, verticies and triangle faces (order based)
12  const getData = ({ e, geometry }) => {
13    const newVertices = [];
14    const newIndices = [];
15    const numVertices = geometry.attributes.position.array.length / 3;
16
17    const position = geometry.attributes.position;
18
19    console.log({ e: e.intersections });
20    // This is the face we have clicked or hovered on all coming through the useful
21    // onclick event / onPointerMove event, which is actually a threejs raycaster with
22    // optimizations
23    const aIndex = e.intersections[0].face.a;
24    const bIndex = e.intersections[0].face.b;
25    const cIndex = e.intersections[0].face.c;
26
27    // for the new verticies we are adding we dont want to reuse indicies as this would cause weird faces
28    // for new verticies we can create new indicies and add them onto the end
29    const newAIndex = numVertices + 0 * 3;
30    const newBIndex = numVertices + 0 * 3 + 1;
31    const newCIndex = numVertices + 0 * 3 + 2;
32
33    // This is grabbing the position using the intersections face indicies
34    const aPosition = new THREE.Vector3().fromBufferAttribute(position, aIndex);
35    const bPosition = new THREE.Vector3().fromBufferAttribute(position, bIndex);
36    const cPosition = new THREE.Vector3().fromBufferAttribute(position, cIndex);
37
38    // we can then find the mid point between each corner
39    const abPosition = new THREE.Vector3().lerpVectors(
40      aPosition,
41      bPosition,
42      0.5
43    );
44    const bcPosition = new THREE.Vector3().lerpVectors(
45      bPosition,
46      cPosition,
47      0.5
48    );
49    const caPosition = new THREE.Vector3().lerpVectors(
50      cPosition,
51      aPosition,
52      0.5
53    );
54
55    // and finally we add the indicies and vertexs to the arrays
56
57    // if we add midpoints between a triangle we go from 1 triangle to 4 which requires
58    // 3 verticies for each triangle and therefore 12 in total indicies are added.
59    // IMPORTANT: they come in 3 and the order really does matter 1 for each corner of the triangle
60    // and it is completely ok for one part of this truplet group of indicies to be reused in other groups.
61    // hence interleaved
62
63    // Just remember 3 indexs = 1 face drawn
64    newIndices.push(
65      aIndex,
66      newAIndex,
67      newCIndex,
68      newAIndex,
69      bIndex,
70      newBIndex,
71      newAIndex,
72      newBIndex,
73      newCIndex,
74      newBIndex,
75      cIndex,
76      newCIndex
77    );
78
79    // we only want to add new vertex's not the old ones otherwise we get duplication
80    newVertices.push(
81      abPosition.x,
82      abPosition.y,
83      abPosition.z,
84      bcPosition.x,
85      bcPosition.y,
86      bcPosition.z,
87      caPosition.x,
88      caPosition.y,
89      caPosition.z
90    );
91
92    return { newVertices, newIndices };
93  };
94
95  function filterArray(source, arr) {
96    const result = [];
97    for (let i = 0; i < arr.length; i += 3) {
98      const index1 = arr[i];
99      const index2 = arr[i + 1];
100      const index3 = arr[i + 2];
101
102      if (
103        source.includes(index1) &&
104        source.includes(index2) &&
105        source.includes(index3)
106      ) {
107        continue;
108      }
109
110      result.push(index1, index2, index3);
111    }
112    return result;
113  }
114
115  const loopCut = ({ geometry, e }) => {
116    const { newVertices, newIndices } = getData({ e, geometry });
117
118    // we have to reduce the overall incies count as when we generate them above,
119    // we have to remove the old face and add the new faces which make up the old face ]
120    geometry.index.count -= 3;
121
122    const positions = geometry.attributes.position.array;
123
124    let indices = geometry.index.array;
125
126    // As we are updating the number of verticies I found you have to set the draw rannge to the
127    // new total number of verticies which is roughly less than the total of old + new indicies
128    geometry.setDrawRange(0, indices.length + newIndices.length);
129
130    // setting the position attribute with the updated positions
131    geometry.setAttribute(
132      "position",
133      new THREE.Float32BufferAttribute(
134        new Float32Array([...positions, ...newVertices]),
135        3
136      )
137    );
138
139    // As stated we have to remove the old face otherwise it comes back in the onClick / onPointerMove events
140    // and it tries to subdivide the same face which results in no extra [points but more verticies in the same position
141    const filteredArrIndex = filterArray(
142      [
143        e.intersections[0].face.a,
144        e.intersections[0].face.b,
145        e.intersections[0].face.c,
146      ],
147      indices
148    );
149
150    // Setting the index's which determine face rendering
151    geometry.setIndex(
152      new THREE.BufferAttribute(
153        new Uint32Array([...filteredArrIndex, ...newIndices]),
154        1
155      )
156    );
157
158    // Probs dont need all this and abit gungho but ah well
159    // nobody knows everything haha
160    geometry.verticesNeedUpdate = true;
161    geometry.attributes.position.needsUpdate = true;
162    geometry.index.needsUpdate = true;
163    geometry.computeFaceNormals = true;
164    geometry.computeVertexNormals();
165    geometry.computeBoundingSphere();
166    geometry.computeBoundingBox();
167  };
168
169  return (
170    <group>
171      <mesh
172        ref={mesh}
173        // Change to onClick in you want to
174        onPointerMove={(e) => {
175          // One to visualise the verticies, Points
176          // and the Cube for visually looking at the geometry
177          loopCut({ e, geometry: geom.current, meshA: mesh.current, scene });
178          loopCut({
179            e,
180            geometry: pointsGeom.current,
181            meshA: mesh.current,
182            scene,
183          });
184        }}
185        scale={[2, 2, 2]}
186        needsUpdate
187      >
188        <boxBufferGeometry ref={geom} />
189        <meshBasicMaterial needsUpdate />
190      </mesh>
191      <points scale={[2, 2, 2]}>
192        <boxBufferGeometry ref={pointsGeom} />
193        <pointsMaterial size={0.04} color={"red"} />
194      </points>
195    </group>
196  );
197});

The key bit to understand is this is an indexed geometry, I.e. the order of the indices dictates to what face is constructed. So:

1const indexs = [1, 2, 3, 4, 5, 6, 7, 8, 9];

this has 3 faces 1/2/3, 4/5/6 and 7/8/9.

The aim we are trying to accomplish is to subdivide each triangle into half way points between each vertex, i.e. a subdivision of the faces. Take the diagram below as an example:

In this example we can see that we split the initial triangle made of 3 vertices into 4 triangles.

1// 6 vertices 
2// 4 faces 
3// 12 indexes

Here is the function which grabs the data:

1const getData = ({ e, geometry }) => {
2    const newVertices = [];
3    const newIndices = [];
4    const numVertices = geometry.attributes.position.array.length / 3;
5
6    const position = geometry.attributes.position;
7
8    console.log({ e: e.intersections });
9    // This is the face we have clicked or hovered on all coming through the useful
10    // onclick event / onPointerMove event, which is actually a threejs raycaster with
11    // optimizations
12    const aIndex = e.intersections[0].face.a;
13    const bIndex = e.intersections[0].face.b;
14    const cIndex = e.intersections[0].face.c;
15
16    // for the new verticies we are adding we dont want to reuse indicies as this would cause weird faces
17    // for new verticies we can create new indicies and add them onto the end
18    const newAIndex = numVertices + 0 * 3;
19    const newBIndex = numVertices + 0 * 3 + 1;
20    const newCIndex = numVertices + 0 * 3 + 2;
21
22    // This is grabbing the position using the intersections face indicies
23    const aPosition = new THREE.Vector3().fromBufferAttribute(position, aIndex);
24    const bPosition = new THREE.Vector3().fromBufferAttribute(position, bIndex);
25    const cPosition = new THREE.Vector3().fromBufferAttribute(position, cIndex);
26
27    // we can then find the mid point between each corner
28    const abPosition = new THREE.Vector3().lerpVectors(
29      aPosition,
30      bPosition,
31      0.5
32    );
33    const bcPosition = new THREE.Vector3().lerpVectors(
34      bPosition,
35      cPosition,
36      0.5
37    );
38    const caPosition = new THREE.Vector3().lerpVectors(
39      cPosition,
40      aPosition,
41      0.5
42    );
43
44    // and finally we add the indicies and vertexs to the arrays
45
46    // if we add midpoints between a triangle we go from 1 triangle to 4 which requires
47    // 3 verticies for each triangle and therefore 12 in total indicies are added.
48    // IMPORTANT: they come in 3 and the order really does matter 1 for each corner of the triangle
49    // and it is completely ok for one part of this truplet group of indicies to be reused in other groups.
50    // hence interleaved
51
52    // Just remember 3 indexs = 1 face drawn
53    newIndices.push(
54      aIndex,
55      newAIndex,
56      newCIndex,
57      newAIndex,
58      bIndex,
59      newBIndex,
60      newAIndex,
61      newBIndex,
62      newCIndex,
63      newBIndex,
64      cIndex,
65      newCIndex
66    );
67
68    // we only want to add new vertex's not the old ones otherwise we get duplication
69    newVertices.push(
70      abPosition.x,
71      abPosition.y,
72      abPosition.z,
73      bcPosition.x,
74      bcPosition.y,
75      bcPosition.z,
76      caPosition.x,
77      caPosition.y,
78      caPosition.z
79    );
80
81    return { newVertices, newIndices };
82  };

Here we grab the indexes and then the vertexs from the bufferAttribute:

1const aIndex = e.intersections[0].face.a;
2const bIndex = e.intersections[0].face.b;
3const cIndex = e.intersections[0].face.c;
4
5const aPosition = new THREE.Vector3().fromBufferAttribute(position, aIndex);
6const bPosition = new THREE.Vector3().fromBufferAttribute(position, bIndex);
7const cPosition = new THREE.Vector3().fromBufferAttribute(position, cIndex);

The face is a triangle and abc represent the points on this triangle. fromBufferAttribute then accepts a vector and an index. Which gives the positions of the points on the tirangle.

Below Gets the position half way through each edge of the triangle.

1// we can then find the mid point between each corner
2const abPosition = new THREE.Vector3().lerpVectors(
3  aPosition,
4  bPosition,
5  0.5
6);
7
8const bcPosition = new THREE.Vector3().lerpVectors(
9  bPosition,
10  cPosition,
11  0.5
12);
13
14const caPosition = new THREE.Vector3().lerpVectors(
15  cPosition,
16  aPosition,
17  0.5
18);

Then we create the new indexs of each of the 4 triangles.

1// Just remember 3 indexs = 1 face drawn
2newIndices.push(
3  aIndex,
4  newAIndex,
5  newCIndex,
6  newAIndex,
7  bIndex,
8  newBIndex,
9  newAIndex,
10  newBIndex,
11  newCIndex,
12  newBIndex,
13  cIndex,
14  newCIndex
15);

Each subdivision has 3 new vertices so we want to add these 9 new components of the 3 vectors to our newVertices array.

1// we only want to add new vertex's not the old ones otherwise we get duplication
2newVertices.push(
3  abPosition.x,
4  abPosition.y,
5  abPosition.z,
6  bcPosition.x,
7  bcPosition.y,
8  bcPosition.z,
9  caPosition.x,
10  caPosition.y,
11  caPosition.z
12);

Now we want to loopcut on an event listener, so heres the function which will accomplish this:

1const loopCut = ({ geometry, e }) => {
2  const { newVertices, newIndices } = getData({ e, geometry });
3
4  // we have to reduce the overall incies count as when we generate them above,
5  // we have to remove the old face and add the new faces which make up the old face ]
6  geometry.index.count -= 3;
7
8  const positions = geometry.attributes.position.array;
9
10  let indices = geometry.index.array;
11
12  // As we are updating the number of verticies I found you have to set the draw rannge to the
13  // new total number of verticies which is roughly less than the total of old + new indicies
14  geometry.setDrawRange(0, indices.length + newIndices.length);
15
16  // setting the position attribute with the updated positions
17  geometry.setAttribute(
18    "position",
19    new THREE.Float32BufferAttribute(
20      new Float32Array([...positions, ...newVertices]),
21      3
22    )
23  );
24
25  // As stated we have to remove the old face otherwise it comes back in the onClick / onPointerMove events
26  // and it tries to subdivide the same face which results in no extra [points but more verticies in the same position
27  const filteredArrIndex = filterArray(
28    [
29      e.intersections[0].face.a,
30      e.intersections[0].face.b,
31      e.intersections[0].face.c,
32    ],
33    indices
34  );
35
36  // Setting the index's which determine face rendering
37  geometry.setIndex(
38    new THREE.BufferAttribute(
39      new Uint32Array([...filteredArrIndex, ...newIndices]),
40      1
41    )
42  );
43
44  // Probs dont need all this and abit gungho but ah well
45  // nobody knows everything haha
46  geometry.verticesNeedUpdate = true;
47  geometry.attributes.position.needsUpdate = true;
48  geometry.index.needsUpdate = true;
49  geometry.computeFaceNormals = true;
50  geometry.computeVertexNormals();
51  geometry.computeBoundingSphere();
52  geometry.computeBoundingBox();
53};

This creates the data:

1const { newVertices, newIndices } = getData({ e, geometry });

and then this sets the data for the index and position:

1// As we are updating the number of verticies I found you have to set the draw rannge to the
2// new total number of verticies which is roughly less than the total of old + new indicies
3geometry.setDrawRange(0, indices.length + newIndices.length);
4
5// setting the position attribute with the updated positions
6geometry.setAttribute(
7  "position",
8  new THREE.Float32BufferAttribute(
9    new Float32Array([...positions, ...newVertices]),
10    3
11  )
12);
13// Setting the index's which determine face rendering
14geometry.setIndex(
15  new THREE.BufferAttribute(
16    new Uint32Array([...filteredArrIndex, ...newIndices]),
17    1
18  )
19);

We have to remove the old indexs otherwise another face would show up and mess with what the cube looks like.

1function filterArray(source, arr) {
2  const result = [];
3  for (let i = 0; i < arr.length; i += 3) {
4    const index1 = arr[i];
5    const index2 = arr[i + 1];
6    const index3 = arr[i + 2];
7
8    if (
9      source.includes(index1) &&
10      source.includes(index2) &&
11      source.includes(index3)
12    ) {
13      continue;
14    }
15
16    result.push(index1, index2, index3);
17  }
18  return result;
19}

If the index’s exist then we skip adding them to the end array. Therefore removing the old indices.

Finally we add this function onto an event listener:

1onPointerMove={(e) => {
2  // One to visualise the verticies, Points
3  // and the Cube for visually looking at the geometry
4  loopCut({ e, geometry: geom.current, meshA: mesh.current, scene });
5  loopCut({
6    e,
7    geometry: pointsGeom.current,
8    meshA: mesh.current,
9    scene,
10  });
11}}

Subdivision of Geometry Vertices in Three

More articles from theFrontDev

R&D - Water Ripple, Postprocessing and HTML like world

Top resources for web 3D in 2023