[b]Tracing the rays for fun and profit:
[/b]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. [b]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.
[/b]-----------------------------------------------------------------------------------------------------------------------------------------------
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 (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 xpsi and yphi 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]
[b]Сферический ray-tracing.
[/b]
Стандартный алгоритм ray-tracing, или метод трассировки лучей, был предложен Артуром Аппелем (Arthur Appel) еще в 1968 году и дополнен алгоритмом общей рекурсии, разработанным Whitted в 1980 году.
В основном он сводится к необходимости для каждого пикселя на экране в декартовой системе координат провести луч и искать пересечения с плоскостями треугольников, затем для каждого пересечения смотреть, попадает ли луч в треугольник. Первое попадание по лучу, заданного параметрически, и есть тот пиксель, цвет которого дальше надо считать.
Прочие вариации этого алгоритма аналогично сложны по вычислениям.
Используемые так же, пиксельные Shader’ы достаточно быстры и все последние видеокарты приспособлены именно под них. Но невозможно осуществить нормальный доступ из шейдера к прочей геометрии сцены. Для стандартных треугольников метод применим, но не для непрямолинейной геометрии - сфер и т.п.
Визуальное качество применения пиксельных шейдеров не может сравниться даже с традиционным ray-tracing’ом.
[b]
Суть предлагаемого сферического ray-tracing’a:
[/b]Для каждого примитива считаются нужные сферические координаты раз в кадр. Что можно делать как стандартным способом перспективного преобразования для обычных декартовых систем координат, так и через формулы преобразования декартовых координат в сферические. Во втором случае мы получим перспективно-правильную проекцию.
В итоге мы получаем линейную зависимость угловых составляющих сферических координат на плоскости от координат на нашем экране. Здесь не приводится доказательств того, что при такой аналогии сохраняются все возможные свойства, потому что способов доказательства очень много, это не входит в рамки данного текста и, к тому же, это проверено экспериментально.
Затем осуществляется стандартная растеризация, например scan-line алгоритм, но в угловой составляющей сферических координат. После этого мы можем перебрать в цикле каждый примитив и трассировать только лучи, попадающие в эти примитивы: перебираем каждую строчку от минимальной до максимальной, а в каждой строчке перебираем от просчитанного ранее минимального столбца до максимального.
Для каждого такого попадания просчитывается дистанция и сравнивается с буфером глубины.
После этого попадание считается действительным и происходит расчет текстурных координат, вторичных и прочих лучей и других свойств, для вычисления цвета этого пикселя.
Таким образом, мы почти полностью избавляемся от присущего ray-tracing’у метода грубой силы, сохраняя все его возможности, и внося еще множество разных оптимизаций.
[b]Основные отличия нового алгоритма, которые могут применяться по отдельности в реализации ray-tracing’a:
[/b]1. использование сферических координат для трассировки первичного луча.
-
использование сферических координат для трассировки вторичных лучей и всех остальных лучей.
-
предварительный просчет принадлежности пикселей рабочей плоскости к примитивам (предварительная растеризация) через переход на рабочую плоскость, либо из сферических координат либо из декартовых.
-
использование предварительной растеризации для по-примитивной трассировки.
-
просчитывание углов лучей отражения и преломления линейной комбинацией двумерных углов предыдущего луча и нормали.
-
предварительная растеризация примитивов в координатах вторичных и прочих лучей для их трассировки.
[i]Многие эти особенности могут быть реализованы, или уже реализованы в других, не ray-tracingовых, методах отображения. Например можно использовать сферические координаты в реализации стандартных shaderов.
[/i]
[b]Основные отличия нового алгоритма позволяют:
[/b]1. не высчитывать лучи параметрически.
-
использовать угловые составляющие сферических координат как координаты пикселя на экране.
-
в следствии применять к ray-tracing стандартные алгоритмы растеризации и буферизации.
-
в следствии трассировать не каждый пиксель на экране, а лишь пиксели, попадающие в треугольник или другой приметив.
-
в итоге - рисовать, перебирая в цикле все примитиве на сцене, пикселями, попадающими в примитивы, и при этом знать о каждом пикселе в примитиве его реальные координаты.
-
на каждый пиксель на экране применять только те вычисления, которые требуются для вычисления его вторичных лучей, текстурных координат и т.п. Все остальные вычисления можно производить раз в кадр для каждого примитива в рамках его растеризации, если свойства растеризации изменились относительно предыдущего кадра.
-
вторичные лучи, shadow rays и т.п. так же просчитывать в сферических координатах.
-
осуществлять преобразования не переходя из сферических в декартовы координаты и обратно.
[b]Аннотация.
[/b]Данный алгоритм является крупным шагом к рендерингу в реальном времени с высоким качеством изображения. На 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 Алексей Косяков Валентинович]