text:
## 1. Introduction and overview

This document takes you through an inital LSDTopoTools analysis. Through the tutorials contained here we will demonstrate how our analysis programs run: they all share a common interface.

Before you start

Before you start you need to install LSDTopoTools. If you haven’t done that, please follow the link below.

In addition, you will need to use some basic linux shell commands. If you have never done this before I suggest reading this brief introduction: Basic use of the linux shell.

### 1.1. The basic structure of an analysis

Our analyses are packaged into separate programs. They are run from the Linux shell. If you don’t have Linux, don’t worry, we use containers to create a Linux environment in your computer (see installation instructions). All of our programs operate the same way:

• You call the programs (such as `lsdtt-basic-metrics` and `lsdtt-channel-extraction`) from the command line.

• These programs work on topographic data, and they use a parameter file that tells the programs what to do with the data.

The basic structure looks like this:

Figure 1. All LSDTopoTools analyses work like this.

#### 1.1.1. Running a typical analysis for lsdtt-basic-metrics

In the next section we will walk you though an analysis. However, reading this will help you understand where you are going, so we recommend you read the whole thing!

• You run the program from a terminal window

• You can supply the program with:

• a directory name

• a parameter file name

• both of these things

• none of these things

• If you don’t supply a parameter filename, the program will assume the parameter file is called `LSDTT_parameters.driver`

• If the parameter file doesn’t exist, you will get an error message.

Any of the following calls to one of the programs will work, as long as your files are in the right place:

``````$lsdtt-basic-metrics$ lsdtt-basic-metrics /LSDTopoTools/data/A_project
$lsdtt-basic-metrics AParameterFile.param$ lsdtt-basic-metrics /LSDTopoTools/data/A_project AParameterFile.param``````
• The program name (`lsdtt-basic-metrics`), the directory name (`/LSDTopoTools/data/A_project`) and the parameter file name (`AParameterFile.param`) will change but all LSDTopoTools calls follow this same basic structure.

• Now, all parameter files have these basic elements in them:

``````read path: /LSDTopoTools/data/A_project
write path: /LSDTopoTools/data/A_project
write fname: Data_prefix``````
• You need to change the path and fnames to reflect your data!

• If the `read path` and `write path` are not specified, then the program will assume the data is in the same directory as the program is being run.

#### 1.1.2. How do I change my parameter files?

You can edit your parameter files in a text editor: this is just a program that edits plain text. DO NOT use a word processor. These modify file types.

There are many options for text editors but we like: * Brackets works on any operating system. * Atom also works on any operating system.

If you are on Windows then pspad is also quite good.

##### A note on read and write paths
 If you leave `read path` and `write path` blank, LSDTopoTools programs will assume the data is in the current directory. You can find out what the current directory is by typing `pwd` at the command prompt. As long as your data is in the same directory as your parameter file you won’t need to bother with this section at all. 99% of LSDTopoTools users can skip this section.

Editing read and write paths can be a bit annoying if you are moving data from place to place, so we have a python script, called `LSDTTParamfileUpdater.py` that updates the paths in the parameter file for you. The way you run that is:

1. Download the script into your data folder (i.e. in the second terminal window you have open above):

``$wget https://raw.githubusercontent.com/LSDtopotools/LSDAutomation/master/LSDTTParamfileUpdater.py`` 2. Run the file ``$ python LSDTTParamfileUpdater.py``
3. Again, you don’t need to do any of this if your data is in the same directory as your parameter file and you have left the `read path` and `write path` out of your parameter file.

## 2. Basic analyses in LSDTopoTools using the lsdtt-basic-metrics program

This chapter will walk you through some basic topographic analysis using our program lsdtt-basic-metrics. This program can extract topographic metrics like slope, aspect and curvature. Alongside these metrics it can also extract channel networks, and get drainage areas. The program is intended for everyday data processing. A number of these operations are available in GIS software, but we tend to prefer LSDTopoTools because:

• The slope and curvature metrics in typical GIS software only uses information from the nearest pixels. We fit a polynomial surface from a neighbourhood of pixels. See Hurst et al., 2012, DOI: 10.1029/2011JF002057 and Grieve et al., 2016, doi:10.5194/esurf-4-627-2016 for the rationale.

• Our channel extractions for the d8 method are based on the FASTSCAPE algorithm and are MUCH faster than running channel extraction in typical GIS software.

• The program does some data preprocessing behind the scenes that you would need to do manually in a GIS. For example, if the nodata values are messed up, LSDTopoTools can fix these.

• We have automated some basin selection routines, which again you would need to do by hand in a GIS.

• Our channel extraction spits out networks with drainage areas, locations, chi coordinates and all sorts of other goodies that would take ages on a GIS.

The examples in this section are used for both LSDTopoTools workshops as well as in the University of Edinburgh course, Eroding Landscapes.

### 2.1. Your first analysis using LSDTopoTools

We are going to run an LSDTopoTools2 program that is used for basic topographic analysis. If you have installed the programs already you just need to make sure that they are in your path. See the installation instructions.

Before you start

Before you start you need to install LSDTopoTools. If you haven’t done that, please follow the link below.

In addition, you will need to use some basic linux shell commands. If you have never done this before I suggest reading this brief introduction: Basic use of the linux shell.

#### 2.1.1. Get the test data

If you have followed the installation instructions and grabbed the example data, you already have what you need! If not, follow the steps below:

1. If you are using a docker container, just run the script:

``# Get_LSDTT_example_data.sh``
2. If you are on a native linux or using the University of Edinburgh servers, do the following:

1. If you have installed LSDTopoTools, you will have a directory somewhere called `LSDTopoTools`. Go into it.

2. Run the following commands (you only need to do this once):

``````$mkdir data$ cd data
$wget https://github.com/LSDtopotools/ExampleTopoDatasets/archive/master.zip$ unzip master.zip
$mv ./ExampleTopoDatasets-master ./ExampleTopoDatasets$ rm master.zip``````
3. WARNING: This downloads a bit over 150Mb of data so make sure you have room.

#### 2.1.2. Run an analysis

1. Go into the directory with this data: `cd ExampleTopoDatasets/BasicMetricsData`.

2. If you have installed `LSDTopoTools` correctly, you should just be able to call `lsdtt-basic-metrics`:

``$lsdtt-basic-metrics WA_BasicMetrics01.driver`` 3. This will spit out some information to you screen. It will also make a hillshade of the DEM, which is called `WA_FirstExample_hs.bil`. #### 2.1.3. Look at the data 1. You can look at this raster in QGIS. We have some instructions for QGIS, if you want to see instructions for adding data click here. 2. Open QGIS and load the raster. The new raster is in the same directory with your other data and is called `WA_FirstExample_hs.bil`.The data will look like this: Figure 2. A hillshade of the Whiteadder catchement 3. As you can see, the DEM has quite a few artefacts. There isn’t much we can do about that, I’m afraid. ### 2.2. Getting surface metrics Now we will get a bit more information about the DEM. Again, we will run an LSDTopoTools program (`lsdtt-basic-metrics`) that will ingest a raster `WA.bil` and spit out some new rasters. 1. Start by running the program with the second driver file: ``$ lsdtt-basic-metrics WA_BasicMetrics02.driver``
2. This does more stuff. We can look at the driver file:

``````# Parameters for extracting simple surface metrics
# Comments are preceded by the hash symbol

# These are parameters for the file i/o
write fname: WA_SecondExample

# Parameters for surface metrics
print_slope: true
print_aspect: true
print_curvature: true
print_tangential_curvature: true``````
3. In this case the program is printing slope, aspect, curvature, and tangential curvature rasters. They have filenames that reflect their contents so have a look. Slope tells you how steep the landscape is, aspect which direction the surface is pointing, curvature how, uh, curvy the landscape is (mathematically it is how quickly slope changes in space) and the tangential curvature is how curvy the landscape is in the direction of steepest descent. Essentially tangential curvature tells you how tightly curved contours are and is useful for finding valleys.

4. The way these are calculated is by fitting a surface of radius `surface_fitting_radius` to the points in the DEM and then calculating derivatives of that surface.

#### 2.2.1. Questions and tasks for surface metrics

• Try changing the `surface_fitting_radius`. What happens?

### 2.3. Drainage area and channel extraction

Finally, we will compute some drainage areas and extract a channel network. To do this run the driver file `WA_BasicMetrics03.driver`.

1. Run the program using:

``\$ lsdtt-basic-metrics WA_BasicMetrics03.driver``
2. Yet more stuff will come out. Some are drainage area rasters, but there is also a `csv` file, `WA_ThirdExample_CN.csv`.

3. You will get a file with points, which you can load into QGIS. You can read about how to do that in our QGIS instructions. You will get something that looks a bit like this:

Figure 3. A simple channel network

#### 2.3.1. Questions for channel extraction.

• Try changing the `threshold_contributing_pixels` parameter. What happens to the channel network?

• More advanced: You can get a smoothed elevation raster with the following driver file line: `print_smoothed_elevation: true`. Try creating a smoothed elevation raster and then using this smoothed raster for the drainage extraction. You will need to change the `read fname` parameter to reflect the smoothed raster.

### 2.4. Summary

You now have seen the basic interface of LSDTopoTools programs, got a small taste of Linux, and know a few things about QGIS. From here you should be able to move on to more advanced topographic analysis.

## 3. More advanced options in lsdtt-basic-metrics

One of the most common operations when analysing topographic data is extracting channel networks. We have an entire package for that, which has a number of different channel extraction algorithms.

However, many users just want channels extracted with the minimum of fuss and so we provide a simple channel profile extraction tool in lsdtt-basic-metrics.

### 3.1. What channels do you want? Selecting basins

Sometimes you don’t want every channel in the landscape, but only particular channels. We have some basin selection tools for this.

The next driver file has some options for selecting basins (`WA_BasicMetrics04.driver`):

``````# These are parameters for the file i/o
write fname: WA_FourthExample

# Basic channel network
threshold_contributing_pixels: 5000
print_junctions_to_csv: true

# Convert to json
convert_csv_to_geojson: true

# Getting the basins
find_basins: true
minimum_basin_size_pixels: 10000
maximum_basin_size_pixels: 100000000
only_take_largest_basin: false

# Print the basin raster
print_basin_raster: true``````

The key elements here are:

• `find_basins: true` This tells the program to find specific basins

• `minimum_basin_size_pixels: 10000` This tells the program to get basins at least this big. They must be smaller than `maximum_basin_size_pixels`.

• `only_take_largest_basin` When false it finds all basins in the size window, whereas if tru you only get the larges basin.

• `print_basin_raster: true` this prints a basin raster.

Run the driver and have a look at the new files.

If you load the basin raster in QGIS (it has the extension `AllBasins`)

