Simplify mesh via approximation algorithm

Apologizing in advance if this is already covered in the docs and I just missed it or haven’t used the right search term.

I want to simply my rendered meshes with an approximation algorithm like this
https://doc.cgal.org/latest/Surface_mesh_approximation/index.html
and use the result for my physics collision meshes.

I’ve seen these docs:

But it’s not clear to me exactly how to do this in the manner that I want to accomplish.

I will say, that when I render the edges of my meshes using this method:

export const showMeshEdges = (
  mesh: Mesh,
  epsilon = 0.999,
  color = new Color4(0, 0, 1, 1)
) => {
  mesh.enableEdgesRendering(epsilon)
  mesh.edgesWidth = 4.0;
  mesh.edgesColor = color;
}

The resulting polygons look like what I would want to use. Is there a way to get a mesh out of that?

1 Like

When the simplification algorithm runs, the result mesh is added as a LOD mesh to the main mesh. You can recover the LOD levels of a mesh using getLODLevelAtDistance or getLODLevels: Mesh | Babylon.js Documentation (babylonjs.com), then clone the mesh you want (so it’s not attached to the main mesh anymore) and do whatever you want with it :smiley:

Here’s an example where I cloned a simplified mesh and positioned independently of the original one: Manipulate decimated mesh | Babylon.js Playground (babylonjs.com)

No apologies needed, the docs don’t make that clear :slight_smile:

3 Likes

Took the opportunity to add this as an example to the simplification page: Update In-Browser_Mesh_Simplification.md by carolhmj · Pull Request #471 · BabylonJS/Documentation (github.com) :slight_smile:

3 Likes

Okay awesome! I’ll try this out and then I’ll render the edges of the resulting mesh to get a feel for the results. Which simplification algorithm does this use?

I tried to see it from this page

But the link there-

An implementation of the Quadratic Error simplification algorithm.
Original paper : http://www1.cs.columbia.edu/~cs4162/html05s/garland97.pdf

is dead. I’m guessing it’s not the same as this one
https://doc.cgal.org/latest/Surface_mesh_approximation/index.html

but if it produces good results then I’m totally happy with that.

And also thank you!

You’re welcome! I don’t think it’s the same as the CGAL one, but I’ll just tag the author of the method @RaananW to confirm that :slight_smile:

A few other links:
https://users.csc.calpoly.edu/~zwood/teaching/csc570/final06/jseeba/ , and
http://www.cs.cmu.edu/~garland/Papers/quadrics.pdf

Looking at the name (and without digging too much into the algorithms), it doesn’t seem to be the same as the one you linked to. but it does provide good results :slight_smile:

2 Likes

@carolhmj @RaananW So here’s some screen shots of the results I get:

image

I was expecting the colors to look a bit off according to what the docs said, but I was hopping the overall shape of each mesh would be retained. I think this might have something to do with the meshes not being “optimized” - something to do with overlapping indices?

If this is the case, do either of you know how to fix this? The result I’m going for here with the collision meshes is that they represent a watered down version of the objects I want them to become physics imposters for, that way the memory load remains low when I instantiate mesh imposters for each.

The version we had implemented is not taking textures into account, and it does show. I don’t have any magic solution for that. What are the settings on your run?

This method gets called for each mesh

export const reduceMeshSize = (mesh: Mesh): Promise<Mesh|null> => {
  const totalVert = mesh.getTotalVertices() || 0

  let quality = 1.0
  if (totalVert > 500) { // for meshes with vertices, V, 500 < V < 1000 quality factor is above 1, but fixing this doesn't affect the results
    quality = 1000 / totalVert
  }
  const parallelProcessing = true
  const type = SimplificationType.QUADRATIC

  return new Promise<Mesh | null>((resolve) => {
    const successCallback = () => {
      console.log('simplified mesh success callback, mesh: ', mesh.id, mesh)
      resolve(mesh.getLODLevelAtDistance(0))
    }

    console.log('calling simplify: ', totalVert, quality)

    mesh.simplify(
      [{ distance: 0, quality, optimizeMesh: true }],
      parallelProcessing,
      type,
      successCallback
    )
  })
}
                total vertices, quality factor
