Octree problem

[Pellaeon]

hustbaer schrieb:

Nen Octree verwendet man normalerweise ja bloss um ein Set an Kandidaten zu ermitteln. Daher arbeitet man auch nicht mit Dreiecken sondern mit Bounding Boxen.
Und daher stellt sich das Problem mit Dreiecken auch nicht.

Würd ich so nicht sagen. Kommt halt drauf an, wofür man den Octree nimmt.

@blink: Das heir funktioniert bei mir wunderbar:
http://www.planet-source-code.com/vb/scripts/ShowCode.asp?txtCodeId=10317&lngWId=3

Musst dir mal anschauen. Das Prinzip geht aus dem Quellcode ganz gut hervor

[blinki]

@Pellaeon: wenn ich das so mache wie im Quellcode, ist es genau so, wie wenn ich nur überprüfen würde ob ein Eckpunkte vom Dreieck in der box ist, nämlich es sind immer noch die gleichen Dreiecke wo ich hindurch kann.

[krabbels]

Gast25250 schrieb:

Du musst einfach eine Referenz auf das Dreieck in jeder Zelle speichern, die vom Dreieck geschnitten wird.

Dann kann es aber passieren, dass du die selben Dreiecke mehrmals zeichnest.

[Pellaeon]

blinki schrieb:

@Pellaeon: wenn ich das so mache wie im Quellcode, ist es genau so, wie wenn ich nur überprüfen würde ob ein Eckpunkte vom Dreieck in der box ist, nämlich es sind immer noch die gleichen Dreiecke wo ich hindurch kann.

Öhm nein der Code fängt alle Fälle ab, auch den wenn alle Punkte außerhalb sind un das Dreieck trotzdem die Box schneidet. Schau ihn dir mal genau an!

[Gast25250]

krabbels schrieb:

Gast25250 schrieb:

Du musst einfach eine Referenz auf das Dreieck in jeder Zelle speichern, die vom Dreieck geschnitten wird.

Dann kann es aber passieren, dass du die selben Dreiecke mehrmals zeichnest.

For all interesting cells
  For all tris in cell
    tri->marker = true;

for all tris
  if (tri->marker)
    draw

so nicht

gruss, Gast

[Gast25250]

blinki schrieb:

@hustbaer in den Enknoten überprüfe ich welche Dreiecke in der Bounding Box sind oder mach ich da jetzt was falsch?

@Gast25250 ich weiss jetzt nicht ob ich dich richtig verstanden hab, aber ich will ja wissen wie ich das überprüfen kann, wenn das die Bounding Box Schneidet. Die meisten testen die Eckpunkte von den Dreiecken aber bei mir sind welche so groß, dass die Eckpunkte nicht mehr in der Box sind.

So könnte eine Dreiecksklasse für einen Octree aussehen:

//! A triangle which can be added to an OcTree.
template <class T>
class OcTriangle {

public:
	typedef T Point;
	typedef typename T::ValueType ValueType;

// ****************************************************************************************

	//! (Void-)Constructor
	OcTriangle() : triplane(v0, v1, v2) {
	}

// ****************************************************************************************

	//! Constructor
	OcTriangle(Point v0_, Point v1_, Point v2_) : v0(v0_), v1(v1_), v2(v2_), triplane(v0_, v1_, v2_) {
	}

// ****************************************************************************************

	//! Returns if the triangle is contained in / intersects the cell from 'start' to 'end'.
	inline bool isContainedIn(const Point& start, const Point& end) const {

		// Trivial reject, triangle lies entirely outside one of the cells faces:
		if (v0.x < start.x && v1.x < start.x && v2.x < start.x) return false;
		if (v0.x > end.x && v1.x > end.x && v2.x > end.x) return false;
		if (v0.y < start.y && v1.y < start.y && v2.y < start.y) return false;
		if (v0.y > end.y && v1.y > end.y && v2.y > end.y) return false;
		if (v0.z < start.z && v1.z < start.z && v2.z < start.z) return false;
		if (v0.z > end.z && v1.z > end.z && v2.z > end.z) return false;

		// Trivial accept, one vertex of the triangle lies entirely in the cell.
		if ((start < v0 && end > v0) || (start < v1 && end > v1) || (start < v2 && end > v2)) return true;

		// Not so trivial accept, check if one of the cells edges intersects the triangle:
		if (lineIntersects(start, Point(end.x, start.y, start.z))) return true;
		if (lineIntersects(start, Point(start.x, end.y, start.z))) return true;
		if (lineIntersects(start, Point(start.x, start.y, end.z))) return true;
		if (lineIntersects(end, Point(start.x, end.y, end.z))) return true;
		if (lineIntersects(end, Point(end.x, start.y, end.z))) return true;
		if (lineIntersects(end, Point(end.x, end.y, start.z))) return true;
		if (lineIntersects(Point(end.x, end.y, start.x), Point(end.x, start.y, start.z))) return true;
		if (lineIntersects(Point(end.x, end.y, start.x), Point(start.x, end.y, start.z))) return true;
		if (lineIntersects(Point(start.x, end.y, end.z), Point(start.x, start.y, end.z))) return true;
		if (lineIntersects(Point(start.x, end.y, end.z), Point(start.x, end.y, start.z))) return true;
		if (lineIntersects(Point(start.x, start.y, end.z), Point(end.x, start.y, end.z))) return true;
		if (lineIntersects(Point(end.x, start.y, start.z), Point(end.x, start.y, end.z))) return true;

		return false;
	}

// ****************************************************************************************

