Nacházíte se zde: Rhino3D.cz > Články > Zásuvné moduly > Rekonstrukce množiny bodů

Rekonstrukce množiny bodů

Publikováno: 24.11.2006 | Autor: David Rutten | Rubrika: Zásuvné moduly | Komentáře: 6 - Doporučit

Rekonstrukce množiny bodůRekonstrukce množiny bodů (Poinset Reconstruction, zkráceně PSR) je proces tvorby geometrie vyšší úrovně z obyčejných bodů. Nejčastěji se ní setkáte ve strojírenství při skenování objektů laserovým scannerem, ale poměrně časté je i využití v geodezii a architektuře, kde máte k dispozici vyměřený terén v podobě prostorových bodů a potřebujete z nich udělat souvislou polygonovou síť.

Stáhněte si nejnovější instalaci zásuvného modulu PointSetReconstruction, který běží v betaverzi Rhina z 15. listopadu 2006. O případných nových verzích, překompilovaných pro novější bety Rhina, vás budeme informovat v Atualitách na hlavní stránce tohoto serveru.

Kontaktujte Davida Ruttena, autora tohoto zásuvného modulu.

Co je to rekonstrukce množiny bodů?

Rekonstrukce množiny bodů (Poinset Reconstruction, zkráceně PSR) je proces tvorby geometrie vyšší úrovně z obyčejných bodů. Existuje mnoho algoritmů, které lze sdružit pod tuto hlavičku a tento zásuvný modul implementuje některé z nich. Nejznámějšími příklady jsou Delaunayovy sítě a Voronoiovy diagramy:

První obrázek představuje Delaunayovu triangulaci množiny neuspořádaných bodů. Druhý obrázek znázorňuje Voronoiovo dělení 2D prostoru, reprezentovaného mrakem bodů.

Příkazy

Tento zásuvný modul nabízí několik příkazů, jejich počet se bude doufám neustále zvyšovat. Většina příkazů sdílí společné rozhraní a postup práce:

  • vyberte vstupní geometrii
  • změňte volby
  • vložte řešení
Jako vstupní geometrii můžete vybrat jakékoliv množství bodů, mraků bodů, křivek a nebo sítí. Pokud vyberete křivky, budete vyzváni k zadání hodnoty dělení, která bude použita pro vzorkování křivek. Křivky jsou také vždy vzorkovány ve svách zlomech. Po výběru vstupních křivek buď příkaz dokončí svoji činnost, pokud neobsahuje žádné volby, nebo vykreslí náhled výsledku a nabídne vám možnost měnit pomocí myši volby v příkazovém řádku. Některé volby mohou způsobit neplatný výsledek, v takovém případě bude muset být přepočítán. To je potenciálně velice náročná operace, ale tyto procesy můžete vždy přerušit stiskem klávesy Esc.

K dispozici máte tyto příkazy:

* Nenabízí žádné příkazové volby

Delaunay

Delaunayova triangulace je 2.5rozměrný proces prokládání trojúhelníků neorganizovanými body tak, aby ve výsledné síti nezůstaly žádné otvory. Na výstupu je vždy polygonová síť (nikoliv NURBS plocha) a tento algoritmus neumí zacházet s překrytím bodů v z-ové ose. Síť lze vybarvit pomocí několika dostupných stínovacích algoritmů (viz. níže). Tyto barvy přetrvají i po vložení sítě do scény.

  • Terrain » aplikuje standardní barvy, asociované s terénem. Musíte specifikovat výšku mořské hladiny a to, zda je terén osvětlen z nějakého směru (na rozdíl od ambientního osvětlení).
  • Slope » nejstrmější oblasti jsou označeny zeleně a nejplošší žlutě. Gradient je poté roztažen tak, aby odrážel celý rozsah strmosti sítě.
  • Deviation » tento shader lze použít pro odhad přesnosti vodicích ploch. Musíte zadat hodnotu odchylky (standardně 20%) a všechny vrcholy, které přesáhnou tuto vzdálenost, budou obarveny červeně nebo žlutě. Odchylka je měřena jako procento maximální odchylky.
  • UVW ^ XYZ » tyto shadery jednoduše mapují červené, zelené a modré komponenty vrcholu na jeho relativní pozici v UVW nebo XYZ obálkovém kvádru celé množiny bodů.
  • Texture » tento shader lze použít pro kontrolu distribuce (u,v) souřadnic pro mapování textur ve výstupní síti. Dobže vyvážená šachovnice indikuje vhodnou volbu vodicí plochy. Tato textura není 'zapečena' do výsledné síti, to znamená, že při vložení geometrie do scény bude ztracena.
  • Occupancy » tento shader obarví vrcholy sítě na základě počtu sbíhajících se vrcholů. Pokud existují velké oblasti červeno - fialových vrcholů, pak aktuální vodicí plocha těžce deformuje projekci.

