svn merge -r 22571:22800 https://svn.blender.org/svnroot/bf-blender/trunk/blender
[blender.git] / source / blender / render / intern / source / rayobject.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version. 
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * The Original Code is Copyright (C) 2009 Blender Foundation.
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): AndrĂ© Pinto.
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29 #include <assert.h>
30
31 #include "BKE_utildefines.h"
32 #include "BLI_arithb.h"
33
34 #include "RE_raytrace.h"
35 #include "render_types.h"
36 #include "rayobject.h"
37 #include "raycounter.h"
38
39 /*
40  * Determines the distance that the ray must travel to hit the bounding volume of the given node
41  * Based on Tactical Optimization of Ray/Box Intersection, by Graham Fyffe
42  *  [http://tog.acm.org/resources/RTNews/html/rtnv21n1.html#art9]
43  */
44 int RE_rayobject_bb_intersect_test(const Isect *isec, const float *_bb)
45 {
46         const float *bb = _bb;
47         
48         float t1x = (bb[isec->bv_index[0]] - isec->start[0]) * isec->idot_axis[0];
49         float t2x = (bb[isec->bv_index[1]] - isec->start[0]) * isec->idot_axis[0];
50         float t1y = (bb[isec->bv_index[2]] - isec->start[1]) * isec->idot_axis[1];
51         float t2y = (bb[isec->bv_index[3]] - isec->start[1]) * isec->idot_axis[1];
52         float t1z = (bb[isec->bv_index[4]] - isec->start[2]) * isec->idot_axis[2];
53         float t2z = (bb[isec->bv_index[5]] - isec->start[2]) * isec->idot_axis[2];
54
55         RE_RC_COUNT(isec->raycounter->bb.test);
56         
57         if(t1x > t2y || t2x < t1y || t1x > t2z || t2x < t1z || t1y > t2z || t2y < t1z) return 0;
58         if(t2x < 0.0 || t2y < 0.0 || t2z < 0.0) return 0;
59         if(t1x > isec->labda || t1y > isec->labda || t1z > isec->labda) return 0;
60         RE_RC_COUNT(isec->raycounter->bb.hit);  
61
62         return 1;
63 }
64
65
66 /* only for self-intersecting test with current render face (where ray left) */
67 static int intersection2(VlakRen *face, float r0, float r1, float r2, float rx1, float ry1, float rz1)
68 {
69         float co1[3], co2[3], co3[3], co4[3];
70         float x0,x1,x2,t00,t01,t02,t10,t11,t12,t20,t21,t22;
71         float m0, m1, m2, divdet, det, det1;
72         float u1, v, u2;
73
74         VECCOPY(co1, face->v1->co);
75         VECCOPY(co2, face->v2->co);
76         if(face->v4)
77         {
78                 VECCOPY(co3, face->v4->co);
79                 VECCOPY(co4, face->v3->co);
80         }
81         else
82         {
83                 VECCOPY(co3, face->v3->co);
84         }
85
86         t00= co3[0]-co1[0];
87         t01= co3[1]-co1[1];
88         t02= co3[2]-co1[2];
89         t10= co3[0]-co2[0];
90         t11= co3[1]-co2[1];
91         t12= co3[2]-co2[2];
92         
93         x0= t11*r2-t12*r1;
94         x1= t12*r0-t10*r2;
95         x2= t10*r1-t11*r0;
96
97         divdet= t00*x0+t01*x1+t02*x2;
98
99         m0= rx1-co3[0];
100         m1= ry1-co3[1];
101         m2= rz1-co3[2];
102         det1= m0*x0+m1*x1+m2*x2;
103         
104         if(divdet!=0.0f) {
105                 u1= det1/divdet;
106
107                 if(u1<ISECT_EPSILON) {
108                         det= t00*(m1*r2-m2*r1);
109                         det+= t01*(m2*r0-m0*r2);
110                         det+= t02*(m0*r1-m1*r0);
111                         v= det/divdet;
112
113                         if(v<ISECT_EPSILON && (u1 + v) > -(1.0f+ISECT_EPSILON)) {
114                                 return 1;
115                         }
116                 }
117         }
118
119         if(face->v4) {
120
121                 t20= co3[0]-co4[0];
122                 t21= co3[1]-co4[1];
123                 t22= co3[2]-co4[2];
124
125                 divdet= t20*x0+t21*x1+t22*x2;
126                 if(divdet!=0.0f) {
127                         u2= det1/divdet;
128                 
129                         if(u2<ISECT_EPSILON) {
130                                 det= t20*(m1*r2-m2*r1);
131                                 det+= t21*(m2*r0-m0*r2);
132                                 det+= t22*(m0*r1-m1*r0);
133                                 v= det/divdet;
134         
135                                 if(v<ISECT_EPSILON && (u2 + v) >= -(1.0f+ISECT_EPSILON)) {
136                                         return 2;
137                                 }
138                         }
139                 }
140         }
141         return 0;
142 }
143
144 #include "DNA_material_types.h"
145 static int vlr_check_intersect(Isect *is, ObjectInstanceRen *obi, VlakRen *vlr)
146 {
147         /* for baking selected to active non-traceable materials might still
148          * be in the raytree */
149         if(!(vlr->mat->mode & MA_TRACEBLE))
150                 return 0;
151
152         /* I know... cpu cycle waste, might do smarter once */
153         if(is->mode==RE_RAY_MIRROR)
154                 return !(vlr->mat->mode & MA_ONLYCAST);
155         else
156                 return (is->lay & obi->lay);
157 }
158
159 static int vlr_check_intersect_solid(Isect *is, ObjectInstanceRen* obi, VlakRen *vlr)
160 {
161         /* solid material types only */
162         if (vlr->mat->material_type == MA_TYPE_SURFACE)
163                 return 1;
164         else
165                 return 0;
166 }
167
168 /* ray - triangle or quad intersection */
169 /* this function shall only modify Isect if it detects an hit */
170 static int intersect_rayface(RayFace *face, Isect *is)
171 {
172         float co1[3],co2[3],co3[3],co4[3];
173         float x0,x1,x2,t00,t01,t02,t10,t11,t12,t20,t21,t22,r0,r1,r2;
174         float m0, m1, m2, divdet, det1;
175         float labda, u, v;
176         short ok=0;
177         
178         if(is->orig.ob == face->ob && is->orig.face == face->face)
179                 return 0;
180                 
181         if(is->skip & RE_SKIP_VLR_RENDER_CHECK)
182         {
183                 if(vlr_check_intersect(is, (ObjectInstanceRen*)face->ob, (VlakRen*)face->face ) == 0)
184                         return 0;
185         }
186         if(is->skip & RE_SKIP_VLR_NON_SOLID_MATERIAL)
187         {
188                 if(vlr_check_intersect_solid(is, (ObjectInstanceRen*)face->ob, (VlakRen*)face->face) == 0)
189                         return 0;
190         }
191
192         RE_RC_COUNT(is->raycounter->faces.test);
193
194         //Load coords
195         VECCOPY(co1, face->v1);
196         VECCOPY(co2, face->v2);
197         if(RE_rayface_isQuad(face))
198         {
199                 VECCOPY(co3, face->v4);
200                 VECCOPY(co4, face->v3);
201         }
202         else
203         {
204                 VECCOPY(co3, face->v3);
205         }
206
207         t00= co3[0]-co1[0];
208         t01= co3[1]-co1[1];
209         t02= co3[2]-co1[2];
210         t10= co3[0]-co2[0];
211         t11= co3[1]-co2[1];
212         t12= co3[2]-co2[2];
213         
214         r0= is->vec[0];
215         r1= is->vec[1];
216         r2= is->vec[2];
217         
218         x0= t12*r1-t11*r2;
219         x1= t10*r2-t12*r0;
220         x2= t11*r0-t10*r1;
221
222         divdet= t00*x0+t01*x1+t02*x2;
223
224         m0= is->start[0]-co3[0];
225         m1= is->start[1]-co3[1];
226         m2= is->start[2]-co3[2];
227         det1= m0*x0+m1*x1+m2*x2;
228         
229         if(divdet!=0.0f) {
230
231                 divdet= 1.0f/divdet;
232                 u= det1*divdet;
233                 if(u<ISECT_EPSILON && u>-(1.0f+ISECT_EPSILON)) {
234                         float cros0, cros1, cros2;
235                         
236                         cros0= m1*t02-m2*t01;
237                         cros1= m2*t00-m0*t02;
238                         cros2= m0*t01-m1*t00;
239                         v= divdet*(cros0*r0 + cros1*r1 + cros2*r2);
240
241                         if(v<ISECT_EPSILON && (u + v) > -(1.0f+ISECT_EPSILON)) {
242                                 labda= divdet*(cros0*t10 + cros1*t11 + cros2*t12);
243
244                                 if(labda>-ISECT_EPSILON && labda<is->labda) {
245                                         ok= 1;
246                                 }
247                         }
248                 }
249         }
250
251         if(ok==0 && RE_rayface_isQuad(face)) {
252
253                 t20= co3[0]-co4[0];
254                 t21= co3[1]-co4[1];
255                 t22= co3[2]-co4[2];
256
257                 divdet= t20*x0+t21*x1+t22*x2;
258                 if(divdet!=0.0f) {
259                         divdet= 1.0f/divdet;
260                         u = det1*divdet;
261                         
262                         if(u<ISECT_EPSILON && u>-(1.0f+ISECT_EPSILON)) {
263                                 float cros0, cros1, cros2;
264                                 cros0= m1*t22-m2*t21;
265                                 cros1= m2*t20-m0*t22;
266                                 cros2= m0*t21-m1*t20;
267                                 v= divdet*(cros0*r0 + cros1*r1 + cros2*r2);
268         
269                                 if(v<ISECT_EPSILON && (u + v) >-(1.0f+ISECT_EPSILON)) {
270                                         labda= divdet*(cros0*t10 + cros1*t11 + cros2*t12);
271                                         
272                                         if(labda>-ISECT_EPSILON && labda<is->labda) {
273                                                 ok= 2;
274                                         }
275                                 }
276                         }
277                 }
278         }
279
280         if(ok) {
281         
282                 /* when a shadow ray leaves a face, it can be little outside the edges of it, causing
283                 intersection to be detected in its neighbour face */
284                 if(is->skip & RE_SKIP_VLR_NEIGHBOUR)
285                 {
286                         if(labda < 0.1f && is->orig.ob == face->ob)
287                         {
288                                 VlakRen * a = is->orig.face;
289                                 VlakRen * b = face->face;
290
291                                 /* so there's a shared edge or vertex, let's intersect ray with face
292                                 itself, if that's true we can safely return 1, otherwise we assume
293                                 the intersection is invalid, 0 */
294                                 if(a->v1==b->v1 || a->v2==b->v1 || a->v3==b->v1 || a->v4==b->v1
295                                 || a->v1==b->v2 || a->v2==b->v2 || a->v3==b->v2 || a->v4==b->v2
296                                 || a->v1==b->v3 || a->v2==b->v3 || a->v3==b->v3 || a->v4==b->v3
297                                 || (b->v4 && (a->v1==b->v4 || a->v2==b->v4 || a->v3==b->v4 || a->v4==b->v4)))
298                                 if(!intersection2((VlakRen*)a, -r0, -r1, -r2, is->start[0], is->start[1], is->start[2]))
299                                 {
300                                         return 0;
301                                 }
302                         }
303                 }
304
305                 RE_RC_COUNT(is->raycounter->faces.hit);
306
307                 is->isect= ok;  // wich half of the quad
308                 is->labda= labda;
309                 is->u= u; is->v= v;
310
311                 is->hit.ob   = face->ob;
312                 is->hit.face = face->face;
313 #ifdef RT_USE_LAST_HIT
314                 is->last_hit = (RayObject*) RE_rayobject_unalignRayFace(face);
315 #endif
316                 return 1;
317         }
318
319         return 0;
320 }
321
322 void RE_rayface_from_vlak(RayFace *face, ObjectInstanceRen *obi, VlakRen *vlr)
323 {
324         VECCOPY(face->v1, vlr->v1->co);
325         VECCOPY(face->v2, vlr->v2->co);
326         VECCOPY(face->v3, vlr->v3->co);
327         if(vlr->v4)
328         {
329                 VECCOPY(face->v4, vlr->v4->co);
330                 face->quad = 1;
331         }
332         else
333         {
334                 face->quad = 0;
335         }
336
337         face->ob   = obi;
338         face->face = vlr;
339 }
340
341
342 int RE_rayobject_raycast(RayObject *r, Isect *isec)
343 {
344         int i;
345         RE_RC_COUNT(isec->raycounter->raycast.test);
346
347         /* Setup vars used on raycast */
348         isec->labda *= Normalize(isec->vec);
349         isec->dist = VecLength(isec->vec);
350         
351         for(i=0; i<3; i++)
352         {
353                 isec->idot_axis[i]              = 1.0f / isec->vec[i];
354                 
355                 isec->bv_index[2*i]             = isec->idot_axis[i] < 0.0 ? 1 : 0;
356                 isec->bv_index[2*i+1]   = 1 - isec->bv_index[2*i];
357                 
358                 isec->bv_index[2*i]             = i+3*isec->bv_index[2*i];
359                 isec->bv_index[2*i+1]   = i+3*isec->bv_index[2*i+1];
360         }
361
362 #ifdef RT_USE_LAST_HIT  
363         /* Last hit heuristic */
364         if(isec->mode==RE_RAY_SHADOW && isec->last_hit)
365         {
366                 RE_RC_COUNT(isec->raycounter->rayshadow_last_hit.test);
367                 
368                 if(RE_rayobject_intersect(isec->last_hit, isec))
369                 {
370                         RE_RC_COUNT(isec->raycounter->raycast.hit);
371                         RE_RC_COUNT(isec->raycounter->rayshadow_last_hit.hit);
372                         return 1;
373                 }
374         }
375 #endif
376
377 #ifdef RT_USE_HINT
378         isec->hit_hint = 0;
379 #endif
380
381         if(RE_rayobject_intersect(r, isec))
382         {
383                 RE_RC_COUNT(isec->raycounter->raycast.hit);
384
385 #ifdef RT_USE_HINT
386                 isec->hint = isec->hit_hint;
387 #endif
388                 return 1;
389         }
390         return 0;
391 }
392
393 int RE_rayobject_intersect(RayObject *r, Isect *i)
394 {
395         if(RE_rayobject_isRayFace(r))
396         {
397                 return intersect_rayface( (RayFace*) RE_rayobject_align(r), i);
398         }
399         else if(RE_rayobject_isRayAPI(r))
400         {
401                 r = RE_rayobject_align( r );
402                 return r->api->raycast( r, i );
403         }
404         else assert(0);
405 }
406
407 void RE_rayobject_add(RayObject *r, RayObject *o)
408 {
409         r = RE_rayobject_align( r );
410         return r->api->add( r, o );
411 }
412
413 void RE_rayobject_done(RayObject *r)
414 {
415         r = RE_rayobject_align( r );
416         r->api->done( r );
417 }
418
419 void RE_rayobject_free(RayObject *r)
420 {
421         r = RE_rayobject_align( r );
422         r->api->free( r );
423 }
424
425 void RE_rayobject_merge_bb(RayObject *r, float *min, float *max)
426 {
427         if(RE_rayobject_isRayFace(r))
428         {
429                 RayFace *face = (RayFace*) RE_rayobject_align(r);
430                 
431                 DO_MINMAX( face->v1, min, max );
432                 DO_MINMAX( face->v2, min, max );
433                 DO_MINMAX( face->v3, min, max );
434                 if(RE_rayface_isQuad(face)) DO_MINMAX( face->v4, min, max );
435         }
436         else if(RE_rayobject_isRayAPI(r))
437         {
438                 r = RE_rayobject_align( r );
439                 r->api->bb( r, min, max );
440         }
441         else assert(0);
442 }
443
444 float RE_rayobject_cost(RayObject *r)
445 {
446         if(RE_rayobject_isRayFace(r))
447         {
448                 return 1.0;
449         }
450         else if(RE_rayobject_isRayAPI(r))
451         {
452                 r = RE_rayobject_align( r );
453                 return r->api->cost( r );
454         }
455         else assert(0);
456 }
457
458 void RE_rayobject_hint_bb(RayObject *r, RayHint *hint, float *min, float *max)
459 {
460         if(RE_rayobject_isRayFace(r))
461         {
462                 return;
463         }
464         else if(RE_rayobject_isRayAPI(r))
465         {
466                 r = RE_rayobject_align( r );
467                 return r->api->hint_bb( r, hint, min, max );
468         }
469         else assert(0);
470 }
471