[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [12202] branches/cloth/blender/source/ blender/blenkernel: New: Collision detection for inter-timestep-collisions for triangle-point contacts .
Daniel Genrich
daniel.genrich at gmx.net
Thu Oct 4 00:43:26 CEST 2007
Revision: 12202
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=12202
Author: genscher
Date: 2007-10-04 00:43:26 +0200 (Thu, 04 Oct 2007)
Log Message:
-----------
New: Collision detection for inter-timestep-collisions for triangle-point contacts. No response yet though.
Modified Paths:
--------------
branches/cloth/blender/source/blender/blenkernel/BKE_cloth.h
branches/cloth/blender/source/blender/blenkernel/intern/collision.c
Modified: branches/cloth/blender/source/blender/blenkernel/BKE_cloth.h
===================================================================
--- branches/cloth/blender/source/blender/blenkernel/BKE_cloth.h 2007-10-03 21:01:14 UTC (rev 12201)
+++ branches/cloth/blender/source/blender/blenkernel/BKE_cloth.h 2007-10-03 22:43:26 UTC (rev 12202)
@@ -235,9 +235,31 @@
float pa[3], pb[3]; // collision point p1 on face1, p2 on face2
int lastsign; // indicates if the distance sign has changed, unused itm
float time; // collision time, from 0 up to 1
- unsigned int ap1, ap2, ap3, bp1, bp2, bp3;
+ unsigned int ap1, ap2, ap3, bp1, bp2, bp3, bp4;
+ unsigned int pointsb[4];
} CollPair;
+/* used for collisions in collision.c */
+typedef struct EdgeCollPair
+{
+ unsigned int p11, p12, p21, p22;
+ float normal[3];
+ float vector[3];
+ float time;
+ int lastsign;
+ float pa[3], pb[3]; // collision point p1 on face1, p2 on face2
+} EdgeCollPair;
+/* used for collisions in collision.c */
+typedef struct FaceCollPair
+{
+ unsigned int p11, p12, p13, p21;
+ float normal[3];
+ float vector[3];
+ float time;
+ int lastsign;
+ float pa[3], pb[3]; // collision point p1 on face1, p2 on face2
+} FaceCollPair;
+
#endif
Modified: branches/cloth/blender/source/blender/blenkernel/intern/collision.c
===================================================================
--- branches/cloth/blender/source/blender/blenkernel/intern/collision.c 2007-10-03 21:01:14 UTC (rev 12201)
+++ branches/cloth/blender/source/blender/blenkernel/intern/collision.c 2007-10-03 22:43:26 UTC (rev 12202)
@@ -71,123 +71,254 @@
#include "Bullet-C-Api.h"
-#define DERANDOMIZE 1
+
+/**
+ * gsl_poly_solve_cubic -
+ *
+ * copied from SOLVE_CUBIC.C --> GSL
+ */
+#define mySWAP(a,b) do { float tmp = b ; b = a ; a = tmp ; } while(0)
+int gsl_poly_solve_cubic (float a, float b, float c, float *x0, float *x1, float *x2)
+{
+ float q = (a * a - 3 * b);
+ float r = (2 * a * a * a - 9 * a * b + 27 * c);
+
+ float Q = q / 9;
+ float R = r / 54;
+
+ float Q3 = Q * Q * Q;
+ float R2 = R * R;
+
+ float CR2 = 729 * r * r;
+ float CQ3 = 2916 * q * q * q;
+
+ if (R == 0 && Q == 0)
+ {
+ *x0 = - a / 3 ;
+ *x1 = - a / 3 ;
+ *x2 = - a / 3 ;
+ return 3 ;
+ }
+ else if (CR2 == CQ3)
+ {
+ /* this test is actually R2 == Q3, written in a form suitable
+ for exact computation with integers */
+
+ /* Due to finite precision some float roots may be missed, and
+ considered to be a pair of complex roots z = x +/- epsilon i
+ close to the real axis. */
+
+ float sqrtQ = sqrtf (Q);
+
+ if (R > 0)
+ {
+ *x0 = -2 * sqrtQ - a / 3;
+ *x1 = sqrtQ - a / 3;
+ *x2 = sqrtQ - a / 3;
+ }
+ else
+ {
+ *x0 = - sqrtQ - a / 3;
+ *x1 = - sqrtQ - a / 3;
+ *x2 = 2 * sqrtQ - a / 3;
+ }
+ return 3 ;
+ }
+ else if (CR2 < CQ3) /* equivalent to R2 < Q3 */
+ {
+ float sqrtQ = sqrtf (Q);
+ float sqrtQ3 = sqrtQ * sqrtQ * sqrtQ;
+ float theta = acosf (R / sqrtQ3);
+ float norm = -2 * sqrtQ;
+ *x0 = norm * cosf (theta / 3) - a / 3;
+ *x1 = norm * cosf ((theta + 2.0 * M_PI) / 3) - a / 3;
+ *x2 = norm * cosf ((theta - 2.0 * M_PI) / 3) - a / 3;
+
+ /* Sort *x0, *x1, *x2 into increasing order */
+
+ if (*x0 > *x1)
+ mySWAP(*x0, *x1) ;
+
+ if (*x1 > *x2)
+ {
+ mySWAP(*x1, *x2) ;
+
+ if (*x0 > *x1)
+ mySWAP(*x0, *x1) ;
+ }
+
+ return 3;
+ }
+ else
+ {
+ float sgnR = (R >= 0 ? 1 : -1);
+ float A = -sgnR * powf (fabs (R) + sqrtf (R2 - Q3), 1.0/3.0);
+ float B = Q / A ;
+ *x0 = A + B - a / 3;
+ return 1;
+ }
+}
+
+
+/**
+ * gsl_poly_solve_quadratic
+ *
+ * copied from GSL
+ */
+int gsl_poly_solve_quadratic (float a, float b, float c, float *x0, float *x1)
+{
+ float disc = b * b - 4 * a * c;
+
+ if (disc > 0)
+ {
+ if (b == 0)
+ {
+ float r = fabs (0.5 * sqrtf (disc) / a);
+ *x0 = -r;
+ *x1 = r;
+ }
+ else
+ {
+ float sgnb = (b > 0 ? 1 : -1);
+ float temp = -0.5 * (b + sgnb * sqrtf (disc));
+ float r1 = temp / a ;
+ float r2 = c / temp ;
+
+ if (r1 < r2)
+ {
+ *x0 = r1 ;
+ *x1 = r2 ;
+ }
+ else
+ {
+ *x0 = r2 ;
+ *x1 = r1 ;
+ }
+ }
+ return 2;
+ }
+ else if (disc == 0)
+ {
+ *x0 = -0.5 * b / a ;
+ *x1 = -0.5 * b / a ;
+ return 2 ;
+ }
+ else
+ {
+ return 0;
+ }
+}
-enum TRIANGLE_MARK
-{
- TM_MV = 1,
- TM_ME = 2,
- TM_V1 = 4,
- TM_V2 = 8,
- TM_V3 = 16,
- TM_E1 = 32,
- TM_E2 = 64,
- TM_E3 = 128
-};
-DO_INLINE int hasTriangleMark(unsigned char mark, unsigned char bit) { return mark & bit; }
-DO_INLINE void setTriangleMark(unsigned char *mark, unsigned char bit) { mark[0] |= bit; }
-DO_INLINE void clearTriangleMark(unsigned char *mark, unsigned char bit) { mark[0] &= ~bit; }
+/*
+ * See Bridson et al. "Robust Treatment of Collision, Contact and Friction for Cloth Animation"
+ * page 4, left column
+ */
-void generateTriangleMarks()
+int cloth_get_collision_time(float a[3], float b[3], float c[3], float d[3], float e[3], float f[3], float solution[3])
{
- /*
- unsigned int firstEdge = 0;
+ int num_sols = 0;
- // 1. Initialization
- memset(m_triangleMarks, 0, sizeof(unsigned char) * m_triangleCount);
+ float g = -a[2] * c[1] * e[0] + a[1] * c[2] * e[0] +
+ a[2] * c[0] * e[1] - a[0] * c[2] * e[1] -
+ a[1] * c[0] * e[2] + a[0] * c[1] * e[2];
- // 2. The Marking Process
-
- // 2.1 Randomly mark triangles for covering vertices.
- for (unsigned int v = 0; v < m_vertexCount; ++v)
+ float h = -b[2] * c[1] * e[0] + b[1] * c[2] * e[0] - a[2] * d[1] * e[0] +
+ a[1] * d[2] * e[0] + b[2] * c[0] * e[1] - b[0] * c[2] * e[1] +
+ a[2] * d[0] * e[1] - a[0] * d[2] * e[1] - b[1] * c[0] * e[2] +
+ b[0] * c[1] * e[2] - a[1] * d[0] * e[2] + a[0] * d[1] * e[2] -
+ a[2] * c[1] * f[0] + a[1] * c[2] * f[0] + a[2] * c[0] * f[1] -
+ a[0] * c[2] * f[1] - a[1] * c[0] * f[2] + a[0] * c[1] * f[2];
+
+ float i = -b[2] * d[1] * e[0] + b[1] * d[2] * e[0] +
+ b[2] * d[0] * e[1] - b[0] * d[2] * e[1] -
+ b[1] * d[0] * e[2] + b[0] * d[1] * e[2] -
+ b[2] * c[1] * f[0] + b[1] * c[2] * f[0] -
+ a[2] * d[1] * f[0] + a[1] * d[2] * f[0] +
+ b[2] * c[0] * f[1] - b[0] * c[2] * f[1] +
+ a[2] * d[0] * f[1] - a[0] * d[2] * f[1] -
+ b[1] * c[0] * f[2] + b[0] * c[1] * f[2] -
+ a[1] * d[0] * f[2] + a[0] * d[1] * f[2];
+
+ float j = -b[2] * d[1] * f[0] + b[1] * d[2] * f[0] +
+ b[2] * d[0] * f[1] - b[0] * d[2] * f[1] -
+ b[1] * d[0] * f[2] + b[0] * d[1] * f[2];
+
+ // Solve cubic equation to determine times t1, t2, t3, when the collision will occur.
+ if(ABS(j) > ALMOST_ZERO)
+ {
+ i /= j;
+ h /= j;
+ g /= j;
+
+ num_sols = gsl_poly_solve_cubic(i, h, g, &solution[0], &solution[1], &solution[2]);
+ }
+ else if(ABS(i) > ALMOST_ZERO)
+ {
+ num_sols = gsl_poly_solve_quadratic(i, h, g, &solution[0], &solution[1]);
+ solution[2] = -1.0;
+ }
+ else if(ABS(h) > ALMOST_ZERO)
{
- if (vertexCover(v) == 0)
+ solution[0] = -g / h;
+ solution[1] = solution[2] = -1.0;
+ num_sols = 1;
+ }
+ else if(ABS(g) > ALMOST_ZERO)
{
+ solution[0] = 0;
+ solution[1] = solution[2] = -1.0;
+ num_sols = 1;
+ }
- // Randomly select an edge whose first triangle we're going to flag.
-
-#ifndef DERANDOMIZE
- firstEdge = (unsigned int)((float)(random() & 0x7FFFFFFF) /
- (float)(0x80000000) *
- (float)(m_vertices[v].getEdgeCount()));
-#endif
- for (unsigned int ofs = 0; ofs < m_vertices[v].getEdgeCount(); ++ofs)
+ // Discard negative solutions
+ if ((num_sols >= 1) && (solution[0] < 0))
{
- unsigned int edgeIdx = (firstEdge + ofs) % m_vertices[v].getEdgeCount();
- if (m_edges[m_vertices[v].getEdge(edgeIdx)].getTriangleCount())
- setTriangleMark(m_triangleMarks[m_edges[m_vertices[v].getEdge(edgeIdx)].getTriangle(0)], TM_MV);
-}
-}
-}
- */
- /* If the Cloth is malformed (vertices without adjacent triangles) there might still be uncovered vertices. (Bad luck.) */
- /*
- // 2.2 Randomly mark triangles for covering edges.
- for (unsigned int e = 0; e < m_edgeCount; ++e)
+ --num_sols;
+ solution[0] = solution[num_sols];
+ }
+ if ((num_sols >= 2) && (solution[1] < 0))
{
- if (m_edges[e].getTriangleCount() && (edgeCover(e) == 0))
+ --num_sols;
+ solution[1] = solution[num_sols];
+ }
+ if ((num_sols == 3) && (solution[2] < 0))
{
-#ifndef DERANDOMIZE
- setTriangleMark(m_triangleMarks[m_edges[e].getTriangle(static_cast<UINT32>((float)(random() & 0x7FFFFFFF) /
- (float)(0x80000000) *
- (float)(m_edges[e].getTriangleCount())))], TM_ME);
-#else
- setTriangleMark(m_triangleMarks[m_edges[e].getTriangle(0)], TM_ME);
-#endif
-}
-}
+ --num_sols;
+ }
-
- // 3. The Unmarking Process
- for (unsigned int t = 0; (t < m_triangleCount); ++t)
+ // Sort
+ if (num_sols == 2)
{
- bool overCoveredVertices = true;
- bool overCoveredEdges = true;
- for (unsigned char i = 0; (i < 3) && (overCoveredVertices || overCoveredEdges); ++i)
+ if (solution[0] > solution[1])
+ {
+ double tmp = solution[0];
+ solution[0] = solution[1];
+ solution[1] = tmp;
+ }
+ }
+ else if (num_sols == 3)
{
- if (vertexCover(m_triangles[t].getVertex(i)) == 1)
- overCoveredVertices = false;
- if (edgeCover(m_triangles[t].getEdge(i)) == 1)
- overCoveredEdges = false;
+ // Bubblesort
+ if (solution[0] > solution[1]) {
+ double tmp = solution[0]; solution[0] = solution[1]; solution[1] = tmp;
+ }
+ if (solution[1] > solution[2]) {
+ double tmp = solution[1]; solution[1] = solution[2]; solution[2] = tmp;
+ }
+ if (solution[0] > solution[1]) {
+ double tmp = solution[0]; solution[0] = solution[1]; solution[1] = tmp;
+ }
+ }
- assert(vertexCover(m_triangles[t].getVertex(i)) > 0);
- assert(edgeCover(m_triangles[t].getEdge(i)) > 0);
+ return num_sols;
}
- if (overCoveredVertices)
- clearTriangleMark(m_triangleMarks[t], TM_MV);
- if (overCoveredEdges)
- clearTriangleMark(m_triangleMarks[t], TM_ME);
-}
-
- // 4. The Bit Masking Process
- vector<bool> vertexAssigned(m_vertexCount, false);
- vector<bool> edgeAssigned(m_edgeCount, false);
- for (unsigned int t = 0; (t < m_triangleCount); ++t)
- {
- for (unsigned char i = 0; i < 3; ++i)
- {
- if (!vertexAssigned[m_triangles[t].getVertex(i)])
- {
- vertexAssigned[m_triangles[t].getVertex(i)] = true;
- setTriangleMark(m_triangleMarks[t], 1 << (2 + i));
-}
- if (!edgeAssigned[m_triangles[t].getEdge(i)])
- {
- edgeAssigned[m_triangles[t].getEdge(i)] = true;
- setTriangleMark(m_triangleMarks[t], 1 << (5 + i));
-}
-}
-}
- */
-}
-
// w3 is not perfect
-void bvh_compute_barycentric (float pv[3], float p1[3], float p2[3], float p3[3], float *w1, float *w2, float *w3)
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list