The Standard Template Library (STL) [Austern98, SGI-STL] contains several examples of a similar interface design: Iterators are the interface between sequences of items in container classes and generic algorithms on sequences. However, they (usually) do not modify the container. Among the container classes some modifying functions, e.g., insert or remove, describe a standardized interface for modifying the container classes and can be used for generic algorithms on container classes. This project is expected to design a generic interface in the same spirit for triangulating polygons.

We start with a set of data structures that can represent a simple polygon, and with a set of algorithms that can triangulate it. We suggest to use the Computational Geometry Algorithms Library (CGAL) <www.cgal.org> [Fabri99] as a source of data structures and algorithms in geometry and also as a platform for realizing this project. Possible data structures could be:

• A std::list of 2D points.
• The class CGAL::Polygon_2.
• An individual facet of a 3D polyhedral surface, e.g., the class CGAL::Polyhedron_3.
• While working with the triangulation data structure underlying the class CGAL::Triangulation_2 one can end up in the situation to triangulate a polygonal hole in the triangulation structure.

All these representations would be for simple polygons without holes. An optional extension would be to extend this project to polygons with holes as they can be represented with:

• A std::list of std::list's of 2D points, where the first list is the outer boundary of the polygon and all succeeding lists are the inner boundaries of holes in the polygon, one list per hole.
• The class CGAL::Planar_map_2 can contain faces with holes.
• The class CGAL::Nef_polyhedron_2 can contain faces with holes.

Examples of algorithms that triangulate polygons are:

• Ear-cutting algorithm: An ear is a triangle formed by two consecutive edges of the polygon with a convex angle that contains no other point of a polygon. There exist always at least two ears in a polygon. An ear can be cut from the polygon, reducing its size and thus triangulating it.
• A sweep-line algorithm, see [Chapter 3, deBerg00].
• The constrained triangulation in CGAL. It creates a triangulation of the convex hull of a set of points respecting a set of constrained edges that have to be present in the triangulation, which would be the polygon boundary edges here. Afterwards the triangles in the polygon interior have to be selected, i.e., distinguished from those outside of the polygon.

Clearly iterators can be used in examining the input polygon. The new part will be the modifying part of the algorithms; where do we create and store the result triangles:

• For a single polygon we might just write triangles to an output iterator, for example, for storage in a container or for rendering.
• For polygons embedded in a data structure, such as a triangulation or a polyhedral surface, one wants the result triangles to replace the original polygon and to have the proper neighborhood pointers.

The goal of the project is to design the interface and to realize some of the data structures and algorithms, possibly based on the already existing CGAL implementations. The task includes:

• Analyse the set of operations of each agorithm and how it could be implemented for each data structure considered.
• Find a common set (or several sets) of operations that support the different combinations.
• Implement the interface for the data structures, possibly with adaptors for the existing data structures in CGAL.
• Implement the algorithm based on this interface, maybe also with adaptors to the already existing algorithms in CGAL.
• Test your generic algorithms on the different representations.
• Document the design, for example, in the style of CGAL or using Doxygen.

Prerequisites

This project requires interest in geometry or graphics and some knowledge of geometric algorithms. Since CGAL will be covered later in the course, it might be necessary to learn about CGAL prior to that.

References

[Austern98]

Mathew H. Austern. Generic Programming and the STL: Using and Extending the C++ Standard Template Library. Addison-Wesley, 1998.

 

[SGI-STL]

Silicon Graphics Computer Systems, Inc. Standard Template Library Programmer's Guide. http://www.sgi.com/tech/stl/.

 

[Fabri99]

Andreas Fabri, Geert-Jan Giezeman, Lutz Kettner, Stefan Schirra, and Sven Schönherr. On the Design of CGAL, the Computational Geometry Algorithms Library. Software -- Practice and Experience, submitted 1999, to appear. (also available as technical report)

 

[deBerg00]

Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer, 2nd edition, 2000.

Matrix Result

Using the quaternion to matrix conversion here we get:

so substituting the quaternion results above into the matrix we get:

Substituting the following expansions:

(v1 x v2).x = v1.y * v2.z - v2.y * v1.z
(v1 x v2).y = v1.z * v2.x - v2.z * v1.x
(v1 x v2).z = v1.x * v2.y - v2.x * v1.y
(v1 x v2).x² = v1.y * v2.z * v1.y * v2.z + v2.y * v1.z * v2.y * v1.z - 2 * v2.y * v1.z * v1.y * v2.z
(v1 x v2).y² = v1.z * v2.x * v1.z * v2.x + v2.z * v1.x * v2.z * v1.x - 2* v2.z * v1.x * v1.z * v2.x
(v1 x v2).z² = v1.x * v2.y * v1.x * v2.y +v2.x * v1.y * v2.x * v1.y - 2 * v2.x * v1.y * v1.x * v2.y
v1•v2 = v1.x * v2.x + v1.y * v2.y + v1.z * v2.z

This is getting far too complicated ! can anyone help me simplify this?

Code

sfrotation angleBetween(sfvec3f v1,sfvec3f v2) {
float angle;
// turn vectors into unit vectors
n1 = v1.norm();
n2 = v2.norm();
angle = Math.acos( sfvec3f.dot(n1,n2) );
// if no noticable rotation is available return zero rotation
// this way we avoid Cross product artifacts
if( Math.abs(angle) < 0.0001 ) return new sfrotation( 0, 0, 1, 0 );
// in this case there are 2 lines on the same axis
if(Math.abs(angle)-Math.pi) < 0.001){
n1 = n1.Rotx( 0.5f );
// there are an infinite number of normals
// in this case. Anyone of these normals will be
// a valid rotation (180 degrees). so I rotate the curr axis by 0.5 radians this way we get one of these normals
}
sfvec3f axis = n1;
axis.cross(n2);
return new sfrotation(axis.x,axis.y,axis.z,angle);
}

/** note v1 and v2 dont have to be nomalised, thanks to minorlogic for telling me about this:
* http://www.euclideanspace.com/maths/algebra/vectors/angleBetween/minorlogic.htm
*/
sfquat angleBetween(sfvec3f v1,sfvec3f v2) {
float d = sfvec3f.dot(v1,v2);
sfvec3f axis = v1;
axis.cross(v2);
float qw = (float)Math.sqrt(v1.len_squared()*v2.len_squared()) + d;
if (qw < 0.0001) { // vectors are 180 degrees apart
return (new sfquat(0,-v1.z,v1.y,v1.x)).norm;
}
sfquat q= new sfquat(qw,axis.x,axis.y,axis.z);
return q.norm();
}

matrix version

sfmatrix angleBetween(sfvec3f v1,sfvec3f v2) {
// turn vectors into unit vectors
n1 = v1.norm();
n2 = v2.norm(); 	sfvec3f vs = new sfvec3f(n1);
vs.cross(n2); // axis multiplied by sin	sfvec3f v = new sfvec3f(vs);
v = v.norm(); // axis of rotation
float ca = dot(n1, n2) ; // cos angle	sfvec3f vt = new sfvec3f(v);	vt.scale((1.0f - ca);	sfmatrix rotM = new sfmatrix();
rotM.m11 = vt.x * v.x + ca;
rotM.m22 = vt.y * v.y + ca;
rotM.m33 = vt.z * v.z + ca;	vt.x *= v.y;
vt.z *= v.x;
vt.y *= v.z;	rotM.m12 = vt.x - vs.z;
rotM.m13 = vt.z + vs.y;
rotM.m21 = vt.x + vs.z;
rotM.m23 = vt.y - vs.x;
rotM.m31 = vt.z - vs.y;
rotM.m32 = vt.y + vs.x;
return rotM;
}

see also code from minorlogic

An introduction to building HP TouchSmart-hosted applications and a step-by-step tutorial for a “Hello World”

Building Your First TouchSmart Application
A developers guide to the TouchSmart Platform

Introduction

The Hewlett-Packard TouchSmart PC is an innovative new PC form-factor which affords users the unique ability to control interactions using only their hands. Through the use of a very stylish “10 foot” style user interface, the user can simply touch the integrated screen and perform most essential functions – viewing photos, listening to music, and surfing the web – all without using a keyboard or mouse.

The TouchSmart interface can be considered an entirely new user-interface platform – and now HP has opened up this platform to the entire developer community. With the release of the TouchSmart Application Developer Guidelines you can now build applications which run on this unique platform – and cater to its expanding user-base.

This article walks you through building your first TouchSmart application, with the goal of creating a basic application template which you can use for all your TouchSmart projects.

Getting Started

In order to follow the steps in this document, you will need to be familiar with Windows Presentation Foundation (WPF) and .NET development with C#. This article assumes a basic knowledge of these technologies. Please visit the Microsoft Developer Network (MSDN) at http://msdn.microsoft.com for more information.

In addition, the following is required:

• TouchSmart PC (model IQ504 or IQ506, current at the time of this writing)
• Latest TouchSmart software (available from http://support.hp.com)
• Microsoft Visual Studio 2008, Express (free) or Professional Edition
• HP TouchSmart Application Development Guidelines (available from here).
• .NET Framework 3.5 (although the same techniques can be used to build an application using Visual Studio 2005 and .NET 3.0)

It is recommended you install Visual Studio 2008 on the TouchSmart PC for ease of development, however it is not required. Since the TouchSmart application we are building is simply a Windows Presentation Foundation application it will run on any Vista or Windows XP PC with .NET 3.5.

Important Background Information

Before getting started you should know some important background information about a typical TouchSmart application:

• To best integrate with the TouchSmart look-and-feel you should develop your application using the Windows Presentation Foundation (WPF)
• The application runs as a separate process with a window that has the frame removed, it is not running within the TouchSmart shell process.
• The TouchSmart shell is responsible for launching your application. Additionally, the TouchSmart shell will control the position and sizing of your window.
• You must create three separate UI layouts for your application. This is not as difficult as it sounds; only one layout is interactive with controls – the other two layouts are for display only.
• Design your application for a “10 foot” viewing experience. Plan to increase font and control sizes if you are converting an existing application.
• Do not use pop-up windows in your application. This is perhaps the most unique requirement in building a TouchSmart application. The Windows “MessageBox” and other pop-up windows are not supported and should not be used. The best model to follow is to build your application like it was going to run in a web browser.
• Your application must support 64-bit Vista, as this is the operating system used on the TouchSmart PC.

<AppManagementSetting>
<UserEditable>true</UserEditable>
<RunAtStartup>true</RunAtStartup>
<RemoveFromTaskbar>false</RemoveFromTaskbar>   <AppPath>C:\TouchSmart\HelloTouchSmart\HelloTouchSmart\bin\Release\HelloTouchSmart.exe
</AppPath>
<AppParameters>chromeless</AppParameters>
<AllowAttach>true</AllowAttach>
<Section>Top</Section>
<Type>InfoView</Type>
<DisplayName>HelloTouchSmart</DisplayName>
<IsVisible>true</IsVisible>
<UserDeleted>false</UserDeleted>
<InDefaultSet>false</InDefaultSet>
<IconName />
</AppManagementSetting>

NextWindow's touch Application Program Interface (API) provides programmers with access to touch data generated by a NextWindow touch screen. It also provides derived touch information. For information about the capabilities of NextWindow products and which ones you can interface to using the API, see NextWindow Latest Technical Information.

The touch events, data and derived information can be used in any way the application wants.

Communications are via HID-compliant USB.

The API is in the form of a DLL that provides useful functions for application developers.

Multi-Touch

Multi-touch simply refers to a touch-sensitive device that can independently detect and optionally resolve the position of two or more touches on screen at the same time. In contrast, a traditional touch screen senses the position of a single touch and hence is not a multi-touch device.

	“Detect” refers to the ability to sense that a touch has occurred somewhere on screen.
	“Resolve” refers to the ability to report the coordinates of the touch position.

NextWindow’s standard optical touch hardware can detect two touches on screen. The firmware can resolve the position of two simultaneous touches (with some limitations).

NextWindow Multi-Touch API Downloads

NWMultiTouchAPI_v1260.zip contains the following files:

Note

NextWindow's DLL is 32-bit. If you are building an application on a 64-bit machine, you need to specify a 32-bit build. To change this setting in Visual C#, change the platform target to x86 under the Build page of Project Settings. See the following Microsoft article for more details.

http://msdn.microsoft.com/en-us/library/kb4wyys2.aspx

Example Code

NWMultiTouchCSharpSample_v1260.zip

NWMultiTouchCPlusPlusSample_v1260.zip

Documentation

NextWindow USB API User Guide v1.7 (91 KB pdf file)

NextWindow Multi-Touch Whitepaper (2722 KB pdf)

For this article, I wanted to demonstrate how to access gestures and flicks using C# code. I'll talk about accessing flicks using the tablet API and accessing gestures using the N-Trig native libraries. Surprisingly I couldn't find much out there that goes into any kind of depth in coding for either of these topics. So it seemed like a good opportunity to present some examples. I've included code for a C# game that uses the gestures for control. I hope you find it fun and useful.

Even though they are called "flicks", a flick is really a single touch gesture and an N-Trig gesture is a double touch gesture.  All the examples run on Windows Vista Ultimate 32bit. Windows Vista will only detect up to two fingers on the touch surface. However, Windows 7 promises to allow more than two finger detection. I'll have to try that next. HP is already shipping hardware that is multi-touch enabled on their TouchSmart PCs.  The Dell Latitude XT and XT2 tablet PCs are also using the N-Trig hardware for multi-touch.

Code to Detect If Running on a Tablet PC

I found some simple code to determine if your app is running on a tablet PC. It is a native call to GetSystemMetrics which is in User32.dll and you pass in SM_TABLETPC. I've included this code in the Flicks class.  You may want your app to auto-detect if it's running on a tablet to determine which features to enable.

Accessing Flicks (Single Touch Gestures) or UniGesture

If you've never heard of flicks before, they are single touch gestures that are triggered based on the speed of the touch across the tablet surface.  You can find more detail here.  It currently gives you eight directions that can be programmed at the OS level for use by applications.

I used the tabflicks.h file that I found in the folder - "C:\Program Files\Microsoft SDKs\Windows\v6.0A\Include" This header file is included with the Windows SDK. It contains all the flick structures and macro definitions needed to access flicks. I created a  class library project called FlickLib that contains the C# structures, DllImports and code to store and process the data. I also wrote a test WinForm application that shows the usage of the library.

I override the WndProc method of the WinForm to gain access to the WM_TABLET_FLICK messages sent to the window. The flick data is encoded in the WParam and the LParam of the windows message. I discovered that even though the params are IntPtr type, they are not actually pointers but are the real integer values to be used. I kept getting an Access Violation exception when I was trying to marshal the IntPtr to a structure. The solution was non-obvious. I couldn't find that documented anywhere. But it works correctly now so this is my contribution to the web for anyone trying to solve the same problem.

It is important to note that on line # 117, I set msg.Result = IntPtr.Zero.  This tells the base.WndProc method that the message has been handled so ignore it.  This is important because the underlying pen flicks can be assigned to actions such as copy and paste.  If the message is not flagged as handled, the app will attempt to perform the action.

Accessing Double Touch Gestures or DuoGestures

The N-Trig hardware on the HP TouchSmart tablet provides the ability to detect two (or more) touches on the surface. This allows the tablet to respond on two finger gestures. You can see the current DuoGestures in use from N-Trig here.

I've created a class library project called GestureLib which wraps the native libraries from N-Trig so that they can be called using C#. Obviously this will only run on tablets that have the N-Trig hardware. Currently there is the HP TouchSmart tx2 and the Dell Latitude XT & XT2 laptops. I'll be testing and updating code for the HP TouchSmart IQ505 panel that uses the NextWindow hardware. If someone has any other tablets, touch panels and/or UMPC devices, I'd be happy to work together to create a version for that as well.

Once you look at the code you will note that you have to connect to the N-Trig hardware at the start of the app.  I put that call in the OnLoad method.  Once you have a handle to the hardware, then you will use that throughout the lifetime of the app.  It is stored in the Gestures class.  With the handle, you will register which gesture messages you want the window to receive.  Once registered, you will start to see NTR_WM_GESTURE message showing up in the WndProc method.  I created a ProcessMessage method in the Gestures class that will determine which gesutre type it is and extract the data for the particular gesture.

One thing to note is if you look at the DllImports for the NtrigISV.dll native library you will see that there is name mangling with the method calls. I had to use Dependency Walker to determine the actual names of the methods. So be warned that when N-Trig releases a new version of their DLL that this code will probably break.

Problems with Marshalling Data from C++ to C#

I had an issue where I was only getting the Zoom messages.  My friend, Ben Gavin, helped me solve the problem.  It had to do with marshalling the data into the struct.  The original C++ struct looks like this:

For my original port, I just did a LayoutKind.Sequential and set everything as a bool like below.

Trouble is that bool in C++ is one byte where as a bool in C# is an Int32 or four bytes. Now if the C++ struct was labeled with a BOOL, then it would have been four bytes. So the new declaration of the struct in C# looks like this:

Once I used the FieldOffsetAttribute to set each bool to one byte each, the Rotate messages started to work correctly. Thanks Ben...

WPF Gestures Example Code

Using the same GestureLib class library, I also created an app that shows how to capture the gestures using a WPF application.  That was an interesting exercise because I had never gotten a Windows handle from a WPF app.  I discovered the WinInteropHelper class that gets the underlying Windows handle. I also had to hook the MessageProc handler to get the messages.  The WndProc method is not available to override in WPF.

Gesture Blocks - C# Game using Gestures and Flicks

Just creating test apps is boring and I wanted to create a game example that uses the flicks and gestures for control. I chose to build a simple game that shows off some of the possibilities for touch control. I call the game Gesture Blocks. It will give you a good starting point on using gestures in games. Watch the video to see the gestures in action.

Conclusion

I hope the code I provided was useful and helpful. I will try to update the examples as issues are resolved. I'm also going to work on some other game examples that continue to show what can be done with gestures. The next project will be to load Windows 7 onto the tablet and write some code for more than DuoGestures.

以下是做CAD二次開發一年多來的一些讀書筆記﹕
节选于《AutoCAD高级开发技术：ARX编程及应用》

跟大家分享
一．图块设计技术:

在AutoCAD数据库中，以各图块实际上市存储在块表记录里的实体集合。每个图块从一格AcDbBlockBegin对象开始，紧接着是一个或多个AcDbEntity对象，最后以AcDbBolckEnd对象结束，按其所属关系得层次结构分为三层：第一层为块表，是属于数据库管理的根对象；第二层为块表记录，是属于块表管理的对象；第三层为组成图块的实体对象，是属于块表记录管理的基本对象。因而，在AutoCAD数据库中，定义图块的第一个过程式向块表中加入一条新的块表记录，然后将组成图块的实体对象写入该块表记录中。

1.AutoCAD数据库中图块的引用
在AutoCAD系统中插入已定义的块并不是将块中所有实体复制到数据库中，而是通过块引用机制向块表记录增加一个AcDbBlockReference类引用对象。所谓的块引用实际上是用户用Insert命令或ARX引用程序向AutoCAD数据库中插入的图块。在ARX应用程序中，利用定义的AcDbBlockReference类实例及相应的成员函数可以设置插入块的有关特性，如插入点、旋转角以及XYZ方向的比例系数等。插入不带属性的简单图块的编程技术相对比较简单，做法如下：
A．创建一个指向AcDbBlockReference类对象实例的指针。
B．调用该类的成员函数setBlockTableRecord()设置引用图块的ID号。
C．调用该类的成员函数setPosition(),setRotation()和setScaleFactors()分别设置块引用的插入点、旋转角和XYZ方向的比例系数等。
D．打开当前图形模型空间的块表，利用getBlockTable()函数获得指向当前图形的块表指针。
E．调用appendAcDbEntity()函数将块引用加入当前数据库模型空间块表记录中。

2. 属性块的引用：
在块定义中的附加属性信息必须通过调用AcDbBlockReference类的成员函数appendAttribute()才能加入到块引用中。
定义属性块时，属性实质上是附加于构成图块的某一实体上的一个或多个非图形信息。因此，在插入属性时必须检索出属性块定义时的所有附加信息，然后将其附加于块引用的相应实体上，这就需要遍历块中的全部实体。
通过属性块的ID号打开其块表记录，从而获得指向块表记录的指针。程序代码为:
AcDbBlockTableRecord *pBlockDef; //定义指向块表记录的指针
acdbOpenObject(pBlockDef,blockid,AcDb::kForRead); //获得指向块表记录的指针
参数blockid为属性的ID号，然后，定义一个用于遍历块表记录的浏览器，获得指向块表记录的浏览器指针，如：
AcDbBlockTableIterator *pIterator; //定义指向块表记录浏览器的指针
pBlockDef->newIterator(pIterator); //获得指向块表记录的浏览器指针
成员函数newIterator()用于创建块表记录的浏览器对象，参数pIterator为指向块表记录的浏览器指针。在此基础上建立一个循环结构，用于遍历图块中的全部实体，得到指向某一实体的指针，其结构如下：
AcDbEntity *pEnt; //定义指向实体的指针
AcDbAttributeDefinition *pAttdef; //定义指向属性定义的指针
For (pIterator->state(); !pterator->done(); pIterator->step())
{
pIterator->getEntity(pEnt,AcDb::kForRead); //得到指向实体的指针
pAttdef = AcDbAttributeDefinition::cast(pEnt); //得到指向属性定义的指针
//处理属性插入的代码
……
pEnt->close(); //关闭尸体对象
}
实体属性的插入代码的执行机理如下：
1）. 创建AcDbAttribute类对象，获得指向该对象的指针。
如： AcDbAttribute *pAtt = new AcDbAttribute;
2）. 设置新建的AcDbAttribute类对象的属性值及特性,如属性位置,字高,旋转角度,属性文本等.
3) . 调用appendAttribute()函数将属性附加于pBlkRef指向的块引用中。
如： pBlkRef->appendAttribute(attid,pAtt);
其中，pBlkRef为指向块引用的指针，pAtt为前面创建的AcDbAttribute类对象的指针。

