4. große Geschwindigkeitsunterschiede

große Geschwindigkeitsunterschiede

  • N

    Hallo liebe Community

    Ich arbeite momentan mit VC++ 6.0 und habe ein Tool geschrieben, welches ein Polygonnetz (Dreiecke) einliest. Die Datenstruktur besteht grob gesagt aus einem Vertexarray und einem Dreiecksarray.

    Dann habe ich eine Funktion, welche mir jeden Punkt das Netzes um eine kleine Distanz entgegen seiner Normalen verschiebt. Dann teste ich, ob dieser verschobene Punkt innerhalb des Netzes liegt (Schnitttests mit den Dreiecken). Diese Funktion ist recht aufwändig. Nun habe ich die Operation auf 2 verschiedenen Rechnern ausgeführt, einem PC und einem Laptop.

    Laptop: 1,4 GHz Celeron, 512 MB DDR(?) RAM --> Zeit etwa 32 Sekunden
    PC: 1,3 GHz Duron, 768 MB DDR RAM --> Zeit etwa 57 Sekunden

    Woher kommt dieser extrem Geschwindigkeitsunterschied? Wie kann ich dem entgegenwirken?

    MfG
    Neron

    0
  • ?

    Ich schätze mal:

    CeleronM: 256KB L2 Cache
    Duron: 64KB L2 Cache

    hol dir mal die kostenlose Express Version und compiliere mit Optimierungen durch. Wirkt Wunder...

    0
  • G

    Gute Frage, mein

    Laptop: 1,4 GHz Celeron, 512 MB DDR(?) RAM

    ist auch fast so schnell wie ein Pentium 4 3GHZ...

    0
  • N

    SeppSchrot schrieb:

    hol dir mal die kostenlose Express Version und compiliere mit Optimierungen durch. Wirkt Wunder...

    Wenn's so einfach wär. Ich hab mir das Teil schon geholt, aber da scheiterts schon an der Stdafx.h. Sieht so aus, als müßte ich's in dem Fall nochmal neu anlegen 😞

    0
  • ?

    Schalt mal in den Projekteinstellungen den vorkompilierten Header aus.

    0
  • N

    Hm, aber ich hab die stdafx.h in mehreren Dateien eingebunden, da entstehen ne Menge Fehler und irgendwie schleicht sie sich immer wieder ein.

    Eine andere Sache. Ich wollte mit VC++ 2005 Express Edition eben ein neues projekt anlegen, aber scheinbar kann ich für Win32 nur eine Konsolenanwendung anlegen. Geht da echt nicht mehr?

    0
  • T

    Neron17 schrieb:

    Eine andere Sache. Ich wollte mit VC++ 2005 Express Edition eben ein neues projekt anlegen, aber scheinbar kann ich für Win32 nur eine Konsolenanwendung anlegen. Geht da echt nicht mehr?

    Doch das geht:
    http://msdn.microsoft.com/vstudio/express/visualc/usingpsdk/

    0
  • A

    Schon mal versucht einfach eine leere stdafx.h Datei anzulegen?

    0
  • N

    So langsam komm ich dem Ziel näher. Hab mir jetzt den Link von 1310-Logik angesehen und die Erweiterung installiert. Nun hab ich in den Include-Verzeichnissen der SDK auch die geforderten Header-Dateien. Allerdings spuckt er mir nun Fehler aus, dass er eine Header-Datei (afxwin.h), die in der stdafx.h eingebunden wird nicht findet. Die entsprechende Datei befindet sich in einem Unterverzeichnis des SDK/Include-Ordners, welchen ich schon eingebunden habe. Wieso findet er die Datei nicht? Wenn ich unter zusätzliche Includeverzeichnisse für das Projekt noch das Unterverzeichnis angebe (nämlich den Ordner mfc), findet er sie...aber 3 Schritte später findet er die nächste Header Datei nicht, die aber im gleichen Verzeichnis wie die afxwin.h steht, also auch im Ordner mfc - da blick ich nich durch? Irgendwelche Vorschläge?

    Edit: Hier mal die Fehlermeldung:

    fatal error RC1015: cannot open include file 'afxres.h'
    0
  • A

    ARGH! Die MFC ist doch im PlatformSDK garnicht dabei! Wenn du unbedingt die MFC brauchst, mußt die mind. die Standard-Edition von VS kaufen.

    0
  • ?

    Au Backe,
    dein Projekt nutzt ja MFC Framework, oder?
    Ich dachte, es gehe jetzt nur um pures Win32.

    MFC geht meines Wissens mit dem freien MS Compilern nicht.

    0
  • N

    SeppSchrot schrieb:

    Au Backe,...

    Jup, besser hätt ich's nich sagen können 😉

    Naja, so runde 300 Euro sind n bissel happig für mich, da werd ich wohl weiterhin bei VC++ 6.0 bleiben. Ich danke trotzdem allen für die Hilfe. Wer weiß, vielleicht brauch ich die vollinstallierte VS 2005 Express Edition ja doch irgendwann mal 😉

    Also vielen Dank nochmal und ganz sicher bis demnächst
    Liebe Grüße
    Neron

    0
  • ?

    Poste später einfach mal deine konkreten Algorithmen, da kann man sicherlich auch selber was rausholen.

    Oder du versuchst dein Projekt auf ein anderes Framework zu porten, dann kannst du einen der besseren Compiler nehmen.

    PS: Wenn du Schüler/Studi bist:
    http://www.edv-buchversand.de/product.php?cnt=product&id=so-1419&lng=0

    0
  • N

    SeppSchrot schrieb:

    Poste später einfach mal deine konkreten Algorithmen, da kann man sicherlich auch selber was rausholen.

    Leicht gesagt - die Algorithmen sind schon ganz schön krass und auch bissel verzweigt, da müsst ich einiges erklären. Aber ich poste mal meine Hauptfunktionen, die ich am ehesten optimieren möchte...

    Also, dies is die Hauptfunktion. Übergeben wird ein Punkt und ein Zeiger auf das Dreiecksnetz, hier skeleton genannt. skeleton besteht aus Eckpunkten (Position + Normale) und Dreiecken (3er-Pack von Eckpunkten). Richtig los gehts beim Kommentar "// 1: Check..." Ich gehe in der Funktion von meinem Punkt aus und schieße einen Strahl in positiver X-Richtung. Dann gucke ich, wie oft der Strahl ein Dreieck schneidet (ungerade Anzahl-->Punkt ist drinnen, gerade Anzahl-->Punkt ist draußen)

    Ich eliminiere also alle Dreiecke, die auf keinen Fall geschnitten werden können und teste dann auf Schnitt mit potentiellen Kandidaten...

    int pointInMesh( sVertex p, CSkeleton* skeleton )
{
	/* reference will be a line starting in "point", directed along the x-axis */

	// variables to store triangle vertices
	sVertex p0, p1, p2;

	// variable to save intersected vertices and edges
	intersections intersect_store;
	intersect_store.third_vertice = new sVertex[20];
	intersect_store.int_e = 0;
	intersect_store.int_v = 0;

	int crossings = 0; // to count the number of crossings

	sTriangle* triangle = skeleton->gettarray(); // pointer to the triangle-array
	int trianglenum = skeleton->gettnum(); 
	sVertex* vertex = skeleton->getvarray(); // pointer to the vertex-array;
	int vertexnum = skeleton->getvnum(); 

	// check all triangles for potential intersection points
	for ( int i = 0; i < trianglenum; ++i )
	{
		// get the triangle-vertices
		p0 = vertex[triangle[i].v[0]];
		p1 = vertex[triangle[i].v[1]];
		p2 = vertex[triangle[i].v[2]];
		// 1: check if all the y-values are on one side of point
		if ( !(((p0.pos.y < p.pos.y) && (p1.pos.y < p.pos.y) && (p2.pos.y < p.pos.y )) ||
			   ((p0.pos.y > p.pos.y) && (p1.pos.y > p.pos.y) && (p2.pos.y > p.pos.y ))) )
		{
			// 2: check if all the z-values are on one side of point
			if ( !(((p0.pos.z < p.pos.z) && (p1.pos.z < p.pos.z) && (p2.pos.z < p.pos.z )) ||
				   ((p0.pos.z > p.pos.z) && (p1.pos.z > p.pos.z) && (p2.pos.z > p.pos.z ))) )
			{
				// 3: check if any of the x-values is on the "right side" of point
				if( (p0.pos.x > p.pos.x) || (p1.pos.x > p.pos.x) || (p2.pos.x > p.pos.x) )
				{
					// we have a potential intersection of the line and the triangle
					// make a final test and add the result to the counter
					crossings += lineIntersectTriangle( p, p0, p1, p2, &intersect_store, skeleton );
				}
			}
		}
	}
	// check the number of crossings for even/odd
	if ( ( crossings % 2 ) == 0 )
	{
		// even means the point isn't inside
		return 0;
	}
	else
	{
		// odd means the point is inside
		return 1;
	}
}

    In dieser Funktion ermittle ich den Schnittpunkt des Strahls mit der Dreiecksebene (Ebenengleichung aufstellen und mit der Geradengleichung kombinieren)

    int lineIntersectTriangle
