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