Generating surface normals

• US 6,867,773 B2
• Filed: 05/13/2002
• Issued: 03/15/2005
• Est. Priority Date: 05/13/2002
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Hux, William A.
• Primary Examiner(s): Nguyen, Kimbinh T.
• Application Number:
  US10/145,265
• Publication Number:
  US 20030210243A1
• Time in Patent Office: 1,037 Days
• Field of Search: 345/419, 345/420, 345/421, 345/424, 345/427, 382/154, 382/205
• US Class Current: 345/424
• CPC Class Codes: G06T 15/50 Lighting effects
• CPC Class Codes: G06T 17/10 Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A method of determining neighboring voxels that contribute to a surface of an object includes evaluating a primary voxel that corresponds to a side of a reference voxel. The side of the reference voxel is adjacent to an outside voxel, which is outside the object. The primary voxel is adjacent to the outside voxel and is adjacent to a corresponding secondary voxel. The secondary voxel is age adjacent to a corresponding tertiary voxel. The method also includes determining whether the primary voxel, the secondary voxel or the tertiary voxel is on the same surface as the reference voxel.

Claims

1. A method of determining neighboring voxels that contribute to a surface of an object, comprising:

evaluating a primary voxel corresponding to a side of a reference voxel, side of the reference voxel being adjacent to an outside voxel, the outside voxel being outside the object, the primary voxel being adjacent to the outside voxel and adjacent to a corresponding secondary voxel, the secondary voxel being adjacent to a corresponding tertiary voxel; and

determining whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as the reference voxel;

wherein determining whether the primary voxel the secondary voxel or the tertiary voxel is on a same surface as the reference voxel comprises picking the primary voxel in the primary voxel is inside the surface of the object unless the corresponding secondary voxel is outside the surface of the object and the corresponding tertiary voxel is inside the surface of the object.

2. The method of claim 1, further comprising evaluating up to eight primary voxels for each side of the reference voxel that is attached to the outside voxel.

3. The method of claim 2, further comprising using a three by three by three (3×

3×

3) volume of voxels to include the eight primary voxels, the corresponding eight secondary voxels, and the corresponding eight tertiary voxels, the reference voxel being in the center of the 3×

3×

3 volume.

4. The method of claim 1, wherein determining whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as reference voxel comprises picking the secondary voxel if the primary voxel is outside the surface of the object and the secondary voxel is inside the surface of the object.

5. The method of claim 1, wherein determining whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as the reference voxel comprises picking no voxels if the corresponding secondary voxel is outside the surface of the object and the corresponding tertiary voxel is inside the surface of the object.

6. An apparatus comprising:

a memory that stores executable instructions for determining neighboring voxels that contribute to a surface of an object; and

a processor that executes the instructions to;

evaluate a primary voxel corresponding to a side of a reference voxel, the side of the reference voxel being adjacent to an outside voxel, the outside voxel being outside the object, the primary voxel being adjacent to the outside voxel and adjacent to a corresponding secondary voxel, the secondary voxel being adjacent to a corresponding tertiary voxel; and

determine whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as the reference voxel;

wherein determining whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as the reference voxel comprises picking the primary voxel if the primary voxel is inside the surface of the object unless the corresponding secondary voxel is outside the surface of the object and the corresponding voxel is inside the surface of the object.

7. The apparatus of claim 6, wherein the processor executes instructions to evaluate up to eight primary voxel for each side of the reference voxel that is attached to the outside voxel.

8. The apparatus of claim 7, wherein the processor executes instructions to use a three by three by three (3×

3×

3) volume of voxels to include the eight primary voxels, the corresponding eight secondary voxels, and the corresponding eight tertiary voxels, the reference voxel being in the center of the 3×

3×

3 volume.

9. The apparatus of claim 6, wherein the processor determines whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as the reference voxel by picking the secondary voxel if the primary voxel is outside the surface of the object and the secondary voxel is inside the surface of the object.

10. The apparatus of claim 6, wherein the processor determines whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as the reference voxel by picking no voxels if the corresponding secondary voxel is outside the surface of the object and the corresponding tertiary voxel is inside the surface of the object.

11. An article comprising a machine-readable medium that stores executable instructions for determining neighboring voxels that contribute to a surface of an object, the instructions causing a machine to:

evaluate a primary voxel corresponding to a side of a reference voxel, the side of the reference voxel being adjacent to an outside voxel, the outside voxel being outside the object, the primary voxel being adjacent to the outside voxel and adjacent to a corresponding secondary voxel, the secondary voxel being adjacent to a corresponding tertiary voxel; and

determine whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as the reference voxel;

wherein determining whether the primary voxel, the secondary voxel or tertiary voxel is on a same surface as the reference voxel comprises picking the primary voxel the primary voxel is inside the surface of the object unless the corresponding secondary voxel is outside the surface of the object and the corresponding tertiary voxel is inside the surface of the object.

12. The article of claim 11, further comprising instructions causing the machine to evaluate up to eight primary voxels for each side of the reference voxel that is attached to the outside voxel.

13. The article of claim 12, further comprising instructions causing the machine to use a three by three by three (3×

3×

3) volume of voxels to include the eight primary voxels, the corresponding eight secondary voxels, and the corresponding eight tertiary voxels, the reference voxel being in the center of the 3×

