BICPL: subdivide_polygons.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/geom.h> 00017 00018 #ifndef lint 00019 static char rcsid[] = "$Header: /software/source//libraries/bicpl/Geometry/subdivide_polygons.c,v 1.18 2000/02/06 15:30:19 stever Exp $"; 00020 #endif 00021 00022 private void subdivide_polygon( 00023 polygons_struct *polygons, 00024 int poly, 00025 int *new_n_points, 00026 Point *new_points[], 00027 int *new_n_polygons, 00028 int *new_end_indices[], 00029 int *new_n_indices, 00030 int *new_indices[], 00031 int n_neighbours[], 00032 int *neighbours[], 00033 int *midpoints[] ); 00034 00035 /* ----------------------------- MNI Header ----------------------------------- 00036 @NAME : subdivide_polygons 00037 @INPUT : polygons 00038 @OUTPUT : 00039 @RETURNS : 00040 @DESCRIPTION: Subdivides the polygons, each polygon become 4 polygons. 00041 Can only handle polygons that have 3 or 4 vertices. 00042 @METHOD : 00043 @GLOBALS : 00044 @CALLS : 00045 @CREATED : 1993 David MacDonald 00046 @MODIFIED : 00047 ---------------------------------------------------------------------------- */ 00048 00049 public void subdivide_polygons( 00050 polygons_struct *polygons ) 00051 { 00052 int i, new_n_points, new_n_indices, new_n_polygons; 00053 int *new_indices, *new_end_indices; 00054 int size, *n_point_neighbours, **point_neighbours; 00055 int **midpoints; 00056 int total_n_point_neighbours; 00057 Point *new_points; 00058 Point dummy; 00059 Colour save_colour; 00060 progress_struct progress; 00061 00062 new_points = NULL; 00063 00064 if( is_this_sphere_topology( polygons ) ) 00065 { 00066 print( "Subdividing assuming sphere topology.\n" ); 00067 create_polygons_sphere( &dummy, 0.0, 0.0, 0.0, 0, 0, TRUE, polygons ); 00068 return; 00069 } 00070 00071 save_colour = polygons->colours[0]; 00072 00073 new_n_points = polygons->n_points; 00074 new_n_polygons = 0; 00075 new_n_indices = 0; 00076 00077 size = 0; 00078 SET_ARRAY_SIZE( new_points, size, new_n_points, DEFAULT_CHUNK_SIZE ); 00079 00080 for_less( i, 0, new_n_points ) 00081 new_points[i] = polygons->points[i]; 00082 00083 create_polygon_point_neighbours( polygons, FALSE, &n_point_neighbours, 00084 &point_neighbours, NULL, NULL ); 00085 00086 total_n_point_neighbours = 0; 00087 00088 for_less( i, 0, new_n_points ) 00089 total_n_point_neighbours += n_point_neighbours[i]; 00090 00091 ALLOC( midpoints, new_n_points ); 00092 ALLOC( midpoints[0], total_n_point_neighbours ); 00093 00094 for_less( i, 1, new_n_points ) 00095 midpoints[i] = &midpoints[i-1][n_point_neighbours[i-1]]; 00096 00097 for_less( i, 0, total_n_point_neighbours ) 00098 midpoints[0][i] = -1; 00099 00100 initialize_progress_report( &progress, TRUE, polygons->n_items, 00101 "Subdividing Polygon" ); 00102 00103 for_less( i, 0, polygons->n_items ) 00104 { 00105 subdivide_polygon( polygons, i, 00106 &new_n_points, &new_points, 00107 &new_n_polygons, &new_end_indices, 00108 &new_n_indices, &new_indices, 00109 n_point_neighbours, point_neighbours, midpoints ); 00110 update_progress_report( &progress, i+1 ); 00111 } 00112 00113 terminate_progress_report( &progress ); 00114 00115 delete_polygon_point_neighbours( polygons, n_point_neighbours, 00116 point_neighbours, NULL, NULL ); 00117 00118 FREE( midpoints[0] ); 00119 FREE( midpoints ); 00120 00121 delete_polygons( polygons ); 00122 00123 ALLOC( polygons->colours, 1 ); 00124 polygons->colour_flag = ONE_COLOUR; 00125 polygons->colours[0] = save_colour; 00126 00127 ALLOC( polygons->normals, new_n_points ); 00128 00129 polygons->n_points = new_n_points; 00130 polygons->points = new_points; 00131 polygons->n_items = new_n_polygons; 00132 polygons->end_indices = new_end_indices; 00133 polygons->indices = new_indices; 00134 } 00135 00136 /* ----------------------------- MNI Header ----------------------------------- 00137 @NAME : subdivide_polygon 00138 @INPUT : polygons 00139 poly 00140 @OUTPUT : new_n_points 00141 new_points 00142 new_n_polygons 00143 new_end_indices 00144 new_n_indices 00145 new_indices 00146 midpoint_table 00147 @RETURNS : 00148 @DESCRIPTION: Subdivides the poly'th polygon into 4 new polygons. 00149 @METHOD : 00150 @GLOBALS : 00151 @CALLS : 00152 @CREATED : 1993 David MacDonald 00153 @MODIFIED : 00154 ---------------------------------------------------------------------------- */ 00155 00156 private void subdivide_polygon( 00157 polygons_struct *polygons, 00158 int poly, 00159 int *new_n_points, 00160 Point *new_points[], 00161 int *new_n_polygons, 00162 int *new_end_indices[], 00163 int *new_n_indices, 00164 int *new_indices[], 00165 int n_neighbours[], 00166 int *neighbours[], 00167 int *midpoints[] ) 00168 { 00169 int edge, size, i0, i1, point_indices[4], p; 00170 int midpoint_indices[4], centre_point_index, p1, p2; 00171 Point midpoint; 00172 00173 size = GET_OBJECT_SIZE( *polygons, poly ); 00174 00175 if( size < 3 || size > 4 ) 00176 { 00177 print_error( "Polygon size %d in subdivide polygons\n", size ); 00178 return; 00179 } 00180 00181 for_less( edge, 0, size ) 00182 { 00183 point_indices[edge] = polygons->indices[ 00184 POINT_INDEX(polygons->end_indices,poly,edge)]; 00185 } 00186 00187 for_less( edge, 0, size ) 00188 { 00189 p1 = point_indices[edge]; 00190 p2 = point_indices[(edge+1)%size]; 00191 i0 = MIN( p1, p2 ); 00192 i1 = MAX( p1, p2 ); 00193 00194 for_less( p, 0, n_neighbours[i0] ) 00195 { 00196 if( neighbours[i0][p] == i1 ) 00197 break; 00198 } 00199 00200 if( p >= n_neighbours[i0] ) 00201 handle_internal_error( "subdivide_polygon" ); 00202 00203 midpoint_indices[edge] = midpoints[i0][p]; 00204 00205 if( midpoint_indices[edge] < 0 ) 00206 { 00207 midpoint_indices[edge] = *new_n_points; 00208 midpoints[i0][p] = *new_n_points; 00209 INTERPOLATE_POINTS( midpoint, polygons->points[i0], 00210 polygons->points[i1], 0.5 ); 00211 ADD_ELEMENT_TO_ARRAY( *new_points, *new_n_points, 00212 midpoint, DEFAULT_CHUNK_SIZE ); 00213 } 00214 } 00215 00216 if( size == 3 ) 00217 { 00218 00219 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00220 point_indices[0], DEFAULT_CHUNK_SIZE ); 00221 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00222 midpoint_indices[0], DEFAULT_CHUNK_SIZE ); 00223 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00224 midpoint_indices[2], DEFAULT_CHUNK_SIZE ); 00225 ADD_ELEMENT_TO_ARRAY( *new_end_indices, *new_n_polygons, 00226 *new_n_indices, DEFAULT_CHUNK_SIZE ); 00227 00228 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00229 midpoint_indices[0], DEFAULT_CHUNK_SIZE ); 00230 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00231 point_indices[1], DEFAULT_CHUNK_SIZE ); 00232 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00233 midpoint_indices[1], DEFAULT_CHUNK_SIZE ); 00234 ADD_ELEMENT_TO_ARRAY( *new_end_indices, *new_n_polygons, 00235 *new_n_indices, DEFAULT_CHUNK_SIZE ); 00236 00237 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00238 midpoint_indices[2], DEFAULT_CHUNK_SIZE ); 00239 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00240 midpoint_indices[0], DEFAULT_CHUNK_SIZE ); 00241 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00242 midpoint_indices[1], DEFAULT_CHUNK_SIZE ); 00243 ADD_ELEMENT_TO_ARRAY( *new_end_indices, *new_n_polygons, 00244 *new_n_indices, DEFAULT_CHUNK_SIZE ); 00245 00246 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00247 midpoint_indices[2], DEFAULT_CHUNK_SIZE ); 00248 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00249 midpoint_indices[1], DEFAULT_CHUNK_SIZE ); 00250 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00251 point_indices[2], DEFAULT_CHUNK_SIZE ); 00252 ADD_ELEMENT_TO_ARRAY( *new_end_indices, *new_n_polygons, 00253 *new_n_indices, DEFAULT_CHUNK_SIZE ); 00254 } 00255 else 00256 { 00257 centre_point_index = *new_n_points; 00258 00259 ADD_POINTS( midpoint, polygons->points[point_indices[0]], 00260 polygons->points[point_indices[1]] ); 00261 ADD_POINTS( midpoint, midpoint, polygons->points[point_indices[2]] ); 00262 ADD_POINTS( midpoint, midpoint, polygons->points[point_indices[3]] ); 00263 SCALE_POINT( midpoint, midpoint, 0.25 ); 00264 00265 ADD_ELEMENT_TO_ARRAY( *new_points, *new_n_points, 00266 midpoint, DEFAULT_CHUNK_SIZE ); 00267 00268 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00269 point_indices[0], DEFAULT_CHUNK_SIZE ); 00270 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00271 midpoint_indices[0], DEFAULT_CHUNK_SIZE ); 00272 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00273 centre_point_index, DEFAULT_CHUNK_SIZE ); 00274 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00275 midpoint_indices[3], DEFAULT_CHUNK_SIZE ); 00276 ADD_ELEMENT_TO_ARRAY( *new_end_indices, *new_n_polygons, 00277 *new_n_indices, DEFAULT_CHUNK_SIZE ); 00278 00279 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00280 midpoint_indices[0], DEFAULT_CHUNK_SIZE ); 00281 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00282 point_indices[1], DEFAULT_CHUNK_SIZE ); 00283 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00284 midpoint_indices[1], DEFAULT_CHUNK_SIZE ); 00285 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00286 centre_point_index, DEFAULT_CHUNK_SIZE ); 00287 ADD_ELEMENT_TO_ARRAY( *new_end_indices, *new_n_polygons, 00288 *new_n_indices, DEFAULT_CHUNK_SIZE ); 00289 00290 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00291 midpoint_indices[3], DEFAULT_CHUNK_SIZE ); 00292 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00293 centre_point_index, DEFAULT_CHUNK_SIZE ); 00294 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00295 midpoint_indices[2], DEFAULT_CHUNK_SIZE ); 00296 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00297 point_indices[3], DEFAULT_CHUNK_SIZE ); 00298 ADD_ELEMENT_TO_ARRAY( *new_end_indices, *new_n_polygons, 00299 *new_n_indices, DEFAULT_CHUNK_SIZE ); 00300 00301 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00302 centre_point_index, DEFAULT_CHUNK_SIZE ); 00303 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00304 midpoint_indices[1], DEFAULT_CHUNK_SIZE ); 00305 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00306 point_indices[2], DEFAULT_CHUNK_SIZE ); 00307 ADD_ELEMENT_TO_ARRAY( *new_indices, *new_n_indices, 00308 midpoint_indices[2], DEFAULT_CHUNK_SIZE ); 00309 ADD_ELEMENT_TO_ARRAY( *new_end_indices, *new_n_polygons, 00310 *new_n_indices, DEFAULT_CHUNK_SIZE ); 00311 } 00312 }