( sVertex p, sVertex p0, sVertex p1, sVertex p2, intersections* intersect_store, CSkeleton* skeleton )
{

	// normal vector
	float p0p1[3] = { (p1.pos.x - p0.pos.x), 
					  (p1.pos.y - p0.pos.y),
					  (p1.pos.z - p0.pos.z) };
	float p0p2[3] = { (p2.pos.x - p0.pos.x), 
					  (p2.pos.y - p0.pos.y),
					  (p2.pos.z - p0.pos.z) };
	float normal[3] = { ((p0p1[1]*p0p2[2]) - (p0p1[2]*p0p2[1])), 
						((p0p1[2]*p0p2[0]) - (p0p1[0]*p0p2[2])), 
						((p0p1[0]*p0p2[1]) - (p0p1[1]*p0p2[0])) };

	// combine the normal vector and the given point
	float rest = (-1)*((p0.pos.x * normal[0]) + (p0.pos.y * normal[1]) + (p0.pos.z * normal[2]));

	// equation in normal form
	// normal[0]*x + normal[1]*y + normal[2]*z + rest = 0

	// apply the linear equation to the plane equation
	// normal[0]*(p.pos.x+r) + normal[1]*p.pos.y + normal[2]*p.pos.z + rest = 0;
	float r;
	if ( normal[0] != 0 )
	{
		r = ((-1)*(normal[1]*p.pos.y + normal[2]*p.pos.z + rest)/normal[0])
			- p.pos.x;
	}
	else
	{
		// normal is orthogonal to the linear equation, no intersection point
		return 0;
	}

	if ( r <= 0.0f )
	{
		// distance == 0, point lies in opposite direction or on the triangle 
		return 0;
	}

	// calculate the intersection point
	sVertex intersectionpoint;
	intersectionpoint.pos.x = p.pos.x + r;
	intersectionpoint.pos.y = p.pos.y;
	intersectionpoint.pos.z = p.pos.z ;

	// test wether the intersection point with the plane (!) lies inside the triangle
	return pointInTriangle( intersectionpoint, p0, p1, p2, intersect_store );
}

    Die letzte Funktion prüft mittels baryzentrischer Koordinaten, ob der Schnittpunkt mit der Ebene, in der das Dreieck liegt, auch innerhalb des Dreiecks liegt. Ich weiß sie funktioniert, die Logik dahinter zu erklären würde auch meine Grenzen sprengen 😃

    int pointInTriangle
