algorithmus: voxel ermitteln/bestimmen/suchen

[ecutioner]

Hallo

Ich will einen Algorithmus schreiben, der mir sagt ob einen Punkt (x y z) im drei-demensionalenraum sich innerhalb vier Linien bzw. innerhalb einer Pyramide befindet. s. Anhang/bild.

jede Linie ist beschrieben durch ihre Voxelnposition d.h ich habe 4 Arrays, wo in jede Array die voxeln von der linie gespeichert sind.

z.B [X1 Y1 Z1] % voxel-array für linie 1

X1(1)= 0 Y1(1)=0 Z1(1)=0

X1(2)= 0 Y1(2)=1 Z1(2)=1

...

...

...

X1(70)= 75 Y1(70)=75 Z1(70)=75

hat jmd eine Idee wie ich das Algorithmus realisieren kann?

im schlimmsten fall muss ich alle voxeln, die sich innerhalb der pyramide befinden, ermitteln und in einem array speichern. und dann über diesen Array iterieren, ich weiß aber trotzdem nciht wie ich die voxeln ermitteln soll und diese methode wird auch höchstwahrscheinlich zeit und rechenaufwändig sein.

ich hoffe ich habe mich gut ausgedrückt. Ich bin für jede Idee dankbar.

danke im Vorraus.

[flashpixx]

Da Du ja im realen keinen unendlichen Vektorraum hast, sondern dieser durch die 3 Geraden und die max. Höhe / Breite / Tiefe des Bildraumes begrenzt sind, kannst Du das als konvexes Polygon auffassen und musst nur prüfen, ob ein Punkt innerhalb des Polygons liegt. Je nach Anwendung braucht man das auch nicht in R^3 berechnen, sondern kann das nach R^2 projizieren und mit die Berechnung mit baryzentrischen Koordinaten durchführen

[Mcolli]

Junge Junge,

das ist mal was wo man länger über das Vorgehen als über die Formulierung nachdenken muss, und der flashpixx hat sich auch schon was überlegt

Aus mathematischer Sicht denke ich, dass flashpixx da richtig liegt und Du mit der Projekttion deiner Geraden rechnen kannst.

Die Genauigkeit bei der Rechnung sollte meiner Meinung aber deutlich geringer als vermutet sein, da Du das ganze ja bestimmt auf einem Bildschirm darstellen willst un es so nur auf 1 Pixel Genauigkeit ankommt da, 0,1 Pixel ja nicht darstelllbar sind.

Bei dieser Aussage gehe ich davon aus, dass Du, wie bei Voxel wohl üblich, keine Farbkorrekturen der Pixel à là AA machen willst. (ich kenn mich da aber nur "Bild-Leser" mäßig aus)

[lilith2k3]

IDa Du ja im realen keinen unendlichen Vektorraum hast, sondern dieser durch die 3 Geraden und die max. Höhe / Breite / Tiefe des Bildraumes begrenzt sind, kannst Du das als konvexes Polygon auffassen und musst nur prüfen, ob ein Punkt innerhalb des Polygons liegt. Je nach Anwendung braucht man das auch nicht in R^3 berechnen, sondern kann das nach R^2 projizieren und mit die Berechnung mit baryzentrischen Koordinaten durchführench will einen Algorithmus schreiben, der mir sagt ob einen Punkt (x y z) im drei-demensionalenraum sich innerhalb vier Linien bzw

Prinzipiell hast Du recht, dass sich zwar das dreidimensionale für den Anwendungsfall in ein zweidimensionales Problem überführen lässt. Nur ist dann die Frage, ob es nicht einfacher ist, es für den dreidimensionalen Raum auszurechnen und in die Ebene zu projezieren.

[M.A.Knapp]

@ecutioner: Was genau willst du machen ? Um was für Daten handelt es sich ?

Punktwolke ? Reguläres Volumen ?

[ecutioner]

als erstes muss ich euch für die schnelle antwort danken und entschuldige mich für das späte antwort.

Also es geht um volumentomographie. Man will versuchen die Bildgebende verfahren in der Medizin zu verbessern und vor allem zu beschleunigen um z.B chemikalische abläufe in irgendeiine Gewebe zu beobachten.

