BRL-CAD
bn_obr.c
Go to the documentation of this file.
1 /* B N _ O B R . C
2  * BRL-CAD
3  *
4  * Copyright (c) 2013-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 
21 #include "common.h"
22 
23 #include <stdlib.h>
24 #include <stdio.h>
25 #include <string.h>
26 
27 #include "bu.h"
28 #include "vmath.h"
29 #include "bn.h"
30 #include "plot3.h"
31 
32 HIDDEN
33 void plot_obr(int test_num, const point_t *pnt_array, int pnt_cnt)
34 {
35  int i = 0;
36  struct bu_vls name;
37  FILE *plot_file = NULL;
38  bu_vls_init(&name);
39  bu_vls_printf(&name, "obr_test_%.3d.pl", test_num);
40  plot_file = fopen(bu_vls_addr(&name), "w");
41  pl_color(plot_file, 0, 255, 0);
42  for (i = 0; i < pnt_cnt; i++) {
43  pdv_3move(plot_file, pnt_array[i]);
44  if (i < pnt_cnt - 1) {
45  pdv_3cont(plot_file, pnt_array[i+1]);
46  } else {
47  pdv_3cont(plot_file, pnt_array[0]);
48  }
49  }
50  fclose(plot_file);
51  bu_vls_free(&name);
52 }
53 
54 
55 int
56 main(int argc, const char **argv)
57 {
58  int i = 0;
59  int retval = 0;
60 
61  int do_plotting = 0;
62 
63  if (argc == 2 && BU_STR_EQUAL(argv[1], "-p")) do_plotting = 1;
64 
65  /* 2D input */
66  {
67  point2d_t center;
68  vect2d_t u, v;
69  point2d_t pnts[4+1] = {{0}};
70  point2d_t expected[4+1] = {{0}};
71  point2d_t output_pnts[4+1] = {{0}};
72  point_t output_3d_pnts[4+1] = {{0}};
73  int n = 4;
74 
75  V2SET(pnts[0], 1.5, 1.5);
76  V2SET(pnts[1], 3.0, 2.0);
77  V2SET(pnts[2], 2.0, 2.5);
78  V2SET(pnts[3], 1.0, 2.0);
79 
80  V2SET(expected[0], 1.2, 1.4);
81  V2SET(expected[1], 3.0, 2.0);
82  V2SET(expected[2], 2.75, 2.75);
83  V2SET(expected[3], 0.95, 2.15);
84 
85 
86  retval = bn_2d_obr(&center, &u, &v, (const point2d_t *)pnts, n);
87  if (retval) return -1;
88  V2ADD3(output_pnts[2], center, u, v);
89  V2SCALE(u, u, -1);
90  V2ADD3(output_pnts[3], center, u, v);
91  V2SCALE(v, v, -1);
92  V2ADD3(output_pnts[0], center, u, v);
93  V2SCALE(u, u, -1);
94  V2ADD3(output_pnts[1], center, u, v);
95  bu_log("Test #001: polyline_2d_hull - 4 point test:\n");
96  bu_log("bn_2d_obr: center (%f, %f)\n", V2ARGS(center));
97  bu_log(" u (%f, %f)\n", V2ARGS(u));
98  bu_log(" v (%f, %f)\n", V2ARGS(v));
99 
100  for (i = 0; i < 4; i++) {
101  bu_log(" expected[%d]: (%f, %f)\n", i, V2ARGS(expected[i]));
102  bu_log(" actual[%d]: (%f, %f)\n", i, V2ARGS(output_pnts[i]));
103  if (!NEAR_ZERO(output_pnts[i][0] - expected[i][0], VUNITIZE_TOL) ||
104  !NEAR_ZERO(output_pnts[i][1] - expected[i][1], VUNITIZE_TOL)) {
105  retval += 1;
106  }
107  }
108  if (retval) {return -1;} else {bu_log("Test #001 Passed!\n");}
109  if (do_plotting) {
110  VSET(output_3d_pnts[0], output_pnts[0][0], output_pnts[0][1], 0);
111  VSET(output_3d_pnts[1], output_pnts[1][0], output_pnts[1][1], 0);
112  VSET(output_3d_pnts[2], output_pnts[2][0], output_pnts[2][1], 0);
113  VSET(output_3d_pnts[3], output_pnts[3][0], output_pnts[3][1], 0);
114  if (do_plotting) {
115  const point_t *const_output_3d_pnts = (const point_t *)output_3d_pnts;
116  plot_obr(1, const_output_3d_pnts, 4);
117  }
118  }
119  }
120 
121  /* Triangle input */
122  {
123  point2d_t center;
124  vect2d_t u, v;
125  point2d_t pnts[3+1] = {{0}};
126  point2d_t expected[4+1] = {{0}};
127  point2d_t output_pnts[4+1] = {{0}};
128  point_t output_3d_pnts[4+1] = {{0}};
129  int n = 3;
130 
131  V2SET(pnts[0], 1.0, 0.0);
132  V2SET(pnts[1], 3.0, 0.0);
133  V2SET(pnts[2], 2.0, 4.0);
134 
135  V2SET(expected[0], 1.0, 0.0);
136  V2SET(expected[1], 3.0, 0.0);
137  V2SET(expected[2], 3.0, 4.0);
138  V2SET(expected[3], 1.0, 4.0);
139 
140 
141  retval = bn_2d_obr(&center, &u, &v, (const point2d_t *)pnts, n);
142  if (retval) return -1;
143  V2ADD3(output_pnts[2], center, u, v);
144  V2SCALE(u, u, -1);
145  V2ADD3(output_pnts[3], center, u, v);
146  V2SCALE(v, v, -1);
147  V2ADD3(output_pnts[0], center, u, v);
148  V2SCALE(u, u, -1);
149  V2ADD3(output_pnts[1], center, u, v);
150  bu_log("Test #001: polyline_2d_hull - triangle test:\n");
151  bu_log("bn_2d_obr: center (%f, %f)\n", V2ARGS(center));
152  bu_log(" u (%f, %f)\n", V2ARGS(u));
153  bu_log(" v (%f, %f)\n", V2ARGS(v));
154 
155  for (i = 0; i < 4; i++) {
156  bu_log(" expected[%d]: (%f, %f)\n", i, V2ARGS(expected[i]));
157  bu_log(" actual[%d]: (%f, %f)\n", i, V2ARGS(output_pnts[i]));
158  if (!NEAR_ZERO(output_pnts[i][0] - expected[i][0], SMALL_FASTF) ||
159  !NEAR_ZERO(output_pnts[i][1] - expected[i][1], SMALL_FASTF)) {
160  retval += 1;
161  }
162  }
163  if (do_plotting) {
164  VSET(output_3d_pnts[0], output_pnts[0][0], output_pnts[0][1], 0);
165  VSET(output_3d_pnts[1], output_pnts[1][0], output_pnts[1][1], 0);
166  VSET(output_3d_pnts[2], output_pnts[2][0], output_pnts[2][1], 0);
167  VSET(output_3d_pnts[3], output_pnts[3][0], output_pnts[3][1], 0);
168  if (do_plotting) {
169  const point_t *const_output_3d_pnts = (const point_t *)output_3d_pnts;
170  plot_obr(8, const_output_3d_pnts, 4);
171  }
172  }
173  if (retval) {return -1;} else {bu_log("Triangle Test Passed!\n");}
174  }
175 
176 
177  /* 3D input */
178  {
179  point_t center;
180  vect_t u, v;
181  point_t output_pnts[4+1] = {{0}};
182  point_t test2_points[17+1] = {{0}};
183  point_t expected[4+1] = {{0}};
184  VSET(test2_points[0], -0.5, 0.5, 0.5);
185  VSET(test2_points[1], 0.5, -0.5, 0.5);
186  VSET(test2_points[2], 0.5, 0.5, 0.5);
187  VSET(test2_points[3], -0.5, -0.5, 0.5);
188  VSET(test2_points[4], 0.5, 0.5, 0.5);
189  VSET(test2_points[5], -0.5, -0.5, 0.5);
190  VSET(test2_points[6], -0.5, 0.5, 0.5);
191  VSET(test2_points[7], 0.5, -0.5, 0.5);
192  VSET(test2_points[8], 0.1666666666666666574148081, 0.1666666666666666574148081, 0.5);
193  VSET(test2_points[9], -0.1666666666666666574148081, -0.1666666666666666574148081, 0.5);
194  VSET(test2_points[10], -0.3888888888888888950567946, -0.05555555555555555247160271, 0.5);
195  VSET(test2_points[11], -0.3518518518518518600757261, 0.09259259259259258745267118, 0.5);
196  VSET(test2_points[12], -0.4629629629629629095077803, -0.01851851851851851749053424, 0.5);
197  VSET(test2_points[13], 0.05555555555555555247160271, 0.3888888888888888950567946, 0.5);
198  VSET(test2_points[14], 0.3888888888888888950567946, 0.05555555555555555247160271, 0.5);
199  VSET(test2_points[15], 0.3518518518518518600757261, 0.2407407407407407273769451, 0.5);
200  VSET(test2_points[16], -0.05555555555555555247160271, -0.05555555555555555247160271, 0.5);
201  VSET(expected[0], 0.5, 0.5, 0.5);
202  VSET(expected[1], 0.5, -0.5, 0.5);
203  VSET(expected[2], -0.5, -0.5, 0.5);
204  VSET(expected[3], -0.5, 0.5, 0.5);
205  retval = bn_3d_coplanar_obr(&center, &u, &v, (const point_t *)test2_points, 17);
206  if (retval) return -1;
207  VADD3(output_pnts[2], center, u, v);
208  VSCALE(u, u, -1);
209  VADD3(output_pnts[3], center, u, v);
210  VSCALE(v, v, -1);
211  VADD3(output_pnts[0], center, u, v);
212  VSCALE(u, u, -1);
213  VADD3(output_pnts[1], center, u, v);
214  bu_log("Test #002: 3d obr - points in XY plane at Z=0.5, duplicate points:\n");
215  for (i = 0; i < 4; i++) {
216  bu_log(" expected[%d]: (%f, %f, %f)\n", i, V3ARGS(expected[i]));
217  bu_log(" actual[%d]: (%f, %f, %f)\n", i, V3ARGS(output_pnts[i]));
218  if (!NEAR_ZERO(output_pnts[i][0] - expected[i][0], VUNITIZE_TOL) ||
219  !NEAR_ZERO(output_pnts[i][1] - expected[i][1], VUNITIZE_TOL) ||
220  !NEAR_ZERO(output_pnts[i][2] - expected[i][2], VUNITIZE_TOL)) {
221  retval += 1;
222  }
223  }
224  if (retval) {return -1;} else {bu_log("Test #002 Passed!\n");}
225  if (do_plotting) {
226  const point_t *const_output_pnts = (const point_t *)output_pnts;
227  plot_obr(2, const_output_pnts, 4);
228  }
229 
230  }
231 
232  {
233  point_t center;
234  vect_t u, v;
235  point_t output_pnts[4+1] = {{0}};
236  point_t test3_points[17+1] = {{0}};
237  point_t expected[4+1] = {{0}};
238 
239  VSET(test3_points[0],-0.2615997126297299746333636,0.9692719821506950994560725,1.113297221058902053414386);
240  VSET(test3_points[1],-0.6960082873702697625617475,-0.3376479821506951362053428,0.791972778941099408989146);
241  VSET(test3_points[2],0.08930731496876459507561208,0.2282231541335035251982788,0.5408368359872989250547448);
242  VSET(test3_points[3],-1.046915314968769772363544,0.4034008458664972707197194,1.364433164012702537348787);
243  VSET(test3_points[4],0.08930731496876459507561208,0.2282231541335035251982788,0.5408368359872989250547448);
244  VSET(test3_points[5],-1.046915314968769772363544,0.4034008458664972707197194,1.364433164012702537348787);
245  VSET(test3_points[6],-0.2615997126297299746333636,0.9692719821506950994560725,1.113297221058902053414386);
246  VSET(test3_points[7],-0.6960082873702697625617475,-0.3376479821506951362053428,0.791972778941099408989146);
247  VSET(test3_points[8],-0.2894335616770786212548217,0.2866157180445003671565019,0.8153689453291005362345345);
248  VSET(test3_points[9],-0.6681744383229220041187091,0.3450082819554983748489008,1.089901054670902258436627);
249  VSET(test3_points[10],-0.6588964886404735654679143,0.5725603699908965449338893,1.189210479914168061554847);
250  VSET(test3_points[11],-0.5295568798643752739252477,0.628946878032363931865234,1.13080291854799019901634);
251  VSET(test3_points[12],-0.6558038387463227536500199,0.6484110660026961570068238,1.222313621661925475692101);
252  VSET(test3_points[13],-0.1539086531126804824332055,0.4947036181095669227225642,0.823167667458433838234555);
253  VSET(test3_points[14],-0.2987115113595283921732459,0.05906363000910182931013637,0.7160595200858336228932899);
254  VSET(test3_points[15],-0.1662792526892814537475829,0.1913008340623683078973727,0.6907551004674108430236856);
255  VSET(test3_points[16],-0.5419274794409739692824246,0.3255440939851655945957987,0.9983903515569694242515197);
256  VSET(expected[0], 0.089307314968765, 0.228223154133504, 0.540836835987299);
257  VSET(expected[1], -0.696008287370264, -0.337647982150691, 0.791972778941097);
258  VSET(expected[2], -1.046915314968751, 0.403400845866492, 1.364433164012691);
259  VSET(expected[3], -0.261599712629723, 0.969271982150686, 1.113297221058893);
260 
261  retval = bn_3d_coplanar_obr(&center, &u, &v, (const point_t *)test3_points, 17);
262  if (retval) return -1;
263  VADD3(output_pnts[2], center, u, v);
264  VSCALE(u, u, -1);
265  VADD3(output_pnts[3], center, u, v);
266  VSCALE(v, v, -1);
267  VADD3(output_pnts[0], center, u, v);
268  VSCALE(u, u, -1);
269  VADD3(output_pnts[1], center, u, v);
270  bu_log("Test #003: 3d obr - points in tilted plane, duplicate points:\n");
271  for (i = 0; i < 4; i++) {
272  bu_log(" expected[%d]: (%.15f, %.15f, %.15f)\n", i, V3ARGS(expected[i]));
273  bu_log(" actual[%d]: (%.15f, %.15f, %.15f)\n", i, V3ARGS(output_pnts[i]));
274  if (!NEAR_ZERO(output_pnts[i][0] - expected[i][0], VUNITIZE_TOL) ||
275  !NEAR_ZERO(output_pnts[i][1] - expected[i][1], VUNITIZE_TOL) ||
276  !NEAR_ZERO(output_pnts[i][2] - expected[i][2], VUNITIZE_TOL)) {
277  retval += 1;
278  }
279  }
280  if (retval) {return -1;} else {bu_log("Test #003 Passed!\n");}
281  if (do_plotting) {
282  const point_t *const_output_pnts = (const point_t *)output_pnts;
283  plot_obr(3, const_output_pnts, 4);
284  }
285 
286 
287  }
288 
289  {
290  point_t center;
291  vect_t u, v;
292  point_t output_pnts[4+1] = {{0}};
293  point_t test4_points[9+1] = {{0}};
294  point_t expected[4+1] = {{0}};
295 
296  VSET(test4_points[0],-0.2894335616770786212548217,0.2866157180445003671565019,0.8153689453291005362345345);
297  VSET(test4_points[1],-0.6681744383229220041187091,0.3450082819554983748489008,1.089901054670902258436627);
298  VSET(test4_points[2],-0.6588964886404735654679143,0.5725603699908965449338893,1.189210479914168061554847);
299  VSET(test4_points[3],-0.5295568798643752739252477,0.628946878032363931865234,1.13080291854799019901634);
300  VSET(test4_points[4],-0.6558038387463227536500199,0.6484110660026961570068238,1.222313621661925475692101);
301  VSET(test4_points[5],-0.1539086531126804824332055,0.4947036181095669227225642,0.823167667458433838234555);
302  VSET(test4_points[6],-0.2987115113595283921732459,0.05906363000910182931013637,0.7160595200858336228932899);
303  VSET(test4_points[7],-0.1662792526892814537475829,0.1913008340623683078973727,0.6907551004674108430236856);
304  VSET(test4_points[8],-0.5419274794409739692824246,0.3255440939851655945957987,0.9983903515569694242515197);
305  VSET(expected[0], -0.804068848240491, 0.450183326349575, 1.227405986932079);
306  VSET(expected[1], -0.277478009809908, 0.042630029322528, 0.694574374420025);
307  VSET(expected[2], -0.018014243195113, 0.389528573715492, 0.685662735197256);
308  VSET(expected[3], -0.544605081625695, 0.797081870742539, 1.218494347709310);
309 
310  retval = bn_3d_coplanar_obr(&center, &u, &v, (const point_t *)test4_points, 9);
311  if (retval) return -1;
312  VADD3(output_pnts[2], center, u, v);
313  VSCALE(u, u, -1);
314  VADD3(output_pnts[3], center, u, v);
315  VSCALE(v, v, -1);
316  VADD3(output_pnts[0], center, u, v);
317  VSCALE(u, u, -1);
318  VADD3(output_pnts[1], center, u, v);
319  bu_log("Test #004: 3d obr - points from test 4 sans square corners, no duplicate points:\n");
320  for (i = 0; i < 4; i++) {
321  bu_log(" expected[%d]: (%.15f, %.15f, %.15f)\n", i, V3ARGS(expected[i]));
322  bu_log(" actual[%d]: (%.15f, %.15f, %.15f)\n", i, V3ARGS(output_pnts[i]));
323  if (!NEAR_ZERO(output_pnts[i][0] - expected[i][0], VUNITIZE_TOL) ||
324  !NEAR_ZERO(output_pnts[i][1] - expected[i][1], VUNITIZE_TOL) ||
325  !NEAR_ZERO(output_pnts[i][2] - expected[i][2], VUNITIZE_TOL)) {
326  retval += 1;
327  }
328  }
329  if (retval) {return -1;} else {bu_log("Test #004 Passed!\n");}
330  if (do_plotting) {
331  const point_t *const_output_pnts = (const point_t *)output_pnts;
332  plot_obr(4, const_output_pnts, 4);
333  }
334 
335  }
336 
337 
338  return 0;
339 }
340 
341 
342 /** @} */
343 /*
344  * Local Variables:
345  * mode: C
346  * tab-width: 8
347  * indent-tabs-mode: t
348  * c-file-style: "stroustrup"
349  * End:
350  * ex: shiftwidth=4 tabstop=8
351  */
void bu_vls_init(struct bu_vls *vp)
Definition: vls.c:56
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
HIDDEN void plot_obr(int test_num, const point_t *pnt_array, int pnt_cnt)
Definition: bn_obr.c:33
void pdv_3move(register FILE *plotfp, const fastf_t *pt)
Definition: plot3.c:618
#define VSET(a, b, c, d)
Definition: color.c:53
#define SMALL_FASTF
Definition: defines.h:342
Header file for the BRL-CAD common definitions.
int bn_3d_coplanar_obr(point_t *center, vect_t *v1, vect_t *v2, const point_t *points_3d, int pnt_cnt)
Uses the Rotating Calipers algorithm to find the minimum oriented bounding rectangle for a set of cop...
Definition: obr.c:496
#define HIDDEN
Definition: common.h:86
void bu_vls_free(struct bu_vls *vp)
Definition: vls.c:248
int bn_2d_obr(point2d_t *center, vect2d_t *u, vect2d_t *v, const point2d_t *points_2d, int pnt_cnt)
Routines for the computation of oriented bounding rectangles 2D and 3D.
Definition: obr.c:470
#define V3ARGS(a)
Definition: color.c:56
#define NEAR_ZERO(val, epsilon)
Definition: color.c:55
void pdv_3cont(register FILE *plotfp, const fastf_t *pt)
Definition: plot3.c:630
char * bu_vls_addr(const struct bu_vls *vp)
Definition: vls.c:111
void pl_color(register FILE *plotfp, int r, int g, int b)
Definition: plot3.c:325
int main(int argc, const char **argv)
Definition: bn_obr.c:56
void bu_vls_printf(struct bu_vls *vls, const char *fmt,...) _BU_ATTR_PRINTF23
Definition: vls.c:694
Definition: vls.h:56
#define BU_STR_EQUAL(s1, s2)
Definition: str.h:126