Thesis Update

Future Work

2005-09-20T16:51:00.000+02:00

Additional Feedback

The force feedback was difficult to feel during testing. The vibration caused by the drill made feeling some forces impossible. Many errors were caused when the feedback could not be felt. Adding sound to the program could increase the experience. Sound could give the user additional feedback. For example, the closer the distance between two objects the higher the frequency.

Density

A density property exists in the octree structure but is currently unused. This is when collisions occur with a leaf node and should be viewed as object persistence. Currently, leaf nodes are removed after a collision between a leaf node and the cursor object occurs. The possible extension is to modify a counter when collisions occur and only remove the leaf when the counter expires. This can be extended to represent 3D data with density information.

Graphics improvements

The current program displays the maximum haptics workspace as the screen dimensions. This should be changed to better fit the drilling area. A zoom feature is not implemented and the current camera angle rotations are controlled by the keyboard. Ideally the haptic device should control this. The haptics could be used to position the viewing angle by capturing the motion of the haptics endpoint. Rotations could also be obtained from the orientation of the haptic device.

The marching cubes algorithm needs to be adjusted. Holes appear in the current implementation. The problem is when one branch has all 8 leaf nodes removed.

Alternative Device

Stronger force feedback should be tested to prevent removing desired material. Currently the forces provide the user with the knowledge that the desired shape is near but the user can easily overpower the force feedback. Larger haptic devices from SensAble Technologies provide increased forces.

The program should be easily scalable to work with a larger device by SensAble. The other devices are capable of rendering stronger forces and have greater accuracy. The levels of force would have to be adjusted in an extended program but most other features are similar between all SensAble devices because they all can use the OpenHaptics Toolkit and the HDAPI.

Voxelization

It is possible to precompute the collision space of for the STL object. The octree object would be modified to store the shape of the STL object. This could remove using the SWIFT collision detection package with the tradeoff being that the resolution of the octree would determine the accuracy of the final shape.

2005-09-02T19:56:00.000+02:00

August Test 1: Torus

Spam

2005-08-19T23:26:00.000+02:00

Due to unsolicited posting I have disabled anonymous posting. I can be reached by email or members of blogspot.com are allowed to post. I encourage anyone with questions or comments to post or contact me. I am very interested in hearing feedback about this site.

Testing Issue

2005-08-18T17:15:00.000+02:00

I have been testing for over 2 weeks. What has become apparent is the tool calibration does not work. I have been trying to troubleshoot this problem to no avail. The transformation matrix that is generated from the code varies. The endpoint position calculated can vary by 5 - 10 mm. I have halted further testing until this can be resolved.

I have checked matrix multiplication, both order and differences between column major and row major. I have upgraded the API and reinstalled the drivers that the haptic device uses. I tried hard coding the translation determined from measuring. This did not work either. I am leaning towards the hardware being defective or that the haptic device is not capable of giving the required accuracy.

Sample Test pictures and screenshots available here as long as my student account stays open.

Marching Cubes

2005-07-24T13:36:00.000+02:00

I realized after reading through other research papers that implementing the Marching Cubes algorithm into my project would not be difficult. The octree data structure is ideal for adding the marching cubes technique.

The octree structure has branch and leaf nodes. The leaf nodes could be viewed as vertices rather than cubes. The leaf nodes are updated to reflect whether they are outside, are on the border or inside of the object. Each branch keeps track of 8 children and whether a child should be drawn. This reduces branches that need to be visited when drawing the object. If a branch has one child that is on the border, then the current branch should be drawn.

Source code was obtained that provides a lookup table with 256 entries. This is because there are 2^8 possible combinations. These can be reduced to around 15 general cases due to rotations but a lookup table lists all triangles that should be drawn for each case.

The triangles are formed using midway points between the vertices. There are 8 vertices for a cube and there are 12 midway points. These points are referenced in the lookup table. Normals can then be computed from the order of the midpoints.

Kinematic Chain

2005-07-20T21:11:00.000+02:00

The order of matrix multiplication is crutial for obtaining correct orientation and position information. The kinematic chain is the order that the transformation matrices are multiplied in order to move between coordinate systems.

The haptic device has an internal kinematic chain that we will not explore, but we will use the haptics coordinate at (0,0,0) using the right hand rule and with no rotation. Having the haptic device directly in front of you. The x-axis is positive to the right. The y-axis is positive to the ceiling. The z-axis is positive in the direction away from the haptic device.

The haptics has a base coordinate system that we will use as the world coordinate system. Transformations are calculated in the following ways

Haptics (World Zero) -- This is identity 4x4 matrix
Stylus (Center of Rotation) -- Calculated and Returned from HD - HD_Current_Transform
Tool Tip (TCP) -- Calibrated from reading in points
WorkPiece (Orientation) -- Read in from calibration subroutine

Kinematic Chain
Tool Tip to Haptics

T = Tool Tip x Stylus

Tool Tip to WorkPiece

T = Tool Tip x Stylus x inverse(WorkPiece)

Freeze

2005-07-20T19:15:00.000+02:00

Last week I put a freeze on development. No new features will be implemented in this system. The next phase of the project is testing. This week of coding is dedicated to making cosmetic changes and increasing reliability. Current features to wrap up include combining getting the dimensions and coordinate system of the stock material and creating a bounding box around the STL/TRI object and fitting it into the octree object.

The console based interface is getting updated to use GLUI. This puts a java looking panel in an openGl window. This plugs in nicely with existing code. The GLUI allows programmers to build buttons, panels, etc. manually with the same effect as with windows forms.

