Generate the maximum capacity 3D box that can be inscribed within a set of points

I am working with a 3D mesh composed of a collection of 3D points (vertices) and a series of faces (connections between points).

Q1 Is there a method to determine the largest inscribed box (volume) that can fit inside the mesh?

[OP]

Greetings everyone, I appreciate any assistance you can provide. I am utilizing vectors to generate three-dimensional shapes. I am seeking guidance on identifying the most sizable box that can be accommodated within the object. For example, if we have a sphere, how can we determine the largest box that fits inside it? Alternatively, if we have a 3D arrow, what approach should be taken to find the largest enclosed box? I possess arrays containing all the vectors utilized to construct these objects and am eager to discover a means of utilizing these arrays to locate the most extensive box that fits within the created structures.

javascript3dthree.jsgeometry

Answer №1

  1. To determine if a generic point is inside your mesh, you must perform a hit test on your faces.

    Instead of dealing with lines, consider the faces of your mesh and handle them as

    • planes defined by 2 basis vectors and 2 parameters (2D plane subset)

    Find the intersection, convert to 2D parameters, and verify if they fall within the valid range of the face.

  2. Next, calculate the bounding box of your mesh.

    Simply determine the minimum and maximum values for each axis based on your vertex points, which will give you the maximum size of your polygon.

  3. It's not possible to solve your task algebraically for generic meshes, so

    You'll need to resort to brute force and heuristics. For instance, use the "generate and test" method to generate all valid solutions and choose the largest among them. While finding the optimal solution by trying all possibilities is unfeasible due to infinite combinations, you can aim for an approximation. Integration of a Voxel map can significantly enhance performance in this process.

    Heuristics involve testing only certain solutions based on task knowledge or exploiting specific aspects of the dataset. For example, if your mesh is symmetric, begin with centered and symmetric boxes aligned with the mesh, avoiding unwieldy, misaligned options.

  4. Create a Voxel map

    Given the bounding box, construct a 3D array that dissects your mesh volume into cubes and categorize each voxel as 0 (outside) or 1 (inside) the mesh.

  5. Develop a function to determine if a generic box is inside the mesh.

    Simply iterate through 3 nested loops for each voxel of the box, checking if all Voxels are set to 1 to confirm the box is inside.

  6. Create a box generator and tester

    Generate all possible valid boxes with a defined grid step (e.g., voxel size). For axis-aligned boxes, perform 6 nested for loops, calculating the volume and comparing it to the current solution:

    • If the volume is not greater, skip and proceed to the next box
    • If the volume is larger, execute the function outlined in bullet #5
    • If the box is inside, record it as the new solution

  7. By the end, you'll have an approximation of your solution.

  8. Enhance precision by increasing the voxel count (utilize smaller voxels) post bullet #7

    For example, double the number of voxels per axis. Now, test boxes within +/- 1 voxel from the found solution. This recursive approach can help achieve the desired accuracy.

[Additional Notes]

If your box is arbitrarily oriented, incorporating 3 more dimensions (angles) increases complexity significantly. Consider rotating the mesh to align the box with the axes by identifying the largest inscribed line and adjusting the mesh accordingly. The initial filling style of the Voxel map influences whether the solution touches the surface.

Similar questions

If you have not found the answer to your question or you are interested in this topic, then look at other similar questions below or use the search

please transmit the id (or retrieve the id from the router path)

I have a basic blog built with React/Redux for the frontend, featuring user registration and articles. I ran into an issue when trying to pass the article ID to the editor component. The form is the same, but the paths differ for adding new articles and ed ...

javascriptreactjsreduxreact-router

Functionality that can be utilized repeatedly

I've been struggling to implement a feature for repeatable blocks in my web form. The issue I'm facing is that when I click the buttons, nothing happens even though they work fine when tested in the console. I've been stuck on this problem f ...

javascriptjqueryhtml

Creating a switch statement that evaluates the id of $(this) element as a case

I have a menu bar with blocks inside a div. I am looking to create a jQuery script that changes the class of surrounding blocks in the menu when hovering over a specific one. My idea is to use a switch statement that checks the ID of $(this) and then modif ...

javascriptjqueryhtmlcssswitch-statement

Revamp the website's design

I am looking to revamp the color theme of my website with just a click of a button. Can someone provide me with a link to a reference website where I can get some inspiration? ...

javascriptcssajax

I encountered a 404 Error message while attempting to access a specific express route

My Angular CLI generated app is running with an Express.js and MongoDB server. After running npm start, I can access http://localhost:3000, which routes to my homepage. The other links on the navbar work well to control routes, e.g., http://localhost:3000/ ...

