GMLscripts.com

Discuss and collaborate on GML scripts
Invert

You are not logged in.

#1 2011-05-12 21:03:29

Daniel
Member
Registered: 2011-05-04
Posts: 25

Today I hijacked the zbuffer.

The infamous zbuffer gets hijacked every now and then, and today, I hijacked it to render voronoi regions in practically no time.

Download an example here, in .gm81, or just read (I prefer you read) the following.

I needed to generate a voronoi region, which means, for every point on the screen, set it's color to the color of the nearest "region" point. Voronoi regions are very helpful in many ways. For example, generate it, and you can determine the nearest instance simply by finding out which voronoi region you are in. This would make "nearest instance" calls VERY fast, then simply remove the region you checked, re-scan voronoi regions, and you've found the second closest point. Another very useful way to use it is for random map generators, if you need to have "countries" or something similar, it will generate countries of all shapes and sizes.

Anywho, they look like this:

voronoi.png

The way I generated that was simply by drawing cones into the screen with perspective turned off. This means for every pixel, the zbuffer determined the closest vertex, which happened to be the vertex of the cone of each region. So in other words, give every cone a different color, and the zbuffer will figure out which pixel is closest to which point.

The base of the cone needs to be very big, and the "depth" of the cone needs to be fairly high. As you can imagine, a low depth makes the cone have very unsteep edges, so zbuffer fighting occurs, but when the edges are very steep, the zbuffer has no problem figuring out which face to draw.

Last edited by Daniel (2011-05-20 14:59:09)

Offline

#2 2011-05-12 21:30:14

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Today I hijacked the zbuffer.

Brilliant lateral thinking, man. My hat is off to you for making the mental connection between Voronoi diagrams, intersecting cone boundaries, and the z-buffer. Seems obvious upon reflection, but that's what makes it great -- it's simple but not obvious at all.

I'm having trouble loading your example, but that's probably because the recent updates have broken GM8.1 in a few ways.

EDIT:

Actually, I've downloaded a 404 error page. hmmm

Last edited by xot (2011-05-12 21:40:03)


Abusing forum power since 1986.

Offline

#3 2011-05-20 02:44:06

xDanielx
Member
Registered: 2009-01-02
Posts: 38

Re: Today I hijacked the zbuffer.

Very clever!

Offline

#4 2011-05-20 14:59:24

Daniel
Member
Registered: 2011-05-04
Posts: 25

Re: Today I hijacked the zbuffer.

Fixed the link, thanks xot. smile

Offline

#5 2011-05-20 15:19:53

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Today I hijacked the zbuffer.

Hey, cool, it works now. That's really neat.


Abusing forum power since 1986.

Offline

#6 2011-05-26 07:40:53

Rani_sputnik
Member
Registered: 2011-04-24
Posts: 18

Re: Today I hijacked the zbuffer.

Lmao I literally just submitted the same thing to the script submission page! It would seem great minds think alike tongue Very nifty I'm downloading now to see if you have any little speed ups I can add to mine, haha.

I hope this isn't too topic hi-jacky-y but anyone care to speculate on a 3d voronoi grid of this nature? I'd be keen to hear ideas (because incidentally it's what I'm moving on to next). The problem with the depth buffer method is that you need a higher order of dimension because you are effectively taking cross sections in a strange way. To do the same thing in 3d you'd need some kind of voxel renderer or something... and that's where the breadcrumbs end...

Anyway, sorry for the sort-of-divergent conversation, great work man smile

Offline

#7 2011-05-28 01:24:03

xDanielx
Member
Registered: 2009-01-02
Posts: 38

Re: Today I hijacked the zbuffer.

I don't think you would want to use any buffer-filling approach to generate a 3D diagram. Even with with a good OpenCL implementation on a modern GPU, filling the 3D buffer would be orders of magnitude slower than filling a 2D buffer, and the RAM consumption could quickly go into the gigabytes.

It could work if you only need a low-resolution grid, but the traditional algorithms for generating Voronoi diagrams would be more flexible, since their time complexity is affected only by the number of regions and not by desired precision.

Offline

#8 2011-05-28 05:40:49

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Today I hijacked the zbuffer.

I have to agree that an analytical approach would be best. Voronoi diagrams are pretty simple to construct in 2D. I imagine a 3D analogue would not be a great deal more complicated. Constructing a polygonal representation of the volumes might be tricky (although Quake-era FPS map creation tools did this regularly), but BSP-tree traversal would make most other interactions quite simple.

I wonder what sort of practical uses a 3D Voronoi diagram would have.


Abusing forum power since 1986.

Offline

#9 2011-05-30 21:45:09

Rani_sputnik
Member
Registered: 2011-04-24
Posts: 18

Re: Today I hijacked the zbuffer.

I wonder what sort of practical uses a 3D Voronoi diagram would have.

It makes frieken sweet models! smile Also I'm thinking I would do some kind of destructible terrain thing with it, where that land is made up of point masses and the mesh is extracted from the points - similar to what you do with surface extraction in a liquid.

Yeah, most definitely a 3d 'raster' voxel thing (Is that what I should call it?) is a bad idea with conventional geometry, I agree now 100% I guess that's me desperately hoping for a way around doing math *sighs.

Offline

#10 2011-05-31 06:43:59

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Today I hijacked the zbuffer.

That's not a bad application. In fact, I think I read about a recent game using this approach for it's destructible environments ...

OK, here is the thing I was remembering. "Fragged", a December 2010 article in Game Developer magazine, discusses using 3D Voronoi diagrams for fragmenting 3D models. From the link below, the article begins on page 11 (page 9 of the magazine). I'm not sure this link is strictly legal, although I think it falls under educational fair use. Regardless, I'm sure any readers will get over it.

EDIT: New, legit, official link courtesy of Game Developer magazine.

http://twvideo01.ubm-us.net/o1/vault/GD … r_2010.pdf

Some other stuff.

This paper discusses the concept some, including voxelization of fragments.

http://guildhall.smu.edu/fileadmin/Mast … _Final.pdf

EDIT: Presumed mirror of the above paper.

https://www.smu.edu/~/media/Site/guildh … ashx?la=en

Last edited by xot (2015-10-03 19:05:16)


Abusing forum power since 1986.

Offline

#11 2015-10-01 08:25:38

Juju
Member
Registered: 2015-10-01
Posts: 43

Re: Today I hijacked the zbuffer.

Anyone have the original source? Long shot I know...

Offline

#12 2015-10-03 18:55:02

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Today I hijacked the zbuffer.

I believe this is an unaltered copy from the original post.

https://www.dropbox.com/s/3l9l5xj9shr4r … .gm81?dl=0

I've also fixed some links in my previous post.


Abusing forum power since 1986.

Offline

#13 2015-10-04 06:26:27

Juju
Member
Registered: 2015-10-01
Posts: 43

Re: Today I hijacked the zbuffer.

Wheee, thanks xot.

Offline

Board footer

Powered by FluxBB