Force Rendering

The problem with force rendering was solved by changing a setting used with the SWIFT collision detection package. There are two options offered when creating the workspace for the collision detection. Sorting deals with the way the program sorts the objects to try to optimize the search.

Broad Phase offers the option to create tight bounding boxes around the object. This optimizes the query phase. If the object position is not inside of the bounding box, then no test is made and data will be returned from a query. This reduces the amount of computation by closely representing the object by the bounding boxes.

However, this causes a problem when making queries. There are various queries offered by the package and most allow the user to specify a threshold as to when the function should return a value. This doesn't work when the Broad Phase option is selected. When option is disabled, then queries return the distance between objects within the set tolerence.

Force Smoothing

2005-07-06T16:26:00.000+02:00

The haptic device does not react well to the forces sent by the project. According to the haptics documentation, buzzing occurs when the haptic device can't render the forces. This can occur when the force is too high, there direction changes or the difference between forces is too great. The documentation recommends smoothing the forces.

Force with STL

The SWIFT collision detection package has a funtion that returns the normal vector between two objects. This can be used as the direction of the force vector. The distance between the objects is returned as well. The smoothing will keep track of past forces and take an average of the forces. Weights will be adjusted to ensure a smooth performance.

Force with octree

The force vector will be in the opposite direction of motion. The negative of the velocity vector is used to simulate resistance when contacting a cell.

A possible enhancement to this technique is adding a counter to the cells. Currently a cell is removed the first time contact is made with the tooltip. The counter could be used to remove the cell only when the counter reaches a certain limit. This would delay the removal and allow the force to be rendered for a longer time.

Initializing the Stock Material

2005-07-06T16:18:00.000+02:00

Professor Horsch provided me with code to create a transformation matrix from reading in 3 points; origin, x-axis and y-axis. The code was included into the project but could not be tested until the haptic to screen mapping was working. After fixing the mapping last week the code was tested.

The matrix mulitplication needed is as follows:

Translation from default haptic TCP to desired Tooltip *
Current Transformation Matrix from world center point to TCP *
inverted Transformation Matrix from world center point to origin of stock material

After this multiplication, the coordinates can be used as input to the collision detection algorithms. This does not take into account orientation of the tooltip, and this doesn't matter is the tooltip is a sphere.

Week Update 24, 2005

2005-06-27T13:51:00.000+02:00

Progress

This week I resolved the issue where the drawn graphic cursor position and actual haptic cursor position were different. The haptics and and collision detection algorithms were correct, but the cursor was drawn with an extra offset. This was because code from the project simpleHapticScene was used in stlViewer to draw the cursor. The code was copied into the prototype project unchanged.

The original code multiplies the current openGL matrix with the modelview matrix and then the transform from the haptics to get the cursor into the correct position. In prototype the openGL draw is different. It uses a glLookAt() function rather than glFrustrum(). By eliminating the extra matrix multiplication, the cursor appears at the correct position.

Project prototype

The octree structure was incorporated into the project. The octree structure is different from the voxel structure, so I will introduce a new keyword octree object. An octree divides a cube into 8 sub cubes recursively. Each node has 8 children and a link back to the parent node. The root is the beginning node with the maximum coordinates of the stock material.

The advantage of using an octree is that it is meant to have better performance when searching for a specific cell. My implementation keeps track of whether its children should be drawn or checked for collisions. This is achieved by having a boolean variable for each child and only visiting child nodes that are set. Children nodes update the parent when they are updated. For example, a collision is detected and a leaf node must be removed. The cell sets a variable so that it is marked removed and then tells its’ parent node that it is no longer active. The parent node checks the rest of the children if there are any cells that are still active. If there aren’t it will tell its’ parent that it is no longer active.

The initial performance of the collision detection and drawing of the cells were as expected. Collisions with the octree object and the haptics cursor were detected and handled without noticeable drag. The code was tested first without haptic feedback and then with haptic feedback and the system seemed to perform the same.

Statistics

The numbers I use are not exact and are often estimated. I use worst case or simple cases to compare performance. The observations are not meant to be exact or always true, but are meant to justify the use of octrees.

I didn’t like using the voxel object because every cycle of the openGL thread would visit every cell in the voxel object. Although it would only check a variable whether it would have to be drawn, it was still at least 128^3 (~2,000,000) checks. This doesn’t include the operations if the cell had to be drawn. When drawing the outer shell, the octree had to check (~225,000) cells. This is a saving of about a factor of 10.

On the other hand, if every cell must be drawn then it is likely that the voxel object would outperform the octree object. The octree would have to check nearly 4.5 million cells. This is an extreme case and this project would never draw every cell because the inside of the octree object is hollow. Another reason that the performance shouldn’t be that bad is that all cells that are inside of the STL/TRI object will not be drawn. I assume on average the STL/TRI object will take up at least 50% of the space.

The memory requirement for the voxel object is higher than the voxel object because each level has 8 children. Each node also has position coordinates and other variables. The voxel object is an array of unsigned char 128^3.

It must be noted that there is no drawing optimization. Both techniques simply draw every cell whether it is visible to the viewer or not. This could be optimized by raytracing or similar techniques to only draw cells that are visible from the viewing angle.

A concern is overheating the processor. When drawing the octree object with 5 levels, the cpu runs around 60 – 80% @ 1600 Mhz. However, the voxel object and the octree object both cause the cpu to run at 100% when it has 128^3 cubes/leaf nodes. The bottleneck for the voxel object is drawing the cells. The bottleneck for the octree seems to be the collision detection. The next step is testing the number of checks for a collision with the octree because this could be an area for optimization.

