The setup: I'm using a cubemap projection to create a planet out of blocks. A cubemap projection is quite simple: take the vector from the center of a cube to any point on that cube, normalize it, then multiply that by the radius of a sphere and you have your coordinate's new position. Here's a quick illustration in 2D:
Now, as I said, I've created this so that it's made of blocks. So in practice, I divide my cube into equal square subdivisions (like a rubik's cube). I use a custom coordinate: (Face, X, Y, Shell). Face refers to which face on the cube the point is on. X and Y refer to its position on the face. Shell refers to its 'height'. In practice this translates into the radius of the sphere I project the point onto. If I haven't explained it well, hopefully an image will help:
--That's a planet generated with an entirely random heightmap, with backface culling turned off. Anyways, now that you have the idea of what I'm working with--
My problem is that I cannot get backface culling to work predictably. My current system works as follows:
- Calculate the center of the block
- Get the normal of the vertices on each triangle of the block by taking the cross product of two sides of the triangle
- Get the vector from the center of the triangle (the average of the triangle's vertices) to the center of the block, normalize it.
- Take the dot product of the normal of the triangle and the normal to the center of the block
- If the dot product is >= 0, flip the first and last indices of the triangle
Here's that in code:
public bool CheckIndices(Quad q, Vector3 centerOfBlock)
{
Vector3[] vertices = new Vector3[3];
for (int v = 0; v < 3; v++)
vertices[v] = q.Corners[indices[v]].Position;
Vector3 center = (vertices[0] + vertices[1] + vertices[2]) / 3f;
Vector3 normal = Vector3.Cross(vertices[1] - vertices[0], vertices[2] - vertices[0]);
Vector3 position = center - centerOfBlock;
position.Normalize();
normal.Normalize();
float dotProduct = Vector3.Dot(position, normal);
if (dotProduct >= 0)
{
int swap = indices[0];
indices[0] = indices[2];
indices[2] = swap;
return false;
}
return true;
}
I use a Quad class to hold triangles and some other data. Triangles store an int[3] for indices which correspond to the vertices stored in Quad.
However, when I use this method, at least half of the faces are drawn in the wrong direction. I have noticed two patterns in the problem:
- Faces which point outward from the center of the planet are always correct
- Faces which point inward toward the center of the planet are always incorrect
This led me to believe that my calculated center of the block was incorrect and in fact somewhere between the block and the center of the planet. However, changing my calculations for the center of the block was ineffective.
I have used two different methods to calculate the center of the block. The first was to find the projected position of a coordinate which had +.5 X, +.5 Y, and +.5 Shell (Z) from the block's position. Because I define block position using the bottom-left-back corner, this new coordinate would naturally be in the center of the block. The other method I use is to calculate the real position of each corner of the block and then average these vectors. This method seemed pretty foolproof to me, yet it did not succeed.
For this reason I am beginning to doubt the code I pasted above which determines if a triangle must be flipped. I do not remember all of the reasoning behind some of the logic, specifically behind the >= 0 statement. I just need another pair of eyes: is something wrong here?
dot(normal, normal) >= 0is the right approach. Think about this: sideways polys' normals will be perpendicular to that line, and floating point math is lossy (rounding errors), so you'll get random results depending on exactly how much rounding error you have, and where. Maybe there is a way to build your data so you don't have to swap it to begin with? Like, figure out the correct policy for the way it should face when building each poly. Can you share some of that code/pseudocode? - Merlyn Morgan-Graham