Ray Tracer Project

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

User avatar
Govalant
Posts: 249
Joined: Mon Sep 17, 2007 2:50 am UTC
Location: Rosario, Argentina
Contact:

Ray Tracer Project

Postby Govalant » Thu May 05, 2011 6:42 pm UTC

I'm in second year Computer Science and I have to choose a project. The prof gave the ray tracer as an example (or maybe ray caster, he just basically said "take a 3d picture") an it seems pretty cool.

Do you think it's feasible to write this? I may be in the same group with two other students and have about two months until delivery.
Now these points of data make a beautiful line.

How's things?
-Entropy is winning.

User avatar
diabolo
Posts: 72
Joined: Fri Aug 08, 2008 4:17 pm UTC
Location: france

Re: Ray Tracer Project

Postby diabolo » Thu May 05, 2011 7:48 pm UTC

I'd say yes because it will depend on how complex you want (/are expected) to make it.

It shouldn't take long to make a simple version that works only with primary rays on spheres (for each pixel cast a ray and draw the pixel with the color of the first sphere the ray hits). You'd already be "taking a picture", it would be all flat and maybe not very interesting but still.
To make pretty images you would need to add lights, reflection, refraction, different types of objects, ... maybe optimize things so you don't have to brute force every raycast...

In my opinion it's feasible, and I believe you should be able to do it in a way that let you get results early and improve them incrementally (which is cool).

Carnildo
Posts: 2023
Joined: Fri Jul 18, 2008 8:43 am UTC

Re: Ray Tracer Project

Postby Carnildo » Fri May 06, 2011 5:58 am UTC

Govalant wrote:I'm in second year Computer Science and I have to choose a project. The prof gave the ray tracer as an example (or maybe ray caster, he just basically said "take a 3d picture") an it seems pretty cool.

Do you think it's feasible to write this? I may be in the same group with two other students and have about two months until delivery.

I wrote a basic raytracer in an afternoon once. Being familar with the POV-Ray code helped, but a basic raytracer is certainly something you could do in two months.

User avatar
Govalant
Posts: 249
Joined: Mon Sep 17, 2007 2:50 am UTC
Location: Rosario, Argentina
Contact:

Re: Ray Tracer Project

Postby Govalant » Tue May 10, 2011 3:10 am UTC

Thanks to you both, the Ray Tracer it is :P

Also if anyone has any nice articles on it they'd be helpful. I already have a few, but the more the better.
Thanks!
Now these points of data make a beautiful line.

How's things?
-Entropy is winning.

User avatar
zed0
Posts: 179
Joined: Sun Dec 17, 2006 11:00 pm UTC

Re: Ray Tracer Project

Postby zed0 » Mon May 16, 2011 4:02 pm UTC

While it's not really an article someone I used to know made a ray tracer in his spare time.
He posted on the MSDN forums about it a while back.

It's not the same ray tracer but he also made one which, with more recent modifications from other people, can be found in this git repository if you're interested in looking at the sources.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Ray Tracer Project

Postby Yakk » Mon May 16, 2011 6:47 pm UTC

How is your linear algebra?

I'd start with a really simple raster and triangle ray tracer.

Your scene is a collection of triangles. Your viewport is a bunch of parallel lines coming out from infinity.

You take these rays, and find the first triangle they intersect. You then color your output display that color.

Start with a single triangle. Draw white if you hit it, and black if you don't.

Next, add in a collection of triangles. (Keep it simple at this step -- an array of triangles. You go over each and every one, and find the one you hit earliest. Return from the function (distance, trianglePtr) or something).

Next, color the triangle. Change the color of the hit vectors to match the triangle.

Next, have a two triangles "go though" each other. Does it render right?

Now for some fun stuff. Add in transparency. When you hit a triangle that is transparent, keep going and pick up more colors. When the occlusion of the ray reaches nearly unity, stop going (this is important for later on). So now your rays have to start "before infinity".

Next, add in viewport change. Allow yourself to look at the model from a different angle. This is important for the next step...

Reflection. A certain percent of the brightness. By this point, you probably want to move over to exponential brightness, or things will look really muddy.

