File: bih.h

package info (click to toggle)
darkplaces 0~20180412~beta1-2
  • links: PTS, VCS
  • area: main
  • in suites: buster
  • size: 18,200 kB
  • sloc: ansic: 176,886; makefile: 485; pascal: 455; perl: 372; objc: 245; sh: 102
file content (91 lines) | stat: -rw-r--r-- 2,511 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

// This code written in 2010 by Forest Hale (darkplacesengine gmail com), and placed into public domain.

// Based on information in http://zach.in.tu-clausthal.de/papers/vrst02.html (in particular vrst02_boxtree.pdf)

#ifndef BIH_H
#define BIH_H

#define BIH_MAXUNORDEREDCHILDREN 8

typedef enum biherror_e
{
	BIHERROR_OK, // no error, be happy
	BIHERROR_OUT_OF_NODES // could not produce complete hierarchy, maxnodes too low (should be roughly half of numleafs)
}
biherror_t;

typedef enum bih_nodetype_e
{
	BIH_SPLITX = 0,
	BIH_SPLITY = 1,
	BIH_SPLITZ = 2,
	BIH_UNORDERED = 3,
}
bih_nodetype_t;

typedef enum bih_leaftype_e
{
	BIH_BRUSH = 4,
	BIH_COLLISIONTRIANGLE = 5,
	BIH_RENDERTRIANGLE = 6
}
bih_leaftype_t;

typedef struct bih_node_s
{
	bih_nodetype_t type; // = BIH_SPLITX and similar values
	// TODO: store just one float for distance, and have BIH_SPLITMINX and BIH_SPLITMAXX distinctions, to reduce memory footprint and traversal time, as described in the paper (vrst02_boxtree.pdf)
	// TODO: move bounds data to parent node and remove it from leafs?
	float mins[3];
	float maxs[3];
	// node indexes of children (always > this node's index)
	int front;
	int back;
	// interval of children
	float frontmin; // children[0]
	float backmax; // children[1]
	// BIH_UNORDERED uses this for a list of leafindex (all >= 0), -1 = end of list
	int children[BIH_MAXUNORDEREDCHILDREN];
}
bih_node_t;

typedef struct bih_leaf_s
{
	bih_leaftype_t type; // = BIH_BRUSH And similar values
	float mins[3];
	float maxs[3];
	// data past this point is generic and entirely up to the caller...
	int textureindex;
	int surfaceindex;
	int itemindex; // triangle or brush index
}
bih_leaf_t;

typedef struct bih_s
{
	// permanent fields
	// leafs are constructed by caller before calling BIH_Build
	int numleafs;
	bih_leaf_t *leafs;
	// nodes are constructed by BIH_Build
	int numnodes;
	bih_node_t *nodes;
	int rootnode; // 0 if numnodes > 0, -1 otherwise
	// bounds calculated by BIH_Build
	float mins[3];
	float maxs[3];

	// fields used only during BIH_Build:
	int maxnodes;
	int error; // set to a value if an error occurs in building (such as numnodes == maxnodes)
	int *leafsort;
	int *leafsortscratch;
}
bih_t;

int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_node_t *nodes, int *temp_leafsort, int *temp_leafsortscratch);

int BIH_GetTriangleListForBox(const bih_t *bih, int maxtriangles, int *trianglelist_idx, int *trianglelist_surf, const float *mins, const float *maxs);

#endif