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 
newtri(void * tex,vector v0,vector v1,vector v2)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 
newstri(void * tex,vector v0,vector v1,vector v2,vector n0,vector n1,vector n2)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 
tri_bbox(void * obj,vector * min,vector * max)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 
tri_intersect(tri * trn,ray * ry)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 
tri_normal(tri * trn,vector * pnt,ray * incident,vector * N)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 
stri_normal(stri * trn,vector * pnt,ray * incident,vector * N)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