BICPL: ray_bintree.c Source File

00001 /* ---------------------------------------------------------------------------- 00002 @COPYRIGHT : 00003 Copyright 1993,1994,1995 David MacDonald, 00004 McConnell Brain Imaging Centre, 00005 Montreal Neurological Institute, McGill University. 00006 Permission to use, copy, modify, and distribute this 00007 software and its documentation for any purpose and without 00008 fee is hereby granted, provided that the above copyright 00009 notice appear in all copies. The author and McGill University 00010 make no representations about the suitability of this 00011 software for any purpose. It is provided "as is" without 00012 express or implied warranty. 00013 ---------------------------------------------------------------------------- */ 00014 00015 #include <volume_io/internal_volume_io.h> 00016 #include <bicpl/data_structures.h> 00017 #include <bicpl/geom.h> 00018 00019 #ifndef lint 00020 static char rcsid[] = "$Header: /software/source//libraries/bicpl/Data_structures/ray_bintree.c,v 1.18 2000/02/06 15:30:11 stever Exp $"; 00021 #endif 00022 00023 private void recursive_intersect_ray( 00024 Point *origin, 00025 Vector *direction, 00026 Real t_min, 00027 Real t_max, 00028 bintree_node_struct *node, 00029 object_struct *object, 00030 int *obj_index, 00031 Real *closest_dist, 00032 int *n_intersections, 00033 Real *distances[] ); 00034 00035 private int n_nodes_searched = 0; 00036 private int n_objects_searched = 0; 00037 00038 /* ----------------------------- MNI Header ----------------------------------- 00039 @NAME : print_bintree_stats 00040 @INPUT : n_objects 00041 @OUTPUT : 00042 @RETURNS : 00043 @DESCRIPTION: Prints information on the bintree search structure. 00044 @METHOD : 00045 @GLOBALS : 00046 @CALLS : 00047 @CREATED : Jun 21, 1995 David MacDonald 00048 @MODIFIED : 00049 ---------------------------------------------------------------------------- */ 00050 00051 public void print_bintree_stats( 00052 int n_objects ) 00053 { 00054 print( "Nodes %g ", (Real) n_nodes_searched / (Real) n_objects ); 00055 print( "Objects %g\n", (Real) n_objects_searched / (Real) n_objects ); 00056 } 00057 00058 /* ----------------------------- MNI Header ----------------------------------- 00059 @NAME : intersect_ray_with_bintree 00060 @INPUT : origin 00061 direction 00062 bintree 00063 @OUTPUT : object 00064 obj_index 00065 dist 00066 distances 00067 @RETURNS : number of intersections 00068 @DESCRIPTION: Tests if the ray intersects the objects in the bintree. 00069 @METHOD : 00070 @GLOBALS : 00071 @CALLS : 00072 @CREATED : 1993 David MacDonald 00073 @MODIFIED : 00074 ---------------------------------------------------------------------------- */ 00075 00076 public int intersect_ray_with_bintree( 00077 Point *origin, 00078 Vector *direction, 00079 bintree_struct_ptr bintree, 00080 object_struct *object, 00081 int *obj_index, 00082 Real *dist, 00083 Real *distances[] ) 00084 { 00085 int n_intersections; 00086 Real t_min, t_max; 00087 00088 n_intersections = 0; 00089 if( obj_index != (int *) NULL ) 00090 *obj_index = -1; 00091 00092 if( ray_intersects_range( &bintree->range, origin, direction, 00093 &t_min, &t_max ) ) 00094 { 00095 recursive_intersect_ray( origin, direction, t_min, t_max, 00096 bintree->root, object, obj_index, dist, 00097 &n_intersections, distances ); 00098 } 00099 00100 return( n_intersections ); 00101 } 00102 00103 /* ----------------------------- MNI Header ----------------------------------- 00104 @NAME : recursive_intersect_ray 00105 @INPUT : origin 00106 direction 00107 t_min 00108 t_max 00109 node 00110 @OUTPUT : object 00111 obj_index 00112 closest_dist 00113 n_intersections 00114 distances 00115 @RETURNS : 00116 @DESCRIPTION: Traverses the bintree testing for ray intersection. 00117 @METHOD : 00118 @GLOBALS : 00119 @CALLS : 00120 @CREATED : Jun 21, 1995 David MacDonald 00121 @MODIFIED : 00122 ---------------------------------------------------------------------------- */ 00123 00124 private void recursive_intersect_ray( 00125 Point *origin, 00126 Vector *direction, 00127 Real t_min, 00128 Real t_max, 00129 bintree_node_struct *node, 00130 object_struct *object, 00131 int *obj_index, 00132 Real *closest_dist, 00133 int *n_intersections, 00134 Real *distances[] ) 00135 { 00136 BOOLEAN test_child, searching_left; 00137 int i, n_objects, *object_list, axis_index; 00138 bintree_node_struct *left_child, *right_child; 00139 Real delta, left_limit, right_limit; 00140 Real t, t_min_child, t_max_child; 00141 00142 if( distances == NULL && obj_index != NULL && 00143 *obj_index >= 0 && *closest_dist < t_min ) 00144 return; 00145 00146 ++n_nodes_searched; 00147 00148 if( bintree_node_is_leaf( node ) ) 00149 { 00150 n_objects = get_bintree_leaf_objects( node, &object_list ); 00151 00152 for_less( i, 0, n_objects ) 00153 { 00154 ++n_objects_searched; 00155 00156 intersect_ray_object( origin, direction, 00157 object, object_list[i], obj_index, 00158 closest_dist, n_intersections, 00159 distances ); 00160 } 00161 } 00162 else 00163 { 00164 axis_index = get_node_split_axis( node ); 00165 delta = (Real) Vector_coord( *direction, axis_index ); 00166 00167 if( delta > 0.0 ) 00168 searching_left = TRUE; 00169 else 00170 searching_left = FALSE; 00171 00172 for_less( i, 0, 2 ) 00173 { 00174 t_min_child = t_min; 00175 t_max_child = t_max; 00176 00177 if( searching_left && get_bintree_left_child( node, &left_child ) ) 00178 { 00179 left_limit = get_node_split_position( left_child ); 00180 00181 if( delta == 0.0 ) 00182 { 00183 test_child = ((Real) Point_coord(*origin,axis_index) <= 00184 left_limit); 00185 } 00186 else 00187 { 00188 test_child = FALSE; 00189 00190 t = (left_limit - (Real) Point_coord(*origin,axis_index)) / 00191 delta; 00192 00193 if( delta < 0.0 && t <= t_max_child ) 00194 { 00195 test_child = TRUE; 00196 00197 if( t > t_min_child ) 00198 t_min_child = t; 00199 } 00200 else if( delta > 0.0 && t >= t_min_child ) 00201 { 00202 test_child = TRUE; 00203 00204 if( t < t_max_child ) 00205 t_max_child = t; 00206 } 00207 } 00208 00209 if( test_child ) 00210 { 00211 recursive_intersect_ray( origin, direction, 00212 t_min_child, t_max_child, 00213 left_child, object, 00214 obj_index, closest_dist, 00215 n_intersections, distances ); 00216 00217 if( distances == NULL && obj_index != NULL && 00218 *obj_index >= 0 && *closest_dist < t_min ) 00219 return; 00220 } 00221 } 00222 else if( !searching_left && 00223 get_bintree_right_child( node, &right_child ) ) 00224 { 00225 right_limit = get_node_split_position( right_child ); 00226 00227 if( delta == 0.0 ) 00228 { 00229 test_child = ((Real) Point_coord(*origin,axis_index) >= 00230 right_limit); 00231 } 00232 else 00233 { 00234 test_child = FALSE; 00235 00236 t = (right_limit - (Real) Point_coord(*origin,axis_index)) / 00237 delta; 00238 00239 if( delta < 0.0 && t >= t_min_child ) 00240 { 00241 test_child = TRUE; 00242 00243 if( t < t_max_child ) 00244 t_max_child = t; 00245 } 00246 else if( delta > 0.0 && t <= t_max_child ) 00247 { 00248 test_child = TRUE; 00249 00250 if( t > t_min_child ) 00251 t_min_child = t; 00252 } 00253 } 00254 00255 if( test_child ) 00256 { 00257 recursive_intersect_ray( origin, direction, 00258 t_min_child, t_max_child, 00259 right_child, object, 00260 obj_index, closest_dist, 00261 n_intersections, distances ); 00262 00263 if( distances == NULL && obj_index != NULL && 00264 *obj_index >= 0 && *closest_dist < t_min ) 00265 return; 00266 } 00267 } 00268 00269 searching_left = !searching_left; 00270 } 00271 } 00272 } 00273 00274 /* ----------------------------- MNI Header ----------------------------------- 00275 @NAME : ray_intersects_range 00276 @INPUT : range - a box 00277 origin 00278 direction 00279 @OUTPUT : t_min 00280 t_max 00281 @RETURNS : TRUE if ray intersects box 00282 @DESCRIPTION: Tests if the ray intersects the box and passes back the 00283 two intersection distances. 00284 @METHOD : 00285 @GLOBALS : 00286 @CALLS : 00287 @CREATED : Jun 21, 1995 David MacDonald 00288 @MODIFIED : 00289 ---------------------------------------------------------------------------- */ 00290 00291 public BOOLEAN ray_intersects_range( 00292 range_struct *range, 00293 Point *origin, 00294 Vector *direction, 00295 Real *t_min, 00296 Real *t_max ) 00297 { 00298 BOOLEAN intersects; 00299 00300 intersects = clip_line_to_box( origin, direction, 00301 (Real) range->limits[X][0], 00302 (Real) range->limits[X][1], 00303 (Real) range->limits[Y][0], 00304 (Real) range->limits[Y][1], 00305 (Real) range->limits[Z][0], 00306 (Real) range->limits[Z][1], t_min, t_max ); 00307 00308 00309 if( intersects ) 00310 { 00311 if( *t_min < 0.0 ) 00312 *t_min = 0.0; 00313 00314 intersects = (*t_min <= *t_max); 00315 } 00316 00317 return( intersects ); 00318 }