Allegro.cc - Online Community

Allegro.cc Forums » Off-Topic Ordeals » Any interest in a 'ray casting' competition?

This thread is locked; no one can reply to it. rss feed Print
Any interest in a 'ray casting' competition?
Thomas Harte
Member #33
April 2000
avatar

Quote:

I noticed that Thomas is using a Mac.
...
Im going to stay compatible only with x86 and just hope my entry still works on >=75% of the judges. Sorry Thomas

That's cool. My macitude is one of the main reasons that the 75%/50% rules exist.

Perhaps we should be looking for some non-competing judges so that the spread of machines is more realistic? I'd be surprised if as much as 9% of Allegro users use an Apple. That'd be twice the average across all computers sold...

Quote:

and maybe some inline assembly to speed up the inner raycasting loops

Check out the GCC vector extensions if you're just looking for SIMD (i.e. MMX/SSE for intel people, Altivec for us Macers) usage!

The Mac has 32 128bit vector registers if that helps anybody plan. I don't have a clue about the PC but if you're otherwise thinking of using inline assembly, I guess you know.

EDIT: 100th post! Nice! But lets keep pushing...

EDIT2: I'm giving strong consideration to adding a 'best in 24 hours' category back in to try and attract the Speedhack/TINS crowd. Will have to think about that sort of thing.

Fladimir da Gorf
Member #1,565
October 2001
avatar

Quote:

Check out the GCC vector extensions if you're just looking for SIMD (i.e. MMX/SSE for intel people, Altivec for us Macers) usage!

Maybe I could use those if I make something software-based.

Quote:

The Mac has 32 128bit vector registers if that helps anybody plan. I don't have a clue about the PC but if you're otherwise thinking of using inline assembly, I guess you know.

Whoah, that's a lot! Thus far I've been coping with 8 64-bit registers. There could be more these days, though.

EDIT: By the way, the GCC vector extension supports division operator, but I wasn't aware of that MMX had a division instruction... maybe only SSE supports it? So it's only for floats?

OpenLayer has reached a random SVN version number ;) | Online manual | Installation video!| MSVC projects now possible with cmake | Now alvailable as a Dev-C++ Devpack! (Thanks to Kotori)

HoHo
Member #4,534
April 2004
avatar

Quote:

There could be more these days, though.

no there isn't on x86 architecture

In IA-32 architecture there is 8 32bit general purpourse registers, 8 64bit MMX/FPU registers and 8 128bit SSE registers, no more no less. On AMD64/EM64T there is 16 64bit general purpource registers if OS is 64bit, not sure about the numbers of mmx/fpu and sse registers.

Hopefully my memory is good enough and I didn't mess up the numbers and names.

[edit]
mixed up some things

__________
In theory, there is no difference between theory and practice. But, in practice, there is - Jan L.A. van de Snepscheut
MMORPG's...Many Men Online Role Playing Girls - Radagar
"Is Java REALLY slower? Does STL really bloat your exes? Find out with your friendly host, HoHo, and his benchmarking machine!" - Jakub Wasilewski

Thomas Harte
Member #33
April 2000
avatar

Quote:

By the way, the GCC vector extension supports division operator, but I wasn't aware of that MMX had a division instruction... maybe only SSE supports it?

Having a quick read around the subject, it seems Altivec doesn't have a divide. It has some other complicated but useful sounding features to do with determining the minimum and maximum values in vectors and getting the hardware to do a 1 cycle 'permutation' (i.e. arbitrarily shift and combine bits from the vector registers into one target register) but not that, and nothing that does 'horizontal' operations (in intel speak). It also seems to be based entirely on three address form.

I think I need to read up a little more on this sort of topic!

Krzysztof Kluczek
Member #4,191
January 2004
avatar

Quote:

Check out the GCC vector extensions if you're just looking for SIMD (i.e. MMX/SSE for intel people, Altivec for us Macers) usage!

I don't think any external code could be useful inside inner loop of scanline filler to do normalmapping.

