Revision: 55941
http://sourceforge.net/p/brlcad/code/55941
Author: phoenixyjll
Date: 2013-07-03 04:43:06 +0000 (Wed, 03 Jul 2013)
Log Message:
-----------
The surface tree could be reused - avoid generating the surface tree again and
again. And add some special splitting machanism for polylines.
Modified Paths:
--------------
brlcad/trunk/include/brep.h
brlcad/trunk/src/libbrep/intersect.cpp
Modified: brlcad/trunk/include/brep.h
===================================================================
--- brlcad/trunk/include/brep.h 2013-07-02 19:13:33 UTC (rev 55940)
+++ brlcad/trunk/include/brep.h 2013-07-03 04:43:06 UTC (rev 55941)
@@ -1948,6 +1948,9 @@
* surfaceB_vdomain - [in]
* optional restriction on surfaceB v domain
*
+ * tree - [in]
+ * optional surface tree for surfaceB, to avoid re-computation
+ *
* Returns:
* True for an intersection. False for no intersection.
*/
@@ -1957,7 +1960,8 @@
ON_ClassArray<ON_PX_EVENT>& x,
double tolerance = 0.0,
const ON_Interval* surfaceB_udomain = 0,
- const ON_Interval* surfaceB_vdomain = 0);
+ const ON_Interval* surfaceB_vdomain = 0,
+ brlcad::SurfaceTree* tree = 0);
/**
* An overload of ON_Intersect for curve-curve intersection.
Modified: brlcad/trunk/src/libbrep/intersect.cpp
===================================================================
--- brlcad/trunk/src/libbrep/intersect.cpp 2013-07-02 19:13:33 UTC (rev
55940)
+++ brlcad/trunk/src/libbrep/intersect.cpp 2013-07-03 04:43:06 UTC (rev
55941)
@@ -75,14 +75,18 @@
{
for (int i = 0; i < 2; i++)
m_children[i] = new Subcurve();
-
- if (m_curve->Split(m_t.Mid(), m_children[0]->m_curve,
m_children[1]->m_curve) == false)
+ ON_SimpleArray<double> pline_t;
+ double split_t = m_t.Mid();
+ if (m_curve->IsPolyline(NULL, &pline_t) && pline_t.Count() > 2) {
+ split_t = pline_t[pline_t.Count()/2];
+ }
+ if (m_curve->Split(split_t, m_children[0]->m_curve,
m_children[1]->m_curve) == false)
return -1;
- m_children[0]->m_t = ON_Interval(m_t.Min(), m_t.Mid());
+ m_children[0]->m_t = m_children[0]->m_curve->Domain();
m_children[0]->SetBBox(m_children[0]->m_curve->BoundingBox());
m_children[0]->m_islinear = m_children[0]->m_curve->IsLinear();
- m_children[1]->m_t = ON_Interval(m_t.Mid(), m_t.Max());
+ m_children[1]->m_t = m_children[1]->m_curve->Domain();
m_children[1]->SetBBox(m_children[1]->m_curve->BoundingBox());
m_children[1]->m_islinear = m_children[1]->m_curve->IsLinear();
@@ -154,14 +158,14 @@
m_children[i] = new Subsurface();
ON_Surface *temp_surf1 = NULL, *temp_surf2 = NULL;
ON_BOOL32 ret = true;
- ret = m_surf->Split(0, m_u.Mid(), temp_surf1, temp_surf2);
+ ret = m_surf->Split(0, m_surf->Domain(0).Mid(), temp_surf1, temp_surf2);
if (!ret) {
delete temp_surf1;
delete temp_surf2;
return -1;
}
- ret = temp_surf1->Split(1, m_v.Mid(), m_children[0]->m_surf,
m_children[1]->m_surf);
+ ret = temp_surf1->Split(1, m_surf->Domain(1).Mid(),
m_children[0]->m_surf, m_children[1]->m_surf);
delete temp_surf1;
if (!ret) {
delete temp_surf2;
@@ -443,7 +447,8 @@
ON_ClassArray<ON_PX_EVENT>& x,
double tolerance,
const ON_Interval* surfaceB_udomain,
- const ON_Interval* surfaceB_vdomain)
+ const ON_Interval* surfaceB_vdomain,
+ brlcad::SurfaceTree* tree)
{
if (tolerance <= 0.0)
tolerance = PSI_DEFAULT_TOLERANCE;
@@ -464,15 +469,19 @@
brep->AddSurface(surfaceB.Duplicate());
brep->NewFace(0);
ON_2dPoint closest_point_uv;
- brlcad::SurfaceTree *tree = new brlcad::SurfaceTree(brep->Face(0), false,
MAX_PSI_DEPTH);
+ bool delete_tree = false;
+ if (!tree) {
+ tree = new brlcad::SurfaceTree(brep->Face(0), false, MAX_PSI_DEPTH);
+ delete_tree = true;
+ }
if (brlcad::get_closest_point(closest_point_uv, brep->Face(0), pointA,
tree) == false) {
delete brep;
- delete tree;
+ if (delete_tree) delete tree;
return false;
}
delete brep;
- delete tree;
+ if (delete_tree) delete tree;
ON_3dPoint closest_point_3d = surfaceB.PointAt(closest_point_uv.x,
closest_point_uv.y);
if (pointA.DistanceTo(closest_point_3d) <= tolerance
@@ -560,7 +569,7 @@
void
-newton_cci(double& t_a, double& t_b, const ON_Curve* curveA, const ON_Curve*
curveB)
+newton_cci(double& t_a, double& t_b, const ON_Curve* curveA, const ON_Curve*
curveB, double intersection_tolerance)
{
// Equations:
// x_a(t_a) - x_b(t_b) = 0
@@ -572,6 +581,9 @@
double last_t_a = DBL_MAX*.5, last_t_b = DBL_MAX*.5;
ON_3dPoint pointA = curveA->PointAt(t_a);
ON_3dPoint pointB = curveB->PointAt(t_b);
+ if (pointA.DistanceTo(pointB) < intersection_tolerance)
+ return;
+
int iteration = 0;
while (fabs(last_t_a - t_a) + fabs(last_t_b - t_b) > ON_ZERO_TOLERANCE
&& iteration++ < CCI_MAX_ITERATIONS) {
@@ -753,9 +765,9 @@
// may miss some overlap cases. (Overlap events can also converge
to one
// point)
double t_a1 = i->first->m_t.Min(), t_b1 = i->second->m_t.Min();
- newton_cci(t_a1, t_b1, curveA, curveB);
+ newton_cci(t_a1, t_b1, curveA, curveB, intersection_tolerance);
double t_a2 = i->first->m_t.Max(), t_b2 = i->second->m_t.Max();
- newton_cci(t_a2, t_b2, curveA, curveB);
+ newton_cci(t_a2, t_b2, curveA, curveB, intersection_tolerance);
ON_3dPoint pointA1 = curveA->PointAt(t_a1);
ON_3dPoint pointB1 = curveB->PointAt(t_b1);
@@ -1010,7 +1022,7 @@
void
-newton_csi(double& t, double& u, double& v, const ON_Curve* curveA, const
ON_Surface* surfB)
+newton_csi(double& t, double& u, double& v, const ON_Curve* curveA, const
ON_Surface* surfB, double intersection_tolerance, brlcad::SurfaceTree*
UNUSED(tree))
{
// Equations:
// x_a(t) - x_b(u,v) = 0
@@ -1020,6 +1032,9 @@
double last_t = DBL_MAX/3, last_u = DBL_MAX/3, last_v = DBL_MAX/3;
ON_3dPoint pointA = curveA->PointAt(t);
ON_3dPoint pointB = surfB->PointAt(u, v);
+ if (pointA.DistanceTo(pointB) < intersection_tolerance)
+ return;
+
int iteration = 0;
while (fabs(last_t - t) + fabs(last_u - u) + fabs(last_v - v) >
ON_ZERO_TOLERANCE
&& iteration++ < CCI_MAX_ITERATIONS) {
@@ -1069,6 +1084,15 @@
if (overlap_tolerance <= 0.0)
overlap_tolerance = 2*intersection_tolerance;
+ // We need ON_BrepFace for get_closest_point().
+ // This is used in point-surface intersections, in case we build the
+ // tree again and again.
+ ON_Brep *brep = ON_Brep::New();
+ brep->AddSurface(surfaceB->Duplicate());
+ brep->NewFace(0);
+ ON_2dPoint closest_point_uv;
+ brlcad::SurfaceTree *tree = new brlcad::SurfaceTree(brep->Face(0), false,
MAX_PSI_DEPTH);
+
Subcurve rootA;
Subsurface rootB;
if (!build_curve_root(curveA, curveA_domain, rootA))
@@ -1139,7 +1163,7 @@
// First, we check the endpoints of the line segment
ON_ClassArray<ON_PX_EVENT> px_event1, px_event2;
int intersections = 0;
- if (ON_Intersect(line.from, *surfaceB, px_event1)) {
+ if (ON_Intersect(line.from, *surfaceB, px_event1,
intersection_tolerance, 0, 0, tree)) {
Event->m_A[intersections] = line.from;
Event->m_B[intersections] = px_event1[0].m_B;
Event->m_a[intersections] = i->first->m_t.Min();
@@ -1147,7 +1171,7 @@
Event->m_b[2*intersections+1] = px_event1[0].m_b[1];
intersections++;
}
- if (ON_Intersect(line.to, *surfaceB, px_event2)) {
+ if (ON_Intersect(line.to, *surfaceB, px_event2,
intersection_tolerance, 0, 0, tree)) {
Event->m_A[intersections] = line.to;
Event->m_B[intersections] = px_event2[0].m_B;
Event->m_a[intersections] = i->first->m_t.Max();
@@ -1245,7 +1269,7 @@
ON_3dPoint intersection = line.from +
line.Direction()*line_t;
ON_2dPoint uv;
ON_ClassArray<ON_PX_EVENT> px_event;
- if (!ON_Intersect(intersection, *(i->second->m_surf),
px_event))
+ if (!ON_Intersect(intersection, *(i->second->m_surf),
px_event, intersection_tolerance, 0, 0, tree))
continue;
ON_X_EVENT* Event = new ON_X_EVENT;
@@ -1271,10 +1295,10 @@
// point)
double u1 = i->second->m_u.Mid(), v1 = i->second->m_v.Mid();
double t1 = i->first->m_t.Min();
- newton_csi(t1, u1, v1, curveA, surfaceB);
+ newton_csi(t1, u1, v1, curveA, surfaceB, intersection_tolerance, tree);
double u2 = i->second->m_u.Mid(), v2 = i->second->m_v.Mid();
double t2 = i->first->m_t.Max();
- newton_csi(t2, u2, v2, curveA, surfaceB);
+ newton_csi(t2, u2, v2, curveA, surfaceB, intersection_tolerance, tree);
if (isnan(u1) || isnan(v1) || isnan(t1)) {
u1 = u2; v1 = v2; t1 = t2;
@@ -1341,7 +1365,7 @@
ON_3dPoint test_point = curveA->PointAt(t1 +
(t2-t1)*j*strike);
ON_ClassArray<ON_PX_EVENT> psi_x;
// Use point-surface intersection
- if (!ON_Intersect(test_point, *surfaceB, psi_x,
overlap_tolerance))
+ if (!ON_Intersect(test_point, *surfaceB, psi_x,
overlap_tolerance, 0, 0, tree))
break;
}
if (j == CSI_OVERLAP_TEST_POINTS) {
This was sent by the SourceForge.net collaborative development platform, the
world's largest Open Source development site.
------------------------------------------------------------------------------
This SF.net email is sponsored by Windows:
Build for Windows Store.
http://p.sf.net/sfu/windows-dev2dev
_______________________________________________
BRL-CAD Source Commits mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/brlcad-commits
