I have an OpenGL Tessellated Sphere and I want to cut a cylindrical hole in it

I am working on a piece of software which generated a polygon mesh to represent a sphere, and I want to cut a hole through the sphere. This polygon mesh is only an overlay across the surface of the sphere. I have a good idea of how to determine which polygons will intersect my hole, and I can remove them from my collection, but after that point I am getting a little confused. I was wondering if anyone could help me with the high-level concepts?

Basically, I envision three situations:

1.) The cylindrical hole does not intersect my sphere.
2.) The cylindrical hole partially goes through my sphere.
3.) The cylindrical hole goes all the way through my sphere. 

For #1, I can test for this (no polygons removed) and act accordingly (do nothing). For #2 and #3, I am not sure how to re-tessellate my sphere to account for the hole. For #3, I have somewhat of an idea that is basically along the following lines:

a.) Find your entry point (a circle)
b.) Find your exit point (a circle) 
c.) Remove the necessary polygons
d.) Make new polygons along the 4* 'sides' of the hole to keep my 
    sphere a manifold. 

This extremely simplified algorithm has some 'holes' I would like to fill in. For example, I don't actually want to have 4 sides to my hole - it should be a cylinder, or at lease a tessellated representation of a cylinder. I'm also not sure how to make these new polygons to keep my sphere with a hole in a tessellated surface.

I have no idea how to approach scenario #2.

Solution 1:

Sounds like you want constructive solid geometry.

Carve might do what you want. If you just want run-time rendering OpenCSG will work.

Solution 2:

I implemented CSG operations using scalar fields earlier this year. It works well if performance isn't important. That is, the calculations aren't real time. The problem is that the derivative isn't defined everywhere, so you can forget about computing cheap vertex-normals that way. It has to be done as a post-step. See here for the paper I used (in the first answer), and some screenshots I made:

CSG operations on implicit surfaces with marching cubes

Also, CSG this way requires the initial mesh to be represented using implicit surfaces. While any geometric mesh can be split into planes, it wouldn't give good results. So spheres would have to be represented by a radius and an origin, and cylinders would be represented by a radius, origin and base height.

Solution 3:

Well if you want just to render this (visualize) then may be you do not need to change the generated meshes at all. Instead use Stencil buffer to render your sphere with the holes. For example I am rendering disc (thin cylinder) with circular holes near its outer edge (as a base plate for machinery) with combination of solid and transparent objects around so I need the holes are really holes. As I was lazy to triangulate the shape as is generated at runtime I chose stencil for this.

1. Create OpenGL context with Stencil buffer

   I am using 8 bit for stencil but this technique uses just single bit.

2. Clear stencil with 0 and turn off Depth&Color masks

   This has to be done before rendering your mesh with stencil. So if you have more objects rendered in this way you need to do this before each one of them.

3. Set stencil with 1 for solid mesh

4. Clear stencil with 0 for hole meshes

5. Turn on Depth&Color masks and render solid mesh where stencil is 1

In code it looks like this:

// [stencil]
glEnable(GL_STENCIL_TEST);
// whole stencil=0
glClearStencil(0);
glClear(GL_STENCIL_BUFFER_BIT);
// turn off color,depth
glStencilMask(0xFF);
glColorMask(GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE);
glDepthMask(GL_FALSE);
// stencil=1 for solid mesh
glStencilFunc(GL_ALWAYS,1,0xFF);
glStencilOp(GL_KEEP, GL_KEEP, GL_REPLACE);
glCylinderxz(0.0,y,0.0,r,qh);
// stencil=0 for hole meshes
glStencilFunc(GL_ALWAYS,0,0xFF);
glStencilOp(GL_KEEP, GL_KEEP, GL_REPLACE);
for(b=0.0,j=0;j<12;j++,b+=db)
    {
    x=dev_R*cos(b);
    z=dev_R*sin(b);
    glCylinderxz(x,y-0.1,z,dev_r,qh+0.2);
    }
// turn on color,depth
glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE);
glDepthMask(GL_TRUE);
// render solid mesh the holes will be created by the stencil test
glStencilFunc(GL_NOTEQUAL,0,0xFF);
glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
glColor3f(0.1,0.3,0.4);
glCylinderxz(0.0,y,0.0,r,qh);
glDisable(GL_STENCIL_TEST);

where glCylinderxz(x,y,z,r,h) is just function that render cylinder at (x,y,z) with radius r with y-axis as its rotation axis. The db is angle step (2*Pi/12). Radiuses are r-big, dev_r-hole radius, dev_R-hole centers And qhis the thickness of the plate.

The result looks like this (each of the 2 plates is rendered with this):

This approach is more suited for thin objects. If your cuts leads to thick enough sides then you need to add a cut side rendering otherwise the lighting could be wrong on these parts.