Finally, lets add in a light. When you hit a triangle, find the vector to the light (or each light), and determine how much brightness it deposits. If you want to get fancy, you should also take into account things blocking the light.

Things get exceedingly complex from here on out -- you will want to ray-trace from the light out, following reflections, while also ray-tracing from the eyes, tracing reflections (and transparency).

You also will want to improve your collision detection system from a basic "look at each triangle" to something like an oct-tree.

Multiple samples per pixel, perspective transformations, objects whose position is described by matrix transformations, etc.

Monte-carlo frequency and spacial sampling, frequency response and differential diffraction (rainbows!), bump mapping...

The rabbit hole goes on down to infinity.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Xeio
Friends, Faidites, Countrymen
Posts: 5101
Joined: Wed Jul 25, 2007 11:12 am UTC
Location: C:\Users\Xeio\
Contact:

Re: Ray Tracer Project

Postby Xeio » Mon May 16, 2011 7:19 pm UTC

Yakk wrote:Things get exceedingly complex from here on out -- you will want to ray-trace from the light out, following reflections, while also ray-tracing from the eyes, tracing reflections (and transparency).
Actually, this is fairly easy unless you're going at it from a performance perspective, since you just "fire" the rays, multiply by whatever coefficient they need, and return the result to the original ray.

Also, I suggest implementing things like spheres (you can make perfect spheres in raytracing, unlike with normal rendering), they look a lot cooler after you start shading/lighting/reflection. Geometry references (book or otherwise) are really useful for that since you basically just have to implement the ready-made formulas.

User avatar
uncivlengr
Posts: 1202
Joined: Fri Nov 14, 2008 10:35 pm UTC
Location: N 49°19.01 W 123°04.41

Re: Ray Tracer Project

Postby uncivlengr » Mon May 16, 2011 7:26 pm UTC

Excel Unusual recently went through the process of developing a 2d optics model, using spherical mirrors (circular in 2d, I guess). It's applied in Excel but there's enough background that it should be applicable to any language.
I don't know what to do for you

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Ray Tracer Project

Postby Yakk » Mon May 16, 2011 8:23 pm UTC

Xeio wrote:
Yakk wrote:Things get exceedingly complex from here on out -- you will want to ray-trace from the light out, following reflections, while also ray-tracing from the eyes, tracing reflections (and transparency).
Actually, this is fairly easy unless you're going at it from a performance perspective, since you just "fire" the rays, multiply by whatever coefficient they need, and return the result to the original ray.

Yes, but performance quickly collapses. You end up having to use hacks, because the number of paths you are interested in can easily grow exponentially.

...

Now I'm just playing around...

One could imagine generating a "sphere map" of incoming light by angle for each point on each surface. The fidelity of this map can vary. The outgoing light from the point then becomes a property of the sphere map scaled by the properties of the substance (how much does it scatter light? how much does it refract it?)

The density of the points on the surface you care about is also important -- I could see a first approximation where your samples are interpolated over the surface in a presumed simple way, and where discontinuities are detected and the sample rate scales upwards...

That would be amusing to write. It would, in theory, generate a really crude image that would add detail using heuristics (hey look, there is a relatively sharp edge here and/or difference in how the lighting behaves -- lets add more points! Oh, I threw a ray at that surface that is way off what I was expecting -- I should increase detail in that area.) Detecting "sharp" things is hard still... I guess that is why you do both push-and-pull detail boosting?

Note that my knowledge of raytracing consists of fiddling around, and spending time with someone who did a masters working on some parts of the problem. So it isn't that deep.
Also, I suggest implementing things like spheres (you can make perfect spheres in raytracing, unlike with normal rendering), they look a lot cooler after you start shading/lighting/reflection. Geometry references (book or otherwise) are really useful for that since you basically just have to implement the ready-made formulas.

I thought triangles plus non-constant normals generate something basically indistinguishable from a sphere to the eye? (the shape of the edge can be off, admittedly)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

_Axle_
Posts: 253
Joined: Fri Sep 24, 2010 7:33 pm UTC

