[Bf-blender-cvs] [8f4c256c268] soc-2022-soft-bodies: First pass at the tetrahedralization code, there are some bugs present that need to be addressed. Currently the more pressing bug is wrong tet being returned by getContainingTet()
Aarnav Dhanuka
noreply at git.blender.org
Sun Jul 3 22:51:41 CEST 2022
Commit: 8f4c256c26842cdb8878bdb8256657fa5ca6f732
Author: Aarnav Dhanuka
Date: Mon Jul 4 01:46:41 2022 +0530
Branches: soc-2022-soft-bodies
https://developer.blender.org/rB8f4c256c26842cdb8878bdb8256657fa5ca6f732
First pass at the tetrahedralization code, there are some bugs present that need to be addressed. Currently the more pressing bug is wrong tet being returned by getContainingTet()
===================================================================
M source/blender/modifiers/intern/MOD_weld.cc
===================================================================
diff --git a/source/blender/modifiers/intern/MOD_weld.cc b/source/blender/modifiers/intern/MOD_weld.cc
index 93d4b56176c..ce1b02244bb 100644
--- a/source/blender/modifiers/intern/MOD_weld.cc
+++ b/source/blender/modifiers/intern/MOD_weld.cc
@@ -18,7 +18,17 @@
#include "BLI_array.hh"
#include "BLI_index_range.hh"
#include "BLI_span.hh"
+
+#include "BLI_math_vector.h"
+#include "BLI_utildefines.h"
+
#include "BLI_vector.hh"
+#include "BLI_math_vec_types.hh"
+#include "BLI_math_vector.hh"
+
+// #include "bmesh_construct.h"
+#include "bmesh.h"
+#include "bmesh_tools.h"
#include "BLT_translation.h"
@@ -36,6 +46,7 @@
#include "BKE_deform.h"
#include "BKE_modifier.h"
#include "BKE_screen.h"
+#include "BKE_mesh.h"
#include "UI_interface.h"
#include "UI_resources.h"
@@ -54,90 +65,539 @@ using blender::Array;
using blender::IndexMask;
using blender::Span;
using blender::Vector;
+using namespace blender;
+using namespace blender::math;
+// using namespace std;
-static Span<MDeformVert> get_vertex_group(const Mesh &mesh, const int defgrp_index)
-{
- if (defgrp_index == -1) {
- return {};
- }
- const MDeformVert *vertex_group = static_cast<const MDeformVert *>(
- CustomData_get_layer(&mesh.vdata, CD_MDEFORMVERT));
- if (!vertex_group) {
- return {};
+
+Vector<Vector<int>> tetFaces({{2,1,0}, {0,1,3}, {1,2,3}, {2,0,3}});
+float inf = 1000000000000;// C has no FLOAT_MAX :/
+
+static float randomEps(){
+ // Why are we using a random epsilon value?
+ return 0;
+}
+
+static bool isInside(Vector<float> vert){
+ return true;
+}
+
+// Used to populate a tets face normals and planesD
+static void setTetProperties(Vector<float3> &verts,
+ Vector<int> &tetVertId,
+ Vector<float3> &faceNormals,
+ Vector<float> &planesD,
+ int tetNr){
+ for(int i = 0; i<4; i++){
+ float3 p0 = verts[tetVertId[4*tetNr + tetFaces[i][0]]];
+ float3 p1 = verts[tetVertId[4*tetNr + tetFaces[i][1]]];
+ float3 p2 = verts[tetVertId[4*tetNr + tetFaces[i][2]]];
+
+ float3 normal = cross(p1 - p0, p2 - p0);
+ normal = normalize(normal);
+
+ faceNormals[4*tetNr + i] = normal;
+ planesD[4*tetNr + i] = dot(p0, normal);
}
- return {vertex_group, mesh.totvert};
}
-static Vector<int64_t> selected_indices_from_vertex_group(Span<MDeformVert> vertex_group,
- const int index,
- const bool invert)
-{
- Vector<int64_t> selected_indices;
- for (const int i : vertex_group.index_range()) {
- const bool found = BKE_defvert_find_weight(&vertex_group[i], index) > 0.0f;
- if (found != invert) {
- selected_indices.append(i);
+static int findContainingTet(Vector<float3> &verts,
+ Vector<int> &tetVertId,
+ Vector<int> &tetFaceNeighbors,
+ Vector<float3> &faceNormals,
+ Vector<float> &planesD,
+ int tetMarkId,
+ Vector<int> &tetMarks,
+ float3 currVert){
+
+ bool found = false;
+ int tetNr = 0;
+
+ while(tetNr < tetVertId.size()/4 && tetVertId[4*tetNr]<0)
+ tetNr++;
+
+ float3 center(0.0, 0.0, 0.0);
+ while(!found){
+ if(tetNr < 0 || tetMarks[tetNr] == tetMarkId){
+ break;
+ }
+
+ tetMarks[tetNr] = tetMarkId;
+
+ center = {0.0,0.0,0.0};
+ for(int i = 0; i<4; i++){
+ center += verts[tetVertId[4*tetNr + i]];
+ }
+ center*=0.25;
+
+ float minT = inf; //
+ int minFaceNr = -1;
+
+ for(int i = 0; i<4; i++){
+ float3 normal = faceNormals[4*tetNr + i];
+ float d = planesD[4*tetNr + i];
+
+ float hp = dot(normal, currVert) - d;
+ float hc = dot(normal, center) - d;
+
+ float t = hp - hc;
+ if(t == 0.0)
+ continue;
+
+ t = -hc/t;
+
+ if(t >= 0.0 && t < minT){
+ minT = t;
+ minFaceNr = i;
+ }
+ }
+
+ if(minT >= 1.0){
+ found = true;
+ }
+ else{
+ tetNr = tetFaceNeighbors[4*tetNr + minFaceNr];
}
}
- return selected_indices;
+
+ if(found)
+ return tetNr;
+ else
+ return -1;
}
-static Array<bool> selection_array_from_vertex_group(Span<MDeformVert> vertex_group,
- const int index,
- const bool invert)
-{
- Array<bool> selection(vertex_group.size());
- for (const int i : vertex_group.index_range()) {
- const bool found = BKE_defvert_find_weight(&vertex_group[i], index) > 0.0f;
- selection[i] = (found != invert);
+static float3 getCircumCenter(float3 p0, float3 p1, float3 p2, float3 p3){
+ float3 b = p1 - p0;
+ float3 c = p2 - p0;
+ float3 d = p3 - p0;
+
+ float det = 2.0 * (b.x*(c.y*d.z - c.z*d.y) - b.y*(c.x*d.z - c.z*d.x) + b.z*(c.x*d.y - c.y*d.x));
+ if (det == 0.0){
+ return p0;
+ }
+ else{
+ float3 v = cross(c, d)*dot(b, b) + cross(d, b)*dot(c, c) + cross(b, c)*dot(d, d);
+ v /= det;
+ return p0 + v;
}
- return selection;
+
}
-static std::optional<Mesh *> calculate_weld(const Mesh &mesh, const WeldModifierData &wmd)
-{
- const int defgrp_index = BKE_id_defgroup_name_index(&mesh.id, wmd.defgrp_name);
- Span<MDeformVert> vertex_group = get_vertex_group(mesh, defgrp_index);
- const bool invert = (wmd.flag & MOD_WELD_INVERT_VGROUP) != 0;
-
- if (wmd.mode == MOD_WELD_MODE_ALL) {
- if (!vertex_group.is_empty()) {
- Vector<int64_t> selected_indices = selected_indices_from_vertex_group(
- vertex_group, defgrp_index, invert);
- return blender::geometry::mesh_merge_by_distance_all(
- mesh, IndexMask(selected_indices), wmd.merge_dist);
+// Remove unused params
+static Vector<std::pair<int, Vector<int>>> getViolatingTets(Vector<float3> &verts,
+ Vector<int> &tetVertId,
+ Vector<int> &tetFaceNeighbors,
+ Vector<float3> &faceNormals,
+ Vector<float> &planesD,
+ int tetMarkId,
+ Vector<int> &tetMarks,
+ float3 currVert,
+ int containingTetNr
+ ){
+
+ Vector< std::pair<int,Vector<int>> > violatingTets;
+ Vector<int> stack;
+
+ stack.append(containingTetNr);
+ tetMarks[containingTetNr] = tetMarkId;
+
+ while(stack.size()){
+ int currTet = stack.last();
+ stack.remove_last();
+
+ tetMarks[currTet] = tetMarkId;
+ Vector<int> currTetBorderFaces;
+
+ for(int i = 0; i<4; i++){
+ int neighborTet = tetFaceNeighbors[4*currTet + i];
+
+ if(neighborTet<0){
+ currTetBorderFaces.append(i);
+ continue;
+ }
+ if(tetMarks[neighborTet]==tetMarkId){
+ continue;
+ }
+
+ float3 p0 = verts[tetVertId[4*currTet + 0]];
+ float3 p1 = verts[tetVertId[4*currTet + 1]];
+ float3 p2 = verts[tetVertId[4*currTet + 2]];
+ float3 p3 = verts[tetVertId[4*currTet + 3]];
+
+ float3 circumCenter = getCircumCenter(p0, p1, p2, p3);
+ float circumRadius = length(p0 - circumCenter);
+
+ if(length(currVert - circumCenter) <= circumRadius){
+ stack.append(neighborTet);
+ tetMarks[neighborTet] = tetMarkId;
+ }
+ else{
+ currTetBorderFaces.append(i);
+ }
+ }
+ violatingTets.append({currTet, currTetBorderFaces});
+ }
+
+ // for(int currTet = 0; currTet<tetVertId.size()/4; currTet++){
+ // float3 p0 = verts[tetVertId[4*currTet + 0]];
+ // float3 p1 = verts[tetVertId[4*currTet + 1]];
+ // float3 p2 = verts[tetVertId[4*currTet + 2]];
+ // float3 p3 = verts[tetVertId[4*currTet + 3]];
+
+ // float3 circumCenter = getCircumCenter(p0, p1, p2, p3);
+ // float circumRadius = length(p0 - circumCenter);
+ // if()
+ // }
+
+ return violatingTets;
+}
+
+static Vector<int> createTets(Vector<float3> verts, /*tree, */ float minTetQuality){
+ Vector<int> tetVertId; // Stores indices of vertex that form a tet. Every tet is stored as 4 indices
+ Vector<int> tetFaceNeighbors; // Stores index of tet that shares the face as per tetFaces order. 4 neighbors per tet, 1 for each face
+
+ int firstFreeTet = -1;
+
+ Vector<float3> faceNormals; // Stores the normal of each of face of the tet
+ Vector<float> planesD;
+
+ int tetMarkId = 0;
+ Vector<int> tetMarks;
+ /*Used to keep track of visited tets for various processess. In each step where visited tets need to avoided,
+ on visiting them, a unique number is stored representing that particular step
+ */
+
+ int bigTet = verts.size() - 4;
+
+ for(int i = 0; i<4; i++){
+ tetVertId.append(bigTet + i);
+ tetFaceNeighbors.append(-1);
+ faceNormals.append({0.0, 0.0, 0.0});
+ planesD.append(0.0);
+ }
+ tetMarks.append(0);
+ setTetProperties(verts, tetVertId, faceNormals, planesD, 0);
+
+ for(int vertNr = 0; vertNr<bigTet; vertNr++){
+ float3 currVert = verts[vertNr];
+
+ // std::cout << "Adding vert " << vertNr << std::endl;
+
+ // Find containing tet (need to understand) center can lie outside the tet?
+ tetMarkId += 1;
+ int containingTetNr = -1;
+ containingTetNr = findContainingTet(verts, tetVertId, tetFaceNeighbors, faceNormals, planesD, tetMarkId, tetMarks, currVert);
+
+ if(containingTetNr == -1){
+ std::cout << "Couldn't add vert " << vertNr << std::endl;
+ continue;
+ }
+
+ tetMarkId += 1;
+ Vector<std::pair<int, Vector<int>>> violatingTets = getViolatingTets(verts, tetVertId, tetFaceNeighbors, faceNormals, planesD, tetMarkId, tetMarks, currVert, containingTetNr);
+
+ Vector<int> newTets; // Stores tet numbers of the new tets formed. Used for making neighbors of the new tets formed
+ for(int violatingTetNr = 0; violatingTetNr<violatingTets.size(); violatingTetNr++){
+ int violatingTet = violatingTets[violatingTetNr].first;
+ Vector<int> boundaryFaces = violatingTets[violatingTetNr].second;
+
+ Vector<int> currTetVerts;
+ Vector<int> currTetNeighbors;
+ for(int i = 0; i<4; i++){
+ currTet
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list