Hacker News new | past | comments | ask | show | jobs | submit login
Procedurally generating a rounded box mesh (wwwtyro.net)
121 points by wwwtyro 23 days ago | hide | past | favorite | 41 comments

I've written my fair share of this sort of code, but it's a very painful way to create geometry. I don't mean to be discouraging. I just did way too much of this myself, and I regret how much time I spent on custom primatives.

A 3D artist would probably create something like this by cutting the mesh and applying Catmull-Clark subdivision (assuming they didn't have a proper bevel tool). If you have a library of generic mesh manipulation functions lying around, the programmatic way and the artists' way would likely be the same. Creating those generic functions is a lot of work but it pays off fairly quickly. You need generic functions eventually anyway, to create more complex shapes.

It's also worth noting that the optimized mesh has some unfortunate drawbacks. Mesh properties are generally only stored on the vertex, and are interpolated across the attached faces. Having long, thin triangles or big differences in triangle area will often create problems when vertex properties are interpolated across the face. So, you may need to break those big faces into multiple triangles anyway.

Having long, thin triangles or big differences in triangle area will often create problems when vertex properties are interpolated across the face.

That can definitely be a problem in general, but is it likely to crop up in this case?

Those long triangles are flat so the normal is constant. Neither 2D nor 3D texture coordinates will have too much distortion.

And if it was a problem, you could fix it by scaling back the optimization, no?

If you have a library of generic mesh manipulation functions lying around, the programmatic way and the artists' way would likely be the same. Creating those generic functions is a lot of work but it pays off fairly quickly.

Yes, you’re right about that. I think this is still interesting and useful from the perspective of understanding how to build a basic mesh programmatically. And sometimes it’s easier to crank something out in a brute-force way like this than to figure out how to combine your general-purpose tools in just the right way.

It's a beautiful write-up and the technique can be useful sometimes. I just had flashbacks to the literal months I wasted doing this sort of thing for a dozen different shapes and the horror that was stitching them together. I wanted to communicate that the method described is not the way you would go about creating most geometry; you can be much more productive using higher-level geometry operations.

> That can definitely be a problem in general, but is it likely to crop up in this case?

Only issue I can think of is slight loss of precision along big surfaces, as partial derivatives will have bigger deltas. It's only a problem if your fragment shader maths is numerically sensitive to such things.

It's fine for use in rendering if this is the final shape and it will never be modified. You're just a bit limited in terms of what you can do with it.

By generic function, do you mean the catmull clark subdivision?

That would be one example of such a function, yes. Libraries like IGL or OpenSubdiv can help you to implement more, too.

Such a nice job on the visuals and interactive components! It takes a lot of work to craft a post like that.

I think it’s worth mentioning the ray marching (signed distance field) method for creating rounded boxes, because of how surprisingly simple it is - a single subtraction added to the sharp-cornered box does the trick. Even more fun, and relevant to the Apple story, it works exactly the same in 2d, and it can be used to anti-alias your 2d rounded boxes beautifully! (Useful if you want to render dynamic-radius rounded corners in real-time.)


SDFs are nice but to make a nice triangle mesh, you'll have to sample points on the isosurface, by geodesic distance.

I think the most common approach to convert SDF to polygons is called 'marching cubes' and it yields triangles and quads, but I guess you can always 'convex' (halve) the quads afterwards to get 100% triangles. It will most probably not be as neat and tidy as the mesh in the article though!

If you can identify lots of locations of points on the isosurface, it could probably be fairly easily triangulated in this case too since a rounded cube is a fairly simple and convex shape.. but the result will also be inherently noisy I think.

Guess it's all about the use case eh?

True! Yes, and this is a good summary of how the 2d anti-aliasing I mentioned works. Of course SDFs aren’t the only alternative to a mesh-free rounded box, there’s also ray-rounded box intersection. I think IQ has one of those too?

I agree it's utterly astounding what can be done with 'analytic' (ie 'vector' vs 'rasterized') SDFs, (and different ray-intersection/marching methods too) and what IQ does and how much he shares the actual code and ideas just fills me with gratitude every time I read/watch! Cheers for the link above, i'm definitely gonna have a play with some of those functions!

I'm still looking for my jaw after his painting with math girl

A small but crucial detail that sets Apple apart from almost everyone else in both digital and physical design is the use of curvature continuity.

"Posers" use G1 continuity, Apple uses G2 at a minimum if not G3. More complex math but smoother corners and surfaces. There's actually no 'radii' on Apple products.


A good 99 Percent Invisible podcast on this:


Squircles were actually part of the visual language of Nokia years before iOS 7 added G2+ continuity.


If you’re looking for “smoothness”, check out my treatise on the Euler spiral: https://xixixao.github.io/euler-spiral-explanation/

I have used superellipses as oscillators.

They look much better than rounded rectangles, and probably work with less and more equally spaced polygons in 3d. You can probably calculate the points as slices in azimuth, or as a continuous helical spiral.

They give larger curvature smoothness than rounded rectangles, and superformula gives a wide variety of shapes and smooth transition between a circle and a square with changing parameters.

Superformula is a generalisation of superellipse, and works in 2D and 3D. Superellipsoid is the 3D counterpart:

* [Superformula - Wikipedia] (https://en.wikipedia.org/wiki/Superformula)

* [Superellipse - Wikipedia](https://en.wikipedia.org/wiki/Superellipse)

* [Superellipsoid - Wikipedia](https://en.wikipedia.org/wiki/Superellipsoid)

Squircle is a special case of superellipse with parameters a and b equal and n set to 4:

* [Squircle - Wikipedia](https://en.wikipedia.org/wiki/Squircle)

Danish Piet Hein invented the Superegg:

* [Superegg - Wikipedia](https://en.wikipedia.org/wiki/Superegg)

An intuitive understanding or the mathematical formulas is that they describe an oscillating radius, which results in the various shapes as you move along the angle in polar coordinates.

I find it vaguely amusing that the author (and apparently yourself) claim that using simply rounded corners would be a "lack of care and detail". I mean if you prefer Apple's fancier corners then great, but shaming a manufacturer for using a perfectly serviceable rounded corner is a bit much IMO.

To quote Charles and Ray Eames: “The details are not the details; they make the product”.

For sure, but what details matter is often subjective. I've looked around my desk and surely the vast majority of the objects here use the simpler rounded corner but I really fail to see how it's bad craftsmanship.

If anything I'd argue that for professional appliances the circular corners convey a less organic, more industrial look that feels, to me, more suitable.

But then again, I enjoy brutalist architecture, so you can probably safely discard my opinion.

Can you explain the advantage of using these Gn curves instead of just using a larger radius?

In the Medium article, the comparison between the Apple and non-Apple would be less striking if the non-Apple version had a larger radius.

The difference is subtle, but there’s still a perceptible type of “corner” where the square meets the circle. So if you round a sharp 90 degree angle with a circle, you end up with two very subtle corners on either side of the circle, where the circle touches the flat edges. A larger radius doesn’t fix this, it’s inherent to the connection between a square and a circle.

One way to think about it is in terms of the derivative of the path (which is what “Gn” means). A straight edge has a constant straight derivative, parallel to the path. A circle has a constant derivative perpendicular to the path. When you connect the two, there is a discontinuity in the derivative, the rate of change of the path jerks suddenly from circle to straight edge. And you can see it visually, even though it’s pretty subtle. With a smoother curve, the derivative is also smooth, and then there’s no abruptness in the curvature where the two edges meet.

A better reference to Apple's rounded corners than BGR's blogspam (linked in TFA) is straight from the source at folklore.org, from Apple early employee Andy Hertzfeld himself:



Here's a better way.

Start with a mesh with 24 vertices which results in the cube with all vertices and all edges cut with planes. Each vertex of the original cube becomes a triangle.

Then iteratively split edges in half, projecting the split points onto the desired surface. The algorithm only needs to split edges near the vertices of the original cube, so the split+project step is like this:

    float3 midpoint = ( v1 + v2 ) * 0.5;
    float3 rv = (midpoint - sphereCenter).normalize();
    midpoint = sphereCenter + rv * sphereRadius;
Unlike the OP's code, will result in uniform triangle density of the mesh.

That's how people are usually generating good quality spherical meshes: start with icosahedron, then a few iterations of splitting edges in half + reprojecting back to the sphere.

I like this method better: https://prideout.net/blog/octasphere/

To me it produces more pleasant resulting mesh, which gets important with fewer subdivisions. Here's what it looks like: https://i.imgur.com/o3RFfZx.mp4

But the criticisms from slavik81 still applies, it produces long triangles with insufficient surface information for the flat parts.

Isn’t that exactly the same method?

(Still a useful link, though, as it’s a great writeup from a slightly different perspective)

Edit to add: doh, you’re right! I was too quick on the draw. Cube versus octahedron.

It's articles like this that actually get me interested in learning computer graphics. When I took graphics in college, I spent half my time debugging weird C++ build problems and the other half of the time trying to get X windows to forward over SSH from the school shared Linux machines to my personal laptop.

It would have been *so cool* to have had a course that could focus on just the neat graphics algorithms like this by having WebGL sandboxes for both the lecture notes and maybe even the homeworks!

The book https://www.realtimerendering.com/ is a great introduction. And, that site links several other great books that are available as free and legal downloads.

See here: [1][2] for something that might get you started. Have fun!

[1] https://github.com/stackgl/shader-school

[2] https://github.com/stackgl/webgl-workshop

I wish I’d had that too. I’ve told several graphics prof friends of mine they should do a whole course using ShaderToy. None have yet, but I’m pretty sure there are such graphics classes out there. I also love doing graphics stuff in Python and in Processing and similar environments - for precisely the same reason, that you get to make pictures without having to muck through C++ and devices and all kinds of low-level details. One of my faves, that I’ve used to create quite a few published book illustrations is called “NodeBox” - it has a GUI version but I loved the older pure Python API.

Somewhere in-between is JavaScript - it’s not quite as easy as NodeBox or ShaderToy, it’s not a sandbox necessarily, but it’s pretty damn easy to setup your own sandbox from scratch, you can do amazing amounts of graphics right in the browser with very little setup and very few low level details.

Very nice visuals, but "procedural generation" does not seem to be the right term for this code. Maybe it should be called an "algorithmic technique" instead, or something like that?

Procedural generation normally is a randomized process that does not try to get an optimal solution. Instead, it typically aims to be a generator for a large diverse population of "interesting" outcomes, where "interesting" is often a subjective metric, but does not really have to be.

At least to me procedural generation is anything created by computer code (ie. a procedure) rather than a human artist. Typically geometry, textures, or music. Randomness is a useful tool for creating "natural" forms but by no means a required or defining feature. Size-restricted demos (eg. 64k, 4k, or 1k intros) are a great example of procedurally generated everything.

Demos are fine without randomness, but what we see here is an algorithm or a numerical method to make a mesh.

It sounds like there's more than one sense of what "procedural generation" means - to me it means basically generation by algorithm (or some kind of automated setup) rather than by hand or 'manual' generation (like painting a picture).

Where I work there's lots of use of SideFX Houdini, and we regularly talk about how "procedural" any given setup is, where "more procedural" means either that it has a 'seed' that can be randomised, to generate an infinite number of varieties, or (more importantly) the setup is more capable of working with new versions of input assets (a new version of animation or a different 3d model, say), whilst still robustly producing a correct-enough result.

It sounds like gp might mean this sense, but you've got something more formal in mind?

Okay, yeah, I agree that the more important part in procedural generation is to be able to produce a large population of interesting artifacts. The means to get there can involve more or less randomness (it can be a small seed input, a set of parameters, or a random sequence of numbers).

Even something like Mandelbrot or Julia sets (or similar fractals) are fully deterministic algorithms, but the choice of the position and scale (quite a small initial input) is sufficient to generate a large variety of interesting results => procedural generation.

The procedure must be making some kind of sequence of choices that leads to a set of diverging final outcomes. The choices can be prescribed by some kind of input value, or determined by a PRNG of the generation procedure itself (also actually a deterministic sequence).

However, not everything made by a computed program should be called "procedurally generated". Word docs are not a result of procedural generation. Arithmetic operators and sorting algorithms are not procedural generation techniques by themselves (although they can be used in procedural generation as building blocks).

I think that we agree about the 'random-seed' type of procedural generation, however a word document is hardly even generated by an algorithm at all! It's usually generated entirely by the author (perhaps with semi-code-like templates if they use that part?). GPT3/etc would be an example of 'procedural' word-processing, to me.

Where we mainly might not agree yet is about setups that instead process input-assets, and the idea is not for them to explore the parameter-space, but just to re-execute the effect as close to as it was intended as possible, and how reliably they do this can be called how 'procedural' they are. It is not usually expected to involve huge amounts of extra exploration to find something that works for a new input, as long as the effect is set up to be 'procedural' enough. This is a VFX-based perspective and I'd expect a games-perspective on this stuff to be quite different!

I guess touch is still something to think about (trying to move that 3D box)

Cool website. 3D is so cool, I struggled with it using 3js but it's neat. The basic cube rotation tutorial/camera rendering pane... I hope to get into this stuff again.

Does anyone still draw rectangles as described in the linked anecdote? Or is it not worth the added performance now we have faster processors

Sweet geometry. Messing with the 2 sliders tool there, it strongly reminds me of the geometry generated by Chaikin or Split Tweak curve smoothing.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact