search

slic3r / Slic3r

Open Source toolpath generator for 3D printers
https://slic3r.org/
GNU Affero General Public License v3.0
3.35k stars 1.29k forks source link

[GSoC] cvrieos / Wireframe printing #3933

Closed alranel closed 7 years ago

alranel commented 7 years ago

This issue is dedicated to the GSoC student @curieos who proposed to implement the wireframe printing technique in Slic3r: https://summerofcode.withgoogle.com/projects/#5662414690320384

This topic was discussed in this original issue: https://github.com/alexrj/Slic3r/issues/2274

@curieos has been working on another pull request (#3885) for adding a shell_thickness option, which is not finished yet. I recommend finishing it during the four-weeks community bonding period so that you'll be free for working on wireframe afterwards.

@curieos, welcome to Slic3r! Would you please introduce yourself to the Slic3r community? Please mention any experience with 3D printing or similar technologies, and include your time zone and operating system.

curieos commented 7 years ago

Howdy. I'm going to be working on the wireframe printing algorithm this summer. I've been into the reprap community since joining my local makerspace back in 2011. My first printer I built was a Rostock Mini, which I still have the parts for, and currently I have a TAZ 6, Rostock MAX, and most of the parts for an Ultimaker, all that I made. I will admit I dont often use Slic3r, but I'm definitely going to build some profiles for my printers now that I've seen how active this community is.

I typically prefer to develop on a UNIX based OS. I have computers running each major OS, and the one I will be using most often is running Ubuntu 16.04. I live in the US Central timezone (GMT-5/6)

alranel commented 7 years ago

Your project is conceptually simple but it has tricky details, so it requires good planning before starting writing code. In order to be able to start coding in June, this study should happen in May.

I suggest to think about wireframe printing as a distinct process than normal layer-based G-code generation. We don't need to merge the two things together, code-wise. Wireframe can be implemented like a black box which takes a model as input, a config, and generates an output. This approach allows you to put it into its own isolated class (I suggest the name WireframePrint as opposed to Print and SLAPrint which we already have). Of course, while writing this class you'll be able to reuse all the components provided by libslic3r, such as:

I suggest to start your preliminary study by focusing on some key points:

  1. What settings does wireframe need from user? Make a full list, including nozzle diameter, speed and everything you think might affect output.
  2. What mesh styles are you going to implement? There are multiple ways for joining the nodes.
  3. What cases do we need to handle? Make a comprehensive set of shapes which might create problems when generating nodes. A parallelepiped or a cylinder is easy, but what happens when the shape changes too quickly across Z? What happens with horizontal surfaces? What happens if we have a parallelepiped with a cylinder on top of it? What if we have two cylinders on top of it?
    • Check all the pictures available on the Internet for inspiration about weird test cases. Don't limit yourself to simple geometry.
    • Try to actually draw the resulting meshes, either by hand drawing or with your favorite CAD. You'll find problematic situations for which you'll need an algorithm.
    • It's legit to limit the domain of your implementation by excluding some shapes or circumstances which cannot be supported in a reasonable way. However, the domain should be defined explicitely and clearly.
  4. How did others implement this? AFAIK there are at least three open-sourced attempts to implement this. Two are mentioned in #2274 (one is by me, and it's very incomplete and potentially wrong, but still useful to study) and then there is Cura. Study them, find their limits and issues and think about how to improve them.
    • I suggest doing this step after the previous ones. I coded most of Slic3r without looking at the only software existing at the time (Skeinforge). This took more time, but I came up with original and creative ideas that worked better.

One more thing to say. I suggest to split the coding work in two subsequent goals:

  1. Create a command line utility that reads input file and options as arguments and passes them to your WireframePrint which will write a G-code file.
    • This will make testing faster, and you will be able to compile using CMake without using the Perl toolchain.
  2. Integrate your WireframePrint class into the GUI, which means: graphical config options and 3D preview.
    • These things are not the core part of your project, so I would leave them as a secondary goal in case you have time for them. So, no need to focus on studying those parts of the codebase.

Make sure you can compile the pure-C++ part of Slic3r with CMake by executing the following commands:

cd build
cmake ../src
make

And study how src/slic3r.cpp and src/utils/extrude-tin.cpp are written. In case you have any questions, please do not really hesitate to ask them!

Of course, all of this is a proposal and I'm open to hearing your thoughts. :)

curieos commented 7 years ago

I'm settling into my current living arrangement after moving. My friend is graduating tomorrow so it will be a busy day but I will try to the requirements checklist soon.

curieos commented 7 years ago

I'm most of the way through writing a post generator for my blog (www.clongnecker.com/blog). I'll try to get some project details on my site too (www.clongnecker.com/projects/wireframe). When I finish the post generator I will be posting more updates there.

curieos commented 7 years ago

I have the post generator working now. I have the first post uploaded and I will be working to update the project page and researching. I will post more often on my blog and reserve big stuff for here.

curieos commented 7 years ago

I will be adding to this yet, just posting to save

What settings does wireframe need from the user? (New settings first) Printer Geometry

Material Settings?

Print Settings

What mesh styles are you going to implement? There are a few styles I can think of. It could generate triangles varying between between right and equilateral, or it could do some sort of sine wave type pattern. I think typically the triangles will be more feasible to print, but more than 1 style would definitely be pretty cool. Something that goes along with this thought how to align the vertical towers. The one created in the paper attempts to align them between layers in hopes to increase strength. This might be useful as a setting?

What cases do we need to handle?

alranel commented 7 years ago

Any updates @curieos? The community bonding period has ended and you are supposed to be coding full time by now, updating your log on a daily basis. We're a bit beyond the schedule. I recommend to focus on the project otherwise it will be difficult to get to a usable result.

curieos commented 7 years ago

@alexrj Yeah, I have my branch set up.

I signed a lease for my new apartment Tuesday and I'm moving in starting Friday, so these next couple days might be a bit slow on progress as I move.

My goal for this week is to add options for Wireframe and to get some dummy methods setup to run for wireframe when it is enabled. In order to accomplish this I need to find where the Print object is created in the CLI tool. I was looking in slic3r.cpp and I found where the SLAPrint object is created, but I cant find where the regular Print object is created. Also I was talking to @lordofhyphens on IRC and he said I could inherit Print in WireframePrint and just override the methods I need to change. Does this seem like a good idea? Looking at SLAPrint it does not inherit Print, though it's quite a bit different from the FFF process.

curieos commented 7 years ago

Looking around, it seems PrintObject holds the Print class. I'm thinking I can extend PrintObject to switch between using a WireframePrint object vs a Print object based on config settings. Does this seem like a good idea? I was trying to use SLAPrint as an example, but it is not implemented like I expected so its not quite as useful as I thought it would be.

Also, looking around at the CLI tool, I am unable to determine how it does all the slicing functions. I looked in slic3r.cpp, extrude-tin.cpp, and libslic3r.h, and I also searched all the .cpp, .hpp, .c, and .h files for references to PrintObject and I was unable to find what I was expecting.

curieos commented 7 years ago

I got my keys for my new apartment today and I'm going to be moving over the next couple days. To make matters worse, my internet wont be activated until mid-next week. I have a few ways around this so I will still be able to work but my availability will be spotty until our service is activated.

curieos commented 7 years ago

My internet gets connected Thursday. I'm trying to get my place ready so I can start working immediately when I get it setup. Sorry for the delay and thank you for the patience

curieos commented 7 years ago

Something is wrong with my internet. Ive been on the phone/chatting with someone like 10 times these past two days to figure it out. Someone is coming monday to service. Ill go to my local library and utilize their network there this weekend. Im so sorry this is all happening, CenturyLink has been a huge PITA so far

curieos commented 7 years ago

I think I have been searching for something that is not there. I thought the C++ compiled slic3r binary would slice things, but it seems I was incorrect, only the perl portion does that.

@alexrj, you mentioned creating a command-line utility. I thought I was supposed to extend the slic3r c++ utility, but now I think you actually meant creating a C++ utility like extrude-tin or slic3r. I'll get to work creating this instead.

lordofhyphens commented 7 years ago

@curieos it does slice things, but it doesn't generate toolpaths useful for a FDM printer (see: SLAPrint::slice()). The first step though is that SLAPrint::slice() calls through to TriangleMesh which has a method in it to cut the model into Z wafers. I don't know if this will be useful to you though.

@alexrj didn't extend an existing class when he wrote SLAPrint.

curieos commented 7 years ago

That makes sense since there wasn't much in common between SLA and FFF printing, but wireframe is still FFF. I think it might work out pretty well if I do it with inheritance, but if you guys don't like it it wont be to difficult to change.

alranel commented 7 years ago

Print is a class for filament prints (FFF/FDM). It's called Print instead of FFFPrint just for historical reasons.

SLAPrint is a class for SLA prints. It doesn't inherit from Print, as it has its own logic. Your WireframePrint class will need to be a third type of print, so you need to create a new class from scratch, and not use Print, PrintObject, PrintRegion.

Inheriting from PrintObject and other Print classes will be problematic, as you'll need to make most of those methods virtual (which adds a little overhead) and you'll be using structures that are much bigger than needed. I suggest you write a WireframePrint family of classes from scratch. This will make your work cleaner.

curieos commented 7 years ago

Okay, thank you for the input, that makes a lot of sense.

alranel commented 7 years ago

TriangleMeshSlicer will slice the mesh and then you can do whatever you want with the resulting slices.

However @curieos, you didn't finish the first assignments I wrote on May 5th.

curieos commented 7 years ago

I've been generating some test models for wireframe and I'm going to work on creating depictions of what I think the frame should look like so I can reverse engineer what wireframe should be doing. I'll get more tests made and I'll put a real effort into getting caught up as best I can.

Meanwhile, heres a little taste:

boxholehoriz overhang slottedbox tube
lordofhyphens commented 7 years ago

IRC conversation from Thursday June 15:

[22:24] <LoH|Lenneth> How are your studies into wireframe going?
[22:28] <LoH|Lenneth> What have you considered for test cases that need to be handled?
[22:28] <cvrieous> I've got some of the file structure setup and I feel like I've got a decent idea of what I have to program for now. I still need to figure out some test cases. It might be a good idea to create some test models?
[22:29] <LoH|Lenneth> Yes, it would be a good idea.
[22:30] <LoH|Lenneth> Sound had some good suggestions; the idea here is to think of some problems that make your initial approaches sweat 
[22:30] <cvrieous> I had a few ideas a while ago but I foolishly neglected to write them down
[22:30] <LoH|Lenneth> Trolling through the open/closed issues for Slic3r might give you some ideas too
[22:31] <cvrieous> related to this or just general issues
[22:31] <LoH|Lenneth> related to this; people tend to find the weirdest models
[22:31] <cvrieous> okay
[22:31] <LoH|Lenneth> sculptures, etc on thingiverse would work too
[22:32] <LoH|Lenneth> scale up that 5mm step cube ;)
[22:32] <LoH|Lenneth> Obviously some geometries aren't going to work at all. 
[22:33] <cvrieous> tbh the benchy provides a whole lot of weird geometry cases to worry about
[22:33] <LoH|Lenneth> Yes, that's probably a good place to start once you move past simple shapes; although you should probably start with ones that you can render by hand
[22:34] <LoH|Lenneth> They'd make decent regression tests too
[22:34] <cvrieous> yeah
[22:34] <cvrieous> control your variables
[22:34] <cvrieous> I just just thinking about typical benchmark prints
[22:34] <LoH|Lenneth> as well as feature tests
[22:35] <LoH|Lenneth> Something that may be helpful in testing is to have a printout of the "draw order" and the sticks generated
[22:36] <cvrieous> like formatted text output?
[22:36] <LoH|Lenneth> yeah, doesn't have to be too fancy though
[22:38] <LoH|Lenneth> I would like you to add some of those test meshes (either a scanned-in hand drawing or out of a cad program) to the issue/devlog
[22:38] <cvrieous> yeah that was the plan for tomorrow
[22:38] <LoH|Lenneth> Alright. 
[22:38] <cvrieous> *is
[22:41] <LoH|Lenneth> I think the process of sketching out how the nodes would have to be placed with different shapes (think of some vases that slope in and out) will be instructive
[22:42] <cvrieous> yeah that seems like a good idea
[22:42] <cvrieous> thank you for the advice/input
[22:42] <LoH|Lenneth> When you start wanting to generate vertices, look at trianglemesh's Z slice
[22:42] <cvrieous> okay
[22:43] <LoH|Lenneth> The logic to figure out how dense they need to be is related to adaptive slicing
[22:43] <LoH|Lenneth> The algorithm used is probably overkill, but it exists in platsch's adaptive-slicing branch
[22:44] <cvrieous> okay, so look there for some ideas?
[22:44] <LoH|Lenneth> If you find yourself stuck on how to set things up in Z
[22:44] <cvrieous> okay
[22:45] <LoH|Lenneth> the next "trick" will be aligning the nodes on successive layers so that it is printable, then the draw order
curieos commented 7 years ago

