Triangulacia povrchu na 3d point cloude

S.T.E.A.L.T.H

Zdravim,
mam nasledujuci problem a po par dnoch googlenia si uz neviem rady.
Ako uz nazov temy vravi, potrebujem 3d point cloud popisat polygonalnou mriezkou z trojuholnikov. Snazim sa na to najst nejaku kniznicu/funkciu pre python, no zatial marne, nakolko potrebujem aby to bolo fakt dost rychle.
3d point cloud, ktory potrebujem triangulovat je na obrazku 1.
Ako prve som skusal pouzit Delaunay triangulaciu implementovanu v kniznicy scipy. V skratke asi takyto nejaky kod:

Kód: Vybrať všetko

import numpy as np
from scipy.spatial import Delaunay
points = np.array([[x, y, z]...])
tri = Delaunay(points)
indices = tri.simplices
vertices = points[indices]

V tomto pripade som z toho samozrejme dostal len tetrahedrony, tak som skusil nieco ine.

Kód: Vybrať všetko

import numpy as np
from scipy.spatial import Delaunay
points = np.array([[x, y, z]...])
tri = Delaunay(points)
vertices = points[tri.convex_hull]

Tu som sa posunul uz dalej, nakolko v tomto pripade uz dostanem trojuholniky. Vsetko je v pohode, pokial je objekt konvexny (jedna z gul na obrazku v point cloude). Ak ale potrebujem nejaky objekt, ktory je konkavny (konkretne priklad obrazok 1), tak dostanem z toho to co je na obrazku 2. To ale nechcem, ja chcem jednoducho pospajat tie body do trojuholnikov.

Najnovsie som skusal aj python-pcl, prepojenie Ckoveho PCL Library s Pythonom, ale tam nie je takmer nic a dokumentacia miziva

, takze som sa nikam nedostal.

Ak by niekto vedel co s tym alebo mal nejaky napad a chcel by to oskusat, budem vdacny. Cloud je v prilohe cloud.dat.tar.gz

Dakujem za kazdy napad

harrison314

Ty chces spravit konvexnu obalku niecoho co nie je konvexne a to je probem.

Prve co ma naladlo je vypocitat tazisko bodov, do tohto taziska umiestnis rovinu, na ktoru premietnes vsteky body co su nad nou, a v 2d spravis trianguulaciu, potom to iste s bodmi pod nou, a tieto triangulacie prensies do 3d, ale fakt neviem.

Potom evolucne algoritmy a budes sa snazit minimalizovat/maximalizovat objem, ale to nie je prave richle.

PS: ber to ako rypanie

ale ked to chces richle preco pouzivas pyton?

S.T.E.A.L.T.H

Prvotna myslienka ma zaujala (s tym prenesenim do roviny), tak som to skusil, ale dostal som to co vidis na obrazku. Uz rozmyslam len nad tym, ze sa budem musiet pozriet na PCL kniznicu pre C++ a spojit to s pythonom.
Btw, mne je jasne, ze som sa snazil dostat konvex z niecoho co konvexne nie je, ale skusal som. Scipy a ta triangulacia tam nema moznost concave_hull, len convex
P.S.
Preco python? Lebo sa mi v tom dobre programuje

V skratke asi tak, ze sa mi globalne lepsie programuje v interpretovacich jazykoch. Prvotna myslienka bola, robit to v C++, ale az tak s nim kamarat nie som.

harrison314

S.T.E.A.L.T.H napísal:Prvotna myslienka ma zaujala (s tym prenesenim do roviny), tak som to skusil, ale dostal som to co vidis na obrazku. Uz rozmyslam len nad tym, ze sa budem musiet pozriet na PCL kniznicu pre C++ a spojit to s pythonom.

To na tom obrazku to vyzera ako cisto 2d. Ja som to myslel tak, ze v 2d si urcis medzi ktorimi bodmi budu hrany, ale vykteslis ich uz v 3d, v prietore pôvodnych bodov.

Problem je v tom, ze deterministicky algoritmom nedokaze urcit, ktore body treba pospajat pokial objekt nie je konvexny, moze to len odhadnut, to ti je dufam jasne.

