#define to store coordinates at VlakRen and not at VlakFace
[blender-staging.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 #include <stdio.h>
31
32 #include "BKE_utildefines.h"
33 #include "BLI_arithb.h"
34
35 #include "RE_raytrace.h"
36 #include "render_types.h"
37 #include "rayobject.h"
38
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 float RE_rayobject_bb_intersect(const Isect *isec, const float *_bb)
46 {
47         const float *bb = _bb;
48         float dist;
49         
50         float t1x = (bb[isec->bv_index[0]] - isec->start[0]) * isec->idot_axis[0];
51         float t2x = (bb[isec->bv_index[1]] - isec->start[0]) * isec->idot_axis[0];
52         float t1y = (bb[isec->bv_index[2]] - isec->start[1]) * isec->idot_axis[1];
53         float t2y = (bb[isec->bv_index[3]] - isec->start[1]) * isec->idot_axis[1];
54         float t1z = (bb[isec->bv_index[4]] - isec->start[2]) * isec->idot_axis[2];
55         float t2z = (bb[isec->bv_index[5]] - isec->start[2]) * isec->idot_axis[2];
56
57         RE_RC_COUNT(isec->raycounter->bb.test);
58
59         if(t1x > t2y || t2x < t1y || t1x > t2z || t2x < t1z || t1y > t2z || t2y < t1z) return FLT_MAX;
60         if(t2x < 0.0 || t2y < 0.0 || t2z < 0.0) return FLT_MAX;
61         if(t1x > isec->labda || t1y > isec->labda || t1z > isec->labda) return FLT_MAX;
62
63         RE_RC_COUNT(isec->raycounter->bb.hit);
64
65         dist = t1x;
66         if (t1y > dist) dist = t1y;
67     if (t1z > dist) dist = t1z;
68         return dist;
69 }
70
71
72 /* only for self-intersecting test with current render face (where ray left) */
73 static int intersection2(VlakRen *face, float r0, float r1, float r2, float rx1, float ry1, float rz1)
74 {
75         float co1[3], co2[3], co3[3], co4[3];
76         float x0,x1,x2,t00,t01,t02,t10,t11,t12,t20,t21,t22;
77         float m0, m1, m2, divdet, det, det1;
78         float u1, v, u2;
79
80         VECCOPY(co1, face->v1->co);
81         VECCOPY(co2, face->v2->co);
82         if(face->v4)
83         {
84                 VECCOPY(co3, face->v4->co);
85                 VECCOPY(co4, face->v3->co);
86         }
87         else
88         {
89                 VECCOPY(co3, face->v3->co);
90         }
91
92         t00= co3[0]-co1[0];
93         t01= co3[1]-co1[1];
94         t02= co3[2]-co1[2];
95         t10= co3[0]-co2[0];
96         t11= co3[1]-co2[1];
97         t12= co3[2]-co2[2];
98         
99         x0= t11*r2-t12*r1;
100         x1= t12*r0-t10*r2;
101         x2= t10*r1-t11*r0;
102
103         divdet= t00*x0+t01*x1+t02*x2;
104
105         m0= rx1-co3[0];
106         m1= ry1-co3[1];
107         m2= rz1-co3[2];
108         det1= m0*x0+m1*x1+m2*x2;
109         
110         if(divdet!=0.0f) {
111                 u1= det1/divdet;
112
113                 if(u1<ISECT_EPSILON) {
114                         det= t00*(m1*r2-m2*r1);
115                         det+= t01*(m2*r0-m0*r2);
116                         det+= t02*(m0*r1-m1*r0);
117                         v= det/divdet;
118
119                         if(v<ISECT_EPSILON && (u1 + v) > -(1.0f+ISECT_EPSILON)) {
120                                 return 1;
121                         }
122                 }
123         }
124
125         if(face->v4) {
126
127                 t20= co3[0]-co4[0];
128                 t21= co3[1]-co4[1];
129                 t22= co3[2]-co4[2];
130
131                 divdet= t20*x0+t21*x1+t22*x2;
132                 if(divdet!=0.0f) {
133                         u2= det1/divdet;
134                 
135                         if(u2<ISECT_EPSILON) {
136                                 det= t20*(m1*r2-m2*r1);
137                                 det+= t21*(m2*r0-m0*r2);
138                                 det+= t22*(m0*r1-m1*r0);
139                                 v= det/divdet;
140         
141                                 if(v<ISECT_EPSILON && (u2 + v) >= -(1.0f+ISECT_EPSILON)) {
142                                         return 2;
143                                 }
144                         }
145                 }
146         }
147         return 0;
148 }
149
150
151 /* ray - triangle or quad intersection */
152 /* this function shall only modify Isect if it detects an hit */
153 static int intersect_rayface(RayFace *face, Isect *is)
154 {
155         float co1[3],co2[3],co3[3],co4[3];
156         float x0,x1,x2,t00,t01,t02,t10,t11,t12,t20,t21,t22,r0,r1,r2;
157         float m0, m1, m2, divdet, det1;
158         float labda, u, v;
159         short ok=0;
160         
161         if(is->orig.ob == face->ob && is->orig.face == face->face)
162                 return 0;
163
164         RE_RC_COUNT(is->raycounter->faces.test);
165
166 #ifdef RE_RAYFACE_COORDS_VLAKREN
167         {
168                 VlakRen *vlr = (VlakRen*)face->face;
169                 VECCOPY(co1, vlr->v1->co);
170                 VECCOPY(co2, vlr->v2->co);
171                 if(vlr->v4)
172                 {
173                         VECCOPY(co3, vlr->v4->co);
174                         VECCOPY(co4, vlr->v3->co);
175                 }
176                 else
177                 {
178                         VECCOPY(co3, vlr->v3->co);
179                 }
180         }
181 #else
182         VECCOPY(co1, face->v1);
183         VECCOPY(co2, face->v2);
184         if(RE_rayface_isQuad(face))
185         {
186                 VECCOPY(co3, face->v4);
187                 VECCOPY(co4, face->v3);
188         }
189         else
190         {
191                 VECCOPY(co3, face->v3);
192         }
193 #endif
194
195         t00= co3[0]-co1[0];
196         t01= co3[1]-co1[1];
197         t02= co3[2]-co1[2];
198         t10= co3[0]-co2[0];
199         t11= co3[1]-co2[1];
200         t12= co3[2]-co2[2];
201         
202         r0= is->vec[0];
203         r1= is->vec[1];
204         r2= is->vec[2];
205         
206         x0= t12*r1-t11*r2;
207         x1= t10*r2-t12*r0;
208         x2= t11*r0-t10*r1;
209
210         divdet= t00*x0+t01*x1+t02*x2;
211
212         m0= is->start[0]-co3[0];
213         m1= is->start[1]-co3[1];
214         m2= is->start[2]-co3[2];
215         det1= m0*x0+m1*x1+m2*x2;
216         
217         if(divdet!=0.0f) {
218
219                 divdet= 1.0f/divdet;
220                 u= det1*divdet;
221                 if(u<ISECT_EPSILON && u>-(1.0f+ISECT_EPSILON)) {
222                         float cros0, cros1, cros2;
223                         
224                         cros0= m1*t02-m2*t01;
225                         cros1= m2*t00-m0*t02;
226                         cros2= m0*t01-m1*t00;
227                         v= divdet*(cros0*r0 + cros1*r1 + cros2*r2);
228
229                         if(v<ISECT_EPSILON && (u + v) > -(1.0f+ISECT_EPSILON)) {
230                                 labda= divdet*(cros0*t10 + cros1*t11 + cros2*t12);
231
232                                 if(labda>-ISECT_EPSILON && labda<is->labda) {
233                                         ok= 1;
234                                 }
235                         }
236                 }
237         }
238
239         if(ok==0 && RE_rayface_isQuad(face)) {
240
241                 t20= co3[0]-co4[0];
242                 t21= co3[1]-co4[1];
243                 t22= co3[2]-co4[2];
244
245                 divdet= t20*x0+t21*x1+t22*x2;
246                 if(divdet!=0.0f) {
247                         divdet= 1.0f/divdet;
248                         u = det1*divdet;
249                         
250                         if(u<ISECT_EPSILON && u>-(1.0f+ISECT_EPSILON)) {
251                                 float cros0, cros1, cros2;
252                                 cros0= m1*t22-m2*t21;
253                                 cros1= m2*t20-m0*t22;
254                                 cros2= m0*t21-m1*t20;
255                                 v= divdet*(cros0*r0 + cros1*r1 + cros2*r2);
256         
257                                 if(v<ISECT_EPSILON && (u + v) >-(1.0f+ISECT_EPSILON)) {
258                                         labda= divdet*(cros0*t10 + cros1*t11 + cros2*t12);
259                                         
260                                         if(labda>-ISECT_EPSILON && labda<is->labda) {
261                                                 ok= 2;
262                                         }
263                                 }
264                         }
265                 }
266         }
267
268         if(ok) {
269         
270                 /* when a shadow ray leaves a face, it can be little outside the edges of it, causing
271                 intersection to be detected in its neighbour face */
272                 if(is->skip & RE_SKIP_VLR_NEIGHBOUR)
273                 {
274                         if(labda < 0.1f && is->orig.ob == face->ob)
275                         {
276                                 VlakRen * a = is->orig.face;
277                                 VlakRen * b = face->face;
278
279                                 /* so there's a shared edge or vertex, let's intersect ray with face
280                                 itself, if that's true we can safely return 1, otherwise we assume
281                                 the intersection is invalid, 0 */
282                                 if(a->v1==b->v1 || a->v2==b->v1 || a->v3==b->v1 || a->v4==b->v1
283                                 || a->v1==b->v2 || a->v2==b->v2 || a->v3==b->v2 || a->v4==b->v2
284                                 || a->v1==b->v3 || a->v2==b->v3 || a->v3==b->v3 || a->v4==b->v3
285                                 || (b->v4 && (a->v1==b->v4 || a->v2==b->v4 || a->v3==b->v4 || a->v4==b->v4)))
286                                 if(intersection2((VlakRen*)b, -r0, -r1, -r2, is->start[0], is->start[1], is->start[2]))
287                                 {
288                                         return 0;
289                                 }
290                         }
291                 }
292 #if 0
293                 else if(labda < ISECT_EPSILON)
294                 {
295                         /* too close to origin */
296                         return 0;
297                 }
298 #endif
299
300                 RE_RC_COUNT(is->raycounter->faces.hit);
301
302                 is->isect= ok;  // wich half of the quad
303                 is->labda= labda;
304                 is->u= u; is->v= v;
305
306                 is->hit.ob   = face->ob;
307                 is->hit.face = face->face;
308 #ifdef RT_USE_LAST_HIT
309                 is->last_hit = (RayObject*) RayObject_unalignRayFace(face);
310 #endif
311                 return 1;
312         }
313
314         return 0;
315 }
316
317 void RE_rayface_from_vlak(RayFace *face, ObjectInstanceRen *obi, VlakRen *vlr)
318 {
319 #ifdef RE_RAYFACE_COORDS_LOCAL
320         VECCOPY(face->v1, vlr->v1->co);
321         VECCOPY(face->v2, vlr->v2->co);
322         VECCOPY(face->v3, vlr->v3->co);
323         if(vlr->v4)
324         {
325                 VECCOPY(face->v4, vlr->v4->co);
326                 face->quad = 1;
327         }
328         else
329         {
330                 face->quad = 0;
331         }
332 #elif defined(RE_RAYFACE_COORDS_POINTER)
333         face->v1 = vlr->v1->co;
334         face->v2 = vlr->v2->co;
335         face->v3 = vlr->v3->co;
336         face->v4 = vlr->v4 ? vlr->v4->co : NULL;
337 #elif defined(RE_RAYFACE_COORDS_VLAKREN)
338 #endif
339         face->ob   = obi;
340         face->face = vlr;
341 }
342
343
344 int RE_rayobject_raycast(RayObject *r, Isect *isec)
345 {
346         int i;
347         RE_RC_COUNT(isec->raycounter->raycast.test);
348
349         /* Setup vars used on raycast */
350         isec->labda *= Normalize(isec->vec);
351         isec->dist = VecLength(isec->vec);
352         
353         for(i=0; i<3; i++)
354         {
355                 isec->idot_axis[i]              = 1.0f / isec->vec[i];
356                 
357                 isec->bv_index[2*i]             = isec->idot_axis[i] < 0.0 ? 1 : 0;
358                 isec->bv_index[2*i+1]   = 1 - isec->bv_index[2*i];
359                 
360                 isec->bv_index[2*i]             = i+3*isec->bv_index[2*i];
361                 isec->bv_index[2*i+1]   = i+3*isec->bv_index[2*i+1];
362         }
363
364 #ifdef RT_USE_LAST_HIT  
365         /* Last hit heuristic */
366         if(isec->mode==RE_RAY_SHADOW && isec->last_hit)
367         {
368                 RE_RC_COUNT(isec->raycounter->rayshadow_last_hit.test);
369                 
370                 if(RE_rayobject_intersect(isec->last_hit, isec))
371                 {
372                         RE_RC_COUNT(isec->raycounter->raycast.hit);
373                         RE_RC_COUNT(isec->raycounter->rayshadow_last_hit.hit);
374                         return 1;
375                 }
376         }
377 #endif
378
379 #ifdef RT_USE_HINT
380         isec->hit_hint = 0;
381 #endif
382
383         if(RE_rayobject_intersect(r, isec))
384         {
385 #ifdef RE_RAYCOUNTER
386                 RE_RC_COUNT(isec->raycounter->raycast.hit);
387 #endif
388
389 #ifdef RT_USE_HINT
390                 isec->hint = isec->hit_hint;
391 #endif
392                 return 1;
393         }
394         return 0;
395 }
396
397 int RE_rayobject_intersect(RayObject *r, Isect *i)
398 {
399         if(RayObject_isRayFace(r))
400         {
401                 return intersect_rayface( (RayFace*) RayObject_align(r), i);
402         }
403         else if(RayObject_isRayAPI(r))
404         {
405                 r = RayObject_align( r );
406                 return r->api->raycast( r, i );
407         }
408         else assert(0);
409 }
410
411 void RE_rayobject_add(RayObject *r, RayObject *o)
412 {
413         r = RayObject_align( r );
414         return r->api->add( r, o );
415 }
416
417 void RE_rayobject_done(RayObject *r)
418 {
419         r = RayObject_align( r );
420         r->api->done( r );
421 }
422
423 void RE_rayobject_free(RayObject *r)
424 {
425         r = RayObject_align( r );
426         r->api->free( r );
427 }
428
429 void RE_rayobject_merge_bb(RayObject *r, float *min, float *max)
430 {
431         if(RayObject_isRayFace(r))
432         {
433                 RayFace *face = (RayFace*) RayObject_align(r);
434                 
435 #ifdef RE_RAYFACE_COORDS_VLAKREN
436                 VlakRen *vlr = (VlakRen*)face->face;
437                 DO_MINMAX( vlr->v1->co, min, max );
438                 DO_MINMAX( vlr->v2->co, min, max );
439                 DO_MINMAX( vlr->v3->co, min, max );
440                 if(RE_rayface_isQuad(face)) DO_MINMAX( vlr->v4->co, min, max );
441 #else
442                 DO_MINMAX( face->v1, min, max );
443                 DO_MINMAX( face->v2, min, max );
444                 DO_MINMAX( face->v3, min, max );
445                 if(RE_rayface_isQuad(face)) DO_MINMAX( face->v4, min, max );
446 #endif
447         }
448         else if(RayObject_isRayAPI(r))
449         {
450                 r = RayObject_align( r );
451                 r->api->bb( r, min, max );
452         }
453         else assert(0);
454 }
455
456 float RE_rayobject_cost(RayObject *r)
457 {
458         if(RayObject_isRayFace(r))
459         {
460                 return 1.0;
461         }
462         else if(RayObject_isRayAPI(r))
463         {
464                 r = RayObject_align( r );
465                 return r->api->cost( r );
466         }
467         else assert(0);
468 }
469
470 void RE_rayobject_hint_bb(RayObject *r, RayHint *hint, float *min, float *max)
471 {
472         if(RayObject_isRayFace(r))
473         {
474                 return;
475         }
476         else if(RayObject_isRayAPI(r))
477         {
478                 r = RayObject_align( r );
479                 return r->api->hint_bb( r, hint, min, max );
480         }
481         else assert(0);
482 }
483
484 #ifdef RE_RAYCOUNTER
485 void RE_RC_INFO(RayCounter *info)
486 {
487         printf("----------- Raycast counter --------\n");
488         printf("Rays total: %llu\n", info->raycast.test );
489         printf("Rays hit: %llu\n",   info->raycast.hit  );
490         printf("\n");
491         printf("BB tests: %llu\n", info->bb.test );
492         printf("BB hits: %llu\n", info->bb.hit );
493         printf("\n");   
494         printf("Primitives tests: %llu\n", info->faces.test );
495         printf("Primitives hits: %llu\n", info->faces.hit );
496         printf("------------------------------------\n");
497         printf("Shadow last-hit tests per ray: %f\n", info->rayshadow_last_hit.test / ((float)info->raycast.test) );
498         printf("Shadow last-hit hits per ray: %f\n",  info->rayshadow_last_hit.hit  / ((float)info->raycast.test) );
499         printf("\n");
500         printf("Hint tests per ray: %f\n", info->raytrace_hint.test / ((float)info->raycast.test) );
501         printf("Hint hits per ray: %f\n",  info->raytrace_hint.hit  / ((float)info->raycast.test) );
502         printf("\n");
503         printf("BB tests per ray: %f\n", info->bb.test / ((float)info->raycast.test) );
504         printf("BB hits per ray: %f\n", info->bb.hit / ((float)info->raycast.test) );
505         printf("\n");
506         printf("Primitives tests per ray: %f\n", info->faces.test / ((float)info->raycast.test) );
507         printf("Primitives hits per ray: %f\n", info->faces.hit / ((float)info->raycast.test) );
508         printf("------------------------------------\n");
509 }
510
511 void RE_RC_MERGE(RayCounter *dest, RayCounter *tmp)
512 {
513         dest->faces.test += tmp->faces.test;
514         dest->faces.hit  += tmp->faces.hit;
515
516         dest->bb.test += tmp->bb.test;
517         dest->bb.hit  += tmp->bb.hit;
518
519         dest->raycast.test += tmp->raycast.test;
520         dest->raycast.hit  += tmp->raycast.hit;
521         
522         dest->rayshadow_last_hit.test += tmp->rayshadow_last_hit.test;
523         dest->rayshadow_last_hit.hit  += tmp->rayshadow_last_hit.hit;
524
525         dest->raytrace_hint.test += tmp->raytrace_hint.test;
526         dest->raytrace_hint.hit  += tmp->raytrace_hint.hit;
527 }
528
529 #endif