# How to subdivide an octahedron into a sphere?

For a game I'm making, I have to tessellate an octahedron into a sphere on the GPU (shaders). What I've done is I've successfully tessellated the faces, but I'm having trouble subdividing more spaces, or in better terms, create more faces on the shape. I'm using tessellation shaders to help with this. I would use geometry shaders, but from what I learned, I shouldn't because it makes the program performance worse, and it isn't worth using because tessellation shaders can already created new geometry like geometry shaders. TES (Tessellation Evaluation Shader)

#version 450 core

layout(triangles, equal_spacing, ccw) in;

in vec3 vertex_coord[];
// output vec
out vec3 vert;

// allows for object transformations and for movement
uniform mat4 model;
uniform mat4 view;
uniform mat4 projection;

void main()
{
// patch coords
float u = gl_TessCoord.x;
float v = gl_TessCoord.y;
float w = gl_TessCoord.z;

// retrieve control point vertex coordinates
vec3 t00 = vertex_coord;
vec3 t01 = vertex_coord;
vec3 t10 = vertex_coord;

// bi-linearly interpolate vertex coordinate across patch
vec3 t0 = (t01 - t00) * w + t00;
vec3 t1 = (t00 - t10) * v + t01;
vec3 t2 = (t10 - t01) * u + t10;
vec3 vert = (t1 - t0 - t2) * v + t0;

// retrieve control point position coordinates
vec4 p00 = gl_in.gl_Position;
vec4 p01 = gl_in.gl_Position;
vec4 p10 = gl_in.gl_Position;

// compute patch surface normal
vec4 u_vec = p01 - p00;
vec4 v_vec = p10 - p00;
vec4 w_vec = p10 - p01;
vec4 normal = normalize( vec4(cross(u_vec.xyz, v_vec.xyz), 0) );

// bi-linearly interpolate position coordinate across patch
vec4 p0 = (p01 - p00) * u + p00;
vec4 p1 = (p00 - p10) * v + p10;
vec4 p2 = (p01 - p00) * w + p01;
vec4 p = (p1 - p0)  * w + p0;

// displace point along normal
//p += normal;

// output patch point position in clip space
gl_Position = projection * view * model * p;
}


For a reference, this is the type of subdivision I'm trying to go for, except it's not conducted on the CPU, it's on the GPU, for better performance, and because it seems to be easier to do than on the CPU. After modifying the tessellation variables above, I came a little bit closer to what I was going for but still not quite (captured in wireframe mode) As per @user253751's suggestion, I normalized the vertex coordinates and it didn't work as well as before. A birds eye view of the result: Here are the original vertices that created the octahedron in case that might help someone better understand the problem.

float vertices[] = {
//top-north-east
0.0,  1.0,  0.0,
0.0,  0.0,  1.0,
1.0,  0.0,  0.0,

//top-north-west
0.0,  1.0,  0.0,
-1.0,  0.0,  0.0,
0.0,  0.0,  1.0,

//top-south-west
0.0,  1.0,  0.0,
0.0,  0.0, -1.0,
-1.0,  0.0,  0.0,

//top-south-east
0.0,  1.0,  0.0,
1.0,  0.0,  0.0,
0.0,  0.0, -1.0,

//bottom-north-east
0.0, -1.0,  0.0,
1.0,  0.0,  0.0,
0.0,  0.0,  1.0,

//bottom-north-west
0.0, -1.0,  0.0,
0.0,  0.0,  1.0,
-1.0,  0.0,  0.0,

//bottom-south-west
0.0, -1.0,  0.0,
-1.0,  0.0,  0.0,
0.0,  0.0, -1.0,

//bottom-south-east
0.0, -1.0,  0.0,
0.0,  0.0, -1.0,
1.0,  0.0,  0.0,
};


I also found these Wikipedia articles and a youtube video to help visualize my desired outcome for the program.

https://en.wikipedia.org/wiki/Geodesic_polyhedron

https://en.wikipedia.org/wiki/N-sphere#Octahedral_sphere

