Křivky a povrchy

Note	Implicitní a parametrické reprezentace. Interpolace a aproximace. Cn, Gn spojitost, podmínky spojitosti pro po částech definované funkce. Bézierovy křivky, B-spline křivky, ~~NURBS,~~ Coonsovy ~~křivky a~~ pláty. Povrchy tvořené rekurzivním dělením polygonů. PB009, PA010

Druhy reprezentace

Jak povrchy tak křivky mohou být reprezentovány třemi způsoby:

Explicitní reprezentace

Křivka nebo povrch je vyjádřen pomocí funkce.

y z = f (x) = f (x, y) pro k \overset{r}{ˇ} ivku pro povrch

Omezení na funkce je však příliš silné. Spoustu pěkných křivek a povrchů nelze vyjádřit pomocí jediné funkce.

Implicitní reprezentace

Máme k dispozici rovnici ve tvaru:

F (x, y) F (x, y, z) = c = c pro k \overset{r}{ˇ} ivku pro povrch

kde $c$ je konstanta a je obvykle rovná 0.

Tato rovnice udává množinu bodů, ze které se křivka nebo povrch sestává. Takové množině se někdy říká level set a metodám, které s nimi pracují level-set methods.

Important

Výhodou implicitně zadaných ploch je kompaktnější reprezentace a jednodušší ray casting. Nicméně výpočty s nimi jsou časově náročné, takže se stejně nejdřív převádí na polygonové meshe — polygonizace.

Important

Tahle sekce přesahuje do 3D modelování a datové struktury → Implicitní reprezentace a modelování.

Parametrická reprezentace

Udává dráhu pohybujícího se bodu, či něco jako hladinu povrchu. Snadno se z ní vyjadřuje tečna, čehož se využívá při jejich skládání.

Pro křivky:

Q (t) q (t) = [x (t), y (t), z (t)] = (x (t), y (t), z (t)) (bodov \overset{a}{ˊ} rovnice k \overset{r}{ˇ} ivky) (vektorov \overset{a}{ˊ} rovnice k \overset{r}{ˇ} ivky)

kde $t$ je "čas" z intervalu $[t_{min}, t_{max}]$ , nejčastěji $[0, 1]$ . Výhodné je, že takto zadaná křivka se může sama křížit, uzavírat, a podobně.

Analogicky pro povrchy:

Q (u, v) = [x (u, v), y (u, v), z (u, v)]

kde pro $u$ a $v$ už metafora s časem nefunguje. Obvykle obě náleží do intervalu $[0, 1]$ .

Terminologie

Pro zbytek otázky je podstatné znát několik termínů:

Dotykový / tečný / tangent vektor křivky

Aktuální směr křivky v daném bodě. Z parametricky vyjádřené křivky $q$ ho lze v čase $t_{0}$ získat jako derivaci:

