Отверстие в многоугольнике

Мне нужно создать трехмерную модель куба с круглым отверстием, пробитым в центре одной грани, полностью проходящим через куб на противоположную сторону. Я могу генерировать вершины для граней и отверстий.

Четыре грани (нетронутые отверстием) можно смоделировать как одну треугольную полосу. Внутренняя часть отверстия также может быть смоделирована как одна треугольная полоса.

Как мне сгенерировать индексный буфер для граней с отверстиями? Есть ли стандартный алгоритм (ы) для этого?

Я использую Direct3D, но идеи из других стран приветствуются.

12.12.2008 05:25:56
6 ОТВЕТОВ
РЕШЕНИЕ

Вы хотите посмотреть Тесселяцию, которая является областью математики, которая имеет дело с тем, что показывает MizardX. Сферы в 3D-графиках должны иметь дело с этим все время, и есть множество алгоритмов тесселяции, чтобы принять лицо с дырой и вычислить треугольники должны были сделать это.

4
12.12.2008 16:51:38

Современное оборудование обычно не может правильно отображать вогнутые полигоны.
В частности, обычно даже нет способа определить многоугольник с отверстием.
Вам нужно как-то найти триангуляцию плоскости вокруг отверстия. Наилучшим способом, вероятно, является создание треугольников от вершины отверстия до ближайших вершин прямоугольной грани. Это, вероятно, создаст несколько очень тонких треугольников. если это не проблема, то все готово. если это так, то вам понадобится алгоритм обтекания / оптимизации сетки для создания красивых треугольников.

3
12.12.2008 05:34:09

Альфа-смешение не может быть и речи? Если нет, просто текстурируйте стороны с отверстиями, используя текстуру с прозрачностью в середине. Вы должны сделать больше рендеринга полигонов, так как вы не можете использовать преимущества рисования спереди назад и игнорирования закрытых граней, но это может быть быстрее, чем иметь много маленьких треугольников.

3
12.12.2008 05:44:22
Отличная идея! Но в моем случае все немного сложнее, и мне придется использовать меш.
Agnel Kurian 12.12.2008 06:01:58

Чтобы создать индексный буфер, который вы хотите, вы можете сделать это следующим образом. Мышление в 2D с рассматриваемой гранью в виде квадрата с вершинами (± 1, ± 1) и дыркой в ​​виде круга в середине.

  1. Вы идете по краю круга, разделяя его на несколько отрезков.
  2. Для каждой вершины вы проецируете ее на окружающий квадрат (x/M,y/M), где Mесть max(abs(x),abs(y)). Mявляется абсолютной величиной самой большой координаты, поэтому она масштабируется (x,y)так, чтобы самая большая координата была ± 1.
  3. Эту линию вы также поделите на некоторое количество сегментов.
  4. Сегменты двух последующих линий соединяются попарно как грани.

Это пример, подразделяющий круг на 64 сегмента, а каждый луч на 8 сегментов. Вы можете выбрать номера в соответствии с вашими требованиями.

альтернативный текст http://pici.se/pictures/AVhcssRRz.gif

Вот некоторый код Python, который демонстрирует это:

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()
6
20.12.2008 00:03:14
MizardX, я не совсем понял: «2. Для каждой вершины вы проецируете ее на окружающий квадрат с помощью (x / M, y / M), где M - max (abs (x), abs (y))». А как вы сгенерировали изображение?
Agnel Kurian 18.12.2008 09:11:35

Я представляю 4 треугольных веера, идущих с 4 углов площади.

2
12.12.2008 17:15:34

Просто мысль -

Если вы любите обманывать (как это часто делалось в играх), вы всегда можете построить обычный куб, но иметь текстуру для двух граней, которые вам нужны, с отверстием (альфа = 0), затем вы можете либо обрезать его в шейдере. или смешайте его (в этом случае вам нужно выполнить рендеринг с помощью Z sort). Вы получите внутреннее отверстие, построив внутренний цилиндр, обращенный внутрь и без крышек.

Конечно, это будет работать, только если геометрия не важна для вас.

1
15.02.2009 07:14:58