11 bool intersect(
const Triangle *triangle,
const Ray& ray,
const float htmax,
float &t,
float &tu,
float &tv )
19 const float det=
dot(ab, pvec);
20 if (det > -0.0001f && det < 0.0001f)
return false;
22 const float inv_det= 1.0f / det;
28 const float u=
dot(tvec, pvec) * inv_det;
29 if(u < 0.0f || u > 1.0f)
return false;
35 const float v=
dot(ray.direction, qvec) * inv_det;
36 if(v < 0.0f || u + v > 1.0f)
return false;
39 float hit=
dot(ac, qvec) * inv_det;
45 return (hit > 0 && hit < htmax);
66 bool intersect(
const BBox& box,
const Ray &ray,
const float htmax )
69 float tmin= (box.min.x - ray.origin.x) / ray.direction.x;
70 float tmax= (box.max.x - ray.origin.x) / ray.direction.x;
71 if(tmax < tmin) std::swap(tmin, tmax);
74 float tymin= (box.min.y - ray.origin.y) / ray.direction.y;
75 float tymax= (box.max.y - ray.origin.y) / ray.direction.y;
76 if(tymax < tymin) std::swap(tymin, tymax);
78 if((tmin > tymax) || (tymin > tmax))
return false;
79 if(tymin > tmin) tmin= tymin;
80 if(tymax < tmax) tmax= tymax;
83 float tzmin= (box.min.z - ray.origin.z) / ray.direction.z;
84 float tzmax= (box.max.z - ray.origin.z) / ray.direction.z;
85 if(tzmax < tzmin) std::swap(tzmin, tzmax);
87 if((tmin > tzmax) || (tzmin > tmax))
return false;
88 if(tzmin > tmin) tmin= tzmin;
89 if(tzmax < tmax) tmax= tzmax;
92 return (tmin < tmax && tmax > 0 && tmin < htmax);
101 node->triangle=
nullptr;
110 leaf->right=
nullptr;
111 leaf->triangle= triangle;
119 CutLess(
const int a,
const float c ) : axis(a), cut(c) {}
124 bool operator() (
const Triangle& t )
128 bbox_insert(box, t.a);
129 bbox_insert(box, t.b);
130 bbox_insert(box, t.c);
132 if(axis == 0 && box.min.x < cut)
return true;
133 else if(axis == 1 && box.min.y < cut)
return true;
134 else if(axis == 2 && box.min.z < cut)
return true;
139 BVHNode *build_node( std::vector<Triangle>& triangles,
const unsigned int begin,
const unsigned int end )
146 for(
unsigned int i= begin; i <
end; i++)
148 bbox_insert(box, triangles[i].a);
149 bbox_insert(box, triangles[i].b);
150 bbox_insert(box, triangles[i].c);
155 return create_leaf(box, &triangles.front() +
begin);
162 if(d.x > d.y && d.x > d.z) { axis= 0; cut= (box.min.x + box.max.x) / 2; }
163 else if(d.y > d.x && d.y > d.z) { axis= 1; cut= (box.min.y + box.max.y) / 2; }
164 else { axis= 2; cut= (box.min.z + box.max.z) / 2; }
170 if(mid == begin || mid == end)
172 mid= (begin +
end) / 2;
174 return create_node(box,
175 build_node(triangles, begin, mid),
176 build_node(triangles, mid, end));
180 BVH make_bvh(
const std::vector<vec3>& positions )
185 bvh.triangles.reserve(positions.size() / 3);
186 for(
unsigned int i= 0; i +2 < positions.size(); i= i + 3)
189 printf(
"building bvh %d triangles...\n", (
int) bvh.triangles.size());
192 bvh.root= build_node(bvh.triangles, 0, bvh.triangles.size());
193 bvh.box= bvh.root->box;
198 unsigned long int box_n= 0;
199 unsigned long int tri_n= 0;
202 void node_intersect(
const BVHNode *node,
const Ray& ray,
Hit& hit )
204 if(node ==
nullptr)
return;
211 if(intersect(node->triangle, ray, hit.
t, t, u, v))
215 hit.
p= ray.origin + t * ray.direction;
219 Vector ab=
Vector(node->triangle->a, node->triangle->b);
220 Vector ac=
Vector(node->triangle->a, node->triangle->c);
226 unsigned int id= (
unsigned long int) node->triangle & 255;
227 hit.
color=
Color(1.f - (
id % 16) / 15.f, (
id % 16) / 15.f,
id / 255.f);
235 if(intersect(node->box, ray, hit.
t))
238 node_intersect(node->left, ray, hit);
239 node_intersect(node->right, ray, hit);
244 bool intersect(
const BVH& bvh,
const Ray& ray,
const float tmax,
Hit& hit )
249 node_intersect(bvh.root, ray, hit);
representation d'un triangle.
void end(Widgets &w)
termine la description des elements de l'interface graphique.
Vector normalize(const Vector &v)
renvoie un vecteur unitaire / longueur == 1.
Color Black()
utilitaire. renvoie une couleur noire.
representation d'une couleur (rgba) transparente ou opaque.
Color color
couleur de la surface au point d'intersection
representation d'un vecteur 3d.
float dot(const Vector &u, const Vector &v)
renvoie le produit scalaire de 2 vecteurs.
float t
abscisse : p= o + t.d
representation d'un point d'intersection.
void begin(Widgets &w)
debut de la description des elements de l'interface graphique.
void printf(Text &text, const int px, const int py, const char *format,...)
affiche un texte a la position x, y. meme utilisation que printf().
Vector n
normale de la surface au point d'intersection
representation d'un rayon.
representation d'un noeud du bvh.
float distance(const Point &a, const Point &b)
renvoie la distance etre 2 points.
representation d'un point 3d.
Vector cross(const Vector &u, const Vector &v)
renvoie le produit vectoriel de 2 vecteurs.