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

(version 1.0)

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.

Any chance you could generate this as PDF? It would be much easier than reading it in flash in a web page. Plus, google can then index it.

I’ve posted the HTML so it’s easier to read, except converting the vector graphics winds up as GIFs which I won’t try to resize, since they’re not even antialiased.

If anyone wants the original Word file to try to clean this up for HTML, just email me.

Pingback: Jeff Barr’s Blog » Links for Thursday, August 28, 2008

Thank you, Avai. This helps greatly and I want to encourage you to write more to help folks understand some of the geometric issues.

Thanks for this clear, careful explanation. I appreciate the time you took to explain these ideas as simply as possible, avoiding jargon as much as you could reasonably do.

I suspect that, in spite of the problems you identify with the existence of “faces”, that faces needed to be there, and were a good decision, because, ultimately, the point of SL is to get people to use and enjoy it. Users need to be able to “paint” their objects. If SL didn’t offer us the power to put different textures on different parts of a prim, we’d probably just use more prims. I’m sure of that.

Whether it would be better to use more prims, or to use multiple textures, I cannot say, but I realize there may be a “tipping point” where one strategy becomes more efficient than the other.

Thanks, Jasper. I’ll try to make it clearer in the next revision that I’m all in favor of being able to put unique textures on parts of prims. I just don’t think faces are the way to do it.

If prims are first considered a single material and texture, you can always add texture layers on top of that. One layer could be for custom-painted texture areas anywhere on the prim — grafitti or posters, or whatever — and these could wrap the prim in any way, not just per face. Other layers could add reflection, bump mapping, and so on. You could even have a 2nd material and use a texture layer to blend between the two, much as terrain blends between multiple materials in different places.

There’s no reason you couldn’t then emulate what you get now, plus a lot more, and avoid the cost of having one prim fall into multiple rendering queues.

Hi Avi,

Met you briefly at Metaverse Roadmap back in Feb when you talked about BigStage.

Really sensational post. Very timely for us. We have been taking an interest in OpenSim and SL as we moved towards announcing we are open sourcing more of the VastPark VW technology. It all feels a bit foreign and kluged together. We’ve had the benefits of 5 years of rebuilds in private! We focussed on hard core Web-sized issues that SL has smacked into: Web scalability, distributed eco-system, file format abstraction so developers can “write once run anywhere”, multi-format syndication and referenced-based remixing, simple multi-user networking and so on. We just kept going back to the drawing board. But now I can see the open source (OpenSim) express is starting to leave the experimental platform and “standards” orientated platforms like VastPark need to create a 1st class seat for themselves or else look like every other proprietary world with a widget system. Woopee! While Flash, Unity and some future MS effort may play strong roles I don’t think the rest including Lively are so significant to the future of the Immersive Web.

The real question for us now comes: How do we standardize around some of the key SL concepts that will benefit this future web without losing the good stuff we’ve developed like importing of mesh, media format abstration, lean and mean open markup language (IMML), simple conceptual structure, seamless runtime linking between worlds and more. The key think is which bits are worth keeping. I know people focus on the Avatars – fine, that can be a plugin – but should SL’s prim system be converted into the local platform’s structure or show it end up being replicated?

I dunno. I don’t know if it’s really the way forward, but we’re enthusiastic about the people involved in OpenSim and the community of experts like yourself who are doing the spade work on so much of this. It’s fascinating moment in the Web’s development.

Hope Seattle and the new job is treating you well.

Thanks, Bruce. Great comments.

I hope to be able to talk more about the more generalized prim system I’ve been thinking about.

Excellent explanation, Avi, that leaves me with a very clear idea of how everything got started and just how much potential there can be within the basic building blocks within SL. I watch the OS project with great interest too as it promises so much just from its potential to cross borders 😉

Ah, great post! A very fun read for me, and confirmed the mental model I had built up from working with the prims for years as a user. It also has sparked up my imagination, picturing all the things that could be possible by extending the algorithm to support different paths and profiles — squares, triangles, other regular polygons, stars, and so forth.

Perhaps you could offer some insight on a few things that I have been curious about:

