   would this work?
  I'm trying to determine, given two triangles A and B and an occluding triangle O, if A is visible from B, i.e. if any ray cast between any two points along the two triangle surfaces will intersect with the occluder or not.the way I plan on doing this is by constructing a frustum for each endpoint of triangle A with the occluder triangle, then doing a simple point in frustum test for each endpoint of B for these three frustums.would this work for all cases?struct Plane3d{   Vector3 normal;   float distance;};class Frustum{public:   Frustum(const Vector3& p, const Triangle& t)   { for(int i = 0; i < 3; ++i) {    planes.normal = (t.point[(i+1)%2] - t.point).cross(t.point - p).normalize();    planes.distance = planes.normal.dot(p); }    }   bool isPointInside(const Vector3& v)   { for(int i = 0; i < 3; ++i) {    if(planes.normal.dot(v) < planes.distance)  return false; } return true;   }private:   Plane3d planes[3];};struct Triangle{   Vector3 point[3];};bool isVisible(const Triangle& a, const Triangle& b, const Triangle& o){   for(int i = 0; i < 3; ++i)   { Frustum f(a.point, o); for(int j = 0; j < 3; ++j) {    if(!f.isPointInside(b.point[j]))  return true; }   }   return false;}dot = dot productcross = cross product   
Quote:would this work for all cases?I would say no. I do have a question though. If a point falls within the frustum created from a point and the edges of the occluder triangle (and is on the opposite side of the occluder plane, which it doesn't look like you're checking for), then that point would *not* be visible from the query point, yet it looks like you're returning true in this case. Am I missing something?   ;  how fast does it have to be?hmmm.... compute convex hull of A and B, and test intersection with occluder using the SAT?In fact, constructing the convex hull would be pretty fast. Start with a pyramid, using A as the base, and one of B's vertex as the tip. Then expand that pyramid into the convex hull using the two remaining vertices of B. Then the collision detection with the occluder itself is pretty easy. as a bonus, that could extend easily to any type of convex polygon (either for A, B and O).   ;Quote:Original post by jykQuote:would this work for all cases?I would say no. I do have a question though. If a point falls within the frustum created from a point and the edges of the occluder triangle (and is on the opposite side of the occluder plane, which it doesn't look like you're checking for), then that point would *not* be visible from the query point, yet it looks like you're returning true in this case. Am I missing something?If the point isn't inside the frustum then it must be visible:bool isVisible(const Triangle& a, const Triangle& b, const Triangle& o){   for(int i = 0; i < 3; ++i)   { Frustum f(a.point, o); for(int j = 0; j < 3; ++j) {    if(!f.isPointInside(b.point[j]))  return true; }   }   return false;}I think you missed the ! before isPointInside.I was forgetting to check against the occluder triangle, but you would just need to add another plane to the frustum:class Frustum{public:   Frustum(const Vector3& p, const Triangle& t)   { for(int i = 0; i < 3; ++i) {    planes.normal = (t.point[(i+1)%2] - t.point).cross(t.point - p).normalize();    planes.distance = planes.normal.dot(p); } planes[3].normal = (t.point[1] - t.point[0]).cross(t.point[2] - t.point[0]).normalize(); planes[3].distance = planes[3].normal.dot(t.point[0]);    }   bool isPointInside(const Vector3& v)   { for(int i = 0; i < 4; ++i) {    if(planes.normal.dot(v) < planes.distance)  return false; } return true;   }private:   Plane3d planes[4];};If this worked could you not construct a beam tree for each point of triangle A with every occluding triangle and then clip triangle B to this tree to determine if it was visible? then do this three times for each vertex?   ;Quote:I think you missed the ! before isPointInside.Yup, I think I did :|   ;  I don't understand.Wouldn't this algorithm prevent you from taking advantage of hardware acceleration (i.e. vertex buffers and batch draws of indexed primitives)?I suppose if massive numbers of triangles could be culled by a single occlusion test this might be useful.However, your content development people would need to carefully generate appropriate occluding geometry for you, I don't think you could get away with just using the sources meshes directly (as their would be too many triangle against triangle checks to perform per frame).Are you trying to use this for a portal culling system?   