BRL-CAD
metaball_tri.c
Go to the documentation of this file.
1 /* M E T A B A L L _ T R I . C
2  * BRL-CAD
3  *
4  * Copyright (c) 1985-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 /** @addtogroup primitives */
21 /** @{ */
22 /** @file primitives/metaball/metaball_tri.c
23  *
24  * Tessellation/facetization routines for the metaball primitive.
25  *
26  * Here be magic.
27  *
28  *
29  * 4
30  * 4-----------5
31  * 8/| 9/|
32  * / | 0 / |
33  * 0-----------1 |5
34  * | |7 | |
35  * | | 6 1| |
36  * 3| 7--------|--6
37  * | / | /
38  * |/11 |/10
39  * 3-----------2
40  * 2
41  */
42 /** @} */
43 
44 #include "common.h"
45 
46 #include <stddef.h>
47 #include <string.h>
48 #include <math.h>
49 #include "bio.h"
50 
51 #include "vmath.h"
52 #include "db.h"
53 #include "nmg.h"
54 #include "rtgeom.h"
55 #include "raytrace.h"
56 #include "nurb.h"
57 #include "wdb.h"
58 
59 #include "metaball.h"
60 
61 /**
62  * Tessellate a metaball.
63  */
64 int
65 rt_metaball_tess(struct nmgregion **r, struct model *m, struct rt_db_internal *ip, const struct rt_tess_tol *ttol, const struct bn_tol *tol)
66 {
67  struct rt_metaball_internal *mb;
68  fastf_t mtol, radius;
69  point_t center, min, max;
70  fastf_t i, j, k, finalstep = +INFINITY;
71  struct bu_vls times = BU_VLS_INIT_ZERO;
72  struct wdb_metaballpt *mbpt;
73  struct shell *s;
74  int numtri = 0;
75 
76  if (r == NULL || m == NULL)
77  return -1;
78  *r = NULL;
79 
80  NMG_CK_MODEL(m);
81 
83  mb = (struct rt_metaball_internal *)ip->idb_ptr;
84  RT_METABALL_CK_MAGIC(mb);
85 
86  rt_prep_timer();
87 
88  /* since this geometry isn't necessarily prepped, we have to figure out the
89  * finalstep and bounding box manually. */
90  for (BU_LIST_FOR(mbpt, wdb_metaballpt, &mb->metaball_ctrl_head))
91  V_MIN(finalstep, mbpt->fldstr);
92  finalstep /= (fastf_t)1e5;
93 
94  radius = rt_metaball_get_bounding_sphere(&center, mb->threshold, mb);
95  if (radius < 0) { /* no control points */
96  bu_log("Attempting to tessellate metaball with no control points");
97  return -1;
98  }
99  rt_metaball_bbox(ip, &min, &max, tol);
100 
101  /* TODO: get better sampling tolerance, unless this is "good enough" */
102  mtol = ttol->abs;
103  V_MAX(mtol, ttol->rel * radius * 10);
104  V_MAX(mtol, tol->dist);
105 
106  *r = nmg_mrsv(m); /* new empty nmg */
107  s = BU_LIST_FIRST(shell, &(*r)->s_hd);
108 
109  /* the incredibly na´ve approach. Time could be cut in half by simply
110  * caching 4 point values, more by actually marching or doing active
111  * refinement. This is the simplest pattern for now.
112  */
113  for (i = min[X]; i < max[X]; i += mtol)
114  for (j = min[Y]; j < max[Y]; j += mtol)
115  for (k = min[Z]; k < max[Z]; k += mtol) {
116  point_t p[8];
117  int pv = 0;
118 
119  /* generate the vertex values */
120 #define MEH(c,di,dj,dk) VSET(p[c], i+di, j+dj, k+dk); pv |= rt_metaball_point_inside((const point_t *)&p[c], mb) << c;
121  MEH(0, 0, 0, mtol);
122  MEH(1, mtol, 0, mtol);
123  MEH(2, mtol, 0, 0);
124  MEH(3, 0, 0, 0);
125  MEH(4, 0, mtol, mtol);
126  MEH(5, mtol, mtol, mtol);
127  MEH(6, mtol, mtol, 0);
128  MEH(7, 0, mtol, 0);
129 #undef MEH
130 
131  if ( pv != 0 && pv != 255 ) { /* entire cube is either inside or outside */
132  point_t edges[12];
133  int rval;
134 
135  /* compute the edge values (if needed) */
136 #define MEH(a,b,c) if (!(pv&(1<<b)&&pv&(1<<c))) { \
137  rt_metaball_find_intersection(edges+a, mb, (const point_t *)(p+b), (const point_t *)(p+c), mtol, finalstep); \
138 }
139 
140  /* magic numbers! an edge, then the two attached vertices.
141  * For edge/vertex mapping, refer to the awesome ascii art
142  * at the beginning of this file. */
143  MEH(0 ,0,1);
144  MEH(1 ,1,2);
145  MEH(2 ,2,3);
146  MEH(3 ,0,3);
147  MEH(4 ,4,5);
148  MEH(5 ,5,6);
149  MEH(6 ,6,7);
150  MEH(7 ,4,7);
151  MEH(8 ,0,4);
152  MEH(9 ,1,5);
153  MEH(10,2,6);
154  MEH(11,3,7);
155 #undef MEH
156 
157  rval = nmg_mc_realize_cube(s, pv, (point_t *)edges, tol);
158  numtri += rval;
159  if (rval < 0) {
160  bu_log("Error attempting to realize a cube O.o\n");
161  return rval;
162  }
163  }
164  }
165 
166  nmg_mark_edges_real(&s->l.magic);
167  nmg_region_a(*r, tol);
168 
169  nmg_model_fuse(m, tol);
170 
171  rt_get_timer(&times, NULL);
172  bu_log("metaball tessellate (%d triangles): %s\n", numtri, bu_vls_addr(&times));
173 
174  return 0;
175 }
176 
177 /*
178  * Local Variables:
179  * mode: C
180  * tab-width: 8
181  * indent-tabs-mode: t
182  * c-file-style: "stroustrup"
183  * End:
184  * ex: shiftwidth=4 tabstop=8
185  */
#define BU_LIST_FOR(p, structure, hp)
Definition: list.h:365
int nmg_model_fuse(struct model *m, const struct bn_tol *tol)
Definition: nmg_fuse.c:1919
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
#define MEH(c, di, dj, dk)
double dist
>= 0
Definition: tol.h:73
if lu s
Definition: nmg_mod.c:3860
Header file for the BRL-CAD common definitions.
int nmg_mc_realize_cube(struct shell *s, int pv, point_t *edges, const struct bn_tol *tol)
Definition: nmg_tri_mc.c:396
double rel
rel dist tol
Definition: raytrace.h:181
double rt_get_timer(struct bu_vls *vp, double *elapsed)
Definition: timer-nt.c:44
Definition: color.c:49
#define RT_CK_DB_INTERNAL(_p)
Definition: raytrace.h:207
int nmg_mark_edges_real(const uint32_t *magic_p)
Definition: nmg_misc.c:846
Support for uniform tolerances.
Definition: tol.h:71
char * bu_vls_addr(const struct bu_vls *vp)
Definition: vls.c:111
struct nmgregion * nmg_mrsv(struct model *m)
Definition: nmg_mk.c:306
fastf_t rt_metaball_get_bounding_sphere(point_t *center, fastf_t threshold, struct rt_metaball_internal *mb)
Definition: metaball.c:100
void * idb_ptr
Definition: raytrace.h:195
int rt_metaball_bbox(struct rt_db_internal *ip, point_t *min, point_t *max, const struct bn_tol *tol)
Definition: metaball.c:165
double abs
absolute dist tol
Definition: raytrace.h:180
Definition: color.c:51
int rt_metaball_tess(struct nmgregion **r, struct model *m, struct rt_db_internal *ip, const struct rt_tess_tol *ttol, const struct bn_tol *tol)
Definition: metaball_tri.c:65
#define BU_VLS_INIT_ZERO
Definition: vls.h:84
Definition: vls.h:56
double fastf_t
Definition: defines.h:300
void rt_prep_timer(void)
Definition: timer-nt.c:36
Definition: color.c:50
#define BU_LIST_FIRST(structure, hp)
Definition: list.h:312
void nmg_region_a(struct nmgregion *r, const struct bn_tol *tol)
Definition: nmg_mk.c:2557