ref: f8c416f7bb32c781434bce40af9b86cf3e73b82f
dir: /tools/3D-Reconstruction/sketch_3D_reconstruction/BVH.pde/
/* *AABB bounding box *Bouding Volume Hierarchy */ class BoundingBox { float min_x, min_y, min_z, max_x, max_y, max_z; PVector center; BoundingBox() { min_x = Float.POSITIVE_INFINITY; min_y = Float.POSITIVE_INFINITY; min_z = Float.POSITIVE_INFINITY; max_x = Float.NEGATIVE_INFINITY; max_y = Float.NEGATIVE_INFINITY; max_z = Float.NEGATIVE_INFINITY; center = new PVector(); } // build a bounding box for a triangle void create(Triangle t) { min_x = min(t.p1.x, min(t.p2.x, t.p3.x)); max_x = max(t.p1.x, max(t.p2.x, t.p3.x)); min_y = min(t.p1.y, min(t.p2.y, t.p3.y)); max_y = max(t.p1.y, max(t.p2.y, t.p3.y)); min_z = min(t.p1.z, min(t.p2.z, t.p3.z)); max_z = max(t.p1.z, max(t.p2.z, t.p3.z)); center.x = (max_x + min_x) / 2; center.y = (max_y + min_y) / 2; center.z = (max_z + min_z) / 2; } // merge two bounding boxes void add(BoundingBox bbx) { min_x = min(min_x, bbx.min_x); min_y = min(min_y, bbx.min_y); min_z = min(min_z, bbx.min_z); max_x = max(max_x, bbx.max_x); max_y = max(max_y, bbx.max_y); max_z = max(max_z, bbx.max_z); center.x = (max_x + min_x) / 2; center.y = (max_y + min_y) / 2; center.z = (max_z + min_z) / 2; } // get bounding box center axis value float getCenterAxisValue(int axis) { if (axis == 1) { return center.x; } else if (axis == 2) { return center.y; } // when axis == 3 return center.z; } // check if a ray is intersected with the bounding box boolean intersect(Ray r) { float tmin, tmax; if (r.dir.x >= 0) { tmin = (min_x - r.ori.x) * (1.0f / r.dir.x); tmax = (max_x - r.ori.x) * (1.0f / r.dir.x); } else { tmin = (max_x - r.ori.x) * (1.0f / r.dir.x); tmax = (min_x - r.ori.x) * (1.0f / r.dir.x); } float tymin, tymax; if (r.dir.y >= 0) { tymin = (min_y - r.ori.y) * (1.0f / r.dir.y); tymax = (max_y - r.ori.y) * (1.0f / r.dir.y); } else { tymin = (max_y - r.ori.y) * (1.0f / r.dir.y); tymax = (min_y - r.ori.y) * (1.0f / r.dir.y); } if (tmax < tymin || tymax < tmin) { return false; } tmin = tmin < tymin ? tymin : tmin; tmax = tmax > tymax ? tymax : tmax; float tzmin, tzmax; if (r.dir.z >= 0) { tzmin = (min_z - r.ori.z) * (1.0f / r.dir.z); tzmax = (max_z - r.ori.z) * (1.0f / r.dir.z); } else { tzmin = (max_z - r.ori.z) * (1.0f / r.dir.z); tzmax = (min_z - r.ori.z) * (1.0f / r.dir.z); } if (tmax < tzmin || tmin > tzmax) { return false; } return true; } } // Bounding Volume Hierarchy class BVH { // Binary Tree BVH left, right; BoundingBox overall_bbx; ArrayList<Triangle> mesh; BVH(ArrayList<Triangle> mesh) { this.mesh = mesh; overall_bbx = new BoundingBox(); left = null; right = null; int mesh_size = this.mesh.size(); if (mesh_size <= 1) { return; } // random select an axis int axis = int(random(100)) % 3 + 1; // build bounding box and save the selected center component float[] axis_values = new float[mesh_size]; for (int i = 0; i < mesh_size; i++) { Triangle t = this.mesh.get(i); overall_bbx.add(t.bbx); axis_values[i] = t.bbx.getCenterAxisValue(axis); } // find the median value of selected center component as pivot axis_values = sort(axis_values); float pivot; if (mesh_size % 2 == 1) { pivot = axis_values[mesh_size / 2]; } else { pivot = 0.5f * (axis_values[mesh_size / 2 - 1] + axis_values[mesh_size / 2]); } // Build left node and right node by partitioning the mesh based on triangle // bounding box center component value ArrayList<Triangle> left_mesh = new ArrayList<Triangle>(); ArrayList<Triangle> right_mesh = new ArrayList<Triangle>(); for (int i = 0; i < mesh_size; i++) { Triangle t = this.mesh.get(i); if (t.bbx.getCenterAxisValue(axis) < pivot) { left_mesh.add(t); } else if (t.bbx.getCenterAxisValue(axis) > pivot) { right_mesh.add(t); } else if (left_mesh.size() < right_mesh.size()) { left_mesh.add(t); } else { right_mesh.add(t); } } left = new BVH(left_mesh); right = new BVH(right_mesh); } // check if a ray intersect with current volume boolean intersect(Ray r, float[] param) { if (mesh.size() == 0) { return false; } if (mesh.size() == 1) { Triangle t = mesh.get(0); return t.intersect(r, param); } if (!overall_bbx.intersect(r)) { return false; } boolean left_res = left.intersect(r, param); boolean right_res = right.intersect(r, param); return left_res || right_res; } }