Algorithms in XR

Posted on In

XR devices leverages variety of algorithms, mainly include computer vision and computer graphics categories.

Computer Vision

Computer Vision algorithms leverages cameras and other on-device sensors, to estimate the state of both environment and the user.

SLAM

SLAM estimates user’s pose for world-locked rendering, and also provides anchors to pin virtual content into physical world over time.

In terms of the form factor of XR, SLAM usually consists of following components.

  • VIO: open loop odometry
    • Consumes camera and IMU measurements
    • Estimate pose at realtime
    • Accurate in small region, will drift when moving in large regions
  • Map Management: close loop map and pose optimization.
    • Consumes VIO poses and triangulated map points
    • Leverages place recognition and global optimization to maintain a geometric consistent map
    • Resolve VIO drift and achieves accurate anchoring over time/session. Since VIO poses cannot jump in XR system, it is the anchor’s position that get dragged back to the correct location / loading map to align with current poses.

See more about SLAM in here

Reconstruction

Reconstruction computes the environment surfaces, find planes and classify scene elements, providing physical world-aligned virtual content placement and physics effect.

Specifically, it contains following components.

  • Mesh Reconstruction
    • Consumes VIO poses, depth images
    • Estimate the triangle meshes of the scene and object surfaces
    • It uses voxel to represent the space, and estimates the TSDF values for each voxel over the time, and then generate the triangle meshes from the voxels
  • Plane Finding
  • Scene Understanding

Object Tracking

Object tracking tracks the known objects’ poses in the space.

Eye Tracking

Eye tracking computes the eye position and gaze direction of the user relative to the device. Used for foveate rendering and gaze interaction.

It consumes camera frames capturing the user’s eyes, extract glints and leverages device calibration data to compute eye poses. The glints are the reflections of LEDs on the corneas of eyes, and the LED positions will be pre-calculated during device calibration process.

Eye tracking also involves a user enrollment process, to compute the kalpa angles between optical and visual axis, and also estimates the other parameters for the eyes.

Hand Tracking

Hand tracking tracks the hand joints’s poses and recognize hands gestures. Used for hand interaction.

It consumes the cameras data, and estimate the per-joint pose for each hand.

Computer Graphics

How to use computer to calculate, process and show the shapes. How to convert 2D/3D object to 2D grid format showing in computer screen. The research content includes in following parts.

Modeling

express the objects with math model

  • Polygon, Parametric method
  • Point-based modeling: sample points in the surface
  • Volume data: sample points in the 3d space

Rendering

Graphics Pipeline. determine the color of each pixel according to the model, light, shader, texture and etc.

  • Graphics Pipeline
    • Pixel by pixel drawing
      • Cast a line from each pixel to the object
    • Piece by piece drawing (surface piece)
      • Project the piece from surface of object to the screen
      • Vertex Operations -> Rasterization -> Fragment Operations -> Frame Buffer
        • Vertex Operation: vertex transformation. Applying MVP matrix to transform vertex into clip space.
          • Model space -> (Model matrix, where the model locates in the world) -> World space -> (View matrix, where the camera locates in the world) -> Camera space -> (Projection matrix, the camera intrinsic) -> Clip space
        • Rasterization: convert shape to 2D grid image
        • Fragment operations: calculate the color of each pixel
        • Frame Buffer: display cache
  • Graphics System Development Library - Software
    • Provide interfaces for operate the graphics card driver, provide the graphics pipeline for rendering
    • OpenGL: Cross-platform
    • Direct3D: Good at game
    • Metal: Apple devices
  • GPU - Hardware
    • Parallel calculation, faster
    • Allow edited shader in the graphics pipeline
      • Vertex Shader -> Geometry Shader -> Rasterization -> Fragment Shader -> Frame Buffer
      • HLSL - for D3D shader language
      • GLSL - for OpenGL shader language

Basic Rendering Technology

To render an object to the screen, it is required to calculate the following effects on the object

  • Lighting effect
    • Direct lighting
      • Diffuse reflection
      • Specular reflection
      • Ambient reflection
    • Indirect lighting
      • Ray-tracing
      • Radiosity
      • Photon mapping
  • Texture effect
    • Map a texture function to the surface of object to influence the parameters of the diffuse lighting
    • Can influence color, bump, reflect, transparent
    • Methods
      • Bumping mapping
      • Displacement mapping
  • Shadow effect
    • Based on test light: shot raycast from point to light origin
    • Shadow volume: project the shadow object’s boundary to the viewing area
    • Shadow mapping: move the view point to the light origin, generate a texture containing the depth info, then move back, generate the final image according to the texture
  • Environment mapping
    • Object with a flat surface will reflect the environment in the surface
    • Pipeline
      • Capture the environmental images with a central camera
      • Map to the surface of a sphere
      • Adjust the object’s texture according to the sphere
  • Baking
    • Put the object into lighting environment, calculate the appearance and store the info into texture. Next time just put the texture to object

Accelerated rendering technology

  • LOD (Level of Detail)
    • Set different levels of the model according to the viewing distance. Farther, Rougher
  • Billboard
    • Use a 2D plane instead of 3D objects. But the plane always faces to human
  • Scene culling
    • Don’t generate objects that are invisible
    • Requires scene management
      • Scene Graph
        • Form the objects in tree data structure according to the logic of the objects
        • Use for dynamic scene
      • Space division
        • Form the objects in tree data structure according to the location of the objects
        • Use for static scene

Space division example - Quadtree

Collision detection

  • Divide in time domain
    • Static, discrete dynamics, continuous dynamic
  • Divide in space domain
    • Based on image space
    • Based on geometric space
      • Based on hierarchical bounding box
        • Use big bounding box to filter invalid collision