June 22

What did I accomplish

I generated wireframe drawings of several of the test meshes I created and started to get a feel for what the code will need to do and how I can break functionality down.

What do I need to work on

Tomorrow I plan to create blog posts with screenshots of the wireframes I generated, an explanation of what I learned creating it, and links to download the files I created.

curieos commented 7 years ago

June 23

I'm working on putting what I've done in writing. Its a lot of content so I'm putting it on my blog but I am going to update this post with direct links as I go.

The box test The slotted box test The y block test

lordofhyphens commented 7 years ago

Reminder: An optimal solution for the path for the draw order resembles the Hamiltonian path problem.

curieos commented 7 years ago

June 24

I don't have wireframes generated for all of these but I can still talk about the rationale for creating the tests

The horizontal bore box test The tube test The cylinder test The prisms test The overhang test The rounded cube test

curieos commented 7 years ago

June 25

What did I accomplish

I finished generating tests/documentation and discussed my plans with LoH

What do I plan to work on

curieos commented 7 years ago

June 27

What did I accomplish

I created a thought dump on google docs to help sort through my thoughts since I was starting to forget my train of thought from before

What do I plan to work on

Flush out the ideas from the thought dump into a more formal writeup and start work on the CL utility. I should be able to split things up into small-ish tasks so I can do a checklist style thing to mark them as complete.