Figure 4. Basins extracted from the DEM

You can try modifying some of the parameters like the minimum and maximum basin size and the flag `only_take_largest_basin` to see what you get.

#### 3.1.1. Geojson data

If you use the switch `convert_csv_to_geojson: true` the csv files will be converted to geojson files which can be loaded directly as shapefiles in a GIS. Have a look at our QGIS documents; we have instructions for loading "vector" data. Geojson files contain GIS-readable vector data.

### 3.2. Picking basins

1. If you ran the previous driver you will get a geojson file that has `_JN.geojson` in the name. If you load this data in a GIS you will see something like this:

Figure 5. Junctions in the DEM
Figure 6. Junction information in the DEM

You can see in the table to the right the junction number is 12.

2. If you want to pick certain junctions you can make a text file and just write the junction numbers you want in that text file.

3. We have added a junctions file in the directory with the data called `selected_WA.junctions`. It has a few junctions picked. The line to add to the parameter file are:

``BaselevelJunctions_file: /LSDTopoTools/dataExampleTopoDatasets/selected_WA.junctions``
 This line needs the entire path to your file. So you will probably need to go into the file and change the filename to match your directory structure.
4. Run the next parameter file (`WA_BasicMetrics05.driver`) and have a look at the basins generated. They will look something like this:

Figure 7. Selected basins

### 3.3. An important note on basin selection.

In LSDTopoTools basins are selected on the basis of junctions. But junctions have two or more contributing channels! The basin selected by a junction includes the channel going downstream that stops one pixel before the next junction. In this way we can select basins that are representative of a given Strahler order.

1. The next driver file is `WA_BasicMetrics06.driver` and it looks like this:

``````# These are parameters for the file i/o
write fname: WA_SixthExample

# Basic channel network
threshold_contributing_pixels: 5000

# Convert to json
convert_csv_to_geojson: true

# Getting the basins
find_basins: true
maximum_basin_size_pixels: 100000000
only_take_largest_basin: true

# Print the basin raster
print_chi_data_maps: true``````
2. The key element of this file is `print_chi_data_maps: true`. This prints a channel network that you can load into a GIS (the file has the extension `_chi_data_map`):

Figure 8. The channel network produced from the chi data maps
3. This looks a bit like the old channel network but the file contains much more information. If you open the csv file you will see the location of the points but also drainage area, elevation, flow distance, keys for identifying tributaries, and something called the chi coordinate, which you can read all about in a different part of the documentation.

4. You could, for example, make a chi-elevation plot using the data in the csv file:

Figure 9. A chi-elevation plot for the basin

## Appendix A: Analysis options for the lsdtt-basic-metrics program

All LSDTopoTools parameter files have the same format:

``````# comment
keyword: value
keywords with spaces: value``````
 The parameter file has a specific format, but the filename can be anything you want. We tend to use the extensions `.param` and `.driver` for these files, but you could use the extension `.MyDogSpot` if that tickled your fancy.
LSDTopoTools parameter file format
1. The `#` denotes a comment. The program will ignore line that start with this symbol.

2. Keywords or phrases are followed by a colon (`:`).

3. Keywords MUST be spelled exactly. They are not case sensitive. If you have a leading space it will not work. If you have a space before the colon (`:`) it will not work.

4. The order of the keywords do not matter.

5. If a keyword is not found, a default value is assigned. That is, you don’t need to worry about forgetting an essential parameter since they all are assigned default values.

Input format

Below are options for the parameter files. For these programs there are options for converting to point data, which requires georeferencing. Therefore, all DEMs must be in ENVI `bil` format (DO NOT use ArcMap’s bil format: these are two different things. See the section [Preparing your data] if you want more details). The reason we use `bil` format is because it retains georeferencing which is essential to our file output since many of the files output to `csv` format with latitude and longitude as coordinates.

### A.1. Basic file input and output

Table 1. File input and output options. These do not have defaults and MUST be declared.
Keyword Input type Description

write path

string

The path to which data is written. The code will NOT create a path: you need to make the write path before you start running the program.

string

The path from which data is read.

write fname

string

The prefix of rasters to be written without extension. For example if this is `Test` and you have selected `bil` format then a fill operation will result in a file called `Test_Fill.bil`.

string

The filename of the raster to be read without extension. For example if the raster is `MyRaster.bil`, read fname will be `MyRaster`.

string

The filename of a channel heads file. You can import channel heads. If this is set to `NULL` then the channels will be calculated using a pixel threshold.

### A.2. DEM preprocessing

Table 2. DEM preprocessing. These just help you clean data and perform very basic operations.
Keyword Input type Default value Description

minimum_elevation

float

0

If you have the `remove_seas` keyword set to true, the program will change any elevation node below this value to NoData.

maximum_elevation

float

30000

If you have the `remove_seas` keyword set to true, the program will change any elevation node above this value to NoData.

remove_seas

bool

false

If true, this changes extreme value in the elevation to NoData.

min_slope_for_fill

float

0.001

The minimum slope between pixels for use in the fill function.

raster_is_filled

bool

false

If true, the code assumes the raster is already filled and doesn’t perform the filling routine. This should save some time in computation, but make sure the raster really is filled or else you will get segmentation faults!

carve_before_fill

bool

false

If true, this runs a carving algoriothm before the fill function (Algorithm from Lindsay 2016). This breaches dams so that you don’t get giant flat areas.

only_check_parameters

bool

false

If true, this checks parameter values but doesn’t run any analyses. Mainly used to see if raster files exist.

### A.3. Raster trimming options (more preprocessing)

Table 3. These are more preprocessing routines specifically for trimming rasters
Keyword Input type Default value Description

remove_nodes_influenced_by_edge

bool

false

If true, this removes all pixels that are influenced by the edge or nodata. Influence is determined by D8 flow: The code starts at any node adjacent to the edge or nodata and then "erases" (converts to no data) all pixels downstream of this subset of pixels.

isolate_pixels_draining_to_fixed_channel

bool

false

If true, this only retains pixels from the DEM that drain to a set of points (usually a channel), which is stored in the fixed channel csv (see below).

fixed_channel_csv_name

string

single_channel_nodes

This is the name of a csv file that contains a list of nodes. It looks for node indices (it can find "ni", "nodeindex", or "index" in the csv) so is actually rather crap since you will need to update this file any time you change the raster. SMM needs to change this to read lat-long so it is not DEM-specific

print_trimmed_raster

bool

false

This is a slightly different trimmer: it finds the largest rectangular raster without nodata around the edges and prints to file.

trimming_buffer_pixels

int

0

THis is a parameter for the `print_trimmed_raster` option: it creates a buffer between the last nodata node and the edge of the DEM.

### A.4. Basic data output

Table 4. Basic printing operations. For simple rasters and network data that doesn’t require chi analysis.
Keyword Input type Default value Description

convert_csv_to_geojson

bool

false

If true, this converts any csv file (except for slope-area data) to geojson format. This format takes up much more space than csv (file sizes can be 10x larger) but is georeferenced and can be loaded directly into a GIS. Also useful for webmapping. It assumes your raster is in UTM coordinates, and prints points with latitude and longitude in WGS84.

print_raster_without_seas

bool

false

If true, prints a raster that has removed the seas (and very high peaks). This is useful if your NoDataValue is not registering and you use the `minimum_elevation`, `maximum_eleation`, and `remove_seas` flags to correct this. WARNING! This overwrites your original raster.

print_fill_raster

bool

false

If true, prints the fill raster.

bool

false

If true, prints the hillshade raster. The format of this is stupidly different from other printing calls for a stupid inheritance reason. Try to ignore. Most GIS routines have a hillshading options but for some reason they look crappier than our in-house hillshading. I’m not sure why but if you want a hillshade I recommend using this function.

print_distance_from_outlet

bool

false

Prints a raster that gives the distance from the outlet.

print_wiener_filtered_raster

bool

false

This returns a filtered raster using something called a Wiener filter. It is a rather fancy way to smooth topography. Note that this uses a memory-hungry fourier transform and so will struggle or even crash on large DEMs.

### A.5. Surface fitting

Table 5. These are options for polynomial surface fitting.
Keyword Input type Default value Description

float

30

The radius of the polynomial window over which the surface is fitted. If you have lidar data, we have found that a radius of 5-8 metres works best.

print_smoothed_elevation

bool

false

Prints a raster of elevations that have been smoothed over the polynomial window

print_slope

bool

false

If true, prints the topographic gradient raster.

print_aspect

bool

false

If true, prints the aspect raster.

print_curvature

bool

false

If true, prints the curvature raster.

print_planform_curvature

bool

false

If true, prints the planform curvature raster. That is the curvature of the countour lines.

print_profile_curvature

bool

false

If true, prints the profile curvature raster. That is the curvature along the line of steepest descent.

print_tangential_curvature

bool

false

If true, prints the tangential curvature raster. This is the curvature perpendicular to the line of steepest descent. A bit like the planform curvature but adjusted for slope.

print_point_classification

bool

false

If true, prints a point classification raster. This takes the value 1 if there is a peak, 2 if there is a depression and 3 if there is a saddle.

bool

false

If true, prints two rasters, for sloipes in each of the cardinal directions

calculate_basin_statistics

bool

false

If true, it goes thrugh the basin selection, and then prints statistics about slope and/or curvature for that basin. You must have print_slope and/or print_curvature set to true for this to work. The output goes into a csv file.

calculate_window_size

bool

false

It this is set to true, runs a calculation to estimate the best window size for surface fitting. Warning: this is computationally expensive and might take a while.

### A.6. Roughness calculation

Table 6. These are options for calculationg landscape roughness
Keyword Input type Default value Description

REI_critical_slope

float

1.0

Critical slope for the rock exposure index calculation

float

10.0

Radius for the window for the rock exposure index calculation

print_REI_raster

bool

false

If true, prints the REI to a raster

print_roughness_rasters

bool

false

If true, prints the S1,S2, and S3 rasters. See Milodwski et al, ESURF for details.

float

3.0

Radius for the window for the roughness calculation

### A.7. Drainage area extraction

Table 7. These are options for drainage area extraction.
Keyword Input type Default value Description

float

30

The radius of the polynomial window over which the surface is fitted. If you have lidar data, we have found that a radius of 5-8 metres works best.

print_dinf_drainage_area_raster

bool

false

If true, prints drainage area calculated using the d-infinity algorithm.

print_d8_drainage_area_raster

bool

false

If true, prints drainage area calculated using the d8 algorithm. This is simply the steepest of the 8 nearest neighbours.

print_QuinnMD_drainage_area_raster

bool

false

If true, prints drainage area calculated using the Quinn algorithm. This is a multiple flow direction algorithm.

print_FreemanMD_drainage_area_raster

