Mesh optimization support

[IntellectualKitty]

Github user zeux has a tiny, freely available mesh optimization library available at https://github.com/zeux/meshoptimizer under the MIT license that includes pre-transform, post-transform, and overdraw optimization support. The interface is simple and easy to use, requiring access only to indices and vertex positions in a fashion similar to glVertexPointer.

As someone still fairly new to Cinder, I'm not yet fluent enough to say where it would be best to integrate such a library, whether in TriMesh, VboMesh, or Batch. However, it would be almost trivial to integrate it with Cinder.

The library is based on the Tipsy paper. I wrote a similar library (unpublished) a number of years back, but zeux's library is more complete and his implementation may be better than mine. What I learned from the experience is that mesh optimization can have a powerful effect on performance, particularly when using large, complex meshes.

This is something that I will need in the project that I'm working on, and I suspect that it would benefit other users as well. If there is interest in doing this, I think it would be best accomplished by someone more familiar with Cinder. However, if someone can give me some guidance about the best way to do the integration (I'm most familiar with TriMesh, which is where I'd start on my own), I'd be glad to do it (but it might be several weeks before I can get to it).

[paulhoux]

Hi, thanks for pointing to this library. Have you tried it yourself? If so, did you test how much of an improvement it is? I could imagine that it should be pretty easy for users to add this library to their project if they need the performance boost. I am not sure if it is such a major game changer that it should be added to Cinder by default. But of course that is not up to me :)

[IntellectualKitty]

I tested a wide variety of OBJ files with the mesh optimization tool that is included, and was very impressed with the statistics that it reported. From past experience, I knew what to expect from each different type of model. And it was clear that his implementation was at least as good as mine, and definitely more thorough.

As for actual performance testing, the answer is no. I'm not set up to do that yet. I'm still rather new to Cinder, and I'm only able to work on this in my very limited spare time. My goal is to use Cinder to revive a project that I was working on a few years ago – a hyper-realistic space combat simulator with highly detailed models. Which, of course, is why I'm interested in mesh optimization. So, I'm not able to report any real results, and it's been long enough since I was working on that old project that I'd be making up numbers if I tried to recall the speedup that I got with my own code.

One of the really nice things about Tipsy-based optimization is that it is extremely fast. By that, I mean fast enough for interactive use such as with a 3D modeling app. You wouldn't be able to perform optimization every frame, but you should easily be able run a background thread that performed mesh optimization once per second and the user would never know.

The one hard part about mesh optimization is determining the size of the post-transform vertex cache. As I seem to recall from years ago, it was difficult or even impossible to try to query this information from the GPU. I doubt things have improved because I wasn't able to get anything when I was Googling post-transform vertex cache sizes the other night.

Knowing the cache size is pretty important since, if you overestimate, you'll actually be tuning for cache misses and your "optimization" could be making things worse than random order. So, when in doubt, it's always best to underestimate the cache size. Given how fast mesh optimization is, it's certainly possible to determine the optimal cache by performance testing at runtime – for instance, the first time the application starts up (or if there's been a hardware change) – but it's far easier to optimize your meshes during development using the lowest end hardware that you plan to support.

Zeux's library works around this issue by also offering a pre-transform optimization that "does not try to model cache replacement and instead just orders vertices in the order of their use, which generally produces results that are close to optimal on real meshes," to quote his README. I didn't include that type of optimization in my code, so I have no experience with it, but my guess is that he's probably correct.

My experience has been with complex meshes with lots of overdraw, which makes mesh optimization pretty important for my rather special case. But I have no experience with instancing lots of small meshes with limited overdraw, which is certainly more common. However, if you're transforming a large number of vertices, I suspect that the benefit with either pre- or post-transformation could be significant. To answer your original question, I don't currently have any numbers that I can give you, but mesh optimization is beneficial enough that it has been actively researched (see the link to the Tipsy paper in my original post).

The nice thing about mesh optimization is that, apart from the difficulties with determining cache size, it is both fast and easy to perform. The benefit of the Tipsy paper that Zeux's library is based on is that the results were as good or better than previous methods, but it was fast enough to be used at runtime. From the very impressive projects gallery that Cinder has, it seems like people are using Cinder for some pretty intensive work. So, incorporating mesh optimization could be a big win for a lot of people without a lot of effort involved.

[IntellectualKitty]

I should also add that Hugues Hoppe of Microsoft Research did significant work into mesh optimization. Here's a link to his paper.

I'm a macOS guy so I'm not very familiar with Microsoft products, but I believe that they incorporated this work and also the work that he did on mesh simplification into Direct3D.