	//! Check if line ('start' - 'end') intersects the triangle.
	inline bool lineIntersects(const Point& start, const Point& end) const {

		Point direction = end-start;

		ValueType d = - ((start-v0)|triplane.getNormal())/(direction|triplane.getNormal());

		if ((d < 0) || (d > 1)) return false;

		// Line between 'start' and 'end' intersects triangle plane, check if the
		// intersection point lies within the triangle.
		Point intersect_point = start + direction * d;

		return liesInsideTriangle(intersect_point);
	}

// ****************************************************************************************

	//! Computes the intersection point between the ray through 'start' and 'end' and the plane in which the triangle is embedded.
	inline Point getPlaneIntersection(const Point& start, const Point& end) const {

		Point direction = end-start;

		ValueType d = - ((start-v0)|triplane.getNormal())/(direction|triplane.getNormal());

		// Line between 'start' and 'end' intersects triangle plane, check if the
		// intersection point lies within the triangle.
		return start + direction * d;

	}

// ****************************************************************************************

	//! Computes the (real) distance between 'point' and the triangle.
	inline ValueType distance(const Point& point) {

		// If the ray ('point', triangles normal) intersects the triangle-plane within the triangle,
		// the distance between the triangles and the point is the distance between point and intersection.
		ValueType d = triplane.getDistance(point);
		Point intersection = start + direction * d;

		point2d<ValueType> v0proj, v1proj, v2proj, iproj;
		if (triplane.getNormal().x <= triplane.getNormal().y && triplane.getNormal().x <= triplane.getNormal().z) {
			v0proj = point2d<ValueType>(v0.y, v0.z);
			v1proj = point2d<ValueType>(v1.y, v1.z);
			v2proj = point2d<ValueType>(v2.y, v2.z);
			iproj = point2d<ValueType>(point.y, point.z);
		} else {
			v0proj = point2d<ValueType>(v0.x, v0.z);
			v1proj = point2d<ValueType>(v1.x, v1.z);
			v2proj = point2d<ValueType>(v2.x, v2.z);
			iproj = point2d<ValueType>(point.x, point.z);
		}
		// 2D barycentric test:
		ValueType a_tri = Matrix3D<ValueType>(v0proj.x, v1proj.x, v2proj.x, v0proj.y, v1proj.y, v2proj.y, 1, 1, 1).determinant();
		ValueType a_0 = Matrix3D<ValueType>(iproj.x, v1proj.x, v2proj.x, iproj.y, v1proj.y, v2proj.y, 1, 1, 1).determinant()/a_tri;
		ValueType a_1 = Matrix3D<ValueType>(v0proj.x, iproj.x, v2proj.x, v0proj.y, iproj.y, v2proj.y, 1, 1, 1).determinant()/a_tri;
		ValueType a_2 = Matrix3D<ValueType>(v0proj.x, v1proj.x, iproj.x, v0proj.y, v1proj.y, iproj.y, 1, 1, 1).determinant()/a_tri;

		if (a_0 >= 0 && a_1 >= 0 && a_2 >= 0) { // point lies within triangle
			return (intersection-point).length());
		}

		// Intersection does not lie within the triangle.
		if (a_0 < 0) { // closest point must lie on the line 'v1' - 'v2'
			if (a_1 < 0) { // closest point must lie on the line 'v0' - 'v2'
				// ergo, closest point is 'v2'
				return (v2-point).length();
			}
			if (a_2 < 0) { // closest point must lie on the line 'v0' - 'v1'
				// ergo, closest point is 'v1'
				return (v1-point).length();
			}
			// well, closest point is the distance between point and the line 'v1' - 'v2'.
			return (getClosestPointOnLine(v1, v2, point)-point).length();
		}
		if (a_1 < 0) { // closest point must lie on the line 'v0' - 'v2'
			if (a_2 < 0) { // closest point must lie on the line 'v0' - 'v1'
				// ergo, closest point is 'v0'
				return (v0-point).length();
			}
			// well, closest point is the distance between point and the line 'v0' - 'v2'.
			return (getClosestPointOnLine(v2, v0, point)-point).length();
		}
		if (a_2 < 0) { // a_1 and a_0
		}

	}