3×

3 volume.

14. The article of claim 11, wherein instructions causing the machine to determine whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as the reference voxel comprises instructions causing a machine to pick the secondary voxel if the primary voxel is outside the surface of the object and the secondary voxel is inside the surface of the object.

15. The article of claim 11, wherein instruction causing the machine to determine whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as the reference voxel comprises instructions causing a machine to pick no voxels if the corresponding secondary voxel is outside the surface of the object and the corresponding tertiary voxel is inside the surface of the object.

16. A method of determining neighboring voxels that contribute to a surface of an object, comprising:

evaluating a primary voxel corresponding to a side of a reference voxel, the side of the reference voxel being adjacent to an outside voxel, the outside voxel being outside the object, the primary voxel being adjacent to the outside voxel and adjacent to a corresponding secondary voxel, the secondary voxel being adjacent to a corresponding tertiary voxel; and

determining whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as the reference voxel;

wherein determining whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as the reference voxel comprises picking the secondary voxel if the primary voxel is outside the surface of the object and the secondary voxel is inside the surface of the object.

17. The method of claim 16, further comprising evaluating up to eight primary voxels for each side of the reference voxel that is attached to the outside voxel.

18. The method of claim 17, further comprising using a three by three by three (3×

3×

3) volume of voxels to include the eight primary voxels, the corresponding eight secondary voxels, and the corresponding eight tertiary voxels, the reference voxel being in the center of the 3×

3×

3 volume.

19. The method of claim 16, wherein determining whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as the reference voxel comprises picking the primary voxel if the primary voxel is inside the surface of the object less the corresponding secondary voxel is outside the surface of the object and the corresponding tertiary voxel is inside the surface of the object.

20. The method of claim 19, wherein determining whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as the reference voxel comprises picking no voxels if the corresponding secondary voxel is outside the surface of the object and the corresponding tertiary voxel is inside the surface of the object.

21. An apparatus comprising:

a memory that stores executable instructions for determining neighboring voxels that contribute to a surface of an object; and

a processor that executes the instructions to;

evaluate a primary voxel corresponding to a side of a reference voxel, the side of the reference voxel being adjacent to an outside voxel, the outside voxel being outside the object, the primary voxel being adjacent to the outside voxel and adjacent to a corresponding secondary voxel, the secondary voxel being adjacent to a corresponding tertiary voxel; and

determine whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as the reference voxel;

wherein determining whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as the reference voxel comprises picking the secondary voxel if the primary voxel is outside the surface of the object and the secondary voxel is inside the surface of the object.

22. The apparatus of claim 21, wherein the processor executes instructions to evaluate up to eight primary voxels for each side of the reference voxel that is attached to the outside voxel;

and.

23. The apparatus of claim 22, wherein the processor executes instructions to use a three by three by three (3×

3×

3) volume of voxels to include the eight primary voxels, the corresponding eight secondary voxels, and the corresponding eight tertiary voxel, the reference voxel being in the center of the 3×

3×

3 volume.

24. The apparatus of claim 21, wherein the processor determines whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as the reference voxel by picking the primary voxel if the primary voxel is inside the surface of the object unless the corresponding secondary voxel is outside the surface of the object and the corresponding tertiary voxel is inside the surface of the object.

25. The apparatus of claim 24, wherein processor determines whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as the reference voxel by picking no voxels if the corresponding secondary voxel is outside the surface of the object and the corresponding tertiary voxel is inside the surface of the object.

26. An article comprising a machine-readable medium that stores executable instructions for determining neighboring voxels that contribute to a surface of an object, the instructions causing a machine to:

evaluate a primary voxel corresponding to a side of a reference voxel, the side of the reference voxel being adjacent to an outside voxel, the outside voxel being outside the object, the primary voxel being adjacent to the outside voxel and adjacent to a corresponding secondary voxel, the secondary voxel being adjacent to a corresponding tertiary voxel; and

determine whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as the reference voxel;

wherein determining whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as the reference voxel comprises picking the secondary voxel if the primary voxel is outside the surface of the object and the secondary voxel is inside the surface of the object.

27. The article of claim 26, further comprising instructions causing the machine to evaluate up to eight primary voxels for each side of the reference voxel that is attached to the outside voxel;

and.

28. The article of claim 27, further comprising instructions causing the machine to use a three by three by three (3×

3×

3) volume of voxels to include the eight primary voxels, the corresponding eight secondary voxels, and the corresponding eight tertiary voxels the reference voxel being in the center of the 3×

3×

3 volume.

29. The article of claim 26, wherein instructions causing the machine to determine whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as the reference voxel comprises instructions causing a machine to pick the primary voxel if the primary voxel is inside the surface of the object unless the corresponding secondary voxel is outside the surface of the object and the corresponding tertiary voxel is inside the surface of the object.

30. The article of claim 26, wherein instructions causing the machine to determine whether the primary voxel, the secondary voxel or the tertiary voxel is on a same surface as the reference voxel comprises instructions causing a machine to pick no voxels if the corresponding secondary voxel is outside the surface of the object and the corresponding tertiary voxel is inside the surface of the object.