bool

false

If true, prints drainage area calculated using the Freeman algorithm. This is a multiple flow direction algorithm.

print_MD_drainage_area_raster

bool

false

If true, prints drainage area calculated using the multidirectional algorithm. This is a multiple flow direction algorithm. Unlike the Quinn and Freeman algorithms it makes no attempt whatsoever to control dispersion.

### A.8. Basic channel extraction and printing

This simply gets a channel network and prints its location. It is a rather rudimentary way of seeing where channels are. More advanced options are in the next table.

Table 8. These are options for drainage area extraction.
Keyword Input type Default value Description

print_stream_order_raster

bool

false

If true, prints the stream order raster (but printing this to csv is more efficient, use `print_channels_to_csv`).

print_channels_to_csv

bool

false

Prints the channel network to a csv file. Includes stream order and other useful information. Much more memory efficient than printing the whole raster. It prints all channel nodes across the DEM rather than printing nodes upstream of selected basins. If you want to see the channels selected for chi analysis use `print_chi_data_maps`.

print_junction_index_raster

bool

false

If true, prints the junction index raster (but printing this to csv is more efficient, use `print_junctions_to_csv`).

print_junctions_to_csv

bool

false

Prints the junction indices to a csv file. Much more memory efficient than printing the whole raster.

print_junctions_angles_to_csv

bool

false

Prints the junction angles of each junction to a csv file. This has rather a lot of data outputs. It rejects junctions with more than two donors. It records the order of the junction and each of the two donors. It also records the drainage area of the junction and the two donors. It records the bearing of each of the three channels (all pointing away from the junction, so the two donors point upstream and the channel below the junction points downstream). It also records the angle between the two donors as well as the angle between the D1 and the downstream channel, and D2 and the downstream channel.

extract_single_channel

bool

false

If true, this takes a single source (entered as a lat-long in a csv file, see below) and follows it doenstream. A very easy way to get statistics from a single channel. The channel records flow distance and drainage area.

use_dinf_for_single_channel

bool

false

If true, records the dinf drainage area rather than D8 drainage area in the single channel csv

channel_source_fname

string

single_channel_source

Name of a csv file that has latitude and longitude as column headers. Only takes the first item in the file as the channel source. Used by `extract_single_channel`.

### A.9. More advanced channel and basin selection

These options give you a bit of control over selecting basins.

 If you just want the largest complete basin, set `find_largest_complete_basins: true` AND `maximum_basin_size_pixels: 10000000000000` (or any really big number).
Table 9. Options for determining which channels and basins to analyse, including settings for the fill function.
Keyword Input type Default value Description

find_basins

bool

false

If this is true, it i) Gets all the basins in a DEM and takes those between the `minimum_basin_size_pixels` and `maximum_basin_size_pixels`. It then removes basins that are influenced by the edge of the DEM, and then removes nested basins. The reason for removing basins draining the edge is that all drainage areas and chi coordinates require that the basin is complete. If not, your areas and chi coordinate, will be incorrect.

BaselevelJunctions_file

string

NULL

You can write a file that contains a list of junction numbers (to see where they are, use `print_junctions_to_csv`) to get basins above specific junctions only. The file format is just a list of integers.

string

NULL

This reads a channel heads file. It will supercede the `threshold_contributing_pixels` flag. That is, if you give a valid CHeads filename the code will ignore the threshold pixels and use the sources in the file instead. You can calculate channel heads using our channel extraction tools. The file needs to be a csv file and you pass the filename WITHOUT EXTENSION. The format of the filename is one with 5 columns: `node_index,row,col,x,y`. The `x,y` coordinates are in local UTM coordinates.

threshold_contributing_pixels

int

1000

The number of pixels required to generate a channel (i.e., the source threshold).

minimum_basin_size_pixels

int

5000

The minimum number of pixels in a basin for it to be retained. This operation works on the baselevel basins: subbasins within a large basin are retained.

maximum_basin_size_pixels

int

500000

The maximum number of pixels in a basin for it to be retained. This is only used by `find_complete_basins_in_window` but that algorithm for selecting basins is the default.

bool

true

If true, the channel network will extend beyond selected baselevel junctions downstream until it reaches the pixel before the receiver junction. If false, the channel simply extends upstream from the selected basin. The reason for this switch is because if one if extracting basins by drainage order, then the, say, a 2nd order drainage basin starts at the node immediately upstream of the most upstream 3rd order junction.

only_take_largest_basin

bool (true or 1 will work)

false

If this is true, a chi map is created based only upon the largest basin in the raster.

print_basin_raster

bool

false

If true, prints a raster with the basins. IMPORTANT! This should be set to true if you want to use any of our python plotting functions that use basin information. Note that if this is true it will also print csv files with basin numbers and source numbers to assist plotting.

print_chi_data_maps

bool

false

This prints the channel networks (a bit like `print_channels_to_csv`) but contains MUCH more informatioon: elevation, flow distance, dranage area (from d8), the chi coordinate (have a look at our chi documentation for more details) and various keys to sources and basins so you can colour or sort channels by basin or tributary if you want. If you are going to work with channels using LSDTT_BasicMetrics this is the output to use.

#### A.9.1. Basic parameters for the chi coordinate

Table 10. Parameters for calculating the chi coordinate.
Keyword Input type Default value Description

A_0

float

1

The A0 parameter (which nondimensionalises area) for chi analysis. This is in m2. Note that when A0 = 1 then the slope in chi space is the same as the channel steepness index (often denoted by ks).

m_over_n

float

0.5

The m/n parameter (sometimes known as the concavity index) for calculating chi. Note that if you do any m/n analysis (either `calculate_MLE_collinearity` or `print_profiles_fxn_movern_csv`) this m/n value will be replaced.

### A.10. Example parameter files

We have a number of example parameter files in the repository LSDTT_chi_examples. The chapter on examples will walk you through the various things these files do.


text:
# AN EXTENSION OF GENERALIZED VECTOR QUASI-VARIATIONAL INEQUALITY

• Kum Sang-Ho ;
• Kim Won-Kyu
• Published : 2006.04.01
• 70 19

#### Abstract

In this paper, we shall give an affirmative answer to the question raised by Kim and Tan [1] dealing with generalized vector quasi-variational inequalities which generalize many existence results on (VVI) and (GVQVI) in the literature. Using the maximal element theorem, we derive two theorems on the existence of weak solutions of (GVQVI), one theorem on the existence of strong solution of (GVQVI), and one theorem on strong solution in the 1-dimensional case.

#### Keywords

generalized vector quasi-variational inequality;equilibrium

#### References

1. N. Bourbaki, Topological Vector Spaces (translated by H. G. Eggleston and S. Madan), Springer-Verlag, New York, 1987
2. X. -P. Ding, W. K. Kim, and K. -K. Tan, Equilibria of non-compact generalized games with L$^*$-majorized preferences, J. Math. Anal. Appl. 164 (1992), 508-517 https://doi.org/10.1016/0022-247X(92)90130-6
3. H. Kneser, Sur un theoreme fondamental de la theorie des jeux, C. R. Acad. Sci. Paris 234 (1952), 2418-2420
4. P. Q. Khanh and L. M. Luu, On the existence of solutions to vector quasivariational inequalities and quasi-complementarity problems with applications to traffic network equilibria, J. Optim. Theory Appl. 123 (2004), 533-548 https://doi.org/10.1007/s10957-004-5722-3
5. Y. Chiang, O. Chadli, and J. C. Yao, Existence of solutions to implicit vector variational inequalities, J. Optim. Theory Appl, 116 (2003), 251-264 https://doi.org/10.1023/A:1022472103162
6. W. K. Kim and K. -K. Tan, On generalized vector quasi-variational inequalities, Optimization 46 (1999), 185-198 https://doi.org/10.1080/02331939908844451
7. X. -P. Ding, W. K. Kim, and K. -K. Tan, Equilibria of generalized games with L-majorized multifunctions, Int. J. Math. Math. Sci. 17 (1994), 783-790 https://doi.org/10.1155/S0161171294001092

format: plain


text:
# Search for the doubly charmed baryon $\Xi_{cc}^+$

[to restricted-access page]

## Abstract

A search for the doubly charmed baryon Xi_cc^+ in the decay mode Xi_cc^+ -> Lambda_c^+ K^- pi^+ is performed with a data sample, corresponding to an integrated luminosity of 0.65/fb, of pp collisions recorded at a centre-of-mass energy of 7 TeV. No significant signal is found in the mass range 3300-3800 MeV/c^2. Upper limits at the 95% confidence level on the ratio of the Xi_cc^+ production cross-section times branching fraction to that of the Lambda_c^+, R, are given as a function of the Xi_cc^+ mass and lifetime. The largest upper limits range from R < 1.5 x 10^-2 for a lifetime of 100 fs to R < 3.9 x 10^-4 for a lifetime of 400 fs.

## Figures and captions

 Invariant mass spectrum of $\Lambda _ c ^+ \rightarrow p K ^- \pi ^+$ candidates for 5$\%$ of the data, with events chosen at random during preselection (due to bandwidth limits for the normalisation mode). The dashed line shows the fitted background contribution, and the solid line the sum of $\Lambda _ c ^+$ signal and background. pub-Lc-bw.pdf [25 KiB] HiDef png [151 KiB] Thumbnail [152 KiB] *.C file The distribution of the invariant mass difference $\delta m$, defined in Eq. 3, for simulated $\Xi_{ c c }^+$ events with a $\Xi_{ c c }^+$ mass of 3500 ${\mathrm{ Me V /}c^2}$ . The solid line shows the fitted signal shape. In order to increase the available statistics, the trigger and ANN requirements are not applied in this plot. pub-Xi[..].pdf [22 KiB] HiDef png [149 KiB] Thumbnail [142 KiB] *.C file Spectrum of $\delta m$ requiring $2273 < m([ p K ^- \pi ^+ ]_{\Lambda _ c }) < 2303$ ${\mathrm{ Me V /}c^2}$ . Both plots show the same data sample, but with different $\delta m$ ranges and binnings. The wide signal region is shown in the right plot and indicated by the dotted vertical lines in the left plot. pub-sp[..].pdf [17 KiB] HiDef png [146 KiB] Thumbnail [157 KiB] *.C file pub-sp[..].pdf [18 KiB] HiDef png [171 KiB] Thumbnail [180 KiB] *.C file Measured signal yields as a function of $\delta m$. The upper two plots show the estimated signal yield as a dark line and the $\pm 1\sigma$ statistical error bands as light grey lines for (upper left) the baseline method and (upper right) the cross-check method. The central values of the two methods are compared in the lower plot and found to agree well. pub-yi[..].pdf [23 KiB] HiDef png [480 KiB] Thumbnail [296 KiB] *.C file pub-yi[..].pdf [23 KiB] HiDef png [419 KiB] Thumbnail [268 KiB] *.C file pub-yi[..].pdf [20 KiB] HiDef png [274 KiB] Thumbnail [228 KiB] *.C file Upper limits on $R$ at the 95% CL as a function of $\delta m$, for five $\Xi_{ c c }^+$ lifetime hypotheses. pub-li[..].pdf [29 KiB] HiDef png [351 KiB] Thumbnail [302 KiB] *.C file Mass difference spectrum requiring $2273 < m([ p K ^- \pi ^+ ]_{\Lambda _ c }) < 2303$ ${\mathrm{ Me V /}c^2}$ . Candidates are also required to be consistent with (left) an intermediate $\Sigma_{ c }(2455)^{++}$, (right) an intermediate $\Sigma_{ c }(2520)^{++}$. pub-sp[..].pdf [14 KiB] HiDef png [110 KiB] Thumbnail [122 KiB] *.C file pub-sp[..].pdf [14 KiB] HiDef png [115 KiB] Thumbnail [127 KiB] *.C file Animated gif made out of all figures. PAPER-2013-049.gif Thumbnail