3. AutoCAD数据库中图块的检索
对于AutoCAD数据库来说，图块的检索主要包括用户定义的有名块和图形中已插入的块引用两个方面。
1）. 先介绍当前图形数据库中块的检索技术：
用ads_tblnext()函数可以得到当前图形的数据库中表示块定义得链表，将改链表存储于结果缓冲区类型的变量中，利用结果缓冲区中的联合体成员就可以获得块名、基点等信息。重复调用ads_tblnext()函数将遍历整个数据库链表中的所有块表记录，从而得到全部已定义的图块信息。
2) . 用户定义数据库中块的检索：
对于在ARX应用中定义的其他数据库，只能用ARX库的函数才能检索出该数据库中所定义的图块，程序的主要设计技术如下：
A. 利用AcDbBlockTable类的成员函数newIterator()创建块表浏览器.
如： pBTable->newiterator(pBIterator);
pBTable为AcDbBlockTable类指针；pBIterator为AcDbBlockTableIterator类块表浏览器指针.
B. 利用循环结构和块表浏览器遍历块表。
C．利用AcDbBlockTableIterator类成员函数getRecord()获得块表记录。
如：pIterator->getRecord(pBTRecord,AcDb::kForRead);
D. 利用块表记录类的成员函数getName()得到块名。
4. 块中实体的检索：
在检索任意数据库中的图块时，主要是利用块表浏览器遍历块表，从而获得图块名。而在获得块名的前提下，利用ARX库提供的块表记录浏览器遍历块表记录中的所有实体，从而实现对块中实体的检索。方法为：
A．用一种合适的方式获得图块名，得到指向该图快的块表记录。
B．生成块表记录浏览器。
C．遍历块中的多有实体，得到检索结果。

现在知道图框的名字是A3，要求遍历图框中属性：pBlkRef为AcDbBlockReference实体。
AcDbObjectIterator *pBlkRefAttItr=pBlkRef->attributeIterator();
for (pBlkRefAttItr->start(); !pBlkRefAttItr->done();pBlkRefAttItr->step())
{
AcDbObjectId attObjId;
attObjId = pBlkRefAttItr->objectId();

AcDbAttribute *pAtt = NULL;
Acad::ErrorStatus es = acdbOpenObject(pAtt, attObjId, AcDb::kForRead);
if (es != Acad::eOk)
{
acutPrintf("\nFailed to open attribute");
delete pBlkRefAttItr;
continue;
}
if (strcmp(pAtt->tag(),"TITLE:") == 0)
{
CString title = pAtt->textString();
if (strcmp(title,"PROGRESS(D)") == 0)
{ //操作
}
else if (strcmp(title,"PROGRESS(P)") == 0)
{
//操作
}
}
pAtt->close();
}

二．容器对象：符号表的操作和使用技术
符号表的操作主要分为向符号表中加入一条符号表记录，符号表记录的检索和符号表记录中对象的处理等，每一种操作都是通过相应的符号表类提供的成员函数来实现的。
1.层表的操作和使用技术：
A． 创建新层：
1). 以写的方式调用getSymbolTable()函数打开当前数据库的层表，获得指向该表的指针。
2) 调用构造函数AcDbLayerTableRecord()创建层表建立对象。
3) 设置层名。
4) 设置层的有关属性。
5) 调用add()函数将层表记录加入到层表中。
6) 关闭层表和层表记录。

2. 层的属性设置和查询函数
层的属性包括：颜色、冻结状态、锁定状态、开关状态、在新视口中层的冻结状态和线型，下面列出的设置和查询函数均是AcDbLayerTableRecord类的成员函数。
A．设置颜色：setColor(const AcCmColor color);
B．设置冻结状态：setIsFrozen(bool frozen);
如果参数frozen为true表层冻结；frozen为false表层冻结。
C．设置锁定状态：setIsLocked(bool locked);
如果参数locked为true表层锁定；locked为false表层解锁。
D．设置开关状态：setIsOff(bool off)；
如果参数off为true表层关闭；off为false表层打开。
E．设置在新视口中层的冻结状态：setVPDFLT(bool frozen)；
如果参数frozen为true表在新视口中层将冻结；frozen为false表在新视口中层解冻。
F．设置线型：setLinetypeObjectId(AcDbObjectId id)；
在调用构造函数AcDbLayerTableRecord()创建层表记录时，上述参数的缺省值为：
Color为7(white),isFrozen为false，isLocked为false，isoff为false，VPDFLT为false，线型的ID号为NULL。

3. 层属性的修改和查询实例的基本方法：
A．以读方式打开层表，获得指向层表的指针。
B．调用层表类的成员函数getAt()，以写的方式获得指定层名的层表记录指针。
C．调用属性设置函数修改属性或调用属性查询函数获得属性；

4. 数据库中层的检索的基本方法：
A．利用AcDbLayerTable类的成员函数newIterator()创建层表浏览器。
B．利用循环结构和块表浏览器遍历块表。
C．利用AcDbLayerTableIterator类的成员函数getRecord()获得块表记录。
D．利用成员函数getName()得到层名。

5. 设置图形数据库的当前层：
调用AcDbDatabase类的成员函数setClayer()设置图形数据库的当前层，其函数原型为：
Acad::ErrorStatus setClayer(AcDbObjectId objId);
函数的参数为层表的ID号。获得层表记录ID号的主要方法有：
1) 将新建的层表记录加入层表时，用下面的形式调用add()函数：
AcDbLayerTable::add(AcDbObjectId & layerID,AcDbLayerTableRecord *pRecord);
在关闭层表和层表记录的代码后，加入“acdbCurDwg()->setClayer(layerID);”设置当前层。
2) 若层已经存在，则可利用获得指定符号表ID号的形式调用getAt()函数：
AcDbLayerTable:: getAt(const char* entryName, AcDbObjectId& recordId, bool getErasedRecord = false) const;
然后调用加入“acdbCurDwg()->setClayer(layerID);”设置当前层。
6. 定义字体样式
AutoCAD数据库的字体样式是字体样式中的一条记录，其缺省的字体样式名为STANDARD，字体文件名为txt.shx。用STYLE定义一个新的字体样式包括建立样式名，选择字体文件和确定字体效果三步操作。用户新定义的字体样式是作为一条字体样式表记录加入字体样式表中。
A．以写方式调用getTextStyleTable()哈数打开当前图形数据库的字体样式表，获得指向该表的指针。
B．调用构造函数AcDbTextStyleRecord()创建字体样式表记录对象。
C．设置字体样式名和字体文件名。
D．设置字体的效果，包括倒置、反向、垂直、宽度比例和倾斜角的设置。
E．调用add()函数将字体样式表记录加入字体样式表中。
F．关闭字体样式表和字体样式表记录。

7. 尺寸标注样式和尺寸变量
尺寸标注样式是AutoCAD数据库中尺寸标注样式表的一条记录，其缺省的尺寸标注样式名为STANDSRD，该样式由系统自动建立。尺寸变量是确定组成尺寸标注线、尺寸界线、尺寸文字以及箭头的样式、大小和它们之间相对位置等的变量。
对标注样式名为STANDARD的尺寸变量进行修改，首先要打开当前图形数据库的尺寸标注样式表，并调用getAt()函数获得指向尺寸标注样式表记录STANDARD的指针，然后调用AcDbDimStyleTableRecord类成员函数设置尺寸变量。
建立新的尺寸标注样式与建立图层和定义字体样式基本相同。，其步骤为：
A．以写的方式调用getDimStyleTable()函数打开当前图形数据库的尺寸标注样式表，获得指向该表的指针.
B．调用构造函数AcDbDimStyleRecord()创建尺寸标注样式表记录对象。
C．设置尺寸标注样式名。
D．调用AcDbDimStyleRecord类的成员函数设置尺寸变量。
E．调用add()函数将尺寸标注样式表记录加入到尺寸标注样式中。
F．关闭尺寸标注样式表和尺寸标注样式表记录。

8. 符号表记录的建立：
9种符号表作为AutoCAD数据库中的根对象和容器，包含的下级对象为相应的符号表记录。符号表本身只能由AutoCAD系统建立而不能由应用程序创建，应用程序只能创建符号表记录。如块表中的块表记录，层表中的层表记录，字体样式表中的字体样式记录等，虽然各种具体的符号表记录名称不同，但建立的基本方法相同。归纳主要以下几步：
A．以写的方式调用get##BASE_NAME##Table()函数打开数据库的## BASE_NAME##表，获得指向该表的指针。
B．调用构造函数AcDb##BASE_NAME##Record()创建相应的符号表记录对象。
C．调用setName()函数设置相应的符号表记录名。
D．調用符号记录表的成员函数设置其属性。
E．调用add()函数将所创建立的符号表记录加入其符号表。
F．关闭符号表和符号表记录。

9. 符号表记录的编辑：
对于符号表的符号表记录，可以通过符号表记录类的成员函数对其属性进行编辑，如更改字体样式表的字型文件、文字的字高和宽度比例等。符号表记录的编辑实现技术可以分三步：
A．以读的方式调用get##BASE_NAME##Table()函数打开数据库的##BASE_NAME##表，获得指向该表的指针。
B．调用符号表类的成员函数getAt()获得符号表记录指针。
C．调用相应的符号表记录成员函数修改其属性。

10.符号表记录的查询：
符号表记录的查询主要利用符号表浏览器和循环结构实现，步骤如下：
A．利用AcDb##BASE_NAME##Table类的成员函数newIterator()创建符号表浏览器。
B．利用循环结构和块表浏览器遍历块表。
C．利用AcDb##BASE_NAME##TableIterator类的成员函数getRecord()获得符号表记录。
D．利用成员函数getName()得到符号表记录名。
例子：
AcDb##BASE_NAME##Table *pTable;
acdbHostApplicationServices()->workingDatabase()
->get##BASE_NAME##Table (pTable,AcDb::kForRead);

AcDb##BASE_NAME##TableIterator *pIter;
pTable ->newIterator(pIter);
pTable ->close();

AcDb##BASE_NAME##TableRecord *pRecord;
for (pIter ->start();!pIter ->done();pIter ->step())
{
pIter ->getRecord(pRecord,AcDb::kForWrite);
char *m_name;
pRecord ->getName(m_name);
//添加相应的操作
free(m_Layername);
pRecord ->close();
}
delete pLayerIter;

三．对象字典的操作
对象字典和符号表均是AutoCAD图形数据库中的容器对象。在9种符号表中，每一种符号表只能用来存储特定的对象，如块表用来存储块表记录，层表用来存储层表记录等，而对象字典却不受此限制，它可以存储任何类型的对象，包括其他对象字典、数据库对象和应用程序创建的对象。因此，所谓的对象字典实际上是一种通用的对象容器。

1. 组字典的操作使用技术:
组是实体等数据库对象的有序集合，是组字典的成员。从层次关系来看，组是管理其所包含对象的容器，而组字典则是管理组对象的容器。一个组实际上可以认为是一个选择集，但又不同于一般的选择集，它是組字典中一個有名的常驻对象。当组中的一个实体被删除时，该实体自动地从组中移出；当恢复被删除的是天时，该实体又自动地加入到该组中。使用组可以简化操作，容易实现对一批对象的颜色、层和线型等属性的统一修改。
组字典中可以包含若干个组，每个组通过其组名来区分。
A．直接从数据库中获得指向组字典的指针：
Acad::ErrorStatus getGroupDictionary（AcDbDictionary*& pDict，AcDb::OpenMode mode);
B．从对象字典中获得组字典的指针：
由于组字典是对象字典中的一个名为“ACAD_GROUP”的成员，因此先获得数据库中指向对象字典的指针，然后调用getAt()函数获得指向组字典的指针。
AcDbDictionary *pNamedObj,*pGroupDict;
acdbCurDwg()->getNamedObjectsDictionary(pNamedObj,AcDb::kForRead);
pNamedObj->getAt("ACAD_GROUP",(AcDbObject *&)pGroupDict,AcDb::kForWrite);

2. 将组加入组字典中：
setAt(const char* srchKey,AcDbObject *newValue,AcDbObjectId& retObjId);
各参数的意义为：srchKey为组名，用字符串表示；newValue为加入到组字典中的新组的指针；retObjId为函数返回的已加入组字典中的组对象的ID号。如果在组字典中已有同名的组存在，则将被新加入的组取代。调用该函数时，必须先创建组对象，将指向组对象的指针和定义的组名作为输入参数，并获得加入组字典中的组对象ID号。
其中组对象为AcDbGroup类。具体的操作查相关的类函数即可！

3.建立多线样式：
多线是指多条互相平行的直线，各条线的线型、颜色和他们之间的间距等属性可互不相同。多条的这些属性由多线样式定义。定义一个多线样式的步骤为：
A．通过getMLStyleDictionary()函数获得指向图形数据库中的多线样式字典的指针。
B．用多线样式的构造函数AcDbMlineStyle()创建多线样式对象。
C．利用AcDbDictionary类的成员函数setAt()将所建立的多线样式加入字典中。
D．调用有关函数设置多线样式的属性，如设置多次按名称、元素特性和多线特性等。

4.用户对象字典的操作和使用技术：
在AutoCAD数据库中，对象字典是字典类数据库对象的总称。按其层次关系可分为两类，一是由AutoCAD数据库直接管理的第一层对象字典；二是由第一层对象字典管理的第二层对象字典。为了便于区别，我们把第一层对象字典成为有名对象字典，用户在应用程序中定义的字典成为用户字典。前面提到的组字典、多线样式字典和用户对象字典均属于第二层对象字典，其中组字典和多线字典是系统自动生成的对象字典。
对象字典的第三层为字典中的对象。如：组诗组字典中的对象，多线样式是多线样式字典中的对象，在用户对象字典中可以包含任何类型的对象，如实体对象、自定义对象和数据库对象等。有名对象字典中的各用户对象字典之间，通过其字名来表示；用户字典中的对象利用其对象名来区分。
4.1 用户对象字典的定义和字典对象的查询：
在有名对象字典中定义一个用户对象字典的实质是创建一个AcDbDictionary类对象，并将其加入有名对象字典中，其步骤为：第一,调用AcDbDatabase类的成员函数getNameObjectDictionary()得到有名对象字典的地址(即指针)；第二，定义新的用户对象字典并加入有名对象字典中。
例子：
AcDbDictionary *pNamedObj; //定义有名对象字典
acdbCurDwg()->getNamedObjectsDictionary(pNamedObj,AcDb::kForWrite);
AcDbDictionary *pDict = new AcDbDictionary; //定义用户对象字典
AcDbObjectId eid;
pNamedObj->setAt("Name",pDict,eid);
而在用户字典中对象查询的第一步是建立字典浏览器遍历对象字典：
AcDbDictionaryIterator *pDictIter = pDict->newIterator();
字典对象查询的第二步是得到指向对象的指针：
pDictIter->getObject(pObj,AcDb::kForRead);
在获得对象指针的前提下，可以利用对象的成员函数进行查询、检索和编辑等操作。
另外，用户字典中的对象名可以用AcDbDictionaryIterator类的成员函数name()获得。而该对象名表示的对象类名可以用“pObj->isA()->name()”形式获得。
需要注意的是：将块表记录中的实体对象加入用户字典，并不是将实体复制到字典中，而是在字典中存储其对象的指针。因此，当块表记录中的实体被删除后，在字典中相应的对象名和指针也不再存在。

