# Notes on the librt code

## Introduction

* more information about raytracing can be found here[1]
* a well-documented example of librt usage can be found in `src/rt/rtexample.c`
* Introduction to MGED[2] helps with the terminology used throughout BRL-CAD
* There's also a quick reference card[3]

## Terminology

* solid: a primitive shape created (e.g., a sphere) with the geometry editor
  + e.g., `make sph1.s sph` creates the solid `sph1.s`
* region: result of boolean expression over one or more solids
  + e.g., `r sph.r u sph1.s - sph2.s` creates the region `sph.r` as the result
    of the boolean expression `u sph1.s - sph2.s` (all points in `sph1.s` but
    not in `sph2.s`)
* ray: a line which is shot from a point in a direction
* (ray) intersection: a segment on the ray, intersecting a solid in the
  database; it's a segment (as opposed to a point) because in 3D, shapes have
  depth
* partition: list of segments (intervals of ray) intersecting a *single* region
  (not just a solid, but a region --- see above for the difference)

## Structures

* `struct soltab`: linked list of solids (see above) in the current database;
  contains information such as solid type (`st_id`, e.g., ID_EHY) and a list of
  regions (see above) that the solid is a part of (`st_regions`).
* `struct hit`: one point where a ray hits geometry; defined as distance from
  where the ray is shot.
* `struct seg`: a segment defining a ray intersection (see above); uses two
  `struct hit`s to define the segment; also holds a pointer to the solid (see
  above) that intersects the ray at this segment; can link to other segments if
  the ray intersects multiple solids where it exits the geometry; contains
  pointers to other segs if a torus; also contains pointer to original geometry.
  + give example with torus
* `union tree`: boolean operations for creating an object, in binary tree form
* `struct region`: contains name of region (e.g. `sph.r`), pointer to boolean
  tree and material, among other things.
* `struct partition`: ray intersection with a region; circular doubly-linked
  list; inseg/inhit is the intersection with the first solid in the region;
  outseg/outhit with the last solid in the region
  + in `rtexample.c`, the region and the in/out segments of each partition are
    printed in the hit callback;
  + TODO: give example (e.g., running tree on the database, and output of
    shooting a ray towards a region in the database)
* TODO: add `struct xray`

## Functions

* rt_gettree
  + add the geometry tree for the second argument to the raytracer instance
  + this is where the boolean tree is constructed (in `db_recurse`)
  + each primitive has an import (and export) function; in the case of a
    combination (a region is also a combination), it takes care of allocating
    memory for the boolean trees; the memory is a `bu_ptbl` big enough to store
    all the children; as such, the nodes are stored in continuous memory (good
    for cache behaviour)

* bool_eval
  + O(|non-leaf| + |leaf| * |partition|)

* rt_boolfinal
  + goes through all partition in `InputHdp` (argument); for each partition
    - clear `regiontable` (`bu_ptbl_reset(regiontable)`)
    - for each segment in the partition
      o add the regions it is involved with to the set `regiontable` (argument)
    - for each region in `regiontable`, evaluate its tree (`bool_eval`)
      o TODO: what does it mean to evaluate the tree?
    - if a primitive is part of more than one region (`claiming_region` > 1),
      then overlap occurs (e.g., imagine two C's which share the vertical bar)

* TODO: rt_shootray

* rt_boolweave

## Possible optimisations

* bool_eval: maybe the tree can be evaluated differently for the common case?
* bool_eval: could `BU_PTBL_FOR` be replaced with lookup into `solidbits`? would
  reduce complexity to O(|nodes|)
* rt_boolfinal: construction of regiontable using bu_ptbl_cat_uniq can be more
  efficient

[1]: https://www.scratchapixel.com/lessons/3d-basic-rendering/introduction-to-ray-tracing/
[2]: https://brlcad.org/w/images/c/cf/Introduction_to_MGED.pdf
[3]: http://brlcad.org/w/images/5/52/MGED_Quick_Reference_Card.pdf