Re: Ray Tracer Project

Postby _Axle_ » Mon May 16, 2011 9:19 pm UTC

Don't know where to start exactly, so here is just my ramblings on the topic :
I have programmed a C++ ray tracer from scratch as a school project and now currently rewriting from scratch again a ray tracer in C#. That involved writing my own math libraries ( basically a Vector3 and a Matrix 3x3 class, as well as a Ray Class/Struct ).
I also have written a 2D and 3D rendering pipeline from scratch at school, as well as many projects that involved either OpenGL and DirectX, so my perspective of how to approach the Ray Tracer is from that end, not a generic CS major.

Yakk did make some good points about how to start, though I think the order might be a little off in my mind.

Starting with a non-recursive Ray Caster is important. There is no point to just jump into the deep end if you have never programmed a Ray Tracer before. Though, I think the camera is important enough that it should be learned and integrated at the start of your Ray Caster.

The Transparency would be physically wrong, unless you actually curve the ray. Unless we assume all objects are infinitely thin shell and have normal air inside, so the index of refraction never comes into play.

For lighting, look at Phong Lighting. Yes, its wrong, but its one of the better 'fast' lighting models we have. Though, you could look up other lighting models and use those instead, though they might require more pieces of data. Phong only requires simple math data that is already present in the scene ( Object locations, Normals, Diffuse, Specular and Ambient ). When doing lighting, look into shadows, if an object is in between your contact point and a light, it receives no light from it.

At using just triangles... I think for a Ray Tracer, it is just generally wrong. For a regular Raster pipeline, it makes sense, but not for a Ray Tracer. It would take hundreds, if not a thousand triangles to simulate a smooth sphere, when all you needed was a Center point and a radius. Also, there is only 1 object to check against, not hundreds. Ray Tracing allows the collision between 2 'objects' of equations, so it is best to use functions that define objects and not just triangles everywhere.

At Performance . . . I really wouldn't worry too much about it, since its a ray tracer.... unless your idea is to make it real time.
Yakk wrote:Computer Science is to Programming as Materials Physics is to Structural Engineering.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Ray Tracer Project

Postby WarDaft » Mon May 16, 2011 11:15 pm UTC

Eh, with triangles and clever depth mapping, you can approximate a sphere essentially indistinguishably with a d20. If you don't care about efficiency, you could even use a trapezoid.

Also, depending on the language you're using, recursive ray tracing could be one of the easiest ways to do anything more than just painting the shapes on the scene.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

_Axle_
Posts: 253
Joined: Fri Sep 24, 2010 7:33 pm UTC

Re: Ray Tracer Project

Postby _Axle_ » Mon May 16, 2011 11:19 pm UTC

WarDaft wrote:Eh, with triangles and clever depth mapping, you can approximate a sphere essentially indistinguishably with a d20. If you don't care about efficiency, you could even use a trapezoid.

Also, depending on the language you're using, recursive ray tracing could be one of the easiest ways to do anything more than just painting the shapes on the scene.


But its missing the point of a Ray vs Sphere collision is very simple, straight forward and only 1 object. If you mapped a Sphere by using other objects, you are already increasing how many collisions you have to calculate and the memory footprint of said object.
Yakk wrote:Computer Science is to Programming as Materials Physics is to Structural Engineering.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Ray Tracer Project

Postby WarDaft » Mon May 16, 2011 11:42 pm UTC

But it's not missing the fact that it's hard much harder to go from rendering a mathematically defined sphere to rendering almost arbitrary surfaces, than it is to go from depth mapped triangles to almost arbitrary surfaces.

What it's really missing is convenient multiple point of view calculations. The texture for the triangle would have to be at least partially calculated from every angle of interest that can see it. Of course you could fudge it for diffuse global lighting calculations, just leave it as triangles. The differences could certainly be discernible, but viewers would be unable to tell which was the more correct render in virtually all cases. For reflections though, you'd have some work to do. It is faster than making zillions of little polygons, though I don't know how it would compare to Bézier surfaces.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

Re: Ray Tracer Project

