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 }