Untitled
Loading...
Searching...
No Matches
acceleration.c File Reference

Acceleration structure generation and how we traverse them. More...

#include "core/camera.h"
#include "utilities/mathf.h"
#include "mesh.h"
#include "utilities/types.h"
#include "utilities/utilities.h"
#include <math.h>
#include "render/render.h"
#include "load/init.h"

Go to the source code of this file.

Functions

void swap_size_t (size_t *a, size_t *b)
 Swaps a and b.
void assign_next_nodes (BVHNode *nodes, int index, int next)
 Assigns next nodes for stackless traversal top-down.
bool BVH_slab_test_aabb (RayHit *hit, AABB aabb, vec3 origin, vec3 inv_dir)
 Slab test for BVH.
void ray_traverse_mesh_bvh (Mesh *m, MeshNode *mn, BVHNode *nodes, vec3 inv_pos, vec3 mod_dir, vec3 inv_dir, RayHit *hit, bool check_normal)
 Traverses a Mesh's triangle BVH.
void ray_traverse_scene_bvh (SceneData *sd, BVHNode *nodes, vec3 origin, vec3 dir, vec3 mod_dir, vec3 inv_dir, RayHit *hit, bool check_normal)
 Traverses a SceneData's MeshNode BVH.
void process_collision_node (Mesh *m, MeshNode *mn, BVHNode *node, vec3 proposed, CollisionPoints *p)
 Processes Player collision against a static MeshNode's triangle BVH node.
bool subdivide_scene_bvh (Vector *bvh_nodes, size_t *indices, AABB *aabbs, int pidx, int depth, int axes_tried)
 Subdivides the SceneData's MeshNodes into a BVH.
bool subdivide_mesh_tri_bvh (Mesh *mesh, int pidx, int depth, int axes_tried)
 Subdivides the Mesh's triangles into a BVH.
bool subdivide_light_bvh (Vector *bvh_nodes, size_t *indices, AABB *aabbs, Light *lights, int pidx, int depth, int axes_tried)
 Subdivides the SceneData's Lights into a BVH.
bool ray_intersects_aabb (AABB aabb, vec3 origin, vec3 dir, vec3 inv_dir)
 Checks if a ray intersects an aabb.
bool ray_intersects_aabb_with_point (AABB aabb, vec3 origin, vec3 dir, vec3 inv_dir, vec3 *intersection_point)
 Checks if a ray intersects an aabb and outputs an intersection point.
bool ray_intersects_obb_with_point (OBB obb, vec3 origin, vec3 dir, vec3 *intersection_point)
 Checks if a ray intersects an obb and outputs an intersection point.
RayHit raycast_scene (vec3 start, vec3 dir, float initial_t, bool check_normal)
 Raycasts through the scene and finds closest intersection to meshes.
bool traverse_collision_bvh (Mesh *m, MeshNode *mn, BVHNode *nodes, BVHNode *node, vec3 proposed, vec3 inv_p, CollisionPoints *p)
 Traverses the mesh bvh to find collisions based on point vs aabb within a certain epsilon for player collisions.
void init_scene_bvh ()
 Initializes or updates the pre-existing scene bvh based on all mesh nodes with valid meshes.
void init_mesh_tri_bvh (Mesh *mesh)
 Initializes the bvh for a mesh's triangles.
void build_light_bvh ()
 Initializes a bvh for all current lights and emissive triangles in the scene, and sets the flux up for importance sampling.

Variables

const float RAY_EPS = 1e-6f

Detailed Description

Acceleration structure generation and how we traverse them.

Definition in file acceleration.c.

Function Documentation

◆ swap_size_t()

void swap_size_t ( size_t * a,
size_t * b )

Swaps a and b.

Definition at line 111 of file acceleration.c.

References swap_size_t().

Referenced by subdivide_light_bvh(), subdivide_mesh_tri_bvh(), subdivide_scene_bvh(), and swap_size_t().

◆ assign_next_nodes()

void assign_next_nodes ( BVHNode * nodes,
int index,
int next )

Assigns next nodes for stackless traversal top-down.

Parameters
nodesThe BVHNodes to assign over.
indexThe recursive current node index.
nextEither the parent's right or parent-parent's right etc.

Definition at line 118 of file acceleration.c.

References assign_next_nodes(), BVHNode::left, BVHNode::next, and BVHNode::right.

Referenced by assign_next_nodes(), build_light_bvh(), init_mesh_tri_bvh(), and init_scene_bvh().

◆ BVH_slab_test_aabb()

bool BVH_slab_test_aabb ( RayHit * hit,
AABB aabb,
vec3 origin,
vec3 inv_dir )

Slab test for BVH.