javascriptangularjsnode.jsexpressangular-ui-router

Creating a line of functions pool in Javascript with a delay feature

Recently, I created a code snippet that simulates a function line. It involves calling functions such as fn1, delay, fn2, delay, and so on. The idea is to call a function, remove it from the line, have a short sleep, and repeat. However, I've encount ...

javascriptjqueryfunctionlinepool

Using absolute positioning on elements can result in the page zooming out

While this answer may seem obvious, I have been unable to find any similar solutions online. The problem lies with my responsive navbar, which functions perfectly on larger screens. However, on mobile devices, the entire website appears zoomed out like thi ...

javascripthtmlcssreactjsnext.js

Transform a complex PHP array into JSON format using JavaScript

I have a three-tiered PHP array with both numeric indices and key-value pairs. I would like to convert it to JSON, and reiterate through the object list. How would I do this? The PHP array is called $main_array, and appears as: Array( [0] => Arra ...

javascriptphpajax

The Angular Material date picker unpredictably updates when a date is manually changed and the tab key is pressed

My component involves the use of the Angular material date picker. However, I have encountered a strange issue with it. When I select a date using the calendar control, everything works fine. But if I manually change the date and then press the tab button, ...

javascripthtmlangulartypescriptangular-material

What is the best way to insert a permanent script tag into the body of a Gatsby site? Can conditional rendering be used to control

As an illustration: - const nation = "USA" import chat from './utils/script'; // script is imported from a file if(nation === "USA") // utilized conditionally in the component { chat } else { console.log("Not USA") } inform me witho ...

javascriptreactjsgatsby

Having trouble locating the web element within a div popup while utilizing Node.js and WebdriverIO

I need assistance with a seemingly simple task. I am currently learning webdriverjs and attempted to write a short code to register for an account on the FitBit website at URL: www.fitbit.com/signup. After entering my email and password, a popup appears as ...

javascriptnode.jsseleniumselenium-webdriver

Retrieving data from a database using PHP and presenting it in a loop for showcasing in JavaScript

I am currently working on a code and trying to achieve the following output: { title:"<?php echo $sender_fullname; ?>", mp3:"link", }, I want to display this in JavaScript using PHP. // Include database require_once "db.php"; // Get email ...

phpjavascriptmysql

Tips on expanding the background beyond the boundaries of a parent container with a specific width limit

Could you please take a look at the code snippet below? I am dealing with a situation where I have a container with a fixed width, and inside that container, there are rows whose width exceeds that of the parent container. Some of these rows have a backgro ...

javascripthtmlcssreactjs

Is there a way to enable hover functionality on mobile devices? I wish for the hover effect seen on desktop to be triggered automatically on mobile devices

I attempted to implement @media (hover: hover) without success. In my design, I have three images in a row that reveal a text overlay when hovered over with a mouse. However, the issue arises when I try to switch to a mobile view, as the images remain un ...

javascripthtmljquerycssbootstrap-5

Inject "incorrect" information using jQuery

I am dealing with the following constellation: <dl> <dt>Content</dt> <dd>123</dd> <dt>Content</dt> <dd>123</dd> <dt>Content</dt> <dd>123</dd> </dt> ...

javascriptjquery

Cutting imagery to create a new design element

https://i.sstatic.net/IAh0h.jpg There is an image above with 6 gears (circles with pointy edges). My goal is to separate them into individual pictures and, on each picture's hover, have a relevant line with text appear. How can I achieve this? The a ...

javascripthtmlcss

Classify JavaScript Array Elements based on their Value

Organize array items in JavaScript based on their values If you have a JSON object similar to the following: [ { prNumber: 20000401, text: 'foo' }, { prNumber: 20000402, text: 'bar' }, { prNumber: 2000040 ...

javascriptjqueryjson

Jquery refuses to conceal a particular element

I've encountered this issue before, but I'm facing a problem this time. I'm attempting to create a popup that is initially hidden. When clicked, the popup does appear, but I'm unable to close it. Additionally, when trying to change the ...

javascriptjqueryhtmlcss

Javascript is not functioning properly when making an ajax call

Having a bit of trouble with JavaScript not working after an Ajax call. Everything functions normally until new data is fetched from the database or an Ajax call is made. The issue seems to be that the JavaScript doesn't load properly. Any help would ...

phpjavascriptjqueryhtmlajax

Extracting multiline value from a textarea using JavaScript

I'm trying to extract a multiline value from a textarea using JavaScript or jQuery and store it in a cookie. Below is the code snippet I am using: HTML: <textarea id="cont" cols="72" rows="15"> JavaScript: var txt = $('#cont').val( ...

javascriptjqueryhtmlcookies