Mesh simplification function

It would be useful to have a mesh simplification function in Three.js. I have noticed that some external libraries, for example the ThreeCSG.js, create meshes with lots of unnecessary triangles, which could be optimized away, since they are co-planar and adjacent.

Perhaps a useful way to implement this would be to define a new kind of mesh that is a list of 2D Shapes and their 3D plane and 3D position. Then add functions that convert regular meshes to and from this format.

Author: Fantashit

7 thoughts on “Mesh simplification function

  1. Apologies for abandoning this thread for sometime. Since @mattdesl pinged me on this, here’s some updates

    • With regards to scale @bhouston, some initial measurement shows that it takes about 2-3ms to reduce a single vertex. https://twitter.com/BlurSpline/status/741625571432534017/photo/1
    • From my rough estimates to reduce a geometry by 1000 vertices might take 3s, 10000 vertices might take 30s, 100K vertices might take 5 minutes.
    • I haven’t looked into optimization of the code yet, and I do not have comparison to how other algorithms work so I don’t have a gauge to whether how fast or slow this is.
    • The first time I’m trying to do is first get my code to run with the current three.js version. It might require me to work with BufferGeometry instead, so I’ll try to see how it goes.
  2. I added textures support and just came back a couple of days ago to add normals support so normals don’t have to be recalculated after optimisation(this prevents damaging edges and making them look too round)

    60%% faces removed on the right:
    image
    image

    Here’s my playground https://codesandbox.io/s/2o51o1q27p

    Press “optimizeModel” to recalculate

    For development purposes I added drag and drop for 3DS, DAE, FBX so you can just drop files where the Elf figure currently is and see how other models are working with this

  3. I’ve rewritten the whole thing to remove Vertex and Triangle custom classes and turn all data into flat typed arrays with SharedArrayBuffers to support workers and sharing memory.

    https://codesandbox.io/s/qvx30mkzo6

    Each worker gets its range of vertices to process. Number of vertices / total workers * current worker

    Race conditions in workers and general mess of early prototype make optimisation fail sometimes and “optimizeModel” has to be clicked to try again. workersAmount in line 1379 sets amount of workers(defaults to navigator.hardwareConcurrency)
    FIELDS_NO sets amount of fields for faces and neighbours belonging to each vertex(these are 2 flat arrays. Their length: number of vertices * 50 fields for data each), currently it’s set to 50 but it also works with 20 or 1000, there’s also support for oversized fields in separate arrays. These oversize arrays are being copied instead of shared when creating workers so this needs improving.

    Without stopping rendering in Codesandbox
    Tested 22MB model with 225k vertices on 2 years old XPS 15 with i5 6300hq 4 cores and no hyper threading
    main thread only – 120 seconds
    1 worker – 120 seconds
    2 workers – 33 seconds
    3 workers – 21 seconds
    4 workers – 14 seconds

    On my PC with 16 cores works in 4-5 seconds when using 8 workers

    Due to security problems SharedArrayBuffer was disabled in Chrome for a while but now it’s enabled by default.

    Here’s the model I’m using for testing https://free3d.com/3d-model/angel-lucy-sculpture-46454.html
    Drag and drop FBX file where the doll is. The time being measured console.time("Mesh simplification"); is after model is loaded to before it’s reassembled back into BufferGeometry. Reassembling takes ages due to faulty mesh result which must be worked on

    Update:
    The problem with vertex not being found is caused by workers working simultaneously in the same area. For now I limited amount of workers so each has to process at least 2000 vertices to avoid overcrowding. Synchronising start time instead of allowing each to work straight after receiving data may also help keeping them further away. For now try catch and retrying operation on the same vertex when computing edge collapse helped with 90%% failures. Probably these problems can be solved or greatly improved without introducing communication between workers or atomics, which would be fun but too complex for now.

  4. I used edge length indexing on a private version of the simplifier to give about a two orders of magnitude speedup. With some time I could isolate that code and integrate it into this implementation.

  5. https://codesandbox.io/s/xrlplpmr1q fixed problems with very distorted mesh when loading BufferGeometry directly without Geometry

    Update: there was a problem with the optimiser intermittently failing due to workers working on the same vertex simultaneously(neighbour vertex might be in another worker’s working range). I just added vertexWorkStatus array that holds work status for the vertex and the neighbour vertex with which it creates the edge. Now before collapsing an edge workers check the status of the vertices and that intermittent error should be prevent.
    Update 2: There was a problem with larger models because neighbours data array was using Int16Array but if there are more than 32768 vertices it should use Int32Array. Now this is fixed so models with hundreds of thousands of vertices will work correctly. Like this one https://free3d.com/3d-model/angel-lucy-sculpture-46454.html

Comments are closed.