Using Inbuilt Datastructures #893

Kushal-Shah-03 · 2024-08-10T23:13:08Z

Removed VertexDatapool class and used Vec and VecView instead.

Kushal-Shah-03 · 2024-08-10T23:15:18Z

Sorry, for the delay, it took me some time to figure out where to use Vec and VecView. There is another class called Pool, I think since it's using unique_ptrs, we can't replace it with Vec, but I'm not sure, could you @pca006132, help me out with this?

codecov · 2024-08-10T23:31:29Z

Codecov Report

Attention: Patch coverage is 81.37255% with 57 lines in your changes missing coverage. Please review.

Project coverage is 87.67%. Comparing base (d437097) to head (abfd857).
Report is 78 commits behind head on master.

Files	Patch %	Lines
src/manifold/src/quickhull.cpp	80.00%	49 Missing ⚠️
src/manifold/src/quickhull.h	80.00%	6 Missing ⚠️
src/manifold/src/impl.cpp	90.47%	2 Missing ⚠️

Additional details and impacted files

@@            Coverage Diff             @@
##           master     #893      +/-   ##
==========================================
- Coverage   91.84%   87.67%   -4.17%     
==========================================
  Files          37       66      +29     
  Lines        4976     9448    +4472     
  Branches        0     1024    +1024     
==========================================
+ Hits         4570     8284    +3714     
- Misses        406     1164     +758

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

pca006132 · 2024-08-11T04:56:28Z

src/manifold/src/quickhull.cpp

