Three.js - can I detect geometry 'islands' when importing?

Question

I'm importing .3DS models into Blender 2.72b, then exporting them with the Three.js import/export addon. The models have multiple geometry 'islands' (separate groups of connected faces and vertices), each with its own material. I'd like to be able to pair each material with its corresponding island, without having to create separate THREE.Geometry objects. After some digging, I found this question which suggests using a THREE.MeshFaceMaterial to achieve multiple materials for one object. The only problem is that the geometry in that example is a simple cube, whereas my models have hundreds of faces spread across 2-5 islands.

Does Three.js have functionality for identifying geometry 'islands' in a mesh?

Answer 1

This is I think the correct way:

function unmergeGeometryArray(geometry) {
        // Asumptions:
        // geometry is BufferGeometry 
        // The geometry has no index duplicates (2 equal positions with different index) neither empty triangles, the geometry has been processed with mergeVertices function
        // normal attribute is discarded, can be recomputed after, only color and position attributes are taken into account
        
        const material = new THREE.MeshBasicMaterial({
            side: THREE.DoubleSide,
            vertexColors: THREE.VertexColors
        });
        
        const indexArray = geometry.index.array;
        const positionArray = geometry.attributes.position.array;
        const positionCount = geometry.attributes.position.count;
        const totalTriangles = indexArray.length / 3;
        
        let triangleVisitedArray = new Uint8Array(totalTriangles);
        let indexVisitedArray = new Uint8Array(positionCount);
        let indexToTriangleIndexMap = [];
        
        let missingVertices = positionCount;
        let missingTriangles = totalTriangles;
        
        // Functions:
        function computeTrianglesRecursive(index, out){ 
            //console.log("- start of computeTriangles with index:", index);    
            if (indexVisitedArray[index] === 1 || missingVertices === 0 || missingTriangles === 0) {
                return;
            }       
            indexVisitedArray[index] = 1;
            missingVertices -= 1;       
            let triangleIndexArray = indexToTriangleIndexMap[index];        
            for(let i=0; i<indexToTriangleIndexMap[index].length; i++) {
                let triangleIndex = indexToTriangleIndexMap[index][i];
                if (triangleVisitedArray[triangleIndex] === 0) {
                    triangleVisitedArray[triangleIndex] = 1
                    missingTriangles -= 1;
                    //console.log("-- index: ", index, "; i: ", i, "; triangleIndex: ", triangleIndex);
                    out.push(triangleIndex);
                    childIndex1 = indexArray[triangleIndex*3+1];
                    computeTriangles(childIndex1, out);
                    childIndex2 = indexArray[triangleIndex*3+2];
                    computeTriangles(childIndex2, out);
                }
            }
        }
        
        function computeTriangles(indexTocheck){
            let out = [];
            let startIndex = indexTocheck;  
            let indexToCheckArray = [indexTocheck];
            let i = 0;
            
            while (i<indexToCheckArray.length) {
                let index = indexToCheckArray[i];
                if (indexVisitedArray[index] == 0) {
                    indexVisitedArray[index] = 1;
                    missingVertices -= 1;   
                    let triangleIndexArray = indexToTriangleIndexMap[index];
                    for(let j=0; j<indexToTriangleIndexMap[index].length; j++) {
                        let triangleIndex = indexToTriangleIndexMap[index][j];
                        if (triangleVisitedArray[triangleIndex] === 0) {
                            triangleVisitedArray[triangleIndex] = 1;
                            missingTriangles -= 1;
                            out.push(triangleIndex);
                            let rootIndex = indexArray[triangleIndex*3];
                            let child1Index = indexArray[triangleIndex*3+1];
                            let child2Index = indexArray[triangleIndex*3+2];
                            
                            if (indexToCheckArray.indexOf(rootIndex) === -1) {
                                indexToCheckArray.push(rootIndex);
                            }
                            
                            if (indexToCheckArray.indexOf(child1Index) === -1) {
                                indexToCheckArray.push(child1Index);
                            }
                            
                            if (indexToCheckArray.indexOf(child2Index) === -1) {
                                indexToCheckArray.push(child2Index);
                            }
                        }
                    }
                }
                i +=1;
            }
            return out;
        }
        
        // In the first loop we reorder indices asc order + generate map
        for (triangleIndex=0; triangleIndex<totalTriangles; triangleIndex++) {
            const geoIndex1 = indexArray[triangleIndex*3];
            const geoIndex2 = indexArray[triangleIndex*3+1];
            const geoIndex3 = indexArray[triangleIndex*3+2];
            const triangleIndexVertexArray = [ geoIndex1, geoIndex2, geoIndex3 ].sort(function(a, b) { 
                return a - b; 
            });
            if (indexToTriangleIndexMap[geoIndex1] === undefined) {
                indexToTriangleIndexMap[geoIndex1] = [triangleIndex];
            } else {
                indexToTriangleIndexMap[geoIndex1].push(triangleIndex);
            }
            if (indexToTriangleIndexMap[geoIndex2] === undefined) {
                indexToTriangleIndexMap[geoIndex2] = [triangleIndex];
            } else {
                indexToTriangleIndexMap[geoIndex2].push(triangleIndex);
            }
            if (indexToTriangleIndexMap[geoIndex3] === undefined) {
                indexToTriangleIndexMap[geoIndex3] = [triangleIndex];
            } else {
                indexToTriangleIndexMap[geoIndex3].push(triangleIndex);
            }
            //indexArray[triangleIndex*3] = triangleIndexVertexArray[0];
            //indexArray[triangleIndex*3+1] = triangleIndexVertexArray[1];
            //indexArray[triangleIndex*3+2] = triangleIndexVertexArray[2];
        }
        
        let geometryTriangleArray = [];
        let index = 0;
        while (index<indexToTriangleIndexMap.length && missingVertices>0 && missingTriangles>0){
            let out = [];
            if (indexVisitedArray[index] === 0) {
                out = computeTriangles(index);
            }
            if (out.length > 0) {
                geometryTriangleArray.push(out);
            }
            index += 1;
        }
        
        let geometryArray = [];
        for (let i=0; i<geometryTriangleArray.length; i++) {
            let out = {
                positionArray: [],
                colorArray: [],
                indexArray: [],
                indexMap: [],
                currentIndex: 0
            }
            let triangleArray = geometryTriangleArray[i];
            
            for (let j=0; j<triangleArray.length; j++) {
                let triangleIndex = triangleArray[j];
                let rootIndex = indexArray[triangleIndex*3];
                if (out.indexMap[rootIndex] === undefined) {
                    out.indexMap[rootIndex] = out.currentIndex;
                    // add vertex position and color
                    out.positionArray.push(
                        geometry.attributes.position.array[rootIndex*3],
                        geometry.attributes.position.array[rootIndex*3+1],
                        geometry.attributes.position.array[rootIndex*3+2]
                    );
                    if (geometry.attributes.color != undefined) {
                        out.colorArray.push(
                            geometry.attributes.color.array[rootIndex*3],
                            geometry.attributes.color.array[rootIndex*3+1],
                            geometry.attributes.color.array[rootIndex*3+2]
                        );
                    }
                    out.currentIndex += 1;
                }
                
                let child1Index = indexArray[triangleIndex*3+1];
                if (out.indexMap[child1Index] === undefined) {
                    out.indexMap[child1Index] = out.currentIndex;
                    // add vertex position and color
                    out.positionArray.push(
                        geometry.attributes.position.array[child1Index*3],
                        geometry.attributes.position.array[child1Index*3+1],
                        geometry.attributes.position.array[child1Index*3+2]
                    );
                    if (geometry.attributes.color != undefined) {
                        out.colorArray.push(
                            geometry.attributes.color.array[child1Index*3],
                            geometry.attributes.color.array[child1Index*3+1],
                            geometry.attributes.color.array[child1Index*3+2]
                        );
                    }
                    
                    out.currentIndex += 1;
                }
                
                let child2Index = indexArray[triangleIndex*3+2];
                if (out.indexMap[child2Index] === undefined) {
                    out.indexMap[child2Index] = out.currentIndex;
                    // add vertex position and color
                    out.positionArray.push(
                        geometry.attributes.position.array[child2Index*3],
                        geometry.attributes.position.array[child2Index*3+1],
                        geometry.attributes.position.array[child2Index*3+2]
                    );
                    if (geometry.attributes.color != undefined) {
                        out.colorArray.push(
                            geometry.attributes.color.array[child2Index*3],
                            geometry.attributes.color.array[child2Index*3+1],
                            geometry.attributes.color.array[child2Index*3+2]
                        );
                    }
                    
                    out.currentIndex += 1;
                }
                
                // Add indices:
                out.indexArray.push(out.indexMap[rootIndex], out.indexMap[child1Index], out.indexMap[child2Index]);
            }
            
            const geoPositions = new Float32Array(out.positionArray);
            const geoColors = new Float32Array(out.colorArray);
            const geoIndices = new Uint32Array(out.indexArray);
            const geo = new THREE.BufferGeometry();
            geo.name = "G_" + i;
            geo.index = new THREE.BufferAttribute(geoIndices, 1, false);
            geo.attributes.position = new THREE.BufferAttribute(geoPositions, 3, false);
            geo.attributes.color = new THREE.BufferAttribute(geoColors, 3, true);
            geo.computeBoundingSphere();
            geo.computeBoundingBox();
            geometryArray.push(geo);
        }
        return geometryArray;
    }