Pokud jsou body organizovány (pokud leží v mřížce nebo na kružnici), může řešení selhat. V takovém případě musíte zvýšit šum vzorkování (sampling noise). Dlaším rizikem jsou překrývající se body. Pokud v jakémkoliv vertikálním směru nad sebou existuje více než jeden bod, bude výsledkem delaunayova algoritmu nesmysl:

Výše uvedené obrázky ukazují výchozí triangulaci téměř uzavřené koule bodů. Protože je delaunayova trianglace 2D proces, propojí body na spodku koule s body na vrcholu koule. U těchto případů nevhodně uspořádaných bodů lze někdy použít projekční vodicí plochu. Tato plocha převzorkuje body pomocí pokročilejších projekčních algoritmů, jako jsou zarovnané roviny, koule, NURBS plochy nebo hyperbolické singularity. Pokud na tento mrak bodů použijeme hyperbolické vodítko, může být plocha vytvořena správně:

Vodicí plochy lze vybrat z voleb v příkazovém řádku v průběhu vykonávání příkazu. Některá vodítka vycházejí z existující geometrie a některá jsou čistě virtuální.

Voronoi

Voronoiovo členění spočívá v rozdělení prostoru na jednotlivé buňky, přičemž každá buňka obsahuje všechny možné souřadnice, které jsou blíže lokálnímu bodu než jakýkoliv jiný bod v této množině. Tato metoda obvykle vede k velice přirozenému rozdělení prostoru; k podobnému, jaké vidíte u nahromaděných mýdlových bublin. Voronoiovy diagramy také trpí na organizovaná vstupní data, pro potlačení neplatných řešením proto mohou potřebovat šum.

Voronoiovy diagramy podporují vodicí plochy a řešení bude promítnuto zpět na plochu:


Voronoiův diagram s prázdným vodítkem


Stejný Voronoiův diagram s vodicí plochou

Pro voronoiův algoritmus jsou dostupné tyto shadery, ale barvy nejsou trvalé - nejsou vloženy do výsledného modelu. Výstupem je skupina uzavřených lomených čar, z nichž každá představuje jednu voronoiovu buňku. K dispozici máte tyto shadery:

  • Random » každé buňce přiřadí náhodnou barvu.
  • Area » barevný gradient přiřadí na základě obsahu buněk.
  • Circumference » barevný gradient přiřadí na základě obvodu buněk.
  • Asymmetry » barevný gradient přiřadí na základě blízkosti buňky k hranici děleno diagonálou obálkového kvádru buňky. Tento shader můžete využít pro indikaci nepravidelně dostribuovaných oblastí ve voronoiově řešení. Zcela uvolněné voronoiovo řešení má tendenci tvořit hexagonální buňky s body umístěnými uprostřed.

3DVoronoi

Trojrozměrné Voronoiovo členění prostoru je podobné jako 2D Voronoiovy diagramy. Tento příkaz je ve velice raném stádiu a proto při jeho používání doporučuji zvýšenou obezřetnost. Před spuštěním tohoto příkazu si model vždy uložte. Tento příkaz momentálně nemá žádné volby.

OcTree

Členění OcTree rozděluje prostor na jednotlivé bloky, kde každý blok (krychle) obsahuje určitý počet bodů z původního mraku bodů a všechny krychle dohromady obsahují všechny body. Krychle jsou děleny tehdy, když obsahují více než N bodů nebo když přesáhnou určitý objem nebo jinou prahovou hodnotu:

Pro řízení metody dělení máte k dispozici několik voleb:

  • Sample Threshold » kdykoliv krychle obsahuje více než tuto prahovou hodnotu bodů, bude rozdělena na 8 menších krychlí. Výchozí hodnota je 1, ale vyšší čísla sníží výpočetní čas.
  • Volume threshold » kdykoliv je krychle větší než určitý počet kubických jednotek, bude rozdělena na 8 menších krychlí. Implicitně je objemové dělení vypnuté.

V závislosti na aktivní prahové hodnotě jsou zde další volby:

  • PreventSampleUnderrun » když je tato hodnota aktivní, zabrání dělení krychlí, které jsou větší než 'Volume Threshold', pokud obsahují méně než 'Sample Threshold' bodů.
  • PreventVolumeUnderrun » když je tato hodnota aktivní, zabrání dělení krychlí, které obsahují více než 'Sample Threshold' bodů, pokud je jejich objem menší než 'Volume threshold'.

