BRL-CAD
vert_tree.c
Go to the documentation of this file.
1 /* V E R T _ T R E E . C
2  * BRL-CAD
3  *
4  * Copyright (c) 2002-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 /** @addtogroup vtree */
21 /** @{ */
22 /** @file libbn/vert_tree.c
23  *
24  * @brief
25  * Routines to manage a binary search tree of vertices.
26  *
27  * The actual vertices are stored in an array
28  * for convenient use by routines such as "mk_bot".
29  * The binary search tree stores indices into the array.
30  *
31  */
32 
33 #include "common.h"
34 
35 #include <stdlib.h>
36 #include <stdio.h>
37 #include <math.h>
38 #include <string.h>
39 #include <ctype.h>
40 #include <errno.h>
41 
42 #include "vmath.h"
43 #include "bu/malloc.h"
44 #include "bu/log.h"
45 #include "bn/vert_tree.h"
46 
47 
48 /**
49  * Structure to make vertex searching fast.
50  *
51  * Each leaf represents a vertex, and has an index into
52  * the vertices array ("the_array")
53  *
54  * Each node is a cutting plane at the "cut_val" on
55  * the "coord" (0, 1, or 2) axis.
56  *
57  * All vertices with "coord" value less than the "cut_val" are in the "lower"
58  * subtree, others are in the "higher".
59  */
60 union vert_tree {
61  char type; /* type - leaf or node */
62  struct vert_leaf {
63  char type;
64  int index; /* index into the array */
65  } vleaf;
66  struct vert_node {
67  char type;
68  double cut_val; /* cutting value */
69  int coord; /* cutting coordinate */
70  union vert_tree *higher, *lower; /* subtrees */
71  } vnode;
72 };
73 
74 /* types for the above "vert_tree" */
75 #define VERT_LEAF 'l'
76 #define VERT_NODE 'n'
77 
78 
79 struct vert_root *
81 {
82  struct vert_root *tree;
83 
84  BU_ALLOC(tree, struct vert_root);
85  tree->magic = VERT_TREE_MAGIC;
86  tree->tree_type = TREE_TYPE_VERTS;
87  tree->the_tree = (union vert_tree *)NULL;
88  tree->curr_vert = 0;
89  tree->max_vert = VERT_BLOCK;
90  tree->the_array = (fastf_t *)bu_malloc( tree->max_vert * 3 * sizeof( fastf_t ), "vert tree array" );
91 
92  return tree;
93 }
94 
95 struct vert_root *
97 {
98  struct vert_root *tree;
99 
100  BU_ALLOC(tree, struct vert_root);
101  tree->magic = VERT_TREE_MAGIC;
103  tree->the_tree = (union vert_tree *)NULL;
104  tree->curr_vert = 0;
105  tree->max_vert = VERT_BLOCK;
106  tree->the_array = (fastf_t *)bu_malloc( tree->max_vert * 6 * sizeof( fastf_t ), "vert tree array" );
107 
108  return tree;
109 }
110 
111 
112 /**
113  * static recursion routine used by "clean_vert_tree"
114  */
115 static void
116 clean_vert_tree_recurse( union vert_tree *ptr )
117 {
118  if ( ptr->type == VERT_NODE ) {
119  clean_vert_tree_recurse( ptr->vnode.higher );
120  clean_vert_tree_recurse( ptr->vnode.lower );
121  }
122 
123  bu_free( (char *)ptr, "vert_tree" );
124 
125 }
126 
127 void
128 clean_vert_tree( struct vert_root *tree_root )
129 {
130  BN_CK_VERT_TREE( tree_root );
131 
132  if ( !tree_root->the_tree ) return;
133 
134  clean_vert_tree_recurse( tree_root->the_tree );
135  tree_root->the_tree = (union vert_tree *)NULL;
136  tree_root->curr_vert = 0;
137 }
138 
139 /**
140  * static recursive routine used by "free_vert_tree"
141  */
142 static void
143 free_vert_tree_recurse( union vert_tree *ptr )
144 {
145  if ( ptr->type == VERT_NODE ) {
146  free_vert_tree_recurse( ptr->vnode.higher );
147  free_vert_tree_recurse( ptr->vnode.lower );
148  }
149 
150  bu_free( (char *)ptr, "vert_tree" );
151 
152 }
153 
154 void
156 {
157  union vert_tree *ptr;
158 
159  if ( !vert_root )
160  return;
161 
162  BN_CK_VERT_TREE( vert_root );
163 
164  ptr = vert_root->the_tree;
165  if ( !ptr )
166  return;
167 
168  free_vert_tree_recurse( ptr );
169 
170  if ( vert_root->the_array ) {
171  bu_free( (char *)vert_root->the_array, "vertex array" );
172  }
173 
174  vert_root->the_tree = (union vert_tree *)NULL;
175  vert_root->the_array = (fastf_t *)NULL;
176  vert_root->curr_vert = 0;
177  vert_root->max_vert = 0;
178 }
179 
180 int
181 Add_vert( double x, double y, double z, struct vert_root *vert_root, fastf_t local_tol_sq )
182 {
183  union vert_tree *ptr, *prev=NULL, *new_leaf, *new_node;
184  vect_t diff = VINIT_ZERO;
185  vect_t vertex;
186 
187  BN_CK_VERT_TREE( vert_root );
188 
189  if ( vert_root->tree_type != TREE_TYPE_VERTS ) {
190  bu_bomb( "Error: Add_vert() called for a tree containing vertices and normals\n" );
191  }
192 
193  VSET( vertex, x, y, z );
194 
195  /* look for this vertex already in the list */
196  ptr = vert_root->the_tree;
197  while ( ptr ) {
198  if ( ptr->type == VERT_NODE ) {
199  prev = ptr;
200  if ( vertex[ptr->vnode.coord] >= ptr->vnode.cut_val ) {
201  ptr = ptr->vnode.higher;
202  } else {
203  ptr = ptr->vnode.lower;
204  }
205  } else {
206  int ij;
207 
208  ij = ptr->vleaf.index*3;
209  diff[0] = fabs( vertex[0] - vert_root->the_array[ij] );
210  diff[1] = fabs( vertex[1] - vert_root->the_array[ij+1] );
211  diff[2] = fabs( vertex[2] - vert_root->the_array[ij+2] );
212  if ( (diff[0]*diff[0] + diff[1]*diff[1] + diff[2]*diff[2]) <= local_tol_sq ) {
213  /* close enough, use this vertex again */
214  return ptr->vleaf.index;
215  }
216  break;
217  }
218  }
219 
220  /* add this vertex to the list */
221  if ( vert_root->curr_vert >= vert_root->max_vert ) {
222  /* allocate more memory for vertices */
223  vert_root->max_vert += VERT_BLOCK;
224 
225  vert_root->the_array = (fastf_t *)bu_realloc( vert_root->the_array, sizeof( fastf_t ) * vert_root->max_vert * 3,
226  "vert_root->the_array" );
227  }
228 
229  VMOVE( &vert_root->the_array[vert_root->curr_vert*3], vertex );
230 
231  /* add to the tree also */
232  BU_ALLOC(new_leaf, union vert_tree);
233  new_leaf->vleaf.type = VERT_LEAF;
234  new_leaf->vleaf.index = vert_root->curr_vert++;
235  if ( !vert_root->the_tree ) {
236  /* first vertex, it becomes the root */
237  vert_root->the_tree = new_leaf;
238  } else if ( ptr && ptr->type == VERT_LEAF ) {
239  /* search above ended at a leaf, need to add a node above this leaf and the new leaf */
240  BU_ALLOC(new_node, union vert_tree);
241  new_node->vnode.type = VERT_NODE;
242 
243  /* select the cutting coord based on the biggest difference */
244  if ( diff[0] >= diff[1] && diff[0] >= diff[2] ) {
245  new_node->vnode.coord = 0;
246  } else if ( diff[1] >= diff[2] && diff[1] >= diff[0] ) {
247  new_node->vnode.coord = 1;
248  } else if ( diff[2] >= diff[1] && diff[2] >= diff[0] ) {
249  new_node->vnode.coord = 2;
250  }
251 
252  /* set the cut value to the mid value between the two vertices */
253  new_node->vnode.cut_val = (vertex[new_node->vnode.coord] +
254  vert_root->the_array[ptr->vleaf.index * 3 + new_node->vnode.coord]) * 0.5;
255 
256  /* set the node "lower" and "higher" pointers */
257  if ( vertex[new_node->vnode.coord] >=
258  vert_root->the_array[ptr->vleaf.index * 3 + new_node->vnode.coord] ) {
259  new_node->vnode.higher = new_leaf;
260  new_node->vnode.lower = ptr;
261  } else {
262  new_node->vnode.higher = ptr;
263  new_node->vnode.lower = new_leaf;
264  }
265 
266  if ( ptr == vert_root->the_tree ) {
267  /* if the above search ended at the root, redefine the root */
268  vert_root->the_tree = new_node;
269  } else {
270  /* set the previous node to point to our new one */
271  if ( prev->vnode.higher == ptr ) {
272  prev->vnode.higher = new_node;
273  } else {
274  prev->vnode.lower = new_node;
275  }
276  }
277  } else if ( ptr && ptr->type == VERT_NODE ) {
278  /* above search ended at a node, just add the new leaf */
279  prev = ptr;
280  if ( vertex[prev->vnode.coord] >= prev->vnode.cut_val ) {
281  if ( prev->vnode.higher ) {
282  bu_bomb("higher vertex node already exists in Add_vert()?\n");
283  }
284  prev->vnode.higher = new_leaf;
285  } else {
286  if ( prev->vnode.lower ) {
287  bu_bomb("lower vertex node already exists in Add_vert()?\n");
288  }
289  prev->vnode.lower = new_leaf;
290  }
291  } else {
292  fprintf( stderr, "*********ERROR********\n" );
293  }
294 
295  /* return the index into the vertex array */
296  return new_leaf->vleaf.index;
297 }
298 
299 int
300 Add_vert_and_norm( double x, double y, double z, double nx, double ny, double nz, struct vert_root *vert_root, fastf_t local_tol_sq )
301 {
302  union vert_tree *ptr, *prev=NULL, *new_leaf, *new_node;
303  fastf_t diff[6];
304  fastf_t vertex[6];
305  double d1_sq=0.0, d2_sq=0.0;
306 
307  BN_CK_VERT_TREE( vert_root );
308 
309  if ( vert_root->tree_type != TREE_TYPE_VERTS_AND_NORMS ) {
310  bu_bomb( "Error: Add_vert_and_norm() called for a tree containing just vertices\n" );
311  }
312 
313  VSET( vertex, x, y, z );
314  VSET( &vertex[3], nx, ny, nz );
315 
316  /* look for this vertex and normal already in the list */
317  ptr = vert_root->the_tree;
318  while ( ptr ) {
319  int i;
320 
321  if ( ptr->type == VERT_NODE ) {
322  prev = ptr;
323  if ( vertex[ptr->vnode.coord] >= ptr->vnode.cut_val ) {
324  ptr = ptr->vnode.higher;
325  } else {
326  ptr = ptr->vnode.lower;
327  }
328  } else {
329  int ij;
330 
331  ij = ptr->vleaf.index*6;
332  for ( i=0; i<6; i++ ) {
333  diff[i] = fabs( vertex[i] - vert_root->the_array[ij+i] );
334  }
335  d1_sq = VDOT( diff, diff );
336  d2_sq = VDOT( &diff[3], &diff[3] );
337  if ( d1_sq <= local_tol_sq && d2_sq <= 0.0001 ) {
338  /* close enough, use this vertex and normal again */
339  return ptr->vleaf.index;
340  }
341  break;
342  }
343  }
344 
345  /* add this vertex and normal to the list */
346  if ( vert_root->curr_vert >= vert_root->max_vert ) {
347  /* allocate more memory for vertices */
348  vert_root->max_vert += VERT_BLOCK;
349 
350  vert_root->the_array = (fastf_t *)bu_realloc( vert_root->the_array,
351  sizeof( fastf_t ) * vert_root->max_vert * 6,
352  "vert_root->the_array" );
353  }
354 
355  VMOVE( &vert_root->the_array[vert_root->curr_vert*6], vertex );
356  VMOVE( &vert_root->the_array[vert_root->curr_vert*6+3], &vertex[3] );
357 
358  /* add to the tree also */
359  BU_ALLOC(new_leaf, union vert_tree);
360  new_leaf->vleaf.type = VERT_LEAF;
361  new_leaf->vleaf.index = vert_root->curr_vert++;
362  if ( !vert_root->the_tree ) {
363  /* first vertex, it becomes the root */
364  vert_root->the_tree = new_leaf;
365  } else if ( ptr && ptr->type == VERT_LEAF ) {
366  fastf_t max;
367  int i;
368 
369  /* search above ended at a leaf, need to add a node above this leaf and the new leaf */
370  BU_ALLOC(new_node, union vert_tree);
371  new_node->vnode.type = VERT_NODE;
372 
373  /* select the cutting coord based on the biggest difference */
374  if ( d1_sq <= local_tol_sq ) {
375  /* cut based on normal */
376  new_node->vnode.coord = 3;
377  } else {
378  new_node->vnode.coord = 0;
379  }
380  max = diff[new_node->vnode.coord];
381  for ( i=new_node->vnode.coord+1; i<6; i++ ) {
382  if ( diff[i] > max ) {
383  new_node->vnode.coord = i;
384  max = diff[i];
385  }
386  }
387 
388  /* set the cut value to the mid value between the two vertices or normals */
389  new_node->vnode.cut_val = (vertex[new_node->vnode.coord] +
390  vert_root->the_array[ptr->vleaf.index * 3 + new_node->vnode.coord]) * 0.5;
391 
392  /* set the node "lower" and "higher" pointers */
393  if ( vertex[new_node->vnode.coord] >=
394  vert_root->the_array[ptr->vleaf.index * 3 + new_node->vnode.coord] ) {
395  new_node->vnode.higher = new_leaf;
396  new_node->vnode.lower = ptr;
397  } else {
398  new_node->vnode.higher = ptr;
399  new_node->vnode.lower = new_leaf;
400  }
401 
402  if ( ptr == vert_root->the_tree ) {
403  /* if the above search ended at the root, redefine the root */
404  vert_root->the_tree = new_node;
405  } else {
406  /* set the previous node to point to our new one */
407  if ( prev->vnode.higher == ptr ) {
408  prev->vnode.higher = new_node;
409  } else {
410  prev->vnode.lower = new_node;
411  }
412  }
413  } else if ( ptr && ptr->type == VERT_NODE ) {
414  /* above search ended at a node, just add the new leaf */
415  prev = ptr;
416  if ( vertex[prev->vnode.coord] >= prev->vnode.cut_val ) {
417  if ( prev->vnode.higher ) {
418  bu_bomb("higher vertex node already exists in Add_vert_and_norm()?\n");
419  }
420  prev->vnode.higher = new_leaf;
421  } else {
422  if ( prev->vnode.lower ) {
423  bu_bomb("lower vertex node already exists in Add_vert_and_norm()?\n");
424  }
425  prev->vnode.lower = new_leaf;
426  }
427  } else {
428  fprintf( stderr, "*********ERROR********\n" );
429  }
430 
431  /* return the index into the vertex array */
432  return new_leaf->vleaf.index;
433 }
434 /** @} */
435 /*
436  * Local Variables:
437  * mode: C
438  * tab-width: 8
439  * indent-tabs-mode: t
440  * c-file-style: "stroustrup"
441  * End:
442  * ex: shiftwidth=4 tabstop=8
443  */
#define VERT_NODE
Definition: vert_tree.c:76
#define VSET(a, b, c, d)
Definition: color.c:53
Header file for the BRL-CAD common definitions.
char type
Definition: vert_tree.c:61
struct vert_root * create_vert_tree_w_norms(void)
routine to create a vertex tree.
Definition: vert_tree.c:96
union vert_tree * the_tree
the actual vertex tree
Definition: vert_tree.h:53
#define BN_CK_VERT_TREE(_p)
Definition: vert_tree.h:64
void free_vert_tree(struct vert_root *tree_root)
Routine to free a vertex tree and all associated dynamic memory.
Definition: vert_tree.c:155
int Add_vert_and_norm(double x, double y, double z, double nx, double ny, double nz, struct vert_root *tree_root, fastf_t local_tol_sq)
Routine to add a vertex and a normal to the current list of part vertices. The array is re-alloc'd if...
Definition: vert_tree.c:300
struct vert_root * create_vert_tree(void)
routine to create a vertex tree.
Definition: vert_tree.c:80
void * bu_malloc(size_t siz, const char *str)
Definition: malloc.c:314
#define VERT_BLOCK
number of vertices to malloc per call when building the array
Definition: vert_tree.h:62
int tree_type
vertices or vertices with normals
Definition: vert_tree.h:52
#define BU_ALLOC(_ptr, _type)
Definition: malloc.h:223
int Add_vert(double x, double y, double z, struct vert_root *tree_root, fastf_t local_tol_sq)
Routine to add a vertex to the current list of part vertices. The array is re-alloc'd if needed...
Definition: vert_tree.c:181
#define TREE_TYPE_VERTS_AND_NORMS
Definition: vert_tree.h:60
struct vert_tree::vert_leaf vleaf
uint32_t magic
Definition: vert_tree.h:51
void * bu_realloc(void *ptr, size_t siz, const char *str)
size_t max_vert
the current maximum capacity of the array
Definition: vert_tree.h:56
Vertex tree support Routines to manage a binary search tree of vertices.
Definition: vert_tree.h:50
#define TREE_TYPE_VERTS
Definition: vert_tree.h:59
size_t curr_vert
the number of vertices currently in the array
Definition: vert_tree.h:55
void clean_vert_tree(struct vert_root *tree_root)
Routine to free the binary search tree and reset the current number of vertices. The vertex array is ...
Definition: vert_tree.c:128
#define VERT_TREE_MAGIC
Definition: magic.h:212
union vert_tree * lower
Definition: vert_tree.c:70
struct vert_tree::vert_node vnode
fastf_t * the_array
the array of vertices
Definition: vert_tree.h:54
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
union vert_tree * higher
Definition: vert_tree.c:70
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
double fastf_t
Definition: defines.h:300
#define VERT_LEAF
Definition: vert_tree.c:75