operacje logiczne na siatkach

15

dany zestaw wierzchołków i trójkątów dla każdej siatki. Czy ktoś zna algorytm lub miejsce, w którym można zacząć szukać (najpierw spróbowałem google, ale nie znalazłem dobrego miejsca do rozpoczęcia) do wykonywania operacji boolowskich na wspomnianych siatkach i uzyskania zestawu wierzchołków i trójkąta dla powstałej siatki? Szczególnie interesujące są odejmowanie i zjednoczenie.

Przykładowe zdjęcia: http://www.rhino3d.com/4/help/Commands/Booleans.htm

graphics algorithm graphics-programming procedural lathomas64
źródło

Odpowiedzi:

10

Myślę o tym jako o konstruktywnej geometrii bryły (CSG). Mam nadzieję, że znajdziesz tu pomoc.

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

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

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

Na początek wyszukaj również w Google Konstruktywną geometrię bryłową.

HTH

JustBoo
źródło
+1 - zamierzałem zamieścić te same linki, JustBoo - dopóki nie zauważyłem, że mnie pobiłaś! :)
jacmoe,
dzięki! Terminologia Konstruktywna-pełna geometria jest dokładnie tym, czego potrzebowałem!
lathomas64,
@jacmoe - Ironia jest teraz niesamowita i pełna :-) Za niektóre z nich zasługujesz na uznanie. Dzięki.
JustBoo,
niektóre z nich? : PI wierzę, że zapisałem je wszystkie tam na dole. : D Nadal są to tylko podstawowe rzeczy CSG. Staje się dość włochaty - nawet duże pakiety do modelowania komercyjnego nie mają racji.
jacmoe
3

Myślę, że możemy to rozwiązać, jeśli tylko o tym pomyślimy.

Oczywiście chcesz utworzyć ściany (trójkąty), w których przecinają się dwie geometrie. Następnie masz trzy siatki: przecięcie, które właśnie izolowałeś, geometrię 1 i geometrię 2.

Następnie po prostu usuń to, czego nie potrzebujesz!

  • BooleanDifference: usuń izolowaną część i geometrię 2.
  • BooleanIntersection: usuń geometrię 1 i 2, pozostawiając izolowaną część
  • BooleanUnion: scal geometrie 1 i 2 i usuń izolowaną część (pamiętaj, aby połączyć geometrie 1 i 2 w jednolitą geometrię)
  • BooleanSplit: Oddziel geometrię 1, geometrię 2 i zduplikuj izolowaną część (dołącz jedną do geometrii 1, a drugą do geometrii 2)

Myślę, że to obejmuje, co? Najtrudniejszą częścią byłoby oczywiście stworzenie twarzy skrzyżowania. W tym celu iteruj po każdej twarzy jednej i sprawdź, czy ta twarz jest częścią drugiej; jeśli jest całkowicie w środku, skopiuj twarz jako część siatki przecięcia. Jeśli jest częściowo wewnątrz, musisz podzielić trójkąt wzdłuż linii przecięcia; Myślę, że DirectX i OpenGL miałyby w tym celu funkcje pomocnicze, lub to tylko matematyka 3D (wektory). Nauczyłem się tego rodzaju rzeczy w Rachunku 3 (a może 2?), Ale jeśli nie masz pojęcia, może zapytaj na stronie math.stackexchange.com . I oczywiście, jeśli twarz jest na zewnątrz, nie rób nic. Po wykonaniu iteracji po wszystkich powierzchniach obu siatek pozostanie siatka przecięcia.

Ricket
źródło
2

Jeśli masz do czynienia z modelami wielokątnymi, być może będziesz musiał poradzić sobie z geometrią niezróżnicowaną, co oznacza, że ​​pytanie, co jest „wewnątrz”, a co „na zewnątrz” nie jest zdefiniowane. Wykonanie operacji boolowskiej jest trudne, jeśli nie wiesz, czy masz 0, czy 1.

Musisz także radzić sobie z przypadkowymi przypadkami, takimi jak wielokąty współpłaskie, wielokąty przecinające krawędzie, wierzchołki leżące na krawędziach i / lub twarzach oraz rzeczy tego rodzaju. Żadna z tych rzeczy nie jest niemożliwa, potrzebujesz tylko solidnego sposobu reprezentowania danych siatki i ścisłej definicji tego, co się wydarzy w takich przypadkach.

JasonD
źródło
1

Warto zauważyć, że większość twoich operacji może być reprezentowana przez negację i zjednoczenie, gdzie negacja jakiejś geometrii jest właśnie tą geometrią z odwróconymi normalnymi. Jeśli więc możesz uzyskać prawidłowy związek, pozostałe operacje powinny po prostu następować:

  • przecięcie (A, B): =! union (! A,! B)
  • odejmij (A i B): =! union (! A, B)

Sander ma kilka całkiem dobrych postów na blogu, które omawiają implementacje CSG: http://sandervanrossen.blogspot.com/search/label/CSG

jpaver
źródło
1
Chciałem wspomnieć o moich własnych materiałach CSG, ale najwyraźniej ktoś inny już to zrobił: O)
Sander van Rossen