solche abläufe können so schnell sein dass jede milli-sekunde gold wert ist. Von jedem Voxel der vom Strahl getroffen wird muss das volumen berechnet werden Bsp.: Vges= V/2 wenn der Voxel in der mitte getroffen wird usw. damit der "volumenberechner" kein zeit, mit Voxeln die nicht vom Strahl getroffen werden, verliert, soll dieser algorithmus helfen zu sagen welche Voxeln vom körper genau vom LichStrahl getroffen werden, dieser algorithmus ist so zusagen nur ein puzzelstück.

zum Alg.:

ich hab mich mit flashpixx´s Methode befasst, und muss echt sagen das war ein sehr sehr guter denkanstoß.

[M.A.Knapp]

Ah, wunderbar ... sowas ist eh mein Brotberuf ... mache SW-Entwicklung im PACS Bereich (komplett alles von Netzwerkkommunikation über Userinterface bis zum 3D Volume Renderer)

Willst du alle Voxel innerhalb der Pyramide verarbeiten oder

brauchst du nur einen Test um festzustellen, ob ein Voxel innerhalb der Pyramide liegt ?

[flashpixx]

Von jedem Voxel der vom Strahl getroffen wird muss das volumen berechnet werden Bsp.: Vges= V/2 wenn der Voxel in der mitte getroffen wird usw. damit der "volumenberechner" kein zeit, mit Voxeln die nicht vom Strahl getroffen werden, [...]

ich verweise hier einmal auf entsprechende Algorithmen aus der Computergraphik im Bereich Rendering. Da Du eine feste Strahlenquelle hast, die im Grunde aussendet und Du hier Schnitte berechnen musst, kannst Du je nach Voraussetzung auch nur die Punkte berechnen, die überhaupt relevant sind, d.h. z.B. Punkte die "verdeckt" sind fallen schon mal raus. Entsprechende Datenstrukturen sind kd-Trees, um sehr effizient zu testen, ob überhaupt berechnet werden muss.

Zusätzlich solltest Du Dir auch überlegen, welche Zusammenhänge existieren, denn gerade wenn man im Bereich eines Raytracings arbeitet, würde sich eine direkte Parallelisierung des Datenraumes ergeben, wobei man Performance via Pipelining des GPUs, CPU Parallelisierung (MPI, MPICH2) oder beides in Kombination (OpenCL) erreichen kann.

[...] verliert, soll dieser algorithmus helfen zu sagen welche Voxeln vom körper genau vom LichStrahl getroffen werden, dieser algorithmus ist so zusagen nur ein puzzelstück.

Das ist im Grunde nur entsprechendes Raytracing. Denn Du hast einen Strahl und willst wissen, ob ein Schnitt mit einem Objekt bzw. dessen Oberfläche vorliegt. Wobei hier natürlich direkt sich eine entsprechende Diskretisierung des Objektes ergeben muss.

ich hab mich mit flashpixx´s Methode befasst, und muss echt sagen das war ein sehr sehr guter denkanstoß.

Dieser erste Ansatz beruht im Grunde nur auf den konvexen Mengen und eben deren Definition bezüglich Strecken innerhalb. Je nach Anwendung und Datengrundlage wäre auch zu überlegen, ob man eben zu Algorithmen bezügl. der Konvexe Hülle ? Wikipedia greift.

[M.A.Knapp]

Wenn du alle Voxel verarbeiten möchtest:

Der Mittelstrahl der Pyramide dient als bestimmung der Hauptrichtung (X, Y oder Z), dann bestimmst du den Schnittpunkt der Pyramide mit jeder Voxel-Ebene normal zur Hauptrichtung und verarbeitest die Voxel wie in einem 2D Array (Randvoxel brauchen ein bißl Sonderbehandlung), sollte in Summe doch recht flott gehen.

[flashpixx]

@M.A.Knapp: Würde ich bei größeren Datenmengen nicht mehr so naiv machen. Ich würde da dann wohl zu kd-Tree mit Frustrum-Culling bzw zum testen inverse-frustrum-clulling gegen die Splittingplane verwenden. Lässt sich auch sehr schön via SIMD parallelisieren

[M.A.Knapp]

@M.A.Knapp: Würde ich bei größeren Datenmengen nicht mehr so naiv machen. Ich würde da dann wohl zu kd-Tree mit Frustrum-Culling bzw zum testen inverse-frustrum-clulling gegen die Splittingplane verwenden. Lässt sich auch sehr schön via SIMD parallelisieren

