Thursday, August 10, 2006
Modeling and Slicing
Since Forrest switched over to using a grid view for his model decomposition technique (and has been making really good progress on it), I decided to see if I could get my ideas in a geometric slicing algorithm working. It also let me wet my feet working with the 3D data. Here are some of the images for the progress I've made. I've talked a little about the current limitations on the message board -- there are two degenerate cases on the inset algorithm that need to be handled 1. Clipping off tips in acute inner angles, and 2. clipping off intersections.) To exersize the code, I created this little widget model. It has some wavy fiddly bits in the middle of a sphere with a square hole knocked out of it. I modeled it around the concept that Forrest started with on his explorations.
Here is a wire frame image of the same model, hopefully, the little wavy fiddly bits make more sense with this.
The images that follow are screen captures of a Z Plane explorer I wrote to visualize the algorithm. I think it should demonstrate that the geometric approach should work well. You can see the degenerate cases pretty clearly here. I can zoom the Z plane around real time -- each layer is recalculated every time the scrollbar changes, and I'd guess it takes about .2 seconds to calculate and draw -- including slicing the model, and then performing the inset algorithm. The model is approximately 11000 triangles.
Here is a layer very near the bottom. It an intersetion type degenerate case. The inset borders intersect each other, and also extend beyond the borders of the object in places.
The black lines represent the triangles from the model (I got an STL import from blender to work, so it's not a problem like I originally thought. I did have to write an STL loader in C#, though.)
The red lines represent the inset algorithm operating on the black edges.
Here is one of the lowest non-degenerate planes. As I move up the model, we are good until the fiddly bits in the middle start to appear.
Here you can start to see the interior angle degenerate case. The interior angle 'horn' is extending a bit further than it needs to here. It should be capped to prevent it from growing even longer as the angle becomes more acute.
The degenerate case gets worse.
This is pretty close to dead center. Note the little horns. This is another the interior angle degenerate case for some really tiny triangles. My current idea for solving the degenerate case would probably leave bumps instead of horns for this particular situation.
All the remaining layers are mirror images of the above, so I won't bore you by posting them (And I seem to be having problems uploading images, anyway. I'm still a blogger newbie.)
Comments:
Links to this post:
<< Home
****All the remaining layers are mirror images of the above, so I won't bore you by posting them (And I seem to be having problems uploading images, anyway.****
That's been a problem for the last week or so. Try uploading them as small pics on the upload form. That seems to work better. It defaults to medium.
That's been a problem for the last week or so. Try uploading them as small pics on the upload form. That seems to work better. It defaults to medium.
BTW, that degenerate case that you show was just the sort of thing that drove me to using grids. I bailed out long before you did, however. Good luck on getting a good solution to that. It would be great if you could get it to work.
Wow Beagle, that is nice stuff! I like seeing your text and images, it helps me understand, being a programming ultra-newbie. I, ahem, know a little bit of FORTH. ;)
I'm stumped on the hornes at the top of the square, what is causing those??
I'm stumped on the hornes at the top of the square, what is causing those??
*** C#? ***
Yeah, everything written to generate the slices was written in C#.
*** that degenerate case that you show was just the sort of thing that drove me to using grids ***
I think I have a solution -- as soon as the filament has moved 'far enough' past an interior point, stop, move over to the opposite segment, and then start moving back along the other segment. Just need to get a little time to solve for it mathematically. Probably take me an hour or so to get the algebraic solution so it can be inserted into code.
*** I'm stumped on the hornes at the top of the square, what is causing those?? ***
Very likely, double precision round off error. When the segments get really really tiny (such as when you slice a piece off a triangle .00000000001 above the tip), the unit vector calculations I use to generate the inset angles start getting imprecise.. very imprecise in this situation.
A few solutions would be:
1. Replace really tiny segments with a single point, and get rid of the problem.
* I'll probably be doing this anyway, but it's low risk so I'm postponing it and working on the other degenerate cases first.
2. Cap interior angles -- as mentioned above. This would result in an ultra tiny 'bump' of length about the size of the base of the horn. The height of the bump would depend on how I decide to cut off the end.
Yeah, everything written to generate the slices was written in C#.
*** that degenerate case that you show was just the sort of thing that drove me to using grids ***
I think I have a solution -- as soon as the filament has moved 'far enough' past an interior point, stop, move over to the opposite segment, and then start moving back along the other segment. Just need to get a little time to solve for it mathematically. Probably take me an hour or so to get the algebraic solution so it can be inserted into code.
*** I'm stumped on the hornes at the top of the square, what is causing those?? ***
Very likely, double precision round off error. When the segments get really really tiny (such as when you slice a piece off a triangle .00000000001 above the tip), the unit vector calculations I use to generate the inset angles start getting imprecise.. very imprecise in this situation.
A few solutions would be:
1. Replace really tiny segments with a single point, and get rid of the problem.
* I'll probably be doing this anyway, but it's low risk so I'm postponing it and working on the other degenerate cases first.
2. Cap interior angles -- as mentioned above. This would result in an ultra tiny 'bump' of length about the size of the base of the horn. The height of the bump would depend on how I decide to cut off the end.
Filtering out and discarding very small details (geometry/polygon generation errors) might be a good approach.
It's used a lot with 3D software, two points within a set distance (usualy adjustable by the user) are just welded together, so as to discard the second point. It's also used to remove "leaky polygons" as Adrian calls them
It's used a lot with 3D software, two points within a set distance (usualy adjustable by the user) are just welded together, so as to discard the second point. It's also used to remove "leaky polygons" as Adrian calls them
I think I'm going to hold off addressing leaky polygon data. I feel I can use the 'garbage in/garbage out' excuse here. If I need to, I'll think about creating a "garbage compactor" utility to turn a garbage data file into a good data file.
Depending on how my intersection and acute angle cases work out, I may need to add some graph optimizations. One of the solutions creates (potentially many) more line segments for an inset operation, and the intersection processing has the potential of also exploding the line segment count. Removing tiny lines segments and segments forming angles near 180 might be useful, but I won't know until I get both cases fixed first.
Depending on how my intersection and acute angle cases work out, I may need to add some graph optimizations. One of the solutions creates (potentially many) more line segments for an inset operation, and the intersection processing has the potential of also exploding the line segment count. Removing tiny lines segments and segments forming angles near 180 might be useful, but I won't know until I get both cases fixed first.
Don't want to sound like a cracked record here, but the CSG approach eliminates all these problems. Firstly - it is incapable of representing an invalid object (it may not be the object you want, but it's always a real solid...); secondly, it's _really_ easy to offset.
As feeble as my voice may be, I'd like to second Adrian.
I have spent a good decade chassing polygons around computer screens. I've noticed 3d software (including some very slick high end stuff) never seems to have fully resolve polygon derived flaws. (None of which I saw in POV-RAY 11 years ago!)
Programmers and users always end up having to waste time patching things up at different levels, most of all when files are sent from one application to another.(Shiver)
I suspect CSG might be a time saver over...well, time! Maybe me threatening to apply my newbie FORTH skills will jolt a brave soul into action! It could get ugly... ;)
I have spent a good decade chassing polygons around computer screens. I've noticed 3d software (including some very slick high end stuff) never seems to have fully resolve polygon derived flaws. (None of which I saw in POV-RAY 11 years ago!)
Programmers and users always end up having to waste time patching things up at different levels, most of all when files are sent from one application to another.(Shiver)
I suspect CSG might be a time saver over...well, time! Maybe me threatening to apply my newbie FORTH skills will jolt a brave soul into action! It could get ugly... ;)
***
..Maybe me threatening to apply my newbie FORTH skills ..
***
lol. Back.. you.. you.. FORTH programmer!! Actually, I wrote a forth compiler/interpreter in C back in 1990 or so. It's a nice language for some applications, but can be a bit unwieldy for others.
Anyway, the simple approach to solving the acute angles problem made things worse for some very fine detailed test cases (I thought it worked because of my testing with some simple large detail models.) Also, it appears I might have to solve the intersection cases first. They are needed for my next approach to solving the problem. (I'm going to try one more idea before I give up.)
I know, CSG works.. but I'm a mathematician at heart, and this problem is just too juicy to pass up right now. :)
..Maybe me threatening to apply my newbie FORTH skills ..
***
lol. Back.. you.. you.. FORTH programmer!! Actually, I wrote a forth compiler/interpreter in C back in 1990 or so. It's a nice language for some applications, but can be a bit unwieldy for others.
Anyway, the simple approach to solving the acute angles problem made things worse for some very fine detailed test cases (I thought it worked because of my testing with some simple large detail models.) Also, it appears I might have to solve the intersection cases first. They are needed for my next approach to solving the problem. (I'm going to try one more idea before I give up.)
I know, CSG works.. but I'm a mathematician at heart, and this problem is just too juicy to pass up right now. :)
I've actually been looking a lot at the CSG approach the last few days; I've been trying to work through deriving the curve that is the intersection of all of the primary BRL-CAD primitives with a plane. The arb8 (six-planar-face shape defined by eight points) and ellipsoid are not bad, but the truncated general cone has been giving me headaches. I think that it'll always produce something at least related to a conic section, but I'm not sure. It's this sort of linear interpolation between two arbitrary ellipses in three-dimensional space. Tremendously convenient to have around, represents all of your cylindrical and cone-shaped bits in the same form, but not so easy to deal with mathematically at my level. Of course, getting something to work for bag-of-triangles would be good, as that's what STL files and other facet-based formats come in as. Thinking of it, there is also the torous, which might be useful.
The intersections of conic surfaces will yield intersection lines described by solutions to 4th order polynomials. It gets really ugly solving these. I don't think you'd want to try going up to the torus, which, as a 4th order polynomial surface, would result in having to solve 8th order polynomials (for a torus intersecting a torus.)
If you do have the general 2nd order, 3rd degree polynomial surface intersections licked, estimating a torus with 2 or 3 flattened elipsoids and 2 or 3 one sheet hyperboloid can give a pretty accurate representation. It's a lot better than polyhedron approximations with 100's of faces.
If you do have the general 2nd order, 3rd degree polynomial surface intersections licked, estimating a torus with 2 or 3 flattened elipsoids and 2 or 3 one sheet hyperboloid can give a pretty accurate representation. It's a lot better than polyhedron approximations with 100's of faces.
I'm not looking at the intersections of two arbitrary quadric surfaces; I'm looking at the intersections of quadric surfaces (at least, I think that the tgc is a quadric surface, it's just an odd one), and a plane. I believe that leaves me with getting out a quadratic... and a quartic for the torous, which certainly isn't nice, but if things really go badly I can represent that as "the solution of the intersection of this surface with this plane" for an exact representation, and then use splines to actually generate positioning data for the machine.
What I'm trying to work out is first what the curves will be, then how to define a new curve that is the set of all points such that the minimum distance between that point and any point on the original curve is a specified constant... then working out where the toolpath changes from one curve to another and all. It may very well be intractable, but I'm finding it interesting to try.
Partly I just can't stand the way STL works - as a format it seems to me to leave a lot to be desired, and I'd love to have a system that operated on a higher level than facets. And I like BRL-CAD.
What I'm trying to work out is first what the curves will be, then how to define a new curve that is the set of all points such that the minimum distance between that point and any point on the original curve is a specified constant... then working out where the toolpath changes from one curve to another and all. It may very well be intractable, but I'm finding it interesting to try.
Partly I just can't stand the way STL works - as a format it seems to me to leave a lot to be desired, and I'd love to have a system that operated on a higher level than facets. And I like BRL-CAD.
Hmm... Oops, you're right. Solving for intersection keeps the highest degree polynomial. I think I was confused with multiplying them together to get the XOR volume.
Post a Comment
Links to this post:
<< Home
