opérations booléennes sur les mailles

15

étant donné un ensemble de sommets et de triangles pour chaque maillage. Quelqu'un connaît-il un algorithme ou un endroit pour commencer à chercher (j'ai essayé Google d'abord mais je n'ai pas trouvé un bon endroit pour commencer) pour effectuer des opérations booléennes sur lesdites mailles et obtenir un ensemble de sommets et de triangles pour le maillage résultant? La soustraction et l'union sont particulièrement intéressantes.

Exemples d'images: http://www.rhino3d.com/4/help/Commands/Booleans.htm

lathomas64
la source

Réponses:

10

Je pense à cela comme Constructive-Solid-Geometry (CSG). J'espère que vous pouvez trouver de l'aide ici.

http://www.alsprogrammingresource.com/csg.html

http://createuniverses.blogspot.com/2009/09/qtcsg-constructive-solid-geometry.html

http://www.nigels.com/research/

Recherchez également sur google la géométrie solide constructive pour commencer.

HTH

JustBoo
la source
+1 - J'allais publier les mêmes liens, JustBoo - jusqu'à ce que je remarque que vous m'avez battu! :)
jacmoe
Merci! La terminologie Constructive-Solid-Geometry est exactement ce dont j'avais besoin!
lathomas64
@jacmoe - L'ironie est incroyable et complète maintenant :-) Vous méritez le crédit pour certains d'entre eux. THX.
JustBoo
certains d'entre eux? : PI pense que je les ai tous notés là-bas. : D Pourtant, ce ne sont que des trucs CSG de base. Cela devient assez poilu à partir de là - même les principaux packages de modélisation commerciale ne l'ont pas bien compris.
jacmoe
3

Je pense que nous pouvons le résoudre si nous y réfléchissons.

Vous souhaiterez évidemment créer des faces (triangles) à l'intersection des deux géométries. Il vous reste alors trois mailles: l'intersection que vous venez d'isoler, la géométrie 1 et la géométrie 2.

Ensuite, supprimez simplement ce dont vous n'avez pas besoin!

  • BooleanDifference: supprimer la pièce isolée et la géométrie 2.
  • BooleanIntersection: supprimer les géométries 1 et 2, laissant la pièce isolée
  • BooleanUnion: fusionnez les géométries 1 et 2 et supprimez la pièce isolée (assurez-vous d'assembler les géométries 1 et 2 en une géométrie solide)
  • BooleanSplit: séparez la géométrie 1, la géométrie 2 et dupliquez la pièce isolée (attachez-en une à la géométrie 1 et l'autre à la géométrie 2)

Je pense que ça le couvre, hein? La partie difficile serait évidemment de créer les faces d'intersection. Pour cela, parcourez chaque face de l'un et vérifiez si cette face fait partie de l'autre; s'il est totalement à l'intérieur, copiez la face dans le cadre du maillage d'intersection. S'il est partiellement à l'intérieur, vous devez diviser le triangle le long de la ligne d'intersection; Je pense que DirectX et OpenGL auraient tous les deux des fonctions d'aide pour cela, ou c'est juste un peu de calcul en avion 3D (vecteurs). J'ai appris ce genre de chose dans Calculus 3 (ou était-ce 2?) Mais si vous n'avez pas la moindre idée, demandez peut-être à math.stackexchange.com . Et puis bien sûr, si le visage est à l'extérieur, ne faites rien. Une fois que vous avez parcouru toutes les faces des deux maillages, vous resterez avec le maillage d'intersection.

Ricket
la source
2

Si vous avez affaire à des modèles polygonaux, vous devrez peut-être vous occuper de la géométrie non multiple, ce qui signifie que la question de savoir ce qui est "à l'intérieur" et ce qui est "à l'extérieur" n'est pas définie. Il est difficile d'effectuer une opération booléenne si vous ne savez pas si vous avez un 0 ou un 1.

Vous devez également faire face à des cas marginaux tels que des polygones coplanaires, des polygones qui coupent des bords, des sommets qui se trouvent sur des bords et / ou des faces, et des choses de cette nature. Rien de tout cela n'est impossible, vous avez juste besoin d'une manière très robuste de représenter vos données de maillage, et d'une définition précise de ce que vous attendez dans ces cas.

JasonD
la source
1

Il convient de noter que la plupart de vos opérations peuvent être représentées par la négation et l'union, où la négation d'une géométrie est simplement cette géométrie avec ses normales inversées. Donc, si vous pouvez réussir l'union, les autres opérations devraient simplement suivre:

  • intersection (A, B): =! union (! A,! B)
  • soustraire (A et B): =! union (! A, B)

Sander a quelques bons articles de blog qui discutent des implémentations CSG: http://sandervanrossen.blogspot.com/search/label/CSG

jpaver
la source
1
J'allais mentionner mes propres trucs CSG, mais apparemment quelqu'un d'autre l'a déjà fait: O)
Sander van Rossen