warning fixes.
[blender-staging.git] / source / blender / render / intern / raytrace / rayobject.cpp
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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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_math.h"
33 #include "DNA_material_types.h"
34
35 #include "RE_raytrace.h"
36 #include "render_types.h"
37 #include "rayobject.h"
38 #include "raycounter.h"
39
40 /*
41  * Determines the distance that the ray must travel to hit the bounding volume of the given node
42  * Based on Tactical Optimization of Ray/Box Intersection, by Graham Fyffe
43  *  [http://tog.acm.org/resources/RTNews/html/rtnv21n1.html#art9]
44  */
45 int RE_rayobject_bb_intersect_test(const Isect *isec, const float *_bb)
46 {
47         const float *bb = _bb;
48         
49         float t1x = (bb[isec->bv_index[0]] - isec->start[0]) * isec->idot_axis[0];
50         float t2x = (bb[isec->bv_index[1]] - isec->start[0]) * isec->idot_axis[0];
51         float t1y = (bb[isec->bv_index[2]] - isec->start[1]) * isec->idot_axis[1];
52         float t2y = (bb[isec->bv_index[3]] - isec->start[1]) * isec->idot_axis[1];
53         float t1z = (bb[isec->bv_index[4]] - isec->start[2]) * isec->idot_axis[2];
54         float t2z = (bb[isec->bv_index[5]] - isec->start[2]) * isec->idot_axis[2];
55
56         RE_RC_COUNT(isec->raycounter->bb.test);
57         
58         if(t1x > t2y || t2x < t1y || t1x > t2z || t2x < t1z || t1y > t2z || t2y < t1z) return 0;
59         if(t2x < 0.0 || t2y < 0.0 || t2z < 0.0) return 0;
60         if(t1x > isec->labda || t1y > isec->labda || t1z > isec->labda) return 0;
61         RE_RC_COUNT(isec->raycounter->bb.hit);  
62
63         return 1;
64 }
65
66
67 /* only for self-intersecting test with current render face (where ray left) */
68 static int intersection2(VlakRen *face, float r0, float r1, float r2, float rx1, float ry1, float rz1)
69 {
70         float co1[3], co2[3], co3[3], co4[3];
71         float x0,x1,x2,t00,t01,t02,t10,t11,t12,t20,t21,t22;
72         float m0, m1, m2, divdet, det, det1;
73         float u1, v, u2;
74
75         VECCOPY(co1, face->v1->co);
76         VECCOPY(co2, face->v2->co);
77         if(face->v4)
78         {
79                 VECCOPY(co3, face->v4->co);
80                 VECCOPY(co4, face->v3->co);
81         }
82         else
83         {
84                 VECCOPY(co3, face->v3->co);
85         }
86
87         t00= co3[0]-co1[0];
88         t01= co3[1]-co1[1];
89         t02= co3[2]-co1[2];
90         t10= co3[0]-co2[0];
91         t11= co3[1]-co2[1];
92         t12= co3[2]-co2[2];
93         
94         x0= t11*r2-t12*r1;
95         x1= t12*r0-t10*r2;
96         x2= t10*r1-t11*r0;
97
98         divdet= t00*x0+t01*x1+t02*x2;
99
100         m0= rx1-co3[0];
101         m1= ry1-co3[1];
102         m2= rz1-co3[2];
103         det1= m0*x0+m1*x1+m2*x2;
104         
105         if(divdet!=0.0f) {
106                 u1= det1/divdet;
107
108                 if(u1<ISECT_EPSILON) {
109                         det= t00*(m1*r2-m2*r1);
110                         det+= t01*(m2*r0-m0*r2);
111                         det+= t02*(m0*r1-m1*r0);
112                         v= det/divdet;
113
114                         if(v<ISECT_EPSILON && (u1 + v) > -(1.0f+ISECT_EPSILON)) {
115                                 return 1;
116                         }
117                 }
118         }
119
120         if(face->v4) {
121
122                 t20= co3[0]-co4[0];
123                 t21= co3[1]-co4[1];
124                 t22= co3[2]-co4[2];
125
126                 divdet= t20*x0+t21*x1+t22*x2;
127                 if(divdet!=0.0f) {
128                         u2= det1/divdet;
129                 
130                         if(u2<ISECT_EPSILON) {
131                                 det= t20*(m1*r2-m2*r1);
132                                 det+= t21*(m2*r0-m0*r2);
133                                 det+= t22*(m0*r1-m1*r0);
134                                 v= det/divdet;
135         
136                                 if(v<ISECT_EPSILON && (u2 + v) >= -(1.0f+ISECT_EPSILON)) {
137                                         return 2;
138                                 }
139                         }
140                 }
141         }
142         return 0;
143 }
144
145 static inline 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 inline 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 static inline int vlr_check_bake(Isect *is, ObjectInstanceRen* obi, VlakRen *vlr)
169 {
170         return (obi->obr->ob != is->userdata);
171 }
172
173 static inline int rayface_check_cullface(RayFace *face, Isect *is)
174 {
175         float nor[3];
176         
177         /* don't intersect if the ray faces along the face normal */
178         if(face->quad) normal_quad_v3( nor,face->v1, face->v2, face->v3, face->v4);
179         else normal_tri_v3( nor,face->v1, face->v2, face->v3);
180
181         return (INPR(nor, is->vec) < 0);
182 }
183
184 /* ray - triangle or quad intersection */
185 /* this function shall only modify Isect if it detects an hit */
186 static int intersect_rayface(RayObject *hit_obj, RayFace *face, Isect *is)
187 {
188         float co1[3],co2[3],co3[3],co4[3]={0};
189         float x0,x1,x2,t00,t01,t02,t10,t11,t12,t20,t21,t22,r0,r1,r2;
190         float m0, m1, m2, divdet, det1;
191         float labda, u, v;
192         short ok=0;
193         
194         if(is->orig.ob == face->ob && is->orig.face == face->face)
195                 return 0;
196                 
197         /* check if we should intersect this face */
198         if(is->skip & RE_SKIP_VLR_RENDER_CHECK)
199         {
200                 if(vlr_check_intersect(is, (ObjectInstanceRen*)face->ob, (VlakRen*)face->face ) == 0)
201                         return 0;
202         }
203         else if(is->skip & RE_SKIP_VLR_NON_SOLID_MATERIAL)
204         {
205                 if(vlr_check_intersect(is, (ObjectInstanceRen*)face->ob, (VlakRen*)face->face ) == 0)
206                         return 0;
207                 if(vlr_check_intersect_solid(is, (ObjectInstanceRen*)face->ob, (VlakRen*)face->face) == 0)
208                         return 0;
209         }
210         else if(is->skip & RE_SKIP_VLR_BAKE_CHECK) {
211                 if(vlr_check_bake(is, (ObjectInstanceRen*)face->ob, (VlakRen*)face->face ) == 0)
212                         return 0;
213         }
214
215         if(is->skip & RE_SKIP_CULLFACE)
216         {
217                 if(rayface_check_cullface(face, is) == 0)
218                         return 0;
219         }
220
221         RE_RC_COUNT(is->raycounter->faces.test);
222
223         //Load coords
224         VECCOPY(co1, face->v1);
225         VECCOPY(co2, face->v2);
226         if(RE_rayface_isQuad(face))
227         {
228                 VECCOPY(co3, face->v4);
229                 VECCOPY(co4, face->v3);
230         }
231         else
232         {
233                 VECCOPY(co3, face->v3);
234         }
235
236         t00= co3[0]-co1[0];
237         t01= co3[1]-co1[1];
238         t02= co3[2]-co1[2];
239         t10= co3[0]-co2[0];
240         t11= co3[1]-co2[1];
241         t12= co3[2]-co2[2];
242         
243         r0= is->vec[0];
244         r1= is->vec[1];
245         r2= is->vec[2];
246         
247         x0= t12*r1-t11*r2;
248         x1= t10*r2-t12*r0;
249         x2= t11*r0-t10*r1;
250
251         divdet= t00*x0+t01*x1+t02*x2;
252
253         m0= is->start[0]-co3[0];
254         m1= is->start[1]-co3[1];
255         m2= is->start[2]-co3[2];
256         det1= m0*x0+m1*x1+m2*x2;
257         
258         if(divdet!=0.0f) {
259
260                 divdet= 1.0f/divdet;
261                 u= det1*divdet;
262                 if(u<ISECT_EPSILON && u>-(1.0f+ISECT_EPSILON)) {
263                         float cros0, cros1, cros2;
264                         
265                         cros0= m1*t02-m2*t01;
266                         cros1= m2*t00-m0*t02;
267                         cros2= m0*t01-m1*t00;
268                         v= divdet*(cros0*r0 + cros1*r1 + cros2*r2);
269
270                         if(v<ISECT_EPSILON && (u + v) > -(1.0f+ISECT_EPSILON)) {
271                                 labda= divdet*(cros0*t10 + cros1*t11 + cros2*t12);
272
273                                 if(labda>-ISECT_EPSILON && labda<is->labda) {
274                                         ok= 1;
275                                 }
276                         }
277                 }
278         }
279
280         if(ok==0 && RE_rayface_isQuad(face)) {
281
282                 t20= co3[0]-co4[0];
283                 t21= co3[1]-co4[1];
284                 t22= co3[2]-co4[2];
285
286                 divdet= t20*x0+t21*x1+t22*x2;
287                 if(divdet!=0.0f) {
288                         divdet= 1.0f/divdet;
289                         u = det1*divdet;
290                         
291                         if(u<ISECT_EPSILON && u>-(1.0f+ISECT_EPSILON)) {
292                                 float cros0, cros1, cros2;
293                                 cros0= m1*t22-m2*t21;
294                                 cros1= m2*t20-m0*t22;
295                                 cros2= m0*t21-m1*t20;
296                                 v= divdet*(cros0*r0 + cros1*r1 + cros2*r2);
297         
298                                 if(v<ISECT_EPSILON && (u + v) >-(1.0f+ISECT_EPSILON)) {
299                                         labda= divdet*(cros0*t10 + cros1*t11 + cros2*t12);
300                                         
301                                         if(labda>-ISECT_EPSILON && labda<is->labda) {
302                                                 ok= 2;
303                                         }
304                                 }
305                         }
306                 }
307         }
308
309         if(ok) {
310         
311                 /* when a shadow ray leaves a face, it can be little outside the edges of it, causing
312                 intersection to be detected in its neighbour face */
313                 if(is->skip & RE_SKIP_VLR_NEIGHBOUR)
314                 {
315                         if(labda < 0.1f && is->orig.ob == face->ob)
316                         {
317                                 VlakRen * a = (VlakRen*)is->orig.face;
318                                 VlakRen * b = (VlakRen*)face->face;
319
320                                 /* so there's a shared edge or vertex, let's intersect ray with face
321                                 itself, if that's true we can safely return 1, otherwise we assume
322                                 the intersection is invalid, 0 */
323                                 if(a->v1==b->v1 || a->v2==b->v1 || a->v3==b->v1 || a->v4==b->v1
324                                 || a->v1==b->v2 || a->v2==b->v2 || a->v3==b->v2 || a->v4==b->v2
325                                 || a->v1==b->v3 || a->v2==b->v3 || a->v3==b->v3 || a->v4==b->v3
326                                 || (b->v4 && (a->v1==b->v4 || a->v2==b->v4 || a->v3==b->v4 || a->v4==b->v4)))
327                                 if(!intersection2((VlakRen*)a, -r0, -r1, -r2, is->start[0], is->start[1], is->start[2]))
328                                 {
329                                         return 0;
330                                 }
331                         }
332                 }
333
334                 RE_RC_COUNT(is->raycounter->faces.hit);
335
336                 is->isect= ok;  // which half of the quad
337                 is->labda= labda;
338                 is->u= u; is->v= v;
339
340                 is->hit.ob   = face->ob;
341                 is->hit.face = face->face;
342 #ifdef RT_USE_LAST_HIT
343                 is->last_hit = hit_obj;
344 #endif
345                 return 1;
346         }
347
348         return 0;
349 }
350
351 RayObject* RE_rayface_from_vlak(RayFace *rayface, ObjectInstanceRen *obi, VlakRen *vlr)
352 {
353         return RE_rayface_from_coords(rayface, obi, vlr, vlr->v1->co, vlr->v2->co, vlr->v3->co, vlr->v4 ? vlr->v4->co : 0 );
354 }
355
356 RayObject* RE_rayface_from_coords(RayFace *rayface, void *ob, void *face, float *v1, float *v2, float *v3, float *v4)
357 {
358         rayface->ob = ob;
359         rayface->face = face;
360
361         VECCOPY(rayface->v1, v1);
362         VECCOPY(rayface->v2, v2);
363         VECCOPY(rayface->v3, v3);
364         if(v4)
365         {
366                 VECCOPY(rayface->v4, v4);
367                 rayface->quad = 1;
368         }
369         else
370         {
371                 rayface->quad = 0;
372         }
373
374         return RE_rayobject_unalignRayFace(rayface);
375 }
376
377 RayObject* RE_vlakprimitive_from_vlak(VlakPrimitive *face, struct ObjectInstanceRen *obi, struct VlakRen *vlr)
378 {
379         face->ob = obi;
380         face->face = vlr;
381         return RE_rayobject_unalignVlakPrimitive(face);
382 }
383
384
385 int RE_rayobject_raycast(RayObject *r, Isect *isec)
386 {
387         int i;
388         RE_RC_COUNT(isec->raycounter->raycast.test);
389
390         /* Setup vars used on raycast */
391         isec->dist = len_v3(isec->vec);
392         
393         for(i=0; i<3; i++)
394         {
395                 isec->idot_axis[i]              = 1.0f / isec->vec[i];
396                 
397                 isec->bv_index[2*i]             = isec->idot_axis[i] < 0.0 ? 1 : 0;
398                 isec->bv_index[2*i+1]   = 1 - isec->bv_index[2*i];
399                 
400                 isec->bv_index[2*i]             = i+3*isec->bv_index[2*i];
401                 isec->bv_index[2*i+1]   = i+3*isec->bv_index[2*i+1];
402         }
403
404 #ifdef RT_USE_LAST_HIT  
405         /* Last hit heuristic */
406         if(isec->mode==RE_RAY_SHADOW && isec->last_hit)
407         {
408                 RE_RC_COUNT(isec->raycounter->rayshadow_last_hit.test);
409                 
410                 if(RE_rayobject_intersect(isec->last_hit, isec))
411                 {
412                         RE_RC_COUNT(isec->raycounter->raycast.hit);
413                         RE_RC_COUNT(isec->raycounter->rayshadow_last_hit.hit);
414                         return 1;
415                 }
416         }
417 #endif
418
419 #ifdef RT_USE_HINT
420         isec->hit_hint = 0;
421 #endif
422
423         if(RE_rayobject_intersect(r, isec))
424         {
425                 RE_RC_COUNT(isec->raycounter->raycast.hit);
426
427 #ifdef RT_USE_HINT
428                 isec->hint = isec->hit_hint;
429 #endif
430                 return 1;
431         }
432         return 0;
433 }
434
435 int RE_rayobject_intersect(RayObject *r, Isect *i)
436 {
437         if(RE_rayobject_isRayFace(r))
438         {
439                 return intersect_rayface(r, (RayFace*) RE_rayobject_align(r), i);
440         }
441         else if(RE_rayobject_isVlakPrimitive(r))
442         {
443                 //TODO optimize (useless copy to RayFace to avoid duplicate code)
444                 VlakPrimitive *face = (VlakPrimitive*) RE_rayobject_align(r);
445                 RayFace nface;
446                 RE_rayface_from_vlak(&nface, face->ob, face->face);
447
448                 if(face->ob->transform_primitives)
449                 {
450                         mul_m4_v3(face->ob->mat, nface.v1);
451                         mul_m4_v3(face->ob->mat, nface.v2);
452                         mul_m4_v3(face->ob->mat, nface.v3);
453                         if(RE_rayface_isQuad(&nface))
454                                 mul_m4_v3(face->ob->mat, nface.v4);
455                 }
456
457                 return intersect_rayface(r, &nface, i);
458         }
459         else if(RE_rayobject_isRayAPI(r))
460         {
461                 r = RE_rayobject_align( r );
462                 return r->api->raycast( r, i );
463         }
464         else assert(0);
465     return 0; /* wont reach this, quiet compilers */
466 }
467
468 void RE_rayobject_add(RayObject *r, RayObject *o)
469 {
470         r = RE_rayobject_align( r );
471         return r->api->add( r, o );
472 }
473
474 void RE_rayobject_done(RayObject *r)
475 {
476         r = RE_rayobject_align( r );
477         r->api->done( r );
478 }
479
480 void RE_rayobject_free(RayObject *r)
481 {
482         r = RE_rayobject_align( r );
483         r->api->free( r );
484 }
485
486 void RE_rayobject_merge_bb(RayObject *r, float *min, float *max)
487 {
488         if(RE_rayobject_isRayFace(r))
489         {
490                 RayFace *face = (RayFace*) RE_rayobject_align(r);
491                 
492                 DO_MINMAX( face->v1, min, max );
493                 DO_MINMAX( face->v2, min, max );
494                 DO_MINMAX( face->v3, min, max );
495                 if(RE_rayface_isQuad(face)) DO_MINMAX( face->v4, min, max );
496         }
497         else if(RE_rayobject_isVlakPrimitive(r))
498         {
499                 VlakPrimitive *face = (VlakPrimitive*) RE_rayobject_align(r);
500                 RayFace nface;
501                 RE_rayface_from_vlak(&nface, face->ob, face->face);
502
503                 if(face->ob->transform_primitives)
504                 {
505                         mul_m4_v3(face->ob->mat, nface.v1);
506                         mul_m4_v3(face->ob->mat, nface.v2);
507                         mul_m4_v3(face->ob->mat, nface.v3);
508                         if(RE_rayface_isQuad(&nface))
509                                 mul_m4_v3(face->ob->mat, nface.v4);
510                 }
511
512                 DO_MINMAX( nface.v1, min, max );
513                 DO_MINMAX( nface.v2, min, max );
514                 DO_MINMAX( nface.v3, min, max );
515                 if(RE_rayface_isQuad(&nface)) DO_MINMAX( nface.v4, min, max );
516         }
517         else if(RE_rayobject_isRayAPI(r))
518         {
519                 r = RE_rayobject_align( r );
520                 r->api->bb( r, min, max );
521         }
522         else assert(0);
523 }
524
525 float RE_rayobject_cost(RayObject *r)
526 {
527         if(RE_rayobject_isRayFace(r) || RE_rayobject_isVlakPrimitive(r))
528         {
529                 return 1.0;
530         }
531         else if(RE_rayobject_isRayAPI(r))
532         {
533                 r = RE_rayobject_align( r );
534                 return r->api->cost( r );
535         }
536         else
537         {
538                 assert(0);
539                 return 1.0; /* XXX, better default value? */
540         }
541 }
542
543 void RE_rayobject_hint_bb(RayObject *r, RayHint *hint, float *min, float *max)
544 {
545         if(RE_rayobject_isRayFace(r) || RE_rayobject_isVlakPrimitive(r))
546         {
547                 return;
548         }
549         else if(RE_rayobject_isRayAPI(r))
550         {
551                 r = RE_rayobject_align( r );
552                 return r->api->hint_bb( r, hint, min, max );
553         }
554         else assert(0);
555 }
556
557 int RE_rayobjectcontrol_test_break(RayObjectControl *control)
558 {
559         if(control->test_break)
560                 return control->test_break( control->data );
561
562         return 0;
563 }
564
565
566 /*
567  * Empty raytree
568  */
569 static int RE_rayobject_empty_intersect(RayObject *o, Isect *is)
570 {
571         return 0;
572 }
573
574 static void RE_rayobject_empty_free(RayObject *o)
575 {
576 }
577
578 static void RE_rayobject_empty_bb(RayObject *o, float *min, float *max)
579 {
580         return;
581 }
582
583 static float RE_rayobject_empty_cost(RayObject *o)
584 {
585         return 0.0;
586 }
587
588 static void RE_rayobject_empty_hint_bb(RayObject *o, RayHint *hint, float *min, float *max)
589 {}
590
591 static RayObjectAPI empty_api =
592 {
593         RE_rayobject_empty_intersect,
594         NULL, //static void RE_rayobject_instance_add(RayObject *o, RayObject *ob);
595         NULL, //static void RE_rayobject_instance_done(RayObject *o);
596         RE_rayobject_empty_free,
597         RE_rayobject_empty_bb,
598         RE_rayobject_empty_cost,
599         RE_rayobject_empty_hint_bb
600 };
601
602 static RayObject empty_raytree = { &empty_api, {0, 0} };
603
604 RayObject *RE_rayobject_empty_create()
605 {
606         return RE_rayobject_unalignRayAPI( &empty_raytree );
607 }