BRL-CAD
nmg_manif.c
Go to the documentation of this file.
1 /* N M G _ M A N I F . C
2  * BRL-CAD
3  *
4  * Copyright (c) 1994-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 nmg */
21 /** @{ */
22 /** @file primitives/nmg/nmg_manif.c
23  *
24  * Routines for assessing the manifold dimension of an object.
25  *
26  */
27 /** @} */
28 
29 #include "common.h"
30 
31 #include <string.h>
32 #include "bio.h"
33 
34 #include "vmath.h"
35 #include "nmg.h"
36 #include "raytrace.h"
37 
38 #define PAINT_INTERIOR 1
39 #define PAINT_EXTERIOR 0
40 
41 #define BU_LIST_LINK_CHECK(p) \
42  if (BU_LIST_PNEXT_PLAST(bu_list, p) != p || \
43  BU_LIST_PLAST_PNEXT(bu_list, p) != p) { \
44  bu_log("%s[%d]: linked list integrity check failed\n", \
45  __FILE__, __LINE__); \
46  bu_log("%p->forw(%p)->back = %p\n", \
47  (void *)(p), (void *)(p)->forw, (void *)(p)->forw->back); \
48  bu_log("%p->back(%p)->forw = %p\n", \
49  (void *)(p), (void *)(p)->back, (void *)(p)->back->forw); \
50  bu_bomb("Goodbye\n"); \
51  }
52 
53 
54 /**
55  * Determine if a face has any "dangling" edges.
56  *
57  * Return
58  * 1 face has dangling edge
59  * 0 face does not have a dangling edge
60  */
61 int
62 nmg_dangling_face(const struct faceuse *fu, register const char *manifolds)
63 {
64  struct loopuse *lu;
65  struct edgeuse *eu;
66  const struct edgeuse *eur;
67  struct faceuse *newfu;
68 
69  NMG_CK_FACEUSE(fu);
70 
71  if (RTG.NMG_debug & DEBUG_MANIF)
72  bu_log("nmg_dangling_face(%p %s)\n", (void *)fu, manifolds);
73 
74  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
75  NMG_CK_LOOPUSE(lu);
76  BU_LIST_LINK_CHECK(&lu->l);
77 
78  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) == NMG_EDGEUSE_MAGIC) {
79  /* go looking around each edge for a face of the same
80  * shell which isn't us and isn't our mate. If we
81  * find us or our mate before another face of this
82  * shell, we are non-3-manifold.
83  */
84 
85  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
86 
87  NMG_CK_EDGEUSE(eu);
88  BU_LIST_LINK_CHECK(&eu->l);
89 
91  newfu = eur->up.lu_p->up.fu_p;
92 
93  /* skip any known dangling-edge faces or
94  * faces known to be 2manifolds.
95  */
96  while (manifolds &&
97  NMG_MANIFOLDS(manifolds, newfu) & NMG_2MANIFOLD &&
98  eur != eu->eumate_p) {
100  eur->eumate_p);
101  newfu = eur->up.lu_p->up.fu_p;
102  }
103 
104  if (eur == eu->eumate_p) {
105  goto out;
106  }
107  }
108  }
109  }
110  eur = (const struct edgeuse *)NULL;
111 
112 out:
113  if (RTG.NMG_debug & DEBUG_BASIC) {
114  struct bn_tol tol; /* HACK */
115  tol.magic = BN_TOL_MAGIC;
116  tol.dist = 1;
117  tol.dist_sq = tol.dist * tol.dist;
118  tol.perp = 1e-5;
119  tol.para = 1 - tol.perp;
120 
121  bu_log("nmg_dangling_face(fu=%p, manifolds=%s) dangling_eu=%p\n", (void *)fu, manifolds, (void *)eur);
122  if (eur) nmg_pr_fu_around_eu(eur, &tol);
123  }
124  if ((RTG.NMG_debug & DEBUG_MANIF) && (eur != (const struct edgeuse *)NULL))
125  bu_log("\tdangling eu %p\n", (void *)eur);
126 
127  return eur != (const struct edgeuse *)NULL;
128 }
129 
130 
131 /**
132  * "Paint" the elements of a face with a meaning. For example
133  * mark everything in a face as being part of a 2-manifold
134  */
135 static void paint_face(struct faceuse *fu, long *paint_table, long paint_color, char *paint_meaning, char *tbl)
136 {
137  struct faceuse *newfu;
138  struct loopuse *lu;
139  struct edgeuse *eu;
140  const struct edgeuse *eur;
141 
142  if (RTG.NMG_debug & DEBUG_MANIF)
143  bu_log("nmg_paint_face(%p, %ld)\n", (void *)fu, paint_color);
144 
145  if (NMG_INDEX_VALUE(paint_table, fu->index) != 0)
146  return;
147 
148  NMG_INDEX_ASSIGN(paint_table, fu, paint_color);
149 
150  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
151 
152  if (RTG.NMG_debug & DEBUG_MANIF)
153  bu_log("\tlu=%p\n", (void *)lu);
154 
155  NMG_CK_LOOPUSE(lu);
156  BU_LIST_LINK_CHECK(&lu->l);
157 
158  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) != NMG_EDGEUSE_MAGIC)
159  continue;
160 
161  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
162  if (RTG.NMG_debug & DEBUG_MANIF)
163  bu_log("\t\teu=%p\n", (void *)eu);
164  NMG_CK_EDGEUSE(eu);
165  NMG_CK_EDGEUSE(eu->eumate_p);
167  NMG_CK_EDGEUSE(eur);
168  NMG_CK_FACEUSE(eur->up.lu_p->up.fu_p);
169  newfu = eur->up.lu_p->up.fu_p;
170 
171  if (RTG.NMG_debug & DEBUG_MANIF)
172  bu_log("\t\t\teur=%p, newfu=%p\n", (void *)eur, (void *)newfu);
173 
174  BU_LIST_LINK_CHECK(&eu->l);
175  BU_LIST_LINK_CHECK(&eur->l);
176 
177  while (NMG_MANIFOLDS(tbl, newfu) & NMG_2MANIFOLD &&
178  eur != eu->eumate_p) {
180  eur->eumate_p);
181  newfu = eur->up.lu_p->up.fu_p;
182 
183  if (RTG.NMG_debug & DEBUG_MANIF)
184  bu_log("\t\t\teur=%p, newfu=%p\n", (void *)eur, (void *)newfu);
185  }
186 
187  if (newfu == fu->fumate_p)
188  continue;
189  else if (newfu->orientation == OT_SAME)
190  paint_face(newfu, paint_table, paint_color,
191  paint_meaning, tbl);
192  else {
193  /* mark this group as being interior */
194  paint_meaning[paint_color] = PAINT_INTERIOR;
195 
196  if (RTG.NMG_debug & DEBUG_MANIF)
197  bu_log("\t---- Painting fu %p as interior, new_fu = %p, eu=%p, eur=%p\n",
198  (void *)fu, (void *)newfu, (void *)eu, (void *)eur);
199  }
200  }
201  }
202 }
203 
204 
205 static void set_edge_sub_manifold(char *tbl, struct edgeuse *eu_p, char manifold)
206 {
207 
208  NMG_CK_EDGEUSE(eu_p);
209  NMG_CK_EDGE(eu_p->e_p);
210  NMG_CK_VERTEXUSE(eu_p->vu_p);
211  NMG_CK_VERTEX(eu_p->vu_p->v_p);
212 
213  NMG_SET_MANIFOLD(tbl, eu_p, manifold);
214  NMG_SET_MANIFOLD(tbl, eu_p->e_p, manifold);
215 
216  NMG_SET_MANIFOLD(tbl, eu_p->vu_p, manifold);
217  NMG_SET_MANIFOLD(tbl, eu_p->vu_p->v_p, manifold);
218 }
219 
220 
221 static void set_loop_sub_manifold(char *tbl, struct loopuse *lu_p, char manifold)
222 {
223  struct edgeuse *eu_p;
224  struct vertexuse *vu_p;
225 
226  NMG_CK_LOOPUSE(lu_p);
227 
228  NMG_SET_MANIFOLD(tbl, lu_p, manifold);
229  NMG_SET_MANIFOLD(tbl, lu_p->l_p, manifold);
230  if (BU_LIST_FIRST_MAGIC(&lu_p->down_hd) == NMG_VERTEXUSE_MAGIC) {
231  vu_p = BU_LIST_FIRST(vertexuse, &lu_p->down_hd);
232  NMG_SET_MANIFOLD(tbl, vu_p, manifold);
233  NMG_SET_MANIFOLD(tbl, vu_p->v_p, manifold);
234  } else if (BU_LIST_FIRST_MAGIC(&lu_p->down_hd) == NMG_EDGEUSE_MAGIC) {
235  for (BU_LIST_FOR(eu_p, edgeuse, &lu_p->down_hd)) {
236  BU_LIST_LINK_CHECK(&eu_p->l);
237  set_edge_sub_manifold(tbl, eu_p, manifold);
238  }
239  } else
240  bu_bomb("bad child of loopuse\n");
241 }
242 static void set_face_sub_manifold(char *tbl, struct faceuse *fu_p, char manifold)
243 {
244  struct loopuse *lu_p;
245 
246  NMG_CK_FACEUSE(fu_p);
247  NMG_CK_FACE(fu_p->f_p);
248 
249  NMG_SET_MANIFOLD(tbl, fu_p, manifold);
250  NMG_SET_MANIFOLD(tbl, fu_p->f_p, manifold);
251  for (BU_LIST_FOR(lu_p, loopuse, &fu_p->lu_hd)) {
252  BU_LIST_LINK_CHECK(&lu_p->l);
253  set_loop_sub_manifold(tbl, lu_p, manifold);
254  }
255 }
256 
257 
258 char *
259 nmg_shell_manifolds(struct shell *sp, char *tbl)
260 {
261  struct edgeuse *eu_p;
262  struct loopuse *lu_p;
263  struct faceuse *fu_p;
264  char *paint_meaning;
265  long *paint_table;
266  long paint_color;
267  int found;
268 
269  if (RTG.NMG_debug & DEBUG_MANIF)
270  bu_log("nmg_shell_manifolds(%p)\n", (void *)sp);
271 
272  NMG_CK_SHELL(sp);
273 
274  if (tbl == (char *)NULL)
275  tbl = (char *)bu_calloc(sp->r_p->m_p->maxindex, 1, "manifold table");
276 
277  /*
278  * points in shells form 0-manifold objects.
279  */
280  if (sp->vu_p) {
281  NMG_CK_VERTEXUSE(sp->vu_p);
282  NMG_SET_MANIFOLD(tbl, sp, NMG_0MANIFOLD);
283  NMG_SET_MANIFOLD(tbl, sp->vu_p, NMG_0MANIFOLD);
284  NMG_SET_MANIFOLD(tbl, sp->vu_p->v_p, NMG_0MANIFOLD);
285  BU_LIST_LINK_CHECK(&sp->vu_p->l);
286  }
287 
288  /* edges in shells are (components of)
289  * 1-manifold objects.
290  */
291  if (BU_LIST_NON_EMPTY(&sp->eu_hd)) {
292 
293  for (BU_LIST_FOR(eu_p, edgeuse, &sp->eu_hd)) {
294  BU_LIST_LINK_CHECK(&eu_p->l);
295  set_edge_sub_manifold(tbl, eu_p, NMG_1MANIFOLD);
296  }
297  NMG_SET_MANIFOLD(tbl, sp, NMG_1MANIFOLD);
298  }
299 
300  /* loops in shells are (components of)
301  * 1-manifold objects.
302  */
303  if (BU_LIST_NON_EMPTY(&sp->lu_hd)) {
304 
305  for (BU_LIST_FOR(lu_p, loopuse, &sp->lu_hd)) {
306  BU_LIST_LINK_CHECK(&lu_p->l);
307 
308  set_loop_sub_manifold(tbl, lu_p, NMG_1MANIFOLD);
309  }
310  NMG_SET_MANIFOLD(tbl, sp, NMG_1MANIFOLD);
311  }
312 
313  if (RTG.NMG_debug & DEBUG_MANIF)
314  bu_log("starting manifold classification on shell faces\n");
315 
316  /*
317  * faces may be either 2 or 3 manifold components.
318  */
319  if (BU_LIST_IS_EMPTY(&sp->fu_hd))
320  return tbl;
321 
322 
323  /* mark all externally dangling faces and faces
324  * with or adjacent to dangling edges.
325  */
326  do {
327  found = 0;
328  for (BU_LIST_FOR(fu_p, faceuse, &sp->fu_hd)) {
329  NMG_CK_FACEUSE(fu_p);
330  BU_LIST_LINK_CHECK(&fu_p->l);
331 
332  /* if this has already been marked as a 2-manifold
333  * then we don't need to check it again
334  */
335  if (NMG_MANIFOLDS(tbl, fu_p) & NMG_2MANIFOLD)
336  continue;
337 
338  if (nmg_dangling_face(fu_p, tbl)) {
339  found = 1;
340 
341  NMG_SET_MANIFOLD(tbl, fu_p, NMG_2MANIFOLD);
342 
343  if (RTG.NMG_debug & DEBUG_MANIF)
344  bu_log("found dangling face\n");
345  }
346  }
347  } while (found);
348 
349  /* paint the exterior faces to discover what the
350  * actual enclosing shell is
351  */
352 
353  if (RTG.NMG_debug & DEBUG_MANIF)
354  bu_log("starting to paint non-dangling faces\n");
355 
356  paint_meaning = (char *)bu_calloc(sp->r_p->m_p->maxindex, sizeof(char), "paint meaning table");
357  paint_table = (long *)bu_calloc(sp->r_p->m_p->maxindex, sizeof(long), "paint table");
358  paint_color = 1;
359 
360  for (BU_LIST_FOR(fu_p, faceuse, &sp->fu_hd)) {
361  BU_LIST_LINK_CHECK(&fu_p->l);
362 
363  if (fu_p->orientation != OT_SAME ||
364  NMG_INDEX_VALUE(paint_table, fu_p->index) != 0)
365  continue;
366 
367  paint_face(fu_p, paint_table, paint_color, paint_meaning, tbl);
368  paint_color++;
369  }
370 
371  if (RTG.NMG_debug & DEBUG_MANIF)
372  bu_log("painting done, looking at colors\n");
373 
374  /* all the faces painted with "interior" paint are 2manifolds
375  * those faces still painted with "exterior" paint are
376  * 3manifolds, i.e. part of the enclosing surface
377  */
378  for (BU_LIST_FOR(fu_p, faceuse, &sp->fu_hd)) {
379  BU_LIST_LINK_CHECK(&fu_p->l);
380  paint_color = NMG_INDEX_VALUE((long *)paint_table, fu_p->index);
381 
382  /* this should never trigger. */
383  /* it is easier to compare against the max model index */
384  if (paint_color > sp->r_p->m_p->maxindex - 1) {
385  bu_log("nmg_shell_manifolds(): ERROR, color index out of range (%ld > %ld)\n",
386  paint_color, sp->r_p->m_p->maxindex - 1);
387  bu_bomb("nmg_shell_manifolds(): ERROR, color index out of range\n");
388  break;
389  }
390 
391  if (NMG_INDEX_VALUE(paint_meaning, paint_color) == PAINT_INTERIOR) {
392  set_face_sub_manifold(tbl, fu_p, NMG_2MANIFOLD);
393  } else if (NMG_INDEX_VALUE(paint_meaning, paint_color) == PAINT_EXTERIOR) {
394  set_face_sub_manifold(tbl, fu_p, NMG_3MANIFOLD);
395  }
396  }
397 
398  bu_free(paint_meaning, "paint meaning table");
399  bu_free(paint_table, "paint table");
400 
401  for (BU_LIST_FOR(fu_p, faceuse, &sp->fu_hd)) {
402  BU_LIST_LINK_CHECK(&fu_p->l);
403 
404  if (fu_p->orientation != OT_SAME)
405  NMG_CP_MANIFOLD(tbl, fu_p, fu_p->fumate_p);
406  }
407 
408  return tbl;
409 }
410 
411 
412 char *
413 nmg_manifolds(struct model *m)
414 {
415  struct nmgregion *rp;
416  struct shell *sp;
417  char *tbl;
418 
419 
420  NMG_CK_MODEL(m);
421  if (RTG.NMG_debug & DEBUG_MANIF)
422  bu_log("nmg_manifolds(%p)\n", (void *)m);
423 
424  tbl = (char *)bu_calloc(m->maxindex, 1, "manifold table");
425 
426 
427  for (BU_LIST_FOR(rp, nmgregion, &m->r_hd)) {
428  NMG_CK_REGION(rp);
429  BU_LIST_LINK_CHECK(&rp->l);
430 
431  for (BU_LIST_FOR(sp, shell, &rp->s_hd)) {
432 
433  NMG_CK_SHELL(sp);
434  BU_LIST_LINK_CHECK(&sp->l);
435 
436  nmg_shell_manifolds(sp, tbl);
437 
438  /* make sure the region manifold bits are a superset
439  * of the shell manifold bits
440  */
441  NMG_CP_MANIFOLD(tbl, rp, sp);
442  }
443  }
444 
445  return tbl;
446 }
447 
448 
449 /*
450  * Local Variables:
451  * mode: C
452  * tab-width: 8
453  * indent-tabs-mode: t
454  * c-file-style: "stroustrup"
455  * End:
456  * ex: shiftwidth=4 tabstop=8
457  */
#define BU_LIST_FOR(p, structure, hp)
Definition: list.h:365
#define NMG_EDGEUSE_MAGIC
Definition: magic.h:120
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
#define BU_LIST_LINK_CHECK(p)
Definition: nmg_manif.c:41
double dist
>= 0
Definition: tol.h:73
lu
Definition: nmg_mod.c:3855
#define BU_LIST_IS_EMPTY(hp)
Definition: list.h:295
double dist_sq
dist * dist
Definition: tol.h:74
#define BN_TOL_MAGIC
Definition: magic.h:74
Header file for the BRL-CAD common definitions.
#define BU_LIST_NON_EMPTY(hp)
Definition: list.h:296
NMG_CK_LOOPUSE(lu)
char * nmg_manifolds(struct model *m)
Definition: nmg_manif.c:413
uint32_t NMG_debug
debug bits for NMG's see nmg.h
Definition: raytrace.h:1699
void * bu_calloc(size_t nelem, size_t elsize, const char *str)
Definition: malloc.c:321
#define PAINT_EXTERIOR
Definition: nmg_manif.c:39
#define PAINT_INTERIOR
Definition: nmg_manif.c:38
goto out
Definition: nmg_mod.c:3846
Support for uniform tolerances.
Definition: tol.h:71
#define BU_LIST_FIRST_MAGIC(hp)
Definition: list.h:416
#define NMG_VERTEXUSE_MAGIC
Definition: magic.h:145
oldeumate e_p eu_p
Definition: nmg_mod.c:3940
double perp
nearly 0
Definition: tol.h:75
uint32_t magic
Definition: tol.h:72
int nmg_dangling_face(const struct faceuse *fu, register const char *manifolds)
Definition: nmg_manif.c:62
void nmg_pr_fu_around_eu(const struct edgeuse *eu, const struct bn_tol *tol)
Definition: nmg_pr.c:953
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
NMG_CK_SHELL(s)
const struct edgeuse * nmg_radial_face_edge_in_shell(const struct edgeuse *eu)
Definition: nmg_info.c:1021
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
double para
nearly 1
Definition: tol.h:76
char * nmg_shell_manifolds(struct shell *sp, char *tbl)
Definition: nmg_manif.c:259
#define BU_LIST_FIRST(structure, hp)
Definition: list.h:312
struct rt_g RTG
Definition: globals.c:39