• Fundamanetally, it looks like your vertices as being moved to incorrect locations. That's an awful lot of code to debug by eye (we've all had to go hunting for a swapped +/- or whatever it may be, they're easy to miss at a glance), so I'd suggest narrowing the scope a little. Personally, I'd start by trying to hard code some values in the shader (say p in the evaluation shader), observe how that varies the result and work backwards from there to track down which input/calculation isn't working as expected. Mar 1 at 22:14
• It might also be easier to see what's going on if you reduce this to a minimal test case with just one patch. Mar 2 at 16:38
• You might find renderdoc.org useful to help you understand what's going on.
Mar 3 at 17:23
• You seem to be making a lot of edits that don't materially improve the question or make it any easier to answer. Consider following the advice above and reducing this to a smaller test case that's easier for a reader to read, reproduce, and reason about - like a single triangle. Once you get answers that successfully fix a single triangle, you can apply those fixes to the whole octahedron/sphere. Mar 8 at 15:58
• Your math seems pretty complex - what's wrong with just taking the interpolated vertex coordinate and then normalizing it (i.e. dividing by its length)? not a good enough subdivision? Mar 10 at 20:50

After over a week of work, I have finally (partially) solved the problem. I was doing too much in the TE shader, so, using a tutorial I have linked right here https://prideout.net/blog/old/blog/index.html@p=48.html I normalized variables in certain ways (I think it's spherical coordinates but I'm not sure) and that resulted in me solving the problem

Here's the new TES that works

#version 450 core

layout(triangles, equal_spacing, cw) in;

in vec3 vertex_coord[];
// output vec
out vec3 vert;

// allows for object transformations and for movement
uniform mat4 model;
uniform mat4 view;
uniform mat4 projection;

void main()
{
// make it into a sphere
vec3 u = gl_TessCoord.x * vertex_coord;
vec3 v = gl_TessCoord.y * vertex_coord;
vec3 w = gl_TessCoord.z * vertex_coord;
vec3 pos = normalize(u + v + w);

// output patch point position in clip space
gl_Position = projection * view * model * vec4(pos, 1.0);
}


To any future viewers who are trying this as well, here are the main parts of the program

TCS

#version 450 core

// specify control points per output per patch
// control size of input and output arrays
layout(vertices=3) out;
in vec3 vert_coord[];
out vec3 vertex_coord[];

// for tessellation
uniform mat4 view;
uniform mat4 model;

void main()
{
// pass attributes through
gl_out[gl_InvocationID].gl_Position = gl_in[gl_InvocationID].gl_Position;
vertex_coord[gl_InvocationID] = vert_coord[gl_InvocationID];

// control tessellation
if(gl_InvocationID==0)
{
/* dynamic tessellation */
// first: define rendering constants to control tessellation
const float MIN_TESS_LEVEL = 4;
const float MAX_TESS_LEVEL = 64;
const float MIN_DISTANCE = 20;
const float MAX_DISTANCE = 800;
// second: transform each vertex into each eye
vec4 eye_space_pos_1 = view * model * gl_in.gl_Position;
vec4 eye_space_pos_2 = view * model * gl_in.gl_Position;
vec4 eye_space_pos_3 = view * model * gl_in.gl_Position;
// third: distance from camera scaled between 0 and 1
float distance_1 = clamp((abs(eye_space_pos_1.z)-MIN_DISTANCE)/(MAX_DISTANCE-MIN_DISTANCE), 0.0, 1.0);
float distance_2 = clamp((abs(eye_space_pos_2.z)-MIN_DISTANCE)/(MAX_DISTANCE-MIN_DISTANCE), 0.0, 1.0);
float distance_3 = clamp((abs(eye_space_pos_3.z)-MIN_DISTANCE)/(MAX_DISTANCE-MIN_DISTANCE), 0.0, 1.0);
// fourth: interpolate edge tessellation level based on closer vertex
float tess_level_1 = mix(MAX_TESS_LEVEL, MIN_TESS_LEVEL, min(distance_3, distance_1));
float tess_level_2 = mix(MAX_TESS_LEVEL, MIN_TESS_LEVEL, min(distance_1, distance_2));
float tess_level_3 = mix(MAX_TESS_LEVEL, MIN_TESS_LEVEL, min(distance_2, distance_1));
// fifth: set the corresponding outer tessellation levels
gl_TessLevelOuter = tess_level_1;
gl_TessLevelOuter = tess_level_2;
gl_TessLevelOuter = tess_level_3;
// sixth: set the inner tessellation levels
gl_TessLevelInner = max(tess_level_2, tess_level_1);
gl_TessLevelInner = max(tess_level_1, tess_level_3);
}
}