// ****************************************************************************************

	//! Vertex of the triangle.
	Point v0;
	//! Vertex of the triangle.
	Point v1;
	//! Vertex of the triangle.
	Point v2;

private:

// ****************************************************************************************

	inline Point getClosestPointOnLine(const Point& v0, const Point& v1, const Point& p) const {

		ValueType u = ((p.x-v0.x)*(v1.x-v0.x) + (p.y-v0.y)*(v1.y-v0.y) + (p.z-v0.z)*(v1.z-v0.z)) / (v0-v1).squaredLength();

		if (u <= 0) return v0;
		if (u >= 1) return v1;

        return (v0 + (v1-v0)*u);
	}

// ****************************************************************************************

	//! Checks if 'point' lies inside the triangle; it is assumed, that 'point' lies on the plane of the triangle.
	inline bool liesInsideTriangle(const Point& point) const {

		// Project triangle and point into 2D and do computation there:
		// Project triangle and point onto some plane
		point2d<ValueType> v0proj, v1proj, v2proj, iproj;
		if (triplane.getNormal().x <= triplane.getNormal().y && triplane.getNormal().x <= triplane.getNormal().z) {
			v0proj = point2d<ValueType>(v0.y, v0.z);
			v1proj = point2d<ValueType>(v1.y, v1.z);
			v2proj = point2d<ValueType>(v2.y, v2.z);
			iproj = point2d<ValueType>(point.y, point.z);
		} else {
			v0proj = point2d<ValueType>(v0.x, v0.z);
			v1proj = point2d<ValueType>(v1.x, v1.z);
			v2proj = point2d<ValueType>(v2.x, v2.z);
			iproj = point2d<ValueType>(point.x, point.z);
		}
		// 2D barycentric test:
		ValueType a_tri = Matrix3D<ValueType>(v0proj.x, v1proj.x, v2proj.x, v0proj.y, v1proj.y, v2proj.y, 1, 1, 1).determinant();
		ValueType a_0 = Matrix3D<ValueType>(iproj.x, v1proj.x, v2proj.x, iproj.y, v1proj.y, v2proj.y, 1, 1, 1).determinant()/a_tri;
		ValueType a_1 = Matrix3D<ValueType>(v0proj.x, iproj.x, v2proj.x, v0proj.y, iproj.y, v2proj.y, 1, 1, 1).determinant()/a_tri;
		ValueType a_2 = Matrix3D<ValueType>(v0proj.x, v1proj.x, iproj.x, v0proj.y, v1proj.y, iproj.y, 1, 1, 1).determinant()/a_tri;

		if (a_0 > 0 && a_1 > 0 && a_2 > 0)
			return true;

		return false;
	}

// ****************************************************************************************

	Plane<vec3d> triplane;
};

[hustbaer]

blinki schrieb:

@hustbaer in den Enknoten überprüfe ich welche Dreiecke in der Bounding Box sind oder mach ich da jetzt was falsch?

Ok, kommt vielleicht wirklich drauf an wofür genau den den Octree verwenden willst.
Ich kenne eben nur Anwendungen wo man keine Dreiecke sondern ganze Objekte bzw. Teil-Objekte in den Octree steckt, und dafür verwendet man eben die Bounding Box(en) des Objektes.

[blinki]

@Pellaeon: ich weiß dann nicht warum es bei mir nicht richtig funktioniert, ich könnte ja ein bisschen code von mir schicken oder?
Werde es dann auch später mal mit Gast25250 code versuchen.

[blinki]

hier ist der Code wo ich glaub das da der Fehler drinne ist.