OcTrees podporují vodicí plochy a výsledné krychle budou promítnuty zpět na vodicí plochu tak, aby reflektovaly vnitřní schéma dělení:

QuadTree

Členění QuadTree rozděluje plochu na jednotlivé čtverce, kde každý čtverec obsahuje určitý počet bodů z původního mraku bodů a všechny čtverce dohromady obsahují všechny body. Čtverce jsou děleny tehdy, když obsahují více než N bodů nebo když přesáhnou určitý obsah nebo jinou prahovou hodnotu:

Pro řízení metody dělení máte k dispozici několik voleb:

  • Sample Threshold » kdykoliv krychle obsahuje více než tuto prahovou hodnotu bodů, bude rozdělena na 8 menších krychlí. Výchozí hodnota je 1, ale vyšší čísla sníží výpočetní čas.
  • Area threshold » kdykoliv je čtverec větší než určitý počet plošných jednotek, bude rozdělen na 4 menší čtverce. Implicitně je plošné dělení vypnuté..

Depending on which threshold values are active there are two additional options:

  • PreventSampleUnderrun » když je tato hodnota aktivní, zabrání dělení čtverců, které jsou větší než 'Area Threshold', pokud obsahují méně než 'Sample Threshold' bodů.
  • PreventAreaUnderrun » když je tato hodnota aktivní, zabrání dělení čtverců, obsahují více než 'Sample Threshold' bodů, pokud jsou menší než 'Area threshold'.

Octrees a "QuadTrees" používají stejné shaderové rutiny:

  • Random » přiřadí kvádrům náhodnou barvu.
  • Volume » přiřazuje barvy na základě objemového gradientu (to je pro QuadTrees bezcenné, protože všechny větve stromu mají nulový objem).
  • Area » přiřadí barvy na základě gradientu obsahu plochy.
  • Recursion » přiřadí barvy na základě hloubky dělení.

QuadTrees podporují vodicí plochy a výsledné čtverce budou promítnuty zpět na vodicí plochu tak, aby reflektovaly vnitřní schéma dělení::

Spanning Circles (proložené kružnice) a Convex Hulls (konvexní obálky)

Proložené kružnice a konvexní obálky jsou způsoby, jak zapouzdřit body. Tyto příkazy v současnosti nenabízí žádné volby. Výsledky vidíte níže:

Diskuse k článku

  • [6] Jan Slanina – 03. 02. 2007, 10:08 – reakce na [5]

    reagovat

    Ten návod na RhinoScript vycházel na našem serveru česky (http://www.rhino3d.cz/vyhledavani.html?keyw=rhino script) ale není úplně dokončenej, protože na to byl prakticky nulovej ohlas. Mnohem novější manuál ke skriptování (v angličtině) od Davida je na http://en.wiki.mcneel.com/default.aspx/McNeel/Rhin oScript101

  • [5] JJJ – 02. 02. 2007, 17:21

    Reaguje: [6] - reagovat

    Na strance Davida Ruttena http://www.reconstructivism.net/ je take strucny uvod do Rhino scriptu (anglicky)

  • [4] manca – 10. 12. 2006, 00:00 – reakce na [3]

    reagovat

    dobry, to uz beha
    jenom upozorneni, Esc to cancel nefunguje, tzn, kdyz se toho zada moc > bud schodit rhino, nebo se sesype comp >>>> ukladejte!!!!!!

  • [3] Jan Slanina – 01. 12. 2006, 13:38 – reakce na [2]

    Reaguje: [4] - reagovat

    Ten soubor *.rhp co si stáhneš si musíš nakopírovat do adresáře Plug-Ins v Rhinu 4 a pak v Rhinu spoustit pomocí menu Nástroje > Volby okno Volby Rhina. Zapneš si panel Zásuvné moduly, ukáže se seznam zásuvných modulů. Klikneš na Instalovat, vyhledáš ten soubor *.rhp, co jsi ho uložil do adresáře Plug-ins a nainstaluješ ho.

  • [2] manca – 29. 11. 2006, 23:02

    Reaguje: [3] - reagovat

    super clanek, akorat ta aplikace z 15.11. neni valid win32 application
    co s tim muzu delat?

  • [1] veduuu – 27. 11. 2006, 11:37

    reagovat

    vynikajúci článok.S tvorbou terénu som mal vždy problémy, či to bolo v rhine alebo iných programoch.Zo sásuvnými modelovacími modulmi ako tieto a rendrovacími ako V-Ray sa Rhino pomaly ale iste stane číslom jedna na trhu.
    Ďakujem.