Cleanup: spelling
[blender-staging.git] / source / blender / freestyle / intern / geometry / GeomUtils.h
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * ***** END GPL LICENSE BLOCK *****
19  */
20
21 #ifndef __GEOMUTILS_H__
22 #define __GEOMUTILS_H__
23
24 /** \file blender/freestyle/intern/geometry/GeomUtils.h
25  *  \ingroup freestyle
26  *  \brief Various tools for geometry
27  *  \author Stephane Grabli
28  *  \date 12/04/2002
29  */
30
31 #include <vector>
32
33 #include "Geom.h"
34
35 #include "../system/FreestyleConfig.h"
36
37 using namespace std;
38
39 namespace Freestyle {
40
41 using namespace Geometry;
42
43 namespace GeomUtils {
44
45 //
46 // Templated procedures
47 //
48 /////////////////////////////////////////////////////////////////////////////
49
50 /*! Computes the distance from a point P to a segment AB */
51 template<class T>
52 real distPointSegment(const T& P, const T& A, const T& B)
53 {
54         T AB, AP, BP;
55         AB = B - A;
56         AP = P - A;
57         BP = P - B;
58
59         real c1(AB * AP);
60         if (c1 <= 0)
61                 return AP.norm();
62
63         real c2(AB * AB);
64         if (c2 <= c1)
65                 return BP.norm();
66
67         real b = c1 / c2;
68         T Pb, PPb;
69         Pb = A + b * AB;
70         PPb = P - Pb;
71
72         return PPb.norm();
73 }
74
75 //
76 // Non-templated procedures
77 //
78 /////////////////////////////////////////////////////////////////////////////
79 typedef enum {
80         DONT_INTERSECT,
81         DO_INTERSECT,
82         COLINEAR,
83         COINCIDENT,
84 } intersection_test;
85
86 intersection_test intersect2dSeg2dSeg(const Vec2r& p1, const Vec2r& p2, // first segment
87                                       const Vec2r& p3, const Vec2r& p4, // second segment
88                                       Vec2r& res);                      // found intersection point
89
90 intersection_test intersect2dLine2dLine(const Vec2r& p1, const Vec2r& p2, // first segment
91                                         const Vec2r& p3, const Vec2r& p4, // second segment
92                                         Vec2r& res);                      // found intersection point
93
94 intersection_test intersect2dSeg2dSegParametric(const Vec2r& p1, const Vec2r& p2, // first segment
95                                                 const Vec2r& p3, const Vec2r& p4, // second segment
96                                                 real& t,                          // I = P1 + t * P1P2)
97                                                 real& u,                          // I = P3 + u * P3P4
98                                                 real epsilon = M_EPSILON);
99
100 /*! check whether a 2D segment intersect a 2D region or not */
101 bool intersect2dSeg2dArea(const Vec2r& min, const Vec2r& max, const Vec2r& A, const Vec2r& B);
102
103 /*! check whether a 2D segment is included in a 2D region or not */
104 bool include2dSeg2dArea(const Vec2r& min, const Vec2r& max, const Vec2r& A, const Vec2r& B);
105
106 /*! Box-triangle overlap test, adapted from Tomas Akenine-Möller code */
107 bool overlapTriangleBox(Vec3r& boxcenter, Vec3r& boxhalfsize, Vec3r triverts[3]);
108
109 /*! Fast, Minimum Storage Ray-Triangle Intersection, adapted from Tomas Möller and Ben Trumbore code. */
110 bool intersectRayTriangle(const Vec3r& orig, const Vec3r& dir, const Vec3r& v0, const Vec3r& v1, const Vec3r& v2,
111                           real& t,                         // I = orig + t * dir
112                           real& u, real& v,                // I = (1 - u - v) * v0 + u * v1 + v * v2
113                           const real epsilon = M_EPSILON); // the epsilon to use
114
115 /*! Intersection between plane and ray adapted from Graphics Gems, Didier Badouel */
116 intersection_test intersectRayPlane(const Vec3r& orig, const Vec3r& dir, // ray origin and direction
117                                     // plane's normal and offset (plane = { P / P.N + d = 0 })
118                                     const Vec3r& norm, const real d,
119                                     real& t,                         // I = orig + t * dir
120                                     const real epsilon = M_EPSILON); // the epsilon to use
121
122 /*! Intersection Ray-Bounding box (axis aligned).
123  *  Adapted from Williams et al, "An Efficient Robust Ray-Box Intersection Algorithm", JGT 10:1 (2005), pp. 49-54.
124  */
125 bool intersectRayBBox(const Vec3r& orig, const Vec3r& dir,      // ray origin and direction
126                       const Vec3r& boxMin, const Vec3r& boxMax, // the bbox
127                       // the interval in which at least on of the intersections must happen
128                       real t0, real t1,
129                       real& tmin,                               // Imin = orig + tmin * dir is the first intersection
130                       real& tmax,                               // Imax = orig + tmax * dir is the second intersection
131                       real epsilon = M_EPSILON);                // the epsilon to use
132
133 /*! Checks whether 3D point P lies inside or outside of the triangle ABC */
134 bool includePointTriangle(const Vec3r& P, const Vec3r& A, const Vec3r& B, const Vec3r& C);
135
136 void transformVertex(const Vec3r& vert, const Matrix44r& matrix, Vec3r& res);
137
138 void transformVertices(const vector<Vec3r>& vertices, const Matrix44r& trans, vector<Vec3r>& res);
139
140 Vec3r rotateVector(const Matrix44r& mat, const Vec3r& v);
141
142 //
143 // Coordinates systems changing procedures
144 //
145 /////////////////////////////////////////////////////////////////////////////
146
147 /*! From world to image
148  *  p
149  *    point's coordinates expressed in world coordinates system
150  *  q
151  *    vector in which the result will be stored
152  *  model_view_matrix
153  *    The model view matrix expressed in line major order (OpenGL
154  *    matrices are column major ordered)
155  *  projection_matrix
156  *    The projection matrix expressed in line major order (OpenGL
157  *    matrices are column major ordered)
158  *  viewport
159  *    The viewport: x,y coordinates followed by width and height (OpenGL like viewport)
160  */
161 void fromWorldToImage(const Vec3r& p, Vec3r& q, const real model_view_matrix[4][4], const real projection_matrix[4][4],
162                       const int viewport[4]);
163
164 /*! From world to image
165  *  p
166  *    point's coordinates expressed in world coordinates system
167  *  q
168  *    vector in which the result will be stored
169  *  transform
170  *    The transformation matrix (gathering model view and projection), 
171  *    expressed in line major order (OpenGL matrices are column major ordered)
172  *  viewport
173  *    The viewport: x,y coordinates followed by width and height (OpenGL like viewport)
174  */
175 void fromWorldToImage(const Vec3r& p, Vec3r& q, const real transform[4][4], const int viewport[4]);
176
177 /*! Projects from world coordinates to camera coordinates 
178  *  Returns the point's coordinates expressed in the camera's 
179  *  coordinates system.
180  *  p
181  *    point's coordinates expressed in world coordinates system
182  *  q
183  *    vector in which the result will be stored
184  *  model_view_matrix
185  *    The model view matrix expressed in line major order (OpenGL
186  *    matrices are column major ordered)
187  */
188 void fromWorldToCamera(const Vec3r& p, Vec3r& q, const real model_view_matrix[4][4]);
189
190 /*! Projects from World Coordinates to retina coordinates
191  *  Returns the point's coordinates expressed in Retina system.
192  *  p
193  *    point's coordinates expressed in camera system
194  *  q
195  *    vector in which the result will be stored
196  *  projection_matrix
197  *    The projection matrix expressed in line major order (OpenGL
198  *    matrices are column major ordered)
199  */
200 void fromCameraToRetina(const Vec3r& p, Vec3r& q, const real projection_matrix[4][4]);
201
202 /*! From retina to image.
203  *  Returns the coordinates expressed in Image coordinates system.
204  *  p
205  *    point's coordinates expressed in retina system
206  *  q
207  *    vector in which the result will be stored
208  *  viewport
209  *    The viewport: x,y coordinates followed by width and height (OpenGL like viewport).
210  */
211 void fromRetinaToImage(const Vec3r& p, Vec3r& q, const int viewport[4]);
212
213 /*! From image to retina
214  *  p
215  *    point's coordinates expressed in image system
216  *  q
217  *    vector in which the result will be stored
218  *  viewport
219  *    The viewport: x,y coordinates followed by width and height (OpenGL like viewport).
220  */
221 void fromImageToRetina(const Vec3r& p, Vec3r& q, const int viewport[4]);
222
223 /*! computes the coordinates of q in the camera coordinates system, 
224  *  using the known z coordinates of the 3D point. 
225  *  That means that this method does not inverse any matrices, 
226  *  it only computes X and Y from x,y and Z)
227  *  p
228  *    point's coordinates expressed in retina system
229  *  q
230  *    vector in which the result will be stored
231  *  projection_matrix
232  *    The projection matrix expressed in line major order (OpenGL
233  *    matrices are column major ordered)
234  */
235 void fromRetinaToCamera(const Vec3r& p, Vec3r& q, real z, const real projection_matrix[4][4]);
236
237 /*! Projects from camera coordinates to world coordinates
238  *  Returns the point's coordinates expressed in the world's 
239  *  coordinates system.
240  *  p
241  *    point's coordinates expressed in the camera coordinates system
242  *  q
243  *    vector in which the result will be stored
244  *  model_view_matrix
245  *    The model view matrix expressed in line major order (OpenGL
246  *    matrices are column major ordered)
247  */
248 void fromCameraToWorld(const Vec3r& p, Vec3r& q, const real model_view_matrix[4][4]);
249
250 } // end of namespace GeomUtils
251
252 } /* namespace Freestyle */
253
254 #endif // __GEOMUTILS_H__