Spheres, Cubes and Collisions

2005-06-23T14:26:00.000+02:00

Assumption:
The drill bit is spherical. All vectors from the origin with the length of the radius will fall along the edge of the sphere.

Process:
This also works in the opposite direction. A vector SampleVector from a point outside of the sphere to the origin will cross the border of the sphere. If the radius of the sphere is subtracted from the vector SampleVector, this will return the distance from the initial position to the border of the sphere. This distance to the edge of the sphere will provide collision detection.

Using this we can calculate the distance from the center point of a cube to the edge of the sphere. The vector from the centerpoint of the cube to the centerpoint of the sphere is created. The vector is then shortened by the length of the radius. The position is checked to see if it lies within the coordinates of the cube. If it is then a collision occurs.

Note: The cube is a set dimension. It would make more sense to use a Marching Cubes type algorithm, but this should be seen as an improvement to the system. The project will remove the voxel, that is not draw the voxel, when the edge of the sphere reaches the center of the cube.

Initial Reaction to Visual and Haptic feedback

2005-06-20T14:30:00.000+02:00

The TCP position and the collision points with the voxel object and STL/TRI object do not match. The collisions occur and forces can be rendered, but it seems to be a scaling issue or an error in the matrix transformations.

Observation

The program removes voxels from the voxel shell when collisions occur. It also renders a force when a collision occurs between the cursor and the STL/TRI object.

I observed that trying to remove voxels was difficult without forcefeedback. The drilling device is attached to the haptic device and is proving difficult to maneuver. The tool is not a free moving device and is restricted. It also moves easier along certain axes.

The TCP seems easier to swing left to right along the XZ plane. This can provide stability but it often results in a path that is circular rather then linear. Moving directly in one direction is difficult.

Today I included the force feedback when a collision occurs with the voxel object. This immediately increased my ability to stay in contact with the voxel object. As stated before, the virtual tooltip was not in contact with the voxel object when collisions occured. In a sense I could only tell if a collision occured if I removed voxels. Based on that knowledge I would try to remove neighboring voxels. This was not trivial. What this suggests is that the haptic feedback maybe as important as visual feedback.

Next Step

Resolve the issue of difference between visual and haptic collision points
Move Voxel object and use Matrix math to get TCP to voxel coordinate system
Move STL/TRI object inside of Voxel object. This should be only one Transformation
Enhance viewing; angle, position, mobility
Move octree implementation from stlViewer to Prototype

SOON TESTING!

Week Update June 10, 2005

2005-06-10T12:32:00.000+02:00

Coordinates

The prototype project is able to read in coordinates of stock material and both create a new coordinate system and the transformation matrix (voxel coordinate system). It still has a problem that the voxel object is not displayed correctly after multiplying the voxel coordinate system. The voxel object seems rotated across the z-axis.

Collision detection with the voxel object requires moving the tooltip to the voxel coordinate system. This should be the multiplication of the two matrices. This will be tested next week.

Octrees

I spent an afternoon modifying the code of the octree to see if I could reduce the memory requirement when running 7 levels. The octree causes two main problems; large memory requirement and the processor runs at 100% when drawing the voxel shell.

I reduced the size of each node from 104 bytes to 80 bytes. This was accomplished by changing the type of the vectors from doubles to floats. The affect was minimal and it is unlikely to increase the performance beyond the current state. A reduction of 40 bytes would be required to provide a noticeable difference.

General Plans/Clarification

The STL/TRI file will be loaded. The system will get the bounding box of the object.
Next the coordinates from the stock material will be read in. The system will create the voxel object with these coordinates. Then, the STL/TRI object will be situated into the voxel object.

The STL/TRI file will not be scaled and it is assumed that the voxel object will fit around the STL/TRI object. The STL/TRI object can be rotated to fit into the voxel object, but the assumption is that it is possible to fit the object inside of the voxel object.

Force Rendering

Only collisions with the STL/TRI object render force feedback. The haptic device buzzes when rendering feedback. The method for rendering forces will have to be refined to reduce this. It is possible that the Omni haptic is not capable of rendering these forces to the tooltip. The extra translations might be causing the buzzing.

New Terminology

voxel coordinate system

Remaining issues

2005-06-07T15:54:00.000+02:00

Voxel object:

Read in coordinates of Stock Material to get correct orientation, size and position.
Find bounding box for STL/TRI object.
Fix Prototype cursor and voxel removal.
Detect collisions and generate forces.

The voxel object will be rotated and translated. This will affect the current method because it relies on the voxel object starting at the origin.

STL/TRI object:

Scaling of STL/TRI object to fit inside of Voxel object.
Convert TRI files into STL files. Assure that the project can read STL files.
Smooth forces, the current problem is vibration. This is a common issue and is documented in the OHTK programmers API.

Pre Demo Update

2005-06-02T18:18:00.000+02:00

Welcome to June!

Top News:

Realigning the TCP

The drilling tool has been attached to the haptic device. The greater part of today was spent realigning the TCP position. The old TCP was at the tip of the stylus pen which was only a z translation. The offset of the drilling tool and the angle of which it is attached requires a translation in all three axes.

Octrees

This week I decided to convert the voxel shell into an octree. Collision detection and simulating cell removal have not been integrated yet. It is not clear whether there is an improvement over using the old way. The memory requirement of an octree might offset the benefit of optimized drawing.

Currently 7 levels is the limit for my machine which amounts to the 128^3. The processor runs at 100% using both methods. The real test will be on the deformable shape. I plan on writing code to allow both techniques to be used.

