BRL-CAD
shape_recognition.cpp
Go to the documentation of this file.
1 #include "common.h"
2 
3 #include <set>
4 #include <map>
5 
6 #include "bu/log.h"
7 #include "bu/str.h"
8 #include "bu/malloc.h"
9 #include "shape_recognition.h"
10 
11 curve_t
12 GetCurveType(ON_Curve *curve)
13 {
14  /* First, see if the curve is planar */
15 /* if (!curve->IsPlanar()) {
16  return CURVE_GENERAL;
17  }*/
18 
19  /* Check types in order of increasing complexity - simple
20  * is better, so try simple first */
21  ON_BoundingBox c_bbox;
22  curve->GetTightBoundingBox(c_bbox);
23  if (c_bbox.IsDegenerate() == 3) return CURVE_POINT;
24 
25  if (curve->IsLinear()) return CURVE_LINE;
26 
27  ON_Arc arc;
28  if (curve->IsArc(NULL, &arc, BREP_CYLINDRICAL_TOL)) {
29  if (arc.IsCircle()) return CURVE_CIRCLE;
30  ON_Circle circ(arc.StartPoint(), arc.MidPoint(), arc.EndPoint());
31  bu_log("arc's circle: center %f, %f, %f radius %f\n", circ.Center().x, circ.Center().y, circ.Center().z, circ.Radius());
32  return CURVE_ARC;
33  }
34 
35  // TODO - looks like we need a better test for this...
36  if (curve->IsEllipse(NULL, NULL, BREP_ELLIPSOIDAL_TOL)) return CURVE_ELLIPSE;
37 
38  return CURVE_GENERAL;
39 }
40 
42 GetSurfaceType(const ON_Surface *in_surface, struct filter_obj *obj)
43 {
45  ON_Surface *surface = in_surface->Duplicate();
46  if (obj) {
47  filter_obj_init(obj);
48  if (surface->IsPlanar(obj->plane, BREP_PLANAR_TOL)) {
49  ret = SURFACE_PLANE;
50  goto st_done;
51  }
52  delete surface;
53  surface = in_surface->Duplicate();
54  if (surface->IsSphere(obj->sphere , BREP_SPHERICAL_TOL)) {
55  ret = SURFACE_SPHERE;
56  goto st_done;
57  }
58  delete surface;
59  surface = in_surface->Duplicate();
60  if (surface->IsCylinder(obj->cylinder , BREP_CYLINDRICAL_TOL)) {
61  ret = SURFACE_CYLINDER;
62  goto st_done;
63  }
64  delete surface;
65  surface = in_surface->Duplicate();
66  if (surface->IsCone(obj->cone, BREP_CONIC_TOL)) {
67  ret = SURFACE_CONE;
68  goto st_done;
69  }
70  delete surface;
71  surface = in_surface->Duplicate();
72  if (surface->IsTorus(obj->torus, BREP_TOROIDAL_TOL)) {
73  ret = SURFACE_TORUS;
74  goto st_done;
75  }
76  } else {
77  if (surface->IsPlanar(NULL, BREP_PLANAR_TOL)) {
78  ret = SURFACE_PLANE;
79  goto st_done;
80  }
81  delete surface;
82  surface = in_surface->Duplicate();
83  if (surface->IsSphere(NULL, BREP_SPHERICAL_TOL)) {
84  ret = SURFACE_SPHERE;
85  goto st_done;
86  }
87  delete surface;
88  surface = in_surface->Duplicate();
89  if (surface->IsCylinder(NULL, BREP_CYLINDRICAL_TOL)) {
90  ret = SURFACE_CYLINDER;
91  goto st_done;
92  }
93  delete surface;
94  surface = in_surface->Duplicate();
95  if (surface->IsCone(NULL, BREP_CONIC_TOL)) {
96  ret = SURFACE_CONE;
97  goto st_done;
98  }
99  delete surface;
100  surface = in_surface->Duplicate();
101  if (surface->IsTorus(NULL, BREP_TOROIDAL_TOL)) {
102  ret = SURFACE_TORUS;
103  goto st_done;
104  }
105  }
106 st_done:
107  delete surface;
108  return ret;
109 }
110 
111 
112 surface_t
114 {
115  int planar = 0;
116  int spherical = 0;
117  int cylindrical = 0;
118  int cone = 0;
119  int torus = 0;
120  int general = 0;
121  int hof = -1;
122  surface_t hofo = SURFACE_PLANE;
123  for (int f_it = 0; f_it < brep->m_F.Count(); f_it++) {
124  ON_BrepFace &used_face = brep->m_F[f_it];
125  int surface_type = (int)GetSurfaceType(used_face.SurfaceOf(), NULL);
126  switch (surface_type) {
127  case SURFACE_PLANE:
128  planar++;
129  if (hofo < SURFACE_PLANE) {
130  hof = f_it;
131  hofo = SURFACE_PLANE;
132  }
133  break;
134  case SURFACE_SPHERE:
135  spherical++;
136  if (hofo < SURFACE_SPHERE) {
137  hof = f_it;
138  hofo = SURFACE_SPHERE;
139  }
140  break;
141  case SURFACE_CYLINDER:
142  cylindrical++;
143  if (hofo < SURFACE_CYLINDER) {
144  hof = f_it;
145  hofo = SURFACE_CYLINDER;
146  }
147  break;
148  case SURFACE_CONE:
149  cone++;
150  if (hofo < SURFACE_CONE) {
151  hof = f_it;
152  hofo = SURFACE_CONE;
153  }
154  break;
155  case SURFACE_TORUS:
156  torus++;
157  if (hofo < SURFACE_TORUS) {
158  hof = f_it;
159  hofo = SURFACE_TORUS;
160  }
161  break;
162  default:
163  general++;
164  hofo = SURFACE_GENERAL;
165  //std::cout << "general surface(" << used_face.m_face_index << "): " << used_face.SurfaceIndexOf() << "\n";
166  break;
167  }
168  }
169 #if 0
170  if (!general)
171  std::cout << "highest order face: " << hof << "(" << hofo << ")\n";
172 
173  std::cout << "\n";
174  std::cout << bu_vls_addr(data->key) << ":\n";
175  std::cout << "planar_cnt: " << planar << "\n";
176  std::cout << "spherical_cnt: " << spherical << "\n";
177  std::cout << "cylindrical_cnt: " << cylindrical << "\n";
178  std::cout << "cone_cnt: " << cone << "\n";
179  std::cout << "torus_cnt: " << torus << "\n";
180  std::cout << "general_cnt: " << general << "\n";
181  std::cout << "\n";
182 #endif
183  return hofo;
184 }
185 
186 void
188 {
189  if (!obj) return;
190  if (!obj->plane) obj->plane = new ON_Plane;
191  if (!obj->sphere) obj->sphere = new ON_Sphere;
192  if (!obj->cylinder) obj->cylinder = new ON_Cylinder;
193  if (!obj->cone) obj->cone = new ON_Cone;
194  if (!obj->torus) obj->torus = new ON_Torus;
195  obj->type = BREP;
196 }
197 
198 void
200 {
201  if (!obj) return;
202  delete obj->plane;
203  delete obj->sphere;
204  delete obj->cylinder;
205  delete obj->cone;
206  delete obj->torus;
207 }
208 
209 volume_t
211 {
212  if (subbrep_is_planar(data)) return PLANAR_VOLUME;
214  if (subbrep_is_cone(data, BREP_CONIC_TOL)) return CONE;
215  return BREP;
216 }
217 
218 void
220 {
221  if (!obj) return;
222  BU_GET(obj->params, struct csg_object_params);
223  BU_GET(obj->key, struct bu_vls);
224  BU_GET(obj->children, struct bu_ptbl);
225  bu_vls_init(obj->key);
226  bu_ptbl_init(obj->children, 8, "children table");
227  obj->parent = NULL;
228  obj->brep = brep->Duplicate();
229  obj->local_brep = NULL;
230  obj->type = BREP;
231 }
232 
233 void
235 {
236  if (!obj) return;
237  BU_PUT(obj->params, struct csg_object_params);
238  bu_vls_free(obj->key);
239  BU_PUT(obj->key, struct bu_vls);
240  for (unsigned int i = 0; i < BU_PTBL_LEN(obj->children); i++){
241  //struct subbrep_object_data *obj = (struct subbrep_object_data *)BU_PTBL_GET(obj->children, i);
242  //subbrep_object_free(obj);
243  }
244  bu_ptbl_free(obj->children);
245  BU_PUT(obj->children, struct bu_ptbl);
246  if (obj->faces) bu_free(obj->faces, "obj faces");
247  if (obj->loops) bu_free(obj->loops, "obj loops");
248  if (obj->edges) bu_free(obj->edges, "obj edges");
249  if (obj->fol) bu_free(obj->fol, "obj fol");
250  if (obj->fil) bu_free(obj->fil, "obj fil");
251  if (obj->face_map) bu_free(obj->face_map, "obj face_map");
252  if (obj->surface_map) bu_free(obj->surface_map, "obj surface_map");
253  if (obj->edge_map) bu_free(obj->edge_map, "obj edge_map");
254  if (obj->vertex_map) bu_free(obj->vertex_map, "obj vertex_map");
255  if (obj->loop_map) bu_free(obj->loop_map, "obj loop_map");
256  if (obj->c3_map) bu_free(obj->c3_map, "obj c3_map");
257  if (obj->c2_map) bu_free(obj->c2_map, "obj c2_map");
258  if (obj->trim_map) bu_free(obj->trim_map, "obj trim_map");
259  obj->parent = NULL;
260  delete obj->brep;
261 }
262 
263 
264 std::string
265 face_set_key(std::set<int> fset)
266 {
267  std::set<int>::iterator s_it;
268  std::set<int>::iterator s_it2;
269  std::string key;
270  struct bu_vls vls_key = BU_VLS_INIT_ZERO;
271  for (s_it = fset.begin(); s_it != fset.end(); s_it++) {
272  bu_vls_printf(&vls_key, "%d", (*s_it));
273  s_it2 = s_it;
274  s_it2++;
275  if (s_it2 != fset.end()) bu_vls_printf(&vls_key, "_");
276  }
277  bu_vls_printf(&vls_key, ".s");
278  key.append(bu_vls_addr(&vls_key));
279  bu_vls_free(&vls_key);
280  return key;
281 }
282 
283 void
284 set_to_array(int **array, int *array_cnt, std::set<int> *set)
285 {
286  std::set<int>::iterator s_it;
287  int i = 0;
288  (*array_cnt) = set->size();
289  if ((*array_cnt) > 0) {
290  (*array) = (int *)bu_calloc((*array_cnt), sizeof(int), "array");
291  for (s_it = set->begin(); s_it != set->end(); s_it++) {
292  (*array)[i] = *s_it;
293  i++;
294  }
295  }
296 }
297 
298 void
299 array_to_set(std::set<int> *set, int *array, int array_cnt)
300 {
301  for (int i = 0; i < array_cnt; i++) {
302  set->insert(array[i]);
303  }
304 }
305 
306 void
307 map_to_array(int **array, int *array_cnt, std::map<int,int> *map)
308 {
309  std::map<int,int>::iterator m_it;
310  int i = 0;
311  (*array_cnt) = map->size();
312  if ((*array_cnt) > 0) {
313  (*array) = (int *)bu_calloc((*array_cnt)*2, sizeof(int), "array");
314  for (m_it = map->begin(); m_it != map->end(); m_it++) {
315  (*array)[i] = m_it->first;
316  (*array)[i+*array_cnt] = m_it->first;
317  i++;
318  }
319  }
320 }
321 
322 void
323 array_to_map(std::map<int,int> *map, int *array, int array_cnt)
324 {
325  for (int i = 0; i < array_cnt; i++) {
326  (*map)[array[i]] = array[array_cnt+i];
327  }
328 }
329 
330 struct bu_ptbl *
332 {
333  struct bu_ptbl *subbreps;
334  std::set<std::string> subbrep_keys;
335  BU_GET(subbreps, struct bu_ptbl);
336  bu_ptbl_init(subbreps, 8, "subbrep table");
337 
338  /* For each face, build the topologically connected subset. If that
339  * subset has not already been seen, add it to the brep's set of
340  * subbreps */
341  for (int i = 0; i < brep->m_F.Count(); i++) {
342  std::string key;
343  std::set<int> faces;
344  std::set<int> loops;
345  std::set<int> edges;
346  std::set<int> fol; /* Faces with outer loops in object loop network */
347  std::set<int> fil; /* Faces with only inner loops in object loop network */
348  std::queue<int> local_loops;
349  std::set<int> processed_loops;
350  std::set<int>::iterator s_it;
351 
352  ON_BrepFace *face = &(brep->m_F[i]);
353  faces.insert(i);
354  fol.insert(i);
355  local_loops.push(face->OuterLoop()->m_loop_index);
356  processed_loops.insert(face->OuterLoop()->m_loop_index);
357  while(!local_loops.empty()) {
358  ON_BrepLoop* loop = &(brep->m_L[local_loops.front()]);
359  loops.insert(local_loops.front());
360  local_loops.pop();
361  for (int ti = 0; ti < loop->m_ti.Count(); ti++) {
362  ON_BrepTrim& trim = face->Brep()->m_T[loop->m_ti[ti]];
363  ON_BrepEdge& edge = face->Brep()->m_E[trim.m_ei];
364  if (trim.m_ei != -1 && edge.TrimCount() > 1) {
365  edges.insert(trim.m_ei);
366  for (int j = 0; j < edge.TrimCount(); j++) {
367  int fio = edge.Trim(j)->FaceIndexOf();
368  if (edge.m_ti[j] != ti && fio != -1) {
369  int li = edge.Trim(j)->Loop()->m_loop_index;
370  faces.insert(fio);
371  if (processed_loops.find(li) == processed_loops.end()) {
372  local_loops.push(li);
373  processed_loops.insert(li);
374  }
375  if (li == brep->m_F[fio].OuterLoop()->m_loop_index) {
376  fol.insert(fio);
377  }
378  }
379  }
380  }
381  }
382  }
383  for (s_it = faces.begin(); s_it != faces.end(); s_it++) {
384  if (fol.find(*s_it) == fol.end()) {
385  fil.insert(*s_it);
386  }
387  }
388  key = face_set_key(faces);
389 
390  /* If we haven't seen this particular subset before, add it */
391  if (subbrep_keys.find(key) == subbrep_keys.end()) {
392  subbrep_keys.insert(key);
393  struct subbrep_object_data *new_obj;
394  BU_GET(new_obj, struct subbrep_object_data);
395  subbrep_object_init(new_obj, brep);
396  bu_vls_sprintf(new_obj->key, "%s", key.c_str());
397  set_to_array(&(new_obj->faces), &(new_obj->faces_cnt), &faces);
398  set_to_array(&(new_obj->loops), &(new_obj->loops_cnt), &loops);
399  set_to_array(&(new_obj->edges), &(new_obj->edges_cnt), &edges);
400  set_to_array(&(new_obj->fol), &(new_obj->fol_cnt), &fol);
401  set_to_array(&(new_obj->fil), &(new_obj->fil_cnt), &fil);
402 
403  if (subbrep_shape_recognize(new_obj) == BREP) {
404  (void)subbrep_make_brep(new_obj);
405  }
406 
407  bu_ptbl_ins(subbreps, (long *)new_obj);
408  }
409  }
410 
411  return subbreps;
412 }
413 
414 
415 
416 
417 
418 void
419 print_subbrep_object(struct subbrep_object_data *data, const char *offset)
420 {
421  struct bu_vls log = BU_VLS_INIT_ZERO;
422  bu_vls_printf(&log, "\n");
423  bu_vls_printf(&log, "%sObject %s:\n", offset, bu_vls_addr(data->key));
424  bu_vls_printf(&log, "%sType: ", offset);
425  switch (data->type) {
426  case COMB:
427  bu_vls_printf(&log, "comb\n");
428  break;
429  case PLANAR_VOLUME:
430  bu_vls_printf(&log, "planar\n");
431  break;
432  case CYLINDER:
433  bu_vls_printf(&log, "cylinder\n");
434  break;
435  case CONE:
436  bu_vls_printf(&log, "cone\n");
437  break;
438  case SPHERE:
439  bu_vls_printf(&log, "sphere\n");
440  break;
441  case ELLIPSOID:
442  bu_vls_printf(&log, "ellipsoid\n");
443  break;
444  case TORUS:
445  bu_vls_printf(&log, "torus\n");
446  break;
447  default:
448  bu_vls_printf(&log, "brep\n");
449  }
450  bu_vls_printf(&log, "%sFace set: ", offset);
451  for (int i = 0; i < data->faces_cnt; i++) {
452  bu_vls_printf(&log, "%d", data->faces[i]);
453  if (i + 1 != data->faces_cnt) bu_vls_printf(&log, ",");
454  }
455  bu_vls_printf(&log, "\n");
456  bu_vls_printf(&log, "%sLoop set: ", offset);
457  for (int i = 0; i < data->loops_cnt; i++) {
458  bu_vls_printf(&log, "%d", data->loops[i]);
459  if (i + 1 != data->loops_cnt) bu_vls_printf(&log, ",");
460  }
461  bu_vls_printf(&log, "\n");
462  bu_vls_printf(&log, "%sEdge set: ", offset);
463  for (int i = 0; i < data->edges_cnt; i++) {
464  bu_vls_printf(&log, "%d", data->edges[i]);
465  if (i + 1 != data->edges_cnt) bu_vls_printf(&log, ",");
466  }
467  bu_vls_printf(&log, "\n");
468  bu_vls_printf(&log, "%sFaces with outer loop set: ", offset);
469  for (int i = 0; i < data->fol_cnt; i++) {
470  bu_vls_printf(&log, "%d", data->fol[i]);
471  if (i + 1 != data->fol_cnt) bu_vls_printf(&log, ",");
472  }
473  bu_vls_printf(&log, "\n");
474  bu_vls_printf(&log, "%sFaces with only inner loops set: ", offset);
475  for (int i = 0; i < data->fil_cnt; i++) {
476  bu_vls_printf(&log, "%d", data->fil[i]);
477  if (i + 1 != data->fil_cnt) bu_vls_printf(&log, ",");
478  }
479  bu_vls_printf(&log, "\n");
480 
481  bu_log("%s\n", bu_vls_addr(&log));
482  bu_vls_free(&log);
483 }
484 
485 
486 
487 
488 void
489 set_filter_obj(ON_BrepFace *face, struct filter_obj *obj)
490 {
491  if (!obj) return;
492  filter_obj_init(obj);
493  obj->stype = GetSurfaceType(face->SurfaceOf(), obj);
494  // If we've got a planar face, we can stop now - planar faces
495  // are determinative of volume type only when *all* faces are planar,
496  // and that case is handled elsewhere - anything is "allowed".
497  if (obj->stype == SURFACE_PLANE) obj->type = BREP;
498 
499  // If we've got a general surface, anything is allowed
500  if (obj->stype == SURFACE_GENERAL) obj->type = BREP;
501 
502  if (obj->stype == SURFACE_CYLINDRICAL_SECTION || obj->stype == SURFACE_CYLINDER) obj->type = CYLINDER;
503 
504  if (obj->stype == SURFACE_CONE) obj->type = CONE;
505 
506  if (obj->stype == SURFACE_SPHERICAL_SECTION || obj->stype == SURFACE_SPHERE) obj->type = SPHERE;
507 
508  if (obj->stype == SURFACE_TORUS) obj->type = TORUS;
509 }
510 
511 int
512 apply_filter_obj(ON_BrepFace *face, int loop_index, struct filter_obj *obj)
513 {
514  int ret = 1;
515  struct filter_obj *local_obj;
516  BU_GET(local_obj, struct filter_obj);
517  int surface_type = (int)GetSurfaceType(face->SurfaceOf(), local_obj);
518 
519  std::set<int> allowed;
520 
521  if (obj->type == CYLINDER) {
522  allowed.insert(SURFACE_CYLINDRICAL_SECTION);
523  allowed.insert(SURFACE_CYLINDER);
524  allowed.insert(SURFACE_PLANE);
525  }
526 
527  if (obj->type == CONE) {
528  allowed.insert(SURFACE_CONE);
529  allowed.insert(SURFACE_PLANE);
530  }
531 
532  if (obj->type == SPHERE) {
533  allowed.insert(SURFACE_SPHERICAL_SECTION);
534  allowed.insert(SURFACE_SPHERE);
535  allowed.insert(SURFACE_PLANE);
536  }
537 
538  if (obj->type == TORUS) {
539  allowed.insert(SURFACE_TORUS);
540  allowed.insert(SURFACE_PLANE);
541  }
542 
543 
544  // If the face's surface type is not part of the allowed set for
545  // this object type, we're done
546  if (allowed.find(surface_type) == allowed.end()) {
547  ret = 0;
548  goto filter_done;
549  }
550  if (obj->type == CYLINDER) {
551  if (surface_type == SURFACE_PLANE) {
552  int is_parallel = obj->cylinder->Axis().IsParallelTo(local_obj->plane->Normal(), BREP_PLANAR_TOL);
553  if (is_parallel == 0) {
554  ret = 0;
555  goto filter_done;
556  }
557  }
558  if (surface_type == SURFACE_CYLINDER || surface_type == SURFACE_CYLINDRICAL_SECTION ) {
559  // Make sure the surfaces are on the same cylinder
560  if (obj->cylinder->circle.Center().DistanceTo(local_obj->cylinder->circle.Center()) > BREP_CYLINDRICAL_TOL) {
561  ret = 0;
562  goto filter_done;
563  }
564  }
565  }
566  if (obj->type == CONE) {
567  }
568  if (obj->type == SPHERE) {
569  }
570  if (obj->type == TORUS) {
571  }
572 
573 filter_done:
574  filter_obj_free(local_obj);
575  BU_PUT(local_obj, struct filter_obj);
576  return ret;
577 }
578 
579 void
580 add_loops_from_face(ON_BrepFace *face, struct subbrep_object_data *data, std::set<int> *loops, std::queue<int> *local_loops, std::set<int> *processed_loops)
581 {
582  for (int j = 0; j < face->m_li.Count(); j++) {
583  int loop_in_set = 0;
584  int loop_ind = face->m_li[j];
585  int k = 0;
586  while (k < data->loops_cnt) {
587  if (data->loops[k] == loop_ind) loop_in_set = 1;
588  k++;
589  }
590  if (loop_in_set) loops->insert(loop_ind);
591  if (loop_in_set && processed_loops->find(loop_ind) == processed_loops->end()) {
592  local_loops->push(loop_ind);
593  }
594  }
595 }
596 
597 
598 /* In order to represent complex shapes, it is necessary to identify
599  * subsets of subbreps that can be represented as primitives. This
600  * function will identify such subsets, if possible. If a subbrep
601  * can be successfully decomposed into primitive candidates, the
602  * type of the subbrep is set to COMB and the children bu_ptbl is
603  * populated with subbrep_object_data sets. */
604 int
606 {
607  //if (BU_STR_EQUAL(bu_vls_addr(data->key), "325_326_441_527_528.s")) {
608  // std::cout << "looking at 325_326_441_527_528\n";
609  //}
610 
612  if (hof >= SURFACE_GENERAL) {
613  data->type = BREP;
614  std::cout << "general surface present: " << bu_vls_addr(data->key) << "\n\n";
615  return 0;
616  }
617  std::set<int> processed_faces;
618  std::set<std::string> subbrep_keys;
619  /* For each face, identify the candidate solid type. If that
620  * subset has not already been seen, add it to the brep's set of
621  * subbreps */
622  for (int i = 0; i < data->faces_cnt; i++) {
623  std::string key;
624  std::set<int> faces;
625  std::set<int> loops;
626  std::set<int> edges;
627  std::queue<int> local_loops;
628  std::set<int> processed_loops;
629  std::set<int>::iterator s_it;
630  struct filter_obj *filters;
631  BU_GET(filters, struct filter_obj);
632  std::set<int> locally_processed_faces;
633 
634  ON_BrepFace *face = &(data->brep->m_F[data->faces[i]]);
635  set_filter_obj(face, filters);
636  if (filters->type == BREP) {
637  filter_obj_free(filters);
638  BU_PUT(filters, struct filter_obj);
639  continue;
640  }
641  if (filters->stype == SURFACE_PLANE) {
642  filter_obj_free(filters);
643  BU_PUT(filters, struct filter_obj);
644  continue;
645  }
646  faces.insert(data->faces[i]);
647  //std::cout << "working: " << data->faces[i] << "\n";
648  locally_processed_faces.insert(data->faces[i]);
649  add_loops_from_face(face, data, &loops, &local_loops, &processed_loops);
650 
651  while(!local_loops.empty()) {
652  int curr_loop = local_loops.front();
653  local_loops.pop();
654  if (processed_loops.find(curr_loop) == processed_loops.end()) {
655  ON_BrepLoop* loop = &(data->brep->m_L[curr_loop]);
656  loops.insert(curr_loop);
657  processed_loops.insert(curr_loop);
658  for (int ti = 0; ti < loop->m_ti.Count(); ti++) {
659  ON_BrepTrim& trim = face->Brep()->m_T[loop->m_ti[ti]];
660  ON_BrepEdge& edge = face->Brep()->m_E[trim.m_ei];
661  if (trim.m_ei != -1 && edge.TrimCount() > 1) {
662  edges.insert(trim.m_ei);
663  for (int j = 0; j < edge.TrimCount(); j++) {
664  int fio = edge.Trim(j)->FaceIndexOf();
665  if (fio != -1 && locally_processed_faces.find(fio) == locally_processed_faces.end()) {
666  ON_BrepFace *fface = &(data->brep->m_F[fio]);
667  surface_t stype = GetSurfaceType(fface->SurfaceOf(), NULL);
668  // If fio meets the criteria for the candidate shape, add it. Otherwise,
669  // it's not part of this shape candidate
670  if (apply_filter_obj(fface, curr_loop, filters)) {
671  // TODO - more testing needs to be done here... get_allowed_surface_types
672  // returns the volume_t, use it to do some testing to evaluate
673  // things like normals and shared axis
674  //std::cout << "accept: " << fio << "\n";
675  faces.insert(fio);
676  locally_processed_faces.insert(fio);
677  // The planar faces will always share edges with the non-planar
678  // faces, which drive the primary shape. Also, planar faces are
679  // more likely to have other edges that relate to other shapes.
680  if (stype != SURFACE_PLANE)
681  add_loops_from_face(fface, data, &loops, &local_loops, &processed_loops);
682  }
683  }
684  }
685  }
686  }
687  }
688  }
689  key = face_set_key(faces);
690 
691  /* If we haven't seen this particular subset before, add it */
692  if (subbrep_keys.find(key) == subbrep_keys.end()) {
693  subbrep_keys.insert(key);
694  struct subbrep_object_data *new_obj;
695  BU_GET(new_obj, struct subbrep_object_data);
696  subbrep_object_init(new_obj, data->brep);
697  bu_vls_sprintf(new_obj->key, "%s", key.c_str());
698  set_to_array(&(new_obj->faces), &(new_obj->faces_cnt), &faces);
699  set_to_array(&(new_obj->loops), &(new_obj->loops_cnt), &loops);
700  set_to_array(&(new_obj->edges), &(new_obj->edges_cnt), &edges);
701  new_obj->fol_cnt = 0;
702  new_obj->fil_cnt = 0;
703 
704  new_obj->type = filters->type;
705  switch (new_obj->type) {
706  case CYLINDER:
707  (void)cylinder_csg(new_obj, BREP_CYLINDRICAL_TOL);
708  break;
709  case CONE:
710  (void)cone_csg(new_obj, BREP_CONIC_TOL);
711  break;
712  case SPHERE:
713  bu_log("process partial sphere\n");
714  break;
715  case ELLIPSOID:
716  bu_log("process partial ellipsoid\n");
717  break;
718  case TORUS:
719  bu_log("process partial torus\n");
720  break;
721  default:
722  break;
723  }
724 
725  bu_ptbl_ins(data->children, (long *)new_obj);
726  }
727  filter_obj_free(filters);
728  BU_PUT(filters, struct filter_obj);
729  }
730  if (subbrep_keys.size() == 0) {
731  data->type = BREP;
732  return 0;
733  }
734  data->type = COMB;
735  return 1;
736 }
737 
738 int
740 {
741  if (data->local_brep) return 0;
742  data->local_brep = ON_Brep::New();
743  // For each edge in data, find the corresponding loop in data and construct
744  // a new face in the brep with the surface from the original face and the
745  // loop in data as the new outer loop. Trim down the surface for the new
746  // role. Add the corresponding 3D edges and sync things up.
747 
748  // Each edge will map to two faces in the original Brep. We only want the
749  // subset of data that is part of this particular subobject - to do that,
750  // we need to map elements from their indices in the old Brep to their
751  // locations in the new.
752  std::map<int, int> face_map;
753  std::map<int, int> surface_map;
754  std::map<int, int> edge_map;
755  std::map<int, int> vertex_map;
756  std::map<int, int> loop_map;
757  std::map<int, int> c3_map;
758  std::map<int, int> c2_map;
759  std::map<int, int> trim_map;
760  std::map<int, int> subloop_map; // When not all of the trims from an old loop are used, make new loops here so we have somewhere to stash the trims. They'll be useful if we want/need to construct faces closing the new subbreps.
761 
762  std::set<int> faces;
763  std::set<int> fil;
764  std::set<int> loops;
765  std::set<int> isolated_trims; // collect 2D trims whose parent loops aren't fully included here
766  array_to_set(&faces, data->faces, data->faces_cnt);
767  array_to_set(&fil, data->fil, data->fil_cnt);
768  array_to_set(&loops, data->loops, data->loops_cnt);
769 
770  // Each edge has a trim array, and the trims will tell us which loops
771  // are to be included and which faces the trims belong to. There will
772  // be some trims that belong to a face that is not included in the
773  // subbrep face list, and those are rejected - those rejections indicate
774  // a new face needs to be created to close the Brep. The edges will drive
775  // the population of new_brep initially - for each element pulled in by
776  // the edge, it is either added or (if it's already in the map) references
777  // are updated.
778 
779  for (int i = 0; i < data->edges_cnt; i++) {
780  int c3i;
781  ON_BrepEdge *old_edge = &(data->brep->m_E[data->edges[i]]);
782  //std::cout << "old edge: " << old_edge->Vertex(0)->m_vertex_index << "," << old_edge->Vertex(1)->m_vertex_index << "\n";
783 
784  // Get the 3D curves from the edges
785  if (c3_map.find(old_edge->EdgeCurveIndexOf()) == c3_map.end()) {
786  ON_Curve *nc = old_edge->EdgeCurveOf()->Duplicate();
787  c3i = data->local_brep->AddEdgeCurve(nc);
788  c3_map[old_edge->EdgeCurveIndexOf()] = c3i;
789  } else {
790  c3i = c3_map[old_edge->EdgeCurveIndexOf()];
791  }
792 
793  // Get the vertices from the edges
794  int v0i, v1i;
795  if (vertex_map.find(old_edge->Vertex(0)->m_vertex_index) == vertex_map.end()) {
796  ON_BrepVertex& newv0 = data->local_brep->NewVertex(old_edge->Vertex(0)->Point(), old_edge->Vertex(0)->m_tolerance);
797  v0i = newv0.m_vertex_index;
798  vertex_map[old_edge->Vertex(0)->m_vertex_index] = v0i;
799  } else {
800  v0i = vertex_map[old_edge->Vertex(0)->m_vertex_index];
801  }
802  if (vertex_map.find(old_edge->Vertex(1)->m_vertex_index) == vertex_map.end()) {
803  ON_BrepVertex& newv1 = data->local_brep->NewVertex(old_edge->Vertex(1)->Point(), old_edge->Vertex(1)->m_tolerance);
804  v1i = newv1.m_vertex_index;
805  vertex_map[old_edge->Vertex(1)->m_vertex_index] = v1i;
806  } else {
807  v1i = vertex_map[old_edge->Vertex(1)->m_vertex_index];
808  }
809  ON_BrepEdge& new_edge = data->local_brep->NewEdge(data->local_brep->m_V[v0i], data->local_brep->m_V[v1i], c3i, NULL ,0);
810  edge_map[old_edge->m_edge_index] = new_edge.m_edge_index;
811  //std::cout << "new edge: " << v0i << "," << v1i << "\n";
812 
813  // Get the 2D curves from the trims
814  for (int j = 0; j < old_edge->TrimCount(); j++) {
815  ON_BrepTrim *old_trim = old_edge->Trim(j);
816  if (faces.find(old_trim->Face()->m_face_index) != faces.end()) {
817  if (c2_map.find(old_trim->TrimCurveIndexOf()) == c2_map.end()) {
818  ON_Curve *nc = old_trim->TrimCurveOf()->Duplicate();
819  int c2i = data->local_brep->AddTrimCurve(nc);
820  c2_map[old_trim->TrimCurveIndexOf()] = c2i;
821  //std::cout << "c2i: " << c2i << "\n";
822  }
823  }
824  }
825 
826  // Get the faces and surfaces from the trims
827  for (int j = 0; j < old_edge->TrimCount(); j++) {
828  ON_BrepTrim *old_trim = old_edge->Trim(j);
829  if (face_map.find(old_trim->Face()->m_face_index) == face_map.end()) {
830  if (faces.find(old_trim->Face()->m_face_index) != faces.end()) {
831  ON_Surface *ns = old_trim->Face()->SurfaceOf()->Duplicate();
832  int nsid = data->local_brep->AddSurface(ns);
833  surface_map[old_trim->Face()->SurfaceIndexOf()] = nsid;
834  ON_BrepFace &new_face = data->local_brep->NewFace(nsid);
835  face_map[old_trim->Face()->m_face_index] = new_face.m_face_index;
836  //std::cout << "old_face: " << old_trim->Face()->m_face_index << "\n";
837  //std::cout << "new_face: " << new_face.m_face_index << "\n";
838  if (fil.find(old_trim->Face()->m_face_index) != fil.end()) {
839  data->local_brep->FlipFace(new_face);
840  }
841 
842  }
843  }
844  }
845 
846  // Get the loops from the trims
847  for (int j = 0; j < old_edge->TrimCount(); j++) {
848  ON_BrepTrim *old_trim = old_edge->Trim(j);
849  ON_BrepLoop *old_loop = old_trim->Loop();
850  if (face_map.find(old_trim->Face()->m_face_index) != face_map.end()) {
851  if (loops.find(old_loop->m_loop_index) != loops.end()) {
852  if (loop_map.find(old_loop->m_loop_index) == loop_map.end()) {
853  // After the initial breakout, all loops in any given subbrep are outer loops,
854  // whatever they were in the original brep.
855  ON_BrepLoop &nl = data->local_brep->NewLoop(ON_BrepLoop::outer, data->local_brep->m_F[face_map[old_loop->m_fi]]);
856  loop_map[old_loop->m_loop_index] = nl.m_loop_index;
857  //std::cout << "adding loop: " << old_loop->m_loop_index << "\n";
858  }
859  } else {
860  //std::cout << "have isolated trim whose parent loop isn't fully included\n";
861  if (subloop_map.find(old_loop->m_loop_index) == subloop_map.end()) {
862  ON_BrepLoop &nl = data->local_brep->NewLoop(ON_BrepLoop::outer, data->local_brep->m_F[face_map[old_loop->m_fi]]);
863  subloop_map[old_loop->m_loop_index] = nl.m_loop_index;
864  isolated_trims.insert(old_trim->m_trim_index);
865  }
866  }
867  }
868  }
869  }
870 
871  // Now, create new trims using the old loop definitions and the maps
872  std::map<int, int>::iterator loop_it;
873  for (loop_it = loop_map.begin(); loop_it != loop_map.end(); loop_it++) {
874  ON_BrepLoop &old_loop = data->brep->m_L[(*loop_it).first];
875  ON_BrepLoop &new_loop = data->local_brep->m_L[(*loop_it).second];
876  for (int j = 0; j < old_loop.TrimCount(); j++) {
877  ON_BrepTrim *old_trim = old_loop.Trim(j);
878  //std::cout << "loop[" << (*loop_it).first << "," << (*loop_it).second << "]: trim " << old_trim->m_trim_index << "\n";
879  ON_BrepEdge *o_edge = old_trim->Edge();
880  if (o_edge) {
881  ON_BrepEdge &n_edge = data->local_brep->m_E[edge_map[o_edge->m_edge_index]];
882  //std::cout << "edge(" << o_edge->m_edge_index << "," << n_edge.m_edge_index << ")\n";
883  ON_BrepTrim &nt = data->local_brep->NewTrim(n_edge, old_trim->m_bRev3d, new_loop, c2_map[old_trim->TrimCurveIndexOf()]);
884  nt.m_tolerance[0] = old_trim->m_tolerance[0];
885  nt.m_tolerance[1] = old_trim->m_tolerance[1];
886 
887  nt.m_iso = old_trim->m_iso;
888  } else {
889  /* If we didn't have an edge originally, we need to add the 2d curve here */
890  if (c2_map.find(old_trim->TrimCurveIndexOf()) == c2_map.end()) {
891  ON_Curve *nc = old_trim->TrimCurveOf()->Duplicate();
892  int c2i = data->local_brep->AddTrimCurve(nc);
893  c2_map[old_trim->TrimCurveIndexOf()] = c2i;
894  //std::cout << "2D only c2i: " << c2i << "\n";
895  }
896  if (vertex_map.find(old_trim->Vertex(0)->m_vertex_index) == vertex_map.end()) {
897  ON_BrepVertex& newvs = data->local_brep->NewVertex(old_trim->Vertex(0)->Point(), old_trim->Vertex(0)->m_tolerance);
898  ON_BrepTrim &nt = data->local_brep->NewSingularTrim(newvs, new_loop, old_trim->m_iso, c2_map[old_trim->TrimCurveIndexOf()]);
899  nt.m_tolerance[0] = old_trim->m_tolerance[0];
900  nt.m_tolerance[1] = old_trim->m_tolerance[1];
901  } else {
902  ON_BrepTrim &nt = data->local_brep->NewSingularTrim(data->local_brep->m_V[vertex_map[old_trim->Vertex(0)->m_vertex_index]], new_loop, old_trim->m_iso, c2_map[old_trim->TrimCurveIndexOf()]);
903  nt.m_tolerance[0] = old_trim->m_tolerance[0];
904  nt.m_tolerance[1] = old_trim->m_tolerance[1];
905  }
906  }
907  }
908  }
909  std::set<int>::iterator trims_it;
910  for (trims_it = isolated_trims.begin(); trims_it != isolated_trims.end(); trims_it++) {
911  ON_BrepTrim &old_trim = data->brep->m_T[*trims_it];
912  ON_BrepLoop &new_loop = data->local_brep->m_L[subloop_map[old_trim.Loop()->m_loop_index]];
913  ON_BrepEdge *o_edge = old_trim.Edge();
914  if (o_edge) {
915  ON_BrepEdge &n_edge = data->local_brep->m_E[edge_map[o_edge->m_edge_index]];
916  //std::cout << "edge(" << o_edge->m_edge_index << "," << n_edge.m_edge_index << ")\n";
917  ON_BrepTrim &nt = data->local_brep->NewTrim(n_edge, old_trim.m_bRev3d, new_loop, c2_map[old_trim.TrimCurveIndexOf()]);
918  nt.m_tolerance[0] = old_trim.m_tolerance[0];
919  nt.m_tolerance[1] = old_trim.m_tolerance[1];
920 
921  nt.m_iso = old_trim.m_iso;
922  } else {
923  /* If we didn't have an edge originally, we need to add the 2d curve here */
924  if (c2_map.find(old_trim.TrimCurveIndexOf()) == c2_map.end()) {
925  ON_Curve *nc = old_trim.TrimCurveOf()->Duplicate();
926  int c2i = data->local_brep->AddTrimCurve(nc);
927  c2_map[old_trim.TrimCurveIndexOf()] = c2i;
928  //std::cout << "2D only c2i: " << c2i << "\n";
929  }
930  if (vertex_map.find(old_trim.Vertex(0)->m_vertex_index) == vertex_map.end()) {
931  ON_BrepVertex& newvs = data->local_brep->NewVertex(old_trim.Vertex(0)->Point(), old_trim.Vertex(0)->m_tolerance);
932  ON_BrepTrim &nt = data->local_brep->NewSingularTrim(newvs, new_loop, old_trim.m_iso, c2_map[old_trim.TrimCurveIndexOf()]);
933  nt.m_tolerance[0] = old_trim.m_tolerance[0];
934  nt.m_tolerance[1] = old_trim.m_tolerance[1];
935  } else {
936  ON_BrepTrim &nt = data->local_brep->NewSingularTrim(data->local_brep->m_V[vertex_map[old_trim.Vertex(0)->m_vertex_index]], new_loop, old_trim.m_iso, c2_map[old_trim.TrimCurveIndexOf()]);
937  nt.m_tolerance[0] = old_trim.m_tolerance[0];
938  nt.m_tolerance[1] = old_trim.m_tolerance[1];
939  }
940  }
941  }
942 
943  // Make sure all the loop directions are correct
944  for (int l = 0; l < data->local_brep->m_L.Count(); l++) {
945  if (data->local_brep->LoopDirection(data->local_brep->m_L[l]) != 1) {
946  data->local_brep->FlipLoop(data->local_brep->m_L[l]);
947  }
948  }
949 
950  data->local_brep->ShrinkSurfaces();
951  data->local_brep->CullUnusedSurfaces();
952 
953  map_to_array(&(data->face_map), &(data->face_map_cnt), &face_map);
954  map_to_array(&(data->surface_map), &(data->surface_map_cnt), &surface_map);
955  map_to_array(&(data->edge_map), &(data->edge_map_cnt), &edge_map);
956  map_to_array(&(data->vertex_map), &(data->vertex_map_cnt), &vertex_map);
957  map_to_array(&(data->loop_map), &(data->loop_map_cnt), &loop_map);
958  map_to_array(&(data->c3_map), &(data->c3_map_cnt), &c3_map);
959  map_to_array(&(data->c2_map), &(data->c2_map_cnt), &c2_map);
960  map_to_array(&(data->trim_map), &(data->trim_map_cnt), &trim_map);
961 
962  std::cout << "new brep done: " << bu_vls_addr(data->key) << "\n";
963 
964  return 1;
965 }
966 
967 int
969 {
970  struct subbrep_object_data *top_union = NULL;
971  /* The toplevel unioned object in the tree will be the one with no faces
972  * that have only inner loops in the object loop network */
973  for (unsigned int i = 0; i < BU_PTBL_LEN(subbreps); i++){
974  struct subbrep_object_data *obj = (struct subbrep_object_data *)BU_PTBL_GET(subbreps, i);
975  if (obj->fil_cnt == 0) {
976  top_union = obj;
977  } else {
978  bu_log("Error - multiple objects appear to qualify as the first union object\n");
979  return 0;
980  }
981  }
982  if (!top_union) {
983  bu_log("Error - no object qualifies as the first union object\n");
984  return 0;
985  }
986  /* Once the top level is identified, all other objects are parented to that object.
987  * Technically they are not children of that object but of the toplevel comb */
988  for (unsigned int i = 0; i < BU_PTBL_LEN(subbreps); i++){
989  struct subbrep_object_data *obj = (struct subbrep_object_data *)BU_PTBL_GET(subbreps, i);
990  if (obj != top_union) obj->parent = top_union;
991  }
992 
993  /* For each child object, we need to ascertain whether the object is subtracted from the
994  * top object or unioned to it. The general test for this is to raytrace the original BRep
995  * through the child volume in question, and determine from the raytrace results whether
996  * the volume adds to or takes away from the solidity along that shotline. This is a
997  * relatively expensive test, so if we have simpler shapes that let us do other tests
998  * let's try those first. */
999 
1000  /* Once we know whether the local shape is a subtraction or addition, we can decide for the
1001  * individual shapes in the combination whether they are subtractions or unions locally.
1002  * For example, if a cylinder is subtracted from the toplevel nmg, and a cone is
1003  * in turn subtracted from that cylinder (in other words, the cone shape contributes volume to the
1004  * final shape) the cone is subtracted from the local comb containing the cylinder and the cone, which
1005  * is in turn subtracted from the toplevel nmg. Likewise, if the cylinder had been unioned to the nmg
1006  * to add volume and the cone had also added volume to the final shape (i.e. it's surface normals point
1007  * outward from the cone) then the code would be unioned with the cylinder in the local comb, and the
1008  * local comb would be unioned into the toplevel. */
1009 
1010  return 0;
1011 }
1012 
1013 // Local Variables:
1014 // tab-width: 8
1015 // mode: C++
1016 // c-basic-offset: 4
1017 // indent-tabs-mode: t
1018 // c-file-style: "stroustrup"
1019 // End:
1020 // ex: shiftwidth=4 tabstop=8
void bu_vls_init(struct bu_vls *vp)
Definition: vls.c:56
int subbrep_is_cone(struct subbrep_object_data *data, fastf_t cone_tol)
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
void filter_obj_free(struct filter_obj *obj)
int subbrep_is_planar(struct subbrep_object_data *data)
volume_t
void bu_ptbl_init(struct bu_ptbl *b, size_t len, const char *str)
Definition: ptbl.c:32
#define BREP_TOROIDAL_TOL
surface_t highest_order_face(ON_Brep *brep)
struct bu_ptbl * find_subbreps(ON_Brep *brep)
#define BREP_CONIC_TOL
Header file for the BRL-CAD common definitions.
void map_to_array(int **array, int *array_cnt, std::map< int, int > *map)
void set_filter_obj(ON_BrepFace *face, struct filter_obj *obj)
#define BREP_CYLINDRICAL_TOL
int bu_ptbl_ins(struct bu_ptbl *b, long *p)
void array_to_map(std::map< int, int > *map, int *array, int array_cnt)
curve_t GetCurveType(ON_Curve *curve)
Definition: ptbl.h:62
void bu_vls_free(struct bu_vls *vp)
Definition: vls.c:248
int apply_filter_obj(ON_BrepFace *face, int loop_index, struct filter_obj *obj)
COMPLEX data[64]
Definition: fftest.c:34
ON_Plane * plane
void * bu_calloc(size_t nelem, size_t elsize, const char *str)
Definition: malloc.c:321
#define BU_PTBL_GET(ptbl, i)
Definition: ptbl.h:108
void bu_vls_sprintf(struct bu_vls *vls, const char *fmt,...) _BU_ATTR_PRINTF23
Definition: vls.c:707
surface_t GetSurfaceType(const ON_Surface *in_surface, struct filter_obj *obj)
#define BU_GET(_ptr, _type)
Definition: malloc.h:201
void filter_obj_init(struct filter_obj *obj)
struct bu_ptbl * children
void array_to_set(std::set< int > *set, int *array, int array_cnt)
#define BREP_SPHERICAL_TOL
void add_loops_from_face(ON_BrepFace *face, struct subbrep_object_data *data, std::set< int > *loops, std::queue< int > *local_loops, std::set< int > *processed_loops)
ON_Cone * cone
#define BU_PUT(_ptr, _type)
Definition: malloc.h:215
Definition: joint.h:84
char * bu_vls_addr(const struct bu_vls *vp)
Definition: vls.c:111
void subbrep_object_init(struct subbrep_object_data *obj, ON_Brep *brep)
#define BU_PTBL_LEN(ptbl)
Definition: ptbl.h:107
void bu_ptbl_free(struct bu_ptbl *b)
Definition: ptbl.c:226
void subbrep_object_free(struct subbrep_object_data *obj)
int subbrep_split(struct subbrep_object_data *data)
surface_t
int cylinder_csg(struct subbrep_object_data *data, fastf_t cyl_tol)
std::string face_set_key(std::set< int > fset)
subbrep_object_data * parent
ON_Torus * torus
int subbreps_boolean_tree(struct bu_ptbl *subbreps)
int subbrep_is_cylinder(struct subbrep_object_data *data, fastf_t cyl_tol)
struct bu_vls * key
void bu_vls_printf(struct bu_vls *vls, const char *fmt,...) _BU_ATTR_PRINTF23
Definition: vls.c:694
#define BREP_PLANAR_TOL
void set_to_array(int **array, int *array_cnt, std::set< int > *set)
surface_t stype
int subbrep_make_brep(struct subbrep_object_data *data)
void print_subbrep_object(struct subbrep_object_data *data, const char *offset)
#define BREP_ELLIPSOIDAL_TOL
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
volume_t subbrep_shape_recognize(struct subbrep_object_data *data)
#define BU_VLS_INIT_ZERO
Definition: vls.h:84
ON_Sphere * sphere
Definition: vls.h:56
ON_Cylinder * cylinder
csg_object_params * params
int cone_csg(struct subbrep_object_data *data, fastf_t cone_tol)