Parameters
hitThe RayHit that tests its t value.
aabbThe AABB to slab test.
originThe origin of the ray.
inv_dir\(\frac{1}{\mathit{ray}}\)
Returns
true if node is entered.

Definition at line 134 of file acceleration.c.

References BVH_slab_test_aabb(), hit, AABB::max_x, AABB::max_y, AABB::max_z, AABB::min_x, AABB::min_y, AABB::min_z, vec3::x, vec3::y, and vec3::z.

Referenced by BVH_slab_test_aabb(), ray_traverse_mesh_bvh(), and ray_traverse_scene_bvh().

◆ ray_traverse_mesh_bvh()

void ray_traverse_mesh_bvh ( Mesh * m,
MeshNode * mn,
BVHNode * nodes,
vec3 inv_pos,
vec3 mod_dir,
vec3 inv_dir,
RayHit * hit,
bool check_normal )

Traverses a Mesh's triangle BVH.

Parameters
mThe target Mesh.
mnThe target MeshNode.
nodesThe BVHNode tree.
inv_pos\(M^{-1} \begin{bmatrix} o_x \\ o_y \\ o_z \\ 1 \end{bmatrix}\)
mod_dir\(M^{-1} \begin{bmatrix} d_x \\ d_y \\ d_z \\ 0 \end{bmatrix}\)
inv_dir\(\frac{1}{\mathit{mod\_dir}}\)
hitThe current RayHit data for the query.
check_normalIf it should cull backfaces.

Definition at line 299 of file acceleration.c.

References BVHNode::aabb, RayHit::b0, RayHit::b1, RayHit::b2, Mesh::bvh_indices, BVH_slab_test_aabb(), CAST_VEC, BVHNode::count, BVHNode::first_index, hit, RayHit::hit, HIT_STATIC, MeshNode::id, MeshFace::indices, BVHNode::left, RayHit::mesh_node_idx, BVHNode::next, MeshFace::normal, Point::pos, RayHit::pos, ray_intersects_triangle(), ray_traverse_mesh_bvh(), BVHNode::right, RayHit::t, RayHit::tri, Mesh::tris, vec3_dot(), Mesh::vertices, vec3::x, vec3::y, and vec3::z.

Referenced by ray_traverse_mesh_bvh(), and ray_traverse_scene_bvh().

◆ ray_traverse_scene_bvh()

void ray_traverse_scene_bvh ( SceneData * sd,
BVHNode * nodes,
vec3 origin,
vec3 dir,
vec3 mod_dir,
vec3 inv_dir,
RayHit * hit,
bool check_normal )

◆ process_collision_node()

◆ subdivide_scene_bvh()

bool subdivide_scene_bvh ( Vector * bvh_nodes,
size_t * indices,
AABB * aabbs,
int pidx,
int depth,
int axes_tried )

Subdivides the SceneData's MeshNodes into a BVH.

Parameters
bvh_nodesThe created BVHNodes.
indicesThe array of indices that are sorted as the BVH is built.
aabbsThe AABBs of each MeshNode.
pidxThe parent idx.
depthThe current depth.
axes_triedHow many axes have been unsuccessfully tried for a given node before a split is decided as impossible at 3.
Returns
false if it is a leaf.

Definition at line 562 of file acceleration.c.

References BVHNode::aabb, calculate_aabb_extents(), CAST_VEC, AABB::center, BVHNode::count, Vector::count, AABB::extents, BVHNode::first_index, BVHNode::index, BVHNode::left, AABB::max_x, AABB::max_y, AABB::max_z, AABB::min_x, AABB::min_y, AABB::min_z, BVHNode::next, BVHNode::parent, BVHNode::right, subdivide_scene_bvh(), swap_size_t(), vector_expand(), X, vec3::x, Y, vec3::y, Z, and vec3::z.

Referenced by init_scene_bvh(), subdivide_light_bvh(), and subdivide_scene_bvh().

◆ subdivide_mesh_tri_bvh()

bool subdivide_mesh_tri_bvh ( Mesh * mesh,
int pidx,
int depth,
int axes_tried )

Subdivides the Mesh's triangles into a BVH.

Parameters
mesthThe Mesh.
pidxThe parent idx.
depthThe current depth.
axes_triedHow many axes have been unsuccessfully tried for a given node before a split is decided as impossible at 3.
Returns
false if it is a leaf.

Definition at line 936 of file acceleration.c.

