Week Update 24, 2005

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

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

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

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

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

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.