void objekt::SplitNode( NODE* pNode, int iMaxDepth)
{
	if(iMaxDepth <= 0) return;

	if(pNode->dwNumTriangles <= 100) return;

	D3DXVECTOR3 vCenter(0.5f * (pNode->min + pNode->max));

	DWORD* pdwTemp;
	DWORD facecount;
	D3DXVECTOR3 vTriA;
	D3DXVECTOR3 vTriB;
	D3DXVECTOR3 vTriC;

	for(DWORD i = 0; i < 8; i++)
	{
		pNode->child[i] = (NODE *)calloc( sizeof( NODE), 1);

		switch(i)
		{
		case 0:
			pNode->child[i]->min = pNode->min;
			pNode->child[i]->max = vCenter;
			break;

		case 1:
			pNode->child[i]->min = pNode->min;
			pNode->child[i]->min.x = vCenter.x;
			pNode->child[i]->max = vCenter;
			pNode->child[i]->max.x = pNode->max.x;
			break;

		case 2:
			pNode->child[i]->min = pNode->min;
			pNode->child[i]->min.y = vCenter.y;
			pNode->child[i]->max = vCenter;
			pNode->child[i]->max.y = pNode->max.y;
			break;

		case 3:
			pNode->child[i]->min = pNode->min;
			pNode->child[i]->min.x = vCenter.x;
			pNode->child[i]->min.y = vCenter.y;
			pNode->child[i]->max = vCenter;
			pNode->child[i]->max.x = pNode->max.x;
			pNode->child[i]->max.y = pNode->max.y;
			break;

		case 4:
			pNode->child[i]->min = pNode->min;
			pNode->child[i]->min.z = vCenter.z;
			pNode->child[i]->max = vCenter;
			pNode->child[i]->max.z = pNode->max.z;
			break;

		case 5:
			pNode->child[i]->min = pNode->min;
			pNode->child[i]->min.x = vCenter.x;
			pNode->child[i]->min.z = vCenter.z;
			pNode->child[i]->max = vCenter;
			pNode->child[i]->max.x = pNode->max.x;
			pNode->child[i]->max.z = pNode->max.z;
			break;

		case 6:
			pNode->child[i]->min = pNode->min;
			pNode->child[i]->min.y = vCenter.y;
			pNode->child[i]->min.z = vCenter.z;
			pNode->child[i]->max = vCenter;
			pNode->child[i]->max.y = pNode->max.y;
			pNode->child[i]->max.z = pNode->max.z;
			break;

		case 7:
			pNode->child[i]->min = vCenter;
			pNode->child[i]->max = pNode->max;
			break;
		}

		pdwTemp = new DWORD[pNode->dwNumTriangles];
		facecount = 0;

		for(DWORD j = 0; j < pNode->dwNumTriangles; j++)
		{
			vTriA = pVerices[pwIndices[pNode->pdwTriangles[j]].vertex[0]];
			vTriB = pVerices[pwIndices[pNode->pdwTriangles[j]].vertex[1]];
			vTriC = pVerices[pwIndices[pNode->pdwTriangles[j]].vertex[2]];
			if(isectboxtri(pNode->child[i]->min ,pNode->child[i]->max ,vTriA ,vTriB, vTriC))
			{
				pdwTemp[facecount] = pNode->pdwTriangles[j];
				facecount++;
			}
		}
		pNode->child[i]->pdwTriangles = (DWORD *)calloc(facecount * sizeof( DWORD), 1);
		memcpy(pNode->child[i]->pdwTriangles, pdwTemp, facecount * sizeof(DWORD));
		pNode->child[i]->dwNumTriangles = facecount;

		delete pdwTemp;

		pNode->child[i]->bIsLeaf = true;

		SplitNode(pNode->child[i], iMaxDepth -1);
	}

	delete pNode->pdwTriangles;

	pNode->bIsLeaf = false;
}

[__Stefan__]

Wieso berechnest du nicht für jedes Dreieck eine Bounding Box und prüfst jeweils mit welchen Nodes des Octrees diese überschneidet?

[Gast25250]

Stefan schrieb:

Wieso berechnest du nicht für jedes Dreieck eine Bounding Box und prüfst jeweils mit welchen Nodes des Octrees diese überschneidet?

Weil grosse Dreiecke dann in zu vielen Nodes verzeichnet wären.

[blinki]

Hat sonst keiner eine Idee was ich machen könnte? Eigentlich müssten doch alle Dreiecke richtig zugeteilt sein.

[Pellaeon]

blinki schrieb:

Hat sonst keiner eine Idee was ich machen könnte? Eigentlich müssten doch alle Dreiecke richtig zugeteilt sein.

Du könntest a deinen Octree mal visualisieren um die Aufteilung zu sehen.
ansonsten wirst wohl oder übel mal den Debugger anwerfen müssen und nachschauen, wo es hängt.

[Plassy]

wenn du die Dreiecke nicht in ihrer "Urform" brauchst, kannst
du die Dreiecke so zerschneiden (clipping), dass sie passen.
Am ende hast du zwar mehr Dreiecke als vorher, aber dafür liegt dann
jedes Dreieck in einer Zelle und nicht in mehreren.