## Tables and captions

 Systematic uncertainties on the single-event sensitivity $\alpha$. Table_1.pdf [24 KiB] HiDef png [156 KiB] Thumbnail [65 KiB] tex code Single-event sensitivity $\alpha$ for different lifetime hypotheses $\tau$, assuming $m(\Xi_{ c c }^+ )=3500$ ${\mathrm{ Me V /}c^2}$ . The uncertainties quoted include statistical and systematic effects, and are correlated between different lifetime hypotheses. Table_2.pdf [40 KiB] HiDef png [150 KiB] Thumbnail [56 KiB] tex code Variation in single-event sensitivity for different mass hypotheses $m(\Xi_{ c c }^+ )$, assuming $\tau=333$ $\rm fs$ . The uncertainties quoted include statistical and systematic effects, and are correlated between different mass hypotheses. The variation is shown separately for all effects other than the efficiency of the $\delta m$ window ($\alpha_u$), for the correction due to the mass-dependent resolution, and for the combination ($\alpha$). Table_3.pdf [51 KiB] HiDef png [54 KiB] Thumbnail [27 KiB] tex code Expected value of the signal yield $N_{\text{sig}}$ for different values of $R$ and lifetime hypotheses, assuming $m(\Xi_{ c c }^+ )=3500$ ${\mathrm{ Me V /}c^2}$ . The uncertainties quoted are due to the systematic uncertainty on $\alpha$. Table_4.pdf [41 KiB] HiDef png [85 KiB] Thumbnail [42 KiB] tex code Largest values of the upper limits (UL) on $R$ at the 95% CL in blocks of $\delta m$ for a range of lifetime hypotheses, given in units of $10^{-3}$. The largest values across the entire 500 ${\mathrm{ Me V /}c^2}$ range are also shown. Table_5.pdf [38 KiB] HiDef png [144 KiB] Thumbnail [71 KiB] tex code

## Supplementary Material [file]

 Colour versions of figures in LHCb-PAPER-2013-049. Fig1.pdf [25 KiB] HiDef png [175 KiB] Thumbnail [150 KiB] *C file Fig2.pdf [23 KiB] HiDef png [174 KiB] Thumbnail [146 KiB] *C file Fig3a.pdf [17 KiB] HiDef png [155 KiB] Thumbnail [154 KiB] *C file Fig4a.pdf [23 KiB] HiDef png [560 KiB] Thumbnail [289 KiB] *C file Fig4b.pdf [23 KiB] HiDef png [490 KiB] Thumbnail [261 KiB] *C file Fig4c.pdf [20 KiB] HiDef png [402 KiB] Thumbnail [204 KiB] *C file Fig5.pdf [29 KiB] HiDef png [467 KiB] Thumbnail [286 KiB] *C file

Created on 19 October 2019.


text:
# How Can I Get Rid Of Chipmunks Chipmunks How Can You Get Rid Of Chipmunks In The Garage

how can i get rid of chipmunks chipmunks how can you get rid of chipmunks in the garage.

how to get rid of chipmunks under porch insulation,how do i get rid of chipmunks under my deck,how to get rid of chipmunks under porch ceiling,how to get rid of chipmunks under porch roof,how to get rid of chipmunks under porch enclosures,how can you get rid of chipmunks in the garage,how can i get rid of chipmunks in my yard,how can i get rid of chipmunks in my garden,how can i get rid of chipmunks in my house,how to get rid of chipmunks under porch,how do i get rid of chipmunks without killing them softly movie.


text:
#### Archived

This topic is now archived and is closed to further replies.

# making a maze game

This topic is 5982 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I am trying to make a maze game on a console application. I''ve created a text file containing a maze I drew using ASCII text. How do I display this maze in the console application and make it so the user can move through the maze? I would most appreciate some syntax with explanations because I am just a beginner. I am especially wondering about wall detection (how to set it so user cannot move through walls). Any help would be great, thanks so much applekid

##### Share on other sites

The first and easiest way is the wall detection.

You make an array of your maze''s width*height like this (console)
int Maze[80][25];

and for wall, you use number 1, for floor, you use number 0. And then when you move, you check your next step (i.e. you stepped left) and see if there''s a wall there, if not, then move there, like this:

  if(PLAYER_LEFT) //however you code your movement{   if(Maze[x-1][y] != 1) //x and y is player position   {      x--; //moves left   } //no need for else because there''s nothing to do}

Now for the ASCII text display, I think there''s a file called conio.h that works with Borland C++ (the one I used at school) but I don''t know how to do it with Microsoft VC++ (yet).

With conio.h you could do this:
for(int x = 0; x < 80; x++) //the horizontal row of the maze
for(int y = 0; y < 25; y++) //the vertical row of the maze
{
gotoxy(x,y); // x and y is the array position for when you do a loop
if(Maze[x][y] == 1) //it is a wall
cout << ''+'';
}

But if you have MSVC++ then you need to do a little research on how to do this gotoxy feature.

If you have Borland, you can also do this someChar = kbhit() with conio.h, and it gets the key that you press (if you use a for left, it gets a and you deal with it). if MSVC++, then you have to do research also.

I guess that''s everything that you need to know.

If you need help, send me email at Bartrack@yahoo.com, I''ve been a beginner so don''t worry. Oh also, for the array of your map, you load in your file into that.

You know your game is in trouble when your AI says, in a calm, soothing voice, "I''m afraid I can''t let you do that, Dave"

1. 1
2. 2
3. 3
Rutin
14
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633701
• Total Posts
3013437
×


text:
Lemma 21.22.2. Let $I$ be an ideal of a ring $A$. Let $\mathcal{C}$ be a site. Let

$\ldots \to \mathcal{F}_3 \to \mathcal{F}_2 \to \mathcal{F}_1$

be an inverse system of $A$-modules on $\mathcal{C}$ such that $\mathcal{F}_ n = \mathcal{F}_{n + 1}/I^ n\mathcal{F}_{n + 1}$. Let $p \geq 0$. Given $n$ define

$N_ n = \bigcap \nolimits _{m \geq n} \mathop{\mathrm{Im}}\left( H^{p + 1}(\mathcal{C}, I^ n\mathcal{F}_{m + 1}) \to H^{p + 1}(\mathcal{C}, I^ n\mathcal{F}_{n + 1}) \right)$

If $\bigoplus N_ n$ satisfies the ascending chain condition as a graded $\bigoplus _{n \geq 0} I^ n/I^{n + 1}$-module, then the inverse system $M_ n = H^ p(\mathcal{C}, \mathcal{F}_ n)$ satisfies the Mittag-Leffler condition1.

Proof. The proof is exactly the same as the proof of Lemma 21.22.1. In fact, the result will follow from the arguments given there as soon as we show that $\bigoplus N_ n$ is a graded $\bigoplus _{n \geq 0} I^ n/I^{n + 1}$-submodule of $\bigoplus H^{p + 1}(\mathcal{C}, I^ n\mathcal{F}_{n + 1})$ and that the boundary maps $\delta _ n : M_ n \to H^{p + 1}(\mathcal{C}, I^ n\mathcal{F}_{n + 1})$ have image contained in $N_ n$.

Suppose that $\xi \in N_ n$ and $f \in I^ k$. Choose $m \gg n + k$. Choose $\xi ' \in H^{p + 1}(\mathcal{C}, I^ n\mathcal{F}_{m + 1})$ lifting $\xi$. We consider the diagram

$\xymatrix{ 0 \ar[r] & I^ n\mathcal{F}_{m + 1} \ar[d]_ f \ar[r] & \mathcal{F}_{m + 1} \ar[d]_ f \ar[r] & \mathcal{F}_ n \ar[d]_ f \ar[r] & 0 \\ 0 \ar[r] & I^{n + k}\mathcal{F}_{m + 1} \ar[r] & \mathcal{F}_{m + 1} \ar[r] & \mathcal{F}_{n + k} \ar[r] & 0 }$

constructed as in the proof of Lemma 21.22.1. We get an induced map on cohomology and we see that $f \xi ' \in H^{p + 1}(\mathcal{C}, I^{n + k}\mathcal{F}_{m + 1})$ maps to $f \xi$. Since this is true for all $m \gg n + k$ we see that $f\xi$ is in $N_{n + k}$ as desired.

To see the boundary maps $\delta _ n$ have image contained in $N_ n$ we consider the diagrams

$\xymatrix{ 0 \ar[r] & I^ n\mathcal{F}_{m + 1} \ar[d] \ar[r] & \mathcal{F}_{m + 1} \ar[d] \ar[r] & \mathcal{F}_ n \ar[d] \ar[r] & 0 \\ 0 \ar[r] & I^ n\mathcal{F}_{n + 1} \ar[r] & \mathcal{F}_{n + 1} \ar[r] & \mathcal{F}_ n \ar[r] & 0 }$

for $m \geq n$. Looking at the induced maps on cohomology we conclude. $\square$

[1] In fact, there exists a $c \geq 0$ such that $\mathop{\mathrm{Im}}(M_ n \to M_{n - c})$ is the stable image for all $n \geq c$.

In your comment you can use Markdown and LaTeX style mathematics (enclose it like $\pi$). A preview option is available if you wish to see how it works out (just click on the eye in the toolbar).


text:
# tenor basis swap spreads and compounding

Let's say I have a 3mv6m tenor basis swap that is quoted at a spread of x bp (and it is a spread on the 3m leg while the 6m leg is the flat leg). Nowadays, I think the convention in most currencies is to compound the 3m rate so that there is a single payment only at the 6m schedule. For this case I have 2 questions related to the spread and handling of the compounding:

