Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.4k views
in Technique[技术] by (71.8m points)

math - How do I initialize the t-variables in "A Fast Voxel Traversal Algorithm for Ray Tracing"?

I am trying to implement the algorithm explained on this paper, used to traverse grid cells in order following a straight line, which is useful for ray tracing:

http://www.cse.yorku.ca/~amana/research/grid.pdf

The paper describes the algorithm as two parts: initialisation and iterative traversal. I can undersand the iterative traversal part, but I'm having trouble understanding how some of the variables in the initialisation part are calculated.

I need help initialising tMaxX, tMaxY, tDeltaX & tDeltaY. Their initialisation procedure is explained as follows:

Next, we determine the value of t at which the ray crosses the ?rst vertical voxel boundary and store it in variable tMaxX. We perform a similar computation in y and store the result in tMaxY. The minimum of these two values will indicate how much we can travel along the ray and still remain in the current voxel.

Finally, we compute tDeltaX and tDeltaY. TDeltaX indicates how far along the ray we must move (in units of t) for the horizontal component of such a movement to equal the width of a voxel. Similarly, store in tDeltaY the amount of movement along the ray which has a vertical component equal to the height of a voxel.

I'm not able to deduce the code I need form the English description given above. Can someone translate it to a math/pseudocode expression for me?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

Initialization for X-coordinate variables (the same for Y)

  DX = X2 - X1
  tDeltaX = GridCellWidth / DX
  tMaxX = tDeltaX * (1.0 - Frac(X1 / GridCellWidth)) 
  //Frac if fractional part of float, for example, Frac(1.3) = 0.3, Frac(-1.7)=0.3

Example:

  GridCellWidth, Height = 20
  X1 = 5, X2 = 105 
  Y1 = 5, Y2 = 55 
  DX = 100, DY  = 50
  tDeltaX = 0.2, tDeltaY = 0.4 
  tMaxX = 0.2 * (1.0 - 0.25) = 0.15  //ray will meet first vertical line at this param
  tMaxY = 0.4 * (1.0 - 0.25) = 0.3   //ray will meet first horizontal line at this param

We can see that first cell border will be met at parameter t = 0.15


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...