In article <3ee5829b$1@news.povray.org>,
 "Thorsten Froehlich" <tho### [at] trfde> wrote:

> No, the problem is, you cannot optimise the scanline algorithm further than
> what I outlined (at least not bringing down the complexity).  In fact, the
> complexity I outlined holds for the first implementations 30 or so years ago
> and it still holds in the 3d hardware accelerators of today.  The main
> benefit of the scanline algorithm is that you can make the constant time
> factor very, very small compared to ray-tracing.

You could probably do something somewhat similar to bounding...do an 
assay render on the bounding box of a group of triangles. If it would 
have been drawn, fully render the individual triangles, if it would not 
have been drawn then ignore them. Probably not as efficient as in 
raytracing, but it could work...I don't see a way to get it to work with 
hardware accelerated rendering though, unless there's a way to check if 
the depth buffer would have been modified without actually modifying it. 
You could save/render/compare/restore, but that'd probably take longer, 
especially on large resolutions.


> Yes, it does.  The problem is, the one million to one difference of the
> constant factors.  And due to the simplicity of the scanline algorithm, it
> is, compared to ray-tracing, much easier to implement it in hardware (you
> need only a few thousand gates, most of the logic on today's accelerator
> chips is used for texture and geometry computations.

It can also be done easily with integer math, while raytracing requires 
floating point...even 64 bits isn't enough for practical fixed point 
raytracing. This lets the logic be simplified, cutting development costs 
and allowing higher speeds to be attained more easily.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message

In article <3ee5a9ca@news.povray.org>,
 sascha <sas### [at] userssourceforgenet> wrote:

> I agree with you that raytracing would be the winner if there were *a 
> lot* of primitives which appear smaller than a single pixel so that 
> their bounding-boxes will never get hit by a ray - but usually both, 
> REYES and game-engines use some sort of level-of-detail optimizations to 
> prevent this scenario...

The shapes don't need to appear smaller than a pixel, they just need to 
have another shape be hit in front of their bounds so the bounded shape 
isn't tested. If you have a lot of shapes partially or totally obscured 
by other shapes, raytracing gets better by testing fewer shapes while 
scanlining stays about the same, having to draw the same number of 
triangles and shade the same number of pixels.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message

In article <cja### [at] netplexaussieorg> , 
Christopher James Huff <cja### [at] earthlinknet>  wrote:

> You could probably do something somewhat similar to bounding...do an
> assay render on the bounding box of a group of triangles.

No, because you would have to be able to keep multiple levels.  A bounding
box is bigger than the actual geometry.  So only looking at the frontmost
bounding box isn't enough.

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

In article <3ee5f3e7@news.povray.org>,
 "Thorsten Froehlich" <tho### [at] trfde> wrote:

> > You could probably do something somewhat similar to bounding...do an
> > assay render on the bounding box of a group of triangles.
> 
> No, because you would have to be able to keep multiple levels.  A bounding
> box is bigger than the actual geometry.  So only looking at the frontmost
> bounding box isn't enough.

I don't think you understood what I meant. Draw from front to back. Use 
single bounding boxes for closely spatially related groups of triangles, 
maybe with an oct-tree structure. If the bounding box of a group is 
occluded by triangles that have already been drawn (it has no pixels at 
lesser depth), all those triangles are also occluded, so no need to draw 
them. I'm assuming no alpha-style transparency, because you mentioned 
backside culling. Nothing to do with the frontmost bounding box, except 
that you could skip the test for the frontmost few levels because they 
are so unlikely to be occluded.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message

I've just read a paper which states that real-time ray-tracing might become
doable on the next generation GPUs using their fragment shaders:

Ray Tracing on Programmable Graphics Hardware - Purcell et al., SIGGRAPH
2002
http://graphics.stanford.edu/papers/rtongfx/

- Micha


-- 
POV-Ray Objects Collection: http://bjects.povworld.org

Post a reply to this message

> Yes, the display routines are not intended to display a high framerate.
> The time taken to display the image is not long enough to bother
> optimizing though...what's a few hundred milliseconds when the render
> takes seconds, let alone minutes or hours?

Yeah, entirely as I expected.

> In addition to that, parsing is pretty slow, especially when you're
> talking about doing real-time stuff.

Mmm... that's true... I wonder how much time the actual physics simulation
took up? hehehe

> > ...such as building polyhedrons out of planes using CSG? (I do this all
the
> > time... *is* there any other way to build polyhedrons in POV?!?)
>
> Yes, that is one good example. POV can't bound an intersection of
> infinite shapes, you really need to manually bound when making
> polyhedrons that way.

...and remember to tell POV-Ray *not* to remove them ;-)

