Bezier recorte

Question

Eu estou tentando encontrar / fazer um algoritmo para calcular a interseção (um novo objeto cheia) de dois arbitrária cheio 2D objetos. Os objectos são definidas utilizando linhas ou beziers cúbicos e podem ter furos ou auto-se intersectam. Eu estou ciente de vários algoritmos existentes fazendo o mesmo com polígonos, aqui . No entanto, eu gostaria de apoiar beziers sem subdividindo-os em polígonos, ea saída deve ter aproximadamente os mesmos pontos de controle como a entrada em áreas onde não existem cruzamentos.

Isto é para um programa interativo para fazer alguma CSG, mas o recorte não precisa ser em tempo real. Eu procurei por um tempo, mas não encontraram bons pontos de partida.

Answer 1

Eu encontrei o seguinte publicação para ser o melhor de informações sobre Bezier Clipping:

T. W. Sederberg, BYU, Computer Aided Design geométrico notas do curso

Capítulo 7, que fala sobre curva de intersecção está disponível online. Ele descreve 4 abordagens diferentes para encontrar interseções e descreve Bezier Clipping em detalhes:

http://www.tsplines.com/technology/edu/CurveIntersection.pdf

Answer 2

Eu sei que estou em risco de ser redundante, mas eu estava investigando o mesmo problema e encontrou uma solução que eu tinha lido em trabalhos acadêmicos, mas não tinha encontrado uma solução trabalhando.

Você pode reescrever as curvas bezier como um conjunto de duas equações cúbicas bi-variada como esta:

• ? X = ax1 * T-, ^ 3 + bx1 * T-, ^ 2 + cx1 * T ^ + dx1 - ax2 * t2 ^ 3 - bx2 * t2 ^ 2 - * cx2 t2 - dx2
• Ay = ay1 * T-, ^ 3 + by1 * T-, ^ 2 + cy1 * T ^ + dy1 - ay2 * t2 ^ 3 - by2 * t2 ^ 2 - * cy2 t2 - dy2

Obviamente, as curvas se cruzam para valores de (T ^, t2) onde Ax = Ay = 0. Infelizmente, é complicado pelo fato de que é difícil encontrar raízes em duas dimensões e abordagens aproximados tendem a (como outro escritor colocá-lo) explodir.

Mas se você estiver usando números inteiros ou números racionais para seus pontos de controle, então você pode usar bases de Groebner para reescrever seus bi-variada ordem de 3 polinômios em um (possivelmente-up-to- fim-9-assim-seu-nove possíveis-cruzamentos) monovariate polinomial. Depois disso, você só precisa encontrar suas raízes (para, digamos t2) em uma dimensão, e conecte seus resultados de volta em uma de suas equações originais para encontrar a outra dimensão.

Burchburger tem uma introdução amigável-leigo a bases de Groebner chamados " Bases de Gröbner: Uma Breve Introdução Para sistemas teóricos " Isso foi muito útil para mim. Google. O outro papel que foi útil foi um chamado " Rápido, achatamento preciso do caminho Bézier cúbica e curvas de deslocamento " pelo TF Hain, que tem muitas equações de utilidade para curvas bezier, incluindo como encontrar os coeficientes do polinômio para as equações x e y.

Quanto a saber se o recorte Bezier vai ajudar com este método particular, eu duvido, mas bezier recorte é um método para estreitar onde interseções pode ser, não para encontrar uma resposta final (embora possivelmente aproximado) de onde ele está. Um monte de tempo com este método será gasto em encontrar a equação mono-variada, e que a tarefa não pode ficar mais fácil com o grampeamento. Encontrar as raízes é por comparação trivial.

No entanto, uma das vantagens deste método é que ele não depende de forma recursiva subdividindo a curva, eo problema se torna um problema de apuramento de raiz unidimensional simples, que não é fácil, mas bem documentado. A principal desvantagem é que a computação em bases de Groebner é caro e torna-se muito complicado se você está lidando com flutuação de polinômios ponto ou usando ordem superior curvas de Bezier.

Se você quiser algum código acabado em Haskell para encontrar as interseções, deixe-me saber.

Answer 3

Eu escrevi código para fazer isso há muito, muito tempo atrás. O projeto que eu estava trabalhando em 2D definido objetos usando limites por partes Bezier que foram gerados como caminhos PostScipt.

A abordagem que eu usei foi:

Let curvas p, q, ser definido por pontos de controle de Bezier. Será que eles se cruzam?

Calcule a caixas delimitadoras dos pontos de controle. Se eles não se sobrepõem, então as duas curvas não se cruzam. Caso contrário:
p.x (t), p.y (t), q.x (u), q.y (u) são polinómios cúbicos em 0 <= t, u <= 1.0. A distância ao quadrado (p.x - q.x) ** 2 + (p.y - q.y) ** 2 é um polinômio em (t, u). Use Newton-Raphson para tentar resolver isso para zero. Descartar todas as soluções fora 0 <= t, u <= 1.0

N-R pode ou não pode convergir. As curvas não pode se intersectam, ou N-R pode apenas explodir quando as duas curvas são quase paralelos. Então cortou N-R se ele não está convergindo depois depois de algum número arbitrário de iterações. Este pode ser um número relativamente pequeno.

Se N-R não convergem para uma solução, dividir uma curva (por exemplo, p) em duas curvas PA, PB em t = 0,5. Isso é fácil, é só computação pontos médios, como mostra o artigo ligado. Então teste recursivamente (q, aa) e (q, PB) para intersecções. (Note-se que na camada seguinte de recursividade que q tornou-se p, de modo que p e q são dividida alternadamente em cada uma das pregas do recursão.)

A maioria das chamadas recursiva retornar rapidamente porque as caixas delimitadoras são não-sobreposição.

Você terá de cortar a recursividade em algum profundidade arbitrária, para lidar com casos estranhos, onde as duas curvas são paralelas e não chegam a tocar, mas a distância entre eles é arbitrariamente pequeno - talvez apenas 1 ULP de diferença.

Quando você encontrar uma interseção, você não está feito, porque curvas cúbicos pode ter vários cruzamentos. Então você tem que dividir cada curva no ponto de interseção, e de forma recursiva verificar se há mais interections entre (pa, qa), (pa, qb), (pb, QA), (pb, qb).

Answer 4

Há uma série de trabalhos de pesquisa acadêmica em fazer bezier recorte:

http://www.andrew.cmu.edu/user /sowen/abstracts/Se306.html

http://citeseerx.ist.psu.edu /viewdoc/summary?doi=10.1.1.61.6669

http://www.dm.unibo.it/~casciola /html/research_rr.html

Eu recomendo os métodos de intervalo, porque como você descreve, você não tem que dividir para baixo para polígonos, e você pode obter resultados garantidos, bem como definir a sua própria precisão arbitrária para o conjunto de resultados. Para mais informações sobre prestação de intervalo, você pode também consultar a http://www.sunfishstudio.com