4.2 用户对象字典：扩展记录的加入和查询。
扩展记录属于AcDbxrecord类的对象，可用来定义任何类型的数据。扩展记录的数据项采用结果缓冲区链表的形式定义，每一项由DXF组码和相应的组值构成。扩展记录是一个在应用程序中定义的数据库对象，属于有名对象字典的下级对象或某一对象的扩展字典和其他扩展记录的下级对象。
在ARX中创建扩展记录的主要步骤如下：
1.获得数据库中指向有名对象字典的指针。
2.建立一个新的用户脆响字典，并加入有名对象字典中。
3.创建新的扩展记录，并加入用户对象字典中，如：
AcDbXrecord *pXrec = new AcDbXrecord;
pDict->setAt("XREC1", pXrec, xrecObjId);
4.用ads_buildlist()函数构造由扩展记录数据项组成的缓冲区链表，其一般形式为：
ads_buildlist(<组码1>，<组值1>，<组码2>，<组值2>，……，0)；
5. 调用AcDbXrecord的成员函数setFromRbChain()设置扩展记录所指向的链表指针。

三．ARX应用程序中的尺寸标注技术
1. 尺寸对象的组成和常用的尺寸标注类：
尺寸标注也是AutoCAD数据库中块表记录中的一种对象。一个完整的尺寸对象由尺寸标注线，尺寸界线，尺寸箭头和尺寸文字构成。
在AutoCAD数据库中，AcDbDimension类为尺寸标注的基类，其派生类主要有对齐标注(AcDbAlignedDimension),两线定角标注(AcDb2LineAngularDimension),三点定角标注(AcDb3PointAngularDimension),直径标注(AcDbDiametricDimension),半径标注(AcDbRadialDimension),坐标尺寸标注(AcDbOrdinateDimension),定角标注(AcDbRotatedDimension)等。
尺寸标注类是实体类(AcDbEntity)的派生类，其主要成员函数的原型为：
1.设置尺寸文字位置：
Acad::ErrorStatus setTextPosition(const AcGePoint3d& unnamed);
2. 设置尺寸标注样式：
Acad::ErrorStatus setDimensionStyle(AcDbObjectId unnamed);
3. 设置尺寸文字：
Acad::ErrorStatus setDimensionText(const char* unnamed);
4. 设置尺寸文字旋转角度：
Acad::ErrorStatus setTextRotation(double unnamed);
5. 查询尺寸文字：
Char* dimensionText()const;
6. 查询尺寸文字位置：
AcGePoint3d textPosition()const;
7. 查询尺寸文字旋转角度
double textRotation()const;
2.尺寸标注的鼠标拖动技术：
实现尺寸标注线和尺寸文字为字的鼠标拖动的关键是跟踪鼠标的移动，并根据鼠标的位置动态显示尺寸标注。用ads_grread()憾事跟踪鼠标的移动，其函数原型为：
Int ads_grread(int track,int *type,struct resbuf *result);
参数track为控制位，其值为1则将鼠标的坐标存入result中；type表示输入的种类，如按鼠标左键，则type=3；
尺寸标注的鼠标拖动原理为：
首先，设置ads_grread()函数控制位track=1,在循环结构中用ads_grread()函数追踪鼠标的移动，获得当前鼠标位置的x,y坐标。用ads_grread(track,&type,&result)形式调用，则点的x和y坐标值可分别用result.resval.rpoint[X]和result.resval.rpoint[Y]形式获得。其次，以写方式打开尺寸标注对象，用获得的X，Y坐标设置尺寸标注线和尺寸位置，并关闭对象。循环执行，实现尺寸步标注对象的拖动。如果按鼠标左键拾取一个点，则type=3，结束循环。
例子：公差标注设置函数：
void SetDimtpAndDimtm(double tp,double tm)
{
AcDbDimStyleTable *pDimStyleTbl;
acdbCurDwg()->getDimStyleTable(pDimStyleTbl,AcDb::kForRead);
AcDbDimStyleTableRecord *pDimStyleTblRcd;
pDimStyleTbl->getAt("",pDimStyleTblRcd,AcDb::kForWrite);
if (fabs(tp) == fabs(tm))
{
pDimStyleTblRcd->setDimtfac(1.0)
}
else pDimStyleTblRcd->setDimtfac(0.5);
if (tp == 0.0 && tm == 0.0)
{
pDimStyleTblRcd->setDimtol(0);
}
else
{
pDimStyleTblRcd->setDimtp(tp);
pDimStyleTblRcd->setDimtol(1);
pDimStyleTblRcd->setDimtm(tm);
}
pDimStyleTblRcd->close();
pDimStyleTbl->close();
}

3.图案填充函数介绍：
图案填充函数AcDbHatCh也是实体立体(AcDbEntity)的派生类，与尺寸标注类似，图案填充也是 AutoCAD数据库中块表记录中的一种对象。
生成图案填充对象的步骤为：
A．调用图案填充类的构造函数创建AcDbHatch类对象。
B．调用AcDbHatch类的成员函数设置填充图案的法向矢量，关联，标高，缩放比例，填充图案，填充方式和填充边界等属性。
C．调用evaluateHatch()显示填充图案。
D．将AcDbHatch类对象写入当前图形数据库的块表记录中。

4.ARX应用程序中视图管理技术和应用：
视图和视口是AutoCAD环境中图形显示中经常涉及到的基本概念。图形屏幕上用于显示图形的一个矩形区域称为视口，可以把整个图形屏幕作为一个视口，也可以把整个视图屏幕设置成多个视口。当前视口中显示的复杂图形按不同的窗口大小设置，并以视图名为表示在图形数据库中保存。在需要时，显示指定视图以满足对图形编辑和浏览的需要。
视图的管理包括视图的定义，显示，属性设置和查询等功能。在AutoCAD的交互环境中，用户可以使用VIEW命令对视图进行命名，保存，恢复和删除。在ARX应用程序中，主要是通过使图表类及视图表记录类的成员函数实现视图的管理功能。
视图类作为视图表(AcDbViewTable)中的一条视图记录(AcDbViewTableRecord)保存在AutoCAD数据库中。把当前视口中指定窗口每得图形定义为一个新的视图的操作等价于向数据库中添加一个AcDbViewTableRecord类对象。其实现步骤为：
A．调用视图标记录类的构造函数创建AcDbViewTableRecord类对象；
B．调用AcDbViewTableRecord类的成员函数设置视图名，视图中心点，视图高度和宽度等属性；
C．获得当前图形数据库中的视图表指针，将AcDbViewTableRecord类对象添加到数据库中。
视图的查询首先要获得当前图形数据库中指定视图师表记录的指针，然后调用相应的成员函数得到该视图的属性。

四．ARX中的实体造型技术和应用
三维造型包括线框模型、表面模型和实体模型三种形式，其中三维实体具有体的特征。能夠較全面地反映形体的物理特征。在机械CAD中，利用实体造型技术用户不仅可以通过并、交、差布尔运算生成所需的机械零部件模型，而且还能够对形体进行剖切成剖视图以进行体积、重心和惯性矩等物性计算和分析，进而在实体模型的基础上生成NC代码，在ARX应用程序中，并不是直接使用AutoCAD系统本身提供的有关实体造型和编辑命令，而是通过直接生成数据库对象及调用AcDb3dSolid类的成员函数来进行实体造型。
1.基本三维实体生成方法：
在AutoCAD数据库中，三维实体属于AcDb3dSolid类对象，该类是AcDbEntity类的派生类。
对于一个具体的几何实体，即ACIS对象来说，AcDb3dSolid实体是一个容器和接口。
通过AcDb3dSolid类的成员函数可以生成各种基本的三维实体以及实现实体的布尔运算。生成三维实体的基本步骤为：
A．调用AcDb3dSolid类的构造函数创建一个容器对象：
如：AcDb3dSolid *p3dObj = new AcDb3dSolid;
B.调用AcDb3dSolid类的成员函数创建基本三维实体对象。其一般形式为：
指向AcDb3dSolid类对象的指针-〉创建基本三维实体对象成员函数。
B．将AcDb3dSolid类对象写入当前图形数据库的块表记录中，其代码设计方法与二维对象的添加完全相同。

ARX程序的消息响应：
ARX程序实质上是一动态库，它直接与AutoCAD进行对话，即AutoCAD发送各种消息给ARX程序，ARX程序负责对各种消息作出相应的处理。
kInitAppMsg:
当ARX程序被加载时发送该消息，用以建立AutoCAD和应用程序之间的对话。
kUnloadAppMsg:
当ARX程序卸载时(不论是用户卸载应用程序，还是由AutoCAD终止退出)发送该消息，关闭文件以及执行必要的清理工作。
kOleUnloadAppMsg:
发送该消息确定应用程序是否可以卸载，即该应用程序的ActiveX对象或接口是否被其他应用程序所引用。
kLoadDwgMsg:
当打开一幅图形时发送消息，此时AutoCAD的图形编辑环境进行了初始化，并且，应用程序可以调用ARX的全局函数，而acedCommand()函数除外。
kUnLoadDwgMsg:
当用户退出当前的图形编辑时发送该消息。

下面的代码将实例生成由 某一图层上所有的实体组成的选择集：
struct resbuf *plb;
char sbuf[32];
ads_name ss1;
plb = acutNewRb(8) //图层DXF组码是8
strcpy(sbuf,”PARTS”); //图层名为PARTS
plb->resval.rstring = sbuf;
plb->rbnext = NULL;
acedSSGet(“X”,NULL,NULL,plb,ss1);
acutRelRb(plb); //don’t forget
下面的例子是选择“PARTS”图层上的所有圆，这是一个利用acutBuildList()函数构造结果缓冲区表后再传给acedSSGet()函数的实例：
ads_name ss1;
struct resbuf *rb1;
rb1 = acutBuildList(RTDXFO,”CIRCLE”,8,”PARTS”,RTNONE);
acedSSGet(“X”,NULL,NULL,rb1,ss1);
acutRelRb(plb); //don’t forget

以上經為個人筆記﹐愿與大家分享﹐共同進步﹗
如有錯誤﹐敬請指出﹗

posted on 2006-02-08 14:09 梦在天涯 阅读(2287) 评论(2)  编辑 收藏 引用 所属分类: ARX/DBX

Background

Touchlib does a fine job of picking out contacts within the input surface. At the moment, there is no formal way of defining how those blob contacts are translated into intended user actions. Some of this requires application assistance to provide context, but some of it is down to pattern matching the appearance, movement and loss of individual blobs or combined blobs.

What I'm attempting to describe here, and for others to contribute to, is a way of

1. Describing a standard library of gestures suitable for the majority of applications
2. A library of code that supports the defined gestures, and generates events to the application layer

By using an XML dialect to describe gestures, it means that individual applications can specify their range of supported gestures to the Gesture Engine. Custom gestures can be supported.

By loosely coupling gesture recognition to the application, we can allow people to build different types of input device and plug them all into the same applications where appropriate.

In the early stages of development, we are all doing our own thing with minimal overlap. Over time we will realise the benefits of various approaches, and by using some standardised interfaces, we can mix and match to take advantage of the tools that work best for our applications. Hard coded interfaces or internal gesture recognition will tie you down and potentially make your application obsolete as things move on.

I'd really appreciate some feedback on this - this is just my take on how to move this forward a little at this stage.

Gesture Definition Markup Langauge

GDML is a proposed XML dialect that describes how events on the input surface are built up to create distinct gestures.

Tap Gesture

<gdml>
<gesture name="tap">
<comment>
A 'tap' is considered to be equivalent to the single click event in a
normal windows/mouse environment.
</comment>
<sequence>
<acquisition type="blob"/>
<update>
<range max="10" />
<size maxDiameter="10" />
<duration max="250" />
</update>
<loss>
<event name="tap">
<var name="x" />
<var name="y" />
<var name="size" />
</event>
</loss>
</sequence>
</gesture>
</gdml>

The gesture element defines the start of a gesture, and in this case gives it the name 'tap'.

The sequence element defines the start of a sequence of events that will be tracked. This gesture is considered valid whilst the events sequence remains valid.

The acquisition element defines that an acquisition event should be seen (fingerDown in Touchlib). This tag is designed to be extensible to input events other than blob, such as fiduciary markers, real world objects or perhaps facial recognition for input systems that are able to distinguish such features.

The update element defines the allowed parameters for the object once acquired. If the defined parameters become invalid during tracking of the gesture, the gesture is no longer valid.

The range element validates that the current X and Y coordinates of the object are within the specified distance of the original X and Y coordinates. range should ultimately support other validations, such as 'min'.

The size element validates that the object diameter is within the specified range. Again, min and other validations of size could be defined. Size allows you to distinguish between finger and palm sized touch events for example.

The duration element defines that the object should only exist for the specified time period (milliseconds). If the touch remains longer than this period, its not a 'tap', but perhaps a 'move' or 'hold' gesture.

The loss element defines what should occur when the object is lost from the input device.

The event element defines that the gesture library should generate a 'tap' event to the application layer, providing the x, y, and size variables.

Double Tap Gesture

<gesture name="doubleTap">
<comment>
A 'doubleTap' gesture is equivalent to the double click event in a normal
windows/mouse environment.
</comment>
<sequence>
<gestureRef id="A" name="tap" />
<duration max="250" />
<gestureRef id="B" name="tap">
<onEvent name="acquisition">
<range objects="A,B" max="10" />
</onEvent>
<onEvent name="tap">
<range objects="A,B" max="10" />
<event name="doubleTap">
<var name="x" />
<var name="y" />
<var name="size" />
</event>
</onEvent>
</gestureRef>
</sequence>
</gesture>

This example shows how more complex gestures can be built from simple gestures. A double tap gesture is in effect, two single taps with a short space between. The taps should be within a defined range of each other, so that they are not confused with taps in different regions of the display.

Note that the gesture is not considered invalid if a tap is generated in another area of the display. GestureLib will discard it and another tap within the permitted range will complete the sequence.

In the case of double tap, an initial tap gesture is captured. A timer is then evaluated, such that the gesture is no longer valid if the specified duration expires. However, if a second tap is initiated, it is checked to make sure that it is within range of the first. range is provided with references to the objects that need comparing (allowing for other more complex gestures to validate subcomponents of the gesture). This is done at the point of acquisition of the second object.

Once the second tap is complete and the event raised, range is again validated, and an event generated to inform the application of the gesture.

Move Gesture

<gesture name="move">
<comment>
A 'move' is considered to be a sustained finger down incorporating
movement away from the point of origin (with potential return during
the transition).
</comment>
<sequence>
<aquisition type="blob" />
<update>
<range min="5" />
<event name="move">
<var name="x" />
<var name="y" />
<var name="size" />
</event>
</update>
<loss>
<event name="moveComplete">
<var name="x" />
<var name="y" />
<var name="size" />
</event>
</loss>
</sequence>
</gesture>

Zoom Gesture

<gesture name="zoom">
<comment>
A 'zoom' is considered to be two objects that move towards or away from
each other in the same plane.
</comment>
<sequence>
<compound>
<gestureRef id="A" name="move">
<gestureRef id="B" name="move">
</compound>
<onEvent name="move">
<plane objects="A,B" maxVariance="5" />
<event name="zoom">
<var name="plane.distance" />
<var name="plane.centre" />
</event>
</onEvent>
<onEvent name="moveComplete">
<plane objects="A,B" maxVariance="5" />
<event name="zoomComplete">
<var name="plane.distance" />
<var name="plane.centre" />
</event>
</onEvent>
</sequence>
</gesture>

A zoom gesture is a compound of two move gestures.

The compound element defines that the events occur in parallel rather than series.

The plane element calculates the line between the two objects, and checks the maximum variance in the angle from its initial (so you can distinguish between a zoom and a rotate, for example).

'move' events from either object are translated into zoom events to the application.

Rotate Gesture

<gesture name="rotate">
<comment>
A 'rotate' is considered to be two objects moving around a central axis
</comment>
<sequence>
<compound>
<gestureRef id="A" name="move">
<gestureRef id="B" name="move">
</compound>
<onEvent name="move">
<axis objects="A,B" range="5" />
<event name="rotate">
<var name="axis.avgX" />
<var name="axis.avgY" />
<var name="axis.angleMax" />
</event>
</onEvent>
<onEvent name="moveComplete">
<axis objects="A,B" range="5" />
<event name="rotateComplete">
<var name="axis.avgX" />
<var name="axis.avgY" />
<var name="axis.angleMax" />
</event>
</onEvent>
</sequence>
</gesture>

The axis element calculates the midpoint between two objects and compares current position against the initial.

GestureLib - A Gesture Recognition Engine

GestureLib does not currently exist!

The purpose of GestureLib is to provide an interface between Touchlib (or any other blob/object tracking software), and the application layer. GestureLib analyses object events generated by Touchlib, and creates Gesture related events to the application for processing.

GestureLib reads gesture definitions defined in GDML, and the operates a pattern matching principle to those gestures to determine which gestures are in progress.

Why GestureLib?

My feeling is that this functionality should be separated from Touchlib, a) for the sake of clarity, and b) because its quite likely that working solutions for a high performance multi-touch environment will require distributed processing. i.e. one system doing blob tracking, another doing gesture recognition, and a further system for the application. If you can get all of your components within the same machine, then excellent, but modularity gives a great deal of flexibility and scalability.

Proposed Processing

When a object is acquired, GestureLib sends an event to the application layer providing the basic details of the acquired object, such as coordinates and size. The application can then provide context to GestureLib about the gestures that are allowed in this context.

