Browse Prior Art Database

Tentative Edge Classification Using Truth Tables

IP.com Disclosure Number: IPCOM000035423D
Original Publication Date: 1989-Jul-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 4 page(s) / 40K

Publishing Venue

IBM

Related People

Halbert, AR: AUTHOR [+2]

Abstract

This article describes an efficient time saving mechanism for tentative edge classification in a Constructive Solid Geometry (CSG) solid modelling system by using truth tables. First discussed is tentative edge generation and classification in general, followed by how truth tables and relmaps may be used to implement the classification.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 47% of the total text.

Page 1 of 4

Tentative Edge Classification Using Truth Tables

This article describes an efficient time saving mechanism for tentative edge classification in a Constructive Solid Geometry (CSG) solid modelling system by using truth tables. First discussed is tentative edge generation and classification in general, followed by how truth tables and relmaps may be used to implement the classification.

One procedure for generating a wire frame picture from a CSG model involves several steps, basically: - recursive subdivision of the viewing space to produce simplified (pruned) models for the convex (usually rectangular) subvolumes thereby produced (voxels) -drawing edges for the simplified models within the voxels The drawing process involves two steps: -generating tentative edge segments - deciding whether a tentative edge segment corresponds to a real edge

There is a trade-off between the amounts of work to be performed by recursive subdivision and within the routine which actually draws the picture. As the drawing routine is made more efficient, some of the work that was previously most efficiently performed by recursive subdivision is now more efficiently passed to the new drawing routine. Thus, any improvement in this routine gives a disproportionately large improvement to the overall process. Tentative Edge Segment Generation

The figure shows the basic principle of edge segment generation. Voxel: -1 < x < 1, -1 < y < 1, -1 < z < 1 Model: (x < = 0) int (x > = -2) int (y < = 0) int (x > = - 2) int (z < = 0) int (z > = -2)

The intersection line yz of primitives (y < = 0) and (z < = 0) is the parameterised line T -> (T,0,0).

Intersections of yz with the voxel are at T0 = -1 (point(-1,0,0) and T1 = 1 (point (1,0,0)). The intersection with the boundary of primitive (x < = 0) is at Tx = 0 (point(0,0,0)).

We have two potential edge segments. -The left one (T0 < T < Tx) is a true edge -The right one (Tx < T < T1) lines fully outside the model.

The routine is called for a given voxel with a truth table node which contains: -pointers at up to five primitives - a truth table representing the boolean operation combining these primitives.

The primitives are all fairly flat within the voxel, and are replaced by planar approximations at the start of the draw process. The draw process then generates the set S of tentative edges within the voxel as follows: initially S is empty for each primitive pair i,j: 1. work out the intersection line ij (a point on this line is represented by a parameter T) 2. clip ij to the voxel to give parameters T0 and T1 3. if line ij does not intersect voxel, move to next i,j 4. for each remaining primitive k not equal to [i,j], work out parameter Tk for intersection of ij with k 5. sort the set of intersection parameters to give a list of segments T0, Tk1, ... , T1 (each interval in the list represents a tentative edge

1

Page 2 of 4

segment to be added to S). Tentative edge classification Each edge generated by the procedure above...