Kollisionserkennung zwischen Punktwolken und/oder Dreiecksnetzen

[jonas93]

Hallo zusammen,

bevor ich anfange zu programmieren wollte ich mich hier noch einmal nach anderen Meinungen oder Tipps umhören.

Ich möchte berechnen, ob und wo zwei Objekte kollieren. Die Objekte bewegen sich nicht und sind auch nicht deformierbar (statische Szene, Rechenzeit erstmal nicht relevant).

Objekt A: 3D-Punktwolke
Objekt B: Dreiecksmesh bzw. CAD-Datei

Lösungsansätze:
1)Konvertieren → zwei Punktwolken → mit Raumpartitionierungsverfahren ermitteln, welche Punkte aus Objekt A in der Nähe von Punkten aus Objekt B sind (dann braucht man auch die Oberflächennormalen der einzelnen Punkte um zu bestimmen, ob ein Punkt aus der anderen Wolke innerhalb oder außerhalb liegt..)

2)Konvertieren → zwei Dreiecksnetze → Kollisionserkennung über Bounding Volume Hierachies, dazu wollte ich das Rad nicht neu erfinden und gerne Bibliotheken wie die OpenDynamicsEngine oder Bullet o.Ä. nutzen

Was würdet ihr bevorzugen? Gibt es noch (einfache) Alternativen, auf die ich bisher nicht gekommen bin? Hat jemand Erfahrung mit den genannten Engines?

Gruß
Jonas

[dot]

Was genau definierst du dabei als Kollision der Punktwolke mit dem Mesh? Wenn ein Punkt genau auf einem Polygon des Mesh zu liegen kommt? Wenn ein Punkt innerhalb des vom Mesh eingeschlossenen Volumens liegt? Falls Zweiteres: Wie genau definierst du den "Punkt" in dem die beiden kollidieren?

[jonas93]

Genau, ich möchte dann berechnen, ob ein Punkt der Punktwolke im vom Mesh umschlossenen Volumen liegt. Punkte in der Nähe (innerhalb gewisser Toleranz) einer Dreiecksfläche würde ich dann als Berührpunkte definieren. Punkte die weiter ins Volumen eindringen sind die, die ich auf jeden Fall finden möchte.

[dot]

Klingt für mich so, als wäre es sinnvoll, das Mesh in einen BSP-Baum zu zerlegen. Mit dem solltest du deine Tests effizient durchführen können...

[rapso]

wenn du nur rausfinden willst,ob ein punkt innerhalb des volumens des anderen meshes liegen, musst du lediglich von dem punkt aus einen ray bis ausserhalb das meshes definieren und zaehlen wie oft es das mesch schneidet. ist die anzahl gerade -> ausserhalb, bei ungerade -> innerhalb.

[jonas93]

Danke für eure Antworten und entschuldigt meine späte Rückmeldung. Ich habe nun zwei OBB-Bäume aus einer VTK-Klasse für die Meshes erstellt. Der Schnitttest zwischen den Blättern der beiden OBB-Bäume funktioniert auch bereits.

Für einen detaillierteren Schnitttest, also den zwischen Dreiecksflächen und nicht zwischen Hüllkörpern, brauche ich die Eckpunkte der Dreiecke und die Normalenvektoren.

Auf die x, y, z-Werte der Eckpunkte der Dreiecke in den kollidierenden Hüllkörpern kann ich mittlerweile zugreifen. Nur bei den Normalenvektoren komme ich ohne Hilfe nicht mehr weiter.

Ich lese eine STL mittels vtkSTLReader ein. In der STL sind die Eckpunkte und Normalen ja enthalen. Ich versuche nun aus einem vtkPolyData-Objekt die Normalen auszulesen:

vtkSmartPointer<vtkPolyData> pdata = vtkSmartPointer<vtkPolyData>::New();
	pdata->DeepCopy(reader2->GetOutput());
	std::cout << "Looking for cell normals..." << std::endl;

	// Count points
	vtkIdType numPoints = pdata->GetNumberOfPoints();
	std::cout << "There are " << numPoints << " points." << std::endl;

	// Count triangles
	vtkIdType numPolys = pdata->GetNumberOfPolys();
	std::cout << "There are " << numPolys << " polys." << std::endl;

	// Double normals in an array
	vtkDoubleArray* normalDataDouble = vtkDoubleArray::SafeDownCast(pdata->GetCellData()->GetNormals());

	if (normalDataDouble)
	{
		int nc = normalDataDouble->GetNumberOfTuples();
		std::cout << "There are " << nc
			<< " components in normalDataDouble" << std::endl;
	}

Die Anzahl der Punkte und Flächen wird korrekt ausgegeben, nur das Array mit den Normalen scheint leer zu sein.
Wie komme ich an die Normalenvektoren?

[rapso]

vielleicht ein bug im vtkSTLReader. setz ein breakpoint wo normalen gelesen werden sollen und pruefe was schiefgeht. (wie sollen wir herausfinden weshalb der reader deine datei ohne normalen ausgibt )