Optimal mesh format for dynamic point cloud?

Troubleshooting graphics
1

Hi all,
I’m intending to build a prototype for my game, and, after taking a quick glance, jME seems to be the most hassle-free (and out-of-the-box working) managed cross-platform engine that supports certain features I need.

For this (isometric) game, I have an idea of using point clouds for most objects and backdrops, since it allows to rotate camera arbitrarily while maintaining per-pixel geometric detail. Of course, ideally I’d use voxels, but I don’t think it’s a realistic option for most non-high-end hardware.

The idea is basically like this:

  • To reduce storage requirements, all components of point cloud vertices are stored as bytes (e.g. 3 bytes for XYZ, 1 byte for index in 256-color palette). This requires me to split objects into 256x256x256 blocks (and probably with a limit of 64k vertices per cloud), which is fine with me.
  • If it was only for rendering, I could just use separate buffers for each kind of vertex data. However, I’m also thinking to utilize point clouds for spatial queries, by sorting points in Morton order (Z-order curve - Wikipedia), which also gives me the ability to add/remove “voxels” in the array. For this purpose, I suppose, some sort of interleaved format would be the best, but I couldn’t find any examples on how to use interleaved formats in jME. Is it possible at all?

On an unrelated note: the “Search Forums” doesn’t seem to work for me, I keep getting a page with only “Google custom search Loading” text in it. Did anyone encounter the same problem?

2

Answering my own questions:

