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

Question

Hello,

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.

I have some experience with ray tracing, but none with this form of graphics development. I appreciate the feedback that stackoverflow has provided in the past. Thank you for your time and consideration with regard to my question.

-Brian J. Stinar-

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.

Answer 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:

http://stackoverflow.com/questions/2882008/csg-operations-on-implicit-surfaces-with-marching-cubes-solved

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.