HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
GU_IntersectionAnalysis.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: GU_IntersectionAnalysis.h
7  *
8  */
9 
10 #pragma once
11 
12 #include "GU_API.h"
13 #include "GU_Detail.h"
14 #include <UT/UT_SharedPtr.h>
15 #include <UT/UT_Array.h>
17 #include <utility>
18 #include <string>
19 #include <hboost/optional.hpp>
20 
22 {
23 public:
24  /// Shorthands for common vector types
25  using Real = fpreal64;
30 
31  /// Supporting data structures specifying the information about triangle and
32  /// segment intersections
33 
34  /// Where on a segment does the intersection lie
36  {
37  SEGMENT_INTERIOR = 0, // intersection occurs in the interior of the segment
38  SEGMENT_VERTEX, // intersection occurs at the segment vertex
39  SEGMENT_SEGMENT // the intersection forms a line segment
40  };
41 
43  {
45  SegmentIntersectionInfo(Real t) // know the type from t value
46  : type(t==0||t==1 ? SEGMENT_VERTEX : SEGMENT_INTERIOR), t(t), t2(-1)
47  { }
48  SegmentIntersectionInfo(Real t, Real t2) // type is always segment
49  : type(SEGMENT_SEGMENT), t(t), t2(t2)
50  { }
52 
53  /// t is the intersection parameter giving the intersection point:
54  /// x = (1-t)*a + t*b
55  /// where (a,b) marks the corresponding segment
57  Real t2; // valid only when type == SEGMENT_SEGMENT
58  };
59 
60  /// Where on the triangle does the intersection lie
62  {
63  TRIANGLE_INTERIOR = 0, // intersection point inside the triangle
64  TRIANGLE_EDGE, // intersection point on triangle boundary
65  TRIANGLE_VERTEX, // intersection point on triangle vertex
66  TRIANGLE_SEGMENT // intersection forms a line segment
67  };
68 
70  {
73  : type(t), idx(i), idx2(-1) { }
75  : type(t), idx(i), idx2(i2) { }
77 
78  // edge idx if type == TRIANGLE_EDGE, and vtx idx if type == TRIANGLE_VERTEX
79  int idx;
80  int idx2; // (WIP) not -1 only when type == TRIANGLE_SEGMENT
81  Real u, v;
82  Real u2, v2; // (WIP) valid only when type == TRIANGLE_SEGMENT
83  };
84 
85  /// This routine computes the intersection between a segment and a triangle.
86  /// PRE: p0,p1,p2 are triangle vertex positions
87  /// n is the triangle normal ( e.g. cross(p1-p0, p2-p0).normalize() )
88  /// a,b are segment vertex positions
89  /// Assume that all points are distinct.
90  /// POST: Returns the intersection info as defined above. This method
91  /// guarantees that the local primitive 1-u-v,u,v, coordinates are in the
92  /// triangle interior (i.e. no coordinate is exactly 0 or 1) if
93  /// intersection type is TRIANGLE_INTERIOR. Naturally, one of 1-u-v,u,v
94  /// is zero if the type is TRIANGLE_EDGE, and two are 0 if type is
95  /// TRIANGLE_VERTEX.
96  static hboost::optional<std::pair<SegmentIntersectionInfo, TriangleIntersectionInfo>>
97  triangleSegmentIntersect(
98  const Vec3& p0, const Vec3& p1, const Vec3& p2, const Vec3& n,
99  const Vec3& a, const Vec3& b);
100  template<bool USEFILTER>
101  static hboost::optional<std::pair<SegmentIntersectionInfo, TriangleIntersectionInfo>>
102  triangleSegmentIntersect(
103  const Vec3& p0, const Vec3& p1, const Vec3& p2, const Vec3& n,
104  const Vec3& a, const Vec3& b, const UT_GeometryPredicates<Real,USEFILTER>& pred);
105 
106  /// PRE: Two segments p0-p1 and q0-q1. Assume that all points are distinct.
107  /// POST: Find t coordinates for the two segments respectively
108  /// if the intersection is close to endpoints p0,p1,q0,q1 then these
109  /// will be accordinly snapped to 0 or 1 so you can test them against
110  /// 1 and 0 later with operator==
111  static hboost::optional< std::pair<SegmentIntersectionInfo, SegmentIntersectionInfo> >
112  segmentSegmentIntersect(
113  const Vec3& p0, const Vec3& p1,
114  const Vec3& q0, const Vec3& q1);
115  template<bool USEFILTER>
116  static hboost::optional< std::pair<SegmentIntersectionInfo, SegmentIntersectionInfo> >
117  segmentSegmentIntersect(
118  const Vec3& p0, const Vec3& p1,
119  const Vec3& q0, const Vec3& q1, const UT_GeometryPredicates<Real,USEFILTER>& pred);
120 
121  /// Approximate version of the function above.
122  /// tol is the distance tolerance between line segments. If tol == 0, this
123  /// function simply calls the function above
124  static hboost::optional< std::pair<SegmentIntersectionInfo, SegmentIntersectionInfo> >
125  segmentSegmentIntersect(
126  const Vec3& p0, const Vec3& p1,
127  const Vec3& q0, const Vec3& q1, Real tol);
128  template<bool USEFILTER>
129  static hboost::optional< std::pair<SegmentIntersectionInfo, SegmentIntersectionInfo> >
130  segmentSegmentIntersect(
131  const Vec3& p0, const Vec3& p1,
132  const Vec3& q0, const Vec3& q1, Real tol, const UT_GeometryPredicates<Real,USEFILTER>& pred);
133 
134  /// Given valid details gdp0 and gdp1, returns points of intersection
135  /// between the two details or self-intersection if gdp1 is null. This routine
136  /// requires a valid gdp containing triangles and curves only, as ensured by
137  /// validateGeometry
138  static UT_Vector3DArray findIntersectionPoints(
139  // input
140  const GEO_Detail* gdp0,
141  const GA_PrimitiveGroup* prim_grp0,
142  const GEO_Detail* gdp1 = NULL,
143  const GA_PrimitiveGroup* prim_grp1 = NULL,
144  Real prox_tol = 0,
145  // output
146  UT_Array<UT_Int32Array>* input_num_arr = NULL,
147  UT_Array<UT_Int64Array>* prim_num_arr = NULL,
148  UT_Array<UT_Fpreal32Array>* prim_uvw_arr = NULL,
149  UT_Array<UT_Int64Array>* pt_num_arr = NULL);
150 
151  /// Returns a shared pointer to a GU_Detail containing validated geometry
152  /// from the given input GU_Detail. A warning message is provided if the
153  /// input detail needed significant changes for validation.
154  /// This routine insures that the detail passed into findIntersectionPoints
155  /// is valid.
156  static UT_SharedPtr<GU_Detail> validateGeometry(const GU_Detail* geo, std::string& warning);
157 
158 private:
159  /// Given a triangle p0-p1-p2 and a segment a-b on the 2D plane, return
160  /// the intersection data. Incomplete WIP
161  static hboost::optional< std::pair<SegmentIntersectionInfo, TriangleIntersectionInfo> >
162  triangleSegmentIntersect2D(
163  const Vec2& p0, const Vec2& p1, const Vec2& p2,
164  const Vec2& a, const Vec2& b);
165 
166  // figure out intersection between the two given intervals:
167  // [a[0] a[1]] and [b[0] b[1]]
168  // the returned Vec2 denote intervals as fractions of the input intervals
169  // respectively. E.g. (0,1) will denote the full input interval
170  static hboost::optional< std::pair<Vec2,Vec2> >
171  intervalIntersection(Vec2 a, Vec2 b, Real tol);
172 };
GLsizei const GLchar *const * string
Definition: glcorearb.h:813
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
TriangleIntersectionInfo(TriangleIntersectionType t, int i)
Wrapper around hboost::shared_ptr.
Definition: UT_SharedPtr.h:27
3D Vector class.
4D Vector class.
Definition: UT_Vector4.h:152
2D Vector class.
Definition: UT_Vector2.h:137
SegmentIntersectionType
Where on a segment does the intersection lie.
png_uint_32 i
Definition: png.h:2877
GLdouble n
Definition: glcorearb.h:2007
TriangleIntersectionInfo(TriangleIntersectionType t, int i, int i2)
double fpreal64
Definition: SYS_Types.h:191
#define GU_API
Definition: GU_API.h:11
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
TriangleIntersectionType
Where on the triangle does the intersection lie.
fpreal64 Real
Shorthands for common vector types.
GLint GLint GLsizei GLint GLenum GLenum type
Definition: glcorearb.h:107