Solutions to Previous Issues

2005-05-25T17:35:00.000+02:00

Coordinate Mapping:

The coordinate mapping seems to work now. Code from simplehapticscene was incorporated into the project prototype. This gets the dimensions of the haptic workspace and creates the openGl viewing frustrum from these dimensions.

Collisions and Forces:

Collisions with the haptic cursor and the TRI object have been tested. There are scaling issues between the actual contact points of the TRI object and the cursor. The cursor can also

Collisions occur and forces are rendered. The SWIFT package has a function to query the distance to collision. This will also return a normal vector in the direction of the collision. This is the direction to render the force.

Orientation

Prototype currently reads in 3 points from the stock material to create the final translation thanks to code provided by Professor Horsch. This is created by reading in three points, the origin, a point along the positive x-axis and a point along the positive y-axis. The program calculates the coordinate system from these points. This will have to be documented later.

This code will be extended to read in a fourth point with an added restriction. This code is meant to get the orientation. I will extend the code to allow the dimensions to be read in. the fourth point will be along the x-axis. The restriction is that all points will have to be at corners.

This means that the stock material does not have to have a specific starting position. Once the stock material is secured to the working surface, the position is read in. This can be extended to allow the workpiece to be moved after the drilling process has been started. This assumes that the origin was not removed. Repositioning the workpiece can cause accuracy issues.

Week Update May 20, 2005

2005-05-20T22:40:00.000+02:00

Unofficial News:

Last week's weekly update somehow got lost, or never written, so this is a two week update. In my opinion the project is progressing well. Later next month the drilling device should be attached and tested. The project now incorporates the collision detection package SWIFT. The system doesn't seem slow. However, the ultimate test will be loading the STL file and surrounding it with the voxel shell.

Voxel Headache:

The voxel shell is the main problem with the system. This is because its shape is dynamic. The STL or TRI objects are compiled by openGl using display lists. The objects are first loaded into a temporary storage, then stored using openGl display lists. The display list stores the shape at compile time. The program does not need to store the object after the shape is given to openGl. Drawing the shape is then only one line of code.

Another issue is finding which cells of the voxel object need to be updated after a collision occurs. If the sphere contacts only a part of a voxel, should it be removed? What other issues exist?

SWIFT News:

The package was incorporated into stlViewer first and then into Prototype. Under Prototype the collision detection algorithm did not seem to slow down the system. This needs more testing, but this is a very good sign. The step of voxelizing the STL object will be left out of the system unless a noticable system lag occurs.

Status:

SWIFT Collision detection is tested and working.
TRI files are used to load the objects.
The haptic device can move the cursor on screen.
HDAPI is used to update position, force and use collision detection

Issues:

Mapping haptic coordinates to the screen.
Test collision detection with haptic cursor and TRI object.
Surround STL/TRI object with voxel shell.
Moving voxel shell, coordinate system, calibration, other related issues.
Generate correct force vector.

Implementing SWIFT

2005-05-19T22:26:00.000+02:00

Project stlViewer was modified to incorporate the SWIFT package. The project uses SWIFT to load two spherical objects from a given TRI file. The SWIFT source code was modified to allow the vertex data to be retreived from it. The program has a TRI file reader and stores data as a mesh. A function was added to return a struct, SOLID, that contains the array of every face and each face having 3 vertices.

stlViewer loads the two sphere objects and draws them using openGl. One sphere can be moved and when a collision occurs the console prints that a collision has occured.

SWIFT will be linked with haptic thread. The haptics thread will send the rotation and translation information to the graphics thread and the SWIFT package. This is because the only moving object is the haptic device/drilling tool. The SWIFT package offers a function that returns the distance between the two objects. This will be used as a spring force.

Building SWIFT: Issues and Tips

2005-05-14T15:50:00.000+02:00

Package Details:

The SWIFT collision detection package is available from the UNC software page. The download is in the form of a ZIP file. The ZIP file contains the source code, documentation and an example project. Compiling the example project in .Net 2003 is straightforward after unpacking the ZIP file. The files are written in C++. The files swift.h and swift.lib must be included into a project to use the SWIFT collision detection package.

Rebuilding SWIFT:

The thesis project requires using a multi-threaded DLL runtime library because of the OpenHaptics Toolkit. The example SWIFT file is set to build using the single threaded runtime library. To test the SWIFT library the example project was build using the multi-threaded DLL option. To successfully build the example and the thesis project with the SWIFT library included, the SWIFT package must be rebuilt.

Rebuilding Source Code

Open Project file swift.dsw
Change Build Configuration from Debug to Release
Change Project Properties->C/C++->Code Generation->Runtime Library

Multi-threaded DLL (/MD)

Build Project

If Link errors occur see below

Including the SWIFT library into Existing Projects

Check that Project Properties

C/C++->Code Generation->Runtime Library is set to Multi-threaded DLL (/MD)
C/C++->General->Additional Include Directories add path to swift.h header file. (ex. ..\swift\include\ )
Linker->General->Additional Library Directories add path to the rebuilt swift.lib file. (ex. ...\swift\release\ )
Linker->Input->Additional Dependencies add swift.lib

Include swift.h

Possible Error Messages VC++ .Net 2003

If Link errors occur and complain about missing files it is caused by switching the runtime libraries. The missing files are a part of Visual Studio 6. If you don't have Visual Studio 6, trying searching the internet for the files or find someone with a copy of these files. Copy the Library and DLL files from a Visual Studio Directory to the windows/system32 directory or place them in the project folder.

STL files and Collision Detection

