# PQP

**Repository Path**: zen_shawn/PQP

## Basic Information

- **Project Name**: PQP
- **Description**: Mirror to https://github.com/GammaUNC/PQP
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2020-08-17
- **Last Updated**: 2022-06-06

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# PQP
###### [http://gamma.cs.unc.edu/SSV/](http://gamma.cs.unc.edu/SSV/)
###### Authored by Eric Larsen and Stefan Gottschalk
###### UNC - Chapel Hill Computer Science
###### geom (at) cs (dot) unc (dot) edu

|Version|Changes|
|-------|:------|
|1.3    | now use isnan() to test for NaN, instead of a comparison that was sometimes optimized away.
|1.2    | Altered the triangle distance routine due to a degeneracy problem when edges of two triangles nearly intersect.
|1.1    | Fixed a bug in calculating query times on Win32 machines. Added a demo 'falling' which can demonstrate all of the proximity query types. 
|1.0    | First release of library 

## Introduction

PQP, which stands for Proximity Query Package, is a library for three
types of proximity queries performed on geometric models composed of
triangles:

* collision detection - detect whether two models overlap, and optionally, which triangles of the models overlap.
* distance computation - compute the distance between two models, i. e., the length of the shortest translation that makes the models overlap
* tolerance verification - detect whether two models are closer or farther than a tolerance value.

By default, the library uses "RSS" bounding volumes for distance and
tolerance queries, and OBBs for collision detection (see `PQP_Compile.h`).
Descriptions of the bounding volumes and algorithms used in this package 
are contained in:

- [Fast Proximity Queries with Swept Sphere Volumes](http://gamma.cs.unc.edu/SSV/ssv.pdf)
     <br>Eric Larsen, Stefan Gottschalk, Ming C. Lin, Dinesh Manocha
     <br>Technical report TR99-018, Department of Computer Science
     <br>UNC Chapel Hill 

- [OBB-Tree: A Hierarchical Structure for Rapid Interference Detection](http://gamma.cs.unc.edu/SSV/obb.pdf)
     <br>Stefan Gottschalk, Ming C. Lin and Dinesh Manocha
     <br>Technical report TR96-013, Department of Computer Science, University of North Carolina, Chapel Hill.
     <br>Proc. of ACM Siggraph'96.

## Layout of Files

```
 PQP_v1.3/
   Makefile           Unix makefile to build PQP library
   PQP.dsw PQP.dsp    MS VC++ 5.0 workspace and project files for PQP

   src/
     PQP source

   lib/             
     libPQP.a         after Unix compilation
     PQP.lib          after Win32 compilation

   include/
     PQP.h            include this file to use PQP classes and functions.
     PQP_Internal.h   
     PQP_Compile.h    *WARNING* you should only modify PQP_Compile.h in
     Tri.h            the src directory, not here, because these files
     BV.h             are copied here from src when you perform a build
                     
   demos/
     Makefile         Unix makefile for both demos
     demos.dsw        MS VC++ 5.0 workspace for demos
 
     falling/         source and project files
     sample/          "      "   "       "
     spinning/        "      "   "       "
```

## Building the PQP Library

 In the top level directory, there is a Unix Makefile for building the PQP
 library.  Type 'make' to create a 'libPQP.a' in the lib directory.
 The compiler is currently set to g++ with -O2 level optimization. 

 In Visual C++ 5.0 or higher, open PQP.dsw to build the library.

 Building on either platform has a side effect of copying the include
 files needed for a client application to the include/ directory.  

## Building the Demos

 In the demos directory is a Unix Makefile.  Typing `make` will perform a
 `make` in the `sample` and `spinning` directories.  For VC++5.0
 users, the demos directory contains a demos.dsw file which contains
 projects for both demos.
 
 - sample

   This demo is adapted from the sample client included with RAPID.  Two 
   tori are created, and proximity queries are performed on them at  
   several configurations

 - spinning

   The spinning demo is a GLUT application, so paths to the GLUT & OpenGL
   libraries and includes must be set in spinning/Makefile, or in the 
   VC++ project settings. When run, a bunny and a torus should appear in
   the GLUT window, with a line drawn between their closest points.
   Pressing a key alternately starts and stops them spinning.

 - falling

   This demo is also a GLUT application, showing a bent torus
   falling through the center of a knobby torus.  Each of the three 
   proximity query types can be demonstrated.

## Creating a PQP Client Application

 `PQP.h` contains the most complete information on constructing client
 applications.  Here is a summary of the steps involved.

 1. Include the PQP API header.

    ```
    #include "PQP.h"
    ```

 2. Create two instances of `PQP_Model`.

    ```
    PQP_Model m1, m2;
    ```

 3. Specify the triangles of each `PQP_Model`. Note that PQP uses the `PQP_REAL` type for all its floating point 
    values. This can be set in "PQP_Compile.h", and is "double" by default

    ```
    // begin m1
    m1.BeginModel();
    
    // create some triangles
    PQP_REAL p1[3], p2[3], p3[3];  
    PQP_REAL q1[3], q2[3], q3[3];
    PQP_REAL r1[3], r2[3], r3[3];
    
    // initialize the points
     .
     . 
     .  
    
    // add triangles that will belong to m1
    m1.AddTri(p1, p2, p3, 0);
    m1.AddTri(q1, q2, q3, 1);
    m1.AddTri(r1, r2, r3, 2);
    
    // end m1, which builds the model
        
    m1.EndModel();
    ```

 4. Specify the orientation and position of each model.

    The position of a model is specified as a 3 vector giving the
    position of its frame in the world, stored in a `PQP_REAL [3]`.

    The rotation for a model is specified as a 3x3 matrix, whose columns
    are the model frame's basis vectors, stored in row major order in
    a `PQP_REAL [3][3]`;

    Note that an OpenGL 4x4 matrix has column major storage.

 5. Perform any of the three proximity queries.

    ```
    // collision

    PQP_CollideResult cres;
    PQP_Collide(&cres,R1,T1,&m1,R2,T2,&m2);

    // distance

    PQP_DistanceResult dres;
    double rel_err = 0.0, abs_err = 0.0;
    PQP_Distance(&dres,R1,T1,&m1,R2,T2,&m2,rel_err,abs_err);

    // tolerance
 
    PQP_ToleranceResult tres;
    double tolerance = 1.0;
    PQP_Tolerance(&tres,R1,T1,&m1,R2,T2,&m2,tolerance);
    ```

    See "PQP.h" for complete information.

 6. Access the result structure passed in the query call.

    ```
    int colliding = cres.Colliding();
    double distance = dres.Distance();
    int closer = tres.CloserThanTolerance();
    ```
    
See "PQP.h" for the complete interface to each result structure.