Quote:

In IA-32 architecture there is 8 32bit general purpourse registers, 8 64bit MMX registers and 8 128bit SSE/FPU registers, no more no less.

FPU stack is shared with MMX registers, not SSE ones. :)

HoHo
Member #4,534
April 2004
avatar

Quote:

In IA-32 architecture there is 8 32bit general purpourse registers, 8 64bit MMX registers and 8 128bit SSE/FPU registers, no more no less.

Thanks for reminding. Repaired

__________
In theory, there is no difference between theory and practice. But, in practice, there is - Jan L.A. van de Snepscheut
MMORPG's...Many Men Online Role Playing Girls - Radagar
"Is Java REALLY slower? Does STL really bloat your exes? Find out with your friendly host, HoHo, and his benchmarking machine!" - Jakub Wasilewski

Thomas Harte
Member #33
April 2000
avatar

Quote:

I don't think any external code could be useful inside inner loop of scanline filler to do normalmapping.

I have no idea whatsoever what you mean by this. Code external to what? The gcc extensions aren't function calls or anything like that...

EDIT: I was mistaken about the lack of 'horizontal' operations. Operators to do various combinations of adds, averages and compares across vector elements seem to exist.

Krzysztof Kluczek
Member #4,191
January 2004
avatar

Quote:

The gcc extensions aren't function calls or anything like that...

Well, they seem much more useful now. :)

Peter Hull
Member #1,136
March 2001

It doesn't have to be an 'action' game does it? How about something like SimCity with ray-traced buildings?

Pete

nonnus29
Member #2,606
August 2002
avatar

I think that should be allowable....

HoHo
Member #4,534
April 2004
avatar

Things like this should definitely be allowed.

I don't think limiting to some certain game generes or engine types is a good idea.

I have a rather unique idea for my little thingie and it probably wouldn't fit in most engine or game types. It does use raytracing(not casting) for generating visuals and that should be enough for being accepted for competition

__________
In theory, there is no difference between theory and practice. But, in practice, there is - Jan L.A. van de Snepscheut
MMORPG's...Many Men Online Role Playing Girls - Radagar
"Is Java REALLY slower? Does STL really bloat your exes? Find out with your friendly host, HoHo, and his benchmarking machine!" - Jakub Wasilewski

Thomas Harte
Member #33
April 2000
avatar

I third the motion that any restriction should be placed on gameplay.

I know at least two people are planning 'big surprise' type entries, but does anybody want to discuss their plans? I'm having quite a few thoughts but I'm just not sure how well they're going to come off and which I'm going to be able to complete. I need to make an actual decision between two quite different ideas I have and get going (since I'm generally too busy to be a 'within the competition time' sort of entrant).

Hopefully when OS 10.4 arrives on Saturday with XCode 2.0 it won't break the Allegro (or any other) project stationery, otherwise I'll be irritatingly delayed.

HoHo
Member #4,534
April 2004
avatar

Quote:

does anybody want to discuss their plans?

I could discuss a bit more in detail after I get my "engine" running fast enough and some features like moving camera and geometry. After having achieved this I could start implementing my game ideas. Until then I describe what it can do so far.

Currently it has no SIMD support and runs crappy 1.6fps@640x480 with ~2600 polygons on my p4 3.3G when I disable shadows. When I enable them speed drops about two times(depending mostly on amount of lights).

On the good side I can increase polycount from 2.6k to 13k* and have only about 10-15% speedtrop ;D
*)same model duplicated 5x in slightly different positions

What is the smallest screen area that must be rendered with casting/tracing rays? Can I run the game in 640x480 with game area of ~600x400 and render a 2x scaled image in it(300x200)? If I could then I guess my game should be running ~5-10fps on machines supporting floating point SIMD and frequency >2GHz p4/1.5GHz amd's.

On the other hand I have lots of ideas how to speed stuff up considerably so maybe in the end it's runnable even on those <800MHz machines.

