new fast ray tracing algorithm

[krio]

If You are interested in using this algorithm, with purposes please contact me

via this e-mail: sinnlabs@list.ru

Full documentation is here.

I am not hosting it anywhere because mirrors could easily be brought down by someone not willing this to pass to the public.

It also can't fit in the attachments.

 

Tracing the rays for fun and profit:

The ways of spherical ray tracing

by

(--Sinn-Labs--)

 

 

 

-----------------------------------------------------------------------------------------------------------------------------------------------

Intro:

-----------------------------------------------------------------------------------------------------------------------------------------------

Authors:

Alex "krio" V. Kossiakov, student of Moscow State University, Faculty of Computational Mathematics and Cybernetics

-----------------------------------------------------------------------------------------------------------------------------------------------

Copyrights:

© Alex V. Kossiakov, all rights reserved. If you read this document, then everything is copyrighted and protected by law. You may freely distribute this document only without any modifications. The original document in russian which was copyrighted MUST be distributed within this document, attached after the "[EOF]" marker. The attached document contains main concept of the algorithm so you can't use it or it's minor parts in commercial ways without my permission.

-----------------------------------------------------------------------------------------------------------------------------------------------

About Sinn Labs:

Born in depth of Moscow school 1134, migrated to Moscow State University. With this document we are hoping to get some money resources for our next topic (which might blow you away). That's why we had to copyright this "technology".

-----------------------------------------------------------------------------------------------------------------------------------------------

About the topic:

Ray tracing was a very expensive technology in computer graphics scene. In fact everybody thought it is not matching with traditional graphics pipeline. But it all was in past. And this document should explain why.

-----------------------------------------------------------------------------------------------------------------------------------------------

Special thanks:

