KiCad PCB EDA Suite
cbvh_packet_traversal.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2015-2016 Mario Luzeiro <mrluzeiro@ua.pt>
5  * Copyright (C) 1992-2016 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, you may find one here:
19  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20  * or you may search the http://www.gnu.org website for the version 2 license,
21  * or you may write to the Free Software Foundation, Inc.,
22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23  */
24 
30 #include "cbvh_pbrt.h"
31 #include <wx/debug.h>
32 
33 
34 #define BVH_RANGED_TRAVERSAL
35 //#define BVH_PARTITION_TRAVERSAL
36 
37 
38 #define MAX_TODOS 64
39 
40 
41 struct StackNode
42 {
43  int cell;
44  unsigned int ia; // Index to the first alive ray
45 };
46 
47 
48 static inline unsigned int getFirstHit( const RAYPACKET &aRayPacket,
49  const CBBOX &aBBox,
50  unsigned int ia,
51  HITINFO_PACKET *aHitInfoPacket )
52 {
53  float hitT;
54 
55  if( aBBox.Intersect( aRayPacket.m_ray[ia], &hitT ) )
56  if( hitT < aHitInfoPacket[ia].m_HitInfo.m_tHit )
57  return ia;
58 
59  if( !aRayPacket.m_Frustum.Intersect( aBBox ) )
61 
62  for( unsigned int i = ia + 1; i < RAYPACKET_RAYS_PER_PACKET; ++i )
63  {
64  if( aBBox.Intersect( aRayPacket.m_ray[i], &hitT ) )
65  if( hitT < aHitInfoPacket[i].m_HitInfo.m_tHit )
66  return i;
67  }
68 
70 }
71 
72 
73 #ifdef BVH_RANGED_TRAVERSAL
74 
75 static inline unsigned int getLastHit( const RAYPACKET &aRayPacket,
76  const CBBOX &aBBox,
77  unsigned int ia,
78  HITINFO_PACKET *aHitInfoPacket )
79 {
80  for( unsigned int ie = (RAYPACKET_RAYS_PER_PACKET - 1); ie > ia; --ie )
81  {
82  float hitT;
83 
84  if( aBBox.Intersect( aRayPacket.m_ray[ie], &hitT ) )
85  if( hitT < aHitInfoPacket[ie].m_HitInfo.m_tHit )
86  return ie + 1;
87  }
88 
89  return ia + 1;
90 }
91 
92 
93 // "Large Ray Packets for Real-time Whitted Ray Tracing"
94 // http://cseweb.ucsd.edu/~ravir/whitted.pdf
95 
96 // Ranged Traversal
97 bool CBVH_PBRT::Intersect( const RAYPACKET &aRayPacket,
98  HITINFO_PACKET *aHitInfoPacket ) const
99 {
100  if( m_nodes == NULL )
101  return false;
102 
103  if( (&m_nodes[0]) == NULL )
104  return false;
105 
106  bool anyHitted = false;
107  int todoOffset = 0, nodeNum = 0;
108  StackNode todo[MAX_TODOS];
109 
110  unsigned int ia = 0;
111 
112  while( true )
113  {
114  const LinearBVHNode *curCell = &m_nodes[nodeNum];
115 
116  ia = getFirstHit( aRayPacket, curCell->bounds, ia, aHitInfoPacket );
117 
118  if( ia < RAYPACKET_RAYS_PER_PACKET )
119  {
120  if( curCell->nPrimitives == 0 )
121  {
122  StackNode &node = todo[todoOffset++];
123  node.cell = curCell->secondChildOffset;
124  node.ia = ia;
125  nodeNum = nodeNum + 1;
126  continue;
127  }
128  else
129  {
130  const unsigned int ie = getLastHit( aRayPacket,
131  curCell->bounds,
132  ia,
133  aHitInfoPacket );
134 
135  for( int j = 0; j < curCell->nPrimitives; ++j )
136  {
137  const COBJECT *obj = m_primitives[curCell->primitivesOffset + j];
138 
139  if( aRayPacket.m_Frustum.Intersect( obj->GetBBox() ) )
140  {
141  for( unsigned int i = ia; i < ie; ++i )
142  {
143  const bool hitted = obj->Intersect( aRayPacket.m_ray[i],
144  aHitInfoPacket[i].m_HitInfo );
145 
146  if( hitted )
147  {
148  anyHitted |= hitted;
149  aHitInfoPacket[i].m_hitresult |= hitted;
150  aHitInfoPacket[i].m_HitInfo.m_acc_node_info = nodeNum;
151  }
152  }
153  }
154  }
155  }
156  }
157 
158  if( todoOffset == 0 )
159  break;
160 
161  const StackNode &node = todo[--todoOffset];
162 
163  nodeNum = node.cell;
164  ia = node.ia;
165  }
166 
167  return anyHitted;
168 
169 }// Ranged Traversal
170 #endif
171 
172 
173 // "Ray Tracing Deformable Scenes Using Dynamic Bounding Volume Hierarchies"
174 // http://www.cs.cmu.edu/afs/cs/academic/class/15869-f11/www/readings/wald07_packetbvh.pdf
175 
176 #ifdef BVH_PARTITION_TRAVERSAL
177 
178 static inline unsigned int getLastHit( const RAYPACKET &aRayPacket,
179  const CBBOX &aBBox,
180  unsigned int ia,
181  const unsigned int *aRayIndex,
182  HITINFO_PACKET *aHitInfoPacket )
183 {
184  for( unsigned int ie = (RAYPACKET_RAYS_PER_PACKET - 1); ie > ia; --ie )
185  {
186  float hitT;
187 
188  if( aBBox.Intersect( aRayPacket.m_ray[ aRayIndex[ie] ], &hitT ) )
189  if( hitT < aHitInfoPacket[ aRayIndex[ie] ].m_HitInfo.m_tHit )
190  return ie + 1;
191  }
192 
193  return ia + 1;
194 }
195 
196 
197 static inline unsigned int partRays( const RAYPACKET &aRayPacket,
198  const CBBOX &aBBox,
199  unsigned int ia,
200  unsigned int *aRayIndex,
201  HITINFO_PACKET *aHitInfoPacket )
202 {
203 
204  if( !aRayPacket.m_Frustum.Intersect( aBBox ) )
206 
207  unsigned int ie = 0;
208 
209  for( unsigned int i = 0; i < ia; ++i )
210  {
211  float hitT;
212  if( aBBox.Intersect( aRayPacket.m_ray[ aRayIndex[i] ], &hitT ) )
213  if( hitT < aHitInfoPacket[ aRayIndex[i] ].m_HitInfo.m_tHit )
214  std::swap( aRayIndex[ie++], aRayIndex[i] );
215  }
216 
217  return ie;
218 }
219 
220 
221 bool CBVH_PBRT::Intersect( const RAYPACKET &aRayPacket,
222  HITINFO_PACKET *aHitInfoPacket ) const
223 {
224  bool anyHitted = false;
225  int todoOffset = 0, nodeNum = 0;
226  StackNode todo[MAX_TODOS];
227 
228  unsigned int I[RAYPACKET_RAYS_PER_PACKET];
229 
230  memcpy( I, m_I, RAYPACKET_RAYS_PER_PACKET * sizeof( unsigned int ) );
231 
232  unsigned int ia = 0;
233 
234  while( true )
235  {
236  const LinearBVHNode *curCell = &m_nodes[nodeNum];
237 
238  ia = partRays( aRayPacket, curCell->bounds, ia, I, aHitInfoPacket );
239 
240  if( ia < RAYPACKET_RAYS_PER_PACKET )
241  {
242  if( curCell->nPrimitives == 0 )
243  {
244  StackNode &node = todo[todoOffset++];
245  node.cell = curCell->secondChildOffset;
246  node.ia = ia;
247  nodeNum = nodeNum + 1;
248  continue;
249  }
250  else
251  {
252  unsigned int ie = getLastHit( aRayPacket,
253  curCell->bounds,
254  ia,
255  I,
256  aHitInfoPacket );
257 
258  for( int j = 0; j < curCell->nPrimitives; ++j )
259  {
260  const COBJECT *obj = m_primitives[curCell->primitivesOffset + j];
261 
262  if( aRayPacket.m_Frustum.Intersect( obj->GetBBox() ) )
263  {
264  for( unsigned int i = 0; i < ie; ++i )
265  {
266  unsigned int idx = I[i];
267 
268  bool hitted = obj->Intersect(
269  aRayPacket.m_ray[idx],
270  aHitInfoPacket[idx].m_HitInfo );
271 
272  if( hitted )
273  {
274  anyHitted |= hitted;
275  aHitInfoPacket[idx].m_hitresult |= hitted;
276  aHitInfoPacket[idx].m_HitInfo.m_acc_node_info = nodeNum;
277  }
278  }
279  }
280  }
281  }
282  }
283 
284  if( todoOffset == 0 )
285  break;
286 
287  const StackNode &node = todo[--todoOffset];
288 
289  nodeNum = node.cell;
290  ia = node.ia;
291  }
292 
293  return anyHitted;
294 }// Partition Traversal
295 #endif
CONST_VECTOR_OBJECT m_primitives
Definition: cbvh_pbrt.h:159
RAY m_ray[RAYPACKET_RAYS_PER_PACKET]
Definition: raypacket.h:46
int primitivesOffset
leaf
Definition: cbvh_pbrt.h:90
uint16_t nPrimitives
0 -> interior node
Definition: cbvh_pbrt.h:95
CFRUSTUM m_Frustum
Definition: raypacket.h:45
const CBBOX & GetBBox() const
Definition: cobject.h:94
bool Intersect(const RAY &aRay, HITINFO &aHitInfo) const override
Definition: cbvh_pbrt.cpp:1129
HITINFO m_HitInfo
Definition: hitinfo.h:63
bool Intersect(const CBBOX &aBBox) const
Intersect - Intersects a bbox with this frustum.
Definition: cfrustum.cpp:65
bool Intersect(const RAY &aRay, float *t) const
Function Intersect.
Definition: cbbox_ray.cpp:46
static unsigned int getLastHit(const RAYPACKET &aRayPacket, const CBBOX &aBBox, unsigned int ia, HITINFO_PACKET *aHitInfoPacket)
static unsigned int getFirstHit(const RAYPACKET &aRayPacket, const CBBOX &aBBox, unsigned int ia, HITINFO_PACKET *aHitInfoPacket)
LinearBVHNode * m_nodes
Definition: cbvh_pbrt.h:160
#define MAX_TODOS
virtual bool Intersect(const RAY &aRay, HITINFO &aHitInfo) const =0
Functions Intersect.
#define RAYPACKET_RAYS_PER_PACKET
Definition: raypacket.h:40
unsigned int m_acc_node_info
( 4) The acc stores here the node that it hits
Definition: hitinfo.h:47
unsigned int m_I[RAYPACKET_RAYS_PER_PACKET]
Definition: cbvh_pbrt.h:165
int secondChildOffset
interior
Definition: cbvh_pbrt.h:91
bool m_hitresult
Definition: hitinfo.h:62
CBBOX bounds
Definition: cbvh_pbrt.h:85
Class CBBOX manages a bounding box defined by two SFVEC3F min max points.
Definition: cbbox.h:40
This BVH implementation is based on the source code implementation from the book "Physically Based Re...