2005-05-12T14:48:00.000+02:00

Swift Custom File Formats

The UNC collision detection packages offer speed and flexibility. The file types that are used contain all the sets of vertices and faces that represent the object. The faces for this project will be triangles, although this is not a requirement. The UNC collision detection package SWIFT uses a specialized file format named TRI. All vertices are listed, then the faces are built from references these vertices.

The format for a TRI file is

TRI
nv = number of vertices
nf = number of faces
coordinates = list of the vertex position coordinates as reals.
There are 3*nv coordinates.
face indices = list of the vertex indices given in CCW orientation
for each face. There are 3*nf indices.
[1]

The main difference between STL files and TRI files are the way they represent the triangles. STL files specify coordinates for each vertex in each triangle (face). This is inefficient because in a closed object a vertex can share multiple faces. The vertex is repeated. The TRI file format, among others, lists all possible vertices first. Then, the triangle faces are created by referencing 3 vertices.

Affect

There is a file format TRIS that is similar to an STL file. Techniques on converting STL files will be researched. Currently I have found a program to convert a STL file to an .OBJ file.

For an explanation of why the project needs collision detection, see force-rendering-and-collision.html.

[1] Ehman, Stephan. SWIFT Speedy Walking via Improved Feature Testing. Application Manual. http://www.cs.unc.edu/􀀀 geom/SWIFT/

Possible Collision Detection Solutions

2005-05-10T14:50:00.000+02:00

Since the HLAPI cannot be modified it cannot be used in this project. This means that we don't get the benefit of automatic collision detection and haptics rendering provided by the HLAPI. A collision detection package must be incorporated into the project to help render forces when contact with the STL object occurs. UNC chapel hill's team gamma has an impressive page on Collision Detection, Haptics and Robotics. Professor Horsch has suggested implementing one of the two packages:

SWIFT
PQP

SWIFT claims speed, while PQP seems to be easier to implement. Both packages will be explored over the next few weeks.

Week Update May 6, 2005

2005-05-06T22:42:00.000+02:00

Project Prototype:

Voxels
The voxel object was incorporated into the project. Currently it is an example provided by Prof. Horsch. The code will be modified to create the cuboid voxel shell. The voxel object will have to surround the STL object.

Forces and Collision
When a collision occurs a force will be sent to the haptic device. The focus of the next few weeks will be resetting and adjusting forces.

Project stlViewer:

Voxel object was modified. Each voxel is now drawn as a 3D coordinate using 3 lines rather than 6 planes.

Progress

A drilling tool was provided by Prof. Dr. Horsch. Next week I will enlist the help of the Darmstadt machining lab to attach the tool to the haptic device

Outlook

By June 3 demo

Align voxel object and STL Import voxel object using haptic device.
Feedback to simulate a collision and resist penetration.

Next phase

Drilling tool should be attached.
Experiment drilling with simple shapes
Collision Detection with STL object

Thread Safety .. or Ignoring Thread Safety

2005-05-06T21:01:00.000+02:00

Problem:
The voxel object needs to be drawn by the graphics thread and updated by the haptics thread. The Haptics Programmers PDF suggests creating a snapshot for shared data because the haptics thread runs considerably faster and can change the data while the graphics thread is attempting to draw the object. Creating a snapshot would mean that at the worst case a 3D array 128^3 would have to be copied 60 times per second.

Partial Solutions and Assumptions:
The graphics thread is a read-only thread while the haptics thread is a write-only thread. The collision detection exists in the haptic thread so the data needs to be correct. The proposed solution is to overlook the possibility of inconsistant data for the graphic thread and have one object shared between the two threads. It is unknown if there will be a noticable display lag in the graphics thread. This issue will be tracked throughout the course of the project.

Terms and Definitions

2005-05-04T11:34:00.000+02:00

Callback -- Function that is set to run on the scheduler. These can set responses to user events or query device state. They can be Asynchronous or Synchronous. callbacks-and-scheduler-from-hdapi
Graphics Thread -- see Scheduler
Haptic Device -- Phantom Omni 6 DOF device. Can render force feedback in 3 dimensions. sensable-omni-phantom
Haptic Thread -- see Scheduler
HDAPI --Haptic Device API. This allows low a level interface with the haptic device. see hdapi-vs-hlapi
HLAPI -- Haptic Library API. This builds on top of the HDAPI and allows collision detection based on openGL methods. see hdapi-vs-hlapi
Octree -- Storage technique for representing 3D objects. This is an extension from quadtrees. A cube is divided into 8 equal sized cubes. There are multiple levels each level having 8 children. This storage technique is meant to enhance performace by reducing cells to check. Eg. An array would check each item in the array. An octree is meant to quickly dismiss branches that are unnecessary.
OpenGl -- A graphics programming API allowing 2 and 3 dimensional manipulation. multi-language multi-platform
Scheduler -- This is an infinite loop that responds to events based on callbacks. Events can be from user devices or based on idle time. The scheduler will execute at a set frequency. openGl and the HDAPI use seperate schedulers. OpenGl is around 60 Hz while the Haptic scheduler is at 1000 Hz. callbacks-and-scheduler-from-hdapi
STL file -- STereoLithography. A triangle mesh that forms a shell of a solid object. All faces are listed. Each face has a normal vector and then 3 vectors with 3 coordinates each. see stl-files-and-collision-detection
STL Object -- This represents the desired shape in the virtual environment consisting of openGL triangles. The triangle data is loaded from an STL file. Forces should be rendered to prevent the tool tip to penetrate this shape.
Stock Material -- Real world drilling material. This will be simulated by the Voxel Object
SWIFT -- University of North Carolina's collision detection package. SWIFT
TCP -- Tool Center Point. This is the endpoint of the kinematic chain representing the tooltip of the Haptic device.
TRI file -- a file consisting of faces and vertex points that represent a triangle mesh that forms a shell of a solid object. First all unique vertice positions are listed. Then all triangles are formed by referencing 3 listed vertice positions. see stl-files-and-collision-detection
Voxel -- Volume Pixel, used to represent 3D objects. see voxels-what-to-know
Voxel Object -- The 3D array that surrounds the STL Object and simulates the Stock Material. Each cell has a value associated with it 0 is Empty, 1 is Inner, and 2 is the Body. Cells marked Body are the only cells drawn. The Voxel object starts as a cuboid shell.
Voxel Shell -- All cells of the Voxel Object that have value Body. This simulates the current progress and should mirror the actual milling material.