( sVertex intPoint, sVertex p0, sVertex p1, sVertex p2, intersections* intersect_store )
{
	int crossings = 0; // counter
	int i = 0;

	/* test if the point is one of the vertices */
	if ( (intPoint.pos == p0.pos) || (intPoint.pos == p1.pos) || (intPoint.pos == p2.pos) )
	{
		// test if the point is already inside intersect_store
		for( i=0; i < intersect_store->int_v; ++i )
		{
			if ( (intPoint.pos.x == intersect_store->intersected_vertices[i][0]) &&
				 (intPoint.pos.y == intersect_store->intersected_vertices[i][1]) &&
				 (intPoint.pos.z == intersect_store->intersected_vertices[i][2]) )
			{
				// point is already inside
				return 0;
			}
		}			
		// point is not inside, so store it 
		intersect_store->intersected_vertices[intersect_store->int_v][0] = intPoint.pos.x;
		intersect_store->intersected_vertices[intersect_store->int_v][1] = intPoint.pos.y;
		intersect_store->intersected_vertices[intersect_store->int_v][2] = intPoint.pos.z;
		++intersect_store->int_v;
		// new intersection point, so return 1;
		return 1;
	}

	// intPoint = x*p0 + y*p1 + z*p2;

	float x,y,z,denom;
	denom = area( p0, p1, p0, p2 );
	x = area( intPoint, p1, intPoint, p2 ) / denom;
	if ( x > 1.0001 )
	{
		return 0;
	}
	y = area( intPoint, p0, intPoint, p2 ) / denom;
	if ( x+y > 1.0001 )
	{
		return 0;
	}
	z = area( intPoint, p0, intPoint, p1 ) / denom;
	if ( x+y+z > 1.0001 )
	{
		return 0;
	}

	return 1;
}

    So, hier nochmal die area-Funktion

    /*************************
 * Area between 2 Vectors *
 **************************/

float area( sVertex p0, sVertex p1, sVertex p2, sVertex p3 )
 {
	 float v1[3] = { (p1.pos.x - p0.pos.x), (p1.pos.y - p0.pos.y), (p1.pos.z - p0.pos.z) };
	 float v2[3] = { (p3.pos.x - p2.pos.x), (p3.pos.y - p2.pos.y), (p3.pos.z - p2.pos.z) };

	 return fabs(sqrt(pow((v1[1]*v2[2] - v1[2]*v2[1]),2) + 
					  pow((v1[2]*v2[0] - v1[0]*v2[2]),2) + 
					  pow((v1[0]*v2[1] - v1[1]*v2[0]),2)));
 }

    Wie gesagt, funktionieren tun die Funktionen soweit. Optimiert sind sie hier und da sicher nicht, vielleicht findet ihr ja was 🙂

    0
Anmelden zum Antworten