3d fillet algorithm prototype

So someone (Gosh I love starting with “So”. It’s so… so… 21st century) suggested OpenSCAD needs a ‘fillet’ command.

Actually someone has a name, Alex Davies, who has made a 3d printed violin.

http://www.youtube.com/channel/UC3uf5smi5KrvhZvBs8tYqUA?feature=watch

Anyways the problem with doing this is that there are, apparently, no open source free 3d fillet algorithms out there.

So let’s invent one!

After farting around on google with ‘fillet’ and ‘algorithm’ a while I find this 2d fillet algorithm discussion

http://topomorph.info/post/The-fillet-pseudo-code.aspx

OK. Interesting but lets expand it to 3d and throw out the complicated stuff.

Basically Topomorph is using the ‘offset’ idea to do fillets. OK. So, first, what is ‘offset’?

CGAL Has 2d offset already. It’s like “growing” or “shrinking” a polygon, but in a way so that your ‘new’ polygon has sides that are the same distance from the old polygon. If you straight out ‘scale’ shrink you dont get that. See here:

CGAL’s 2d offest:

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Straight_skeleton_2/Chapter_main.html

Giles Bathgate’s Rapcad uses CGAL’s offset, and explains why it’s not the same as ‘scale’

http://gilesbathgate.com/2012/09/01/offset-advantage/

OK. Now we understand 2d offset, sorta. We also understand, from TopoMorph, roughly how Offset can help make Fillets.

How do we do it in 3d then?

First, lets simplify the Topomorph method. Instead of Arcs and stuff, let’s just do a simple triangle, between simple intersection points. Imagine two squares intersecting — the blue and red are their offsets. The shape on the bottom  is the result of “fillet union”, with a ‘triangular’ fillet shape instead of a nice arc. It seems relatively simple to do something like this in 2d, given that you already have ‘interesection’ and ‘offset’ functions. . . .

Image

Now, how does this work in 3d?

Imagine two 3d shapes. Shape1, Shape2. Let’s do cubes.

What does a cube and it’s offest look like? Like this:

Image

One box ‘inside’ another.

OK.

So what if we intersect these things? First we have to know what two cubes looks like:

Image

OK.

Now, imagine we make these cubes into pure-surfaces, no ‘inside’ volume.

Now. Imagine these three things:

  1. Intersection of shape1 surface with shape2 surface
  2. Intersection of shape1-offset with shape2
  3. Intersection of shape1 with shape2-offset

Those are three ‘polylines’ (lines in 3d space with vertexes, connected by a single line once each)

What does this look like? Behold.

Green polyline = interesection between the cube surfaces.

Image

Red line = offset of left-hand cube intersected with surface of right-hand cube

Image

blue line = offset of right-hand cube intersected with surface of left-hand cube

Image

Both offset-intersections shown together:

Image

OK. So we have these things. What do we do with them?

Connect them, of course. The ‘triangle’ in pink here is an attempt to show the new edges created when we create ‘faces’ from the extant polylines and vertexes for our fillet.

Image

And finally. Let’s imagine the faces drawn without the wireframe.

Image

It is an analogy to the 2d ‘fillet join’ of squares, above. Instead of two 2d-triangles, we are here using a triangular-cross-section ‘tube’ to ‘fillet’ between the two cubes.

But what if we want a smooth fillet?

Remember our first example, the like to TopoMorph. We can modify the triangles so that they are curves, and draw more faces between them.

———————————-

That’s all well and good. But how do you actually implement such an algorithm?

I am not quite sure. And that is where another idea comes in.

Using multiple ‘offset’ intersections.

Imagine taking the blue polyline, and making another blue polyline ‘offset’ a little bit more from the original. That gives us a sequence of , well, faces, and helps us build our face set. Maybe.

But what could it also do?

Imagine multiple red offset polylines, and multiple blue offset polylines. Now draw a simple flat face between each one. Union. What does that make? A Bezier curve is what it makes. Remember from Wikipedia. A bezier curve is just the curve formed by drawing straight lines between points on two line segments joined at an angle.

Image

Now imagine that in 3d, multiple blue offsets, each connecting a single flat face to a matching red offset. If you get the ordering right, you get a 3d sequence of flat faces that together form a Bezier curve style surface. Yay. Nice Fillet.

“And nobody had to get nailed to anything. ” – Douglas Adams

——

Ok that all sounds nice. Why don’t you just bash it out in a weekend in C++ then?

The hurdles are as follows.

1. There is no 3d offset in CGAL. You’d have to invent it.

2. What if the two cubes touch exactly on a single surface? Then you have a polygon not a polyline. Same for the offsets. How to deal with that?

3. What about ‘holes’ in the shapes? What about those intersections? What do you do, for example, about a hollow cylinder ‘fillet joined’ to a cube?

4. How does the computation time of ‘offset’ compare against the computation time of Minkowski Sum? Because you can do Minkowski Sum to do alot of this same stuff. It’s just sooooo slooowowwwwww in CGAL.

5. How do you actually connect the proper vertices and edges in ‘facets’ when creating the fillet polyhedron? What algorithm is that? How robust is it ? How do you test it? Do you have to invent it from scratch?

6. are you sure there are no open source programs that do this already?

7. are you sure there are no free algorithms out there that do this already?

In the end, though, i think it would be an interesting project, worthwhile at least.

At least to start, we could do it in 2d, and it wouldn’t be that impossible to implement.

 
Advertisements

About donbright

don bright http://github.com/donbright
This entry was posted in Uncategorized. Bookmark the permalink.

5 Responses to 3d fillet algorithm prototype

  1. donbright says:

    lol, very fascinating library here that does some filleting (they dont call it filleting)

    http://www.iearobotics.com/blog/2012/09/13/enhancing-openscad-ii-bevel-library/

  2. It might be interesting to have a look at how Implicitcad does this, although its probably not applicable to BRep primitives. I also think that OpenCASCADE supports fillets.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s