> There are alternate methods: you could use boxes
> or meshes. An intersection of two boxes makes an efficient octahedron,
> and of course a box is the best way to do a cube.

Usually I just want to build million-sided mirror balls or gemstones or
such... and I don't like meshes. Somehow seems like a "trick". (OK, I'm
weird!)

Thanks.
Andrew.

Post a reply to this message

Micha Riser <mri### [at] gmxnet> wrote:
> I've just read a paper which states that real-time ray-tracing might become
> doable

  "Real-time raytracing" is not an unambiguous term.
  There have been real-time raytracers in the mid-90's for the first Pentium,
so in that sense that's old news. It doesn't *become* doable because it
has been doable for over 5 years.

  All this comes down to how we really want to define "realtime raytracing".
What kind of frame rates, scene complexity and image resolution is enough
to satisfy the conditions?

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message

Thorsten Froehlich wrote:

> In article <3ee4e321$1@news.povray.org> , sascha
> <sas### [at] userssourceforgenet>  wrote:
> 
> No, the problem is, you cannot optimise the scanline algorithm further
> than
> what I outlined (at least not bringing down the complexity).  In fact, the
> complexity I outlined holds for the first implementations 30 or so years
> ago
> and it still holds in the 3d hardware accelerators of today.  The main
> benefit of the scanline algorithm is that you can make the constant time
> factor very, very small compared to ray-tracing.
> 
>> But couldn't the same (or other - e.g. octree) optimizations be applied
>> to the scanline algorithm too?
> 
> No, because the scanline algorithm requires you to draw everything in the
> viewing area to determine its visibility.  You can cull backfacing
> triangles, but that only divides to constant factor by about two.

Well, there is further optimisation possible: view-frustum culling and
occlusion culling. You can determine on the CPU (using some Bounding Volume
Hierarchies) which groups of triangles are not visible from the viewpoint.
For example a scene in a house you can quickly determine which rooms one
sees into at all and which you don't. So there is no need to move these
triangles down the rendering pipline. Of course this triangle exculsion is
only an conservative estimation and no exact solution.

Another interesting thing to think about is: Why do we use triangles? As
today there are often tens of triangles per pixel in a detailed model one
doesn't really need the full triangles. So another idea is to stick to
points and not store the interconnections of the points but only the points
assosiated with a normal and a texture. This reduces the memory
requirements. For the rendering you draw either a small box for each point
(which is supported by todays GPUs) or more exact a small ellipse. Using
points as basing privmitives has another advantage: You can quickly
generate different LODs of models (which is much slower for triangle
meshs), so you can use a reduced-point version when an object is farther
away.

That this actuallly works can be seen in the video from:
http://www9.informatik.uni-erlangen.de/Research/Rendering/SPT

- Micha

-- 
POV-Ray Objects Collection: http://objects.povworld.org

Post a reply to this message

Warp wrote:

> Micha Riser <mri### [at] gmxnet> wrote:
>> I've just read a paper which states that real-time ray-tracing might
>> become doable
> 
>   "Real-time raytracing" is not an unambiguous term.
>   There have been real-time raytracers in the mid-90's for the first
>   Pentium,
> so in that sense that's old news. It doesn't *become* doable because it
> has been doable for over 5 years.

I know that it has been made on CPUs already.. but, if you had properly
quoted my statement it would say:

"I've just read a paper which states that real-time ray-tracing might become
doable on the next generation GPUs using their fragment shaders:"

so the new thing is that it's getting possible on the standard GPUs.

- Micha


-- 
POV-Ray Objects Collection: http://objects.povworld.org

Post a reply to this message

In article <3ee6649f@news.povray.org>, Micha Riser <mri### [at] gmxnet> 
wrote:

> Another interesting thing to think about is: Why do we use triangles? As
> today there are often tens of triangles per pixel in a detailed model one
> doesn't really need the full triangles. So another idea is to stick to
> points and not store the interconnections of the points but only the points
> assosiated with a normal and a texture. This reduces the memory
> requirements. For the rendering you draw either a small box for each point
> (which is supported by todays GPUs) or more exact a small ellipse. Using
> points as basing privmitives has another advantage: You can quickly
> generate different LODs of models (which is much slower for triangle
> meshs), so you can use a reduced-point version when an object is farther
> away.

Point fields can be raytraced as well...there's an algorithm that 
basically uses a disc for each point, intersecting with several nearby 
discs and interpolating normals and intersection points. I've been 
working on an implementation, but it isn't even rendering plain discs 
yet.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message