1 /*
2     Copyright (c) 2005-2020 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.h"
51 #include "types.h"
52 #include "vector.h"
53 #include "macros.h"
54 #include "intersect.h"
55 #include "util.h"
56 
57 #define TRIANGLE_PRIVATE
58 #include "triangle.h"
59 
60 static object_methods tri_methods = {
61   (void (*)(void *, void *))(tri_intersect),
62   (void (*)(void *, void *, void *, void *))(tri_normal),
63   tri_bbox,
64   free
65 };
66 
67 static object_methods stri_methods = {
68   (void (*)(void *, void *))(tri_intersect),
69   (void (*)(void *, void *, void *, void *))(stri_normal),
70   tri_bbox,
71   free
72 };
73 
newtri(void * tex,vector v0,vector v1,vector v2)74 object * newtri(void * tex, vector v0, vector v1, vector v2) {
75   tri * t;
76   vector edge1, edge2, edge3;
77 
78   VSub(&v1, &v0, &edge1);
79   VSub(&v2, &v0, &edge2);
80   VSub(&v2, &v1, &edge3);
81 
82   /* check to see if this will be a degenerate triangle before creation */
83   if ((VLength(&edge1) >= EPSILON) &&
84       (VLength(&edge2) >= EPSILON) &&
85       (VLength(&edge3) >= EPSILON)) {
86 
87     t=(tri *) rt_getmem(sizeof(tri));
88 
89     t->nextobj = NULL;
90     t->methods = &tri_methods;
91 
92     t->tex = (texture *)tex;
93     t->v0 = v0;
94     t->edge1 = edge1;
95     t->edge2 = edge2;
96 
97     return (object *) t;
98   }
99 
100   return NULL; /* was a degenerate triangle */
101 }
102 
103 
newstri(void * tex,vector v0,vector v1,vector v2,vector n0,vector n1,vector n2)104 object * newstri(void * tex, vector v0, vector v1, vector v2,
105                            vector n0, vector n1, vector n2) {
106   stri * t;
107   vector edge1, edge2, edge3;
108 
109   VSub(&v1, &v0, &edge1);
110   VSub(&v2, &v0, &edge2);
111   VSub(&v2, &v1, &edge3);
112 
113   /* check to see if this will be a degenerate triangle before creation */
114   if ((VLength(&edge1) >= EPSILON) &&
115       (VLength(&edge2) >= EPSILON) &&
116       (VLength(&edge3) >= EPSILON)) {
117 
118     t=(stri *) rt_getmem(sizeof(stri));
119 
120     t->nextobj = NULL;
121     t->methods = &stri_methods;
122 
123     t->tex = (texture *)tex;
124     t->v0 = v0;
125     t->edge1 = edge1;
126     t->edge2 = edge2;
127     t->n0 = n0;
128     t->n1 = n1;
129     t->n2 = n2;
130 
131     return (object *) t;
132   }
133 
134   return NULL; /* was a degenerate triangle */
135 }
136 
137 #define CROSS(dest,v1,v2) \
138           dest.x=v1.y*v2.z-v1.z*v2.y; \
139           dest.y=v1.z*v2.x-v1.x*v2.z; \
140           dest.z=v1.x*v2.y-v1.y*v2.x;
141 
142 #define DOT(v1,v2) (v1.x*v2.x+v1.y*v2.y+v1.z*v2.z)
143 
144 #define SUB(dest,v1,v2) \
145           dest.x=v1.x-v2.x; \
146           dest.y=v1.y-v2.y; \
147           dest.z=v1.z-v2.z;
148 
tri_bbox(void * obj,vector * min,vector * max)149 static int tri_bbox(void * obj, vector * min, vector * max) {
150   tri * t = (tri *) obj;
151   vector v1, v2;
152 
153   VAdd(&t->v0, &t->edge1, &v1);
154   VAdd(&t->v0, &t->edge2, &v2);
155 
156   min->x = MYMIN( t->v0.x , MYMIN( v1.x , v2.x ));
157   min->y = MYMIN( t->v0.y , MYMIN( v1.y , v2.y ));
158   min->z = MYMIN( t->v0.z , MYMIN( v1.z , v2.z ));
159 
160   max->x = MYMAX( t->v0.x , MYMAX( v1.x , v2.x ));
161   max->y = MYMAX( t->v0.y , MYMAX( v1.y , v2.y ));
162   max->z = MYMAX( t->v0.z , MYMAX( v1.z , v2.z ));
163 
164   return 1;
165 }
166 
tri_intersect(tri * trn,ray * ry)167 static void tri_intersect(tri * trn, ray * ry) {
168   vector tvec, pvec, qvec;
169   flt det, inv_det, t, u, v;
170 
171   /* begin calculating determinant - also used to calculate U parameter */
172   CROSS(pvec, ry->d, trn->edge2);
173 
174   /* if determinant is near zero, ray lies in plane of triangle */
175   det = DOT(trn->edge1, pvec);
176 
177    if (det > -EPSILON && det < EPSILON)
178      return;
179 
180    inv_det = 1.0 / det;
181 
182    /* calculate distance from vert0 to ray origin */
183    SUB(tvec, ry->o, trn->v0);
184 
185    /* calculate U parameter and test bounds */
186    u = DOT(tvec, pvec) * inv_det;
187    if (u < 0.0 || u > 1.0)
188      return;
189 
190    /* prepare to test V parameter */
191    CROSS(qvec, tvec, trn->edge1);
192 
193    /* calculate V parameter and test bounds */
194    v = DOT(ry->d, qvec) * inv_det;
195    if (v < 0.0 || u + v > 1.0)
196      return;
197 
198    /* calculate t, ray intersects triangle */
199    t = DOT(trn->edge2, qvec) * inv_det;
200 
201   add_intersection(t,(object *) trn, ry);
202 }
203 
204 
tri_normal(tri * trn,vector * pnt,ray * incident,vector * N)205 static void tri_normal(tri * trn, vector  * pnt, ray * incident, vector * N) {
206 
207   CROSS((*N), trn->edge1, trn->edge2);
208 
209   VNorm(N);
210 
211   if (VDot(N, &(incident->d)) > 0.0)  {
212     N->x=-N->x;
213     N->y=-N->y;
214     N->z=-N->z;
215   }
216 }
217 
stri_normal(stri * trn,vector * pnt,ray * incident,vector * N)218 static void stri_normal(stri * trn, vector  * pnt, ray * incident, vector * N) {
219   flt U, V, W, lensqr;
220   vector P, tmp, norm;
221 
222   CROSS(norm, trn->edge1, trn->edge2);
223   lensqr = DOT(norm, norm);
224 
225   VSUB((*pnt), trn->v0, P);
226 
227   CROSS(tmp, P, trn->edge2);
228   U = DOT(tmp, norm) / lensqr;
229 
230   CROSS(tmp, trn->edge1, P);
231   V = DOT(tmp, norm) / lensqr;
232 
233   W = 1.0 - (U + V);
234 
235   N->x = W*trn->n0.x + U*trn->n1.x + V*trn->n2.x;
236   N->y = W*trn->n0.y + U*trn->n1.y + V*trn->n2.y;
237   N->z = W*trn->n0.z + U*trn->n1.z + V*trn->n2.z;
238 
239   VNorm(N);
240 }
241 
242