BRL-CAD
Loading...
Searching...
No Matches
space_partition.h
Go to the documentation of this file.
1/* S P A C E _ P A R T I T I O N . H
2 * BRL-CAD
3 *
4 * Copyright (c) 1993-2025 United States Government as represented by
5 * the U.S. Army Research Laboratory.
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public License
9 * version 2.1 as published by the Free Software Foundation.
10 *
11 * This library is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this file; see the file named COPYING for more
18 * information.
19 */
20/** @file space_partition.h
21 *
22 */
23
24#ifndef RT_SPACE_PARTITION_H
25#define RT_SPACE_PARTITION_H
26
27#include "common.h"
28#include "vmath.h"
29#include "bu/malloc.h"
30#include "bn/tol.h"
31#include "rt/defines.h"
32#include "rt/application.h"
33#include "rt/soltab.h"
34
36
37struct rt_piecelist; /* forward declaration */
38
39/**
40 * Structures for space subdivision.
41 *
42 * cut_type is an integer for efficiency of access in rt_shootray() on
43 * non-word addressing machines.
44 *
45 * If a solid has 'pieces', it will be listed either in bn_list
46 * (initially), or in bn_piecelist, but not both.
47 */
48struct cutnode {
50 int cn_axis; /**< @brief 0, 1, 2 = cut along X, Y, Z */
51 fastf_t cn_point; /**< @brief cut through axis==point */
52 union cutter * cn_l; /**< @brief val < point */
53 union cutter * cn_r; /**< @brief val >= point */
54};
55
56struct boxnode {
60 struct soltab **bn_list; /**< @brief bn_list[bn_len] */
61 size_t bn_len; /**< @brief # of solids in list */
62 size_t bn_maxlen; /**< @brief # of ptrs allocated to list */
63 struct rt_piecelist *bn_piecelist; /**< @brief [] solids with pieces */
64 size_t bn_piecelen; /**< @brief # of piecelists used */
65 size_t bn_maxpiecelen; /**< @brief # of piecelists allocated */
66};
67
68
69#define CUT_CUTNODE 1
70#define CUT_BOXNODE 2
71#define CUT_MAXIMUM 2
72union cutter {
74 union cutter *cut_forw; /**< @brief Freelist forward link */
75 struct cutnode cn;
76 struct boxnode bn;
77};
78
79
80#define CUTTER_NULL ((union cutter *)0)
81
82/**
83 * Print out a cut tree.
84 *
85 * lvl is recursion level.
86 */
87RT_EXPORT extern void rt_pr_cut(const union cutter *cutp,
88 int lvl);
89
90struct rt_i; /*forward declaration */
91struct resource; /*forward declaration */
92struct soltab; /*forward declaration */
93RT_EXPORT extern void rt_pr_cut_info(const struct rt_i *rtip,
94 const char *str);
95RT_EXPORT extern void remove_from_bsp(struct soltab *stp,
96 union cutter *cutp,
97 struct bn_tol *tol);
98RT_EXPORT extern void insert_in_bsp(struct soltab *stp,
99 union cutter *cutp);
100RT_EXPORT extern void fill_out_bsp(struct rt_i *rtip,
101 union cutter *cutp,
102 struct resource *resp,
103 fastf_t bb[6]);
104
105/**
106 * Add a solid into a given boxnode, extending the lists there. This
107 * is used only for building the root node, which will then be
108 * subdivided.
109 *
110 * Solids with pieces go onto a special list.
111 */
112RT_EXPORT extern void rt_cut_extend(union cutter *cutp,
113 struct soltab *stp,
114 const struct rt_i *rtip);
115
116/**
117 * Return pointer to cell 'n' along a given ray. Used for debugging
118 * of how space partitioning interacts with shootray. Intended to
119 * mirror the operation of rt_shootray(). The first cell is 0.
120 */
121RT_EXPORT extern const union cutter *rt_cell_n_on_ray(struct application *ap,
122 int n);
123/*
124 * The rtip->rti_CutFree list can not be freed directly because is
125 * bulk allocated. Fortunately, we have a list of all the
126 * bu_malloc()'ed blocks. This routine may be called before the first
127 * frame is done, so it must be prepared for uninitialized items.
128 */
129RT_EXPORT extern void rt_cut_clean(struct rt_i *rtip);
130
131
132#ifdef USE_OPENCL
133struct clt_bvh_bounds {
134 cl_double p_min[3], p_max[3];
135};
136
137struct clt_linear_bvh_node {
138 struct clt_bvh_bounds bounds;
139 union {
140 cl_int primitives_offset; /* leaf */
141 cl_int second_child_offset; /* interior */
142 } u;
143 cl_ushort n_primitives; /* 0 -> interior node */
144 cl_uchar axis; /* interior node: xyz */
145 cl_uchar pad[1]; /* ensure 32 byte total size */
146};
147
148
149RT_EXPORT extern void
153#endif
154
155
157
158#endif /* RT_SPACE_PARTITION_H */
159
160/*
161 * Local Variables:
162 * tab-width: 8
163 * mode: C
164 * indent-tabs-mode: t
165 * c-file-style: "stroustrup"
166 * End:
167 * ex: shiftwidth=4 tabstop=8
168 */
Definition dvec.h:74
Header file for the BRL-CAD common definitions.
void float float int * n
Definition tig.h:74
double fastf_t
fastest 64-bit (or larger) floating point type
Definition vmath.h:334
void rt_cut_clean(struct rt_i *rtip)
void rt_pr_cut_info(const struct rt_i *rtip, const char *str)
void rt_cut_extend(union cutter *cutp, struct soltab *stp, const struct rt_i *rtip)
const union cutter * rt_cell_n_on_ray(struct application *ap, int n)
void rt_pr_cut(const union cutter *cutp, int lvl)
void insert_in_bsp(struct soltab *stp, union cutter *cutp)
void remove_from_bsp(struct soltab *stp, union cutter *cutp, struct bn_tol *tol)
void fill_out_bsp(struct rt_i *rtip, union cutter *cutp, struct resource *resp, fastf_t bb[6])
Definition tol.h:72
struct rt_piecelist * bn_piecelist
[] solids with pieces
fastf_t bn_max[3]
struct soltab ** bn_list
bn_list[bn_len]
fastf_t bn_min[3]
size_t bn_len
# of solids in list
size_t bn_maxpiecelen
# of piecelists allocated
size_t bn_maxlen
# of ptrs allocated to list
size_t bn_piecelen
# of piecelists used
fastf_t cn_point
cut through axis==point
int cn_axis
0, 1, 2 = cut along X, Y, Z
union cutter * cn_r
val >= point
union cutter * cn_l
val < point
union cutter * cut_forw
Freelist forward link.
struct boxnode bn
struct cutnode cn
fundamental vector, matrix, quaternion math macros