curieos commented 7 years ago

June 28

Commits

https://github.com/curieos/Slic3r/commit/86a5a319ace778da5d9142dbe28c93bec3536fc9 https://github.com/curieos/Slic3r/commit/08eec723031970e152fb0c99e2191591b0fe627f

Todo

curieos commented 7 years ago

June 29

Commits

https://github.com/curieos/Slic3r/commit/01a94d889f77073cc759617d4b51933c41793da4 https://github.com/curieos/Slic3r/commit/e6a2e94857c1867d263ee2a7b51c4a2bb927f0ae

alranel commented 7 years ago

Conversation from today over IRC:

[23:07:51] <LoH>    curieos_: so where are you on algorithms for wireframe?
[23:09:30] <curieos_>   I have that checklist on my post from yesterday on the issue, I'm running through that right now
[23:10:14]  Jokeri (~Jokeri@176-93-4-141.bb.dnainternet.fi) left IRC.
[23:18:40] <LoH>    curieos_: so how is your schedule going to change to be able to complete on time?
[23:19:12] <curieos_>   like my development schedule?
[23:19:17] <curieos_>   based on my proposal?
[23:20:42] <LoH>    curieos_: Yes. You were not, at least to anyone observing, working on the problem for most of June. Your proposal indicated that you'd have some basic algorithms down and testable by the first week of July (the end of the first evaluation).
[23:21:34] <LoH>    So how much do you think your schedule will slip w/r/t the proposal?
[23:28:45] <curieos_>   I'm thinking through this so my answer is going to be in chunks
[23:28:47] <curieos_>   Doing my manual tests, I think I learned that node placement and step placement should be done around the same time because optimal step placement is based on the geometry of the triangles that are to be formed.
[23:30:20] <curieos_>   Stretch goals have also changed. I'm thinking more support/infill. Just throwing this out there bc my brain wont shut up about it
[23:31:30] <curieos_>   I think the Gcode generation step is going to be the easiest (simplest)
[23:35:29] <LoH>    Between now and Sunday, what could you have done?
[23:35:59] <curieos_>   tbh I'm still thinking through how to determine the best spot for steps. The manual tests weren't quite like what I'm dealing with here, I can visually see the model as a whole which makes it easy to analyze the geometry. I still haven't figured out a way to work through the problem other than creating a slice at the max height, analyzing it, and then working down if its not ideal, which is kinda slow
[23:36:53] <curieos_>   I can have steps 1-5 done by tomorrow on that checklist
[23:42:16] <Sound>  curieos_: you should put the highest priority on figuring out the algorithm itself, in terms of pseudocode or block diagram or plain English - whatever - but that comes before implementation details
[23:43:56] <Sound>  curieos_: i.e. what are the lessons learned from your investigation about shapes? what are the shapes we can't handle? are you sure you investigated all possible shapes?
[23:44:06] <curieos_>   LoH said I should be pushing more so I was trying to do that
[23:46:35] <Sound>  curieos_: that includes any kind of observable activity, including design work.  When he told you to do so, there was almost nothing out there showing your work, not even thoughts or questions, so he recommended to show your activity on a daily basis
[23:52:03] <curieos_>   I was talking about the more recent time I talked to him. He was talking about TriangleMesh, TriangleMeshSlicer, and other programming details
[23:52:41] <Sound>  curieos_: you drafted a cylinder test case but you didn't actually analyze it saying "I don't think much explanation is required for this one." However, are you entirely sure you don't need to analyze it? What will happen if I give you a low-resolution cylinder and a very high-resolution one, with hundreds of tiny segments? Are you sure you know it? Don't underestimate the importance of studying test cases
[23:54:11] <curieous>   <LoH|Work> curieous: what are you working on?
[23:54:11] <curieous>   [14:31]  <curieous> LoH|Work gonna start working on piecing what I need to code together in writing and then I'm gonna work on doing it
[23:54:11] <curieous>   [14:46]  <LoH|Work> Best push more commits; because I'll be using the state of the thread and your repository commits in my evaluation.
[23:54:18] <curieous>   that was from yesterday
[23:54:40] <curieos_>   or maybe tuesday
[23:54:51] <LoH>    I was trying to get you to produce something simple to hack around on, as you seemed to be in analysis paralysis.
[23:54:58] <curieos_>   okay
[23:56:07] <curieos_>   thats fair but I feel like I'm being told two different things
[23:57:22] <curieos_>   and I dont have an application to draw around circles. My prisms test was meant to isolate the problem you mentioned btw, at what point does a many-sided prism become a cylinder
[23:58:36] <curieos_>   So the cylinder test was supposed to be a standard high-resolution cylinder
[23:59:49]  emaker (~Thunderbi@cpc87211-aztw31-2-0-cust64.18-1.cable.virginm.net) left IRC. (Quit: emaker)
[00:00:05] <Sound>  curieos_: there's no true cylinder in STL :-)
[00:00:30] <LoH>    Sound and I have different problem-solving approaches, which accounts for some of that.
[00:00:39] <curieos_>   My plan was to pseudocode what I need to write (see June 25) but my focus shifted to putting out commits
[00:01:22] <curieos_>   I know but if you export a cylinder in a solid modeler it outputs a high resolution approximation
[00:02:01] <Sound>  you define the resolution
[00:02:35] <curieos_>   I know but typically its pretty high-res
[00:03:43] <Sound>  curieos_: I'm telling you there's no concept of "high-res", it's wrong :-)
[00:04:25] <LoH>    Sound: may be beside the point here though; wireframe is more of a low-res application
[00:05:15] <LoH>    Is STL an appropriate format for visualizing the node placement? There's vertices all over the place to define the mesh and you'd just need to define the triangles accordingly
[00:06:37] <Sound>  LoH: heh, of course it's a low-res application.  But if curieos_ completed her investigation, she would have noticed that low-res result does not always coincide with a low-res input mesh, which you cannot trust
[00:07:02] <curieos_>   I'm not sure, I've seen some pretty messy meshes with a lot of extra triangles.
[00:07:42] <LoH>    I meant in terms of generating a mesh (as this application would certainly have to do)
[00:07:44] <Sound>  Think about a cube.  Its faces are made by two triangles with a diagonal edge between them. That diagonal edge has no meaning for wireframe, and must be ignored
[00:08:27] <curieos_>   okay
[00:08:29] <curious>    'optimised out'
[00:08:59] <LoH>    That diagonal edge is likely important for structure IMHO, but that can be figured out with print tests. :-p
[00:09:44] <Sound>  LoH: think about a *large* cube, which will be printed in terms of several layers/nodes
[00:10:21] <Sound>  like in this example by curieos_: http://clongnecker.com/blog/2017/06/22/box_test/BoxSlice3.png
[00:11:19] <Sound>  any large diagonal edge between the mesh facets was implicitely ignored by curieos_ (correctly), and then she generated a node structure on the full flat face, totally ignoring how that face was represented in the input mesh
[00:12:30] <Sound>  that cube side might have been represented in the original STL face in infinite ways, not just by two triangles
[00:16:12] <Sound>  So it's not just a matter of optimization. It's a deeper design choice: what are the semantics of the input mesh? Do we trust it as a pre-made wireframe structure, which we just need to convert into G-code?  Or are we taking *general* input and we're studying a way to generate the wireframe on it without trusting the input tesselation?
[00:17:13] <curieos_>   A simple mesh that gets messy is the box with a hole in it
[00:18:37] <Sound>  so curieos_, I want to stress out that you will *never* get any input looking like the perfect cylinder you displayed.  You will get polygon meshes which approximate a cylinder, but they might have 5, 10, 100, 1000, 10000 segments
[00:18:58] <curieos_>   I'm aware
[00:19:45] <Sound>  you need to analyze those cases, and *define* (you're the architect!) how you want to handle them
[00:20:27] <Sound>  suppose you have a cylinder with 1000 segments around each slice, are you actually building 1000 nodes? those diagonals would be too close to each other, you can't do it physically. So what are you going to do?
[00:21:08] <Sound>  (I don't know the answer - but this is the question I would need to answer myself if I were going to code something for it)
[00:25:19] <curieos_>   I was thinking that I should handle anything that has greater than 140(?) degree internal angles as a circle. I didn't generate the mesh for a cylinder because inventor isn't capable of wrapping a sketch afaik, but I was thinking since there isn't anything that would cause a need for a lower step height it would just go at the full 5mm up to the top and I would add the maximum nodes I could equally spaced apart
[00:26:01] <curieos_>   of course, analyzing things like this is expensive, especially with high segment models
[00:27:39] <Sound>  first note about your answer - if the tool you're using for drawing your test cases isn't good, use another tool.  Paper and pencil are the most powerful ones, since you just need to sketch nodes and segments.
[00:27:39] <curieos_>   but it would be a start
[00:28:43] <curieos_>   yeah, I'm thinking I should go and do some paper tests and do my best to only give myself access to the information I will have in the code
[00:29:01] <curieos_>   read as I'm going to do that
[00:29:23] <Sound>  only give yourself access to the information? I don't get it, what do you mean?
[00:30:23] <curieos_>   well so with the stuff I was doing in inventor I could visually see everything and the shape it forms as a whole, so I can make assumptions about it that I may not be able to while coding
[00:30:47] <Sound>  okay
[00:30:56] <curieos_>   so I would try to think through it as a triangular mesh instead of a solid object
[00:31:14]  teepee_ (~teepee@unaffiliated/teepee) joined the channel.
[00:31:39] <curieos_>   and I can get slices of the object as specific Z coords
[00:32:21] <Sound>  based on my experience, I can tell you that any approach which is based on hard-coded thresholds (like your 140°) does not work.   But I don't want you to just trust me - I want you to discover that yourself by thinking hard about how to handle those cylinder cases
[00:32:38] <curieos_>   okay
[00:33:22] <Sound>  Take paper and pencil, and draw a low-res cylinder and a high-res one (or multiple intermediate cases), and try to draw the resulting nodes
[00:33:56]  teepee (~teepee@unaffiliated/teepee) left IRC. (Ping timeout: 245 seconds)
[00:33:56]  teepee_ is now known as teepee
[00:34:40] <Sound>  Also, when you said you want to handle stuff with more than 140° as a circle, you were clearly not thinking about curved shapes which are not circles. That approach doesn't work.  Your test case suite lacks curved non-cylindric objects
[00:35:24]  M0wLaue (~M0wLaue@95.90.217.22) left IRC. (Ping timeout: 260 seconds)
[00:37:16] <curieos_>   Actually I was thinking about that, which is why I referred to it that way instead of number of sides. I was thinking about it in terms of how to identify how many sides an equilateral polygon should have based on the interior angle of each side
[00:37:53] <curieos_> http://image.tutorvista.com/content/feed/tvcs/octagon_measure20of20interior20angle_16.PNG
[00:37:55] <curieos_>   like this image
[00:39:05] <curieos_>   also 140 degrees was a spitball number that I was thinking of making configurable/variable.
[00:39:10] <Sound>  But what about non-equilateral polygons?
[00:40:23] <Sound>  i.e. this https://thingiverse-production-new.s3.amazonaws.com/renders/69/8f/63/ca/13/74643e87a65696cfbd4287af8555a176_preview_featured.jpg
[00:41:23] <curieos_>   the edges that are greater than X degrees would be treated like a circle, and the edges less than X degrees would be treated as a "hard edge", so a node would be placed there, like I was thinking for this test http://clongnecker.com/blog/2017/06/25/multiroundedcube_test/
[00:41:50] <Sound>  1. What does "treated like a circle" mean?
[00:42:56] <Sound>  2. In my example, no part of that curved contour is a part of a circle.  Not all curves are arcs of circles.
[00:43:19]  Sappy (~Sappy@92.49.28.13) left IRC. (Quit: Going offline, see ya! (www.adiirc.com))
[00:46:44] <curieos_>   It just means that any nodes in the slice are ignored if the interior angle is greater than that threshold. Like with the box, the points on the slices (polygons) should end up in the corners which are 90 degrees. If there are any extra points they will be ignored since the interior angle is 180 degrees, greater than the threshold
[00:47:50] <Sound>  So according to what you just said, if you have a high-resolution cylinder, where all segments have a relative angle > 140°C you'll be ignoring *all* vertices.
[00:48:04] <Sound>  140°, of course, no "C"
[00:48:22] <LoH>    I prefer to think of angles as boiling ;)
[00:49:34] <curieos_>   yeah, all the vertices of the mesh shall be ignored and wireframe shall place its own nodes where it thinks they best go
[00:51:01] <curieos_>   which should be the maximum that fit along the the perimeter (obeying the printer geometry), equally spaced apart
[00:52:19] <Sound>  This is a good answer, okay
[00:53:02]  rjsnyder (~rjsnyder@p20030080AD1E19005CC8372BB7BF0B0E.dip0.t-ipconnect.de) joined the channel.
[00:53:16] <curieos_>   my biggest concern is this is potentially expensive on higher-res meshes
[00:53:35] <LoH>    Optimally? Probably
[00:54:14] <Sound>  May I help you reframe the problem you're dealing with?  The core of your task will be an algorithm that transforms a generic mesh into a low-poly mesh which honors a defined set of requirements (for example: edges can be only horizontal, vertical, or diagonal; distance between vertical edges is >= x, etc.) When you get such a low-poly mesh, you just generate G-code for its edges, and that's the easy part
[00:56:37] <Sound>  First, I'd recommend to define this set of requirements explicitely (they could even be turned into unit tests), and then you can think about your algorithm as a black box which does this low-poly conversion
[00:57:14] <Sound>  i.e. given a cylinder, how to generate a reasonable low-poly version of it?
[00:57:46]  rjsnyder (~rjsnyder@p20030080AD1E19005CC8372BB7BF0B0E.dip0.t-ipconnect.de) left IRC. (Ping timeout: 276 seconds)
[00:58:17] <curieos_>   so you think I should manipulate the TriangleMesh and then use the vertices to generate the gcode?
[01:00:40] <LoH>    I'd start with generating simpler models with your algorithm and work on generating gcode separately
[01:01:31] <Sound>  curieos_: that could be a way, but I think it's not worth to keep using the TriangleMesh structure also after you apply your algorithm.  Since one of the requirements of your low-poly mesh is about having horizontal edges, you can take advantage of it and use your own internal data structure, based on layers, or anything else
[01:02:14] <Sound>  curieos_: what I just said is really not a change in what you are doing.  It's just a hint about how to see the same problem from a more clear perspective
[01:03:00] <Sound>  in terms of computational geometry, you are writing an algorithm for turning a generic mesh into a low-poly mesh honoring a set of defined requirements
[01:04:09] <Sound>  such requirements are given by: wireframe process and chosen mesh style (i.e. horizontal/vertical/diagonal edges), and printer geometry
[01:10:12] <curieos_>   okay
[01:10:35] <Sound>  Does this approach make sense for you?
[01:10:50] <curieos_>   yeah
curieos commented 7 years ago

June 30

What I plan to do

LoH was saying I should simplify the mesh upon import. I want to investigate how consistent the simplification is to see if I can rely on it to make some of my ideas more viable. I'm going to download Blender and recreate some of the meshes I made for my tests, but I will create extra unneeded polygons and see how consistently the simplification algorithm behaves. I plan to test this on flat-faced objects and curves of varying resolution.

After I do this I'm going to do some more thinking by hand drawing some of the tests I wasn't able to do in inventor and taking a slightly different approach to solving them. Before I was looking at each face of the object and trying to fit wireframe into that geometry. I think this is really difficult to translate to wireframe, and if I spend some more time I think I can come up with some better ideas.

curieos commented 7 years ago

July 2

What I did

I created some meshes in blender to test a few cases. I may make some more depending on the results of my testing

What I plan to do tomorrow

Tomorrow I will get my C++ wireframe utility to import an STL file, run the simplification algorithm, and then export it as filename_simple.stl so I can then view what changes it made to the mesh. If there is some kind of consistency then my work will be made a bit easier.

curieos commented 7 years ago

July 3

I forgot that simplify is a method of Polygon, not of Model or TriangleMesh. My plan to simplify the STL files fell through, but even still I gained some potentially valuable test meshes. I will post the new ones on my blog soon.

curieos commented 7 years ago

July 7

What I did

While I was thinking through my hand-drawn test I came up with an idea to simplify the analysis of the mesh. I think I can use the split method to cut the model into chunks to analyze on their own. Then, I can run through all the points that don't lie on the top/bottom of the slice and analyze how the geometry changes. If there are no points then the maximum step height can be used, otherwise the geometry would need to be analyzed to determine if a step should be added at the same level.

More to come with links to details on my blog.

curieos commented 7 years ago

July 11

What I've been doing

I've been thinking through the problems that are left with my idea and one has me particularity stuck. The points are easy to identify, but figuring out if that point is significant is more complicated. I was thinking I could analyze the angle between two mostly vertical edges coming from the point, but this only works if the model has polygons that are aligned vertically I think. I need to investigate this with blender.

Additionally, determining the correct edges to analyze might be difficult since a properly triangulated mesh should have at least 6 connecting verts (or "edges") under typical circumstances.

curieos commented 7 years ago

July 12

I can use the cross product to check the edges for parallelism. Now I need to figure out how to select the correct edges

lordofhyphens commented 7 years ago

What about comparisons of the candidate edge with the surface normal of the "bed" the object is placed on? You'd have to generate this plane (and by generate, I mean determine where it is in relation to the orientation of the object). I would imagine that you are looking for specific orientations of the candidate edges relative to the object's spatial placement.

curieos commented 7 years ago

July 15

I've been pondering this over the past few days and I think I found a solution that should work. I want to check out some messier meshes to see if my ideas hold up, but I think if I look through all the tris that the point in question is tied to and find the two (above and below) that are closest in X and Y those will be the best to analyze with. This implies that I'm starting with the lowest points first and moving up until I find a point that is "important" or until I reach the end, which means the max step height can be used.

curieos commented 7 years ago

July 17

While investigating I managed to break my idea very quickly. I was thinking the closer the connected vertex is to the one being analyzed the more ideal it would be to use, but even with a simple sloping box this idea fails.

screen shot 2017-07-17 at 4 11 45 pm
bubnikv commented 7 years ago

By the way, did you study the implementation in Cura?

On Mon, Jul 17, 2017 at 11:21 PM, Caroline notifications@github.com wrote:

July 17

While investigating I managed to break my idea very quickly. I was thinking the closer the connected vertex is to the one being analyzed the more ideal it would be to use, but even with a simple sloping box this idea fails.

[image: screen shot 2017-07-17 at 4 11 45 pm] https://user-images.githubusercontent.com/21280590/28290297-8c0c7042-6b0b-11e7-906b-f9835af5bea1.png

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/alexrj/Slic3r/issues/3933#issuecomment-315888419, or mute the thread https://github.com/notifications/unsubscribe-auth/AFj5I0k83kge1J1lmGQ2gROAKZI4wn9aks5sO9BHgaJpZM4NRMzR .

curieos commented 7 years ago

I'm trying to find Cura's implementation, but a quick search of the GitHub doesn't show what I'm expecting to see. I thought someone had posted a link to the issue discussing it in Cura but I couldn't find that either.

edit: I was looking in the wrong repo, forgot Cura has a frontend separate from the back

alranel commented 7 years ago

The problem there is that you're assuming your input mesh has horizontal segments forming closed loops, coinciding with the output wireframe. The purpose of studying potential geometries was to show that you have to deal with generic shapes, whose meshes may be composed by random triangles. The job of a slicer is to approximate those geometries and generate the desired output. You're not writing a simple converter, you're coding a strategy for building an approximation of a given generic shape. The step height of a wireframe (i.e. vertical distance between horizontal extrusions) is a constant parameter. So the first step of your workflow will be to slice the mesh with multiple planes located at those heights. Those slices might not coincide with horizontal edges of mesh triangles. Slices will be generic closed loops. Such loops might be equal (i.e. same shape, same vertices) or similar (i.e. same shape, different vertices because triangles were sliced in their sloping edges) or different. If you don't get the "similar" case, think about a triangle mesh representing a cube. Try to slice it at z = total_height * 0.2 and z = total_height * 0.8: you'll get two closed loops having 8 vertices each. They will have the same shape (a square) but 4 out of those 8 vertices will be positioned in a different place. So you can't assume there's any correspondence between two subsequent layers in terms of vertices count and/or position.

Summarizing:

So, you sliced your solid and you have multiple closed loops at multiple heights. Now you have to define a logic for building a sensible mesh between those loops. Since you can't rely on vertices, you can only rely on the shape. In other words you have a lot of freedom about where to place your nodes.

  1. Start thinking in a plane. Suppose you have a closed loop with random vertices (please, draw a few examples). Which existing vertices would you pick as nodes? Your configuration parameters provide you with constraints for solving this problem (i.e. minimum/maximum distance between nodes). You might have to skip some existing vertices. Which ones would you skip? I'd probably keep the ones with the most acute angles and discard the others. Do you need to add more vertices for breaking this distance?
    • Write this algorithm. This is your first goal. You can test this code against several shapes, with few or many vertices. Make sure for any shape you get a meaningful output (= nodes).
  2. Afterwards, when that algorithm works, you'll need to expand it by taking one more variable into account: the previous layer (pick the lower one for simplicity). When looking for potential nodes on a layer you'll need to give priority to those nodes that form vertical extrusions with nodes you selected on the lower layer and/or generate valid wireframe connections between layers, according to the geometric constraints of the wireframe.
  3. While doing that, you'll find sudden changes in shapes which you'll need to handle somehow. But that's too far to discuss for now.
curieos commented 7 years ago

I think you misunderstand, I'm not worrying about the slices, I'm worrying about finding the ideal places for the slices. I'm thinking if I cut out a section of the mesh and only analyze that I can better determine the ideal placement. If the section I am analyzing doesn't have any points outside of the top/bottom xy planes, then the maximum step height can be used. If there are points inside there, then I think they should be analyzed to see if they are extra points that are unnecessary (like the example I showed a bit earlier) or if they are significant (as in the geometry doesn't have a straight side, for if it curves. If it is straight the cross product will be 0)

edit: Also, using the cross product I believe I can simplify determining the angle between two edges, potentially for use with the node placement algorithm.

curieos commented 7 years ago

July 23

I had a busy weekend because my birthday was Saturday. Ideas are taking a while so I'm thinking @alexrj is right, I'm just going to make a simple spec that I can expand later when I find ways to do what I'm wanting.

curieos commented 7 years ago

July 24

What I need to do

I want to make a simplified version of wireframe that I can expand on. The step height will not change to adapt to the geometry, it will be locked at Max Step Height. Nodes will be generated at all verts and then removed to respect printer geometry. Additional points may be generated if there is sufficient distance from one node to another.

curieos commented 7 years ago

July 25

I forgot to post updates/push changes

What I did

I've been filling in some of the WP objects to help learn how they interact in regular printing. I need to fill in the rest so I can use them soon.

Commits:

https://github.com/curieos/Slic3r/commit/41f1e05c94f50bedccb51f4730c92df825170d60

curieos commented 7 years ago

July 26

todo

curieos commented 7 years ago

July 27

lordofhyphens commented 7 years ago

@curieos Any updates?

curieos commented 7 years ago

Sorry for the lack of communication. I've been really busy cleaning my apartment and getting ready to buy a new car. Tomorrow I am getting my new car, but I have to drive to Illinois so its going to take most of the day. @lordofhyphens I've been seeing your messages on IRC but every time I get to them you're offline. I'll start the pull request this Friday after I register my vehicle.

lordofhyphens commented 7 years ago

@curieos You will have 3 weeks to finish by then, and don't classes start a week before that? What else is going to compete for your time and attention? Best work that out now. 75 hours is what you have left according to what you committed to at the beginning of this project, assuming you don't work weekends. 120 is if you treat it like the full time position. Or 150 if you go all out. A more demanding pace than 150 hours over three weeks is likely not feasible.

@alexrj