1) is the spread of x bp quoted as a 3m compounded spread (like it was before when there was no compounding) or a 6m compounded spread (to be directly added to a 3m rate compounded to 6m)?

2) assuming the x bp spread is a normal 3m spread: is the implied 3m cashflow (incl. spread cashflow) compounded with the 3m rate flat (i.e. no compounding with spread included)?

Anybody trading tenor basis swaps here?

TIA for any feedback.

This would be specified in the ISDA or term sheet. There are four alternative methods:

No compounding: Meaning neither the rate nor the spread get compounded.

Compounding: Meaning both the spread and the libor rate get compounded.

Spread exclusive compounding:Meaning the libor get compounded but the spread does not. This was not covered by ISDA 2006 but was quite widespread.

Flat compounding: Slightly more involved, but in your example of 3mV6m, would mean that the first 3m of the quarterly leg gets compounded at the interest rate (excluding spread) but then the amount of first sub period would include spread. So you can see it’s half way between the two extremes.

The calculations are detailed in the below excel file:

https://www.isda.org/a/aKiDE/compounding-worked-examples.xls

Convention for most currencies is flat compounding. This includes the most liquid G4 basis swaps:

• EUR 3m vs 6m, 3m vs 12m, 1m vs 3m
• USD 1m vs 3m, 3m vs 6m
• GBP 3m vs 6m, 1m vs 3m
• JPY 3m vs 6m, 1m vs 6m, 1m vs 3m

Typically the spread is quoted in terms of the leg with the shorter tenor.

Two notable exceptions are EONIA v 3m and the (relatively new) SOFR v FF basis swaps. Here we exclude the spread rather than use flat compounding.

• in GBP between 2002 and 2015 I never saw a single compounded basis swap. Q payments were made every quarter (without being compounded to the next quarter), and S payments were made half year. Of course another approach is to book 3m +some spread or 6m -some other spread. This was distinctly different to the way USD basis trades were booked, in my historic experience, which were genuinely compounded. SONIA-3M were always booked as 3M minus some spread. – Attack68 May 30 at 12:49


text:
# American Institute of Mathematical Sciences

February  2013, 33(2): 739-755. doi: 10.3934/dcds.2013.33.739

## Uniqueness of harmonic map heat flows and liquid crystal flows

 1 Department of Mathematics, South China University of Technology, Guangzhou, 510640

Received  July 2011 Revised  January 2012 Published  September 2012

In this paper, we prove a limiting uniqueness criterion to harmonic map heat flows and liquid crystal flows. We firstly establish the uniqueness of harmonic map heat flows from $R^n$ to a smooth, compact Riemannian manifold $N$ in the class $C([0,T),BMO_T(R^n,N))\cap L^\infty_{loc}((0,T);\dot{W}^{1,\infty}(R^n))$ for $0< T ≤ +\infty.$ For the nematic liquid crystal flows $(v,d)$, we show that the mild solution is unique under the class $C([0,T),BMO_T^{-1}(R^n))\cap L^\infty_{loc}((0,T);L^\infty(R^n))\times C([0,T),BMO_T(R^n,S^2))\cap L^\infty_{loc}((0,T);\dot{W}^{1,\infty}(R^n))$ for $0< T ≤ +\infty.$
Citation: Junyu Lin. Uniqueness of harmonic map heat flows and liquid crystal flows. Discrete and Continuous Dynamical Systems, 2013, 33 (2) : 739-755. doi: 10.3934/dcds.2013.33.739
##### References:
 [1] Y. Chen and W. Y. Ding, Blow up and global existence for heat flows of harmonic maps, Invent. Math., 99 (1990), 567-578. doi: 10.1007/BF01234431. [2] K. Chang, W. Ding and R. Ye, Finite time blow-up of the heat flow of harmonic maps from surfaces, JDG, 36 (1992), 507-515. [3] J. M. Coron and J. M. Ghidaglia, Explosion en temps fini pour le flot des applications harmoniques, C. R. Acad. Sci. Paris, 308 (1989), 339-344. [4] Y. Chen and M. Struwe, Existence and partial regularity results for the heat flow of harmonic maps, Math. Z., 201 (1989), 83-103. doi: 10.1007/BF01161997. [5] J. L. Ericksen, Hydrostatic theory of liquid crystal, Arch. Rational Mech. Anal., 9 (1962), 371-378. [6] J. Eells and J. Sampson, Harmonic mappings of Riemannian manifolds, Amer. J. Math., 86 (1964), 109-160. doi: 10.2307/2373037. [7] A. Freire, Uniqueness for the harmonic map flow from surfaces to general targets, Comm. Math. Helvetici., 70 (1995), 310-338. doi: 10.1007/BF02566010. [8] P. G. de Gennes and J. Prost, "The Physics of Liquid Crystals," New York, Oxford University Press, 1993. [9] J. Jost, Ein existenzbeiweis fiir harmonisch Abbildungen, die ein Dirichlet problem 16sen mittels der methode des warmeflusses, Manuscripta Math., 34 (1981), 17-25. doi: 10.1007/BF01168706. [10] H. Koch and D. Tataru, Well-posedness for theNavier-Stokes equations, Adv. Math., 157 (2001), 22-35. doi: 10.1006/aima.2000.1937. [11] F. M. Leslie, Some constitutive equations for liquid crystals, Arch. Rational Mech. Anal., 28 (1968), 265-283. doi: 10.1007/BF00251810. [12] J. Y. Lin and S. J. Ding, On the well-posedness for the heat flow of harmonic maps and hydrodynamic flow of nematic liquid crystals in critical spaces, Math. Meth. Appl. Sciences, DOI: 10.1002/mma.1548. doi: 10.1002/mma.1548. [13] F. Lin and C. Liu, Nonparabolic dissipative systems modeling the flow of liquid crystals, Comm. Pure Appl. Math., 48 (1995), 501-537. [14] F. Lin and C. Liu, Partial regularities of nonlinear disspative systems modeling the flow of liquid crystals, DCDS, 2 (1996), 1-23. [15] F. Lin and C. Liu, Existence of solutions for the Ericksen-Leslie system, Arch. Rational Mech. Aanl., 154 (2000), 135-156. [16] F. H. Lin, J. Y. Lin and C. Y. Wang, Liquid crystal flow in two dimensions, Arch. Ration. Mech. Anal., 197 (2010), 297-336. doi: 10.1007/s00205-009-0278-x. [17] F. Lin and C. Wang, On the uniqueness of heat flow of harmonic maps and hydrodynamic flow of nematic liquid crystals, Chinese Annals of Mathematics, 31 (2010), 921-938. doi: 10.1007/s11401-010-0612-5. [18] H. Miura, Remark on uniqueness of mild solutions to the Navier-Stokes equations, J. Funt. Anal., 218 (2005), 110-129. doi: 10.1016/j.jfa.2004.07.007. [19] M. Struwe, On the evolution of harmonic maps in higher dimensions, J. Diff. Geom., 28 (1988), 485-502. [20] A. Soyeur, A global existence result for the heat flow of harmonic maps, Comm. PDE, 15 (1990), 237-244. doi: 10.1080/03605309908820685. [21] M. Struwe, On the evolution of harmonic maps of Riemannian surfaces, Comment. Math. Helv, 60 (1985), 558-581. doi: 10.1007/BF02567432. [22] C. Wang, Well-posedness for the heat flow of harmonic maps and the liquid crystal flow with rough initial data, Arch. Rational Mech. Anal., 200 (2011), 1-19. [23] X. Xu and Z. Zhang, Global regularity and uniqueness of weak solution for the 2-D liquid crystal flows, JDE, 252 (2012), 1169-1181. doi: 10.1016/j.jde.2011.08.028.

show all references

