Vývoj výpočetní geometrie
Petra Surynková Univerzita Karlova v Praze Matematicko-fyzikální fakulta
[email protected]
Přehled
Motivace Úvod { {
Křivky a plochy počítačové grafiky { {
Rozvoj počítačové grafiky Výpočetní geometrie Vývoj konstruování křivek a ploch Příklady křivek a ploch počítačové grafiky
Závěr
Vývoj výpočetní geometrie, 2009
Petra Surynková
Motivace
Podat přehled ve vývoji výpočetní geometrie a počítačové grafiky Zaměříme se na konstruování křivek a ploch
metody vyvinuté pro lodní, letecký a automobilový průmysl
Rozvoj výpočetní techniky
tvorba matematického aparátu, který přinesl nové metody konstruování křivek a ploch (do té doby konstrukce spočívaly na metodách deskriptivní geometrie)
Vývoj výpočetní geometrie, 2009
Petra Surynková
Rozvoj počítačové grafiky
60. léta 20. století - základy počítačové grafiky
zpracování grafické informace na počítači otázky výstupu z počítače, vstup grafické informace do počítače vytváření, manipulace a popis grafické informace rychle vyvíjející se vědní obor
70. léta 20. století – z počítačové grafiky se oddělují nové podobory
př. výpočetní geometrie (Computational Geometry)
Vývoj výpočetní geometrie, 2009
Petra Surynková
Výpočetní geometrie
Pojem výpočetní geometrie poprvé (1971) zavedl Archibald Forest {
{
I
absolvent strojního inženýrství na University of Edinburgh, zakládající člen Computer-aided Design Group, později profesor na University of East Anglia konzultant u Rolls-Royce, Boeing, General Motors a dalších
Výpočetní geometrie
zahrnovala geometrické teorie { { {
zabývající se transformacemi zobrazením prostoru do roviny týkající se konstruování křivek a ploch pomocí počítače a grafického výstupu
Vývoj výpočetní geometrie, 2009
Petra Surynková
Výpočetní geometrie
V dnešním pojetí
II
návrhy a analýza efektivních algoritmů pro řešení geometrických problémů určování vlastností a vztahů objektů v rovině a ve vícerozměrném prostoru tyto problémy mohou vycházet z aplikací například v počítačové grafice nebo v prostorovém modelování
Hlavní oblasti
kombinatorická výpočetní geometrie (Combinatorial Computational Geometry) numerická výpočetní geometrie - častěji známá pod pojmem geometrické modelování nebo Computer Aided Geometric Design (CAGD) – předmětem našeho pojednání
Vývoj výpočetní geometrie, 2009
Petra Surynková
Křivky a plochy
I
Vývoj konstruování křivek a ploch
počátky geometrického modelování – velmi staré kořeny (římské impérium) {
z počátku především v lodním stavitelství
techniky používané při stavbě lodí – nejvíce se zdokonalovaly ve 13. – 16. století (hlavně v Itálii) k uchování základní geometrie lodi se používaly malé dřevěné modely žádné výkresy popisující tvar lodi první známé zmínky o konstruktivní geometrii, pomocí níž se definovaly křivky užité v lodním průmyslu – r. 1752
Vývoj výpočetní geometrie, 2009
Petra Surynková
Křivky a plochy
II
Novodobá historie {
geometrické modelování – veliký pokrok v oblasti letectví 1944 – Roy Liming { analytik, North American Aviation (výrobce letadel) { společně s konstruktérem a designérem Edgardem Schmuedem – matematizace povrchu letounů
Vývoj výpočetní geometrie, 2009
Petra Surynková
Křivky a plochy {
{
{
{
III
v knize Analytical Geometry with Application to Aircraft – poprvé klasické konstruování kombinované s výpočetními metodami poprvé zavedl mnohem účinnější metody – jako první začal popisovat křivky numericky (konstruování křivek a ploch – v minulosti spočívalo na metodách DG) nesporné výhody – interpretace matematického popisu (na rozdíl od kresby) vždy správná veliký ohlas - brzy se rozšířilo do dalších amerických společností pro výrobu letadel
Vývoj výpočetní geometrie, 2009
Petra Surynková
Křivky a plochy
v lodním i leteckém průmyslu { { {
IV
postupně se začínaly využívat kubiky (do té doby kružnice, kuželosečky) plochy se rozdělily na části (tzv. pláty) vše definováno pomocí matematických rovnic
60. léta 20. století {
James C. Ferguson
analytik u amerického výrobce letadel Boeing matematicky popsal plochu s kubickými parametrickými křivkami, na místo ploch vytvářených do té doby graficky na základě oblouků kuželoseček
Vývoj výpočetní geometrie, 2009
Petra Surynková
Křivky a plochy {
Steven Anson Coons
V
profesor na Massachusetts Institute of Technology (MIT) ve strojním inženýrství, zaměstnanec u amerického výrobce letadel Chance Vought matematizace povrchů letounů popisy obecných plátů ploch – zadávány libovolnými okrajovými křivkami jeho teorie – základ pro definice ploch, které se dnes běžně užívají – př. B-spline nebo NURBS plochy
60. léta 20. století {
{
výroba prvních počítačů, které se využívají ve strojírenství k řízení strojů, postupně se rozšiřují do dalších odvětví ještě však nejsou známy metody, jak počítačům předávat data v numerické podobě (Limingova metoda používána zpočátku jen v leteckém průmyslu)
Vývoj výpočetní geometrie, 2009
Petra Surynková
Křivky a plochy
Evropa {
VI
k rozvoji geometrického modelování (a to právě v předávání dat počítači) nezávisle na sobě přispěli Francouzi Paul de Faget de Casteljau a Pierre Etienne Bézier
Paul de Faget de Casteljau (*1930) { {
pracoval pro francouzskou automobilovou firmu – Citroën k zadávání křivek používal kontrolní polygon do té doby tato metoda nebyla nikdy použita v diferenciální geometrii existuje pojem kontrolního polygonu (od r. 1923) – neuplatnilo se v praxi křivka se zadává pomocí blízkých bodů (ne body, které leží na křivce) změna křivky – zajištěna změnou poloh bodů kontrolního polygonu, nemanipuluje se přímo s křivkou (totéž pro plochy)
Vývoj výpočetní geometrie, 2009
Petra Surynková
Křivky a plochy { { {
VII
postup, který používal – dnes známý jako de Casteljau algoritmus firma Citroën jeho práci držela v tajnosti Casteljau své postupy navrhoval již v r. 1959, zveřejněny až na konci 70. let 20. století
Pierre Etienne Bézier (1910 v Paříži - 1999 v Paříži) { { {
pracoval pro francouzskou konkurenční automobilovou firmu – Renault začátek 60. let 20. století – vedoucí konstrukčního oddělení zabýval se tím, jak počítačově reprezentovat křivky a plochy
Vývoj výpočetní geometrie, 2009
Petra Surynková
Křivky a plochy {
{
{
VIII
lze dokázat, že křivky, které vyvinul – shodné s těmi, které popsal de Casteljau nezávisle také objevil algoritmus de Casteljau
Bézierova práce – publikována
R. A. Forrestem doplněna také o popis Bézierových křivek pomocí Bersteinových polynomů Casteljau používal Bersteinovy polynomy již v padesátých letech) díky tomu tyto křivky a plochy nesou jméno Béziera, přestože je Casteljau vyvinul mnohem dříve
Vývoj výpočetní geometrie, 2009
Petra Surynková
Křivky a plochy
IX
většina významných objevů v oblasti geometrického modelování byla až do 70. let 20. století izolována nakonec tyto snahy vyvrcholily vznikem nové vědní disciplíny CAGD {
bez zavedení počítačů do výroby by se ale tato disciplína jistě nemohla rozvinout
Vývoj výpočetní geometrie, 2009
Petra Surynková
Křivky a plochy
X
metody počítačového modelování { { {
velmi se zdokonalily dnes – k dispozici velmi kvalitní matematický aparát výraznou změnu přineslo používání - racionálních Bézierových křivek a ploch a neuniformních racionálních B-spline křivek a ploch tzv. NURBS
těmito metodami lze pomocí aproximace generovat klasické geometrické prvky – kuželosečky, kulové plochy
v
posledních letech vývoj v oblasti geometrického modelování přinesl mnoho dalších typů křivek a ploch zaváděných k různým speciálním účelům
Vývoj výpočetní geometrie, 2009
Petra Surynková
Vývoj výpočetní geometrie, 2009
Petra Surynková
Příklady křivek a ploch
křivky a plochy – explicitně, implicitně, parametricky
I
volba reprezentace závisí na konkrétním účelu a aplikaci
dva základní způsoby zpracování vstupní množiny řídících bodů – interpolace a aproximace Bézierova křivka – příklad aproximační křivky { n - tého stupně zadána n + 1 řídícími body P0 {
{
P1
B(t )
P2
prochází prvním a posledním bodem řídícího polygonu, ostatní body pouze aproximuje nevýhoda - při změně polohy jednoho bodu řídícího polygonu, dojde ke změně tvaru celé křivky
to se řeší dělením křivek na segmenty a jejich postupným napojováním
Vývoj výpočetní geometrie, 2009
P3 Petra Surynková
Příklady křivek a ploch
další aproximační metody {
{ {
II
Coonsovy kubiky – neprocházejí krajními body kontrolního polygonu B-spline křivky – skládají se z více segmentů obecnější křivky – NURBS (neuniformní racionální B-spline křivky)
aparát konstruování křivek – rozšiřitelné do vyšší dimenze { {
interpolační (poměrně složité), aproximační plochy plochy modelujeme pomocí zadávání sítě řídících bodů, která tvoří v trojrozměrném prostoru mnohostěn
Vývoj výpočetní geometrie, 2009
Petra Surynková
Příklady křivek a ploch
III
Bézierova
plocha – příklad aproximační plochy m × n- tého stupně zadána maticí řídících bodů velikosti m + 1) × ( nplochy + 1) {okrajovými (křivkami jsou Bézierovy křivky {
další
příklady
{Coonsovy
plochy {B-spline plochy {NURBS
Vývoj výpočetní geometrie, 2009
Petra Surynková
Ukázky
ukázky Bézierovy křivky ukázky napojování Bézierových plátů {
{ {
velmi zajímavá oblast týkající se modelování ploch - tzv. plátování přičemž se požadují různé stupně hladkosti plátování se využívá při konstrukci složitějších tvarů a výhody jsou obdobné jako u křivek – změny poloh řídících bodů ovlivňují výsledný tvar pouze lokálně
Vývoj výpočetní geometrie, 2009
Petra Surynková
Závěr
geometrické modelování { {
{
obor, který se neustále vyvíjí v současné době využívá počítačové modely prakticky každá oblast výroby rozvoj grafických editorů, tzv. CAD systémů, umožnil projektování na počítači v různých odvětvích průmyslu
Vývoj výpočetní geometrie, 2009
Petra Surynková
