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