Programs:

stlViewer: Initial project. First was used to load and display STL objects from a file. Then haptics were added. Voxels were added next. Collision detection and force rendering were explored using this project. This project relies on the HLAPI. This project was converted into prototype. Recently this was extended to use the SWIFT collision detection package.

prototype: working Project. This is the conversion of the project stlViewer to use the HDAPI. This will have custom force rendering and the SWIFT collision detection.

Force Assumptions and Method

2005-05-03T12:03:00.000+02:00

The haptic device can only render forces in 3 dimensions. The tooltip has no torque feedback so for this project the milling must be perpendicular to the real world material (voxel object). When the tool center point (TCP) enters the voxel object then force rendering starts.

First the force axis and force direction are computed from the initial contact point

Force axis -- The x, y or z plane that the force will be rendered in
force direction -- The direction in the plane to render the force. initial point - current point

While the TCP lies within the voxel object the force axis and force direction will remain the same. The user must exit the voxel object to reset the force axis.

Proper use of the milling--

Tool is held perpendicular to the voxel object at all times
Milling at an angle will cause unexpected results and is unsafe!
The tool should be exited from the voxel shell when changing the milling axis

Force Rendering and HLAPI News

2005-05-03T00:34:00.000+02:00

Professor Horsch and I sent an email to the support department at SensAble to check if the HLAPI (Haptic Library API) could be modified to move the tool center point. I was informed by Prof. Horsch that currently the HLAPI cannot be modified. The next release of the development kit is set for July/August and this feature may be included.

The project will use the HDAPI (Haptic Device API) and all forces will be rendered manually. There will be different forces.

A lock position -- This could be used to 'hang' the tool. Force would be applied to prevent the tool from moving. This point would be away from the material
Constant friction -- this might assist the overall experience. **will explain if included**
Voxel Contact -- The force cannot be too great, but the user must feel contact with the voxel shell. The voxel shell is deformable. Force Rendered in opposite direction of mill direction
STL Voxel Shell -- **If included** Provide stronger feedback, yet not highest level
STL object -- Highest resisting force

The initial point of contact with the voxel shell can be tracked. While still in contact with voxels, the force is rendered in the vector from current position to initial point of contact.

Assumption

Voxel object has collapsing outer shell. In the end all voxels in the voxel object should lie inside of the STL Object.

STL Voxels **if included** are not drawn

New Issue

Collision Detection for STL object - Cylinder to set of static triangle planes

Week Update April 29, 2005

2005-05-01T13:21:00.000+02:00

Current Work:

Prototype project was created. This is the combination of stlViewer, cubeTest, slidingContact and various parts from other haptics example projects. The Prototype project is the conversion of stlViewer to use the HDAPI

Currently the project inputs an STL file. It has simple lighting and graphics. The viewing angle is controlled by the keyboard, but rotations aren't included. The haptic interface is setup, but forces are not yet rendered. The outline for the Prototype project follows the example project slidingContact.

New Issues/Questions:

Collision Detection between cursor (cylinder) and STL object (triangle planes)
Attaching drilling tool to haptic device
Fitting STL object into an imported Voxel Shell

Scaling
Orientation

Method for computing Forces

How? -- hdSet (...) --
What are the max forces?
How the forces change between contact with objects

Timeline Update -- Phase 1

2005-04-25T14:04:00.000+02:00

Phase 1 is now complete!

This phase was to determine whether the project was possible. It explored different graphics components based on openGL. It also focused on current trends in research related to haptics and visual representation. The scope and major hurdles for the project were determined. The project will proceed.

Issues Encountered:

Issues encountered have either been resolved or a work around exists. One issue was the discovery of the limit of the haptic device. The force feedback is only in 3 dimensions. A fully functional system must incorporate at least 5 degrees of freedom feedback. To overcome this issue, all drilling be done perpendicular to the drilling plane.

Another issue was moving the tool center point (TCP) of the haptic device. As stated in other posts, the TCP must be at the drilling endpoint. Using the HDAPI the TCP can be moved and have forces generated based on the new position. The remaining issue is that the HLAPI cannot be used without modifying its source code. Using the HDAPI requires custom collision detection and force rendering.

Accomplishments:

An openGL graphic environment was created. An ASCII STL file can be loaded. Force feedback can be generated using the STL file. A voxel shell can be loaded into the environment and the haptic device can simulate removing pieces. Camera angles can be moved.

Known Issues:

Haptic to viewing transformation/mapping
Must implement custom force/collision detection -- HLAPI cannot be used
How to attach drilling device to haptic device.
Drawing 100,000 Voxels is upper limit of machine

Skills and Knowledge Acquired:

programming with openGL
What voxels are and their costs and benefits
how to incorporate API's into existing code
what callbacks are and how they interact with a scheduler
Interact with developers using Sensable Developers Forum

Week Update April 22, 2005

2005-04-25T14:01:00.000+02:00

Resolved Issues:

StlViewer was modified to allow the haptic cursor to interact with the voxel shell. The problem was matching the coordinate systems. The voxel shell was drawn incorrectly. When the original voxelization pyramid was used, the cursor interacted with voxel object.

Remaining Issues:

Must migrate to HDAPI
Determining the correct scale of the voxel shell around the STL object.

Questions:

How to resolve system lag, mainly openGL optimizations can Oct trees be used?
Should STL object be voxelized for 3 layer collision detection?
Collision Detection -- Voxel based, Cylinder to Plane
How to attach drilling device to haptic device?

Answered Questions:

Workspace to graphics mapping. See Post for Workspace Mapping
Would there be a benefit from using VTK. See Post VTK

Force Rendering and Collision Detection -- Plan

2005-04-22T11:36:00.000+02:00

The HDAPI allows the HD_CURRENT_FORCE variable to be set. This provides the developer with control of custom force rendering. The SlidingContact example creates a force field around two sphere objects. Collision detection is used to update the force on the cursor object and then sent to the haptic device.

Our prototype system will take advantage of custom force control and collision detection. The collision detection will be divided into either 2 or 3 stages.

The first stage is a collision between the cursor and the voxel shell.
The second stage would involve voxelizing the STL object. This stage is meant to reduce the number of collision checks by creating a rough outer shell of the STL object. This stage is only needed if the collision detection between the STL file and the cursor proves to be too expensive.
The last stage is to do collision detection between the cursor (tooltip) and the STL object. This is an expensive operation because STL files are normally not optimized. A sample STL file rendered had 1600 facets. Various collision detection algorithms will be explored for this issue.

Voxels are used in this program to represent 3D shapes as well as provide quick collision detection. A collision between the cursor and the voxel object can be detected by checking the coordinates of the cursor. If it lies within the voxel coordinates a collision has occured. The voxels that are within the cursor coordinates can be checked whether they are part of the body or are free.

An important assumption is that the STL object will lie within the voxel object. Collision detection between the cursor and the STL object only needs to be done when the cursor lies within the voxel space. The STL object is static and a voxel representation can be created but only to reduce the number of collision checks. The voxel object will have a changing shape and the goal is to represent the STL object as voxels.

Haptic Device to Graphic Mapping

2005-04-21T15:01:00.000+02:00

For the past few weeks, I have been struggling to convert the haptic work coordinates to the graphic coordinates. I have been modifying code given in the haptic examples. The simpleHapticScene example provides code to generate the cursor on the screen.

The problem was having the coordinate system of the haptic cursor interact with the voxel shell. The cursor could be drawn to the screen, but when the cursor should have crossed into the voxel shell nothing happened.

Project stlViewer took code from a voxelization project. This took a geometric pyramid and created a voxel shape from this. Dr. Horsch modified this to distinguish the outer shell and the inner body, where the outer shell voxels are drawn. Our project will only require a voxel shell without the need for the voxelization step. I modified the code to create a cube that was 127^3 with only the outer shell drawn.

The next step was allowing the keyboard to move the cursor in the virtual environment and remove voxels when a collision occured. I modified the code provided by Dr. Horsch to activate the invisible voxels surrounding the one that was removed. When a collision occured with a voxel, its neighbors that were not drawn before had there type changed to be on the border.

The haptic toolkit provides a way to get the final transformation. There are two levels, the HL and the HD. The HL provides a proxy transformation that is the calculated with an extra translation. The HD provides the exact transformation; that is, it provides the machine values.

Today I found out that I was multiplying by the wrong transformations. The code provided by simplehapticscene to draw the haptic cursor uses a mapping technique to draw the cursor. I have struggled to get this to work, so instead I took the HD_CURRENT_TRANSFORM and generated the cursor at that position.

Callbacks and the Scheduler -- From a HDAPI viewpoint

2005-04-19T14:42:00.000+02:00

The Scheduler is the thread controlling the haptic device. This is the main interface and runs at 1000Hz. Queries such as position or state must be accessed by calls to the scheduler. The scheduler allows get and set operations to many hardware variables, i.e. position or force.

The HD requires creating CallBacks to be run on the scheduler. Some Events are predefined, but the custom functions can also be passed to the scheduler. The CallBacks can be sent to run every frame, scheduled by the programmer, or triggered by predefined events.

Asynchronous -- "return immediately after being scheduled" represent haptic effects
Synchronous -- "only return after they are completed, ...application thread waits for a synchronous call before continuing." Use to get snapshot of state/variables

[1] OpenHaptics Toolkit - Programmer's Guide 5-5 37/118

CallBacks have two return types.

HD_CALLBACK_CONTINUE -- The CallBack will be rescheduled to run on next tick
HD_CALLBACK_DONE -- Will not be rescheduled

Examples

hdScheduleSynchronous(DeviceStateCallback, &state, HD_MIN_SCHEDULER_PRIORITY);
hdScheduleAsynchronous(AForceSettingCallback, (void*)0, HD_DEFAULT_SCHEDULER_PRIORITY);

HLAPI -- Forces and Collision Detection

2005-04-19T11:29:00.000+02:00

The section called HDAPI vs. HLAPI mentioned that the HL used openGl to render haptic feedback. The HL commands to capture the shapes are wrapped around existing openGL code.

