BRL-CAD
bot.c
Go to the documentation of this file.
1 /* B O T . C
2  * BRL-CAD
3  *
4  * Copyright (c) 1999-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 primitives */
21 /** @{ */
22 /** @file primitives/bot/bot.c
23  *
24  * Intersect a ray with a bag o' triangles.
25  *
26  */
27 
28 #include "common.h"
29 
30 #include <stdlib.h>
31 #include <stdio.h>
32 #include <string.h>
33 #include <math.h>
34 #include <ctype.h>
35 #include "bnetwork.h"
36 
37 #include "tcl.h"
38 #include "bu/cv.h"
39 #include "vmath.h"
40 #include "db.h"
41 #include "nmg.h"
42 #include "rtgeom.h"
43 #include "raytrace.h"
44 #include "bot.h"
45 
46 #include "vds.h"
47 
48 #define GLUE(_a, _b) _a ## _b
49 #define XGLUE(_a, _b) GLUE(_a, _b)
50 
51 #include "tie.h"
52 #include "btg.h" /* for the bottie_ functions */
53 
54 #define MAXHITS 128
55 
56 #define BOT_MIN_DN 1.0e-9
57 
58 #define BOT_UNORIENTED_NORM(_ap, _hitp, _out) { \
59  if (!(_ap)->a_bot_reverse_normal_disabled) { \
60  if (_out) { /* this is an exit */ \
61  if ((_hitp)->hit_vpriv[X] < 0.0) { \
62  VREVERSE((_hitp)->hit_normal, trip->tri_N); \
63  } else { \
64  VMOVE((_hitp)->hit_normal, trip->tri_N); \
65  } \
66  } else { /* this is an entrance */ \
67  if ((_hitp)->hit_vpriv[X] > 0.0) { \
68  VREVERSE((_hitp)->hit_normal, trip->tri_N); \
69  } else { \
70  VMOVE((_hitp)->hit_normal, trip->tri_N); \
71  } \
72  } \
73  } else { \
74  VMOVE((_hitp)->hit_normal, trip->tri_N); \
75  } \
76  }
77 
78 
79 /* forward declarations needed for the included routines below */
80 int
82  struct hit *hits,
83  size_t nhits,
84  struct soltab *stp,
85  struct xray *rp,
86  struct application *ap,
87  struct seg *seghead,
88  struct rt_piecestate *psp);
89 
90 HIDDEN int
91 rt_bot_unoriented_segs(struct hit *hits,
92  size_t nhits,
93  struct soltab *stp,
94  struct xray *rp,
95  struct application *ap,
96  struct seg *seghead,
97  struct bot_specific *bot);
98 
99 size_t
100 rt_botface_w_normals(struct soltab *stp,
101  struct bot_specific *bot,
102  fastf_t *ap,
103  fastf_t *bp,
104  fastf_t *cp,
105  fastf_t *vertex_normals, /* array of nine values (three unit normals vectors) */
106  size_t face_no,
107  const struct bn_tol *tol);
108 
109 
110 #define TRI_TYPE float
111 #define NORM_TYPE signed char
112 #define NORMAL_SCALE 127.0
113 #define ONE_OVER_SCALE (1.0/127.0)
114 #include "./g_bot_include.c"
115 #undef TRI_TYPE
116 #undef NORM_TYPE
117 #undef NORMAL_SCALE
118 #undef ONE_OVER_SCALE
119 #define TRI_TYPE double
120 #define NORM_TYPE fastf_t
121 #define NORMAL_SCALE 1.0
122 #define ONE_OVER_SCALE 1.0
123 #include "./g_bot_include.c"
124 #undef TRI_TYPE
125 #undef NORM_TYPE
126 #undef NORMAL_SCALE
127 #undef ONE_OVER_SCALE
128 
129 
130 /**
131  * This function is called with pointers to 3 points, and is used to
132  * prepare BOT faces. ap, bp, cp point to vect_t points.
133  *
134  * Return -
135  * 0 if the 3 points didn't form a plane (e.g., collinear, etc.).
136  * # pts (3) if a valid plane resulted.
137  */
138 size_t
140  struct bot_specific *bot,
141  fastf_t *ap,
142  fastf_t *bp,
143  fastf_t *cp,
144  fastf_t *vertex_normals, /* array of nine values (three unit normals vectors) */
145  size_t face_no,
146  const struct bn_tol *tol)
147 {
148 
149  if (bot->bot_flags & RT_BOT_USE_FLOATS) {
150  return rt_botface_w_normals_float(stp, bot, ap, bp, cp,
151  vertex_normals, face_no, tol);
152  } else {
153  return rt_botface_w_normals_double(stp, bot, ap, bp, cp,
154  vertex_normals, face_no, tol);
155  }
156 }
157 
158 
159 size_t
160 rt_botface(struct soltab *stp,
161  struct bot_specific *bot,
162  fastf_t *ap,
163  fastf_t *bp,
164  fastf_t *cp,
165  size_t face_no,
166  const struct bn_tol *tol)
167 {
168  return rt_botface_w_normals(stp, bot, ap, bp, cp, NULL, face_no, tol);
169 }
170 
171 
172 /**
173  * Do the prep to support pieces for a BOT/ARS
174  */
175 void
176 rt_bot_prep_pieces(struct bot_specific *bot,
177  struct soltab *stp,
178  size_t ntri,
179  const struct bn_tol *tol)
180 {
181  if (bot->bot_flags & RT_BOT_USE_FLOATS) {
182  rt_bot_prep_pieces_float(bot, stp, ntri, tol);
183  } else {
184  rt_bot_prep_pieces_double(bot, stp, ntri, tol);
185  }
186 }
187 
188 
189 /**
190  * Calculate an RPP for a BoT
191  */
192 int
193 rt_bot_bbox(struct rt_db_internal *ip, point_t *min, point_t *max) {
194  struct rt_bot_internal *bot_ip;
195  size_t tri_index;
196  point_t p1, p2, p3;
197  size_t pt1, pt2, pt3;
198 
199  RT_CK_DB_INTERNAL(ip);
200  bot_ip = (struct rt_bot_internal *)ip->idb_ptr;
201  RT_BOT_CK_MAGIC(bot_ip);
202 
203  VSETALL((*min), INFINITY);
204  VSETALL((*max), -INFINITY);
205 
206  for (tri_index = 0; tri_index < bot_ip->num_faces; tri_index++) {
207  pt1 = bot_ip->faces[tri_index*3];
208  pt2 = bot_ip->faces[tri_index*3 + 1];
209  pt3 = bot_ip->faces[tri_index*3 + 2];
210  VMOVE(p1, &bot_ip->vertices[pt1*3]);
211  VMOVE(p2, &bot_ip->vertices[pt2*3]);
212  VMOVE(p3, &bot_ip->vertices[pt3*3]);
213  VMINMAX((*min), (*max), p1);
214  VMINMAX((*min), (*max), p2);
215  VMINMAX((*min), (*max), p3);
216  }
217 
218  /* Prevent the RPP from being 0 thickness */
219  if (NEAR_EQUAL((*min)[X], (*max)[X], SMALL_FASTF)) {
220  (*min)[X] -= SMALL_FASTF;
221  (*max)[X] += SMALL_FASTF;
222  }
223  if (NEAR_EQUAL((*min)[Y], (*max)[Y], SMALL_FASTF)) {
224  (*min)[Y] -= SMALL_FASTF;
225  (*max)[Y] += SMALL_FASTF;
226  }
227  if (NEAR_EQUAL((*min)[Z], (*max)[Z], SMALL_FASTF)) {
228  (*min)[Z] -= SMALL_FASTF;
229  (*max)[Z] += SMALL_FASTF;
230  }
231  return 0;
232 }
233 
234 
235 /**
236  * Given a pointer to a GED database record, and a transformation
237  * matrix, determine if this is a valid BOT, and if so, precompute
238  * various terms of the formula.
239  *
240  * Returns -
241  * 0 BOT is OK
242  * !0 Error in description
243  *
244  * Implicit return -
245  * A struct bot_specific is created, and its address is stored in
246  * stp->st_specific for use by bot_shot().
247  */
248 int
249 rt_bot_prep(struct soltab *stp, struct rt_db_internal *ip, struct rt_i *rtip)
250 {
251  struct rt_bot_internal *bot_ip;
252  size_t rt_bot_mintie;
253 
254  RT_CK_DB_INTERNAL(ip);
255  bot_ip = (struct rt_bot_internal *)ip->idb_ptr;
256  RT_BOT_CK_MAGIC(bot_ip);
257 
258  rt_bot_mintie = RT_DEFAULT_MINTIE;
259  if (getenv("LIBRT_BOT_MINTIE")) {
260  rt_bot_mintie = atoi(getenv("LIBRT_BOT_MINTIE"));
261  }
262 
263  if (rt_bot_bbox(ip, &(stp->st_min), &(stp->st_max))) return 1;
264 
265  if (rt_bot_mintie > 0 && bot_ip->num_faces >= rt_bot_mintie /* FIXME: (necessary?) && (bot_ip->face_normals != NULL || bot_ip->orientation != RT_BOT_UNORIENTED) */)
266  return bottie_prep_double(stp, bot_ip, rtip);
267  else if (bot_ip->bot_flags & RT_BOT_USE_FLOATS)
268  return rt_bot_prep_float(stp, bot_ip, rtip);
269  else
270  return rt_bot_prep_double(stp, bot_ip, rtip);
271 }
272 
273 
274 void
275 rt_bot_print(const struct soltab *stp)
276 {
277  if (stp) RT_CK_SOLTAB(stp);
278 }
279 
280 
281 HIDDEN int
282 rt_bot_plate_segs(struct hit *hits,
283  size_t nhits,
284  struct soltab *stp,
285  struct xray *rp,
286  struct application *ap,
287  struct seg *seghead,
288  struct bot_specific *bot)
289 {
290  if (bot->bot_flags & RT_BOT_USE_FLOATS) {
291  return rt_bot_plate_segs_float(hits, nhits, stp, rp, ap, seghead, bot);
292  } else {
293  return rt_bot_plate_segs_double(hits, nhits, stp, rp, ap, seghead, bot);
294  }
295 }
296 
297 
298 HIDDEN int
300  size_t nhits,
301  struct soltab *stp,
302  struct xray *rp,
303  struct application *ap,
304  struct seg *seghead,
305  struct bot_specific *bot)
306 {
307  if (bot->bot_flags & RT_BOT_USE_FLOATS) {
308  return rt_bot_unoriented_segs_float(hits, nhits, stp, rp, ap, seghead);
309  } else {
310  return rt_bot_unoriented_segs_double(hits, nhits, stp, rp, ap, seghead);
311  }
312 }
313 
314 
315 /**
316  * Given an array of hits, make segments out of them. Exactly how
317  * this is to be done depends on the mode of the BoT.
318  */
319 int
320 rt_bot_makesegs(struct hit *hits, size_t nhits, struct soltab *stp, struct xray *rp, struct application *ap, struct seg *seghead, struct rt_piecestate *psp)
321 {
322  struct bot_specific *bot = (struct bot_specific *)stp->st_specific;
323 
324  if (bot->bot_mode == RT_BOT_PLATE ||
325  bot->bot_mode == RT_BOT_PLATE_NOCOS) {
326  return rt_bot_plate_segs(hits, nhits, stp, rp, ap, seghead, bot);
327  }
328 
329  if (bot->bot_flags & RT_BOT_USE_FLOATS) {
330  return rt_bot_makesegs_float(hits, nhits, stp, rp, ap, seghead, psp);
331  } else {
332  return rt_bot_makesegs_double(hits, nhits, stp, rp, ap, seghead, psp);
333  }
334 }
335 
336 
337 /**
338  * Intersect a ray with a bot. If an intersection occurs, a struct
339  * seg will be acquired and filled in.
340  *
341  * Notes for rt_bot_norm(): hit_private contains pointer to the
342  * tri_specific structure. hit_vpriv[X] contains dot product of ray
343  * direction and unit normal from tri_specific.
344  *
345  * Returns -
346  * 0 MISS
347  * >0 HIT
348  */
349 int
350 rt_bot_shot(struct soltab *stp, struct xray *rp, struct application *ap, struct seg *seghead)
351 {
352  struct bot_specific *bot;
353 
354  if (UNLIKELY(!stp || !ap || !seghead))
355  return 0;
356 
357  bot = (struct bot_specific *)stp->st_specific;
358  if (UNLIKELY(!bot))
359  return 0;
360 
361  if (bot->tie != NULL) {
362  return bottie_shot_double(stp, rp, ap, seghead);
363  } else if (bot->bot_flags & RT_BOT_USE_FLOATS) {
364  return rt_bot_shot_float(stp, rp, ap, seghead);
365  } else {
366  return rt_bot_shot_double(stp, rp, ap, seghead);
367  }
368 }
369 
370 
371 /**
372  * Intersect a ray with a list of "pieces" of a BoT.
373  *
374  * This routine may be invoked many times for a single ray, as the ray
375  * traverses from one space partitioning cell to the next.
376  *
377  * Plate-mode (2 hit) segments will be returned immediately in
378  * seghead.
379  *
380  * Generally the hits are stashed between invocations in psp.
381  */
382 int
383 rt_bot_piece_shot(struct rt_piecestate *psp, struct rt_piecelist *plp, double dist_corr, struct xray *rp, struct application *ap, struct seg *seghead)
384 {
385  struct soltab *stp;
386  struct bot_specific *bot;
387 
388  RT_CK_PIECELIST(plp);
389  stp = plp->stp;
390  RT_CK_SOLTAB(stp);
391  bot = (struct bot_specific *)stp->st_specific;
392 
393  if (bot->bot_flags & RT_BOT_USE_FLOATS) {
394  return rt_bot_piece_shot_float(psp, plp, dist_corr, rp, ap, seghead);
395  } else {
396  return rt_bot_piece_shot_double(psp, plp, dist_corr, rp, ap, seghead);
397  }
398 }
399 
400 
401 void
402 rt_bot_piece_hitsegs(struct rt_piecestate *psp, struct seg *seghead, struct application *ap)
403 {
404  RT_CK_PIECESTATE(psp);
405  RT_CK_AP(ap);
406  RT_CK_HTBL(&psp->htab);
407 
408  /* Sort hits, Near to Far */
409  rt_hitsort(psp->htab.hits, psp->htab.end);
410 
411  /* build segments */
412  (void)rt_bot_makesegs(psp->htab.hits, psp->htab.end, psp->stp, &ap->a_ray, ap, seghead, psp);
413 }
414 
415 
416 /**
417  * Given ONE ray distance, return the normal and entry/exit point.
418  */
419 void
420 rt_bot_norm(struct hit *hitp, struct soltab *stp, struct xray *rp)
421 {
422  struct bot_specific *bot=(struct bot_specific *)stp->st_specific;
423 
424  if (bot->bot_flags & RT_BOT_USE_FLOATS) {
425  rt_bot_norm_float(bot, hitp, stp, rp);
426  } else {
427  rt_bot_norm_double(bot, hitp, stp, rp);
428  }
429 }
430 
431 
432 /**
433  * Return the curvature of the bot.
434  */
435 void
436 rt_bot_curve(struct curvature *cvp, struct hit *hitp, struct soltab *stp)
437 {
438  if (stp) RT_CK_SOLTAB(stp);
439 
440  cvp->crv_c1 = cvp->crv_c2 = 0;
441 
442  /* any tangent direction */
443  bn_vec_ortho(cvp->crv_pdir, hitp->hit_normal);
444  cvp->crv_c1 = cvp->crv_c2 = 0;
445 }
446 
447 
448 /**
449  * For a hit on the surface of an bot, return the (u, v) coordinates
450  * of the hit point, 0 <= u, v <= 1.
451  *
452  * u = azimuth
453  * v = elevation
454  */
455 void
456 rt_bot_uv(struct application *ap, struct soltab *stp, struct hit *hitp, struct uvcoord *uvp)
457 {
458  if (ap) RT_CK_APPLICATION(ap);
459  if (stp) RT_CK_SOLTAB(stp);
460  if (hitp) RT_CK_HIT(hitp);
461  if (!uvp) return;
462 }
463 
464 
465 void
466 rt_bot_free(struct soltab *stp)
467 {
468  struct bot_specific *bot =
469  (struct bot_specific *)stp->st_specific;
470 
471  if (bot->tie != NULL) {
472  bottie_free_double(bot->tie);
473  bot->tie = NULL;
474  }
475 
476  if (bot->bot_flags & RT_BOT_USE_FLOATS) {
477  rt_bot_free_float(bot);
478  } else {
479  rt_bot_free_double(bot);
480  }
481 }
482 
483 
484 int
485 rt_bot_class(const struct soltab *stp, const fastf_t *min, const fastf_t *max, const struct bn_tol *tol)
486 {
487  if (stp) RT_CK_SOLTAB(stp);
488  if (tol) BN_CK_TOL(tol);
489  if (!min) return 0;
490  if (!max) return 0;
491 
492  return 0;
493 }
494 
495 
496 vdsNode *
497 build_vertex_tree(struct rt_bot_internal *bot)
498 {
499  size_t i, node_indices, tri_indices;
500  vect_t normal = {1.0, 0.0, 0.0};
501  unsigned char color[] = {255, 0 , 0};
502  vdsNode *leaf_nodes;
503  vdsNode **node_list;
504 
505  node_indices = bot->num_vertices * 3;
506  tri_indices = bot->num_faces * 3;
507 
508  vdsBeginVertexTree();
509  vdsBeginGeometry();
510 
511  /* create nodes */
512  for (i = 0; i < node_indices; i += 3) {
513  vdsAddNode(bot->vertices[i], bot->vertices[i + 1], bot->vertices[i + 2]);
514  }
515 
516  /* create triangles */
517  for (i = 0; i < tri_indices; i += 3) {
518  vdsAddTri(bot->faces[i], bot->faces[i + 1], bot->faces[i + 2],
519  normal, normal, normal, color, color, color);
520  }
521 
522  leaf_nodes = vdsEndGeometry();
523 
524  node_list = (vdsNode **)bu_malloc(bot->num_vertices * sizeof(vdsNode *), "node_list");
525  for (i = 0; i < bot->num_vertices; ++i) {
526  node_list[i] = &leaf_nodes[i];
527  }
528 
529  vdsClusterOctree(node_list, bot->num_vertices, 0);
530  bu_free(node_list, "node_list");
531 
532  return vdsEndVertexTree();
533 }
534 
535 
537  double dmin;
538  double dmax;
539  vdsNode *root;
541 };
542 
543 
544 static int
545 should_fold(const vdsNode *node, void *udata)
546 {
547  int i, num_edges, short_edges, short_spaces;
548  fastf_t dist_01, dist_12, dist_20;
549  vdsNode *corner_nodes[3];
550  struct bot_fold_data *fold_data = (struct bot_fold_data *)udata;
551 
552  if (node->nsubtris < 1) {
553  return 0;
554  }
555 
556  /* If it's really small, fold */
557  if (fold_data->dmax < fold_data->point_spacing) return 1;
558 
559  /* Long, thin objects shouldn't disappear */
560  if (fold_data->dmax/fold_data->dmin > 5.0 && node->nsubtris < 30) return 0;
561 
562  num_edges = node->nsubtris * 3;
563  short_edges = short_spaces = 0;
564 
565  for (i = 0; i < node->nsubtris; ++i) {
566  /* get the three nodes corresponding to the three corner */
567  corner_nodes[0] = vdsFindNode(node->subtris[i].corners[0].id, fold_data->root);
568  corner_nodes[1] = vdsFindNode(node->subtris[i].corners[1].id, fold_data->root);
569  corner_nodes[2] = vdsFindNode(node->subtris[i].corners[2].id, fold_data->root);
570 
571  dist_01 = DIST_PT_PT(corner_nodes[0]->coord, corner_nodes[1]->coord);
572  dist_12 = DIST_PT_PT(corner_nodes[1]->coord, corner_nodes[2]->coord);
573  dist_20 = DIST_PT_PT(corner_nodes[2]->coord, corner_nodes[0]->coord);
574 
575  /* check triangle edge point spacing against target point spacing */
576  if (dist_01 < fold_data->point_spacing) {
577  ++short_edges;
578  }
579  if (dist_12 < fold_data->point_spacing) {
580  ++short_edges;
581  }
582  if (dist_20 < fold_data->point_spacing) {
583  ++short_edges;
584  }
585  }
586 
587  if (((fastf_t)short_edges / num_edges) > .2 && node->nsubtris > 10) {
588  return 1;
589  }
590 
591  return 0;
592 }
593 
594 
595 static void
596 plot_node(const vdsNode *node, void *udata)
597 {
598  vdsTri *t = node->vistris;
599  struct bu_list *vhead = (struct bu_list *)udata;
600 
601  while (t != NULL) {
602  vdsUpdateTriProxies(t);
603  RT_ADD_VLIST(vhead, t->proxies[2]->coord, BN_VLIST_LINE_MOVE);
604  RT_ADD_VLIST(vhead, t->proxies[0]->coord, BN_VLIST_LINE_DRAW);
605  RT_ADD_VLIST(vhead, t->proxies[1]->coord, BN_VLIST_LINE_DRAW);
606  RT_ADD_VLIST(vhead, t->proxies[2]->coord, BN_VLIST_LINE_DRAW);
607  t = t->next;
608  }
609 }
610 
611 
612 int
613 rt_bot_adaptive_plot(struct rt_db_internal *ip, const struct rt_view_info *info)
614 {
615  double d1, d2, d3;
616  point_t min;
617  point_t max;
618 
619  vdsNode *vertex_tree;
620  struct rt_bot_internal *bot;
621  struct bot_fold_data fold_data;
622 
623  BU_CK_LIST_HEAD(info->vhead);
624  RT_CK_DB_INTERNAL(ip);
625 
626  bot = (struct rt_bot_internal *)ip->idb_ptr;
627  RT_BOT_CK_MAGIC(bot);
628 
629  vertex_tree = build_vertex_tree(bot);
630 
631  fold_data.root = vertex_tree;
632  fold_data.point_spacing = info->point_spacing;
633  (void)rt_bot_bbox(ip, &min, &max);
634  d1 = max[0] - min[0];
635  d2 = max[1] - min[1];
636  d3 = max[2] - min[2];
637  fold_data.dmin = d1;
638  if (d2 < fold_data.dmin) fold_data.dmin = d2;
639  if (d3 < fold_data.dmin) fold_data.dmin = d3;
640  fold_data.dmax = d1;
641  if (d2 > fold_data.dmax) fold_data.dmax = d2;
642  if (d3 > fold_data.dmax) fold_data.dmax = d3;
643 
644  vdsAdjustTreeTopDown(vertex_tree, should_fold, (void *)&fold_data);
645  vdsRenderTree(vertex_tree, plot_node, NULL, (void *)info->vhead);
646  vdsFreeTree(vertex_tree);
647 
648  return 0;
649 }
650 
651 
652 int
653 rt_bot_plot(struct bu_list *vhead, struct rt_db_internal *ip, const struct rt_tess_tol *UNUSED(ttol), const struct bn_tol *UNUSED(tol), const struct rt_view_info *UNUSED(info))
654 {
655  struct rt_bot_internal *bot_ip;
656  size_t i;
657 
658  BU_CK_LIST_HEAD(vhead);
659  RT_CK_DB_INTERNAL(ip);
660  bot_ip = (struct rt_bot_internal *)ip->idb_ptr;
661  RT_BOT_CK_MAGIC(bot_ip);
662 
663  if (bot_ip->num_vertices <= 0 || !bot_ip->vertices || bot_ip->num_faces <= 0 || !bot_ip->faces)
664  return 0;
665 
666  for (i = 0; i < bot_ip->num_faces; i++) {
667  if (bot_ip->faces[i*3+2] < 0 || (size_t)bot_ip->faces[i*3+2] > bot_ip->num_vertices)
668  continue; /* sanity */
669 
670  RT_ADD_VLIST(vhead, &bot_ip->vertices[bot_ip->faces[i*3+0]*3], BN_VLIST_LINE_MOVE);
671  RT_ADD_VLIST(vhead, &bot_ip->vertices[bot_ip->faces[i*3+1]*3], BN_VLIST_LINE_DRAW);
672  RT_ADD_VLIST(vhead, &bot_ip->vertices[bot_ip->faces[i*3+2]*3], BN_VLIST_LINE_DRAW);
673  RT_ADD_VLIST(vhead, &bot_ip->vertices[bot_ip->faces[i*3+0]*3], BN_VLIST_LINE_DRAW);
674  }
675 
676  return 0;
677 }
678 
679 
680 int
681 rt_bot_plot_poly(struct bu_list *vhead, struct rt_db_internal *ip, const struct rt_tess_tol *UNUSED(ttol), const struct bn_tol *UNUSED(tol))
682 {
683  struct rt_bot_internal *bot_ip;
684  size_t i;
685 
686  BU_CK_LIST_HEAD(vhead);
687  RT_CK_DB_INTERNAL(ip);
688  bot_ip = (struct rt_bot_internal *)ip->idb_ptr;
689  RT_BOT_CK_MAGIC(bot_ip);
690 
691  if (bot_ip->num_vertices <= 0 || !bot_ip->vertices || bot_ip->num_faces <= 0 || !bot_ip->faces)
692  return 0;
693 
694  /* XXX Should consider orientation here, flip if necessary. */
695  for (i = 0; i < bot_ip->num_faces; i++) {
696  point_t aa, bb, cc;
697  vect_t ab, ac;
698  vect_t norm;
699 
700  if (bot_ip->faces[i*3+2] < 0 || (size_t)bot_ip->faces[i*3+2] > bot_ip->num_vertices)
701  continue; /* sanity */
702 
703  VMOVE(aa, &bot_ip->vertices[bot_ip->faces[i*3+0]*3]);
704  VMOVE(bb, &bot_ip->vertices[bot_ip->faces[i*3+1]*3]);
705  VMOVE(cc, &bot_ip->vertices[bot_ip->faces[i*3+2]*3]);
706 
707  VSUB2(ab, aa, bb);
708  VSUB2(ac, aa, cc);
709  VCROSS(norm, ab, ac);
710  VUNITIZE(norm);
711  RT_ADD_VLIST(vhead, norm, BN_VLIST_TRI_START);
712 
713  if ((bot_ip->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) &&
714  (bot_ip->bot_flags & RT_BOT_USE_NORMALS)) {
715  vect_t na, nb, nc;
716 
717  VMOVE(na, &bot_ip->normals[bot_ip->face_normals[i*3+0]*3]);
718  VMOVE(nb, &bot_ip->normals[bot_ip->face_normals[i*3+1]*3]);
719  VMOVE(nc, &bot_ip->normals[bot_ip->face_normals[i*3+2]*3]);
721  RT_ADD_VLIST(vhead, aa, BN_VLIST_TRI_MOVE);
723  RT_ADD_VLIST(vhead, bb, BN_VLIST_TRI_DRAW);
725  RT_ADD_VLIST(vhead, cc, BN_VLIST_TRI_DRAW);
726  RT_ADD_VLIST(vhead, aa, BN_VLIST_TRI_END);
727  } else {
728  RT_ADD_VLIST(vhead, aa, BN_VLIST_TRI_MOVE);
729  RT_ADD_VLIST(vhead, bb, BN_VLIST_TRI_DRAW);
730  RT_ADD_VLIST(vhead, cc, BN_VLIST_TRI_DRAW);
731  RT_ADD_VLIST(vhead, aa, BN_VLIST_TRI_END);
732  }
733  }
734 
735  return 0;
736 }
737 
738 
739 void
740 rt_bot_centroid(point_t *cent, const struct rt_db_internal *ip)
741 {
742  size_t i;
743  struct rt_bot_internal *bot_ip = (struct rt_bot_internal *)ip->idb_ptr;
744  RT_BOT_CK_MAGIC(bot_ip);
745 
746  rt_bot_condense(bot_ip);
747  VSETALL(*cent, 0.0);
748  for (i = 0; i < bot_ip->num_vertices; i++) {
749  VADD2(*cent, *cent, &bot_ip->vertices[i*3]);
750  }
751  VSCALE(*cent, *cent, 1.0 / (fastf_t)bot_ip->num_vertices);
752 }
753 
754 
755 /**
756  * Returns -
757  * -1 failure
758  * 0 OK. *r points to nmgregion that holds this tessellation.
759  */
760 int
761 rt_bot_tess(struct nmgregion **r, struct model *m, struct rt_db_internal *ip, const struct rt_tess_tol *UNUSED(ttol), const struct bn_tol *tol)
762 {
763  struct rt_bot_internal *bot_ip;
764  struct shell *s;
765  struct vertex **verts;
766  point_t pt[3];
767  point_t center;
768  size_t i;
769 
770  RT_CK_DB_INTERNAL(ip);
771  bot_ip = (struct rt_bot_internal *)ip->idb_ptr;
772  RT_BOT_CK_MAGIC(bot_ip);
773  if (bot_ip->mode == RT_BOT_PLATE || bot_ip->mode == RT_BOT_PLATE_NOCOS) {
774 #define RT_BOT_TESS_MAX_FACES 1024
775  size_t faces[RT_BOT_TESS_MAX_FACES];
776  plane_t planes[RT_BOT_TESS_MAX_FACES];
777 
778  rt_bot_centroid(&center, ip);
779  fprintf(stderr, "center pt = (%g %g %g)\n", V3ARGS(center));
780 
781  /* get the faces that use each vertex */
782  for (i = 0; i < bot_ip->num_vertices; i++) {
783  size_t faceCount = 0;
784  size_t j;
785  for (j = 0; j < bot_ip->num_faces; j++) {
786  size_t k;
787  for (k = 0; k < 3; k++) {
788  if ((size_t)bot_ip->faces[j*3+k] == i) {
789  /* this face uses vertex i */
790  faces[faceCount] = j;
791  faceCount++;
792  break;
793  }
794  }
795  }
796  fprintf(stderr, "Vertex #%lu appears in %lu faces\n", (long unsigned)i, (long unsigned)faceCount);
797  if (faceCount == 0) {
798  continue;
799  }
800  if (bot_ip->bot_flags & RT_BOT_HAS_SURFACE_NORMALS)
801  for (i = 0; i < faceCount; i++) {
802  size_t k;
803  fastf_t *plane;
804  for (k = 0; k < 3; k++) {
805  size_t idx = faces[i] * 3 + k;
806  VMOVE(planes[i], &bot_ip->normals[bot_ip->face_normals[idx]*3]);
807  planes[i][3] = VDOT(planes[i], &bot_ip->vertices[bot_ip->faces[faces[i]*3]*3]);
808  }
809  plane = planes[i];
810  fprintf(stderr, "\tplane #%lu = (%g %g %g %g)\n", (long unsigned)i, V4ARGS(plane));
811  }
812  }
813  return -1;
814  }
815  *r = nmg_mrsv(m); /* Make region, empty shell, vertex */
816  s = BU_LIST_FIRST(shell, &(*r)->s_hd);
817 
818  verts = (struct vertex **)bu_calloc(bot_ip->num_vertices, sizeof(struct vertex *), "rt_bot_tess: *verts[]");
819 
820  for (i = 0; i < bot_ip->num_faces; i++) {
821  struct faceuse *fu;
822  struct vertex **corners[3];
823 
824  if (bot_ip->faces[i*3+2] < 0 || (size_t)bot_ip->faces[i*3+2] > bot_ip->num_vertices)
825  continue; /* sanity */
826 
827  if (bot_ip->orientation == RT_BOT_CW) {
828  VMOVE(pt[2], &bot_ip->vertices[bot_ip->faces[i*3+0]*3]);
829  VMOVE(pt[1], &bot_ip->vertices[bot_ip->faces[i*3+1]*3]);
830  VMOVE(pt[0], &bot_ip->vertices[bot_ip->faces[i*3+2]*3]);
831  corners[2] = &verts[bot_ip->faces[i*3+0]];
832  corners[1] = &verts[bot_ip->faces[i*3+1]];
833  corners[0] = &verts[bot_ip->faces[i*3+2]];
834  } else {
835  VMOVE(pt[0], &bot_ip->vertices[bot_ip->faces[i*3+0]*3]);
836  VMOVE(pt[1], &bot_ip->vertices[bot_ip->faces[i*3+1]*3]);
837  VMOVE(pt[2], &bot_ip->vertices[bot_ip->faces[i*3+2]*3]);
838  corners[0] = &verts[bot_ip->faces[i*3+0]];
839  corners[1] = &verts[bot_ip->faces[i*3+1]];
840  corners[2] = &verts[bot_ip->faces[i*3+2]];
841  }
842 
843  if (!bn_3pts_distinct(pt[0], pt[1], pt[2], tol)
844  || bn_3pts_collinear(pt[0], pt[1], pt[2], tol))
845  continue;
846 
847  if ((fu=nmg_cmface(s, corners, 3)) == (struct faceuse *)NULL) {
848  bu_log("rt_bot_tess() nmg_cmface() failed for face #%zu\n", i);
849  continue;
850  }
851 
852  if (!(*corners[0])->vg_p)
853  nmg_vertex_gv(*(corners[0]), pt[0]);
854  if (!(*corners[1])->vg_p)
855  nmg_vertex_gv(*(corners[1]), pt[1]);
856  if (!(*corners[2])->vg_p)
857  nmg_vertex_gv(*(corners[2]), pt[2]);
858 
859  if (nmg_calc_face_g(fu))
860  nmg_kfu(fu);
861  else if (bot_ip->mode == RT_BOT_SURFACE) {
862  struct vertex **tmp;
863 
864  tmp = corners[0];
865  corners[0] = corners[2];
866  corners[2] = tmp;
867  if ((fu=nmg_cmface(s, corners, 3)) == (struct faceuse *)NULL)
868  bu_log("rt_bot_tess() nmg_cmface() failed for face #%zu\n", i);
869  else
870  nmg_calc_face_g(fu);
871  }
872  }
873 
874  bu_free(verts, "rt_bot_tess *verts[]");
875 
876  nmg_mark_edges_real(&s->l.magic);
877 
878  nmg_region_a(*r, tol);
879 
880  if (bot_ip->mode == RT_BOT_SOLID && bot_ip->orientation == RT_BOT_UNORIENTED)
881  nmg_fix_normals(s, tol);
882 
883  return 0;
884 }
885 
886 
887 /**
888  * Import an BOT from the database format to the internal format.
889  * Apply modeling transformations as well.
890  */
891 int
892 rt_bot_import4(struct rt_db_internal *ip, const struct bu_external *ep, const fastf_t *mat, const struct db_i *dbip)
893 {
894  struct rt_bot_internal *bot_ip;
895  union record *rp;
896  size_t i;
897  size_t chars_used;
898 
899  if (dbip) RT_CK_DBI(dbip);
900  BU_CK_EXTERNAL(ep);
901  rp = (union record *)ep->ext_buf;
902  /* Check record type */
903  if (rp->u_id != DBID_BOT) {
904  bu_log("rt_bot_import4: defective record\n");
905  return -1;
906  }
907 
908  RT_CK_DB_INTERNAL(ip);
909  ip->idb_major_type = DB5_MAJORTYPE_BRLCAD;
910  ip->idb_type = ID_BOT;
911  ip->idb_meth = &OBJ[ID_BOT];
912  BU_ALLOC(ip->idb_ptr, struct rt_bot_internal);
913 
914  bot_ip = (struct rt_bot_internal *)ip->idb_ptr;
915  bot_ip->magic = RT_BOT_INTERNAL_MAGIC;
916 
917  bot_ip->num_vertices = ntohl(*(uint32_t *)&rp->bot.bot_num_verts[0]);
918  bot_ip->num_faces = ntohl(*(uint32_t *)&rp->bot.bot_num_triangles[0]);
919  bot_ip->orientation = rp->bot.bot_orientation;
920  bot_ip->mode = rp->bot.bot_mode;
921  bot_ip->bot_flags = 0;
922 
923  bot_ip->vertices = (fastf_t *)bu_calloc(bot_ip->num_vertices * 3, sizeof(fastf_t), "Bot vertices");
924  bot_ip->faces = (int *)bu_calloc(bot_ip->num_faces * 3, sizeof(int), "Bot faces");
925 
926  if (mat == NULL) mat = bn_mat_identity;
927  for (i = 0; i < bot_ip->num_vertices; i++) {
928  double tmp[ELEMENTS_PER_POINT];
929 
930  bu_cv_ntohd((unsigned char *)tmp, (const unsigned char *)(&rp->bot.bot_data[i*24]), ELEMENTS_PER_POINT);
931  MAT4X3PNT(&(bot_ip->vertices[i*ELEMENTS_PER_POINT]), mat, tmp);
932  }
933 
934  chars_used = bot_ip->num_vertices * ELEMENTS_PER_POINT * 8;
935 
936  for (i = 0; i < bot_ip->num_faces; i++) {
937  size_t idx=chars_used + i * 12;
938 
939  bot_ip->faces[i*ELEMENTS_PER_POINT + 0] = ntohl(*(uint32_t *)&rp->bot.bot_data[idx + 0]);
940  bot_ip->faces[i*ELEMENTS_PER_POINT + 1] = ntohl(*(uint32_t *)&rp->bot.bot_data[idx + 4]);
941  bot_ip->faces[i*ELEMENTS_PER_POINT + 2] = ntohl(*(uint32_t *)&rp->bot.bot_data[idx + 8]);
942  }
943 
944  if (bot_ip->mode == RT_BOT_PLATE || bot_ip->mode == RT_BOT_PLATE_NOCOS) {
945  chars_used = bot_ip->num_vertices * ELEMENTS_PER_POINT * 8 + bot_ip->num_faces * 12;
946 
947  bot_ip->thickness = (fastf_t *)bu_calloc(bot_ip->num_faces, sizeof(fastf_t), "BOT thickness");
948  for (i = 0; i < bot_ip->num_faces; i++) {
949  double scan;
950 
951  bu_cv_ntohd((unsigned char *)&scan, (const unsigned char *)(&rp->bot.bot_data[chars_used + i*8]), 1);
952  bot_ip->thickness[i] = scan; /* convert double to fastf_t */
953  }
954 
955  bot_ip->face_mode = bu_hex_to_bitv((const char *)(&rp->bot.bot_data[chars_used + bot_ip->num_faces * 8]));
956  } else {
957  bot_ip->thickness = (fastf_t *)NULL;
958  bot_ip->face_mode = (struct bu_bitv *)NULL;
959  }
960 
961  return 0; /* OK */
962 }
963 
964 
965 /**
966  * The name is added by the caller, in the usual place.
967  */
968 int
969 rt_bot_export4(struct bu_external *ep, const struct rt_db_internal *ip, double local2mm, const struct db_i *dbip)
970 {
971  struct rt_bot_internal *bot_ip;
972  union record *rec;
973  size_t i;
974  size_t chars_used;
975  size_t num_recs;
976  struct bu_vls face_mode = BU_VLS_INIT_ZERO;
977 
978  if (dbip) RT_CK_DBI(dbip);
979  RT_CK_DB_INTERNAL(ip);
980  if (ip->idb_type != ID_BOT) return -1;
981  bot_ip = (struct rt_bot_internal *)ip->idb_ptr;
982  RT_BOT_CK_MAGIC(bot_ip);
983 
984  if (bot_ip->num_normals > 0) {
985  bu_log("BOT surface normals not supported in older database formats, normals not saved\n");
986  bu_log("\tPlease update to current database format using \"dbupgrade\"\n");
987  }
988 
989  BU_CK_EXTERNAL(ep);
990  ep->ext_nbytes = sizeof(struct bot_rec) - 1 +
991  bot_ip->num_vertices * ELEMENTS_PER_POINT * 8 + bot_ip->num_faces * ELEMENTS_PER_POINT * 4;
992  if (bot_ip->mode == RT_BOT_PLATE || bot_ip->mode == RT_BOT_PLATE_NOCOS) {
993  if (!bot_ip->face_mode) {
994  bot_ip->face_mode = bu_bitv_new(bot_ip->num_faces);
995  }
996  if (!bot_ip->thickness)
997  bot_ip->thickness = (fastf_t *)bu_calloc(bot_ip->num_faces, sizeof(fastf_t), "BOT thickness");
998  bu_bitv_to_hex(&face_mode, bot_ip->face_mode);
999  ep->ext_nbytes += bot_ip->num_faces * 8 + bu_vls_strlen(&face_mode) + 1;
1000  }
1001 
1002  /* round up to the nearest granule */
1003  if (ep->ext_nbytes % (sizeof(union record))) {
1004  ep->ext_nbytes += (sizeof(union record))
1005  - ep->ext_nbytes % (sizeof(union record));
1006  }
1007  num_recs = ep->ext_nbytes / sizeof(union record) - 1;
1008  ep->ext_buf = (uint8_t *)bu_calloc(1, ep->ext_nbytes, "bot external");
1009  rec = (union record *)ep->ext_buf;
1010 
1011  rec->bot.bot_id = DBID_BOT;
1012 
1013  *(uint32_t *)&rec->bot.bot_nrec[0] = htonl((uint32_t)num_recs);
1014  rec->bot.bot_orientation = bot_ip->orientation;
1015  rec->bot.bot_mode = bot_ip->mode;
1016  rec->bot.bot_err_mode = 0;
1017  *(uint32_t *)&rec->bot.bot_num_verts[0] = htonl(bot_ip->num_vertices);
1018  *(uint32_t *)&rec->bot.bot_num_triangles[0] = htonl(bot_ip->num_faces);
1019 
1020  /* Since libwdb users may want to operate in units other than mm,
1021  * we offer the opportunity to scale the solid (to get it into mm)
1022  * on the way out.
1023  */
1024 
1025 
1026  /* convert from local editing units to mm and export to database
1027  * record format
1028  */
1029  for (i = 0; i < bot_ip->num_vertices; i++) {
1030  /* must be double for import and export */
1031  double tmp[ELEMENTS_PER_POINT];
1032 
1033  VSCALE(tmp, &bot_ip->vertices[i*ELEMENTS_PER_POINT], local2mm);
1034  bu_cv_htond((unsigned char *)&rec->bot.bot_data[i*24], (const unsigned char *)tmp, ELEMENTS_PER_POINT);
1035  }
1036 
1037  chars_used = bot_ip->num_vertices * 24;
1038 
1039  for (i = 0; i < bot_ip->num_faces; i++) {
1040  size_t idx=chars_used + i * 12;
1041 
1042  *(uint32_t *)&rec->bot.bot_data[idx + 0] = htonl(bot_ip->faces[i*ELEMENTS_PER_POINT+0]);
1043  *(uint32_t *)&rec->bot.bot_data[idx + 4] = htonl(bot_ip->faces[i*ELEMENTS_PER_POINT+1]);
1044  *(uint32_t *)&rec->bot.bot_data[idx + 8] = htonl(bot_ip->faces[i*ELEMENTS_PER_POINT+2]);
1045  }
1046 
1047  chars_used += bot_ip->num_faces * 12;
1048 
1049  if (bot_ip->mode == RT_BOT_PLATE || bot_ip->mode == RT_BOT_PLATE_NOCOS) {
1050  for (i = 0; i < bot_ip->num_faces; i++) {
1051  /* must be double for import and export */
1052  double tmp;
1053 
1054  tmp = bot_ip->thickness[i] * local2mm;
1055  bu_cv_htond((unsigned char *)&rec->bot.bot_data[chars_used], (const unsigned char *)&tmp, 1);
1056  chars_used += 8;
1057  }
1058  bu_strlcpy((char *)&rec->bot.bot_data[chars_used], bu_vls_addr(&face_mode), ep->ext_nbytes - (sizeof(struct bot_rec)-1) - chars_used);
1059  bu_vls_free(&face_mode);
1060  }
1061 
1062  return 0;
1063 }
1064 
1065 
1066 int
1067 rt_bot_import5(struct rt_db_internal *ip, const struct bu_external *ep, const fastf_t *mat, const struct db_i *dbip)
1068 {
1069  struct rt_bot_internal *bip;
1070  unsigned char *cp;
1071  size_t i;
1072 
1073  BU_CK_EXTERNAL(ep);
1074  if (dbip) RT_CK_DBI(dbip);
1075 
1076  RT_CK_DB_INTERNAL(ip);
1077  ip->idb_major_type = DB5_MAJORTYPE_BRLCAD;
1078  ip->idb_type = ID_BOT;
1079  ip->idb_meth = &OBJ[ID_BOT];
1080  BU_ALLOC(ip->idb_ptr, struct rt_bot_internal);
1081 
1082  bip = (struct rt_bot_internal *)ip->idb_ptr;
1083  bip->magic = RT_BOT_INTERNAL_MAGIC;
1084 
1085  cp = ep->ext_buf;
1086  bip->num_vertices = ntohl(*(uint32_t *)&cp[0]);
1087  cp += SIZEOF_NETWORK_LONG;
1088  bip->num_faces = ntohl(*(uint32_t *)&cp[0]);
1089  cp += SIZEOF_NETWORK_LONG;
1090  bip->orientation = *cp++;
1091  bip->mode = *cp++;
1092  bip->bot_flags = *cp++;
1093 
1094  if (bip->num_vertices > 0) {
1095  bip->vertices = (fastf_t *)bu_calloc(bip->num_vertices * ELEMENTS_PER_POINT, sizeof(fastf_t), "BOT vertices");
1096  } else {
1097  bip->vertices = (fastf_t *)NULL;
1098  }
1099 
1100  if (bip->num_faces > 0) {
1101  bip->faces = (int *)bu_calloc(bip->num_faces * 3, sizeof(int), "BOT faces");
1102  } else {
1103  bip->faces = (int *)NULL;
1104  }
1105 
1106  if (bip->vertices == NULL || bip->faces == NULL) {
1107  bu_log("WARNING: BoT contains %zu vertices, %zu faces\n", bip->num_vertices, bip->num_faces);
1108  return -1;
1109  }
1110 
1111  if (mat == NULL)
1112  mat = bn_mat_identity;
1113 
1114  for (i = 0; i < bip->num_vertices; i++) {
1115  /* must be double for import and export */
1116  double tmp[ELEMENTS_PER_POINT];
1117 
1118  bu_cv_ntohd((unsigned char *)tmp, (const unsigned char *)cp, ELEMENTS_PER_POINT);
1119  cp += SIZEOF_NETWORK_DOUBLE * ELEMENTS_PER_POINT;
1120  MAT4X3PNT(&(bip->vertices[i*ELEMENTS_PER_POINT]), mat, tmp);
1121  }
1122 
1123  for (i = 0; i < bip->num_faces; i++) {
1124  bip->faces[i*3 + 0] = ntohl(*(uint32_t *)&cp[0]);
1125  cp += SIZEOF_NETWORK_LONG;
1126  bip->faces[i*3 + 1] = ntohl(*(uint32_t *)&cp[0]);
1127  cp += SIZEOF_NETWORK_LONG;
1128  bip->faces[i*3 + 2] = ntohl(*(uint32_t *)&cp[0]);
1129  cp += SIZEOF_NETWORK_LONG;
1130  }
1131 
1132  if (bip->mode == RT_BOT_PLATE || bip->mode == RT_BOT_PLATE_NOCOS) {
1133  bip->thickness = (fastf_t *)bu_calloc(bip->num_faces, sizeof(fastf_t), "BOT thickness");
1134  for (i = 0; i < bip->num_faces; i++) {
1135  double scan;
1136  bu_cv_ntohd((unsigned char *)&scan, cp, 1);
1137  bip->thickness[i] = scan; /* convert double to fastf_t */
1138  cp += SIZEOF_NETWORK_DOUBLE;
1139  }
1140  bip->face_mode = bu_hex_to_bitv((const char *)cp);
1141  while (*(cp++) != '\0');
1142  } else {
1143  bip->thickness = (fastf_t *)NULL;
1144  bip->face_mode = (struct bu_bitv *)NULL;
1145  }
1146 
1147  if (bip->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) {
1148  /* must be double for import and export */
1149  double tmp[ELEMENTS_PER_VECT];
1150 
1151  bip->num_normals = ntohl(*(uint32_t *)&cp[0]);
1152  cp += SIZEOF_NETWORK_LONG;
1153  bip->num_face_normals = ntohl(*(uint32_t *)&cp[0]);
1154  cp += SIZEOF_NETWORK_LONG;
1155 
1156  if (bip->num_normals <= 0) {
1157  bip->normals = (fastf_t *)NULL;
1158  }
1159  if (bip->num_face_normals <= 0) {
1160  bip->face_normals = (int *)NULL;
1161  }
1162  if (bip->num_normals > 0) {
1163  bip->normals = (fastf_t *)bu_calloc(bip->num_normals * 3, sizeof(fastf_t), "BOT normals");
1164 
1165  for (i = 0; i < bip->num_normals; i++) {
1166  bu_cv_ntohd((unsigned char *)tmp, (const unsigned char *)cp, ELEMENTS_PER_VECT);
1167  cp += SIZEOF_NETWORK_DOUBLE * ELEMENTS_PER_VECT;
1168  MAT4X3VEC(&(bip->normals[i*ELEMENTS_PER_VECT]), mat, tmp);
1169  }
1170  }
1171  if (bip->num_face_normals > 0) {
1172  bip->face_normals = (int *)bu_calloc(bip->num_face_normals * 3, sizeof(int), "BOT face normals");
1173 
1174  for (i = 0; i < bip->num_face_normals; i++) {
1175  bip->face_normals[i*3 + 0] = ntohl(*(uint32_t *)&cp[0]);
1176  cp += SIZEOF_NETWORK_LONG;
1177  bip->face_normals[i*3 + 1] = ntohl(*(uint32_t *)&cp[0]);
1178  cp += SIZEOF_NETWORK_LONG;
1179  bip->face_normals[i*3 + 2] = ntohl(*(uint32_t *)&cp[0]);
1180  cp += SIZEOF_NETWORK_LONG;
1181  }
1182  }
1183  } else {
1184  bip->normals = (fastf_t *)NULL;
1185  bip->face_normals = (int *)NULL;
1186  bip->num_normals = 0;
1187  bip->num_face_normals = 0;
1188  }
1189 
1190  bip->tie = NULL;
1191 
1192  return 0; /* OK */
1193 }
1194 
1195 
1196 int
1197 rt_bot_export5(struct bu_external *ep, const struct rt_db_internal *ip, double local2mm, const struct db_i *dbip)
1198 {
1199  struct rt_bot_internal *bip;
1200  struct bu_vls vls = BU_VLS_INIT_ZERO;
1201  unsigned char *cp;
1202  size_t i;
1203  size_t rem;
1204 
1205  RT_CK_DB_INTERNAL(ip);
1206  if (dbip) RT_CK_DBI(dbip);
1207 
1208  if (ip->idb_type != ID_BOT) return -1;
1209  bip = (struct rt_bot_internal *)ip->idb_ptr;
1210  RT_BOT_CK_MAGIC(bip);
1211 
1212  BU_CK_EXTERNAL(ep);
1213 
1214  if (bip->mode == RT_BOT_PLATE || bip->mode == RT_BOT_PLATE_NOCOS) {
1215  /* build hex string for face mode */
1216  if (bip->face_mode)
1217  bu_bitv_to_hex(&vls, bip->face_mode);
1218  }
1219 
1220  ep->ext_nbytes = 3 /* orientation, mode, bot_flags */
1221  + SIZEOF_NETWORK_LONG * (bip->num_faces * 3 + 2) /* faces, num_faces, num_vertices */
1222  + SIZEOF_NETWORK_DOUBLE * bip->num_vertices * 3; /* vertices */
1223 
1224  if (bip->mode == RT_BOT_PLATE || bip->mode == RT_BOT_PLATE_NOCOS) {
1225  ep->ext_nbytes += SIZEOF_NETWORK_DOUBLE * bip->num_faces /* face thicknesses */
1226  + bu_vls_strlen(&vls) + 1; /* face modes */
1227  }
1228 
1229  if (bip->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) {
1230  ep->ext_nbytes += SIZEOF_NETWORK_DOUBLE * bip->num_normals * 3 /* vertex normals */
1231  + SIZEOF_NETWORK_LONG * (bip->num_face_normals * 3 + 2); /* indices into normals array, num_normals, num_face_normals */
1232  }
1233 
1234  ep->ext_buf = (uint8_t *)bu_malloc(ep->ext_nbytes, "BOT external");
1235 
1236  cp = ep->ext_buf;
1237  rem = ep->ext_nbytes;
1238 
1239  *(uint32_t *)&cp[0] = htonl(bip->num_vertices);
1240  cp += SIZEOF_NETWORK_LONG;
1241  rem -= SIZEOF_NETWORK_LONG;
1242 
1243  *(uint32_t *)&cp[0] = htonl(bip->num_faces);
1244  cp += SIZEOF_NETWORK_LONG;
1245  rem -= SIZEOF_NETWORK_LONG;
1246 
1247  *cp++ = bip->orientation;
1248  *cp++ = bip->mode;
1249  *cp++ = bip->bot_flags;
1250  rem -= 3;
1251 
1252  for (i = 0; i < bip->num_vertices; i++) {
1253  /* must be double for import and export */
1254  double tmp[ELEMENTS_PER_POINT];
1255 
1256  VSCALE(tmp, &bip->vertices[i*ELEMENTS_PER_POINT], local2mm);
1257  bu_cv_htond(cp, (unsigned char *)tmp, ELEMENTS_PER_POINT);
1258  cp += SIZEOF_NETWORK_DOUBLE * ELEMENTS_PER_POINT;
1259  rem -= SIZEOF_NETWORK_DOUBLE * ELEMENTS_PER_POINT;
1260  }
1261 
1262  for (i = 0; i < bip->num_faces; i++) {
1263  *(uint32_t *)&cp[0] = htonl(bip->faces[i*3 + 0]);
1264  cp += SIZEOF_NETWORK_LONG;
1265  rem -= SIZEOF_NETWORK_LONG;
1266 
1267  *(uint32_t *)&cp[0] = htonl(bip->faces[i*3 + 1]);
1268  cp += SIZEOF_NETWORK_LONG;
1269  rem -= SIZEOF_NETWORK_LONG;
1270 
1271  *(uint32_t *)&cp[0] = htonl(bip->faces[i*3 + 2]);
1272  cp += SIZEOF_NETWORK_LONG;
1273  rem -= SIZEOF_NETWORK_LONG;
1274  }
1275 
1276  if (bip->mode == RT_BOT_PLATE || bip->mode == RT_BOT_PLATE_NOCOS) {
1277  for (i = 0; i < bip->num_faces; i++) {
1278  /* must be double for import and export */
1279  double tmp;
1280 
1281  tmp = bip->thickness[i] * local2mm;
1282  bu_cv_htond(cp, (const unsigned char *)&tmp, 1);
1283  cp += SIZEOF_NETWORK_DOUBLE;
1284  rem -= SIZEOF_NETWORK_DOUBLE;
1285  }
1286  bu_strlcpy((char *)cp, bu_vls_addr(&vls), rem);
1287  cp += bu_vls_strlen(&vls);
1288  rem -= bu_vls_strlen(&vls);
1289  *cp = '\0';
1290  cp++;
1291  rem--;
1292  bu_vls_free(&vls);
1293  }
1294 
1295  if (bip->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) {
1296  *(uint32_t *)&cp[0] = htonl(bip->num_normals);
1297  cp += SIZEOF_NETWORK_LONG;
1298  rem -= SIZEOF_NETWORK_LONG;
1299 
1300  *(uint32_t *)&cp[0] = htonl(bip->num_face_normals);
1301  cp += SIZEOF_NETWORK_LONG;
1302  rem -= SIZEOF_NETWORK_LONG;
1303 
1304  if (bip->num_normals > 0) {
1305  /* must be double for import and export */
1306  double *normals;
1307  normals = (double *)bu_malloc(bip->num_normals*ELEMENTS_PER_VECT*sizeof(double), "normals");
1308 
1309  /* convert fastf_t to double */
1310  for (i = 0; i < bip->num_normals * ELEMENTS_PER_VECT; i++) {
1311  normals[i] = bip->normals[i];
1312  }
1313 
1314  bu_cv_htond(cp, (unsigned char*)normals, bip->num_normals*ELEMENTS_PER_VECT);
1315 
1316  bu_free(normals, "normals");
1317 
1318  cp += SIZEOF_NETWORK_DOUBLE * ELEMENTS_PER_VECT * bip->num_normals;
1319  rem -= SIZEOF_NETWORK_DOUBLE * ELEMENTS_PER_VECT * bip->num_normals;
1320  }
1321  if (bip->num_face_normals > 0) {
1322  for (i = 0; i < bip->num_face_normals; i++) {
1323  *(uint32_t *)&cp[0] = htonl(bip->face_normals[i*ELEMENTS_PER_VECT + 0]);
1324  cp += SIZEOF_NETWORK_LONG;
1325  rem -= SIZEOF_NETWORK_LONG;
1326 
1327  *(uint32_t *)&cp[0] = htonl(bip->face_normals[i*ELEMENTS_PER_VECT + 1]);
1328  cp += SIZEOF_NETWORK_LONG;
1329  rem -= SIZEOF_NETWORK_LONG;
1330 
1331  *(uint32_t *)&cp[0] = htonl(bip->face_normals[i*ELEMENTS_PER_VECT + 2]);
1332  cp += SIZEOF_NETWORK_LONG;
1333  rem -= SIZEOF_NETWORK_LONG;
1334  }
1335  }
1336  }
1337 
1338  return 0;
1339 }
1340 
1341 
1342 static char *unoriented="unoriented";
1343 static char *ccw="counter-clockwise";
1344 static char *cw="clockwise";
1345 static char *unknown_orientation="unknown orientation";
1346 static char *surface="\tThis is a surface with no volume\n";
1347 static char *solid="\tThis is a solid object (not just a surface)\n";
1348 static char *plate="\tThis is a FASTGEN plate mode solid\n";
1349 static char *nocos="\tThis is a plate mode solid with no obliquity angle effect\n";
1350 static char *unknown_mode="\tunknown mode\n";
1351 
1352 /**
1353  * Make human-readable formatted presentation of this solid. First
1354  * line describes type of solid. Additional lines are indented one
1355  * tab, and give parameter values.
1356  */
1357 int
1358 rt_bot_describe(struct bu_vls *str, const struct rt_db_internal *ip, int verbose, double mm2local)
1359 {
1360  struct rt_bot_internal *bot_ip =
1361  (struct rt_bot_internal *)ip->idb_ptr;
1362  char buf[256];
1363  char *orientation, *mode;
1364  size_t i;
1365 
1366  size_t badVertexCount = 0;
1367 
1368  RT_BOT_CK_MAGIC(bot_ip);
1369  bu_vls_strcat(str, "Bag of triangles (BOT)\n");
1370 
1371  switch (bot_ip->orientation) {
1372  case RT_BOT_UNORIENTED:
1373  orientation = unoriented;
1374  break;
1375  case RT_BOT_CCW:
1376  orientation = ccw;
1377  break;
1378  case RT_BOT_CW:
1379  orientation = cw;
1380  break;
1381  default:
1382  orientation = unknown_orientation;
1383  break;
1384  }
1385  switch (bot_ip->mode) {
1386  case RT_BOT_SURFACE:
1387  mode = surface;
1388  break;
1389  case RT_BOT_SOLID:
1390  mode = solid;
1391  break;
1392  case RT_BOT_PLATE:
1393  mode = plate;
1394  break;
1395  case RT_BOT_PLATE_NOCOS:
1396  mode = nocos;
1397  break;
1398  default:
1399  mode = unknown_mode;
1400  break;
1401  }
1402  snprintf(buf, 256, "\t%lu vertices, %lu faces (%s)\n",
1403  (long unsigned)bot_ip->num_vertices,
1404  (long unsigned)bot_ip->num_faces,
1405  orientation);
1406  bu_vls_strcat(str, buf);
1407  bu_vls_strcat(str, mode);
1408  if ((bot_ip->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) && bot_ip->num_normals > 0) {
1409  bu_vls_strcat(str, "\twith surface normals");
1410  if (bot_ip->bot_flags & RT_BOT_USE_NORMALS) {
1411  bu_vls_strcat(str, " (they will be used)\n");
1412  } else {
1413  bu_vls_strcat(str, " (they will be ignored)\n");
1414  }
1415  }
1416 
1417  if (!verbose)
1418  return 0;
1419 
1420  for (i = 0; i < bot_ip->num_faces; i++) {
1421  size_t j, k;
1422  point_t pt[3];
1423 
1424  snprintf(buf, 256, "\tface %lu:", (long unsigned)i);
1425  bu_vls_strcat(str, buf);
1426 
1427  for (j = 0; j < 3; j++) {
1428  size_t ptnum;
1429 
1430  ptnum = bot_ip->faces[i*3+j];
1431  if (ptnum >= bot_ip->num_vertices) {
1432  bu_vls_strcat(str, " (\?\?\? \?\?\? \?\?\?)");
1433  badVertexCount++;
1434  } else {
1435  VSCALE(pt[j], &bot_ip->vertices[ptnum*3], mm2local);
1436  snprintf(buf, 256, " (%g %g %g)", V3INTCLAMPARGS(pt[j]));
1437  bu_vls_strcat(str, buf);
1438  }
1439  }
1440  if ((bot_ip->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) && bot_ip->num_normals > 0) {
1441  bu_vls_strcat(str, " normals: ");
1442  for (k = 0; k < 3; k++) {
1443  size_t idx;
1444 
1445  idx = i*3 + k;
1446  if ((size_t)bot_ip->face_normals[idx] >= bot_ip->num_normals) {
1447  bu_vls_strcat(str, "none ");
1448  } else {
1449  snprintf(buf, 256, "(%g %g %g) ", V3INTCLAMPARGS(&bot_ip->normals[bot_ip->face_normals[idx]*3]));
1450  bu_vls_strcat(str, buf);
1451  }
1452  }
1453  bu_vls_strcat(str, "\n");
1454  } else {
1455  bu_vls_strcat(str, "\n");
1456  }
1457  if (bot_ip->mode == RT_BOT_PLATE || bot_ip->mode == RT_BOT_PLATE_NOCOS) {
1458  char *face_mode;
1459 
1460  if (BU_BITTEST(bot_ip->face_mode, i))
1461  face_mode = "appended to hit point";
1462  else
1463  face_mode = "centered about hit point";
1464  snprintf(buf, 256, "\t\tthickness = %g, %s\n", INTCLAMP(mm2local*bot_ip->thickness[i]), face_mode);
1465  bu_vls_strcat(str, buf);
1466  }
1467  }
1468  if (badVertexCount > 0) {
1469  snprintf(buf, 256, "\tThis BOT has %lu invalid references to vertices\n", (long unsigned)badVertexCount);
1470  bu_vls_strcat(str, buf);
1471  }
1472 
1473  return 0;
1474 }
1475 
1476 
1477 HIDDEN void
1478 bot_ifree2(struct rt_bot_internal *bot_ip)
1479 {
1480  RT_BOT_CK_MAGIC(bot_ip);
1481  bot_ip->magic = 0; /* sanity */
1482 
1483  if (bot_ip->tie != NULL) {
1484  bot_ip->tie = NULL;
1485  }
1486 
1487  if (bot_ip->vertices != NULL) {
1488  bu_free(bot_ip->vertices, "BOT vertices");
1489  bot_ip->vertices = NULL;
1490  bot_ip->num_vertices = 0;
1491  }
1492  if (bot_ip->faces != NULL) {
1493  bu_free(bot_ip->faces, "BOT faces");
1494  bot_ip->faces = NULL;
1495  bot_ip->num_faces = 0;
1496  }
1497 
1498  if (bot_ip->mode == RT_BOT_PLATE || bot_ip->mode == RT_BOT_PLATE_NOCOS) {
1499  if (bot_ip->thickness != NULL) {
1500  bu_free(bot_ip->thickness, "BOT thickness");
1501  bot_ip->thickness = NULL;
1502  }
1503  if (bot_ip->face_mode != NULL) {
1504  bu_free(bot_ip->face_mode, "BOT face_mode");
1505  bot_ip->face_mode = NULL;
1506  }
1507  }
1508 
1509  if (bot_ip->normals != NULL) {
1510  bu_free(bot_ip->normals, "BOT normals");
1511  }
1512 
1513  if (bot_ip->face_normals != NULL) {
1514  bu_free(bot_ip->face_normals, "BOT normals");
1515  }
1516 
1517  bu_free(bot_ip, "bot ifree");
1518 }
1519 
1520 
1521 /**
1522  * Free the storage associated with the rt_db_internal version of this
1523  * solid.
1524  */
1525 void
1527 {
1528  struct rt_bot_internal *bot_ip;
1529 
1530  RT_CK_DB_INTERNAL(ip);
1531 
1532  bot_ip = (struct rt_bot_internal *)ip->idb_ptr;
1533  bot_ifree2(bot_ip);
1534  ip->idb_ptr = NULL; /* sanity */
1535 }
1536 
1537 
1538 int
1539 rt_bot_xform(struct rt_db_internal *op, const fastf_t *mat, struct rt_db_internal *ip, const int release, struct db_i *dbip)
1540 {
1541  struct rt_bot_internal *botip, *botop;
1542  size_t i;
1543  point_t pt;
1544 
1545  RT_CK_DB_INTERNAL(ip);
1546  botip = (struct rt_bot_internal *)ip->idb_ptr;
1547  RT_BOT_CK_MAGIC(botip);
1548  if (dbip) RT_CK_DBI(dbip);
1549 
1550  if (op != ip && !release) {
1551  RT_DB_INTERNAL_INIT(op);
1552  BU_ALLOC(botop, struct rt_bot_internal);
1553  botop->magic = RT_BOT_INTERNAL_MAGIC;
1554  botop->mode = botip->mode;
1555  botop->orientation = botip->orientation;
1556  botop->bot_flags = botip->bot_flags;
1557  botop->num_vertices = botip->num_vertices;
1558  botop->num_faces = botip->num_faces;
1559  if (botop->num_vertices > 0) {
1560  botop->vertices = (fastf_t *)bu_malloc(botip->num_vertices * ELEMENTS_PER_POINT * sizeof(fastf_t), "botop->vertices");
1561  }
1562  if (botop->num_faces > 0) {
1563  botop->faces = (int *)bu_malloc(botip->num_faces * 3 * sizeof(int), "botop->faces");
1564  memcpy(botop->faces, botip->faces, botop->num_faces * 3 * sizeof(int));
1565  }
1566  if (botip->thickness)
1567  botop->thickness = (fastf_t *)bu_malloc(botip->num_faces * sizeof(fastf_t), "botop->thickness");
1568  if (botip->face_mode)
1569  botop->face_mode = bu_bitv_dup(botip->face_mode);
1570  if (botip->thickness) {
1571  for (i = 0; i < botip->num_faces; i++)
1572  botop->thickness[i] = botip->thickness[i];
1573  }
1574 
1575  if (botop->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) {
1576  botop->num_normals = botip->num_normals;
1577  botop->normals = (fastf_t *)bu_calloc(botop->num_normals * 3, sizeof(fastf_t), "BOT normals");
1578  botop->face_normals = (int *)bu_calloc(botop->num_faces * 3, sizeof(int), "BOT face normals");
1579  memcpy(botop->face_normals, botip->face_normals, botop->num_faces * 3 * sizeof(int));
1580  }
1581  op->idb_ptr = (void *)botop;
1582  op->idb_major_type = DB5_MAJORTYPE_BRLCAD;
1583  op->idb_type = ID_BOT;
1584  op->idb_meth = &OBJ[ID_BOT];
1585  } else
1586  botop = botip;
1587 
1588  if (ip != op) {
1589  if (ip->idb_avs.magic == BU_AVS_MAGIC) {
1590  bu_avs_init(&op->idb_avs, ip->idb_avs.count, "avs");
1591  bu_avs_merge(&op->idb_avs, &ip->idb_avs);
1592  }
1593  }
1594 
1595  for (i = 0; i < botip->num_vertices; i++) {
1596  MAT4X3PNT(pt, mat, &botip->vertices[i*ELEMENTS_PER_POINT]);
1597  VMOVE(&botop->vertices[i*ELEMENTS_PER_POINT], pt);
1598  }
1599 
1600  for (i = 0; i < botip->num_normals; i++) {
1601  MAT4X3VEC(pt, mat, &botip->normals[i*3]);
1602  VMOVE(&botop->normals[i*3], pt);
1603  }
1604 
1605  if (release && op != ip) {
1606  rt_bot_ifree(ip);
1607  }
1608 
1609  return 0;
1610 }
1611 
1612 
1613 int
1615  const struct rt_bot_internal *bot,
1616  const point_t pt2,
1617  const mat_t mat)
1618 {
1619  point_t v;
1620  size_t idx;
1621  fastf_t dist=MAX_FASTF;
1622  int closest=-1;
1623 
1624  RT_BOT_CK_MAGIC(bot);
1625 
1626  for (idx = 0; idx < bot->num_vertices; idx++) {
1627  fastf_t tmp_dist;
1628  fastf_t tmpx, tmpy;
1629 
1630  MAT4X3PNT(v, mat, &bot->vertices[idx*ELEMENTS_PER_POINT]);
1631  tmpx = v[X] - pt2[X];
1632  tmpy = v[Y] - pt2[Y];
1633  tmp_dist = tmpx * tmpx + tmpy * tmpy;
1634  if (tmp_dist < dist) {
1635  dist = tmp_dist;
1636  closest = idx;
1637  }
1638  }
1639 
1640  return closest;
1641 }
1642 
1643 
1644 size_t
1645 rt_bot_get_edge_list(const struct rt_bot_internal *bot, size_t **edge_list)
1646 {
1647  size_t i;
1648  size_t edge_count = 0;
1649  size_t v1, v2, v3;
1650 
1651  if (bot->num_faces < 1)
1652  return edge_count;
1653 
1654  *edge_list = (size_t *)bu_calloc(bot->num_faces * 3 * 2, sizeof(size_t), "bot edge list");
1655 
1656  for (i = 0; i < bot->num_faces; i++) {
1657  v1 = bot->faces[i*3 + 0];
1658  v2 = bot->faces[i*3 + 1];
1659  v3 = bot->faces[i*3 + 2];
1660 
1661  if (!rt_bot_edge_in_list(v1, v2, *edge_list, edge_count)) {
1662  (*edge_list)[edge_count*2 + 0] = v1;
1663  (*edge_list)[edge_count*2 + 1] = v2;
1664  edge_count++;
1665  }
1666  if (!rt_bot_edge_in_list(v3, v2, *edge_list, edge_count)) {
1667  (*edge_list)[edge_count*2 + 0] = v3;
1668  (*edge_list)[edge_count*2 + 1] = v2;
1669  edge_count++;
1670  }
1671  if (!rt_bot_edge_in_list(v1, v3, *edge_list, edge_count)) {
1672  (*edge_list)[edge_count*2 + 0] = v1;
1673  (*edge_list)[edge_count*2 + 1] = v3;
1674  edge_count++;
1675  }
1676  }
1677 
1678  return edge_count;
1679 }
1680 
1681 
1682 int
1683 rt_bot_edge_in_list(const size_t v1, const size_t v2, const size_t edge_list[], const size_t edge_count)
1684 {
1685  size_t i;
1686  size_t ev1, ev2;
1687 
1688  for (i = 0; i < edge_count; i++) {
1689  ev1 = edge_list[i*2 + 0];
1690  ev2 = edge_list[i*2 + 1];
1691 
1692  if (ev1 == v1 && ev2 == v2)
1693  return 1;
1694 
1695  if (ev1 == v2 && ev2 == v1)
1696  return 1;
1697  }
1698 
1699  return 0;
1700 }
1701 
1702 
1703 /**
1704  * This routine finds the edge closest to the 2D point "pt2", and
1705  * returns the edge as two vertex indices (vert1 and vert2). These
1706  * vertices are ordered (closest to pt2 is first)
1707  */
1708 int
1710  int *vert1,
1711  int *vert2,
1712  const struct rt_bot_internal *bot,
1713  const point_t pt2,
1714  const mat_t mat)
1715 {
1716  size_t i;
1717  fastf_t dist=MAX_FASTF, tmp_dist;
1718  size_t *edge_list;
1719  size_t edge_count = 0;
1720  struct bn_tol tol;
1721 
1722  RT_BOT_CK_MAGIC(bot);
1723 
1724  if (bot->num_faces < 1)
1725  return -1;
1726 
1727  /* first build a list of edges */
1728  if ((edge_count = rt_bot_get_edge_list(bot, &edge_list)) == 0)
1729  return -1;
1730 
1731  /* build a tolerance structure for the bn_dist routine */
1732  tol.magic = BN_TOL_MAGIC;
1733  tol.dist = 0.0;
1734  tol.dist_sq = 0.0;
1735  tol.perp = 0.0;
1736  tol.para = 1.0;
1737 
1738  /* now look for the closest edge */
1739  for (i = 0; i < edge_count; i++) {
1740  point_t p1, p2, pca;
1741  vect_t p1_to_pca, p1_to_p2;
1742  int ret;
1743 
1744  MAT4X3PNT(p1, mat, &bot->vertices[ edge_list[i*2+0]*3]);
1745  MAT4X3PNT(p2, mat, &bot->vertices[ edge_list[i*2+1]*3]);
1746  p1[Z] = 0.0;
1747  p2[Z] = 0.0;
1748 
1749  ret = bn_dist_pt2_lseg2(&tmp_dist, pca, p1, p2, pt2, &tol);
1750 
1751  if (ret < 3 || tmp_dist < dist) {
1752  switch (ret) {
1753  case 0:
1754  dist = 0.0;
1755  if (tmp_dist < 0.5) {
1756  *vert1 = edge_list[i*2+0];
1757  *vert2 = edge_list[i*2+1];
1758  } else {
1759  *vert1 = edge_list[i*2+1];
1760  *vert2 = edge_list[i*2+0];
1761  }
1762  break;
1763  case 1:
1764  dist = 0.0;
1765  *vert1 = edge_list[i*2+0];
1766  *vert2 = edge_list[i*2+1];
1767  break;
1768  case 2:
1769  dist = 0.0;
1770  *vert1 = edge_list[i*2+1];
1771  *vert2 = edge_list[i*2+0];
1772  break;
1773  case 3:
1774  dist = tmp_dist;
1775  *vert1 = edge_list[i*2+0];
1776  *vert2 = edge_list[i*2+1];
1777  break;
1778  case 4:
1779  dist = tmp_dist;
1780  *vert1 = edge_list[i*2+1];
1781  *vert2 = edge_list[i*2+0];
1782  break;
1783  case 5:
1784  dist = tmp_dist;
1785  V2SUB2(p1_to_pca, pca, p1);
1786  V2SUB2(p1_to_p2, p2, p1);
1787  if (MAG2SQ(p1_to_pca) / MAG2SQ(p1_to_p2) < 0.25) {
1788  *vert1 = edge_list[i*2+0];
1789  *vert2 = edge_list[i*2+1];
1790  } else {
1791  *vert1 = edge_list[i*2+1];
1792  *vert2 = edge_list[i*2+0];
1793  }
1794  break;
1795  }
1796  }
1797  }
1798 
1799  bu_free(edge_list, "bot edge list");
1800 
1801  return 0;
1802 }
1803 
1804 
1805 static char *modes[]={
1806  "ERROR: Unrecognized mode",
1807  "surf",
1808  "volume",
1809  "plate",
1810  "plate_nocos"
1811 };
1812 
1813 
1814 static char *orientation[]={
1815  "ERROR: Unrecognized orientation",
1816  "no",
1817  "rh",
1818  "lh"
1819 };
1820 
1821 
1822 static char *los[]={
1823  "center",
1824  "append"
1825 };
1826 
1827 
1828 /**
1829  * Examples -
1830  * db get name fm get los facemode bit vector
1831  * db get name fm# get los face mode of face # (center, append)
1832  * db get name V get coords for all vertices
1833  * db get name V# get coords for vertex #
1834  * db get name F get vertex indices for all faces
1835  * db get name F# get vertex indices for face #
1836  * db get name f get list of coords for all faces
1837  * db get name f# get list of 3 3tuple coords for face #
1838  * db get name T get thickness for all faces
1839  * db get name T# get thickness for face #
1840  * db get name N get list of normals
1841  * db get name N# get coords for normal #
1842  * db get name fn get list indices into normal vectors for all faces
1843  * db get name fn# get list indices into normal vectors for face #
1844  * db get name nv get num_vertices
1845  * db get name nt get num_faces
1846  * db get name nn get num_normals
1847  * db get name nfn get num_face_normals
1848  * db get name mode get mode (surf, volume, plate, plane_nocos)
1849  * db get name orient get orientation (no, rh, lh)
1850  * db get name flags get BOT flags
1851  */
1852 int
1853 rt_bot_get(struct bu_vls *logstr, const struct rt_db_internal *intern, const char *attr)
1854 {
1855  struct rt_bot_internal *bot=(struct rt_bot_internal *)intern->idb_ptr;
1856  int status;
1857  size_t i;
1858  long li;
1859 
1860  RT_BOT_CK_MAGIC(bot);
1861 
1862  if (attr == (char *)NULL) {
1863  bu_vls_strcpy(logstr, "bot");
1864  bu_vls_printf(logstr, " mode %s orient %s",
1865  modes[bot->mode], orientation[bot->orientation]);
1866  bu_vls_printf(logstr, " flags {");
1867  if (bot->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) {
1868  bu_vls_printf(logstr, " has_normals");
1869  }
1870  if (bot->bot_flags & RT_BOT_USE_NORMALS) {
1871  bu_vls_printf(logstr, " use_normals");
1872  }
1873  if (bot->bot_flags & RT_BOT_USE_FLOATS) {
1874  bu_vls_printf(logstr, " use_floats");
1875  }
1876  bu_vls_printf(logstr, "} V {");
1877  for (i = 0; i < bot->num_vertices; i++)
1878  bu_vls_printf(logstr, " { %.25G %.25G %.25G }",
1879  V3ARGS(&bot->vertices[i*3]));
1880  bu_vls_strcat(logstr, "} F {");
1881  for (i = 0; i < bot->num_faces; i++)
1882  bu_vls_printf(logstr, " { %d %d %d }",
1883  V3ARGS(&bot->faces[i*3]));
1884  bu_vls_strcat(logstr, "}");
1885  if (bot->mode == RT_BOT_PLATE || bot->mode == RT_BOT_PLATE_NOCOS) {
1886  bu_vls_strcat(logstr, " T {");
1887  for (i = 0; i < bot->num_faces; i++)
1888  bu_vls_printf(logstr, " %.25G", bot->thickness[i]);
1889  bu_vls_strcat(logstr, "} fm ");
1890  bu_bitv_to_hex(logstr, bot->face_mode);
1891  }
1892  if (bot->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) {
1893  bu_vls_printf(logstr, " N {");
1894  for (i = 0; i < bot->num_normals; i++) {
1895  bu_vls_printf(logstr, " { %.25G %.25G %.25G }", V3ARGS(&bot->normals[i*3]));
1896  }
1897  bu_vls_printf(logstr, "} fn {");
1898  for (i = 0; i < bot->num_face_normals; i++) {
1899  bu_vls_printf(logstr, " { %d %d %d }", V3ARGS(&bot->face_normals[i*3]));
1900  }
1901  bu_vls_printf(logstr, "}");
1902  }
1903  status = BRLCAD_OK;
1904  } else {
1905  if (attr[0] == 'N') {
1906  if (attr[1] == '\0') {
1907  if (!(bot->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) || bot->num_normals < 1) {
1908  bu_vls_strcat(logstr, "{}");
1909  } else {
1910  for (i = 0; i < bot->num_normals; i++) {
1911  bu_vls_printf(logstr, " { %.25G %.25G %.25G }", V3ARGS(&bot->normals[i*3]));
1912  }
1913  }
1914  status = BRLCAD_OK;
1915  } else {
1916  li = atol(&attr[1]);
1917  if (li < 0 || (size_t)li >= bot->num_normals) {
1918  bu_vls_printf(logstr, "Specified normal index [%ld] is out of range", li);
1919  status = BRLCAD_ERROR;
1920  } else {
1921  bu_vls_printf(logstr, "%.25G %.25G %.25G", V3ARGS(&bot->normals[li*3]));
1922  status = BRLCAD_OK;
1923  }
1924  }
1925  } else if (!bu_strncmp(attr, "fn", 2)) {
1926  if (attr[2] == '\0') {
1927  for (i = 0; i < bot->num_face_normals; i++) {
1928  bu_vls_printf(logstr, " { %d %d %d }", V3ARGS(&bot->face_normals[i*3]));
1929  }
1930  status = BRLCAD_OK;
1931  } else {
1932  li = atol(&attr[2]);
1933  if (li < 0 || (size_t)li >= bot->num_face_normals) {
1934  bu_vls_printf(logstr, "Specified face index [%ld] is out of range", li);
1935  status = BRLCAD_ERROR;
1936  } else {
1937  bu_vls_printf(logstr, "%d %d %d", V3ARGS(&bot->face_normals[li*3]));
1938  status = BRLCAD_OK;
1939  }
1940  }
1941  } else if (BU_STR_EQUAL(attr, "nn")) {
1942  if (!(bot->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) || bot->num_normals < 1) {
1943  bu_vls_strcat(logstr, "0");
1944  } else {
1945  bu_vls_printf(logstr, "%lu", (long unsigned)bot->num_normals);
1946  }
1947  status = BRLCAD_OK;
1948  } else if (BU_STR_EQUAL(attr, "nfn")) {
1949  if (!(bot->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) || bot->num_face_normals < 1) {
1950  bu_vls_strcat(logstr, "0");
1951  } else {
1952  bu_vls_printf(logstr, "%lu", (long unsigned)bot->num_face_normals);
1953  }
1954  status = BRLCAD_OK;
1955  } else if (!bu_strncmp(attr, "fm", 2)) {
1956  if (bot->mode != RT_BOT_PLATE && bot->mode != RT_BOT_PLATE_NOCOS) {
1957  bu_vls_strcat(logstr, "Only plate mode BOTs have face_modes");
1958  status = BRLCAD_ERROR;
1959  } else {
1960  if (attr[2] == '\0') {
1961  bu_bitv_to_hex(logstr, bot->face_mode);
1962  status = BRLCAD_OK;
1963  } else {
1964  li = atol(&attr[2]);
1965  if (li < 0 || (size_t)li >= bot->num_faces) {
1966  bu_vls_printf(logstr, "face number [%ld] out of range (0..%zu)", li, bot->num_faces-1);
1967  status = BRLCAD_ERROR;
1968  } else {
1969  bu_vls_printf(logstr, "%s",
1970  los[BU_BITTEST(bot->face_mode, li)?1:0]);
1971  status = BRLCAD_OK;
1972  }
1973  }
1974  }
1975  } else if (attr[0] == 'V') {
1976  if (attr[1] != '\0') {
1977  li = atol(&attr[1]);
1978  if (li < 0 || (size_t)li >= bot->num_vertices) {
1979  bu_vls_printf(logstr, "vertex number [%ld] out of range (0..%zu)", li, bot->num_vertices-1);
1980  status = BRLCAD_ERROR;
1981  } else {
1982  bu_vls_printf(logstr, "%.25G %.25G %.25G",
1983  V3ARGS(&bot->vertices[li*3]));
1984  status = BRLCAD_OK;
1985  }
1986  } else {
1987  for (i = 0; i < bot->num_vertices; i++)
1988  bu_vls_printf(logstr, " { %.25G %.25G %.25G }",
1989  V3ARGS(&bot->vertices[i*3]));
1990  status = BRLCAD_OK;
1991  }
1992  } else if (attr[0] == 'F') {
1993  /* Retrieve one face, as vertex indices */
1994  if (attr[1] == '\0') {
1995  for (i = 0; i < bot->num_faces; i++)
1996  bu_vls_printf(logstr, " { %d %d %d }",
1997  V3ARGS(&bot->faces[i*3]));
1998  status = BRLCAD_OK;
1999  } else {
2000  li = atol(&attr[1]);
2001  if (li < 0 || (size_t)li >= bot->num_faces) {
2002  bu_vls_printf(logstr, "face number [%ld] out of range (0..%zu)", li, bot->num_faces-1);
2003  status = BRLCAD_ERROR;
2004  } else {
2005  bu_vls_printf(logstr, "%d %d %d",
2006  V3ARGS(&bot->faces[li*3]));
2007  status = BRLCAD_OK;
2008  }
2009  }
2010  } else if (BU_STR_EQUAL(attr, "flags")) {
2011  bu_vls_printf(logstr, "{");
2012  if (bot->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) {
2013  bu_vls_printf(logstr, " has_normals");
2014  }
2015  if (bot->bot_flags & RT_BOT_USE_NORMALS) {
2016  bu_vls_printf(logstr, " use_normals");
2017  }
2018  if (bot->bot_flags & RT_BOT_USE_FLOATS) {
2019  bu_vls_printf(logstr, " use_floats");
2020  }
2021  bu_vls_printf(logstr, "}");
2022  status = BRLCAD_OK;
2023  } else if (attr[0] == 'f') {
2024  size_t indx;
2025  /* Retrieve one face, as list of 3 3tuple coordinates */
2026  if (attr[1] == '\0') {
2027  for (i = 0; i < bot->num_faces; i++) {
2028  indx = bot->faces[i*3+0];
2029  bu_vls_printf(logstr, " { %.25G %.25G %.25G }",
2030  bot->vertices[indx*3+0],
2031  bot->vertices[indx*3+1],
2032  bot->vertices[indx*3+2]);
2033  indx = bot->faces[i*3+1];
2034  bu_vls_printf(logstr, " { %.25G %.25G %.25G }",
2035  bot->vertices[indx*3+0],
2036  bot->vertices[indx*3+1],
2037  bot->vertices[indx*3+2]);
2038  indx = bot->faces[i*3+2];
2039  bu_vls_printf(logstr, " { %.25G %.25G %.25G }",
2040  bot->vertices[indx*3+0],
2041  bot->vertices[indx*3+1],
2042  bot->vertices[indx*3+2]);
2043  }
2044  status = BRLCAD_OK;
2045  } else {
2046  li = atol(&attr[1]);
2047  if (li < 0 || (size_t)li >= bot->num_faces) {
2048  bu_vls_printf(logstr, "face number [%ld] out of range (0..%zu)", li, bot->num_faces-1);
2049  status = BRLCAD_ERROR;
2050  } else {
2051  indx = bot->faces[li*3+0];
2052  bu_vls_printf(logstr, " { %.25G %.25G %.25G }",
2053  bot->vertices[indx*3+0],
2054  bot->vertices[indx*3+1],
2055  bot->vertices[indx*3+2]);
2056  indx = bot->faces[li*3+1];
2057  bu_vls_printf(logstr, " { %.25G %.25G %.25G }",
2058  bot->vertices[indx*3+0],
2059  bot->vertices[indx*3+1],
2060  bot->vertices[indx*3+2]);
2061  indx = bot->faces[li*3+2];
2062  bu_vls_printf(logstr, " { %.25G %.25G %.25G }",
2063  bot->vertices[indx*3+0],
2064  bot->vertices[indx*3+1],
2065  bot->vertices[indx*3+2]);
2066  status = BRLCAD_OK;
2067  }
2068  }
2069  } else if (attr[0] == 'T') {
2070  if (bot->mode != RT_BOT_PLATE && bot->mode != RT_BOT_PLATE_NOCOS) {
2071  bu_vls_strcat(logstr, "Only plate mode BOTs have thicknesses");
2072  status = BRLCAD_ERROR;
2073  } else {
2074  if (attr[1] == '\0') {
2075  for (i = 0; i < bot->num_faces; i++)
2076  bu_vls_printf(logstr, " %.25G", bot->thickness[i]);
2077  status = BRLCAD_OK;
2078  } else {
2079  li = atol(&attr[1]);
2080  if (li < 0 || (size_t)li >= bot->num_faces) {
2081  bu_vls_printf(logstr, "face number [%ld] out of range (0..%zu)", li, bot->num_faces-1);
2082  status = BRLCAD_ERROR;
2083  } else {
2084  bu_vls_printf(logstr, " %.25G", bot->thickness[li]);
2085  status = BRLCAD_OK;
2086  }
2087  }
2088  }
2089  } else if (BU_STR_EQUAL(attr, "nv")) {
2090  bu_vls_printf(logstr, "%zu", bot->num_vertices);
2091  status = BRLCAD_OK;
2092  } else if (BU_STR_EQUAL(attr, "nt")) {
2093  bu_vls_printf(logstr, "%zu", bot->num_faces);
2094  status = BRLCAD_OK;
2095  } else if (BU_STR_EQUAL(attr, "mode")) {
2096  bu_vls_printf(logstr, "%s", modes[bot->mode]);
2097  status = BRLCAD_OK;
2098  } else if (BU_STR_EQUAL(attr, "orient")) {
2099  bu_vls_printf(logstr, "%s", orientation[bot->orientation]);
2100  status = BRLCAD_OK;
2101  } else {
2102  bu_vls_printf(logstr, "BoT has no attribute '%s'", attr);
2103  status = BRLCAD_ERROR;
2104  }
2105  }
2106 
2107  return status;
2108 }
2109 
2110 
2111 int
2112 bot_check_vertex_indices(struct bu_vls *logstr, struct rt_bot_internal *bot)
2113 {
2114  size_t badVertexCount = 0;
2115  size_t i;
2116  for (i = 0; i < bot->num_faces; i++) {
2117  int k;
2118  for (k = 0; k < 3; k++) {
2119  int vertex_no = bot->faces[i*3+k];
2120  if (vertex_no < 0 || (size_t)vertex_no >= bot->num_vertices) {
2121  bu_vls_printf(logstr, "WARNING: BOT has illegal vertex index (%d) in face #(%zu)\n", vertex_no, i);
2122  badVertexCount++;
2123  }
2124  }
2125  }
2126  return badVertexCount;
2127 }
2128 
2129 
2130 /**
2131  * Examples -
2132  * db adjust name fm set los facemode bit vector
2133  * db adjust name fm# set los face mode of face # (center, append)
2134  * db adjust name V set coords for all vertices
2135  * db adjust name V# set coords for vertex #
2136  * db adjust name F set vertex indices for all faces
2137  * db adjust name F# set vertex indices for face #
2138  * db adjust name T set thickness for all faces
2139  * db adjust name T# set thickness for face #
2140  * db adjust name N set list of normals
2141  * db adjust name N# set coords for normal #
2142  * db adjust name fn set list indices into normal vectors for all faces
2143  * db adjust name fn# set list indices into normal vectors for face #
2144  * db adjust name nn set num_normals
2145  * db adjust name mode set mode (surf, volume, plate, plane_nocos)
2146  * db adjust name orient set orientation (no, rh, lh)
2147  * db adjust name flags set flags
2148  */
2149 int
2150 rt_bot_adjust(struct bu_vls *logstr, struct rt_db_internal *intern, int argc, const char **argv)
2151 {
2152  struct rt_bot_internal *bot;
2153  Tcl_Obj *obj, **obj_array;
2154  int len;
2155  size_t i;
2156  long li;
2157 
2158  RT_CK_DB_INTERNAL(intern);
2159  bot = (struct rt_bot_internal *)intern->idb_ptr;
2160  RT_BOT_CK_MAGIC(bot);
2161 
2162  while (argc >= 2) {
2163  obj = Tcl_NewStringObj(argv[1], -1);
2164 
2165  if (!bu_strncmp(argv[0], "fm", 2)) {
2166  if (argv[0][2] == '\0') {
2167  if (bot->face_mode)
2168  bu_free(bot->face_mode, "bot->face_mode");
2169  bot->face_mode = bu_hex_to_bitv(argv[1]);
2170  } else {
2171  li = atol(&(argv[0][2]));
2172  if (li < 0 || (size_t)li >= bot->num_faces) {
2173  bu_vls_printf(logstr, "face number [%ld] out of range (0..%zu)", li, bot->num_faces-1);
2174  Tcl_DecrRefCount(obj);
2175  return BRLCAD_ERROR;
2176  }
2177 
2178  if (isdigit((int)*argv[1])) {
2179  if (atol(argv[1]) == 0)
2180  BU_BITCLR(bot->face_mode, li);
2181  else
2182  BU_BITSET(bot->face_mode, li);
2183  } else if (BU_STR_EQUAL(argv[1], "append"))
2184  BU_BITSET(bot->face_mode, li);
2185  else
2186  BU_BITCLR(bot->face_mode, li);
2187  }
2188  } else if (BU_STR_EQUAL(argv[0], "nn")) {
2189  long new_num = 0;
2190  size_t old_num = bot->num_normals;
2191 
2192  new_num = atol(Tcl_GetStringFromObj(obj, NULL));
2193  if (new_num < 0) {
2194  bu_vls_printf(logstr, "Number of normals [%ld] may not be less than 0", new_num);
2195  Tcl_DecrRefCount(obj);
2196  return BRLCAD_ERROR;
2197  }
2198 
2199  if (new_num == 0) {
2200  bot->num_normals = 0;
2201  if (bot->normals) {
2202  bu_free(bot->normals, "BOT normals");
2203  bot->normals = (fastf_t *)NULL;
2204  }
2205  bot->num_normals = 0;
2206  } else {
2207  if ((size_t)new_num != old_num) {
2208  bot->num_normals = (size_t)new_num;
2209  if (bot->normals) {
2210  bot->normals = (fastf_t *)bu_realloc((char *)bot->normals, bot->num_normals * 3 * sizeof(fastf_t), "BOT normals");
2211  } else {
2212  bot->normals = (fastf_t *)bu_calloc(bot->num_normals * 3, sizeof(fastf_t), "BOT normals");
2213  }
2214 
2215  if ((size_t)new_num > old_num) {
2216  for (i = old_num; i < (size_t)new_num; i++) {
2217  VSET(&bot->normals[i*3], 0, 0, 0);
2218  }
2219  }
2220  }
2221 
2222  }
2223 
2224  } else if (!bu_strncmp(argv[0], "fn", 2)) {
2225  char *f_str;
2226 
2227  if (argv[0][2] == '\0') {
2228  (void)Tcl_ListObjGetElements(brlcad_interp, obj, &len, &obj_array);
2229  if ((size_t)len != bot->num_faces || len <= 0) {
2230  bu_vls_printf(logstr, "Only %d face normals? Must provide normals for all faces!!!", len);
2231  Tcl_DecrRefCount(obj);
2232  return BRLCAD_ERROR;
2233  }
2234  if (bot->face_normals)
2235  bu_free(bot->face_normals, "BOT face_normals");
2236  bot->face_normals = (int *)bu_calloc(len*3, sizeof(int), "BOT face_normals");
2237  bot->num_face_normals = len;
2238  for (i = 0; i < (size_t)len; i++) {
2239  f_str = Tcl_GetStringFromObj(obj_array[i], NULL);
2240  while (isspace((int)*f_str)) f_str++;
2241 
2242  if (*f_str == '\0') {
2243  bu_vls_printf(logstr, "incomplete list of face_normals");
2244  Tcl_DecrRefCount(obj);
2245  return BRLCAD_ERROR;
2246  }
2247 
2248  /* normal [X, y, z] */
2249  li = atol(f_str);
2250  if (li < 0) {
2251  bu_vls_printf(logstr, "invalid face normal index [%ld]", li);
2252  Tcl_DecrRefCount(obj);
2253  return BRLCAD_ERROR;
2254  }
2255  bot->face_normals[i*3+0] = (size_t)li;
2256 
2257  f_str = bu_next_token(f_str);
2258  if (*f_str == '\0') {
2259  bu_vls_printf(logstr, "incomplete list of face_normals");
2260  Tcl_DecrRefCount(obj);
2261  return BRLCAD_ERROR;
2262  }
2263 
2264  /* normal [x, Y, z] */
2265  li = atol(f_str);
2266  if (li < 0) {
2267  bu_vls_printf(logstr, "invalid face normal index [%ld]", li);
2268  Tcl_DecrRefCount(obj);
2269  return BRLCAD_ERROR;
2270  }
2271 
2272  bot->face_normals[i*3+1] = li;
2273  f_str = bu_next_token(f_str);
2274  if (*f_str == '\0') {
2275  bu_vls_printf(logstr, "incomplete list of face_normals");
2276  Tcl_DecrRefCount(obj);
2277  return BRLCAD_ERROR;
2278  }
2279 
2280  /* normal [x, y, Z] */
2281  li = atol(f_str);
2282  if (li < 0) {
2283  bu_vls_printf(logstr, "invalid face normal index [%ld]", li);
2284  Tcl_DecrRefCount(obj);
2285  return BRLCAD_ERROR;
2286  }
2287  bot->face_normals[i*3+2] = li;
2288  }
2289  bot->bot_flags |= RT_BOT_HAS_SURFACE_NORMALS;
2290  } else {
2291  li = atol(&argv[0][2]);
2292  if (li < 0 || (size_t)li >= bot->num_faces) {
2293  bu_vls_printf(logstr, "face_normal number [%ld] out of range!!!", li);
2294  Tcl_DecrRefCount(obj);
2295  return BRLCAD_ERROR;
2296  }
2297  i = (size_t)li;
2298  f_str = Tcl_GetStringFromObj(obj, NULL);
2299  while (isspace((int)*f_str)) f_str++;
2300 
2301  li = atol(f_str);
2302  if (li < 0) {
2303  bu_vls_printf(logstr, "invalid face normal index [%ld]", li);
2304  Tcl_DecrRefCount(obj);
2305  return BRLCAD_ERROR;
2306  }
2307  bot->face_normals[i*3+0] = li;
2308  f_str = bu_next_token(f_str);
2309  if (*f_str == '\0') {
2310  bu_vls_printf(logstr, "incomplete vertex");
2311  Tcl_DecrRefCount(obj);
2312  return BRLCAD_ERROR;
2313  }
2314 
2315  li = atol(f_str);
2316  if (li < 0) {
2317  bu_vls_printf(logstr, "invalid face normal index [%ld]", li);
2318  Tcl_DecrRefCount(obj);
2319  return BRLCAD_ERROR;
2320  }
2321  bot->face_normals[i*3+1] = li;
2322  f_str = bu_next_token(f_str);
2323  if (*f_str == '\0') {
2324  bu_vls_printf(logstr, "incomplete vertex");
2325  Tcl_DecrRefCount(obj);
2326  return BRLCAD_ERROR;
2327  }
2328 
2329  li = atol(f_str);
2330  if (li < 0) {
2331  bu_vls_printf(logstr, "invalid face normal index [%ld]", li);
2332  Tcl_DecrRefCount(obj);
2333  return BRLCAD_ERROR;
2334  }
2335  bot->face_normals[i*3+2] = li;
2336  }
2337  } else if (argv[0][0] == 'N') {
2338  char *v_str;
2339 
2340  if (argv[0][1] == '\0') {
2341  (void)Tcl_ListObjGetElements(brlcad_interp, obj, &len, &obj_array);
2342  if (len <= 0) {
2343  bu_vls_printf(logstr, "Must provide at least one normal!!!");
2344  Tcl_DecrRefCount(obj);
2345  return BRLCAD_ERROR;
2346  }
2347  bot->num_normals = len;
2348  if (bot->normals) {
2349  bu_free(bot->normals, "BOT normals");
2350  bot->normals = (fastf_t *)NULL;
2351  }
2352  bot->num_normals = 0;
2353  bot->normals = (fastf_t *)bu_calloc(len*3, sizeof(fastf_t), "BOT normals");
2354  for (i = 0; i < (size_t)len; i++) {
2355  v_str = Tcl_GetStringFromObj(obj_array[i], NULL);
2356  while (isspace((int)*v_str)) v_str++;
2357  if (*v_str == '\0') {
2358  bu_vls_printf(logstr, "incomplete list of normals");
2359  Tcl_DecrRefCount(obj);
2360  return BRLCAD_ERROR;
2361  }
2362  bot->normals[i*3+0] = atof(v_str);
2363  v_str = bu_next_token(v_str);
2364  if (*v_str == '\0') {
2365  bu_vls_printf(logstr, "incomplete list of normals");
2366  Tcl_DecrRefCount(obj);
2367  return BRLCAD_ERROR;
2368  }
2369  bot->normals[i*3+1] = atof(v_str);
2370  v_str = bu_next_token(v_str);
2371  if (*v_str == '\0') {
2372  bu_vls_printf(logstr, "incomplete list of normals");
2373  Tcl_DecrRefCount(obj);
2374  return BRLCAD_ERROR;
2375  }
2376  bot->normals[i*3+2] = atof(v_str);
2377  }
2378  bot->bot_flags |= RT_BOT_HAS_SURFACE_NORMALS;
2379  } else {
2380  li = atol(&argv[0][1]);
2381  if (li < 0 || (size_t)li >= bot->num_normals) {
2382  bu_vls_printf(logstr, "normal number [%ld] out of range!!!", li);
2383  Tcl_DecrRefCount(obj);
2384  return BRLCAD_ERROR;
2385  }
2386  i = (size_t)li;
2387  v_str = Tcl_GetStringFromObj(obj, NULL);
2388  while (isspace((int)*v_str)) v_str++;
2389 
2390  bot->normals[i*3+0] = atof(v_str);
2391  v_str = bu_next_token(v_str);
2392  if (*v_str == '\0') {
2393  bu_vls_printf(logstr, "incomplete normal");
2394  Tcl_DecrRefCount(obj);
2395  return BRLCAD_ERROR;
2396  }
2397  bot->normals[i*3+1] = atof(v_str);
2398  v_str = bu_next_token(v_str);
2399  if (*v_str == '\0') {
2400  bu_vls_printf(logstr, "incomplete normal");
2401  Tcl_DecrRefCount(obj);
2402  return BRLCAD_ERROR;
2403  }
2404  bot->normals[i*3+2] = atof(v_str);
2405  }
2406  } else if (argv[0][0] == 'V') {
2407  char *v_str;
2408 
2409  if (argv[0][1] == '\0') {
2410  (void)Tcl_ListObjGetElements(brlcad_interp, obj, &len, &obj_array);
2411  if (len <= 0) {
2412  bu_vls_printf(logstr, "Must provide at least one vertex!!!");
2413  Tcl_DecrRefCount(obj);
2414  return BRLCAD_ERROR;
2415  }
2416  bot->num_vertices = len;
2417  if (bot->vertices)
2418  bu_free(bot->vertices, "BOT vertices");
2419  bot->vertices = (fastf_t *)bu_calloc(len*3, sizeof(fastf_t), "BOT vertices");
2420  for (i = 0; i < (size_t)len; i++) {
2421  v_str = Tcl_GetStringFromObj(obj_array[i], NULL);
2422  while (isspace((int)*v_str)) v_str++;
2423  if (*v_str == '\0') {
2424  bu_vls_printf(logstr, "incomplete list of vertices");
2425  Tcl_DecrRefCount(obj);
2426  return BRLCAD_ERROR;
2427  }
2428  bot->vertices[i*3+0] = atof(v_str);
2429  v_str = bu_next_token(v_str);
2430  if (*v_str == '\0') {
2431  bu_vls_printf(logstr, "incomplete list of vertices");
2432  Tcl_DecrRefCount(obj);
2433  return BRLCAD_ERROR;
2434  }
2435  bot->vertices[i*3+1] = atof(v_str);
2436  v_str = bu_next_token(v_str);
2437  if (*v_str == '\0') {
2438  bu_vls_printf(logstr, "incomplete list of vertices");
2439  Tcl_DecrRefCount(obj);
2440  return BRLCAD_ERROR;
2441  }
2442  bot->vertices[i*3+2] = atof(v_str);
2443  }
2444  } else {
2445  li = atol(&argv[0][1]);
2446  if (li < 0 || (size_t)li >= bot->num_vertices) {
2447  bu_vls_printf(logstr, "vertex number [%ld] out of range!!!", li);
2448  Tcl_DecrRefCount(obj);
2449  return BRLCAD_ERROR;
2450  }
2451  i = (size_t)li;
2452  v_str = Tcl_GetStringFromObj(obj, NULL);
2453  while (isspace((int)*v_str)) v_str++;
2454 
2455  bot->vertices[i*3+0] = atof(v_str);
2456  v_str = bu_next_token(v_str);
2457  if (*v_str == '\0') {
2458  bu_vls_printf(logstr, "incomplete vertex");
2459  Tcl_DecrRefCount(obj);
2460  return BRLCAD_ERROR;
2461  }
2462  bot->vertices[i*3+1] = atof(v_str);
2463  v_str = bu_next_token(v_str);
2464  if (*v_str == '\0') {
2465  bu_vls_printf(logstr, "incomplete vertex");
2466  Tcl_DecrRefCount(obj);
2467  return BRLCAD_ERROR;
2468  }
2469  bot->vertices[i*3+2] = atof(v_str);
2470  }
2471  } else if (argv[0][0] == 'F') {
2472  char *f_str;
2473 
2474  if (argv[0][1] == '\0') {
2475  (void)Tcl_ListObjGetElements(brlcad_interp, obj, &len, &obj_array);
2476  if (len <= 0) {
2477  bu_vls_printf(logstr, "Must provide at least one face!!!");
2478  Tcl_DecrRefCount(obj);
2479  return BRLCAD_ERROR;
2480  }
2481  bot->num_faces = len;
2482  if (bot->faces)
2483  bu_free(bot->faces, "BOT faces");
2484  bot->faces = (int *)bu_calloc(len*3, sizeof(int), "BOT faces");
2485  if (bot->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) {
2486  if (!bot->face_normals) {
2487  bot->face_normals = (int *)bu_malloc(bot->num_faces * 3 * sizeof(int), "bot->face_normals");
2488  bot->num_face_normals = bot->num_faces;
2489  for (i = 0; i < bot->num_face_normals; i++) {
2490  VSETALL(&bot->face_normals[i*3], -1);
2491  }
2492  } else if (bot->num_face_normals < bot->num_faces) {
2493  bot->face_normals = (int *)bu_realloc(bot->face_normals, bot->num_faces * 3 * sizeof(int), "bot->face_normals");
2494  for (i = bot->num_face_normals; i < bot->num_faces; i++) {
2495  VSETALL(&bot->face_normals[i*3], -1);
2496  }
2497  bot->num_face_normals = bot->num_faces;
2498  }
2499  }
2500  for (i = 0; i < (size_t)len; i++) {
2501  f_str = Tcl_GetStringFromObj(obj_array[i], NULL);
2502  while (isspace((int)*f_str)) f_str++;
2503 
2504  if (*f_str == '\0') {
2505  bu_vls_printf(logstr, "incomplete list of faces");
2506  Tcl_DecrRefCount(obj);
2507  return BRLCAD_ERROR;
2508  }
2509 
2510  li = atol(f_str);
2511  if (li < 0) {
2512  bu_vls_printf(logstr, "invalid face index [%ld]", li);
2513  Tcl_DecrRefCount(obj);
2514  return BRLCAD_ERROR;
2515  }
2516  bot->faces[i*3+0] = li;
2517 
2518  f_str = bu_next_token(f_str);
2519  if (*f_str == '\0') {
2520  bu_vls_printf(logstr, "incomplete list of faces");
2521  Tcl_DecrRefCount(obj);
2522  return BRLCAD_ERROR;
2523  }
2524 
2525  li = atol(f_str);
2526  if (li < 0) {
2527  bu_vls_printf(logstr, "invalid face index [%ld]", li);
2528  Tcl_DecrRefCount(obj);
2529  return BRLCAD_ERROR;
2530  }
2531  bot->faces[i*3+1] = li;
2532 
2533  f_str = bu_next_token(f_str);
2534  if (*f_str == '\0') {
2535  bu_vls_printf(logstr, "incomplete list of faces");
2536  Tcl_DecrRefCount(obj);
2537  return BRLCAD_ERROR;
2538  }
2539 
2540  li = atol(f_str);
2541  if (li < 0) {
2542  bu_vls_printf(logstr, "invalid face index [%ld]", li);
2543  Tcl_DecrRefCount(obj);
2544  return BRLCAD_ERROR;
2545  }
2546  bot->faces[i*3+2] = li;
2547  }
2548  } else {
2549  li = atol(&argv[0][1]);
2550  if (li < 0 || (size_t)li >= bot->num_faces) {
2551  bu_vls_printf(logstr, "face number [%ld] out of range!!!", li);
2552  Tcl_DecrRefCount(obj);
2553  return BRLCAD_ERROR;
2554  }
2555  i = (size_t)li;
2556  f_str = Tcl_GetStringFromObj(obj, NULL);
2557  while (isspace((int)*f_str)) f_str++;
2558 
2559  li = atol(f_str);
2560  if (li < 0) {
2561  bu_vls_printf(logstr, "invalid face index [%ld]", li);
2562  Tcl_DecrRefCount(obj);
2563  return BRLCAD_ERROR;
2564  }
2565  bot->faces[i*3+0] = li;
2566 
2567  f_str = bu_next_token(f_str);
2568  if (*f_str == '\0') {
2569  bu_vls_printf(logstr, "incomplete vertex");
2570  Tcl_DecrRefCount(obj);
2571  return BRLCAD_ERROR;
2572  }
2573 
2574  li = atol(f_str);
2575  if (li < 0) {
2576  bu_vls_printf(logstr, "invalid face index [%ld]", li);
2577  Tcl_DecrRefCount(obj);
2578  return BRLCAD_ERROR;
2579  }
2580  bot->faces[i*3+1] = li;
2581  f_str = bu_next_token(f_str);
2582  if (*f_str == '\0') {
2583  bu_vls_printf(logstr, "incomplete vertex");
2584  Tcl_DecrRefCount(obj);
2585  return BRLCAD_ERROR;
2586  }
2587 
2588  li = atol(f_str);
2589  if (li < 0) {
2590  bu_vls_printf(logstr, "invalid face index [%ld]", li);
2591  Tcl_DecrRefCount(obj);
2592  return BRLCAD_ERROR;
2593  }
2594  bot->faces[i*3+2] = li;
2595  }
2596  bot_check_vertex_indices(logstr, bot);
2597  } else if (argv[0][0] == 'T') {
2598  char *t_str;
2599 
2600  if (argv[0][1] == '\0') {
2601  (void)Tcl_ListObjGetElements(brlcad_interp, obj, &len, &obj_array);
2602  if (len <= 0) {
2603  bu_vls_printf(logstr, "Must provide at least one thickness!!!");
2604  Tcl_DecrRefCount(obj);
2605  return BRLCAD_ERROR;
2606  }
2607  if ((size_t)len > bot->num_faces) {
2608  bu_vls_printf(logstr, "Too many thicknesses (there are not that many faces)!!!");
2609  Tcl_DecrRefCount(obj);
2610  return BRLCAD_ERROR;
2611  }
2612  if (!bot->thickness) {
2613  bot->thickness = (fastf_t *)bu_calloc(bot->num_faces, sizeof(fastf_t),
2614  "bot->thickness");
2615  }
2616  for (i = 0; i < (size_t)len; i++) {
2617  bot->thickness[i] = atof(Tcl_GetStringFromObj(obj_array[i], NULL));
2618  }
2619  } else {
2620  li = atol(&argv[0][1]);
2621  if (li < 0 || (size_t)li >= bot->num_faces) {
2622  bu_vls_printf(logstr, "face number [%ld] out of range!!!", li);
2623  Tcl_DecrRefCount(obj);
2624  return BRLCAD_ERROR;
2625  }
2626  if (!bot->thickness) {
2627  bot->thickness = (fastf_t *)bu_calloc(bot->num_faces, sizeof(fastf_t),
2628  "bot->thickness");
2629  }
2630  t_str = Tcl_GetStringFromObj(obj, NULL);
2631  bot->thickness[li] = atof(t_str);
2632  }
2633  } else if (BU_STR_EQUAL(argv[0], "mode")) {
2634  char *m_str;
2635 
2636  m_str = Tcl_GetStringFromObj(obj, NULL);
2637  if (isdigit((int)*m_str)) {
2638  int mode;
2639 
2640  mode = atoi(m_str);
2641  if (mode < RT_BOT_SURFACE || mode > RT_BOT_PLATE_NOCOS) {
2642  bu_vls_printf(logstr, "unrecognized mode!!!");
2643  Tcl_DecrRefCount(obj);
2644  return BRLCAD_ERROR;
2645  }
2646  bot->mode = mode;
2647  } else {
2648  if (!bu_strncmp(m_str, modes[RT_BOT_SURFACE], 4))
2649  bot->mode = RT_BOT_SURFACE;
2650  else if (BU_STR_EQUAL(m_str, modes[RT_BOT_SOLID]))
2651  bot->mode = RT_BOT_SOLID;
2652  else if (BU_STR_EQUAL(m_str, modes[RT_BOT_PLATE]))
2653  bot->mode = RT_BOT_PLATE;
2654  else if (BU_STR_EQUAL(m_str, modes[RT_BOT_PLATE_NOCOS]))
2655  bot->mode = RT_BOT_PLATE_NOCOS;
2656  else {
2657  bu_vls_printf(logstr, "unrecognized mode!!!");
2658  Tcl_DecrRefCount(obj);
2659  return BRLCAD_ERROR;
2660  }
2661  }
2662  } else if (!bu_strncmp(argv[0], "orient", 6)) {
2663  char *o_str;
2664 
2665  o_str = Tcl_GetStringFromObj(obj, NULL);
2666  if (isdigit((int)*o_str)) {
2667  int orient;
2668 
2669  orient = atoi(o_str);
2670  if (orient < RT_BOT_UNORIENTED || orient > RT_BOT_CW) {
2671  bu_vls_printf(logstr, "unrecognized orientation!!!");
2672  Tcl_DecrRefCount(obj);
2673  return BRLCAD_ERROR;
2674  }
2675  bot->orientation = orient;
2676  } else {
2677  if (BU_STR_EQUAL(o_str, orientation[RT_BOT_UNORIENTED]))
2678  bot->orientation = RT_BOT_UNORIENTED;
2679  else if (BU_STR_EQUAL(o_str, orientation[RT_BOT_CCW]))
2680  bot->orientation = RT_BOT_CCW;
2681  else if (BU_STR_EQUAL(o_str, orientation[RT_BOT_CW]))
2682  bot->orientation = RT_BOT_CW;
2683  else {
2684  bu_vls_printf(logstr, "unrecognized orientation!!!");
2685  Tcl_DecrRefCount(obj);
2686  return BRLCAD_ERROR;
2687  }
2688  }
2689  } else if (BU_STR_EQUAL(argv[0], "flags")) {
2690  (void)Tcl_ListObjGetElements(brlcad_interp, obj, &len, &obj_array);
2691  bot->bot_flags = 0;
2692  for (i = 0; i < (size_t)len; i++) {
2693  char *str;
2694 
2695  str = Tcl_GetStringFromObj(obj_array[i], NULL);
2696  if (BU_STR_EQUAL(str, "has_normals")) {
2697  bot->bot_flags |= RT_BOT_HAS_SURFACE_NORMALS;
2698  } else if (BU_STR_EQUAL(str, "use_normals")) {
2699  bot->bot_flags |= RT_BOT_USE_NORMALS;
2700  } else if (BU_STR_EQUAL(str, "use_floats")) {
2701  bot->bot_flags |= RT_BOT_USE_FLOATS;
2702  } else {
2703  bu_vls_printf(logstr, "unrecognized flag (must be \"has_normals\", \"use_normals\", or \"use_floats\"!!!");
2704  Tcl_DecrRefCount(obj);
2705  return BRLCAD_ERROR;
2706  }
2707  }
2708  }
2709 
2710  Tcl_DecrRefCount(obj);
2711 
2712  argc -= 2;
2713  argv += 2;
2714  }
2715 
2716  if (bot->mode == RT_BOT_PLATE || bot->mode == RT_BOT_PLATE_NOCOS) {
2717  if (!bot->thickness)
2718  bot->thickness = (fastf_t *)bu_calloc(bot->num_faces, sizeof(fastf_t), "BOT thickness");
2719  if (!bot->face_mode) {
2720  bot->face_mode = bu_bitv_new(bot->num_faces);
2721  }
2722  } else {
2723  if (bot->thickness) {
2724  bu_free(bot->thickness, "BOT thickness");
2725  bot->thickness = (fastf_t *)NULL;
2726  }
2727  if (bot->face_mode) {
2728  bu_free(bot->face_mode, "BOT facemode");
2729  bot->face_mode = (struct bu_bitv *)NULL;
2730  }
2731  }
2732 
2733  return BRLCAD_OK;
2734 }
2735 
2736 
2737 int
2738 rt_bot_form(struct bu_vls *logstr, const struct rt_functab *ftp)
2739 {
2740  RT_CK_FUNCTAB(ftp);
2741 
2742  bu_vls_printf(logstr,
2743  "mode {%%s} orient {%%s} V { {%%f %%f %%f} {%%f %%f %%f} ...} F { {%%lu %%lu %%lu} {%%lu %%lu %%lu} ...} T { %%f %%f %%f ... } fm %%s");
2744 
2745  return BRLCAD_OK;
2746 }
2747 
2748 
2749 int
2750 rt_bot_params(struct pc_pc_set *ps, const struct rt_db_internal *ip)
2751 {
2752  if (!ps) return 0;
2753  RT_CK_DB_INTERNAL(ip);
2754 
2755  return 0; /* OK */
2756 }
2757 
2758 
2759 /*************************************************************************
2760  *
2761  * BoT support routines used by MGED, converters, etc.
2762  *
2763  *************************************************************************/
2764 
2765 struct bot_edge {
2766  int v;
2767  size_t use_count;
2768  struct bot_edge *next;
2769 };
2770 
2771 
2772 /* Builds a table of all unique edges in bot, storing the result in edges.
2773  * Returns number of edges.
2774  *
2775  * Edge i to j (i < j) is represented as the bot_edge struct with v = j,
2776  * stored in the list headed by (struct bot_edge*) edges[i].
2777  */
2778 int
2779 buildEdgeTable(struct rt_bot_internal *bot, struct bot_edge ***edges)
2780 {
2781  size_t tmp, flen, currFace;
2782  int currVert, nextVert, from, to;
2783  size_t numVertices, numEdges = 0;
2784  int *faces;
2785  struct bot_edge *edge;
2786 
2787  RT_BOT_CK_MAGIC(bot);
2788 
2789  numVertices = bot->num_vertices;
2790  faces = bot->faces;
2791 
2792  /* allocate array with one index per vertex */
2793  *edges = (struct bot_edge**)bu_calloc(numVertices, sizeof(struct bot_edge*), "edges");
2794 
2795  /* for each face */
2796  flen = bot->num_faces * 3;
2797  for (currFace = 0; currFace < flen; currFace += 3) {
2798 
2799  for (currVert = 0; currVert < 3; currVert++) {
2800 
2801  /* curr and next vertex form an edge of curr face */
2802 
2803  /* get relative indices */
2804  nextVert = currVert + 1;
2805 
2806  if (nextVert > 2) {
2807  nextVert = 0;
2808  }
2809 
2810  /* get actual indices */
2811  from = faces[currFace + currVert];
2812  to = faces[currFace + nextVert];
2813 
2814  /* make sure 'from' is the lower index */
2815  if (to < from) {
2816  tmp = from;
2817  from = to;
2818  to = tmp;
2819  }
2820 
2821  /* get the list for this index */
2822  edge = (*edges)[from];
2823 
2824  /* make new list */
2825  if (edge == (struct bot_edge*)NULL) {
2826 
2827  BU_ALLOC(edge, struct bot_edge);
2828  (*edges)[from] = edge;
2829  }
2830 
2831  /* list already exists */
2832  else {
2833 
2834  /* look for existing entry */
2835  while (edge->next && edge->v != to) {
2836  edge = edge->next;
2837  }
2838 
2839  /* this edge found previously - update use count */
2840  if (edge->v == to) {
2841 
2842  edge->use_count++;
2843  continue;
2844  }
2845 
2846  /* this edge is new - append a new entry for it */
2847  BU_ALLOC(edge->next, struct bot_edge);
2848  edge = edge->next;
2849  }
2850 
2851  /* initialize new entry */
2852  edge->v = to;
2853  edge->use_count = 1;
2854  edge->next = (struct bot_edge*)NULL;
2855 
2856  numEdges++;
2857 
2858  } /* indices loop */
2859  } /* faces loop */
2860 
2861  return numEdges;
2862 }
2863 
2864 
2865 /**
2866  * Routine for finding the smallest edge length in a BoT.
2867  */
2868 float
2869 minEdge(struct rt_bot_internal *bot)
2870 {
2871  size_t i;
2872  size_t numVerts;
2873  fastf_t epsilon = 1e-10;
2874  fastf_t *vertices;
2875  fastf_t currMag, minMag = MAX_FASTF;
2876  struct bot_edge *edge, *tmp;
2877  struct bot_edge **edges = NULL;
2878  vect_t start, curr;
2879 
2880  RT_BOT_CK_MAGIC(bot);
2881 
2882  numVerts = bot->num_vertices;
2883  vertices = bot->vertices;
2884 
2885  /* build edge list */
2886  buildEdgeTable(bot, &edges);
2887 
2888  /* for each vertex */
2889  for (i = 0; i < numVerts; i++) {
2890 
2891  edge = edges[i];
2892 
2893  /* make sure this list exists */
2894  if (edge == (struct bot_edge*)NULL) {
2895  continue;
2896  }
2897 
2898  /* starting vertex for these edges */
2899  VMOVE(start, &vertices[i]);
2900 
2901  /* for each edge beginning with this index */
2902  while (edge != (struct bot_edge*)NULL) {
2903 
2904  /* calculate edge vector using current end vertex */
2905  VSUB2(curr, start, &vertices[edge->v]);
2906 
2907  /* see if it has the smallest magnitude so far */
2908  currMag = MAGSQ(curr);
2909 
2910  if (currMag < minMag && currMag > epsilon) {
2911  minMag = currMag;
2912  }
2913 
2914  edge = edge->next;
2915  }
2916  }
2917 
2918  /* free table memory */
2919  for (i = 0; i < numVerts; i++) {
2920 
2921  edge = edges[i];
2922 
2923  while (edge != (struct bot_edge*)NULL) {
2924  tmp = edge;
2925  edge = edge->next;
2926  bu_free(tmp, "struct bot_edge");
2927  }
2928  }
2929  bu_free(edges, "bot edge table");
2930  edges = NULL;
2931 
2932  return sqrt(minMag);
2933 }
2934 
2935 
2936 /**
2937  * Routine for finding the largest edge length in a BoT.
2938  */
2939 float
2940 maxEdge(struct rt_bot_internal *bot)
2941 {
2942  size_t i;
2943  size_t numVerts;
2944  fastf_t *vertices;
2945  fastf_t currMag, maxMag = 0.0;
2946  struct bot_edge *edge, *tmp;
2947  struct bot_edge **edges = NULL;
2948  vect_t start, curr;
2949 
2950  RT_BOT_CK_MAGIC(bot);
2951 
2952  numVerts = bot->num_vertices;
2953  vertices = bot->vertices;
2954 
2955  /* build edge list */
2956  buildEdgeTable(bot, &edges);
2957 
2958  /* for each vertex */
2959  for (i = 0; i < numVerts; i++) {
2960 
2961  edge = edges[i];
2962 
2963  /* make sure this list exists */
2964  if (edge == (struct bot_edge*)NULL) {
2965  continue;
2966  }
2967 
2968  /* starting vertex for these edges */
2969  VMOVE(start, &vertices[i]);
2970 
2971  /* for each edge beginning with this index */
2972  while (edge != (struct bot_edge*)NULL) {
2973 
2974  /* calculate edge vector using current end vertex */
2975  VSUB2(curr, start, &vertices[edge->v]);
2976 
2977  /* see if it has the largest magnitude so far */
2978  currMag = MAGSQ(curr);
2979 
2980  if (currMag > maxMag) {
2981  maxMag = currMag;
2982  }
2983 
2984  edge = edge->next;
2985  }
2986  }
2987 
2988  /* free table memory */
2989  for (i = 0; i < numVerts; i++) {
2990 
2991  edge = edges[i];
2992 
2993  while (edge != (struct bot_edge*)NULL) {
2994  tmp = edge;
2995  edge = edge->next;
2996  bu_free(tmp, "struct bot_edge");
2997  }
2998  }
2999  bu_free(edges, "bot edge table");
3000  edges = NULL;
3001 
3002  return sqrt(maxMag);
3003 }
3004 
3005 
3006 /**
3007  * RT_BOT_PROPGET
3008  *
3009  * Command used to query BoT property values. Returns parseable
3010  * values rather than formatted strings.
3011  *
3012  * Returns -1 on error.
3013  */
3014 fastf_t
3015 rt_bot_propget(struct rt_bot_internal *bot, const char *property)
3016 {
3017  size_t len;
3018 
3019  RT_BOT_CK_MAGIC(bot);
3020 
3021  len = strlen(property);
3022 
3023  /* return value of requested property */
3024  if (bu_strncmp(property, "faces", len) == 0) {
3025  return bot->num_faces;
3026  }
3027  else if (bu_strncmp(property, "orientation", len) == 0) {
3028  return bot->orientation;
3029  }
3030  else if (bu_strncmp(property, "type", len) == 0 ||
3031  bu_strncmp(property, "mode", len) == 0)
3032  {
3033  return bot->mode;
3034  }
3035  else if (bu_strncmp(property, "vertices", len) == 0) {
3036  return bot->num_vertices;
3037  }
3038  else if (bu_strncmp(property, "minEdge", len) == 0 ||
3039  bu_strncmp(property, "minedge", len) == 0)
3040  {
3041  return minEdge(bot);
3042  }
3043  else if (bu_strncmp(property, "maxEdge", len) == 0 ||
3044  bu_strncmp(property, "maxedge", len) == 0)
3045  {
3046  return maxEdge(bot);
3047  }
3048 
3049  return -1;
3050 }
3051 
3052 
3053 /**
3054  * This routine adjusts the vertex pointers in each face so that
3055  * pointers to duplicate vertices end up pointing to the same vertex.
3056  * The unused vertices are removed and the resulting bot is condensed.
3057  * Returns the number of vertices fused.
3058  */
3059 int
3060 rt_bot_vertex_fuse(struct rt_bot_internal *bot, const struct bn_tol *tol)
3061 {
3062 #if 1
3063  /* THE OLD WAY .. possibly O(n^3) with the vertex shifting */
3064 
3065  size_t i, j, k;
3066  size_t count = 0;
3067 
3068  RT_BOT_CK_MAGIC(bot);
3069 
3070  for (i = 0; i < bot->num_vertices; i++) {
3071  j = i + 1;
3072  while (j < bot->num_vertices) {
3073  if (bn_pt3_pt3_equal(&bot->vertices[i*3], &bot->vertices[j*3], tol)) {
3074  count++;
3075 
3076  /* update bot */
3077  bot->num_vertices--;
3078 
3079  /* shift vertices down */
3080  for (k = j; k < bot->num_vertices; k++)
3081  VMOVE(&bot->vertices[k*3], &bot->vertices[(k+1)*3]);
3082 
3083  /* update face references */
3084  for (k = 0; k < bot->num_faces*3; k++) {
3085  if ((size_t)bot->faces[k] == j) {
3086  bot->faces[k] = i;
3087  } else if ((size_t)bot->faces[k] > j)
3088  bot->faces[k]--;
3089  }
3090  } else {
3091  j++;
3092  }
3093  }
3094  }
3095 #else
3096 
3097  /* THE NEW WAY .. possibly O(n) with basic bin sorting */
3098 
3099  size_t i, j, k;
3100  size_t count = 0;
3101 
3102  long slot;
3103  size_t total = 0;
3104  long *bin[256];
3105  size_t bin_capacity[256];
3106  size_t bin_todonext[256];
3107  const int DEFAULT_CAPACITY = 32;
3108  fastf_t min_xval = (fastf_t)LONG_MAX;
3109  fastf_t max_xval = (fastf_t)LONG_MIN;
3110  fastf_t delta = (fastf_t)0.0;
3111 
3112  vect_t deleted;
3113  VSETALL(deleted, INFINITY);
3114 
3115  RT_BOT_CK_MAGIC(bot);
3116 
3117  /* initialize a simple 256-slot integer bin space partitioning */
3118  for (slot = 0; slot < 256; slot++) {
3119  bin_todonext[slot] = 0;
3120  bin_capacity[slot] = DEFAULT_CAPACITY;
3121  bin[slot] = bu_calloc(DEFAULT_CAPACITY, sizeof(long *), "vertices bin");
3122  }
3123 
3124  /* first pass to get the range of vertex values */
3125  for (i = 0; i < bot->num_vertices; i++) {
3126  /* bins are assigned based on X value */
3127  if ((&bot->vertices[i*3])[X] < min_xval)
3128  min_xval = (&bot->vertices[i*3])[X];
3129  if ((&bot->vertices[i*3])[X] > max_xval)
3130  max_xval = (&bot->vertices[i*3])[X];
3131 
3132  /* sanity to make sure our book-keeping doesn't go haywire */
3133  if (ZERO((&bot->vertices[i*3])[X] - deleted[X])) {
3134  bu_log("WARNING: Unable to fuse due to vertex with infinite value (idx=%ld)\n", i);
3135  return 0;
3136  }
3137  }
3138  /* sanity swap */
3139  if (min_xval > max_xval) {
3140  fastf_t t;
3141  t = min_xval;
3142  min_xval = max_xval;
3143  max_xval = t;
3144  }
3145  /* range sanity */
3146  if (max_xval > (fastf_t)LONG_MAX) {
3147  max_xval = (fastf_t)LONG_MAX;
3148  }
3149  if (min_xval < (fastf_t)LONG_MIN) {
3150  min_xval = (fastf_t)LONG_MIN;
3151  }
3152  if (ZERO(max_xval - min_xval)) {
3153  if (ZERO(max_xval - (fastf_t)LONG_MAX)) {
3154  max_xval += VDIVIDE_TOL;
3155  } else {
3156  min_xval -= VDIVIDE_TOL;
3157  }
3158  }
3159 
3160  /* calculate the width of a bin */
3161  delta = fabs(max_xval - min_xval) / (fastf_t)256.0;
3162  if (ZERO(delta))
3163  delta = (fastf_t)1.0;
3164 
3165  /* second pass to sort the vertices into bins based on their X value */
3166  for (i = 0; i < bot->num_vertices; i++) {
3167  if ((&bot->vertices[i*3])[X] > (fastf_t)LONG_MAX) {
3168  /* exceeds our range, put in last bin */
3169  slot = 255;
3170  } else if ((&bot->vertices[i*3])[X] < (fastf_t)LONG_MIN) {
3171  /* exceeds our range, put in first bin */
3172  slot = 0;
3173  } else {
3174  /* bins are assigned based on X value */
3175  slot = (long)(((&bot->vertices[i*3])[X] - min_xval) / delta);
3176  }
3177 
3178  /* extra sanity that we don't imagine non-existent bins */
3179  if (slot < 0) {
3180  slot = 0;
3181  } else if (slot > 255) {
3182  slot = 255;
3183  }
3184 
3185  if (bin_todonext[slot] + 1 > bin_capacity[slot]) {
3186 
3187 /* bu_log("increasing %i from capacity %ld given next is %ld\n", slot, bin_capacity[slot], bin_todonext[slot]); */
3188 
3189  BU_ASSERT_LONG(bin_capacity[slot], <, LONG_MAX / 2);
3190 
3191  bin[slot] = bu_realloc(bin[slot], bin_capacity[slot] * 2 * sizeof(int), "increase vertices bin");
3192  bin_capacity[slot] *= 2;
3193 
3194  /* init to zero for sanity */
3195  for (j = bin_todonext[slot]+1; j < bin_capacity[slot]; j++) {
3196  bin[slot][j] = 0;
3197  }
3198  }
3199 
3200 /* bu_log("setting bin[%lu][%lu] = %ld\n", slot, bin_todonext[slot], i); */
3201 
3202  bin[slot][bin_todonext[slot]++] = i;
3203  }
3204 
3205  /* third pass to check the vertices in each bin */
3206  for (slot = 0; slot < 256; slot++) {
3207 
3208  /* iterate over all vertices in this bin */
3209  for (i = 0; i < bin_todonext[slot]; i++) {
3210 
3211  /* compare to the other vertices in this bin */
3212  for (j = i + 1; j < bin_todonext[slot]; j++) {
3213 
3214  /* specifically not using tolerances here (except underlying representation tolerance) */
3215  if (VEQUAL(&bot->vertices[bin[slot][i]*3], &bot->vertices[bin[slot][j]*3])) {
3216  count++;
3217 
3218  /* update face references */
3219  for (k = 0; k < bot->num_faces*3; k++) {
3220  if (bot->faces[k] == bin[slot][j]) {
3221  bot->faces[k] = bin[slot][i];
3222  }
3223  }
3224 
3225  /* wipe out the vertex marking it for cleanup later */
3226  VMOVE(&bot->vertices[bin[slot][j]*3], deleted);
3227  }
3228  }
3229  }
3230  }
3231 
3232  /* clean up and compress */
3233  k = rt_bot_condense(bot);
3234  if (k < count) {
3235  bu_log("WARNING: Condensed fewer vertices than expected (%ld < %ld)\n", k, count);
3236  }
3237 
3238  /* sanity check, there should be no deleted vertices */
3239  for (i = 0; i < bot->num_vertices; i++) {
3240  if (VEQUAL(&bot->vertices[i*3], deleted)) {
3241  bu_bomb("INTERNAL ERROR: encountered unexpected state during vertex fusing\n");
3242  }
3243  }
3244 
3245  /* clear and release the memory for our integer bin space partitioning */
3246  for (slot = 0; slot < 256; slot++) {
3247  total += bin_todonext[slot];
3248 /* bu_log("[%lu]: %ld (of %ld)\n", slot, bin_todonext[slot], bin_capacity[slot]); */
3249  bu_free(bin[slot], "vertices bin");
3250  bin_capacity[slot] = bin_todonext[slot] = 0;
3251  }
3252  memset(bin, 0, 256 * sizeof(long *));
3253 
3254 /* bu_log("sorted %lu of %lu vertices\n", total, bot->num_vertices); */
3255 #endif
3256 
3257  return count;
3258 }
3259 
3260 
3261 int
3262 rt_bot_same_orientation(const int *a, const int *b)
3263 {
3264  int i;
3265 
3266  for (i = 0; i < 3; i++) {
3267  if (a[0] == b[i]) {
3268  i++;
3269  if (i == 3)
3270  i = 0;
3271  if (a[1] == b[i])
3272  return 1;
3273  else
3274  return 0;
3275  }
3276  }
3277 
3278  return 0;
3279 }
3280 
3281 
3282 int
3283 rt_bot_face_fuse(struct rt_bot_internal *bot)
3284 {
3285  size_t num_faces;
3286  size_t i, j, k, l;
3287  int count = 0;
3288 
3289  RT_BOT_CK_MAGIC(bot);
3290 
3291  num_faces = bot->num_faces;
3292  for (i = 0; i < num_faces; i++) {
3293  j = i + 1;
3294 
3295  while (j<num_faces) {
3296  /* each pass through this loop either increments j or
3297  * decrements num_faces
3298  */
3299  int match = 0;
3300  int elim;
3301 
3302  for (k = i * 3; k < (i+1) * 3; k++) {
3303  for (l = j * 3; l < (j+1) * 3; l++) {
3304  if (bot->faces[k] == bot->faces[l]) {
3305  match++;
3306  break;
3307  }
3308  }
3309  }
3310 
3311  if (match != 3) {
3312  j++;
3313  continue;
3314  }
3315 
3316  /* these two faces have the same vertices */
3317  elim = -1;
3318  switch (bot->mode) {
3319  case RT_BOT_PLATE:
3320  case RT_BOT_PLATE_NOCOS:
3321  /* check the face thickness and face mode */
3322  if (!ZERO(bot->thickness[i] - bot->thickness[j]) ||
3323  (BU_BITTEST(bot->face_mode, i)?1:0) != (BU_BITTEST(bot->face_mode, j)?1:0))
3324  break;
3325  case RT_BOT_SOLID:
3326  case RT_BOT_SURFACE:
3327  if (bot->orientation == RT_BOT_UNORIENTED) {
3328  /* faces are identical, so eliminate one */
3329  elim = j;
3330  } else {
3331  /* need to check orientation */
3332  if (rt_bot_same_orientation(&bot->faces[i*3], &bot->faces[j*3]))
3333  elim = j;
3334  }
3335  break;
3336  default:
3337  bu_bomb("bot_face_condense: Unrecognized BOT mode!!!\n");
3338  break;
3339  }
3340 
3341  if (elim == -1) {
3342  j++;
3343  continue;
3344  }
3345 
3346  /* we are eliminating face number "elim" */
3347  for (l = elim; l < num_faces - 1; l++) {
3348  VMOVE(&bot->faces[l*3], &bot->faces[(l+1)*3]);
3349  }
3350 
3351  if (bot->mode == RT_BOT_PLATE || bot->mode == RT_BOT_PLATE_NOCOS) {
3352  for (l = elim; l < num_faces - 1; l++) {
3353  bot->thickness[l] = bot->thickness[l+1];
3354  if (BU_BITTEST(bot->face_mode, l+1))
3355  BU_BITSET(bot->face_mode, l);
3356  else
3357  BU_BITCLR(bot->face_mode, l);
3358  }
3359  }
3360  num_faces--;
3361  }
3362  }
3363 
3364  count = bot->num_faces - num_faces;
3365 
3366  if (count) {
3367  bot->num_faces = num_faces;
3368  bot->faces = (int *)bu_realloc(bot->faces, num_faces*3*sizeof(int), "BOT faces realloc");
3369  if (bot->mode == RT_BOT_PLATE || bot->mode == RT_BOT_PLATE_NOCOS) {
3370  struct bu_bitv *new_mode;
3371 
3372  bot->thickness = (fastf_t *)bu_realloc(bot->thickness, num_faces*sizeof(fastf_t), "BOT thickness realloc");
3373  new_mode = bu_bitv_new(num_faces);
3374  for (l = 0; l < num_faces; l++) {
3375  if (BU_BITTEST(bot->face_mode, l))
3376  BU_BITSET(new_mode, l);
3377  }
3378  if (bot->face_mode)
3379  bu_free(bot->face_mode, "BOT face_mode");
3380  bot->face_mode = new_mode;
3381  }
3382  }
3383 
3384  return count;
3385 }
3386 
3387 
3388 /**
3389  * Get rid of unused vertices
3390  */
3391 int
3392 rt_bot_condense(struct rt_bot_internal *bot)
3393 {
3394  size_t i, j, k;
3395  size_t num_verts;
3396  size_t dead_verts = 0;
3397  int *verts;
3398 
3399  RT_BOT_CK_MAGIC(bot);
3400 
3401  num_verts = bot->num_vertices;
3402  verts = (int *)bu_calloc(num_verts, sizeof(int), "rt_bot_condense: verts");
3403 
3404  /* walk the list of vertices, and mark each one if it is used */
3405 
3406  for (i = 0; i < bot->num_faces*3; i++) {
3407  j = bot->faces[i];
3408  if (j >= num_verts) {
3409  bu_log("Illegal vertex number %zu, should be 0 through %zu\n", j, num_verts-1);
3410  bu_bomb("Illegal vertex number\n");
3411  }
3412  verts[j] = 1;
3413  }
3414 
3415  /* Walk the list of vertices, eliminate each unused vertex by
3416  * copying the rest of the array downwards
3417  */
3418  for (i = 0; i < num_verts-dead_verts; i++) {
3419  while (!verts[i] && i < num_verts-dead_verts) {
3420  dead_verts++;
3421  for (j = i; j < num_verts-dead_verts; j++) {
3422  k = j+1;
3423  VMOVE(&bot->vertices[j*3], &bot->vertices[k*3]);
3424  verts[j] = verts[k];
3425  }
3426  for (j = 0; j < bot->num_faces * 3; j++) {
3427  if ((size_t)bot->faces[j] >= i)
3428  bot->faces[j]--;
3429  }
3430  }
3431  }
3432 
3433  bu_free((char *)verts, "rt_bot_condense: verts");
3434 
3435  if (!dead_verts) return 0;
3436 
3437  /* Reallocate the vertex array (which should free the space we are
3438  * no longer using)
3439  */
3440  bot->num_vertices -= dead_verts;
3441  bot->vertices = (fastf_t *)bu_realloc(bot->vertices, bot->num_vertices*3*sizeof(fastf_t), "rt_bot_condense: realloc vertices");
3442 
3443  return dead_verts;
3444 }
3445 
3446 
3447 int
3448 find_closest_face(fastf_t **centers, int *piece, int *old_faces, size_t num_faces, fastf_t *vertices)
3449 {
3450  pointp_t v0, v1, v2;
3451  point_t center;
3452  size_t i;
3453  fastf_t one_third = 1.0/3.0;
3454  fastf_t min_dist;
3455  size_t min_face=-1;
3456 
3457  if ((*centers) == NULL) {
3458  int count_centers = 0;
3459 
3460  /* need to build the centers array */
3461  (*centers) = (fastf_t *)bu_malloc(num_faces * 3 * sizeof(fastf_t), "center");
3462  for (i = 0; i < num_faces; i++) {
3463  if (old_faces[i*3] == -1) {
3464  continue;
3465  }
3466  count_centers++;
3467  v0 = &vertices[old_faces[i*3+0]*3];
3468  v1 = &vertices[old_faces[i*3+1]*3];
3469  v2 = &vertices[old_faces[i*3+2]*3];
3470  VADD3(center, v0, v1, v2);
3471  VSCALE(&(*centers)[i*3], center, one_third);
3472  }
3473  }
3474 
3475  v0 = &vertices[piece[0]*3];
3476  v1 = &vertices[piece[1]*3];
3477  v2 = &vertices[piece[2]*3];
3478 
3479  VADD3(center, v0, v1, v2);
3480  VSCALE(center, center, one_third);
3481 
3482  min_dist = MAX_FASTF;
3483 
3484  for (i = 0; i < num_faces; i++) {
3485  vect_t diff;
3486  fastf_t dist;
3487 
3488  if (old_faces[i*3] == -1) {
3489  continue;
3490  }
3491 
3492  VSUB2(diff, center, &(*centers)[i*3]);
3493  dist = MAGSQ(diff);
3494  if (dist < min_dist) {
3495  min_dist = dist;
3496  min_face = i;
3497  }
3498  }
3499 
3500  return min_face;
3501 }
3502 
3503 
3504 void
3505 Add_unique_verts(int *piece_verts, int *v)
3506 {
3507  int i, j;
3508  int *ptr=v;
3509 
3510  for (j = 0; j < 3; j++) {
3511  i = -1;
3512  while (piece_verts[++i] != -1) {
3513  if (piece_verts[i] == (*ptr)) {
3514  break;
3515  }
3516  }
3517  if (piece_verts[i] == -1) {
3518  piece_verts[i] = (*ptr);
3519  }
3520  ptr++;
3521  }
3522 }
3523 
3524 
3525 /**
3526  * This routine sorts the faces of the BOT such that when they are
3527  * taken in groups of "tris_per_piece", * each group (piece) will
3528  * consist of adjacent faces
3529  */
3530 int
3531 rt_bot_sort_faces(struct rt_bot_internal *bot, size_t tris_per_piece)
3532 {
3533  fastf_t *centers = (fastf_t *)NULL; /* triangle centers, used when all else fails */
3534  int *new_faces = (int *)NULL; /* the sorted list of faces to be attached to the BOT at the end of this routine */
3535  int *new_norms = (int *)NULL; /* the sorted list of vertex normals corresponding to the "new_faces" list */
3536  int *old_faces = (int *)NULL; /* a copy of the original face list from the BOT */
3537  int *piece = (int *)NULL; /* a small face list, for just the faces in the current piece */
3538  int *piece_norms = (int *)NULL; /* vertex normals for faces in the current piece */
3539  int *piece_verts = (int *)NULL; /* a list of vertices in the current piece (each vertex appears only once) */
3540  unsigned char *vert_count; /* an array used to hold the number of piece vertices that appear in each BOT face */
3541  size_t new_face_count = 0; /* the current number of faces in the "new_faces" list */
3542  size_t faces_left; /* the number of faces in the "old_faces" array that have not yet been used */
3543  size_t piece_len; /* the current number of faces in the piece */
3544  size_t max_verts; /* the maximum number of piece_verts found in a single unused face */
3545  size_t i;
3546  size_t j;
3547 
3548  RT_BOT_CK_MAGIC(bot);
3549 
3550  /* allocate memory for all the data */
3551  new_faces = (int *)bu_calloc(bot->num_faces * 3, sizeof(int), "new_faces");
3552  old_faces = (int *)bu_calloc(bot->num_faces * 3, sizeof(int), "old_faces");
3553  piece = (int *)bu_calloc(tris_per_piece * 3, sizeof(int), "piece");
3554  vert_count = (unsigned char *)bu_malloc(bot->num_faces * sizeof(unsigned char), "vert_count");
3555  piece_verts = (int *)bu_malloc((tris_per_piece * 3 + 1) * sizeof(int), "piece_verts");
3556  centers = (fastf_t *)NULL;
3557 
3558  if (bot->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) {
3559  new_norms = (int *)bu_calloc(bot->num_faces * 3, sizeof(int), "new_norms");
3560  piece_norms = (int *)bu_calloc(tris_per_piece * 3, sizeof(int), "piece_norms");
3561  }
3562 
3563  /* make a copy of the faces list, this list will be modified
3564  * during the process.
3565  */
3566  for (i = 0; i < bot->num_faces * 3; i++) {
3567  old_faces[i] = bot->faces[i];
3568  }
3569 
3570  /* process until we have sorted all the faces */
3571  faces_left = bot->num_faces;
3572  while (faces_left) {
3573  size_t cur_face;
3574  int done_with_piece;
3575 
3576  /* initialize piece_verts */
3577  for (i = 0; i < tris_per_piece * 3 + 1; i++) {
3578  piece_verts[i] = -1;
3579  }
3580 
3581  /* choose first unused face on the list */
3582  cur_face = 0;
3583  while (cur_face < bot->num_faces && old_faces[cur_face*3] == -1) {
3584  cur_face++;
3585  }
3586 
3587  if (cur_face >= bot->num_faces) {
3588  /* all faces used, we must be done */
3589  break;
3590  }
3591 
3592  /* copy that face to start the piece */
3593  VMOVE(piece, &old_faces[cur_face*3]);
3594  if (bot->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) {
3595  VMOVE(piece_norms, &bot->face_normals[cur_face*3]);
3596  }
3597 
3598  /* also copy it to the piece vertex list */
3599  VMOVE(piece_verts, piece);
3600 
3601  /* mark this face as used */
3602  VSETALL(&old_faces[cur_face*3], -1);
3603 
3604  /* update counts */
3605  piece_len = 1;
3606  faces_left--;
3607 
3608  if (faces_left == 0) {
3609  /* handle the case where the first face in a piece is the
3610  * only face left.
3611  */
3612  for (j = 0; j < piece_len; j++) {
3613  VMOVE(&new_faces[new_face_count*3], &piece[j*3]);
3614  if (bot->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) {
3615  VMOVE(&new_norms[new_face_count*3], &piece_norms[j*3]);
3616  }
3617  new_face_count++;
3618  }
3619  piece_len = 0;
3620  max_verts = 0;
3621 
3622  /* set flag to skip the loop below */
3623  done_with_piece = 1;
3624  } else {
3625  done_with_piece = 0;
3626  }
3627 
3628  while (!done_with_piece) {
3629  size_t max_verts_min;
3630 
3631  /* count the number of times vertices from the current
3632  * piece appear in the remaining faces.
3633  */
3634  (void)memset(vert_count, '\0', bot->num_faces);
3635  max_verts = 0;
3636  for (i = 0; i < bot->num_faces; i++) {
3637  size_t vert_num;
3638  int v0, v1, v2;
3639 
3640  vert_num = i * 3;
3641  if (old_faces[vert_num] == -1) {
3642  continue;
3643  }
3644  v0 = old_faces[vert_num];
3645  v1 = old_faces[vert_num+1];
3646  v2 = old_faces[vert_num+2];
3647 
3648  j = (size_t)-1;
3649  while (piece_verts[++j] != -1) {
3650  if (v0 == piece_verts[j]
3651  || v1 == piece_verts[j]
3652  || v2 == piece_verts[j])
3653  {
3654  vert_count[i]++;
3655  }
3656  }
3657 
3658  if (vert_count[i] > 1) {
3659  /* add this face to the piece */
3660  VMOVE(&piece[piece_len*3], &old_faces[i*3]);
3661  if (bot->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) {
3662  VMOVE(&piece_norms[piece_len*3], &bot->face_normals[i*3]);
3663  }
3664 
3665  /* Add its vertices to the list of piece vertices */
3666  Add_unique_verts(piece_verts, &old_faces[i*3]);
3667 
3668  /* mark this face as used */
3669  VSETALL(&old_faces[i*3], -1);
3670 
3671  /* update counts */
3672  piece_len++;
3673  faces_left--;
3674  vert_count[i] = 0;
3675 
3676  /* check if this piece is done */
3677  if (piece_len == tris_per_piece || faces_left == 0) {
3678  /* copy this piece to the "new_faces" list */
3679  for (j = 0; j < piece_len; j++) {
3680  VMOVE(&new_faces[new_face_count*3], &piece[j*3]);
3681  if (bot->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) {
3682  VMOVE(&new_norms[new_face_count*3], &piece_norms[j*3]);
3683  }
3684  new_face_count++;
3685  }
3686  piece_len = 0;
3687  max_verts = 0;
3688  done_with_piece = 1;
3689  break;
3690  }
3691  }
3692  if (vert_count[i] > max_verts) {
3693  max_verts = vert_count[i];
3694  }
3695  }
3696 
3697  /* set this variable to 2, means look for faces with at
3698  * least common edges.
3699  */
3700  max_verts_min = 2;
3701 
3702  if (max_verts == 0 && !done_with_piece) {
3703  /* none of the remaining faces has any vertices in
3704  * common with the current piece.
3705  */
3706  size_t face_to_add;
3707 
3708  /* resort to using triangle centers. find the closest
3709  * face to the first face in the piece
3710  */
3711  face_to_add = find_closest_face(&centers, piece, old_faces, bot->num_faces, bot->vertices);
3712 
3713  /* Add this face to the current piece */
3714  VMOVE(&piece[piece_len*3], &old_faces[face_to_add*3]);
3715  if (bot->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) {
3716  VMOVE(&piece_norms[piece_len*3], &bot->face_normals[face_to_add*3]);
3717  }
3718 
3719  /* Add its vertices to the list of piece vertices */
3720  Add_unique_verts(piece_verts, &old_faces[face_to_add*3]);
3721 
3722  /* mark this face as used */
3723  VSETALL(&old_faces[face_to_add*3], -1);
3724 
3725  /* update counts */
3726  piece_len++;
3727  faces_left--;
3728 
3729  /* check if this piece is done */
3730  if (piece_len == tris_per_piece || faces_left == 0) {
3731  /* copy this piece to the "new_faces" list */
3732  for (j = 0; j < piece_len; j++) {
3733  VMOVE(&new_faces[new_face_count*3], &piece[j*3]);
3734  if (bot->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) {
3735  VMOVE(&new_norms[new_face_count*3], &piece_norms[j*3]);
3736  }
3737  new_face_count++;
3738  }
3739  piece_len = 0;
3740  max_verts = 0;
3741  done_with_piece = 1;
3742  }
3743  } else if (max_verts == 1 && !done_with_piece) {
3744  /* the best we can find is common vertices */
3745  max_verts_min = 1;
3746  } else if (!done_with_piece) {
3747  /* there are some common edges, so ignore simple shared vertices */
3748  max_verts_min = 2;
3749  }
3750 
3751  /* now add the faces with the highest counts to the
3752  * current piece; do this in a loop that starts by only
3753  * accepting the faces with the most vertices in common
3754  * with the current piece
3755  */
3756  while (max_verts >= max_verts_min && !done_with_piece) {
3757  /* check every face */
3758  for (i = 0; i < bot->num_faces; i++) {
3759  /* if this face has enough vertices in common with
3760  * the piece, add it to the piece
3761  */
3762  if (vert_count[i] == max_verts) {
3763  VMOVE(&piece[piece_len*3], &old_faces[i*3]);
3764  if (bot->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) {
3765  VMOVE(&piece_norms[piece_len*3], &bot->face_normals[i*3]);
3766  }
3767  Add_unique_verts(piece_verts, &old_faces[i*3]);
3768  VSETALL(&old_faces[i*3], -1);
3769 
3770  piece_len++;
3771  faces_left--;
3772 
3773  /* Check if we are done */
3774  if (piece_len == tris_per_piece || faces_left == 0) {
3775  /* copy this piece to the "new_faces" list */
3776  for (j = 0; j < piece_len; j++) {
3777  VMOVE(&new_faces[new_face_count*3], &piece[j*3]);
3778  if (bot->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) {
3779  VMOVE(&new_norms[new_face_count*3], &piece_norms[j*3]);
3780  }
3781  new_face_count++;
3782  }
3783  piece_len = 0;
3784  max_verts = 0;
3785  done_with_piece = 1;
3786  break;
3787  }
3788  }
3789  }
3790  max_verts--;
3791  }
3792  }
3793  }
3794 
3795  bu_free(old_faces, "old_faces");
3796  bu_free(piece, "piece");
3797  bu_free(vert_count, "vert_count");
3798  bu_free(piece_verts, "piece_verts");
3799  if (centers) {
3800  bu_free(centers, "centers");
3801  centers = NULL;
3802  }
3803 
3804  /* do some checking on the "new_faces" */
3805  if (new_face_count != bot->num_faces) {
3806  bu_log("new_face_count = %zu, should be %zu\n", new_face_count, bot->num_faces);
3807  bu_free(new_faces, "new_faces");
3808  return 1;
3809  }
3810 
3811  if (bot->faces)
3812  bu_free(bot->faces, "bot->faces");
3813 
3814  bot->faces = new_faces;
3815 
3816  if (bot->bot_flags & RT_BOT_HAS_SURFACE_NORMALS) {
3817  bu_free(piece_norms, "piece_norms");
3818  if (bot->face_normals)
3819  bu_free(bot->face_normals, "bot->face_normals");
3820  bot->face_normals = new_norms;
3821  }
3822 
3823  return 0;
3824 }
3825 
3826 
3827 HIDDEN void
3828 delete_edge(int v1, int v2, struct bot_edge **edges)
3829 {
3830  struct bot_edge *edg, *prev=NULL;
3831 
3832  if (v1 < v2) {
3833  edg = edges[v1];
3834  while (edg) {
3835  if (edg->v == v2) {
3836  edg->use_count--;
3837  if (edg->use_count < 1) {
3838  if (prev) {
3839  prev->next = edg->next;
3840  } else {
3841  edges[v1] = edg->next;
3842  }
3843  edg->v = -1;
3844  edg->next = NULL;
3845  bu_free(edg, "bot_edge");
3846  return;
3847  }
3848  }
3849  prev = edg;
3850  edg = edg->next;
3851  }
3852  } else {
3853  edg = edges[v2];
3854  while (edg) {
3855  if (edg->v == v1) {
3856  edg->use_count--;
3857  if (edg->use_count < 1) {
3858  if (prev) {
3859  prev->next = edg->next;
3860  } else {
3861  edges[v2] = edg->next;
3862  }
3863  edg->v = -1;
3864  edg->next = NULL;
3865  bu_free(edg, "bot_edge");
3866  return;
3867  }
3868  }
3869  prev = edg;
3870  edg = edg->next;
3871  }
3872  }
3873 }
3874 
3875 
3876 /**
3877  * Routine to perform the actual edge decimation step The edge from v1
3878  * to v2 is eliminated by moving v1 to v2. Faces that used this edge
3879  * are eliminated. Faces that used v1 will have that reference
3880  * changed to v2.
3881  */
3882 HIDDEN int
3883 decimate_edge(int v1, int v2, struct bot_edge **edges, size_t num_edges, int *faces, size_t num_faces, int face_del1, int face_del2)
3884 {
3885  size_t i;
3886  struct bot_edge *edg;
3887 
3888  /* first eliminate all the edges of the two deleted faces from the edge list */
3889  delete_edge(faces[face_del1 * 3 + 0], faces[face_del1 * 3 + 1], edges);
3890  delete_edge(faces[face_del1 * 3 + 1], faces[face_del1 * 3 + 2], edges);
3891  delete_edge(faces[face_del1 * 3 + 2], faces[face_del1 * 3 + 0], edges);
3892  delete_edge(faces[face_del2 * 3 + 0], faces[face_del2 * 3 + 1], edges);
3893  delete_edge(faces[face_del2 * 3 + 1], faces[face_del2 * 3 + 2], edges);
3894  delete_edge(faces[face_del2 * 3 + 2], faces[face_del2 * 3 + 0], edges);
3895 
3896  /* do the decimation */
3897  for (i = 0; i < 3; i++) {
3898  faces[face_del1*3 + i] = -1;
3899  faces[face_del2*3 + i] = -1;
3900  }
3901  for (i = 0; i < num_faces * 3; i++) {
3902  if (faces[i] == v1) {
3903  faces[i] = v2;
3904  }
3905  }
3906 
3907  /* update the edge list; now move all the remaining edges at
3908  * edges[v1] to somewhere else.
3909  */
3910  edg = edges[v1];
3911  while (edg) {
3912  struct bot_edge *ptr;
3913  struct bot_edge *next;
3914 
3915  next = edg->next;
3916 
3917  if (edg->v < v2) {
3918  ptr = edges[edg->v];
3919  while (ptr) {
3920  if (ptr->v == v2) {
3921  ptr->use_count++;
3922  edg->v = -1;
3923  edg->next = NULL;
3924  bu_free(edg, "bot edge");
3925  break;
3926  }
3927  ptr = ptr->next;
3928  }
3929  if (!ptr) {
3930  edg->next = edges[edg->v];
3931  edges[edg->v] = edg;
3932  edg->v = v2;
3933  }
3934  } else if (edg->v > v2) {
3935  ptr = edges[v2];
3936  while (ptr) {
3937  if (ptr->v == edg->v) {
3938  ptr->use_count++;
3939  edg->v = -1;
3940  edg->next = NULL;
3941  bu_free(edg, "bot edge");
3942  break;
3943  }
3944  ptr = ptr->next;
3945  }
3946  if (!ptr) {
3947  edg->next = edges[v2];
3948  edges[v2] = edg;
3949  }
3950  } else {
3951  edg->v = -1;
3952  edg->next = NULL;
3953  bu_free(edg, "bot edge");
3954  }
3955 
3956  edg = next;
3957  }
3958  edges[v1] = NULL;
3959 
3960  /* now change all remaining v1 references to v2 */
3961  for (i = 0; i < num_edges; i++) {
3962  struct bot_edge *next, *prev, *ptr;
3963 
3964  prev = NULL;
3965  edg = edges[i];
3966  /* look at edges starting from vertex #i */
3967  while (edg) {
3968  next = edg->next;
3969 
3970  if (edg->v == v1) {
3971  /* this one is affected */
3972  edg->v = v2; /* change v1 to v2 */
3973  if ((size_t)v2 < i) {
3974  /* disconnect this edge from list #i */
3975  if (prev) {
3976  prev->next = next;
3977  } else {
3978  edges[i] = next;
3979  }
3980 
3981  /* this edge must move to the "v2" list */
3982  ptr = edges[v2];
3983  while (ptr) {
3984  if ((size_t)ptr->v == i) {
3985  /* found another occurrence of this edge
3986  * increment use count
3987  */
3988  ptr->use_count++;
3989 
3990  /* delete the original */
3991  edg->v = -1;
3992  edg->next = NULL;
3993  bu_free(edg, "bot edge");
3994  break;
3995  }
3996  ptr = ptr->next;
3997  }
3998  if (!ptr) {
3999  /* did not find another occurrence, add to list */
4000  edg->next = edges[v2];
4001  edges[v2] = edg;
4002  }
4003  edg = next;
4004  } else if ((size_t)v2 > i) {
4005  /* look for other occurrences of this edge in this
4006  * list if found, just increment use count
4007  */
4008  ptr = edges[i];
4009  while (ptr) {
4010  if (ptr->v == v2 && ptr != edg) {
4011  /* found another occurrence */
4012  /* increment use count */
4013  ptr->use_count++;
4014 
4015  /* disconnect original from list */
4016  if (prev) {
4017  prev->next = next;
4018  } else {
4019  edges[i] = next;
4020  }
4021 
4022  /* free it */
4023  edg->v = -1;
4024  edg->next = NULL;
4025  bu_free(edg, "bot edge");
4026 
4027  break;
4028  }
4029  ptr = ptr->next;
4030  }
4031  if (!ptr) {
4032  prev = edg;
4033  }
4034  edg = next;
4035  } else {
4036  /* disconnect original from list */
4037  if (prev) {
4038  prev->next = next;
4039  } else {
4040  edges[i] = next;
4041  }
4042 
4043  /* free it */
4044  edg->v = -1;
4045  edg->next = NULL;
4046  bu_free(edg, "bot edge");
4047  }
4048  } else {
4049  /* unaffected edge, just continue */
4050  edg = next;
4051  }
4052  }
4053  }
4054 
4055  return 2;
4056 }
4057 
4058 
4059 /* for simplicity, only consider vertices that are shared with less
4060  * than MAX_AFFECTED_FACES */
4061 #define MAX_AFFECTED_FACES 128
4062 
4063 
4064 /**
4065  * Routine to determine if the specified edge can be eliminated within
4066  * the given constraints:
4067  *
4068  * "faces" is the current working version of the BOT face list.
4069  *
4070  * "v1" and "v2" are the indices into the BOT vertex list, they define
4071  * the edge.
4072  *
4073  * "max_chord_error" is the maximum distance allowed between the old
4074  * surface and new.
4075  *
4076  * "max_normal_error" is actually the minimum dot product allowed
4077  * between old and new surface normals (cosine).
4078  *
4079  * "min_edge_length_sq" is the square of the minimum allowed edge
4080  * length.
4081  *
4082  * any constraint value of -1.0 means ignore this constraint
4083  *
4084  * returns 1 if edge can be eliminated without breaking constraints, 0
4085  * otherwise.
4086  */
4087 HIDDEN int
4088 edge_can_be_decimated(struct rt_bot_internal *bot,
4089  int *faces,
4090  struct bot_edge **edges,
4091  int v1,
4092  int v2,
4093  int *face_del1,
4094  int *face_del2,
4095  fastf_t max_chord_error,
4096  fastf_t max_normal_error,
4097  fastf_t min_edge_length_sq)
4098 {
4099  size_t i, j, k;
4100  size_t num_faces = bot->num_faces;
4101  size_t num_edges = bot->num_vertices;
4102  size_t count, v1_count;
4103  size_t affected_count = 0;
4104  vect_t v01, v02, v12;
4105  fastf_t *vertices = bot->vertices;
4106  size_t faces_affected[MAX_AFFECTED_FACES];
4107 
4108  if (v1 == -1 || v2 == -1) {
4109  return 0;
4110  }
4111 
4112  /* find faces to be deleted or affected */
4113  *face_del1 = -1;
4114  *face_del2 = -1;
4115  for (i = 0; i < num_faces*3; i += 3) {
4116  count = 0;
4117  v1_count = 0;
4118  for (j = 0; j < 3; j++) {
4119  k = i + j;
4120  if (faces[k] == v1) {
4121  /* found a reference to v1, count it */
4122  count++;
4123  v1_count++;
4124  } else if (faces[k] == v2) {
4125  /* found a reference to v2, count it */
4126  count++;
4127  }
4128  }
4129  if (count > 1) {
4130  /* this face will get deleted */
4131  if (*face_del1 != -1) {
4132  *face_del2 = i/3;
4133  } else {
4134  *face_del1 = i/3;
4135  }
4136  } else if (v1_count) {
4137  /* this face will be affected */
4138  faces_affected[affected_count] = i;
4139  affected_count++;
4140  if (affected_count >= MAX_AFFECTED_FACES) {
4141  return 0;
4142  }
4143  }
4144  }
4145 
4146  /* if only one face will be deleted, do not decimate this may be a
4147  * free edge
4148  */
4149  if (*face_del2 == -1) {
4150  return 0;
4151  }
4152 
4153  /* another easy test to avoid moving free edges */
4154  if (affected_count < 1) {
4155  return 0;
4156  }
4157 
4158  /* for BOTs that are expected to have free edges, do a rigorous
4159  * check for free edges
4160  */
4161  if (bot->mode == RT_BOT_PLATE || bot->mode == RT_BOT_SURFACE) {
4162  struct bot_edge *edg;
4163 
4164  /* check if vertex v1 is on a free edge */
4165  for (i = 0; i < num_edges; i++) {
4166  edg = edges[i];
4167  while (edg) {
4168  if ((i == (size_t)v1 || edg->v == v1) && edg->use_count < 2) {
4169  return 0;
4170  }
4171  edg = edg->next;
4172  }
4173  }
4174  }
4175 
4176  /* calculate edge vector */
4177  VSUB2(v12, &vertices[v1*3], &vertices[v2*3]);
4178 
4179  if (min_edge_length_sq > SMALL_FASTF) {
4180  if (MAGSQ(v12) > min_edge_length_sq) {
4181  return 0;
4182  }
4183  }
4184 
4185  if (max_chord_error > -1.0 - SMALL_FASTF || max_normal_error > -1.0 - SMALL_FASTF) {
4186  /* check if surface is within max_chord_error of vertex to be
4187  * eliminated; loop through all affected faces.
4188  */
4189  for (i = 0; i < affected_count; i++) {
4190  fastf_t dist;
4191  fastf_t dot;
4192  plane_t pla, plb;
4193  int va, vb, vc;
4194 
4195  /* calculate plane of this face before and after
4196  * adjustment if the normal changes too much, do not
4197  * decimate
4198  */
4199 
4200  /* first calculate original face normal (use original BOT
4201  * face list)
4202  */
4203  va = bot->faces[faces_affected[i]];
4204  vb = bot->faces[faces_affected[i]+1];
4205  vc = bot->faces[faces_affected[i]+2];
4206  VSUB2(v01, &vertices[vb*3], &vertices[va*3]);
4207  VSUB2(v02, &vertices[vc*3], &vertices[va*3]);
4208  VCROSS(plb, v01, v02);
4209  VUNITIZE(plb);
4210  plb[W] = VDOT(&vertices[va*3], plb);
4211 
4212  /* do the same using the working face list */
4213  va = faces[faces_affected[i]];
4214  vb = faces[faces_affected[i]+1];
4215  vc = faces[faces_affected[i]+2];
4216  /* make the proposed decimation changes */
4217  if (va == v1) {
4218  va = v2;
4219  } else if (vb == v1) {
4220  vb = v2;
4221  } else if (vc == v1) {
4222  vc = v2;
4223  }
4224  VSUB2(v01, &vertices[vb*3], &vertices[va*3]);
4225  VSUB2(v02, &vertices[vc*3], &vertices[va*3]);
4226  VCROSS(pla, v01, v02);
4227  VUNITIZE(pla);
4228  pla[W] = VDOT(&vertices[va*3], pla);
4229 
4230  /* max_normal_error is actually a minimum dot product */
4231  dot = VDOT(pla, plb);
4232  if (max_normal_error > -1.0 - SMALL_FASTF && dot < max_normal_error) {
4233  return 0;
4234  }
4235 
4236  /* check the distance between this new plane and vertex
4237  * v1
4238  */
4239  dist = fabs(DIST_PT_PLANE(&vertices[v1*3], pla));
4240  if (max_chord_error > -1.0 - SMALL_FASTF && dist > max_chord_error) {
4241  return 0;
4242  }
4243  }
4244  }
4245 
4246  return 1;
4247 }
4248 
4249 
4250 /**
4251  * routine to reduce the number of triangles in a BOT by edges
4252  * decimation.
4253  *
4254  * max_chord_error is the maximum error distance allowed
4255  * max_normal_error is the maximum change in surface normal allowed
4256  *
4257  * This and associated routines maintain a list of edges and their
4258  * "use counts" A "free edge" is one with a use count of 1, most edges
4259  * have a use count of 2 When a use count reaches zero, the edge is
4260  * removed from the list. The list is used to direct the edge
4261  * decimation process and to avoid deforming the shape of a non-volume
4262  * enclosing BOT by keeping track of use counts (and thereby free
4263  * edges) If a free edge would be moved, that decimation is not
4264  * performed.
4265  */
4266 int
4267 rt_bot_decimate(struct rt_bot_internal *bot, /* BOT to be decimated */
4268  fastf_t max_chord_error, /* maximum allowable chord error (mm) */
4269  fastf_t max_normal_error, /* maximum allowable normal error (degrees) */
4270  fastf_t min_edge_length) /* minimum allowed edge length */
4271 {
4272  int *faces = NULL;
4273  struct bot_edge **edges = NULL;
4274  fastf_t min_edge_length_sq = 0.0;
4275  size_t edges_deleted = 0;
4276  size_t edge_count = 0;
4277  size_t face_count = 0;
4278  size_t actual_count = 0;
4279  size_t deleted = 0;
4280  size_t i = 0;
4281  int done;
4282 
4283  RT_BOT_CK_MAGIC(bot);
4284 
4285  /* convert normal error to something useful (a minimum dot product) */
4286  if (max_normal_error > -1.0 - SMALL_FASTF) {
4287  max_normal_error = cos(max_normal_error * DEG2RAD);
4288  }
4289 
4290  if (min_edge_length > SMALL_FASTF) {
4291  min_edge_length_sq = min_edge_length * min_edge_length;
4292  } else {
4293  min_edge_length_sq = min_edge_length;
4294  }
4295 
4296  /* make a working copy of the face list */
4297  faces = (int *)bu_malloc(sizeof(int) * bot->num_faces * 3, "faces");
4298  for (i = 0; i < bot->num_faces * 3; i++) {
4299  faces[i] = bot->faces[i];
4300  }
4301  face_count = bot->num_faces;
4302 
4303  /* make a list of edges in the BOT; each edge will be in the list
4304  * for its lower numbered vertex index
4305  */
4306  edge_count = buildEdgeTable(bot, &edges);
4307 
4308  /* the decimation loop */
4309  done = 0;
4310  while (!done) {
4311  done = 1;
4312 
4313  /* visit each edge */
4314  for (i = 0; i < bot->num_vertices; i++) {
4315  struct bot_edge *ptr;
4316  int face_del1, face_del2;
4317 
4318  ptr = edges[i];
4319  while (ptr) {
4320 
4321  /* try to avoid making 2D objects */
4322  if (face_count < 5)
4323  break;
4324 
4325  /* check if this edge can be eliminated (try both directions) */
4326  if (edge_can_be_decimated(bot, faces, edges, i, ptr->v,
4327  &face_del1, &face_del2,
4328  max_chord_error,
4329  max_normal_error,
4330  min_edge_length_sq)) {
4331  face_count -= decimate_edge(i, ptr->v, edges, bot->num_vertices,
4332  faces, bot->num_faces,
4333  face_del1, face_del2);
4334  edges_deleted++;
4335  done = 0;
4336  break;
4337  } else if (edge_can_be_decimated(bot, faces, edges, ptr->v, i,
4338  &face_del1, &face_del2,
4339  max_chord_error,
4340  max_normal_error,
4341  min_edge_length_sq)) {
4342  face_count -= decimate_edge(ptr->v, i, edges, bot->num_vertices,
4343  faces, bot->num_faces,
4344  face_del1, face_del2);
4345  edges_deleted++;
4346  done = 0;
4347  break;
4348  } else {
4349  ptr = ptr->next;
4350  }
4351  }
4352  }
4353  }
4354 
4355  /* free some memory */
4356  for (i = 0; i < bot->num_vertices; i++) {
4357  struct bot_edge *ptr, *ptr2;
4358 
4359  ptr = edges[i];
4360  while (ptr) {
4361  ptr2 = ptr;
4362  ptr = ptr->next;
4363  bu_free(ptr2, "ptr->edges");
4364  }
4365  }
4366  bu_free(edges, "edges");
4367  edges = NULL;
4368 
4369  /* condense the face list */
4370  actual_count = 0;
4371  deleted = 0;
4372  for (i = 0; i < bot->num_faces * 3; i++) {
4373  if (faces[i] == -1) {
4374  deleted++;
4375  continue;
4376  }
4377  if (deleted) {
4378  faces[i-deleted] = faces[i];
4379  }
4380  actual_count++;
4381  }
4382 
4383  if (actual_count % 3) {
4384  bu_log("rt_bot_decimate: face vertices count is not a multiple of 3!!\n");
4385  bu_free(faces, "faces");
4386  return -1;
4387  }
4388 
4389  bu_log("original face count = %zu, edge count = %zu\n", bot->num_faces, edge_count);
4390  bu_log("\tedges deleted = %zu\n", edges_deleted);
4391  bu_log("\tnew face_count = %zu\n", face_count);
4392 
4393  actual_count /= 3;
4394 
4395  if (face_count != actual_count) {
4396  bu_log("rt_bot_decimate: Face count is confused!!\n");
4397  bu_free(faces, "faces");
4398  return -2;
4399  }
4400 
4401  if (bot->faces)
4402  bu_free(bot->faces, "bot->faces");
4403  bot->faces = (int *)bu_realloc(faces, sizeof(int) * face_count * 3, "bot->faces");
4404  bot->num_faces = face_count;
4405 
4406  /* removed unused vertices */
4407  (void)rt_bot_condense(bot);
4408 
4409  return edges_deleted;
4410 }
4411 
4412 
4413 HIDDEN int
4415 {
4416  if (ap) RT_CK_APPLICATION(ap);
4417  return 0;
4418 }
4419 
4420 
4421 HIDDEN int
4422 bot_smooth_hit(struct application *ap, struct partition *PartHeadp, struct seg *UNUSED(seg))
4423 {
4424  struct partition *pp;
4425  struct soltab *stp;
4426  vect_t inormal, onormal;
4427  vect_t *normals=(vect_t *)ap->a_uptr;
4428 
4429  for (pp = PartHeadp->pt_forw; pp != PartHeadp; pp = pp->pt_forw) {
4430  stp = pp->pt_inseg->seg_stp;
4431  RT_HIT_NORMAL(inormal, pp->pt_inhit, stp, &(ap->a_ray), pp->pt_inflip);
4432 
4433  stp = pp->pt_outseg->seg_stp;
4434  RT_HIT_NORMAL(onormal, pp->pt_outhit, stp, &(ap->a_ray), pp->pt_outflip);
4435  if (pp->pt_inhit->hit_surfno == ap->a_user) {
4436  VMOVE(normals[pp->pt_inhit->hit_surfno], inormal);
4437  break;
4438  }
4439  if (pp->pt_outhit->hit_surfno == ap->a_user) {
4440  VMOVE(normals[pp->pt_outhit->hit_surfno], onormal);
4441  break;
4442  }
4443  }
4444 
4445  return 1;
4446 }
4447 
4448 
4449 int
4450 rt_bot_smooth(struct rt_bot_internal *bot, const char *bot_name, struct db_i *dbip, fastf_t norm_tol_angle)
4451 {
4452  int vert_no;
4453  size_t i, j, k;
4454  struct rt_i *rtip;
4455  struct application ap;
4456  fastf_t normal_dot_tol = 0.0;
4457  vect_t *normals;
4458  const double ONE_THIRD = 1.0 / 3.0;
4459 
4460  RT_BOT_CK_MAGIC(bot);
4461 
4462  if (norm_tol_angle < 0.0 || norm_tol_angle > M_PI) {
4463  bu_log("normal tolerance angle must be from 0 to Pi\n");
4464  return -2;
4465  }
4466 
4467  if ((bot->orientation == RT_BOT_UNORIENTED) && (bot->mode != RT_BOT_SOLID)) {
4468  bu_log("Cannot smooth unoriented BOT primitives unless they are solid objects\n");
4469  return -3;
4470  }
4471 
4472  normal_dot_tol = cos(norm_tol_angle);
4473 
4474  if (bot->normals) {
4475  bu_free(bot->normals, "bot->normals");
4476  bot->normals = NULL;
4477  }
4478 
4479  if (bot->face_normals) {
4480  bu_free(bot->face_normals, "bot->face_normals");
4481  bot->face_normals = NULL;
4482  }
4483 
4484  bot->bot_flags &= ~(RT_BOT_HAS_SURFACE_NORMALS | RT_BOT_USE_NORMALS);
4485  bot->num_normals = 0;
4486  bot->num_face_normals = 0;
4487 
4488  /* build an array of surface normals */
4489  normals = (vect_t *)bu_calloc(bot->num_faces, sizeof(vect_t), "normals");
4490 
4491  if (bot->orientation == RT_BOT_UNORIENTED) {
4492  /* need to do raytracing, do prepping */
4493  rtip = rt_new_rti(dbip);
4494 
4495  RT_APPLICATION_INIT(&ap);
4496  ap.a_rt_i = rtip;
4497  ap.a_hit = bot_smooth_hit;
4498  ap.a_miss = bot_smooth_miss;
4499  ap.a_uptr = (void *)normals;
4500  if (rt_gettree(rtip, bot_name)) {
4501  bu_log("rt_gettree failed for %s\n", bot_name);
4502  return -1;
4503  }
4504  rt_prep(rtip);
4505 
4506  /* find the surface normal for each face */
4507  for (i = 0; i < bot->num_faces; i++) {
4508  vect_t a, b;
4509  vect_t inv_dir;
4510 
4511  if (bot->faces[i*3+2] < 0 || (size_t)bot->faces[i*3+2] > bot->num_vertices)
4512  continue; /* sanity */
4513 
4514  VSUB2(a, &bot->vertices[bot->faces[i*3+1]*3], &bot->vertices[bot->faces[i*3]*3]);
4515  VSUB2(b, &bot->vertices[bot->faces[i*3+2]*3], &bot->vertices[bot->faces[i*3]*3]);
4516  VCROSS(ap.a_ray.r_dir, a, b);
4517  VUNITIZE(ap.a_ray.r_dir);
4518 
4519  /* calculate ray start point */
4520  VADD3(ap.a_ray.r_pt, &bot->vertices[bot->faces[i*3]*3],
4521  &bot->vertices[bot->faces[i*3+1]*3],
4522  &bot->vertices[bot->faces[i*3+2]*3]);
4523  VSCALE(ap.a_ray.r_pt, ap.a_ray.r_pt, ONE_THIRD);
4524 
4525  /* back out to bounding box limits */
4526 
4527  /* Compute the inverse of the direction cosines */
4528  if (ap.a_ray.r_dir[X] < -SQRT_SMALL_FASTF) {
4529  inv_dir[X] = 1.0/ap.a_ray.r_dir[X];
4530  } else if (ap.a_ray.r_dir[X] > SQRT_SMALL_FASTF) {
4531  inv_dir[X] = 1.0/ap.a_ray.r_dir[X];
4532  } else {
4533  ap.a_ray.r_dir[X] = 0.0;
4534  inv_dir[X] = INFINITY;
4535  }
4536  if (ap.a_ray.r_dir[Y] < -SQRT_SMALL_FASTF) {
4537  inv_dir[Y] = 1.0/ap.a_ray.r_dir[Y];
4538  } else if (ap.a_ray.r_dir[Y] > SQRT_SMALL_FASTF) {
4539  inv_dir[Y] = 1.0/ap.a_ray.r_dir[Y];
4540  } else {
4541  ap.a_ray.r_dir[Y] = 0.0;
4542  inv_dir[Y] = INFINITY;
4543  }
4544  if (ap.a_ray.r_dir[Z] < -SQRT_SMALL_FASTF) {
4545  inv_dir[Z]=1.0/ap.a_ray.r_dir[Z];
4546  } else if (ap.a_ray.r_dir[Z] > SQRT_SMALL_FASTF) {
4547  inv_dir[Z]=1.0/ap.a_ray.r_dir[Z];
4548  } else {
4549  ap.a_ray.r_dir[Z] = 0.0;
4550  inv_dir[Z] = INFINITY;
4551  }
4552 
4553  if (!rt_in_rpp(&ap.a_ray, inv_dir, rtip->mdl_min, rtip->mdl_max)) {
4554  /* ray missed!!! */
4555  bu_log("ERROR: Ray missed target!!!!\n");
4556  }
4557  VJOIN1(ap.a_ray.r_pt, ap.a_ray.r_pt, ap.a_ray.r_min, ap.a_ray.r_dir);
4558  ap.a_user = i;
4559  (void) rt_shootray(&ap);
4560  }
4561  rt_free_rti(rtip);
4562  } else {
4563  /* calculate normals */
4564  for (i = 0; i < bot->num_faces; i++) {
4565  vect_t a, b;
4566 
4567  if (bot->faces[i*3+2] < 0 || (size_t)bot->faces[i*3+2] > bot->num_vertices)
4568  continue; /* sanity */
4569 
4570  VSUB2(a, &bot->vertices[bot->faces[i*3+1]*3], &bot->vertices[bot->faces[i*3]*3]);
4571  VSUB2(b, &bot->vertices[bot->faces[i*3+2]*3], &bot->vertices[bot->faces[i*3]*3]);
4572  VCROSS(normals[i], a, b);
4573  VUNITIZE(normals[i]);
4574  if (bot->orientation == RT_BOT_CW) {
4575  VREVERSE(normals[i], normals[i]);
4576  }
4577  }
4578  }
4579 
4580  bot->num_normals = bot->num_faces * 3;
4581  bot->num_face_normals = bot->num_faces;
4582 
4583  bot->normals = (fastf_t *)bu_calloc(bot->num_normals * 3, sizeof(fastf_t), "bot->normals");
4584  bot->face_normals = (int *)bu_calloc(bot->num_face_normals * 3, sizeof(int), "bot->face_normals");
4585 
4586  /* process each face */
4587  for (i = 0; i < bot->num_faces; i++) {
4588  vect_t def_norm; /* default normal for this face */
4589 
4590  VMOVE(def_norm, normals[i]);
4591 
4592  /* process each vertex in his face */
4593  for (k = 0; k < 3; k++) {
4594  vect_t ave_norm;
4595 
4596  /* the actual vertex index */
4597  vert_no = bot->faces[i*3+k];
4598  VSETALL(ave_norm, 0.0);
4599 
4600  /* find all the faces that use this vertex */
4601  for (j = 0; j < bot->num_faces * 3; j++) {
4602  if (bot->faces[j] == vert_no) {
4603  size_t the_face;
4604 
4605  the_face = j / 3;
4606 
4607  /* add all the normals that are within tolerance
4608  * this also gets def_norm
4609  */
4610  if (VDOT(normals[the_face], def_norm) >= normal_dot_tol) {
4611  VADD2(ave_norm, ave_norm, normals[the_face]);
4612  }
4613  }
4614  }
4615  VUNITIZE(ave_norm);
4616  VMOVE(&bot->normals[(i*3+k)*3], ave_norm);
4617  bot->face_normals[i*3+k] = i*3+k;
4618  }
4619  }
4620 
4621  bu_free(normals, "normals");
4622  normals = NULL;
4623 
4624  bot->bot_flags |= RT_BOT_HAS_SURFACE_NORMALS;
4625  bot->bot_flags |= RT_BOT_USE_NORMALS;
4626 
4627  return 0;
4628 }
4629 
4630 
4631 int
4632 rt_bot_flip(struct rt_bot_internal *bot)
4633 {
4634  size_t i;
4635  size_t tmp_index;
4636 
4637  RT_BOT_CK_MAGIC(bot);
4638 
4639  for (i = 0; i < bot->num_faces; ++i) {
4640  /* Swap any two vertex references. Here we're swapping 1 and 2. */
4641  tmp_index = bot->faces[i*3+1];
4642  bot->faces[i*3+1] = bot->faces[i*3+2];
4643  bot->faces[i*3+2] = tmp_index;
4644  }
4645 
4646  switch (bot->orientation) {
4647  case RT_BOT_CCW:
4648  bot->orientation = RT_BOT_CW;
4649  break;
4650  case RT_BOT_CW:
4651  bot->orientation = RT_BOT_CCW;
4652  break;
4653  case RT_BOT_UNORIENTED:
4654  default:
4655  break;
4656  }
4657 
4658  return 0;
4659 }
4660 
4661 
4662 struct tri_edges {
4663  struct bu_list l;
4664  size_t edge_1[2];
4665  size_t edge_2[2];
4666  size_t edge_3[2];
4667  size_t tri;
4668 };
4669 
4670 
4671 struct tri_pts {
4672  struct bu_list l;
4673  int a;
4674  int b;
4675  int c;
4676  int tri;
4677 };
4678 
4679 
4680 void
4681 rt_bot_sync_func(struct rt_bot_internal *bot,
4682  struct tri_edges *tep,
4683  struct tri_edges *headTep,
4684  struct tri_edges *usedTep)
4685 {
4686  struct tri_edges *neighbor_tep;
4687  struct tri_edges **stack = (struct tri_edges **)bu_calloc(bot->num_faces, sizeof(struct tri_edges *), "rt_bot_sync_func: stack");
4688  register size_t si = 0;
4689  register int not_done = 1;
4690 
4691  while (not_done) {
4692  begin:
4693  for (BU_LIST_FOR(neighbor_tep, tri_edges, &headTep->l)) {
4694  if ((tep->edge_1[0] == neighbor_tep->edge_1[0] &&
4695  tep->edge_1[1] == neighbor_tep->edge_1[1]) ||
4696  (tep->edge_1[0] == neighbor_tep->edge_2[0] &&
4697  tep->edge_1[1] == neighbor_tep->edge_2[1]) ||
4698  (tep->edge_1[0] == neighbor_tep->edge_3[0] &&
4699  tep->edge_1[1] == neighbor_tep->edge_3[1]) ||
4700  (tep->edge_2[0] == neighbor_tep->edge_1[0] &&
4701  tep->edge_2[1] == neighbor_tep->edge_1[1]) ||
4702  (tep->edge_2[0] == neighbor_tep->edge_2[0] &&
4703  tep->edge_2[1] == neighbor_tep->edge_2[1]) ||
4704  (tep->edge_2[0] == neighbor_tep->edge_3[0] &&
4705  tep->edge_2[1] == neighbor_tep->edge_3[1]) ||
4706  (tep->edge_3[0] == neighbor_tep->edge_1[0] &&
4707  tep->edge_3[1] == neighbor_tep->edge_1[1]) ||
4708  (tep->edge_3[0] == neighbor_tep->edge_2[0] &&
4709  tep->edge_3[1] == neighbor_tep->edge_2[1]) ||
4710  (tep->edge_3[0] == neighbor_tep->edge_3[0] &&
4711  tep->edge_3[1] == neighbor_tep->edge_3[1])) {
4712  /* Found a shared edge of a neighboring triangle whose
4713  * orientation needs to be reversed.
4714  */
4715  size_t tmp_index;
4716 
4717  BU_LIST_DEQUEUE(&neighbor_tep->l);
4718  BU_LIST_APPEND(&usedTep->l, &neighbor_tep->l);
4719 
4720  /* Swap any two vertex references. Here we're swapping 1 and 2. */
4721  tmp_index = bot->faces[neighbor_tep->tri*3+1];
4722  bot->faces[neighbor_tep->tri*3+1] = bot->faces[neighbor_tep->tri*3+2];
4723  bot->faces[neighbor_tep->tri*3+2] = tmp_index;
4724 
4725  /* Also need to reverse the edges in neighbor_tep */
4726  tmp_index = neighbor_tep->edge_1[0];
4727  neighbor_tep->edge_1[0] = neighbor_tep->edge_1[1];
4728  neighbor_tep->edge_1[1] = tmp_index;
4729  tmp_index = neighbor_tep->edge_2[0];
4730  neighbor_tep->edge_2[0] = neighbor_tep->edge_2[1];
4731  neighbor_tep->edge_2[1] = tmp_index;
4732  tmp_index = neighbor_tep->edge_3[0];
4733  neighbor_tep->edge_3[0] = neighbor_tep->edge_3[1];
4734  neighbor_tep->edge_3[1] = tmp_index;
4735 
4736  stack[++si] = tep;
4737  tep = neighbor_tep;
4738  goto begin;
4739  } else if ((tep->edge_1[0] == neighbor_tep->edge_1[1] &&
4740  tep->edge_1[1] == neighbor_tep->edge_1[0]) ||
4741  (tep->edge_1[0] == neighbor_tep->edge_2[1] &&
4742  tep->edge_1[1] == neighbor_tep->edge_2[0]) ||
4743  (tep->edge_1[0] == neighbor_tep->edge_3[1] &&
4744  tep->edge_1[1] == neighbor_tep->edge_3[0]) ||
4745  (tep->edge_2[0] == neighbor_tep->edge_1[1] &&
4746  tep->edge_2[1] == neighbor_tep->edge_1[0]) ||
4747  (tep->edge_2[0] == neighbor_tep->edge_2[1] &&
4748  tep->edge_2[1] == neighbor_tep->edge_2[0]) ||
4749  (tep->edge_2[0] == neighbor_tep->edge_3[1] &&
4750  tep->edge_2[1] == neighbor_tep->edge_3[0]) ||
4751  (tep->edge_3[0] == neighbor_tep->edge_1[1] &&
4752  tep->edge_3[1] == neighbor_tep->edge_1[0]) ||
4753  (tep->edge_3[0] == neighbor_tep->edge_2[1] &&
4754  tep->edge_3[1] == neighbor_tep->edge_2[0]) ||
4755  (tep->edge_3[0] == neighbor_tep->edge_3[1] &&
4756  tep->edge_3[1] == neighbor_tep->edge_3[0])) {
4757  /* Found a shared edge of a neighboring triangle whose
4758  * orientation is fine.
4759  */
4760 
4761  BU_LIST_DEQUEUE(&neighbor_tep->l);
4762  BU_LIST_APPEND(&usedTep->l, &neighbor_tep->l);
4763 
4764  stack[++si] = tep;
4765  tep = neighbor_tep;
4766  goto begin;
4767  }
4768  }
4769 
4770  if (si < 1)
4771  not_done = 0;
4772  else
4773  tep = stack[si--];
4774  }
4775 
4776  bu_free((void *)stack, "rt_bot_sync_func: stack");
4777 }
4778 
4779 
4780 int
4781 rt_bot_sync(struct rt_bot_internal *bot)
4782 {
4783  size_t i;
4784  struct tri_edges headTep;
4785  struct tri_edges usedTep;
4786  struct tri_edges *tep;
4787  struct tri_edges *alltep;
4788  size_t pt_A, pt_B, pt_C;
4789 
4790  RT_BOT_CK_MAGIC(bot);
4791 
4792  /* Nothing to do */
4793  if (bot->num_faces < 2)
4794  return 0;
4795 
4796  BU_LIST_INIT(&headTep.l);
4797  BU_LIST_INIT(&usedTep.l);
4798 
4799  alltep = (struct tri_edges *)bu_calloc(bot->num_faces, sizeof(struct tri_edges), "rt_bot_sync: alltep");
4800 
4801  /* Initialize tep list */
4802  for (i = 0; i < bot->num_faces; ++i) {
4803  tep = &alltep[i];
4804  BU_LIST_APPEND(&headTep.l, &tep->l);
4805 
4806  pt_A = bot->faces[i*3+0];
4807  pt_B = bot->faces[i*3+1];
4808  pt_C = bot->faces[i*3+2];
4809 
4810  tep->tri = i;
4811  tep->edge_1[0] = pt_A;
4812  tep->edge_1[1] = pt_B;
4813  tep->edge_2[0] = pt_B;
4814  tep->edge_2[1] = pt_C;
4815  tep->edge_3[0] = pt_C;
4816  tep->edge_3[1] = pt_A;
4817  }
4818 
4819  while (BU_LIST_WHILE(tep, tri_edges, &headTep.l)) {
4820  BU_LIST_DEQUEUE(&tep->l);
4821  BU_LIST_APPEND(&usedTep.l, &tep->l);
4822 
4823  rt_bot_sync_func(bot, tep, &headTep, &usedTep);
4824  }
4825 
4826  while (BU_LIST_WHILE(tep, tri_edges, &usedTep.l)) {
4827  BU_LIST_DEQUEUE(&tep->l);
4828  }
4829 
4830  bu_free((void *)alltep, "rt_bot_sync: alltep");
4831 
4832  return 0;
4833 }
4834 
4835 
4836 void
4837 rt_bot_split_func(struct rt_bot_internal *bot,
4838  struct tri_pts *tpp,
4839  struct tri_pts *headTpp,
4840  struct tri_pts *usedTpp)
4841 {
4842  struct tri_pts *neighbor_tpp;
4843  struct tri_pts **stack = (struct tri_pts **)bu_calloc(bot->num_faces, sizeof(struct tri_pts *), "rt_bot_split_func: stack");
4844  register size_t si = 0;
4845  register int not_done = 1;
4846 
4847  while (not_done) {
4848  begin:
4849  for (BU_LIST_FOR(neighbor_tpp, tri_pts, &headTpp->l)) {
4850  if ((tpp->a == neighbor_tpp->a && tpp->b == neighbor_tpp->b) ||
4851  (tpp->a == neighbor_tpp->b && tpp->b == neighbor_tpp->a) ||
4852  (tpp->a == neighbor_tpp->b && tpp->b == neighbor_tpp->c) ||
4853  (tpp->a == neighbor_tpp->c && tpp->b == neighbor_tpp->b) ||
4854  (tpp->a == neighbor_tpp->a && tpp->b == neighbor_tpp->c) ||
4855  (tpp->a == neighbor_tpp->c && tpp->b == neighbor_tpp->a) ||
4856  (tpp->a == neighbor_tpp->a && tpp->c == neighbor_tpp->b) ||
4857  (tpp->a == neighbor_tpp->b && tpp->c == neighbor_tpp->a) ||
4858  (tpp->a == neighbor_tpp->b && tpp->c == neighbor_tpp->c) ||
4859  (tpp->a == neighbor_tpp->c && tpp->c == neighbor_tpp->b) ||
4860  (tpp->a == neighbor_tpp->a && tpp->c == neighbor_tpp->c) ||
4861  (tpp->a == neighbor_tpp->c && tpp->c == neighbor_tpp->a) ||
4862  (tpp->b == neighbor_tpp->a && tpp->c == neighbor_tpp->b) ||
4863  (tpp->b == neighbor_tpp->b && tpp->c == neighbor_tpp->a) ||
4864  (tpp->b == neighbor_tpp->b && tpp->c == neighbor_tpp->c) ||
4865  (tpp->b == neighbor_tpp->c && tpp->c == neighbor_tpp->b) ||
4866  (tpp->b == neighbor_tpp->a && tpp->c == neighbor_tpp->c) ||
4867  (tpp->b == neighbor_tpp->c && tpp->c == neighbor_tpp->a)) {
4868  /* Found a shared edge of a neighboring triangle */
4869 
4870  BU_LIST_DEQUEUE(&neighbor_tpp->l);
4871  BU_LIST_APPEND(&usedTpp->l, &neighbor_tpp->l);
4872 
4873  stack[++si] = tpp;
4874  tpp = neighbor_tpp;
4875  goto begin;
4876  }
4877  }
4878 
4879  if (si < 1)
4880  not_done = 0;
4881  else
4882  tpp = stack[si--];
4883  }
4884 
4885  bu_free((void *)stack, "rt_bot_split_func: stack");
4886 }
4887 
4888 
4889 #define REMAP_BOT_VERTS(_oldbot, _newbot, _vmap, _vcount, _ovi, _i) { \
4890  size_t vmi; \
4891  \
4892  for (vmi = 0; vmi < _vcount; vmi++) { \
4893  if (_ovi == _vmap[vmi]) { \
4894  _newbot->faces[_i] = vmi; \
4895  break; \
4896  } \
4897  } \
4898  \
4899  if (vmi == _vcount) { \
4900  _vmap[_vcount] = _ovi; \
4901  _newbot->faces[_i] = _vcount; \
4902  VMOVE(&_newbot->vertices[_vcount*3], &_oldbot->vertices[_ovi*3]); \
4903  ++_vcount; \
4904  } \
4905  }
4906 
4907 
4908 struct rt_bot_internal *
4909 rt_bot_create(struct rt_bot_internal *bot, struct tri_pts *newTpp)
4910 {
4911  size_t i;
4912  struct tri_pts *tpp;
4913  struct rt_bot_internal *newbot;
4914 
4915  BU_ALLOC(newbot, struct rt_bot_internal);
4916 
4917  newbot->num_faces = 0;
4918  for (BU_LIST_FOR(tpp, tri_pts, &newTpp->l)) {
4919  ++newbot->num_faces;
4920  }
4921 
4922  newbot->magic = bot->magic;
4923  newbot->mode = bot->mode;
4924  newbot->orientation = bot->orientation;
4925  newbot->bot_flags = bot->bot_flags;
4926 
4927  {
4928  size_t vcount;
4929  int *vmap = (int *)bu_calloc(bot->num_vertices * 3, sizeof(int), "Bot vertices");
4930 
4931  newbot->vertices = (fastf_t *)bu_calloc(bot->num_vertices * 3, sizeof(fastf_t), "Bot vertices");
4932  newbot->faces = (int *)bu_calloc(newbot->num_faces * 3, sizeof(int), "Bot faces");
4933  if (bot->mode == RT_BOT_PLATE) {
4934  newbot->thickness = (fastf_t *)bu_calloc(bot->num_faces, sizeof(fastf_t), "Bot thickness");
4935  newbot->face_mode = bu_bitv_new(newbot->num_faces);
4936  }
4937 
4938  i = 0;
4939  vcount = 0;
4940  for (BU_LIST_FOR(tpp, tri_pts, &newTpp->l)) {
4941 
4942  REMAP_BOT_VERTS(bot, newbot, vmap, vcount, tpp->a, i*3);
4943  REMAP_BOT_VERTS(bot, newbot, vmap, vcount, tpp->b, i*3+1);
4944  REMAP_BOT_VERTS(bot, newbot, vmap, vcount, tpp->c, i*3+2);
4945 
4946  if (bot->mode == RT_BOT_PLATE) {
4947  newbot->thickness[i] = bot->thickness[tpp->tri];
4948 
4949  if (BU_BITTEST(bot->face_mode, tpp->tri))
4950  BU_BITSET(newbot->face_mode, i);
4951  /* else already cleared via bu_bitv_new() */
4952  }
4953 
4954  ++i;
4955  }
4956 
4957  newbot->num_vertices = vcount;
4958  bu_free(vmap, "rt_bot_create: vmap");
4959  }
4960 
4961  return newbot;
4962 }
4963 
4964 
4965 struct rt_bot_list *
4966 rt_bot_split(struct rt_bot_internal *bot)
4967 {
4968  size_t i;
4969  size_t first;
4970  struct tri_pts headTp;
4971  struct tri_pts usedTp;
4972  struct tri_pts *tpp;
4973  struct tri_pts *alltpp;
4974  struct rt_bot_list *headRblp = (struct rt_bot_list *)0;
4975  struct rt_bot_list *rblp;
4976 
4977  RT_BOT_CK_MAGIC(bot);
4978 
4979  BU_ALLOC(headRblp, struct rt_bot_list);
4980  BU_LIST_INIT(&headRblp->l);
4981 
4982  /* Nothing to do */
4983  if (bot->num_faces < 2)
4984  return headRblp;
4985 
4986  BU_LIST_INIT(&headTp.l);
4987  BU_LIST_INIT(&usedTp.l);
4988 
4989  alltpp = (struct tri_pts *)bu_calloc(bot->num_faces, sizeof(struct tri_pts), "rt_bot_split: alltpp");
4990 
4991  /* Initialize tpp list */
4992  for (i = 0; i < bot->num_faces; ++i) {
4993  tpp = &alltpp[i];
4994  BU_LIST_APPEND(&headTp.l, &tpp->l);
4995 
4996  tpp->tri = i;
4997  tpp->a = bot->faces[i*3+0];
4998  tpp->b = bot->faces[i*3+1];
4999  tpp->c = bot->faces[i*3+2];
5000  }
5001 
5002  first = 1;
5003  while (BU_LIST_WHILE(tpp, tri_pts, &headTp.l)) {
5004  BU_LIST_DEQUEUE(&tpp->l);
5005  BU_LIST_APPEND(&usedTp.l, &tpp->l);
5006 
5007  rt_bot_split_func(bot, tpp, &headTp, &usedTp);
5008 
5009  if (first) {
5010  first = 0;
5011 
5012  if (BU_LIST_NON_EMPTY(&headTp.l)) {
5013  /* Create a new bot */
5014  BU_ALLOC(rblp, struct rt_bot_list);
5015  rblp->bot = rt_bot_create(bot, &usedTp);
5016  BU_LIST_APPEND(&headRblp->l, &rblp->l);
5017  }
5018  } else {
5019  /* Create a new bot */
5020  BU_ALLOC(rblp, struct rt_bot_list);
5021  rblp->bot = rt_bot_create(bot, &usedTp);
5022  BU_LIST_APPEND(&headRblp->l, &rblp->l);
5023  }
5024 
5025  while (BU_LIST_WHILE(tpp, tri_pts, &usedTp.l)) {
5026  BU_LIST_DEQUEUE(&tpp->l);
5027  }
5028  }
5029 
5030  bu_free((void *)alltpp, "rt_bot_split: alltpp");
5031 
5032  return headRblp;
5033 }
5034 
5035 
5036 struct rt_bot_list *
5037 rt_bot_patches(struct rt_bot_internal *bot)
5038 {
5039  size_t i, j;
5040  struct tri_pts headTp;
5041  struct tri_pts xplus;
5042  struct tri_pts xminus;
5043  struct tri_pts yplus;
5044  struct tri_pts yminus;
5045  struct tri_pts zplus;
5046  struct tri_pts zminus;
5047  struct tri_pts *tpp;
5048  struct tri_pts *alltpp;
5049  struct rt_bot_list *headRblp = (struct rt_bot_list *)0;
5050  struct rt_bot_list *rblp;
5051 
5052  vect_t from_xplus = {-1, 0, 0};
5053  vect_t from_xminus = {1, 0, 0};
5054  vect_t from_yplus = {0, -1, 0};
5055  vect_t from_yminus = {0, 1, 0};
5056  vect_t from_zplus = {0, 0, -1};
5057  vect_t from_zminus = {0, 0, 1};
5058 
5059  RT_BOT_CK_MAGIC(bot);
5060 
5061  BU_ALLOC(headRblp, struct rt_bot_list);
5062  BU_LIST_INIT(&headRblp->l);
5063 
5064  /* Nothing to do */
5065  if (bot->num_faces < 2)
5066  return NULL;
5067 
5068  BU_LIST_INIT(&headTp.l);
5069  BU_LIST_INIT(&xplus.l);
5070  BU_LIST_INIT(&xminus.l);
5071  BU_LIST_INIT(&yplus.l);
5072  BU_LIST_INIT(&yminus.l);
5073  BU_LIST_INIT(&zplus.l);
5074  BU_LIST_INIT(&zminus.l);
5075 
5076  alltpp = (struct tri_pts *)bu_calloc(bot->num_faces, sizeof(struct tri_pts), "patches alltpp");
5077 
5078  for (i = 0; i < bot->num_faces; ++i) {
5079  vect_t a, b, norm_dir;
5080  fastf_t results[6];
5081  int result_max = 0;
5082  fastf_t tmp = 0.0;
5083  VSETALLN(results, 0, 6);
5084 
5085  tpp = &alltpp[i];
5086  tpp->tri = i;
5087  tpp->a = bot->faces[i*3+0];
5088  tpp->b = bot->faces[i*3+1];
5089  tpp->c = bot->faces[i*3+2];
5090 
5091  VSUB2(a, &bot->vertices[bot->faces[i*3+1]*3], &bot->vertices[bot->faces[i*3]*3]);
5092  VSUB2(b, &bot->vertices[bot->faces[i*3+2]*3], &bot->vertices[bot->faces[i*3]*3]);
5093  VCROSS(norm_dir, a, b);
5094  VUNITIZE(norm_dir);
5095  results[0] = VDOT(from_xplus, norm_dir);
5096  results[1] = VDOT(from_xminus, norm_dir);
5097  results[2] = VDOT(from_yplus, norm_dir);
5098  results[3] = VDOT(from_yminus, norm_dir);
5099  results[4] = VDOT(from_zplus, norm_dir);
5100  results[5] = VDOT(from_zminus, norm_dir);
5101 
5102  for (j = 0; j < 6; j++) {
5103  if (results[j] > tmp) {
5104  result_max = j;
5105  tmp = results[j];
5106  }
5107  }
5108 
5109 
5110  if (result_max == 0) {
5111  BU_LIST_APPEND(&xplus.l, &tpp->l);
5112  }
5113  if (result_max == 1) {
5114  BU_LIST_APPEND(&xminus.l, &tpp->l);
5115  }
5116  if (result_max == 2) {
5117  BU_LIST_APPEND(&yplus.l, &tpp->l);
5118  }
5119  if (result_max == 3) {
5120  BU_LIST_APPEND(&yminus.l, &tpp->l);
5121  }
5122  if (result_max == 4) {
5123  BU_LIST_APPEND(&zplus.l, &tpp->l);
5124  }
5125  if (result_max == 5) {
5126  BU_LIST_APPEND(&zminus.l, &tpp->l);
5127  }
5128 
5129  }
5130  if (BU_LIST_NON_EMPTY(&xplus.l)) {
5131  /* Create a new bot */
5132  BU_ALLOC(rblp, struct rt_bot_list);
5133  rblp->bot = rt_bot_create(bot, &xplus);
5134  BU_LIST_APPEND(&headRblp->l, &rblp->l);
5135  }
5136  if (BU_LIST_NON_EMPTY(&xminus.l)) {
5137  /* Create a new bot */
5138  BU_ALLOC(rblp, struct rt_bot_list);
5139  rblp->bot = rt_bot_create(bot, &xminus);
5140  BU_LIST_APPEND(&headRblp->l, &rblp->l);
5141  }
5142  if (BU_LIST_NON_EMPTY(&yplus.l)) {
5143  /* Create a new bot */
5144  BU_ALLOC(rblp, struct rt_bot_list);
5145  rblp->bot = rt_bot_create(bot, &yplus);
5146  BU_LIST_APPEND(&headRblp->l, &rblp->l);
5147  }
5148  if (BU_LIST_NON_EMPTY(&yminus.l)) {
5149  /* Create a new bot */
5150  BU_ALLOC(rblp, struct rt_bot_list);
5151  rblp->bot = rt_bot_create(bot, &yminus);
5152  BU_LIST_APPEND(&headRblp->l, &rblp->l);
5153  }
5154  if (BU_LIST_NON_EMPTY(&zplus.l)) {
5155  /* Create a new bot */
5156  BU_ALLOC(rblp, struct rt_bot_list);
5157  rblp->bot = rt_bot_create(bot, &zplus);
5158  BU_LIST_APPEND(&headRblp->l, &rblp->l);
5159  }
5160  if (BU_LIST_NON_EMPTY(&zminus.l)) {
5161  /* Create a new bot */
5162  BU_ALLOC(rblp, struct rt_bot_list);
5163  rblp->bot = rt_bot_create(bot, &zminus);
5164  BU_LIST_APPEND(&headRblp->l, &rblp->l);
5165  }
5166 
5167  while (BU_LIST_WHILE(tpp, tri_pts, &xplus.l)) {
5168  BU_LIST_DEQUEUE(&tpp->l);
5169  }
5170 
5171  while (BU_LIST_WHILE(tpp, tri_pts, &xminus.l)) {
5172  BU_LIST_DEQUEUE(&tpp->l);
5173  }
5174 
5175  while (BU_LIST_WHILE(tpp, tri_pts, &yplus.l)) {
5176  BU_LIST_DEQUEUE(&tpp->l);
5177  }
5178 
5179  while (BU_LIST_WHILE(tpp, tri_pts, &yminus.l)) {
5180  BU_LIST_DEQUEUE(&tpp->l);
5181  }
5182 
5183 
5184  while (BU_LIST_WHILE(tpp, tri_pts, &zplus.l)) {
5185  BU_LIST_DEQUEUE(&tpp->l);
5186  }
5187 
5188 
5189  while (BU_LIST_WHILE(tpp, tri_pts, &zminus.l)) {
5190  BU_LIST_DEQUEUE(&tpp->l);
5191  }
5192 
5193  bu_free((void *)alltpp, "rt_bot_patches: alltpp");
5194 
5195  return headRblp;
5196 }
5197 
5198 
5199 void
5200 rt_bot_list_free(struct rt_bot_list *headRblp, int fbflag)
5201 {
5202  struct rt_bot_list *rblp;
5203 
5204  while (BU_LIST_WHILE(rblp, rt_bot_list, &headRblp->l)) {
5205  /* Remove from list and free */
5206  BU_LIST_DEQUEUE(&rblp->l);
5207 
5208  if (fbflag)
5209  bot_ifree2(rblp->bot);
5210 
5211  bu_free(rblp, "rt_bot_list_free: rblp");
5212  }
5213 
5214  bu_free(headRblp, "rt_bot_list_free: headRblp");
5215 }
5216 
5217 
5218 void
5219 rt_bot_volume(fastf_t *volume, const struct rt_db_internal *ip)
5220 {
5221  /* contains information used to analyze a polygonal face */
5222  struct poly_face
5223  {
5224  char label[5];
5225  size_t npts;
5226  point_t *pts;
5227  plane_t plane_eqn;
5228  fastf_t area;
5229  };
5230  size_t i;
5231  struct poly_face face = { { 0, 0, 0, 0, 0 }, 0, NULL, HINIT_ZERO, 0.0 };
5232  struct rt_bot_internal *bot = (struct rt_bot_internal *)ip->idb_ptr;
5233  struct bn_tol tol;
5234  RT_BOT_CK_MAGIC(bot);
5235 
5236  *volume = 0.0;
5237  if (bot->mode == RT_BOT_SURFACE)
5238  return;
5239 
5240  /* allocate pts array, 3 vertices per bot face */
5241  face.pts = (point_t *)bu_calloc(3, sizeof(point_t), "rt_bot_volume: pts");
5242  BN_TOL_INIT(&tol);
5243  tol.dist_sq = BN_TOL_DIST * BN_TOL_DIST;
5244 
5245 
5246  for (face.npts = 0, i = 0; i < bot->num_faces; face.npts = 0, i++) {
5247  int a, b, c;
5248  vect_t tmp;
5249 
5250 
5251  /* find indices of the 3 vertices that make up this face */
5252  a = bot->faces[i * ELEMENTS_PER_POINT + 0];
5253  b = bot->faces[i * ELEMENTS_PER_POINT + 1];
5254  c = bot->faces[i * ELEMENTS_PER_POINT + 2];
5255 
5256  /* find normal, needed to calculate volume later */
5257  if (bot->bot_flags == RT_BOT_HAS_SURFACE_NORMALS && bot->normals) {
5258  /* bot->normals array already exists, use those instead */
5259  VMOVE(face.plane_eqn, &bot->normals[i * ELEMENTS_PER_VECT]);
5260  } else if (UNLIKELY(bn_mk_plane_3pts(face.plane_eqn, (&bot->vertices[(a) * ELEMENTS_PER_POINT]), (&bot->vertices[(b) * ELEMENTS_PER_POINT]), (&bot->vertices[(c) * ELEMENTS_PER_POINT]), &tol) < 0)) {
5261  continue;
5262  }
5263 
5264  VMOVE((face).pts[(face).npts], (&bot->vertices[(a) * ELEMENTS_PER_POINT])); (face).npts++;
5265  VMOVE((face).pts[(face).npts], (&bot->vertices[(b) * ELEMENTS_PER_POINT])); (face).npts++;
5266  VMOVE((face).pts[(face).npts], (&bot->vertices[(c) * ELEMENTS_PER_POINT])); (face).npts++;
5267 
5268  /* SURFACE AREA */
5269 
5270  /* sort points */
5271  bn_polygon_sort_ccw(face.npts, face.pts, face.plane_eqn);
5272  bn_polygon_area(&face.area, face.npts, (const point_t *)face.pts);
5273 
5274  /* VOLUME */
5275  VSCALE(tmp, face.plane_eqn, face.area);
5276  *volume += fabs(VDOT(face.pts[0], tmp));
5277  if (bot->mode == RT_BOT_PLATE || bot->mode == RT_BOT_PLATE_NOCOS) {
5278  if (BU_BITTEST(bot->face_mode, i))
5279  *volume += face.area * bot->thickness[i];
5280  else
5281  *volume += face.area * 0.5 * bot->thickness[i];
5282  }
5283  }
5284  *volume /= 3.0;
5285  bu_free((char *)face.pts, "rt_bot_volume: pts");
5286 }
5287 
5288 void
5289 rt_bot_surf_area(fastf_t *area, const struct rt_db_internal *ip)
5290 {
5291  typedef point_t triangle[3];
5292  struct rt_bot_internal *bot_ip =
5293  (struct rt_bot_internal *)ip->idb_ptr;
5294  size_t a, b, j;
5295  triangle *whole_bot_vertices = (triangle *)bu_calloc(bot_ip->num_faces, sizeof(triangle), "rt_bot_surf_area: whole_bot_vertices"); /* [face][corner][x,y,z] */
5296  fastf_t whole_bot_overall_area;
5297 
5298  whole_bot_overall_area = 0;
5299 
5300  for (a = 0; a < bot_ip->num_faces; a++) {
5301  point_t pt[3];
5302 
5303  for (j = 0; j < 3; j++) {
5304  size_t ptnum;
5305  ptnum = bot_ip->faces[a*3+j];
5306  VSCALE(pt[j], &bot_ip->vertices[ptnum*3], 1);
5307  /* transfer the vertices into an array, which is structured after the faces, which is necessary for later comparisons, if the bot is a plate */
5308  switch (bot_ip->mode) {
5309  case RT_BOT_PLATE:
5310  case RT_BOT_PLATE_NOCOS:
5311  whole_bot_vertices[a][j][0] = pt[j][X];
5312  whole_bot_vertices[a][j][1] = pt[j][Y];
5313  whole_bot_vertices[a][j][2] = pt[j][Z];
5314  break;
5315  }
5316  }
5317 
5318  whole_bot_overall_area += bn_area_of_triangle((const fastf_t *)&pt[0], (const fastf_t *)&pt[1], (const fastf_t *)&pt[2]);
5319  }
5320 
5321  switch (bot_ip->mode) {
5322  case RT_BOT_PLATE:
5323  case RT_BOT_PLATE_NOCOS:
5324  for (a = 0; a-1 < bot_ip->num_faces; a++) {
5325  int a_is_exterior_edge, b_is_exterior_edge, c_is_exterior_edge;
5326  a_is_exterior_edge = 1;
5327  b_is_exterior_edge = 1;
5328  c_is_exterior_edge = 1;
5329  /* get exterior edges by checking each possible combination between the faces a and b */
5330  for (b = 0; b < bot_ip->num_faces; b++) {
5331  if (a == b)
5332  continue; /* can't check against own face */
5333  /* if both vertices are equal, a and b have a common edge, so it can't be an exterior edge, so the variable is set to 0(false) */
5334  if (EQUAL(whole_bot_vertices[a][0], whole_bot_vertices[b][0]) && EQUAL(whole_bot_vertices[a][1], whole_bot_vertices[b][1]))
5335  a_is_exterior_edge = 0;
5336  else if (EQUAL(whole_bot_vertices[a][0], whole_bot_vertices[b][1]) && EQUAL(whole_bot_vertices[a][1], whole_bot_vertices[b][2]))
5337  a_is_exterior_edge = 0;
5338  else if (EQUAL(whole_bot_vertices[a][0], whole_bot_vertices[b][2]) && EQUAL(whole_bot_vertices[a][1], whole_bot_vertices[b][0]))
5339  a_is_exterior_edge = 0;
5340  else if (EQUAL(whole_bot_vertices[a][0], whole_bot_vertices[b][1]) && EQUAL(whole_bot_vertices[a][1], whole_bot_vertices[b][0]))
5341  a_is_exterior_edge = 0;
5342  else if (EQUAL(whole_bot_vertices[a][0], whole_bot_vertices[b][2]) && EQUAL(whole_bot_vertices[a][1], whole_bot_vertices[b][1]))
5343  a_is_exterior_edge = 0;
5344  else if (EQUAL(whole_bot_vertices[a][0], whole_bot_vertices[b][0]) && EQUAL(whole_bot_vertices[a][1], whole_bot_vertices[b][2]))
5345  a_is_exterior_edge = 0;
5346  if (EQUAL(whole_bot_vertices[a][1], whole_bot_vertices[b][0]) && EQUAL(whole_bot_vertices[a][2], whole_bot_vertices[b][1]))
5347  b_is_exterior_edge = 0;
5348  else if (EQUAL(whole_bot_vertices[a][1], whole_bot_vertices[b][1]) && EQUAL(whole_bot_vertices[a][2], whole_bot_vertices[b][2]))
5349  b_is_exterior_edge = 0;
5350  else if (EQUAL(whole_bot_vertices[a][1], whole_bot_vertices[b][2]) && EQUAL(whole_bot_vertices[a][2], whole_bot_vertices[b][0]))
5351  b_is_exterior_edge = 0;
5352  else if (EQUAL(whole_bot_vertices[a][1], whole_bot_vertices[b][1]) && EQUAL(whole_bot_vertices[a][2], whole_bot_vertices[b][0]))
5353  b_is_exterior_edge = 0;
5354  else if (EQUAL(whole_bot_vertices[a][1], whole_bot_vertices[b][2]) && EQUAL(whole_bot_vertices[a][2], whole_bot_vertices[b][1]))
5355  b_is_exterior_edge = 0;
5356  else if (EQUAL(whole_bot_vertices[a][1], whole_bot_vertices[b][0]) && EQUAL(whole_bot_vertices[a][2], whole_bot_vertices[b][2]))
5357  b_is_exterior_edge = 0;
5358  if (EQUAL(whole_bot_vertices[a][0], whole_bot_vertices[b][0]) && EQUAL(whole_bot_vertices[a][2], whole_bot_vertices[b][1]))
5359  c_is_exterior_edge = 0;
5360  else if (EQUAL(whole_bot_vertices[a][0], whole_bot_vertices[b][1]) && EQUAL(whole_bot_vertices[a][2], whole_bot_vertices[b][2]))
5361  c_is_exterior_edge = 0;
5362  else if (EQUAL(whole_bot_vertices[a][0], whole_bot_vertices[b][2]) && EQUAL(whole_bot_vertices[a][2], whole_bot_vertices[b][0]))
5363  c_is_exterior_edge = 0;
5364  else if (EQUAL(whole_bot_vertices[a][0], whole_bot_vertices[b][1]) && EQUAL(whole_bot_vertices[a][2], whole_bot_vertices[b][0]))
5365  c_is_exterior_edge = 0;
5366  else if (EQUAL(whole_bot_vertices[a][0], whole_bot_vertices[b][2]) && EQUAL(whole_bot_vertices[a][2], whole_bot_vertices[b][1]))
5367  c_is_exterior_edge = 0;
5368  else if (EQUAL(whole_bot_vertices[a][0], whole_bot_vertices[b][0]) && EQUAL(whole_bot_vertices[a][2], whole_bot_vertices[b][2]))
5369  c_is_exterior_edge = 0;
5370 
5371  }
5372  if (a_is_exterior_edge == 1) {
5373  fastf_t rectangle_size, edge_length;
5374 
5375  edge_length = bn_dist_pt3_pt3(whole_bot_vertices[a][0], whole_bot_vertices[a][1]);
5376  rectangle_size = bot_ip->thickness[a] * edge_length;
5377  whole_bot_overall_area += rectangle_size;
5378 
5379  }
5380  if (b_is_exterior_edge == 1) {
5381  fastf_t rectangle_size, edge_length;
5382 
5383  edge_length = bn_dist_pt3_pt3(whole_bot_vertices[a][1], whole_bot_vertices[a][2]);
5384  rectangle_size = bot_ip->thickness[a] * edge_length;
5385  whole_bot_overall_area += rectangle_size;
5386  }
5387  if (c_is_exterior_edge == 1) {
5388  fastf_t rectangle_size, edge_length;
5389 
5390  edge_length = bn_dist_pt3_pt3(whole_bot_vertices[a][2], whole_bot_vertices[a][0]);
5391  rectangle_size = bot_ip->thickness[a] * edge_length;
5392  whole_bot_overall_area += rectangle_size;
5393  }
5394  }
5395 
5396  }
5397  *area = whole_bot_overall_area;
5398  bu_free((char *)whole_bot_vertices, "rt_bot_surf_area: whole_bot_vertices");
5399  return;
5400 }
5401 
5402 /** @} */
5403 /*
5404  * Local Variables:
5405  * mode: C
5406  * tab-width: 8
5407  * indent-tabs-mode: t
5408  * c-file-style: "stroustrup"
5409  * End:
5410  * ex: shiftwidth=4 tabstop=8
5411  */
void nmg_fix_normals(struct shell *s_orig, const struct bn_tol *tol)
Definition: nmg_misc.c:3505
void rt_bot_volume(fastf_t *volume, const struct rt_db_internal *ip)
Definition: bot.c:5219
struct xray a_ray
Actual ray to be shot.
Definition: raytrace.h:1583
#define BN_TOL_INIT(_p)
Definition: tol.h:87
#define BU_LIST_FOR(p, structure, hp)
Definition: list.h:365
Definition: raytrace.h:800
#define RT_CK_FUNCTAB(_p)
Definition: raytrace.h:2242
double bn_area_of_triangle(const point_t a, const point_t b, const point_t c)
Returns the area of a triangle. Algorithm by Jon Leech 3/24/89.
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
#define SIZEOF_NETWORK_DOUBLE
Definition: cv.h:48
struct hit * pt_outhit
OUT hit ptr.
Definition: raytrace.h:579
#define BU_AVS_MAGIC
Definition: magic.h:46
void rt_bot_free(struct soltab *stp)
Definition: bot.c:466
struct rt_bot_list * rt_bot_patches(struct rt_bot_internal *bot)
Definition: bot.c:5037
size_t edge_1[2]
Definition: bot.c:4664
size_t edge_3[2]
Definition: bot.c:4666
HIDDEN int rt_bot_plate_segs(struct hit *hits, size_t nhits, struct soltab *stp, struct xray *rp, struct application *ap, struct seg *seghead, struct bot_specific *bot)
Definition: bot.c:282
Definition: list.h:118
struct bu_bitv * bu_bitv_new(size_t nbits)
Definition: bitv.c:91
point_t mdl_min
min corner of model bounding RPP
Definition: raytrace.h:1769
#define RT_BOT_INTERNAL_MAGIC
Definition: magic.h:85
int rt_bot_prep(struct soltab *stp, struct rt_db_internal *ip, struct rt_i *rtip)
Definition: bot.c:249
void rt_bot_split_func(struct rt_bot_internal *bot, struct tri_pts *tpp, struct tri_pts *headTpp, struct tri_pts *usedTpp)
Definition: bot.c:4837
int nmg_kfu(struct faceuse *fu1)
Definition: nmg_mk.c:1207
#define RT_CK_APPLICATION(_p)
Definition: raytrace.h:1675
#define RT_CK_PIECELIST(_p)
Definition: raytrace.h:1410
HIDDEN int edge_can_be_decimated(struct rt_bot_internal *bot, int *faces, struct bot_edge **edges, int v1, int v2, int *face_del1, int *face_del2, fastf_t max_chord_error, fastf_t max_normal_error, fastf_t min_edge_length_sq)
Definition: bot.c:4088
int rt_bot_bbox(struct rt_db_internal *ip, point_t *min, point_t *max)
Definition: bot.c:193
int bottie_shot_double(struct soltab *stp, struct xray *rp, struct application *ap, struct seg *seghead)
Definition: btg.c:195
double dmin
Definition: bot.c:537
double dist
>= 0
Definition: tol.h:73
fastf_t point_spacing
Definition: bot.c:540
size_t rt_bot_get_edge_list(const struct rt_bot_internal *bot, size_t **edge_list)
Definition: bot.c:1645
vect_t crv_pdir
Principle direction.
Definition: raytrace.h:307
const mat_t bn_mat_identity
Matrix and vector functionality.
Definition: mat.c:46
struct bu_list l
Definition: bot.c:4672
void rt_free_rti(struct rt_i *rtip)
Definition: prep.c:156
struct soltab * seg_stp
pointer back to soltab
Definition: raytrace.h:372
if lu s
Definition: nmg_mod.c:3860
int rt_bot_decimate(struct rt_bot_internal *bot, fastf_t max_chord_error, fastf_t max_normal_error, fastf_t min_edge_length)
Definition: bot.c:4267
void rt_bot_surf_area(fastf_t *area, const struct rt_db_internal *ip)
Definition: bot.c:5289
void bu_vls_strcat(struct bu_vls *vp, const char *s)
Definition: vls.c:368
#define VSET(a, b, c, d)
Definition: color.c:53
#define VSETALL(a, s)
Definition: color.c:54
Definition: raytrace.h:215
void bu_avs_merge(struct bu_attribute_value_set *dest, const struct bu_attribute_value_set *src)
Definition: avs.c:154
#define ID_BOT
Bag o' triangles.
Definition: raytrace.h:488
#define SIZEOF_NETWORK_LONG
Definition: cv.h:46
#define M_PI
Definition: fft.h:35
Definition: pc.h:108
double dist_sq
dist * dist
Definition: tol.h:74
void rt_hitsort(struct hit h[], int nh)
Definition: raytrace.h:368
#define MAX_AFFECTED_FACES
Definition: bot.c:4061
#define BU_ASSERT_LONG(_lhs, _relation, _rhs)
Definition: defines.h:240
int rt_bot_makesegs(struct hit *hits, size_t nhits, struct soltab *stp, struct xray *rp, struct application *ap, struct seg *seghead, struct rt_piecestate *psp)
Definition: bot.c:320
size_t edge_2[2]
Definition: bot.c:4665
int rt_bot_find_e_nearest_pt2(int *vert1, int *vert2, const struct rt_bot_internal *bot, const point_t pt2, const mat_t mat)
Definition: bot.c:1709
Definition: raytrace.h:248
void nmg_vertex_gv(struct vertex *v, const fastf_t *pt)
Definition: nmg_mk.c:1668
#define BN_TOL_MAGIC
Definition: magic.h:74
#define SMALL_FASTF
Definition: defines.h:342
HIDDEN void delete_edge(int v1, int v2, struct bot_edge **edges)
Definition: bot.c:3828
struct bu_list l
Definition: bot.c:4663
char pt_inflip
flip inhit->hit_normal
Definition: raytrace.h:581
Header file for the BRL-CAD common definitions.
ustring closest
struct seg * pt_outseg
OUT seg pointer.
Definition: raytrace.h:578
int rt_bot_sync(struct rt_bot_internal *bot)
Definition: bot.c:4781
#define BU_LIST_APPEND(old, new)
Definition: list.h:197
int bottie_prep_double(struct soltab *stp, struct rt_bot_internal *bot_ip, struct rt_i *rtip)
Definition: btg.c:63
size_t use_count
Definition: bot.c:2767
int rt_bot_adjust(struct bu_vls *logstr, struct rt_db_internal *intern, int argc, const char **argv)
Definition: bot.c:2150
int rt_bot_find_v_nearest_pt2(const struct rt_bot_internal *bot, const point_t pt2, const mat_t mat)
Definition: bot.c:1614
char pt_outflip
flip outhit->hit_normal
Definition: raytrace.h:582
struct soltab * stp
Definition: raytrace.h:1380
int rt_in_rpp(struct xray *rp, const fastf_t *invdir, const fastf_t *min, const fastf_t *max)
void bu_cv_htond(unsigned char *out, const unsigned char *in, size_t count)
#define BU_LIST_NON_EMPTY(hp)
Definition: list.h:296
int rt_bot_class(const struct soltab *stp, const fastf_t *min, const fastf_t *max, const struct bn_tol *tol)
Definition: bot.c:485
#define MAX_FASTF
Definition: defines.h:340
float minEdge(struct rt_bot_internal *bot)
Definition: bot.c:2869
int tri
Definition: bot.c:4676
int(* a_hit)(struct application *, struct partition *, struct seg *)
called when shot hits model
Definition: raytrace.h:1584
struct hit * pt_inhit
IN hit pointer.
Definition: raytrace.h:577
#define HIDDEN
Definition: common.h:86
int nmg_calc_face_g(struct faceuse *fu)
Definition: nmg_misc.c:1786
#define BU_BITSET(_bv, bit)
Definition: bitv.h:183
int rt_bot_import5(struct rt_db_internal *ip, const struct bu_external *ep, const fastf_t *mat, const struct db_i *dbip)
Definition: bot.c:1067
void * bu_malloc(size_t siz, const char *str)
Definition: malloc.c:314
#define BN_VLIST_TRI_VERTNORM
per-vertex normal, for interpolation
Definition: vlist.h:93
int rt_bot_flip(struct rt_bot_internal *bot)
Definition: bot.c:4632
Definition: bot.c:4671
void rt_bot_curve(struct curvature *cvp, struct hit *hitp, struct soltab *stp)
Definition: bot.c:436
struct rt_bot_list * rt_bot_split(struct rt_bot_internal *bot)
Definition: bot.c:4966
void bottie_free_double(void *vtie)
Definition: btg.c:236
if(share_geom)
Definition: nmg_mod.c:3829
int idb_major_type
Definition: raytrace.h:192
int rt_bot_vertex_fuse(struct rt_bot_internal *bot, const struct bn_tol *tol)
Definition: bot.c:3060
void bu_vls_free(struct bu_vls *vp)
Definition: vls.c:248
int bu_strncmp(const char *string1, const char *string2, size_t n)
Definition: str.c:191
Definition: color.c:49
struct rt_i * a_rt_i
this librt instance
Definition: raytrace.h:1588
int rt_bot_condense(struct rt_bot_internal *bot)
Definition: bot.c:3392
int rt_bot_plot_poly(struct bu_list *vhead, struct rt_db_internal *ip, const struct rt_tess_tol *ttol, const struct bn_tol *tol)
Definition: bot.c:681
void * memset(void *s, int c, size_t n)
void rt_bot_centroid(point_t *cent, const struct rt_db_internal *ip)
Definition: bot.c:740
int rt_bot_import4(struct rt_db_internal *ip, const struct bu_external *ep, const fastf_t *mat, const struct db_i *dbip)
Definition: bot.c:892
void rt_bot_list_free(struct rt_bot_list *headRblp, int fbflag)
Definition: bot.c:5200
#define BU_BITTEST(_bv, bit)
Definition: bitv.h:168
struct bu_list * vhead
Definition: raytrace.h:1926
#define RT_ADD_VLIST(hd, pnt, draw)
Definition: raytrace.h:1865
int rt_bot_shot(struct soltab *stp, struct xray *rp, struct application *ap, struct seg *seghead)
Definition: bot.c:350
#define RT_CK_DB_INTERNAL(_p)
Definition: raytrace.h:207
size_t rt_botface(struct soltab *stp, struct bot_specific *bot, fastf_t *ap, fastf_t *bp, fastf_t *cp, size_t face_no, const struct bn_tol *tol)
Definition: bot.c:160
int bn_dist_pt2_lseg2(fastf_t *dist_sq, fastf_t pca[2], const point_t a, const point_t b, const point_t p, const struct bn_tol *tol)
Find the distance from a point P to a line segment described by the two endpoints A and B...
#define BU_ALLOC(_ptr, _type)
Definition: malloc.h:223
void * bu_calloc(size_t nelem, size_t elsize, const char *str)
Definition: malloc.c:321
fastf_t crv_c2
curvature in other direction
Definition: raytrace.h:309
int rt_bot_sort_faces(struct rt_bot_internal *bot, size_t tris_per_piece)
Definition: bot.c:3531
#define RT_CK_HIT(_p)
Definition: raytrace.h:259
struct rt_htbl htab
accumulating hits here
Definition: raytrace.h:1384
#define RT_DB_INTERNAL_INIT(_p)
Definition: raytrace.h:199
#define BN_VLIST_LINE_MOVE
Definition: vlist.h:82
#define BU_BITCLR(_bv, bit)
Definition: bitv.h:185
const struct rt_functab * idb_meth
for ft_ifree(), etc.
Definition: raytrace.h:194
#define RT_CK_AP(_p)
Definition: raytrace.h:1674
#define bu_strlcpy(dst, src, size)
Definition: str.h:60
int a_user
application-specific value
Definition: raytrace.h:1617
#define V3ARGS(a)
Definition: color.c:56
#define BRLCAD_OK
Definition: defines.h:71
unsigned char * bp
Definition: rot.c:56
int rt_bot_describe(struct bu_vls *str, const struct rt_db_internal *ip, int verbose, double mm2local)
Definition: bot.c:1358
uint8_t * ext_buf
Definition: parse.h:216
struct seg * pt_inseg
IN seg ptr (gives stp)
Definition: raytrace.h:576
void rt_bot_piece_hitsegs(struct rt_piecestate *psp, struct seg *seghead, struct application *ap)
Definition: bot.c:402
point_t st_max
max X, Y, Z of bounding RPP
Definition: raytrace.h:438
#define SQRT_SMALL_FASTF
Definition: defines.h:346
HIDDEN void bot_ifree2(struct rt_bot_internal *bot_ip)
Definition: bot.c:1478
#define RT_BOT_TESS_MAX_FACES
int rt_bot_tess(struct nmgregion **r, struct model *m, struct rt_db_internal *ip, const struct rt_tess_tol *ttol, const struct bn_tol *tol)
Definition: bot.c:761
#define BN_VLIST_LINE_DRAW
Definition: vlist.h:83
struct bu_attribute_value_set idb_avs
Definition: raytrace.h:196
#define BN_TOL_DIST
Definition: tol.h:109
size_t bu_vls_strlen(const struct bu_vls *vp)
Definition: vls.c:189
int rt_bot_edge_in_list(const size_t v1, const size_t v2, const size_t edge_list[], const size_t edge_count)
Definition: bot.c:1683
void * bu_realloc(void *ptr, size_t siz, const char *str)
point_t * pts
Definition: arbn.c:1285
char * bu_next_token(char *str)
Definition: parse.c:2469
#define UNUSED(parameter)
Definition: common.h:239
int bn_polygon_area(fastf_t *area, size_t npts, const point_t *pts)
Functions for working with polygons.
Definition: polygon.c:28
int nmg_mark_edges_real(const uint32_t *magic_p)
Definition: nmg_misc.c:846
uint32_t magic
Definition: avs.h:84
Support for uniform tolerances.
Definition: tol.h:71
void bu_avs_init(struct bu_attribute_value_set *avp, size_t len, const char *str)
Definition: avs.c:47
#define BN_CK_TOL(_p)
Definition: tol.h:82
char * bu_vls_addr(const struct bu_vls *vp)
Definition: vls.c:111
struct bu_bitv * bu_bitv_dup(const struct bu_bitv *bv)
#define BN_VLIST_TRI_END
last vert (repeats 1st), draw poly
Definition: vlist.h:92
#define BU_LIST_WHILE(p, structure, hp)
Definition: list.h:410
size_t npts
Definition: arbn.c:1284
fastf_t rt_bot_propget(struct rt_bot_internal *bot, const char *property)
Definition: bot.c:3015
struct nmgregion * nmg_mrsv(struct model *m)
Definition: nmg_mk.c:306
HIDDEN int bot_smooth_miss(struct application *ap)
Definition: bot.c:4414
HIDDEN int bot_smooth_hit(struct application *ap, struct partition *PartHeadp, struct seg *seg)
Definition: bot.c:4422
vect_t r_dir
Direction of ray (UNIT Length)
Definition: raytrace.h:219
void rt_bot_sync_func(struct rt_bot_internal *bot, struct tri_edges *tep, struct tri_edges *headTep, struct tri_edges *usedTep)
Definition: bot.c:4681
struct rt_i * rt_new_rti(struct db_i *dbip)
Definition: prep.c:58
int rt_gettree(struct rt_i *rtip, const char *node)
Definition: tree.c:869
#define RT_CK_DBI(_p)
Definition: raytrace.h:829
int b
Definition: bot.c:4674
#define BN_VLIST_TRI_START
pt[] has surface normal
Definition: vlist.h:89
void bu_bitv_to_hex(struct bu_vls *v, const struct bu_bitv *bv)
Definition: bitv.c:222
int rt_bot_face_fuse(struct rt_bot_internal *bot)
Definition: bot.c:3283
int rt_bot_xform(struct rt_db_internal *op, const fastf_t *mat, struct rt_db_internal *ip, const int release, struct db_i *dbip)
Definition: bot.c:1539
fastf_t point_spacing
Definition: raytrace.h:1934
double perp
nearly 0
Definition: tol.h:75
fastf_t r_min
entry dist to bounding sphere
Definition: raytrace.h:220
int a
Definition: bot.c:4673
char label[5]
Definition: arbn.c:1283
#define ZERO(val)
Definition: units.c:38
size_t end
index of first available location
Definition: raytrace.h:1363
#define BU_LIST_INIT(_hp)
Definition: list.h:148
void * idb_ptr
Definition: raytrace.h:195
vdsNode * build_vertex_tree(struct rt_bot_internal *bot)
Definition: bot.c:497
double bn_dist_pt3_pt3(const point_t a, const point_t b)
Returns distance between two points.
point_t r_pt
Point at which ray starts.
Definition: raytrace.h:218
point_t st_min
min X, Y, Z of bounding RPP
Definition: raytrace.h:437
plane_t plane_eqn
Definition: arbn.c:1286
int c
Definition: bot.c:4675
void bu_cv_ntohd(unsigned char *out, const unsigned char *in, size_t count)
uint32_t magic
Definition: tol.h:72
vdsNode * root
Definition: bot.c:539
const struct rt_functab OBJ[]
Definition: table.c:159
#define REMAP_BOT_VERTS(_oldbot, _newbot, _vmap, _vcount, _ovi, _i)
Definition: bot.c:4889
int rt_bot_adaptive_plot(struct rt_db_internal *ip, const struct rt_view_info *info)
Definition: bot.c:613
int bn_3pts_collinear(point_t a, point_t b, point_t c, const struct bn_tol *tol)
Check to see if three points are collinear.
void bn_vec_ortho(vect_t out, const vect_t in)
#define RT_DEFAULT_MINTIE
Definition: raytrace.h:1415
HIDDEN fastf_t bin(fastf_t val, fastf_t step)
Definition: nmg_tri_mc.c:461
point_t mdl_max
max corner of model bounding RPP
Definition: raytrace.h:1770
int rt_bot_get(struct bu_vls *logstr, const struct rt_db_internal *intern, const char *attr)
Definition: bot.c:1853
void rt_prep(struct rt_i *rtip)
#define RT_CK_SOLTAB(_p)
Definition: raytrace.h:453
void bu_vls_printf(struct bu_vls *vls, const char *fmt,...) _BU_ATTR_PRINTF23
Definition: vls.c:694
int rt_bot_export5(struct bu_external *ep, const struct rt_db_internal *ip, double local2mm, const struct db_i *dbip)
Definition: bot.c:1197
int bot_check_vertex_indices(struct bu_vls *logstr, struct rt_bot_internal *bot)
Definition: bot.c:2112
void * st_specific
-> ID-specific (private) struct
Definition: raytrace.h:435
void rt_bot_prep_pieces(struct bot_specific *bot, struct soltab *stp, size_t ntri, const struct bn_tol *tol)
Definition: bot.c:176
int bn_3pts_distinct(const point_t a, const point_t b, const point_t c, const struct bn_tol *tol)
#define BN_VLIST_TRI_DRAW
subsequent triangle vertex
Definition: vlist.h:91
fastf_t crv_c1
curvature in principle dir
Definition: raytrace.h:308
void rt_bot_norm(struct hit *hitp, struct soltab *stp, struct xray *rp)
Definition: bot.c:420
Definition: color.c:51
int rt_bot_export4(struct bu_external *ep, const struct rt_db_internal *ip, double local2mm, const struct db_i *dbip)
Definition: bot.c:969
int rt_shootray(struct application *ap)
void * a_uptr
application-specific pointer
Definition: raytrace.h:1618
void bu_vls_strcpy(struct bu_vls *vp, const char *s)
Definition: vls.c:310
#define RT_CK_PIECESTATE(_p)
Definition: raytrace.h:1387
int hit_surfno
solid-specific surface indicator
Definition: raytrace.h:255
struct hit * hits
hits[blen] data storage area
Definition: raytrace.h:1365
struct rt_bot_internal * rt_bot_create(struct rt_bot_internal *bot, struct tri_pts *newTpp)
Definition: bot.c:4909
int rt_bot_piece_shot(struct rt_piecestate *psp, struct rt_piecelist *plp, double dist_corr, struct xray *rp, struct application *ap, struct seg *seghead)
Definition: bot.c:383
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
struct bot_edge * next
Definition: bot.c:2768
vect_t hit_normal
DEPRECATED: Surface Normal at hit_point, use RT_HIT_NORMAL.
Definition: raytrace.h:252
#define BU_CK_LIST_HEAD(_p)
Definition: list.h:142
int buildEdgeTable(struct rt_bot_internal *bot, struct bot_edge ***edges)
Definition: bot.c:2779
#define BU_CK_EXTERNAL(_p)
Definition: parse.h:224
int(* a_miss)(struct application *)
called when shot misses
Definition: raytrace.h:1585
struct faceuse * nmg_cmface(struct shell *s, struct vertex ***verts, int n)
Definition: nmg_mod.c:979
#define BU_VLS_INIT_ZERO
Definition: vls.h:84
#define RT_HIT_NORMAL(_normal, _hitp, _stp, _unused, _flipflag)
Definition: raytrace.h:273
struct soltab * stp
ref back to solid
Definition: raytrace.h:1408
size_t tri
Definition: bot.c:4667
int bn_pt3_pt3_equal(const point_t a, const point_t b, const struct bn_tol *tol)
double dmax
Definition: bot.c:538
#define BU_LIST_DEQUEUE(cur)
Definition: list.h:209
HIDDEN int decimate_edge(int v1, int v2, struct bot_edge **edges, size_t num_edges, int *faces, size_t num_faces, int face_del1, int face_del2)
Definition: bot.c:3883
size_t ext_nbytes
Definition: parse.h:210
int rt_bot_smooth(struct rt_bot_internal *bot, const char *bot_name, struct db_i *dbip, fastf_t norm_tol_angle)
Definition: bot.c:4450
Definition: bitv.h:105
bn_poly_t rem[1]
struct partition * pt_forw
forwards link
Definition: raytrace.h:574
void rt_bot_ifree(struct rt_db_internal *ip)
Definition: bot.c:1526
#define RT_APPLICATION_INIT(_p)
Definition: raytrace.h:1676
HIDDEN void verbose(struct human_data_t *dude)
Definition: human.c:2008
void Add_unique_verts(int *piece_verts, int *v)
Definition: bot.c:3505
int rt_bot_form(struct bu_vls *logstr, const struct rt_functab *ftp)
Definition: bot.c:273