For example, take a photo light table type application. This will have a background canvas (which might support zoom and pan/move gestures), and image objects arranged on the canvas. When the user touches a single photo, the application can inform GestureLib that the applicable gestures for this object are 'tap', 'move' and 'zoom'.

GestureLib now starts tracking further incoming events knowing that for this particular object, only three gestures are possible. Based on the allowable parameters for the defined gestures, GestureLib is then able to determine over time which unique gesture is valid. For example if a finger appears, it could be a tap, move or potentially a zoom if another finger appears. If the finger is quickly released, only a tap gesture is possible (assuming that a move must contain a minimum time or distance parameter). If the finger moves outside the permitted range for a tap, tap can be excluded, and matching continues with only move or zoom. Zoom is invalid until another finger appears, but would have an internal timeout that means the introduction of another finger later in the sequence can be treated as a separate gesture (perhaps another user, or the same user interacting with another part of the application).

Again, the application can be continually advised of touch events so that it can continue to provide context, without needing to do the math to figure out the exact gesture.

19 Responses to “Touchlib compiling instructions (Windows)”

1. rbedi100 Says:
   August 31st, 2008 at 3:06 am

   Hi,
   Thanks for the great instructions on compiling touchlib, but one question-do I need Visual Studio 05, or will Visual C++ Express, Dev C++, or another compiler work as well? Thx,
   rbedi100

2. sasha237 Says:
   September 7th, 2008 at 7:22 pm

   Also it works with Visual Studio 2008. Thanks.

3. mr b Says:
   September 13th, 2008 at 6:10 pm

   hi just wandering is the touchlib software free, and does it means you can use a camera too to control it.

4. Laurence Muller Says:
   September 13th, 2008 at 11:42 pm

   @rbedi100:
   I’m not sure if it will work on Visual Studio Express or other ‘free’ IDE’s.

   @mr b:
   The software is free and released under GPL2. You can control the camera parameters if needed.

5. Richard Z Says:
   October 25th, 2008 at 11:07 am

   Hi, i have done as this tutorial, but when i compile the touchlib ,there are lots of errors in “C:\Program Files\Microsoft SDKs\Windows\v6.1\Include\intsafe.h(1278) : error C2061 ..” .
   and when i compile “configapp”,it’s succes!
   is my intsafe.h file have sth wrong?
   thank you!

6. Laurence Muller Says:
   October 31st, 2008 at 11:42 am

   @Richard Z:
   Strange error, are you using visual studio 2005 (or express?)?

   I guess you’ve set the include directories properly?
   C:\Program Files\Microsoft SDKs\Windows\v6.1\Samples\Multimedia\DirectShow\BaseClasses

   and

   C:\Program Files\Microsoft SDKs\Windows\v6.1\Include

   with this library directory:

   C:\Program Files\Microsoft SDKs\Windows\v6.1\Lib

7. zousong Says:
   December 30th, 2008 at 11:59 am

   Hi, i have done as this tutorial, but when i compile the touchlib .compling can pass but i have a link problem:
   and i use visual studio 2005 express
   1>DSVLCaptureFilter.obj : error LNK2019: unresolved external symbol __imp__CoInitialize@4 referenced in function “public: __thiscall DSVLCaptureFilter::DSVLCaptureFilter(char *)” (??0DSVLCaptureFilter@@QAE@PAD@Z)

8. Laurence Muller Says:
   January 12th, 2009 at 4:27 pm

   @zousong:
   It seems like it can not find the DSVL.lib file, check your path settings in the environmental variables:

   It should be this:
   name: “DSVL_HOME”
   value: “C:\_libraries\dsvl-0.0.8c”

9. Ghanshyam Says:
   March 14th, 2009 at 8:57 am

   I m not getting the directry as
   1.C:\Program Files\Microsoft Platform SDK for Windows Server 2003 R2\Include
   2.C:\Program Files\Microsoft Platform SDK for Windows Server 2003 R2\Samples\Multimedia\DirectShow\BaseClasses

   HOw to add these directries…plz suggest me.thanks

10. ghanshyam Says:
    March 14th, 2009 at 4:31 pm

    dear Harry van der Veen
    i want to install touch lib on window xp.
    i used the Touchlib compiling instructions Multigesture_net.htm.
    but afterall we r getting the same error as

    Error 23 error C2065: ‘m_pSchedule’ : undeclared identifier c:\program files\microsoft sdks\windows\v6.1\samples\multimedia\directshow\baseclasses\refclock.h 139

    Error 79 error C2327: ‘CBaseReferenceClock::LPCTSTR’ : is not a type name, static, or enumerator c:\program files\microsoft sdks\windows\v6.1\samples\multimedia\directshow\baseclasses\sysclock.h 25

    plz suggest me as poss as.
    thanking u

11. Aung Sithu Says:
    March 26th, 2009 at 5:11 am

    @ghanshyam

    You need to have the baseclasses directory (samples/multimedia/directshow) before the sdk include directory.

12. Aung Sithu Says:
    March 26th, 2009 at 5:18 am

    Ghanshyam Says:
    March 14th, 2009 at 8:57 am

    I m not getting the directry as
    1.C:\Program Files\Microsoft Platform SDK for Windows Server 2003 R2\Include
    2.C:\Program Files\Microsoft Platform SDK for Windows Server 2003 R2\Samples\Multimedia\DirectShow\BaseClasses

    
    Mine look like this:
    C:\Program Files\Microsoft SDKs\Windows\v6.0\Samples\Multimedia\DirectShow\BaseClasses
    and
    C:\Program Files\Microsoft SDKs\Windows\v6.0\Include
    

13. Tan Says:
    April 10th, 2009 at 8:17 am

    Thanx for the great instruction…

    I followed your steps but am getting the errors below. Please advice.

    Compiling…
    cl : Command line warning D9035 : option ‘Wp64′ has been deprecated and will be removed in a future release
    DSVLCaptureFilter.cpp
    c:\documents and settings\g\desktop\new folder\multitouch\google\touchlib-src-win32-20071106\touchlib\include\dsvlcapturefilter.h(9) : fatal error C1083: Cannot open include file: ’streams.h’: No such file or directory
    FilterFactory.cpp
    c:\documents and settings\g\desktop\new folder\multitouch\google\touchlib-src-win32-20071106\touchlib\include\videowrapperfilter.h(8) : fatal error C1083: Cannot open include file: ’streams.h’: No such file or directory
    VideoWrapperFilter.cpp
    c:\documents and settings\g\desktop\new folder\multitouch\google\touchlib-src-win32-20071106\touchlib\include\videowrapperfilter.h(8) : fatal error C1083: Cannot open include file: ’streams.h’: No such file or directory
    Generating Code…

14. Yenni Says:
    April 13th, 2009 at 5:41 am

    To Tan :

    Just include iostream instead

    To Laurence Muller :
    Thank you for the instructions

    To Anyone please :

    Does anyone see an error in the code below? i keep getting an error at ‘_AUX_RGBImageRec *Image;’ . The code below is from textures.h. And the error am getting is : error C2143: syntax error : missing ‘;’ before ‘*’. Am sure its sumtin stupid, i just dont see it tho.

    #include

    class COGLTexture
    {
    public:
    COGLTexture();
    ~COGLTexture();
    #ifdef WIN32
    _AUX_RGBImageRec *Image;
    #endif
    unsigned int GetID();
    void LoadFromFile(char *filename);
    void SetActive();
    int GetWidth();
    int GetHeight();
    private:
    int Width, Height;
    unsigned int ID;
    bool bInitialized;
    };

15. LucasM Says:
    April 13th, 2009 at 11:53 am

    It seems that the most recent windows SDK (v6.1) no longer supports glaux.h which is required by the demo projects in touchlib. Looking a bit around on internet it seems that it should no longer be used. To solve the problem I copied glaux.h and glaux.lib from the previous SDK (for Windows Server 2003 R2).

16. Yenni Says:
    April 13th, 2009 at 6:08 pm

    correction , the first line is: #include

17. Yenni Says:
    April 13th, 2009 at 6:09 pm

    GL/gl.h

18. LBDL Says:
    April 17th, 2009 at 8:02 pm

    Hi I am getting a lot of compile errors with refclock.h
    I am using VS2008 btw but that should make no odds…
    any clues
    Error 44 error C2061: syntax error : identifier ‘CAMSchedule’ c:\program files\microsoft sdks\windows\v6.1\samples\multimedia\directshow\baseclasses\refclock.h 80 touchlib
    for example
    I am trying to build touchlib

19. xlmeng Says:
    April 21st, 2009 at 5:22 am

    I had the same problem as LBDL’s. Found the solution here:
    http://social.msdn.microsoft.com/forums/en-US/windowsdirectshowdevelopment/thread/5da8f0b8-d2a9-4caf-81e1-7f5788fa1c00/
    The solution work for xp and vista

1. （介绍后加）

http://link.brightcove.com/services/player/bcpid1875256036?bctid=20915830001

2. 超大型多点触摸墙，完美展示多点触摸的魅力

http://www.mt2a.com/viewthread.php?tid=70&extra=page%3D1

3. mt2a论坛

http://www.mt2a.com/

4. 一个OpenCV 机器视觉爱好者的blog

http://blog.csdn.net/hunnish

5. TouchLib 官方网站

http://nuigroup.com/touchlib/

6. DameTouch的视频空间（优酷）

http://u.youku.com/DamoTouch 

7. 《世界构建者》（World Builder）

<embed src="http://player.youku.com/player.php/sid/XNzY0NjIyNDQ=/v.swf" quality="high" width="480" height="400" align="center" allowScriptAccess="sameDomain" type="application/x-shockwave-flash"></embed> 

8. TouchLess 微软的无需接触的触摸技术

http://vimeo.com/1893407?pg=embed&sec=1893407

http://www.codeplex.com/touchless

9. 一种实现原理

What is Touchlib?

Touchlib is our library for creating multi-touch interaction surfaces. It handles tracking blobs of infrared light for you and sends your programs multitouch events, such as 'finger down', 'finger moved', and 'finger released'. It includes a configuration app and a few demos to get you started. It interaces with most major types of webcams and video capture devices. It currently works only under windows but efforts are being made to port it to other platforms.

Who Should Use Touchlib?

Touchlib only comes with simple demo applications. If you want to use touchlib you must be prepared to make your own apps. There are a few ways to do this. You can build applications in C++ and take advantage of touchlib's simple programming interface. Touchlib does not provide you with any graphical or front end abilities - it simply passes you touch events. The graphics are up to you. If you like, take a look at the example apps which use OpenGL GLUT.

If you don't want to have to compile touchlib, binaries are available.

As of the current version, touchlib now can broadcast events in the TUIO protocol (which uses OSC). This makes touchlib compatible with several other applications that support this protocol, such as vvvv, Processing, PureData, etc.. This also makes it possible to use touchlib for blob detection / tracking and something like vvvv or Processing to write appliactions. Of course the other option is to do all your blob detection and processing in vvvv or processing. It's up to you. Supporting the TUIO protocol also enables a distributed architecture where one machine can be devoted to detection and tracking and another machine can handle the application.

If you don't like touchlib and want to program your own system, the latest version of OpenCV (1.0) now has support for blob detection and tracking. This might be a good starting point.

My Mindmap

My mindmap for the touchscreen is available here. This contains info on what parts you'll need for the construction of the screen, where to find them and some very basic instructions for how to build a screen. It also includes some more links. I hope it's useful for some of the people reading this who are interested in doing their own screens. You'll need Freemind (which is coincidentally, free), in order to view it. I'm a big fan of freemind for planning out projects and getting ideas down. It's hierarchical nature allows you to organize and hide parts you are not interested in. It can also link to images, other mindmaps and web pages.

FAQ

Frequently asked questions about the construction of the screen can be found here.

Where to get the source to Touchlib, our multitouch table library:

All our source code is available on our Google Code site at http://code.google.com/p/touchlib/ . You can acces the repsitory using Subversion. If you are using windows, get TortoiseSVN. Use Tortoise to access the repository and download all the files (much easier than going thru the web interface). If you are interested in porting touchlib to linux or the mac, please email me. The system was written in such a way that it should be easy to port and does not depend heavily on any windows specific api's.

Binaries are available here.

Touchlib is written in C++ (the BlobTracking / Analysis is all written by yours truly) and has a Visual Studio 2005 Solution ready to compile. No docs are available right now and it's windows only (though it should be possible to make everything compile under other OS's with a little work). It currently depends on OpenCV, DirectShow (you'll need the Microsoft Platform SDK), VideoWrapper and the DSVideoLib. The source code includes our main library which you can link into your application to start capturing touch events. It has support for most major camera/webcam types. It also includes a basic config app which will need to be run in order to calibrate your camera, and has a couple example apps. Alternately, I've heard other people have used things like vvvv, EyesWeb, processing and Max/MSP in order to do blob tracking / processing and make applications. You can check out some of the demo apps if you want to see how it works. Pong or the config app should be fairly easy to follow. Setting up a bare minimum multitouch app should only take a dozen lines of code or less.

DL Links for dependencies:

• OpenCV - I used Beta 5. Hopefully it is compatible with newer versions (RC 1 is available now).
• DSVideoLib
• VideoWrapper
• Platform SDK
• Also GLUT was used for most of the applications.
• The DirectX SDK is also required
• OSCPack for the OSC application

You'll need to configure a few environment variables to get everything compiled. They are:

• DSVL_HOME - dsvideolib root directory
• VIDEOWRAPPER_HOME - root directory of the video wrapper library
• OPENCV_HOME - root directory of OpenCV
• OSCPACK_HOME - root directory of oscpack

The config app

In order to calibrate the touchlib library for your camera and projector, you'll need to run the config app. Here's how it works. You'll need to set up your computer so that the main monitor is the video projector so that the app comes up on that screen. Run the config app. Press 'b' at any time to recapture the background. Tweak the sliders until you get the desired results. The last step (rectify) should just have light coming from your finger tips (no background noise, etc). When you are satisfied press 'enter'. This will launch the app in full screen mode and you'll see a grid of points (green pluses). Now you can press 'c' to start calibrating. The current point should turn red. Press on your FTIR screen where the point is. Hopefully a press is detected (you can check by looking in the debug window). Press 'space' to calibrate the next point. You'll continue through until all points are calibrated. Note that the screen may not indicate where you are pressing. When you are all done, you can press 'ESC' to quit. All your changes (slider tweaks and calibration points) are saved to the config.xml file. Now when you run any touchlib app it will be calibrated. Note that any changes to where the projector is pointing or your webcam will require a re-calibration.

Testing

Alternate config files are available if you want to test the library using an .AVI for input (instead of the webcam). Replace the config.xml with 5point_avi.xml or 2point_avi.xml. You can edit those files to use a different AVI if you like (you can record a new one using your camera - but you may need to tweak some of the other settings in the config too).

Links

NEW: We now have an official community site for building FTIR tables. Access the site here . The site includes forums, a wiki, news and more.

Other tables and info.

• My Blog - read updates about my progress with the screen
• A HowTo for building FTIR screens
• Pasta and Vinegar: Interactive tables
• Reactivision software
• TUIO protocol
• Some nice info on the Tangent table.
• Links on del.icio.us tagged with multitouch
• DIY Multitouch - A bunch of links and info on various multitouch techniques.
• Khronos Projector - Uses infrared + a stretchy lycra surface and detects the depressions on the surface.
• Smartskin - uses capacitance testing to detect conductive objects, such as skin. Sounds like the best choice for a small form factor. Could fit over or be integrated with an LCD monitor.
• Malleable touch surface
• Here's one of the demos featured on Han's multitouch screen, in more detail. Rigid shape manipulation.
• Warcraft 3 multitouch. Nice. I'd like to be able to get this running on my screen (even if it's only single touch)
• this interesting item: the Entertaible
• Jeff Han's page. The one that started it all

Other

IRC: #ftir on irc.freenode.net

Working in 3D usually involves the use of solid objects. At times you may need to combine multiple parts into one, or remove sections from a solid. AutoCAD has some commands that make this easy for you. These are the boolean operations as well as some other helpful commands for solids editing.:

COMMAND	INPUT	ICON	DESCRIPTION
UNION (Boolean)	UNI		Joins two or more solids into creating one based on the total geometry of all.
SUBTRACT (Boolean)	SU		Subtracts one or more solids from another creating a solid based on the remaining geometry.
INTERSECT (Boolean)	IN		Creates a single solid from one more solids based on the intersected geometry.
EXTRUDE FACE	SOLID EDIT		Allows you to increase the size of a solid by extruding out one of its faces.
SLICE	SLICE		Slices a solid along a cutting plane.
3D ALIGN	3DALIGN		Aligns 2 3D Objects in 3D space.

The boolean commands work only on solids or regions. They are easy to work with IF you follow the command line prompts. Here is an example of each.

Start these exercises by drawing a box 5W X 7L X 3H and a cylinder 3 units in diameter so that the center of the circle is on the midpoint of the block.

UNION

Below left, there is a box and a cylinder. These are two separate objects. If you want to combine them into one object, you have to use the union command.

The UNION command combines one or more solid objects into one object.

Here are the command line prompts and the resulting object:

Command: UNION <ENTER>
Select objects: <SELECT THE BLOCK> 1 found
Select objects: <SELECT THE CYLINDER> 1 found
Select objects: <ENTER>

NOTE: The object that you select first will determine the properties of the unioned object when it is created.

SUBTRACT

The subtract command is used to cut away, or remove the volume of one object from another. It is important to check the command line when using this command. Remember that AutoCAD always asks for the object that you are subtracting FROM first, then it asks for the objects to subtract. Here is an example:

The SUBTRACT command removes the volume of one or more solid objects from an object.

Command: SUBTRACT
Select solids and regions to subtract from...
Select objects: <SELECT THE BLOCK> 1 found <ENTER>
Select objects: Select solids and regions to subtract...
Select objects: <SELECT THE CYLINDER> 1 found <ENTER>
Select objects: <ENTER>

INTERSECT

This command creates a new solid from the intersecting volume of two or more solids or regions. AutoCAD will find where the two objects have an volume of interference and retain that area and discard the rest. Here is an example of this command shown below:

The INTERSECT command combines the volume of one or more solid objects at the areas of interference to create one solid object.

