View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Marching cubes and edge detection with 3D edge detector

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

5 replies to this topic

### #1Martin Perry  Members

Posted 18 January 2014 - 07:10 AM

I have a question. If I run classic Marching Cubes i need to iterate all  voxels and calculate iso surface in them. That means I need to decompress my data to get RAW stream (or use compression, that allows random access. Most of those compressions, that also brings high ratios are slow to do in realtime.

So my thoughts. If I compress data with DCT (and Huffman, that is fast for decompress), I can detect edges in DCT domain (I have found this article about it http://www.sciencedirect.com/science/article/pii/S187770581106557X). So basicly, I compress each slice as single 2D image. During extraction, I do edge detection in DCT. Than I got point cloud of edge points. On this, I run triangulation. Now, points from edges are in grid and most likely if point at [x,y] is edge, one of its neighbour will be detected as edge as well. I connect those points in a similar way as Marching Cube does.

Its just idea, I dont tested it. I would like to discuss, if it is possible and also see some remarks on my approach (or if it is totally stupid :-))

Thank you

### #2Ryan_001  Prime Members

Posted 18 January 2014 - 06:06 PM

You don't need to have the entire voxel space in memory to run a MC algorithm over it.  In my own implementation I used 2D slices, so if the volume was WxHxD the total memory requirement at any one point in time was only 3xWxH.  At each point I needed the point previous and the point ahead along all 3 axis.  3 2D slices was the minimum (well you could get by with a little less) I needed to store without recalculating (in your case uncompressing) a point more than once.

Edited by Ryan_001, 18 January 2014 - 06:13 PM.

### #3Martin Perry  Members

Posted 19 January 2014 - 02:24 AM

Yes.. but i still need to transfer data from HDD to RAM (or VRAM). If they are uncompressed, its bottleneck. Plus if compressed, i need to uncompress DCT to RAW data. So extraction directly from DCT domain would be faster.

### #4Ryan_001  Prime Members

Posted 19 January 2014 - 03:51 PM

If we're talking about the normal DCT/IDTC used in image processing (aka jpeg) then its not a memory issue.  In jpeg (or mpeg) the data is uncompressed from either a Huffman or arithmetic encoded entropy stream into its quantanized coefficients.  The coefficients take up as much space as the final output.  So unless you plan to do the entropy decode on the video card (not entirely impossible in theory, though not easy I'd imagine), you're not saving much by working directly on the DCT coefficients as opposed to the post transform data.

In the paper they are clearly performing the edge detection on the uncompressed coefficients, and not on the compressed/entropy encoded data stream.  The IDCT transform is so fast compared to all the other operations that occur its kinda a non-issue IMO.

You mention a few things though that might imply you don't fully understand the question.  Not trying to be antagonistic (tone is very hard to convey in writing).  The discreet cosine transform (like that used in jpeg or mpeg) in and of itself does not perform compression.  I'll describe it briefly but you may want to google about jpeg, pictures can really make it easier to understand.

The original source image data (you called it RAW I think) in pixels is divided into 8x8 blocks (merely for ease of computation, the DCT can use blocks of any size, but 8x8 is the de-factor standard).  Each pixel in the 8x8 block is a single 8-bit byte (in the case of color images each channel is compressed separately).  Each block is transformed by the forward discreet cosine transform, abbreviated to DCT.  The output of the forward DCT isn't any smaller, in fact it can be larger.  When I played around with the DCT (years ago) you could see that the result of the DCT would sometimes exceed the 8-bits of the source image, so an in-place transform would cause issues if this wasn't taken into account.  Some papers I read used pre-scaling, some did other methods (I was lazy and just used a floats as the intermediate), each method had its pros/cons.  Bottom line is though, you're not saving memory by doing the forward DCT.  The coefficients after the forward DCT are then quantanized, which reduces their magnitude and is the 'lossy' step of compression.  There are all sorts of various standard quantanization matricies, but in general they tend to favor the top left coefficients and throw out the bottom right coefficients.  After this the entropy encoding occurs.  This is the step that actually compresses the data, up till now you've actually made things larger/more difficult to work with.

### #5Martin Perry  Members

Posted 20 January 2014 - 02:08 AM

Thank you.

I know, that DCT does not reduce size of image and coefficients are larger (if not quantized). But main concenr is, that RLE / Huffman is fast to decompress on GPU. Plus if I didnt take 8x8 blocks and do DCT over full image resolution, I got better compression results, but IDCT is after that slower. Thats why I thought oc computing in DCT domain.

### #6Ryan_001  Prime Members

Posted 20 January 2014 - 04:30 PM

You can go slightly larger with the DCT.  I've played around with full image DCTs.  Problem is coefficient quantinization will cause obvious 'ringing' artifacts.  At large block sizes you can start to see the cosine waves as they propagate through the image.  You trade blockiness for ringing.  IMHO it wasn't a good trade-off.  Wavelets work much better if a high quality transform is what you're looking for, with all sorts to choose from with different properties.  For image compression they are pretty much superior in every way to the DCT.  Also wavelets are generally easier to analyse when it comes to things like edge detection, ect...  Though for 'ease of use' I'd just to the full decompress + transform and have the MC algorithm work with the final pixel data.

That said... do you think you can get a good huffman and/or arithmetic decoder + RLE expansion running quickly on a GPU?  The very nature of it would seem to suggest it would be difficult but to be honest I've never tried or read anything on it.  If you attempt it, post it up here somewhere I'd be curious on how it goes.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.