How can I correctly pass 2 vertices instead of all 4 for a quad to a vertex shader?

Question

If I am rendering quads, but all the quads will be axis-aligned (that is, their plane is always parallel to either the X Y or Z plane), I thought I could cut vertex video memory usage in half by passing opposite corners (6 floats) instead of all corners (12 floats) to the vertex shader per instance. Provided to the shader would be a buffer of these opposing corners and a per-instance vertex ID which would be from [0, 4).

There are 3 orderings for vertices in a quad, which I call C, Z, and X, where C is the most standard. This determine which vertex ID corresponds to which corner. Here are some graphs to illustrate the relationship between the vertex ID and the corresponding corner:

C:

3----2
     |
     |
0----1

Z:

2----3
 \
  \
   \
    \
0----1

X:

2----1
 \  /
  \/
  /\
 /  \
0    3

I would like to be able to, given only the ID and 2 vertices, determine the location in 3D space of the vertex corresponding to ID. If the planes are axis-aligned, I could pass a normal ID and use a switch statement or so in the shader but I would prefer to be able to do this implicitly. Since the planes are axis-aligned one of the coordinates in one of the points will equal the corresponding coordinate in the other plane.

I have thought about how I can arrange the data into a new vertex given only vertex-ID and 2 opposite points but I ran into a difficulty. For each of the 4 points, I either use an XYZ value from the low or high corner. I know that if I go with C, for example, if vertex ID is 0 the result will just be the lower vertex and if the ID is 2 the result will be the higher one.

But for the other 2, I will need to grab some values from the lower vertex and some from the higher vertex. But given only vertex ID, no matter what I try, I cannot seem to be able to produce a quad whose vertex order (C/Z/X) is consistent. For example if I make a table (l or h means the resulting vertex will have the corresponding coordinate from the low or high vertex respectively):

VID 0 1 2 3
Dim
0   l l h h
1   l h h l
2   l h l h

This does create squares with correct coordinates given the vertex ID and only 2 opposite corners corresponding to the square, but the issue is, if the square is X-aligned, the resulting vertex ordering is X-style, Y-aligned gives Z-style ordering, and Z-aligned gives C-style ordering. I need them to have consistent ordering.

I have thought about all these tables I could make about which (low/high) vertex we pick an XYZ coordinate from given the vertex ID, and there are only 4096 possibilities, and none of them seem to satisfy the requirements of giving a consistent vertex-ordering style. So this alone cannot solve the problem. I will need some other strategy.

This question is more theoretical than programmatic, but how can I, given only 2 opposing vertices and a vertex ID, get the Nth vertex corresponding of 4 vertices of a square described by the opposite vertices, where the resulting vertex-ordering is correct and consistent?

Answer 1

I'm going to ignore your commentary about the possible ordering of four supplied quad vertices, as I don't think it's relevant to the question.

The question(s) as I understand them, are:

(a) can you supply only two corner verticies of an axis-aligned 3d quad, and automatically determine the normal. (short answer: no, not in the general case)

(b) how can you generate the four vertices of an axis-aligned quad given the corner vertices when you know the normal?

(c) is this a worthwhile optimization of anything useful (short answer: probably not)

---

The reason you can't omit the quad-normal (or axis alignment) is that if the corner verticies happen to lie on two axis-aligned planes, you will have no way to disambiguate which one you wanted.

Imagine the (x,y,z) corner points (0,0,0) and (1,0,0)

Did you want a y-axis aligned plane or a z-axis aligned plane? There is no way to know without giving it the normal, because both the y and z coordinates match.

This becomes apparent when you generate the coordinates for the y-axis and z-axis aligned quads... because both of them share the two points above as corners.

y-axis quad : (0,0,0) (0,0,1) (1,0,0) (1,0,1) 
z-axis quad : (0,0,0) (0,1,0) (1,0,0) (1,1,0)

---

To generate the 4 corners of the axis-aligned quad given the normal, you are going to permutate the coordinates around the other axis. This becomes simpler if you think about it in 2d on the axis.

Given two 2d corners: (a,b) (c,d) 
The four corners are: (a,b) (a,d) (c,d) (c,b)

For example: (0,1) (2,3) -> (0,1) (0,3) (2,3) (2,1)

To do this in 3d, you simply add the 3rd coordinate for axis-alignment without changing it:

X-aligned: (X,a,b) (X,c,d) -> (X,a,b) (X,a,d) (X,c,d) (X,c,b)
Y-aligned: (a,Y,b) (c,Y,d) -> (a,Y,b) (a,Y,d) (c,Y,d) (c,Y,b)
Z-aligned: (a,b,Z) (c,d,Z) -> (a,b,Z) (z,d,Z) (c,d,Z) (c,b,Z)

---

The reason this probably isn't a useful optimization to do on 3d GPUs has to do with how GPUs handle conditionals.

In the GPU, if you put in a switch, which you must have to choose between the three axis alignment cases above, ALL GPU cores need to follow every branch of the switch, ignoring the cases that don't apply to them. This means you are running all three lines above on all GPU cores for all QUADS in your quad list. The GPU will run the vertex code faster if you supply the extra vertices so it doesn't have to run the conditional.

Also, by supplying the axis information in a packed form (one byte), you are going to unalign the entire quad vertex buffer. Instead of each Quad being 4x3x16bits, each quad will be 2x3x16bits + 8bits (axis). If you are just loading a buffer and sending it to the GPU it's probably fine but if your CPU is generating the quad-buffer, then the unaligned 16bit floats could potentially slow things down quite a bit in the CPU generation.

Are there situations where this could produce a speedup? Maybe.... If you have pre-calculated quad-buffers with extremely large numbers of only axis-aligned-quads, then you could reduce the size of those buffers substantially. You could even remove the axis-alignment byte, by instead supplying a per-draw-call list of three ints (# x-axis aligned, # y-axis aligned, # z-axis aligned) and then pre-order the quad-corner list so all the x-axis aligned quad are first, followed by y-axis-aligned, followed by z-axis aligned. This would basically make the size of your "axis aligned quad draw" buffer down by half, so for very large numbers of only axis aligned quads, that could be relevant.

However, I can't imagine the application for which this is relevant.

Voxel bricks can be drawn faster by using the GPU for the ray-marching of the voxel grid itself.

Further, even if you want to use the CPU to do it, voxel bricks are generally uniform size, so you don't need the flexibility of arbitrary corners, and can instead just supply the center point of the voxel and the face-number (1-6).