@@ -32,33 +32,11 @@ double defaultEps() { return 0.0000001; }
 ConvexHull QuickHull::getConvexHull(const std::vector<glm::dvec3>& pointCloud,
                                    bool CCW, bool useOriginalIndices,
                                    double epsilon) {
-  VertexDataSource vertexDataSource(pointCloud);
+  manifold::Vec<glm::dvec3> vertexDataSource(pointCloud);


@elalish I vaguely recall you said we should move the quickhull thing into the manifold namespace right?

If we move the namespace, we don't need this manifold:: namespace specifier.

Also, will this change the timing? You are copying the points into a Vec. Should we modify the input pointCloud to VecView?

@elalish I vaguely recall you said we should move the quickhull thing into the manifold namespace right?

If we move the namespace, we don't need this manifold:: namespace specifier.

That was regarding removing the namespace for quickhull right? So, should I also wrap the code in namespace manifold?

Also, will this change the timing? You are copying the points into a Vec. Should we modify the input pointCloud to VecView?

I tried modifying the input 'pointCloud' to VecView, but it was showing the error that VecView had a protected constructor. I can try to surpass that though, I'll give it one more try.

Also, optimizedVertexBuffer is a unique_ptr so, it won't be compatible with VecView right?, so when I'm calling

vertices = manifold::VecView<glm::dvec3>(*optimizedVertexBuffer); it won't work right?

Just change the namespace for quickhull to manifold.

Can you show me the modification and error message about protected constructor?

optimizedVertexBuffer is an internal buffer, you want Vec for that.

I'll change the namespace

[ 14%] Building CXX object src/manifold/CMakeFiles/manifold.dir/src/manifold.cpp.o
cd /home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/build/src/manifold && /usr/bin/c++ -Dmanifold_EXPORTS -I/home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/src/manifold/include -I/home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/src/utilities/include -I/home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/build/_deps/glm-src -I/home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/src/collider/include -I/home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/src/polygon/include -O3 -DNDEBUG -fPIC -Werror -Wall -Wno-unused -Wno-array-bounds -Wno-stringop-overflow -Wno-alloc-size-larger-than -DMANIFOLD_EXCEPTIONS=1 -Winvalid-pch -include /home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/build/src/manifold/CMakeFiles/manifold.dir/cmake_pch.hxx -MD -MT src/manifold/CMakeFiles/manifold.dir/src/manifold.cpp.o -MF CMakeFiles/manifold.dir/src/manifold.cpp.o.d -o CMakeFiles/manifold.dir/src/manifold.cpp.o -c /home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/src/manifold/src/manifold.cpp
/home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/src/manifold/src/manifold.cpp: In static member function ‘static manifold::Manifold manifold::Manifold::Hull(const std::vector<glm::vec<3, float, glm::packed_highp> >&)’:
/home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/src/manifold/src/manifold.cpp:927:13: error: use of deleted function ‘manifold::QuickHull::QuickHull()’
927 | QuickHull qh;
| ^~
In file included from /home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/src/manifold/src/manifold.cpp:23:
/home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/src/manifold/src/quickhull.h:637:7: note: ‘manifold::QuickHull::QuickHull()’ is implicitly deleted because the default definition would be ill-formed:
637 | class QuickHull {
| ^~~~~~~~~
/home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/src/manifold/src/quickhull.h:637:7: error: ‘constexpr manifold::VecView::VecView() [with T = glm::vec<3, double, glm::packed_highp>]’ is protected within this context
In file included from /home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/src/utilities/include/vec.h:24,
from /home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/src/utilities/include/utils.h:27,
from /home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/src/utilities/include/sparse.h:21,
from /home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/src/collider/include/collider.h:18,
from /home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/src/manifold/src/impl.h:18,
from /home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/src/manifold/src/boolean3.h:16,
from /home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/src/manifold/src/manifold.cpp:19:
/home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/src/utilities/include/vec_view.h:109:3: note: declared protected here
109 | VecView() = default;
| ^~~~~~~
make[2]: *** [src/manifold/CMakeFiles/manifold.dir/build.make:208: src/manifold/CMakeFiles/manifold.dir/src/manifold.cpp.o] Error 1
make[2]: Leaving directory '/home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/build'
make[1]: *** [CMakeFiles/Makefile2:538: src/manifold/CMakeFiles/manifold.dir/all] Error 2
make[1]: Leaving directory '/home/kushal/gitrepo/GSOC/manfioldAlgov2/manifold/build'
make: *** [Makefile:159: all] Error 2

In terms of modification all I'm doing is since we want to make pointCloud VecView, I make some Vec's VecView's for the code to compile (without incorrect function definitions) but this error persists

I just looked at it, this QuickHull class is just something that holds all data in the QuickHull algorithm. You can move the getConvexHull functions out into a standalone function, and construct QuickHull within that function. You should initialize VecView in the constructor of the QuickHull class, so we do not have to default-construct the VecView (which doesn't make sense, you can treat this VecView as a reference, you should not have null references).

Alright, I'll commit the changes I've made to the Mesh structure first and then I'll work on this, to separate the commits

pca006132 · 2024-08-11T06:02:35Z

For the pool thing, just change the inner vector into Vec. And I am curious how much reuse does this pool enable.

Kushal-Shah-03 · 2024-08-11T14:20:37Z

For the pool thing, just change the inner vector into Vec. And I am curious how much reuse does this pool enable.

So, at just one place it actually uses the erase function call of vector, should I just work around that by manually erasing it by iterating the Vec (since the inbuilt call was O(n) anyway), or should I modify our implementation of Vec to add a erase implementation? [Also, note this won't add a massive overhead, this is only called when the hull algorithm fails to solve a horizon edge]

8000

Kushal-Shah-03 · 2024-08-11T20:32:48Z

Also, regarding the HalfEdge datastructure, since most of the parameters are the same except one, I decided to add the inbuilt structure in the new structure as a variable, but since our HalfEdge structure stores startVert,endVert,pairedHalfEdge and face as int while the implementation uses size_t, what should I be doing, should I just change the implementation to now use int instead of size_t, because otherwise there are lot's of warnings and errors.

Also, I feel that despite it using almost the same variables, we cannot afford to remove the implementations structure, because it uses functions to disable the edges when not in use [and I think this disabling might be the reason this implementation gives such a good performance in terms of speed].

elalish · 2024-08-12T05:51:55Z

Manual erasing and switching to int sound fine to me for now. When in doubt, go with fewer lines of added/changed code.

How does the disabling of edges work? Is it just a marker per edge, or a more complex/efficient structure? If the former, you can probably just add a parallel vector.

Kushal-Shah-03 · 2024-08-12T06:29:30Z

Manual erasing and switching to int sound fine to me for now. When in doubt, go with fewer lines of added/changed code.

How does the disabling of edges work? Is it just a marker per edge, or a more complex/efficient structure? If the former, you can probably just add a parallel vector.

Alright I'll switch to int.
It is sort of a marker (it sets the endVertex to MAX to mark it as unused), Instead of a parallel vector I was just planning to add our HalfEdge structure as a variable inside each HalfEdge that also works right? [since this HalfEdge has a next halfedge corresponding variable (so it actually isn't stored chronologically), so an independent vector of our halfedge structure would not be very useful]

pca006132 · 2024-08-12T12:19:13Z

Instead of a parallel vector I was just planning to add our HalfEdge structure as a variable inside each HalfEdge that also works right? [since this HalfEdge has a next halfedge corresponding variable (so it actually isn't stored chronologically), so an independent vector of our halfedge structure would not be very useful]

I don't understand this part, can you elaborate a bit or maybe just show some pseudocode?

So, at just one place it actually uses the erase function call of vector, should I just work around that by manually erasing it by iterating the Vec (since the inbuilt call was O(n) anyway), or should I modify our implementation of Vec to add a erase implementation? [Also, note this won't add a massive overhead, this is only called when the hull algorithm fails to solve a horizon edge]

Adding erase method to our Vec implementation is fine. It should be very simple.

elalish · 2024-08-12T15:21:58Z

We actually use a similar system - we set a halfedge to {-1, -1, -1, -1} to indicate it has been removed, for instance. You can feel free to use any negative flags you need for your implementation.

Kushal-Shah-03 · 2024-08-13T13:10:06Z

I don't understand this part, can you elaborate a bit or maybe just show some pseudocode?

I'm just using our HalfEdge implementation as a variable inside the HalfEdge implementation of the algortihm:
So, the code looks like this

struct HalfEdge {
    manifold::Halfedge halfEdgeManifold;
    int next;
    // functions
}

pca006132 · 2024-08-13T14:12:34Z

I don't understand why you still need the old halfedge data structure there. The two fields left are a next index (which manifold's halfedge data structure already has) and manifold's halfedge data structure.

Kushal-Shah-03 · 2024-08-13T14:16:46Z

I don't understand why you still need the old halfedge data structure there. The two fields left are a next index (which manifold's halfedge data structure already has) and manifold's halfedge data structure.

https://github.com/elalish/manifold/blob/e01d31611ed5894094cc89005db89b1ca2f417bf/src/manifold/src/shared.h#L123C1-L132C3
I might have missed something, but this does not have the next index right?

pca006132 · 2024-08-13T14:18:32Z

oh sorry, I forgot that we assume that the halfedge data structure is for triangular mesh, and the next id is always computable from the current id (using the next function)

it is very likely that the halfedge here also has this property.

Kushal-Shah-03 · 2024-08-13T14:21:54Z

oh sorry, I forgot that we assume that the halfedge data structure is for triangular mesh, and the next id is always computable from the current id (using the next function)

it is very likely that the halfedge here also has this property.

Do you mean the NextHalfEdge function? I just thought, that since we are disabling, we might reuse it later with other values, leading to it not being in the order of indexes (which is what I think the NextHalfEdge function assumes)

pca006132 · 2024-08-13T14:23:58Z

They disable all three halfedges around the face, so this should not be an issue.

Kushal-Shah-03 · 2024-08-13T14:29:03Z

They disable all three halfedges around the face, so this should not be an issue.

Ya, but they also change the order of the HalfEdges right? so we would need a next variable (they do so to avoid rearranging everytime as far I understand)
https://github.com/elalish/manifold/blob/e01d31611ed5894094cc89005db89b1ca2f417bf/src/manifold/src/quickhull.h#L581C1-L603C6

pca006132 · 2024-08-13T14:34:44Z

I see. I think this is fine for now. In the future if we have time we should look at how to avoid those halfedge reordering, so we can directly use as our halfedge data structure.

Kushal-Shah-03 · 2024-08-13T14:38:03Z

Also, I've made the change for the VecView (the error I was having) and Vec for Pool, could you go through them once as well when you have time

pca006132 · 2024-08-13T14:52:38Z

src/manifold/src/quickhull.h

    if (data.size() == 0) {
-      return std::unique_ptr<std::vector<size_t>>(new std::vector<size_t>());
+      return std::unique_ptr<manifold::Vec<size_t>>(


std::make_unique<manifold::Vec<size_t>>()

pca006132 · 2024-08-13T14:56:11Z

src/manifold/src/quickhull.h

-          new std::vector<glm::dvec3>(*o.optimizedVertexBuffer));
-      vertices = VertexDataSource(*optimizedVertexBuffer);
+          new manifold::Vec<glm::dvec3>(*o.optimizedVertexBuffer));
+      vertices = manifold::Vec<glm::dvec3>(*optimizedVertexBuffer);


can you just use vertices = *optimizedVertexBuffer?

Kushal-Shah-03 · 2024-08-13T20:46:08Z

I've made the changes @elalish and @pca006132 , could you review this once. I will start working on profiling, so that we can plan further.

pca006132 · 2024-08-19T02:08:03Z

The compilation error is probably caused by missing include, instead of conditional compilation.

src/utilities/include/public.h

pca006132 · 2024-08-19T14:29:12Z

src/manifold/src/quickhull.h

+class ConvexHull {
+ public:
+  Vec<Halfedge> halfedges;
+  std::vector<glm::dvec3> vertices;


I found that I forgot to change this to Vec.

pca006132 · 2024-08-19T14:31:17Z

src/manifold/src/quickhull.h

-  std::vector<size_t> horizonEdgesData;
+  Vec<size_t> newFaceIndices;
+  Vec<size_t> newHalfedgeIndices;
+  std::vector<std::unique_ptr<Vec<size_t>>> disabledFacePointVectors;


Maybe reorder this to make std::vector at the start/end? Just make it a bit more consistent...

pca006132 · 2024-08-19T14:32:02Z

src/manifold/src/quickhull.h

+  Vec<size_t> newHalfedgeIndices;
+  std::vector<std::unique_ptr<Vec<size_t>>> disabledFacePointVectors;
+  Vec<size_t> visibleFaces;
+  Vec<size_t> horizonEdgesData;
  struct FaceData {


and maybe move this struct definition to the start of the outer class.

pca006132 · 2024-08-19T14:33:42Z

src/manifold/src/quickhull.h

-  HalfEdgeMesh getConvexHullAsMesh(const double* vertexData, size_t vertexCount,
-                                   bool CCW, double eps = defaultEps());
+  //   Convex hull of the point cloud as halfEdge vector and vertex vector
+  ConvexHull getConvexHullAsMesh(const Vec<glm::dvec3>& pointCloud, bool CCW,


Questions: Is it useful to keep CCW here? Can we pass the mesh epsilon from our mesh function?

No need to fix it in this PR, just food for thought.

So, the original implementation handled CCW, so I decided to handle it as well, if we don't plan to use CCW in the future, I can go ahead and remove it.

I think we should be able to use the mesh epsilon as well, we can test that in the next PR, and look at the results.

pca006132 · 2024-08-19T14:34:50Z

src/manifold/src/quickhull.cpp

 #include <limits>

+namespace manifold {
+
 double defaultEps() { return 0.0000001; }


Should we change to kTolerance? After the double precision PR the epsilon will be much smaller though, we should see how this default epsilon affects precision and runtime.

We can do it in a later PR.

I'm not sure what kTolerance is here, I will look into it, but it's possible that the epsilon value was chosen to improve speed, we can look into it while assessing speed in the next PR.

pca006132 · 2024-08-19T14:37:17Z

src/manifold/src/quickhull.cpp

+
+std::unique_ptr<Vec<size_t>> QuickHull::getIndexVectorFromPool() {
+  auto r = indexVectorPool.get();
+  r->resize(0);


This resize actually causes reallocation, so currently the pool is pretty much useless. We should try and see if this pool actually helps (by implementing an alternative resize function in vec.h to avoid it from shrinking) or we can remove it all together.

Anyway, it seems that the pool magically helps despite this resize will cause reallocation, and changing this resize to something that does not perform reallocation will not help. I guess it is about the size of Face and allocating empty unique pointers...

Should further investigate later.

Yeah, I had experimented with this as well, changing it seemed to affect the speed negatively, but I wasn't sure as to why. Let's look into it in the next PR as well.

pca006132 · 2024-08-19T15:28:05Z

One potential direction for optimization is to look at splitting std::vector<Face> to multiple vectors (vec of structs to struct of vecs), as Face is now a huge struct, and some of the tight loops are not using all fields of Face and may benefit from better spatial locality from struct of vecs.

Kushal-Shah-03 · 2024-08-19T16:29:05Z

That's an excellent idea, I think I'll just push a final commit making the modifications that you suggested, then we should move to a new PR, where we can start discussing these points related to optimization, because otherwise these two PR's will get mixed up, and we'll loose track of our ideas. So, once this PR get's merged I'll open another PR where I'll add the tracy headers, and then we can look into various optimizations there, does that sound alright?

Kushal-Shah-03 · 2024-08-19T16:54:30Z

I've made the changes that were suggested. I'm also testing this code on the Thingi10K dataset again, just in case we modified something incorrectly leading to bugs. I'll update once it's done.

Kushal-Shah-03 · 2024-08-19T17:15:54Z

Ok, so this comes as a surprise to me, but while testing, this test case file 101213.stl, seems to go in an infinite loop (since it never caused a timeout before and since the time was 0.0006 seconds before, I doubt it's due to a timeout). I am looking to investigate as to what change could have caused this issue. @pca006132 it seemed to work after my last commit , any places you would suggest looking at? (I am thinking I'll start by going back commits one by one to see which commit caused the issue and then we can try to find what caused it?)

Kushal-Shah-03 · 2024-08-19T17:39:10Z

Ok, so this comes as a surprise to me, but while testing, this test case file 101213.stl, seems to go in an infinite loop (since it never caused a timeout before and since the time was 0.0006 seconds before, I doubt it's due to a timeout). I am looking to investigate as to what change could have caused this issue. @pca006132 it seemed to work after my last commit , any places you would suggest looking at? (I am thinking I'll start by going back commits one by one to see which commit caused the issue and then we can try to find what caused it?)

So, to clarify it wasn't a timeout, it was a segfault, I apologize for that miscommunication, I've identified that it's occurring in SplitPinchedVerts() (there were no segfaults in the algorithm call) https://github.com/elalish/manifold/blob/74e15b1574ebe6ae01d1fd2cffbe75aeeb7b8fab/src/manifold/src/edge_op.cpp#L671C1-L675C8 (Somewhere here).
I understand that it's probably not an error there, it's probably related to some other bug in the algorithm, and I will try to check out older commits and see if I can find the issue

Kushal-Shah-03 · 2024-08-19T17:52:17Z

Alright, so it's one of d9edae6 or 76d4126 that caused the issue. The former wasn't compiling on my system, but the latter is the first time the file 101213.stl leads to a segfault. @pca006132 there are lots of changes in these two commits, since you made them do you have any ideas as to what could have caused it? Because I am slightly lost as to where I should look for it, since I don't quite understand all the simplifications you made to the code.

pca006132 · 2024-08-20T00:03:52Z

Interesting. To start you can call the ismanifold method to check if the halfedge vector is wrong. I am busy these two days so I cannot debug this for now, sorry about that.

Kushal-Shah-03 · 2024-08-20T07:46:36Z

Interesting. To start you can call the ismanifold method to check if the halfedge vector is wrong. I am busy these two days so I cannot debug this for now, sorry about that.

No problem, I had some spare time and tried to understand the code as much as I could, and I noticed that when you're reordering the halfedges, you've assumed that all faces are valid (and there will be no disabled faces, which is not the case). I've added return when the face is disabled or the halfedge is disabled and since the all the faces are not being considered now, I used j from 0 incrementing it by 3 instead of the face_index*3. Good news is that it is working on all cases now, with the same accuracy.
Could you go through it once, and see if the code follows how you wanted to simplify it?

pca006132 · 2024-08-20T09:34:21Z

src/manifold/src/quickhull.cpp

+                 // for each halfedge)
+  for_each(autoPolicy(mesh.halfedges.size()), countAt(0_uz),
+           countAt(mesh.halfedges.size()), [&](size_t i) {
+             if (mesh.halfedges[i].pairedHalfedge < 0) return;


This part will not work when run in parallel. You can change the autoPolicy to ExecutionPolicy::Seq for now and optimize that later.

Yeah, I realized I hadn't handled for parallel execution. I've made the changes now.

Kushal-Shah-03 · 2024-08-20T12:01:06Z

I've checked it again on the dataset, it's working correctly. I think the PR is ready to merge now.

elalish

Great job working together on this! If it's not too onerous, it would be great to include the test object that caught this error in our TEST set, but let's do that as a follow-on.

pca006132 · 2024-08-20T16:15:49Z

src/manifold/src/quickhull.cpp

+  Vec<int> faceMap(mesh.faces.size());
+
+  // reorder halfedges
+  // Since all faces are not used now (so we should start from 0 and just


This is a bit confusing to read. I think this means 'some faces are disabled and should not go into the halfedge vector'.

pca006132 · 2024-08-20T16:18:12Z

src/manifold/src/quickhull.cpp

+        if (mesh.halfedges[i].pairedHalfedge < 0) return;
+        if (mesh.faces[mesh.halfedges[i].face].isDisabled()) return;
+        if (AtomicAdd(counts[mesh.halfedges[i].face], 1) > 0) return;
+        int currIndex = AtomicAdd(j, 3);


Atomic works here, but typically I would avoid this kind of frequent atomic updates to the same variable as it is quite expensive. If you think about it, the CPU must synchronize all access to this variable, and it is quite frequent. Anyway, just food for thought and I should have actual benchmark data supporting my claim (or the null hypothesis, i.e. atomic add is good enough).

And it is nice that you can figure this out! This is the interesting thing about parallel programming!

pca006132 · 2024-08-20T16:22:42Z

src/manifold/src/quickhull.cpp

+  // remove unused vertices
+  for_each(autoPolicy(halfedges.size() / 3), countAt(0_uz),
+           countAt(halfedges.size() / 3), [&](size_t i) {
+             AtomicAdd(counts[halfedges[3 * i].startVert], 1);


Food for thought: maybe atomic set will be better for performance, and we don't need the transform iterator later.

I couldn't find the function for atomic set, could you tell me what to use?

pca006132 · 2024-08-20T16:22:57Z

src/manifold/src/quickhull.cpp

+             he.endVert = counts[he.endVert];
+           });
+  // setting face id
+  for (size_t index = 0; index < halfedges.size(); index++) {


parallel? and combine with the loop before?

pca006132 · 2024-08-20T16:24:26Z

test/hull_test.cpp

@@ -52,6 +52,7 @@ bool isMeshConvex(manifold::Manifold hullManifold, double epsilon = 0.0000001) {

      // If any vertex lies on the opposite side of the normal direction
      if (distance > epsilon) {
+        std::cout << distance << std::endl;


remove this?

pca006132 · 2024-08-20T16:25:59Z

src/manifold/src/quickhull.cpp

+        }
+      }
+      if (change_flag == 1)
+        tf.pointsOnPositiveSide->resize(tf.pointsOnPositiveSide->size() - 1);


we can use pop_back(), I forgot to fix this.

pca006132 · 2024-08-20T16:27:19Z

src/manifold/src/impl.cpp

@@ -478,6 +478,35 @@ Manifold::Impl::Impl(const Mesh& mesh, const MeshRelationD& relation,
  Finish();
 }

+void Manifold::Impl::Hull(const std::vector<glm::vec3>& vertPos) {


btw why are we taking std::vector here? shouldn't we take VecView?

pca006132 · 2024-08-20T16:28:12Z

oops, we can address the comments in the next PR I guess

elalish · 2024-08-20T16:35:53Z

oops, sorry @pca006132! Yeah, let's address in the next PR - this discussion is getting too long to keep track of.

Kushal-Shah-03 · 2024-08-20T16:40:05Z

Yeah I agree with @elalish, it's gotten a bit hard to keep track of the conversation. I'll open another PR, where I will add the tracy headers and do some of the changes you suggested, then we can look into it further.

Kushal-Shah-03 · 2024-08-20T16:41:59Z

Great job working together on this! If it's not too onerous, it would be great to include the test object that caught this error in our TEST set, but let's do that as a follow-on.

That's a great idea, it's a testcase where the algorithm disables some faces, so adding that case will ensure we've handled disabling the faces correctly.

Kushal-Shah-03 · 2024-08-18T20:22:33Z

src/utilities/include/public.h

@@ -598,7 +598,6 @@ class Quality {
 *  @brief Custom Exceptions
 * @{
 */
-#ifdef MANIFOLD_DEBUG


We should still keep #ifdef MANIFOLD_EXCEPTIONS right?, because otherwise std::logic_error and such errors won't be defined (as won't be included).

Kushal-Shah-03 · 2024-08-19T16:24:12Z

src/manifold/src/quickhull.h

-  HalfEdgeMesh getConvexHullAsMesh(const double* vertexData, size_t vertexCount,
-                                   bool CCW, double eps = defaultEps());
+  //   Convex hull of the point cloud as halfEdge vector and vertex vector
+  ConvexHull getConvexHullAsMesh(const Vec<glm::dvec3>& pointCloud, bool CCW,


So, the original implementation handled CCW, so I decided to handle it as well, if we don't plan to use CCW in the future, I can go ahead and remove it.

I think we should be able to use the mesh epsilon as well, we can test that in the next PR, and look at the results.

Kushal-Shah-03 · 2024-08-19T16:25:33Z

src/manifold/src/quickhull.cpp

 #include <limits>

+namespace manifold {
+
 double defaultEps() { return 0.0000001; }


I'm not sure what kTolerance is here, I will look into it, but it's possible that the epsilon value was chosen to improve speed, we can look into it while assessing speed in the next PR.

Kushal-Shah-03 · 2024-08-19T16:26:59Z

src/manifold/src/quickhull.cpp

+
+std::unique_ptr<Vec<size_t>> QuickHull::getIndexVectorFromPool() {
+  auto r = indexVectorPool.get();
+  r->resize(0);


Yeah, I had experimented with this as well, changing it seemed to affect the speed negatively, but I wasn't sure as to why. Let's look into it in the next PR as well.

Kushal-Shah-03 · 2024-08-20T11:17:30Z

src/manifold/src/quickhull.cpp

+                 // for each halfedge)
+  for_each(autoPolicy(mesh.halfedges.size()), countAt(0_uz),
+           countAt(mesh.halfedges.size()), [&](size_t i) {
+             if (mesh.halfedges[i].pairedHalfedge < 0) return;


Yeah, I realized I hadn't handled for parallel execution. I've made the changes now.

Kushal-Shah-03 · 2024-08-21T12:57:52Z

src/manifold/src/quickhull.cpp

+  // remove unused vertices
+  for_each(autoPolicy(halfedges.size() / 3), countAt(0_uz),
+           countAt(halfedges.size() / 3), [&](size_t i) {
+             AtomicAdd(counts[halfedges[3 * i].startVert], 1);


I couldn't find the function for atomic set, could you tell me what to use?

Kushal-Shah-03 and others added 2 commits August 11, 2024 04:40

Removing VertexDatSource structure and Replacing it with Vec

037f063

Merge branch 'elalish:master' into HullAlgov2

4313227

Kushal-Shah-03 changed the title ~~Using Inbuild Datastructures~~ Using Inbuilt Datastructures Aug 10, 2024

pca006132 reviewed Aug 11, 2024

View reviewed changes

Kushal-Shah-03 added 4 commits August 13, 2024 18:42

Integrated HalfEdge datastructure of Manifold (in progress)

ff28542

Merge remote-tracking branch 'origin/HullAlgov2' into HullAlgov2

56af511

Changed QuickHull Class to accomodate VecView

ad1e0a2

Formatting changes and modified erase

1043e4c

pca006132 reviewed Aug 13, 2024

View reviewed changes

Made the suggested changes

c8d439f

fix include

10000

f95fe21

format

fdaf121

elalish approved these changes Aug 19, 2024

View reviewed changes

src/utilities/include/public.h Show resolved Hide resolved

pca006132 reviewed Aug 19, 2024

View reviewed changes

Made the suggested changes

9432445

Kushal-Shah-03 added 2 commits August 20, 2024 13:13

Fixed : processing disabled faces bug

8c6525a

Removed unecessary comments

b0fbf4c

pca006132 reviewed Aug 20, 2024

View reviewed changes

Kushal-Shah-03 added 3 commits August 20, 2024 15:52

Trying atomic for j

24f4add

Suggested fix

87aad9b

Atomic Add should work

abfd857

elalish approved these changes Aug 20, 2024

View reviewed changes

elalish merged commit fd485f6 into elalish:master Aug 20, 2024
22 checks passed

pca006132 reviewed Aug 20, 2024

View reviewed changes

Kushal-Shah-03 commented Aug 22, 2024

View reviewed changes

elalish mentioned this pull request Nov 5, 2024

v3.0 #1024

Merged

Using Inbuilt Datastructures #893

Using Inbuilt Datastructures #893

Uh oh!

Conversation

Uh oh!

Uh oh!

Uh oh!

Codecov Report

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

8000 Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!