q^{'} (t_{0}) = (\frac{\partial x ( t _{0} )}{\partial t}, \frac{\partial y ( t _{0} )}{\partial t}, \frac{\partial z ( t _{0} )}{\partial t})

Rovnice tečny $p$ je pak $p (u) = q (t_{0}) + q^{'} (t_{0}) \cdot u$ .

Polynomiální křivka

Velmi častý druh křivek v počítačové grafice. Vypadají jako:

Q_{n} (t) = a_{0} + a_{1} \cdot t + a_{2} \cdot t^{2} + \dots + a_{n} \cdot t^{n}

Je velmi snadné je evaluovat a derivovat. Z nich často skládáme křivky po částech.

Kubika

Polynomiální křivka třetího stupně.

Parametricky:

x (t) = a_{x} t^{3} + b_{x} t^{2} + c_{x} t + d_{x} y (t) = a_{y} t^{3} + b_{y} t^{2} + c_{y} t + d_{y} z (t) = a_{z} t^{3} + b_{z} t^{2} + c_{z} t + d_{z}

Zapsáno pomocí matice:

Q (t) = T \cdot C = [t^{3}, t^{2}, t, 1] \cdot a_{x} b_{x} c_{x} d_{x} a_{y} b_{y} c_{y} d_{y} a_{z} b_{z} c_{z} d_{z}

Tečný vektor $q^{'}$ je pak:

q^{'} (t) = \frac{\partial}{\partial t} \cdot C = [3 t^{2}, 2 t, 1, 0] \cdot C

U kubik platí, že $C = M \cdot G$ , kde $M$ je bázová matice a $G$ je vektor geometrických podmínek.

$T \cdot M$ definuje polynomiální bázi — skupinu polynomů — která je společná pro všechny křivky určitého typu.
$G$ pak obsahuje parametry konkrétní křivky — řídící a dotykové body.
$t$ udává, jestli jsme na začátku či konci křivky.

Tečná rovina

Rovina, která se povrchu dotýká v konkrétním bodě a její normála je na povrch kolmá. Pro parametrickou plochu $Q$ je tečná plocha $T$ dána jako:

q_{u} (u, v) q_{v} (u, v) T (r, s) = \frac{\partial Q ( u , v )}{\partial u} = (\frac{\partial x ( u , v )}{\partial u}, \frac{\partial y ( u , v )}{\partial u}, \frac{\partial z ( u , v )}{\partial u}) = \frac{\partial Q ( u , v )}{\partial v} = (\frac{\partial x ( u , v )}{\partial v}, \frac{\partial y ( u , v )}{\partial v}, \frac{\partial z ( u , v )}{\partial v}) = Q (u, v) + r . q_{u} + s . q_{v}, r, s \in R

kde $q_{u}$ je tečný vektor ve směru parametru $u$ , a analogicky $q_{v}$

Normála / kolmice

Normálu $n$ parametricky dané plochy $Q$ určíme jako vektorový součin tečných vektorů:

n = \frac{q _{u} \times q _{v}}{∥ q _{u} \times q _{v} ∥}

Gradient

Funkce, která vrací "směr a velikost největšího růstu". Nejčastěji se používá u povrchů k určení normály, ale lze ji použít v libovolné dimenzi k různým účelům. Pokud je povrch $f$ zadán implicitně, pak je gradient:

\nabla f = (\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}, \frac{\partial f}{\partial z})

Interpolace a aproximace

Interpolace: Prokládání daných bodů křivkou. Konstrukce křivky, která interpolovanými body prochází.

V případě kubiky výše to znamená, že $G$ obsahuje body, kterými křivka prochází.

Mějmě funkci $f (x)$ , jejíž hodnotu známe v bodech $f (x_{0}), f (x_{1}), \dots, f (x_{n})$ . Interpolace znamená nalezení hodnot $f (x)$ pro všechna $x_{0} < x < x_{n}$ .
Aproximace: Přiblížení, odhad. Je nepřesným popisem nějaké jiné entity (např. čísla či funkce). Saháme k ní, pokud pro analytické řešení nemáme dost informací nebo výpočetní kapacity. Aproximace je méně přesná než interpolace, ale výpočetně jednodušší.

V případě kubiky výše to znamená, že $G$ obsahuje řídící body, které sice udávají směr křivky, ale ta jimi neprochází.

Spojitost

Představme si, že máme dva segmenty křivky: $Q_{1}$ a $Q_{2}$ , spojené v bodě $t$ , tedy $Q_{1} (t) = Q_{2} (t)$ . Tento bod nazýváme uzlem (knot). Spojitost je zjednodušeně způsob, jakým jsou tyhle segmenty spojeny v uzlu.

Parametrická spojitost stupně $n$ ( $C^{n}$ )

Křivka $Q$ patří do třídy $C^{n}$ , pokud má ve všech bodech $t$ spojitou derivaci až do řádu $n$ .

$C^{0}$ — dva segmenty jsou spojené; konečný bod jednoho segmentu je počátečním bodem druhého.
$C^{1}$ — platí $C^{0}$ a navíc je tečný vektor na konci prvního segmentu shodný s tečným vektorem na začátku druhého segmentu — první derivace v uzlu jsou si rovny.
$C^{2}$ — platí $C^{1}$ a druhé derivace v uzlu jsou si rovny.
$C^{n}$ — platí $C^{n - 1}$ a navíc jsou si $n$ -té derivace v uzlu rovny.

Bod pohybující se po $C^{0}$ -spojité dráze sebou "trhne" v prostoru, když projde uzlem.
V případě $C^{1}$ křivky se při průchodu uzlem směr ani rychlost prudce nezmění, může se však změnit zrychlení.
V případě $C^{2}$ křivky se při průchodu uzlem nezmění už ani zrychlení.

Geometrická spojitost stupně $n$ ( $G^{n}$ )

Je podobná parametrické spojitosti, ale vyžaduje jen "geometrickou" spojitost. Vyžaduje, aby si derivace byly sobě úměrné. [5] [6]

$G^{0}$ — koncový bod prvního segmentu je totožný s počátečním bodem druhého segmentu ( $C^{0} = G^{0}$ ).
$G^{1}$ — platí $G^{0}$ a navíc je směr tečny na konci prvního segmentu shodný s směrem tečny na začátku druhého segmentu. Velikost tečného vektoru (rychlost) se však může prudce změnit.
$G^{2}$ — platí $G^{1}$ a navíc mají stejný střed křivosti (center of curvature). [4]

Platí, že $C^{n} \Rightarrow G^{n}$ , ale obráceně $G^{n} \neq \Rightarrow C^{n}$ .

Note	Podle slidů z PB009 musí faktor úměrnosti být různý od 0. [3] Podle Barskyho a DeRoseho musí v první derivaci být $> 0$ a v dalších už je to šumák. [6] Co je správně? Kdo ví. Nemám dost častu to zjistit, takže to ponechávám jako cvičení čtenáři.

Křivky

Lagrangeův interpolační polynom

Základní metoda interpolace funkce, jejíž hodnotu známe jen v $n + 1$ diskrétních bodech $P_{0}, P_{1}, ... P_{n}$ . Sestává se z pomocných polynomů $ℓ_{i}$ : [7]

ℓ_{i} (x) = 0 \leq k \leq n, k \neq = i \prod n \frac{x - x _{k}}{x _{i} - x _{k}}

Který splňuje podmínku:

ℓ_{i} (x_{k}) = {10 pro i = k pro i \neq = k

Pak polynom $P$ interpoluje danou množinu bodů:

P (x) = i = 0 \sum n P_{i} ℓ_{i} (x)

Blbé je, že musíme všechny pomocné polynomy přepočítat, když přidáme nový bod.

Hornerovo schéma / Horner’s method: Metoda evaluace polynomů. Vychází z myšlenky, že násobení se dá nestovat: [15]

$a_{0} + a_{1} \cdot x + a_{2} \cdot x^{2} + ... + a_{n} \cdot x_{n} = a_{0} + x (a_{1} + x (a_{2} + ... + x (a_{n - 1} + x \cdot a_{n}) ...))$

Vyžaduje jen $n$ násobení a $n$ sčítání, což je optimální.

Hermitovské křivky

Asi nejznámnější interpolační křivky v počítačové grafice. Jsou určeny dvěma řídícími body — $P_{0}$ a $P_{1}$ — a dvěma dotykovými vektory — $p_{0}^{'}$ a $p_{1}^{'}$ . Řídící body určují začátek a konec křivky, dotykové vektory její směr a vyklenutí. Pokud jsou oba vektory nulové, je to úsečka.

Je jednoduché je na sebe navázat v $C^{1}$ , neboť tečné vektory jsou přímo součástí definice.

Cubic Hermite spline / Ferguson curve: Pro Hermitovskou kubiku platí: [9] [10]

$Q (t) = [t^{3} t^{2} t 1] \cdot 2 - 3 01 - 2 300 1 - 2 10 1 - 1 00 \cdot P_{0} P_{1} p^{'}_{0} p^{'}_{1} = = P_{0} \cdot F_{1} (t) + P_{1} \cdot F_{2} (t) + p^{'}_{0} \cdot F_{3} (t) + p^{'}_{1} \cdot F_{4} (t)$

kde $F_{1}, F_{2}, F_{3}, F_{4}$ jsou Hermitovské polynomy 3. stupně:

$F_{1} (t) F_{2} (t) F_{3} (t) F_{4} (t) = 2 t^{3} - 3 t^{2} + 1 = - 2 t^{3} + 3 t^{2} = t^{3} - 2 t^{2} + t = t^{3} - t^{2}$

Bézierova křivka

Asi nejčastěji používaná aproximační křivka. Využívá se zejména ve 2D grafice, třeba při definici fontů.

Bézierova křivka $n$ -tého stupně je definována $n + 1$ řídícími body $P_{0}, P_{1}, ... P_{n}$ .
Změnou polohy jednoho bodu dojde ke změně celé křivky. Proto se často dělí na segmenty menšího stupně, které se pak navazují na sebe.

Základem jsou Bernsteinovy polynomy $n$ -tého stupně:

b_{ν, n} (x) = (ν n) x^{ν} (1 - x)^{n - ν}, ν = 0, \dots, n,

Mezi jejich vlastnosti patří:

Nezápornost: $b_{ν, n} (x) \geq 0$ pro $x \in [0, 1]$ .
Jejich součet je roven jedné: $\sum_{ν = 0}^{n} b_{ν, n} (x) = 1$ .
Dají se vyjádřit rekurzí: $b_{ν, n} (x) = (1 - x) \cdot b_{ν, n - 1} (x) + x \cdot b_{ν - 1, n - 1} (x)$ .

Obrázek 1. Bernstein basis polynomials for 4th degree curve blending by VisorZ

DeCasteljau algorithm: Rekurzivní algoritmus pro konstrukci Bézierových křivek. Využívá vlastností Bernsteinových polynomů.
Bézierova kubika: Bézierova křivka třetího stupně. Je dána čtyřmi řídícími body $P_{0}, P_{1}, P_{2}, P_{3}$ :

$P (t) = (1 - t)^{3} \cdot P_{0} + 3 \cdot (1 - t)^{2} \cdot t \cdot P_{1} + 3 \cdot (1 - t) \cdot t^{2} \cdot P_{2} + t^{3} \cdot P_{3}$

B-spline

Splajn / spline

Splajn stupně $n$ po částech definovaná polynomiální funkce stupně $n - 1$ proměnné $x$ . [8]

Tip	Po částech definovaná / piecewise znamená, že má několik intervalů a pro každý z nich jiný polynom.

Místa, kde se části polynomu dotýkají jsou uzly a jsou značeny pomocí $t_{0}, t_{1}, ..., t_{n}$ a řazeny v neklesajícím pořadí.
Pokud jsou uzly unikátní, pak je splajn v uzlech $C^{n - 2}$ spojitý. [8]
Pokud je $r$ uzlů shodných, je v tomto místě pouze $C^{n - r - 1}$ spojitý.

⁂

Basis spline / B-spline stupně $n$ je aproximační křivka / splajn daná sekvencí $n$ uzlů. Jako funkce vrací užitečné hodnoty jen mezi prvním a posledním uzlem, všude jinde je nulová. Svůj název dostala podle toho, že B-splajny slouží jako bázové funkce pro splajnové křivky.

Lze ji definovat pomocí Cox-de Boorovy rekurzivní formule:

Tip	de Boorův algoritmus je generalizací DeCasteljauova algoritmu ale pro B-splajny.

B_{i, 0} (x) B_{i, n} (x) = {10 pro t_{i} \leq x < t_{i + 1} jinak = \frac{x - t _{i}}{t _{i + n} - t _{i}} B_{i, n - 1} (x) + \frac{t _{i + n + 1} - x}{t _{i + n + 1} - t _{i + 1}} B_{i + 1, n - 1} (x)

Zatímco $x$ jde od $t_{i}$ k $t_{i + n}$ , červený výraz začíná na 1 a klesá k 0.

Podobně, zatímco $x$ jde od $t_{i + 1}$ k $t_{i + n + 1}$ , modrý výraz začíná na 0 a roste k 1.

Navíc platí $\sum_{i = 0}^{n} B_{i, n} (x) = 1$ .

Jejich užitečnost spočívá v tom, že libovolný splajn stupně $n$ daný sekvencí uzlů lze vyjádřit jako lineární kombinaci B-splajnů:

S (x) = i = 0 \sum c_{i} B_{i, n} (x)

Note	Uzlů je zpravidla víc než $n + 1$ , protože pak teprve máme víc než jeden B-spline, který kombinujeme.

Uniformní B-splajny

Uzly jsou rozloženy rovnoměrně. Tedy mezi každými dvěma uzly $t_{i}$ a $t_{i + 1}$ je stejná vzdálenost $h$ .

Příklad:

T = [t_{0} t_{1} t_{2} t_{3}] = [0 0. \overline{3} 0. \overline{6} 1]

Coonsova kubika

Kubika $P$ daná 4 řídícími body $P_{0}, P_{1}, P_{2}, P_{3}$ . Neprochází ani jedním z kontrolních bodů. [11]

P (t) B_{0} (t) B_{1} (t) B_{2} (t) B_{3} (t) = B_{0} (t) \cdot P_{0} + B_{1} (t) \cdot P_{1} + B_{2} (t) \cdot P_{2} + B_{3} (t) \cdot P_{3}, t \in [0, 1] = \frac{1}{6} (1 - t)^{3} = \frac{1}{6} (3 t^{3} - 6 t^{2} + 4) = \frac{1}{6} (- 3 t^{3} + 3 t^{2} + 3 t + 1) = \frac{1}{6} t^{3}

Note	Něco ohledně tohohle termínu mi hrozně smrdí. Zdá se, že jediní, kdo používají "coons cubic curve" jsme my a ČVUT.

Povrchy

Interpolace je náročná, proto se častěji používají aproximační povrchy.

Interpolační plocha

Plocha $P$ . Dáno:

$(m + 1) \times (n + 1)$ řídících bodů $P_{i, j}$ .
$m + 1$ hodnot $u_{k}$ a $n + 1$ hodnot $v_{l}$ .

Platí, že $P (u_{k}, u_{l}) = P_{k, l}$ pro $k = 0, 1, ..., m$ a $l = 0, 1, ..., n$ .

Interpolujeme vektorovým polynomem $a_{i, j}$ :

P (u, v) = i = 0 \sum m \sum j = 0^{n} a_{i, j} \cdot u^{i} \cdot v^{j}

V případě Lagrangeova polynomu je $a_{i, j} = ℓ_{i}^{m} (u) \cdot ℓ_{j}^{n} (v)$ .

Hermitovský plát

Interpolační povrch.

12-ti vektorová varianta: 4 rohové body a 8 tečných vektorů.
16-ti vektorová varianta: 4 rohové body, 8 tečných vektorů a 4 zkrutové vektory.

Coonsovy pláty / Coonsovy plochy / Coons patch

Plochy vzniknuvší interpolací mezi křivkami udávající jejich okraje. Dají se na sebe pěkně napojovat, právě protože jsou definovány svými okraji.

Warning

Coonsovy pláty jsou interpolační, zatímco Coonsovy křivky jsou aproximační.

Bilineární Coonsovy pláty: Určeny 4 křivkami $P (u, 0), P (u, 1), P (0, v), P (1, v)$ , které tvoří okraj plátu.

Implicitně se dá zapsat jako:

$[1 - u - 1 u] \cdot C \cdot 1 - v - 1 v = 0$

Povrch je pak tvořen body $C$ , které tuto rovnici splňují.

Explicitně se dá zapsat jako:

$P (u, v) = [1 - u u] \cdot [P_{0, v} P_{1, v}] + [P_{u, 0} P_{u, 1}] \cdot [1 - v v] - [1 - u u] \cdot [P_{0, 0} P_{1, 0} P_{0, 1} P_{1, 1}] \cdot [1 - v v]$

Zásadním nedostatek těchto ploch je, že není snadné vyjádřit tečné vektory na okrajích, a proto není snadné je napojovat na sebe.
Bikubické Coonsovy pláty: Podobné bilineárním, ale používájí Hermitovské polynomy:

$F_{1} (t) F_{2} (t) = 2 t^{3} - 3 t^{2} + 1 = - 2 t^{3} + 3 t^{2}$

Implicitně je pak tento plát dán:

$[F_{1} (u) - 1 F_{2} (u)] \cdot C \cdot F_{1} (v) - 1 F_{2} (v) = 0$

Stejně jako u bilineárních ploch, i tady je těžké získat tečné vektory na okrajích.
Obecná bikubická plocha: Kromě rohů je parametrizována i tečnými vektory na okrajích. Konečně tedy umožňuje snadné navazování.

Bézierovy plochy

Aproximační plochy dány $(m + 1) \times (n + 1)$ řídícími body. Jsou:

snadno diferencovatelné,
jednoduše se modelují,
lze z nich relativně snadno spočítat průnik s paprskem,
speciální případ NURBS ploch.

P (u, v) = i = 0 \sum m j = 0 \sum n B_{i}^{m} (u) \cdot B_{j}^{n} (v) \cdot a_{i, j}

Kde $B_{i}^{m} (u)$ a $B_{j}^{n} (v)$ jsou Bernsteinovy polynomy.

Při změně jendoho z bodů se změní celá plocha, proto se často více plátů spojuje dohromady. Pro spojitost $G^{0}$ se musí rovnat řídící body na okrajích. Pro $G^{0}$ musí tečné vektory na okrajích být lineárně závislé.

Zobrazují se rekurzivním dělením (patch splitting). Využívá se algoritmu de Casteljau.

B-spline plochy

Aproximační plochy analogické B-spline křivkám, ale se dvěma parametry.

Jsou lepší pro modelování než Hermitovské nebo Bézierovy plochy, protože se lépe navazují, jelikož B-splajny stupně $k$ garantují spojitost $C^{k - 1}$ .
Změnou jednoho řídícího bodu nezměníme celou plochu, ale jen část.
Celá plocha leží v konvexním obalu řídících bodů.
Průchodu řídícím bodem lze dosáhnout zvýšením jeho násobnosti (a tak snížením spojitosti).
Invariantní k lineárním transformacím.

NURBS plochy: Standard v průmyslovém modelování. Umožňují definovat velké množstí ploch: free-form surfaces, plochy založené na přímkách a kuželosečkách, atd. [13] Jsou invariantní k lineárním transformacím i k perspektivní projekci.

$S (u, v) = i = 1 \sum k j = 1 \sum l R_{i, j} (u, v) P_{i, j}$

kde $P_{i, j}$ jsou řídící body a $R_{i, j} (u, v)$ jsou NURBS bázové funkce:

$R_{i, j} (u, v) = \frac{N _{i, n} ( u ) N _{j, m} ( v ) w _{i, j}}{\sum _{p = 1}^{k} \sum _{q = 1}^{l} N _{p, n} ( u ) N _{q, m} ( v ) w _{p, q}}$

$N_{i, n} (u)$ a $N_{j, m} (v)$ jsou B-spline bázové funkce stupně $n$ a $m$ . $w_{i, j}$ jsou váhy.

Tip	NURBS plochy se využívají v modelovací technice sweeping (šablonování), kdy se množina bodů pohybuje (posunuje, rotuje, …) prostorem za vniku tělesa. [14]

Surface subdivision / rekurzivní dělení polygonů

Polygonové povrchy dělíme v případě, kdy chceme je zjemnit, vyhladit.

Pravidla dělení

Dělení dodržují nějaké pravidlo.

Topologická pravidla: udávají vztahy pro generování nových vrcholů, hran, atd. z topologie objektu.
Geometrická pravidla: generují nové vrcholy, hrany, atd. na základě intepolací sousedních vrcholů.

Extraordinary vertices / mimořádné vrcholy

Vrcholy, které mají jiný počet sousedů (valenci) než ostatní vrcholy.

4-point scheme

Interpolace $C^{1}$ křivkou.

Catmull-Clark

Aproximuje původní mesh. Zachovává $C^{2}$ , na mimořádných bodech ale jen $C^{1}$ . Po první iteraci vždy vznikou quady. Založený na bikubických uniformních B-splinech.

Doo-Sabin

Aproximuje původní mesh. Narozdíl od Catmull-Clark je založený na bikvadratických uniformních B-splinech.

Loop

Aproximuje původní mesh. Funguje jen na trojúhelníkové síti.

Butterfly

Interpoluje původní mesh. Funguje jen na trojúhelníkové síti.

Zdroje

[1] Byška, Furmanová, Kozlíková, Trtík: PA010 Intermediate Computer Graphics (podzim 2021)
[2] Sochor: PA010 Intermediate Computer Graphics (podzim 2020)
[3] Sochor: PB009 Principles of Computer Graphics (jaro 2019)
[4] Wikipedia: Smoothness
[5] Jaakko Kurhila and Matti Mäkelä: Parametric Curves
[6] Geometric Continuity of Parametric Curves: Three Equivalent Characterizations
[7] Wikipedia: Lagrange polynomial
[8] Wikipedia: B-spline
[9] Wikipedia: Cubic Hermite spline
[10] ČVUT: Ferguson curve
[11] ČVUT: Coons curve
[12] Wikipedia: Coons patch
[13] Wikipedia: Non-uniform rational B-spline
[14] Wikipedia: Solid modeling
[15] Wikipedia: Horner’s method