BRL-CAD
polyclip.cpp
Go to the documentation of this file.
1 /* P O L Y C L I P . C P P
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 /** @addtogroup libged */
21 /** @{ */
22 /** @file libged/polyclip.cpp
23  *
24  * An interface to src/other/clipper.
25  *
26  */
27 /** @} */
28 
29 #include "common.h"
30 
31 #include <clipper.hpp>
32 
33 #include "ged.h"
34 
35 
36 typedef struct {
37  ClipperLib::long64 x;
38  ClipperLib::long64 y;
40 
41 struct segment_node {
42  struct bu_list l;
43  int reverse;
44  int used;
45  void *segment;
46 };
47 
48 struct contour_node {
49  struct bu_list l;
50  struct bu_list head;
51 };
52 
53 
54 static fastf_t
55 load_polygon(ClipperLib::Clipper &clipper, ClipperLib::PolyType ptype, bview_polygon *gpoly, fastf_t sf, matp_t mat)
56 {
57  register size_t j, k, n;
58  ClipperLib::Polygon curr_poly;
59  fastf_t vZ = 1.0;
60 
61  for (j = 0; j < gpoly->gp_num_contours; ++j) {
62  n = gpoly->gp_contour[j].gpc_num_points;
63  curr_poly.resize(n);
64  for (k = 0; k < n; k++) {
65  point_t vpoint;
66 
67  /* Convert to view coordinates */
68  MAT4X3PNT(vpoint, mat, gpoly->gp_contour[j].gpc_point[k]);
69  vZ = vpoint[Z];
70 
71  curr_poly[k].X = (ClipperLib::long64)(vpoint[X] * sf);
72  curr_poly[k].Y = (ClipperLib::long64)(vpoint[Y] * sf);
73  }
74 
75  try {
76  clipper.AddPolygon(curr_poly, ptype);
77  } catch (...) {
78  bu_log("Exception thrown by clipper\n");
79  }
80  }
81 
82  return vZ;
83 }
84 
85 static fastf_t
86 load_polygons(ClipperLib::Clipper &clipper, ClipperLib::PolyType ptype, bview_polygons *subj, fastf_t sf, matp_t mat)
87 {
88  register size_t i;
89  fastf_t vZ = 1.0;
90 
91  for (i = 0; i < subj->gp_num_polygons; ++i)
92  vZ = load_polygon(clipper, ptype, &subj->gp_polygon[i], sf, mat);
93 
94  return vZ;
95 }
96 
97 
98 /*
99  * Process/extract the clipper_polys into a bview_polygon.
100  */
101 static bview_polygon *
102 extract(ClipperLib::ExPolygons &clipper_polys, fastf_t sf, matp_t mat, fastf_t vZ)
103 {
104  register size_t i, j, k, n;
105  size_t num_contours = 0;
106  bview_polygon *result_poly;
107 
108  /* Count up the number of contours. */
109  for (i = 0; i < clipper_polys.size(); ++i)
110  /* Add the outer and the holes */
111  num_contours += clipper_polys[i].holes.size() + 1;
112 
113  BU_ALLOC(result_poly, bview_polygon);
114  result_poly->gp_num_contours = num_contours;
115 
116  if (num_contours < 1)
117  return result_poly;
118 
119  result_poly->gp_hole = (int *)bu_calloc(num_contours, sizeof(int), "gp_hole");
120  result_poly->gp_contour = (bview_poly_contour *)bu_calloc(num_contours, sizeof(bview_poly_contour), "gp_contour");
121 
122  n = 0;
123  for (i = 0; i < clipper_polys.size(); ++i) {
124  point_t vpoint;
125 
126  result_poly->gp_hole[n] = 0;
127  result_poly->gp_contour[n].gpc_num_points = clipper_polys[i].outer.size();
128  result_poly->gp_contour[n].gpc_point =
129  (point_t *)bu_calloc(result_poly->gp_contour[n].gpc_num_points,
130  sizeof(point_t), "gpc_point");
131 
132  for (j = 0; j < result_poly->gp_contour[n].gpc_num_points; ++j) {
133  VSET(vpoint, (fastf_t)(clipper_polys[i].outer[j].X) * sf, (fastf_t)(clipper_polys[i].outer[j].Y) * sf, vZ);
134 
135  /* Convert to model coordinates */
136  MAT4X3PNT(result_poly->gp_contour[n].gpc_point[j], mat, vpoint);
137  }
138 
139  ++n;
140  for (j = 0; j < clipper_polys[i].holes.size(); ++j) {
141  result_poly->gp_hole[n] = 1;
142  result_poly->gp_contour[n].gpc_num_points = clipper_polys[i].holes[j].size();
143  result_poly->gp_contour[n].gpc_point =
144  (point_t *)bu_calloc(result_poly->gp_contour[n].gpc_num_points,
145  sizeof(point_t), "gpc_point");
146 
147  for (k = 0; k < result_poly->gp_contour[n].gpc_num_points; ++k) {
148  VSET(vpoint, (fastf_t)(clipper_polys[i].holes[j][k].X) * sf, (fastf_t)(clipper_polys[i].holes[j][k].Y) * sf, vZ);
149 
150  /* Convert to model coordinates */
151  MAT4X3PNT(result_poly->gp_contour[n].gpc_point[k], mat, vpoint);
152  }
153 
154  ++n;
155  }
156  }
157 
158  return result_poly;
159 }
160 
161 
163 ged_clip_polygon(ClipType op, bview_polygon *subj, bview_polygon *clip, fastf_t sf, matp_t model2view, matp_t view2model)
164 {
165  fastf_t inv_sf;
166  fastf_t vZ;
167  ClipperLib::Clipper clipper;
168  ClipperLib::ExPolygons result_clipper_polys;
170 
171  /* need to scale the points up/down and then convert to/from long64 */
172  /* need a matrix to rotate into a plane */
173  /* need the inverse of the matrix above to put things back after clipping */
174 
175  /* Load subject polygon into clipper */
176  load_polygon(clipper, ClipperLib::ptSubject, subj, sf, model2view);
177 
178  /* Load clip polygon into clipper */
179  vZ = load_polygon(clipper, ClipperLib::ptClip, clip, sf, model2view);
180 
181  /* Convert op from BRL-CAD to Clipper */
182  switch (op) {
183  case gctIntersection:
184  ctOp = ClipperLib::ctIntersection;
185  break;
186  case gctUnion:
187  ctOp = ClipperLib::ctUnion;
188  break;
189  case gctDifference:
190  ctOp = ClipperLib::ctDifference;
191  break;
192  default:
193  ctOp = ClipperLib::ctXor;
194  break;
195  }
196 
197  /* Clip'em */
198  clipper.Execute(ctOp, result_clipper_polys, ClipperLib::pftEvenOdd, ClipperLib::pftEvenOdd);
199 
200  inv_sf = 1.0/sf;
201  return extract(result_clipper_polys, inv_sf, view2model, vZ);
202 }
203 
204 
206 ged_clip_polygons(ClipType op, bview_polygons *subj, bview_polygons *clip, fastf_t sf, matp_t model2view, matp_t view2model)
207 {
208  fastf_t inv_sf;
209  fastf_t vZ;
210  ClipperLib::Clipper clipper;
211  ClipperLib::ExPolygons result_clipper_polys;
213 
214  /* need to scale the points up/down and then convert to/from long64 */
215  /* need a matrix to rotate into a plane */
216  /* need the inverse of the matrix above to put things back after clipping */
217 
218  /* Load subject polygons into clipper */
219  load_polygons(clipper, ClipperLib::ptSubject, subj, sf, model2view);
220 
221  /* Load clip polygons into clipper */
222  vZ = load_polygons(clipper, ClipperLib::ptClip, clip, sf, model2view);
223 
224  /* Convert op from BRL-CAD to Clipper */
225  switch (op) {
226  case gctIntersection:
227  ctOp = ClipperLib::ctIntersection;
228  break;
229  case gctUnion:
230  ctOp = ClipperLib::ctUnion;
231  break;
232  case gctDifference:
233  ctOp = ClipperLib::ctDifference;
234  break;
235  default:
236  ctOp = ClipperLib::ctXor;
237  break;
238  }
239 
240  /* Clip'em */
241  clipper.Execute(ctOp, result_clipper_polys, ClipperLib::pftEvenOdd, ClipperLib::pftEvenOdd);
242 
243  inv_sf = 1.0/sf;
244  return extract(result_clipper_polys, inv_sf, view2model, vZ);
245 }
246 
247 
248 int
249 ged_export_polygon(struct ged *gedp, bview_data_polygon_state *gdpsp, size_t polygon_i, const char *sname)
250 {
251  register size_t j, k, n;
252  register size_t num_verts = 0;
253  struct rt_db_internal internal;
254  struct rt_sketch_internal *sketch_ip;
255  struct line_seg *lsg;
256  struct directory *dp;
257  vect_t view;
258  point_t vorigin;
259  mat_t invRot;
260 
261  GED_CHECK_EXISTS(gedp, sname, LOOKUP_QUIET, GED_ERROR);
262  RT_DB_INTERNAL_INIT(&internal);
263 
264  if (polygon_i >= gdpsp->gdps_polygons.gp_num_polygons ||
265  gdpsp->gdps_polygons.gp_polygon[polygon_i].gp_num_contours < 1)
266  return GED_ERROR;
267 
268  for (j = 0; j < gdpsp->gdps_polygons.gp_polygon[polygon_i].gp_num_contours; ++j)
269  num_verts += gdpsp->gdps_polygons.gp_polygon[polygon_i].gp_contour[j].gpc_num_points;
270 
271  if (num_verts < 3)
272  return GED_ERROR;
273 
274  internal.idb_major_type = DB5_MAJORTYPE_BRLCAD;
275  internal.idb_type = ID_SKETCH;
276  internal.idb_meth = &OBJ[ID_SKETCH];
277 
278  BU_ALLOC(internal.idb_ptr, struct rt_sketch_internal);
279  sketch_ip = (struct rt_sketch_internal *)internal.idb_ptr;
280  sketch_ip->magic = RT_SKETCH_INTERNAL_MAGIC;
281  sketch_ip->vert_count = num_verts;
282  sketch_ip->verts = (point2d_t *)bu_calloc(sketch_ip->vert_count, sizeof(point2d_t), "sketch_ip->verts");
283  sketch_ip->curve.count = num_verts;
284  sketch_ip->curve.reverse = (int *)bu_calloc(sketch_ip->curve.count, sizeof(int), "sketch_ip->curve.reverse");
285  sketch_ip->curve.segment = (void **)bu_calloc(sketch_ip->curve.count, sizeof(void *), "sketch_ip->curve.segment");
286 
287  bn_mat_inv(invRot, gdpsp->gdps_rotation);
288  VSET(view, 1.0, 0.0, 0.0);
289  MAT4X3PNT(sketch_ip->u_vec, invRot, view);
290 
291  VSET(view, 0.0, 1.0, 0.0);
292  MAT4X3PNT(sketch_ip->v_vec, invRot, view);
293 
294  /* should already be unit vectors */
295  VUNITIZE(sketch_ip->u_vec);
296  VUNITIZE(sketch_ip->v_vec);
297 
298  /* Project the origin onto the front of the viewing cube */
299  MAT4X3PNT(vorigin, gdpsp->gdps_model2view, gdpsp->gdps_origin);
300  vorigin[Z] = gdpsp->gdps_data_vZ;
301 
302  /* Convert back to model coordinates for storage */
303  MAT4X3PNT(sketch_ip->V, gdpsp->gdps_view2model, vorigin);
304 
305  n = 0;
306  for (j = 0; j < gdpsp->gdps_polygons.gp_polygon[polygon_i].gp_num_contours; ++j) {
307  size_t cstart = n;
308 
309  for (k = 0; k < gdpsp->gdps_polygons.gp_polygon[polygon_i].gp_contour[j].gpc_num_points; ++k) {
310  point_t vpt;
311  vect_t vdiff;
312 
313  MAT4X3PNT(vpt, gdpsp->gdps_model2view, gdpsp->gdps_polygons.gp_polygon[polygon_i].gp_contour[j].gpc_point[k]);
314  VSUB2(vdiff, vpt, vorigin);
315  VSCALE(vdiff, vdiff, gdpsp->gdps_scale);
316  V2MOVE(sketch_ip->verts[n], vdiff);
317 
318  if (k) {
319  BU_ALLOC(lsg, struct line_seg);
320  sketch_ip->curve.segment[n-1] = (void *)lsg;
321  lsg->magic = CURVE_LSEG_MAGIC;
322  lsg->start = n-1;
323  lsg->end = n;
324  }
325 
326  ++n;
327  }
328 
329  if (k) {
330  BU_ALLOC(lsg, struct line_seg);
331  sketch_ip->curve.segment[n-1] = (void *)lsg;
332  lsg->magic = CURVE_LSEG_MAGIC;
333  lsg->start = n-1;
334  lsg->end = cstart;
335  }
336  }
337 
338 
339  GED_DB_DIRADD(gedp, dp, sname, RT_DIR_PHONY_ADDR, 0, RT_DIR_SOLID, (void *)&internal.idb_type, GED_ERROR);
340  GED_DB_PUT_INTERNAL(gedp, dp, &internal, &rt_uniresource, GED_ERROR);
341 
342  return GED_OK;
343 }
344 
345 
347 ged_import_polygon(struct ged *gedp, const char *sname)
348 {
349  register size_t j, n;
350  register size_t ncontours = 0;
351  struct rt_db_internal intern;
352  struct rt_sketch_internal *sketch_ip;
353  struct bu_list HeadSegmentNodes;
354  struct bu_list HeadContourNodes;
355  struct segment_node *all_segment_nodes;
356  struct segment_node *curr_snode;
357  struct contour_node *curr_cnode;
358  bview_polygon *gpp;
359 
360  if (wdb_import_from_path(gedp->ged_result_str, &intern, sname, gedp->ged_wdbp) == GED_ERROR)
361  return (bview_polygon *)0;
362 
363  sketch_ip = (rt_sketch_internal *)intern.idb_ptr;
364  if (sketch_ip->vert_count < 3 || sketch_ip->curve.count < 1) {
365  rt_db_free_internal(&intern);
366  return (bview_polygon *)0;
367  }
368 
369  all_segment_nodes = (struct segment_node *)bu_calloc(sketch_ip->curve.count, sizeof(struct segment_node), "all_segment_nodes");
370 
371  BU_LIST_INIT(&HeadSegmentNodes);
372  BU_LIST_INIT(&HeadContourNodes);
373  for (n = 0; n < sketch_ip->curve.count; ++n) {
374  all_segment_nodes[n].segment = sketch_ip->curve.segment[n];
375  all_segment_nodes[n].reverse = sketch_ip->curve.reverse[n];
376  BU_LIST_INSERT(&HeadSegmentNodes, &all_segment_nodes[n].l);
377  }
378 
379  curr_cnode = (struct contour_node *)0;
380  while (BU_LIST_NON_EMPTY(&HeadSegmentNodes)) {
381  struct segment_node *unused_snode = BU_LIST_FIRST(segment_node, &HeadSegmentNodes);
382  uint32_t *magic = (uint32_t *)unused_snode->segment;
383  struct line_seg *unused_lsg;
384 
385  BU_LIST_DEQUEUE(&unused_snode->l);
386 
387  /* For the moment, skipping everything except line segments */
388  if (*magic != CURVE_LSEG_MAGIC)
389  continue;
390 
391  unused_lsg = (struct line_seg *)unused_snode->segment;
392  if (unused_snode->reverse) {
393  int tmp = unused_lsg->start;
394  unused_lsg->start = unused_lsg->end;
395  unused_lsg->end = tmp;
396  }
397 
398  /* Find a contour to add the unused segment to. */
399  for (BU_LIST_FOR(curr_cnode, contour_node, &HeadContourNodes)) {
400  for (BU_LIST_FOR(curr_snode, segment_node, &curr_cnode->head)) {
401  struct line_seg *curr_lsg = (struct line_seg *)curr_snode->segment;
402 
403  if (unused_lsg->start == curr_lsg->end) {
404  unused_snode->used = 1;
405  BU_LIST_APPEND(&curr_snode->l, &unused_snode->l);
406  goto end;
407  }
408 
409  if (unused_lsg->end == curr_lsg->start) {
410  unused_snode->used = 1;
411  BU_LIST_INSERT(&curr_snode->l, &unused_snode->l);
412  goto end;
413  }
414  }
415  }
416 
417  end:
418 
419  if (!unused_snode->used) {
420  ++ncontours;
421  BU_ALLOC(curr_cnode, struct contour_node);
422  BU_LIST_INSERT(&HeadContourNodes, &curr_cnode->l);
423  BU_LIST_INIT(&curr_cnode->head);
424  BU_LIST_INSERT(&curr_cnode->head, &unused_snode->l);
425  }
426  }
427 
428  BU_ALLOC(gpp, bview_polygon);
429  gpp->gp_num_contours = ncontours;
430  gpp->gp_hole = (int *)bu_calloc(ncontours, sizeof(int), "gp_hole");
431  gpp->gp_contour = (bview_poly_contour *)bu_calloc(ncontours, sizeof(bview_poly_contour), "gp_contour");
432 
433  j = 0;
434  while (BU_LIST_NON_EMPTY(&HeadContourNodes)) {
435  register size_t k = 0;
436  size_t npoints = 0;
437  struct line_seg *curr_lsg = NULL;
438 
439  curr_cnode = BU_LIST_FIRST(contour_node, &HeadContourNodes);
440  BU_LIST_DEQUEUE(&curr_cnode->l);
441 
442  /* Count the number of segments in this contour */
443  for (BU_LIST_FOR(curr_snode, segment_node, &curr_cnode->head))
444  ++npoints;
445 
446  gpp->gp_contour[j].gpc_num_points = npoints;
447  gpp->gp_contour[j].gpc_point = (point_t *)bu_calloc(npoints, sizeof(point_t), "gpc_point");
448 
449  while (BU_LIST_NON_EMPTY(&curr_cnode->head)) {
450  curr_snode = BU_LIST_FIRST(segment_node, &curr_cnode->head);
451  BU_LIST_DEQUEUE(&curr_snode->l);
452 
453  curr_lsg = (struct line_seg *)curr_snode->segment;
454 
455  /* Convert from UV space to model space */
456  VJOIN2(gpp->gp_contour[j].gpc_point[k], sketch_ip->V,
457  sketch_ip->verts[curr_lsg->start][0], sketch_ip->u_vec,
458  sketch_ip->verts[curr_lsg->start][1], sketch_ip->v_vec);
459  ++k;
460  }
461 
462  /* free contour node */
463  bu_free((void *)curr_cnode, "curr_cnode");
464 
465  ++j;
466  }
467 
468  /* Clean up */
469  bu_free((void *)all_segment_nodes, "all_segment_nodes");
470  rt_db_free_internal(&intern);
471 
472  return gpp;
473 }
474 
475 
476 fastf_t
477 ged_find_polygon_area(bview_polygon *gpoly, fastf_t sf, matp_t model2view, fastf_t size)
478 {
479  register size_t j, k, n;
480  ClipperLib::Polygon poly;
481  fastf_t area = 0.0;
482 
483  if (NEAR_ZERO(sf, SMALL_FASTF))
484  return 0.0;
485 
486  for (j = 0; j < gpoly->gp_num_contours; ++j) {
487  n = gpoly->gp_contour[j].gpc_num_points;
488  poly.resize(n);
489  for (k = 0; k < n; k++) {
490  point_t vpoint;
491 
492  /* Convert to view coordinates */
493  MAT4X3PNT(vpoint, model2view, gpoly->gp_contour[j].gpc_point[k]);
494 
495  poly[k].X = (ClipperLib::long64)(vpoint[X] * sf);
496  poly[k].Y = (ClipperLib::long64)(vpoint[Y] * sf);
497  }
498 
499  area += (fastf_t)ClipperLib::Area(poly);
500  }
501 
502  sf = 1.0/(sf*sf) * size * size;
503 
504  return (area * sf);
505 }
506 
507 
508 typedef struct {
510  point2d_t *pc_point;
512 
513 typedef struct {
515  int *p_hole;
517 } polygon_2d;
518 
519 
520 int
522 {
523  register size_t i, j;
524  register size_t beginA, endA, beginB, endB;
525  fastf_t tol_dist;
526  fastf_t tol_dist_sq;
527  fastf_t scale;
528  polygon_2d polyA_2d;
529  polygon_2d polyB_2d;
530  point2d_t pt_2d;
531  point_t A;
532  size_t winding = 0;
533  int ret = 0;
534 
536  GED_CHECK_VIEW(gedp, GED_ERROR);
537 
538  if (polyA->gp_num_contours < 1 || polyA->gp_contour[0].gpc_num_points < 1 ||
539  polyB->gp_num_contours < 1 || polyB->gp_contour[0].gpc_num_points < 1)
540  return 0;
541 
542  if (gedp->ged_wdbp->wdb_tol.dist > 0.0)
543  tol_dist = gedp->ged_wdbp->wdb_tol.dist;
544  else
545  tol_dist = BN_TOL_DIST;
546 
547  if (gedp->ged_wdbp->wdb_tol.dist_sq > 0.0)
548  tol_dist_sq = gedp->ged_wdbp->wdb_tol.dist_sq;
549  else
550  tol_dist_sq = tol_dist * tol_dist;
551 
552  if (gedp->ged_gvp->gv_scale > (fastf_t)UINT16_MAX)
553  scale = gedp->ged_gvp->gv_scale;
554  else
555  scale = (fastf_t)UINT16_MAX;
556 
557  /* Project polyA and polyB onto the view plane */
558  polyA_2d.p_num_contours = polyA->gp_num_contours;
559  polyA_2d.p_hole = (int *)bu_calloc(polyA->gp_num_contours, sizeof(int), "p_hole");
560  polyA_2d.p_contour = (poly_contour_2d *)bu_calloc(polyA->gp_num_contours, sizeof(poly_contour_2d), "p_contour");
561 
562  for (i = 0; i < polyA->gp_num_contours; ++i) {
563  polyA_2d.p_hole[i] = polyA->gp_hole[i];
564  polyA_2d.p_contour[i].pc_num_points = polyA->gp_contour[i].gpc_num_points;
565  polyA_2d.p_contour[i].pc_point = (point2d_t *)bu_calloc(polyA->gp_contour[i].gpc_num_points, sizeof(point2d_t), "pc_point");
566 
567  for (j = 0; j < polyA->gp_contour[i].gpc_num_points; ++j) {
568  point_t vpoint;
569 
570  MAT4X3PNT(vpoint, gedp->ged_gvp->gv_model2view, polyA->gp_contour[i].gpc_point[j]);
571  VSCALE(vpoint, vpoint, scale);
572  V2MOVE(polyA_2d.p_contour[i].pc_point[j], vpoint);
573  }
574  }
575 
576  polyB_2d.p_num_contours = polyB->gp_num_contours;
577  polyB_2d.p_hole = (int *)bu_calloc(polyB->gp_num_contours, sizeof(int), "p_hole");
578  polyB_2d.p_contour = (poly_contour_2d *)bu_calloc(polyB->gp_num_contours, sizeof(poly_contour_2d), "p_contour");
579 
580  for (i = 0; i < polyB->gp_num_contours; ++i) {
581  polyB_2d.p_hole[i] = polyB->gp_hole[i];
582  polyB_2d.p_contour[i].pc_num_points = polyB->gp_contour[i].gpc_num_points;
583  polyB_2d.p_contour[i].pc_point = (point2d_t *)bu_calloc(polyB->gp_contour[i].gpc_num_points, sizeof(point2d_t), "pc_point");
584 
585  for (j = 0; j < polyB->gp_contour[i].gpc_num_points; ++j) {
586  point_t vpoint;
587 
588  MAT4X3PNT(vpoint, gedp->ged_gvp->gv_model2view, polyB->gp_contour[i].gpc_point[j]);
589  VSCALE(vpoint, vpoint, scale);
590  V2MOVE(polyB_2d.p_contour[i].pc_point[j], vpoint);
591  }
592  }
593 
594  /*
595  * Check every line segment of polyA against every line segment of polyB.
596  * If there are any intersecting line segments, there exists an overlap.
597  */
598  for (i = 0; i < polyA_2d.p_num_contours; ++i) {
599  for (beginA = 0; beginA < polyA_2d.p_contour[i].pc_num_points; ++beginA) {
600  vect2d_t dirA;
601 
602  if (beginA == polyA_2d.p_contour[i].pc_num_points-1)
603  endA = 0;
604  else
605  endA = beginA + 1;
606 
607  V2SUB2(dirA, polyA_2d.p_contour[i].pc_point[endA], polyA_2d.p_contour[i].pc_point[beginA]);
608 
609  for (j = 0; j < polyB_2d.p_num_contours; ++j) {
610  for (beginB = 0; beginB < polyB_2d.p_contour[j].pc_num_points; ++beginB) {
611  vect2d_t distvec;
612  vect2d_t dirB;
613 
614  if (beginB == polyB_2d.p_contour[j].pc_num_points-1)
615  endB = 0;
616  else
617  endB = beginB + 1;
618 
619  V2SUB2(dirB, polyB_2d.p_contour[j].pc_point[endB], polyB_2d.p_contour[j].pc_point[beginB]);
620 
621  if (bn_isect_lseg2_lseg2(distvec,
622  polyA_2d.p_contour[i].pc_point[beginA], dirA,
623  polyB_2d.p_contour[j].pc_point[beginB], dirB,
624  &gedp->ged_wdbp->wdb_tol) == 1) {
625  /* Check to see if intersection is near an end point */
626  if (!NEAR_EQUAL(distvec[0], 0.0, tol_dist_sq) &&
627  !NEAR_EQUAL(distvec[0], 1.0, tol_dist_sq) &&
628  !NEAR_EQUAL(distvec[1], 0.0, tol_dist_sq) &&
629  !NEAR_EQUAL(distvec[1], 1.0, tol_dist_sq)) {
630  ret = 1;
631  goto end;
632  }
633  }
634  }
635  }
636  }
637  }
638 
639  for (i = 0; i < polyB_2d.p_num_contours; ++i) {
640  size_t npts_on_contour = 0;
641  size_t npts_outside = 0;
642 
643  /* Skip holes */
644  if (polyB_2d.p_hole[i])
645  continue;
646 
647  /* Check if all points in the current polygon B contour are inside A */
648  for (beginB = 0; beginB < polyB_2d.p_contour[i].pc_num_points; ++beginB) {
649  winding = 0;
650  V2MOVE(pt_2d, polyB_2d.p_contour[i].pc_point[beginB]);
651  V2MOVE(A, pt_2d);
652  A[2] = 0.0;
653 
654  for (j = 0; j < polyA_2d.p_num_contours; ++j) {
655  point_t B, C;
656  vect_t BmA, CmA;
657  vect_t vcross;
658 
659  for (beginA = 0; beginA < polyA_2d.p_contour[j].pc_num_points; ++beginA) {
660  fastf_t dot;
661 
662  if (beginA == polyA_2d.p_contour[j].pc_num_points-1)
663  endA = 0;
664  else
665  endA = beginA + 1;
666 
667  if (V2NEAR_EQUAL(polyA_2d.p_contour[j].pc_point[beginA], pt_2d, tol_dist_sq) ||
668  V2NEAR_EQUAL(polyA_2d.p_contour[j].pc_point[endA], pt_2d, tol_dist_sq)) {
669  /* pt_2d is the same as one of the end points, so count it */
670  ++npts_on_contour;
671 
672  if (polyA_2d.p_hole[j])
673  winding = 0;
674  else
675  winding = 1;
676 
677  goto endA;
678  }
679 
680  if ((polyA_2d.p_contour[j].pc_point[beginA][1] <= pt_2d[1] &&
681  polyA_2d.p_contour[j].pc_point[endA][1] > pt_2d[1])) {
682  V2MOVE(B, polyA_2d.p_contour[j].pc_point[endA]);
683  B[2] = 0.0;
684  V2MOVE(C, polyA_2d.p_contour[j].pc_point[beginA]);
685  C[2] = 0.0;
686  } else if ((polyA_2d.p_contour[j].pc_point[endA][1] <= pt_2d[1] &&
687  polyA_2d.p_contour[j].pc_point[beginA][1] > pt_2d[1])) {
688  V2MOVE(B, polyA_2d.p_contour[j].pc_point[beginA]);
689  B[2] = 0.0;
690  V2MOVE(C, polyA_2d.p_contour[j].pc_point[endA]);
691  C[2] = 0.0;
692  } else {
693  /* check if the point is on a horizontal edge */
694  if (NEAR_EQUAL(polyA_2d.p_contour[j].pc_point[beginA][1],
695  polyA_2d.p_contour[j].pc_point[endA][1], tol_dist_sq) &&
696  NEAR_EQUAL(polyA_2d.p_contour[j].pc_point[beginA][1], pt_2d[1], tol_dist_sq) &&
697  ((polyA_2d.p_contour[j].pc_point[beginA][0] <= pt_2d[0] &&
698  polyA_2d.p_contour[j].pc_point[endA][0] >= pt_2d[0]) ||
699  (polyA_2d.p_contour[j].pc_point[endA][0] <= pt_2d[0] &&
700  polyA_2d.p_contour[j].pc_point[beginA][0] >= pt_2d[0]))) {
701  ++npts_on_contour;
702 
703  if (polyA_2d.p_hole[j])
704  winding = 0;
705  else
706  winding = 1;
707 
708  goto endA;
709  }
710 
711  continue;
712  }
713 
714  VSUB2(BmA, B, A);
715  VSUB2(CmA, C, A);
716  VUNITIZE(BmA);
717  VUNITIZE(CmA);
718  dot = VDOT(BmA, CmA);
719 
720  if (NEAR_EQUAL(dot, -1.0, tol_dist_sq) || NEAR_EQUAL(dot, 1.0, tol_dist_sq)) {
721  ++npts_on_contour;
722 
723  if (polyA_2d.p_hole[j])
724  winding = 0;
725  else
726  winding = 0;
727 
728  goto endA;
729  }
730 
731  VCROSS(vcross, BmA, CmA);
732 
733  if (vcross[2] > 0)
734  ++winding;
735  }
736  }
737 
738  endA:
739  /* found a point on a polygon B contour that's outside of polygon A */
740  if (!(winding%2)) {
741  ++npts_outside;
742  if (npts_outside != npts_on_contour) {
743  break;
744  }
745  }
746  }
747 
748  /* found a B polygon contour that's completely inside polygon A */
749  if (winding%2 || (npts_outside != 0 &&
750  npts_outside != polyB_2d.p_contour[i].pc_num_points &&
751  npts_outside == npts_on_contour)) {
752  ret = 1;
753  goto end;
754  }
755  }
756 
757  for (i = 0; i < polyA_2d.p_num_contours; ++i) {
758  size_t npts_on_contour = 0;
759  size_t npts_outside = 0;
760 
761  /* Skip holes */
762  if (polyA_2d.p_hole[i])
763  continue;
764 
765  /* Check if all points in the current polygon A contour are inside B */
766  for (beginA = 0; beginA < polyA_2d.p_contour[i].pc_num_points; ++beginA) {
767  winding = 0;
768  V2MOVE(pt_2d, polyA_2d.p_contour[i].pc_point[beginA]);
769  V2MOVE(A, pt_2d);
770  A[2] = 0.0;
771 
772  for (j = 0; j < polyB_2d.p_num_contours; ++j) {
773  point_t B, C;
774  vect_t BmA, CmA;
775  vect_t vcross;
776 
777  for (beginB = 0; beginB < polyB_2d.p_contour[j].pc_num_points; ++beginB) {
778  fastf_t dot;
779 
780  if (beginB == polyB_2d.p_contour[j].pc_num_points-1)
781  endB = 0;
782  else
783  endB = beginB + 1;
784 
785  if (V2NEAR_EQUAL(polyB_2d.p_contour[j].pc_point[beginB], pt_2d, tol_dist_sq) ||
786  V2NEAR_EQUAL(polyB_2d.p_contour[j].pc_point[endB], pt_2d, tol_dist_sq)) {
787  /* pt_2d is the same as one of the end points, so count it */
788 
789  if (polyB_2d.p_hole[j])
790  winding = 0;
791  else
792  winding = 1;
793 
794  ++npts_on_contour;
795  goto endB;
796  }
797 
798  if ((polyB_2d.p_contour[j].pc_point[beginB][1] <= pt_2d[1] &&
799  polyB_2d.p_contour[j].pc_point[endB][1] > pt_2d[1])) {
800  V2MOVE(B, polyB_2d.p_contour[j].pc_point[endB]);
801  B[2] = 0.0;
802  V2MOVE(C, polyB_2d.p_contour[j].pc_point[beginB]);
803  C[2] = 0.0;
804  } else if ((polyB_2d.p_contour[j].pc_point[endB][1] <= pt_2d[1] &&
805  polyB_2d.p_contour[j].pc_point[beginB][1] > pt_2d[1])) {
806  V2MOVE(B, polyB_2d.p_contour[j].pc_point[beginB]);
807  B[2] = 0.0;
808  V2MOVE(C, polyB_2d.p_contour[j].pc_point[endB]);
809  C[2] = 0.0;
810  } else {
811  /* check if the point is on a horizontal edge */
812  if (NEAR_EQUAL(polyB_2d.p_contour[j].pc_point[beginB][1],
813  polyB_2d.p_contour[j].pc_point[endB][1], tol_dist_sq) &&
814  NEAR_EQUAL(polyB_2d.p_contour[j].pc_point[beginB][1], pt_2d[1], tol_dist_sq) &&
815  ((polyB_2d.p_contour[j].pc_point[beginB][0] <= pt_2d[0] &&
816  polyB_2d.p_contour[j].pc_point[endB][0] >= pt_2d[0]) ||
817  (polyB_2d.p_contour[j].pc_point[endB][0] <= pt_2d[0] &&
818  polyB_2d.p_contour[j].pc_point[beginB][0] >= pt_2d[0]))) {
819  if (polyB_2d.p_hole[j])
820  winding = 0;
821  else
822  winding = 1;
823 
824  ++npts_on_contour;
825 
826  goto endB;
827  }
828 
829  continue;
830  }
831 
832  VSUB2(BmA, B, A);
833  VSUB2(CmA, C, A);
834  VUNITIZE(BmA);
835  VUNITIZE(CmA);
836  dot = VDOT(BmA, CmA);
837 
838  if (NEAR_EQUAL(dot, -1.0, tol_dist_sq) || NEAR_EQUAL(dot, 1.0, tol_dist_sq)) {
839  if (polyB_2d.p_hole[j])
840  winding = 0;
841  else
842  winding = 1;
843 
844  ++npts_on_contour;
845  goto endB;
846  }
847 
848  VCROSS(vcross, BmA, CmA);
849 
850  if (vcross[2] > 0)
851  ++winding;
852  }
853  }
854 
855  endB:
856  /* found a point on a polygon A contour that's outside of polygon B */
857  if (!(winding%2)) {
858  ++npts_outside;
859  if (npts_outside != npts_on_contour) {
860  break;
861  }
862  }
863  }
864 
865  /* found an A polygon contour that's completely inside polygon B */
866  if (winding%2 || (npts_outside != 0 &&
867  npts_outside != polyA_2d.p_contour[i].pc_num_points &&
868  npts_outside == npts_on_contour)) {
869  ret = 1;
870  break;
871  } else
872  ret = 0;
873  }
874 
875 end:
876 
877  for (i = 0; i < polyA->gp_num_contours; ++i)
878  bu_free((void *)polyA_2d.p_contour[i].pc_point, "pc_point");
879  for (i = 0; i < polyB->gp_num_contours; ++i)
880  bu_free((void *)polyB_2d.p_contour[i].pc_point, "pc_point");
881 
882  bu_free((void *)polyA_2d.p_hole, "p_hole");
883  bu_free((void *)polyA_2d.p_contour, "p_contour");
884  bu_free((void *)polyB_2d.p_hole, "p_hole");
885  bu_free((void *)polyB_2d.p_contour, "p_contour");
886 
887  return ret;
888 }
889 
890 
891 /*
892  * Local Variables:
893  * tab-width: 8
894  * mode: C
895  * indent-tabs-mode: t
896  * c-file-style: "stroustrup"
897  * End:
898  * ex: shiftwidth=4 tabstop=8
899  */
#define GED_DB_DIRADD(_gedp, _dp, _name, _laddr, _len, _dirflags, _ptr, _flags)
Definition: ged.h:213
#define GED_OK
Definition: ged.h:55
#define BU_LIST_FOR(p, structure, hp)
Definition: list.h:365
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
#define BU_LIST_INSERT(old, new)
Definition: list.h:183
fastf_t C[2 *MAX_CNT+1][2 *MAX_CNT+1]
Definition: dsp_brep.cpp:38
size_t gp_num_contours
Definition: bview.h:170
Definition: list.h:118
point_t * gpc_point
Definition: bview.h:166
double dist
>= 0
Definition: tol.h:73
Definition: ged.h:338
int wdb_import_from_path(struct bu_vls *logstr, struct rt_db_internal *ip, const char *path, struct rt_wdb *wdb)
Definition: wdb.c:431
#define VSET(a, b, c, d)
Definition: color.c:53
double dist_sq
dist * dist
Definition: tol.h:74
bview_polygon * ged_import_polygon(struct ged *gedp, const char *sname)
Definition: polyclip.cpp:347
#define SMALL_FASTF
Definition: defines.h:342
size_t gp_num_polygons
Definition: bview.h:179
struct rt_wdb * ged_wdbp
Definition: ged.h:340
Header file for the BRL-CAD common definitions.
#define BU_LIST_APPEND(old, new)
Definition: list.h:197
int ged_polygons_overlap(struct ged *gedp, bview_polygon *polyA, bview_polygon *polyB)
Definition: polyclip.cpp:521
#define BU_LIST_NON_EMPTY(hp)
Definition: list.h:296
bview_polygons gdps_polygons
Definition: bview.h:199
#define GED_ERROR
Definition: ged.h:61
struct bview * ged_gvp
Definition: ged.h:361
size_t gpc_num_points
Definition: bview.h:165
#define GED_DB_PUT_INTERNAL(_gedp, _dp, _intern, _resource, _flags)
Definition: ged.h:243
if(share_geom)
Definition: nmg_mod.c:3829
int bn_isect_lseg2_lseg2(fastf_t *dist, const point_t p, const vect_t pdir, const point_t q, const vect_t qdir, const struct bn_tol *tol)
Intersect two 2D line segments, defined by two points and two vectors. The vectors are unlikely to be...
poly_contour_2d * p_contour
Definition: polyclip.cpp:516
ClipperLib::long64 y
Definition: polyclip.cpp:38
Definition: color.c:49
struct resource rt_uniresource
default. Defined in librt/globals.c
Definition: globals.c:41
#define GED_CHECK_VIEW(_gedp, _flags)
Definition: ged.h:140
#define GED_CHECK_DATABASE_OPEN(_gedp, _flags)
Definition: ged.h:114
bview_poly_contour * gp_contour
Definition: bview.h:175
int * p_hole
Definition: polyclip.cpp:515
#define BU_ALLOC(_ptr, _type)
Definition: malloc.h:223
void * bu_calloc(size_t nelem, size_t elsize, const char *str)
Definition: malloc.c:321
fastf_t gv_scale
Definition: bview.h:211
#define RT_DIR_SOLID
this name is a solid
Definition: raytrace.h:883
size_t pc_num_points
Definition: polyclip.cpp:509
#define RT_DB_INTERNAL_INIT(_p)
Definition: raytrace.h:199
#define LOOKUP_QUIET
Definition: raytrace.h:893
void bn_mat_inv(mat_t output, const mat_t input)
#define NEAR_ZERO(val, epsilon)
Definition: color.c:55
int * gp_hole
Definition: bview.h:174
bview_polygon * ged_clip_polygons(ClipType op, bview_polygons *subj, bview_polygons *clip, fastf_t sf, matp_t model2view, matp_t view2model)
Definition: polyclip.cpp:206
#define RT_DIR_PHONY_ADDR
Special marker for d_addr field.
Definition: raytrace.h:879
bview_polygon * gp_polygon
Definition: bview.h:180
#define BN_TOL_DIST
Definition: tol.h:109
oldeumate l2 magic
Definition: nmg_mod.c:3843
ClipperLib::long64 x
Definition: polyclip.cpp:37
#define GED_CHECK_EXISTS(_gedp, _name, _noisy, _flags)
Definition: ged.h:171
struct bu_vls * ged_result_str
Definition: ged.h:357
fastf_t ged_find_polygon_area(bview_polygon *gpoly, fastf_t sf, matp_t model2view, fastf_t size)
Definition: polyclip.cpp:477
struct bu_list head
Definition: polyclip.cpp:50
#define BU_LIST_INIT(_hp)
Definition: list.h:148
void * idb_ptr
Definition: raytrace.h:195
struct bn_tol wdb_tol
Definition: raytrace.h:1269
point2d_t * pc_point
Definition: polyclip.cpp:510
mat_t gv_model2view
Definition: bview.h:222
const struct rt_functab OBJ[]
Definition: table.c:159
int clip(fastf_t *, fastf_t *, fastf_t *, fastf_t *)
Definition: clip.c:66
bview_polygon * ged_clip_polygon(ClipType op, bview_polygon *subj, bview_polygon *clip, fastf_t sf, matp_t model2view, matp_t view2model)
Definition: polyclip.cpp:163
ClipType
Definition: bview.h:162
#define RT_SKETCH_INTERNAL_MAGIC
Definition: magic.h:108
size_t p_num_contours
Definition: polyclip.cpp:514
#define A
Definition: msr.c:51
Definition: color.c:51
#define idb_type
Definition: raytrace.h:198
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
struct bu_list l
Definition: polyclip.cpp:49
struct bu_list l
Definition: polyclip.cpp:42
#define BU_LIST_DEQUEUE(cur)
Definition: list.h:209
#define CURVE_LSEG_MAGIC
Definition: magic.h:199
void * segment
Definition: polyclip.cpp:45
double fastf_t
Definition: defines.h:300
int ged_export_polygon(struct ged *gedp, bview_data_polygon_state *gdpsp, size_t polygon_i, const char *sname)
Definition: polyclip.cpp:249
#define ID_SKETCH
2D sketch
Definition: raytrace.h:484
void rt_db_free_internal(struct rt_db_internal *ip)
Definition: dir.c:216
Definition: color.c:50
#define BU_LIST_FIRST(structure, hp)
Definition: list.h:312