doxygen: prevent GPL license block from being parsed as doxygen comment.
[blender.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
30 #include <assert.h>
31
32 #include "MEM_guardedalloc.h"
33
34 #include "BLI_math.h"
35 #include "BLI_utildefines.h"
36
37 #include "DNA_material_types.h"
38
39 #include "rayintersection.h"
40 #include "rayobject.h"
41 #include "raycounter.h"
42 #include "render_types.h"
43
44 /* RayFace
45
46    note we force always inline here, because compiler refuses to otherwise
47    because function is too long. Since this is code that is called billions
48    of times we really do want to inline. */
49
50 MALWAYS_INLINE RayObject* rayface_from_coords(RayFace *rayface, void *ob, void *face, float *v1, float *v2, float *v3, float *v4)
51 {
52         rayface->ob = ob;
53         rayface->face = face;
54
55         copy_v3_v3(rayface->v1, v1);
56         copy_v3_v3(rayface->v2, v2);
57         copy_v3_v3(rayface->v3, v3);
58
59         if(v4)
60         {
61                 copy_v3_v3(rayface->v4, v4);
62                 rayface->quad = 1;
63         }
64         else
65         {
66                 rayface->quad = 0;
67         }
68
69         return RE_rayobject_unalignRayFace(rayface);
70 }
71
72 MALWAYS_INLINE void rayface_from_vlak(RayFace *rayface, ObjectInstanceRen *obi, VlakRen *vlr)
73 {
74         rayface_from_coords(rayface, obi, vlr, vlr->v1->co, vlr->v2->co, vlr->v3->co, vlr->v4 ? vlr->v4->co : 0);
75
76         if(obi->transform_primitives)
77         {
78                 mul_m4_v3(obi->mat, rayface->v1);
79                 mul_m4_v3(obi->mat, rayface->v2);
80                 mul_m4_v3(obi->mat, rayface->v3);
81
82                 if(RE_rayface_isQuad(rayface))
83                         mul_m4_v3(obi->mat, rayface->v4);
84         }
85 }
86
87 RayObject* RE_rayface_from_vlak(RayFace *rayface, ObjectInstanceRen *obi, VlakRen *vlr)
88 {
89         return rayface_from_coords(rayface, obi, vlr, vlr->v1->co, vlr->v2->co, vlr->v3->co, vlr->v4 ? vlr->v4->co : 0);
90 }
91
92 /* VlakPrimitive */
93
94 RayObject* RE_vlakprimitive_from_vlak(VlakPrimitive *face, struct ObjectInstanceRen *obi, struct VlakRen *vlr)
95 {
96         face->ob = obi;
97         face->face = vlr;
98
99         return RE_rayobject_unalignVlakPrimitive(face);
100 }
101
102 /* Checks for ignoring faces or materials */
103
104 MALWAYS_INLINE int vlr_check_intersect(Isect *is, ObjectInstanceRen *obi, VlakRen *vlr)
105 {
106         /* for baking selected to active non-traceable materials might still
107          * be in the raytree */
108         if(!(vlr->flag & R_TRACEBLE))
109                 return 0;
110
111         /* I know... cpu cycle waste, might do smarter once */
112         if(is->mode==RE_RAY_MIRROR)
113                 return !(vlr->mat->mode & MA_ONLYCAST);
114         else
115                 return (is->lay & obi->lay);
116 }
117
118 MALWAYS_INLINE int vlr_check_intersect_solid(Isect *is, ObjectInstanceRen* obi, VlakRen *vlr)
119 {
120         /* solid material types only */
121         if (vlr->mat->material_type == MA_TYPE_SURFACE)
122                 return 1;
123         else
124                 return 0;
125 }
126
127 MALWAYS_INLINE int vlr_check_bake(Isect *is, ObjectInstanceRen* obi, VlakRen *vlr)
128 {
129         return (obi->obr->ob != is->userdata);
130 }
131
132 /* Ray Triangle/Quad Intersection */
133
134 MALWAYS_INLINE int isec_tri_quad(float start[3], float dir[3], RayFace *face, float uv[2], float *lambda)
135 {
136         float co1[3], co2[3], co3[3], co4[3];
137         float t0[3], t1[3], x[3], r[3], m[3], u, v, divdet, det1, l;
138         int quad;
139
140         quad= RE_rayface_isQuad(face);
141
142         copy_v3_v3(co1, face->v1);
143         copy_v3_v3(co2, face->v2);
144         copy_v3_v3(co3, face->v3);
145
146         copy_v3_v3(r, dir);
147
148         /* intersect triangle */
149         sub_v3_v3v3(t0, co3, co2);
150         sub_v3_v3v3(t1, co3, co1);
151
152         cross_v3_v3v3(x, r, t1);
153         divdet= dot_v3v3(t0, x);
154
155         sub_v3_v3v3(m, start, co3);
156         det1= dot_v3v3(m, x);
157         
158         if(divdet != 0.0f) {
159                 divdet= 1.0f/divdet;
160                 v= det1*divdet;
161
162                 if(v < RE_RAYTRACE_EPSILON && v > -(1.0f+RE_RAYTRACE_EPSILON)) {
163                         float cros[3];
164
165                         cross_v3_v3v3(cros, m, t0);
166                         u= divdet*dot_v3v3(cros, r);
167
168                         if(u < RE_RAYTRACE_EPSILON && (v + u) > -(1.0f+RE_RAYTRACE_EPSILON)) {
169                                 l= divdet*dot_v3v3(cros, t1);
170
171                                 /* check if intersection is within ray length */
172                                 if(l > -RE_RAYTRACE_EPSILON && l < *lambda) {
173                                         uv[0]= u;
174                                         uv[1]= v;
175                                         *lambda= l;
176                                         return 1;
177                                 }
178                         }
179                 }
180         }
181
182         /* intersect second triangle in quad */
183         if(quad) {
184                 copy_v3_v3(co4, face->v4);
185                 sub_v3_v3v3(t0, co3, co4);
186                 divdet= dot_v3v3(t0, x);
187
188                 if(divdet != 0.0f) {
189                         divdet= 1.0f/divdet;
190                         v = det1*divdet;
191                         
192                         if(v < RE_RAYTRACE_EPSILON && v > -(1.0f+RE_RAYTRACE_EPSILON)) {
193                                 float cros[3];
194
195                                 cross_v3_v3v3(cros, m, t0);
196                                 u= divdet*dot_v3v3(cros, r);
197         
198                                 if(u < RE_RAYTRACE_EPSILON && (v + u) > -(1.0f+RE_RAYTRACE_EPSILON)) {
199                                         l= divdet*dot_v3v3(cros, t1);
200                                         
201                                         if(l >- RE_RAYTRACE_EPSILON && l < *lambda) {
202                                                 uv[0]= u;
203                                                 uv[1]= -(1.0f + v + u);
204                                                 *lambda= l;
205                                                 return 2;
206                                         }
207                                 }
208                         }
209                 }
210         }
211
212         return 0;
213 }
214
215 /* Simpler yes/no Ray Triangle/Quad Intersection */
216
217 MALWAYS_INLINE int isec_tri_quad_neighbour(float start[3], float dir[3], RayFace *face)
218 {
219         float co1[3], co2[3], co3[3], co4[3];
220         float t0[3], t1[3], x[3], r[3], m[3], u, v, divdet, det1;
221         int quad;
222
223         quad= RE_rayface_isQuad(face);
224
225         copy_v3_v3(co1, face->v1);
226         copy_v3_v3(co2, face->v2);
227         copy_v3_v3(co3, face->v3);
228
229         negate_v3_v3(r, dir); /* note, different than above function */
230
231         /* intersect triangle */
232         sub_v3_v3v3(t0, co3, co2);
233         sub_v3_v3v3(t1, co3, co1);
234
235         cross_v3_v3v3(x, r, t1);
236         divdet= dot_v3v3(t0, x);
237
238         sub_v3_v3v3(m, start, co3);
239         det1= dot_v3v3(m, x);
240         
241         if(divdet != 0.0f) {
242                 divdet= 1.0f/divdet;
243                 v= det1*divdet;
244
245                 if(v < RE_RAYTRACE_EPSILON && v > -(1.0f+RE_RAYTRACE_EPSILON)) {
246                         float cros[3];
247
248                         cross_v3_v3v3(cros, m, t0);
249                         u= divdet*dot_v3v3(cros, r);
250
251                         if(u < RE_RAYTRACE_EPSILON && (v + u) > -(1.0f+RE_RAYTRACE_EPSILON))
252                                 return 1;
253                 }
254         }
255
256         /* intersect second triangle in quad */
257         if(quad) {
258                 copy_v3_v3(co4, face->v4);
259                 sub_v3_v3v3(t0, co3, co4);
260                 divdet= dot_v3v3(t0, x);
261
262                 if(divdet != 0.0f) {
263                         divdet= 1.0f/divdet;
264                         v = det1*divdet;
265                         
266                         if(v < RE_RAYTRACE_EPSILON && v > -(1.0f+RE_RAYTRACE_EPSILON)) {
267                                 float cros[3];
268
269                                 cross_v3_v3v3(cros, m, t0);
270                                 u= divdet*dot_v3v3(cros, r);
271         
272                                 if(u < RE_RAYTRACE_EPSILON && (v + u) > -(1.0f+RE_RAYTRACE_EPSILON))
273                                         return 2;
274                         }
275                 }
276         }
277
278         return 0;
279 }
280
281 /* RayFace intersection with checks and neighbour verifaction included,
282    Isect is modified if the face is hit. */
283
284 MALWAYS_INLINE int intersect_rayface(RayObject *hit_obj, RayFace *face, Isect *is)
285 {
286         float dist, uv[2];
287         int ok= 0;
288         
289         /* avoid self-intersection */
290         if(is->orig.ob == face->ob && is->orig.face == face->face)
291                 return 0;
292                 
293         /* check if we should intersect this face */
294         if(is->check == RE_CHECK_VLR_RENDER)
295         {
296                 if(vlr_check_intersect(is, (ObjectInstanceRen*)face->ob, (VlakRen*)face->face) == 0)
297                         return 0;
298         }
299         else if(is->check == RE_CHECK_VLR_NON_SOLID_MATERIAL)
300         {
301                 if(vlr_check_intersect(is, (ObjectInstanceRen*)face->ob, (VlakRen*)face->face) == 0)
302                         return 0;
303                 if(vlr_check_intersect_solid(is, (ObjectInstanceRen*)face->ob, (VlakRen*)face->face) == 0)
304                         return 0;
305         }
306         else if(is->check == RE_CHECK_VLR_BAKE) {
307                 if(vlr_check_bake(is, (ObjectInstanceRen*)face->ob, (VlakRen*)face->face) == 0)
308                         return 0;
309         }
310
311         /* ray counter */
312         RE_RC_COUNT(is->raycounter->faces.test);
313
314         dist= is->dist;
315         ok= isec_tri_quad(is->start, is->dir, face, uv, &dist);
316
317         if(ok) {
318         
319                 /* when a shadow ray leaves a face, it can be little outside the edges
320                    of it, causing intersection to be detected in its neighbour face */
321                 if(is->skip & RE_SKIP_VLR_NEIGHBOUR)
322                 {
323                         if(dist < 0.1f && is->orig.ob == face->ob)
324                         {
325                                 VlakRen * a = (VlakRen*)is->orig.face;
326                                 VlakRen * b = (VlakRen*)face->face;
327
328                                 /* so there's a shared edge or vertex, let's intersect ray with
329                                    face itself, if that's true we can safely return 1, otherwise
330                                    we assume the intersection is invalid, 0 */
331                                 if(a->v1==b->v1 || a->v2==b->v1 || a->v3==b->v1 || a->v4==b->v1
332                                 || a->v1==b->v2 || a->v2==b->v2 || a->v3==b->v2 || a->v4==b->v2
333                                 || a->v1==b->v3 || a->v2==b->v3 || a->v3==b->v3 || a->v4==b->v3
334                                 || (b->v4 && (a->v1==b->v4 || a->v2==b->v4 || a->v3==b->v4 || a->v4==b->v4))) {
335                                         /* create RayFace from original face, transformed if necessary */
336                                         RayFace origface;
337                                         ObjectInstanceRen *ob= (ObjectInstanceRen*)is->orig.ob;
338                                         rayface_from_vlak(&origface, ob, (VlakRen*)is->orig.face);
339
340                                         if(!isec_tri_quad_neighbour(is->start, is->dir, &origface))
341                                         {
342                                                 return 0;
343                                         }
344                                 }
345                         }
346                 }
347
348                 RE_RC_COUNT(is->raycounter->faces.hit);
349
350                 is->isect= ok;  // which half of the quad
351                 is->dist= dist;
352                 is->u= uv[0]; is->v= uv[1];
353
354                 is->hit.ob   = face->ob;
355                 is->hit.face = face->face;
356 #ifdef RT_USE_LAST_HIT
357                 is->last_hit = hit_obj;
358 #endif
359                 return 1;
360         }
361
362         return 0;
363 }
364
365 /* Intersection */
366
367 int RE_rayobject_raycast(RayObject *r, Isect *isec)
368 {
369         int i;
370
371         RE_RC_COUNT(isec->raycounter->raycast.test);
372
373         /* setup vars used on raycast */
374         for(i=0; i<3; i++)
375         {
376                 isec->idot_axis[i]              = 1.0f / isec->dir[i];
377                 
378                 isec->bv_index[2*i]             = isec->idot_axis[i] < 0.0 ? 1 : 0;
379                 isec->bv_index[2*i+1]   = 1 - isec->bv_index[2*i];
380                 
381                 isec->bv_index[2*i]             = i+3*isec->bv_index[2*i];
382                 isec->bv_index[2*i+1]   = i+3*isec->bv_index[2*i+1];
383         }
384
385 #ifdef RT_USE_LAST_HIT  
386         /* last hit heuristic */
387         if(isec->mode==RE_RAY_SHADOW && isec->last_hit)
388         {
389                 RE_RC_COUNT(isec->raycounter->rayshadow_last_hit.test);
390                 
391                 if(RE_rayobject_intersect(isec->last_hit, isec))
392                 {
393                         RE_RC_COUNT(isec->raycounter->raycast.hit);
394                         RE_RC_COUNT(isec->raycounter->rayshadow_last_hit.hit);
395                         return 1;
396                 }
397         }
398 #endif
399
400 #ifdef RT_USE_HINT
401         isec->hit_hint = 0;
402 #endif
403
404         if(RE_rayobject_intersect(r, isec))
405         {
406                 RE_RC_COUNT(isec->raycounter->raycast.hit);
407
408 #ifdef RT_USE_HINT
409                 isec->hint = isec->hit_hint;
410 #endif
411                 return 1;
412         }
413
414         return 0;
415 }
416
417 int RE_rayobject_intersect(RayObject *r, Isect *i)
418 {
419         if(RE_rayobject_isRayFace(r))
420         {
421                 return intersect_rayface(r, (RayFace*) RE_rayobject_align(r), i);
422         }
423         else if(RE_rayobject_isVlakPrimitive(r))
424         {
425                 //TODO optimize (useless copy to RayFace to avoid duplicate code)
426                 VlakPrimitive *face = (VlakPrimitive*) RE_rayobject_align(r);
427                 RayFace nface;
428                 rayface_from_vlak(&nface, face->ob, face->face);
429
430                 return intersect_rayface(r, &nface, i);
431         }
432         else if(RE_rayobject_isRayAPI(r))
433         {
434                 r = RE_rayobject_align(r);
435                 return r->api->raycast(r, i);
436         }
437         else {
438                 assert(0);
439         return 0;
440         }
441 }
442
443 /* Building */
444
445 void RE_rayobject_add(RayObject *r, RayObject *o)
446 {
447         r = RE_rayobject_align(r);
448         return r->api->add(r, o);
449 }
450
451 void RE_rayobject_done(RayObject *r)
452 {
453         r = RE_rayobject_align(r);
454         r->api->done(r);
455 }
456
457 void RE_rayobject_free(RayObject *r)
458 {
459         r = RE_rayobject_align(r);
460         r->api->free(r);
461 }
462
463 float RE_rayobject_cost(RayObject *r)
464 {
465         if(RE_rayobject_isRayFace(r) || RE_rayobject_isVlakPrimitive(r))
466         {
467                 return 1.0f;
468         }
469         else if(RE_rayobject_isRayAPI(r))
470         {
471                 r = RE_rayobject_align(r);
472                 return r->api->cost(r);
473         }
474         else {
475                 assert(0);
476                 return 1.0f;
477         }
478 }
479
480 /* Bounding Boxes */
481
482 void RE_rayobject_merge_bb(RayObject *r, float *min, float *max)
483 {
484         if(RE_rayobject_isRayFace(r))
485         {
486                 RayFace *face = (RayFace*) RE_rayobject_align(r);
487                 
488                 DO_MINMAX(face->v1, min, max);
489                 DO_MINMAX(face->v2, min, max);
490                 DO_MINMAX(face->v3, min, max);
491                 if(RE_rayface_isQuad(face)) DO_MINMAX(face->v4, min, max);
492         }
493         else if(RE_rayobject_isVlakPrimitive(r))
494         {
495                 VlakPrimitive *face = (VlakPrimitive*) RE_rayobject_align(r);
496                 RayFace nface;
497                 rayface_from_vlak(&nface, face->ob, face->face);
498
499                 DO_MINMAX(nface.v1, min, max);
500                 DO_MINMAX(nface.v2, min, max);
501                 DO_MINMAX(nface.v3, min, max);
502                 if(RE_rayface_isQuad(&nface)) DO_MINMAX(nface.v4, min, max);
503         }
504         else if(RE_rayobject_isRayAPI(r))
505         {
506                 r = RE_rayobject_align(r);
507                 r->api->bb(r, min, max);
508         }
509         else
510                 assert(0);
511 }
512
513 /* Hints */
514
515 void RE_rayobject_hint_bb(RayObject *r, RayHint *hint, float *min, float *max)
516 {
517         if(RE_rayobject_isRayFace(r) || RE_rayobject_isVlakPrimitive(r))
518         {
519                 return;
520         }
521         else if(RE_rayobject_isRayAPI(r))
522         {
523                 r = RE_rayobject_align(r);
524                 return r->api->hint_bb(r, hint, min, max);
525         }
526         else
527                 assert(0);
528 }
529
530 /* RayObjectControl */
531
532 int RE_rayobjectcontrol_test_break(RayObjectControl *control)
533 {
534         if(control->test_break)
535                 return control->test_break(control->data);
536
537         return 0;
538 }
539
540 void RE_rayobject_set_control(RayObject *r, void *data, RE_rayobjectcontrol_test_break_callback test_break)
541 {
542         if(RE_rayobject_isRayAPI(r))
543         {
544                 r = RE_rayobject_align(r);
545                 r->control.data = data;
546                 r->control.test_break = test_break;
547         }
548 }
549