Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / 3D Theory & Graphics / 3DDDA (3D Digital Differential Analyzer) Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
Jay Webb

August 16, 1999, 03:42 PM

Hi, I'm new to 3d graphics. I'm learning about octree generation and
how to obtain the cubelets in an octree divided worldspace that a line passes through.

The ideal method is to detect which cubelets a line passes through
using 3DDDA. I cant find any information or at least a pseudo algorithm
on how to do 3DDDA. Can anyone help me with this?

 
Raven

August 17, 1999, 11:56 AM

>>The ideal method is to detect which cubelets a line passes through
>>using 3DDDA. I cant find any information or at least a pseudo algorithm
>>on how to do 3DDDA. Can anyone help me with this?
Elaborate a little on 3DDDA. I haven't heard of this, maybe its known by a different name. That would explain why you can't find anything. What do you mean by Differential Digital Analysis?
Another thing is that its rarely needed to find the octree-nodes(cubelets) through which a line passes. The whole point of an octree is to go the other way around, to find the node you need quickly and extract the actual geometry from it. Unless you are using octree-encoding as your ONLY method of storing 3D data(no polygons). This is theoretically possible but very memory-intensive and very slow to process or animate. In practice it makes so many difficulties its unusable.

- Raven

 
Miklos Erdelyi

August 20, 1999, 07:21 PM

Raven wrote:
>>>>The ideal method is to detect which cubelets a line passes through
>>>>using 3DDDA. I cant find any information or at least a pseudo algorithm
>>>>on how to do 3DDDA. Can anyone help me with this?
I don't know what is 3DDA but well I don't care. Use Woo's algorithm to find which AABB of the node does a line (ray) intersect. The idea is very simple: reject those planes of the AABB which are back facing to the ray origin, and then calculate the 't' intersection points with the frontfacing planes and the ray. The biggest 't' will be the leftmost and that will ne a potential hit. Check whether the intersection point lies on the face of that side of the AABB. Done.
This is quite useful, for example if you want to do point-to-point visibility test w/ your octree.
[AABB = axis-aligned bounding box :-]

 
Andrew H. Cox

August 23, 1999, 08:59 PM

Jay Webb wrote:
>>Hi, I'm new to 3d graphics. I'm learning about octree generation and
>>how to obtain the cubelets in an octree divided worldspace that a line passes through.
>>
>>The ideal method is to detect which cubelets a line passes through
>>using 3DDDA. I cant find any information or at least a pseudo algorithm
>>on how to do 3DDDA. Can anyone help me with this?

G.Gems IV

There is a C routine in the online code (at www.acm.org) for a uniform grid 3D line routine that uses error variables + branches per step Bresenham style.

A guy asked about this on comp.graphics.algorithms a couple of months ago and then posted his own solution a day later.

Regards,

Andrew H. Cox

 
This thread contains 4 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.