1/* 2 *AABB bounding box 3 *Bouding Volume Hierarchy 4 */ 5class BoundingBox { 6 float min_x, min_y, min_z, max_x, max_y, max_z; 7 PVector center; 8 BoundingBox() { 9 min_x = Float.POSITIVE_INFINITY; 10 min_y = Float.POSITIVE_INFINITY; 11 min_z = Float.POSITIVE_INFINITY; 12 max_x = Float.NEGATIVE_INFINITY; 13 max_y = Float.NEGATIVE_INFINITY; 14 max_z = Float.NEGATIVE_INFINITY; 15 center = new PVector(); 16 } 17 // build a bounding box for a triangle 18 void create(Triangle t) { 19 min_x = min(t.p1.x, min(t.p2.x, t.p3.x)); 20 max_x = max(t.p1.x, max(t.p2.x, t.p3.x)); 21 22 min_y = min(t.p1.y, min(t.p2.y, t.p3.y)); 23 max_y = max(t.p1.y, max(t.p2.y, t.p3.y)); 24 25 min_z = min(t.p1.z, min(t.p2.z, t.p3.z)); 26 max_z = max(t.p1.z, max(t.p2.z, t.p3.z)); 27 center.x = (max_x + min_x) / 2; 28 center.y = (max_y + min_y) / 2; 29 center.z = (max_z + min_z) / 2; 30 } 31 // merge two bounding boxes 32 void add(BoundingBox bbx) { 33 min_x = min(min_x, bbx.min_x); 34 min_y = min(min_y, bbx.min_y); 35 min_z = min(min_z, bbx.min_z); 36 37 max_x = max(max_x, bbx.max_x); 38 max_y = max(max_y, bbx.max_y); 39 max_z = max(max_z, bbx.max_z); 40 center.x = (max_x + min_x) / 2; 41 center.y = (max_y + min_y) / 2; 42 center.z = (max_z + min_z) / 2; 43 } 44 // get bounding box center axis value 45 float getCenterAxisValue(int axis) { 46 if (axis == 1) { 47 return center.x; 48 } else if (axis == 2) { 49 return center.y; 50 } 51 // when axis == 3 52 return center.z; 53 } 54 // check if a ray is intersected with the bounding box 55 boolean intersect(Ray r) { 56 float tmin, tmax; 57 if (r.dir.x >= 0) { 58 tmin = (min_x - r.ori.x) * (1.0f / r.dir.x); 59 tmax = (max_x - r.ori.x) * (1.0f / r.dir.x); 60 } else { 61 tmin = (max_x - r.ori.x) * (1.0f / r.dir.x); 62 tmax = (min_x - r.ori.x) * (1.0f / r.dir.x); 63 } 64 65 float tymin, tymax; 66 if (r.dir.y >= 0) { 67 tymin = (min_y - r.ori.y) * (1.0f / r.dir.y); 68 tymax = (max_y - r.ori.y) * (1.0f / r.dir.y); 69 } else { 70 tymin = (max_y - r.ori.y) * (1.0f / r.dir.y); 71 tymax = (min_y - r.ori.y) * (1.0f / r.dir.y); 72 } 73 74 if (tmax < tymin || tymax < tmin) { 75 return false; 76 } 77 78 tmin = tmin < tymin ? tymin : tmin; 79 tmax = tmax > tymax ? tymax : tmax; 80 81 float tzmin, tzmax; 82 if (r.dir.z >= 0) { 83 tzmin = (min_z - r.ori.z) * (1.0f / r.dir.z); 84 tzmax = (max_z - r.ori.z) * (1.0f / r.dir.z); 85 } else { 86 tzmin = (max_z - r.ori.z) * (1.0f / r.dir.z); 87 tzmax = (min_z - r.ori.z) * (1.0f / r.dir.z); 88 } 89 if (tmax < tzmin || tmin > tzmax) { 90 return false; 91 } 92 return true; 93 } 94} 95// Bounding Volume Hierarchy 96class BVH { 97 // Binary Tree 98 BVH left, right; 99 BoundingBox overall_bbx; 100 ArrayList<Triangle> mesh; 101 BVH(ArrayList<Triangle> mesh) { 102 this.mesh = mesh; 103 overall_bbx = new BoundingBox(); 104 left = null; 105 right = null; 106 int mesh_size = this.mesh.size(); 107 if (mesh_size <= 1) { 108 return; 109 } 110 // random select an axis 111 int axis = int(random(100)) % 3 + 1; 112 // build bounding box and save the selected center component 113 float[] axis_values = new float[mesh_size]; 114 for (int i = 0; i < mesh_size; i++) { 115 Triangle t = this.mesh.get(i); 116 overall_bbx.add(t.bbx); 117 axis_values[i] = t.bbx.getCenterAxisValue(axis); 118 } 119 // find the median value of selected center component as pivot 120 axis_values = sort(axis_values); 121 float pivot; 122 if (mesh_size % 2 == 1) { 123 pivot = axis_values[mesh_size / 2]; 124 } else { 125 pivot = 126 0.5f * (axis_values[mesh_size / 2 - 1] + axis_values[mesh_size / 2]); 127 } 128 // Build left node and right node by partitioning the mesh based on triangle 129 // bounding box center component value 130 ArrayList<Triangle> left_mesh = new ArrayList<Triangle>(); 131 ArrayList<Triangle> right_mesh = new ArrayList<Triangle>(); 132 for (int i = 0; i < mesh_size; i++) { 133 Triangle t = this.mesh.get(i); 134 if (t.bbx.getCenterAxisValue(axis) < pivot) { 135 left_mesh.add(t); 136 } else if (t.bbx.getCenterAxisValue(axis) > pivot) { 137 right_mesh.add(t); 138 } else if (left_mesh.size() < right_mesh.size()) { 139 left_mesh.add(t); 140 } else { 141 right_mesh.add(t); 142 } 143 } 144 left = new BVH(left_mesh); 145 right = new BVH(right_mesh); 146 } 147 // check if a ray intersect with current volume 148 boolean intersect(Ray r, float[] param) { 149 if (mesh.size() == 0) { 150 return false; 151 } 152 if (mesh.size() == 1) { 153 Triangle t = mesh.get(0); 154 return t.intersect(r, param); 155 } 156 if (!overall_bbx.intersect(r)) { 157 return false; 158 } 159 boolean left_res = left.intersect(r, param); 160 boolean right_res = right.intersect(r, param); 161 return left_res || right_res; 162 } 163} 164