I just ran some tests in 300x200 on my 3.3G p4.
I had two scenes. One had 2610 triangles(simple room and a knot in it), other had 13010 triangles (same room, 5 knots with little position offsets). Knots are untextured, walls had bilineary filtered texture on them.

ints means intersections, time is in milliseconds.

1With shadows from two pointlights:
2Scene1:
3Rays per second: 790891
4Ints per second: 9650854
5Ints per ray: 12.2025
6Avg. frame time: 271
7 
8Scene2:
9Rays per second: 678799
10Ints per second: 10904076
11Ints per ray: 16.0638
12Avg. frame time: 316
13 
14Without shadows:
15Scene1:
16Rays per second: 1.57013e+06
17Ints per second: 6064711
18Ints per ray: 3.86255
19Avg. frame time: 136
20 
21Scene2:
22Ints: 411827252
23Rays per second: 1.50791e+06
24Ints per second: 6859443
25Ints per ray: 4.54898
26Avg. frame time: 142

I guess I'm in pretty good shape already, 7fps without shadows and high polycount and ~3fps with shadows.

How many rays does your engines cast per second? I guess duke/doom style engines cast way more rays but image quality and scene composition flexibility is something to be desired.

There are one huge problem I currently have no ideas how to solve. In it's current state it's impossible to have any moving geometry in my engine. Moving lights is easy but making geometry moveable is going to be darn hard. Hopwfully I can get it done within three months.

As a little teaser I attached a sample screenshot of the high detailed scene with shadows enabled. It doesn't represent my game what so ever. Enjoy :-P

__________
In theory, there is no difference between theory and practice. But, in practice, there is - Jan L.A. van de Snepscheut
MMORPG's...Many Men Online Role Playing Girls - Radagar
"Is Java REALLY slower? Does STL really bloat your exes? Find out with your friendly host, HoHo, and his benchmarking machine!" - Jakub Wasilewski

Oscar Giner
Member #2,207
April 2002
avatar

But you're doing a raytracer, not a raycaster. You can not cast more than one ray per pixel (the one from the camera).

Fladimir da Gorf
Member #1,565
October 2001
avatar

I'd say a raytracer does for a raycaster in this competition...

OpenLayer has reached a random SVN version number ;) | Online manual | Installation video!| MSVC projects now possible with cmake | Now alvailable as a Dev-C++ Devpack! (Thanks to Kotori)

Oscar Giner
Member #2,207
April 2002
avatar

A raycaster is a kind of raytracer, not the other way.

HoHo
Member #4,534
April 2004
avatar

If I disable shadows then my engine is technically a raycaster. Only difference is that I use different methods for storing scene and traversing it than usual raycasters do

__________
In theory, there is no difference between theory and practice. But, in practice, there is - Jan L.A. van de Snepscheut
MMORPG's...Many Men Online Role Playing Girls - Radagar
"Is Java REALLY slower? Does STL really bloat your exes? Find out with your friendly host, HoHo, and his benchmarking machine!" - Jakub Wasilewski

Fladimir da Gorf
Member #1,565
October 2001
avatar

I think if you read the rules, a raytracer does for a raycaster... I'm not sure, though. But technically you're right Oscar.

OpenLayer has reached a random SVN version number ;) | Online manual | Installation video!| MSVC projects now possible with cmake | Now alvailable as a Dev-C++ Devpack! (Thanks to Kotori)

Thomas Harte
Member #33
April 2000
avatar

Quote:

You can not cast more than one ray per pixel (the one from the camera).

But that brings us into several difficulties. What exactly counts as one ray? HoHo's shadows appear not to have soft edges, so I guess he is only casting one ray per pixel, it just so happens that the ray can 'bounce'. Constructing a rule that doesn't allow bouncing also kills a wide range of possible portal engines, namely those that keep sectors without an absolute position but merely as relative to one another. In those it is clear that if space is considered a global then single rays jump around and change direction all over the place.