Depth Buffer -- The HL reads the openGl depth buffer to calculate the geometry and render forces. "The depth buffer is used for hidden surface removal." [1]

Depth buffer shapes are less accurate than feedback buffer shapes although in nearly all
applications, the difference in accuracy is undetectable. [2]

Feedback Buffer -- "Capture geometric primitieves" Commands that generate points, lines and polygons. [1]

If you are rendering lines and points to be used as constraints, you must use a feedbackbuffer shape since depth buffer shapes cannot capture points and lines.[2]

[1] The OpenHaptics™ Toolkit: A Library for Adding 3D Touch™ Navigation and Haptics to Graphics Applications
Brandon Itkowitz* Josh Handley† Weihang Zhu
[2] OHTK Programmer's Guide 7-12 page 62/118

2005-04-16T23:24:00.000+02:00

SensAble Omni Phantom

Visualization ToolKit (VTK) -- To integrate or not to integrate

2005-04-16T22:23:00.000+02:00

"The Visualization ToolKit (VTK) is an open source, freely available software system for 3D computer graphics, image processing, and visualization..."
VTK Home Page http://www.vtk.org/ 16 April 2005

The initial phase of the project was to determine whether to design a system bottom up or to modify an existing engine. The VTK provides many features, automatic lighting, an STL file reader, and a marching cubes implementation. Using the VTK marching cubes implementation would decrease design time but is not crutial to the system. I have implemented an ASCII STL reader.

The control of openGL is hidden from the programmer and this is the main downside of using this system. Integrating the controls of the haptic device would be required and it is unknown if it is possible or . Another issue is the workspace to graphics mapping. Since the openGL calls are hidden, it is unclear whether the model transformation matrix is accessible.

At this point in time, the risks of switching to the VTK outweigh the benefits.

HDAPI vs. HLAPI

2005-04-16T20:45:00.000+02:00

The HDAPI provides low-level access to the haptic device, enables haptics programmers to render forces directly, offers control over configuring the runtime behavior of the drivers, and provides convenient utility features and debugging aids.

The HLAPI provides high-level haptic rendering and is designed to be familiar to OpenGL® API programmers. It allows significant reuse of existing OpenGL code and greatly simplifies synchronization of the haptics and graphics threads. The PHANTOM Device Drivers support all shipping PHANTOM devices.

3D TOUCH™ SDK OPENHAPTICS™ TOOLKIT PROGRAMMER’S GUIDE
2004 SensAble Technologies

Voxels -- What to Know

2005-04-16T20:39:00.000+02:00

Definition:

The term voxel is short for volume pixel. Pixels represent only two dimensions. Voxels allow objects to be represented in 3 dimensions. Voxels are used to represent volume data, such as CAT scans and MRIs.

In Use:

A 3 dimension array will represent the voxels. The array type will be an unsigned char, where a zero is outside of the object, a one would represent the outer shell of the object, a two would represent the undrawn inside of the object.
The memory size will increase with resolution (ex. 128 cells in each x, y and z coordinates as an unsigned char)
Voxelization is the process of converting a set of geometric shapes into a voxel representation. A problem is finding a ratio of memory size to resolution. One technique for voxelization is presented by
E. Karabassi, G. Papaioannou, T. Theoharis, "A Fast Depth Buffer Based Voxelization Algorithm,
Journal of Graphics Tools", ACM, 4(4), pp.5-10, 1999.

Project Specific Assumptions:

The real world material will be represented by a voxel shell. The material will be cuboid, not required to be cubic. The original object does not require voxelization, because of its shape. The STL object could be voxelized to enhance collision detection.

if tooltip is within voxel coordinates
check for collision with voxel outer shell
check for collision with STL voxel shell
use other collision detection to check for contact with STL
object

Voxels are used because of quick collision detection. The position of where an object collides with the voxel shell can be checked easily. X, Y and Z coordinates with the offsets figured in will determine which cells need to be checked. If any cells have a value of one, being part of the outer shell, then a collision has occured.

Week update April 15, 2005

2005-04-16T12:31:00.000+02:00

Current Issues:

Mapping the Cursor/haptic device Workspace to Screen coordinates.
Including tooltip transformation: Current Projects rely on Haptic Library to Render forces. The translation for the tooltip requires the projects moving away from the Haptic Library(HL) API and using the Haptic Device(HD) API. The HL is a high level library that automates most processes, including capturing and rendering forces. The HD requires callbacks to be written to simulate forces and provide collision detection.
Collision Detection techniques
Migrate working systems to HD
Calculate and Generate custom forces

Current State of System: Projects

stlViewer

The haptic tooltip can be drawn on the screen
Loads STL object
Loads a voxel shell, the shell is updated when contact occurs with cursor
Allows cursor control with keyboard or haptic interface
With keyboard control, voxel shell can be deformed

Issues:

Relies on HL to capture shapes from OpenGL calls
Must migrate to HD
Does not include tooltip transformation
haptic cursor does not interact with voxel shell correctly

Various Toolkit Examples:

Slidingcontact has been modified to demonstrate the possibility of adding the translation using HD.
cubeTest loads a STL file and allows haptic feedback. The forces are rendered by the openGL viewing matrix. If the viewing matrix shows the virtual model at an angle, then the forces will correspond to the viewing shape not the actual shape. This project uses HL and has a mapping of the workspace to visual display.

Questions:

How to map workspace
Collision Detection -- Voxel based, Cylinder to Plane
How to resolve system lag, mainly openGL optimizations can Oct trees be used
Should STL object be voxelized for 3 layer collision detection
Would there be a benefit from using VTK