Procedural Geometry Generation

Question

I have recently been looking into SceneKit for OS X and noticed that there are several factory methods to create geometric shapes such as:

Box, Capsule, Cone, Cylinder, Plane, Pyramid, Sphere, Torus and Tube.

I am interested in adding such primitive shapes to my renderer but am struggling to find any reasonable source from which I can gather an understanding of procedural generation. There are several resources which detail the theory, but lack the appropriate source code to back it up.

SceneKit provides factory methods which allow for dynamically setting the attributes of such shapes. In the case of the Box, you can provide integer values for the number of width, height and depth segments which each face should be divided into.

I understand the theory but lack the knowledge to begin subdividing geometry faces to achieve the desired effect.

The vertices for each shape are most likely quite easy to generate in simple loops. What stumps me is knowing how to create the faces, or rather the appropriate texture coordinates for each face. Normals can be calculated per face so I'm fairly confident I could achieve what I want, it's just knowing where to start.

Can anyone provide any details on procedural geometry? What I really need is some source code to glean some information from. I have searched high and low for tutorials but have so far come up with only a few reasonable sites or blogs. Any good books, tutorials, blogs or research papers would be appreciated.

Edit based on comments

I should have clarified that I know how to create vertices for basic shapes, most of these can probably be achieved by simple loops. What I don't comprehend is how to create faces from the generated array of vertices. How do I create a triangle strip, or triangles, from a seemingly unordered array of vertices?

I assume that once I get past this point, I can create the normals from each face. Whilst I haven't delved into this yet, I have seen a lot of references to this and am sure it will be easy enough to implement.

Ideally, i'd like to be able to generate geometry from a given set of properties such as the way that SceneKit provides. Given SceneKit has done it, and you can do similar things in Blender and Maya etc, I assume i'm not trying to implement the impossible.

The final aspect would be applying textures. Again, this isn't something I have implemented but have read up on and am aware of the requirements.

The main problem here is that I know what I want to achieve but am struggling to decipher how to implement for the aforementioned primitives. I was hopeful that I would be able to find some semblance of knowledge by way of source code but I really haven't come across anything suitable so far.

Answer 1

The way to generate the edges and the faces of a primitive shape like a box, a cone and all those you cited is to generate them at the same time you create the vertices. In fact, you should create the vertices in a logical way that makes it easy to compute the edges and faces accordingly.

There are algorithms that take as input a set of points in space and compute a so-called "point set triangulation" over it, but the problem of point set triangulation is NP-complete, so that it is faster to make the edges and faces as you go than to just compute the vertices and let an algorithm do the work. Just letting you know this solution exists.

Apart from this inefficient solution, I reckon you can only treat the primitives on a per-case basis, as in the examples that follow.

A mesh is vertices and faces. The edges are contained within the description of the faces unless your mesh contains lines that do not make up faces. The vertices are tuples of 3 floating-point coordinates. The edges are simply pairs of references to the vertices, but then again you surely won't need them. Say for instance that your vertices are in an indexed array. Well your your edges could then be pairs of indices of that array. The faces are triplets of references to vertices or triplets of indices in the indexed array case.

You should be able to count the vertices, edges and faces that make up each of these primitive shapes because being able to count them means understanding the properties of the object which helps you devise the method with which you'll build them, using loops and other tools as we'll see.

Cone

For a cone with n+2 vertices, 3n edges and 2n faces:

1. Make two separate vertices.
2. Make a circle around one of the vertices (the base vertex), that is within a plane perpendicular to the segment between the first two vertices. Hopefully you can make a circle using trigonometry, right? That's already all of the vertices of the cone. That's also one third of all the edges (there are n edges in the circle and 3n in total).
3. Make n edges from the base vertex to the n vertices in the circle. You can make one half of the faces (that's n faces) as you do that.
4. Make n edges from the tip vertex to the n vertices in the circle. You can make the other half of the faces (that's n faces) as you do that.

1) 2)
3)
4)
End result:

You can also create the edges and faces as you run the loop that makes the circle. Same complexity, same thing. Make one vertex on the circle, store it into your array of vertices, add the corresponding edge (pair of indices) to the array of pairs of indices if you feel like it, and finally add the corresponding face to your array of triplets of indices. Move on to the next vertex.

The cylinder and the tube: not doing the same work twice, and quads

Again, for the tube it starts with a vertex and a circle which will be the center of either the top or the bottom disc of the cylinder:

1. Make a vertex.
2. Make a circle around the vertex. Add edges (if you want edges) between the successive vertices of the circle and between the center vertex and each circle vertex. Add faces between each triplet of vertices made of the center vertex and two successive vertices on the circle.
3. Duplicate all that, translate the copy in the direction perpendicular to the base you just made, by the length of the desired cylinder.
4. Link the top and the bottom.

To link the top and the bottom, you must make quads between pairs of pairs of vertices that face each other. So think ahead and why not make yourself a function that makes two triangular faces out of four vertices?

Done. Notice that this time we use the fact that the same structure (circle + center) appears twice in a cylinder to take a shortcut. We don't have to make all of the vertices, edges and faces by hand, contrary to the cone where it was necessary.

Following this laziness principle, it's also possible to just make one quarter of the circle and duplicate it, and again, to make a full circle with very simple transformations (valid with any circle so with the cone too), but that's really overkill for a not so complex shape.

You must always use the geometric properties of the objects you make to simplify their making. Namely, their symmetries and invariants.

For a cylinder, just don't make the base vertex, just make the circle, duplicate, translate the copy, make the quads, done.

The sphere and the capsule: adding complexity, still not the same work twice

To create a capsule, we want to create a UV sphere, split it into two halves, translate the first half and then link the two with the sides of the capsules.

Again it's possible to make only one eighth (!!) of the sphere, then duplicate it and reverse it, and then duplicate and reverse the result except along another axis, etc, to get a full sphere, in 4 steps (create the eighth, duplicate and reverse three times). Maybe overkill, but less so than in the case of the circle.

A simple UV sphere:

We in fact only make one half of it (for example), duplicate that half, turn the copy upside down and translate it by the length of the capsule:

We link the top and bottom half:

The real (somewhat) hard work comes from the trigonometry that goes into making a sphere. The set of all vertices belonging to a UV sphere can be described as the set of all points of the form:

where R is the radius of the sphere and, for a certain positive even integer N, we have the constant

θ = × π/N,

k and n are integers with k varying from 0 to 2N-1 and n varying from -N/2 to +N/2.

To make a half-sphere or an eigth of a sphere, you have to restrict the set of values taken by k and n.

If k were real numbers and not just integer numbers, you'd get a whole sphere, not just the vertices on its surface. So what we've done here is rasterizing the surface equation of the primitive.

The fearsome torus: it's easy after all we've seen!

Again, more trigonometry, more vertices, more quads, more symmetries, more invariants... more geometry! Find out the equation for the surface of a torus, "rasterize it" properly, simplify the problem using the (obvious) symmetries of the torus and, finally, loop through the set of vertices you just defined and make the edges and faces as you go!

See? Completely straightforward.