Algorithm to produce rounded edges and corners in a 3D mesh

I post this as an answer because I can't put images into comments.

Sattle point

Here's an image of two brothers camping:

sattlepoint

They placed their simple tents right beside each other in the middle of a steep walley (that's one bad place for tents, but thats not the point), so one end of each tent points upwards. At the point where the four squares meet you have a sattle point. The two edges on top of each tent can be rounded normally as well as the two downward edges. But at the sattle point you have different curvature in both directions and therefore its not possible to use a sphere. This rules out Svante's solution.

Selfintersection

The following image shows some 3D polygons if viewed from the side. Its some sharp thing with a hole drilled into it from the other side. The left image shows it before, the right after rounding.

alt text .

The mass thats get removed from the sharp edge containts the end of the drill hole.

There is someething else to see here. The drill holes sides might be very large polygons (lets say it's not a hole but a slit). Still you only get small radii at the top. you can't just scale your polygons, you have to take into account the neighboring polygon.

Convexity

You say you're only removing mass, this is only true if your geometry is convex. Look at the image you posted. But now assume that the viewer is inside the volume. The radii turn away from you and therefore add mass.

NURBS

I'm not a nurbs specialist my self. But the constraints would look something like this: The corners of the nurbs patch must be at the same position as the corners of the scaled-down polygons. The normal vectors of the nurb surface at the corners must be equal to the normal of the polygon. This should be sufficent to gurarantee that the nurb edge will be a straight line following the polygon edge. The normals also ensure that no visible edges will result at the border between polygon and nurbs patch.

I'd just do the math myself. nurbs are just polygons. You'll have some unknown coefficients and your constraints. This gives you a system of equations (often linear) that you can solve.

I'd rather have a general-purpose algorithm, but for my current purposes the maximum number of faces around a corner vertex is 5. Also, you may assume the mesh is always closed. I don't know much about NURBS surfaces, but even with NURBS it seems to me the problem remains of how to blend the various rounded edges that meet at the corner.

Adrian Lopez 2010-08-14 23:16:18

NURBS seem to be a good idea. They can handle all the special cases and offer great flexibility. Since they're based on polynomials they cannot form perfect circular forms like cylinders. But they approximate them very well. Basically what you do is, you set contraints at the boundaries of the NURBS patch, like that it should connect to the shrunk polygons and to neighboring NURBS and then let the 'math' fill the surface smoothly.

Lawnmower 2010-08-15 19:47:40

I'm not able to visualize it, perhaps due to my relative lack of experience with NURBS. How would the control points be arranged? What would be their weights?

Adrian Lopez 2010-08-16 07:01:08

In section 8.7 of Piegl and Tiller's "The NURBS Book", the authors discuss the creation of rounded edges and corners (also known fillet surfaces) for the case where 3 edges meet at a vertex. For corner fillets in general, however, the authors go on to say the situation "is more complex", and that a corner patch "may not even be representable as a NURBS surface."

Adrian Lopez 2010-08-20 01:20:06

Spheres would work when all the incoming edges have curves with the same radius, but what about when the incoming curved edges have different radii (as when not all the faces that meet have the same angle between them)? How would you blend them in that case?

Adrian Lopez 2010-08-15 17:59:47

@Adrian Lopez: I would not use different radii for the cylinders. You can accomodate different angles between adjacent faces by just changing the segment angle.

Svante 2010-08-15 18:21:51

@Svante: What do you mean "changing the segment angle"?

Adrian Lopez 2010-08-15 19:10:23

@Adrian Lopez: You can accomodate all possible angles with a single radius. Visualize the faces as tangential planes to the cylinder. The planar angle is the same as the angle of the visible segment of the cylinder, independent of the radius.

Svante 2010-08-15 21:46:05

@Svante: For a single radius to connect the edges of two polygons, the cylinder's position would have to be shifted up or down depending on the angle between polygons being less or more acute, respectively, which seems to me would make blending the edges at a corner even more difficult. Also, it may lead to situations where the cylinder would be located so far away from the edge that it would lie outside the opposite ends of the polygons themselves. Finally, I would need a different approach to creating the initial gaps between polygons than my current method of shrinking them all in place.

Adrian Lopez 2010-08-16 06:49:22

@Adrian Lopez: Of course, you need to choose a radius that does not "eat" a face completely. I think that the easiest approach is to construct an "inner polygon" which is defined by having all faces at a fixed distance equal to the radius to the corresponding outer face. These faces are then translated out by the radius, the edges used as axes for cylinders of the radius, and the corners as centres for spheres of the radius.

Svante 2010-08-16 11:22:08

@Svante that's the way, but it will only work for convex geometry. Also small geometry will cause all sorts of problems. This is how it would work for convex geometry: for each surface of the polyhedron (the polygons), create the corresponding plane. Translate each plane torwards the inside by r. Treat each plane as an inequality. The points satisfying all inequalities make the "inner polyhedron" you where talking about. The way with the inequalities ensures that small geometry is handled properly (that is, it vanishes).

Lawnmower 2010-08-16 14:52:33

(1) I thought by "sattle point" you meant something else, but it's basically what I was thinking of when I said to Svante that spheres wouldn't work when not all polygons that meet have the same angle between them, as in the image you've presented. (2) I see now what you meant by self-intersections. For some reason I was thinking of the large polygons being angled in the opposite direction as in your image. I don't know how to address it except by rounding the small geometry more aggressively or the large polygons less aggressively. It's not likely to become an issue for my purposes.

Adrian Lopez 2010-08-16 16:41:40

(3) I see now how a convex polygon would gain mass at edges where it's convex. (4) I'll have to think some more about the NURBS approach before I comment on it.

Adrian Lopez 2010-08-16 16:42:14

regarding (3): mass is lost at convex edges and gained at concave ones.

Lawnmower 2010-08-16 17:23:41

@Lawnmower: Doh. I got convex and concave mixed up.

Adrian Lopez 2010-08-16 17:52:17

@Lawnmower: On the matter of NURBS patches, can the polygons that make up the cage of a NURBS surface be something other than quads? I don't know how to connect the various corners of the scaled-down polygons using only quads. For instance, the cube in my mockup has three polygon corners meeting at each of the cube's corners, while more complex shapes could involve more than four.

Adrian Lopez 2010-08-16 18:02:22

afaik this should be possible. quads are the just easiest, most common case. I'd dig into the nurbs math, you'll have to anyway. I'd guess that in the end you'll end up using a trianglar (or what ever) subarea of the (u,v) parameter space.

Lawnmower 2010-08-16 18:39:01

It now occurs to me that I can turn any convex polygon into a group of quads by adding a central point and connecting the midpoint of each edge to this central point. I could then attach these to quads that make up the rounded edges and treat the whole thing like a NURBS surface. I just don't know if there's likely to be any smoothness problems with such an arrangement of quads for the NURBS control cage.

Adrian Lopez 2010-08-16 20:55:45

"midpoint of each edge to this central point" wouldn't this produce triangles? For quads you'd have to use two 'original' edges plus the two that you get by connecting to the central vertex. This opens the question of what do to if you face an odd number of edges..

Lawnmower 2010-08-16 21:05:59

In order to get triangles you'd have to connect the central point to each of the polygon's vertices. When you connect the central point to the midpoints of the polygon's edges, you get quads instead: half of two contiguous edges plus lines from the midpoints of those edges to the central point makes four edges and therefore a quad.

Adrian Lopez 2010-08-17 00:22:12

you're right! Smart idea.

Lawnmower 2010-08-17 06:47:19

ansaurus

tags:

views:

answers:

Algorithm to produce rounded edges and corners in a 3D mesh

related questions