gameUtils.ts:989 calling simplify:   438 1
gameUtils.ts:989 calling simplify:  13351 0.07490075649764062
gameUtils.ts:989 calling simplify:  11286 0.0886053517632465
gameUtils.ts:989 calling simplify:  4473 0.22356360384529397
gameUtils.ts:989 calling simplify:  7501 0.13331555792560992
gameUtils.ts:989 calling simplify:  7514 0.13308490817141336
gameUtils.ts:989 calling simplify:  3430 0.2915451895043732
gameUtils.ts:989 calling simplify:  8709 0.11482374555057986
gameUtils.ts:989 calling simplify:  5148 0.19425019425019424
gameUtils.ts:989 calling simplify:  9620 0.10395010395010396
gameUtils.ts:989 calling simplify:  3030 0.33003300330033003
gameUtils.ts:989 calling simplify:  2947 0.33932813030200204
gameUtils.ts:989 calling simplify:  11057 0.09044044496698923
gameUtils.ts:989 calling simplify:  6209 0.16105653084232566
gameUtils.ts:989 calling simplify:  13184 0.07584951456310679
gameUtils.ts:989 calling simplify:  2408 0.4152823920265781
gameUtils.ts:989 calling simplify:  913 1.095290251916758
gameUtils.ts:989 calling simplify:  192 1
gameUtils.ts:989 calling simplify:  45 1
gameUtils.ts:989 calling simplify:  132 1
gameUtils.ts:989 calling simplify:  766 1.3054830287206267
gameUtils.ts:989 calling simplify:  7030 0.1422475106685633
gameUtils.ts:989 calling simplify:  6797 0.14712373105781962
gameUtils.ts:989 calling simplify:  107 1
gameUtils.ts:989 calling simplify:  212 1
gameUtils.ts:989 calling simplify:  3058 0.3270111183780249
gameUtils.ts:989 calling simplify:  5354 0.1867762420620097
gameUtils.ts:989 calling simplify:  116 1
gameUtils.ts:989 calling simplify:  5190 0.1926782273603083
gameUtils.ts:989 calling simplify:  1081 0.9250693802035153
gameUtils.ts:989 calling simplify:  855 1.1695906432748537
gameUtils.ts:989 calling simplify:  6926 0.14438348252959862
gameUtils.ts:989 calling simplify:  11134 0.08981498113885396
gameUtils.ts:989 calling simplify:  2887 0.3463803255975061
gameUtils.ts:989 calling simplify:  3388 0.29515938606847697
gameUtils.ts:989 calling simplify:  1887 0.5299417064122947
gameUtils.ts:989 calling simplify:  1555 0.6430868167202572
gameUtils.ts:989 calling simplify:  115 1
gameUtils.ts:989 calling simplify:  4168 0.2399232245681382
gameUtils.ts:989 calling simplify:  12343 0.08101758081503686
gameUtils.ts:989 calling simplify:  414 1
gameUtils.ts:989 calling simplify:  4669 0.21417862497322768
gameUtils.ts:989 calling simplify:  8974 0.11143302874972141
gameUtils.ts:989 calling simplify:  1613 0.6199628022318661
gameUtils.ts:989 calling simplify:  9734 0.10273268954181221
gameUtils.ts:989 calling simplify:  1699 0.5885815185403178
gameUtils.ts:989 calling simplify:  10187 0.09816432708353784
gameUtils.ts:989 calling simplify:  34 1
gameUtils.ts:989 calling simplify:  12057 0.0829393713195654
gameUtils.ts:989 calling simplify:  84 1
gameUtils.ts:989 calling simplify:  10570 0.0946073793755913
gameUtils.ts:989 calling simplify:  206 1
gameUtils.ts:989 calling simplify:  9013 0.11095084877399312
gameUtils.ts:989 calling simplify:  1111 0.9000900090009001
gameUtils.ts:989 calling simplify:  6319 0.1582528881152081
gameUtils.ts:989 calling simplify:  48 1
gameUtils.ts:989 calling simplify:  10850 0.09216589861751152
gameUtils.ts:989 calling simplify:  2430 0.411522633744856
gameUtils.ts:989 calling simplify:  96 1
gameUtils.ts:989 calling simplify:  11229 0.0890551251224508
gameUtils.ts:989 calling simplify:  5929 0.16866250632484397
gameUtils.ts:989 calling simplify:  5033 0.1986886548778065
gameUtils.ts:989 calling simplify:  7232 0.13827433628318583
gameUtils.ts:989 calling simplify:  8072 0.12388503468780972
gameUtils.ts:989 calling simplify:  2005 0.49875311720698257
gameUtils.ts:989 calling simplify:  1970 0.5076142131979695
gameUtils.ts:989 calling simplify:  4384 0.2281021897810219
gameUtils.ts:989 calling simplify:  9750 0.10256410256410256
gameUtils.ts:989 calling simplify:  8192 0.1220703125
gameUtils.ts:989 calling simplify:  6836 0.14628437682855472
gameUtils.ts:989 calling simplify:  6895 0.145032632342277
gameUtils.ts:989 calling simplify:  17694 0.05651633322030067
gameUtils.ts:989 calling simplify:  1421 0.7037297677691766
gameUtils.ts:989 calling simplify:  283 1
gameUtils.ts:989 calling simplify:  496 1
gameUtils.ts:989 calling simplify:  11705 0.08543357539513029
gameUtils.ts:989 calling simplify:  5104 0.19592476489028213
gameUtils.ts:989 calling simplify:  154 1
gameUtils.ts:989 calling simplify:  10559 0.0947059380623165
gameUtils.ts:989 calling simplify:  153 1
gameUtils.ts:989 calling simplify:  310 1
gameUtils.ts:989 calling simplify:  8913 0.11219566924716706
gameUtils.ts:989 calling simplify:  7030 0.1422475106685633
gameUtils.ts:989 calling simplify:  7636 0.13095861707700368
gameUtils.ts:989 calling simplify:  8605 0.11621150493898896
gameUtils.ts:989 calling simplify:  8980 0.111358574610245
gameUtils.ts:989 calling simplify:  9153 0.1092537965694308
gameUtils.ts:989 calling simplify:  5378 0.1859427296392711
gameUtils.ts:989 calling simplify:  7851 0.12737230925996687
gameUtils.ts:989 calling simplify:  7854 0.12732365673542145
gameUtils.ts:989 calling simplify:  7766 0.12876641771825909
gameUtils.ts:989 calling simplify:  5431 0.18412815319462345
gameUtils.ts:989 calling simplify:  5802 0.1723543605653223
gameUtils.ts:989 calling simplify:  10073 0.09927529038022437
gameUtils.ts:989 calling simplify:  1483 0.6743088334457181
gameUtils.ts:989 calling simplify:  6544 0.1528117359413203
gameUtils.ts:989 calling simplify:  6694 0.14938751120406335
gameUtils.ts:989 calling simplify:  6390 0.1564945226917058
gameUtils.ts:989 calling simplify:  9173 0.10901558922925979
gameUtils.ts:989 calling simplify:  3546 0.2820078962210942
gameUtils.ts:989 calling simplify:  3234 0.30921459492888065
gameUtils.ts:989 calling simplify:  10662 0.09379103357719001
gameUtils.ts:989 calling simplify:  5643 0.177210703526493
gameUtils.ts:989 calling simplify:  4156 0.24061597690086622
gameUtils.ts:989 calling simplify:  2927 0.341646737273659
gameUtils.ts:989 calling simplify:  5572 0.17946877243359655
gameUtils.ts:989 calling simplify:  5194 0.19252984212552945
gameUtils.ts:989 calling simplify:  8154 0.1226391954868776
gameUtils.ts:989 calling simplify:  6817 0.14669209329617133
gameUtils.ts:989 calling simplify:  1957 0.510986203372509
gameUtils.ts:989 calling simplify:  6255 0.15987210231814547
gameUtils.ts:989 calling simplify:  15388 0.06498570314530804
gameUtils.ts:989 calling simplify:  51 1
gameUtils.ts:989 calling simplify:  7028 0.14228799089356858
gameUtils.ts:989 calling simplify:  1244 0.8038585209003215
gameUtils.ts:989 calling simplify:  13587 0.07359976448075366
gameUtils.ts:989 calling simplify:  15387 0.06498992656138299
gameUtils.ts:989 calling simplify:  1074 0.931098696461825

