How can I generate a cube using JavaScript and this coordinate format?

Question

Given this code:

{
( 256 64 16 ) ( 256 64 0 ) ( 256 0 16 ) mmetal1_2 0 0 0 1 1
( 0 0 0 ) ( 0 64 0 ) ( 0 0 16 ) mmetal1_2 0 0 0 1 1
( 64 256 16 ) ( 0 256 16 ) ( 64 256 0 ) mmetal1_2 0 0 0 1 1
( 0 0 0 ) ( 0 0 16 ) ( 64 0 0 ) mmetal1_2 0 0 0 1 1
( 64 64 0 ) ( 64 0 0 ) ( 0 64 0 ) mmetal1_2 0 0 0 1 1
( 0 0 -64 ) ( 64 0 -64 ) ( 0 64 -64 ) mmetal1_2 0 0 0 1 1
}

How can I generate a cube using JavaScript (or any additional library) and the coordinates above? The code above should be interpreted as follows:

In the example shown here, this brush is a 6 sided cuboid. The plane of its first face is defined by 3 points, ( 256 64 16 ) ( 256 64 0 ) ( 256 0 16 ). The other information supplied is the texture used by the face. "mmetal1_2" is the name of the texture, a single plane may only have a single texture. "0 0 0 1 1" are how the texture is display, and are respectively "X offset" "Y offset" "Rotation" "X scale" and "Y scale".

The plane points ( p1 ) ( p2 ) ( p3 ) are interpreted as follows. The plane points must be arranged such that the cross product of the vectors (p3 - p1) and (p2 - p1) is not null, that is, the three points must be linearly independent. Then, the normalized cross product represents the normal vector of the plane. Every point p for which (p - p1) * normal <= 0 (where * is the dot product) holds is considered to be in the half space defined by the plane. Every other point is considered not to be in the half space.

Note #1: CSS can be used, if necessary.

Note #2: What I actually need here is the concept and the mathematical functions. I can extract the coordinates using a JavaScript loop, but I don't know how to initially approach this. I just need a nudge in the right direction.

Note #3: I only need the first three sets of values, not the texture and the offset.

Here are the specifications for this coordinates system: https://quakewiki.org/wiki/Quake_Map_Format

Answer 1

The points (p1)(p2)(p3) define a plane in terms of a triangle that lies on the plane. The points are arranged so that the plane's normal (the normalized "cross product of the vectors (p3 - p1) and (p2 - p1)") points outward. We can define the plane in terms of the plane equation Ax+Bx+Cx+D=0 as follows:

   (A, B, C) = N = normalize(cross(p3-p1,p2-p1))
   D = -dot(p1,N)

The intersection of these planes forms a convex polyhedron. Finding this polyhedron involves finding the vertices of the intersection of the planes as one of the steps. The wiki article you mention links to a journal article explaining one way to generate these vertices.

The format you mention describes a convex polyhedron (convex polytope) using its half-space representation (or h-representation or h-rep). Since a given set of planes can describe many convex polyhedra, it's more likely you want to convert the minimal half-space representation of the convex polyhedron to its minimal vertex representation (or v-representation or v-rep). Here, a minimal representation is one whose vertices intersect at least three planes but describe a solid that intersects all the half-spaces. Then, you need to generate the convex hull of the minimal vertex representation.

---

Since the question requests more detail, I will add it:

Generating a mesh of the polyhedron involves the following steps.

1. For each set of plane points (p1)(p2)(p3), find the coefficients of the plane equation, as defined above.
2. Find the set of points that intersect three or more planes. This is done by checking whether each set of three planes intersects in a point. The result will generally be many more points than there are vertices in the final polyhedron, so now we need to cull them.
3. For each point, check whether that point is inside all of the planes. More specifically, a point is inside a plane if D+dot(P,N) <= 0, where D and N are the plane's parameters as given above, and P is the point in question. Only points that are inside all the planes are kept.
4. Eliminate duplicate points. Duplicates usually indicate that more than three planes intersect in the same point.
5. The final step is to generate the convex hull of the points. Algorithms such as QuickHull can be useful here. The result will be a convex polyhedron with each face a convex polygon. If necessary, each face of the polyhedron can be triangulated using a relatively trivial procedure.

I have written code that implements this method.