1

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.

genpfault
  • 51,148
  • 11
  • 85
  • 139
Brian Stinar
  • 1,080
  • 1
  • 14
  • 32
  • 2
    Do you actually need the mesh geometry stored, or is the visualization the only important aspect? –  Oct 19 '10 at 08:19
  • The visualization is the only important aspect. We are using other (more mathematically precise) definitions of our objects as inputs into our simulation - this is only used for visualization. We currently are putting translucent cylinders into our visualization to represent holes, which doesn't look that great. – Brian Stinar Oct 20 '10 at 15:23
  • Actually, we do need to handle the case where the user inputs STL (stereolithography, CAD) files so the solution needs to be able to handle these. – Brian Stinar Oct 22 '10 at 22:10

3 Answers3

2

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

example

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.

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380
2

Sounds like you want constructive solid geometry.

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

genpfault
  • 51,148
  • 11
  • 85
  • 139
  • Thanks for the suggestion. If OpenCSG will allow me to specify these sorts of primitives (sphere - cylinder), WITHOUT re-writing my entire OpenGL based geometry package, this will be very nice. Carve sounds interesting as well, I will be reading about these much more. – Brian Stinar Oct 18 '10 at 23:19
1

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.

Community
  • 1
  • 1
  • Thank you for the answer. We do not have to do this in real time - after the user adds a hole (subtracts?) it is all right to have a few seconds of post processing and re-rendering. I think I am beginning to understand the need for a more mathematically precise definition of my shapes in order to perform these arbitrary additions and subtractions. It seems like working entirely in vertices will not get me to where I want to go. – Brian Stinar Oct 20 '10 at 15:25
  • Furthermore, since you don't need the actual vertices computed, you can use the CSG equations from the paper in my post applied to raymarching. It's a viable solution with DirectX or OpenGL shaders. –  Oct 21 '10 at 07:30