Today in keeping with my series Game Programming is Hard, I’m going to share with you something different – the process itself. Also in keeping with the series – a major theme of which is that even platforms specifically designed to help more people create games require you to solve even basic problems that you shouldn’t need to solve – today I’m going to show you what happens when you try to do something simple, namely, texture map a sphere.
(I will talk about how to generate vertices for a sphere in a future post, by the way).
Texture mapping is a pretty simple concept. You have a 2D texture of arbitrary size and you want to put it on a 3D surface. By now you should already appreciate that even very curvy surfaces in 3D graphics are in fact comprised of nothing but flat surfaces, so it shouldn’t necessarily be rocket science to paste a flat texture on a flat surface. Also, I hope you realize by now that all surfaces are actually just triangles.
If everything in life were easy, we’d have such a thing as a triangular texture and each triangle in your 3D world would have a 2D triangular texture which is exactly the right size and it would be as simple as slapping them on piece by piece. Of course, that’s impossible for a variety of reasons. First, image files are rectangular, so automatically, there’s gonna be some kind of math involved to extract the triangle from the rectangle. Second, could you imagine the painstaking process that would be involved in creating 1 perfect texture for each triangle in your scene? Yeah, exactly – it would be an impossible undertaking. Not to mention the fact that your triangles are going to move and scale.
In the real world, texture files are squares, and when you define vertices which, in 3’s define triangles in your 3D world, you associate each vertex with what’s called a texture coordinate. That’s a location in the texture file. When you have 3 texture coordinates, one for each vertex, you’ve defined a triangle inside your texture. Imagine taking a pair of scissors and cutting that triangle out of your texture. Then you scale that triangle to fit the actual size of the 3D triangle, and then you plaster it on. Pretty simple, right?
In order for texture coordinates to work for varying size textures (e.g., 512×512, 2048×1024, etc), texture coordinates don’t specify pixels, they specify a scale value from 0 to 1. This value is multiplied by the width or height of the actual texture in use to get the actual pixel in the texture to use.
It all sounds pretty simple, right?
Sure! So, let’s say you have a sphere with somewhere around 3500 triangles. That would be a geodesic dome of frequency 3, which is also known as a subdivided icosahedron of frequency 3, meaning each surface of the icosahedron is recursively subdivided from 1 triangle into 4 other triangles (like a Triforce). This resolution is enough to make a pretty smooth looking sphere.
How do you wrap a square or rectangular texture on a sphere? How do you take the 11000 or so vertices and generate texture coordinates for each vertex such that the result is that the rectangular texture is drawn correctly on the sphere?
Well as it turns out we already do the reverse whenever we make a map. Think about how we define locations on planet earth. We use latitude and longitude right? That’s a 2-dimensional description of what is in reality a 3D point. The reason we don’t include the 3rd dimension is because it’s fixed – that dimension is, give or take sea-level, the radius of the earth.
A little bit of googling will give you the formulas you need to convert a 3D point that exists on the surface of a sphere into what amounts to latitude and longitude coordinates (often called polar coordinates because they are actually calculated based on angles). In fact, angles are what you’re going to get. You’ll get the angle in the horizontal (XZ) plane and the angle in the vertical (XY) plane, and those combined with a fixed radius define a sphere. It involes some arctangents and then a bit of scaling to convert radians into texture space (0 to 1, remember?).
But that’s not the problem you’re going to face. It’s pretty easy to compute the texture coordinates. What isn’t easy is fixing the result, which contains an ugly beast known colloquially as the “seam problem”:
What the hell is that, and why is it there?
That is the seam of the texture. But why does it exist?
That’s a good question. Before I started googling furiously, I thought about some facts about the seam. The fact that I used the earth as a texture helped me here because I can recognize the approximate longitude and latitutde of any given point on the sphere. This seam – the only seam – is appearing in the middle of the Pacific Ocean. What latitudinal or longitudinal feature exists there? The international dateline, also known as longitude zero.
Ah. A clue. The seam also coincidentally occurs where I would expect the texture to wrap around itself – where its horizontal edges would meet. In texture coordinate space, this means where 0 and 1f meet.
At this point I have a pretty good idea that this is a boundary case. But what could go wrong?
The distorted texture along the seam indicates to me that something is gong wrong with the texture being picked by triangles occuping by the seam. Since this is a boundary case scenario, the most obvious answer is that the triangles along the seam do not fit cleanly inside the texture. What if two of the vertices lie close to the edge of the texture and the other goes off of it? Since texture coordinates are constrained to be between 0 and 1, this would result in wrapping, and the texture mapper probably does not like it when vertices supplied in clockwise order do not represent a clockwise texture map result, which would be the case if a value that should be greater than 1.0 is wrapped around 1.0 to be less than the other vertices.
To test this hypothesis, I sought out to identify the triangles where this might be the case.
As with all geometry I create in XNA, I create basic primitive class that supplies the Vector3’s which identify the vertices. Then, for specific drawable components (like a textured sphere), I build an array of IVertexType based on those vectors. In this case, I have a method which takes an array of Vector3 which represent a triangle list of a geodesic sphere with frequency 3 and creates an instance of VertexPositionTexture for each Vector3. I calculate the texture components using the standard polar method. I process my vectors in groups of 3 so I can think of myself working with a triangle rather than an individual isolated point, because what I’m really looking for are triangles that cross the seam.
There wasn’t any guarantee starting off that any of my geodesic sphere’s many triangles would have vertices that correspond to an exact 1.0 texture coordinate, but I thought that would be a good place to start. I started by looking at the first vertex in each triangle and checking it’s horizontal texture coordinate to see if it was 1.0. This is actually sufficient because of another fact of XNA – namely, that polygons, at least when they are in lists rather than strips – always must be specified in clockwise order. What that means is that if the first vertex has a texture coordinate of 1.0, then the next one must have a texture coordinate higher. In reality, it will be lower because of wrapping – and that’s exactly the problem. So, I identified those triangles and simply chose not to draw them by eliminating them from the vertex buffer – by continuing in my loop before returning the vectors that comprise that triangle. (FYI, I am using the yield return mechanic in C#. I’m a huge fan).
Here’s the way the seam looks when I eliminate those triangles:
Ah. Good, I am eliminating triangles where this is the case.
The middle looks like a zipper, where alternating triangles are still showing. What must I know about these triangles?
First, I had to figure out which one of the vertices in the triangle was actually first. It was obviously one of the two vertices on the left (remember, my coordinate system is moving left to right here, also known as west to east). It could be the bottom vertex – moving clockwise we’d come to the top vertex and that has the same value – 1.0f. So I put a break point there and compared the Y values of the two points in question. I’m calling my triangle’s vertices A,B,C (clockwise in that order). Texture coordinates are usually called (U,V) to distinguish them from world coordinates (which are called X,Y,Z). So whichever of my two triangle verts – A or B – had a higher V value was the top vertex.
Except I was initially wrong here, and my debugging proved it. If A were the top vertex then moving clockwise we would expect B to have a different U value, but it didn’t. Why not? A has a higher Y value, but not a higher V value because texture coordinates start in the upper left corner of a texture, so while U increases left to right as we expect for normal cartesian coordinates, V decreases from bottom to top, starting at 1.0 and ending at 0.0. So, A is not the top vertex of each triangle but rather the bottom one after all. This is useful to know.
As I thought about it more I realized that knowing the vertex order of the triangles I was already culling from the seam wasn’t going to help me because I didn’t know what the order of the remaining triangles was. I just needed to do a little trial and error. So, I started checking vertex B’s texture coordinates for a value of 1.0f. This is the result of also culling these triangles:
More of the seam was now gone, but not all of it. So, I added checks for vertex C as well.
As it turned out, I had to do every combination of check to get the seam to be entirely culled. The check is simple. I just look for a texture coordinate at 1f and then look for another texture coordinate in the triangle that is close to 0 (depending on how resolute your sphere is, the actual value is going to be different. In my case, a number as small as 0.5f works to cull the triangles).
The result is this:
At this point I have successfully removed the distorted seam from my sphere; unfortunately, this now looks even worse than the distorted seam. It reminds me vaguely of the scene from The Langoliers when they start eating giant black holes through the terrain.
The reason that I removed these triangles wasn’t because I wanted to remove them but rather that I needed to identify the seam triangles that weren’t being rendered correctly and the easiest way in to do that in graphics programming is to cause them to change their appearance somehow on the screen so they stand out. Rendering them as black holes (by not rendering them all, as a matter of fact) is an easy way to do that.
Now that we’ve made some headway, how do I solve the problem?
Well, there are a few ways to do it. My initial thought was, okay, make sure that no triangles cross this boundary, but the problem with that is I have vertices that map, in UV coordinates, to 1.0f UF. This is in fact a good thing, because the only way to ensure that no triangles cross this boundary would be to have vertices land exactly on the border. The triangles on the left of the border will work nicely, but that same vertex is repeated in the triangles on the right of the border that connect to it, which is not a problem per se, except that you need to ensure that the vertex with a U value of 1.0f is the last vertex in order on those triangles.
Ultimately it seemed like it was way too much trouble, so I thought about alternatives. One of those is recognizing the fact that if the texture wants to wrap, why not just let it? If I have a texture coordinate of 1.0f U, why not just set it 0.0f U for the triangles where this is a problem? I will be off by at most 1 texture pixel (called a “texel” for those in the loop). I can live with that. So I tried it. I started with the first set of triangles I culled, where A and B both have a U coordinate of 1.0f and C has a coordinate very close to zero. I set A and B’s U to 0.0 and gave it a shot:
That looks pretty good, right? No weird seam – at least on the triangles that I’ve drawn so far.
Unfortunately, as I tried to continue with this strategy I was unable to eliminate all of the weirdness. I decided to switch to a different texture – a simple one with one half red, one half blue, so the seam would be more obvious. The Pacific Ocean leaves something to be desired.
Much to my horror, this is what I saw:
The fact that the edges of my missing triangles are not lining up with the color boundary is a problem.
I realized doing simple value checks wasn’t going to cut it. What I really needed to figure out was whether the triangle’s U were wrapping or not. So I got out a scratch pad – actually, the back of one of the sheets from my “Stupidest things ever said” desk calendar – and started drawing some points and edges.
I realized that what I was really looking for were texture mapped triangles that were not in clockwise order. This explains the seam perfectly. Not only is it guaranteed to happen at the seam, but it is very likely that the GPU chokes when it gets a bad texture triangle (e.g. not clockwise) in the same way that the GPU chokes when it gets a bad triangle (e.g., not clockwise, and well, not choke, but rather, cull).
I had to do a little bit of Google sleuthing and write a function that returns something called the “signed area of a simple polygon.” Triangles are the simplest possible polygons. I implemented a signed area function, which is basically the sum of 2D cross products, and then ran it against my texture triangles. If a texture triangle’s signed area came up negative, it means it’s counter clockwise. This means it crosses the texture boundary. When I cull those triangles, this is what I see:
At this point, it’s important to realize why this isn’t working like it’s supposed to. Obviously textures can wrap in 3D rendering systems; it happens all the time. Why aren’t these textures wrapping properly?!
The reason is that if you want texture wrapping to work, you still need to specify clockwise texture triangles. Why aren’t these triangles clockwise? It’s not the “texture” boundary it’s crossing. Remember that we are calculating each vertex as a polar coordinate, and the polar coordinates are not wrapping, and they shouldn’t.
So the situation comes down to this: when a texture triangle ends up counterclockwise, we have to add 1.0f to the offending vertex and enable wrapping. That should do it.
There’s only one catch. Texture wrapping doesn’t work in DX10 and therefore it doesn’t work in XNA. Specifically, specifying a value of more than 1.0 for a texture coordinate will not wrap as you expect, and it isn’t as simple as just doing the wrapping yourself because you end up in the original situation – a counterclockwise texture triangle. The recommended solution to this problem for DX10 is to create a vertex where the texture coordinate would be 1.0 and create multiple faces so that you can texture them properly without wrapping.
The only problem with that is a) it’s hard and b) the result is no longer a regular geodesic dome – the vertices are not uniform across the face because you have to subdivide any triangle that crosses the seam in a bizarre way. Imagine a triangle being bisected so that the result is a triangle – the tip – and a trapezoid – the base. And then the trapezoid needs to be turned into three triangles itself, because a trapezoid is not a triangle.
At this point, I did what you sometimes have to do in this business: I gave up.
My objective was to add a textured sphere primitive into my XNA toolbox and since I had already created a geodesic dome I figured I’d just texture map it and be done.
There’s a significantly easier way to create a texture mapped sphere, and that is to start with the texture coordinates themselves. The process goes like this:
Decide how many meridians you want. (Call it longitude step). Decide how many tropics you want (call it latitude step). Iterate latitude from 0 to 1.0 inclusive, increasing by latitude step. For each latitude, iterate longitude from 0 to 1.0f inclusive. For each combination of latitude/longitude, you have a texture coordinate – your x value is your longitude and your y value is your latitude. To turn that into 3D points, you just need to use some simple trigonometry: you scale your longitude from 0-1f to 0-2pi radians, you scale your latitude from 0-1f to 0-pi radians, you take some sins and consines, and mulitply those by the radius of your sphere (which should be 1.0 because all primtiives should be unit primtives centered around 0,0,0). After that you just need to do a little creative looping to create triangle strips (or lists, which are far, far easier) out of these points and you’re done.
I was familiar with this technique from previous 3D graphics work so it was just a matter of implementing it. It took me about 3 hours under heavy distraction from the wife, the baby, and the TV to get right.
The lesson today is that sometimes you have to go back to the drawing board, and that’s okay. But it illustrates one of the reasons why game programming is hard. I just assumed that texture coordinates wrapped the way they had in previous DX editions so I spent a long time going down a rabbit hole that a more experienced game developer has already gone down and knows not to go down again. If you’re starting to play with 3D graphics, XNA, DX, OpenGL, whatever – expect to waste a lot – and I mean a lot of time – learning things the hard way. It’s going to happen.
Just remember, there’s always a way out of the rabbit hole, and often times it’s back the way you came.