Hole in a Polygon

Question

I need to create a 3D model of a cube with a circular hole punched at the center of one face passing completely through the cube to the opposite side. I am able to generate the vertices for the faces and for the holes.

Four of the faces (untouched by the hole) can be modeled as a single triangle strip. The inside of the hole can also be modeled as a single triangle strip.

How do I generate the index buffer for the faces with the holes? Is there a standard algorithm(s) to do this?

I am using Direct3D but ideas from elsewhere are welcome.

Answer 1

To generate the index-buffer you want, you could do like this. Thinking in 2D with the face in question as a square with vertices (±1, ±1), and the hole as a circle in the middle.

1. You walk along the edge of the circle, dividing it into some number of segments.
2. For each vertex, you project it onto the surrounding square with (x/M,y/M), where M is max(abs(x),abs(y)). M is the absolute value of the biggest coordinate, so this will scale (x,y) so that the biggest coordinate is ±1.
3. This line you also divide into some number of segments.
4. The segments of two succeeding lines you join pairwise as faces.

This is an example, subdividing the circle into 64 segments, and each ray into 8 segments. You can choose the numbers to match your requirements.

alt text http://pici.se/pictures/AVhcssRRz.gif

Here is some Python code that demonstrates this:

from math import sin, cos, pi
from itertools import izip

def pairs(iterable):
    """Yields the previous and the current item on each iteration.
    """
    last = None
    for item in iterable:
        if last is not None:
            yield last, item
        last = item

def circle(radius, subdiv):
    """Yields coordinates of a circle.
    """
    for angle in xrange(0,subdiv+1):
        x = radius * cos(angle * 2 * pi / subdiv)
        y = radius * sin(angle * 2 * pi / subdiv)
        yield x, y

def line(x0,y0,x1,y1,subdiv):
    """Yields coordinates of a line.
    """
    for t in xrange(subdiv+1):
        x = (subdiv - t)*x0 + t*x1
        y = (subdiv - t)*y0 + t*y1
        yield x/subdiv, y/subdiv

def tesselate_square_with_hole((x,y),(w,h), radius=0.5, subdiv_circle=64, subdiv_ray=8):
    """Yields quads of a tesselated square with a circluar hole.
    """
    for (x0,y0),(x1,y1) in pairs(circle(radius,subdiv_circle)):
        M0 = max(abs(x0),abs(y0))
        xM0, yM0 = x0/M0, y0/M0

        M1 = max(abs(x1),abs(y1))
        xM1, yM1 = x1/M1, y1/M1

        L1 = line(x0,y0,xM0,yM0,subdiv_ray)
        L2 = line(x1,y1,xM1,yM1,subdiv_ray)
        for ((xa,ya),(xb,yb)),((xc,yc),(xd,yd)) in pairs(izip(L1,L2)):
            yield ((x+xa*w/2,y+ya*h/2),
                   (x+xb*w/2,y+yb*h/2),
                   (x+xc*w/2,y+yc*h/2),
                   (x+xd*w/2,y+yd*h/2))


import pygame
def main():
    """Simple pygame program that displays the tesselated figure.
    """
    print('Calculating faces...')
    faces = list(tesselate_square_with_hole((150,150),(200,200),0.5,64,8))
    print('done')

    pygame.init()
    pygame.display.set_mode((300,300))
    surf = pygame.display.get_surface()
    running = True

    while running:
        need_repaint = False
        for event in pygame.event.get() or [pygame.event.wait()]:
            if event.type == pygame.QUIT:
                running = False
            elif event.type in (pygame.VIDEOEXPOSE, pygame.VIDEORESIZE):
                need_repaint = True
        if need_repaint:
            print('Repaint')
            surf.fill((255,255,255))
            for pa,pb,pc,pd in faces:
                # draw a single quad with corners (pa,pb,pd,pc)
                pygame.draw.aalines(surf,(0,0,0),True,(pa,pb,pd,pc),1)
            pygame.display.flip()

try:
    main()
finally:
    pygame.quit()