References BVHNode::aabb, Mesh::bvh_indices, calculate_aabb_extents(), CAST_VEC, AABB::center, BVHNode::count, Vector::count, AABB::extents, BVHNode::first_index, BVHNode::index, BVHNode::left, AABB::max_x, AABB::max_y, AABB::max_z, AABB::min_x, AABB::min_y, AABB::min_z, BVHNode::next, Mesh::nodes, BVHNode::parent, BVHNode::right, subdivide_mesh_tri_bvh(), swap_size_t(), Mesh::tri_aabbs, Mesh::tris, vector_expand(), Mesh::vertices, X, vec3::x, Y, vec3::y, Z, and vec3::z.

Referenced by init_mesh_tri_bvh(), and subdivide_mesh_tri_bvh().

◆ subdivide_light_bvh()

bool subdivide_light_bvh ( Vector * bvh_nodes,
size_t * indices,
AABB * aabbs,
Light * lights,
int pidx,
int depth,
int axes_tried )

Subdivides the SceneData's Lights into a BVH.

Parameters
bvh_nodesThe created BVHNodes.
indicesThe array of indices that are sorted as the BVH is built.
aabbsThe AABBs of each MeshNode.
lightsThe array of Lights.
pidxThe parent idx.
depthThe current depth.
axes_triedHow many axes have been unsuccessfully tried for a given node before a split is decided as impossible at 3.
Returns
false if it is a leaf.

Definition at line 1278 of file acceleration.c.

References BVHNode::aabb, AREA_LIGHT, calculate_aabb_extents(), CAST_VEC, AABB::center, BVHNode::count, Vector::count, DIRECTIONAL_LIGHT, BVHNode::emissive_flux, AABB::extents, BVHNode::first_index, BVHNode::flux, BVHNode::index, BVHNode::left, Light::light_type, AABB::max_x, AABB::max_y, AABB::max_z, AABB::min_x, AABB::min_y, AABB::min_z, BVHNode::next, BVHNode::parent, Light::power, BVHNode::right, subdivide_light_bvh(), subdivide_scene_bvh(), swap_size_t(), vector_expand(), X, vec3::x, Y, vec3::y, Z, and vec3::z.

Referenced by build_light_bvh(), and subdivide_light_bvh().

◆ ray_intersects_aabb()

bool ray_intersects_aabb ( AABB aabb,
vec3 origin,
vec3 dir,
vec3 inv_dir )

Checks if a ray intersects an aabb.

Parameters
aabbThe aabb to check.
originThe origin of the ray.
dirThe dir of the ray.
inv_dir1.0f/dir of the ray.
Returns
If we intersected the aabb.

Definition at line 157 of file acceleration.c.

References AABB::max_x, AABB::max_y, AABB::max_z, AABB::min_x, AABB::min_y, AABB::min_z, ray_intersects_aabb(), vec3::x, vec3::y, and vec3::z.

Referenced by ray_intersects_aabb().

◆ ray_intersects_aabb_with_point()

bool ray_intersects_aabb_with_point ( AABB aabb,
vec3 origin,
vec3 dir,
vec3 inv_dir,
vec3 * intersection_point )

Checks if a ray intersects an aabb and outputs an intersection point.

Parameters
aabbThe aabb to check.
originThe origin of the ray.
dirThe dir of the ray.
inv_dir1.0f/dir of the ray.
intersection_pointA pointer to where we will place the intersection point.
Precondition
intersection_point must not be NULL.
Returns
If we intersected the aabb.

Definition at line 182 of file acceleration.c.

References AABB::max_x, AABB::max_y, AABB::max_z, AABB::min_x, AABB::min_y, AABB::min_z, ray_intersects_aabb_with_point(), vec3_add(), vec3_scale(), vec3::x, vec3::y, and vec3::z.

Referenced by process_sdl_event(), ray_intersects_aabb_with_point(), and ray_traverse_scene_bvh().

◆ ray_intersects_obb_with_point()

bool ray_intersects_obb_with_point ( OBB obb,
vec3 origin,
vec3 dir,
vec3 * intersection_point )

Checks if a ray intersects an obb and outputs an intersection point.

Parameters
obbThe obb to check.
originThe origin of the ray.
dirThe dir of the ray.
intersection_pointA pointer to where we will place the intersection point.
Precondition
intersection_point must not be NULL.
Returns
If we intersected the obb.

Definition at line 220 of file acceleration.c.

References mat3::a0, mat3::a1, mat3::a2, mat3::b0, mat3::b1, mat3::b2, mat3::c0, mat3::c1, mat3::c2, OBB::center, OBB::extents, RAY_EPS, ray_intersects_obb_with_point(), OBB::rot, vec3_add(), vec3_dot(), vec3_normalize(), vec3_scale(), vec3_sub(), vec3::x, vec3::y, and vec3::z.

Referenced by check_lighting_pv(), process_sdl_event(), and ray_intersects_obb_with_point().

