[brlcad-commits] SF.net SVN: brlcad:[55912] brlcad/trunk/src/libbrep/opennurbs_ext.cpp
Open Source Solid Modeling CAD
Brought to you by:
brlcad
From: <sta...@us...> - 2013-07-01 18:49:57
|
Revision: 55912 http://sourceforge.net/p/brlcad/code/55912 Author: starseeker Date: 2013-07-01 18:49:53 +0000 (Mon, 01 Jul 2013) Log Message: ----------- isolate test logic, ws Modified Paths: -------------- brlcad/trunk/src/libbrep/opennurbs_ext.cpp Modified: brlcad/trunk/src/libbrep/opennurbs_ext.cpp =================================================================== --- brlcad/trunk/src/libbrep/opennurbs_ext.cpp 2013-07-01 18:30:38 UTC (rev 55911) +++ brlcad/trunk/src/libbrep/opennurbs_ext.cpp 2013-07-01 18:49:53 UTC (rev 55912) @@ -54,7 +54,7 @@ /// another arbitrary calculation tolerance (need to try VDIVIDE_TOL or VUNITIZE_TOL to tighten the bounds) #define TOL2 0.00001 -void + void brep_get_plane_ray(ON_Ray& r, plane_ray& pr) { vect_t v1; @@ -78,7 +78,7 @@ TRACE1("n1:" << ON_PRINT3(pr.n1) << " n2:" << ON_PRINT3(pr.n2) << " d1:" << pr.d1 << " d2:" << pr.d2); } -void + void brep_r(const ON_Surface* surf, plane_ray& pr, pt2d_t uv, ON_3dPoint& pt, ON_3dVector& su, ON_3dVector& sv, pt2d_t R) { vect_t vp; @@ -91,7 +91,7 @@ } -void + void brep_newton_iterate(plane_ray& pr, pt2d_t R, ON_3dVector& su, ON_3dVector& sv, pt2d_t uv, pt2d_t out_uv) { vect_t vsu, vsv; @@ -99,7 +99,7 @@ VMOVE(vsv, sv); mat2d_t jacob = { VDOT(pr.n1, vsu), VDOT(pr.n1, vsv), - VDOT(pr.n2, vsu), VDOT(pr.n2, vsv) }; + VDOT(pr.n2, vsu), VDOT(pr.n2, vsv) }; mat2d_t inv_jacob; if (mat2d_inverse(inv_jacob, jacob)) { // check inverse validity @@ -112,7 +112,7 @@ } } -void + void brep_newton_iterate(const ON_Surface* UNUSED(surf), plane_ray& pr, pt2d_t R, ON_3dVector& su, ON_3dVector& sv, pt2d_t uv, pt2d_t out_uv) { vect_t vsu, vsv; @@ -120,7 +120,7 @@ VMOVE(vsv, sv); mat2d_t jacob = { VDOT(pr.n1, vsu), VDOT(pr.n1, vsv), - VDOT(pr.n2, vsu), VDOT(pr.n2, vsv) }; + VDOT(pr.n2, vsu), VDOT(pr.n2, vsv) }; mat2d_t inv_jacob; if (mat2d_inverse(inv_jacob, jacob)) { // check inverse validity @@ -136,2327 +136,2358 @@ namespace brlcad { -inline void -distribute(const int count, const ON_3dVector* v, double x[], double y[], double z[]) -{ - for (int i = 0; i < count; i++) { - x[i] = v[i].x; - y[i] = v[i].y; - z[i] = v[i].z; - } -} + inline void + distribute(const int count, const ON_3dVector* v, double x[], double y[], double z[]) + { + for (int i = 0; i < count; i++) { + x[i] = v[i].x; + y[i] = v[i].y; + z[i] = v[i].z; + } + } -//-------------------------------------------------------------------------------- -// CurveTree -CurveTree::CurveTree(const ON_BrepFace* face) : - m_face(face), m_adj_face_index(-99) -{ - m_root = initialLoopBBox(); + //-------------------------------------------------------------------------------- + // CurveTree + CurveTree::CurveTree(const ON_BrepFace* face) : + m_face(face), m_adj_face_index(-99) + { + m_root = initialLoopBBox(); - for (int li = 0; li < face->LoopCount(); li++) { - bool innerLoop = (li > 0) ? true : false; - ON_BrepLoop* loop = face->Loop(li); - // for each trim - for (int ti = 0; ti < loop->m_ti.Count(); ti++) { - int adj_face_index = -99; - ON_BrepTrim& trim = face->Brep()->m_T[loop->m_ti[ti]]; + for (int li = 0; li < face->LoopCount(); li++) { + bool innerLoop = (li > 0) ? true : false; + ON_BrepLoop* loop = face->Loop(li); + // for each trim + for (int ti = 0; ti < loop->m_ti.Count(); ti++) { + int adj_face_index = -99; + ON_BrepTrim& trim = face->Brep()->m_T[loop->m_ti[ti]]; - if (trim.m_ei != -1) { // does not lie on a portion of a singular surface side - ON_BrepEdge& edge = face->Brep()->m_E[trim.m_ei]; - switch (trim.m_type) { - case ON_BrepTrim::unknown: - bu_log("ON_BrepTrim::unknown on Face:%d\n", face->m_face_index); - break; - case ON_BrepTrim::boundary: - //bu_log("ON_BrepTrim::boundary on Face:%d\n", face->m_face_index); - break; - case ON_BrepTrim::mated: - if (edge.m_ti.Count() == 2) { - if (face->m_face_index == face->Brep()->m_T[edge.m_ti[0]].FaceIndexOf()) { - adj_face_index = face->Brep()->m_T[edge.m_ti[1]].FaceIndexOf(); + if (trim.m_ei != -1) { // does not lie on a portion of a singular surface side + ON_BrepEdge& edge = face->Brep()->m_E[trim.m_ei]; + switch (trim.m_type) { + case ON_BrepTrim::unknown: + bu_log("ON_BrepTrim::unknown on Face:%d\n", face->m_face_index); + break; + case ON_BrepTrim::boundary: + //bu_log("ON_BrepTrim::boundary on Face:%d\n", face->m_face_index); + break; + case ON_BrepTrim::mated: + if (edge.m_ti.Count() == 2) { + if (face->m_face_index == face->Brep()->m_T[edge.m_ti[0]].FaceIndexOf()) { + adj_face_index = face->Brep()->m_T[edge.m_ti[1]].FaceIndexOf(); + } else { + adj_face_index = face->Brep()->m_T[edge.m_ti[0]].FaceIndexOf(); + } } else { - adj_face_index = face->Brep()->m_T[edge.m_ti[0]].FaceIndexOf(); + bu_log("Mated Edge should have 2 adjacent faces, right? Face(%d) has %d trim indexes\n", face->m_face_index, edge.m_ti.Count()); } - } else { - bu_log("Mated Edge should have 2 adjacent faces, right? Face(%d) has %d trim indexes\n", face->m_face_index, edge.m_ti.Count()); - } - break; - case ON_BrepTrim::seam: - if (edge.m_ti.Count() == 2) { - if ((face->m_face_index == face->Brep()->m_T[edge.m_ti[0]].FaceIndexOf()) && (face->m_face_index == face->Brep()->m_T[edge.m_ti[1]].FaceIndexOf())) { + break; + case ON_BrepTrim::seam: + if (edge.m_ti.Count() == 2) { + if ((face->m_face_index == face->Brep()->m_T[edge.m_ti[0]].FaceIndexOf()) && (face->m_face_index == face->Brep()->m_T[edge.m_ti[1]].FaceIndexOf())) { + adj_face_index = face->m_face_index; + } else { + bu_log("Seamed Edge should have 1 faces sharing the trim so trim index should be one, right? Face(%d) has %d trim indexes\n", face->m_face_index, edge.m_ti.Count()); + bu_log("Face(%d) has %d, %d trim indexes\n", face->m_face_index, face->Brep()->m_T[edge.m_ti[0]].FaceIndexOf(), face->Brep()->m_T[edge.m_ti[1]].FaceIndexOf()); + } + } else if (edge.m_ti.Count() == 1) { adj_face_index = face->m_face_index; } else { bu_log("Seamed Edge should have 1 faces sharing the trim so trim index should be one, right? Face(%d) has %d trim indexes\n", face->m_face_index, edge.m_ti.Count()); - bu_log("Face(%d) has %d, %d trim indexes\n", face->m_face_index, face->Brep()->m_T[edge.m_ti[0]].FaceIndexOf(), face->Brep()->m_T[edge.m_ti[1]].FaceIndexOf()); } - } else if (edge.m_ti.Count() == 1) { - adj_face_index = face->m_face_index; - } else { - bu_log("Seamed Edge should have 1 faces sharing the trim so trim index should be one, right? Face(%d) has %d trim indexes\n", face->m_face_index, edge.m_ti.Count()); - } - break; - case ON_BrepTrim::singular: - bu_log("ON_BrepTrim::singular on Face:%d\n", face->m_face_index); - break; - case ON_BrepTrim::crvonsrf: - bu_log("ON_BrepTrim::crvonsrf on Face:%d\n", face->m_face_index); - break; - case ON_BrepTrim::ptonsrf: - bu_log("ON_BrepTrim::ptonsrf on Face:%d\n", face->m_face_index); - break; - case ON_BrepTrim::slit: - bu_log("ON_BrepTrim::slit on Face:%d\n", face->m_face_index); - break; - default: - bu_log("ON_BrepTrim::default on Face:%d\n", face->m_face_index); + break; + case ON_BrepTrim::singular: + bu_log("ON_BrepTrim::singular on Face:%d\n", face->m_face_index); + break; + case ON_BrepTrim::crvonsrf: + bu_log("ON_BrepTrim::crvonsrf on Face:%d\n", face->m_face_index); + break; + case ON_BrepTrim::ptonsrf: + bu_log("ON_BrepTrim::ptonsrf on Face:%d\n", face->m_face_index); + break; + case ON_BrepTrim::slit: + bu_log("ON_BrepTrim::slit on Face:%d\n", face->m_face_index); + break; + default: + bu_log("ON_BrepTrim::default on Face:%d\n", face->m_face_index); + } } - } - const ON_Curve* trimCurve = trim.TrimCurveOf(); - double min, max; - (void) trimCurve->GetDomain(&min, &max); - ON_Interval t(min, max); + const ON_Curve* trimCurve = trim.TrimCurveOf(); + double min, max; + (void) trimCurve->GetDomain(&min, &max); + ON_Interval t(min, max); - TRACE("need to subdivide"); - // divide on param interval + TRACE("need to subdivide"); + // divide on param interval - if (!trimCurve->IsLinear()) { - int knotcnt = trimCurve->SpanCount(); - double *knots = new double[knotcnt + 1]; + if (!trimCurve->IsLinear()) { + int knotcnt = trimCurve->SpanCount(); + double *knots = new double[knotcnt + 1]; - trimCurve->GetSpanVector(knots); - std::list<fastf_t> splitlist; - for (int knot_index = 1; knot_index <= knotcnt; knot_index++) { - ON_Interval range(knots[knot_index - 1], knots[knot_index]); + trimCurve->GetSpanVector(knots); + std::list<fastf_t> splitlist; + for (int knot_index = 1; knot_index <= knotcnt; knot_index++) { + ON_Interval range(knots[knot_index - 1], knots[knot_index]); - if (range.Length() > TOL) - getHVTangents(trimCurve, range, splitlist); - } - for (std::list<fastf_t>::iterator l = splitlist.begin(); l != splitlist.end(); l++) { - double xmax = *l; - if (!NEAR_EQUAL(xmax, min, TOL)) { - m_root->addChild(subdivideCurve(trimCurve, adj_face_index, min, xmax, innerLoop, 0)); + if (range.Length() > TOL) + getHVTangents(trimCurve, range, splitlist); } - min = xmax; - } - delete [] knots; - } else { - int knotcnt = trimCurve->SpanCount(); - double *knots = new double[knotcnt + 1]; + for (std::list<fastf_t>::iterator l = splitlist.begin(); l != splitlist.end(); l++) { + double xmax = *l; + if (!NEAR_EQUAL(xmax, min, TOL)) { + m_root->addChild(subdivideCurve(trimCurve, adj_face_index, min, xmax, innerLoop, 0)); + } + min = xmax; + } + delete [] knots; + } else { + int knotcnt = trimCurve->SpanCount(); + double *knots = new double[knotcnt + 1]; - trimCurve->GetSpanVector(knots); - for (int knot_index = 1; knot_index <= knotcnt; knot_index++) { - double xmax = knots[knot_index]; - if (!NEAR_EQUAL(xmax, min, TOL)) { - m_root->addChild(subdivideCurve(trimCurve, adj_face_index, min, xmax, innerLoop, 0)); + trimCurve->GetSpanVector(knots); + for (int knot_index = 1; knot_index <= knotcnt; knot_index++) { + double xmax = knots[knot_index]; + if (!NEAR_EQUAL(xmax, min, TOL)) { + m_root->addChild(subdivideCurve(trimCurve, adj_face_index, min, xmax, innerLoop, 0)); + } + min = xmax; } - min = xmax; + delete [] knots; } - delete [] knots; - } - if (!NEAR_EQUAL(max, min, TOL)) { - m_root->addChild(subdivideCurve(trimCurve, adj_face_index, min, max, innerLoop, 0)); + if (!NEAR_EQUAL(max, min, TOL)) { + m_root->addChild(subdivideCurve(trimCurve, adj_face_index, min, max, innerLoop, 0)); + } } } + getLeaves(m_sortedX); + m_sortedX.sort(sortX); + getLeaves(m_sortedY); + m_sortedY.sort(sortY); + + return; } - getLeaves(m_sortedX); - m_sortedX.sort(sortX); - getLeaves(m_sortedY); - m_sortedY.sort(sortY); - return; -} + CurveTree::~CurveTree() + { + delete m_root; + } -CurveTree::~CurveTree() -{ - delete m_root; -} + BRNode* + CurveTree::getRootNode() const + { + return m_root; + } -BRNode* -CurveTree::getRootNode() const -{ - return m_root; -} + int + CurveTree::depth() + { + return m_root->depth(); + } -int -CurveTree::depth() -{ - return m_root->depth(); -} + ON_2dPoint + CurveTree::getClosestPointEstimate(const ON_3dPoint& pt) + { + return m_root->getClosestPointEstimate(pt); + } -ON_2dPoint -CurveTree::getClosestPointEstimate(const ON_3dPoint& pt) -{ - return m_root->getClosestPointEstimate(pt); -} + ON_2dPoint + CurveTree::getClosestPointEstimate(const ON_3dPoint& pt, ON_Interval& u, ON_Interval& v) + { + return m_root->getClosestPointEstimate(pt, u, v); + } -ON_2dPoint -CurveTree::getClosestPointEstimate(const ON_3dPoint& pt, ON_Interval& u, ON_Interval& v) -{ - return m_root->getClosestPointEstimate(pt, u, v); -} + void + CurveTree::getLeaves(std::list<BRNode*>& out_leaves) + { + m_root->getLeaves(out_leaves); + } -void -CurveTree::getLeaves(std::list<BRNode*>& out_leaves) -{ - m_root->getLeaves(out_leaves); -} + void + CurveTree::getLeavesAbove(std::list<BRNode*>& out_leaves, const ON_Interval& u, const ON_Interval& v) + { + point_t bmin, bmax; + double dist; + for (std::list<BRNode*>::iterator i = m_sortedX.begin(); i != m_sortedX.end(); i++) { + BRNode* br = dynamic_cast<BRNode*>(*i); + br->GetBBox(bmin, bmax); -void -CurveTree::getLeavesAbove(std::list<BRNode*>& out_leaves, const ON_Interval& u, const ON_Interval& v) -{ - point_t bmin, bmax; - double dist; - for (std::list<BRNode*>::iterator i = m_sortedX.begin(); i != m_sortedX.end(); i++) { - BRNode* br = dynamic_cast<BRNode*>(*i); - br->GetBBox(bmin, bmax); - - dist = TOL;//0.03*DIST_PT_PT(bmin, bmax); - if (bmax[X]+dist < u[0]) - continue; - if (bmin[X]-dist < u[1]) { - if (bmax[Y]+dist > v[0]) { - out_leaves.push_back(br); + dist = TOL;//0.03*DIST_PT_PT(bmin, bmax); + if (bmax[X]+dist < u[0]) + continue; + if (bmin[X]-dist < u[1]) { + if (bmax[Y]+dist > v[0]) { + out_leaves.push_back(br); + } + } } } - } -} -void -CurveTree::getLeavesAbove(std::list<BRNode*>& out_leaves, const ON_2dPoint& pt, fastf_t tol) -{ - point_t bmin, bmax; - for (std::list<BRNode*>::iterator i = m_sortedX.begin(); i != m_sortedX.end(); i++) { - BRNode* br = dynamic_cast<BRNode*>(*i); - br->GetBBox(bmin, bmax); + void + CurveTree::getLeavesAbove(std::list<BRNode*>& out_leaves, const ON_2dPoint& pt, fastf_t tol) + { + point_t bmin, bmax; + for (std::list<BRNode*>::iterator i = m_sortedX.begin(); i != m_sortedX.end(); i++) { + BRNode* br = dynamic_cast<BRNode*>(*i); + br->GetBBox(bmin, bmax); - if (bmax[X]+tol < pt.x) - continue; - if (bmin[X]-tol < pt.x) { - if (bmax[Y]+tol > pt.y) { - out_leaves.push_back(br); + if (bmax[X]+tol < pt.x) + continue; + if (bmin[X]-tol < pt.x) { + if (bmax[Y]+tol > pt.y) { + out_leaves.push_back(br); + } + } } } - } -} -void -CurveTree::getLeavesRight(std::list<BRNode*>& out_leaves, const ON_Interval& u, const ON_Interval& v) -{ - point_t bmin, bmax; - double dist; - for (std::list<BRNode*>::iterator i = m_sortedX.begin(); i != m_sortedX.end(); i++) { - BRNode* br = dynamic_cast<BRNode*>(*i); - br->GetBBox(bmin, bmax); + void + CurveTree::getLeavesRight(std::list<BRNode*>& out_leaves, const ON_Interval& u, const ON_Interval& v) + { + point_t bmin, bmax; + double dist; + for (std::list<BRNode*>::iterator i = m_sortedX.begin(); i != m_sortedX.end(); i++) { + BRNode* br = dynamic_cast<BRNode*>(*i); + br->GetBBox(bmin, bmax); - dist = TOL;//0.03*DIST_PT_PT(bmin, bmax); - if (bmax[Y]+dist < v[0]) - continue; - if (bmin[Y]-dist < v[1]) { - if (bmax[X]+dist > u[0]) { - out_leaves.push_back(br); + dist = TOL;//0.03*DIST_PT_PT(bmin, bmax); + if (bmax[Y]+dist < v[0]) + continue; + if (bmin[Y]-dist < v[1]) { + if (bmax[X]+dist > u[0]) { + out_leaves.push_back(br); + } + } } } - } -} -void -CurveTree::getLeavesRight(std::list<BRNode*>& out_leaves, const ON_2dPoint& pt, fastf_t tol) -{ - point_t bmin, bmax; - for (std::list<BRNode*>::iterator i = m_sortedX.begin(); i != m_sortedX.end(); i++) { - BRNode* br = dynamic_cast<BRNode*>(*i); - br->GetBBox(bmin, bmax); + void + CurveTree::getLeavesRight(std::list<BRNode*>& out_leaves, const ON_2dPoint& pt, fastf_t tol) + { + point_t bmin, bmax; + for (std::list<BRNode*>::iterator i = m_sortedX.begin(); i != m_sortedX.end(); i++) { + BRNode* br = dynamic_cast<BRNode*>(*i); + br->GetBBox(bmin, bmax); - if (bmax[Y]+tol < pt.y) - continue; - if (bmin[Y]-tol < pt.y) { - if (bmax[X]+tol > pt.x) { - out_leaves.push_back(br); + if (bmax[Y]+tol < pt.y) + continue; + if (bmin[Y]-tol < pt.y) { + if (bmax[X]+tol > pt.x) { + out_leaves.push_back(br); + } + } } } - } -} -fastf_t -CurveTree::getVerticalTangent(const ON_Curve *curve, fastf_t min, fastf_t max) -{ - fastf_t mid; - ON_3dVector tangent; - bool tanmin; + fastf_t + CurveTree::getVerticalTangent(const ON_Curve *curve, fastf_t min, fastf_t max) + { + fastf_t mid; + ON_3dVector tangent; + bool tanmin; - // first lets check end points - tangent = curve->TangentAt(max); - if (NEAR_ZERO(tangent.x, TOL2)) - return max; - tangent = curve->TangentAt(min); - if (NEAR_ZERO(tangent.x, TOL2)) - return min; + // first lets check end points + tangent = curve->TangentAt(max); + if (NEAR_ZERO(tangent.x, TOL2)) + return max; + tangent = curve->TangentAt(min); + if (NEAR_ZERO(tangent.x, TOL2)) + return min; - tanmin = (tangent[X] < 0.0); - while ((max-min) > TOL2) { - mid = (max + min)/2.0; - tangent = curve->TangentAt(mid); - if (NEAR_ZERO(tangent[X], TOL2)) { - return mid; + tanmin = (tangent[X] < 0.0); + while ((max-min) > TOL2) { + mid = (max + min)/2.0; + tangent = curve->TangentAt(mid); + if (NEAR_ZERO(tangent[X], TOL2)) { + return mid; + } + if ((tangent[X] < 0.0) == tanmin) { + min = mid; + } else { + max = mid; + } + } + return min; } - if ((tangent[X] < 0.0) == tanmin) { - min = mid; - } else { - max = mid; - } - } - return min; -} -fastf_t -CurveTree::getHorizontalTangent(const ON_Curve *curve, fastf_t min, fastf_t max) -{ - fastf_t mid; - ON_3dVector tangent; - bool tanmin; + fastf_t + CurveTree::getHorizontalTangent(const ON_Curve *curve, fastf_t min, fastf_t max) + { + fastf_t mid; + ON_3dVector tangent; + bool tanmin; - // first lets check end points - tangent = curve->TangentAt(max); - if (NEAR_ZERO(tangent.y, TOL2)) - return max; - tangent = curve->TangentAt(min); - if (NEAR_ZERO(tangent.y, TOL2)) - return min; + // first lets check end points + tangent = curve->TangentAt(max); + if (NEAR_ZERO(tangent.y, TOL2)) + return max; + tangent = curve->TangentAt(min); + if (NEAR_ZERO(tangent.y, TOL2)) + return min; - tanmin = (tangent[Y] < 0.0); - while ((max-min) > TOL2) { - mid = (max + min)/2.0; - tangent = curve->TangentAt(mid); - if (NEAR_ZERO(tangent[Y], TOL2)) { - return mid; + tanmin = (tangent[Y] < 0.0); + while ((max-min) > TOL2) { + mid = (max + min)/2.0; + tangent = curve->TangentAt(mid); + if (NEAR_ZERO(tangent[Y], TOL2)) { + return mid; + } + if ((tangent[Y] < 0.0) == tanmin) { + min = mid; + } else { + max = mid; + } + } + return min; } - if ((tangent[Y] < 0.0) == tanmin) { - min = mid; - } else { - max = mid; - } - } - return min; -} -bool -CurveTree::getHVTangents(const ON_Curve* curve, ON_Interval& t, std::list<fastf_t>& list) -{ - double x; - double midpoint = (t[1]+t[0])/2.0; - ON_Interval left(t[0], midpoint); - ON_Interval right(midpoint, t[1]); - int status = ON_Curve_Has_Tangent(curve, t[0], t[1], TOL); + bool + CurveTree::getHVTangents(const ON_Curve* curve, ON_Interval& t, std::list<fastf_t>& list) + { + double x; + double midpoint = (t[1]+t[0])/2.0; + ON_Interval left(t[0], midpoint); + ON_Interval right(midpoint, t[1]); + int status = ON_Curve_Has_Tangent(curve, t[0], t[1], TOL); - switch (status) { + switch (status) { - case 1: /* 1 Vertical tangent */ - x = getVerticalTangent(curve, t[0], t[1]); - list.push_back(x); - return true; + case 1: /* 1 Vertical tangent */ + x = getVerticalTangent(curve, t[0], t[1]); + list.push_back(x); + return true; - case 2: /* 1 Horizontal tangent */ - x = getHorizontalTangent(curve, t[0], t[1]); - list.push_back(x); - return true; + case 2: /* 1 Horizontal tangent */ + x = getHorizontalTangent(curve, t[0], t[1]); + list.push_back(x); + return true; - case 3: /* Horizontal and vertical tangents present - Simple midpoint split */ - if (left.Length() > TOL) - getHVTangents(curve, left, list); - if (right.Length() > TOL) - getHVTangents(curve, right, list); - return true; + case 3: /* Horizontal and vertical tangents present - Simple midpoint split */ + if (left.Length() > TOL) + getHVTangents(curve, left, list); + if (right.Length() > TOL) + getHVTangents(curve, right, list); + return true; - default: - return false; + default: + return false; - } + } - return false; //Should never get here -} + return false; //Should never get here + } -BRNode* -CurveTree::curveBBox(const ON_Curve* curve, int adj_face_index, ON_Interval& t, bool isLeaf, bool innerTrim, const ON_BoundingBox& bb) -{ - BRNode* node; - int vdot = 1; + BRNode* + CurveTree::curveBBox(const ON_Curve* curve, int adj_face_index, ON_Interval& t, bool isLeaf, bool innerTrim, const ON_BoundingBox& bb) + { + BRNode* node; + int vdot = 1; - if (isLeaf) { - TRACE("creating leaf: u(" << u.Min() << ", " << u.Max() << ") v(" << v.Min() << ", " << v.Max() << ")"); - node = new BRNode(curve, adj_face_index, bb, m_face, t, vdot, innerTrim); - } else { - node = new BRNode(bb); - } + if (isLeaf) { + TRACE("creating leaf: u(" << u.Min() << ", " << u.Max() << ") v(" << v.Min() << ", " << v.Max() << ")"); + node = new BRNode(curve, adj_face_index, bb, m_face, t, vdot, innerTrim); + } else { + node = new BRNode(bb); + } - return node; + return node; -} + } -BRNode* -CurveTree::initialLoopBBox() -{ - ON_BoundingBox bb; - for (int i = 0; i < m_face->LoopCount(); i++) { - ON_BrepLoop* loop = m_face->Loop(i); - if (loop->m_type == ON_BrepLoop::outer) { - if (loop->GetBBox(bb[0], bb[1], 0)) { - TRACE("BBox for Loop min<" << bb[0][0] << ", " << bb[0][1] ", " << bb[0][2] << ">"); - TRACE("BBox for Loop max<" << bb[1][0] << ", " << bb[1][1] ", " << bb[1][2] << ">"); + BRNode* + CurveTree::initialLoopBBox() + { + ON_BoundingBox bb; + for (int i = 0; i < m_face->LoopCount(); i++) { + ON_BrepLoop* loop = m_face->Loop(i); + if (loop->m_type == ON_BrepLoop::outer) { + if (loop->GetBBox(bb[0], bb[1], 0)) { + TRACE("BBox for Loop min<" << bb[0][0] << ", " << bb[0][1] ", " << bb[0][2] << ">"); + TRACE("BBox for Loop max<" << bb[1][0] << ", " << bb[1][1] ", " << bb[1][2] << ">"); + } + break; + } } - break; + BRNode* node = new BRNode(bb); + return node; } - } - BRNode* node = new BRNode(bb); - return node; -} -BRNode* -CurveTree::subdivideCurve(const ON_Curve* curve, int adj_face_index, double min, double max, bool innerTrim, int divDepth) -{ - ON_Interval dom = curve->Domain(); - ON_3dPoint points[2]; - points[0] = curve->PointAt(min); - points[1] = curve->PointAt(max); - point_t minpt, maxpt; - VSETALL(minpt, INFINITY); - VSETALL(maxpt, -INFINITY); - for (int i = 0; i < 2; i++) - VMINMAX(minpt, maxpt, ((double*)points[i])); - points[0]=ON_3dPoint(minpt); - points[1]=ON_3dPoint(maxpt); - ON_BoundingBox bb(points[0], points[1]); + BRNode* + CurveTree::subdivideCurve(const ON_Curve* curve, int adj_face_index, double min, double max, bool innerTrim, int divDepth) + { + ON_Interval dom = curve->Domain(); + ON_3dPoint points[2]; + points[0] = curve->PointAt(min); + points[1] = curve->PointAt(max); + point_t minpt, maxpt; + VSETALL(minpt, INFINITY); + VSETALL(maxpt, -INFINITY); + for (int i = 0; i < 2; i++) + VMINMAX(minpt, maxpt, ((double*)points[i])); + points[0]=ON_3dPoint(minpt); + points[1]=ON_3dPoint(maxpt); + ON_BoundingBox bb(points[0], points[1]); - ON_Interval t(min, max); - if (isLinear(curve, min, max) || divDepth >= BREP_MAX_LN_DEPTH) { - double delta = (max - min)/(BREP_BB_CRV_PNT_CNT-1); - point_t pnts[BREP_BB_CRV_PNT_CNT]; - ON_3dPoint pnt; - for (int i=0;i<BREP_BB_CRV_PNT_CNT-1;i++) { - pnt = curve->PointAt(min + delta*i); - VSET(pnts[i], pnt[0], pnt[1], pnt[2]); + ON_Interval t(min, max); + if (isLinear(curve, min, max) || divDepth >= BREP_MAX_LN_DEPTH) { + double delta = (max - min)/(BREP_BB_CRV_PNT_CNT-1); + point_t pnts[BREP_BB_CRV_PNT_CNT]; + ON_3dPoint pnt; + for (int i=0;i<BREP_BB_CRV_PNT_CNT-1;i++) { + pnt = curve->PointAt(min + delta*i); + VSET(pnts[i], pnt[0], pnt[1], pnt[2]); + } + pnt = curve->PointAt(max); + VSET(pnts[BREP_BB_CRV_PNT_CNT-1], pnt[0], pnt[1], pnt[2]); + + VSETALL(minpt, MAX_FASTF); + VSETALL(maxpt, -MAX_FASTF); + for (int i = 0; i < BREP_BB_CRV_PNT_CNT; i++) + VMINMAX(minpt, maxpt, ((double*)pnts[i])); + + VMOVE(pnt, minpt); + bb.Set(pnt, false); + VMOVE(pnt, maxpt); + bb.Set(pnt, true); + return curveBBox(curve, adj_face_index, t, true, innerTrim, bb); + } + + // else subdivide + BRNode* parent = curveBBox(curve, adj_face_index, t, false, innerTrim, bb); + double mid = (max+min)/2.0; + BRNode* l = subdivideCurve(curve, adj_face_index, min, mid, innerTrim, divDepth+1); + BRNode* r = subdivideCurve(curve, adj_face_index, mid, max, innerTrim, divDepth+1); + parent->addChild(l); + parent->addChild(r); + return parent; } - pnt = curve->PointAt(max); - VSET(pnts[BREP_BB_CRV_PNT_CNT-1], pnt[0], pnt[1], pnt[2]); - VSETALL(minpt, MAX_FASTF); - VSETALL(maxpt, -MAX_FASTF); - for (int i = 0; i < BREP_BB_CRV_PNT_CNT; i++) - VMINMAX(minpt, maxpt, ((double*)pnts[i])); - VMOVE(pnt, minpt); - bb.Set(pnt, false); - VMOVE(pnt, maxpt); - bb.Set(pnt, true); - return curveBBox(curve, adj_face_index, t, true, innerTrim, bb); - } + /** + * Determine whether a given curve segment is linear + */ + bool + CurveTree::isLinear(const ON_Curve* curve, double min, double max) + { + ON_3dVector tangent_start = curve->TangentAt(min); + ON_3dVector tangent_end = curve->TangentAt(max); + double vdot = tangent_start * tangent_end; + if (vdot < BREP_CURVE_FLATNESS) + return false; - // else subdivide - BRNode* parent = curveBBox(curve, adj_face_index, t, false, innerTrim, bb); - double mid = (max+min)/2.0; - BRNode* l = subdivideCurve(curve, adj_face_index, min, mid, innerTrim, divDepth+1); - BRNode* r = subdivideCurve(curve, adj_face_index, mid, max, innerTrim, divDepth+1); - parent->addChild(l); - parent->addChild(r); - return parent; -} + ON_3dPoint pmin = curve->PointAt(min); + ON_3dPoint pmax = curve->PointAt(max); + const ON_Surface* surf = m_face->SurfaceOf(); + ON_Interval u = surf->Domain(0); + ON_Interval v = surf->Domain(1); + point_t a, b; + VSET(a, u[0], v[0], 0.0); + VSET(b, u[1], v[1], 0.0); + double dd = DIST_PT_PT(a, b); + double cd = DIST_PT_PT(pmin, pmax); -/** - * Determine whether a given curve segment is linear - */ -bool -CurveTree::isLinear(const ON_Curve* curve, double min, double max) -{ - ON_3dVector tangent_start = curve->TangentAt(min); - ON_3dVector tangent_end = curve->TangentAt(max); - double vdot = tangent_start * tangent_end; - if (vdot < BREP_CURVE_FLATNESS) - return false; + if (cd > BREP_TRIM_SUB_FACTOR*dd) + return false; - ON_3dPoint pmin = curve->PointAt(min); - ON_3dPoint pmax = curve->PointAt(max); + double delta = (max - min)/(BREP_BB_CRV_PNT_CNT-1); + ON_3dPoint points[BREP_BB_CRV_PNT_CNT]; + for (int i=0;i<BREP_BB_CRV_PNT_CNT-1;i++) { + points[i] = curve->PointAt(min + delta*i); + } + points[BREP_BB_CRV_PNT_CNT-1] = curve->PointAt(max); - const ON_Surface* surf = m_face->SurfaceOf(); - ON_Interval u = surf->Domain(0); - ON_Interval v = surf->Domain(1); - point_t a, b; - VSET(a, u[0], v[0], 0.0); - VSET(b, u[1], v[1], 0.0); - double dd = DIST_PT_PT(a, b); - double cd = DIST_PT_PT(pmin, pmax); + ON_3dVector A; + ON_3dVector B; + vdot = 1.0; + A = points[BREP_BB_CRV_PNT_CNT-1] - points[0]; + A.Unitize(); + for (int i=1;i<BREP_BB_CRV_PNT_CNT-1;i++) { + B = points[i] - points[0]; + B.Unitize(); + vdot = vdot * (A * B); + if (vdot < BREP_CURVE_FLATNESS) + return false; //already failed + } - if (cd > BREP_TRIM_SUB_FACTOR*dd) - return false; + return vdot >= BREP_CURVE_FLATNESS; + } - double delta = (max - min)/(BREP_BB_CRV_PNT_CNT-1); - ON_3dPoint points[BREP_BB_CRV_PNT_CNT]; - for (int i=0;i<BREP_BB_CRV_PNT_CNT-1;i++) { - points[i] = curve->PointAt(min + delta*i); + //-------------------------------------------------------------------------------- + // SurfaceTree + SurfaceTree::SurfaceTree() + : m_removeTrimmed(false), + ctree(NULL), + m_face(NULL), + m_root(NULL) + { } - points[BREP_BB_CRV_PNT_CNT-1] = curve->PointAt(max); - ON_3dVector A; - ON_3dVector B; - vdot = 1.0; - A = points[BREP_BB_CRV_PNT_CNT-1] - points[0]; - A.Unitize(); - for (int i=1;i<BREP_BB_CRV_PNT_CNT-1;i++) { - B = points[i] - points[0]; - B.Unitize(); - vdot = vdot * (A * B); - if (vdot < BREP_CURVE_FLATNESS) - return false; //already failed - } + SurfaceTree::SurfaceTree(const ON_BrepFace* face, bool removeTrimmed, int depthLimit) + : m_removeTrimmed(removeTrimmed), + m_face(face) + { + // first, build the Curve Tree + if (removeTrimmed) + ctree = new CurveTree(m_face); + else + ctree = NULL; - return vdot >= BREP_CURVE_FLATNESS; -} + // build the surface bounding volume hierarchy + const ON_Surface* surf = face->SurfaceOf(); + if (!surf) { + TRACE("ERROR: NULL surface encountered in SurfaceTree()"); + return; + } -//-------------------------------------------------------------------------------- -// SurfaceTree -SurfaceTree::SurfaceTree() - : m_removeTrimmed(false), - ctree(NULL), - m_face(NULL), - m_root(NULL) -{ -} + TRACE("Creating surface tree for: " << face->m_face_index); + ON_Interval u = surf->Domain(0); + ON_Interval v = surf->Domain(1); + double uq = u.Length()*0.25; + double vq = v.Length()*0.25; -SurfaceTree::SurfaceTree(const ON_BrepFace* face, bool removeTrimmed, int depthLimit) - : m_removeTrimmed(removeTrimmed), - m_face(face) -{ - // first, build the Curve Tree - if (removeTrimmed) - ctree = new CurveTree(m_face); - else - ctree = NULL; + /////////////////////////////////////////////////////////////////////// + // Populate initial frames array for use in tree build + ON_Plane frames[9]; + surf->FrameAt(u.Min(), v.Min(), frames[0]); + surf->FrameAt(u.Max(), v.Min(), frames[1]); + surf->FrameAt(u.Max(), v.Max(), frames[2]); + surf->FrameAt(u.Min(), v.Max(), frames[3]); + surf->FrameAt(u.Mid(), v.Mid(), frames[4]); + surf->FrameAt(u.Mid() - uq, v.Mid() - vq, frames[5]); + surf->FrameAt(u.Mid() - uq, v.Mid() + vq, frames[6]); + surf->FrameAt(u.Mid() + uq, v.Mid() - vq, frames[7]); + surf->FrameAt(u.Mid() + uq, v.Mid() + vq, frames[8]); - // build the surface bounding volume hierarchy - const ON_Surface* surf = face->SurfaceOf(); - if (!surf) { - TRACE("ERROR: NULL surface encountered in SurfaceTree()"); - return; + m_root = subdivideSurfaceByKnots(surf, u, v, frames, 0, depthLimit); + if (m_root) { + m_root->BuildBBox(); + } + TRACE("u: [" << u[0] << ", " << u[1] << "]"); + TRACE("v: [" << v[0] << ", " << v[1] << "]"); + TRACE("m_root: " << m_root); } - TRACE("Creating surface tree for: " << face->m_face_index); - ON_Interval u = surf->Domain(0); - ON_Interval v = surf->Domain(1); - double uq = u.Length()*0.25; - double vq = v.Length()*0.25; - /////////////////////////////////////////////////////////////////////// - // Populate initial frames array for use in tree build - ON_Plane frames[9]; - surf->FrameAt(u.Min(), v.Min(), frames[0]); - surf->FrameAt(u.Max(), v.Min(), frames[1]); - surf->FrameAt(u.Max(), v.Max(), frames[2]); - surf->FrameAt(u.Min(), v.Max(), frames[3]); - surf->FrameAt(u.Mid(), v.Mid(), frames[4]); - surf->FrameAt(u.Mid() - uq, v.Mid() - vq, frames[5]); - surf->FrameAt(u.Mid() - uq, v.Mid() + vq, frames[6]); - surf->FrameAt(u.Mid() + uq, v.Mid() - vq, frames[7]); - surf->FrameAt(u.Mid() + uq, v.Mid() + vq, frames[8]); - - m_root = subdivideSurfaceByKnots(surf, u, v, frames, 0, depthLimit); - if (m_root) { - m_root->BuildBBox(); + SurfaceTree::~SurfaceTree() + { + delete ctree; + delete m_root; } - TRACE("u: [" << u[0] << ", " << u[1] << "]"); - TRACE("v: [" << v[0] << ", " << v[1] << "]"); - TRACE("m_root: " << m_root); -} -SurfaceTree::~SurfaceTree() -{ - delete ctree; - delete m_root; -} + BBNode* + SurfaceTree::getRootNode() const + { + return m_root; + } -BBNode* -SurfaceTree::getRootNode() const -{ - return m_root; -} + int + SurfaceTree::depth() + { + return m_root->depth(); + } -int -SurfaceTree::depth() -{ - return m_root->depth(); -} + ON_2dPoint + SurfaceTree::getClosestPointEstimate(const ON_3dPoint& pt) + { + return m_root->getClosestPointEstimate(pt); + } -ON_2dPoint -SurfaceTree::getClosestPointEstimate(const ON_3dPoint& pt) -{ - return m_root->getClosestPointEstimate(pt); -} + ON_2dPoint + SurfaceTree::getClosestPointEstimate(const ON_3dPoint& pt, ON_Interval& u, ON_Interval& v) + { + return m_root->getClosestPointEstimate(pt, u, v); + } -ON_2dPoint -SurfaceTree::getClosestPointEstimate(const ON_3dPoint& pt, ON_Interval& u, ON_Interval& v) -{ - return m_root->getClosestPointEstimate(pt, u, v); -} + void + SurfaceTree::getLeaves(std::list<BBNode*>& out_leaves) + { + m_root->getLeaves(out_leaves); + } -void -SurfaceTree::getLeaves(std::list<BBNode*>& out_leaves) -{ - m_root->getLeaves(out_leaves); -} + const ON_Surface * + SurfaceTree::getSurface() + { + return m_face->SurfaceOf(); + } -const ON_Surface * -SurfaceTree::getSurface() -{ - return m_face->SurfaceOf(); -} + int + brep_getSurfacePoint(const ON_3dPoint& pt, ON_2dPoint& uv , BBNode* node) { + plane_ray pr; + const ON_Surface *surf = node->m_face->SurfaceOf(); + double umin, umax; + double vmin, vmax; + surf->GetDomain(0, &umin, &umax); + surf->GetDomain(1, &vmin, &vmax); + ON_3dVector dir = node->m_normal; + dir.Reverse(); + ON_Ray ray((ON_3dPoint&)pt, dir); + brep_get_plane_ray(ray, pr); -int -brep_getSurfacePoint(const ON_3dPoint& pt, ON_2dPoint& uv , BBNode* node) { - plane_ray pr; - const ON_Surface *surf = node->m_face->SurfaceOf(); - double umin, umax; - double vmin, vmax; - surf->GetDomain(0, &umin, &umax); - surf->GetDomain(1, &vmin, &vmax); + //know use this as guess to iterate to closer solution + pt2d_t Rcurr; + pt2d_t new_uv; + ON_3dVector su, sv; + bool found=false; + fastf_t Dlast = MAX_FASTF; + pt2d_t nuv; + nuv[0] = (node->m_u[1] + node->m_u[0])/2.0; + nuv[1] = (node->m_v[1] + node->m_v[0])/2.0; + ON_3dPoint newpt; + for (int i = 0; i < BREP_MAX_ITERATIONS; i++) { + brep_r(surf, pr, nuv, newpt, su, sv, Rcurr); + fastf_t d = v2mag(Rcurr); - ON_3dVector dir = node->m_normal; - dir.Reverse(); - ON_Ray ray((ON_3dPoint&)pt, dir); - brep_get_plane_ray(ray, pr); + if (d < BREP_INTERSECTION_ROOT_EPSILON) { + TRACE1("R:"<<ON_PRINT2(Rcurr)); + found = true; + break; + } else if (d < BREP_INTERSECTION_ROOT_SETTLE) { + found = true; + } + brep_newton_iterate(pr, Rcurr, su, sv, nuv, new_uv); - //know use this as guess to iterate to closer solution - pt2d_t Rcurr; - pt2d_t new_uv; - ON_3dVector su, sv; - bool found=false; - fastf_t Dlast = MAX_FASTF; - pt2d_t nuv; - nuv[0] = (node->m_u[1] + node->m_u[0])/2.0; - nuv[1] = (node->m_v[1] + node->m_v[0])/2.0; - ON_3dPoint newpt; - for (int i = 0; i < BREP_MAX_ITERATIONS; i++) { - brep_r(surf, pr, nuv, newpt, su, sv, Rcurr); - fastf_t d = v2mag(Rcurr); - - if (d < BREP_INTERSECTION_ROOT_EPSILON) { - TRACE1("R:"<<ON_PRINT2(Rcurr)); - found = true; - break; - } else if (d < BREP_INTERSECTION_ROOT_SETTLE) { - found = true; - } - brep_newton_iterate(pr, Rcurr, su, sv, nuv, new_uv); - - //Check for closed surface wrap around - if (surf->IsClosed(0)) { - if (new_uv[0] < umin) { - new_uv[0] = umin; - } else if (new_uv[0] > umax) { - new_uv[0] = umax; - } - } - if (surf->IsClosed(1)) { - if (new_uv[1] < vmin) { - new_uv[1] = vmin; - } else if (new_uv[1] > vmax) { - new_uv[1] = vmax; - } - } + //Check for closed surface wrap around + if (surf->IsClosed(0)) { + if (new_uv[0] < umin) { + new_uv[0] = umin; + } else if (new_uv[0] > umax) { + new_uv[0] = umax; + } + } + if (surf->IsClosed(1)) { + if (new_uv[1] < vmin) { + new_uv[1] = vmin; + } else if (new_uv[1] > vmax) { + new_uv[1] = vmax; + } + } #ifdef HOOD - //push answer back to within node bounds - double ufluff = (node->m_u[1] - node->m_u[0])*0.01; - double vfluff = (node->m_v[1] - node->m_v[0])*0.01; + //push answer back to within node bounds + double ufluff = (node->m_u[1] - node->m_u[0])*0.01; + double vfluff = (node->m_v[1] - node->m_v[0])*0.01; #else - //push answer back to within node bounds - double ufluff = 0.0; - double vfluff = 0.0; + //push answer back to within node bounds + double ufluff = 0.0; + double vfluff = 0.0; #endif - if (new_uv[0] < node->m_u[0] - ufluff) - new_uv[0] = node->m_u[0]; - else if (new_uv[0] > node->m_u[1] + ufluff) - new_uv[0] = node->m_u[1]; + if (new_uv[0] < node->m_u[0] - ufluff) + new_uv[0] = node->m_u[0]; + else if (new_uv[0] > node->m_u[1] + ufluff) + new_uv[0] = node->m_u[1]; - if (new_uv[1] < node->m_v[0] - vfluff) - new_uv[1] = node->m_v[0]; - else if (new_uv[1] > node->m_v[1] + vfluff) - new_uv[1] = node->m_v[1]; + if (new_uv[1] < node->m_v[0] - vfluff) + new_uv[1] = node->m_v[0]; + else if (new_uv[1] > node->m_v[1] + vfluff) + new_uv[1] = node->m_v[1]; - surf->EvNormal(new_uv[0], new_uv[1], newpt, ray.m_dir); - ray.m_dir.Reverse(); - brep_get_plane_ray(ray, pr); + surf->EvNormal(new_uv[0], new_uv[1], newpt, ray.m_dir); + ray.m_dir.Reverse(); + brep_get_plane_ray(ray, pr); - if (d < Dlast) { - move(nuv, new_uv); - Dlast = d; + if (d < Dlast) { + move(nuv, new_uv); + Dlast = d; + } + } + if (found) { + uv.x = nuv[0]; + uv.y = nuv[1]; + return 1; + } + return -1; } - } - if (found) { - uv.x = nuv[0]; - uv.y = nuv[1]; - return 1; - } - return -1; -} -int -SurfaceTree::getSurfacePoint(const ON_3dPoint& pt, ON_2dPoint& uv, const ON_3dPoint& from, double tolerance) const -{ - std::list<BBNode*> nodes; - (void)m_root->getLeavesBoundingPoint(from, nodes); + int + SurfaceTree::getSurfacePoint(const ON_3dPoint& pt, ON_2dPoint& uv, const ON_3dPoint& from, double tolerance) const + { + std::list<BBNode*> nodes; + (void)m_root->getLeavesBoundingPoint(from, nodes); - double min_dist = MAX_FASTF; - ON_2dPoint curr_uv(0.0, 0.0); - bool found = false; + double min_dist = MAX_FASTF; + ON_2dPoint curr_uv(0.0, 0.0); + bool found = false; - std::list<BBNode*>::iterator i; - for (i = nodes.begin(); i != nodes.end(); i++) { - BBNode* node = (*i); - if (brep_getSurfacePoint(pt, curr_uv, node)) { - ON_3dPoint fp = m_face->SurfaceOf()->PointAt(curr_uv.x, curr_uv.y); - double dist = fp.DistanceTo(pt); - if (NEAR_ZERO(dist, BREP_SAME_POINT_TOLERANCE)) { - uv = curr_uv; - found = true; - return 1; //close enough to same point so no sense in looking for one closer - } else if (NEAR_ZERO(dist, tolerance)) { - if (dist < min_dist) { - uv = curr_uv; - min_dist = dist; - found = true; //within tolerance but may be a point closer so keep looking + std::list<BBNode*>::iterator i; + for (i = nodes.begin(); i != nodes.end(); i++) { + BBNode* node = (*i); + if (brep_getSurfacePoint(pt, curr_uv, node)) { + ON_3dPoint fp = m_face->SurfaceOf()->PointAt(curr_uv.x, curr_uv.y); + double dist = fp.DistanceTo(pt); + if (NEAR_ZERO(dist, BREP_SAME_POINT_TOLERANCE)) { + uv = curr_uv; + found = true; + return 1; //close enough to same point so no sense in looking for one closer + } else if (NEAR_ZERO(dist, tolerance)) { + if (dist < min_dist) { + uv = curr_uv; + min_dist = dist; + found = true; //within tolerance but may be a point closer so keep looking + } + } } } + if (found) { + return 1; + } + return -1; } - } - if (found) { - return 1; - } - return -1; -} -//static int bb_cnt=0; -BBNode* -SurfaceTree::surfaceBBox(const ON_Surface *localsurf, bool isLeaf, ON_Plane *m_frames, const ON_Interval& u, const ON_Interval& v) -{ - point_t min, max, buffer; - ON_BoundingBox bbox = localsurf->BoundingBox(); + //static int bb_cnt=0; + BBNode* + SurfaceTree::surfaceBBox(const ON_Surface *localsurf, bool isLeaf, ON_Plane *m_frames, const ON_Interval& u, const ON_Interval& v) + { + point_t min, max, buffer; + ON_BoundingBox bbox = localsurf->BoundingBox(); - VSETALL(buffer, BREP_EDGE_MISS_TOLERANCE); + VSETALL(buffer, BREP_EDGE_MISS_TOLERANCE); - //bu_log("in bb%d rpp %f %f %f %f %f %f\n", bb_cnt, min[0], max[0], min[1], max[1], min[2], max[2]); - VMOVE(min, bbox.Min()); - VMOVE(max, bbox.Max()); + //bu_log("in bb%d rpp %f %f %f %f %f %f\n", bb_cnt, min[0], max[0], min[1], max[1], min[2], max[2]); + VMOVE(min, bbox.Min()); + VMOVE(max, bbox.Max()); - // calculate the estimate point on the surface: i.e. use the point - // on the surface defined by (u.Mid(), v.Mid()) as a heuristic for - // finding the uv domain bounding a portion of the surface close - // to an arbitrary model-space point (see - // getClosestPointEstimate()) - ON_3dPoint estimate; - ON_3dVector normal; - estimate = m_frames[4].origin; - normal = m_frames[4].zaxis; + // calculate the estimate point on the surface: i.e. use the point + // on the surface defined by (u.Mid(), v.Mid()) as a heuristic for + // finding the uv domain bounding a portion of the surface close + // to an arbitrary model-space point (see + // getClosestPointEstimate()) + ON_3dPoint estimate; + ON_3dVector normal; + estimate = m_frames[4].origin; + normal = m_frames[4].zaxis; - BBNode* node; - if (isLeaf) { -/* vect_t delta; */ + BBNode* node; + if (isLeaf) { + /* vect_t delta; */ - VSUB2(min, min, buffer); - VADD2(max, max, buffer); -/* VSUB2(delta, max, min); - VSCALE(delta, delta, BBOX_GROW_3D); - VSUB2(min, min, delta); - VADD2(max, max, delta); -*/ - TRACE("creating leaf: u(" << u.Min() << ", " << u.Max() << - ") v(" << v.Min() << ", " << v.Max() << ")"); - node = new BBNode(ctree, ON_BoundingBox(ON_3dPoint(min), - ON_3dPoint(max)), - m_face, - u, v); - node->prepTrims(); + VSUB2(min, min, buffer); + VADD2(max, max, buffer); + /* VSUB2(delta, max, min); + VSCALE(delta, delta, BBOX_GROW_3D); + VSUB2(min, min, delta); + VADD2(max, max, delta); + */ + TRACE("creating leaf: u(" << u.Min() << ", " << u.Max() << + ") v(" << v.Min() << ", " << v.Max() << ")"); + node = new BBNode(ctree, ON_BoundingBox(ON_3dPoint(min), + ON_3dPoint(max)), + m_face, + u, v); + node->prepTrims(); - } else { - node = new BBNode(ctree, ON_BoundingBox(ON_3dPoint(min), - ON_3dPoint(max))); - } + } else { + node = new BBNode(ctree, ON_BoundingBox(ON_3dPoint(min), + ON_3dPoint(max))); + } - node->m_estimate = estimate; - node->m_normal = normal; - node->m_face = m_face; - node->m_u = u; - node->m_v = v; - return node; -} + node->m_estimate = estimate; + node->m_normal = normal; + node->m_face = m_face; + node->m_u = u; + node->m_v = v; + return node; + } -BBNode* -initialBBox(CurveTree* ctree, const ON_Surface* surf, const ON_BrepFace* face, const ON_Interval& u, const ON_Interval& v) -{ - ON_BoundingBox bb = surf->BoundingBox(); - BBNode* node = new BBNode(ctree, bb, face, u, v, false, false); - ON_3dPoint estimate; - ON_3dVector normal; - if (!surf->EvNormal(surf->Domain(0).Mid(), surf->Domain(1).Mid(), estimate, normal)) { - bu_bomb("Could not evaluate estimate point on surface"); - } - node->m_estimate = estimate; - node->m_normal = normal; - node->m_face = face; - node->m_u = u; - node->m_v = v; - return node; -} + BBNode* + initialBBox(CurveTree* ctree, const ON_Surface* surf, const ON_BrepFace* face, const ON_Interval& u, const ON_Interval& v) + { + ON_BoundingBox bb = surf->BoundingBox(); + BBNode* node = new BBNode(ctree, bb, face, u, v, false, false); + ON_3dPoint estimate; + ON_3dVector normal; + if (!surf->EvNormal(surf->Domain(0).Mid(), surf->Domain(1).Mid(), estimate, normal)) { + bu_bomb("Could not evaluate estimate point on surface"); + } + node->m_estimate = estimate; + node->m_normal = normal; + node->m_face = face; + node->m_u = u; + node->m_v = v; + return node; + } -BBNode* -SurfaceTree::subdivideSurfaceByKnots(const ON_Surface *localsurf, - const ON_Interval& u, - const ON_Interval& v, - ON_Plane frames[], - int divDepth, - int depthLimit) -{ - double uq = u.Length()*0.25; - double vq = v.Length()*0.25; - localsurf->FrameAt(u.Mid() - uq, v.Mid() - vq, frames[5]); - localsurf->FrameAt(u.Mid() - uq, v.Mid() + vq, frames[6]); - localsurf->FrameAt(u.Mid() + uq, v.Mid() - vq, frames[7]); - localsurf->FrameAt(u.Mid() + uq, v.Mid() + vq, frames[8]); - BBNode* quads[4]; + BBNode* + SurfaceTree::subdivideSurfaceByKnots(const ON_Surface *localsurf, + const ON_Interval& u, + const ON_Interval& v, + ON_Plane frames[], + int divDepth, + int depthLimit) + { + double uq = u.Length()*0.25; + double vq = v.Length()*0.25; + localsurf->FrameAt(u.Mid() - uq, v.Mid() - vq, frames[5]); + localsurf->FrameAt(u.Mid() - uq, v.Mid() + vq, frames[6]); + localsurf->FrameAt(u.Mid() + uq, v.Mid() - vq, frames[7]); + localsurf->FrameAt(u.Mid() + uq, v.Mid() + vq, frames[8]); + BBNode* quads[4]; - unsigned int do_u_split = 0; - unsigned int do_v_split = 0; - BBNode* parent = NULL; - double usplit; - double vsplit; + unsigned int do_u_split = 0; + unsigned int do_v_split = 0; + unsigned int do_both_splits = 0; + BBNode* parent = NULL; + double usplit; + double vsplit; - // Knots - int spanu_cnt = localsurf->SpanCount(0); - int spanv_cnt = localsurf->SpanCount(1); - parent = initialBBox(ctree, localsurf, m_face, u, v); - if (spanu_cnt > 1) { - double *spanu = new double[spanu_cnt+1]; - localsurf->GetSpanVector(0, spanu); - do_u_split = 1; - usplit = spanu[(spanu_cnt+1)/2]; - delete [] spanu; - } - if (spanv_cnt > 1) { - double *spanv = new double[spanv_cnt+1]; - localsurf->GetSpanVector(1, spanv); - do_v_split = 1; - vsplit = spanv[(spanv_cnt+1)/2]; - delete [] spanv; - } + // Knots + int spanu_cnt = localsurf->SpanCount(0); + int spanv_cnt = localsurf->SpanCount(1); + parent = initialBBox(ctree, localsurf, m_face, u, v); + if (spanu_cnt > 1) { + double *spanu = new double[spanu_cnt+1]; + localsurf->GetSpanVector(0, spanu); + do_u_split = 1; + usplit = spanu[(spanu_cnt+1)/2]; + delete [] spanu; + } + if (spanv_cnt > 1) { + double *spanv = new double[spanv_cnt+1]; + localsurf->GetSpanVector(1, spanv); + do_v_split = 1; + vsplit = spanv[(spanv_cnt+1)/2]; + delete [] spanv; + } + if (do_u_split && do_v_split) { + do_both_splits = 1; + do_u_split = 0; + do_v_split = 0; + } - /////////////////////////////////// + /////////////////////////////////// - if ((spanu_cnt > 1) && (spanv_cnt > 1)) { - ON_Interval firstu(u.Min(), usplit); - ON_Interval secondu(usplit, u.Max()); - ON_Interval firstv(v.Min(), vsplit); - ON_Interval secondv(vsplit, v.Max()); - ON_BoundingBox box = localsurf->BoundingBox(); + if (do_both_splits) { + ON_Interval firstu(u.Min(), usplit); + ON_Interval secondu(usplit, u.Max()); + ON_Interval firstv(v.Min(), vsplit); + ON_Interval secondv(vsplit, v.Max()); + ON_BoundingBox box = localsurf->BoundingBox(); - ON_Surface *q0surf = NULL; - ON_Surface *q1surf = NULL; - ON_Surface *q2surf = NULL; - ON_Surface *q3surf = NULL; + ON_Surface *q0surf = NULL; + ON_Surface *q1surf = NULL; + ON_Surface *q2surf = NULL; + ON_Surface *q3surf = NULL; - bool split = ON_Surface_Quad_Split(localsurf, u, v, usplit, vsplit, &q0surf, &q1surf, &q2surf, &q3surf); - /* FIXME: this needs to be handled more gracefully */ - if (!split) { - delete parent; - return NULL; - } - q0surf->ClearBoundingBox(); - q1surf->ClearBoundingBox(); - q2surf->ClearBoundingBox(); - q3surf->ClearBoundingBox(); + bool split = ON_Surface_Quad_Split(localsurf, u, v, usplit, vsplit, &q0surf, &q1surf, &q2surf, &q3surf); + /* FIXME: this needs to be handled more gracefully */ + if (!split) { + delete parent; + return NULL; + } + q0surf->ClearBoundingBox(); + q1surf->ClearBoundingBox(); + q2surf->ClearBoundingBox(); + q3surf->ClearBoundingBox(); - /********************************************************************* - * In order to avoid fairly expensive re-calculation of 3d points at - * uv coordinates, all values that are shared between children at - * the same depth of a surface subdivision are pre-computed and - * passed as parameters. - * - * The majority of these points are already evaluated in the process - * of testing whether a subdivision has produced a leaf node. These - * values are in the normals and corners arrays and have index values - * corresponding to the values of the figure on the left below. There - * are four other shared values that are precomputed in the sharedcorners - * and sharednormals arrays; their index values in those arrays are - * illustrated in the figure on the right: - * - * - * 3-------------------2 +---------2---------+ - * | | | | - * | 6 8 | | | - * | | | | - * V| 4 | 1 3 - * | | | | - * | 5 7 | | | - * | | | | - * 0-------------------1 +---------0---------+ - * U U - * - * Values inherited from Values pre-prepared in - * parent subdivision shared arrays - * - * - * When the four subdivisions are made, the parent parameters - * are passed to the children as follows (values from the - * shared arrays are prefaced with an s): - * - * 3--------------S2 S2--------------2 - * | | | | - * | | | | - * V | 6 | | 8 | - * | | | | - * | | | | - * S1--------------4 4--------------S3 - * U U - * - * Quadrant 3 Quadrant 2 - * - * S1--------------4 4--------------S3 - * | | | | - * | | | | - * V | 5 | | 7 | - * | | | | - * | | | | - * 0--------------S0 S0--------------1 - * U U - * - * Quadrant 0 Quadrant 1 - * - * - **********************************************************************/ + /********************************************************************* + * In order to avoid fairly expensive re-calculation of 3d points at + * uv coordinates, all values that are shared between children at + * the same depth of a surface subdivision are pre-computed and + * passed as parameters. + * + * The majority of these points are already evaluated in the process + * of testing whether a subdivision has produced a leaf node. These + * values are in the normals and corners arrays and have index values + * corresponding to the values of the figure on the left below. There + * are four other shared values that are precomputed in the sharedcorners + * and sharednormals arrays; their index values in those arrays are + * illustrated in the figure on the right: + * + * + * 3-------------------2 +---------2---------+ + * | | | | + * | 6 8 | | | + * | | | | + * V| 4 | 1 3 + * | | | | + * | 5 7 | | | + * | | | | + * 0-------------------1 +---------0---------+ + * U U + * + * Values inherited from Values pre-prepared in + * parent subdivision shared arrays + * + * + * When the four subdivisions are made, the parent parameters + * are passed to the children as follows (values from the + * shared arrays are prefaced with an s): + * + * 3--------------S2 S2--------------2 + * | | | | + * | | | | + * V | 6 | | 8 | + * | | | | + * | | | | + * S1--------------4 4--------------S3 + * U U + * + * Quadrant 3 Quadrant 2 + * + * S1--------------4 4--------------S3 + * | | | | + * | | | | + * V | 5 | | 7 | + * | | | | + * | | | | + * 0--------------S0 S0--------------1 + * U U + * + * Quadrant 0 Quadrant 1 + * + * + **********************************************************************/ - ON_Plane sharedframes[4]; - localsurf->FrameAt(usplit, v.Min(), sharedframes[0]); - localsurf->FrameAt(u.Min(), vsplit, sharedframes[1]); - localsurf->FrameAt(usplit, v.Max(), sharedframes[2]); - localsurf->FrameAt(u.Max(), vsplit, sharedframes[3]); - // When splitting via knots, we don't know what point frames[4] is until - // the knot is selected - localsurf->FrameAt(usplit, vsplit, frames[4]); + ON_Plane sharedframes[4]; + localsurf->FrameAt(usplit, v.Min(), sharedframes[0]); + localsurf->FrameAt(u.Min(), vsplit, sharedframes[1]); + localsurf->FrameAt(usplit, v.Max(), sharedframes[2]); + localsurf->FrameAt(u.Max(), vsplit, sharedframes[3]); + // When splitting via knots, we don't know what point frames[4] is until + // the knot is selected + localsurf->FrameAt(usplit, vsplit, frames[4]); - ON_Plane *newframes; - newframes = (ON_Plane *)bu_malloc(9*sizeof(ON_Plane), "new frames"); - newframes[0] = frames[0]; - newframes[1] = sharedframes[0]; - newframes[2] = frames[4]; - newframes[3] = sharedframes[1]; - newframes[4] = frames[5]; - quads[0] = subdivideSurfaceByKnots(q0surf, firstu, firstv, newframes, divDepth+1, depthLimit); - delete q0surf; - newframes[0] = sharedframes[0]; - newframes[1] = frames[1]; - newframes[2] = sharedframes[3]; - newframes[3] = frames[4]; - newframes[4] = frames[7]; - quads[1] = subdivideSurfaceByKnots(q1surf, secondu, firstv, newframes, divDepth+1, depthLimit); - delete q1surf; - newframes[0] = frames[4]; - newframes[1] = sharedframes[3]; - newframes[2] = frames[2]; - newframes[3] = sharedframes[2]; - newframes[4] = frames[8]; - quads[2] = subdivideSurfaceByKnots(q2surf, secondu, secondv, newframes, divDepth+1, depthLimit); - delete q2surf; - newframes[0] = sharedframes[1]; - newframes[1] = frames[4]; - newframes[2] = sharedframes[2]; - newframes[3] = frames[3]; - newframes[4] = frames[6]; - quads[3] = subdivideSurfaceByKnots(q3surf, firstu, secondv, newframes, divDepth+1, depthLimit); - delete q3surf; - bu_free(newframes, "free subsurface frames array"); + ON_Plane *newframes; + newframes = (ON_Plane *)bu_malloc(9*sizeof(ON_Plane), "new frames"); + newframes[0] = frames[0]; + newframes[1] = sharedframes[0]; + newframes[2] = frames[4]; + newframes[3] = sharedframes[1]; + newframes[4] = frames[5]; + quads[0] = subdivideSurfaceByKnots(q0surf, firstu, firstv, newframes, divDepth+1, depthLimit); + delete q0surf; + newframes[0] = sharedframes[0]; + newframes[1] = frames[1]; + newframes[2] = sharedframes[3]; + newframes[3] = frames[4]; + newframes[4] = frames[7]; + quads[1] = subdivideSurfaceByKnots(q1surf, secondu, firstv, newframes, divDepth+1, depthLimit); + delete q1surf; + newframes[0] = frames[4]; + newframes[1] = sharedframes[3]; + newframes[2] = frames[2]; + newframes[3] = sharedframes[2]; + newframes[4] = frames[8]; + quads[2] = subdivideSurfaceByKnots(q2surf, secondu, secondv, newframes, divDepth+1, depthLimit); + delete q2surf; + newframes[0] = sharedframes[1]; + newframes[1] = frames[4]; + newframes[2] = sharedframes[2]; + newframes[3] = frames[3]; + newframes[4] = frames[6]; + quads[3] = subdivideSurfaceByKnots(q3surf, firstu, secondv, newframes, divDepth+1, depthLimit); + delete q3surf; + bu_free(newframes, "free subsurface frames array"); - parent->m_trimmed = true; - parent->m_checkTrim = false; + parent->m_trimmed = true; + parent->m_checkTrim = false; - for (int i = 0; i < 4; i++) { - if (!quads[i]) { - continue; - } - if (!(quads[i]->m_trimmed)) { - parent->m_trimmed = false; - } - if (quads[i]->m_checkTrim) { - parent->m_checkTrim = true; - } - } - if (m_removeTrimmed) { - for (int i = 0; i < 4; i++) { - if (!quads[i]) { - continue; + for (int i = 0; i < 4; i++) { + if (!quads[i]) { + continue; + } + if (!(quads[i]->m_trimmed)) { + parent->m_trimmed = false; + } + if (quads[i]->m_checkTrim) { + parent->m_checkTrim = true; + } } - if (!(quads[i]->m_trimmed)) { - parent->addChild(quads[i]); + if (m_removeTrimmed) { + for (int i = 0; i < 4; i++) { + if (!quads[i]) { + continue; + } + if (!(quads[i]->m_trimmed)) { + parent->addChild(quads[i]); + } + } + } else { + for (int i = 0; i < 4; i++) { + parent->addChild(quads[i]); + } } + parent->BuildBBox(); + return parent; } - } else { - for (int i = 0; i < 4; i++) { - parent->addChild(quads[i]); - } - } - } else if (spanu_cnt > 1) { - ON_Interval firstu(u.Min(), usplit); - ON_Interval secondu(usplit, u.Max()); - ////////////////////////////////////// - ON_Surface *east = NULL; - ON_Surface *west = NULL; + if (do_u_split) { + ON_Interval firstu(u.Min(), usplit); + ON_Interval secondu(usplit, u.Max()); + ////////////////////////////////////// + ON_Surface *east = NULL; + ON_Surface *west = NULL; - ON_BoundingBox box = localsurf->BoundingBox(); + ON_BoundingBox box = localsurf->BoundingBox(); - int dir = 0; - bool split = localsurf->Split(dir, usplit, east, west); + int dir = 0; + bool split = localsurf->Split(dir, usplit, east, west); - /* FIXME: this needs to be handled more gracefully */ - if (!split || !east || !west) { - bu_log("DEBUG: Split failure (split:%d, surf1:%p, surf2:%p)\n", split, (void *)east, (void *)west); - delete parent; - return NULL; - } + /* FIXME: this needs to be handled more gracefully */ + if (!split || !east || !west) { + bu_log("DEBUG: Split failure (split:%d, surf1:%p, surf2:%p)\n", split, (void *)east, (void *)west); + delete parent; + return NULL; + } - east->ClearBoundingBox(); - west->ClearBoundingBox(); + east->ClearBoundingBox(); + west-... [truncated message content] |