Answer 2

I tried with a function but still is not accurate, it produce more geometries than non connected geometries:

If somebody could have a look on it, it would be grate.

function groupGeometryIntoNonConnectedGeometries(geometry) {
        const material = new THREE.MeshBasicMaterial({
            side: THREE.DoubleSide,
            vertexColors: THREE.VertexColors
        });
        let geometryArray = [];
        const indexArray = geometry.index.array;
        const positionArray = geometry.attributes.position.array;
        const positionCount = geometry.attributes.position.count;
        const color = new THREE.Vector3(geometry.attributes.color.array[0], geometry.attributes.color.array[1], geometry.attributes.color.array[2]);
        const totalTriangles = indexArray.length / 3;
        let geometryCount = 0;
        let indexValueAlreadyVisited = new Uint8Array(indexArray.length);   
        let structure = [];
            /*
             * indexValue: {
             *  child: [ [indexval0, indexval1], [] ],
             *  parent: null
             * }
             */
        // Initialize Structure:
        for (var vextexIdx=0; vextexIdx<positionCount; vextexIdx++) {
            structure[vextexIdx] = {
                child: [],
                parent: null
            }
        }   
        
        for (idx=0; idx<totalTriangles; idx++) {
            const geoIndex1 = indexArray[idx*3];
            const geoIndex2 = indexArray[idx*3+1];
            const geoIndex3 = indexArray[idx*3+2];
            const triangleIndexVertexArray = [ geoIndex1, geoIndex2, geoIndex3 ].sort(function(a, b) { 
                return a - b; 
            });
            structure[ triangleIndexVertexArray[0] ].child.push(triangleIndexVertexArray[1], triangleIndexVertexArray[2]);
            structure[ triangleIndexVertexArray[1] ].parent = triangleIndexVertexArray[0];
            structure[ triangleIndexVertexArray[2] ].parent = triangleIndexVertexArray[0];              
        }
        let count = 0;
        let currentCount = 0;
        let geometryStructureArray = [];
        
        for (let strIdx=0; strIdx<structure.length; strIdx++) {
            if (structure[strIdx].parent == null) {
                currentCount = count;
                geometryStructureArray[currentCount] = {
                    name: "G_" + currentCount,
                    indexMap: {},
                    currentIndex: 0,
                    indexArray: [],
                    positionArray: [],
                    colorArray: []
                };
                count += 1;
            }
            if (structure[strIdx].child.length > 0) {
                const childLen = structure[strIdx].child.length / 2;
                for (let childIdx=0; childIdx<childLen; childIdx++) {
                    const vertexIndex0 = strIdx;
                    const vertexIndex1 = structure[strIdx].child[childIdx*2];
                    const vertexIndex2 = structure[strIdx].child[childIdx*2+1];
                    const v0 = new THREE.Vector3( positionArray[strIdx*3], positionArray[strIdx*3+1], positionArray[strIdx*3+2] );
                    const v1 = new THREE.Vector3( positionArray[vertexIndex1*3], positionArray[vertexIndex1*3+1], positionArray[vertexIndex1*3+2] );
                    const v2 = new THREE.Vector3( positionArray[vertexIndex2*3], positionArray[vertexIndex2*3+1], positionArray[vertexIndex2*3+2] );
                    
                    // check vertex0
                    if (geometryStructureArray[currentCount].indexMap[vertexIndex0] == undefined) {
                        geometryStructureArray[currentCount].indexMap[vertexIndex0] = geometryStructureArray[currentCount].currentIndex;
                        geometryStructureArray[currentCount].indexArray.push(geometryStructureArray[currentCount].currentIndex);
                        geometryStructureArray[currentCount].positionArray.push(v0.x, v0.y, v0.z);
                        geometryStructureArray[currentCount].colorArray.push(color.x, color.y, color.z);
                        geometryStructureArray[currentCount].currentIndex += 1;
                    } else {
                        geometryStructureArray[currentCount].indexArray.push(geometryStructureArray[currentCount].indexMap[vertexIndex0]);
                    }
                    
                    // check vertex1
                    if (geometryStructureArray[currentCount].indexMap[vertexIndex1] == undefined) {
                        geometryStructureArray[currentCount].indexMap[vertexIndex1] = geometryStructureArray[currentCount].currentIndex;
                        geometryStructureArray[currentCount].indexArray.push(geometryStructureArray[currentCount].currentIndex);
                        geometryStructureArray[currentCount].positionArray.push(v1.x, v1.y, v1.z);
                        geometryStructureArray[currentCount].colorArray.push(color.x, color.y, color.z);
                        geometryStructureArray[currentCount].currentIndex += 1;
                    } else {
                        geometryStructureArray[currentCount].indexArray.push(geometryStructureArray[currentCount].indexMap[vertexIndex1]);
                    }
                    
                    // check vertex1
                    if (geometryStructureArray[currentCount].indexMap[vertexIndex2] == undefined) {
                        geometryStructureArray[currentCount].indexMap[vertexIndex2] = geometryStructureArray[currentCount].currentIndex;
                        geometryStructureArray[currentCount].indexArray.push(geometryStructureArray[currentCount].currentIndex);
                        geometryStructureArray[currentCount].positionArray.push(v2.x, v2.y, v2.z);
                        geometryStructureArray[currentCount].colorArray.push(color.x, color.y, color.z);
                        geometryStructureArray[currentCount].currentIndex += 1;
                    } else {
                        geometryStructureArray[currentCount].indexArray.push(geometryStructureArray[currentCount].indexMap[vertexIndex2]);
                    }
                    
                }
            }   
        }
        
        // Convert to geometryArray:
        const geometryStructureArrayLen = geometryStructureArray.length;
        const object3d = new THREE.Object3D();
        
        for (let geoIdx=0; geoIdx<geometryStructureArrayLen; geoIdx++) {
            const geo = new THREE.BufferGeometry();
            geo.name = "G_" + geoIdx;
            const geoPositions = new Float32Array(geometryStructureArray[geoIdx].positionArray);
            const geoColors = new Float32Array(geometryStructureArray[geoIdx].colorArray);
            const geoIndices = new Uint32Array(geometryStructureArray[geoIdx].indexArray);
            //console.log(geoIdx, "geoPositions: ", geoPositions);
            //console.log(geoIdx, "geoColors: ", geoColors);
            //console.log(geoIdx, "geoIndices: ", geoIndices);
            geo.index = new THREE.BufferAttribute(geoIndices, 1, false);
            
            geo.attributes.position = new THREE.BufferAttribute(geoPositions, 3, false);
            geo.attributes.color = new THREE.BufferAttribute(geoColors, 3, true);
            geo.computeBoundingSphere();
            geo.computeBoundingBox();
            
            const mesh = new THREE.Mesh(geo, material);
            mesh.name = "M_" + geoIdx;
            object3d.add(mesh);
        }
        //return [structure, geometryStructureArray, object3d, count];
        return object3d;
    }

Best regards

Answer 3

No. three.js does not have functionality for identifying geometry 'islands' in a mesh.

When using MeshFaceMaterial, WebGLRenderer breaks the geometry into chunks anyway -- one chunk for each material. It does that because WebGL supports one shader per geometry.

I would not merge all your geometries, and then use MeshFaceMaterial, only to have the renderer break the single geometry apart.

You can merge geometries that share a single material if you wish.

three.js r.69