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.
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.
posted by Tosowski at 6/27/2005 01:51:00 PM
0 Comments:
Post a Comment
<< Home