Ale napadlo ma, ze mozno na to pristupujes zle, ale to je tym ze neviem kontext, mozno treba zvolit inu reprezentaciu daneho objektu, napriklad volumetricku, s tym sa uz da nieco robit, ja som na to robil projekt v OpenGL..

S.T.E.A.L.T.H

Jj, na tom obrazku je 2d, lebo mne pri tom napadlo, ze ak by to tirangulovalo v 2d, tak do 3d to viem vytoahnut tak, ze len pridam z suradnicu, ale informacia o tom, ktore body maju byt spojene uz mam, no, kedze ide o konvexnu vec, tak to spojilo ako to spojilo.
A background za tym je taky, ze mam funkciu popisujucu tvar telesa a ja ho potrebujem pokryt trojuholnikmi, aby som nasledne vedel zratat intenzitu ziarenia z viditelneho povrchu.

harrison314

S.T.E.A.L.T.H napísal:A background za tym je taky, ze mam funkciu popisujucu tvar telesa a ja ho potrebujem pokryt trojuholnikmi, aby som nasledne vedel zratat intenzitu ziarenia z viditelneho povrchu.

Vies pre kazdy bod v priestore povedat, ci sa nachdza v nutri telesa? Ak hej, skus najst nejake algoritmy pre zobrzazovanie volumetrickych dat, mnohe dokazu previest takuto reprezentaciu do klasickych polygonov.

S.T.E.A.L.T.H

Jj, to viem povedat, nakolko mam implicitnu funkciu, ktora to teleso popisuje. Nakoniec som to ale vyriesil tak, ze som pouzil PCL kniznicu pre C++. Spravim to tak, ze budem spustat binarku z pythonu a s vystupom, ktore mi da C++ budem pracovat dalej. No aj tak dakujem za snahu a rady

//autoeditácia príspevku (13 Jan 2015, 11:05)
Obnovym trocha tuto temu.
Pouzil som na tento problem ako som pisal PCL, ale riesenie nebolo nakoniec vo vsetkych pripadoch stopercentne, ba dokonca spravilo to viac neuplnych triangulacii ako uplnych a to si nemozem v mojom probleme dovolit. Od vtedy som to ale neriesil a fungoval som dalej s konvexnymi telesami a tam ide bez problemov delaunayova triangulacia. Ked som sa po dlhsom case k tomuto problemu trosku vratil, napadlo mi, ci nie je nejako mozne vytvorit polygonalnu trojuholnikovu mriezku ak mam problem definovany implicitnou funkciou vo sferickych suradniciach, kde je dany povrch definvany zadanim azimutalneho a polarneho uhla s dopocitanim polomeru?

Runes

Chlopi zacal som riesit podobny problem

mam napr 1 2 3 kamery, zatial uvazujem ze by mali stacit dve

tieto dve kamery sa kukaju na teleso pred nimi obe su rovnako smerovane len su od seba cize dajme tomu stereovizia. Chcem zistit vzdialenost tohoto telesa teda hociktoreho bodu ktory si urcim. Malo by to ist triangulaciou ale nedari sa mi najst daky vypocet ako na to daky rieseny priklad. Neviete o dacom ?

harrison314

Pozri si ako to riesi kinekt.

S.T.E.A.L.T.H

Nakoniec sa mi už dosť dávno podarilo nájsť riešenie, ale zabudol som to sem napísať. Toto vyriešilo moje trápenie.
CGAL Surface Reconstruction from Point Sets

Triangulacia povrchu na 3d point cloude

Triangulacia povrchu na 3d point cloude

Re: Triangulacia povrchu na 3d point cloude

Re: Triangulacia povrchu na 3d point cloude

Re: Triangulacia povrchu na 3d point cloude

Re: Triangulacia povrchu na 3d point cloude

Re: Triangulacia povrchu na 3d point cloude

Re: Triangulacia povrchu na 3d point cloude

Re: Triangulacia povrchu na 3d point cloude

Re: Triangulacia povrchu na 3d point cloude

Re: Triangulacia povrchu na 3d point cloude