Podstawy modelowania krzywych i powierzchni Przemysław Kiciak

Spis treści książki

Przedmowa 13 Przedmowa do wydania trzeciego 17 0. Wiadomości wstępne 19 0.1. Reprezentacje figur geometrycznych 19 0.2. Reprezentacje krzywych i powierzchni parametrycznych 20 0.3. Zadanie interpolacyjne Lagrange'a 24 0.3.1. Algorytm Aitkena 24 0.3.2. Własności wielomianowych krzywych interpolacyjnych 26 0.4. Obcinanie narożników 27 1. Krzywe Béziera 29 1.1. Algorytm de Casteljau 29 1.2. Wielomiany Bernsteina 30 1.3. Własności wielomianów Bernsteina 32 1.4. Podwyższenie stopnia 36 1.5. Blossoming 40 1.5.1. Formy biegunowe i diagonalne 40 1.5.2. Algorytm de Casteljau i podział krzywej 41 1.5.3. Formy biegunowe i podwyższenie stopnia 45 1.6. Pochodna krzywej Béziera 45 1.7. Pochodne wyższego rzędu 47 1.8. Łączenie krzywych Béziera 50 1.9. Uzupełnienia 51 1.9.1. Schemat Hornera w bazie wielomianów Bernsteina 51 1.9.2. Obniżenie stopnia krzywej 52 1.9.3. Formy biegunowe i pochodne 54 1.9.4. Krzywizna i skręcenie krzywej Béziera 57 1.9.5. Twierdzenie Menelaosa 60 1.9.6. Twierdzenie aproksymacyjne Weierstrassa 61 2. Wymierne krzywe Béziera 63 2.1. Krzywe jednorodne i wymierne 63 2.2. Jednorodne i wymierne krzywe Béziera 65 2.3. Kształtowanie wymiernych krzywych Béziera 68 2.4. Własności wymiernych krzywych Béziera 69 2.5. Podwyższenie i obniżenie stopnia 70 2.6. Reparametryzacja krzywej wymiernej 71 2.7. Pochodne krzywych wymiernych 72 2.8. Łączenie wymiernych krzywych Béziera 73 2.9. Uzupełnienia 74 2.9.1. Dwustosunek i zasadnicze twierdzenie geometrii rzutowej 74 2.9.2. Reprezentacja krzywej wymiernej przy użyciu punktów pomocniczych 75 2.9.3. Reprezentacja krzywych stożkowych 77 2.9.4. Obcinanie krzywych 79 2.9.5. Rzutowanie krzywych 82 2.9.6. Procedura rysowania krzywych 83 2.9.7. Formy biegunowe krzywych wymiernych 88 2.9.8. Krzywizna i skręcenie wymiernej krzywej Béziera 92 3. Trójkątne płaty Béziera 95 3.1. Określenie płata trójkątnego 95 3.2. Algorytm de Casteljau dla płatów trójkątnych 96 3.3. Podział płata trójkątnego i blossoming 98 3.4. Podwyższenie stopnia płata 100 3.5. Pochodne płatów trójkątnych 101 3.6. Łączenie płatów trójkątnych 104 3.7. Wymierne trójkątne płaty Béziera 105 3.8. Uzupełnienia 107 3.8.1. Szybkie obliczanie punktów płata trójkątnego 107 3.8.2. Formy biegunowe i krzywizny płata 108 3.8.3. Reparametryzacja płata wymiernego 111 3.8.4. Trójkąty na sferze 111 4. Tensorowe płaty Béziera 115 4.1. Określenie płata 115 4.2. Własności płatów wynikające z określenia tensorowego 116 4.2.1. Wyznaczanie punktów płata 117 4.2.2. Podwyższenie stopnia płata 119 4.2.3. Pochodne cząstkowe płatów Béziera 120 4.2.4. Podział płata Béziera 121 4.2.5. Zasady łączenia płatów Béziera z ciągłościąCk 123 4.3. Płaszczyzna styczna do płatów zdegenerowanych 124 4.4. Wymierne prostokątne płaty Béziera 125 4.4.1. Podstawowe własności płatów wymiernych 126 4.4.2. Obliczanie pochodnych płata wymiernego 127 4.4.3. Płaszczyzna styczna do płata wymiernego 128 4.5. Uzupełnienia 130 4.5.1. Przetwarzanie tablic punktów kontrolnych 130 4.5.2. Znajdowanie tensorowej reprezentacji płatów trójkątnych 133 4.5.3. Swobodna deformacja 137 4.5.4. Śledzenie promieni 141 4.5.5. Wyznaczanie punktów przecięcia krzywych 147 4.5.6. Rozwiązywanie układów równań algebraicznych 148 4.5.7. Wyznaczanie przecięć powierzchni 159 5. Krzywe B-sklejane 173 5.1. Konstrukcja gładko połączonych krzywych Béziera 175 5.2. Zastosowanie różnic dzielonych 178 5.2.1. Funkcje sklejane i baza obciętych potęg 178 5.2.2. Określenie funkcji B-sklejanych 181 5.2.3. Wzór Mansfielda-de Boora-Coxa 185 5.2.4. Algorytm de Boora 186 5.2.5. Własności funkcji i krzywych B-sklejanych 188 5.2.6. Pochodne krzywej B-sklejanej 191 5.3. Wstawianie węzłów 195 5.3.1. Procedura wstawiania węzła 195 5.3.2. Związek wstawiania węzła z algorytmem de Boora 199 5.3.3. Zmiana bazy po wstawieniu węzła 200 5.3.4. Usuwanie węzła 204 5.3.5. Zastosowania procedury wstawiania węzła 205 5.4. Blossoming 208 5.4.1. Formy biegunowe funkcji i krzywych sklejanych 208 5.4.2. Ciągłość funkcji sklejanych w węzłach 211 5.4.3. Formy biegunowe i wstawianie węzłów 217 5.4.4. Algorytm Oslo 217 5.4.5. Zbieżność procesu wstawiania węzłów 222 5.4.6. Podwyższenie stopnia 227 5.5. Funkcje B-sklejane i sympleksy 228 5.5.1. Funkcje miary przekroju 228 5.5.2. Sympleksy i wielomiany Bernsteina 229 5.5.3. Wielościany, wielomiany i funkcje sklejane 231 5.5.4. Sympleksowa definicja funkcji B-sklejanych 232 5.5.5. Związek sympleksów z różnicami dzielonymi 233 5.5.6. Całkowanie funkcji B-sklejanych 239 5.5.7. Ciągłość funkcji sklejanych w węzłach 239 5.5.8. Rozkład jedynki 240 5.5.9. Własność minimalnego no´snika 241 5.5.10. Wstawianie węzła 242 5.5.11. Podwyższenie stopnia 244 5.5.12. Sympleksowy dowód wzoru Mansfielda-de Boora-Coxa 246 5.6. Krzywe B-sklejane z węzłami równoodległymi 250 5.7. Wymierne krzywe B-sklejane (krzywe NURBS) 255 5.8. Uzupełnienia 260 5.8.1. Krzywe zamknięte 260 5.8.2. Interpolacyjne krzywe B-sklejane trzeciego stopnia 261 5.8.3. Twierdzenie Schoenberga-Whitney 264 5.8.4. Aproksymacyjne krzywe B-sklejane 266 5.8.5. Obliczanie długości krzywych 268 6. Powierzchnie B-sklejane 271 6.1. Określenie płata B-sklejanego 271 6.2. Podstawowe własności płatów B-sklejanych 272 6.3. Wymierne powierzchnie B-sklejane (powierzchnie NURBS) 274 6.4. Przykłady konstrukcji płatów B-sklejanych 275 6.4.1. Powierzchnie rozpinane 275 6.4.2. Powierzchnie zakreślane 281 6.4.3. Produkt sferyczny i powierzchnie obrotowe 284 6.5. Powierzchnie reprezentowane przez siatki 286 6.5.1. Płaty tensorowe z węzłami równoodległymi 286 6.5.2. Siatki nieregularne 288 6.5.3. Zagęszczanie siatek 289 6.5.4. Elementy szczególne w siatkach 291 6.5.5. Powierzchnia graniczna 292 6.6. Uzupełnienia 294 6.6.1. Momenty i twierdzenia Guldina 294 6.6.2. Powierzchnie prostokreślne i rozwijalne 298 7. Krzywe i powierzchnie w reprezentacji Hermite'a 301 7.1. Lokalne bazy Hermite'a 301 7.2. Interpolacyjne krzywe sklejane trzeciego stopnia 303 7.2.1. Związek reprezentacji Hermite'a i Béziera krzywych trzeciego stopnia 303 7.2.2. Równania ciągłości pochodnej drugiego rzędu 304 7.2.3. Warunki brzegowe 305 7.2.4. Dobór węzłów dla krzywych interpolacyjnych 309 7.2.5. Własność minimalnej energii 310 7.2.6. Błąd aproksymacji dla interpolacyjnych funkcji sklejanych 312 7.3. Płaty określone przez warunki interpolacyjne 317 7.3.1. Płaty Coonsa 317 7.3.2. Płaty bikubiczne w reprezentacji Hermite'a 322 7.3.3. Konstrukcja powierzchni złożonych z płatów bikubicznych 324 7.3.4. Płaty Gregory'ego 328 7.3.5. Płaty Browna 331 8. Ciągłość geometryczna krzywych 333 8.1. Pojęcie ciągłości geometrycznej 333 8.1.1. Związek ciągłości parametryzacji z ciągłością˛ geometryczną 334 8.1.2. Krzywe geometrycznie sklejane 335 8.2. Równania ciągłości geometrycznej krzywych 337 8.2.1. Wzór Faa di Bruno 337 8.2.2. Łączenie zreparametryzowanych krzywych 338 8.3. Interpretacja ciągłości geometrycznej krzywych 342 8.4. Krzywe ? -sklejane 345 8.5. Krzywe ?-sklejane 348 8.5.1. Definicja 349 8.5.2. Znajdowanie łuków wielomianowych krzywej ?-sklejanej 350 8.5.3. Konstrukcja funkcji ?-sklejanych 352 8.5.4. Istnienie i jednoznaczność funkcji ?-sklejanych 358 8.5.5. Krzywe ?-sklejane z globalnymi parametrami połączenia 360 8.5.6. Dalsze własności i przykłady 362 8.5.7. Wstawianie węzłów 365 8.6. Krzywe ?-sklejane 367 8.7. Tensorowe powierzchnie geometrycznie sklejane 369 9. Ciągłość geometryczna powierzchni 371 9.1. Równania ciągłości geometrycznej 371 9.1.1. Uogólniony wzór Faa di Bruno 371 9.1.2. Równania ciągłości geometrycznej połączenia pary płatów 372 9.2. Interpretacja ciągłości geometrycznej powierzchni 375 9.3. Równania ciągłości dla płatów wielomianowych 377 9.3.1. Podstawy algebraiczne 377 9.3.2. Rozwiązania równań ciągłości 380 9.4. Konstrukcja pary gładko połączonych płatów 385 9.4.1. Konstrukcja pary płatów wielomianowych połączonych z ciągłością G1 387 9.4.2. Konstrukcja pary płatów wielomianowych połączonych z ciągłością˛G2 390 9.4.3. Konstrukcja pary gładko połączonych płatów wymiernych 391 9.5. Geometrycznie ciągłe powierzchnie wypełniające 394 9.5.1. Wypełnianie przerwy między płatami B-sklejanymi 394 9.5.2. Powierzchnie wypełniające dla płatów obciętych 399 9.6. Ciągłość geometryczna powierzchni granicznych 407 9.7. Warunki zgodności G1 we wspólnym narożniku 411 9.7.1. Lokalne warunki zgodności G1 412 9.7.2. Globalne warunki zgodności G1 414 9.8. Warunki zgodności drugiego i wyższych rzędów 419 9.8.1. Lokalne warunki zgodności G2 419 9.8.2. Funkcje sklejane dwóch zmiennych 422 9.8.3. Trygonometryczne funkcje sklejane 430 9.8.4. Trygonometryczne funkcje sklejane i warunki zgodności G1 434 9.8.5. Trygonometryczne funkcje sklejane i warunki zgodności G2 437 9.9. Wypełnianie wielokątnych otworów 450 9.9.1. Schemat Hahna 450 9.9.2. Podstawy teoretyczne 452 9.9.3. Konstrukcja przestrzeni klasy G1 i G2 456 9.9.4. Minimalizacja form kwadratowych 473 9.9.5. Optymalizacja kształtu 482 9.9.6. Przykładowe wyniki 487 A. Przegląd podstawowych pojęc´ algebry liniowej 491 A.1. Przestrzenie liniowe 491 A.1.1. Macierze 493 A.1.2. Układy współrzędnych 494 A.1.3. Przekształcenia liniowe 495 A.1.4. Funkcjonały i przestrzeń sprzężona 496 A.1.5. Normy 496 A.1.6. Iloczyny skalarne 497 A.1.7. Przekształcenia izometryczne 499 A.1.8. Wyznaczniki 499 A.1.9. Iloczyny wektorowe i zewnętrzne 501 A.1.10. Interpretacja geometryczna funkcjonału 503 A.1.11. Układy równań liniowych 504 A.1.12. Algebraiczne zagadnienia własne 508 A.2. Przestrzenie afiniczne 509 A.2.1. Współrzędne kartezjańskie i jednorodne 511 A.2.2. Współrzędne barycentryczne 512 A.2.3. Przekształcenia afiniczne 515 A.2.4. Przekształcenia afiniczne przestrzeni trójwymiarowej 517 A.2.5. Mierzenie zbiorów 524 B. Działania na wielomianach w bazach Bernsteina 529 B.1. Działania na wielomianach 529 B.1.1. Mnożenie i dzielenie 529 B.1.2. Mnożenie wielomianów wielu zmiennych 532 B.1.3. Dodawanie i odejmowanie 532 B.1.4. Algorytm Euklidesa 533 B.1.5. Obliczanie iloczynu skalarnego 534 B.2. Działania na funkcjach wektorowych 535 B.2.1. Mnożenie wielomianu i krzywej 535 B.2.2. Wyznaczanie płatów Béziera opisujących wektory normalne 537 B.3. Działania na funkcjach sklejanych 543 B.3.1. Mnożenie funkcji sklejanych 543 B.3.2. Obliczanie iloczynu skalarnego 544 C. Elementy geometrii różniczkowej 545 C.1. Krzywizny krzywych 545 C.1.1. Parametryzacja łukowa 545 C.1.2. Równania Freneta 546 C.1.3. Krzywizna krzywej płaskiej 548 C.1.4. Krzywizny krzywej przestrzennej 549 C.2. Krzywizny powierzchni 550 C.2.1. Różniczki płata 550 C.2.2. Pierwsza i druga forma podstawowa 552 C.2.3. Krzywizna normalna powierzchni 554 C.2.4. Krzywizny i kierunki główne powierzchni 556 C.2.5. Klasyfikacja punktów powierzchni 557 D. Różnice dzielone 559 D.1. Schemat Hornera i bazy Newtona 560 D.2. Określenie i własności różnic dzielonych 562 D.3. Algorytm różnic dzielonych 565 D.4. Reszta interpolacyjna 567 D.5. Wzór Leibniza 568 D.6. Różnice dzielone, sympleksy i funkcje B-sklejane 569 E. Metody numeryczne 571 E.1. Arytmetyka zmiennopozycyjna 571 E.1.1. Uwagi o błędach reprezentacji i zaokrągleń 572 E.2. Rozwiązywanie równań liniowych 575 E.2.1. Układy z macierzą trójkątną 575 E.2.2. Eliminacja Gaussa 576 E.2.3. Inne metody 580 E.3. Rozwiązywanie liniowych zadań najmniejszych kwadratów 582 E.3.1. Zadania regularne 582 E.3.2. Zadania dualne 585 E.3.3. Zadania regularne z więzami 586 E.4. Rozwiązywanie równań nieliniowych 587 E.4.1. Metoda bisekcji 589 E.4.2. Metoda Newtona 591 E.4.3. Metoda Newtona dla układów równań 593 E.4.4. Metoda siecznych 596 E.4.5. Regula falsi i algorytm Illinois 597 E.5. Algebraiczne zagadnienie własne 601 E.6. Optymalizacja 602 E.6.1. Minimalizacja funkcji jednej zmiennej 602 E.6.2. Minimalizacja gładkiej funkcji wielu zmiennych 603 F. Wizualizacja kształtu powierzchni 605 F.1. Funkcje kształtu i ich warstwice 606 F.1.1. Własności warstwic 606 F.1.2. Przekroje płaskie powierzchni 607 F.1.3. Lambertowskie odbicie światła i izofoty 608 F.1.4. Linie odblasku 610 F.1.5. Krzywizny powierzchni 614 F.2. Krzywe charakterystyczne 615 F.2.1. Całkowanie krzywych charakterystycznych 615 F.2.2. Warstwice i linie najszybszego spadku funkcji kształtu 617 F.2.3. Linie krzywiznowe 619 Literatura 621 Skorowidz