little_helpers/tikz/sketch-0.2.161/geometry.h

   1 /* geometry.h
   2    Copyright (C) 2005,2006,2007,2008 Eugene K. Ressler, Jr.
   3
   4 This file is part of Sketch, a small, simple system for making
   5 3d drawings with LaTeX and the PSTricks or TikZ package.
   6
   7 Sketch is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 Sketch is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with Sketch; see the file COPYING.txt.  If not, see
  19 http://www.gnu.org/copyleft */
  20
  21 #ifndef __GEOMETRY_H
  22 #define __GEOMETRY_H
  23
  24 // ---- memory -----------------------------------------------------------------
  25
  26 #include <float.h>              // floating point definitions
  27 #include "dynarray.h"           // dynamic arrays
  28
  29 // bit N
  30 #define bit(N)  (1u << (N))
  31
  32 // size of a static or auto declared array
  33 #define ARRAY_SIZE(A) (sizeof (A) / sizeof (A)[0])
  34
  35 // checking memory allocators
  36 void *safe_malloc (unsigned size);
  37 void *safe_realloc (void *p, unsigned size);
  38 char *safe_strdup (char *str);
  39 void safe_free (void *p);
  40 #ifdef _DEBUG
  41 #define malloc(N)    __call_safe_malloc_instead()
  42 #define realloc(P,N) __call_safe_alloc_instead()
  43 #define strdup(S)    __call_safe_alloc_instead()
  44 #define free(P)      __call_safe_free_instead()
  45 #endif
  46
  47 // ---- numerics ---------------------------------------------------------------
  48
  49 // float declarations to ease compilation
  50 // with either single or double precision
  51 typedef unsigned int SIZE, INDEX;
  52 typedef double FLOAT;
  53
  54 #define FLOAT_SCAN_FMT "%lf"
  55 #define FLOAT_EPS (8*DBL_EPSILON)
  56 #define FLOAT_MIN FLT_MIN
  57 #define FLOAT_MAX FLT_MAX
  58
  59 #ifdef _MSC_VER
  60 // kill loss of precision warnings for case where FLOAT is float
  61 #pragma warning(disable:4244 4305)
  62 #endif
  63
  64 #define PI ((FLOAT)3.1415926535897932384626433832795028841971693993751)
  65
  66 // Max and min operators
  67 FLOAT max_float (FLOAT x, FLOAT y);
  68 FLOAT min_float (FLOAT x, FLOAT y);
  69
  70 // ---- points -----------------------------------------------------------------
  71
  72 // indices
  73 #define X 0
  74 #define Y 1
  75 #define Z 2
  76 #define W 3
  77
  78 // points
  79 typedef FLOAT POINT_2D[2], POINT_3D[3];
  80 void copy_pt_2d (POINT_2D r, POINT_2D s);
  81 void copy_pt_3d (POINT_3D r, POINT_3D s);
  82 void find_pt_3d_from_2d (POINT_3D r, POINT_2D pt);
  83
  84 // ---- polylines --------------------------------------------------------------
  85
  86 // polylines are just dynamic arrays of points
  87
  88 typedef struct polyline_2d_t
  89 {
  90   DYNAMIC_2D_ARRAY_FIELDS (POINT_2D, v, n_vertices);
  91   struct polyline_2d_t *next;
  92 }
  93 POLYLINE_2D;
  94
  95 DECLARE_DYNAMIC_2D_ARRAY_PROTOS (POLYLINE_2D, POINT_2D, FLOAT, polyline_2d,
  96                                  v, n_vertices)
  97      typedef struct polyline_3d_t
  98      {
  99        DYNAMIC_2D_ARRAY_FIELDS (POINT_3D, v, n_vertices);
 100        struct polyline_3d_t *next;
 101      }
 102 POLYLINE_3D;
 103
 104 DECLARE_DYNAMIC_2D_ARRAY_PROTOS (POLYLINE_3D, POINT_3D, FLOAT, polyline_3d,
 105                                  v, n_vertices)
 106 // ---- polygons ---------------------------------------------------------------
 107 // polygons are just a dynamic arrays of points; chains represent complex polygons
 108      typedef struct polygon_2d_t
 109      {
 110        DYNAMIC_2D_ARRAY_FIELDS (POINT_2D, v, n_sides);
 111        struct polygon_2d_t *next;
 112      }
 113 POLYGON_2D;
 114
 115 DECLARE_DYNAMIC_2D_ARRAY_PROTOS (POLYGON_2D, POINT_2D, FLOAT, polygon_2d, v,
 116                                  n_sides)
 117      typedef struct polygon_3d_t
 118      {
 119        DYNAMIC_2D_ARRAY_FIELDS (POINT_3D, v, n_sides);
 120        struct polygon_3d_t *next;
 121      }
 122 POLYGON_3D;
 123
 124 DECLARE_DYNAMIC_2D_ARRAY_PROTOS (POLYGON_3D, POINT_3D, FLOAT, polygon_3d, v,
 125                                  n_sides)
 126 // ---- vectors ----------------------------------------------------------------
 127      typedef FLOAT *VECTOR;
 128
 129 // vectors of dynamic length
 130      void init_vec (VECTOR * v);
 131      void clear_vec (VECTOR * v);
 132      void setup_vec (VECTOR * v, SIZE n);
 133      void init_and_setup_vec (VECTOR * v, SIZE n);
 134      void zero_vec (VECTOR r, SIZE n);
 135      void copy_vec (VECTOR r, VECTOR v, SIZE n);
 136
 137 // vectors of useful static length.
 138      typedef FLOAT VECTOR_2D[2], VECTOR_3D[3], VECTOR_4D[4];
 139
 140      FLOAT length_vec_2d (VECTOR_2D v);
 141      FLOAT length_vec_3d (VECTOR_3D v);
 142      FLOAT dist_2d (POINT_2D p1, POINT_2D p2);
 143      FLOAT dist_3d (POINT_3D p1, POINT_3D p2);
 144      FLOAT length_vec_2d_sqr (VECTOR_2D v);
 145      FLOAT length_vec_3d_sqr (VECTOR_3D v);
 146      FLOAT dist_2d_sqr (POINT_2D p1, POINT_2D p2);
 147      FLOAT dist_3d_sqr (POINT_3D p1, POINT_3D p2);
 148      void zero_vec_2d (VECTOR_2D v);
 149      void zero_vec_3d (VECTOR_3D v);
 150      void negate_vec_2d (VECTOR_2D r, VECTOR_2D v);
 151      void negate_vec_3d (VECTOR_3D r, VECTOR_3D v);
 152      void copy_vec_2d (VECTOR_2D r, VECTOR_2D s);
 153      void copy_vec_3d (VECTOR_3D r, VECTOR_3D s);
 154      void scale_vec_2d (VECTOR_2D r, VECTOR_2D v, FLOAT s);
 155      void scale_vec_3d (VECTOR_3D r, VECTOR_3D v, FLOAT s);
 156      int find_unit_vec_2d (VECTOR_2D r, VECTOR_2D v);
 157      int find_unit_vec_3d (VECTOR_3D r, VECTOR_3D v);
 158      void add_vecs_2d (VECTOR_2D r, VECTOR_2D a, VECTOR_2D b);
 159      void add_vecs_3d (VECTOR_3D r, VECTOR_3D a, VECTOR_3D b);
 160      void sub_vecs_2d (VECTOR_2D r, VECTOR_2D a, VECTOR_2D b);
 161      void sub_vecs_3d (VECTOR_3D r, VECTOR_3D a, VECTOR_3D b);
 162      void add_vec_to_pt_2d (POINT_2D r, POINT_2D pt, VECTOR_2D v);
 163      void add_vec_to_pt_3d (POINT_3D r, POINT_3D pt, VECTOR_3D v);
 164      void add_scaled_vec_to_pt_2d (POINT_2D r, POINT_2D pt, VECTOR_2D v,
 165                                    FLOAT s);
 166      void add_scaled_vec_to_pt_3d (POINT_3D r, POINT_3D pt, VECTOR_3D v,
 167                                    FLOAT s);
 168      void sub_pts_2d (VECTOR_2D r, POINT_2D a, POINT_2D b);
 169      void sub_pts_3d (VECTOR_3D r, POINT_3D a, POINT_3D b);
 170      void fold_min_pt_2d (POINT_2D min, POINT_2D new_pt);
 171      void fold_min_pt_3d (POINT_3D min, POINT_3D new_pt);
 172      void fold_max_pt_2d (POINT_2D max, POINT_2D new_pt);
 173      void fold_max_pt_3d (POINT_3D max, POINT_3D new_pt);
 174
 175      FLOAT dot_2d (VECTOR_2D a, VECTOR_2D b);
 176      FLOAT dot_3d (VECTOR_3D a, VECTOR_3D b);
 177      void cross (VECTOR_3D r, VECTOR_3D a, VECTOR_3D b);
 178
 179 // linear interpolation operators
 180      void lerp_2d (POINT_2D r, FLOAT t, POINT_2D p1, POINT_2D p2);
 181      void lerp_3d (POINT_3D r, FLOAT t, POINT_3D p1, POINT_3D p2);
 182
 183 // find parameters of intersection point of two line segments
 184      int line_intersect_2d (POINT_2D a, POINT_2D b, POINT_2D c, POINT_2D d,
 185                             FLOAT eps, FLOAT * t_ab, FLOAT * t_cd);
 186
 187 // ---- planes -----------------------------------------------------------------
 188      typedef struct plane_t
 189      {
 190        VECTOR_3D n;
 191        POINT_3D p;
 192        FLOAT c;
 193      }
 194 PLANE;
 195
 196 // return description of the plane of a polygon using Newell's method
 197      void find_polygon_plane (PLANE * plane, POLYGON_3D * polygon);
 198
 199 #define S_IN      (1)
 200 #define S_ON      (2)
 201 #define S_OUT     (4)
 202 #define S_IN_ON   (S_ON | 8)
 203 #define S_OUT_ON  (S_ON | 16)
 204 #define S_SPLIT   (32)
 205
 206 // #define PLANE_HALF_THICKNESS  (10.0 * FLOAT_EPS)
 207 #define PLANE_HALF_THICKNESS  (.001/2)
 208
 209 // given a plane of thickness 2 * half_thickness, return:
 210 //   S_IN or S_OUT if the point is resp. inside or outside the thickness of the plane
 211 //   S_IN_ON or S_OUT_ON if the point is within half_thickness of the plane on the resp. side
 212 //   S_ON if the point is precisely on the plane; no IN or OUT determination can be made
 213      int pt_side_of_plane (PLANE * plane, POINT_3D p);
 214
 215 // given a polygon and a plane, return:
 216 //   S_IN if all the verices are IN or ON the thickened plane
 217 //   S_OUT if all the verices are OUTside or ON the thickened plane
 218 //   S_ON if all vertice are ON the thickened plane
 219 //   S_SPLIT otherwise
 220      int polygon_side_of_plane (POLYGON_3D * polygon, PLANE * plane);
 221
 222 // given a polyline and a plane, return:
 223 //   S_IN if all segments of the line are fully INside the thickened plane
 224 //   S_OUT if all segments of the line are fully OUTside the thickened plane
 225 //   S_ON if all vertice are ON the thickened plane
 226 //   S_SPLIT otherwise
 227      int polyline_side_of_plane (POLYLINE_3D * polyline, PLANE * plane);
 228
 229 // ---- boxes ------------------------------------------------------------------
 230
 231      typedef struct box_2d_t
 232      {
 233        POINT_2D min, max;
 234      }
 235 BOX_2D;
 236
 237      typedef struct box_3d_t
 238      {
 239        POINT_3D min, max;
 240      }
 241 BOX_3D;
 242
 243      void init_box_2d (BOX_2D * b);
 244      void init_box_3d (BOX_3D * b);
 245      void fold_min_max_pt_2d (BOX_2D * b, POINT_2D p);
 246      void fold_min_max_pt_3d (BOX_3D * b, POINT_3D p);
 247      void fold_min_max_polygon_2d (BOX_2D * b, POLYGON_2D * polygon);
 248      void fold_min_max_polygon_3d (BOX_3D * b, POLYGON_3D * polygon);
 249      void fold_min_max_polyline_2d (BOX_2D * b, POLYLINE_2D * polyline);
 250      void fold_min_max_polyline_3d (BOX_3D * b, POLYLINE_3D * polyline);
 251      void copy_box_2d (BOX_2D * r, BOX_2D * s);
 252      void copy_box_3d (BOX_3D * r, BOX_3D * s);
 253      int boxes_2d_intersect_p (BOX_2D * a, BOX_2D * b);
 254      int boxes_3d_intersect_p (BOX_2D * a, BOX_2D * b);
 255
 256 // ---- transformations --------------------------------------------------------
 257
 258 // homogeneous transform stored in column major order
 259      typedef FLOAT TRANSFORM[16];
 260
 261 // for initializations of identity transforms
 262 #define IDENT_TRANSFORM  \
 263 { 1.0, 0.0, 0.0, 0.0, \
 264   0.0, 1.0, 0.0, 0.0, \
 265   0.0, 0.0, 1.0, 0.0, \
 266   0.0, 0.0, 0.0, 1.0 }
 267
 268 // ---- global contstants ------------------------------------------------------
 269
 270      extern TRANSFORM identity;
 271      extern POINT_2D origin_2d;
 272      extern POINT_3D origin_3d;
 273      extern VECTOR_2D I_2d;
 274      extern VECTOR_2D J_2d;
 275      extern VECTOR_3D I_3d;
 276      extern VECTOR_3D J_3d;
 277      extern VECTOR_3D K_3d;
 278
 279 // row-column tranform indexing matches OpenGL convention: column major
 280 #define IT(I,J) (4 * ((J) - 1) + ((I) - 1))
 281
 282 // copy source to result transform
 283      void copy_transform (TRANSFORM r, TRANSFORM s);
 284
 285 // set the result transform to the identity
 286      void set_ident (TRANSFORM r);
 287
 288 // create a rotation transform thru angle theta about axis u (must be unit vec)
 289      void set_angle_axis_rot (TRANSFORM r, FLOAT theta, VECTOR_3D u);
 290
 291 // create a rotation transform thru angle theta
 292 // u is optional axis which need not be a unit vector (default is [0,0,1])
 293 // p is optional center of rotation (default is (0,0,0))
 294      void set_angle_axis_rot_about_point (TRANSFORM r, FLOAT theta,
 295                                           POINT_3D p, VECTOR_3D u);
 296
 297 // create a scale transform
 298      void set_scale (TRANSFORM r, FLOAT sx, FLOAT sy, FLOAT sz);
 299
 300 // create a translation transform
 301      void set_translation (TRANSFORM r, FLOAT dx, FLOAT dy, FLOAT dz);
 302
 303 // create a true perspective projection (depth = p for all projected points)
 304      void set_perspective_projection (TRANSFORM r, FLOAT p);
 305
 306 // create a perspective transformation (depth is a pseudodepth)
 307      void set_perspective_transform (TRANSFORM r, FLOAT p);
 308
 309 // create a true parallel projection (depth = 0 for all projected points)
 310      void set_parallel_projection (TRANSFORM r);
 311
 312 // create an OpenGL-like view transformation matrix
 313      void set_view_transform (TRANSFORM r, POINT_3D eye, VECTOR_3D vd,
 314                               VECTOR_3D up);
 315      void set_view_transform_with_look_at (TRANSFORM r, POINT_3D eye,
 316                                            POINT_3D look_at, VECTOR_3D up);
 317
 318 // invert a given transform m; return its determinant; we give up if the
 319 // determinant is too small
 320      void invert (TRANSFORM r, FLOAT * det_rtn, TRANSFORM m, FLOAT min_det);
 321
 322 // compose two transforms, but result cannot be the same as either operand
 323      void compose_unsafe (TRANSFORM r, TRANSFORM a, TRANSFORM b);
 324
 325 // same as above, but safe to use either operand to hold result.
 326      void compose (TRANSFORM r, TRANSFORM a, TRANSFORM b);
 327
 328      void transform_pt_3d (POINT_3D r, TRANSFORM m, POINT_3D p);
 329      void transform_vec_3d (VECTOR_3D r, TRANSFORM m, VECTOR_3D p);
 330
 331 // ---- quaternions ------------------------------------------------------------
 332
 333      typedef FLOAT QUATERNION[4];
 334
 335 // for initializations of identity quaternions
 336 #define IDENT_QUAT { 0.0, 0.0, 0.0, 1.0 }
 337
 338      void set_ident_quat (QUATERNION q);
 339      void set_angle_axis_quat (QUATERNION q, FLOAT theta, VECTOR_3D axis);
 340      void find_rot_from_quat (TRANSFORM r, QUATERNION q);
 341      void find_quat_from_rot (QUATERNION q, TRANSFORM r);
 342      void mult_quat (QUATERNION r, QUATERNION a, QUATERNION b);
 343
 344 // clear any storage for vertices in a polygon; after this,
 345 // its state is the same as after init_polygon_2d()
 346      void clear_polygon_2d (POLYGON_2D * poly);
 347
 348 // compute minkowski difference B - A with distinguished point p
 349      void make_cso_polygon_2d (POLYGON_2D * r, POLYGON_2D * a, POINT_2D p,
 350                                POLYGON_2D * b);
 351
 352 // checks to see if p is left of or on all the edges of polygon a.
 353      int point_inside_convex_polygon_2d_p (POINT_2D p, POLYGON_2D * a);
 354
 355 // checks to see if p is no more than eps right of all the edges of polygon a.
 356      int point_near_convex_polygon_2d_p (POINT_2D p, POLYGON_2D * a,
 357                                          FLOAT eps);
 358
 359 #endif