Command: INTERSECT
Select objects: <SELECT THE BLOCK> 1 found
Select objects: <SELECT THE CYLINDER> 1 found
Select objects: <ENTER>

Try these commands with various 3D solid objects to get familiar with them. Draw the block in Lesson 3-2. Draw the outline of the block, extrude it - then draw the circle and extrude it. Then subtract the circle from the block.

These commands will allow you do a lot of 3D work, using only the extrude and these boolean commands. Of course, there are some other ways to edit 3D solids.

SLICE

This command does exactly what the name implies. You can slice a 3D solid just like you were using a knife.

Start with the basic block and cylinder shape you used in the examples above.

The INTERSECT command combines the volume of one or more solid objects at the areas of interference to create one solid object.

Command: SLICE
Select objects: 1 found
Select objects: Specify first point on slicing plane by
[Object/Zaxis/View/XY/YZ/ZX/3points] <3points>: PICK POINT 1
Specify second point on plane: PICK POINT 2
Specify third point on plane: PICK POINT 3
Specify a point on desired side of the plane or [keep Both sides]: <Pick on the side towards the cylinder>

This is a very useful command - think of it as a trim in 3D. Make sure you have your Osnaps on for this command and that you pick the correct points. In a complex 3D drawing, this can be tough to see.

EXTRUDE FACE

Just as there is a "trim"-like command in 3D - there is also a "stretch". This is a new command in recent versions.

I usually start this command by clicking on the menu item Modify > Solids Editing > Extrude Faces. There is also an icon for it on the Solids Editing menu.

The command is quite easy to use, but you need to be careful on which face you select.

Try to extend one edge of the block by 1 inch. Start the command and pick the face on the side (on the bottom line). You'll notice that the bottom face highlights as well. Next type R and pick the bottom face to remove it. Then follow the command line to finish the command.

Command: _solidedit
Solids editing automatic checking: SOLIDCHECK=1
Enter a solids editing option [Face/Edge/Body/Undo/eXit] <eXit>: _face
Enter a face editing option
[Extrude/Move/Rotate/Offset/Taper/Delete/Copy/coLor/Undo/eXit] <eXit>: _extrude
Select faces or [Undo/Remove]: (PICK BOTTOM LINE OF SIDE FACE) 2 faces found.
Select faces or [Undo/Remove/ALL]: R
Remove faces or [Undo/Add/ALL]: (PICK AN EDGE ON THE BOTTOM FACE)2 faces found, 1 removed.
Remove faces or [Undo/Add/ALL]: (ENTER)
Specify height of extrusion or [Path]: 1 (ENTER)
Specify angle of taper for extrusion <0>: (ENTER)
Solid validation started.
Solid validation completed.
Enter a face editing option
[Extrude/Move/Rotate/Offset/Taper/Delete/Copy/coLor/Undo/eXit] <eXit>: (ENTER)

You should end up with this:

Another way of editing faces in AutoCAD 2007 is to use grips to extrude the faces, just like you would on a 2D object. Here is an image below that shows some of the grips available.This option is only available on the basic shapes shown in lesson 3-10.

3D ALIGN

Sometimes, you may find it faster or easier to draw something separately and then move and align it into place. The command to use this in 3D is (funnily enough) 3DALIGN.

This is a simple example, but will show you the method.

Draw a box that is 5 x 5 x 6 tall. Next draw a cylinder that is 3 in diameter and 1 tall. It should look like this:

The goal will be to align the cylinder on the front face of the box where the dotted line is.

Turn on your quadrant Osnaps. Start the 3DALIGN command. You will first be asked to select the objects - select the cylinder and press enter.

Now you will be asked to select the 3 points as indicated below: the centre and 2 quadrants. Now the cylinder will be "stuck" to your cursor as AutoCAD asks where it needs to go.

Line the cylinder up with the box by using object tracking to locate the centre of the face on the box first. Then pick on the midpoints to line up the cylinder to the box. After you pick the 3rd point, the cylinder should move into place and end the command.

Here's a view of the points that were picked incase you had trouble.

The finished 'alignment job' should look like this after using the hide command.

Review:

After learning how to draw some basic 3D solids, you can see that using equally basic editing commands you can have a lot of options. Before advancing, review these commands by drawing simple 3D shapes and editing them.

With the commands explained on these pages, you will be able draw most of the shapes you will need in 3D. There are other options, but get very familiar with these 3D editing options before moving on. The drawings done in the sample drawing section were done almost exclusively with the commands taught in Lessons 3-7 to 3-11. You approach will make the project easy or difficult. Think of the various ways to draw an object before starting. You could save days with some forethought.

Extra Practice: Draw this object as a 3D solid using primitive solids and boolean operations.

Extra Practice: Draw this object as a 3D solid using primitive solids and boolean operations.

DWG ("drawing") is a format used for storing two and three dimensional design data and metadata. It is the native format for several CAD packages including AutoCAD, Intellicad^{[citation needed]} (and its variants), Caddie and DWG is supported non-natively^[2] by many other CAD applications.

[edit] History of the DWG format

DWG (denoted by the .dwg filename extension) was the native file format for the Interact CAD package, developed by Mike Riddle in the late 1970s^[3], and subsequently licensed by Autodesk in 1982 as the basis for AutoCAD^[4][5][6]. From 1982 to 2007, Autodesk created versions of AutoCAD which wrote no less than 18 major variants of the DWG file format, none of which are publicly documented^[7].

The DWG format is probably the most widely used format for CAD drawings. Autodesk estimates that in 1998 there were in excess of two billion DWG files in existence.^[8]

There are several claims to control of the DWG format.^[9] It is Autodesk who designs, defines, and iterates the DWG format as the native format for their CAD applications. Autodesk sells a read/write library, called RealDWG,^[10] under selective licensing terms for use in non-competitive applications. Several companies^{[citation needed]} have attempted to reverse engineer Autodesk's DWG format, and offer software libraries to read and write Autodesk DWG files. The most successful is Open Design Alliance,^[11] a non-profit consortium created in 1998 by a number of software developers (including competitors to Autodesk), released a read/write/view library called the OpenDWG Toolkit, which was based on the MarComp AUTODIRECT libraries.^[12] (ODA has since rewritten and updated that code.)^{[citation needed]} There are no open-source DWG libraries currently available, and neither RealDWG^[10] nor DWGdirect are licensed on terms that are compatible with the gnu gpl, or similar free software license.

In 1998, Autodesk added file verification to AutoCAD R14.01, through a function called DWGCHECK. This function was supported by an encrypted checksum and product code (called a "watermark" by Autodesk), written into DWG files created by the program.^[13][14] In 2006, in response to Autodesk users experiencing bugs and incompatibilities in files written by reverse-engineered DWG read/write libraries, Autodesk modified AutoCAD 2007, to include "TrustedDWG technology", a function which would embed a text string within DWG files written by the program: "Autodesk DWG. This file is a Trusted DWG last saved by an Autodesk application or Autodesk licensed application."^[15] This helped Autodesk software users ensure that the files they were opening were created by an Autodesk, or RealDWG application, reducing risk of incompatibilities.^[16] AutoCAD would pop up a message, warning of potential stability problems, if a user opened a 2007 version DWG file which did not include this text string.

In 2008 The Free Software Foundation asserted the need for an open replacement for the DWG format by placing 'Replacement for OpenDWG libraries'^[17] in 9th place on their High Priority Free Software Projects list.

In 2008 Autodesk and Bentley agreed on exchange of software libraries, including Autodesk RealDWG, to improve the ability to read and write the companies' respective DWG and DGN formats in mixed environments with greater fidelity. In addition, the two companies will facilitate work process interoperability between their AEC applications through supporting the reciprocal use of available Application Programming Interfaces (APIs). ^[18]

[edit] Legal issues

On 22 November 2006, Autodesk sued the Open Design Alliance alleging that its DWGdirect libraries infringed Autodesk's trademark for the word "Autodesk", by writing the TrustedDWG code (including the word "AutoCAD") into DWG files it created. In April 2007, the suit was dropped, with Autodesk modifying the warning message in AutoCAD 2008 (to make it more benign), and the Open Design Alliance removing support for the TrustedDWG code from its DWGdirect libraries.^[19]

In 2006, Autodesk applied for a US trademark on "DWG", as applied to software (as distinct to its application as a file format name.) ^[20]. In a non-final action in May, 2007, the examining attorney refused to register the mark, as it is "merely descriptive" of the use of DWG as a file format name (for which Autodesk does not claim any trademark rights.) In September, 2007, Autodesk responded, claiming that DWG has gained a "secondary meaning," separate from its use as a file format name.^[21]. As of June 22, 2008, Autodesk's #78852798 application received an Office Action notifying the suspension of the procedure, stating the facts are that:

As early as 1996, Autodesk has disclaimed exclusive use of the DWG mark in US trademark filings.^[22]

[edit] Free viewers

There are no open source viewers for DWG files since the licensing of the libraries needed by lx-viewer^[23] now restricts their use to members of the Open Design Alliance.

[edit] Free for unlimited time

• Linux Drawing Viewer / Lx-Viewer only for members of the Open Design Alliance
• Autodesk makes Design Review 2008 (41 MB) (cannot view DWG files natively, requires DWG TrueView) and DWG TrueView 2008 (120 MB). For Windows XP/Vista, also 64-bit.
• Caddie (Free version plots and edits but does not save)
• eDrawings Viewer by SolidWorks, 11.8 Mb. For Windows NT/2000/XP & Mac OS X 10.4+
• Bentley View by Bentley, 58.2 Mb. For Windows 98/ME/NT/2000/XP.
• VariCAD Viewer is a CAD/CAM file viewer able to render DWG files. It is the only such application which runs on the Linux operating system.

Note: DWG Trueview requires that a survey be filled out before download. Design Review has an optional survey.

[edit] References

[edit] See also

• DXF, Autodesk's Drawing Exchange Format
• DWF, Autodesk's Design Web Format
• OpenDWG
• IntelliCAD
• AutoCAD
• Caddie, Low cost DWG based AEC CAD software with digital terrain modelling and photorealistic rendering
• CAD
• Comparison of CAD software includes software which supports the DWG format.
• Comparison of CAD, CAM and CAE file viewers includes viewers for the DWG format.

[edit] External links

• The EveryDWG File Converter is a Windows application from the Open Design Alliance that converts files back and forth between DWG and DXF formats. It also runs with Wine on Linux
• Fighting over DWG: BricsCad and Autodesk Announcements Prove the Value of OpenDWG is an article published in 2005 on the aecnews.com website
• AutoDWG has utilities for converting between the DWG, DWF, DXF, PDF and Adobe Flash formats.
• Any DWG Converter provides converters for converting DWG to DXF, PDF, DWF and Images formats.

We all live in the real world where things behave according to the laws of physics that we learned about in high school or college. Because of this, we're all expert critics about what looks right or more often wrong in many 3D games. We complain when a character's feet slide across the ground or when we can pick out the repeating pattern in the animation of a flag blowing in the wind. Adding realistic physical simulation to a game to improve these effects can be a giant effort and the rewards for the time invested haven't proven to be worthwhile, yet.

Often, though, it's possible to incrementally add elements to a game that can provide increased realism without extremely high risks. Improving the animation behavior of simple cloth objects like flags in the wind and billowing sails is one area where realism increases without the 18 month development risk of introducing a full-fledged physics engine. Not that I don't want to see more games with all-out physics happening, but I think there are some simple things that can be done with cloth objects in the meantime to improve realism and save modelers time.

At the Game Developers Conference in March 2000, I presented my implementation of two techniques for simulating cloth. I was pointed to another, more recent, technique by someone who attended the class. In this paper I'll recap what I presented about at the conference and include information about the newer technique. Hopefully you'll be able to take the ideas I present here and add some level of support for cloth simulation into your title.

2. Background

Various researchers have come up with different techniques for simulating cloth and other deformable surfaces. The technique that is used by all three methods presented here, and by far the most common, is the idea of a mass-spring system. Simply put, a continuous cloth surface is discretized into a finite number of particles much like a sphere is divided into a group of vertices and triangles for drawing with 3D hardware. The particles are then connected in an orderly fashion with springs. Each particle is connected with springs to its four neighbors along both the horizontal and vertical axes. These springs are called "stretch'" springs because they prevent the cloth from stretching too much. Additional springs are added from each particle to its four neighbors along the diagonal directions. These "shear" springs resist any shearing movement of the cloth. Finally, each spring is connected to the four neighbors along both the horizontal and vertical axes but skipping over the closest particles. These springs are called "bend" springs and prevent the cloth from folding in on itself too easily.

.
Figure 1 - Stretch (blue), Shear (green), and Bend (red) springs

Figure 1 shows a representation of a mass-spring system using the previously mentioned stretch, shear, and bend springs. When rendering this surface, the masses and springs themselves are not typically drawn but are used to generate triangle vertices. The nature of the cloth simulation problem involves solving for the positions of the particles at each frame of a simulation. The positions are affected by the springs keeping the particles together as well as by external forces acting on the particles like gravity, wind, or forces due to collisions with other objects or the cloth with itself.

In the next section we'll look at the problem that we're trying to solve to realistically animate a cloth patch. Much of this will be very familiar to anyone who has already experimented with cloth simulation. Feel free to skip to Section 4 if you just want details on the various implementations I tried.

Like any other physical simulation problem, we ultimately want to find new positions and velocities for objects (cloth particles in our case) using Newton's classic law: or more directly . This says that we can find the acceleration () on a particle by taking the total force () acting on the particle and dividing by the mass (m) of the particle. Using Newton's laws of motion, we can solve the differential equations and to find the velocity () and position () of the particle. For simple forces, it may be possible to analytically solve these equations, but realistically, we'll need to do numerical integration of the acceleration to find new velocities and integrate those to find the new positions. In Sections 3.1 through 3.3 we'll take a high level look at explicit integration, implicit integration, and adding post-integration deformation constraints for solving the equations of motion for cloth particles. Many excellent in-depth articles have been written about various aspects of physics simulation including cloth simulation. I'd highly recommend the articles by Jeff Lander^{i, ii}, and Chris Heckerⁱⁱⁱ if you haven't already read them.


3.1. Explicit Integration

One of the simplest ways to numerically integrate the differential equations of motion is to use the tried-and-true method known as Euler's method. For a given initial position, , and velocity, , at time and a time step, , we can calculate a new position, , and velocity, , using a Taylor series expansion of the above differential equations and then dropping some terms (which may introduce error, ):

(1.1)

(1.2)

Unfortunately, Euler's method takes no notice of quickly changing derivatives and so does not work very well for the stiff differential equations that result from the strong springs connecting cloth particles. Provot^iv introduced one method to overcome this problem and Desbrun^v later expanded on this. We'll examine these in more depth in Section 3.3. Until then, let's look at implicit integration.

3.2. Implicit Integration

Given the problem with Euler's method for stiff differential equations and knowing that the problem still exists for other similar "explicit" integration methods, some researchers have worked with what are known as "implicit" integration methods. Baraff and Witkin^vi presented a thorough examination of using implicit integration methods for the cloth problem. Implicit integration sets up a system of equations and then solves for a solution such that the derivatives are consistent both at the beginning and the end of the time step. In essence, rather than looking at the acceleration at the beginning of the time step, it finds an acceleration at the end of the time step that would point back to the initial position and velocity.

The formulation I'm using here is from the Baraff and Witkin paper except I've used to represent the position of the particles rather than . The system of equations is

(1.3)

Here M^-1 is the inverse of a matrix with the mass of the individual particles along the diagonal. If all the particles are the same mass, we can just divide by the scalar mass, m. Like was done in the explicit case, we use a Taylor series expansion of the differential equations to form the approximating discrete system:

(1.4)

The top row of this system is trivial to find once we've found the bottom row, so by plugging the top row into the bottom row, we get the linear system:



3.3. Deformation Constraints

When using either explicit integration or implicit integration to determine new positions and velocities for the cloth particles, it is possible to further improve upon the solution using deformation constraints after the integration process. Provot proposed this method in his paper and Desbrun further combined this with a partial implicit integration technique to achieve good performance with large time steps.

The technique is very simple and easy to implement. Once an integration of positions and velocities has been done, a correction is applied iteratively. The correction is formed by assuming that the particles moved in the correct direction but that they may have moved too far. Particles are then pulled together along the correct direction until they are within the limits of the deformation constraints. The process can be applied multiple times until convergence is reached within some tolerance or there is no time left for the process to be able to maintain a given frame rate. Using deformation constraints can take a normally unstable system and stabilize it quite well. I've found that using a fixed number of iterations typically works well.

Now that we've taken a brief look at integration techniques and how to improve upon the results, let's have a look at the implementations I did. The source code for my implementations can be downloaded and used in your application or just examined for ideas.

Click here to download source code (366kb zip)

I tried implementing a simple cloth patch using three techniques: explicit integration with deformation constraints, implicit integration, and semi-implicit integration with deformation constraints. The sample application depicted in Figure 2 shows a simple cloth patch that can be suspended by any or all of its four corners.


Figure 2 - Cloth Sample Application

Gravity pulls downward on the particles and stretch, shear, and bend springs keep the particles together as a cloth patch. A wireframe version of the cloth is shown in Figure 3. Two triangles are produced for every four particles forming a grid square.


Figure 3 - Wireframe view of cloth patch

I'll discuss the implementation specifics here with a simple analysis of the results in Section 5.


4.1. Basics

For the three implementations, I shared a lot of code. Everything is written in C++ with a rough attempt at modularizing the cloth specific code into a set of physics/cloth related classes. I used a 3D application wizard to create the framework and then added the cloth specific stuff. Information about the 3D AppWizard, for those interested, can be found in the article Creating A Custom Appwizard for 3D Development.

When wading through the source code, you'll find that there are quite a few files. Most of the files that pertain to the cloth simulation are in the files that begin with "Physics_". In addition to these I also created a "ClothObject" class with corresponding filenames which is instantiated and manipulated from the "ClothSample" class.

I experimented with performance with both single-precision and double-precision floating point numbers. To easily change this, I created a typedef in Physics.h for a "Physics_t" type that is used anywhere you would normally use "float" or "double". I found (expectedly) that performance slowed when using double-precision numbers and I didn't notice any improved stability. Your mileage may vary especially if you add support for collision detection and response.

