BRL-CAD
bot_solidity.c
Go to the documentation of this file.
1 /* B O T _ S O L I D I T Y . C
2  * BRL-CAD
3  *
4  * Copyright (c) 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 /** @file libgcv/bot_solidity.c
21  *
22  * Functions for determining whether a BoT is solid.
23  *
24  */
25 
26 
27 #include "bot_solidity.h"
28 
29 #include <stdlib.h>
30 
31 
32 #define EDGE_EQUAL(e1, e2) (((e1).va == (e2).va) && ((e1).vb == (e2).vb))
33 
34 
35 struct halfedge {
36  int va, vb;
37  int flipped;
38 };
39 
40 
41 HIDDEN int
42 set_edge(struct halfedge *edge, int va, int vb)
43 {
44  if (va == vb)
45  return 0;
46 
47  if (va < vb) {
48  edge->va = va;
49  edge->vb = vb;
50  edge->flipped = 0;
51  } else {
52  edge->va = vb;
53  edge->vb = va;
54  edge->flipped = 1;
55  }
56 
57  return 1;
58 }
59 
60 
61 HIDDEN int
62 halfedge_compare(const void *pleft, const void *pright)
63 {
64  const struct halfedge *left = (const struct halfedge *)pleft;
65  const struct halfedge *right = (const struct halfedge *)pright;
66 
67  int a = left->va - right->va;
68  return a ? a : left->vb - right->vb;
69 }
70 
71 
72 HIDDEN struct halfedge *
73 generate_edge_list(const struct rt_bot_internal *bot)
74 {
75  const size_t num_edges = 3 * bot->num_faces;
76  struct halfedge *edge_list;
77  size_t face_index, edge_index;
78 
79  edge_list = (struct halfedge *)bu_calloc(num_edges, sizeof(struct halfedge),
80  "edge_list");
81 
82  for (face_index = 0, edge_index = 0; face_index < bot->num_faces;
83  ++face_index) {
84  const int *face = &bot->faces[face_index * 3];
85 
86  int success = set_edge(&edge_list[edge_index++], face[0], face[1])
87  && set_edge(&edge_list[edge_index++], face[1], face[2])
88  && set_edge(&edge_list[edge_index++], face[2], face[0]);
89 
90  if (!success) {
91  bu_free(edge_list, "edge_list");
92  return NULL;
93  }
94  }
95 
96  qsort(edge_list, num_edges, sizeof(struct halfedge), halfedge_compare);
97 
98  return edge_list;
99 }
100 
101 
102 int
103 gcv_bot_is_solid(const struct rt_bot_internal *bot)
104 {
105  const size_t num_edges = 3 * bot->num_faces;
106  struct halfedge *edge_list;
107  size_t i;
108 
109  if (bot->num_faces < 4 || bot->num_vertices < 4 || num_edges % 2)
110  return 0;
111 
112  if (!(edge_list = generate_edge_list(bot)))
113  return 0;
114 
115  for (i = 0; i + 1 < num_edges; i += 2) {
116  /* each edge must have two half-edges */
117  if (!EDGE_EQUAL(edge_list[i], edge_list[i + 1])) {
118  bu_free(edge_list, "edge_list");
119  return 0;
120  }
121 
122  /* adjacent half-edges must be compatibly oriented */
123  if (edge_list[i].flipped == edge_list[i + 1].flipped) {
124  bu_free(edge_list, "edge_list");
125  return 0;
126  }
127 
128  /* only two half-edges may share an edge */
129  if (i + 2 < num_edges)
130  if (EDGE_EQUAL(edge_list[i], edge_list[i + 2])) {
131  bu_free(edge_list, "edge_list");
132  return 0;
133  }
134  }
135 
136  bu_free(edge_list, "edge_list");
137  return 1;
138 }
139 
140 
141 int
142 gcv_bot_is_closed_fan(const struct rt_bot_internal *bot)
143 {
144  const size_t num_edges = 3 * bot->num_faces;
145  struct halfedge *edge_list;
146  size_t i;
147 
148  if (bot->num_faces < 4 || bot->num_vertices < 4 || num_edges % 2)
149  return 0;
150 
151  if (!(edge_list = generate_edge_list(bot)))
152  return 0;
153 
154  for (i = 0; i + 1 < num_edges; i += 2) {
155  /* each edge must have two half-edges */
156  if (!EDGE_EQUAL(edge_list[i], edge_list[i + 1])) {
157  bu_free(edge_list, "edge_list");
158  return 0;
159  }
160 
161  /* only two half-edges may share an edge */
162  if (i + 2 < num_edges)
163  if (EDGE_EQUAL(edge_list[i], edge_list[i + 2])) {
164  bu_free(edge_list, "edge_list");
165  return 0;
166  }
167  }
168 
169  bu_free(edge_list, "edge_list");
170  return 1;
171 }
172 
173 
174 int
175 gcv_bot_is_orientable(const struct rt_bot_internal *bot)
176 {
177  const size_t num_edges = 3 * bot->num_faces;
178  struct halfedge *edge_list;
179  size_t i;
180 
181  if (bot->num_faces < 4 || bot->num_vertices < 4)
182  return 0;
183 
184  if (!(edge_list = generate_edge_list(bot)))
185  return 0;
186 
187  for (i = 0; i + 1 < num_edges; i += 2) {
188  /* skip if there is no adjacent half-edge */
189  if (!EDGE_EQUAL(edge_list[i], edge_list[i + 1])) {
190  --i;
191  continue;
192  }
193 
194  /* adjacent half-edges must be compatibly oriented */
195  if (edge_list[i].flipped == edge_list[i + 1].flipped) {
196  bu_free(edge_list, "edge_list");
197  return 0;
198  }
199 
200  /* only two half-edges may share an edge */
201  if (i + 2 < num_edges)
202  if (EDGE_EQUAL(edge_list[i], edge_list[i + 2])) {
203  bu_free(edge_list, "edge_list");
204  return 0;
205  }
206  }
207 
208  bu_free(edge_list, "edge_list");
209  return 1;
210 }
211 
212 
213 /*
214  * Local Variables:
215  * tab-width: 8
216  * mode: C
217  * indent-tabs-mode: t
218  * c-file-style: "stroustrup"
219  * End:
220  * ex: shiftwidth=4 tabstop=8
221  */
int gcv_bot_is_orientable(const struct rt_bot_internal *bot)
Definition: bot_solidity.c:175
int flipped
Definition: bot_solidity.c:37
HIDDEN struct halfedge * generate_edge_list(const struct rt_bot_internal *bot)
Definition: bot_solidity.c:73
#define HIDDEN
Definition: common.h:86
void * bu_calloc(size_t nelem, size_t elsize, const char *str)
Definition: malloc.c:321
int gcv_bot_is_closed_fan(const struct rt_bot_internal *bot)
Definition: bot_solidity.c:142
int gcv_bot_is_solid(const struct rt_bot_internal *bot)
Definition: bot_solidity.c:103
HIDDEN int set_edge(struct halfedge *edge, int va, int vb)
Definition: bot_solidity.c:42
#define EDGE_EQUAL(e1, e2)
Definition: bot_solidity.c:32
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
HIDDEN int halfedge_compare(const void *pleft, const void *pright)
Definition: bot_solidity.c:62