As of 2007, interleaved format does not work (http://hub.jmonkeyengine.org/forum/topic/vertex-array/). No idea if it became supported in the meantime, though.

Forum search, for some reason, works for me only in private window in Opera 21 browser (and doesn’t work in Firefox at all). Maybe this has something to do with the plugins I have there.

3

Forum search works fine for me. We’re just calling out to google anyway.

4

As to your original problem, you may need to explain more. It’s either something pretty clever or you are vastly underestimating what you will be throwing at the GPU. I can’t really tell for sure.

How big of a “thing” will your points represent? Do you have a picture of what you are trying to accomplish?

5

pspeed, thanks for the reply,

I found that “Google AJAX Search API” was among the widgets blocked by Ghostery plugin (I think I batch-blocked everything when installing it). My bad :slight_smile: The search started working in Firefox too after I whitelisted this widget.

In case my idea actually works, the points will represent objects (e.g. furniture, debris, etc.), characters, buildings and terrain. Since the view is isometric and the user won’t be able to zoom in/out, I can create all assets at predetermined resolution (e.g. I expect most characters to fit in 64 or even 32 pixel box). Something along these lines: http://www.miniwizardstudios.com/iso-chars.asp

And, since camera will rotate only in limited range (e.g. from top view to 45 degree view), there shouldn’t be too many objects or terrain/building blocks falling within the visible range.

Small objects/characters would each be represented by a single point cloud, and large objects (buildings, terrain) would be split into blocks. Since only the boundary “voxels” are actually stored, and most objects are approximately convex, I expect the overdraw to not be too high.
So, even at 1280x1080 resolution (~1.4 megapixels) I am probably looking at rendering about 7 million points per frame (without shadows, though) in worst case, which a relatively modern hardware should handle fine. Of course, since it’s going to look like pixel art anyway, I probably can get away with a lower screen resolution (maybe even 640x480 or 320x240).

I hope to keep in GPU memory only the subset of the world that’s relatively close to the camera view, while loading/unloading other objects in background.

I’m also having an idea of using the point clouds in roughly the same way as sparse voxel octrees – e.g. for collision detection (I don’t have much experience in this field, but I heard that it’s possible), and maybe also for in-game “voxel” editing. So, in case I would ever get to modifying point clouds in-game, I was wondering if there’s a way to use a single mesh buffer (merely as an optimization) to store all the points’ attributes :slight_smile:

Is this a sufficient explanation of what I’m trying to accomplish, or did you mean something else?

6

These statements seem to be at odds with one another:

@digl said: Of course, ideally I'd use voxels, but I don't think it's a realistic option for most non-high-end hardware.
@digl said: So, even at 1280x1080 resolution (~1.4 megapixels) I am probably looking at rendering about 7 million points per frame (without shadows, though) in worst case, which a relatively modern hardware should handle fine.

7 million points is a lot of points.

Moreover, a 64 x 64 x 64 cube is a lot of data. That’s a quarter of a million “cells” right there that you will need to store outright or compress in some way… and compression increases the time it takes to get it out and to the GPU again. And that’s just one object. I don’t know if oct trees will really help overcome all of the issues here.

I’m sure it will be an interesting experiment, though.

7

Well, from what I’ve read, as far as in 2002 pure point performance was already at 136 million vertices per second (GeForce4), so for more recent GPUs the number should be even higher.
However, 1280x1080 is actually a stretch – I don’t plan to use such high resolution (most importantly because of space/bandwidth requirements), so actual point count would be much lower. I just imagined a case when someone still wants to play pixel-arty game in full HD – but then, (s)he should probably have the hardware to back it up :slight_smile:

64x64x64 cube is a quarter of a million cells – but for most objects, only a fraction of these cells is ever visible (the boundary ones). So, there’s really no need for compression, I’m just going to store boundary points in an interleaved vertex buffer, or a set of separate vertex buffers for each kind of vertex attrribute.
In my scheme, I’ll need to store at least 4 bytes per point, but I hope that certain tricks (e.g. per-object palettes) would give an opportunity to re-use the same vertex buffers for visually different objects.

On a side note, octrees generally offer much better compression than point clouds (no need to explicitly store position for voxels), but their use requires clever data structures and algorithms. Here I stick to plain old vertices, it’s just that they can be sorted in a way that permits spatial searches with log(n) complexity.

Yup, that’s about it – for now I’m just going to experiment and figure out what works :slight_smile:

8

Just a note: 136 million vertexes per second

…is only 2.3 million vertexes per frame for 60 FPS.

Points have the issue that every one will hit both the vertex and the fragment shader so a lot of the optimization tricks that the card can do sort of go out the window. Just something to think about.

9

Well, here are some results of my experiments. (Screenshot)

I’ve found a sufficiently big model on blendswap (“port town”) and wrote a number of scripts to “voxelize” it (render slices in Blender, combine slices into an octree). The polygon model to octree conversion took about 2-3 days of computation on my PC. To test the performance, I used Unity3D (since I know it quite well already); the octree is converted at startup to ~150 point cloud objects, ~10M points total. Of course, it’s quite non-optimal (e.g. a large portion of points is never supposed to be seen, so they could be safely removed in theory), thus I’m not sure if the same conclusions will apply to optimal models. Also, this town is uncharacteristic in the sense that there are lots of high buildings close together, which shouldn’t probably happen in an isometric game (they obscure most of the view and result in high overdraw).

Anyway. On my relatively new PC (CPU: AMD A10-6700 APU 3.70 GHz, GPU: AMD Radeon HD 8670D) 10M points (without any fancy effects, though) perform at about 30 FPS. On my old (2008) laptop with a relatively low-end on-board GPU, FPS for the 10M points is 3 (maybe in part due to insufficient amount of GPU memory, I haven’t verified exactly).

At the camera zooming that I expected the game to run, the voxelization resolution turned out to be too low to show no gaps at any angle, so for now I made points 3 pixels wide (alternatively, a screen-space in-filling algorithm can be used, I suppose). On one hand, this means no per-pixel detail; on the other hand, it reduces the amount of points rendered (~3M on average). After looking at it for a bit, I’m starting to consider that maybe static environment looks quite ok with non-per-pixel (but still uniform) detalization.

If anyone wants to run the test:
http://www73.zippyshare.com/v/91276184/file.html - linux build
http://www73.zippyshare.com/v/50670051/file.html - macos build
http://www73.zippyshare.com/v/33591860/file.html - windows build
Controls:
WASD - move character
Drag left mouse button - rotate camera
Mouse scroll - zoom in/out

So… for now, I can’t make a decisive conclusion on whether the performance/hardware balance satisfies my expectations. All in all, the time-proven 3D-polygon/2D-prerendered approaches, despite their respective restrictions, are much easier both in terms of performance and of modeling pipeline – so I’m not sure if the voxel/pointcloud style would be worth the trouble in the end.

10

How about a different approach?

Having tested the above demo, I would say that you could archive something very similar looking with normal models, and a shader.
Can you explain a bit more in detail why you want this with point vertexes?

11
@digl said: despite their respective restrictions

Yeah, I’m curious about this, too.

I don’t know of restrictions of the 3D polygon approach that isn’t just magnified exponentially in your point cloud version.

12

Basically, I’m trying to achieve a “made out of matter” look (points = elementary units of “matter”), versus the “infinitely thin cardboard toys” look of polygons. To achieve the same effect with polygons, one would need a per-pixel resolution both for meshes and for textures anyway. So baking everything to points would take less space, all in all.

The “restriction of polygons” is, basically, a single problematic case: if the model (or its part) has subpixel thickness (e.g. a cloth, anything smaller than a character’s hand, etc.), there’s a high chance that, during the rasterization, it would hit only a few disconnected pixels, or even none at all (thus causing an “appear-disappear” flicker). Points, on the other hand, will render no matter what. The only way to battle this effect in the polygonal system, as far as I can see, is to either explicitly take into account the minimal thickness when modeling, or to render everything at several times the screen resolution and then downsample (antialiasing is a nice bonus, though).

13

Hmm, after giving it a serious thought, I suppose certain tricks like GPU tesselation/geometry shaders and relief mapping would make subpixel detail possible without actually storing all that geometry (and textures in some cases can be reused). However, ambient occlusion would probably still be necessary to bake for every object individually.

14
@digl said: or to render everything at several times the screen resolution and then downsample

You just described the antia-aliasing built into every graphics card. Only they can do it even more efficiently, I guess.

On the other hand, there is no (easy) way to do proper antialiasing with your point cloud approach. Given your description it seems you will be aligning every point with screen pixels (or you’d have the exact same issue)… and that means all of your edges will be jagged. All of your “atoms” would have to pick one pixel or the other if they were spanning pixels.

With the polygon approach, there are always ways to add more detail. In the end, the more detail you add then it starts to approach being “as bad as particles”.

15

Honestly speaking, I didn’t intend to use antialiasing with pointclouds. Basically, I see it like that:

  1. Point clouds (alternatively, non-filtered voxels) have “oldskool pixel-arty” look.
  2. Antialiased hi-poly meshes with HD textures (alternatively, filtered voxels) have “high-end polished” look.
  3. Low-poly meshes (antialiased or not) have “made-out-of-cardboard stylized” look.
    These styles are all self-consistent (“what you see is what there is/what is meant”), and for a different game I would have probably sticked to the low-poly style without second thought. Unfortunately, I strongly feel that “cardboard stylization” won’t suit the mood of this project, so I have to consider less convenient options first.

Well, I suppose if I have any further progress, I’ll share the results again =)

16

…After two weeks of pondering, I have finally made up my mind.
In short, it seems that the GPUs that can render dense point cloud scenes in realtime, are, most likely, the GPUs that can do direct voxel raycasting/cone-tracing (via CUDA/OpenCL) or dynamic tesselation with comparable or better performance.
So the original question of this thread is probably rendered moot, since building a point-cloud-based game would be, in most cases, less practical than using a polygonal or voxel representation.

I guess I’ll have to bite the bullet and take either “pre-rendered 2.5D” or “polygonal stylized” route 8)