--- /dev/null
+/* Copyright (C) 2021 Harry Godden (hgn)
+ *
+ * Straightforward implementations for:
+ * Vector 2,3,4
+ * Simple Matrices in 3x3 and 4x3
+ * Plane maths
+ * Other useful geometric functions
+ */
+
+#define CXR_INLINE static inline
+#define CXR_PIf 3.14159265358979323846264338327950288f
+
+CXR_INLINE double cxr_minf( double a, double b )
+{
+ return a < b? a: b;
+}
+
+CXR_INLINE double cxr_maxf( double a, double b )
+{
+ return a > b? a: b;
+}
+
+CXR_INLINE int cxr_min( int a, int b )
+{
+ return a < b? a: b;
+}
+
+CXR_INLINE int cxr_max( int a, int b )
+{
+ return a > b? a: b;
+}
+
+CXR_INLINE double cxr_clampf( double v, double a, double b )
+{
+ return cxr_minf( b, cxr_maxf( a, v ) );
+}
+
+CXR_INLINE double cxr_rad( double deg )
+{
+ return deg * CXR_PIf / 180.0f;
+}
+
+/*
+ * Vector 2 Functions
+ */
+CXR_INLINE void v2_zero( v2f a )
+{
+ a[0] = 0.0; a[1] = 0.0;
+}
+
+CXR_INLINE void v2_fill( v2f a, double v )
+{
+ a[0] = v; a[1] = v;
+}
+
+CXR_INLINE void v2_copy( v2f a, v2f b )
+{
+ b[0] = a[0]; b[1] = a[1];
+}
+
+CXR_INLINE void v2_minv( v2f a, v2f b, v2f dest )
+{
+ dest[0] = cxr_minf(a[0], b[0]);
+ dest[1] = cxr_minf(a[1], b[1]);
+}
+
+CXR_INLINE void v2_maxv( v2f a, v2f b, v2f dest )
+{
+ dest[0] = cxr_maxf(a[0], b[0]);
+ dest[1] = cxr_maxf(a[1], b[1]);
+}
+
+CXR_INLINE void v2_sub( v2f a, v2f b, v2f d )
+{
+ d[0] = a[0]-b[0]; d[1] = a[1]-b[1];
+}
+
+CXR_INLINE double v2_cross( v2f a, v2f b )
+{
+ return a[0] * b[1] - a[1] * b[0];
+}
+
+CXR_INLINE void v2_add( v2f a, v2f b, v2f d )
+{
+ d[0] = a[0]+b[0]; d[1] = a[1]+b[1];
+}
+
+CXR_INLINE void v2_muls( v2f a, double s, v2f d )
+{
+ d[0] = a[0]*s; d[1] = a[1]*s;
+}
+
+CXR_INLINE void v2_mul( v2f a, v2f b, v2f d )
+{
+ d[0] = a[0]*b[0]; d[1] = a[1]*b[1];
+}
+
+CXR_INLINE void v2_muladds( v2f a, v2f b, double s, v2f d )
+{
+ d[0] = a[0]+b[0]*s; d[1] = a[1]+b[1]*s;
+}
+
+CXR_INLINE double v2_dot( v2f a, v2f b )
+{
+ return a[0] * b[0] + a[1] * b[1];
+}
+
+CXR_INLINE void v2_div( v2f a, v2f b, v2f d )
+{
+ d[0] = a[0]/b[0]; d[1] = a[1]/b[1];
+}
+
+CXR_INLINE double v2_length2( v2f a )
+{
+ return v2_dot( a, a );
+}
+
+CXR_INLINE double v2_length( v2f a )
+{
+ return sqrt( v2_length2( a ) );
+}
+
+CXR_INLINE double v2_dist2( v2f a, v2f b )
+{
+ v2f delta;
+ v2_sub( a, b, delta );
+ return v2_length2( delta );
+}
+
+CXR_INLINE double v2_dist( v2f a, v2f b )
+{
+ return sqrt( v2_dist2( a, b ) );
+}
+
+CXR_INLINE void v2_normalize( v2f a )
+{
+ v2_muls( a, 1.0 / v2_length( a ), a );
+}
+
+/*
+ * Vector 3 Functions
+ */
+
+CXR_INLINE void v3_zero( v3f a )
+{
+ a[0] = 0.f; a[1] = 0.f; a[2] = 0.f;
+}
+
+CXR_INLINE void v3_copy( v3f a, v3f b )
+{
+ b[0] = a[0]; b[1] = a[1]; b[2] = a[2];
+}
+
+CXR_INLINE void v3_add( v3f a, v3f b, v3f d )
+{
+ d[0] = a[0]+b[0]; d[1] = a[1]+b[1]; d[2] = a[2]+b[2];
+}
+
+CXR_INLINE void v3_sub( v3f a, v3f b, v3f d )
+{
+ d[0] = a[0]-b[0]; d[1] = a[1]-b[1]; d[2] = a[2]-b[2];
+}
+
+CXR_INLINE void v3_mul( v3f a, v3f b, v3f d )
+{
+ d[0] = a[0]*b[0]; d[1] = a[1]*b[1]; d[2] = a[2]*b[2];
+}
+
+CXR_INLINE void v3_div( v3f a, v3f b, v3f d )
+{
+ d[0] = a[0]/b[0]; d[1] = a[1]/b[1]; d[2] = a[2]/b[2];
+}
+
+CXR_INLINE void v3_muls( v3f a, double s, v3f d )
+{
+ d[0] = a[0]*s; d[1] = a[1]*s; d[2] = a[2]*s;
+}
+
+CXR_INLINE void v3_divs( v3f a, double s, v3f d )
+{
+ d[0] = a[0]/s; d[1] = a[1]/s; d[2] = a[2]/s;
+}
+
+CXR_INLINE void v3_muladds( v3f a, v3f b, double s, v3f d )
+{
+ d[0] = a[0]+b[0]*s; d[1] = a[1]+b[1]*s; d[2] = a[2]+b[2]*s;
+}
+
+CXR_INLINE double v3_dot( v3f a, v3f b )
+{
+ return a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
+}
+
+CXR_INLINE void v3_cross( v3f a, v3f b, v3f d )
+{
+ d[0] = a[1] * b[2] - a[2] * b[1];
+ d[1] = a[2] * b[0] - a[0] * b[2];
+ d[2] = a[0] * b[1] - a[1] * b[0];
+}
+
+CXR_INLINE double v3_length2( v3f a )
+{
+ return v3_dot( a, a );
+}
+
+CXR_INLINE double v3_length( v3f a )
+{
+ return sqrt( v3_length2( a ) );
+}
+
+CXR_INLINE double v3_dist2( v3f a, v3f b )
+{
+ v3f delta;
+ v3_sub( a, b, delta );
+ return v3_length2( delta );
+}
+
+CXR_INLINE double v3_dist( v3f a, v3f b )
+{
+ return sqrt( v3_dist2( a, b ) );
+}
+
+CXR_INLINE void v3_normalize( v3f a )
+{
+ v3_muls( a, 1.0 / v3_length( a ), a );
+}
+
+CXR_INLINE void v3_negate( v3f a, v3f dest )
+{
+ v3_muls( a, -1.0, dest );
+}
+
+CXR_INLINE double cxr_lerpf( double a, double b, double t )
+{
+ return a + t*(b-a);
+}
+
+CXR_INLINE void v3_lerp( v3f a, v3f b, double t, v3f d )
+{
+ d[0] = a[0] + t*(b[0]-a[0]);
+ d[1] = a[1] + t*(b[1]-a[1]);
+ d[2] = a[2] + t*(b[2]-a[2]);
+}
+
+CXR_INLINE void v3_minv( v3f a, v3f b, v3f dest )
+{
+ dest[0] = cxr_minf(a[0], b[0]);
+ dest[1] = cxr_minf(a[1], b[1]);
+ dest[2] = cxr_minf(a[2], b[2]);
+}
+
+CXR_INLINE void v3_maxv( v3f a, v3f b, v3f dest )
+{
+ dest[0] = cxr_maxf(a[0], b[0]);
+ dest[1] = cxr_maxf(a[1], b[1]);
+ dest[2] = cxr_maxf(a[2], b[2]);
+}
+
+CXR_INLINE double v3_minf( v3f a )
+{
+ return cxr_minf( cxr_minf( a[0], a[1] ), a[2] );
+}
+
+CXR_INLINE double v3_maxf( v3f a )
+{
+ return cxr_maxf( cxr_maxf( a[0], a[1] ), a[2] );
+}
+
+CXR_INLINE void v3_fill( v3f a, double v )
+{
+ a[0] = v;
+ a[1] = v;
+ a[2] = v;
+}
+
+/*
+ * Vector 4 Functions
+ */
+CXR_INLINE void v4_copy( v4f a, v4f b )
+{
+ b[0] = a[0]; b[1] = a[1]; b[2] = a[2]; b[3] = a[3];
+}
+
+CXR_INLINE void v4_zero( v4f a )
+{
+ a[0] = 0.f; a[1] = 0.f; a[2] = 0.f; a[3] = 0.f;
+}
+
+CXR_INLINE void v4_muls( v4f a, double s, v4f d )
+{
+ d[0] = a[0]*s; d[1] = a[1]*s; d[2] = a[2]*s; d[3] = a[3]*s;
+}
+
+/*
+ * Matrix 3x3
+ */
+
+CXR_INLINE void m3x3_inv_transpose( m3x3f src, m3x3f dest )
+{
+ double a = src[0][0], b = src[0][1], c = src[0][2],
+ d = src[1][0], e = src[1][1], f = src[1][2],
+ g = src[2][0], h = src[2][1], i = src[2][2];
+
+ double det = 1.f /
+ (+a*(e*i-h*f)
+ -b*(d*i-f*g)
+ +c*(d*h-e*g));
+
+ dest[0][0] = (e*i-h*f)*det;
+ dest[1][0] = -(b*i-c*h)*det;
+ dest[2][0] = (b*f-c*e)*det;
+ dest[0][1] = -(d*i-f*g)*det;
+ dest[1][1] = (a*i-c*g)*det;
+ dest[2][1] = -(a*f-d*c)*det;
+ dest[0][2] = (d*h-g*e)*det;
+ dest[1][2] = -(a*h-g*b)*det;
+ dest[2][2] = (a*e-d*b)*det;
+}
+
+CXR_INLINE void m3x3_mulv( m3x3f m, v3f v, v3f d )
+{
+ v3f res;
+
+ res[0] = m[0][0]*v[0] + m[1][0]*v[1] + m[2][0]*v[2];
+ res[1] = m[0][1]*v[0] + m[1][1]*v[1] + m[2][1]*v[2];
+ res[2] = m[0][2]*v[0] + m[1][2]*v[1] + m[2][2]*v[2];
+
+ v3_copy( res, d );
+}
+
+/*
+ * Matrix 4x3
+ */
+
+#define M4X3_IDENTITY {{1.0f, 0.0f, 0.0f, },\
+ { 0.0f, 1.0f, 0.0f, },\
+ { 0.0f, 0.0f, 1.0f, },\
+ { 0.0f, 0.0f, 0.0f }}
+
+CXR_INLINE void m4x3_to_3x3( m4x3f a, m3x3f b )
+{
+ v3_copy( a[0], b[0] );
+ v3_copy( a[1], b[1] );
+ v3_copy( a[2], b[2] );
+}
+
+CXR_INLINE void m4x3_copy( m4x3f a, m4x3f b )
+{
+ v3_copy( a[0], b[0] );
+ v3_copy( a[1], b[1] );
+ v3_copy( a[2], b[2] );
+ v3_copy( a[3], b[3] );
+}
+
+CXR_INLINE void m4x3_identity( m4x3f a )
+{
+ m4x3f id = M4X3_IDENTITY;
+ m4x3_copy( id, a );
+}
+
+CXR_INLINE void m4x3_mul( m4x3f a, m4x3f b, m4x3f d )
+{
+ double
+ a00 = a[0][0], a01 = a[0][1], a02 = a[0][2],
+ a10 = a[1][0], a11 = a[1][1], a12 = a[1][2],
+ a20 = a[2][0], a21 = a[2][1], a22 = a[2][2],
+ a30 = a[3][0], a31 = a[3][1], a32 = a[3][2],
+ b00 = b[0][0], b01 = b[0][1], b02 = b[0][2],
+ b10 = b[1][0], b11 = b[1][1], b12 = b[1][2],
+ b20 = b[2][0], b21 = b[2][1], b22 = b[2][2],
+ b30 = b[3][0], b31 = b[3][1], b32 = b[3][2];
+
+ d[0][0] = a00*b00 + a10*b01 + a20*b02;
+ d[0][1] = a01*b00 + a11*b01 + a21*b02;
+ d[0][2] = a02*b00 + a12*b01 + a22*b02;
+ d[1][0] = a00*b10 + a10*b11 + a20*b12;
+ d[1][1] = a01*b10 + a11*b11 + a21*b12;
+ d[1][2] = a02*b10 + a12*b11 + a22*b12;
+ d[2][0] = a00*b20 + a10*b21 + a20*b22;
+ d[2][1] = a01*b20 + a11*b21 + a21*b22;
+ d[2][2] = a02*b20 + a12*b21 + a22*b22;
+ d[3][0] = a00*b30 + a10*b31 + a20*b32 + a30;
+ d[3][1] = a01*b30 + a11*b31 + a21*b32 + a31;
+ d[3][2] = a02*b30 + a12*b31 + a22*b32 + a32;
+}
+
+CXR_INLINE void m4x3_mulv( m4x3f m, v3f v, v3f d )
+{
+ v3f res;
+
+ res[0] = m[0][0]*v[0] + m[1][0]*v[1] + m[2][0]*v[2] + m[3][0];
+ res[1] = m[0][1]*v[0] + m[1][1]*v[1] + m[2][1]*v[2] + m[3][1];
+ res[2] = m[0][2]*v[0] + m[1][2]*v[1] + m[2][2]*v[2] + m[3][2];
+
+ v3_copy( res, d );
+}
+
+/*
+ * Affine transformations
+ */
+CXR_INLINE void m4x3_translate( m4x3f m, v3f v )
+{
+ v3_muladds( m[3], m[0], v[0], m[3] );
+ v3_muladds( m[3], m[1], v[1], m[3] );
+ v3_muladds( m[3], m[2], v[2], m[3] );
+}
+
+CXR_INLINE void m4x3_scale( m4x3f m, double s )
+{
+ v3_muls( m[0], s, m[0] );
+ v3_muls( m[1], s, m[1] );
+ v3_muls( m[2], s, m[2] );
+}
+
+CXR_INLINE void m4x3_rotate_x( m4x3f m, double angle )
+{
+ m4x3f t = M4X3_IDENTITY;
+ double c, s;
+
+ c = cosf( angle );
+ s = sinf( angle );
+
+ t[1][1] = c;
+ t[1][2] = s;
+ t[2][1] = -s;
+ t[2][2] = c;
+
+ m4x3_mul( m, t, m );
+}
+
+CXR_INLINE void m4x3_rotate_y( m4x3f m, double angle )
+{
+ m4x3f t = M4X3_IDENTITY;
+ double c, s;
+
+ c = cosf( angle );
+ s = sinf( angle );
+
+ t[0][0] = c;
+ t[0][2] = -s;
+ t[2][0] = s;
+ t[2][2] = c;
+
+ m4x3_mul( m, t, m );
+}
+
+CXR_INLINE void m4x3_rotate_z( m4x3f m, double angle )
+{
+ m4x3f t = M4X3_IDENTITY;
+ double c, s;
+
+ c = cosf( angle );
+ s = sinf( angle );
+
+ t[0][0] = c;
+ t[0][1] = s;
+ t[1][0] = -s;
+ t[1][1] = c;
+
+ m4x3_mul( m, t, m );
+}
+
+CXR_INLINE void m4x3_expand_aabb_point( m4x3f m, boxf box, v3f point )
+{
+ v3f v;
+ m4x3_mulv( m, point, v );
+
+ v3_minv( box[0], v, box[0] );
+ v3_maxv( box[1], v, box[1] );
+}
+
+CXR_INLINE void box_concat( boxf a, boxf b )
+{
+ v3_minv( a[0], b[0], a[0] );
+ v3_maxv( a[1], b[1], a[1] );
+}
+
+CXR_INLINE void box_copy( boxf a, boxf b )
+{
+ v3_copy( a[0], b[0] );
+ v3_copy( a[1], b[1] );
+}
+
+CXR_INLINE void m4x3_transform_aabb( m4x3f m, boxf box )
+{
+ v3f a; v3f b;
+
+ v3_copy( box[0], a );
+ v3_copy( box[1], b );
+ v3_fill( box[0], INFINITY );
+ v3_fill( box[1], -INFINITY );
+
+ m4x3_expand_aabb_point( m, box, a );
+ m4x3_expand_aabb_point( m, box, (v3f){ a[0], b[1], a[2] } );
+ m4x3_expand_aabb_point( m, box, (v3f){ b[0], a[1], a[2] } );
+ m4x3_expand_aabb_point( m, box, (v3f){ b[0], b[1], a[2] } );
+ m4x3_expand_aabb_point( m, box, b );
+ m4x3_expand_aabb_point( m, box, (v3f){ a[0], b[1], b[2] } );
+ m4x3_expand_aabb_point( m, box, (v3f){ b[0], a[1], b[2] } );
+ m4x3_expand_aabb_point( m, box, (v3f){ b[0], b[1], b[2] } );
+}
+
+CXR_INLINE void tri_normal( v3f p0, v3f p1, v3f p2, v3f normal )
+{
+ v3f v0, v1;
+ v3_sub( p1, p0, v0 );
+ v3_sub( p2, p0, v1 );
+ v3_cross( v0, v1, normal );
+ v3_normalize( normal );
+}
+
+CXR_INLINE void tri_to_plane( v3f a, v3f b, v3f c, v4f plane )
+{
+ tri_normal( a,b,c, plane );
+ plane[3] = v3_dot( plane, a );
+}
+
+CXR_INLINE int plane_intersect( v4f a, v4f b, v4f c, v3f p )
+{
+ double const epsilon = 0.001;
+
+ v3f x, bc, ca, ab;
+ double d;
+
+ v3_cross( a, b, x );
+ d = v3_dot( x, c );
+
+ if( d < epsilon && d > -epsilon ) return 0;
+
+ v3_cross(b,c,bc);
+ v3_cross(c,a,ca);
+ v3_cross(a,b,ab);
+
+ v3_muls( bc, -a[3], p );
+ v3_muladds( p, ca, -b[3], p );
+ v3_muladds( p, ab, -c[3], p );
+
+ v3_negate( p, p );
+ v3_divs( p, d, p );
+
+ return 1;
+}
+
+CXR_INLINE void normal_to_plane( v3f normal, v3f p, v4f plane )
+{
+ v3_copy( normal, plane );
+ plane[3] = v3_dot( normal, p );
+}
+
+CXR_INLINE double plane_polarity( v4f p, v3f a )
+{
+ return
+ v3_dot( a, p )
+ - (p[0]*p[3]*p[0] + p[1]*p[3]*p[1] + p[2]*p[3]*p[2]);
+}
+
+CXR_INLINE void plane_project_point( v4f plane, v3f a, v3f d )
+{
+ v3f ref, delta;
+ v3_muls( plane, plane[3], ref );
+
+ v3_sub( a, ref, delta );
+ v3_muladds( a, plane, -v3_dot(delta,plane), d );
+}
+
+CXR_INLINE double line_line_dist( v3f pa0, v3f pa1, v3f pb0, v3f pb1 )
+{
+ v3f va, vb, n, delta;
+ v3_sub( pa1, pa0, va );
+ v3_sub( pb1, pb0, vb );
+
+ v3_cross( va, vb, n );
+ v3_normalize( n );
+
+ v3_sub( pb0, pa0, delta );
+
+ return fabs( v3_dot( n, delta ) );
+}
+
+CXR_INLINE double segment_segment_dist( v3f a0, v3f a1, v3f b0, v3f b1,
+ v3f a, v3f b )
+{
+ v3f r,u,v;
+ v3_sub( b0, a0, r );
+ v3_sub( a1, a0, u );
+ v3_sub( b1, b0, v );
+
+ double ru = v3_dot( r,u ),
+ rv = v3_dot( r,v ),
+ uu = v3_dot( u,u ),
+ uv = v3_dot( u,v ),
+ vv = v3_dot( v,v );
+
+ double det = uu*vv - uv*uv,
+ s,
+ t;
+
+ if( det < 1e-6 *uu*vv )
+ {
+ s = ru/uu;
+ t = 0.0;
+ }
+ else
+ {
+ s = (ru*vv - rv*uv)/det;
+ t = (ru*uv - rv*uu)/det;
+ }
+
+ s = cxr_clampf( s, 0.0, 1.0 );
+ t = cxr_clampf( t, 0.0, 1.0 );
+
+ double S = cxr_clampf((t*uv + ru)/uu, 0.0, 1.0),
+ T = cxr_clampf((s*uv - rv)/vv, 0.0, 1.0);
+
+ v3_muladds( a0, u, S, a );
+ v3_muladds( b0, v, T, b );
+
+ return v3_dist( a, b );
+}
projects / convexer.git / blobdiff