Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Thu Apr 17, 2014 1:58 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 21 posts ] 
Author Message
 Post subject: Reducing STL triangles with Meshlab
PostPosted: Sun Dec 01, 2013 8:20 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Now that Shapeways has eliminated their high polygon print option it's extra important for designers to get their model under 1 million triangles. Also, without the high polygon backdoor you can't as easily cheat the density discount so if you want to maximize the discount you need to get the whole print into one model.

Fortunately Meshlab makes it possible to reduce triangles. Shapeways has a post about it here however their post isn't specific to puzzles and it doesn't say anything about what to do when things go wrong. On every model I've tried to reduce, things have gone wrong.

So before I jump into details, you may be wondering "how much can I reduce my models and still have them print well?". My testing suggest you can reduce at least 3x and probably much more than that if you're careful. For the resolution of Shapeways' print process, 1M triangles should be enough for pretty much any puzzle. I reduced a model that was 3M triangles to 1M and compared the two prints visually and with calipers and could not find ANY difference at all.

Here is a part that shows why:
Attachment:
reduced_triangle_waste.png
reduced_triangle_waste.png [ 134.08 KiB | Viewed 1340 times ]
See how the triangles are disproportionately allocated to fillets? Well, on twisty puzzles the fillets are the smallest, least important, and more importantly, least accurately printed portion of parts. Solidworks exports parts with much more detail than can actually be printed. If you imagine the part as 0.1mm voxels you'll see how overly precise this model is.


Using Meshlab you can reduce the triangle counts of your models. I have a few tips for doing so:

  • Work on one copy of each part. DO NOT work on the whole model all at once.
  • Use Quadric Edge Collapse Decimation when possible
  • Very carefully inspect the reduced part for issues
  • Fall back on Clustering Decimation when there are problems with QECD
  • Don't bother to reduce parts more than necessary
  • You can reduce really small parts more since the triangles on those parts are already smaller compared to printer resolution
  • Focus on reducing the parts costing you the most triangles overall (factor in part counts)

I've reduced Carl's Real5x5x5 design for him so I have several examples.

When things go well you start out with a part like:
Attachment:
reduced_333_edge_before.png
reduced_333_edge_before.png [ 81.35 KiB | Viewed 1340 times ]

Then using Filters -> Remeshing, Simplification, and Reconstruction -> Quadric Edge Collapse Decimation:
Attachment:
reduced_qecd_box.png
reduced_qecd_box.png [ 92.51 KiB | Viewed 1340 times ]

You get:
Attachment:
reduced_333_edge_after.png
reduced_333_edge_after.png [ 75.41 KiB | Viewed 1340 times ]


Here is another example. Before:
Attachment:
reduced_555_tcenter2_before.png
reduced_555_tcenter2_before.png [ 160.42 KiB | Viewed 1340 times ]

After:
Attachment:
reduced_555_tcenter2_after.png
reduced_555_tcenter2_after.png [ 145.05 KiB | Viewed 1340 times ]

I encourage you to open both of those images up in new tabs and then switch back and forth between them to see the change.


However things don't always go well. The most common issue is a plane being extended into a fillet or across a corner. For example, here is the start piece:
Attachment:
reduced_333_edge_side_before.png
reduced_333_edge_side_before.png [ 62.76 KiB | Viewed 1340 times ]

But when you try QECD you get could get an issue like this (the planar simplification option reduces these issues a lot):
Attachment:
reduced_333_edge_side_problem.png
reduced_333_edge_side_problem.png [ 60.75 KiB | Viewed 1340 times ]


To fix this you can try rebuilding the mesh with Filters -> Remeshing, Simplification, and Reconstruction -> Cluster Decimation:
Attachment:
reduced_cd_box.png
reduced_cd_box.png [ 45.86 KiB | Viewed 1340 times ]