The mass-spring system is implemented as a particle system. This basically means that I don't do any handling of torque or moments of inertia. Within the Physics_ParticleSystem class, I allocate necessary information for the various integration schemes and I allocate large vectors for holding the positions, velocities, forces, etc. of the individual particles. I maintain a linked list of forces that act on the particles. With this implementation there's no way of dynamically changing the number of particles in the system (although forces can be added and removed). For the implicit integration scheme, I allocate some sparse, symmetric matrices to hold the derivatives of the forces and temporary results. For the semi-implicit scheme, I allocate some dense, symmetric matrices to hold the Hessian matrix and inverse matrix, W, for filtering the linear component of the forces.

Regardless of which integration scheme is used we'll use the same overall update algorithm. Pseudo-code for updating the cloth is shown in Figure 4. This routine, Update, is called once per frame and in my implementation uses a fixed time step. Ideally, you'll want to use a variable time step. Remember that doing so can have an impact on performance, especially in the semi-implicit implementation of Desbrun's algorithm because a matrix inversion would be done at each frame where the step size changed. Clearing the accumulators is a no-brainer so I'll just dive into the other three steps of the algorithm in further detail.

4.2.1. Calculating forces and derivatives

My implementation only has two types of forces, a spring force and a gravity force. Both are derived from a Physics_Force base class. During the update routine of the particle system, each force is enumerated and told to apply itself to the fo rce and force derivative accumulators. Force derivatives are only needed when using the implicit integration scheme (actually, they're needed for the semi-implicit integration scheme, but are handled differently).

The gravity force is simple and just adds a constant (the direction and magnitude of gravity: 0,-9.8,0 in my case) to the "external" force accumulator. I maintain separate "internal" and "external" accumulators to support the split integration scheme proposed by Desbrun. The downside to this is that I would really need a separate spring force for handling user supplied force to the cloth because the spring force as implemented assumes that it is acting internally to the cloth only.

The spring force is a simple, linear spring with damping. I derived the force from a condition function as was done in the Baraff/Witkin paper. Unlike the Baraff/Witkin paper's use of separate condition functions for stretching, shearing and bending on a per triangle basis, I use just one condition function for a linear spring connecting two particles. The condition function I used was where p₀ and p₁ are the two particles affected by the spring and dist is the rest distance of the spring. Forces were calculated as derivatives of the energy function formed by the condition function: .
The Desbrun paper uses the time step and spring constant to apply damping but I apply damping as derived by the Baraff/Witkin paper. The damping constant I use is a small multiple of the spring constant.

4.2.2. Integrating forces and updating positions and velocities

By far, the trickiest code to understand is that for integrating the forces to determine new velocities and positions for the cloth particles. We'll start with the simplest case, the explicit integration scheme with deformation constraints.

4.2.2.1. Explicit integration with deformation constraints

Using explicit Euler integration is a straightforward application of equations. The acceleration is found by dividing the force for each particle by the particles mass (actually, we store 1/mass and then do a multiplication). Then, the acceleration is multiplied by the time step to update the velocities. The new velocities are multiplied by the time step to update the positions. The new positions are actually stored in a temporary location so that the deformation constraints can be applied. To apply the deformation constraints, each spring force is asked to "fixup" its associated particles. Basically, if the length of the spring has exceeded a maximum value (determined as a multiple of the rest length of the spring), then the particles are pulled closer together. Finally, we take the fixed-up temporary positions, subtract the starting positions and divide by the time step to get the actual velocities needed to achieve the end state. Then we copy the temporary positions to the actual positions vector and we're ready to render.

4.2.2.2. Implicit integration

At the other end of the spectrum in terms of difficulty is doing full implicit integration using equation (1.6). For this, we form a large, linear system of equations and then use an iterative solution method called the pre-conditioned conjugate gradient method. The Baraff/Witkin paper goes into details on this and explains the use of a filtering process for constraining particles. In my implementation, I inlined the filtering function everywhere it was used. I won't go into the ugly details of the conjugate gradient method, but I will explain briefly some of the tricks I used to improve performance. For one, the large sparse matrices that get formed are all symmetric, so I cut storage requirements almost in half by only storing the upper triangle of the matrices. In doing so, I had to think carefully about the matrix-vector multiply routines. Secondly, in cases where we would actually be using a matrix but one that only had non-zero elements along the diagonal, I just stored the matrix as a vector. I added some specialized routines to the Physics_LargeVector class for "inverting" the vector which just replaced each element with one over the element. Finally, I didn't do any dynamic allocation of the temporary sparse matrices because the overhead would have been too severe. So I ended up keeping some temporary matrices as private members of the Physics_ParticleSystem class.

4.2.2.3. Semi-implicit integration with deformation constraints

The last integration method I tried was a semi-implicit method as described by Desbrun. Desbrun divided the internal forces acting on the cloth into linear components and non-linear components. The linear components could then be easily integrated using implicit integration without having to solve a linear system. Instead, a large constant matrix is inverted once and then just a matrix multiply is required to do the integration. The non-linear components are approximated as torque changes on a global scale when using his technique. In addition, deformation constraints are used to prevent overly large stretching. As mentioned previously, I created a Physics_SymmetricMatrix class for storing the Hessian matrix of the linear portion of the internal cloth forces. The Hessian matrix is used in place of from equation (1.6) and because of the linear nature imposed by Desbrun's splitting of the forces, is zero. Due to the splitting of the problem into a linear and non-linear portion, we don't need to solve a linear system as we did in the Baraff/Witkin implementation. Rather, we can just "filter" the internal forces by multiplying by the inverse matrix where I is the identity matrix, dt is the time step, m is the mass of a particle, and H is the Hessian matrix. We then need to compensate for errors in torque introduced by the splitting. I'd refer the reader to the Desbrun article for more information about the technique. As in the explicit integration scheme, once we've integrated the forces and obtained new velocities and positions (again stored in a temporary vector) we can apply the deformation constraints. See above for details.

While the above explanations of the update loops give the core information about how the cloth patch animates, there is some secondary information that is useful to know when looking through the code. I'll go through several different areas and unless otherwise noted, the text refers to all three update methodologies.

Each particle in the mesh can belong to at most six triangles. I generate a normal for each triangle and then add these and normalize to get the normal at each particle. This process doesn't seem to consume much time, but if every processor cycle is critical, you can choose to average less than six normals.

For the semi-implicit implemenation, I need to form the Hessian matrix that corresponds to the way the particles are connected by the springs. I do this once, upfront, because the spring constants don't change and so the Hessian matrix doesn't change. For each spring, it's Prepare Matrices method is called. This method sets the appropriate elements in the Hessian matrix that the spring affects. Prepare Matrices also is called to "touch" elements of the sparse matrices that will be used by the implicit implementation. This enables the memory allocation to happen only once.

I incorporated a very simplistic collision detection for the cloth with the ground plane. If you use the number keys (0,1,2,3) to toggle constraints on the corners, you can get the cloth to move downward. When it hits the floor, I stop all movement in the downward direction and fix the particles to the plane of the floor. There's no friction, so it's not very realistic. For the implicit implementation, I imposed constraints and particle adjustments as describe by Baraff and Witkin, however things tend to jump unstably as the cloth hits the floor. It's possible a smaller time step is needed but I didn't investigate further.

Both the explicit and semi-implicit routines use particles with infinite mass to constrain them. Because of this, the Fixup routine for applying the deformation constraints looks at the inverse mass of each particle and only moves the particle if its mass is non-infinite (which means the inverse mass is non-zero).

While running the demo the following keys affect the behavior of the cloth:

• P - Pauses the animation of the cloth
• W - Toggles wireframe so you can see the triangles
• X - Exits the demo
• F - Toggles to fullscreen mode
• H - Brings up a help menu showing these keys
• R - Resets the cloth to its initial position - horizontal to the floor and a bit above it
• 0, 1, 2, 3 - Toggles constraints for the four corners of the cloth

Finally, the configuration of the cloth simulation (number of particles, strength of springs, time step, etc.) is contained in Cloth.ini. I added comments for each entry in the file so look there if you want to play around with things. By default the integration method is explicit.

Since I've covered three different techniques for updating the cloth, I'm sure you're wondering what the best m ethod is. Well, for the case I tried the explicit implementation is clearly the fastest as the results in Figure 5 show. This table was generated from running the sample code on an Intel® Pentium® III processor-based system running at 600 Mhz with Microsoft Windows* 98 and DirectX* 7.0. The graphics card was a Matrox* G-400 with the resolution set to 1024x768 @ 60Hz and the color depth set to 16-bit. I used a fixed time step of 0.02 seconds which would be appropriate for a frame rate of 50 frames per second.


Figure 5 - Performance results for various cloth sizes

Some interesting things to note about the performance that isn't shown in the figure are:

• Initialization time for the implicit method can be fairly large as the sparse matrices are allocated.
• Initialization time for the semi-implicit method can be considerably larger than that for the implicit method because a large matrix (1089x1089 in the 33x33 patch case) needs to be inverted. The same amount of computation would be required any time the time step changed.
• The implicit method is the only one that uses the actual spring strengths to hold the cloth together. Because of this, it may be necessary to increase the spring constants when using the implicit method.
• Desbrun claimed being able to vary the strength of the spring constant by a factor of 10⁶ without causing instability. I was only able to achieve a factor of 10⁵ which makes me think that other simulation specifics (like particle masses) may have been different.
• For the explicit and semi-implicit cases I needed to make the mass of the particles fairly large to achieve stability with a time step of 0.02 seconds. This could cause the cloth to have unusual properties if incorporated with other physics simulation involving inertia and collisions. In your game you may want to maintain separate masses for the updating of the cloth and the interaction of the cloth with the world.
• Because I haven't implemented real collision detection it's uncertain how collision with other objects will affect the stability and hence the performance of the various implementations.
• I maintained a linked list of spring forces that needed to be applied and then have their deformation constraints applied. Performance could be improved by storing these in an array that could be more quickly walked through.

Even though explicit integration seems to work best for my test case, the benefits of implicit integration should not be overlooked. Implicit integration can stably handle extremely large forces without blowing up. Explicit integration schemes cannot make such a claim. And while deformation constraints can be used with explicit integration to provide realistic looking cloth, implicit integration would have to be used if a more physically accurate simulation of cloth was required.

I breezed through some of the math and background with the hope that the accompanying source code would be even more valuable than a theoretical explanation which can be found in other more academic papers. Feel fr ee to take parts of the code and incorporate it in your title. There's a lot more that can be done than what I've presented here. Start simple and add a wind force and remember that it should affect triangles created by the particles not the particles themselves. Or try adding a user controllable mouse force to drag the cloth around. Depending on whether you want to use cloth simulation for eye candy in your game (like flags blowing in the wind or the sail on a ship) or as a key element, you'll probably need collision detection at some point. Keep in mind that cloth-cloth collision detection can be difficult to do efficiently.

Well, I've taken a brief look at real-time simulation of realistic looking cloth and hopefully have presented something of use to you in your game development. I look forward to seeing new games that incorporate various aspects of physics simulation with cloth simulation as one of them.

Click here to download source code (366kb zip)

i Jeff Lander. Lone Game Developer Battles Physics Simulator. On www.gamasutra.com*, February 2000.

ii Jeff Lander. Graphic Content: Devil in the Blue-Faceted Dress: Real-time Cloth Animation. In Game Developer Magazine. May 1999.

iii Chris Hecker. Physics Articles at http://chrishecker.com/Rigid_Body_Dynamics* originally published in Game Developer Magazine. October 1996 through June 1997.

iv Xavier Provot. Deformation Constraints in a Mass-Spring Model to Describe Rigid Cloth Behavior. In Graphics Interface, pages 147-155, 1995.

v Mathieu Desbrun, Peter Schroder and Alan Barr. Interactive Animation of Structured Deformable Objects. In Graphics Interface '99. June 1999.

vi D. Baraff and A. Witkin. Large Steps in Cloth Simulation. Computer Graphics (Proc. SIGGRAPH), pages 43-54, 1998.

The following is an excerpt from Advanced Game Development with Programmable Graphics Hardware (ISBN 1-56881-240-X) published by A K Peters, Ltd.

--

Integrating shadows to the relief map objects is an important feature in fully integrating the effect into a game scenario. The corrected depth option (see Chapter 5), which ensures that the depth values stored in Z-buffer include the displaced depth from the relief map, makes it possible to implement correct shadow effects for such objects. We consider the use of stencil shadows and shadow maps in this context. We can implement three types of shadows: shadows from relief object to the world, from the world to relief object and from relief object to itself (self-shadows).

Let us first consider what can be achieved using stencil volume shadows. When generating the shadow volumes, we can only use the polygons from the original mesh to generate the volume. This means that the shadows from relief objects to the world will not show the displaced geometry of the relief texture, but will reflect the shape of the original triangle mesh without the displaced pixels (Figure 1).

	Figure 1. A relief mapped object cannot produce correct object to world shadows using shadow volumes.

However, as we have the corrected depth stored in Z-buffer when rendering the lighting pass we can have shadows volumes from the world projected onto the relief objects correctly, and they will follow the displaced geometry properly. Self-shadows (relief object to itself) are not possible with stencil shadows.

Thus, using relief maps in conjunction with shadow volumes, we have the following:

• Relief object to world: correct silhouette or displacement visible in shadows is not possible.
• World to relief object: shadows can project on displaced pixels correctly.
• Relief object to relief object: not possible.

Relief mapped objects integrate much better into shadow map algorithms. Using a shadow map, we can resolve all three cases; as for any other object, we render the relief mapped object into the shadow map. As the shadow map only needs depth values, the shader, used when rendering the object to the shadow map, does not need to calculate lighting. Also if no self-shadows are desired, we could simplify the ray intersect function to invoke only the linear search (as in this case we only need to know if a pixel has an intersection and we do not need the exact intersection point). The shader used when rendering relief objects to a shadow map is given in Listing 4.4, and an example is shown in Figure 2.

	Figure 2. Using relief mapped objects in conjunction with shadow maps. Shadows from relief object to world.

To project shadows from the world to the relief map objects, we need to pass the shadow map texture and light matrix (light frustum view/projection/bias multiplied by inverse camera view matrix). Then, just before calculating the final colour in the shader we project the displaced pixel position into the light space and compare the depth map at that position to the pixel depth in light space.

#ifdef RM_SHADOWS
  // transform pixel position to shadow map space
  sm= mul (viewinverse_lightviewprojbias,position);   
  sm/=sm.w;
  if (sm.z> f1tex2D (shadowmap,sm.xy))
    att=0; // set attenuation to 0
#endif

	Figure 3. Shadows from world to relief objects. Left image shows normal mapping, and right image, relief mapping (notice how the shadow boundary follows the displaced relief correctly).

An example of this approach is shown in Figure 3. This is compared with a conventional render using a normal map in conjunction with a shadow map. Thus, using relief maps in conjunction with shadow maps, we can implement the following:

• Relief object to world: good silhouette and displacement visible in
  shadows.
• World to relief object: Shadows can project on displaced pixels correctly.
• Relief object to relief object: possible if full linear/binary search and
  depth correct used when rendering to shadow map.

Listing 4.4
Using relief mapped objects in conjunction with shadow maps.

float ray_intersect_rm_shadow(
    in sampler2D reliefmap,
    in float2 tx,
    in float3 v,
    in float f,
    in float tmax)
{
  const int linear_search_steps=10;

  float t=0.0;
  float best_t=tmax+0.001;
  float size=best_t/linear_search_steps;

  // search for first point inside object
  for ( int i=0;i<linear_search_steps-1;i++ )
  {
    t+=size;
    float3 p=ray_position(t,tx,v,f);
    float4 tex= tex2D (reliefmap,p.xy);
    if (best_t>tmax)
    if (p.z>tex.w)
         best_t=t;
  }

  return best_t;
}

f2s main_frag_relief_shadow(
    v2f IN,
    uniform sampler2D rmtex: TEXUNIT0 , // rm texture map
    uniform float4 planes,     // near and far plane info
    uniform float tile,                  // tile factor
    uniform float depth)       // depth factor
{
    f2s OUT;

    // view vector in eye space
    float3 view= normalize (IN.vpos);

    // view vector in tangent space
    float3 v= normalize ( float3 ( dot (view,IN.tangent.xyz),
        dot (view,IN.binormal.xyz), dot (-view,IN.normal)));

    // mapping scale from object to texture space
    float2 mapping= float2 (IN.tangent.w,IN.binormal.w)/tile;

    // quadric coefficients transformed to texture space
    float2 quadric=IN.curvature.xy*mapping.xy*mapping.xy/depth;

    // view vector in texture space
    v.xy/=mapping;
    v.z/=depth;

    // quadric applied to view vector coodinates
    float f=quadric.x*v.x*v.x+quadric.y*v.y*v.y;

    // compute max distance for search min(t(z=0),t(z=1))
    float d=v.z*v.z-4*f;
    float tmax=100;
    if (d>0)     // t when z=1
        tmax=(-v.z+ sqrt (d))/(-2*f);
    d=v.z/f;     // t when z=0
    if (d>0)
        tmax= min (tmax,d);

#ifndef RM_DEPTHCORRECT
  // no depth correct, use simple ray_intersect
  float t=ray_intersect_rm_shadow(rmtex,IN. texcoord*tile,v,f,tmax);
  if (t>tmax)
      discard ; // no intesection, discard fragment
#else
    // with depth correct, use full ray_intersect
    float t=ray_intersect_rm(rmtex,IN.texcoord*tile,v,f,tmax);
    if (t>tmax)
        discard ; // no intesection, discard fragment

    // compute displaced pixel position in view space
    float3 p=IN.vpos.xyz+view*t;

    // a=-far/(far-near)
    // b=-far*near/(far-near)
    // Z=(a*z+b)/-z
    OUT.depth=((planes.x*p.z+planes.y)/-p.z);
#endif

    return OUT;
}

The Mechanics of Robust Stencil Shadows

The idea of using the stencil buffer to generate shadows has been around for over a decade, but only recently has 3D graphics hardware advanced to the point where using the stencil algorithm on a large scale has become practical. Not long ago, there existed some unsolved problems pertaining to stencil shadows that prevented the algorithm from working correctly under various conditions. Advances have now been made, however, so that stencil shadows can be robustly implemented to handle arbitrarily positioned point lights and infinite directional lights having any desired spatial relationship with the camera. This article presents the intricacies of the entire stencil shadow algorithm and covers every mathematical detail of its efficient implementation.

Algorithm Overview

The basic concept of the stencil shadow algorithm is to use the stencil buffer as a masking mechanism to prevent pixels in shadow from being drawn during the rendering pass for a particular light source. This is accomplished by rendering an invisible shadow volume for each shadow-casting object in a scene using stencil operations that leave nonzero values in the stencil buffer wherever light is blocked. Once the stencil buffer has been filled with the appropriate mask, a lighting pass only illuminates pixels where the value in the stencil buffer is zero.

As shown in Figure 1, an object’s shadow volume encloses the region of space for which light is blocked by the object. This volume is constructed by finding the edges in the object’s triangle mesh representing the boundary between lit triangles and unlit triangles and extruding those edges away from the light source. Such a collection of edges is called the object’s silhouette with respect to the light source. The shadow volume is rendered into the stencil buffer using operations that modify the stencil value at each pixel depending on whether the depth test passes or fails. Of course, this requires that the depth buffer has already been initialized to the correct values by a previous rendering pass. Thus, the scene is first rendered using a shader that applies surface attributes that do not depend on any light source, such as ambient illumination, emission, and environment mapping.

 

	Figure 1. An object’s shadow volume encloses the region of space for which light is blocked by the object.

The original stencil algorithm renders the shadow volume in two stages. In the first stage, the front faces of the shadow volume (with respect to the camera) are rendered using a stencil operation that increments the value in the stencil buffer whenever the depth test passes. In the second stage, the back faces of the shadow volume are rendered using a stencil operation that decrements the value in the stencil buffer whenever the depth test passes. As illustrated in Figure 2, this technique leaves nonzero values in the stencil buffer wherever the shadow volume intersects any surface in the scene, including the surface of the object casting the shadow.

 

	Figure 2. Numbers at the ends of rays emanating from the camera position C represent the values left in the stencil buffer for a variety of cases. The stencil value is incremented when front faces of the shadow volume pass the depth test, and the stencil value is decremented when back faces of the shadow volume pass the depth test. The stencil value does not change when the depth test fails.

There are two major problems with the method just described. The first is that no matter what finite distance we extrude an object’s silhouette away from a light source, it is still possible that it is not far enough to cast a shadow on every object in the scene that should intersect the shadow volume. The example shown in Figure 3 demonstrates how this problem arises when a light source is very close to a shadow-casting object. Fortunately, this problem can be elegantly solved by using a special projection matrix and extruding shadow volumes all the way to infinity.

 

	Figure 3. No matter what finite distance an object’s silhouette is extruded away from a light source, moving the light close enough to the object can result in a shadow volume that cannot reach other objects in the scene.

The second problem shows up when the camera lies inside the shadow volume or the shadow volume is clipped by the near plane. Either of these occurrences can leave incorrect values in the stencil buffer causing the wrong surfaces to be illuminated. The solution to this problem is to add caps to the shadow volume geometry, making it a closed surface, and using different stencil operations. The two caps added to the shadow volume are derived from the object’s triangle mesh as follows. A front cap is constructed using the unmodified vertices of triangles facing toward the light source. A back cap is constructed by projecting the vertices of triangles facing away from the light source to infinity. For the resulting closed shadow volume, we render back faces (with respect to the camera) using a stencil operation that increments the stencil value whenever the depth test fails, and we render front faces using a stencil operation that decrements the stencil value whenever the depth test fails. As shown in Figure 4, this technique leaves nonzero values in the stencil buffer for any surface intersecting the shadow volume for arbitrary camera positions. Rendering shadow volumes in this manner is more expensive than using the original technique, but we can determine when it’s safe to use the less-costly depth-pass method without having to worry about capping our shadow volumes.

 

	Figure 4. Using a capped shadow volume and depth-fail stencil operations allows the camera to be inside the shadow volume. The stencil value is incremented when back faces of the shadow volume fail the depth test, and the stencil value is decremented when front faces of the shadow volume fail the depth test. The stencil value does not change when the depth test passes.

The details of everything just described are discussed throughout the remainder of this article. In summary, the rendering algorithm for a single frame runs through the following steps.

A Clear the frame buffer and perform an ambient rendering pass. Render the visible scene using any surface shading attribute that does not depend on any particular light source.

B Choose a light source and determine what objects may cast shadows into the visible region of the world. If this is not the first light to be rendered, clear the stencil buffer.

C For each object, calculate the silhouette representing the boundary between triangles facing toward the light source and triangles facing away from the light source. Construct a shadow volume by extruding the silhouette away from the light source.

D Render the shadow volume using specific stencil operations that leave nonzero values in the stencil buffer where surfaces are in shadow.

E Perform a lighting pass using the stencil test to mask areas that are not illuminated by the light source.

F Repeat steps B through E for every light source that may illuminate the visible region of the world.

For a scene illuminated by n lights, this algorithm requires at least n+1 rendering passes. More than n+1 passes may be necessary if surface shading calculations for a single light source cannot be accomplished in a single pass. To efficiently render a large scene containing many lights, one must be careful during each pass to render only objects that could potentially be illuminated by a particular light source. An additional optimization using the scissor rectangle can also save a significant amount of rasterization work -- this optimization is discussed in the last section of this article.

One aspect of advanced rendering we haven't discussed yet is stenciling, a technique that can be useful for developing commercial applications. If you want your 3D applications to stand apart from the crowd, you'd be wise to combine stenciling with the texturing techniques you learned about in earlier chapters. This chapter will detail how to use stenciling and show you the different types of effects you can generate with it.

Many 3D games and simulations on the market use cinema-quality special effects to add to their dramatic impact. You can use stencil buffers to create effects such as composites, decals, dissolves, fades, outlines, silhouettes, swipes, and shadows. Stencil buffers determine whether the pixels in an image are drawn. To perform this function, stencil buffers let you enable or disable drawing to the render-target surface on a pixel-by-pixel basis. This means your software can "mask" portions of the rendered image so that they aren't displayed.

When the stenciling feature is enabled, Microsoft Direct3D performs a stencil test for each pixel that it plans to write to the render-target surface. The stencil test uses a stencil reference value, a stencil mask, a comparison function, and a pixel value from the stencil buffer that corresponds to the current pixel in the target surface. Here are the specific steps used in this test:

1. Perform a bitwise AND operation of the stencil reference value with the stencil mask.
2. Perform a bitwise AND operation on the stencil-buffer value for the current pixel with the stencil mask.
3. Compare the results of Step 1 and Step 2 by using the comparison function.

By controlling the comparison function, the stencil mask, the stencil reference value, and the action taken when the stencil test passes or fails, you can control how the stencil buffer works. As long as the test succeeds, the current pixel will be written to the target. The default comparison behavior (the value that the D3DCMPFUNC enumerated type defines for D3DCMP_ALWAYS) is to write the pixel without considering the contents of the stencil buffer. You can change the comparison function to any function you want by setting the value of the D3DRENDERSTATE_STENCILFUNC render state and passing one of the members of the D3DCMPFUNC enumerated type.

Creating a Stencil Buffer

Before creating a stencil buffer, you need to determine what stenciling capabilities the target system supports. To do this, call the IDirect3DDevice7::GetCaps method. The dwStencilCaps flags specify the stencil-buffer operations that the device supports. The reported flags are valid for all three stencil-buffer operation render states: D3DRENDERSTATE_STENCILFAIL, D3DRENDERSTATE_STENCILPASS, and D3DRENDERSTATE_STENCILZFAIL. Direct3D defines the following flags for dwStencilCaps:

• D3DSTENCILCAPS_DECR Indicates that the D3DSTENCILOP_DECR operation is supported
  
  
• D3DSTENCILCAPS_DECRSAT Indicates that the D3DSTENCILOP_DECRSAT operation is supported
  
  
• D3DSTENCILCAPS_INCR Indicates that the
  D3DSTENCILOP_INCR operation is supported
  
  
• D3DSTENCILCAPS_INCRSAT Indicates that the D3DSTENCILOP_INCRSAT operation is supported
  
  
• D3DSTENCILCAPS_INVERT Indicates that the D3DSTENCILOP_INVERT operation is supported
  
  
• D3DSTENCILCAPS_KEEP Indicates that the D3DSTENCILOP_KEEP operation is supported
  
  
• D3DSTENCILCAPS_REPLACE Indicates that the D3DSTENCILOP_REPLACE operation is supported
  
  
• D3DSTENCILCAPS_ZERO Indicates that the D3DSTENCILOP_ZERO operation is supported
  

Parameter	Description
riidDevice	A reference to a globally unique identifier (GUID) for the device whose depth-buffer formats you want enumerated
IpEnumCallback	The address of a D3DEnumPixelFormatsCallback function you want called for each supported depth-buffer format
IpContext	Application-defined data that is passed to the callback function

If the method succeeds, it returns the value D3D_OK. If it fails, the method returns one of these four values:

• DDERR_INVALIDOBJECT
  
  
• DDERR_INVALIDPARAMS
  
  
• DDER_NOZBUFFERHW
  
  
• DDERR_OUTOFMEMORY

The code in listing 1 determines what stencil buffer formats are available and what operations are supported and then creates a stencil buffer. As you can see, this code notes whether the stencil buffer supports more than 1-bit -- some stenciling techniques must be handled differently if only a 1-bit stencil buffer is available.

Clearing a Stencil Buffer

The IDirect3DDevice7 interface includes the Clear method, which you can use to simultaneously clear the render target's color buffer, depth buffer, and stencil buffer. Here's the declaration for the IDirect3DDevice7::Clear method:

    HRESULT IDirect3DDevice7::Clear(
       DWORD dwCount,
       LPD3DRECT lpRects,
       DWORD dwFlags,
       D3DVALUE dvZ,
       DWORD dwStencil
    );

Parameter	Description
dwCount	The number of rectangles in the array at lpRects.
IpRects	An array of D3DRECT structures defining the rectangles to be cleared. You can set a rectangle to the dimensions of the render-target surface to clear the entire surface. Each of these rectangles uses screen coordinates that correspond to points on the render-target surface. The coordinates are clipped to the bounds of the viewport rectangle.
dwFlags	Flags indicating which surfaces should be cleared. This parameter can be any combination of the following flags, but at least one flag must be used:
	D3DCLEAR_TARGET Clear the render-target surface to the color in the dwColor parameter. D3DCLEAR_STENCIL Clear the stencil buffer to the value in the dwStencil parameter.
	D3DCLEAR_ZBUFFER Clear the depth buffer to the value in the dvZ parameter.
dwColor	D3DCLEAR_ZBUFFER Clear the depth buffer to the value in the dvZ parameter..
dvZ	A 32-bit RGBA color value to which the render-target surface will be cleared.
dwStencil	The new z value that this method stores in the depth buffer. This parameter can range from 0.0 to 1.0, inclusive. The value of 0.0 represents the nearest distance to the viewer, and 1.0 represents the farthest distance.
	The integer value to store in each stencil-buffer entry. This parameter can range from 0 to 2n-1 inclusive, in which n is the bit depth of the stencil buffer.

The IDirect3DDevice7::Clear method still accepts the older D3DCLEAR_TARGET flag, which clears the render target using an RGBA color you provide in the dwColor parameter. This method also still accepts the D3DCLEAR_ZBUFFER flag, which clears the depth buffer to a depth you specify in dvZ (in which 0.0 is the closest distance and 1.0 is the farthest). DirectX 6 introduced the D3DCLEAR_STENCIL flag, which you can use to reset the stencil bits to the value you specify in the dwStencil parameter. This value can be an integer ranging from 0 to 2n-1, in which n is the bit depth of the stencil buffer.

________________________________________________________

Configuring the Stenciling State

Configuring the Stenciling State
You control the various settings for the stencil buffer using the IDirect3DDevice7::
SetRenderState method. Listing 2 shows the stencil-related members of the D3DRENDERSTATETYPE enumerated type.

      These are the definitions for the stencil-related render states:

• D3DRENDERSTATE_STENCILENABLE Use this member to enable or disable stenciling. To enable stenciling, use this member with TRUE; to disable stenciling, use it with FALSE. The default value is FALSE.
  
  
• D3DRENDERSTATE_STENCILFAIL Use this member to indicate the stencil operation to perform if the stencil test fails. The stencil operation can be one of the members of the D3DSTENCILOP enumerated type. The default value is D3DSTENCILOP_KEEP.
  
  
• D3DRENDERSTATE_STENCILZFAIL Use this member to indicate the stencil operation to perform if the stencil test passes and the depth test (z-test) fails. The operation can be one of the members of the D3DSTENCILOP enumerated type. The default value is D3DSTENCILOP_KEEP.
  
  
• D3DRENDERSTATE_STENCILPASS Use this member to indicate the stencil operation to perform if both the stencil test and the depth test (z-test) pass. The operation can be one of the members of the D3DSTENCILOP enumerated type. The default value is D3DSTENCILOP_KEEP.
  
  
• D3DRENDERSTATE_STENCILFUNC Use this member to indicate the comparison function for the stencil test. The comparison function can be one of the members of the D3DCMPFUNC enumerated type. The default value is D3DCMP_ALWAYS. This function compares the reference value to a stencil-buffer entry and applies only to the bits in the reference value and stencil-buffer entry that are set in the stencil mask. (The D3DRENDERSTATE_STENCILMASK render state sets the stencil mask.) If the comparison is true, the stencil test passes.
  
  
• D3DRENDERSTATE_STENCILREF Use this member to indicate the integer reference value for the stencil test. The default value is 0.
  
  
• D3DRENDERSTATE_STENCILMASK Use this member to specify the mask to apply to the reference value and each stencil-buffer entry to determine the significant bits for the stencil test. The default mask is 0xFFFFFFFF.
  
  
• D3DRENDERSTATE_STENCILWRITEMASK Use this member to specify the mask to apply to values written into the stencil buffer. The default mask is 0xFFFFFFFF.
  
  

The D3DSTENCILOP enumerated type describes the stencil operations for the D3DRENDERSTATE_STENCILFAIL, D3DRENDERSTATE_STENCILZFAIL, and D3DRENDERSTATE_STENCILPASS render states. Here's the definition of D3DSTENCILOP:

    //--------------------------------------------------
    // Name: RenderShadow
    // Desc:
    //------------------------------------------------
    HRESULT CMyD3DApplication::RenderShadow()
    {
        // Turn off depth buffer and turn on
           stencil buffer.
        m_pd3dDevice->SetRenderState(
                           D3DRENDERSTATE_ZWRITEENABLE,
                                     FALSE );
        m_pd3dDevice->SetRenderState(
                           D3DRENDERSTATE_STENCILENABLE,
                                     TRUE );

Next the code sets the comparison function that performs the stencil test by calling the IDirect3DDevice7::SetRenderState method and setting the first parameter to D3DRENDERSTATE_STENCILFUNC. The second parameter is set to a member of the D3DCMPFUNC enumerated type. In this code, we want to update the stencil buffer everywhere a primitive is rendered, so we use D3DCMP_ALWAYS:

     //
    // Set up stencil comparison function,
       reference value, and masks.
    // Stencil test passes if ((ref & mask)
       cmpfn (stencil & mask))
    // is true.
    //
    m_pd3dDevice->SetRenderState(
                           D3DRENDERSTATE_STENCILFUNC,
                                 D3DCMP_ALWAYS );

In this sample, we don't want the stencil buffer to change if either the stencil buffer test or the depth buffer test fails, so we set the appropriate states to D3DSTENCILOP_KEEP:

     m_pd3dDevice->SetRenderState(
                          D3DRENDERSTATE_STENCILZFAIL,
                                  D3DSTENCILOP_KEEP );
     m_pd3dDevice->SetRenderState(
                          D3DRENDERSTATE_STENCILFAIL,
                                  D3DSTENCILOP_KEEP );

The settings in listing 3 are different depending on whether a 1-bit or a multibit stencil buffer is present. If the stencil buffer has only 1 bit, the value 1 is stored in the stencil buffer whenever the stencil test passes. Otherwise, an increment operation (either D3DSTENCILOP_INCR or D3DSTENCILOP_INCRSAT) is applied if the stencil test passes. At this point, the stencil state is configured and the code is ready to render some primitives.

________________________________________________________

Creating Effects

Creating Effects
Now that you've seen how to create stencil buffers and configure how they work, let's look at some of the effects you can render with them. The following sections describe several ways Microsoft recommends using stencil buffers. Each of these approaches produces impressive results, but a few of them have drawbacks.

Composites

You can use stencil buffers for compositing 2D or 3D images onto a 3D scene. By using a mask in the stencil buffer to occlude a portion of the render-target surface, you can write stored 2D information (such as text or bitmaps). You can also render 3D primitives -- or for that matter a complete scene -- to the area of the render-target surface that you specify in a stencil mask.

Developers often use this effect to composite several scenes in simulations and games. Many driving games feature a rear view mirror that displays the scene behind the driver. You can composite this second 3D scene with the driver's view forward by using a stencil to block the portion to which you want the mirror image rendered. You can also use composites to create 2D "cockpits" for vehicle simulations by combining a 2D, bitmapped image of the cockpit with the final, rendered 3D scene.

Decals

You can use decals to control which pixels form a primitive image you draw to a render-target surface. When you apply a texture to an object (for example, applying scratch marks to a floor), you need the texture (the scratch marks) to appear immediately on top of the object (the floor). Because the z values of the scratch marks and the floor are equal, the depth buffer might not yield consistent results, meaning that some pixels in the back primitive might be rendered on top of those in the front primitive. This overlap, which is commonly known as z-fighting or flimmering, can cause the final image to shimmer as you animate from one frame to the next.

You can prevent flimmering by using a stencil to mask the section of the back primitive on which you want the decal to appear. You can then turn off z-buffering and render the image of the front primitive into the masked area of the render-target surface.

Dissolves

You can use dissolves to gradually replace an image by displaying a series of frames that transition from one image to another. In Chapter 8, you saw how to use multiple-texture blending to create this effect by gradually blending two textures together. Stencil buffers allow you to produce similar dissolves, except that a stencil-based dissolve looks more pixelated than a multiple-texture blending one. However, stencil buffers let you use texture-blending capabilities for other effects while performing a dissolve. This capability enables you to efficiently produce more complex effects than you could by using texture blending alone.

A stencil buffer can perform a dissolve by controlling which pixels you draw from two different images to the render-target surface. You can perform a dissolve by defining a base stencil mask for the first frame and altering it incrementally or by defining a series of stencil masks and copying them into the stencil buffer on successive frames.

To start a dissolve, set the stencil function and stencil mask so that most of the pixels from the starting image pass the stencil test and most of the ending image's pixels fail. For each subsequent frame, update the stencil mask to allow fewer pixels in the starting image to pass the test and more pixels in the ending image to pass. By controlling the stencil mask, you can create a variety of dissolve effects.

Although this approach can produce some fantastic effects, it can be a bit slow on some systems. You should test the performance on your target systems to verify that this approach works efficiently for your application.

Fades

You can fade in or out using a form of dissolving. To perform this effect, use any dissolve pattern you want. To fade in, use a stencil buffer to dissolve from a black or white image to a rendered 3D scene. To fade out, start with a rendered 3D scene and dissolve to black or white. As with dissolves, you should check the performance of fades on the target systems to verify that their speed and appearance is acceptable.

Outlines

You can apply a stencil mask to a primitive that's the same shape but slightly smaller than the primitive. The resulting image will contain only the primitive's outline. You can then fill this stencil-masked area of the primitive with a color or set of colors to produce an outline around the image.

Silhouettes

When you set the stencil mask to the same size and shape as the primitive you're rendering, Direct3D produces a final image containing a "black hole" where the primitive should be. By coloring this hole, you can produce a silhouette of the primitive.

Swipes

A swipe makes an image appear as though it's sliding into the scene over another image. You can use stencil masks to disable the writing of pixels from the starting image and enable the writing of pixels from the ending image. To perform a swipe, you can define a series of stencil masks that Direct3D will load into the stencil buffer in a succession of frames, or you can change the starting stencil mask for a series of successive frames. Both methods cause the final image to look as though it's gradually sliding on top of the starting image from right to left, left to right, top to bottom, and so on.

To handle a swipe, remember to read the pixels from the ending image in the reverse order in which you're performing the swipe. For example, if you're performing a swipe from left to right, you need to read pixels from the ending image from right to left. As with dissolves, this effect can render somewhat slowly. Therefore, you should test its performance on your target systems.

Shadows

Shadow volumes, which allow an arbitrarily shaped object to cast a shadow onto another arbitrarily shaped object, can produce some incredibly realistic effects. To create shadows with stencil buffers, take an object you want to cast a shadow. Using this object and the light source, build a set of polygonal faces (a shadow volume) to represent the shadow.

You can compute the shadow volume by projecting the vertices of the shadow-casting object onto a plane that's perpendicular to the direction of light from the light source, finding the 2D convex hull of the projected vertices (that is, a polygon that "wraps around" all the projected vertices), and extruding the 2D convex hull in the light direction to form the 3D shadow volume. The shadow volume must extend far enough so that it covers any objects that will be shadowed. To simplify computation, you might want the shadow caster to be a convex object.

To render a shadow, you must first render the geometry and then render the shadow volume without writing to the depth buffer or the color buffer. Use alpha blending to avoid having to write to the color buffer. Each place that the shadow volume appears will be marked in the stencil buffer. You can then reverse the cull and render the backfaces of the shadow volume, unmarking all the pixels that are covered in the stencil buffer. All these pixels will have passed the z-test, so they'll be visible behind the shadow volume. Therefore, they won't be in shadow. The pixels that are still marked are the ones lying inside the front and back boundaries of the shadow volume-these pixels will be in shadow. You can blend these pixels with a large black rectangle that covers the viewport to generate the shadow.

The ShadowVol and ShadowVol2 Demos

The ShadowVol sample on the companion CD in the \mssdk\Samples\Multimedia\D3dim\Src\ShadowVol directory contains a project that shows how to create and use stencil buffers to implement shadow volumes. The code illustrates how to use shadow volumes to cast the shadow of an arbitrarily shaped object onto another arbitrarily shaped object. The ShadowVol2 sample, which the Microsoft DirectX 7 SDK setup program on the companion CD installs in the \mssdk\Samples\Multimedia\D3dim\Src\ShadowVol2 directory on your hard disk, provides some additional capabilities for producing shadows with stencils.

The sample application provides these features in its Shadow Modes menu:

• Draw Shadows: Allows you to turn on and off shadow rendering.
  
  
• Show Shadow Volumes: Draws the shadow volumes used to compute the shadows rather than drawing the shadows themselves.
  
  
• Draw Shadow Volume Caps: When you turn this item off, some "extra" shadows might become visible where the far caps of the cylindrical shadow volumes happen to be visible.
  
  
• 1-Bit Stencil Buffer Mode: Tells the code to use a different algorithm that uses only 1 bit of stencil buffer, which won't allow overlapping shadows. If the device supports only 1-bit stencils, you'll be forced to use this mode.
  
  
• Z-Order Shadow Vols in 1-Bit Stencil Buffer Mode: The shadow volumes must be rendered front to back, which means that if you don't check this option, rendering might be incorrect.

<<"F12xi01.eps">>

Figure 12-1. Shadow cast

<<"F12xi02.eps">>

Figure 12-2. Shadow volumes

<<"F12xi03.eps">>

Figure 12-3. Another view of the rendered shadows

The Code So Far

In this chapter, we didn't add any new code to the RoadRage project. To see these effects in action, refer to the ShadowVol and ShadowVol2 demo projects included in the DirectX samples.

Conclusion

In this chapter, you learned about stencil buffers and the exciting effects they can produce. In today's market, making your code stand out is a requisite if you want it to sell your applications and keep your users coming back for more. Incorporating strategic stencil-buffer effects into the introduction and into the body of a 3D real-time game might help you win over even the most discriminating game players.

In Chapter 13, we'll discuss how to load and animate 3D models. Creating animated, lifelike characters that your users can interact with is one of the most powerful capabilities you can add to any game.

Peter Kovach has been involved in computer software and hardware development since the mid-1970s. After 11 years in various levels of development and project management, he was eager to being pushing the envelope in 3D virtual world development. He currently words at Medtronic, where he is the project lead developming programmable, implantable medical devices that use a next-generation graphical user interface.

Collision detection

From Wikipedia, the free encyclopedia

Jump to: navigation, search

For collision detection on networks see CSMA/CD

In physical simulations, video games and computational geometry, collision detection involves algorithms for checking for collision, i.e. intersection, of two given solids. Simulating what happens once a collision is detected is sometimes referred to as "collision response", for which see physics engine and ragdoll physics. Collision detection algorithms are a basic component of 3D video games. Without them, characters could go through walls and other obstacles.

Contents [hide] 1 Overview 2 Collision detection in physical simulation 2.1 A posteriori versus a priori 3 Optimization 3.1 Exploiting temporal coherence 3.2 Pairwise pruning 3.3 Exact pairwise collision detection 3.4 A priori pruning 3.5 Spatial partitioning 4 Video games 5 Open Source Collision Detection 6 References 7 See also 8 External links

[edit] Overview

Billiards balls hitting each other are a classic example applicable within the science of collision detection.

In physical simulation, we wish to conduct experiments, such as playing billiards. The physics of bouncing billiard balls are well understood, under the umbrella of rigid body motion and elastic collisions. An initial description of the situation would be given, with a very precise physical description of the billiard table and balls, as well as initial positions of all the balls. Given a certain impulsion on the cue ball (probably resulting from a player hitting the ball with his cue stick), we want to calculate the trajectories, precise motion, and eventual resting places of all the balls with a computer program. A program to simulate this game would consist of several portions, one of which would be responsible for calculating the precise impacts between the billiard balls. This particular example also turns out to be numerically unstable: a small error in any calculation will cause drastic changes in the final position of the billiard balls.

Video games have similar requirements, with some crucial differences. While physical simulation needs to simulate real-world physics as precisely as possible, video games need to simulate real-world physics in an acceptable way, in real time and robustly. Compromises are allowed, so long as the resulting simulation is satisfying to the game player.

[edit] Collision detection in physical simulation

Physical simulators differ in the way they react on a collision. Some use the softness of the material to calculate a force, which will resolve the collision in the following time steps like it is in reality. Due to the low softness of some materials this is very CPU intensive. Some simulators estimate the time of collision by linear interpolation, roll back the simulation, and calculate the collision by the more abstract methods of conservation laws.

Some iterate the linear interpolation (Newton's method) to calculate the time of collision with a much higher precision than the rest of the simulation. Collision detection utilizes time coherence to allow ever finer time steps without much increasing CPU demand, such as in air traffic control.

After an inelastic collision, special states of sliding and resting can occur and, for example, the Open Dynamics Engine uses constrains to simulate them. Constrains avoid inertia and thus instability. Implementation of rest by means of a scene graph avoids drift.

In other words, physical simulators usually function one of two ways, where the collision is detected a posteriori (after the collision occurs) or a priori (before the collision occurs). In addition to the a posteriori and a priori distinction, almost all modern collision detection algorithms are broken into a hierarchy of algorithms.

[edit] A posteriori versus a priori

In the a posteriori case, we advance the physical simulation by a small time step, then check if any objects are intersecting, or are somehow so close to each other that we deem them to be intersecting. At each simulation step, a list of all intersecting bodies is created, and the positions and trajectories of these objects are somehow "fixed" to account for the collision. We say that this method is a posteriori because we typically miss the actual instant of collision, and only catch the collision after it has actually happened.

In the a priori methods, we write a collision detection algorithm which will be able to predict very precisely the trajectories of the physical bodies. The instants of collision are calculated with high precision, and the physical bodies never actually interpenetrate. We call this a priori because we calculate the instants of collision before we update the configuration of the physical bodies.

The main benefits of the a posteriori methods are as follows. In this case, the collision detection algorithm need not be aware of the myriad physical variables; a simple list of physical bodies is fed to the algorithm, and the program returns a list of intersecting bodies. The collision detection algorithm doesn't need to understand friction, elastic collisions, or worse, nonelastic collisions and deformable bodies. In addition, the a posteriori algorithms are in effect one dimension simpler than the a priori algorithms. Indeed, an a priori algorithm must deal with the time variable, which is absent from the a posteriori problem.

On the other hand, a posteriori algorithms cause problems in the "fixing" step, where intersections (which aren't physically correct) need to be corrected. In fact, there are some^[who?] who believe that such an algorithm is inherently flawed and unstable^{[citation needed]}.

The benefits of the a priori algorithms are increased fidelity and stability. It is difficult (but not completely impossible) to separate the physical simulation from the collision detection algorithm. However, in all but the simplest cases, the problem of determining ahead of time when two bodies will collide (given some initial data) has no closed form solution -- a numerical root finder is usually involved.

Some objects are in resting contact, that is, in collision, but neither bouncing off, nor interpenetrating, such as a vase resting on a table. In all cases, resting contact requires special treatment: If two objects collide (a posteriori) or slide (a priori) and their relative motion is below a threshold, friction becomes stiction and both objects are arranged in the same branch of the scene graph; however, some believe that it poses special problems in a posteriori algorithm^{[citation needed]}.

[edit] Optimization

The obvious approaches to collision detection for multiple objects are very slow. Checking every object against every other object will, of course, work, but is too inefficient to be used when the number of objects is at all large. Checking objects with complex geometry against each other in the obvious way, by checking each face against each other face, is itself quite slow. Thus, considerable research has been applied to speeding up the problem.

[edit] Exploiting temporal coherence

In many applications, the configuration of physical bodies from one time step to the next changes very little. Many of the objects may not move at all. Algorithms have been designed so that the calculations done in a preceding time step can be reused in the current time step, resulting in faster algorithms.

At the coarse level of collision detection, the objective is to find pairs of objects which might potentially intersect. Those pairs will require further analysis. An early high performance algorithm for this was developed by M. C. Lin at U.C. Berkley [1], who suggested using axis-aligned bounding boxes for all n bodies in the scene.

Each box is represented by the product of three intervals (i.e., a box would be .) A common algorithm for collision detection of bounding boxes is sweep and prune. We observe that two such boxes, and intersect if, and only if, I₁ intersects J₁, I₂ intersects J₂ and I₃ intersects J₃. We suppose that, from one time step to the next, I_k and J_k intersect, then it is very likely that at the next time step, they will still intersect. Likewise, if they did not intersect in the previous time step, then they are very likely to continue not to.

So we reduce the problem to that of tracking, from frame to frame, which intervals do intersect. We have three lists of intervals (one for each axis) and all lists are the same length (since each list has length n, the number of bounding boxes.) In each list, each interval is allowed to intersect all other intervals in the list. So for each list, we will have an matrix M = (m_ij) of zeroes and ones: m_ij is 1 if intervals i and j intersect, and 0 if they do not intersect.

By our assumption, the matrix M associated to a list of intervals will remain essentially unchanged from one time step to the next. To exploit this, the list of intervals is actually maintained as a list of labeled endpoints. Each element of the list has the coordinate of an endpoint of an interval, as well as a unique integer identifying that interval. Then, we sort the list by coordinates, and update the matrix M as we go. It's not so hard to believe that this algorithm will work relatively quickly if indeed the configuration of bounding boxes does not change significantly from one time step to the next.

In the case of deformable bodies such as cloth simulation, it may not be possible to use a more specific pairwise pruning algorithm as discussed below, and an n-body pruning algorithm is the best that can be done.

If an upper bound can be placed on the velocity of the physical bodies in a scene, then pairs of objects can be pruned based on their initial distance and the size of the time step.

[edit] Pairwise pruning

Once we've selected a pair of physical bodies for further investigation, we need to check for collisions more carefully. However, in many applications, individual objects (if they are not too deformable) are described by a set of smaller primitives, mainly triangles. So now, we have two sets of triangles, and (for simplicity, we will assume that each set has the same number of triangles.)

The obvious thing to do is to check all triangles S_j against all triangles T_k for collisions, but this involves n² comparisons, which is highly inefficient. If possible, it is desirable to use a pruning algorithm to reduce the number of pairs of triangles we need to check.

The most widely used family of algorithms is known as the hierarchical bounding volumes method. As a preprocessing step, for each object (in our example, S and T) we will calculate a hierarchy of bounding volumes. Then, at each time step, when we need to check for collisions between S and T, the hierarchical bounding volumes are used to reduce the number of pairs of triangles under consideration. For the sake of simplicity, we will give an example using bounding spheres, although it has been noted that spheres are undesirable in many cases.^{[citation needed]}

If E is a set of triangles, we can precalculate a bounding sphere B(E). There are many ways of choosing B(E), we only assume that B(E) is a sphere that completely contains E and is as small as possible.

Ahead of time, we can compute B(S) and B(T). Clearly, if these two spheres do not intersect (and that is very easy to test,) then neither do S and T. This is not much better than an n-body pruning algorithm, however.

If is a set of triangles, then we can split it into two halves and . We can do this to S and T, and we can calculate (ahead of time) the bounding spheres B(L(S)),B(R(S)) and B(L(T)),B(R(T)). The hope here is that these bounding spheres are much smaller than B(S) and B(T). And, if, for instance, B(S) and B(L(T)) do not intersect, then there is no sense in checking any triangle in S against any triangle in L(T).

As a precomputation, we can take each physical body (represented by a set of triangles) and recursively decompose it into a binary tree, where each node N represents a set of triangles, and its two children represent L(N) and R(N). At each node in the tree, as a we can precompute the bounding sphere B(N).

When the time comes for testing a pair of objects for collision, their bounding sphere tree can be used to eliminate many pairs of triangles.

Many variants of the algorithms are obtained by choosing something other than a sphere for B(T). If one chooses axis-aligned bounding boxes, one gets AABBTrees. Oriented bounding box trees are called OBBTrees. Some trees are easier to update if the underlying object changes. Some trees can accommodate higher order primitives such as splines instead of simple triangles.

[edit] Exact pairwise collision detection

Once we're done pruning, we are left with a number of candidate pairs to check for exact collision detection.

A basic observation is that for any two convex objects which are disjoint, one can find a plane in space so that one object lies completely on one side of that plane, and the other object lies on the opposite side of that plane. This allows the development of very fast collision detection algorithms for convex objects.

Early work in this area involved "separating plane" methods. Two triangles collide essentially only when they can not be separated by a plane going through three vertices. That is, if the triangles are v₁,v₂,v₃ and v₄,v₅,v₆ where each v_j is a vector in , then we can take three vertices, v_i,v_j,v_k, find a plane going through all three vertices, and check to see if this is a separating plane. If any such plane is a separating plane, then the triangles are deemed to be disjoint. On the other hand, if none of these planes are separating planes, then the triangles are deemed to intersect. There are twenty such planes.

If the triangles are coplanar, this test is not entirely successful. One can either add some extra planes, for instance, planes that are normal to triangle edges, to fix the problem entirely. In other cases, objects that meet at a flat face must necessarily also meet at an angle elsewhere, hence the overall collision detection will be able to find the collision.

Better methods have since been developed. Very fast algorithms are available for finding the closest points on the surface of two convex polyhedral objects. Early work by M. C. Lin ^[1] used a variation on the simplex algorithm from linear programming. The Gilbert-Johnson-Keerthi distance algorithm has superseded that approach. These algorithms approach constant time when applied repeatedly to pairs of stationary or slow-moving objects, when used with starting points from the previous collision check.

The end result of all this algorithmic work is that collision detection can be done efficiently for thousands of moving objects in real time on typical personal computers and game consoles.

[edit] A priori pruning

Where most of the objects involved are fixed, as is typical of video games, a priori methods using precomputation can be used to speed up execution.

Pruning is also desirable here, both n-body pruning and pairwise pruning, but the algorithms must take time and the types of motions used in the underlying physical system into consideration.

When it comes to the exact pairwise collision detection, this is highly trajectory dependent, and one almost has to use a numerical root-finding algorithm to compute the instant of impact.

As an example, consider two triangles moving in time v₁(t),v₂(t),v₃(t) and v₄(t),v₅(t),v₆(t). At any point in time, the two triangles can be checked for intersection using the twenty planes previously mentioned. However, we can do better, since these twenty planes can all be tracked in time. If P(u,v,w) is the plane going through points u,v,w in