Kevin R. Harris for his opengl samples (http://www.codesampler.com)

-----------------------------------------------------------------------------------------------------------------------------------------------

 

Lets go!

 

The spherical coordinates is a representation of 3d out of 3 parameters: two angles - alpha, beta and the distance r to the point. Well, nothing really new, because we all remember how to generate a sphere:

x = r * cos(b) * cos(a)

y = r * cos(b) * sin(a)

z = r * sin(b)

 

 

What if we will take alpha and beta to be equal our x*psi and y*phi on the screen??

Yes! lines will still be lines, so triangles will still be triangles!!

What does this mean? This means that we can forget about the distances for a while. Looks like a spherical projection. And we are just taking the part of that sphere as an our screen and the eye's location in the 0. Notice that we'll get a prospectively-correct image. But. For each frame we'll have to calculate millions of arctangents to know what alpha and what beta each vertex has. No problem. Let’s just use the standard algorithm to get a prospectively-nice image - instead of arctangents we'll just divide x and y by r (let’s call it ortho projection).

 

Well, ok. But lets look how a plane looks like in spherical coordinates:

Ax + By + Cz + D = 0

means

r * (A * cos(b) * cos(a) + B * cos(b) * sin(a) + C * sin(b)) + D = 0

r * k + D = 0

r = - D/k

 

Good, but we must calculate lots of sin and cos, that will take a lot of time... If alpha and beta depend on screen's x and y, then we can just precalculate them and put in an array of lets say 640x480x3 elements: cos(b)*cos(a) ; cos(b)*sin(a) ; sin(b). And how should we calculate A,B,C and D? We have lets say all three vertexes of triangle M1(x1,y1,z1), M2(x2,y2,z2), M3(x3,y3,z3):

A = y1 (z2 - z3) + y2 (z3 - z1) + y3(z1 - z2) B = z1 (x2 - x3) + z2 (x3 - x1) + z3(x1 - x2)

C = x1 (y2 - y3) + x2 (y3 - y1) + x3(y1 - y2) - D = x1(y2 z3 - y3 z2) + x2 (y3 z1 - y1 z3) + x3 (y1 z2 - y2 z1)

 

Looks like we can calculate the distance from an eye to any pixel on any triangle fast enough. Now, how do we use this all? How do we draw our scene?

Well, personally I was shocked when realized that classical ray tracing is brute forcing all the pixels on the screen and at every pixel we search for triangles which we intersect with that ray and then looking which triangle is first on the distance. What else can we do instead this brute force?? Lets try it that way:

 

Per frame before rendering: for each triangle to calculate all the needed above data AND where actually that triangle should be rendered on the screen: for each y that is in the bounding box of that triangle we precalculate xmin and xmax where the y is intersecting our triangle. Just a basic rasterization!!

When rendering: for each triangle; for y that is in bounding box; for x that is from xmin to xmax DO: check if that pixel is in the screen; check if in the depth buffer for that x and y the ID of the triangle is the ID of our triangle, if so - we have intersection and can do our per pixel calculations.

 

That is all for primary rays.. What's up with the secondary? We can do just exactly the same, but at first we only have to recalculate the spherical coordinates with a zero at the point where the second ray comes from. Oh, and normals are calculated with ortho projecting {A,B,C} vector. And reflection angle is just simple linear combination of the primary ray's angle and normal's angle. Just realize a line coming through this two 2d angles - what we need is a third point on that line which is as far away from the normal's as ray's from the normal's and is located in one of two ways:

ray's - normal's - reflection's angles; or: reflection's - normal's - ray's angles. Refraction is calculated some similar way. Just draw a 2d projection of angles into dots on a paper and see it by your self.

 

What’s up with spheres? Nothing really. Only the fact that we should calculate the r in a such way: -r^2 = alpha^2 + betta^2 - sphere_radius^2. Normals should be represented in angles and calculated with ortho projection, gladly we can convert our spherical coordinates to standard ones in a few multiplies. Reflections and refracts are calculated in similar to triangles way from this point.

 

How to code it on gpu? There are actually number of ways. I'm not sure yet which one is the best.

And now just realize how fast it will work if Nvidia/Ati will use it directly in the rasterization process to pass the data (pixel's distance or 3d location) to pixel shaders... But before it happens you may try to pass that data in a texture or three, depending on what depth quality you are aiming at. There are lots of other things for them to think about, and it's their job.

 

This stuff works really faster than the traditional ray tracing. I did do a lot of test-coding, got amazing results, but we are not distributing inner sources just because I’m not the best coder around and I had a very tight time limit.

 

------------------------------------------------------------------------------------------------------------------------------------------------

Outro:

Everything what is imaginable IS possible.

------------------------------------------------------------------------------------------------------------------------------------------------

[EOF]

[ATTACHED ORIGINAL COPYRIGHTED DOCUMENT]

Сферический ray-tracing.

 

Стандартный алгоритм ray-tracing, или метод трассировки лучей, был предложен Артуром Аппелем (Arthur Appel) еще в 1968 году и дополнен алгоритмом общей рекурсии, разработанным Whitted в 1980 году.

В основном он сводится к необходимости для каждого пикселя на экране в декартовой системе координат провести луч и искать пересечения с плоскостями треугольников, затем для каждого пересечения смотреть, попадает ли луч в треугольник. Первое попадание по лучу, заданного параметрически, и есть тот пиксель, цвет которого дальше надо считать.

Прочие вариации этого алгоритма аналогично сложны по вычислениям.

 

Используемые так же, пиксельные Shader'ы достаточно быстры и все последние видеокарты приспособлены именно под них. Но невозможно осуществить нормальный доступ из шейдера к прочей геометрии сцены. Для стандартных треугольников метод применим, но не для непрямолинейной геометрии - сфер и т.п.

Визуальное качество применения пиксельных шейдеров не может сравниться даже с традиционным ray-tracing'ом.

 

 

Суть предлагаемого сферического ray-tracing'a:

Для каждого примитива считаются нужные сферические координаты раз в кадр. Что можно делать как стандартным способом перспективного преобразования для обычных декартовых систем координат, так и через формулы преобразования декартовых координат в сферические. Во втором случае мы получим перспективно-правильную проекцию.

В итоге мы получаем линейную зависимость угловых составляющих сферических координат на плоскости от координат на нашем экране. Здесь не приводится доказательств того, что при такой аналогии сохраняются все возможные свойства, потому что способов доказательства очень много, это не входит в рамки данного текста и, к тому же, это проверено экспериментально.

Затем осуществляется стандартная растеризация, например scan-line алгоритм, но в угловой составляющей сферических координат. После этого мы можем перебрать в цикле каждый примитив и трассировать только лучи, попадающие в эти примитивы: перебираем каждую строчку от минимальной до максимальной, а в каждой строчке перебираем от просчитанного ранее минимального столбца до максимального.

Для каждого такого попадания просчитывается дистанция и сравнивается с буфером глубины.

После этого попадание считается действительным и происходит расчет текстурных координат, вторичных и прочих лучей и других свойств, для вычисления цвета этого пикселя.

Таким образом, мы почти полностью избавляемся от присущего ray-tracing'у метода грубой силы, сохраняя все его возможности, и внося еще множество разных оптимизаций.

 

Основные отличия нового алгоритма, которые могут применяться по отдельности в реализации ray-tracing'a:

1. использование сферических координат для трассировки первичного луча.

2. использование сферических координат для трассировки вторичных лучей и всех остальных лучей.

3. предварительный просчет принадлежности пикселей рабочей плоскости к примитивам (предварительная растеризация) через переход на рабочую плоскость, либо из сферических координат либо из декартовых.

4. использование предварительной растеризации для по-примитивной трассировки.

5. просчитывание углов лучей отражения и преломления линейной комбинацией двумерных углов предыдущего луча и нормали.

6. предварительная растеризация примитивов в координатах вторичных и прочих лучей для их трассировки.

Многие эти особенности могут быть реализованы, или уже реализованы в других, не ray-tracing`овых, методах отображения. Например можно использовать сферические координаты в реализации стандартных shader`ов.

 

Основные отличия нового алгоритма позволяют:

1. не высчитывать лучи параметрически.

2. использовать угловые составляющие сферических координат как координаты пикселя на экране.

3. в следствии применять к ray-tracing стандартные алгоритмы растеризации и буферизации.

4. в следствии трассировать не каждый пиксель на экране, а лишь пиксели, попадающие в треугольник или другой приметив.

5. в итоге - рисовать, перебирая в цикле все примитиве на сцене, пикселями, попадающими в примитивы, и при этом знать о каждом пикселе в примитиве его реальные координаты.

6. на каждый пиксель на экране применять только те вычисления, которые требуются для вычисления его вторичных лучей, текстурных координат и т.п. Все остальные вычисления можно производить раз в кадр для каждого примитива в рамках его растеризации, если свойства растеризации изменились относительно предыдущего кадра.

7. вторичные лучи, shadow rays и т.п. так же просчитывать в сферических координатах.

8. осуществлять преобразования не переходя из сферических в декартовы координаты и обратно.

 

 

Аннотация.

Данный алгоритм является крупным шагом к рендерингу в реальном времени с высоким качеством изображения. На CPU можно получить существенное ускорения работы ray-tracing'a.

Если этот метод возможно будет реализовать на GPU, то можно будет достичь очень хороших результатов, но для этого может потребоваться реорганизация pipeline'a.

[END OF ATTACHED DOCUMENT, EVERYTHING ABOVE THIS LINE IN THE ATTACHED DOCUMENT IS COPYRIGHTED, ALEX V. KOSSIAKOV: ©2004 Алексей Косяков Валентинович]

[salf]

Well, ok. But lets look how a plane looks like in spherical coordinates:

Ax + By + Cz + D = 0

means

r * (A * cos(b) * cos(a) + B * cos(b) * sin(a) + C * sin(b)) + D = 0

r * k + D = 0

r = - D/k

 

Good, but we must calculate lots of sin and cos, that will take a lot of time... If alpha and beta depend on screen's x and y, then we can just precalculate them and put in an array of lets say 640x480x3 elements: cos(b)*cos(a) ; cos(b)*sin(a) ; sin(b). And how should we calculate A,B,C and D? We have lets say all three vertexes of triangle M1(x1,y1,z1), M2(x2,y2,z2), M3(x3,y3,z3):

A = y1 (z2 - z3) + y2 (z3 - z1) + y3(z1 - z2) B = z1 (x2 - x3) + z2 (x3 - x1) + z3(x1 - x2)

C = x1 (y2 - y3) + x2 (y3 - y1) + x3(y1 - y2) - D = x1(y2 z3 - y3 z2) + x2 (y3 z1 - y1 z3) + x3 (y1 z2 - y2 z1)

 

 

No need for the russian version, that was already in russian for me.

[Crazy Homeless Guy]

at 18 i was out drinking and chasing women, and hadn't used a computer for anything more than a text editor.

[Ernest Burden III]

at 18 i was out drinking and chasing women, and hadn't used a computer for anything more than a text editor.

 

At 18 I was a full-time renderer. Drawing perspectives by hand, airbrushing.

 

I could have done the math thing...I'm sure I could.

 

I am unsure what is being offered by this thread. There is some algorithm for raytracing, and it cannot be put on a website but it is put in text on our site? Is this an 'information wants to be free' exercise or a pitch to buy a product that uses this math? I just cannot tell. I cannot even tell what rendering engine would be able to use it.

 

See, I didn't do the math thing. I did the rendering thing.

[William Alexander]

at 18 i was out drinking and chasing women, and hadn't used a computer for anything more than a text editor.

 

Gee, at 18 I had just gotten other the thrill of Pong. Although, shots & centipede were interesting, looking like 16 yrs old had to do something with my frustration. hehehehe

[voltaire_ira]

Gee, at 18 I had just gotten other the thrill of Pong. Although, shots & centipede were interesting, looking like 16 yrs old had to do something with my frustration. hehehehe

gee, at 18 I had just cursed architecture for all the math subjects we were taking.hehehehe, i thought architecture had less math since its primarily graphical..hehe, i was wrong!

[krio]

At 18 I was a full-time renderer. Drawing perspectives by hand, airbrushing.

 

I could have done the math thing...I'm sure I could.

 

I am unsure what is being offered by this thread. There is some algorithm for raytracing, and it cannot be put on a website but it is put in text on our site? Is this an 'information wants to be free' exercise or a pitch to buy a product that uses this math? I just cannot tell. I cannot even tell what rendering engine would be able to use it.

 

See, I didn't do the math thing. I did the rendering thing.

 

 

It is posted on several forums for public testing.

[IC]

18 year old Russian Mathematician?

 

Never mind that-have you seen Sandrak, the 11 year old Latvian bodybuilder? Now that's advan...eh, wrong!

[STRAT]

/me gets back to toast and coffee

[kippu]

OMG OMG ...this is a cgarchitecture site ...architecture and computers ....please dont overload me with anything else

[JHalton]

I think if you amend the algorithm line 156 to e=3 x alpha over a % rty should

show the below result. In math form of course.

 

...>9

I can predict that that the formula for the 3 by 3 square will be 21. I will now prove this.

 

So X = 5T-19

 

T = 8

 

X = 5x8-19

 

= 40-21 = 19

 

The full formula= X=5T-21

 

Below is a grid with parts of the formula in. I will use this to

 

Figure out a formula for any T-Total on any width grid.

 

T-2G-1

 

T-2G

 

T-2G+1

 

T-G

 

T

 

T-total = T-2G-1

 

T-2G

 

T-2G+1

 

T-G

 

T

 

X=5T-7G

 

If the Grid Width (= G), and the T-Number (= T), the T-Total (= X) is calculated by

 

X=5T-7G Now I'm going to try the grid that I drew earlier i.e. G=9

 

The formula is X=5T-7G

 

Which changes to X=5T-7x9 X=5T-63.

 

Rotation of T shapes

 

1

 

2

 

3

 

4

 

5

 

6

 

7

 

8

 

9

 

10

 

11

 

12

 

13

 

14

 

15

 

16

 

17

 

18

 

19

 

20

 

21

 

22

 

23

 

24

 

25

 

26

 

27

 

28

 

29

 

30 <......>

 

 

LOL

 

Dan gets back to thinking of going outside for a cigarette.

[salf]

oh yeah?

 

well...lets see if anybody can beat this:

 

We can agree that A girlfriend is a product of time

and money right?

 

Girlfriend = Time * Money

 

Your girlfriend is a woman!

 

Girfriend = Woman

Woman = Time * Money

 

We all know that time is money...

 

time = money

woman = money * money

 

woman = (money)^2

 

We also know that money is the root of all evil,

correct?

 

money = sqrt(evil)

 

woman = [sqrt(evil)]^2

 

Hence,

 

woman = evil

 

WOMEN ARE EVIL!!!

[Ernest Burden III]

It is posted on several forums for public testing.

 

For those of us that are not young or smart--can you explain HOW this would be used and why it is better than what's in use today? Every now and then there is a new 'revolutionary' algorithm that will raytrace so fast it has time left over to make Strat's toast. Do you have examples of what your math can do vs. existing solutions?

 

Is this math something that can be used to write a new rendering engine for Max or Cinema, or is it meant for prodocts like POVray?

[kicks]

[Juan Altieri]

at 18 i have an atari and i wonder how any person can did this incredible complex thing...

[Crazy Homeless Guy]

still no one has an idea how the algorithym aactually applies to us. what does it mean, can we use it now? i am computer savy, but i do not know how to compile code, and why i wish i knew, there are other things that i need to acomplish in the 3d world before i start compiling my own code.

 

so basically i am asking, is this a teaser for something, or is this something i can use?

[krio]

For those of us that are not young or smart--can you explain HOW this would be used and why it is better than what's in use today? Every now and then there is a new 'revolutionary' algorithm that will raytrace so fast it has time left over to make Strat's toast. Do you have examples of what your math can do vs. existing solutions?

 

Is this math something that can be used to write a new rendering engine for Max or Cinema, or is it meant for prodocts like POVray?

 

 

Yes, this algorithm was created as new algorithm for all ray-tracing engines - 3d MAX, MAYA, POVray etc. And it's so fast so it can be used for realtime game engines(with better quality for sure). I've posted it so you can try it and see the difference(if you know how to code).

[STRAT]

yes, but how do i actually use it? how do i actually put it into action?

[IC]

What these replies are all saying Krio, is that we're not the people to try this.

 

Probably about 98% of us only know enough about computers to do what we do:produce the final result you see here.

 

No offence-I just think you're wasting your time here unless you provide us with an .exe file or something similarly simple!