/****************************************************************************\ Copyright 1995 The University of North Carolina at Chapel Hill. All Rights Reserved. Permission to use, copy, modify and distribute this software and its documentation for educational, research and non-profit purposes, without fee, and without a written agreement is hereby granted, provided that the above copyright notice and the following three paragraphs appear in all copies. IN NO EVENT SHALL THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF NORTH CAROLINA HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. Permission to use, copy, modify and distribute this software and its documentation for educational, research and non-profit purposes, without fee, and without a written agreement is hereby granted, provided that the above copyright notice and the following three paragraphs appear in all copies. THE UNIVERSITY OF NORTH CAROLINA SPECIFICALLY DISCLAIM ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF NORTH CAROLINA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. The authors may be contacted via: US Mail: Jonathan Cohen Amitabh Varshney Department of Computer Science Department of Computer Science Sitterson Hall, CB #3175 State University of New York University of N. Carolina Stony Brook, NY 11794-4400, USA Chapel Hill, NC 27599-3175 Phone: (919)962-1749 Phone: (516)632-8446 EMail: cohenj@cs.unc.edu varshney@cs.sunysb.edu \****************************************************************************/ /*****************************************************************************\ intersect.c -- Description : Intersection test functions ---------------------------------------------------------------------------- $Source: /cvs/RenderPark/SE/Simplify/intersect.c,v $ $Revision: 1.1.1.1 $ $Date: 2000/04/06 15:35:32 $ $Author: philippe $ $Locker: $ \*****************************************************************************/ /*----------------------------- Local Includes -----------------------------*/ #include #include #include #include #include #include /*----------------------------- Local Constants -----------------------------*/ #define MAX_FUZZ (1e-2) #define MIN_FUZZ (1e-8) /*------------------------------ Local Macros -------------------------------*/ /*------------------------------- Local Types -------------------------------*/ /*------------------------ Local Function Prototypes ------------------------*/ int tri_tri_intersect(Triangle *tri1, Triangle *tri2, double fuzz_factor, int common_verts[3][2], int num_common_verts, int test_type); int edge_tri_intersect(Edge *edge, Triangle *tri, double fuzz_factor, int common_verts[2][2], int num_common_verts); int rawtri_rawtri_intersect(RawTriangle *tri1, RawTriangle *tri2, double fuzz_factor); int lineseg_rawtri_intersect(LineSegment *lineseg, RawTriangle *tri, double *t, double fuzz_factor); /*------------------------------ Local Globals ------------------------------*/ /*---------------------------------Functions-------------------------------- */ /*****************************************************************************\ @ test_self_intersect() ----------------------------------------------------------------------------- description : Find self intersections in a surface mesh. input : Surface mesh, its octree and octree data elements, some allocated space to store octree query results, and an intersection fuzz factor. output : Fuzz factor may be reduced based on how close the surface comes to self-intersecting notes : This routine filters out all triangles which share a common vertex. This is really incorrect, however. Triangles which share a common vertex or edge should employ slightly modified intersection tests, not be totally eliminated from consideration. \*****************************************************************************/ void test_self_intersect(Surface *model, Octree *tree, OctreeData *octdata, OctreeData **query_result, double *fuzz_factor) { int i, j; int query_count; Triangle *tri1, *tri2; int nearby, intersecting; int intersect, done; nearby = intersecting = 0; *fuzz_factor = -MAX_FUZZ; for (i=0; inum_tris; i++) { tri1 = &(model->tris[i]); #ifdef USE_TRIOCTREE trioctree_tri_range_query(tree, tri1, query_result, &query_count); #else octree_range_query(tree, octdata[i].bbox, query_result, &query_count); #endif for (j=0; jdata); #endif if (tri2->id <= tri1->id) continue; nearby++; done = FALSE; while (done == FALSE) { intersect = index_filtered_tri_tri_intersect(tri1, tri2, *fuzz_factor, SURFACE_VS_ITSELF); if (intersect == FALSE) done = TRUE; else { *fuzz_factor /= 2.0; if (*fuzz_factor > -MIN_FUZZ) { fprintf(stderr, "intersecting pair: (tri #%d, tri #%d)\n", tri1->id, tri2->id); intersecting++; *fuzz_factor = -MIN_FUZZ; done = TRUE; } } } } } fprintf(stderr, "Found %d pairs of nearby triangles\n", nearby); fprintf(stderr, "Found %d pairs of intersecting triangles\n", intersecting); fprintf(stderr, "Final fuzz factor: %g\n", *fuzz_factor); fprintf(stderr, "\n"); return; } /** End of test_self_intersect() **/ /*****************************************************************************\ @ edge_offsets_intersect() ----------------------------------------------------------------------------- description : Intersect a line segment with the two offset surfaces. input : Offset surface octrees, space for query results, two vertices defining the line segment, intersection fuzz factor. output : TRUE if the line segment intersects an offset surface, FALSE otherwise. notes : If an edge shares both its vertices with the offset surface, it's possible for the edge to be totally outside the offset volume, with no other intersections appearing. This function will still return FALSE. This is okay, however, because this call just prunes down the number of candidate edges accepted for generating candidate triangles. This problem will be dealt with properly when considering the candidate triangles. \*****************************************************************************/ int edge_offsets_intersect(Octree *outer_offset, Octree *inner_offset, OctreeData **query_result, Edge *edge, double fuzz_factor) { int i; int query_count; Triangle *tri; #ifndef USE_TRIOCTREE Extents edge_bbox; double fuzz_width; #endif /* test for interesection with outer offset */ #ifdef USE_TRIOCTREE trioctree_edge_range_query(outer_offset, edge, query_result, &query_count); #else for (i=0; i<3; i++) { edge_bbox[LO][i] = FMIN(edge->verts[0]->coord[i], edge->verts[1]->coord[i]); edge_bbox[HI][i] = FMAX(edge->verts[0]->coord[i], edge->verts[1]->coord[i]); if (fuzz_factor < 0.0) { fuzz_width = (edge_bbox[HI][i] - edge_bbox[LO][i]) * -fuzz_factor; edge_bbox[LO][i] -= fuzz_width; edge_bbox[HI][i] += fuzz_width; } } octree_range_query(outer_offset, edge_bbox, query_result, &query_count); #endif for (i=0; idata); #endif if (coord_filtered_edge_tri_intersect(edge, tri, fuzz_factor)) return TRUE; } /* test for intersection with inner offset */ #ifdef USE_TRIOCTREE trioctree_edge_range_query(inner_offset, edge, query_result, &query_count); #else octree_range_query(inner_offset, edge_bbox, query_result, &query_count); #endif for (i=0; idata); #endif if (coord_filtered_edge_tri_intersect(edge, tri, fuzz_factor)) return TRUE; } return FALSE; } /** End of edge_offsets_intersect() **/ /*****************************************************************************\ @ tri_offsets_intersect() ----------------------------------------------------------------------------- description : Test a triangle for intersection with the two offset surfaces. input : Triangle, offset surface octrees, space for query results, intersection fuzz factor. output : TRUE if the triangle intersects an offset surface, FALSE otherwise. notes : If a triangle shares all 3 vertices with an offset surface, it's possible for it to lie totally outside the offset volume without any further intersections. However, among the set of triangles used to fill a hole, at least one must either share an edge with the offset volume or intersect the offset volume in this case. So this function may return FALSE for triangles which share 3 vertices with an offset surface (and don't share an edge), knowing that another triangle will prevent the hole from being filled this way. \*****************************************************************************/ int tri_offsets_intersect(Triangle *tri, Octree *outer_offset, Octree *inner_offset, OctreeData **query_result, double fuzz_factor) { int i; #ifndef USE_TRIOCTREE Extents tri_bbox; double fuzz_width; #endif Triangle *tri2; int query_count; /* test the outer offset surface */ #ifdef USE_TRIOCTREE trioctree_tri_range_query(outer_offset, tri, query_result, &query_count); #else for (i=0; i<3; i++) { tri_bbox[LO][i] = FMIN(FMIN(tri->verts[0]->coord[i], tri->verts[1]->coord[i]), tri->verts[2]->coord[i]); tri_bbox[HI][i] = FMAX(FMAX(tri->verts[0]->coord[i], tri->verts[1]->coord[i]), tri->verts[2]->coord[i]); if (fuzz_factor < 0.0) { fuzz_width = (tri_bbox[HI][i] - tri_bbox[LO][i]) * -fuzz_factor; tri_bbox[LO][i] -= fuzz_width; tri_bbox[HI][i] += fuzz_width; } } octree_range_query(outer_offset, tri_bbox, query_result, &query_count); #endif for (i=0; idata); #endif if (coord_filtered_tri_tri_intersect(tri, tri2, fuzz_factor, SURFACE_VS_OUTER)) return TRUE; } #ifdef USE_TRIOCTREE trioctree_tri_range_query(inner_offset, tri, query_result, &query_count); #else /* test the inner offset surface */ octree_range_query(inner_offset, tri_bbox, query_result, &query_count); #endif for (i=0; idata); #endif if (coord_filtered_tri_tri_intersect(tri, tri2, fuzz_factor, SURFACE_VS_INNER)) return TRUE; } return FALSE; } /** End of tri_offsets_intersect() **/ /*****************************************************************************\ @ tri_model_interference() ----------------------------------------------------------------------------- description : Tests whether a candidate triangle has any non-adjacent intersections with a surface mesh, excluding triangles which are adjacent to a particular given vertex. input : Triangle to test, vertex to indicate which mesh triangles to ignore, surface mesh octree, space for query result, intersection fuzz factor. output : TRUE if the triangle interferes with the surface, FALSE otherwise. notes : The vertex is typically a vertex we are considering for removal and the triangle is one we are considering as a candidate to fill the hole. We test for intersection with the other hole candidates seperately. \*****************************************************************************/ int tri_model_interference(Triangle *tri, Vertex *vert, Octree *model_octree, OctreeData **query_result, double fuzz_factor) { int i; #ifndef USE_TRIOCTREE Extents tri_bbox; double fuzz_width; #endif Triangle *tri2; int query_count; #ifdef USE_TRIOCTREE trioctree_tri_range_query(model_octree, tri, query_result, &query_count); #else for (i=0; i<3; i++) { tri_bbox[LO][i] = FMIN(FMIN(tri->verts[0]->coord[i], tri->verts[1]->coord[i]), tri->verts[2]->coord[i]); tri_bbox[HI][i] = FMAX(FMAX(tri->verts[0]->coord[i], tri->verts[1]->coord[i]), tri->verts[2]->coord[i]); if (fuzz_factor < 0.0) { fuzz_width = (tri_bbox[HI][i] - tri_bbox[LO][i]) * -fuzz_factor; tri_bbox[LO][i] -= fuzz_width; tri_bbox[HI][i] += fuzz_width; } } octree_range_query(model_octree, tri_bbox, query_result, &query_count); #endif for (i=0; idata); #endif if ((tri2->verts[0] == vert) || (tri2->verts[1] == vert) || (tri2->verts[2] == vert)) continue; if (index_filtered_tri_tri_intersect(tri, tri2, fuzz_factor, SURFACE_VS_ITSELF)) return TRUE; } return FALSE; } /** End of tri_model_interference() **/ /*****************************************************************************\ @ tri_solution_interference() ----------------------------------------------------------------------------- description : Test to see if a candidate triangle to be used in filling a hole intersects with any of the other candidate triangles already selected. input : Hole being filled, candidate triangle, intersection fuzz factor. output : TRUE if the triangle intersects one of the other solution triangles, FALSE otherwise. notes : \*****************************************************************************/ int tri_solution_interference(Hole *hole, Triangle *tri, double fuzz_factor) { int i; for (i=0; i < *hole->num_solution_tris_ptr; i++) if (index_filtered_tri_tri_intersect(tri, hole->solution_tris[i], fuzz_factor, SURFACE_VS_ITSELF)) return TRUE; return FALSE; } /** End of tri_solution_interference() **/ /*****************************************************************************\ @ edge_tubes_intersect() ----------------------------------------------------------------------------- description : Intersect an edge with a set of border tubes. input : Two vertices defining the edge, border tubes octree, space for query result, and intersection fuzz factor. output : TRUE if the edge intersects the tubes, FALSE otherwise. notes : It is not necessary to filter out shared vertices, because the border tube is constructed around the border edges and then offset. Even if a vertex of the border tube cannot be offset, it does not lie exactly on a vertex of a border edge. \*****************************************************************************/ int edge_tubes_intersect(Edge *edge, Octree *tubes, OctreeData **query_result, double fuzz_factor) { int i; #ifndef USE_TRIOCTREE Extents edge_bbox; double fuzz_width; #endif int query_count; Triangle *tri; #ifdef USE_TRIOCTREE trioctree_edge_range_query(tubes, edge, query_result, &query_count); #else for (i=0; i<3; i++) { edge_bbox[LO][i] = FMIN(edge->verts[0]->coord[i], edge->verts[1]->coord[i]); edge_bbox[HI][i] = FMAX(edge->verts[0]->coord[i], edge->verts[1]->coord[i]); if (fuzz_factor < 0.0) { fuzz_width = (edge_bbox[HI][i] - edge_bbox[LO][i]) * -fuzz_factor; edge_bbox[LO][i] -= fuzz_width; edge_bbox[HI][i] += fuzz_width; } } octree_range_query(tubes, edge_bbox, query_result, &query_count); #endif for (i=0; idata); #endif if (unfiltered_edge_tri_intersect(edge, tri, fuzz_factor)) return TRUE; } return FALSE; } /** End of edge_tubes_intersect() **/ /*****************************************************************************\ @ index_filtered_tri_tri_intersect() ----------------------------------------------------------------------------- description : input : output : notes : \*****************************************************************************/ int index_filtered_tri_tri_intersect(Triangle *tri1, Triangle *tri2, double fuzz_factor, int test_type) { int intersect, num_common_verts; int common_verts[3][2]; num_common_verts = get_common_index_verts(tri1, tri2, common_verts); intersect = tri_tri_intersect(tri1, tri2, fuzz_factor, common_verts, num_common_verts, test_type); return intersect; } /** End of index_filtered_tri_tri_intersect() **/ /*****************************************************************************\ @ coord_filtered_tri_tri_intersect() ----------------------------------------------------------------------------- description : input : output : notes : \*****************************************************************************/ int coord_filtered_tri_tri_intersect(Triangle *tri1, Triangle *tri2, double fuzz_factor, int test_type) { int intersect, num_common_verts; int common_verts[3][2]; num_common_verts = get_common_coord_verts(tri1, tri2, common_verts); intersect = tri_tri_intersect(tri1, tri2, fuzz_factor, common_verts, num_common_verts, test_type); return intersect; } /** End of coord_filtered_tri_tri_intersect() **/ /*****************************************************************************\ @ coord_filtered_edge_tri_intersect() ----------------------------------------------------------------------------- description : input : output : notes : \*****************************************************************************/ int coord_filtered_edge_tri_intersect(Edge *edge, Triangle *tri, double fuzz_factor) { int intersect, num_common_verts; int common_verts[2][2]; num_common_verts = get_common_coord_edge_tri_verts(edge, tri, common_verts); intersect = edge_tri_intersect(edge, tri, fuzz_factor, common_verts, num_common_verts); return intersect; } /** End of coord_filtered_edge_tri_intersect() **/ /*****************************************************************************\ @ unfiltered_edge_tri_intersect() ----------------------------------------------------------------------------- description : input : output : notes : \*****************************************************************************/ int unfiltered_edge_tri_intersect(Edge *edge, Triangle *tri, double fuzz_factor) { int intersect, num_common_verts; int common_verts[2][2]; num_common_verts = 0; intersect = edge_tri_intersect(edge, tri, fuzz_factor, common_verts, num_common_verts); return intersect; } /** End of unfiltered_edge_tri_intersect() **/ /*****************************************************************************\ @ edge_tri_intersect() ----------------------------------------------------------------------------- description : input : output : notes : \*****************************************************************************/ int edge_tri_intersect(Edge *edge, Triangle *tri, double fuzz_factor, int common_verts[2][2], int num_common_verts) { LineSegment lineseg; RawTriangle rawtri; int intersect; double t; switch(num_common_verts) { case 0: VERTS_TO_LINESEG(edge->verts[0], edge->verts[1], lineseg); tri_to_rawtri(tri, &rawtri); intersect = lineseg_rawtri_intersect(&lineseg, &rawtri, &t, fuzz_factor); break; case 1: /* If they are coplanar and overlapping in 2D, this is an intersection, but it's not an interpenetration condition (and this function is currently only called to test a surface edge vs. an offset or border tube face). */ intersect = FALSE; break; case 2: /* Again, not an interpenetration condition */ intersect = FALSE; break; default: fprintf(stderr, "edge_tri_intersect: invalid number of common verts (%d)\n", num_common_verts); exit(-1); } return intersect; } /** End of edge_tri_intersect() **/ /*****************************************************************************\ @ tri_tri_intersect() ----------------------------------------------------------------------------- description : Triangle intersection routine with special filtering for common vertices and edges (the triangles must share exactly the same vertices -- the structure addresses are compared, not the vertex coordinates). Naturally, shared vertices and edges do not count as intersections. input : Two triangles and an intersection fuzz factor. output : TRUE if the triangles intersect, FALSE otherwise. notes : \*****************************************************************************/ int tri_tri_intersect(Triangle *tri1, Triangle *tri2, double fuzz_factor, int common_verts[3][2], int num_common_verts, int test_type) { RawTriangle rawtri1, rawtri2; LineSegment lineseg; double t; int intersect; double cos_theta; Edge *offset_edge; Triangle *other_offset_tri; Vertex *tri_vert, *offset_vert1, *offset_vert2; double tri_vert_dot1, tri_vert_dot2; double offset_vert1_dot, offset_vert2_dot; int and_test; int i; intersect = FALSE; switch(num_common_verts) { case 0: /* no known degeneracies -- do entire triangle-triangle intersection */ tri_to_rawtri(tri1, &rawtri1); tri_to_rawtri(tri2, &rawtri2); intersect = rawtri_rawtri_intersect(&rawtri1, &rawtri2, fuzz_factor); break; case 1: /* single vertex in common -- intersect the edge opposite the vertex on each triangle with the other triangle */ switch(common_verts[0][0]) { case 0: VERTS_TO_LINESEG(tri1->verts[1], tri1->verts[2], lineseg); break; case 1: VERTS_TO_LINESEG(tri1->verts[0], tri1->verts[2], lineseg); break; case 2: VERTS_TO_LINESEG(tri1->verts[0], tri1->verts[1], lineseg); break; default: fprintf(stderr, "tri_tri_intersect: invalid common vert\n"); exit(1); } tri_to_rawtri(tri2, &rawtri2); intersect = lineseg_rawtri_intersect(&lineseg, &rawtri2, &t, fuzz_factor); if (intersect == TRUE) break; switch(common_verts[0][1]) { case 0: VERTS_TO_LINESEG(tri2->verts[1], tri2->verts[2], lineseg); break; case 1: VERTS_TO_LINESEG(tri2->verts[0], tri2->verts[2], lineseg); break; case 2: VERTS_TO_LINESEG(tri2->verts[0], tri2->verts[1], lineseg); break; default: fprintf(stderr, "tri_tri_intersect: invalid common vert\n"); exit(1); } tri_to_rawtri(tri1, &rawtri1); intersect = lineseg_rawtri_intersect(&lineseg, &rawtri1, &t, fuzz_factor); break; case 2: switch (test_type) { case SURFACE_VS_ITSELF: /* The two triangles share an edge. So find the angle between the two triangles (or cos(angle)) and use that to decide if they are intersecting. */ cos_theta = DOTPROD3(tri1->plane_eq, tri2->plane_eq); /* adjust if the orientation of the triangles disagree -- note that this won't happen if the two triangles are from the same surface, but if they are on different surfaces with a coincident edge, they may be treating the edge in the same direction instead of opposite directions */ if (!(((common_verts[1][0] == (common_verts[0][0] + 1) % 3) && (common_verts[0][1] == (common_verts[1][1] + 1) % 3)) || ((common_verts[0][0] == (common_verts[1][0] + 1) % 3) && (common_verts[1][1] == (common_verts[0][1] + 1) % 3)))) { fprintf(stderr, "tri_tri_intersect: shared edge orientation error\n"); exit(-1); /* cos_theta *= -1.0; */ } /* Now use the fuzz_factor and cos_theta to determine if we've got an intersection. Even with a positive fuzz factor, I think we should report an intersection if the triangles are exactly coplanar and overlapping. If the fuzz_factor is negative, we report an intersection if we are within fuzz_factor percent of 180 degrees (but measured on the interval (0,1), probably not exactly the same as measuring in degrees). */ if (fuzz_factor >= 0) intersect = ((cos_theta <= -1) ? TRUE : FALSE); else intersect = ((cos_theta <= (-1-fuzz_factor)) ? TRUE : FALSE); break; case SURFACE_VS_OUTER: case SURFACE_VS_INNER: /* In these cases, we must make sure that the triangle lies on the interior of the offset volume. If not, we return an intersection, causing this triangulation to fail. */ for (i=0, offset_edge = NULL; i<3; i++) if (((common_verts[0][1] == i) && (common_verts[1][1] == ((i+1)%3))) || ((common_verts[0][1] == ((i+1)%3)) && (common_verts[1][1] == i))) offset_edge = tri2->edges[i]; if (offset_edge == NULL) { fprintf(stderr, "tri_tri_intersect: couldn't find offset edge\n"); exit(-1); } if (offset_edge->tris[0] == tri2) other_offset_tri = offset_edge->tris[1]; else if (offset_edge->tris[1] == tri2) other_offset_tri = offset_edge->tris[0]; else { fprintf(stderr, "tri_tri_intersect: couldn't find other offset tri\n"); exit(-1); } for (i=0, tri_vert = NULL; i<3; i++) if ((common_verts[0][0] != i) && (common_verts[1][0] != i)) tri_vert = tri1->verts[i]; if (tri_vert == NULL) { fprintf(stderr, "tri_tri_intersect: couldn't find tri vert\n"); exit(-1); } tri_vert_dot1 = DOTPROD3(tri_vert->coord, tri2->plane_eq); if (test_type == SURFACE_VS_OUTER) tri_vert_dot1 *= -1.0; if (other_offset_tri != NULL) /* (i.e. offset_edge not a border edge) */ { for (i=0, offset_vert1 = NULL; i<3; i++) if ((tri2->verts[i] != offset_edge->verts[0]) && (tri2->verts[i] != offset_edge->verts[1])) offset_vert1 = tri2->verts[i]; for (i=0, offset_vert2 = NULL; i<3; i++) if ((other_offset_tri->verts[i] != offset_edge->verts[0]) && (other_offset_tri->verts[i] != offset_edge->verts[1])) offset_vert2 = other_offset_tri->verts[i]; offset_vert1_dot = DOTPROD3(offset_vert1->coord, other_offset_tri->plane_eq); offset_vert2_dot = DOTPROD3(offset_vert2->coord, tri2->plane_eq); if (test_type == SURFACE_VS_OUTER) { offset_vert1_dot *= -1.0; offset_vert2_dot *= -1.0; } and_test = FALSE; if ((offset_vert1_dot >= 0.0) || (offset_vert2_dot >= 0.0)) and_test = TRUE; tri_vert_dot2 = DOTPROD3(tri_vert->coord, other_offset_tri->plane_eq); if (test_type == SURFACE_VS_OUTER) tri_vert_dot2 *= -1.0; if (((and_test == TRUE) && ((tri_vert_dot1 >= 0.0) && (tri_vert_dot2 >= 0.0))) || ((and_test == FALSE) && ((tri_vert_dot1 >= 0.0) || (tri_vert_dot2 >= 0.0)))) intersect = FALSE; else intersect = TRUE; } else { if (tri_vert_dot1 >= 0.0) intersect = FALSE; else intersect = TRUE; } break; default: fprintf(stderr, "tri_tri_intersect: invalid test_type\n"); exit(-1); } break; case 3: switch (test_type) { case SURFACE_VS_ITSELF: /* identical triangles -- they intersect */ intersect = TRUE; break; case SURFACE_VS_OUTER: case SURFACE_VS_INNER: /* triangle lies on offset triangle -- this seems valid enough */ intersect = FALSE; break; } break; default: fprintf(stderr, "tri_tri_intersect: invalid number of common verts\n"); exit(1); break; } return intersect; } /** End of tri_tri_intersect() **/ /*****************************************************************************\ @ rawtri_rawtri_intersect() ----------------------------------------------------------------------------- description : Intersect two arbitrary triangles input : 2 triangles, intersection fuzz factor. fuzz_factor specifies how fuzzy the intersection should be. negative: returns MORE intersections than non-fuzzy positive: returns FEWER intersections than non-fuzzy output : TRUE if they intersect, FALSE otherwise. notes : assumes cases with shared edges or vertices have already been filtered out \*****************************************************************************/ int rawtri_rawtri_intersect(RawTriangle *tri1, RawTriangle *tri2, double fuzz_factor) { int i, j; LineSegment edges[2][3]; double t; for (i=0; i<3; i++) { j= (i+1) % 3; VEC3_ASN_OP(edges[0][i].endpoints[0], =, tri1->verts[i]); VEC3_ASN_OP(edges[0][i].endpoints[1], =, tri1->verts[j]); VEC3_ASN_OP(edges[1][i].endpoints[0], =, tri2->verts[i]); VEC3_ASN_OP(edges[1][i].endpoints[1], =, tri2->verts[j]); } for (i=0; i<3; i++) { if (lineseg_rawtri_intersect(&(edges[0][i]), tri2, &t, fuzz_factor)) return TRUE; if (lineseg_rawtri_intersect(&(edges[1][i]), tri1, &t, fuzz_factor)) return TRUE; } return FALSE; } /** End of rawtri_rawtri_intersect() **/ /*****************************************************************************\ @ lineseg_rawtri_intersect() ----------------------------------------------------------------------------- description : intersects a line segment with a triangle input : line segment, triangle, fuzz_factor specifies how fuzzy the intersection should be. negative: returns MORE intersections than non-fuzzy positive: returns FEWER intersections than non-fuzzy output : If line segment intersects triangle, t indicates where on line segment (0-1), and return value is TRUE. Otherwise, return value is FALSE. notes : 1. Assumes shared vertices and edges have already been filtered out 2. The line/triangle parallel case is really incorrect -- this should actually jump down to a 2D test if the distance between the line and the triangle plane is small enough. \*****************************************************************************/ int lineseg_rawtri_intersect(LineSegment *lineseg, RawTriangle *tri, double *t, double fuzz_factor) { Point ptmp; double dtmp, N_dot_v; int i, j, k; Point u, v; Point abs_norm; double alpha, beta; /* first find the intersection of the line ray with the triangle plane */ /* _ _ plane equation is N.x = D, where N = (A,B,C) = tri->plane_eq[0,1,2] _ _ given edge between p and q, parametric form of a point on the line is: _ _ _ _ _ (p + tv), t in [0,1], and v = q - p _ _ given point on line, (p + tv), find t value of intersection _ _ _ N.(p + tv) = D, so _ _ D - N.p t = ------- _ _ N.v */ VEC3_V_OP_V(v, lineseg->endpoints[1], -, lineseg->endpoints[0]); N_dot_v = DOTPROD3(tri->plane_eq, v); if (N_dot_v == 0) /* ray & triangle are parallel => no intersection */ { *t = MAXDOUBLE; return(FALSE); } *t = ((tri->plane_eq[3] - DOTPROD3(lineseg->endpoints[0], tri->plane_eq)) / N_dot_v); if ((*t < fuzz_factor) || (*t > (1-fuzz_factor))) { *t = MAXDOUBLE; return (FALSE); } /* compute the intersection point in ptmp */ VEC3_V_OP_V_OP_S(ptmp, lineseg->endpoints[0], +, v, *, (*t)); /* now see if ptmp lies inside the triangle */ for(i = 0; i < 3; i++) abs_norm[i] = fabs(tri->plane_eq[i]); dtmp=FMAX(abs_norm[X], FMAX(abs_norm[Y], abs_norm[Z])); if (dtmp == abs_norm[X]) { i = 0; j = 1; k = 2; } else if (dtmp == abs_norm[Y]) { i = 1; j = 2; k = 0; } else /*(dtmp == abs_norm[Z])*/{ i = 2; j = 0; k = 1; } u[0] = ptmp[j] - tri->verts[0][j]; v[0] = ptmp[k] - tri->verts[0][k]; u[1] = tri->verts[1][j] - tri->verts[0][j]; v[1] = tri->verts[1][k] - tri->verts[0][k]; u[2] = tri->verts[2][j] - tri->verts[0][j]; v[2] = tri->verts[2][k] - tri->verts[0][k]; dtmp = 1.0 / (u[1]*v[2] - v[1]*u[2]); alpha = (u[0]*v[2] - v[0]*u[2]) * dtmp; beta = (u[1]*v[0] - v[1]*u[0]) * dtmp; if ((alpha >= fuzz_factor) && (beta >= fuzz_factor) && (alpha + beta <= 1-fuzz_factor)) { if ((*t >= fuzz_factor) && (*t <= 1-fuzz_factor)) return(TRUE); } else *t = MAXDOUBLE; return(FALSE); } /** End of lineseg_rawtri_intersect() **/ /*****************************************************************************\ $Log: intersect.c,v $ Revision 1.1.1.1 2000/04/06 15:35:32 philippe Initial CVS release Revision 1.9 1997/04/10 20:10:46 cohenj Added Amitabh's name to credits Revision 1.8 1996/11/15 20:34:02 cohenj Made line segment/triangle intersection routine more readable Revision 1.7 1996/08/15 01:47:12 cohenj fixed bug in trioctree query call parameters * Revision 1.6 96/04/19 03:33:29 cohenj * 1. Moved test_self_intesect() to this file. * 2. Added fuzz width around all query boxes. * 3. Removed all signs of unfiltered surface intersections, the old * minside calculation, and the old offset method. * 4. Moved some functions around (so now diff doesn't give very * meaningful results -- oh, well) * * Revision 1.5 96/04/18 19:13:33 cohenj * 1. Reorganized the filtered intersection tests. * 2. Added filtering for triangle vs. offset intersections. * This also included a volume test for triangles which share * an edge with the offset surface * 3. Added some code for testing trioctree data structure * * Revision 1.4 96/04/08 18:49:56 cohenj * added procedure comments and copyright * * Revision 1.3 95/10/16 16:29:41 cohenj * added tri_model_interference() and edge_tubes_intersect() functions. * * Revision 1.2 95/09/30 06:11:10 cohenj * almost done writing revision 1 -- just need the code to update * the model after a vertex is removed and finalize the model after removing * all vertices in the queue. * * Revision 1.1 95/09/15 16:28:21 cohenj * Initial revision * * Revision 1.1 1995/08/30 20:57:04 cohenj * Initial revision * * Revision 1.1 1995/08/30 20:57:04 cohenj * Initial revision * \*****************************************************************************/