Here is a link to Hoppe's mesh processing library on Github.

[richardeakin]

I've only skimmed the info on tipsy, but it appears it is meant to make the mesh data more gpu friendly, which seems interesting. I would think you could use this as a post step when exporting your model, but maybe I'm not aware of all that the tipsify algo has to offer.

If you wanted to use it directly in cinder, keep in mind that gl::VboMesh (and its more commonly used counterpart, gl::Batch) take in a geom::Source to load data, as seen here. Model loaders, such as cinder's basic ObjLoader implement this so that they can be efficiently uploaded to the gpu in as few steps as possible. You typically don't need to use a TriMesh when dealing with exported models, or even cinder's GeomIO library (you can see those here in the right column).

My suggestion would be to experiment with how you could utilize this mesh optimization as a step that fits within this geom::Source ecosystem, and I don't think you'll need to modify any of cinder's sources to do so. You could start by getting its data output to a TriMesh as that is usually the easiest to figure out, though you'll probably want it to be a subclass of either geom::Source or even geom::Modifier (unforunately not much documentation on that one yet, but it lives here).

Then if you like, you can package what you come up with as a cinderblock so others can easily use it. We do incorporate blocks into core, but only after a good deal of real world testing and considering the extra dependency weight. Seeing it used in your space sim would be a great start. :)

[IntellectualKitty]

@richardeakin thanks for the guidance about how to go about incorporating this.

"[Making] mesh data more gpu friendly" is a perfect description. There are two parts. First, triangles are ordered within the mesh so that, for any given orientation, they are drawn in front to back to order as much as possible to reduce pixel processing cost based on early Z-test rejection (aka, reducing overdraw). Second, vertices are ordered to maximize utilization of the post-transform vertex cache to reduce the vertex processing load.

I haven't seriously worked with or contributed to a project that utilizes extensible packages before, but that is a sensible engineering approach. My thinking had simply been that incorporating this into the core would make it readily available for people.

[IntellectualKitty]

@richardeakin I'm afraid that the more I study your comment, the more I realize I don't understand it.

I believe I understand the point of geom::Source as the abstract basis for other types of geometry, but the purpose or at least the usage of geom::Modifiers eludes me.

Incidentally, the geom::Modifiers::Params class looks like it's missing the protected: keyword on line 195 or 196 for its data members.

At this point, I think the easiest thing for me at my level of experience with Cinder is to try to incorporate the mesh optimization into TriMesh. It already has the vertex attributes and indices as members, and I feel comfortable adding it there because, as I think about it at least, it's implicitly a TriMesh operation.

Incidentally, I noticed that TriMesh has a verticesEqual() function, but it doesn't seem to be used anywhere. I searched the whole repository. Were you planning to provide a function to join equal vertices? That's the type of mesh cleanup that I wanted to add anyway, along with the mesh optimization that we've already been discussing. (I generally don't have a lot of trust in mesh exporters doing the right thing, so I generally gravitate to incorporating mesh cleanup and optimization into the engine. Also, I think it makes life easier to have that in one place rather than trying to incorporate it into each exporter or loader.)

Something else I noticed is that the TriMesh::calcBoundingBox() seems like it should actually be part of AxisAlignedBox, similar to Sphere::calculateBoundingSphere( const std::vector &points ).