1) It feels to me like Path Cut and Profile Cut are reversed for Cylinder/Box/Prism compared to Torus/Tube/Ring. That is, for Box et al., “Path Cut” seems to clearly edit the profile, while “Profile Cut” seems to edit the path (using a modified client or the dimpled-sphere-to-box trick to edit that attribute). Is this part of the interface, or part of the volume algorithm? And, was this a design decision, an oversight, or am I just thinking about the geometry in the wrong way?

2) Am I correct in thinking that it should be possible to have torus-like prims, but with a square or triangular path instead of a circle? I.e. something visually similar to 4 wooden rods joined into a square frame (or 3 into a triangular frame). Is there support in the volume algorithm for such square and triangle paths?

3) Could you talk about the “Planar Mapping” texture coordinate algorithm? I’m particularly interested in knowing the origins of the strange effect it has when applied to spheres and other rounded prims.

For 1 and 2, yes. Some things are reversed because it makes more sense to swap path and profile. And a profile can really be any non-self-intersecing shape, but preferably one that doesn’t result in self-intersecting geometry when applied along the path.

For 3, you get different texturing results depending on how you select paths and profiles for making spheres. There’s more than one choice. Convolving a semicircular profile around a circular path gives spherical coordinates. But you could also imagine a sphere built as a circle convoled over a straight line path that has its scale set such that the result is a sphere instead of a cylinder. That could be made to have a much better texture projection, especially for the poles.

Pingback: The 108 faces of a cube « Through the Broken Looking Glass

Pingback: Understanding Virtual Worlds | Insight Into SL Prims

Very interesting, I know this is a bit of a late post.

I did have a question as to why the ability to use more of the points isn’t available to the user? I enjoy making complex geometry, and would prefer making it in SL rather then sculpting it.

This would include a more practice (in my opinion) though more complex extrusion system. That would be more like you would find in 3D design software.

Dear Avi – can I ask a very techie question? I have scripted an importer for 3ds max > SL and I am just adding an automatic texture align script for prims which need special texture mapping like cut or tapered prims etc.

I am stuck on one single type – that is planar texture applied to the sides of a tapered or sheared box prim – it has to be planar to avoid texture tearing – but there is a shift in the planar numbers when the prim is tapered or sheared – the sloping side texture is offset and stretched. This needs to be corrected and it would be great to get the script to do it – but I can’t figure out how to measure the effect – it looks as thought the planar map is projected from a central point somwhere and distorts when the prim changes shape or proportions. Would love to understand this.

{PS – how I wish I had known about this site a year ago – great stuff

Toby, I’m not sure of the current way they’re handling texture projection. Originally, a tapered or sheared box worked just like any box.

As I mentioned, if I had to do it again, I would eliminate the Face concept and just begin with simple projections of the same texture everywhere, applying special cases as decals.

The popping you’re seeing could be from some mismatch between faces and actual sides — maybe some optimization kicking in.

Sorry I couldn’t be of more help.

Hey thanks for replying Avi. I have written a workaround so no problem really – but just to torment you further – tell me – is this not the code that produces the planar projection ? ( line 73 ) :

http://bitbucket.org/lindenlab/trunk/src/e2726e788831/indra/viewer/llface.cpp

I don’t know C++ but it looks fairly comprehensible ?

That code looks suspicious to me. I could imagine how it might produce different results when the normal of a face changes under twist or tapering operations. You should ask someone at LL to look at it.

> Now, all primitives in the Second Life system are essentially the same. They’re all “topologically equivalent” to a cylinder or sphere.

do you mean “torus”?

Yes, qarl, even the torus. In pure terms, a torus has a hole and therefore is not topologically equivalent.

But in SL and any polygonally-rendered computer graphics, any ring of polygons needs an extra set of vertices at the seam to avoid texture map problems. So you could say the torus ring in SL is not truly closed, and therefore just a cylinder bent into a circle.

Primitives with holes in them also violate the topological equivalence rule, strictly speaking. But in practice, you can really think of the hole as a negative space prim inside a simple genus zero prim and not worry about it.

It’s nice IMO when you can take hard math problems and say you don’t have to worry about them. Makes things nice and fast.

Pingback: Materials Coming Soon - Page 11 - SLUniverse Forums