First. Lets write what do we know about each voxel :
voxel = (x, y, z, color) // or some other information
General way is simply this:
set of voxels = set of (x,y,z, color)
Note, that triplet (x,y,z) identify each voxel uniquely, since voxel is point in space and there is no way two points occupy one place (I believe we are talking about static voxel data).
It should be fine for simple data. But it is by no means a fast data structure.
Rendering is AFAIK done by scanline algorithm. Tom's Hardware article on voxels has image of scanline algorithm.
If fast lookup is needed, then the fastest data structure for lookup is hash (aka array, map ...). So You have to make hash out of it. So, naively we want just fastest way to get arbitrary element:
array [x][y][z] of (color)
This has O(1) for looking up voxel by x,y,z coordinates.
Problem is, that it's space requirements are O(D^3), where D is range of each x,y and z numbers (forget Real number, since if they were Chars, which have range of 256 values, there would be 256^3 = 2^24 == 16 777 216 elements in array).
But it depends on what You want to do with voxels. If rendering is what You want, then it is probably this array what You want. But problem of storage still remains ...
If storage is the problem
One method is to use RLE compression in the array. Imagine a slice of voxels (set of voxels, where voxels have one coordinate constant value .... like plane where z = 13 for example). Such slice of voxels would be looking like some simple drawing in MSPaint. Voxel model, I'd say, usually occupy fraction of all the possible places (D^3 space of all possible voxels). I believe, that "take a pair from triplet of coordinates and compress the remaining axis" would do the trick (for example take [x][y] and for each element compress the all voxels at z axis at given x,y ... there should be 0 to few elements, RLE would do fine here):
array [x][y] of RLE compressed z "lines" of voxel; each uncompressed voxel has color
Other method to solve storage problem would be instead of array using tree data structure:
tree data structure = recursively classified voxels
for octrees: recursively classified by which octant does voxel at (x,y,z) belong to
- Octree, as mentioned by Nick. It should compress voxels. Octree has even a decent speed for lookup, I guess it is some O(log N), where N is number of voxels.
- Octree should be able to store decently arbitrary voxel data.
If voxels are some simplistic heightmap You might store just that. Or You might store parameters to function which generates the heightmap, aka procedurally generate it ...
And of course You can combine all possible approaches. But don't overdo it, unless You test that Your code works and measure that it is REALLY faster (so it is worth the optimization).
Other than Octrees is RLE compression with voxels, google "voxlap", "ken silverman" ...
There is list of resources and discussion on how to make fast voxel renderer, includes papers and source code.