##### References:
 [1] Y. Chen and W. Y. Ding, Blow up and global existence for heat flows of harmonic maps, Invent. Math., 99 (1990), 567-578. doi: 10.1007/BF01234431. [2] K. Chang, W. Ding and R. Ye, Finite time blow-up of the heat flow of harmonic maps from surfaces, JDG, 36 (1992), 507-515. [3] J. M. Coron and J. M. Ghidaglia, Explosion en temps fini pour le flot des applications harmoniques, C. R. Acad. Sci. Paris, 308 (1989), 339-344. [4] Y. Chen and M. Struwe, Existence and partial regularity results for the heat flow of harmonic maps, Math. Z., 201 (1989), 83-103. doi: 10.1007/BF01161997. [5] J. L. Ericksen, Hydrostatic theory of liquid crystal, Arch. Rational Mech. Anal., 9 (1962), 371-378. [6] J. Eells and J. Sampson, Harmonic mappings of Riemannian manifolds, Amer. J. Math., 86 (1964), 109-160. doi: 10.2307/2373037. [7] A. Freire, Uniqueness for the harmonic map flow from surfaces to general targets, Comm. Math. Helvetici., 70 (1995), 310-338. doi: 10.1007/BF02566010. [8] P. G. de Gennes and J. Prost, "The Physics of Liquid Crystals," New York, Oxford University Press, 1993. [9] J. Jost, Ein existenzbeiweis fiir harmonisch Abbildungen, die ein Dirichlet problem 16sen mittels der methode des warmeflusses, Manuscripta Math., 34 (1981), 17-25. doi: 10.1007/BF01168706. [10] H. Koch and D. Tataru, Well-posedness for theNavier-Stokes equations, Adv. Math., 157 (2001), 22-35. doi: 10.1006/aima.2000.1937. [11] F. M. Leslie, Some constitutive equations for liquid crystals, Arch. Rational Mech. Anal., 28 (1968), 265-283. doi: 10.1007/BF00251810. [12] J. Y. Lin and S. J. Ding, On the well-posedness for the heat flow of harmonic maps and hydrodynamic flow of nematic liquid crystals in critical spaces, Math. Meth. Appl. Sciences, DOI: 10.1002/mma.1548. doi: 10.1002/mma.1548. [13] F. Lin and C. Liu, Nonparabolic dissipative systems modeling the flow of liquid crystals, Comm. Pure Appl. Math., 48 (1995), 501-537. [14] F. Lin and C. Liu, Partial regularities of nonlinear disspative systems modeling the flow of liquid crystals, DCDS, 2 (1996), 1-23. [15] F. Lin and C. Liu, Existence of solutions for the Ericksen-Leslie system, Arch. Rational Mech. Aanl., 154 (2000), 135-156. [16] F. H. Lin, J. Y. Lin and C. Y. Wang, Liquid crystal flow in two dimensions, Arch. Ration. Mech. Anal., 197 (2010), 297-336. doi: 10.1007/s00205-009-0278-x. [17] F. Lin and C. Wang, On the uniqueness of heat flow of harmonic maps and hydrodynamic flow of nematic liquid crystals, Chinese Annals of Mathematics, 31 (2010), 921-938. doi: 10.1007/s11401-010-0612-5. [18] H. Miura, Remark on uniqueness of mild solutions to the Navier-Stokes equations, J. Funt. Anal., 218 (2005), 110-129. doi: 10.1016/j.jfa.2004.07.007. [19] M. Struwe, On the evolution of harmonic maps in higher dimensions, J. Diff. Geom., 28 (1988), 485-502. [20] A. Soyeur, A global existence result for the heat flow of harmonic maps, Comm. PDE, 15 (1990), 237-244. doi: 10.1080/03605309908820685. [21] M. Struwe, On the evolution of harmonic maps of Riemannian surfaces, Comment. Math. Helv, 60 (1985), 558-581. doi: 10.1007/BF02567432. [22] C. Wang, Well-posedness for the heat flow of harmonic maps and the liquid crystal flow with rough initial data, Arch. Rational Mech. Anal., 200 (2011), 1-19. [23] X. Xu and Z. Zhang, Global regularity and uniqueness of weak solution for the 2-D liquid crystal flows, JDE, 252 (2012), 1169-1181. doi: 10.1016/j.jde.2011.08.028.
 [1] T. Tachim Medjo. On the existence and uniqueness of solution to a stochastic simplified liquid crystal model. Communications on Pure and Applied Analysis, 2019, 18 (5) : 2243-2264. doi: 10.3934/cpaa.2019101 [2] Domenico Mucci. Maps into projective spaces: Liquid crystal and conformal energies. Discrete and Continuous Dynamical Systems - B, 2012, 17 (2) : 597-635. doi: 10.3934/dcdsb.2012.17.597 [3] Zhaoyang Qiu, Yixuan Wang. Martingale solution for stochastic active liquid crystal system. Discrete and Continuous Dynamical Systems, 2021, 41 (5) : 2227-2268. doi: 10.3934/dcds.2020360 [4] Zhenlu Cui, M. Carme Calderer, Qi Wang. Mesoscale structures in flows of weakly sheared cholesteric liquid crystal polymers. Discrete and Continuous Dynamical Systems - B, 2006, 6 (2) : 291-310. doi: 10.3934/dcdsb.2006.6.291 [5] Shanshan Guo, Zhong Tan. Energy dissipation for weak solutions of incompressible liquid crystal flows. Kinetic and Related Models, 2015, 8 (4) : 691-706. doi: 10.3934/krm.2015.8.691 [6] Jihong Zhao, Qiao Liu, Shangbin Cui. Global existence and stability for a hydrodynamic system in the nematic liquid crystal flows. Communications on Pure and Applied Analysis, 2013, 12 (1) : 341-357. doi: 10.3934/cpaa.2013.12.341 [7] Chun Liu, Huan Sun. On energetic variational approaches in modeling the nematic liquid crystal flows. Discrete and Continuous Dynamical Systems, 2009, 23 (1&2) : 455-475. doi: 10.3934/dcds.2009.23.455 [8] Chun Liu, Jie Shen. On liquid crystal flows with free-slip boundary conditions. Discrete and Continuous Dynamical Systems, 2001, 7 (2) : 307-318. doi: 10.3934/dcds.2001.7.307 [9] Xiaoli Li, Boling Guo. Well-posedness for the three-dimensional compressible liquid crystal flows. Discrete and Continuous Dynamical Systems - S, 2016, 9 (6) : 1913-1937. doi: 10.3934/dcdss.2016078 [10] Zhenlu Cui, Qi Wang. Permeation flows in cholesteric liquid crystal polymers under oscillatory shear. Discrete and Continuous Dynamical Systems - B, 2011, 15 (1) : 45-60. doi: 10.3934/dcdsb.2011.15.45 [11] Qiang Tao, Ying Yang. Exponential stability for the compressible nematic liquid crystal flow with large initial data. Communications on Pure and Applied Analysis, 2016, 15 (5) : 1661-1669. doi: 10.3934/cpaa.2016007 [12] Sili Liu, Xinhua Zhao, Yingshan Chen. A new blowup criterion for strong solutions of the compressible nematic liquid crystal flow. Discrete and Continuous Dynamical Systems - B, 2020, 25 (11) : 4515-4533. doi: 10.3934/dcdsb.2020110 [13] Yang Liu, Xin Zhong. On the Cauchy problem of 3D nonhomogeneous incompressible nematic liquid crystal flows with vacuum. Communications on Pure and Applied Analysis, 2020, 19 (11) : 5219-5238. doi: 10.3934/cpaa.2020234 [14] Francisco Guillén-González, Mouhamadou Samsidy Goudiaby. Stability and convergence at infinite time of several fully discrete schemes for a Ginzburg-Landau model for nematic liquid crystal flows. Discrete and Continuous Dynamical Systems, 2012, 32 (12) : 4229-4246. doi: 10.3934/dcds.2012.32.4229 [15] Jishan Fan, Fei Jiang. Large-time behavior of liquid crystal flows with a trigonometric condition in two dimensions. Communications on Pure and Applied Analysis, 2016, 15 (1) : 73-90. doi: 10.3934/cpaa.2016.15.73 [16] Yang Liu, Sining Zheng, Huapeng Li, Shengquan Liu. Strong solutions to Cauchy problem of 2D compressible nematic liquid crystal flows. Discrete and Continuous Dynamical Systems, 2017, 37 (7) : 3921-3938. doi: 10.3934/dcds.2017165 [17] Yinxia Wang. A remark on blow up criterion of three-dimensional nematic liquid crystal flows. Evolution Equations and Control Theory, 2016, 5 (2) : 337-348. doi: 10.3934/eect.2016007 [18] Dongfen Bian, Yao Xiao. Global well-posedness of non-isothermal inhomogeneous nematic liquid crystal flows. Discrete and Continuous Dynamical Systems - B, 2021, 26 (3) : 1243-1272. doi: 10.3934/dcdsb.2020161 [19] Hao Wu. Long-time behavior for nonlinear hydrodynamic system modeling the nematic liquid crystal flows. Discrete and Continuous Dynamical Systems, 2010, 26 (1) : 379-396. doi: 10.3934/dcds.2010.26.379 [20] Shengquan Liu, Jianwen Zhang. Global well-posedness for the two-dimensional equations of nonhomogeneous incompressible liquid crystal flows with nonnegative density. Discrete and Continuous Dynamical Systems - B, 2016, 21 (8) : 2631-2648. doi: 10.3934/dcdsb.2016065

2020 Impact Factor: 1.392


text:
Implementation

# How to Create a Custom 2D Physics Engine: The Basics and Impulse Resolution

by

There are many reasons you might want to create a custom physics engine: first, learning and honing your skills in mathematics, physics and programming are great reasons to attempt such a project; second, a custom physics engine can tackle any sort of technical effect the creator has the skill to create. In this article I would like to provide a solid introduction on how to create a custom physics engine entirely from scratch.

Physics provides a wonderful means for allowing a player to immerse themselves within a game. It makes sense that a mastery of a physics engine would be a powerful asset for any programmer to have at their disposal. Optimizations and specializations can be made at any time due to a deep understanding of the inner workings of the physics engine.

By the end of this tutorial the following topics will have been covered, in two dimensions:

• Simple collision detection
• Simple manifold generation
• Impulse resolution

Here's a quick demo:

Note: Although this tutorial is written using C++, you should be able to use the same techniques and concepts in almost any game development environment.

## Prerequisites

This article involves a fair amount of mathematics and geometry, and to a much lesser extent actual coding. A couple prerequisites for this article are:

• A basic understanding of simple vector math
• The ability to perform algebraic math

## Collision Detection

There are quite a few articles and tutorials throughout the internet, including here on Tuts+, that cover collision detection. Knowing this, I would like to run through the topic very quickly as this section is not the focus of this article.

### Axis Aligned Bounding Boxes

An Axis Aligned Bounding Box (AABB) is a box that has its four axes aligned with the coordinate system in which it resides. This means it is a box that cannot rotate, and is always squared off at 90 degrees (usually aligned with the screen). In general it is referred to as a "bounding box" because AABBs are used to bound other more complex shapes.

The AABB of a complex shape can be used as a simple test to see if more complex shapes inside the AABBs can possibly be intersecting. However in the case of most games the AABB is used as a fundamental shape, and does not actually bound anything else. The structure of your AABB is important. There are a few different ways to represent an AABB, however this is my favorite:

struct AABB
{
Vec2 min;
Vec2 max;
};

This form allows an AABB to be represented by two points. The min point represents the lower bounds of the x and y axis, and max represents the higher bounds - in other words, they represent the top left and bottom right corners. In order to tell whether two AABB shapes are intersecting you will need to have a basic understanding of the Separating Axis Theorem (SAT).

Here's a quick test taken from Real-Time Collision Detection by Christer Ericson, which makes use of the SAT:

bool AABBvsAABB( AABB a, AABB b )
{
// Exit with no intersection if found separated along an axis
if(a.max.x < b.min.x or a.min.x > b.max.x) return false
if(a.max.y < b.min.y or a.min.y > b.max.y) return false

// No separating axis found, therefor there is at least one overlapping axis
return true
}

### Circles

A circle is represented by a radius and point. Here is what your circle structure ought to look like:

struct Circle
{
Vec position
};

Testing for whether or not two circles intersect is very simple: take the radii of the two circles and add them together, then check to see if this sum is greater than the distance between the two circles.

An important optimization to make here is get rid of any need to use the square root operator:

float Distance( Vec2 a, Vec2 b )
{
return sqrt( (a.x - b.x)^2 + (a.y - b.y)^2 )
}

bool CirclevsCircleUnoptimized( Circle a, Circle b )
{
return r < Distance( a.position, b.position )
}

bool CirclevsCircleOptimized( Circle a, Circle b )
{
r *= r
return r < (a.x + b.x)^2 + (a.y + b.y)^2
}

In general multiplication is a much cheaper operation than taking the square root of a value.

## Impulse Resolution

Impulse resolution is a particular type of collision resolution strategy. Collision resolution is the act of taking two objects who are found to be intersecting and modifying them in such a way as to not allow them to remain intersecting.

In general an object within a physics engine has three main degrees of freedom (in two dimensions): movement in the xy plane and rotation. In this article we implicitly restrict rotation and use just AABBs and Circles, so the only degree of freedom we really need to consider is movement along the xy plane.

By resolving detected collisions we place a restriction upon movement such that objects cannot remain intersecting one another. The idea behind impulse resolution is to use an impulse (instantaneous change in velocity) to separate objects found colliding. In order to do this the mass, position, and velocity of each object must be taken into account somehow: we want large objects colliding with smaller ones to move a little bit during collision, and to send the small objects flying away. We also want objects with infinite mass to not move at all.