@RaananW another thing I realized, some of these meshes are monolithic and contain many trees as well as other objects. The algorithm we’re using probably doesn’t realize the need to distinguish the individual shapes nearly so much as the overall shape of the cluster of trees and such.

quality 1.0 should provide the same result, but simplification will still run! Once could argue that if quality => 1.0 it should simply return the mesh (and I wouldn’t argue with you :-)) but it wasn’t implemented this way. Could be an improvement though!
I am sure some meshes will not work well with this algorithm. It doesn’t fit any type of mesh, and eventually is meant for Auto-LOD. I wouldn’t trust it as a simplification algorithms to meshes near the camera

2 Likes

Hey @RaananW what do you know about the various decimation algos in use these days?

Hey,

Sorry, I am totally not updated… But TBH I doubt there are any new and exciting new players in this field. They were all invented at times when they were REALLY needed :wink: But this is just an assumption.

1 Like

I think this is very popular. GitHub - PixarAnimationStudios/OpenSubdiv: An Open-Source subdivision surface library.

Also will probably play well with usd and materialx . I think they are all member projects of the same open source foundation

1 Like

@jeremy-coleman What do you think of this one?

i think creating a map from the original model is probably much important than the decimation itself, like this:

For the sphere approximation, i guess the tldr is “We also proposed an algorithm…with a natural multi-resolution structure and an explicit control on its feature sensitivity”. That could be useful, but I think it’s probably safer to choose something being used by tons of people with budgets across projects in the billions of dollars. Implementing algorithms can be mentally rewarding but also time intensive, so I guess it really boils down to what you want to spend your time on

3 Likes

Yeah. I get where you’re coming from. I was exploring the SQEM algo because someone had already put in the work to implement it in c++. It was looking really exciting for a moment with the results I was getting until I realized that the researchers hadn’t yet figured out a good way to go back from spherical meshes to triangular meshes. So that was a dead end lol.

I did end up finding a great approach for the meantime:

  1. Use blender to generate a height map for the scene
  2. Create mesh from heightmap
  3. Create a physics mesh imposter from the created heightmap mesh
  4. Profit!

This is actually working really well for me right now, and I’m getting around all the previous memory errors I had before with ammo js.

1 Like