Blender
V3.3
|
#include <ctype.h>
#include <float.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "MEM_guardedalloc.h"
#include "DNA_meta_types.h"
#include "DNA_object_types.h"
#include "DNA_scene_types.h"
#include "BLI_listbase.h"
#include "BLI_math.h"
#include "BLI_memarena.h"
#include "BLI_string_utils.h"
#include "BLI_utildefines.h"
#include "BKE_global.h"
#include "BKE_displist.h"
#include "BKE_mball_tessellate.h"
#include "BKE_object.h"
#include "BKE_scene.h"
#include "DEG_depsgraph.h"
#include "DEG_depsgraph_query.h"
#include "BLI_strict_flags.h"
Go to the source code of this file.
Classes | |
struct | corner |
struct | cube |
struct | cubes |
struct | centerlist |
struct | edgelist |
struct | intlist |
struct | intlists |
struct | Box |
struct | MetaballBVHNode |
struct | process |
Macros | |
#define | MBALL_ARRAY_LEN_INIT 4096 |
#define | L 0 /* Left direction: -x, -i. */ |
#define | R 1 /* Right direction: +x, +i. */ |
#define | B 2 /* Bottom direction: -y, -j. */ |
#define | T 3 /* Top direction: +y, +j. */ |
#define | N 4 /* Near direction: -z, -k. */ |
#define | F 5 /* Far direction: +z, +k. */ |
#define | LBN 0 /* Left bottom near corner. */ |
#define | LBF 1 /* Left bottom far corner. */ |
#define | LTN 2 /* Left top near corner. */ |
#define | LTF 3 /* Left top far corner. */ |
#define | RBN 4 /* Right bottom near corner. */ |
#define | RBF 5 /* Right bottom far corner. */ |
#define | RTN 6 /* Right top near corner. */ |
#define | RTF 7 /* Right top far corner. */ |
#define | HASHBIT (5) |
#define | HASHSIZE (size_t)(1 << (3 * HASHBIT)) |
#define | HASH(i, j, k) ((((((i)&31) << 5) | ((j)&31)) << 5) | ((k)&31)) |
#define | MB_BIT(i, bit) (((i) >> (bit)) & 1) |
#define | LB 0 /* left bottom edge */ |
#define | LT 1 /* left top edge */ |
#define | LN 2 /* left near edge */ |
#define | LF 3 /* left far edge */ |
#define | RB 4 /* right bottom edge */ |
#define | RT 5 /* right top edge */ |
#define | RN 6 /* right near edge */ |
#define | RF 7 /* right far edge */ |
#define | BN 8 /* bottom near edge */ |
#define | BF 9 /* bottom far edge */ |
#define | TN 10 /* top near edge */ |
#define | TF 11 /* top far edge */ |
Typedefs | |
typedef struct corner | CORNER |
typedef struct cube | CUBE |
typedef struct cubes | CUBES |
typedef struct centerlist | CENTERLIST |
typedef struct edgelist | EDGELIST |
typedef struct intlist | INTLIST |
typedef struct intlists | INTLISTS |
typedef struct Box | Box |
typedef struct MetaballBVHNode | MetaballBVHNode |
typedef struct process | PROCESS |
Functions | |
static int | vertid (PROCESS *process, const CORNER *c1, const CORNER *c2) |
static void | add_cube (PROCESS *process, int i, int j, int k) |
static void | make_face (PROCESS *process, int i1, int i2, int i3, int i4) |
static void | converge (PROCESS *process, const CORNER *c1, const CORNER *c2, float r_p[3]) |
static void | make_box_union (const BoundBox *a, const Box *b, Box *r_out) |
static void | make_box_from_metaelem (Box *r, const MetaElem *ml) |
static unsigned int | partition_mainb (MetaElem **mainb, unsigned int start, unsigned int end, unsigned int s, float div) |
static void | build_bvh_spatial (PROCESS *process, MetaballBVHNode *node, unsigned int start, unsigned int end, const Box *allbox) |
static float | densfunc (const MetaElem *ball, float x, float y, float z) |
static float | metaball (PROCESS *process, float x, float y, float z) |
static void | freepolygonize (PROCESS *process) |
static void | docube (PROCESS *process, CUBE *cube) |
static CORNER * | setcorner (PROCESS *process, int i, int j, int k) |
static int | nextcwedge (int edge, int face) |
static int | otherface (int edge, int face) |
static void | makecubetable (void) |
void | BKE_mball_cubeTable_free (void) |
static int | setcenter (PROCESS *process, CENTERLIST *table[], const int i, const int j, const int k) |
static void | setedge (PROCESS *process, int i1, int j1, int k1, int i2, int j2, int k2, int vid) |
static int | getedge (EDGELIST *table[], int i1, int j1, int k1, int i2, int j2, int k2) |
static void | addtovertices (PROCESS *process, const float v[3], const float no[3]) |
static void | vnormal (PROCESS *process, const float point[3], float r_no[3]) |
static void | next_lattice (int r[3], const float pos[3], const float size) |
static void | prev_lattice (int r[3], const float pos[3], const float size) |
static void | closest_latice (int r[3], const float pos[3], const float size) |
static void | find_first_points (PROCESS *process, const unsigned int em) |
static void | polygonize (PROCESS *process) |
static void | init_meta (Depsgraph *depsgraph, PROCESS *process, Scene *scene, Object *ob) |
void | BKE_mball_polygonize (Depsgraph *depsgraph, Scene *scene, Object *ob, ListBase *dispbase) |
Variables | |
static INTLISTS * | cubetable [256] |
static char | faces [256] |
static int | corner1 [12] |
static int | corner2 [12] |
static int | leftface [12] |
static int | rightface [12] |
Definition at line 263 of file mball_tessellate.c.
Definition at line 514 of file mball_tessellate.c.
Definition at line 513 of file mball_tessellate.c.
Definition at line 266 of file mball_tessellate.c.
#define HASH | ( | i, | |
j, | |||
k | |||
) | ((((((i)&31) << 5) | ((j)&31)) << 5) | ((k)&31)) |
Definition at line 285 of file mball_tessellate.c.
#define HASHBIT (5) |
the LBN corner of cube (i, j, k), corresponds with location (i-0.5)*size, (j-0.5)*size, (k-0.5)*size)
Definition at line 281 of file mball_tessellate.c.
Hash table size (32768).
Definition at line 283 of file mball_tessellate.c.
BASED AT CODE (but mostly rewritten) : C code from the article "An Implicit Surface Polygonizer" by Jules Bloomenthal jbloo in "Graphics Gems IV", Academic Press, 1994 m@be auty. gmu. edu
Authored by Jules Bloomenthal, Xerox PARC. Copyright (c) Xerox Corporation, 1991. All rights reserved. Permission is granted to reproduce, use and distribute this code for any and all purposes, provided that this notice appears in all copies.
Definition at line 261 of file mball_tessellate.c.
Definition at line 505 of file mball_tessellate.c.
Definition at line 268 of file mball_tessellate.c.
Definition at line 267 of file mball_tessellate.c.
Definition at line 508 of file mball_tessellate.c.
Definition at line 507 of file mball_tessellate.c.
Definition at line 506 of file mball_tessellate.c.
Definition at line 270 of file mball_tessellate.c.
Definition at line 269 of file mball_tessellate.c.
#define MB_BIT | ( | i, | |
bit | |||
) | (((i) >> (bit)) & 1) |
Definition at line 287 of file mball_tessellate.c.
#define MBALL_ARRAY_LEN_INIT 4096 |
Definition at line 42 of file mball_tessellate.c.
Definition at line 265 of file mball_tessellate.c.
Definition at line 262 of file mball_tessellate.c.
Definition at line 509 of file mball_tessellate.c.
Definition at line 272 of file mball_tessellate.c.
Definition at line 271 of file mball_tessellate.c.
Definition at line 512 of file mball_tessellate.c.
Definition at line 511 of file mball_tessellate.c.
Definition at line 510 of file mball_tessellate.c.
Definition at line 274 of file mball_tessellate.c.
Definition at line 273 of file mball_tessellate.c.
Definition at line 264 of file mball_tessellate.c.
Definition at line 516 of file mball_tessellate.c.
Definition at line 515 of file mball_tessellate.c.
typedef struct centerlist CENTERLIST |
typedef struct MetaballBVHNode MetaballBVHNode |
Adds cube at given lattice position to cube stack of process.
Definition at line 1036 of file mball_tessellate.c.
References BLI_memarena_alloc(), process::centers, cube::corners, cubes::cube, process::cubes, cube::i, cube::j, cube::k, MB_BIT, cubes::next, process::pgn_elements, setcenter(), and setcorner().
Referenced by docube(), and find_first_points().
Adds a vertex, expands memory if needed.
Definition at line 933 of file mball_tessellate.c.
References process::co, copy_v3_v3(), process::curvertex, MBALL_ARRAY_LEN_INIT, MEM_reallocN, process::no, process::totvertex, UNLIKELY, and v.
Referenced by vertid().
Definition at line 820 of file mball_tessellate.c.
References cubetable, intlists::list, MEM_freeN, intlist::next, intlists::next, and NULL.
Referenced by BlendfileLoadingBaseTest::TearDown(), and WM_exit_ex().
void BKE_mball_polygonize | ( | Depsgraph * | depsgraph, |
Scene * | scene, | ||
Object * | ob, | ||
ListBase * | dispbase | ||
) |
Definition at line 1374 of file mball_tessellate.c.
References Freestyle::a, process::allbb, BLI_addtail(), BLI_memarena_new(), BLI_MEMARENA_STD_BUFSIZE, build_bvh_spatial(), process::co, process::converge_res, process::curindex, process::curvertex, DAG_EVAL_RENDER, Object::data, DEG_get_mode(), process::delta, depsgraph, DL_INDEX4, MetaBall::flag, freepolygonize(), G, G_TRANSFORM_EDIT, G_TRANSFORM_OBJ, DispList::index, process::indices, init_meta(), Box::max, MB_UPDATE_FAST, MB_UPDATE_HALFRES, MB_UPDATE_NEVER, MEM_callocN, MEM_reallocN, process::metaball_bvh, Box::min, process::no, normalize_v3(), DispList::nors, DispList::nr, DispList::parts, process::pgn_elements, polygonize(), MetaBall::rendersize, Object::scale, scene, process::size, process::thresh, MetaBall::thresh, process::totelem, process::totindex, process::totvertex, DispList::type, DispList::verts, and MetaBall::wiresize.
Referenced by BKE_displist_make_mball().
|
static |
Recursively builds a BVH, dividing elements along the middle of the longest axis of allbox.
Definition at line 188 of file mball_tessellate.c.
References MetaElem::bb, BLI_memarena_alloc(), process::bvh_queue_size, INIT_MINMAX, process::mainb, make_box_from_metaelem(), make_box_union(), Box::max, Box::min, node, NULL, partition_mainb(), and process::pgn_elements.
Referenced by BKE_mball_polygonize().
Definition at line 1073 of file mball_tessellate.c.
References floorf, pos, r, and size().
Referenced by find_first_points().
|
static |
Given two corners, computes approximation of surface intersection point between them. In case of small threshold, do bisection.
Definition at line 997 of file mball_tessellate.c.
References corner::co, process::converge_res, copy_v3_v3(), interp_v3_v3v3(), metaball(), and corner::value.
Referenced by vertid().
Computes density from given metaball at given position. Metaball equation is: (1 - r^2 / R^2)^3 * s
r = distance from center R = metaball radius s - metaball stiffness
Definition at line 300 of file mball_tessellate.c.
References ATTR_FALLTHROUGH, MetaElem::expx, MetaElem::expy, MetaElem::expz, MetaElem::imat, MetaElem::len, len_squared_v3(), MB_BALL, MB_CUBE, MB_ELIPSOID, MB_PLANE, MB_TUBE, MB_TUBEX, MB_TUBEY, MB_TUBEZ, mul_m4_v3(), MetaElem::rad2, MetaElem::s, MetaElem::type, x, y, and z.
Referenced by metaball().
triangulate the cube directly, without decomposition
Definition at line 584 of file mball_tessellate.c.
References add_cube(), corner1, corner2, cube::corners, count, cubetable, faces, cube::i, intlist::i, cube::j, cube::k, intlists::list, make_face(), MB_BIT, intlist::next, intlists::next, corner::value, and vertid().
Referenced by polygonize().
Find at most 26 cubes to start polygonization from.
Definition at line 1083 of file mball_tessellate.c.
References Freestyle::a, blender::bke::attribute_accessor_functions::add(), add_cube(), usdtokens::b(), MetaElem::bb, center, closest_latice(), copy_v3_v3_int(), DO_MIN, process::mainb, mid_v3_v3v3(), next_lattice(), prev_lattice(), setcorner(), process::size, corner::value, and BoundBox::vec.
Referenced by polygonize().
Definition at line 479 of file mball_tessellate.c.
References BLI_memarena_free(), process::bvh_queue, process::centers, process::corners, process::edges, process::mainb, MEM_freeN, and process::pgn_elements.
Referenced by BKE_mball_polygonize().
|
static |
Definition at line 906 of file mball_tessellate.c.
References HASH, edgelist::i1, i1, edgelist::i2, edgelist::j1, edgelist::j2, edgelist::k1, edgelist::k2, edgelist::next, NULL, t, and edgelist::vid.
Referenced by vertid().
|
static |
Iterates over ALL objects in the scene and all of its sets, including making all duplis (not only meta-elements). Copies meta-elements to process.mainb array. Computes bounding boxes for building BVH.
Definition at line 1163 of file mball_tessellate.c.
References process::allbb, ATTR_FALLTHROUGH, MetaElem::bb, BKE_object_visibility(), BKE_scene_base_iter_next(), BLI_memarena_alloc(), BLI_split_name_num(), copy_m4_m4(), copy_v3_fl3(), copy_v3_v3(), Object::data, DEG_get_mode(), depsgraph, DO_MINMAX, MetaBall::editelems, MetaBall::elems, MetaElem::expx, MetaElem::expy, MetaElem::expz, ListBase::first, MetaElem::flag, Base::flag_legacy, has_zero_axis_m4(), Object::id, MetaElem::imat, INIT_MINMAX, invert_m4_m4(), process::mainb, make_box_union(), MetaElem::mat, Box::max, MAX_ID_NAME, MB_BALL, MB_CUBE, MB_ELIPSOID, MB_HIDE, MB_NEGATIVE, MB_PLANE, MB_TUBE, process::mem, MEM_reallocN, Box::min, mul_m4_series, mul_m4_v3(), ID::name, MetaElem::next, NULL, OB_DUPLIFACES, OB_DUPLIVERTS, OB_FROMDUPLI, OB_MBALL, OB_VISIBLE_SELF, Object::obmat, Object::parent, process::pgn_elements, pos, MetaElem::quat, quat_to_mat4(), MetaElem::rad, MetaElem::rad2, rot, MetaElem::s, scene, STREQ, process::totelem, Object::transflag, MetaElem::type, Object::type, unit_m4(), UNLIKELY, BoundBox::vec, MetaElem::x, MetaElem::y, and MetaElem::z.
Referenced by BKE_mball_polygonize().
Definition at line 143 of file mball_tessellate.c.
References MetaElem::bb, copy_v3_v3(), r, and BoundBox::vec.
Referenced by build_bvh_spatial().
Definition at line 132 of file mball_tessellate.c.
References Freestyle::a, usdtokens::b(), Box::max, max_ff(), Box::min, and min_ff().
Referenced by build_bvh_spatial(), and init_meta().
Adds face to indices, expands memory if needed.
Definition at line 428 of file mball_tessellate.c.
References accumulate_vertex_normals_v3(), process::co, process::curindex, i1, process::indices, MBALL_ARRAY_LEN_INIT, MEM_reallocN, process::no, normal_quad_v3(), normal_tri_v3(), NULL, process::totindex, and UNLIKELY.
Referenced by docube().
create the 256 entry table for cubical polygonization
Definition at line 741 of file mball_tessellate.c.
References B, BF, BN, Freestyle::c, corner1, corner2, cubetable, e, ELEM, F, faces, intlist::i, L, LB, leftface, LF, intlists::list, LN, LT, MB_BIT, MEM_callocN, N, intlist::next, intlists::next, nextcwedge(), NULL, otherface(), pos, R, RB, RF, rightface, RN, RT, T, TF, and TN.
Referenced by polygonize().
Computes density at given position form all meta-balls which contain this point in their box. Traverses BVH using a queue.
Definition at line 398 of file mball_tessellate.c.
References process::bvh_queue, densfunc(), process::metaball_bvh, node, process::thresh, x, y, and z.
Referenced by converge(), metaball_foreach_id(), metaball_free_data(), metaball_init_data(), setcorner(), and vnormal().
Definition at line 1060 of file mball_tessellate.c.
References ceil(), pos, r, and size().
Referenced by find_first_points(), and prev_lattice().
|
static |
|
static |
Definition at line 732 of file mball_tessellate.c.
References leftface, and rightface.
Referenced by makecubetable().
|
static |
Partitions part of process.mainb array [start, end) along axis s. Returns i, where centroids of elements in the [start, i) segment lie "on the right side" of div, and elements in the [i, end) segment lie "on the left"
Definition at line 155 of file mball_tessellate.c.
References MetaElem::bb, SWAP, and BoundBox::vec.
Referenced by build_bvh_spatial().
The main polygonization proc. Allocates memory, makes cubetable, finds starting surface points and processes cubes on the stack until none left.
Definition at line 1134 of file mball_tessellate.c.
References process::bvh_queue, process::bvh_queue_size, Freestyle::c, process::centers, process::corners, cubes::cube, process::cubes, docube(), process::edges, find_first_points(), HASHSIZE, makecubetable(), MEM_callocN, cubes::next, NULL, and process::totelem.
Referenced by BKE_mball_polygonize().
Definition at line 1066 of file mball_tessellate.c.
References next_lattice(), pos, r, and size().
Referenced by find_first_points().
|
static |
Inserts cube at lattice i, j, k into hash table, marking it as "done"
Definition at line 846 of file mball_tessellate.c.
References BLI_memarena_alloc(), HASH, centerlist::i, centerlist::j, centerlist::k, l, centerlist::next, BMLoop::next, NULL, and process::pgn_elements.
Referenced by add_cube().
return corner with the given lattice location set (and cache) its function value
Definition at line 662 of file mball_tessellate.c.
References BLI_memarena_alloc(), Freestyle::c, process::corners, float(), HASH, metaball(), NULL, process::pgn_elements, and process::size.
Referenced by add_cube(), and find_first_points().
|
static |
Sets vid of vertex lying on given edge.
Definition at line 873 of file mball_tessellate.c.
References BLI_memarena_alloc(), process::edges, HASH, edgelist::i1, i1, edgelist::i2, edgelist::j1, edgelist::j2, edgelist::k1, edgelist::k2, edgelist::next, process::pgn_elements, t, and edgelist::vid.
Referenced by vertid().
If it wasn't previously computed, does converge() and adds vertex to process.
Definition at line 969 of file mball_tessellate.c.
References addtovertices(), converge(), process::curvertex, process::edges, getedge(), corner::i, corner::j, corner::k, setedge(), v, vnormal(), and zero_v3().
Referenced by docube().
Computes normal from density field at given point.
Definition at line 953 of file mball_tessellate.c.
References process::delta, metaball(), and point.
Referenced by GeometryManager::device_update_mesh(), Mesh::pack_normals(), and vertid().
|
static |
|
static |
|
static |
Definition at line 518 of file mball_tessellate.c.
Referenced by BKE_mball_cubeTable_free(), docube(), and makecubetable().
|
static |
Definition at line 519 of file mball_tessellate.c.
Referenced by bevel_build_edge_polygons(), bevel_rebuild_existing_polygons(), BKE_mesh_validate_arrays(), BKE_pbvh_get_grid_updates(), BKE_pbvh_update_normals(), bm_face_array_calc_bounds(), bm_face_array_calc_unique_uv_coords(), bm_face_array_uv_rotate_fit_aabb(), bm_face_array_uv_scale_y(), bm_face_array_visit(), BM_faces_join(), BM_faces_join_pair(), bm_log_face_values_swap(), bm_log_faces_restore(), bm_log_faces_unmake(), BM_mesh_calc_edge_groups_as_arrays(), bm_mesh_calc_tessellation_with_partial__multi_threaded(), bm_mesh_calc_tessellation_with_partial__single_threaded(), bm_mesh_calc_uv_islands(), BM_mesh_intersect(), BM_mesh_normals_update_with_partial_ex(), bm_uuidwalk_rehash_facelinks(), BM_vert_collapse_faces(), bmo_connect_verts_exec(), bmo_create_cube_exec(), bmo_dissolve_faces_exec(), bmo_recalc_face_normals_array(), ccgSubSurf__allFaces(), ccgSubSurf__effectedFaceNeighbors(), docube(), ED_uvedit_pack_islands_multi(), ED_uvedit_selected_faces(), edbm_select_similar_region_exec(), Freestyle::WFillGrid::fillGrid(), Freestyle::WSFillGrid::fillGrid(), blender::io::obj::fixup_invalid_polygon(), get_selected_indices(), knife_find_line_hits(), makecubetable(), mesh_separate_arrays(), MOD_solidify_nonmanifold_modifyMesh(), multires_stitch_grids(), partialvis_update_bmesh(), partialvis_update_bmesh_faces(), pbvh_faces_node_nearest_to_ray(), pbvh_faces_node_raycast(), pbvh_update_normals_accum_task_cb(), QFLOW_quadriflow_remesh(), recalc_face_normals_find_index(), sculpt_undo_bmesh_push(), btConvexHullInternal::shrink(), subdiv_ccg_average_inner_grids_task(), subdiv_ccg_coord_to_ptex_coord(), subdiv_ccg_eval_regular_grid(), subdiv_ccg_eval_special_grid(), subdiv_ccg_init_faces_edge_neighborhood(), subdiv_ccg_init_faces_vertex_neighborhood(), subdiv_ccg_recalc_modified_inner_normal_task(), and blender::meshintersect::CDTArrangement< Arith_t >::~CDTArrangement().
|
static |