Archived

This topic is now archived and is closed to further replies.

LinaInverse2010

Divisor question

Recommended Posts

Lina*,

This doesn''t sound like a game development question. It could easily be math homework. The forum has a specific policy on homework, and homework-like questions, which you should review here:

Forum FAQ

Remember, although some theoretical and interesting math/physics discussions are appropriate for the forum, you should at least contribute your own approach to the solution before asking for the answer. And for homework, you should never ask for the answer, only for hints or suggestions that can help you solve the problem yourself!

That said, here is a clue. You cannot solve for both t and z with just one equation. If there are two unknowns, you must have two equations. Otherwise, one of the unknowns will remain unknown.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Actually you CAN solve in two unknowns with one equation.
To do this, you must study diophantine equations.

The given equation, however, has no general solution and is not even diophantine and therefore cannot be homework.
In general factorization is only possible in the numerator(!)

Share this post


Link to post
Share on other sites
Actually it is a problem related to triangle intersection.

I'm tracing coherent rays in packets of 4x4. So the upper left ray is lets say UL then I previously computed the size of each pixel in the current view space which are defined by du and dv

so the initial ray direction is RD(0,0) = UL - EYE. So any pixel (i,j) is in the direction on RD(i,j) = UL - EYE + i*du + j*dv .

Now intersecting with a triangle, the time is:
t(0,0) = (n % ao) / (n % RD)

so the next pixel:
t(0, 1) = (n % ao) / ( (n % RD) + (n % dv) )

so I want : t(0,i) = (n % ao) * (P / (n % RD) + Q * i / (n % dv))

so I just need the P and Q values. I don't know if this is possible, but I remeber in middle school doing something like this, but I can't remember what we did.

LinaInverse

Just for refernece % = dot product for a vector.
And * is a scalar multiplication

[edited by - LinaInverse2010 on October 8, 2003 2:49:20 PM]

[edited by - LinaInverse2010 on October 8, 2003 2:49:44 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
From all you''ve posted, I was able to figure out that these are pluecker coords, right?
How do you get t(0,0) and t(0,1)? Why factorize in like that when you can just search for a linear combination in the denominator??
My guess after 5 mins of ray-tracing is that you could probably get some recurence relation for p and q but that''s just a guess

btw the web seems to be full of super-heavily optimized line-trianlge intersect algorithms, so why not settle for an existing solution? FPGA''s don''t seem THAT demanding... (said after 0 mins of fpga''s

Share this post


Link to post
Share on other sites
Well, the problem is a division on an FPGA takes up a lot of space, even with just 16-bit fixed point numbers its going to take about 20-30% of my chip up. Also the delay on it is around 120 ns, which would cost me about 3-4 cycles more per triangle intersection. If I could just use a multiply/add or two, I''d be much better off.

Right now on the $800 boards where using for this project ( http://www.xess.com/prod014_3.php3 ) have "300K Gates", which by the way is a very bad indicator of how much they hold. Just for your reference a single cycle implementation of the "Fast, Minimum Storage Ray-Triangle Intersection", availible at http://www.acm.org/jgt/papers/MollerTrumbore97/ , takes up more space than these chips have using 16-bit fixed point numbers, with the division about 150% of the chip would be used. Right now I got a single cycle setup per triangle, and a double cycle intersect per ray on that triangle design that takes up about 70% of the chip (I have 9 16-bit multipliers and 22 Adder/Subtractors).

So I''m really trying to optimize everything, and I''d like to use the division component for other calculations on the chip when it isn''t being used by the triangle intersector.

LinaInverse

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
Actually you CAN solve in two unknowns with one equation.
To do this, you must study diophantine equations.


AHH. That'd teach me to assume the solution must be from a continuous domain rather than a discrete set!



Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

[edited by - grhodes_at_work on October 8, 2003 9:18:08 PM]

Share this post


Link to post
Share on other sites