◆ raycast_scene()

RayHit raycast_scene ( vec3 start,
vec3 dir,
float initial_t,
bool check_normal )

Raycasts through the scene and finds closest intersection to meshes.

Parameters
startThe ray's starting position.
dirThe dir of the ray.
initial_tThe starting T to begin evaluating, usually set at INFINITY.
check_normalTo check backfaces or not.
Returns
A RayHit with hit information.

Definition at line 448 of file acceleration.c.

References SceneData::bvh_nodes, CAST_VEC, Vector::count, MeshNode::global_matrix, GLOBALS, hit, RayHit::hit, mat4_mul_point(), RayHit::mesh_node_idx, Globals::mesh_nodes, RayHit::pos, ray_traverse_scene_bvh(), raycast_scene(), Globals::scene_data, RayHit::t, vec3::x, vec3::y, and vec3::z.

Referenced by find_closest_visible_aportal(), interpolate_nearest_aprobes(), pathfind_audio_occlusion(), process_sdl_event(), raycast_scene(), recalculate_audio_portal_paths(), resolve_collisions(), update_audio_occlusion(), update_body_from_legs(), and update_leg().

◆ traverse_collision_bvh()

bool traverse_collision_bvh ( Mesh * m,
MeshNode * mn,
BVHNode * nodes,
BVHNode * node,
vec3 proposed,
vec3 inv_p,
CollisionPoints * p )

Traverses the mesh bvh to find collisions based on point vs aabb within a certain epsilon for player collisions.

Parameters
mThe mesh we are traversing.
mnThe mesh node we are traversing.
nodesThe bvh nodes we are traversing.
nodeThe current node.
proposedThe position we are checking.
inv_posThe position transformed into mesh node local space using inv matrix.
pThe array of collision points to append to.
Returns
If it collides with a mesh.

Definition at line 514 of file acceleration.c.

References BVHNode::aabb, BVHNode::left, AABB::max_x, AABB::max_y, AABB::max_z, AABB::min_x, AABB::min_y, AABB::min_z, point_in_aabb(), process_collision_node(), BVHNode::right, and traverse_collision_bvh().

Referenced by player_find_collision(), and traverse_collision_bvh().

◆ init_scene_bvh()

◆ init_mesh_tri_bvh()

◆ build_light_bvh()

void build_light_bvh ( )

Initializes a bvh for all current lights and emissive triangles in the scene, and sets the flux up for importance sampling.

Definition at line 1600 of file acceleration.c.

References Light::A, BVHNode::aabb, Light::area, AREA_LIGHT, assign_next_nodes(), Light::B, Vector::buffer, build_light_bvh(), Mesh::bvh_indices, SceneData::bvh_indices, SceneData::bvh_indices_count, Light::C, calculate_aabb_bounds(), calculate_aabb_extents(), CAST_VEC, AABB::center, BVHNode::count, Vector::count, DIRECTIONAL_LIGHT, BVHNode::emissive_flux, Material::emissive_strength, AABB::extents, BVHNode::first_index, BVHNode::flux, MeshNode::free, MeshNode::global_matrix, GLOBALS, BVHNode::index, LightBVH::indices, MeshFace::indices, LightBVH::indices_count, init_vector(), Light::intensity, Material::ke, BVHNode::left, SceneData::light_bvh, Light::light_type, Globals::lights, LightBVH::lights, Light::lum, M_PI, mat3_from_mat4(), mat3_inverse_transpose(), mat3_mul_vec3(), mat4_mul_point(), MeshFace::material_id, Globals::materials, AABB::max_x, AABB::max_y, AABB::max_z, Light::mesh, MeshNode::mesh, Globals::mesh_nodes, Globals::meshes, AABB::min_x, AABB::min_y, AABB::min_z, BVHNode::next, LightBVH::nodes, Light::normal, MeshFace::normal, Light::outer_angle, BVHNode::parent, POINT_LIGHT, Light::pos, Point::pos, Light::power, Light::radius, Light::rgb, BVHNode::right, rot(), Globals::scene_data, SPOT_LIGHT, MeshNode::static_mesh, subdivide_light_bvh(), Light::surface_area, Light::threshold, Light::tri, triangle_area(), triangle_centroid(), Mesh::tris, vec3_normalize(), vec3_scale(), vec4_length(), vec4_to_vec3(), vector_expand(), Mesh::vertices, vec3::x, vec3::y, and vec3::z.

Referenced by build_light_bvh(), and render_light_menu().

Variable Documentation

◆ RAY_EPS

const float RAY_EPS = 1e-6f

Definition at line 218 of file acceleration.c.

Referenced by ray_intersects_obb_with_point().