In addition we have problems with people who want to do post processing effects. Full scene anti-aliasing becomes impossible, as do camera focus effects.

On the current competition rules ray tracing is allowed. But the question isn't so much "what may be entered" as "what may win". You'll see that I've recently added the categories "best 'Wolfenstein' style game" and "best 'Doom' style game". The idea of those is that an incentive remains for those of us who just want to do the traditional thing. Those categories are picked on the idea that the majority of people will.

In addition, the final formulation of categories (the element of the competition rules that has so far received the least thought) should be structured so that the "prettiest" entry doesn't win a clean sweep on that basis alone. So in a strict sense the scope of the competition in tems of algorithms and the display they can generate shouldn't necessarily act to deter from entries that have large limitations on the display they can produce where those limitations can be justified for some reason.

Fladimir da Gorf
Member #1,565
October 2001
avatar

By the way, I don't think the rules say you have to cast one ray per pixel? Have I understood them correctly?

OpenLayer has reached a random SVN version number ;) | Online manual | Installation video!| MSVC projects now possible with cmake | Now alvailable as a Dev-C++ Devpack! (Thanks to Kotori)

Thomas Harte
Member #33
April 2000
avatar

Quote:

By the way, I don't think the rules say you have to cast one ray per pixel? Have I understood them correctly?

No, they don't. But I was at least partly seeking to explain why they don't.

nonnus29
Member #2,606
August 2002
avatar

My 'secret plan' is to raycast the walls and draw my own polygons (probably just gauroud, affine texture mapped nothing exciting).

Erkle
Member #3,493
May 2003
avatar

What exactly is a "Doom style game"? I plan on doing something like Duke Nukem 3D, would this still fit in th Doom category?

I'm a little confused about the uniform ray rule, does it mean I can't make mirrors by bouncing rays? Can I do per-slither lighting by casting rays from nearby lights to the current slither? Can I do Quake 3 style teleporters that you can see through?

P.S. Duke Nukem 3D does mirrors without bouncing by making a virtual sector behind the wall. It also does lighting per-sector not per-slither.

P.P.S. I assume I can't just make an engine that loads the actual Duke Nukem 3D levels and art, that would be a little unfair. Although it would definitely pass the 30 minutes gameplay thing;D

If the writing above has offended you, you've read it wrong.....fool.
And if you read that wrong it means 'All of the above is opinion and is only to be treated as such.'

Krzysztof Kluczek
Member #4,191
January 2004
avatar

Quote:

What exactly is a "Doom style game"?

Surely the one that looks closest to Doom 3. ;D

Quote:

I assume I can't just make an engine that loads the actual Duke Nukem 3D levels and art, that would be a little unfair. Although it would definitely pass the 30 minutes gameplay thing;D

I think you forgot about small think called game logic. ;)

Thomas Harte
Member #33
April 2000
avatar

Quote:

What exactly is a "Doom style game"?

I was thinking overwhelmingly of engines that use vertical slithers but in contrast to the Wolfenstein category offer height variations and/or non-orthogonal walls. I'll add some guidance as to the intended meaning but as with any other competition rule it means exactly as much or as little as the judges decide.

Quote:

I'm a little confused about the uniform ray rule, does it mean I can't make mirrors by bouncing rays? Can I do per-slither lighting by casting rays from nearby lights to the current slither? Can I do Quake 3 style teleporters that you can see through?

Think of it as though the rays you are casting need to have uniform 'height' and 'width' in your game world. They can then bounce around or jump position (as per my example of a relative sector world above) if they like. The point is to restrict a proliferation of arbitrarily sized rays which could be argued to be how a BSP based front to back polygon filler composes its scene without restricting people to rays of zero volume.

Quote:

P.P.S. I assume I can't just make an engine that loads the actual Duke Nukem 3D levels and art, that would be a little unfair.

Newest formulation of the rule in question, to answer your question:

"Entries must be substantially the work of the person or team submitting"

Do as little or as much as you feel the judges will tolerate!



Go to: