Re: BSP edge list

Bernd Kreimeier (Bernd.Kreimeier@NeRo.Uni-Bonn.DE)
Wed, 19 Jun 1996 09:52:49 +0200 (MET DST)

Date: Wed, 19 Jun 1996 09:52:49 +0200 (MET DST)
From: Bernd Kreimeier <Bernd.Kreimeier@NeRo.Uni-Bonn.DE>
Message-Id: <>
Subject: Re: BSP edge list

Greg Lewis wrote:
> And, thus I would only need to compute half of the
> vertices (since the start of one is the end of the next edge).

From: Jim Bucher <>
>So you should be able to transform the verticies in the vertex
>list and avoid transforming the same vertex twice.

Yep, a separate vertex transformation pass is a common approach.
Internally, the vertex is stored as

struct tVertex
// world space coordinates
float _x;
float _y;
float _z;

// transformed view space coordinates
float _tx;
float _ty;
float _tz;

or the likes. One could add the screen space coordinates as
well from perspective projection. However, this approach
clearly does not scale - you will transform all the vertices
in the world, even if only a few percent are actually within
the view frustrum or close.

You might maintain bool flags to indicate transformation has
already been done, or you might flag all vertices in the PVS,
and transform only those, or might transform all vertices in
the leafs of the BSP actually reached during traversal...
which would bring you back to your original problem.

Now and then I am considering a sorting of the vertex list
by leaf (roughly, not perfectly), with a first_vertex,
nOf_vertices pointer into the vertex list for each leaf
(will have to be overlapping). This is probably not worth
the trouble. Any other ideas?


P.S.: is there really a non-closed polygon? From the
description of Quake's rasterizer I knew that concave
polygons and holes are handled, but I cannot imagine
how this will work with non-closed polygons. Any examples?