The smaller the cell size the closer the resulting mesh is to to the original and the less it is reduced. I usually try to rebuild the mesh with 0.5% or ever smaller cells first and then try QECD on the rebuilt mesh. Clustering Decimation is actually really close to the algorithm used by the Shapeways printers to discretize the mesh into a grid. If you keep the cells small you won't cause any issues. I usually play with the cell size and look at the resulting mesh to find a big enough cell size that there is meaningful reduction but not too big that I think there is a chance the part could be affected. In the case of this part, after Cluster Decimation the part looks like:
Attachment:
reduced_333_edge_side_step1.png
reduced_333_edge_side_step1.png [ 62.44 KiB | Viewed 1340 times ]

And then QECD works properly without causing any issues and I can further reduce the part to this:
Attachment:
reduced_333_edge_side_after.png
reduced_333_edge_side_after.png [ 56.66 KiB | Viewed 1340 times ]


The other type of issue you can run into with QECD is spikes like this:
Attachment:
reduced_555_face_problem.png
reduced_555_face_problem.png [ 56.82 KiB | Viewed 1340 times ]

As you can imagine, it's hard to make a working puzzle with spikes like that. (Actually, I don't think this part is printable...) Spikes can be very frustrating to work with. I usually try the Clustering Decimation trick to rebuild the mesh and then if I need to, further reduce the new mesh with QECD. I've found that if you use too small a cell size with Clustering Decimation, QECD will continue to trigger the spike problem. One sure way to avoid spikes is to turn off the QECD option "Optimal position of simplified vertices" but the resulting reduction is usually not all that great. You can try reducing the model only a little bit without "Optimal position of simplified vertices" and then try reducing it more by turning "Optimal position of simplified vertices" back on. This can often avoid forming spikes.

If you're a designer and you don't want to use Meshlab, or your model is giving you trouble, I'm willing to reduce and pack your designs for you. I bet even Oskar's 17x17x17 could be reduced to just a few packed 1M triangle models. Oskar, I'd love to give it a shot!

_________________
Prior to using my real name I posted under the account named bmenrigh.


Last edited by Brandon Enright on Sun Dec 01, 2013 9:32 pm, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Reducing STL triangles with Meshlab
PostPosted: Sun Dec 01, 2013 9:00 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
To prioritize which pieces to reduce and to keep track of how much each piece needed to be reduced I created a spreadsheet:
Attachment:
reduction_priority_table.png
reduction_priority_table.png [ 55.62 KiB | Viewed 1322 times ]


Some of the columns are generated by formulas based on values in the other cells which allows me to keep track of which pieces need the most work. Of course if you need to do some really dramatic triangle reduction you could put a lot more effort into figuring out which parts are the "best" ones to reduce and by how much.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Reducing STL triangles with Meshlab
PostPosted: Sun Dec 01, 2013 9:13 pm 
Offline
User avatar

Joined: Sat Apr 21, 2007 11:21 pm
Location: Marin, CA
I found that turning off "preserve normals" stopped spikes for me. It makes no sense, but I've reduced dozens of models now without spikes. I'd be curious to know if it also works on that part!

I have wished I could script up a reducer for multiple parts to prep them for Tom's packer!

EDIT -- By the way, it's very nice of you to spend the time putting this video together!

_________________
Jason Smith posted here as 'io' through 2012.
Visit Jason Smith's PuzzleForge on Shapeways!
Jason Smith's Puzzles - YouTube Channel.


Top
 Profile  
 
 Post subject: Re: Reducing STL triangles with Meshlab
PostPosted: Sun Dec 01, 2013 9:42 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
JasonSmith wrote:
I found that turning off "preserve normals" stopped spikes for me. It makes no sense, but I've reduced dozens of models now without spikes. I'd be curious to know if it also works on that part!
It does seem to work on all of the parts I've tried but I wonder if it's actually introducing a subtle problem where the normal of one or more triangles is flipped and the part no longer makes physical sense. I'm not sure how to use Meshlab to check for that or, more importantly, how to fix it if it does happen.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Reducing STL triangles with Meshlab
PostPosted: Sun Dec 01, 2013 10:00 pm 
Offline
User avatar

