BSPImplT.hh 9.03 KB
Newer Older
Jan Möbius's avatar
Jan Möbius committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
/*===========================================================================*\
*                                                                            *
*                              OpenFlipper                                   *
 *           Copyright (c) 2001-2015, RWTH-Aachen University                 *
 *           Department of Computer Graphics and Multimedia                  *
 *                          All rights reserved.                             *
 *                            www.openflipper.org                            *
 *                                                                           *
 *---------------------------------------------------------------------------*
 * This file is part of OpenFlipper.                                         *
 *---------------------------------------------------------------------------*
 *                                                                           *
 * 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.              *
*                                                                            *
\*===========================================================================*/


//=============================================================================
//
//  CLASS BSPImplT
//
//=============================================================================

#ifndef BSPIMPLT_HH
#define BSPIMPLT_HH


//== INCLUDES =================================================================


#include <OpenMesh/Core/Geometry/VectorT.hh>


//== CLASS DEFINITION =========================================================
#include <vector>
#include <ostream>

template <class BSPCore>
class BSPImplT : public BSPCore
{
public: //---------------------------------------------------------------------

  typedef typename BSPCore::Traits      Traits;
  typedef typename BSPCore::Handle      Handle;
  typedef typename BSPCore::Point       Point;
  typedef typename BSPCore::Scalar      Scalar;
  typedef typename BSPCore::Node        Node;
  typedef typename BSPCore::Handles     Handles;
  typedef typename BSPCore::HandleIter  HandleIter;


public: //---------------------------------------------------------------------

  BSPImplT(const Traits& _traits, const Scalar& _infinity = std::numeric_limits<Scalar>::infinity()) :
      BSPCore(_traits),
      infinity_(_infinity) {}
  ~BSPImplT() {}


  /// Store nearest neighbor information
  struct NearestNeighbor
  {
    NearestNeighbor() {}
    NearestNeighbor(Handle _h, Scalar _d) : handle(_h), dist(_d) {}
    Handle  handle;
    Scalar  dist;
  };

  /// Store nearest neighbor information
  typedef  std::vector< std::pair<Handle,Scalar> > RayCollision;

  /// Return handle of the nearest neighbor face
  NearestNeighbor nearest(const Point& _p) const;

  /** \brief intersect mesh with ray
   *
   * This function shots a ray through the mesh and collects all intersected triangles and
   * the handle of the closest face ( non-directional, so no matter of the ray direction, the
   * closest face handle is returned in either direction)
   *
   * @param _p Start point of the ray
   * @param _r Ray direction
   * @return   Collision information
   */
  RayCollision raycollision (const Point& _p, const Point& _r) const;

  /** \brief intersect mesh with ray
   *
   * This function shots a ray through the mesh and collects all intersected triangles and
   * the handle of the closest face ( directional, so the ray direction is taken into account!).
   *
   * Only hits with a distance > 0.0 to the point p will be collected (_p will be skipped!)
   *
   * @param _p Start point of the ray
   * @param _r Ray direction
   * @return   Collision information
   */
  RayCollision directionalRaycollision (const Point& _p, const Point& _r) const;

  /** \brief intersect mesh with ray
   *
   * This function shots a ray through the mesh and determines the first intersected triangle and
   * the handle of the closest face ( directional, so the ray direction is taken into account!).
   *
   * Only hits with a distance > 0.0 to the point p will be collected (_p will be skipped!).
   * Note that for compatibility reasons the return type is still a vector of collisions.
   *
   * @param _p Start point of the ray
   * @param _r Ray direction
   * @return   Collision information
   */
  RayCollision nearestRaycollision(const Point& _p, const Point& _r) const;

  /** \brief intersect mesh with open ball
   *
   * All triangles that have at least one vertex (!) inside the ball are given to the Callback,
   * triangles which have no vertex inside the ball but intersect it MAY be returned. (TODO)
   * Each triangle can be returned up to three times, make sure to handle this, e.g.
   * by putting the values into an std::(unordered_)set.
   *
   * @param _c Center of the ball
   * @param _r Radius of the ball
   * @param _callback Callable that accepts Handle or const Handle&, e.g. (const Handle &h) -> void
   */
  template<class Callback>
  void intersectBall(const Point & _c, Scalar _r, Callback _callback) const;

private: //---------------------------------------------------------------------


  /// Store nearest neighbor information
  struct NearestNeighborData
  {
    Point   ref;
    Scalar  dist;
    Handle  nearest;

    friend std::ostream &operator<< (std::ostream &stream, const NearestNeighborData &data) {
        stream << "[NearestNeghborData instance. ref: " << data.ref << ", dist: " << data.dist << ", nearest: " << data.nearest.idx() << "]";
        return stream;
    }
  };

  /// Store ray collide information
  struct RayCollisionData
  {
172
173
    RayCollisionData() : ref(), ray() {}

Jan Möbius's avatar
Jan Möbius committed
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
    Point   ref;
    Point   ray;
    RayCollision hit_handles;
  };


  // Recursive part of nearest()
  void _nearest(Node* _node, NearestNeighborData& _data) const;

  /**  \brief recursive part of raycollision()
   *
   * @param _node The current node in the tree
   * @param _data Data pointer, used to collect the collision information
   */
  void _raycollision_non_directional(Node* _node, RayCollisionData& _data) const;

  /**  \brief recursive part of directionalRaycollision()
   *
   * @param _node The current node in the tree
   * @param _data Data pointer, used to collect the collision information
   */
  void _raycollision_directional(Node* _node, RayCollisionData& _data) const;

  void _raycollision_nearest_directional(Node* _node, RayCollisionData& _data) const;

  template<class Callback>
  void _intersect_ball(const Node& _node, const Point & _c, Scalar _r, Callback _callback) const;

  template<typename T,typename U>
  struct less_pair_second: public std::binary_function<T,U,bool> {
      bool operator()(const std::pair<T,U> &left, const std::pair<T,U> &right) {
          return (fabs(left.second) < fabs(right.second));
      }
  };

  const Scalar infinity_;

};

//=============================================================================
#if defined(OM_INCLUDE_TEMPLATES) && !defined(BSPIMPLT_C)
#  define BSPIMPLT_TEMPLATES
216
#  include "BSPImplT_impl.hh"
Jan Möbius's avatar
Jan Möbius committed
217
218
219
220
#endif
//=============================================================================
#endif // BSPIMPLT_HH defined
//=============================================================================