KiCad PCB EDA Suite
bvh_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) 2015-2020 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 "bvh_pbrt.h"
31 
32 
33 #define BVH_RANGED_TRAVERSAL
34 //#define BVH_PARTITION_TRAVERSAL
35 
36 
37 #define MAX_TODOS 64
38 
39 
40 struct StackNode
41 {
42  int cell;
43  unsigned int ia; // Index to the first alive ray
44 };
45 
46 
47 static inline unsigned int getFirstHit( const RAYPACKET& aRayPacket, const BBOX_3D& aBBox,
48  unsigned int ia, HITINFO_PACKET* aHitInfoPacket )
49 {
50  float hitT;
51 
52  if( aBBox.Intersect( aRayPacket.m_ray[ia], &hitT )
53  && ( hitT < aHitInfoPacket[ia].m_HitInfo.m_tHit ) )
54  return ia;
55 
56  if( !aRayPacket.m_Frustum.Intersect( aBBox ) )
58 
59  for( unsigned int i = ia + 1; i < RAYPACKET_RAYS_PER_PACKET; ++i )
60  {
61  if( aBBox.Intersect( aRayPacket.m_ray[i], &hitT )
62  && ( hitT < aHitInfoPacket[i].m_HitInfo.m_tHit ) )
63  return i;
64  }
65 
67 }
68 
69 
70 #ifdef BVH_RANGED_TRAVERSAL
71 
72 static inline unsigned int getLastHit( const RAYPACKET& aRayPacket, const BBOX_3D& aBBox,
73  unsigned int ia, HITINFO_PACKET* aHitInfoPacket )
74 {
75  for( unsigned int ie = (RAYPACKET_RAYS_PER_PACKET - 1); ie > ia; --ie )
76  {
77  float hitT;
78 
79  if( aBBox.Intersect( aRayPacket.m_ray[ie], &hitT )
80  && ( hitT < aHitInfoPacket[ie].m_HitInfo.m_tHit ) )
81  return ie + 1;
82  }
83 
84  return ia + 1;
85 }
86 
87 
88 // "Large Ray Packets for Real-time Whitted Ray Tracing"
89 // http://cseweb.ucsd.edu/~ravir/whitted.pdf
90 
91 // Ranged Traversal
92 bool BVH_PBRT::Intersect( const RAYPACKET& aRayPacket, HITINFO_PACKET* aHitInfoPacket ) const
93 {
94  if( m_nodes == nullptr )
95  return false;
96 
97  if( &m_nodes[0] == nullptr )
98  return false;
99 
100  bool anyHit = false;
101  int todoOffset = 0, nodeNum = 0;
102  StackNode todo[MAX_TODOS];
103 
104  unsigned int ia = 0;
105 
106  while( true )
107  {
108  const LinearBVHNode *curCell = &m_nodes[nodeNum];
109 
110  ia = getFirstHit( aRayPacket, curCell->bounds, ia, aHitInfoPacket );
111 
112  if( ia < RAYPACKET_RAYS_PER_PACKET )
113  {
114  if( curCell->nPrimitives == 0 )
115  {
116  StackNode& node = todo[todoOffset++];
117  node.cell = curCell->secondChildOffset;
118  node.ia = ia;
119  nodeNum = nodeNum + 1;
120  continue;
121  }
122  else
123  {
124  const unsigned int ie = getLastHit( aRayPacket, curCell->bounds, ia,
125  aHitInfoPacket );
126 
127  for( int j = 0; j < curCell->nPrimitives; ++j )
128  {
129  const OBJECT_3D* obj = m_primitives[curCell->primitivesOffset + j];
130 
131  if( aRayPacket.m_Frustum.Intersect( obj->GetBBox() ) )
132  {
133  for( unsigned int i = ia; i < ie; ++i )
134  {
135  const bool hit = obj->Intersect( aRayPacket.m_ray[i],
136  aHitInfoPacket[i].m_HitInfo );
137 
138  if( hit )
139  {
140  anyHit |= hit;
141  aHitInfoPacket[i].m_hitresult |= hit;
142  aHitInfoPacket[i].m_HitInfo.m_acc_node_info = nodeNum;
143  }
144  }
145  }
146  }
147  }
148  }
149 
150  if( todoOffset == 0 )
151  break;
152 
153  const StackNode& node = todo[--todoOffset];
154 
155  nodeNum = node.cell;
156  ia = node.ia;
157  }
158 
159  return anyHit;
160 
161 }
162 #endif
163 
164 
165 // "Ray Tracing Deformable Scenes Using Dynamic Bounding Volume Hierarchies"
166 // http://www.cs.cmu.edu/afs/cs/academic/class/15869-f11/www/readings/wald07_packetbvh.pdf
167 
168 #ifdef BVH_PARTITION_TRAVERSAL
169 
170 static inline unsigned int getLastHit( const RAYPACKET& aRayPacket, const BBOX_3D& aBBox,
171  unsigned int ia, const unsigned int* aRayIndex,
172  HITINFO_PACKET* aHitInfoPacket )
173 {
174  for( unsigned int ie = (RAYPACKET_RAYS_PER_PACKET - 1); ie > ia; --ie )
175  {
176  float hitT;
177 
178  if( aBBox.Intersect( aRayPacket.m_ray[ aRayIndex[ie] ], &hitT )
179  && ( hitT < aHitInfoPacket[ aRayIndex[ie] ].m_HitInfo.m_tHit ) )
180  return ie + 1;
181  }
182 
183  return ia + 1;
184 }
185 
186 
187 static inline unsigned int partRays( const RAYPACKET& aRayPacket, const BBOX_3D& aBBox,
188  unsigned int ia, unsigned int* aRayIndex,
189  HITINFO_PACKET* aHitInfoPacket )
190 {
191 
192  if( !aRayPacket.m_Frustum.Intersect( aBBox ) )
194 
195  unsigned int ie = 0;
196 
197  for( unsigned int i = 0; i < ia; ++i )
198  {
199  float hitT;
200 
201  if( aBBox.Intersect( aRayPacket.m_ray[ aRayIndex[i] ], &hitT )
202  && ( hitT < aHitInfoPacket[ aRayIndex[i] ].m_HitInfo.m_tHit ) )
203  std::swap( aRayIndex[ie++], aRayIndex[i] );
204  }
205 
206  return ie;
207 }
208 
209 
210 bool BVH_PBRT::Intersect( const RAYPACKET& aRayPacket, HITINFO_PACKET* aHitInfoPacket ) const
211 {
212  bool anyHit = false;
213  int todoOffset = 0, nodeNum = 0;
214  StackNode todo[MAX_TODOS];
215 
216  unsigned int I[RAYPACKET_RAYS_PER_PACKET];
217 
218  memcpy( I, m_I, RAYPACKET_RAYS_PER_PACKET * sizeof( unsigned int ) );
219 
220  unsigned int ia = 0;
221 
222  while( true )
223  {
224  const LinearBVHNode *curCell = &m_nodes[nodeNum];
225 
226  ia = partRays( aRayPacket, curCell->bounds, ia, I, aHitInfoPacket );
227 
228  if( ia < RAYPACKET_RAYS_PER_PACKET )
229  {
230  if( curCell->nPrimitives == 0 )
231  {
232  StackNode& node = todo[todoOffset++];
233  node.cell = curCell->secondChildOffset;
234  node.ia = ia;
235  nodeNum = nodeNum + 1;
236  continue;
237  }
238  else
239  {
240  unsigned int ie = getLastHit( aRayPacket, curCell->bounds, ia, I,
241  aHitInfoPacket );
242 
243  for( int j = 0; j < curCell->nPrimitives; ++j )
244  {
245  const OBJECT_3D* obj = m_primitives[curCell->primitivesOffset + j];
246 
247  if( aRayPacket.m_Frustum.Intersect( obj->GetBBox() ) )
248  {
249  for( unsigned int i = 0; i < ie; ++i )
250  {
251  unsigned int idx = I[i];
252 
253  bool hit = obj->Intersect( aRayPacket.m_ray[idx],
254  aHitInfoPacket[idx].m_HitInfo );
255 
256  if( hit )
257  {
258  anyHit |= hit;
259  aHitInfoPacket[idx].m_hitresult |= hit;
260  aHitInfoPacket[idx].m_HitInfo.m_acc_node_info = nodeNum;
261  }
262  }
263  }
264  }
265  }
266  }
267 
268  if( todoOffset == 0 )
269  break;
270 
271  const StackNode& node = todo[--todoOffset];
272 
273  nodeNum = node.cell;
274  ia = node.ia;
275  }
276 
277  return anyHit;
278 }
279 #endif
static unsigned int getFirstHit(const RAYPACKET &aRayPacket, const BBOX_3D &aBBox, unsigned int ia, HITINFO_PACKET *aHitInfoPacket)
RAY m_ray[RAYPACKET_RAYS_PER_PACKET]
Definition: raypacket.h:59
int primitivesOffset
leaf
Definition: bvh_pbrt.h:90
CONST_VECTOR_OBJECT m_primitives
Definition: bvh_pbrt.h:144
unsigned int ia
uint16_t nPrimitives
0 -> interior node
Definition: bvh_pbrt.h:95
virtual bool Intersect(const RAY &aRay, HITINFO &aHitInfo) const =0
Manage a bounding box defined by two SFVEC3F min max points.
Definition: bbox_3d.h:41
bool Intersect(const RAY &aRay, float *t) const
Definition: bbox_3d_ray.cpp:46
This BVH implementation is based on the source code implementation from the book "Physically Based Re...
float m_tHit
( 4) distance
Definition: hitinfo.h:43
static unsigned int getLastHit(const RAYPACKET &aRayPacket, const BBOX_3D &aBBox, unsigned int ia, HITINFO_PACKET *aHitInfoPacket)
bool Intersect(const BBOX_3D &aBBox) const
Intersect aBBox with this frustum.
Definition: frustum.cpp:62
#define I(x, y, z)
Definition: md5_hash.cpp:18
HITINFO m_HitInfo
Definition: hitinfo.h:63
FRUSTUM m_Frustum
Definition: raypacket.h:58
#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
bool Intersect(const RAY &aRay, HITINFO &aHitInfo) const override
Definition: bvh_pbrt.cpp:1066
const BBOX_3D & GetBBox() const
Definition: object_3d.h:92
int secondChildOffset
interior
Definition: bvh_pbrt.h:91
bool m_hitresult
Definition: hitinfo.h:62
#define MAX_TODOS
unsigned int m_I[RAYPACKET_RAYS_PER_PACKET]
Definition: bvh_pbrt.h:150
LinearBVHNode * m_nodes
Definition: bvh_pbrt.h:145
BBOX_3D bounds
Definition: bvh_pbrt.h:85