BRL-CAD
nmg_tri_mc.c
Go to the documentation of this file.
1 /* N M G _ T R I _ M C . 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_tri_mc.c
23  *
24  * Triangulate the faces of a polygonal NMG using the marching cubes
25  * algorithm.
26  *
27  *
28  * Vertex and edge indices (note that it seems rotated 90 degrees from the stuff
29  * you see on the sources. They used OpenGL coordinates, we use BRL-CAD.)
30  * 4
31  * 4-----------5
32  * 8/| 9/|
33  * / | 0 / |
34  * 0-----------1 |5
35  * | |7 | |
36  * | | 6 1| |
37  * 3| 7--------|--6
38  * | / | /
39  * |/11 |/10
40  * 3-----------2
41  * 2
42  */
43 /** @} */
44 
45 /* rough game plan
46  * [ ] develop/proof metaball primitive tessellation using MC (end of Jan10)
47  * [ ] asc-g/g-asc of metaballs for regression/comparison testing
48  * [X] asc-g
49  * [X] g-asc
50  * [ ] regression shtuff (on hold; regress/ has issues)
51  * [X] edge solve cubes
52  * [X] write compiled table shtuff (use existing table, the hex/index one?)
53  * [X] produce NMG mesh
54  * ============================================================
55  * [ ] experiment with decimating
56  * [X] hoist code where final cube edge intersections is known
57  * [ ] implement ray-firing to find edge intersects
58  * [X] hoise table stuff
59  * [X] hoist NMG mesh writer. (End of Feb10)
60  * ============================================================
61  * [ ] try decimation?
62  * [ ] ???
63  * [ ] profit! (Mid Apr10)
64  * [ ] explore optimizations if time left?
65  * [ ] compare old nmg tesselator for accuracy/performance/robustness?
66  */
67 
68 #include "common.h"
69 
70 #include <string.h>
71 #include <stdlib.h>
72 #include <math.h>
73 #include "bio.h"
74 
75 #include "bu/parallel.h"
76 #include "vmath.h"
77 #include "nmg.h"
78 #include "raytrace.h"
79 #include "plot3.h"
80 
81 #define MAX_INTERSECTS 1024
82 
83 #define VOODOO 10010.001
84 
85 /* set this to 1 for full midpoint use. Set it to 2 for x/y mid and real z. */
87 
88 /*
89  * Table data acquired from Paul Borke's page at
90  * http://local.wasp.uwa.edu.au/~pbourke/geometry/polygonise/
91  *
92  * Asserts it's from Cory Gene Bloyde, who has provided "public domain" code
93  * including the tables. http://www.siafoo.net/snippet/100
94  *
95  * Grid definition matches SIGGRAPH 1987 p 164 (original presentation of technique)
96  */
97 
98 HIDDEN int mc_tris[256][16] = {
99  /* 00 */ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
100  /* 01 */ {0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
101  /* 02 */ {0, 1, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
102  /* 03 */ {1, 8, 3, 9, 8, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
103  /* 04 */ {1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
104  /* 05 */ {0, 8, 3, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
105  /* 06 */ {9, 2, 10, 0, 2, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
106  /* 07 */ {2, 8, 3, 2, 10, 8, 10, 9, 8, -1, -1, -1, -1, -1, -1, -1},
107  /* 08 */ {3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
108  /* 09 */ {0, 11, 2, 8, 11, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
109  /* 0a */ {1, 9, 0, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
110  /* 0b */ {1, 11, 2, 1, 9, 11, 9, 8, 11, -1, -1, -1, -1, -1, -1, -1},
111  /* 0c */ {3, 10, 1, 11, 10, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
112  /* 0d */ {0, 10, 1, 0, 8, 10, 8, 11, 10, -1, -1, -1, -1, -1, -1, -1},
113  /* 0e */ {3, 9, 0, 3, 11, 9, 11, 10, 9, -1, -1, -1, -1, -1, -1, -1},
114  /* 0f */ {9, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
115  /* 10 */ {4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
116  /* 11 */ {4, 3, 0, 7, 3, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
117  /* 12 */ {0, 1, 9, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
118  /* 13 */ {4, 1, 9, 4, 7, 1, 7, 3, 1, -1, -1, -1, -1, -1, -1, -1},
119  /* 14 */ {1, 2, 10, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
120  /* 15 */ {3, 4, 7, 3, 0, 4, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1},
121  /* 16 */ {9, 2, 10, 9, 0, 2, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1},
122  /* 17 */ {2, 10, 9, 2, 9, 7, 2, 7, 3, 7, 9, 4, -1, -1, -1, -1},
123  /* 18 */ {8, 4, 7, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
124  /* 19 */ {11, 4, 7, 11, 2, 4, 2, 0, 4, -1, -1, -1, -1, -1, -1, -1},
125  /* 1a */ {9, 0, 1, 8, 4, 7, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1},
126  /* 1b */ {4, 7, 11, 9, 4, 11, 9, 11, 2, 9, 2, 1, -1, -1, -1, -1},
127  /* 1c */ {3, 10, 1, 3, 11, 10, 7, 8, 4, -1, -1, -1, -1, -1, -1, -1},
128  /* 1d */ {1, 11, 10, 1, 4, 11, 1, 0, 4, 7, 11, 4, -1, -1, -1, -1},
129  /* 1e */ {4, 7, 8, 9, 0, 11, 9, 11, 10, 11, 0, 3, -1, -1, -1, -1},
130  /* 1f */ {4, 7, 11, 4, 11, 9, 9, 11, 10, -1, -1, -1, -1, -1, -1, -1},
131  /* 20 */ {9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
132  /* 21 */ {9, 5, 4, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
133  /* 22 */ {0, 5, 4, 1, 5, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
134  /* 23 */ {8, 5, 4, 8, 3, 5, 3, 1, 5, -1, -1, -1, -1, -1, -1, -1},
135  /* 24 */ {1, 2, 10, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
136  /* 25 */ {3, 0, 8, 1, 2, 10, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1},
137  /* 26 */ {5, 2, 10, 5, 4, 2, 4, 0, 2, -1, -1, -1, -1, -1, -1, -1},
138  /* 27 */ {2, 10, 5, 3, 2, 5, 3, 5, 4, 3, 4, 8, -1, -1, -1, -1},
139  /* 28 */ {9, 5, 4, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
140  /* 29 */ {0, 11, 2, 0, 8, 11, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1},
141  /* 2a */ {0, 5, 4, 0, 1, 5, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1},
142  /* 2b */ {2, 1, 5, 2, 5, 8, 2, 8, 11, 4, 8, 5, -1, -1, -1, -1},
143  /* 2c */ {10, 3, 11, 10, 1, 3, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1},
144  /* 2d */ {4, 9, 5, 0, 8, 1, 8, 10, 1, 8, 11, 10, -1, -1, -1, -1},
145  /* 2e */ {5, 4, 0, 5, 0, 11, 5, 11, 10, 11, 0, 3, -1, -1, -1, -1},
146  /* 2f */ {5, 4, 8, 5, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1},
147  /* 30 */ {9, 7, 8, 5, 7, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
148  /* 31 */ {9, 3, 0, 9, 5, 3, 5, 7, 3, -1, -1, -1, -1, -1, -1, -1},
149  /* 32 */ {0, 7, 8, 0, 1, 7, 1, 5, 7, -1, -1, -1, -1, -1, -1, -1},
150  /* 33 */ {1, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
151  /* 34 */ {9, 7, 8, 9, 5, 7, 10, 1, 2, -1, -1, -1, -1, -1, -1, -1},
152  /* 35 */ {10, 1, 2, 9, 5, 0, 5, 3, 0, 5, 7, 3, -1, -1, -1, -1},
153  /* 36 */ {8, 0, 2, 8, 2, 5, 8, 5, 7, 10, 5, 2, -1, -1, -1, -1},
154  /* 37 */ {2, 10, 5, 2, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1},
155  /* 38 */ {7, 9, 5, 7, 8, 9, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1},
156  /* 39 */ {9, 5, 7, 9, 7, 2, 9, 2, 0, 2, 7, 11, -1, -1, -1, -1},
157  /* 3a */ {2, 3, 11, 0, 1, 8, 1, 7, 8, 1, 5, 7, -1, -1, -1, -1},
158  /* 3b */ {11, 2, 1, 11, 1, 7, 7, 1, 5, -1, -1, -1, -1, -1, -1, -1},
159  /* 3c */ {9, 5, 8, 8, 5, 7, 10, 1, 3, 10, 3, 11, -1, -1, -1, -1},
160  /* 3d */ {5, 7, 0, 5, 0, 9, 7, 11, 0, 1, 0, 10, 11, 10, 0, -1},
161  /* 3e */ {11, 10, 0, 11, 0, 3, 10, 5, 0, 8, 0, 7, 5, 7, 0, -1},
162  /* 3f */ {11, 10, 5, 7, 11, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
163  /* 40 */ {10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
164  /* 41 */ {0, 8, 3, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
165  /* 42 */ {9, 0, 1, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
166  /* 43 */ {1, 8, 3, 1, 9, 8, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1},
167  /* 44 */ {1, 6, 5, 2, 6, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
168  /* 45 */ {1, 6, 5, 1, 2, 6, 3, 0, 8, -1, -1, -1, -1, -1, -1, -1},
169  /* 46 */ {9, 6, 5, 9, 0, 6, 0, 2, 6, -1, -1, -1, -1, -1, -1, -1},
170  /* 47 */ {5, 9, 8, 5, 8, 2, 5, 2, 6, 3, 2, 8, -1, -1, -1, -1},
171  /* 48 */ {2, 3, 11, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
172  /* 49 */ {11, 0, 8, 11, 2, 0, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1},
173  /* 4a */ {0, 1, 9, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1},
174  /* 4b */ {5, 10, 6, 1, 9, 2, 9, 11, 2, 9, 8, 11, -1, -1, -1, -1},
175  /* 4c */ {6, 3, 11, 6, 5, 3, 5, 1, 3, -1, -1, -1, -1, -1, -1, -1},
176  /* 4d */ {0, 8, 11, 0, 11, 5, 0, 5, 1, 5, 11, 6, -1, -1, -1, -1},
177  /* 4e */ {3, 11, 6, 0, 3, 6, 0, 6, 5, 0, 5, 9, -1, -1, -1, -1},
178  /* 4f */ {6, 5, 9, 6, 9, 11, 11, 9, 8, -1, -1, -1, -1, -1, -1, -1},
179  /* 50 */ {5, 10, 6, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
180  /* 51 */ {4, 3, 0, 4, 7, 3, 6, 5, 10, -1, -1, -1, -1, -1, -1, -1},
181  /* 52 */ {1, 9, 0, 5, 10, 6, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1},
182  /* 53 */ {10, 6, 5, 1, 9, 7, 1, 7, 3, 7, 9, 4, -1, -1, -1, -1},
183  /* 54 */ {6, 1, 2, 6, 5, 1, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1},
184  /* 55 */ {1, 2, 5, 5, 2, 6, 3, 0, 4, 3, 4, 7, -1, -1, -1, -1},
185  /* 56 */ {8, 4, 7, 9, 0, 5, 0, 6, 5, 0, 2, 6, -1, -1, -1, -1},
186  /* 57 */ {7, 3, 9, 7, 9, 4, 3, 2, 9, 5, 9, 6, 2, 6, 9, -1},
187  /* 58 */ {3, 11, 2, 7, 8, 4, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1},
188  /* 59 */ {5, 10, 6, 4, 7, 2, 4, 2, 0, 2, 7, 11, -1, -1, -1, -1},
189  /* 5a */ {0, 1, 9, 4, 7, 8, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1},
190  /* 5b */ {9, 2, 1, 9, 11, 2, 9, 4, 11, 7, 11, 4, 5, 10, 6, -1},
191  /* 5c */ {8, 4, 7, 3, 11, 5, 3, 5, 1, 5, 11, 6, -1, -1, -1, -1},
192  /* 5d */ {5, 1, 11, 5, 11, 6, 1, 0, 11, 7, 11, 4, 0, 4, 11, -1},
193  /* 5e */ {0, 5, 9, 0, 6, 5, 0, 3, 6, 11, 6, 3, 8, 4, 7, -1},
194  /* 5f */ {6, 5, 9, 6, 9, 11, 4, 7, 9, 7, 11, 9, -1, -1, -1, -1},
195  /* 60 */ {10, 4, 9, 6, 4, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
196  /* 61 */ {4, 10, 6, 4, 9, 10, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1},
197  /* 62 */ {10, 0, 1, 10, 6, 0, 6, 4, 0, -1, -1, -1, -1, -1, -1, -1},
198  /* 63 */ {8, 3, 1, 8, 1, 6, 8, 6, 4, 6, 1, 10, -1, -1, -1, -1},
199  /* 64 */ {1, 4, 9, 1, 2, 4, 2, 6, 4, -1, -1, -1, -1, -1, -1, -1},
200  /* 65 */ {3, 0, 8, 1, 2, 9, 2, 4, 9, 2, 6, 4, -1, -1, -1, -1},
201  /* 66 */ {0, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
202  /* 67 */ {8, 3, 2, 8, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1},
203  /* 68 */ {10, 4, 9, 10, 6, 4, 11, 2, 3, -1, -1, -1, -1, -1, -1, -1},
204  /* 69 */ {0, 8, 2, 2, 8, 11, 4, 9, 10, 4, 10, 6, -1, -1, -1, -1},
205  /* 6a */ {3, 11, 2, 0, 1, 6, 0, 6, 4, 6, 1, 10, -1, -1, -1, -1},
206  /* 6b */ {6, 4, 1, 6, 1, 10, 4, 8, 1, 2, 1, 11, 8, 11, 1, -1},
207  /* 6c */ {9, 6, 4, 9, 3, 6, 9, 1, 3, 11, 6, 3, -1, -1, -1, -1},
208  /* 6d */ {8, 11, 1, 8, 1, 0, 11, 6, 1, 9, 1, 4, 6, 4, 1, -1},
209  /* 6e */ {3, 11, 6, 3, 6, 0, 0, 6, 4, -1, -1, -1, -1, -1, -1, -1},
210  /* 6f */ {6, 4, 8, 11, 6, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
211  /* 70 */ {7, 10, 6, 7, 8, 10, 8, 9, 10, -1, -1, -1, -1, -1, -1, -1},
212  /* 71 */ {0, 7, 3, 0, 10, 7, 0, 9, 10, 6, 7, 10, -1, -1, -1, -1},
213  /* 72 */ {10, 6, 7, 1, 10, 7, 1, 7, 8, 1, 8, 0, -1, -1, -1, -1},
214  /* 73 */ {10, 6, 7, 10, 7, 1, 1, 7, 3, -1, -1, -1, -1, -1, -1, -1},
215  /* 74 */ {1, 2, 6, 1, 6, 8, 1, 8, 9, 8, 6, 7, -1, -1, -1, -1},
216  /* 75 */ {2, 6, 9, 2, 9, 1, 6, 7, 9, 0, 9, 3, 7, 3, 9, -1},
217  /* 76 */ {7, 8, 0, 7, 0, 6, 6, 0, 2, -1, -1, -1, -1, -1, -1, -1},
218  /* 77 */ {7, 3, 2, 6, 7, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
219  /* 78 */ {2, 3, 11, 10, 6, 8, 10, 8, 9, 8, 6, 7, -1, -1, -1, -1},
220  /* 79 */ {2, 0, 7, 2, 7, 11, 0, 9, 7, 6, 7, 10, 9, 10, 7, -1},
221  /* 7a */ {1, 8, 0, 1, 7, 8, 1, 10, 7, 6, 7, 10, 2, 3, 11, -1},
222  /* 7b */ {11, 2, 1, 11, 1, 7, 10, 6, 1, 6, 7, 1, -1, -1, -1, -1},
223  /* 7c */ {8, 9, 6, 8, 6, 7, 9, 1, 6, 11, 6, 3, 1, 3, 6, -1},
224  /* 7d */ {0, 9, 1, 11, 6, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
225  /* 7e */ {7, 8, 0, 7, 0, 6, 3, 11, 0, 11, 6, 0, -1, -1, -1, -1},
226  /* 7f */ {7, 11, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
227  /* 80 */ {7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
228  /* 81 */ {3, 0, 8, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
229  /* 82 */ {0, 1, 9, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
230  /* 83 */ {8, 1, 9, 8, 3, 1, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1},
231  /* 84 */ {10, 1, 2, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
232  /* 85 */ {1, 2, 10, 3, 0, 8, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1},
233  /* 86 */ {2, 9, 0, 2, 10, 9, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1},
234  /* 87 */ {6, 11, 7, 2, 10, 3, 10, 8, 3, 10, 9, 8, -1, -1, -1, -1},
235  /* 88 */ {7, 2, 3, 6, 2, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
236  /* 89 */ {7, 0, 8, 7, 6, 0, 6, 2, 0, -1, -1, -1, -1, -1, -1, -1},
237  /* 8a */ {2, 7, 6, 2, 3, 7, 0, 1, 9, -1, -1, -1, -1, -1, -1, -1},
238  /* 8b */ {1, 6, 2, 1, 8, 6, 1, 9, 8, 8, 7, 6, -1, -1, -1, -1},
239  /* 8c */ {10, 7, 6, 10, 1, 7, 1, 3, 7, -1, -1, -1, -1, -1, -1, -1},
240  /* 8d */ {10, 7, 6, 1, 7, 10, 1, 8, 7, 1, 0, 8, -1, -1, -1, -1},
241  /* 8e */ {0, 3, 7, 0, 7, 10, 0, 10, 9, 6, 10, 7, -1, -1, -1, -1},
242  /* 8f */ {7, 6, 10, 7, 10, 8, 8, 10, 9, -1, -1, -1, -1, -1, -1, -1},
243  /* 90 */ {6, 8, 4, 11, 8, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
244  /* 91 */ {3, 6, 11, 3, 0, 6, 0, 4, 6, -1, -1, -1, -1, -1, -1, -1},
245  /* 92 */ {8, 6, 11, 8, 4, 6, 9, 0, 1, -1, -1, -1, -1, -1, -1, -1},
246  /* 93 */ {9, 4, 6, 9, 6, 3, 9, 3, 1, 11, 3, 6, -1, -1, -1, -1},
247  /* 94 */ {6, 8, 4, 6, 11, 8, 2, 10, 1, -1, -1, -1, -1, -1, -1, -1},
248  /* 95 */ {1, 2, 10, 3, 0, 11, 0, 6, 11, 0, 4, 6, -1, -1, -1, -1},
249  /* 96 */ {4, 11, 8, 4, 6, 11, 0, 2, 9, 2, 10, 9, -1, -1, -1, -1},
250  /* 97 */ {10, 9, 3, 10, 3, 2, 9, 4, 3, 11, 3, 6, 4, 6, 3, -1},
251  /* 98 */ {8, 2, 3, 8, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1},
252  /* 99 */ {0, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
253  /* 9a */ {1, 9, 0, 2, 3, 4, 2, 4, 6, 4, 3, 8, -1, -1, -1, -1},
254  /* 9b */ {1, 9, 4, 1, 4, 2, 2, 4, 6, -1, -1, -1, -1, -1, -1, -1},
255  /* 9c */ {8, 1, 3, 8, 6, 1, 8, 4, 6, 6, 10, 1, -1, -1, -1, -1},
256  /* 9d */ {10, 1, 0, 10, 0, 6, 6, 0, 4, -1, -1, -1, -1, -1, -1, -1},
257  /* 9e */ {4, 6, 3, 4, 3, 8, 6, 10, 3, 0, 3, 9, 10, 9, 3, -1},
258  /* 9f */ {10, 9, 4, 6, 10, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
259  /* a0 */ {4, 9, 5, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
260  /* a1 */ {0, 8, 3, 4, 9, 5, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1},
261  /* a2 */ {5, 0, 1, 5, 4, 0, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1},
262  /* a3 */ {11, 7, 6, 8, 3, 4, 3, 5, 4, 3, 1, 5, -1, -1, -1, -1},
263  /* a4 */ {9, 5, 4, 10, 1, 2, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1},
264  /* a5 */ {6, 11, 7, 1, 2, 10, 0, 8, 3, 4, 9, 5, -1, -1, -1, -1},
265  /* a6 */ {7, 6, 11, 5, 4, 10, 4, 2, 10, 4, 0, 2, -1, -1, -1, -1},
266  /* a7 */ {3, 4, 8, 3, 5, 4, 3, 2, 5, 10, 5, 2, 11, 7, 6, -1},
267  /* a8 */ {7, 2, 3, 7, 6, 2, 5, 4, 9, -1, -1, -1, -1, -1, -1, -1},
268  /* a9 */ {9, 5, 4, 0, 8, 6, 0, 6, 2, 6, 8, 7, -1, -1, -1, -1},
269  /* aa */ {3, 6, 2, 3, 7, 6, 1, 5, 0, 5, 4, 0, -1, -1, -1, -1},
270  /* ab */ {6, 2, 8, 6, 8, 7, 2, 1, 8, 4, 8, 5, 1, 5, 8, -1},
271  /* ac */ {9, 5, 4, 10, 1, 6, 1, 7, 6, 1, 3, 7, -1, -1, -1, -1},
272  /* ad */ {1, 6, 10, 1, 7, 6, 1, 0, 7, 8, 7, 0, 9, 5, 4, -1},
273  /* ae */ {4, 0, 10, 4, 10, 5, 0, 3, 10, 6, 10, 7, 3, 7, 10, -1},
274  /* af */ {7, 6, 10, 7, 10, 8, 5, 4, 10, 4, 8, 10, -1, -1, -1, -1},
275  /* b0 */ {6, 9, 5, 6, 11, 9, 11, 8, 9, -1, -1, -1, -1, -1, -1, -1},
276  /* b1 */ {3, 6, 11, 0, 6, 3, 0, 5, 6, 0, 9, 5, -1, -1, -1, -1},
277  /* b2 */ {0, 11, 8, 0, 5, 11, 0, 1, 5, 5, 6, 11, -1, -1, -1, -1},
278  /* b3 */ {6, 11, 3, 6, 3, 5, 5, 3, 1, -1, -1, -1, -1, -1, -1, -1},
279  /* b4 */ {1, 2, 10, 9, 5, 11, 9, 11, 8, 11, 5, 6, -1, -1, -1, -1},
280  /* b5 */ {0, 11, 3, 0, 6, 11, 0, 9, 6, 5, 6, 9, 1, 2, 10, -1},
281  /* b6 */ {11, 8, 5, 11, 5, 6, 8, 0, 5, 10, 5, 2, 0, 2, 5, -1},
282  /* b7 */ {6, 11, 3, 6, 3, 5, 2, 10, 3, 10, 5, 3, -1, -1, -1, -1},
283  /* b8 */ {5, 8, 9, 5, 2, 8, 5, 6, 2, 3, 8, 2, -1, -1, -1, -1},
284  /* b9 */ {9, 5, 6, 9, 6, 0, 0, 6, 2, -1, -1, -1, -1, -1, -1, -1},
285  /* ba */ {1, 5, 8, 1, 8, 0, 5, 6, 8, 3, 8, 2, 6, 2, 8, -1},
286  /* bb */ {1, 5, 6, 2, 1, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
287  /* bc */ {1, 3, 6, 1, 6, 10, 3, 8, 6, 5, 6, 9, 8, 9, 6, -1},
288  /* bd */ {10, 1, 0, 10, 0, 6, 9, 5, 0, 5, 6, 0, -1, -1, -1, -1},
289  /* be */ {0, 3, 8, 5, 6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
290  /* bf */ {10, 5, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
291  /* c0 */ {11, 5, 10, 7, 5, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
292  /* c1 */ {11, 5, 10, 11, 7, 5, 8, 3, 0, -1, -1, -1, -1, -1, -1, -1},
293  /* c2 */ {5, 11, 7, 5, 10, 11, 1, 9, 0, -1, -1, -1, -1, -1, -1, -1},
294  /* c3 */ {10, 7, 5, 10, 11, 7, 9, 8, 1, 8, 3, 1, -1, -1, -1, -1},
295  /* c4 */ {11, 1, 2, 11, 7, 1, 7, 5, 1, -1, -1, -1, -1, -1, -1, -1},
296  /* c5 */ {0, 8, 3, 1, 2, 7, 1, 7, 5, 7, 2, 11, -1, -1, -1, -1},
297  /* c6 */ {9, 7, 5, 9, 2, 7, 9, 0, 2, 2, 11, 7, -1, -1, -1, -1},
298  /* c7 */ {7, 5, 2, 7, 2, 11, 5, 9, 2, 3, 2, 8, 9, 8, 2, -1},
299  /* c8 */ {2, 5, 10, 2, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1},
300  /* c9 */ {8, 2, 0, 8, 5, 2, 8, 7, 5, 10, 2, 5, -1, -1, -1, -1},
301  /* ca */ {9, 0, 1, 5, 10, 3, 5, 3, 7, 3, 10, 2, -1, -1, -1, -1},
302  /* cb */ {9, 8, 2, 9, 2, 1, 8, 7, 2, 10, 2, 5, 7, 5, 2, -1},
303  /* cc */ {1, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
304  /* cd */ {0, 8, 7, 0, 7, 1, 1, 7, 5, -1, -1, -1, -1, -1, -1, -1},
305  /* ce */ {9, 0, 3, 9, 3, 5, 5, 3, 7, -1, -1, -1, -1, -1, -1, -1},
306  /* cf */ {9, 8, 7, 5, 9, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
307  /* d0 */ {5, 8, 4, 5, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1},
308  /* d1 */ {5, 0, 4, 5, 11, 0, 5, 10, 11, 11, 3, 0, -1, -1, -1, -1},
309  /* d2 */ {0, 1, 9, 8, 4, 10, 8, 10, 11, 10, 4, 5, -1, -1, -1, -1},
310  /* d3 */ {10, 11, 4, 10, 4, 5, 11, 3, 4, 9, 4, 1, 3, 1, 4, -1},
311  /* d4 */ {2, 5, 1, 2, 8, 5, 2, 11, 8, 4, 5, 8, -1, -1, -1, -1},
312  /* d5 */ {0, 4, 11, 0, 11, 3, 4, 5, 11, 2, 11, 1, 5, 1, 11, -1},
313  /* d6 */ {0, 2, 5, 0, 5, 9, 2, 11, 5, 4, 5, 8, 11, 8, 5, -1},
314  /* d7 */ {9, 4, 5, 2, 11, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
315  /* d8 */ {2, 5, 10, 3, 5, 2, 3, 4, 5, 3, 8, 4, -1, -1, -1, -1},
316  /* d9 */ {5, 10, 2, 5, 2, 4, 4, 2, 0, -1, -1, -1, -1, -1, -1, -1},
317  /* da */ {3, 10, 2, 3, 5, 10, 3, 8, 5, 4, 5, 8, 0, 1, 9, -1},
318  /* db */ {5, 10, 2, 5, 2, 4, 1, 9, 2, 9, 4, 2, -1, -1, -1, -1},
319  /* dc */ {8, 4, 5, 8, 5, 3, 3, 5, 1, -1, -1, -1, -1, -1, -1, -1},
320  /* dd */ {0, 4, 5, 1, 0, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
321  /* de */ {8, 4, 5, 8, 5, 3, 9, 0, 5, 0, 3, 5, -1, -1, -1, -1},
322  /* df */ {9, 4, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
323  /* e0 */ {4, 11, 7, 4, 9, 11, 9, 10, 11, -1, -1, -1, -1, -1, -1, -1},
324  /* e1 */ {0, 8, 3, 4, 9, 7, 9, 11, 7, 9, 10, 11, -1, -1, -1, -1},
325  /* e2 */ {1, 10, 11, 1, 11, 4, 1, 4, 0, 7, 4, 11, -1, -1, -1, -1},
326  /* e3 */ {3, 1, 4, 3, 4, 8, 1, 10, 4, 7, 4, 11, 10, 11, 4, -1},
327  /* e4 */ {4, 11, 7, 9, 11, 4, 9, 2, 11, 9, 1, 2, -1, -1, -1, -1},
328  /* e5 */ {9, 7, 4, 9, 11, 7, 9, 1, 11, 2, 11, 1, 0, 8, 3, -1},
329  /* e6 */ {11, 7, 4, 11, 4, 2, 2, 4, 0, -1, -1, -1, -1, -1, -1, -1},
330  /* e7 */ {11, 7, 4, 11, 4, 2, 8, 3, 4, 3, 2, 4, -1, -1, -1, -1},
331  /* e8 */ {2, 9, 10, 2, 7, 9, 2, 3, 7, 7, 4, 9, -1, -1, -1, -1},
332  /* e9 */ {9, 10, 7, 9, 7, 4, 10, 2, 7, 8, 7, 0, 2, 0, 7, -1},
333  /* ea */ {3, 7, 10, 3, 10, 2, 7, 4, 10, 1, 10, 0, 4, 0, 10, -1},
334  /* eb */ {1, 10, 2, 8, 7, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
335  /* ec */ {4, 9, 1, 4, 1, 7, 7, 1, 3, -1, -1, -1, -1, -1, -1, -1},
336  /* ed */ {4, 9, 1, 4, 1, 7, 0, 8, 1, 8, 7, 1, -1, -1, -1, -1},
337  /* ee */ {4, 0, 3, 7, 4, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
338  /* ef */ {4, 8, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
339  /* f0 */ {9, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
340  /* f1 */ {3, 0, 9, 3, 9, 11, 11, 9, 10, -1, -1, -1, -1, -1, -1, -1},
341  /* f2 */ {0, 1, 10, 0, 10, 8, 8, 10, 11, -1, -1, -1, -1, -1, -1, -1},
342  /* f3 */ {3, 1, 10, 11, 3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
343  /* f4 */ {1, 2, 11, 1, 11, 9, 9, 11, 8, -1, -1, -1, -1, -1, -1, -1},
344  /* f5 */ {3, 0, 9, 3, 9, 11, 1, 2, 9, 2, 11, 9, -1, -1, -1, -1},
345  /* f6 */ {0, 2, 11, 8, 0, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
346  /* f7 */ {3, 2, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
347  /* f8 */ {2, 3, 8, 2, 8, 10, 10, 8, 9, -1, -1, -1, -1, -1, -1, -1},
348  /* f9 */ {9, 10, 2, 0, 9, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
349  /* fa */ {2, 3, 8, 2, 8, 10, 0, 1, 8, 1, 10, 8, -1, -1, -1, -1},
350  /* fb */ {1, 10, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
351  /* fc */ {1, 3, 8, 9, 1, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
352  /* fd */ {0, 9, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
353  /* fe */ {0, 3, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
354  /* ff */ {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}};
355 
356 /* pairs of vertices associated with the edge. */
357 HIDDEN int edge_vertex[12][2] = {
358  {0, 1}, {1, 2}, {2, 3}, {3, 0},
359  {4, 5}, {5, 6}, {6, 7}, {7, 4},
360  {0, 4}, {1, 5}, {2, 6}, {3, 7}};
361 
362 HIDDEN point_t point_offset[8] = {
363  {0, 0, 1}, {1, 0, 1}, {1, 0, 0}, {0, 0, 0},
364  {0, 1, 1}, {1, 1, 1}, {1, 1, 0}, {0, 1, 0}};
365 
366 
367 /* returns the number of triangles added or -1 on failure */
368 int
369 rt_tri_mc_realize_cube(fastf_t *tris, int pv, point_t *edges)
370 {
371  int *vi, fo;
372  fastf_t *mytri = tris;
373 
374  vi = (int *)(mc_tris[pv]);
375 
376  fo = 0;
377  while (*vi >= 0) {
378  if (++fo > 5) {
379  bu_log("Whoa, too many triangles?\n");
380  return -1;
381  }
382 
383  VMOVE(mytri, edges[vi[0]]);
384  VMOVE(mytri+1, edges[vi[1]]);
385  VMOVE(mytri+2, edges[vi[2]]);
386 
387  mytri+=3;
388  vi+=3;
389  }
390 
391  return fo;
392 }
393 
394 
395 int
396 nmg_mc_realize_cube(struct shell *s, int pv, point_t *edges, const struct bn_tol *tol)
397 {
398  int *vi, fo, valids = 0;
399  struct faceuse *fu;
400  struct vertex *vertl[3], **f_vertl[3];
401 
402  f_vertl[0] = &vertl[0];
403  f_vertl[1] = &vertl[2];
404  f_vertl[2] = &vertl[1];
405 
406  vi = (int *)(mc_tris[pv]);
407  /*
408  * vi now has the vertex list for our (possibly up to) 5 triangles as
409  * offsets into "edges". If the tuple is all '-1', there is no triangle. The
410  * vi array is actually 16 triangles, with an extra terminal -1.
411  */
412 
413  fo = 0;
414  while (*vi >= 0) {
415  if (++fo > 5) {
416  bu_log("Whoa, too many triangles?\n");
417  return -1;
418  }
419 
420  if (!bn_3pts_distinct(edges[vi[0]], edges[vi[1]], edges[vi[2]], tol) ||
421  bn_3pts_collinear(edges[vi[0]], edges[vi[1]], edges[vi[2]], tol)) {
422  vi+=3;
423  continue;
424  }
425 
426  valids++;
427 
428  memset((char *)vertl, 0, sizeof(vertl));
429  /* LOCK */
431 
432  fu = nmg_cmface(s, f_vertl, 3);
433 
434  nmg_vertex_gv(vertl[0], edges[vi[0]]);
435  nmg_vertex_gv(vertl[1], edges[vi[1]]);
436  nmg_vertex_gv(vertl[2], edges[vi[2]]);
437  if (nmg_calc_face_g(fu)) {
438  /* this flips out and spins. */
439  bu_log("Face calc failed\n");
440  nmg_kfu(fu);
441  bu_bomb("Bad face calc\n");
442  return 0;
443  }
444 
445  if (nmg_fu_planeeqn(fu, tol))
446  bu_log("Tiny triangle! <%g %g %g> <%g %g %g> <%g %g %g> (%g %g %g)\n",
447  V3ARGS(edges[vi[0]]), V3ARGS(edges[vi[1]]), V3ARGS(edges[vi[2]]),
448  DIST_PT_PT(edges[vi[0]], edges[vi[1]]),
449  DIST_PT_PT(edges[vi[0]], edges[vi[2]]),
450  DIST_PT_PT(edges[vi[1]], edges[vi[2]]));
451  /* UNLOCK */
453 
454  vi+=3;
455  }
456 
457  return valids;
458 }
459 
460 
461 HIDDEN fastf_t bin(fastf_t val, fastf_t step) {return step*floor(val/step);}
462 
463 #define INHIT 1
464 #define OUTHIT 2
465 #define NOHIT -1
466 struct whack {
467  point_t hit;
468  int in; /* 1 for inhit, 2 for outhit, -1 to terminate */
469 };
470 
471 
472 HIDDEN int
473 bangbang(struct application * a, struct partition *PartHeadp, struct seg * UNUSED(s))
474 {
475  struct partition *pp;
476  struct whack *t = (struct whack *)a->a_uptr;
477  int intersects = 0;
478 
479  for (pp = PartHeadp->pt_forw; pp != PartHeadp; pp = pp->pt_forw) {
480  if (pp->pt_outhit->hit_dist>0.0) {
481  if (pp->pt_inhit->hit_dist>0.0) {
482  VJOIN1(t->hit, a->a_ray.r_pt, pp->pt_inhit->hit_dist, a->a_ray.r_dir);
483  t->in=INHIT;
484  t++;
485  intersects++;
486  }
487  VJOIN1(t->hit, a->a_ray.r_pt, pp->pt_outhit->hit_dist, a->a_ray.r_dir);
488  t->in=OUTHIT;
489  t++;
490  intersects++;
491  if (intersects >= MAX_INTERSECTS)
492  bu_bomb("Too many intersects in marching cubes");
493  }
494  }
495  t->in = NOHIT;
496  return 0;
497 }
498 
499 
500 HIDDEN int
501 missed(struct application *a)
502 {
503  struct whack *t = (struct whack *)a->a_uptr;
504  t->in = NOHIT;
505  return 0;
506 }
507 
508 
509 HIDDEN int
510 bitdiff(unsigned char t, unsigned char a, unsigned char b)
511 {
512  unsigned char ma, mb, hb;
513  ma = 1<<a;
514  mb = 1<<b;
515  hb = t&(ma|mb);
516  return hb == ma || hb == mb;
517 }
518 
519 
520 HIDDEN int
521 rt_nmg_mc_crosspew(struct application *a, int edge, point_t *p, point_t *edges, struct whack *muh, const fastf_t step, const struct bn_tol *tol)
522 {
523  struct whack *puh;
524  int i;
525  fastf_t dist;
526 
527  for (i = 0; i < MAX_INTERSECTS; i++) {
528  muh[i].in = 0;
529  VSETALL(muh[i].hit, VOODOO);
530  }
531 
532  VJOIN1(a->a_ray.r_pt, *p, -2*tol->dist, a->a_ray.r_dir);
533  rt_shootray(a);
534  puh=muh;
535  while (puh->in > 0 && puh->hit[Z] <= a->a_ray.r_pt[Z]-tol->dist) {
536  bu_log("%d %g isn't close enough, moving on\n", puh->in, puh->hit[Z]);
537  puh++;
538  if (puh->in < 1)
539  bu_log("puhh?\n");
540  }
541  dist = DIST_PT_PT(a->a_ray.r_pt, puh->hit);
542  if (dist > (step + 2.5*tol->dist)) {
543  bu_log("spooky action on edge:%d. (in:%d) (%g %g %g -> %g %g %g) step:%g dist:%g\n", edge, puh->in, V3ARGS(a->a_ray.r_pt), V3ARGS(a->a_ray.r_dir), step, dist);
544  VJOIN1(edges[edge], a->a_ray.r_pt, 0.5*step+tol->dist, a->a_ray.r_dir);
545  } else if (puh->in > 0)
546  VMOVE(edges[edge], muh->hit);
547  return 0;
548 }
549 
550 
551 HIDDEN int
552 rt_nmg_mc_pew(struct shell *s, struct whack *primp[4], struct application *a, fastf_t x, fastf_t y, fastf_t b, fastf_t step, const struct bn_tol *tol)
553 {
554  int i, in[4] = { 0, 0, 0, 0}, count = 0;
555  fastf_t last_b = -VOODOO;
556 
557  while (primp[0]->in>0 || primp[1]->in>0 || primp[2]->in>0 || primp[3]->in>0) {
558  unsigned char pv;
559  point_t edges[12];
560  struct whack muh[MAX_INTERSECTS];
561  point_t p[8];
562 
563  a->a_uptr = muh;
564  if ((in[0]|in[1]|in[2]|in[3]) == 0) {
565  b = +INFINITY;
566  /* figure out the first hit distance and bin it */
567  for (i = 0; i < 4; i++)
568  if (primp[i]->in>0 && primp[i]->hit[Z] < b) b = primp[i]->hit[Z];
569  b = bin(b, step);
570  } else {
571  /* if we know we're intersecting the surface, walk slow. */
572  if (NEAR_ZERO(last_b+VOODOO, tol->dist))
573  bu_log("teh fux? lastb = %g\n", last_b);
574  b = last_b + step;
575  }
576 
577  for (i = 0; i < 8; i++)
578  VSET(p[i], x+step*point_offset[i][X], y+step*point_offset[i][Y], b+step*point_offset[i][Z]);
579 
580  /* build the point vector */
581  pv = 0;
582  if (in[0] && primp[0]->hit[Z] > b+step) pv |= 0x09;
583  if (in[1] && primp[1]->hit[Z] > b+step) pv |= 0x06;
584  if (in[2] && primp[2]->hit[Z] > b+step) pv |= 0x90;
585  if (in[3] && primp[3]->hit[Z] > b+step) pv |= 0x60;
586 
587 #define MEH(A, I, O) \
588  if (primp[A][1].in > 0 && primp[A][1].hit[Z] < b+step+tol->dist) primp[A]+=2; \
589  if (primp[A]->hit[Z] < b+step+tol->dist) { \
590  if (primp[A]->in==1) { in[A]=1; pv |= 1<<I;} \
591  if (primp[A]->in==2) { in[A]=0; pv |= 1<<O;} \
592  } else pv |= in[A]<<I | in[A]<<O;
593 
594  /* p t b */
595  MEH(0, 0, 3);
596  MEH(1, 1, 2);
597  MEH(2, 4, 7);
598  MEH(3, 5, 6);
599 #undef MEH
600 
601 #define MUH(a, l) if (bitdiff(pv, edge_vertex[a][0], edge_vertex[a][1])) { VMOVE(edges[a], l->hit); l++; } /* we already have ray intersect data for these. */
602  for (i = 0; i < 12; i++)
603  VSETALL(edges[i], VOODOO);
604 
605  MUH(1 , primp[1]);
606  MUH(3 , primp[0]);
607  MUH(5 , primp[3]);
608  MUH(7 , primp[2]);
609 #undef MUH
610 
613  for (i = 1; i < 8; i += 2)
614  if (bitdiff(pv, edge_vertex[i][0], edge_vertex[i][1]))
615  VADD2SCALE(edges[i], p[edge_vertex[i][0]], p[edge_vertex[i][1]], 0.5);
616  for (i = 0; i < 7; i += 2)
617  if (bitdiff(pv, edge_vertex[i][0], edge_vertex[i][1]))
618  VADD2SCALE(edges[i], p[edge_vertex[i][0]], p[edge_vertex[i][1]], 0.5);
619  for (i = 8; i < 12; i++)
620  if (bitdiff(pv, edge_vertex[i][0], edge_vertex[i][1]))
621  VADD2SCALE(edges[i], p[edge_vertex[i][0]], p[edge_vertex[i][1]], 0.5);
622  } else {
623  /* the 'muh' list may have to be walked. */
624 #define MEH(A, B, C) if (bitdiff(pv, B, C)) rt_nmg_mc_crosspew(a, A, p+B, edges, muh, step, tol)
625  VSET(a->a_ray.r_dir, 1, 0, 0);
626  MEH(0 , 0, 1);
627  MEH(2 , 3, 2);
628  MEH(4 , 4, 5);
629  MEH(6 , 7, 6);
630 
631  VSET(a->a_ray.r_dir, 0, 1, 0);
632  MEH(8 , 0, 4);
633  MEH(9 , 1, 5);
634  MEH(10, 2, 6);
635  MEH(11, 3, 7);
636 #undef MEH
637 #define MEH(A, B, C, D) if (NEAR_EQUAL(edges[B][Z], p[A][Z], tol->dist)) { VMOVE(edges[C], p[A]); VMOVE(edges[D], p[A]); }
638  MEH(0, 3, 0, 8);
639  MEH(1, 1, 0, 9);
640  MEH(2, 1, 2, 10);
641  MEH(3, 3, 2, 11);
642  MEH(4, 7, 4, 8);
643  MEH(5, 5, 4, 9);
644  MEH(6, 5, 6, 10);
645  MEH(7, 7, 6, 11);
646 #undef MEH
647  }
648 
649  /* stuff it into an nmg shell */
650  if (pv != 0 && pv != 0xff && s) /* && s should go away. */
651  count += nmg_mc_realize_cube(s, pv, edges, tol);
652 
653  last_b = b;
654  }
655  return count;
656 }
657 
658 
659 struct mci_s {
660  struct shell *s; /* where to put it. */
661  double step;
662  struct rt_i *rtip;
663  const struct bn_tol *tol;
666  unsigned long count;
667  int ncpu;
668 };
669 
670 
671 HIDDEN void
672 fire_row(int cpu, void * ptr)
673 {
674  struct mci_s *m = (struct mci_s *)ptr;
675  struct application a;
676  struct whack prim[4][MAX_INTERSECTS];
677  struct whack *primp[4];
678  fastf_t x, y, z;
679  unsigned long count = 0;
680 
682  a.a_rt_i = m->rtip;
683  a.a_rt_i->useair = 1;
684  a.a_hit = bangbang;
685  a.a_miss = missed;
687  a.a_resource = m->resources + cpu;
688 
689  x=bin(a.a_rt_i->mdl_min[X], m->step) - m->step + (m->step * cpu);
690 
691  for (; x<m->endx; x += m->step * (fastf_t)m->ncpu) {
692  y=bin(a.a_rt_i->mdl_min[Y], m->step) - m->step;
693  for (; y<m->endy; y+=m->step) {
694  int i, j;
695 
696  for (i = 0; i < 4; i++)
697  primp[i] = prim[i];
698 
699  for (i = 0; i < 4; i++)
700  for (j = 0; j < MAX_INTERSECTS - 1; j++) {
701  prim[i][j].in = 0;
702  VSETALL(prim[i][j].hit, VOODOO);
703  }
704 
705  z = bin(a.a_rt_i->mdl_min[Z] - m->tol->dist - m->step, m->step);
706 
707  VSET(a.a_ray.r_dir, 0, 0, 1);
708  a.a_uptr = primp[0];
709  VSET(a.a_ray.r_pt, x, y, z);
710  rt_shootray(&a);
711 
712  a.a_uptr = primp[1];
713  VSET(a.a_ray.r_pt, x+m->step, y, z);
714  rt_shootray(&a);
715 
716  a.a_uptr = primp[2];
717  VSET(a.a_ray.r_pt, x, y+m->step, z);
718  rt_shootray(&a);
719 
720  a.a_uptr = primp[3];
721  VSET(a.a_ray.r_pt, x+m->step, y+m->step, z);
722  rt_shootray(&a);
723 
724  z = +INFINITY;
725 
726  count += rt_nmg_mc_pew(m->s, primp, &a, x, y, z, m->step, m->tol);
727  }
728  }
729  bu_log("%d done, %lu\n", cpu, count);
730  m->count += count;
731  /* free the rt stuff we don't need anymore */
732 }
733 
734 
735 /* rtip needs to be valid, s is where the results are stashed */
736 int
737 nmg_mc_evaluate(struct shell *s, struct rt_i *rtip, const struct db_full_path *pathp, const struct rt_tess_tol *ttol, const struct bn_tol *tol)
738 {
739  struct mci_s m;
740  int i;
741 
742  m.s = s;
743  m.rtip = rtip;
744  m.tol = tol;
745  m.count = 0;
746 
747  m.ncpu = bu_avail_cpus();
748  m.ncpu = 1; /* seems to be an issue with confused loop calculation in the NMG code. */
749  for (i = 0; i < MAX_PSW; i++)
750  rt_init_resource(&m.resources[i], i, rtip);
751 
752  rt_gettree(rtip, db_path_to_string(pathp));
753  rt_prep_parallel(rtip, m.ncpu);
754 
755  /* use rel value * bounding spheres diameter or the abs tolerance */
756  m.step = NEAR_ZERO(ttol->abs, tol->dist) ? 0.5 * rtip->rti_radius * ttol->rel : ttol->abs;
757 
758  m.endx=bin(rtip->mdl_max[X], m.step) + m.step;
759  m.endy=bin(rtip->mdl_max[Y], m.step) + m.step;
760 
761  bu_parallel(fire_row, m.ncpu, &m);
762 
763  return m.count;
764 }
765 
766 
767 void
768 nmg_triangulate_model_mc(struct model *m, const struct bn_tol *tol)
769 {
770  BN_CK_TOL(tol);
771  NMG_CK_MODEL(m);
772  nmg_vmodel(m);
773 
774  if (RTG.NMG_debug & DEBUG_TRI)
775  bu_log("Triangulating NMG\n");
776 
777  if (RTG.NMG_debug & DEBUG_TRI)
778  bu_log("Triangulation completed\n");
779 }
780 
781 
782 /*
783  * Local Variables:
784  * mode: C
785  * tab-width: 8
786  * indent-tabs-mode: t
787  * c-file-style: "stroustrup"
788  * End:
789  * ex: shiftwidth=4 tabstop=8
790  */
void nmg_triangulate_model_mc(struct model *m, const struct bn_tol *tol)
Definition: nmg_tri_mc.c:768
Definition: db_flip.c:35
#define MAX_INTERSECTS
Definition: nmg_tri_mc.c:81
struct xray a_ray
Actual ray to be shot.
Definition: raytrace.h:1583
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
struct hit * pt_outhit
OUT hit ptr.
Definition: raytrace.h:579
double rti_radius
radius of model bounding sphere
Definition: raytrace.h:1773
HIDDEN int rt_nmg_mc_crosspew(struct application *a, int edge, point_t *p, point_t *edges, struct whack *muh, const fastf_t step, const struct bn_tol *tol)
Definition: nmg_tri_mc.c:521
int nmg_fu_planeeqn(struct faceuse *fu, const struct bn_tol *tol)
Definition: nmg_mod.c:1311
point_t mdl_min
min corner of model bounding RPP
Definition: raytrace.h:1769
int nmg_kfu(struct faceuse *fu1)
Definition: nmg_mk.c:1207
double step
Definition: nmg_tri_mc.c:661
double dist
>= 0
Definition: tol.h:73
if lu s
Definition: nmg_mod.c:3860
fastf_t endy
Definition: nmg_tri_mc.c:665
int useair
1="air" regions are retained while prepping
Definition: raytrace.h:1756
#define VSET(a, b, c, d)
Definition: color.c:53
#define VSETALL(a, s)
Definition: color.c:54
void bu_semaphore_acquire(unsigned int i)
Definition: semaphore.c:180
Definition: raytrace.h:368
Definition: raytrace.h:248
void nmg_vertex_gv(struct vertex *v, const fastf_t *pt)
Definition: nmg_mk.c:1668
struct shell * s
Definition: nmg_tri_mc.c:660
Header file for the BRL-CAD common definitions.
HIDDEN int edge_vertex[12][2]
Definition: nmg_tri_mc.c:357
struct resource * a_resource
dynamic memory resources
Definition: raytrace.h:1591
int a_onehit
flag to stop on first hit
Definition: raytrace.h:1586
int nmg_mc_realize_cube(struct shell *s, int pv, point_t *edges, const struct bn_tol *tol)
Definition: nmg_tri_mc.c:396
int(* a_hit)(struct application *, struct partition *, struct seg *)
called when shot hits model
Definition: raytrace.h:1584
struct hit * pt_inhit
IN hit pointer.
Definition: raytrace.h:577
int marching_cubes_use_midpoint
Definition: nmg_tri_mc.c:86
#define HIDDEN
Definition: common.h:86
const struct bn_tol * tol
Definition: nmg_tri_mc.c:663
int nmg_calc_face_g(struct faceuse *fu)
Definition: nmg_misc.c:1786
HIDDEN int bangbang(struct application *a, struct partition *PartHeadp, struct seg *s)
Definition: nmg_tri_mc.c:473
double rel
rel dist tol
Definition: raytrace.h:181
void rt_init_resource(struct resource *resp, int cpu_num, struct rt_i *rtip)
Definition: prep.c:585
int nmg_mc_evaluate(struct shell *s, struct rt_i *rtip, const struct db_full_path *pathp, const struct rt_tess_tol *ttol, const struct bn_tol *tol)
Definition: nmg_tri_mc.c:737
#define OUTHIT
Definition: nmg_tri_mc.c:464
Definition: color.c:49
struct rt_i * a_rt_i
this librt instance
Definition: raytrace.h:1588
#define MUH(a, l)
struct resource resources[MAX_PSW]
Definition: nmg_tri_mc.c:664
void * memset(void *s, int c, size_t n)
uint32_t NMG_debug
debug bits for NMG's see nmg.h
Definition: raytrace.h:1699
#define NOHIT
Definition: nmg_tri_mc.c:465
#define V3ARGS(a)
Definition: color.c:56
#define NEAR_ZERO(val, epsilon)
Definition: color.c:55
#define MEH(A, I, O)
#define INHIT
Definition: nmg_tri_mc.c:463
fastf_t endx
Definition: nmg_tri_mc.c:665
#define UNUSED(parameter)
Definition: common.h:239
Support for uniform tolerances.
Definition: tol.h:71
#define BN_CK_TOL(_p)
Definition: tol.h:82
char * db_path_to_string(const struct db_full_path *pp)
Definition: db_fullpath.c:191
HIDDEN int missed(struct application *a)
Definition: nmg_tri_mc.c:501
void bu_semaphore_release(unsigned int i)
Definition: semaphore.c:218
void nmg_vmodel(const struct model *m)
Definition: nmg_ck.c:635
size_t bu_avail_cpus(void)
Definition: parallel.c:193
vect_t r_dir
Direction of ray (UNIT Length)
Definition: raytrace.h:219
#define MAX_PSW
Definition: parallel.h:48
void bu_parallel(void(*func)(int func_ncpu, void *func_data), int ncpu, void *data)
int rt_gettree(struct rt_i *rtip, const char *node)
Definition: tree.c:869
#define RT_SEM_WORKER
Definition: raytrace.h:1730
int ncpu
Definition: nmg_tri_mc.c:667
point_t hit
Definition: nmg_tri_mc.c:467
point_t r_pt
Point at which ray starts.
Definition: raytrace.h:218
HIDDEN int bitdiff(unsigned char t, unsigned char a, unsigned char b)
Definition: nmg_tri_mc.c:510
int bn_3pts_collinear(point_t a, point_t b, point_t c, const struct bn_tol *tol)
Check to see if three points are collinear.
HIDDEN fastf_t bin(fastf_t val, fastf_t step)
Definition: nmg_tri_mc.c:461
point_t mdl_max
max corner of model bounding RPP
Definition: raytrace.h:1770
double abs
absolute dist tol
Definition: raytrace.h:180
int bn_3pts_distinct(const point_t a, const point_t b, const point_t c, const struct bn_tol *tol)
unsigned long count
Definition: nmg_tri_mc.c:666
Definition: color.c:51
void rt_prep_parallel(struct rt_i *rtip, int ncpu)
int rt_shootray(struct application *ap)
void * a_uptr
application-specific pointer
Definition: raytrace.h:1618
int in
Definition: nmg_tri_mc.c:468
int rt_tri_mc_realize_cube(fastf_t *tris, int pv, point_t *edges)
Definition: nmg_tri_mc.c:369
HIDDEN int mc_tris[256][16]
Definition: nmg_tri_mc.c:98
#define VOODOO
Definition: nmg_tri_mc.c:83
int(* a_miss)(struct application *)
called when shot misses
Definition: raytrace.h:1585
struct rt_i * rtip
Definition: nmg_tri_mc.c:662
struct faceuse * nmg_cmface(struct shell *s, struct vertex ***verts, int n)
Definition: nmg_mod.c:979
struct partition * pt_forw
forwards link
Definition: raytrace.h:574
#define RT_APPLICATION_INIT(_p)
Definition: raytrace.h:1676
fastf_t hit_dist
dist from r_pt to hit_point
Definition: raytrace.h:250
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
double fastf_t
Definition: defines.h:300
Definition: color.c:50
HIDDEN void fire_row(int cpu, void *ptr)
Definition: nmg_tri_mc.c:672
HIDDEN int rt_nmg_mc_pew(struct shell *s, struct whack *primp[4], struct application *a, fastf_t x, fastf_t y, fastf_t b, fastf_t step, const struct bn_tol *tol)
Definition: nmg_tri_mc.c:552
HIDDEN point_t point_offset[8]
Definition: nmg_tri_mc.c:362
struct rt_g RTG
Definition: globals.c:39