[Algorithms] Ellipsoid Engine used in game "Ecstatica": how its done?

[Andre Krause]

hello,

i recently re-discovered the game ecstatica from andrew spencer productions:

http://www.gamespot.com/pc/action/ecstatica2/images.html

my question is - how did he draw those ellipsoids that fast ? (ecstatica
1 was from 1994 and was quite impressive as compared with those low-poly
non-textured models in for example alone in the dark)

i can somehow imagine how to render fast, axis-aligned ellipsoids
including some z-buffer,
but i cant imagine how those ellipsoids could be rendered with a free
long axis. wouldn't this require a full matrix multiplication per pixel?
even with lookup tables for sin/cos i can imagine it would have been too
slow on 1994 hardware.

another question: how is collision detection done int alone-in-the-dark
style games with pre-rendered 3d-backgrounds? ok, visibilty check is
easy - just store a z-buffer. but how is collision with the pre-rendered
background done? did they store some kind 3d-z-buffer ? maybe with
voxels twice or 4 times the size of the pixel resolution? or did they
just define a bunch of bounding boxes?

third question/idea: would it be cool to make some pixelshader on modern
graphics card, implementing those ellipsoids and making a modern variant
of ecstatica? this would give some nice organic look. and with todays
hardware, one could maybe literally spit out millions of those ellipsoids..

[Michael Robb]

Back in those days, everything was done in software rendering.

It's fairly simple to scan-convert ellipsoids as the equation is simply:

A.x^2 + B.y^2 + C.z^2 + D.x + E.y + F.z + G.xy + H.xz + I.yz + J = 0

Blinn did a paper on rendering quadrics, cubic and quartic equations
using fragment shaders.

He constructs a bounding box around each primitive, then converts the
interpolated pixel position in world space into the starting point and
direction of the ray, which is then used to raytrace the selected
equation (calculating outward normal).

- Michael

[Andre Krause]

Post by Michael Robb
Back in those days, everything was done in software rendering.
A.x^2 + B.y^2 + C.z^2 + D.x + E.y + F.z + G.xy + H.xz + I.yz + J = 0
Blinn did a paper on rendering quadrics, cubic and quartic equations
using fragment shaders.
He constructs a bounding box around each primitive, then converts the
interpolated pixel position in world space into the starting point and
direction of the ray, which is then used to raytrace the selected
equation (calculating outward normal).

thanks! i also found a very nice article describing the method using GPU
to visualize molecules from 2006:

http://www.cs.princeton.edu/~tweyrich/projects/quadrics/pbg06.pdf

its very sophisticated, using deferred shadning, soft shadows and
shilouette rendering. very impressive supplementary video:

http://www.cs.princeton.edu/~tweyrich/projects/quadrics/pbg06_divx.avi

[Tobias Sicheritz]

Post by Andre Krause
i can somehow imagine how to render fast, axis-aligned ellipsoids
including some z-buffer,
but i cant imagine how those ellipsoids could be rendered with a free
long axis. wouldn't this require a full matrix multiplication per pixel?
even with lookup tables for sin/cos i can imagine it would have been too
slow on 1994 hardware.

Before floating point & matrices, fixed point integer was used mostly in
real-time computer graphics and Bresenham's life saving algorithms from the
60ies used only addition, subtraction and multiplication by constant (which is
done using bitwise-shifts).

http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
http://www.j3d.org/matrix_faq/curvfaq_latest.html#Q23


Tobi

Post by Andre Krause
hello,
http://www.gamespot.com/pc/action/ecstatica2/images.html
my question is - how did he draw those ellipsoids that fast ? (ecstatica
1 was from 1994 and was quite impressive as compared with those low-poly
non-textured models in for example alone in the dark)
i can somehow imagine how to render fast, axis-aligned ellipsoids
including some z-buffer,
but i cant imagine how those ellipsoids could be rendered with a free
long axis. wouldn't this require a full matrix multiplication per pixel?
even with lookup tables for sin/cos i can imagine it would have been too
slow on 1994 hardware.
another question: how is collision detection done int alone-in-the-dark
style games with pre-rendered 3d-backgrounds? ok, visibilty check is
easy - just store a z-buffer. but how is collision with the pre-rendered
background done? did they store some kind 3d-z-buffer ? maybe with
voxels twice or 4 times the size of the pixel resolution? or did they
just define a bunch of bounding boxes?
third question/idea: would it be cool to make some pixelshader on modern
graphics card, implementing those ellipsoids and making a modern variant
of ecstatica? this would give some nice organic look. and with todays
hardware, one could maybe literally spit out millions of those ellipsoids..
-------------------------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc.
Still grepping through log files to find problems? Stop.
Now Search log events and configuration files using AJAX and a browser.
Download your FREE copy of Splunk now >> http://get.splunk.com/
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

[c***@playstation.sony.com]

Post by Andre Krause
my question is - how did he draw those ellipsoids that fast ? (ecstatica
1 was from 1994 and was quite impressive as compared with those low-poly
non-textured models in for example alone in the dark)

I don't know for sure, but my understanding was that it was just a
bitmap with an ellipsoid on it, that was scaled/rotated to create
all other ellipsoids. But I could be wrong.


Christer Ericson
http://realtimecollisiondetection.net/blog/

[c***@playstation.sony.com]

Post by c***@playstation.sony.com

Post by Andre Krause
my question is - how did he draw those ellipsoids that fast ?

(ecstatica

Post by c***@playstation.sony.com

Post by Andre Krause
1 was from 1994 and was quite impressive as compared with those

low-poly

Post by c***@playstation.sony.com

Post by Andre Krause
non-textured models in for example alone in the dark)

I don't know for sure, but my understanding was that it was just a
bitmap with an ellipsoid on it, that was scaled/rotated to create
all other ellipsoids. But I could be wrong.

To corroborate what I said, here's an old news post from 1995 claiming the
same (which is probably where I first heard this was how they did it):

http://groups.google.com/group/comp.graphics.algorithms/msg/3af369af84b5cb7b?dmode=source&hl=en

Christer Ericson
http://realtimecollisiondetection.net/blog/

[Andre Krause]

Post by Andre Krause

Post by c***@playstation.sony.com

Post by Andre Krause
my question is - how did he draw those ellipsoids that fast ?

(ecstatica

Post by c***@playstation.sony.com

Post by Andre Krause
1 was from 1994 and was quite impressive as compared with those

low-poly

Post by c***@playstation.sony.com

Post by Andre Krause
non-textured models in for example alone in the dark)

I don't know for sure, but my understanding was that it was just a
bitmap with an ellipsoid on it, that was scaled/rotated to create
all other ellipsoids. But I could be wrong.

To corroborate what I said, here's an old news post from 1995 claiming the
http://groups.google.com/group/comp.graphics.algorithms/msg/3af369af84b5cb7b?dmode=source&hl=en
Christer Ericson
http://realtimecollisiondetection.net/blog/

thanks alot! this explains the impressive speed of ecstatica rendering
back in 1994.

and that z-depth offset associated with the stretched sphere image is a
neat idea. i think they used the same trick in super mario 64 for
rendering the bombs.