BRL-CAD
bot_wireframe.cpp
Go to the documentation of this file.
1 #include "common.h"
2 
3 #include <map>
4 #include <queue>
5 
6 #include "vmath.h"
7 #include "raytrace.h"
8 #include "wdb.h"
9 
10 // Make an edge using consistent vertex ordering
11 static std::pair<unsigned int, unsigned int>
12 mk_edge(unsigned int pt_A, unsigned int pt_B)
13 {
14  if (pt_A <= pt_B) {
15  return std::make_pair(pt_A, pt_B);
16  } else {
17  return std::make_pair(pt_B, pt_A);
18  }
19 }
20 
21 // Build a set of edge-centric data structures to represent the mesh
22 unsigned int
23 edge_mappings(struct rt_bot_internal *bot, unsigned int **edges_ptr, unsigned int **faces_ptr) {
24 
25  // Nick Reed's idea - use a C++ map of pairs to ints as a one-time method
26  // to generate unique int identifiers for edges.
27  std::map<std::pair<unsigned int, unsigned int>, unsigned int> edge_to_int;
28  std::pair<std::map<std::pair<unsigned int, unsigned int>, unsigned int>::iterator, bool> ret;
29  unsigned int edge_cnt = 0;
30  // Each face will have 3 edges
31  unsigned int *faces = *edges_ptr;
32  // Max possible need for this array is 3 edges for each face, 2 vertex indices per edge
33  unsigned int *edges = *faces_ptr;
34 
35  for (unsigned int i = 0; i < bot->num_faces; ++i) {
36  ret = edge_to_int.insert(std::pair<std::pair<unsigned int, unsigned int>, unsigned int>(mk_edge(bot->faces[i*3+0], bot->faces[i*3+1]), edge_cnt));
37  if (ret.second == false) {
38  // rows are faces, columns are the 1st, 2nd and 3rd edges
39  faces[3 * i + 0] = ret.first->second;
40  } else {
41  // rows are faces, columns are the 1st, 2nd and 3rd edges
42  faces[3 * i + 0] = edge_cnt;
43  edges[2 * edge_cnt + 0] = bot->faces[i*3+0];
44  edges[2 * edge_cnt + 1] = bot->faces[i*3+1];
45  edge_cnt++;
46  }
47  ret = edge_to_int.insert(std::pair<std::pair<unsigned int, unsigned int>, unsigned int>(mk_edge(bot->faces[i*3+1], bot->faces[i*3+2]), edge_cnt));
48  if (ret.second == false) {
49  // rows are faces, columns are the 1st, 2nd and 3rd edges
50  faces[3 * i + 1] = ret.first->second;
51  } else {
52  // rows are faces, columns are the 1st, 2nd and 3rd edges
53  faces[3 * i + 1] = edge_cnt;
54  edges[2 * edge_cnt + 0] = bot->faces[i*3+1];
55  edges[2 * edge_cnt + 1] = bot->faces[i*3+2];
56  edge_cnt++;
57  }
58  ret = edge_to_int.insert(std::pair<std::pair<unsigned int, unsigned int>, unsigned int>(mk_edge(bot->faces[i*3+2], bot->faces[i*3+0]), edge_cnt));
59  if (ret.second == false) {
60  // rows are faces, columns are the 1st, 2nd and 3rd edges
61  faces[3 * i + 2] = ret.first->second;
62  } else {
63  // rows are faces, columns are the 1st, 2nd and 3rd edges
64  faces[3 * i + 2] = edge_cnt;
65  edges[2 * edge_cnt + 0] = bot->faces[i*3+2];
66  edges[2 * edge_cnt + 1] = bot->faces[i*3+0];
67  edge_cnt++;
68  }
69  }
70 
71  return edge_cnt;
72 }
73 
74 
75 // Calculate area of a face
76 static double
77 face_area(struct rt_bot_internal *bot, size_t face_num)
78 {
79  point_t ptA, ptB, ptC;
80  double a, b, c, p;
81  double area;
82  VMOVE(ptA, &bot->vertices[bot->faces[face_num*3+0]*3]);
83  VMOVE(ptB, &bot->vertices[bot->faces[face_num*3+1]*3]);
84  VMOVE(ptC, &bot->vertices[bot->faces[face_num*3+2]*3]);
85  a = DIST_PT_PT(ptA, ptB);
86  b = DIST_PT_PT(ptB, ptC);
87  c = DIST_PT_PT(ptC, ptA);
88  p = (a + b + c)/2;
89  area = sqrt(p*(p-a)*(p-b)*(p-c));
90  return area;
91 }
92 
93 /**********************************************************
94  * Code for identifying semi-flat patches in bots
95  * and creating wireframe edges
96  **********************************************************/
97 extern "C" int
98 rt_bot_adaptive_plot(struct rt_db_internal *ip, const struct rt_view_info *info)
99 {
100  struct rt_bot_internal *bot;
101  RT_CK_DB_INTERNAL(ip);
102  BU_CK_LIST_HEAD(info->vhead);
103  bot = (struct rt_bot_internal *)ip->idb_ptr;
104  RT_BOT_CK_MAGIC(bot);
105  vect_t gvects[6];
106  VSET(gvects[0], -1,0,0);
107  VSET(gvects[1], 0,-1,0);
108  VSET(gvects[2], 0,0,-1);
109  VSET(gvects[3], 1,0,0);
110  VSET(gvects[4], 0,1,0);
111  VSET(gvects[5], 0,0,1);
112 
113  if (bot->num_vertices <= 0 || !bot->vertices || bot->num_faces <= 0 || !bot->faces)
114  return 0;
115 
116  /* Declare key containers */
117  double *face_normals= (double *)bu_calloc(bot->num_faces * 3, sizeof(double), "normals");
118  /* Stash all the initial categorization test results - can be re-used later */
119 // unsigned int *categorization_results = (unsigned int *)bu_calloc(sizeof(unsigned int) * bot->num_faces * 6, "categorization results");
120  /* Initial group assignments */
121  unsigned int *groups = (unsigned int *)bu_calloc(bot->num_faces, sizeof(unsigned int), "groups");
122  /* Initially, patch breakdown is made in a faces -> patch_id map */
123  unsigned int *patches= (unsigned int *)bu_calloc(bot->num_faces, sizeof(unsigned int), "patch_id_numbers");
124  /* Don't know yet how big these needs to be */
125  unsigned int *vert_to_face = NULL;
126 
127  /* Sanity check vertex indices in face definitions */
128  for (unsigned int i = 0; i < bot->num_faces; ++i) {
129  if ((unsigned int)bot->faces[i*3+0] > (unsigned int)(bot->num_vertices)) return 0;
130  if ((unsigned int)bot->faces[i*3+1] > (unsigned int)(bot->num_vertices)) return 0;
131  if ((unsigned int)bot->faces[i*3+2] > (unsigned int)(bot->num_vertices)) return 0;
132  }
133 
134  /* Pre-compute face normals once */
135  for (unsigned int i = 0; i < bot->num_faces; i++) {
136  vect_t a, b, norm_dir;
137  VSUB2(a, &bot->vertices[bot->faces[i*3+1]*3], &bot->vertices[bot->faces[i*3]*3]);
138  VSUB2(b, &bot->vertices[bot->faces[i*3+2]*3], &bot->vertices[bot->faces[i*3]*3]);
139  VCROSS(norm_dir, a, b);
140  VUNITIZE(norm_dir);
141  face_normals[i*3]=norm_dir[0];
142  face_normals[i*3+1]=norm_dir[1];
143  face_normals[i*3+2]=norm_dir[2];
144  }
145 
146  /* Calculate categorization results and assign groups */
147  for (unsigned int i = 0; i < bot->num_faces; i++) {
148  int result_max = 0;
149  double result = 0.0;
150  double vdot = 0.0;
151  vect_t norm_dir;
152  VSET(norm_dir, face_normals[i*3], face_normals[i*3+1], face_normals[i*3+2]);
153  for (unsigned int j=0; j < 6; j++) {
154  vdot = VDOT(gvects[j],norm_dir);
155  //categorization_results[i*j] = vdot;
156  if (vdot > result) {
157  result_max = j;
158  result = vdot;
159  }
160  }
161  groups[i] = result_max;
162  }
163  bu_free(face_normals, "face_normals");
164 
165  /* Determine the maximum number of faces associated with any one vertex */
166  unsigned int *vert_face_cnt = (unsigned int *)bu_calloc(bot->num_vertices, sizeof(unsigned int), "vert face cnt");
167  for (unsigned int i = 0; i < bot->num_faces; i++) {
168  vert_face_cnt[bot->faces[i*3+0]]++;
169  vert_face_cnt[bot->faces[i*3+1]]++;
170  vert_face_cnt[bot->faces[i*3+2]]++;
171  }
172  unsigned int max_face_cnt = 0;
173  for (unsigned int i = 0; i < bot->num_vertices; i++) {
174  if (vert_face_cnt[i] > max_face_cnt)
175  max_face_cnt = vert_face_cnt[i];
176  }
177  /* Now, allocate a 2D array that can hold the full vert->face map
178  * and populate it */
179  vert_to_face = (unsigned int *)bu_calloc(bot->num_vertices * max_face_cnt, sizeof(unsigned int), "map");
180  unsigned int *vert_sizes = (unsigned int *)bu_calloc(bot->num_vertices, sizeof(unsigned int), "map");
181  for (unsigned int i = 0; i < bot->num_faces; i++) {
182  for (unsigned int j = 0; j < 3; j++) {
183  unsigned int vert = bot->faces[i*3+j];
184  unsigned int k = vert_sizes[vert];
185  /* rows are vertex indexes, columns hold the faces */
186  /* Need to increment face index by one so we can reference
187  * the first face and still use the true/false test that 0 allows */
188  vert_to_face[max_face_cnt * vert + k] = i + 1;
189  vert_sizes[vert]++;
190  //bu_log("vert_to_face(%d,%d)[%d] = %d\n", vert, k, max_face_cnt * vert + k, i + 1);
191  }
192  }
193 
194 
195  /* Order the groups by number of bots */
196  /* Note - needed only when group boarders are not enforced in patch building */
197 // unsigned int group_cnt[6] = {0};
198  unsigned int ordered_groups[6] = {0,1,2,3,4,5};
199 /* for (unsigned int i = 0; i < bot->num_faces; i++) {
200  group_cnt[groups[i]]++;
201  }
202  for (unsigned int i = 0; i < 6; i++) {
203  unsigned int more = 0;
204  for (unsigned int j = 0; j < 6; j++) {
205  if (group_cnt[j] > group_cnt[i]) more++;
206  }
207  ordered_groups[more] = i;
208  }
209 */
210 
211 
212  // All faces must belong to some patch - continue until all faces are processed
213  unsigned int patch_cnt = 0;
214  for (unsigned int i = 0; i < 6; i++) {
215  int unused = 0;
216  while (unused != -1) {
217  unsigned int face_stp = 0;
218  // Start a new patch
219  unused = -1;
220  patch_cnt++;
221  // Find remaining face in group
222  while (unused == -1 && face_stp < bot->num_faces) {
223  if (ordered_groups[i] == groups[face_stp] && !patches[face_stp]) {
224  unused = face_stp;
225  }
226  face_stp++;
227  }
228  if (unused != -1) {
229  std::queue<unsigned int> face_queue;
230  face_queue.push(unused);
231  patches[unused] = patch_cnt;
232  while (!face_queue.empty()) {
233  unsigned int face_num = face_queue.front();
234  face_queue.pop();
235  for (unsigned int k = 0; k < 3; k++) {
236  unsigned int vert_id = bot->faces[face_num*3+k];
237  for (unsigned int l = 0; l < vert_face_cnt[vert_id]; l++) {
238  unsigned int new_face = vert_to_face[max_face_cnt * vert_id + l] - 1;
239  if (groups[new_face] == ordered_groups[i] && !patches[new_face]) {
240  face_queue.push(new_face);
241  patches[new_face] = patch_cnt;
242  }
243  }
244  }
245  }
246  }
247  }
248  }
249  bu_free(groups, "groups");
250  bu_free(vert_to_face, "vert_to_face");
251 
252  unsigned int *patch_vert_cnt = vert_sizes;
253  memset(patch_vert_cnt, 0, bot->num_vertices * sizeof(unsigned int));
254  unsigned int *vert_edge_status = (unsigned int *)bu_calloc(bot->num_vertices, sizeof(unsigned int), "vert status");
255  for (unsigned int i = 0; i < patch_cnt; i++) {
256  memset(patch_vert_cnt, 0, bot->num_vertices * sizeof(unsigned int));
257  for (unsigned int j = 0; j < bot->num_faces; j++) {
258  if (patches[j] == i+1) {
259  patch_vert_cnt[bot->faces[j*3+0]]++;
260  patch_vert_cnt[bot->faces[j*3+1]]++;
261  patch_vert_cnt[bot->faces[j*3+2]]++;
262  }
263  }
264  for (unsigned int j = 0; j < bot->num_vertices; j++) {
265  if (patch_vert_cnt[j] && patch_vert_cnt[j] != vert_face_cnt[j]) {
266  vert_edge_status[j]++;
267  }
268  }
269  }
270  bu_free(patches, "patches");
271  bu_free(patch_vert_cnt, "patch_vert_cnt");
272  bu_free(vert_face_cnt, "vert_face_cnt");
273 
274  for (unsigned int j = 0; j < bot->num_faces; j++) {
275  if (vert_edge_status[bot->faces[j*3+0]] && vert_edge_status[bot->faces[j*3+1]]) {
276  RT_ADD_VLIST(info->vhead, &(bot->vertices[bot->faces[j*3+0]*3]), BN_VLIST_LINE_MOVE);
277  RT_ADD_VLIST(info->vhead, &(bot->vertices[bot->faces[j*3+1]*3]), BN_VLIST_LINE_DRAW);
278  }
279  if (vert_edge_status[bot->faces[j*3+1]] && vert_edge_status[bot->faces[j*3+2]]) {
280  RT_ADD_VLIST(info->vhead, &(bot->vertices[bot->faces[j*3+1]*3]), BN_VLIST_LINE_MOVE);
281  RT_ADD_VLIST(info->vhead, &(bot->vertices[bot->faces[j*3+2]*3]), BN_VLIST_LINE_DRAW);
282  }
283  if (vert_edge_status[bot->faces[j*3+2]] && vert_edge_status[bot->faces[j*3+0]]) {
284  RT_ADD_VLIST(info->vhead, &(bot->vertices[bot->faces[j*3+2]*3]), BN_VLIST_LINE_MOVE);
285  RT_ADD_VLIST(info->vhead, &(bot->vertices[bot->faces[j*3+0]*3]), BN_VLIST_LINE_DRAW);
286  }
287  }
288 
289  bu_free(vert_edge_status, "vert status");
290 
291  return 0;
292 }
293 
294 // Local Variables:
295 // tab-width: 8
296 // mode: C++
297 // c-basic-offset: 4
298 // indent-tabs-mode: t
299 // c-file-style: "stroustrup"
300 // End:
301 // ex: shiftwidth=4 tabstop=8
int rt_bot_adaptive_plot(struct rt_db_internal *ip, const struct rt_view_info *info)
#define VSET(a, b, c, d)
Definition: color.c:53
Header file for the BRL-CAD common definitions.
std::pair< size_t, size_t > mk_edge(size_t pt_A, size_t pt_B)
void * memset(void *s, int c, size_t n)
struct bu_list * vhead
Definition: raytrace.h:1926
#define RT_ADD_VLIST(hd, pnt, draw)
Definition: raytrace.h:1865
#define RT_CK_DB_INTERNAL(_p)
Definition: raytrace.h:207
void * bu_calloc(size_t nelem, size_t elsize, const char *str)
Definition: malloc.c:321
#define BN_VLIST_LINE_MOVE
Definition: vlist.h:82
#define BN_VLIST_LINE_DRAW
Definition: vlist.h:83
void * idb_ptr
Definition: raytrace.h:195
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
#define BU_CK_LIST_HEAD(_p)
Definition: list.h:142
unsigned int edge_mappings(struct rt_bot_internal *bot, unsigned int **edges_ptr, unsigned int **faces_ptr)