Joined: Sat Apr 21, 2007 11:21 pm
Location: Marin, CA
Great! I've been using that trick for the last 12 radiolarians, but that doesn't mean it won't cause a problem someday. I should have mentioned it before, since it snagged me for awhile.

Shapeways will give a "mixed normals" error if that problem ever happens though.

So far, SW seems to produce consistent normals, and QECD seems to maintain them. So far...

I say this because it still doesn't make sense to me that points would move to maintain normals, so I think it's a bug in the code that we simply avoid by bypassing the option.

Normals are usually defined by the face winding order (I think counterclockwise is "out").

Some formats like OBJ do let you save normals at each face or vertex, but those should be discarded by Shapeways I would think.

A lot of guessing going on here, I know. But also 2 years of decimation! :)

Meshlab does have a "recompute normals" function somewhere, but again I haven't needed it.

_________________
Jason Smith posted here as 'io' through 2012.
Visit Jason Smith's PuzzleForge on Shapeways!
Jason Smith's Puzzles - YouTube Channel.


Top
 Profile  
 
 Post subject: Re: Reducing STL triangles with Meshlab
PostPosted: Mon Dec 02, 2013 12:34 am 
Offline
User avatar

Joined: Thu Dec 21, 2006 5:32 pm
Location: Bay Area, CA
If you have perhaps smaller examples of these bugs you might try to see if the maintainers of Meshlab have interest. Geometry bugs like these are hard to find and having concise examples can really help find them.

Dave

P.S. My very first job as a programmer was writing a small font converter and I had loads of spike-producing bugs which made for very interesting output.

_________________
Image
LitwinPuzzles.com has info on my puzzles.


Top
 Profile  
 
 Post subject: Re: Reducing STL triangles with Meshlab
PostPosted: Mon Dec 02, 2013 12:53 am 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
First, THANKS SO MUCH for your help with this Brandon. Its really appreciated. Second, this is the kind of post I want to read a few times (same for that link to the Shapeways page) before I jump into the meat of the topic. Besides its too late to think too hard. :) So I won't go there just yet. However there are two things I wanted to ask about after just the first pass.
Brandon Enright wrote:
Now that Shapeways has eliminated their high polygon print option it's extra important for designers to get their model under 1 million triangles.
When was the back door option removed? Was there some announcement made? Because I think I missed it. Granted I rarely used it anyways as I didn't want to use it in any of my shop offerings. I didn't want to find out what happened if a customer ordered a big cube and I failed to notice or was away from email on vacation of something. I can just see Shapeways printing one solid cube and shipping it to the customer who was expecting a puzzle. With that mentality, even when I was printing puzzles for myself I was usually testing a model that I had hopes of being able to offer in my shop so I wanted to test the exact same STL files the future customers would be able to select. So I'm not too upset to see it go. Just surprised that I hadn't heard anything about it being gone before now. I know at one point in time Shapeways had talked about replacing the backdoor option with something more permanent but the last time I saw that discussed was over a year ago... maybe even 2 years ago now. Was there anything mentioned when they removed the backdoor option?
JasonSmith wrote:
EDIT -- By the way, it's very nice of you to spend the time putting this video together!
Video!? Did I miss something? If there is a video I'd love to see it but I didn't see mention of a video in the first post.

Carl

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: Reducing STL triangles with Meshlab
PostPosted: Mon Dec 02, 2013 1:31 am 
Offline
User avatar

Joined: Sat Apr 21, 2007 11:21 pm
Location: Marin, CA
wwwmwww wrote:
Video!? Did I miss something? If there is a video I'd love to see it but I didn't see mention of a video in the first post.


Oops! I had just been thinking a video of this could be nice, and putting the kids to bed at the same time. Neurons must have crossed. What I meant to say is that the act of compiling and posting this information was generous and appreciated.

_________________
Jason Smith posted here as 'io' through 2012.
Visit Jason Smith's PuzzleForge on Shapeways!
Jason Smith's Puzzles - YouTube Channel.


