-
Notifications
You must be signed in to change notification settings - Fork 1
/
README.txt
239 lines (165 loc) · 7.97 KB
/
README.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
Copyright 1999 University of North Carolina at Chapel Hill.
All rights reserved.
Permission to use, copy, modify, and distribute this software and its
documentation for educational, research, and non-profit purposes, without fee,
and without a written agreement is hereby granted, provided that the above
copyright notice and the following three paragraphs appear in all copies.
IN NO EVENT SHALL THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL BE LIABLE TO
ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES,
INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS
DOCUMENTATION, EVEN IF THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL HAS
BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL SPECIFICALLY DISCLAIMS ANY
WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED
HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF NORTH CAROLINA AT
CHAPEL HILL HAS NO OBLIGATIONS TO PROVIDE MAINTENANCE, SUPPORT, UPDATES,
ENHANCEMENTS, OR MODIFICATIONS.
The authors may be contacted via:
US Mail: Eric Larsen, Stefan Gottschalk
Department of Computer Science
Sitterson Hall, CB #3175
University of North Carolina
Chapel Hill, NC 27599-3175
Phone: (919) 962-1749
Email: geom@cs.unc.edu
---------------------------------------------------------------------------
PQP v. 1.3
Eric Larsen, Stefan Gottschalk
UNC - Chapel Hill Computer Science
geom@cs.unc.edu
---------------------------------------------------------------------------
Changes:
1.0 - first release of library
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.2 - altered the triangle distance routine due to a degeneracy problem
when edges of two triangles nearly intersect.
1.3 - now use isnan() to test for NaN, instead of a comparison that was
sometimes optimized away.
---------------------------------------------------------------------------
I. 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:
Eric Larsen, Stefan Gottschalk, Ming Lin, Dinesh Manocha,
"Fast Proximity Queries with Swept Sphere Volumes",
Technical report TR99-018, Department of Computer Science,
UNC Chapel Hill
S. Gottschalk, M. C. Lin and D. Manocha,
"OBB-Tree: A Hierarchical Structure for Rapid Interference Detection",
Technical report TR96-013, Department of Computer Science, University
of N. Carolina, Chapel Hill.
Proc. of ACM Siggraph'96.
II. 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/ " " " "
III. 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.
IV. 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.
V. 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.