From: John Tsiombikas Date: Wed, 6 Dec 2017 04:43:16 +0000 (+0200) Subject: cleaned up and fleshed out geom.h/geom.cc and preparing to add bounding X-Git-Url: http://git.mutantstargoat.com/user/nuclear/?p=laserbrain_demo;a=commitdiff_plain;h=ca5d732eb2b76da1e01428193effeb205ae951e9 cleaned up and fleshed out geom.h/geom.cc and preparing to add bounding volumes to the scene nodes --- diff --git a/src/geom.cc b/src/geom.cc index 55cfed7..890d975 100644 --- a/src/geom.cc +++ b/src/geom.cc @@ -2,6 +2,16 @@ #include #include "geom.h" +#define SPHERE(ptr) ((Sphere*)ptr) +#define AABOX(ptr) ((AABox*)ptr) +#define BOX(ptr) ((Box*)ptr) +#define PLANE(ptr) ((Plane*)ptr) + +GeomObject::GeomObject() +{ + type = GOBJ_UNKNOWN; +} + GeomObject::~GeomObject() { } @@ -9,47 +19,17 @@ GeomObject::~GeomObject() Sphere::Sphere() { + type = GOBJ_SPHERE; radius = 1.0; } Sphere::Sphere(const Vec3 ¢, float radius) : center(cent) { + type = GOBJ_SPHERE; this->radius = radius; } -GeomObjectType Sphere::get_type() const -{ - return GOBJ_SPHERE; -} - -void Sphere::set_union(const GeomObject *obj1, const GeomObject *obj2) -{ - if(obj1->get_type() != GOBJ_SPHERE || obj2->get_type() != GOBJ_SPHERE) { - fprintf(stderr, "Sphere::set_union: arguments must be spheres"); - return; - } - const Sphere *sph1 = (const Sphere*)obj1; - const Sphere *sph2 = (const Sphere*)obj2; - - float dist = length(sph1->center - sph2->center); - float surf_dist = dist - (sph1->radius + sph2->radius); - float d1 = sph1->radius + surf_dist / 2.0; - float d2 = sph2->radius + surf_dist / 2.0; - float t = d1 / (d1 + d2); - - if(t < 0.0) t = 0.0; - if(t > 1.0) t = 1.0; - - center = sph1->center * t + sph2->center * (1.0 - t); - radius = std::max(dist * t + sph2->radius, dist * (1.0f - t) + sph1->radius); -} - -void Sphere::set_intersection(const GeomObject *obj1, const GeomObject *obj2) -{ - fprintf(stderr, "Sphere::intersection undefined\n"); -} - bool Sphere::intersect(const Ray &ray, HitPoint *hit) const { float a = dot(ray.dir, ray.dir); @@ -95,58 +75,32 @@ bool Sphere::contains(const Vec3 &pt) const float Sphere::distance(const Vec3 &v) const { + return std::max(length(v - center) - radius, 0.0f); +} + +float Sphere::signed_distance(const Vec3 &v) const +{ return length(v - center) - radius; } AABox::AABox() { + type = GOBJ_AABOX; } AABox::AABox(const Vec3 &vmin, const Vec3 &vmax) : min(vmin), max(vmax) { + type = GOBJ_AABOX; } -GeomObjectType AABox::get_type() const +Vec3 AABox::get_corner(int idx) const { - return GOBJ_AABOX; -} - -void AABox::set_union(const GeomObject *obj1, const GeomObject *obj2) -{ - if(obj1->get_type() != GOBJ_AABOX || obj2->get_type() != GOBJ_AABOX) { - fprintf(stderr, "AABox::set_union: arguments must be AABoxes too\n"); - return; - } - const AABox *box1 = (const AABox*)obj1; - const AABox *box2 = (const AABox*)obj2; - - min.x = std::min(box1->min.x, box2->min.x); - min.y = std::min(box1->min.y, box2->min.y); - min.z = std::min(box1->min.z, box2->min.z); - - max.x = std::max(box1->max.x, box2->max.x); - max.y = std::max(box1->max.y, box2->max.y); - max.z = std::max(box1->max.z, box2->max.z); -} - -void AABox::set_intersection(const GeomObject *obj1, const GeomObject *obj2) -{ - if(obj1->get_type() != GOBJ_AABOX || obj2->get_type() != GOBJ_AABOX) { - fprintf(stderr, "AABox::set_intersection: arguments must be AABoxes too\n"); - return; - } - const AABox *box1 = (const AABox*)obj1; - const AABox *box2 = (const AABox*)obj2; - - for(int i=0; i<3; i++) { - min[i] = std::max(box1->min[i], box2->min[i]); - max[i] = std::min(box1->max[i], box2->max[i]); - - if(max[i] < min[i]) { - max[i] = min[i]; - } - } + static const Vec3 v[] = { + Vec3(-0.5, -0.5, -0.5), Vec3(0.5, -0.5, -0.5), Vec3(0.5, -0.5, 0.5), Vec3(-0.5, -0.5, 0.5), + Vec3(-0.5, 0.5, -0.5), Vec3(0.5, 0.5, -0.5), Vec3(0.5, 0.5, 0.5), Vec3(-0.5, 0.5, 0.5) + }; + return v[idx] * Vec3(max - min); } bool AABox::intersect(const Ray &ray, HitPoint *hit) const @@ -225,6 +179,85 @@ float AABox::distance(const Vec3 &v) const return 0.0; // TODO } +float AABox::signed_distance(const Vec3 &v) const +{ + return 0.0; // TODO +} + +Box::Box() +{ +} + +Box::Box(const Vec3 &min, const Vec3 &max) + : AABox(min, max) +{ +} + +// XXX all this shit is completely untested +Box::Box(const Vec3 &pos, const Vec3 &vi, const Vec3 &vj, const Vec3 &vk) +{ + float ilen = length(vi); + float jlen = length(vj); + float klen = length(vk); + + min = Vec3(-ilen, -jlen, -klen); + max = Vec3(ilen, jlen, klen); + + float si = ilen == 0.0 ? 1.0 : 1.0 / ilen; + float sj = jlen == 0.0 ? 1.0 : 1.0 / jlen; + float sk = klen == 0.0 ? 1.0 : 1.0 / klen; + + xform = Mat4(vi * si, vj * sj, vk * sk); + xform.translate(pos); +} + +Box::Box(const Vec3 *varr, int vcount) +{ + calc_bounding_aabox(this, varr, vcount); +} + +Vec3 Box::get_corner(int idx) const +{ + static const Vec3 v[] = { + Vec3(-0.5, -0.5, -0.5), Vec3(0.5, -0.5, -0.5), Vec3(0.5, -0.5, 0.5), Vec3(-0.5, -0.5, 0.5), + Vec3(-0.5, 0.5, -0.5), Vec3(0.5, 0.5, -0.5), Vec3(0.5, 0.5, 0.5), Vec3(-0.5, 0.5, 0.5) + }; + + return xform * (v[idx] * Vec3(max - min)); +} + +bool Box::intersect(const Ray &ray, HitPoint *hit) const +{ + Mat4 inv_xform = inverse(xform); + Mat4 dir_inv_xform = inv_xform.upper3x3(); + Mat4 dir_xform = transpose(dir_inv_xform); + Ray local_ray = Ray(inv_xform * ray.origin, dir_inv_xform * ray.dir); + + bool res = AABox::intersect(local_ray, hit); + if(!res || !hit) return res; + + hit->pos = xform * hit->pos; + hit->normal = dir_xform * hit->normal; + hit->local_ray = local_ray; + hit->ray = ray; + return true; +} + +bool Box::contains(const Vec3 &pt) const +{ + // XXX is it faster to extract 6 planes and do dot products? sounds marginal + return AABox::contains(inverse(xform) * pt); +} + +float Box::distance(const Vec3 &v) const +{ + return 0.0f; // TODO +} + +float Box::signed_distance(const Vec3 &v) const +{ + return 0.0f; // TODO +} Plane::Plane() : normal(0.0, 1.0, 0.0) @@ -249,21 +282,6 @@ Plane::Plane(const Vec3 &normal, float dist) pt = this->normal * dist; } -GeomObjectType Plane::get_type() const -{ - return GOBJ_PLANE; -} - -void Plane::set_union(const GeomObject *obj1, const GeomObject *obj2) -{ - fprintf(stderr, "Plane::set_union undefined\n"); -} - -void Plane::set_intersection(const GeomObject *obj1, const GeomObject *obj2) -{ - fprintf(stderr, "Plane::set_intersection undefined\n"); -} - bool Plane::intersect(const Ray &ray, HitPoint *hit) const { float ndotdir = dot(normal, ray.dir); @@ -290,5 +308,275 @@ bool Plane::contains(const Vec3 &v) const float Plane::distance(const Vec3 &v) const { + return std::max(dot(v - pt, normal), 0.0f); +} + +float Plane::signed_distance(const Vec3 &v) const +{ return dot(v - pt, normal); } + + +Disc::Disc() +{ + radius = 1.0; +} + +Disc::Disc(const Vec3 &pt, const Vec3 &normal, float rad) + : Plane(pt, normal) +{ + radius = rad; +} + +Disc::Disc(const Vec3 &normal, float dist, float rad) + : Plane(normal, dist) +{ + radius = rad; +} + +bool Disc::intersect(const Ray &ray, HitPoint *hit) const +{ + HitPoint phit; + if(Plane::intersect(ray, &phit)) { + if(length_sq(phit.pos - pt) <= radius * radius) { + *hit = phit; + return true; + } + } + return false; +} + +bool Disc::contains(const Vec3 &pt) const +{ + Vec3 pj = proj_point_plane(pt, *this); + return length_sq(pj - this->pt) <= radius * radius; +} + +float Disc::distance(const Vec3 &v) const +{ + return 0.0; // TODO +} + +float Disc::signed_distance(const Vec3 &v) const +{ + return 0.0; // TODO +} + + +Vec3 proj_point_plane(const Vec3 &pt, const Plane &plane) +{ + float dist = plane.signed_distance(pt); + return pt - plane.normal * dist; +} + +// ---- bounding sphere calculations ---- + +bool calc_bounding_sphere(Sphere *sph, const GeomObject *obj) +{ + switch(obj->type) { + case GOBJ_SPHERE: + *sph = *(Sphere*)obj; + break; + + case GOBJ_AABOX: + sph->center = (AABOX(obj)->min + AABOX(obj)->max) * 0.5; + sph->radius = length(AABOX(obj)->max - AABOX(obj)->min) * 0.5; + break; + + case GOBJ_BOX: + sph->center = (BOX(obj)->min + BOX(obj)->max) * 0.5 + BOX(obj)->xform.get_translation(); + sph->radius = length(BOX(obj)->max - BOX(obj)->min) * 0.5; + break; + + case GOBJ_PLANE: + default: + return false; + } + return true; +} + +bool calc_bounding_sphere(Sphere *sph, const GeomObject *a, const GeomObject *b) +{ + Sphere bsa, bsb; + + if(!calc_bounding_sphere(&bsa, a) || !calc_bounding_sphere(&bsb, b)) { + return false; + } + + float dist = length(bsa.center - bsb.center); + float surf_dist = dist - (bsa.radius + bsb.radius); + float d1 = bsa.radius + surf_dist / 2.0; + float d2 = bsb.radius + surf_dist / 2.0; + float t = d1 / (d1 + d2); + + if(t < 0.0) t = 0.0; + if(t > 1.0) t = 1.0; + + sph->center = bsa.center * t + bsb.center * (1.0 - t); + sph->radius = std::max(dist * t + bsb.radius, dist * (1.0f - t) + bsa.radius); + return true; +} + +bool calc_bounding_sphere(Sphere *sph, const GeomObject **objv, int num) +{ + if(num <= 0) return false; + + if(!calc_bounding_sphere(sph, objv[0])) { + return false; + } + + for(int i=1; icenter = Vec3(0.0, 0.0, 0.0); + for(int i=0; icenter += xform * v[i]; + } + sph->center /= (float)num; + + float rad_sq = 0.0f; + for(int i=0; icenter; + rad_sq = std::max(rad_sq, dot(dir, dir)); + } + sph->radius = sqrt(rad_sq); + return true; +} + +bool calc_bounding_aabox(AABox *box, const GeomObject *obj) +{ + switch(obj->type) { + case GOBJ_AABOX: + *box = *(AABox*)obj; + break; + + case GOBJ_BOX: + { + Vec3 v[8]; + for(int i=0; i<8; i++) { + v[i] = BOX(obj)->get_corner(i); + } + calc_bounding_aabox(box, v, 8); + } + break; + + case GOBJ_SPHERE: + { + float r = SPHERE(obj)->radius; + box->min = SPHERE(obj)->center - Vec3(r, r, r); + box->max = SPHERE(obj)->center + Vec3(r, r, r); + } + break; + + case GOBJ_PLANE: + default: + return false; + } + return true; +} + +bool calc_bounding_aabox(AABox *box, const GeomObject *a, const GeomObject *b) +{ + AABox bba, bbb; + + if(!calc_bounding_aabox(&bba, a) || !calc_bounding_aabox(&bbb, b)) { + return false; + } + + for(int i=0; i<3; i++) { + box->min[i] = std::min(bba.min[i], bbb.min[i]); + box->max[i] = std::max(bba.max[i], bbb.max[i]); + } + return true; +} + +bool calc_bounding_aabox(AABox *box, const GeomObject **objv, int num) +{ + if(num <= 0) return false; + + if(!calc_bounding_aabox(box, objv[0])) { + return false; + } + + for(int i=1; imin = box->max = xform * v[0]; + for(int i=1; imin[j] = std::min(box->min[j], p[j]); + box->max[j] = std::max(box->max[j], p[j]); + } + } + return true; +} + +bool intersect_sphere_sphere(Disc *result, const Sphere &a, const Sphere &b) +{ + Vec3 dir = b.center - a.center; + + float dist_sq = length_sq(dir); + if(dist_sq <= 1e-8) return false; + + float rsum = a.radius + b.radius; + float rdif = fabs(a.radius - b.radius); + if(dist_sq > rsum * rsum || dist_sq < rdif * rdif) { + return false; + } + + float dist = sqrt(dist_sq); + float t = (dist_sq + a.radius * a.radius - b.radius * b.radius) / (2.0 * sqrt(dist_sq)); + + result->pt = a.center + dir * t; + result->normal = dir / dist; + result->radius = sin(acos(t)) * a.radius; + return true; +} + +bool intersect_plane_plane(Ray *result, const Plane &a, const Plane &b) +{ + return false; // TODO +} + +bool intersect_sphere_plane(Sphere *result, const Sphere &s, const Plane &p) +{ + return false; // TODO +} + +bool intersect_plane_sphere(Sphere *result, const Plane &p, const Sphere &s) +{ + return false; // TODO +} + +bool intersect_aabox_aabox(AABox *res, const AABox &a, const AABox &b) +{ + for(int i=0; i<3; i++) { + res->min[i] = std::max(a.min[i], b.min[i]); + res->max[i] = std::min(a.max[i], b.max[i]); + + if(res->max[i] < res->min[i]) { + res->max[i] = res->min[i]; + } + } + return res->min.x != res->max.x && res->min.y != res->max.y && res->min.z != res->max.z; +} diff --git a/src/geom.h b/src/geom.h index e110193..24a0b86 100644 --- a/src/geom.h +++ b/src/geom.h @@ -1,12 +1,17 @@ #ifndef GEOMOBJ_H_ #define GEOMOBJ_H_ +/* TODO: + * - implement distance functions + */ + #include enum GeomObjectType { GOBJ_UNKNOWN, GOBJ_SPHERE, GOBJ_AABOX, + GOBJ_BOX, GOBJ_PLANE }; @@ -23,16 +28,16 @@ struct HitPoint { class GeomObject { public: - virtual ~GeomObject(); - virtual GeomObjectType get_type() const = 0; + GeomObjectType type; - virtual void set_union(const GeomObject *obj1, const GeomObject *obj2) = 0; - virtual void set_intersection(const GeomObject *obj1, const GeomObject *obj2) = 0; + GeomObject(); + virtual ~GeomObject(); virtual bool intersect(const Ray &ray, HitPoint *hit = 0) const = 0; virtual bool contains(const Vec3 &pt) const = 0; virtual float distance(const Vec3 &v) const = 0; + virtual float signed_distance(const Vec3 &v) const = 0; }; class Sphere : public GeomObject { @@ -43,15 +48,11 @@ public: Sphere(); Sphere(const Vec3 ¢er, float radius); - GeomObjectType get_type() const; - - void set_union(const GeomObject *obj1, const GeomObject *obj2); - void set_intersection(const GeomObject *obj1, const GeomObject *obj2); - - bool intersect(const Ray &ray, HitPoint *hit = 0) const; - bool contains(const Vec3 &pt) const; + virtual bool intersect(const Ray &ray, HitPoint *hit = 0) const; + virtual bool contains(const Vec3 &pt) const; - float distance(const Vec3 &v) const; + virtual float distance(const Vec3 &v) const; + virtual float signed_distance(const Vec3 &v) const; }; class AABox : public GeomObject { @@ -61,17 +62,34 @@ public: AABox(); AABox(const Vec3 &min, const Vec3 &max); - GeomObjectType get_type() const; + virtual Vec3 get_corner(int idx) const; + + virtual bool intersect(const Ray &ray, HitPoint *hit = 0) const; + virtual bool contains(const Vec3 &pt) const; + + virtual float distance(const Vec3 &v) const; + virtual float signed_distance(const Vec3 &v) const; +}; + +class Box : public AABox { +public: + Mat4 xform; + + Box(); + Box(const Vec3 &min, const Vec3 &max); + Box(const Vec3 &pos, const Vec3 &vi, const Vec3 &vj, const Vec3 &vk); + Box(const Vec3 *varr, int vcount); - void set_union(const GeomObject *obj1, const GeomObject *obj2); - void set_intersection(const GeomObject *obj1, const GeomObject *obj2); + virtual Vec3 get_corner(int idx) const; - bool intersect(const Ray &ray, HitPoint *hit = 0) const; - bool contains(const Vec3 &pt) const; + virtual bool intersect(const Ray &ray, HitPoint *hit = 0) const; + virtual bool contains(const Vec3 &pt) const; - float distance(const Vec3 &v) const; + virtual float distance(const Vec3 &v) const; + virtual float signed_distance(const Vec3 &v) const; }; + class Plane : public GeomObject { public: Vec3 pt, normal; @@ -81,15 +99,62 @@ public: Plane(const Vec3 &p1, const Vec3 &p2, const Vec3 &p3); Plane(const Vec3 &normal, float dist); - GeomObjectType get_type() const; + virtual bool intersect(const Ray &ray, HitPoint *hit = 0) const; + virtual bool contains(const Vec3 &pt) const; - void set_union(const GeomObject *obj1, const GeomObject *obj2); - void set_intersection(const GeomObject *obj1, const GeomObject *obj2); + virtual float distance(const Vec3 &v) const; + virtual float signed_distance(const Vec3 &v) const; +}; - bool intersect(const Ray &ray, HitPoint *hit = 0) const; - bool contains(const Vec3 &pt) const; +class Disc : public Plane { +public: + float radius; + + Disc(); + Disc(const Vec3 &pt, const Vec3 &normal, float rad); + Disc(const Vec3 &normal, float dist, float rad); - float distance(const Vec3 &v) const; + virtual bool intersect(const Ray &ray, HitPoint *hit = 0) const; + //! true if the projection of pt to the plane is contained within the disc radius + virtual bool contains(const Vec3 &pt) const; + + virtual float distance(const Vec3 &v) const; + virtual float signed_distance(const Vec3 &v) const; }; +//! project point to plane +Vec3 proj_point_plane(const Vec3 &pt, const Plane &plane); + +//! calculate the bounding sphere of any object +bool calc_bounding_sphere(Sphere *sph, const GeomObject *obj); +//! calculate the bounding sphere of two objects +bool calc_bounding_sphere(Sphere *sph, const GeomObject *a, const GeomObject *b); +//! calculate the bounding sphere of multiple objects +bool calc_bounding_sphere(Sphere *sph, const GeomObject **objv, int num); +//! calculate the bounding sphere of multiple points, optionally transformed by `xform` +bool calc_bounding_sphere(Sphere *sph, const Vec3 *v, int num, const Mat4 &xform = Mat4::identity); + +//! calculate the bounding axis-aligned box of any object +bool calc_bounding_aabox(AABox *box, const GeomObject *obj); +//! calculate the bounding axis-aligned box of two objects +bool calc_bounding_aabox(AABox *box, const GeomObject *a, const GeomObject *b); +//! calculate the bounding axis-aligned box of multiple objects +bool calc_bounding_aabox(AABox *box, const GeomObject **objv, int num); +//! calculate the bounding axis-aligned box of multiple points, optionally transformed by `xform` +bool calc_bounding_aabox(AABox *box, const Vec3 *v, int num, const Mat4 &xform = Mat4::identity); + +//! calculate the intersection plane of two spheres. false if there is no plane or infinite planes. +bool intersect_sphere_sphere(Plane *result, const Sphere &a, const Sphere &b); +//! calculate the intersection line of two planes. returns false if planes are exactly parallel. +bool intersect_plane_plane(Ray *result, const Plane &a, const Plane &b); +/*! calculate the intesection circle of a plane and a sphere. returns false if they don't intersect. + * \{ + */ +bool intersect_sphere_plane(Sphere *result, const Sphere &s, const Plane &p); +bool intersect_plane_sphere(Sphere *result, const Plane &p, const Sphere &s); +//! \} + +//! calculate the intersection of two axis-aligned bounding boxes +bool intersect_aabox_aabox(AABox *res, const AABox &a, const AABox &b); + #endif // GEOMOBJ_H_ diff --git a/src/mesh.h b/src/mesh.h index 90cd1e7..2e43781 100644 --- a/src/mesh.h +++ b/src/mesh.h @@ -221,6 +221,7 @@ public: * @{ */ float get_bsphere(Vec3 *center, float *rad) const; const Sphere &get_bsphere() const; + /// @} static void set_intersect_mode(unsigned int mode); static unsigned int get_intersect_mode(); diff --git a/src/object.cc b/src/object.cc index d850d47..3318660 100644 --- a/src/object.cc +++ b/src/object.cc @@ -35,3 +35,9 @@ void Object::update(float dt) void Object::draw() const { } + +const AABox &Object::get_aabox() const +{ + static AABox null_box; + return null_box; +} diff --git a/src/object.h b/src/object.h index cc82d1b..65c39e1 100644 --- a/src/object.h +++ b/src/object.h @@ -32,6 +32,8 @@ public: virtual void update(float dt = 0.0f); virtual void draw() const; + + virtual const AABox &get_aabox() const; }; #endif // OBJECT_H_ diff --git a/src/objmesh.cc b/src/objmesh.cc index 3076e67..ab741f4 100644 --- a/src/objmesh.cc +++ b/src/objmesh.cc @@ -31,3 +31,8 @@ void ObjMesh::draw() const glPopMatrix(); } } + +const AABox &ObjMesh::get_aabox() const +{ + return mesh ? mesh->get_aabbox() : Object::get_aabox(); +} diff --git a/src/objmesh.h b/src/objmesh.h index 811caf6..ece9efe 100644 --- a/src/objmesh.h +++ b/src/objmesh.h @@ -13,6 +13,8 @@ public: ObjType get_type() const; void draw() const; + + const AABox &get_aabox() const; }; #endif // OBJMESH_H_