Octahedron verticies and indices

     unsigned int draw_calls = 3;
float vertices[] = {
//top-north-east
0.0,  1.0,  0.0,
0.0,  0.0,  1.0,
1.0,  0.0,  0.0,

//top-north-west
0.0,  1.0,  0.0,
-1.0,  0.0,  0.0,
0.0,  0.0,  1.0,

//top-south-west
0.0,  1.0,  0.0,
0.0,  0.0, -1.0,
-1.0,  0.0,  0.0,

//top-south-east
0.0,  1.0,  0.0,
1.0,  0.0,  0.0,
0.0,  0.0, -1.0,

//bottom-north-east
0.0, -1.0,  0.0,
1.0,  0.0,  0.0,
0.0,  0.0,  1.0,

//bottom-north-west
0.0, -1.0,  0.0,
0.0,  0.0,  1.0,
-1.0,  0.0,  0.0,

//bottom-south-west
0.0, -1.0,  0.0,
-1.0,  0.0,  0.0,
0.0,  0.0, -1.0,

//bottom-south-east
0.0, -1.0,  0.0,
0.0,  0.0, -1.0,
1.0,  0.0,  0.0,
};

unsigned int indices[] = {
// first triangle
0, 1, 2,
// second triangle
3, 4, 5,
// third triangle
6, 7, 8,
// fourth triangle
9, 10, 11,
// fifth triangle
12, 13, 14,
// sixth triangle
15, 16, 17,
// seventh triangle
18, 19, 20,
// eighth triangle
21, 22, 23
};


Tessellation specifications and draw call

#define NUM_PATCH_PTS 3
unsigned int draw_calls = 3;
// max tessellation points / patches
glPatchParameteri(GL_PATCH_VERTICES, NUM_PATCH_PTS);
glBindVertexArray(vao);
glDrawArrays(GL_PATCHES, 0, draw_calls*draw_calls*NUM_PATCH_PTS);


This is what it looks like now As you can see, around 80% of the sphere is rendered, so it's not perfect, but I'm working on it and when I fix this, I will update this answer, this might take a while...

EDIT: Ok, so 2 months later but I finally fixed the sphere problem. After I went to another forum over the weekend and posted my problem, I got help. It turns out that the coordinates were wrong. The problematic ones were top-north-east and bottom-south-east. Here are the new and improved coordinates as well as proof that it really works.

    float vertices[] = {
//top-north-east
0.0f, 1.0f,  0.0f,
0.0f,  0.0f,  1.0f,
1.0f,  0.0f,  0.0f,

//top-north-west
0.0f,  1.0f,  0.0f,
-1.0f,  0.0f,  0.0f,
0.0f,  0.0f,  1.0f,

//top-south-west
0.0f,  1.0f,  0.0f,
0.0f,  0.0f, -1.0f,
-1.0f,  0.0f,  0.0f,

//top-south-east
0.0f, -1.0f,  0.0f,
1.0f,  0.0f,  0.0f,
0.0f,  0.0f, -1.0f,

//bottom-north-east
0.0f, -1.0f,  0.0f,
1.0f,  0.0f,  0.0f,
0.0f,  0.0f,  1.0f,

//bottom-north-west
0.0f, -1.0f,  0.0f,
0.0f,  0.0f,  1.0f,
-1.0f,  0.0f,  0.0f,

//bottom-south-west
0.0f, -1.0f,  0.0f,
-1.0f,  0.0f,  0.0f,
0.0f,  0.0f, -1.0f,

//bottom-south-east
0.0f, 1.0f,  0.0f,
0.0f,  0.0f, -1.0f,
1.0f,  0.0f,  0.0f
}; Took two months but I told everyone I would be back to solve the problem!