Here’s a first stab at the missing documentation for LLVolume.cpp — not on a line-by-line basis, because frankly, the code today looks way more complicated than the code I originally wrote. But this should, if I did my job, explain how prims work and what can be done under the hood. It doesn’t cover what could be done with new systems, but I’ll leave that for another day.
This is version 1.0. Comments are welcome, and I can take a 2nd pass at it later.
Volumes, Faces, and Prims
To explain the origin and construction of LLVolumes (the basic building block of almost every Second Life object), we’ll need to cover a few concepts in geometric modeling, and touch on some broader design issues in Second Life.
I’m going to talk tangentially about those broader issues, because a) I didn’t decide them myself, and b) I don’t know how proprietary Linden feels about some of these, open source client notwithstanding.
But what I think is obvious to any observer is that Second Life is a world built of Prims. Terrain, Avatars, Sky, and Particle Systems use their own unique methods. But 98% of the objects you see are Prims. Here’s why:
The original idea was construct a small set of physically-simulated primitives that could be used like virtual Legos to build any desired shape by simple placement, sizing, and customization. Small and simple objects compress well for network streaming – much better than most custom geometry approaches, and can be streamed at an amazing rate, thus offsetting how simple the objects are in appearance – i.e., you can use lots of them for cheap. This is one reason that it’s difficult to import 3D geometry – the network and rendering systems are simply optimized for prims.
The downside, of course, is that these pseudo-solid volumes are not as efficient to render as arbitrary hand-crafted polygons, since there are lots of overlapping and hidden surfaces (which take time to render, even if you don’t see them) and require lots of tiny state changes, including simple changes in position and orientation, each of which takes a small-but-cumulative amount of time for any 3D hardware system to set up and work through. If you’re interested in those issues, see my old scenegraph article for some explanation as to why, and how to optimize around that.
An ideal solution might work like Constructive Solid Geometry, where simple shapes are composed and combined on the CPU to make a more optimized mesh. But that takes lots of cycles, and, in fact, it’s much easier to just draw all of the prims. Real-time rendering often requires minimizing what the CPU does and pushes everything possible down to the hardware. So that’s what we did. Someday soon, that work can be done on the GPU, and then the equation might change.
So how does one efficiently build 3D volumes to make so many prims, and do quickly enough? Simplicity. There are hundreds of mathematical models for constructing volumes. There are sweeps, lofts, extrusions, implicit and explicit surfaces, subdivision surfaces, metaballs, and more. The key for us was keeping it to a small set, and my personal contribution to this was making one small piece of code that could do them all.
Now, LLVolume isn’t quite as small today as it was when I wrote it. But the main ideas still hold. The core concept simplifies geometric sweeps, lofts, and extrusions into a single operation, which I tend to call convolution.
The term comes from signal theory where one waveforms is essentially multiplied at every point along another. It’s also related to the cross-product for vectors, if that helps. We take two curves in space, 2D or 3D and multiply them perpendicularly such that we produce a 3D volume. One input is called the Profile and one is called the Path.
They’re named to imply that the profile is applied along the path. But in truth, there’s a natural duality which allows us to reverse things and often get the same result. That little swap will help explain some of the less intuitive results later on.
So here’s the equation of a cylinder, in symbolic form. We take a circular profile and convolve it with a simple straight line – a segment with a beginning and an end.
We can break down that equation into some procedural steps. Below, we’ve rotated the circular profile out of the plane and oriented its “up” vector to match the direction of the line. The circle is multiplied along the line at every point from beginning to end, yielding our resulting cylinder.
We could have just as easily reversed things and applied a line at every point along the perimeter of the circle. We’d still get the same cylinder.
Not every combination can be swapped so easily, and some produce what we call degenerate geometry. Because of that potential, there may be cases where path and profile choice might differ from what you might expect.
Now, in practice, “circles” in computer graphics are generally made up approximations, almost always akin to piece-wise-linear curves. That means every X degrees or linear distance around the circle, we get a new vertex, a point, and those points are connected by straight lines, not real arcs. It makes things simpler for the computer, and if done right, you’d never notice.
Naively, we can create a procedure that simply creates a vertex of our final object at each combination of vertices in our path and profile. If our circle is made up of 32 vertices and our simple path has only two (i.e., beginning and end), the convolution of those curves gives 64 new points on a cylinder.
If the profile was a square instead of a circle, it would naturally have four unique points in space. And when convolved along the same path, we’d wind up with a 3D box of 8 unique vertices. If the profile was a triangle, we’d get a wedge shape of 6.
Any 2D profile works pretty much the same.
And in a sense, that’s all we need to do for most shapes. But that’s not the end of the story. We need customizations, like twist, and shear, inner radius, and various cuts to consider. And then there’s “level of detail” or LOD to think about, where we want to dial in the amount of subdivision to use less geometry in the distance and more up close.
Remember when we said paths and profiles were 2D or 3D? If we store a “twist” amount around each point in a path, we’ve added one degree of freedom to each point. That’ll make the profile “twist” as we apply along the path for interesting results. If we allow the profile to rotate away from pure perpendicular application along the path, that adds two more degrees of freedom, for total of six. Not all of these controls are exposed to the end user, for better or worse, but they’re all possible.
So is “scale” — a seventh dimension — that lets us make the primitives looking like pyramids and cones by simply scaling the profile as we apply it along the path. If you could edit those parameters for every point on a path, you could even make horns, parabolic dishes, and obelisks in a single prim.
And remember, we’re still talking about the same basic operation – the convolution of two simple 2D to 7D shapes. There’s always the possibility of using multiple profiles, interpolated (or morphed) along the path. The way that could be achieved is through parameterization.
Parameterization simply requires that for any profile or path, we will create a parameter (call it T or U or V) that goes from zero to one (or any known values) along the length of the curve. And while we didn’t implement full parametric morphing between arbitrary profiles back then, parameterization of both paths and profiles is still critical for things like texture mapping, as we’ll see in a minute.
In the existing system, we have exactly one profile and one path per volume, which you choose by selecting a basic primitive type from a pre-defined list. You could probably choose individually, but there are protocol size implications Linden had to worry about.
Keep in mind, the profile and path can have as many vertices and can follow any general shape you want, as long as it doesn’t have true holes or self-intersect. In the case of a torus, both are circles of N vertices. But flexi-prims take advantage of moving a multitude of vertices in a path using animation functions to make wiggly, snake-like motions possible.
So let’s get to holes and cuts, since that’s important aspect of the design. It happens to be the thing that makes the system more complicated than it needs to be. In CSG, there is no need to define primitives with holes or cuts, because you can add those by subtracting one object from another. But remember, we couldn’t afford to do full CSG, so generating holes and cuts in volumes became more important up front.
Now, all primitives in the Second Life system are essentially the same. They’re all “topologically equivalent” to a cylinder or sphere.
Topological equivalence is one of those cool mathematic concepts with some important implications. Here’s how you can try it at home:
Take any 3D shape you can think of. You’re allowed to stretch, pull it, bend it any way you want, but you can never cut it or allow any part to pass through itself. If you can turn one shape into another, they’re topologically equivalent.
And if you play the game, you will see that a cube can be turned into a sphere, a cylinder, or even a banana. A glass is also equivalent, because you could grab the bottom of the inside and pull it out — there’s no constraint on preserving volume or mass. A teacup, however, is different, because its handle has a hole in it. There’s no way you could make or destroy a hole without cutting or allowing parts of the object to meet and therefore overlap in space (touching means overlapping in a strict sense). That’s a big hint as to how we handle holes, btw.
Cuts or Slices are a bit of a misnomer, actually. In the pie-chart profile to the right, there is no real cut or slice, at least not in the topological sense. All we’ve done is moved a section of the circle, a couple of vertices actually, into a new configuration. It’s still an arbitrary curve with no holes. Convolving that profile is now just as easy as convolving the original perfect circle — at least until you think about Linden’s concept of a “face,” which I’ll get to in a minute.
So in trying to make the simplest possible system, holes present a big challenge. But if you take the banana example, as I hinted at earlier, there’s an easy solution, and that is: don’t allow holes. Ever.
A circle with a “slice” in it, like the pie chart can be “hollowed out” as in the image above, without ever creating a true geometric hole. The interior potion is always connected to the exterior portion by the slice, and we again have a simple arbitrary 2D curve, which our simple system can handle. The slice is really just an operation that changes the shape of the profile. The convolution doesn’t need to know about it, except to the extent that it creates new faces (see below).
The only thing hard about it is knowing that if we have 0 degrees of slice (i.e., no slice), we need to omit those two edges that can never be seen. In fact, as long as holes can be tunneled to the outside by removing a secret slice, you could have any number of parallel holes in a profile – Swiss cheese if you like. And there is in fact no requirement that any hole even is the same shape as the profile – you could have a round hole in a square profile – as long as there are no interpenetrations, it doesn’t matter.
If 2D profile editing was exposed to the end user, you’d see some very complicated primitives being built using just the methods I’ve mentioned above. The tradeoffs would be different – meatier prims, but hopefully fewer of them.
So let’s talk about texture coordinates. In the case of a cylinder, the texture coordinates naturally fall out of the parametric solution. Consider our original example, with the individual texture coordinates noted for inputs and, if I could easily draw it, the output.
If the circle goes from zero to one around its perimeter and the line goes from zero to one along its length, then the outside of the cylinder properly goes from (0,0) to (1,1) around its perimeter too, just as if it was a flat quad being drawn with a basic texture on it and then bent into the shape we want. The parameters we used simply become the final texture coordinates, which can be scaled or augmented by special effects. The top and bottom of the cylinder can be thought of as simple circles inscribed in squares, where the square also run from (0,0) to (1,1) at its extremes. That makes mapping easy there too.
One minor complication is that for all modern (and ancient) 3D hardware, each vertex can only have one texture coordinate (per available texture unit, that is). When we go a full 360 degrees around the cylinder, the beginning and end line up in space, but must correspond to both zero and one in texture coordinates to finish the circle with no gaps or seams. So the typical answer is to duplicate the vertex – one for the beginning of the circle and one for the end, overlapped in space.
But in the case of a square profile, having unique texture coordinates per edge gets even trickier because each side can also have its own texture. Each hard edge or discontinuity in a profile implies a new face in geometric terms. And so a cube naturally has six faces. A cone has two. And a cylinder, as we said, has three. But a cylinder with a “slice” and “hole” in it has three more – one for the “interior” circle and one for each of the “cut” ends that are not exposed. Needless to say, most of the complication comes from handling these face boundaries and transitions.
Although we claimed a cube has 8 unique vertices, in practice, it has 24 – 6 faces of 4 overlapping vertices each. A cylinder made from a 32-point circle has not 64, but 128 vertices because the top and bottom cap need their own vertices.
To be blunt, faces are something I should have tried harder to kill or minimize, way back when. Most volumes can be thought of as solid materials, where the same texture should apply throughout. Indeed, a cube could be thought of (and is handled internally as) a curve with vertices at 0, 0.25, 0.5, 0.75, and 1.0 in the parametric space, with no separate faces required. So we probably could have defaulted to a sort of 3D texturing – one texture per prim, and automatic texture coords to make it look more real. Faces with unique textures became a real pain the ass to optimize for better performance, and they don’t help streaming much either.
I’ll stop there for now. For version one, let me know if anything isn’t clear and I’ll flesh it out a bit. And let me know if there’s a specific area you think I missed.