Developer Documentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
Geometry.h
1 /*
2 Copyright (c) 2006, Michael Kazhdan and Matthew Bolitho
3 All rights reserved.
4 
5 Redistribution and use in source and binary forms, with or without modification,
6 are permitted provided that the following conditions are met:
7 
8 Redistributions of source code must retain the above copyright notice, this list of
9 conditions and the following disclaimer. Redistributions in binary form must reproduce
10 the above copyright notice, this list of conditions and the following disclaimer
11 in the documentation and/or other materials provided with the distribution.
12 
13 Neither the name of the Johns Hopkins University nor the names of its contributors
14 may be used to endorse or promote products derived from this software without specific
15 prior written permission.
16 
17 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
18 EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO THE IMPLIED WARRANTIES
19 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
20 SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
21 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
22 TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
23 BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
25 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
26 DAMAGE.
27 */
28 
29 #ifndef GEOMETRY_INCLUDED
30 #define GEOMETRY_INCLUDED
31 
32 #include <cmath>
33 #include <vector>
34 #include <cstdio>
35 #include <cstdlib>
36 #include "Hash.h"
37 
38 template<class Real>
39 Real Random(void);
40 
41 template< class Real >
42 struct Point3D
43 {
44  Real coords[3];
45  Point3D( void ) { coords[0] = coords[1] = coords[2] = Real(0); }
46  Point3D( Real v0 , Real v1 , Real v2 ){ coords[0] = v0 , coords[1] = v1 , coords[2] = v2; }
47  template< class Real2 > Point3D( const Point3D< Real2 >& p ){ coords[0] = Real( p[0] ) , coords[1] = Real( p[1] ) , coords[2] = Real( p[2] ); }
48  inline Real& operator[] ( int i ) { return coords[i]; }
49  inline const Real& operator[] ( int i ) const { return coords[i]; }
50  inline Point3D& operator += ( Point3D p ){ coords[0] += p.coords[0] , coords[1] += p.coords[1] , coords[2] += p.coords[2] ; return *this; }
51  inline Point3D& operator -= ( Point3D p ){ coords[0] -= p.coords[0] , coords[1] -= p.coords[1] , coords[2] -= p.coords[2] ; return *this; }
52  inline Point3D& operator *= ( Real r ){ coords[0] *= r , coords[1] *= r , coords[2] *= r ; return *this; }
53  inline Point3D& operator /= ( Real r ){ coords[0] /= r , coords[1] /= r , coords[2] /= r ; return *this; }
54  inline Point3D operator + ( Point3D p ) const { Point3D q ; q.coords[0] = coords[0] + p.coords[0] , q.coords[1] = coords[1] + p.coords[1] , q.coords[2] = coords[2] + p.coords[2] ; return q; }
55  inline Point3D operator - ( Point3D p ) const { Point3D q ; q.coords[0] = coords[0] - p.coords[0] , q.coords[1] = coords[1] - p.coords[1] , q.coords[2] = coords[2] - p.coords[2] ; return q; }
56  inline Point3D operator * ( Real r ) const { Point3D q ; q.coords[0] = coords[0] * r , q.coords[1] = coords[1] * r , q.coords[2] = coords[2] * r ; return q; }
57  inline Point3D operator / ( Real r ) const { return (*this) * ( Real(1.)/r ); }
58 };
59 
60 template< class Real >
61 struct XForm3x3
62 {
63  Real coords[3][3];
64  XForm3x3( void ) { for( int i=0 ; i<3 ; i++ ) for( int j=0 ; j<3 ; j++ ) coords[i][j] = Real(0.); }
65  static XForm3x3 Identity( void )
66  {
67  XForm3x3 xForm;
68  xForm(0,0) = xForm(1,1) = xForm(2,2) = Real(1.);
69  return xForm;
70  }
71  Real& operator() ( int i , int j ){ return coords[i][j]; }
72  const Real& operator() ( int i , int j ) const { return coords[i][j]; }
73  Point3D< Real > operator * ( const Point3D< Real >& p ) const
74  {
75  Point3D< Real > q;
76  for( int i=0 ; i<3 ; i++ ) for( int j=0 ; j<3 ; j++ ) q[i] += coords[j][i] * p[j];
77  return q;
78  }
79  XForm3x3 operator * ( const XForm3x3& m ) const
80  {
81  XForm3x3 n;
82  for( int i=0 ; i<3 ; i++ ) for( int j=0 ; j<3 ; j++ ) for( int k=0 ; k<3 ; k++ ) n.coords[i][j] += m.coords[i][k]*coords[k][j];
83  return n;
84  }
85  XForm3x3 transpose( void ) const
86  {
87  XForm3x3 xForm;
88  for( int i=0 ; i<3 ; i++ ) for( int j=0 ; j<3 ; j++ ) xForm( i , j ) = coords[j][i];
89  return xForm;
90  }
91  Real subDeterminant( int i , int j ) const
92  {
93  int i1 = (i+1)%3 , i2 = (i+2)%3;
94  int j1 = (j+1)%3 , j2 = (j+2)%3;
95  return coords[i1][j1] * coords[i2][j2] - coords[i1][j2] * coords[i2][j1];
96  }
97  Real determinant( void ) const { return coords[0][0] * subDeterminant( 0 , 0 ) + coords[1][0] * subDeterminant( 1 , 0 ) + coords[2][0] * subDeterminant( 2 , 0 ); }
98  XForm3x3 inverse( void ) const
99  {
100  XForm3x3 xForm;
101  Real d = determinant();
102  for( int i=0 ; i<3 ; i++ ) for( int j=0 ; j<3 ;j++ ) xForm.coords[j][i] = subDeterminant( i , j ) / d;
103  return xForm;
104  }
105 };
106 
107 template< class Real >
108 struct XForm4x4
109 {
110  Real coords[4][4];
111  XForm4x4( void ) { for( int i=0 ; i<4 ; i++ ) for( int j=0 ; j<4 ; j++ ) coords[i][j] = Real(0.); }
112  static XForm4x4 Identity( void )
113  {
114  XForm4x4 xForm;
115  xForm(0,0) = xForm(1,1) = xForm(2,2) = xForm(3,3) = Real(1.);
116  return xForm;
117  }
118  Real& operator() ( int i , int j ){ return coords[i][j]; }
119  const Real& operator() ( int i , int j ) const { return coords[i][j]; }
120  Point3D< Real > operator * ( const Point3D< Real >& p ) const
121  {
122  Point3D< Real > q;
123  for( int i=0 ; i<3 ; i++ )
124  {
125  for( int j=0 ; j<3 ; j++ ) q[i] += coords[j][i] * p[j];
126  q[i] += coords[3][i];
127  }
128  return q;
129  }
130  XForm4x4 operator * ( const XForm4x4& m ) const
131  {
132  XForm4x4 n;
133  for( int i=0 ; i<4 ; i++ ) for( int j=0 ; j<4 ; j++ ) for( int k=0 ; k<4 ; k++ ) n.coords[i][j] += m.coords[i][k]*coords[k][j];
134  return n;
135  }
136  XForm4x4 transpose( void ) const
137  {
138  XForm4x4 xForm;
139  for( int i=0 ; i<4 ; i++ ) for( int j=0 ; j<4 ; j++ ) xForm( i , j ) = coords[j][i];
140  return xForm;
141  }
142  Real subDeterminant( int i , int j ) const
143  {
144  XForm3x3< Real > xForm;
145  int ii[] = { (i+1)%4 , (i+2)%4 , (i+3)%4 } , jj[] = { (j+1)%4 , (j+2)%4 , (j+3)%4 };
146  for( int _i=0 ; _i<3 ; _i++ ) for( int _j=0 ; _j<3 ; _j++ ) xForm( _i , _j ) = coords[ ii[_i] ][ jj[_j] ];
147  return xForm.determinant();
148  }
149  Real determinant( void ) const { return coords[0][0] * subDeterminant( 0 , 0 ) - coords[1][0] * subDeterminant( 1 , 0 ) + coords[2][0] * subDeterminant( 2 , 0 ) - coords[3][0] * subDeterminant( 3 , 0 ); }
150  XForm4x4 inverse( void ) const
151  {
152  XForm4x4 xForm;
153  Real d = determinant();
154  for( int i=0 ; i<4 ; i++ ) for( int j=0 ; j<4 ;j++ )
155  if( (i+j)%2==0 ) xForm.coords[j][i] = subDeterminant( i , j ) / d;
156  else xForm.coords[j][i] = -subDeterminant( i , j ) / d;
157  return xForm;
158  }
159 };
160 
161 
162 template<class Real>
163 Point3D<Real> RandomBallPoint(void);
164 
165 template<class Real>
166 Point3D<Real> RandomSpherePoint(void);
167 
168 template<class Real>
169 double Length(const Point3D<Real>& p);
170 
171 template<class Real>
172 double SquareLength(const Point3D<Real>& p);
173 
174 template<class Real>
175 double Distance(const Point3D<Real>& p1,const Point3D<Real>& p2);
176 
177 template<class Real>
178 double SquareDistance(const Point3D<Real>& p1,const Point3D<Real>& p2);
179 
180 template <class Real>
181 void CrossProduct(const Point3D<Real>& p1,const Point3D<Real>& p2,Point3D<Real>& p);
182 
183 
184 class Edge{
185 public:
186  double p[2][2];
187  double Length(void) const{
188  double d[2];
189  d[0]=p[0][0]-p[1][0];
190  d[1]=p[0][1]-p[1][1];
191 
192  return sqrt(d[0]*d[0]+d[1]*d[1]);
193  }
194 };
195 class Triangle{
196 public:
197  double p[3][3];
198  double Area(void) const{
199  double v1[3] , v2[3] , v[3];
200  for( int d=0 ; d<3 ; d++ )
201  {
202  v1[d] = p[1][d] - p[0][d];
203  v2[d] = p[2][d] - p[0][d];
204  }
205  v[0] = v1[1]*v2[2] - v1[2]*v2[1];
206  v[1] = -v1[0]*v2[2] + v1[2]*v2[0];
207  v[2] = v1[0]*v2[1] - v1[1]*v2[0];
208  return sqrt( v[0]*v[0] + v[1]*v[1] + v[2]*v[2] ) / 2;
209  }
210  double AspectRatio(void) const{
211  double d=0;
212  int i,j;
213  for(i=0;i<3;i++){
214  for(i=0;i<3;i++)
215  for(j=0;j<3;j++){d+=(p[(i+1)%3][j]-p[i][j])*(p[(i+1)%3][j]-p[i][j]);}
216  }
217  return Area()/d;
218  }
219 
220 };
221 class CoredPointIndex{
222 public:
223  int index;
224  char inCore;
225 
226  int operator == (const CoredPointIndex& cpi) const {return (index==cpi.index) && (inCore==cpi.inCore);};
227  int operator != (const CoredPointIndex& cpi) const {return (index!=cpi.index) || (inCore!=cpi.inCore);};
228 };
229 class EdgeIndex{
230 public:
231  int idx[2];
232 };
233 class CoredEdgeIndex{
234 public:
235  CoredPointIndex idx[2];
236 };
237 class TriangleIndex{
238 public:
239  int idx[3];
240 };
241 
242 class TriangulationEdge
243 {
244 public:
245  TriangulationEdge(void);
246  int pIndex[2];
247  int tIndex[2];
248 };
249 
250 class TriangulationTriangle
251 {
252 public:
253  TriangulationTriangle(void);
254  int eIndex[3];
255 };
256 
257 template<class Real>
258 class Triangulation
259 {
260 public:
261 
262  std::vector<Point3D<Real> > points;
263  std::vector<TriangulationEdge> edges;
264  std::vector<TriangulationTriangle> triangles;
265 
266  int factor( int tIndex,int& p1,int& p2,int& p3);
267  double area(void);
268  double area( int tIndex );
269  double area( int p1 , int p2 , int p3 );
270  int flipMinimize( int eIndex);
271  int addTriangle( int p1 , int p2 , int p3 );
272 
273 protected:
274  hash_map<long long,int> edgeMap;
275  static long long EdgeIndex( int p1 , int p2 );
276  double area(const Triangle& t);
277 };
278 
279 
280 template<class Real>
281 void EdgeCollapse(const Real& edgeRatio,std::vector<TriangleIndex>& triangles,std::vector< Point3D<Real> >& positions,std::vector<Point3D<Real> >* normals);
282 template<class Real>
283 void TriangleCollapse(const Real& edgeRatio,std::vector<TriangleIndex>& triangles,std::vector<Point3D<Real> >& positions,std::vector<Point3D<Real> >* normals);
284 
285 struct CoredVertexIndex
286 {
287  int idx;
288  bool inCore;
289 };
290 class CoredMeshData
291 {
292 public:
293  std::vector<Point3D<float> > inCorePoints;
294  virtual void resetIterator( void ) = 0;
295 
296  virtual int addOutOfCorePoint( const Point3D<float>& p ) = 0;
297  virtual int addPolygon( const std::vector< CoredVertexIndex >& vertices ) = 0;
298 
299  virtual int nextOutOfCorePoint( Point3D<float>& p )=0;
300  virtual int nextPolygon( std::vector< CoredVertexIndex >& vertices ) = 0;
301 
302  virtual int outOfCorePointCount(void)=0;
303  virtual int polygonCount( void ) = 0;
304 };
305 // Stores the iso-span of each vertex, rather than it's position
306 class CoredMeshData2
307 {
308 public:
309  struct Vertex
310  {
311  Point3D< float > start , end;
312  float value;
313  Vertex( void ):value(0.f) { ; }
314  Vertex( Point3D< float > s , Point3D< float > e , float v ):start(s),end(e),value(v) { }
315  Vertex( Point3D< float > s , Point3D< float > e , Point3D< float > p ):
316  start(s),end(e)
317  {
318  // < p , e-s > = < s + v*(e-s) , e-s >
319  // < p , e-s > - < s , e-s > = v || e-s || ^2
320  // v = < p-s , e-s > / || e-s ||^2
321  Point3D< float > p1 = p-s , p2 = e-s;
322  value = ( p1[0] * p2[0] + p1[1] * p2[1] + p1[2] * p2[2] ) / ( p2[0] * p2[0] + p2[1] * p2[1] + p2[2] * p2[2] );
323  }
324  };
325  std::vector< Vertex > inCorePoints;
326  virtual void resetIterator( void ) = 0;
327 
328  virtual int addOutOfCorePoint( const Vertex& v ) = 0;
329  virtual int addPolygon( const std::vector< CoredVertexIndex >& vertices ) = 0;
330 
331  virtual int nextOutOfCorePoint( Vertex& v ) = 0;
332  virtual int nextPolygon( std::vector< CoredVertexIndex >& vertices ) = 0;
333 
334  virtual int outOfCorePointCount( void )=0;
335  virtual int polygonCount( void ) = 0;
336 };
337 
338 class CoredVectorMeshData : public CoredMeshData
339 {
340  std::vector<Point3D<float> > oocPoints;
341  std::vector< std::vector< int > > polygons;
342  int polygonIndex;
343  int oocPointIndex;
344 public:
345  CoredVectorMeshData(void);
346 
347  void resetIterator(void);
348 
349  int addOutOfCorePoint( const Point3D<float>& p );
350  int addPolygon( const std::vector< CoredVertexIndex >& vertices );
351 
352  int nextOutOfCorePoint( Point3D<float>& p );
353  int nextPolygon( std::vector< CoredVertexIndex >& vertices );
354 
355  int outOfCorePointCount(void);
356  int polygonCount( void );
357 };
358 class CoredVectorMeshData2 : public CoredMeshData2
359 {
360  std::vector< CoredMeshData2::Vertex > oocPoints;
361  std::vector< std::vector< int > > polygons;
362  int polygonIndex;
363  int oocPointIndex;
364 public:
365  CoredVectorMeshData2( void );
366 
367  void resetIterator(void);
368 
369  int addOutOfCorePoint( const CoredMeshData2::Vertex& v );
370  int addPolygon( const std::vector< CoredVertexIndex >& vertices );
371 
372  int nextOutOfCorePoint( CoredMeshData2::Vertex& v );
373  int nextPolygon( std::vector< CoredVertexIndex >& vertices );
374 
375  int outOfCorePointCount( void );
376  int polygonCount( void );
377 };
378 class BufferedReadWriteFile
379 {
380  bool tempFile;
381  FILE* _fp;
382  char *_buffer , _fileName[1024];
383  size_t _bufferIndex , _bufferSize;
384 public:
385  BufferedReadWriteFile( char* fileName=NULL , int bufferSize=(1<<20) );
386  ~BufferedReadWriteFile( void );
387  bool write( const void* data , size_t size );
388  bool read ( void* data , size_t size );
389  void reset( void );
390 };
391 class CoredFileMeshData : public CoredMeshData
392 {
393  char pointFileName[1024] , polygonFileName[1024];
394  BufferedReadWriteFile *oocPointFile , *polygonFile;
395  int oocPoints , polygons;
396 public:
397  CoredFileMeshData( void );
398  ~CoredFileMeshData( void );
399 
400  void resetIterator( void );
401 
402  int addOutOfCorePoint( const Point3D< float >& p );
403  int addPolygon( const std::vector< CoredVertexIndex >& vertices );
404 
405  int nextOutOfCorePoint( Point3D< float >& p );
406  int nextPolygon( std::vector< CoredVertexIndex >& vertices );
407 
408  int outOfCorePointCount( void );
409  int polygonCount( void );
410 };
411 class CoredFileMeshData2 : public CoredMeshData2
412 {
413  FILE *oocPointFile , *polygonFile;
414  int oocPoints , polygons;
415 public:
416  CoredFileMeshData2( void );
417  ~CoredFileMeshData2( void );
418 
419  void resetIterator( void );
420 
421  int addOutOfCorePoint( const CoredMeshData2::Vertex& v );
422  int addPolygon( const std::vector< CoredVertexIndex >& vertices );
423 
424  int nextOutOfCorePoint( CoredMeshData2::Vertex& v );
425  int nextPolygon( std::vector< CoredVertexIndex >& vertices );
426 
427  int outOfCorePointCount( void );
428  int polygonCount( void );
429 };
430 #include "Geometry.inl"
431 
432 #endif // GEOMETRY_INCLUDED
Edge
Definition: Geometry.h:184