helix 301 Report post Posted February 8, 2005 I don't know why I'm having trouble figuring this out. I've written this collision routine in the past (lost it in a hard drive crash :( ). What's the algorithm for this? Source code, pseudocode, or a description will be fine. Thanks! 0 Share this post Link to post Share on other sites
jyk 2094 Report post Posted February 8, 2005 Do you need the point of intersection, or just a boolean result? 0 Share this post Link to post Share on other sites
oliii 2196 Report post Posted February 8, 2005 easy peasyvoid AxisIntersect(float min, float max, float p, float d, float& tfirst, float& tlast){ if (fabs(d) > 1.0E-8f) { float t0 = (min - p) / d; float t1 = (max - p) / d; if (t0 > t1) swap(t0, t1); if (t0 > tfirst) tfirst = t0; if (t1 < tlast) tlast = t1; if (tmast < tfirst) return false; retrun true; } else { return (p > min) && (p < max); }}bool BoxRayIntersect(Vector Min, Vector Max, Vector P, Vector D, float maxt){ float mint = 0; if (!AxisIntersect(Min.x, Max.x, P.x, D.x, mint, maxt)) return false; if (!AxisIntersect(Min.y, Max.y, P.y, D.y, mint, maxt)) return false; if (!AxisIntersect(Min.z, Max.z, P.z, D.z, mint, maxt)) return false; return true;}this is code from the top of my head. I believe it is correct, but I've been drinking a bit...you can also add extra info, like the normal if intersection at point of intersection, ect... 0 Share this post Link to post Share on other sites
helix 301 Report post Posted February 8, 2005 The point of intersection would be nice but only for completeness. The bare minimum is to just return a boolean.oliii, that function doesn't appear to work for me. I don't really understand what you are doing so could you explain it a little bit? 0 Share this post Link to post Share on other sites
oliii 2196 Report post Posted February 8, 2005 picture worth a 1000 words/* missed intersection. -------------------- intervals [tymin, tymax] and [txmin, txmax] do not overlap (here, txmin > tymax) | | | | *P0 | | \ | | \tymin | | --------*-----+-----+----------------- \ | | \ | | -----------*--+-----+----------------- tymax \ | | \| | *txmin| |\ | | \ | | \ | | \ | | \| | *txmax | |\ | | \ | | *P1 we have intersection. ---------------------- intervals [tymin, tymax] and [txmin, txmax] overlap (tymin < txmax and tymax > txmin) *P0 | | \ | | \ | | \|txmin | * | |\ tymin --------------+-*----+----------------- | \ | | \ tymax --------------+----*-+----------------- | \| | *txmax | |\ | | \ | | \ | | *P1 | | in code, you start off with a ray where tfirst = 0.0f, and tlast = |P1 - P0|- first, you test intersection with the two X planes=> will give you [txmin, txmax]=> also, you notice that txmin > tfirst, and txmax < tlast, so then tfirst = txmin, tlast = txmax- second, you test with the Y planes=> will give you [tymin, tymax]=> here also, (tymin > tfirst), so tfirst = tymin=> (tymax < tlast), so tlast = tymax- finally, (tlast > tfirst). this is consistent. so we have an intersection.in case of no intersection-------------------------- first, you test intersection with the two X planes=> will give you [txmin, txmax]=> also, you notice that txmin > tfirst, and txmax < tlast, so then tfirst = txmin, tlast = txmax- second, you test with the Y planes=> will give you [tymin, tymax]=> but here, tymin is not > tfirst=> (tymax < tlast), so tlast = tymax- finally, now that we have tfirst = txmin, tlast = tymaxbut, (tfirst > tlast). discrepency, the interseciton is invalid.- bottom line-------------you keep testing intersections with pairs of planes along axes. -> you keep reducing the initial interval [tfirst, tlast] with the small values for both. -> As soon as the interval becomes invalidated, it means that the ray missed the box and there is no intersection./**/this is the code I have which works bool CRasteriser::ClipSegment(float min, float max, float a, float b, float d, float& t0, float& t1){ const float threshold = 1.0e-6f; if (Abs(d) < threshold) { if (d > 0.0f) { return !(b < min || a > max); } else { return !(a < min || b > max); } } float u0, u1; u0 = (min - a) / (d); u1 = (max - a) / (d); if (u0 > u1) { Swap(u0, u1); } if (u1 < t0 || u0 > t1) { return false; } t0 = Max(u0, t0); t1 = Min(u1, t1); if (t1 < t0) { return false; } return true; }bool CRasteriser::ClipSegment(Vector& A, Vector& B, const Vector& Min, const Vector& Max){ Vector S = A; Vector D = (B - A); float t0 = 0.0f, t1 = 1.0f; if (!ClipSegment(Min.x, Max.x, A.x, B.x, D.x, t0, t1)) { return false; } if (!ClipSegment(Min.y, Max.y, A.y, B.y, D.y, t0, t1)) { return false; } if (!ClipSegment(Min.z, Max.z, A.z, B.z, D.z, t0, t1)) { return false; } A = S + D * t0; B = S + D * t1; return true;}you can find the full featured code hereyou need to run demo 3 to run the code (press '3'). it is a ray rasteriser. But the first stage is clipping the ray to the voxel map area (a cube). The clipping basically clip the ray to the cube, so it calculates the points of intersection of the ray with the cube. to get the normals at points of collision, simply store the normals at tfirst and tlast (call them Nfirst, Nlast) everytime tfirst and tlast are changed. 0 Share this post Link to post Share on other sites
helix 301 Report post Posted February 8, 2005 Thanks for the detailed description. I've got my collision working now.I ...uh... had a bug with the coordinates I was using that was screwing it up... :) 0 Share this post Link to post Share on other sites