Revision: 76839
http://sourceforge.net/p/brlcad/code/76839
Author: starseeker
Date: 2020-08-19 00:59:34 +0000 (Wed, 19 Aug 2020)
Log Message:
-----------
Strip out disable/incomplete code from the CDT implementation. VCS has it if
an opportunity to revisit it appears.
Modified Paths:
--------------
brlcad/trunk/doc/legal/embedded/CMakeLists.txt
brlcad/trunk/include/bg/trimesh.h
brlcad/trunk/include/brep/CMakeLists.txt
brlcad/trunk/src/libbg/CMakeLists.txt
brlcad/trunk/src/libbg/tests/CMakeLists.txt
brlcad/trunk/src/libbrep/CMakeLists.txt
brlcad/trunk/src/libbrep/cdt/tri_isect.cpp
brlcad/trunk/src/libbrep/cdt/util.cpp
Removed Paths:
-------------
brlcad/trunk/doc/legal/embedded/point_in_polyhedron.txt
brlcad/trunk/include/brep/cdt2.h
brlcad/trunk/src/libbg/tests/trimesh_pt_in.c
brlcad/trunk/src/libbg/trimesh_pt_in.c
brlcad/trunk/src/libbrep/cdt/omesh.cpp
brlcad/trunk/src/libbrep/cdt/overt.cpp
brlcad/trunk/src/libbrep/cdt/ovlps.cpp
brlcad/trunk/src/libbrep/cdt/ovlps_grps.cpp
brlcad/trunk/src/libbrep/cdt2/
Modified: brlcad/trunk/doc/legal/embedded/CMakeLists.txt
===================================================================
--- brlcad/trunk/doc/legal/embedded/CMakeLists.txt 2020-08-19 00:37:19 UTC
(rev 76838)
+++ brlcad/trunk/doc/legal/embedded/CMakeLists.txt 2020-08-19 00:59:34 UTC
(rev 76839)
@@ -45,7 +45,6 @@
ParaView.txt
pbrt.txt
point_in_polygon.txt
- point_in_polyhedron.txt
polygonizer.txt
pstdint.txt
qsort.txt
Deleted: brlcad/trunk/doc/legal/embedded/point_in_polyhedron.txt
===================================================================
--- brlcad/trunk/doc/legal/embedded/point_in_polyhedron.txt 2020-08-19
00:37:19 UTC (rev 76838)
+++ brlcad/trunk/doc/legal/embedded/point_in_polyhedron.txt 2020-08-19
00:59:34 UTC (rev 76839)
@@ -1,35 +0,0 @@
-Original python implementation from
-https://github.com/mdickinson/polyhedron
-
-BSD 3-Clause License
-
-Copyright (c) 2019, Mark Dickinson
-All rights reserved.
-
-Redistribution and use in source and binary forms, with or without
-modification, are permitted provided that the following conditions are met:
-
-1. Redistributions of source code must retain the above copyright notice, this
- list of conditions and the following disclaimer.
-
-2. Redistributions in binary form must reproduce the above copyright notice,
- this list of conditions and the following disclaimer in the documentation
- and/or other materials provided with the distribution.
-
-3. Neither the name of the copyright holder nor the names of its
- contributors may be used to endorse or promote products derived from
- this software without specific prior written permission.
-
-THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
-AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
-IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
-FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-
-file:/src/libbg/trimesh_pt_in.c
-
Modified: brlcad/trunk/include/bg/trimesh.h
===================================================================
--- brlcad/trunk/include/bg/trimesh.h 2020-08-19 00:37:19 UTC (rev 76838)
+++ brlcad/trunk/include/bg/trimesh.h 2020-08-19 00:59:34 UTC (rev 76839)
@@ -172,22 +172,6 @@
const int *ifaces, int n_ifaces, const point_t *ipnts);
-/**
- * @brief
- * Low level per-face contribution to inside/outside test, used if
- * calling codes prefer to construct their own test with their own
- * mesh containers.
- */
-BG_EXPORT int
-bg_ptm_triangle_chain(point_t v1, point_t v2, point_t v3, point_t tp, int
*exact_flag);
-
-/**
- * @brief
- * Report if point tp is inside or outside of the trimesh.
- */
-BG_EXPORT int
-bg_trimesh_pt_in(point_t tp, int num_faces, int *faces, int num_vertices,
point_t *pts);
-
__END_DECLS
#endif /* BG_TRIMESH_H */
Modified: brlcad/trunk/include/brep/CMakeLists.txt
===================================================================
--- brlcad/trunk/include/brep/CMakeLists.txt 2020-08-19 00:37:19 UTC (rev
76838)
+++ brlcad/trunk/include/brep/CMakeLists.txt 2020-08-19 00:59:34 UTC (rev
76839)
@@ -15,7 +15,6 @@
BRLCAD_MANAGE_FILES(brep_headers ${INCLUDE_DIR}/brlcad/brep)
CMAKEFILES(CMakeLists.txt)
-CMAKEFILES(cdt2.h)
# Local Variables:
# tab-width: 8
Deleted: brlcad/trunk/include/brep/cdt2.h
===================================================================
--- brlcad/trunk/include/brep/cdt2.h 2020-08-19 00:37:19 UTC (rev 76838)
+++ brlcad/trunk/include/brep/cdt2.h 2020-08-19 00:59:34 UTC (rev 76839)
@@ -1,148 +0,0 @@
-/* C D T . H
- * BRL-CAD
- *
- * Copyright (c) 2004-2020 United States Government as represented by
- * the U.S. Army Research Laboratory.
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public License
- * version 2.1 as published by the Free Software Foundation.
- *
- * This library is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this file; see the file named COPYING for more
- * information.
- */
-/** @{ */
-/** @file brep/cdt.h */
-/** @addtogroup brep_util
- *
- * @brief
- * Constrained Delaunay Triangulation of brep solids.
- *
- */
-
-#ifndef BREP_CDT_H
-#define BREP_CDT_H
-
-#include "common.h"
-
-#include "bg/defines.h"
-#include "brep/defines.h"
-
-__BEGIN_DECLS
-
-/* Container that holds the state of a triangulation */
-struct brep_cdt_impl;
-struct brep_cdt {
- struct brep_cdt_impl *i;
- struct bu_vls *msgs;
-};
-
-/* Create and initialize a CDT state with default tolerances. bv
- * must be a pointer to an ON_Brep object. */
-extern BREP_EXPORT int
-brep_cdt_create(struct brep_cdt **cdt, void *bv, const char *objname);
-
-/* Destroy a CDT state */
-extern BREP_EXPORT void
-brep_cdt_destroy(struct brep_cdt *s);
-
-extern BREP_EXPORT const char *
-brep_cdt_objname(struct brep_cdt *s);
-
-/* Set/get the CDT tolerances. */
-extern BREP_EXPORT void
-brep_cdt_tol_set(struct brep_cdt *s, const struct bg_tess_tol *t);
-extern BREP_EXPORT void
-brep_cdt_tol_get(struct bg_tess_tol *t, const struct brep_cdt *s);
-
-/* Return a pointer to the ON_Brep associated with state s. */
-extern BREP_EXPORT void *
-brep_cdt_brep_get(struct brep_cdt *s);
-
-/* Given a state, produce a triangulation. Returns 0 if a solid, valid
- * triangulation was produced, 1 if a triangulation was produced but it
- * isn't solid, and -1 if no triangulation could be produced. If faces is
- * non-null, the triangulation will only attempt to triangulate the
- * specified face(s) and the return code will be the number of successfully
- * triangulated faces. If the CDT tolerances have been updated since the
- * last Tessellate call, the old tessellation information will be replaced. */
-extern BREP_EXPORT int
-brep_cdt_triangulate(struct brep_cdt *s, int face_cnt, int *faces, long flags);
-
-/* The default triangulation attempts to satisfy a number of mesh quality
constraints,
- * which slows the triangulation process. The following flags allow the
caller to
- * disable them to trade off increased speed for lower quality mesh outputs */
-#define BG_CDT_NO_WATERTIGHT 0x1 /**< @brief Disable watertight
meshing. */
-#define BG_CDT_NO_EDGE_OPTIMIZE 0x2 /**< @brief Disable distortion
correction near face edges. */
-#define BG_CDT_NO_VALIDITY 0x4 /**< @brief Disable triangle validity
checking. */
-
-/* Given a state, report the status of its triangulation. -4 indicate an
- * unsuitable ON_Brep is present, -3 indicates a failed attempt on a
- * theoretically usable ON_Brep, -2 indicates a non-solid result is present
- * after an attempt to process all faces, -1 indicates a state which no attempt
- * has been made, 0 indicates a solid, valid full brep triangulation is
- * present, and >0 indicates the number of faces has been triangulated short of
- * processing the full brep, in case a partial list had been supplied to
- * brep_cdt_triangulate. */
-extern BREP_EXPORT int
-brep_cdt_status(struct brep_cdt *s);
-
-/* Construct a vlist plot from the triangulation. Modes are:
- *
- * 0 - shaded 3D triangles
- * 1 - 3D triangle wireframe
- * 2 - 2D triangle wireframe (from parametric space)
- *
- * Returns 0 if vlist was successfully generated, else -1
- */
-extern BREP_EXPORT int
-brep_cdt_vlist(
- struct bn_vlblock *vbp,
- struct bu_list *vlfree,
- struct bu_color *c,
- int mode,
- struct brep_cdt *s);
-
-/* Given two or more triangulation states, refine them to clear any face
- * overlaps introduced by the triangulation. If any of the states are
- * un-tessellated, first perform the tessellation indicated by the state
- * settings and then proceed to resolve after all states have an initial
- * tessellation. Returns 0 if no changes were needed, the number of
- * updated CDT states if changes were made, and -1 if one or more
- * unresolvable overlaps were encountered. Individual CDT states may
- * subsequently be queried for other information about their specific
- * states with other function calls - this function returns only the
- * overall result. */
-extern BREP_EXPORT int
-brep_cdt_ovlp_resolve(struct brep_cdt **s_a, int s_cnt, double lthreshold, int
timeout);
-
-/* Retrieve the face, vertex and normal information from a tessellation state
- * in the form of integer and fastf_t arrays. */
-extern BREP_EXPORT int
-brep_cdt_mesh(
- int **faces, int *fcnt, fastf_t **vertices, int *vcnt,
- int **face_normals, int *fn_cnt, fastf_t **normals, int *ncnt,
- struct brep_cdt *s, int exp_face_cnt, int *exp_faces
- );
-
-__END_DECLS
-
-/** @} */
-
-#endif /* BREP_CDT_H */
-
-/*
- * Local Variables:
- * tab-width: 8
- * mode: C
- * indent-tabs-mode: t
- * c-file-style: "stroustrup"
- * End:
- * ex: shiftwidth=4 tabstop=8
- */
Modified: brlcad/trunk/src/libbg/CMakeLists.txt
===================================================================
--- brlcad/trunk/src/libbg/CMakeLists.txt 2020-08-19 00:37:19 UTC (rev
76838)
+++ brlcad/trunk/src/libbg/CMakeLists.txt 2020-08-19 00:59:34 UTC (rev
76839)
@@ -28,7 +28,6 @@
tri_tri.c
trimesh.cpp
trimesh_isect.cpp
- trimesh_pt_in.c
util.c
)
Modified: brlcad/trunk/src/libbg/tests/CMakeLists.txt
===================================================================
--- brlcad/trunk/src/libbg/tests/CMakeLists.txt 2020-08-19 00:37:19 UTC (rev
76838)
+++ brlcad/trunk/src/libbg/tests/CMakeLists.txt 2020-08-19 00:59:34 UTC (rev
76839)
@@ -132,12 +132,7 @@
add_test(NAME bg_tri_pt_dist_coplanar_center COMMAND bg_tri_closest_pt
0,0,0 -1,-1,0 1,-1,0 0,1,0 0)
add_test(NAME bg_tri_pt_dist_coplanar_vert_closest COMMAND bg_tri_closest_pt
-2,-1,0 -1,-1,0 1,-1,0 0,1,0 1)
-# ************ trimesh_pt_in.cpp tests ***********
-BRLCAD_ADDEXEC(bg_trimesh_pt_in trimesh_pt_in.c "libbg;libbn;libbu" TEST)
-
-add_test(NAME bg_trimesh_pt_in_basic COMMAND bg_trimesh_pt_in 1)
-
# ************ polygon_op.cpp tests ***********
BRLCAD_ADDEXEC(bg_polygon_op polygon_op.c "libbg;libbn;libbu" TEST)
Deleted: brlcad/trunk/src/libbg/tests/trimesh_pt_in.c
===================================================================
--- brlcad/trunk/src/libbg/tests/trimesh_pt_in.c 2020-08-19 00:37:19 UTC
(rev 76838)
+++ brlcad/trunk/src/libbg/tests/trimesh_pt_in.c 2020-08-19 00:59:34 UTC
(rev 76839)
@@ -1,161 +0,0 @@
-/* T R I M E S H _ P T _ I N . C
- * BRL-CAD
- *
- * Copyright (c) 2011-2020 United States Government as represented by
- * the U.S. Army Research Laboratory.
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public License
- * version 2.1 as published by the Free Software Foundation.
- *
- * This library is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this file; see the file named COPYING for more
- * information.
- */
-
-#include "common.h"
-
-#include <stdio.h>
-
-#include "bu.h"
-#include "bg.h"
-
-int
-main(int argc, char **argv)
-{
- int test_num = 0;
-
- if (argc != 2)
- bu_exit(1, "ERROR: [%s] input format is: test_number\n", argv[0]);
-
- bu_setprogname(argv[0]);
-
- sscanf(argv[1], "%d", &test_num);
-
- if (test_num == 1) {
- int status = -1;
- point_t TP = VINIT_ZERO;
- int num_faces = 4;
- int num_verts = 4;
- int *faces = (int *)bu_calloc(num_faces * 3, sizeof(int), "faces
array");
- point_t *verts = (point_t *)bu_calloc(num_verts, sizeof(point_t),
"vertices array");
-
- VSET(verts[0], -1, -1, -1);
- VSET(verts[1], 1, -1, -1);
- VSET(verts[2], 0, 1, -1);
- VSET(verts[3], 0, 0, 1);
-
- faces[0*3+0] = 3;
- faces[0*3+1] = 2;
- faces[0*3+2] = 0;
-
- faces[1*3+0] = 1;
- faces[1*3+1] = 3;
- faces[1*3+2] = 0;
-
- faces[2*3+0] = 2;
- faces[2*3+1] = 3;
- faces[2*3+2] = 1;
-
- faces[3*3+0] = 0;
- faces[3*3+1] = 2;
- faces[3*3+2] = 1;
-
- VSET(TP, 0, 0, 2);
- status = bg_trimesh_pt_in(TP, num_faces, faces, num_verts, verts);
-
- if (status == -1) {
- bu_exit(-1, "Fatal error - mesh validity test failed\n");
- } else {
- bu_log("Status: %s\n", (status) ? "inside" : "outside");
- if (status) {
- bu_exit(-1, "Fatal error - test point is outside mesh, but
reported inside\n");
- }
- }
-
- VSET(TP, 0, 0, 0);
- status = bg_trimesh_pt_in(TP, num_faces, faces, num_verts, verts);
-
- if (status == -1) {
- bu_exit(-1, "Fatal error - mesh validity test failed\n");
- } else {
- bu_log("Status: %s\n", (status) ? "inside" : "outside");
- if (!status) {
- bu_exit(-1, "Fatal error - test point is inside mesh, but
reported outside\n");
- }
- }
-
- return 0;
- }
-
- // Flip the triangles from test 1
- if (test_num == 2) {
- int status = -1;
- point_t TP = VINIT_ZERO;
- int num_faces = 4;
- int num_verts = 4;
- int *faces = (int *)bu_calloc(num_faces * 3, sizeof(int), "faces
array");
- point_t *verts = (point_t *)bu_calloc(num_verts, sizeof(point_t),
"vertices array");
-
- VSET(verts[0], -1, -1, -1);
- VSET(verts[1], 1, -1, -1);
- VSET(verts[2], 0, 1, -1);
- VSET(verts[3], 0, 0, 1);
-
- faces[0*3+0] = 3;
- faces[0*3+1] = 0;
- faces[0*3+2] = 2;
-
- faces[1*3+0] = 1;
- faces[1*3+1] = 0;
- faces[1*3+2] = 3;
-
- faces[2*3+0] = 2;
- faces[2*3+1] = 1;
- faces[2*3+2] = 3;
-
- faces[3*3+0] = 0;
- faces[3*3+1] = 1;
- faces[3*3+2] = 2;
-
- VSET(TP, 0, 0, 2);
- status = bg_trimesh_pt_in(TP, num_faces, faces, num_verts, verts);
-
- if (status == -1) {
- bu_exit(-1, "Fatal error - mesh validity test failed\n");
- } else {
- bu_log("Status: %s\n", (status) ? "inside" : "outside");
- }
-
- VSET(TP, 0, 0, 0);
- status = bg_trimesh_pt_in(TP, num_faces, faces, num_verts, verts);
-
- if (status == -1) {
- bu_exit(-1, "Fatal error - mesh validity test failed\n");
- } else {
- bu_log("Status: %s\n", (status) ? "inside" : "outside");
- }
-
- return 0;
- }
-
- bu_log("Error: unknown test number %d\n", test_num);
- return -1;
-}
-
-
-/** @} */
-/*
- * Local Variables:
- * mode: C
- * tab-width: 8
- * indent-tabs-mode: t
- * c-file-style: "stroustrup"
- * End:
- * ex: shiftwidth=4 tabstop=8
- */
Deleted: brlcad/trunk/src/libbg/trimesh_pt_in.c
===================================================================
--- brlcad/trunk/src/libbg/trimesh_pt_in.c 2020-08-19 00:37:19 UTC (rev
76838)
+++ brlcad/trunk/src/libbg/trimesh_pt_in.c 2020-08-19 00:59:34 UTC (rev
76839)
@@ -1,405 +0,0 @@
-/* This is a C translation of Mark Dickinson's point-in-polyhedron test from
- * https://github.com/mdickinson/polyhedron/ */
-
-/* TODO - should also look into this code to see if it can do the same job
- * faster...:
- *
- * https://github.com/GavinBarill/fast-winding-number-soups
- */
-
-/*
- * BSD 3-Clause License
- *
- * Copyright (c) 2019, Mark Dickinson
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions are met:
- *
- * 1. Redistributions of source code must retain the above copyright notice,
this
- * list of conditions and the following disclaimer.
- *
- * 2. Redistributions in binary form must reproduce the above copyright notice,
- * this list of conditions and the following disclaimer in the documentation
- * and/or other materials provided with the distribution.
- *
- * 3. Neither the name of the copyright holder nor the names of its
- * contributors may be used to endorse or promote products derived from
- * this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
- * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
ARE
- * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
- * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
- * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
LIABILITY,
- * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
USE
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-/*
- * Robust point-in-polyhedron test.
- *
- * Given an closed, oriented surface in R^3 described by a triangular mesh, the
- * code below gives a robust algorithm for determining whether a given point is
- * inside, on the boundary of, or outside, the surface. The algorithm should
give
- * correct results even in degenerate cases, and applies to disconnected
- * polyhedra, non simply-connected surfaces, and so on. There are no
requirements
- * for the surface to be convex, simple, connected or simply-connected.
- *
- * More precisely, we give a method for computing the *winding number* of a
closed
- * oriented surface S around a point TP that doesn't lie on S. Roughly
speaking,
- * the winding number of the closed oriented surface S around a point TP not
on S
- * is the number of times that the surface encloses that point; for a simple
- * outward-oriented surface (like that of a convex polyhedron, for example),
the
- * winding number will be 1 for points inside the surface and 0 for points
- * outside.
- *
- * For a precise definition of winding number, we can turn to algebraic
topology:
- * our oriented surface is presented as a collection of combinatorial data
- * defining abstract vertices, edges and triangles, together with a mapping of
- * those vertices to R^3. The combinatorial data describe a simplicial
complex C,
- * and assuming that TP doesn't lie on the surface, the mapping of the
vertices to
- * R^3 gives a continuous map from the geometric realization of C to R^3 -
{TP}.
- * This in turn induces a map on second homology groups:
- *
- * H^2(C, Z) -> H^2(R^3 - {TP}, Z)
- *
- * and by taking the usual right-handed orientation in R^3 we identify H^2(R^3
-
- * {TP}, Z) with Z. The image of [S] under this map gives the winding number.
In
- * particular, the well-definedness of the winding number does not depend on
- * topological properties of the embedding: it doesn't matter if the surface is
- * self-intersecting, or has degenerate triangles. The only condition is that
TP
- * does not lie on the surface S.
- *
- * Algorithm
- * ---------
- * The algorithm is based around the usual method of ray-casting: we take a
- * vertical line L through TP and count the intersections of this line with the
- * triangles of the surface, keeping track of orientations as we go. Let's
ignore
- * corner cases for a moment and assume that:
- *
- * (1) TP does not lie on the surface, and
- * (2) for each triangle T (thought of as a closed subset of R^3) touched by
- * our vertical line L, L meets the interior of T in exactly one point Q
- *
- * Then there are four possibilities for each such triangle T:
- *
- * 1. T lies *above* TP and is oriented *upwards* (*away* from TP).
- * 2. T lies *above* TP and is oriented *downwards* (*towards* TP).
- * 3. T lies *below* TP and is oriented *downwards* (*away* from TP).
- * 4. T lies *below* TP and is oriented *upwards* (*towards* TP).
- *
- * Let's write N1, N2, N3 and N4 for the counts of triangles satisfying
conditions
- * 1, 2, 3 and 4 respectively. Since we have a closed surface, these numbers
- * are not independent; they satisfy the relation:
- *
- * N1 + N4 == N2 + N3
- *
- * That is, the number of upward-facing triangles must match the number of
- * downward-facing triangles. The winding number w is then given by:
- *
- * w = N1 - N2 == N3 - N4
- *
- * In the code below, we simply compute 2*w = (N1 + N3) - (N2 + N4), so each
- * triangle oriented away from TP contributes 1 to 2w, while each triangle
oriented
- * towards TP contributes -1.
- *
- *
- * Making the algorithm robust
- * ---------------------------
- * Now we describe how to augment the basic algorithm described above to
include:
- *
- * - correct treatment of corner cases (vertical triangles, cases where L
meets an
- * edge or vertex directly, etc.)
- *
- * - detection of the case where the point lies directly on the surface.
- *
- * It turns out that to make the algorithm robust, all we need to do is be
careful
- * and consistent about classifying vertices, edges and triangles. We do this
as
- * follows:
- *
- * - Each vertex of the surface that's not equal to TP is considered
*positive* if
- * its coordinates are lexicographically greater than TP, and *negative*
- * otherwise.
- *
- * - For an edge PQ of the surface that's not collinear with TP, we first
describe
- * the classification in the case that P is negative and Q is positive, and
- * then extend to arbitrary PQ.
- *
- * For P negative and Q positive, there are two cases:
- *
- * 1. P and Q have distinct x coordinates. In that case we classify the edge
- * PQ by its intersection with the plane passing through TP and parallel
- * to the yz-plane: the edge is *positive* if the intersection point is
- * positive, and *negative* otherwise.
- *
- * 2. P and Q have the same x coordinate, in which case they must have
- * distinct y coordinates. (If the x and the y coordinates both match
- * then PQ passes through TP.) We classify by the intersection of PQ
- * with the line parallel to the y-axis through TP.
- *
- * For P positive and Q negative, we classify as above but reverse the sign.
- * For like-signed P and Q, the classification isn't used.
- *
- * Computationally, in case 1 above, the y-coordinate of the intersection
- * point is:
- *
- * Py + (Qy - Py) * (TPx - Px) / (Qx - Px)
- *
- * and this is greater than TPy iff
- *
- * (Py - TPy) * (Qx - TPx) - (Px - TPx) * (Qy - TPy)
- *
- * is positive, so the sign of the edge is the sign of the above expression.
- * Similarly, if this quantity is zero then we need to look at the
z-coordinate
- * of the intersection, and the sign of the edge is given by
- *
- * (Pz - TPz) * (Qx - TPx) - (Px - TPx) * (Qz - TPz)
- *
- * In case 2, both of the above quantities are zero, and the sign of the
edge is
- * the sign of
- *
- * (Pz - TPz) * (Qy - TPy) - (Py - TPy) * (Qz - TPz)
- *
- * Another way to look at this: if P, Q and TP are not collinear then the
- * matrix
- *
- * ( Px Qx TPx )
- * ( Py Qy TPx )
- * ( Pz Qz TPx )
- * ( 1 1 1 )
- *
- * has rank 3. It follows that at least one of the three 3x3 minors
- *
- * | Px Qx TPx | | Px Qx TPx | | Py Qy TPy |
- * | Py Qy TPy | | Pz Qz TPz | | Pz Qz TPz |
- * | 1 1 1 | | 1 1 1 | | 1 1 1 |
- *
- * is nonzero. We define the sign of PQ to be the *negative* of the sign of
the
- * first nonzero minor in that list.
- *
- * - Each triangle PQR of the surface that's not coplanar with TP is considered
- * *positive* if its normal points away from TP, and *negative* if its normal
- * points towards TP.
- *
- * Computationally, the sign of the triangle PQR is the sign of the 4x4
- * determinant
- *
- * | Px Qx Rx TPx |
- * | Py Qy Ry TPy |
- * | Pz Qz Rz TPz |
- * | 1 1 1 1 |
- *
- * or equivalently of the 3x3 determinant
- *
- * | Px-TPx Qx-TPx Rx-TPx |
- * | Py-TPy Qy-TPy Ry-TPy |
- * | Pz-TPz Qz-TPz Rz-TPz |
- *
- *
- * Now to compute the contribution of any given triangle to the total winding
- * number:
- *
- * 1. Classify the vertices of the triangle. At the same time, we can check
that
- * none of the vertices is equal to TP. If all vertices have the same sign,
- * then the winding number contribution is zero.
- *
- * 2. Assuming that the vertices do not all have the same sign, two of the
three
- * edges connect two differently-signed vertices. Classify both those edges
- * (and simultaneously check that they don't pass through TP). If the edges
- * have opposite classification, then the winding number contribution is
zero.
- *
- * 3. Now two of the edges have the same sign: classify the triangle itself.
If
- * the triangle is positive it contributes 1/2 to the winding number total;
if
- * negative it contributes -1/2. In practice we count contributions of 1
and
- * -1, and halve the total at the end.
- *
- * Note that an edge between two like-signed vertices can never pass through
TP, so
- * there's no need to check the third edge in step 2. Similarly, a triangle
whose
- * edge-cycle is trivial can't contain TP in its interior.
- *
- * To understand what's going on above, it's helpful to step into the world of
- * homology again. The homology of R^3 - {TP} can be identified with that of
the
- * two-sphere S^2 by deformation retract, and we can decompose the two-sphere
as a
- * CW complex consisting of six cells, as follows:
- *
- * 0-cells B and F, where B = (-1, 0, 0) and F = (1, 0, 0)
- * 1-cells L and R, where
- * L = {(cos t, sin t, 0) | -pi <= t <= 0 }
- * R = {(cos t, sin t, 0) | 0 <= t <= pi }
- * 2-cells U and D, where U is the top half of the sphere (z >= 0)
- * and D is the bottom half (z <= 0), both oriented outwards.
- *
- * And the homology of the CW complex is now representable in terms of cellular
- * homology:
- *
- * d d
- * Z[U] + Z[D] --> Z[L] + Z[R] --> Z[B] + Z[F]
- *
- * with boundary maps given by:
- *
- * d[U] = [L] + [R]; d[D] = -[L] - [R]
- * d[R] = [B] - [F]; d[L] = [F] - [B]
- *
- * Now the original map C -> R^3 - {TP} from the geometric realization of the
- * simplicial complex is homotopic to a map C -> S^2 that sends:
- *
- * * each positive vertex to F and each negative vertex to B
- * * each edge with boundary [F] - [B] to L if the edge is negative, and -R if
the
- * edge is positive
- * * each edge with boundary [B] - [F] to R if the edge is positive, and -L if
the
- * edge is negative
- * * all other edges to 0
- * * each triangle whose boundary is [L] + [R] to either U or -D,
- * depending on whether the triangle is positive or negative
- * * each triangle whose boundary is -[L] - [R] to either D or -U,
- * depending on whether the triangle is positive or negative
- * * all other triangles to 0
- *
- * Mapping all of the triangles in the surface this way, and summing the
results
- * in second homology, we end up with (winding number)*([U] + [D]).
- */
-
-#include "common.h"
-
-#include "vmath.h"
-#include "bu/log.h"
-#include "bg/trimesh.h"
-
-/* Return 1 if x is positive, -1 if it's negative, and 0 if it's zero. */
-static int ptm_sign(double x)
-{
- if (x > 0) return 1;
- if (x < 0) return -1;
- return 0;
-}
-
-/* Sign of the vertex P with respect to O, as defined above. */
-static int ptm_vertex_sign(point_t V, point_t TP, int *exact_flag)
-{
- int rx,ry, rz;
- rx = ptm_sign(V[X] - TP[X]);
- if (rx) return rx;
-
- ry = ptm_sign(V[Y] - TP[Y]);
- if (ry) return ry;
-
- rz = ptm_sign(V[Z] - TP[Z]);
- if (rz) return rz;
-
- (*exact_flag) = 1;
- /*bu_log("Error: vertex coincides with test point\n");*/
- return 0;
-}
-
-/* Sign of the edge PQ with respect to O, as defined above. */
-static int ptm_edge_sign(point_t P, point_t Q, point_t TP, int *exact_flag)
-{
- int r1, r2, r3;
- r1 = ptm_sign((P[Y] - TP[Y]) * (Q[X] - TP[X]) - (P[X] - TP[X]) * (Q[Y] -
TP[Y]));
- if (r1) return r1;
-
- r2 = ptm_sign((P[Z] - TP[Z]) * (Q[X] - TP[X]) - (P[X] - TP[X]) * (Q[Z] -
TP[Z]));
- if (r2) return r2;
-
- r3 = ptm_sign((P[Z] - TP[Z]) * (Q[Y] - TP[Y]) - (P[Y] - TP[Y]) * (Q[Z] -
TP[Z]));
- if (r3) return r3;
-
- (*exact_flag) = 1;
- /*bu_log("Error: vertices collinear with origin\n");*/
- return 0;
-}
-
-/* Sign of the triangle PQR with respect to O, as defined above. */
-static int ptm_triangle_sign(point_t P, point_t Q, point_t R, point_t TP, int
*exact_flag)
-{
- double m1_0 = P[X] - TP[X];
- double m1_1 = P[Y] - TP[Y];
- double m2_0 = Q[X] - TP[X];
- double m2_1 = Q[Y] - TP[Y];
- double m3_0 = R[X] - TP[X];
- double m3_1 = R[Y] - TP[Y];
-
- int r = ptm_sign(
- (m1_0 * m2_1 - m1_1 * m2_0) * (R[Z] - TP[Z]) +
- (m2_0 * m3_1 - m2_1 * m3_0) * (P[Z] - TP[Z]) +
- (m3_0 * m1_1 - m3_1 * m1_0) * (Q[Z] - TP[Z]));
-
- if (!r) {
- (*exact_flag) = 1;
- /*bu_log("vertices coplanar with origin\n");*/
- }
- return r;
-}
-
-/* Return the contribution of this triangle to the winding number. */
-int
-bg_ptm_triangle_chain(point_t v1, point_t v2, point_t v3, point_t tp, int
*exact_flag)
-{
- int ef = 0;
- int v1sign = ptm_vertex_sign(v1, tp, &ef);
- int v2sign = ptm_vertex_sign(v2, tp, &ef);
- int v3sign = ptm_vertex_sign(v3, tp, &ef);
- int face_boundary = 0;
- int tsign;
-
- if (v1sign != v2sign) {
- face_boundary += ptm_edge_sign(v1, v2, tp, &ef);
- }
- if (v2sign != v3sign) {
- face_boundary += ptm_edge_sign(v2, v3, tp, &ef);
- }
- if (v3sign != v1sign) {
- face_boundary += ptm_edge_sign(v3, v1, tp, &ef);
- }
- if (!face_boundary) {
- if (ef) {
- (*exact_flag) = 1;
- }
- return 0;
- }
-
- tsign = ptm_triangle_sign(v1, v2, v3, tp, &ef);
- if (ef) {
- (*exact_flag) = 1;
- }
- return tsign;
-}
-
-
-int
-bg_trimesh_pt_in(point_t tp, int num_faces, int *faces, int num_vertices,
point_t *pts)
-{
- int exact = 0;
- int wn = 0;
- int not_solid = bg_trimesh_solid2(num_vertices, num_faces, (fastf_t *)pts,
faces, NULL);
- if (not_solid) {
- return -1;
- }
-
- for (int i = 0; i < num_faces; i++) {
- point_t v1, v2, v3;
- VMOVE(v1, pts[faces[3*i+0]]);
- VMOVE(v2, pts[faces[3*i+1]]);
- VMOVE(v3, pts[faces[3*i+2]]);
- wn += bg_ptm_triangle_chain(v1, v2, v3, tp, &exact);
- if (exact) return 2;
- }
-
- return wn;
-}
-
-
-
-/*
- * Local Variables:
- * tab-width: 8
- * mode: C
- * indent-tabs-mode: t
- * c-file-style: "stroustrup"
- * End:
- * ex: shiftwidth=4 tabstop=8
- */
Modified: brlcad/trunk/src/libbrep/CMakeLists.txt
===================================================================
--- brlcad/trunk/src/libbrep/CMakeLists.txt 2020-08-19 00:37:19 UTC (rev
76838)
+++ brlcad/trunk/src/libbrep/CMakeLists.txt 2020-08-19 00:59:34 UTC (rev
76839)
@@ -49,26 +49,11 @@
#opennurbs_fit.cpp
)
-set(CDT2_srcs
- cdt2/cdt.cpp
- cdt2/vert.cpp
- cdt2/edge.cpp
- cdt2/mesh.cpp
- cdt2/polygon.cpp
- )
-if (ENABLE_CDT2)
- set(LIBBREP_SOURCES ${LIBBREP_SOURCES} ${CDT2_srcs})
-endif (ENABLE_CDT2)
-
set(libbrep_ignored_files
tools/tools.h
brep_except.h
cdt/cdt.h
cdt/mesh.h
- cdt/omesh.cpp
- cdt/overt.cpp
- cdt/ovlps.cpp
- cdt/ovlps_grps.cpp
cdt/RTree.h
opennurbs_fit.h
opennurbs_fit.cpp
@@ -76,8 +61,6 @@
shape_recognition/shape_recognition.h
shape_recognition/torus.cpp
surface_tree_queue_tests.patch
- ${CDT2_srcs}
- cdt2/cdt.h
)
CMAKEFILES(${libbrep_ignored_files})
Deleted: brlcad/trunk/src/libbrep/cdt/omesh.cpp
===================================================================
--- brlcad/trunk/src/libbrep/cdt/omesh.cpp 2020-08-19 00:37:19 UTC (rev
76838)
+++ brlcad/trunk/src/libbrep/cdt/omesh.cpp 2020-08-19 00:59:34 UTC (rev
76839)
@@ -1,585 +0,0 @@
-/* C D T _ O V L P S . C P P
- * BRL-CAD
- *
- * Copyright (c) 2007-2020 United States Government as represented by
- * the U.S. Army Research Laboratory.
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public License
- * version 2.1 as published by the Free Software Foundation.
- *
- * This library is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this file; see the file named COPYING for more
- * information.
- */
-/** @addtogroup libbrep */
-/** @{ */
-/** @file cdt_ovlps.cpp
- *
- * Constrained Delaunay Triangulation of NURBS B-Rep objects.
- *
- * overlap mesh implementation
- *
- */
-
-#include "common.h"
-#include <iostream>
-#include <numeric>
-#include <queue>
-#include <random>
-#include <string>
-#include "bu/str.h"
-#include "bg/tri_pt.h"
-#include "./cdt.h"
-
-void
-omesh_t::plot_vtree(const char *fname)
-{
- FILE *plot = fopen(fname, "w");
- RTree<long, double, 3>::Iterator tree_it;
- long v_ind;
- vtree.GetFirst(tree_it);
- while (!tree_it.IsNull()) {
- v_ind = *tree_it;
- pl_color(plot, 255, 0, 0);
- overts[v_ind]->plot(plot);
- ++tree_it;
- }
- fclose(plot);
-}
-
-std::string
-omesh_t::sname()
-{
- struct ON_Brep_CDT_State *s_cdt = (struct ON_Brep_CDT_State *)fmesh->p_cdt;
- return std::string(s_cdt->name);
-}
-
-bool
-omesh_t::validate_vtree()
-{
- RTree<long, double, 3>::Iterator tree_it;
- long v_ind;
- vtree.GetFirst(tree_it);
- while (!tree_it.IsNull()) {
- v_ind = *tree_it;
- overt_t *ov = overts[v_ind];
- ON_3dPoint vp = ov->vpnt();
- std::set<overt_t *> search_vert_bb = vert_search(ov->bb);
- if (!search_vert_bb.size()) {
- std::cout << "Error: no nearby verts for vert bb " << v_ind <<
"??\n";
- return false;
- }
- if (search_vert_bb.find(ov) == search_vert_bb.end()) {
- std::cout << "Error: vert in tree, but bb search couldn't find: "
<< v_ind << "\n";
- std::set<overt_t *> s2 = vert_search(ov->bb);
- if (s2.find(ov) == s2.end()) {
- std::cout << "Second try didn't work: " << v_ind << "\n";
- }
- return false;
- }
-
- ON_BoundingBox pbb(vp, vp);
- std::set<overt_t *> search_vert = vert_search(pbb);
- if (!search_vert.size()) {
- std::cout << "Error: vert point not contained by tree box?? " <<
v_ind << "??\n";
- std::set<overt_t *> sv2 = vert_search(pbb);
- if (sv2.find(ov) == sv2.end()) {
- std::cout << "Second try didn't work: " << v_ind << "\n";
- }
- return false;
- }
-
- ++tree_it;
- }
- return true;
-}
-
-std::set<std::pair<long, long>>
-omesh_t::vert_ovlps(omesh_t *other)
-{
- std::set<std::pair<long, long>> vert_pairs;
- vert_pairs.clear();
- vtree.Overlaps(other->vtree, &vert_pairs);
- return vert_pairs;
-}
-
-void
-omesh_t::plot(const char *fname)
-{
- struct bu_color c = BU_COLOR_INIT_ZERO;
- unsigned char rgb[3] = {0,0,255};
-
- // Randomize the blue so (usually) subsequent
- // draws of different meshes won't erase the
- // previous wireframe
- std::random_device rd;
- std::mt19937 reng(rd());
- std::uniform_int_distribution<> rrange(100,250);
- int brand = rrange(reng);
- rgb[2] = (unsigned char)brand;
-
- FILE *plot = fopen(fname, "w");
-
- RTree<size_t, double, 3>::Iterator tree_it;
- size_t t_ind;
- triangle_t tri;
-
- bu_color_from_rgb_chars(&c, (const unsigned char *)rgb);
-
- pl_color(plot, 0, 0, 255);
- fmesh->tris_tree.GetFirst(tree_it);
- while (!tree_it.IsNull()) {
- t_ind = *tree_it;
- tri = fmesh->tris_vect[t_ind];
- fmesh->plot_tri(tri, &c, plot, 255, 0, 0);
- ++tree_it;
- }
-
- double tri_r = 0;
-
- bu_color_rand(&c, BU_COLOR_RANDOM_LIGHTENED);
- pl_color_buc(plot, &c);
- std::set<size_t>::iterator ts_it;
- for (ts_it = intruding_tris.begin(); ts_it != intruding_tris.end();
ts_it++) {
- tri = fmesh->tris_vect[*ts_it];
- double tr = fmesh->tri_pnt_r(tri.ind);
- tri_r = (tr > tri_r) ? tr : tri_r;
- fmesh->plot_tri(tri, &c, plot, 255, 0, 0);
- }
-
-
-
- std::set<overt_t *>::iterator iv_it;
- std::map<uedge_t, std::vector<revt_pt_t>>::iterator es_it;
- for (es_it = edge_sets.begin(); es_it != edge_sets.end(); es_it++) {
- for (size_t i = 0; i < es_it->second.size(); i++) {
- overt_t *iv = es_it->second[i].ov;
- ON_3dPoint vp = iv->vpnt();
- pl_color(plot, 255, 0, 0);
- plot_pnt_3d(plot, &vp, tri_r, 0);
- pl_color(plot, 0, 255, 0);
- ON_3dPoint sp = es_it->second[i].spnt;
- plot_pnt_3d(plot, &sp, tri_r, 0);
- }
- }
-
- std::map<bedge_seg_t *, std::set<overt_t *>>::iterator ev_it;
- pl_color(plot, 128, 0, 255);
- for (ev_it = edge_verts->begin(); ev_it != edge_verts->end(); ev_it++) {
- bedge_seg_t *eseg = ev_it->first;
- struct ON_Brep_CDT_State *s_cdt_edge = (struct ON_Brep_CDT_State
*)eseg->p_cdt;
- int f_id1 =
s_cdt_edge->brep->m_T[eseg->tseg1->trim_ind].Face()->m_face_index;
- int f_id2 =
s_cdt_edge->brep->m_T[eseg->tseg2->trim_ind].Face()->m_face_index;
- cdt_mesh_t &fmesh_f1 = s_cdt_edge->fmeshes[f_id1];
- cdt_mesh_t &fmesh_f2 = s_cdt_edge->fmeshes[f_id2];
- omesh_t *o1 = fmesh_f1.omesh;
- omesh_t *o2 = fmesh_f2.omesh;
- if (o1 == this || o2 == this) {
- std::set<overt_t *>::iterator v_it;
- for (v_it = ev_it->second.begin(); v_it != ev_it->second.end();
v_it++) {
- overt_t *iv = *v_it;
- if (iv->omesh == this) continue;
- ON_3dPoint vp = iv->vpnt();
- plot_pnt_3d(plot, &vp, tri_r, 0);
- }
- }
- }
-
- pl_color(plot, 0, 0, 255);
-
-
- fclose(plot);
-}
-
-void
-omesh_t::plot()
-{
- struct bu_vls fname = BU_VLS_INIT_ZERO;
- struct ON_Brep_CDT_State *s_cdt = (struct ON_Brep_CDT_State *)fmesh->p_cdt;
- bu_vls_sprintf(&fname, "%s-%d_ovlps.plot3", s_cdt->name, fmesh->f_id);
- plot(bu_vls_cstr(&fname));
- bu_vls_free(&fname);
-}
-
-overt_t *
-omesh_t::vert_closest(double *vdist, overt_t *v)
-{
- ON_BoundingBox fbbox = v->omesh->fmesh->bbox();
- ON_3dPoint opnt = v->bb.Center();
-
- // Find close verts, iterate through them and
- // find the closest
- ON_BoundingBox s_bb = v->bb;
- ON_3dPoint p = v->vpnt();
- std::set<overt_t *> nverts = vert_search(s_bb);
- bool last_try = false;
- while (!nverts.size() && !last_try) {
- ON_3dVector vmin = s_bb.Min() - s_bb.Center();
- ON_3dVector vmax = s_bb.Max() - s_bb.Center();
- vmin.Unitize();
- vmax.Unitize();
- vmin = vmin * s_bb.Diagonal().Length() * 2;
- vmax = vmax * s_bb.Diagonal().Length() * 2;
- s_bb.m_min = opnt + vmin;
- s_bb.m_max = opnt + vmax;
- if (s_bb.Includes(fbbox, true)) {
- last_try = true;
- }
- nverts = vert_search(s_bb);
- }
-
- double dist = DBL_MAX;
- overt_t *nv = NULL;
- std::set<overt_t *>::iterator v_it;
- for (v_it = nverts.begin(); v_it != nverts.end(); v_it++) {
- overt_t *ov = *v_it;
- ON_3dPoint np = ov->vpnt();
- if (np.DistanceTo(p) < dist) {
- nv = ov;
- dist = np.DistanceTo(p);
- }
- }
- if (vdist) {
- (*vdist) = dist;
- }
- return nv;
-}
-
-overt_t *
-omesh_t::vert_closest(double *vdist, ON_3dPoint &opnt)
-{
- ON_BoundingBox fbbox = fmesh->bbox();
-
- ON_3dPoint ptol(ON_ZERO_TOLERANCE, ON_ZERO_TOLERANCE, ON_ZERO_TOLERANCE);
- ON_BoundingBox s_bb(opnt, opnt);
- ON_3dPoint npnt = opnt + ptol;
- s_bb.Set(npnt, true);
- npnt = opnt - ptol;
- s_bb.Set(npnt, true);
-
- std::set<overt_t *> nverts = vert_search(s_bb);
- bool last_try = false;
- while (!nverts.size() && !last_try) {
- ON_3dVector vmin = s_bb.Min() - s_bb.Center();
- ON_3dVector vmax = s_bb.Max() - s_bb.Center();
- vmin.Unitize();
- vmax.Unitize();
- vmin = vmin * s_bb.Diagonal().Length() * 2;
- vmax = vmax * s_bb.Diagonal().Length() * 2;
- s_bb.m_min = opnt + vmin;
- s_bb.m_max = opnt + vmax;
- if (s_bb.Includes(fbbox, true)) {
- last_try = true;
- }
- nverts = vert_search(s_bb);
- }
-
- double dist = DBL_MAX;
- overt_t *nv = NULL;
- std::set<overt_t *>::iterator v_it;
- for (v_it = nverts.begin(); v_it != nverts.end(); v_it++) {
- overt_t *ov = *v_it;
- ON_3dPoint np = ov->vpnt();
- if (np.DistanceTo(opnt) < dist) {
- nv = ov;
- dist = np.DistanceTo(opnt);
- }
- }
- if (vdist) {
- (*vdist) = dist;
- }
- return nv;
-}
-
-double
-omesh_t::closest_pt(ON_3dPoint &cp, ON_3dVector &cn, const ON_3dPoint &op)
-{
- ON_BoundingBox fbbox = fmesh->bbox();
- if (!fmesh->tris_vect.size()) {
- return DBL_MAX;
- }
-
- double lguess = fbbox.Diagonal().Length()/(double)fmesh->tris_vect.size();
- lguess = (lguess < ON_ZERO_TOLERANCE) ? ON_ZERO_TOLERANCE : lguess;
-
- ON_3dPoint ptol(lguess, lguess, lguess);
- ON_BoundingBox s_bb(op, op);
- ON_3dPoint npnt = op + ptol;
- s_bb.Set(npnt, true);
- npnt = op - ptol;
- s_bb.Set(npnt, true);
-
- // Find close triangles, iterate through them and
- // find the closest interior edge
- std::set<size_t> ntris = tris_search(s_bb);
- bool last_try = false;
- while (!ntris.size() && !last_try) {
- ON_3dVector vmin = s_bb.Min() - s_bb.Center();
- ON_3dVector vmax = s_bb.Max() - s_bb.Center();
- vmin.Unitize();
- vmax.Unitize();
- vmin = vmin * s_bb.Diagonal().Length() * 2;
- vmax = vmax * s_bb.Diagonal().Length() * 2;
- s_bb.m_min = op + vmin;
- s_bb.m_max = op + vmax;
- if (s_bb.Includes(fbbox, true)) {
- last_try = true;
- }
- ntris = tris_search(s_bb);
- }
-
- double tdist = DBL_MAX;
- point_t closest_pt = VINIT_ZERO;
- triangle_t ctri;
- std::set<size_t>::iterator tr_it;
- for (tr_it = ntris.begin(); tr_it != ntris.end(); tr_it++) {
- triangle_t t = fmesh->tris_vect[*tr_it];
-
- point_t T_V[3];
- VSET(T_V[0], fmesh->pnts[t.v[0]]->x, fmesh->pnts[t.v[0]]->y,
fmesh->pnts[t.v[0]]->z);
- VSET(T_V[1], fmesh->pnts[t.v[1]]->x, fmesh->pnts[t.v[1]]->y,
fmesh->pnts[t.v[1]]->z);
- VSET(T_V[2], fmesh->pnts[t.v[2]]->x, fmesh->pnts[t.v[2]]->y,
fmesh->pnts[t.v[2]]->z);
-
- point_t opt;
- point_t lclosest_pt;
- VSET(opt, op.x, op.y, op.z);
-
- double ltdist = bg_tri_closest_pt(&lclosest_pt, opt, T_V[0], T_V[1],
T_V[2]);
-
- if (ltdist < tdist) {
- VMOVE(closest_pt, lclosest_pt);
- ctri = t;
- tdist = ltdist;
- }
- }
-
- ON_3dPoint on_cp(closest_pt[X], closest_pt[Y], closest_pt[Z]);
- ON_3dVector on_cn = ctri.m->tnorm(ctri);
-
- cp = on_cp;
- cn = on_cn;
-
- return tdist;
-}
-
-uedge_t
-omesh_t::closest_uedge(ON_3dPoint &p)
-{
- uedge_t uedge;
-
- if (!fmesh->pnts.size()) return uedge;
-
- ON_BoundingBox fbbox = fmesh->bbox();
- if (!fmesh->tris_vect.size()) {
- return uedge_t();
- }
-
- double lguess = fbbox.Diagonal().Length()/(double)fmesh->tris_vect.size();
- lguess = (lguess < ON_ZERO_TOLERANCE) ? ON_ZERO_TOLERANCE : lguess;
-
- ON_3dPoint ptol(lguess, lguess, lguess);
- ON_BoundingBox s_bb(p, p);
- ON_3dPoint npnt = p + ptol;
- s_bb.Set(npnt, true);
- npnt = p - ptol;
- s_bb.Set(npnt, true);
-
- // Find close triangles, iterate through them and
- // find the closest interior edge
- std::set<size_t> ntris = tris_search(s_bb);
- bool last_try = false;
- while (!ntris.size() && !last_try) {
- ON_3dVector vmin = s_bb.Min() - s_bb.Center();
- ON_3dVector vmax = s_bb.Max() - s_bb.Center();
- vmin.Unitize();
- vmax.Unitize();
- vmin = vmin * s_bb.Diagonal().Length() * 2;
- vmax = vmax * s_bb.Diagonal().Length() * 2;
- s_bb.m_min = p + vmin;
- s_bb.m_max = p + vmax;
- if (s_bb.Includes(fbbox, true)) {
- last_try = true;
- }
- ntris = tris_search(s_bb);
- }
-
- double uedist = DBL_MAX;
- std::set<size_t>::iterator tr_it;
- for (tr_it = ntris.begin(); tr_it != ntris.end(); tr_it++) {
- triangle_t t = fmesh->tris_vect[*tr_it];
- ON_3dPoint tp = p;
- uedge_t ue = fmesh->closest_uedge(t, tp);
- double ue_cdist = fmesh->uedge_dist(ue, p);
- if (ue_cdist < uedist) {
- uedge = ue;
- uedist = ue_cdist;
- }
- }
-
- return uedge;
-}
-
-
-std::set<uedge_t>
-omesh_t::interior_uedges_search(ON_BoundingBox &bb)
-{
- std::set<uedge_t> uedges;
- uedges.clear();
-
- ON_3dPoint opnt = bb.Center();
-
- if (!fmesh->pnts.size()) return uedges;
-
- ON_BoundingBox fbbox = fmesh->bbox();
-
- // Find close triangles, iterate through them and
- // find the closest interior edge
- ON_BoundingBox s_bb = bb;
- std::set<size_t> ntris = tris_search(s_bb);
- bool last_try = false;
- while (!ntris.size() && !last_try) {
- ON_3dVector vmin = s_bb.Min() - s_bb.Center();
- ON_3dVector vmax = s_bb.Max() - s_bb.Center();
- vmin.Unitize();
- vmax.Unitize();
- vmin = vmin * s_bb.Diagonal().Length() * 2;
- vmax = vmax * s_bb.Diagonal().Length() * 2;
- s_bb.m_min = opnt + vmin;
- s_bb.m_max = opnt + vmax;
- if (s_bb.Includes(fbbox, true)) {
- last_try = true;
- }
- ntris = tris_search(s_bb);
- }
-
- std::set<size_t>::iterator tr_it;
- for (tr_it = ntris.begin(); tr_it != ntris.end(); tr_it++) {
- triangle_t t = fmesh->tris_vect[*tr_it];
- ON_3dPoint tp = bb.Center();
- uedge_t ue = fmesh->closest_interior_uedge(t, tp);
- uedges.insert(ue);
- }
-
- return uedges;
-}
-
-std::set<size_t>
-omesh_t::tris_search(ON_BoundingBox &bb)
-{
- return fmesh->tris_search(bb);
-}
-
-static bool NearVertsCallback(long data, void *a_context) {
- std::set<long> *nverts = (std::set<long> *)a_context;
- nverts->insert(data);
- return true;
-}
-std::set<overt_t *>
-omesh_t::vert_search(ON_BoundingBox &bb)
-{
- double fMin[3], fMax[3];
- fMin[0] = bb.Min().x - ON_ZERO_TOLERANCE;
- fMin[1] = bb.Min().y - ON_ZERO_TOLERANCE;
- fMin[2] = bb.Min().z - ON_ZERO_TOLERANCE;
- fMax[0] = bb.Max().x + ON_ZERO_TOLERANCE;
- fMax[1] = bb.Max().y + ON_ZERO_TOLERANCE;
- fMax[2] = bb.Max().z + ON_ZERO_TOLERANCE;
- std::set<long> vtree_near_verts;
- size_t nhits = vtree.Search(fMin, fMax, NearVertsCallback, (void
*)&vtree_near_verts);
-
- if (!nhits) {
- return std::set<overt_t *>();
- }
-
- std::set<overt_t *> near_overts;
- std::set<long>::iterator n_it;
- for (n_it = vtree_near_verts.begin(); n_it != vtree_near_verts.end();
n_it++) {
- near_overts.insert(overts[*n_it]);
- }
-
- return near_overts;
-}
-
-overt_t *
-omesh_t::vert_add(long f3ind, ON_BoundingBox *bb)
-{
- overt_t *nv = new overt_t(this, f3ind);
- if (bb) {
- nv->update(bb);
- } else {
- nv->update();
- }
- overts[f3ind] = nv;
- return nv;
-}
-
-std::set<omesh_t *>
-scdt_meshes(std::set<std::pair<cdt_mesh_t *, cdt_mesh_t *>> *check_pairs,
struct ON_Brep_CDT_State *s_cdt)
-{
- std::set<omesh_t *> check_meshes;
- std::set<std::pair<cdt_mesh_t *, cdt_mesh_t *>>::iterator o_it;
- for (o_it = check_pairs->begin(); o_it != check_pairs->end(); o_it++) {
- if ((struct ON_Brep_CDT_State *)o_it->first->omesh->fmesh->p_cdt ==
s_cdt) {
- check_meshes.insert(o_it->first->omesh);
- }
- if ((struct ON_Brep_CDT_State *)o_it->second->omesh->fmesh->p_cdt ==
s_cdt) {
- check_meshes.insert(o_it->second->omesh);
- }
- }
-
- return check_meshes;
-}
-
-
-bool
-omesh_t::closest_nearby_mesh_point(ON_3dPoint &s_p, ON_3dVector &s_n,
ON_3dPoint *p, struct ON_Brep_CDT_State *s_cdt)
-{
- std::set<omesh_t *> check_meshes = scdt_meshes(check_pairs, s_cdt);
-
- ON_BoundingBox pbb(*p, *p);
-
- bool have_dist = false;
- double cdist = DBL_MAX;
- ON_3dPoint cp;
- ON_3dVector cn;
- std::set<omesh_t *>::iterator om_it;
- for (om_it = check_meshes.begin(); om_it != check_meshes.end(); om_it++) {
- omesh_t *om = *om_it;
- if (om->fmesh->bbox().IsDisjoint(pbb)) continue;
- ON_3dPoint om_cp;
- ON_3dVector om_cn;
- double ldist = om->closest_pt(om_cp, om_cn, *p);
- if (ldist < DBL_MAX && cdist > ldist) {
- cdist = ldist;
- cp = om_cp;
- cn = om_cn;
- have_dist = true;
- }
- }
- if (!have_dist) {
- cdist = closest_pt(cp, cn, *p);
- }
-
- s_p = cp;
- s_n = cn;
-
- return (cdist < DBL_MAX);
-}
-
-/** @} */
-
-// Local Variables:
-// mode: C++
-// tab-width: 8
-// c-basic-offset: 4
-// indent-tabs-mode: t
-// c-file-style: "stroustrup"
-// End:
-// ex: shiftwidth=4 tabstop=8
-
Deleted: brlcad/trunk/src/libbrep/cdt/overt.cpp
===================================================================
--- brlcad/trunk/src/libbrep/cdt/overt.cpp 2020-08-19 00:37:19 UTC (rev
76838)
+++ brlcad/trunk/src/libbrep/cdt/overt.cpp 2020-08-19 00:59:34 UTC (rev
76839)
@@ -1,282 +0,0 @@
-/* C D T _ O V L P S . C P P
- * BRL-CAD
- *
- * Copyright (c) 2007-2020 United States Government as represented by
- * the U.S. Army Research Laboratory.
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public License
- * version 2.1 as published by the Free Software Foundation.
- *
- * This library is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this file; see the file named COPYING for more
- * information.
- */
-/** @addtogroup libbrep */
-/** @{ */
-/** @file cdt_ovlps.cpp
- *
- * Constrained Delaunay Triangulation of NURBS B-Rep objects.
- *
- * overlap vertex implementation.
- *
- */
-
-#include "common.h"
-#include <iostream>
-#include <numeric>
-#include <queue>
-#include <random>
-#include <string>
-#include "bu/str.h"
-#include "./mesh.h"
-#include "./cdt.h"
-
-ON_3dPoint
-overt_t::vpnt() {
- ON_3dPoint vp = *(omesh->fmesh->pnts[p_id]);
- return vp;
-}
-
-bool
-overt_t::edge_vert() {
- return (omesh->fmesh->ep.find(p_id) != omesh->fmesh->ep.end());
-}
-
-void
-overt_t::update() {
-
- // Get pnt's associated edges.
- std::set<edge_t> edges = omesh->fmesh->v2edges[p_id];
-
- // If we don't have any edge information, this method of
- // updating the vertex isn't viable - leave it as is.
- if (!edges.size()) {
- return;
- }
-
- double fMin[3], fMax[3];
- if (init) {
- // Previously updated - remove old instance from tree
- fMin[0] = bb.Min().x-ON_ZERO_TOLERANCE;
- fMin[1] = bb.Min().y-ON_ZERO_TOLERANCE;
- fMin[2] = bb.Min().z-ON_ZERO_TOLERANCE;
- fMax[0] = bb.Max().x+ON_ZERO_TOLERANCE;
- fMax[1] = bb.Max().y+ON_ZERO_TOLERANCE;
- fMax[2] = bb.Max().z+ON_ZERO_TOLERANCE;
- omesh->vtree.Remove(fMin, fMax, p_id);
- }
-
- // find the shortest edge associated with pnt
- std::set<edge_t>::iterator e_it;
- double elen = DBL_MAX;
- for (e_it = edges.begin(); e_it != edges.end(); e_it++) {
- ON_3dPoint *p1 = omesh->fmesh->pnts[(*e_it).v[0]];
- ON_3dPoint *p2 = omesh->fmesh->pnts[(*e_it).v[1]];
- double dist = p1->DistanceTo(*p2);
- elen = (dist < elen) ? dist : elen;
- }
- v_min_edge_len = elen;
-
- // We also need to check if the vertex is close to
- // the opposite edge of one of its triangles - that
- // will constrain how we can move it without flipping
- // a triangle.
- std::set<size_t> vtri_inds = omesh->fmesh->v2tris[p_id];
- std::set<size_t>::iterator tv_it;
- for (tv_it = vtri_inds.begin(); tv_it != vtri_inds.end(); tv_it++) {
- triangle_t tri = omesh->fmesh->tris_vect[*tv_it];
- double odist = tri.opp_edge_dist(p_id);
- elen = (odist < elen) ? odist : elen;
- }
-
- // create a bbox around pnt using length ~20% of the shortest edge length.
- ON_3dPoint v3dpnt = *omesh->fmesh->pnts[p_id];
-
- ON_BoundingBox init_bb(v3dpnt, v3dpnt);
- bb = init_bb;
- ON_3dPoint npnt = v3dpnt;
- double lfactor = 0.2;
- npnt.x = npnt.x + lfactor*elen;
- bb.Set(npnt, true);
- npnt = v3dpnt;
- npnt.x = npnt.x - lfactor*elen;
- bb.Set(npnt, true);
- npnt = v3dpnt;
- npnt.y = npnt.y + lfactor*elen;
- bb.Set(npnt, true);
- npnt = v3dpnt;
- npnt.y = npnt.y - lfactor*elen;
- bb.Set(npnt, true);
- npnt = v3dpnt;
- npnt.z = npnt.z + lfactor*elen;
- bb.Set(npnt, true);
- npnt = v3dpnt;
- npnt.z = npnt.z - lfactor*elen;
- bb.Set(npnt, true);
-
- // (re)insert the vertex into the parent omesh's vtree, once we're done
- // updating
- fMin[0] = bb.Min().x;
- fMin[1] = bb.Min().y;
- fMin[2] = bb.Min().z;
- fMax[0] = bb.Max().x;
- fMax[1] = bb.Max().y;
- fMax[2] = bb.Max().z;
- if (fMin[0] < -0.4*DBL_MAX || fMax[0] > 0.4*DBL_MAX) {
- std::cout << "Bad vert box!\n";
- }
- omesh->vtree.Insert(fMin, fMax, p_id);
-
- // Any closet point calculations and alignments are now invalid - update
accordingly
- std::map<omesh_t *, overt_t *>::iterator a_it;
- for (a_it = aligned.begin(); a_it != aligned.end(); a_it++) {
- overt_t *other_vert = a_it->second;
- other_vert->aligned.erase(omesh);
- other_vert->cpoints.erase(this);
- other_vert->cnorms.erase(this);
- }
- aligned.clear();
- cpoints.clear();
- cnorms.clear();
-
- // Once we've gotten here, the vertex is fully initialized
- init = true;
-}
-
-void
-overt_t::update(ON_BoundingBox *bbox) {
- double fMin[3], fMax[3];
-
- if (!bbox) {
- std::cerr << "Cannot update vertex with NULL bounding box!\n";
- return;
- }
-
- if (init) {
- // Previously updated - remove old instance from tree
- fMin[0] = bb.Min().x-ON_ZERO_TOLERANCE;
- fMin[1] = bb.Min().y-ON_ZERO_TOLERANCE;
- fMin[2] = bb.Min().z-ON_ZERO_TOLERANCE;
- fMax[0] = bb.Max().x+ON_ZERO_TOLERANCE;
- fMax[1] = bb.Max().y+ON_ZERO_TOLERANCE;
- fMax[2] = bb.Max().z+ON_ZERO_TOLERANCE;
- omesh->vtree.Remove(fMin, fMax, p_id);
- }
-
- // Use the new bbox to set bb
- bb = *bbox;
-
- // Get pnt's associated edges.
- std::set<edge_t> edges = omesh->fmesh->v2edges[p_id];
-
- // find the shortest edge associated with pnt
- std::set<edge_t>::iterator e_it;
- double elen = DBL_MAX;
- for (e_it = edges.begin(); e_it != edges.end(); e_it++) {
- ON_3dPoint *p1 = omesh->fmesh->pnts[(*e_it).v[0]];
- ON_3dPoint *p2 = omesh->fmesh->pnts[(*e_it).v[1]];
- double dist = p1->DistanceTo(*p2);
- elen = (dist < elen) ? dist : elen;
- }
- v_min_edge_len = elen;
-
- // (re)insert the vertex into the parent omesh's vtree, once we're done
- // updating
- fMin[0] = bb.Min().x;
- fMin[1] = bb.Min().y;
- fMin[2] = bb.Min().z;
- fMax[0] = bb.Max().x;
- fMax[1] = bb.Max().y;
- fMax[2] = bb.Max().z;
- if (fMin[0] < -0.4*DBL_MAX || fMax[0] > 0.4*DBL_MAX) {
- std::cout << "Bad vert box!\n";
- }
- omesh->vtree.Insert(fMin, fMax, p_id);
-
- // Once we've gotten here, the vertex is fully initialized
- init = true;
-}
-
-void
-overt_t::update_ring()
-{
- std::set<long> mod_verts;
-
- // 1. Get pnt's associated edges.
- std::set<edge_t> edges = omesh->fmesh->v2edges[p_id];
-
- // 2. Collect all the vertices associated with all the edges connected to
- // the original point - these are the vertices that will have a new
associated
- // edge length after the change, and need to check if they have a new
minimum
- // associated edge length (with its implications for bounding box size).
- std::set<edge_t>::iterator e_it;
- for (e_it = edges.begin(); e_it != edges.end(); e_it++) {
- mod_verts.insert((*e_it).v[0]);
- mod_verts.insert((*e_it).v[1]);
- }
-
- // 3. Update each vertex
- std::set<long>::iterator v_it;
- for (v_it = mod_verts.begin(); v_it != mod_verts.end(); v_it++) {
- omesh->overts[*v_it]->update();
- }
-}
-
-int
-overt_t::adjust(ON_3dPoint &target_point, double dtol)
-{
- ON_3dPoint s_p;
- ON_3dVector s_n;
- bool feval = omesh->fmesh->closest_surf_pnt(s_p, s_n, &target_point, dtol);
- if (feval) {
-
- // See if s_p is an actual move - if not, this is a no-op
- ON_3dPoint p = vpnt();
- if (p.DistanceTo(s_p) < ON_ZERO_TOLERANCE) {
- return 0;
- }
-
- (*omesh->fmesh->pnts[p_id]) = s_p;
- (*omesh->fmesh->normals[omesh->fmesh->nmap[p_id]]) = s_n;
- update();
- // We just changed the vertex point values - need to update all
- // this vertex and all vertices connected to the updated vertex
- // by an edge.
- update_ring();
-
- return 1;
- }
-
- return 0;
-}
-
-
-void
-overt_t::plot(FILE *plot)
-{
- ON_3dPoint *i_p = omesh->fmesh->pnts[p_id];
- ON_BoundingBox_Plot(plot, bb);
- double r = 0.05*bb.Diagonal().Length();
- pl_color(plot, 0, 255, 0);
- plot_pnt_3d(plot, i_p, r, 0);
-}
-
-
-
-/** @} */
-
-// Local Variables:
-// mode: C++
-// tab-width: 8
-// c-basic-offset: 4
-// indent-tabs-mode: t
-// c-file-style: "stroustrup"
-// End:
-// ex: shiftwidth=4 tabstop=8
-
Deleted: brlcad/trunk/src/libbrep/cdt/ovlps.cpp
===================================================================
--- brlcad/trunk/src/libbrep/cdt/ovlps.cpp 2020-08-19 00:37:19 UTC (rev
76838)
+++ brlcad/trunk/src/libbrep/cdt/ovlps.cpp 2020-08-19 00:59:34 UTC (rev
76839)
@@ -1,1545 +0,0 @@
-/* C D T _ O V L P S . C P P
- * BRL-CAD
- *
- * Copyright (c) 2007-2020 United States Government as represented by
- * the U.S. Army Research Laboratory.
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public License
- * version 2.1 as published by the Free Software Foundation.
- *
- * This library is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this file; see the file named COPYING for more
- * information.
- */
-/** @addtogroup libbrep */
-/** @{ */
-/** @file cdt_ovlps.cpp
- *
- * Constrained Delaunay Triangulation of NURBS B-Rep objects.
- *
- * This file is logic specifically for refining meshes to clear
- * overlaps between sets of objects.
- *
- */
-
-#include "common.h"
-#include <iostream>
-#include <numeric>
-#include <queue>
-#include <random>
-#include <string>
-#include "bg/chull.h"
-#include "bg/tri_pt.h"
-#include "bg/tri_tri.h"
-#include "./cdt.h"
-
-void
-plot_active_omeshes(
- std::set<std::pair<cdt_mesh_t *, cdt_mesh_t *>> &check_pairs
- )
-{
- std::set<omesh_t *> a_omesh = itris_omeshes(check_pairs);
- std::set<omesh_t *>::iterator a_it;
- // Plot overlaps with refinement points
- for (a_it = a_omesh.begin(); a_it != a_omesh.end(); a_it++) {
- omesh_t *am = *a_it;
- am->plot();
- }
-}
-
-
-// Functions to build sets of active meshes from the active pairs set
-
-std::set<omesh_t *>
-active_omeshes(std::set<std::pair<cdt_mesh_t *, cdt_mesh_t *>> &check_pairs)
-{
- std::set<omesh_t *> a_omesh;
- std::set<omesh_t *>::iterator a_it;
- // Find the meshes with actual refinement points
- std::set<std::pair<cdt_mesh_t *, cdt_mesh_t *>>::iterator cp_it;
- for (cp_it = check_pairs.begin(); cp_it != check_pairs.end(); cp_it++) {
- omesh_t *omesh1 = cp_it->first->omesh;
- omesh_t *omesh2 = cp_it->second->omesh;
- a_omesh.insert(omesh1);
- a_omesh.insert(omesh2);
- }
-
- return a_omesh;
-}
-
-std::set<omesh_t *>
-refinement_omeshes(std::set<std::pair<cdt_mesh_t *, cdt_mesh_t *>>
&check_pairs)
-{
- std::set<omesh_t *> a_omesh;
- std::set<omesh_t *>::iterator a_it;
- // Find the meshes with actual refinement points
- std::set<std::pair<cdt_mesh_t *, cdt_mesh_t *>>::iterator cp_it;
- for (cp_it = check_pairs.begin(); cp_it != check_pairs.end(); cp_it++) {
- omesh_t *omesh1 = cp_it->first->omesh;
- omesh_t *omesh2 = cp_it->second->omesh;
- if (omesh1->edge_sets.size()) {
- a_omesh.insert(omesh1);
- }
- if (omesh2->edge_sets.size()) {
- a_omesh.insert(omesh2);
- }
- }
-
- return a_omesh;
-}
-
-std::set<omesh_t *>
-itris_omeshes(std::set<std::pair<cdt_mesh_t *, cdt_mesh_t *>> &check_pairs)
-{
- std::set<omesh_t *> a_omesh;
- std::set<omesh_t *>::iterator a_it;
- // Find the meshes with actual refinement points
- std::set<std::pair<cdt_mesh_t *, cdt_mesh_t *>>::iterator cp_it;
- for (cp_it = check_pairs.begin(); cp_it != check_pairs.end(); cp_it++) {
- omesh_t *omesh1 = cp_it->first->omesh;
- omesh_t *omesh2 = cp_it->second->omesh;
- if (omesh1->itris.size()) {
- a_omesh.insert(omesh1);
- }
- if (omesh2->itris.size()) {
- a_omesh.insert(omesh2);
- }
- }
-
- return a_omesh;
-}
-
-/******************************************************************************
- * As a first step, use the face bboxes to narrow down where we have potential
- * interactions between breps
-
******************************************************************************/
-
-struct nf_info {
- std::set<std::pair<cdt_mesh_t *, cdt_mesh_t *>> *check_pairs;
- cdt_mesh_t *cmesh;
-};
-
-static bool NearFacesPairsCallback(void *data, void *a_context) {
- struct nf_info *nf = (struct nf_info *)a_context;
- cdt_mesh_t *omesh = (cdt_mesh_t *)data;
- std::pair<cdt_mesh_t *, cdt_mesh_t *> p1(nf->cmesh, omesh);
- std::pair<cdt_mesh_t *, cdt_mesh_t *> p2(omesh, nf->cmesh);
- if ((nf->check_pairs->find(p1) == nf->check_pairs->end()) &&
(nf->check_pairs->find(p1) == nf->check_pairs->end())) {
- nf->check_pairs->insert(p1);
- }
- return true;
-}
-
-std::set<std::pair<cdt_mesh_t *, cdt_mesh_t *>>
-possibly_interfering_face_pairs(struct ON_Brep_CDT_State **s_a, int s_cnt)
-{
- std::set<std::pair<cdt_mesh_t *, cdt_mesh_t *>> check_pairs;
- RTree<void *, double, 3> rtree_fmeshes;
- for (int i = 0; i < s_cnt; i++) {
- struct ON_Brep_CDT_State *s_i = s_a[i];
- for (int i_fi = 0; i_fi < s_i->brep->m_F.Count(); i_fi++) {
- const ON_BrepFace *i_face = s_i->brep->Face(i_fi);
- ON_BoundingBox bb = i_face->BoundingBox();
- cdt_mesh_t *fmesh = &s_i->fmeshes[i_fi];
- struct nf_info nf;
- nf.cmesh = fmesh;
- nf.check_pairs = &check_pairs;
- double fMin[3];
- fMin[0] = bb.Min().x;
- fMin[1] = bb.Min().y;
- fMin[2] = bb.Min().z;
- double fMax[3];
- fMax[0] = bb.Max().x;
- fMax[1] = bb.Max().y;
- fMax[2] = bb.Max().z;
- // Check the new box against the existing tree, and add any new
- // interaction pairs to check_pairs
- rtree_fmeshes.Search(fMin, fMax, NearFacesPairsCallback, (void
*)&nf);
- // Add the new box to the tree so any additional boxes can check
- // against it as well
- rtree_fmeshes.Insert(fMin, fMax, (void *)fmesh);
- }
- }
-
- return check_pairs;
-}
-
-overt_t *
-nearby_vert(ON_3dPoint &spnt, ON_3dVector &sn, overt_t *v, omesh_t *other_m,
int level)
-{
- // If we already know the answer, just return it and skip all the
calculations...
- if (v->aligned.find(other_m) != v->aligned.end()) {
- overt_t *ov = v->aligned[other_m];
- if (v->alevel[ov] == level) {
- spnt = v->cpoints[ov];
- sn = v->cnorms[ov];
- return ov;
- } else {
- // Alignment was done at another level - closest surface point is
still
- // OK, but vert mapping may not be - erase it and make a new
determination.
- v->aligned.erase(other_m);
- }
- }
-
- // Past the easy case - now we need to do some work. Find the closest
vertex point
- // and the closest surface point/normal.
- double vdist;
- overt_t *v_closest = other_m->vert_closest(&vdist, v);
-
- ON_3dPoint opnt = v->vpnt();
- ON_3dPoint vcpnt = v_closest->vpnt();
- double vo_to_vc = vcpnt.DistanceTo(opnt);
- double spdist = vo_to_vc * 10;
- if (v->cpoints.find(v_closest) != v->cpoints.end() &&
v->cnorms.find(v_closest) != v->cnorms.end()) {
- // If we already have calculated the closest surface point, just reuse
it
- spnt = v->cpoints[v_closest];
- sn = v->cnorms[v_closest];
- } else {
- if (!other_m->fmesh->closest_surf_pnt(spnt, sn, &opnt, spdist)) {
- // If there's no closest surface point within dist, there's probably
- // an error - it should at least have found the v_closest point...
- std::cerr << "Error - couldn't find closest point\n";
- } else {
- v->cpoints[v_closest] = spnt;
- v->cnorms[v_closest] = sn;
- }
- }
-
- // If we're extremely close, just go with v_closest
- if (vdist < 2*ON_ZERO_TOLERANCE) {
- v->alevel[v_closest] = level;
- return v_closest;
- }
-
- // See if the closest vert bbox overlaps the closest surface
- // point to v. If not, there is definitely no nearby vertex defined,
- // since we know spnt is free to be defined as a vertex according
- // to other_m's vertices.
- ON_BoundingBox spbb(spnt, spnt);
- if (v_closest->bb.IsDisjoint(spbb)) {
- return NULL;
- }
-
- // We know v_closest isn't nearby according according to v_closest's bbox,
- // but v_closest may have an arbitrarily sized bbox depending on its
- // associated edge lengths. Hence it may contain spnt even though (from
- // v's perspective) it isn't close. Construct a new bbox using the
- // v_closest point and the box size of v, and repeat the bbox check for
- // spbb.
- ON_BoundingBox v_closest_v_bb(v_closest->vpnt(), v_closest->vpnt());
- ON_3dPoint c1 = vcpnt + v->bb.Diagonal()*0.5;
- ON_3dPoint c2 = vcpnt - v->bb.Diagonal()*0.5;
- v_closest_v_bb.Set(c1, true);
- v_closest_v_bb.Set(c2, true);
- if (v_closest_v_bb.IsDisjoint(spbb)) {
- return NULL;
- }
-
- // If the surface point is close to the closest existing vertex per its
- // bounding box size, report the vertex as nearby. In essence this can be
- // considered an "approximate" nearby vert match, keyed to local edge
- // lengths from involved triangle edges.
- double factor = (level < INT_MAX) ? (1.0/(double)(10 + level)) : 0;
- double cvbbdiag = v_closest->bb.Diagonal().Length() * factor + 2 *
ON_ZERO_TOLERANCE;
- if (vcpnt.DistanceTo(spnt) < cvbbdiag) {
- v->aligned[other_m] = v_closest;
- v->alevel[v_closest] = level;
- return v_closest;
- }
-
- return NULL;
-}
-
-int
-add_refinement_vert(overt_t *v, omesh_t *other_m, int level)
-{
- // If we've already got a matching vertex, we don't change anything because
- // of this vertex.
- ON_3dPoint spnt;
- ON_3dVector sn;
- if (nearby_vert(spnt, sn, v, other_m, level)) {
- return 0;
- }
-
- // If we're close to a brep face edge, needs to go in edge_verts.
- // else, list as a new vert requiring a nearby vert on mesh other_m.
- //
- // What should happen in successive iterations is the following:
- // 1. The first pass will split the brep face edge at the closest
- // point to the near-edge point in question, introducing a new
- // triangle edge and triangles in the vicinity of the nearby vertex.
- //
- // 2. A second pass will then find the closest edge to the same
- // vertex (if the vertex is still intruding) closer to the new
- // interior edge than the original brep face edge, and the categorization
- // of the point will change to an interior point.
- ON_3dPoint vpnt = v->vpnt();
- uedge_t closest_edge = other_m->closest_uedge(vpnt);
- if (other_m->fmesh->brep_edges.find(closest_edge) !=
other_m->fmesh->brep_edges.end()) {
- bedge_seg_t *bseg = other_m->fmesh->ue2b_map[closest_edge];
- if (!bseg) {
- std::cout << "couldn't find bseg pointer??\n";
- return 0;
- } else {
- (*other_m->edge_verts)[bseg].insert(v);
- }
- } else {
- // Point is interior - stash relevant information
- revt_pt_t rpt;
- rpt.spnt = spnt;
- rpt.sn = sn;
- rpt.ov = v;
- other_m->edge_sets[closest_edge].push_back(rpt);
- }
-
- return 1;
-}
-
-
-/* There are three levels of aggressiveness we can use when assigning
refinement points:
- *
- * 1. Only use vertices that share at least two triangles which overlap with
the other mesh
- * 2. Use all vertices from triangles that overlap
- * 3. MAYBE TODO... Use all vertices from the other mesh that are contained
by the bounding box of the
- * overlapping triangle from this mesh.
- */
-size_t
-omesh_refinement_pnts(
- std::set<std::pair<cdt_mesh_t *, cdt_mesh_t *>> check_pairs,
- int level
- )
-{
- std::set<omesh_t *> a_omesh = active_omeshes(check_pairs);
- std::set<omesh_t *>::iterator a_it;
-
- // Clear everything, even if we don't have intersecting triangles
- (*a_omesh.begin())->edge_verts->clear();
- for (a_it = a_omesh.begin(); a_it != a_omesh.end(); a_it++) {
- (*a_it)->edge_sets.clear();
- (*a_it)->ivert_ref_cnts.clear();
- }
-
- a_omesh = itris_omeshes(check_pairs);
- if (!a_omesh.size()) return 0;
-
- // Count triangles to determine which verts need attention. If a vertex
is associated
- // with two or more triangles that intersect another face, it is a
refinement point
- // candidate.
- for (a_it = a_omesh.begin(); a_it != a_omesh.end(); a_it++) {
- omesh_t *am = *a_it;
- std::map<size_t, std::set<std::pair<omesh_t *, size_t>> >::iterator
p_it;
- for (p_it = am->itris.begin(); p_it != am->itris.end(); p_it++) {
- std::set<std::pair<omesh_t *, size_t>>::iterator s_it;
- for (s_it = p_it->second.begin(); s_it != p_it->second.end();
s_it++) {
- omesh_t *im = s_it->first;
- size_t otri_ind = s_it->second;
- triangle_t tri = im->fmesh->tris_vect[otri_ind];
- for (int i = 0; i < 3; i++) {
- overt_t *v = im->overts[tri.v[i]];
- am->ivert_ref_cnts[v].insert(otri_ind);
- }
- }
- }
- }
- for (a_it = a_omesh.begin(); a_it != a_omesh.end(); a_it++) {
- omesh_t *am = *a_it;
- std::map<overt_t *, std::set<long>>::iterator r_it;
- for (r_it = am->ivert_ref_cnts.begin(); r_it !=
am->ivert_ref_cnts.end(); r_it++) {
- //VPCHECK(r_it->first, NULL);
- // If there are enough activity hits, we need a nearby vertex
- if (r_it->second.size() > 1 || level > 0) {
- add_refinement_vert(r_it->first, am, level);
- }
- }
- }
-
- //plot_active_omeshes(check_pairs, NULL);
-
- // Add triangle intersection vertices that are close to the edge of the
opposite
- // triangle, whether or not they satisfy the count criteria - these are a
source
- // of potential trouble.
- if (!level) {
- for (a_it = a_omesh.begin(); a_it != a_omesh.end(); a_it++) {
- omesh_t *am = *a_it;
- std::map<size_t, std::set<std::pair<omesh_t *, size_t>> >::iterator
p_it;
- for (p_it = am->itris.begin(); p_it != am->itris.end(); p_it++) {
- triangle_t t1 = am->fmesh->tris_vect[p_it->first];
- std::set<std::pair<omesh_t *, size_t>>::iterator s_it;
- for (s_it = p_it->second.begin(); s_it != p_it->second.end();
s_it++) {
- omesh_t *im = s_it->first;
- size_t otri_ind = s_it->second;
- triangle_t t2 = im->fmesh->tris_vect[otri_ind];
- tri_nearedge_refine(t1, t2, level);
- }
- }
- }
- }
-
- size_t rcnt = 0;
- for (a_it = a_omesh.begin(); a_it != a_omesh.end(); a_it++) {
- omesh_t *am = *a_it;
- rcnt += am->edge_sets.size();
- }
-
- plot_active_omeshes(check_pairs);
-
- return rcnt;
-}
-
-bool
-omesh_smooth(std::set<std::pair<cdt_mesh_t *, cdt_mesh_t *>> check_pairs)
-{
- std::set<omesh_t *> a_omesh = active_omeshes(check_pairs);
- std::set<omesh_t *>::iterator a_it;
-
- for (a_it = a_omesh.begin(); a_it != a_omesh.end(); a_it++) {
- omesh_t *am = *a_it;
- if (!am->fmesh->optimize()) {
- return false;
- }
- // Need to update vertex bboxes after changing triangles!
- std::set<triangle_t>::iterator n_it;
- std::set<overt_t *> tri_verts;
- for (n_it = am->fmesh->new_tris.begin(); n_it !=
am->fmesh->new_tris.end(); n_it++) {
- for (int i = 0; i < 3; i++) {
- tri_verts.insert(am->overts[(*n_it).v[i]]);
- }
- }
- std::set<overt_t *>::iterator o_it;
- for (o_it = tri_verts.begin(); o_it != tri_verts.end(); o_it++) {
- (*o_it)->update();
- }
- }
-
- return true;
-}
-
-size_t
-omesh_ovlps(std::set<std::pair<cdt_mesh_t *, cdt_mesh_t *>> check_pairs, int
mode)
-{
- size_t tri_isects = 0;
-
- // Assemble the set of mesh faces that (per the check_pairs sets) we
- // may need to process.
- std::set<omesh_t *> a_omesh = active_omeshes(check_pairs);
- std::set<omesh_t *>::iterator a_it;
-
- // Scrub the old data in active mesh containers (if any)
- for (a_it = a_omesh.begin(); a_it != a_omesh.end(); a_it++) {
- omesh_t *am = *a_it;
- am->itris.clear();
- am->intruding_tris.clear();
- }
- a_omesh.clear();
-
- // Intersect first the triangle RTrees, then any potentially
- // overlapping triangles found within the leaves.
- std::set<std::pair<cdt_mesh_t *, cdt_mesh_t *>>::iterator cp_it;
- for (cp_it = check_pairs.begin(); cp_it != check_pairs.end(); cp_it++) {
- omesh_t *omesh1 = cp_it->first->omesh;
- omesh_t *omesh2 = cp_it->second->omesh;
- struct ON_Brep_CDT_State *s_cdt1 = (struct ON_Brep_CDT_State
*)omesh1->fmesh->p_cdt;
- struct ON_Brep_CDT_State *s_cdt2 = (struct ON_Brep_CDT_State
*)omesh2->fmesh->p_cdt;
- if (s_cdt1 != s_cdt2) {
- std::set<std::pair<size_t, size_t>> tris_prelim;
- size_t ovlp_cnt =
omesh1->fmesh->tris_tree.Overlaps(omesh2->fmesh->tris_tree, &tris_prelim);
- if (ovlp_cnt) {
- std::set<std::pair<size_t, size_t>>::iterator tb_it;
- for (tb_it = tris_prelim.begin(); tb_it != tris_prelim.end();
tb_it++) {
- triangle_t t1 = omesh1->fmesh->tris_vect[tb_it->first];
- triangle_t t2 = omesh2->fmesh->tris_vect[tb_it->second];
- int isect = tri_isect(t1, t2, mode);
- if (isect) {
- omesh1->itris[t1.ind].insert(std::make_pair(omesh2,
t2.ind));
- omesh2->itris[t2.ind].insert(std::make_pair(omesh1,
t1.ind));
- omesh1->intruding_tris.insert(t1.ind);
- omesh2->intruding_tris.insert(t2.ind);
- a_omesh.insert(omesh1);
- a_omesh.insert(omesh2);
- tri_isects++;
- }
- }
- }
- }
- }
-
- //plot_active_omeshes(check_pairs, NULL);
-
- return tri_isects;
-}
-
-void
-flip_tri(triangle_t &t)
-{
- long tmp = t.v[2];
- t.v[2] = t.v[1];
- t.v[1] = tmp;
-}
-
-bool
-orient_tri(cdt_mesh_t &fmesh, triangle_t &t)
-{
- ON_3dVector tdir = fmesh.tnorm(t);
- ON_3dVector bdir = fmesh.bnorm(t);
- bool flipped_tri = (ON_DotProduct(tdir, bdir) < 0);
- if (flipped_tri) {
- long tmp = t.v[2];
- t.v[2] = t.v[1];
- t.v[1] = tmp;
- return true;
- }
- return false;
-}
-
-int
-ovlp_split_interior_edge(overt_t **nv, std::set<long> &ntris, omesh_t *omesh,
uedge_t &ue)
-{
- std::set<overt_t *> overts_to_update;
-
- // Find the two triangles that we will be using to form the outer polygon
- std::set<size_t> rtris = omesh->fmesh->uedges2tris[ue];
- if (rtris.size() != 2) {
- std::cout << "Error - could not associate uedge with two triangles??\n";
- return -1;
- }
- std::set<size_t> crtris = rtris;
- triangle_t tri1 = omesh->fmesh->tris_vect[*crtris.begin()];
- crtris.erase(crtris.begin());
- triangle_t tri2 = omesh->fmesh->tris_vect[*crtris.begin()];
- crtris.erase(crtris.begin());
-
- cpolygon_t *polygon = omesh->fmesh->uedge_polygon(ue);
-
- // Add interior point.
- ON_3dPoint epnt = (*omesh->fmesh->pnts[ue.v[0]] +
*omesh->fmesh->pnts[ue.v[1]]) * 0.5;
- double spdist =
omesh->fmesh->pnts[ue.v[0]]->DistanceTo(*omesh->fmesh->pnts[ue.v[1]]);
- ON_3dPoint spnt;
- ON_3dVector sn;
- if (!omesh->fmesh->closest_surf_pnt(spnt, sn, &epnt, spdist*10)) {
- std::cerr << "Error - couldn't find closest point\n";
- delete polygon;
- return -1;
- }
- // Base the bbox on the edge length, since we don't have any topology yet.
- ON_BoundingBox sbb(spnt,spnt);
- ON_3dPoint sbb1 = spnt - ON_3dPoint(.1*spdist, .1*spdist, .1*spdist);
- ON_3dPoint sbb2 = spnt + ON_3dPoint(.1*spdist, .1*spdist, .1*spdist);
- sbb.Set(sbb1, true);
- sbb.Set(sbb2, true);
-
- // We're going to use it - add new 3D point
- long f3ind = omesh->fmesh->add_point(new ON_3dPoint(spnt));
- long fnind = omesh->fmesh->add_normal(new ON_3dPoint(sn));
- struct ON_Brep_CDT_State *s_cdt = (struct ON_Brep_CDT_State
*)omesh->fmesh->p_cdt;
- CDT_Add3DPnt(s_cdt, omesh->fmesh->pnts[f3ind], omesh->fmesh->f_id, -1, -1,
-1, 0, 0);
- CDT_Add3DNorm(s_cdt, omesh->fmesh->normals[fnind],
omesh->fmesh->pnts[f3ind], omesh->fmesh->f_id, -1, -1, -1, 0, 0);
- omesh->fmesh->nmap[f3ind] = fnind;
- overt_t *nvrt = omesh->vert_add(f3ind, &sbb);
- overts_to_update.insert(nvrt);
-
- // The 'old' triangles may themselves have been newly introduced - we're
now going to remove
- // them from the mesh regardless, so make sure the ntris set doesn't
include them any more.
- ntris.erase(tri1.ind);
- ntris.erase(tri2.ind);
-
- // Split the old triangles, perform the removals and add the new triangles
- int new_tris = 0;
- std::set<triangle_t>::iterator s_it;
- std::set<triangle_t> t1_tris = tri1.split(ue, f3ind, false);
- omesh->fmesh->tri_remove(tri1);
- for (s_it = t1_tris.begin(); s_it != t1_tris.end(); s_it++) {
- triangle_t vt = *s_it;
- omesh->fmesh->tri_add(vt);
- ntris.insert(omesh->fmesh->tris_vect.size() - 1);
- // In addition to the genuinely new vertices, altered triangles
- // may need updated vert bboxes
- for (int i = 0; i < 3; i++) {
- overts_to_update.insert(omesh->overts[vt.v[i]]);
- }
- new_tris++;
- }
- std::set<triangle_t> t2_tris = tri2.split(ue, f3ind, false);
- omesh->fmesh->tri_remove(tri2);
- for (s_it = t2_tris.begin(); s_it != t2_tris.end(); s_it++) {
- triangle_t vt = *s_it;
- omesh->fmesh->tri_add(vt);
- ntris.insert(omesh->fmesh->tris_vect.size() - 1);
- // In addition to the genuinely new vertices, altered triangles
- // may need updated vert bboxes
- for (int i = 0; i < 3; i++) {
- overts_to_update.insert(omesh->overts[vt.v[i]]);
- }
- new_tris++;
- }
-
- // Have new triangles, update overts
- std::set<overt_t *>::iterator n_it;
- for (n_it = overts_to_update.begin(); n_it != overts_to_update.end();
n_it++) {
- (*n_it)->update();
- }
-
- (*nv) = nvrt;
-
- //omesh->fmesh->valid(1);
-
- return new_tris;
-}
-
-
-static int
-interior_edge_verts(omesh_t *omesh)
-{
- struct ON_Brep_CDT_State *s_cdt = (struct ON_Brep_CDT_State
*)omesh->fmesh->p_cdt;
-
- //std::cout << "Processing " << s_cdt->name << " face " <<
omesh->fmesh->f_id << ":\n";
-
- std::map<uedge_t, std::vector<revt_pt_t>>::iterator es_it;
-
- int new_tris = 0;
-
- std::map<uedge_t, std::vector<revt_pt_t>> wedge_sets = omesh->edge_sets;
-
- while (wedge_sets.size()) {
- std::map<uedge_t, std::vector<revt_pt_t>> updated_esets;
-
- uedge_t ue = wedge_sets.begin()->first;
- std::vector<revt_pt_t> epnts = wedge_sets.begin()->second;
- wedge_sets.erase(wedge_sets.begin());
-
- // Find the two triangles that we will be using to form the outer
polygon
- std::set<size_t> rtris = omesh->fmesh->uedges2tris[ue];
- if (rtris.size() != 2) {
- std::cout << "Error - could not associate uedge with two
triangles??\n";
- }
- std::set<size_t> crtris = rtris;
- triangle_t tri1 = omesh->fmesh->tris_vect[*crtris.begin()];
- crtris.erase(crtris.begin());
- triangle_t tri2 = omesh->fmesh->tris_vect[*crtris.begin()];
- crtris.erase(crtris.begin());
-
- // For the involved triangle edges that are not the edge to be removed,
we will
- // need to reassess their closest edge assignment after new edges are
added.
- // Build up the set of those uedges for later processing. While we are
looping,
- // get initial data for the polygon build.
- std::set<uedge_t> pnt_reassignment_edges;
- std::set<size_t>::iterator r_it;
- for (r_it = rtris.begin(); r_it != rtris.end(); r_it++) {
- triangle_t tri = omesh->fmesh->tris_vect[*r_it];
- std::set<uedge_t> tuedges = omesh->fmesh->uedges(tri);
- pnt_reassignment_edges.insert(tuedges.begin(), tuedges.end());
- }
- pnt_reassignment_edges.erase(ue);
-
-
- cpolygon_t *polygon = omesh->fmesh->uedge_polygon(ue);
-
-#if 0
- {
- FILE *t1plot = fopen("t1.plot", "w");
- struct bu_color c = BU_COLOR_INIT_ZERO;
- unsigned char rgb[3] = {0,0,255};
- bu_color_from_rgb_chars(&c, (const unsigned char *)rgb);
- omesh->fmesh->plot_tri(tri1, &c, t1plot, 255, 0, 0);
- fclose(t1plot);
- }
- {
- FILE *t2plot = fopen("t2.plot", "w");
- struct bu_color c = BU_COLOR_INIT_ZERO;
- unsigned char rgb[3] = {0,0,255};
- bu_color_from_rgb_chars(&c, (const unsigned char *)rgb);
- omesh->fmesh->plot_tri(tri2, &c, t2plot, 255, 0, 0);
- fclose(t2plot);
- }
-#endif
-
- // Add any interior points to the polygon before cdt.
- std::set<overt_t *> overts_to_update;
- bool have_inside = false;
- for (size_t i = 0; i < epnts.size(); i++) {
- bool skip_epnt = false;
-
- VPCHECK(epnts[i].ov, NULL);
-
- ON_BoundingBox sbb(epnts[i].spnt,epnts[i].spnt);
- ON_3dVector vmin = epnts[i].ov->bb.Min() - epnts[i].ov->bb.Center();
- ON_3dVector vmax = epnts[i].ov->bb.Max() - epnts[i].ov->bb.Center();
- vmin.Unitize();
- vmax.Unitize();
- vmin = vmin * epnts[i].ov->bb.Diagonal().Length() * 0.5;
- vmax = vmax * epnts[i].ov->bb.Diagonal().Length() * 0.5;
- sbb.m_min = epnts[i].spnt + vmin;
- sbb.m_max = epnts[i].spnt + vmax;
-
-
- double vdist;
- overt_t *v_closest = omesh->vert_closest(&vdist, epnts[i].spnt);
- double cvbbdiag = v_closest->bb.Diagonal().Length() * 0.1;
- if (vdist < cvbbdiag) {
- // Too close to a vertex in the current mesh, skip
- //std::cout << "skip epnt, too close to vert\n";
- continue;
- }
-
- // If the point is too close to a brep face edge,
- // we also need to reject it to avoid creating degenerate
- // triangles
- std::set<uedge_t>::iterator ue_it;
- std::set<uedge_t> b_ue_1 = omesh->fmesh->b_uedges(tri1);
- for (ue_it = b_ue_1.begin(); ue_it != b_ue_1.end(); ue_it++) {
- uedge_t lue = *ue_it;
- double epdist = omesh->fmesh->uedge_dist(lue, epnts[i].spnt);
- ON_Line lline(*omesh->fmesh->pnts[lue.v[0]],
*omesh->fmesh->pnts[lue.v[1]]);
- if (epdist < 0.001 * lline.Length()) {
- //std::cout << "Close to brep face edge\n";
- skip_epnt = true;
- break;
- }
- }
- if (skip_epnt) {
- continue;
- }
- std::set<uedge_t> b_ue_2 = omesh->fmesh->b_uedges(tri2);
- for (ue_it = b_ue_2.begin(); ue_it != b_ue_2.end(); ue_it++) {
- uedge_t lue = *ue_it;
- double epdist = omesh->fmesh->uedge_dist(lue, epnts[i].spnt);
- ON_Line lline(*omesh->fmesh->pnts[lue.v[0]],
*omesh->fmesh->pnts[lue.v[1]]);
- if (epdist < 0.001 * lline.Length()) {
- //std::cout << "Close to brep face edge\n";
- skip_epnt = true;
- break;
- }
- }
- if (skip_epnt) {
- continue;
- }
-
- bool inside = false;
- {
- // Use the overt point for this - the closest surface point will
- // always pass, so it's not usable for rejection.
- ON_3dPoint ovpnt = epnts[i].ov->vpnt();
- double u, v;
- polygon->tplane.ClosestPointTo(ovpnt, &u, &v);
- std::pair<double, double> proj_2d;
- proj_2d.first = u;
- proj_2d.second = v;
- polygon->pnts_2d.push_back(proj_2d);
- inside = polygon->point_in_polygon(polygon->pnts_2d.size() - 1,
false);
- polygon->pnts_2d.pop_back();
- }
- if (inside) {
- ON_3dPoint p = epnts[i].spnt;
- double u, v;
- polygon->tplane.ClosestPointTo(p, &u, &v);
- std::pair<double, double> proj_2d;
- proj_2d.first = u;
- proj_2d.second = v;
- polygon->pnts_2d.push_back(proj_2d);
- size_t p2dind = polygon->pnts_2d.size() - 1;
-
- // We're going to use it - add new 3D point to CDT
- long f3ind = omesh->fmesh->add_point(new
ON_3dPoint(epnts[i].spnt));
- long fnind = omesh->fmesh->add_normal(new
ON_3dPoint(epnts[i].sn));
- CDT_Add3DPnt(s_cdt, omesh->fmesh->pnts[f3ind],
omesh->fmesh->f_id, -1, -1, -1, 0, 0);
- CDT_Add3DNorm(s_cdt, omesh->fmesh->normals[fnind],
omesh->fmesh->pnts[f3ind], omesh->fmesh->f_id, -1, -1, -1, 0, 0);
- omesh->fmesh->nmap[f3ind] = fnind;
- overt_t *nvrt = omesh->vert_add(f3ind, &sbb);
- overts_to_update.insert(nvrt);
- polygon->p2o[p2dind] = f3ind;
- polygon->interior_points.insert(p2dind);
-
- have_inside = true;
- }
-
- }
-
- if (!have_inside) {
- // No point in doing this if none of the points are interior
- delete polygon;
- continue;
- }
-
- polygon->cdt();
- //omesh->fmesh->boundary_edges_plot("bedges.plot3");
-
- if (polygon->tris.size()) {
- unsigned char rgb[3] = {0,255,255};
- struct bu_color c = BU_COLOR_INIT_ZERO;
- bu_color_from_rgb_chars(&c, (const unsigned char *)rgb);
- omesh->fmesh->tri_remove(tri1);
- omesh->fmesh->tri_remove(tri2);
- std::set<triangle_t>::iterator v_it;
- for (v_it = polygon->tris.begin(); v_it != polygon->tris.end();
v_it++) {
- triangle_t vt = *v_it;
- orient_tri(*omesh->fmesh, vt);
- omesh->fmesh->tri_add(vt);
- // In addition to the genuinely new vertices, altered triangles
- // may need updated vert bboxes
- for (int i = 0; i < 3; i++) {
- overts_to_update.insert(omesh->overts[vt.v[i]]);
- }
- }
-
- new_tris += polygon->tris.size();
-
- //omesh->fmesh->tris_set_plot(polygon->tris, "poly_tris.plot3");
- //polygon->polygon_plot_in_plane("poly.plot3");
- } else {
- std::cout << "polygon cdt failed!\n";
- bu_file_delete("tri_replace_pair_fail.plot3");
- polygon->polygon_plot_in_plane("tri_replace_pair_fail.plot3");
- }
-
- if (!omesh->fmesh->valid(1)) {
- std::cout << "CDT broke mesh!\n";
- polygon->polygon_plot_in_plane("poly.plot3");
- bu_exit(1, "Fatal cdt error\n");
- }
- delete polygon;
-
- // Have new triangles, update overts
- std::set<overt_t *>::iterator n_it;
- for (n_it = overts_to_update.begin(); n_it != overts_to_update.end();
n_it++) {
- (*n_it)->update();
- }
-
- // Reassign points to their new closest edge (may be the same edge, but
we need
- // to check)
- std::set<uedge_t>::iterator pre_it;
- for (pre_it = pnt_reassignment_edges.begin(); pre_it !=
pnt_reassignment_edges.end(); pre_it++) {
- uedge_t rue = *pre_it;
- std::vector<revt_pt_t> old_epnts = wedge_sets[rue];
- std::map<uedge_t, std::vector<revt_pt_t>>::iterator er_it =
wedge_sets.find(rue);
- wedge_sets.erase(er_it);
- for (size_t i = 0; i < old_epnts.size(); i++) {
- overt_t *ov = old_epnts[i].ov;
- std::set<uedge_t> close_edges =
omesh->interior_uedges_search(ov->bb);
- double mindist = DBL_MAX;
- uedge_t closest_uedge;
- std::set<uedge_t>::iterator c_it;
- for (c_it = close_edges.begin(); c_it != close_edges.end();
c_it++) {
- uedge_t cue = *c_it;
- double dline = omesh->fmesh->uedge_dist(cue,
old_epnts[i].spnt);
- if (mindist > dline) {
- closest_uedge = cue;
- mindist = dline;
- }
- }
-
- wedge_sets[closest_uedge].push_back(old_epnts[i]);
- }
- }
- }
-
- return new_tris;
-}
-
-
-static overt_t *
-get_largest_overt(std::set<overt_t *> &verts)
-{
- double elen = 0;
- overt_t *l = NULL;
- std::set<overt_t *>::iterator v_it;
- for (v_it = verts.begin(); v_it != verts.end(); v_it++) {
- overt_t *v = *v_it;
- if (v->min_len() > elen) {
- elen = v->min_len();
- l = v;
- }
- }
- return l;
-}
-
-static overt_t *
-closest_overt(std::set<overt_t *> &verts, overt_t *v)
-{
- overt_t *closest = NULL;
- double dist = DBL_MAX;
- ON_3dPoint p1 = *v->omesh->fmesh->pnts[v->p_id];
- std::set<overt_t *>::iterator v_it;
- for (v_it = verts.begin(); v_it != verts.end(); v_it++) {
- overt_t *c = *v_it;
- ON_3dPoint p2 = *c->omesh->fmesh->pnts[c->p_id];
- double d = p1.DistanceTo(p2);
- if (dist > d) {
- closest = c;
- dist = d;
- }
- }
- return closest;
-}
-
-// TODO - right now, we've locked brep face edge points. This
-// isn't ideal, as we could in principle move those points locally
-// along the edge curve to align with other points. This way we
-// end up with small triangles to handle fixed edge points. However,
-// adjusting the brep edge points will involved local knowledge
-// on the part of each edge vertex about the distances to the next
-// edge vertices on either side, as well as updating the corresponding
-// vert values throughout the data structures.
-//
-// Return how many vertices were actually moved a significant distance
-// per their bounding box dimensions
-static int
-adjust_overt_pair(overt_t *v1, overt_t *v2)
-{
-#if 0
- v1->omesh->near_verts.erase(v2);
- v2->omesh->near_verts.erase(v1);
-#endif
-
- // If we've got two edge vertices, no dice
- if (v1->edge_vert() && v2->edge_vert()) return 0;
-
- ON_3dPoint p1 = v1->vpnt();
- ON_3dPoint p2 = v2->vpnt();
- double pdist = p1.DistanceTo(p2);
- ON_3dPoint s1_p, s2_p;
- ON_3dVector s1_n, s2_n;
-
- if (v1->edge_vert()) {
- // It's all up to v2 - if we're too far away, skip it
- if (pdist > v2->min_len()*0.5) {
- return 0;
- }
- return v2->adjust(p1, pdist);
- }
-
- if (v2->edge_vert()) {
- // It's all up to v1 - if we're too far away, skip it
- if (pdist > v1->min_len()*0.5) {
- return 0;
- }
- return v1->adjust(p2, pdist);
- }
-
- ON_Line l(p1,p2);
- // Weight the t parameter on the line so we are closer to the vertex
- // with the shorter edge length (i.e. less freedom to move without
- // introducing locally severe mesh distortions.)
- double t = 1 - (v2->min_len() / (v1->min_len() + v2->min_len()));
- ON_3dPoint p_wavg = l.PointAt(t);
- if ((p1.DistanceTo(p_wavg) > v1->min_len()*0.5) || (p2.DistanceTo(p_wavg)
> v2->min_len()*0.5)) {
- std::cout << "WARNING: large point shift compared to triangle edge
length.\n";
- }
-
- int adj_cnt = 0;
- adj_cnt += v1->adjust(p_wavg, pdist);
- adj_cnt += v2->adjust(p_wavg, pdist);
-
- return adj_cnt;
-}
-
-static size_t
-adjust_close_verts(std::set<std::pair<cdt_mesh_t *, cdt_mesh_t *>>
&check_pairs)
-{
- std::map<overt_t *, std::set<overt_t*>> vert_ovlps;
- std::set<std::pair<cdt_mesh_t *, cdt_mesh_t *>>::iterator cp_it;
- for (cp_it = check_pairs.begin(); cp_it != check_pairs.end(); cp_it++) {
- omesh_t *omesh1 = cp_it->first->omesh;
- omesh_t *omesh2 = cp_it->second->omesh;
- struct ON_Brep_CDT_State *s_cdt1 = (struct ON_Brep_CDT_State
*)omesh1->fmesh->p_cdt;
- struct ON_Brep_CDT_State *s_cdt2 = (struct ON_Brep_CDT_State
*)omesh2->fmesh->p_cdt;
- if (s_cdt1 == s_cdt2) continue;
-#if 0
- struct bu_vls fname = BU_VLS_INIT_ZERO;
- bu_vls_sprintf(&fname, "%s-%d-vtree.plot3", s_cdt1->name,
omesh1->fmesh->f_id);
- omesh1->plot_vtree(bu_vls_cstr(&fname));
- bu_vls_sprintf(&fname, "%s-%d-vtree.plot3", s_cdt2->name,
omesh2->fmesh->f_id);
- omesh2->plot_vtree(bu_vls_cstr(&fname));
- bu_vls_free(&fname);
- std::cout << "omesh1 vtree cnt: " << omesh1->vtree.Count() << "\n";
- std::cout << "omesh2 vtree cnt: " << omesh2->vtree.Count() << "\n";
-#endif
- std::set<std::pair<long, long>> vert_pairs = omesh1->vert_ovlps(omesh2);
- //std::cout << "(" << s_cdt1->name << "," << omesh1->fmesh->f_id <<
")+(" << s_cdt2->name << "," << omesh2->fmesh->f_id << "): " <<
vert_pairs.size() << " vert box overlaps\n";
- std::set<std::pair<long, long>>::iterator v_it;
- for (v_it = vert_pairs.begin(); v_it != vert_pairs.end(); v_it++) {
- long v_first = (long)v_it->first;
- long v_second = (long)v_it->second;
- overt_t *v1 = omesh1->overts[v_first];
- overt_t *v2 = omesh2->overts[v_second];
- vert_ovlps[v1].insert(v2);
- vert_ovlps[v2].insert(v1);
- }
- }
- std::cout << "Found " << vert_ovlps.size() << " vertices with box
overlaps\n";
-
-
- std::queue<std::pair<overt_t *, overt_t *>> vq;
- std::set<overt_t *> vq_multi;
- std::map<overt_t *, std::set<overt_t*>>::iterator vo_it;
- for (vo_it = vert_ovlps.begin(); vo_it != vert_ovlps.end(); vo_it++) {
- overt_t *v = vo_it->first;
- if (vo_it->second.size() > 1) {
- vq_multi.insert(v);
- continue;
- }
- overt_t *v_other = *vo_it->second.begin();
- if (vert_ovlps[v_other].size() > 1) {
- // The other point has multiple overlapping points
- vq_multi.insert(v);
- continue;
- }
- // Both v and it's companion only have one overlapping point
- vq.push(std::make_pair(v,v_other));
- v->aligned[v_other->omesh] = v_other;
- v_other->aligned[v->omesh] = v;
- }
-
- std::cout << "Have " << vq.size() << " simple interactions\n";
- std::cout << "Have " << vq_multi.size() << " complex interactions\n";
- std::set<overt_t *> adjusted;
-
- int adjusted_overts = 0;
- while (!vq.empty()) {
- std::pair<overt_t *, overt_t *> vpair = vq.front();
- vq.pop();
-
- if (adjusted.find(vpair.first) == adjusted.end() &&
adjusted.find(vpair.second) == adjusted.end()) {
- adjusted_overts += adjust_overt_pair(vpair.first, vpair.second);
- adjusted.insert(vpair.first);
- adjusted.insert(vpair.second);
- }
- }
-
- // If the box structure is more complicated, we need to be a bit selective
- while (vq_multi.size()) {
- overt_t *l = get_largest_overt(vq_multi);
- if (!l) {
- vq_multi.erase(vq_multi.begin());
- continue;
- }
- overt_t *c = closest_overt(vert_ovlps[l], l);
- vq_multi.erase(l);
- vq_multi.erase(c);
- vert_ovlps[l].erase(c);
- vert_ovlps[c].erase(l);
- //std::cout << "COMPLEX - adjusting 1 pair only:\n";
- if (adjusted.find(l) == adjusted.end() && adjusted.find(c) ==
adjusted.end()) {
- adjusted_overts += adjust_overt_pair(l, c);
- adjusted.insert(l);
- adjusted.insert(c);
- l->aligned[c->omesh] = c;
- c->aligned[l->omesh] = l;
- }
- }
-
- return adjusted_overts;
-}
-
-
-static void
-replace_edge_split_tri(cdt_mesh_t &fmesh, size_t t_id, long np_id, uedge_t
&split_edge)
-{
- triangle_t &t = fmesh.tris_vect[t_id];
- std::set<triangle_t> ntris = t.split(split_edge, np_id, false);
-
- fmesh.tri_remove(t);
- std::set<triangle_t>::iterator t_it;
- for (t_it = ntris.begin(); t_it != ntris.end(); t_it++) {
- triangle_t nt = *t_it;
- fmesh.tri_add(nt);
- }
-}
-
-int
-ovlp_split_edge(
- overt_t **nv1,
- overt_t **nv2,
- std::set<bedge_seg_t *> *nsegs,
- bedge_seg_t *eseg, double t
- )
-{
- int replaced_tris = 0;
-
- std::vector<std::pair<cdt_mesh_t *,uedge_t>> uedges = eseg->uedges();
-
- cdt_mesh_t *fmesh_f1 = uedges[0].first;
- cdt_mesh_t *fmesh_f2 = uedges[1].first;
-
- int f_id1 = fmesh_f1->f_id;
- int f_id2 = fmesh_f2->f_id;
-
- uedge_t ue1 = uedges[0].second;
- uedge_t ue2 = uedges[1].second;
-
- std::set<size_t> f1_tris = fmesh_f1->uedges2tris[ue1];
- std::set<size_t> f2_tris = fmesh_f2->uedges2tris[ue2];
-
- size_t tris_cnt = 0;
- if (fmesh_f1->f_id == fmesh_f2->f_id) {
- std::set<size_t> f_alltris;
- f_alltris.insert(f1_tris.begin(), f1_tris.end());
- f_alltris.insert(f2_tris.begin(), f2_tris.end());
- tris_cnt = f_alltris.size();
- } else {
- tris_cnt = f1_tris.size() + f2_tris.size();
- }
- if (tris_cnt != 2) {
- if (f1_tris.size() != 1 || ((fmesh_f1->f_id == fmesh_f2->f_id) &&
(f1_tris.size() != 2))) {
- std::cerr << "FATAL: could not find expected triangle in mesh " <<
fmesh_f1->name << "," << f_id1 << " using uedge " << ue1.v[0] << "," <<
ue1.v[1] << "\n";
- ON_3dPoint v1 = *fmesh_f1->pnts[ue1.v[0]];
- ON_3dPoint v2 = *fmesh_f1->pnts[ue1.v[1]];
- std::cerr << "ue1.v[0]: " << v1.x << "," << v1.y << "," << v1.z <<
"\n";
- std::cerr << "ue1.v[1]: " << v2.x << "," << v2.y << "," << v2.z <<
"\n";
- CDT_Audit((struct ON_Brep_CDT_State *)eseg->p_cdt);
- CDT_Audit((struct ON_Brep_CDT_State *)fmesh_f1->p_cdt);
- exit(1);
- }
- if (f2_tris.size() != 1 || ((fmesh_f1->f_id == fmesh_f2->f_id) &&
(f2_tris.size() != 2))) {
- std::cerr << "FATAL: could not find expected triangle in mesh " <<
fmesh_f2->name << "," << f_id2 << " using uedge " << ue2.v[0] << "," <<
ue2.v[1] << "\n";
- ON_3dPoint v1 = *fmesh_f2->pnts[ue2.v[0]];
- ON_3dPoint v2 = *fmesh_f2->pnts[ue2.v[1]];
- std::cerr << "ue2.v[0]: " << v1.x << "," << v1.y << "," << v1.z <<
"\n";
- std::cerr << "ue2.v[1]: " << v2.x << "," << v2.y << "," << v2.z <<
"\n";
- CDT_Audit((struct ON_Brep_CDT_State *)eseg->p_cdt);
- CDT_Audit((struct ON_Brep_CDT_State *)fmesh_f2->p_cdt);
- exit(1);
- }
- ON_3dPoint ue1_p1 = *fmesh_f1->pnts[ue1.v[0]];
- ON_3dPoint ue1_p2 = *fmesh_f1->pnts[ue1.v[1]];
- std::cout << fmesh_f1->name << "," << f_id1 << " ue1: " << ue1.v[0] <<
"," << ue1.v[1] << ": " << ue1_p1.x << "," << ue1_p1.y << "," << ue1_p1.z << "
-> " << ue1_p2.x << "," << ue1_p2.y << "," << ue1_p2.z << "\n";
- ON_3dPoint ue2_p1 = *fmesh_f2->pnts[ue2.v[0]];
- ON_3dPoint ue2_p2 = *fmesh_f2->pnts[ue2.v[1]];
- std::cout << fmesh_f2->name << "," << f_id2 << " ue2: " << ue2.v[0] <<
"," << ue2.v[1] << ": " << ue2_p1.x << "," << ue2_p1.y << "," << ue2_p1.z << "
-> " << ue2_p2.x << "," << ue2_p2.y << "," << ue2_p2.z << "\n";
- return -1;
- }
-
- // We're replacing the edge and its triangles - clear old data
- // from the containers
- fmesh_f1->brep_edges.erase(ue1);
- fmesh_f2->brep_edges.erase(ue2);
- fmesh_f1->ue2b_map.erase(ue1);
- fmesh_f2->ue2b_map.erase(ue2);
-
- int eind = eseg->edge_ind;
- struct ON_Brep_CDT_State *s_cdt_edge = (struct ON_Brep_CDT_State
*)eseg->p_cdt;
- std::set<bedge_seg_t *> epsegs = s_cdt_edge->e2polysegs[eind];
- epsegs.erase(eseg);
- std::set<bedge_seg_t *> esegs_split = split_edge_seg(s_cdt_edge, eseg, 1,
&t, 1);
- if (!esegs_split.size()) {
- std::cerr << "SPLIT FAILED!\n";
- return -1;
- }
-
- if (nsegs) {
- (*nsegs).insert(esegs_split.begin(), esegs_split.end());
- }
-
- epsegs.insert(esegs_split.begin(), esegs_split.end());
- s_cdt_edge->e2polysegs[eind].clear();
- s_cdt_edge->e2polysegs[eind] = epsegs;
- std::set<bedge_seg_t *>::iterator es_it;
- for (es_it = esegs_split.begin(); es_it != esegs_split.end(); es_it++) {
- bedge_seg_t *es = *es_it;
-
- std::vector<std::pair<cdt_mesh_t *,uedge_t>> nuedges = es->uedges();
- cdt_mesh_t *f1 = nuedges[0].first;
- cdt_mesh_t *f2 = nuedges[1].first;
- uedge_t ue_1 = nuedges[0].second;
- uedge_t ue_2 = nuedges[1].second;
-
- f1->brep_edges.insert(ue_1);
- f2->brep_edges.insert(ue_2);
- f1->ue2b_map[ue_1] = es;
- f2->ue2b_map[ue_2] = es;
- }
-
- // Need to return one of the inserted verts from this process - we need to
- // check if that point is going to require any splitting on any other
- // objects' faces. Any triangle from another object "close" to the new
- // point should have a vertex that can be adjusted, or if not one needs to
- // be introduced.
- long np_id;
- if (f_id1 == f_id2) {
- std::set<size_t> ftris;
- std::set<size_t>::iterator tr_it;
- uedge_t ue;
- ue = (f1_tris.size()) ? ue1 : ue2;
- ftris.insert(f1_tris.begin(), f1_tris.end());
- ftris.insert(f2_tris.begin(), f2_tris.end());
- np_id = fmesh_f1->pnts.size() - 1;
- fmesh_f1->ep.insert(np_id);
- for (tr_it = ftris.begin(); tr_it != ftris.end(); tr_it++) {
- replace_edge_split_tri(*fmesh_f1, *tr_it, np_id, ue);
- replaced_tris++;
- }
- omesh_t *om = fmesh_f1->omesh;
- overt_t *nvert = om->vert_add(np_id);
- (*nv1) = nvert;
- (*nv2) = nvert;
- } else {
- np_id = fmesh_f1->pnts.size() - 1;
- fmesh_f1->ep.insert(np_id);
- replace_edge_split_tri(*fmesh_f1, *f1_tris.begin(), np_id, ue1);
- replaced_tris++;
- omesh_t *om1 = fmesh_f1->omesh;
- overt_t *nvert1 = om1->vert_add(np_id);
- (*nv1) = nvert1;
-
- np_id = fmesh_f2->pnts.size() - 1;
- fmesh_f2->ep.insert(np_id);
- replace_edge_split_tri(*fmesh_f2, *f2_tris.begin(), np_id, ue2);
- replaced_tris++;
- omesh_t *om2 = fmesh_f2->omesh;
- overt_t *nvert2 = om2->vert_add(np_id);
- (*nv2) = nvert2;
- }
-
- return replaced_tris;
-}
-
-// Find the point on the edge nearest to the point, and split the edge at that
point.
-//
-// TODO - probably need to get more aggressive about splitting near verts as
the
-// iteration count increases - if there's no other way to resolve the mesh,
that's
-// what we need to do, small triangles or not...
-static int
-bedge_split_at_t(
- overt_t **nv,
- bedge_seg_t *eseg, double t,
- std::set<bedge_seg_t *> *nsegs
- )
-{
- int replaced_tris = 0;
- ON_NurbsCurve *nc = eseg->nc;
- ON_3dPoint cep = nc->PointAt(t);
- double epdist1 = eseg->e_start->DistanceTo(cep);
- double epdist2 = eseg->e_end->DistanceTo(cep);
- double lseg_check = 0.1 * eseg->e_start->DistanceTo(*eseg->e_end);
- if (epdist1 > lseg_check && epdist2 > lseg_check) {
- // If the point is not close to a start/end point on the edge then
split the edge.
- overt_t *nv2;
- int rtris = ovlp_split_edge(nv, &nv2, nsegs, eseg, t);
- if (rtris >= 0) {
- replaced_tris += rtris;
- } else {
- std::cout << "split failed\n";
- }
- }
-// else {
-// std::cout << "split point too close to vertices - skip\n";
-// }
- return replaced_tris;
-}
-
-int
-bedge_split_near_verts(
- std::set<overt_t *> *nverts,
- std::map<bedge_seg_t *, std::set<overt_t *>> &edge_verts
- )
-{
- int replaced_tris = 0;
- std::map<bedge_seg_t *, std::set<overt_t *>>::iterator ev_it;
- int evcnt = 0;
- for (ev_it = edge_verts.begin(); ev_it != edge_verts.end(); ev_it++) {
- //std::cout << "ev (" << evcnt+1 << " of " << edge_verts.size() <<")\n";
- std::set<overt_t *> verts = ev_it->second;
- std::set<bedge_seg_t *> segs;
- segs.insert(ev_it->first);
-
- while (verts.size()) {
- overt_t *v = *verts.begin();
- ON_3dPoint p = v->vpnt();
- verts.erase(v);
-
-#if 0
- if (PPCHECK(p)) {
- std::cout << v->omesh->sname() << ":\n";
- std::cout << "center " << p.x << " " << p.y << " " << p.z <<
"\n";
- }
-#endif
-
- bedge_seg_t *eseg_split = NULL;
- double split_t = -1.0;
- double closest_dist = DBL_MAX;
- std::set<bedge_seg_t *>::iterator e_it;
- //std::cout << "segs size: " << segs.size() << "\n";
- for (e_it = segs.begin(); e_it != segs.end(); e_it++) {
- bedge_seg_t *eseg = *e_it;
- ON_NurbsCurve *nc = eseg->nc;
- ON_Interval domain(eseg->edge_start, eseg->edge_end);
- double t;
- ON_NurbsCurve_GetClosestPoint(&t, nc, p, 0.0, &domain);
- ON_3dPoint cep = nc->PointAt(t);
- double ecdist = cep.DistanceTo(p);
- if (closest_dist > ecdist) {
- //std::cout << "closest_dist: " << closest_dist << "\n";
- //std::cout << "ecdist: " << ecdist << "\n";
- closest_dist = ecdist;
- eseg_split = eseg;
- split_t = t;
- }
- }
-
- std::set<bedge_seg_t *> nsegs;
- overt_t *nv = NULL;
- int ntri_cnt = bedge_split_at_t(&nv, eseg_split, split_t, &nsegs);
- if (ntri_cnt) {
- segs.erase(eseg_split);
- replaced_tris += ntri_cnt;
- segs.insert(nsegs.begin(), nsegs.end());
- nverts->insert(nv);
- }
- }
- evcnt++;
- }
-
- return replaced_tris;
-}
-
-
-// TODO - need to add a check for triangles with all three vertices on the
-// same brep face edge - c.s face 4 appears to have some triangles appearing
-// of that sort, which are messing with the ovlp resolution...
-bool
@@ Diff output truncated at 100000 characters. @@
This was sent by the SourceForge.net collaborative development platform, the
world's largest Open Source development site.
_______________________________________________
BRL-CAD Source Commits mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/brlcad-commits