In order to achieve such effects and follow along with natural intuition of how objects behave we'll use rigid bodies and a fair bit of math. A rigid body is just a shape defined by the user (that is, by you, the developer) that is implicitly defined to be non-deformable. Both AABBs and Circles in this article are non-deformable, and will always be either an AABB or Circle. No squashing or stretching allowed.

Working with rigid bodies allows for a lot of math and derivations to be heavily simplified. This is why rigid bodies are commonly used in game simulations, and why we'll be using them in this article.

### Our Objects Collided - Now What?

Assuming we have two shapes found to be intersecting, how does one actually separate the two? Lets assume our collision detection provided us with two important pieces of information:

• Collision normal
• Penetration depth

In order to apply an impulse to both objects and move them apart, we need to know what direction to push them and by how much. The collision normal is the direction in which the impulse will be applied. The penetration depth (along with some other things) determine how large of an impulse will be used. This means the only value that needs to be solved for is the magnitude of our impulse.

Now let's go on a long trek to discover how we can solve for this impulse magnitude. We'll start with our two objects that have been found to be intersecting:

Equation 1

$V^{AB} = V^B - V^A$ Note that in order to create a vector from position A to position B, you must do: endpoint - startpoint. $$V^{AB}$$ is the relative velocity from A to B. This equation ought to be expressed in terms of the collision normal $$n$$ - that is, we would like to know the relative velocity from A to B along the collision normal's direction:

Equation 2

$V^{AB} \cdot n = (V^B - V^A) \cdot n$

We are now making use of the dot product. The dot product is simple; it is the sum of component-wise products:

Equation 3

$V_1 = \begin{bmatrix}x_1 \\y_1\end{bmatrix}, V_2 = \begin{bmatrix}x_2 \\y_2\end{bmatrix} \\ V_1 \cdot V_2 = x_1 * x_2 + y_2 * y_2$

The next step is to introduce what is called the coefficient of restitution. Restitution is a term that means elasticity, or bounciness. Each object in your physics engine will have a restitution represented as a decimal value. However only one decimal value will be used during the impulse calculation.

To decide what restitution to use (denoted by $$e$$ for epsilon), you should always use the lowest restitution involved in the collision for intuitive results:

// Given two objects A and B
e = min( A.restitution, B.restitution )

Once $$e$$ is acquired we can place it into our equation solving for the impulse magnitude.

Newton's Law of Restitution states the following:

Equation 4

$V' = e * V$

All this is saying is that the velocity after a collision is equal to the velocity before it, multiplied by some constant. This constant represents a "bounce factor". Knowing this, it becomes fairly simple to integrate restitution into our current derivation:

Equation 5

$V^{AB} \cdot n = -e * (V^B - V^A) \cdot n$

Notice how we introduced a negative sign here. In Newton's Law of Restitution, $$V'$$, the resulting vector after the bounce, is actually going in the opposite direction of V. So how do we represent opposite directions in our derivation? Introduce a negative sign.

So far so good. Now we need to be able to express these velocities while under the influence of an impulse. Here's a simple equation for modify a vector by some impulse scalar $$j$$ along a specific direction $$n$$:

Equation 6

$V' = V + j * n$

Hopefully the above equation makes sense, as it is very important to understand. We have a unit vector $$n$$ which represents a direction. We have a scalar $$j$$ which represents how long our $$n$$ vector will be. We then add our scaled $$n$$ vector to $$V$$ to result in $$V'$$. This is just adding one vector onto another, and we can use this small equation to apply an impulse of one vector to another.

There's a little more work to be done here. Formally, an impulse is defined as a change in momentum. Momentum is mass * velocity. Knowing this, we can represent an impulse as it is formally defined like so:

Equation 7

$Impulse = mass * Velocity \\ Velocity = \frac{Impulse}{mass} \therefore V' = V + \frac{j * n}{mass}$

The three dots in a small triangle ($$\therefore$$) can be read as "therefore". It is used to show that the thing beforehand can be used to conclude that whatever comes next is true.

Good progress has been made so far! However we need to be able to express an impulse using $$j$$ in terms of two different objects. During a collision with object A and B, A will be pushed in the opposite direction of B:

Equation 8

$V'^A = V^A + \frac{j * n}{mass^A} \\ V'^B = V^B - \frac{j * n}{mass^B}$

These two equations will push A away from B along the direction unit vector $$n$$ by impulse scalar (magnitude of $$n$$) $$j$$.

All that is now required is to merge Equations 8 and 5. Our resulting equation will look something like this:

Equation 9

$(V^A - V^V + \frac{j * n}{mass^A} + \frac{j * n}{mass^B}) * n = -e * (V^B - V^A) \cdot n \\ \therefore \\ (V^A - V^V + \frac{j * n}{mass^A} + \frac{j * n}{mass^B}) * n + e * (V^B - V^A) \cdot n = 0$

If you recall, the original goal was to isolate our magnitude. This is because we know what direction to resolve the collision in (assumed given by the collision detection), and only have left to solve the magnitude of this direction. The magnitude which is an unknown in our case is $$j$$; we must isolate $$j$$ and solve for it.

Equation 10

$(V^B - V^A) \cdot n + j * (\frac{j * n}{mass^A} + \frac{j * n}{mass^B}) * n + e * (V^B - V^A) \cdot n = 0 \\ \therefore \\ (1 + e)((V^B - V^A) \cdot n) + j * (\frac{j * n}{mass^A} + \frac{j * n}{mass^B}) * n = 0 \\ \therefore \\ j = \frac{-(1 + e)((V^B - V^A) \cdot n)}{\frac{1}{mass^A} + \frac{1}{mass^B}}$

Whew! That was a fair bit of math! It is all over for now though. It's important to notice that in the final version of Equation 10 we have $$j$$ on the left (our magnitude) and everything on the right is all known. This means we can write a few lines of code to solve for our impulse scalar $$j$$. And boy is the code a lot more readable than mathematical notation!

void ResolveCollision( Object A, Object B )
{
// Calculate relative velocity
Vec2 rv = B.velocity - A.velocity

// Calculate relative velocity in terms of the normal direction
float velAlongNormal = DotProduct( rv, normal )

// Do not resolve if velocities are separating
if(velAlongNormal > 0)
return;

// Calculate restitution
float e = min( A.restitution, B.restitution)

// Calculate impulse scalar
float j = -(1 + e) * velAlongNormal
j /= 1 / A.mass + 1 / B.mass

// Apply impulse
Vec2 impulse = j * normal
A.velocity -= 1 / A.mass * impulse
B.velocity += 1 / B.mass * impulse
}

There are a few key things to note in the above code sample. The first thing is the check on Line 10, if(VelAlongNormal > 0). This check is very important; it makes sure that you only resolve a collision if the objects are moving towards each other.

If objects are moving away from one another we want to do nothing. This will prevent objects that shouldn't actually be considered colliding from resolving away from one another. This is important for creating a simulation that follows human intuition on what should happen during object interaction.

The second thing to note is that inverse mass is computed multiple times for no reason. It is best to just store your inverse mass within each object and pre-compute it one time:

A.inv_mass = 1 / A.mass
Many physics engines do not actually store raw mass. Physics engines often times store inverse mass and inverse mass alone. It just so happens that most math involving mass is in the form of 1/mass.

The last thing to note is that we intelligently distribute our impulse scalar $$j$$ over the two objects. We want small objects to bounce off of big objects with a large portion of $$j$$, and the big objects to have their velocities modified by a very small portion of $$j$$.

In order to do this you could do:

float mass_sum = A.mass + B.mass
float ratio = A.mass / mass_sum
A.velocity -= ratio * impulse

ratio = B.mass / mass_sum
B.velocity += ratio * impulse

It is important to realize that the above code is equivalent to the ResolveCollision() sample function from before. Like stated before, inverse masses are quite useful in a physics engine.

### Sinking Objects

If we go ahead and use the code we have so far, objects will run into each other and bounce off. This is great, although what happens if one of the objects has infinite mass? Well we need a good way to represent infinite mass within our simulation.

I suggest using zero as infinite mass - although if we try to compute inverse mass of an object with zero we will have a division by zero. The workaround to this is to do the following when computing inverse mass:

if(A.mass == 0)
A.inv_mass = 0
else
A.inv_mass = 1 / A.mass

A value of zero will result in proper calculations during impulse resolution. This is still okay. The problem of sinking objects arises when something starts sinking into another object due to gravity. Perhaps something with low restitution hits a wall with infinite mass and begins to sink.

This sinking is due to floating point errors. During each floating point calculation a small floating point error is introduced due to hardware. (For more information, Google [Floating point error IEEE754].) Over time this error accumulates in positional error, causing objects to sink into one another.

In order to correct this error it must be accounted for. To correct this positional error I will show you a method called linear projection. Linear projection reduces the penetration of two objects by a small percentage, and this is performed after the impulse is applied. Positional correction is very simple: move each object along the collision normal $$n$$ by a percentage of the penetration depth:

void PositionalCorrection( Object A, Object B )
{
const float percent = 0.2 // usually 20% to 80%
Vec2 correction = penetrationDepth / (A.inv_mass + B.inv_mass)) * percent * n
A.position -= A.inv_mass * correction
B.position += B.inv_mass * correction
}

Note that we scale the penetrationDepth by the total mass of the system. This will give a positional correction proportional to how much mass we are dealing with. Small objects push away faster than heavier objects.

There is a slight problem with this implementation: if we are always resolving our positional error then objects will jitter back and forth while they rest upon one another. In order to prevent this some slack must be given. We only perform positional correction if the penetration is above some arbitrary threshold, referred to as "slop":

void PositionalCorrection( Object A, Object B )
{
const float percent = 0.2 // usually 20% to 80%
const float slop = 0.01 // usually 0.01 to 0.1
Vec2 correction = max( penetration - k_slop, 0.0f ) / (A.inv_mass + B.inv_mass)) * percent * n
A.position -= A.inv_mass * correction
B.position += B.inv_mass * correction
}

This allows objects to penetrate ever so slightly without the position correction kicking in.

## Simple Manifold Generation

The last topic to cover in this article is simple manifold generation. A manifold in mathematical terms is something along the lines of "a collection of points that represents an area in space". However, when I refer to the term manifold I am referring to a small object that contains information about a collision between two objects.

Here is a typical manifold setup:

struct Manifold
{
Object *A;
Object *B;
float penetration;
Vec2 normal;
};

During collision detection, both penetration and the collision normal should be computed. In order to find this info the original collision detection algorithms from the top of this article must be extended.

### Circle vs Circle

