graphics,3d,mesh , Algorithm for cutting a mesh using another mesh

Algorithm for cutting a mesh using another mesh


Tag: graphics,3d,mesh

I am looking for an algorithm that given two meshes could clip one using another.
The simplest form of this is clipping a mesh using a plane. I've already implemented that by following something similar to what is described here.
What it does is basically inspecting all mesh vertices and triangles with respect to the plane (the plane's normal and point are given). If the triangle is completely above the plane, it is left untouched. If it falls completely below the plane, it is discarded. If some of the edges of the triangle intersect with the plane, the intersecting points with the plane are calculated and added as the new vertices. Finally a cap is generated for the hole on the place the mesh was cut.

The problem is that the algorithm assumes that the plane is unlimited, therefore whatever is in its path is clipped. In the simplest form, I need an extension of this without the assumption of a plane of "infinite" size.

To clarify, imagine that we have a 3D model of a desk with 2 boxes on it. The boxes are adjacent (but not touching or stacked). The user will define a cutting plane of a limited width and height underneath the first box and performs the cut. We end up with a desk model (mesh) with a box on it and another box (mesh) that can be freely moved around/manipulated.

In the general form, I'd like the user to be able to define a bounding box for the box he/she wants to separate from the desk model and perform the cut using that bounding box.

If I could extend the algorithm I already have to an algorithm with limited-sized planes, that would be great for now.


What you're looking for are constructive solid geometry/boolean algorithms with arbitrary meshes. It's considerably more complex than slicing meshes by an infinite plane.

Among the earliest and simplest research in this area, and a good starting point, is Constructive Solid Geometry for Polyhedral Objects by Trumbore and Hughes.

From the original paper: enter image description here

More elaborate solutions extend upon this subject with a variety of data structures.

The real complexity of the operation lies in the slicing algorithm to slice one triangle against another. The nightmare of implementing robust CSG lies in numerical precision. It's easy when you involve objects far more complex than a cube to run into cases where a slice is made just barely next to a vertex (at which point you have the tough decision of merging the new split vertex or not prior to carrying out more splits), where polygons are coplanar (or almost), etc.

So I suggest initially erring on the side of using very high-precision floating point numbers, possibly even higher than double precision to focus on getting something working correctly and robustly. You can optimize later (first pass should be to use an accelerator like an octree/kd-tree/bvh), but you'll avoid many headaches this way in your first iteration.

This is vastly simpler to implement at render time if you're focusing on a raytracer rather than a modeling software, e.g. With raytracers, all you have to do to do this kind of arbitrary clipping is pretend that an object used to subtract from another has its polygons flipped in the culling process, e.g. It's easy to solve robustly at the ray level, but quite a bit harder to do robustly at the geometric level.

Another thing you can do to make your life so much easier if you can afford it is to voxelize your object, find subtractions/additions/unions of voxels, and then translate the voxels back into a mesh. This is so much easier to make robust, but harder to do efficiently and the voxel->polygon conversion can get quite involved if you want better results than what marching cubes provide.

It's a really tough area to do extremely well and requires perseverance, and thus the reason for the existence of things like this:


How to check a point is inside an ellipsoid with orientation?

For an ellipsoid of the form with orientation vector and centre at point , how to find whether a point is inside the ellipsoid or not? An additional note that the geometry actually is with a=b (spheroid) and therefore one axis is sufficient to define orientation Note: I see a...

plotting points in 3d surface using x,y,z coordinates

I need to plot some points in 3d surface based on x,y,z coordiantes values in a file named as test.dat test.dat file contains At-No X Y Z 6 3.532210 -2.171743 0.921140 7 1.164869 -1.418981 0.782133 1 2.454732 2.332989 -0.907213 6 -3.246376 -1.047325 -0.602590 6 -2.620684 0.053348 -0.013310 6 -4.569969 -1.249720...

How to setup camera to point at object

In my app I load models from different files (format is the same) and they have different geometry: big, small, wide, etc. I have object and camera position hard coded and for some cases I don't see anything because camera not point to object. Maybe there is a way to...

Add white rectangle above a screenshot in a Graphics object (java) [duplicate]

This question already has an answer here: How to add text to an image in java? 1 answer I've got a method that's supposed to add some text to screenshots. The screenshot is fed into this method as a File object like this: private void modifyScreenshot(File file) throws Exception...

Displaying surface with non-rectangular boundary

Refer to the attached image. I want to display the image in Matlab using the function surf(). However, I only want to display the region of the actual object without the background (the pale-green region surrounding the actual object which has 0 value). How to do that? I tried replacing...

Plot: Add legend that overlay several Frames

How can we write a legend that overlay several frames? Using the xpd parameter, the legend can exit its frame but still cannot enter the next frame. par(mfrow=c(1,2)) plot(rnorm(120), rnorm(120)) legend(x = -0.1, y=0.1, legend = "Legend that covers both plots", text.col="red", cex=2, box.col="red", xpd=TRUE) plot(rnorm(120), rnorm(120)) One dummy solution...

How colorize Circles in a plot in MATLAB?

I have a MATLAB code as follows: MinVal = -1; MaxVal = 1; MaxRadius = 0.5; nCircles = 5; Dimension = 2; Circles = zeros(nCircles, Dimension); Radius = zeros(nCircles, 1); for i = 1 : nCircles Circles(i,:) = unifrnd(MinVal, MaxVal, [1, Dimension]); Radius(i) = unifrnd(0, MaxRadius, 1); end t =...

Why is my rectangle being drawn wrong?

I'm trying to draw a rectangle around my screen. Here's my code: let viewRect = SKShapeNode(rect: self.view!.frame) viewRect.strokeColor = SKColor.whiteColor() viewRect.lineWidth = 2.0 addChild(viewRect) I'm using self.view!.frame instead of self.frame because my scene is not the same size as my screen (the scene is stretched to fill my screen). I...

Relationship between AFX_WM_DRAW2D and WM_PAINT in MFC Application

What is the relationship between the two messages in the subject? When exactly the AFX_WM_DRAW2D is passed to application queue. I am asking because I have encountered the strangest recursive call of AFX_WM_DRAW2D handler. Whenever I am trying to paint something inside the AFX_WM_DRAW2Din compatibe render target the handler is...

Java Unicode character displaying box instead of Runic letter

I am trying to draw random Nordic runes in a little Java game, but all I'm getting back is a square character. public class MyComponent extends JComponent { public void paintComponent(Graphics g) { String s = "\u16A8"; g.drawString(s,50,50); } } What the character should be displaying: What it's actually...

how to create a 3D height map in python

I have a 2D array Z that stores the height at that element's position. Other than using the method here in which I need to create array X and Y with the same size as Z, are there any simpler methods to create a 3D height map? The 3D surface...

Safe frame calculation

How safe frame is calculated in 3ds Max. I want to know the relationship between Viewport width and height, Render width and height(aspect ratio) in the calculation of safe frame width and height. My final goal is to find the distance between top left corner of the plane and top...

Pygame 3D: How to and is it possible?

So I want to program a 3d-mesh viewer in pygame, no other 3rd-party modules wanted (panda3d is perfect, but it's very complicated). My idea is: list_of_surfs = {'85 50':'70deg'} #the 85 50 and the dimensions of the #side/surf, and 70 deg of rotation to be able to see it, then...

picture box crossed out C#

I have a project in which I draw several rectangles using GDI. I do it using i++ from i=0 to i<=10. I use e.Graphics.FillRectangles. I refresh the drawn rectangles every 1/10s by calling Graphics.Invalidate() My problem is that my picture box gets crossed out when drawing more the 4 rectangles....

Animation not adding to JFrame

I'm new to java swing, so forgive me if my mistake is extremely obvious. What my code is supposed to do here is create one JFrame and animate two boxes moving upwards through the frame side by side. However, I'm seeing only one box (the blue box created by the...

Transparent RichTextBox with Graphic not showing Text

I have the following code working, and commented out the Text being drawn onto the control as I started out using this as a graphic only control. Moving on, I have switched the control to be RichTextBox instead of Control so that I can have all the goodies that come...

How to calculate a random point inside a cube

I'm trying to figure out the math to find a random point inside a cube. I have something small but it can't take into account the rotation of the cube. Here are some images of my results. Here you can see the cube is rotated to some degree but when...

How to create an indent in shaped control that allows painting on indented region?

I have a custom control, which I am applying a shape to. The shape has a pointer (similar to the message indicator in Skype that shows if the message was a received message, or a sent message) that is on the left or right side. When the indicator is on...

How to upscale and render remote(RGB565) frame buffer on Android native?

I have ported remote frame buffer receive C code on Android 4.2.2 which receives frame buffer from host in RGB565 format. Able to render the received framebuffer following the standard android example frameworks/native/services/surfaceflinger/tests/resize/resize.cpp. Following is the code snippet used sp<Surface> surface = client->createSurface(String8("resize"), 800, 480, PIXEL_FORMAT_RGB_565, 0); SurfaceComposerClient::openGlobalTransaction(); surface->setLayer(100000); SurfaceComposerClient::closeGlobalTransaction();...

Simultaneous Rotate and Translate not working as expected in javafx

I have built the following "system" from Circles and a Line. I am trying to implement just following two transitions in the system. When the Green Circle is dragged, both the Green and Blue circle should rotate about the Red center, in the direction of drag. When the Red center...

AttributeError: '_Screen' object has no attribute 'mainloop'

I'm designing a simple Python program that uses the Turtle graphics module to draw lines on the screen with the arrow keys. import turtle turtle.setup(400,500) # Determine the window size wn = turtle.Screen() # Get a reference to the window wn.title("Handling keypresses!") # Change the window title wn.bgcolor("lightgreen") # Set...

Why will my geometry not appear? (jMonkeyEngine)

I'm just now picking up jMonkeyEngine and I've encountered an issue I can't seem to solve. In the simpleInitApp method in the main class, I can use the following code to successfully render a box: Box playerBase = new Box(Vector3f.ZERO,1f,1f,1f); Geometry playerBaseGeom = new Geometry("playerBase", playerBase); Transform fixBaseHeight = new...

3D Lines disappear sometimes

I am building 3d line chart from data here is the code Demo the part of code that generate line is parentTransform = new THREE.Object3D(); var _color = d3.scale.category10(); for (var i = 5; i > 0; i--) { var material = new THREE.LineBasicMaterial({ // color: 0x0000ff,linewidth: 30 color: _color(i),...

Can the OpenGL 'deprecated' functions possibly be unsupported?

I am testing with glDrawPixels to port my simple pixel-drawn 2D game from Windows API to OpenGL with GLFW. It runs nicely with FPS over 100, additionally cross-platform. Just one thing that is slightly annoying me is that I'm using a deprecated feature. I don't see any problems now, but...

Interactive bend image

I'd like to transform image in web browser this way -> more precisely, it should be 3D effect (like wrap the image around can). I'm considering these options: CSS3 transform (is it possible with matrix3d somehow?) HTML5 canvas (I don't have any experience here yet) applet or flash (this would...

Make Camera LookDirection look front face

How to look at the front of 3D Model in WPF? I am confused to set X Y Z for LookDirection. I don't know what happens when I set xyz and I don't know where camera is looking at. I don't know the same thing for UpDirection. Below is my...

C++ GUI Challenge

Recently I was challenged by a friend to create a snake game much like the classic Nokia version using the C++ language. I have been programming in Java, but unlike Java, C++ doesn't seem to have standard gui libraries. Therefore after looking into GUI for C++ many different api are...

How to implement .png pics in a JFrame?

What I want to do is making a window, a GUI, and putting an image in it. I watched a YT tutorial ( and copied everything similar but the Window I make has no image at all. I tried different file types like .jpg and different window sizes, matching he...

creating a 3d array in python does not create array correctly

I wish to make a 3d array by appending each element to the array in a loop, but instead of getting a 3d array I just get a 1d array with more elements in it. I'm working in Python 2.7 I want to get labels = [1,34,u'te],[2,44,u've],[4,43,u'ht] My code so...

How can I convert PNG to GIF keeping the transparency?

How can I convert PNG to GIF keeping the transparency? I would have hoped that using the Assign( ) method would work but it doesn't seem to migrate transparency. In the GIF, it's represented as black. png:=TPngImage.Create; try png.LoadFromFile(sFile); // comes from file: png.TransparencyMode; // comes from file: png.Transparent //...

How to make a Javafx Image Crop App

I am building an application for my colleagues to crop image. I use FXML with Scene Builder to build the GUI. The user click a button to choose a image from his computer. Then, the image is shown in the GUI. User can zoom and move in the pane. At...

Errors trying to add rectangles to JPanel

I am trying to draw a grid of rectangles on a JPanel that already has a few JButtons on it. I get a big list of errors when I try to run it. Here's my code: package GameOfLife; import java.awt.Dimension; import java.awt.Graphics; import java.awt.Graphics2D; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.awt.*;...

Buttons and paint method

I'm having trouble with my buttons. I know they're working because I've tested them out by exiting the problem through System.exit. Here is what my output looks like: When I click the close button, the handle on the switch should redraw to the other side and the close button...

Spotlight with shadows becomes square-like

I've been following a two part tutorial on shadow mapping from OGLDev (part 1, part 2) for a couple of days now, and I've nearly finished implementing it. My problem is that when I enable shadow maps the illuminated region which shadows appear in appears as a "strip" and I'm...

Finding 3D coordinate of object

I try to find 3D coordinate (in world )of abject that I know his coordinate in image .so after some research in internet I succed to find X and Y cordinate. but I can't find Z that is my program in openCV void drawAndCalcul3D(int x,int y,Mat& frame) { cv::Mat uvPoint...

Why is Java Graphics not painting?

I'm a bit new to programming right now and am trying to make Pong in java. However I'm not able to make any graphics show up. Main Class public class Pong1 { public static Frame frame = new Frame(); public static Panel panel = new Panel(); public static void main(String[]...

Why am I getting a QWidget error?

I have recently found this person's code that I could possibly be able to use for my project but I'm still pretty new to Python so I'm having a really rough time understanding the code and the error that keeps occurring even though the code is exactly the same as...

Applying rotation to Graphics object

I have very little experience programming with graphics objects. I am currently tasked with exporting a document (.tiff image) with redacted annotations. The redacted annotation is just a black rectangle object. I am able to get the x coordinates, y coordinates, width and height properties through the .XMP data. There...

Transform rhombus defined by corners to another rhombus

If you have a 2D model in the shape of a rhombus, defined by it's four corners, and you want to transform it into the shape of another rhombus, given it's 4 corners, how would you do this? Can you do it with a transformation matrix? My line of thinking...

Plot multiple frames of different size on the same window

Consider this example: par(mfrow=c(2,3)) frame() image(matrix(1:100, nrow=100), main="my wide plot", axes=FALSE) frame() plot(rnorm(120), rnorm(120), main="plot 1") plot(dpois(0:20, lambda=6), type="b", main="plot 2") x = rnorm(100) y = x+runif(100, 10, 12) plot(x=x, y=y, , main="plot 3") How can I do to make my first graph (image(...) titled my wide plot) to occupy...

how to refresh JFrame after after adding java 2d components

in this code i added two components to the jframe and also used revalidate and repaint but only one of the components is being viewed. i need a way to refresh the jframe class A extends JPanel{ int i ,j; A(int i,int j){ this.i = i; this.j = j; }...

JavaFX 8 Transform to pitch, yaw and roll rotation angles

Implementing the answer from this thread I have this code that translates the deltayaw, deltaroll and deltapitch angles into one angle and rotates a node around it. The angles that are taken as the parameters are momentary changes of angles since giving the whole angles would ignore the changes in...

Draw a sphere on a billboard with world normal from a pointlist

I am drawing spheres on billboards by passing center world positions via a StructuredBuffer and use the geometry shader to build a billboard facing the camera. The sphere is drawn correctly and I can figure out the UVs. Now I would like to light it but I cannot figure how...

GDI+ curve “overflowing”

I'm currently using GDI+ to draw a line graph, and using Graphics.DrawCurve to smooth out the line. The problem is that the curve doesn't always match the points I feed it, and that makes the curve grow out of the graph frame in some points, as seen below(red is Graphics.DrawLines,...

Converting 2D images to 3D

I was trying to convert 2D images to 3D by rotating them about the axes (like a circle to a sphere). Currently my problem is that suppose I have two functions f(x) and g(x) both in one variable. I wish to make a plot of the functions and use rotation...

MATLAB: How to make camera light follow 3D Rotation

I have come into a problem recently when trying to rotate 3D objects. I am building a GUI and I have a separate figure where an object is plotted. In the figure, I allow the user to use MATLAB's built-in rotate button to move the object around. However, I am...

What does the terms Sampling,Scanline Mean in Raster Graphics(Bresenham's Algorithm)

Im a novice when it comes to computer graphics.Im trying to learn Bresenham's Scanline algorithm. It says Pixels positions along a Line are determined by sampling at unit X intervals What exactly does this sampling mean,in layman's terms. Then it says Plot the pixel whose scan line value is closest...

Blurring in PyGame

I'm working on a short intro in PyGame, and I need to blur some static lines. After two days of searching, I can't find anything. Does PyGame have a built-in method to blur a shape or surface? Will I need to do it manually? What would be the best way...

Creating new shape palettes in ggplot2 and other R graphics

I'd like to specify my own shape palettes for ggplot2 at least as a vector for input into scale_shape_manual. I really like the paired shapes palette from JMP, but noticed R doesn't have some of these shapes. In particular, sideways triangles (e.g. |> or <|) or a filled upside down...

Unity WebPlayer “Failed to initialize player's 3D settings”?

I am trying to execute one of Daqri's AR demos, but I keep getting "Failed to initialize player's 3D settings" ...error every time I try to run the demo (Which is essentially a webpage). I am using unity 5.0.0f4 and even 4.5.3f3 (As a tried to implement a fix that...