BRL-CAD
tri_face.c
Go to the documentation of this file.
1 /* T R I _ F A C E . C
2  * BRL-CAD
3  *
4  * Copyright (c) 2011-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 tri_face.c
21  *
22  * Implements triangulateFace routine for triangulating convex/concave planar
23  * N-gons. Uses nmg for triangulation, but accepts and returns simple arrays.
24  *
25  */
26 
27 #include "common.h"
28 
29 #include "bu/malloc.h"
30 #include "nmg.h"
31 #include "raytrace.h"
32 
33 static const int VERTICES_PER_FACE = 3;
34 
35 /* nmg access routines */
36 
37 HIDDEN struct shell*
38 get_first_shell(struct model *model)
39 {
40  struct nmgregion *region;
41  struct shell *shell;
42 
43  region = BU_LIST_FIRST(nmgregion, &model->r_hd);
44  shell = BU_LIST_FIRST(shell, &region->s_hd);
45 
46  return shell;
47 }
48 
49 HIDDEN struct model*
50 get_faceuse_model(struct faceuse *fu)
51 {
52  return fu->s_p->r_p->m_p;
53 }
54 
55 /* nmg construction routines */
56 
57 HIDDEN struct vertex_g*
58 make_nmg_vertex_g(struct model *model, double x, double y, double z, long index)
59 {
60  struct vertex_g *vg;
61 
62  GET_VERTEX_G(vg, model);
63  vg->magic = NMG_VERTEX_G_MAGIC;
64 
65  VSET(vg->coord, x, y, z);
66  vg->index = index;
67 
68  return vg;
69 }
70 
71 HIDDEN struct vertex*
72 make_nmg_vertex(struct model *model, double x, double y, double z, long index)
73 {
74  struct vertex *v;
75 
76  GET_VERTEX(v, model);
77  v->magic = NMG_VERTEX_MAGIC;
78 
79  BU_LIST_INIT(&v->vu_hd);
80  v->vg_p = make_nmg_vertex_g(model, x, y, z, index);
81  v->index = index;
82 
83  return v;
84 }
85 
86 HIDDEN void
87 attach_face_g_plane(struct model *model, struct face *f)
88 {
89  struct face_g_plane *plane;
90 
91  GET_FACE_G_PLANE(plane, model);
92  plane->magic = NMG_FACE_G_PLANE_MAGIC;
93 
94  /* link up and down */
95  BU_LIST_INIT(&plane->f_hd);
96  BU_LIST_PUSH(&plane->f_hd, &f->l);
97 
98  f->g.plane_p = plane;
99 }
100 
101 /* builds an nmg model containing a single faceuse which represents the face
102  * specified in points[]
103  */
104 HIDDEN struct model*
105 make_model_from_face(const double points[], int numPoints)
106 {
107  int i;
108  struct model *model;
109  struct shell *shell;
110  struct faceuse *fu;
111  struct vertex **verts;
112  const double *p;
113 
114  /* make base nmg model */
115  model = nmg_mm();
116  nmg_mrsv(model);
117 
118  /* copy each point into vertex to create verts array */
119  verts = (struct vertex**)bu_malloc(sizeof(struct vertex*) * numPoints,
120  "verts");
121 
122  for (i = 0; i < numPoints; i++) {
123  p = &points[i * ELEMENTS_PER_POINT];
124  verts[i] = make_nmg_vertex(model, p[X], p[Y], p[Z], (long)i);
125  }
126 
127  /* add face from verts */
128  shell = get_first_shell(model);
129  nmg_cface(shell, verts, numPoints);
130  bu_free(verts, "verts");
131 
132  /* add geometry to face */
133  fu = BU_LIST_FIRST(faceuse, &shell->fu_hd);
134  attach_face_g_plane(model, fu->f_p);
135  if (nmg_calc_face_plane(fu, fu->f_p->g.plane_p->N)) {
136  nmg_km(model);
137  model = NULL;
138  } else {
139  fu->orientation = OT_SAME;
140  }
141 
142  return model;
143 }
144 
145 struct faceuse*
146 make_faceuse_from_face(const double points[], int numPoints)
147 {
148  struct model *model;
149  struct shell *shell;
150  struct faceuse *fu = NULL;
151 
152  model = make_model_from_face(points, numPoints);
153 
154  if (model != NULL) {
155  shell = get_first_shell(model);
156  fu = BU_LIST_FIRST(faceuse, &shell->fu_hd);
157  }
158 
159  return fu;
160 }
161 
162 /* triangulation routines */
163 
164 /* Searches points[] for the specified point. Match is determined using the
165  * specified distance tolerance.
166  *
167  * If match is found, returns the point number (starting at 0) of the match.
168  * Otherwise returns -1.
169  */
170 HIDDEN int
172  const double point[],
173  const double points[],
174  size_t numPoints,
175  double tol)
176 {
177  size_t i;
178  const double *currPoint;
179 
180  for (i = 0; i < numPoints; ++i) {
181  currPoint = &points[i * ELEMENTS_PER_POINT];
182 
183  if (VNEAR_EQUAL(currPoint, point, tol)) {
184  return i;
185  }
186  }
187 
188  return -1;
189 }
190 
191 /* points is the specification of face points. It should contain consecutive
192  * three-coordinate vertices that specify a planar N-gon in CCW/CW order.
193  *
194  * faces will specify numFaces triangle faces with three consecutive vertex
195  * references per face. Vertex reference v refers to the three consecutive
196  * coordinates starting at points[v * ELEMENTS_PER_VERTEX].
197  */
198 void
200  int **faces,
201  size_t *numFaces,
202  const double points[],
203  size_t numPoints,
204  struct bn_tol tol)
205 {
206  struct model *model;
207  struct faceuse *fu;
208  struct loopuse *lu;
209  struct edgeuse *eu;
210  size_t numFaceVertices;
211  int i, ref;
212  double point[3];
213 
214  /* get nmg faceuse that represents the face specified by points */
215  fu = make_faceuse_from_face(points, numPoints);
216 
217  if (fu == NULL) {
218  *faces = NULL;
219  *numFaces = 0;
220  return;
221  }
222 
223  /* triangulate face */
224  if (nmg_triangulate_fu(fu, &tol)) {
225  *faces = NULL;
226  *numFaces = 0;
227  return;
228  }
229 
230  /* face now composed of triangular loops */
231  *numFaces = 0;
232  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
233  (*numFaces)++;
234  }
235 
236  /* create faces array */
237  numFaceVertices = *numFaces * VERTICES_PER_FACE;
238  *faces = (int*)bu_malloc(numFaceVertices * sizeof(int), "faces");
239 
240  i = 0;
241  for (BU_LIST_FOR(lu, loopuse, &fu->lu_hd)) {
242  for (BU_LIST_FOR(eu, edgeuse, &lu->down_hd)) {
243  VMOVE(point, eu->vu_p->v_p->vg_p->coord);
244  ref = getPointReference(point, points, numPoints, tol.dist);
245  (*faces)[i++] = ref;
246  }
247  }
248 
249  model = get_faceuse_model(fu);
250  nmg_km(model);
251 }
252 
253 
254 /*
255  * Local Variables:
256  * tab-width: 8
257  * mode: C
258  * indent-tabs-mode: t
259  * c-file-style: "stroustrup"
260  * End:
261  * ex: shiftwidth=4 tabstop=8
262  */
HIDDEN struct vertex_g * make_nmg_vertex_g(struct model *model, double x, double y, double z, long index)
Definition: tri_face.c:58
#define BU_LIST_FOR(p, structure, hp)
Definition: list.h:365
int nmg_calc_face_plane(struct faceuse *fu_in, fastf_t *pl)
Definition: nmg_misc.c:1557
struct faceuse * nmg_cface(struct shell *s, struct vertex **verts, int n)
Definition: nmg_mod.c:1130
double dist
>= 0
Definition: tol.h:73
#define NMG_VERTEX_MAGIC
Definition: magic.h:147
lu
Definition: nmg_mod.c:3855
#define VSET(a, b, c, d)
Definition: color.c:53
Header file for the BRL-CAD common definitions.
void triangulateFace(int **faces, size_t *numFaces, const double points[], size_t numPoints, struct bn_tol tol)
Definition: tri_face.c:199
struct faceuse * make_faceuse_from_face(const double points[], int numPoints)
Definition: tri_face.c:146
#define HIDDEN
Definition: common.h:86
HIDDEN void attach_face_g_plane(struct model *model, struct face *f)
Definition: tri_face.c:87
void * bu_malloc(size_t siz, const char *str)
Definition: malloc.c:314
Definition: color.c:49
void nmg_km(struct model *m)
Definition: nmg_mk.c:1634
int nmg_triangulate_fu(struct faceuse *fu, const struct bn_tol *tol)
Definition: nmg_tri.c:3327
Coord * point
Definition: chull3d.cpp:52
Support for uniform tolerances.
Definition: tol.h:71
struct nmgregion * nmg_mrsv(struct model *m)
Definition: nmg_mk.c:306
#define NMG_FACE_G_PLANE_MAGIC
Definition: magic.h:125
#define BU_LIST_PUSH(hp, p)
Definition: list.h:246
struct model * nmg_mm(void)
Definition: nmg_mk.c:235
#define BU_LIST_INIT(_hp)
Definition: list.h:148
HIDDEN int getPointReference(const double point[], const double points[], size_t numPoints, double tol)
Definition: tri_face.c:171
HIDDEN struct vertex * make_nmg_vertex(struct model *model, double x, double y, double z, long index)
Definition: tri_face.c:72
HIDDEN struct shell * get_first_shell(struct model *model)
Definition: tri_face.c:38
Definition: color.c:51
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
#define NMG_VERTEX_G_MAGIC
Definition: magic.h:146
HIDDEN struct model * get_faceuse_model(struct faceuse *fu)
Definition: tri_face.c:50
Definition: color.c:50
#define BU_LIST_FIRST(structure, hp)
Definition: list.h:312
HIDDEN struct model * make_model_from_face(const double points[], int numPoints)
Definition: tri_face.c:105