Hängt von der Größe der Daten ab ... wenns nur ein 1024^3 x 16bit Volumen ist, dann geht sicher eine Brute-Force Methode - alle Voxel der Pyramide zu verarbeiten - auch noch recht schnell.

Ist die Frage, ob der Overhead für einen Octree geringer ist, als wenn man eine jede Voxel-Ebene mit 4 Strahlen schneidet, da man, wenn man die Schnittpunkte der Pyramide mit einer Voxelebene kennt, kann man relativ leicht die Positition der anderen Voxel im 2D berechnen.

Bearbeitet 6. November 2010 von M.A.Knapp

[ecutioner]

Willst du alle Voxel innerhalb der Pyramide verarbeiten oder

brauchst du nur einen Test um festzustellen, ob ein Voxel innerhalb der Pyramide liegt ?

Nein ich brauche nur einen Test um festzustellen, ob ein Voxel innerhalb der Pyramide liegt?

ich verweise hier einmal auf entsprechende Algorithmen aus der Computergraphik im Bereich Rendering. Da Du eine feste Strahlenquelle hast, die im Grunde aussendet und Du hier Schnitte berechnen musst, kannst Du je nach Voraussetzung auch nur die Punkte berechnen, die überhaupt relevant sind, d.h. z.B. Punkte die "verdeckt" sind fallen schon mal raus.

welchen Algorthmus "aus der Computergraphik im Bereich Rendering" meinst du genau??

Die Strahlenquelle ist nicht fest sondern variable. die Position bekommt der Alg. als input/parameter.

Mit "verdeckt" meinst du schon punkte die voll bestrahlt werden oder? die braucht man aber auch, sie werden dann in eine andere liste gespeichert.

Das ist im Grunde nur entsprechendes Raytracing. Denn Du hast einen Strahl und willst wissen, ob ein Schnitt mit einem Objekt bzw. dessen Oberfläche vorliegt. Wobei hier natürlich direkt sich eine entsprechende Diskretisierung des Objektes ergeben muss.

ich habe ein anderes verfahren benutzt und zwar der Bresenham 3d algorithmus. Ich kenne nämlich den endpunkt bzw. ich weiß wo der licht endet (dioden-chip) das endpunkt/endposition ist bekannt. Ausserdem ist das licht, was beispielsweiße von der röntgenröhre rauskommt, kein wirkliches strahl ehe eine "fläche" z.B pyramidenstrahl oder kegelstrahl.

[flashpixx]

ich habe ein anderes verfahren benutzt und zwar der Bresenham 3d algorithmus.

Das ist ein Algorithmus um eine Linie zwischen zwei Punkten zu zeichnen, d.h. eigentlich um sie als diskrete Punkte zu zeichnen, sprich es ist ein Rasterisierungsalgorithmus

Ausserdem ist das licht, was beispielsweiße von der röntgenröhre rauskommt, kein wirkliches strahl ehe eine "fläche" z.B pyramidenstrahl oder kegelstrahl.

Deswegen mein Hinweis auf Frustrum-Culling, denn dies ist genau das Verfahren, was diesem exakt entspricht. Du hast einen Ausgangspunkt und mit der Entfernung von diesem entwickelt sich das ganze direkt pyramidal. In Verbindung mit kd-Trees ist das Verfahren sehr effizient bezugl. der Schnittpunktberechnung zwischen Frustrum und einem Objekt.

Mit "verdeckt" meinst du schon punkte die voll bestrahlt werden oder? die braucht man aber auch, sie werden dann in eine andere liste gespeichert.

Dies entspricht einer weiteren Traversierung des kd-Trees, da innerhalb des Trees Objekte, die zuerst durch den Strahl geschnitten werden, als erstes geliefert werden.

Wenn die Objekte innerhalb des Trees für alle Strahlenpositionen gleich sind und sich immer nur die Strahlenposition verändert, dann musst Du nur einmal den Tree aufbauen und kannst bei entsprechender Umsetzung als Multithread oder CPU-orientiert den Baum mit mehreren Strahlenquellen verarbeiten.

[ecutioner]

Ich bedanke mich schon mal für die vielen infos ^^ Ich werde mich mit raytracing, KDtrees intensiv auseinander setzen und falls ich noch fragen habe werde ich auf euch zurückkommen ^^

vielen dank nochmal