Postby squareroot » Tue May 17, 2011 12:51 am UTC

"A d20 is virtually indistinguishable from a sphere" sounds pretty wrong to me... it may be true if you have a good shading algorithm, but look at something http://en.wikipedia.org/wiki/File:Gouraud_low_anim.gif and tell me that looks like a sphere.
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

_Axle_
Posts: 253
Joined: Fri Sep 24, 2010 7:33 pm UTC

Re: Ray Tracer Project

Postby _Axle_ » Tue May 17, 2011 12:56 am UTC

I will add more later, since I am about to head out, but ..

You can render every object as if it was a mesh of polys ( Triangles ), though doing so changes where you set your focus on your project. Improving Speed will be your number 1 task, so you will need some world space division ( KD-Tree, HBV, Oct tree, combination of stuff, etc ). Also, your scene has to be pre-defined as triangles or you need to write up functions that convert functions into a mesh of polys.

In the end, having a combination of everything would be a perfect world, but for a first ray tracer/Early CS class, working around a few limitations, such as "Objects can only be planes, Spheres, Boxes, Ellipsoids" is a fair way to implement it.
Yakk wrote:Computer Science is to Programming as Materials Physics is to Structural Engineering.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Ray Tracer Project

Postby WarDaft » Tue May 17, 2011 1:17 am UTC

squareroot wrote:"A d20 is virtually indistinguishable from a sphere" sounds pretty wrong to me... it may be true if you have a good shading algorithm, but look at something http://en.wikipedia.org/wiki/File:Gouraud_low_anim.gif and tell me that looks like a sphere.


Well that's why I said "and clever depth mapping." I specifically mean to map the texture as being 'beneath' the triangle you are rendering, and trace across it to generate the appearance of three dimensional texture, rather than bump mapping which merely simulates this by the cheaper operation of displacement.

I should think the easiest way to write a ray tracer would be one that implemented only triangles. To get nicer looking objects, add simple textures. To get very detailed shapes without requiring prohibitively many triangles, add depth mapping as part of the texture operation.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Xeio
Friends, Faidites, Countrymen
Posts: 5101
Joined: Wed Jul 25, 2007 11:12 am UTC
Location: C:\Users\Xeio\
Contact:

Re: Ray Tracer Project

Postby Xeio » Tue May 17, 2011 10:43 pm UTC

Yakk wrote:Yes, but performance quickly collapses. You end up having to use hacks, because the number of paths you are interested in can easily grow exponentially.
Doesn't matter, I would never suggest trying to write a performance tracer as a first project. Even a naive tracer can render a simple scene fairly quickly with modern hardware.

WarDaft wrote:I should think the easiest way to write a ray tracer would be one that implemented only triangles. To get nicer looking objects, add simple textures. To get very detailed shapes without requiring prohibitively many triangles, add depth mapping as part of the texture operation.
I think it really depends on what your goals are. Spheres are one of the show-offy things because they can be done almost as trivially as triangles in raytracing (you can have a perfect sphere with no real performance drops, actually it's likely a lot faster than a dozen triangles unless you have a lot of triangle-specific optimizations or spacial optimizations to trim objects). Also, they look cooler. You can't forget coolness, this is a raytracer after all.

It's all to do with how in-depth the OP wants to go with the project. Are simple shapes ok? Solid colors? Do you want texturing? Reflection? Refraction? Naive lighting (blocked rays to a light source/tangent lines)? Ambient occlusion? Radiosity? Non-point light sources? What realistic scene size do you want to trace in, say, a minute?

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Ray Tracer Project

Postby WarDaft » Wed May 18, 2011 12:36 am UTC

What I meant was that I imagine it would be easier to implement triangles and then height mapping for shapes that triangles don't approximate well, rather than implementing a variety of shapes.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
headprogrammingczar
Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: Ray Tracer Project

Postby headprogrammingczar » Wed May 18, 2011 9:44 pm UTC

I think it would be easier to implement everything as NURBS, and totally ditch the special cases.
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you


Return to “Computer Science”

Who is online

Users browsing this forum: Majestic-12 [Bot] and 5 guests