To reiterate my previous point, I think TriMesh is the best place for me to include mesh optimization because I have a clear understanding of that class (and it's easily usable in a Batch). But if you think I'm barking up the wrong tree, please let me know.

EDIT: Obviously that wouldn't work with a cinderblock. So, what's the most helpful thing I can do in that case? Report my results back here so we can discuss them and how to proceed from there?

[andrewfb]

I think this is definitely an interesting project, so thanks for taking a look at it. I think most of us who've used techniques like this have done so with outboard tools. I think it's worth weighing the potential benefits of having integrated functionality against those of having it as a standalone tool - perhaps one written in Cinder even.

I'd say for me, the primary use-case for its implementation in Cinder (whether into the core or as a CinderBlock) would be for dynamically generated geometry. In the case where the geometry is known ahead of time, whatever asset pipeline you're using would presumably be augmented to do mesh optimization. However if you're generating the geometry on the fly in some sense - including geometry that is user submitted, say by opening an OBJ file - obviously you wouldn't have that luxury, and you'd have to perform the processing at runtime.

The geom:: pipeline is meant for procedurally creating geometry. geom::Sources are straightforward, and Modifiers are meant to perform some sort of manipulation of the geometry, and can be chained together. This post from the old forum provides some visual reference for use cases. An example Modifier starting point might be geom::Twist - implementation here.

Another good reference would be geom::Subdivide which is probably the most similar to what you'd be doing.

TriMesh input( ... );
TriMesh output( input >> geom::Optimize().exampleParam( 2.0 ) );

gl::Batch optSphere( geom::Sphere() >> geom::Optimize() );

The pseudocode above demonstrates how a Modifier can be used both with TriMeshes and with geom::Source primitives like geom::Sphere, which is part of the appeal of it existing as a Modifier.

Writing code that directly manipulates a TriMesh seems like a reasonable starting point if you don't want to dig into writing a geom::Modifier immediately. However I'd say if you'd rather go that route, I'd recommend a free function so that it could be a CinderBlock; something like say,
TriMesh optimize( const TriMesh &input ) assuming there's no strong reason to modify the input TriMesh directly.

We often use CinderBlocks as a testing ground for new features, allowing the API to settle out, and also to gauge user interest and use cases. If this feature proved to be popular, I could certainly see it finding its way into core at some point.

[IntellectualKitty]

@andrewfb Thank you! This makes it a lot clearer!

These are really good suggestions. And I can see the value and purpose of geom::Modifier now.

I can also see that it's not going to be quite as straightforward as I thought. I can see geom::Modifier being used with any geom::Source for operations that would be applicable regardless of primitive type like pre-transform optimization and joining equal vertices. But overdraw optimization would be applicable only if the primitive type is triangles.

Just so I'm clear on the best approach to use, is using geom::Modifier the best route for something like overdraw optimization even if it's restricted to a specific primitive type? In the geom::Subdivide code you linked to, if the primitive type isn't triangles, the error is logged and the operation is aborted. Should I take that to be the standard procedure to use?

Again, thank you for clearing this up. After this weekend, it's probably going to be a few weeks before I'm going to be able to get back to this. But I think it's going to be far easier now.

[andrewfb]

Yes - I'd say logging an error is the right response to someone trying to optimize a primitive type for which it doesn't make sense. For bonus points you might also handle TRIANGLE_STRIP and TRIANGLE_FAN as input while still outputting TRIANGLES. geom::Subdivide could be improved in that regard.

[IntellectualKitty]

Now that I'm starting to get a feel for this, I think a better approach would be to create geom::Modifiers specifically for the purpose of converting TRIANGLE_STRIP and TRIANGLE_FAN to TRIANGLES, and then feed the output to the appropriate geom::Modifiers for optimization. I always find it better to break up complex tasks into small, manageable pieces that are focused on a specific purpose because they are easier to develop, easier to understand, less error prone, and more reusable. For instance, geom::Modifiers that broke up TRIANGLE_STRIP and TRIANGLE_FAN into TRIANGLES could then be used as input for geom::Subdivide and then geom::Subdivide wouldn't need to be altered.

I have not tested it, but from what I've read it seems that triangle strips aren't significantly faster than regular triangle lists on modern hardware. So, I don't currently have plans to use anything but regular triangles in my project.

[IntellectualKitty]

For anyone who is interested, the author of the mesh optimization library and I have had some discussions that I found very educational. I came away suitably impressed with the Tipsy algorithm and realized that my concerns about overdraw optimization were overblown (at least as far as Tipsy's ability to optimize for it).

My own performance results were very interesting. The conclusion that I came to is that geometry is very sensitive to optimization. The caveat is that the degree of mesh optimization that can be performed depends on how close to optimal the geometry already is. That may sound like a no-brainer, but computed geometry is often already in a relatively good state by nature and because of the natural locality in the modeling process, traditional geometry can be as well.

What I ultimately ended up doing was pre-sorting vertices and triangles in random order to establish a consistent baseline for testing. What I found was that it was relatively easy to get a 50-100% speedup from that baseline. In addition to the state that the geometry original was in, I sometimes used Assimp – which includes a vertex-cache only (no overdraw reduction) variant of the Tipsy algorithm – instead of Cinder's builtin ObjLoader. So, the results that I obtained when simply loading the geometry varied based on the nature of the geometry itself and the loader used, from relatively little to very high.

@andrewfb 's comments – as well as the ease of use of zeux's library – made it very easy to implement mesh optimization as a geom::Modifier. I don't plan to put together a Cinder Block since I'm already maintaining a fork of Cinder, but the code is relatively trivial to write. I have no plans in the immediate future to add it to my Cinder fork since it's already embedded in my application, but I'd be happy to put together a PR if and when I do if there's any interest.