Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.
Posted 17 December 2012 - 01:08 AM
Posted 17 December 2012 - 04:13 AM
//Note: both hulls are already made to be around zero, so no tranlation is required. QWConvexHull *MiniskySum(QWConvexHull *A, QWConvexHull *B){ unsigned int Len = A->GetPlaneCount()+B->GetPlaneCount(); if(!Len) return 0x0; QWVector4 *R = new QWVector4[Len]; Len=0; //Add the first object as the starting shape. for(unsigned int i=0;i<A->GetPlaneCount();i++) R[Len++] = A->GetTranslatedPlane(i); //go through each point of A: for(unsigned int i=0;i<A->GetPlaneCount();i++){ QWVector4 AP = A->GetTranslatedPlane(i); QWVector3 AT = QWVector3(AP.x*AP.w, AP.y*AP.w, AP.z*AP.w); //calculate the point of the plane for the convex hull. for(unsigned int d=0;d<B->GetPlaneCount();d++){ QWVector4 BP = B->GetTranslatedPlane(d); QWVector3 BT = QWVector3(BP.x*BP.w, BP.y*BP.w, BP.z*BP.w); //calculate the point for B's plane. BT = AT+BT; /Combine the two! unsigned char RF=0; for(unsigned int x=0;x<Len;x++){ //discover if this point is inside the existing convex hull. if(QWConvexHull::PlanePointDistance(R[x], BT)>QWEPSILON){ RF=1; break; } } //If it's inside, we ignore this plane. if(!RF) continue; //Calculate the resulting point's plane relative to the origin. //since BT is not in the unit sphere, but does exist on the correct plane, we translate the resulting plane's D component to be at the correct distance. QWVector4 Z = QWVector4(BP.x, BP.y, BP.z, (BP.x*BT.x+BP.y*BT.y+BP.z*BT.z)); R[Len++] = Z; //currently, we brute force to figure out if their are any plane points that are inside our finished hull. for(unsigned int x=0;x<Len;x++){ QWVector3 P = QWVector3(R[x].x*R[x].w, R[x].y*R[x].w, R[x].z*R[x].w); for(unsigned int y=0;y<Len;y++){ if(QWConvexHull::PlanePointDistance(R[y], P)>=QWEPSILON){ //We've discovered y is inside of x, so we get rid of y. R[y--] = R[--Len]; break; } } } } } //Now just build the actual hull. QWConvexHull *H = new QWConvexHull(A->GetCenter()); for(unsigned int i=0;i<Len;i++) H->PushPlane(R[i]); //QWConvexHull *Hull delete[] R; return H; }
Posted 17 December 2012 - 06:08 AM
Posted 17 December 2012 - 06:49 AM
Applying transformations directly to normals will work correctly only with orthogonal transformations. For general transforms you'll have to use the cofactor matrix.
Besides, you're not saving that much space by using the plane equation. More precisely, for zero genus, closed, triangulated surface with 'n' vertices, you'll use '8n-16' fp units to store the planes, on the other hand you'll use '3n' fp units and '6n-12' integer units to store the vertices and indices.
Also, what general purpose calculations are better be done on plane equations than on points? I ask this because all implementations that I've done so far faired far better with verts/indcs representation. For instance you want to do Minkowski sums, they're quite easy when it's just points, but working with normals makes things more complicated.
//where R is some large number. QWVector3 QWConvexHull::GetSurfacePoint(QWVector3 Direction, float R){ QWVector3 E = Direction*R; for(unsigned int i=m_PlaneCount;i<m_PlaneCount*2;i++){ QWVector4 P = m_PlaneList[i]; float Dot = P.x*E.x+P.y*E.y+P.z*E.z; if(QWFCmp(Dot, 0.0f)) continue; float D = P.w/Dot; if(D<1.0f && D>0.0f) E*=D; } return m_Center+E; }
Posted 17 December 2012 - 07:41 AM
think about what information needs to be represented from that triangle, if you want to test if a point is inside your convex hull, then you need to test that it's inside all the planes of each triangle, if you want to test ray intersection with your triangle, first you have to get the point's intersection point with the plane that the triangle resides on, then you have to test that the point is inside the triangle.
Edited by max343, 17 December 2012 - 07:42 AM.
Posted 17 December 2012 - 07:54 AM
here's an idea, link me to relevant information, you say it can be done in O(log(n)), then tell me how, instead of just making wild claims.think about what information needs to be represented from that triangle, if you want to test if a point is inside your convex hull, then you need to test that it's inside all the planes of each triangle, if you want to test ray intersection with your triangle, first you have to get the point's intersection point with the plane that the triangle resides on, then you have to test that the point is inside the triangle.
Testing whether a point is inside a convex mesh takes O(log(n)) time. Why test it against all triangles?
Same thing goes for intersecting a ray with a convex mesh. Testing it against all triangles is suboptimal (can be done in O(log(n)) time).
Posted 17 December 2012 - 08:32 AM
Amazing... Wild claims? Instead of being rude (and down-voting) you can just read some textbook on computational geometry.
Lookup what is Dobkin-Kirkpatrick hierarchy.
Edited by slicer4ever, 17 December 2012 - 08:36 AM.
Posted 17 December 2012 - 08:58 AM
Posted 17 December 2012 - 09:09 AM
Now that I see what the problem is, I can give you the full answer. Using plane equations for meshes is suboptimal for this types of queries, because you want to exploit the convexity of your mesh. Multiple plane equations don't contain that information explicitly. On the other hand using verts/indcs is useful because you can construct the Dobkin-Kirkpatrick hierarchy (during pre-processing, takes linear time) and traverse only the most relevant parts of your convex mesh which results in a logarithmic time algorithm.
Implementation details can be found in almost any textbook that mentions this hierarchy.
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.
GameDev.net™, the GameDev.net logo, and GDNet™ are trademarks of GameDev.net, LLC.