Top
 Profile  
 
 Post subject: Re: Reducing STL triangles with Meshlab
PostPosted: Mon Dec 02, 2013 6:30 am 
Offline
User avatar

Joined: Sun Mar 15, 2009 12:00 am
Location: Jarrow, England
Very useful post Brandon, whenever I have used Meshlab to reduce triangles, I have usually given up because I didn't understand what the hell it was doing.

When Meshlab introduces these errors, and you don't know how the fixes work (e.g. turning off preserve normals) then couldn't you just fix the stl manually using, for example, SketchUp? If you post an example of stl part with errors, I could see how easy it is to fix.

By the way, when I have designed stuff using Inventor, when I output the stl files there are options to change various parameters (select a mesh accuracy of Low, Medium, High and Custom) which has a drastic effect on the number of triangles produced. Does SolidWorks not have this option?

_________________
My Shapeways Shop: http://www.shapeways.com/shops/gus_shop

Image


Top
 Profile  
 
 Post subject: Re: Reducing STL triangles with Meshlab
PostPosted: Mon Dec 02, 2013 1:52 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
Gus wrote:
Very useful post Brandon, whenever I have used Meshlab to reduce triangles, I have usually given up because I didn't understand what the hell it was doing.
Agreed... very nice post. I haven't even tried this before. Looks like something I'll need to play with.
Gus wrote:
By the way, when I have designed stuff using Inventor, when I output the stl files there are options to change various parameters (select a mesh accuracy of Low, Medium, High and Custom) which has a drastic effect on the number of triangles produced. Does SolidWorks not have this option?
Yes, Solidworks has these options. Here is what their STL option screen looks like.
Attachment:
STLoptions.png
STLoptions.png [ 35.08 KiB | Viewed 1181 times ]
You can change deviation tolerance which I think controls how far the surface deviates from the ideal surface. I've personally never tried anything over 0.05mm for this parameter but Solidworks itself places limits on what this can be adjusted to. On all but 2 of my Real5x5x5 parts the imposed limit was less then 0.05mm. In the screen capture the maximum for a particular part is 0.0265184. I have no idea how Solidworks determines this limit. The reason why I go with 0.05 is my models have a minimum wall thickness of 0.75mm. Shapeways allows down to 0.7mm for SW&F. So if there is a point where the wall thickness drops below 0.7mm due to the deviation tolerance then Shapeways could reject the model. Granted the wall has two surfaces and I think deviation tolerance could add up and allow the wall to be only 0.65mm thick in certain location in a worst case situation but that hasn't happened to me yet. If it ever does I may step up to 0.8mm walls. The other parameter Solidworks lets one vary is the angle tolerance. I believe this is how much the normal angle can vary from the ideal normal at any given location. For all the parts of the Real5x5x5 I used 24 degrees. Still SolidWorks itself places limits on this parameter. For this particular part is was 30 degrees (actually 30.00000057 degrees, no idea why it isn't 30 exactly) and to be honest 24 degrees is larger then I've ever tried before. I'm not sure if this maximum is part dependent as the deviation tolerance is... I simply have never pushed it this far before. Still even if I had allowed the maximum for both parameters for all parts I'm pretty sure my total would have still been well over 1 million triangles.

Maybe there is a parameter somewhere that can be adjusted that would allow these maximums to be calculated differently. Hmmm... I think I do know a way to indirectly change these maximums. Let me test something and I'll post again.

Carl

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: Reducing STL triangles with Meshlab
PostPosted: Mon Dec 02, 2013 2:18 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
I should mention that I think gears are very sensitive to triangle counts. Involute curves need to be very precise or the gears can have lots of issues. Don't naively reduce gear parts. If you really need to get their triangle counts lower, reduce a pair of gears and print them to test.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Reducing STL triangles with Meshlab
PostPosted: Mon Dec 02, 2013 2:19 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
wwwmwww wrote:
Hmmm... I think I do know a way to indirectly change these maximums. Let me test something and I'll post again.
Ok... I placed 10 copies of the same part I used to make the above screeen capture into one file. Like this:
Attachment:
10copies.png
10copies.png [ 56.06 KiB | Viewed 1172 times ]
And here are the new maximum settings for both of these tolerances.
Attachment:
STLoptions2.PNG
STLoptions2.PNG [ 35.33 KiB | Viewed 1172 times ]
So yes, one could use this trick to make STL files that contain lower resolution parts and then pull out a single copy of the part wanted with Meshlab. The thing is that this method only works on the deviation tolerance and not the angle tolerance and as I said above I have concerns about going much above 0.05mm. Another reason why I've picked that number is that I've heard it stated (not sure if I can find it in writing at the moment) that the printing resolution of SW&F is 0.1mm and as a wall has 2 sides a deviation of less then 0.05mm in either side of that wall should be negligible on a printed part. I think one is much safer pushing angle tolerance. But that is just an educated guess.

If someone knows where the printer resolution of SW&F is stated would you mind post a link? The 0.1mm figure is just from memory and I may very well be wrong.

Carl

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: Reducing STL triangles with Meshlab
PostPosted: Mon Dec 02, 2013 2:59 pm 
Offline
User avatar

Joined: Sun Mar 15, 2009 12:00 am
Location: Jarrow, England
wwwmwww wrote:
If someone knows where the printer resolution of SW&F is stated would you mind post a link? The 0.1mm figure is just from memory and I may very well be wrong.
http://www.shapeways.com/materials/strong-flexible-design-guidelines and
http://www.shapeways.com/tutorials/design_rules_for_3d_printing

_________________
My Shapeways Shop: http://www.shapeways.com/shops/gus_shop

Image


Top
 Profile  
 
 Post subject: Re: Reducing STL triangles with Meshlab
PostPosted: Mon Dec 02, 2013 3:17 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
Gus wrote:
wwwmwww wrote:
If someone knows where the printer resolution of SW&F is stated would you mind post a link? The 0.1mm figure is just from memory and I may very well be wrong.
http://www.shapeways.com/materials/strong-flexible-design-guidelines and
http://www.shapeways.com/tutorials/design_rules_for_3d_printing
Thanks for the links. But I still don't see exactly what I'm after. Say I want to print a 1cm cube. How many layers need to be printed in Shapeways printers if they are using SW&F? I'm going to guess 100. If so then the print resolution in the vertical direction would be 0.1mm. In the horizontal direction it could be different. Anyways, I just remembered where I heard the 0.1mm figure. Its at the 2:38 mark in this video.
http://www.youtube.com/watch?v=hmxjLpu2BvY
This sounds exactly like the process for SW&F but I'm not sure if this is the same printer Shapeways uses or not.

Carl

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: Reducing STL triangles with Meshlab
PostPosted: Mon Dec 02, 2013 4:30 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
wwwmwww wrote:
Gus wrote:
wwwmwww wrote:
If someone knows where the printer resolution of SW&F is stated would you mind post a link? The 0.1mm figure is just from memory and I may very well be wrong.
http://www.shapeways.com/materials/strong-flexible-design-guidelines and
http://www.shapeways.com/tutorials/design_rules_for_3d_printing
Thanks for the links. But I still don't see exactly what I'm after. Say I want to print a 1cm cube. How many layers need to be printed in Shapeways printers if they are using SW&F? I'm going to guess 100. If so then the print resolution in the vertical direction would be 0.1mm. In the horizontal direction it could be different. Anyways, I just remembered where I heard the 0.1mm figure. Its at the 2:38 mark in this video.
http://www.youtube.com/watch?v=hmxjLpu2BvY
This sounds exactly like the process for SW&F but I'm not sure if this is the same printer Shapeways uses or not.

Carl

I'm pretty sure the voxels aren't uniform in shape or size over the whole printer volume. The center of the print close to the laser has a better resolution (or at least lower error) than the far away corners of the print. As with anything involving manufacturing or real world engineering, things aren't quite as exact as folks like us would like.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Reducing STL triangles with Meshlab
PostPosted: Mon Dec 16, 2013 2:39 am 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
I've been working with JasonSmith on a project and we ran into an interesting issue reducing the triangles of some parts. Jason exported (from Solidworks) a set of three parts at extremely high resolution -- 675246 triangles for only three parts! In order to pack the parts with some others, we needed to get the three parts down to 142k triangles. Unfortunately using the default reduction settings messes up the model. Fortunately we figured out that if you tweak the Boundary Preserving Weight value you can avoid the issues.

Here are the original parts:
Attachment:
triangles_tumbletest_orig.png
triangles_tumbletest_orig.png [ 222.51 KiB | Viewed 936 times ]

Here is some of the lettering up-close:
Attachment:
triangles_tumbletest_orig_close.png
triangles_tumbletest_orig_close.png [ 126.64 KiB | Viewed 936 times ]

If you choose the "default" reduction option like this:
Attachment:
triangles_tumbletest_qecd_default.png
triangles_tumbletest_qecd_default.png [ 20.34 KiB | Viewed 936 times ]

The model gets badly damaged. As you can see, a lot of the lettering is now messed up:
Attachment:
triangles_tumbletest_reduced_bad.png
triangles_tumbletest_reduced_bad.png [ 238.8 KiB | Viewed 936 times ]

And here is the reduction up close:
Attachment:
triangles_tumbletest_reduced_bad_close.png
triangles_tumbletest_reduced_bad_close.png [ 94.4 KiB | Viewed 936 times ]

Notice that a few gaps formed by the letters get closed? These issues violate the mesh boundary. If you increase the weight of the mesh boundary in the reduction to 10 like this:
Attachment:
triangles_tumbletest_qecd_fix.png
triangles_tumbletest_qecd_fix.png [ 20.52 KiB | Viewed 936 times ]

Then everything works out fine:
Attachment:
triangles_tumbletest_reduced_fix.png
triangles_tumbletest_reduced_fix.png [ 181.91 KiB | Viewed 936 times ]

And here is the fixed reduction up close:
Attachment:
triangles_tumbletest_reduced_fix_close.png
triangles_tumbletest_reduced_fix_close.png [ 92.3 KiB | Viewed 936 times ]

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Reducing STL triangles with Meshlab
PostPosted: Mon Dec 16, 2013 3:19 am 
Offline
User avatar

Joined: Sun Mar 15, 2009 12:00 am
Location: Jarrow, England
Have you been on the Meshlab forum or did you just tweak the values by trial and error until it did something useful?

_________________
My Shapeways Shop: http://www.shapeways.com/shops/gus_shop

Image


Top
 Profile  
 
 Post subject: Re: Reducing STL triangles with Meshlab
PostPosted: Mon Dec 16, 2013 3:26 am 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Gus wrote:
Have you been on the Meshlab forum or did you just tweak the values by trial and error until it did something useful?

I tried 2, 5, 10, and 100. 2 and 5 didn't work and I couldn't really tell the difference between 10 and 100 so I figured conservative is better.

I'm sure weights like this don't have an "optimal" value. My recommendation would be to start with 1 and if you have mesh boundary problems, explore the effect other values have. 10 worked great in this case.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Reducing STL triangles with Meshlab
PostPosted: Mon Dec 16, 2013 3:50 am 
Offline
User avatar

Joined: Sun Mar 15, 2009 12:00 am
Location: Jarrow, England
I wish we could get one of the Meshlab programmers to explain what the hell all of these different parameters are designed to do. But I suppose that we will never get a one size fits all set of numbers, they would depend on what "type" of model you had.

<edit>I had a look at the Meshlab forum and searched for "Quadric Edge Collapse Decimation" but the results were disappointing, mainly about the programming side of things. I also searched for this on the 'net, but again mainly the results are oriented towards code and the technicalities, not the practicalities (the Shapeways tutorial was 2nd in the list).</edit>

_________________
My Shapeways Shop: http://www.shapeways.com/shops/gus_shop

Image


Top
 Profile  
 
 Post subject: Re: Reducing STL triangles with Meshlab
PostPosted: Mon Dec 16, 2013 4:08 am 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Gus wrote:
I wish we could get one of the Meshlab programmers to explain what the hell all of these different parameters are designed to do. But I suppose that we will never get a one size fits all set of numbers, they would depend on what "type" of model you had.


The Quadric Edge Collapse Decimation algorithm plugin uses this code. Looks like it's a simple loop making use of the LocalOptimization class.
Code:
void QuadricSimplification(CMeshO &m,int  TargetFaceNum, bool Selected, tri::Tr\
iEdgeCollapseQuadricParameter &pp, CallBackPos *cb)
{
  math::Quadric<double> QZero;
  QZero.SetZero();
  tri::QuadricTemp TD(m.vert,QZero);
  tri::QHelper::TDp()=&TD;

  if(Selected) // simplify only inside selected faces                           
  {
    // select only the vertices having ALL incident faces selected             
    tri::UpdateSelection<CMeshO>::VertexFromFaceStrict(m);

    // Mark not writable un-selected vertices                                   
    CMeshO::VertexIterator  vi;
    for(vi=m.vert.begin();vi!=m.vert.end();++vi) if(!(*vi).IsD())
    {
          if(!(*vi).IsS()) (*vi).ClearW();
                      else (*vi).SetW();
    }
  }

  if(pp.PreserveBoundary && !Selected)
        {
    pp.FastPreserveBoundary=true;
                pp.PreserveBoundary = false;
        }

  if(pp.NormalCheck) pp.NormalThrRad = M_PI/4.0;


  vcg::LocalOptimization<CMeshO> DeciSession(m,&pp);
        cb(1,"Initializing simplification");
        DeciSession.Init<tri::MyTriEdgeCollapse >();

        if(Selected)
                TargetFaceNum= m.fn - (m.sfn-TargetFaceNum);
        DeciSession.SetTargetSimplices(TargetFaceNum);
        DeciSession.SetTimeBudget(0.1f); // this allow to update the progress b\
ar 10 time for sec...                                                           
//  if(TargetError< numeric_limits<double>::max() ) DeciSession.SetTargetMetric\
(TargetError);                                                                 
  //int startFn=m.fn;                                                           
  int faceToDel=m.fn-TargetFaceNum;
while( DeciSession.DoOptimization() && m.fn>TargetFaceNum )
{
   cb(100-100*(m.fn-TargetFaceNum)/(faceToDel), "Simplifying...");
};

        DeciSession.Finalize<tri::MyTriEdgeCollapse >();

  if(Selected) // Clear Writable flags                                         
  {
    CMeshO::VertexIterator  vi;
    for(vi=m.vert.begin();vi!=m.vert.end();++vi)
      if(!(*vi).IsD()) (*vi).SetW();
  }
}


The rest of it is in the vcg/complex/algorithms/ portion of the VCG library. Specifically vcg/complex/algorithms/local_optimization.h and vcg/complex/algorithms/local_optimization.h and vcg/complex/algorithms/local_optimization/tri_edge_collapse_quadric.h

Unfortunately the code to actually do the bulk of the algorithm is quite complex and the comments are in Italian with a bit of English here and there.

It seems like the algorithm works by finding edges (lines with a vertex on each end) that can be contracted to a point. There is an priority metric that gets computed for each edge and then the edges with the highest priority get removed. After each removal, the new and affected edges have their metric recomputed. The error heuristic looks pretty messy. I'll bet that educated guessing is the best way to figure out the right parameters for a model.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Reducing STL triangles with Meshlab
PostPosted: Mon Dec 16, 2013 7:34 am 
Offline
User avatar

Joined: Sun Mar 15, 2009 12:00 am
Location: Jarrow, England
So trial and error it is then!

_________________
My Shapeways Shop: http://www.shapeways.com/shops/gus_shop

Image


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 21 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group