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

Question

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.

Answer 1

Sounds like you want constructive solid geometry.

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