BRL-CAD
nmg_mk.c
Go to the documentation of this file.
1 /* N M G _ M K . 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_mk.c
23  *
24  * Support routines for n-Manifold Geometry.
25  *
26  * Naming convention
27  * nmg_m* routines "make" NMG structures.
28  * nmg_k* routines "kill" (delete) NMG structures.
29  *
30  * in each of the above cases the letters or words following are an
31  * attempt at a mnemonic representation for what is manipulated
32  *
33  * m Model
34  * r Region
35  * s shell
36  * f face
37  * fu faceuse
38  * l loop
39  * lu loopuse
40  * e edge
41  * eu edgeuse
42  * v vertex
43  * vu vertexuse
44  *
45  *
46  * Rules:
47  *
48  * edges of loops of the same face must not overlap
49  * XXX - What does "overlap" mean? ctj
50  * the "magic" member of each struct is the first item.
51  *
52  * All routines which create and destroy the NMG data structures are
53  * contained in this module.
54  *
55  */
56 /** @} */
57 
58 #include "common.h"
59 
60 #include <stddef.h>
61 #include <math.h>
62 #include <string.h>
63 #include "bio.h"
64 
65 #include "vmath.h"
66 #include "nmg.h"
67 #include "raytrace.h"
68 #include "nurb.h"
69 
70 
71 /************************************************************************
72  * *
73  * "Make" Routines *
74  * *
75  * The subroutines create new topological entities and return a *
76  * pointer to the new entity. *
77  * *
78  ************************************************************************/
79 
80 
81 /**
82  * The nmg_m*() routines are used to create a topology-only object
83  * which at first has no geometry associated with it at all.
84  * A topology-only object can be used to answer questions like:
85  * is this vertex ON this shell?
86  * is this vertex ON this face?
87  * is this vertex ON this edge?
88  * Is this face ON this shell?
89  * and many more.
90  *
91  * After the topology has been built, most applications will proceed to
92  * associate geometry with the topology, primarily by supplying
93  * Cartesian coordinates for each struct vertex, and by supplying
94  * or computing face normals for the planar faces. (Linear edge geometry
95  * is optional, as it is implicit from the vertex geometry).
96  *
97  * Objects which have been fully populated with geometry can be used to
98  * answer questions about where things are located and how large they are.
99  *
100  * The abstract objects are:
101  * model, nmgregion, shell, face, loop, edge and vertex.
102  * The uses of those objects are:
103  * faceuse, loopuse, edgeuse and vertexuse.
104  * Geometry can optionally be associated with the abstract objects:
105  * face_g (plane equation, bounding box)
106  * loop_g (just a bounding box, for planar faces)
107  * edge_g (to track edge subdivision heritage, for linear edges)
108  * vertex_g (Cartesian coordinates)
109  * The uses of those objects can optionally have attributes:
110  * nmgregion_a (region bounding box) [nmgregions have no uses]
111  * shell_a (shell bounding box) [shells have no uses]
112  * vertexuse_a (special surface normal, for normal interpolation)
113  *
114  * Consider for example a simple cube.
115  *
116  * As a topology-only object, it would have the following structures:
117  *
118  * 1 model structure
119  * This is the handle which everything else hangs on.
120  * The model structure r_hd references 1 region structure.
121  * 1 nmgregion structure.
122  * The region structure s_hd references 1 shell structure.
123  * Also, m_p references the model.
124  * 1 shell structure.
125  * The shell structure fu_hd references 12 faceuse structures.
126  * One for each side of each of the 6 faces of the cube.
127  * Also, r_p references the nmgregion.
128  * 12 faceuse structures.
129  * Each faceuse structure lu_hd references 1 loopuse structure.
130  * Also, 1 face structure and 1 faceuse structure (its mate),
131  * plus s_p references the shell.
132  * 6 face structures.
133  * Each face structure fu_p references a random choice of 1 of
134  * the two parent faceuse structures sharing this face, and is
135  * in turn referenced by that faceuse and its mate.
136  * 12 loopuse structures
137  * Each loopuse structure down_hd references 4 edgeuse structures.
138  * Also, 1 loop structure, and 1 loopuse structure (its mate).
139  * The four edgeuse structures define the perimeter of the
140  * surface area that comprises this face.
141  * Because their orientation is OT_SAME, each loopuse "claims"
142  * all the surface area inside it for the face.
143  * (OT_OPPOSITE makes a hole, claiming surface area outside).
144  * Plus, "up" references the parent object (faceuse, here).
145  * 6 loop structures
146  * Each loop structure references a random choice of 1 of its
147  * parent loopuse structures and is in turn referenced by that
148  * loopuse and its mate.
149  * 48 edgeuse structures
150  * Each edgeuse structure references 1 vertexuse structure,
151  * 1 edge structure, and 2 other edgeuse structures (its mate
152  * and the next edgeuse radial to this edgeuse).
153  * (if this edge was NOT used in another face, then the
154  * radial pointer and mate pointer would point to the SAME
155  * edgeuse)
156  * To find all edgeuses around a given edge, follow radial to
157  * mate to radial to mate until you are back to the original
158  * edgeuse.
159  * Plus, "up" references the parent object (loopuse, here).
160  * 12 edge structures
161  * Each edge structure references a random choice of one of
162  * its parent edgeuse structures and is in turn referenced
163  * by that edgeuse, the mate of that edgeuse, the radial of
164  * that edgeuse and the mate of the radial. (In this simple
165  * case of the cube, there are 4 edgeuses per edge).
166  * 48 vertexuse structures.
167  * Each vertexuse structure references one vertex structure
168  * and is in turn enrolled as a member of the linked list
169  * headed by that vertex structure.
170  * Each vertexuse is cited by exactly one edgeuse.
171  * Also, "up" references the parent object (edgeuse, here).
172  * 8 vertex structures
173  * Each vertex structure references 6 vertexuse structures
174  * via its linked list. (In the case of the cube,
175  * there are three faces meeting at each vertex, and each of
176  * those faces has two faceuse structs of one loopuse each. Each
177  * loopuse will cite the vertex via one edgeuse, so 3*2 = 6).
178  *
179  * As well as each "use" pointing down to what it uses, the "use" points
180  * up to the structure that uses it. So working up from any abstract object
181  * or its use, the top of the tree (struct model) can be found.
182  * Working down from the struct model, all elements of the object can be
183  * visited.
184  *
185  * The object just described contains no geometry. There is no way to tell
186  * where in space the object lies or how big it is.
187  *
188  * To add geometry, the following structures are needed:
189  * 8 vertex_g structures
190  * each vertex_g structure contains a point in space (point_t)
191  * and is referenced by 1 vertex structure.
192  * 12 edge_g structures (completely optional)
193  * each edge_g structure contains the parametric definition of
194  * the line which contains the line segment which is the edge,
195  * given as a point in space and a direction vector. It is
196  * referenced by 1 edge structure. (In general, it is referenced
197  * by all edges sharing that line).
198  * In a simple case the point would be the same as one of
199  * the vertex_g points and the direction would be the normalized
200  * (unit) vector of the difference between the two vertex_g points.
201  * 6 loop_g structures
202  * Each loop_g structure contains a bounding box for the loop.
203  * It is referenced by 1 loop structure.
204  * 6 face_g_plane structures
205  * Each face_g_plane structure contains a plane equation and
206  * a bounding box. It is referenced by one face structure.
207  * The plane equation is calculated from the vertex_g data
208  * by nmg_fu_planeeqn().
209  * See h/vmath.h for the definition of a plane equation.
210  * 1 shell_a structure
211  * Each shell_a structure contains the bounding box for the
212  * shell. It is referenced by 1 shell structure.
213  * 1 nmgregion_a structure
214  * Each nmgregion_a structure contains the bounding box for the
215  * region. It is referenced by 1 region structure.
216  *
217  */
218 
219 
220 /**
221  * Make Model
222  *
223  * Create a new model. The region list is empty. Creates a new model
224  * structure. The model region structure list is empty.
225  *
226  * Returns -
227  * (struct model *)
228  *
229  * "maxindex" is a misnomer. It is the value of the NEXT index
230  * assigned. This allows "ptab"s to be allocated easily using maxindex
231  * and the index value of the structures to be the actual index into
232  * the "ptab".
233  */
234 struct model *
235 nmg_mm(void)
236 {
237  struct model *m;
238 
239  NMG_GETSTRUCT(m, model);
240 
241  BU_LIST_INIT(&m->r_hd);
242  m->index = 0;
243  m->maxindex = 1;
244  m->magic = NMG_MODEL_MAGIC; /* Model Structure is GOOD */
245  m->manifolds = (char *)NULL;
246 
247  if (RTG.NMG_debug & DEBUG_BASIC) {
248  bu_log("nmg_mm() returns model %p\n", (void *)m);
249  }
250 
251  return m;
252 }
253 
254 
255 /**
256  * Make Model and Region.
257  *
258  * Create a new model, and an "empty" region to go with it.
259  * Essentially this creates a minimal model system.
260  *
261  * Returns -
262  * (struct model *)
263  *
264  * Implicit Return -
265  * The new region is found with BU_LIST_FIRST(nmgregion, &m->r_hd);
266  */
267 struct model *
268 nmg_mmr(void)
269 {
270  struct model *m;
271  struct nmgregion *r;
272 
273  m = nmg_mm();
274  GET_REGION(r, m);
275 
276  r->m_p = m;
277 
278  r->ra_p = (struct nmgregion_a *)NULL;
279  BU_LIST_INIT(&r->s_hd);
280  r->l.magic = NMG_REGION_MAGIC; /* Region Structure is GOOD */
281 
282  BU_LIST_APPEND(&m->r_hd, &r->l);
283 
284  if (RTG.NMG_debug & DEBUG_BASIC) {
285  bu_log("nmg_mmr() returns model %p with region %p\n", (void *)m, (void *)r);
286  }
287 
288  return m;
289 }
290 
291 
292 /**
293  * Make new region, shell, vertex in model as well as the required
294  * "uses". Create a new region in model consisting of a minimal
295  * shell.
296  *
297  * Returns -
298  * (struct nmgregion *)
299  *
300  * Implicit Returns -
301  * Region is also found with r=BU_LIST_FIRST(nmgregion, &m->r_hd);
302  * The new shell is found with s=BU_LIST_FIRST(shell, &r->s_hd);
303  * The new vertexuse is s->vu_p;
304  */
305 struct nmgregion *
306 nmg_mrsv(struct model *m)
307 {
308  struct nmgregion *r;
309 
310  NMG_CK_MODEL(m);
311 
312  GET_REGION(r, m);
313  r->m_p = m;
314  r->ra_p = (struct nmgregion_a *) NULL;
315 
316  BU_LIST_INIT(&r->s_hd);
317  r->l.magic = NMG_REGION_MAGIC; /* Region struct is GOOD */
318 
319  (void)nmg_msv(r);
320 
321  /* new region goes at "head" of list of regions in model */
322  BU_LIST_APPEND(&m->r_hd, &r->l);
323 
324  if (RTG.NMG_debug & DEBUG_BASIC) {
325  bu_log("nmg_mrsv(m=%p) returns r=%p\n", (void *)m, (void *)r);
326  }
327 
328  return r;
329 }
330 
331 
332 /**
333  * Make Vertexuse on existing vertex
334  *
335  * This is a support routine for this module, and is not intended for
336  * general use, as it requires lots of cooperation from the caller.
337  * (Like setting the parent's down pointer appropriately).
338  *
339  * This means that a vu is created but is not attached to the parent
340  * structure. This is "bad" and requires the caller to fix.
341  *
342  * upptr is a pointer to parent struct
343  */
344 static struct vertexuse *
345 nmg_mvu(struct vertex *v, uint32_t *upptr, struct model *m)
346 {
347  struct vertexuse *vu;
348 
349  NMG_CK_VERTEX(v);
350  NMG_CK_MODEL(m);
351 
352  if (*upptr != NMG_SHELL_MAGIC &&
353  *upptr != NMG_LOOPUSE_MAGIC &&
354  *upptr != NMG_EDGEUSE_MAGIC) {
355  bu_log("nmg_mvu() in %s:%d magic not shell, loop, or edge. Was %x (%s)\n",
356  __FILE__, __LINE__,
357  *upptr, bu_identify_magic(*upptr));
358  bu_bomb("nmg_mvu() Cannot build vertexuse without parent\n");
359  }
360 
361  GET_VERTEXUSE(vu, m);
362 
363  vu->v_p = v;
364  vu->a.plane_p = (struct vertexuse_a_plane *)NULL;
365  BU_LIST_APPEND(&v->vu_hd, &vu->l);
366  vu->up.magic_p = upptr;
367  vu->l.magic = NMG_VERTEXUSE_MAGIC; /* Vertexuse struct is GOOD */
368 
369  if (RTG.NMG_debug & DEBUG_BASIC) {
370  bu_log("nmg_mvu(v=%p, up=%p) returns vu=%p\n",
371  (void *)v, (void *)upptr, (void *)vu);
372  }
373  return vu;
374 }
375 
376 
377 /**
378  * Make Vertex, Vertexuse
379  *
380  * This is a support routine for this module, and is not intended for
381  * general use, as it requires lots of cooperation from the caller.
382  * (Like setting the parent's down pointer appropriately).
383  *
384  * This means that a vu is created but is not attached to the parent
385  * structure. This is "bad" and requires the caller to fix.
386  */
387 static struct vertexuse *
388 nmg_mvvu(uint32_t *upptr, struct model *m)
389 {
390  struct vertex *v;
391  struct vertexuse *ret_vu;
392 
393  NMG_CK_MODEL(m);
394  GET_VERTEX(v, m);
395  BU_LIST_INIT(&v->vu_hd);
396  v->vg_p = (struct vertex_g *)NULL;
397  v->magic = NMG_VERTEX_MAGIC; /* Vertex struct is GOOD */
398  ret_vu = nmg_mvu(v, upptr, m);
399 
400  if (RTG.NMG_debug & DEBUG_BASIC) {
401  bu_log("nmg_mvvu(upptr=%p, m=%p) returns vu=%p\n",
402  (void *)upptr, (void *)m, (void *)ret_vu);
403  }
404 
405  return ret_vu;
406 }
407 
408 
409 /**
410  * Make Shell, Vertex Use, Vertex
411  *
412  * Create a new shell in a specified region. The shell will consist
413  * of a single vertexuse and vertex (which are also created).
414  *
415  * Returns -
416  * (struct shell *)
417  *
418  * Implicit Returns -
419  * The new shell is also found with s=BU_LIST_FIRST(shell, &r->s_hd);
420  * The new vertexuse is s->vu_p;
421  */
422 struct shell *
423 nmg_msv(struct nmgregion *r)
424 {
425  struct shell *s;
426  struct vertexuse *vu;
427 
428  NMG_CK_REGION(r);
429 
430  /* set up shell */
431  GET_SHELL(s, r->m_p);
432 
433  s->r_p = r;
434  BU_LIST_APPEND(&r->s_hd, &s->l);
435 
436  s->sa_p = (struct shell_a *)NULL;
437  BU_LIST_INIT(&s->fu_hd);
438  BU_LIST_INIT(&s->lu_hd);
439  BU_LIST_INIT(&s->eu_hd);
440  s->vu_p = (struct vertexuse *) NULL;
441  s->l.magic = NMG_SHELL_MAGIC; /* Shell Struct is GOOD */
442 
443  vu = nmg_mvvu(&s->l.magic, r->m_p);
444  s->vu_p = vu;
445 
446  if (RTG.NMG_debug & DEBUG_BASIC) {
447  bu_log("nmg_msv(r=%p) returns s=%p, vu=%p\n", (void *)r, (void *)s, (void *)s->vu_p);
448  }
449 
450  return s;
451 }
452 
453 
454 /**
455  * Make Face from a wire loop.
456  *
457  * make a face from a pair of loopuses. The loopuses must be direct
458  * children of a shell. The new face will be a child of the same
459  * shell.
460  *
461  * Given a wire loop (by definition, a loop attached to a shell),
462  * create a new face, faceuse (and mate) and move the wire loop from
463  * the shell to the new faceuse (and mate).
464  *
465  * Implicit Returns -
466  * The first faceuse is fu1=BU_LIST_FIRST(faceuse, &s->fu_hd);
467  * The second faceuse follows: fu2=BU_LIST_NEXT(faceuse, &fu1->l.magic);
468  */
469 struct faceuse *
470 nmg_mf(struct loopuse *lu1)
471 {
472  struct face *f;
473  struct faceuse *fu1, *fu2;
474  struct loopuse *lu2;
475  struct shell *s;
476  struct model *m;
477 
478  NMG_CK_LOOPUSE(lu1);
479  if (*lu1->up.magic_p != NMG_SHELL_MAGIC) {
480  bu_bomb("nmg_mf() loop must be child of shell for making face\n");
481  }
482  lu2 = lu1->lumate_p;
483  NMG_CK_LOOPUSE(lu2);
484  if (lu2->up.magic_p != lu1->up.magic_p) {
485  bu_bomb("nmg_mf() loopuse mate does not have same parent\n");
486  }
487 
488  s = lu1->up.s_p;
489  NMG_CK_SHELL(s);
490 
491  m = nmg_find_model(&s->l.magic);
492  GET_FACE(f, m);
493  GET_FACEUSE(fu1, m);
494  GET_FACEUSE(fu2, m);
495 
496  f->fu_p = fu1;
497  f->g.plane_p = (struct face_g_plane *)NULL;
498  f->flip = 0;
499  BU_LIST_INIT(&f->l);
500  f->l.magic = NMG_FACE_MAGIC; /* Face struct is GOOD */
501 
502  BU_LIST_INIT(&fu1->lu_hd);
503  BU_LIST_INIT(&fu2->lu_hd);
504  fu1->s_p = fu2->s_p = s;
505  fu1->fumate_p = fu2;
506  fu2->fumate_p = fu1;
507  fu1->orientation = fu2->orientation = OT_UNSPEC;
508  fu1->f_p = fu2->f_p = f;
509  fu1->l.magic =
510  fu2->l.magic = NMG_FACEUSE_MAGIC; /* Faceuse structs are GOOD */
511 
512  /* move the loopuses from the shell to the faceuses */
513  BU_LIST_DEQUEUE(&lu1->l);
514  BU_LIST_DEQUEUE(&lu2->l);
515  BU_LIST_APPEND(&fu1->lu_hd, &lu1->l);
516  BU_LIST_APPEND(&fu2->lu_hd, &lu2->l);
517 
518  lu1->up.fu_p = fu1;
519  lu1->orientation = OT_SAME;
520  lu2->up.fu_p = fu2;
521  lu2->orientation = OT_SAME;
522 
523  /* connect the faces to the parent shell: head, fu1, fu2... */
524  BU_LIST_APPEND(&s->fu_hd, &fu1->l);
525  BU_LIST_APPEND(&fu1->l, &fu2->l);
526 
527  if (RTG.NMG_debug & DEBUG_BASIC) {
528  bu_log("nmg_mf(lu1=%p) returns fu=%p\n", (void *)lu1, (void *)fu1);
529  }
530 
531  return fu1;
532 }
533 
534 
535 /**
536  * Make a new loop (with specified orientation) and vertex, in a shell
537  * or face.
538  * XXX - vertex or vertexuse? or both? ctj
539  *
540  * If the vertex 'v' is NULL, the shell's lone vertex is used, or a
541  * new vertex is created.
542  *
543  * "magic" must point to the magic number of a faceuse or shell.
544  *
545  * If the shell has a lone vertex in it, that lone vertex *will* be
546  * used. If a non-NULL 'v' is provided, the lone vertex and 'v' will
547  * be fused together. XXX Why is this good?
548  *
549  * If a convenient shell does not exist, use s=nmg_msv() to make the
550  * shell and vertex, then call lu=nmg_mlv(s, s->vu_p->v_p, OT_SAME),
551  * followed by nmg_kvu(s->vu_p).
552  *
553  * Implicit returns -
554  * The new vertexuse can be had by:
555  * BU_LIST_FIRST(vertexuse, &lu->down_hd);
556  *
557  * In case the returned loopuse isn't retained, the new loopuse was
558  * inserted at the +head+ of the appropriate list, e.g.:
559  * lu = BU_LIST_FIRST(loopuse, &fu->lu_hd);
560  * or
561  * lu = BU_LIST_FIRST(loopuse, &s->lu_hd);
562  *
563  * N.B. This function is made more complex than warranted by using
564  * the "hack" of stealing a vertexuse structure from the shell if at
565  * all possible. A future enhancement to this function would be to
566  * remove the vertexuse steal and have the caller pass in the vertex
567  * from the shell followed by a call to nmg_kvu(s->vu_p). The v==NULL
568  * convention is used only in nmg_mod.c.
569  */
570 struct loopuse *
571 nmg_mlv(uint32_t *magic, struct vertex *v, int orientation)
572 {
573  struct loop *l;
574  struct loopuse *lu1, *lu2;
575  struct vertexuse *vu1 = NULL;
576  struct vertexuse *vu2;
577  struct model *m;
578  /* XXX - why the new union? ctj */
579  union {
580  struct shell *s;
581  struct faceuse *fu;
582  uint32_t *magic_p;
583  } p;
584 
585  p.magic_p = magic;
586 
587  if (v) {
588  NMG_CK_VERTEX(v);
589  }
590 
591  m = nmg_find_model(magic);
592  GET_LOOP(l, m);
593  GET_LOOPUSE(lu1, m);
594  GET_LOOPUSE(lu2, m);
595 
596  l->lg_p = (struct loop_g *)NULL;
597  l->lu_p = lu1;
598  l->magic = NMG_LOOP_MAGIC; /* Loop struct is GOOD */
599 
600  BU_LIST_INIT(&lu1->down_hd);
601  BU_LIST_INIT(&lu2->down_hd);
602  lu1->l_p = lu2->l_p = l;
603  lu1->orientation = lu2->orientation = orientation;
604 
605  lu1->lumate_p = lu2;
606  lu2->lumate_p = lu1;
607 
608  /* The only thing left to do to make the loopuses good is to */
609  /* set the "up" pointer and "l.magic". */
610  if (*p.magic_p == NMG_SHELL_MAGIC) {
611  struct shell *s = p.s;
612 
613  /* First, finish setting up the loopuses */
614  lu1->up.s_p = lu2->up.s_p = s;
615 
616  lu1->l.magic = lu2->l.magic =
617  NMG_LOOPUSE_MAGIC; /* Loopuse structs are GOOD */
618 
619  BU_LIST_INSERT(&s->lu_hd, &lu1->l);
620  BU_LIST_INSERT(&lu1->l, &lu2->l);
621 
622  /* Second, build the vertices */
623  /* This "if" degenerates to the "else" clause if no stealing */
624  vu1 = s->vu_p;
625  if (vu1) {
626  /* Use shell's lone vertex */
627  s->vu_p = (struct vertexuse *)NULL;
628  vu1->up.lu_p = lu1;
629  if (v) nmg_movevu(vu1, v);
630  } else {
631  if (v) vu1 = nmg_mvu(v, &lu1->l.magic, m);
632  else vu1 = nmg_mvvu(&lu1->l.magic, m);
633  }
634  NMG_CK_VERTEXUSE(vu1);
635  RT_LIST_SET_DOWN_TO_VERT(&lu1->down_hd, vu1);
636  /* vu1->up.lu_p = lu1; done by nmg_mvu/nmg_mvvu */
637 
638  vu2 = nmg_mvu(vu1->v_p, &lu2->l.magic, m);
639  NMG_CK_VERTEXUSE(vu2);
640  RT_LIST_SET_DOWN_TO_VERT(&lu2->down_hd, vu2);
641  /* vu2->up.lu_p = lu2; done by nmg_mvu() */
642  } else if (*p.magic_p == NMG_FACEUSE_MAGIC) {
643  /* First, finish setting up the loopuses */
644  lu1->up.fu_p = p.fu;
645  lu2->up.fu_p = p.fu->fumate_p;
646  lu1->l.magic = lu2->l.magic =
647  NMG_LOOPUSE_MAGIC; /* Loopuse structs are GOOD */
648 
649  BU_LIST_INSERT(&p.fu->fumate_p->lu_hd, &lu2->l);
650  BU_LIST_INSERT(&p.fu->lu_hd, &lu1->l);
651 
652  /* Second, build the vertices */
653  if (v) vu1 = nmg_mvu(v, &lu1->l.magic, m);
654  else vu1 = nmg_mvvu(&lu1->l.magic, m);
655  RT_LIST_SET_DOWN_TO_VERT(&lu1->down_hd, vu1);
656  /* vu1->up.lu_p = lu1; done by nmg_mvu/nmg_mvvu */
657 
658  vu2 = nmg_mvu(vu1->v_p, &lu2->l.magic, m);
659  RT_LIST_SET_DOWN_TO_VERT(&lu2->down_hd, vu2);
660  /* vu2->up.lu_p = lu2; done by nmg_mvu() */
661  } else {
662  bu_bomb("nmg_mlv() unknown parent for loopuse!\n");
663  }
664 
665  if (RTG.NMG_debug & DEBUG_BASIC) {
666  bu_log("nmg_mlv(up=%p, v=%p, %s) returns lu=%p on vu=%p\n",
667  (void *)magic, (void *)v, nmg_orientation(orientation),
668  (void *)lu1, (void *)vu1);
669  }
670  return lu1;
671 }
672 
673 
674 /**
675  * Make wire edge.
676  *
677  * Make a new edge between a pair of vertices in a shell.
678  *
679  * A new vertex will be made for any NULL vertex pointer parameters.
680  * If we need to make a new vertex and the shell still has its
681  * vertexuse we re-use that vertex rather than freeing and
682  * re-allocating.
683  *
684  * If both vertices were specified, and the shell also had a vertexuse
685  * pointer, the vertexuse in the shell is killed. XXX Why?
686  *
687  * Explicit Return -
688  * An edgeuse in shell "s" whose vertexuse refers to vertex v1.
689  * The edgeuse mate's vertexuse refers to vertex v2
690  *
691  * Implicit Returns -
692  * 1) If the shell had a lone vertex in vu_p, it is destroyed,
693  * even if both vertices were specified.
694  * 2) The returned edgeuse is the first item on the shell's
695  * eu_hd list, followed immediately by the mate.
696  */
697 struct edgeuse *
698 nmg_me(struct vertex *v1, struct vertex *v2, struct shell *s)
699 {
700  struct edge *e;
701  struct edgeuse *eu1;
702  struct edgeuse *eu2;
703  struct vertexuse *vu;
704  struct model *m;
705 
706  if (v1) NMG_CK_VERTEX(v1);
707  if (v2) NMG_CK_VERTEX(v2);
708  NMG_CK_SHELL(s);
709 
710  m = nmg_find_model(&s->l.magic);
711  GET_EDGE(e, m);
712  GET_EDGEUSE(eu1, m);
713  GET_EDGEUSE(eu2, m);
714 
715  BU_LIST_INIT(&eu1->l2);
716  BU_LIST_INIT(&eu2->l2);
717  eu1->l2.magic = eu2->l2.magic = NMG_EDGEUSE2_MAGIC;
718 
719  e->eu_p = eu1;
720  /* e->is_real = XXX; */
721  e->magic = NMG_EDGE_MAGIC; /* Edge struct is GOOD */
722 
723  eu1->radial_p = eu1->eumate_p = eu2;
724  eu2->radial_p = eu2->eumate_p = eu1;
725 
726  eu1->e_p = eu2->e_p = e;
727  eu1->orientation = eu2->orientation = OT_NONE;
728  /* XXX - why not OT_UNSPEC? ctj */
729  eu1->vu_p = eu2->vu_p = (struct vertexuse *) NULL;
730 
731  eu1->l.magic = eu2->l.magic =
732  NMG_EDGEUSE_MAGIC; /* Edgeuse structs are GOOD */
733  /* Not really, edgeuses require vertexuses, but we've got to */
734  /* call nmg_mvvu() or nmg_mvu() before we can set vu_p so we */
735  /* NULL out vu_p now. */
736 
737  /* link the edgeuses to the parent shell */
738  eu1->up.s_p = eu2->up.s_p = s;
739 
740  if (v1) {
741  eu1->vu_p = nmg_mvu(v1, &eu1->l.magic, m);
742  } else if (s->vu_p) {
743  /* This clause of the if statement dies when no vertex stealing */
744  /* steal the vertex from the shell */
745  vu = s->vu_p;
746  s->vu_p = (struct vertexuse *)NULL;
747  eu1->vu_p = vu;
748  vu->up.eu_p = eu1;
749  } else {
750  eu1->vu_p = nmg_mvvu(&eu1->l.magic, m);
751  }
752 
753  if (v2) {
754  eu2->vu_p = nmg_mvu(v2, &eu2->l.magic, m);
755  } else if (s->vu_p) {
756  /* This clause of the if statement dies when no vertex stealing */
757  /* steal the vertex from the shell */
758  vu = s->vu_p;
759  s->vu_p = (struct vertexuse *)NULL;
760  eu2->vu_p = vu;
761  vu->up.eu_p = eu2;
762  } else {
763  eu2->vu_p = nmg_mvvu(&eu2->l.magic, m);
764  }
765 
766  /* This if statement dies when no vertex stealing */
767  if (s->vu_p) {
768  /* Ensure shell no longer has any stored vertexuse */
769  (void)nmg_kvu(s->vu_p);
770  s->vu_p = (struct vertexuse *)NULL;
771  }
772 
773  /* shell's eu_head, eu1, eu2, ... */
774  BU_LIST_APPEND(&s->eu_hd, &eu1->l);
775  BU_LIST_APPEND(&eu1->l, &eu2->l);
776 
777  if (RTG.NMG_debug & DEBUG_BASIC) {
778  bu_log("nmg_me(v1=%p, v2=%p, s=%p) returns eu=%p\n",
779  (void *)v1, (void *)v2, (void *)s, (void *)eu1);
780  }
781 
782  return eu1;
783 }
784 
785 
786 /**
787  * Make an edge on vertexuse.
788  *
789  * The new edge runs from and to that vertex.
790  *
791  * If the vertexuse was the shell's sole vertexuse, then the new edge
792  * is a wire edge in the shell's eu_hd list.
793  *
794  * If the vertexuse was part of a loop-of-a-single-vertex, either as a
795  * loop in a face or as a wire-loop in the shell, the loop becomes a
796  * regular loop with one edge that runs from and to the original
797  * vertex.
798  */
799 struct edgeuse *
800 nmg_meonvu(struct vertexuse *vu)
801 {
802  struct edge *e;
803  struct edgeuse *eu1, *eu2;
804  struct model *m;
805 
806  NMG_CK_VERTEXUSE(vu);
807 
808  m = nmg_find_model(vu->up.magic_p);
809  GET_EDGE(e, m);
810  GET_EDGEUSE(eu1, m);
811  GET_EDGEUSE(eu2, m);
812 
813  BU_LIST_INIT(&eu1->l2);
814  BU_LIST_INIT(&eu2->l2);
815  eu1->l2.magic = eu2->l2.magic = NMG_EDGEUSE2_MAGIC;
816 
817  e->eu_p = eu1;
818  e->is_real = 0;
819  e->magic = NMG_EDGE_MAGIC;
820 
821  eu1->radial_p = eu1->eumate_p = eu2;
822  eu2->radial_p = eu2->eumate_p = eu1;
823  eu1->e_p = eu2->e_p = e;
824  eu1->orientation = eu2->orientation = OT_NONE;
825  /* XXX Why not OT_UNSPEC? */
826  eu1->vu_p = vu;
827  /* vu->up needs to be set but we can't do that until we recover */
828  /* the shell or loopuse from the up pointer. */
829 
830  eu2->vu_p = (struct vertexuse *) NULL;
831 
832  /* link edgeuses to parent */
833  if (*vu->up.magic_p == NMG_SHELL_MAGIC) {
834  struct shell *s;
835 
836  s = eu2->up.s_p = eu1->up.s_p = vu->up.s_p;
837  eu1->l.magic = eu2->l.magic =
838  NMG_EDGEUSE_MAGIC; /* Edgeuse structs are GOOD */
839  /* eu2 is fake good till it has a real vu */
840 
841  vu->up.eu_p = eu1; /* vu is good again */
842 
843  if (s->vu_p != vu)
844  bu_bomb("nmg_meonvu() vertexuse parent shell disowns vertexuse!\n");
845  s->vu_p = (struct vertexuse *)NULL; /* remove from shell */
846 
847  eu2->vu_p = nmg_mvu(vu->v_p, &eu2->l.magic, m);
848  BU_LIST_APPEND(&s->eu_hd, &eu2->l);
849  BU_LIST_APPEND(&s->eu_hd, &eu1->l);
850  } else if (*vu->up.magic_p == NMG_LOOPUSE_MAGIC) {
851  struct loopuse *lu;
852  struct loopuse *lumate;
853  struct vertexuse *vumate;
854 
855  lu = vu->up.lu_p;
856  NMG_CK_LOOPUSE(lu);
857  lumate = lu->lumate_p;
858  NMG_CK_LOOPUSE(lumate);
859 
860  /* do a little consistency checking */
861  if (lu == lumate) bu_bomb("nmg_meonvu() lu mate is lu\n");
862  if (BU_LIST_FIRST_MAGIC(&lumate->down_hd) != NMG_VERTEXUSE_MAGIC)
863  bu_bomb("nmg_meonvu() mate of vertex-loop is not vertex-loop!\n");
864  vumate = BU_LIST_FIRST(vertexuse, &lumate->down_hd);
865  NMG_CK_VERTEXUSE(vumate);
866  if (vu == vumate) bu_bomb("nmg_meonvu() vu mate is vu\n");
867  NMG_CK_VERTEX(vu->v_p);
868  NMG_CK_VERTEX(vumate->v_p);
869 
870  /* edgeuses point at vertexuses */
871  eu2->vu_p = vumate;
872 
873  /* edgeuses point at parent loopuses */
874  eu1->up.lu_p = lu;
875  eu2->up.lu_p = lumate;
876 
877  eu1->l.magic = eu2->l.magic =
878  NMG_EDGEUSE_MAGIC; /* Edgeuse structs are GOOD */
879 
880  /* Fix forw & back pointers after "abuse", above */
881  /*
882  * The down_hd can be a POINTER to a vertexuse or
883  * the head of a linked list. In this case we are
884  * changing from a pointer to a linked list so we
885  * initialize the linked list head then add the loopuses
886  * to that list.
887  */
888  BU_LIST_INIT(&lu->down_hd);
889  BU_LIST_INIT(&lumate->down_hd);
890  /* Add edgeuses to loopuses linked lists */
891  BU_LIST_APPEND(&lumate->down_hd, &eu2->l);
892  BU_LIST_APPEND(&lu->down_hd, &eu1->l);
893 
894  /* vertexuses point up at edgeuses */
895  vu->up.eu_p = eu1;
896  vumate->up.eu_p = eu2;
897  } else {
898  bu_bomb("nmg_meonvu() cannot make edge, vertexuse not sole element of object\n");
899  }
900 
901  if (RTG.NMG_debug & DEBUG_BASIC) {
902  bu_log("nmg_meonvu(vu=%p) returns eu=%p\n", (void *)vu, (void *)eu1);
903  }
904 
905  return eu1;
906 }
907 
908 
909 /**
910  * Make wire loop from wire edgeuse list
911  *
912  * Passed a pointer to a shell. The wire edgeuse child of the shell
913  * is taken as the head of a list of edge(use)s which will form the
914  * new loop. The loop is created from the first N contiguous edges.
915  * Thus the end of the new loop is * delineated by the "next"
916  * edge(use)being:
917  *
918  * A) the first object in the list (no other edgeuses in shell list)
919  * B) non-contiguous with the previous edge
920  *
921  * A loop is created from this list of edges. The edges must form a
922  * true circuit, or we dump core on your disk. If we succeed, then
923  * the edgeuses are moved from the shell edgeuse list to the loop, and
924  * the two loopuses are inserted into the shell.
925  */
926 struct loopuse *
927 nmg_ml(struct shell *s)
928 {
929  struct loop *l;
930  struct loopuse *lu1, *lu2;
931  struct edgeuse *p1;
932  struct edgeuse *p2;
933  struct edgeuse *feu;
934  struct model *m;
935 
936  NMG_CK_SHELL(s);
937  /* If loop on single vertex */
938  if (BU_LIST_IS_EMPTY(&s->eu_hd) && s->vu_p) {
939  NMG_CK_VERTEXUSE(s->vu_p);
940  NMG_CK_VERTEX(s->vu_p->v_p);
941  lu1 = nmg_mlv(&s->l.magic, s->vu_p->v_p, OT_UNSPEC);
942  /* (void) nmg_kvu(s->vu_p); */
943 
944  if (RTG.NMG_debug & DEBUG_BASIC) {
945  bu_log("nmg_ml(s=%p) returns lu of single vertex=%p\n", (void *)s, (void *)lu1);
946  }
947 
948  return lu1;
949  }
950 
951  m = nmg_find_model(&s->l.magic);
952  GET_LOOP(l, m);
953  GET_LOOPUSE(lu1, m);
954  GET_LOOPUSE(lu2, m);
955 
956  l->lg_p = (struct loop_g *)NULL;
957  l->lu_p = lu1;
958  l->magic = NMG_LOOP_MAGIC; /* loop struct is GOOD */
959 
960  BU_LIST_INIT(&lu1->down_hd);
961  BU_LIST_INIT(&lu2->down_hd);
962  lu1->l_p = lu2->l_p = l;
963  lu1->orientation = lu2->orientation = OT_UNSPEC;
964  lu1->lumate_p = lu2;
965  lu2->lumate_p = lu1;
966  lu1->up.s_p = lu2->up.s_p = s;
967  lu1->l.magic = lu2->l.magic =
968  NMG_LOOPUSE_MAGIC; /* Loopuse structs are GOOD */
969 
970  /* Save the first edgeuse so we can tell if the loop closes */
971  feu = BU_LIST_FIRST(edgeuse, &s->eu_hd);
972  if (feu) {
973  NMG_CK_EDGEUSE(feu);
974  NMG_CK_VERTEXUSE(feu->vu_p);
975  NMG_CK_VERTEX(feu->vu_p->v_p);
976  }
977 
978  /* Safety catch in case eu_hd is empty */
979  p2 = (struct edgeuse *)NULL;
980  while (BU_LIST_NON_EMPTY(&s->eu_hd)) {
981  p1 = BU_LIST_FIRST(edgeuse, &s->eu_hd);
982  NMG_CK_EDGEUSE(p1);
983  p2 = p1->eumate_p;
984  NMG_CK_EDGEUSE(p2);
985 
986  /* bogosity check */
987  if (p1->up.s_p != s || p2->up.s_p != s)
988  bu_bomb("nmg_ml() edgeuse mates don't have proper parent!\n");
989 
990  /* dequeue the first edgeuse */
991  BU_LIST_DEQUEUE(&p1->l);
992  if (BU_LIST_IS_EMPTY(&s->eu_hd)) {
993  bu_log("nmg_ml() in %s at %d edgeuse mate not in this shell\n",
994  __FILE__, __LINE__);
995  bu_bomb("nmg_ml\n");
996  }
997 
998  /* dequeue the edgeuse's mate */
999  BU_LIST_DEQUEUE(&p2->l);
1000 
1001  /* Insert the next new edgeuse(s) at tail of the loop's list
1002  * (i.e., insert just before the head).
1003  * head, ....., p2, p1, (tail)
1004  */
1005  BU_LIST_INSERT(&lu1->down_hd, &p1->l);
1006  BU_LIST_INSERT(&lu2->down_hd, &p2->l);
1007 
1008  p1->up.lu_p = lu1;
1009  p2->up.lu_p = lu2;
1010 
1011  /* If p2's vertex does not match next one coming, quit */
1012  if (BU_LIST_IS_EMPTY(&s->eu_hd)) break;
1013  p1 = BU_LIST_FIRST(edgeuse, &s->eu_hd);
1014  NMG_CK_EDGEUSE(p1);
1015  NMG_CK_VERTEXUSE(p1->vu_p);
1016  NMG_CK_VERTEX(p1->vu_p->v_p);
1017  NMG_CK_VERTEXUSE(p2->vu_p);
1018  NMG_CK_VERTEX(p2->vu_p->v_p);
1019  if (p1->vu_p->v_p != p2->vu_p->v_p) {
1020  break;
1021  }
1022  }
1023 
1024  if (p2) {
1025  NMG_CK_EDGEUSE(p2);
1026  NMG_CK_VERTEXUSE(p2->vu_p);
1027  NMG_CK_VERTEX(p2->vu_p->v_p);
1028  }
1029  if (p2 && p2->vu_p->v_p != feu->vu_p->v_p) {
1030  bu_log("nmg_ml() Edge(use)s do not form proper loop!\n");
1031  nmg_pr_s(s, (char *)NULL);
1032  bu_log("nmg_ml() Edge(use)s do not form proper loop!\n");
1033  bu_bomb("nmg_ml\n");
1034  }
1035 
1036  /* Head, lu1, lu2, ... */
1037  BU_LIST_APPEND(&s->lu_hd, &lu2->l);
1038  BU_LIST_APPEND(&s->lu_hd, &lu1->l);
1039 
1040  if (RTG.NMG_debug & DEBUG_BASIC) {
1041  bu_log("nmg_ml(s=%p) returns lu=%p\n", (void *)s, (void *)lu1);
1042  }
1043 
1044  return lu1;
1045 }
1046 
1047 
1048 /************************************************************************
1049  * *
1050  * "Kill" Routines *
1051  * *
1052  * These subroutines delete (kill) a topological entity, *
1053  * eliminating any related subordinate entities where appropriate. *
1054  * *
1055  * If the superior entity becomes empty as a result of a "kill" *
1056  * operation, and that superior entity isn't allowed to *be* empty, *
1057  * then a TRUE (1) return code is given, indicating that the *
1058  * caller needs to immediately delete the superior entity before *
1059  * performing any other NMG operations. *
1060  * *
1061  * During this interval, the superior entity is in an "illegal" *
1062  * state that the verify routines (nmg_vshell, etc.) and subsequent *
1063  * NMG processing routines will not accept, so that code which fails *
1064  * to honor the return codes will "blow up" downstream. *
1065  * Unfortunately, in some cases the problem won't be detected for *
1066  * quite a while, but this is better than having subsequent code *
1067  * encountering entities that *look* valid, but shouldn't be. *
1068  * *
1069  ************************************************************************/
1070 
1071 
1072 /**
1073  * Kill vertexuse, and null out parent's vu_p.
1074  *
1075  * This routine is not intended for general use by applications,
1076  * because it requires cooperation on the part of the caller to
1077  * properly dispose of or fix the now *quite* illegal parent.
1078  * (Illegal because the parent's vu_p is NULL). It exists primarily
1079  * as a support routine for "mopping up" after nmg_klu(), nmg_keu(),
1080  * nmg_ks(), and nmg_mv_vu_between_shells().
1081  *
1082  * It is also used in a particularly ugly way in nmg_cut_loop() and
1083  * nmg_split_lu_at_vu() as part of their method for obtaining an
1084  * "empty" loopuse/loop set.
1085  *
1086  * It is worth noting that all these callers ignore the return code,
1087  * because they *all* exist to intentionally empty out the parent, but
1088  * the return code is provided anyway, in the name of [CTJ] symmetry.
1089  *
1090  * Returns -
1091  * 0 If all is well in the parent
1092  * 1 If parent is empty, and is thus "illegal"
1093  */
1094 int
1095 nmg_kvu(struct vertexuse *vu)
1096 {
1097  struct vertex *v;
1098  int ret = 0;
1099 
1100  if (!vu)
1101  return 1;
1102 
1103  NMG_CK_VERTEXUSE(vu);
1104 
1105  if (vu->a.magic_p) {
1106  NMG_CK_VERTEXUSE_A_EITHER(vu->a.magic_p);
1107  switch (*vu->a.magic_p) {
1109  FREE_VERTEXUSE_A_PLANE(vu->a.plane_p);
1110  break;
1112  FREE_VERTEXUSE_A_CNURB(vu->a.cnurb_p);
1113  break;
1114  }
1115  }
1116 
1117  v = vu->v_p;
1118  if (v) {
1119  NMG_CK_VERTEX(v);
1120 
1121  BU_LIST_DEQUEUE(&vu->l);
1122  if (BU_LIST_IS_EMPTY(&v->vu_hd)) {
1123  /* last vertexuse on vertex */
1124  if (v->vg_p) FREE_VERTEX_G(v->vg_p);
1125  FREE_VERTEX(v);
1126  }
1127  }
1128 
1129  /* erase existence of this vertexuse from parent */
1130  if (vu->up.magic_p != NULL) {
1131  if (*vu->up.magic_p == NMG_SHELL_MAGIC) {
1132  if (vu->up.s_p) {
1133  vu->up.s_p->vu_p = (struct vertexuse *)NULL;
1134  ret = nmg_shell_is_empty(vu->up.s_p);
1135  }
1136  } else if (*vu->up.magic_p == NMG_LOOPUSE_MAGIC) {
1137  if (vu->up.lu_p) {
1138  /* Reset the hack */
1139  BU_LIST_INIT(&vu->up.lu_p->down_hd);
1140  ret = 1;
1141  }
1142  } else if (*vu->up.magic_p == NMG_EDGEUSE_MAGIC) {
1143  if (vu->up.eu_p) {
1144  vu->up.eu_p->vu_p = (struct vertexuse *)NULL;
1145  ret = 1;
1146  }
1147  } else
1148  bu_bomb("nmg_kvu() killing vertexuse of unknown parent?\n");
1149  }
1150 
1151  if (RTG.NMG_debug & DEBUG_BASIC) {
1152  bu_log("nmg_kvu(vu=%p) ret=%d\n", (void *)vu, ret);
1153  }
1154 
1155  FREE_VERTEXUSE(vu);
1156 
1157  return ret;
1158 }
1159 
1160 
1161 /**
1162  * Internal routine to release face geometry when no more faces use
1163  * it.
1164  */
1165 static void
1166 nmg_kfg(uint32_t *magic_p)
1167 {
1168  switch (*magic_p) {
1169  case NMG_FACE_G_PLANE_MAGIC: {
1170  /* If face_g is not referred to by any other face, free it */
1171  struct face_g_plane *pp;
1172  pp = (struct face_g_plane *)magic_p;
1173  if (BU_LIST_NON_EMPTY(&(pp->f_hd))) return;
1174  FREE_FACE_G_PLANE(pp);
1175  }
1176  break;
1177  case NMG_FACE_G_SNURB_MAGIC: {
1178  /* If face_g is not referred to by any other face, free it */
1179  struct face_g_snurb *sp;
1180  sp = (struct face_g_snurb *)magic_p;
1181  if (BU_LIST_NON_EMPTY(&(sp->f_hd))) return;
1182  bu_free((char *)sp->u.knots, "nmg_kfg snurb u knots[]");
1183  bu_free((char *)sp->v.knots, "nmg_kfg snurb v knots[]");
1184  bu_free((char *)sp->ctl_points, "nmg_kfg snurb ctl_points[]");
1185  FREE_FACE_G_SNURB(sp);
1186  }
1187  break;
1188  default:
1189  bu_bomb("nmg_kfg() bad magic\n");
1190  }
1191 }
1192 
1193 
1194 /**
1195  * Kill Faceuse
1196  *
1197  * delete a faceuse and its mate from the parent shell.
1198  *
1199  * Any children found are brutally murdered as well. The faceuses are
1200  * dequeued from the parent shell's list here.
1201  *
1202  * Returns -
1203  * 0 If all is well
1204  * 1 If parent shell is now empty, and is thus "illegal"
1205  */
1206 int
1207 nmg_kfu(struct faceuse *fu1)
1208 {
1209  struct faceuse *fu2;
1210  struct face *f1;
1211  struct face *f2;
1212  struct shell *s;
1213  int ret;
1214 
1215  if (!fu1)
1216  return 1;
1217 
1218  NMG_CK_FACEUSE(fu1);
1219  fu2 = fu1->fumate_p;
1220  NMG_CK_FACEUSE(fu2);
1221  f1 = fu1->f_p;
1222  f2 = fu2->f_p;
1223  NMG_CK_FACE(f1);
1224  NMG_CK_FACE(f2);
1225  if (f1 != f2)
1226  bu_bomb("nmg_kfu() faceuse mates do not share face!\n");
1227  s = fu1->s_p;
1228  NMG_CK_SHELL(s);
1229 
1230  /* kill off the children (infanticide?)*/
1231  while (BU_LIST_NON_EMPTY(&fu1->lu_hd)) {
1232  (void)nmg_klu(BU_LIST_FIRST(loopuse, &fu1->lu_hd));
1233  }
1234 
1235  /* Release the face geometry */
1236  if (f1->g.magic_p) {
1237  /* Disassociate this face from face_g */
1238  BU_LIST_DEQUEUE(&f1->l);
1239  nmg_kfg(f1->g.magic_p);
1240  }
1241  FREE_FACE(f1);
1242  fu1->f_p = fu2->f_p = (struct face *)NULL;
1243 
1244  /* remove ourselves from the parent list */
1245  BU_LIST_DEQUEUE(&fu1->l);
1246  if (BU_LIST_IS_EMPTY(&s->fu_hd))
1247  bu_bomb("nmg_kfu() faceuse mate not in parent shell?\n");
1248  BU_LIST_DEQUEUE(&fu2->l);
1249 
1250  ret = nmg_shell_is_empty(s);
1251 
1252  if (RTG.NMG_debug & DEBUG_BASIC) {
1253  bu_log("nmg_kfu(fu1=%p) fu2=%p ret=%d\n", (void *)fu1, (void *)fu2, ret);
1254  }
1255 
1256  FREE_FACEUSE(fu1);
1257  FREE_FACEUSE(fu2);
1258 
1259  return ret;
1260 }
1261 
1262 
1263 /**
1264  * Kill loopuse, loopuse mate, and loop.
1265  *
1266  * if the loop contains any edgeuses or vertexuses they are killed
1267  * before the loop is deleted.
1268  *
1269  * We support the concept of killing a loop with no children to
1270  * support the routine "nmg_demote_lu"
1271  *
1272  * Returns -
1273  * 0 If all is well
1274  * 1 If parent is empty, and is thus "illegal"
1275  */
1276 int
1277 nmg_klu(struct loopuse *lu1)
1278 {
1279  struct loopuse *lu2;
1280  uint32_t magic1;
1281  int ret = 0;
1282 
1283  if (!lu1)
1284  return 1;
1285 
1286  NMG_CK_LOOPUSE(lu1);
1287  lu2 = lu1->lumate_p;
1288  NMG_CK_LOOPUSE(lu2);
1289 
1290  if (lu1->l_p != lu2->l_p)
1291  bu_bomb("nmg_klu() loopmates do not share loop!\n");
1292 
1293  if (*lu1->up.magic_p != *lu2->up.magic_p)
1294  bu_bomb("nmg_klu() loopuses do not have same type of parent!\n");
1295 
1296  /* deal with the children */
1297  magic1 = BU_LIST_FIRST_MAGIC(&lu1->down_hd);
1298  if (magic1 != BU_LIST_FIRST_MAGIC(&lu2->down_hd))
1299  bu_bomb("nmg_klu() loopuses do not have same type of child!\n");
1300 
1301  if (magic1 == NMG_VERTEXUSE_MAGIC) {
1302  /* Follow the vertex-loop hack downward,
1303  * nmg_kvu() will clean up */
1304  (void)nmg_kvu(BU_LIST_FIRST(vertexuse, &lu1->down_hd));
1305  (void)nmg_kvu(BU_LIST_FIRST(vertexuse, &lu2->down_hd));
1306  } else if (magic1 == NMG_EDGEUSE_MAGIC) {
1307  /* delete all edgeuse in the loopuse (&mate) */
1308  while (BU_LIST_NON_EMPTY(&lu1->down_hd)) {
1309  (void)nmg_keu(BU_LIST_FIRST(edgeuse, &lu1->down_hd));
1310  }
1311  } else if (magic1 == BU_LIST_HEAD_MAGIC) {
1312  /* down_hd list is empty, no problem */
1313  } else {
1314  bu_log("nmg_klu(%p) magic=%s\n", (void *)lu1, bu_identify_magic(magic1));
1315  bu_bomb("nmg_klu: unknown type for loopuse child\n");
1316  }
1317 
1318  /* disconnect from parent's list */
1319  if (*lu1->up.magic_p == NMG_SHELL_MAGIC) {
1320  BU_LIST_DEQUEUE(&lu1->l);
1321  BU_LIST_DEQUEUE(&lu2->l);
1322  ret = nmg_shell_is_empty(lu1->up.s_p);
1323  } else if (*lu1->up.magic_p == NMG_FACEUSE_MAGIC) {
1324  BU_LIST_DEQUEUE(&lu1->l);
1325  BU_LIST_DEQUEUE(&lu2->l);
1326  ret = BU_LIST_IS_EMPTY(&lu1->up.fu_p->lu_hd);
1327  } else {
1328  bu_bomb("nmg_klu() unknown parent for loopuse\n");
1329  }
1330 
1331  NMG_CK_LOOP(lu1->l_p);
1332  if (lu1->l_p->lg_p) {
1333  NMG_CK_LOOP_G(lu1->l_p->lg_p);
1334  FREE_LOOP_G(lu1->l_p->lg_p);
1335  }
1336  FREE_LOOP(lu1->l_p);
1337  if (RTG.NMG_debug & DEBUG_BASIC) {
1338  bu_log("nmg_klu(lu1=%p) lu2=%p ret=%d\n", (void *)lu1, (void *)lu2, ret);
1339  }
1340 
1341  FREE_LOOPUSE(lu1);
1342  FREE_LOOPUSE(lu2);
1343 
1344  return ret;
1345 }
1346 
1347 
1348 /**
1349  * Internal routine to kill an edge geometry structure (of either
1350  * type), if all the edgeuses on its list have vanished. Regardless,
1351  * the edgeuse's geometry pointer is cleared.
1352  *
1353  * This routine does only a single edgeuse. If the edgeuse mate has
1354  * geometry to be killed, make a second call. Sometimes only one of
1355  * the two needs to release the geometry.
1356  *
1357  * Returns -
1358  * 0 If the old edge geometry (eu->g.magic_p) has other uses.
1359  * 1 If the old edge geometry has been destroyed. Caller beware!
1360  *
1361  * NOT INTENDED FOR GENERAL USE!
1362  * However, nmg_mod.c needs it for nmg_eusplit(). (Drat!)
1363  */
1364 /* static */ int
1365 nmg_keg(struct edgeuse *eu)
1366 {
1367  if (!eu)
1368  return 1;
1369 
1370  NMG_CK_EDGEUSE(eu);
1371 
1372  if (!eu->g.magic_p)
1373  return 1; /* no geometry to kill */
1374 
1375  switch (*eu->g.magic_p) {
1376  case NMG_EDGE_G_LSEG_MAGIC: {
1377  struct edge_g_lseg *lp;
1378  lp = eu->g.lseg_p;
1379  eu->g.magic_p = NULL;
1380  if (BU_LIST_NON_EMPTY(&lp->eu_hd2)) return 0;
1381  FREE_EDGE_G_LSEG(lp);
1382  break;
1383  }
1384 
1385  case NMG_EDGE_G_CNURB_MAGIC: {
1386  struct edge_g_cnurb *eg;
1387  eg = eu->g.cnurb_p;
1388  eu->g.magic_p = NULL;
1389  if (BU_LIST_NON_EMPTY(&eg->eu_hd2)) return 0;
1390  if (eg->order != 0) {
1391  bu_free((char *)eg->k.knots, "nmg_keg cnurb knots[]");
1392  bu_free((char *)eg->ctl_points, "nmg_keg cnurb ctl_points[]");
1393  }
1394  FREE_EDGE_G_CNURB(eg);
1395  break;
1396  }
1397  }
1398 
1399  return 1; /* edge geometry has been destroyed */
1400 }
1401 
1402 
1403 /**
1404  * Delete an edgeuse & its mate from a shell or loop.
1405  *
1406  * Returns -
1407  * 0 If all is well
1408  * 1 If the parent now has no edgeuses, and is thus "illegal" and in
1409  * need of being deleted. (The lu / shell deletion can't be handled
1410  * at this level, and must be done by the caller).
1411  */
1412 int
1413 nmg_keu(register struct edgeuse *eu1)
1414 {
1415  register struct edgeuse *eu2;
1416  struct edge *e;
1417  int ret = 0;
1418 
1419  if (!eu1)
1420  return 0;
1421 
1422  NMG_CK_EDGEUSE(eu1);
1423  e = eu1->e_p;
1424  NMG_CK_EDGE(e);
1425 
1426  eu2 = eu1->eumate_p;
1427  NMG_CK_EDGEUSE(eu2);
1428  NMG_CK_EDGE(eu2->e_p);
1429 
1430  if (e != eu2->e_p) {
1431  bu_bomb("nmg_keu() edgeuse pair does not share edge\n");
1432  }
1433 
1434  /* unlink from radial linkages (if any) */
1435  if (eu1->radial_p != eu2) {
1436  NMG_CK_EDGEUSE(eu1->radial_p);
1437  NMG_CK_EDGEUSE(eu2->radial_p);
1438 
1439  eu1->radial_p->radial_p = eu2->radial_p;
1440  eu2->radial_p->radial_p = eu1->radial_p;
1441 
1442  NMG_CK_EDGEUSE(eu1->radial_p);
1443  NMG_CK_EDGEUSE(eu2->radial_p);
1444 
1445  /* since there is a use of this edge left, make sure the edge
1446  * structure points to a remaining edgeuse
1447  */
1448  if (e->eu_p == eu1 || e->eu_p == eu2)
1449  e->eu_p = eu1->radial_p;
1450  NMG_CK_EDGEUSE(e->eu_p);
1451  } else {
1452  /* since these two edgeuses are the only use of this edge,
1453  * we need to free the edge (since all uses are about
1454  * to disappear).
1455  */
1456  FREE_EDGE(e);
1457  e = (struct edge *)NULL;
1458  eu1->e_p = e; /* sanity */
1459  eu2->e_p = e;
1460  }
1461 
1462  /* handle geometry, if any */
1463  if (eu1->g.magic_p) {
1464  /* Dequeue edgeuse from geometry's list of users */
1465  BU_LIST_DEQUEUE(&eu1->l2);
1466 
1467  /* Release the edgeuse's geometry pointer */
1468  nmg_keg(eu1);
1469  }
1470 
1471  if (eu2->g.magic_p) {
1472  /* Dequeue edgeuse from geometry's list of users */
1473  BU_LIST_DEQUEUE(&eu2->l2);
1474 
1475  /* Release the edgeuse's geometry pointer */
1476  nmg_keg(eu2);
1477  }
1478 
1479  /* remove the edgeuses from their parents */
1480  if (*eu1->up.magic_p == NMG_LOOPUSE_MAGIC) {
1481  struct loopuse *lu1, *lu2;
1482  lu1 = eu1->up.lu_p;
1483  lu2 = eu2->up.lu_p;
1484  NMG_CK_LOOPUSE(lu1);
1485  NMG_CK_LOOPUSE(lu2);
1486 
1487  if (lu1 == lu2) bu_bomb("nmg_keu() edgeuses on same loopuse\n");
1488  if (lu1->lumate_p != lu2 || lu1 != lu2->lumate_p) {
1489  bu_log("nmg_keu() lu1=%p, mate=%p\n", (void *)lu1, (void *)lu1->lumate_p);
1490  bu_log("nmg_keu() lu2=%p, mate=%p\n", (void *)lu2, (void *)lu2->lumate_p);
1491  bu_bomb("nmg_keu() edgeuse mates don't belong to loopuse mates\n");
1492  }
1493 
1494  /* remove the edgeuses from their parents */
1495  BU_LIST_DEQUEUE(&eu1->l);
1496  BU_LIST_DEQUEUE(&eu2->l);
1497 
1498  /* If loopuse list is empty, caller needs to delete it. */
1499  if (BU_LIST_IS_EMPTY(&lu1->down_hd)) ret = 1;
1500  } else if (*eu1->up.magic_p == NMG_SHELL_MAGIC) {
1501  if (eu1->up.s_p != eu2->up.s_p) {
1502  bu_bomb("nmg_keu() edgeuses don't share parent shell\n");
1503  }
1504 
1505  /* unlink edgeuses from the parent shell */
1506  BU_LIST_DEQUEUE(&eu1->l);
1507  BU_LIST_DEQUEUE(&eu2->l);
1508  ret = nmg_shell_is_empty(eu1->up.s_p);
1509  } else {
1510  bu_bomb("nmg_keu() bad up pointer\n");
1511  }
1512 
1513  /* kill the vertexuses associated with these edgeuses */
1514  if (eu1->vu_p) {
1515  (void)nmg_kvu(eu1->vu_p);
1516  }
1517  if (eu2->vu_p) {
1518  (void)nmg_kvu(eu2->vu_p);
1519  }
1520 
1521  if (RTG.NMG_debug & DEBUG_BASIC) {
1522  bu_log("nmg_keu(eu1=%p) eu2=%p ret=%d\n", (void *)eu1, (void *)eu2, ret);
1523  }
1524 
1525  FREE_EDGEUSE(eu1);
1526  FREE_EDGEUSE(eu2);
1527 
1528  if (e) {
1529  NMG_CK_EDGE(e);
1530  NMG_CK_EDGEUSE(e->eu_p);
1531  }
1532 
1533  return ret;
1534 }
1535 
1536 
1537 /**
1538  * Kill a shell and all children
1539  *
1540  * Returns -
1541  * 0 If all is well
1542  * 1 If parent nmgregion is now empty. While not "illegal",
1543  * an empty region is probably worthy of note.
1544  */
1545 int
1546 nmg_ks(struct shell *s)
1547 {
1548  struct nmgregion *r;
1549 
1550  if (!s)
1551  return 0;
1552 
1553  NMG_CK_SHELL(s);
1554  r = s->r_p;
1555  if (r)
1556  NMG_CK_REGION(r);
1557 
1558  while (BU_LIST_NON_EMPTY(&s->fu_hd))
1559  (void)nmg_kfu(BU_LIST_FIRST(faceuse, &s->fu_hd));
1560  while (BU_LIST_NON_EMPTY(&s->lu_hd))
1561  (void)nmg_klu(BU_LIST_FIRST(loopuse, &s->lu_hd));
1562  while (BU_LIST_NON_EMPTY(&s->eu_hd))
1563  (void)nmg_keu(BU_LIST_FIRST(edgeuse, &s->eu_hd));
1564  if (s->vu_p)
1565  nmg_kvu(s->vu_p);
1566 
1567  BU_LIST_DEQUEUE(&s->l);
1568 
1569  if (s->sa_p) {
1570  FREE_SHELL_A(s->sa_p);
1571  }
1572 
1573  if (RTG.NMG_debug & DEBUG_BASIC) {
1574  bu_log("nmg_ks(s=%p)\n", (void *)s);
1575  }
1576 
1577  FREE_SHELL(s);
1578 
1579  if (r && BU_LIST_IS_EMPTY(&r->s_hd))
1580  return 1;
1581 
1582  return 0;
1583 }
1584 
1585 
1586 /**
1587  * Kill a region and all shells in it.
1588  *
1589  * Returns -
1590  * 0 If all is well
1591  * 1 If model is now empty. While not "illegal",
1592  * an empty model is probably worthy of note.
1593  */
1594 int
1595 nmg_kr(struct nmgregion *r)
1596 {
1597  struct model *m;
1598 
1599  if (!r)
1600  return 0;
1601 
1602  NMG_CK_REGION(r);
1603  m = r->m_p;
1604  if (m)
1605  NMG_CK_MODEL(m);
1606 
1607  while (BU_LIST_NON_EMPTY(&r->s_hd))
1608  (void)nmg_ks(BU_LIST_FIRST(shell, &r->s_hd));
1609 
1610  BU_LIST_DEQUEUE(&r->l);
1611 
1612  if (r->ra_p) {
1613  FREE_REGION_A(r->ra_p);
1614  }
1615 
1616  if (RTG.NMG_debug & DEBUG_BASIC) {
1617  bu_log("nmg_kr(r=%p)\n", (void *)r);
1618  }
1619 
1620  FREE_REGION(r);
1621 
1622  if (m && BU_LIST_IS_EMPTY(&m->r_hd)) {
1623  m->maxindex = 1; /* Reset when last region is killed */
1624  return 1;
1625  }
1626  return 0;
1627 }
1628 
1629 
1630 /**
1631  * Kill an entire model. Nothing is left.
1632  */
1633 void
1634 nmg_km(struct model *m)
1635 {
1636  if (!m)
1637  return;
1638 
1639  NMG_CK_MODEL(m);
1640 
1641  while (BU_LIST_NON_EMPTY(&m->r_hd))
1642  (void)nmg_kr(BU_LIST_FIRST(nmgregion, &m->r_hd));
1643 
1644  if (m->manifolds) {
1645  bu_free((char *)m->manifolds, "free manifolds table");
1646  m->manifolds = (char *)NULL;
1647  }
1648 
1649  if (RTG.NMG_debug & DEBUG_BASIC) {
1650  bu_log("nmg_km(m=%p)\n", (void *)m);
1651  }
1652 
1653  FREE_MODEL(m);
1654 }
1655 
1656 
1657 /************************************************************************
1658  * *
1659  * "Geometry" and "Attribute" Routines *
1660  * *
1661  ************************************************************************/
1662 
1663 
1664 /**
1665  * Associate point_t ("vector") coordinates with a vertex
1666  */
1667 void
1668 nmg_vertex_gv(struct vertex *v, const fastf_t *pt)
1669 {
1670  struct vertex_g *vg;
1671  struct model *m;
1672 
1673  NMG_CK_VERTEX(v);
1674 
1675  vg = v->vg_p;
1676  if (vg) {
1677  NMG_CK_VERTEX_G(v->vg_p);
1678  } else {
1679  m = nmg_find_model(
1680  &BU_LIST_NEXT(vertexuse, &v->vu_hd)->l.magic);
1681  GET_VERTEX_G(vg, m);
1682 
1683  vg->magic = NMG_VERTEX_G_MAGIC;
1684  v->vg_p = vg;
1685  }
1686  VMOVE(vg->coord, pt);
1687 
1688  if (RTG.NMG_debug & DEBUG_BASIC) {
1689  bu_log("nmg_vertex_gv(v=%p, pt=(%g %g %g))\n", (void *)v, V3ARGS(pt));
1690  }
1691 }
1692 
1693 
1694 /**
1695  * a version that can take x, y, z coords and doesn't need a point
1696  * array. Mostly useful for quick and dirty programs.
1697  */
1698 void
1699 nmg_vertex_g(register struct vertex *v, fastf_t x, fastf_t y, fastf_t z)
1700 {
1701  point_t pt;
1702 
1703  pt[0] = x;
1704  pt[1] = y;
1705  pt[2] = z;
1706 
1707  if (RTG.NMG_debug & DEBUG_BASIC) {
1708  bu_log("nmg_vertex_g(v=%p, pt=(%g %g %g))\n", (void *)v, x, y, z);
1709  }
1710 
1711  nmg_vertex_gv(v, pt);
1712 }
1713 
1714 
1715 /**
1716  * Assign a normal vector to a vertexuse
1717  */
1718 void
1719 nmg_vertexuse_nv(struct vertexuse *vu, const fastf_t *norm)
1720 {
1721  struct model *m;
1722 
1723  NMG_CK_VERTEXUSE(vu);
1724 
1725  if (!vu->a.magic_p) {
1726  struct vertexuse_a_plane *vua;
1727  m = nmg_find_model(&vu->l.magic);
1728  GET_VERTEXUSE_A_PLANE(vua, m);
1729  vua->magic = NMG_VERTEXUSE_A_PLANE_MAGIC;
1730  vu->a.plane_p = vua;
1731  } else if (*vu->a.magic_p == NMG_VERTEXUSE_A_CNURB_MAGIC) {
1732  /* Assigning a normal vector to a cnurb vua is illegal */
1733  bu_bomb("nmg_vertexuse_nv() Illegal assignment of normal vector to edge_g_cnurb vertexuse\n");
1734  } else {
1735  NMG_CK_VERTEXUSE_A_PLANE(vu->a.plane_p);
1736  }
1737 
1738  VMOVE(vu->a.plane_p->N, norm);
1739 
1740  if (RTG.NMG_debug & DEBUG_BASIC) {
1741  bu_log("nmg_vertexuse_nv(vu=%p, norm=(%g %g %g))\n", (void *)vu, V3ARGS(norm));
1742  }
1743 }
1744 
1745 
1746 /**
1747  * Given a vertex with associated geometry in model space which lies
1748  * on a face_g_snurb surface, it will have a corresponding set of (u,
1749  * v) or (u, v, w) parameters on that surface. Build the association
1750  * here.
1751  *
1752  * Note that all vertexuses of a single vertex which are all used by
1753  * the same face_g_snurb will have the same "param" value, but will
1754  * have individual vertexuse_a_cnurb structures.
1755  */
1756 void
1757 nmg_vertexuse_a_cnurb(struct vertexuse *vu, const fastf_t *uvw)
1758 {
1759  struct vertexuse_a_cnurb *vua;
1760  struct model *m;
1761 
1762  NMG_CK_VERTEXUSE(vu);
1763 
1764  if (vu->a.magic_p) bu_bomb("nmg_vertexuse_a_cnurb() vu has attribute already\n");
1765  NMG_CK_EDGEUSE(vu->up.eu_p);
1766  if (vu->up.eu_p->g.magic_p) NMG_CK_EDGE_G_CNURB(vu->up.eu_p->g.cnurb_p);
1767 
1768  m = nmg_find_model(&vu->l.magic);
1769  GET_VERTEXUSE_A_CNURB(vua, m);
1770  VMOVE(vua->param, uvw);
1771  vua->magic = NMG_VERTEXUSE_A_CNURB_MAGIC;
1772 
1773  vu->a.cnurb_p = vua;
1774 
1775  if (RTG.NMG_debug & DEBUG_BASIC) {
1776  bu_log("nmg_vertexuse_a_cnurb(vu=%p, param=(%g %g %g)) vua=%p\n",
1777  (void *)vu, V3ARGS(uvw), (void *)vua);
1778  }
1779 }
1780 
1781 
1782 /**
1783  * Compute the equation of the line formed by the endpoints of the
1784  * edge.
1785  *
1786  * XXX This isn't the best name. nmg_edge_g_lseg() ?
1787  */
1788 void
1789 nmg_edge_g(struct edgeuse *eu)
1790 {
1791  struct model *m;
1792  struct edge_g_lseg *eg_p = (struct edge_g_lseg *)NULL;
1793  struct edge *e;
1794  struct edgeuse *eu2;
1795  pointp_t pt;
1796  int found_eg=0;
1797 
1798  NMG_CK_EDGEUSE(eu);
1799  e = eu->e_p;
1800  NMG_CK_EDGE(e);
1801  NMG_CK_VERTEXUSE(eu->vu_p);
1802  NMG_CK_VERTEX(eu->vu_p->v_p);
1803  NMG_CK_VERTEX_G(eu->vu_p->v_p->vg_p);
1804 
1805  NMG_CK_EDGEUSE(eu->eumate_p);
1806  NMG_CK_VERTEXUSE(eu->eumate_p->vu_p);
1807  NMG_CK_VERTEX(eu->eumate_p->vu_p->v_p);
1808  NMG_CK_VERTEX_G(eu->eumate_p->vu_p->v_p->vg_p);
1809 
1810  if (eu->vu_p->v_p == eu->eumate_p->vu_p->v_p)
1811  bu_bomb("nmg_edge_g(): Warning - edge runs from+to same vertex, 0 len!\n");
1812 
1813  eg_p = eu->g.lseg_p;
1814  if (eg_p) {
1815  NMG_CK_EDGE_G_LSEG(eg_p);
1816  bu_bomb("nmg_edge_g() geometry already assigned\n");
1817  }
1818 
1819  /* Search all other uses of this edge for an existing edge_g_lseg */
1820  eu2 = eu->eumate_p->radial_p;
1821  while (eu2 != eu) {
1822  if (eu2->g.magic_p && *eu2->g.magic_p == NMG_EDGE_G_LSEG_MAGIC) {
1823  eg_p = eu2->g.lseg_p;
1824  found_eg = 1;
1825  break;
1826  }
1827  eu2 = eu2->eumate_p->radial_p;
1828  }
1829 
1830  if (!eg_p) {
1831  /* Make new edge_g structure */
1832  m = nmg_find_model(&eu->l.magic);
1833  GET_EDGE_G_LSEG(eg_p, m);
1834  BU_LIST_INIT(&eg_p->eu_hd2);
1835  eg_p->l.magic = NMG_EDGE_G_LSEG_MAGIC;
1836 
1837  /* copy the point from the vertex of one of our edgeuses */
1838  pt = eu->vu_p->v_p->vg_p->coord;
1839  VMOVE(eg_p->e_pt, pt);
1840 
1841  /* compute the direction from the endpoints of the edgeuse(s) */
1842  pt = eu->eumate_p->vu_p->v_p->vg_p->coord;
1843  VSUB2(eg_p->e_dir, eg_p->e_pt, pt);
1844 
1845  /* If the edge vector is essentially 0 magnitude we're in trouble.
1846  * Warn the user and create an arbitrary vector we can use.
1847  */
1848  if (VNEAR_ZERO(eg_p->e_dir, SMALL_FASTF)) {
1849  pointp_t pt2 = eu->vu_p->v_p->vg_p->coord;
1850  VPRINT("nmg_edge_g(): e_dir too small", eg_p->e_dir);
1851  bu_log("nmg_edge_g(): (%g %g %g) -> (%g %g %g)",
1852  pt[X], pt[Y], pt[Z],
1853  pt2[X], pt2[Y], pt2[Z]);
1854 
1855  VSET(eg_p->e_dir, 1.0, 0.0, 0.0);
1856  VPRINT("nmg_edge_g(): Forcing e_dir to", eg_p->e_dir);
1857  bu_bomb("nmg_edge_g(): 0 length edge\n");
1858  }
1859  }
1860 
1861  /* Dequeue edgeuses from their current list (should point to themselves), add to new list */
1862  BU_LIST_DEQUEUE(&eu->l2);
1863  BU_LIST_DEQUEUE(&eu->eumate_p->l2);
1864 
1865  /* Associate edgeuse with this geometry */
1866  BU_LIST_INSERT(&eg_p->eu_hd2, &eu->l2);
1867  BU_LIST_INSERT(&eg_p->eu_hd2, &eu->eumate_p->l2);
1868  eu->g.lseg_p = eg_p;
1869  eu->eumate_p->g.lseg_p = eg_p;
1870 
1871  if (!found_eg) {
1872  /* No uses of this edge have geometry, get them all */
1873  eu2 = eu->eumate_p->radial_p;
1874  while (eu2 != eu) {
1875  eu2->g.lseg_p = eg_p;
1876  BU_LIST_INSERT(&eg_p->eu_hd2, &eu2->l2);
1877  eu2->eumate_p->g.lseg_p = eg_p;
1878  BU_LIST_INSERT(&eg_p->eu_hd2, &eu2->eumate_p->l2);
1879 
1880  eu2 = eu2->eumate_p->radial_p;
1881  }
1882  }
1883 
1884  if (RTG.NMG_debug & DEBUG_BASIC) {
1885  bu_log("nmg_edge_g(eu=%p) eg=%p\n", (void *)eu, (void *)eg_p);
1886  }
1887 }
1888 
1889 
1890 /**
1891  * For an edgeuse associated with a face_g_snurb surface, create a
1892  * spline curve in the parameter space of the snurb which describes
1893  * the path from the start vertex to the end vertex.
1894  *
1895  * The parameters of the end points are taken from the vertexuse
1896  * attributes at either end of the edgeuse.
1897  */
1898 void
1899 nmg_edge_g_cnurb(struct edgeuse *eu, int order, int n_knots, fastf_t *kv, int n_pts, int pt_type, fastf_t *points)
1900 {
1901  struct model *m;
1902  struct edge_g_cnurb *eg;
1903  struct edge *e;
1904  struct faceuse *fu;
1905 
1906  NMG_CK_EDGEUSE(eu);
1907  e = eu->e_p;
1908  NMG_CK_EDGE(e);
1909  NMG_CK_VERTEXUSE(eu->vu_p);
1910  NMG_CK_VERTEX(eu->vu_p->v_p);
1911  NMG_CK_VERTEX_G(eu->vu_p->v_p->vg_p);
1912 
1913  NMG_CK_EDGEUSE(eu->eumate_p);
1914  NMG_CK_VERTEXUSE(eu->eumate_p->vu_p);
1915  NMG_CK_VERTEX(eu->eumate_p->vu_p->v_p);
1916  NMG_CK_VERTEX_G(eu->eumate_p->vu_p->v_p->vg_p);
1917 
1918  if (eu->g.cnurb_p) {
1919  bu_bomb("nmg_edge_g_cnurb() geometry already assigned\n");
1920  }
1921  fu = nmg_find_fu_of_eu(eu);
1922  NMG_CK_FACEUSE(fu);
1923  NMG_CK_FACE_G_SNURB(fu->f_p->g.snurb_p);
1924 
1925  /* Make new edge_g structure */
1926  m = nmg_find_model(&eu->l.magic);
1927  GET_EDGE_G_CNURB(eg, m);
1928  BU_LIST_INIT(&eg->eu_hd2);
1929 
1930  eg->order = order;
1931  if (n_knots > 0 && kv) {
1932  eg->k.k_size = n_knots;
1933  eg->k.knots = kv;
1934  } else {
1935  /* Give a default curve, no interior knots */
1936  rt_nurb_kvknot(&eg->k, order, 0.0, 1.0, n_knots - (2 * order), (struct resource *)NULL);
1937  }
1938 
1939  if (n_pts < 2) bu_bomb("nmg_edge_g_cnurb() n_pts < 2\n");
1940  eg->c_size = n_pts;
1941  eg->pt_type = pt_type;
1942  if (points) {
1943  eg->ctl_points = points;
1944  } else {
1945  int ncoord = RT_NURB_EXTRACT_COORDS(pt_type);
1946 
1947  eg->ctl_points = (fastf_t *)bu_calloc(
1948  ncoord * n_pts,
1949  sizeof(fastf_t),
1950  "cnurb ctl_points[]");
1951 
1952  /*
1953  * As a courtesy, set first and last point to
1954  * the PARAMETER values of the edge's vertices.
1955  */
1956  NMG_CK_VERTEXUSE_A_CNURB(eu->vu_p->a.cnurb_p);
1957  NMG_CK_VERTEXUSE_A_CNURB(eu->eumate_p->vu_p->a.cnurb_p);
1958  switch (ncoord) {
1959  case 4:
1960  eg->ctl_points[3] = 1;
1961  eg->ctl_points[ (n_pts-1)*ncoord + 3] = 1;
1962  /* fall through... */
1963  case 3:
1964  VMOVE(eg->ctl_points, eu->vu_p->a.cnurb_p->param);
1965  VMOVE(&eg->ctl_points[ (n_pts-1)*ncoord ],
1966  eu->eumate_p->vu_p->a.cnurb_p->param);
1967  break;
1968  case 2:
1969  V2MOVE(eg->ctl_points, eu->vu_p->a.cnurb_p->param);
1970  V2MOVE(&eg->ctl_points[ (n_pts-1)*ncoord ],
1971  eu->eumate_p->vu_p->a.cnurb_p->param);
1972  break;
1973  default:
1974  bu_bomb("nmg_edge_g_cnurb() bad ncoord?\n");
1975  }
1976  }
1977 
1978  /* Dequeue edgeuses from their current list (should point to themselves), add to new list */
1979  BU_LIST_DEQUEUE(&eu->l2);
1980  BU_LIST_DEQUEUE(&eu->eumate_p->l2);
1981 
1982  /* Associate edgeuse with this geometry */
1983  BU_LIST_INSERT(&eg->eu_hd2, &eu->l2);
1984  BU_LIST_INSERT(&eg->eu_hd2, &eu->eumate_p->l2);
1985  eu->g.cnurb_p = eg;
1986  eu->eumate_p->g.cnurb_p = eg;
1987 
1988  eg->l.magic = NMG_EDGE_G_CNURB_MAGIC;
1989 
1990  if (RTG.NMG_debug & DEBUG_BASIC) {
1991  bu_log("nmg_edge_g_cnurb(eu=%p, order=%d, n_knots=%d, kv=%p, n_pts=%d, pt_type=%x, points=%p) eg=%p\n",
1992  (void *)eu, order, n_knots, (void *)eg->k.knots,
1993  n_pts, (unsigned int)pt_type,
1994  (void *)eg->ctl_points, (void *)eg);
1995  }
1996 }
1997 
1998 
1999 /**
2000  * For an edgeuse associated with a face_g_snurb surface, create a
2001  * spline "curve" in the parameter space of the snurb which describes
2002  * a STRAIGHT LINE in parameter space from the u, v parameters of the
2003  * start vertex to the end vertex.
2004  *
2005  * The parameters of the end points are found in the vertexuse
2006  * attributes at either end of the edgeuse, which should have already
2007  * been established.
2008  *
2009  * This is a special case of nmg_edge_g_cnurb(), and should be used
2010  * when the path through parameter space is known to be a line
2011  * segment. This permits the savings of a lot of memory, both in core
2012  * and on disk, by eliminating a knot vector (typ. 64 bytes or more)
2013  * and a ctl_point[] array (typ. 16 bytes or more).
2014  *
2015  * This special condition is indicated by order == 0. See nmg.h for
2016  * details.
2017  */
2018 void
2019 nmg_edge_g_cnurb_plinear(struct edgeuse *eu)
2020 {
2021  struct model *m;
2022  struct edge_g_cnurb *eg;
2023  struct edge *e;
2024  struct faceuse *fu;
2025 
2026  NMG_CK_EDGEUSE(eu);
2027  e = eu->e_p;
2028  NMG_CK_EDGE(e);
2029  NMG_CK_VERTEXUSE(eu->vu_p);
2030  NMG_CK_VERTEX(eu->vu_p->v_p);
2031  NMG_CK_VERTEX_G(eu->vu_p->v_p->vg_p);
2032 
2033  NMG_CK_EDGEUSE(eu->eumate_p);
2034  NMG_CK_VERTEXUSE(eu->eumate_p->vu_p);
2035  NMG_CK_VERTEX(eu->eumate_p->vu_p->v_p);
2036  NMG_CK_VERTEX_G(eu->eumate_p->vu_p->v_p->vg_p);
2037 
2038  NMG_CK_VERTEXUSE_A_CNURB(eu->vu_p->a.cnurb_p);
2039  NMG_CK_VERTEXUSE_A_CNURB(eu->eumate_p->vu_p->a.cnurb_p);
2040 
2041  if (eu->g.cnurb_p) {
2042  bu_bomb("nmg_edge_g_cnurb_plinear() geometry already assigned\n");
2043  }
2044  fu = nmg_find_fu_of_eu(eu);
2045  NMG_CK_FACEUSE(fu);
2046  NMG_CK_FACE_G_SNURB(fu->f_p->g.snurb_p);
2047 
2048  /* Make new edge_g structure */
2049  m = nmg_find_model(&eu->l.magic);
2050  GET_EDGE_G_CNURB(eg, m);
2051  BU_LIST_INIT(&eg->eu_hd2);
2052 
2053  eg->order = 0; /* SPECIAL FLAG */
2054 
2055  /* Dequeue edgeuses from their current list (should point to themselves), add to new list */
2056  BU_LIST_DEQUEUE(&eu->l2);
2057  BU_LIST_DEQUEUE(&eu->eumate_p->l2);
2058 
2059  /* Associate edgeuse with this geometry */
2060  BU_LIST_INSERT(&eg->eu_hd2, &eu->l2);
2061  BU_LIST_INSERT(&eg->eu_hd2, &eu->eumate_p->l2);
2062  eu->g.cnurb_p = eg;
2063  eu->eumate_p->g.cnurb_p = eg;
2064 
2065  eg->l.magic = NMG_EDGE_G_CNURB_MAGIC;
2066 
2067  if (RTG.NMG_debug & DEBUG_BASIC) {
2068  bu_log("nmg_edge_g_cnurb_plinear(eu=%p) order=0, eg=%p\n",
2069  (void *)eu, (void *)eg);
2070  }
2071 }
2072 
2073 
2074 /**
2075  * Associate edgeuse 'eu' with the edge_g_X structure given as
2076  * 'magic_p'. If the edgeuse is already associated with some
2077  * geometry, release that first. Note that, to start with, the two
2078  * edgeuses may be using different original geometries.
2079  *
2080  * Also do the edgeuse mate.
2081  *
2082  * Returns -
2083  * 0 If the old edge geometry (eu->g.magic_p) has other uses.
2084  * 1 If the old edge geometry has been destroyed. Caller beware!
2085  */
2086 int
2087 nmg_use_edge_g(struct edgeuse *eu, uint32_t *magic_p)
2088 {
2089  struct edge_g_lseg *old;
2090  /* eg->eu_hd2 is a pun for eu_hd2 in either _lseg or _cnurb */
2091  struct edge_g_lseg *eg = (struct edge_g_lseg *)magic_p;
2092  int ndead = 0;
2093 
2094  if (!magic_p) return 0; /* Don't use a null new geom */
2095 
2096  NMG_CK_EDGEUSE(eu);
2097  NMG_CK_EDGE_G_LSEG(eg);
2098  if (eu == eu->eumate_p) bu_bomb("nmg_use_edge_g() eu == eumate_p!\n");
2099 
2100  old = eu->g.lseg_p; /* This may be NULL. For printing only. */
2101 
2102  /* Handle edgeuse */
2103  if (eu->g.lseg_p != eg && eu->g.lseg_p) {
2104 
2105  NMG_CK_EDGE_G_LSEG(eu->g.lseg_p);
2106 
2107  BU_LIST_DEQUEUE(&eu->l2);
2108  ndead += nmg_keg(eu);
2109  eu->g.magic_p = NULL;
2110  }
2111  if (eu->g.lseg_p != eg) {
2112  BU_LIST_INSERT(&eg->eu_hd2, &(eu->l2));
2113  eu->g.magic_p = magic_p;
2114  }
2115 
2116  /* Handle edgeuse mate separately */
2117  if (eu->eumate_p->g.lseg_p != eg && eu->eumate_p->g.lseg_p) {
2118  struct edgeuse *mate = eu->eumate_p;
2119 
2120  NMG_CK_EDGEUSE(mate);
2121  NMG_CK_EDGE_G_LSEG(mate->g.lseg_p);
2122 
2123  BU_LIST_DEQUEUE(&mate->l2);
2124  ndead += nmg_keg(mate);
2125  mate->g.magic_p = NULL;
2126  }
2127 
2128  if (eu->eumate_p->g.lseg_p != eg) {
2129  BU_LIST_INSERT(&eg->eu_hd2, &(eu->eumate_p->l2));
2130  eu->eumate_p->g.magic_p = magic_p;
2131  }
2132  if (eu->g.magic_p != eu->eumate_p->g.magic_p) bu_bomb("nmg_use_edge_g() eu and mate not using same geometry?\n");
2133 
2134  if (RTG.NMG_debug & DEBUG_BASIC) {
2135  bu_log("nmg_use_edge_g(eu=%p, magic_p=%p) old_eg=%p, ret=%d\n",
2136  (void *)eu, (void *)magic_p, (void *)old, ndead);
2137  }
2138  return ndead;
2139 }
2140 
2141 
2142 /**
2143  * Build the bounding box for a loop.
2144  *
2145  * The bounding box is guaranteed never to have zero thickness.
2146  *
2147  * XXX This really isn't loop geometry, this is a loop attribute.
2148  * This routine really should be called nmg_loop_bb(), unless it gets
2149  * something more to do.
2150  */
2151 void
2152 nmg_loop_g(struct loop *l, const struct bn_tol *tol)
2153 {
2154  struct edgeuse *eu;
2155  struct vertex_g *vg;
2156  struct loop_g *lg;
2157  struct loopuse *lu;
2158  struct model *m;
2159  uint32_t magic1;
2160  fastf_t thickening;
2161 
2162  NMG_CK_LOOP(l);
2163  BN_CK_TOL(tol);
2164  lu = l->lu_p;
2165  NMG_CK_LOOPUSE(lu);
2166 
2167  lg = l->lg_p;
2168  if (lg) {
2169  NMG_CK_LOOP_G(lg);
2170  } else {
2171  m = nmg_find_model(lu->up.magic_p);
2172  GET_LOOP_G(l->lg_p, m);
2173  lg = l->lg_p;
2174  lg->magic = NMG_LOOP_G_MAGIC;
2175  }
2176  VSETALL(lg->max_pt, -INFINITY);
2177  VSETALL(lg->min_pt, INFINITY);
2178 
2179  magic1 = BU_LIST_FIRST_MAGIC(&lu->down_hd);
2180  if (magic1 == NMG_EDGEUSE_MAGIC) {
2181  for (BU_LIST_FOR (eu, edgeuse, &lu->down_hd)) {
2182  vg = eu->vu_p->v_p->vg_p;
2183  NMG_CK_VERTEX_G(vg);
2184  VMINMAX(lg->min_pt, lg->max_pt, vg->coord);
2185  if (!eu->g.magic_p && eu->vu_p->v_p != eu->eumate_p->vu_p->v_p)
2186  nmg_edge_g(eu);
2187  }
2188  } else if (magic1 == NMG_VERTEXUSE_MAGIC) {
2189  struct vertexuse *vu;
2190  vu = BU_LIST_FIRST(vertexuse, &lu->down_hd);
2191  NMG_CK_VERTEXUSE(vu);
2192  NMG_CK_VERTEX(vu->v_p);
2193  vg = vu->v_p->vg_p;
2194  NMG_CK_VERTEX_G(vg);
2195  VMOVE(lg->min_pt, vg->coord);
2196  VMOVE(lg->max_pt, vg->coord);
2197  } else {
2198  bu_log("nmg_loop_g() loopuse down is %s (%x)\n",
2199  bu_identify_magic(magic1), magic1);
2200  bu_bomb("nmg_loop_g() loopuse has bad child\n");
2201  }
2202 
2203  /* Pad the dimension of the loop bounding box which is less than
2204  * distance tolerance so that the resulting dimension will be
2205  * at least distance tolerance.
2206  */
2207  thickening = 0.5 * tol->dist;
2208  if (NEAR_ZERO(lg->max_pt[X] - lg->min_pt[X], tol->dist)) {
2209  lg->min_pt[X] -= thickening;
2210  lg->max_pt[X] += thickening;
2211  }
2212  if (NEAR_ZERO(lg->max_pt[Y] - lg->min_pt[Y], tol->dist)) {
2213  lg->min_pt[Y] -= thickening;
2214  lg->max_pt[Y] += thickening;
2215  }
2216  if (NEAR_ZERO(lg->max_pt[Z] - lg->min_pt[Z], tol->dist)) {
2217  lg->min_pt[Z] -= thickening;
2218  lg->max_pt[Z] += thickening;
2219  }
2220 
2221  if (RTG.NMG_debug & DEBUG_BASIC) {
2222  bu_log("nmg_loop_g(l=%p, tol=%p)\n", (void *)l, (void *)tol);
2223  }
2224 
2225 }
2226 
2227 
2228 /**
2229  * Assign plane equation to face.
2230  * XXX Should probably be called nmg_face_g_plane()
2231  *
2232  * In the interest of modularity this no longer calls nmg_face_bb().
2233  */
2234 void
2235 nmg_face_g(struct faceuse *fu, const fastf_t *p)
2236 {
2237  int i;
2238  struct face_g_plane *fg;
2239  struct face *f;
2240  struct model *m;
2241 
2242  NMG_CK_FACEUSE(fu);
2243  f = fu->f_p;
2244  NMG_CK_FACE(f);
2245 
2246  fu->orientation = OT_SAME;
2247  fu->fumate_p->orientation = OT_OPPOSITE;
2248 
2249  fg = f->g.plane_p;
2250  if (fg) {
2251  /* Face already has face_g_plane associated with it */
2252  NMG_CK_FACE_G_PLANE(fg);
2253  } else {
2254  m = nmg_find_model(&fu->l.magic);
2255  GET_FACE_G_PLANE(f->g.plane_p, m);
2256  f->flip = 0;
2257  fg = f->g.plane_p;
2258  fg->magic = NMG_FACE_G_PLANE_MAGIC;
2259  BU_LIST_INIT(&fg->f_hd);
2260  BU_LIST_APPEND(&fg->f_hd, &f->l);
2261  }
2262 
2263  if (f->flip) {
2264  for (i=0; i < ELEMENTS_PER_PLANE; i++)
2265  fg->N[i] = -p[i];
2266  } else {
2267  HMOVE(fg->N, p);
2268  }
2269 
2270  if (RTG.NMG_debug & DEBUG_BASIC) {
2271  bu_log("nmg_face_g(fu=%p, p=(%g %g %g %g))\n", (void *)fu, V4ARGS(p));
2272  }
2273 }
2274 
2275 
2276 /**
2277  * Assign plane equation to this face. If other faces use current
2278  * geometry for this face, then make a new geometry for this face.
2279  */
2280 void
2281 nmg_face_new_g(struct faceuse *fu, const fastf_t *pl)
2282 {
2283  struct face *f;
2284  struct face *f_tmp;
2285  struct face_g_plane *fg;
2286  struct model *m;
2287  int use_count=0;
2288 
2289  NMG_CK_FACEUSE(fu);
2290  f = fu->f_p;
2291  NMG_CK_FACE(f);
2292  fg = f->g.plane_p;
2293 
2294  /* if this face has no geometry, just call nmg_face_g() */
2295  if (!fg) {
2296  nmg_face_g(fu, pl);
2297  return;
2298  }
2299 
2300  /* count uses of this face geometry */
2301  for (BU_LIST_FOR (f_tmp, face, &fg->f_hd))
2302  use_count++;
2303 
2304  /* if this is the only use, just call nmg_face_g() */
2305  if (use_count < 2) {
2306  nmg_face_g(fu, pl);
2307  return;
2308  }
2309 
2310  /* There is at least one other use of this face geometry */
2311 
2312  fu->orientation = OT_SAME;
2313  fu->fumate_p->orientation = OT_OPPOSITE;
2314 
2315  /* dequeue this face from fg's face list */
2316  BU_LIST_DEQUEUE(&f->l);
2317 
2318  /* get a new geometry structure */
2319  m = nmg_find_model(&fu->l.magic);
2320  GET_FACE_G_PLANE(f->g.plane_p, m);
2321  f->flip = 0;
2322  fg = f->g.plane_p;
2323  fg->magic = NMG_FACE_G_PLANE_MAGIC;
2324  BU_LIST_INIT(&fg->f_hd);
2325  BU_LIST_APPEND(&fg->f_hd, &f->l);
2326 
2327  HMOVE(fg->N, pl);
2328 
2329  if (RTG.NMG_debug & DEBUG_BASIC) {
2330  bu_log("nmg_face_new_g(fu=%p, pl=(%g %g %g %g))\n", (void *)fu, V4ARGS(pl));
2331  }
2332 }
2333 
2334 
2335 /**
2336  * Create a new NURBS surface to be the geometry for an NMG face.
2337  *
2338  * If either of the knot vector arrays or the ctl_points arrays are
2339  * given as non-null, then simply swipe the caller's arrays. The
2340  * caller must have allocated them with bu_malloc() or malloc(). If
2341  * the pointers are NULL, then the necessary storage is allocated
2342  * here.
2343  *
2344  * This is the NMG parallel to rt_nurb_new_snurb().
2345  */
2346 void
2347 nmg_face_g_snurb(struct faceuse *fu, int u_order, int v_order, int n_u_knots,
2348  int n_v_knots, fastf_t *ukv, fastf_t *vkv, int n_rows, int n_cols,
2349  int pt_type, fastf_t *mesh)
2350 {
2351  struct face_g_snurb *fg;
2352  struct face *f;
2353  struct model *m;
2354 
2355  NMG_CK_FACEUSE(fu);
2356  f = fu->f_p;
2357  NMG_CK_FACE(f);
2358 
2359  fu->orientation = OT_SAME;
2360  fu->fumate_p->orientation = OT_OPPOSITE;
2361 
2362  fg = f->g.snurb_p;
2363  if (fg) {
2364  /* Face already has geometry associated with it */
2365  bu_bomb("nmg_face_g_snurb() face already has geometry\n");
2366  }
2367 
2368  m = nmg_find_model(&fu->l.magic);
2369  GET_FACE_G_SNURB(f->g.snurb_p, m);
2370  fg = f->g.snurb_p;
2371 
2372  fg->order[0] = u_order;
2373  fg->order[1] = v_order;
2374  fg->u.magic = NMG_KNOT_VECTOR_MAGIC;
2375  fg->v.magic = NMG_KNOT_VECTOR_MAGIC;
2376  fg->u.k_size = n_u_knots;
2377  fg->v.k_size = n_v_knots;
2378 
2379  if (ukv) {
2380  fg->u.knots = ukv;
2381  } else {
2382  fg->u.knots = (fastf_t *)bu_calloc(n_u_knots, sizeof(fastf_t), "u.knots[]");
2383  }
2384  if (vkv) {
2385  fg->v.knots = vkv;
2386  } else {
2387  fg->v.knots = (fastf_t *)bu_calloc(n_v_knots, sizeof(fastf_t), "v.knots[]");
2388  }
2389 
2390  fg->s_size[0] = n_rows;
2391  fg->s_size[1] = n_cols;
2392  fg->pt_type = pt_type;
2393 
2394  if (mesh) {
2395  fg->ctl_points = mesh;
2396  } else {
2397  int nwords;
2398  nwords = n_rows * n_cols * RT_NURB_EXTRACT_COORDS(pt_type);
2399  fg->ctl_points = (fastf_t *)bu_calloc(
2400  nwords, sizeof(fastf_t), "snurb ctl_points[]");
2401  }
2402 
2403  f->flip = 0;
2404  BU_LIST_INIT(&fg->f_hd);
2405  BU_LIST_APPEND(&fg->f_hd, &f->l);
2406  fg->l.magic = NMG_FACE_G_SNURB_MAGIC;
2407 
2408  if (RTG.NMG_debug & DEBUG_BASIC) {
2409  bu_log("nmg_face_g_snurb(fu=%p, u_order=%d, v_order=%d, n_u_knots=%d, n_v_knots=%d, "
2410  "ukv=%p, vkv=%p, n_rows=%d, n_cols=%d, pt_type=%x, "
2411  "mesh=%p) fg=%p\n",
2412  (void *)fu, u_order, v_order, n_u_knots, n_v_knots,
2413  (void *)fg->u.knots, (void *)fg->v.knots, n_rows, n_cols, (unsigned int)pt_type,
2414  (void *)fg->ctl_points, (void *)fg);
2415  }
2416 }
2417 
2418 
2419 /**
2420  * Build the bounding box for a face
2421  */
2422 void
2423 nmg_face_bb(struct face *f, const struct bn_tol *tol)
2424 {
2425  struct loopuse *lu;
2426  struct faceuse *fu;
2427 
2428  BN_CK_TOL(tol);
2429  NMG_CK_FACE(f);
2430  fu = f->fu_p;
2431  NMG_CK_FACEUSE(fu);
2432 
2433  f->max_pt[X] = f->max_pt[Y] = f->max_pt[Z] = -MAX_FASTF;
2434  f->min_pt[X] = f->min_pt[Y] = f->min_pt[Z] = MAX_FASTF;
2435 
2436  /* compute the extent of the face by looking at the extent of
2437  * each of the loop children.
2438  */
2439  for (BU_LIST_FOR (lu, loopuse, &fu->lu_hd)) {
2440  nmg_loop_g(lu->l_p, tol);
2441 
2442  if (lu->orientation != OT_BOOLPLACE) {
2443  VMIN(f->min_pt, lu->l_p->lg_p->min_pt);
2444  VMAX(f->max_pt, lu->l_p->lg_p->max_pt);
2445  }
2446  }
2447 
2448  /* Note, calculating the bounding box for face_g_snurbs
2449  * from the extents of the loop does not work
2450  * since the loops are most likely in parametric space
2451  * thus we need to calculate the bounding box for the
2452  * face_g_snurb here instead. There may be a more efficient
2453  * way, and one may need some time to take a good look at
2454  * this
2455  */
2456 
2457  if (*fu->f_p->g.magic_p == NMG_FACE_G_SNURB_MAGIC) {
2458  rt_nurb_s_bound(fu->f_p->g.snurb_p, fu->f_p->g.snurb_p->min_pt,
2459  fu->f_p->g.snurb_p->max_pt);
2460  VMIN(f->min_pt, fu->f_p->g.snurb_p->min_pt);
2461  VMAX(f->max_pt, fu->f_p->g.snurb_p->max_pt);
2462  }
2463 
2464  if (RTG.NMG_debug & DEBUG_BASIC) {
2465  bu_log("nmg_face_bb(f=%p, tol=%p)\n", (void *)f, (void *)tol);
2466  }
2467 }
2468 
2469 
2470 /**
2471  * Build the bounding box for a shell
2472  */
2473 void
2474 nmg_shell_a(struct shell *s, const struct bn_tol *tol)
2475 {
2476  struct shell_a *sa;
2477  struct vertex_g *vg;
2478  struct faceuse *fu;
2479  struct loopuse *lu;
2480  struct edgeuse *eu;
2481  struct model *m;
2482 
2483  NMG_CK_SHELL(s);
2484  BN_CK_TOL(tol);
2485 
2486  if (s->sa_p) {
2487  NMG_CK_SHELL_A(s->sa_p);
2488  } else {
2489  m = nmg_find_model(&s->l.magic);
2490  GET_SHELL_A(s->sa_p, m);
2491  s->sa_p->magic = NMG_SHELL_A_MAGIC;
2492  }
2493  sa = s->sa_p;
2494 
2495  VSETALL(sa->max_pt, -MAX_FASTF);
2496  VSETALL(sa->min_pt, MAX_FASTF);
2497 
2498  for (BU_LIST_FOR (fu, faceuse, &s->fu_hd)) {
2499  struct face *f;
2500 
2501  f = fu->f_p;
2502  NMG_CK_FACE(f);
2503  nmg_face_bb(f, tol);
2504 
2505  VMIN(sa->min_pt, f->min_pt);
2506  VMAX(sa->max_pt, f->max_pt);
2507 
2508  /* If next faceuse shares this face, skip it */
2509  if (BU_LIST_NOT_HEAD(fu, &fu->l) &&
2510  (BU_LIST_NEXT(faceuse, &fu->l)->f_p == f)) {
2511  fu = BU_LIST_PNEXT(faceuse, fu);
2512  }
2513  }
2514  for (BU_LIST_FOR (lu, loopuse, &s->lu_hd)) {
2515  nmg_loop_g(lu->l_p, tol);
2516 
2517  VMIN(sa->min_pt, lu->l_p->lg_p->min_pt);
2518  VMAX(sa->max_pt, lu->l_p->lg_p->max_pt);
2519  }
2520  for (BU_LIST_FOR (eu, edgeuse, &s->eu_hd)) {
2521  NMG_CK_EDGEUSE(eu);
2522  NMG_CK_EDGE(eu->e_p);
2523  vg = eu->vu_p->v_p->vg_p;
2524  NMG_CK_VERTEX_G(vg);
2525  VMINMAX(sa->min_pt, sa->max_pt, vg->coord);
2526  }
2527  if (s->vu_p) {
2528  NMG_CK_VERTEXUSE(s->vu_p);
2529  NMG_CK_VERTEX(s->vu_p->v_p);
2530  if (s->vu_p->v_p->vg_p) {
2531  NMG_CK_VERTEX_G(s->vu_p->v_p->vg_p);
2532  vg = s->vu_p->v_p->vg_p;
2533  VMINMAX(sa->min_pt, sa->max_pt, vg->coord);
2534  }
2535  }
2536 
2537 
2538  if (BU_LIST_IS_EMPTY(&s->fu_hd) &&
2539  BU_LIST_IS_EMPTY(&s->lu_hd) &&
2540  BU_LIST_IS_EMPTY(&s->eu_hd) && !s->vu_p) {
2541  bu_log("nmg_shell_a() at %d in %s. Shell has no children\n",
2542  __LINE__, __FILE__);
2543  bu_bomb("nmg_shell_a\n");
2544  }
2545 
2546  if (RTG.NMG_debug & DEBUG_BASIC) {
2547  bu_log("nmg_shell_a(s=%p, tol=%p)\n", (void *)s, (void *)tol);
2548  }
2549 }
2550 
2551 
2552 /**
2553  * build attributes/extents for all shells in a region
2554  *
2555  */
2556 void
2557 nmg_region_a(struct nmgregion *r, const struct bn_tol *tol)
2558 {
2559  register struct shell *s;
2560  struct nmgregion_a *ra;
2561 
2562  NMG_CK_REGION(r);
2563  BN_CK_TOL(tol);
2564  if (r->ra_p) {
2565  ra = r->ra_p;
2566  NMG_CK_REGION_A(ra);
2567  } else {
2568  GET_REGION_A(ra, r->m_p);
2569  r->ra_p = ra;
2570  }
2571 
2572  ra->magic = NMG_REGION_A_MAGIC;
2573 
2574  VSETALL(ra->max_pt, -MAX_FASTF);
2575  VSETALL(ra->min_pt, MAX_FASTF);
2576 
2577  for (BU_LIST_FOR (s, shell, &r->s_hd)) {
2578  nmg_shell_a(s, tol);
2579  NMG_CK_SHELL_A(s->sa_p);
2580  VMIN(ra->min_pt, s->sa_p->min_pt);
2581  VMAX(ra->max_pt, s->sa_p->max_pt);
2582  }
2583 
2584  if (RTG.NMG_debug & DEBUG_BASIC) {
2585  bu_log("nmg_region_a(r=%p, tol=%p)\n", (void *)r, (void *)tol);
2586  }
2587 }
2588 
2589 
2590 /************************************************************************
2591  * *
2592  * "Demote" Routines *
2593  * *
2594  * As part of the boolean operations, sometimes it is desirable *
2595  * to "demote" entities down the "chain of being". The sequence is: *
2596  * *
2597  * face --> wire loop --> wire edge (line segment) --> vertex *
2598  * *
2599  ************************************************************************/
2600 
2601 
2602 /**
2603  * Demote a loopuse of edgeuses to a bunch of wire edges in the shell.
2604  *
2605  * Returns -
2606  * 0 If all is well (edges moved to shell, loopuse deleted).
2607  * 1 If parent is empty, and is thus "illegal". Still successful.
2608  */
2609 int
2610 nmg_demote_lu(struct loopuse *lu1)
2611 {
2612  struct edgeuse *eu1;
2613  uintptr_t tmp;
2614  struct shell *s;
2615  int ret_val;
2616 
2617  NMG_CK_LOOPUSE(lu1);
2618 
2619  if (RTG.NMG_debug & DEBUG_CLASSIFY)
2620  bu_log("nmg_demote_lu(%p)\n", (void *)lu1);
2621 
2622  if (BU_LIST_FIRST_MAGIC(&lu1->down_hd) == NMG_VERTEXUSE_MAGIC) {
2623  bu_bomb("nmg_demote_lu() demoting loopuse of a single vertex\n");
2624  }
2625 
2626  if (BU_LIST_FIRST_MAGIC(&lu1->down_hd) != NMG_EDGEUSE_MAGIC)
2627  bu_bomb("nmg_demote_lu: bad loopuse child\n");
2628 
2629  /* get the parent shell */
2630  s = nmg_find_s_of_lu(lu1);
2631  NMG_CK_SHELL(s);
2632 
2633  /* move all edgeuses (&mates) to shell
2634  */
2635  while (BU_LIST_NON_EMPTY(&lu1->down_hd)) {
2636 
2637  eu1 = BU_LIST_FIRST(edgeuse, &lu1->down_hd);
2638  NMG_CK_EDGEUSE(eu1);
2639  NMG_CK_EDGE(eu1->e_p);
2640  NMG_CK_EDGEUSE(eu1->eumate_p);
2641  NMG_CK_EDGE(eu1->eumate_p->e_p);
2642 
2643  BU_LIST_DEQUEUE(&eu1->eumate_p->l);
2644  BU_LIST_APPEND(&s->eu_hd, &eu1->eumate_p->l);
2645 
2646  BU_LIST_DEQUEUE(&eu1->l);
2647  BU_LIST_APPEND(&s->eu_hd, &eu1->l);
2648 
2649  eu1->up.s_p = eu1->eumate_p->up.s_p = s;
2650  }
2651  /* lu1 is in an illegal state here, with a null edge list */
2652 
2653  if (BU_LIST_NON_EMPTY(&lu1->lumate_p->down_hd))
2654  bu_bomb("nmg_demote_lu: loopuse mates don't have same # of edges\n");
2655 
2656  tmp = (uintptr_t)lu1;
2657  ret_val = nmg_klu(lu1);
2658 
2659  if (RTG.NMG_debug & DEBUG_BASIC) {
2660  bu_log("nmg_demote_lu(lu=%p) returns %d\n", (void *)tmp, ret_val);
2661  }
2662 
2663  return ret_val;
2664 }
2665 
2666 
2667 /**
2668  * Demote a wire edge into a pair of self-loop vertices
2669  *
2670  *
2671  * Returns -
2672  * 0 If all is well
2673  * 1 If shell is empty, and is thus "illegal".
2674  */
2675 int
2676 nmg_demote_eu(struct edgeuse *eu)
2677 {
2678  struct shell *s;
2679  struct vertex *v;
2680  int ret_val;
2681  size_t tmp;
2682 
2683  if (*eu->up.magic_p != NMG_SHELL_MAGIC)
2684  bu_bomb("nmg_demote_eu() up is not shell\n");
2685  s = eu->up.s_p;
2686  NMG_CK_SHELL(s);
2687 
2688  NMG_CK_EDGEUSE(eu);
2689  v = eu->vu_p->v_p;
2691  (void)nmg_mlv(&s->l.magic, v, OT_SAME);
2692 
2693  NMG_CK_EDGEUSE(eu->eumate_p);
2694  v = eu->eumate_p->vu_p->v_p;
2696  (void)nmg_mlv(&s->l.magic, v, OT_SAME);
2697 
2698  tmp = (size_t)eu;
2699  (void)nmg_keu(eu);
2700 
2701  ret_val = nmg_shell_is_empty(s);
2702 
2703  if (RTG.NMG_debug & DEBUG_BASIC) {
2704  bu_log("nmg_demote_eu(eu=%p) returns %d\n", (void *)tmp, ret_val);
2705  }
2706 
2707  return ret_val;
2708 }
2709 
2710 
2711 /************************************************************************
2712  * *
2713  * "Modify" Routines *
2714  * *
2715  * These routines would go in nmg_mod.c, except that they create *
2716  * or delete fundamental entities directly as part of their operation. *
2717  * Thus, they are part of the make/kill purpose of this module. *
2718  * *
2719  ************************************************************************/
2720 
2721 
2722 /**
2723  * Move a vertexuse from an old vertex to a new vertex. If this was
2724  * the last use, the old vertex is destroyed.
2725  *
2726  * XXX nmg_jvu() as a better name?
2727  */
2728 void
2729 nmg_movevu(struct vertexuse *vu, struct vertex *v)
2730 {
2731  struct vertex *oldv;
2732 
2733  NMG_CK_VERTEXUSE(vu);
2734  NMG_CK_VERTEX(v);
2735 
2736  oldv = vu->v_p;
2737  NMG_CK_VERTEX(oldv);
2738 
2739  BU_LIST_DEQUEUE(&vu->l);
2740  if (BU_LIST_IS_EMPTY(&oldv->vu_hd)) {
2741  /* last vertexuse on vertex */
2742  if (oldv->vg_p) FREE_VERTEX_G(oldv->vg_p);
2743  FREE_VERTEX(oldv);
2744  }
2745  BU_LIST_APPEND(&v->vu_hd, &vu->l);
2746  vu->v_p = v;
2747 
2748  if (RTG.NMG_debug & DEBUG_BASIC) {
2749  bu_log("nmg_movevu(vu=%p, v=%p)\n", (void *)vu, (void *)v);
2750  }
2751 }
2752 
2753 
2754 /**
2755  * Move a pair of edgeuses onto a single edge (glue edgeuse). The
2756  * edgeuse eusrc and its mate are moved to the edge used by eudst.
2757  * eusrc is made to be immediately radial to eudst. if eusrc does not
2758  * share the same vertices as eudst, we bomb.
2759  *
2760  * The edgeuse geometry pointers are not changed by this operation.
2761  *
2762  * This routine was formerly called nmg_moveeu().
2763  */
2764 void
2765 nmg_je(struct edgeuse *eudst, struct edgeuse *eusrc)
2766 {
2767  struct edgeuse *eudst_mate;
2768  struct edgeuse *eusrc_mate;
2769  struct edge *e;
2770 
2771  NMG_CK_EDGEUSE(eudst);
2772  NMG_CK_EDGEUSE(eusrc);
2773  eudst_mate = eudst->eumate_p;
2774  eusrc_mate = eusrc->eumate_p;
2775  NMG_CK_EDGEUSE(eudst_mate);
2776  NMG_CK_EDGEUSE(eusrc_mate);
2777 
2778  /* protect the morons from themselves. Don't let them
2779  * move an edgeuse to itself or its mate
2780  */
2781  if (eusrc == eudst || eusrc_mate == eudst) {
2782  bu_log("nmg_je() moving edgeuse to itself\n");
2783  return;
2784  }
2785 
2786  if (eusrc->e_p == eudst->e_p &&
2787  (eusrc->radial_p == eudst || eudst->radial_p == eusrc)) {
2788  bu_log("nmg_je() edgeuses already share edge\n");
2789  return;
2790  }
2791 
2792  /* make sure vertices are shared */
2793  if (! ((eudst_mate->vu_p->v_p == eusrc->vu_p->v_p &&
2794  eudst->vu_p->v_p == eusrc_mate->vu_p->v_p) ||
2795  (eudst->vu_p->v_p == eusrc->vu_p->v_p &&
2796  eudst_mate->vu_p->v_p == eusrc_mate->vu_p->v_p))) {
2797  /* edgeuses do NOT share vertices. */
2798  bu_log("eusrc (v=%p) (%g %g %g)\n",
2799  (void *)eusrc->vu_p->v_p, V3ARGS(eusrc->vu_p->v_p->vg_p->coord));
2800  bu_log("eusrc_mate (v=%p) (%g %g %g)\n",
2801  (void *)eusrc_mate->vu_p->v_p, V3ARGS(eusrc_mate->vu_p->v_p->vg_p->coord));
2802  bu_log("eudst (v=%p) (%g %g %g)\n",
2803  (void *)eudst->vu_p->v_p, V3ARGS(eudst->vu_p->v_p->vg_p->coord));
2804  bu_log("eudst_mate (v=%p) (%g %g %g)\n",
2805  (void *)eudst_mate->vu_p->v_p, V3ARGS(eudst_mate->vu_p->v_p->vg_p->coord));
2806  bu_bomb("nmg_je() edgeuses do not share vertices, cannot share edge\n");
2807  }
2808 
2809  e = eusrc->e_p;
2810  eusrc_mate->e_p = eusrc->e_p = eudst->e_p;
2811 
2812  /* if we're not deleting the edge, make sure it will be able
2813  * to reference the remaining uses, otherwise, take care of disposing
2814  * of the (now unused) edge
2815  */
2816  if (eusrc->radial_p != eusrc_mate) {
2817  /* this is NOT the only use of the eusrc edge! */
2818  if (e->eu_p == eusrc || e->eu_p == eusrc_mate)
2819  e->eu_p = eusrc->radial_p;
2820 
2821  /* disconnect from the list of uses of this edge */
2822  eusrc->radial_p->radial_p = eusrc_mate->radial_p;
2823  eusrc_mate->radial_p->radial_p = eusrc->radial_p;
2824  } else {
2825  /* FIXME: this used to call FREE_EDGE() here but is now a
2826  * potential memory leak. need to evaluate callers of
2827  * nmg_je() to make sure they are managing memory release
2828  * properly and/or re-add release of memory in here if needed.
2829  */
2830 
2831  /* this is the only use of the eusrc edge. kill/free edge but not
2832  * here. the edge should be freed by the calling function which can
2833  * determine this edge should be freed by its edgeuse pointer
2834  * pointing to itself and the magic number set to zero.
2835  */
2836  e->eu_p = (struct edgeuse *)e;
2837  e->magic = 0;
2838  }
2839 
2840  eusrc->radial_p = eudst;
2841  eusrc_mate->radial_p = eudst->radial_p;
2842 
2843  eudst->radial_p->radial_p = eusrc_mate;
2844  eudst->radial_p = eusrc;
2845 
2846  if (RTG.NMG_debug & DEBUG_BASIC) {
2847  bu_log("nmg_je(eudst=%p, eusrc=%p)\n", (void *)eudst, (void *)eusrc);
2848  }
2849 }
2850 
2851 
2852 /**
2853  * If edgeuse is part of a shared edge (more than one pair of edgeuses
2854  * on the edge), it and its mate are "unglued" from the edge, and
2855  * associated with a new edge structure.
2856  *
2857  * Primarily a support routine for nmg_eusplit()
2858  *
2859  * If the original edge had edge geometry, that is *not* duplicated
2860  * here, because it is not easy (or appropriate) for nmg_eusplit() to
2861  * know whether the new vertex lies on the previous edge geometry or
2862  * not. Hence having the nmg_ebreak() interface, which preserves the
2863  * ege geometry across a split, and nmg_esplit() which does not.
2864  */
2865 void
2866 nmg_unglueedge(struct edgeuse *eu)
2867 {
2868  struct edge *old_e;
2869  struct edge *new_e;
2870  struct model *m;
2871 
2872  NMG_CK_EDGEUSE(eu);
2873  old_e = eu->e_p;
2874  NMG_CK_EDGE(old_e);
2875 
2876  /* if we're already a single edge, just return */
2877  if (eu->radial_p == eu->eumate_p) {
2878  if (RTG.NMG_debug & DEBUG_BASIC) {
2879  bu_log("nmg_unglueedge(eu=%p) (nothing unglued)\n", (void *)eu);
2880  }
2881  return;
2882  }
2883 
2884  m = nmg_find_model(&eu->l.magic);
2885  GET_EDGE(new_e, m); /* create new edge */
2886 
2887  new_e->magic = NMG_EDGE_MAGIC;
2888  new_e->eu_p = eu;
2889 
2890  /* make sure the old edge isn't pointing at this edgeuse */
2891  if (old_e->eu_p == eu || old_e->eu_p == eu->eumate_p) {
2892  old_e->eu_p = old_e->eu_p->radial_p;
2893  }
2894 
2895  /* unlink edgeuses from old edge */
2896  eu->radial_p->radial_p = eu->eumate_p->radial_p;
2897  eu->eumate_p->radial_p->radial_p = eu->radial_p;
2898  eu->eumate_p->radial_p = eu;
2899  eu->radial_p = eu->eumate_p;
2900 
2901  /* Associate edgeuse and mate with new edge */
2902  eu->eumate_p->e_p = eu->e_p = new_e;
2903 
2904  if (RTG.NMG_debug & DEBUG_BASIC) {
2905  bu_log("nmg_unglueedge(eu=%p)\n", (void *)eu);
2906  }
2907 }
2908 
2909 
2910 /**
2911  * Join two vertexes into one.
2912  *
2913  * v1 inherits all the vertexuses presently pointing to v2, and v2 is
2914  * then destroyed.
2915  */
2916 void
2917 nmg_jv(register struct vertex *v1, register struct vertex *v2)
2918 {
2919  register struct vertexuse *vu;
2920 
2921  NMG_CK_VERTEX(v1);
2922  NMG_CK_VERTEX(v2);
2923 
2924  if (v1 == v2) return;
2925 
2926  /*
2927  * Walk the v2 list, unlinking vertexuse structs,
2928  * and adding them to the *end* of the v1 list
2929  * (which preserves relative ordering).
2930  */
2931  vu = BU_LIST_FIRST(vertexuse, &v2->vu_hd);
2932  while (BU_LIST_NOT_HEAD(vu, &v2->vu_hd)) {
2933  register struct vertexuse *vunext;
2934 
2935  NMG_CK_VERTEXUSE(vu);
2936  vunext = BU_LIST_PNEXT(vertexuse, vu);
2937  BU_LIST_DEQUEUE(&vu->l);
2938  BU_LIST_INSERT(&v1->vu_hd, &vu->l);
2939  vu->v_p = v1; /* "up" to new vertex */
2940  vu = vunext;
2941  }
2942 
2943  /* Kill vertex v2 */
2944  if (v2->vg_p) {
2945  if (!v1->vg_p) {
2946  v1->vg_p = v2->vg_p;
2947  } else {
2948  FREE_VERTEX_G(v2->vg_p);
2949  }
2950  }
2951 
2952  if (RTG.NMG_debug & DEBUG_BASIC) {
2953  bu_log("nmg_jv(v1=%p, v2=%p)\n", (void *)v1, (void *)v2);
2954  }
2955 
2956  FREE_VERTEX(v2);
2957 }
2958 
2959 
2960 /**
2961  * Join two faces, so that they share one underlying face geometry.
2962  * The loops of the two faces remains unchanged.
2963  *
2964  * If one of the faces does not have any geometry, then it is made to
2965  * share the geometry of the other.
2966  */
2967 void
2968 nmg_jfg(struct face *f1, struct face *f2)
2969 {
2970  struct face_g_plane *fg1;
2971  struct face_g_plane *fg2;
2972  struct face *f;
2973 
2974  NMG_CK_FACE(f1);
2975  NMG_CK_FACE(f2);
2976  fg1 = f1->g.plane_p;
2977  fg2 = f2->g.plane_p;
2978  if (fg2 && !fg1) {
2979  /* Make f1 share existing geometry of f2 */
2980  NMG_CK_FACE_G_PLANE(fg1);
2981  f1->g.plane_p = fg2;
2982  f1->flip = f2->flip;
2983  BU_LIST_INSERT(&fg2->f_hd, &f1->l);
2984 
2985  if (RTG.NMG_debug & DEBUG_BASIC) {
2986  bu_log("nmg_jfg(f1=%p, f2=%p)\n", (void *)f1, (void *)f2);
2987  }
2988  return;
2989  }
2990  if (fg1 && !fg2) {
2991  /* Make f2 share existing geometry of f1 */
2992  NMG_CK_FACE_G_PLANE(fg1);
2993  f2->g.plane_p = fg1;
2994  f2->flip = f1->flip;
2995  BU_LIST_INSERT(&fg1->f_hd, &f2->l);
2996 
2997  if (RTG.NMG_debug & DEBUG_BASIC) {
2998  bu_log("nmg_jfg(f1=%p, f2=%p)\n", (void *)f1, (void *)f2);
2999  }
3000  return;
3001  }
3002 
3003  NMG_CK_FACE_G_PLANE(fg1);
3004  NMG_CK_FACE_G_PLANE(fg2);
3005 
3006  if (fg1 == fg2) {
3007  if (RTG.NMG_debug & DEBUG_BASIC) {
3008  bu_log("nmg_jfg(f1=%p, f2=%p)\n", (void *)f1, (void *)f2);
3009  }
3010  return;
3011  }
3012 
3013  /* Unhook all the faces on fg2 list, and add to fg1 list */
3014  while (BU_LIST_NON_EMPTY(&fg2->f_hd)) {
3015  f = BU_LIST_FIRST(face, &fg2->f_hd);
3016  BU_LIST_DEQUEUE(&f->l);
3017  NMG_CK_FACE(f);
3018  f->g.plane_p = fg1;
3019  /* flip flag is left unchanged here, on purpose */
3020  BU_LIST_INSERT(&fg1->f_hd, &f->l);
3021  }
3022 
3023  /* fg2 list is now empty, release that face geometry */
3024  FREE_FACE_G_PLANE(fg2);
3025 
3026  if (RTG.NMG_debug & DEBUG_BASIC) {
3027  bu_log("nmg_jfg(f1=%p, f2=%p)\n", (void *)f1, (void *)f2);
3028  }
3029 }
3030 
3031 
3032 /**
3033  * Join two edge geometries.
3034  *
3035  * For all edges in the model which refer to 'src_eg', change them to
3036  * refer to 'dest_eg'. The source is destroyed.
3037  *
3038  * It is the responsibility of the caller to make certain that the
3039  * 'dest_eg' is the best one for these edges. Outrageously wrong
3040  * requests will cause this routine to abort.
3041  *
3042  * This algorithm does not make sense if dest_eg is an edge_g_cnurb;
3043  * those only make sense in the parameter space of their associated
3044  * face.
3045  */
3046 void
3047 nmg_jeg(struct edge_g_lseg *dest_eg, struct edge_g_lseg *src_eg)
3048 {
3049  register struct edgeuse *eu;
3050 
3051  NMG_CK_EDGE_G_LSEG(src_eg);
3052  NMG_CK_EDGE_G_LSEG(dest_eg);
3053  if (RTG.NMG_debug & DEBUG_BASIC) {
3054  bu_log("nmg_jeg(src_eg=%p, dest_eg=%p)\n",
3055  (void *)src_eg, (void *)dest_eg);
3056  }
3057 
3058  while (BU_LIST_NON_EMPTY(&src_eg->eu_hd2)) {
3059  struct bu_list *midway; /* &eu->l2, midway into edgeuse */
3060 
3061  NMG_CK_EDGE_G_LSEG(src_eg);
3062 
3063  /* Obtain an eu from src_eg */
3064  midway = BU_LIST_FIRST(bu_list, &src_eg->eu_hd2);
3065  NMG_CKMAG(midway, NMG_EDGEUSE2_MAGIC, "edgeuse2 [l2]");
3066  eu = BU_LIST_MAIN_PTR(edgeuse, midway, l2);
3067  NMG_CK_EDGEUSE(eu);
3068 
3069  if (eu->g.lseg_p != src_eg) {
3070  bu_log("nmg_jeg() eu=%p, eu->g=%p != src_eg=%p?? dest_eg=%p\n",
3071  (void *)eu, (void *)eu->g.lseg_p, (void *)src_eg, (void *)dest_eg);
3072  bu_bomb("nmg_jeg() edge geometry fumble\n");
3073  }
3074 
3075  /* Associate eu and mate with dest_eg. src_eg freed when unused. */
3076  if (nmg_use_edge_g(eu, &dest_eg->l.magic))
3077  break; /* src_eg destroyed */
3078  }
3079 }
3080 
3081 
3082 /**
3083  * Kill zero length edgeuse from a shell and
3084  * return the number of edgeuse killed. If the
3085  * shell becomes empty, this function will bomb.
3086  *
3087  */
3088 int
3089 nmg_keu_zl(struct shell *s, const struct bn_tol *tol)
3090 {
3091  int empty_loop = 0;
3092  int empty_face = 0;
3093  int empty_shell = 0;
3094  int eu_killed = 0;
3095  struct loopuse *lu;
3096  struct faceuse *fu;
3097  struct edgeuse *eu;
3098 
3099  NMG_CK_SHELL(s);
3100 
3101  eu_killed = 0;
3102  empty_shell = 0;
3103  fu = BU_LIST_FIRST(faceuse, &s->fu_hd);
3104  while (BU_LIST_NOT_HEAD(fu, &s->fu_hd)) {
3105  NMG_CK_FACEUSE(fu);
3106  if (fu->orientation != OT_SAME) {
3107  fu = BU_LIST_PNEXT(faceuse, fu);
3108  continue;
3109  }
3110  empty_face = 0;
3111  lu = BU_LIST_FIRST(loopuse, &fu->lu_hd);
3112  while (BU_LIST_NOT_HEAD(lu, &fu->lu_hd)) {
3113  NMG_CK_LOOPUSE(lu);
3114  if (BU_LIST_FIRST_MAGIC(&lu->down_hd) != NMG_EDGEUSE_MAGIC) {
3115  bu_bomb("loopuse does not contains edgeuse\n");
3116  }
3117  empty_loop = 0;
3118  eu = BU_LIST_FIRST(edgeuse, &lu->down_hd);
3119  while (BU_LIST_NOT_HEAD(eu, &lu->down_hd)) {
3120  NMG_CK_EDGEUSE(eu);
3121  if ((eu->vu_p->v_p->vg_p == eu->eumate_p->vu_p->v_p->vg_p) ||
3122  bn_pt3_pt3_equal(eu->vu_p->v_p->vg_p->coord,
3123  eu->eumate_p->vu_p->v_p->vg_p->coord, tol)) {
3124  /* fuse the two vertices */
3125  nmg_jv(eu->vu_p->v_p, eu->eumate_p->vu_p->v_p);
3126 
3127  eu_killed++;
3128  if (nmg_keu(eu)) {
3129  empty_loop = 1;
3130  }
3131  eu = BU_LIST_FIRST(edgeuse, &lu->down_hd);
3132  } else {
3133  eu = BU_LIST_PNEXT(edgeuse, eu);
3134  }
3135  }
3136  if (empty_loop) {
3137  if (nmg_klu(lu)) {
3138  empty_face = 1;
3139  }
3140  lu = BU_LIST_FIRST(loopuse, &fu->lu_hd);
3141  } else {
3142  lu = BU_LIST_PNEXT(loopuse, lu);
3143  }
3144  }
3145 
3146  if (empty_face) {
3147  if (nmg_kfu(fu)) {
3148  empty_shell = 1;
3149  }
3150  fu = BU_LIST_FIRST(faceuse, &s->fu_hd);
3151  } else {
3152  fu = BU_LIST_PNEXT(faceuse, fu);
3153  }
3154  }
3155 
3156  if (empty_shell) {
3157  bu_bomb("nmg_keu_zl(): removing zero length edgeuse resulted in an empty shell\n");
3158  }
3159 
3160  return eu_killed;
3161 }
3162 
3163 /*
3164  * Local Variables:
3165  * mode: C
3166  * tab-width: 8
3167  * indent-tabs-mode: t
3168  * c-file-style: "stroustrup"
3169  * End:
3170  * ex: shiftwidth=4 tabstop=8
3171  */
int nmg_keg(struct edgeuse *eu)
Definition: nmg_mk.c:1365
#define NMG_MODEL_MAGIC
Definition: magic.h:133
#define BU_LIST_FOR(p, structure, hp)
Definition: list.h:365
#define NMG_EDGEUSE_MAGIC
Definition: magic.h:120
void nmg_edge_g_cnurb(struct edgeuse *eu, int order, int n_knots, fastf_t *kv, int n_pts, int pt_type, fastf_t *points)
Definition: nmg_mk.c:1899
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
#define BU_LIST_INSERT(old, new)
Definition: list.h:183
struct faceuse * nmg_find_fu_of_eu(const struct edgeuse *eu)
Definition: nmg_info.c:270
void nmg_movevu(struct vertexuse *vu, struct vertex *v)
Definition: nmg_mk.c:2729
Definition: list.h:118
#define NMG_EDGE_MAGIC
Definition: magic.h:123
int nmg_kfu(struct faceuse *fu1)
Definition: nmg_mk.c:1207
#define NMG_SHELL_MAGIC
Definition: magic.h:142
int nmg_demote_eu(struct edgeuse *eu)
Definition: nmg_mk.c:2676
#define NMG_LOOP_G_MAGIC
Definition: magic.h:131
double dist
>= 0
Definition: tol.h:73
#define NMG_VERTEX_MAGIC
Definition: magic.h:147
#define NMG_FACE_G_SNURB_MAGIC
Definition: magic.h:126
void nmg_je(struct edgeuse *eudst, struct edgeuse *eusrc)
Definition: nmg_mk.c:2765
if lu s
Definition: nmg_mod.c:3860
lu
Definition: nmg_mod.c:3855
#define VSET(a, b, c, d)
Definition: color.c:53
int nmg_keu_zl(struct shell *s, const struct bn_tol *tol)
Definition: nmg_mk.c:3089
#define VSETALL(a, s)
Definition: color.c:54
#define NMG_KNOT_VECTOR_MAGIC
Definition: magic.h:129
int nmg_kr(struct nmgregion *r)
Definition: nmg_mk.c:1595
#define BU_LIST_IS_EMPTY(hp)
Definition: list.h:295
void nmg_vertex_gv(struct vertex *v, const fastf_t *pt)
Definition: nmg_mk.c:1668
void nmg_jv(register struct vertex *v1, register struct vertex *v2)
Definition: nmg_mk.c:2917
struct faceuse * nmg_mf(struct loopuse *lu1)
Definition: nmg_mk.c:470
int nmg_demote_lu(struct loopuse *lu1)
Definition: nmg_mk.c:2610
#define SMALL_FASTF
Definition: defines.h:342
void nmg_face_g(struct faceuse *fu, const fastf_t *p)
Definition: nmg_mk.c:2235
struct model * nmg_mmr(void)
Definition: nmg_mk.c:268
void nmg_jfg(struct face *f1, struct face *f2)
Definition: nmg_mk.c:2968
Header file for the BRL-CAD common definitions.
void nmg_vertexuse_nv(struct vertexuse *vu, const fastf_t *norm)
Definition: nmg_mk.c:1719
#define BU_LIST_APPEND(old, new)
Definition: list.h:197
void nmg_unglueedge(struct edgeuse *eu)
Definition: nmg_mk.c:2866
int nmg_shell_is_empty(register const struct shell *s)
Definition: nmg_info.c:203
void nmg_face_g_snurb(struct faceuse *fu, int u_order, int v_order, int n_u_knots, int n_v_knots, fastf_t *ukv, fastf_t *vkv, int n_rows, int n_cols, int pt_type, fastf_t *mesh)
Definition: nmg_mk.c:2347
#define BU_LIST_NON_EMPTY(hp)
Definition: list.h:296
#define MAX_FASTF
Definition: defines.h:340
int nmg_kvu(struct vertexuse *vu)
Definition: nmg_mk.c:1095
#define NMG_LOOPUSE_MAGIC
Definition: magic.h:130
NMG_CK_LOOPUSE(lu)
struct f2 f2
BU_LIST_DEQUEUE & eu1
Definition: nmg_mod.c:3839
void nmg_edge_g(struct edgeuse *eu)
Definition: nmg_mk.c:1789
int nmg_ks(struct shell *s)
Definition: nmg_mk.c:1546
int nmg_use_edge_g(struct edgeuse *eu, uint32_t *magic_p)
Definition: nmg_mk.c:2087
Definition: color.c:49
#define NMG_EDGEUSE2_MAGIC
Definition: magic.h:119
#define NMG_LOOP_MAGIC
Definition: magic.h:132
uint32_t NMG_debug
debug bits for NMG's see nmg.h
Definition: raytrace.h:1699
#define NMG_FACE_MAGIC
Definition: magic.h:127
void * bu_calloc(size_t nelem, size_t elsize, const char *str)
Definition: malloc.c:321
struct shell * nmg_find_s_of_lu(const struct loopuse *lu)
Definition: nmg_info.c:220
void nmg_vertex_g(register struct vertex *v, fastf_t x, fastf_t y, fastf_t z)
Definition: nmg_mk.c:1699
#define V3ARGS(a)
Definition: color.c:56
#define NEAR_ZERO(val, epsilon)
Definition: color.c:55
struct loopuse * nmg_mlv(uint32_t *magic, struct vertex *v, int orientation)
Definition: nmg_mk.c:571
void nmg_km(struct model *m)
Definition: nmg_mk.c:1634
struct f1 f1
struct loopuse * nmg_ml(struct shell *s)
Definition: nmg_mk.c:927
void nmg_face_new_g(struct faceuse *fu, const fastf_t *pl)
Definition: nmg_mk.c:2281
#define NMG_SHELL_A_MAGIC
Definition: magic.h:141
void nmg_face_bb(struct face *f, const struct bn_tol *tol)
Definition: nmg_mk.c:2423
struct edgeuse * nmg_me(struct vertex *v1, struct vertex *v2, struct shell *s)
Definition: nmg_mk.c:698
#define BU_LIST_PNEXT(structure, p)
Definition: list.h:422
oldeumate l2 magic
Definition: nmg_mod.c:3843
#define NMG_REGION_MAGIC
Definition: magic.h:137
Support for uniform tolerances.
Definition: tol.h:71
#define BN_CK_TOL(_p)
Definition: tol.h:82
struct shell * nmg_msv(struct nmgregion *r)
Definition: nmg_mk.c:423
#define BU_LIST_FIRST_MAGIC(hp)
Definition: list.h:416
#define NMG_VERTEXUSE_MAGIC
Definition: magic.h:145
struct edgeuse * nmg_meonvu(struct vertexuse *vu)
Definition: nmg_mk.c:800
#define NMG_VERTEXUSE_A_CNURB_MAGIC
Definition: magic.h:143
struct nmgregion * nmg_mrsv(struct model *m)
Definition: nmg_mk.c:306
#define BU_LIST_MAIN_PTR(_type, _ptr2, _name2)
Definition: list.h:470
struct fg_node fg
Definition: chull3d.cpp:80
#define NMG_FACE_G_PLANE_MAGIC
Definition: magic.h:125
int nmg_is_vertex_a_selfloop_in_shell(const struct vertex *v, const struct shell *s)
Definition: nmg_info.c:1820
void nmg_edge_g_cnurb_plinear(struct edgeuse *eu)
Definition: nmg_mk.c:2019
struct model * nmg_mm(void)
Definition: nmg_mk.c:235
void nmg_pr_s(const struct shell *s, char *h)
Definition: nmg_pr.c:230
#define NMG_EDGE_G_LSEG_MAGIC
Definition: magic.h:122
#define BU_LIST_INIT(_hp)
Definition: list.h:148
void nmg_jeg(struct edge_g_lseg *dest_eg, struct edge_g_lseg *src_eg)
Definition: nmg_mk.c:3047
int nmg_klu(struct loopuse *lu1)
Definition: nmg_mk.c:1277
#define NMG_EDGE_G_CNURB_MAGIC
Definition: magic.h:121
eu1 up magic_p
Definition: nmg_mod.c:3915
#define NMG_VERTEXUSE_A_PLANE_MAGIC
Definition: magic.h:144
Definition: color.c:51
#define NMG_REGION_A_MAGIC
Definition: magic.h:136
int nmg_keu(register struct edgeuse *eu1)
Definition: nmg_mk.c:1413
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
#define NMG_VERTEX_G_MAGIC
Definition: magic.h:146
NMG_CK_SHELL(s)
void nmg_vertexuse_a_cnurb(struct vertexuse *vu, const fastf_t *uvw)
Definition: nmg_mk.c:1757
int bn_pt3_pt3_equal(const point_t a, const point_t b, const struct bn_tol *tol)
#define BU_LIST_DEQUEUE(cur)
Definition: list.h:209
void nmg_shell_a(struct shell *s, const struct bn_tol *tol)
Definition: nmg_mk.c:2474
#define BU_LIST_HEAD_MAGIC
Definition: magic.h:56
#define NMG_FACEUSE_MAGIC
Definition: magic.h:124
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
double fastf_t
Definition: defines.h:300
#define VPRINT(a, b)
Definition: raytrace.h:1881
const char * bu_identify_magic(uint32_t magic)
eu2
Definition: nmg_mod.c:3875
char * nmg_orientation(int orientation)
Definition: nmg_pr.c:50
#define BU_LIST_NEXT(structure, hp)
Definition: list.h:316
void rt_nurb_kvknot(register struct knot_vector *new_knots, int order, fastf_t lower, fastf_t upper, int num, struct resource *res)
Definition: nurb_knot.c:47
#define BU_LIST_NOT_HEAD(p, hp)
Definition: list.h:324
void nmg_loop_g(struct loop *l, const struct bn_tol *tol)
Definition: nmg_mk.c:2152
Definition: color.c:50
#define BU_LIST_FIRST(structure, hp)
Definition: list.h:312
eu1 orientation
Definition: nmg_mod.c:3916
int rt_nurb_s_bound(struct face_g_snurb *srf, fastf_t *bmin, fastf_t *bmax)
Definition: nurb_bound.c:48
struct rt_g RTG
Definition: globals.c:39
struct model * nmg_find_model(const uint32_t *magic_p_arg)
Definition: nmg_info.c:57
void nmg_region_a(struct nmgregion *r, const struct bn_tol *tol)
Definition: nmg_mk.c:2557