Coupure de Bézier

Question

J'essaie de trouver / créer un algorithme pour calculer l'intersection (un nouvel objet rempli) de deux objets 2D remplis de manière arbitraire. Les objets sont définis en utilisant des lignes ou des courbes de Béziers cubiques et peuvent avoir des trous ou s'auto-intersecter. Je suis au courant de plusieurs algorithmes existants faisant de même avec les polygones, répertoriés ici . Cependant, je voudrais soutenir les beziers sans les subdiviser en polygones, et la sortie devrait avoir à peu près les mêmes points de contrôle que l'entrée dans les zones où il n'y a pas d'intersections.

Il s’agit d’un programme interactif permettant de réaliser du CSG, mais la coupure n’a pas besoin d’être en temps réel. J'ai cherché pendant un moment mais je n'ai pas trouvé de bons points de départ.

Answer 1

J'ai trouvé que la publication suivante était la meilleure des informations concernant Bézier Clipping:

T. W. Sederberg, BYU, Notes de cours sur la conception géométrique assistée par ordinateur

Le chapitre 7, qui traite de l'intersection de courbes, est disponible en ligne. Il décrit 4 approches différentes pour trouver des intersections et décrit Bézier Clipping en détail:

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

Answer 2

Je sais que je risque d’être licencié, mais j’enquêtais sur le même problème et j’ai trouvé une solution que j’avais lue dans des revues universitaires, mais pour laquelle je n’avais pas trouvé de solution efficace.

Vous pouvez réécrire les courbes de Bézier sous la forme d'un ensemble de deux équations cubiques à deux variables comme ceci:

• & # 8710; x = ax & # 8321; * t & # 8321; ^ 3 + bx & # 8321; * t & # 8321; ^ 2 + cx # 8321; * t & # 8321; + dx & # 8321; - ax & # 8322; * t & # 8322; ^ 3 - bx & # 8322; * t & # 8322; ^ 2 - cx & # 8322; * t & # 8322; - dx & # 8322;
• & # 8710; y = ay & # 8321; * t & # 8321; ^ 3 + par & # 8321; * t & # 8321; ^ 2 + cy # 8321; * t & # 8321; + dy & # 8321; - ay & # 8322; * t & # 8322; ^ 3 - par & # 8322; * t & # 8322; ^ 2 - cy & # 8322; * t & # 8322; - dy & # 8322;

Évidemment, les courbes se croisent pour les valeurs de (t & # 8321;, t & # 8322;) où & # 8710; x = & # 8710; y = 0. Malheureusement, c'est compliqué par le fait qu’il est difficile de trouver des racines dans deux dimensions et que les approches approximatives tendent à exploser (comme le dit un autre écrivain).

Toutefois, si vous utilisez des nombres entiers ou des nombres rationnels pour vos points de contrôle, vous pouvez utiliser les bases Groebner pour réécrire vos polynômes à deux variables 2 dans un (éventuellement ordre-9-ainsi-vos-neuf-intersections possibles) polynôme monovarié. Après cela, il vous suffit de trouver vos racines (par exemple, t & # 8322;) dans une dimension et de replacer vos résultats dans l’une de vos équations originales pour trouver l’autre dimension.

Burchburger a introduit aux bases Groebner une introduction conviviale appelée & « Gr & # 246; Bases Bner: brève introduction aux théoriciens des systèmes &»; cela m'a été très utile. Recherche le sur Google. L’autre document utile a été le & "; l'aplatissement rapide et précis du cube B & # 233; les courbes de décalage et de décalage &". TF Hain, qui contient de nombreuses équations d’utilité pour les courbes de Bézier, notamment la recherche des coefficients polynomiaux pour les équations x et y.

Quant à savoir si la coupure de Bézier aidera avec cette méthode particulière, j'en doute, mais la coupure de Bézier est une méthode permettant de préciser les intersections possibles, et non de trouver une réponse finale (bien que éventuellement approximative). Avec cette méthode, vous passerez beaucoup de temps à trouver l'équation à une variable, et cette tâche ne sera pas plus facile avec l'écrêtage. La comparaison des racines est triviale.

Cependant, l’un des avantages de cette méthode est qu’elle ne dépend pas de la subdivision récursive de la courbe et que le problème devient un simple problème de recherche de racine unidimensionnelle, qui n’est pas facile, mais bien documenté. L’inconvénient majeur est que le calcul des bases Groebner est coûteux et devient très difficile à manier s’il s’agit de polynômes à virgule flottante ou de courbes de Bézier d’ordre supérieur.

Si vous souhaitez que du code terminé dans Haskell trouve les intersections, faites-le moi savoir.

Answer 3

J'ai écrit du code pour le faire il y a très très longtemps. Le projet sur lequel je travaillais travaillait sur des objets 2D définis en utilisant des limites de Bézier par morceaux générées sous forme de chemins PostScipt.

L'approche que j'ai utilisée était la suivante:

Soit les courbes p, q, définies par les points de contrôle de Bézier. Est-ce qu'ils se croisent?

Calcule les boîtes englobantes des points de contrôle. Si elles ne se chevauchent pas, les deux courbes ne se croisent pas. Sinon:

p.x (t), p.y (t), q.x (u), q.y (u) sont des polynômes cubiques sur 0 < = t, u < = 1,0. La distance au carré (p.x - q.x) ** 2 + (p.y - q.y) ** 2 est un polynôme de (t, u). Utilisez Newton-Raphson pour essayer de résoudre ce problème pour zéro. Jeter toutes les solutions en dehors de 0 & Lt; = t, u & Lt; = 1,0

N-R peut ou non converger. Les courbes peuvent ne pas se croiser ou N-R peut simplement exploser lorsque les deux courbes sont presque parallèles. Donc, coupez N-R si elle ne converge pas après un nombre arbitraire d'itérations. Cela peut être un nombre assez petit.

Si N-R ne converge pas vers une solution, divisez une courbe (disons p) en deux courbes pa, pb à t = 0,5. C'est simple, il suffit de calculer les points médians, comme le montre l'article lié. Puis testez récursivement (q, pa) et (q, pb) pour les intersections. (Notez que dans la couche suivante de la récursion, q est devenu p, de sorte que p et q sont alternativement divisés sur chaque couche de la récursivité.)

La plupart des appels récursifs reviennent rapidement car les boîtes englobantes ne se chevauchent pas.

Vous devrez couper la récursion à une profondeur arbitraire, pour gérer les cas étranges où les deux courbes sont parallèles et ne se touchent pas tout à fait, mais la distance qui les sépare est arbitrairement petite - peut-être seulement 1 ULP de différence.

Lorsque vous trouvez une intersection, vous n’avez pas terminé, car les courbes cubiques peuvent avoir plusieurs intersections. Vous devez donc fractionner chaque courbe au point d'intersection et vérifier de manière récursive d'autres intersections entre (pa, qa), (pa, qb), (pb, qa), (pb, qb).

Answer 4

Il existe un certain nombre de travaux de recherche universitaires sur la coupure de bezier:

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

Je recommande les méthodes d'intervalle car, comme vous le décrivez, il n'est pas nécessaire de diviser des polygones, vous pouvez obtenir des résultats garantis et définir votre propre précision arbitraire pour l'ensemble de résultats. Pour plus d'informations sur le rendu par intervalles, vous pouvez également consulter http://www.sunfishstudio.com