1 /* 2 Copyright (c) 2005-2021 Intel Corporation 3 4 Licensed under the Apache License, Version 2.0 (the "License"); 5 you may not use this file except in compliance with the License. 6 You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10 Unless required by applicable law or agreed to in writing, software 11 distributed under the License is distributed on an "AS IS" BASIS, 12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 See the License for the specific language governing permissions and 14 limitations under the License. 15 */ 16 17 /* 18 The original source for this example is 19 Copyright (c) 1994-2008 John E. Stone 20 All rights reserved. 21 22 Redistribution and use in source and binary forms, with or without 23 modification, are permitted provided that the following conditions 24 are met: 25 1. Redistributions of source code must retain the above copyright 26 notice, this list of conditions and the following disclaimer. 27 2. Redistributions in binary form must reproduce the above copyright 28 notice, this list of conditions and the following disclaimer in the 29 documentation and/or other materials provided with the distribution. 30 3. The name of the author may not be used to endorse or promote products 31 derived from this software without specific prior written permission. 32 33 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS 34 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 35 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 36 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 37 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 38 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 39 OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 40 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 41 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 42 OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 43 SUCH DAMAGE. 44 */ 45 46 /* 47 * triangle.cpp - This file contains the functions for dealing with triangles. 48 */ 49 50 #include "machine.hpp" 51 #include "types.hpp" 52 #include "vector.hpp" 53 #include "macros.hpp" 54 #include "intersect.hpp" 55 #include "util.hpp" 56 57 #define TRIANGLE_PRIVATE 58 #include "triangle.hpp" 59 60 static object_methods tri_methods = { (void (*)(void *, void *))(tri_intersect), 61 (void (*)(void *, void *, void *, void *))(tri_normal), 62 tri_bbox, 63 free }; 64 65 static object_methods stri_methods = { (void (*)(void *, void *))(tri_intersect), 66 (void (*)(void *, void *, void *, void *))(stri_normal), 67 tri_bbox, 68 free }; 69 70 object *newtri(void *tex, vector v0, vector v1, vector v2) { 71 tri *t; 72 vector edge1, edge2, edge3; 73 74 VSub(&v1, &v0, &edge1); 75 VSub(&v2, &v0, &edge2); 76 VSub(&v2, &v1, &edge3); 77 78 /* check to see if this will be a degenerate triangle before creation */ 79 if ((VLength(&edge1) >= EPSILON) && (VLength(&edge2) >= EPSILON) && 80 (VLength(&edge3) >= EPSILON)) { 81 t = (tri *)rt_getmem(sizeof(tri)); 82 83 t->nextobj = nullptr; 84 t->methods = &tri_methods; 85 86 t->tex = (texture *)tex; 87 t->v0 = v0; 88 t->edge1 = edge1; 89 t->edge2 = edge2; 90 91 return (object *)t; 92 } 93 94 return nullptr; /* was a degenerate triangle */ 95 } 96 97 object *newstri(void *tex, vector v0, vector v1, vector v2, vector n0, vector n1, vector n2) { 98 stri *t; 99 vector edge1, edge2, edge3; 100 101 VSub(&v1, &v0, &edge1); 102 VSub(&v2, &v0, &edge2); 103 VSub(&v2, &v1, &edge3); 104 105 /* check to see if this will be a degenerate triangle before creation */ 106 if ((VLength(&edge1) >= EPSILON) && (VLength(&edge2) >= EPSILON) && 107 (VLength(&edge3) >= EPSILON)) { 108 t = (stri *)rt_getmem(sizeof(stri)); 109 110 t->nextobj = nullptr; 111 t->methods = &stri_methods; 112 113 t->tex = (texture *)tex; 114 t->v0 = v0; 115 t->edge1 = edge1; 116 t->edge2 = edge2; 117 t->n0 = n0; 118 t->n1 = n1; 119 t->n2 = n2; 120 121 return (object *)t; 122 } 123 124 return nullptr; /* was a degenerate triangle */ 125 } 126 127 #define CROSS(dest, v1, v2) \ 128 dest.x = v1.y * v2.z - v1.z * v2.y; \ 129 dest.y = v1.z * v2.x - v1.x * v2.z; \ 130 dest.z = v1.x * v2.y - v1.y * v2.x; 131 132 #define DOT(v1, v2) (v1.x * v2.x + v1.y * v2.y + v1.z * v2.z) 133 134 #define SUB(dest, v1, v2) \ 135 dest.x = v1.x - v2.x; \ 136 dest.y = v1.y - v2.y; \ 137 dest.z = v1.z - v2.z; 138 139 static int tri_bbox(void *obj, vector *min, vector *max) { 140 tri *t = (tri *)obj; 141 vector v1, v2; 142 143 VAdd(&t->v0, &t->edge1, &v1); 144 VAdd(&t->v0, &t->edge2, &v2); 145 146 min->x = MYMIN(t->v0.x, MYMIN(v1.x, v2.x)); 147 min->y = MYMIN(t->v0.y, MYMIN(v1.y, v2.y)); 148 min->z = MYMIN(t->v0.z, MYMIN(v1.z, v2.z)); 149 150 max->x = MYMAX(t->v0.x, MYMAX(v1.x, v2.x)); 151 max->y = MYMAX(t->v0.y, MYMAX(v1.y, v2.y)); 152 max->z = MYMAX(t->v0.z, MYMAX(v1.z, v2.z)); 153 154 return 1; 155 } 156 157 static void tri_intersect(tri *trn, ray *ry) { 158 vector tvec, pvec, qvec; 159 flt det, inv_det, t, u, v; 160 161 /* begin calculating determinant - also used to calculate U parameter */ 162 CROSS(pvec, ry->d, trn->edge2); 163 164 /* if determinant is near zero, ray lies in plane of triangle */ 165 det = DOT(trn->edge1, pvec); 166 167 if (det > -EPSILON && det < EPSILON) 168 return; 169 170 inv_det = 1.0 / det; 171 172 /* calculate distance from vert0 to ray origin */ 173 SUB(tvec, ry->o, trn->v0); 174 175 /* calculate U parameter and test bounds */ 176 u = DOT(tvec, pvec) * inv_det; 177 if (u < 0.0 || u > 1.0) 178 return; 179 180 /* prepare to test V parameter */ 181 CROSS(qvec, tvec, trn->edge1); 182 183 /* calculate V parameter and test bounds */ 184 v = DOT(ry->d, qvec) * inv_det; 185 if (v < 0.0 || u + v > 1.0) 186 return; 187 188 /* calculate t, ray intersects triangle */ 189 t = DOT(trn->edge2, qvec) * inv_det; 190 191 add_intersection(t, (object *)trn, ry); 192 } 193 194 static void tri_normal(tri *trn, vector *pnt, ray *incident, vector *N) { 195 CROSS((*N), trn->edge1, trn->edge2); 196 197 VNorm(N); 198 199 if (VDot(N, &(incident->d)) > 0.0) { 200 N->x = -N->x; 201 N->y = -N->y; 202 N->z = -N->z; 203 } 204 } 205 206 static void stri_normal(stri *trn, vector *pnt, ray *incident, vector *N) { 207 flt U, V, W, lensqr; 208 vector P, tmp, norm; 209 210 CROSS(norm, trn->edge1, trn->edge2); 211 lensqr = DOT(norm, norm); 212 213 VSUB((*pnt), trn->v0, P); 214 215 CROSS(tmp, P, trn->edge2); 216 U = DOT(tmp, norm) / lensqr; 217 218 CROSS(tmp, trn->edge1, P); 219 V = DOT(tmp, norm) / lensqr; 220 221 W = 1.0 - (U + V); 222 223 N->x = W * trn->n0.x + U * trn->n1.x + V * trn->n2.x; 224 N->y = W * trn->n0.y + U * trn->n1.y + V * trn->n2.y; 225 N->z = W * trn->n0.z + U * trn->n1.z + V * trn->n2.z; 226 227 VNorm(N); 228 } 229