Lets start with the simplest collision algorithm: Circle vs Circle. This test is mostly trivial. Can you imagine what the direction to resolve the collision will be in? It is the vector from Circle A to Circle B. This can be obtained by subtracting B's position from A's.

Penetration depth is related to the Circles' radii and distance from one another. The overlap of the Circles can be computed by subtracting the summed radii by the distance from each object.

Here is a full sample algorithm for generating the manifold of a Circle vs Circle collision:

bool CirclevsCircle( Manifold *m )
{
// Setup a couple pointers to each object
Object *A = m->A;
Object *B = m->B;

// Vector from A to B
Vec2 n = B->pos - A->pos

r *= r

if(n.LengthSquared( ) > r)
return false

// Circles have collided, now compute manifold
float d = n.Length( ) // perform actual sqrt

// If distance between circles is not zero
if(d != 0)
{
// Distance is difference between radius and distance
m->penetration = r - d

// Utilize our d since we performed sqrt on it already within Length( )
// Points from A to B, and is a unit vector
c->normal = t / d
return true
}

// Circles are on same position
else
{
// Choose random (but consistent) values
c->normal = Vec( 1, 0 )
return true
}
}

The most notable things here are: we do not perform any square roots until necessary (objects are found to be colliding), and we check to make sure the circles are not on the same exact position. If they are on the same position our distance would be zero, and we must avoid division by zero when we compute t / d.

### AABB vs AABB

The AABB to AABB test is a little more complex than Circle vs Circle. The collision normal will not be the vector from A to B, but will be a face normal. An AABB is a box with four faces. Each face has a normal. This normal represents a unit vector that is perpendicular to the face.

Examine the general equation of a line in 2D:

$ax + by + c = 0 \\ normal = \begin{bmatrix}a \\b\end{bmatrix}$

In the above equation, a and b are the normal vector for a line, and the vector (a, b) is assumed to be normalized (length of vector is zero). Again, our collision normal (direction to resolve the collision) will be in the direction of one of the face normals.

Do you know what c represents in the general equation of a line? c is the distance from the origin. This is very useful for testing to see if a point is on one side of a line or another, as you will see in the next article.

Now all that is needed is to find out which face is colliding on one of the objects with the other object, and we have our normal. However sometimes multiple faces of two AABBs can intersect, such as when two corners intersect each other. This means we must find the axis of least penetration.

Here is a full algorithm for AABB to AABB manifold generation and collision detection:

bool AABBvsAABB( Manifold *m )
{
// Setup a couple pointers to each object
Object *A = m->A
Object *B = m->B

// Vector from A to B
Vec2 n = B->pos - A->pos

AABB abox = A->aabb
AABB bbox = B->aabb

// Calculate half extents along x axis for each object
float a_extent = (abox.max.x - abox.min.x) / 2
float b_extent = (bbox.max.x - bbox.min.x) / 2

// Calculate overlap on x axis
float x_overlap = a_extent + b_extent - abs( n.x )

// SAT test on x axis
if(x_overlap > 0)
{
// Calculate half extents along x axis for each object
float a_extent = (abox.max.y - abox.min.y) / 2
float b_extent = (bbox.max.y - bbox.min.y) / 2

// Calculate overlap on y axis
float y_overlap = a_extent + b_extent - abs( n.y )

// SAT test on y axis
if(y_overlap > 0)
{
// Find out which axis is axis of least penetration
if(x_overlap > y_overlap)
{
// Point towards B knowing that n points from A to B
if(n.x < 0)
m->normal = Vec2( -1, 0 )
else
m->normal = Vec2( 0, 0 )
m->penetration = x_overlap
return true
}
else
{
// Point toward B knowing that n points from A to B
if(n.y < 0)
m->normal = Vec2( 0, -1 )
else
m->normal = Vec2( 0, 1 )
m->penetration = y_overlap
return true
}
}
}
}

### Circle vs AABB

The last test I will cover is the Circle vs AABB test. The idea here is to compute the closest point on the AABB to the Circle; from there the test devolves into something similar to the Circle vs Circle test. Once the closest point is computed and a collision is detected the normal is the direction of the closest point to the circle's center. The penetration depth is the difference between the distance of the closest point to the circle and the radius of the circle.

There is one tricky special case; if the circle's center is within the AABB then the center of the circle needs to be clipped to the closest edge of the AABB, and the normal needs to be flipped.

bool AABBvsCircle( Manifold *m )
{
// Setup a couple pointers to each object
Object *A = m->A
Object *B = m->B

// Vector from A to B
Vec2 n = B->pos - A->pos

// Closest point on A to center of B
Vec2 closest = n

// Calculate half extents along each axis
float x_extent = (A->aabb.max.x - A->aabb.min.x) / 2
float y_extent = (A->aabb.max.y - A->aabb.min.y) / 2

// Clamp point to edges of the AABB
closest.x = Clamp( -x_extent, x_extent, closest.x )
closest.y = Clamp( -y_extent, y_extent, closest.y )

bool inside = false

// Circle is inside the AABB, so we need to clamp the circle's center
// to the closest edge
if(n == closest)
{
inside = true

// Find closest axis
if(abs( n.x ) > abs( n.y ))
{
// Clamp to closest extent
if(closest.x > 0)
closest.x = x_extent
else
closest.x = -x_extent
}

// y axis is shorter
else
{
// Clamp to closest extent
if(closest.y > 0)
closest.y = y_extent
else
closest.y = -y_extent
}
}

Vec2 normal = n - closest
real d = normal.LengthSquared( )

// Early out of the radius is shorter than distance to closest point and
// Circle not inside the AABB
if(d > r * r && !inside)
return false

// Avoided sqrt until we needed
d = sqrt( d )

// Collision normal needs to be flipped to point outside if circle was
// inside the AABB
if(inside)
{
m->normal = -n
m->penetration = r + d
}
else
{
m->normal = n
m->penetration = r + d
}

return true
}

## Conclusion

Hopefully by now you've learned a thing or two about physics simulation. This tutorial is enough to let you set up a simple custom physics engine made entirely from scratch. In the next part, we will be covering all the necessary extensions that all physics engines require, including:

• Contact pair sorting and culling


text: HINT: $\displaystyle a^{m_1}=a^{m_2}$ for some $\displaystyle m_1 \neq m_2 \in \mathbb{N}$, because we are in a finite group.


text:
# Data processing for the sandwiched Rényi divergence: a condition for equality

Research paper by Felix Leditzky, Cambyse Rouzé, Nilanjana Datta

Indexed on: 15 Nov '16Published on: 15 Nov '16Published in: Letters in Mathematical Physics

#### Abstract

The $$\alpha$$-sandwiched Rényi divergence satisfies the data processing inequality, i.e. monotonicity under quantum operations, for $$\alpha \ge 1/2$$. In this article, we derive a necessary and sufficient algebraic condition for equality in the data processing inequality for the $$\alpha$$-sandwiched Rényi divergence for all $$\alpha \ge 1/2$$. For the range $$\alpha \in [1/2,1)$$, our result provides the only condition for equality obtained thus far. To prove our result, we first consider the special case of partial trace and derive a condition for equality based on the original proof of the data processing inequality by Frank and Lieb (J Math Phys 54(12):122201, 2013) using a strict convexity/concavity argument. We then generalize to arbitrary quantum operations via the Stinespring Representation Theorem. As applications of our condition for equality in the data processing inequality, we deduce conditions for equality in various entropic inequalities. We formulate a Rényi version of the Araki–Lieb inequality and analyze the case of equality, generalizing a result by Carlen and Lieb (Lett Math Phys 101(1):1–11, 2012) about equality in the original Araki–Lieb inequality. Furthermore, we prove a general lower bound on a Rényi version of the entanglement of formation and observe that it is attained by states saturating the Rényi version of the Araki–Lieb inequality. Finally, we prove that the known upper bound on the entanglement fidelity in terms of the usual fidelity is saturated only by pure states.


text:
#### Archived

This topic is now archived and is closed to further replies.

# annoying vibrating line!

## Recommended Posts

robert_s    122
Hi all!! Here I have a bit funny problem in my flight sim engine and I don''t know if I can explain properly!! Imagine you see in front of you a horizontal line across the window you looking at. say its about 1000 units on -Z so its quite far in my case but still clearly visible! now when I move the planes nose up slowly looking all the time at the vertical line in front of me I can see on the window that the line obviously doesn''t move it stays at the same position only plane moves. so on the window I can see the line moving down when you reverse physics ie. line moves plane doesn''t. when I move the plane nose up slowly the line moves smoothly down the window but when I do same thing quickly then the line appears to vibrate ie. slightly going one unit up and down. It does that quickly so all you can see is a blured double line. When I slow down again it becomes more visible and I can see just one line. I know it might be funny but its quite annoying!! May be you guys had same thing and can help me!! Do you think this is caused coz of my plane movements?

##### Share on other sites
Lord Karnus    122
It sounds to me like there''s a limiter somewhere in your code to slow down the movement of the plane, like :
  if (AddToPitch > 90) AddToPitch = 90;

if there is this in the code, make sure it is before any rotations and before you draw the scene, or it will rotate, then draw, then modify the pitch, so the next frame will be out of wack.
Hope this helps.

email

the way that things have come to be.
Desensitized to everything.
What became of subtlety?
--Tool

##### Share on other sites
robert_s    122
Yes! exactly! Thats what I use but its done in the function below! ie. every time I press an arrow the glutPostRedisplay is called to redraw all again so I think its before anythingelse happens! am I right do you think?

void ArrowKeys(int key, int x, int y)
{
switch (key)
{

case GLUT_KEY_DOWN: if( MouseY < 800.0) {MouseY += 20.0;}
glutPostRedisplay();
break;
case GLUT_KEY_UP: if( MouseY > -800.0) {MouseY -= 20.0;}
glutPostRedisplay();
break;
case GLUT_KEY_LEFT: if( MouseX > -1000.0) {MouseX -= 50.0;}
glutPostRedisplay();
break;
case GLUT_KEY_RIGHT: if( MouseX < 1000.0) {MouseX += 50.0;}
glutPostRedisplay();
break;
}
}

##### Share on other sites
Lord Karnus    122
I''ve never used GLUT myself, but if I''m correct, you might want to wait until all physics code has run before calling glutPostRedisplay()
instead of having it in each case, I would put it at the very end of each program main loop.
For example
  int main(){ while(bGameRunning) { // Do key input/player physics // Do NPC/AI moves and physics glutPostRedisplay(); }}

and comment out all other references to glutPostRedisplay()
I believe that gluPostRedisplay is similar to swapping the buffers without GLUT
If nothing else, it would improve your FPS because, as it is now, only one screen transformation is taking place per frame.

email

the way that things have come to be.
Desensitized to everything.
What became of subtlety?
--Tool